A kettős feladat - kidolgozása szabályokat - Linear Programming

Bemutatja a szabályokat, hogy a kettős probléma. Tartják szimmetrikus, aszimmetrikus és vegyes páros. Elemzett példák összeállításakor két problémát.

Dupla vagy konjugált lineáris programozási feladat megvan az a tulajdonsága, hogy a megoldások egyik feladata kaphat más feladatokat. Itt nézd meg a szabályokat kidolgozásánál két problémát.

Szimmetrikus kettős probléma

Tekintsük a lineáris programozás feladata a nem-negatív változók és az egyenlőtlenségek a rendszer korlátai a következő formában:
(1.1);
(1.2)
Itt van. van néhány számot. Minden rendszer vonal (1,2) az egyenlőtlenség karakterek.

A kettős probléma:
(2.1);
(2.2)
Itt a rendszer összes vonal (2,2) az egyenlőtlenség karakterek. Mátrix együtthatók a korlát rendszer (2.2) az átültetett mátrix a rendszer (1.2). Ez magában foglalja a sorok és oszlopok. A kettős probléma változó. Minden változó nemnegatív.

Az eredeti probléma (1) gyakran nevezik közvetlen kihívást jelent, és a probléma (2) - kettős. Ha a kiindulási, hogy a probléma (2), majd (2) fogja irányítani a feladatot, és a feladat (1) - kettős. Feladatok (1) és (2) nevezzük szimmetrikus kettős feladattal.

Így egy szimmetrikus kettős probléma lehet kialakítani, ha az összes változó az eredeti problémát, és a nem-negatív kényszer rendszer nem tartalmaz egyenletek. Ha a keresett legfeljebb az objektív függvény, az egyenlőtlenséget kell alakítani az űrlapot. Ha keres legalább egyenlőtlenségeket kell alakítani az űrlapot. Ha módosítani szeretné a jel, meg kell, hogy szaporodnak mindkét oldalán egyenlőtlenség -1.

Példa egy szimmetrikus kettős problémát

Mivel lineáris programozási feladat:
;

Készítsen kettős probléma.

A kezdeti probléma a feladat megtalálni a minimum. Ezért minden jelét egyenlőtlenség kell. Az első és a harmadik egyenlőtlenségek tartalmazza a jel. Szorozzuk őket -1:

Átírjuk a korlátozó rendszer, egyértelműen megjelölve az együtthatók a változók:

A rendszer korlátai együttható mátrix formában:

Átültetésének mátrix. Azaz az első sor lehet írva, mint az első oszlopban, a második sor felírható a második oszlopban a harmadik sorban felírható a harmadik oszlopban.

A kettős probléma:
;

Aszimmetrikus kettős probléma

A kihívás a maximális

Tekintsük a kanonikus lineáris programozási feladat maximális nem-negatív változók és egyenletek megszorítások a rendszer:
(3.1);
(3.2)
Itt van. van néhány számot. Minden rendszer tételek (3.2) általános egyenletet. Minden változó nemnegatív.

A kettős probléma:
(4.1);
(4.2)
Itt a rendszer összes vonal (4,2) az egyenlőtlenség karakterek. Matrix együtthatóit kényszer rendszer (4.2) a ültették mátrix rendszer (3.2). A kettős probléma változó. Változókat lehet pozitív vagy negatív.

Ellentétben aszimmetrikus pár problémák (3) és (4) egy szimmetrikus pár (1) és (2), hogy a rendszer korlátai (3.2) tartalmaz csak egyenlőséget, és a rendszerben (4.2) feltétel nélküli nonnegativeness változók.

A feladat legalább

Most tekintsük a kanonikus lineáris programozási feladat, hogy legalább:
(5.1);
(5.2)

A kettős probléma:
(6.1);
(6.2)

korlátozási rendszert (6.2) eltér (4.2), amelyek jelei egyenlőtlenség.

Kommunikáció a szimmetrikus pár kettős problémák

Megmutatjuk, hogy a kiegyensúlyozatlan pár problémák (3) - (4) úgy állíthatjuk elő, szimmetrikus pár (1) - (2).

Tételezzük fel, hogy van egy közvetlen probléma a célfüggvény
(3.1)
és korlátait a rendszer
(3.2)
Minden egyenlet leírható két egyenlőtlenségek:

Egyenlőtlenségek jelek szorozzuk -1:

A rendszer korlátai egyenlőtlenségeket.

By (1) - (2) megkapjuk a kettős probléma:
;

kettős probléma egy nem-negatív változók:
.
Könnyen belátható, hogy ezek a változók a probléma része formájában különbségek
.

Azt, hogy a helyettesítés
.
Mivel mind. A változók egyaránt lehet pozitív és negatív.

És megkapjuk a kettős probléma (4):
(4.1);
(4.2)

Ha vesszük az eredeti probléma (4) végző összes lépéseket fordított sorrendben, megkapjuk a kettős probléma (3).

Ugyanilyen módon lehet a probléma (5), hogy megkapja a kettős probléma (6), és a probléma (6), hogy megkapja a kettős probléma (5).

vegyes probléma

Most tekintsük a vegyes problémát.

Tegyük fel, hogy van egy közvetlen problémát (1) a maximális, egy olyan rendszerben, amely korlátozza az i-edik sor egy egyenlőséget. Ezután a kettős probléma formájában (2), egy kivétellel - a változó lehet pozitív vagy negatív. Ez azt jelenti, hogy nincs korlátozás.

Ugyanez történik, ha van egy közvetlen probléma (2) legalább a rendszerben, amely korlátozza az i-edik sor egy egyenlőséget. A kettős probléma a forma (1) egy kivétellel - a változó lehet akár jel.

Most tegyük fel, hogy van egy közvetlen problémát (1) a maximális, de nincs korlátozás. Vagyis a változó lehet pozitív vagy negatív. Ezután a két probléma van egy form (2) egy kivétellel - edik sorának korlátozási rendszert az egyenlőség.

Végül tegyük fel, hogy van egy direkt probléma (2) a minimum, de nincs korlátozás. Ezután a kettős probléma a forma (1) egy kivétellel - edik sorának korlátozási rendszert az egyenlőség.

Mindez lehetővé teszi számunkra olyan szabályok, hogy a kettős probléma.

Szabályzat készítés kettős problémák

1. az eredeti probléma, hogy a maximális, az összes egyenlőtlenség megszorítások a rendszer termel:
.
Az eredeti probléma, hogy legalább az összes egyenlőtlenség csökken:
.
Ha meg akarjuk változtatni a jel, majd szorozzuk mindkét oldalán egyenlőtlenség -1.
2. Hozzuk létre két probléma ugyanúgy, mint a szimmetrikus pár feladatokat.
3. Ha az eredeti probléma, én megszorítások a rendszer vonal egyenlőség, majd átmegyünk ki a feltétel nem negativitás th változó a kettős probléma.
4. Ha az eredeti probléma, nincs nemnegativitását feltétele az i-edik változó. A edik sorának a kettős probléma változó egyenlőtlenség jele az egyenlőségjel.

Példa a kevert kettős problémát

Mivel lineáris programozási feladat:
;

Készítsen kettős probléma.

A célfüggvény egy szabad tag 5. Annak érdekében, hogy azt a formát (2,1), akkor be egy változót, és adjunk hozzá az egyenlőséget. Akkor a probléma a következő lesz:

Ez a probléma a probléma találni egy minimum. Ezért minden jelét egyenlőtlenség kell. Harmadik egyenlőtlenségeket tartalmazó jel. Ezért megszorozzuk -1:

Átírjuk a korlátozó rendszer, egyértelműen megjelölve az együtthatók a változók:

A rendszer korlátai együttható mátrix formában:

Átültetésének mátrix. Azaz, az első sorban felírható az első oszlopban a második sorban felírható a második oszlop, és így tovább.

Építünk a kettős probléma mind szimmetrikus pár.
;

Csakúgy, mint az eredeti probléma 1., 2. és 4. sorban a rendszer korlátaira egyenletek, a változók kettős probléma. és bármilyen jel. Nem negatív változó csak. Ezért a feltételek nem negativitás változót a következő formában:
.

Csakúgy, mint az eredeti probléma, és változóknak tetszőleges jeleket, a 3. és 4. sor rendszer korlátai a kettős probléma van egyenletek.

Így a kettős probléma a következő formában:
;

A negyedik egyenletet. Cserélje ki a változó és annak értékét, megszorozzuk a harmadik sorban -1.