dnes je 13.7.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) = c T 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 x N = 0, pak vektor bazických proměnných x B = b. Jestliže b0, pak je takto získané bazické řešení navíc přípustné.

Příklad 1

Příklad
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  ≥ 

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 x 1 = (0, 0, 50, 60)T.

Abychom mohli posoudit, zda bazické řešení x 1 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í x 1 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í x 1 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

  50    60   
λ ≤ 20 = min {  –––  ,   ––– 
     

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í x 2 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í x 2 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í x 1, 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:

   
––  x2 + x3 –  ––  x4 = 10 
   

     
x1 ––  x2 +   ––  x4 = 20 
     

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

     
x3 = 10 –  ––  x2 ––  x4 
     

     
x1 = 20 –  ––  x2 –  ––  x4 
     

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) = c T x | Ax = b, x ≥ 0}

která je v kanonickém tvaru. Nechť x 1 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 x k. Je-li splněno, pak nastává konec (bazické řešení x k 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í x k+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 
xB 1  cB 1  a11  a12  ...  a1n  b1 
xB 2  cB 2  a21  a22  ...  a2n  b2 
 
 
 
xB m  cB m  am1  am2  ...  amn  bm 
    1  2  ...  n 

Symboly xB i a cB i označují i-tou bazickou proměnnou a její koeficient v účelové funkci. Přitom xB i 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

Příklad
Ř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 
x3  50 
x4  60 
  –21  –4  430 

Poslední řádek tabulky je určen takto: ∆1 = 5 × 2 + 3 × 3 – 40 = –21, ∆2 = 5 × 4

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