Lineární a Celo£íselné Programování text k p°edná²kám
Obsah
1 Lineární a celo£íselné programování
4
1.1
Obecná formulace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
1.2
Algebraický model
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
1.3
P°íklad
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
2 e²ení úlohy lineárního programování
7
2.1
Simplexová metoda . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2
Model v se²it¥ EXCEL
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10
2.3
Triky p°i práci v EXCELu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11
3 Úlohy I.
7
11
3.1
Optimální produkce
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2
Optimální produkce s omezenými zdroji
. . . . . . . . . . . . . . . . . . . . . . .
12
3.3
Optimální produkce s výb¥rem surovin . . . . . . . . . . . . . . . . . . . . . . . .
14
3.4
Optimální krmná sm¥s . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
15
3.5
Optimální °ezání ty£í . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
16
4 Úlohy II. 4.1
11
17
Minimální tok náklad· v síti
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
17
P°íklad 1
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
18
P°íklad 2
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
20
4.2
P°i°azovací dopravní problém . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
21
4.3
P°i°azovací dopravní problém (pomocí MCNF)
. . . . . . . . . . . . . . . . . . .
22
4.4
Nejkrat²í cesta grafem (pomocí MCNF)
. . . . . . . . . . . . . . . . . . . . . . .
23
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
23
P°íklad
1
5 Celo£íselné programování
27
6 Formulace úloh celo£íselného programování
30
6.1
6.2
Speciální typy omezení . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
30
Omezení na výb¥r
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
30
Aktivace omezení . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
30
Výb¥r z mnoºiny omezení
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
31
Implikované omezení . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
32
Omezení na oblasti . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
35
Aproximace kriteriální funkce . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
36
Aproximace skokové funkce
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
36
Aproximace po £ástech lineární funkce . . . . . . . . . . . . . . . . . . . . . . . .
37
Aproximace sou£inu v kriteriu . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
39
Realizace minimaxu v kriteriu . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
41
7 e²ení úlohy celo£íselného programování 7.1
Metoda v¥tví a mezí
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.2
Metoda se£ných nadrovin
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8 Úlohy III.
42 42 45
49
8.1
Úloha o batohu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
49
8.2
Výb¥r z mnoºiny investic
50
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9 Úlohy IV. 9.1
51
Problém obchodního cestujícího (TSP) . . . . . . . . . . . . . . . . . . . . . . . .
10 Úlohy V.
51
55
10.1 Problém pokrytí oblastí
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
56
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
58
10.3 Obsazování leteckých tras posádkami . . . . . . . . . . . . . . . . . . . . . . . . .
59
10.2 Kuch°ka a recepty
P°íklad 1
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
60
P°íklad 2
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
62
11 Úlohy VI.
62
11.1 Problém rozmíst¥ní sklad· . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
63
11.2 Vy²et°ení infek£ního onemocn¥ní
67
. . . . . . . . . . . . . . . . . . . . . . . . . . .
2
12 Úlohy VII. 12.1 Problém po²tovních box·
71 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
13 Zobecn¥ní TSP
71
72
13.1 Nejkrat²í cesta grafem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
72
13.2 Nejkrat²í cesta z daného uzlu
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
74
13.3 Nejkrat²í cesta s více náv²t¥vami m¥st . . . . . . . . . . . . . . . . . . . . . . . .
75
13.4 Nejkrat²í cesta klastry uzl·
76
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
1
Lineární a celo£íselné programování
1.1
Obecná formulace
Standardní úloha zní: 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 → max
Ax ≤ b x≥0
Poznámka Omezení vytvá°í simplex na kterém se hledá optimum. Lineární kriterium tvo°í nadrovinu v prostoru
1.2
x, J.
Extrém je ve vrcholu nebo na hranici nebo ute£e do nekone£na.
Algebraický model
1. De nice neznámých (rozhodovacích) veli£in V prvé °ad¥ musíme de novat veli£iny spojité
x≥0
x,
x které budeme optimalizovat. Ty mohou být
nap°. po£et ks vyráb¥ného produktu, nebo diskrétní
za°ízení s rychlým ob£erstvením nebo binární
x ∈ {0, 1} ,
x ≥ 0, cele
nap°. po£et
které nazýváme rozhodovací (0
ne, 1 ano) nap°. ozna£ení investic z ur£ité mnoºiny, které budou realizovány. 2. De nice kritéria Kritérium v¥t²inou vyjad°uje n¥co, co chceme maximalizovat (zisk) nebo minimalizovat (náklady, ztráty atd.). Je vyjád°en jako funkce optimalizovaných veli£in form¥
c0 x
P
jako sou£in vektor· nebo matic (
j,j cij xij ).
Prom¥nné
c
x,
v¥t²inou ve
se £asto nazývají
ceny. 3. De nice omezujících podmínek Vyjad°ují podmínky, za kterých má optimalizace probíhat. Nejb¥ºn¥j²í jsou (a) nezápornost nebo celo£íselnost neznámých (b) omezení ve tvaru nerovností
Ax ≤ b,
x ≥ 0, x ∈ {0, 1}
kde matice
A
má rozm¥ry po£et omezení
po£et neznámých (c) a p°ípadn¥ dal²í, se kterými se postupn¥ setkáme v p°íkladech.
4
×
1.3
P°íklad
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 Váhy v kriteriu volte následovn¥ a)
c = [5, 1],
b)
c = [1, 1] ,
c)
c = [1, 3] ,
d)
c = [−1, 1].
a vysv¥tlete výsledky.
e²ení Geometrická interpretace úlohy ne na následujícím obrázku
x2 criterion 3
criterion 3
[0, 8]
direction of maximization
criterion 2
criterion 1
[0, 3] [5/3, 2] [0, 2] [6/7, 25/7] admissible solutions
[4, 0]
[5, 0]
x1
K °e²ení lze pouºít nap°. Excel.
5
e²itel lze nalézt v menu Data (pokud tam není, je t°eba ho nainstalovat File - Options - Add-ins dole Go a snad tam vleze :-) ) Nastavíme ho takto
6
Pozn. V nové verzi lze za²krtnout - prom¥nné
2
2.1
x
jsou nezáporné.
e²ení úlohy lineárního programování
Simplexová metoda
Pro °e²ení základní úlohy lze vyuºít
simplexovou metodu,
která prochází vrcholy simplexu
omezení tak, aby stále nar·stala hodnota kriteria. Postup je obsaºen v následujícím p°íkladu
Demonstrace simplexové metody
Příklad
x 3
2
2
3
c
Zadání z=2x(1)+3x(2) -> max x(1)+x(2)<=5 x(1)+2x(2)<=8
z 12
(-x(1)+x(2)<=-4) A
Ax 1 1 2
Tabulka x1 -2 1 1
b
1 2 -1
5 7 4
5 8 4
nové další omezení pro demonstraci nerovnosti <= v omezení (viz další strana) (zatím bez nového omezení)
x2 -3 1 2 |
s1 0 1 0
s2 0 0 1
RHS 0 5 8
x1 -0.5 0.5 0.5 |
x2 0 0 1
s1 0 1 0
s2 1.5 -0.5 0.5
RHS 12 1 4
x1 0 1 0
x2 0 0 1
s1 1 2 -1
s2 1 -1 1
RHS 13 2 3
pokračuje dále ...
7
---
5/1 8/2
pro nebazické=0 je krit.=0 první omezení druhé omezení
---
výsledek krit.=13 x1=2 x2=3
nebazické jsou 0 bazické mají hodnotu z pravého sloupce (krit. je bazické)
... pokračování
nejsou splněny základní podmínky ulohy ( záp. pravá strana omezení nebo obrácená nerovnost >= )
Když nejsou pravé stany kladné, tak se to nasobí -1 Když není <=, postupujeme následovně odečteme s_slack a přičteme x_art (artificial) - obě veličiny jsou nezáporné řešíme pro koeficienty v kriteriu rovny nule a jedna pro x_art - tj pro krit. = x_art --> max nulujeme koeficient pro x_art v kriteriu - řádek podmínky násobíme -1 a přičteme ke kriteriu normálně vyřešíme a dostaneme tabulku z fáze I. u tabulky vynecháme sloupec pro x_art řádek 0 pro kriterium nahradíme původním řádkem Původní tabulka + nové omez. x1 x2 s1 -2 -3 0 1 1 1 1 2 0 2 -1 0
s2 0 0 1 0
s3 0 0 0 -1
xA 1 0 0 1
RHS 0 5 8 4
Řešíme pro c=0 tj. min z=xA x1 x2 s1 0 0 0 1 1 1 1 2 0 2 -1 0
s2 0 0 1 0
s3 0 0 0 -1
xA 1 0 0 1
RHS 0 5 8 4
s2 0 0 1 0
s3 1 0 0 -1
xA 0 0 0 1
RHS 0 5 8 4
báze: posl. ř. odečíst od prvního x1 x2 s1 -2 1 0 1 1 1 1 2 0 2 -1 0 | pokračuje ...
8
Nové omezení (pro demonstraci postupu s nerovností >=) -2x1+x2<=-4
---
5/1 8/1 4/2
... pokračování u x1 je záporná cena -- posledním ř. a prvním prvkem nulujeme první sl. x1 x2 s1 s2 s3 xA 0 0 0 0 0 1 0 1.5 1 0 0.5 -0.5 0 2.5 0 1 0.5 -0.5 1 -0.5 0 0 -0.5 0.5 xx xx xx x1=2
x2=0
s1=3
s2=6
s3=0
xA=0
x2 -3 1.5 2.5 -0.5 |
s1 0 1 0 0
s2 0 0 1 0
s3 0 0.5 0.5 -0.5
RHS 0 3 6 2
x1 -2 0 0 1 |
x2 0 1 0 0
s1 2 0.667 -1.667 0.333
s2 0 0 1 0
s3 1 0.333 -0.333 -0.333
RHS 6 2 1 3
0 0 0 1
0 1 0 0
2 2/3 2/3 -1 2/3 1/3
0 0 1 0
1/3 1/3 - 1/3 - 1/3
12 2 1 3
Fáze II x1 -2 0 0 1
x1=3
RHS 4 3 6 2
záporná pravá strana nebo omezení >=
x2=2
s1=0
s2=1
s3=0
---
2 2.4
---
Konec
z=12
Tedy:
•
standardní podmínky jsou:
•
maximalizace kriteria, nezáporné pravé strany omezení, nerovnosti typu
≤,
nezáporné prom¥nné
x.
sestavíme simplexovou tabulku
• standardní °e²ení
najdeme nejmen²í záporný koe cient v °ádku kriteria
9
→
klí£ový sloupec
2 2.4
pro kladné prvky v klí£ovém sloupci najdeme nejmen²í podíl levé strany a prvku v klí£ovém sloupci
klí£ový °ádek
na pr·se£íku kl. sl. a kl. °. leºí klí£ový prvek
∗ ∗
→
ten vyd¥líme kl. prvkem tím vynulujeme ostatní prvky v kl. sloupci
to d¥láme, dokud je v °ádku kriteria n¥jaký záporný prvek Výsledek: bázové veli£iny mají hodnoty odpovídající pravým stranám; nebázové veli£iny jsou nula.
• nestandardní °e²ení
≥→
záporné
b
záporné
b a podmínka ≤ (násobíme -1) nebo kladné b a podmínka ≥ → dále uvedený
a podmínka
násobíme -1
postup
•
postup
ode£teme slack variable
s
a p°i£teme arti cial variable
°e²íme celý problém pro kriterium
z = xA → max
xA .
a do°e²íme aº do konce
ve výsledné tabulce nahradíme °ádek kriteria p·vodním a vynecháme sloupec s arti cial variable
2.2
vy°e²íme a to je °e²ení p·vodní nestandardní úlohy.
Model v se²it¥ EXCEL
1. Nejd°íve vymezíme blok bun¥k pro neznámé
x
(p°ípadn¥ dal²í neznámé)
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 koe cienty 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 x i
(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í.
10
2.3
Triky p°i práci v EXCELu
Blok bun¥k - taºení my²í nebo Shift ²ipla 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) - za xované 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.
Zadání dolar·
- 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: =suma(A1:A10*B1:B10) + Ctrl Shift Enter ud¥lá maticový výpo£et =
P
i
a i bi
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í.)
3
Úlohy I.
3.1
Optimální produkce
Máme rozhodnout o mnoºství, ve kterém budou vyráb¥ny produkty A a B. K jejich výrob¥ jsou zapot°ebí dva drahé stroje jejichº vyuºití je omezeno. Úloha je zadána v tabulce
Stroj
as stroj· pot°ebný
as stroj·
na 1000 výrobk·
k vyuºití
Produkt A
Produkt B
1
4
6
24
2
4
2
12
Cílem je navrhnout maximální produkci.
e²ení
x1
a
x2
- produkce výrobk· A a B v tisících.
Formulace úlohy je následující
x1 + x2 → max
4x1 + 6x2
≤ 24
4x1 + 2x2
≤ 12
11
x1 ≥ 0, x2 ≥ 0 Pokra£ování p°íkladu Uvaºujme nyní ceny
c1 = 10
pro A a
c2 = 20
pro B. Chceme docílit maximálního zisku.
e²ení Nové kriterium bude
10x1 + 20x2 → max Dal²í pokra£ování Firma podepsala dohodu s dodavatelem, ºe minimální produkce výrobk· bude 1 tis. Náklady na výrobu jednotlivých výrobk· jsou
n1 = 5
a
n2 = 10.
Cílem je minimalizovat výdaje.
e²ení Nové kritérium a dal²í omezení jsou
5x1 + 10x2 → min
x1 ≥ 1, x2 ≥ 1
3.2
Optimální produkce s omezenými zdroji
Továrna s dv¥ma provozy produkuje výrobek A, který se prodává samostatn¥ a nebo jako sou£ást pro výrobek B. Oba výrobky pot°ebují ur£itou surovinu (S), jejíº zdroj je omezen. Speci kace úlohy je dána v tabulce
Surovina +
Spot°eba
K dispozici
+ A pro B
na jednotku produkce
celkem
Produkt A
Produkt B
S
5
2
3000
A
0
1
Cena produktu
5
10
× ×
Dále stanovíme podmínku, ºe minimální po£et samostatných výrobk· musí být 250 ks. Poºadujeme a) maximální produkci, b) maximální zisk.
e²ení
x1
je po£et kus· A a
x2
pro B.
Kriterium pro maximální produkci
x1 + x2 → max, 12
a pro maximální zisk
5x1 + 10x2 → max . Podmínky
5x1 + 2x2 ≤ 3000 x1 − x2 ≥ 250 x1 ≥ 0, x2 ≥ 0 Program: produkce2Vyrobky.xlsx
13
3.3
Optimální produkce s výb¥rem surovin
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. Speci kace je v tabulce
Surovina
Výrobek
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
Chceme minimalizovat výdaje.
e²ení
x1 · · · x4
jsou navrhovaná mnoºství zakoupených surovin. Platí
20x1 + 10x2 + 5x3 + 10x4 → min
2x1 + 10x2 + 5x3 + 20x4
≥ 1000
10x1 + 5x2 + x3
≥ 2000
Program: produkceSeSurovinou.xlsx
14
3.4
Optimální krmná sm¥s
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. Cena jednoho kg píce je 0.50 K£ a kuku°ice 0.40 K£. Dal²í speci kace jsou v tabulce 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
Poºadujeme minimální výdaje.
15
e²ení
x1
zna£í mnoºství píce,
x2
mnoºství kuku°ice. Platí
0.5x1 + 0.4x2 → min
x1 + 1.25x2 0.4x1 + 0.08x2
≥ 2.5 ≥ 0.24
nebo = v omezení (nechceme zbytky). Program: KrmnaSmes.xlsx
3.5
Optimální °ezání ty£í
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
16
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. Program: RezaniTyci.xlsx
4
4.1
Úlohy II.
Minimální tok náklad· v síti
Minimum Cost Network Flow Problem (MCNF)
17
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
xkj −
j
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.
P°íklad 1 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
3
3
6
6
18
7
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)
5
21 14 9
18 7
32 12
31 , 29 35
0 hrana
(7, 1)
je zp¥tná s cenou 0.
Jednotlivé toky budou
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
,
kde nepouºitým hranám jsme p°i°adili 0. Stejn¥ tak doplníme 0 do matice ohodnocení. Minimální kapacitu hran zadáme jako 0, maximální 80. Potom úloha má tvar: 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
Pozor
xij ≥ L, xij ≤ U,
p°ípadn¥
k -tém
°ádku minus
xij ≥ 0, xij ≤ U.
Bude-li zadána p°íli² malá maximální kapacita hran, bude problém ne°e²itelný.
Program: minCostFlow1.xlsx
19
P°íklad 2 Je dáno 9 uzl· podle obrázku
zdroj
cíl zdroj
zdroj
umely uzel
cíl zdroj zpetna hrana
se £ty°mi zdroji a dv¥ma poºadavky. Silnými ²ipkami je vyzna£en výsledek. Detaily zadání jsou v programu.
20
Poznámka Graf sám nemá jeden výstupní uzel. Aby se mohla zavést zp¥tná hrana, je t°eba de novat pomocný uzel s
b = 0
do n¥hoº vedou pomocné hrany s nulovým ohodnocením. Ten se pak propojí se
vstupem 1 (protoºe ten vede dále do ostatních vstup·). Program: minCostFlow2.xlsx
4.2
P°i°azovací dopravní problém m zdrojových uzl·, kaºdý s si , i ∈ {1 · · · m} = M jednotkami zboºí, a n cílových uzl·, dj , j ∈ {1 · · · n} = N jednotkami poºadavk·. cij , i ∈ M, j ∈ N je jednotková cena za zboºí po hran¥ i, j a xij je mnoºství zboºí p°epravené po této hran¥. Chceme dosáhnout
Je dáno kaºdý s p°evoz
minima náklad· za p°evoz. Úloha
X
cij xij → min
ij
X
xij = si , ∀i
j
X
xij = dj , ∀j
i
xij ≥ 0, ∀ij 21
Lze °e²it p°ímo pomocí LP. Program: assignmenProbl.xlsx
4.3
P°i°azovací dopravní problém (pomocí MCNF)
Jedná se jiné °e²ení úlohy dopravního problému.
si
jsou zdroje,
di
poºadavky.
e²ení Lze °e²it jako MCNF vhodnou úpravou grafu:
1. P°i°adíme
bi = si , 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
Tyto hrany mají nulová ohodnocení.
22
m+1
aº
m+n
spojíme s uzlem
m + n + 1.
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 modi kovaný graf aplikujeme MCNF. Modi kovaný graf je na obrázku.
b>0
b<0
1
m+1
0
m+n+1
P
P
i bi
j bj
m+n
m
Program: assignmenProblAsMCNF.xlsx (velké - prohlédnout v Excelu)
4.4
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
(i, j) .
m.
e²ení Pomocí MCNF, kde uvaºujeme o p°eprav¥ jednotky toku z uzlu 1 do uzlu
1, ∀ij
a
bi = 0, ∀i.
P°íklad Uvaºujeme graf z obrázku
23
m.
Poloºíme
Uij =
2
5 8
1
3 10
6 9
4
7
Hledáme nejkrat²í cestu z uzlu 1 do uzlu 7 (nebo z uzlu s k tomu metodu MCNF. Údaje a °e²ení jsou v programu. Program: assignmenProblMinPath.xlsx
24
bi = 1 do uzlu s bj = −1) a vyuºíváme
25
26
5
Celo£íselné programování
Úloha IP je vlastn¥ úloha LP, roz²í°ená o celo£íselné prom¥nné. Tedy
c0 x → min
Ax ≥ 0 xR ≥ 0 xI ∈ I, xB ∈ {0, 1} kde
xR
xI
je mnoºina reálných prom¥nných,
jsou celo£íselné prom¥nné a
xB
jsou celo£íselné
prom¥nné pouze s dv¥ma hodnotami 0 a 1.
P°íklad Chceme investovat $14000. Na²li jsme £ty°i investi£ní p°íleºitosti. Akce 1 vyºaduje investici ve vý²i $5000 a má o£ekávaný výnos $8000; Akce 2 vyºaduje $7000 a má hodnotu $11000; Akce 3 vyºaduje $4000 má hodnotu $6000; Akce 4 poºaduje $3000 má hodnotu $4000. Do kterých akcí bychom m¥li vloºit své peníze tak, aby se dosáhlo maximálního zisku?
e²ení De nujeme vektor prom¥nných znam rozhodnutí:
xi = 1
x = [x1 , x2 , x3 , x4 ] , xi ∈ {0, 1}. Jednotlivé prom¥nné mají i realizovat; xi = 0 nerealizovat. Úloha má tvar
znamená akci
8x1 + 11x2 + 6x3 + 4x4 → max
5x1 + 7x2 + 4x3 + 3x4 ≤ 14 x
binární
e²ení je
x1 = 0, x2 = x3 = x4 = 1
s kriteriem 21.
Úloha v Excelu je následující
27
vý-
Poznámka P°itom je ale z°ejmé, ºe nejvýnosn¥j²í akce je akce 1. Pom¥ry výnos / investice je
1.6, 1.57, 1.5, 1.33
M¥li bychom tedy sázet p°edev²ím na akci 1. Kdyº zru²íme podmínku na binární veli£iny, do-
x1 = 2.8 a ostatní nula s kriteriem x1 = 2, x3 = 1, ostatní nula s kriteriem 22.
staneme jako °e²ení neomezené) je
22.4. e²ení pro
x
celo£íselné (ale
Z uvedeného je patrné, ºe za °e²ení IP není vhodné vzít zaokrouhlené °e²ení LP. e²ení 2, 0, 0, 0 dá kriterium 16. Tento fakt, který je velmi významný, budeme demonstrovat na 2D p°ípadu, který lze pozorovat gra cky. Uvaºujme úlohu
x1 + 9x2 → max
kterou °e²íme pro spojité
x,
x1 + 10x2
≤ 30
3x1 + 5x2
≤ 25
zaokrouhlené
x
a celo£íselné
28
x.
Výsledky jsou
Spojité:
x = [4, 2.6]
Zaokrouhlené: Celo£íselné:
s kriteriem 27.4
x = [4, 2]
x = [0, 3]
s kriteriem 22
s kriteriem 27
Odtud je z°ejmé, ºe IP °e²ení je daleko blíºe LP °e²ení neº zaokrouhlené. Situace je na obrázku
kde plné £áry jsou hranice omezení, £árkované £áry ukazují vrstevnice kriteria které nar·stá sm¥rem nahoru. Programy: IP_rounding.xlsx a IP_rounding.sce.
Poznámka Krom¥ uvedeného je moºno uvaºovat je²t¥ dal²í podmínky: 1. Lze ud¥lat nejvý²e 2 investice
X
xi ≤ 2
2. Jestliºe chceme realizovat akci 2, musíme rovn¥º realizovat akci 4
x2 − x4 ≤ 0
3. Jestliºe budeme realizovat akci 1, potom akci realizovat 3 nelze
x1 + x3 ≤ 1
Takovými omezeními se budeme zabývat dále.
29
6
Formulace úloh celo£íselného programování
6.1
Speciální typy omezení
Pomocí celo£íselných, zejména binárních, veli£in je moºno modelovat daleko ²ir²í okruh omezení neº v klasickém LP.
Omezení na výb¥r Pro binární
x
modelujeme: bude spln¥no alespo¬
X kde
P
X
xi ≥ k,
k,
k , nejvý²e k X xi ≤ k
práv¥
xi = k,
0
xi = [1, 1, · · · , 1] [x1 , x2 , · · · , xn ] .
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
a0 x − By ≤ b. Tato podmínka °íká
30
ºe maximální hodnota
•
je-li
y = 1,
pak p·vodní podmínka je vºdy spln¥na (podmínka je vy°azena)
•
je-li
y = 0,
pak p·vodní podmínka z·stává v platnosti.
Hodnota binární prom¥nné
y
tedy aktivuje nebo deaktivuje p·vodní podmínku
a0 x ≤ b.
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
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 nebo zavedeme
y1 = y y 2 = 1 − y
≤ b1 ≤ b2 ≥ 1
a 0
a1 x − B1 y
≤
b1
a2 x − B2 (1 − y) ≤
b2
0
31
B1
a
B2 .
Poznámka Podmínka
y2 = 1
y1 + y2 ≥ 1 °íká, ºe p°ipou²tíme následující moºnosti: y1 = 1 a y2 = 0 nebo y1 = 0 a y1 = 1 a y2 = 1. Tedy alespo¬ jedna podmínka je vºdy spln¥na. Stejn¥ lze modelovat
nebo
práv¥ 1 nebo nejvý²e jedno. Jednodu²e lze roz²í°it na
k
podmínek.
Implikované omezení Máme dv¥ omezení
0
a1 x > b1
a
0
a2 x ≤ b2 .
Chceme aby platilo: kdyº platí první omezení, pak
platí i druhé (kdyº první neplatí, tak nic). Jde o implikaci. Pro tu platí
Odtud vidíme, ºe
(a ⇒ b)
a
b
a⇒b
a0
a0 ∨ b
0
0
1
1
1
0
1
1
1
1
1
0
0
0
0
1
1
1
0
1
je stejné jako
(a0 ∨ b),
stavec.
32
p°i£emº alternativu umíme - viz p°edchozí od-
Poznámka a ⇒ b je v²echno pravda, jen 1 ⇒ 0 je ²patné a nesmíme to p°ipustit. Jestliºe a0 ∨ b a chceme se vyhnout kombinaci 1, 0, tedy a0 = 1 a b = 0 nesmí nastat b = 0. Viz záv¥ry dále.
V implikaci
modelujeme jako
a=0 (i)
a
Opa£ná
z1 = 1 (ii)
0
a1 x − b1 ≤ M z1 a pro z = 0 se podmínka vyºaduje (pro z = 1 je vy°azena). 0 0 (negace) 0 podmínka, tedy a1 x ≤ b1 bude a1 x − b ≥ −M z1 a op¥t, pro z1 = 0 platí, pro
Modelujeme:
je vy°azena.
Alternativa dvou podmínek
0
a1 x > b1
a
0
a2 x ≤ b2
se modeluje
0
a1 x − b1 ≤ M z1 0
a2 x − b2 ≤ M z2 z1 + z2 ≤ 1 (iii)
Implikace ale je
a0 ∨ b
- první podmínka se bere opa£ná. Bude tedy 0
a1 x − b1 ≥ −M z1 0
a2 x − b2 ≤ M z2 z1 + z2 ≤ 1 Program
33
Nebo je²t¥ jednou
1
nebo (jednodu²eji) Implikaci
0 ≤ x ≤ 10 ⇒ 0 ≤ y ≤ 10
°e²íme takto
x ≤ 4 + 6z y ≤ 10 − 4z z ∈ {0, 1} Je-li Pro
x > 4 pak pak z první podmínky plyne, ºe z = 1 x ≤ 4 m·ºe být z 0 nebo 1 a tedy druhá podmínka
a tedy podmínka
y≤6
je aktivována.
m·ºe a nemusí nastat.
Program
1 Implikovaná podmínka (je²t¥ jednou)
(i) náhrada implikace A ⇒ B je totéº jako A0 ∨ B
(ii) Pro
A
A0
B
A⇒B
A0 ∨ B
0 0 1 1
1 1 0 0
0 1 0 1
1 1 0 1
1 1 0 1
model alternativy
A : x ≥ l1 a B : x ≤ l2 bude x ≥ l1 − M z1 x ≤ l2 + M z2 z1 + z2 ≤ 1
protoºe: z = 0,0 - první platí a druhá platí; 0,1 nebo 1,0 jedna platí druhá neplatí; a vyhýbáme se moºnosti z =1,1 - neplatí ani jedna. Pozn.: V obou p°ípadech platí, ºe z = 0 aktivuje podmínku a tedy z = 1 ji deaktivuje - d¥lá neplatnou.
(iii) Jako
model implikace
(ii), ale první podmínku bereme negovanou, tedy (x ≤ l1 ) ∨ (x ≤ l2 )
odtud bude
x ≤ l1 + M z1 x ≤ l2 + M z2 z1 + z2 ≤ 1 coº je snad kone£n¥ v souladu s programem. Program: Podm43_impl_omez_V.xlsx
34
Poznámka 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í.
Omezení na oblasti Nech´ omezení tvo°í
k
r·zných oblastí (disjunktních nebo i p°ekrývajících se). Jednotlivé oblasti
jsou popsány pomocí lineárních omezení první oblast
0
0
0
a1 x ≤ b1 , a2 x ≤ b2 , a3 x ≤ b3
druhá oblast
0
0
a4 x ≤ b4 , a5 x ≤ b5 ···
Chceme zaru£it, ºe optimální bod °e²ení bude leºet alespo¬ v jedné z oblastí. Modelujeme takto první oblast 0
a1 x − B1 y1 ≤ b1 , 0
a2 x − B2 y1 ≤ b2 , 0
a3 x − B3 y1 ≤ b3 35
druhá oblast 0
a4 x − B4 y2 ≤ b4 , 0
a5 x − B5 y2 ≤ b5 atd., a
k X
yj ≥ 1
j=1 kde napravo v poslední podmínce je po£et oblastí z výroku aspo¬ v jedné oblasti a
{0, 1} . Kaºdá rovnice má svoje Bi (maximální j = 1, 2, · · · , k, kde k je celkový po£et oblastí.
6.2
yj ∈ yj ,
hodnota levé strany) ale spole£nou veli£inu
Aproximace kriteriální funkce
Aproximace skokové funkce V n¥kterých p°ípadech pot°ebujeme modelovat nelineární funkci (nap°. skok v po£átku). Nap°íklad náklady na výrobu ur£itého výrobku, pokud výrobu budeme realizovat, 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. Jde tedy o následující funkci
(
0 K + c0 x
pro pro
36
x=0 . x≥0
Modelujeme ji takto
Ky + c0 x → min
x ≤ By x≥0 y ∈ {0, 1} Pro
y=0
dostáváme
x=0
a kriterium je také 0; pro
y=1
je
x≤B
a kriterium je
K + c0 x.
Tedy to, co jsme namodelovali je binárn¥ lineární a kopíruje na²i formulaci úlohy (nelineární funkci náklad·).
Aproximace po £ástech lineární funkce 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
0
4
10
(0, 4) a
má sklon 4, druhá na
15
(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 prvního úseku
0 ≤ δ2 ≤ 6
délka druhého úseku
0 ≤ δ3 ≤ 5
délka t°etího úseku
37
Funkci
f (x)
vyjád°íme takto
f (x) = 5δ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
5
x − 10
To zaru£í následující podmínky s dv¥ma novými binárními prom¥nnými
w1
a
w2
4w1 ≤ δ1 ≤ 4 6w2 ≤ δ2 ≤ 6w1 0 ≤ δ3 ≤ 5w2 w1 , w2 ∈ {0, 1} Skute£n¥, pro
w1 = w2 = 0
dostaneme
0 ≤ δ1 ≤ 4, pro
w1 = 1
a
w2 = 0
a nakonec pro
δ2 = 0,
δ3 = 0
δ1 = 4, 0 ≤ δ2 ≤ 6,
δ3 = 0
je
w1 = w2 = 1
máme
δ1 = 4, Poslední varianta
w1 = 0
a
w2 = 1
δ2 = 6, 0 ≤ δ3 ≤ 5.
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.
Poznámka Aproximaci nelineární funkce lze provést jejím nahrazením po £ástech lineární funkcí a postupovat podle p°edchozího.
38
Aproximace sou£inu v kriteriu Máme
x1 , x3 , x3
Kriterium: Zavedeme
- binární veli£iny,
y ∈ (0, u)
spojitá nebo diskrétní veli£ina.
x1 · x2 · x3 · y. w = x1 · x2 · x3 · y
a podmínky
w≥0 w ≤ uxj
w≥u
X
→ w − uxj ≤ 0
w ≤y → w−y ≤0 X xi − 3 + y → u xi − 3 + y − w ≤ 0
39
Poznámka 1. Obecn¥ m·ºe být v sou£inu
k
binárních prom¥nných. Potom poslední podmínka bude
u
X
xi − k + y − w ≤ 0
2. Pokud by n¥která binární prom¥nná byla umocn¥ná, lze mocninu vynechat, protoºe platí
xk = x
pro
x ∈ {0, 1} .
Analýza úlohy Uvaºujme nejd°íve jen dv¥ binární veli£iny pro
w = x1 x2 , w ∈ {0, 2}
x1 a x2 a kriterium J = x1 x2 . Odpovídající podmínky
jsou
P1 : 2w ≤ x1 + x2 P2 : w + 1 ≥ x 1 + x 2 Skute£n¥: pro
x1 + x2 = 0
je
2w ≤ 0 → w ≤ 0 w + 1 ≥ 0 → w ≥ −1 a tedy Pro
w ∈ (−1, 0)
x1 + x2 = 1
a pro
w ∈ {0, 1}
je
w = 0.
je
2w ≤ 1 → w ≤ 0.5 w+1≥1→w ≥0 40
odkud Pro
w ∈ (0, 0.5)
x1 + x2 = 2
a tedy
w=0
je
2w ≤ 2 → w ≤ 1 w+1≥2→w ≥1 a tedy
w = 1.
To p°esn¥ kopíruje sou£in
x1 x2 .
Dále budeme uvaºovat sou£in binární veli£iny bude
J = xy .
w = xy
Op¥t zavedeme
x∈ {0, 1}
a reálné veli£iny
y ∈ (0, u) .
Kriterium
a podmínky
w ≤ ux w≥0 w≤y w ≥ u (x − 1) + y Pro
x=0
bude
w ≤ 0, w ≥ 0, w ≤ y, w ≥ −u + y kde první dv¥ podmínky de nují Pro
x=1
w=0
a druhé dv¥ jsou automatiky spln¥ny.
bude
w ≤ u, w ≥ 0, w ≤ y, w ≥ y kde t°etí a £tvrtá podmínka dává
w=1
a první dv¥ jsou spln¥ny.
Nebo Pro
y
binární bude
w ≥ 0, w ≤ x, w ≤ y, w ≥ x + y − 1 po prozkoumání zjistíme, ºe skute£n¥ je
w = xy.
Realizace minimaxu v kriteriu Máme
k
pracovních tým· pracujících na r·zných úkolech. Chceme navrhnout podmínky práce
tak, aby práce v²ech tým· byla skon£ena co nejd°íve, p°i£emº kaºdý tým musí ukon£it v²echny své úkoly. Hledáme tedy minimum pro nejdel²í dobu pln¥ní úkol· - coº je úloha minimaxu. Modelujeme takto:
p1 (x) , p2 (x) , · · · , pk (x) x).
jsou doby trvání práce jednotlivých tým· (v závislosti na optimalizo-
vané veli£in¥
De nujeme novou prom¥nnou
q
(trvání nejdel²í práce) a zavedeme podmínky
p1
≤
q
p2
≤
q
··· pk
≤
a jako kriterium vezmeme
q → min 41
q
Program pro 3 týmy a 5 úkol· je
7
7.1
e²ení úlohy celo£íselného programování
Metoda v¥tví a mezí
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á.
Poznámka 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 ukázat, ºe optimální °e²ení m·ºe leºet libovoln¥ daleko. Viz p°íklad.
omezení
vrstevnice kritéria optimální LP ?e?ení optimální IP ?e?ení zaokrouhlené LP ?e?ení
42
Z obrázku je vid¥t, ºe zaokrouhlené °e²ení leºí od optimální vrstevnice kriteria dále, neº optimální IP °e²ení. Je to úloha
x + 5y → max x + 5y ≤ 50 x−y ≤5 x + y ≤ 30
a bu¤ LP nebo IP (di_Lp_Ip.lpx). LP dá
[12.5, 7.5]
a IP
[10, 8]
coº není zaokrouhlení.
Metoda v¥tví a mezí (Branch and Bound - B&B) postupuje takto:
1. Vezme optimální LP °e²ení - nap°. na ose
x
nebo
y
(p·jdeme p°es
x).
[12.5, 7.5]
a tento bod vyjme z p°ípustné oblasti bu¤
Tj. p°idá dv¥ nová omezení
x ≤ 12
a
x ≥ 13.
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 (simplex) pro p·vodní úlohu + dv¥ nová omezení. 3. Dostaneme optimální °e²ení. Pokud je celo£íselné, je konec. Pokud není, pokra£ujeme stejn¥ jako p°ed tím (s necelo£íselnou sloºkou optimálního °e²ení). 4. Takhle stále p°idáváme nová omezení, dokud nedostaneme celo£íselné °e²ení.
e²ení budeme demonstrovat na dvou následujících p°íkladech.
43
P°íklad 1 2x1 + 1x2 → max −2x1 + x2 ≤ 11 Lp °e²ení dá
[1.57, 3.14] , J = 33 V¥tvíme nejd°íve podle podle
x1 ,
potom podle
x2
x1 ≤ 1 [1, 4.5] x2 ≤ 1 [1, 2] J = 21
x2 ≥ 5 [2, 1] J = 12
44
P°íklad 2 x1 + 10x2 → max −4x1 + x2 ≤ 0.5 3x1 + x2 ≤ 10 LP °e²ení
[1.36, 5.93] J = 60.64
x1 ≤ 1 [1, 4.5]
x1 ≥ 2 [2, 4] J = 42
x2 ≤ 4 [1, 4] J = 41
7.2
x2 ≥ 5 XXX
Metoda se£ných nadrovin
Tato metoda vychází z optimální simplexové tabulky pro LP. Tuto tabulku p°epí²eme do rovnic. V nich eliminujeme zlomkové koe cienty na pravou stranu a vzniklé rovnice se zlomkovými koe cienty znovu °e²íme simplexovou tabulkou. Kon£íme, kdyº jako výsledek obdrºíme celá £ísla.
Poznámka (geometrická interpretace) 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í.
45
Postup budeme ilustrovat na p°íklad¥.
J = 5x + 8y → max
x + y + s1 = 6 5x + 9y + s2 =45 x, y, s1 , s2 ≥0 LP °e²ení tohoto problému dá simplexovou tabulku
(−z) x y
− 45 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
•
vlevo jsou jen celo£íselné koe cienty,
•
vpravo jdou zlomky, a to tak, ºe
absolutní hodnoty jsou kladné, koe cienty u prom¥nných jsou záporné.
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 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í je stejná jako první
46
≤ 0 (a tedy i levé).
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¥. Program: cuts.lpx První °e²ení
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]
47
xa y .
Ta jsou
Kdyº zkusíme druhé omezení, dostaneme
7
11 3, 3
a museli bychom v hledání dál pokra£ovat.
48
8
8.1
Úlohy III.
Úloha o batohu
Jedná se o jednu ze základních úloh z t°ídy investi£ního rozhodování, viz úvod do IP. Formulace základní úlohy o batohu je následující: Jedeme na výlet stopem a balíme si s sebou
M . Jednotlivé v¥ci mají sv·j i = 1, 2, · · · , n. Chceme s sebou vzít co
v¥ci do batohu. Objem (nosnost) batohu je omezený hodnotou objem (váhu)
mi
a d·leºitost
di
a celkem jich je
n,
tedy
nejvíce d·leºitých v¥cí tak, aby nebyla p°ekro£ena kapacita batohu. Matematická formulace je následující:
n X
di xi → max
i=1 n X
m i xi ≤ M
i=1
xi ∈ {0, 1} , ∀i Základní úloha: C:\_Skola\LinearProgramming_II\Kapsack0.lpx
Více v¥cí najednou: C:\_Skola\LinearProgramming_II\Kapsack1.lpx
49
8.2
Výb¥r z mnoºiny investic
Máme moºnost investovat do n¥kolika z ²esti akcí. Kaºdá akce má n¥jaké nan£ní nároky (investice) a p°inese ur£itý zisk. Máme omezené nan£ní moºnosti. Speci kace je dána v tabulce.
akce
1
2
3
4
5
6
nance k dispozici
nároky
6
9
8
4
9
5
30
výnosy
15
24
25
10
25
20
X
Jak akce vybrat, aby celkový zisk byl maximální a abychom nep°ekro£ili nance, které máme k dispozici. e²ení Ze zadání máme
c0 = [15, 24, 25, 10, 25, 20] A = [6, 9, 8, 4, 9, 5] Zavedeme binární vektor
x - xi ∈ {0, 1} p°i£emº 0 znamená i-tou akci nerealizujeme, 1 znamená
realizujeme. Úloha potom je
c0 x → max
Ax ≤ 30 x ∈ {0, 1} Excel: VyberAkci.xlsx
50
9
9.1
Úlohy IV.
Problém obchodního cestujícího (TSP)
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á. Úlohu budeme demonstrovat pro 5 m¥st.
51
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.
Pro nejkrat²í cestu musí platit
X
J=
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 − 22
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 ×
5 3
= 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:
2 Ve skute£nosti sta£í kontrolovat cykly od 2 do n , kde [·] zna£í celou £ást £ísla. Je to proto, ºe kdyº se 2
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 k > n tedy bude v grafu je²t¥ jeden cyklus s délkou l ≤ n , který 2 2
jsme jiº kontrolovali mezi cykly 2,3· · · , n . Vedle cyklu s délkou v¥t²í neº 2 ty ale budou také pat°it mezi jiº kontrolované.
52
n 2
m·ºe být také více dal²ích cykl·,
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
Program: TSP_asym5.xlsx
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 x d
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
Tady se zadávají délky cest
2 2 9
5
8
1
4
1 1
9 4 6
4 1
1 8 1
7 6
1 3 6
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
53
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! Obecn¥: 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
kou v¥t²í neº
2
kroky, kde
k>
n 2
tedy bude v grafu je²t¥ jeden
, n2 . Vedle cyklu s dél2 m·ºe být také více dal²ích cykl·, ty ale budou také pat°it mezi jiº kontrolované.
n l ≤
cyklus s délkou
k
n
, který jsme jiº kontrolovali mezi cykly 2,3· · ·
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:
•
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
54
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
10
Úlohy V.
Následující p°íklady pat°í do skupiny úloh o mnoºinách: Set covering, Set partitioning a Set packing. Jejich obecné formulace jsou následující: Set covering
c0 x → min
Ax ≥ 1 x ∈ (0, 1)
55
Set partitioning
c0 x → min
Ax = 1 x ∈ (0, 1) Set packing
c0 x → max
Ax ≤ 1 x ∈ (0, 1) Dále uvedem p°íklady na jednotlivé typy úloh.
10.1
Problém pokrytí oblastí
(Set covering) 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¥?
e²ení 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, oblasti jsou
56
··· ,
7. Sousední
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} Program: pozarniStanice.xlsx
57
10.2
Kuch°ka a recepty
(Set packing) 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í
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?
58
Program: recepty.xlsx e²ení: A, C, D.
10.3
Obsazování leteckých tras posádkami
(Set partitioning) 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. 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
59
1. ºádná etapa nez·staly neobsazena, 2. náklady na realizaci tras byly minimální. Ozna£íme
xj ∈ {0, 1} cj
indikuje, zda trasa
j
bude realizována (tj. obsazena posádkou),
j
je cena za pronajatí posádky na trase
ai,j ∈ {0, 1}
(realizaci trasy
ozna£uje (jedni£kou), ºe etapa
Úloha je formulována takto
n X
i
j ),
je za°azena do trasy
j
cj xj → min
j=1 n X
ai,j xj = 1, i = 1, 2, · · · , m
j=1
xj ∈ {0, 1} , j = 1, 2, · · · , n kde kriterium 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
P°íklad 1 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
60
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 de novány bu¤ jako samostatné lety nebo jsou sestaveny z navazujících etap a jsou de novány maticí
a.
Zde vybereme trasy takto
a=
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 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. 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í.
61
P°íklad 2 Jiný p°íklad je realizován v programu: planovaniLetu.xlsx
11
Úlohy VI.
V n¥kterých úlohách je kombinace spojité optimalizace s výb¥rem. Ukáºeme dva takové p°íklady.
62
11.1
Problém rozmíst¥ní sklad·
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
j.
xi,j .
zákazníka.
Úlohu formulujeme takto
m X n X
ci,j xi,j +
m X
i=1 j=1 m X
fi yi → min
i=1
xi,j = dj , j = 1 · · · n
i=1 n X
xi,j
n X − yi dj ≤ 0 , i = 1 · · · m
j=1
j=1
xi,j ≥ 0 , ∀i, ∀j yi ∈ {0, 1} , ∀i Vysv¥tlení: kriterium: celková cena za zboºí a dovoz + poplatky za pronájem sklad·; spln¥ní poºadavk· zákazník·; odb¥r jen z pronajatých sklad· - podmínka je
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 j=1
63
dj
tedy celkové mnoºství zboºí, odebrané ze skladu
i
je men²í nebo rovno celkovému poºadavku
3
v²ech zákazník· (rovno, kdyby se bralo v²echno z jednoho skladu). (Vy²et°ení infek£ního onemocn¥ní)
n
V
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í De nujeme veli£inu
xij ∈ {0, 1}
s hodnotou 1 jestliºe tým
i
bude vy²et°ovat místo
j
nebude. Omezení - kaºdé místo bude nav²tíveno práv¥ jednou
X
xij = 1, ∀j
i - ºádný tým nenav²tíví více neº dv¥ místa
X
xij ≤ 2, ∀i
j
-
x
je binární
xij ∈ {0, 1} , ∀i, j Kriterium - vy²et°ení v²ech míst
X
tij xij , ∀i
j - cestování
X
dkl xik xil , ∀i
k,l; k6=l
Optimalizace:
min maxi
nP
j tij xij +
P
k,l; k6=l dkl xik xil
o
JE TAM SUMA?
Pro kaºdou konstelaci je jeden tým nejdel²í a tohle maximum chceme minimalizovat. Tohle ale neumíme
(i)
(i)
nelinearita v sou£inu,
(ii)
minimax.
nelinearita
3 P d je z°ejm¥ to nejmen²í velké £íslo, aby se podmínka vºdy splnila. j
64
a 0, kdyº
Zavedeme novou prom¥nnou
wikl = xik xil s podmínkami
wikl ≤ xik , wikl ≥ 0, wikl ≤ xil , wikl ≥ xik + xil − 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 Program: infection_small.xlsx,
infection_bigger.xlsx
65
66
11.2 V
n
Vy²et°ení infek£ního onemocn¥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í De nujeme veli£inu
xij ∈ {0, 1}
s hodnotou 1 jestliºe tým
i
bude vy²et°ovat místo
j
nebude. Omezení - kaºdé místo bude nav²tíveno práv¥ jednou
X
xij = 1, ∀j
i - ºádný tým nenav²tíví více neº dv¥ místa
X
xij ≤ 2, ∀i
j -
x
je binární
xij ∈ {0, 1} , ∀i, j Kriterium - vy²et°ení v²ech míst
X
tij xij , ∀i
j - cestování
X
dkl xik xil , ∀i
k,l; k6=l
Optimalizace:
min maxi
nP
j tij xij
+
P
k,l; k6=l
dkl xik xil
o
JE TAM SUMA?
Pro kaºdou konstelaci je jeden tým nejdel²í a tohle maximum chceme minimalizovat. Tohle ale neumíme
(i)
(i)
nelinearita v sou£inu,
(ii)
minimax.
nelinearita
Zavedeme novou prom¥nnou
wikl = xik xil s podmínkami
wikl ≤ xik , wikl ≥ 0, wikl ≤ xil , wikl ≥ xik + xil − 1. 67
a 0, kdyº
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 Program: infection_small.xlsx,
infection_bigger.xlsx
68
69
Po£ítám, ºe tady asi bude konec (jestli ne d°ív). Zbytek je ne ukázku a podobn¥
70
12
Úlohy VII.
12.1
Problém po²tovních box·
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 8×70×0.2 = 112 (dny, platba, procenta).
Zavedeme binární veli£iny pobo£ku
yj
1-pobo£ka
j
bude otev°ena, a
xij
1-oblast
i
posílá platby na
j.
Kriterium
28x11 + 84x12 + 112x13 + 112x14 + 60x21 + · · · + 16x44 + +50y1 + 50y2 + 50y3 + 50y4 → min Omezení
X
xij = 1 ∀i
j
···
kaºdá oblast musí být p°i°azena jedné pobo£ce.
X
xij ≤ 4yj ∀j
i
···
neotev°ené pobo£ce se nesmí nic posílat (4 je tam proto, aby pro
- velké £íslo)
71
y=1
podmínka vypadla
xij , yj ∈ {0, 1} ∀i, j Program: LockBoxes.xlsx
13
Zobecn¥ní TSP
13.1
Nejkrat²í cesta grafem
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.
72
puvodni graf
0
0
0
0
novy uzel
Program: TSP_asym6Ham1.xlsx
73
13.2
Nejkrat²í cesta z daného uzlu
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
Program: TSP_asym6Ham2.xlsx
74
13.3
Nejkrat²í cesta s více náv²t¥vami m¥st
Úloha je dána jako asymetrický TSP, ale p°ipou²tíme více náv²t¥v jednotlivých m¥st.
75
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
Matice nejkrat²ích vzdáleností se velice jednodu²e spo£te pomocí operace 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 provádí sou£et prvk· a vezme se minimum, tedy
(A ⊕ B)i,j = min {ai,k + bk,j }∀k 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. Program: TSP_asym5vice.xlsx (veliké - podívat se v Excelu)
13.4
Nejkrat²í cesta klastry uzl·
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 aplikujeme TSP. Program: TSP_asym6klast.xlsx
76
M → ∞.
Dále
77
