Optimalitás állapot támogató program - studopediya

Táblázat nézet ZLP. Simplex - asztalra.

ZLP szimplex módszer SOLUTIONS

3.1. Általános jellemzők és főbb állomásait simplex - módszer

Az alapítók a szimplex módszer egy szovjet matematikus LV Kantorovich és az amerikai matematikus, John. Danzig.

A szimplex módszer használható megoldani minden ZLP vagy észlelni megoldhatatlan. Sok különleges ZLP osztályok is megoldható más, hatékonyabb módszereket ezen osztályok. Azonban az az előnye a szimplex módszer - az egyetemesség. Szinte az összes számítógépes programok célja a szabványos megoldások ZLP simplex - módszer.

Bemutatjuk egy általános képet a szimplex módszer.

Hisszük, hogy a ZLP rögzítik a kanonikus formában és az objektív függvény minimalizálását. Mint már tudjuk, az optimális tervet kell törekedni között a támogatási programok ZLP. A szimplex módszer nem támogatja az összes tervek (ami gyakran nem lehetséges, mert a nagy számú), és abból kiindulva némi kezdeti támogatási program, azt következetesen át más támogatási programok csökkent a célfüggvényt. Szimplex módszer nem működik, ha akár azt találtuk, hogy az optimális támogatási program vagy meghatározott oldhatatlansága a problémát.

A döntés ZLP szimplex módszer a következő lépésekből áll:

1) hozza ZLP kanonikus formában;

2) így a lineáris egyenletrendszer a Jordan formában nem negatív jobb oldalán egyidejű ellenőrzése ZLP oldhatatlansága miatt ellentmondás van a rendszer lineáris megszorítások;

3) tanulmányozza a támogatási program optimalitást;

4) Tanulmány ZLP megoldhatatlannak miatt határtalansággal alján a SDT a célfüggvény;

5) Az átmenet egy új, „jobb” támogatási program.

Annak érdekében, hogy csökkentse és egyszerűsítse a rekordokat a döntést ZLP szimplex módszer az úgynevezett simplex asztalra. Ahhoz, hogy a szimplex tábla ZLP kell, hogy a táblázat nézet. Itt van, hogyan.

Hagyja ZLP írt kanonikus alakja (2,3-2,5). Hogy ZLP a táblázat rendszer (2.4) kell először okoz Jordan formában nem negatív jobb oldalán. Tegyük fel, hogy a Jordan forma formájában (2.6). Fejezzük (2.6) keresztül szabad alapváltozó:

Behelyettesítve a célfüggvény (2.3) helyett az alapvető változók, expressziós keresztül szabad változók képletekkel (3.1), kizárva ezzel az objektív függvény alapváltozó. A célfüggvény formájában:

Táblázatos formában az objektív függvény van írva a következő:

Vegye figyelembe az alábbi funkciókat ZLP táblázatos formában:

a) a lineáris egyenletrendszer adják a Jordan forma nemnegatívak jobb oldalán;

b) a célfüggvény az alapvető változók vannak zárva, és meg van írva a forma (3.3).

Most viszont, hogy a leírás a szimplex tábla. Hagyja ZLP rögzített táblázatos formában:

Aztán töltött simplex asztalra néz ki.

Referencia ZPL terv :. Ez az úgynevezett támogatási program ennek megfelelő táblázatot simplex. Amint látható, a általános képletű (3,2), az értéke a célfüggvény a referenciasík egyenlő # 947; 0.

Vegyünk egy példát. Hogy az asztalra a következőt jelenti, és töltse ZLP simplex táblázat:

Kezdetben ZLP kell hozni a kanonikus formában. Ehhez a funkcióhoz fnuzhno helyébe - az f:

Az egyenletrendszert kell írni, a Jordán formában nem negatív jobb oldalán. Összességében vétel, amellyel ez megvalósítható minősül később (lásd 3.7). Példánkban ez Jordan formában már változó, és az alap. Mi távolítják el az alapvető változók a célfüggvény - f. Ebből a célból, hogy kifejezzük őket a szabad és helyettesíteni ezeket a kifejezéseket a célfüggvényt.

Táblázat nézet ZLP következőképpen:

Töltsük simplex asztal (rekordok csökkenti az első oszlop címe: „B”, az utolsó oszlop - „Q”).

Az érték a célfüggvény a referencia sík, a megfelelő simplex táblázat 6. Mi írjuk a célfüggvényt táblázatos formában, ahol. Mivel minden lehetséges megoldást ZLP változók csak nem negatív értékek az utolsó rekord a célfüggvény látható, hogy annak értéke bármely pontján az SDT nem kevesebb, mint 6 Ezért a minimális érték a célfüggvény az SDT 6, és ez megvalósítható a vonatkoztatási sík, megfelelő szimplex tábla.

3.4. Feltétel unsolvability ZLP miatt határtalansággal alján a SDT a célfüggvény.

Ha ZLP simplex asztal tele van, az SDT nem üres feladat, ezért a támogatási program, amely megfelel a szimplex tábla tartozik SDT. Azonban ZLP lehetnek oldhatatlanok miatt az SDT nem korlátos alatt a cél funkciót.

Az a feltétel, formálhatók a döntésképtelenség.

Ha a szimplex tábla tartalmaz legalább egy oszlopot, amely eltér a szélsőjobb, melynek alsó sorban érdemes egy pozitív szám, és az összes többi sor az oszlop - nem pozitív szám, a ZLP megoldhatatlan miatt SDT korlátos alatt a cél funkciót.

Ahhoz, hogy újra példát használja tanulmány.

Az oszlopot az alsó sorban tartalmaz egy pozitív szám, és a többi sor - nem pozitív szám. Lássuk be a döntésképtelenség ZLP.

Írunk Jordan alakja megfelel simplex asztal és transzfer feltételeinek tartalmazó, a jobb oldalon. megkapjuk

Legyen egy - bármilyen pozitív szám. Nyilvánvaló, ZLP a következő lehetséges megoldást :. Mi az A értékét a célfüggvény ugyanakkor megvalósítható megoldás. Táblázat 3.4, van:

. Ahol jelezzük lehetséges megoldás f = 4 - 2a. Ebből látjuk, hogy az érték a célfüggvény lehet tetszőlegesen kicsi elég nagy a. Más szóval, az objektív függvény nem korlátos alatt S & DT. Következésképpen ZLP megoldhatatlan.

3.5. Az átállás az új támogatási programot.

Tegyük fel, hogy a optimumfeltételekbe és a döntésképtelenség nem teljesülnek. Ezután a szimplex módszer költözik egy új támogatási programot. Ez az átmenet miatt törlik az alapja az egyik alapvető változók és a bevezetés alapján az egyik szabad változók. A következő két feltételnek kell teljesülnie:

1) új alapokra még érvényesnek kell lennie, azaz a jobbra az megfelel a Jordán formában kell még nem negatív;

2) ha új referenciaérték a célfüggvény szempontjából nem haladhatja meg a korábbi érték a referencia síkra.

Oszlop simplex táblázatot, amelyben van egy változó be a bázis, az úgynevezett általános oszlopot. A string, amelyben van egy változó kimenet a bázis, az úgynevezett általános vonal. Elem metszéspontjában az általános vonal és az általános oszlop, az úgynevezett Általános elemet.

Általános szabály a választott elem.

A pozitív szám áll, mint egy általános oszlopban válassza bármelyik oszlop a szimplex tábla eltér a szélsőjobb, ami az alsó sorban. csak a sorok a szimplex táblázat ezután megkülönböztetendő az alsó, amelyben a keresztezi az általános oszlopon pozitív számok. Állandó a mester minden egyes oszlopban az ilyen vonalak számított állandó kifejezés kapcsolódik az elem. String, amelyek az aránya a minimális van kiválasztva, mint az általános. Elem metszéspontjában az általános vonal és az általános oszlop és az akarat az általános elem.

Hadd illusztráljam ezt a szabályt példával.

Mivel választani lehet egy oszlopra vagy egy oszlop általános oszlopot. Mi választjuk ki (leggyakrabban választhat az oszlopot, amelyben az alján egy nagy pozitív szám). Most folytassa a választás az általános vonal. Ehhez tartjuk két sorban - és. Van egy arány 4: 2 és 8: 3. Ugyanilyen fontos az arány 4: 2, ezért úgy döntünk, az első sorban, mint általában. Következésképpen, az általános elem 2 - ez a kereszteződésekben a oszlop és sor.

Miután kiválasztotta a General tételt el kell menni egy új támogatási program, amelyben a változó az alap és a változó x1 - ingyen. Az együtthatót az új Jordán formában kell lennie 1-gyel egyenlő Ezért a táblázat első sorában 3,5 osztva 2, majd megszorozzuk a kapott első sor a (3), és hozzátéve, hogy a második sor, kizárják a második egyenletből. Hasonló módon, az eljárás Jordan szabályt, és a harmadik egyenlet a célfüggvény (az utóbbi igényel táblázatos nézet ZLP).

Ennek eredményeként megkapjuk az alábbi táblázat tartalmazza.