Ekonomicko-matematické
metody 6
Prof. RNDr. Jaroslav Ramík, CSc.
prednasi doc. RNDr. David Bartl, Ph.D.
EMM 6
Úloha lineárního programování
i Základní tvar
cxxx+ c2x2+... + c^n -» MAX;   (1) účelová funkce
(MIN)
za podmínek
a2lXl+ a22X2+ ••• + a2rfin   — ^2
amlXl+ am2X2+ — + amnXn —
(2) omezující podmínky ve tvaru nerovností
xl > 0 , x2 > 0 ,..., xn> 0
(3) podmínky nezápornosti
MME6
2
Rriklad 1: Optimální výrobní plán - úloha LP
z = 2000*! + 300(k2 -> MAX;
při omezeních
0,9jc! + 0,3x2 < 270 0,5x2 < 100 0,1^ + 0,2x2<60
Xi> 0
MME6
3
Dualita jako vztah mezi dvěma úlohami lineárního programování
• Dualitou v úlohách LP rozumíme vzájemný, přesně definovaný vztah mezi dvojicí úloh LP -primární a duální úlohou vycházejících ze stejných vstupních dat.
• Dualita je vzájemně symetrickým vztahem obou úloh - úloha primární není nadřazena úloze duální ani naopak!
• Duální úloha k duální úloze je úloha primární.
• Formální formulace tvaru primární a duální úlohy - souměrná a nesouměrná dualita.
EMM 6
Souměrná dualita - zápis pomocí
sumací
primární úloha (P)	duální úloha (D)
maximalizovat n z=Hcjxj 7=1	minimalizovat m 1=1
n 7=1	Ev* -cy> y = i525 ...5 «
Xj >0,   j = 1,2,...,«	7ř > 0,   / = 1,2,...,/«
EMM 6
Souměrná dualita - maticový zápis
Primární úloha	Duální úloha
(P)	(D)
maximalizovat	minimalizovat
z = cTx	/=bTy
Ax<b	ATy > c
x>0	y>0
EMM 6
Souměrná dualita - postup konstrukce duální úlohy k úloze primární
• maximalizace účelové funkce se mění na minimalizaci, popř. naopak
• ke každému vlastnímu omezení (P) se přiřadí jedna duální proměnná yt, i= 1,2,...,m a dále podmínka :
yt>0
• ke každé proměnné xp j= 1,2,...,«, (P) se přiřadí vlastní omezení duální úlohy
• matice strukturních koeficientů (D) se mění na transponovanou matici strukturních koeficientů (P)
• koeficienty pravé strany (D) se mění na koeficienty účelové funkce (P) a naopak
• smysl nerovností vlastních omezení se v (D) mění na opačný! bmm 6
Souměrná dualita
Příklad 1: „Krmné směsi"
(P)	(D)
maximalizovat z = 2000*i + 3000*2	minimalizovat /= 270ji + 100y2 + 60j3
0,9*! + 0,3*2 ^ 270 0,5*2 < 100 0,1*! + 0,2*2 < 60 \	0,9ji          + 0,1^ > 2000 0,3^ + 0,5^2 + 0,2^ > 3000
*!>0 / *2>0	EMM 6                      > 0
Nesouměrná dualita
• U souměrné duality byla v úloze s maximalizací účelové funkce všechna vlastní omezení ve tvaru nerovnic se smyslem nerovnosti „<"
• Pro všechny proměnné platily podmínky nezápornosti
• V reálných úlohách LP se tato situace často nevyskytuje
EMM 6
Nesouměrná dualita
Příklad 2: „Krmné směsi"
(P) maximalizovat
z = 2000^ + 3000*2
za podmínek
0,9*! + 0,3*2 ^ 270 0,5*2 > 100
0,l*i +0,2*2 < 60
*i > 0
*2>0
Podmínku > vynásobíme -1, a tím změníme znak nerovnosti na < , pak je úloha ve tvaru pro souměrnou dualitu
EMM 6
Nesouměrná dualita
Příklad 3: „Krmné směsi"
(P)
maximalizovat
z = 2000*! + 3000*2 za podmínek
0,9*! + 0,3*2 ^ 270 0,5*2 < 100
0,1*! + 0,2*2 = 60
*i>0
*2>0
EMM 6
Nesouměrná dualita
Příklad 3: „Krmné směsi" - řešení 1
• Rozložíme 3. podmínku = ve tvaru rovnosti na dvě nerovnice:
0,1*! + 0,2;t2 > 60 0,l*i + 0,2*2 < 60
• 1. nerovnici > vynásobíme -1 -0,1*! -0,2*2 <-60
• Pak je úloha ve tvaru pro souměrnou dualitu
EMM 6
Nesouměrná dualita
Příklad 3: „Krmné směsi" - řešení 2
Primární úloha má nyní tvar: maximalizovat
z = 2000*! + 3000*2
za podmínek
0,9*! + 0,3*2 < 270 0,5*2 < 100
0,1*! + 0,2*2 < 60
-0,1*! - 0,2*2 <-60
*i > 0
*2>0
4 podmínky < => 4 duální proměnné yx, y2, y3\ y3"!!!
EMM 6
Nesouměrná dualita
Příklad 3: „Krmné směsi" - řešení 3
Duální úloha je tedy následující: minimalizovat
/= 270^ + 100y2 + 600^3") za podmínek
0,9^+ 0,l(y3'-y3")>2000 0,3y1 + 0,5y2 +0,20^-y3'')> 3000
Jl>0 ^
EMM 6
Nesouměrná dualita
Příklad 3: „Krmné směsi" - řešení 4
• Označíme y3 = y3- y3" , lze (D) zjednodušit
• Pozor! rozdíl dvou nezáporných čísel není vždy nezáporný
(P)	(D)
maximalizovat z = 2000^ + 3000*2	minimalizovat /= 270?! + 100y2 + 60y3
0,9*! + 0,3*2 < 270 0,5*2 < 100 0,l*j+ 0,2*2 = 60 ^	0,9?! + 0,ly3 > 2000 0,3y! + 0,5^ + 0,2y3 > 3000
*i> 0 *2>0 EM	v. ?i>0 vi 6              y3 libovolné
Nesouměrná dualita úlohy LP
s rovnicemi ve vlastních omezeních -standardní tvar (maticový zápis)
(P)	(D)
maximalizovat z = cTx	minimalizovat /=bTy
Ax = b	ATy > c
x>0	y - libovolné (tj. omezení nezápornosti chybí)
EMM 6
Vztahy mezi (P) a (D) úlohou LP
Věty 1 až 5:
1. Duální úloha k duální úloze LP je úloha primární
2. Mají-li obě úlohy (P) a (D) přípustné řešení, pak mají obě také řešení optimální
3. Je-li x libovolné přípustné řešení úlohy (P), y libovolné přípustné řešení úlohy (D), pak
cTx < bTy
4. Platili cTx = bTy, pak x je optimální řešení úlohy (P) a y je optimální řešení úlohy (D)
5. Má-li jedna z úloh (P) a (D) přípustné řešení, ale nemá řešení optimální, pak druhá úloha nemá žádné přípustné řešení
EMM 6
Věta 6: Hlavní věta o dualitě
Má-li jedna z úloh (P) nebo (D) optimální řešení (x nebo y), má jej také druhá úloha, přičemž platí, že hodnoty účelových funkcí jsou stejné, tj. cTx = bTy
EMM 6
Příklad 4: Primární a duální úloha
(P) (D)
3 jcj + 2 x2 + x3    MAX;    6y1 + l0y2 -> MIN;
při omezeních při omezeních
2 xx +3 jc2 + 6 x3 < 6 2    + 4 y2 > 3
4xj+       2x3<10 3>;i -2
*>0 6y1 + 2y2>l
yj>0
Přípustná reseni (napr.):
xJ = (x{, x2;x3) = (l ,0,0), jT=(};i ;,y2) = (l, 1) Optimální řešení:
x*T = (2,5 ; 0,33 ; 0),j>*T = (0,67 ; 0,42), cTj*r*=6Tv* = 8,17
EMM 6
Příklad 1: „Krmné směsi"
(P)	(D)
maximalizovat z = 2000*! + 3000*2	minimalizovat /= 210yi + 100y2 + 60y3
0,9*! + 0,3*2 ^ 270 0,5*2 < 100 0,l*i + 0,2*2 < 60	0,9^          + 0,1^ > 2000 0,3^ + 0,5y2 + 0,2y3 > 3000
*i> 0 *2>0	EMM 6                 3^3 > 0
Ekonomická interpretace duality 1
Prvky primárního modelu (P):
• xx množství výrobku 1 (vyrobené směsi I)
• x2 množství výrobku2 (vyrobené směsi II)
• z celkový zisk, z* = 1 020 000,- Kč
• bx disponibilní kapacita zdrojel (rýže), bx = 270
• b2 disponibilní kapacita zdroje2 (pšenice), b2= 100
• b3 disponibilní kapacita zdroje3 (vloček), b3 = 60
• x* optimálni výrobní program
x* = (240; 180)
• Označme j* optimální řešení duální úlohy
y* = (666,67 ; 0 ; 14000)
EMM 6
Ekonomická interpretace duality 2
Podle hlavní věty o dualitě platí
Pšenice Vločky
Rýže
z* = 270-666,67 + 100 0 +60-14000 = 1020000
• Hodnoty duální proměnné interpretujeme jako ocenění 1 jednotky příslušného zdroje
• Jde tu o marginální ocenění zdrojů, tzn. nejvyšší cenu jednotky užitého zdroje, za kterou se ještě „vyplatí" nakoupit tento zdroj, tzv. stínová cena („shadow price")
• Je-li skutečná cena jednotky zdroje menší než stínová cena, vyplatí se rozšířit výrobu nákupem tohoto zdroje
• Stínová cena představuje náklady obětované příležitosti: nevyčerpaný zdroj má nulovou hodnotu duální proměnné, tj. nulovou stínovou cenu. Jeho zvýšení o jednotku proto nezpůsobí zvýšení zisku!
EMM 6
Ekonomická interpretace duality 3
Konkrétně:
• jednotka 1. zdroje (rýže) se podílí na dalším zisku hodnotou   yl = 666,67 Kč
• y2 = 0 znamená, že se 2. zdroj (pšenice) na dalším ev. zisku přímo nepodílí. Tento zdroj není plně využit => jeho zvýšení o jednotku nezpůsobí zvýšení hodnoty účelové funkce (tj. zvýšení zisku)
• jednotka 3. zdroje (vločky) se podílí na dalším zisku hodnotou y3 = 14 000 Kč (stínová cena)
EMM 6
Ekonomická interpretace duality 4
• Otázka: Jak se změní hodnota účelové funkce (zisk), jestliže se kapacita rýže zvýší o jednotku?
• Odpověď: Vzroste o hodnotu příslušné duální proměnné yx = 2000/3 (ověřte v Excelu - Řešiteli!)
• y2 = 0 => změna kapacit u 2. zdroje nemá na výsledný zisk žádný vliv. SKUTEČNĚ???!!!
• Kdyby kapacita pšenice (2. zdroj) výrazně poklesla (o kolik?), stala by se pak nedostatkovou a to by jistě celkový zisk ovlivnilo => hodnoty duálních proměnných je nutné uvažovat jen
v rámci intervalů stability jednotlivých zdrojů!
EMM 6
Dopravní problém LP
Dodavatelé     Doprava zboží - dopravní cesty Odběratelé
Di
D2
Dm
O2
Ch
EMM 6
Ekonomický a matematický model dopravního problému (DP)
Prvky DP:
• m dodavatelů (výrobců, zdrojů ):    Dx, D2, ...,Dm
• n odběratelů (spotřebitelů, skladů): Ox, 02, ...,On
• kapacity jednotlivých dodavatelů:
• požadavky odběratelů: bl,b2,...,bn
• náklady na přepravu jedné jednotky zboží
z místa zdroje D{ do odběratelského místa 0}: cř>
Cíl řešení DP:
• Naplánovat objemy přepravy x- mezi Di a Oj tak, aby byly uspokojeny požadavky všech dodavatelů i odběratelů a celkové přepravní náklady byly minimální!
EMM 6
Matematický model DP 1
Dodavatelé	Odběratelé				Kapacity dodavatelů
	o,	o2	• • •		
		C12 X12	• • • • • •	X\n	ax
	C2l	C22 X22		C2n X2n	
•  • •	• • •	• • •	• • •	• • •	• • •
Dm	Xm\	Cm2 Xm2	• • • • • •	r mn x mn	
Požadavky odběratelů		b2	• • •	K	V a. i*, A
Matematický model DP 2
• Rozlišujeme:
• Vyrovnaný dopravní problém
2>,=2><
• Nevyrovnaný dopravní problém
Každý nevyrovnaný DP lze převést na vyrovnaný!
EMM 6
Převod nevyrovnaného DP na
vyrovnaný DP
... při převisu nabídky:
• přidáme do modelu fiktivního odběratele Op
jehož požadavek bf se bude rovnat danému přebytku, tj.
bf=Hai-HbJ
... při převisu poptávky:
• doplníme model o fiktivního dodavatele Df,
jehož kapacita afse bude rovnat chybějícímu množství, tj.
ar =HbJ-Hai
• Dopravní náklady od fiktivního dodavatele a k fiktivnímu odběrateli jsou nulové !
Převod nevyrovnaného DP na vyrovnaný DP: Příklad
Dodavatelé	Odběratelé			Kapacity
		02	o3	dodavatelů
Dl	10	13	6	100
D2	15	18	10	150
D3	8	12	11	300
Požadavky odběratelů	130	210	160	550 500
Převod nevyrovnaného DP na vyrovnaný DP: Příklad - řešení
Dodavatelé	Odběratelé				Kapacity dodavatelů
		o2		Of	
A	10	13	6	0	100
D2	15	18	10	0	150
D3	8	12	11	0	300
Požadavky odběratelů	130	210	160	50	550 550
EMM 6
Matematický model (vyrovnaného)
DP
Minimalizovat
m n
za podmínek
n
Yjxij=ai   i = h2,...,m,
m
i=i
x, > 0.
EMM 6
Matematický model (nevyrovnaného)
DP: 2>,>E
a
Minimalizovat
m n
Z — 7   7 C X
za podmínek
n
m
2*y-*/   7 = 1,2...., n,
i=i
**/ * 0.
EMM 6
Řešení vyrovnaného DP
DP má vždy optimální řešení!
	Nalezení počátečního přípustného řešení			
				
	Test optimality: Je nalezené		ANO	Konec
	reseni optimální?			
		NE		
	Výpočet nového přípustného řešení (spec. Simplex, metoda)			
EMM 6
Nalezení počátečního řešení:
Metoda severozápadního rohu - SZR
Dodavatelé	Odběratelé				Kapacity dodavatelů
	Oi	o2		Of	
Di	10 100	13	6	0	100
D2	i 15 30 ->	18 120	10	0	150
D3	8	•l 12 90->	11 160 ->	0 50	300
Požadavky odběratelů	130	210	160	50	550 550
Nalezení optimálního řešení: speciální Simplexová metoda (Excel-Řešitel)
Pokud at a ^ jsou celá čísla, je i optimální řešení celočíselné, tj. xt] jsou celá čísla EMM6
DP Příklad: Optimální řešení
Excel - Řešitel
c =						c'x =	
10		13	6	0		4960	
15		18	10	0			
8		12	11	0			
'i							ai =
0		40	60	0	100		100
0		0	100	50	150	—	150
130		170	0	0	300		300
130		210	160	50			
bi =			—				
130		210	160	50			
EMM 6
Přiřazovací problém - speciální DP
Přiřadit n objektů na n aktivit tak, aby se maximalizoval celkový užitek:
Maximalizovat    z = yycx
1=1 7=1
n n
za podmínek       IX=1 *=i>2,...,«, IX=1 7=^2....,«,
xtJ > 0.
Cý - dílčí užitek z přiřazení objektu i na aktivitu 7 xy = 1 pokud objekt / se přiřadí na aktivitu j, xti = 0 jinak
EMM 6
Přiřazovací problém: Příklad 4
Cy - užitek (body) z přiřazení i na j
Objekty	Aktivity			Přiřazené objekty
		A2	A3	
ox	10 0	13 1	6 0	1
02	15 1	18 0	10 0	1
03	8 0	12 0	11 1	1
Přiřazené aktivity	1	j EMM	61	3 3
Přiřazovací problém: Příklad 4
Řešení Excel - Řešitel
c„ =						c'x =
10		13	6			39
15		18	10			
8		12	11			
						ai =
0		1	0	1		1
1		0	0	1	—	1
0		0	1	1		1
1		1	1			
bi =			—			
1		1	1			
DP PP.xIs
EMM 6