dnes je 3.7.2022

Input:

Analýza citlivosti

13.10.2008, , Zdroj: Verlag Dashöfer

17.4.9
Analýza citlivosti

Doc. Ing. Alois Fiala, CSc.

Postoptimalizační analýza

Až dosud jsme předpokládali, že v úloze lineárního programování jsou všechny prvky matice A i vektorů b a c známé konstanty a že je pevně dán i počet proměnných a omezení. To ovšem ne vždy odpovídá skutečnosti. Často se zpočátku zabýváme zjednodušenou úlohou, v níž neuvažujeme všechna omezení a všechny proměnné. Dodatečně pak chceme zjistit, zda to, co jsme vynechali, skutečně nemá na optimální řešení vliv. Rovněž veličiny v zadání úlohy se často mohou měnit nebo mohou být pouhými odhady a potřebujeme zjistit, jak případné změny těchto veličin ovlivňují optimální řešení úlohy. Těmito otázkami se zabývá analýza citlivosti, která také bývá nazývána postoptimalizační analýzou. Někdy lze popsat změnu zadání úlohy jako závislost veličin úlohy na parametrech, které nabývají hodnot z dané množiny. Sledujeme pak závislost optimálního řešení na těchto parametrech a hovoříme o úloze parametrického programování.

Změna zadání úlohy může spočívat v pouhé změně existujících neřiditelných veličin, tj. koeficientů účelové funkce, hodnot pravých stran omezujících podmínek a koeficientů levých stran těchto podmínek (strukturních koeficientů). Může ale také dojít ke změně struktury modelu, spočívající v přidání či vypuštění proměnných nebo omezení. Při změně zadání se řešení úlohy může změnit různými způsoby: může se změnit pouze optimální hodnota účelové funkce, mohou se změnit optimální hodnoty proměnných při zachování optimálnosti dosavadní báze, může se změnit optimální báze a také se může stát, že úloha nebude mít vůbec přípustné či optimální řešení.

Základní přístupy

V analýze citlivosti optimálního řešení na změny zadání úlohy existují dva základní přístupy:

  • První přístup, který můžeme označit jako experimentální, spočívá v tom, že po vyřešení úlohy zkoumáme důsledky změn, ke kterým dojde v jejím zadání. Neznamená to ovšem, že bychom museli řešit změněnou úlohu od počátku. Většinou totiž můžeme navázat na optimální simplexovou tabulku původní úlohy.

  • Při druhém přístupu, označovaném jako analytický, se zkoumá vždy vliv změn jediné zadané veličiny a zjišťuje se, v jakém rozmezí se tato veličina může změnit, aniž by se změnila optimální báze (hledá se tzv. interval stability).

Důsledky změn pravých stran omezujících podmínek

Změna vektoru b má vliv na hodnoty bázických proměnných a na hodnotu účelové funkce. Tato změna neovlivní kritérium optimality, ale může ovlivnit platnost podmínky nezápornosti řešení. Označme ~b = b + δb. Platí-li tedy pro nový vektor:

B-1~ b0

pak je dosavadní báze primárně přípustná a také optimální, přičemž B-1 ~ b je vektor nových optimálních hodnot bázických proměnných a cBT B-1 ~ b je nová optimální hodnota účelové funkce. V opačném případě v poslední simplexové tabulce změníme poslední sloupec a pokračujeme dále ve výpočtu pomocí duálně simplexového algoritmu.

Důsledky změn účelové funkce

Změna vektoru c způsobí změny pouze v posledním řádku simplexové tabulky, tj. má vliv na kritérium optimality a na hodnotu účelové funkce. Stačí tedy pro nový vektor vypočítat vektor redukovaných cen:

~ T = ~ cBT B-1 A – ~ cT

a prověřit platnost kritéria optimality (~ ≥ 0 pro maximalizační úlohu, ~ ≤ 0 pro minimalizační úlohu). Zůstává-li toto kritérium v platnosti, je báze B nadále optimální, nemění se optimální hodnoty bázických proměnných a optimální hodnota účelové funkce je ~ cBT B-1b. V opačném případě v poslední simplexové tabulce změníme poslední řádek a pokračujeme dále ve výpočtu pomocí primárně simplexového algoritmu.

Intervaly stability pro hodnoty pravých stran

Uvažujme nyní změnu pravé strany k-tého omezení z hodnoty bk na hodnotu bk + δbk a označme ~ b nový vektor pravých stran, který má na rozdíl od původního vektoru takto změněnou pouze k-tou složku. Nechť B je optimální báze a nechť ai,j(k) (i = 1, ... , m) jsou prvky toho sloupce poslední simplexové tabulky, v němž se nachází k-tý sloupec matice B-1 (to znamená, že v počáteční simplexové tabulce byl tento sloupec jednotkový s jedničkou v k-tém řádku). Označme dále β = B-1b. Aby báze B zůstala optimální, musí platit B-1 ~ b0. Po úpravě dostáváme soustavu nerovností:

βi + αi, j(k) δbk ≥ 0, i = 1, ... , m

Řešením této soustavy odvodíme následující podmínky pro δbk:

Příklad 1

Uvažujme úlohu z příkladu 4 v § 17/4.5 a hledejme intervaly stability pro hodnoty pravých stran. Původní vektor pravých stran b = (210, 100, 60, 40)T a simplexová tabulka s optimálním řešením vypadá takto:

   
x1 x2 x3 x4 x5 x6
x6 0 0 1/3 –1 0 1 10
x1 1 0 2/3 –1 0 0 40
x5 0 0 –2/3 1 1 0 20
x2 0 1 –1/3 1 0 0 30
z 0 0 2/3 2 0 0 340

Interval stability pro b1 odvodíme pomocí sloupce x3, neboť v tomto sloupci se nachází první sloupec matice B-1 (ve výchozí simplexové tabulce se v tomto sloupci nacházel první sloupec jednotkové matice).

Nejvyšší přípustný nárůst i pokles hodnoty b1 je tedy roven 30 a intervalem stability pro b1 je interval <210 – 30; 210 + 30> = <180; 240>.

Interval stability pro b2 odvodíme pomocí sloupce x4.

Hodnota b2 se tedy může zvýšit nejvýše o 10 a snížit nejvýše o 20. Intervalem stability pro b2 je interval <100 – 20; 100 + 10> = <80; 110>.

Interval stability pro b3 odvodíme pomocí sloupce x5.

Všechny hodnoty v uvedeném sloupci jsou nezáporné, a tudíž hodnota b3 může růst neomezeně, zatímco snížit se může nejvýše o 20. Intervalem stability pro b3 je interval <40; ∞).

Interval stability pro b4 odvodíme pomocí sloupce x6.

Intervalem stability pro b4 je interval <30; ∞).

Intervaly stability pro koeficienty účelové funkce v maximalizační úloze

Nechť B je optimální báze a označme αij prvky matice B-1A. Pak pro redukované ceny platí, že:

kde cBi je koeficient u i-té bázické proměnné (tj. u bázické proměnné vyskytující se v poslední simplexové tabulce v i-tém řádku). Nechť se k-tý koeficient účelové funkce změní z hodnoty ck na hodnotu ck + δck a označme ~c nový vektor pravých stran, který má na rozdíl od původního vektoru takto změněnou pouze k-tou složku. Musíme zde rozlišovat, zda se jedná o koeficient u bázické nebo nebázické proměnné.

Je-li

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