Keresés

Keresendő kifejezés:

Toplista

Toplista
  • betöltés...

Segítség!

Ahhoz, hogy mások kérdéseit és válaszait megtekinthesd, nem kell beregisztrálnod, azonban saját kérdés kiírásához ez szükséges!

Dualitás

névtelen_06 kérdése
37
Csatoltam képet.
Jelenleg 1 felhasználó nézi ezt a kérdést.
0
Felsőoktatás / Matematika

Válaszok

2
bongolo { Aranyérmes } megoldása
7.9. feladat:

Először nézzük, hogy mi a duálfeladat:

A célfüggvényben minimum van, tehát a primálfeladat egy minimumfeladat. A feltételek között van kisebbegyenlő, nagyobbegyenlő és egyenlő is, tehát ez egy általános feladat. Normál minimumfeladatnál nincs kisebbegyenlő, ezért alakítsuk át az első feltétel negálásával, az új feltételek ezek:
`{: (-x_1,,,+,x_3,≥,-22),(-2x_1,+,x_2,-,x_3,≥,4),(-4x_1,+,x_2,,,=,2):}`
`x_1, x_2, x_3 ≥ 0`

`2x_1+3x_2+x_3=z -> min`

Mátrixokkal:

`bar bar A=((-1,0,1),(-2,1,-1),(-4,1,0)), bar b=((-22),(4),(2)), bar c^T=((2,3,1))`

`bar bar A·bar x ≥ bar b \ \ \ ` (az első sor egyenlőség, azt nem részletezem most külön mátrixszal)
`bar x ≥ bar 0`
`bar c^T·bar x -> min`

Megjegyzés: Hivatalosan több mátrixszal kellene ezt felírni: az egyenlőség soroknak külön mátrix kellene, mert azokhoz olyan `y` változók kerülnek majd, amik lehetnek negatívak is. Nem akartam annyira elbonyolítani a mátrixokat, ezért pl. csak egy `bar bar A` mátrix van. Így is jó lesz az eredmény persze, csak a fenti mátrixos egyenlőtlenség nem teljesen igaz, és kicsit jobban kell figyelni, mikre jön ki előjelkorlát.

A minimumfeladatnak a duálisa maximumfeladat, ahol `x`-ek helyett más változók, `y`-ok vannak:

`bar bar A^T·bar y ≤ bar c`
`bar y ≥ bar 0 \ \ \ ` (`y_1`-re nincs előjelkorlát, mert az első feltétel egyenlőség volt)
`bar b^T·bar y -> max`

Vagyis kiírva részletesen:

`{:(-y_1,-,2y_2,-,4y_3,≤,2),(,,y_2,+,y_3,≤,3),(y_1,-,y_2,,,≤,1):}`
`y_2 ≥ 0, y_3 ≥ 0 \ \ \ ` (`y_1` előjele kötetlen)

`-22y_1+4y_2+2y_3 -> max`
-----------------------------------------

Ez lett tehát a duál feladat. Nézzük viszont az eredeti primálfeladat megoldását először:

A primál-szimplex algoritmus maximumfeladatot old meg. Ezért a célfüggvény minimuma helyett a negált célfüggvény maximumát keressük (az egyértelműség céljából ezt külön változóval, `ζ` zetával jelölöm majd, `ζ=-z`) :

`-2x_1-3x_2-x_3=ζ -> max`

Az eredeti feltételek pedig:
`{: (x_1,,,-,x_3,≤,22),(-2x_1,+,x_2,-,x_3,≥,4),(-4x_1,+,x_2,,,=,2):}`
és persze `x_1, x_2, x_3 ≥ 0`

Sehol sincs negatív szám a jobb oldalon, eddig jó. (Ha van, azt a sort negálni kell.)

Alakítsuk át az egyenlőtlenségeket egyenletté:
Ahol ≤ van, ott hozzáadunk egy nemnegatív számot és egyenlő lesz. (első sor, `u_1`)
Ahol pedig ≥ van, ott levonunk egy nemnegatív számot és úgy lesz egyenlő: (második sor, `u_2`)

`{: (x_1,,,-,x_3,+,bb(u_1),,,=,22)
,(-2x_1,+,x_2,-,x_3,,,-,bb(u_2),=,4)
,(-4x_1,+,x_2,,,,,,,=,2):}`
és persze `x_1, x_2, x_3, u_1, u_2 ≥ 0`
Ez a feladat kanonikus alakja.

Ennek a mátrixa (illetve táblázata) ilyen:
`((x_1,x_2,x_3,u_1,u_2,|,b),(1,0,-1,1,0,|,22),(-2,1,-1,0,-1,|,4),(-4,1,0,0,0,|,2))`
Az oszlopvektorok között egyetlen egységvektor van: `u_1`. (Az `u_2` oszlop nem egységvektor, mert mínusz 1 van 1 helyett.) Ezért be kell még két új változót is vezetni, hogy ne csak az `u_1` oszlopában, hanem mindenhol legyen olyan változó, ami egységvektor része:

`{: (x_1, , ,-,x_3,+,u_1, , , , , , ,=,22)
,(-2x_1,+,x_2,-,x_3, , ,-,u_2,+,bb(w_2), , ,=,4)
,(-4x_1,+,x_2, , , , , , , , ,+,bb(w_3),=,2):}`

(Van, aki ezeket is `w` helyett `u`-nak nevezi, csak valami módosító jelet tesz hozzá. Mondjuk `u^(**)` vagy `um`. És olyan is van, aki teljesen más logikával vezeti be őket, de szerintem ez, hogy muszáj legyen minden sorhoz egységvektor, egyszerűbb.)
Ezek a `w` segédváltozók, szemben az `u`-kkal, nulla értéket kell majd a végén felvegyenek, de menet közben még nincs ilyen kikötés. Ebben a feladatban kellett két ilyen `w`, ezért ezekhez fel kell venni a `w_0=w_2+w_3 -> max` segéd-célfüggvényt is; ezt kell majd első lépésben maximalizálni (kezdetben negatív lesz, maximalizálódik 0-ra, hisz a `w`-k nullák kell legyenek).

A tábla most ilyen:
`((x_1,x_2,x_3,bb(u_1),u_2,bb(w_2),bb(w_3),|,b)
,(1 ,0 ,-1 ,bb(1) ,0 ,bb(0) ,bb(0) ,|,22)
,(-2 ,1 ,-1 ,bb(0) ,-1 ,bb(1) ,bb(0) ,|,4)
,(-4 ,1 ,0 ,bb(0) ,0 ,bb(0) ,bb(1) ,|,2))`
A egységvektorok `u_1`, `w_2` és `w_3`-nál vannak. Ezek alkotják a kezdeti bázist; ezek nevét a tábla elejére kell írni a megfelelő sorba (ahol 1 a vektor értéke), az oszlopaik pedig kiesnek:
`(( ,x_1,x_2,x_3,u_2,|,b)
,(u_1,1 ,0 ,-1 ,0 ,|,22)
,(w_2,-2 ,1 ,-1 ,-1 ,|,4)
,(w_3,-4 ,1 ,0 ,0 ,|,2))`

Be kell írni a táblába még a `z` (pontosabban most `ζ`) valamint a `w_0` célfüggvényeket is. Rendezzük nullára a `ζ` célfüggvényt, úgy kerül be az utolsó sorba: `ζ+2x_1+3x_2+x_3=0`
`(( ,x_1,x_2,x_3,u_2,|,b)
,(u_1,1 ,0 ,-1 ,0 ,|,22)
,(w_2,-2 ,1 ,-1 ,-1 ,|,4)
,(w_3,-4 ,1 ,0 ,0 ,|,2)
,(- ,- ,- ,- ,- ,|,-)
,(ζ ,2 ,3 ,1 ,0 ,|,0))`

Megjegyzés: Van, aki a `ζ=-2x_1-3x_2-x_3` célfüggvényt úgy írja be a táblába, hogy az utolsó sor ez lesz:
`((-ζ,-2,-3,-1,0,|,0))`
Ez valójában azt jelenti, hogy úgy rendezett nullára, hogy `ζ` előjele negatív lett, az `x`-ek együtthatóinak előjele pedig megmaradt. Ekkor a generáló elem kiválasztásakor nem negatív, hanem pozitív számot kellene keresni a `ζ` sorában, egyébként minden változatlan. És persze az optimális értékként is `-ζ` értéke adódik majd a jobb alsó sarokban, amit negálni kell a végén.

Van még `w_0` segéd-célfüggvény is, aminek rendezett formája (ahogy be kell írni a táblázatba) ez: `w_0-w_2-w_3`: adjuk össze a `w_2` valamint `w_3` sorok számértékeit oszloponként, és azok negáltját írjuk a legutolsó sorba. (A `b` oszlopban is össze kell adni a `w` sorok értékeit, majd negálni: vagyis `w_0` negatívról indul, aztán a maximuma 0 lesz majd.) Ez lesz a végleges tábla:
`(( ,x_1,x_2,x_3,u_2,|,b)
,(u_1,1 ,0 ,-1 ,0 ,|,22)
,(w_2,-2 ,1 ,-1 ,-1 ,|,4)
,(w_3,-4,bb(1),0 ,0 ,|,2)
,(- ,- ,- ,- ,- ,|,-)
,(ζ ,2 ,3 ,1 ,0 ,|,0)
,(w_0,6 ,-2 ,1 ,1 ,|,-6))`

Első fázisban a `w_0` sorát kell báziscserékkel maximalizálni. Ennek hatására egy lehetséges megoldást kapunk (ami még nem lesz optimális):

Keressünk a `w_0` sorában negatív számot (persze nem a `b` oszlopban). Ez most az `x_2` oszlopánál van (-2), ezért `x_2`-t vonjuk be a bázisba az `u_1`, `w_2` vagy `w_3` helyébe (amik a vonal felett vannak). Azt lehet csak választani, ahol pozitív szám van a megfelelő sorban, most ez `w_2` vagy `w_3` lehet. Azt választjuk, amit ha a `b` oszlopbeli számot osztjuk ezzel, a legkisebb értéket kapjuk: ezek a hányadosok most `4/1` és `2/1`, a `w_3` nyert.

Ha több választási lehetőség is lenne, akkor:
- Egyrészt `u` sor helyett `w` sort érdemesebb választani, hisz a `w`-ktől akarunk megszabadulni.
- Másrészt azt a számot érdemes választani, amivel minél több szám is osztható; a legjobb persze az 1.

Tehát most a `w_3` és `x_2` vektorokat cseréljük meg a bázisban, a generáló elem ezen sor és oszlop metszéspontjában az `1`. A csere maga ezeket a lépéseket jelenti: (egy új táblába kell beírni a lépések eredményét)
- az új tábla fejlécei ugyanazok, csak `w_3` és `x_2` felcserélődik
- a generáló elem helyett a reciprokát vesszük (ez most 1/1=1)
- a sor többi elemét elosztjuk a generáló elemmel (most `1`-gyel)
- az oszlop többi elemét elosztjuk a generáló elem negáltjával (most `"-1"`-gyel)

Ez mindeddig ennyi:
`(( ,x_1,w_3,x_3,u_2,|,b)
,(u_1, ,0 , , ,|, )
,(w_2, ,-1 , , ,|, )
,(x_2,-4,bb(1),0 ,0 ,|,2)
,(- ,- ,- ,- ,- ,|,-)
,(ζ , ,-3 , , ,|, )
,(w_0, ,2 , , ,|, ))`

- a többi számot pedig mindenhol így számoljuk ki: mondjuk `v` a szám eredeti értéke, alatta vagy felette az eredeti táblában a generáló elem sorában `s` van, mellette a generáló elem oszlopában `o`, a generáló elem pedig `g`.
Az új érték `v-(s·o)/g`. Még egyszer: az eredeti táblából kell venni a `v, s, o, g` értékeket (egy téglalap sarkai...)

Az első báziscsere végeredménye ez lett, ellenőrizd:
`(( ,x_1,w_3,x_3,u_2,|,b)
,(u_1,1 ,0 ,-1 ,0 ,|,22)
,(w_2,2 ,-1 ,-1 ,-1 ,|,2)
,(x_2,-4, 1 ,0 ,0 ,|,2)
,(- ,- ,- ,- ,- ,|,-)
,(ζ ,14 ,-3 ,1 ,0 ,|,-6)
,(w_0,-2 ,2 ,1 ,1 ,|,-2))`
(`w_0` értéke (a `b` oszlopban) máris -6-ról -2-re nőtt.)

A becserélt `w_3` oszlopot el is lehetne hagyni, de most kell majd a duális feladat megoldásához. Ott hagyjuk, de ezt a vektort már nem visszük megint vissza a bázisba!! Akkor se, ha alatta a `w_0` sorban negatív szám lenne!

Lett másik negatív a `w_0` sorában (az `x_1` oszlopban a -2), tehát folytatni kell, a fentieket kell azzal is megtenni. A generáló elem most a `w_2` sorában a 2-es értékű elem. Az új tábla, már csak a végeredményt írom ide a báziscsere után:
`(( ,w_2,w_3 ,x_3 ,u_2 ,|,b)
,(u_1,-1/2,1/2,-1/2,1/2 ,|,21)
,(x_1,1/2 ,-1/2,-1/2,-1/2,|,1)
,(x_2,2 ,-1 ,-2 ,-2 ,|,6)
,(- ,- ,- ,- ,- ,|,-)
,(ζ ,-7 ,4 ,8 ,7 ,|,-20)
,(w_0,1 ,1 ,0 ,0 ,|,0 ))`

Nincs több negatív a `w_0` sorban (vagy ha lenne, de nincs felette pozitív generáló elem), ezért abba kell hagyni a báziscserét.

Vége van tehát az első fázisnak. Ekkor ilyen esetek lehetnek:
- Maradt negatív szám `w_0`-ban (mert nem tudtunk felette generáló elemet találni). Ekkor nincs lehetséges megoldás, így optimális sincs. (Most nem ez a helyzet.)
- Nincs negatív szám `w_0`-ban, de maradt a bázisban (bal oldalon fent) `w`. Ekkor sincs lehetséges megoldás, így optimális sincs. (Most nem ez a helyzet.)
- Nincs negatív szám `w_0`-ban, a `w_0` sor végén 0 érték van, és bal oldalon fent nem maradt `w` a bázisban. Ekkor a kapott tábla egy lehetséges, de még nem optimális megoldás. (Most ez a helyzet.)

Folytatjuk `ζ` optimalizálásával. `w_0` sorára már nincs szükség, elhagyjuk:
`(( ,w_2,w_3 ,x_3 ,u_2 ,|,b)
,(u_1,-1/2,1/2,-1/2,1/2 ,|,21)
,(x_1,1/2 ,-1/2,-1/2,-1/2,|,1)
,(x_2,2 ,-1 ,-2 ,-2 ,|,6)
,(- ,- ,- ,- ,- ,|,-)
,(ζ ,-7 ,4 ,8 ,7 ,|,-20))`

Most a megoldás második fázisában `ζ` sorában keresünk negatív elemeket, és a fentiekhez hasonlóan báziscseréket végzünk a talált oszloppal. Most viszont csak `w_2` oszlopában van negatív szám, de `w`-t nem vihetünk vissza a bázisba, ezért most kész vagyunk.

Az optimális bázist az `x_1, x_2` és `u_1` változókhoz tartozó oszlopvektorok alkotják, az optimális bázismegoldás az, amikor `w_2, w_3, x_3` és `u_2` (amik felül vannak) mind nulla:
`x_1=1, x_2=6, u_1=21, x_3=0, u_2=0` (és persze mindkét `w` is nulla, de ez kötelező.)
Az optimális célfüggvényérték pedig `ζ=-20, z=-ζ=20`

Az optimális bázismegoldás degenerált, mert `x_3=0` nem került be a bázisba. Alternatív optimális bázis nincs, mert `ζ` sorában nincs 0 elem. Ha lenne, azt az oszlopot bevonhatnánk a bázisba, de nem változna a célfüggvény értéke (a 0 miatt ugyanaz maradna).

-------------------
Még nincs kész, majd folytatom. Le kell még olvasni erről a duális feladat megoldását, aztán megoldani azt is duál-szimplex-szel.
1

bongolo { Aranyérmes } válasza
Az előző válasz végén kis apróság: Az optimális megoldásban teljesen felesleges volt az `u_1=21`-et odaírnom, hisz csak az `x`-ek az érdekesek.

Nagyobb gond, hogy kicsit elrontottam az előző válaszban a duálfeladatot. Valami fura okból azt írtam, hogy az első sorban van egyenlőség, pedig a harmadik sor az. Ezért a duális feladatban nem `y_1` előjele kötetlen, hanem `y_3`-é.

Aztán van, aki máshogy csinálja, amitől kicsit máshogy néz ki a duálfeladat (más az előjel), bár a kettő ekvivalens. Leírom azt a módszert is, mert a primál feladat optimális megoldásának a táblájából az ilyen módszerrel csinált duál feladat megoldása olvasható le.

A primál feladat tehát ez:

`{: (x_1,,,-,x_3,≤,22),(-2x_1,+,x_2,-,x_3,≥,4),(-4x_1,+,x_2,,,=,2):}`

`x_1, x_2, x_3 ≥ 0`

`2x_1+3x_2+x_3=z -> min`

A módszer lényegéhez tartozik, hogy nem negálom az első sort! A mátrixok:

`bar bar A=((1,0,-1),(-2,1,-1),(-4,1,0)), bar b=((22),(4),(2)), bar c^T=((2,3,1))`

`bar bar A·bar x ⋚ bar b`
`bar x ≥ bar 0`
`bar c^T·bar x -> min`

A minimumfeladatnak a duálisa maximumfeladat, ahol `x`-ek helyett más változók, `y`-ok vannak: annyi változó, ahány feltétel van a primálban (ez az előző válaszomban is így volt, csak nem írtam oda). Minden feltétel sorhoz tartozik egy változó.

`bar bar A^T·bar y ≤ bar c`
`bar b^T·bar y -> max`
A primálban a feltétel lehetett `≤`, `≥` vagy `=` is, a duálban mindig `≤`. (Ha a duál minimumfeladat lenne, akkor mind `≥` lenne.) A primálban az `x` változók mind `≥ 0` előjelűek voltak, az `y` változók előjelei viszont mások: Ha a primál minimumfeladat feltételében `≥` van, a hozzá tartozó `y` változó `y ≥ 0` előjelű. Ha a feltétel `≤`, akkor a változó `y ≤ 0` előjelű. Ha pedig a feltétel egyenlőség, akkor bármilyen előjelű lehet a hozzá tartozó változó.
(Persze ha a primálfeladat maximumfeladat, akkor fordítva: ott a "szokásos" feltétel a `≤`, azon sorok lesznek `≥ 0` előjelűek, stb.)

Vagyis kiírva részletesen a duál feladatot:

`{:(y_1,-,2y_2,-,4y_3,≤,2),(,,y_2,+,y_3,≤,3),(-y_1,-,y_2,,,≤,1):}`
`y_1 ≤ 0, y_2 ≥ 0 \ \ \ ` (`y_3` előjele kötetlen)

`22y_1+4y_2+2y_3 -> max`
-----------------------------------------

A duál feladat megoldását így lehet leolvasni a primál eredmény-táblájából:

A primál feladat megoldásakor a kezdő táblában a kezdő bázisok soronként az `u_1, w_2` és `w_3` változók voltak. Ez azért fontos, mert ezekhez a sorokhoz lett rendelve a duál feladat `y_1, y_2` és `y_3` változója. A primál feladat megoldása pedig ez lett az előző válasz végén:

`(( ,w_2,w_3 ,x_3 ,u_2 ,|,b)
,(u_1,-1/2,1/2,-1/2,1/2 ,|,21)
,(x_1,1/2 ,-1/2,-1/2,-1/2,|,1)
,(x_2,2 ,-1 ,-2 ,-2 ,|,6)
,(- ,- ,- ,- ,- ,|,-)
,(ζ ,-7 ,4 ,8 ,7 ,|,-20))`

Az utolsó sorban a `ζ` helyett írjuk vissza az eredeti `z`-t, amitől persze a teljes sor negálódik:

`(( ,w_2,w_3 ,x_3 ,u_2 ,|,b)
,(u_1,-1/2,1/2,-1/2,1/2 ,|,21)
,(x_1,1/2 ,-1/2,-1/2,-1/2,|,1)
,(x_2,2 ,-1 ,-2 ,-2 ,|,6)
,(- ,- ,- ,- ,- ,|,-)
,(z ,7 ,-4 ,-8 ,-7 ,|,20))`

A duál feladat `y_1` változója tehát az első feltétel-sorhoz tartozott, amihez az `u_1` bázisvektort rendeltük. `y_2` a második sor, ahhoz a `w_2` tartozik, `y_3`-hoz pedig a `w_3`. Ezért a duál feladat optimális megoldását a `z` sorban az `u_1, w_2, w_3` oszlopból tudjuk leolvasni.
`u_1` nem került ki a bázisból (nincs felül), nincs a táblában oszlopa. Ezért a hozzá tartozó `y_1` optimális értéke `0`. `w_2` illetve `w_3` alatt `7` illetve `-4` van, vagyis `y_2=7` és `y_3=-4` adja az optimumot. (`y_3` negatív lett, de szabad neki, kötetlen az előjele.)
Az optimális célfüggvényérték pedig `22y_1+4y_2+2y_3=20`

0