Szabályai a szerkezet két problémát - studopediya
Minden lineáris programozási feladat, amit úgy hívunk eredeti. Meg lehet ellátni illő más lineáris programozási feladat az úgynevezett kettős hozzá. Együttesen ezek a feladatok alkotják egy pár kölcsönösen kettős problémák, és ezek közül bármelyik lehet tekinteni, mint egy kiindulási pont. Megoldása egy ilyen probléma, hogy lehetséges olyan megoldás, és egyéb feladatokat.
A kettős probléma - egy kiegészítő lineáris programozási probléma kapjuk a megfelelő szabályok közvetlenül a kezdeti feltételek.
Megfogalmazzuk a szabályokat az építési két problémát:
1. Ha a cél f függvény az eredeti probléma maximális, akkor a kettős célfüggvény z - minimalizálható, és fordítva.
2. A számos korlátozást (m) egyenlő a számát az eredeti probléma a kettős változók és mennyisége változó (n) egyenlő a kezdeti mennyiségét a kettős korlátok. Változók jelöli kettős problémájának yi (i = 1, m).
3. Mivel a változók az eredeti probléma a kettős korlátok, minden változó xj> = 0 megfelel a kettős problémájának formában korlátozás "<=» (z→max) или «>= »(Z → perc), és fordítva.
4. Minden változó xj. nem korlátozódik a jel megfelel a korlátozás az űrlap „=” kettős probléma, és fordítva.
5. Szabad tagok korlátozza a kezdeti probléma, bi (I = 1, m) a duális a együtthatók a változók yi (I = 1, m) a célfüggvény és az együtthatók Cj (j = 1, n) a változók xj (j = 1 , n) az objektív függvényben az eredeti probléma mentes tagjai kettős korlátok.
6. Egy mátrix együtthatók az ismeretlenek a korlátai az eredeti probléma a kettős átültetett (A t).
Tekintsük az általános formája az egyik különösebb problémát a lineáris programozás, amely ellátja az eredeti:
Kettős hogy ez a probléma a következő lenne:
Ha alkalmazza a szabályokat építési kettős probléma, megkapjuk az eredeti probléma.
Az 5. táblázat mutatja bizonyos típusú kiindulási lineáris programozási problémák mátrix formában, és megfelelő kettős problémákat. Keresztül Y = (y1. Y2, ..., ym) jelöli a mátrix sor ismeretlen kettős probléma. Row mátrix Y megszorozzuk balról az oszlopon B mátrix (a célfüggvény), és a mátrix (korlátot) szabályai alapján a szorzás a két mátrix, valamint a szabályok építése kettős problémák (különösen a kettős feladatát mátrix együtthatók az ismeretlenek a korlátozások ültetni).