Z´ aklady line´ arn´ıho programov´ an´ı Vyˇsˇs´ı matematika, Inˇzen´yrsk´a matematika LDF MENDELU
Podpoˇreno projektem Pr˚ uˇrezov´ a inovace studijn´ıch program˚ u Lesnick´ e a dˇrevaˇrsk´ e fakulty MENDELU v Brnˇ e (LDF) s ohledem na discipl´ıny spoleˇ cn´ eho z´ akladu http://akademie.ldf.mendelu.cz/cz (reg. ˇ e republiky. ˇ c. CZ.1.07/2.2.00/28.0021) za pˇrispˇ en´ı finanˇ cn´ıch prostˇredk˚ u EU a st´ atn´ıho rozpoˇ ctu Cesk´
Simona Fiˇsnarov´ a (MENDELU)
Z´ aklady line´ arn´ıho programov´ an´ı
VMAT, IMT
1 / 25
´ Uloha line´ arn´ıho programov´ an´ı – z´ akladn´ı pojmy ´ Ulohou line´ arn´ıho programov´ an´ı rozum´ıme u ´lohu naj´ıt maximum nebo minimum line´ arn´ı funkce n promˇenn´ych x1 , x2 , . . . , xn : z = c1 x1 + c2 x2 + · · · + cn xn
(1)
na mnoˇ zinˇ e zadan´ e soustavou line´ arn´ıch nerovnic nebo rovnic:
(2)
a11 x1 + a12 x2 + · · · + a1n xn
≤ .. .
b1
ak1 x1 + ak2 x2 + · · · + akn xn
≥ .. .
bk
am1 x1 + am2 x2 + · · · + amn xn
=
bm ,
x1 , x2 , . . . , xn ≥ 0.
(3)
Vˇsechny koeficienty aij , bj , ci , i ∈ {1, . . . , n}, j ∈ {1, . . . , m} jsou re´ aln´ a ˇc´ısla.
Simona Fiˇsnarov´ a (MENDELU)
Z´ aklady line´ arn´ıho programov´ an´ı
VMAT, IMT
2 / 25
Funkce (1) se naz´yv´a u ´ˇcelov´a funkce, podm´ınky (2) a (3) se naz´yvaj´ı omezuj´ıc´ı podm´ınky, pˇriˇcemˇz podm´ınky (2) se naz´yvaj´ı vlastn´ı omezen´ı a podm´ınky (3) se naz´yvaj´ı podm´ınky nez´apornosti. Pˇr´ıpustn´ym ˇreˇsen´ım u ´lohy line´arn´ıho programov´an´ı rozum´ıme vektor (x1 , x2 , . . . , xn ), kter´y vyhovuje omezuj´ıc´ım podm´ınk´am (2) a (3). Mnoˇzina vˇsech pˇr´ıpustn´ych ˇreˇsen´ı (tj. mnoˇzina vˇsech ˇreˇsen´ı soustavy (2), (3)) se naz´yv´a pˇr´ıpustn´a mnoˇzina. Optim´aln´ım ˇreˇsen´ım u ´lohy line´arn´ıho programov´an´ı rozum´ıme takov´e pˇr´ıpustn´e ˇreˇsen´ı, pro kter´e je hodnota u ´ˇcelov´e funkce maxim´aln´ı (resp. minim´aln´ı). Tato maxim´aln´ı (resp. minim´aln´ı) hodnota u ´ˇcelov´e funkce se naz´yv´a optim´aln´ı hodnota.
Simona Fiˇsnarov´ a (MENDELU)
Z´ aklady line´ arn´ıho programov´ an´ı
VMAT, IMT
3 / 25
Definice (Vrchol pˇr´ıpustn´ e mnoˇ ziny) ˇ ˇze bod Necht’ M ⊆ Rn je pˇr´ıpustn´a mnoˇzina urˇcen´a soustavou (2), (3). Rekneme, x ¯ ∈ M je vrchol mnoˇziny M , jestliˇze x ¯ neleˇz´ı na u ´seˇcce s krajn´ımi body x a y pro ˇz´adnou dvojici bod˚ u x, y ∈ M takov´ych, ˇze x 6= y 6= x ¯. Pozn´ amka (Konvexn´ı mnoˇ zina, polyedr) Mnoˇzina bod˚ u M ⊆ Rn se naz´yv´a konvexn´ı, jestliˇze spolu s kaˇzd´ymi dvˇema body x, y ∈ M patˇr´ı do mnoˇziny tak´e cel´a u ´seˇcka s krajn´ımi body x a y. Pˇr´ıpustn´a mnoˇzina urˇcen´a soustavou nerovnic (2), (3) je konvexn´ı mnoˇzina a naz´yv´a se polyedr.
Simona Fiˇsnarov´ a (MENDELU)
Z´ aklady line´ arn´ıho programov´ an´ı
VMAT, IMT
4 / 25
Vˇ eta Je-li pˇr´ıpustn´a mnoˇzina pr´azdn´a, pak u ´loha line´arn´ıho programov´an´ı nem´a ˇreˇsen´ı. Necht’ je pˇr´ıpustn´a mnoˇzina nepr´azdn´a a ohraniˇcen´a. Pak nab´yv´a u ´ˇcelov´a funkce sv´eho maxima (resp. minima) v nˇekter´em z vrchol˚ u pˇr´ıpustn´e mnoˇziny. Necht’ pˇr´ıpustn´a mnoˇzina nen´ı ohraniˇcen´a. Jestliˇze u ´ˇcelov´a funkce nab´yv´a na t´eto mnoˇzinˇe sv´eho maxima (resp. minima), pak se optim´aln´ı hodnota nach´az´ı v nˇekter´em z vrchol˚ u pˇr´ıpustn´e mnoˇziny. Nab´yv´a-li u ´ˇcelov´a funkce optim´aln´ı hodnoty ve dvou r˚ uzn´ych vrcholech, pak nab´yv´a optim´aln´ı hodnoty tak´e ve vˇsech bodech leˇz´ıc´ıch na u ´seˇcce urˇcen´e tˇemito vrcholy. Pozn´ amka Pokud nen´ı pˇr´ıpustn´a mnoˇzina ohraniˇcen´a, pak u ´loha nemus´ı m´ıt ˇreˇsen´ı, nebot’ u ´ˇcelov´a funkce nemus´ı b´yt nad touto mnoˇzinou shora (zdola) ohraniˇcen´a.
Simona Fiˇsnarov´ a (MENDELU)
Z´ aklady line´ arn´ıho programov´ an´ı
VMAT, IMT
5 / 25
Grafick´ e ˇreˇsen´ı – dvˇ e promˇ enn´ e
V pˇr´ıpadˇe dvou promˇenn´ych lze u ´lohu line´arn´ıho programov´an´ı vyˇreˇsit graficky pomoc´ı vrstevnic u ´ˇcelov´e funkce (viz absolutn´ı extr´emy funkce dvou promˇenn´ych). Pˇr´ıpustnou mmnoˇzinu zakresl´ıme jako pr˚ unik koneˇcn´eho poˇctu polorovin urˇcen´ych omezuj´ıc´ımi podm´ınkami. Grafem u ´ˇcelov´e funkce je rovina, jej´ıˇz vrstevnice jsou pˇr´ımky.
Simona Fiˇsnarov´ a (MENDELU)
Z´ aklady line´ arn´ıho programov´ an´ı
VMAT, IMT
6 / 25
Grafick´ e ˇreˇsen´ı – dvˇ e promˇ enn´ e
Je-li pˇr´ıpustn´ a mnoˇ zina ohraniˇ cen´ a, pak u ´ˇcelov´a funkce nab´yv´a na t´eto mnoˇzinˇe sv´eho maxima (resp. minima) v nˇekter´em z vrchol˚ u mnoˇziny. Maximum (minimum) tedy m˚ uˇzeme naj´ıt 1 2
bud’ pomoc´ı vrstevnic u ´ˇcelov´e funkce nebo tak, ˇze urˇc´ıme vrcholy pˇr´ıpustn´e mnoˇziny, spoˇc´ıt´ame hodnotu u ´ˇcelov´e funkce ve vˇsech vrcholech a vybereme nejvˇetˇs´ı (resp. nejmenˇs´ı) hodnotu.
Pˇritom se m˚ uˇze st´at, ˇze funkce nab´yv´a maxima (resp. minima) ve dvou r˚ uzn´ych vrcholech. V tom pˇr´ıpadˇe je maximum (minimum) nabyto ve vˇsech bodech u ´seˇcky, jej´ıˇz krajn´ı body jsou tyto vrcholy.
Simona Fiˇsnarov´ a (MENDELU)
Z´ aklady line´ arn´ıho programov´ an´ı
VMAT, IMT
7 / 25
Pˇr´ıklad (Ohraniˇ cen´ a pˇr´ıpustn´ a mnoˇ zina, jedno ˇreˇsen´ı) Najdˇete maximum funkce z = x1 + x2 na mnoˇzinˇe urˇcen´e nerovnostmi
x2
z=9 %
1 0
z=4 2
3
≥
−3
x1 + 2x2
≥
2
x1
≤
3
x1 , x2
≥
0
Po nakreslen´ı pˇr´ıpustn´e mnoˇziny vid´ıme, ˇze ´ tato mnoˇzina je ohraniˇcen´ a. Ulohu m˚ uˇzeme tedy vyˇreˇsit graficky pomoc´ı vrstevnic nebo porovn´ an´ım hodnot u ´ˇcelov´e funkce ve vrcholech:
max
6
3
x1 − x2
x1
z(0, 1)
=
0+1=1
z(2, 0)
=
2+0=2
z(3, 0)
=
3+0=3
z(3, 6)
=
3+6=9
z(0, 3)
=
0+3=3
V obou pˇr´ıpadech vid´ıme, ˇze u ´ˇcelov´ a funkce nab´yv´ a maxima v bodˇe (3, 6) (optim´ aln´ı ˇreˇsen´ı). Optim´ aln´ı hodnota je 9. Simona Fiˇsnarov´ a (MENDELU)
Z´ aklady line´ arn´ıho programov´ an´ı
VMAT, IMT
8 / 25
Pˇr´ıklad (Ohraniˇ cen´ a pˇr´ıpustn´ a mnoˇ zina, v´ıce ˇreˇsen´ı) Najdˇete maximum funkce z = −x1 + x2 na mnoˇzinˇe urˇcen´e nerovnostmi x1 − x2
≥
−3
x1 + 2x2
≥
2
x1
≤
3
x1 , x2
≥
0
Porovn´ ame hodnoty u ´ˇcelov´e funkce ve vrcholech: x2 6
z=3 z=1
3 1 0
2
3
Simona Fiˇsnarov´ a (MENDELU)
x1
z(0, 1)
=
−0 + 1 = 1
z(2, 0)
=
−2 + 0 = −2
z(3, 0)
=
−3 + 0 = −3
z(3, 6)
=
−3 + 6 = 3
z(0, 3)
=
−0 + 3 = 3
Vid´ıme, ˇze funkce nab´yv´ a maxima ve vrcholech (0, 3) a (3, 6). To znamen´ a, ˇze maximum je nabyto ve vˇsech bodech u ´seˇcky, kter´ a tyto dva body spojuje. Tot´eˇz je vidˇet i nakreseln´ım vrstevnic u ´ˇcelov´e funkce. Optim´ aln´ı hodnota je 3. Z´ aklady line´ arn´ıho programov´ an´ı
VMAT, IMT
9 / 25
Grafick´ e ˇreˇsen´ı – dvˇ e promˇ enn´ e
Je-li pˇr´ıpustn´ a mnoˇ zina neohraniˇ cen´ a a nab´yv´a-li u ´ˇcelov´a funkce sv´eho maxima (resp. minima) na t´eto mnoˇzinˇe, pak je tohoto maxima (minima) nabyto v nˇekter´em z vrchol˚ u mnoˇziny. M˚ uˇze vˇsak nastat situace, ˇze u ´ˇcelov´a funkce sv´eho maxima (resp. minima) na neohraniˇcen´e mnoˇzinˇe v˚ ubec nenab´yv´a. Metodu dosazen´ı vrchol˚ u tedy nelze pouˇz´ıt a maximum (resp. minimum) na neohraniˇcen´e mnoˇzinˇe vyˇsetˇrujeme vˇzdy pouze pomoc´ı vrstevnic u ´ˇcelov´e funkce.
Simona Fiˇsnarov´ a (MENDELU)
Z´ aklady line´ arn´ıho programov´ an´ı
VMAT, IMT
10 / 25
Pˇr´ıklad (Neohraniˇ cen´ a pˇr´ıpustn´ a mnoˇ zina) Najdˇete maximum a minimum funkce z = x1 + x2 na mnoˇzinˇe urˇcen´e nerovnostmi x1 − x2
x2
−2x1 + x2
≤ 2
x1 , x2
≥ 0
z→∞
% 2 z=4 z=2
min 0
≤ 1
1
x1
z=0
Simona Fiˇsnarov´ a (MENDELU)
Pˇr´ıpustn´a mnoˇzina nen´ı ohraniˇcen´a. Po nakreslen´ı vrstevnic vid´ıme, ˇze u ´ˇcelov´a funkce nab´yv´a minim´aln´ı hodnoty 0 v bodˇe (0, 0). ´ Uloha naj´ıt maximum vˇsak nem´a ˇreˇsen´ı, nebot’ u ´ˇcelov´a funkce nen´ı na pˇr´ıpustn´e mnoˇzinˇe shora ohraniˇcen´a. (Nab´yv´a zde libovolnˇe velk´ych hodnot.)
Z´ aklady line´ arn´ıho programov´ an´ı
VMAT, IMT
11 / 25
Simplexov´ a metoda
Simplexov´a metoda je (narozd´ıl od grafick´e metody) pouˇziteln´a pˇri libovoln´em poˇctu promˇenn´ych. Idea t´eto metody spoˇc´ıv´a v tom, ˇze “cestujeme po hran´ach” pˇr´ıpustn´e mnoˇziny od jednoho vrcholu ke druh´emu a hled´ame vrchol s optim´aln´ı hodnotou. Pˇritom nen´ı nutn´e obej´ıt vˇsechny vrcholy, nebot’ v kaˇzd´em vrcholu pozn´ame, zda jsme jiˇz dos´ahli optim´aln´ı hodnoty.
Simona Fiˇsnarov´ a (MENDELU)
Z´ aklady line´ arn´ıho programov´ an´ı
VMAT, IMT
12 / 25
Metodu si vysvˇetl´ıme na u ´loze zadan´e ve speci´aln´ım tvaru. V obecn´em pˇr´ıpadˇe je postup obdobn´y, ale trochu komplikovanˇejˇs´ı. Uvaˇzujme maximalizaˇcn´ı u ´lohu line´arn´ıho programov´an´ı: z = c1 x1 + c2 x2 + · · · + cn xn → max na mnoˇzinˇe zadan´e soustavou line´arn´ıch nerovnic: a11 x1 + a12 x2 + · · · + a1n xn
≤ b1
a21 x1 + a22 x2 + · · · + a2n xn
≤ b2 .. .
am1 x1 + am2 x2 + · · · + amn xn
≤ bm ,
x1 , x2 , . . . , xn ≥ 0, a pˇredpokl´adejme, ˇze bj ≥ 0 pro kaˇzd´e j ∈ {1, . . . , m}. Vˇsimnˇeme si, ˇze takto zadan´a pˇr´ıpustn´a mnoˇzina nen´ı pr´azdn´a, nebot’ vektor (0, 0, . . . , 0) splˇ nuje vˇsechny nerovnice. Simona Fiˇsnarov´ a (MENDELU)
Z´ aklady line´ arn´ıho programov´ an´ı
VMAT, IMT
13 / 25
Kaˇzdou z nerovnic tvoˇr´ıc´ıch vlastn´ı omezen´ı u ´lohy pˇrevedeme na rovnici tak, ˇze k lev´e stranˇe pˇriˇcteme novou nez´apornou promˇennou. Celkem tedy zavedeme dalˇs´ıch m promˇenn´ych, oznaˇcme je xn+1 , xn+2 , . . . , xn+m . Tyto promˇenn´e se naz´yvaj´ı doplˇ nkov´e promˇenn´e a vyjadˇruj´ı rozd´ıl mezi levou a pravou stranou p˚ uvodn´ıch nerovnost´ı. P˚ uvodn´ı u ´lohu jsme tedy pˇrevedli na u ´lohu: z = c1 x1 + c2 x2 + · · · + cn xn → max na mnoˇzinˇe zadan´e soustavou line´arn´ıch rovnic: a11 x1 + a12 x2 + · · · + a1n xn + xn+1 (4)
a21 x1 + a22 x2 + · · · + a2n xn .. . am1 x1 + am2 x2 + · · · + amn xn
= b1 + xn+2
= b2
+ xn+m = bm ,
x1 , x2 , . . . , xn+m ≥ 0,
Simona Fiˇsnarov´ a (MENDELU)
Z´ aklady line´ arn´ıho programov´ an´ı
VMAT, IMT
14 / 25
Definice (Bazick´ e ˇreˇsen´ı) ˇ sen´ı (x1 , x2 , . . . , xn+m ) soustavy (4) naz´yv´ame bazick´ym ˇreˇsen´ım, jestliˇze Reˇ x1 , x2 , . . . , xn+m ≥ 0, n (z celkov´eho poˇctu n + m) promˇenn´ych je nulov´ych sloupce matice soustavy (4) odpov´ıdaj´ıc´ı zb´yvaj´ıc´ım m promˇenn´ym jsou line´arnˇe nez´avisl´e (tj. je moˇzn´e je ekvivalentn´ımi u ´pravami pˇrev´est na jednotkovou matici). Tyto promˇenn´e naz´yv´ame bazick´e promˇenn´e. Bazick´e ˇreˇsen´ı se naz´yv´a degenerovan´e, jestliˇze jsou nulov´e i nˇekter´e bazick´e promˇenn´e. Tedy napˇr. vektor, jehoˇz sloˇzky jsou x1 = 0, x2 = 0, . . . , xn = 0, xn+1 = b1 , xn+2 = b2 , . . . , xn+m = bn , je bazick´e ˇreˇsen´ı soustavy (4), pˇriˇcemˇz bazick´e promˇenn´e jsou xn+1 , . . . , xn+m (sloupce odpov´ıdaj´ıc´ı tˇemto promˇenn´ym tvoˇr´ı jednotkovou matici a jsou tedy line´ arnˇe nez´ avisl´e).
Vˇ eta (Charakterizace vrchol˚ u) Vektor (x1 , x2 , . . . , xn+m ) je bazick´ym ˇreˇsen´ım soustavy (4) pr´avˇe tehdy, kdyˇz (x1 , x2 , . . . , xn ) je vrcholem pˇr´ıpustn´e mnoˇziny. Simona Fiˇsnarov´ a (MENDELU)
Z´ aklady line´ arn´ıho programov´ an´ı
VMAT, IMT
15 / 25
Danou u ´lohu jsme tedy pˇrevedli na u ´lohu naj´ıt takov´e bazick´e ˇreˇsen´ı soustavy (4), pro kter´e je odpov´ıdaj´ıc´ı hodnota u ´ˇcelov´e funkce c1 x1 + c2 x2 + · · · + cn xn maxim´aln´ı. Hodnotu u ´ˇcelov´e funkce m˚ uˇzeme pˇridat do soustavy jako dalˇs´ı promˇennou: Rovnici z = c1 x1 + c2 x2 + · · · + cn xn pˇrep´ıˇseme do tvaru −c1 x1 − c2 x2 − · · · − cn xn + z = 0 a pˇrid´ame k soustavˇe (4): a11 x1 + a12 x2 + · · · + a1n xn + xn+1 a21 x1 + a22 x2 + · · · + a2n xn .. .
= b1 + xn+2
am1 x1 + am2 x2 + · · · + amn xn −c1 x1 −
c2 x 2 − · · · −
cn xn
= b2
+ xn+m
= bm , +z = 0
x1 , x2 , . . . , xn+m ≥ 0, Simona Fiˇsnarov´ a (MENDELU)
Z´ aklady line´ arn´ıho programov´ an´ı
VMAT, IMT
16 / 25
Koeficienty z´ıskan´e soustavy zap´ıˇseme do tabulky:
xn+1 xn+2
x1 a11 a21
x2 a12 a22
··· ··· ···
xn a1n a2n .. .
xn+1 1 0
xn+2 0 1
··· ··· ···
xn+m 0 0
b1 b2
xn+m z
am1 −c1
am2 −c2
··· ···
amn −cn
0 0
0 0
··· ···
1 0
bm 0
Toto je tzv. v´ychoz´ı simplexov´ a tabulka a m˚ uˇzeme z n´ı vyˇc´ıst v´ychoz´ı bazick´e ˇreˇsen´ı: x1 = 0, x2 = 0, . . . , xn = 0, xn+1 = b1 , xn+2 = b2 , . . . , xn+m = bn . V lev´em sloupci vid´ıme bazick´e promˇenn´e a promˇennou z, v prav´em sloupci vid´ıme hodnotu bazick´ych promˇenn´ych a hodnotu promˇenn´e z (tj. hodnotu u ´ˇcelov´e funkce). Ostatn´ı promˇenn´e nejsou bazick´e a klademe je rovny nule. Toto v´ychoz´ı pˇr´ıpustn´e ˇreˇsen´ı odpov´ıd´ a vrcholu (0, 0, . . . , 0) pˇr´ıpustn´e mnoˇziny, hodnota u ´ˇcelov´e funkce je zde nulov´ a. Sloupec odpov´ıdaj´ıc´ı promˇenn´e z jsme z´ amˇernˇe vynechali, nebot’ se d´ ale nebude mˇenit.
Simona Fiˇsnarov´ a (MENDELU)
Z´ aklady line´ arn´ıho programov´ an´ı
VMAT, IMT
17 / 25
Nyn´ı je potˇreba odpovˇedˇet na ot´azku, zda je v´ychoz´ı hodnota z optim´aln´ı a pokud ne, jak´ym zp˚ usobem naj´ıt bazick´e ˇreˇsen´ı s vˇetˇs´ı hodnotou, pˇr´ıpadnˇe jak poznat, ˇze optim´aln´ı hodnota neexistuje. Kriterium optimality Jsou-li vˇsechny koeficienty v posledn´ım ˇr´adku tabulky (ˇr´adek u ´ˇcelov´e funkce) nez´aporn´e, pak z je optim´aln´ı hodnota a odpov´ıdaj´ıc´ı vektor (x1 , x2 , . . . , xn ) (v pˇr´ıpadˇe v´ychoz´ı tabulky (0, 0, . . . , 0)) je optim´aln´ı ˇreˇsen´ı. Je-li alespoˇ n jeden koeficient v posledn´ım ˇr´adku z´aporn´y, vybereme koeficient s nejv´ıce z´apornou hodnotou a sloupec, ve kter´em se tento koeficient nach´az´ı, nazveme kl´ıˇcov´y sloupec. a. Pokud se v kl´ıˇcov´em sloupci nenach´ az´ı ˇz´ adn´y kladn´y prvek, znamen´ a to, ˇze u ´ˇcelov´ a funkce nen´ı nad pˇr´ıpustnou mnoˇzinou shora ohraniˇcen´ a a maxim´ aln´ı ´ hodnota tedy neexistuje. Uloha nem´ a ˇreˇsen´ı. b. Pokud je alespoˇ n jeden prvek v kl´ıˇcov´em sloupci kladn´y, pak najdeme nov´e bazick´e ˇreˇsen´ı.
Simona Fiˇsnarov´ a (MENDELU)
Z´ aklady line´ arn´ıho programov´ an´ı
VMAT, IMT
18 / 25
Pˇrechod k nov´ emu bazick´ emu ˇreˇsen´ı 1
Pro vˇsechny kladn´e prvky v kl´ıˇcov´em sloupci spoˇcteme pod´ıly: odpov´ıdaj´ıc´ı hodnota bj kladn´y prvek kl´ıˇcov´eho sloupce v j-t´em ˇr´adku a vybereme prvek, pro kter´y je tento pod´ıl nejmenˇs´ı. Tento prvek nazveme kl´ıˇcov´y prvek a odpov´ıdaj´ıc´ı ˇr´adek nazveme kl´ıˇcov´y ˇr´adek.
2
Pomoc´ı ekvivalentn´ıch ˇr´adkov´ych u ´prav uprav´ıme tabulku tak, abychom m´ısto kl´ıˇcov´eho prvku dostali ˇc´ıslo jedna a na vˇsech ostatn´ıch pozic´ıch v kl´ıˇcov´em sloupci byly nuly. (Kl´ıˇcov´y ˇr´adek vydˇel´ıme kl´ıˇcov´ym prvkem a pot´e vhodn´e n´asobky kl´ıˇcov´eho ˇr´adku pˇriˇc´ıt´ame k ostatn´ım ˇr´adk˚ um tabulky.)
3
Provedeme pˇreps´an´ı bazick´ych promˇenn´ych v prvn´ım sloupci. M´ısto p˚ uvodn´ı promˇenn´e bude v kl´ıˇcov´em ˇr´adku promˇenn´a odpov´ıdaj´ı kl´ıˇcov´emu sloupci.
4
Z nov´e tabulky vyˇcteme nov´e bazick´e ˇreˇsen´ı a odpov´ıdaj´ıc´ı hodnotu z. Stejn´ym zp˚ usobem jako u v´ychoz´ıho ˇreˇsen´ı zjist´ıme, zda je hodnota optim´aln´ı a pokud ne, pˇrejdeme k dalˇs´ımu bazick´emu ˇreˇsen´ı. Simona Fiˇsnarov´ a (MENDELU)
Z´ aklady line´ arn´ıho programov´ an´ı
VMAT, IMT
19 / 25
Pˇr´ıklad (Simplexov´ a metoda) ˇ ste u Reˇ ´lohu z = 2x1 + x2 − 2x3 → max pˇri omezuj´ıc´ıch podm´ınk´ach 2x1 − x2 − x3 ≤ 2 x1 − x2 + x3 ≤ 4 x1 + x2 + 2x3 ≤ 6 x1 , x2 , x3 ≥ 0 Zavedeme dopˇ nkov´e promˇenn´e a pˇrevedeme na soustavu rovnic (spolu s rovnic´ı pro u ´ˇcelovou funkci): 2x1 − x2 − x3 + x4 x1 − x2 + x3 x1 + x2 + 2x3
=2 + x5
=4 + x6
=6
−2x1 − x2 + 2x3 +z =0 x1 , x2 , x3 , x4 , x5 , x6 ≥ 0 Simona Fiˇsnarov´ a (MENDELU)
Z´ aklady line´ arn´ıho programov´ an´ı
VMAT, IMT
20 / 25
Pˇr´ıklad (Simplexov´ a metoda – pokraˇ cov´ an´ı)
V´ychoz´ı tabulka:
x4 x5 x6 z
x1 2 1 1 −2
x2 −1 −1 1 −1
x3 −1 1 2 2
x4 1 0 0 0
x5 0 1 0 0
x6 0 0 1 0
2 4 6 0
V´ychoz´ı bazick´e ˇreˇsen´ı: x1 = 0, x2 = 0, x3 = 0, x4 = 2, x5 = 4, x6 = 6, z = 0. V posledn´ım ˇr´ adku tabulky jsou z´ aporn´e hodnoty =⇒ budeme hledat jin´e bazick´e ˇreˇsen´ı s vˇetˇs´ı hodnotou z.
Simona Fiˇsnarov´ a (MENDELU)
Z´ aklady line´ arn´ıho programov´ an´ı
VMAT, IMT
21 / 25
Pˇr´ıklad (Simplexov´ a metoda – pokraˇ cov´ an´ı)
V´ychoz´ı tabulka:
x4 x5 x6 z
x1 2 1 1 −2
x2 −1 −1 1 −1
x3 −1 1 2 2
x4 1 0 0 0
x5 0 1 0 0
x6 0 0 1 0
2 4 6 0
V´ychoz´ı bazick´e ˇreˇsen´ı: x1 = 0, x2 = 0, x3 = 0, x4 = 2, x5 = 4, x6 = 6, z = 0. V posledn´ım ˇr´ adku tabulky jsou z´ aporn´e hodnoty =⇒ budeme hledat jin´e bazick´e ˇreˇsen´ı s vˇetˇs´ı hodnotou z. Z posledn´ıho ˇr´ adku tabulky vybereme nejv´ıce z´ aporn´y prvek. Tento prvek urˇcuje kl´ıˇcov´y sloupec.
Simona Fiˇsnarov´ a (MENDELU)
Z´ aklady line´ arn´ıho programov´ an´ı
VMAT, IMT
21 / 25
Pˇr´ıklad (Simplexov´ a metoda – pokraˇ cov´ an´ı)
V´ychoz´ı tabulka:
x4 x5 x6 z
x1 2 1 1 −2
x2 −1 −1 1 −1
x3 −1 1 2 2
x4 1 0 0 0
x5 0 1 0 0
x6 0 0 1 0
2 4 6 0
V´ychoz´ı bazick´e ˇreˇsen´ı: x1 = 0, x2 = 0, x3 = 0, x4 = 2, x5 = 4, x6 = 6, z = 0. V posledn´ım ˇr´ adku tabulky jsou z´ aporn´e hodnoty =⇒ budeme hledat jin´e bazick´e ˇreˇsen´ı s vˇetˇs´ı hodnotou z. Z posledn´ıho ˇr´ adku tabulky vybereme nejv´ıce z´ aporn´y prvek. Tento prvek urˇcuje kl´ıˇcov´y a ˇc´ısla v kl´ıˇcov´em sloupci spoˇc´ıt´ ame pod´ıly: sloupec. Pro vˇsechna kladn´ 2 = 1, 2
Simona Fiˇsnarov´ a (MENDELU)
4 = 4, 1
6 =6 1
Z´ aklady line´ arn´ıho programov´ an´ı
VMAT, IMT
21 / 25
Pˇr´ıklad (Simplexov´ a metoda – pokraˇ cov´ an´ı)
V´ychoz´ı tabulka:
x4 x5 x6 z
x1
x2
x3
x4
x5
x6
2 1 1 −2
−1 −1 1 −1
−1 1 2 2
1 0 0 0
0 1 0 0
0 0 1 0
2 4 6 0
V´ychoz´ı bazick´e ˇreˇsen´ı: x1 = 0, x2 = 0, x3 = 0, x4 = 2, x5 = 4, x6 = 6, z = 0. V posledn´ım ˇr´ adku tabulky jsou z´ aporn´e hodnoty =⇒ budeme hledat jin´e bazick´e ˇreˇsen´ı s vˇetˇs´ı hodnotou z. Z posledn´ıho ˇr´ adku tabulky vybereme nejv´ıce z´ aporn´y prvek. Tento prvek urˇcuje kl´ıˇcov´y sloupec. Pro vˇsechna kladn´ a ˇc´ısla v kl´ıˇcov´em sloupci spoˇc´ıt´ ame pod´ıly: 2 =1 , 2
4 = 4, 1
6 =6 1
Vybereme prvek, pro kter´y je pod´ıl nejmenˇs´ı – kl´ıˇcov´y prvek.
Simona Fiˇsnarov´ a (MENDELU)
Z´ aklady line´ arn´ıho programov´ an´ı
VMAT, IMT
21 / 25
Pˇr´ıklad (Simplexov´ a metoda – pokraˇ cov´ an´ı)
V´ychoz´ı tabulka:
x4 x5 x6 z
x1
x2
x3
x4
x5
x6
2 1 1 −2
−1 −1 1 −1
−1 1 2 2
1 0 0 0
0 1 0 0
0 0 1 0
2 4 6 0
V´ychoz´ı bazick´e ˇreˇsen´ı: x1 = 0, x2 = 0, x3 = 0, x4 = 2, x5 = 4, x6 = 6, z = 0. V posledn´ım ˇr´ adku tabulky jsou z´ aporn´e hodnoty =⇒ budeme hledat jin´e bazick´e ˇreˇsen´ı s vˇetˇs´ı hodnotou z. Z posledn´ıho ˇr´ adku tabulky vybereme nejv´ıce z´ aporn´y prvek. Tento prvek urˇcuje kl´ıˇcov´y sloupec. Pro vˇsechna kladn´ a ˇc´ısla v kl´ıˇcov´em sloupci spoˇc´ıt´ ame pod´ıly: 2 =1 , 2
4 = 4, 1
6 =6 1
Vybereme prvek, pro kter´y je pod´ıl nejmenˇs´ı – kl´ıˇcov´y prvek. Pomoc´ı ekvivalentn´ıch ˇr´ adkov´ych u ´prav pˇrejdeme k nov´e tabulce, ve kter´e bude na m´ıstˇe kl´ıˇcov´eho prvku ˇc´ıslo 1 a vˇsude jinde v kl´ıˇcov´em sloupci budou nuly. (Kl´ıˇcov´y ˇr´ adek vydˇel´ıme ˇc´ıslem 2 a pot´e pˇriˇcteme vhodn´e n´ asobky kl´ıˇcov´eho ˇr´ adku k ostatn´ım ˇr´ adk˚ um.) V prvn´ım sloupci pˇrep´ıˇseme bazick´e promˇenn´e – novou bazickou promˇennou bude x1 (m´ısto x4 ). Simona Fiˇsnarov´ a (MENDELU)
Z´ aklady line´ arn´ıho programov´ an´ı
VMAT, IMT
21 / 25
Pˇr´ıklad (Simplexov´ a metoda – pokraˇ cov´ an´ı) x1 1
x2 − 12
x3 − 12
x5
0
x6
0
− 12 3 2
3 2 5 2
x1 Druh´a tabulka:
x4 1 2 − 12 − 12
x5 0
x6 0
1
1
0
3
0
1
5
z 0 −2 1 1 0 0 2 Bazick´e ˇreˇsen´ı: x1 = 1, x2 = 0, x3 = 0, x4 = 0, x5 = 3, x6 = 5, z = 2. V posledn´ım ˇr´adku tabulky je z´aporn´a hodnota =⇒ hled´ame dalˇs´ı bazick´e ˇreˇsen´ı s vˇetˇs´ı hodnotou z.
Simona Fiˇsnarov´ a (MENDELU)
Z´ aklady line´ arn´ıho programov´ an´ı
VMAT, IMT
22 / 25
Pˇr´ıklad (Simplexov´ a metoda – pokraˇ cov´ an´ı) x1 1
x2 − 12
x3 − 12
x5
0
x6
0
− 12 3 2
3 2 5 2
x1 Druh´a tabulka:
x4 1 2 − 12 − 12
x5 0
x6 0
1
1
0
3
0
1
5
z 0 −2 1 1 0 0 2 Bazick´e ˇreˇsen´ı: x1 = 1, x2 = 0, x3 = 0, x4 = 0, x5 = 3, x6 = 5, z = 2. V posledn´ım ˇr´adku tabulky je z´aporn´a hodnota =⇒ hled´ame dalˇs´ı bazick´e ˇreˇsen´ı s vˇetˇs´ı hodnotou z. Jedin´a z´aporn´a hodnota v posledn´ım ˇr´adku urˇcuje kl´ıˇcov´y sloupec,
Simona Fiˇsnarov´ a (MENDELU)
Z´ aklady line´ arn´ıho programov´ an´ı
VMAT, IMT
22 / 25
Pˇr´ıklad (Simplexov´ a metoda – pokraˇ cov´ an´ı) x1 1
x2 − 12
x3 − 12
x5
0
− 12
3 2
1 2 − 12
x6
0
3 2
5 2
− 12
x1 Druh´a tabulka:
x4
x5 0
x6 0
1
1
0
3
0
1
5
z 0 −2 1 1 0 0 2 Bazick´e ˇreˇsen´ı: x1 = 1, x2 = 0, x3 = 0, x4 = 0, x5 = 3, x6 = 5, z = 2. V posledn´ım ˇr´adku tabulky je z´aporn´a hodnota =⇒ hled´ame dalˇs´ı bazick´e ˇreˇsen´ı s vˇetˇs´ı hodnotou z. Jedin´a z´aporn´a hodnota v posledn´ım ˇr´adku urˇcuje kl´ıˇcov´y sloupec, jedin´a kladn´a hodnota v kl´ıˇcov´em sloupci urˇcuje kl´ıˇcov´y prvek.
Simona Fiˇsnarov´ a (MENDELU)
Z´ aklady line´ arn´ıho programov´ an´ı
VMAT, IMT
22 / 25
Pˇr´ıklad (Simplexov´ a metoda – pokraˇ cov´ an´ı) x1 1
x2 − 12
x3 − 12
x5
0
− 12
3 2
1 2 − 12
x6
0
3 2
5 2
− 12
x1 Druh´a tabulka:
x4
x5 0
x6 0
1
1
0
3
0
1
5
z 0 −2 1 1 0 0 2 Bazick´e ˇreˇsen´ı: x1 = 1, x2 = 0, x3 = 0, x4 = 0, x5 = 3, x6 = 5, z = 2. V posledn´ım ˇr´adku tabulky je z´aporn´a hodnota =⇒ hled´ame dalˇs´ı bazick´e ˇreˇsen´ı s vˇetˇs´ı hodnotou z. Jedin´a z´aporn´a hodnota v posledn´ım ˇr´adku urˇcuje kl´ıˇcov´y sloupec, jedin´a kladn´a hodnota v kl´ıˇcov´em sloupci urˇcuje kl´ıˇcov´y prvek. Pomoc´ı ekvivalentn´ıch ˇr´adkov´ych u ´prav pˇrejdeme k nov´e tabulce, ve kter´e bude na m´ıstˇe kl´ıˇcov´eho prvku ˇc´ıslo 1 a vˇsude jinde v kl´ıˇcov´em sloupci budou nuly. (Kl´ıˇcov´y ˇr´adek vydˇel´ıme ˇc´ıslem 32 a pot´e pˇriˇcteme vhodn´e n´asobky kl´ıˇcov´eho ˇr´adku k ostatn´ım ˇr´adk˚ um.) V prvn´ım sloupci pˇrep´ıˇseme bazick´e promˇenn´e – novou bazickou promˇennou bude x2 (m´ısto x6 ).
Simona Fiˇsnarov´ a (MENDELU)
Z´ aklady line´ arn´ıho programov´ an´ı
VMAT, IMT
22 / 25
Pˇr´ıklad (Simplexov´ a metoda – pokraˇ cov´ an´ı)
Tˇret´ı tabulka:
x1
x1 1
x2 0
x5
0
0
x2
0
1
0 x2 =
z Bazick´e ˇreˇsen´ı: x1 =
8 3,
x3
x4
0
1 3 7 3 5 3 13 3
1 3 − 23 − 13 1 3
x5 0
10 3 ,
x3 = 0, x4 = 0,
1 0 0
x6 1 3 1 3 2 3 4 3
8 3 14 3 10 3 26 3 x5 = 14 3 ,
x6 = 0, z =
26 3 .
V posledn´ım ˇr´adku tabulky nen´ı ˇz´adn´a z´aporn´a hodnota =⇒ naˇsli jsme optim´aln´ı ˇreˇsen´ı. Optim´aln´ı ˇreˇsen´ı: x1 = 83 , x2 = Optim´aln´ı hodnota: z =
Simona Fiˇsnarov´ a (MENDELU)
10 3 ,
x3 = 0.
26 3 .
Z´ aklady line´ arn´ıho programov´ an´ı
VMAT, IMT
23 / 25
Minimalizaˇ cn´ı u ´loha Postup simplexov´e metody jsme si vysvˇetlili v pˇr´ıpadˇe, kdy hled´ame maximum u ´ˇcelov´e funkce. Obecnˇe plat´ı: min f = − max(−f ). M´ame-li tedy na zadan´e pˇr´ıpustn´e mnoˇzinˇe naj´ıt minimum funkce z = c1 x1 + c2 x2 + · · · + cn xn , postupujeme tak, ˇze najdeme maximum funkce z˜ = −c1 x1 − c2 x2 − · · · − cn xn . Mohou nastat tyto pˇr´ıpady: Maximum funkce z˜ = −c1 x1 − c2 x2 − · · · − cn xn na dan´e mnoˇzinˇe neexistuje. Pak na dan´e mnoˇzinˇe neexistuje ani minimum funkce z = c1 x1 + c2 x2 + · · · + cn xn . Maximum funkce z˜ = −c1 x1 − c2 x2 − · · · − cn xn na dan´e mnoˇzinˇe existuje. Necht’ hodnota tohoto maxima je z¯. Pak existuje i minimum funkce z = c1 x1 + c2 x2 + · · · + cn xn (ve stejn´ych bodech jako maximum funkce z˜) a jeho hodnota je −¯ z. Simona Fiˇsnarov´ a (MENDELU)
Z´ aklady line´ arn´ıho programov´ an´ı
VMAT, IMT
24 / 25
Vyuˇ zit´ı syst´ em˚ u poˇ c´ıtaˇ cov´ e algebry Pˇr´ıklad ˇ ste u Reˇ ´lohu z = 2x1 + x2 − 2x3 → max pˇri omezuj´ıc´ıch podm´ınk´ach 2x1 − x2 − x3 ≤ 2 x1 − x2 + x3 ≤ 4 x1 + x2 + 2x3 ≤ 6 x1 , x2 , x3 ≥ 0. ˇ sen´ı pomoc´ı Wolfram Alpha (http://www.wolframalpha.com/): Reˇ maximize 2x+y-2z on 2x-y-z<=2, x-y+z<=4, x+y+2z<=6, x>=0, y>=0, z>=0
Simona Fiˇsnarov´ a (MENDELU)
Z´ aklady line´ arn´ıho programov´ an´ı
VMAT, IMT
25 / 25
