Symetrický duální problém lineárního programování a jeho využití při analýze citlivosti. Základní věta o dualitě

Symetrický duální problém lineárního programování a jeho využití při analýze citlivosti. Základní věta o dualitě

S každou úlohou lineárního programování je jistým způsobem úzce spojena jiná úloha, která je rovněž lineární, a která je původní úlohou jednoznačně určena. Přitom maximalizační úloze odpovídá úloha minimalizační a naopak. Úlohy lineárního programování se tedy vlastně vyskytují ve dvojicích (hovoříme o dvojicích duálně sdružených úloh). Původní úlohu v této dvojici nazýváme primární, kdežto úlohu s ní sdruženou označujeme jako duální.

Úloha (2.65) – (2.67) je tedy jakýmsi ”zrcadlovým obrazem“ úlohy (2.62) – (2.64) a proto zde hovoříme o dvojici

symetricky duálně sdružených úloh.

Slabá věta o dualitě

Necht’ primární úloha je maximalizační s účelovou funkcí f(x) a duální úloha je minimalizační s účelovou funkcí g(u), a necht’ x je libovolné přípustné řešení primární úlohy a u je libovolné přípustné řešení duální úlohy. Pak platí

Silná věta o dualitě

Má-li jedna z duálně sdružených úloh optimální řešení, má optimální řešení i úloha druhá, přičemž optimální hodnoty účelových funkcí si jsou rovny.

Věta o komplementaritě

Přípustná řešení primární úlohy ( ) a duální úlohy ( ) jsou optimální právě tehdy, když platí

Analýza citlivosti

Analýza citlivosti (postoptimalizační analýza) zkoumá vliv změn zadání úlohy na optimální řešení.

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

úloha nebude mít vůbec přípustné řešení

K analýze citlivosti optimálního řešení na změny zadání úlohy existují dva základní přístupy. Prvý přístup můžeme označit jako experimentální, druhý přístup je analytický.

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 pevně dán je i počet proměnných a omezení. Toto 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ěž koeficienty 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 koeficientů ovlivňují optimální řešení úlohy. Těmito otázkami se zabývá analýza citlivosti.

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

úloha nebude mít vůbec přípustné řešení