A kettős szimplex módszer
Kettős szimplex módszer.
A kettős szimplexes módszer érzése abban a tényben rejlik, hogy a közvetlen probléma helyett a szokásos szimplex módszerrel megoldható. Ezután a kettős probléma megoldásával az egyenes optimális megoldása megtalálható. Ehhez egy-egy egyeztetés jön létre a vonal változói és a kettős probléma között. A közvetlen probléma kezdeti változóit kettős kettős változó társítja, és az eredeti probléma további változói a vonal probléma kezdeti változóira vannak leképezve.
Tegyük fel, hogy megoldjuk a kettős problémát, és megkapjuk az optimális szimplex táblázatot. A közvetlen probléma optimális megoldását az F-sor együtthatói határozzák meg. A közvetlen probléma változóit a kettős probléma optimális szimplex táblázatának F-sorában levő megfelelő nem bázikus változók koefficienseihez hasonlítjuk. A fennmaradó változók nulla. A legegyszerűbb a kettős szimplex módszer alkalmazása abban az esetben, ha a közvetlen probléma korlátai száma sokkal nagyobb, mint az ismeretlenek száma, valamint az egész programozási problémákban.
1. példa A dual simplex módszer alkalmazásával oldja meg a következő problémát:
A probléma egyenlőtlenségeit csökkentjük a ≥ jelre, megszorozzuk az első, a második és a negyedik korlátot (-1); akkor a kettős probléma modellje a következőképpen alakul:
A 3. táblázat szerinti megoldás. 2, optimális. Írjuk le a vonalváltozók és a kettős probléma közötti megfelelést. Ha a közvetlen probléma korlátai az egyenlõségek formájához vezetnek, akkor az x3 kiegészítõként jelenik meg. x4. x5. x6.
Az F-vonalon az y1 nemváltozóváltozókra együtthatók vannak. y2. Y5. y4. Találjuk meg a közvetlen probléma optimális megoldását:
Az x5 változó. a y3-nak megfelelő. és x2. amely y6-nak felel meg. egyenlő nullával.
min F (y) = max F (x) = 6.
Így a párhuzamos problémák egyikének megoldása a szimplex módszerrel automatikusan megszerzi a másik megoldását.