17.4.5
Jednofázová simplexová metoda
Doc. Ing. Alois Fiala, CSc.
Velmi snadné získání výchozího bazického řešení umožňuje kanonický tvar úlohy LP. Řekneme, že úloha
max { f(x) = cT x | Ax = b, x ≥ 0 }
kde A je typu (m, n), je v kanonickém tvaru, jestliže
matice A obsahuje jednotkovou matici E typu (m, m).
Je-li zadaná úloha v kanonickém tvaru, zvolíme za bázi jednotkovou
matici, tj. B = E. Jestliže položíme vektor nebazických
proměnných xN = 0, pak vektor bazických proměnných xB = b. Jestliže b ≥ 0, pak je takto
získané bazické řešení navíc přípustné.
Příklad 1
Uvažujme úlohu
Tuto úlohu můžeme interpretovat jako úlohu optimalizace výrobního
programu se dvěma druhy výrobků (jejich množství reprezentují proměnné
x1 a x2) a dvěma výrobními zdroji (nevyužitá množství
zdrojů vyjadřují proměnné x3 a x4). Koeficienty v účelové
funkci vyjadřují zisk z prodeje jednotky výrobku, resp. z pronájmu jednotky
výrobního zdroje.
Zadaná úloha je v kanonickém tvaru a pravé strany rovnic jsou
nezáporné. Za bázi zvolme poslední dva sloupce matice soustavy rovnic. Tedy
proměnné x3 a x4 budou bazické a proměnné x1 a
x2 budou nebazické. Jestliže položíme x1 = x2 = 0, dostaneme hodnoty x3 = 50, x4 = 60 a výchozím
přípustným bazickým řešením bude vektor x1 = (0, 0, 50,
60)T.
Abychom mohli posoudit, zda bazické řešení x1 je
či není optimální, vyjádříme z daných rovnic bazické proměnné pomocí
nebazických:
x3 = 50 –2 x1 – 4
x2
x4 = 60 –3 x1 – 2
x2
a získané vyjádření dosadíme do účelové funkce:
z = 40x1 + 30x2 + 5(50 – 2x1 –
4x2) + 3(60 – 3x1 – 2x2) =
(5 . 50 + 3 .
60) – (5 . 2 + 3 . 3 – 40)x1 – (5 . 4 + 3 . 2 – 30)x2 =
430 – (–21)x1 – (–4)x2
Zde tedy máme účelovou funkci vyjádřenou pomocí nebazických
proměnných. Toto vyjádření můžeme symbolicky zapsat ve tvaru
z = F – ∆1x1 –
∆2x2
kde veličina F = 430 je hodnota účelové funkce pro bazické řešení x 1 a ∆1 = –21 a ∆2 = –4 jsou tzv. redukované ceny.
Zkusme nyní posoudit jiná řešení dané úlohy získaná tím způsobem,
že za x1, resp. x2 dosadíme nějakou hodnotu λ > 0
zvolenou tak, aby řešení zůstalo nezáporné. V tomto případě můžeme např. použít
λ = 1. Pro x1 = 1 bude z = 430 + 21 =451 a pro x2 = 1
bude z = 430 + 4 = 434. To znamená, že existují řešení s větší hodnotou účelové
funkce, než je hodnota F, a řešení x1 tedy není
optimální.
Z předchozího plyne, že hodnota –∆j představuje změnu
hodnoty účelové funkce při jednotkovém zvýšení hodnoty nebazické proměnné.
Je-li ∆j < 0, hodnota účelové funkce se zvýší, při ∆j > 0 dojde k jejímu snížení. Aktuální bazické řešení je tedy optimální,
jestliže jsou pro všechny nebazické proměnné redukované ceny ∆j nezáporné. Jestliže je některá z redukovaných cen Dj záporná,
aktuální bazické řešení není optimální, protože hodnotu účelové funkce lze
zvětšit dosazením hodnoty λ > 0 za některou z proměnných, pro něž je
∆j < 0.
V případě řešení x1 jsme zjistili, že redukované
ceny ∆1 a ∆2 jsou záporné a tudíž toto řešení není
optimální. Přejdeme tedy k jinému řešení tak, že za nějakou nebazickou
proměnnou dosadíme kladnou hodnotu λ. Protože volbou x1 = 1
dosáhneme většího přírůstku účelové funkce než volbou x2 = 1 (21
oproti 4), zvolíme proměnnou x1. Nové řešení tedy bude mít tvar
x2 = (λ, 0, 50 – 2λ, 60 –
3λ)T
kde λ > 0. Aby toto řešení dané soustavy rovnic splňovalo
podmínky nezápornosti, musí platit
50 – 2λ ≥ 0
60 – 3λ ≥ 0
Řešením této soustavy nerovnic je
Jak vyplývá ze základní věty LP, při hledání optimálního řešení se
stačí omezit na konečnou množinu bazických řešení. Řešení x2 tedy musí být bazické, což znamená, že musí mít nejvýše dvě složky kladné.
Abychom toho dosáhli, položíme λ = 20, čímž dojde k anulování proměnné
x4 a dostaneme bazické řešení x2 = (20, 0, 10,
0)T.
Řešení x2 odpovídá bázi, tvořené třetím a prvým
sloupcem matice dané soustavy rovnic. Abychom mohli prověřit optimalitu tohoto
řešení stejným způsobem jako v případě řešení x1, musíme tuto
soustavu upravit eliminační metodou tak, aby zůstal zachován jednotkový sloupec
u proměnné x3 a aby se jednotkový sloupec, který byl u proměnné
x4, objevil u proměnné x1. První rovnici upravíme tak, že
od ní odečteme druhou rovnici vynásobenou 2/3. Druhou rovnici upravíme
vydělením třemi. Tak dostaneme následující soustavu:
Tato úprava nám dovoluje vyjádřit bazické proměnné pomocí
nebazických
a dosadit za ně do účelové funkce:
Tedy F = 850, ∆2 = 10 a ∆4 = 7. Redukované
ceny ∆2 a ∆4 jsou kladné, a tudíž je řešení x2 = (20, 0, 10, 0)T optimální. Optimální hodnota účelové funkce je
rovna 850. Uvedený postup výpočtu je příkladem použití simplexového
algoritmu.
NahoruSimplexový algoritmus
Mějme úlohu
max {f(x) = cT x | Ax = b, x ≥ 0}
která je v kanonickém tvaru. Nechť x1 je výchozí
přípustné bázické řešení. Položme k = 1, A(k) = A, b(k) = b. Simplexový algoritmus sestává z
následujících tří kroků, které později rozvedeme podrobněji:
-
Test kritéria optimality pro xk. Je-li
splněno, pak nastává konec (bazické řešení xk je optimálním
řešením).
-
Určení klíčového prvku ars(k) matice A(k). Není-li možné určit klíčový prvek, pak nastává
konec (úloha nemá konečné optimální řešení).
-
Simplexová transformace matice (A(k) | b(k)). Získáme matici (A(k+1) | b(k+1)) a nové bazické řešení xk+1.
Položíme k = k + 1 a postup opakujeme od bodu 1.
Výpočet podle tohoto algoritmu probíhá v simplexové tabulce,
která má tuto strukturu:
Symboly xBi a cBi označují i-tou bazickou proměnnou a její koeficient v účelové funkci. Přitom
xBi je ta bazická proměnná, která se nachází v i-tém
řádku (jí odpovídající jednotkový sloupec má jedničku v i-tém řádku). Veličiny
∆j a F se vypočtou podle následujících vzorců:
Redukované ceny ∆j slouží k testování kritéria optimality
a F představuje hodnotu účelové funkce pro aktuální bazické řešení. Redukovaná
cena ∆j se vypočte tak, že se od skalárního součinu vektoru cen
bazických proměnných a j-tého sloupce matice A odečte cenový koeficient
j-té proměnné. Hodnota F se vypočte jako skalární součin vektoru cen bazických
proměnných a vektoru pravých stran.
Aktuální bázické řešení se získá tak, že se nebázické proměnné
položí rovny nule a bázické proměnné v jednotlivých řádcích se rovnají pravým
stranám.
NahoruKritérium optimality
V případě maximalizační úlohy je aktuální bazické řešení
optimální, jestliže platí
∆j (k) ≥ 0 pro j = 1, ... ,
n
Minimalizační úlohu můžeme převést na maximalizační tak, že místo
minimalizace funkce f(x) maximalizujeme funkci - f(x). Můžeme
ovšem také řešit přímo minimalizační úlohu s upraveným kritériem optimality,
podle nějž je aktuální bazické řešení minimalizační úlohy optimální,
jestliže platí
∆j(k) ≤ 0 pro j = 1, ... ,
n
NahoruUrčení klíčového prvku
Nejprve se určí index s klíčového sloupce podle vztahu
kde J je množina indexů těch sloupců, kde nebylo splněno kritérium
optimality. Klíčový sloupec určuje proměnnou, která se stane bazickou (budeme
říkat, že vstoupí do báze). Pokud podmínce pro klíčový sloupec vyhovuje několik
sloupců tabulky, můžeme volit kterýkoli z nich. Uvedená formulace je společná
pro maximalizační i minimalizační úlohu. Pro maximalizační úlohu můžeme
podmínku pro klíčový sloupec zapsat takto:
a pro minimalizační úlohu takto:
Pak se stanoví index r klíčového řádku na základě vztahu
Klíčový řádek určuje proměnnou, která přestane být bazickou (budeme
říkat, že bude vyloučena z báze). Je-li určen klíčový prvek, pak do báze
vstupuje proměnná xs a nahrazuje bazickou proměnnou na r-té pozici.
Jestliže podmínce pro klíčový sloupec vyhovuje několik řádků tabulky, můžeme
volit kterýkoli z nich. Pokud této podmínce nevyhovuje žádný řádek (všechny
hodnoty jsou nulové nebo záporné), znamená to, že úloha nemá konečné optimální
řešení.
NahoruSimplexová transformace
Klíčový řádek podělíme klíčovým prvkem:
Ostatní řádky (i = 1, ... , m, i ≠ r) upravíme tak, že od nich
odečteme klíčový řádek podělený klíčovým prvkem a násobený prvkem nacházejícím
se na průsečíku upravovaného řádku a klíčového sloupce:
Z uvedených vzorců vyplývá, že řádek, který není klíčový, nesmíme
při úpravě ničím násobit nebo dělit. Pokud tuto zásadu nedodržíme, ztratíme
kanonický tvar a hodnota bazické proměnné odpovídající tomuto řádku se nebude
rovnat pravé straně.
Příklad 2
Řešme nyní úlohu z příkladu 1 při použití simplexové tabulky.
Postup výpočtu zachycují následující tabulky:
Poslední řádek tabulky je určen takto: ∆1 = 5 × 2 + 3 ×
3 – 40 = –21, ∆2 = 5 × 4 + 3 × 2 – 30 = –4, ∆3 = 5 × 1 +
3 × 0 – 5 = 0, ∆4 = 5 × 0 + 3 × 1 – 3 = 0 a F = 5 × 50 + 3 × 60 =
430. Kritérium optimality je nejvíce porušeno ve sloupci proměnné
x1, takže tento sloupec bude klíčový a proměnná x1 vstoupí do báze. Minimální hodnota podílu bi / ai1 pro
ai1 > 0 nastává v řádku s bazickou proměnnou…
