1/12
Oper´ aci´ okutat´ as 3. gyakorlat ´ ris Programoza ´ si feladatok megolda ´ sa szimplex Linea ´ dszerrel mo
P´ ecsi Tudom´ anyegyetem PTI
2/12
Norm´ al feladatok megold´ asa szimplex m´ odszerrel
2/12
Norm´ al feladatok megold´ asa szimplex m´ odszerrel Defin´ıci´ o. Egy LP-feladatot norm´ al feladatnak nevez¨unk, ha • felt´etelrendszere csak ≤ rel´aci´okat tartalmaz • a v´altoz´ok csak nemnegat´ıv ´ert´ekeket vehetnek fel • a c´elf¨uggv´eny maximum´at keress¨uk. • a felt´etelek jobboldal´an csak nemnegat´ıv konstansok lehetnek.
3/12
M˝ uveletek a szimplex-t´ abl´ aban
3/12
M˝ uveletek a szimplex-t´ abl´ aban • A pivot elem hely´ere a reciprok´at ´ırjuk • A pivot elem sor´aban minden elemet elosztunk a pivotelemmel • A pivot elem oszlop´aban minden elemet elosztunk a pivotelemmel ´es vessz¨uk az ellentetj´et • A t¨obbi elemet u´gy sz´amoljuk, mint a b´aziscser´en´el
4/12
Pivot elem v´ alaszt´ asa
4/12
Pivot elem v´ alaszt´ asa • Olyan oszlopban v´alasztjuk a pivot elemet ahol a c´elsor eleme negat´ıv • Pozit´ıv sz´amot v´alasztunk pivot elemnek • A kiv´alasztott oszlop pozit´ıv elemeivel osszuk el az utols´o oszlop megfelel˝o elemeit ´es azt a sz´amot v´alasztjuk pivot elemnek, amelyre ez a h´anyados a legkisebb (sz˝ uk keresztmetszet szab´ aly)
4/12
Pivot elem v´ alaszt´ asa • Olyan oszlopban v´alasztjuk a pivot elemet ahol a c´elsor eleme negat´ıv • Pozit´ıv sz´amot v´alasztunk pivot elemnek • A kiv´alasztott oszlop pozit´ıv elemeivel osszuk el az utols´o oszlop megfelel˝o elemeit ´es azt a sz´amot v´alasztjuk pivot elemnek, amelyre ez a h´anyados a legkisebb (sz˝ uk keresztmetszet szab´ aly) A negat´ıv c´elelem˝u oszlopok k¨oz¨ul az al´abbiak alapj´an v´alaszthatunk: • A legnagyobb abszol´ut´ert´ek˝u negat´ıv c´elelem oszlop´ab´ol v´alasztunk • Minden negat´ıv c´elelem˝u oszlopban hat´arozzuk meg a pivot elemet ´es sz´am´ıtsuk ki a c´elf¨uggv´eny n¨oveked´es´et. V´alasszuk azt az oszlopot, amelyn´el a n¨oveked´es a legnagyobb • K¨onnyebb sz´amol´as ´erdek´eben olyan oszlopot v´alasztunk, ahol pivot elem 1-nek ad´odik. • K¨onnyebb sz´amol´as ´erdek´eben olyan oszlopot v´alasztunk, ahol pivot elem sor´aban vagy oszlop´aban 0-t, vagy 0-kat tal´alunk.
5/12
Az algoritmus v´ eget´ er
5/12
Az algoritmus v´ eget´ er • ha a c´elf¨uggv´eny sor´aban nincs negat´ıv elem, ekkor az optim´alis megold´as ´es a hozz´atartoz´o c´elf¨uggv´eny´ert´ek a t´abl´ab´ol kiolvashat´o • ha a negat´ıv c´elelemek oszlopaiban nincs pozit´ıv elem, ilyenkor a c´elf¨uggv´eny a lehets´eges megold´asok halmaz´an tetsz˝olegesen nagy ´ert´eket felvehet • Bizonyos esetekben v´egtelen ciklusra vezet az algoritmus. Az ilyen esetek akkor l´ephetnek fel, ha a pivot elem sor´aban az utols´o oszlopban 0 ´all. (Ilyen esetekben a c´elf¨uggv´eny ´ert´ek nem n¨ovekszik.) Az a´ltalunk haszn´altakn´al l´enyegesen bonyolultabb pivotelem-v´alaszt´asi szab´alyokkal a v´egtelen ciklus elker¨ulhet˝o.
6/12
P´ eld´ ak 1.a) Oldjuk meg a Horg´asz-probl´em´at szimplex algoritmussal! x1 + x2 + 2x3 ≤ 4 2x1 + + 3x3 ≤ 5 2x1 + 2x2 + 4x3 ≤ 7 x1, x2, x3 ≥ 0 3x1 + 2x2 + 4x3 = z → max Az indul´o szimplex-t´abla: x1 x2 x3 A szimplex t´abl´ab´ol kiolvashat´o A t´abl´a hoz z −3 −2 −4 0 1 b´azismegold´as: u1 1 1 2 4 a B0 = 0 [x, u] = [0, 0, 0, 4, 5, 7], u2 2 0 3 5 0 a c´elf¨uggv´eny ´ert´eke z = 0. u3 2 2 4 7
tatoz´ o b´azis 0 0 1 0 . 0 1
6/12
P´ eld´ ak 1.a) Oldjuk meg a Horg´asz-probl´em´at szimplex algoritmussal! x1 + x2 + 2x3 ≤ 4 2x1 + + 3x3 ≤ 5 2x1 + 2x2 + 4x3 ≤ 7 x1, x2, x3 ≥ 0 3x1 + 2x2 + 4x3 = z → max Az indul´o szimplex-t´abla: x1 x2 x3 A szimplex t´abl´ab´ol kiolvashat´o A t´abl´a hoz z −3 −2 −4 0 1 b´azismegold´as: u1 1 1 2 4 a B0 = 0 [x, u] = [0, 0, 0, 4, 5, 7], u2 2 0 3 5 0 a c´elf¨uggv´eny ´ert´eke z = 0. u3 2 2 4 7
tatoz´ o b´azis 0 0 1 0 . 0 1
6/12
P´ eld´ ak 1.a) Oldjuk meg a Horg´asz-probl´em´at szimplex algoritmussal! x1 + x2 + 2x3 ≤ 4 2x1 + + 3x3 ≤ 5 2x1 + 2x2 + 4x3 ≤ 7 x1, x2, x3 ≥ 0 3x1 + 2x2 + 4x3 = z → max Az indul´o szimplex-t´abla: x1 x2 x3 A szimplex t´abl´ab´ol kiolvashat´o A t´abl´a hoz z −3 −2 −4 0 1 b´azismegold´as: u1 1 1 2 4 a B0 = 0 [x, u] = [0, 0, 0, 4, 5, 7], u2 2 0 3 5 0 a c´elf¨uggv´eny ´ert´eke z = 0. u3 2 2 4 7
tatoz´ o b´azis 0 0 1 0 . 0 1
7/12
Elemi b´azistranszform´aci´oval u´j b´azisra t´er¨unk a´t. Ehhez a pivot elemet a legkisebb negat´ıv c´elelem oszlop´ab´ol (3. oszlop) v´alasztjuk. Az oszlopot a sz˝uk keresztmetszet elve alapj´an a 2. sor hely´ere vissz¨uk a b´azisba: x1 x2 x3 z
− 3 −2 −4 0
u1
1
1
2 4
u2
2
0
3 5
u3
2
2
4 7
7/12
Elemi b´azistranszform´aci´oval u´j b´azisra t´er¨unk a´t. Ehhez a pivot elemet a legkisebb negat´ıv c´elelem oszlop´ab´ol (3. oszlop) v´alasztjuk. Az oszlopot a sz˝uk keresztmetszet elve alapj´an a 2. sor hely´ere vissz¨uk a b´azisba: x1 x2 x3 z
− 3 −2 −4 0
u1
1
1
2 4
u2
2
0
3 5
u3
2
2
4 7
7/12
Elemi b´azistranszform´aci´oval u´j b´azisra t´er¨unk a´t. Ehhez a pivot elemet a legkisebb negat´ıv c´elelem oszlop´ab´ol (3. oszlop) v´alasztjuk. Az oszlopot a sz˝uk keresztmetszet elve alapj´an a 2. sor hely´ere vissz¨uk a b´azisba: x1 x2 x3 x1 x2 u2 z
− 3 −2 −4 0
z
4 3
20 3
1 − 23
2 3 5 3 1 3
− 13 −2
u1
1
1
2 4
u1 − 13
u2
2
0
3 5
x3
2 3 2 3
0
1 3 4 −3
u3 − 2 u3 2 2 4 7 A szimplex t´abl´ab´ol kiolvashat´o b´azismegold´as: [x, u] = [0, 0, 35 , 23 , 0, 13 ], a c´elf¨uggv´eny ´ert´eke z = 20 3. 1 2 0 A t´abl´ahoz tatoz´o b´azis a B1 = 0 3 0 . 0 4 1
7/12
Elemi b´azistranszform´aci´oval u´j b´azisra t´er¨unk a´t. Ehhez a pivot elemet a legkisebb negat´ıv c´elelem oszlop´ab´ol (3. oszlop) v´alasztjuk. Az oszlopot a sz˝uk keresztmetszet elve alapj´an a 2. sor hely´ere vissz¨uk a b´azisba: x1 x2 x3 x1 x2 u2 z
− 3 −2 −4 0
z
4 3
20 3
1 − 23
2 3 5 3 1 3
− 13 −2
u1
1
1
2 4
u1 − 13
u2
2
0
3 5
x3
2 3 2 3
0
1 3 4 −3
u3 − 2 u3 2 2 4 7 A szimplex t´abl´ab´ol kiolvashat´o b´azismegold´as: [x, u] = [0, 0, 35 , 23 , 0, 13 ], a c´elf¨uggv´eny ´ert´eke z = 20 3. 1 2 0 A t´abl´ahoz tatoz´o b´azis a B1 = 0 3 0 . 0 4 1
7/12
A bejel¨olt elemet v´alasztjuk pivotelemnek, ´ıgy a 2. oszlop ker¨ul a 3. b´azisvektor hely´ere: x1 x2 u2 z
− 13 −2
u1 − 13 x3 u3 −
2 3 2 3
4 3
20 3
1 − 32
2 3 5 3 1 3
0 2
1 3 − 34
7/12
A bejel¨olt elemet v´alasztjuk pivotelemnek, ´ıgy a 2. oszlop ker¨ul a 3. b´azisvektor hely´ere: x1 x2 u2 x1 u3 u2 z
− 13 −2
u1 − 13 x3
2 3 2 3
4 3
20 3
z
1 − 32
2 3 5 3 1 3
0
1 3 − 34
1
0
21 3
u1
0 − 21
0
x3
2 3 1 3
3 6 5 3 1 6
−1
1 3 1 2 2 −3
0
u3 − 2 x2 − A szimplex t´abl´ab´ol kiolvashat´o b´azismegold´as: [x, u] = [0, 16 , 53 , 12 , 0, 0], a c´elf¨uggv´eny ´ert´eke z = 21 3. 1 2 1 A t´abl´ahoz tatoz´o b´azis a B2 = 0 3 0 . 0 4 2
7/12
A bejel¨olt elemet v´alasztjuk pivotelemnek, ´ıgy a 2. oszlop ker¨ul a 3. b´azisvektor hely´ere: x1 x2 u2 x1 u3 u2 z
− 13 −2
u1 − 13 x3
2 3 2 3
4 3
20 3
z
1 − 32
2 3 5 3 1 3
0
1 3 − 34
1
0
21 3
u1
0 − 21
0
x3
2 3 1 3
3 6 5 3 1 6
−1
1 3 1 2 2 −3
0
u3 − 2 x2 − A szimplex t´abl´ab´ol kiolvashat´o b´azismegold´as: [x, u] = [0, 16 , 53 , 12 , 0, 0], a c´elf¨uggv´eny ´ert´eke z = 21 3. 1 2 1 A t´abl´ahoz tatoz´o b´azis a B2 = 0 3 0 . 0 4 2
7/12
A megjel¨olt elemet v´alasztva pivotelemnek, az 1. oszlopot vissz¨uk a b´azisba, a 2. sor hely´ere: x1 u3 u2 1
0
21 3
u1
0 − 12
0
x3
2 3 1 3
3 6 5 3 1 6
z
−1
x2 −
1 3 1 2 2 −3
0
7/12
A megjel¨olt elemet v´alasztva pivotelemnek, az 1. oszlopot vissz¨uk a b´azisba, a 2. sor hely´ere: x1 u3 u2 x3 u3 u2 1
0
21 3
z
u1
0 − 12
0
x3
2 3 1 3
3 6 5 3 1 6
z
−1
1 3 1 2 2 −3
0
3 2
1
1 2
19 2
u1
0 − 21
0
x1
3 2 1 2
1 2 5 2
1 2 1 1 2 −2
0
x2 1 x2 − A szimplex t´abl´ab´ol kiolvashat´o b´azismegold´as: [x, u] = [ 52 , 1, 0, 21 , 0, 0], a c´elf¨uggv´eny ´ert´eke z = 19 2. 1 1 1 A t´abl´ahoz tatoz´o b´azis a B3 = 0 2 0 . 0 2 2
7/12
A megjel¨olt elemet v´alasztva pivotelemnek, az 1. oszlopot vissz¨uk a b´azisba, a 2. sor hely´ere: x1 u3 u2 x3 u3 u2 1
0
21 3
z
u1
0 − 12
0
x3
2 3 1 3
3 6 5 3 1 6
z
−1
1 3 1 2 2 −3
0
3 2
1
1 2
19 2
u1
0 − 21
0
x1
3 2 1 2
1 2 5 2
1 2 1 1 2 −2
0
x2 1 x2 − A szimplex t´abl´ab´ol kiolvashat´o b´azismegold´as: [x, u] = [ 52 , 1, 0, 21 , 0, 0], a c´elf¨uggv´eny ´ert´eke z = 19 2. 1 1 1 A t´abl´ahoz tatoz´o b´azis a B3 = 0 2 0 . 0 2 2
7/12
A megjel¨olt elemet v´alasztva pivotelemnek, az 1. oszlopot vissz¨uk a b´azisba, a 2. sor hely´ere: x1 u3 u2 x3 u3 u2 1
0
21 3
z
u1
0 − 12
0
x3
2 3 1 3
3 6 5 3 1 6
z
−1
1 3 1 2 2 −3
0
3 2
1
1 2
19 2
u1
0 − 21
0
x1
3 2 1 2
1 2 5 2
1 2 1 1 2 −2
0
x2 1 x2 − A szimplex t´abl´ab´ol kiolvashat´o b´azismegold´as: [x, u] = [ 52 , 1, 0, 21 , 0, 0], a c´elf¨uggv´eny ´ert´eke z = 19 2. 1 1 1 A t´abl´ahoz tatoz´o b´azis a B3 = 0 2 0 . 0 2 2 Mivel a c´elsorban nincs negat´ıv elem, az algoritmus v´eget ´ert. A kapott megold´as optim´alis.
8/12
1.b) Oldjuk meg a k¨ovetkez˝o LP-feladatot szimplex algoritmussal! 2x1 − x2 ≤ 3 x1 − 3x2 ≤ 6 3x1 − 2x2 ≤ 10 x1, x2 ≥ 0 2x1 + x2 = z → max
8/12
1.b) Oldjuk meg a k¨ovetkez˝o LP-feladatot szimplex algoritmussal! 2x1 − x2 ≤ 3 x1 − 3x2 ≤ 6 3x1 − 2x2 ≤ 10 x1, x2 ≥ 0 2x1 + x2 = z → max x1 x2 z −2 −1 0 u1
2 −1
3
u2
1 −3
6
u3
3 −2 10
8/12
1.b) Oldjuk meg a k¨ovetkez˝o LP-feladatot szimplex algoritmussal! 2x1 − x2 ≤ 3 x1 − 3x2 ≤ 6 3x1 − 2x2 ≤ 10 x1, x2 ≥ 0 2x1 + x2 = z → max x1 x2 z −2 −1 0 u1
2 −1
3
u2
1 −3
6
u3
3 −2 10
8/12
1.b) Oldjuk meg a k¨ovetkez˝o LP-feladatot szimplex algoritmussal! 2x1 − x2 ≤ 3 x1 − 3x2 ≤ 6 3x1 − 2x2 ≤ 10 x1, x2 ≥ 0 2x1 + x2 = z → max x1 x2 u1 x2 z −2 −1 0 z 1 −2 3 u1
2 −1
3
x1
u2
1 −3
6
u2 −
u3
3 −2 10
u3 −
1 2 1 2 3 2
− 12 − 52 − 12
3 2 9 2 11 2
8/12
1.b) Oldjuk meg a k¨ovetkez˝o LP-feladatot szimplex algoritmussal! 2x1 − x2 ≤ 3 x1 − 3x2 ≤ 6 3x1 − 2x2 ≤ 10 x1, x2 ≥ 0 2x1 + x2 = z → max x1 x2 u1 x2 z −2 −1 0 z 1 −2 3 u1
2 −1
3
x1
u2
1 −3
6
u2 −
1 2 1 2 3 2
− 12 − 52
3 2 9 2 11 2
u3 − − 12 u3 3 −2 10 A m´asodik t´abl´aban a negat´ıv c´elelem alatt nincs pozit´ıv sz´am, ez´ert a c´elf¨uggv´eny tetsz˝olegesen nagy ´ert´ekeket felvehet a lehets´eges megold´asok halmaz´an.
8/12
1.b) Oldjuk meg a k¨ovetkez˝o LP-feladatot szimplex algoritmussal! 2x1 − x2 ≤ 3 x1 − 3x2 ≤ 6 3x1 − 2x2 ≤ 10 x1, x2 ≥ 0 2x1 + x2 = z → max x1 x2 u1 x2 z −2 −1 0 z 1 −2 3 u1
2 −1
3
x1
u2
1 −3
6
u2 −
1 2 1 2 3 2
− 12 − 52
3 2 9 2 11 2
u3 − − 12 u3 3 −2 10 A m´asodik t´abl´aban a negat´ıv c´elelem alatt nincs pozit´ıv sz´am, ez´ert a c´elf¨uggv´eny tetsz˝olegesen nagy ´ert´ekeket felvehet a lehets´eges megold´asok halmaz´an. ´Irjuk fel a kapott t´abl´ahoz tartoz´o egyenletrendszert:
9/12
u1 − 2x2 + z 1 2 u1 − 21 u1 − 23 u1
− −
1 2 x2 5 2 x2 1 2 x2
= 3 + x1
= + u2
=
− + u3 = Az egyes egyenletekb˝ol a b´azisv´altoz´okat kifejezve: z = 3 − u1 + 2x2 x1 = u2 = u3 =
3 2 9 2 11 2
− + +
1 2 u1 1 2 u1 3 2 u1
+ + +
1 2 x2 5 2 x2 1 2 x2 1 2 d, u2
3 2 9 2 11 2
1 Az u1 = 0, x2 = d > 0 ´ert´ekekkel az x1 = 23 + = 29 + 52 d, u3 = 11 + 2 2d lehets´eges megold´ast kapjuk, amely mellett a c´elf¨uggv´eny ´ert´eke z = 3 + 2d lesz, amely d → ∞ eset´en minden hat´aron t´ul n˝o.
9/12
u1 − 2x2 + z 1 2 u1 − 21 u1 − 23 u1
− −
1 2 x2 5 2 x2 1 2 x2
= 3 + x1
= + u2
=
− + u3 = Az egyes egyenletekb˝ol a b´azisv´altoz´okat kifejezve: z = 3 − u1 + 2x2 x1 = u2 = u3 =
3 2 9 2 11 2
− + +
1 2 u1 1 2 u1 3 2 u1
+ + +
1 2 x2 5 2 x2 1 2 x2 1 2 d, u2
3 2 9 2 11 2
1 Az u1 = 0, x2 = d > 0 ´ert´ekekkel az x1 = 23 + = 29 + 52 d, u3 = 11 + 2 2d lehets´eges megold´ast kapjuk, amely mellett a c´elf¨uggv´eny ´ert´eke z = 3 + 2d lesz, amely d → ∞ eset´en minden hat´aron t´ul n˝o.
9/12
u1 − 2x2 + z 1 2 u1 − 21 u1 − 23 u1
− −
1 2 x2 5 2 x2 1 2 x2
= 3 + x1
= + u2
=
− + u3 = Az egyes egyenletekb˝ol a b´azisv´altoz´okat kifejezve: z = 3 − u1 + 2x2 x1 = u2 = u3 =
3 2 9 2 11 2
− + +
1 2 u1 1 2 u1 3 2 u1
+ + +
1 2 x2 5 2 x2 1 2 x2 1 2 d, u2
3 2 9 2 11 2
1 Az u1 = 0, x2 = d > 0 ´ert´ekekkel az x1 = 23 + = 29 + 52 d, u3 = 11 + 2 2d lehets´eges megold´ast kapjuk, amely mellett a c´elf¨uggv´eny ´ert´eke z = 3 + 2d lesz, amely d → ∞ eset´en minden hat´aron t´ul n˝o.
9/12
u1 − 2x2 + z 1 2 u1 − 21 u1 − 23 u1
− −
1 2 x2 5 2 x2 1 2 x2
= 3 + x1
= + u2
=
− + u3 = Az egyes egyenletekb˝ol a b´azisv´altoz´okat kifejezve: z = 3 − u1 + 2x2 x1 = u2 = u3 =
3 2 9 2 11 2
− + +
1 2 u1 1 2 u1 3 2 u1
+ + +
1 2 x2 5 2 x2 1 2 x2 1 2 d, u2
3 2 9 2 11 2
1 Az u1 = 0, x2 = d > 0 ´ert´ekekkel az x1 = 23 + = 29 + 52 d, u3 = 11 + 2 2d lehets´eges megold´ast kapjuk, amely mellett a c´elf¨uggv´eny ´ert´eke z = 3 + 2d lesz, amely d → ∞ eset´en minden hat´aron t´ul n˝o.
9/12
Feladatok 1. Oldjuk meg a k¨ovetkez˝o LP-feladatot szimplex algoritmussal! x1 + 2x2 + x3 + x5 ≤ 100 x2 + x3 + x4 + x5 ≤ 80 x1 + x3 + x4 ≤ 50 x1, x2, x3, x4, x5 ≥ 0 2x1 + x2 + 3x3 + x4 + 2x5 = z → max Megold´as: x = (20, 0, 30, 0, 50), u = (0, 0, 0) z = 230
10/12
Feladatok 2. Oldjuk meg a k¨ovetkez˝o LP-feladatot szimplex algoritmussal! 2x1 − 5x2 ≤ 10 7x1 + 8x2 ≤ 56 −5x1 + 2x2 ≤ 10 x1, x2 ≥ 0 −x1 + 5x2 = z → max 175 777 Megold´as: x = ( 16 27 , 27 ), u = ( 27 , 0, 0) z =
859 27
11/12
Feladatok 3. Oldjuk meg a k¨ovetkez˝o LP-feladatot szimplex algoritmussal! x1 + x2 − x1 − −x1 + 2x2 + x1, x2, x3 6x1 + 7x2 + 2x3
x3 ≤ 12 x3 ≤ 8 2x3 ≤ 6 ≥ 0 = z → max
Megold´as: x = (9, 0, 12), u = (0, 2, 0) z = 132
11/12
Feladatok 4. Oldjuk meg a k¨ovetkez˝o LP-feladatot szimplex algoritmussal! x1 −
x2 + x3 ≤ 8 x2 + x3 − x4 ≤ 11 x1 + 2x2 − x3 + x4 ≤ 10 x1, x2, x3, x4, x5 ≥ 0 6x1 + 2x2 + 5x3 + 7x4 = z → max Megold´as: x = (0, 0, 8, 18), u = (0, 21, 0) z = 166
12/12
Felhaszn´ alt Irodalom
[1.] Bajalinov Erik - Imreh Bal´azs: Oper´ aci´ okutat´ as, Polygon 2005. [2.] Imreh Bal´azs: Bevezet´es az oper´ aci´ okutat´ asba, Phare 1999. [3.] Temesi J´ozsef - Varr´o Zolt´an: Oper´ aci´ okutat´ as, Aula 2007.
