Szimplex módszer megoldására LP problémák
A célfüggvény együtthatók oszlopon Sa rögzített azonos indexek alapjául vektorok.
Oszlop F0 rögzített pozitív elemei az eredeti támogatási program abban eredményeként számítás kapott pozitív komponensek optimális tervet. Az oszlopok P1 ... Pn rögzített korlátozás tényező az ismeretlen.
Az (m + 1) -edik sor: F0 - aktuális értéke a célfüggvény; Pj oszlopok írt számokat.
1. LP problémát a kanonikus és megtalálni a kezdeti támogatási program.
2. Töltsük fel a kezdeti simplex asztalra.
3. Határozza meg, hogy van-e legalább egy negatív szám # 916; j a (m + 1) -edik sor. Ha nem, akkor talált támogatási program optimális.
4. Keresse meg a legkevésbé negatív # 916; j, és a megfelelő oszlop nevezzük permisszív. Ha a kiadás oszlopban a számok aij nem pozitív, a célfüggvény nem korlátozódik az első és az LP probléma nincs megoldás.
5. Keressen egy kapcsolat bi aij pozitív megoldása oszlopban. A legkisebb ilyen kapcsolatokat határozza meg a felbontást a sor.
6. A metszi a sor és oszlop lehetővé meghatározzák lehetővé elem.
7. Minden eleme felbontású vonalak osztják engedélyező elem.
8. Minden elemek lehetővé teszik oszlopon (mellett lehetővé tevő tag) van helyettesítve nullákkal.
9. A fennmaradó elemeit a táblázat számítjuk ki a szabály egy téglalap, és van rögzítve a bevezetése egy új változó alapján. Ebben az esetben a felbontás sor adja meg a változó, amely ki van zárva az alapja, és lehetővé teszi az oszlop - egy olyan változót vezetünk be az alapja.
10. Folytatás a 3. lépéssel.
Ez a referencia terv * X = (0; 8; 20; 0; 0; 96) van optimalizálva, mivel minden # 916; j nem-negatív.
A maximális érték a függvény egy optimális döntés:
Fmax = 0 + 8 · 9 × 10 + 20 × 16 + 0 + 0 · 0 · 0 · 0 + 96 = 400
Egyéni feladatok. Oldja meg a problémát LP szimplex módszer. Options feladatokat veszi az egyéni feladatok a fenti 1.1.
1.3. Mesterséges alapon módszer.
Általában vezetés után a VP probléma kanonikus alakja, hogy írjon közvetlenül támogatják a terv nem sikerül, mert között vektorok Pj. Nem m egységes. Ebben az esetben, LP probléma megoldódik egy mesterséges alap.
Nyilatkozat a problémát. Szükséges, hogy megtalálják a legnagyobb a függvény
de ezek között a vektorok Pj nem m egységes.
Definíció. A probléma, ami abból áll, hogy meghatározzuk a maximális függvény
az úgynevezett kiterjesztett kapcsolatban az eredeti probléma (1,10), (1.11).
M itt van néhány nagy pozitív számok, amelyek értéke nincs beállítva.
Kiterjesztett probléma (1,12), (1,13) van egy támogatási terv:
Változók xn + 1. xn + 2 ... xn + m nevezzük mesterséges, és a rendszer egység vektorok Pn + 1. Pn + 2 ... Pn + m mesterséges formák alapján.
Ha az optimális terv kiterjesztett probléma (1,12), (1,13) értékei a mesterséges változók nulla, - van egy optimális forrást probléma (1,10), (1.11).
Ezért a folyamat megoldására LP probléma (1,10), (1.11) a következő lépésekből áll:
1. Annak érdekében, hogy az eredeti probléma kiterjesztett típusú probléma (1,12), (1,13).
2. Keresse meg a támogatási programot a kiegészített probléma.
3. A szimplex módszer kizárják a mesterséges számítások alapján vektor. Az eredmény egy olyan támogatási program az eredeti probléma. Ha mesterséges változókat kizárt alapján nem lehetséges, akkor a LP probléma megoldhatatlan.
4. A eredeti problémát talált támogatási program (1,10), (1.11), illetve a szimplex módszerrel az optimális tervét, vagy állítsa unsolvability
Példa. Keresse meg a minimum
Képviseli a probléma kanonikus formában: