Lineární programování Petr Tichý
19. prosince 2012
1
Outline
1
Lineární programování
2
Optimalita a dualita
3
Geometrie úlohy
4
Simplexová metoda
2
Lineární programování Lineární program
(1)
min f (x)
x∈Rn
za podmínek
h(x) = 0,
q(x) ≤ 0.
Položme f (x) ≡ cT x,
h(x) ≡ Ax − b,
q(x) ≡ −x,
kde A ∈ Rm×n , b ∈ Rm , c ∈ Rn , m ≤ n, a přepišme ve standardním tvaru (2)
min cT x
x∈Rn
za podmínek
Ax = b,
x ≥ 0.
Problém (2) nazveme lineární program (LP).
3
Převod na standardní tvar LP často nejsou zadány ve standardním tvaru, ale např. ve tvaru min cT x
x∈Rn
za podmínek
Ax ≤ b.
Převod standardní tvar: předchozí lze ekvivalentně zapsat min cT x
x∈Rn
za podmínek
Ax + z = b,
z ≥ 0.
Zavedeme pomocné proměnné x+ a x− , x = x+ − x− ,
x+ ≡ max{x, 0} ≥ 0,
x− ≡ max{−x, 0} ≥ 0
a původní problém přepíšeme ve standardním tvaru min cT x
x∈Rn
za podmínek
x ≡ [x+ , x− , z],
Ax = b,
c ≡ [c, −c, 0],
x ≥ 0,
A ≡ [A, −A, I]. 4
Neexistence řešení
Mohou nastat situace, kdy úloha LP nemá řešení množina přípustných bodů Ax = b, x ≥ 0 je prázdná. existuje posloupnost xk ∈ Rn tak, že cT xk −→ −∞
pro
k → ∞,
problém není zdola omezen.
5
Outline
1
Lineární programování
2
Optimalita a dualita
3
Geometrie úlohy
4
Simplexová metoda
6
LP a Karush-Kuhn-Tackerovy (KKT) podmínky Je-li x∗ řešením (1), pak existují λ ∈ Rm , µ ∈ Rn tak, že ∇f (x∗ ) + ∇h(x∗ )λ + ∇q(x∗ )µ = 0, µT q(x∗ ) = 0, µ ≥ 0. Po dosazení do LP (společně s podmínkami pro přípustnou oblast), c − AT λ − µ = 0, µT x∗ = 0, (3)
µ ≥ 0, Ax∗ = b, x∗ ≥ 0.
7
KKT podmínky jsou postačující LP je konvexní (f i přípustná oblast jsou konvexní) ⇒ KKT podmínky jsou i postačující pro existenci globáního minima.
Věta Splňuje-li nějaká trojice (λ∗ , µ∗ , x∗ ) podmínky (3), pak je x∗ bodem globáního minima problému (2) Důkaz:
8
Duální problém Problém (2) nazveme primární problém. Duálním problémem k problému (2) nazveme problém max bT λ
(4)
λ∈Rm
za podmínky
AT λ ≤ c .
Ekvivalentní vyjádření duálního problému: (5)
max bT λ
λ∈Rm
za podmínek
AT λ + µ = c ,
µ ≥ 0.
λ a µ se nazývají duální proměnné. Primární a duální problém → nad stejnými daty A, b, c. Jaký je mezi nimi vztah?
9
Vztah primárního a duálního problému Pozorování: KKT podmínky pro duální problém (5) se shodují s KKT podmíkami (3) pro problém (2).
Lemma (slabá dualita) Je-li x bodem přípustné oblasti problému (2) a λ bodem přípustné oblasti problému (4), pak platí cT x ≥ λT b .
Důsledek Jsou-li x0 a λ0 body přípustných oblastí problémů (2) a (4) a platí-li cT x0 = λT0 b , potom jsou x0 a λ0 řešeními korespondujících problémů. 10
Vztah primárního a duálního problému Silná dualita
min cT x
za podmínek
Ax = b,
max bT λ
za podmínky
AT λ ≤ c .
x∈Rn λ∈Rm
x ≥ 0.
Věta (silná dualita) Problém (2) má konečné řešení právě tehdy, když problém (4) má konečné řešení. Mají-li oba problémy konečná řešení, pak jsou si hodnoty cílových funkcí v řešení rovny. Je-li jeden z problémů neomezený, potom je přípustna oblast druhého problému prázdná.
11
Outline
1
Lineární programování
2
Optimalita a dualita
3
Geometrie úlohy
4
Simplexová metoda
12
Bázické body Idea
Nechť A ∈ Rm×n , b ∈ Rm , m ≤ n. Uvažujme problém (6)
Ax = b .
Je-li rank(A) = m, lze z A vybrat m lineárně nezávislých sloupců a poskládat je do (regulární) matice B, např. (pro jednoduchost), B = [a1 , . . . , am ]. Soustava BxB = b má jednoznačné řešení. Položíme-li "
x=
xB 0
#
,
je x jedním z řešení soustavy (6). 13
Bázické body Definice
Definice (bázický bod) Uvažujme problém (6) a nechť B ∈ Rm×m je regulární matice vytvořená z vybraných sloupců matice A. Položme všechny složky vektoru x, které nejsou asociovány se sloupci B, rovny nule. Položme zbývající složky x rovny příslušným složkám řešení soustavy BxB = b. Takový vektor x nazveme bázickým bodem problému (6). Složky vektoru x korespondující k sloupcům B nazveme bázické proměnné. V dalším předpoklad: m < n a A má lineárně nezávislé řádky. Pokud je jedna nebo více bázických proměnných nulových, pak x nazveme degenerovaný bázický bod. Zajímají nás bázické přípustné body splňující navíc x ≥ 0. 14
Řešení a bázické přípustné body Věta (Základní věta lineárního programování) Uvažujme problém min cT x
x∈Rn
za podmínek (7)
Ax = b,
x ≥ 0,
kde A ∈ Rm×n , rank(A) = 0. Existuje-li přípustný bod splňující (7), pak existuje i bázický přípustný bod. Existuje-li řešení výše uvažovaného problému, pak existuje i řešení, které je bázickým přípustným bodem. Důsledek: Řešení problému lineárního programování stačí hledat mezi bázickými přípustnými body. 15
Geometrie úlohy Definice (extrémní bod) Nechť C ⊆ Rn je konvexní množina. Bod x ∈ C nazveme extrémním bodem množiny C, pokud neexistují dva různé body x1 ∈ C a x2 ∈ C takové, že x = αx1 + (1 − α)x2
pro nějaké 0 < α < 1 .
Věta (ekvivalence extrémních a bázických přípustných bodů) Nechť A ∈ Rm×n , b ∈ Rm , m < n, rank(A) = m. Nechť K je konvexní polytop (průnik poloprostorů) obsahující všechny vektory x ∈ Rn splňující podmínky (7), Ax = b,
x ≥ 0.
Potom x je extrémním bodem K právě tehdy, je-li přípustným bázickým bodem. 16
Geometrie úlohy
17
Důsledky geometrické interpretace úlohy
1
Je-li konvexní množina K určená podmínkami Ax = b a x ≥ 0 neprázdná, pak má alespoň jeden extrémní bod.
2
Množina K určená podmínkami Ax = b a x ≥ 0 má nejvýše konečný počet extrémních bodů.
3
Je-li K omezená, pak je K mnohostěnem (polyhedronem), tj. je konvexní kombinací konečného počtu bodů.
18
Outline
1
Lineární programování
2
Optimalita a dualita
3
Geometrie úlohy
4
Simplexová metoda
19
Idea simplexové metody
Idea: Procházet bázické přípustné body (jeden z nich je řešením). V každém proku je potřeba: zůstat v množině bázických přípustných bodů, snižovat hodnotu cílové funkce, umět detekovat případ, kdy je problém neomezený.
20
Formalismus výběru sloupců Ze sloupců matice A vybereme m, které jsou LN → B. Označme B množinu indexů takových, že B = [ai ]i∈B , →
A
B
→
B.
Dále označme N = {1, 2, 3, . . . , n} \ B a N = [ai ]i∈N , A
→
N
→
N.
B nazveme množinou bázických a N nebázických indexů. Podle B a N lze rozdělit n-složkové vektory x, µ a c na xB ≡ [xi ]i∈B ,
xN ≡ [xi ]i∈N ,
cB ≡ [ci ]i∈B ,
cN ≡ [ci ]i∈N ,
µB ≡ [µi ]i∈B ,
µN ≡ [µi ]i∈N .
21
Idea dosazení do KKT
Podle definic indexových množin B a N , a matic B a N je Ax = b
⇔
BxB + N xN = b .
x je dle definice bázickým bodem ⇔ xB = B −1 b, xN = 0. Idea: Mějmě bázický přípustný bod x a příslušné indexové množiny. Dosaďme jej do KKT podmínek a volme ostatní parametry tak, aby byly KKT podmínky „co nejlépe“ splněny. (Pokud se podaří nalézt x splňující KKT podmínky, máme řešení.
22
Dosazení bázického přípustného bodu do KKT podmínek Ax = b, x ≥ 0, T
µ x = 0, T
c − A λ − µ = 0, µ ≥ 0. x je přípustný bázický → první dvě podmínky splněny a xN = 0. Volme µB ≡ 0, potom xT µ = xTB µB + xTN µN = 0 ⇒ třetí OK. Dopočítejme λ a µN tak, aby byla splněna čtvrtá podmínka: cB − B T λ − µB = 0
a
cN − N T λ − µN = 0.
S využitím µB = 0 dostaneme λ = B −T cB
a
µN = cN − N T λ.
Pokud µN ≥ 0 → pátá splněna a máme řešení. Pokud ne, využijeme záporné složky µN k přesunu do „lepšího“ bodu. 23
Formulace problému přesunu Máme bázický přípustný x a množiny indexů B, N . Chceme přesun x→y tak, aby y byl bázický přípustný, aby byla „lépe“ splněna podmínka nezápornosti µ, aby klesla cenová funkce, cT x ≥ cT y, aby došlo k výměně pouze jednoho indexu mezi B a N . Pivoting: Chceme určit vstupní index k ∈ N a výstupní index p ∈ B, zaměnit je, a určit příslušné bázické řešení y. 24
Určení vstupního a výstupního indexu Zvolme vstupní index k tak, že µk < 0. ak je příslušný sloupec A. Nové y bude určitě splňovat yi = 0 pro i ∈ N , i 6= k. Chceme Ay = b → dosaďme, Ay = ByB + ak yk = b = Ax = BxB , a proto (8)
yB = xB − B −1 ak yk . | {z } d
Volme yk > 0 jako nejmenší kladné číslo takové, že je některá ze složek yB nulová. Index této nulové složky je výstupní index p. Geometricky: Pohyb po hraně přípustného mnohostěnu až dokud nedojdeme do dalšího vrcholu. 25
Jak krok (8) ovlivní cT x? jednoduchými algebraickými úpravami lze ukázat cT y = cT x + µk yk . Víme, že µk < 0. Je-li báze nedegenerovaná, je yk > 0 a µ k yk < 0 .
Věta Je-li lineární program (2) omezený a nedegenerovaný, pak simplexová metoda nalezne optimální řešení po konečné počtu kroků.
26
Krok simplexové metody Dáno B, N a x, xN = 0. Řešme B T λ = cB → λ. Spočtěme µN = cN − N T λ. Pokud µN ≥ 0 → stop, máme řešení. Určeme vstupní index k tak, že µk < 0. Řešme Bd = ak , získáme d = B −1 ak . Pokud d ≥ 0 → stop, neomezený problém. Určeme yk a výstupní index p: (xB )i di >0 di
yk ≡ min
a p je index, pro který nastává minimum. Aktualizace yB = xB − dyk ,
yN = [0, . . . , 0, yk , 0, . . . , 0]T .
Záměňme v B a N indexy k a p. 27
Krok simplexové metody
28
