Line´ arn´ı programov´ an´ı
Simplexov´ a metoda
Grafick´ a metoda
Optim´ aln´ı v´ yrobn´ı program
Optim´ aln´ı v´ yrobn´ı program Radka Zahradn´ıkov´a e-mail:
[email protected]
1. ˇcervence 2010
Literatura
Line´ arn´ı programov´ an´ı
Simplexov´ a metoda
Grafick´ a metoda
Obsah
1
Line´ arn´ı programov´ an´ı
2
Simplexov´ a metoda
3
Grafick´ a metoda
4
Optim´ aln´ı v´ yrobn´ı program ˇ sen´ı grafickou metodou Reˇ ˇ sen´ı simplexovou metodou Reˇ
5
Literatura
Optim´ aln´ı v´ yrobn´ı program
Literatura
Line´ arn´ı programov´ an´ı
Simplexov´ a metoda
Grafick´ a metoda
Optim´ aln´ı v´ yrobn´ı program
nejjednoduˇs´ı u ´loha matematick´eho modelov´an´ı aplikace: optimalizace v´yrobn´ıch pl´an˚ u, dˇelen´ı materi´alu, m´ıˇsen´ı surovin, dopravn´ıch pl´an˚ u pˇri z´asobov´an´ı atd. algoritmy ˇreˇsen´ı u ´lohy LP zaloˇzeny na vyuˇzit´ı numerick´ych metod ˇreˇsen´ı SLAR odvozen´ych od Gaussovy eliminaˇcn´ı metody
Literatura
Line´ arn´ı programov´ an´ı
Simplexov´ a metoda
Grafick´ a metoda
Optim´ aln´ı v´ yrobn´ı program
Literatura
Geometrick´ a interpretace
mnoˇzina pˇr´ıpustn´ych ˇreˇsen´ı V u ´lohy LP je podmnoˇzina prostoru R n , vymezen´a nerovnost´ı Av ≤ b c´ıl u ´lohy LP - naj´ıt pˇr´ıpustn´e ˇreˇsen´ı v ∗ ∈ V , kter´e maximalizuje (minimalizuje) danou line´arn´ı funkci z = cv → max, (pˇr´ıp. −cv → min) na pˇr´ıpustn´e mnoˇzinˇe V nepr´azdn´a mnoˇzina pˇr´ıpustn´ych ˇreˇsen´ı vytv´aˇr´ı v R n vˇzdy uzavˇren´y konvexn´ı polyedr kaˇzd´y uzavˇren´y konvexn´ı polyedr je jednoznaˇcnˇe pops´an sv´ymi vrcholy kaˇzd´y z vrchol˚ u polyedru pˇr´ıpustn´ych ˇreˇsen´ı u ´lohy LP bazick´e ˇreˇsen´ı optim´aln´ı ˇreˇsen´ı u ´lohy LP leˇz´ı v nˇekter´em z vrchol˚ u polyedru
Line´ arn´ı programov´ an´ı
Simplexov´ a metoda
Grafick´ a metoda
Optim´ aln´ı v´ yrobn´ı program
Kanonick´ y tvar
´ Uloha LP b´yv´a obvykle specifikov´ana jako: Av
≤ b, b ≥ 0
v
≥ 0
z
= cv + d → max v
Tento tvar u ´lohy LP se naz´yv´a kanonick´y. - pˇredpoklad nez´apornsti pˇr´ıpustn´ych ˇreˇsen´ı - poˇc´atak soustavy souˇradnic - bazick´e ˇreˇsen´ı
Literatura
Line´ arn´ı programov´ an´ı
Simplexov´ a metoda
Grafick´ a metoda
Optim´ aln´ı v´ yrobn´ı program
Literatura
obecn´a metoda ˇreˇsen´ı u ´lohy LP pro u ´lohu v kanonick´em tvaru transformace u ´lohy zaveden´ım vektoru pomocn´ych promˇenn´ych v ∈ R m , definovan´eho zp˚ usobem: v = b − Av nerovnost Av ≤ b splnˇena pokud v ≥ 0 → ˇreˇsen´ı v pˇr´ıpustn´e pokud v ≥ 0 a v ≥ 0 simplexov´y tvar: Av + v
=
b, b ≥ 0, v ≥ 0, v ≥ 0
z − cv
=
d
z
→ max v ,v
d´ale iterativn´ı vyuˇzit´ı Gaussovy eliminace
Line´ arn´ı programov´ an´ı
Simplexov´ a metoda
Grafick´ a metoda
Optim´ aln´ı v´ yrobn´ı program
Simplexov´ y algoritmus
Pˇredpokl´adejme, ˇze m´ame u ´lohu line´arn´ıho programov´an´ı ve standardn´ım tvaru. Tj. Av
≤
b
v
≥
0
cv
→ max v
kde z = cv je c´ılov´a funkce, Av ≤ b jsou omezuj´ıc´ı podm´ınky a v ≥ 0 je podm´ınka nez´apornosti.
Literatura
Line´ arn´ı programov´ an´ı
Simplexov´ a metoda
Grafick´ a metoda
Optim´ aln´ı v´ yrobn´ı program
Literatura
Simplexov´ y algoritmus
Nalezen´ı v´ ychoz´ıho bazick´ eho ˇreˇsen´ı Zaveden´ım pomocn´ych promˇenn´ych v pˇrevedeme danou u ´lohu do kanonick´eho tvaru, kter´y potˇrebujeme pro aplikaci t´eto metody. Av + v
=
b
z − cv
=
d
z
→ max v ,v
V´ychoz´ım bazick´ym ˇreˇsen´ım zvol´ıme poˇc´atek soustavy souˇradnic, tzn. v = 0, v = b
Line´ arn´ı programov´ an´ı
Simplexov´ a metoda
Grafick´ a metoda
Optim´ aln´ı v´ yrobn´ı program
Simplexov´ y algoritmus
Sestaven´ı simplexov´ e tabulky
e
z
v1 a1,1 a2,1 .. .
v2 a1,2 a2,2 .. .
... ... ... .. .
vn a1,n a2,n .. .
v1 1 0 .. .
v2 0 1 .. .
... ... ... .. .
vm 0 0 .. .
b1 b2 .. .
am,1 −c1
am,2 −c2
... ...
am,n −cn
0 0
0 0
... ...
1 0
bm d
Literatura
Line´ arn´ı programov´ an´ı
Simplexov´ a metoda
Grafick´ a metoda
Optim´ aln´ı v´ yrobn´ı program
Simplexov´ y algoritmus
Nalezen´ı bazick´ eho ˇreˇsen´ı s vyˇsˇs´ı hodnotou c´ılov´ e funkce Podoba simplexov´e tabulky a bazick´eho ˇreˇsen´ı v k-t´em kroku algoritmu: ek z
v Ak ck
bk dk
vik = bik ⇔ i ∈ e k / ek vik = 0 ⇔ i ∈
Literatura
Line´ arn´ı programov´ an´ı
Simplexov´ a metoda
Grafick´ a metoda
Optim´ aln´ı v´ yrobn´ı program
Simplexov´ y algoritmus
Nalezen´ı bazick´ eho ˇreˇsen´ı s vyˇsˇs´ı hodnotou c´ılov´ e funkce v´ybˇer nov´e bazick´e promˇenn´e (kl´ıˇcov´eho sloupce) na z´akladˇe hodnoty prvk˚ u vektoru c k v´ybˇer bazick´e promˇenn´e, kter´a bude vyˇrazena z b´aze bk (kl´ıˇcov´eho ˇr´adku) na z´akladˇe hodnoty pod´ılu: aki i,j
pˇrepoˇcet nov´eho bazick´eho ˇreˇsen´ı a vyˇc´ıslen´ı hodnoty c´ılov´e funkce vyuˇzit´ım Gaussovy eliminace
Literatura
Line´ arn´ı programov´ an´ı
Simplexov´ a metoda
Grafick´ a metoda
Optim´ aln´ı v´ yrobn´ı program
Literatura
Simplexov´ y algoritmus Poˇ cet ˇreˇsen´ı Simplexov´y algoritmus m˚ uˇze b´yt ukonˇcen jedn´ım z n´asleduj´ıc´ıch v´ysledk˚ u: existuje pr´avˇe jedno ˇreˇsen´ı posledn´ı ˇr´adek simlexov´e tabulky neobsahuje ˇz´adn´e z´aporn´e a nulov´e prvky existuje nekoneˇcnˇe mnoho ˇreˇsen´ı posledn´ı ˇr´adek tabulky neobsahuje ˇz´adn´e z´aporn´e prvky a nav´ıc je prvek i vektoru c end odpov´ıdaj´ıc´ı nebazick´e promˇenn´e viend nulov´y. ˇreˇsen´ı je v nekoneˇcnu sloupec odpov´ıdaj´ıc´ı novˇe vybran´e bazick´e promˇenn´e neobsahuje ˇz´adn´y kladn´y prvek
Line´ arn´ı programov´ an´ı
Simplexov´ a metoda
Grafick´ a metoda
Optim´ aln´ı v´ yrobn´ı program
Literatura
Popis metody
Pro vˇsechny omezuj´ıc´ı podm´ınky zaneseme do grafu hraniˇcn´ı pˇr´ımky definuj´ıc´ı poloroviny a oznaˇc´ıme smˇer polorovin. Najdeme pr˚ unik jednotliv´ych polorovin - polyedr ohraniˇcuj´ıc´ı mnoˇzinu pˇr´ıpustn´ych ˇreˇsen´ı u ´lohy. Nalezneme extrem´aln´ı vrchol. Urˇc´ıme promˇenn´e u ´lohy LP a hodnotu c´ılov´e funkce v extrem´aln´ım vrcholu.
Line´ arn´ı programov´ an´ı
Simplexov´ a metoda
Grafick´ a metoda
Optim´ aln´ı v´ yrobn´ı program
Literatura
Zad´ an´ı probl´ emu
Beaver Creek Pottery Company je mal´a firma, kter´a vyr´ab´ı origin´aln´ı hrnky a misky. Spoleˇcnost pˇritom vyuˇz´ıv´a dva z´akladn´ı zdroje - speci´aln´ı hrnˇc´ıˇrskou hl´ınu a kvalifikovanou pr´aci. Na vyroben´ı 1 hrnku je potˇreba 3 libry hl´ıny a 2 hodiny pr´ace. Na vyroben´ı misky 4 libry hl´ıny a hodina pr´ace. Hrnek se prod´av´a za 50 dolar˚ u, miska za 40 dolar˚ u. Spoleˇcnost chce zjistit, kolik misek a kolik hrnk˚ u m´a kaˇzd´y den vyrobit, aby dos´ahla maxim´aln´ıho zisku, pokud m´a na kaˇzd´y den k dispozici 120 liber hl´ıny a pracovn´ı kapacita je 40 hodin.
Line´ arn´ı programov´ an´ı
Simplexov´ a metoda
Grafick´ a metoda
Optim´ aln´ı v´ yrobn´ı program
ˇ sen´ı grafickou metodou Reˇ
Formulace u ´lohy
x1 ...poˇcet misek x2 ...poˇcet hrnk˚ u C´ılem u ´lohy je naj´ıt takov´y poˇcet vyr´abˇen´ych kus˚ u jednotliv´ych v´yrobk˚ u, aby bylo dosaˇzeno maxima c´ılov´e funkce: z = 40x1 + 50x2 , Omezuj´ıc´ı podm´ınka pro pr´aci: 1x1 +2x2 ≤ 40. Omezuj´ıc´ı podm´ınka pro hl´ınu: 4x1 + 3x2 ≤ 120 Podm´ınky nez´apornosti: x1 ≥ 0 x2 ≥ 0
Literatura
Line´ arn´ı programov´ an´ı
Simplexov´ a metoda
Grafick´ a metoda
Optim´ aln´ı v´ yrobn´ı program
Literatura
ˇ sen´ı grafickou metodou Reˇ
Mnoˇ zina pˇr´ıpustn´ ych ˇreˇsen´ı Pokud nyn´ı pro obˇe omezuj´ıc´ı podm´ınky zaneseme do grafu hraniˇcn´ı pˇr´ımky definuj´ıc´ı poloroviny, oznaˇc´ıme smˇer polorovin a najdeme jejich pr˚ unik, dostaneme mnoˇzinu pˇr´ıpustn´ych ˇreˇsen´ı (viz obr. 1). 40
35 4x +3x =120 1
2
30
x2
25 x +2x =40 1
20
2
15
10
5
0
0
5
10
15
20 x
25
30
35
40
1
Obr´ azek: Mnoˇzina pˇr´ıpustn´ych ˇreˇsen´ı
Line´ arn´ı programov´ an´ı
Simplexov´ a metoda
Grafick´ a metoda
Optim´ aln´ı v´ yrobn´ı program
Literatura
ˇ sen´ı grafickou metodou Reˇ
Extrem´ aln´ı vrchol Z teorie v´ıme, ˇze funkce nab´yv´a sv´eho optima vˇzdy v jednom z vrchol˚ u polyedru. Pokud vykresl´ıme pˇr´ımku c´ılov´e funkce pro r˚ uzn´a z (napˇr. z=800, 1200, 1600 - viz obr. 2) zjist´ıme, ˇze c´ılov´a funkce nab´yv´a sv´eho maxima na mnoˇzinˇe pˇr´ıpustn´ych smˇer˚ u v bodˇe, kter´y je nejd´al od poˇc´atku. 35
30
40x +50x =1600
25
1
20
2
40x +50x =1200
x2
1
2
15 40x1+50x2=800 10
5
0
5
10
15
20 x
25
30
35
40
1
Obr´ azek: C´ılov´e funkce pro r˚ uzn´e hodnoty z
Line´ arn´ı programov´ an´ı
Simplexov´ a metoda
Grafick´ a metoda
Optim´ aln´ı v´ yrobn´ı program
Literatura
ˇ sen´ı grafickou metodou Reˇ
Extrem´ aln´ı vrchol Postup pro urˇcen´ı maxima (viz obr. 3): Nakresl´ıme pˇr´ımku c´ılov´e funkce pro libovoln´e z, napˇr. z=800 Nakresl´ıme pˇr´ımku rovnobˇeˇznou s pˇr´ımkou z=800 dot´ykaj´ıc´ı se mnoˇziny pˇr´ıpustn´ych ˇreˇsn´ı v bodˇe nejv´ıce vzd´alen´em od poˇc´atku - extrem´aln´ı vrchol 35
30
25
x2
20
15
10
5
0
5
10
15
20 x
25
30
35
40
1
Obr´ azek: Hled´an´ı extrem´aln´ıho vrcholu
Line´ arn´ı programov´ an´ı
Simplexov´ a metoda
Grafick´ a metoda
Optim´ aln´ı v´ yrobn´ı program
ˇ sen´ı grafickou metodou Reˇ
ˇ sen´ı v extrem´ Reˇ aln´ım vrcholu
ˇ s´ıme soustavu 2 rovnic: Reˇ 1x1 + 2x2 = 40 ⇒ x1 = 40 − 2x2 4x1 + 3x2 = 120 ⇒ 4(40 − 2x2 ) + 3x2 = 120 ⇒ 5x2 = 40
tedy x2 =8 ⇒ x1 =24. a z = 40x1 + 50x2 =40*24+50*8= 1360 dolar˚ u.
Literatura
Line´ arn´ı programov´ an´ı
Simplexov´ a metoda
Grafick´ a metoda
Optim´ aln´ı v´ yrobn´ı program
Literatura
ˇ sen´ı grafickou metodou Reˇ
Shrnut´ı Hodnoty ve vˇsech vrcholech polyedru Pro vrchol A dostaneme: x1 =0 misek, x2 =20 hrnk˚ u, z=1000 dolar˚ u. Pro vrchol B dostaneme: x1 =24 misek, x2 =8 hrnk˚ u, z=1360 dolar˚ u. Pro vrchol C dostaneme: x1 =30 misek, x2 =0 hrnk˚ u, z=1200 dolar˚ u. Zjistili jsme tedy, ˇze optim´aln´ı v´yrobn´ı program firmy je vyrobit kaˇzd´y den 24 misek a 8 hrnk˚ u, zisk firmy bude 1360 dolar˚ u dennˇe. 20
A
18 16 14
x2
12 10 8
B
6 4 2 C 0
0
5
10
15 x1
20
25
30
Obr´ azek: Mnoˇzina pˇr´ıpustn´ych ˇreˇsen´ı s vyznaˇcen´ymi vrcholy
Line´ arn´ı programov´ an´ı
Simplexov´ a metoda
Grafick´ a metoda
Optim´ aln´ı v´ yrobn´ı program
ˇ sen´ı simplexovou metodou Reˇ
Formulace u ´lohy
D´ano: c´ılov´a funkce: z = 40x1 + 50x2 omezuj´ıc´ı podm´ınky: 1x1 +2x2 ≤ 40, 4x1 +3x2 ≤ 120 podm´ınky nez´apornosti: x1 ≥ 0, x2 ≥ 0
Literatura
Line´ arn´ı programov´ an´ı
Simplexov´ a metoda
Grafick´ a metoda
Optim´ aln´ı v´ yrobn´ı program
Literatura
ˇ sen´ı simplexovou metodou Reˇ
Kanonick´ y tvar
´ Ulohu LP pˇrep´ıˇseme do kanonick´eho tvaru, abychom mohli pouˇz´ıt simlexovou metodu, tj. zavedeme pˇr´ıdavn´e promˇenn´e s1 a s2 . 1x1 + 2x2 + s1 = 40 4x1 + 3x2 + s2 = 120 z − 40x1 − 50x2 = 0 kde x1 ≥ 0, x2 ≥ 0, s1 ≥ 0, s2 ≥ 0 a z − 40x1 − 50x2 = 0 je pˇrepsan´a c´ılov´a funkce, kterou chceme maximalizovat.
Line´ arn´ı programov´ an´ı
Simplexov´ a metoda
Grafick´ a metoda
Optim´ aln´ı v´ yrobn´ı program
Literatura
ˇ sen´ı simplexovou metodou Reˇ
Simplexov´ a tabulka
Jako v´ychoz´ı bazick´e ˇreˇsen´ı vol´ıme poˇc´atek soustavy souˇradnic, tj. x1 = 0, x2 = 0 a dopoˇcteme hodnoty s1 , s2 . Tedy dostaneme: x (0) = (x1 , x2 , s1 , s2 ) = (0, 0, 40, 120). V´ychoz´ı simplexov´a tabulka m´a n´asleduj´ıc´ı tvar: s1 s2 z
x1 1 4 -40
x2 2 3 -50
s1 1 0 0
s2 0 1 0
b 40 120 0
Bazick´e promˇenn´e jsou v prvn´ım sloupci (s1 , s2 )
Line´ arn´ı programov´ an´ı
Simplexov´ a metoda
Grafick´ a metoda
Optim´ aln´ı v´ yrobn´ı program
ˇ sen´ı simplexovou metodou Reˇ
Hled´ an´ı nov´ eho bazick´ eho ˇreˇsen´ı-krok 1
Kl´ıˇcov´y sloupec - nalezen´ı nov´e bazick´e promˇenn´e Pouˇzijeme pravidlo v´ybˇeru promˇenn´e s nejvˇetˇs´ı absolutn´ı hodnotou z´aporn´eho prvku v posledn´ım ˇr´adku - tj. x2 . Kl´ıˇcov´y ˇr´adek - nalezen´ı vyˇrazovan´e bazick´e promˇenn´e Pro vˇsechny nez´aporn´e prvky kl´ıˇcov´eho sloupce spoˇcteme pod´ıl posledn´ıho sloupce tabulky a odpov´ıdaj´ıc´ıho prvku ˇ adek s nejmenˇs´ım pod´ılem je kl´ıˇcov´ym kl´ıˇcov´eho sloupce. R´ ˇr´adkem - tj. s1 . s1 s2 z
x1 1 4 -40
x2 2 3 -50
s1 1 0 0
s2 0 1 0
b 40 120 0
pod´ıl 40 2 = 20 120 3 = 40 -
Literatura
Line´ arn´ı programov´ an´ı
Simplexov´ a metoda
Grafick´ a metoda
Optim´ aln´ı v´ yrobn´ı program
Literatura
ˇ sen´ı simplexovou metodou Reˇ
Hled´ an´ı nov´ eho bazick´ eho ˇreˇsen´ı-krok 1 Kl´ıˇcov´y prvek Pr˚ useˇc´ık kl´ıˇcov´eho sloupce a kl´ıˇcov´eho ˇr´adku definuje kl´ıˇcov´y prvek (2). Promˇenn´a x2 nahrad´ı bazickou promˇennou s1 . Pˇrepoˇcet nov´eho bazick´eho ˇreˇsen´ı Vyuˇzit´ım Gaussovy eliminaˇcn´ı metody nahrad´ıme bazickou promˇennou odpov´ıdaj´ıc´ı kl´ıˇcov´emu ˇr´adku s1 promˇennou odpov´ıdaj´ıc´ı kl´ıˇcov´emu sloupci x2 . ˇ ıd´ıc´ım prvkem eliminace je kl´ıˇcov´y prvek, ke kaˇzd´emu ˇr´adku R´ pˇriˇcteme takov´y n´asobek kl´ıˇcov´eho ˇr´adku, aby hodnoty vˇsech prvk˚ u v kl´ıˇcov´em sloupci byly rovny 0. Kl´ıˇcov´y ˇr´adek uprav´ıme tak, aby na pozici kl´ıˇcov´eho prvku byla 1. n´asobek - 23 25
s1 s2 z
x1 1 4 -40
x2 2 3 -50
s1 1 0 0
s2 0 1 0
b 40 120 0
Line´ arn´ı programov´ an´ı
Simplexov´ a metoda
Grafick´ a metoda
Optim´ aln´ı v´ yrobn´ı program
ˇ sen´ı simplexovou metodou Reˇ
Hled´ an´ı nov´ eho bazick´ eho ˇreˇsen´ı-krok 1
Zisk nov´eho bazick´eho ˇreˇsen´ı Proveden´ım u ´prav dostaneme novou simplexovou tabulku: x1 x2 s2 z
1 2 5 2
-15
x2 1 0 0
s1 1 2
− 32 25
s2 0 1 0
b 20 60 1000
Nov´ym bazick´ym ˇreˇsen´ım je x (1) = (0, 20, 0, 60) a hodnota c´ılov´e funkce vzrostla na z=1000.
Literatura
Line´ arn´ı programov´ an´ı
Simplexov´ a metoda
Grafick´ a metoda
Optim´ aln´ı v´ yrobn´ı program
Literatura
ˇ sen´ı simplexovou metodou Reˇ
Hled´ an´ı nov´ eho bazick´ eho ˇreˇsen´ı-krok 2
Kl´ıˇcov´y sloupec - nalezen´ı nov´e bazick´e promˇenn´e Z´aporn´a hodnota v posledn´ım ˇr´adku je pouze u x1 , tedy jen pro tento prvek m˚ uˇze doj´ız k n´ar˚ ustu c´ılov´e funke, tj. x1 bude novou bazickou promˇennou. Kl´ıˇcov´y ˇr´adek - nalezen´ı vyˇrazovan´e bazick´e promˇenn´e Vypoˇcteme pod´ıl posledn´ıho sloupce tabulky a odpov´ıdaj´ıc´ıho prvku kl´ıˇcov´eho sloupce a zjist´ıme minim´aln´ı hodnotu → s2 bude vyˇrazenou promˇennou. x1 x2 s2 z
1 2 5 2
-15
x2 1 0 0
s1 1 2
− 32 25
s2 0 1 0
b 20 60 1000
pod´ıl 40 24 -
Line´ arn´ı programov´ an´ı
Simplexov´ a metoda
Grafick´ a metoda
Optim´ aln´ı v´ yrobn´ı program
Literatura
ˇ sen´ı simplexovou metodou Reˇ
Hled´ an´ı nov´ eho bazick´ eho ˇreˇsen´ı-krok 2
Kl´ıˇcov´y prvek Pr˚ useˇc´ık kl´ıˇcov´eho sloupce a kl´ıˇcov´eho ˇr´adku definuje kl´ıˇcov´y prvek 52 . Promˇenn´a x1 nahrad´ı bazickou promˇennou s2 . Pˇrepoˇcet nov´eho bazick´eho ˇreˇsen´ı Gaussovou eliminac´ı zajist´ıme, aby promˇenn´a x1 nahradila bazickou promˇennou s2 . n´asobek - 51 6
x1 x2 s2 z
1 2 5 2
-15
x2 1 0 0
s1 1 2
− 32 25
s2 0 1 0
b 20 60 1000
Line´ arn´ı programov´ an´ı
Simplexov´ a metoda
Grafick´ a metoda
Optim´ aln´ı v´ yrobn´ı program
Literatura
ˇ sen´ı simplexovou metodou Reˇ
Hled´ an´ı nov´ eho bazick´ eho ˇreˇsen´ı-krok 2
Zisk nov´eho bazick´eho ˇreˇsen´ı Proveden´ım u ´prav dostaneme novou simplexovou tabulku: x2 x1 z
x1 0 1 0
x2 1 0 0
s1 4 5
− 35 16
s2 - 51 1 6
b 8 24 1360
Nov´ym bazick´ym ˇreˇsen´ım je x (2) = (24, 8, 0, 0) a hodnota c´ılov´e funkce vzrostla na z=1360. Nyn´ı uˇz nem˚ uˇzeme vybrat promˇennou, kter´a by zv´yˇsila hodnotu c´ılov´e funkce, tedy algoritmus skonˇcil a st´avaj´ıc´ı bazick´e ˇreˇsen´ı je optim´aln´ım ˇreˇsen´ım u ´lohy.
Line´ arn´ı programov´ an´ı
Simplexov´ a metoda
Grafick´ a metoda
Optim´ aln´ı v´ yrobn´ı program
Literatura
ˇ sen´ı simplexovou metodou Reˇ
Shrnut´ı Hodnoty ve vˇsech vrcholech polyedru Pro vrchol A dostaneme: x1 =0, x2 =20,s1 =0, s2 =60, z=1000 Pro vrchol B dostaneme: x1 =24, x2 =8,s1 =0, s2 =0, z=1360 Pro vrchol C dostaneme: x1 =30, x2 =0,s1 =10, s2 =0, z=1200 Opˇet jsme tedy zjistili, ˇze optim´aln´ı v´yrobn´ı program firmy je vyrobit kaˇzd´y den 24 misek a 8 hrnk˚ u, zisk firmy bude 1360 dolar˚ u dennˇe. 40
35 4x1+3x2+s2=120 30
25
x
2
A
x +2x +s =40 1
20
2
1
15
B
10
5 C 0
0
5
10
15
20 x1
25
30
35
40
Obr´ azek: Mnoˇzina pˇr´ıpustn´ych ˇreˇsen´ı s vyznaˇcen´ymi vrcholy
Line´ arn´ı programov´ an´ı
Simplexov´ a metoda
Grafick´ a metoda
Optim´ aln´ı v´ yrobn´ı program
Zdroje
skripta k pˇredmˇetu Operaˇcn´ı anal´yza internetov´y zdroj: http://www.fi.muni.cz/ hlineny/Teaching/OU/OU-lect–6.pdf
Literatura
