Ekonomicko-matematické metody 5b přednáší doc. RNDr. David Bartl, Ph.D. Ú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. 𝑨𝒙 = 𝒃 𝒙 ≥ 𝟎 2 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 3 (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 4 (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á 5 Bazické řešení v úloze (P) Řešení 𝒙 ∈ ℝ 𝑛 soustavy 𝑨𝒙 = 𝒃 je • bazické právě tehdy, když množina sloupců 𝒂𝑗 ∶ 𝑥𝑗 ≠ 0 je lineárně nezávislá; • nedegenerované bazické právě tehdy, když je bazické a množina sloupců 𝒂𝑗 ∶ 𝑥𝑗 ≠ 0 generuje všechny ostatní sloupce matice (tvoří bázi – prostoru sloupců matice 𝑨); • přípustné bazické právě tehdy, když je bazické a současně 𝒙 ≥ 𝟎. 6 Primární degenerace bazického řešení Když řešení 𝒙 ∈ ℝ 𝑛 soustavy 𝑨𝒙 = 𝒃 je bazické a degenerované, znamená to, že množina sloupců 𝒂𝑗 ∶ 𝑥𝑗 ≠ 0 je „příliš malá“ (nevygeneruje všechny sloupce matice 𝑨), to znamená, že řešení 𝒙 obsahuje „příliš mnoho nulových složek“. 7 Bazické řešení v úloze (D) Bod resp. řešení 𝒚T ∈ ℝ1×𝑚 je • bazické právě tehdy, když množina sloupců 𝒂𝑗 ∶ 𝒚T 𝒂𝑗 = 𝑐𝑗 generuje všechny ostatní sloupce matice 𝑨; • nedegenerované bazické právě tehdy, když je bazické a množina sloupců 𝒂𝑗 ∶ 𝑦 𝑇 𝑎𝑗 = 𝑐𝑗 je navíc lineárně nezávislá (tvoří bázi – prostoru sloupců matice 𝑨); • přípustné bazické právě tehdy, když je bazické a současně 𝒚T 𝑨 ≤ 𝒄T . 8 Duální degenerace bazického řešení Když řešení 𝒚T ∈ ℝ1×𝑚 je bazické a degenerované, znamená to, že množina sloupců 𝒂𝑗 ∶ 𝒚T 𝒂𝑗 = 𝑐𝑗 je „příliš velká“ (není lineárně nezávislá), to znamená, že v řešení 𝒚T je „příliš mnoho aktivních podmínek “. 9 Základní věta lineárního programování Základní věta LP: Jestliže obě úlohy (P) a (D) mají optimální řešení, potom mají i bazická optimální řešení 𝒙∗ a 𝒚T∗. Navíc platí rovnice 𝒄T 𝒙∗ = 𝒚T∗ 𝑨𝒙∗ = 𝒚T∗ 𝒃 a platí podmínka komplementarity 𝒄T − 𝒚T∗ 𝑨 𝒙∗ = ෍ 𝑗=1 𝑛 𝑐𝑗 − 𝒚T∗ 𝒂𝑗 𝑥𝑗 ∗ = 0 10 Báze Bází rozumíme množinu indexů 𝐵 ⊆ {1, … , 𝑛} takovou, že množina sloupců {𝒂𝑗 ∶ 𝑗 ∈ 𝐵} je lineárně nezávislá a současně generuje ostatní sloupce matice 𝑨. Cvičení: Vraťte se k definici bazického řešení v úloze (P) a v úloze (D). 11 Báze Mějme bázi 𝐵 ⊆ {1, … , 𝑛}. Klademe 𝑁 = 1, … , 𝑛 ∖ 𝐵. 𝐵 – množina indexů bazických proměnných 𝑥𝑗 𝑁 – množina indexů nebazických proměnných 𝑥𝑗 Báze 𝐵 určuje bazické řešení úlohy (P) a úlohy (D) následujícím způsobem. 12 Bazické řešení úlohy (P) určené bází 𝐵 Mějme bázi 𝐵 ⊆ {1, … , 𝑛} a předpokládejme, že soustava 𝑨𝒙 = 𝒃 má alespoň jedno řešení. (Např. 𝑨 je matice typu 𝑚 × 𝑛 a platí, že hodnost 𝑨 = 𝑚 ≤ 𝑛.) Řešme soustavu lineárních rovnic 𝑨 𝐵 𝒙 𝐵 = 𝒃 (soustava má právě jedno řešení) a položme 𝒙 𝑁 = 𝟎 𝑁 Takto získané řešení 𝒙 soustavy 𝑨𝒙 = 𝒃 je bazickým řešením úlohy (P) určeným bází 𝐵. 13 Bazické řešení úlohy (D) určené bází 𝐵 Mějme bázi 𝐵 ⊆ {1, … , 𝑛}. Řešme soustavu lineárních rovnic 𝒚T 𝑨 𝐵 = 𝒄 𝐵 T (soustava má alespoň jedno řešení). Takto získaný bod resp. řešení 𝒚 𝑇 je bazickým řešením úlohy (D) určeným bází 𝐵. 14 Bazické řešení úlohy (P) a báze Mějme bazické řešení 𝒙 ∈ ℝ 𝑛 soustavy 𝑨𝒙 = 𝒃. Jestliže je nedegenerované, potom toto řešení 𝒙 určuje bázi: 𝐵 = 𝑗 ∶ 𝑥𝑗 ≠ 0 Jestliže bazické řešení 𝒙 je degenerované, potom do množiny 𝑗 ∶ 𝑥𝑗 ≠ 0 přidáme další indexy sloupců matice 𝑨 tak, aby množina 𝒂𝑗 ∶ 𝑗 ∈ 𝐵 generovala všechny ostatní sloupce matice 𝑨. 15 Bazické řešení úlohy (D) a báze Mějme bazické řešení 𝒚T ∈ ℝ1×𝑚. Jestliže je nedegenerované, potom toto řešení 𝒚T určuje bázi: 𝐵 = 𝑗 ∶ 𝒚T 𝒂𝑗 = 𝑐𝑗 Jestliže bazické řešení 𝒚T je degenerované, potom z množiny 𝑗 ∶ 𝒚T 𝒂𝑗 = 𝑐𝑗 odebíráme indexy sloupců matice 𝑨 tak, aby množina 𝒂𝑗 ∶ 𝑗 ∈ 𝐵 byla lineárně nezávislá. 16 Báze Báze 𝐵 ⊆ {1, … , 𝑛} je: • primárně přípustná právě tehdy, když bazické řešení úlohy (P) určené bází 𝐵 je primárně přípustné, • duálně přípustná právě tehdy, když bazické řešení úlohy (D) určené bází 𝐵 je duálně přípustné, • optimální právě tehdy, když je přípustná primárně i duálně zároveň. 17 Připomeňme základní větu LP: Základní věta LP: Jestliže obě úlohy (P) a (D) mají optimální řešení, potom mají i bazická optimální řešení 𝒙∗ a 𝒚T∗. Navíc platí rovnice 𝒄T 𝒙∗ = 𝒚T∗ 𝑨𝒙∗ = 𝒚T∗ 𝒃 a platí podmínka komplementarity 𝒄T − 𝒚T∗ 𝑨 𝒙∗ = ෍ 𝑗=1 𝑛 𝑐𝑗 − 𝒚T∗ 𝒂𝑗 𝑥𝑗 ∗ = 0 18 Základní věta lineárního programování Poznámka k rovnici 𝒄T 𝒙∗ = 𝒚T∗ 𝑨𝒙∗ = 𝒚T∗ 𝒃: Ekonomická interpretace řešení (duálních proměnných) je obdobná jako v případě úloh v kanonickém tvaru. Proměnné 𝑥𝑗 ∗ resp. 𝑦𝑖 ∗ mají význam pro citlivostní analýzu: Jak moc se změní společná optimální hodnota, jestliže 𝑐𝑗 resp. 𝑏𝑖 se změní? Poznámka: Změna musí být „malá“! (Malá tak, aby nedošlo ke změně optimální báze.) 19