Ekonomicko-matematické
metody 5
přednáší
doc. RNDr. David Bartl, Ph.D.
Úlohy lineárního programování (LP) I
Nechť 𝑨 ∈ ℝ 𝑚×𝑛
je matice, 𝒃 ∈ ℝ 𝑚
je vektor
pravých stran a 𝒄 ∈ ℝ 𝑛
resp. 𝒄T
∈ ℝ1×𝑛
je
vektor (gradient) cílové funkce.
Primární úloha LP v kanonickém tvaru:
𝒄T
𝒙 ⟶ max
z.p.
𝑨𝒙 ≤ 𝒃
𝒙 ≥ 𝟎
I 2
Primární úloha LP v kanonickém tvaru:
𝑐1 𝑥1 + 𝑐2 𝑥2 + ⋯ + 𝑐 𝑛 𝑥 𝑛 ⟶ max
z.p.
𝑎11 𝑥1 + 𝑎12 𝑥2 + ⋯ + 𝑎1𝑛 𝑥 𝑛 ≤ 𝑏1
𝑎21 𝑥1 + 𝑎22 𝑥2 + ⋯ + 𝑥2𝑛 𝑥 𝑛 ≤ 𝑏2
… … … … … … … … … … … … … … … …
𝑎 𝑚1 𝑥1 + 𝑎 𝑚2 𝑥2 + ⋯ + 𝑎 𝑚𝑛 𝑥 𝑛 ≤ 𝑏 𝑚
𝑥1, 𝑥2, … , 𝑥 𝑛 ≥ 0
I 3
(P) a (D) úloha LP v kanonickém tvaru
Úloha LP v kanonickém tvaru
PRIMÁRNÍ (P)
𝒄T 𝒙 ⟶ max
z.p.
𝑨𝒙 ≤ 𝒃
𝒙 ≥ 𝟎
kde 𝒙 ∈ ℝ 𝑛 je proměnná
DUÁLNÍ (D)
𝒚T 𝒃 ⟶ min
z.p.
𝒚T
𝑨 ≥ 𝒄T
𝒚T 𝑨 ≥ 𝟎T
kde 𝒚T ∈ ℝ1×𝑚 je proměnná
respektive
I 4
(P) a (D) úloha LP v kanonickém tvaru
Úloha LP v kanonickém tvaru
PRIMÁRNÍ (P)
𝒄T 𝒙 ⟶ max
z.p.
𝑨𝒙 ≤ 𝒃
𝒙 ≥ 𝟎
kde 𝒙 ∈ ℝ 𝑛 je proměnná
DUÁLNÍ (D)
𝒃T 𝒚 ⟶ min
z.p.
𝑨T
𝒚 ≥ 𝒄
𝒚 ≥ 𝟎
kde 𝒚 ∈ ℝ 𝑚
je proměnná
I 5
Úlohy LP v kanonickém tvaru
Každou úlohu LP lze převést na kanonický tvar
(P) resp. (D) pomocí obvyklých úprav:
• Podmínky 𝑪𝒙 = 𝒅 napíšeme jako 𝑪𝒙 ≤ 𝒅 a 𝑪𝒙 ≥ 𝒅
respektive
podm. 𝒚T 𝑪 = 𝒅T napíšeme jako 𝒚T 𝑪 ≤ 𝒅T a 𝒚T 𝑪 ≥ 𝒅T
• Podmínky 𝑪𝒙 ≥ 𝒅 napíšeme jako −𝑪𝒙 ≤ −𝒅
respektive
podmínky 𝒚T
𝑪 ≤ 𝒅T
napíšeme jako −𝒚T
𝑪 ≥ −𝒅T
I 6
Úlohy LP v kanonickém tvaru
Každou úlohu LP lze převést na kanonický tvar
(P) resp. (D) pomocí obvyklých úprav:
• Proměnnou 𝑥 ∈ ℝ neomezenou ve znaménku napíšeme
jako 𝑥 = 𝑥+ − 𝑥−, kde 𝑥+, 𝑥− ≥ 0.
(V případě proměnné 𝑦 ∈ ℝ obdobně.)
• Cílovou funkci 𝒄T 𝒙 ⟶ min napíšeme jako −𝒄T 𝒙 ⟶ max
respektive
cílovou funkci 𝒚T
𝒃 ⟶ max napíšeme jako −𝒚T
𝒃 ⟶ min
I 7
Připomeňme úlohy LP v kan. tvaru:
Úloha LP v kanonickém tvaru
PRIMÁRNÍ (P)
𝒄T 𝒙 ⟶ max
z.p.
𝑨𝒙 ≤ 𝒃
𝒙 ≥ 𝟎
kde 𝒙 ∈ ℝ 𝑛 je proměnná
DUÁLNÍ (D)
𝒚T 𝒃 ⟶ min
z.p.
𝒚T
𝑨 ≥ 𝒄T
𝒚T 𝑨 ≥ 𝟎T
kde 𝒚T ∈ ℝ1×𝑚 je proměnná
I 8
Věta o slabé dualitě
Jestliže 𝒙 a 𝒚T
jsou přípustná řešení úloh (P) a (D),
potom platí
𝒄T 𝒙 ≤ 𝒚T 𝒃
Důkaz: 𝒄T 𝒙 ≤ 𝒚T 𝑨𝒙 ≤ 𝒚T 𝒃 □
Heslem:
maximum ≤ minimum
I 9
Důsledky věty o slabé dualitě (𝒄T 𝒙 ≤ 𝒚T 𝒃)
• Jestliže 𝒙∗ a 𝒚T∗ jsou přípustná řešení úloh (P) a (D)
taková, že 𝒄T 𝒙∗ = 𝒚T∗ 𝒃,
potom obě řešení jsou optimálními řešeními obou úloh.
• Jestliže úloha (P) není omezená shora
(𝒄T 𝒙 ⟶ +∞ při splnění 𝑨𝒙 ≤ 𝒃, 𝒙 ≥ 𝟎),
potom úloha (D) není přípustná.
• Jestliže úloha (D) není omezená zdola
(𝒚T 𝒃 ⟶ −∞ při splnění 𝒚T 𝑨 ≥ 𝒄T, 𝒚T ≥ 𝟎T),
potom úloha (P) není přípustná.
I 10
Poznámka ke slabé dualitě
Z důkazu (𝒄T
𝒙 ≤ 𝒚T
𝑨𝒙 ≤ 𝒚T
𝒃) plyne:
Rovnost 𝒄T 𝒙∗ = 𝒚T∗ 𝒃 nastává právě tehdy, když
jsou splněny podmínky komplementarity
𝒄T − 𝒚T∗ 𝑨 𝒙∗ = 0 a 𝒚T∗ 𝑨𝒙∗ − 𝒃 = 0
neboli
෍
𝑗=1
𝑛
𝑐𝑗 − 𝒚T∗ 𝒂𝑗 𝑥𝑗
∗
= 0 a ෍
𝑖=1
𝑚
𝑦𝑖
∗
𝒂𝑖
T
𝒙∗ − 𝑏𝑖 = 0
I 11
Věta o silné dualitě (princip duality)
• Jestliže úloha (P) má optimální řešení 𝒙∗
,
potom úloha (D) má optimální řešení 𝒚T∗
a platí rovnost 𝒄T
𝒙∗
= 𝒚T∗
𝒃.
• Jestliže úloha (D) má optimální řešení 𝒚T∗
,
potom úloha (P) má optimální řešení 𝒙∗
a platí rovnost 𝒄T
𝒙∗
= 𝒚T∗
𝒃.
respektive
I 12
Věta o silné dualitě (princip duality)
• Úloha (P) má optimální řešení právě tehdy,
když úloha (D) má optimální řešení.
To jest, optimální řešení mají
• buď obě úlohy současně,
• anebo žádná z nich.
• Jestliže obě úlohy mají optimální řešení,
potom jejich optimální hodnoty se rovnají.
Heslem:
maximum = minimum
I 13
Věta o existenci optimálních řešení
Jestliže obě úlohy (P) a (D) jsou přípustné
(existují nějaká přípustná řešení 𝒙 a 𝒚T
těchto úloh),
potom obě úlohy mají optimální řešení
(existují optimální řešení 𝒙∗
a 𝒚T∗
těchto
úloh).
I 14
Důsledek všech uvedených tvrzení
Pro úlohy (P) a (D) nastává právě jedna
z následujících možností:
• obě úlohy (P) a (D) jsou přípustné, mají optimální řešení
a platí rovnost optimálních hodnot,
• úloha (P) není přípustná a úloha (D) není omezená zdola,
• úloha (D) není přípustná a úloha (P) není omezená shora,
• obě úlohy (P) a (D) jsou nepřípustné.
I 15
Úlohy lineárního programování (LP) II
Nechť 𝑨 ∈ ℝ 𝑚×𝑛
je matice, 𝒃 ∈ ℝ 𝑚
je vektor
pravých stran a 𝒄 ∈ ℝ 𝑛
resp. 𝒄T
∈ ℝ1×𝑛
je
vektor (gradient) cílové funkce.
Primární úloha LP v normálním tvaru:
𝒄T
𝒙 ⟶ max
z.p.
𝑨𝒙 ≤ 𝒃
II 16
Primární úloha LP v normálním tvaru:
𝑐1 𝑥1 + 𝑐2 𝑥2 + ⋯ + 𝑐 𝑛 𝑥 𝑛 ⟶ max
z.p.
𝑎11 𝑥1 + 𝑎12 𝑥2 + ⋯ + 𝑎1𝑛 𝑥 𝑛 ≤ 𝑏1
𝑎21 𝑥1 + 𝑎22 𝑥2 + ⋯ + 𝑥2𝑛 𝑥 𝑛 ≤ 𝑏2
… … … … … … … … … … … … … … … …
𝑎 𝑚1 𝑥1 + 𝑎 𝑚2 𝑥2 + ⋯ + 𝑎 𝑚𝑛 𝑥 𝑛 ≤ 𝑏 𝑚
II 17
(P) a (D) úloha LP v norm. a std. tvaru
Úloha LP
v normálním tvaru
PRIMÁRNÍ (P)
𝒄T 𝒙 ⟶ max
z.p.
𝑨𝒙 ≤ 𝒃
𝒙 ≥ 𝟎
kde 𝒙 ∈ ℝ 𝑛
je proměnná
ve standardním tvaru
DUÁLNÍ (D)
𝒚T 𝒃 ⟶ min
z.p.
𝒚T 𝑨 = 𝒄T
𝒚T
𝑨 ≥ 𝟎T
kde 𝒚T ∈ ℝ1×𝑚 je proměnná
respektive
II 18
(P) a (D) úloha LP v norm. a std. tvaru
Úloha LP
v normálním tvaru
PRIMÁRNÍ (P)
𝒄T 𝒙 ⟶ max
z.p.
𝑨𝒙 ≤ 𝒃
𝒙 ≥ 𝟎
kde 𝒙 ∈ ℝ 𝑛
je proměnná
ve standardním tvaru
DUÁLNÍ (D)
𝒃T 𝒚 ⟶ min
z.p.
𝑨T 𝒚 = 𝒄
𝒚 ≥ 𝟎
kde 𝒚 ∈ ℝ 𝑚
je proměnná
II 19
Úlohy LP v norm. a std. tvaru
Každou úlohu LP lze převést na normální (P)
a standardní (D) tvar pomocí úprav, které už
známe, a přidáme:
• Podmínky 𝑪𝒚 ≤ 𝒅 napíšeme jako 𝑪𝒚 + 𝒔 = 𝒅 neboli
𝑪𝒚 + 𝑰𝒔 = 𝒅, kde 𝑰 je jednotková matice a 𝒔 ≥ 𝟎 jsou
nové proměnné (angl. slack variables)
Cvičení: Úlohy (P) a (D) v kanonickém tvaru
převeďte na úlohy (P) a (D) v normálním a
standardním tvaru (a obráceně).
II 20
Připomeňme úlohy LP v n. a s. tvaru:
Úloha LP
v normálním tvaru
PRIMÁRNÍ (P)
𝒄T 𝒙 ⟶ max
z.p.
𝑨𝒙 ≤ 𝒃
𝒙 ≥ 𝟎
kde 𝒙 ∈ ℝ 𝑛
je proměnná
ve standardním tvaru
DUÁLNÍ (D)
𝒚T 𝒃 ⟶ min
z.p.
𝒚T 𝑨 = 𝒄T
𝒚T
𝑨 ≥ 𝟎T
kde 𝒚T ∈ ℝ1×𝑚 je proměnná
II 21
Věta o slabé dualitě
Jestliže 𝒙 a 𝒚T
jsou přípustná řešení úloh (P) a (D),
potom platí
𝒄T 𝒙 ≤ 𝒚T 𝒃
Důkaz: 𝒄T 𝒙 = 𝒚T 𝑨𝒙 ≤ 𝒚T 𝒃 □
Heslem:
maximum ≤ minimum
II 22
Důsledky věty o slabé dualitě (𝒄T 𝒙 ≤ 𝒚T 𝒃)
• Jestliže 𝒙∗ a 𝒚T∗ jsou přípustná řešení úloh (P) a (D)
taková, že 𝒄T 𝒙∗ = 𝒚T∗ 𝒃,
potom obě řešení jsou optimálními řešeními obou úloh.
• Jestliže úloha (P) není omezená shora
(𝒄T 𝒙 ⟶ +∞ při splnění 𝑨𝒙 ≤ 𝒃),
potom úloha (D) není přípustná.
• Jestliže úloha (D) není omezená zdola
(𝒚T 𝒃 ⟶ −∞ při splnění 𝒚T 𝑨 = 𝒄T, 𝒚T ≥ 𝟎T),
potom úloha (P) není přípustná.
II 23
Poznámka ke slabé dualitě
Z důkazu (𝒄T
𝒙 = 𝒚T
𝑨𝒙 ≤ 𝒚T
𝒃) plyne:
Rovnost 𝒄T 𝒙∗ = 𝒚T∗ 𝒃 nastává právě tehdy, když
je splněna podmínka komplementarity
𝒚T∗ 𝑨𝒙∗ − 𝒃 = 0
neboli
෍
𝑖=1
𝑚
𝑦𝑖
∗
𝒂𝑖
T
𝒙∗
− 𝑏𝑖 = 0
II 24
Věta o silné dualitě (princip duality)
• Jestliže úloha (P) má optimální řešení 𝒙∗
,
potom úloha (D) má optimální řešení 𝒚T∗
a platí rovnost 𝒄T
𝒙∗
= 𝒚T∗
𝒃.
• Jestliže úloha (D) má optimální řešení 𝒚T∗
,
potom úloha (P) má optimální řešení 𝒙∗
a platí rovnost 𝒄T
𝒙∗
= 𝒚T∗
𝒃.
respektive
II 25
Věta o silné dualitě (princip duality)
• Úloha (P) má optimální řešení právě tehdy,
když úloha (D) má optimální řešení.
To jest, optimální řešení mají
• buď obě úlohy současně,
• anebo žádná z nich.
• Jestliže obě úlohy mají optimální řešení,
potom jejich optimální hodnoty se rovnají.
Heslem:
maximum = minimum
II 26
Věta o existenci optimálních řešení
Jestliže obě úlohy (P) a (D) jsou přípustné
(existují nějaká přípustná řešení 𝒙 a 𝒚T
těchto úloh),
potom obě úlohy mají optimální řešení
(existují optimální řešení 𝒙∗
a 𝒚T∗
těchto
úloh).
II 27
Důsledek všech uvedených tvrzení
Pro úlohy (P) a (D) nastává právě jedna
z následujících možností:
• obě úlohy (P) a (D) jsou přípustné, mají optimální řešení
a platí rovnost optimálních hodnot,
• úloha (P) není přípustná a úloha (D) není omezená zdola,
• úloha (D) není přípustná a úloha (P) není omezená shora,
• obě úlohy (P) a (D) jsou nepřípustné.
II 28
Úlohy lineárního programování (LP) III
Nechť 𝑨 ∈ ℝ 𝑚×𝑛
je matice, 𝒃 ∈ ℝ 𝑚
je vektor
pravých stran a 𝒄 ∈ ℝ 𝑛
resp. 𝒄T
∈ ℝ1×𝑛
je
vektor (gradient) cílové funkce.
Primární úloha LP ve standardním tvaru:
𝒄T
𝒙 ⟶ min
z.p.
𝑨𝒙 = 𝒃
𝒙 ≥ 𝟎
III 29
Primární úloha LP ve standardním tvaru:
𝑐1 𝑥1 + 𝑐2 𝑥2 + ⋯ + 𝑐 𝑛 𝑥 𝑛 ⟶ min
z.p.
𝑎11 𝑥1 + 𝑎12 𝑥2 + ⋯ + 𝑎1𝑛 𝑥 𝑛 = 𝑏1
𝑎21 𝑥1 + 𝑎22 𝑥2 + ⋯ + 𝑥2𝑛 𝑥 𝑛 = 𝑏2
… … … … … … … … … … … … … … … …
𝑎 𝑚1 𝑥1 + 𝑎 𝑚2 𝑥2 + ⋯ + 𝑎 𝑚𝑛 𝑥 𝑛 = 𝑏 𝑚
𝑥1, 𝑥2, … , 𝑥 𝑛 ≥ 0
III 30
(P) a (D) úloha LP ve std. a norm. tvaru
Úloha LP
ve standardním tvaru
PRIMÁRNÍ (P)
𝒄T 𝒙 ⟶ min
z.p.
𝑨𝒙 = 𝒃
𝒙 ≥ 𝟎
kde 𝒙 ∈ ℝ 𝑛
je proměnná
v normálním tvaru
DUÁLNÍ (D)
𝒚T 𝒃 ⟶ max
z.p.
𝒚T 𝑨 ≤ 𝒄T
𝒚T
𝑨 ≥ 𝟎T
kde 𝒚T ∈ ℝ1×𝑚 je proměnná
respektive
III 31
(P) a (D) úloha LP ve std. a norm. tvaru
Úloha LP
ve standardním tvaru
PRIMÁRNÍ (P)
𝒄T 𝒙 ⟶ min
z.p.
𝑨𝒙 = 𝒃
𝒙 ≥ 𝟎
kde 𝒙 ∈ ℝ 𝑛
je proměnná
v normálním tvaru
DUÁLNÍ (D)
𝒃T 𝒚 ⟶ max
z.p.
𝑨T 𝒚 ≤ 𝒄
𝒚 ≥ 𝟎
kde 𝒚 ∈ ℝ 𝑚
je proměnná
III 32
Úlohy LP ve std. a norm. tvaru
Cvičení: Ukažte, že
• úlohy (P) a (D) v kanonickém tvaru,
• úlohy (P) a (D) v normálním a standardním tvaru,
• úlohy (P) a (D) ve standardním a normálním tvaru
lze převést mezi sebou navzájem.
Cvičení:
Ukažte, že úlohy jsou k sobě duální navzájem:
• Úlohu (P) převeďte na úlohu (D).
• Úlohu (D) převeďte na úlohu (P).
III 33
Připomeňme úlohy LP ve s. a n. tvaru:
Úloha LP
ve standardním tvaru
PRIMÁRNÍ (P)
𝒄T 𝒙 ⟶ min
z.p.
𝑨𝒙 = 𝒃
𝒙 ≥ 𝟎
kde 𝒙 ∈ ℝ 𝑛
je proměnná
v normálním tvaru
DUÁLNÍ (D)
𝒃T 𝒚 ⟶ max
z.p.
𝑨T 𝒚 ≤ 𝒄
𝒚 ≥ 𝟎
kde 𝒚 ∈ ℝ 𝑚
je proměnná
III 34
Věta o slabé dualitě
Jestliže 𝒙 a 𝒚T
jsou přípustná řešení úloh (P) a (D),
potom platí
𝒄T 𝒙 ≥ 𝒚T 𝒃
Důkaz: 𝒄T 𝒙 ≥ 𝒚T 𝑨𝒙 = 𝒚T 𝒃 □
Heslem:
minimum ≥ maximum
III 35
Důsledky věty o slabé dualitě (𝒄T 𝒙 ≥ 𝒚T 𝒃)
• Jestliže 𝒙∗ a 𝒚T∗ jsou přípustná řešení úloh (P) a (D)
taková, že 𝒄T 𝒙∗ = 𝒚T∗ 𝒃,
potom obě řešení jsou optimálními řešeními obou úloh.
• Jestliže úloha (P) není omezená zdola
(𝒄T 𝒙 ⟶ −∞ při splnění 𝑨𝒙 = 𝒃, 𝒙 ≥ 𝟎),
potom úloha (D) není přípustná.
• Jestliže úloha (D) není omezená shora
(𝒚T 𝒃 ⟶ +∞ při splnění 𝒚T 𝑨 ≤ 𝒄T),
potom úloha (P) není přípustná.
III 36
Poznámka ke slabé dualitě
Z důkazu (𝒄T
𝒙 ≥ 𝒚T
𝑨𝒙 = 𝒚T
𝒃) plyne:
Rovnost 𝒄T 𝒙∗ = 𝒚T∗ 𝒃 nastává právě tehdy, když
je splněna podmínky komplementarity
𝒄T − 𝒚T∗ 𝑨 𝒙∗ = 0
neboli
෍
𝑗=1
𝑛
𝑐𝑗 − 𝒚T∗ 𝒂𝑗 𝑥𝑗
∗
= 0
III 37
Věta o silné dualitě (princip duality)
• Jestliže úloha (P) má optimální řešení 𝒙∗
,
potom úloha (D) má optimální řešení 𝒚T∗
a platí rovnost 𝒄T
𝒙∗
= 𝒚T∗
𝒃.
• Jestliže úloha (D) má optimální řešení 𝒚T∗
,
potom úloha (P) má optimální řešení 𝒙∗
a platí rovnost 𝒄T
𝒙∗
= 𝒚T∗
𝒃.
respektive
III 38
Věta o silné dualitě (princip duality)
• Úloha (P) má optimální řešení právě tehdy,
když úloha (D) má optimální řešení.
To jest, optimální řešení mají
• buď obě úlohy současně,
• anebo žádná z nich.
• Jestliže obě úlohy mají optimální řešení,
potom jejich optimální hodnoty se rovnají.
Heslem:
minimum = maximum
III 39
Věta o existenci optimálních řešení
Jestliže obě úlohy (P) a (D) jsou přípustné
(existují nějaká přípustná řešení 𝒙 a 𝒚T
těchto úloh),
potom obě úlohy mají optimální řešení
(existují optimální řešení 𝒙∗
a 𝒚T∗
těchto
úloh).
III 40
Důsledek všech uvedených tvrzení
Pro úlohy (P) a (D) nastává právě jedna
z následujících možností:
• obě úlohy (P) a (D) jsou přípustné, mají optimální řešení
a platí rovnost optimálních hodnot,
• úloha (P) není přípustná a úloha (D) není omezená shora,
• úloha (D) není přípustná a úloha (P) není omezená zdola,
• obě úlohy (P) a (D) jsou nepřípustné.
III 41