EMM7 1
Ekonomicko-matematické
metody 7
Prof. RNDr. Jaroslav Ramík, CSc.
přednáší
doc. RNDr. David Bartl, Ph.D.
EMM7 2
Příklad: 3 účelové funkce
20,20
3
omezeníza
MIN;3),(
MAX;5),(
MAX;2),(
21
21
21213
21212
21211





xx
xx
xxxxf
xxxxf
xxxxf
X
MAX;3),( 21213  xxxxf
EMM7 3
Příklad pokrač.
x2
x1
0
f1
21 3
1
2
3
f2
f3
f1 = 2x1 + x2  x2 = - 2x1 + f1
f2 = x1 + 5x2  x2 = - 0,2x1 + f2
f3 = x1 - 3x2  x2 = 0,33x1- 0,33f3
X
VKLP.xls
x2
x1
0
f1
21 3
1
2
3
f2
f3
X
x1 x2 f1 f2 f3
2 1 5 3 -1
1 2 4 11 -5
2 0 4 2 2
Které „řešení“ je nejlepší?
EMM7 4
Vícekriteriální programování
Nelineární VKP: Základní úloha
f1(x1, x2, ... ,xn)  MAX;
f2(x1, x2, ... ,xn)  MAX;
..................................... (1) účelové funkcefk(x1,
x2, ... ,xn)  MAX; -kritéria (všechny MAX, nebo
všechny MIN)
za podmínek
g1(x1, x2, ... ,xn)  b1
g2(x1, x2, ... ,xn)  b2
............................................... (2) omezující podmínky
gm(x1, x2, ... ,xn)  bm (mohou chybět)
x = (x1, x2, ... ,xn ) - varianty - alternativy
X
EMM7 5
Příklad 1: VKNLP
20,20
3
omezeníza
;MAX3),(
;MAX5),(
;MAX2),(
21
21
21213
21212
2
21211





xx
xx
xxxxf
xxxxf
xxxxf
X
EMM7 6
Definice nedominované varianty
Nechť x(0) je přípustné řešení vyhovující omezením (2).
Řekneme, že přípustné řešení
x(1) dominuje x(0)
jestliže pro všechna kritéria j =1,…,m platí:
fj(x(1))  fj(x(0)) a alespoň pro jedno kritérium „k“ je:
fk(x(1)) > fk(x(0))
Jestliže neexistuje přípustné x(1) takové, že
x(1) dominuje x(0)
potom se x(0) nazývá
nedominovaná (Paretovská) varianta (řešení)
●
●
EMM7 7
Nedominovaná varianta
V úloze VKP obvykle není k dispozici
„optimální řešení“ x* v tom smyslu, že
pro všechna kritéria fj
a všechna přípustná řešení xX platí:
fj(x*) ≥ fj(x)
Odstraníte-li všechna dominovaná
řešení, zůstanou nedominovaná řešení!
(…stejně jich je obvykle příliš mnoho!)
EMM7 8
Příklad 1. Skalarizovaná úloha
20,20
3
omezeníza
MAX;9,00,55,1
.tj
MAX;)3(0,2)5(0,3)0,5(2
.tj
MAX;),(),(),(
21
21
2
2
21
2121
2
21
213321222111





xx
xx
xxx
xxxxxx
xxfvxxfvxxfv
X
20,20
3
omezeníza
MAX;3),(
MAX;5),(
MAX;2),(
21
21
21213
21212
2
21211





xx
xx
xxxxf
xxxxf
xxxxf
Váhy: v1 = 0,5 v2 = 0,3 v3 = 0,2
9
f1, f2, ..., fk - ryze konkávní funkce (kritéria)
g1, g2, ... ,gm - konvexní funkce
Pak platí, že: x* je nedominované (Paretovské) řešení
úlohy (1), (2), právě když existují váhy kritérií
v1, v2, ..., vk vi  0  vi = 1
takové, že x* je optimální řešení skalarizované úlohy:
 vj fj(x1, x2, ... ,xn)  MAX; (1*)
za omezení (2),
tj. 

k
i
ii
X
fv
1x
*
(x)argmaxx
●
Vztah mezi Paretovským řešením úlohy
VKP a optimálním řešením skalarizované
úlohy VKP
EMM7 10
Speciální případ: fj gi jsou lineární funkce, tj.
fj(x1, x2, ... , xn) = c1jx1 + c2jx2 + ... + cnj xn
gi(x1, x2,..., xn) = a1ix1 + a2ix2 + ... + ani xn
Vektorový tvar úlohy VKLP:
C x  MAX; tj.  MAX; (3)
za omezení
X = { x  A x  b , x  0 } (4)
●
●
Vícekriteriální lineární programování
VKLP












nknkk
nn
xcxcxc
xcxcxc
...
...
2211
1212111

11
Vícekriteriální lineární programování
VKLP
Skalarizovaný tvar úlohy VKLP:
v = ( v1, v2, ... ,vk ) – vektor vah: v1, v2, ..., vk vi  0
 vi = 1
Z vícekriteriální úlohy se skalarizací stane
jednokriteriální úloha:
vTC x  MAX; (3*)
za omezení
X = { x  A x  b , x  0 } (4)
přitom vTC x = =  
k
i
n
j
jiji xcv
1 1
 
k
i
n
j
jiji xcv
1 1
EMM7 12
Vztah mezi Paretovským řešením úlohy
VKLP a optimálním řešením
skalarizované úlohy VKLP
1. Nechť x* je nedominované (Paretovské) řešení
úlohy (3), (4), tj. úlohy VKLP.
Potom existuje vektor vah
v = ( v1, v2, ... ,vk )
takových, že x* je optimální řešení skalarizované úlohy
VKLP, tj.
(5)
2. Nechť pro x*  X a pro vektor kladných vah
v = ( v1, v2, ... ,vk ) platí (5).
Potom x* je nedominované (Paretovské) řešení úlohy
(3), (4)
vCxx
X

x
*
argmax
EMM7 13
Příklad 2. VKLP
20,20
3
omezeníza
MAX;3),(
MAX;5),(
MAX;2),(
21
21
21213
21212
21211





xx
xx
xxxxf
xxxxf
xxxxf
X
EMM7 14
Příklad 2. pokrač.
x2
x1
0
f1
21 3
1
2
3
f2
f3
f1 = 2x1 + x2  x2 = - 2x1 + f1
f2 = x1 + 5x2  x2 = - 0,2x1 + f2
f3 = x1 - 3x2  x2 = 0,33x1- 0,33f3
X
x1
* = (x1
*, x2
* ) = (2 , 1) x2
* = (1 , 2) x3
* = (2 , 0)
Paretovská řešení
(červená)
VKLP.xls
x2
x1
0
f1
21 3
1
2
3
f2
f3
X
EMM7 15
Minimaxová optimalizace
min{ f1(x), f2(x),…, fk(x)}  MAX; (6)
za omezení
g1(x)  b1
………… X
gm(x)  bm
x = (x1, x2, ... ,xn)
Optimální řešení úlohy (6) je nedominované
(Paretovské)
Maximalizuje se nejhorší (minimální) hodnota:
EMM7 16
Minimaxová optimalizace:
ekvivalentní tvar
w  MAX; (7)
za omezení
f1(x)  w
…………
fk(x)  w
x = (x1, x2, ... ,xn) X
Přidáme novou - umělou proměnnou w
(nejmenší hodnota ze všech kritérií):
EMM7 17
Příklad 3.
20,20
3
omezeníza
MAX;3),(
MAX;5),(
MAX;2),(
21
21
21213
21212
21211





xx
xx
xxxxf
xxxxf
xxxxf
VKLP.xls
EMM7 18
Příklad 3. pokrač.
wxx
xx
wxx
wxx
wxx
w






0,20,20
3
3
5
2
omezeníza
MAX;
21
21
21
21
21
Hodnoty kritérií
současně
Optimální řešení: x* = (2 , 0)
VKLP.xls
EMM7 19
Cílové programování
• Účelové funkce (kritéria) = cílové funkce fi
• Předem jsou známy cílové hodnoty qi,
kterých mají cílové funkce dosáhnout
(nebo ke kterým se mají co nejvíce
přiblížit)
• Optimální řešení - minimalizuje součet
odchylek od cílových hodnot, tj. součet
absolutních hodnot rozdílu funkčních a
cílových hodnot
EMM7 20
Cílové lineární programování
CLP
;MIN...
1
2211 

k
i
ininii qxcxcxc
qi – zadané cílové hodnoty i-tého kritéria
Minimalizuje se součet (součet kvadrátů)
odchylek od cílových hodnot:
(8)
za omezení
A x  b , x  0
Optimální řešení (8) nemusí být nedominované!
MIN;)( 2
1
T


i
k
i
i qxc
Pozor! Není úloha LP !!
EMM7 21
Cílové lineární programování
ekvivalentní úloha
MIN;)(
1


i
k
i
i hd
za omezení
A x  b , x  0
.,...,2,1,...2211 kihqxcxcxcd iininiii 
qi – zadané cílové hodnoty
1. Minimalizuje se součet kladných hi a záporných
di - odchylek od cílových hodnot qi , resp.
hi ≥ 0, di ≥ 0
EMM7 22
Příklad 4.
20,20
3
omezeníza
MAX;3),(
MAX;5),(
MAX;2),(
21
21
21213
21212
21211





xx
xx
xxxxf
xxxxf
xxxxf
Cílové hodnoty kritérií: q1 = 3, q2 = 4, q3 = 5
EMM7 23
Příklad 4: dokončení
3,2,1,0,0
53
45
32
20,20
3
omezeníza
MIN;
3213
2212
1211
21
21
321321







ihd
hxxd
hxxd
hxxd
xx
xx
hhhddd
ii
Rozdíl mezi
hodnotami a
stanovenými cíli
X
Optimální řešení: x* = (1,222 ; 0,555)
VKLP.xls
EMM7 24
Souhrn: 3 metody řešení VKLP
• Metoda váženého součtu: váhy mohou představovat
relativní významnosti (důležitosti) jednotlivých kritérií
• Metoda minimaxu: realizuje pesimistické
kompromisní řešení – najde nejlepší z možných špatných
situací
• Cílové programování: nejpoužívanější metoda –
minimalizuje součet odchylek od zadaných cílů:
Např. minimalizace (maximalizace) odchylek od
ideálních (bazálních) hodnot jednotlivých kritérií
(Předchází řešení úloh LP s individuálními kritérii!)
Všechny úlohy lze řešit v Excelu – Řešiteli (semináře)