dnes je 29.3.2024

Input:

Jednofázová simplexová metoda

11.1.2008, , Zdroj: Verlag Dashöfer

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, x0 }

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 b0, pak je takto získané bazické řešení navíc přípustné.

Příklad 1

Uvažujme úlohu

                     
z = f(x) = 40 x1 + 30 x2 + 5 x3 + 3 x4 max
2 x1 + 4 x2 + x3 = 50
3 x1 + 2 x2 + x4 = 60
x1, x2, x3, x4 0

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

           
5060
λ ≤ 20 = min { ––– , ––– }
2 3

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:

       
82
–– x2 + x3 –– x4 = 10
3 3

           
21
x1 + –– x2 + –– x4 = 20
33

Tato úprava nám dovoluje vyjádřit bazické proměnné pomocí nebazických

           
82
x3 = 10 – –– x2 + –– x4
33

           
21
x1 = 20 – –– x2 –– x4
33

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.

Simplexový 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:

  1. 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).

  2. 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í).

  3. 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:

             
x1 x2 ... xn
c1 c2 ... cn
xB1 cB1 a11 a12 ... a1n b1
xB2 cB2 a21 a22 ... a2n b2
. . . .. .
. . . .. .
. . . .. .
xBm cBm am1 am2 ... amn bm
1 2 ... n F

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.

Krité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

Urč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í.

Simplexová 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:

   
         1. x1 x2 x3 x4
40 30 5 3
x3 5 2 4 1 0 50
x4 3 3 2 0 1 60
–21 –4 0 0 430

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

Nahrávám...
Nahrávám...