filename: Lukacs-mind.txt, 2007.11.28. ******************************************************** **** **** **** RÉSZLETESEN KIDOLGOZOTT LIN.PROG. FELADAT **** **** **** **** dr.Szalkai István, Pannon Egyetem,Veszprém **** **** 2007.11.28. **** **** **** ******************************************************** Eredeti feladat: ~~~~~~~~~~~~~~~~ Egy gyárban négyféle terméket készítenek: A, B, C, D. Ezek gyártásához két erőforrást használnak fel. Az egyes termékek erőforrás szükségletét, az erőforrások kapacitását és az egyes termékek eladási árát (1000 Ft/db) az alábbi táblázat mutatja: Erőforrások | Termékek Erőforrások | A B C D kapacitása --------------+-------------------------------------------- I. erőforrás | 7 2 11 9 2000 II. erőforrás | 12 8 0 7 3000 --------------+-------------------------------------------- Eladási ár | 60 70 55 112 És most jönnek az egyéb kikötések és feltételek. Hány darabot gyártson a gyár az egyes termékekből, ha a célja a maximális árbevétel és a következő feltételeknek kell teljesülniük: 1. Az I. erőforrás kapacitását teljesen ki kell használni. 2. A B termékből 12 darabbal többet kell termelni mint A-ból. 3. A D termékből legalább kétszer annyit kell termelni, mint C-ből. 4. A B-ből és a D-ből összesen legalább 5 millió forint értékűt kell termelni. Feladat matematikai modelleje: ~~~~~~~~~~~~~~~~~~~~~ I. 7 X1 + 2 X2 + 11 X3 + 9 X4 = 2000 II. 12 X1 + 8 X2 + + 7 X4 <= 3000 (kisebb vagy =) III. – X1 + X2 = 12 IV. 2 X3 – X4 <= 0 V. 70 X2 + + 112 X4 >= 5000 (nagyobb vagy =) 60*X1+70*X2+55*X3+112*X4 => max. ! A feladat megoldása: ************************ ELŐKÉSZÍTÉS: ============ A <= jeleknél bevezetjük az x5,x6 "maradék"változókat, = ami a raktáron marad, természetesen 0-szoros tényezővel kerül be a célfüggvénybe, A >= jeleknél bevezetjük a -x7 "többlet"változókat, így minden sorban tiszta = van: I. 7 X1 + 2 X2 + 11 X3 + 9 X4 = 2000 II. 12 X1 + 8 X2 + + 7 X4 +x5 = 3000 III. – X1 + X2 = 12 IV. 2 X3 – X4 +x6 = 0 V. 70 X2 + + 112 X4 – x7 = 5000 kétfázisú szimplex módszer kell: #=============# H 1.fázis H #=============# Ahol eredetileg = vagy >= volt, ott bevezetjük az u1,u2,u3 fiktív változókat, és addig "dolgozunk", amíg ezek kiesnek. A hozzájuk tartozó (ún.másodlagos) célfüggvény ennek megfelelő- en: max(-u1-u2-u3) . I. 7 X1 + 2 X2 + 11 X3 + 9 X4 +u1 = 2000 II. 12 X1 + 8 X2 + + 7 X4 +x5 = 3000 III. – X1 + X2 +u2 = 12 IV. 2 X3 – X4 +x6 = 0 V. 70 X2 + + 112 X4 – x7 +u3 = 5000 (60*X1+70*X2+55*X3+112*X4) => max.! másodlagos célfüggvény: max(-u1-u2-u3) /azaz a mesterséges változók eltüntetése/ A szimplex tábla felállítása: ------------------------+-------------------------------- 2000 7 2 11 9 0 0 0 1 0 0 # -1 3000 12 8 0 7 1 0 0 0 0 0 # 0 12 -1 1 0 0 0 0 0 0 1 0 # -1 0 0 0 2 -1 0 1 0 0 0 0 # 0 5000 0 70 0 112 0 0 -1 0 0 1 # -1 ------------------------+-------------------------------- -7012 -6 -73 -11 -121 0 0 1 0 0 0 # = cB*yj-cj ------------------------+---------------------------------- b a1 a2 a3 a4 | a5 a6 a7 u1 u2 u3 cB c: 0 0 0 0 | 0 0 0 -1 -1 -1 cB*yj-cj számításai: -7 +1 - 0 -0 = -6, -2 -1 - 70 -0 = -73, -11 -0 - 0 -0 = -11, -9 -0 -112 -0 = -121, a számítások részletei és a végeredmény a jelen file végén ### LA9-1.out ### alatt olvashatók. a végső táblázat: A1 A2 A3 A4 A5 A6 A7 A8 A9 A10 A11 ------------------------------------------------------------------------------------- A4| 29.4802 0 0 1 0 -0.0198 0.2577 0 0.0441 0.0705 0 A2| 124.5639 1 0 0 0 0.0639 0.1696 0 -0.0308 -0.4493 -0 A8|11163.0308 0 0 0 0 0.0308 -42.4009 1 7.7093 54.3348 -1 A3| 136.5639 0 1 0 0 0.0639 0.1696 0 -0.0308 0.5507 0 A5| 58.9604 0 0 0 1 -0.0396 -0.4846 0 0.0881 0.1410 0 e6| -0 0 0 0 0 0 0 0 1 1 1 ------------------------------------------------------------------------------------- b a1 a2 a3 a4 a5 a6 a7 u1 u2 u3 A megoldás optimális, vége az 1. fázisnak. Tehát az induló bázis: a gép jelöléseivel = {A4,A2,A8,A3,A5} azaz a mi jelöléseinkkel = {a3,a1,a7,a2,a4} vagyis sikerült kiejtetnünk az u1,u2,u3 fiktív változókat. Jöhet a 2.fázis #=============# H 2.fázis H #=============# Az induló táblázat az eredeti célfüggvénnyel: max(60*X1+70*X2+55*X3+112*X4) c | B | b | a1 a2 a3 a4 | a5 a6 a7 ----+----+--------------------------------------------------------+------------------- 55 | a3| 29.4802 | 0 0 1 0 | -0.0198 0.2577 0 60 | a1| 124.5639 | 1 0 0 0 | 0.0639 0.1696 0 0 | a7| 11163.0308 | 0 0 0 0 | 0.0308 -42.4009 1 70 | a2| 136.5639 | 0 1 0 0 | 0.0639 0.1696 0 112 | a4| 58.9604 | 0 0 0 1 | -0.0396 -0.4846 0 ----+------------------+------------------------------------------+------------------- | 25258.2828 | 0 0 0 0 | 2.7828 -18.0537 0 +-------------+---------------------------------------------+---------------- 55* (29.4802)+60*(124.5639)+0*(11163.0308 )+70*(136.5639)+112*(58.9604) = 25258,2828 55*(-0.0198)+60*(0.0639)+0* (0.0308)+70*(0.0639)+112*(-0.0396) - 0 = 2,7828 55* (0.2577)+60*(0.1696)+0*(-42.4009)+70*(0.1696)+112*(-0.4846) - 0 = -18,0537 Mivel az a6 oszlopában (z-c) értéke negatív és oszlopában VAN felette pozitív elem, ezért javíthatjuk a célfüggvényt. Egy transzformáció elég, így a számításokat nem írjuk külön file-ba, hanem alább ismertetjük. j=a6 oszlopa, min{29.4802/0.2577, 124.5639/0.1696, 136.5639/0.1696 } = 114,39736 vagyis i=1 sor a főelem. Transzformáció után : c | B | b | a1 a2 a3 a4 | a5 a6 a7 ----+----+--------------------------------------------------------------------- | a6| 114.3974 | 0 0 3.8805 0 | -0.0768 1 0 60 | a1| 105.1621 | 1 0 -0.6581 0 | 0.0769 0 0 0 | a7| 16013.5819 | 0 0 164.5359 0 | -3.2270 0 1 70 | a2| 117.1621 | 0 1 -0.6581 0 | 0.0769 0 0 112 | a4| 114.3974 | 0 0 1.8805 1 | -0.0768 0 0 ----+-------------------+------------------------------------------+---------------- | 27323.5784 | 0 0 70.057 0 | 1.3957 0 0 +--------------+---------------------------------------------+-------------- Vagyis a célfüggvény maximális értéke 27323.5784 . Ez elég jól megegyezik egy program által számított értékkel A változók értékei és részük a maximumban: ----------------------------------------------------------- Variable Value * Coeff = Contrib ----------------------------------------------------------- x1 105.1624 * 60 = 6309.7451 x2 117.1624 * 70 = 8201.3691 x3 0.0000 * 55 = 0.0000 x4 114.3931 * 112 = 12812.0273 ----------------------------------------------------------- Összesen: = 27323,1415 (=max) Az eredeti egyenlőtlenség-rendszerben a bal- és jobboldal eltérései: Feladat eredetileg: ~~~~~~~~~~~~~~~~~~~ I. 7*105.1624+ 2*117.1624+ 11*0 + 9*114.3931 = 1999,9995 = 2000 OK II. 12*105.1624+ 8*117.1624+ + 7*114.3931 = 2999,9997 <= 3000 OK III. -105.1624+ 117.1624 = 12,0000 = 12 OK IV. 2*0 - 114.3931 = - 114.3931 <= 0 OK V. 70*117.1624 +112*114.3931 = 21013,3952 >= 5000 OK ugyanez a program jelentése szerint: ------------------------------------------------------------------------- Constraint RHS Slack(-)/Surplus(+) Dual Price ------------------------------------------------------------------------- I. (=) 2000.0000 0.0000 11.3675 II. (<) 3000.0000 0.0000- 1.3846 III. (=) 12.0000 0.0000 36.1880 IV. (<) 0.0000 114.3931- 0.0000 V. (>) 5000.0000 16013.3965+ 0.0000 ############################# ### ### ### RÉSZLETSZÁMÍTÁSOK ### ### ### ############################# 1.fázis: ### LA9-1.out ### ELEMI BAZISTRANSZFORMACIÓK, MEGADOTT FŐELEMEK ALAPJÁN (™) Szalkai István A beolvasott mátrix : ( A1,...,A11 és e1,...,e6 a gép változói, a mi jelölésünk b,a1,...,a7,u1,...,u3 .) A1 A2 A3 A4 A5 A6 A7 A8 A9 A10 A11 ---------------------------------------------------------------------------------------------------------------------------- e1| 2000.0000 7.0000 2.0000 11.0000 9.0000 0.0000 0.0000 0.0000 1.0000 0.0000 0.0000 e2| 3000.0000 12.0000 8.0000 0.0000 7.0000 1.0000 0.0000 0.0000 0.0000 0.0000 0.0000 e3| 12.0000 -1.0000 1.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 1.0000 0.0000 e4| 0.0000 0.0000 0.0000 2.0000 -1.0000 0.0000 1.0000 0.0000 0.0000 0.0000 0.0000 e5| 5000.0000 0.0000 70.0000 0.0000 112.0000 0.0000 0.0000 -1.0000 0.0000 0.0000 1.0000 e6|-7012.0000 -6.0000 -73.0000 -11.0000 -121.0000 0.0000 0.0000 1.0000 0.0000 0.0000 0.0000 ---------------------------------------------------------------------------------------------------------------------------- b a1 a2 a3 a4 | a5 a6 a7 u1 u2 u3 2.oszlop => minimumszabály: min{2000/7, 3000/12} => A főelem sora és oszlopa: 2 , 2 e1| 250.0000 0.0000 -2.6667 11.0000 4.9167 -0.5833 0.0000 0.0000 1.0000 0.0000 0.0000 A2| 250.0000 1.0000 0.6667 0.0000 0.5833 0.0833 0.0000 0.0000 0.0000 0.0000 0.0000 e3| 262.0000 0.0000 1.6667 0.0000 0.5833 0.0833 0.0000 0.0000 0.0000 1.0000 0.0000 e4| 0.0000 0.0000 0.0000 2.0000 -1.0000 0.0000 1.0000 0.0000 0.0000 0.0000 0.0000 e5| 5000.0000 0.0000 70.0000 0.0000 112.0000 0.0000 0.0000 -1.0000 0.0000 0.0000 1.0000 e6|-5512.0000 0.0000 -69.0000 -11.0000 -117.5000 0.5000 0.0000 1.0000 0.0000 0.0000 0.0000 3.oszlop => minimumszabály: min{250/0.6667, 262/1.67, 5000/70} => A főelem sora és oszlopa: 5 , 3 e1| 440.4762 0.0000 0.0000 11.0000 9.1833 -0.5833 0.0000 -0.0381 1.0000 0.0000 0.0381 A2| 202.3810 1.0000 0.0000 0.0000 -0.4833 0.0833 0.0000 0.0095 0.0000 0.0000 -0.0095 e3| 142.9524 0.0000 0.0000 0.0000 -2.0833 0.0833 0.0000 0.0238 0.0000 1.0000 -0.0238 e4| 0.0000 0.0000 0.0000 2.0000 -1.0000 0.0000 1.0000 0.0000 0.0000 0.0000 0.0000 A3| 71.4286 0.0000 1.0000 0.0000 1.6000 0.0000 0.0000 -0.0143 0.0000 0.0000 0.0143 e6| -583.4286 0.0000 0.0000 -11.0000 -7.1000 0.5000 0.0000 0.0143 0.0000 0.0000 0.9857 5.oszlop => minimumszabály: min{440.476/9.1833, 71.4286/1.60} => A főelem sora és oszlopa: 5 , 5 e1| 30.5060 0.0000 -5.7396 11.0000 0.0000 -0.5833 0.0000 0.0439 1.0000 0.0000 -0.0439 A2| 223.9583 1.0000 0.3021 0.0000 0.0000 0.0833 0.0000 0.0052 0.0000 0.0000 -0.0052 e3| 235.9583 0.0000 1.3021 0.0000 0.0000 0.0833 0.0000 0.0052 0.0000 1.0000 -0.0052 e4| 44.6429 0.0000 0.6250 2.0000 0.0000 0.0000 1.0000 -0.0089 0.0000 0.0000 0.0089 A5| 44.6429 0.0000 0.6250 0.0000 1.0000 0.0000 0.0000 -0.0089 0.0000 0.0000 0.0089 e6| -266.4643 0.0000 4.4375 -11.0000 0.0000 0.5000 0.0000 -0.0491 0.0000 0.0000 1.0491 4.oszlop => minimumszabály: min{30.506/11, 44.643/2} => A főelem sora és oszlopa: 1 , 4 A4| 2.7733 0.0000 -0.5218 1.0000 0.0000 -0.0530 0.0000 0.0040 0.0909 0.0000 -0.0040 A2| 223.9583 1.0000 0.3021 0.0000 0.0000 0.0833 0.0000 0.0052 0.0000 0.0000 -0.0052 e3| 235.9583 0.0000 1.3021 0.0000 0.0000 0.0833 0.0000 0.0052 0.0000 1.0000 -0.0052 e4| 39.0963 0.0000 1.6686 0.0000 0.0000 0.1061 1.0000 -0.0169 -0.1818 0.0000 0.0169 A5| 44.6429 0.0000 0.6250 0.0000 1.0000 0.0000 0.0000 -0.0089 0.0000 0.0000 0.0089 e6| -235.9583 0.0000 -1.3021 0.0000 0.0000 -0.0833 0.0000 -0.0052 1.0000 0.0000 1.0052 3.oszlop => minimumszabály: min{223.958/0.3021, 235.9583/1.3021, 39.0963/1.6686} => A főelem sora és oszlopa: 4 , 3 A4| 14.9992 0.0000 0.0000 1.0000 0.0000 -0.0199 0.3127 -0.0013 0.0341 0.0000 0.0013 A2| 216.8802 1.0000 0.0000 0.0000 0.0000 0.0641 -0.1810 0.0083 0.0329 0.0000 -0.0083 e3| 205.4490 0.0000 0.0000 0.0000 0.0000 0.0006 -0.7804 0.0184 0.1419 1.0000 -0.0184 A3| 23.4312 0.0000 1.0000 0.0000 0.0000 0.0636 0.5993 -0.0101 -0.1090 0.0000 0.0101 A5| 29.9984 0.0000 0.0000 0.0000 1.0000 -0.0397 -0.3746 -0.0026 0.0681 0.0000 0.0026 e6| -205.4490 0.0000 0.0000 0.0000 0.0000 -0.0006 0.7804 -0.0184 0.8581 0.0000 1.0184 8.oszlop => minimumszabály: min{216.88/0.0083, 205.449/0.0184} => A főelem sora és oszlopa: 3 , 8 A1 A2 A3 A4 A5 A6 A7 A8 A9 A10 A11 ---------------------------------------------------------------------------------------------------------------------------- A4| 29.4802 0.0000 0.0000 1.0000 0.0000 -0.0198 0.2577 0.0000 0.0441 0.0705 0.0000 A2| 124.5639 1.0000 0.0000 0.0000 0.0000 0.0639 0.1696 0.0000 -0.0308 -0.4493 -0.0000 A8|11163.0308 0.0000 0.0000 0.0000 0.0000 0.0308 -42.4009 1.0000 7.7093 54.3348 -1.0000 A3| 136.5639 0.0000 1.0000 0.0000 0.0000 0.0639 0.1696 0.0000 -0.0308 0.5507 0.0000 A5| 58.9604 0.0000 0.0000 0.0000 1.0000 -0.0396 -0.4846 0.0000 0.0881 0.1410 0.0000 e6| -0.0000 0.0000 0.0000 0.0000 0.0000 -0.0000 0.0000 0.0000 1.0000 1.0000 1.0000 ---------------------------------------------------------------------------------------------------------------------------- b a1 a2 a3 a4 | a5 a6 a7 u1 u2 u3 A megoldás optimális, vége az 1. fázisnak. Tehát az induló bázis: a gép jelöléseivel = {A4,A2,A8,A3,A5} azaz a mi jelöléseinkkel = {a3,a1,a7,a2,a4} vagyis sikerült kiejtetnünk az u1,u2,u3 fiktív változókat. Jöhet a 2.fázis eof eof