Szimplex módszer megoldására optimalizálási problémák a lineáris programozás, a gazdaság BSEU - blog

Szimplex módszer - egy számítási eljárás elvén alapuló folyamatos javítása, hogy az átmenet az egyik referenciapont (bázis-oldat) a másik. Az érték a célfüggvény javul.

Az összehasonlító oldat egyik lehetséges megoldás, hogy vannak a csúcsai a megvalósítható régióban. Ellenőrzés az optimális felső csúcsok, megkapjuk a kívánt optimális. Ez az elv azon alapul, szimplex módszer.

Simplex - egy konvex sokszög n-dimenziós térben n + 1 csúcsot, amelyek nem fekszenek egy hipersík (hipersík osztja a teret két fele).

Például a vonal osztja a költségvetési megszorítások a haszon és érhetők el.

Ezt bizonyítja, hogy ha az optimális megoldás létezik, akkor szükségszerűen megtalálható egy véges számú iteráció (lépések), kivéve a „hurok”.

Szimplex módszerrel több szintből áll.

Az első szakasz. Beépített eredeti optimalizálási modell. További feltételek eredeti mátrixot alakítunk csökkentett kanonikus formában, amely az összes többi kanonikus formában megkülönbözteti az a tény, hogy a:

a) A jobb oldalán feltételek (szabad kifejezések bi) nem-negatív értékeket;

b) azokat a feltételeket maguk egyenletek;

c) egy mátrixot feltételek teljes azonosságot almátrix.

Ha a szabad kifejezések negatív, akkor mindkét oldalán a egyenlőtlenség szorozni-1 - és az egyenlőtlenség megfordul. Átalakítani egyenlőtlenségek figyelembe egyenletek további változókat vezetünk be, amely jellemzően az összeg fel nem használt forrásokat. Ebben, azt, hogy a gazdasági értelemben.

Végül, ha hozzá további változók feltételek mátrix nem tartalmaz teljes azonosságát részmátrixot, majd belépett a mesterséges változókat, amelyeknek nincs gazdasági értelme. Ezeket be csak azért, hogy a személyazonosság részmátrixot és megkezdi a probléma megoldásának a szimplex módszer.

Az optimális megoldás az összes mesterséges változók (SP) nullának kell lennie. Erre a mesterséges változókat vezetünk a célfüggvény a probléma a nagy negatív együtthatók (-M) a probléma megoldásában max, és a nagy, pozitív együtthatókat (M +), amikor a probléma megoldódik annyiban, min. Ebben az esetben, még egy kis értéke nem nulla változó mesterséges drasztikusan csökkenteni (növekedés) értéke a célfüggvény. Általában M-1000-szer nagyobbnak kell lennie, mint az értéke az együtthatók az alapvető változókat.

A második szakaszban. Beépített kezdeti simplex asztal és keresett néhány kezdeti lúgos oldat. A változók száma, amelyek egy egységet al-mátrixot tekintettük a kezdeti bázikus oldatot. Az e változók értékeit szabadon tagjai. Minden más extrabasis változó nullával egyenlő.

A harmadik szakasz. Ellenőrzés az alapvető megoldás optimalitást segítségével végzik a speciális együttható a célfüggvény értékeléseket. Ha minden a becsült együtthatók a célfüggvény negatív vagy nulla, akkor a meglévő alap megoldás - optimális. Ha legalább egy becslést az együttható a célfüggvény értéke nullánál nagyobb, a meglévő alap nem optimális megoldás, és javítani kell.

A negyedik szakaszban. Az átmenet az új alapvető megoldás. Nyilvánvaló, hogy az az optimális tervet kell megvalósítani, változó, amely növeli az objektív függvény a legnagyobb mértékben. Problémák megoldásában, a nyereség az optimális terv bevezetett termékek, amelyek termelése a legjövedelmezőbb. Ez határozza meg a maximális pozitív értéke a célfüggvény együttható becslése.

Oszlop szimplex tábla ezt a számot egy adott iteráció nevezzük általános oszlopot.

Továbbá, ha legalább az egyik eleme az általános oszlop aij0 szigorúan pozitív, akkor keresett általános vonal (különben a feladat nem optimális megoldás).

Ahhoz, hogy megtalálja az általános vonal minden ingyenes tagok (erőforrások) vannak osztva megfelelő elemek általános oszlopon (erőforrás-felhasználás mértéke egységnyi termék). Ezekből az eredményekből a legkisebb van kiválasztva. A megfelelő sorra az iterációs nevezik általában. Ez megfelel a forrás, amely korlátozza az adott iteráció.

Element simplex asztal, található a kereszteződésekben a oszlop és sor általános, az úgynevezett Általános elemet.

Ezután minden eleme az általános vonal (beleértve a konstans tag) vannak osztva általános elem. Ennek eredményeként ez a művelet, az általános elem válik egyenlő eggyel. Továbbá, szükséges, hogy az összes többi eleme az általános oszlop válna nullával egyenlő, azaz a Általános oszlop egyedinek kell lennie. Minden sor (kivéve általános) transzformáltuk az alábbiak szerint. A kapott elemei az új vonalak szorozni a megfelelő elem mester oszlopon és a terméket kivonjuk az elemek a régi vonal.

Új értékek alapváltozó szerezni az érintett sejtek oszlopon szabad feltételeket.

Az ötödik szakaszban. A kapott lúgos oldatot vizsgáljuk optimalitás (lásd. A harmadik lépés). Ha ez az optimális, akkor a számítások megszűnik. Ellenkező esetben meg kell találni egy új bázis oldatot (negyedik lépésben), és így tovább. D.

Példa megoldásának optimalizálási problémák a lineáris programozás szimplex módszer

Tegyük fel, hogy meg kell találni az optimális terv a termelés két típusú termékek (x1 és x2).