A kettős lineáris programozási feladat

Ezeket a feladatokat a következő tulajdonságokkal rendelkezik:

1. A direkt probléma megkeresi a legmagasabb a célfüggvény (lineáris forma), és a kettős probléma - legalábbis.
2. Az együtthatók a változók a célfüggvény az eredeti probléma mentes tagjai a kettős probléma megszorítások a rendszer. Ezzel szemben, az állandó szempontjából a rendszer határait közvetlen probléma - az együtthatók a változók a célfüggvény a kettős probléma.
3. Minden feladat rendszerének megszorítások formájában adják az egyenlőtlenségek, az összes azonos értelemben, azaz ha a maximális célfüggvény (közvetlen probléma) ezek az egyenlőtlenségek vannak írva a „kisebb vagy egyenlő”, és amikor a legkisebb (kettős feladat) - a jel „nagyobb vagy egyenlő”.
4. Az együtthatók a változók rendszerek korlátozások ismertetett mátrixok
   
   és
   
   amelyek ültették egymáshoz képest.
5. A számos egyenlőtlenség a rendszer korlátozza a közvetlen problémát egybeesik a változók száma a kettős probléma.
6. Feltételei nem negativitás a változók tárolják egy egyenes vonal. és a kettős problémát.

Két lineáris programozási feladat kielégíti a fenti feltételeket, az úgynevezett szimmetrikus kölcsönösen kettős problémákat.

Mi vezette őket hívni egyszerűen kölcsönösen kettős problémákat.

Közvetlen és kettős feladatot együttesen alkotnak egy pár egymással két problémát, ezek közül bármelyik lehet tekinteni, mint az eredeti, míg a másik az lenne, kettős.

Tehát megnéztük közötti levelezés az ősi és a kettős lineáris programozási feladat, eddig csak a problémák rögzítik a kanonikus formában. Megfogalmazzuk a problémát, amíg a szabályok kidolgozásának kettős képest az eredetit a kanonikus probléma (és később lépni a feladatot írt általánosságban):

1. Hogy az összes egyenlőtlenség a rendszer korlátai az eredeti probléma, hogy az egyenlőtlenségek az azonos értelemben (azaz az azonos jel): Ha a keresett legfeljebb a célfüggvény az eredeti probléma (lineáris forma) - meg vannak írva a „kisebb vagy egyenlő”, és ha legalább - a „nagyobb vagy egyenlő” jel. Mert ez az egyenlőtlenség, ahol ez a követelmény nem teljesül, szorozva mínusz egy.
2. A lemerült mátrix együtthatók a változók az eredeti probléma után kapott leírt átalakítások az előző bekezdésben, és a mátrixot alkotják A”, transzponáltja a mátrix
3. Alkotják a rendszer korlátai kettős probléma, figyelembe, mint az együtthatók a változók a mátrix elemeinek A”, és a szabad tagok - az együtthatók a változók a célfüggvény az eredeti probléma és írni az ellenkező értelemben az egyenlőtlenség (azaz a változás jele) képest egyenlőtlenségek lépésben kapott 1.
4. Alkotják a célfüggvény (lineáris forma) a kettős problémát azáltal az együtthatók a változók az eredeti probléma ingyenes tagok restrikciós rendszer lépésben kapott 1.
5. Azt jelzik, hogy szükség van, hogy megtalálják a megoldást a kettős probléma, nevezetesen a minimális célfüggvény, ha az eredeti probléma kérik maximum, és a legnagyobb, ha a minimum kérik az eredeti probléma.
6. Jegyezzük fel a feltétel nem negativitás a változók a kettős probléma.

1. példa: Készítsen egy feladat, kettős az alábbiak szerint: A maximálisan funkció kényszerek

Határozat. Harmadszor, az eredeti probléma egyenlőtlensége a rendszer nem felel meg az 1. bekezdés a rajzon fel a kettős probléma. Ezért szorozza meg negatív:

Ahhoz, hogy megkönnyítse a készítmény a kettős probléma jobb használni kiterjesztett mátrixot B. amelyek együtt az együtthatók a változók az eredeti probléma megszorítások a rendszer írja le a szabad feltételek és az együtthatók a változók a célfüggvény, kiválasztja az erre a célra egy további oszlop (elválasztva vonal) és a vonal (pirossal kiemelve) . Át kell ültetni B mátrix és a átültetni B mátrix”, feladata a kettős forrásból. Mátrixok B és B „jelentése a formában

Így a kettős lineáris programozási feladat csökkenti, hogy megtalálják a minimum egy függvény alatti megszorítások

Most rátérünk az esetben elkészítése kettős probléma, amikor a közvetlen problémát írt általános formája (rendszer korlátozásai egyenlőtlenség lehet a különböző karakterek, valamint egyenletek, nemnegativitását állapot változók nem szükséges). Az ilyen problémák, a következő szabályokat:

1. Ingyenes tagok közvetlen probléma - az együtthatók a célfüggvény a kettős problémát.
2. Az együtthatók a célfüggvény a közvetlen probléma - ingyenes tagok a kettős problémát.
3. Kiterjesztett mátrix közvetlen probléma - az átültetett mátrix terjeszteni a kettős problémát.
4. j-edik ismeretlen közvetlen tervezési probléma egy nem-negatív - j-edik egyenlőtlenség a kettős problémát egy „nagyobb vagy egyenlő”.
5. j-edik ismeretlen a direkt probléma korlátozás nélkül védjegy - j-edik kényszer kettős problémájának formájában egy egyenlet.
6. j-edik ismeretlen a nem közvetlen pozitív probléma - j-edik egyenlőtlenség a kettős problémát egy „kisebb vagy egyenlő, mint”.
7. i-edik egyenlőtlenség a közvetlen problémát egy „kisebb vagy egyenlő” - i-edik ismeretlen a kettős probléma nem negatív.
8. i-edik korlátozása közvetlen probléma formájában az egyenlet - i-edik ismeretlen kettős problémájának korlátozás nélkül jel.
9. i-edik egyenlőtlenség a közvetlen problémát egy „nagyobb vagy egyenlő” - i-edik ismeretlen a kettős problémájának nem pozitív.

2. példa: Készítsen egy feladat, kettős következők: megtalálni a függvény minimuma alatti megszorítások

Határozat. Mint látható, a direkt probléma van írva általánosságban. Meg kell figyelembe venni az elhelyezése jelek szempontjából a kettős probléma. És mégis, mint az előző példában, proizvedom univerzális értelemben - így a B mátrix a közvetlen problémát, és az átültetett B mátrix „a kettős probléma:

Így a kettős lineáris programozási feladat csökkenti, hogy megtalálják a legnagyobb a függvény alatti megszorítások

Az elmélet a kettősség lineáris programozás épült két alapvető tételei.

1. Tétel A közvetlen és a kettős problémát a hatalom egy és csak egy az alábbi állítások. 1. Ha az egyik feladat a lineáris programozás véges optimális, akkor a kettős feladatot is véges optimális, optimális értékeit lineáris formák egyaránt problémák ugyanaz, vagyis. E.F max = Z min iliF min = Z max. 2. Ha a lineáris forma egyik kettős problémák nem kizárólagosan, a feltételeket a másik cél is ellentmondásos. 3. Mindkét probléma nincs megoldás, hiszen a megszorítások a rendszer ellentmondásosak.

Mielőtt megfogalmazzuk a következő tétel, mi egy olyan összefüggés a változók eredeti és két problémát. Felkészülés: a játék követi a képlet, hogy az első alkalommal nem mindenki meg fogja érteni, de elolvasása után a 2. példában meg kell érteni mindent.

Megoldásában a szimplex módszerrel a kezdeti probléma a információs rendszer egyenlőtlenségek, hogy egyenértékű az egyenletrendszert meg kell adnia további m nem-negatív változók (száma egyenlőtlenségek a rendszerben a korlátok) x n + 1. x n + 2. x n + i. x n + m. ahol i = 1, 2; m értéke száma egyenlőtlenség, amelyben a további változó x n + i vezették be.

Rendszer korlátok kettős problémája áll n egyenlőtlenségek tartalmazó m változók. Ha megoldja ezt a problémát, a szimplex módszer, szükséges bevezetni n y m + 1 további nemnegatív változók. y m + 2. y m + j. y m + n. ahol j = 1, 2 n száma a rendszer az egyenlőtlenség korlátok a kettős problémát, amely-ben vezették be további y változó m + j.

Az összes fenti adtak annak megállapítása érdekében, a következő összefüggés a változók eredeti és két problémát lineáris programozás:

Azaz, a legfontosabb változó az eredeti probléma, a saját érdekében, megfelelnek a kiegészítő változó a kettős probléma is, abban a sorrendben jelennek meg. Az viszont, további változókat az eredeti probléma, a saját érdekében, megfelelnek a főbb változók a kettős probléma, abban a sorrendben jelennek meg.

Más szavakkal, minden egyes változó kezdeti X j kezdeti feladatként (j = 1, 2 n) van hozzárendelve további y változó m + j. bevezetett j-edik egyenlőtlenség kettős problémát, és az egyes kiegészítő változó x n + i az eredeti probléma (i = 1, 2 m), bevezetett egyenlőtlenség i -edik az eredeti probléma, - az eredeti Y változó i kettős probléma.

Az összes fenti, amint azt említettük, jobban érthető lesz, a 2. példa melyik lesz röviddel azután tételek 2.

Tétel 2.Komponenty optimális megoldások egyik feladata (közvetlen vagy kettős) az abszolút értékei együtthatók megfelelő változók szempontjából a célfüggvény (lineáris forma), hogy egy másik feladat (vagy kettős vonal), amikor eléri az optimális, és azzal a feltétellel, hogy a kapott oldat nem optimális degenerált.

Tételek 1. és 2. hogy ha megoldani az egyik kölcsönösen kettős lineáris programozási feladatok, azaz megtalálni az optimális megoldást, és az optimális célfüggvény, tudjuk írni a legjobb megoldás, és az optimális célfüggvény egyéb feladatokat. Most, egy példa arra, hogy ki fog alakítani az összes fenti a polcokon.

3. példa alapján a közvetlen döntések és két problémát lineáris programozás 1. példa érvényességét ellenőrizni tételek 1. és 2..

Az 1. példában a kiindulási feladatot kapott: megtalálják a maximum funkciót kényszerek

Tettünk ez kettős feladata van: megtalálni a függvény minimuma alatti megszorítások

A megoldás a direkt probléma szimplex módszer rendszer korlátait-egyenlőtlenségek csökkenteni egyenletrendszer által bevezetése további nem-negatív változók X 3. X 4. X 5. X 6:

Az olvasó ellenőrizheti, a probléma megoldásának a szimplex módszer. hogy a következő megoldásokat:

és a maximális a célfüggvény F max = 13,

míg maga az objektív függvény fejezzük

kettős probléma kényszer rendszer csökken egyenletrendszert bevezetésével további változó y 5. y 6:

A megoldás a kettős probléma szimplex módszerrel a következő választ:

és a minimális a célfüggvény Z min = 13

míg maga az objektív függvény fejezzük

Döntés a kettős problémát, azt látjuk, hogy az első rész 1. Tétel: kettős problémájának is, van egy véges optimális, Z min = F max = 13.

Tegyük meg arról, hogy az is igaz, a 2. Tétel Ehhez mi írjuk a változók az ősi és a kettős probléma, megfigyelésével lehetséges:

Mint látható, a fő változók az eredeti probléma, a saját érdekében, megfelelnek a kiegészítő változó a kettős probléma is, abban a sorrendben jelennek meg. Az viszont, további változókat az eredeti probléma, a saját érdekében, megfelelnek a főbb változók a kettős probléma, abban a sorrendben jelennek meg.

A célfüggvény kapott az utolsó lépés a megoldás a kettős probléma, kifejezve a változók ezt a problémát:

Figyelembe véve az együtthatók a változók y j a célfüggvény és figyelembe véve azok betartását az együtthatók az x i. Mi oldatot kapjunk (4; 1; 0; 5; 4, 0). egybeesik a megoldás a közvetlen problémát.

Megjegyzés. Miután megoldotta az közvetlen problémát, akkor azonnal kap egy megoldást a kettős lineáris programozás feladata. Ha kifejezetten az objektív függvény megoldásával nyerhető közvetlen problémát, keresztül az összes változó a probléma, megkapjuk

By 2. tétel, figyelembe véve az összefüggés a változók az ősi és a kettős problémákat, valamint figyelembe az abszolút értéke az együtthatók a változók, akkor megtalálja az optimális megoldást a kettős probléma (2/3, 0, 0, 7/3, 0, 0). Ahol Z min = F max = 13.

4. példa arról, hogy a rendszer korlátozza a közvetlen problémát

és a kettős probléma

Határozat. Kivonva a második egyenletet rendszer korlátai direkt probléma első egyenlet ugyanazt a rendszert. Kapjuk. Ez az egyenlet nincs megoldás, mivel. Így a rendszer korlátozza a közvetlen probléma ellentmondásos.

Üzembe az első két egyenlőtlenségek a rendszer korlátai a kettős probléma. Azt látjuk, hogy ez lehetetlen. Így a rendszer a korlátozások és a közvetlen, valamint a kettős problémát nem egyértelműek. 3. rész 1. Tétel kettősség, mindkét probléma nincs megoldásokat.

Nézzük újra az egyenes lineáris programozási feladat, és a kettős probléma.

Közvetlen probléma.
maximalizálása funkció