Ekonomicko-matematické
metody 5a
přednáší doc. RNDr. David Bartl, Ph.D.
(P) a (D) úloha LP v kanonickém tvaru
Úloha LP v kanonickém tvaru
F F
PRIMÁRNI (P)
F F
DUALNI (D)
z.p.
c x —> max
Ax < b x>0
z.p.
yTb —> min
yTA > cT -T >0T
kde xeff1 je proměnná
kde yT e Rlxm •
v r
je proměnna
respektive
(P) a (D) úloha LP v kanonickém tvaru
Úloha LP v kanonickém tvaru
PRIMÁRNÍ (P) DUÁLNÍ (D)
cTx —> max bTy —> min
z.p. z.p.
Ax < b ATy > c
x>0 y>o
kde xel" je proměnná       kde y ERm je proměnná
Věta o silné dualitě (princip duality)
• Jestliže úloha (P) má optimální řešení x*, potom úloha (D) má optimální řešení yT* a platí rovnost cTx* = yT*b.
• Jestliže úloha (D) má optimální řešení yT*, potom úloha (P) má optimální řešení x*
a platí rovnost cTx* = yT*b.
respektive
4
Věta o silné dualitě (princip duality)
• Úloha (P) má optimální řešení právě tehdy, když úloha (D) má optimální řešení.
To jest, optimální řešení mají
• buď obě úlohy současně,
• anebo žádná z nich.
• Jestliže obě úlohy mají optimální řešení, potom jejich optimální hodnoty se rovnají.
Heslem:
maximum = minimum
Ekonomická interpretace (příklad)
Uvažujme, že úloha (P) je úlohou stanovení optimálního výrobního programu při míchání směsí (racio, músli, směsi travní / zednické):
• Xj   - množství ;'-té směsi, které se má vyrobit
• cj   - prodejní cena (v n) za 1 jednotku j-té směsi
Co znamená hodnota cílové funkce?
c x = y CjXj = (zisk) n
;'=i
kde: (zisk) = číslo, a = jednotka měny (peníze)
n
Ekonomická interpretace (příklad)
Co znamená rovnost optimálních hodnot cílových funkcí obou úloh?
cTx = yTAx = yTb
Již víme: Levá strana vyjadřuje zisk (v penězích n). Proto i pravá strana vyjadřuje zisk (v penězích a).
7
Ekonomická interpretace (příklad)
Máme:
Uvažujme, že úloha (P)je úlohou stanovení optimálního výrobního programu při míchání směsí (racio, músli, směsi travní / zednické):
• bi   - dostupné množství i-té suroviny Tudíž:
• yt   - cena (v a) za 1 jednotku množství
i-té surovinv
m
yTb
t=i
Ekonomická interpretace (příklad)
Kontrola:
c x = y
TAx = yTb
neboli
n m n
m
j=l (=1j=l
(=1
Dále máme:
• yt   - cena (v a) za 1 jednotku množství
i-té suroviny
• dij - technologický koeficient:
počet jednotek množství i-té suroviny potřebné k výrobě 1 jednotky y'-té směsi
• Xj   - množství y-té směsi, které se má vyrobil
Ekonomická interpretace (příklad)
Dále máme:
• yt   - cena (v ») za 1 jednotku množství
i-té suroviny
• atj - technologický koeficient:
počet jednotek množství i-té suroviny potřebné k výrobě 1 jednotky j-té směsi
• xj   - množství ;'-té směsi, které se má vyrobit
Tudíž:
n m m n
n
y L—L J-j        \----v
j=l i=l i=lj=l
II IIL IIL II
V cjXj = V ytbt = y y yia^ = (zisk)
10
Ekonomická interpretace
Význam duálních proměnných yt, ...,ym v uvažované úloze stanovení optimálního výrobního programu při míchání směsí:
Jsou to tzv. stínové ceny (angl. shadow prices) jednotlivých zdrojů resp. vstupních surovin číslo
Jestliže i-té suroviny je dostatek (a]x < b{), potom její duální cena je nulová (yt = 0).
Jestliže i-tá surovina se výrobou vyčerpá (ajx = bt), potom její duální cena je obvykle (!) kladná {yt > 0).
Ekonomická interpretace
Jak řečeno:
Jestliže i-tá surovina se výrobou vyčerpá (ajx = bt), potom její duální cena je obvykle (!) kladná (yr > 0).
Poznámka:
Může se stát, že i-tá surovina se výrobou vyčerpá (ajx = bi) a její duální cena je přesto nulová (yi = o) - jde o degeneraci řešení.
12
Ekonomická interpretace hodnoty
Význam hodnoty duální proměnné yt\
Jestliže yt > 0, znamená to, že i-tá surovina se vyčerpala, a proto již není možné vyrobit více výrobků (směsí).
Jestliže í-tou surovinu je možné nakoupit na vnějším trhu, pak hodnota yt představuje horní mez ceny, za kterou se vyplatí surovinu nakoupit (je-li dražší, zvýšení výroby nepřinese zisk).
13
Ekonomická interpretace hodnoty
Význam hodnoty duální proměnné yt\
Tedy:
• bt se zvýší (přikoupíme surovinu),
• všechna yt zůstanou na původních hodnotách (to je předpoklad - oprávněný,
pokud změna bt je „malá"),
• xt se změní (dojde ke zvýšení výroby),
• zisk se zvýší (prodejní ceny c} zůstávají stejné)
14