Analýza citlivosti

17.4.9

Analýza citlivosti

Doc. Ing. Alois Fiala, CSc.

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

 NahoruZá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).

 NahoruDů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~ b ≥ 0

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 c_B^T 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.

 NahoruDů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 = ~ c_B^T B^-1 A – ~ c^T

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 ~ c_B^T 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.

 NahoruIntervaly stability pro hodnoty pravých stran

Uvažujme nyní změnu pravé strany k-tého omezení z hodnoty b_k na hodnotu b_k + δb_k 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ť a_i,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 ~ b ≥ 0. Po úpravě dostáváme soustavu nerovností:

β_i + α_{i, j(k)} δb_k ≥ 0, i = 1, ... , m

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

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 c^B_i 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 c_k na hodnotu c_k + δc_k 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…