Bevezetés a lineáris programozásba 8. el˝oadás Farkas István DE ATC Gazdaságelemzési és Statisztikai Tanszék
Szimplex módszer – p. 1/1
Az LP feladatok általános modellje A korlátozó feltételeket írjuk fel a következ˝o alakban: a11 x1 + a12 x2 + . . . + a1n xn ≤ b1 a21 x1 + a22 x2 + . . . + a2n xn ≤ b2 .. . am1 x1 + am2 x2 + . . . + amn xn ≤ bm , ahol xi ≥ 0 minden i = 1, 2, . . . , n-re,
Szimplex módszer – p. 2/1
Az LP feladatok általános modellje A korlátozó feltételeket írjuk fel a következ˝o alakban: a11 x1 + a12 x2 + . . . + a1n xn ≤ b1 a21 x1 + a22 x2 + . . . + a2n xn ≤ b2 .. . am1 x1 + am2 x2 + . . . + amn xn ≤ bm , ahol xi ≥ 0 minden i = 1, 2, . . . , n-re, míg a célfüggvény z = c1 x1 + c2 x2 + . . . + cn xn =⇒ max v. min alakú.
Szimplex módszer – p. 2/1
Az LP feladatok mátrix alakú modellje A modell vektorok és mátrixok seítségével egyszer˝ubben is felírható:
2.)
~x ≥ ~0 A ~x ≤ ~b
3.)
z = ~cT ~x =⇒ max v. min
1.)
Az A mátrix elemeit technikai vagy technológiai koefficiensnek nevezzük. Az ~x vektor elemei a változók (programozási feladatokban ezeket primál változóknak nevezzük). A ~b vektort készlet vagy kapacitás vektornak, a ~cT vektort pedig a célfüggvény vektorának nevezzük.
Szimplex módszer – p. 3/1
Az LP feladatok csoportosítása A feladatoknak két alaptípusa van: maximum- és minimumszámítás. A további csoportosítást maximum feladatoknál a korlátozó feltételek milyensége alapján végezzük. 1. Normál feladat: az ~x ≥ ~0 A ~x ≤ ~b z = ~cT ~x =⇒ max feladatot normál feladatnak hívjuk. Ebben az esetben a feltételek mindegyike ≤. 2. Módosított normál feladat: a korlátozó feltételek között ≤ és = is szerepel. 3. Általános feladat: a korlátozó feltételek között ≤, = és ≥ is szerepel.
Szimplex módszer – p. 4/1
Grafikus megoldás Kétváltozós esetben az LP feladatokat grafikusan is megoldhatjuk. Erre nézünk most egy példát. Feladat. Két termék egy-egy darabjának el˝oállításához négy alapanyagból rendre 8, 1, 3, 0 és 8, 3, 0, 2 egységet kell felhasználni. Az alapanyagokból maximálisan 64, 15, 18, 8 egységet lehet felhasználni. Az egyes végtermékek egy darabjának tiszta hozama 5, illetve 3 egység. Mennyit kell el˝oállítani az egyes termékekb˝ol, hogy a hozam maximális legyen? Mennyi ez a maximum?
Szimplex módszer – p. 5/1
Grafikus megoldás Kétváltozós esetben az LP feladatokat grafikusan is megoldhatjuk. Erre nézünk most egy példát. Feladat. Két termék egy-egy darabjának el˝oállításához négy alapanyagból rendre 8, 1, 3, 0 és 8, 3, 0, 2 egységet kell felhasználni. Az alapanyagokból maximálisan 64, 15, 18, 8 egységet lehet felhasználni. Az egyes végtermékek egy darabjának tiszta hozama 5, illetve 3 egység. Mennyit kell el˝oállítani az egyes termékekb˝ol, hogy a hozam maximális legyen? Mennyi ez a maximum? Megoldás. Elkészítjük a feladat matematikai modelljét. Jelölje x az els˝o termék darbszámát, míg y azt, hogy hány darabot állítunk el˝o a második termékb˝ol.
Szimplex módszer – p. 5/1
Grafikus megoldás Kétváltozós esetben az LP feladatokat grafikusan is megoldhatjuk. Erre nézünk most egy példát. Feladat. Két termék egy-egy darabjának el˝oállításához négy alapanyagból rendre 8, 1, 3, 0 és 8, 3, 0, 2 egységet kell felhasználni. Az alapanyagokból maximálisan 64, 15, 18, 8 egységet lehet felhasználni. Az egyes végtermékek egy darabjának tiszta hozama 5, illetve 3 egység. Mennyit kell el˝oállítani az egyes termékekb˝ol, hogy a hozam maximális legyen? Mennyi ez a maximum? Megoldás. Elkészítjük a feladat matematikai modelljét. Jelölje x az els˝o termék darbszámát, míg y azt, hogy hány darabot állítunk el˝o a második termékb˝ol. x, y
≥
0
8x + 8y
≤
64
x + 3y
≤
15
3x
≤
18
2y
≤
8
z = 5x + 3y
→
max.
Szimplex módszer – p. 5/1
Grafikus megoldás Az egyenl˝otlenség rendszert grafikusan oldjuk meg. Az els˝o feltétel biztosítja, hogy a megoldásokat a koordináta rendszer els˝o síknegyedében keressük. Tekintsünk az egyenl˝otlenségek helyett egyenl˝oségeket. Ekkor egyenesek egyenleteit kapjuk, melyeket tengelymetszetes alakra átírva könnyen ábrázolhatunk. Ezek után besatírozzuk az egyenl˝otlenségeket igazzá tév˝o területrészeket. Ha a feltételben a ≤-jel szerepel, akkor az egyenes alatti pontok-, illetve az egyenes pontjainak koordinátái teszik igazzá az egyenl˝otlenséget. A ≥-jel esetén fordítva. A beszinezett területek metszete tartalmazza azon pontokat, melynek koordinátái az összes feltételt kielégítik. Ez a megengedett megoldások halamaza. Ezen pontok között keressük azt, amelyre a célfüggvény maximális értéket vesz fel.
Szimplex módszer – p. 6/1
Grafikus megoldás Az egyenl˝otlenség rendszert grafikusan oldjuk meg. Az els˝o feltétel biztosítja, hogy a megoldásokat a koordináta rendszer els˝o síknegyedében keressük. Tekintsünk az egyenl˝otlenségek helyett egyenl˝oségeket. Ekkor egyenesek egyenleteit kapjuk, melyeket tengelymetszetes alakra átírva könnyen ábrázolhatunk. Ezek után besatírozzuk az egyenl˝otlenségeket igazzá tév˝o területrészeket. Ha a feltételben a ≤-jel szerepel, akkor az egyenes alatti pontok-, illetve az egyenes pontjainak koordinátái teszik igazzá az egyenl˝otlenséget. A ≥-jel esetén fordítva. A beszinezett területek metszete tartalmazza azon pontokat, melynek koordinátái az összes feltételt kielégítik. Ez a megengedett megoldások halamaza. Ezen pontok között keressük azt, amelyre a célfüggvény maximális értéket vesz fel. A tengelymetszetes alakok: e1 : e2 :
y x + 8 8 x y + 15 5 x e3 : 6 y e4 : 4
=
1
=
1
=
1
=
1.
Szimplex módszer – p. 6/1
Grafikus megoldás Y
zmax = 36 e3
8
6
4
e4
2
e2 zpr = 15
e1 X
0 0
2
4
6
8
10
12
14
16
Foglalkozzunk most a célfüggvénnyel. Adjunk a célfüggvénynek egy tetsz˝oleges értéket, úgy hogy az könnyen ábrázolható legyen. (Érdemes az x és y együtthatóinak közös többszörösét választani.) Így a zpr próbaegyeneshez jutunk: 5x + 3y = 15.
Szimplex módszer – p. 7/1
Grafikus megoldás Azok a pontok, amelyekben a célfüggvény a 15 értéket veszi fel, a fenti egyenesen (ún. szintvonalon) fekszenek. A megengedett megoldások halmazának egyes pontjaiban a célfüggvény azt az értéket veszi fel, amelyhez az adott ponton áthaladó szintvonal tartozik. A más értékekhez tartozó szintvonalak evvel az egyenessel párhuzamosak. Ha az egyenest önmagával párhuzamosan felfelé toljuk, akkor z értéke n˝o, míg lefelé tolva z értéke csökken. Mivel z maximumát keressük, a z értékét növelnünk kell, az egyenest önmagával párhuzamosan felfelé toljuk el. Így elérhet˝o, hogy a párhuzamos egyenesnek csak egy közös pontja legyen a megengedett megoldások halmazával. (Általános esetben ez lehet egy szakasz, illetve egy félegyenes is.) A konkrét példában ez a pont az e1 és e3 egyenesek metszéspontja. Ahhoz, hogy a maximumhelyet megkapjuk, meg kell oldanunk az: x
=
6
8x + 8y
=
64
egyenletrendszert. A széls˝oértékhely koordinátái: x = 6, illetve y = 2. Az els˝o termékb˝ol 6-ot, a másodikból 2-˝ot kell el˝oállítanunk, hogy a maximális hozamot kapjuk. A maximum értékét a célfüggvénybe való behelyettesítéssel kapjuk meg: zmax (6, 2) = 5 · 6 + 3 · 2 = 36.
Szimplex módszer – p. 8/1
A szimplex módszer •
A megoldás els˝o lépéseként elkészítjük az induló táblázatot, melyben az u1 , u2 , u3 és u4 szimbólummal az ún. duál változókat jelöljük. A gyakorlati példára gondolva ezek az er˝oforrások sorait jelölik.
• • • •
A fels˝o sorban a primál változók (~ x vektor elemei), az alsó sorban pedig a célfüggvény együtthatói (~cT vektor elemei), a jobb oldali oszlopban a készletvektor (~b) elemei szerepelnek. Egészítsük ki a táblázatot azzal, hogy a célfüggvény sorának végére 0-t, az elejére pedig (−z)-t írunk, kifejezve ezzel azt, hogy a táblázatnak megfelel˝o program alapján a célfüggvény értéke zérus, illetve hogy a célfüggvény maximumát kapjuk.
Szimplex módszer – p. 9/1
A szimplex módszer •
A megoldás els˝o lépéseként elkészítjük az induló táblázatot, melyben az u1 , u2 , u3 és u4 szimbólummal az ún. duál változókat jelöljük. A gyakorlati példára gondolva ezek az er˝oforrások sorait jelölik.
• • • •
A fels˝o sorban a primál változók (~ x vektor elemei), az alsó sorban pedig a célfüggvény együtthatói (~cT vektor elemei), a jobb oldali oszlopban a készletvektor (~b) elemei szerepelnek. Egészítsük ki a táblázatot azzal, hogy a célfüggvény sorának végére 0-t, az elejére pedig (−z)-t írunk, kifejezve ezzel azt, hogy a táblázatnak megfelel˝o program alapján a célfüggvény értéke zérus, illetve hogy a célfüggvény maximumát kapjuk.
A teljes induló szimplex táblázat tehát: x
y
~b
u1
8
8
64
u2
1
3
15
u3
3
0
18
u4
0
2
8
−z
5
3
0
Szimplex módszer – p. 9/1
A szimplex módszer 1. Ebben a táblázatban – és a további módosított táblázatokban is – a bal oldali oszlopban szerepl˝o változók értékei a jobb oldali oszlop megfelel˝o sorában olvashatók le, míg a fels˝o sorban szerepl˝o változók értékei a program alapján zérussal egyenl˝ok. 2. A program módosítását az egyenletrendszerek megismert módszeréhez hasonlóan végezzük néhány módosítással: (a) Generáló elemet választunk, de ezt csak abból az oszlopból tehetjük meg, ahol a célfüggvény együtthatója nem negatív (így növekedik a célfüggvény). Abból az oszlopból célszer˝u választani, ahol legnagyobb az együttható. (b) Generáló elemnek csak pozitív számot választunk, ellenkez˝o esetben ugyanis az xi ≥ 0 feltételt sértenénk meg. (c) Abból a sorból választunk generáló elemet, ahol a legsz˝ukebb a keresztmetszet, azaz a választott oszlopból csak az az aig > 0 elem lehet generáló elem, amelyre bi a legkisebb. a ig
Szimplex módszer – p. 10/1
A szimplex módszer 1. Ebben a táblázatban – és a további módosított táblázatokban is – a bal oldali oszlopban szerepl˝o változók értékei a jobb oldali oszlop megfelel˝o sorában olvashatók le, míg a fels˝o sorban szerepl˝o változók értékei a program alapján zérussal egyenl˝ok. 2. A program módosítását az egyenletrendszerek megismert módszeréhez hasonlóan végezzük néhány módosítással: (a) Generáló elemet választunk, de ezt csak abból az oszlopból tehetjük meg, ahol a célfüggvény együtthatója nem negatív (így növekedik a célfüggvény). Abból az oszlopból célszer˝u választani, ahol legnagyobb az együttható. (b) Generáló elemnek csak pozitív számot választunk, ellenkez˝o esetben ugyanis az xi ≥ 0 feltételt sértenénk meg. (c) Abból a sorból választunk generáló elemet, ahol a legsz˝ukebb a keresztmetszet, azaz a választott oszlopból csak az az aig > 0 elem lehet generáló elem, amelyre bi a legkisebb. a ig
Tekintsük tehát az induló táblázatot. Mivel 5 > 3, így az x oszlopból célszer˝u választani (x változót célszer˝u bevonni a programba, hiszen minden egysége 5 egységgel növeli a célfüggvényt). A hányadosokra: min
64
15 18 , , 8 1 3
=
18 , 3
Szimplex módszer – p. 10/1
A szimplex módszer tehát az u3 sorhoz tartozó a legkisebb. Azaz az x oszlopából és u3 sorából választunk generáló elemet amit úgy jelzünk, hogy bekeretezzük az itt álló 3-as számot. x
y
~b
u1
8
8
64
u2
1
3
15
0
18
u3
3
u4
0
2
8
−z
5
3
0
3. Ebben az új, javított táblázatban nem hagytunk el oszlopot. A generáló elem sorának elemeit úgy kapjuk, hogy a régi táblázat ezen elemeit osztjuk a generáló elemmel. 4. A generáló elem oszlopának elemeit úgy kapjuk, hogy a régi táblázat ezen elemeit osztjuk a generáló elem (−1)-szeresével. 5. A generáló elem helyére annak reciproka kerül. 6. A többi elemet a teljes bázistranszformációnál tanult és az egyenletrendszereknél alkalmazott módszer szerint számoljuk ki.
Szimplex módszer – p. 11/1
A szimplex módszer Az els˝o javított táblázathoz tartozó program: u3
y
~b
u1
- 38
u2
- 31
3
9
x
1 3
0
6
u4
0
2
8
−z
- 35
3
-30
8
16
Szimplex módszer – p. 12/1
A szimplex módszer Az els˝o javított táblázathoz tartozó program: u3
y
~b
u1
- 38
u2
- 31
3
9
x
1 3
0
6
u4
0
2
8
−z
- 35
3
-30
8
16
A táblázatból leolvasott eredmények: x=6
y=0
u1 = 16
u2 = 9
z = 30 u3 = 0
u4 = 8
Szimplex módszer – p. 12/1
A szimplex módszer Az els˝o javított táblázathoz tartozó program: u3
y
~b
u1
- 38
u2
- 31
3
9
x
1 3
0
6
u4
0
2
8
−z
- 35
3
-30
8
16
A táblázatból leolvasott eredmények: x=6
y=0
u1 = 16
u2 = 9
z = 30 u3 = 0
u4 = 8
A táblázat jelentése: az els˝o termékb˝ol 6, míg a másodikból 0 darabot állítunk el˝o. Ekkor a 3. nyersanyag teljesen elfogy, az els˝o nyersanyagból 16, a másodikból 9, a negyedikb˝ol 8 egység marad. Ilyen termelési program mellett a bevétel 30 egység. Ezt a programot még lehet javítani, mert tudunk generáló elemet választani. Az új táblázat:
Szimplex módszer – p. 12/1
A szimplex módszer A második javított táblázathoz tartozó program: u3
u1
~b
y
- 31
2
u2
2 3 1 3 2 3 - 32
1 8 - 83
0
6
- 82
4
- 83
-36
x u4 −z
3
Szimplex módszer – p. 13/1
A szimplex módszer A második javított táblázathoz tartozó program: u3
u1
~b
y
- 31
2
u2
2 3 1 3 2 3 - 32
1 8 - 83
0
6
- 82
4
- 83
-36
x u4 −z
3
Tovább már nem lehet generáló elemet választani, hiszen a célfüggvény együtthatói negatív számok. A kapott értékek optimálisak. Az eredmény: x=6
y=2
u1 = 0
u2 = 3
zmax = 36 u3 = 0
u4 = 4
Szimplex módszer – p. 13/1
A szimplex módszer A második javított táblázathoz tartozó program: u3
u1
~b
y
- 31
2
u2
2 3 1 3 2 3 - 32
1 8 - 83
0
6
- 82
4
- 83
-36
x u4 −z
3
Tovább már nem lehet generáló elemet választani, hiszen a célfüggvény együtthatói negatív számok. A kapott értékek optimálisak. Az eredmény: x=6
y=2
u1 = 0
u2 = 3
zmax = 36 u3 = 0
u4 = 4
A táblázat jelentése: az els˝o termékb˝ol 6, míg a másodikból 2 darabot állítunk el˝o. Ekkor az 1. és a 3. nyersanyag teljesen elfogy, a második nyersanyagból 3, a negyedikb˝ol 4 egység marad. Ilyen termelési program mellett a maximális bevétel 36 egység.
Szimplex módszer – p. 13/1
Példa Feladat. Oldja meg alábbi az lineáris programozási feladatot! x1 , x2 , x3
≥
0
x1 + x3
≤
40
−x2 + x3
≤
10
x1 + x2 − x3
≤
18
z = 4x1 + 3x3
→
max
Megoldás.
Szimplex módszer – p. 14/1
Példa Feladat. Oldja meg alábbi az lineáris programozási feladatot! x1 , x2 , x3
≥
0
x1 + x3
≤
40
−x2 + x3
≤
10
x1 + x2 − x3
≤
18
z = 4x1 + 3x3
→
max
Megoldás. x1
x2
x3
b
u1
1
0
1
40
u2
0
-1
1
10
u3
1
1
-1
18
−z
4
0
3
0
Szimplex módszer – p. 14/1
Példa Feladat. Oldja meg alábbi az lineáris programozási feladatot! x1 , x2 , x3
≥
0
x1 + x3
≤
40
−x2 + x3
≤
10
x1 + x2 − x3
≤
18
z = 4x1 + 3x3
→
max
Megoldás. x1
x2
x3
b
u1
1
0
1
40
u2
0
-1
1
u3
1
1
−z
4
0
u3
x2
x3
b
u1
-1
-1
2
22
10
u2
0
-1
1
10
-1
18
x1
1
1
-1
18
3
0
−z
-4
-4
7
-72
Szimplex módszer – p. 14/1
Példa u3
x2
u2
b
u1
-1
1
-2
2
x3
0
-1
1
10
x1
1
0
1
28
−z
-4
3
-7
-142
Szimplex módszer – p. 15/1
Példa u3
x2
u2
b
u3
u1
u2
b
u1
-1
1
-2
2
x2
-1
1
-2
2
x3
0
-1
1
10
x3
-1
1
-1
12
x1
1
0
1
28
x1
1
0
1
28
−z
-4
3
-7
-142
−z
-1
-3
-1
-148
Szimplex módszer – p. 15/1
Példa u3
x2
u2
b
u3
u1
u2
b
u1
-1
1
-2
2
x2
-1
1
-2
2
x3
0
-1
1
10
x3
-1
1
-1
12
x1
1
0
1
28
x1
1
0
1
28
-4
3
-7 -142 −z -1 -3 -1 -148 − A célfüggvény a maximumát az → x = (28, 2, 12)T helyen veszi fel zmax = 148 értékkel, míg → − − az → u = 0. −z
Szimplex módszer – p. 15/1
