Lineární programování II
Ivan Nagy, Pavla Pecherková
Obsah 1 Lineární programování
4
1.1
Formulace úlohy
1.2
Algebraický model
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
1.3
Pojmy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
1.3.1
Duální úloha
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
1.3.2
Duální cena (dual price) . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
1.3.3
Redukované náklady (reduced cost)
. . . . . . . . . . . . . . . . . . . . .
5
Simplexová metoda . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6
1.4.1
P°íklad - °e²ení standardní simplexové úlohy
6
1.4.2
P°íklad - °e²ení nestandardní simplexové úlohy
1.4
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2 Modely lineárního programování
4
8
12
2.1
Obecný p°íklad lineárního programování . . . . . . . . . . . . . . . . . . . . . . .
12
2.2
Optimální produkce - 2 výrobky
14
2.3
Optimální produkce s omezenými zdroji
. . . . . . . . . . . . . . . . . . . . . . .
16
2.4
Optimální produkce s výb¥rem surovin . . . . . . . . . . . . . . . . . . . . . . . .
18
2.5
Optimální míchání
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
18
2.5.1
Úloha £. 1 (krmná sm¥s) . . . . . . . . . . . . . . . . . . . . . . . . . . . .
18
2.5.2
Úloha £. 2 (optimální strava v¥z¬·) . . . . . . . . . . . . . . . . . . . . . .
19
2.6
2.7
2.8
Minimální tok náklad· v síti
. . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
20
2.6.1
Úloha £. 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
21
2.6.2
Úloha £. 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
22
P°i°azovací dopravní problém . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
23
2.7.1
PDP °e²ený pomocí lineárního programování
. . . . . . . . . . . . . . . .
23
2.7.2
PDP °e²ený pomocí MCNF (min. cost network ow) . . . . . . . . . . . .
24
Nejkrat²í cesta grafem (pomocí MCNF) 1
. . . . . . . . . . . . . . . . . . . . . . .
25
2
OBSAH
3 Celo£íselné programování
26
3.1
Formulace úlohy
3.2
Formulace celo£íselných program·
3.3
3.4
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
26
3.2.1
Binární veli£iny . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
26
3.2.2
Aktivace omezení . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
27
3.2.3
Výb¥r z mnoºiny omezení . . . . . . . . . . . . . . . . . . . . . . . . . . .
27
3.2.4
Implikované omezení . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
27
3.2.5
Alespo¬ k omezení . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
28
3.2.6
Omezení na oblasti . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
29
Modelování nelineárních funkci
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
29
3.3.1
Fixní náklady . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
29
3.3.2
Po £ástech lineární reprezentace . . . . . . . . . . . . . . . . . . . . . . . .
30
3.3.3
Aproximace nelineárních funkcí . . . . . . . . . . . . . . . . . . . . . . . .
31
3.3.4
Sou£in v kritériu
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
32
Metody °e²ení . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
33
3.4.1
Metoda v¥tví a mezí (branch and bound)
. . . . . . . . . . . . . . . . . .
33
3.4.2
Metoda °ez· (cutting planes)
. . . . . . . . . . . . . . . . . . . . . . . . .
35
4 Modely celo£íselného programování 4.1
4.2
26
39
Výb¥r projektu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
39
4.1.1
Rozpo£et kapitálu (Capital budgeting)[Hlavni text] . . . . . . . . . . . . .
39
4.1.2
Problém batohu [Nas text, Knapsack]
. . . . . . . . . . . . . . . . . . . .
40
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
41
4.2.1
Velikost dávky - bez kapacity[Kniha] . . . . . . . . . . . . . . . . . . . . .
41
4.2.2
Velikost dávky - s kapacitou [Kniha]
. . . . . . . . . . . . . . . . . . . . .
41
4.2.3
Produkce na odbyt [Kniha]
. . . . . . . . . . . . . . . . . . . . . . . . . .
42
4.2.4
Objednávka léku [3 p°íklady]
Plánování produkce
. . . . . . . . . . . . . . . . . . . . . . . . .
43
4.3
P°eprava s pevnou cenou [Kniha] . . . . . . . . . . . . . . . . . . . . . . . . . . .
44
4.4
Problém investi£ního rozhodování [Nas text] . . . . . . . . . . . . . . . . . . . . .
44
4.5
Problém po²tovních box· [Nas text]
. . . . . . . . . . . . . . . . . . . . . . . . .
45
4.6
Propuknutí infek£ního onemocn¥ní [Nas text, 3 p°íklady] . . . . . . . . . . . . . .
46
4.6.1
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
47
Pokrytí mnoºin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
48
4.7.1
48
4.7
P°íklad
Pokrytí mnoºin - set covering [Kniha]
. . . . . . . . . . . . . . . . . . . .
3
OBSAH
4.7.2
Rozd¥lení a zabalení mnoºin (partitioning, packing) [Kniha] . . . . . . . .
49
4.7.3
Rozmíst¥ní sklad· (Warehouse location) [Nas text, Hlavni text] . . . . . .
50
4.8
Problém p°i°azení [Kniha] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
51
4.9
Problém °ezání [Kniha] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
52
4.9.1
ezání ty£í
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
52
4.9.2
ezání papíru . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
52
4.10 TSP - Problém obchodního cestujícího [Nas text, Kniha] . . . . . . . . . . . . . .
53
4.10.1 Asymetrický TSP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
53
4.10.2 Symetrický TSP
55
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.10.3 TSP jako nelineární problém
. . . . . . . . . . . . . . . . . . . . . . . . .
57
4.11 Zobecn¥ní TSP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
58
4.11.1 Nejkrat²í cesta grafem [Kniha]
. . . . . . . . . . . . . . . . . . . . . . . .
58
4.11.2 Nejkrat²í cesta grafem z daného uzlu . . . . . . . . . . . . . . . . . . . . .
59
4.11.3 TSP s opakovanými náv²t¥vami m¥st [Kniha] . . . . . . . . . . . . . . . .
59
4.11.4 TSP s klastry [Kniha]
60
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.12 Optimální po°adí úloh (machine sequencing) [Sheduling]
. . . . . . . . . . . . .
60
. . . . . . . . . . . . . . . . . .
60
. . . . . . . . . . . . . . . . . . . .
62
4.12.1 Plánování sm¥n pro obsluhu (Scheduling) 4.12.2 Obsazování let· posádkami [Nas text]
5 Programové vybavení 5.1
5.2
65
Excel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
65
5.1.1
e²itel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
65
5.1.2
Model v se²it¥ Excel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
65
5.1.3
Triky p°i práci v Excelu . . . . . . . . . . . . . . . . . . . . . . . . . . . .
66
5.1.4
P°íklad v excelu
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
67
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
69
LIPS????
Kapitola 1
Lineární programování 1.1
Formulace úlohy
Nalezn¥te hodnoty vektoru
x,
které
(i)
c0 x = c1 x1 + c2 x2 + ai,1 x1 + ai,2 x2 + · · · + ai,n xn ≤ bi , pro
maximalizují lineární kriterium
· · · + cn xn , (ii) spl¬ují vedlej²í podmínky Ax ≤ b, tedy i = 1, 2, · · · , m (m podmínek pro n prom¥nných) a (iii)
jsou nezáporné.
Zápis standardní úlohy je následující:
c0 x → max1 Ax ≤ b2 x ≥ 03
Poznámka Omezení vytvá°í simplex, na kterém se hledá optimum. Lineární kriterium tvo°í nadrovinu v prostorux,
1.2
J , kde J
je kritérium.. Extrém je ve vrcholu nebo na hranici nebo ute£e do nekone£na.
Algebraický model
1. Denice neznámých (rozhodovacích) veli£in V prvé °ad¥ musíme denovat veli£iny (a) spojité
x≥0
(b) diskrétní
x
které budeme optimalizovat. Ty mohou být:
- nap°. po£et ks vyráb¥ného produktu (lze vyrobit i £ást produktu),
x ≥ 0, x ∈ N
1 hledáme maximum 2 nep°ekro£íme limitující 3 hodnota je nezáporná
x,
- nap°. po£et za°ízení s rychlým ob£erstvením,
omezení (nap°íklad nem·ºeme vyrobit víc výrobk· neº na které máme materiál)
4
KAPITOLA 1.
5
LINEÁRNÍ PROGRAMOVÁNÍ
(c) binární
x ∈ {0, 1} , které nazýváme rozhodovací (0 ne, 1 ano) - nap°. ozna£ení investic
z ur£ité mnoºiny, které budou realizovány. 2. Denice kritéria Kritérium v¥t²inou vyjad°uje n¥co, co chceme maximalizovat (zisk) nebo minimalizovat
x, v¥t²inou ve P c0 x, tedy jako sou£in vektor· nebo matic ( j,j cij xij ). Prom¥nné c se £asto nazývají
(náklady, ztráty atd.). Je vyjád°eno jako funkce optimalizovaných veli£in form¥ ceny. 3. Denice omezujících podmínek
Vyjad°ují podmínky, za kterých má optimalizace probíhat. Nejb¥ºn¥j²í jsou (a) nezápornost
x≥0
nebo nezápornost celo£íselných neznámých
(b) omezení ve tvaru nerovností
Ax ≤ b,
kde matice
A
x ∈ N,
má rozm¥ry po£et omezení
×
po£et neznámých (c) a p°ípadn¥ dal²í, se kterými se postupn¥ setkáme v textu.
1.3
Pojmy
1.3.1 Duální úloha Ke kaºdé primární úloze
c'x → max
s omezením
Ax≤b, x≥0
resp.
c'x → min
s omezením
Ax ≥ b, x≥0
A0 y≥c, y≥0
resp.
b0 y → min
s omezením
A0 y ≤ c, y≥0
existuje tzv. duální úloha
b0 y → min
s omezením
která má dále r·zné vyuºití.
1.3.2 Duální cena (dual price) Kaºdé omezení má svou duální cenu. Je to p°ír·stek v hodnot¥ kriteria, který dostaneme, kdyº k pravé stran¥ omezení typu
≤
p°i£teme jedni£ku - omezení uvolníme o jedna. Jsou nenulové,
jen kdyº je omezení aktivní.
1.3.3 Redukované náklady (reduced cost) Je to informace o tom, o kolik by se musel zm¥nit koecient
cj , aby se veli£ina xj
tj. aby se tato prom¥nná se stala sou£ástí optimálního °e²ení.
stala efektivní,
KAPITOLA 1.
1.4
6
LINEÁRNÍ PROGRAMOVÁNÍ
Simplexová metoda
Pro °e²ení základní úlohy lze vyuºít
simplexovou metodu,
která prochází vrcholy simplexu
omezení (v kaºdém kroku pozm¥ní °e²ení) tak, aby stále nar·stala hodnota kritéria. To znamená, ºe v kaºdém kroku se pozm¥ní °e²ní tak, aby hodnota funkce byla v¥t²í. V p°ípad¥, ºe ani po zm¥n¥ v dal²ím kroku nedojde k zvý²ení hodnoty kritéria, nalezené °e²ení uvaºujeme jako optimální. Simplexová metoda m·ºe být pouºita za p°edpokladu, ºe jsou spln¥ny základní podmínky:
1. maximalizujeme kritérium (minimaliza£ní úloha lze p°evést na maximaliza£ní pomocí vzorce
min f (x) = − max (−f (x))),
2. pravé strany musí být nezáporné,
≤,
3. omezující podmínky jsou vymezeny nerovnostmi typu 4. prom¥nné
x
jsou nezáporné.
P°i °e²ení simplexové úlohy se postupuje v n¥kolika krocích. Nejd°íve si ov¥°íme, zda platí základní podmínky (viz vý²e). Poté sestavíme simplexovou tabulku a následuje vlastní °e²ení úlohy, p°i£emº úloha se °e²í r·zn¥ podle toho, zda se jedná o standardní nebo nestandardní úlohu, tedy úlohu, kde není spln¥na podmínka o nezápornosti pravé strany nebo typu nerovnosti. Postup je ukázán samostatn¥ pro standardní a nestandardní úlohu.
1.4.1 P°íklad - °e²ení standardní simplexové úlohy Zadání úlohy: Ur£ete hodnoty prom¥nné
x = [x1 , x2 ],
kde
x1 ≥ 0, x2 ≥ 0,
která maximalizuje kritérium
J
J = c1 x1 + c2 x2 = 2x1 + 3x2 a vyhovuje podmínkám
x1 + x2
≤ 5
x1 + 2x2
≤ 8
Ov¥°ení platnosti základních podmínek: 1. maximalizujeme kritérium -
X
(ano,
2. pravé strany musí být nezáporné -
X
2x1 + 3x2 → max), (ano, £íslo
5i8
jsou kladná £ísla),
3. omezující podmínky jsou vymezeny nerovnostmi typu mínky jsou uvedeny znaménka 4. prom¥nné
x
jsou nezáporné -
≤
-
X(ano,
v obou rovnicích pod-
≤),
X
(v zadání je denováno, ºe
x1 ≥ 0, x2 ≥ 0).
KAPITOLA 1.
7
LINEÁRNÍ PROGRAMOVÁNÍ
Zbavíme se nerovnosti a maxima: 1. Nerovnosti se zbavíme tak, ºe p°idáme dal²í £len, který bude vºdy kladný, v na²em p°ípad¥ bude rovnice vypadat takto:
x1 + x2 + s1
=
5
x1 + 2x2 + s2
=
8
2. Do simplexové tabulky pot°ebujeme také pouºít kritérium. Pokus bychom pouºili základní tvar, tedy v tomto p°ípad¥ stranu dát
∞.
2x1 +3x2 → max bylo by nutné do simplexové tabulky na pravou
Z tohoto d·vodu se upraví tento °ádek rovnice do tvaru
−2x1 − 3x2
=
0
Sestavení simplexové tabulky: x1
x2
s1
s2
RHS
-2
-3
0
0
0
1
1
1
0
5
1
2
0
1
8
←°ádek kritéria ←1. omezení ←2. omezení
Úprava simplexové tabulky: 1. Najdeme nejmen²í záporný koecient v °ádku kritéria
→klí£ový
sloupec.
Nejmen²í záporný koecient je koecient na kterém hodnota závisí nejvíce. V tomto p°ípad¥ je to tedy hodnota
−3
a tedy prom¥nná
x2 .
2. Pro kladné prvky v klí£ovém sloupci najdeme nejmen²í podíl pravé strany a prvku v klí£ovém sloupci
→klí£ový °ádek. V p°ípad¥, ºe je více klí£ových °ádk·, lze vybrat libovolný
z nich.
5 8 1 = 5, pro druhé omezení je to podíl 2 v °ádku s druhým omezením, a to bude tedy klí£ový °ádek. Pro první omezení je to podíl
= 4.
Men²í podíl je
3. Na pr·se£íku klí£ového sloupce a klí£ového °ádku leºí klí£ový prvek. V na²em p°ípad¥ je tedy klí£ový prvek £íslo
2.
4. Klí£ový °ádek celý vyd¥líme klí£ovým prvkem a ur£íme hodnotu klí£ového prvku. V na²em p°ípad¥ bude nový klí£ový °ádek
x1
x2
s1
s2
RHS
0,5
1
0
0,5
4
a klí£ový prvek bude
x2
=
1 1 4 − x1 − s2 2 2
KAPITOLA 1.
8
LINEÁRNÍ PROGRAMOVÁNÍ
5. Do v²ech prvk· klí£ového sloupce (mimo klí£ového prvku) dosadíme hodnotu klí£ového prvku, tzn. vynulujeme ostatní prvky v klí£ovém sloupci) a upravíme simplexovou tabulku.
x1
x2
s1
s2
RHS
-0,5
0
0
1,5
12
-0,5
0
1
-0,5
1
0,5
1
0
0,5
4
V nové simplexové tabulce se hodnota kritéria
J
←°ádek kritéria ←1. omezení ←2. omezení zvý²ila na hodnotu
12. P°esto není °e²ení
je²t¥ ideální, protoºe v °ádku kritéria se dále objevuje záporný koecient. Z tohoto d·vodu budeme znovu upravovat simplexovou tabulku. 6. V p°ípad¥, ºe se v °ádku kritérií objevuje záporný koecient, opakuje se postup od bodu 1 a to do doby, neº jsou v²echny prvky v °ádku kritéria nezáporné. V na²em p°ípad¥, se simplexová tabulka upraví do následujícího tvaru
Výsledek: a
x2 = 3.
x1
x2
s1
s2
RHS
0
0
1
1
13
1
0
2
-1
2
0
1
-1
1
3
←°ádek kritéria ←1. omezení ←2. omezení
Optimálním °e²ení nalezené simplexovou metodou v tomto p°ípad¥ je pro
Hodnota kritéria
x1 = 2
J = 13.
1.4.2 P°íklad - °e²ení nestandardní simplexové úlohy V n¥kterých zadáních dojde k tomu, ºe nejsou spln¥né v²echny základní podmínky, viz 1.4. Obvykle se jedná o omezení vyºadující nezáporné £íslo na pravé stran¥ nebo o obrácenou nerovnost. V takovém p°ípad¥ se postupuje podle následujícího postupu (hlavní princip je stejný jako u standardní simplexové úlohy).
Zadání úlohy: Ur£ete hodnoty prom¥nné
x = [x1 , x2 ],
kde
x1 ≥ 0, x2 ≥ 0,
která maximalizuje kritérium
J = c1 x1 + c2 x2 = 2x1 + 3x2 a vyhovuje podmínkám
x1 + x2
≤ 5
x1 + 2x2
≤ 8
−2x1 + x2
≤
−4
J
KAPITOLA 1.
9
LINEÁRNÍ PROGRAMOVÁNÍ
Ov¥°ení platnosti základních podmínek: X
1. maximalizujeme kritérium -
(ano,
2. pravé strany musí být nezáporné -
×
2x1 + 3x2 → max), (NE, £íslo
−4
je záporné),
≤- X(ano,
3. omezující podmínky jsou vymezeny nerovnostmi typu mínky jsou uvedeny znaménka 4. prom¥nné
x
jsou nezáporné -
v obou rovnicích pod-
≤),
X
(v zadání je denováno, ºe
x1 ≥ 0, x2 ≥ 0).
Úprava nespln¥né podmínky: 1. ádek, kde je záporná hodnota vynásobíme £íslem
−2x1 + x2 2x1 − x2
≤
−1.
−4 / · (−1)
≥ 4
2. V tuto chvíli jsme splnili ze základních podmínek (1.4) druhou podmínku, ale zase není spln¥na podmínka t°etí, tedy levá strana je
≤neº
strana pravá. Nerovnici vyrovnáme p°i-
dáním dal²ích pomocných prom¥nných. 3. Nerovnosti se zbavíme tak, ºe p°idáme dal²í £len, který bude vºdy kladný, v na²em p°ípad¥ bude rovnice vypadat takto:
kde
xA
xA
x1 + x2 + s1 + xA
=
5
x1 + 2x2 + s2
=
8
2x1 − x2 + s3 − xA
=
4
je pomocná prom¥nná, která zajistí, ºe se vliv na °e²ení vynuluje. Prom¥nné
si
i
jsou nezáporné.
4. Do simplexové tabulky pot°ebujeme také pouºít kritérium. Pokus bychom pouºili základní tvar, tedy v tomto p°ípad¥ stranu dát
∞.
2x1 +3x2 → max bylo by nutné do simplexové tabulky na pravou
Z tohoto d·vodu se upraví tento °ádek rovnice do tvaru
−2x1 − 3x2
=
0
Sestavení simplexové tabulky: x1
x2
s1
s2
s3
xA
RHS
-2
-3
0
0
0
1
0
1
1
1
0
0
0
5
1
2
0
1
0
0
8
2
-1
0
0
-1
1
4
←°ádek kritéria ←1. omezení ←2. omezení ←3. omezení
KAPITOLA 1.
10
LINEÁRNÍ PROGRAMOVÁNÍ
Úprava simplexové tabulky: 1. e²íme celý problém pro kritérium
z = xA → max xA = 1
(a) vynulujeme °ádek kritéria, necháme pouze
x1
x2
s1
s2
s3
xA
RHS
0
0
0
0
0
1
0
1
1
1
0
0
0
5
1
2
0
1
0
0
8
2
-1
0
0
-1
1
4
(°e²íme pro
c = 0,
tj.
min z = xA
←°ádek kritéria ←1. omezení ←2. omezení ←3. omezení
(b) omezení, kde bylo opa£né znaménko (nespl¬ující základní podmínku) ode£teme od °ádku kritéria,
x1
x2
s1
s2
s3
xA
RHS
-2
1
0
0
1
0
0
1
1
1
0
0
0
5
1
2
0
1
0
0
8
2
-1
0
0
-1
1
4
(c) v míst¥, kde je v °ádku kritéria u prom¥nných
←°ádek kritéria ←1. omezení ←2. omezení ←3. omezení
xi
záporná hodnota - tento sloupe£ek
je nutno vynulovat - klí£ový sloupec. Postupujeme jako p°i standardní úloze a pro omezení v klí£ovém sloupci najdeme nejmen²í podíl pravé strany a prvku v klí£ovém sloupci
→klí£ový
°ádek.
x1 kde je hodnota −2. Pro první omezení je to 5 8 = 5 , pro druhé omezení je to podíl 1 1 = 4 a pro t°etí omezení je to podíl 2. Men²í podíl je v °ádku s t°etím omezením, a to bude tedy klí£ový °ádek.
V na²em p°ípad¥ je klí£ový sloupec podíl
4 2 = V na²em p°ípad¥ bude nový klí£ový °ádek
x1
x2
s1
s2
s3
xA
RHS
2
-1
0
0
-1
1
4
a klí£ový prvek bude
x1
1 1 1 2 + x2 + s3 − xA 2 2 2
=
Výsledná tabulka pak bude
x1
x2
s1
s2
s3
xA
RHS
0
0
0
0
0
1
4
0
1,5
1
0
0,5
-0,5
3
0
2,5
0
1
0,5
-0,5
6
1
-0,5
0
0
-0,5
0,5
2
←°ádek kritéria ←1. omezení ←2. omezení ←3. omezení
2. Ve výsledné tabulce nahradíme °ádek kritéria p·vodním a vynecháme sloupec s cal variable).
x1
x2
s1
s2
s3
RHS
-2
-3
0
0
0
0
0
1,5
1
0
0,5
3
0
2,5
0
1
0,5
6
1
-0,5
0
0
-0,5
2
←°ádek kritéria ←1. omezení ←2. omezení ←3. omezení
xA
(arti-
KAPITOLA 1.
11
LINEÁRNÍ PROGRAMOVÁNÍ
3. Pokra£ujeme jako u standardní úlohy, viz 1.4.1. V na²em p°ípad¥ bude °e²ení následující: (a) klí£ový °ádek
(b) klí£ový °ádek
Výsledek: x2 = 3
a
x2 ...
hledání minimálního podílu: 1. omezení
x1
x2
s1
s2
s3
RHS
-2
0
2
0
1
6
0
1
0
0
1
0
1 3 1 3 − 31
2
0
2 3 − 53 1 3
x1 ...
1 0
1 3
←°ádek kritéria ←1. omezení ←2. omezení ←3. omezení
hledání minimálního podílu: 3. omezení
x1
x2
s1
s2
s3
RHS
0
0
0
1
0
0
1
0
1 3 1 3 1 3 − 13
12
0
2 3 2 3 − 53 1 3 2
0 1 0
2 1 3
=2
=3
←°ádek kritéria ←1. omezení ←2. omezení ←3. omezení
Optimálním °e²ení nalezené simplexovou metodou v tomto p°ípad¥ je pro
s2 = 1.
Hodnota kritéria
J = 12.
x 1 = 2,
Kapitola 2
Modely lineárního programování Optimaliza£ní úlohy lineárního programování se li²í podle cíle, kterého chceme dosáhnout. Jinak bude vypadat úloha, kde se maximalizuje zisk a jinak úloha, kde se minimalizují náklady. Proto bychom si p°ed za£átkem práce m¥li odpov¥d¥t na základní otázky: 1. co je cílem optimalizace (£eho chceme dosáhnout)? 2. co jsou °ídící veli£iny (jak m·ºeme ovlivnit cíl)? 3. co nás omezuje (jaké jsou na²e limity)? Odpov¥dí je n¥kolik a dají se rozd¥lit do n¥kolika model·. Práv¥ t¥mto model·m se bude v¥novat následující kapitola, kdy zde budou uvedeny základní optimaliza£ní úlohy. Ke kaºdé úloze bude uvedeno zadání, stru£né vysv¥tlení a p°ipojen odkaz na °e²ení v jednom z níºe uvedených program·.
2.1
Obecný p°íklad lineárního programování
Zadání úlohy: Ur£ete hodnoty prom¥nné
x = [x1 , x2 ],
která maximalizuje kritérium
J = c1 x1 + c2 x2 a vyhovuje podmínkám
3x1 + 5x2
≤ 15
2x1 + x2
≤ 8
x2
≤ 2
x1 ≥ 0, x2 ≥ 0 Zvolte váhy podle následujích varianty a vysv¥tlete výsledky: 12
KAPITOLA 2.
13
MODELY LINEÁRNÍHO PROGRAMOVÁNÍ
1.
c = [5, 1],
2.
c = [1, 1] ,
3.
c = [1, 3] ,
4.
c = [−1, 1].
e²ení gracké: Geometrická interpretace úlohy je na následujícím obrázku
x2 [0, 8]
criterion 3
criterion 3
direction of maximization
criterion 2 criterion 1
[0, 3] [5/3, 2] [0, 2] [6/7, 25/7] admissible
[4, 0]
[5, 0]
solutions
e²ení varianta 1-3: 1. pro simplexovou tabulku (ru£ní výpo£et)
x1
KAPITOLA 2.
14
MODELY LINEÁRNÍHO PROGRAMOVÁNÍ
5x1 + x2
→ max
x1 + x2
→ max
x1 + 3x2
→ max
3x1 + 5x2 + s1
=
15
3x1 + 5x2 + s1
=
15
3x1 + 5x2 + s1
=
15
2x1 + x2 + s2
=
8
2x1 + x2 + s2
=
8
2x1 + x2 + s2
=
8
x2 + s3
=
2
x2 + s3
=
2
x2 + s3
=
2
x1
≥
0
x1
≥
0
x1
≥
0
x2
≥
0
x2
≥
0
x2
≥
0
varianta 1
varianta 2
varianta 3
2. pro Excel (UvodniPriklad.xlsx)
varianta 1
varianta 2
varianta 3
V programu Excel se m¥ní pouze váha ceny (oranºové pozadí) bez zm¥ny podmínek. Hodnota kritéria (zelené pozadí) a hodnoty parametr·
xi
se vypo£tou po pu²t¥ní e²itele.
Výsledek je zobrazen naho°e v bu¬kách s modrým pozadím.
2.2
Optimální produkce - 2 výrobky
Zadání úlohy (1): V jednom podniku se vyrábí výrobky A a B. K jejich výrob¥ jsou zapot°ebí dva drahé stroje, jejichº vyuºití je omezeno a doba k výrob¥ jednotlivých výrobk· se li²í. Jednotlivé £asy jsou uvedeny v tabulce
Cílem je navrhnout produkci výrobk· A a B tak, aby byla maximální.
KAPITOLA 2.
15
MODELY LINEÁRNÍHO PROGRAMOVÁNÍ
Stroj
as stroj· pot°ebný na 1000 výrobk·
as stroj·
[h]
k vyuºití
Produkt A
Produkt B
1
4
6
24
2
4
2
12
[h]
Tabulka 2.1: Optimální produkce - dva výrobky
e²ení (1): Maximalizujeme kritérium
J kde
x1
x2
a
=
c1 x1 + c2 x2
je produkce výrobk· A a B v tisících a
c1 = c2 .
Formulace úlohy je tedy následující
x1 + x2 → max Dále sestavíme podmínky pro lineární programování
4x1 + 6x2
≤ 24
4x1 + 2x2
≤ 12
x1 ≥ 0, x2 ≥ 0
Excel: Podmínky zadáme do Excelu (produkce2Vyrobky.xlsx) Zadání úlohy (2): P°edchozí zadání úlohy (1) je roz²í°eno o znalost cen. Ceny výrobk· jsou nastaveny následovn¥:
c1 = 10
pro výrobek A a
c2 = 20
pro výrobek B. V tomto p°ípad¥ se jiº cena obou výrobk·
neshoduje a my chceme docílit maximálního zisku.
e²ení (2): Nové kritérium bude
10x1 + 20x2 → max kde
x1
a
x2
je produkce výrobk· A a B v tisících a
c1 = 10
Podmínky jsou stejné jako v p°edchozím zadání.
Excel: Podmínky zadáme do Excelu (produkce2Vyrobky.xlsx)
resp.
c2 = 20
je cena výrobku.
KAPITOLA 2.
16
MODELY LINEÁRNÍHO PROGRAMOVÁNÍ
Zadání úlohy (3): P°edchozí zadání úlohy (1) je roz²í°eno o novou informaci. Podnik podepsal dohodu s dodavatelem, ºe minimální produkce výrobk· bude 1 tisíc (nezapome¬te, ºe p·vodní produkce byla také v tisících). Náklady na výrobu jednotlivých výrobk· jsou
n1 = 5
a
n2 = 10.
Cílem je
minimalizovat výdaje.
e²ení (3): Nové kritérium bude
5x1 + 10x2 → min kde
x1
a
x2
je produkce výrobk· A a B v tisících a
n1 = 5
resp.
n2 = 10
je cena výrobku.
x1 ≥ 1, x2 ≥ 1 Dále sestavíme podmínky pro lineární programování
4x1 + 6x2
≤ 24
4x1 + 2x2
≤ 12
x1 ≥ 1, x2 ≥ 1 Na rozdíl od p·vodního zadání (1) je zde zakomponováno, ºe min. produkce je 1 (x1
≥ 1, x ≥ 1).
Excel: Podmínky zadáme do Excelu (produkce2Vyrobky.xlsx) 2.3
Optimální produkce s omezenými zdroji
Zadání úlohy: Továrna s dv¥ma provozy produkuje výrobek A (hliníková trubka), který se prodává samostatn¥ a nebo jako sou£ást pro výrobek B (dopravní zna£ka). Oba výrobky pot°ebují ur£itou surovinu S (Al plech), jejíº zdroj je omezen. Kolik suroviny resp. výrobk· A je pot°eba k výrob¥ výrobk· B je specikováno v tabulce:
Spot°eba
K dispozici
na jednotku produkce
celkem
pouºitý materiál
výrobek A
výrobek B
Surovina
5
2
3000
výrobek A
0
1
Cena produktu (v tis. K£)
5
10
× ×
KAPITOLA 2.
MODELY LINEÁRNÍHO PROGRAMOVÁNÍ
17
Vysv¥tlení tabulky: pro vyrobení výrobku A je pot°eba 5 surovin (k výrob¥ 1 hliníkové trubky je pot°eba 5 Al plech·), ale ºádný dal²í výrobek A. Pro vyrobení výrobku B je pot°eba 2 surovin a 1 výrobek A (k vyrobení celé zna£ky je krom¥ 2 Al plech· pot°eba je²t¥ hliníková trubka). Na sklad¥ je k dispozici 3000 ks surovin (Al plech·). Výrobek A se prodává za 5 000, výrobek B za 10 000. Dále byla stanovena podmínka, ºe na konci musíme mít min. 250 ks výrobk· A. Po£et výrobk· B není omezen. Poºadujeme:
1. maximální produkci, 2. maximální zisk.
e²ení : Podmínky jsou spole£né pro ob¥ variaty, tedy jak pro maximální produkci tak pro maximální zisk
5x1 + 2x2 ≤ 3000
x1 − x2 ≥ 250
x1 ≥ 0, x2 ≥ 0
e²ení (1): Kritérium pro maximální produkci
x1 + x2 → max, x1
je po£et kus· A a
x2
pro B.
Excel: Podmínky zadáme do Excelu (produkceSeSurovinou.xlsx) e²ení (2): Kritérium pro maximální zisk
5x1 + 10x2 → max .
Excel: Podmínky zadáme do Excelu (produkceSeSurovinou.xlsx)
KAPITOLA 2.
2.4
18
MODELY LINEÁRNÍHO PROGRAMOVÁNÍ
Optimální produkce s výb¥rem surovin
Zadání úlohy: Továrna produkuje dva výrobky
B1
B2 . Na výrobu B1 pot°ebuje látku L1 , na B2 látku L2 . A1 , A2 , A3 a A4 , které je t°eba zakoupit. Kaºdá surovina
a
Tyto látky je moºno získat ze surovin
dá jiné mnoºství látek. a Specikace je v tabulce
Surovina
Látka
L1 L2
(pro (pro
B1 ) B2 )
Cena za surovinu
A1
A2
2
10
10 20
→ látka A3
Pot°ebné mnoºství
A4
látky
5
20
1000
1
1
×
2000
10
5
10
Vysv¥tlení tabulky: pro vyrobení látky L1 (resp. L2 ) pot°ebuje 2 (resp. 10) suroviny A2 nebo 10 (resp. 1) surovin A2 nebo 5 (resp. 1) surovin A3 nebo 20 surovin A4 . Víme, ºe pot°ebujeme nakoupit takové mnoºství surovin, abych vyrobili min. 1000 látky
A3 a
10 pro
L1 resp.
2000 látky
L2 .
Cena za surovinu je 20 pro
A1 ,
10 pro
A2 ,
5 pro
A4 .
Cílem je navrhnout koupi surovin tak, abychom minimalizovali výdaje.
e²ení: Kritérium pro minimální výdaje
20x1 + 10x2 + 5x3 + 10x4 → min kde
x1 , x2 , ...
jsou navrhovaná mnoºství zakoupených surovin.
Dále sestavíme podmínky pro lineární programování
2x1 + 10x2 + 5x3 + 20x4
≥ 1000
10x1 + 5x2 + x3
≥ 2000
Excel: Podmínky zadáme do Excelu (VyberSurovinNaVyrobu.xlsx) 2.5
Optimální míchání
2.5.1 Úloha £. 1 (krmná sm¥s) Zadání úlohy: Pro výkrm jednoho kusu dobytka je zapot°ebí 2.5 kg krmné sm¥si a 240 g protein· na den. Pro krmení se pouºívá píce a kuku°ice. Dal²í specikace jsou v tabulce
KAPITOLA 2.
19
MODELY LINEÁRNÍHO PROGRAMOVÁNÍ
Krmivo
krmná sm¥s/kg krmiva
proteiny/kg krmiva
cena K£/kg
Píce (x1 kg)
1
0.4
0.5
Kuku°ice (x2 kg)
1.25
0.08
0.4
Pot°ebné mnoºství
2.5
0.24
Vysv¥tlení tabulky: Z jednoho kg píce se získá 1 kg krmné sm¥si a 400 g protein·. Z jednoho kg píce se získá 1.25 kg krmné sm¥si a 80 g protein·. Cena jednoho kg píce je 0.50 K£ a kuku°ice 0.40 K£. Cílem je vytvo°it takovou krmnou sm¥s, která bude za spln¥ní poºadovaných podmínek nejlevn¥j²í.
e²ení: Kritérium pro minimální výdaje
0.5x1 + 0.4x2 → min kde
x1
zna£í mnoºství píce,
x2
mnoºství kuku°ice.
Dále sestavíme podmínky pro lineární programování
x1 + 1.25x2 0.4x1 + 0.08x2
≥ 2.5 ≥ 0.24
V p°ípad¥, ºe nechceme ºádné zbytky, budeme mít p°esné mnoºství, místo ménko
≥
pouºijeme zna-
=.
Excel: Podmínky zadáme do Excelu (KrmnaSmes.xlsx)
2.5.2 Úloha £. 2 (optimální strava v¥z¬·) Zadání úlohy: Ve v¥zení navrhují optimální stravu v¥z¬·. Cht¥jí ji kombinovat z mléka, fazolí a pomeran£·. P°i tom je t°eba dodrºet minimální poºadavky na obsah stravy podle zákona. Jedna se o vitaminy:
B3 , B1
a
C.
Obsah t¥chto vitamin· v jednotlivých sloºkách stravy je následující mléko
[l]
fazole
[100 g]
pomeran£e
[1 ks]
poºadavek
B3 B1 C
3.2
4.9
0.8
13
1.12
1.3
0.19
1.5
32
0
93
45
cena (v $)
2
0.2
0.25
Vysv¥tlení tabulky: Z jednoho mléka se získá 3.2 vitamínu B3 , 1.12 vitamínu B1 a 32 vitamínu C . Obdobn¥ je to pro 100g fazolí a pomeran£·. Cena za sklenici mléka je 2 $, za 100g fazolí je to 0.2 $ a za 1 ks pomeran£e je to 0.25 $. Aby byly spln¥ny zákonné poºadavky je nutné dodat 13 jednotek vitamínu B3 , 1.5 jednotek vitamínu B1 a 45 jednotek vitamínu C. Cílem je namíchat stravu tak, aby její cena byla co nejmen²í a zárove¬ byl spln¥n zákon?
1 hodnoty
vitamín· i cena je pouze orienta£ní a neodráºí skute£nost.
1
KAPITOLA 2.
20
MODELY LINEÁRNÍHO PROGRAMOVÁNÍ
e²ení: Kritérium pro minimální výdaje
2x1 + 0.2x2 + 0.25x3 → min kde
x1
zna£í mnoºství mléka,
x2
mnoºství fazolí a
x3 mnoºství
pomeran£·.
Dále sestavíme podmínky pro lineární programování
3.2x1 + 4.9x2 + 0.8x3 1.12x1 + 1.3x2 + 0.19x3 32x1 +
+ 93x3
≥ 13 ≥ 1.15 ≥ 45
V p°ípad¥, ºe chceme p°esné zákonné hodnoty, tak místo
≥
pouºijeme znaménko
=.
Excel: Podmínky zadáme do Excelu (?????.xlsx) 2.6
Minimální tok náklad· v síti
Minimum Cost Network Flow Problem (MCNF) Je dána sí´ (souvislý, orientovaný, acyklický graf s jedním vstupem a jedním výstupem) s uzly a
n
hranami. Písmenem
bi
i, tj. bi < 0
ozna£íme zásobu v uzlu
m
výstupní tok - vstupní tok.
bi > 0 jedná se o zásobovací uzel (zdroj), pro jde o uzel s poºadavkem (cíl) a bi = 0 máme uzel pr·jezdní. S kaºdou hranou je spojena dolní mez Lij a horní mez Uij toku touto hranou. Cílem je ur£it velikosti tok· xij v jednotlivých hranách grafu tak, aby náklady na p°epravu byly minimální, jestliºe jednotková cena transportu po hran¥ ij je cij . P P°edpokládáme, ºe platí i bi = 0 (vyrovnané zdroje a poºadavky).
Jestliºe je pro
e²ení Pomocí LP
X
cij xij → min
ij
X j
xkj −
X
xik = bk , ∀k
i
xij ≤ Uij , xij ≥ Lij , 0 ≤ Lij ≤ Uij , ∀i, j
Poznámka c
a
x
jsou £tvercové matice kde °ádky i sloupce jsou indexovány uzly. Prvky t¥chto matic odpo-
vídají hranám grafu. V¥t²inou ne v²echny hrany existují. Neexistující hrany vyplníme nulami. Jako m¥nící se bu¬ky v Excelu zadáme jen existující hrany - nejlépe vytaºené mimo do vektoru. Pro kriterium i podmínky pr·toku m·ºeme pouºít cele matice (i prvky odpovídajícími neexistujícím hranám - jsou to nuly). Podmínky pr·toku konstruujeme jakoby pro diagonálu matice
x
a d¥láme sum(°ádek)-sum(sloupec), kde v °ádcích xujeme (F4) písmenka a ve sloupcích £ísla adres. Pak lze kopírovat. V²e je vid¥t v Excelu.
KAPITOLA 2.
21
MODELY LINEÁRNÍHO PROGRAMOVÁNÍ
2.6.1 Úloha £. 1 Zadání úlohy: Ze skladu (1) pot°ebujeme dovést zboºí do výrobního závodu (7). K výrob¥ pot°ebujeme 150 výrobk· a m·ºeme je poslat pomocí vlaku nebo nákladního automobilu nebo kombinací t¥chto doprav.. Jedna cesta je kapacitn¥ omezena na 80 ks. Máme následující graf (vlevo), který doplníme zp¥tnou hranou s nulovým ohodnocením (vpravo)
4
4 2
2 zdroj
zdroj
cíl 5
1
cíl 5
1
7
7
3
3
6
6
Uzel 1 je zdrojový se zásobou 150 jednotek toku, uzel 7 je cílový, tj. poºadující 150 jednotek toku. Ostatní uzly jsou p°epravní. Ceny za p°epravu jednotky toku jsou dány v tabulce (matici)
startovní uzel
cílový uzel 1 2 3 4 5 6 7
1
2
3
4
5
6
7
0 0 0 0 0 0 x71
x12 0 0 0 0 0 0
x13 0 0 0 0 0 0
0 x24 x34 0 0 0 0
0 x25 x35 0 0 0 0
0 x26 x36 0 0 0 0
0 0 0 x47 x57 x67 0
Tabulka 2.2: Tabulka jednotek toku
cílový uzel
startovní uzel
1
4
5
6
2
14
18
32
3
9
7
12
1
2
3
5
21
7
4
31
5
29
6 7
35 0
Tabulka 2.3: Tabulka ceny p°epravy hrana
(7, 1)
je zp¥tná s cenou 0. Nepouºité hrany mají nulové ohodnocení (bez ohodnocení).
Maximální kapacita byla zadána jako 80, minimální jako 0.
KAPITOLA 2.
22
MODELY LINEÁRNÍHO PROGRAMOVÁNÍ
e²ení: Kritérium
7 X 7 X
cij xij → min
i=1 j=1 Podmínky konstruujeme pro kaºdý uzel. Jdeme po diagonále - to je a ode£teme
k -tý
°ádek. To se rovná
bk , k = 1, 2, · · · , 7.
k,
a se£teme
k -tý
sloupec
Protoºe jsme doplnili 0, m·ºeme d¥lat
sou£ty vºdy od 1 do 7.
X i
xki −
X
xjk = bk
j
k a °íká, ºe to co p°iteklo minus k -tém prvku diagonály matice x k -tém sloupci rovná se bk .
coº se týká uzlu
to co odteklo je to, co z·stalo (ve skladu). V
Excelu: jsme na
a d¥láme: sou£et prvk· v
sou£et prvku v
Dal²í podmínky jsou
xij ≥ L, xij ≤ U,
p°ípadn¥
k -tém
°ádku minus
xij ≥ 0, xij ≤ U 2 .
Excel: Podmínky zadáme do Excelu (minCostFlow1.xlsx)
2.6.2 Úloha £. 2 Zadání úlohy: Je dáno 9 uzl· podle obrázku
zdroj
cíl zdroj
zdroj
umely uzel
cíl zdroj zpetna hrana
jejichº ohodnocení (cena) je uvedeno v následující tabulce V tomto p°ípad¥ jsou zde 4 zdroje, tzn. 4 uzly jsou zdrojové. Jmenovit¥ se jedná o uzly 1 - 4. Poºadavky jsou 2, tzn. 2 uzly jsou cílové, jmenovit¥ se jedná o uzly 8 a 9. Zásoba ve zdrojových uzlech je
2 Pozor:
Bude-li zadána p°íli² malá maximální kapacita hran, bude problém ne°e²itelný.
KAPITOLA 2.
23
MODELY LINEÁRNÍHO PROGRAMOVÁNÍ
1 1
2
3
4
5
8
4
2
9 8
3
9
4
5
5
6
5
5
7
7
4
6
5
3
4
9
5 6 7
2
8
9
9
8
7
9
3
7
Tabulka 2.4: MCNF - více zdroj· a cíl·
£íslo uzlu
1
2
3
4
zásoba
50
30
20
50
a poºadavky v cílových uzlech jsou £íslo uzlu poºadavek
3
8
9
-100
-50
se £ty°mi zdroji a dv¥ma poºadavky.
e²ení: Graf sám nemá jeden výstupní uzel. Aby se mohla zavést zp¥tná hrana, je t°eba denovat pomocný uzel s
b=0
do n¥hoº vedou pomocné hrany s nulovým ohodnocením. V tomto p°í-
pad¥ uzel £. 10. Ten se pak propojí se vstupem 1 (protoºe ten vede dále do ostatních vstup·). Ohodnocení hran bude u t¥chto nov¥ vytvo°ených hran rovno 0.
Excel: Podmínky zadáme do Excelu (minCostFlow2.xlsx) 2.7
P°i°azovací dopravní problém
Je dáno
z, kde i ∈ {1 · · · m} = M , jednotkami zboºí, a n cílových dj , j ∈ {1 · · · n} = N jednotkami poºadavk·. cij , i ∈ M, j ∈ N je jednotková p°evoz zboºí po hran¥ i, j a xij je mnoºství zboºí p°epravené po této hran¥. Chceme m
zdrojových uzl·, kaºdý s
uzl·, kaºdý s cena za
dosáhnout minima náklad· za p°evoz.
2.7.1 PDP °e²ený pomocí lineárního programování e²ení (1): Kritérium pro minimální náklady za p°evoz
X ij
cij xij → min
KAPITOLA 2.
24
MODELY LINEÁRNÍHO PROGRAMOVÁNÍ
Dále sestavíme podmínky pro lineární programování
X
xij = zi , ∀i
j
X
xij = dj , ∀j
i
xij ≥ 0, ∀ij Lze °e²it p°ímo pomocí LP.
Excel: Podmínky zadáme do Excelu (assignmenProbl.xlsx)
2.7.2 PDP °e²ený pomocí MCNF (min. cost network ow) e²ení (2): Lze °e²it jako MCNF vhodnou úpravou grafu: 1. P°i°adíme
bi = zi , i ∈ M
a
bm+j = −dj , j ∈ N .
2. Vytvo°íme pomocné uzly 0 a
m+n+1 sP nulovými cenami, zdroji i poºadavky P b0 = i bi , i ∈ M a poºadavky bm+n+1 = j bj , j ∈
(tohle je v textu ale nechodí to: zdroji
N ). 3. Uzel 0 spojíme hranami s uzly 1 aº
m
a uzly
m+1
aº
m+n
spojíme s uzlem
m + n + 1.
Tyto hrany mají nulová ohodnocení. 4. Zavedeme zp¥tnou hranu
(m + n + 1, 0)
rovn¥º s nulovým ohodnocením.
5. Ignorujeme horní meze tok· (horní meze m·ºeme a nemusíme zadat). Na takto modikovaný graf aplikujeme MCNF. Modikovaný graf je na obrázku.
b>0 1
b<0 m+1
0
m+n+1
P
P
i bi
j bj
m
m+n
Excel: Podmínky zadáme do Excelu (assignmenProblAsMCNF.xlsx)
KAPITOLA 2.
2.8
25
MODELY LINEÁRNÍHO PROGRAMOVÁNÍ
Nejkrat²í cesta grafem (pomocí MCNF)
Je dána ohodnocená sí´, kde ohodnocení
cij
interpretujeme jako délky jednotlivých hran
Úkol je najít nejkrat²í cestu ze zdrojového uzlu 1 do cílového uzlu
e²íme pomocí MCNF, kde uvaºujeme o p°eprav¥ jednotky toku z uzlu 1 do uzlu
Uij = 1, ∀ij
a
(i, j) .
m. m.
Poloºíme
bi = 0, ∀i.
P°íklad Uvaºujeme graf z obrázku
2
5 8
1
3 10
6 9
4
Hledáme nejkrat²í cestu z uzlu 1 do uzlu 7 (nebo z uzlu s
7
bi = 1 do uzlu s bj = −1) a vyuºíváme
k tomu metodu MCNF.
e²ení: Údaje a °e²ení jsou v programu.
Excel: Podmínky zadáme do Excelu (assignmenProblMinPath.xlsx)
Kapitola 3
Celo£íselné programování 3.1
Formulace úlohy
x, které (i) maximalizují lineární kriterium c0 x = c1 x1 + c2 x2 + · · · + cn xn , (ii) spl¬ují vedlej²í podmínky Ax ≤ b, tedy ai,1 x1 + ai,2 x2 + · · · + ai,n xn ≤ bi , pro i = 1, 2, · · · , m (m podmínek pro n prom¥nných) a (iii) jsou celo£íselné1 .
Nalezn¥te hodnoty vektoru
Zápis standardní úlohy celo£íselného programování je následující:
c0 x → opt2 Ax ≤ b3 x ≥ 0, x ∈ N4
3.2
Formulace celo£íselných program·
3.2.1 Binární veli£iny Binární veli£iny mohou nabývat dvou hodnot 0 nebo 1. Souvisí s rozhodováním: n¥co bude 1, nebo nebude Pokud máme
•
alespo¬
•
práv¥
•
nejvý²e
1 Tato
k
→
n
takových veli£in, lze realizovat jednu z následujících podmínek:
k
bude spln¥no (k nebo více):
bude spln¥no:
k
→
0.
Pn
i=1
Pn
i=1
xi ≥ k ,
xi = k ,
bude spln¥no (k nebo mén¥):
Pn
i=1
xi ≤ k .
úloha je prakticky stejná jako úloha lineárního programování, navíc se ale poºaduje, aby °e²ení
x
bylo
celo£íselné.
2 hledáme optimum 3 nep°ekro£íme limitující omezení (nap°íklad 4 hodnota je z oboru p°irozených £ísel
nem·ºeme vyrobit víc výrobk· neº na které máme materiál)
26
KAPITOLA 3.
27
CELOÍSELNÉ PROGRAMOVÁNÍ
3.2.2 Aktivace omezení y∈ {0, 1} a podmínku a0 x ≤ b. Víme dále, podmínky je B . Zkonstruujeme dal²í podmínku
Uvaºujme binární prom¥nnou levé strany
0
ax
této
ºe maximální hodnota
a0 x − By ≤ b. Tato podmínka °íká
•
je-li
y = 1,
pak p·vodní podmínka je vºdy spln¥na (podmínka je vy°azena)
max(a0 x) = B
⇒
a0 x − B · |{z} 1 ≤0 ⇒ 0≤b y=1
•
je-li
y = 0,
pak p·vodní podmínka z·stává v platnosti
a0 x − B · |{z} 0 ≤b
⇒ a0 x ≤ b.
y=0
Hodnota binární prom¥nné
y
tedy aktivuje nebo deaktivuje p·vodní podmínku
a0 x ≤ b.
3.2.3 Výb¥r z mnoºiny omezení Uvaºujme dv¥ podmínky
0
a1 x ≤ b1
0
a2 x ≤ b2
a
s maximálními hodnotami levých stran
B1
a
B2 .
Poºadujeme, aby alespo¬ jedna podmínka byla vºdy platná. Modelujeme takto 0
a1 x − B1 y1 0
a2 x − B2 y2 y1 + y2
≤ b1 ≤ b2 ≥ 1
5 nebo zavedeme ekvivalentní podmínku
y1 = y 0
a
y2 = 1 − y
a1 x − B1 y
≤ b1
0
a2 x − B2 (1 − y) ≤ b2
3.2.4 Implikované omezení Máme dv¥ omezení
0
a1 x > b1
i druhé (kdyº první neplatí,
0
a2 x ≤ b2 . Chceme aby platilo: kdyº platí první omezení, pak platí 6 7 tak nic). Toto pravidlo lze popsat implikací (⇒) nebo disjunkcí
a
(∨). Pro tu platí
5 Podmínka y + y ≥ 1 1 2
y1 = 1
a
y2 = 1.
°íká, ºe p°ipou²tíme následující moºnosti:
Tedy alespo¬ jedna podmínka je vºdy spln¥na.
6 spojení jestliºe-pak 7 spojka nebo
y1 = 1
a
y2 = 0
nebo
y1 = 0
a
y2 = 1
nebo
KAPITOLA 3.
28
CELOÍSELNÉ PROGRAMOVÁNÍ
Odtud vidíme, ºe
(a ⇒ b)
a
b
a⇒b
a0
b
a0 ∨ b
0
0
1
1
0
1
0
1
1
1
1
1
1
0
0
0
0
0
1
1
1
0
1
1
je stejné jako
(a0 ∨ b),
p°i£emº alternativu umíme - viz p°edchozí
odstavec. Nebo lze pouºít následující postup
Zadání úlohy: Vy°e²te implikaci
x≤4⇒y≤6
0 ≤ x ≤ 10 ⇒ 0 ≤ y ≤ 10
za podmínek
P1 : x ≥ 4 + 6z P2 : y ≤ 10 − 4 (1 − z) z ∈ {0, 1}
e²ení: Je-li x ≤ 4 pak z první P2 y ≤ 6 je aktivována. nastat
8.
podmínky Pro
x≤4
P1
plyne, ºe
m·ºe být
z
z = 1
a tedy
(1 − z) = 0.
Potom podmínka
0 nebo 1 a tedy druhá podmínka m·ºe a nemusí
3.2.5 Alespo¬ k omezení 0
ai x ≤ bi , i = 1, 2, · · · , n. Chceme, aby alespo¬ k z nich bylo spln¥no, tzn. ºe m·ºe být spln¥no k a více neº k . Postupujeme podle p°edchozích dvou odstavc·. Denujeme binární prom¥nné y1 , y2 , · · · , yn . P°i konstrukci omezení lze pouºít dv¥ varianty:
Máme
1.
n
omezení
0
ai x − Bi (1 − yi ) ≤ bi . Omezení
i
je v platnosti, jestliºe
yi = 0.
Pro alespo¬
n X
k
omezení v platnosti musí platit
k
omezení v platnosti musí platit
yi ≥ k,
i=1 2.
0
ai x − Bi yi ≤ bi Omezení
i
je v platnosti, jestliºe
yi = 0. n X
Pro alespo¬
yi
≤ n − k.
i=1
8 Místo
6 a -4 u prom¥nné
z
m·ºeme zvolit libovolné (v absolutní hodnot¥) v¥t²í £ísla. Tato zvolená £ísla
jsou p°esn¥ na hranici tak, abychom dosáhli poºadovaného efektu. P°íli² velká £ísla se ale nedoporu£ují, mohou zp·sobit potíºe p°i °e²ení.
KAPITOLA 3.
29
CELOÍSELNÉ PROGRAMOVÁNÍ
3.2.6 Omezení na oblasti Nech´ omezení tvo°í n¥kolik r·zných oblastí (disjunktních nebo i p°ekrývajících se). Jednotlivé oblasti jsou popsány pomocí lineárních omezení. Ukaºme si toto omezení na následujícím p°íklad¥, kdy platí:
0
0
0
0
0
a1 x ≤ b1 , a2 x ≤ b2 , a3 x ≤ b3
první oblast
a4 x ≤ b4 , a5 x ≤ b5
druhá oblast
... Chceme zaru£it, ºe optimální bod °e²ení bude leºet alespo¬ v jedné z oblastí. Modelujeme takto
1. oblast 0
a1 x − B1 y1 ≤ b1 , 0
a2 x − B2 y1 ≤ b2 , 0
a3 x − B3 y1 ≤ b3 2. oblast 0
a4 x − B4 y2 ≤ b4 , 0
a5 x − B5 y2 ≤ b5 3. oblast ....
Zárove¬ musí platit, ºe
k X
yj ≥ 1
j=1 kde
k
je celkový po£et oblastí. Napravo v poslední podmínce je po£et oblastí z výroku aspo¬ v
jedné oblasti a
y1 , y2 ∈ {0, 1} . Kaºdá yj , j = 1, 2, · · · , k .
rovnice má svoje
Bi
(maximální hodnota levé strany) a
spole£nou veli£inu
3.3
Modelování nelineárních funkci
3.3.1 Fixní náklady V n¥kterých p°ípadech pot°ebujeme modelovat nelineární funkci (nap°. skok v po£átku). Pokud výrobu budeme realizovat, náklady na výrobu ur£itého výrobku se sestává z po£áte£ní investice a dále z investice do kaºdého výrobku. Pokud se výroba nerealizuje, jsou v²echny náklady nula.
KAPITOLA 3.
30
CELOÍSELNÉ PROGRAMOVÁNÍ
Za p°edpokladu, ºe
K
je po£áte£ní skok.
( 0 K + c0 x
pro pro
x=0 . x≥0
Zápis takové úlohy je následující
Ky + c0 x → min9 a podmínky
x ≤ By 10 x ≥ 011
y ∈ {0, 1}
3.3.2 Po £ástech lineární reprezentace M¥jme po £ástech lineární funkce - nap°. tu, co je na obrázku
f(x) 3
1
4
x
První úse£ka je na intervalu se sklonem 3. Prom¥nnou
x
9 hledáme minimální náklady 10 Pro y = 0 dostáváme x = 0
0
4
10
15
(0, 4) a
má sklon 4, druhá na
(4, 10) se sklonem 1 a t°etí na (10, 15) x = δ1 + δ2 + δ3 tak, ºe platí
vyjád°íme jako sou£et t°í £len·
0 ≤ δ1 ≤ 4
délka 1. úseku
0 ≤ δ2 ≤ 6
délka 2. úseku
0 ≤ δ3 ≤ 5
délka 3. úseku
a kriterium je také 0; pro
y=1
je
x≤B
a kriterium je
K + c 0 x.
jsme namodelovali je binárn¥ lineární a kopíruje na²i formulaci úlohy (nelineární funkci náklad·).
11 hodnota
je nezáporná
Tedy to, co
KAPITOLA 3.
31
CELOÍSELNÉ PROGRAMOVÁNÍ
w1 = w2 = 0 0 ≤ δ1 ≤ 4 δ2 = 0 δ3 = 0
w1 = 1 a w2 = 0 δ1 = 4 0 ≤ δ2 ≤ 6 δ3 = 0
w1 = w2 = 1 δ1 = 4 δ2 = 6 0 ≤ δ3 ≤ 5
Tabulka 3.1: Po £ástech lineární funkce
Funkci
f (x)
vyjád°íme takto
f (x) = 4δ1 + δ2 + 3δ3 . Musíme ale zajistit, aby se
δi
zapínala postupn¥ a aby niº²í
Tedy, aby p°i pr·chodu hodnot
x
δi
drºely svou maximální hodnotu.
od 0 do 15 bylo
x≤4 x ∈ (4, 10) x > 10
δ1 x−0
δ2 0
δ3 0
4
x−4
0
4
6
x − 10
To zaru£í následující podmínky s dv¥ma novými binárními prom¥nnými
4w1 ≤ δ1
≤4
6w2 ≤ δ2
≤ 6w1
0 ≤ δ3
≤ 5w2
w1
a
w2
w1 , w2 ∈ {0, 1} D·kaz, ºe p°edpis platí je ukázán v následující tabulce Poslední varianta
w1 = 0
a
w2 = 1
je nep°ípustná a podmínka
6w2 ≤ δ2 ≤ 6w1 → 6 ≤ 0
ji
vylu£uje. Stejnou konstrukci lze provést i pro více interval·, pomocí podmínek
Lj wj ≤ δj ≤ Lj wj−1 , kde
Lj
je délka
j -tého
segmentu.
3.3.3 Aproximace nelineárních funkcí Nelineární funkci m·ºeme vhodn¥ rozd¥lit na intervaly a na nich pouºít lineární aproximace. Po£et takových interval· je závislý na nelineární funkci a musí být zvolen vhodn¥ tak, aby platilo, ºe v intervalu je funkce lineární. Pokud platí toto pravidlo, lze pouºít techniku z p°edchozího odstavce.
KAPITOLA 3.
32
CELOÍSELNÉ PROGRAMOVÁNÍ
3.3.4 Sou£in v kritériu Máme
x1 , x2 , x3 ,
- binární veli£iny,
y ∈ (0, u)
je spojitá nebo diskrétní veli£ina.
Kriterium:
x1 · x2 · x3 · y Zavedeme
w = x1 · x2 · x3 · y
max
a podmínky
w ≤ uxj
w≥u
→
X
→ w − uxj ≤ 0
w ≤y → w−y ≤0 X xi − k + y → u xi − k + y − w ≤ 0
Zadání úlohy: Nalezn¥te hodnoty binárních veli£in
KAPITOLA 3.
CELOÍSELNÉ PROGRAMOVÁNÍ
33
e²ení:
3.4
Metody °e²ení
3.4.1 Metoda v¥tví a mezí (branch and bound) Je to metoda pro °e²ení celo£íselného programování, zaloºená na opakovaném °e²ení pomocí simplexové metody s postupným p°idáváním omezení. Metoda konverguje v kone£ném po£tu krok·, i kdyº doba konvergence m·ºe být dlouhá. Jestliºe úlohu °e²íme tak, ºe jednou simplexovou tabulkou dostaneme °e²ení a to zaokrouhlíme, nemusíme dostat optimální °e²ení. Lze dokázat, ºe optimální °e²ení m·ºe leºet libovoln¥ daleko,
KAPITOLA 3.
34
CELOÍSELNÉ PROGRAMOVÁNÍ
omezení
vrstevnice kritéria optimální LP ?e?ení optimální IP ?e?ení zaokrouhlené LP ?e?ení
Obrázek 3.4.1: Porovnání výsledku LP a IP
viz následující p°íklad.
Zadání úlohy: Podle následujícího zadání, chceme dosáhnout maximálního zisku
x + 5y → max
Dále musíme splnit následující podmínky
x + 5y ≤ 50 x−y ≤5 x + y ≤ 30
e²ení: Úlohu nejd°íve vy°e²íme metodou lineárního programování, kde získáme °e²ení ²ení celo£íselného programování dá °e²ení
[10, 8].
[12.5, 7.5].
e-
Výsledek celo£íselného programování není za-
okrouhlení lineárního programování. Z obrázku 3.4.1 je vid¥t, ºe zaokrouhlené °e²ení leºí od optimální vrstevnice kritéria dále, neº optimální IP °e²ení.
Algoritmus Metody v¥tví a mezí (Branch and Bound - B&B) je: 1. Vezmeme optimální LP °e²ení - nap°.
bu¤ na ose
x
nebo
y
(p·jdeme p°es
x).
[12.5, 7.5]
a tento bod vyjmeme z p°ípustné oblasti
Tj. p°idá dv¥ nová omezení
x ≤ 12
a
x ≥ 13.
KAPITOLA 3.
35
CELOÍSELNÉ PROGRAMOVÁNÍ
Tím vzniknou dv¥ nové p°ípustné oblasti - podoblasti p·vodní, kde jiº optimální bod LP neleºí, ale ºádné celo£íselné °e²ení není vyjmuto. 2. Znovu °e²íme LP úlohu (simplexovou metodou) pro p·vodní úlohu s dal²íma dv¥ma omezeními. 3. Dostaneme optimální °e²ení. Pokud je °e²ení celo£íselné, je konec. Pokud není, pokra£ujeme op¥t od bodu 1. 4. Takhle stále p°idáváme nová omezení, dokud nedostaneme integer °e²ení. e²ení budeme demonstrovat na p°edchozím p°íklad¥.
Ob¥ °e²ení pro
y
LP °e²ení
[12.5, 7.5]
°e²ení
omez
x ≤ 12
x(dolní)
[12, 7, 6]
krit=42.4
x >= 13
krit=42.5
°e²eni
omez
x(horní)
X
°e²ení
omez
y≤7
y (dolní)
[12, 7]
krit=40
°e²ení
omez
x≥8
y (horní)
[10, 8]
krit=42
omez vyhodíme pamatujeme a vyhodíme
vyhovují celo£íselnosti. Druhé má ale vy²²í hodnotu kritéria, proto ho volíme.
Vidíme také, ºe toto °e²ení souhlasí s IP °e²ením.
Lips: Podmínky zadáme do programu Lips (BaB_demo.lpx).
3.4.2 Metoda °ez· (cutting planes) Tato metoda vychází z optimální simplexové tabulky pro LP. Tuto tabulku p°epí²eme do rovnic, v kterých eliminujeme zlomkové koecienty na pravou stranu. Vzniklé rovnice se zlomkovými koecienty znovu °e²íme simplexovou tabulkou. Kon£íme, kdyº jako výsledek obdrºíme celá £ísla.
K soustav¥ omezení p°idáváme dal²í lineární omezení, která vylou£í optimální (zlomkové) LP °e²ení ale zachovají v²echna p°ípustná celo£íselná °e²ení.
Zadání úlohy: Podle následujícho zadání, chceme dosáhnout maximálního zisku
J = 5x + 8y → max Dále musíme splnit následující podmínky
x + y + s1 = 6 5x + 9y + s2 =45 x, y, s1 , s2 > ≥0
KAPITOLA 3.
36
CELOÍSELNÉ PROGRAMOVÁNÍ
e²ení: LP °e²ení tohoto problému dá simplexovou tabulku
(−z) x y
− 54 s1 + 94 s1 − 54 s1
− 43 s2 − 41 s2 + 41 s2
−41 41
=
9 4 15 4
= =
Tu p°epí²eme následujícím zp·sobem
(−z) x y
−2s1 +2s1 −2s1
−s2 −s2
+42 −2 −3
= = =
3 4 1 4 3 4
− 34 s1 − 14 s2 − 14 s1 − 34 s2 − 34 s1 − 14 s2
a to tak, ºe
1. vlevo jsou jen celo£íselné koecienty, 2. vpravo jdou zlomky (a) absolutní hodnoty jsou kladné, (b) koecienty u prom¥nných jsou záporné.
Dále platí: 1. Pro celo£íselné °e²ení je jsou levé strany celá £ísla. 2. Pro
s1 , s2 ≥ 0
jsou pravé strany men²í nebo rovny konstantám.
3. Protoºe konstanty jsou kladné zlomky, musí platit ºe pravé strany jsou
≤ 0 (a tedy i levé).
M·ºeme proto psát
1 3 3 1 3 3 − s1 − s2 ≤ 0 → − s1 − s2 + s3 = 0 4 4 4 4 4 4 1 1 3 1 1 3 − s1 − s2 ≤ 0 → − s1 − s2 + s4 = 0 4 4 4 4 4 4 posledn´ı rovnice je stejn´ a jako prvn´ı To jsou podmínky, které p°idáme k p·vodní úloze a op¥t °e²íme pomocí simplexové tabulky. Celo£íselné °e²ení kon£í výpo£et, pro necelo£íselné vyjdeme z nové simplexové tabulky a pokra£ujeme stejn¥. První °e²ení
KAPITOLA 3.
37
CELOÍSELNÉ PROGRAMOVÁNÍ
z tabulky sestavíme nová omezení pro
s1
a
s2
a p°epo£ítáme na
2x + 3y ≤ 15 4x + 7y ≤ 35. První omezení dá rovnou výsledek
[0, 5]
Kdyº zkusíme druhé omezení, dostaneme
7
11 3, 3
xa y .
Ta jsou
KAPITOLA 3.
CELOÍSELNÉ PROGRAMOVÁNÍ
a museli bychom v hledání dál pokra£ovat.
Lips: Podmínky zadáme do programu Lips (cuts.lpx).
38
Kapitola 4
Modely celo£íselného programování 4.1
Výb¥r projektu
4.1.1 Rozpo£et kapitálu (Capital budgeting)[Hlavni text] Pro tyto úlohy lze denovat úlohu dv¥ma zp·soby:
1. Varianta:
Zadání úlohy: Máme moºnost n¥kolika investic. Z kaºdé investice máme o£ekávaný zisk a kaºdá vyºaduje ur£ité zdroje (prac. síly, suroviny atd.), které jsou omezené. Investici bu¤ realizujeme nebo ne. Jak vybrat investice aby p°inesly maximální zisk a nebyly p°ekro£ené omezené zdroje? Zápis standardní úlohy je následující:
c0 x → min1 ax ≤ b
2
x ∈ {0, 1}3
e²ení: Zavedeme binární prom¥nnou zdroje,
aij
xj .
Dále ozna£íme
- jsou poºadavky investice
j
i-tý
na
cj
- výnosy investice
j , bi
- omezení na
zdroj.
2. Varianta:
1 Jestliºe a ij
se týká dodate£ných investic a je
aij > 0,
pak investice pot°ebují dal²í nance; je-li
investice jiº nance produkuje.
2 nep°ekro£íme limitující omezení (nap°íklad nem·ºeme 3 x = 1 realizovat investici, 0 = nerealizovat investici. 39
do investice vloºit víc neº máme zdroj·)
aij < 0,
pak
KAPITOLA 4.
40
MODELY CELOÍSELNÉHO PROGRAMOVÁNÍ
Zadání úlohy: Máme
n
projekt·, které bychom rádi realizovali, ale nemáme najednou tolik pen¥z. Proto
je budeme realizovat po etapách. Z projektu náklady
at,j .
Pro etapu
t
j
o£ekáváme výnos
máme k dispozici nan£ní £ástku
bt .
cj
a v etap¥
t
vyºaduje
Cílem je dosáhnout maxi-
málního zisku v první etap¥, s ohledem na nan£ní omezení v dal²ích etapách. Zápis standardní úlohy je následující:
J= P
P
j cj yj
→ max4
at,j yj ≤ bt , ∀t5
yt ∈ {0, 1} , ∀j 6
4.1.2 Problém batohu [Nas text, Knapsack] (Knapsack problem) Jedná se o nejjednodu²²í úlohu z t°ídy investi£ního rozhodování.
Zadání úlohy : Jedeme na výlet stopem a balíme si s sebou v¥ci do batohu. Objem (nosnost) batohu je omezený hodnotou M . Jednotlivé v¥ci mají sv·j i = 1, 2, · · · , n. Chceme s sebou vzít
objem (váhu)
mi
a d·leºitost
di
a celkem jich je
n,
tedy
co nejvíce d·leºitých v¥cí tak, aby nebyla p°ekro£ena
kapacita batohu.
Matematická formulace je následující: max x
n X
n X
di xi
i=1
m i xi ≤ M
i=1
xi ∈ {0, 1} , ∀i
LIPS: Podmínky zadáme do programu LIPS (Kapsack0.lpx) nebo pro více v¥cí najednou (Kapsack1.lpx) 4 Hledáme °e²ení, kde získáme maximum z n projekt·, které nelze realizovat najednou 5 nep°ekro£íme limitující omezení (nap°íklad nem·ºeme do investice vloºit víc neº máme 6 x = 1 realizovat investici, 0 = nerealizovat investici.
pen¥z)
KAPITOLA 4.
4.2
41
MODELY CELOÍSELNÉHO PROGRAMOVÁNÍ
Plánování produkce
4.2.1 Velikost dávky - bez kapacity[Kniha] Pro budoucí £asová období máme navrhnout objem produkce tak, aby celkové náklady a produkci a skladování byly minimální a aby poºadavky na produkci v jednotlivých etapách byly spln¥ny. P°edpokládáme neomezenou kapacitu produkce v kaºdém období. P°edpokládáme dále, ºe
•
náklady na produkci jsou úm¥rné její velikosti,
•
celkové náklady v kaºdém období jsou úm¥rné úrovni zásob z p°ede²lého období.
Rozhodujeme, zda
yt
vyráb¥t a pokud ano, kolik vyráb¥t
xt .
Zápis standardní úlohy je následující:
P
t
(ct xt + ft yt + ht st ) → min7 st−1 + xt − st = dt 8 xt ≤ M y t 9
xt ≥ 0, st ≥ 0, y ∈ {0, 1} kde
t
je po£et period;
dt
je poºadavek v period¥
jednotka náklad· na produkci,
ht
t ; ft
je po£áte£ní náklad v period¥
je jednotka náklad· na p°echování výrobk·.
Poznámka: P°i objednávkách je
st−1 + xt − st − bt−1 + bt = dt
Excel: Podmínky zadáme do Excelu (VelikostDavkyBezK.xlsx)
4.2.2 Velikost dávky - s kapacitou [Kniha] Stejné jako v p°edchozím p°ípad¥, jen navíc je ýroba v jednotlivých etapách omezena. Z tohoto d·vodu zavedeme novou prom¥nnou
ut ,
tedy omezení výroby v období
Zápis standardní úlohy je následující:
P
t
(ct xt + ft yt + ht st ) → min10
7 kriterium: minimalizace náklad· na produkci a skladování 8 s - úrove¬ zásob v kaºdém období (s = 0). t 0 9 je pot°eba naplnit poºadavky v kaºdém období a M (kapacita) 10 kriterium: minimalizace náklad· na produkci a skladování
je velké £íslo
→∞
t.
t ; ct
je
KAPITOLA 4.
42
MODELY CELOÍSELNÉHO PROGRAMOVÁNÍ
st−1 + xt − st = dt 11 xt ≤ ut yt 12 xt ≥ 0, st ≥ 0, y ∈ {0, 1} kde
t
je po£et period;
dt
t ; ft
je poºadavek v period¥
jednotka náklad· na produkci,
ht
je po£áte£ní náklad v period¥
t ; ct
je
je jednotka náklad· na p°echování výrobk·.
Excel: Podmínky zadáme do Excelu (VelikostDavkyBezK.xlsx) (jen místo M
se dá ta kapacita)
4.2.3 Produkce na odbyt [Kniha] Máme ur£it velikost produkce n¥kolika výrobk· pro kaºdé období ve správném mnoºství a daném £ase. Snaºíme se mít pokud moºno ºádné nebo malé zásoby. V praxi ale p°ipustíme bu¤ malé zásoby nebo p°echodný nedostatek zboºí. (Jestliºe nedostatek nep°ipustíme, pouºijeme velikou penalizaci
→ ∞).
Cíl je platit co nejmén¥ na pokutách za p°ebytek nebo nedostatek zboºí.
Rozhodujeme, zda
yt
vyráb¥t a pokud ano, kolik vyráb¥t
xt .
Zápis standardní úlohy je následující:
P
pj
j
P
t
d+ j,t + qj
P
t
13 d− j,t → min
sj,t−1 + xj,t − dj,t = sj,t , ∀j, t − 14 sj,t = d+ j,t − dj,t , ∀j, t
xj,t = lj,t yj,t , ∀j, t = 1 · · · T − 1 (x = lj,T ) yj,T , ∀j yj,t ≥ 0, kden je po£et r·zných výrobk·; mnoºství výroby;
pj
T
int
je po£et období;
je jednotková pokuta za p°ebytek;
dj,t jsou poºadavky; lj,t je p°edepsané qj je jednotková pokuta za nedostatek.
Excel: Podmínky zadáme do Excelu (produkceNaSpotrebu.xlsx) 11 s - úrove¬ zásob v kaºdém období (s = 0). t 0 12 je pot°eba naplnit poºadavky v kaºdém období s ohledem na omezení 13 kritérium: minimalizovat platby za p°ebytek nebo nedostatek zboºí 14 Stav: d− a d+ mnoºství nedostatku a p°ebytku; s mnoºství zásob. j,t
j,t
j
kapacitou
KAPITOLA 4.
43
MODELY CELOÍSELNÉHO PROGRAMOVÁNÍ
4.2.4 Objednávka léku [3 p°íklady] Zadání úlohy : m potenciálních dodavatel·. iv m¥síci t je cit . Kaºdý dodavatel i má ur£itou minimální dávku odb¥ru li . Nespot°ebovaná balení léku je moºno schovat do dal²ího období jako zásobu zt , která je v²ak omezena velikostí Z . Zbylá Léka°ské st°edisko má rozhodnout o tom, jak objednat ur£itý lék od St°edisko má pro jednotlivé m¥síce poºadavky
dt , t = 1, 2, · · · , T
a cena léku od dodavatele
balení lék· (které nebyly spot°ebovány a uº se nevejdou do zásoby) se musí vyhodit. Cílem je minimalizovat náklady na po°ízení léku v daném £asovém úseku.
e²ení : Zavedeme prom¥nné:
cit
cena za jedno balení léku od dodavatele
dt
poºadavek na m¥síc
li
kolik balení léku bereme od dodavatele
yit
jestli v·bec bereme (0 ne, 1 ano)
t
gt
kolik toho v m¥síci
t
i
xit
zásoba v m¥síci
v m¥síci
t
minimální odb¥r od dodavatele
zt
i
i
v m¥síc
t
(z minulého m¥síce)
t
vyhodíme
První, co je t°eba ud¥lat, je vypo£ítat zásoby
zt .
Vyjdeme z rovnice vyjad°ující zákon zachováni
hmoty (lék·)
zt−1 +
X
xit = dt + zt + gt
i tedy: co zbylo z minula + co jsme odebrali od dodavatel· se musí rovnat tomu, co jsme spot°ebovali + nechali v zásob¥ + co jsme p°ípadn¥ vyhodili. Odtud je
zz = zt−1 +
X
xit − dt − gt .
i To zadáme do Excelu jako po£ítané bu¬ky. Omezení:
xit ≥ li yit ···
kdyº se nebere, tak se nebere; kdyº ano, tak minimum od dodavatele
xit ≤ 1000yit ···
kdyº se nebere, tak
xit
musí být nula, jinak libovolné
xit ∈ {0, 1} , 0 ≤ zt ≤ Z, gt ≥ 0 Kriterium:
X
cit xit → min
Excel: Podmínky zadáme do Excelu (NakupLeku.xlsx)
i
je li
KAPITOLA 4.
4.3
P°eprava s pevnou cenou [Kniha]
Uvaºujeme
ik
44
MODELY CELOÍSELNÉHO PROGRAMOVÁNÍ
m
odb¥rateli
n
zdroj· a
j
odb¥ratel· jednoho druhu zboºí. Náklady na p°epravu zboºí ze zdroje
zahrnují jednotkovou cenu p°epravy
cij
a pevné náklady
fij ,
nezávislé ne mnoº-
ství p°eváºeného zboºí. Máme nalézt minimální náklady na p°epravu tak, aby byly spln¥ny poºadavky odb¥ratel·
dj .
e²ení xij
- mnoºství zboºí z
i
do
j
yij
- jestli se p°evoz z
i
do
j
bude realizovat nebo ne
Úloha
XX
(cij xij + fij yij ) → min X
xij = dj
i
xij ≤ M yij xij ≥ 0, yij ∈ {0, 1} kde
xij
je mnoºství zboºí z
i
do
j , yij
zna£í, jestli se p°evoz z
i
do
j
bude realizovat (1) nebo ne
(0).
Excel: Podmínky zadáme do Excelu (TranspPevnaCena4.xlsx) 4.4
Problém investi£ního rozhodování [Nas text]
Cílem je rozhodnout o ur£itém mnoºství investi£ních akcí. Akce se bu¤ podpo°í celá, nebo se nepodpo°í v·bec. Akcím p°i°adíme stavový vektor
x = [x1 , x2 , · · · , xn ] , xj ∈ {0, 1} ∀j = 1, 2, · · · , n tak, ºe
xi = 1
znamená podporu akce
i, xj = 0
Zisk plynoucí z jednotlivých akcí ozna£íme
znamená, ºe akce
j
nebude podpo°ena.
cj , j = 1, 2, · · · , n. Akce vyºadují m r·zných zdroj· i-tý zdroj pro akci j ozna£íme ai,j a mnoºství bi (omezení jsou psány pro jednotlivé zdroje).
(nance, lidské síly, suroviny atd.). Náklady na jednotlivých zdroj·, které jsou k dispozici Zápis standardní úlohy je následující:
n X
cj xj → max
j=1 n X j=1 Modikace základní úlohy:
ai,j xj ≤ bi , xj ∈ {0, 1} , i = 1, 2, · · · , m
KAPITOLA 4.
•
45
MODELY CELOÍSELNÉHO PROGRAMOVÁNÍ
Modelování závislostí projekt· - realizace projektu
i
je závislá na realizaci projektu
j.
Lze
modelovat jako
xj ≥ xi . •
Výb¥r nejvý²e jednoho ze skupiny
x1 + x2 + x3 + x4 ≤ 1
Excel: Podmínky zadáme do Excelu (InvesticniRozhodnuti.xlsx) 4.5
Problém po²tovních box· [Nas text]
Zadání úlohy : Firma dostává platby od zákazník·. Tyto platby jdou ze 4 míst: západu - 70tis., st°edozápadu - 50tis., východu - 60tis. a jihu - 40tis. v pr·m¥ru za den. Pro výb¥r t¥chto plateb chce otev°ít pobo£ky (po²tovní boxy). Pro tyto boxy p°ichází v úvahu následující místa: Los Angeles, Chicago, New York a Atlanta. Za otev°ení boxu v kaºdém z t¥chto míst zaplatí stejnou £ástku 50tis. Po£et dní, ve kterých budou platby realizovány, je dán v tabulce
z / do
L.A.
Chicago
New York
Atlanta
západ
2
6
8
8
st°edo západ
6
2
5
5
východ
8
5
2
5
jih
8
5
5
2
Po dobu, kdy je platba uskute£n¥na ale není proplacena jsou peníze pro rmu nedostupné a rma ztrácí úrok 20% z jejich p°ípadné investice. Které z pobo£ek má rma otev°ít, aby co nejvíce u²et°ila?
e²ení : Ztráty z nerealizovaných investic jsou dány v tabulce (v tis.)
kde nap°. západ
z / do
L.A.
Chicago
New York
Atlanta
západ
28
84
112
112
st°edo západ
60
20
50
50
východ
96
60
24
60
jih
64
40
40
16
→
New York je
Zavedeme binární veli£iny na pobo£ku
8 · 70 · 0.2 = 112
yj = 1
- pobo£ka
j.
Zápis standardní úlohy je následující:
j
(dny, platba, procenta).
bude otev°ena, a
xij = 1
- oblast
i
posílá platby
KAPITOLA 4.
46
MODELY CELOÍSELNÉHO PROGRAMOVÁNÍ
28x11 + 84x12 + 112x13 + 112x14 + 60x21 + · · · + 16x44 ++50y1 + 50y2 + 50y3 + 50y4 → min15 xij = 1 ∀i16
P
j
P
i
xij ≤ 4yj ∀j 17
xij , yj ∈ {0, 1} ∀i, j
Excel: Podmínky zadáme do Excelu (LockBoxes.xlsx) 4.6
Propuknutí infek£ního onemocn¥ní [Nas text, 3 p°íklady]
Zadání úlohy: V
n
m léka°ských tým·, které mohou j ∈ {1, 2, · · · , n} vy²et°ovat tij hodin.
místech se vyskytlo infek£ní onemocn¥ní. K dispozici je
onemocn¥ní pro²et°it. Tým
i∈ {1, 2, · · · , m}
bude místo
Kaºdý tým m·ºe obslouºit 0, 1 nebo 2 místa. Jestliºe má tým obslouºit je²t¥ druhé místo (z místa
k do místa l), musí se po£ítat s dobou p°ejezdu dkl . Jakmile jsou v²echna místa pro²et°ena,
m·ºe se s infekcí za£ít bojovat. Cílem je navrhnout plán vy²et°ování tak, aby cela akce byla co nejkrat²í.
e²ení: Denujeme veli£inu
xij ∈ {0, 1}
s hodnotou 1 jestliºe tým
i
bude vy²et°ovat místo
j
a 0, kdyº
nebude. 1. Kriterium
P
j tij xij ,
P
k,l; k6=l
∀i18
dkl xik xil , ∀i19
2. Optimalizace:
min maxi
nP
j tij xij
+
P
k,l; k6=l
dkl xik xil
o
3. Omezení
P
i
xij = 1, ∀j 20
15 kritérium 16 kaºdá oblast musí být p°i°azena jedné pobo£ce 17 neotev°ené pobo£ce se nesmí nic posílat (4 je tam 18 musí se vy²et°it v²echna místa 19 na kaºdé místo se musí cestovat 20 kaºdé místo bude nav²tíveno práv¥ jednou
proto, aby pro
y=1
podmínka vypadla - velké £íslo)
KAPITOLA 4.
47
MODELY CELOÍSELNÉHO PROGRAMOVÁNÍ
P
j
xij ≤ 2, ∀ii21
xij ∈ {0, 1} , ∀i, j Pro kaºdou konstelaci je jeden tým nejdel²í a tohle maximum chceme minimalizovat. Tohle ale neumíme
(i)
nelinearita v sou£inu,
(ii)
minimax.
S nelinearitu lze vy°e²it tak, ºe zavedeme novou prom¥nnou
wikl = xik xil s podmínkami
wikl ≤ xik , wikl ≥ 0, wikl ≤ xil , wikl ≥ xik + xil − 1.
4.6.1 P°íklad 2 týmy (i=1,2),
3 místa (j=1,2,3)
stav
x=
x11 x21
x12 x22
x13 x23
binární
£asy
t= veli£ina
w
t11 t21
t12 t22
t13 t23
(cesta tam a zp¥t je stejn¥ dlouhá)
w=
w1;12 w2;12
w1;13 w2;13
w1;21 w2;21
w1;23 w2;23
w1;31 w2;31
w1;32 w2;32
délky p°ejezdu
d=
8, 12, 8, 14, 12, 14
Podmínky 1.
wi;kl ≥ 0, ∀i, k, l
2.
wi;kl − xik ≤ 0,
3.
wi;kl − xik − xil + 1 ≥ 0 P P j tij xij + kl; k6=l dkl wi;kl − q ≤ 0, ∀i
4. kde
q
wi;kl − xil ≤ 0, ∀i, k, l
je nová veli£ina s významem doba trvání nejdel²í akce.
Úloha
q → min
Excel: Podmínky zadáme do Excelu (infection_small.xlsx, 21 ºádný
tým nenav²tíví více neº dv¥ místa
infection_bigger.xlsx)
KAPITOLA 4.
4.7 Existuje
MODELY CELOÍSELNÉHO PROGRAMOVÁNÍ
48
Pokrytí mnoºin m
poºadavk·
Ri
a
n
aktivit
Aj
takových, ºe v celkovém sjednocení pokrývají v²echny
poºadavky, nikoliv ale jednotliv¥. Cílem je najít takovou podmnoºinu aktivit, která ve sjednocení pokryje v²echny poºadavky a minimalizuje ur£ité kriterium (nap°. náklady na vyuºité aktivity). Existují 3 varianty tohoto problému: (1) Set covering, (2) Set partitioning a (3) Set packing. Jejich formulace jsou následující (li²í se v nerovnítku podmínek): 1. Covering
c0 x → min Ax ≥ 1 x ∈ (0, 1) 2. Partitioning
c0 x → min Ax = 1 x ∈ (0, 1) 3. Packing
c0 x → max Ax ≤ 1 x ∈ (0, 1)
4.7.1 Pokrytí mnoºin - set covering [Kniha] Zadání úlohy : (poºární stanice) Uvaºujme m¥sto, které se skládá z n¥kolika oblastí. Ty jsou zachyceny na obrázku
7 2
6 4
1
5 3
Kaºdé oblasti je p°i°azeno £íslo. Ve m¥st¥ chceme vybudovat poºární stanice. Jedna stanice je schopna pokrýt oblast, ve které je postavena a v²echny sousední oblasti (tj. takové, co sousedí hranou). Jak postavit stanice, aby jich bylo co nejmén¥?
KAPITOLA 4.
49
MODELY CELOÍSELNÉHO PROGRAMOVÁNÍ
e²ení : (poºární stanice) Oblastem p°i°adíme binární prom¥nné
x1 , x 2 , · · · , x 7 .
Tyto prom¥nné budou mít hodnotu 1,
kdyº stanice bude, jinak 0. Kriterium: minimální sou£et
x
Podmínky: oblast 1 a její sousedi musí mít alespo¬ jednu stanici; a dále pro 2,
··· ,
7. Sousední
oblasti jsou
1,2,3 2,1,3,4,6,7 3,1,2,4 4,2,3,5 5,4,6 6,2,5,7 7,2,6
Úloha tedy bude
X
xi → min
i
x1 + x2 + x3 ≥ 1 x1 + x2 + x3 + x4 + x6 + x7 ≥ 1 x1 + x2 + x3 + x4 ≥ 1 x2 + x3 + x4 + x5 ≥ 1 x4 + x5 + x6 ≥ 1 x2 + x5 + x6 + x7 ≥ 1 x2 + x6 + x7 ≥ 1
x1 · · · x7 ∈ {0, 1}
Excel: Podmínky zadáme do Excelu (pozarniStanice.xlsx)
4.7.2 Rozd¥lení a zabalení mnoºin (partitioning, packing) [Kniha] Zadání úlohy
: (výb¥r jídel z kucha°ky)
ekáme neohlá²enou náv²t¥vu a chceme ji pohostit. Ve spíºi máme 7 ingrediencí do jídla a dal²í uº nesta£íme po°ídit. Nevíme ale, jaké chut¥ náv²t¥va má, a proto chceme p°ipravit co nejv¥t²í po£et jídel. Máme kucha°ku a z ní jsme vybrali jídla, která obsahují ty ingredience, které máme k dispozici. Ingredience ale nelze d¥lit; kaºdou lze pouºít jen jednou. O£íslujeme-li ingredience 1,2,· · · ,7, pak vybraná jídla podle kucha°ky pot°ebují
KAPITOLA 4.
50
MODELY CELOÍSELNÉHO PROGRAMOVÁNÍ
jídlo
ingredience
A
1,2
B
1
C
2,5,6
D
3,7
E
2,7
F
3,5
G
4,5,6
Která z jídel m·ºeme p°ipravit, aby jich bylo co nejvíce?
e²ení : (výb¥r jídel z kucha°ky) B, C, D.
Excel: Podmínky zadáme do Excelu (recepty.xlsx)
4.7.3 Rozmíst¥ní sklad· (Warehouse location) [Nas text, Hlavni text] Máme
m sklad· a n zákazník·. Máme obstarat a dovézt zboºí, které poºadují zákazníci. Jde o to,
rozhodnout, ze kterého skladu a kolik daného zboºí nakoupit a p°evézt jednotlivým zákazník·m tak, aby cena za nákup a p°evoz byla minimální. Ty sklady, pro které se rozhodneme, musíme pronajmout, a to n¥co stojí.
yi
ozna£uje, zda sklad
fi
je cena pronájmu
i
je pronajatý (yi
i-tého
= 1)
je mnoºství zboºí, zakoupeného ve skladu
ci,j
je cena za nákup jednotky zboºí
poºadavek
j -tého
= 0).
skladu.
xi,j
dj
nebo není (yi
i
a p°evezeného zákazníkovi
xi,j .
zákazníka.
Zápis standardní úlohy je následující:
Pm Pn i=1
j=1 ci,j xi,j
Pm
i=1
Pn
+
Pm
i=1
fi yi → min22
xi,j = dj , j = 1 · · · n23
j=1 xi,j − yi
P
n j=1
dj ≤ 0 , i = 1 · · · m24
xi,j ≥ 0 , ∀i, ∀j 22 celková cena za zboºí a dovoz + 23 spln¥ní poºadavk· zákazník·; 24 odb¥r jen z pronajatých sklad·
poplatky za pronájem sklad·
j.
KAPITOLA 4.
MODELY CELOÍSELNÉHO PROGRAMOVÁNÍ
51
yi ∈ {0, 1} , ∀i kde
yi
i je pronajatý (yi = 1) nebo není (yi = 0), fi je cena pronájmu i-tého i a p°evezeného zákazníkovi j , ci,j je cena xi,j , dj poºadavek j -tého zákazníka.
ozna£uje, zda sklad
skladu,
xi,j
je mnoºství zboºí, zakoupeného ve skladu
za nákup jednotky zboºí
D·kaz, ºe platí, ºe zboºí lze odebrat jen z pronajatých sklad· je následující
n X
xi,j
n X ≤ yi dj , ∀i
j=1 tedy, pro
i
takové, ºe
yi = 0
j=1
dostaneme
n X
xi,j ≤ 0
j=1 a protoºe pro
xi,j
yi = 1
jsou nezáporné, znamená to, ºe k ºádnému odb¥ru z t¥chto sklad· nedo²lo,
máme
n X
xi,j ≤
j=1
n X
dj
j=1
tedy celkové mnoºství zboºí, odebrané ze skladu
i
je men²í nebo rovno celkovému poºadavku
25
v²ech zákazník· (rovno, kdyby se bralo v²echno z jednoho skladu).
Excel: Podmínky zadáme do Excelu (pozarniStanice.xlsx) 4.8
Problém p°i°azení [Kniha]
Zadání úlohy : Uvaºujeme neorientovaný graf. Hledáme podvýb¥r jeho hran tak, ºe kaºdý uzel má nejvý²e jednu hranu (hrany spojují odd¥lené dvojice uzl·) a hran je maximální po£et.
e²ení : Zavedeme uzlo-hranovou inciden£ní matici
a
(svisle uzly, vodorovn¥ hrany) a binární vektor
dimenzí po£et hran kde 1 znamená hrana je vybrána, 0 hrany není vybrána. Zápis standardní úlohy je následující:
X
yj → max
X
aij yj ≤ 1
yj ∈ {0, 1}
Excel: Podmínky zadáme do Excelu (matchingProblem1.xlsx) 25 P d
j je z°ejm¥ to nejmen²í velké £íslo, aby se podmínka vºdy splnila.
y
s
KAPITOLA 4.
52
MODELY CELOÍSELNÉHO PROGRAMOVÁNÍ
Poznámka Varianta této úlohy je, kdyº poºadujeme, aby kaºdý uzel mel nejvý²e
m
hran. Potom podmínka
je
X
4.9
aij yj ≤ m.
Problém °ezání [Kniha]
4.9.1 ezání ty£í Zadání úlohy : Máme ty£e dlouhé 7.4 m a chceme z nich na°ezat kusy dlouhé 150, 210 a 290 cm. Jednotlivé délky pot°ebujeme v mnoºství 1000 ks. Jak máme postupovat, kdyº chceme mít minimální odpad?
e²ení : Nejprve stanovíme tzv. °ezné plány Délka
Ozna£íme
x1 · · · x6
Plán °ezání 1
2
3
4
5
290
1
2
-
1
-
6 1
210
-
-
2
2
1
1
150
3
1
2
-
3
1
Odpad
0
10
20
30
80
90
jsou mnoºství °ezání podle jednotlivých plán·. Úloha je:
10x2 + 20x3 + 30x4 + 80x5 + 90x6 → min x1 + 2x2 + x4 + x6 = 1000 2x2 + 2x4 + x5 + x6 = 1000 3x1 + x2 + 2x3 + 3x5 + x6 = 1000.
Excel: Podmínky zadáme do Excelu (RezaniTyci.xlsx)
4.9.2 ezání papíru Zadání úlohy : W . Pro dal²í prodej se °eºe na pásy o p°edepsaných w1 , w2 , · · · , wm . Jednotliví odb¥ratelé si si p°edepisují po£et rolí bj na°ezaných na ur£itý
Papír se p°i výrob¥ balí do rolí o vý²ce ²í°kách
rozm¥r. Jak role °ezat, aby byl co nejmen²í odpad?
KAPITOLA 4.
53
MODELY CELOÍSELNÉHO PROGRAMOVÁNÍ
e²ení : Kriterium je minimální odpad - tedy výroby
P
yj
P
j
Tj → min
nebo, coº je totéº, minimální po£et rolí z
coº je vlastn¥ po£et °ezání (podle r·zných plán·).
Poznámka Zbytky po °ezání mohou být po£ítány takto
Tj = W −
X
wi aij
i
4.10
TSP - Problém obchodního cestujícího [Nas text, Kniha]
4.10.1 Asymetrický TSP Uvaºujeme
n
m¥st spojených navzájem cestami. Kaºdou cestu uvaºujeme jako jednosm¥rnou,
obousm¥rné jsou dv¥ jednosm¥rky tam a zp¥t. Kaºdá z jednosm¥rek má svou délku (obecn¥ se délka cesty tam nerovná délce zp¥t). Cílem je najít cestu, kterou má projít obchodní cestující tak, aby kaºdé m¥sto nav²tívil práv¥ jednou a vrátil se do stejného m¥sta, ze kterého vy²el. Celá cesta má být nejkrat²í moºná.
Zadání úlohy : Úlohu budeme demonstrovat pro 5 m¥st.
2
d12
4
d21 1
x31 5
x13 3
dij ≥ 0
zna£í délky cest,
xij ∈ {0, 1}
znamená
xij = 1
cestující p·jde z m¥sta
i
do m¥sta
j
;
xij = 0
nep·jde.
KAPITOLA 4.
54
MODELY CELOÍSELNÉHO PROGRAMOVÁNÍ
e²ení : Pro nejkrat²í cestu musí platit
J=
X
dij xij → min
ij Omezení 1: m¥sta se nesmí opakovat
→
kaºdé m¥sto má jen jednu vstupní cestu a jednu
výstupní, tj.
X
xij = 1, ∀j
výstupní
i
X
xij = 1, ∀i
vstupní
j Omezení 2: cesta se nesmí skládat z odd¥lených cykl· - to je problematický a °e²í se r·zn¥. My budeme postupovat následovn¥: Sestavíme v²echny Pro
n=5
bude
k -krokové
k = 2, 3
cykly,
k = 2, 3, 4, · · · , n − 226
a sou£et
xij
v nich musí být
≤k − 1.
a tedy
2-krokové: 12, 13, 14, 15, 23, 24, 25, 34, 35, 45 (a vºdy návrat do prvního, tedy 121, 131, · · · ) 3-krokové: (dohromady jich bude 2 × 53 = 2 × 10 = 20) z uzlu 1: 123, 124, 125, 134, 135, 145, z uzlu 2: 234, 235, 245, z uzlu 3: 345 (a návrat do po£. uzlu - na konci bude je²t¥ £íslo z po£átku); A odzadu: z uzlu 1: 1321, 1421, 1521, 1431, 1531, 1541 z uzlu 2: 2432, 2532, 2542 z uzlu 3: 3543 Návod
•
Za£ínáme od 1 a postupn¥ zvy²ujeme 123
•
Pak zv¥t²ujeme poslední aº do
•
Pak zvý²íme p°edposlední, následuje o jedna v¥t²í 134
•
A zase zvy²ujeme poslední.
•
A tak dál
n
123, 124, 125
Excel: Podmínky zadáme do Excelu (TSP_asym5.xlsx) 26 Ve
skute£nosti sta£í kontrolovat cykly od 2 do
n 2
,
kde
[·]
zna£í celou £ást £ísla. Je to proto, ºe kdyº se
v grafu vytvo°í cyklus, musí být zbylé uzly také v cyklu - pro kaºdý uzel poºadujeme jednu vstupní a jednu výstupní hranu. Pro cyklus s
k
kroky, kde
jsme jiº kontrolovali mezi cykly 2,3· · ·
,
n 2
n k> n tedy bude v grafu je²t¥ jeden cyklus s délkou l ≤ , který 2 2 n . Vedle cyklu s délkou v¥t²í neº 2 m·ºe být také více dal²ích cykl·,
ty ale budou také pat°it mezi jiº kontrolované.
KAPITOLA 4.
55
MODELY CELOÍSELNÉHO PROGRAMOVÁNÍ
Obchodní cestující - 5 měst podmínka na "každé město jednou" x 1 2 3 4 1 0 0 1 0 2 1 0 0 0 3 0 0 0 1 4 0 0 0 0 5 0 1 0 0 1
1
kritérium J= 12
5
0 0 0 1 0
1
1
1
1 1 1 1 1
pro sestavení kritéria
tady je možno zadat apriorní hodnoty x (i když to prakticky nemá význam)
12
13
14
15
21
23
24
25
31
32
34
35
41
42
43
45
51
52
53
54
0 5
1 1
0 8
0 4
1 2
0 9
0 1
0 1
0 1
0 8
1 7
0 6
0 4
0 9
0 6
1 1
0 3
1 1
0 6
0 5
x d
Tady se zadávají délky cest
2 2
1 1
9 5
8
1
4
9 4 6
4 1
1 8
1 3 6
7 6
1
5 5
3
podmínka na cykly II III nemusí se hlídat vůbec 1 protože mohou být jen v kombinacích 1 s dvoukrokovými - a ty už se hlídají 0 0 0 0 1 1 0 1 dvou-krokové
Hlídáme 2 a 3-krokové cykly. 2-krokové jsou OK ihned. 3-krokové bychom museli hlídat tam i zpět, ale v kombinaci s 3-krokovým by musel být 2-krokový a ty se hlídají. Takže zpět nemusíme! Dokonce 3-krokové nemusíme vůbec!!!
Poznámka V podmínkách na cykly musíme hlídat, aby nenastala situace, ºe se v grafu utvo°í dva odd¥lené cykly. 1-krokové cykly nemohou nastat nikdy, protoºe smy£ky v grafu jsou vylou£eny (prvky na diagonále inciden£ní matice se neuvaºují). 2-krokové cykly jsou tam a zp¥t - obsahují tedy oba cykly (po sm¥ru i proti sm¥ru). 3-krokové cykly bychom museli hlídat v obou sm¥rech - tedy po sm¥ru i proti sm¥ru - tj. to, co jsme vý²e uvedli nap°. 1231 a je²t¥ zp¥t 1321. Protoºe ale 3-krokový cyklus muºe být v kombinaci jedin¥ s 2-krokovým (a ty jsou jiº hlídány) nemusíme je jiº v na²em p°ípad¥ (5 m¥st) v·bec hlídat! Sta£í kontrolovat cykly od 2 do
n 2
, kde [·] zna£í celou £ást £ísla. Je to proto, ºe kdyº se v grafu
vytvo°í cyklus, musí být zbylé uzly také v cyklu - pro kaºdý uzel poºadujeme jednu vstupní a jednu výstupní hranu. Pro cyklus s
neº
2
kroky, kde
k>
n 2
tedy bude v grafu je²t¥ jeden cyklus
, n2 . Vedle cyklu s délkou v¥t²í 2 m·ºe být také více dal²ích cykl·, ty ale budou také pat°it mezi jiº kontrolované.
n l ≤
s délkou
k
n
, který jsme jiº kontrolovali mezi cykly 2,3· · ·
4.10.2 Symetrický TSP Na rozdíl od p°edchozího jsou v²echny cesty obousm¥rné. Inciden£ní matice je horní trojúhelník. Kontrola na kaºdé m¥sto jednou se provádí takto:
KAPITOLA 4.
•
56
MODELY CELOÍSELNÉHO PROGRAMOVÁNÍ
Pro kaºdý prvek inciden£ní matice na diagonále (to je to m¥sto) se se£tou prvky nad ním a vpravo od n¥ho.
•
Tento sou£et (po£et cest ve trase, které jím prochází) musí být
≤
2.
Kontrola cykl·:
•
2-krokové cykly se nemusí kontrolovat, protoºe
x
je zadáno jako binární (cyklus by dal 2,
protoºe jdeme tam a zp¥t po stejné cest¥),
• k -krokové
cykly sta£í kontrolovat jen po sm¥ru - proti sm¥ru jsou stejné.
Program: TSP_sym5.xlsx
x 1 2 3 4 5
c
1
2
3
4
5
0 0 0 0 0
0 0 0 0 0
1 0 0 0 0
0 1 1 0 0
1 1 0 0 0
1 1
2
3
4
5
5
6 9
8 8 3
3 5 7 6
2
2
2 3 4
J 25
na diag. a pod nejsou přípustné stavy (hrany nejsou orientované - trojúhelníky)
5
Podmínka 1: každý uzel 2 hrany 2 2 2
každý uzel má právě dvě hrany (vezmu pole (i,i) a sčítám nad ním a vpravo od něj)
Podmínka 2: cykly - je dána tím, že x je binární Tady se zadávají délky cest
2 8 5
5
4
8 1
9
6
3 6
3
5 7
3
KAPITOLA 4.
57
MODELY CELOÍSELNÉHO PROGRAMOVÁNÍ
4.10.3 TSP jako nelineární problém 1.
Varianta s hranami Zadání úlohy : n
Obchodní cestující má nav²tívit
m¥st, kaºdé z nich práv¥ jednou a vrátit se do stejného
m¥sta, ze kterého vy²el. Cena ca cestování má být co nejmen²í. Ceny tras z m¥sta m¥sta
j
jsou dány jako prvky
ci,j
matice
i
do
c.
e²ení : Zavedeme stavovou matici s prvky
xi,j ∈ {0, 1} (nep·jde, p·jde z i
do
j ) a úloha je zadána
následovn¥
n n X X
ci,j xi,j → min
i=1 j=1 n X
xi,j = 1, ∀j
(tj. sloupce)
i=1 m X
xi,j = 1, ∀i,
(tj. °ádky)
j=1
X X
diag (X)
=0
X2 = 0
diag
··· X
kde
n
je po£et m¥st (uzl·) a
X
diag
X n−1 = 0
je £tvercová matice stavových prom¥nných
xi,j .
Poznámka Místo podmínky
P
diag (X)
=0
by také m¥la jít veliká penalizace na diagonále matice
c.
S hodnotou 1000 to ale numericky selhávalo.
2.
Excel: Podmínky zadáme do Excelu (ObchodniCestujiciOK_b.xlsx) Varianta s uzly Zadání úlohy : Jiné moºné °e²ení tohoto problému je uvaºovat místo hran uzly a hrany, které k nim pat°í. Podmínka je, ºe ke kaºdému uzlu pat°í práv¥ dv¥ hrany.
KAPITOLA 4.
58
MODELY CELOÍSELNÉHO PROGRAMOVÁNÍ
e²ení : xk,k matice X. Hrany vstupující do tohoto uzlu xi,k , i = 1, 2, · · · , k − 1 nad tímto uzlem a hrany vystupující z tohoto xk,j , j = k + 1, k + 2, · · · , n - pro v²echny uzly k = 1, 2, · · · , n. Kaºdý uzel má
Uzly vztáhneme k diagonálním prvk·m budou ve sloupci uzlu budou
mít práv¥ dv¥ hrany a tedy podmínky budou
n X
xi,k +
i=1
xi,j ∈ {0, 1}
n X
xk,j = 2, k = 1, 2, · · · , n
j=1
xi,j
pro
Podmínky na sub-trasy jsou stejné - zákaz cykl· o délce men²í neº
n
0
a uvaºujeme jen prvky nad diagonálou
není nutno uvaºovat - hrany
k−k
X,
tedy
i < j.
2 . Podmínku
P
diag (X)
neexistují.
Excel: Podmínky zadáme do Excelu (ObchodniCestujiciOK_b.xlsx) 4.11
Zobecn¥ní TSP
4.11.1 Nejkrat²í cesta grafem [Kniha] Zadání úlohy : V·bec nejkrat²í cesta v²emi uzly bez ohledu na to, kde za£íná a kde kon£í.
e²ení : Vezmeme graf a p°idáme jeden uzel. Z n¥j vedeme cesty tam a zp¥t do v²ech uzl· grafu s nulovou délkou. Na tento roz²í°ený graf aplikujeme TSP a to, co vznikne v p·vodním grafu je nejkrat²í cesta. puvodni graf
0
0
0
0
novy uzel
Excel: Podmínky zadáme do Excelu (TSP_asym6Ham1.xlsx)
=
KAPITOLA 4.
MODELY CELOÍSELNÉHO PROGRAMOVÁNÍ
59
4.11.2 Nejkrat²í cesta grafem z daného uzlu Zadání úlohy : Po£áte£ní uzel cesty je dán. Hledáme nejkrat²í cestu z tohoto uzlu.
e²ení : Vezmeme po£áte£ní uzel, a hranám, které do n¥j vedou dáme nulová ohodnocení. Na tento upravený graf aplikujeme TSP.
0 0 0 0
pocatecni uzel
0 carkovane hrany jsou pridany
Excel: Podmínky zadáme do Excelu (TSP_asym6Ham2.xlsx)
4.11.3 TSP s opakovanými náv²t¥vami m¥st [Kniha] Zadání úlohy : Úloha je dána jako asymetrický TSP, ale p°ipou²tíme více náv²t¥v jednotlivých m¥st. Typická aplika£ní úloha je rozvoz zboºí.
e²ení : Místo matice vzdáleností jednotlivých dvojic uzl· (ohodnoceni hran grafu) zadáme matici nejkrat²ích vzdáleností mezi jednotlivými dvojicemi uzl·. M·ºe být: bu¤ je vzdálenost spojovací hrany nejmen²í, pak ji necháme. Nebo existuje krat²í cesta, pak ji p°epí²eme. Nebo hrana neexistuje, pak ji p°idáme s ohodnocením nejkrat²í vzdálenosti mezi t¥mito uzly.
Poznámka minimální s£ítání matic . Tato operace funguje podobn¥ jako sou£in matic, ale místo násobení prvk· a s£ítání se Matice nejkrat²ích vzdáleností se velice jednodu²e spo£te pomocí operace provádí sou£et prvk· a vezme se minimum, tedy
(A ⊕ B)i,j = min {ai,k + bk,j }∀k
KAPITOLA 4.
60
MODELY CELOÍSELNÉHO PROGRAMOVÁNÍ
Pro výpo£et nejkrat²ích vzdáleností napí²eme matici ohodnocení grafu
D,
kde na diagonále jsou
nuly a mimodiagonální prvky ozna£ují orientovanou vzdálenost mezi uzly. Kde hrana nevede, dáme velké £íslo. A provedeme
D2 = D ⊕ D D3 = D ⊕ D2 ··· Dn−1 = D ⊕ Dn−2 D2 spo£te v²echny nejkrat²í dvou-krokové cesty, D3 t°í-krokové atd. aº n−1-krokové, kde n je po£et uzl· (m¥st). Protoºe nejdel²í cesta grafem má n − 1 hran, obsahuje matice Dn−1 nejkrat²í kde
cesty mezi jednotlivými uzly grafu. Na upravenou matici (nyní minimálních vzdáleností mezi uzly grafu) aplikujeme TSP. Dostaneme navazující dvojice uzl·, které v p·vodním grafu vyzna£íme. Kaºdou hranu ale musíme prozkoumat. Pokud je délka hrany minimální délkou, pak ji na cest¥ ponecháme. Pokud není minimální, musíme hledat, po kterých hranách minimální cesta mezi aktuální dvojicí bod· vede a místo aktuální hrany vyzna£íme tuto minimální cestu. Tím se m·ºe stát, ºe n¥kterým uzlem projdeme vícekrát, ale m·ºeme dostat krat²í cestu neº kdyº trváme na podmínce jediného pr·chodu kaºdým m¥stem.
Excel: Podmínky zadáme do Excelu (TSP_asym5vice.xlsx)
4.11.4 TSP s klastry [Kniha] Zadání úlohy : Uvaºujeme graf jehoº vrcholy jsou pokryty
k klastry tak, ze klastry jsou disjunktní a ºádný vrchol
není nepokryt. Uzly jsou spojeny orientovanými hranami s ohodnocením, reprezentujícím délku hrany. Úkol je projít v²emi uzly tak, ºe po vstupu do uzlu se musí projít v²emi uzly tohoto grafu a cesta je nejkrat²í moºná.
e²ení : Vyjdeme z existujícího grafu a hranám uvnit° klastru p°idáme velké ohodnoceni
M → ∞.
Dále
aplikujeme TSP.
Excel: Podmínky zadáme do Excelu (TSP_asym6klast.xlsx) 4.12
Optimální po°adí úloh (machine sequencing) [Sheduling]
4.12.1 Plánování sm¥n pro obsluhu (Scheduling) 1.
Zam¥stnanci na plný úvazek
KAPITOLA 4.
61
MODELY CELOÍSELNÉHO PROGRAMOVÁNÍ
Zadání úlohy : Plánujeme obsazení 4 sm¥n obsluhy v restauraci s rychlým ob£erstvením. Aby jednotlivé sm¥ny na sebe dob°e navázaly, musí se na za£átku a na konci p°ekrývat. Proto celý den (24 hodin) rozd¥líme na okna po 3 hodinách a sm¥ny sestavujeme podle následující tabulky (X ozna£uje jedno okno) Okno
Sm¥na 1
6-9
X
9-12
X
12-15
X
Sm¥na 2
Sm¥na 3
Sm¥na 4
Poºadavek prac.
X
55 46
X
15-18
X
18-21
X
59 23 X
21-24
X
0-3
X
60 38
3-6 Plat
135
140
190
X
20
X
30
188
Cílem je sestavit sm¥ny tak, aby celková vyplacená odm¥na byla co nejmen²í.
e²ení : Zavedeme
dt
- pot°ební pracovníci pro v okn¥
t; wj
- plat pro sm¥nu
j
(na kaºdé okno je
pot°eba ur£itý po£et pracovník·, sm¥na je obsazena stejnými pracovníky sm¥nu),
yj
- po£et pracovník· ve sm¥n¥
→
platba je za
j , (y1 , y2 , y3 , y4 )
Zápis standardní úlohy je následující:
J=
P
j
P
j
wj yj → min
at,j yj ≥ dt
yj ≥ 0, kde
1
at,j = 1
1
1 1
int
1
1 1
1
1 1 1
y = [y1 , y2 , y3 , y4 ] , t = 1, 2, · · · , 8
Excel: Podmínky zadáme do Excelu (FullTimeWorkers.xlsx) 2.
Brigádníci
[Kniha]
Zadání úlohy : Zase jako p°ed tím, ale najímáme i brigádníky. Ty p°ijímáme na divoko (do jednotlivých £asových oken) platíme mzdou
ct .
Jejich po£et ozna£íme
xt .
KAPITOLA 4.
62
MODELY CELOÍSELNÉHO PROGRAMOVÁNÍ
e²ení : P
j
P
j
M
wj yj +
P
t ct xt
at,j yj + xt ≥ dt 27
P
j
at,j yj − xt ≥ 028
xt , yj ≥ 0,
int
Excel: Podmínky zadáme do Excelu (FullPartTimeWorkers.xlsx)
4.12.2 Obsazování let· posádkami [Nas text] Zadání úlohy : Letecká doprava zaji²´uje spojení mezi vybranými m¥sty. Tyto spoje nazveme etapy letu. Jeden let (s jednou posádkou letadla) letí po ur£itá trase a na ní m·ºe realizovat n¥kolik etap (pokud se mezi n¥ vejde povinný odpo£inek posádky a údrºba letadla). Tak nap°íklad let 10.00 z New Yorku do Chicaga a let 18.00 z Chicaga do Los Angeles je p°íkladem takových etap, které mohou tvo°it jednu trasu s jednou posádkou.
e²ení : Máme
n
etap a
m
posádek.
Nejd°íve sestavíme matici
a, která bude svými sloupci odpovídat jednotlivým etapám. V °ádcích
bude obsahovat v²echny moºné trasy, sestavené z etap, které lze realizovat v jedné trase - etapy budou vyzna£eny jedni£kou ve sloupci p°íslu²né etapy. Cílem je ze v²ech moºných tras vybrat ty, které obsadíme posádkou (budou realizovány) tak, aby 1. ºádná etapa nez·staly neobsazena, 2. náklady na realizaci tras byly minimální. Ozna£íme
xj ∈ {0, 1}, cj
je cena za pronajatí posádky na trase
ai,j ∈ {0, 1}
j
ozna£uje (jedni£kou), ºe etapa
(realizaci trasy
i
j ),
je za°azena do trasy
j
Úloha je formulována takto
Pn
j=1 cj xj
Pn
j=1
→ min29
ai,j xj = 1, i = 1, 2, · · · , m30
27 pro okno t, kde je P a y = 0 musí být x taky 0. Jinak podmínka neplatí. t j t,j j 28 omezení s M °íká, ºe brigádníci se mohou brát jen kdyº je tam uº n¥kdo na plný 29 c je cena za pronajatí posádky na trase j (realizaci trasy j ) j 30 a ∈ {0, 1} ozna£uje (jedni£kou), ºe etapa i je za°azena do trasy j i,j
úvazek
KAPITOLA 4.
63
MODELY CELOÍSELNÉHO PROGRAMOVÁNÍ
xj ∈ {0, 1} , j = 1, 2, · · · , n31 kde kritérium vyjad°uje minimalizaci náklad·, a první podmínka vyjad°uje skute£nost, ºe kaºdá etapa má práv¥ jednu posádku.
Poznámka Jestliºe p°ipustíme, ºe £lenové n¥které posádky mohou ur£itou trasu let¥t jako pasaºé°i (p°eváºí se na místo svého letu na dal²í etap¥), bude mít tato podmínka tvar n X
ai,j xj ≥ 1, ∀i
j=1 1.
P°íklad Uvaºujeme 4 m¥sta:
A, B, C, D
a lety mezi t¥mito m¥sty podle následujícího obrázku
B
1
6
4 2
A
D 5 3
7
C Jednotlivé ²ipky na obrázku zna£í etapy. Jde o to, jak z nich sestavit trasy (obsazené posádkou) tak, aby pronájem posádek by minimální a v²echny etapy byly obslouºeny. Trasy jsou p°edem denovány bu¤ jako samostatné lety nebo jsou sestaveny z navazujících etap a jsou denovány maticí
a=
1 0 0 0 0 0 0
a. 0 1 0 0 0 0 0
Zde vybereme trasy takto
0 0 1 0 0 0 0
0 0 0 1 0 0 0
0 0 0 0 1 0 0
0 0 0 0 0 1 0
0 0 0 0 0 0 1
1 0 0 0 0 1 0
1 0 0 1 0 0 1
1 0 0 0 0 0 1
0 0 1 0 1 1 0
0 0 1 0 0 0 1
Nejd°íve uvaºujeme v²echny etapy jako samostatné lety, potom n¥které trasy sestavené z vhodných etap.
31
indikuje, zda trasa
j
bude realizována (tj. obsazena posádkou)
KAPITOLA 4.
MODELY CELOÍSELNÉHO PROGRAMOVÁNÍ
64
Ceny posádek vezmeme p°ibliºn¥ rovny po£tu etap v p°íslu²né trase a trochu p°ihodíme na samostatné lety, protoºe tam musí posádka dojet z domova. Ceny tedy budou
c = [15, 12, 16, 14, 18, 12, 16, 22, 25, 24, 27, 26] Stavový vektor bude mít 12 prvk·, které budou bu¤ 0 nebo 1. Úloha má tvar
n X
cj xj → min
j=1 n X
aj xj = 1
j=1
xj ∈ {0, 1} e²ení úlohy je
x = [0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0] tedy budou realizovány lety (podle matice
a)
trasa 1
etapa 2
trasa 2
etapa 1,
etapa 4,
etapa 7
trasa 3
etapa 3,
etapa 5,
etapa 6
Tedy, v²echny etapy jsou obsazeny, poletí 3 posádky a doufejme, ºe cena za posádky je minimální. 2.
P°íklad Jiný p°íklad je realizován v programu: planovaniLetu.xlsx
Excel: Podmínky zadáme do Excelu (planovaniLetu.xlsx)
Kapitola 5
Programové vybavení 5.1
Excel
5.1.1 e²itel Pro °e²ení úloh lineárního programování je moºné pouºít aplikaci e²itel, tedy aplikaci, která souºí k vyhledávání extrém· funkce. e²itel je sou£ástí MS Excel Výhoda této aplice je v tom, ºe je p°ehledná a Excel je b¥ºn¥ vyuºívaný a roz²í°ený tabulkový procesor. Nevýhoda je, ºe je omezený prostorem a pro sloºité úlohy se msí pouºít jiný program. V²echny úlohy byly naprogramovány ve verzi MS Excel 2013 a i na tuto verzi optimalizovány. Z toho d·vodu neru£íme za nefunk£nost ve star²ích verzích. Tato verze je zdarma ke staºení na
http://download.cvut.cz/. e²itele naleznete po spu²tení v záloºce DATA, viz obrázek 5.1.1.
Obrázek 5.1.1: Excel - Data - e²itel Pokud tam není, je nutné ho aktivovat. Lze aktivovat následujícím zp·sobem: 1. otev°ete Soubor - Moºnosti - Dopl¬ky a otev°e se vám nové okno, viz obrázek (a), 2. v otev°eném okn¥ dole klikneme na Spravovat: Dopl¬ky aplikace Excel a otev°e se dal²í okno, viz obrázek (b). Za²krtneme e²itel a potvrdíme pomocí tla£ítka OK. Pokud v²e prob¥hlo v po°ádku, v záloºce DATA se objeví e²itel (v anglické verzi Solver).
5.1.2 Model v se²it¥ Excel 1. Nejd°íve vymezíme blok bun¥k pro neznámé 65
x
(p°ípadn¥ dal²í neznámé)
KAPITOLA 5.
66
PROGRAMOVÉ VYBAVENÍ
(a)
(b)
Obrázek 5.1.2: Aktivace e²itele
2. Dále zapí²eme v²echny zadané veli£iny - v¥t²inou to jsou ceny omezení
A
a poºadované pravé strany
c
a koecienty lineárních
b.
3. Spo£teme v²echno, co je pot°eba spo£ítat (do e²itele se dávají jen odkazy na bu¬ky nebo bloky bun¥k). V¥t²inou to je: (a) kriterium
c0 x =
P
i ci xi
(b) vypo£tené pravé strany omezení
Ax =
P
aij xj ∀i
4. Zavoláme e²itele a zadáme v²echny odkazy (a) zvolíme Min nebo Max pro kriterium (b) zadáme blok nebo bloky pro neznáme (optimalizované) veli£iny (c) p°idáme omezení ve tvaru
≤, ≥
nebo bin (volí se na stejném míst¥)
(d) v¥t²inou necháme zatrºenou volbu neomezené veli£iny jsou nezáporné (nemusí se to jiº deklarovat v podmínkách) (e) a v okénku dole vybereme volbu Simplex LP - lineární programování.
5.1.3 Triky p°i práci v Excelu Blok bun¥k - taºení my²í nebo Shift+²ipka P°emíst¥ní bloku (s Ctrl kopie) -uchopení za okraj (bu¬ky nebo bloku) a taºení. Vkopírování hodnoty do celého bloku - vytvo°íme blok, zadáme hodnotu a Ctrl+Enter. Maticové vzorce - provád¥jí operace (nej£ast¥ji násobení) prvek po prvku. Zadávají se pomocí
Ctrl+Shift+Enter. Výsledek m·ºe být v jedné bu¬ce, nebo v bloku bun¥k. Blok je moºno zadat
p°edem (pak se objeví výsledky v celém bloku). Vzorec je moºno kopírovat se v²emi pravidly o posunu adres.
Fixace adres (absolutní adresy) - zaxované adresy se p°i kopírování neposouvají. Adresu xuje dolar p°ed písmenem, £íslem nebo obojím. Dolar p°ed písmenem xuje adresu p°i vodorovném pohybu, p°ed £íslem p°i svislém pohybu a p°ed obojím i ve vodorovném i svislém sm¥ru.
KAPITOLA 5.
Zadání dolar·
67
PROGRAMOVÉ VYBAVENÍ
- automaticky zadáme dolary klávesou F4 ihned po vloºení adresy (jinak se
musí adresa dát do bloku). Opakované stisknutí F4 provede: oba dolary, jen p°ed £íslem, jen p°ed písmenem, ºádný dolar (atd.)
Skalární sou£in - pokud pot°ebujeme maticový výpo£et =
P
i
tak, ºe vytvo°íme sumu sou£inu dvou sloupc· a poté zmá£kneme
=suma(A1:A10*B1:B10) + Ctrl+Shift+Enter
ai bi lze ho jednodu²e vytvo°it Ctrl+Shift+Enter. Nap°íklad
Sou£in matice a vektoru - matice je B1:D10 a vektor A1:A10. Sou£in je =suma(B1:D1*$A$1:$A$10) + Ctrl+Shift+Enter
a rozkopírovat svisle. (Druhá adresa je absolutní - viz xace adres.)
5.1.4 P°íklad v excelu e²íme obecný p°íklad lineárního programování, viz 2.1. Pro p°ehlednost, je hned na za£átku uvedeno °e²ení, které je ozna£eno modrým pozadím (obrázek 5.1.3). Dále jsou uvedeny váhy v kritériu (pro variantu (a) v obecném p°íkladu), tedy váhy
c = [5, 1].
Následují podmínky
3x1 + 5x2
≤ 15
2x1 + x2
≤ 8
x2
≤ 2
které jsou také ve £tvere£ku s oranºovým pozadím, stejn¥ jako váhy v kritériu. Kritérium, které je ozna£eno zeleným pozadím v ráme£ku, je základní parametr, kde se hledá maximum nebo minimim. Ani tento parametr nem¥níme. P°i práci se obvykle m¥ní pouze polí£ka s oranºovým pozadím, tedy zadání.
Obrázek 5.1.3: P°íklad v excelu
KAPITOLA 5.
68
PROGRAMOVÉ VYBAVENÍ
V p°ípad¥, ºe jiº máme nastavené základní hodnoty, p°echázíme k e²iteli (Solver). Spustíme DATA-e²itel (Solver) a objeví se nám tabulka znázorn¥na na obrázku 5.1.4 (a). Pro správnou funkci je pot°eba nastavit následující: 1. 2.
Ú£elová funkce - odkaz na bu¬ku s kritériem (zelené pozadí). Hledat - hledá se minimum, maximum nebo ur£itá hodnota. Pro zadávajícího je d·leºité si uv¥domit co hledá (u zisku nebude hledat minimum a u náklad· maximim).
3.
Prom¥nné modelu - výsledek (modré pozadí). Zde bude optimální hodnota pro zadané veli£iny (nap°íklad kolik kus· výrobku A a B vyrobit).
4.
Omezující podmínky
- zde musí být v²echny podmínky, které je potreba splnit, tzn.
vytvo°í se sloupcový vektor, do kterého se vypo£ítá sou£in výsledku (nap°íklad kolik kus· vyrobit) s hodnotou °ádku tak, aby se dal výsledek porovnat s omezením. Tedy
ax
porovnáme s pravou strannou omezení. Pokud bude je²t¥ jiný poºadavek, nap°íklad minimální vyrobené mnoºství, musí se zapsat také do Omezujících podmínek, kde se klikne na ikonku P°idat a nadenuje se nová podmínka. 5.
Nastavit podmínky nezápornosti - u v¥t²iny problém· se o£ekává, ºe výsledek nem·ºe být záporný (nem·ºeme vyrobit -5 výrobk·). Tato podmínka se m·ºe zadat p°ímo do omezujících podmínek nebo se za²krtne polí£ko s podmínkou nezápornosti.
6.
Vyberte metou °e²ení - na výb¥r je Gradientní metoda, Simplexová metoda a Evolu£ní algoritmust. Zvolení vhodné metody je na zadavateli a ur£í se podle typu úlohy. (a) Simplexová metoda - lineární optimaliza£ní úlohy, (b) Gradientní metoda - hladké nelineární optimaliza£ní úlohy, (c) Evolu£ní algoritmus - nehladké nelineární optimaliza£ní úlohy.
(a)
(b) Obrázek 5.1.4: e²itel
Poté se jiº jen zadá funkce °e²it a objeví se následující tabulka 5.1.4 (b). Tam necháme za²krtnutou moºnost
Uchovat °e²ení e²itele a potvrdit tla£ítkem OK.
KAPITOLA 5.
5.2
PROGRAMOVÉ VYBAVENÍ
LIPS????
69
Literatura [Kniha]
Chen, Batson, Dang: Applied Integer Programming
[Nas text]
U£ební text - LecText_IntPrg.lyx
[Formulating] Formulating Linear Programming Models [Hlavni text]
Hlavní text - Integer programming
[Lockbox]
Lockbox, set coverinc, salesman
[Knapsack]
The knapsack problem
[3 p°íklady]
Infek£ní onemocn¥ní a dal²í
[Sheduling]
Scheduling, sequencing
70