UNIVERZITA OBRANY • KATEDRA EKONOMETRIE
UČEBNÍ TEXT PRO DISTANČNÍ STUDIUM
EKONOMICKO-MATEMATICKÉ
METODY
RNDr. Michal ŠMEREK
doc. RNDr. Jiří MOUČKA, Ph.D.
Brno
2008
Anotace: Skriptum „Ekonomicko-matematické metodyÿ je učební text pro distanční
studium předmětu Ekonomicko-matematické metody v kombinovaném studijním
programu na Fakultě ekonomiky a managementu Univerzity obrany v Brně. Obsahuje základy teorie ekonomicko-matematických metod v rozsahu, který odpovídá
základnímu kurzu ekonomicko-matematických metod schválenému akreditačním
řízením. Způsob zpracování textu respektuje skutečnost, že student bude pracovat s textem samostatně bez pomoci vyučujícího.
Klíčová slova: Soustava lineárních rovnic, soustava lineárních nerovnic, kanonický
tvar soustavy lineárních rovnic, základní a vedlejší proměnná, základní a nezákladní řešení, degenerované a nedegenerované řešení, přípustné a nepřípustné
řešení, optimální a neoptimální řešení, alternativní řešení, úloha výrobního plánování, směšovací úloha, rozdělovací úloha, obecná úloha lineárního programování,
grafická metoda, simplexová metoda, výchozí řešení, základní proměnná, doplňková proměnná, test optimálnosti řešení, zlepšování řešení, metoda umělé báze,
pomocná proměnná, pomocná účelová funkce, rozšířená úloha lineárního programování, dualita, duálně simplexová metoda, parametrické lineární programování,
dopravní úloha, vyrovnaná dopravní úloha, nevyrovnaná dopravní úloha, Vogelova aproximační metoda, výchozí základní řešení, test optima, uzavřený okruh,
přiřazovací problém, maďarská metoda, nezávislé nuly, Königova věta, krycí čáry.
Skriptum neprošlo redakční ani jazykovou úpravou.
Projednáno a schváleno na metodickém shromáždění katedry dne 28. 4. 2008.
Recenzenti:
doc. RNDr. Josef KALAS, CSc.
RNDr. Vratislava MOŠOVÁ, CSc.
c Michal ŠMEREK, Jiří MOUČKA, 2008
ISBN 978-80-7231-526-0
Obsah
Předmluva
5
1 ÚVOD
6
2 MATEMATICKÉ ZÁKLADY LINEÁRNÍHO PROGRAMOVÁNÍ
2.1 Soustava lineárních rovnic . . . . . . . . . . . . . . . . . . . . . . . . .
2.2 Soustava lineárních nerovnic . . . . . . . . . . . . . . . . . . . . . . . .
2.3 Shrnutí 2. kapitoly . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.4 Test ke kapitole 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9
9
15
19
19
3 FORMULACE ÚLOH LINEÁRNÍHO PROGRAMOVÁNÍ
3.1 Úloha výrobního plánování . . . . . . . . . . . . . . . . . . . .
3.2 Směšovací úloha . . . . . . . . . . . . . . . . . . . . . . . . . .
3.3 Rozdělovací úloha . . . . . . . . . . . . . . . . . . . . . . . . .
3.4 Obecná úloha lineárního programování . . . . . . . . . . . . .
3.5 Shrnutí 3. kapitoly . . . . . . . . . . . . . . . . . . . . . . . .
3.6 Test ke kapitole 3 . . . . . . . . . . . . . . . . . . . . . . . . .
.
.
.
.
.
.
21
21
23
26
28
30
30
4 GRAFICKÁ METODA
4.1 Grafická metoda řešení úloh lineárního programování . . . . . . . . . .
4.2 Shrnutí 4. kapitoly . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.3 Test ke kapitole 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
31
31
36
36
5 SIMPLEXOVÁ METODA
5.1 Nalezení výchozího řešení .
5.2 Test optimálnosti řešení .
5.3 Zlepšování řešení . . . . .
5.4 Shrnutí 5. kapitoly . . . .
5.5 Test ke kapitole 5 . . . . .
.
.
.
.
.
37
38
40
41
45
45
6 METODA UMĚLÉ BÁZE
6.1 Metoda umělé báze . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.2 Shrnutí 6. kapitoly . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.3 Test ke kapitole 6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
47
47
51
51
7 DUALITA V ÚLOHÁCH LINEÁRNÍHO PROGRAMOVÁNÍ
7.1 Pojem duality a konstrukce duální úlohy . . . . . . . . . . . . . .
7.2 Ekonomická interpretace duální úlohy . . . . . . . . . . . . . . . .
7.3 Duálně simplexová metoda . . . . . . . . . . . . . . . . . . . . . .
7.4 Shrnutí 7. kapitoly . . . . . . . . . . . . . . . . . . . . . . . . . .
7.5 Test ke kapitole 7 . . . . . . . . . . . . . . . . . . . . . . . . . . .
53
53
61
62
67
67
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
3
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
8 PARAMETRICKÉ LINEÁRNÍ PROGRAMOVÁNÍ
8.1 Parametrizace pravých stran . . . . . . . . . . . . . . .
8.2 Parametrizace koeficientů účelové funkce . . . . . . . .
8.3 Shrnutí 8. kapitoly . . . . . . . . . . . . . . . . . . . .
8.4 Test ke kapitole 8 . . . . . . . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
69
69
72
77
77
9 DOPRAVNÍ ÚLOHA
9.1 Vyrovnaná dopravní úloha . . . . . . . . . . . . . .
9.2 Vogelova aproximační metoda . . . . . . . . . . . .
9.3 Test optima . . . . . . . . . . . . . . . . . . . . . .
9.4 Zlepšování řešení . . . . . . . . . . . . . . . . . . .
9.5 Degenerované a alternativní řešení dopravních úloh
9.6 Nevyrovnaná dopravní úloha . . . . . . . . . . . . .
9.7 Shrnutí 9. kapitoly . . . . . . . . . . . . . . . . . .
9.8 Test ke kapitole 9 . . . . . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
79
79
82
87
89
92
98
103
103
10 PŘIŘAZOVACÍ PROBLÉM
10.1 Přiřazovací problém minimalizačního typu
10.2 Přiřazovací problém maximalizačního typu
10.3 Shrnutí 10. kapitoly . . . . . . . . . . . . .
10.4 Test ke kapitole 10 . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
105
105
113
116
116
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Seznam literatury
119
Rejstřík
121
Vstup do verze k prohlížení na obrazovce.
4
5
Předmluva
Tento učební text byl vytvořen především pro studenty kombinovaného studia Fakulty
ekonomiky a managementu Univerzity obrany v Brně, kteří budou studovat předmět
Ekonomicko-matematické metody distanční formou. Svým stylem navazuje na studijní
materiály vytvořené na katedře ekonometrie v předchozích letech pro výuku předmětů
Matematika a Statistika distanční formou. Prezentovaná učební látka je uspořádaná
a členěná stejným způsobem, což umožní studentům využít své zkušenosti ze studia
dříve absolvovaných předmětů a využít stejný styl práce při studiu. Zařazení mnoha
ilustrativních řešených příkladů, úloh k procvičení a testů umožňuje využití předkládaného učebního textu i studenty prezenčního studia Fakulty ekonomiky a managementu
i studenty jiných fakult a vysokých škol studujících předmět Ekonomicko-matematické
metody, Operační výzkum či Operační analýza se stejným obsahem a v obdobném
rozsahu.
Vědní disciplína Operační výzkum někdy také nazývaná Operační analýza se zabývá
formulováním, modelováním a řešením rozmanitých rozhodovacích situací, tedy situací,
ve kterých rozhodovací subjekt vybírá nejlepší řešení z mnoha možných řešení, které
jsou k dispozici.
Předmět Ekonomicko-matematické metody chápeme jako Operační výzkum zkoumající ekonomické rozhodovací situace.
Z řady dílčích disciplín Operačního výzkumu předkládáme čtenářům základy lineárního programování, především simplexovou metodu a její modifikace, kterou využíváme
při řešení úloh výrobního plánování, směšovacích a rozdělovacích úloh. V druhé části
skript je rozebírána dopravní úloha a přiřazovací problém, což jsou ve své podstatě
opět úlohy lineárního programování, ale vzhledem k jejich specifické formě jsou řešeny
speciálními metodami.
Za jednotící linii lze považovat použitý matematický aparát. Jedná se o základní
pojmy a techniky lineární algebry, které by student většinou měl znát z předmětu
Matematika.
Děkujeme všem, kteří nám nějakým způsobem pomohli při přípravě tohoto textu.
Za pečlivé přečtení textu a cenné připomínky patří naše poděkování zejména oběma
recenzentům – RNDr. Vratislavě Mošové, CSc. a doc. RNDr. Josefu Kalasovi, CSc. Za
kontrolu textu a propočítání příkladů děkujeme rovněž Aleši Koutnému, studentovi
druhého ročníku FEM UO.
Děkujeme také všem, kteří nám svými postřehy, připomínkami a náměty budou
ochotni pomoci dále zkvalitnit obsah i formu tohoto učebního textu.
Brno, 19. 4. 2008
Michal Šmerek
[email protected]
Jiří Moučka
[email protected]
katedra ekonometrie FEM UO v Brně
6
1
ÚVOD
S rozvojem technologií se komplikují i různé výrobní procesy. Potřeba modelovat rozhodovací situace, umět hledat optimální rozhodnutí, řešení, způsobila rozvoj odvětví
nazývaného OPERAČNÍ VÝZKUM (nebo též OPERAČNÍ ANALÝZA či EKONOMICKO - MATEMATICKÉ METODY).
Operačním výzkumem se rozumí souhrn metod, jimiž se řeší rozhodovací situace.
Řeší se problémy, které mají více možných řešení, a mezi nimi se hledá to řešení, které
nejlépe vyhovuje zadanému cíli. Takové řešení se nazývá optimální řešení.
Každý rozhodovací problém má několik fází řešení:
1. Daný problém se analyzuje z ekonomického hlediska, tj. tvoří se ekonomický
model.
2. Sestaví se odpovídající matematický model.
3. Řeší se matematický model - hledá se konkrétní číselné řešení.
4. Interpretace výsledků řešení.
5. Realizace řešení.
ad 1. Výsledkem rozboru ekonomické reality bývá kvalitativní a kvantitativní popis
situace - vlastní slovní zadání úlohy. Problémy sledujeme na zjednodušených modelech (modelem rozumíme zjednodušený obraz skutečnosti; uvažujeme pouze ty
stránky skutečnosti, které jsou z hlediska studovaného jevu významné).
Ekonomický model by měl obsahovat:
• CÍL (kritérium) - musí být jasně vymezen. Příkladem může být např. maximalizace zisku, minimalizace nákladů, . . .
• PROCESY, které probíhají při dané rozhodovací situaci.
• ČINITELE ovlivňující daný proces a popis vztahů mezi procesy a činiteli.
1.0.1 Příklad. Podnik vyrábí tři druhy výrobků V1 , V2 a V3 .
Na výrobu jednoho výrobku V1 spotřebuje 15 kg suroviny S, 3 kWh energie E a
výroba trvá 1 h strojového času T .
Na výrobu jednoho výrobku V2 spotřebuje 20 kg suroviny S, 4 kWh energie E a
výroba trvá 21 h strojového času T .
Na výrobu jednoho výrobku V3 spotřebuje 40 kg suroviny S, 7 kWh energie E a
výroba trvá 3 h strojového času T .
Prodejem každého výrobku V1 dosáhne podnik zisku 700 Kč, u výrobku V2 je to
500 Kč a u výrobku V3 1300 Kč.
Podnik má k dispozici 10 000 kg suroviny S, 4000 kWh energie E a 1000 h
strojového času T .
Při jakém plánu výroby bude zisk podniku maximální?
7
Ekonomickým modelem je již samotné slovní zadání úlohy. Často se však takový
ekonomický model uvádí i ve formě tabulky.
EKONOMICKÝ
MODEL
Výrobky
Disponibilní
V1
V2
V3
množství
surovina
S
15
20
40
10 000
energie
E
3
4
7
4 000
strojový čas
T
1
1
2
3
1 000
700
500
1 300
max
zisk
ad 2. Abychom mohli daný ekonomický model řešit, musíme vyjádřit podmínky i cíl
procesu pomocí matematických prostředků (funkce, rovnice, nerovnice, . . . ). Tím
vytvoříme odpovídající matematický model. Řešením tohoto modelu pak dostáváme odpovídající řešení. Jsou-li funkce, rovnice a nerovnice používané v daném matematickém modelu pouze lineární (tj. 1. stupně), jde o úlohu lineárního
programování.
1.0.2 Příklad. V podniku se provádějí tři činnosti, výroba výrobků V1 , V2 a V3 ,
tedy matematický model bude obsahovat 3 proměnné:
x1 . . . počet vyrobených výrobků V1 ,
x2 . . . počet vyrobených výrobků V2 ,
x3 . . . počet vyrobených výrobků V3 .
Matematické vyjádření omezujících podmínek:
i) Nelze vyrábět záporné množství výrobků =⇒ x1 ≥ 0; x2 ≥ 0; x3 ≥ 0.
Jsou to tzv. podmínky nezápornosti.
ii) Při výrobě jednoho výrobku V1 spotřebujeme 15 kg suroviny S. Vyrobímeli x1 těchto výrobků, spotřebujeme 15 x1 kg suroviny S. Analogicky i pro
výrobky V2 a V3 . Spotřeba suroviny S celkem je tedy:
S : 15x1 + 20x2 + 40x3 kg.
Celková spotřeba nesmí přesáhnout disponibilní množství. Tedy:
S : 15x1 + 20x2 + 40x3 ≤ 10 000.
Analogicky postupujeme i pro spotřebu energie a strojového času:
E : 3x1 + 4x2 + 7x3 ≤ 4 000,
T : x1 + 0,5x2 + 3x3 ≤ 1 000.
Uvedené tři nerovnice se nazývají vlastní omezující podmínky.
Úkolem je určit plán výroby, tj. vektor výroby x = (x1 , x2 , x3 ), při němž bude
zisk maximální. Hodnota zisku pro daný plán výroby je dána funkcí
z = 700x1 + 500x2 + 1 300x3 .
8
Taková funkce se nazývá účelová funkce. Účelová funkce v tomto případě je
maximalizačního typu.
Celkově má tedy matematický model úlohy takový tvar:
z = 700x1 + 500x2 + 1 300x3 −→ max,
15x1 + 20x2 + 40x3 ≤ 10 000,
3x1 + 4x2 +
7x3 ≤ 4 000,
x1 + 0,5x2 +
3x3 ≤ 1 000,
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0.
Sestavení matematického modelu úlohy lineárního programování, stejně jako další fáze
řešení, jsou předmětem studia v následujících kapitolách.
9
2
MATEMATICKÉ ZÁKLADY LINEÁRNÍHO
PROGRAMOVÁNÍ
Tato kapitola slouží k zopakování a prohloubení těch částí učiva základního kurzu matematiky, jež budeme využívat při řešení úloh lineárního programování (dále jen LP).
Především zde uvedeme definice soustavy lineárních rovnic (SLR), soustavy lineárních
nerovnic (SLN), řešení těchto soustav, jejich vlastnosti a základní věty s těmito pojmy
spojené.
Cílem kapitoly je:
• zopakovat si řešení soustavy lineárních rovnic, řešení soustavy úplnou eliminací,
• zopakovat si soustavy lineárních nerovnic, převod SLN na SLR,
• seznámit se s pojmy kanonický tvar SLR, základní a vedlejší proměnná,
základní a nezákladní řešení, degenerované a nedegenerované řešení, atd.
2.1
Soustava lineárních rovnic
2.1.1 Definice. Soustavou m lineárních rovnic o n neznámých rozumíme systém
rovnic
a11 x1 + a12 x2 + . . . + a1n xn = b1 ,
a21 x1 + a22 x2 + . . . + a2n xn = b2 ,
(2.1)
.. ..
.. ..
..
..
..
. .
. .
.
.
.
am1 x1 + am2 x2 + . . . + amn xn = bm ,
přitom pro ni lze užít i ekvivalentní maticový zápis
A · xT = bT ,
kde A je matice soustavy, xT je vektor neznámých a bT je vektor absolutních členů.
Matice R = (A|bT ) je tzv. rozšířená matice soustavy.
2.1.2 Poznámka. Matice soustavy (2.1) je

a11 a12 . . . a1n
 a21 a22 . . . a2n

A =  ..
..
..
 .
.
.
am1 am2 . . . amn



.

10
2 MATEMATICKÉ ZÁKLADY LP
Rozšířená matice soustavy (2.1) má tvar

a11 a12 . . . a1n b1
 a21 a22 . . . a2n b2

R =  ..
..
..
..
 .
.
.
.
am1 am2 . . . amn bm



,

vektor absolutních členů je



b = (b1 , b2 , . . . , bm ), a tedy bT = 

b1
b2
..
.





bm
a vektor neznámých



x = (x1 , x2 , . . . , xn ), a tedy xT = 

x1
x2
..
.



.

xn
2.1.3 Definice. Řešením soustavy lineárních rovnic (2.1) rozumíme každou n-tici
x = (x1 , x2 , . . . , xn ), pro niž je splněno všech m rovnic dané soustavy.
Podmínku řešitelnosti soustavy lineárních rovnic udává tzv. Frobeniova věta:
2.1.4 Věta. (Frobeniova)
Soustava (2.1) má řešení právě tehdy, když hodnost matice A je rovna hodnosti
matice R, tj. když h(A) = h(R).
Důkaz. viz např. v [Moučka1], str. 74.
2
Frobeniovu větu doplňuje tzv. věta o počtu řešení:
2.1.5 Věta. (O počtu řešení SLR)
a) Je-li h(A) = h(R) = n, má soustava (2.1) právě jedno řešení.
b) Je-li h(A) = h(R) = h < n, má soustava (2.1) nekonečně mnoho řešení závislých
na n − h parametrech.
c) Je-li h(A) < h(R), soustava (2.1) nemá řešení.
2.1 Soustava lineárních rovnic
11
2.1.6 Poznámka. V úlohách LP se nejčastěji budeme setkávat s případem b), kdy
soustava má nekonečně mnoho řešení.
2.1.7 Příklad. Řešte soustavu lineárních rovnic:
x1 − 2x2 + x3 + x4 = 1,
x1 − 2x2 + x3 − x4 = −1,
x1 − 2x2 + x3 + 5x4 = 5.
Řešení.

1
 1
1
SLR řešíme úpravou rozšířené matice na schodovitý tvar:
 

1
1 −2 1
1
1
−2 1
1
1
−2
1
1
1
−2 1 −1 −1  ∼  0
0 0 −2 −2  ∼
.
0
0 0 1 1
5
4
−2 1
5
0
0 0
4
Hodnost matice A je rovna hodnosti matice R a tato hodnost je menší než počet
proměnných (h(A) = h(R) = 2 < 4). Tedy soustava rovnic má nekonečně mnoho
řešení závislých na n − h = 4 − 2 = 2 parametrech. Zřejmě x4 = 1. Parametry s a t
pak můžeme volit např. tímto způsobem:
x2 = s, x3 = t, kde s, t ∈ R.
Potom x1 = 1 + 2x2 − x3 − x4 = 2s − t.
Řešení
x = (2s − t, s, t, 1), kde s, t ∈ R,
je tedy obecným řešením uvažované soustavy lineárních rovnic.
Chceme-li určit nějaké konkrétní řešení, zvolíme za s a t konkrétní čísla.
2.1.8 Příklad. Určete alespoň čtyři konkrétní řešení soustavy lineárních rovnic
z předchozího příkladu.
Řešení. Za parametry s a t stačí zvolit konkrétní reálná čísla, např.:
i) s = 2, t = 1 =⇒ x = (3, 2, 1, 1),
ii) s = 1, t = 0 =⇒ x = (2, 1, 0, 1),
iii) s = −1, t = 1 =⇒ x = (−3, −1, 1, 1),
iv) s = 0, t = 0 =⇒ x = (0, 0, 0, 1).
2.1.9 Definice. Řešení, které získáme z obecného řešení, v němž každý parametr
je roven některé proměnné, tím způsobem, že za všechny parametry volíme nuly, se
nazývá základní řešení. Neznámé, jež mají roli parametrů (v počtu n − h) se nazývají vedlejší proměnné, ostatní neznámé (v počtu h) se nazývají základní (bázické)
proměnné.
12
2 MATEMATICKÉ ZÁKLADY LP
2.1.10 Příklad. V příkladě 2.1.7 jsme za parametry volili neznámé x2 , x3 , a tedy
x2 , x3 jsou vedlejší proměnné, zatímco zbývající proměnné, tj. x1 , x4 , jsou základní.
Řešení iv) soustavy, tj. x = (0, 0, 0, 1), je základní řešení soustavy, protože jsme za parametry (tj. za vedlejší proměnné) zvolili nuly.
2.1.11 Definice. Jsou-li v základním řešení všechny základní proměnné nenulové,
nazývá se základní řešení nedegenerované. Je-li v základním řešení alespoň jedna
základní proměnná rovna nule, nazývá se základní řešení degenerované.
2.1.12 Příklad. Řešení iv) soustavy lineárních rovnic z úvodního příkladu tohoto
odstavce, tj. x = (0, 0, 0, 1), je degenerované, protože základní proměnná x1 = 0.
Často budeme pracovat se soustavou lineárních rovnic v tzv. kanonickém tvaru.
2.1.13 Definice. Řekneme, že soustava h lineárních rovnic je v kanonickém tvaru,
pokud její matice soustavy obsahuje všech h sloupců jednotkové matice řádu h, a to
bez ohledu na jejich pořadí.
Uvažujeme-li např. soustavu rovnic tvaru
+ a1,h+1 xh+1 + · · · + a1n xn = b1 ,
+ a2,h+1 xh+1 + · · · + a2n xn = b2 ,
..
..
..
..
.. ..
.
.
.
.
. .
x1
x2
...
(2.2)
xh + ah,h+1 xh+1 + · · · + ahn xn = bh ,
jsou zřejmé následující skutečnosti:
1. Jedná se o soustavu h lineárně nezávislých rovnic. Evidentně totiž nelze žádnou
z těchto rovnic vyjádřit jako lineární kombinaci ostatních rovnic.
2. Hodnost matice soustavy je h, hodnost rozšířené matice soustavy je také h, počet proměnných je n, a tedy, podle věty 2.1.5, existuje nekonečně mnoho řešení
závislých na n − h parametrech.
3. Z tohoto tvaru lze přímo určit základní řešení.
Volbou xh+1 = xh+2 = · · · = xn = 0 (vedlejší proměnné, tj. n − h parametrů)
získáme x1 = b1 , x2 = b2 , . . . , xh = bh (základní proměnné). Proto základní řešení
soustavy (2.2) je
x = (b1 , b2 , . . . , bh , 0, . . . , 0).
Matice soustavy (2.2) je



Ah = 

0 · · · 0 a1,h+1 · · · a1n
1 · · · 0 a2,h+1 · · · a2n
.. . . .. ..
..
.. .
.
.
0 0 · · · 1 ah,h+1 · · · ahn
1
0
..
.



.

(2.3)
2.1 Soustava lineárních rovnic
13
Obsahuje právě h různých základních jednotkových sloupcových vektorů (v (2.3) tvoří
jednotkovou submatici). Tyto sloupcové vektory určují základní proměnné. Uvedeného
principu využíváme při řešení soustavy (2.1). Matici A soustavy (2.1) převedeme pomocí elementárních ekvivalentních úprav na matici Ah soustavy, která je v kanonickém
tvaru. Obě soustavy jsou ekvivalentní a řešení (základní) určíme ze soustavy v kanonickém tvaru.
2.1.14 Příklad. Nalezněte všechna základní řešení SLR:
x1 + 11x2
+ 4x4 = 30,
2x1 + 8x2 − 2x3 + 2x4 = 18,
6x2 + 2x3 + 2x4 = 22.
Řešení. Vlastní řešení provedeme úplnou eliminací v tabulce 2.1.
Z.p.
x1
x1
x3
x1
x4
x3
x1
x4
x2
x3
x4
x2
x3
x1
x2
x1
x2
x3
x4
(1)
11
0
4
2
8
−2
2
0
6
2
2
1
11
0
4
0
−14 −2
−6
0
6
(2)
2
1
11
0
4
0
−8
0
(−4)
0
3
1
1
1
3
0
0
0
2
0
1
0
(1)
1
0
1
0
(−3)
0
0
0
−2
1
0
1
1
0
1
−3
0
1
0
2
(− 3 )
0
0
1
1
1
0
0
3
0
0
1
− 12
1
0
0
− 32
0
1
0
− 12
bi
30
18
22
30
−42
22
30
−20
11
10
5
6
−8
−7
6
8
3
− 35
− 10
3
Tab. 2.1 Určování základních řešení
v příkladu 2.1.14
7
2
5
2
5
2
(aij ) značí klíčový prvek, viz def. 2.1.15
x2 je vedlejší proměnná
volíme x2 = 0 ⇒ x(1) = (10, 0, 6, 5)
x3 je vedlejší proměnná
volíme x3 = 0 ⇒ x(2) = (−8, 6, 0, −7)
x1 je vedlejší proměnná
volíme x1 = 0 ⇒ x(3) = (0, − 10
, 8 , − 35 )
3 3
x4 je vedlejší proměnná
volíme x4 = 0 ⇒ x(4) = ( 52 , 52 , 72 , 0)
14
2 MATEMATICKÉ ZÁKLADY LP
Každý krok tabulky přísluší jiné soustavě lineárních rovnic, které jsou však ekvivalentní. V každém dalším kroku nově vytvoříme základní jednotkový sloupcový vektor
(hovoříme o vstupující proměnné, tj. proměnné, která vstupuje do množiny základních
proměnných).
Určili jsme všechna základní řešení soustavy tří lineárně nezávislých rovnic o čtyřech
neznámých. Jsou čtyři; je jich právě tolik, kolika způsoby lze vybrat trojici základních
proměnných (ze čtyř). Nebo jinak, je jich právě tolik, kolika způsoby lze vybrat jednu
vedlejší proměnnou (ze čtyř).
2.1.15 Definice. Klíčovým prvkem matice rozumíme zvolený nenulový prvek matice, pomocí něhož vhodnými řádkovými úpravami matice změníme tento prvek na
jedničku a vynulujeme všechny ostatní prvky matice ležící ve stejném sloupci jako
klíčový prvek.
2.1.16 Poznámka. Počet všech základních řešení soustavy m lineárně nezávislých
rovnic o n neznámých je nejvýše roven kombinačnímu číslu
n
n
n!
.
=
=
m!(n − m)!
m
n−m
2.1.17 Úkoly a problémy k modulu 2.1
1. Nalezněte všechna základní řešení SLR:
a)
x1 + x2 − 3x3 + x4 = 2,
4x1 + x2
+ x4 = 14,
x1 − 2x2 + x3 − x4 = 2.
b)
2x1 + 3x2 + x3 = 30,
x1 − 2x2 + 3x3 = 35.
c)
x1 + 3x2 = 18,
5x1 + 2x2 = 25,
x1 + x2 = 8.
d)
x1 + x2 = 10,
3x1 − x2 = 2,
x1 + 3x2 = 20.
e)
x1 + x2 + x3 + x4 = 16,
x2 + 2x3 + 3x4 = 20.
2. Nalezněte základní řešení soustavy lineárních rovnic s danou množinou M základních proměnných:
2.2 Soustava lineárních nerovnic
a)
M = {x1 , x2 , x3 },
x1 + 3x2 + 5x3 + 7x4 + 9x5 = 40,
x1 − x2 + x3 − x4 + x5 = 12,
2x1
+ x3
− x5 = 23.
b)
M = {x2 , x3 , x4 },
2x1 − 6x2 + x3 − x4
= −7,
−x1 + x2 − x3
+ x5 = −1,
x1 + 2x2 + x3 + 2x4 + x5 = 10.
c)
M = {x3 , x5 },
x1 − x2 − x3 − x4 + x5 = 4,
− x2 − 2x3 − 3x4 + 4x5 = 20.
d)
M = {x1 , x2 , x3 },
2x1 + x2 + 3x3 − x4 = 16,
x1 − x2 + x3 + x4 = 4,
x1 + x2 + x3
= 6.
Řešení.
1. a)
b)
c)
d)
e)
2.
2.2
a)
b)
c)
d)
15
(4, 4, 0, −6); (0, −12, 4, 26); ( 13
, 1, 43 , 0); (3, 0, 1, 2).
4
(11, 0, 8); (0, 5, 15); ( 165
, − 40
, 0).
7
7
(3, 5).
φ.
(−4, 20, 0, 0); (6, 0, 10, 0); ( 28
, 0, 0, 20
); (0, 12, 4, 0); (0, 14, 0, 2); (0, 0, 28, −12).
3
3
(9, 2, 5, 0, 0).
(0, 1, 2, 3, 0).
(0, 0, 2, 0, 6).
(0, 1, 5, 0), řešení je degenerované.
Soustava lineárních nerovnic
Úloha lineárního programování vede často právě k soustavě lineárních nerovnic (dále
jen SLN). Tu se naučíme převádět na soustavu lineárních rovnic. Už známým způsobem
potom k dané SLR najdeme SLR, která je v kanonickém tvaru a získáme tedy také
výchozí základní řešení.
2.2.1 Definice. Je-li A matice soustavy, xT vektor neznámých a bT vektor absolutních členů, rozumíme soustavou m lineárních nerovnic o n neznámých soustavu
A · xT R bT , tj. ai1 x1 + ai2 x2 + · · · + ain xn R bi , i = 1, 2, . . . , m.
(2.4)
Přitom symbol R zastupuje některý ze symbolů ≥, ≤, případně ještě obecněji jeden
ze symbolů ≥, =, ≤.
16
2 MATEMATICKÉ ZÁKLADY LP
2.2.2 Definice. Řešením soustavy lineárních nerovnic (2.4) rozumíme každou ntici x = (x1 , x2 , . . . , xn ), pro niž je splněno všech m nerovnic dané soustavy.
Nerovnice převádíme na rovnice pomocí tzv. doplňkových proměnných x0i ,
i = 1, 2, . . . , m. Doplňková proměnná vyjadřuje absolutní hodnotu rozdílu levé a
pravé strany (Li a Pi ) příslušné nerovnice, tj.
x0i = |Li − Pi |, i = 1, 2, . . . , m.
Z jejich významu je zřejmé, že musí splňovat podmínky nezápornosti
x0i ≥ 0, i = 1, 2, . . . , m.
(2.5)
Potom nerovnice (2.4) typu ≤ přejdou v rovnice
ai1 x1 + ai2 x2 + · · · + ain xn + x0i = bi , i = 1, 2, . . . , m,
(2.6)
a nerovnice (2.4) typu ≥ přejdou v rovnice
ai1 x1 + ai2 x2 + · · · + ain xn − x0i = bi , i = 1, 2, . . . , m.
(2.7)
Dostaneme soustavu m lineárních rovnic o m + n neznámých s podmínkami nezápornosti (2.5). Každému řešení SLN (2.4) odpovídá určité řešení příslušné SLR (2.6) nebo
(2.7), a naopak. Uvedené tvrzení je předmětem následující věty.
2.2.3 Věta. n-tice (x1 , x2 , . . . , xn ) je řešením soustavy lineárních nerovnic (2.4)
právě tehdy, když (n + m)-tice (x1 , x2 , . . . , xn , x01 , x02 , . . . , x0m ) je řešením soustavy
lineárních rovnic (2.6) nebo (2.7) (případně jejich kombinace), přičemž jsou splněny
podmínky nezápornosti(2.5).
2.2.4 Příklad. Soustavu lineárních nerovnic
7x1 + 5x2 ≤ 850,
2x1 + 2x2 ≤ 300
převeďte pomocí doplňkových proměnných na SLR a úplnou eliminací nalezněte takové
její základní řešení, že na pozici vedlejších proměnných budou doplňkové proměnné.
Řešení. SLN převedeme na SLR, tj. zavedeme doplňkové proměnné x01 ≥ 0 a x02 ≥ 0.
7x1 + 5x2 + x01
= 850,
0
2x1 + 2x2
+ x2 = 300.
SLR je už v kanonickém tvaru (základní proměnné jsou x01 a x02 ), přikročíme k tabulce,
2.2 Soustava lineárních nerovnic
17
v níž postupně určíme požadované řešení, viz tab. 2.2.
Z.p.
x1
x2
x01
x02
bi
x01
7
5
1
0
850
x02
x01
2
(2)
0
1
300
(2)
0
1
- 25
100
x2
1
1
0
150
x1
1
0
x2
0
1
1
2
- 21
1
2
- 45
7
4
50
100
x1 = x2 = 0 ⇒ x(1) = (0, 0; 850, 300)
x1 = x02 = 0 ⇒ x(2) = (0, 150; 100, 0)
x01 = x02 = 0 ⇒ x(3) = (50, 100; 0, 0)
Tab. 2.2 Řešení příkladu 2.2.4
V posledním kroku tabulky jsme získali požadované řešení, tj. x = (50, 100; 0, 0).
18
2 MATEMATICKÉ ZÁKLADY LP
2.2.5 Úkoly a problémy k modulu 2.2
1. SLN převeďte pomocí doplňkových proměnných na SLR a úplnou eliminací nalezněte takové její základní řešení, že na pozici vedlejších proměnných budou
pouze doplňkové proměnné.
a)
6x1 + 2x2 ≤ 12,
x1 + 5x2 ≤ 16.
b)
6x1 + 2x2 ≥ 12,
x1 + 5x2 ≥ 16.
c)
2x1 + x2 ≥ 10,
−x1 + 3x2 ≤ 9.
d)
x1 − x2 ≤ 3,
x1 + 2x2 ≥ 0.
e)
x1 + 11x2 + 4x3 ≤ 30,
x1 + 4x2 + x3 ≥ 9,
3x2 + x3 ≥ 11.
f)
x1 + x2 ≤ 6,
x1 − x2 ≤ 2,
−x1 + 2x2 ≤ 6.
Řešení.
1. a) (1, 3; 0, 0).
b) (1, 3; 0, 0).
c) (3, 4; 0, 0).
d) (2, −1; 0, 0).
e) (−8, 6, −7; 0, 0, 0).
f) (4, 2; 0, 0, 6), (2, 4; 0, 4, 0).
2.3 Shrnutí 2. kapitoly
19
2.3 Shrnutí 2. kapitoly
Klíčová slova:
Soustava lineárních rovnic, matice soustavy, rozšířená matice soustavy, řešitelnost a
počet řešení SLR, úplná eliminace, soustava lineárních nerovnic, převod SLN na SLR,
kanonický tvar SLR, základní a vedlejší proměnná, základní řešení, degenerované a
nedegenerované řešení.
Základní úlohy:
• Nalezení základního řešení pro zadanou množinu základních proměnných, či nalezení všech základních řešení dané soustavy lineárních rovnic.
• Převod soustavy lineárních nerovnic na soustavu lineárních rovnic zavedením doplňkových proměnných.
• Řešení soustav lineárních nerovnic.
Doporučená literatura pro hlubší studium:
[Kříž]:
[Moučka1]:
str. 5–21,
str. 72–90.
2.4 Test ke kapitole 2
1. Nalezněte základní řešení soustavy lineárních rovnic
2x1 + 18x2 + x3 + 4x4 = 20,
x1 + x2 + x3 + x4 = 10
s danou množinou M základních proměnných. V případě, že získané základní
řešení je degenerované, pak to uveďte.
a) M = {x1 , x3 }.
b) M = {x3 , x4 }.
2. Soustavu lineárních nerovnic
2x1 + 18x2 + x3 + 4x4 ≥ 20,
x1 + x2 + x3 + x4 ≤ 10
převeďte na soustavu lineárních rovnic. Nalezněte základní řešení příslušné soustavy lineárních rovnic s danou množinou M základních proměnných. V případě,
že získané základní řešení je degenerované či nepřípustné, pak to uveďte.
20
2 MATEMATICKÉ ZÁKLADY LP
a) M = {x1 , x3 }.
b) M = {x3 , x4 }.
c) M = {x4 , x01 }.
3. Soustavu lineárních podmínek
x1 + 2x2 ≤ 40,
3x1 + x2 ≤ 50,
x1 + x2 = 20
převeďte na soustavu lineárních rovnic. Nalezněte základní řešení příslušné soustavy lineárních rovnic s danou množinou M základních proměnných. V případě,
že získané základní řešení je degenerované či nepřípustné, pak to uveďte.
a) M = {x1 , x01 , x02 }.
b) M = {x2 , x01 , x02 }.
Řešení.
1. a) (10, 0, 0, 0), degenerované.
, 10 ).
b) (0, 0, 20
3 3
2.
a) (10, 0, 0, 0; 0, 0), degenerované.
b) (0, 0, 20
, 10 ; 0, 0).
3 3
c) (0, 0, 0, 10; 20, 0).
3.
a) (20, 0; 20, −10), nepřípustné.
b) (0, 20; 0, 30), degenerované, přípustné.
21
3
FORMULACE ÚLOH LINEÁRNÍHO PROGRAMOVÁNÍ
V tomto odstavci se zaměříme na formulování úloh lineárního programování, budeme
se zabývat sestavováním matematických modelů typických úloh, které se řeší metodami LP. Na konkrétních příkladech si ukážeme, co budeme rozumět úlohou výrobního
plánování, co směšovací úlohou a co rozdělovací úlohou, ale také to, jak matematický
model dané úlohy sestavit a co znamenají jednotlivé prvky tohoto modelu.
Cílem kapitoly je:
• naučit se vytvářet matematický model úlohy výrobního plánování,
• naučit se vytvářet matematický model směšovací úlohy,
• naučit se vytvářet matematický model rozdělovací úlohy,
• pochopit podstatu (typické vlastnosti, společné znaky, atd.) těchto jednotlivých typů úloh.
3.1
Úloha výrobního plánování
S úlohou tohoto typu jsme se již setkali v úvodní kapitole. Uveďme další příklad.
3.1.1 Příklad. Podnik vyrábí dva druhy výrobků V1 , V2 . Tabulka 3.1 udává spotřebu
surovin S1 a S2 v kg potřebných na výrobu 1 ks výrobku. Zisk z jednoho výrobku V1
je 18 Kč, zisk z jednoho výrobku V2 je 8 Kč. Dále je v tabulce uvedeno množství surovin, jimiž podnik disponuje. Úkolem je stanovit optimální výrobní plán, aby podnik
dosáhl maximálního možného zisku. Na tomto místě ovšem nebudeme úlohu řešit, ale
vytvoříme matematický model úlohy.
S1
S2
zisk
[kg/ks]
[kg/ks]
[Kč/ks]
V1
4
4
18
V2
2
1
8
Disponibilní množství
2 000
1 600
max
Tab. 3.1 Ekonomický model úlohy z příkladu 3.1.1
Řešení. Máme-li vytvořit matematický model, musíme vyjádřit problém matematickými prostředky. Nejprve je třeba nadefinovat proměnné :
xi značí počet výrobků Vi , i = 1, 2.
22
3 FORMULACE ÚLOH LP
Z významu proměnných je evidentní, proč musí být platit podmínky nezápornosti:
xi ≥ 0, i = 1, 2.
Vektor x = (x1 , x2 ) budeme nazývat vektorem výroby. Tento vektor jednoznačně určuje
výrobní plán podniku. Dále zformulujeme vlastní omezující podmínky. Výraz
4x1 + 2x2
vyjadřuje množství suroviny S1 (v kg) potřebné na výrobu x1 výrobků V1 a x2 výrobků V2 . Toto množství nemůže převýšit množství, které má podnik na dané období
k dispozici. Tedy:
4x1 + 2x2 ≤ 2 000.
Stejným způsobem lze získat i omezující podmínku týkající se spotřeby suroviny S2 :
4x1 + x2 ≤ 1 600.
Celkový zisk příslušející danému výrobnímu plánu je dán funkcí
z = z(x1 , x2 ) = 18x1 + 8x2 .
Podnik má dosáhnout maximálního zisku, tudíž účelová funkce je maximalizačního
typu. Píšeme
z = z(x1 , x2 ) = 18x1 + 8x2 −→ max.
Hovoříme o maximalizační úloze.
Získali jsme všechny prvky matematického modelu, zapíšeme ho souhrnně:
z = 18x1 + 8x2 −→ max,
4x1 + 2x2 ≤ 2 000,
4x1 + x2 ≤ 1 600,
x1 ≥ 0, x2 ≥ 0.
3.1.2 Úkoly a problémy k modulu 3.1
1. Závod vyrábí dva druhy výrobků V1 a V2 . Na jejich výrobu potřebuje surovinu S
a stojové zařízení Z. Pro plánovací období má k dispozici 1 500 kg suroviny a 240
strojových hodin na zařízení. Na výrobu 1 ks výrobku V1 je potřeba 10 kg suroviny S a 2 strojové hodiny na zařízení Z; na výrobu 1 ks výrobku V2 je potřeba
8 kg suroviny S a 1 strojová hodina na zařízení Z.
Zisk z jednoho výrobku V1 je 308 Kč, zisk z jednoho výrobku V2 je 214 Kč.
Úkolem je stanovit optimální výrobní plán, aby podnik dosáhl maximálního možného zisku.
Vytvořte matematický model úlohy.
3.2 Směšovací úloha
23
2. Podnik vyrábí výrobky A a B. Měsíčně má k dispozici 2 400 kg suroviny S a 3 200
hodin strojového času Z na zařízení a 1 200 hodin z časového fondu F pracovníků.
Na výrobu 1 ks výrobku A je potřeba 6 kg S, 4 h Z a 2 h F .
Na výrobu 1 ks výrobku B je potřeba 4 kg S, 8 h Z, 2 h F a 2 výrobky A. Výrobek A slouží jako polotovar (součástka) pro výrobek B.
Zisk z jednoho výrobku A je 80 Kč, zisk z jednoho výrobku B je 200 Kč.
Úkolem je stanovit optimální měsíční výrobní program s maximálním ziskem.
Vytvořte matematický model úlohy.
3. Podnik vyrábí tři druhy výrobků V1 , V2 a V3 ze tří různých surovin S1 , S2 a S3 ,
kterých má k dispozici po řadě 12, 21 a 12 tun.
Na výrobu 1 ks výrobku V1 je potřeba 1 kg suroviny S1 , 2 kg S2 a 0,5 kg S3 ;
na výrobu 1 ks výrobku V2 je potřeba 2 kg S2 a 2 kg S3 ;
na výrobu 1 ks výrobku V3 je potřeba 2 kg S1 a 3 kg S2 .
Zisk z jednoho výrobku V1 , resp. V2 , resp. V3 je 10, resp. 15, resp. 18 Kč.
Úkolem je stanovit optimální výrobní plán, aby podnik dosáhl maximálního možného zisku.
Vytvořte matematický model úlohy.
Řešení.
1.
z = 308x1 + 214x2 −→ max,
10x1 +
2x1 +
8x2 ≤ 1 500,
x2 ≤ 240,
x1 ≥ 0, x2 ≥ 0.
2.
z = 80x1 + 40x2 −→ max,
6x1 +
4x1 +
2x1 +
−x1 +
4x2
8x2
2x2
2x2
≤ 2 400,
≤ 3 200,
≤ 1 200,
≤
0,
x1 ≥ 0, x2 ≥ 0.
3.
z = 10x1 + 15x2 + 18x3 −→ max,
x1
+ 2x3 ≤ 12 000,
2x1 + 2x2 + 3x3 ≤ 21 000,
0,5x1 + 2x2
≤ 12 000,
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0.
3.2
Směšovací úloha
Podstatu směšovací úlohy, která je také známa pod názvem nutriční úloha, budeme
opět demonstrovat na příkladu.
24
3 FORMULACE ÚLOH LP
3.2.1 Příklad. Podnik má vytvořit krmnou směs, která by obsahovala alespoň
308 mg vápníku a alespoň 214 mg hořčíku. Používá přitom dvou typů krmiv.
Jeden kilogram krmiva K1 obsahuje 10 mg vápníku, 8 mg hořčíku a stojí 150 Kč.
Jeden kilogram krmiva K2 obsahuje 8 mg vápníku, 1 mg hořčíku a stojí 24 Kč.
Úkolem je stanovit složení výsledné krmné směsi tak, aby náklady na její pořízení byly
co nejmenší. Na tomto místě se omezíme na vytvoření matematického modelu.
Řešení.
Je výhodné všechny údaje přenést do přehledné tabulky:
K1
10
8
150
Ca
[mg/kg]
Mg
[mg/kg]
náklady [Kč/kg]
K2
8
1
24
Minimální množství
308
214
max
Tab. 3.2 Ekonomický model úlohy z příkladu 3.2.1
Vytvoříme matematický model této směšovací úlohy.
Proměnné xi značí množství (v kg) krmiva Ki ve výsledné směsi, i = 1, 2. Řešení je
pak představováno vektorem x = (x1 , x2 ), který budeme nazývat směšovacím vektorem.
I zde musí být splněny podmínky nezápornosti,
xi ≥ 0, i = 1, 2,
neboť nelze použít záporné množství krmiva.
Použije-li podnik x1 kg krmiva K1 a x2 kg krmiva K2 , bude množství vápníku a hořčíku
ve výsledné směsi:
Ca : 10x1 + 8x2 ,
Mg :
8x1 + x2 .
V souvislosti s minimálním požadovaným množstvím vápníku a hořčíku ve výsledné
směsi, mají vlastní omezující podmínky tvar:
Ca :
Mg :
10x1 + 8x2 ≥ 308,
8x1 + x2 ≥ 214.
Náklady z na pořízení směsi jsou dány účelovou funkcí
z = z(x1 , x2 ) = 150x1 + 24x2 .
Účelová funkce je minimalizačního typu.
Celkově matematický model úlohy je:
z = 150x1 + 24x2 −→ min,
10x1 + 8x2 ≥ 308,
8x1 + x2 ≥ 214,
x1 ≥ 0, x2 ≥ 0.
3.2 Směšovací úloha
25
3.2.2 Úkoly a problémy k modulu 3.2
1. Podnik má ze surovin S1 a S2 co nejlevněji vyrobit směs, která by obsahovala
alespoň 160 g vitamínu A a alespoň 500 g vitamínu C.
1 kg suroviny S1 obsahuje 1 g vitamínu A a 2 g vitamínu C a stojí 30 Kč;
1 kg suroviny S2 obsahuje 1 g vitamínu A a 5 g vitamínu C a stojí 50 Kč.
Úkolem je stanovit optimální směšovací vektor.
Vytvořte matematický model úlohy.
2. Metalurgický závod má vyrobit nejméně 4 000 kg zinku Zn a nejméně 3 000 kg
cínu Sn. K dispozici má tři druhy rud.
1 tuna rudy A obsahuje 10 kg Zn a 6 kg Sn a stojí 200 Kč;
1 tuna rudy B obsahuje 2 kg Zn a 6 kg Sn a stojí 150 Kč;
1 tuna rudy C obsahuje 12 kg Zn a 4 kg Sn a stojí 250 Kč.
Úkolem je stanovit v jakém množství je třeba jednotlivé druhy rud použít, aby
celková nákupní cena rud byla minimální.
Vytvořte matematický model úlohy.
3. Úkolem je ze surovin S1 a S2 co nejlevněji vytvořit směs o celkové hmotnosti
6 kg tak, aby tato směs obsahovala alespoň 8 g hořčíku a alespoň 60 g vápníku,
přičemž
1 kg suroviny S1 obsahuje 1 g hořčíku, 12 g vápníku a jeho cena je 12 Kč;
1 kg suroviny S2 obsahuje 1,5 g hořčíku, 10 g vápníku a jeho cena je 20 Kč.
Vytvořte matematický model úlohy.
Řešení.
1.
z = 30x1 + 50x2 −→ min,
x1 + x2 ≥ 160,
2x1 + 5x2 ≥ 500,
x1 ≥ 0, x2 ≥ 0.
2.
z = 200x1 + 150x2 + 250x3 −→ min,
10x1 +
6x1 +
2x2 + 12x3 ≥ 4 000,
6x2 + 4x3 ≥ 3 000,
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0.
3.
z = 12x1 + 20x2 −→ min,
x1 + x2 = 6,
x1 + 1,5x2 ≥ 8,
12x1 + 10x2 ≥ 60,
x1 ≥ 0, x2 ≥ 0.
26
3.3
3 FORMULACE ÚLOH LP
Rozdělovací úloha
I tento typ úlohy a tvorbu matematického modelu si ukážeme na příkladu.
3.3.1 Příklad. Uvažujme, že máme k dispozici dostatečné množství základních lan
o délce 32 m. K dalšímu použití potřebujeme alespoň 12 ks 20m lan, alespoň 20 ks 11m
lan a alespoň 26 ks 6m lan. Úkolem je stanovit tzv. optimální skladbu řezných plánů
vzhledem k minimálnímu odpadu. Sestavíme matematický model úlohy.
Řešení. Nejprve musíme jednotlivé řezné plány (tj. způsoby, jimiž lze rozřezat základní lana délky 32 m na kusy délky 20 m, 11 m a 6 m ) stanovit a určit kolik
základních lan každým z těchto způsobů rozřežeme. Sestavíme tabulku řezných plánů,
viz tab. 3.3.
32 m
20 m
11 m
6m
odpad [m]
I.
1
1
0
1
Řezný plán
II. III. IV.
1
0
0
0
2
1
2
1
3
0
4
3
V.
0
0
5
2
Požadované
množství
12
20
26
min
Tab. 3.3 Tabulka řezných plánů z příkladu 3.3.1
Řezný plán I. znamená, že ze základního lana délky 32 m nařežeme 1 ks 20 m
dlouhého lana, 1 ks 11 m dlouhého lana a zbude odpad délky 1 m. Význam ostatních
řezných plánů můžeme interpretovat analogicky.
Vytvoříme matematický model této rozdělovací úlohy.
Proměnné xi značí počet základních 32 m dlouhých lan rozřezaných podle i-tého řezného plánu, i = 1, 2, . . . , 5. Řešení je pak představováno vektorem x = (x1 , x2 , x3 , x4 , x5 ),
který budeme nazývat rozdělovací vektor. I zde musí být splněny podmínky nezápornosti,
xi ≥ 0, i = 1, 2, . . . , 5,
neboť žádným ze způsobů nelze rozřezat záporné množství lan.
Rozřežeme-li x1 lan podle řezného plánu I., . . . , x5 lan podle řezného plánu V., nařežeme
x1 + x2
ks 20 m dlouhých lan,
x1
+ 2x3 + x4
ks 11 m dlouhých lan,
2x2 + x3 + 3x4 + 5x5 ks 6 m dlouhých lan,
a zbude odpad s celkovou délkou (v metrech)
z = x1 + 4x3 + 3x4 + 2x5 .
3.3 Rozdělovací úloha
27
Celkově matematický model úlohy je:
z = x1
+ 4x3 + 3x4 + 2x5 −→ min,
x1 + x2
≥ 12,
x1
+ 2x3 + x4
≥ 20,
2x2 + x3 + 3x4 + 5x5 ≥ 26,
xi ≥ 0, i = 1, 2, . . . , 5.
3.3.2 Příklad. Modifikujme předchozí příklad následovně. Všechny předpoklady i
požadavky zůstávají stejné, pouze změníme kritérium optimality. Nechť je nyní cílem
určit optimální skladbu řezných plánů z hlediska minimálního počtu rozřezaných lan
o základní délce 32 m. Sestavíme matematický model úlohy LP.
Řešení. Matematický model se od předchozího bude lišit jen tvarem účelové funkce:
z = x1 + x2 + x3 + x4 + x5 −→ min.
3.3.3 Úkoly a problémy k modulu 3.3
1. Podnik řeže ze základních tyčí délky 80 cm tyče délek 50 cm, 40 cm a 25 cm. Jejich
minimální požadovaná množství jsou po řadě 50 ks, 80 ks a 95 ks.
Úkolem je stanovit optimální skladbu řezných plánů z hlediska minimalizace odpadu.
Vytvořte matematický model úlohy.
2. Podnik má dostatečnou zásobu základních lan délky 52 m. Je potřeba z nich nařezat alespoň 60 kusů lan délky 18 m a alespoň 100 kusů lan délky 11 m.
Úkolem je stanovit optimální skladbu řezných plánů z hlediska minimalizace odpadu.
Vytvořte matematický model úlohy.
3. K dispozici jsou tyče základní délky 1,5 m. Je potřeba z nich nařezat alespoň
120 ks délky 90 cm, alespoň 80 ks délky 60 cm a alespoň 110 ks délky 45 cm.
Úkolem je stanovit optimální skladbu řezných plánů z hlediska minimalizace odpadu.
Vytvořte matematický model úlohy.
28
3 FORMULACE ÚLOH LP
Řešení.
1.
+ 15x3 + 5x4 −→ min,
z = 5x1
x1
2x2 +
x1
+
≥ 50,
x3
≥ 80,
x3 + 3x4 ≥ 95,
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0.
2.
z = 5x1 + x2 + 8x3 −→ min,
2x1 + x2
≥ 60,
x1 + 3x2 + 4x3 ≥ 100,
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0.
3.
z=
15x2 + 30x3
x1 +
x1
+ 15x5 −→ min,
≥ 120,
+ 2x3 + x4
≥ 80,
x2
+ 2x4 + 3x5 ≥ 110,
x2
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0, x5 ≥ 0.
3.4
Obecná úloha lineárního programování
Jak již bylo uvedeno, soustavu lineárních nerovnic lze pomocí doplňkových proměnných
převést na soustavu lineárních rovnic.
Obecně jde o to, nalézt řešení soustavy lineárních rovnic, splňující podmínky nezápornosti, takové, aby lineární účelová funkce nabyla svého maxima, resp. minima (podle
typu úlohy).
Úlohu LP lze obecně matematicky vyjádřit následovně:
Hledáme řešení soustavy m rovnic o n neznámých (m < n)
a11 x1 + a12 x2 + . . . + a1n xn = b1 ,
a21 x1 + a22 x2 + . . . + a2n xn = b2 ,
.. ..
.. ..
..
..
..
. .
. .
.
.
.
am1 x1 + am2 x2 + . . . + amn xn = bm ,
takové, aby byly splněny podmínky nezápornosti, tj.
xi ≥ 0, i = 1, 2, . . . , n,
a aby účelová funkce
z = c1 x1 + c2 x 2 + · · · + cn xn
nabyla maxima, resp. minima.
Příslušná SLR má nekonečně mnoho řešení (viz Věta 2.1.4 – Frobeniova, m < n).
Smysl mají pouze přípustná řešení (tj. řešení, splňující navíc i podmínky nezápornosti).
3.4 Obecná úloha LP
29
Přípustné řešení, pro něž účelová funkce nabývá maximum (resp. minimum) se nazývá
optimální řešení.
3.4.1 Věta. (Základní věta LP)
Úloha LP má optimální řešení ⇔ úloha LP má základní optimální řešení.
3.4.1 Důsledek. Při hledání optimálního řešení se můžeme omezit jen na základní
řešení, kterých je konečně mnoho. Smysl mají jen základní přípustná řešení (tj. základní
řešení splňující navíc i podmínky nezápornosti).
30
3 FORMULACE ÚLOH LP
3.5 Shrnutí 3. kapitoly
Klíčová slova:
Formulace úloh LP, ekonomický model úlohy, matematický model úlohy, proměnná,
vlastní omezující podmínky, podmínky nezápornosti, účelová funkce, úloha výrobního
plánování, směšovací úloha, rozdělovací úloha, obecná úloha LP.
Základní úlohy:
• Najít matematický model úlohy LP zadané slovně.
• Pochopit princip úloh výrobního plánování, směšovacích úloh, rozdělovacích úloh
a poznat společné prvky a rozdílné prvky těchto typů úloh LP.
Doporučená literatura pro hlubší studium:
[Holoubek]:
[Jablonský]:
[Kříž]:
[Mošová]:
str.
str.
str.
str.
11–18,
25–40,
22–26,
5–12.
3.6 Test ke kapitole 3
1. K dispozici jsou cívky s elektrickým kabelem délky 108 m. Pro další použití z nich
podnik potřebuje nařezat alespoň 30 ks kabelů délky 50 m, alespoň 60 ks délky
40 m a alespoň 150 ks délky 30 m. Sestavte matematický model rozdělovacího
problému, v němž cílem bude:
a) minimalizace odpadu.
b) minimalizace počtu rozřezaných cívek.
Řešení.
1. a)
z = 8x1 + 18x2 + 28x3 + 28x4 + 8x5 + 18x6 −→ min,
2x1 +
x2 +
x2
≥ 30,
+ 2x4 + x5
≥ 60,
x3
+ 2x5 + 3x6 ≥ 150,
x3
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0, x5 ≥ 0, x6 ≥ 0.
b)
z = x1 + x2 + x3 + x4 + x5 + x6 −→ min,
2x1 + x2 + x3
≥ 30,
x2
+ 2x4 + x5
≥ 60,
x3
+ 2x5 + 3x6 ≥ 150,
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0, x5 ≥ 0, x6 ≥ 0.
31
4
GRAFICKÁ METODA
Cílem kapitoly je:
• naučit se řešit úlohy LP grafickou metodou.
4.1
Grafická metoda řešení úloh lineárního programování
Úlohy LP, v níž vystupují jen dvě proměnné lze řešit graficky. Přitom každý bod
v rovině – souřadnice x1 , x2 – představuje právě jedno řešení.
4.1.1 Poznámka. V principu lze grafickou metodu použít i v případě tří proměnných
(každé řešení je pak představováno nějakým bodem prostoru). Už si tedy nevystačíme
papírem, tužkou a pravítkem, museli bychom modelovat trojrozměrně, což zpravidla
činí praktické potíže.
Grafické řešení úlohy lineárního programování (se dvěmi proměnnými x1 , x2 ) se odehrává v kartézské souřadnicové soustavě (dimenze dvě), kde jednotlivé souřadnice představují právě hodnoty jednotlivých proměnných. Osy jsou proto označené jmény proměnných, v našem případě x1 , x2 . Nejprve je potřeba znázornit množinu všech přípustných řešení XP . Tato množina je průnikem množiny řešení jednotlivých omezujících
podmínek (vlastní omezující podmínky a podmínky nezápornosti). Přitom množinou
řešení vyhovující lineární nerovnici je polorovina a množinou řešení vyhovující lineární rovnici je přímka. Průnikem těchto množin je buď ohraničená množina – v tom
případě je to konvexní k-úhelník, k ≤ m + n, kde m je počet vlastních omezujících podmínek, n je počet proměnných, nebo neohraničená konvexní množina, mající k hran a
k − 1 vrcholů.
Budeme uvažovat maximalizační úlohu. Potom hledáme takové přípustné řešení
(x1 , x2 ) ∈ XP , aby hodnota účelové funkce z = z(x1 , x2 ) = c1 x1 + c2 x2 byla maximální
možná. Představme si množinu všech přímek typu
c1 x1 + c2 x2 = s, s ∈ R.
Jedná se o rovnoběžky, všechny s normálovým vektorem n = (c1 , c2 ). Body (x1 , x2 )
na každé takové přímce mají stejnou hodnotu účelové funkce
z = c1 x1 + c2 x2 = s.
Stačí vzít přímku kolmou na normálový vektor n a rovnoběžně ji ve směru vektoru n
posunout do místa posledního průniku s množinou přípustných řešení XP . Tento „poslední průnikÿ odpovídá množině všech optimálních řešení Xopt . Je zřejmé, že tato
množina může být prázdná, jednoprvková nebo obsahovat nekonečně mnoho prvků.
32
4 GRAFICKÁ METODA
4.1.2 Poznámka. Případ, kdy množina Xopt obsahuje nekonečně mnoho prvků nastává ve dvou kvalitativně odlišných případech:
1. „posledním průnikemÿ je úsečka. Krajní body úsečky potom odpovídají dvěma
základním optimálním řešením úlohy.
2. „posledním průnikemÿ je polopřímka. Krajní bod polopřímky potom odpovídá
jedinému základnímu optimálnímu řešení úlohy.
4.1.3 Poznámka. Hodnota účelové funkce z = z(x1 , x2 ) = c1 x1 +c2 x2 roste ve směru
normálového vektoru n = (c1 , c2 ). V případě minimalizační úlohy proto „poslední
průnikÿ kolmice na vektor n a množiny XP hledáme co nejdále proti směru vektoru n.
4.1.4 Poznámka. Grafická metoda využívá přímých výpočtů, např. souřadnice bodu
(tj. hodnoty proměnných v daném řešení) se určí řešením soustavy dvou rovnic (rovnice
přímek protínajících se v daném bodě) o dvou neznámých.
4.1.5 Příklad. Grafickou metodou řešte úlohu LP zadanou matematickým modelem:
7x1 + 5x2 ≤ 850,
2x1 + 2x2 ≤ 300,
z = 7x1 + 6x2 −→ max,
x1 ≥ 0, x2 ≥ 0.
Řešení. Nejprve nalezneme množinu XP všech přípustných řešení. Řešení vyhovující
omezující podmínce 7x1 + 5x2 ≤ 850 vyplní v grafu polorovinu s hraniční přímkou
, 0] (dvěma body
7x1 +5x2 = 850. Tato přímka musí procházet např. body [0, 170] a [ 850
7
je přímka určena jednoznačně). Jelikož každá přímka rozděluje rovinu na dvě opačné
poloroviny, musíme rozhodnout, která z nich odpovídá nerovnici 7x1 + 5x2 ≤ 850.
K tomu stačí vzít libovolný bod, který neleží na dané přímce (a tedy 7x1 +5x2 6= 850) a
zjistit, zda pro něj je nerovnice splněna. Pokud ano, daný bod leží v hledané polorovině;
pokud ne, hledanou polorovinou je polorovina opačná. S výhodou použijeme počátek,
tj. bod O = [0, 0]. Omezující podmínka 7x1 + 5x2 ≤ 850 je splněna (0 ≤ 850). Počátek
tedy leží v hledané polorovině (1). Tuto polorovinu vyznačíme v grafu jejím označením
a šipkou vycházející z hraniční přímky dané poloroviny.
Stejným postupem najdeme i polorovinu (2) všech řešení splňujících podmínku
druhou, tj. 2x1 + 2x2 ≤ 300. Podobně najdeme i poloroviny (3) a (4) odpovídající
podmínkám nezápornosti.
Řešení je přípustné právě tehdy, když splňuje všechny vlastní omezující podmínky a
podmínky nezápornosti. Proto množinu XP všech přípustných řešení získáme průnikem
, 0],
těchto čtyř polorovin. Množina XP je čtyřúhelník OABC, kde O = [0, 0], A = [ 850
7
B = [50, 100] a C = [0, 150]. Na obr. 4.1 je množina XP vyznačena šedou barvou.
Přitom např. souřadnice bodu B jsme získali řešením soustavy rovnic
7x1 + 5x2 = 850,
2x1 + 2x2 = 300
4.1 Grafická metoda řešení úloh LP
33
(bod B leží současně na hraničních přímkách polorovin (1) a (2)).
Obr. 4.1 Řešení úlohy 4.1.5 grafickou metodou
Potřebujeme najít optimální řešení, tj. takové přípustné řešení, které maximalizuje
hodnotu účelové funkce. Z toho důvodu vyznačíme normálový vektor n = (7, 6), jež
přísluší dané účelové funkci (vzhledem k vyšší přehlednosti je v obr. 4.1 vyznačen jeho
desetinásobek). Najdeme kolmici na vektor n, která je co nejdále ve směru vektoru n
a přitom má neprázdný průnik s množinou XP . Tuto přímku vyznačíme – v grafu je
označena symbolem zmax . Vyznačíme také „poslední průnikÿ (tj. průnik přímky zmax
s množinou XP ). Je to bod B. Množina všech optimálních řešení je tedy jednoprvková,
píšeme
Xopt = B = [50, 100].
Maximální hodnota účelové funkce je
zmax = z(B) = 7 · 50 + 6 · 100 = 950.
34
4 GRAFICKÁ METODA
4.1.6 Příklad. Grafickou metodou řešte úlohu LP zadanou matematickým modelem:
7x1 + 5x2 ≤ 850,
2x1 + 2x2 ≤ 300,
z = 2x1 + 7x2 −→ max,
x1 ≥ 0, x2 ≥ 0.
Řešení. Vzhledem k tomu, že omezující podmínky i podmínky nezápornosti jsou
stejné jako v příkladu 4.1.5, je stejná i množina XP všech přípustných řešení úlohy.
Obr. 4.2 Řešení úlohy 4.1.6 grafickou metodou
Rozdílná je účelová funkce. Zkonstruujeme normálový vektor n = (2, 7) příslušný
dané účelové funkci, viz obr. 4.2. I zde najdeme kolmici na vektor n, která má „posledníÿ (ve směru vektoru n) neprázdný průnik s množinou XP . Dostaneme tak:
Xopt = C = [0, 150], zmax = z(C) = 2 · 0 + 7 · 150 = 1 050.
4.1 Grafická metoda řešení úloh LP
35
4.1.7 Poznámka. Na předchozích dvou příkladech je názorně vidět, že účelová
funkce má podstatný vliv na optimální řešení.
36
4 GRAFICKÁ METODA
4.2 Shrnutí 4. kapitoly
Klíčová slova:
Grafická metoda, přímka a polorovina v rovině, průnik konvexních množin v rovině,
množina všech přípustných řešení XP , normálový vektor n, množina všech optimálních
řešení Xopt .
Základní úlohy:
• Najít všechna optimální řešení úlohy LP grafickou metodou.
Doporučená literatura pro hlubší studium:
[Holoubek]:
[Jablonský]:
[Kříž]:
[Mošová]:
str.
str.
str.
str.
19–26,
40–50,
27–35,
13–23.
4.3 Test ke kapitole 4
1. Grafickou metodou vyřešte úlohu 1. z úkolů 3.1.2 na straně 22.
2. Grafickou metodou vyřešte úlohu 2. z úkolů 3.1.2 na straně 22.
3. Grafickou metodou vyřešte úlohu 1. z úkolů 3.2.2 na straně 25.
4. Grafickou metodou vyřešte úlohu 3. z úkolů 3.2.2 na straně 25.
Řešení.
1. Xopt = [70, 100], zmax = 42 960 Kč.
2. Xopt = [400, 0], zmax = 32 000 Kč.
3. Xopt = [100, 60], zmin = 6 000 Kč.
4. Xopt = [2, 4], zmin = 104 Kč.
37
5
SIMPLEXOVÁ METODA
Cílem studia kapitoly je:
• seznámit se s postupem nalezení výchozího základního přípustného řešení
úlohy LP,
• zavést simplexovou tabulku a naučit se v ní orientovat,
• umět rozhodnout, zda dané řešení je či není optimální,
• umět najít lepší základní řešení v případě, že dané řešení není optimální,
• naučit se řešit úlohy LP simplexovou metodou.
Simplexová metoda je výpočetní postup pro určení optimálního řešení úloh lineárního
programování. Algoritmus simplexové metody je schematicky znázorněn na obr. 5.1.
Obr. 5.1 Schéma algoritmu simplexové metody
Při řešení úlohy LP vždy nejprve získáme výchozí základní přípustné řešení. K tomu
je potřeba mít omezující podmínky úlohy ve tvaru soustavy lineárních rovnic v kanonickém tvaru. Jelikož omezující podmínky v úloze LP bývají zpravidla ve tvaru nerovnic,
je prvním krokem převod této soustavy lineárních nerovnic (SLN) na soustavu lineárních rovnic (SLR). Pokud tato soustava není v kanonickém tvaru, tak ji na kanonický
tvar převedeme. Obdržením SLR v kanonickém tvaru jsme vlastně současně získali
výchozí základní přípustné řešení příslušné úlohy. Testem optima lze zjistit, zda dané
základní řešení je či není optimální. V případě, že výchozí základní přípustné řešení je
38
5 SIMPLEXOVÁ METODA
optimální, našli jsme optimální řešení a algoritmus končí. V opačném případě nalezneme lepší základní přípustné řešení úlohy, tj. řešení s vyšší hodnotou účelové funkce
u maximalizační úlohy, resp. řešení s nižší hodnotou účelové funkce u minimalizační
úlohy. Na toto lepší řešení opět aplikujeme test optima, atd. Protože základních řešení
je konečný počet, viz 2.1.16 Poznámka, po konečném počtu kroků dospějeme k optimálnímu řešení. Podrobněji se jednotlivým částem simplexového algoritmu věnují příslušné
moduly této kapitoly.
5.1
Nalezení výchozího řešení
Nejprve je potřeba nalézt výchozí základní přípustné řešení. Tzn., že omezující podmínky se vyjádří ve formě soustavy lineárních rovnic v kanonickém tvaru s nezápornou
pravou stranou všech rovnic, tj. bi ≥ 0, i = 1, 2, . . . , n.
Jak toho dosáhnout, s ohledem na konkrétní tvar omezujících podmínek, je obsahem
následující diskuse:
1. Je-li některé bi < 0, i = 1, 2, . . . , n, pak danou rovnici či nerovnici násobíme
číslem (−1). Získáme tak u všech omezujících podmínek nezáporné pravé strany,
tj. bi ≥ 0, i = 1, 2, . . . , n.
2.a) Jestliže omezující podmínky jsou ve tvaru Ax ≤ b, bi ≥ 0, i = 1, 2, . . . , m, pak
soustavu lineárních nerovnic převedeme pomocí doplňkových proměnných x0i ≥
≥ 0, i = 1, 2, . . . , n na soustavu lineárních rovnic, která již je v kanonickém tvaru.
Získáme
a11 x1 + a12 x2 + . . . + a1n xn + x01
= b1 ,
0
= b2 ,
a21 x1 + a22 x2 + . . . + a2n xn
+ x2
.. ..
.. ..
..
..
..
..
.
. .
. .
.
.
.
am1 x1 + am2 x2 + . . . + amn xn
+ x0m = bm .
Odtud dostáváme výchozí základní řešení ve tvaru
x = (x1 , x2 , . . . , xn ; x01 , x02 , . . . , x0m ) = (0, 0, . . . , 0; b1 , b2 , . . . , bm ).
Toto řešení je přípustné, neboť bi ≥ 0, i = 1, 2, . . . , m (vyhovuje podmínkám
nezápornosti).
2.b) Jestliže alespoň jedna omezující podmínka je ve tvaru
ai1 x1 + ai2 x2 + · · · + ain xn ≥ bi , bi ≥ 0,
pak soustavu lineárních nerovnic převedeme na soustavu lineárních rovnic, která
však není v kanonickém tvaru, např.:
x1 − 2x2 ≥ 5,
2x1 + 3x2 ≥ 2,
x1 ≥ 0, x2 ≥ 0;
−→
x1 − 2x2 −x01
2x1 + 3x2
−x02
= 5,
= 2,
x1 ≥ 0, x2 ≥ 0, x01 ≥ 0, x02 ≥ 0.
5.1 Nalezení výchozího řešení
39
Rovnice nelze násobit číslem (−1), protože bychom obdrželi zápornou pravou
stranu příslušné rovnice (příslušné základní řešení by nebylo přípustné). Výchozí
přípustné řešení (soustavu lineárních rovnic v kanonickém tvaru) lze získat pomocí metody umělé báze, tj. zavedením pomocných proměnných, viz kap. 6.
Simplexová tabulka
V okamžiku, kdy omezující podmínky spolu s anulovanou účelovou funkcí tvoří soustavu lineárních rovnic v kanonickém tvaru, můžeme přikročit k provádění vlastního
simlexového algoritmu. To realizujeme v tzv. simplexové tabulce. Samotnou simplexovou tabulku si popíšeme na následujícím, motivačním, příkladu.
5.1.1 Příklad. Uvažujme úlohu LP zadanou tímto matematickým modelem
2x1 + 5x2 ≤ 1000,
4x1 + x2 ≤ 1100,
z = 3x1 + 2x2 −→ max,
x1 ≥ 0, x2 ≥ 0.
Pomocí doplňkových proměnných a anulováním účelové funkce získáme soustavu tří
lineárních rovnic (o pěti neznámých), která již je v kanonickém tvaru.
= 1 000,
2x1 + 5x2 +x01
4x1 + x2
+x02 = 1 100,
z −3x1 − 2x2
=
0 (max),
x1 ≥ 0, x2 ≥ 0, x01 ≥ 0, x02 ≥ 0.
Ze soustavy (5.1) lze získat výchozí základní přípustné řešení ve tvaru
x = (0, 0; 1 000, 1 100).
Soustavu (5.1) přepíšeme do simplexové tabulky.
Z.p.
x01
x02
z
x1
2
4
−3
x2
5
1
−2
x01
1
0
0
x02
0
1
0
bi
1 000
1 100
0
p=
bi
aik
max
Tab. 5.1 Simplexová tabulka k příkladu 5.1.1
Označme a pojmenujme nyní jednotlivé části tabulky:
(1) 1. sloupec, označený Z.p., je sloupec základních proměnných;
(5.1)
40
5 SIMPLEXOVÁ METODA
2 5 1 0
(2) prvky
tvoří příslušnou matici soustavy;
4 1 0 1
1 000
(3) sloupec
je sloupec absolutních členů bi ;
1 100
(4) poslední sloupec, tj. zde dvě prázdná pole, označený p =
klíčového řádku;
bi
,
aik
slouží pro určení
(5) poslední řádek, tj. (−3 −2 0 0), je řádek koeficientů anulované účelové funkce;
(6) část představovaná jediným políčkem ve sloupci bi a řádku z, představuje hodnotu
účelové funkce příslušné danému základnímu přípustnému řešení. Zde je z = 0.
5.1.2 Úkoly a problémy k modulu 5.1
1. Nalezněte výchozí základní přípustné řešení úlohy 1. z úkolů 3.1.2 na straně 22.
2. Nalezněte výchozí základní přípustné řešení úlohy 2. z úkolů 3.1.2 na straně 22.
3. Nalezněte výchozí základní přípustné řešení úlohy 3. z úkolů 3.1.2 na straně 22.
Řešení.
1. x = (0, 0; 1 500, 240), z(x) = 0.
2. x = (0, 0; 2 400, 3 200, 1 200, 0), z(x) = 0.
3. x = (0, 0, 0; 12 000, 21 000, 12 000), z(x) = 0.
5.2
Test optimálnosti řešení
1. U MAXIMALIZAČNÍCH ÚLOH platí:
Je-li alespoň u jedné vedlejší proměnné xj koeficient cj v řádku (5) účelové funkce
ZÁPORNÝ, je možné hodnotu z účelové funkce zvětšit, tzn. že řešení ještě není
optimální. Je-li v řádku (5) záporných koeficientů více, vybereme nejmenší z nich.
Jsou-li všechny koeficienty u vedlejších proměnných v řádku (5) účelové funkce
nezáporné, je nalezené řešení optimální.
2. U MINIMALIZAČNÍCH ÚLOH platí:
Je-li alespoň u jedné vedlejší proměnné xj koeficient cj v řádku (5) účelové funkce
KLADNÝ, je možné hodnotu z účelové funkce snížit, tzn. že řešení ještě není
optimální. Je-li v řádku (5) kladných koeficientů více, vybereme největší z nich.
Jsou-li všechny koeficienty u vedlejších proměnných v řádku (5) účelové funkce
nekladné, je nalezené řešení optimální.
5.3 Zlepšování řešení
41
Tímto způsobem stanovíme tu proměnnou xj , kterou musíme mezi základní proměnné
zařadit, tj. tzv. vstupující proměnnou. Takto určíme klíčový sloupec.
5.2.1 Úkoly a problémy k modulu 5.2
1. Zjistěte, zda výchozí základní přípustné řešení úlohy 1. z úkolů 5.1.2 na straně 40
je optimální.
2. Zjistěte, zda výchozí základní přípustné řešení úlohy 2. z úkolů 5.1.2 na straně 40
je optimální.
3. Zjistěte, zda výchozí základní přípustné řešení úlohy 3. z úkolů 5.1.2 na straně 40
je optimální.
Řešení.
1. Není optimální.
2. Není optimální.
3. Není optimální.
5.3
Zlepšování řešení
V předchozí části jsme určili, kterou proměnnou musíme mezi základní proměnné zařadit, aby se hodnota účelové funkce zlepšila. Nyní musíme rozhodnout, kterou ze
základních proměnných vyloučíme.
Zjistíme, ve kterých rovnicích má zařazovaná proměnná kladné koeficienty, tj.
vybereme všechny kladné koeficienty v klíčovém sloupci. Těmito koeficienty aik ,
aik > 0, dělíme absolutní členy bi a podíly zapisujeme do sloupce (4) v simplexové tabulce. Vybereme minimum ze všech podílů p = abiki pro aik > 0. Rovnice, v níž
je tento podíl nejmenší obsahuje vylučovanou proměnnou.
5.3.1 Poznámka. Postup pro určení vylučované proměnné je stejný u maximalizačních i minimalizačních úloh.
Výměnu zařazované a vylučované proměnné provedeme úplnou eliminací. Na závěr
kapitoly shrneme postup simplexové metody.
1. Určíme klíčový sloupec, tj. zařazovanou proměnnou, podle toho, který záporný
(u max. úloh), resp. kladný (u min. úloh), koeficient v řádku (5) má největší
absolutní hodnotu.
2. Určíme klíčový řádek, tj. vylučovanou proměnnou, podle toho, který podíl p =
pro aik > 0 je ve sloupci (4) nejmenší.
bi
aik
42
5 SIMPLEXOVÁ METODA
3. Určíme klíčový prvek (pivot) jako průsečík klíčového řádku a klíčového sloupce.
4. Provedeme úplnou eliminaci. Tzn., dělíme všechny prvky klíčového řádku klíčovým prvkem, prvky klíčového sloupce nahradíme příslušným základním sloupcovým jednotkovým vektorem, ostatní prvky dopočítáme (např. podle křížového
pravidla).
Celý postup opakujeme tak dlouho, až budou v řádku (5) všechny koeficienty nezáporné (u max. úloh), resp. nekladné (u min. úloh). V tom případě má úloha optimální
řešení. V případě, že nelze určit klíčový řádek, tj. všechny koeficienty v klíčovém sloupci
jsou záporné, tj. aik < 0, úloha nemá optimální řešení.
5.3.2 Příklad. Řešte úlohu LP zadanou matematickým modelem:
7x1 + 5x2 ≤ 850,
2x1 + 2x2 ≤ 300,
z = 7x1 + 6x2 −→ max,
x1 ≥ 0, x2 ≥ 0.
Řešení. Soustavu lineárních nerovnic převedeme na soustavu lineárních rovnic (zavedením doplňkových proměnných). Současně anulujeme účelovou funkci (tj. od obou
stran účelové rovnice odečteme její pravou stranu).
= 850,
7x1 + 5x2 + x01
2x1 + 2x2
+ x02 = 300,
z −7x1 − 6x2
=
0 (max),
x1 ≥ 0, x2 ≥ 0, x01 ≥ 0, x02 ≥ 0.
Tím jsme získali kanonický tvar soustavy lineárních rovnic s nezápornými pravými
stranami. Můžeme tedy přikročit k simplexové tabulce, viz tab. 5.2.
V posledním kroku tabulky, v řádku účelové funkce již není žádný záporný koeficient
(a úloha je maximalizačního typu), optimální řešení má tedy tvar
xopt = (50, 100; 0, 0)
a maximální hodnota účelové funkce je
zmax = z(xopt ) = 950.
5.3 Zlepšování řešení
43
bi
pro aik > 0
aik
850
7
Z.p.
x1
x2
x01
x02
bi
x01
(7)
5
1
0
850
x02
2
2
0
1
300
150
z
−7
−6
0
0
0
max
1
1
7
0
170
− 27
1
850
7
400
7
100
max
x02
0
5
7
( 74 )
z
0
−1
1
0
850
x1
1
0
1
2
− 45
50
− 12
1
2
7
4
7
4
100
x1
x2
0
1
z
0
0
p=
950
MAX
Tab. 5.2 Simplexová tabulka k příkladu 5.3.2
5.3.3 Příklad. Řešte úlohu LP zadanou matematickým modelem (od předchozího
příkladu se liší jen tvarem účelové funkce):
7x1 + 5x2 ≤ 850,
2x1 + 2x2 ≤ 300,
z = 2x1 + 7x2 −→ max,
x1 ≥ 0, x2 ≥ 0.
Řešení. Opět převedeme SLN na SLR, opět jsme získali kanonický tvar soustavy
lineárních rovnic s nezápornými pravými stranami.
7x1 + 5x2 +x01
= 850,
2x1 + 2x2
+x02 = 300,
z −2x1 − 7x2
=
0 (max),
x1 ≥ 0, x2 ≥ 0, x01 ≥ 0, x02 ≥ 0.
Můžeme tedy přikročit k simplexové tabulce a simplexovou metodou určit optimální
řešení, viz tab. 5.3.
Optimální řešení a maximální hodnota účelové funkce je
xopt = (0, 150; 100, 0),
zmax = z(xopt ) = 1050.
44
5 SIMPLEXOVÁ METODA
bi
pro aik > 0
aik
Z.p.
x1
x2
x01
x02
bi
x01
7
5
1
0
850
170
x02
2
(2)
0
1
300
150
z
-2
-7
0
0
0
max
- 52
1
2
7
2
100
x01
2
0
1
x2
1
1
0
z
5
0
0
p=
150
1050
MAX
Tab. 5.3 Simplexová tabulka k příkladu 5.3.3
5.3.4 Úkoly a problémy k modulu 5.3
1. Simplexovou metodou vyřešte úlohu 1. z úkolů 3.1.2 na straně 22.
2. Simplexovou metodou vyřešte úlohu 2. z úkolů 3.1.2 na straně 22.
3. Vyřešte úlohu 3. z úkolů 3.1.2 na straně 22.
Řešení.
1. xopt = (70, 100; 0, 0), zmax = z(xopt ) = 42 960 Kč.
2. xopt = (400, 0; 0, 1 600, 400, 400), zmax = z(xopt ) = 32 000 Kč.
3. xopt = (0, 6 000, 3 000; 6 000, 0, 0), zmax = z(xopt ) = 144 000 Kč.
5.4 Shrnutí 5. kapitoly
45
5.4 Shrnutí 5. kapitoly
Klíčová slova:
Simplexová metoda, simplexův algoritmus, simplexová tabulka, výchozí řešení, test
optimálnosti řešení, zlepšování řešení, klíčový prvek, úplná eliminace.
Základní úlohy:
• Najít optimální řešení úlohy LP simplexovou metodou.
• Na základě zakončení simplexového algoritmu určit vlastnosti optimálního (optimálních) řešení.
Doporučená literatura pro hlubší studium:
[Holoubek]:
[Jablonský]:
[Kříž]:
[Mošová]:
str.
str.
str.
str.
33–49,
50–61,
36–42,
24–37.
5.5 Test ke kapitole 5
1. Řešte simplexovou metodou úlohu lineárního programování zadanou matematickým modelem:
z = x1 + 2x2 −→ max,
x1 + x2 ≤ 12,
3x1 + x2 ≤ 18,
x1 ≥ 0, x2 ≥ 0.
2. Řešte simplexovou metodou úlohu lineárního programování zadanou matematickým modelem:
z = x1 + 2x2 −→ max,
x1 + x2 ≤ 14,
3x1 + x2 ≤ 10,
x1 ≥ 0, x2 ≥ 0.
46
5 SIMPLEXOVÁ METODA
3. Simplexovou metodou určete všechna základní optimální řešení úlohy lineárního
programování zadanou matematickým modelem:
z = x1 − x2 −→ min,
x1 + x2 ≤ 6,
3x1 + x2 ≤ 15,
−x1 + x2 ≤ 3,
x1 ≥ 0, x2 ≥ 0.
4. Simplexovou metodou určete všechna základní optimální řešení úlohy lineárního
programování zadanou matematickým modelem:
z = −3x1 + x2 −→ min,
x1 + x2 ≤ 10,
3x1 + x2 ≤ 15,
−x1 + x2 ≤ 3,
x1 ≥ 0, x2 ≥ 0.
Řešení.
1. xopt = (0, 12; 0, 6), zmax = z(xopt ) = 24.
2. xopt = (0, 10; 4, 0), zmax = z(xopt ) = 20.
3. xopt,1 = (0, 3; 3, 12, 0), xopt,2 = ( 32 , 92 ; 0, 6, 0), zmin = z(xopt1 ) = z(xopt2 ) = −3.
4. xopt = (5, 0; 5, 0, 8), zmin = z(xopt ) = −15.
47
6
METODA UMĚLÉ BÁZE
Cílem kapitoly je:
• naučit se řešit úlohu LP metodou umělé báze.
Pomocí doplňkových proměnných lze převést na SLR v kanonickém tvaru pouze SLN
typu ”≤”. U nerovnic typu ”≥” a rovnic ”=” využíváme tzv. pomocných proměnných
a používáme metodu umělé báze.
6.1
Metoda umělé báze
Při řešení úlohy LP metodou umělé báze postupujeme následovně:
1. Pomocí doplňkových proměnných x0i ≥ 0 převedeme SLN na SLR.
2. Pokud SLR není v kanonickém tvaru, pak do rovnic, které neobsahují základní
proměnnou, uměle zavedeme nezápornou pomocnou proměnnou x00i ≥ 0.
3. Úlohu doplníme zavedením pomocné účelové funkce z 0 = x001 +x002 +· · ·+x00k → min,
k ≤ m, kde m je počet rovnic a k je počet pomocných (umělých) proměnných.
Dostáváme tak rozšířenou úlohu LP, pro kterou platí následující věta.
6.1.1 Věta. Každému přípustnému řešení rozšířené úlohy odpovídá přípustné řešení původní úlohy právě tehdy, když všechny pomocné proměnné jsou rovny nule,
tj. z 0 = 0.
Důkaz. Věta má tvar ekvivalence, dokážeme postupně obě implikace.
„⇐=ÿ Všechny pomocné proměnné jsou rovny nule, tj. x00i = 0, i = 1, . . . , k. Proto jsou splněny všechny vlastní omezující podmínky rozšířené úlohy, stejně jako vlastní omezující
podmínky původní úlohy a tudíž, řešení rozšířené úlohy odpovídá řešení původní úlohy.
„=⇒ÿ Nechť xroz. = (x1 , x2 , . . . , xn ; x001 , x002 , . . . , x00k ) je přípustné řešení rozšířené úlohy. Pokud
řešení x = (x1 , x2 , . . . , xn ) je současně řešením původní úlohy, nutně jsou splněny jak
omezující podmínky rozšířené úlohy, tak omezující podmínky původní úlohy. Přitom
tyto omezující podmínky se vzájemně liší jen o pomocnou proměnnou x00i , i = 1, . . . , k.
To je možné právě jen v případě, že všechny pomocné proměnné nabývají nulové hodnoty, tj. x001 = x002 = · · · = x00k = 0, tzn. z 0 = 0.
2
48
6 METODA UMĚLÉ BÁZE
6.1.2 Příklad. Uvažujme úlohu LP zadanou tímto matematickým modelem
2x1 + x2 ≤ 10,
−2x1 + 3x2 ≤ 9,
2x1 + 4x2 ≥ 8,
z = 2x1 − 3x2 −→ max,
x1 ≥ 0, x2 ≥ 0.
Řešení. Soustavu lineárních nerovnic převedeme na soustavu lineárních rovnic (zavedením doplňkových proměnných) a anulujeme účelovou rovnici. Dostaneme
= 10,
2x1 + x2 + x01
0
= 9,
−2x1 + 3x2
+ x2
2x1 + 4x2
− x03 = 8,
z −2x1 + 3x2
= 0 (max),
x1 ≥ 0, x2 ≥ 0, x01 ≥ 0, x02 ≥ 0, x03 ≥ 0.
Soustava není v kanonickém tvaru, ve třetí rovnici chybí základní proměnná, proto
ji do této rovnice uměle doplníme, tj. přidáme proměnnou x003 ≥ 0. Úlohu však musíme
doplnit i o pomocnou účelovou funkci z 0 = x003 → min. Po anulování pomocné účelové
funkce dostáváme z 0 − x003 = 0. Celkově tedy
= 10,
2x1 + x2 + x01
0
−2x1 + 3x2
+ x2
= 9,
2x1 + 4x2
− x03 + x003 = 8,
−2x1 + 3x2
z
= 0 (max),
− x003 = 0 (min),
z0
x1 ≥ 0, x2 ≥ 0, x01 ≥ 0, x02 ≥ 0, x001 ≥ 0, x002 ≥ 0.
Připsáním této rovnice pod ostatní jsme však porušili kanonický tvar (soustavy
teď už celkem pěti rovnic o osmi proměnných), proto pátou rovnici sečteme se všemi
rovnicemi, ve kterých se vyskytují pomocné proměnné (v našem případě pouze se třetí
rovnicí). Touto rovnicí nahradíme původní pátou rovnici.
Dostáváme tak rozšířenou úlohu (někdy říkáme též pomocnou úlohu)
2x1 + x2 + x01
= 10,
−2x1 + 3x2
+ x02
= 9,
2x1 + 4x2
− x03 + x003 = 8,
z
−2x1 + 3x2
z 0 +2x1 + 4x2
− x03
= 0 (max),
= 8 (min),
x1 ≥ 0, x2 ≥ 0, x01 ≥ 0, x02 ≥ 0, x03 ≥ 0, x003 ≥ 0.
6.1 Metoda umělé báze
49
Než začneme řešit původní úlohu, musíme vyřešit úlohu pomocnou. Pomocná úloha
umožňuje nalézt základní přípustné řešení původní úlohy, tj. řešení rozšířené úlohy
v případě, že z 0 = 0. Snažíme se tedy minimalizovat pomocnou účelovou funkci. Postupujeme standardním simplexovým algoritmem.
bi
pro aik > 0
aik
Z.p.
x1
x2
x01
x02
x03
x003
bi
x01
2
1
1
0
0
0
10
10
x02
−2
3
0
1
0
0
9
3
x003
2
(4)
0
0
−1
1
8
2
z
p=
−2
3
0
0
0
0
0
max2
0
2
4
0
0
−1
0
8
min1
x01
3
2
0
1
0
− 41
8
x02
− 72
0
0
1
1
4
3
4
− 43
3
x2
1
2
1
4
2
z
− 72
0
0
0
− 14
3
4
− 43
−6
max2
z0
0
0
0
0
0
−1
0
M IN1
z
1
0
0
V našem případě jsme již po prvním kroku nalezli optimální řešení rozšířené úlohy,
a to takové, že hodnota pomocné účelové funkce je rovna nule, z 0 = 0 (všechny pomocné
proměnné – zde x003 – byly vyloučeny z množiny základních proměnných. Proto tomuto
řešení odpovídá základní přípustné řešení původní úlohy. Pokračujeme simplexovým
algoritmem při hledání optimálního řešení původní úlohy (vypustíme řádek pomocné
účelové rovnice z 0 a sloupce koeficientů pomocných proměnných).
bi
pro aik > 0
aik
16
3
Z.p.
x1
x2
x01
x02
x03
bi
x01
3
2
0
1
0
8
x02
0
0
1
3
—
2
4
z
− 27
( 12 )
− 27
1
4
3
4
−6
max
x01
x02
x2
p=
1
0
0
0
0
0
− 14
3
4
0
−3
1
0
(1)
2
2
0
7
0
1
−1
17
—
4
—
max
x1
1
2
0
0
− 21
z
0
7
0
0
−1
8
x03
0
−3
1
0
1
2
x02
0
4
1
1
0
19
x1
1
1
2
1
2
0
0
5
z
0
4
1
0
0
10
M AX
50
6 METODA UMĚLÉ BÁZE
V posledním kroku simplexové tabulky jsme dospěli k optimálnímu řešení (původní) úlohy, xopt = (5, 0; 0, 19, 2), zmax = 10.
6.1.3 Poznámka. Je-li hodnota pomocné účelové funkce příslušná optimálnímu ře0
šení rozšířené úlohy kladná, tj. zmin
> 0, znamená to, že původní úloha nemá přípustné,
a tedy ani optimální, řešení.
6.1.4 Poznámka. Pomocné proměnné x00i nemají žádný věcný (ekonomický) význam.
Jejich význam je čistě matematický, slouží k nalezení výchozího základního přípustného
řešení (původní) úlohy.
6.2 Shrnutí 6. kapitoly
51
6.2 Shrnutí 6. kapitoly
Úlohu lineárního programování metodou umělé báze řešíme ve dvou fázích.
1. Minimalizujeme pomocnou účelovou funkci z 0 postupným vyřazováním pomocných proměnných z množiny základních proměnných a zařazováním proměnných,
které mají věcnou interpretaci. Mohou nastat 2 situace:
0
a) zmin
> 0, potom původní úloha nemá přípustné řešení,
0
b) zmin
= 0, v tom případě máme výchozí přípustné řešení původní úlohy.
2. V případě 1.b) řešíme původní úlohu vzhledem k účelové funkci z.
Klíčová slova:
Metoda umělé báze, pomocná proměnná, pomocná účelová funkce, rozšířená úloha
lineárního programování, pomocná úloha lineárního programování.
Základní úlohy:
• Určení optimálního řešení metodou umělé báze.
Doporučená literatura pro hlubší studium:
[Jablonský]:
[Kříž]:
str. 61–70,
str. 43–47,
6.3 Test ke kapitole 6
1. Vyřešte směšovací úlohu 1. z úkolů 3.2.2 na straně 25.
2. Vyřešte směšovací úlohu 2. z úkolů 3.2.2 na straně 25.
3. Vyřešte směšovací úlohu 3. z úkolů 3.2.2 na straně 25.
4. Vyřešte rozdělovací úlohu 1. z úkolů 3.3.3 na straně 27.
5. Vyřešte rozdělovací úlohu 2. z úkolů 3.3.3 na straně 27.
6. Vyřešte rozdělovací úlohu 3. z úkolů 3.3.3 na straně 27.
7. K dispozici jsou cívky s elektrickým kabelem délky 108 m. Pro další použití z nich
podnik potřebuje nařezat alespoň 30 ks kabelů délky 50 m, alespoň 60 ks délky
40 m a alespoň 150 ks délky 30 m. Určete optimální řešení rozdělovacího problému
z hlediska:
52
6 METODA UMĚLÉ BÁZE
a) minimálního odpadu. Kolik cívek bude v tom případě použito?
b) minimálního počtu rozřezaných cívek. Jaká bude v tom případě celková
délka odpadu?
Řešení.
1. xopt = (100, 60; 0, 0), zmin = z(xopt ) = 6 000 Kč.
2. xopt = (375, 125, 0; 0, 0), zmin = z(xopt ) = 93 750 Kč.
3. xopt = (2, 4; 0, 4), zmin = z(xopt ) = 104 Kč.
4. xopt = (50, 40, 0, 15; 0, 0, 0), zmin = z(xopt ) = 325 cm.
5. xopt = (16, 28, 0; 0, 0), zmin = z(xopt ) = 108 m.
6. xopt = (120, 0, 0, 55, 0; 0, 95, 0), zmin = z(xopt ) = 0 cm.
7.
a) xopt = (15, 0, 0, 0, 75, 0; 0, 15, 0), zmin = z(xopt ) = 720 m, bude použito 90
cívek.
b) xopt = (15, 0, 0, 0, 60, 10; 0, 0, 0), zmin = z(xopt ) = 85 cívek, velikost odpadu
bude 780 m.
53
7
DUALITA V ÚLOHÁCH LINEÁRNÍHO PROGRAMOVÁNÍ
Jak jsme již poznali v předchozích kapitolách, úlohy lineárního programování jsou
buď maximalizačního nebo minimalizačního typu, obsahují m omezujících podmínek
pro n neznámých. Jak si ukážeme dále, lze ke každé takové úloze sestavit v jistém
smyslu úlohu symetrickou, my ji budeme nazývat duální úloha. Přitom taková úloha
má svou interpretaci a také existuje hlubší vzájemný vztah obou úloh, optimálních
řešení těchto úloh, atd.
Cílem studia kapitoly je:
• osvojit si pojem dualita v lineárním programování,
• naučit se sestavovat k dané úloze lineárního programování úlohu duální,
• seznámit se s možností nalezení optimálního řešení dané úlohy pomocí
řešení úlohy duálně sdružené,
• probrat duálně simplexovou metodu.
7.1
Pojem duality a konstrukce duální úlohy
Uvažujme obecnou úlohu lineárního programování, tj. úlohu nalezení takového řešení
vlastních omezujících podmínek
a11 x1 + a12 x2 + . . . + a1n xn = b1 ,
a21 x1 + a22 x2 + . . . + a2n xn = b2 ,
.. ..
.. ..
..
..
..
. .
. .
.
.
.
am1 x1 + am2 x2 + . . . + amn xn = bm ,
aby současně byly splněny podmínky nezápornosti, tj.
xi ≥ 0, i = 1, 2, . . . , n,
a aby účelová funkce
z = c1 x1 + c2 x 2 + · · · + cn xn
nabyla svého maxima, resp. minima.
V úloze se vyskytují tři druhy koeficientů:
aij . . . strukturální koeficienty,
bi . . . celkové úrovně činitelů (pravé strany),
cj . . . cenové koeficienty (vše pro i = 1, . . . , m; j = 1, . . . , n).
54
7 DUALITA V ÚLOHÁCH LP
Tyto koeficienty jsou v matematických modelech propojeny pomocí proměnných xj .
Koeficienty aij , bi se vyskytují ve vlastních omezeních, koeficienty cj se vyskytují v účelové funkci. Takto zformulovaný matematický model budeme nazývat primární matematický model.
Ke každé úloze lineárního programování lze formulovat úlohu duální (pravidla pro
její konstrukci jsou uvedena níže). Dualita je matematický vztah mezi dvěmi úlohami
lineárního programování – primární a duální, které tvoří dvojici duálně sdružených
úloh.
7.1.1 Věta. (O reflexivnosti duality)
Duální úloha k duální úloze je původní primární úloha.
Důkaz. Důkaz plyne přímo, dvojím aplikováním pravidel pro konstrukci duální úlohy.
2
7.1.1 Důsledek. Reflexivnost duality umožňuje z vlastností a řešení primární úlohy
určit vlastnosti a řešení duální úlohy, a naopak.
Duální úlohu lze získat transformací, na základě níže uvedených pravidel, z úlohy
primární, je-li primární úloha v tzv. standardním tvaru. Pokud úloha ve standardním
tvaru není, je třeba ji na standardní tvar převést. To lze udělat vždy.
7.1.2 Definice. Říkáme, že
a) maximalizační úloha je ve standardním tvaru, jestliže všechny vlastní omezující
podmínky jsou typu „≤ÿ nebo „=ÿ, tzn. např.
z = c1 x1 + c2 x2 + . . . + cn xn −→ max,
a11 x1 + a12 x2 + . . . + a1n xn ≤ b1 ,
a21 x1 + a22 x2 + . . . + a2n xn ≤ b2 ,
.. ..
.. ..
..
..
..
. .
. .
.
.
.
am1 x1 + am2 x2 + . . . + amn xn ≤ bm ;
b) minimalizační úloha je ve standardním tvaru, jestliže všechny vlastní omezující
podmínky jsou typu „≥ÿ nebo „=ÿ, tzn. např.
z = c1 x1 + c2 x2 + . . . + cn xn −→ min,
a11 x1 + a12 x2 + . . . + a1n xn ≥ b1 ,
a21 x1 + a22 x2 + . . . + a2n xn ≥ b2 ,
.. ..
.. ..
..
..
..
. .
. .
.
.
.
am1 x1 + am2 x2 + . . . + amn xn ≥ bm .
7.1 Pojem duality a konstrukce duální úlohy
55
7.1.3 Poznámka. Pokud typy nerovností nejsou v souladu s extrémem účelové
funkce, je třeba příslušné vlastní omezující podmínky násobit číslem (−1), a to i za
cenu záporné pravé strany.
Ke každé úloze lineárního programování ve standardním tvaru lze jednoznačně přiřadit duální úlohu, a to na základě těchto pravidel:
• Maximalizační primární úloze ve standardním tvaru přísluší minimalizační duální
úloha ve standardním tvaru, a naopak.
• Každému vlastnímu omezení primární úlohy odpovídá jedna strukturní proměnná
úlohy duální, a naopak.
• Matice strukturních koeficientů primární úlohy a matice strukturních koeficientů
duální úlohy jsou navzájem transponované.
• Vektor pravých stran primární úlohy je vektorem cen úlohy duální, a naopak.
Schematicky můžeme uvedené souvislosti primární a duální úlohy popsat následovně.
PRIMÁRNÍ MATEMATICKÝ MODEL
DUÁLNÍ MATEMATICKÝ MODEL
Účelová funkce maximalizační
(resp. min.)
Účelová funkce minimalizační
(resp. max.)
Vlastní omezení primární úlohy
(v počtu m)
Podmínky nezápornosti duálních
proměnných (v počtu m)
Podmínky nezápornosti primárních
proměnných (v počtu n)
Vlastní omezení duální úlohy
(v počtu n)
Matematický zápis primárního modelu:
Matematický zápis duálního modelu:
z=
n
P
cj xj −→ max,
j=1
f=
m
P
bi ui −→ min,
i=1
A · xT ≤ bT ,
AT · u T ≥ c T ,
xj ≥ 0, j = 1, . . . , n.
ui ≥ 0, i = 1, . . . , m.
Dualita v lineárním programování je jednoznačné přiřazení matematickách modelů
vycházejících ze stejných koeficientů aij , bi , cj , které jsou v modelech jinak umístěny.
56
7 DUALITA V ÚLOHÁCH LP
7.1.4 Definice. Jestliže se v primární úloze objevují vlastní omezující podmínky
pouze ve tvaru nerovnic (nikoli rovnic) a podmínky nezápornosti na všechny proměnné, tvoří primární úloha spolu s duální úlohou dvojici tzv. symetrických duálně
sdružených úloh.
Když se mezi vlastními omezujícími podmínkami primární úlohy vyskytuje nějaká
rovnice, či pokud se nepožaduje nezápornost některé primární proměnné, nazýváme
primární úlohu spolu s duální úlohou dvojicí tzv. nesymetrických duálně sdružených
úloh.
7.1.5 Poznámka. Předchozí definice zavádí příslušné pojmy pomocí vlastností matematického modelu primární úlohy. Stejně tak je lze definovat i pomocí vlastností
matematického modelu duální úlohy, což je přímým důsledkem věty 7.1.1, věty o reflexivnosti duality.
7.1.6 Příklad. Podnik vyrábí dva druhy výrobků V1 a V2 . Tab. 7.1 udává spotřebu
surovin S1 a S2 v kg na výrobu 1 ks výrobku V1 , resp. V2 , i disponibilní množství těchto
surovin. Zisk z každého výrobku V1 je 3 Kč a z 1 ks V2 je 2 Kč. Stanovte optimální
výrobní plán podniku tak, aby dosáhl maximálního zisku. Sestavte matematický model
duální úlohy a nalezněte řešení duální úlohy.
S1
S2
zisk
Výrobky
V1 V2
2
5
4
1
3
2
Disponibilní
množství
1000
1100
max
Tab. 7.1 Ekonomický model úlohy
Řešení. Nejprve sestavíme (primární) matematický model úlohy.
2x1 + 5x2 ≤ 1000,
4x1 + x2 ≤ 1100,
z = 3x1 + 2x2 −→ max,
x1 ≥ 0, x2 ≥ 0.
Zde x1 , resp. x2 značí počet kusů výrobků V1 , resp. V2 .
Primární úloha je maximalizační a všechny vlastní omezující podmínky jsou nerovnosti (konkrétně typu „≤ÿ), tzn. matematický model je ve standardním tvaru. Současně
obě proměnné musí být nezáporné, proto tato úloha a k ní úloha duálně sdružená budou
tvořit dvojici symetrických úloh.
7.1 Pojem duality a konstrukce duální úlohy
57
Primární úloha má dvě vlastní omezení, proto duální úloha bude mít dvě duální
proměnné. Označíme je u1 a u2 . Uplatněním výše uvedených pravidel sestavíme matematický model duální úlohy ve tvaru
4u2 ≥ 3,
u2 ≥ 2,
2u1 +
5u1 +
f = 1000u1 + 1100u2 −→ min,
u1 ≥ 0, u2 ≥ 0.
Znaménka ve vlastních omezujících podmínkách a existence podmínek nezápornosti je
jednoznačně dána skutečností, že se jedná o dvojici symetrických duálně sdružených
úloh ve standardním tvaru.
Nebudeme-li zde uvažovat grafickou metodu, máme v zásadě dvě možnosti, jak
zjistit řešení duální úlohy:
1. samostatným řešením duální úlohy (simplexovou metodou),
2. ze simplexové tabulky vyřešené primární úlohy.
Vyřešme nejprve simplexovou metodou primární úlohu. Poté vyřešíme úlohu duální;
přitom užijeme metody umělé báze.
PRIMÁRNÍ ÚLOHA
Z.p. x1
x2
x01
x02
bi
p=
bi
pro aik > 0
aik
x01
2
5
1
0
1000
500
x02
(4)
1
0
1
1100
275
z
−3
−2
0
0
0
max
x01
0
)
( 18
4
1
− 12
450
100
1
1
4
0
275
1100
z
0
− 54
0
1
4
3
4
825
max
x2
0
1
2
9
− 19
100
x1
1
0
1
− 18
250
z
0
0
5
18
5
18
11
18
x1
950
M AX
V posledním kroku simplexové tabulky jsme dospěli k optimálnímu řešení primární
úlohy, x = (250, 100), zmax = 950.
58
7 DUALITA V ÚLOHÁCH LP
DUÁLNÍ ÚLOHA
bi
pro aik > 0
aik
3
2
2
5
Z.p.
u1
u2
u01
u02
u001
u002
bi
u001
2
4
−1
0
1
0
3
u002
(5)
1
0
−1
0
1
2
0
0
0
0
0
min2
f
−1000 −1100
p=
0
7
5
−1
−1
0
0
5
min1
u001
0
( 18
)
5
−1
2
5
1
− 25
11
18
u1
1
1
5
0
− 15
0
1
5
11
5
2
5
f
0
200
400
min2
0
11
5
11
18
5
18
min1
5
18
1
− 18
− 75
2
− 18
4
18
250
100
950
M IN2
−1
−1
0
M IN1
f
0
−900
0
−200
0
0
18
5
−1
u2
0
1
5
− 18
u1
1
0
1
18
2
5
2
18
4
− 18
f
0
0
0
0
0
f
f
−250 −100
0
0
2
5 11
Optimální řešení duální úlohy je u = ( 18
, 18 ), fmin = 950.
7.1.7 Věta. (Základní věta o dualitě)
Má-li jedna z dvojice duálně sdružených úloh lineárního programování optimální
řešení, pak má i druhá úloha optimální řešení a hodnoty účelových funkcí (pro tato
optimální řešení) jsou stejné.
Řešení duální úlohy lze vyvodit i z posledního kroku simplexové tabulky primární
úlohy. Podobně, na základě reflexivity duality platí, že optimální řešení primární úlohy
lze určit z posledního kroku simplexové tabulky duální úlohy (obsahuje-li optimální
řešení duální úlohy).
V tabulce 7.2, resp. tabulce 7.3, je vidět schématické znázornění posledního kroku
simplexové tabulky, v němž je dosaženo optimální řešení primární, resp. duální, úlohy.
Ukazuje, kde číst optimální řešení duálně sdružené úlohy, tj. řešení duální, resp. primární, úlohy. Optimální řešení duální úlohy je tvořeno proměnnými ui , i = 1, . . . , m
(nečárkované), jež se rovnají koeficientům u doplňkových proměnných x0i , i = 1, . . . , m
z anulované účelové rovnice při optimálním řešení primární úlohy, a dále doplňkovými proměnnými u0i , i = 1, . . . , n, které se rovnají koeficientům u proměnných xi ,
i = 1, . . . , n z téhož, tj. posledního, řádku simplexové tabulky řešení primární úlohy.
Analogicky (opět se zde uplatňuje reflexivnost duality) lze okomentovat optimální řešení primární úlohy „vyčtenéÿ z posledního kroku simplexové tabulky při řešení duální
úlohy.
7.1 Pojem duality a konstrukce duální úlohy
59
Z.p.
..
.
x1 . . . xn
..
.
x01 . . . x0m
..
.
bi
..
.
Z.p.
..
.
u1 . . . um
..
.
u01 . . . u0n
..
.
bi
..
.
z
u01 . . . u0n
u1 . . . um
z=f
f
x01 . . . x0m
x1 . . . xn
f =z
Tab. 7.2 Řešení duální úlohy v řešení
primární úlohy
Tab. 7.3 Řešení primární úlohy v řešení
duální úlohy
7.1.8 Poznámka. Pokud je úloha minimalizační, je třeba koeficienty v anulované
účelové rovnici vynásobit číslem (−1), a teprve pak je považovat za duální proměnné.
Uveďme na tomto místě, jaké kombinace optimálních řešení (a jejich vlastností)
duálně sdružených úloh jsou přípustné. Příslušná tvrzení uvedeme bez důkazu.
• Má-li primární úloha jediné optimální řešení, pak i duální úloha má jediné optimální řešení, a naopak.
• Má-li primární úloha alternativní řešení, pak optimální řešení duální úlohy je
degenerované, a naopak.
• Nemá-li primární úloha konečné optimální řešení (tj. má přípustná řešení, ale
účelová funkce může neomezeně růst, resp. klesat, podle toho, zda jde o maximalizační, resp. minimalizační, úlohu), pak duální úloha nemá žádné přípustné
řešení, a naopak.
7.1.9 Úkoly a problémy k modulu 7.1
1. K úloze zadané matematickým modelem
z = 308x1 + 214x2 −→ max,
10x1 +
2x1 +
8x2 ≤ 1 500,
x2 ≤ 240,
x1 ≥ 0, x2 ≥ 0,
viz úloha 1. z úkolů 3.1.2 na straně 22, sestavte matematický model duální úlohy.
Určete, zda se jedná o dvojici symetrických či nesymetrických duálně sdružených
úloh.
2. K úloze zadané matematickým modelem
z = 30x1 + 50x2 −→ min,
x1 + x2 ≥ 160,
2x1 + 5x2 ≥ 500,
x1 ≥ 0, x2 ≥ 0,
60
7 DUALITA V ÚLOHÁCH LP
viz úloha 1. z úkolů 3.2.2 na straně 25, sestavte matematický model duální úlohy.
Určete, zda se jedná o dvojici symetrických či nesymetrických duálně sdružených
úloh.
3. K úloze zadané matematickým modelem
z = 12x1 + 20x2 −→ min,
x1 + x2 = 6,
x1 + 1,5x2 ≥ 8,
12x1 + 10x2 ≥ 60,
x1 ≥ 0, x2 ≥ 0.
viz úloha 3. z úkolů 3.2.2 na straně 25, sestavte matematický model duální úlohy.
Určete, zda se jedná o dvojici symetrických či nesymetrických duálně sdružených
úloh.
4. K úloze zadané matematickým modelem
z = 5x1 + x2 + 8x3 −→ min,
2x1 + x2
≥ 60,
x1 + 3x2 + 4x3 ≥ 100,
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0.
viz úloha 2. z úkolů 3.3.3 na straně 27, sestavte matematický model duální úlohy.
Určete, zda se jedná o dvojici symetrických či nesymetrických duálně sdružených
úloh.
Řešení.
1.
f = 1500u1 + 240u2 −→ min,
10u1 +
8u1 +
2u2 ≥ 308,
u2 ≥ 214,
u1 ≥ 0, u2 ≥ 0,
2.
f = 160u1 + 500u2 −→ max,
u1 +
u1 +
2u2 ≤ 30,
5u2 ≤ 50,
u1 ≥ 0, u2 ≥ 0,
3.
symetrická dvojice úloh.
symetrická dvojice úloh.
f = 6u1 + 8u2 + 60u3 −→ max,
u1 + u2 + 12u3 ≤ 12,
u1 + 1,5u2 + 10u3 ≤ 20,
u2 ≥ 0, u3 ≥ 0,
nesymetrická dvojice úloh.
7.2 Ekonomická interpretace duální úlohy
4.
f = 60u1 + 100u2 −→ max,
2u1 +
u1 +
u2 ≤ 5,
3u2 ≤ 1,
4u2 ≤ 8,
u1 ≥ 0, u2 ≥ 0,
7.2
61
symetrická dvojice úloh.
Ekonomická interpretace duální úlohy
Dosud jsme duální úlohu (duální proměnné, omezení, účelovou funkci) vnímali pouze
čistě matematicky, bez hlubší ekonomické souvislosti s primární úlohou. Zde vyložíme
tuto souvislost pro případ úlohy výrobního plánování. Využijeme k tomu příkladu
z minulého odstavce.
7.2.1 Příklad. Podnik vyrábí dva druhy výrobků V1 a V2 . Tab. 7.4 udává spotřebu
surovin S1 a S2 v kg na výrobu 1 ks výrobku V1 , resp. V2 , i disponibilní množství těchto
surovin. Zisk z každého výrobku V1 je 3 Kč a z 1 ks V2 je 2 Kč.
S1
S2
zisk
Výrobky
V1 V2
2
5
4
1
3
2
Disponibilní
množství
1000
1100
max
Tab. 7.4 Ekonomický model úlohy
Optimální výrobní plán podniku tak, aby dosáhl maximálního zisku, jsme již stanovili
v příkladu 7.1.6. V tom případě se suroviny transformují na výrobky a ty se (se ziskem)
prodávají. Zde ale uvažujme zcela jinak. Úkolem je sestavit úlohu (její matematický
model), kdy nebudeme ze surovin vyrábět výrobky a ty prodávat, ale budeme prodávat
přímo suroviny, které má podnik k dispozici.
Řešení. Uvažujme tedy přímý prodej surovin. Otázkou, která nás zajímá, je, jaké by
musely být ceny surovin (a jakého nejmenšího možného zisku přitom dosáhneme), aby
se jejich přímý prodej vyplatil.
Označme tedy neznámou cenu jednotkového množství suroviny S1 symbolem u1 a
neznámou cenu jednotkového množství suroviny S2 symbolem u2 . Prodejní cena celkového množství surovin je potom dána funkcí
f = 1000u1 + 1100u2 .
Aby se přímý prodej surovin vyplatil (proti transformaci surovin na výrobky), je třeba
zajistit, aby se přímým prodejem surovin, potřebných pro výrobu 1 ks výrobku V1 ,
dosáhlo alespoň stejného zisku jako v případě jeho výroby a prodeje, tj. alespoň 3 Kč.
Dostáváme podmínku
2u1 + 4u2 ≥ 3.
62
7 DUALITA V ÚLOHÁCH LP
Analogickou úvahou vzhledem k surovinám potřebných k výrobě výrobku V2 dospějeme
k podmínce
5u1 + u2 ≥ 2.
Ceny surovin uvažujeme nezáporné, tj.
u1 ≥ 0, u2 ≥ 0.
Jak už bylo zmíněno, hledáme takové řešení (ceny surovin jednotkového množství) a
nejmenší možný celkový zisk tak, aby se jejich přímý prodej ještě vyplatil. Proto účelová
funkce f musí být minimalizačního typu.
Celkově tak dostáváme matematický model
2u1 +
5u1 +
4u2 ≥ 3,
u2 ≥ 2,
f = 1000u1 + 1100u2 −→ min,
u1 ≥ 0, u2 ≥ 0.
Je zřejmé, že se jedná o matematický model úlohy duální k původní úloze výrobního
plánování. V příkladu 7.1.6 jsme tuto úlohu řešili a získali optimální řešení ve tvaru
5 11
u = ( 18
, 18 ) s hodnotou účelové funkce fmin = 950.
7.3
Duálně simplexová metoda
Dříve než přikročíme k výkladu algoritmu duálně simplexové metody, nadefinujeme
některé pojmy.
7.3.1 Definice. Řešení se nazývá primárně přípustné řešení, jestliže splňuje
všechny vlastní omezující podmínky a podmínky nezápornosti.
Řešení maximalizační úlohy se nazývá duálně přípustné řešení, jestliže koeficienty
v anulované účelové funkci jsou nezáporné.
Řešení minimalizační úlohy se nazývá duálně přípustné řešení, jestliže koeficienty
v anulované účelové funkci jsou nekladné.
7.3.2 Poznámka. Definice primárně přípustného řešení je tedy totožná definici
pojmu přípustné řešení, který jsme užívali dosud.
První část následující poznámky je tudíž zřejmá, druhá část potom také, pokud si
uvědomíme, jaká je souvislost mezi primární a duální úlohou, viz. např. „pravidlaÿ na
str. 55.
7.3.3 Poznámka. Řešení je primárně přípustné, je-li přípustným řešením primární
úlohy.
Řešení je duálně přípustné, je-li přípustným řešením duální úlohy.
7.3 Duálně simplexová metoda
63
7.3.4 Věta. Řešení je současně primárně i duálně přípustné právě tehdy, když
řešení je optimální.
Při simplexové metodě, viz kap. 5, vycházíme z řešení, které je primárně přípustné a
duálně nepřípustné. Postupnými kroky, které zachovávají primární přípustnost, pokračujeme tak dlouho, až najdeme řešení (pokud existuje), které je také duálně přípustné
a tudíž i optimální.
Jak ukážeme dále, v případě duálně simplexové metody budeme vycházet z řešení,
které je duálně přípustné a primárně nepřípustné (tzn., že pravé strany vlastních omezení mohou být i záporné). Postupnými úpravami simplexové tabulky pomocí duálně
simplexové metody, která zachovává duální přípustnost, se dostaneme k řešení, které
je i primárně přípustné a tudíž i optimální.
Nyní vyložíme postup duálně simplexové metody. Vycházíme z duálně přípustného
řešení, viz definice 7.3.1. Dále:
1. Stanovíme klíčový řádek.
Určíme nejmenší hodnotu pravých stran omezujících podmínek. Nechť tato hodnota je v r-tém řádku, tedy min bi = br .
i
• Je-li br > 0, pak řešení je i primárně přípustné, a tedy i optimální.
• Je-li br = 0, pak řešení je optimální. Dané řešení je degenerované.
• Je-li br < 0, pak je nutno pokračovat bodem 2., r-tý řádek je klíčový.
2. Určíme klíčový sloupec.
Uvažujeme pouze záporné koeficienty klíčového řádku, tj. koeficienty arj < 0.
3. Vypočteme podíly p =
cj
arj
pro arj < 0, cj je příslušný koeficient v účelové funkci.
n o
c 4. Určíme min arjj .
arj <0
Sloupec, v němž je dosaženo tohoto minima, je klíčovým sloupcem.
5. Klíčový prvek je v průsečíku klíčového řádku a klíčového sloupce. Tabulka se
přepočte úplnou eliminací. Tzn., opět dělíme všechny prvky klíčového řádku klíčovým prvkem, prvky klíčového sloupce nahradíme příslušným základním sloupcovým jednotkovým vektorem, ostatní prvky dopočítáme (např. podle křížového
pravidla).
6. Pokračujeme bodem 1. pro nové základní řešení.
Ukažme si použití duálně simplexové metody při řešení úlohy, kterou již známe
z příkladů 7.1.6 a 7.2.1.
64
7 DUALITA V ÚLOHÁCH LP
7.3.5 Příklad. Duálně simplexovou metodou řešte úlohu zadanou tímto matematickým modelem:
z = 1000x1 + 1100x2 −→ min,
2x1 +
5x1 +
4x2 ≥ 3,
x2 ≥ 2,
x1 ≥ 0, x2 ≥ 0.
Řešení. Úloha je minimalizačního typu a v anulované účelové funkci
z − 1000x1 − 1100x2 = 0
jsou koeficienty u obou proměnných nekladné. Proto výchozí základní řešení, které
získáme, bude duálně přípustné, a tedy duálně simplexová metoda je pro řešení této
úlohy použitelná. Zavedením doplňkových proměnných převedeme vlastní omezující
podmínky ve tvaru nerovnic do tvaru rovnic
= 3,
2x1 + 4x2 − x01
0
5x1 + x2
− x2 = 2,
x1 ≥ 0, x2 ≥ 0, x01 ≥ 0, x02 ≥ 0.
Kanonický tvar soustavy rovnic, z něhož už lze přímo získat základní výchozí řešení,
dostaneme jednoduchou ekvivalentní úpravou, vynásobením posledních dvou rovnic
číslem (−1). Tedy, soustavu rovnic
−2x1
−4x2 + x01
= −3,
−5x1
−x2
+ x02 = −2,
z −1000x1 −1100x2
= 0 (min),
x1 ≥ 0, x2 ≥ 0, x01 ≥ 0, x02 ≥ 0
můžeme přepsat do simplexové tabulky a použít duálně simplexovou metodu. U každého kroku tabulky vypisujeme příslušné primární i duální základní řešení a primární
i duální přípustnost či nepřípustnost (zkratky P P, DP, P N, DN ).
7.3 Duálně simplexová metoda
65
Z.p.
x1
x2
x01
x02
bi
x01
-2
(-4)
1
0
-3
x02
-5
-1
0
1
-2
z
-1000
-1100
0
0
0
x2
1
- 14
0
x02
1
2
(- 29 )
0
- 14
1
3
4
- 54
z
-450
0
-275
0
825
1
9
- 29
11
18
5
18
-100
950
x2
0
1
x1
1
0
5
- 18
1
18
z
0
0
-250
x = (0, 0; −3, −2)
min
PN
u = (0, 0; 1000, 1100)
min −1000 , −1100 =
−2
−4
DP
1100
4
x = (0, 34 , 0, − 45 )
min
u = (275, 0; 450,
0)o
n
−450 −275 min − 9 , − 1 =
2
M IN
4
PN
DP
450
9
2
5 11
x = ( 18
, 18 ; 0, 0)
PP
u = (250, 100; 0, 0)
DP
Je zřejmé, že se jedná o matematický model úlohy duální k původní úloze výrobního
plánování. V příkladu 7.1.6 jsme tuto úlohu řešili a získali optimální řešení ve tvaru
5 11
u = ( 18
, 18 ) s hodnotou účelové funkce fmin = 950.
7.3.6 Úkoly a problémy k modulu 7.3
1. Duálně simplexovou metodou vyřešte směšovací úlohu 1. z úkolů 3.2.2 na
straně 25.
2. Duálně simplexovou metodou vyřešte směšovací úlohu 2. z úkolů 3.2.2 na
straně 25.
3. Duálně simplexovou metodou vyřešte směšovací úlohu 3. z úkolů 3.2.2 na
straně 25.
4. Duálně simplexovou metodou vyřešte rozdělovací úlohu 1. z úkolů 3.3.3 na
straně 27.
5. Duálně simplexovou metodou vyřešte rozdělovací úlohu 2. z úkolů 3.3.3 na
straně 27.
6. Duálně simplexovou metodou vyřešte rozdělovací úlohu 3. z úkolů 3.3.3 na
straně 27.
7. Duálně simplexovou metodou vyřešte rozdělovací úlohy 7.a) i 7.b) z testu ke
kapitole 6 na straně 51.
66
7 DUALITA V ÚLOHÁCH LP
Řešení.
1. xopt = (100, 60; 0, 0), zmin = z(xopt ) = 6 000 Kč.
2. xopt = (375, 125, 0; 0, 0), zmin = z(xopt ) = 93 750 Kč.
3. xopt = (2, 4; 0, 4), zmin = z(xopt ) = 104 Kč.
4. xopt = (50, 40, 0, 15; 0, 0, 0), zmin = z(xopt ) = 325 cm.
5. xopt = (16, 28, 0; 0, 0), zmin = z(xopt ) = 108 m.
6. xopt = (120, 0, 0, 55, 0; 0, 95, 0), zmin = z(xopt ) = 0 cm.
7.
a) xopt = (15, 0, 0, 0, 75, 0; 0, 15, 0), zmin = z(xopt ) = 720 m, bude použito 90
cívek.
b) xopt = (15, 0, 0, 0, 60, 10; 0, 0, 0), zmin = z(xopt ) = 85 cívek, velikost odpadu
bude 780 m.
7.4 Shrnutí 7. kapitoly
67
7.4 Shrnutí 7. kapitoly
Klíčová slova:
Dualita, standardní tvar úlohy, tvorba duální úlohy, symetrické duálně sdružené
úlohy, nesymetrické duálně sdružené úlohy, duálně simplexová metoda.
Základní úlohy:
• Vytvoření duální úlohy k dané úloze LP.
• Nalezení optimálního řešení úlohy LP ze simplexové tabulky řešení úlohy k ní duální.
• Ekonomická interpretace duální úlohy (duálních proměnných, duálního řešení, duálních omezujících podmínek, atd.).
• Řešení úlohy LP duálně simplexovou metodou.
Doporučená literatura pro hlubší studium:
[Holoubek]:
[Mošová]:
str. 27–32, 56–59,
str. 38–45.
7.5 Test ke kapitole 7
1. K úloze zadané matematickým modelem
z = 80x1 + 40x2 −→ max,
6x1 +
4x1 +
2x1 +
−x1 +
4x2
8x2
2x2
2x2
≤ 2 400,
≤ 3 200,
≤ 1 200,
≤
0,
x1 ≥ 0, x2 ≥ 0.
viz úloha 2. z úkolů 3.1.2 na straně 23, sestavte matematický model duální úlohy.
Jedná o dvojici symetrických či nesymetrických duálně sdružených úloh?
2. K úloze zadané matematickým modelem
z = 10x1 + 15x2 + 18x3 −→ max,
x1
+ 2x3 ≤ 12 000,
2x1 + 2x2 + 3x3 ≤ 21 000,
0,5x1 + 2x2
≤ 12 000,
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0.
viz úloha 3. z úkolů 3.1.2 na straně 23, sestavte matematický model duální úlohy.
Jedná o dvojici symetrických či nesymetrických duálně sdružených úloh?
68
7 DUALITA V ÚLOHÁCH LP
3. K úloze zadané matematickým modelem
z = 200x1 + 150x2 + 250x3 −→ min,
10x1 +
6x1 +
2x2 + 12x3 ≥ 4 000,
6x2 + 4x3 ≥ 3 000,
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0.
viz úloha 2. z úkolů 3.2.2 na straně 25, sestavte matematický model duální úlohy.
Jedná o dvojici symetrických či nesymetrických duálně sdružených úloh?
4. Duálně simplexovou metodou nalezněte optimální řešení úlohy vytvořené v příkladu 1. tohoto testu.
5. Duálně simplexovou metodou nalezněte optimální řešení úlohy vytvořené v příkladu 2. tohoto testu.
6. Duálně simplexovou metodou nalezněte optimální řešení úlohy vytvořené v příkladu 3. tohoto testu. Proveďte rovněž řešení úlohy grafickou metodou.
Řešení.
1.
−→ min,
f = 2 400u1 + 3 200u2 + 1 200u3
6u1 +
4u1 +
4u2 +
8u2 +
2u3 − u4 ≥ 80,
2u3 + 2u4 ≥ 40,
u1 ≥ 0, u2 ≥ 0, u3 ≥ 0, u4 ≥ 0,
2.
f = 12 000u1 + 21 000u2 + 12 000u3 −→ min,
u1 +
2u1 +
2u2 +
2u2 +
3u2
0,5u3 ≥ 10,
2u3 ≥ 15,
≥ 18,
u1 ≥ 0, u2 ≥ 0, u3 ≥ 0,
3.
symetrická dvojice úloh.
symetrická dvojice úloh.
f = 4 000u1 + 3 000u2 −→ max,
10u1 +
2u1 +
12u1 +
6u2 ≤ 200,
6u2 ≤ 150,
4u2 ≤ 250,
u1 ≥ 0, u2 ≥ 0,
symetrická dvojice úloh.
4. uopt = ( 40
, 0, 0, 0; 0, 40
), fmin = f (uopt ) = 32 000.
3
3
5. uopt = (0, 6, 32 ; 11
, 0, 0), fmin = f (uopt ) = 144 000.
4
6. uopt = ( 25
, 275 ; 0, 0, 250
), fmax = f (uopt ) = 93 750.
4 12
3
69
8
PARAMETRICKÉ LINEÁRNÍ PROGRAMOVÁNÍ
Cílem studia kapitoly je:
• naučit se řešit úlohy LP s parametrem v pravých stranách omezení,
• naučit se řešit úlohy LP s parametrem v cenových koeficientech,
• v rámci řešení úloh parametrického LP si blíže osvojit postupy probrané
v předchozích kapitolách, tj. simplexovou metodu, duálně simplexovou metodu, metodu umělé báze, převod SLN na SLR atd.
8.1
Parametrizace pravých stran
Řešme úlohu, v níž pravé strany omezujících podmínek jsou lineární funkcí parametru λ. Uvažujme tedy úlohu zadanou tímto matematickým modelem
z=
n
P
j=1
n
P
cj xj −→ max,
aij xj = δi + γi λ,
(i = 1, 2, . . . , m),
(8.1)
j=1
xj ≥ 0,
(j = 1, 2, . . . , n),
δi , γi , i = 1, 2, . . . , m, jsou konstanty,
λ je proměnný parametr zadaný v intervalu hp, P i, kde p, P ∈ R jsou tzv. technické
meze parametru λ.
Při řešení úlohy (8.1) postupujeme takto:
1. Sestavíme výchozí simplexovou tabulku, kterou rozšíříme o sloupec
bi (p) = δi + γi p (pravé strany, v nichž za λ volíme dolní technickou mez, λ = p).
2. Takto upravenou úlohu řešíme (simplexovou metodou nebo duálně simplexovou
metodou). Mohou nastat tyto případy:
a) Úloha 8.1 nemá ani jedno přípustné řešení (např. při DSM není v klíčovém
řádku žádný záporný koeficient).
b) Úloha 8.1 nemá optimální řešení (např. při SM není v klíčovém sloupci žádný
kladný koeficient).
c) Úloha 8.1 má pro λ = p optimální řešení.
70
8 PARAMETRICKÉ LP
3. V případě c), tj. v k-tém kroku najdeme optimální řešení úlohy (8.1) pro λ = p,
přejdeme k vlastní parametrizaci. Vyšetříme, pro které hodnoty parametru λ
jsou splněny podmínky primární přípustnosti, určíme tak interval hλ, λi. Pokud
je horní hranice λ tohoto intervalu menší než horní technická mez P , tj. λ < P ,
pokračujeme dále duálně simplexovou metodou pro λ > λ.
4. Bod 3. opakujeme tak dlouho, dokud nedostaneme λ ≥ P . Tak určíme optimální
řešení pro všechna λ ∈ hp, P i (řešení jsou samozřejmě závislá na hodnotě λ).
Ukažme si uvedený postup na příkladě.
8.1.1 Příklad. Řešte úlohu parametrického lineárního programování:
z = x1 + 2x2 −→ max,
x1 + x2 ≤ 12 − 12 λ,
3x1 + x2 ≤ 18 + 2λ,
x1 ≥ 0, x2 ≥ 0,
λ ∈ h−9, 24i.
Řešení. Až na výskyt parametru λ pracujeme standardně tak, jak jsme zvyklí řešit
úlohy LP, tj. zavedením doplňkových proměnných převedeme SLN na SLR a anulujeme
účelovou funkci.
= 12 − 21 λ,
x1 + x2 + x01
3x1 + x2
+ x02 = 18 + 2λ,
z− x1 − 2x2
= 0 (max),
x1 ≥ 0, x2 ≥ 0, x01 ≥ 0, x02 ≥ 0.
Získali jsme SLR v kanonickém tvaru, proto přikročíme k simplexové tabulce, přidáme
sloupec bi (p) = bi (−9).
bi
pro aik > 0
aik
33
2
Z.p.
x1
x2
x01
x02
bi (λ)
bi (−9)
x01
1
1
1
0
12 − 12 λ
33
2
x02
3
(1)
0
1
18 + 2λ
0
0
−1 −2
0
0
0
0
max
z
x01
−2
0
1
−1
x2
3
1
0
z
5
0
0
5
λ
2
33
2
1
18 + 2λ
0
2
36 + 4λ
0
−6 −
p=
max
Úlohu řešíme nejprve právě pro hodnotu parametru λ = p = −9. V prvním kroku
tabulky jsme našli optimální řešení úlohy pro λ = −9, xopt = (0, 0; 33
, 0), zmax = 0.
2
8.1 Parametrizace pravých stran
71
Přikročíme k parametrizaci. Parametrické řešení příslušné tomuto kroku je
x = (0, 18 + 2λ; −6 − 25 λ, 0), z = 36 + 4λ.
Řešení je duálně přípustné.
Pro jaké hodnoty je také primárně přípustné, tedy optimální? Dolní a horní hranici
parametru λ stanovíme řešením soustavy nerovnic:
)
18 + 2λ ≥ 0 ⇐⇒ λ ≥ −9
⇐⇒ λ ∈ h−9, − 12
i.
5
5
12
−6 − 2 λ ≥ 0 ⇐⇒ λ ≤ − 5
Protože − 12
< P = 24, pokračujeme v řešení dále. Pro λ > − 12
je již řešení primárně
5
5
nepřípustné, duální přípustnost na parametru λ nezávisí. Proto pokračujeme duálně
. V tom případě je −6 − 52 λ < 0, tato pravá strana
simplexovou metodou pro λ > − 12
5
tudíž určuje klíčový řádek. Pokračujeme výpočtem v simplexové tabulce, v ní už dále
sloupec bi (p) = bi (−9) není potřebný.
Z.p.
x1
x2
x01
x02
x01
−2
0
1
(−1)
−6 − 25 λ
x2
3
1
0
1
18 + 2λ
z
5
0
0
2
36 + 4λ
x02
2
0
−1
1
6 + 52 λ
x2
1
1
1
0
12 − 21 λ
z
1
0
2
0
24 − λ
bi (λ)
max
max
Řešení x = (0, 12− 21 λ; 0, 6+ 52 λ) s hodnotou účelové funkce z = 24−λ, je optimální,
pokud je primárně přípustné, a to je pro všechny hodnoty parametru λ, pro něž platí:
)
6 + 52 λ ≥ 0 ⇐⇒ λ ≥ − 12
5
⇐⇒ λ ∈ h− 12
, 24i.
5
1
12 − 2 λ ≥ 0 ⇐⇒ λ ≤ 24
Tím jsme vyřešili úlohu pro všechny hodnoty parametru λ ∈ h−9, 24i. Na závěr příkladu zjištěná optimální řešení uvedeme do shrnující tabulky, viz tab. 8.1.
λ
xopt (λ)
z(λ)
h−9, − 12
i
5
(0, 18 + 2λ; −6 − 52 λ, 0)
36 + 4λ
h− 12
, 24i
5
(0, 12 − 12 λ; 0, 6 + 25 λ)
24 − λ
Tab. 8.1 Shrnutí výsledků v závislosti na λ
72
8 PARAMETRICKÉ LP
8.1.2 Úkoly a problémy k modulu 8.1
1. Řešte úlohu parametrického lineárního programování:
z = 12x1 + 8x2 −→ max,
4x1 + 2x2 ≤ 2 000 + 4λ,
4x1 + x2 ≤ 1 600 + λ,
2x1 + 2x2 ≤ 1 500 − λ,
x1 ≥ 0, x2 ≥ 0,
λ ∈ h0, 1 500i.
2. Řešte úlohu parametrického lineárního programování:
z = 30x1 + 50x2 −→ min,
x1 + x2 ≥ 160 + λ,
2x1 + 5x2 ≥ 500 + 10λ,
x1 ≥ 0, x2 ≥ 0,
λ ∈ R.
Řešení.
1.
λ
xopt (λ)
z(λ)
i
h0, 50
3
(250 + 52 λ, 500 − 3λ; 0, 100 − 6λ, 0)
7 000 + 6λ
h 50
, 1400
i
3
3
( 850
+ 12 λ, 1400
− λ; − 200
+ 4λ, 0, 0)
3
3
3
21 400
3
h 1400
, 1 500i
3
2.
8.2
(750 −
1
λ, 0; −1 000
2
+ 6λ, −1 400 + 3λ, 0)
− 2λ
9 000 − 6λ
λ
xopt (λ)
z(λ)
(−∞, −160i
(0, 0; −160 − λ, −500 − 10λ)
0
h−160, − 45
i
2
h− 45
, 60i
2
(160 + λ, 0; 0, −180 − 8λ)
4 800 + 30λ
(100 − 53 λ, 60 + 83 λ; 0, 0)
6 000 +
h60, ∞)
(0, 100 + 2λ; −60 + λ, 0)
5 000 + 100λ
250
λ
3
Parametrizace koeficientů účelové funkce
Řešme úlohu, v níž jsou koeficienty účelové funkce lineární funkcí parametru ν. Uvažujme tedy úlohu zadanou tímto matematickým modelem
8.2 Parametrizace koeficientů účelové funkce
z=
n
P
j=1
n
P
73
(σj + τj ν)xj −→ max ,
aij xj = bi ,
(i = 1, 2, . . . , m),
(8.2)
j=1
xj ≥ 0,
(j = 1, 2, . . . , n),
σj , τj , j = 1, 2, . . . , n, jsou konstanty,
ν je proměnný parametr zadaný v intervalu hp, P i, kde p, P ∈ R jsou tzv. technické
meze parametru ν. Změny koeficientů účelové funkce mají vliv na duální přípustnost
řešení.
Při řešení úlohy (8.2) postupujeme takto:
1. Sestavíme výchozí simplexovou tabulku, kterou rozšíříme o řádek
z(p) = σj + τj p (koeficienty anulované účelové rovnice, v nichž za ν volíme
dolní technickou mez, ν = p).
2. Takto upravenou úlohu řešíme simplexovou metodou. Mohou nastat tyto případy:
a) Úloha 8.2 nemá ani jedno přípustné řešení (např. při řešení metodou umělé
0
báze je zmin
> 0).
b) Úloha 8.2 nemá konečné optimální řešení (např. v klíčovém sloupci není
žádný kladný koeficient).
c) Úloha 8.2 má pro ν = p optimální řešení.
3. V případě c), tj. v případě, kdy v k-tém kroku najdeme optimální řešení
úlohy (8.2) pro ν = p, přejdeme k vlastní parametrizaci. Vyšetříme, pro které
hodnoty parametru ν jsou splněny podmínky primární přípustnosti, určíme
tak interval hν, νi. Pokud je horní hranice ν tohoto intervalu menší než horní
technická mez P , tj. ν < P , pokračujeme dále simplexovou metodou pro ν > ν.
4. Bod 3. opakujeme tak dlouho, dokud nedostaneme ν ≥ P . Tak určíme optimální řešení pro všechna ν ∈ hp, P i (řešení jsou samozřejmě závislá na hodnotě
parametru ν).
8.2.1 Příklad. Řešte úlohu parametrického lineárního programování:
z = (3 + ν)x1 + (2 − ν)x2 −→ max,
x1 + x2 ≤ 10,
x2 ≤ 6,
x1 ≥ 0, x2 ≥ 0,
ν ∈ R.
74
Řešení.
8 PARAMETRICKÉ LP
Převedeme SLN na SLR a anulujeme účelovou rovnici.
x2 + x01
= 10,
0
x2
+ x2 = 6,
x1 +
z− (3 + ν)x1 − (2 − ν)x2
x1 ≥ 0, x2 ≥
0, x01
≥
0, x02
= 0 (max),
≥ 0.
Získali jsme SLR v kanonickém tvaru, proto přikročíme k simplexové tabulce, přidáme
řádek z(p) = z(−∞).
bi
pro aik > 0
aik
Z.p.
x1
x2
x01
x02
bi
x01
1
1
1
0
10
10
x02
0
(1)
0
1
6
6
z(ν)
−3 − ν
−2 + ν
0
0
0
z(−∞)
∞
−∞
0
0
0
x01
1
0
1
−1
4
x2
0
1
0
1
6
z(ν)
−3 − ν
0
0
2−ν
12 − 6ν
z(−∞)
∞
0
0
∞
∞
p=
max
M AX
Dospěli jsme k řešení x = (0, 6; 4, 0), které je evidentně optimálním řešením úlohy
pro ν = p = −∞. Přikročíme k parametrizaci, tj. určíme všechny hodnoty parametru ν, pro něž je toto řešení optimální. Primárně přípustné je; vyšetříme tedy duální
přípustnost:
−3 − ν ≥ 0
⇐⇒
ν ≤ −3
2−ν ≥0
⇐⇒
ν≤2
)
⇐⇒
ν ∈ (−∞, −3i.
Celkově, pro ν ∈ (−∞, −3i je optimálním řešením xopt = (0, 6; 4, 0) s hodnotou účelové
funkce zmax = 12 − 6ν.
Pro ν > −3 je již koeficient −3 − ν záporný, a tedy určuje klíčový sloupec. Pokračujeme simplexovou metodou.
8.2 Parametrizace koeficientů účelové funkce
75
bi
pro aik > 0
aik
Z.p.
x1
x2
x01
x02
bi
x01
(1)
0
1
−1
4
4
x2
0
1
0
1
6
–
z(ν)
−3 − ν
0
0
2−ν
12 − 6ν
max
x1
1
0
1
−1
4
–
x2
0
1
0
(1)
6
6
z(ν)
0
0
3+ν
−1 − 2ν
24 − 2ν
max
x1
1
1
1
0
10
x02
0
1
0
1
6
z(ν)
0
1 + 2ν
3+ν
0
30 + 10ν
p=
max
V dalších krocích jsme postupně získali optimální řešení:
- pro ν ∈ h−3, − 21 i : xopt = (4, 6; 0, 0) s hodnotou účelové funkce zmax = 24 − 2ν,
- pro ν ∈ h− 21 , ∞i : xopt = (10, 0; 0, 6) s hodnotou účelové funkce zmax = 30 + 10ν.
Celkově uvedeme zjištěná optimální řešení ve shrnující tabulce 8.2.
ν
xopt
z(ν)
(−∞, −3i
(0, 6; 4, 0)
12 − ν
h−3, − 21 i
h− 12 , ∞)
(4, 6; 0, 0)
24 − 2ν
(10, 0; 0, 6)
30 + 10ν
Tab. 8.2 Shrnutí výsledků v závislosti na ν
8.2.2 Úkoly a problémy k modulu 8.2
1. Řešte úlohu parametrického lineárního programování:
z = (1 − ν)x1 + (2 + 21 ν)x2 −→ max,
x1 + x2 ≤ 4,
x1 + 2x2 ≤ 6,
x1 ≥ 0, x2 ≥ 0,
ν ∈ R.
76
8 PARAMETRICKÉ LP
2. Řešte úlohu parametrického lineárního programování:
z = (1 + ν)x1 + (1 − ν)x2 −→ max,
−2x1 + x2 ≤ 2,
x2 ≤ 5,
x1 ≥ 0, x2 ≥ 0,
ν ∈ R.
Řešení.
1.
2.
ν
xopt
z(ν)
(−∞, − 23 i
(4, 0; 0, 2)
4 − 4ν
h− 23 , 0i
(2, 2; 0, 0)
6−ν
h0, ∞)
(0, 3; 1, 0)
6 + 32 ν
ν
xopt
(−∞, −1i
( 32 , 5; 0, 0)
(−1, ∞)
neexistuje
z(ν)
13
2
− 27 ν
roste nade všechny meze
8.3 Shrnutí 8. kapitoly
77
8.3 Shrnutí 8. kapitoly
Klíčová slova:
Parametrické lineární programování, parametr v pravých stranách vlastních omezujících podmínek, parametr v koeficientech účelové funkce, dolní a horní technická
mez parametru.
Základní úlohy:
• Nalezení optimálního řešení úlohy parametrického lineárního programování s parametrem v pravých stranách omezení.
• Nalezení optimálního řešení úlohy parametrického lineárního programování s parametrem v koeficientech účelové funkce.
Doporučená literatura pro hlubší studium:
[Mošová]:
str. 56–63.
8.4 Test ke kapitole 8
1. Řešte úlohu parametrického lineárního programování:
2x1 + x2 ≤ 10 + λ,
−2x1 + 3x2 ≤ 9 − 3λ,
2x1 + 4x2 ≥ 8 + 4λ,
z = 2x1 − 3x2 −→ max,
x1 ≥ 0, x2 ≥ 0,
λ ∈ h−12, 12i.
2. Řešte úlohu parametrického lineárního programování:
z = (−15 − 2ν)x1 + (−5 + ν)x2 −→ max,
−x1 + x2 ≤ 1,
−x1 − x2 ≤ 2,
x1 ≥ 0, x2 ≥ 0,
ν ∈ R.
78
8 PARAMETRICKÉ LP
Řešení.
1.
2.
λ
xopt (λ)
z(λ)
h−12, −10)
neexistuje ani přípustné řešení
—
h−10, 23 i
(5 + 12 λ, 0; 0, 19 − 2λ, 2 − 3λ)
10 + λ
h 23 , 65
i
18
( 16
, − 32 + λ; 0, 65
− 6λ, 0)
3
3
( 65
, 12i
18
neexistuje ani přípustné řešení
ν
xopt
z(ν)
(−∞, − 15
)
2
neexistuje
neomezeně roste
, 5i
h− 15
2
(0, 0; 1, 2)
0
h5, ∞)
(0, 1; 0, 3)
−5 + ν
38
3
− 3λ
—
79
9
DOPRAVNÍ ÚLOHA
Cílem studia kapitoly je:
• pochopit princip dopravní úlohy,
• naučit se řešit vyrovnané i nevyrovnané dopravní úlohy,
• naučit se poznávat základní vlastnosti uvažovaného řešení (zda je degenerované, alternativní) a správně interpretovat výsledky.
Dopravním problémem nazýváme rozhodovací situaci, při které se má přepravit určité
množství zboží jednoho druhu od m dodavatelů Di (i = 1, 2, ..., m) k n spotřebitelům
Sj (j = 1, 2, ..., n). Přitom dodavatel Di disponuje množstvím ai tohoto zboží a spotřebitel Sj požaduje dodání bj jednotek zboží. Mluvíme potom o kapacitách ai dodavatelů
Di (i = 1, 2, ..., m) a požadavcích bj spotřebitelů Sj (j = 1, 2, ..., n). Dodavatel Di může
dodat zboží více spotřebitelům, ale v součtu nemůže překročit svou kapacitu ai . Podobně, spotřebitel Sj může přijmout zboží od více dodavatelů, ale dohromady nejvýše
množství rovné jeho požadavku bj . Najít řešení znamená stanovit množství zboží, jež
dodavatel Di dodá spotřebiteli Sj pro každé i = 1, 2, ..., m a j = 1, 2, ..., n. Budeme
určovat optimální řešení, u něhož kromě splnění výše uvedených podmínek budeme
požadovat minimalizaci celkových přepravních nákladů.
Nejprve se naučíme řešit dopravní úlohy, v nichž součet kapacit dodavatelů je roven
součtu požadavků spotřebitelů, tj. vyrovnané dopravní úlohy. Po zvládnutí tohoto typu
úloh přikročíme k řešení úloh nevyrovnaných.
9.1
Vyrovnaná dopravní úloha
9.1.1 Definice. Pokud se součet kapacit dodavatelů rovná součtu požadavků spotřebitelů, říkáme, že dopravní úloha je vyrovnaná. V opačném případě nazýváme
úlohu nevyrovnanou.
Na příkladě 9.1.2 si ukážeme, jak dopravní úloha vypadá a vytvoříme matematický
model této úlohy. Uvedené úvahy následně zobecníme.
9.1.2 Příklad. Od dvou dodavatelů D1 a D2 je třeba přemístit zboží ke 3 spotřebitelům S1 , S2 a S3 (m = 2, n = 3). Kapacity dodavatelů jsou u D1 800 ks a u D2 1200
ks. Požadavky spotřebitelů jsou u S1 600 ks, u S2 900 ks, u S3 500 ks. Náklady na přepravu 1 ks zboží po jednotlivých cestách udávají tzv. přepravní sazby cij . Hodnota cij
vyjadřuje náklady na přepravu 1 ks zboží od i-tého dodavatele k j-tému spotřebiteli.
80
9 DOPRAVNÍ ÚLOHA
Např. přeprava 1 ks od D1 k S1 stojí 30 Kč, tedy c11 = 30. Analogický je význam i
dalších přepravních sazeb. Nechť jsou přepravní sazby následující:
c11 = 30; c12 = 10; c13 = 5;
c21 = 15; c22 = 20; c23 = 12.
Úkolem je sestavit optimální plán přepravy, tj. rozhodnout, po kterých cestách a
v jakém množství se má zboží přepravovat, aby celkové přepravní náklady byly minimální. Na tomto místě je naším úkolem sestavit matematický model úlohy.
Řešení. Zavedeme proměnné xij , jež představují množství (počet jednotek, kusů,
apod.) zboží přepraveného od Di k Sj . Řešení této dopravní úlohy je představováno
maticí
x11 x12 x13
X = (xij )2×3 =
.
x21 x22 x23
Vlastní omezení úlohy jsou dány požadavky spotřebitelů a kapacitami dodavatelů a
jsou u vyrovnané úlohy vždy ve tvaru rovnic:
D1 : x11 + x12 + x13 = 800,
D2 : x21 + x22 + x23 = 1200,
S1 :
x11 + x21 = 600,
S2 :
x12 + x22 = 900,
S3 :
x13 + x23 = 500.
(9.1)
Nelze přepravovat záporné množství zboží, proto platí podmínky nezápornosti:
xij ≥ 0, i = 1, 2; j = 1, 2, 3.
Přeprava 1 ks od D1 k S1 stojí 30 Kč, přeprava x11 ks od D1 k S1 stojí 30 x11 Kč, atd.,
proto celkové přepravní náklady jsou dány funkcí
z = 30x11 + 10x12 + 5x13 + 15x21 + 20x22 + 12x23 .
Cílem je nalezení přípustného řešení s nejmenšími celkovými přepravními náklady, tzn.
funkce z je účelovou funkcí minimalizačního typu:
z = 30x11 + 10x12 + 5x13 + 15x21 + 20x22 + 12x23 → min.
Nyní budeme formulovat dopravní úlohu v obecném tvaru.
Uvažujme m dodavatelů D1 , D2 , ..., Dm s kapacitami a1 , a2 , ..., am jednotek zboží. Toto
zboží se má přepravit k n spotřebitelům S1 , S2 , ..., Sn s požadavky b1 , b2 , ..., bn .
Náklady na přepravu jednotky zboží od i-tého dodavatele k j-tému spotřebiteli budeme
označovat cij , i = 1, 2, ..., m, j = 1, 2, ..., n.
Úkolem je určit optimální plán přepravy zboží, tj. určit množství, která se mají dopravit od jednotlivých dodavatelů k jednotlivým spotřebitelům tak, aby požadavky
9.1 Vyrovnaná dopravní úloha
81
spotřebitelů byly splněny a přepravní náklady byly minimální.
Proměnné xij značí množství zboží přepraveného od i-tého dodavatele k j-tému spotřebiteli. Řešení dopravní úlohy představuje matice


x11 . . . x1n


.. ..
X = (xij )m×n =  ...
.
. .
xm1 . . . xmn
Předpokládejme, že úloha je vyrovnaná, tzn. že platí
m
X
ai =
i=1
n
X
bj .
j=1
Matematický model:
z=
m P
n
P
cij xij −→ min,
i=1 j=1
n
P
Di :
j=1
m
P
Sj :
xij = ai ,
i = 1, 2, ..., m,
xij = bj ,
j = 1, 2, ..., n,
i=1
xij ≥ 0,
i = 1, 2, ..., m,
j = 1, 2, ..., n.
Účelová funkce zajišťuje minimalizaci celkových přepravních nákladů. Soustava
vlastních omezení zabezpečuje, že bude zcela vyčerpána kapacita dodavatelů a současně naplněny požadavky spotřebitelů.
Výchozí údaje i vlastní řešení zapisujeme do tabulky:
dod.\ sp.
D1
S1
c11
x11
S2
c12
x12
c21
c22
...
...
Sn
c1n
x1n
ai
a1
c2n
D2
x21
x22
...
x2n
a2
..
.
..
.
..
.
..
.
..
.
..
.
cm1
cm2
cmn
Dm
xm1
xm2
...
xmn
am
bj
b1
b2
...
bn
Σbj = Σai
82
9 DOPRAVNÍ ÚLOHA
9.1.3 Poznámka. Je-li úloha vyrovnaná, tj. platí-li
m
P
i=1
ai =
n
P
bj , pak jedno z m + n
j=1
vlastních omezení je lineárně závislé na ostatních. Základní řešení proto obsahuje právě
m + n − 1 základních proměnných, vedlejší proměnné jsou rovny nule. Základní řešení
tedy může mít maximálně m + n − 1 kladných proměnných (tj. obsazených polí).
Nedegenerované řešení obsahuje právě m + n − 1 kladných xij .
Degenerované řešení obsahuje méně než m + n − 1 kladných xij (aspoň jedna základní
proměnná je rovna nule).
9.1.4 Poznámka. V tabulce budeme používat značení, při němž základní proměnná
bude odpovídat políčku Di Sj obsazenému (nezápornou) hodnotou xij . Takové políčko
budeme nazývat obsazené pole . Vedlejší proměnná bude odpovídat tzv. proškrtnutému
poli, jež budeme značit křížkem „×ÿ.
9.1.5 Postup při řešení dopravní úlohy
Při řešení vyrovnané dopravní úlohy postupujeme následovně
1. Nejprve zjistíme, zda daná dopravní úloha je vyrovnaná. V případě, že není, ji
na vyrovnanou převedeme, viz modul 9.6.
2. Je-li již dopravní úloha vyrovnaná, je třeba nalézt výchozí základní přípustné
řešení, tomu je věnován odstavec 9.2.
3. Uvažované základní řešení dopravní úlohy podrobíme testu optima (zjistíme, zda
řešení je optimální či nikoliv), viz 9.3.
4. Není-li řešení optimální, je třeba najít lepší základní řešení, tzn. základní řešení s nižšími celkovými přepravními náklady. O problematice zlepšování řešení
pojednává modul 9.4.
5. Pokračujeme body 3. a 4. tak dlouho, dokud nenalezneme optimální řešení.
9.2
Vogelova aproximační metoda
Vogelova aproximační metoda (dále jen VAM) slouží k nalezení výchozího základního
přípustného řešení. V literatuře, např. [Jablonský], se čtenář může seznámit i s dalšími
metodami pro nalezení výchozího základního přípustného řešení jako je např. metoda
severozápadního rohu či indexní metoda.
U všech těchto metod se nejprve určí políčko Di Sj , které obsadíme maximálním množstvím xij přepravovaného zboží s ohledem na kapacitu ai a požadavek bj s přihlédnutím
na již obsazená políčka v i-tém řádku a j-tém sloupci. Právě způsobem výběru tohoto
políčka se jmenované metody liší.
Dále, vyčerpáme-li kapacitu nějakého dodavatele, proškrtneme dosud neobsazená pole
daného řádku (zkráceně říkáme, že proškrtneme řádek Di ). Vyčerpáme-li požadavek
nějakého spotřebitele, proškrtneme dosud neobsazená pole daného sloupce (zkráceně
říkáme, že proškrtneme sloupec Sj ).
9.2 Vogelova aproximační metoda
83
Postup VAM
1. K tabulce přidáme řádek (označený ∆j ) a sloupec (označený ∆i ) pro diference
(rozdíly).
2. V každém řádku a sloupci určíme dvě nejnižší sazby, vypočteme jejich rozdíl
(diferenci) a tento zapíšeme do sloupce ∆i a řádku ∆j .
3. Najdeme řádek či sloupec s největší diferencí a v tomto řádku či sloupci obsadíme
políčko s minimální sazbou.
4. V případě vyčerpání kapacity dodavatele proškrtneme příslušný řádek; v případě
uspokojení požadavku spotřebitele proškrtneme příslušný sloupec.
5. Pokračujeme bodem 2. Při výpočtu diferencí neuvažujeme proškrtnutá ani obsazená pole.
9.2.1 Poznámka.
K bodu 3.: Pokud je maximální diference u více řádků či sloupců, obsazujeme políčko
s nejnižší sazbou ze všech dosud neobsazených a neproškrtnutých polí v těchto řádcích
a sloupcích.
K bodu 4.: Pokud je vyčerpán současně řádek i sloupec, proškrtneme (libovolně) jen
jeden z nich. V tom případě v některém z následných kroků budeme nuceni vybrané
políčko obsadit nulovou hodnotou (jedná se o degenerované řešení). Výhodou tohoto
postupu je, že budeme znát všechny základní proměnné, tj. obsazených polí bude právě
m + n − 1.
Postup VAM si ukážeme na příkladu.
9.2.2 Příklad. Nalezněme metodou VAM výchozí základní přípustné řešení dopravní
úlohy z příkladu 9.1.2. Zadání lze znázornit rovněž ve formě tabulky (tab. 9.1), jež
obsahuje kapacity K dodavatelů, požadavky P spotřebitelů a přepravní sazby cij .
cij
S1
S2
S3
K
D1
30
10
5
800
D2
15
20
12
1200
P
600
900
500
2000
Tab. 9.1 Zadání dopravní úlohy, Př. 9.2.2
Rozměry tabulky zvětšíme, přepravní sazby zapíšeme do pravých horních rohů jednotlivých políček, tabulku rozšíříme o sloupec řádkových diferencí ∆i a o řádek sloupcových
diferencí ∆j , viz tab. 9.2.
84
9 DOPRAVNÍ ÚLOHA
S1
30
S2
10
S3
K
D1
800
15
20
12
D2
P
∆j
∆i
5
1200
600
900
500
2000
-
-
Tab. 9.2 Rozšíření tabulky, příprava na VAM
Všechny řádkové i sloupcové diference vypočítáme, viz tab. 9.3.
S1
30
S2
10
S3
K
5
D1
800 5
15
20
12
D2
P
∆j
∆i
1200 3
600
15
900
10
500
7
2000
-
-
Tab. 9.3 Metoda VAM, určení diferencí
Z nich největší je ve sloupci S1 (nabývá hodnoty 15 = max{5, 3, 15, 10, 7}), v tomto
sloupci vybereme políčko s nejmenší sazbou, tj. pole D2 S1 se sazbou 15. Toto pole
obsadíme hodnotou 600 = min{1200, 600}. Tím jsme uspokojili požadavek spotřebitele
S1 , a proto proškrtneme ostatní dosud neobsazená pole tohoto sloupce, tj. proškrtneme
sloupec S1 . Situace je patrná v tab. 9.4.
S2
10
D1
S1
30
×
15
600
20
D2
S3
K
∆i
5
800 5
12
1200 3
1
P
∆j
600
15
900
10
500
7
2000
-
-
Tab. 9.4 Metoda VAM, určení diferencí
Vypočítáme nové diference. Při jejich určení už sloupec S1 neuvažujeme. Největší
z nových diferencí je ve sloupci S2 (má hodnotu 10 = max{5, 8, 10, 7}). V tomto sloupci
9.2 Vogelova aproximační metoda
85
má nejmenší sazbu políčko D1 S2 , jež obsadíme hodnotou 800 = min{800, 900}. Vyčerpali jsme kapacitu dodavatele D1 , proškrtneme tedy řádek D1 . V této fázi už zbývá
jediný nevyplněný řádek (řádek D2 ), viz tab. 9.5.
D1
S1
30
×
S2
10
800
20
D2
15
600
S3
K
∆i
5
×
800 5,5
2
12
1200 3,8
1
P 600
900
∆j 15,× 10,10
500
7,7
2000
-
-
Tab. 9.5 Průběh metody VAM,
Hodnoty proměnných x22 a x23 dopočítáme tak, aby vyhovovali 4. a 5. rovnici
z omezujících podmínek (9.1), tedy
S2 : 800 + x22 = 900,
S3 : 0 + x23 = 500.
Proto x22 = 100, resp. x23 = 500 (zapíšeme do pole D2 S2 , resp. D2 S3 ). Získali jsme tak
výchozí základní přípustné řešení, jež je vidět v tab. 9.6.
D1
S1
30
×
S2
10
800
D2
15
600
20
100
1
3
S3
K
∆i
5
×
800 5,5,×
2
P 600
900
∆j 15,× 10,10
12
500 1200 3,8
4
500
7,7
2000
-
-
Tab. 9.6 Určení výchozího základního řešení dopravní úlohy
9.2.3 Poznámka. Malou číslicí v pravém dolním rohu obsazených polí označujeme
pořadí, v jakém jsme jednotlivá pole obsazovali.
Platí, m + n − 1 = 2 + 3 − 1 = 4. Současně je z tab. 9.6 vidět, že jsou obsazena
právě 4 pole. Základní proměnné jsou tedy x12 , x21 , x22 , x23 , všechny nabývají kladných
hodnot, řešení je proto nedegenerované.
Hodnotu celkových přepravních nákladů pro toto řešení určíme z účelové funkce:
z = 10 · 800 + 15 · 600 + 20 · 100 + 12 · 500 = 25 000 Kč.
86
9 DOPRAVNÍ ÚLOHA
Výchozí řešení ještě nemusí být optimální. Zda je, či nikoliv, to zjistíme testem
optima, jemuž je věnována následující kapitola.
9.2.4 Úkoly a problémy k modulu 9.2
1. Nalezněte metodou VAM výchozí základní přípustné řešení dopravní úlohy,
přičemž kapacity dodavatelů, požadavky spotřebitelů a přepravní sazby udává
tab. 9.7.
cij
S1
S2
S3
S4
K
D1
8
2
9
6
180
D2
11
12
12
11
70
D3
7
2
10
13
80
P
75
100
75
80
330
Tab. 9.7 Zadání dopravní úlohy, úkol 1.
2. Uvažujte dopravní úlohu, jejíž vstupní údaje znazorňuje tabulka 9.8. Metodou
VAM nalezněte výchozí řešení této úlohy.
cij
S1
S2
S3
S4
K
D1
3
15
10
19
160
D2
5
16
12
7
240
D3
2
8
9
6
120
P
120
100
160
140
520
Tab. 9.8 Zadání dopravní úlohy, úkol 2.
3. Nalezněte metodou VAM výchozí základní přípustné řešení dopravní úlohy,
přičemž kapacity dodavatelů, požadavky spotřebitelů a přepravní sazby udává
tab. 9.9.
cij
S1
S2
S3
K
D1
11
18
3
170
D2
14
5
4
100
D3
2
6
9
80
P
90
180
80
350
Tab. 9.9 Zadání dopravní úlohy, úkol 3.
9.3 Test optima
87
Řešení. 
1.

75 20 5 80
 0 0 70 0 , z = 2 165.
0 80 0 0

2.

120 0
40
0
 0
0 100 140 , z = 3 920.
0 100 20
0

3.
9.3

10 80 80
 0 100 0 , z = 2 450.
80 0
0
Test optima
Není-li řešení dopravní úlohy optimální, lze nalézt lepší řešení, tj. základní přípustné řešení s nižší hodnotou celkových přepravních nákladů. Za účelem zjištění, zda uvažované
řešení je či není optimální, budeme provádět tzv. test optima. Tento test je založen na
teorii duality v lineárním programování. Pro provedení testu je třeba mít obsazených
právě m + n − 1 polí (viz s. 83, 4. bod postupu VAM a příslušná poznámka 9.2.1).
Je-li tato podmínka splněna, přidáme sloupec řádkových čísel ui , i = 1, . . . , m a řádek
sloupcových čísel vj , j = 1, . . . , n. Při konstrukci těchto řádkových a sloupcových čísel
budeme požadovat, aby u všech obsazených polí platil vztah
ui + vj = cij .
(9.2)
Protože čísel ui a vj je m + n, ale obsazených polí je m + n − 1 (jedná se o soustavu
m + n − 1 rovnic o m + n neznámých), je třeba jedno z čísel ui a vj zvolit (volba je
libovolná, zpravidla se volí u1 = 0) a ostatní dopočítat z rovnic (9.2).
Pomocí teď už známých čísel ui a vj určíme u všech proškrtnutých polí tzv.
nepřímé sazby c0ij , podle vztahů
ui + vj = c0ij .
(9.3)
Nepřímé sazby c0ij budeme zapisovat do levých dolních rohů jednotlivých proškrtnutých
polí. Nyní již můžeme provést vlastní test optima spočívající v porovnání přímých sazeb
cij s nepřímými sazbami c0ij u všech proškrtnutých polí.
Test optima:
1. Platí-li u všech proškrtnutých polí vztah c0ij ≤ cij , pak dané řešení je optimální.
Přitom:
a) Jsou-li všechny tyto nerovnice splněny ostře, jedná se o jediné optimální
řešení.
88
9 DOPRAVNÍ ÚLOHA
b) Je-li některá z nerovnic c0ij ≤ cij splněna jako rovnice c0ij = cij , pak existuje
i jiné optimální řešení (úloha má alternativní řešení).
2. Existuje-li proškrtnuté pole, kde c0ij > cij , pak dané řešení není optimální.
9.3.1 Příklad. Budeme pokračovat v příkladu 9.1.2, resp. 9.2.2. Provedeme test optima.
Řešení. Zpravidla test optima provádíme v tabulce, v níž jsme nalezli výchozí základní řešení (tab. 9.6). K tabulce pouze přidáme sloupec řádkových čísel ui a řádek
sloupcových čísel vj , viz tab. 9.10.
S1
30
×
D1
5
S2
10
800
2
D2
15
600
P
∆j
vj
600
15,×
5
1
20
100
S3
∆i
ui
5
×
800 5,5,× 0
2
12
500 1200 3,8
3
900
10,10
10
K
10
4
500
7,7
2
2000
-
-
-
Tab. 9.10 Provedení testu optima
Dodržíme konvenci o volbě u1 = 0. Ze vztahů (9.2) (přes obsazená pole!) vypočítáme
postupně
v2 = 10, u2 = 10, v1 = 5 a v3 = 2.
U všech proškrtnutých polí nyní můžeme ze vztahů (9.3) určit nepřímé sazby c0ij . Je
zřejmé, že řešení
0 800 0
X=
600 100 500
je jediné optimální řešení, neboť u obou proškrtnutých polí (D1 S1 a D1 S3 ) je c0ij < cij
(5 < 30 a 2 < 5). Celkové přepravní náklady jsou ve výši z = 25 000 Kč.
9.3.2 Úkoly a problémy k modulu 9.3
1. Zjistěte, zda výchozí řešení z úkolu 1. na str. 86 je optimální.
2. Zjistěte, zda výchozí řešení z úkolu 2. na str. 86 je optimální.
3. Zjistěte, zda výchozí řešení z úkolu 3. na str. 86 je optimální.
9.4 Zlepšování řešení
89
Řešení.
1. Není optimální.
2. Je optimální.
3. Není optimální.
9.4
Zlepšování řešení
Nastane-li případ, že pro nějaké neobsazené pole platí c0ij > cij , pak testované řešení
není optimální a lze najít lepší řešení.
Postup pro určení lepšího základního řešení
1. Najdeme políčko, kde c0ij > cij . Pokud je těchto políček více, vybereme to z nich,
kde je rozdíl c0ij − cij největší. Tím jsme určili vstupující proměnnou xij .
2. Vytvoříme tzv. uzavřený okruh, tj. mnohoúhelník se sudým počtem vrcholů, vrcholy mohou být jen obsazená pole a vybrané neobsazené pole, svislé a vodorovné
hrany se střídají.
3. Neobsazené pole v okruhu označíme znaménkem „+ÿ. V dalších polích - vrcholech
uzavřeného okruhu - střídáme znaménka . . . , +, −, +, . . . .
4. Určíme vystupující proměnnou. Najdeme nejmenší hodnotu ze všech polí označených „−ÿ. Pokud je takových polí více, volíme jediné z nich (libovolně). Toto
pole určuje vystupující proměnnou.
5. Přepočet tabulky. Vybranou sazbu, tj. minimum z „−ÿ-ových polí, přičteme k
polím označeným „+ÿ a odečteme od polí označených „−ÿ. Ostatní políčka zůstávají beze změny.
9.4.1 Poznámka.
K bodu 2.: Uzavřený okruh lze předepsaným způsobem ke každému proškrtnutému
poli přes obsazená pole sestrojit vždy právě jeden (za předpokladu základního řešení
s m + n − 1 obsazenými poli). Uzavřený okruh budeme značit v tabulce vodorovnými
a svislými čárkami, jak je vidět např. v tab. 9.12. Tyto čárky ale budou vyznačený jen
u „vrcholů uzavřeného okruhuÿ, neboť při zlepšení řešení se změní hodnoty pouze těch
proměnných, které jsou přiřazeny těmto políčkům (vrcholům uzavřeného okruhu).
K bodu 3.: Pro označení políček symbolem „+ÿ, resp. „−ÿ máme vyhrazen levý horní
roh příslušného pole.
K bodu 4.: Pokud je ve více „−ÿ-ových polích nejmenší hodnota, v novém (zlepšeném) řešení proškrtneme právě jedno z těchto polí (odpovídající vystupující proměnné),
ostatní tato pole zůstávají obsazená, byť obsazená hodnotou 0. Je zřejmé, že v takovém
případě je nové řešení řešením degenerovaným.
K bodu 5.: Přepočet tabulky, tedy nové (zlepšené) řešení je potřeba přepsat do nové
90
9 DOPRAVNÍ ÚLOHA
tabulky. V ní už samozřejmě nebude sloupec ani řádek diferencí (sloužily pouze pro
nalezení výchozího řešení). Je ale třeba na novém řešení provést test optima, tzn. nově
určit řádková a sloupcová čísla a nepřímé sazby. V případě, že řešení není optimální,
musíme jej dále zlepšovat.
9.4.2 Příklad. Určete optimální řešení dopravní úlohy pro 4 dodavatele a 5 spotřebitelů, přičemž kapacity dodavatelů, požadavky spotřebitelů a přepravní sazby udává
tab. 9.11.
cij
S1
S2
S3
S4
S5
K
D1
2
6
1
8
13
1000
D2
11
5
9
4
7
2000
D3
7
3
10
6
12
2500
D4
1
2
1
1
1
500
P
1500
700
1200
1600
1000
6000
Tab. 9.11 Zadání dopravní úlohy z příkladu 9.4.2
Řešení. Nalezení výchozího základního řešení úlohy metodou VAM je provedeno
v tabulce 9.12.
S1
S2
2
×
D1
×
-2
×
5
1
D4
1500
×
×
700
0
4 +
10 +
5
7
1
2+
1
×
∆i
1000 1,1,×
ui
0
7
500
2000 1,1,1,1,1,5 7
3
6
12
×
100
4
×
×
1500
200
K
13
6
8
3−
7
D3
-3
9 −
5
S5
8
×
1000
-6
×
S4
1
2
11
D2
S3
6
2500 3,3,3,3,3,4 9
8
9
1 −
×
-1
-5
2
-2
P
1500
700
1200
1600
∆j 1,5,4,4,× 1,2,2,2,2,× 0,8,1,1,1,1 3,2,2,2,2,2
vj
-2
-6
1
-3
1
500
500 0,×
1
1
1000
6000
6,5,5,×
0
-
-
-
Tab. 9.12 Nalezení výchozího řešení a test optima, příklad 9.4.2
Následně, stále v tabulce 9.12, byl proveden test optima tohoto řešení. Nalezené základní řešení je nedegenerované, neboť všech m + n − 1 = 8 základních proměnných
9.4 Zlepšování řešení
91
(obsazená pole) nabývá kladných hodnot. Představuje přepravu zboží s celkovými přepravními náklady
z1 = 1 · 1000 + 4 · 1500 + 7 · 500 + 7 · 1500 + 3 · 700 + 10 · 200 + 6 · 100 + 1 · 500 = 26 200 Kč.
Řešení není optimální, neboť u proškrtnutého pole D4 S3 je nepřímá sazba větší než
přímá (2 > 1). Minimum z „−ÿ-ových polí, tj. hodnotu min{200, 1500, 500} = 200,
odečteme od „−ÿ-ových polí a přičteme k „+ÿ-ovým polím. Získané zlepšené řešení je
zobrazeno v tab. 9.13.
S1
S2
2
5
3
1500
10
700
6
×
700
×
-1
P
vj
1
×
200
700
-5
1200
1
-5
1500
-1
2500 8
9
2
×
2000 6
12
300
9
1
D4
7
1300
7
7
D3
1000 0
4
×
1
13
1
9
×
K ui
×
-2
11
5
8
×
1000
-5
×
D2
S5
1
×
-1
S4
6
×
D1
S3
1
1
×
300
500 0
1600
-2
1000
1
6000 - -
-2
Tab. 9.13 Zlepšené řešení a test optima, příklad 9.4.2
Řešení z tab. 9.13 je již optimální. Celkové přepravní náklady jsou
z2 = 1 · 1000 + 4 · 1300 + 7 · 700 + 7 · 1500 + 3 · 700 + 6 · 300 + 1 · 200 + 1 · 300 = 26 000 Kč.
9.4.3 Poznámka. Optimální řešení značí v celkových přepravních nákladech úsporu
200 Kč ve srovnání s předchozím (v tomto případě výchozím) řešením. Přitom minimum
z „−ÿ-ových polí, tj. min{200, 1500, 500}, je také rovno 200. To není bez souvislosti.
Obecně totiž platí, že úspora zlepšeného řešení vůči předchozímu je rovna minimu
z „−ÿ-ových polí vynásobenému rozdílem nepřímé a přímé sazby v klíčovém poli, tj.
∆z = (c0ij − cij ) ·
min
„−ÿ-ová pole
{xij }.
V příkladu 9.4.2 je tato úspora rovna
∆z21 = z1 − z2 = (2 − 1) · min{200, 1500, 500} = 200 Kč.
92
9 DOPRAVNÍ ÚLOHA
9.4.4 Úkoly a problémy k modulu 9.4
1. Určete optimální řešení dopravní úlohy zadané v úkolu 1. na str. 86.
2. Určete optimální řešení dopravní úlohy zadané v úkolu 3. na str. 86.
Řešení.
1.

Xopt

0 95 5 80
=  0 0 70 0 , zmin = 2 090.
75 5 0 0

2.
9.5
Xopt

90 0 80
=  0 100 0 , zmin = 2 210.
0 80 0
Degenerované a alternativní řešení dopravních úloh
V předchozím textu byly oba speciální typy řešení dopravních úloh, degenerované i
alternativní, zmiňovány, a to poměrně podrobně. Protože však oba tyto typy řešení
mají svá specifika, zaslouží více pozornosti.
9.5.1 Degenerované řešení
Základní řešení dopravní úlohy je degenerované, jestliže některá ze základních proměnných tohoto řešení nabývá nulové hodnoty. Jelikož při dodržení pravidel postupu VAM
při určení výchozího základního řešení (viz str. 83) i postupu pro získání zlepšeného
řešení (viz str. 89) vždy obdržíme řešení, kde všem m + n − 1 základním proměnným
odpovídá právě m + n − 1 obsazených polí, znamená to, že degenerované řešení poznáme podle toho, že některé obsazené pole je obsazeno hodnotou nula. Na druhou
stranu, jsou-li v tabulce všechna obsazená pole obsazena kladnou hodnotou, jedná se
o nedegenerované řešení.
Test optima degenerovaného řešení provádíme naprosto shodně jako v případě nedegenerovaného řešení (postup je popsán v modulu 9.3). Podstatné pro test optima
je totiž jen to, zda dané políčko tabulky je obsazené či nikoliv, bez ohledu na to, zda
hodnotou kladnou či nulovou.
Podobně i postup při zlepšování degenerovaného řešení se nijak neliší od postupu
při zlepšování nedegenerovaného řešení (postup viz modul 9.4). Je ale dobré si na tomto
místě uvědomit určitá specifika. Např. se můžeme v případě zlepšování degenerovaného
řešení setkat s tím, že některé (alespoň jedno) „−ÿ-ové pole uzavřeného okruhu je
obsazeno hodnotou nula. Potom i minimum z „−ÿ-ových polí je rovno nule. Nové,
„zlepšenéÿ, řešení je pak totožné s řešením předchozím. Přitom předchozí řešení se
může jevit jako „neoptimálníÿ a současně nové řešení jako optimální (test optima vyjde
9.5 Degenerované a alternativní řešení dopravních úloh
93
negativně, resp. pozitivně). Tento zdánlivý rozpor je dán tím, že uvažovaná řešení se
liší množinou základních proměnných. Uvedenou skutečnost dokládá příklad 9.5.2.
9.5.2 Příklad. Určete optimální řešení dopravní úlohy pro 3 dodavatele a 4 spotřebitele, přičemž kapacity dodavatelů, požadavky spotřebitelů a přepravní sazby udává
tab. 9.14.
cij
S1
S2
S3
S4
K
D1
12
18
3
2
600
D2
20
6
5
3
500
D3
3
7
12
1
400
P
450
500
400
150
1500
Tab. 9.14 Zadání dopravní úlohy z příkladu 9.5.2
Řešení. Tabulka 9.15 představuje výchozí základní řešení dopravní úlohy. Získané
bylo metodou VAM. Ve druhém kroku metody VAM jsme obsadili políčko D2 S2 hodnotou 500, čímž jsme současně vyčerpali kapacitu dodavatele D2 i uspokojili požadavek
spotřebitele S2 . Z možností „proškrtnout řádekÿ, „proškrtnout sloupecÿ, jsme zvolili
možnost „proškrtnout řádekÿ. Výhodou této volby je, že všechny ostatní proměnné
(políčka řádku D1 ) potom získáme velice snadno a rychle, dopočtem „po sloupcíchÿ,
tj. tak, aby se celkové množství dopraveného zboží každému spotřebiteli od všech dodavatelů rovnalo požadavku příslušného spotřebitele.
S1
12 −
+
D1
50
18
K
400
150
600 1,1
5
6
20
6
5
3
×
500
1
9
12
×
-6
500
1,12
18
0
500 2,2 -12
-10
7
×
400
×
-9
∆i ui
2
4
3 +
450
9,8
12
S4
3
0
2
0
−
P
∆j
vj
S3
3
×
D2
D3
S2
400
2,2
3
1
×
-7
150
1,1
2
400 2,× -9
1500 -
-
Tab. 9.15 Nalezení výchozího řešení a test optima, příklad 9.5.2
Základní proměnná x12 = 0, takže se jedná o řešení degenerované. Určíme řádková
čísla ui , i = 1, . . . , 3 a sloupcová čísla vj , j = 1, . . . , 4. Následně pak u proškrtnutých
94
9 DOPRAVNÍ ÚLOHA
polí nepřímé sazby c0ij . Test optima je negativní, neboť v poli D3 S2 je c0ij > cij (9 > 7).
K tomuto poli je jednoznačně přiřazen uzavřený okruh, jak je patrno z tab. 9.15. Jedno
z „−ÿ-ových polí uzavřeného okruhu je obsazeno hodnotou nula (x12 = 0), a tudíž
„zlepšení řešeníÿ nebude znamenat snížení celkových přepravních nákladů. Pouze se
v množině základních proměnných místo proměnné x12 objeví proměnná x32 .
S1
S2
12
D1
S3
18
3
×
50
S4
K
ui
600
0
2
400
150
16
20
×
D2
6
5
×
500
2
×
-7
3
400
0
P
vj
450
12
500
16
500 -10
-8
7
D3
3
12
1
×
-6
×
400 -9
150
2
1500 -
-7
400
3
Tab. 9.16 Optimální řešení, příklad 9.5.2
Nové řešení, jež zobrazuje tab. 9.16, je jediné optimální řešení této úlohy a je degenerované. Jak řešení příslušné tabulce 9.15, tak řešení příslušné tabulce 9.16 má tvar


50
0 400 150
0 .
X =  0 500 0
400 0
0
0
Celkové přepravní náklady jsou z = 5 100 Kč.
9.5.3 Alternativní řešení
Zjistíme-li, že dané řešení (buď výchozí nebo i zlepšené) dopravní úlohy je optimální (tj.
pro všechna neobsazená pole platí c0ij ≤ cij ) a alespoň pro jedno neobsazené pole platí
c0ij = cij , existuje další řešení se stejnou hodnotou účelové funkce, tzv. alternativní
řešení. Nalezení alternativního řešení je podobné s hledáním optimálního řešení. Pole,
pro které platí c0ij = cij , je klíčové pole. Sestrojíme uzavřený okruh k tomuto políčku a
známým způsobem přepočteme tabulku.
9.5.4 Příklad. Určete všechna základní optimální řešení dopravní úlohy pro 3 dodavatele a 4 spotřebitele. Kapacity dodavatelů, požadavky spotřebitelů a přepravní sazby
udává tab. 9.17.
9.5 Degenerované a alternativní řešení dopravních úloh
95
cij
S1
S2
S3
S4
K
D1
16
8
9
1
600
D2
15
1
8
14
800
D3
4
6
8
5
200
P
300
300
600
400
1600
Tab. 9.17 Zadání dopravní úlohy z příkladu 9.5.4
Řešení. Nejprve nalezneme výchozí základní přípustné řešení (metodou VAM), viz
tab. 9.18. Toto řešení je optimální, neboť pro všechna proškrtnutá pole platí c0ij ≤ cij .
Přitom existuje proškrtnuté pole (pole D2 S1 ), kde je tato neostrá nerovnice splněna
jako rovnost (15 = 15). Zřejmě tedy existuje další základní řešení se stejnou hodnotou
účelové funkce. Postup nalezení tohoto alternativního řešení je shodný s postupem při
zlepšování řešení, viz modul 9.4. K poli D2 S1 vytvoříme uzavřený okruh, příslušným
způsobem označíme vrcholy tohoto okruhu symboly „+ÿ či „−ÿ. Minimum z „−ÿ-ových
polí je min{100, 500} = 100.
S1
−
D1
S2
16
5
4
K
9
1 −
300
15
S4
400
2
8
14
×
500
4
6
8
800 7,7,7,7 -1
0
×
×
×
-10
-3
-11
300
300
600
400
11,1,1,1 5,7,7,× 0,1,1,1
4,13,×
16
2
9
1
200
ui
600 7,7,1,7 0
6
3
∆i
1
100
2
15
×
D2
D3
8 +
×
100
+
S3
5
200 1,×
-12
1
P
∆j
vj
1600 -
-
Tab. 9.18 Nalezení výchozího řešení a test optima, příklad 9.5.4
Známým způsobem vytvoříme nové řešení, viz tab. 9.19. Je zákonité, že toto řešení je
opět optimální, že i zde je políčko D1 S1 , kde je nepřímá sazba rovna sazbě přímé. Pokud
bychom k tomuto políčku vytvořili uzavřený okruh a příslušným způsobem vytvořili
„novéÿ řešení, dostali bychom přesně tabulku 9.18, tzn. vrátili bychom se k prvnímu
základnímu optimálnímu řešení dopravní úlohy.
96
9 DOPRAVNÍ ÚLOHA
S1
S2
16
×
D1
S4
9
×
16
K
ui
600
0
1
200
400
2
15
D2
S3
8
100
1
8
300
14
×
400
800 -1
0
4
6
D3
200
×
P
vj
300
16
-10
300
2
8
5
×
-3
×
200 -12
-11
600
9
400
1
1600 -
Tab. 9.19 Alternativní řešení, příklad 9.5.4
Celkově můžeme poznamenat, že řešení


100 0 100 400
X1 =  0 300 500 0 
200 0
0
0
a


0
0 200 400
X2 =  100 300 400 0 
200 0
0
0
jsou jediná dvě základní optimální řešení úlohy. Celkové přepravní náklady jsou samozřejmě v obou případech stejné a rovné hodnotě z = 8 000 Kč.
9.5.5 Nezákladní optimální řešení
Dopravní úloha může mít jediné optimální řešení. V tom případě je zcela jistě řešením
základním.
Má-li ale úloha alternativní řešení, tj. více (alespoň dvě) základních optimálních řešení, pak úloha může mít i nezákladní optimální řešení. Každé přípustné řešení, jež
je konvexní lineární kombinací základních optimálních řešení, je také optimální řešení.
Prakticky bychom nezákladní řešení obdrželi tak, že přepočet tabulky, viz bod 5. postupu na str. 89, nebudeme provádět s minimem z „−ÿ-ových polí, ale hodnota, kterou
přičteme k polím označeným „+ÿ a odečteme
od polí označených
„−ÿ, musí být mezi
nulou a tímto minimem, tj. z intervalu
0,
min
„−ÿ-ová pole
{xij } .
To, zda optimálních nezákladních řešení bude konečně mnoho či nekonečně mnoho,
zavisí na tom, zda úloha je celočíselná (xij ∈ N0 , přepravované zboží je počítáno na
kusy, je nedělitelné), či zda proměnné mohou nabývat libovolných reálných hodnot
z nějakého intervalu (xij ∈ R+
0 , přepravované zboží je látkové povahy, je libovolně
dělitelné).
9.5 Degenerované a alternativní řešení dopravních úloh
97
9.5.6 Úkoly a problémy k modulu 9.5
1. Rozhodněte, zda optimální řešení jsou degenerovaná či nedegenerovaná.
a) Řešení úkolu 1., str. 92,
b) Řešení úkolu 2., str. 92.
2. Nalezněte všechna základní optimální řešení dopravních úloh. O každém z nich
rozhodněte, zda je či není degenerované.
a)
b)
cij
S1
S2
S3
S4
K
D1
2
4
11
6
400
D2
4
2
7
5
500
D3
1
8
5
9
100
P
200
200
300
300
1000
cij
S1
S2
S3
S4
K
D1
10
12
10
16
18
D2
12
10
4
18
20
D3
12
12
0
24
10
D4
14
16
24
18
40
P
22
12
30
24
88
Řešení.
1. a) Je nedegenerované.
b) Je degenerované.

2.
a) Xopt

200 0
0 200
=  0 200 200 100 , zmin = 4 400.
0
0 100 0
Jediné optimální řešení, není degenerované.

b) Xopt,1


6 12 0 0
18 0 0 0
 0 0 20 0
 0 0 20 0 


=
 0 0 10 0 , Xopt,2 =  0 0 10 0
16 0 0 24
4 12 0 24
Řešení jsou degenerovaná.


, zmin = 940.

98
9.6
9 DOPRAVNÍ ÚLOHA
Nevyrovnaná dopravní úloha
Pojem nevyrovnané dopravní úlohy jsme již zavedli v definici 9.1.1. Uvažujme tedy
v tomto modulu dopravní úlohu nevyrovnanou, tj. nechť
m
X
ai 6=
i=1
n
X
bj .
j=1
Nevyrovnanou dopravní úlohu budeme vždy řešit jejím převedením na úlohu vyrovnanou. Toho docílíme zavedením jednoho fiktivního činitele – dodavatele nebo odběratele.
Rozlišujeme dva typy nevyrovnaných dopravních úloh podle toho, zda převyšuje celková kapacita zboží na straně dodavatelů nad celkovými požadavky všech spotřebitelů
či naopak. V souladu s tímto dělením povedeme další výklad.
a)
m
P
ai >
i=1
n
P
bj
j=1
V případě, že celková kapacita zboží na straně dodavatelů převyšuje nad celkovými požadavky všech spotřebitelů, je třeba zavést fiktivního spotřebitele Sf
m
n
P
P
s jeho požadavkem bf =
ai −
bj . Tím získáme dopravní úlohu, která má
i=1
j=1
proti původní o jednoho spotřebitele více, ale je to úloha vyrovnaná.
Při samotném řešení této (vyrovnané) dopravní úlohy je třeba na všechny spotřebitele – ať už se jedná o skutečného či fiktivního – pohlížet stejně. Skutečnost, zda
se jedná o skutečného či fiktivního spotřebitele je pak rozhodující při interpretaci
řešení získaného řešením příslušné vyrovnané úlohy. Když by např. dodavatel Dr
měl dodat xrf jednotek zboží fiktivnímu spotřebiteli Sf , ve skutečnosti (jelikož
spotřebitel Sf neexistuje) by toto zboží bylo nedodáno, zůstalo by dodavateli Dr
na skladě, a tudíž přepravní náklady po cestě Dr Sf jsou nulové. Proto platí:
cif = 0,
b)
m
P
i=1
ai <
n
P
i = 1, 2, . . . , m.
bj
j=1
V případě, že celkové požadavky spotřebitelů převyšují nad celkovou kapacitou
zboží na straně dodavatelů, je třeba zavést fiktivního dodavatele Df s jeho kapan
m
P
P
citou af =
bj −
ai . Tím získáme dopravní úlohu, která má proti původní
j=1
i=1
o jednoho dodavatele více, ale je to úloha vyrovnaná.
Při samotném řešení této (vyrovnané) dopravní úlohy je třeba opět na všechny
dodavatele – ať už se jedná o skutečného či fiktivního – pohlížet stejně. Skutečnost, zda se jedná o skutečného či fiktivního dodavatele je pak rozhodující při
interpretaci řešení získaného řešením příslušné vyrovnané úlohy. Když by např.
fiktivní dodavatel Df měl dodat xf s jednotek zboží spotřebiteli Ss , ve skutečnosti
9.6 Nevyrovnaná dopravní úloha
99
by toto zboží nebylo dodáno (neexistuje ani dodavatel, natož jeho zboží), požadavek spotřebitele Ss by nebyl plně uspokojen. Přepravní náklady po cestě Df Ss
jsou nulové. Proto platí:
cf j = 0,
j = 1, 2, . . . , n.
9.6.1 Příklad. Určete optimální řešení dopravní úlohy pro 3 dodavatele a 5 spotřebitelů, přičemž kapacity dodavatelů, požadavky spotřebitelů a přepravní sazby udává
tab. 9.20.
cij
S1
S2
S3
S4
S5
K
D1
2
6
1
8
13
1000
D2
11
5
9
4
7
2000
D3
7
3
10
6
12
2500
P
1500
700
1200
1600
1000
Tab. 9.20 Zadání dopravní úlohy z příkladu 9.6.1
Řešení. Nejprve zjistíme, zda se jedná o vyrovnanou dopravní úlohu.
3
P
Součet kapacit všech dodavatelů je
ai = 5 500 a součet požadavků všech spotřebitelů
i=1
je
5
P
bj = 6 000. Úloha je tedy nevyrovnaná, typu „b)ÿ, proto zavedeme fiktivního
j=1
dodavatele Df s kapacitou af = 6 000 − 5 500 = 500. Přepravní sazby od tohoto
dodavatele ke všem spotřebitelům mají nulovou hodnotu. Takto změněná dopravní
úloha je už vyrovnaná, viz tab. 9.21
cij
S1
S2
S3
S4
S5
K
D1
2
6
1
8
13
1000
D2
11
5
9
4
7
2000
D3
7
3
10
6
12
2500
Df
0
0
0
0
0
500
P
1500
700
1200
1600
1000
6000
Tab. 9.21 Zadání již vyrovnané dopravní úlohy, příklad 9.6.1
Nalezení výchozího základního řešení úlohy metodou VAM je provedeno v tabulce 9.22.
Následně, stále v tabulce 9.22, byl proveden test optima tohoto řešení. Nalezené základní řešení je nedegenerované, neboť všech m + n − 1 = 8 základních proměnných
(obsazená pole) nabývá kladných hodnot. Představuje přepravu zboží s celkovými přepravními náklady
100
9 DOPRAVNÍ ÚLOHA
z1 = 1 · 1000 + 4 · 1500 + 7 · 500 + 7 · 1500 + 3 · 700 + 10 · 200 + 6 · 100 + 0 · 500 = 25 700 Kč.
S1
S2
S3
2
6
×
D1
5
×
5
×
1
1500
700
5
0
×
-2
2000 1,1,1,1,1,5 7
6
3
6
12
×
2500 3,3,3,3,3,4 9
9
0 −
0
×
1
0
8
×
-6
ui
7
500
100
7
0+
×
Df
10 +
200
4
1000 1,1,×
0
4 +
1500
8
3−
7
D3
-3
9 −
∆i
13
×
2
11
K
8
×
1000
-6
×
D2
S5
1
×
-2
S4
0
500
500 0,×
0
1
-3
P
1500
700
1200
1600
∆j 2,5,4,4,× 3,2,2,2,2,× 1,8,1,1,1,1 4,2,2,2,2,2
vj
-2
-6
1
-3
1000
6000
7,5,5,×
0
-
-
-
Tab. 9.22 Nalezení výchozího řešení a test optima, příklad 9.6.1
Řešení není optimální, neboť u proškrtnutého pole Df S3 je nepřímá sazba větší než
přímá (1 > 0). Minimum z „−ÿ-ových polí, tj. hodnotu min{200, 1500, 500} = 200,
odečteme od „−ÿ-ových polí a přičteme k „+ÿ-ovým polím. Získané zlepšené řešení je
zobrazeno v tab. 9.23.
S1
S2
2
6
×
D1
4
×
3
10
700
6
×
700
0
-2
P
vj
×
12
×
300
0
0
200
-6
1500
-1
2000 6
2500 8
9
0
×
7
1300
9
Df
1000 0
7
7
1500
×
1
9
×
1
K ui
13
×
-2
5
×
5
S5
8
1000
-5
11
D3
S4
1
×
-1
D2
S3
0
×
300
500 -1
1600
-2
1000
1
6000 - -
-3
700
-5
1200
1
Tab. 9.23 Zlepšené řešení a test optima, příklad 9.6.1
9.6 Nevyrovnaná dopravní úloha
101
Řešení z tab. 9.23 je již optimální. Z řešení vyplývá, že požadavky spotřebitelů S3 a S5
nebudou plně uspokojeny. Celkové přepravní náklady jsou
z2 = 1 · 1000 + 4 · 1300 + 7 · 700 + 7 · 1500 + 3 · 700 + 6 · 300 + 0 · 200 + 0 · 300 = 25 500 Kč.
9.6.2 Úkoly a problémy k modulu 9.6
1. Řešte dopravní úlohu zadanou tabulkou 9.24. Určete všechna základní optimální
řešení úlohy a rozhodněte, zda jsou degenerovaná.
cij
S1
S2
S3
S4
K
D1
18
16
10
12
130
D2
8
12
12
5
150
D3
20
18
12
6
140
P
100
120
90
80
Tab. 9.24 Zadání dopravní úlohy 1.
2. Řešte dopravní úlohu zadanou tabulkou 9.25. Určete všechna základní optimální
řešení úlohy a rozhodněte, zda jsou degenerovaná.
cij
S1
S2
S3
S4
K
D1
17
15
9
11
60
D2
8
12
12
5
50
D3
19
17
11
5
70
P
50
60
44
40
Tab. 9.25 Zadání dopravní úlohy 2.
Řešení.
1. Xopt,1




0 40 90 0 0
0 70 60 0 0
=  100 50 0 0 0 , Xopt,2 =  100 50 0 0 0 .
0 30 0 80 30
0
0 30 80 30
Obě řešení jsou nedegenerovaná, z = 3960.

2. Xopt,1


0 16 44 0
0 46 14 0
 50 0 0 0 
 50 0 0 0


=
 0 30 0 40 , Xopt,2 =  0 0 30 40
0 14 0 0
0 14 0 0


.

102
9 DOPRAVNÍ ÚLOHA
Obě řešení jsou degenerovaná, z = 1746.
9.7 Shrnutí 9. kapitoly
103
9.7 Shrnutí 9. kapitoly
Klíčová slova:
Dopravní úloha, dopravní úloha vyrovnaná, nevyrovnaná, Vogelova aproximační
metoda, výchozí základní řešení, test optima, zlepšování řešení, optimální řešení, degenerované řešení, alternativní řešení.
Základní úlohy:
•
•
•
•
Řešení vyrovnané dopravní úlohy.
Řešení nevyrovnané dopravní úlohy.
Určení alternativních řešení dopravní úlohy.
Stanovení všech základních optimálních řešení dopravní úlohy.
Doporučená literatura pro hlubší studium:
[Holoubek]:
[Jablonský]:
[Kříž]:
[Mošová]:
str.
str.
str.
str.
80–100,
91–102,
50–69,
65–72.
9.8 Test ke kapitole 9
1. Řešte dopravní úlohu zadanou tabulkou 9.26. Přitom určete všechna základní
optimální řešení úlohy.
cij
S1
S2
S3
S4
K
D1
17
15
9
11
60
D2
8
12
12
5
70
D3
19
17
11
5
70
P
50
56
44
40
Tab. 9.26 Zadání dopravní úlohy 1.
104
9 DOPRAVNÍ ÚLOHA
2. Řešte dopravní úlohu zadanou tabulkou 9.27. Určete všechna základní optimální
řešení úlohy.
cij
S1
S2
S3
K
D1
11
18
2
40
D2
14
5
4
20
D3
2
6
9
16
P
18
36
16
Tab. 9.27 Zadání dopravní úlohy 2.
3. Řešte dopravní úlohu zadanou tabulkou 9.28. Určete všechna základní optimální
řešení úlohy.
cij
S1
S2
S3
S4
K
D1
9
7
18
14
48
D2
21
5
17
12
32
D3
8
4
10
11
24
P
28
24
20
32
Tab. 9.28 Zadání dopravní úlohy 3.
Řešení.

1. Xopt,1



0 16 44 0 0
0 36 24 0 0
=  50 20 0 0 0 , Xopt,2 =  50 20 0 0 0 , z = 1 816.
0 20 0 40 10
0 0 20 40 10

2. Xopt

18 0 16 6
=  0 20 0 0 , z = 426.
0 16 0 0

3. Xopt,1
Xopt,3



28 0 0 20
28 20 0 0
=  0 24 0 8 , Xopt,2 =  0 4 0 28 ,
0 0 20 4
0 0 20 4


28 0 0 20
=  0 20 0 12 , z = 992.
0 4 20 0
105
10
PŘIŘAZOVACÍ PROBLÉM
Cílem studia kapitoly je:
• pochopit princip přiřazovacího problému,
• naučit se řešit přiřazovací problém minimalizačního typu,
• naučit se řešit přiřazovací problém maximalizačního typu.
Přiřazovacím problémem chápeme úlohu optimálního přiřazení např. strojů na pracovišti, pracovišť k pracovníkům, zákazníků k poskytovatelům služeb, atd., za předpokladu, že právě jeden činitel 1. druhu je přiřazen právě jednomu činiteli 2. druhu.
Přiřazovací problém lze chápat jako dopravní úlohu, kdy počet dodavatelů je roven
počtu spotřebitelů (matice sazeb je čtvercová řádu n), kapacity všech dodavatelů i
požadavky všech spotřebitelů jsou rovny jedné, a přitom hledáme celočíselné řešení.
Pro takto specifický typ dopravní úlohy byla vyvinuta také speciální metoda řešení
minimalizační přiřazovací úlohy, tzv. maďarská metoda. Nejprve se tedy seznámíme
s problematikou řešení minimalizačních úloh, následně se budeme věnovat i řešení maximalizačních úloh.
10.1
Přiřazovací problém minimalizačního typu
Pro získání prvotní představy o přiřazovacím problému uvádíme následující příklad.
10.1.1 Příklad. Podnik má k dispozici 3 jeřáby, které má přepravit na 3 pracoviště
(každý jeřáb právě na jedno pracoviště). Vzdálenosti v km mezi stanovišti jeřábu Ji , i =
= 1, 2, 3, a pracovišti Pj , j = 1, 2, 3, jsou uvedeny v tabulce:
cij
J1
J2
J3
P1
4
1
4
P2
3
2
5
P3
1
6
3
Nalezněte optimální řešení, tj. takový plán přepravy, při kterém bude celkový počet
ujetých kilometrů minimální.
Řešení. Na tomto místě nám bude stačit daný problém vyjádřit matematickými
prostředky, tj. vytvořit matematický model, vlastní řešení úlohy je obsahem příkladu 10.1.3. Je třeba stanovit, který z jeřábů má být přepraven na které pracoviště
tak, aby v součtu přepravní vzdálenost všech jeřábů byla minimální. Zavedeme bivalentní proměnnou
xij , i = 1, 2, 3, j = 1, 2, 3, přičemž
xij = 1, jestliže i-tý jeřáb je přiřazen na j-té pracoviště,
106
10 PŘIŘAZOVACÍ PROBLÉM
xij = 0, jestliže i-tý jeřáb není přiřazen na j-té pracoviště.
Řešením tedy budeme rozumět čtvercovou

x11
X =  x21
x31
matici třetího (obecně n-tého) řádu

x12 x13
x22 x23  .
x32 x33
Každý jeřáb má být přiřazen právě na jedno pracoviště, proto v každém řádku matice X
musí být právě jedna jednička a n−1 nul. Podobně, každému pracovišti má být přiřazen
právě jeden jeřáb, takže každý sloupec matice X musí obsahovat právě jednu jedničku
a n − 1 nul. V souladu s tím můžeme psát omezující podmínky ve tvaru:
J1 : x11 + x12 + x13 = 1,
J2 : x21 + x22 + x23 = 1,
J3 : x31 + x32 + x33 = 1,
(10.1)
P1 : x11 + x21 + x31 = 1,
P2 : x12 + x22 + x32 = 1,
P3 : x13 + x23 + x33 = 1.
(10.2)
resp.
Podmínky (10.1), resp. (10.2) lze úsporněji zapsat ekvivalentním způsobem následovně:
3
X
xij = 1,
i = 1, 2, 3,
(10.3)
xij = 1,
j = 1, 2, 3.
(10.4)
j=1
resp.
3
X
i=1
Účelová funkce zde vyjadřuje součet přepravních vzdáleností. Má tvar:
z = c11 x11 + c12 x12 + c13 x13 + c21 x21 + · · · + c33 x33 → min.
Zkráceně:
z=
3
3 X
X
cij xij → min.
(10.5)
i=1 j=1
Obecně jde o to, přiřadit n činitelů n jiným činitelům tak, aby součet příslušných
sazeb byl minimální (resp. maximální). Matematický model přiřazovacího problému
nyní zobecníme.
10.1 Přiřazovací problém minimalizačního typu
107
OBECNÝ MATEMATICKÝ MODEL:
z=
n P
n
P
cij xij → min.
i=1 j=1
n
P
j=1
n
P
xij = 1,


i = 1, 2, . . . , n 

xij = 1,

j = 1, 2, . . . , n 

i=1
celkem 2n omezení (rovnic),
1
xij =
%
&
n2 proměnných.
0
Je zřejmé, že n proměnných nabývá hodnoty 1, n2 − n proměnných je rovno 0. Základních proměnných je v úloze 2n − 1 (jde o speciální případ dopravní úlohy, kde
m = n). S vyjímkou triviálního případu n = 1 jde tedy vždy o degenerované řešení
(počet základních proměnných nabývajících nulové hodnoty, tj. stupeň degenerace, je
roven n − 1).
Pro řešení přiřazovacího problému se využívá algoritmus nazývaný maďarská metoda.
Postup při užití maďarské metody
Předpokládáme, že řešená úloha je minimalizační.
1. Provedeme redukci sazeb (cij ) matice:
i) od každého řádku matice odečteme nejmenší sazbu v tomto řádku,
ii) od každého sloupce matice odečteme nejmenší sazbu v tomto sloupci.
2. V redukované matici sazeb vyhledáme tzv. nezávislé nuly, tj. nuly, z nichž se každá
nachází v jiném řádku a jiném sloupci. Budeme je označovat pomocí horního
indexu, tj. 01 . V dané matici je třeba najít maximální počet nezávislých nul,
proto postupujeme následovně:
i) Za nezávislou nulu zvolíme tu, která se nachází na svém řádku či sloupci
samostatně.
ii) Vynecháme řádky a sloupce, na jejichž průsečíku se označené nuly nachází
a ve vzniklé submatici pokračujeme bodem 2.i).
iii) Pokud každý řádek či sloupec obsahuje víc než jednu neoznačenou nulu,
vybereme řádek či sloupec s nejmenším počtem nul a ve vybraném řádku či
sloupci libovolnou nulu zvolíme za nezávislou. Pokračujeme bodem 2.ii).
3. Podaří-li se vám vybrat n nezávislých nul, obsadíme místa matice, kde se nezávislé
nuly nacházejí, hodnotou 1, ostatní pole hodnotou 0. Získali jsme optimální řešení
přiřazovacího problému. Hodnota účelové funkce je rovna součtu původních sazeb
příslušných místům obsazených jedničkami.
108
10 PŘIŘAZOVACÍ PROBLÉM
4. Je-li počet nezávislých nul menší než n, zjistíme pomocí tzv. Königovy věty,
zda jsme vybrali maximální možný počet nezávislých nul.
KÖNIGOVA VĚTA:
Maximální počet nezávislých nul v matici je roven minimálnímu počtu
krycích čar, jimiž je možné pokrýt všechny nulové sazby dané matice.
Za tím účelem je potřeba všechny nulové sazby matice pokrýt minimálním počtem
krycích čar.
KONSTRUKCE KRYCÍCH ČAR:
i) Řádky a sloupce, ve kterých neleží nezávislé nuly, označíme *. Nulovými
sazbami takto označených řádků (resp. sloupců) vedeme svislé (resp. vodorovné) čáry.
ii) Vynecháme řádky a sloupce označené * a řádky a sloupce pokryté čarami.
Ve vzniklé submatici pokračujeme krokem 4.i).
iii) Zůstanou-li nepokryté pouze řádky a sloupce s nezávislými nulami, vedeme
minimální počet krycích čar i přes tyto nuly.
5. Je-li počet nalezených nezávislých nul roven počtu krycích čar, jimiž jsme pokryli všechny nulové sazby (tj. vybrali jsme maximální počet nezávislých nul),
přistoupíme k další redukci sazeb matice:
i) z nepokrytých polí vybereme minimální sazbu,
ii) hodnotu této sazby odečteme od všech prvků nepokrytých krycími čarami,
a přičteme k prvkům, kde se krycí čáry kříží,
iii) sazby v polích pokrytých jedinou krycí čarou ponecháme nezměněny.
6. Celý postup opakujeme od 2. bodu (opět hledáme nezávislé nuly).
10.1.2 Poznámka.
K bodu 1.: Redukce sazeb neovlivní tvar řešení, pouze se sníží hodnota účelove funkce
o součet všech odečtených sazeb. Redukce sazeb zajistí, že v každém řádku i každém
sloupci bude alespoň jedna nulová sazba.
K bodu 3.: Algoritmus vždy skončí tímto bodem, tj. bodem 3., tedy nalezením ntice nezávislých nul. Každé takové n-tici nezávislých nul odpovídá optimální řešení
úlohy. Optimálních řešení úlohy je tudíž právě tolik, kolik existuje n-tic nezávislých nul
(v posledně redukované matici sazeb).
K bodu 4.iii): V případě, kdy máme vést krycí čáry přes nulové sazby, jež jsou vždy
současně označenými nezávislými nulami, je zcela jedno, zda jimi vedeme krycí čáry
vodorovně či svisle, na jejich počet to nemá vliv.
K bodu 5.: Touto redukcí matice sazeb se opět nemění optimální řešení, hodnota
účelové funkce se snižuje právě o součin minimální sazby z nepokrytých polí a výrazu
n − nn , kde nn značí počet nezávislých nul.
10.1 Přiřazovací problém minimalizačního typu
109
10.1.3 Příklad. Nalezněte všechna optimální řešení přiřazovacího problému zadaného v příkladu 10.1.1.
Řešení. Začneme redukcí matice sazeb dle bodu 1. algoritmu maďarské metody.
Nejprve od sazeb každého řádku odečteme nejmenší sazbu v daném řádku. Protože
ještě ve druhém sloupci není nulová sazba, odečteme od sazeb tohoto sloupce jedničku
(nejmenší sazba tohoto sloupce).






4 3 1 −1
3 2 0
3 1 0
 1 2 6  −1 −→  0 1 5  −→  0 0 5 
4 5 3 −3
1 2 0
1 1 0
−1
V poslední matici již je v každém řádku alespoň jedna nula a v každém sloupci je
alespoň jedna nula. Dle bodu 2. nalezneme nezávislé nuly (označíme 1 ). V prvním
řádku je jediná nula, proto ji můžeme označit, podobně ve druhém sloupci je jediná
nula, i tu označíme za nezávislou. Samozřejmě dbáme na pravidlo, že nelze označit za
nezávislé dvě nuly v jednom řádku ani v jednom sloupci.





 ∗

 ∗
3 1 01
2 0 0
3 1 01
3 1 01
 0 01 5  −→  0 01 5  −→  0 01 5  −→  0 0 6 
∗ 1 1 0
∗ 1 1 0
0 0 0
1 1 0
1
Označíme * řádky a sloupce, v nichž nejsou nezávislé nuly a vyznačíme krycí čáry,
tj. postupujeme dle bodu 4.i). Počet krycích čar (jimiž jsme pokryli všechny nulové
sazby) je roven počtu nalezených nezávislých nul. Tím jsme si ověřili, že jsme skutečně
vybrali maximální počet nezávislých nul. Nejmenší z nepokrytých sazeb má hodnotu 1.
Provedeme redukci matice sazeb podle bodu 5.
V této znovu redukované matici opět hledáme nezávislé nuly. Tentokrát jsme již našli tři
(tolik, kolik je řád matice) nezávislé nuly. A dokonce jsme objevili tři trojice nezávislých
nul.




2
03 012
2 0 0
 0 0 6  −→  023 01 6 
01 02 03
0 0 0
Úloha má proto

0 0

0 1
Xopt,1 =
1 0

0 0

1 0
Xopt,2 =
0 1

0 1

1 0
Xopt,3 =
0 0
tři optimální řešení

1
0 ,
z(Xopt,1 ) = 1 + 2 + 4 = 7,
0

1
0 ,
z(Xopt,2 ) = 1 + 1 + 5 = 7,
0

0
0 ,
z(Xopt,3 ) = 1 + 3 + 3 = 7.
1
110
10 PŘIŘAZOVACÍ PROBLÉM
10.1.4 Poznámka. Celý postup budeme zapisovat stručněji. Řešení z příkladu 10.1.3
by vypadalo například takto:







 ∗
3 1 01
4 3 1 −1
2
03 012
3 2 0
 1 2 6  −1 −→  0 1 5  −→  0 01 5  −→  023 01 6 
∗ 1 1 0
4 5 3 −3
01 02 03
1 2 0
1
−1
10.1.5 Příklad. Čtyři auta se nachází na čtyřech stanovištích Si , i = 1, 2, 3, 4. Je
třeba je přemístit na čtyři pracoviště Pj , j = 1, 2, 3, 4. Údaje o vzdálenostech v km jsou
v tabulce. Nalezněte optimální řešení úlohy.
A1
A2
A3
A4
Řešení.

5 17
 6 15

 20 10
10 15

0
 01
−→ 
 15
0
23
17
10
20
10
15
15
15
7
4
0
01
13
6
01
5


P1
5
6
20
10
P2
17
15
10
15
P3
23
17
10
20
P4
10
15
15
15


−5
0 12 18 5
∗ 0
 −6
 0 9 11 9 
 1


 −→  0
−→
 −10
 10 0 0 5 
 10
0
−10
0 5 10 5
−5

1
0
4 

5 
0
∗
12 18
9 11
01 0
5 10

0
4 
 −→
0 
01 5
Úloha má jediné optimální řešení

Xopt
0
 1
=
 0
0
0
0
0
1
0
0
1
0

1
0 
,
0 
0
z(Xopt ) = 10 + 6 + 10 + 15 = 41 km.
10.1.6 Příklad. Řešte minimalizační přiřazovací problém, tj. nalezněte všechna optimální řešení úlohu a příslušnou hodnotu účelové funkce, je-li matice sazeb


7 5 7 4 8
 10 5 7 6 7 


 4 8 9 7 10  .


 6 4 7 8 7 
5 6 10 7 9
10.1 Přiřazovací problém minimalizačního typu
Řešení.

7 5
 10 5

 4 8

 6 4
5 6



−→ 


∗
4
6
01
2
0
7
7
9
7
10
2
1
4
01
1
Úloha má tři

0
 0

Xopt,1 = 
 1
 0
0

0
 0

Xopt,2 = 
 1
 0
0

0
 0

Xopt,3 = 
 1
 0
0


4 8
−4
3 1


6 7  −5
 5 0

7 10  −4 −→ 
 0 4
 2 0
8 7  −4
7 9
−5
0 1
1
01
2
0
2
1
0
1
2
3
1
∗
2
0
3
0
1






 −→ 




1
optimální řešení

0 0 1 0
0 0 0 1 

0 0 0 0 
,
0 1 0 0 
1 0 0 0

0 0 1 0
0 1 0 0 

0 0 0 0 
,
1 0 0 0 
0 0 0 1

0 0 1 0
0 1 0 0 

0 0 0 0 
,
0 0 0 1 
1 0 0 0
5
7
0123
3
0
3
2
5
3
5
−2
0
1
3
4
2
111


4

2 



6 
−→



3 
∗
4
−2
3
5
01
2
0
0123
1
1
3
0

2
1
3
02
013
1
023
1
01
1
2
01
2
03
02
1
0
4
01
1
1
01
3
1
3





z(Xopt,1 ) = 4 + 7 + 4 + 7 + 6 = 28,
z(Xopt,2 ) = 4 + 7 + 4 + 4 + 9 = 28,
z(Xopt,3 ) = 4 + 7 + 4 + 7 + 6 = 28.
10.1.7 Úkoly a problémy k modulu 10.1
1. Řešte minimalizační přiřazovací problém s

5 6 9
 5 5 7

 6 7 10
9 11 13
maticí sazeb

10
8 
.
10 
14
01
1
3
4
2
∗
2
0
4
1
2



 −→


1
112
10 PŘIŘAZOVACÍ PROBLÉM
2. Řešte minimalizační přiřazovací problém s

9 7 6
 7 9 4

 7 8 5
9 6 1
maticí sazeb

3
3 
.
7 
2
3. Řešte minimalizační přiřazovací problém s

9 2 7
 7 5 7

 7 5 3
6 2 9
maticí sazeb

7
8 
.
7 
9
4. Řešte minimalizační přiřazovací problém s maticí sazeb


3 10 5 5
 3 5 3 2 


 6 8 10 6  .
5 9 2 2
Řešení.
1. Xopt
2. Xopt

0
 0
=
 0
1
1
0
0
0
0
1
0
0

0
0 
,
1 
0
zmin = 32.

1
0
0
0
0
0
0
1

0
1 
,
0 
0
zmin = 18.
0
 0
=
 1
0

3. Xopt,1
0
 0
=
 0
1

4. Xopt
1
 0
=
 0
0
1
0
0
0
0
0
1
0
0
0
1
0
0
0
0
1


0
0 0
 1 0
1 
 , Xopt,2 = 
 0 0
0 
0
0 1

0
1 
,
0 
0
zmin = 15.
0
0
1
0

1
0 
,
0 
0
zmin = 19.
10.2 Přiřazovací problém maximalizačního typu
10.2
113
Přiřazovací problém maximalizačního typu
Předchozí modul byl věnován přiřazovacím úlohám minimalizačního typu. Nejsou však
vyjímkou přiřazovací problémy maximalizačního typu. Takové úlohy budeme řešit tak,
že je převedeme na minimalizační přiřazovací problém, který má stejnou množinu všech
optimálních řešení jako původní maximalizační úloha. Tento převod na úlohu minimalizační provádíme tak, že všechny prvky matice vynásobíme číslem (−1). Dále postupujeme maďarskou metodou tak, jak byla vyložena v odstavci 10.1.
10.2.1 Příklad. Uvažujme firmu, v níž čtyři pracovníci Pi , i = 1, 2, 3, 4, mohou vyrábět čtyři druhy výrobků Vj , j = 1, 2, 3, 4 (podle toho, na kterou ze čtyř výrobních
linek jsou pracovníci přiřazeni). Počet cij výrobků Vj , které je pracovník Pi schopen
za 1 hodinu vyrobit je uveden v tabulce. Určete, které výrobky bude vyrábět který
pracovník, aby celkový počet výrobků vyrobených za 1 hodinu byl maximální.
Řešení.

5 17
 6 15

 20 10
10 15
23
17
10
20

18 6
 11 2
−→ 
 0 10
10 5
−2
Úloha má dvě

0
 0
Xopt,1 = 
 1
0

0
 0
Xopt,2 = 
 1
0
cij
P1
P2
P3
P4
V1
5
6
20
10


10

15 
 · (−1) −→ 


15
15
−5
−6
−20
−10


0 13
18


11
0 2 
−→ 
 01
10 5 
∗ 10
0 5
−2
4
01
8
3
V2
17
15
10
15
V3 V4
23 10
17 15
10 15
20 15
−17
−15
−10
−15
−23
−17
−10
−20
01
0
10
0
∗
11
0
3
3


−10 −(−23)
−15 
 −(−17) −→
−15  −(−20)
−15 −(−20)

18

 14
 −→  12

 0
10
3
1
01
5
02
012
3
10
0

8
02 

0 
01
optimální řešení

0 1 0
1 0 0 
,
z(Xopt,1 ) = 23 + 15 + 20 + 15 = 73 ks/hod.,
0 0 0 
0 0 1

0 1 0
0 0 1 
,
z(Xopt,2 ) = 23 + 15 + 20 + 15 = 73 ks/hod.
0 0 0 
1 0 0
114
10 PŘIŘAZOVACÍ PROBLÉM
10.2.2 Poznámka. Pozornější čtenář jistě zaznamenal, že se matice sazeb v příkladech 10.1.5 a 10.2.1 shodují, první příklad je ovšem minimalizační, druhý je maximalizační. Optimální řešení úlohy z příkladu 10.1.5 je tak současně nejhorším řešením pro
úlohu z příkladu 10.2.1, a naopak.
10.2.3 Příklad. Nalezněte nejhorší řešení úlohy z příkladu 10.1.1.
Řešení.
Nejhorším řešením přiřazovací úlohy z příkladu 10.1.1 je řešení, jež maximalizuje celkovou přepravní vzdálenost jeřábů. Proto původní matici sazeb násobíme číslem (−1).
Dále, známým způsobem, tj. maďarskou metodou, řešíme teď již minimalizační úlohu.
Nejhorší řešení je


1 0 0
Xopt =  0 0 1  , zmax = z(Xopt ) = 4 + 6 + 5 = 15 km.
0 1 0
10.2.4 Úkoly a problémy k modulu 10.2
1. Řešte maximalizační přiřazovací problém s
10.1.7)

5 6 9
 5 5 7

 6 7 10
9 11 13
maticí sazeb (srovnejte s 1. úkolem

10
8 
.
10 
14
2. Řešte maximalizační přiřazovací problém
10.1.7)

9 7 6
 7 9 4

 7 8 5
9 6 1
s maticí sazeb (srovnejte s 2. úkolem

3
3 
.
7 
2
3. Řešte maximalizační přiřazovací problém
10.1.7)

9 2 7
 7 5 7

 7 5 3
6 2 9
s maticí sazeb (srovnejte s 3. úkolem

7
8 
.
7 
9
10.2 Přiřazovací problém maximalizačního typu
115
4. Řešte maximalizační přiřazovací problém s
10.1.7)

3 10 5
 3 5 3

 6 8 10
5 9 2
maticí sazeb (srovnejte s 4. úkolem
Řešení.
1. Xopt
2. Xopt
3. Xopt

0
 1
=
 0
0
0
0
0
1
0
0
1
0

1
0 
,
0 
0
zmax = 36.

0
 0
=
 0
1
0
1
0
0
1
0
0
0

0
0 
,
1 
0
zmax = 31.

0
0
1
0
0
0
0
1

0
1 
,
0 
0
zmax = 31.
1
 0
=
 0
0

4. Xopt,1
0
 0
=
 0
1
1
0
0
0
0
0
1
0


0
0


1 
1
, Xopt,2 = 
 0
0 
0
0
0
0
0
1

5
2 
.
6 
2
0
0
1
0

1
0 
,
0 
0
zmax = 27.
116
10 PŘIŘAZOVACÍ PROBLÉM
10.3 Shrnutí 10. kapitoly
Klíčová slova:
Přiřazovací problém, maďarská metoda, nezávislé nuly, Königova věta, krycí čáry,
redukce sazeb.
Základní úlohy:
• Najít optimální řešení přiřazovací úlohy minimalizačního typu.
• Najít optimální řešení přiřazovací úlohy maximalizačního typu.
Doporučená literatura pro hlubší studium:
[Holoubek]:
[Jablonský]:
[Mošová]:
str. 100–105,
str. 107–109,
str. 73–77.
10.4 Test ke kapitole 10
1. Řešte přiřazovací problém s maticí sazeb

2 3 11
 2 5 12

 1 5 9
4 6 9

4
6 
.
6 
7
Určete všechna optimální řešení úlohy v případě, že úloha je:
a) minimalizační,
b) maximalizační.
2. Řešte přiřazovací problém s maticí sazeb


6 1 2 11
 5 2 3 12 


 7 2 3 12  .
5 2 2 8
Určete všechna optimální řešení úlohy v případě, že úloha je:
a) minimalizační,
b) maximalizační.
10.4 Test 10
117
3. Řešte přiřazovací problém s maticí

9
 8

 7

 9
6
sazeb
5
8
7
8
5
7
3
3
4
8
1
6
3
6
7
3
6
5
7
3



.


Určete všechna optimální řešení úlohy v případě, že úloha je:
a) minimalizační,
b) maximalizační.
Řešení.
1.

a) Xopt,1
b) Xopt,1
Xopt,3
2.
a) Xopt,1
b) Xopt,1
Xopt,3
0
 0
=
 1
0
1
0
0
0
0
0
0
1

0
1 
,
0 
0

1
 0
=
 0
0

0
 0
=
 0
1
0
0
1
0
0
1
0
0
0
1
0
0
1
0
0
0

0
0 
,
0 
1

0
0 
,
1 
0

0
 1
=
 0
0
1
0
0
0
0
0
1
0

0
0 
,
0 
1

0
0
0
1
0
1
0
0
0
0
0
1
1
0
0
0

0
0 
,
1 
0

0
1 
,
0 
0
1
 0
=
 0
0

0
 0
=
 1
0

Xopt,2
Xopt,2
Xopt,4
Xopt,2
Xopt,2
Xopt,4
0
 0
=
 1
0
0
1
0
0
0
0
0
1

1
0 
,
0 
0

1
 0
=
 0
0

0
 0
=
 0
1
0
0
0
1
0
1
0
0
0
0
1
0
1
0
0
0

0
0 
,
1 
0

0
1 
,
0 
0

0
 1
=
 0
0
0
0
1
0
1
0
0
0

0
0 
,
0 
1

0
0
0
1
0
0
1
0
0
0
0
1
0
1
0
0

0
1 
,
0 
0

1
0 
,
0 
0
1
 0
=
 0
0

0
 0
=
 1
0
zmin = 19,
zmax = 26.
zmin = 17,
zmax = 23.
118
10 PŘIŘAZOVACÍ PROBLÉM

3.
a) Xopt


=



b) Xopt


=


0
0
1
0
0
0
0
0
1
0
0
1
0
0
0
1
0
0
0
0
0
0
0
0
1

1
0
0
0
0
0
0
1
0
0
0
0
0
0
1
0
1
0
0
0
0
0
0
1
0



,




,


zmin = 22,
zmax = 37.
119
Seznam literatury
[Ellinger]
ELLINGER, T., BEUERMANN, G., LEISTEN, R. Operations Research.
Berlin : Springer, 2003. 280 s. ISBN 3-54041050-3.
[Holoubek]
HOLOUBEK, J. Ekonomicko-matematické metody. Brno : MZLU, 2006.
153 s. ISBN 80-7157-970X.
[Hušek]
HUŠEK, R., MAŇAS, M. Matematické metody v ekonomii. Praha :
SNTL, 1989. 402 s. ISBN 80-03-00098-X.
[Jablonský]
JABLONSKÝ, J. Operační výzkum. 2. vyd. Praha : Professional Publishing, 2002. 323 s. ISBN 80-86419-42-8.
[Korda]
KORDA, B. Matematické metody v ekonomii. Praha : SNTL, 1967. 600 s.
[Kříž]
KŘÍŽ, O. Lineární programování. Vyškov : VVŠ PV, 1988. 70 s.
[Mošová]
MOŠOVÁ, V. Lineární programování. Vyškov : VVŠ PV, 1996. 115 s.
[Moučka1]
MOUČKA, J. Lineární algebra. Vyškov : VVŠ PV, 1999. 126 s. ISBN
80-7231-047-X.
[Moučka2]
MOUČKA, J., ŠOTOVÁ, J. Lineární algebra pro distanční studium
[CD-ROM]. 1. vyd. Brno : UO Brno, 2007. ISBN: 978-80-7231-250-4.
[Rašovský]
RAŠOVSKÝ, M. Operační analýza a modelování I. Brno : VŠZ, 1994.
151 s. ISBN 80-7157-104-0.
[Tyc]
TYC, O. Operační výzkum. Brno : MZLU, 2006. 124 s.
ISBN 80-7157-726-X.
[Weir]
WEIR, G. A First Course in Mathematical Modeling. New York : Brooks/Cole Publishing Copany, 1997. 525 s. ISBN 0-534-22248-X.
120
121
Rejstřík
A
alternativní řešení, 94
B
bázická proměnná, 11
D
degenerované řešení, 12, 92
dodavatel, 80
doplňková proměnná, 16
dopravní úloha, 79
alternativní řešení, 94
nevyrovnaná, 79
vyrovnaná, 79
dualita, 53, 55
reflexivnost, 54
duálně sdružené úlohy
nesymetrické, 56
symetrické, 56
duálně simplexová metoda, 62
E
ekonomicko-matematické metody, 6
ekonomický model, 6
F
Frobeniova věta, 10
G
grafická metoda, 31
H
hodnost matice, 10
K
kanonický tvar, 12
kapacita dodavatele, 80
klíčový prvek, 42
klíčový sloupec, 41
klíčový řádek, 41
Königova věta, 108
krycí čáry, 108
křížové pravidlo, 42
M
maďarská metoda, 105
matematický model, 6
duální, 55
primární, 54, 55
matice
hodnost, 10
schodovitý tvar, 11
matice soustavy, 9
metoda
duálně simplexová, 62
grafická, 31
maďarská, 105
simplexová, 37
Vogelova aproximační, 82
N
nedegenerované řešení, 12, 92
nepřímé sazby, 87
nezávislé nuly, 107
nutriční úloha, 23
O
obsazené pole, 82
operační analýza, 6
operační výzkum, 6
optimální řešení, 6
P
parametrické programování, 69
parametrizace
koeficientů účelové funkce, 72
pravých stran, 69
podmínky
nezápornosti, 7
vlastní omezující, 7
požadavek spotřebitele, 80
pravidlo
křížové, 42
proměnná
bázická, 11
122
REJSTŘÍK
doplňková, 16
vedlejší, 11
vstupující, 14, 41
vylučovaná, 41
základní, 11
proškrtnuté pole, 82
přepravní sazby, 79
přiřazovací problém, 105
maximalizační, 113
minimalizační, 105
R
reflexivnost duality, 54
rozhodovací situace, 6
rozšířená matice soustavy, 9
Ř
řešení
degenerované, 12
duálně přípustné, 62
nedegenerované, 12
optimální, 6
primárně přípustné, 62
základní, 11
řešení dopravní úlohy
degenerované, 92
nedegenerované, 92
S
schodovitý tvar matice, 11
simplexová metoda, 37
soustava
lineárních nerovnic, 15
lineárních rovnic, 9
soustava lineárních rovnic
kanonický tvar, 12
spotřebitel, 80
T
test optima, 87
U
uzavřený okruh, 89
Ú
účelová funkce, 8
úloha
dopravní
nevyrovnaná, 79
vyrovnaná, 79
duální, 53
ekonomická interpretace, 61
nutriční, 23
přiřazovací, 105
úloha lineárního programování
standardní tvar, 54
V
vedlejší proměnná, 11
vektor
absolutních členů, 9
neznámých, 9
Vogelova aproximační metoda, 82
vstupující proměnná, 14, 41
vylučovaná proměnná, 41
věta
Frobeniova, 10, 28
Königova, 108
o reflexivnosti duality, 54
o počtu řešení, 10
základní věta o dualitě, 58
Z
zlepšování řešení, 89
základní proměnná, 11
základní řešení, 11
Název:
Autoři:
Recenzenti:
Vedoucí katedry:
Rok vydání:
Počet výtisků:
Počet stran:
Vydavatel:
Sazba:
Vydání:
Tiskem:
Číslo EP:
Číslo zakázky:
Cena pro vnitřní
potřebu:
ISBN tištěné podoby:
Ekonomicko-matematické metody
RNDr. Michal ŠMEREK,
doc. RNDr. Jiří MOUČKA, Ph.D.
doc. RNDr. Josef KALAS, CSc.
RNDr. Vratislava MOŠOVÁ, CSc.
prof. RNDr. Zdeněk ZEMÁNEK, CSc.
2008
100
123
Univerzita obrany
systém LATEX 2ε
první
Vydavatelská skupina UO Brno
17/2008
91,-Kč
978-80-7231-526-0
Download

Lineární programování