MME I - cv. cˇ . 3
18. 10. 2010
Kl´ıcˇ ov´a slova: simplexov´a metoda
1
Simplexov´a metoda
Postup v´ypoˇctu: 1. Nalezen´ı v´ychoz´ıho ˇreˇsen´ı. 2. Test optima: • pokud je ˇreˇsen´ı optim´aln´ı v´ypoˇcet konˇc´ı, • jinak krok 3. 3. Iteraˇcn´ı krok, pot´e opˇet test optima.
1.1 Pˇr´ıklad 1 Bal´ırny cˇ aje Duk´at a.s. pl´anuj´ı na n´asleduj´ıc´ı obdob´ı v´yrobu dvou smˇes´ı cˇ aje Zlat´a smˇes a Standard. Pro v´yrobu tˇechto smˇes´ı maj´ı smluvnˇe k dispozici od dodavatel˚u tˇri druhy cˇ ern´eho cˇ aje (oznaˇcme je C1 , C2 , C3 ) postupnˇe o kapacitˇe 10, 12 a 15 tun liˇs´ıc´ıch se kvalitou a samozˇrejmˇe i n´akupn´ı cenou. Pˇri v´yrobˇe obou smˇes´ı je tˇreba dodrˇzovat technologick´e postupy, kter´e mimo jin´e urˇcuj´ı, jak´e procento jednotliv´ych komponent bude pouˇzito pˇri t´eto v´yrobˇe. N´asleduj´ıc´ı tabulka ukazuje skladbu obou smˇes´ı ( v tun´ach komponenty na 1 tunu smˇesi): Tab. 4.1: skladba k´avov´ych smˇes´ı: druh cˇ aje C1 C2 C3
cˇ ajov´a smˇes Zlat´a smˇes Standard 0,5 0,10 0,25 0,5 0,25 -
kapacita (t) 10 12 15
Na z´akladˇe pˇr´ım´ych a nepˇr´ım´ych n´aklad˚u souvisej´ıc´ıch s v´yrobou a vzhledem k pˇredpokl´adan´e cenˇe obou smˇes´ı byl vykalkulov´an zisk, kter´y cˇ in´ı 10000 Kˇc resp. 8000 Kˇc na 1 tunu smˇesi Zlat´a smˇes resp. Standard. Management firmy Duk´at a.s. chce samozˇrejmˇe napl´anovat produkci tak, aby byl jej´ı celkov´y zisk maxim´aln´ı.
1
MME I - cv. cˇ . 3
18. 10. 2010
ˇ sen´ı 1.2 Reˇ 1.2.1 V´ychoz´ı rˇ eˇsen´ı Matematick´y model (´ucˇ . fce v tis.): zmax = 10x1 + 8x2 0, 5x1 + 0, 1x2 0, 25x1 + 0, 5x2 0, 25x1 xi
10 12 15 0,
≤ ≤ ≤ ≥
i = 1, 2
Tato soustava line´arn´ıch rovnic je v obecn´em tvaru, je nutn´e ji pˇrev´est na standardn´ı tvar pomoc´ı pˇr´ıdatn´ych promˇenn´ych. 0, 5x1 + 0, 1x2 + x′1 0, 25x1 + 0, 5x2 + x′2 0, 25x1 + x′3 xi
≤ ≤ ≤ ≥
10 12 15 0,
i = 1, 2
Tato soustava je v kanonick´em tvaru, protoˇze odpov´ıdaj´ıc´ı matice strukturn´ıch koeficient˚u obsahuje 3 jednotkov´e vektory, kter´e lze uspoˇra´ dat do jednotkov´e matice. Soustava obsahuje 5 promˇenn´ych a 3 rovnice. Soustava m´a tedy maxim´alnˇe 10 z´akladn´ıch ˇreˇsen´ı (tj. poˇcet zp˚usob˚u jak lze vybrat 3 z´akladn´ı promˇenn´e z celkov´eho poˇctu 5 promˇenn´ych). Z´akladn´ı (bazick´e) promˇenn´e jsou x′1 , x′2 , x′3 Nez´akladn´ı promˇenn´e jsou x1 , x2 . Pokud poloˇz´ıme tyto nez´akladn´ı promˇenn´e rovny 0, potom z dan´e soustavy rovnic snadno z´ısk´ame hodnoty z´akladn´ıch promˇenn´ych: x′1 = 10, x′2 = 12, x′3 = 15 ˇ sen´ı z´ıskan´e t´ımto zp˚usobem je, vzhledem k nez´apornosti vˇsech jeho sloˇzek, Reˇ z´akladn´ım ˇreˇsen´ım dan´e u´ lohy LP. Po z´ısk´an´ı v´ychoz´ıho z´akladn´ıho ˇreˇsen´ı lze pˇristoupit v jednotliv´ych iterac´ıch k testu optimality a ke zlepˇsov´an´ı ˇreˇsen´ı. Cel´y v´ypoˇcet je organizov´an v tzv. simplexov´e tabulce. x′1 x′2 x′3 z
x1 1/2 1/4 1/4 -10
x2 x′1 1/10 1 1/2 0 0 0 -8 0 2
x′2 0 1 0 0
x′3 0 0 1 0
bi 10 12 15 0
MME I - cv. cˇ . 3
18. 10. 2010
Posledn´ı ˇra´ dek obsahuje koeficienty u´ cˇ elov´e funkce v anulovan´em tvaru, tj. tvaru, ve kter´em jsou vˇsechny promˇenn´e modelu pˇrevedeny na levou stranu a na prav´e stranˇe je absolutn´ı cˇ len, kter´y ud´av´a poˇca´ teˇcn´ı hodnotu u´ cˇ elov´e funkce ( ta je zpravidla rovna 0). V naˇsem pˇr´ıpadˇe: z − 10x1 − 8x2 = 0 Z´akladn´ı promˇenn´e: nespotˇrebovanou cˇ a´ st suroviny C1 (v tun´ach) nespotˇrebovanou cˇ a´ st suroviny C2 (v tun´ach) nespotˇrebovanou cˇ a´ st suroviny C3 (v tun´ach)
x′1 . . . vyjadˇruje x′2 . . . vyjadˇruje x′3 . . . vyjadˇruje
V´ychoz´ı z´akladn´ı ˇreˇsen´ı: X1 = (0, 0, 10, 12, 15), z = 0 Ekonomick´a interpretace: Nic se nevyr´ab´ı – hodnota u´ cˇ elov´e funkce je nulov´a. Nespotˇrebov´any jsou veˇsker´e suroviny, ˇreˇsen´ı nen´ı tud´ızˇ optim´aln´ı. 1.2.2 Test optima: • pˇri maximalizaci, jsou –li zj ≥ 0 pro vˇsechna j = 1, 2, . . . , n, z´akladn´ı ˇreˇsen´ı je maxim´aln´ı, je –li zj ≤ 0 alespoˇn pro jedno j = 1, 2, . . . , n, z´akladn´ı ˇreˇsen´ı nen´ı maxim´aln´ı. • pˇri minimalizaci, jsou–li zj ≤ 0 pro vˇsechna j = 1, 2, . . . , n, z´akladn´ı ˇreˇsen´ı je minim´aln´ı, je–li zj ≥ 0 alespoˇn pro jedno j = 1, 2, . . . , n, z´akladn´ı ˇreˇsen´ı nen´ı minim´aln´ı. 1.2.3 Pˇrechod na nov´e rˇ eˇsen´ı: Jedna z nez´akladn´ıch promˇenn´ych se stane z´akladn´ı: • vybereme j-t´y sloupec s minim´aln´ı z´apornou hodnotou v u´ cˇ . fci, (v pˇr´ıpadˇe minimalizaˇcn´ı u´ lohy vyb´ır´ame maxim´aln´ı kladnou hodnotu), • v dan´em sloupci vybereme vˇsechny koeficienty vˇetˇs´ı neˇz 0, • vypoˇcteme pod´ıly prav´ych stran bi a vybran´ych koeficient˚u, • vystupuj´ıc´ı promˇennou je ta, na kterou pˇripadne minim´aln´ı pod´ıl – i-t´y ˇra´ dek, • kl´ıcˇ ov´ym prvkem je prvek na pr˚useˇc´ıku i-t´eho ˇra´ dku a j-t´eho sloupce – aij . 3
MME I - cv. cˇ . 3
18. 10. 2010
V naˇsem pˇr´ıpadˇe je tedy kl´ıcˇ ov´y prvn´ı sloupec (z1 = −10), vstupuj´ıc´ı promˇennou je tedy x1 . Kl´ıcˇ ov´ym ˇra´ dkem je prvn´ı ˇra´ dek (jednotliv´e pod´ıly jsou 10 : 1/2 = 20, 12 : 1/4 = 48, 15 : 1/4 = 60 – minimum je 20) vystupuj´ıc´ı promˇenou je tedy x′1 . Pˇrechod k nov´emu ˇreˇsen´ı provedeme pomoc´ı Gaussovy eliminaˇcn´ı metody: V´ychoz´ı rˇ eˇsen´ı s vyznaˇcen´ym kl´ıcˇ ov´ym prvkem: x′1 x′2 x′3 z
x1 1/2 1/4 1/4 -10
x2 x′1 1/10 1 1/2 0 0 0 -8 0
x′2 0 1 0 0
x′3 0 0 1 0
bi 10 12 15 0
x2 x′1 1/5 2 9/20 -1/2 -1/20 -1/2 -6 20
x′2 0 1 0 0
x′3 0 0 1 0
bi 20 7 10 200
Nov´e rˇeˇsen´ı: x1 1 0 0 0
x1 x′2 x′3 z
Nov´e z´akladn´ı ˇreˇsen´ı vypl´yvaj´ıc´ı z druh´eho kroku je tedy: X2 = (20, 0, 0, 7, 10), z = 200 Ekonomick´a interpretace: Vyr´ab´ı se 20 tun smˇesi Zlat´a smˇes. Ze surovin je plnˇe spotˇrebov´ana komponenta C1 , z˚ust´av´a nevyuˇzito 7 tun komponenty C2 a 10 tun komponenty C3 . Hodnota produkce je 200 000 tis. Kˇc. V´ypoˇcet d´ale pokraˇcuje testem optimality, ˇreˇsen´ı nen´ı jeˇstˇe optim´aln´ı. Ve tˇret´ım kroku simplexov´e tabulky pˇrejdeme na dalˇs´ı z´akladn´ı ˇreˇsen´ı. Vstupuj´ıc´ı promˇennou je x2 a nahrazuje vystupuj´ıc´ı promˇennou x′2 , kter´a se st´av´a nez´akladn´ı. Optim´aln´ı rˇ eˇsen´ı: x1 x2 x′3 z
x1 1 0 0 0
x2 0 1 0 0
x′1 x′2 x′3 20/9 -4/9 0 -10/9 20/9 0 -10/18 1/9 1 120/9 120/9 0
4
bi 152/9 140/9 97/9 880/3
MME I - cv. cˇ . 3
18. 10. 2010
Ve tˇret´ım iteraˇcn´ım kroku dost´av´ame optim´aln´ı ˇreˇsen´ı, nebot’ vˇsechna zj ≥ 0: Xopt = (16,89, 15,56, 0, 0, 10,78), z = 293,3 Ekonomick´a interpretace: Optim´aln´ım v´yrobn´ım programem je vyr´abˇet 16,89 tun Smˇesi Super a 15,56 tun smˇesi Standard. Pˇri tomto v´yrobn´ım programu jsou plnˇe spotˇrebov´any cˇ aje C1 a C2 Nevyuˇzito z˚ust´av´a 10,78t cˇ aje C3 . Hodnota produkce je 293 333,3 tis. Kˇc a z dan´ych surovin nen´ı moˇzno za pˇredpokl´adan´ych podm´ınek z´ıskat vˇetˇs´ı. Nenulov´e hodnoty v ˇra´ dku u´ cˇ elov´e funkce simplexov´e tabulky pod pˇr´ıdatn´ymi promˇenn´ymi x′1 a x′2 jsou tzv. st´ınov´e ceny ud´avaj´ı n´am o kolik vzroste hodnota u´ cˇ . fce pokud zv´ysˇ´ıme kapacitu pˇr´ısluˇsn´eho zdroje o jednotku. V naˇsem pˇr´ıpadˇe, pokud zv´ysˇ´ıme kapacitu cˇ aje C1 o tunu, zv´ysˇ´ı se u´ cˇ elov´a funkce o 13 333,33 Kˇc. Z pohledu bal´ıren Duk´at a. s. to m´a tedy v´yznam, zda se vyplat´ı nakoupit o tunu v´ıce cˇ aje C1 .
1.3 Pˇr´ıklad 2 Naleznˇete ˇreˇsen´ı u´ lohy LP: zmin = 6x1 − 2x2 − 8x3 Pˇri platnosti tˇechto omezen´ı: −x1 + 2x2 x1 − 4x2 − 2x3 −x2 + x3 xi
≤ ≤ ≤ ≥
6 8 7 0,
i = 1, 2, 3
Simplexov´a tabulka: x1 x2 x′3 z
x1 -1 1 0 -6
x2 2 -4 -1 2
x3 0 -2 1 8
x′1 1 0 0 0
x′2 0 1 0 0
x′3 0 0 1 0
bi 6 8 7 0
Pˇri volbˇe vstupuj´ıc´ı a vystupuj´ıc´ı promˇenn´e je tˇreba myslet na skuteˇcnost, zˇ e se jedn´a o minimalizaˇcn´ı u´ lohu. Vstupuj´ıc´ı promˇennou je tedy sloupec s nejvyˇssˇ´ı kladnou hodnotou v ˇra´ dku u´ cˇ elov´e funkce. D´ale se postupuje stejnˇe jako u maximalizaˇcn´ı u´ lohy. Vstupuj´ıc´ı promˇennou je tedy x3 a vystupuj´ıc´ı promˇennou je x′3 (v tomto pˇr´ıpadˇe je to jednoduˇssˇ´ı t´ım, zˇ e ve 3. sloupci je jedin´y kladn´y koeficient vyˇssˇ´ı neˇz 0 ve 3. ˇra´ dku). 5
