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.

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`

Kimaradt még az, hogy mi a megoldás duál-szimplex algoritmussal.

Nem tudom, hogyan tanultátok. Az "igazi" duál-szimplex algoritmus az, hogy az eredeti primál feladatot átalakítod csupa ≤ feltételűre úgy, hogy a megfelelő sorokat mínusz 1-gyel szorzod, és lesznek negatív értékek a `b` oszlopban. Ez után a báziscsere úgy megy, hogy a táblában a jobb(!) oldalon kell keresni negatív értéket, annak a sora lesz a cserélendő bázis, és valamelyik oszloppal(!) kell becserélni. Szóval mintha a tábla átlójára tükrözve lenne megoldva a feladat a szimplex módszerrel. ... Persze ennél bonyolultabb, de most nem írom tovább.

Most viszont már úgyis megvan a duál feladat, és a primál feladat duál-szimplex megoldása ugyanaz, mintha a duál feladatot megoldanád a primál-szimplex módszerrel. Úgy fogom megcsinálni (bár nem vagyok róla meggyőződve, hogy ezt várja a tanár).

Szóval a duál feladat ez:

`{:(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`

Oldjuk ezt meg a sima szimplex algoritmussal.

Maximumfeladatról van szó, minden feltétel sorban ≤ van és a jobb oldalon mindenhol pozitív szám van, ez idáig tökéletes. Viszont az `y` változók előjelével gond van: `y_1≤0`, `y_3` pedig bármi lehet. A szimplexhez viszont az kell, hogy mindegyik `≥ 0` legyen! Nem baj, néhány egyszerű trükkel el lehet ezt érni:

Első trükk: `y_1 ≤ 0`, e helyett vezessük be az `y_(11)=-y_1` változót, ez már nem negatív. A feltételek és a célfüggvény ezek lesznek:

`{:(-y_(11),-,2y_2,-,4y_3,≤,2),(,,y_2,+,y_3,≤,3),(y_(11),-,y_2,,,≤,1):}`

`-22y_(11)+4y_2+2y_3 -> max`

Másik trükk: `y_3` tetszőleges előjelű, e helyett legyen két változó: `y_(31)≥0` és `y_(32)≥0`, amikre ez igaz: `y_3=y_(31)-y_(32).` Ezzel a két nemnegatív számmal bármilyen `y_3` előállítható. A feltételek és a célfüggvény ezek lesznek:

`{:(-y_(11),-,2y_2,-,4y_(31),+,4y_(32),≤,2),(,,y_2,+,y_(31),-,y_(32),≤,3),(y_(11),-,y_2,,,,,≤,1):}`

`-22y_(11)+4y_2+2y_(31)-2y_(32) -> max`

Ezzel a két kis módosítással olyan feladatot kaptunk, amiben minden feltétel megmaradt ≤ feltételnek, és minden változó `≥ 0` kell legyen. Az eredeti primál feladathoz képest ez nagy előny, mert egy fázisban meg lehet oldani (ugyanis nem kell bevezetni `w` segédváltozókat)! Ezért szeretik a primál helyett a duál feladatot megoldani.
(Megjegyzés: ez akkor alakul ilyen szépen, ha az eredeti primál feladat célfüggvényében mindenhol plusz van, egyébként, gondolj bele, a duál feladatban a jobb oldalon lennének negatív számok... akkor már nem lenne egyszerűbb a duált megoldani.)

Ha belejössz, ezt a következő lépést át is lehet ugrani és lehet kapásból a táblát felírni, de most megcsinálom részleteiben, hogy jobban látszódjon az elmélet. Szóval ez a lépés az, hogy alakítsuk át az egyenlőtlenségeket egyenletté három `u` segédváltozó bevezetésével. Mivel most mindenhol ≤ van, mindegyik sorhoz hozzá kell adni egy nemnegatív `u`-t:

`{:(-y_(11),-,2y_2,-,4y_(31),+,4y_(32),+,u_1,,,,,=,2),(,,y_2,+,y_(31),-,y_(32),,,+,u_2,,,=,3),(y_(11),-,y_2,,,,,,,,,+,u_3,=,1):}`
és persze `y_(11), y_2, y_(31), y_(32), u_1, u_2, u_3 ≥ 0`

Ennek a mátrixa (illetve táblázata) ilyen lenne:
`((y_(11),y_2,y_(31),y_(32),u_1,u_2,u_3,|,b),(-1,-2,-4,4,1,0,0,|,2),(0,1,1,-1,0,1,0,|,3),(1,-1,0,0,0,0,1,|,1))`
Ott van az oszlopvektorok között a 3 egységvektor: `u_1, u_2` és `u_3`. Ezek adják a kezdeti bázist, tényleg nem kell bevezetni `w` változókat! Az egységoszlopokat ki lehet hagyni a táblából, a nevüket pedig beírni a sorok elé:
`(( ,y_(11),y_2,y_(31),y_(32),|,b)
,(u_1,-1 ,-2 ,-4 ,4 ,|,2)
,(u_2,0 ,1 ,1 ,-1 ,|,3)
,(u_3,1 ,-1 ,0 ,0 ,|,1))`

Be kell írni a táblába még a `z` célfüggvényt is. Rendezzük nullára: `z+22y_(11)-4y_2-2y_(31)+2y_(32)=0`, így kerül be az utolsó sorba:
`(( ,y_(11),y_2,y_(31),y_(32),|,b)
,(u_1,-1 ,-2 ,-4 ,4 ,|,2)
,(u_2,0 ,1 ,1 ,-1 ,|,3)
,(u_3,1 ,-1 ,0 ,0 ,|,1)
,(- ,- ,- ,- ,- ,|,-)
,(z ,22 ,-4 ,-2 ,2 ,|,0))`

Szóval rögtön fel lehetett volna írni ezt a táblát a két kis módosítás után.

Ugyanúgy kell csinálni a báziscseréket, mint az első válaszban is: Keressünk a `z` sorában negatív számot (persze nem a `b` oszlopban). Ez most az `y_2` vagy `y_(31)` lehet. A nagyobb abszolút értékűt válasszuk, ezért `y_2`-t vonjuk be a bázisba az `u_2` helyébe (ott van csak pozitív most).

A generáló elem tehát az `1`. A csere maga ezeket a lépéseket jelenti: (megismétlen ugyanazt, amit az első válaszban már írtam)
- az új tábla fejlécei ugyanazok, csak `u_2` és `y_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:
`(( ,y_(11),u_2,y_(31),y_(32),|,b)
,(u_1, ,2 , , ,|, )
,(y_2,0 ,1 ,1 ,-1 ,|,3)
,(u_3, ,1 , , ,|, )
,(- ,- ,- ,- ,- ,|,-)
,(z , ,4 , , ,|, ))`

- 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:
`(( ,y_(11),u_2,y_(31),y_(32),|,b)
,(u_1,-1 ,2 ,-2 ,2 ,|,8)
,(y_2,0 ,1 ,1 ,-1 ,|,3)
,(u_3,1 ,1 ,1 ,-1 ,|,4)
,(- ,- ,- ,- ,- ,|,-)
,(z ,22 ,4 ,2 ,-2 ,|,12))`
(`z` értéke (a `b` oszlopban) máris 12-re nőtt.)

A következő bázis az `y_(32)` lesz, ott van negatív szám (-2). A generáló elem az `u_1` sorában a 2-es értékű elem, az egyetlen pozitív. Az új tábla, már csak a végeredményt írom ide a báziscsere után:
`(( ,y_(11),u_2,y_(31),u_1,|,b)
,(y_(32),-1/2 ,1 ,-1 ,1/2,|,4)
,(y_2 ,-1/2 ,2 ,0 ,1/2,|,7)
,(u_3 ,1/2 ,2 ,0 ,1/2,|,8)
,(- ,- ,- ,- ,- ,|,-)
,(z ,21 ,6 ,0 ,1 ,|,20))`

Nincs több negatív a `z` sorban, kész vagyunk.

Az optimális bázist az `y_2, y_(32)` és `u_3` változókhoz tartozó vektorok alkotják, az optimális bázismegoldás az, amikor `y_(11), y_(31), u_1` és `u_2` (amik felül vannak) mind nulla:
`y_(11)=0, y_2=7, y_(31)=0, y_(32)=4` (és `u_1=u_2=0, u_3=8`)
Az eredeti változókkal: `y_1=-y_(11)=0, y_2=7, y_3=y_(31)-y_(32)=-4`
Az optimális célfüggvényérték `z=20`.

Az optimális bázismegoldás degenerált, mert `y_(11)=0` nem került be a bázisba (az rendben van, hogy `y_(31)` és `y_(32)` közül csak az egyik került be). Van `z` sorában 0 elem (`y_(31)`), de nincs felette pozitív szám, ezért nincs alternatív optimális bázis.

Ennek a feladatnak a duálisa az eredeti primál feladat. Annak az optimális megoldását is le tudjuk olvasni ugyanolyan módon, mint a második válasz végén: az `u_1, u_2, u_3` voltak az első, második és harmadik feltétel-sorhoz rendelt bázisvektorok, ami sorok a primer feladat `x_1, x_2, x_3` változóihoz vannak rendelve. Ezek optimális értékeit a táblából az `u` változók alatti `z` sorbeli értékekből tudjuk leolvasni:

`u_1` alatt leolvasható, hogy `x_1=1`, `u_2` alatt `x_2=6`. `u_3` nincs felül, ezért a hozzá tartozó `x_3=0`.

Jól számoltunk, ugyanaz jött ki, mint a primer feladat megoldásából.