• ,
' '
I
Obsah
PŘEDMLUVA
oBSAH.,. ...
!' . . . . . . . . . . . . . . .. . . . . . . . . . . ' . . . . . . . . . . . " ' . . . . . . . . . . . . . . . . . . . . . . .
I~····
..................".. . . . . . . ..
li ... . .. .. . . . . . . . . . . . . . . . . . . . ... .. . ... . . . . . . • • • • • • • • •
s
1. OPERACE S VEKTORY A MATICEMI, SOUSTAVY LINEÁRNÍCH ROVNIC -· 7
] .1. ŘEŠENÉ PŘÍKLADY ... ............ ... . ...... . '' ....... ... .. ... ... ... . .... . ... .............. ...... ... ... ............. .. .... 7
1.2. PŘÍKLADY K. PROCVIČBNÍ ................................... ....... ........................... ... ................... l4
1.3.
ŘEŠENJ PŘIKLADŮ ......................................... .......................... ......... ........................... 18
2.. SESTA VENÍ MODELU LINEÁRNÍHO PROGRAM OVÁNÍ.. ..................·-············· 23
2.1 . ŘEŠENÉ PŘ.fKLADY ........... ... . ...... ...................... .. ................................ ................ ...... ... 23
2.2. PŘÍKLADY K PROCVIČEN Í ..... ............................. ...... ............ ........................................ 28
2.3. ŘEŠEN Í PŘÍKLADŮ ....... .. ...... .. .. ..................... .......... ................ ............ .. . ................. ... 34
l. GRAFICKÉ ŘEŠENÍ MODELU LINEÁRNÍHO PROGRAM OV ÁNÍ ············-·····.. 40
3.1. Ř€~ENÉ PŘÍKLADY ..... ... .................... . ... ...... ... .. ..... ..... ........ .... .. .. ................................ .. . 40
3.2. PŘÍK LADY K PROCV1ČENÍ ....... ... .. ................... ... ... .. ... ..... .... .. .............. ... .... ...... ............ 51
3.3. ŘEŠENf PŘfKLADŮ . ....................... ......... ................................. ................... ........... ..... 56
'
4·. SIMYLEXOVY ALGORJTMUS ····-·····"'·--······························- ··········· . ·•····~ ............................ , ~
4.1. ŘEŠENÉ PfdKLADY .......................... .... ............ ....... ....... .... ................ ........................... . 66
4.2. PŘÍKLADY K PROCVlČENÍ ....... .... ................... .. ............. .... ...... ... ........ .......... ...... ......... 75
4.3. ŘEŠENÍ PŘÍKLADŮ ........................................... ..................................... ..................... ... 80
S. LITERA TURA ............-. .....- ....... . -...............................................................................--....................................... 89
5
1.
Operace s vektory a maticemi, soustavy lineárních rovnic
Cílem této kapitoly je poskytnout čtenáři k dispozici matematické nástroje, bez
kterých se při řešení úloh lineárního programování neobejde. Budou zopakovány základní
operace z oblasti lineárni algebry, jejichž bezpečné zvládnutí je klíčem k úspěšnému řešení
modelů LP i provádění postoptimalizačních analýz..
Řešené příklady
1. 1.
V následujícím textu budeme předpokládat, že
a = (3, -1, 2)
b - (2,5,-3)
jsou vektory vektorového prostoru dimenze 3 a
A~G ~I ~)
B=(~ ~3]
2 -1
C=(~l ~ ~ J
5
3 -4
jsou různé matice.
Sčítání vektorů
Vektory sčítáme po složkách. Výsledkem je vektor stejné dimenze jako sčítané vektory.
c =a+ b = (aJ+ bJ, a2 + b2, a3 + b3), tedy pro naše vektory
c = (3, -1, 2) + (2, 5, -3)- (5, 4, -1)
Vektory lze stejným způsobem odčítat:
c = a- b = (aJ - b~, a2- b2, a3- b3), tedy
c = (3, -1, 2)- (2, 5, -3) = (1, -6, 5)
Násobení vektoru skalárem
Nechť k = 5 je konstanta (skalár). Potom lze každý vektor touto konstantou vynásobit tak, že
se konstantou vynásobí každá složka daného vektoru:
c === k.a = (k.aJ, k.a2, k.a 3 ), tedy
c = 5.(3, -1, 2) = (15, -5, 10)
7
Skalární součin dvou vektorů
V prvním případě jsme vynásobili první řádek matice hodnotou 10, ve druhém jsme ke
druhému řádku přičetli dvojnásobek řádku prvního.
Násobit skalárně dva vektory znamená vynásobit mezi sebou odpovídající si složky obou
vektorů a poté tyto součiny sečíst. Výsledkem je jediná hodnota (skalár).
Inverzní matice, Jordanova eliminační metoda
d = a.b = a,.b 1 + a2 .b2 + a3.b3, nebo konkrétně
Podmínky pro existenci inverzní matice k dané matici jsou:
d ~ (3 -1 2) . (2 5, -3) "" 6 - 5 - 6 - -5
)
)
)
Je-li skalární součin dvou vektorů roven nule, pak jsou tyto vektory na sebe kolmé.
Lineární kombinace vektorů, lineární konvexní kombinace vektorů
• matice musí být čtvercová (musí mít stejný počet řádků jako sloupců),
• ř~dk,y ~atice .mus.í být li?eárně nezávislé (žádný z řádků nesmí být možno vyjádřit jako
hnearm kombmac1 ostatmch řádků).
Necht' / 1 = 3 a 12 """ -2 jsou konstanty. Pokud chceme vytvořit vektor c jako lineární kombinaci
vektorů a a b s koeficienty 11 a l2, musíme nejprve vynásobit každý vektor skalárně
příslušným koeficientem lineární kombinace a poté výsledné vektory sečíst:
Existuje ví~e způsobů jak inverzní matici nalézt. Nejčastěji se používá Jordanova eliminační
metoda. Její postup je následující, je dána matice C:
c - !,.a + /2.b :;;; (l,.a,, !,.a2, l,.a3) + (12.b/, l2.b2, l2.b3) = (l,.a,+hb,, z,.a2+l2.b2, J,.a3+l2.b3),
tedy
c=
c = 3. (3, -1, 2) + (-2). (2, 5, -3) = (9, -3, 6) + (-4, -10, 6) = (5, -13, 12)
Lineární kombinaci vektorú nazveme lineární konvexní kombinací v případě, že pro její
koeficienty platí:
11, 12 ~O (oba koeficienty jsou nezáporné) a
!, + l2 = 1 Qejich součet se rovná jedné).
(
oJ
2 4
-1 o
5
2
3 -4
K této matici připíšeme jednotkovou matici:
[
o
2
4
-1
o
5
3
1
OJ
o O1 o
-4 o o 1
2
c
N ásobení matic
Provádíme ekvivalentní operace tak, aby se jednotková matice přesunula na místo matice
Po dokončení přesunu získáme matici C 1 na místě, kde předtím byla jednotková matice.
Matice lze násobit pouze tehdy, pokud má první matice právě tolik sloupců jako druhá řádků.
Výsledkem operace je matice, která má počet řádků stejný jako první matice a počet sloupců
stejný jako druhá matice. Pokud je tedy matice P rozměru m x n a R je matice n x p,
výsledkem jejich součinu bude matice S o rozměru m xp.
~rovedem~ první k.rok. Potřebujeme přemístit pomocí matematických operací první sloupec
Jednotkove s~b~a~1c~ (celkově 4. sloupec) na pozicí prvního sloupce. Použijeme jeden krok
Jordanovy ehmmacm metody, který se skládá ze dvou částí:
Výsledná matice S obsahuje prvky sy, které dostaneme jako skalární součin i-tého řádku
matice P aj-tého sloupce matice R.
5J·(~ ~3]=(12 -5Jo
D = A.B = (1 O
2 -1 3
2 -1
• potřebujeme dostat na první pozici hodnotu 1, proto celý první řádek vydělíme dvěma.
[~1 ~
5
Ekvivalentní operace s maticemi jsou:
5]=(102 -O
SOJ
1 3
A=(1 O
2 -1 3
• přičtení libovolného násobku některého řádku k jinému řádku
8
!]-(:
3 -40
o
1
5
3 -4
o o
1
• v~~vchny ostatní ?odnoty v prvním sloupci musí být nulové, proto ke všem ostatním řádkům
pncteme vhodny násobek, nov~~o pn:_~!ho řádku. ~~ d;uhém řádku v prvním sloupci je
hodnota -1, proto ke druhemu radku pncteme nezmeneny nový první řádek (vynásobíme
ho hodnotou 1).
-1
o 0,5
o 2 o
5
3 -4
1
• násobení řádku matice skalární hodnotou (různou od nuly)
A~ G~~
~ ~ ~ ~J/: 2- [~1 ~ ~ 0~5 ~ ~J
10
Ekvivalentní operace s maticemi
5
~~ t 3J
·
[
2
O OJ 1·1 a přičíst ke druhému
1 o
o o
1
[
1 2
2
o
O 0,5 O OJ
2 0,5 1 o
53-40
Ol
Na třetím řád~u je v prvním sloupci hodnota 5, proto nový první řádek vynásobíme
hodnotou -5 přičteme ho k třetímu řádku.
9
[
O 0,5 O OJ/·(- 5) apřičístketřetímu
2 0,5 1 o
1 2
o 2
53-40
001
[
Ol
2
o
2
2 0,5
Ve druhém kroku potřebujeme dostat jednotkový vektor do druhého sloupce tak, aby jeho
0,5
-7 -4-2,5
jednička byla na druhém řádku. Přitom je ale potřeba zachovat jíž vytvořený jednotkový
O
OJ
1 o
o
vektor v prvním sloupci.
1
Je důležité přesně zachovat tento postup, pokud bychom řádky odečetli obráceně,
přišli bychom o jednotkovou submatici.
Stejným zpl'1sobem pokračujeme dále, dokud se celá jednotková submatice nepřesune.
1
o
[
o
~ ~:; o~ ~J-[~o o~
2
2
-7
4 -2,5
-o s
c-' - 0,~
[ - 0,25
1
1,33
-0,67
0,67
- 0,33
1,167
0,33
-2
o
1 0,25
o -0,5
-1
0,5
3 - 0,75 3,5
oOJ 1
[1o O
1 o
o o
1,33
0,67
0,5
-0,67 -0,33
I -0,25 1,167 0,33
J
J
Druhý řádek vydělíme hodnotou 2. Potom k prvnímu řádku přičteme nový druhý řádek a ke
třetímu řádku také nový druhý řádek. Transformace vypadá takto:
1 -1
21J [1 o 21J
2 00 - o 1 00
[ -1 66 o o 66
o
o
Nyní transformaci dokončíme. Třetí řádek vydělíme hodnotou 6. K prvnímu řádku přičteme
(-2) násobek nového třetího řádku, druhý řádek můžeme nechat beze změny (v jeho třetím
sloupci již nula je).
o0
2IJ0 -[10 1o0o0-1J
o1 1
[o
o 66
o o 11
Řešení soustav lineárních rovnic pomocí Jordanovy eliminační metody
Protože jsme celou dobu prováděli pouze ekvivalentní operace s vektory dané matice,
můžeme transformovanou soustavu přepsat z maticového tvaru zpět do tvaru rovnicového:
Pomocí Jordanovy eliminační metody lze řešit také soustavy lineárních rovnic.
x, + Oxz + Ox3 = -1
Soustavu lineárních rovnic
Ox1 + xz + Ox3 = O
2x, - 2xz ·I 4x3 -= 2
Ox1 + Oxz + x3
x 1 + x 2 + 2x3 := 1
ze kterého rovnou vidíme hledané hodnoty proměnných
-2x, + Xz + 2x3 = 4
x 1 =-l,xz = O,x3 "'= 1
můžeme zapsat do maticového tvaru
Řešení soustav lineárních rovnic s parametrem, bázická a nebázická řešení
-2
42J
1 21
1
proměnných dopočítat.
Pomocí Jordanovy eliminační metody transformujeme matici soustavy (matice koeficientů
proměnných, první tři sloupce matice) do formy jednotkové matice. Protože použijeme pouze
ekvivalentní operace na celé řádky matice, v posledním sloupci dostaneme hledané hodnoty
Mějme soustavu tří lineárních rovnic o pěti neznámých
4x, + 2xz + X3 - 2x4 - x5 = 23
proměnných.
x 1 +x2
V prvním kroku transformujeme matici tak, aby její první sloupec obsahoval jednotkový
vektor s jedničkou na prvním místě. Proto první řádek vydělíme dvěma, ke druhému řádku
přičteme (-1) násobek nového prvního řádku a ke třetímu řádku přičteme dvojnásobek nového
prvního řádku.
x, + 2xz
Transformovaná matice po prvním kroku vypadá takto:
~2 ~ ~] -[~ ~1 2001]
10
1
Pokud soustava lineárních rovnic obsahuje více proměnných než je rovnic, má daná soustava
nekonečně mnoho řešení. Abychom obdrželi nějaké konkrétní řešení, musíme hodnoty
některých proměnných zvolit (lze libovolně) a na jejich základě hodnoty ostatních
24
24
=
o
Protože je proměnných o dvě více než rovnic a rovnice jsou lineárně nezávislé, bude potřeba
při konstrukci konkrétního řešení dvě proměnné považovat za volitelný parametr a na jejich
základě hodnoty zbylých tří dopočítat.
Před odvozováním řešení je výhodné použít Jordanovu eliminační metodu a transformovat
matici soustavy do kanonického tvaru. To je tvar, ve kterém matice soustavy obsahuje
úplnou jednotkovou submatici.
-1 66
ll
Vybereme si tři sloupce proměnných, jejichž sloupcové vektory nejsou lineárně závislé,
například proměnné x 3 , x 4 a x 5 • Soustavu rovnic převedeme do maticové formy resp. do formy
tabulky, jejíž záhlaví tvoří názvy proměnných
x1
4
1
1
x2
x3
2
1
2
o
1
o
x2
x3
4
1
2
1
1
1
2
o
o
2
o
-1
-1
o
1
1
1
-1
o
o
o
1
o
o
23
-1
9
x.
-2
14
x2
x0
=
10- 2x1 -x2
-4+x1
x4
-2
-1
x5
-1
-1
23
9
-1
-2
14
o
Pokud bychom se z nějakého důvodu rozhodli, že nám současná báze nevyhovuje, snadno ji
můžeme změnit. Transformace se provádí opět pomocí Jordanovy eliminační metody.
1
1
1
o
-1
5
-9
5
Pro ilustraci můžeme vytvořit bázi obsahující proměnné
nahradí proměnnou x4:
b
1
o
-4
1
-5
-1
- -4
=:
-5+x2
x1
2
Pro názornost můžeme opět soustavu přepsat do formy rovnic:
+ X5
nebo formou vektoru obecného řešení, ve kterém vyjadřujeme bázické proměnné pomocí
pravých stran a nebázíckých proměnných
-1
-1
b
IoI I Io I I I
·X2
= (0, O, 1O, -4, -5)
xS
-1
I I I I I I I
2
o
o 10
-1
x8
x4
-2
a pomocí Jordanovy eliminační metody dosáhneme kanonického tvaru. Proměnná x 3 již ve
svém sloupci jednotkový vektor má, pod proměnné x 4 a x 5 ho pomocí dvou kroků dostaneme.
x1
Řešení můžeme zapsat formou vektoru bázického řešení
-5
o
x2
x3
1
1
o
o
-1
o
x4
o
1
o
xs
x,, XJ a xs; proměnná x,
tedy v bázi
b
o
o
10
-4
1
-5
I ~ I ~ I ~ I ~ I ~ I! I
a opět určit hodnoty proměnných v daném bázickém řešení:
Je zřejmé, že je při odvozování konkrétních řešení výhodné volit jako parametry proměnné x1
a x2, neboť proměnné x 3, x 4 a x 5 se vyskytují právě v jedné rovnici. Říkáme, že jejich vektory
tvoří bázi daného vektorového prostoru dimenze 3 (tři řádky, tři rovnice, tři složky
sloupcových vektorů). Proto tyto proměnné označujeme termínem bázická proměnná,
ostatní proměnné označujeme jako nebázické proměnné (parametry).
x 1 = 4 ... bázická proměnná na druhém řádku, je rovna druhé složce vektoru pravých stran
Uvedli jsme, že hodnoty parametrů můžeme volit libovolně. Pro pozdější použití je výhodné
definovat jeden speciální typ parametrického řešení; takové, že hodnoty všech parametrů
nabývají nulové hodnoty. V tom případě dopočítávané proměnné nabývají aktuální hodnoty
příslušné pravé strany. Takové řešení označujeme termínem bázické řešení soustavy
lineárních rovnic.
x 5 = -5 ... bázická proměnná na třetím řádku, je rovna třetí složce vektoru pravých stran
Naopak u nebázického řešení je tato podmínka porušena. Stačí, abychom jakékoliv nebázické
proměnné přiřadili hodnotu různou od nuly a již se jedná o řešení nebázické.
Z výše uvedeného příkladu bázické řešení snadno odvodíme. Proměnné v něm nabývají těchto
hodnot:
x, = O ... parametr, v bázickém řešení pokládáme roven nule
x2
= O ... parametr, v bázickém řešení pokládáme roven nule
XJ
=
x4
= -4 ... bázická proměnná na druhém řádku, je rovna druhé složce vektoru pravých stran
1O ... bázická proměnná na prvním řádku, je rovna první složce vektoru pravých stran
x 2 ""' O ... parametr, v bázíckém
řešení
pokládáme roven nule
x 3 = 2 ... bázická proměnná na prvním řádku, je rovna prvni složce vektoru pravých stran
x 4 = O ... parametr, v bázickém řešení pokládáme roven nule
neboli x8 = ( 4, O, 2, O, -5), případně
x4
-5+x2
Z bázického řešení, které je zapsané ve formě vektoru obecného řešení, lze snadno odvodit
řešení nebázické. Stačí dosadit zvolené hodnoty parametrů do soustavy rovnic, převést
s opačným znaménkem na pravou stranu, ze které lze potom snadno odečíst hodnoty
bázických proměnných.
x 5 = -5 ... bázická proměnná na třetím řádku, je rovna třetí složce vektoru pravých stran
12
l3
Položme hodnoty parametrů xz = 2 a X4 = -1. Po dosazení do soustavy rovnic dostaneme
X1
= 4 + X4 = 4- 1 =
X3
=2 -
X5 ""
-5
3,
xz - 2x4 = 2 - 2 + 2
+X
3
2
="'
2,
5
A::: O 2
[
-1 1
z= -5 + 2 = -3,
což múžeme zapsat do vektoru bázického řešení x 8
1.2.
Příklad
= (3, 2, 2, -1, -3).
Příklady k procvičení
3]~ ,o~ [-2~3 ~3] c~(~
~z ~J
,
Pokud je to možné, určete matici D jako
a)D = A.B
b)D=B.C
Příklad
1
a ..- (5, 7, 2, 3), b = (-1, -5, 4, 6), c = (2, -7, -4, 3), d = (1, 4, 3, O)
Určete vektore jako
a) e = a+ b- c
c)D=C.B
d) D = (C.A).B
e)D=A- 1
f) D = (B.C)" 1
b)e ~ b+d-a+c
c)e - 5a-2b
d) e = 3b + 2c - 4a
Příklad
e) lineární kombinaci vektorů ba d s koeficienty / 1 = 3 a / 2 = -2
f) lineární kombinaci vektorů ca d s koeficienty 11 = -5 ah= 4
g) lineární konvexní kombinaci vektorů a a c s koeficientem /1 = 0,7 (/z dopočítejte)
h) lineární konvexní kombinaci vektorů bac s koeficienty /1 = 0,4 (/2 dopočítejte)
A=
4
1
o
-2
2
o
2
2
o
- 1
o
1
-1
o
1
-2
o
Pokud je to možné,
,o~[~
určete
-3 -1
2
o
5
6
~} c~
-2
o
1
2
5 -1
o
1
5
2
o o
-6
matici D jako
a) D = A.C
Příklad
2
a= (5, 7, 2, 3), b = (-1, -5, 4, 6), c = (2, -7, -4, 3), d = (1, 4, 3, O)
Určete hodnotu u jako skalární součin vektorů
b) D = B.C
c)D=C.B
d) D = (A.C).B
a) u - a.b
e)D=K 1
b) u = b.c
f) D = (C.B)" 1
c) u = c.d
g) D =A· 1.C
d) u ="' a.c
e) u = a.d
f) u = b.d
Příklad
5
Pomocí Jordanovy eliminační metody řešte soustavu lineárních rovnic
a) Sx1 + 2x2 = 2
2x, + xz = 1
14
15
Příklad
b)-3x,+x2=-2
+ 3x2 = 6
x,
6
Je dána soustava lineámích rovnic
X1+2x2+X3-X4+2x5 ""
c)2x,-3x2 = 10
6x,- 4x2-
~ 4
5
2XJ - 2x2 -1- X] - X4- 2x5 =
x, + 3x2 + 2x3 ""
2
a) Pomocí Jordanovy eliminační metody převeďte úlohu do kanonického tvaru s bazickými
proměnnými x3, x 4 a x 5.
d) 3x, + x 2 + 3x3 =-2
X2 + X3 ~
10
b) Určete vektor bazického řešení a vektor obecného řešení dané soustavy rovnic
3
c) Nahraďte v bázi proměnnoux3 proměnnoux2 • Určete vektor bazického řešení.
3
Příklad
7
Je dána soustava lineárních rovnic
4x1 + x 1 + 2'C3 =
3
XJ
+ 2x2 + X3- X4 + 2x5 =4
5x, + 4x2- X3 + x 4 + 4x5 = 2
f)
x, - x2
+ 3x3 = 7
2x1 - 2x2
x, +5x2 - x 3 "'" -4
3x, + 9x2 + XJ
+ X3 + 2x4 + X5 :o: 5
a) Pomocí Jordanovy eliminační metody převeďte úlohu do kanonického tvaru s bazickými
proměnnými x 1, x 2 a x 3 .
=5
b) Určete vektor bazického řešení a vektor obecného řešení dané soustavy rovnic
x, -
g)
x2
+ 2x3 + 4x4 = 4
c) Nahraďte v bázi proměnnoux3 proměnnoux5 . Určete vektor bazického řešení.
2x, + 2x2 - 2x3 + X4 - 2
Xt
+ X2 - XJ - X4 = 1
- X2
Příklad
+ 2X3 + X4 = 2
Je dána soustava lineárních rovnic
XJ
h) x, + 3x2 + 2x3 + 2x4 = 8
lx1 -X]+ XJ
+ X4 = 1
x,+x2-x3 +4x4=5
3xl - x 2 + 2x3 + X4 =
8
+ 2x2 - X3 + 2x4 + X5 - X6 = 8
-2xl +X]
XI
+ 2x3 + X4 + 2x5 -
=6
+ 2x2 +X] - 2x4 + X5 + X6 = 2
X!+ X2- 2x3- X4
5
2x6
+ X5-
2x6 =
3
a) Pomocí Jordanovy eliminační metody převeďte úlohu do kanonického tvaru s bazickými
x 4, x 5 a x 6•
proměnnými x 3 ,
i)
lx,
Sx2 - XJ + 3x4 = 4
b) Určete vektor bazického řešení a vektor obecného řešení dané soustavy rovnic
+ Sx3- 2x4 = 1
c) N ahraďte v bázi proměnnou x4 proměnnou x 1. Určete vektor bazického řešení.
x,
+ 2x2 + 6x3 + 2x4 = -2
Xt
+X2 +XJ- X4 = -1
16
d) Nahraďte v bázi proměnnou x5 proměnnou x,. Určete vektor bazického řešení.
17
Řešení příkladů
1.3.
Příklad
Příklad
4
- 2 -9
1
a) D=
a) e = (2, 9, 1O, 6)
b) e -== ( -3, -15, 1, 6)
c) e "" (27, 45, 2, 3)
12
8
4
1
-5
4
-6
12
b)
o=
e) e = (-5, -23, 6, 18)
10
(
31
f) e = (-6, 51, 32, -15)
~
4
(4,1; 2,8; 0,2; 3)
h) e =-- (0,8; -6,2; -0,8; 4,2)
Příklad
c) D=
2
a) u = -14
b) u - 35
56
o
12
72
18
-25
-37
22
-6
77
77
-53
3
2
-2
-1
2
1,5
2
3
1
O, 5
1
1
e) u "" 39
3
(~1 3
8
a) O =
:]
g) D=
=
(-~0 ~20 ~OJ
-15
c) D =
2
4
-2 -3
f) D = nelze
1
-18 -1
b) D
-3
7
d) u = -38
e) D=
12
-40 -82 -82
d) D =
f) u = -9
12
6 -17 -5 29
22 17
ll
7
o -30 -36 12
c) u = -38
Příklad
1
-16
d) e - (-19, -57,-4, 12)
g) e
-14
-6
Příklad
(-8 19]
12
ll
-14
-7
-11
10
9,5 10,5 -10
3,5 5,5
-2
5
a) x 1 =O ;xz= 1
-5 -4
b)
XI=
1,2; Xz = 1,6
c) x 1 =-2,5 ;xz=-5
d)
D = (-66
8
88)
-9
2
e) D = (-:
-2
f) D = nelze
18
~1 7 ~~]
7
-4
d)
XJ
=
-3,4; Xz = 0,4; Xj = 2,6
e)
XJ
=
0; Xz = -1 ; X3 = 2
f) nemá řešení
g)
Xj
= 2; Xz = 0; Xj = 1 ; X4 = 0
h) x,=l5;x2 =10,2;x3=-11;x4 =-7,8
i) nemá řešení
19
Příklad
6
Příklad
a)
7
a)
x1
1
o
2
x2
2
4
-2
x3
1
-1
1
x4
-1
x5
b
o
10
o
2
-1
-2
2
6
1
-1
1
1
1
o
2
-2
2
2
10
14
1
-8
4
-1
-4
o
o
o
-4
-4
1
o
o
-4
1
o
-2
-4
-14
-8
o
o
o
-4
-10
1
2
-1
1
-6
-4
o
o
o
-4
-4
1
o
o
-1,5
-0,25
x2
2
2
x1
1
5
1
1
o
x3
1
-1
1
x4
-1
1
2
2
1
-1
6
4
2
4
-6
-18
-3
-3
4
x5
2
4
1
I
b
4
2
5
o
o
-6
-6
-6
-1
1
o
-1
1
o
-2
1
1
5
-1
-2
1
3
3
15
o
o
o
0,6
-0,6
-0,4
0,6
0,4
0,6
o
o
o
o
1
o
o
1
o
1
1
3
b)
= (0, O, -4, -10, 2),
x8
b)
XI
= (1, o, 3, O, 0),
XB
x2
Xo
1-0,6x4
= -4+4x2
-
0,6x5
O+ 0,6x4 -0,4x5
-10 + 1,5x1 +4x2
Xo
2+0,25x1 -x2
=
3 + 0,4x4 -0,6x5
x4
c)
Xs
x1
x2
x3
x4
x5
b
o
1
-0,25
-1
1
o
o
1
o
o
o
-6
1
1
-1,5
-0,25
0,25
x 8 = (0, 1, O, -6, 1)
o
c)
x1
x2
1
o
o
o
1
o
x3
-1
x5
1
-0,67 -0,33
o
o
1,667 -0,67
1
xn = (-2, -2, O, O, 5)
20
x4
b
-2
-2
5
I
Příklad
8
2.
a)
x1
1
x2
2
1
2
1
-2
1
1
-1
x3
-1
2
1
-2
x4
2
1
-2
x5
1
2
1
x6
-1
-2
-1
1
-2
1
-2
5
-1
1
-8
4
-4
22
2
o
-2
5
2
-1
-3
o
o
o
-1
o
1
4
o
1
2
4
2
-1
2
3
-5
-1
o
o
-13
o
0,6
0,8
-0,6
-0,8
0,8
4,4
10
2
o
o
3
-4
9
o
o
o
-0,6
-0,8
-1,2
1
-0,6
1
2
-4
-4
o
o
o
-1
-0,6
1
0,2
o
o
o
2
1
6
o
-1,6
1
1
b
8
o
o
o
-0,8
o
o
1
1
1
o
o
o
1
o
o
10
o
o
-2,2
0,4
5
-4
-6
o
o
o
-1,3
o
o
1,6
5
1
1,5
1
1
o
Sestavení modelu lineárního programování
Některé učebnice lineárního programování oblast sestavení modelu LP na základě
slovního zadání přechází s poznámkou, že neexistuje univerzální návod, jak tuto
transformaci uskutečnit. To je pravda stejně jako fakt, že modelování, resp. systémové
modelování (definice systému na reálném objektu a následná konstrukce modelu na
základě definovaného systému) patří spt'še do oblasti systémových disciplín.
Na druhou stranu je nutno poznamenat, že drtivá většina školníc/1 úloh je již
formulována jako s/ov1zí model reálného objektu a úkolem studenta je pouze jeho
transformace do matematické a/nebo grafické podoby. Cílem této kapitoly je předat čtenáři
alespoň některé základni "tipy a triky", s jejichž pomocí výše uvedenou transformaci
zvládne.
Obvykle existuje více správných způsobů, jak model sestavit. Proto předtím, než
případně začnete hledat chyby ve svém postupu, doporučujeme zkontrolovat, zda se vaše
řešení neliší od vzorové/to pouze v řádech nebo použitých měrných jednotkách.
2. 1.
Řešené příklady
Příklad
1 -Výroba salámů
Výrobce salámů se každý den ráno rozhoduje, kolik z připravené masové hmoty má zpracovat
na salámy. Masová hmota se dodává ve vaničkách o kapacitě 20 kg. Vyrábí se tři druhy
salámů:
1. salám Standard, na jeden kus se spotřebuje 0,5 kg masové hmoty. Denně se prodá vždy
b)
alespoň
XB
=(O; O; -1,3; 1,6; 5; 1,5)
2. salám Exclusive, na jeden kus se spotřebuje 1 kg masové hmoty. Denně se prodá vždy
alespoň 30 ks.
x2
3. salám Exclusive XXL, na jeden kus se spotřebuje 2,5 kg masové hmoty. Denně prodá vždy
1O ks.
-1,3+x1 +0,6x2
alespoň
1, 6- 0,2x2
Z technologických důvodů je možno hmotu obsaženou v jedné vaničce použít:
5 - x 1 -2x2
• z jedné čtvrtiny na výrobu salámu Standard, další čtvrtinu na salám Exclusive a zbytek na
salám Exclusive XXL. Při tomto technologickém postupu jsou náklady na zpracování
jedné vaničky 500 Kč.
1,5 - x1 -x2
c) nelze, na místě klíčového prvku nesmí být nula
d)
x1
x2
x3
x4
x5
o
x6
1.4
1
o
1
o
b
3,7
1
1,6
5
-3,5
o
0,2
1
2
-1
o
100 ks.
o
o
o
1
o
o
o
1
-1
o
o
• ze dvou pětin na salám Standard a ze tří pětin na salám Exclusive. Při tomto
technologickém postupu jsou náklady na zpracování jedné vaničky 400 Kč.
• z poloviny na salám Exclusive a z poloviny na salám Exclusive XXL. Při tomto
technologickém postupu jsou náklady na zpracování jedné nádoby 250 Kč.
Kolik vaniček s masovou hmotou a jak má výrobce použít na denní produkci, jestliže chce
minimalizovat své náklady?
x 8 = (5; O; 3,7; 1,6; O; -3,5)
22
23
Řešení
Tuto úlohu jsme záměrně zařadili hned na začátek našeho výkladu. Nastává zde typická
situace, kdy není na první pohled jasné, jak definovat proměnné. Mají to být jednotlivé druhy
salámů? Nebo technologické postupy zpracování vaniček s masovou hmotou?
Pokud si nejste jistyak definovat proměnné, podívejte se, jak je formulovaná otázka
v účelové funkci. Učelová funkce obsahuje cíl rozhodování, tj. odkazy na objekty,
které by měly vystupovat jako proměnné.
• ze dvou pětin na salám Standard a ze tří pětin na salám Exclusive. Při tomto
technologickém postupu jsou náklady na zpracování jedné vaničky 400 Kč.
• z poloviny na salám Exclusive a z poloviny na salám Exclusive XXL.
technologickém postupu jsou náklady na zpracování jedné nádoby 250
... počet
x2
..•
x3
... počet
počet
Byly identifikovány tři omezující podmínky. Pro každou je nutno určit levou a pravou stranu
a typ omezení.
• typ omezení je,;~", vyplývá z klíčového slova "alespoň",
Jakmile definujete novou proměnnou, ihned také stanovte jednotky, ve kterých ji
budete nadále vyjadřovat. Toto opatření vám umožní udržet konzistenci modelu a
pomůže formulovat omezující podmínky, případně ověřit správnost jejich sestavení.
Jsou-li definovány proměnné, lze formulovat omezující podmínky. Je nutné projít text úlohy a
analyzovat jednotlivé věty, odstavce a odrážky, zda obsahují nějaké omezující ustanovení.
Když prohledáváte text za účelem sestavení omezujících podmínek, hledejte zejména
kvantifikátory "alespoň", "nejvýše", "právě", "nejméně", "ne více než",
"maximálne', případně výrazy typu "je k dispozici", "je potřeba'' a další, ne/ze je
uvést vyčerpávajícím výčtem.
• jednotky jsou "kusy salámu" (ks).
Abychom sestavili levou stranu omezující podmínky, musíme si uvědomit, jaké jsou možnosti
získání masové hmoty pro výrobu salámu Standard. Buď je zpracována jedna vanička
technologickým postupem 1, nebo je zpracována jedna vanička technologickým postupem 2.
Jiná možnost není, technologický postup 3 dodává masovou hmotu pouze pro výrobu salámu
Exclusive nebo Exclusive XXL.
Pokud zpracujeme jednu nádobu technologickým postupem 1, tato nádoba obsahuje 20 kg
1
masové hmoty. Z toho jde / 4 tj. 5 kg na salám Standard. Protože je na jeden kus tohoto
salámu potřeba 0,5 kg, z 5 kg získáme 10 ks salámu.
Obdobně, pokud zpracujeme jednu nádobu technologickým postupem 2, tato nádoba obsahuje
Projdeme text zadání naší úlohy:
"Výrobce salámů se každý den ráno rozhoduje, kolik z
zpracovat na salámy." Zde není žádná podstatná informace.
"Masová hmota se dodává ve vaničkách o
Parametr vaničky, ale žádné omezení.
kapacitě
připravené
20 kg. Vyrábí se
masové hmoty má
tři
druhy
salámů."
"1. salám Standard, na jeden kus se spotřebuje 0,5 kg masové hmoty." Parametr výrobního
postupu, ale žádné omezení.
Omezení, nutno sestavit omezující podmínku OPI.
"2. salám Exclusive, na jeden kus se spotřebuje 1 kg masové hmoty. Denně se prodá vždy
alespoň 30 ks." Parametr a omezení, omezující podmínka OP2.
"3. salám Exclusive XXL, na jeden kus se spotřebuje 2,5 kg masové hmoty.
vždy alespoň 1Oks." Parametr a omezení, omezující podmínka OP3.
Denně
prodá
Z technologických důvodů je možno hmotu obsaženou v jedné vaničce použít:
• z jedné čtvrtiny na výrobu salámu Standard, další čtvrtinu na salám Exclusive a zbytek na
salám Exclusive XXL. Při tomto technologickém postupu jsou náklady na zpracování
jedné vaničky 500 Kč.
24
také omezující podmínky mají svoje jednotky. Pokud levá a
pravá strana po~mí~ky vychází v různých jednotkách, omezující podmínka je určitě
sestavena nespravne.
• její pravou stranu, je rovna 100,
(vaniček)
nádob masové hmoty zpracovaných technologickým postupem 3 (vaniček)
"Denně se prodá vždy alespoň 100 ks."
Stejně jako proměnné
Sestavíme nyní omezující podmínku OPl. Již ze zadání známe:
nádob masové hmoty zpracovaných technologickým postupem 1 (vaniček)
nádob masové hmoty zpracovaných technologickým postupem 2
tomto
Pouze parametry, žádné další omezující podmínky.
V našem příkladu je cílem minimalizace nákladů výrobce. Je tedy nutno zjistit, co se musí
stát, aby nějaké náklady vznikly. Náklady vznikají každým zpracováním vaničky s masovou
hmotou, a to ve výši 500 Kč technologickým postupem 1, ve výši 400 Kč technologickým
postupem 2 a 250 Kč technologickým postupem 3. Z toho je zřejmá definice proměnných:
x1
Při
Kč."
20 kg masové hmoty. Z toho jdou 215 tj. 8 kg na salám Standard. Protože je na jeden kus
tohoto salámu potřeba 0,5 kg, z 1Okg získáme 16 ks salámu.
Celkové množství masové hmoty pro salám Standard získáme tedy jako součet počtu nádob
zpracovaných technologickým postupem 1 krát jejich výtěžnost (1 O ks/1 nádobu) a počtu
nádob zpracovaných technologickým postupem 2 krát jejich výtěžnost (20 ks/I nádobu).
Omezující podmínka OPI bude mít tento tvar:
IOx1 + 16x2;;::; 100 (ks)
Správnost sestavení této podmínky můžeme ověřit testem na shodu jednotek její levé a pravé
strany:
L:[
~v ].[vaniček]+[ vamcek
~v ].[vaniček]~[ks]
vamcek
P:[ts-]
L=P
Obdobným způsobem sestavíme omezující podmínky OP2 a OP3. OP2 se vztahuje k salámu
Exclusive (získává se pomocí všech tří technologických postupů), OP3 k salámu Exclusive
XXL (získává se pomocí prvního a třetího technologického postupu).
25
OP2: 5x, + 12x2 + lOx3;:::; 30 (ks)
+ 4x3 ;:::; 1O (ks)
OP3: 4x 1
Po sestavení omezujících podmínek zbývá formulovat účelovou funkci. Tento krok nebývá
příliš obtížný. V našem příkladu chceme minimalizovat celkové náklady, jejichž zdrojem jsou
zpracované vaničky s masovou hmotou. Účelovou funkci zapíšeme snadno jako
Sestavíme první omezující podmínku pro kapacitu řezačky. Ze zadání vyplývá, že pokud by
se vyráběly pouze polotovary stolů, bylo by možné zpracovat 1O ks za směnu. Proto
zpracování jednoho polotovaru stolu zabere 1/ 10 směny. Obdobně zpracování jednoho
1
polotovaru skříňky zabere /s směny. Omezující podmínku už potom sestavíme snadno,
budeme ji vyjadřovat ve směnách. K dispozici máme jednu směnu, proto na pravé straně této
podmínky bude hodnota "1 ".
;:::: 100 (ks)
Levá strana této podmínky bude udávat čerpání této směny. Část směny se čerpá zpracováním
libovolného polotovaru; koeficient čerpání byl vypočten výše. Omezující podmínka pro
řezačku má proto tvar
1ho x1 + 1/s Xz ~ 1 (směn)
Sx, + 12x2 + lOx3
;:::; 30
(ks)
Test na jednotky potvrzuje správnost sestavení této podmínky:
+ 4x3
;:::: 10
(ks)
z= 500x, + 400x2 + 250x3 - MIN
(Kč)
Pokud nezapomeneme na podmínky nezápornosti, celý model vypadá takto:
lOx, + 16x2
4x,
z= 500x 1 + 400x2 + 250x3- MIN
XJ,2,3 ~
L
(Kč)
=[ s::n }[ks]+[ s::n }[ks]= [směn]
P :[směn]
0
L=P
Příklad
Když potřebujete sestavit omezující podminku pro rozvržení jedné směny jednoho
stroje, vypočtete si nejprve, jakou část směny zabere výroba jednoho výrobku
každého typu. Tuto miru čerpání potom vynásobte neznámým počtem
rozvrhovaných výrobků; součet celkového čerpání směny za všechny výrobky
nesmi překročit jednu směnu.
2 - Rozvrhování výroby
Dřevozpracující
dílna vyrábí polotovary pro výrobu stolů a skříněk. K tomu používá stroj pro
řezání dílců, stroj pro hmbou přípravu a stroj pro finální úpravu polotovaru. Oba polotovary
musí projít zpracováním na všech strojích. Počet kusů obou polotovarů, který lze zpracovat na
jednotlivých strojích za jednu směnu je v tabulce:
Obdobně sestavíme omezující podmínky pro stroj pro hrubou přípravu a finální úpravu
polotovarů:
Počet
výrobků
za
směnu na
stroji
1
Skříněk
řezačka
10
5
1
/6
hrubá příprava
3
6
Model obsahuje ještě požadavek dosáhnout alespoň 8 000 Kč tržeb za směnu:
finální úprava
6
4
4 000 XJ + 2 000 X2;:::; 8 000 (Kč)
4000
2 000
450
200
Tržby (v
Kč/kus)
Zisk (v Kč/kus)
Je třeba dosáhnout alespoň 8 000
s maximálním ziskem.
Kč
tržeb za
směnu.
z= 450 x, + 200 X2
Navrhněte
výrobní program
ho X1 + /s x2 ~ 1 (směn)
1
/3 x1
Nejprve definujeme proměnné. Definice proměnných je zde jednoduchá a
x2
26
~MAX (Kč)
Po přidání podmínek nezápornosti proměnných celý model vypadá takto:
1
V tomto typu úlohy dělá největší problém sestavení omezujících podmínek pro kapacitu
strojů. Ta není vyjádřena přímo (např. počtem pracovních hodin strojů), ale počtem
jednotlivých výrobků, který by bylo možno zpracovat za jednu směnu v případě, že by celá
kapacita směny byla věnována právě tomuto výrobku.
počet polotovarů stolů
x, + 1/4 x2 ~ 1 (směn)
Účelovou funkci pro maximalizaci zisku sestavíme jako
Řešení
x 1 ...
1
/3 x, + /6 x2 ~ I (směn)
Stolů
Polotovar
1
+ 1/6 x2 ~ 1 (směn)
1
/6x1+ /4x2~ 1 (směn)
1
4 000 XJ + 2 000 X2 ;:::; 8 000
(Kč)
z= 450 x, + 200 X]~ MAX (Kč)
zřejmá:
(ks)
••• počet polotovarů skříněk
(ks)
27
2. 2.
Příklady
k
procvičení
Příklad
Sestavte model lineárního programování následujících problémů.
Příklad
1
Malá firma vyrábí náhrdelníky a prsteny. Za jeden den dokáže vyrobit celkem nejvýše 24 ks
klenotů. Každý náhrdelník se vyrábí jednu hodinu, prsten ptll hodiny. Celkem má firma
k dispozici 16 hodin denně a chce vyrobit každý den nejméně 1O náhrdelníků. Průměrná cena
náhrdelníku je I 500 Kč, prstenu 2 000 Kč. Kolik kusů jednotlivých klenotů by měla firma
vyrobit, aby maximalizovala svoje denní tržby?
Příklad
2
Firma produkuje tři typy kalkulaček: standardní, vědecké a programovatelné. Výrobní
požadavky jsou v tabulce·
Standardní
Vědecká
Programovatelná
5
7
10
Čas výroby (hod)
1
3
4
Pouzdra (ks)
1
1
1
Počet součástek
(ks)
Firma má měsíčně k dispozici 90 000 ks součástek, 30 000 pracovních hodin a 9 000 pouzder.
Cena standardní kalkulačky je 60 Kč, vědecké 150 Kč a programovatelné 350 Kč. Určete
měsíční výrobní program, který maximalizuje příjmy firmy.
Příklad
3
Zemědělský podnik má vyhrazeno na pěstování krmných obilovin nejvýše 200 ha. Rozhoduje
se o osevních výměrách pro pšenici, ječmen a žito. Celkově je nutno vyprodukovat minimálně
4 800 kg krmiva, přičemž výměra pšenice nesmí přesáhnout 120 ha. Plánovaná produkce a
v'
' na
'kl adty na 1 ha Je
. d not rtvých o b.l
. jsou v tab ulce:
pnme
1 ovm
4
Balírny čaje plánují v následujícím období výrobu dvou čajových směsí - lesní směs a ovocný
čaj. Pro výrobu obou směsí mají k dispozici od dodavatelů nejvýše 4000 kg drcených šípků,
600 kg květu ibišku, 350 kg černého rybízu a 200 kg ostružin. Složení obou čajů je uvedeno
v následující tabulce:
Složka
Lesní
směs
(kg I 1000 balenD._ Ovocný
35
ibišku
7
4
Černý rybíz
2
1
Ostružiny
1
o
Květ
Zisk z prodeje jednoho balení lesní směsi je 2 Kč, ovocného
program, který maximalizuje zisk z prodeje balení.
Příklad
1
Kč. Nalezněte
výrobní
V dílně jsou vyráběny tři typy obalů:
• jednoduché lisované obaly,
• ozdobně lisované obaly a
• potištěné ozdobně lisované obaly.
Obaly jsou nejprve lisovány) pak mohou být movu ozdobně lisovány a případně mohou být
ještě potištěny. Výroba je omezena kapacitou lisovacích zařízení a zařízení na potisk.
Kapacita základního lisu je 400 obalů denně, kapacita ozdobného lisování je 250 obalů a
denně je možno potisknout nejvýše 200 obalu.
Náklady na lisování obalů jsou 24)50
náklady na potisk jsou 4 Kč/ks.
Kč/ks,
na ozdobné lisování je to 6 Kč/ks u obou
typů
a
Prodejní ceny jsou následující:
Žito
• obal jednoduchý lisovaný 33)50 Kč/ks)
Produkce kg/ha
260
250
280
• obal lisovaný ozdobný 37 Kč/ks a
Přímé
1600
2600
1800
• obal potištěný ozdobně lisovaný 49,50 Kč/ks.
Jaký je optimální plán na využití půdy, který při splnění uvedených podmínek minimalizuje
přímé náklady?
čaje
5
Ječmen
Kč/ha
(kg I 1000 balení)
30
Drcený šípek
Pšenice
náklady
čaj
Kolik jednotlivých typů obalů má být vyráběno, aby bylo dosaženo maximálního zisku?
Příklad
6
Zemědělský podnik chce na ploše o rozloze maximálně 10 ha pěstovat pšenici a ječmen.
Žádná z obou plodin nesmí být pěstována na méně než 3 ha. Na jaké výměře mají být
jednotlivé obiloviny pěstovány, pokud chce podnik maximalizovat zisk) který je na jeden ha
pšenice 6000 Kč a najeden ha ječmene 4500 Kč?
28
29
Příklad
Příklad
Firma vyrábí a prodává bramborové lupínky za 120 Kč/kg a hranolky za 76 Kč/kg. Na výrobu
1 kg lupínků se spotřebttií 2 kg brambor a 0,4 kg oleje. Na výrobu 1 kg hranolek je zapotřebí
1,5 kg brambor a 0,2 kg oleje. Firma má nakoupeno 100 kg brambor a 16 kg oleje. Brambory
stály 12 Kč/kg a olej 40 Kč/kg. Nalezněte takový plán výroby, při kterém firma dosáhne
maximálního zisku.
Příklad
8
Investor se rozhoduje o rozložení investice mezi akcie, podílové fondy (PF), termínované
vklady (TV) a hypoteční zástavní listy (HZL). Likviditu jednotlivých nástrojů si ohodnotil
bodově (akcie 5 b., PF 4 b., TV 1 b. a HZL 3 b.). Požaduje, aby celková likvidita portfolia
dosáhla nejméně 30 000 000 b. Výnosy nástrojů ohodnotil roční úrokovou mírou (akcie 6%,
PF 4%, TV 1% a HZL 5%) a požaduje dosažení výnosu nejméně 3% p.a. Investuje celkem
právě 1O 000 000 Kč.
Investor dále ohodnotil riziko plynoucí z držby jednotlivých aktiv 1 O, 8, 3 resp. 4 body.
Jak má investor rozložit investici, aby za daných podmínek minimalizoval riziko?
Příklad
9
Strojírenský podnik potřebuje pro svou výrobu kovové tyče různých délek: alespoň 600 tyčí o
délce 90 cm, 600 tyčí o délce 70 cm, 200 tyčí o délce 50 cm a 400 tyčí o délce 35 cm. Tyče se
rezou ze standardmc
' h po 1otovaru• o de'1 ce 200 c m. Lze použít následující čtyři řezné plány:
Řezný plán
Typy tyčí
č.1
č.2
č.3
č.4
tyč
90 cm (ks)
1
-
1
-
tyč
70 cm (ks)
1
1
2
tyč
50 cm (ks)
-
1
-
tyč
35 cm (ks)
1
2
3
-
5
10
5
10
Odpad (cm)
1
Kolik tyčí je nutno rozřezat a jak, aby byly naplněny minimální požadavky na počet tyčí
jednotlivých délek a zároveň byl minimalizován odpad?
Příklad
10
Textilní firma vyrábí tři typy triček ve dvou různých provozech v Mostě a Klatovech.
V Mostě lze denně ušít maximálně 100 luxusních triček, 200 standardních triček a 130
levných triček, v Klatovech se dá denně ušít 200 luxusních triček, 500 standardních triček a
60 levných triček. Firma má objednávku na minimálně 20 000 ks luxusních, 42 000 ks
standardních a 12 000 ks levných triček. Denní náklady provozu v Mostě činí 5 000 Kč a
v Klatovech 8 000 Kč. Kolik dní výroby si má firma "objednat" ve svých jednotlivých
provozech, aby objednávku splnila s minimálními náklady?
30
ll
7
Farmaceutická firma
vitamíny Ba c ac ukr
připravuje
na trh nový vitamínový přípravek, který má obsahovat
' h'a ze dvou smes1, JeJICh s 1ozem Je v t abu1ce:
n pravek se m1c
p~'
v
'
•
••
Směsi
Složky přípravku
směs "soft"
(balíček
směs
'
•
Požadované minimální
množství složky
v přípravku (g)
"bard"
17 g)
(balíček
14 g)
v
vitamín B (g/balíček)
2
5
40
vitamín C (g/balíček)
o
7
28
cukr (g/balíček)
12
5
65
Cena směsi
2
6
---
(Kč/balíček)
Jakým způsobem přípravek namíchat, aby obsahoval dostatek každé složky a
výroba byla co nejlevnější?
Příklad
přitom
jeho
12
Betonárka vyrábí dva druhy betonových směsí: kameninu zpevněnou cementem KSCl a
výplňový beton B5. Na výrobu každé směsi jsou potřeba tři základní suroviny: cement,
kamenivo a voda. Zatímco voda je pro betonárku neomezený zdroj, cementu je možno pro
denní produkci využít nejvýše 80 ta kameniva 50 t. Další suroviny a zdroje jsou k dispozici v
neomezeném množství. Na jeden kubík směsi KSC1 se spotřebuje 0,2 t cementu a 0,5 t
kameniva, na jeden kubík směsi B5 se spotřebuje 0,4 t cementu a 0,3 t kameniva. Určete
výrobní program maximalizující zisk betonárky v případě, že zisk z jednoho kubíku KSC1 je
300 Kč a z jednoho kubíku směsi BS 400 Kč.
Příklad
13
Farma potřebuje nejméně 800 kg speciální stravy pro
strava je směsí kukuřice a sojových bobů se složkami:
hospodářská zvířata denně.
Speciální
proteiny (kg/kg) vláknina (kg/kg) náklady (Kč/kg)
kukuřice
0,08
0,06
3,-
sojové boby
0,60
0,03
9,-
Denní dávka má obsahovat
aspoň
30%
proteinů
a nejvýše 5% vlákniny a má být co
nejlevnější.
Příklad
14
Firma vyrábí hnědý, bílý a moučkový cukr. Na týden má k dispozici 4200 t cukrové třtiny.
Jedna tuna hnědého cukru se vyrobí ze tří tun třtiny. Bílý cukr se vyrábí z hnědého, a to jedna
tuna z 1,25 ta moučkový cukr se vyrábí z bílého, a to jedna tuna z 1,05 t bílého. Jednotkový
zisk je 1500 Kč z tuny hnědého cukru, 2000 Kč z tuny bílého cukru a 2300 Kč z tuny
moučkového cukru.
Maximalizujte zisk z prodeje.
31
Příklad
Příklad
15
V dílně se vyrábějí 4 druhy výrobků- stoly, židle, psací stoly a knihovny. Majitel dílny chce
určit, kolik výrobků z každého druhu musí vyrobit, aby optimálně využit zdroje, kterými
disponuje. Na zhotovení uvedených předmětů se používají dva typy desek. Podnikatel má na
2
skladě 1500 m desek prvního a 1000 m 2 desek druhého typu. Má k dispozici 800 pracovních
hodin. Na výrobu každého stolu, židle, psacího stolu a knihovny je potřeba 5, 1, 9 a 12 m 2
2
desek prvního typu a 2, 3, 4 a 1 m desek druhého typu a 3, 2, 5 a 10 pracovních hodin. Zisk
je vykalkulován na 1200 Kč za stůl, 500 Kč za židli, 1500 Kč za psací stůl a 1000 Kč za
knihovnu. Při zachování uvedených podmínek je potřeba určit takový výrobní plán, aby se
dosáhl maximální zisk.
Příklad
16
Firma balící bonboniéry má k dispozici 60 čokoládových, 60 oříškových a 85 karamelových
bonbónů. Může vyrábět dva druhy bonboniér. Bonboniéra "Karamélie" se skládá ze dvou
čokoládových, šesti oříškových a deseti karamelových bonbónťt, do bonboniéry "Čokoládové
potěšení" se dává deset čokoládových, šest oříškových a pět karamelových. Firma má
vykalkulováno, že na každém kusu bonboniéry "Karamélie" vydělá 30 Kč a kusu bonboniéry
"Čokoládové potěšení" 45 Kč. Jaký je optimální výrobní program firmy, pokud chce
maximalizovat zisk?
Příklad
17
19
Firma vyrábí dva druhy nátěrových hmot (barev) pro interiéry a exteriéry z vodné disperze
epoxidové pryskyřice obsahující aditiva, pigmenty a plniva (složka A) a polyamidového
tvrdidla (složka B). Mísící poměry pro jednotlivé nátěrové hmoty jsou v tabulce:
barva pro exteriéry barva_QTO interi~
složka A (díly)
100
100
složka B (díly)
26
14
5000
4000
zisk (Kč/t)
Denně je k dispozici maximálně 20 t složky A a 14 t složky B. Minimální denní požadavek na
množství barvy pro interiér jsou dvě tuny, navíc toto množství nemá překročit množství barvy
pro exteriér o více jak jednu tunu. Firma chce naplánovat denní výrobu tak, aby byl
maximalizován denní zisk.
Příklad
20
V keramické dílně se vyrábí vázy, misky a talíře. Za jednu směnu je možné vyrobit nejvýše
1O ks váz nebo 16 ks misek nebo 20 ks talířů a malbou ozdobit nejvýše 8 ks váz nebo 1O ks
misek nebo 12 ks talířů. Zisk z prodeje jedné vázy je 500 Kč, z jedné misky 300 Kč a jednoho
talíře 200 Kč. Stanovte výrobní program dílny maximalizující zisk za směnu.
Předpokládejme,
že máme dvě potraviny - chléb a sýr. Obě potraviny obsahují dva výživné
faktory - kalorie a bílkoviny (vyjádřené v gramech). Víme, že jeden kilogram chleba obsahuje
2000 kalorií a 50 gramů bílkovin a jeden kilogram sýra obsahuje 4000 kalorií a 200 gramů
bílkovin. Žádoucí obsah bílkovin ve stravě, kterou máme připravit, činí nejméně 3000 kalorií
a 100 gramů bílkovin. Tržní ceny jsou 20 Kč za kilogram chleba a 60 Kč za kilogram sýra.
Jaké máme zvolit optimální složení potravy, abychom co nejvíce ušetřili?
Příklad
18
Elektrárna má možnost nákupu čtyř různých druhů paliva HULI, HUL2, CULI a CUL2 s
následujícími parametry:
druh
paliva
výhřevnost
[MJ/kg]
obsah vody
[%]
popeloviny
[%]
síra
[%]
[Kč/kg]
HULl
10,0
30
35
4,2
30,5
HUL2
11,7
25
22
4,7
35,0
CULI
11,3
20
17
5,6
32,5
CUL2
14,2
12
9
8,0
43,0
cena
Pro provoz elektrárny je zapotřebí palivová směs o průměrné výhřevnosti v rozmezí 10,5 12,0 MJ/kg. Nejvyšší přípustný obsah vody ve směsi je 24%, popelovin 30% a síry 5,4%.
Určete podíl jednotlivých druhů paliva ve směsi tak, aby celkové náklady na pořízení paliva
byly minimální.
32
33
Řešení příkladů
2.3.
Příklad
x2 ... ovocný čaj (1 000 ks balení)
30x, + 35x2 S 4000 (kg)
X2 ... prsteny (ks)
7xl + 4x2 :5 600 (kg)
x, + x 2 S: 24 (ks)
2x1 + X2 :5 350 (kg)
x1 + O,Sx2 S 16 (hod.)
~
10 (ks)
X 1 :5 200
(kg)
z = 2 OOOx1 + 1 OOOx2 ~ MAX
z = 1 500xr + 2 OOOx2 ~ MAX (Kč)
2
(Kč)
x,, x2 ~O
Příklad
Příklad
4
x 1 ... lesní směs ( 1 000 ks balení)
1
x, . . náhrdelník (ks)
x,
Příklad
5
x 1 .•. obal jednoduchý lisovaný (ks)
x 1 ..• kalkulačka standardní (ks)
x2 ... obal lisovaný ozdobný (ks)
x2 ... kalkulačka vědecká (ks)
x 3 ... obal potištěný ozdobně lisovaný (ks)
XJ ... kalkulačka
programovatelná (ks)
5x, + ?x2 + 1Ox3 S: 90 000 (ks součástek)
x,
+ Jx2 + 4x3 S: 30 000 (prac. hod.)
x, + x2 + X3 S 9 000 (ks pouzder)
z = 60x, + lSOx2 + 350x3 ~ MAX (Kč)
XJ
+ X2 + XJ :5 400 (ks)
X2
+ X3 :5 250 (ks)
X3 :5 200 (ks)
z= 9xl + 6,Sx2 + 15x3
~
XJ, X2,X3
Příklad
Příklad
3
~
MAX (Kč)
0
6
x1 ... výměra pšenice (ha)
x1 ...
výměra
x2 ...
výměra ječmene
pšenice (ha)
(ha)
x2 ...
výměraječmene
(ha)
x, + x2 :5 10 (ha)
x3
.•. výměra
žita (ha)
x1 ~ 3 (ha)
XI
+ X2 + X3 :5 200 (ha)
x2 ~ 3 (ha)
260xl + 250x2 + 280x3 ~ 4 800 (kg)
z= 6x1 + 4,5x2 ~ MAX (tis. Kč)
x 1 S: 120 (ha)
X1, X2 ~
z= 1 600x1 + 2 600x2 + 1 800x3 ~ MIN (Kč)
Příklad
Xj, X2, XJ ~ Ú
x, ... lupínky (kg)
0
7
x2 ... hranolky (kg)
2x1 + l,Sx2.S 100 (kg brambor)
0,4xl + 0,2x2 :5 16 (kg oleje)
z= 80x, + 50x2
XJ, X2 ~
34
~
MAX (Kč)
0
35
Příklad
XI ...
8
objem peněz investovaných do akcií (mil. Kč)
PřUdad
11
x2 ... objem peněz investovaných do podílových fondů (mil. Kč)
x, ... směs "soft" (balíček)
x3 ... objem peněz investovaných do termínovaných vkladů (mil. Kč)
x2 ... směs "bard" (balíček)
X4 ... objem peněz investovaných do hypotečních zástavních listů (mil. Kč)
2x, + Sx2 ~ 40 (g)
Sx, + 4x2 + X3 + 3x4 ~ 30 (mil. bodů)
1x2 ~ 28 (g)
1,06x, + 1,04x2 + I,Olx3 + 1,05x4 ~ 10,03 (mil. Kč)
12x, + Sx2 ~ 65 (g)
x, + x2 + x3 + X4 = 1O (mil.
z= 2xi + 6x2-+ MIN (Kč)
Kč)
z= 1Ox, + 8x2 + 3x3 + 4x4 ~ MIN (mil. bodů)
Příklad
Příklad
12
x 1 ••• směs KSCI (m3)
9
.•.
řezný
plán č. 1 (ks polotovarťl)
x 2 .•. směs BS (m3 )
x2 ...
řezný
plán č. 2 (ks
0,2x 1 + 0,4x2 ~ 80 (t cementu)
X3 ...
řezný
plán
x1
č.
polotovarů)
3 (ks polotovarů)
x4 ... řezný plán č. 4 (ks polotovarů)
0,5xi + 0,3x2 ~50 (t kameniva)
z= 300xi + 400x2 ~MAX
(Kč)
x, + x3 ~ 600 (ks tyčí 90 cm)
x, + X.z + 2x4 ~ 600 (ks tyčí 70 cm)
Příklad
13
x2 + x4 ~ 200 (ks tyčí 50 cm)
x 1 •••
x, + 2x2 + 3x3 ~ 400 (ks
x2 ... sojové boby (kg)
tyčí
z= Sxi + lOx2 + Sx3 + IOx4
35 cm)
~
MIN (cm)
Xt
kukuřice
(kg)
+ X2 ~ 800 (kg)
0,08xi + 0,6x2 ~ 0,3(xi + x2) (kg)
Příklad
10
0,06x1 + 0,03x2 ~ 0,05(xi + x2) (kg)
x 1 ..• výroba v Mostě (dny)
z= 3xi + 9x2 ~ MIN (Kč)
x2 ... výroba v Klatovech (dny)
XJ, X2
IOOx, + 200x2 ~ 20 000 (ks luxusních triček)
Příklad
~
0
14
200xi + SOOx2 ~ 42 000 (ks standardních triček)
x, ... hnědý cukr (t)
l30x, + 60x2 ~ 12 000 (ks levných triček)
x2 ... bílý cukr (t)
z= 5 OOOx, + 8 000x2 ~ MIN (Kč)
x3
.•• moučkový
3xi
-XI
~4
cukr (t)
200 (t)
+ 1,25X2 ~ 0 (t)
-x2 + l,OSx3
~O
(t)
z= 1 500x1 + 2 000x2 + 2 300x3 ~MAX (Kč)
36
37
Příklad
x1
.•.
15
stoly (ks)
Příklad
18
xz ... židle (ks)
x 1 .•• palivo HULI (kg)
x3
x 2 ... palivo HUL2 (kg)
...
psací stoly (ks)
X4 ... knihovny (ks)
x3
5x 1 + xz -l 9x3 + 12x4 S 1 500 (m2 desky prvního typu)
x 4 ... palivo CUL2 (kg)
2t 1 + 3x2 + 4x3 + X4 S 1 000 (m 2 desky druhého typu)
1Ox 1 + ll, 7x2 + ll ,3x3 + 14,2x4;::: 10,5(x, +Xz+ x3 + x4} (MJ)
3x, + 2xz + Sx3 + I Ox4 :S 800 (hod.)
10x1 + 11,7xz + 11,3x3 + 14,2x4 :S 12,0(xJ + Xz + X3 + x4} (MJ)
z - I 200x,
1-
500xz + 1 SOOx3 + 1 OOOx4 ~MAX (Kč)
...palivo
CULI (kg)
0,3x1 + 0,25x2 + 0,2x3 + 0,12x4 :S 0,24(xi + Xz + X3 + x4) (kg)
0,35x1 + 0,22x2 +O, 17x3 + 0,09x4 S 0,3(x, +Xz+ X3 + X4} (kg)
Příklad
16
0,042x 1 + 0,047x2 + O,OS6x3 + 0,08x4 S. 0,054(xJ + Xz + X3 + X4} (kg)
z= 30,5x1 + 35x2 + 32,5x3 + 43x4 ~ MIN (Kč)
x 1 .•. bonboniéra "Karamélie" (ks)
x2
...
bonboniéra ,,Čokoládové potěšení" (ks)
2x, + IOxz .:S 60 (ks čokoládových bonbónů)
Příklad
19
6x, + 6x2 S 60 (ks oříškových bonbónů)
x 1 ..• barva pro exteriéry (t)
1Ox 1 + 5x2 :S 85 (ks karamelových bonbónů)
x 2 ... barva pro interiéry (t)
z= 30x1 + 45x2 ~ MAX (Kč)
100
100
- x1 +-x2 :$; 20 (t slozky A)
Příklad
17
v
126
114
26
14
v
- x1 +-x2 :$; 14 (t slozky B)
126
114
x 1 ... chléb (kg)
x 2 2: 2 (t)
Xz ... sýr (kg)
-x, + Xz :S 1 (t)
2x, + 4x2 ;::: 3 (tis. kalorií)
z= 5 000x1 + 4 OOOxz ~MAX (Kč)
50x1 + 200x2 ;::: I 00 (g bílkovin)
z= 20x 1 + 60x2 ~ MIN (Kč)
Příklad
20
x 1 ... vázy (ks)
Xz ... misky (ks)
x3
.. • talíře
(ks)
1 +-x
1
-1x1 +-x
2
3
10
16
20
v)
:$; 1(smen
1 +-x
1 +-x
1 :$; 1(smen
v)
-x
1
2
3
8
10
12
z= 500x, + 300xz + 200x3 ~MAX (Kč)
38
39
Zakreslíme hraniční přímku omezující podmínky
3.
Grafické řešení modelu lineárního programování
x1 + 2x2 :S; 20
Pokud položíme x 1 =O, z rovnice 2x 2 = 20 zjistíme, že první průsečík má souřadnice [0, 10].
Malé modely lineárního programovam Je možno řešit graficky. Pro grafické
znázornění modelu používáme rovinu, mližeme tedy pracovat s nejvýše dvěma rozměry.
Proto můžeme graficky řešit pouze modely LP, které mají nejvýše dvě rozhodovací
Pokud položíme x2 = O, z rovnice x 1 = 20 zjistíme, že druhý průsečík má souřadnice [20, OJ.
Hraniční přímku
x2
proměnné (počet omezujících podmínek může být libovolný) nebo které mají nejvýše dvě
omezující podmínky (počet proměnných může být libovolný).
V prvním případě hovoříme o řešeni modelu LP v tzv. "prostoru řešení", kdy osy
reprezentují přímo hodnoty rozhodovacích proměnných, ve druhém o řešeni v tzv.
"prostoru požadavků~~, kdy na osy vynášíme míru uspokojeni požadavkti omezujících
podmínek pomocí příslušné rozhodovacíproměnné.
zakreslíme takto:
15
10
Ci/em kapitoly je poskytnout čtenáři návod, jak postupovat při grafickém řešeni
LP obou typů.
modelů
3.1.
5
Řešené příklady
Příklad
1
o
Pomocí vhodného zobrazení řešte graficky model lineárního programování:
Xt
o
5
10
15
20
25
xl
+ 2x2 :S; 20
3xt + 4x2 ~ 12
x, :S; 8
Nyní musíme určit, která z polorovin vymezených hraniční přímkou obsahuje přípustná řešení
úlohy.
Když chcete zjistit, která polorovina obsahuje přípustná řešení, dosad'te do dané
omezující podmínky libovolný bod, který neleží na hraniční přímce. Pokud je pro
tento bod omezující podmínka splněna, je tato podmínka splněna také pro všechny
body dané poloroviny.
z= 2Xt + X2-----+ MAX
Model obsahuje dvě rozhodovací proměnné a tři omezující podmínky, proto je nutné pro
zobrazení zvolit prostor řešení.
Nejprve musíme vymezit prostor přípustných řešení. Ten tvoří geometrický útvar, který
vznikne jako průnik grafického znázornění omezujících podmínek.
Omezující podmínka ve tvaru nerovnice je reprezentována polorovinou. Pokud ji
chcete zakreslit, musíte určit její hraniční přímku a vymezit správnou polorovinu.
Hraniční přímka je spojnice dvou bodů, pro které je omezujícípřímka splněna jako
rovnice.
Obvykle je výhodné dosadit do omezující podmínky počátek souřadnic, bod [0,0]. Pro naši
podmínku dostaneme výraz
o:S; 20,
což platí. Proto všechny body, které leží v polorovině počátku souřadnic, dané omezující
podmínce vyhovují. Přípustnou polorovinu si označíme takto:
Pro konstrukci hraniční přímky muzeme použít dva libovolné body, které splňují vyse
uvedenou podmínku. Nejčastěji se používají průsečíky hledané hraniční přímky s oběma
osami souřadnic.
Když chcete spočítat průsečíky hraniční přímky s osami souřadnic, zvolte nejprve
=O a z dané podmínky vypočtěte hodnotu souřadnice x 2• Poté položte x 2 =O a
vypočtěte příslušnou hodnotu proměnné x 1• Dostanete tak dva body {O,x2] a [xbO].
Jejich spojením obdržíte hledanou hraničnípřímku omezující podmínky.
XJ
40
41
Třetí
x2
Xt
15
omezující podmínka
:s;8
je tedy rovnoběžná s osou x2 a osu x 1 protíná v bodě x 1 = 8. Přípustná polorovina je
polorovina počátku souřadnic. Celou množinu přípustných řešení tvoří konvexní polyedr,
který je zachycen na následujícím obrázku:
x2
15
20
25
xl
Stejným způsobem postupujeme při zakreslení druhé omezující podmínky
3xt+4x 2 ~12
Pnlsečíky s osami jsou [0, 3] a [4, 0], přípustná je polorovina, která počátek souřadnic
neobsahujc:
x2
20
25
xl
Nyní je už pouze potřeba určit, který bod z množiny přípustných řešení s nejlepší hodnotu
funkce
účelové
15
z = 2x, + X2 ---7 MAX
K tomu jsou potřeba dva kroky. Nejprve zakreslíme libovolnou přímku účelové funkce, což
je spojnice všech bodů [x,, x2] (kombinací proměnných), které vykazují stejnou hodnotu
účelové funkce. Potom nalezneme takovou její rovnoběžku, která bude co nejdále od počátku
souřadnic, ale která bude mít s množinou přípustných řešení společný alespoň jeden bod.
Pokud chcete zakreslit nějakou přímku účelové funkce, dosaďte za symbol "z"
libovolnou hodnotu a přimku zakreslete. Hodnoty vhodné pro dosazeni poznáte tak,
že se budou dobře počítat průsečíky přimky účelovéfunkce s osami souřadnic.
5
o
~
r
o
5
10
15
20
25
xl
Třetí omezující podmínka je specifická, neboť obsahuje pouze jednu proměnnou. V takovém
případě je hraniční přímka rovnoběžná s jednou z os souřadnic.
Pokud omezující podmínka obsahuje pouze proměnnou XJt je rovnoběžná s osou
x2. Pokud omezujlcí podmínka obsahuje pouze proměnnou x 2, je rovnoběžná
s osou XJ. Hraničnlpřlmka vždy protíná druhou osu v bodě, jehož hodnota je rovná
hodnotě pravé strany omezující podmínky.
42
V našem případě položíme z = 1O. Nevhodné (i když přípustné) hodnoty by byly třeba
z = 7,153 nebo z = 1000. V prvním případě by se přímka zřejmě zakreslila nepřesně, ve
druhém by se v daném měřítku nevešla do obrázku.
Do obrázku zakreslíme přímku účelové funkce jako spojnici všech bodů, pro které z
tedy
10 =
2XJ
=
1O,
+ X2
Průsečíky
s osami mají souřadnice [0, 10] a [5, 0].
43
Po vyřešení této soustavy lineárních rovnic dostaneme
x2
x, = 8 a x2 -= 6.
15
předpisu účelové
Dosazením tohoto bodu do
\
z = 2.8 + 6 = 22.
\
Úloha je vyřešena, známe jak hodnoty obou rozhodovacích proměnných, tak hodnotu účelové
funkce.
Příklad
2
Pomocí vhodného zobrazení
Xt
15
----
20
25
xl
----- ·~-----------------------------~
Nyní je už snadné najít rovnoběžku přímky účelové funkce, která je nejdále od počátku
(chceme její maximální hodnotu, při minimalizaci bychom ji požadovali nejblíže počátku) a
která má stále s množinou přípustných řešení společný alespoň jeden bod.
x2
15
x<opt)
20
25
xl
Nakonec je potřeba stanovit hodnoty proměnných v optimálním řešení.
Pokud chc~te stt;,nov~t hodnotyJ!~oměnnýc~ v optimálním řešení z grafu, podívejte
se, na kterych prtmkach omezu)lClch podmmek tento bod leží. Hodnoty proměnných
potom vypočtete snadno jako řešení soustavy dvou rovnic o dvou neznámých.
Náš bod optima x<opt.) leží na přímkách
x, + 2x2 = 20 (první omezující podmínka) a
x,
44
=
4x, - 4x2 + 4x3 + x4- x5
~
20
z = 2x 1 + 4x2 + 2x3 + X4 + X5
~
MAX
Model obsahuje pět rozhodovacích proměnných a dvě omezující podmínky, proto je nutné pro
zobrazení zvolit prostor požadavků. Zobrazení modelu v prostoru požadavků vyžaduje, aby
model byl v tzv. rovnicovém tvaru, tj. aby obě omezující podmínky byly vyjádřeny formou
rovmc.
Pokud chcete vyrovnat omezující podmínku do rovnicového tvaru, podívejte se na
typ původní nerovnice. Pokud se jedná o kapacitní podmínku typu "menší nebo
rovno", doplňkovou proměnnou přičtete k levé straně omezující podmínky.
Pokud se jedná o požadavkovou podmínku typu "větší nebo rovno'', doplňkovou
proměnnou od levé strany podmínky odečtěte.
I
o
W
+ 4x2 + 4x3 + 2x4 + 2x5 ~ 10
modelu do rovnicového tvaru není obtížný. Realizujeme ho přidáním nové tzv.
do každé omezující podmínky, která není vyjádřena jako rovnice.
Doplňkové proměnné je výhodné značit symbolem "ď' s indexem, který odpovídá
pořadovému číslu omezující podmínky. Tak vždy ihned vidíme, ke které omezující podmínce
se doplňková proměnná vztahuje a jakou má interpretaci. Můžete se také setkat se značením,
kdy se pokračuje v řadě proměnných ,,x" a používá se nejmenší další volný index. Toto
značení je matematicky přesnější, ale výrazně méně přehledné.
I
/
Q
graficky model lineárního programování:
doplňkové proměnné
\
o
řešte
Převod
I
*
funkce dostaneme její hodnotu, tedy
8 (třetí omezující podmínka).
V takovém případě klademe také na doplňkové podmínky požadavek na jejich nezápornost.
Doplňkové proměnné přebírají
jednotky omezující podmínky, do které byly předány. Jejich
hodnoty interpretujeme jako "rezervu", která zbývá do úplného vyčerpání omezující
podmínky typu "~', resp. jako "překročení požadavku", který byl stanoven omezující
podmínkou typu "?::.".
Dále je budeme doplňkové proměnné považovat za regulérní
musíme zohlednit v účelové funkci.
modelu, proto je také
do modelu, v účelové funkci je vždy
ohodnoťte nulovou sazbou. Tyto proměnné samy o sobě nemají žádný vztah ke
zvyšování nebo snižování hodnoty kritéria optimalizace.
Pokud
přidáváte
proměnné
doplňkové proměnné
45
Změna
vyvolává změnu hodnoty kriteriální funkce pouze
zprostředkovaně přes změnu hodnot rozhodovacích proměnných.
hodnot
doplňkových proměnných
V našem případě převedeme model do rovnicového tvaru takto:
Podobným způsobem zakreslíme vektor pravých stran omezujících podmínek. Není nutné
kvůli jeho zachycení měnit měřítko grafu, neboť není důležitá jeho velikost, ale pouze jeho
směr. Je proto reprezentován přímkou procházející body [0,0] a [10,20], resp. v našem
měřítku lépe body [0,0] a [1,2].
x, + 4x2 + 4x3 + 2x4 + 2x5 + d, = 10
4x,- 4x2 + 4x3 + X4-
X5-
d2 ""' 20
z= 2x, + 4x2 + 2x3 + X4 + x 5 + Od1 + Od2- MAX
3
Nyní mi'tžeme přistoupit ke zobrazení modelu v prostoru požadavků. Nejprve eliminujeme
vliv rúzného ohodnocení rozhodovacích proměnných v účelové funkci.
2
Pokud chcete eliminovat vliv rozdílného ohodnocení proměnných v účelové funkci,
vydělte koeficienty proměnných z matice soustavy koeficienty účelové funkce.
Dostanete tak míru čerpání kapacity resp. uspokojení požadavku omezující
podmínky vztaženou k jednotce účelové funkce.
o
-2
Podíly budeme zapisovat do vektorů aj (pro j-tou proměnnou), které budou obsahovat dvě
složky, pro každou omezující podmínku jednu. V našem případě dostaneme
a 1= (
-1
h, 2), a2 =- (1, -1), a3 - (2, 2), a4 = (2, 1), as = (2; -1)
mťtžeme
vektory a 1 - a 5 zobrazit graficky.
Pokud chcete zobrazit vektor koeficientů proměnných vztažených k jednotce účelové
fuukce, zakreslete do grafu vektor a,;, který vychází z počátku souřadnicového
systému.
V našem
případě můžeme
I
(!)
1
Doplňkové proměnné mají v účelové funkci nulovou sazbu, proto podíly nelze určit. Ke
zptiSobu práce s doplňkovými proměnnými a jejich zobrazení se ještě vrátíme.
Nyní
-1
L
-2
1
2
•a2
as
' b1
3
•
i
Model obsahuje dvě omezující podmínky, proto bázi daného vektorového prostoru dimenze
dva tvoří dvě bázické proměnné. Z obrázku potřebujeme určit:
• které dvojice proměnných tvoří bázi přípustného (nezáporného) řešení modelu,
• která z přípustných bází je bází optimální.
Pokud chcete zjistit, zda je kombinace proměnné i a proměnné j přípustnou
kombinací, spojte vrcholy vektorů a; a a} Pokud tato spojnice - úsečka - protíná
polopřímku vektoru pravých stran, jedná se o přípustnou kombinaci proměnných.
vektory a 1 - a 5 zakreslit takto:
Pokud například spojíme vektory a 1 a a3, zcela určitě jejich spojnice protíná polopřímku
vektoru pravých stran. Proměnné x 1 a x3 tedy tvoří přípustnou bázi úlohy. Naopak je zřejmé,
že spojnice vektorů a3 a a4 přímku vektoru pravých stran neprotíná. Proto proměnné x 3 a x 4
netvoří přípustnou bázi úlohy.
3
Na následujícím obrázku naleznete všechny kombinace rozhodovacích proměnných, které
bázi úlohy:
tvoří přípustnou
r
-2
-1
-···-
- o- 1 ~--·---
,.
~
-1
~
I
-2
46
,..
-------t
r-
2
- - - -..,
b1
3
•
a2
I
47
"<f
b
/<f
b2 4
/
3
3
a3
--------·
2
''
\
\
I
o
\
o
-1
-1
-', 1
\
I
•a2
2
a3
a1 - d1
-----1----------~
'-.
1
-2
b
/
/
/
a4
'
''
'
''
b1
'' 2
'
3
•
as
-2
Nyní se vrátíme ke způsobu zobrazení doplňkových proměnných. Platí:
Vyskytují se pouze v jedné omezující podmínce, jedna ze souřadnic jejich vektoru tedy bude
nulová. Splývají tedy s osou souřadnic odpovídající omezující podmínce, ke které se vztahují.
Dělení
nulou bychom mohli nahradit dělením nějakou velmi malou hodnotou, která se blíží
nule. Vektor doplňkové proměnné by tedy byl velmi (nekonečně) dlouhý. Spojnice vektoru
rozhodovací proměnné s tímto vektorem si tedy můžeme představit jako rovnoběžku s osou,
se kterou vektor doplňkové proměnné splývá.
Pokud chcete zjistit, zda je kombinace rozlwdovaci a doplňkové proměnné
přípustnou kombinací, ved'te vektorem rozhodovaci proměnné polopřímku
rovnoběžnou s příslušnou osou souřadnic ve směru vektoru doplňkové proměnné.
Pokud tato polopřímka protne polopřímku vektoru b, jedná se o přípustnou
kombinaci.
Doplníme náš obrázek o přípustné kombinace rozhodovacích a doplňkových proměnných:
Doplňková proměnná
d 1 byla k levé straně první omezující podmínky přičítána, v matici
soustavy je zastoupena koeficientem "+ 1", a proto jsou polopřímky spojnic s rozhodovacími
proměnnými orientovány směrem do "+oo". Doplňková proměnná d2 byla od levé strany
druhé omezující podmínky odečítána, v matici soustavy je zastoupena koeficientem "-1", a
proto jsou polopřímky spojnic s rozhodovacími proměnnými orientovány směrem do "-oo".
Nyní již známe všechny kombinace (dvojice) proměnných, které mohou tvořit přípustnou bázi
úlohy. Z nich je potřeba vybrat kombinaci optimální, která maximalizuje hodnotu naší
účelové funkce.
Pokud chcete při maximalizaci účelové funkce určit optimální kombinaci
z přípustných kombinaci proměnných, ;jistěte, která z nich protíná přímku pravých
nejdále od konce vektoru pravých stran. Při minimalizaci ;jistěte, která kombinace
ji protíná nejblíže tomuto vrcholu.
Vysvětlení můžeme naznačit
v jednorozměrném prostoru. Dejme tomu, že bychom měli
uspokojit nějaký jednotkový požadavek jedním ze dvou způsobů. Způsob A bychom pro
uspokojení požadavku museli aplikovat 2x; jedna aplikace tedy uspokojí 1h požadavku,
přičemž stojí 4 Kč. Způsob B stačí aplikovat lx, ale jedna aplikace stojí 10 Kč. Chceme
minimalizovat cenu uspokojení požadavku.
Je zřejmé, že pokud bychom vynaložili 1 Kč, můžeme si za ni koupit bud' 1/s uspokojení
1
požadavku způsobem A, nebo / 10 uspokojení požadavku způsobem B. Proto je lepší
investovat do způsobu, který požadavek uspokojí rychleji, tj. jeho vektor je blíže vektoru
požadavku, viz obrázek:
B A
požada\ek
1
48
49
V našem případě hledáme kombinaci proměnných, která hodnotu účelové funkce
maximalizuje. Proto požadujeme, aby spojnice této kombinace protínala přímku vektoru
pravých stran co nejdále od jeho vrcholu:
3. 2.
Příklady
k
procvičení
Řešte graficky následující modely lineárního programování. Jako výsledek uved'te grafické
znázornění modelu a dále podle typu výsledku:
• pokud má model právě jedno optimální řešení, uveďte hodnoty všech ro?.hodovacích
proměnných a hodnotu účelové funkce v optimálním řešení,
b2 4
• pokud model nemá přípustné řešení nebo hodnota
(klesat), pouze tuto skutečnost uveďte,
3
2
I
Příklad
o
-1
1
0
2x 1 +4x2 ~ 8
I
z = 5x 1 + 2.."1 ~ MAX
'
Příklad
2
Optimální báze je tedy složená z bazických proměnných x 1 a d2• Protože víme, že hodnoty
nebázických proměnných pokládáme rovny nule, snadno zjistíme hodnoty obou bazických
x, + 2x2 = 6
proměnných.
2x,- 4x2 s; 8
Pokud chcete zjistit hodnoty bázických proměnných v optimálním řešení, položte
hodnoty všech nebázických proměnných rovny nule. Z původních omezujících
podmínek v rovnicovém tvaru vám zůstane soustava dvou rovnic o dvou
neznámých, kterou snadno vyřešíte.
Máme tedy soustavu
zůstane nám
x, -= 10
4x, + 12x2 s; 12
z= 2x, +X] ~ MIN
-d2 ~ 20
Příklad
a tedy
XJ =
3
3x,- 2x2 s; 4
a víme, že
4x,
z = 3x 1 + 4x2 ~ MIN
-x, + 4x2 ~ 6
4x, -- 4x2 + 4x3 + X4 + X5- d2 = 20
=O, X3 =O, X4 =O, x 5 =O ad, '"' O (všechno jsou to nebázické proměnné),
-x, + 3x2 s; 6
Příklad
x, + x2 + 4x3 + 2x4 -x5 + d, = 10
x2
může neomezeně tůst
x,+x2 :S;l0
-1
-2
funkce
• pokud má model nekonečně mnoho optimálních řešení, uveďte hodnoty všech
rozhodovacích proměnných ve všech bázických optimálních řešeních a hodnotu účelové
funkce.
1
-2
účelové
10, d2
= 20.
4
4x, + 12x2 s; 24
Po dosazení vypočtených hodnot do účelové funkce
4x1 + x2 ~ 2
z = 2x, + 4x2 + 2x3 + x 4 + X5 + Od1 + Od2
-x, +x2 s; 1
nám vyjde optimální hodnota účelové funkce
5x,- 2x2 s; 5
z- 20.
z= 3x, + 2x2 ~ MAX
Úloha je vyřešena, známe jak hodnoty všech proměnných, tak hodnotu účelové funkce.
50
51
Příklad
5
Příklad
9
2x, + 4xz ~ 8
4x 1 + 3x2 ~ 12
3x, +2xz ~ 12
-2"'(., + xz :s; 2
x, + 4xz ~ 6
x,- xz
Sx, + Xz
5
2x, + 2xz ~ 2
z= 6x 1 + 4xz ~MAX
3x, + 2xz = 6
X!,Xz~O
z =4x 1 +xz ~MAX
~
~
1
x,, xz ;;:: O
Příklad
6
-x1 + xz ~ 3
Příklad
-2x, + 6xz ~ 6
x,
2x,+xz~3
Xz;;::
z= x, + 2xz
~MAX
~
3
3
5x1 + 4x2 ~ 8
x, +
X!,Xz~O
10
Xz ~ 6
x 1 -x2 =0
Příklad
z = x, + 2xz ~MAX
7
x,, Xz ~ O
8x, + 4,8xz ~ 48
2x1 - 2xz :s; 4
4x,- 2xz ~ -16
Příklad
4,5x, - 3x2 :s; 9
0,5x, + 3xz + X.J + X4 = 5
x, +xz ~ 2
x, + 0,5xz + 4x3 + 6x4 = 2
z = 6x, + 4x2
~
MIN
ll
z= x, + 2xz + 2x3 + X4 ~ MIN
x,, Xz ~O
X!, Xz, X3, X4 ~
Příklad
Příklad
8
0
12
x, + 2xz :s; 4
x1- 4xz- 2x3 + X4 = 2
-2x, + Xz
2x, + 2xz + O,Sx3 + 6x4 = 1
~
2
x, + Xz = 2
z= 3x, +Xz+ 2x3 + 3x4 ~MAX
-x, + Xz =O
X!, Xz, X3, X4 ~
0
z= 2x, + 3xz ~ MIN
x,, Xz ~O
52
53
Příklad
13
Příklad
18
4xJ + O,Sx2 + 4x3 + 4x4 ~ 4
3x1 + 4x2 + 2x3 + 3x4 + 6xs :S 4
x1 + 3x2 + 2x3 :'S 3
x 1 + 12x2 + 2x3 + 9x4 + 6xs :S 2
z= 4xl + x2 + 2x3 + 6x4 ~MAX
z =x1 + 4x2 + X3 + 1,5x4 + 4xs ~ MIN
Příklad
Příklad
19
3XJ + 0,5X2 + X3 - 2x4 :S 2
-2x1
+ x 3 + 4x4- 9xs :::; 3
2x1 + 3x2 + 3x3 + 3x4 2:. 6
4x 1 + 3x2
z= XJ + x 2 +O, 75x3 + 2x4 ~ MIN
z= 2x1 + x2- X3 + 2x4- 3xs ~MAX
Příklad
Příklad
14
15
+ 2x4 - 3x5 ;:::: 6
20
XJ + X2 + 2X3- 2x4 > 2
3x, - 4x2 + 2xJ- 8x4 + 2xs ;:::: 7
x, - 2x2 + 4x3 + 4x4 :=:: 1
-4x 1+ 2x2 + 4x3- 4x4 + 2x5 < 1
z = XJ + X2 + Xj + 2x4 ~MAX
z= -x1 + 2x2 + X3 - 2x4 + X5
~
MIN
XJ, X2, X3, X4;:::: 0
Příklad
16
4,5x, + 4x2 + 3x3- 2x4:::; 4
l,5x, + 3x2 + 4,5x3 + 6x4 ~ 4
z = 3x1 + x2 + 3x3 + 2x4 ~ MIN
Příklad
17
12x/ + 3x2 + 4x3 + 2x4 + 2x5
~
5
-3x, + x2 - 4x3 + X4 + 6x5 :::; 5
z = 3x, +x2 + 2x3 +x4 + 2xs ~ MIN
54
55
3.3.
Řešení příkladů
Příklad
Příklad
3
1
x2
2
x2
12
10
0,5
o
-6
-2
6
-0,5 ~
4
6
xl
-1
4
-1,5
x<opt.}
-2
2
-2,5
o
o
2
4
6
8
12
xl
L-----------------------------------------~
Model nemá přípustné řešení.
~---------------------------------~------~
XJ
Příklad
= 10, X2 = 0, Z= 50
Příklad
4
2
r- ---- -
------ - - - - - - - - -
x2
5
-2
xl
xl
z(opt.)
-3
-4
-5
x, = 27; 11,x2=25; 17 ,z= 131 /11
- 6;5, X2 -- 12;5, Z-- 66;5
XJ -
56
57
Příklad
S
Příklad
--I
7
x2
4
3
1
0
-6
I
o
2
3
5
6
8
xl
xl
z( opl.)
Úloha má nekonečně mnoho optimálních řešení, leží na úsečce
lx(opt.)J x(opt.)21
Xt ~ O, X ;t -
2, z !; 8
Hodnoty proměnných:
X(opt.)t: XJ
x<opt.)Z:
=
0, X2 ""' 6,
Z :=
24
Příklad
x, = 3,6, x2 = 0,6, z= 24
8
x2
Příklad
6
I
I
x2
xl
-3
-1
-4
,.. -- 0-
-3
-2
~1
~1
~2
~3
~
rI
~2
1
2
3
4
-3
-1
_,
-4 J
xl
Model má jediné přípustné řešení, které je zároveň řešením optimálním
XI =
1, X2 = 1, Z= 5
Hodnota účelové funkce může neomezeně růst.
58
59
Příklad
Příklad
9
ll
b2
r
5
4,5
4
3,5
3
2,5
-3
-2
2
xl
-1
b
1,5
1
0,5
o
o
XJ
= 1,6 , XJ =
Příklad
0,6 , Z
=
7
Xt =
0,5
1
1,5
2
2,5
3
3,5
4
4,5
5
0, X z = 1,6, XJ = 0, X4 = 0,2, Z = 3,6
10
- - -· -
---- -
-
I
I
I
x2
12
Příklad
12
11
10
~I
7
b
xl
-4
-3
-2
-1
o
1
2
3
XJ = 3,x2=3,z=9
Model nemá přípustné řešení.
60
61
Příklad
Příklad
13
15
b2
3,5
3
3
b
2,5
b
2
1,5
-3
-2
1
-2
0,5
-3
o
o
XJ;;;;:
-4 1
5
Hodnota účelové funkce
O, X] = 8, Xj = O, X4 = O, d, = O, d2 = 21, z= 8
Příklad
Příklad
14
16
b2
b2
4,5
7
6
může neomezeně růst.
I
4
1
3,5
5
a4
a4 -
4
d1
3
2
a1
a4
-,
- r--
-2
XI=
-1
o
1
2
3
4
bl
O, X2 =o, X3 = 2, X4 =O, dl= O, d2 =o, z= 1,5
Bázi optimálního řešení tvoří je tvořena proměnnou x3 a v tomto případě libovolnou další
proměnnou.
62
-2
-1
o
1
2
3
--,
4
bt
5
Nekonečně mnoho optimálních řešení, bázická řešení:
16
= 0, X4 = 2/15, d1 = 0, d2 = 0, Z= 4/3
XJ
= 0, X2
XJ
=O, X2 =O, x3 =O, x 4 =
= /15, X3
2
/ 3,
d1 =
16
/ 3,
d2 =O, z= 4i)
63
Příklad
17
Příklad
19
________ ,l
a1 -
d2
I
1
o
,---.
5
a1
bq
6
-2
I
-3
o
-1
I
iI
L
XJ
J
=5/!2, X2 ""' O, Xj =o, X4 =o, xs =o) d, =O, d2 = 6,25, z= 1,25
Příklad
Hodnota účelové funkce
Příklad
18
může neomezeně růst.
20
b2
b2
7 I
a4
6
aJ.
a1
5
I
I
4
3
I
2
l
I
b
b
1 I
o
-- -
o
XI=
1
2
3
-- r
4
5
I
bd
O, x2 =O, X3 =O, X4 =O, x 5 = O, d1 = 4, d2 = 2, z= O
-4
-2
o
2
4
6
8
bl
Model nemá přípustné řešení.
Obě omezující podmínky jsou typu ,,menší nebo rovno". To je jediný případ, kdy může být
kombinace dvou doplňkových proměnných kombinací přípustnou (za předpokladu
nezápornosti pravých stran). Nesmí se na ni zapomenout, neboť při minimalizaci protíná
vektor požadavků nejdále od počátku souřadnic (v nekonečnu).
64
65
Simplexový algoritmus
Simplexový algoritmus je univerzální metoda pro řešeni modelů lineárnilw
programování. Na rozdll od metod grafického řešeni neni simplexový algoritmus limitován
rozměrem modelu.
Pro úspěšné použiti simplexového algoritmu musíte znát pojmy: kanonický tvar
soustavy lineárních rovnic, bázické řešeni soustavy lineárních rovnic, rovnicový tvar
modelu LP, doplňková proměnná a její interpretace, bázická proměntJá a nebázická
proměnná. Dále musíte bezpečně ovládat Jordanovu eliminační metodu, pomocí které
dokážete přejít od jednoho bazického řešení k jinému.
Cílem kapitoly je procvičit vlastní postup aplikace simplexové metody. Proto výše
uvedené pojmy a postupy nebudou opakovány. V případě nejasností se vrat'te k předchozím
kapitolám cvičebnice, připadne· k jiné teoreticky zaměřené publikaci.
Tomuto cíli je podřízen výběr příkladů k procvičení. Příklady mají záměrně
podobnou strukturu a nejsou příliš náročné na výpočet, aby se čtenář mohl soustředit na
aplikaci simplexového algoritmu a zejména na rozhodování o povaze nalezeného
výsledného řešeni.
4. 1.
Řešené příklady
Příklad
1
Pomocí simplexové metody vyřešte model lineárního programování
2x,+4x2+x3~!2
x, +x2 +x3~ 4
2x,-x2+4x3=6
z= 2x, + 4x2 + X3-- MAX
Nejprve musíme model převést do rovnicového tvaru přidáním doplňkových proměnných do
všech nerovnic v modelu. Princip jejich zavedení byl uveden v kapitole 4, řešený příklad 2.
Model v rovnicovém tvaru vypadá takto:
2x1 + 4x2 + X3 + d1 :: 12
X1
+ X2 + X3 - d2 = 4
2x,-x2+4x3=6
z= 2x, + 4xl + X3 + Od1 + Od2 ._ MAX
Poté model převedeme do tvaru kanonického. Na rozdíl od kapitoly 2 nebudeme zatím
používat Jordanovu eliminační metodu, ale zavedeme do modelu tzv. "pomocné proměnné",
v které doplní jednotkové vektory tam, kde jsou potřeba. Podívejme se na maticový zápis
matice soustavy:
[
~
;
2 -1
1
~ ~~]
4
o o
Ze zápisu vidíme, že matice soustavy obsahuje pouze jeden jednotkový vektor. Náleží
doplňkové proměnné d 1, která byla přidána jako proměnná typu rezerva do první omezující
podmínky.
Do druhé omezující podmínky byla přidána doplňková proměnná d2 , která je typu překročení,
a proto má v matici její koeficient zápornou hodnotu. Sama jednotkový vektor nevytvoří,
proto do druhé omezující podmínky musíme přidat pomocnou proměnnou. Dodržíme princip
indexování, který jsme použili u proměnných doplňkových. Pomocnou proměnnou budeme
označovat symbolem "p" a indexem omezující podmínky, do které byla vložena.
Druhá omezující podmínka bude mít tedy tvar
x, +X] + XJ
-
dl+ P2 - 4
Do třetí omezující podmínky zatím nebyla přidána žádná proměnná, která by vytvořila třetí
vektor jednotkové submatice. Proto i do třetí omezující podmínky přidáme pomocnou
proměnnou:
2xl - x2 + 4x3 + P3 ~ 6
Pokud chcete model transformovat z rovnicového do kanonického tvaru, přidejte
pomocnou proměnnou do všech omezujících podmínek, které původně byly typu
";::::H nebo které byly rovnicemL Získáte tak potřebné jednotkové vektory, které vám
zkompletují jednotkovou submatici.
Pomocné proměnné stejně jako proměnné doplňkové přebírají jednotky omezující podmínky,
do které byly přidány. Požadujeme také, aby nabývaly pouze nezáporných hodnot.
Kladnou hodnotu pomocné proměnné lze interpretovat jako míru nesplnění původní
omezující podmínky. Znamená to tedy, že pokud jakákoliv pomocná proměnná nabývá
v aktuálním řešení kladnou hodnotu, dané řešení není přípustným řešením modelu lineárního
programování.
Z tohoto důvodu je požadováno, aby všechny pomocné proměnné měly v optimálním řešení
nulovou hodnotu a byly tedy proměnnými nebázickými. To se řeší jejich znevýhodněním
v účelové funkci.
Pokud chcete přidáváte pomocné proměnné do modelu, v účelové funkci jim vždy
přiřaďte nevýhodnou (prohibitivmJ sazbu. Zabráníte tak těmto proměnným vstoupit
do optimálního řešeni úlohy.
Prohibitivní sazbu stanovujeme pro každý model zvlášť. Bereme ohled na sazby
rozhodovacích proměnných. Prohibitivní sazbu volíme tak, aby byla v absolutní hodnotě
alespoň o jeden řád vyšší než je řád rozhodovacích proměnných. V minimalizačním modelu
bude tato sazba kladná, v maximalizačním záporná.
66
67
Náš model v kanonickém tvaru vypadá takto:
Hodnotu účelové funkce přitom také nalezneme na kriteriálním řádku. Vypočítá se jako
skalární součin vektoru cen bázických proměnných a vektoru hodnot pravých stran. Zapisuje
se pod sloupec b.
2x, + 4x2 + X3 + d1 = 12
+ X2 +X]- d2 + P2 = 4
Xj
V našem případě jsou v bázi pomocné proměnné, proto je aktuální hodnota z= -100 těžko
interpretovatelná. Nejlépe bychom ji mohli interpretovat jako "ocenění ztráty, která vznikla
nesplněním omezujících podmínek".
2x, - x2 + 4x3 + P3 = 6
z= 2x, + 4x2 + x 3 + Od1 + Od2 -IOp2- lOp3
XJ, X2, X],
~MAX
d,, d2,P2.P3 2: o
Následuje výběr proměnné pro zařazení do báze.
Když chcete zjistit, kterou proměnnou zařadit do báze, podívejte se na absolutní
hodnoty proměnných, které zlepšuji hodnotu účelové funkce. Z těchto proměnných
vyberte tu, která má nejvyšší absolutní hodnotu testu optimality.
Sestavíme výchozí simplexovou tabulku. Do prvního sloupce zapíšeme vektor cen bázických
proměnných c8 , do druhého jejich názvy. Do záhlaví tabulky zapíšeme názvy všech
proměnných a jejich ceny. Výchozí simplexová tabulka našeho modelu vypadá takto:
Ce
Xs
2
x1
o
d1
p2
p3
2
1
2
-10
-10
1
x3
o
o
x2
d1
d2
-10
p2
-10
p3
4
1
1
o
1
-1
1
o
o
4
o
o
o
4
-1
1
o
o
1
V našem případě test optimality jednoznačně určil, že má být do báze zařazena proměnná x 3 •
b
Pokud jednu proměnnou do báze zařadíme, jiná musí bázi opustit. Není možné vyřadit
12
proměnnou libovolně, neboť by mohlo dojít k porušení požadavku na nezápornost pravých
stran v novém řešení. K tomu se používá test přípustnosti nového řešení.
4
6
Když chcete '!jistit, kterou proměnnou z háze vyřadit, jednotlivé složky vektoru
pravých stran vydělte hodnotami z matice soustavy, které se nachází ve sloupci
zařazované proměnné. Z háze vyřadíte proměnnou, pro niž vyjde hodnota tohoto
podílu minimální. Uvažujeme přitom pouze ty řádky, na kterých je ve sloupci
zařazované proměnné kladná hodnota.
Z výchozí simplexové tabulky můžeme také vypsat vektor bazického řešení úlohy:
Xn
= (0, O, O, 12, O, 4, 6)
Toto řešení není přípustným řešením úlohy, neboť báze obsahuje pomocné proměnné. Ty
nabývají kladné hodnoty. Je zřejmé, že do splnění druhé omezující podmínky zbývají 4
jednotky, do splnění třetí omezující podmínky 6 jednotek. První omezující podmínka je
splněna.
Následuje testování optimality výchozího bazického řešení. Pro každou nebázickou
proměnnou určíme, zda je její zařazení do báze výhodné z hlediska účelové funkce.
Když chcete otestovat výhodnost zařazení neházické proměnné do báze, vypočtěte
skalární součin vektoru cen házických proměnných a vektoru příslušné proměnné
v matici soustavy. Od výsledku odečtete cenu testované proměnné.
Výsledky zapíšeme do řádku, který k tabulce
kritéria optimality ,,Zj- c/'.
Cs
o
Xs
d1
-10
p2
-10
p3
zj - cj
přidáme. Označíme
ho
Výsledky testu optimality zapiSUJeme do sloupce
vychází takto:
2
4
1
o
o
-10
-10
Xs
x1
x2
x3
d1
d2
p2
p3
b
Q
d1
-10
p2
-10
p3
zj - cj
2
1
2
-32
4
1
1
4
-51
o
o
12
o
o
o
12
4
1,5
es
o
způsobem výpočtu
4
1
o
o
-10
-10
x1
x2
x3
d1
d2
p2
p3
b
2
1
2
-32
4
1
o
12
1
-1
1
4
-51
es
o
-4
o
o
-1
1
o
o
o
1
4
6
o
10
o
o
-100
1
Optimalitu řešení poznáme snadno.
Když chcete '!jistit, zda je aktuální řešení optimální, podívejte se na hodnoty testu
optimality. Pokud jsou při maximalizaci všechny hodnoty nezáporné (při
minimalizaci nekladné), řešeníje optimání.
Naše výchozí řešení není optimální. Pokud bychom zařadili do báze kteroukoliv
z proměnných x 1, x 2, X3, obdržíme řešení s lepší hodnotou účelové funkce.
1
-1
-4
1
o
o
-1
1
o
o
o
10
1
4
6
o
-100
případě test přípustnosti
Podle testu přípustnosti je nutno vyřadit proměnnou p 3 , protože pro ni vychází hodnota podílu
Q minimální. V bázi tedy proměnná X3 nahradí proměnnou PJ· Ke změně báze použijeme
jeden krok Jordanovy eliminační metody s klíčovým prvkem, který leží na průsečíku
klíčového (třetího) řádku a klíčového (třetího) sloupce. Dostaneme tabulku
2
o
o
n. v našem
2
4
1
o
o
-10
-10
d1
d2
p2
p3
b
n
o
12
12
1
4
6
4
1,5
Xe
x1
x2
x3
2
1
4
-10
d1
p2
-10
p3
2
-1
-4
1
1
4
-51
zj- cj
o d1
-10
p2
1
x3
zj- cj
Opět můžeme
-32
1,5
0,5
0,5
-6,5
1
4,25
1,25
-0,25
-16,75
o
o
1
o
o
o
o
-1
1
o
o
o
1
o
10
o
1
o
o
o
-1
o
o
1
o
o
10
o
o
o
-100
-0,25 10,5
-0,25 2,5
0,25
1,5
12,75 -23,5
n
vypsat aktuální vektor bázického řešení
xu =(O; O; 1,5; 10,5; O; 2,5; 0), z= -23,5.
68
69
Ani toto bázické řešení není přípustné. V bázi je stále pomocná proměnná p2, proto vidíme, že
druhá omezující podmínka není splněna o 2,5 jednotky.
Nyní se již pouze celý postup opakuje. Test optimality
určuje
pro vstup do báze
proměnnou
x1 , test přípustnosti vyřazuje z báze proměnnou p 1 . Pro přechod k nové bázi použijeme jeden
krok Jordanovy eliminační metody s
Dostaneme tabulku
ca
Xs
o
d1
p2
p3
-10
-10
zj - cj
o
d1
-10
1
p2
x3
zj- cj
o
d1
x2
x3
4
1
zj - cj
-"'
1
x3
1
1
4
-51
o
o
1
o
o
o
1
o
o
o
d1
1
d2
-10
p2
-10
p3
o
o
o
o
b
12
4
1
6
o
o
o
10
1
o
o
o
o
-1
1
o
o
o
prvkem 1,25 (druhý
-1
1
o
o
o
o
o
10
3,4
-0,8
-0,2
-3,4
o
-0,25
-0,25
o 0,25
o 12,75
-3,4 0,6
0,8 -0,2
0,2
0,2
13,4 9,4
1
řádek,
druhý sloupec).
n
6
4
3
-100
n
10,5 2,471
2,5
2
1,5
-23,5
n
2
2
2
10
řešení
Bázické
x8
4
2
x2
x1
2
4
1
1
-1
2
-32
-4
1,5 4,25
0,5 1,25
0,5 .0,25
-6,5 -16,75
-0,2
o
0,4
1
0,6
o
0,2
o
klíčovým
(0, 2, 2, 2, O, O, 0), z .: 1O
o
-10
-10
Xs
d1
p2
p3
zj- cj
o
-10
d1
p2
x3
1
zj- cj
o
4
1
d1
x2
x3
zj - cj
o
4
1
d2
x2
x3
zj - cj
určit
hodnotu účelové funkce
x 0 =(O; 2,471; 2, 11 8; 0,588; O; O; 0),
Příklad
z= 12
2
Pomocí simplexové metody řešte model lineárního programování
-4x, + x1 + 2xJ + X4
~
I
2x, + 2x1- l Ox3 + X4 5 4
XJ -
8x1 + 4x3 + 2xt~ < 2
z= 2x, + 4x2 + X3 + 2x4----+ MAX
Převedeme model do rovnicového tvaru. Protože j sou všechny omezující podmínky typu "š',
je tento tvar zároveň tvarem kanonickým.
-4x, + x1 + 2x3 + X4 + d,
=1
2"' + 2x1 - ! Ox3 + X4 + d2 = 4
x, - 8x2 + 4x3 + 2x4 + d3
je již přípustným řešením modelu. Všechny hodnoty proměnných jsou nezáporné a v bázi
modelu není žádná pomocná proměnná. Řešení však stále není optimální, hodnota účelové
funkce muže být zlepšena zařazení proměnné d2 do báze. Dle testu přípustnosti musí být
z báze vyřazena proměnná d1• Po změně vypadá simplexové tabulka takto:
Cg
Řešení je optimální, dle testu optimality žádná nebázická proměnná nezlepší dále hodnotu
účelové funkce. Z výsledné simplexové tabulky můžeme vypsat vektor bázického řešení a
2
x1
2
1
4
x2
4
1
-1
2
-32
-4
1,5 4,25
0,5
1,25
0,5 -0,25
-6,5 -16,75
-0,2
o
0,4
1
0,6
o
0,2
o
-0,06
o
0,353
1
0,588
o
o
o
1
x3
1
1
4
-51
o
o
1
o
o
o
1
o
o
o
1
o
o
o
d1
d2
1
o
o
o
1
o
o
o
o
-10
p2
o
-1
1
o
o
o
o
o
-1
1
o
o
o
10
10
3,4
1
o .0,8
o .0,2
o -3,4
0,294
1
0,235 o
0,059 o
1
o
-10
p3
o
o
1
o
-0,25
-0,25
0,25
12,75
-3,4 0,6
0,8 -0,2
0,2
0,2
13,4 9,4
-1
0,176
o -0,06
0,235
10
10
o
b
n
12
6
4
4
6
3
-100
n
10,5 2,471
2,5
2
1,5
-23,5
n
2
0,588
2
2
10
n
0,588
2,471
2,118
12
=2
z= 2x, + 4x2 + XJ + 2x4 +Od, + Od1 + Od3 ----+MAX
Sestavíme výchozí simplexovou tabulku:
2
o
o
o
x4
d1
d2
d3
b
1
o
-10
4
1
1
2
o
o
1
4
-1
-2
2
4
ca
Xs
x1
x2
1
x3
o
d1
d2
-4
2
1
2
d3
zj - cj
1
2
-8
-2
-4
o
o
o
o
o
1
o
o
1
2
o
o
n
Výchozí bázické řešení
Xn -
(0, O, O, O, 1, 4, 2), z= O
je přípustné, model neobsahuje žádnou pomocnou proměnnou. Dle testu optimality bychom
měli do báze zařadit proměnnou x2 a vyřadit proměnnou d 1 :
70
71
1
2
o
o
o
x1
4
x2
x3
x4
d1
d2
d3
b
n
4
1
2
1
1
o
1
1
2
1
-2
-4
10
-31
-18
2
-8
4
-10
1
2
-2
1
-1
10
2
o
o
o
o
1
o
4
2
2
o
n
2
Ce
Xe
o
d1
o d2
o d3
zj- cj
4
x2
o d2
o d3
zj - cj
1
o
o
o
4
-1
2
-14
20
7
1
-2
8
4
o
o
o
1
o
o
1
o
o
o
1
o
Převedeme model do kanonického tvaru:
Xe
Ce
x1
o
o
o
4
x2
d1
d2
d3
zj- cj
4
x2
-4
2
1
-2
4
2
-8
-4
1
o
o
10
--31
-18
o
o
o
d2
d3
zj- cj
4
x2
2
x1
o d3
zj- cj
o
1
o
o
1
1
o
o
o
1
2
o
o
o
x3
x4
d1
d2
d3
o
b
o
o
4
1
2
o
o
o
1
1
1
o
1
2
-2
1
o
o
1
o
o
o
-14
-1
-2
1
2
10
2
0,6
-0,1
6,9
0,2
8
4
0,2
-0,2
1,8
0,4
o
o
o
20
7
-3,6
-1,4
-23,4
-18,2
1
10
4
1,8
0,2
16,2
7,6
o
o
o
1
o
x,
-
účelové
funkce je
potřeba
do
V tomto případě je prohibitivní sazba kladná, neboť se snažíme hodnotu účelové funkce
minimalizovat. Sestavíme výchozí simplexovou tabulku a provedeme test optimality a
přípustnosti:
1
n
1
1
2
n
1
x 1 + 4x2 2:6
p1
o d2
10
p3
zj- cj
1
4
1
19
1
1
4
47
o
o
o
d1
d2
d3
-1
o
o
o
o
o
-10
1
o
o
-1
-10
10
p1
1
o
o
o
10
p3
b
o
o
4
2
6
100
1
o
n
0,2
x8 = (0, O, O, 2, O, 4, 2), z = 100
n
není přípustné, v bázi se nachází pomocné proměnné. Test optimality zařazuje do báze
proměrmou x2 (minimalizuje me, zlepšující proměnné poznáme podle kladných hodnot na
kriteriálním řádku), test přípustnosti vyřazuje z báze proměnnou PJ· Následující simplexová
tabulka vypadá takto:
Pomocí simplexové metody řešte model lineárního programován í
4XJ +X] :52
x1
Výchozí bázické řešení
1
Ce
Xe
x1
10
o
p1
d2
10
p3
1
4
1
19
0,75
3,75
0,25
7,25
zj- cj
10
p1
o d2
3
x2
zj- cj
3
2:4
Xs
3
x2
10
je přípustné, ale podle testu optimality není optimální. Podle testu pří~u~tn?st~ však n:~xistuje
proměnná, která by mohla být z báze V dalším kroku vyř~ena, aby revse~I ZUStalo pnpustné.
Model nemá optimální řešení, hodnota účelové funkce můze neomezene rust.
X!+ X2
6
x,, x2, d,, d2, dJ,p,,p3 2: O
(0,2; 1,8; O; O; O; O; 16,2), z= 7,6
Příklad
=
z= x1 + 3x.? + Od1 + Od2 + Od3 + 10p1 + 1Op3 ---+ MIN
Bázické řešení
x8
+ x2 + d2 = 2
+ 4x1 - d3 + PJ
Ce
2
-10
4
-1
2
0,4
0,1
3,1
1,8
4xl
1
2
10
4
Ani nové bázické řešení není optimální. Pro zlepšení hodnoty
báze zařadit proměnnou x 1 a vyřadit proměrmou d2:
2
XI+ X.?- dl+ Pl = 4
3
x2
1
1
4
47
o
o
o
10
d1
d2
d3
p1
-1
o
o
o
1
o
o
o
-10
-1
1
o
o
o
o
-10
1
o
o
o
1
o
o
-1
-10
0,25
0,25
-0,25
1,75
o
o
o
1
o
o
o
10
p3
b
o
o
n
4
2
4
2
1
6
1,5
o
100
-0,25 2,5
-0,25 0,5
0,25
1,5
-11,8 29,5
n
Bázické řešení
XB
=(O; 1,5; O; 0,5; O; 2,5; 0), z :- 29,5
je stále nepřípustné. V dalším kroku do báze zařadíme proměnnou x a vyřadíme proměrmou
1
dl:
z =x1 + 3x2---+ MIN
XJ, X2
2:0
72
73
1
3
o
o
o
10
10
p1
p3
b
.n
4.2.
1
o
o
4
2
Příklad
1
6
4
2
1,5
o
es
Xs
x1
x2
d1
d2
d3
10
p1
d2
p3
1
4
1
19
1
1
4
47
-1
o
o
o
0,75
3,75
0,25
7,25
o
o
o
10
zj- cj
10
p1
o
d2
3
x2
zj- cj
10
o
p1
x1
x2
1
3
1
o
o
zj- cj
1
o
o
o
o
o
-10
-1
o
o
-10
-1
1
o
o
o
-10
1
o
o
o
-1
-10
0,25
1
0,25
o
o
-0,25
1,75
0,2
-0,2
0,267 0,067
-0,07 -0,27
-1,93 1,267
o
o
o
1
-0,25
3,333
o
o
o
-0,25
0,5
0,133
X!
+ X2 + X3 .::5 550
0,25
-11,8
-0,2
-0,07
0,267
-11,3
1,5
29,5
2,4
0,133
1,467
28,53
6
X2
.::5 200
1
o
o
o
1
3
o
o
o
10
10
Q
4x, + 6x2 + X3 2: 2200
z= 33x 1 + 52x2 + 7x3
Xt,2,3
Xs
x1
x2
d1
d2
d3
p1
p3
b
Q
10
p1
d2
p3
1
1
1
4
47
-1
o
o
o
1
o
o
4
2
6
100
4
2
1,5
zj- cj
10
o
3
p1
d2
x2
zj- cj
4
1
19
0,75
3,75
0,25
7,25
o
10
p1
1
x1
1
3
x2
o
o
o
3
o
o
o
1
-3
15
4
1
-19
o
p1
d3
x2
zj - cj
1
o
o
o
zj - cj
10
o
o
o
o
-10
-1
o
o
-10
-1
o
o
-10
-1
o
o
-10
1
o
o
o
1
o
o
-1
-10
0,25
0,25
-0,25
1,75
0,2
0,267 0,067
-0,07 -0,27
-1,93 1,267
-0,2
o
o
o
1
o
3,333
0,133
6
1
o
o
o
-0,07 0,133
2
0,267 1,467
-11,3 28,53
-
o
o
o
o
1
1
1
o
o
o
o
o
o
2
-1
2
2
26
o
-10
~
MAX
2: 0
Příklad
2
Řešte model lineárního programování pomocí simplexové metody. Pro optimální řešení
uveďte
.n
-0,25 2,5
-0,25 0,5
0,25
1,5
-11,8 29,5
-0,2
2.4
1
-1
4
-7
1
Řešte model lineárního programování pomocí simplexové metody. Pro optimální řešení
uveďte vektor bázického řešení a hodnotu účelové funkce.
.n
es
o
procvičení
k
100
2,5
Účelovou funkci můžeme dále zlepšit zařazením proměnné d3 na úkor x 1:
10
Přfklady
řešení
vektor bázického
X!
+ X2 + X3 .::5 l 050
X3
.::5 350
a hodnotu
účelové
funkce.
4x, + 2x2 + Sx3 2: 4000
z - 33x1 + 15xz + 42x3 ~MAX
.n
Xt ,2,3 ~
0
12
Příklad
Řešte model lineárního programování pomocí simplexové metody. Pro optimální řešení
.n
uveďte
stále není přípustné, v bázi je pomocná proměnná p 1• Test optimality však signalizuje
optimalitu řešení; neexistuje nebázická proměnná, jejíž zařazení do báze zlepší hodnotu
účelové funkce. Úloha proto nemá žádné přípustné řešení, což si můžete sami snadno ověřit
graficky.
vektor bázického
XJ
+ X2 + X3
x,
~
~
řešení
a hodnotu účelové funkce.
1000
350
5x, + 6x2 + 5x3 2: 5200
Bázické řešení
xu = (0, 2, O, O, 2, 2, 0), z= 26
3
/
z= x, + 6x2 + 4x3
X1,2,3
~
MIN
:2!: Ů
Příklad
4
Řešte model lineárního programování pomocí simplexové metody. Pro optimální řešení
uveďte vektor bázického řešení a hodnotu účelové funkce.
XJ
+ X2 + X3 ~ 900
x, ~ 200
3x, + 6x2 + Sx3;::: 4300
z = 2x 1 + 8x2 + 5x3 ~ MIN
Xt,2,3
74
2: Ů
75
....
Příklad
Příklad
S
Řešte model lineárního programování pomocí simplexové metody. Pro optimální řešení
Řešte model lineárního programování pomocí simplexové metody. Pro optimální řešení
uveďte vektor bázického řešení a hodnotu účelové funkce.
uveďte
x,+xzSIOOO
Xt
XI
9
vektor bázického
řešení
+ Xz + XJ S 600
xz :S 200
:S 250
4x, + 2x2 + 2x3 2: 2400
5x, + 4xz + Sx3 2: 3200
z= 32xl + 13xz + 17x3 ~MAX
z= 42xi + 37xz + 42x3 ~ MAX
Xt,2,3
2: 0
Příklad
a hodnotu účelové funkce.
Xt,2,3
2: 0
Příklad
6
10
Řešte model lineárního programování pomocí simplexové metody. Pro optimální řešení
Řešte model lineárního programování pomocí simplexové metody. Pro optimální řešení
uveďte vektor bázického řešení a hodnotu účelové funkce.
uveďte
XJ+XJS550
X!+ Xz + Xj < 700
XJ :S 200
xz :S 250
XI
+ Xz + X3 2: 500
5x, + 6xz + 2x3 2: 3800
z= 3x, + 4x2 + 2x3 ~ MAX
Xt,2,3
2: 0
Příklad
vektor bázického řešení a hodnotu účelové funkce.
z= 43x, + 52xz + 13x3 ~MAX
Xt,2,3
2: 0
Příklad
7
ll
Řešte model lineárního programování pomocí simplexové metody. Pro optimální řešení
Řešte model lineárního programování pomocí simplexové metody. Pro optimální řešení
uveďte vektor bázického řešení a hodnotu účelové funkce.
uveďte
x,+x2:S1150
Xt
XJ S 300
XJ S 250
2x, + 5xz + 6x3 2: 5200
2x, + 5xz + X3 2: 1100
z = x, + 4xz - 8x3
z = 6x, + 8x2 + x 3 ~ MIN
X!,2,3
~
MIN
2: 0
Příklad
vektor bázického řešení a hodnotu účelové funkce.
+ Xz + X3 S 1000
XJ,2,3
2: 0
Příklad
8
Řešte model lineárního programování pomocí simplexové metody. Pro optimální řešení
12
Řešte model lineárního programování pomocí simplexové metody. Pro optimální řešení
uveďte vektor bázického řešení a hodnotu účelové funkce.
uveďte
X2 + X3 S 850
XI
+ X z + X3 S 500
Xz S200
X3
S 100
5x, + 3xz + 6x3?:: 4100
4xi + 5xz + 3x3?:: 1800
z= -4x, + 2xz + 7x3
Xt,2,3
76
2:0
~
MIN
vektor bázického řešení a hodnotu účelové funkce.
z= 6x, + 8xz + 2x3 ~ MIN
Xt,2,3
2: 0
77
Příklad
13
Příklad
Řešte model lineárního programování pomocí simplexové metody. Pro optimální řešení
uveďte vektor bázického řešení a hodnotu účelové funkce.
-1- Xz -1- X3 ~
Xt
850
xz S 850
+ Sxz + Sx3 2: 2800
Xt
z= 7x, + 46xz + 43x3 ---7 MAX
0
X1,2,3 2:_
Příklad
vektor bázického řešení a hodnotu účelové funkce.
-1- Xz -1- X3:::;
XJ
XJ:::;
XJ
+ Xz
Xt
:5 350
-1- X3
720
S 1000
4x1 -1- Xz -1- XJ 2:_ 2000
z= 32x, + 6xz + 6x3
-~
MAX
>0
Příklad
Řešte model lineárního programování pomocí simplexové metody. Pro optimální řešení
uveďte
Řešte model lineárního programování pomocí simplexové metody. Pro optimální řešení
uveďte vektor bázického řešení a hodnotu účelové funkce.
Xl,2,3
14
17
18
Řešte model lineárního programování pomocí simplexové metody. Pro optimální řešení
uveďte vektor bázického řešení a hodnotu účelové funkce_
XJ-I-Xz-I-XJ:51050
350
xz :5 300
4xl + 4x2 + 5x3 2: 3600
5x, + 5xz + Sx3 2: 5200
z= 36x, + 37x2 + 45x3 ---7 MAX
z= 45x1 + 46xz + 45x3 ---7 MAX
X1,2,3 2:_
0
Příklad
XJ,2,3 ~
15
Příklad
Řešte model lineárního programování pomocí simplexové metody. Pro optimální řešení
uveďte vektor bázického řešení a hodnotu účelové funkce.
XJ
-1- Xz +X]
0
:S ll 00
19
Řešte model lineárního programování pomocí simplexové metody. Pro optimální řešení
uveďte vektor bázického řešení a hodnotu účelové funkce.
Xt
-1- X z -1- X3
:5 }000
xz:::; 350
xz :5 250
2xt + xz + 2x3 ~ 350
5x, + 2xz + 4x3 2: 3800
z
=
7x1 + x 2 + 7x3
Xi,2,3
---7
MIN
0
2:_
Příklad
xl,2,3
16
XJ
vektor bázického řešení a hodnotu účelové funkce.
-1- Xz -1- X]:::;
570
---7
MIN
2: O
Příklad
Řešte model lineárního programování pomocí simplexové metody. Pro optimální řešení
uveďte
z= 6,5x 1 + 2x2 + 5x3
20
Řešte model lineárního programování pomocí simplexové metody. Pro optimální řešení
uveďte vektor bázického řešení a hodnotu účelové funkce.
XJ
-1- Xz -1- XJ :::; 600
xz S 200
xz :5 200
2x, +xz + 2x3 ~ 900
6x 1 + 3x2 + 5x3 2: 2600
z= 5x, + 2xz + 8x3 ---7 MIN
z= 5x1 + 2x2 + 4xJ ---7 MIN
XJ,2,3 2:_
78
0
X i ,2,3
2:_
0
79
4.3.
Řešení příkladů
Příklad
Příklad
Výchozí a výsledná simplexová tabulka
1
6
4
Xs
Ca
x1
x2
x3
1
Výchozí a výsledná simplexová tabulka
33
52
7
ca
Xa
x1
x2
x3
o
d1
1
1
1
o
d2
o
1
o
-100
p3
4
6
1
~433
zj-cj
-652
-107
o
d3
x2
x1
52
33
o
o
1
o
zj-cj
o
3
1
o
o
3
o
o
o
~100
d1
d2
d3
p3
1
o
o
o
o
o
o
1
o
o
o
o
-1
100
o
4
2
1
-1
18
1
~1
o
o
o
o
o
o
1
26
1
33
o
1
100
b
o
o
o
100
550
550
200
200
2200
1100/3
-220000
400
200
350
21950
d1
d2
p3
zj-cj
x3
x1
x2
4
1
6
zj~cj
1
1
5
499
1
1
o
o
6
594
5
496
o
o
o
1
o
o
1
o
1
o
o
o
o
o
o
d1
d2
d3
100
p3
1
o
o
o
o
o
o
o
-1
-100
1
o
-1
1
1
-1
o
o
-3
-1
-2
1
-98
450
350
200
3350
b
o
900
o
o
o
6
o
-5
-6
1
o
b
o
1000
350
5200
520000
1000
866,67
Model má právě jedno optimální řešení.
XB
""' (350; 200; 450; O; O; O; 0), z = 3 350
Model má právě jedno optimální řešení.
Příklad
xn = (350; 200; O; O; O; 400; 0), z = 21 950
Příklad
Výchozí a výsledná simplexová tabulka
2
8
5
Cs
Xa
x1
x2
x3
2
Výchozí a výsledná simplexová tabulka
33
15
42
Ca
Xs
x1
x2
x3
o
o
d1
d2
p3
-100
zj~cj
o
d3
x3
x1
42
33
zj-cj
4
1
1
1
1
5
o
o
o
~100
d1
d2
d3
p3
b
o
1
o
o
o
o
1050
350
4000
-400000
1050
350
800
o
o
4
-433
2
-215
~542
o
o
o
o
o
2
o
4
1
o
o
1
18
1
o
o
Model má právě jedno optimální řešení.
xs = (700; O; 350; O; O; 550; 0),
z= 37 800
o
o
1
o
o
o
-1
100
o
-1
o
1
1
1
1
33
-1
9
o
o
o
1
o
o
100
d1
d2
p3
100
550
350
700
37800
zj-cj
x3
x1
d2
5
2
o
1
1
3
298
o
o
o
Model má
právě jedno
XB =
1
o
6
592
5
495
1,5
-0,5
0,5
-1,5
1
zj-cj
1
o
1
o
o
o
o
o
o
d1
d2
d3
100
p3
1
o
o
o
o
o
-1
-100
1
o
900
200
4300
430000
o
-0,5
0,5
-0,5
-1,5
0,5
-0,5
0,5
-98,5
800
100
100
4200
o
o
o
d1
d2
d3
-100
p3
b
o
1000
250
2400
-240000
1000
250
600
o
o
o
-1,5
2,5
-2,5
-2,5
1
o
o
o
o
1
716,67
optimální řešení.
(1 00; O; 800; O; 100; O; 0), z = 4 200
Příklad
5
Výchozí a výsledná simplexová tabulka
32
13
17
Cs
Xs
x1
x2
x3
o
o
d1
d2
p3
-100
zj-cj
o
o
d1
d2
x3
17
zj-cj
1
o
1
1
4
-432
2
-213
2
-217
o
o
o
1
1,0
1
o
2
2
1
4
o
1
o
1
o
o
1
o
o
o
o
o
o
o
o
o
o
-1
100
o
o
o
o
o
o
-0,5
0,5
108,5
1
o
1
o
o
~8,5
1
1000
250
1200
20400
Řešení není optimální, ale pro vybranou proměnnou nelze provést test přípustnosti. To
ukazuje na situaci, kdy hodnota účelové funkce může neomezeně růst, a proto optimální
řešení neexistuje.
80
81
Příklad
6
Příklad
Výchozí a výsledná simplexová tabulka
3
4
2
Ce
Xs
x1
x2
x3
o
d1
1
o
1
o
d2
o
o
1
-100
p3
1
1
1
zj-cj
-103
-104
-102
o
o
d1
d2
x2
4
zj-cj
o
o
o
1
1
1
o
1
1
1
1
2
o
d1
1
o
d2
o
o
d3
o
o
o
o
o
o
o
-1
100
1
o
o
o
o
o
1
1
o
o
-100
p3
o
o
1
o
o
o
o
-1
-4
1
104
b
550
200
500
-50000
n
550
500
8
Výchozí a výsledná simplexová tabulka
7
2
-4
x3
Xs
x2
Ce
x1
o
o
d1
d2
p3
100
zj-cj
o
o
550
200
500
2000
d1
d2
x1
-4
o
o
5
504
o
o
1
o
zj-cj
1
1
3
298
1
1
0,6
-4,4
1
o
6
593
o
o
o
d1
d2
d3
100
p3
1
o
o
o
o
o
o
o
o
1
1
o
o
o
o
1,2
-1 1,8
1
o
o
o
1
o
o
-1
-100
1
o
o
o
o
o
-0,2
0 ,8
0,2
-100,8
b
o
850
850
200
4100
683,33
410000
850
200
820
-3280
Rešen! ncní _opti~1ální, ale pro vybranou proměnnou nelze provést test přípustnosti. To
~~az~e na_ Sit~ac1, kdy hodnota účelové funkce může neomezeně růst, a proto optimální
resem neexistuJe.
Řešení není optimální, ale pro vybranou proměnnou nelze provést test přípustnosti. To
Příklad
Příklad
~
7
Výchozí a výsledná simplexová tabulka
1
4
-8
Ca
Xs
x1
x2
x3
o
d1
1
1
o
o
d2
1
o
o
100
p3
2
5
6
zj-ej
199
496
608
o
o
d1
d2
x3
-8
zj-cj
1
1
1
o
0,3333 0,8333
-3,6667 -10,667
o
o
1
o
o
o
o
d1
d2
d3
1
o
o
o
o
-1
-100
1
o
o
o
1
o
o
o
1
o
o
o
1
o
o
o
o
o
100
p3
o
o
o
b
n
1150
300
5200
520000
1150
866,67
1150
300
-0,1667 0,1667 866,667
1,3333 -101,33 -6933,33
Rešen~ není. opti'?ální, ale pro vybranou proměnnou nelze provést test přípustnosti. To
~az~Je na. S1t~ac1, kdy hodnota účelové funkce může neomezeně klesat, a proto optimální
y
resem neexistuJe.
82
ukazuje na situaci, kdy hodnota
řešení neexistuje.
účelové
funkce
může neomezeně
klesat, a proto optimální
9
Výchozí a výsledná simplexová tabulka
42
37
42
x3
Xs
x1
x2
Ca
o
o
d1
d2
p3
-100
zj-cj
x1
d2
p3
42
o
-100
zj-cj
1
o
1
1
1
o
5
4
-542
-437
5
-542
1
1
1
-1
105
o
o
o
o
o
o
1
o
o
o
d1
d2
d3
-100
p3
1
o
o
o
o
o
o
o
o
1
o
-5
542
1
o
o
-1
100
o
o
o
o
o
o
-1
100
o
1
o
o
1
1
b
n
600
200
3200
-320000
600
640
600
200
200
5200
Podle testu optimality je řešení optimální, neboť neexistuje proměnná, pomocí které by bylo
možné zlepšit hodnotu účelové funkce. V bázi však stále zůstává pomocná proměnná, která
ukazuje na nesplnění omezující podmínky. Úloha proto nemá přípustné řešení.
83
Příklad
Příklad
10
Výchozí a výsledná simplexová tabulka
Výchozí a výsledná simplexová tabulka
Ce
Xe
o
o
d1
d2
p3
-100
zj-cj
43
52
-100
x1
x2
p3
zj-cj
43
x1
1
o
5
-543
1
o
o
o
52
x2
1
1
6
-652
2E-16
1
-9E-16
1E-13
13
x3
1
o
o
d1
1
o
o
2
-213
o
1
1
o
o
-3
330
-5
543
o
o
d2
d3
o
1
o
o
-1
1
-1
109
-100
p3
o
o
o
o
-1
1
100
o
o
o
o
o
-1
100
1
o
b
n
700
700
250
250
3800 633,33
-380000
zj-cj
o
o
d1
6
x1
1
d2
o
p3
2
194
zj-cj
8
x2
1
o
5
492
o
d1
x3
0,6
1
o
o
8
x2
0,4
1
-2,8
o
zj-cj
1
x3
1
1
1
99
o
o
o
d1
d2
d3
100
p3
XB = (O~ 170~
1
o
o
o
o
o
o
1
o
o
o
o
-1
-100
o
o
1
o
-0,8
1
-0,2
-0,6
0,2
-0,2
1
o
o
o
o
1
o
o
-0,2
-1,6
0,2
-98,4
b
n
1000
250
1100
110000
1000
250;
580~
zj-cj
220
xn2
o
o
o
1
39
1
o
o
d2
d3
-100
p3
1
o
o
o
-546
o
o
o
o
o
o
o
o
5
1
1
o
o
5
1
46
o
o
o
1
o
o
o
-1
100
o
1
-1
o
o
o
1
o
o
100
b
Q
850
850
2800
-280000
850
560
1450
850
850
39100
Xs
o
o
d1
d2
p3
580
250
170
1610
Příklad
zj-cj
d1
x3
x1
6
8
x2
1
4
394
5
492
2
x3
1
1
3
298
o
o
-0,25
o
1
1,25
-0,5
o
o
o
o
o
1
1
39
o
1
o
o
o
o
o
5
o
1
1
o
1
-1
46
o
1
o
o
o
-1
o
o
100
1450
850
o
39100
o; o~ 1450; o), z = 39 100
14
Výchozí a výsledná simplexová tabulka
O; O; 0), z - 1 610
x1
1
o
= (O; 850; o;
4
o
Řešení Xnz má ještě navíc tu vlastnost, že je degenerované, neboli jedna složka vektoru
pravých stran nabývá nulovou hodnotu (proměnná x 3 ).
Výchozí a výsledná simplexová tabulka
Ce
d3
x2
x3
46
46
12
zj-cj
4
1
o
d1
1
46
x3
1
V řádku zJ cJ je více nul než je bázických proměnných . Nulová hodnota je navíc ve druhém
sloupci u nebázické proměnné X2- Model má proto nekonečně mnoho optimálních řešení; dvě
bázická jsou:
o
Úloha má právě jedno optimální řešení.
o
1
-107
46
x2
1
1
5
-546
a
Xe
2
6
d3
d2
x3
7
x1
xm = (O~ O; 850; O; 850; 1450~ 0), z = 39 100
Ce
100
d1
d2
p3
zj-cj
Výchozí a výsledná simplexová tabulka
Příklad
o
o
46
ll
o
Xe
o
o
testu ~ptimality je řešení optimální, neboť neexistuje proměnná, pomocí které by bylo
mozn~ zleps1t hodnotu účelové funkce. V ~ázi však stále zůstává pomocná proměnná, která
ukazuJe na nesplnění omezující podmínky. Uloha proto nemá přípustné řešení.
100
Ce
-100
450
250
50
27350
Po~le
Příklad
13
o
o
o
d1
1
d2
d3
100
p3
o
o
o
o
o
-1
1
-100
o
0,25
-0,25
-0,25
-1,5
0,25
-98,5
o
o
o
1
o
o
o
1
o
o
-0,25
1
-0,75
-2,5
o
o
Ce
Xs
o
o
d1
d2
p3
-100
b
n
500
100
1800
180000
500
25
100
375
2450
zj-cj
o
o
-
d3
d2
x3
45
360
zj-cj
36
x1
1
37
x2
1
1
o
4
-436
4
-437
45
x3
1
o
o
o
dí
1
d2
d3
-100
p3
o
o
o
o
o
-1
1
100
o
1
-1
o
100
350
720
32400
-545
o
o
o
o
o
5
1
1
1
1
9
o
o
o
1
8
1
1
o
45
5
1
o
o
o
1
o
o
o
o
o
o
o
b
n
720
350
3600
-360000
720
720
Model má právě jedno optimální řešení.
XB
= (O; O; 720; O; 350; O; 0), z = 32 400
Řešení je degenerované, bázická proměnná d3je rovna nule.
Úloha má právě jedno optimální řešení.
XB = (375~
84
O; 100; 25~ O; O; 0), z= 2 450
85
Příklad
Příklad
15
Výchozí a výsledná simplexová tabulka
7
1
7
Cs
Xs
x1
x2
x3
o
d1
1
1
1
o
d2
o
1
o
100
p3
2
1
2
zj-cj
193
99
193
o
o
o
d1
x2
x3
1
7
1
o
zj-cj
o
o
o
1
o
o
1
o
o
o
o
d1
1
d2
d3
o
o
o
o
o
-1
1
o
o
o
1
o
o
o
1
o
o
-0,5
1
-0,5
-2,5
100
p3
-100
o
0,5
-0,5
-0,5
-3,5
0,5
-96,5
o
o
b
1100
350
350
35000
o
1100
175
17
Výchozí a výsledná simplexová tabulka
32
6
6
Cs
Xs
x1
x2
x3
o
d1
1
1
1
o
d2
1
o
o
-100
p3
4
1
1
zj-cj
-432
-106
-106
750
350
o
d3
o
32
x1
x2
1
6
o
zj-cj
350
o
o
o
o
o
o
o
o
d1
1
d2
d3
-100
p3
o
o
o
o
o
o
o
o
-1
100
1
o
3
1
-1
26
1
-1
o
o
1
o
o
1
1
o
o
1
6
1
o
o
o
o
o
100
b
1000
350
2000
-200000
o
1000
500
50
350
650
15100
~od~l ma al~~rna~zv?í optimální řešení. Protože proměnné x 1 a x3 čerpají zdroje úplně
Model má alternativní optimální řešení. Protože proměnné x2 a x 3 čerpají zdroje úplně
identicky, mají stejné hodnoty ve svých sloupcích a je tedy jedno, kterou z nich budeme
považovat za bázickou (vždy však právě jednu z nich).
promenna x3 nabyva nulove hodnoty.
xm = (350; 650; O; O; O; 50; 0), z = 15 100
tdent~cky, maJI, s_teJne hodnoty ve svých sloupcích a je tedy jedno, kterou z nich budeme
pov~ov~t za baz~c~ou (vž~y však právě jednu z nich). Řešení je navíc degenerované, bázická
Xn
= (O; 350; O; 750; O; O; 0), z = 350
Příklad
Xn2 -
16
Příklad
Výchozí a výsledná simplexová tabulka
5
2
8
Cs
Xs
x1
x2
x3
o
d1
1
1
1
o
d2
o
1
o
100
p3
2
1
2
zj-cj
195
98
192
o
d1
x2
x1
2
5
zj-cj
o
o
1
o
o
1
o
o
o
o
1
-3
'
Model ma pravě
Jedno optimální řešení.
'
Xs =
86
(350; O; 650; O; O; 50; 0), z = 15 100, výsledná tabulka bude úplně stejná.
(350; 200; O; 20; O; O; 0), z = 2 150
o
d1
1
o
o
o
1
o
o
o
o
o
d2
d3
o
o
100
p3
o
o
o
o
o
-1
-100
1
o
-0,5
1
-0,5
-0,5
0,5
-0,5
1
o
-0,5
-2,5
o
0,5
-97,5
b
570
200
900
90000
o
570
450
18
Výchozí a výsledná simplexová tabulka
45
46
45
es
Xs
x1
x2
x3
o
d1
1
1
1
o
d2
o
1
o
-100
p3
5
5
5
zj-cj
-545
-545
-546
o
20
200
350
2150
d3
x2
x1
46
45
zj-cj
o
o
1
o
o
1
o
o
o
o
1
o
o
o
o
d1
1
d2
d3
-100
p3
o
o
o
o
o
-1
100
1
o
1
-1
o
o
o
100
o
o
1
5
o
o
o
1
45
1
-1
1
o
o
o
o
b
o
1050
300
5200
-520000
1050
1040
50
300
750
47550
Model má alternativní optimální řešení. Protože proměnné x 1 a x3 čerpají zdroje úplně
identicky, mají stejné hodnoty ve svých sloupcích a je tedy jedno, kterou z nich budeme
považovat za bázickou (vždy však právě jednu z nich).
x 81
= (750; 300; O; O; O; 50; 0), z = 47 550
Xs2
= (O; 300; 750; O; O; 50; 0), z = 47 550, výsledná tabulka bude úplně stejná.
87
Příklad
19
Výchozí a výsledná simplex ová tabulka
Ce
Xe
o
o
d1
d2
p3
100
zj-cj
5
2
6,5
6,5
x1
1
o
5
493,5
2
x2
1
1
2
198
o
o
x3
x2
x1
o
4
395
o
1
1
o
o
o
o
o
1
o
zj-cj
5
x3
1
[ 5.
o
o
o
d1
1
d2
d3
100
p3
o
o
o
o
o
o
o
-1
-100
1
o
1
o
-1
-4
-3
1
2
-1
o
o
o
o
1
5
o
b
o
1000
250
3800
380000
1000
-1
-1 ,5
1
-98,5
450
250
300
4700
-0,5
0,5
-0,5
-1,5
0,5
-0,5
0,5
-98,5
900
100
150
4700
o
760
Model má nekonečně mnoho optimálních řešení. Bázická jsou
XBt = (300; 250; 450; O; O; O; 0), z = 4 700
a
5
x3
2
x2
d2
o
1,5
-0,5
0,5
o
zj-cj
o
1
o
o
1
o
o
o
o
-1
2
o
-2
1
-1
o
(O; 100; 900; O; 150; O; 0), z = 4 700
XB2 =
Příklad
Výchozí a výsledná simplex ová tabulka
Ce
Xa
o
o
d1
d2
p3
zj-cj
4
2
5
x3
x2
x1
5
x1
1
2
x2
1
4
x3
1
6
595
o
3
298
5
496
o
o
o
o
1
o
zj-cj
1
o
o
1
1
o
o
o
o
o
o
d1
1
d2
d3
o
o
o
o
o
6
o
-5
-1
1
o
o
o
100
p3
o
o
-1
1
-100
o
1
-1
o
b
600
600
200
2600 433,33
260000
-3
1
2
-1
o
1
o
-1
-99
2000
o
o
400
200
v
Rešení je dege~er?vané, .hodnota bázické proměnné x1 je rovna nule. Model
má
mnoho altemativmch optimálních řešení, bázická jsou
Xst
Brožová, H., Houška, M. (2008): Základní metody operační analýzy. PEF
ČZU v Praze
ISBN 978-80-213-0951-7.
'
Eppen, G. D., Gould, F., Schmidt, C. (1993): Introduction to Manag ement
Science. Prentice
Hall, New Jersey, ISBN 978-0877784623
Fotr, J., Dědina, J., Hrůzová, H. (2003): Manažerské rozhodování. Ekopress,
Praha, ISBN 8086119-69-6.
Gros, I. (2003): Kvantitativní metody v manažerském rozhodování. Grada,
Praha, ISBN 80247-0421-8.
Jablonský, J. (2002): Operační výzkum. Professional Publishing, Praha, ISBN
978-80-8694644-3.
Lawrence, J. A., Pastem ak, B. A. (2002): Applied Manag ement Science.
John Wiley and
Sons, ISBN 978- 0471137766.
Lofti, V. (1996) : Decisio n Support for Operations Manag ement and Manag
ement Science.
Burr Ridge, Irwin, ISBN 978-0256115598.
Maňas, M. a kol. (1991): Matematické metody v ekonomice. SNTL, Praha, ISBN
XXXX X
Pelikán, J. (2001): Diskré tní modely v operačním výzkumu. Professional Publish
ing, Praha,
ISBN 80-86419-17-7.
20
100
Literatura
=(O; 200; 400; O; O; O; 0), z= 2 000
nekonečně
Pitel, J. a kol. (1988): Ekonomicko matematické metódy. Príroda, Bratislava,
ISBN XXXX X
Šubrt, T., Brožová, H., Domeová, L., Kučera, P. (2005): Ekonomicko matem
atické metody II
- Aplikace a cvičení. PEF ČZU v Praze, ISBN 80-213-0721-8.
Získal, J., Beránková, M., Houška, M. (2005): Lineární programování I. PEF
ČZU v Praze,
ISBN 80-213-1313-7.
Získal, J., Houška, M., Beránková, M. (2006): Lineární programování II. PEF
ČZU v Praze,
ISBN 80-213 -1353-6.
Získal, J., Domeová, L., M., Beránková, M. (2005): Lineární programování
III. PEF ČZU
v Praze, ISBN 80-213-1397-8.
Získal, J., Havlíček, J. (1998): Ekonomicko matematické metody I. PEF ČZU
v Praze, ISBN
80-213-0761-7.
Získal, J., Kosková, I. (2002): Cvičení z metod operační analýzy. PEF ČZU
v Praze, ISBN
80-213-0244-5.
a
4
x3
x2
d2
2
o
zj-cj
Xsz =
88
2
o
-0,5
0,5
1
o
o
o
1
o
o
o
-1,5
2,5
-2,5
-1
o
-0,5
1
0,5
-0,5
-1
o
o
0,5
-0,5
0,5
-99
400
200
o
2000
(O; 200; 400; O; O; O; 0), z = 2 000
89
Download

null