• ©Jan Schmidt 2011 Katedra číslicového návrhu Fakulta informačních technologií České vysoké učení technické v Praze • Zimní semestr 2011/12 EVROPSKÝ SOCIÁLNÍ FOND PRAHA & EU: INVESTUJENE DO VAŠÍ BUDOUCNOSTI
MI-PAA
13. Lineární programování • Formulace • Prostor řešení a simplexová metoda • Celočíselné lineární programování
Terminologie • „Programování“: čti „programování výrobní linky“ • „Lineární“: čti „při omezujících podmínkách a optimalizačním kritériu vyjádřených lineárními výrazy“ (také kvadratické, hyperbolické … programování) • „Dynamické programování“: programování výpočtu kombinatorického problému
2
Formulace Dána reálná čísla a11 ... amn, b1... bm , c1 ... cn Nalezněte reálná x1 , x2 , ... , xn tak, aby c1x1 + c2x2 + ... + cnxn
max.
cTx max.
za podmínky
a11x1 + a12x2 +... + a1nxn b1 a21x1 + a22x2 + ... + a2nxn b2 am1x1 + am2x2 + ... + amnxn x1
0, x2
0, ... , xn
0
Ax
b
bm x
0 3
Příklady • Výrobní problémy – nechť aij je spotřeba materiálu i pro výrobek j – nechť bi jsou dostupné zdroje materiálu i – nechť cj je zisk z výroby jednotkového množství výrobku j – maximalizace zisku z využití daných zdrojů
• Směšovací problémy – minimalizace nákladů na dosažení stanoveného cíle
4
Příklad Moret & Shapiro x … výroba světlého piva, hl y … výroba tmavého piva, hl
21x + 31y max. 2x + 3y 4x + y 2x + 9y x
0, y
25 32 54 0
Pivovar vaří světlé a tmavé pivo. Na 1hl světlého piva je potřebí 2 jednotky sladu, 4 jednotky chmele a 2 jednotky kvasnic. Na 1hl tmavého piva jsou potřebí 3 jednotky sladu, 1 jednotka chmele a 9 jednotek kvasnic. Zisk z prodeje světlého a tmavého piva je v poměru 21:31. Je k dispozici 25 jednotek sladu, 32 jednotek chmele a 54 jednotek kvasnic. Jaký má být výrobní program pro maximální zisk? 5
Lineární programování a kombinatorické problémy x
konfigurační a výstupní proměnné
A, b, c
vstupní proměnné
Ax x
b 0
cTx max.
omezující podmínky optimalizační kritérium
a přece se netočí … není to kombinatorický problém 6
Tvary lineárního programování cTx max.
cTx max. Ax b x 0
cTx max. Ax = b x 0
Ax =
x
b
0
kanonický tvar
standardní tvar
obecný tvar
formulace základních úloh
metody řešení
praxe 7
Ekvivalence standardní tvar zvláštní případ
ukážeme
obecný tvar zvláštní případ
ukážeme
kanonický tvar
8
Ekvivalence obecný
kanonický xj = xj+ - xj-
xj
0
xj
+
xjpůvodní rovnice
obecný a(i)x
bi
0
0
nechť a(i) je i-tý řádek matice A
a(i)x = bi nová rovnice nové proměnné
a(i)x
bi
-a(i)x
původní rovnice
-bi
nové rovnice
standardní a(i)x + si = bi si 0
a(i)x
bi
a(i)x –si = bi si 0 9
Jak vypadá prostor řešení? Příklad –x1 –x2 – x3 – x4 – x5 – x6 – x7 max. x1 + x2 + x3 + x4 =4 x1 + x5 =2 x3 + x6 =3 3x2 + x3 + x7 = 6 x1, x2, x3, x4, x5, x6, x7
0
m=4 rovnic pro n=7 proměnných n-m=3 proměnné volné nějaký útvar v E3
10
Prostor řešení x1 + x2 + x3 + x4 =4 x1 + x5 =2 x3 + x6 =3 3x2 + x3 + x7 = 6 x1, x2, x3, x4, x5, x6, x7 x1 + x2 + x3 x1 x3 3x2 + x3
4 2 3 6
x1
0 0 0
x2
x3
0
x4, x5, x6, x7
0
11
0,0,3 0,1,3
1,0,3
x3
Geometrický názor 2,0,2
x1
0,0,0
2,0,0
x2
0,2,0
2,2,0
dva průsečíky splynuly v jeden 12
Prostor řešení • Konvexní těleso • y1, y2, ... yk řešení 1 y1+ 2 y2+ ... + k yk je řešení, pokud 1+ 2+ ... + k =1
13
Optimalizační kritérium x1 + x2 + x3 + x4 =4 x1 + x5 =2 x3 + x6 =3 3x2 + x3 + x7 = 6 – x1 – x2 – x3 – x4 – x5 – x6 – x7
x1 + 3x2 + 2x3 – 15
max
max
geometrická reprezentace?
x1 + 3x2 + 2x3 – 15 = z 14
0,0,3
1,0,3
x1 + 3x2 + 2x3 – 15 = z
0,1,3 x3
2,0,2
0,0,0 2,0,0
x2
0,2,0
x1
2,2,0
z = – 15 15
0,0,3
1,0,3
x1 + 3x2 + 2x3 – 15 = z
0,1,3 x3
2,0,2
x1
0,0,0 2,0,0
x2
0,2,0
2,2,0
z = –13 16
0,0,3
1,0,3
x1 + 3x2 + 2x3 – 15 = z
0,1,3 x3
2,0,2
0,0,0 2,0,0
x2
0,2,0
x1
2,2,0
z = –9 17
0,0,3
1,0,3
x1 + 3x2 + 2x3 – 15 = z
0,1,3 x3
2,0,2
x1
0,0,0 2,0,0
x2
0,2,0
2,2,0
z=–6 18
Počet řešení • Prostor řešení je konvexní těleso • Dotyk svazku (nad-)rovin s prostorem řešení je – bod (vrchol) – úsečka (hrana) – (nad-)rovina (stěna)
• Pokud nežádáme všechna řešení, stačí se zabývat jen vrcholy • Nejsou žádná lokální minima • Stačí aplikovat lokální prohledávání (například „pouze nejlepší“) na množinu vrcholů • Ale kde najdeme vrcholy? 19
0,0,3
–9
–8 1,0,3
–6
0,1,3
x3
–9 2,0,2
–13
0,0,0
– 15 x2
0,2,0
–9
x1
2,0,0
2,2,0
–7 20
Báze a bázová řešení nechť a(i) je i-tý sloupec matice A a(1) a(2) a(3) a(4) a(5) a(6) a(7) x1 + x2 + x3 + x4 =4 x1 + x5 =2 x3 + x6 =3 3x2 + x3 + x7 = 6 • Nejméně n-m sloupců lineárně závislých • Volbou m lineárně nezávislých sloupců volíme bázi • Všechny proměnné, které neodpovídají sloupcům báze, položíme rovny nule a řešíme zbylou soustavu • Dostaneme bázové řešení
21
Báze a bázová řešení a(1) a(2) a(3) a(4) a(5) a(6) a(7) x1 + x2 + x3 + x4 =4 x1 + x5 =2 x3 + x6 =3 3x2 + x3 + x7 = 6
B = (a(4) a(5) a(6) a(7)) B = (a(1) a(2) a(3) a(6)) B = (a(1) a(2) a(4) a(6))
x1=x2 =x3=0 (0 0 0 4 2 3 6) x4=x5 =x7=0 (2 2 0 0 0 3 0) x3=x5 =x7=0 (2 2 0 0 0 3 0) dvojitý bod (více než 3 nuly)
B = (a(2) a(5) a(6) a(7))
x1=x3 =x4=0
(0 4 0 0 2 3 –6)
tato báze neodpovídá žádnému řešení22
Přechod mezi bázemi • Každému vrcholu odpovídá nějaká báze • Máme bázi B = (a(B1), a(B2),..., a(Bm)) a odpovídající bázové řešení x • Vybereme si sloupec a(j) , který v bázi není a chceme jej tam mít • Který sloupec vypadne?
23
Přechod mezi bázemi • B = (a(B1), a(B2),..., a(Bm)), odpovídající bázové řešení x • Sloupec a(j) musí být lineární kombinací sloupců báze (s nějakými koeficienty tij) m
a(j) =
i=1
tij a(Bi)
• protože x je řešení a protože proměnné, které neodpovídají sloupcům báze, jsou nulové .
>0
m
i=1 m i=1
xi a(Bi) = b
(xi –
tij) a(Bi) +
rovnice pohybu z původního vrcholu do nového a(j) = b 24
Přechod mezi bázemi B = (a(1) a(3) a(6) a(7))
(2 0 2 0 0 1 4)
a(1) a(2) a(3) a(4) a(5) a(6) a(7) x1 + x2 + x3 + x4 x1 + x5 x3 +x6 3x2 + x3 +x7
=4 =2 =3 =6
chci a(5) do báze a(5) = a(1) - a(3)+ a(6) + a(7)
t15=1 t25= –1 t35=1 t45=1
Jestliže (vhodně uspořádané) sloupce báze tvoří jednotkovou matici, můžeme koeficienty tij číst přímo budeme v tomto tvaru matici udržovat Gaussovou 25 eliminací
Přechod mezi bázemi B = (a(1) a(3) a(6) a(7))
(2 0 2 0 0 1 4)
a(1) a(2) a(3) a(4) a(5) a(6) a(7) x1 + x2 + x3 + x4 x1 + x5 x3 +x6 3x2 + x3 +x7 a(5) = a(1) - a(3)+ a(6) + a(7)
=4 =2 =3 =6
t15=1 t25= –1 t35=1 t45=1
(2–1. ) a(1)+(2+1. ) a(3)+ (1–1. ) a(6)+ (4–1. ) a(7)+ s rostoucím se tento člen max=1 vynuluje nejdříve
a(6) opouští bázi
a(5) = b
(1 0 3 0 1 0 3) 26
–9
0,0,3,1,2,0,3
–8
1,0,3,0,1,0,3
=1
–6 0,1,3,0,2,0,0 x3
–9 2,0,2,0,0,1,4
–15
–13
0,0,0,4,2,3,6
=0
x1
2,0,0,2,0,3,6
x2
0,2,0,2,2,3,0
2,2,0,0,0,3,0
–9
–7
27
Který sloupec? B = (a(B1), a(B2),..., a(Bm)), odpovídající bázové z=
m i=1 m
a(j) = z=
cena řešení x (proměnné, které nepřísluší sloupci báze, jsou nulové)
xi cBi
i=1
tij
j max
proměnné ve sloupcích, příslušejících bázi, redukovány o tij
a(Bi) (cj –
m i=1
tij cBi)
změna ceny při zavedení sloupce j do báze
Zavést sloupec, pro který je z nejlepší nebo aspoň kladné. Neexistuje-li, konec (globální optimum) 28
Tabulky simplexové metody hodnota optimalizačního kritéria c -1 -1 -1 -1 -1 -1 -1
0
0
1 1
1
1
0
0
0
4
0
1 0
0
0
1
0
0
2
0
0 0
1
0
0
1
0
3
0
0 3
1
0
0
0
1
6
-1
A
0. řádek
b
myšlený sloupec pro proměnnou z 29
Řešení příkladu simplexovou metodou na j-té pozici m dostaneme i=1 tij cBi
1
Gaussovou eliminací přivedeme 0 ve sloupcích báze
1 3
2
0
0
0
0
15
1
1
1
1
0
0
0
4
1
0
0
0
1
0
0
2
0
0
1
0
0
1
0
3
0
3
1
0
0
0
1
6
jednotková podmatice báze (nemusíme hledat)
30
2
Co dál? do báze
max
z báze
cj
tijci
a(1)
2
a(5)
-1
1
2 -13
a(2)
2
a(7)
-1
3
6
-9
a(3)
3
a(6)
-1
2
6
-9
z
z
• Nejrychlejší vzestup dostaneme pro a(2) a a(3) • Klasická simplexová metoda rozhoduje jen podle tijci, není tedy metodou pouze nejlepší • Dostaneme a(2) do báze 31
a(2)
3
v bázi
báze a(2) a(4) a(5) a(6), bázové řešení: 0 2 0 2 2 3 0 1 0
1
0
0
0 -1
9
1
0
2/ 3
1
0
0 -1/3
2
1
0
0
0
1
0
0
2
0
0
1
0
0
1
0
3
0
1
1/ 3
0
0
0
1/ 3
2
• vybereme a(3) do báze, bázi opouští a(6), bázové řešení 0 1 3 0 2 0 0 • výběr a(1) do báze vede k 2 2 0 0 3 0 0
32
a(3)
4
v bázi
báze a(2) a(3) a(4) a(5), bázové řešení: 0 1 3 0 2 0 0 1 0
0
0
0 -1 -1
6
1
0 0
1
0 -2/3 0
0
1
0
0
0
1
0
0
2
0
0
1
0
0
1
0
3
0
1
0
0
0 -1/3 1/3
1
Toto by mělo být optimum, avšak kladný koeficient 1. členu 0. řádku nás „navádí“ k přivedení a(1) do báze 33
a(1)
5
v bázi
báze a(1) a(2) a(3) a(5), bázové řešení: 0 1 3 0 2 0 0 0 0
0 -1
0 -1/3 -1
6
1
0 0
1
0 -2/3 0
0
0
0
0
1
1
0
2
0
0
1
0
0
1
0
3
0
1
0
0
0 -1/3 1/3
1
Tato báze odpovídá stejnému bodu jako předchozí (je dvojitý). V 0. řádku není žádný kladný koeficient, víme, že jsme v optimu 34
Simplexová metoda - složitost • možných bází je
m n
• existují instance, na kterých simplexová metoda tyto báze skutečně prohledá • existují polynomiální metody řešení
35
Celočíselné lineární programování A, b, c – celočíselné x – celočíselné
x
{0, 1}: 0/1 lineární programování (zvl. případ)
• Problém batohu je zvláštním případem 0/1 lineárního programování • Problém batohu je NP-těžký • Problém celočíselného lineárního programování je NP-těžký
Řešení celočíselné úlohy má vždy horší optimalizační kritérium než řešení relaxované úlohy v oboru 36 reálných čísel
Příklad
Pivovar vaří světlé a tmavé pivo. Moret & Shapiro Na 1hl světlého piva je potřebí 2 x … výroba světlého jednotky sladu, piva, hl 4 jednotky chmele a y … výroba 2 jednotky kvasnic. Na 1hl tmavého piva, hl tmavého piva jsou potřebí 3 jednotky sladu, 1 jednotka chmele a 9 jednotek kvasnic. 21x + 31y max. Zisk z prodeje světlého a tmavého piva je v poměru 2x + 3y 25 21:31. Je k dispozici 25 4x + y 32 jednotek sladu, 32 jednotek 2x + 9y 54 chmele a 54 jednotek kvasnic. Jaký má být výrobní program x 0, y 0 pro maximální zisk? 37
Příklad 2x+3y=25
4x+y=32
hl
21x+31y = z
2x+9y=54
(7,1 3,6)
1
5
10
hl
38
Příklad, pokračování Moret & Shapiro x … výroba světlého piva, sudů y … výroba tmavého piva, sudů
21x + 31y max. 2x + 3y 4x + y 2x + 9y
25 32 54
Pivo se prodává ve 100l sudech.
x 0, y 0 x, y celé
39
2x+3y=25
4x+y=32
2x+9y=54 229
250
260,7 240
1
5
40
Metoda sečných nadrovin
229
přídavná omezení, volená tak, aby některé neceločíselné vrcholy byly vyloučeny 1
5
250
260,7 240
41
Metoda větví a hranic původní úloha
y
(7,25 3) 245,25
x
y
3
4
máme lepší 7
x
8
není třeba zkoumat, budou horší než 245,25
x 6 (4 6) 250
(7,1 3,6) 260,7;
(6,5 4) 260,5
x 7 nemá řešení
prohledávat prostor úloh tak, aby prořezávání eliminovalo co nejvíce větví 42
Duální úloha „otoč co můžeš“ cTx max.
bTy min.
Ax
ATy
x
b
y
0
c
0
Věty: x,y řešení
cTx
bTy
x,y optimální řešení
cTx = bTy 43
