Simplex - módszer megoldására lineáris programozási feladatok
Bármilyen probléma lineáris programozási (LP) függetlenül a felvétel csökkenthető a standard és a kanonikus formában oldjuk meg a szimplex módszer, amely bizonyos értelemben egy univerzális módszer a PL. C algoritmus módszer iteratív jellegű.
Egy lehetséges megoldás a LP probléma azt mondják, hogy minden olyan megoldást, a korlátok (4.3) feltételeket kielégítő nem negativitás
Az ipari problémák matematikai modellek által vizsgált módszerek LP, mindig változó Xj (j =) arra vonatkozó előírása nem negatív változók.
Simplex - A módszer azon a tényen alapul, hogy ha a mátrix m sorból korlátozások és azok lineárisan független, akkor van egy sor m oszlop, úgynevezett alap, amelyek szintén lineárisan független. A beállított változó értékek megfelelő alap oszlopon, az úgynevezett egy lúgos oldat (referencia határozat támogatási program). Ha a rendszer korlátozásokat - egyenletek tartalmazott N változók Xj (j =) és annak rang egyenlő m, a szimplex módszert minden egyes iteráció találhatók értéke m alapváltozó kielégítő m lineáris megkötöttség és a maradék n - m változó úgynevezett szabad, és nullára állítjuk be .
Simplex módszer lehetővé teszi az átmenet az egyik alapvető megoldás egy másik helyettesítésével iterációk egy oszlopba alapját egy nem-bázikus oszlopot, amíg nincs megvalósítható megoldás találtuk, hogy megfelel a max (perc) a célfüggvény. Ez a megoldás az úgynevezett optimális.
A geometrikus értelmezése a szimplex - módszert, ha a feltételeket, a LP probléma konzisztensek, akkor a domain a megvalósítható megoldásokat képez konvex poliéder az I-dimenziós térben. Ebben az esetben a legjobb megoldás, ha létezik, feltétlenül elért néhány csúcsa a poliéder. Ahhoz, hogy megtalálja a megoldást, hogy a LP problémát, a terv megfelel a csúcsai a poliéder megengedett megoldások elég rendezni (támogató, az alapvető tervek).
C - a módszer lehetővé teszi a szabályos válogatás csúcsai a poliéder. Meghatározása után az egyik csúcsot, ez a módszer segít megállapítani, hogy a megtalált optimális tervet t. E. Akár történt a tetején a szélsőséges érték a célfüggvény. Ha nem optimális tervet, akkor az átmenetet a szomszédos csúcsa a poliéder, amely nem kevesebb (nem több) értéke a célfüggvény.
A munkaeszköz - módszerrel szimplex táblázatban. Ezt követően egymás után mozgó egyik asztalról a másikra, ennek eredményeként megkapjuk az optimális megoldást.
A probléma megoldása érdekében az asztali szimplex módszer, meg kell mutatnia azt a kanonikus formában, azaz a. E. A vezérlőegység kell jelei „egyenlő”, a jogot a nem-negatív számok, és az összes változó előírt követelmény nem negativitás.
Ha a rendszer tartalmaz egyenlőtlenség korlátok, minden egyenlőtlenséget kell alakítani az egyenletet további, vagy mérleg változók. Ezek bekerülnek egy változót minden egyenlőtlenség a „+” jel, ha az egyenlőtlenség £ jel, és a „-” jel, ha az egyenlőtlenség jele ³. Jellemzően a számozás folytatódik a számozás a mérleg változók alapváltozó a probléma. Ugyanezek a változók nulla együtthatók bekerülnek a célfüggvényt.
A kezdeti egyenletrendszer hasznos rekord vektor formában:
A konstrukció egy szimplex 1. táblázat a vektorok j kiválasztásához néhány vektorok, mely komponensek egy egységet képez mátrixot E.
Ha nincsenek ilyen vektorokat lehet használni az alábbi módokon:
1. Végezze m transzformációs rendszer Jordan - Gauss kényszer rendszer (4.3), hogy lehetővé tegye bármely változó tekintetében m. Az eredmény egy mátrix rendszer (4.3) m alapon vektor - oszlop j. azaz Vektorok, amelyekben az egyik koordináta értéke 1, és a többi - a nulla, ha az egységek különböző sorokban a mátrix. Megfelelő alapváltozó rögzített oszlop alapjait az első simplex asztalra.
2. Ha az eredeti rendszer tartalmaz korlátozásokat LP probléma az egyenlőtlenség a jele £, majd bevezetése további nem-negatív változók az átalakulás egyenlőtlenségek az egyenletben, azonnal megszerezni ezeket alap vektorokat, amelyek alapját képezik az első simplex asztalra.
3. Ha vannak jelei a korlátozások az eredeti egyenlőtlenségrendszer ³, a mérleg változókat vezetünk be a bal oldalon a „-” jel. A megfelelő vektort - oszlopában ennek a változónak lesz a következő koordinátákat:
Ebben az esetben, a vektorok hiányozni fog, melyek helye képezhet az egység mátrixot E az első bázis. Minden ilyen egyenlőtlenség, együtt az egyensúlyt a változó be egy másik változó (mesterséges): X # 945; 1. X # 945; 2.
Ezek a változók is kiszabott a követelmény nem negatív: X # 945; 1 ³ 0, X # 945; 2 ³ 0.
A célfüggvény ebben az esetben kerül bevezetésre egy további kifejezés a formában: ± M (X # 945; 1 # 945 + X 2 + X + # 945; m.), Ahol a "+" szimbólum használnak a minimalizálási problémát (F®min) "-" jelet a maximalizálás (F®max). M ³0 - egy nagyon nagy szám. A számítógép számítások rendszerint M = 10 17-én.
Eljárás a probléma megoldására az úgynevezett simplex - segítségével a mesterséges bázisok (kiterjesztett feladat). Simplex asztalok tele vannak, mint a szokásos simplex - módszer. Assertion: ha a referencia oldat (alap terv) a legjobb, az összes mesterséges változók nulla:
kiszámítása szekvenciáját a szimplex módszer, tekintsük a következő példát.
A cég nyersanyagforrásokkal, berendezések és a munkaerő előállításához szükséges bármely négyféle iparcikkek.
Háttér-információk feladatok
Termék típusa erőforrás típus
Ismert erőforrás költségek a termelési egység valamennyi típusú áruk, források, tartalékok, és az eredmény, amelyet az a gazdálkodó egységenként (táblázat. 4.1.).
Ahhoz, hogy meghatározzuk az optimális termékskála, profit maximalizálása és értékelése mind a négy típusú források tekintetében az optimális tartományban.
Bemutatjuk az x1. x2. x3. x4. - illetve a száma iparcikk típusú A, B, C, D, akkor a matematikai modell felírható
A probléma megoldása érdekében a szimplex - módszer átalakítani az egyenlőtlenség az egyenletben, megkapjuk:
Szerint a gazdasági tartalma a változók x5. x6. x7. x8 képviselik a fel nem használt összeg a megfelelő részesedés az egyes típusú, így a célfüggvény ezeknek a további változók szerepelnek nulla együtthatók.
Először simplex asztal tele a következő:
1. A felső sorban a táblázat írja ki az együtthatók az ismeretlen változók a célfüggvény az eredeti probléma.
2. 1. 2. n oszlopból lemerült együtthatók az x1. x2. xn az egyenletekben a rendszer korlátait.
3. Az oszlopot rögzíteni a jobb oldalán egyenletek korlátai.
4. A oszlopban bázisokat be azok a vektorok, amelynek koordinátái alkotják az egységet mátrixot E (alapon.).
5. Az oszlop bázisokat bevitt koefficiens az alapvető változók a célfüggvény.
6. Az alsó sorban a táblázat Zj - Cj = jbaz # 8729; j - Cj nevezzük az index karakterláncot vagy sorok száma, és használják, hogy teszteljék kapott a következő táblázatban megoldások optimalitást.
Fore simplex táblázat - első támogatási programot a probléma:
Ez megfelel annak a ténynek, hogy semmi nem történik, akkor az erőforrások nem használják, a profit - a célfüggvény értéke nulla, és nem a fő változók korlátait. Egy geometriai szempontból koordinálja a csúcsa a poliéder kapott (0, 0, 0, 0, 360, 400, 134, 96).
A probléma megoldása a fokozatos bevezetése terv kulcsfontosságú változó, egy-egy szakaszában a számítás, amíg egy optimális megoldást.
Először el kell dönteni, hogy a négy változót be az alapja. Mivel a probléma megoldódik, hogy a maximumot, akkor jobb, ha kezdeni egy jövedelmezőbb termék. A legjövedelmezőbb elemeket egy számot (50) index táblázat simplex vonal megfelel ez nagyobb abszolút nagyságát.
Határozza meg, hogy mennyi van kialakítva a az áru kiadása, ez függ a források és normák a költségeik. 1 nyers 180 kellően formájában egységek B (360 kg. 2 kg). 2 féle nyersanyag - a 20 egység a B termék (400. 20). elég idő, hogy finanszírozza a berendezések 16 (134 8) egység munkaerő - 8 (96. 12) az egységek B. Nyilvánvaló, hogy több mint 8 egység áruk nem lesz képes. Ezért a változó x3 szempontjából egyenlő 8 és bevezetésre kerül sor a változó x8. amelyek eltávolítják a bázis és nulla lesz. Hangsúlyozzák a 12-es számot, kereszteződésénél található a 3. oszlop x3 bemeneti változó és kimeneti változó húrok x8.
Ezt a számot nevezzük a legfontosabb megoldandó, a vezető tagja.
Tekintsünk egy második lépésben számítási táblázat 4. 2. Először számított vonal bemeneti változó, táblázatban megadott nyíl. Ez a vonal származik a kezdő sort X8 kiviteli alakban elosztjuk az összes elemet a vezetőelem, mivel ebben a tekintetben (1, 12), a változó x3 helyettesíti változó x8. Az oszlopot bázisok elhelyezett profit egységnyi B (50).
Kiszámítása után a vonal x3 újratervezi erőforrás oszlopban.
Nyersanyagok 1 faj csökken, kezdetben volt 360 kg egységnyi elfogyasztott takarmány áruk 2 kg. az előállított valamennyi (96. 12) egységek 8 ezért kihasználatlan marad takarmány formájában 1 lehet 344 kg, azaz a 360 - 96/12 # 8729; 2 = 344.
Hasonlóképpen: 400 - 96/12 # 8729; 20 = 240 kg - 2 fel nem használt nyers formában, 134 - 96/12 # 8729; 8 = 70 gép - h - nem használt időt fennmaradó berendezések alapja ..
Miután az oszlop lefordított erőforrásokat többi oszlop simplex asztalra.
Conversion rendszer (Jordan szabály - Gauss)
j - oszlop oszlop s-
Element Aij átalakítás után a szabály Jordan - alakítjuk Gauss a'ij elem. hol.
Ebben az esetben az összes elemet, amely lehetővé teszi az oszlop vannak nullák, kivéve a rezolváló elemet, amely egyenlővé válik egységét.
A probléma megoldása szimplex módszer
Elemek az index vonalat lehet számítani akár közvetlenül az általános képletű jbaz # 8729; j - Cj. vagy a szabály a Jordánia - Gauss. Az egyik szabály, hogy a számításhoz használt, és a többi - a kontroll. Az eredmény a második támogatási program: x1 = 0, x2 = 0, x3 = 8 x 4 = 0, X5 = 344 x 6 = 240, X7 = 70 × 8 = 0, és a értéke a nyereség - 400 d u. Egy geometriai szempontból, hogy az átmenet a tetején a poliéder a koordináták (0,0,8,0,344,240,70,0). Ezt követően ellenőriznie kell a tervet optimalitást. Erre látható index sort, és ha tartalmaz negatív elemeket, a terv lehet javítani. Mint látható, ez tartalmazza két negatív szám, amely azt jelzi, hogy a nyereség növelhető a bevezetés alapján változó x1 vagy x4. Változó x4 bevezetjük az alapja, mivel ez felel meg a legnagyobb abszolút értékű negatív szám - 27,5.
Ha az index vonal meghatározott kulcsoszlop j. amelyben minden elem negatív, az LP probléma nincs megoldás.
Miután építése a következő fázis 3 simplex táblázat index magában foglalja a csak a nullák és pozitív számok. Ez azt jelenti, hogy a harmadik terv nem lehet javítani, és a legjobb:
x1 = 0, x2 = 0, x3 = 6,25, 7 = x4, x5 = 319,5, x6 = 65, x7 = 0, X8 = 0; ilyen körülmények között, a termelést nem szerezhető nyereség több mint 592,5 g. egységek. Így az árukat kell lennie 6,25 egységek 7 r- és áruk egységek aminosavig nyersanyagot az első fajta és 319,5 kg a második fajta - 65 kg.