28

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. ˇ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´ e republiky.

Simona Fiˇsnarov´a

Brno 2014

´ 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 : (1)

z = c1 x1 + c2 x2 + · · · + cn xn

na mnoˇ zinˇ e zadan´ e soustavou line´ arn´ıch nerovnic nebo rovnic:

(2)

(3)

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.

Vˇsechny koeficienty aij , bj , ci , i ∈ {1, . . . , n}, j ∈ {1, . . . , m} jsou re´ aln´ a ˇc´ısla.

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.

1

Definice (Vrchol pˇr´ıpustn´ e mnoˇ ziny) ˇ Necht’ M ⊆ Rn je pˇr´ıpustn´a mnoˇzina urˇcen´a soustavou (2), (3). Rekneme, ˇze bod 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.

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.

2

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.

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.

3

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

x1 − x2

≥

−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 z=9 %

3 1

z=4

0

2

x1

3

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.

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

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. 4

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.

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

x2

≤ 1

−2x1 + x2

≤ 2

x1 , x2

≥ 0

z→∞

% 2 z=4 z=2

min 0

x1 − x2

1

z=0

x1

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.)

5

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.

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. 6

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 .. .

= b1 + xn+2

am1 x1 + am2 x2 + · · · + amn xn

= b2

+ xn+m = bm ,

x1 , x2 , . . . , xn+m ≥ 0,

Definice (Bazick´ e ˇreˇsen´ı) ˇ sen´ı (x1 , x2 , . . . , xn+m ) soustavy (4) naz´yv´ame bazick´ Reˇ ym ˇreˇsen´ım, jestliˇze 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. 7

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 − · · · −

= b2

+ xn+m

cn xn

= bm , +z = 0

x1 , x2 , . . . , xn+m ≥ 0,

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.

8

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´ı.

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´ı.

9

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

=2 + x5

x1 + x2 + 2x3

=4 + x6

=6

−2x1 − x2 + 2x3 +z =0 x1 , x2 , x3 , x4 , x5 , x6 ≥ 0

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 ). 10

Pˇr´ıklad (Simplexov´ a metoda – pokraˇ cov´ an´ı)

Druh´a tabulka:

x1

x1 1

x2 − 12

x3 − 12

x4

x5

0

− 12

3 2

1 2 − 12

x6

0

3 2

5 2

− 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, 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 ).

Pˇr´ıklad (Simplexov´ a metoda – pokraˇ cov´ an´ı)

Tˇret´ı tabulka:

x1

x1 1

x2 0

x5

0

0

x2

0

1

z

0

Bazick´e ˇreˇsen´ı: x1 = 83 , x2 =

x3

x4

x5 0

0

1 3 7 3 5 3 13 3

1 3 − 23 − 13 1 3

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 =

10 3 ,

x3 = 0.

26 3 .

11

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.

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

12