Szimplex módszer, szimplex tábla
Példaként tekintsük a következ® LP feladatot: z = 5x1 + 4x2 + 3x3 2x1 + 3x2 + x3 4x1 + x2 + 2x3 3x1 + 4x2 + 2x3 x1, x2, x3
= maximum, feltéve, hogy ≤5 ≤ 11 ≤8 ≥0
Vezessük be a s1, s2, s3 hiányváltozókat (a feltételi egyenl®tlenségek jobbés baloldalának különbségét (angolul: slack variable, slack=er®tlen, laza, pangó, slacks=hosszú nadrág, pantalló). Ezek segítségével az eredetivel ekvivalens probléma: z s1 s2 s3
= 5x1 + 4x2 + 3x3 = maximum, feltéve, hogy = 5 − 2x1 − 3x2 − x3 = 11 − 4x1 − x2 − 2x3 = 8 − 3x1 − 4x2 − 2x3 x1, x2, x3, s1, s2, s3 ≥ 0
Itt a s1, s2, s3 változókat bázisváltozóknak, x1, x2, x3-at nembázis változóknak nevezük. Induljunk ki az x1 = x2 = x3 = 0 megoldásból, ekkor s1 = 5, s2 = 11, s3 = 8 és a célfüggvény z = 0.Próbáljunk egy jobb megoldást keresni. Mivel a célfüggvényben x1 együtthatója pozitív, ezért x1 értékét megnövelve z értéke n®. De x1 értékét nem növelhetjük akármekkorára, mert a hiányváltozóknak nemnegatíveknek kell maradniuk. Ha x1 ≥ 0, x2 = x3 = 0 akkor az s1 = 5 − 2x1 ≥ 0 s2 = 11 − 4x1 ≥ 0 s3 = 8 − 3x1 ≥ 0 1
x1 ≤ 25 = 2, 5 x1 ≤ 11 4 = 2, 75 x1 ≤ 38 = 2, 66..
2
egyenl®tlenségek mindegyikének teljesülnie kell ezért 0 ≤ x1 ≤ 2, 5 azaz x1-et legfeljebb 2, 5-re növelhetjük. Legyen tehát 5 1 x1 = , x2 = x3 = 0 akkor s1 = 0, s2 = 1, s3 = 2 2 z értéke 5 · 25 = 12, 5-re n®tt.
Hogyan tovább? Mivel most s1 = x2 = x3 = 0 így x1 szerepét s1 veszi át, a célfüggvényt és a feltételeket át kell írnunk ennek megfelel®en. A s1 de níciójából x1 = 2, 5 − 0, 5s1 − 1, 5x2 − 0, 5x3
ezt a célfüggvénybe, s2, s3-ba helyettesítve kapjuk, hogy z = 5 (2, 5 − 0, 5s1 − 1, 5x2 − 0, 5x3) + 4x2 + 3x3 = 12, 5 − 2, 5s1 − 3, 5x2 + 0, 5x3 s2 = 11 − 4 (2, 5 − 0, 5s1 − 1, 5x2 − 0, 5x3) − x2 − 2x3 = 1 + 2s1 + 5x2 s3 = 8 − 3 (2, 5 − 0, 5s1 − 1, 5x2 − 0, 5x3) − 4x2 − 2x3 = 0, 5 + 1, 5s1 + 0, 5x2 − 0, 5x3
Az új változókkal a problémánk: z x1 s2 s3
= 12, 5 − 2, 5s1 − 3, 5x2 + 0, 5x3 = maximum, feltéve, hogy = 2, 5 − 0, 5s1 − 1, 5x2 − 0, 5x3 = 1 + 2s1 + 5x2 = 0, 5 + 1, 5s1 + 0, 5x2 − 0, 5x3 s1, x2, x3, x1, s2, s3 ≥ 0
Ismét látható, hogy s1 = x2 = x3 = 0 esetén x1 = 2, 5, s2 = 1, s3 = 0, 5 és z = 12, 5. Mivel most a célfüggvényben egyedül x3 együtthatója pozitív, ennek növelésével növelhetjük a célfüggvényt. Mennyivel növelhetjük? Az x3 ≥
3
0, s1 = x2 = 0-nál az x1, s2, s3 ≥ 0 feltételekb®l x1 = 2, 5 − 0, 5x3 ≥ 0 x3 ≤ 5 s2 = 1 ≥ 0 ez minden x3 esetén teljesül s3 = 0, 5 − 0, 5x3 ≥ 0 x3 ≤ 1
ezért x3 = 1 s3 = 0 és s1 = x2 = 0, a célfüggvény 0, 5 · 1 = 0, 5-del n®, 13-ra. Az új (nembázis, vagy független) változók s1, x2, s3, az x3 szerepét s3 veszi át. Mivel a s3 = 0, 5 + 1, 5s1 + 0, 5x2 − 0, 5x3 egyenletb®l x3 = 1 + 3s1 + x2 − 2s3
ezt behelyettítve z, x1, s2 -be (végezze el a számításokat!) kapjuk, az új változókkal felírt problémát: z x1 s2 s3
= 13 − s1 − 3x2 − s3 = maximum, feltéve, hogy = 2 − 2s1 − 2x2 + s3 = 1 + 2s1 + 5x2 = 1 + 3s1 + x2 − 2s3 s1, x2, s3, x1, s2, x3 ≥ 0
Most már nincs pozitív együttható z képletében, nem tudjuk z -t növelni. Mivel s1, x2, s3 ≥ 0 ezért z = 13 − s1 − 3x2 − s3 ≤ 13, de s1 = x2 = s3 = 0 (míg x1, s2, x3 értékeit az el®z® képletekb®l számolhatjuk) mellett z = 13 így az optimális megoldás z = 13. Az el®z®kben tárgyalt feladat szimplex táblája az s1, s2, s2 hiányváltozók bevezetése utáni rendszer 2x1 + 3x2 + x3 + s1 4x1 + x2 + 2x3 + s2 3x1 + 4x2 + 2x3 + s3 −5x1 − 4x2 − 3x3 + z
=5 = 11 =8 =0
4
(ahol x1, x2, x3, s1, s2, s3 ≥ 0 és a z maximumát keressük) együtthatóinak mátrixából áll: s1 s2 s3 z
x 1 x 2 x 3 s1 s2 s 3 2 3 1 1 0 0 5 4 1 2 0 1 0 11 3 4 2 0 0 1 8 −5 −4 −3 0 0 0 0
A táblázat sorainak, oszlopainak jelölését, a célfüggvényt és az egyenletek jobboldalán álló számokat egy-egy vonallal elválasztottuk. 1. lépés. El®ször megkeressük a pivot elemet (pivot= forgó ), a belép® változót és az elhagyott változót. Kiválasztjuk az alsó sor "legnegativabb" elemét (azaz a legnagyobb abszolút érték¶ negatív elemet) ez példánkban −5. Ha több ilyen is van akkor nem számít melyiket választjuk. Ennek az oszlopa lesz a pivot oszlop. Ezután a az utolsó oszlop minden elemét osztjuk a pivot oszlop megfelel® elemével (csak a pozitív elemekkel osztunk, a többi hányadost gyelmen kívül hagyjuk), a hányadosokat az utolsó oszlop után írtuk be: x1 x2 x3
s1
s2
s3
hányados
s1
2
3
1
1
0
0 5
5 2
s2
4
1
2
0
1
0 11
11 4
s3
3
4
2
0
0
1 8
8 3
z −5 −4 −3
0
0
0 0
= 2, 5 pivot sor = 2, 75 = 2, 66
A hányadosok közül megkeressük a legkisebbiket (ha több ilyen is van, akkor mindegy melyiket vesszük) ennek sora a pivot sor nálunk a legkissebb hányados 2,5 az els® sorban így a pivot sor az els® sor. A pivot elem a pivot sorban és pivot oszlopban lév® elem, nálunk 2. A belép®
5
változó a pivot oszlopnak megfelel® változó (nálunk x1), a kilép® változó a pivot sornak megfelel® változó (nálunk s1). Most a pivotálás következik. A pivot sor elemeit elosztjuk a pivot elemmel: 2. lépés.
x1
x2
x3
hányados
s1
s2
s3
s1
1 1, 5 0, 5 0, 5
0
0 2, 5
5 2
s2
4
1
2
0
1
0 11
11 4
s3
3
4
2
0
0
1
8
8 3
z −5 −4 −3
0
0
0
0
= 2, 5 pivot sor = 2, 75 = 2, 66
majd e sor alkalmas többszöröseit a többi sorból levonva elérjük, hogy a pivot oszlop többi elemei zérusok legyenek. Nálunk az els® sor négyszeresét kell levonni a második sorból, majd az els® sor háromszorosát kell levonni a harmadik sorból, végül az els® sor ötszörösét kell az utolsó sorhoz hozzáadni. A kilép® változó nevét a belép®vel kell helyettesíteni. Az így kapott táblázat x1
x2
x3
s1
s2
x1
1
1, 5
0, 5
0, 5
0
0 2, 5
s2
0
−5
0
−2
1
0
s3
0 −0, 5
0, 5 −1, 5
0
1 0, 5
0
0 12, 5
z
0
3, 5 −0, 5
2, 5
s3
1
Ezután ismételjük az 1. és 2. lépést az új táblázattal mindaddig amíg az utolsó sor elemei nemnegatívak vagy zérusok
6
lesznek. Ekkor az optimális megoldás a jobboldali oszlopból olvasható le.
Táblázatunkban a -0,5 oszlopa lesz a pivot oszlop, a pivot sort pedig ismét az utolsó oszlop és a pivot oszlop megfelel® elemeinek hányadosai közül a legkisebb hányados sora adja (csak pozitív elemekkel osztunk), esetünkben a harmadik sor. A belép® változó a pivot oszlopnak megfelel® változó (nálunk x3), a kilép® változó a pivot sornak megfelel® változó (nálunk s3). hányados
x1
x2
x3
s1
s2
x1
1
1, 5
0, 5
0, 5
0
0 2, 5
2,5 0,5
s2
0
−5
0
−2
1
0
−
s3
0 −0, 5
0, 5 −1, 5
0
1 0, 5
0
0 12, 5
z
0
3, 5 −0, 5
2, 5
s3
1
0,5 0,5
=5
= 1 pivot sor
A harmadik sort 0,5-tel elosztjuk, majd az így kapott sor 0,5-szeresét az els®b®l levonjuk és az utolsó sorból is levonjuk. A kapott táblázat (melyb®l az utolsó oszlop hányadosait lehagytuk) x1 x2 x3
2
s3
0 −1 2
1
s2
0 −5
0 −2
1
0 1
x3
0 −1
1 −3
0
2 1
0
0
0
1 13
3
0
s2
x1
z
2
s1
1
7
Mivel az utolsó oszlopban már nincs negatív elem, ezért a megoldás befejez®dött, z maximális értéke 13, és a baloldali oszlopban szerepl® változók optimális értékeit a z oszlopból olvashatjuk le azaz most x1 = 2, s2 = 1, x3 = 1 a többi változó optimális értéke zérus, azaz x2 = s1 = s3 = 0. A fennt ismertetett un. primál szimplex módszer alkalmazható a standard normál maximumfeladat megoldására. Ez a feladat x ≥0 Megjegyzések.
Ax ≤ b, b ≥ 0 c>x = z → max alakba írható, ahol x = (x1, . . . , xn)> ∈ Rn×1 a keresett n dimenziós oszlopmátrix/vektor 0 = (0, . . . , 0)> ∈ Rn×1, az n dimenziós oszlop zérusvektor, az x ≥ 0 egyenl®tlenség koordinátánként (elemenként) értend®, A = (aij ) ∈ Rk×n egy k × n típusú (adott) mátrix, b = (b1, . . . , bk )> ∈ Rk×1 adott k dimenziós nemnegatív koordinátákkal rendelkez® oszlopmátrix/vektor c = (c1, . . . , cn)> ∈ Rn×1 egy n dimenziós adott sorvektor, c> = (c1, . . . , cn) ∈ R1×n. Feltételezhet®, hogy c> ≥ 0>, c> 6= 0> vagyis a ci értékek között vannak pozitívok, ugyanis ellenkez® esetben x = 0 adja az optimális megoldást.
