EMM4
1
Ekonomicko-matematické metody 4
Mgr. Jiří Mazurek, Ph.D.

EMM4
2
Konvexní a konkávní funkce v R1…
grafy
„do V“
 konvexní fce (nikoliv ryze!)           ryze konvexní fce (parabola)
tyto funkce nejsou konvexní!!!

EMM4
3
Konvexní a konkávní funkce v R1
konkávní fce (nikoliv ryze!)   ryze konkávní funkce

EMM4
4
    x(1)         x = lx(1) + (1-l)x(2)  x(2)
konkávní fce (nikoliv ryze!)   ryze konkávní funkce
f(x(1))
f(x(2))
f(x)
lf(x(1)) + (1-l)f(x(2))
Konvexní a konkávní funkce
Jak to vyjádřit matematicky?

EMM4
5
Konvexní a konkávní funkce
Jak to vyjádřit matematicky?
• Funkce  f je konvexní na konvexní množině X Ì Rn
• jestliže pro každé dva body x(1) , x(2) z X   a pro
• každá dvě čísla l1³ 0 , l2 ³ 0 taková že  l1 + l2 = 1 platí:
•
• f(l1x(1) + l2x(2) ) £ l1 f(x(1) ) + l2 f(x(2) ).
•
•Anebo ekvivalentně:
•… pro každé číslo 0 ≤l ≤ 1 , platí:
•
• f(lx(1) + (1-l)x(2) ) £ l f(x(1) ) + (1-l) f(x(2) ).
•
(konkávní)
(³)
(³)

EMM4
6
Konvexní a konkávní funkce …
• Funkce  f je  ryze konvexní na konvexní množině X Ì Rn
• jestliže pro každé dva body x(1) , x(2) z X   a
• každá dvě čísla l1>0 , l2 >0 taková že  l1 + l2 = 1 platí:
•
• f(l1x(1) + l2x(2) ) < l1 f(x(1) ) + l2 f(x(2) )
•
• Zřejmě platí: Funkce f je na XÌ Rn konkávní                   (resp. ryze konkávní)
• jestliže je funkce - f konvexní (resp. ryze konvexní)
•
• Poznámka:   Zobecnění pro funkce n proměnných
(ryze konkávní)
(>)

EMM4
7
Konvexní a konkávní funkce v R2
konkávní fce (nikoliv ryze!)   ryze konkávní funkce

EMM4
8
Konvexní a konkávní funkce …
„Lokální extrémy jsou zároveň globální!!!“
• Věta 3: Jestliže x0 je lokální maximum funkce f(x) na X
• a funkce f(x) je konkávní na X,
• potom x0 je globálním maximem funkce
• f(x) na X,   tj. x0 = arg max f(x)
•      xÎ X
• Je-li f(x) navíc ryze konkávní na X,
• potom x0 je jediným globálním maximem.
•
•Poznámka 1: Analogicky pro lokální minimum a konvexní funkci…
•Poznámka 2: Pozor, neplatí pro lokální maximum                  a konvexní funkci, resp. lok.
minimum a konkávní funkci!!!
•

EMM4
9
Příklad k Větě 3:
není konkávní             konkávní fce ryze konkávní fce funkce
lokální max        globální max
X

EMM4
10
Konvexní a konkávní funkce …
• Věta 4: gj(x) je konvexní funkce na X Ì Rn, bj Î R1
• potom (omezující podmínka)
•
• Zj = {xÎ X | gj(x) £ bj}  je konvexní množina
•
• Poznámka 1:   Průnik konvexních množin je konvexní množina! (Více omezujících podmínek!)
•
• Poznámka 2:   Lineární funkce je zároveň konvexní i konkávní! (nikoliv ryze!!!)
•

EMM4
11
 Jak poznáme, že je
funkce konvexní v X ?
• v R1 (matematika 1. ročník) :  f ´´(x) > 0 pro " x ÎX
•
• v Rn :  pozor!!! parciální derivace:
•
• H = {hij }  =                  = {Ñ2f(x)}
•
•
• Hessova matice (Hessián) je pozitivně definitní (PD)
•
•Sylvestrova podmínka:
•Jestliže všechny hlav. subdeterminanty jsou kladné, potom H je PD.

EMM4
12
Konvexní a konkávní funkce …
• Věta 5: Funkce  f(x) je konvexní na X , jestliže
• všechny hlavní subdeterminanty
• Hessovy matice jsou kladné
• ( pro všechna x Î X Ì Rn )
•
• Věta 6: f1(x) , f2(x) jsou konvexní funkce na
• množině X, a1, a 2 - nezáporné konstanty (tj.³ 0 ),
• potom funkce
• g(x)  = a1.f1(x) + a2.f2(x)
• je konvexní funkce na X Ì Rn

EMM4
13
Příklad 1:
• f(x,y) = 2x2 + xy2 + 3y3           Ñf(x)  = 4x + y2, 2xy +9y2
•
•
•
• H = {Ñ2f(x)} =
•
f  je konvexní na   X = {(x,y)| 2x +18y – y2 > 0} – vnitřek paraboly
1.det [4] = 4 > 0
2.
2.det                    = 8x + 72y – 4y2   > 0
3.

EMM4
14
Příklad 1 – pokrač.

EMM4
15
Úloha matematického programování
tzv. úloha (1) , (2)
• f(x1, x2, ... ,xn) ®  MAX; (1)
•
• za podmínek
•
• g1(x1, x2, ... ,xn) £  b1
• g2(x1, x2, ... ,xn) £  b2
•
• …………………….. X (2)
• gm(x1, x2, ... ,xn) £ bm                                          (mohou chybět)
•            x = (x1, x2, ... ,xn) ³ 0
účelová funkce
omezující podmínky
podmínky nezápornosti

EMM4
16
Maximalizace užitku spotřebitele
při důchodovém omezení
•
• f(x1, x2, ... ,xn) ® MAX;
•za podmínek
• p1x1+ p2x2+…+ pnxn  £  b ,
•       xj ≥ 0 , j =1,2,…,n
•
•f – funkce užitku (konkávní)
•n – počet statků
•pi – cena jednotky i-tého statku
•xi – množství i-tého statku
•b - důchodové omezení spotřebitele (b > 0)

EMM4
17
Příklad: Maximalizace užitku spotřebitele
při důchodovém omezení

EMM4
18
Úloha matematického programování ...
• f  je konkávní,  gi  jsou konvexní funkce na X Ì Rn :
• Potom (1), (2) je úlohou konvexního programování
•
• x = (x1, x2, ... ,xn) ÎX je přípustné řešení úlohy (1), (2)
• jestliže splňuje nerovnosti (2)
• x* = (x1*, x2*, ... ,xn*) ÎX je optimální řešení úlohy  (1), (2)
• jestliže je zároveň přípustné a  x* = arg max f(x)
• tj. pro všechna xÎX platí:          f(x) ≤ f(x*)
•
• Speciální případ: f , gi  - lineární funkce, tj.
• f(x1, x2, ... ,xn) = c1x1  + c2x2  + ... + cnxn
• gm(x1, x2, ... ,xn) = a1ix1  + a2ix2  + ... + anixn - bi
●
●
●

EMM4
19
Teorie sedlových bodů
• Lagrangián úlohy (1), (2):
•
• F(x,y) = f(x) +
• (Nezáporný) sedlový bod Lagrangiánu úlohy (1), (2):
•
• (   ,   ) přičemž     ³ 0 ,    ³ 0 a platí:
•
• F( x,   )  £  F(    ,   )  £  F(   , y) (3)
•
• pro všechna x ³ 0, y ³ 0
•
• Poznámka:
• Pozor!!!    ,    jsou vektory, tj.    = (   1,   2, ...,   n)
• = (   1,   2, ...,   m)
●
●
●
Lagrangeovy multiplikátory

EMM4
20
Teorie sedlových bodů
Sedlový bod funkce f(x,y) = -x2y2
Sedlový bod

EMM4
21
Teorie sedlových bodů
• Věta 7:
• Jestliže    ,    je nezáporný sedlový bod Lagrangiánu úlohy (1), (2),
• tj.     ³ 0,     ³ 0 ,
•
• potom    =                  , tj.    je optimálním řešením
•
• úlohy (1), (2)
•
•
•Poznámka 1: Sedlový bod je optimálním řešením úlohy (1),(2)
•
•
•Poznámka 2: Když      je optimálním řešením úlohy (1), (2),
•
• potom nemusí ještě existovat       takový, že
•
•   ,      je nezáporný sedlový bod Lagr.  (1), (2)

EMM4
22
Teorie sedlových bodů
Postačující podmínka pro existenci sedlového bodu

EMM4
23
Teorie sedlových bodů
(tzv. Kuhn-Tuckerův teorém )
• Věta 9:
• f je konkávní, gj jsou konvexní diferencovatelné funkce
• potom  (   ,   ) je sedlovým bodem Lagrangiánu F úlohy (1), (2), právě když platí:
• (*) Ñx F(   ,   ) ≤ 0 Ñy F(   ,   ) ≥ 0
• ÑxF(   ,   ) = 0 ÑyF(   ,   ) = 0
•       ³ 0       ³ 0
• tzv. Kuhn - Tuckerovy podmínky
•
• Poznámka:
• K.-T. podmínky umožňují nalézt sedlový bod řešením soustavy nerovností (*), což je zobecněná
podmínka „nulovosti gradientu“

EMM4
24
Příklad 2: Výroba „racio“ pokrmů
(úloha lineárního/kvadratického programování)
•(1) Jednotkový zisk nezávisí na množství produkce:
•z = 2000x1 + 3000x2 ® MAX;   „zisk“
•za podmínek
• 0,9x1 + 0,3 x2  £  270  „rýže“
•              0,5 x2  £ 100   „pšenice“
• 0,1x1 + 0,2 x2   £  60   „vločky“
• x1 ³ 0, x2 ³ 0
•
•(2) Jednotkový zisk roste s růstem produkce:
•z = (2000 + x1) x1 + (3000 +8x2) x2 =
•   = 2000 x1 + 3000 x2 + x12 + 8x22 ® MAX;   „zisk“
•za podmínek (stejných!)
•

EMM4
25
Příklad 2 - pokrač.1:
 (úloha nelineárního - kvadratického programování)
•z = 2000 x1 + 3000 x2 + x12 + 8x22 ® MAX;  (1*)
•za podmínek
• 0,9x1 + 0,3 x2  £  270  „rýže“
•              0,5 x2  £ 100   „pšenice“ (2*)
• 0,1x1 + 0,2 x2   £  60   „vločky“
• x1 ³ 0, x2 ³ 0
•…to je úloha nekonvexního (kvadratického) programování
•
•Lagrangián úlohy (1*), (2*):
•F(x1, x1, y1, y2, y3) =  2000 x1 + 3000 x2 + x12 + 8x22
•  + y1(270 - 0,9x1- 0,3 x2) +y2(100 - 0,5 x2) +y3(60 - 0,1x1- 0,2 x2)
•

EMM4
26
Příklad 2 - pokrač.2:
•Lagrangián úlohy (1*), (2*):
•F(x1, x2, y1, y2, y3) =  2000 x1 + 3000 x2 + x12 + 8x22                                  + y1(270
- 0,9x1- 0,3 x2)+y2(100 - 0,5 x2) +y3(60 - 0,1x1- 0,2 x2)
•
•K.T. podmínky:
•∂F/∂x1 = 2000 + 2x1 - 0,9y1 - 0,1y3 ≤ 0
•∂F/∂x2 = 3000 + 16x2 - 0,3y1 - 0,5y2 - 0,2y3 ≤ 0
•∂F/∂y1 = 270 - 0,9x1 - 0,3x2 ≥ 0
•∂F/∂y2 = 100 - 0,5x2 ≥ 0
•∂F/∂y3 = 60 - 0,1x1 - 0,2x2 ≥ 0
•xi ≥ 0, yj ≥ 0, i = 1,2. j =1,2,3.
•+ podmínky komplementarity.
•
•

EMM4
27
Příklad 2 - pokrač. 3:

EMM4
28
Příklad 2 - pokrač. 4:
•Řešení úlohy (1), (2):     x1 =  240,      x2 = 180  , z = 1020000
•
•Řešení úlohy (1*), (2*):  x1* =  200,  x2* = 200,  z* = 1 360 000
•
• y1* =      0
• y2* =  2 800
• y3* = 24 000

EMM4
29
Maximalizace užitku spotřebitele
při důchodovém omezení
•
• f(x1, x2, ... ,xn) ® MAX;
•za podmínek
• p1x1+ p2x2+…+ pnxn  £  b ,
•       xj ≥ 0 , j =1,2,…,n
•
•f – funkce užitku (konkávní)
•n – počet statků
•pi – cena jednotky i-tého statku
•xi – množství i-tého statku
•b - důchodové omezení spotřebitele (b > 0)

EMM4
30
Maximalizace užitku spotřebitele
Kuhn-Tuckerovy podmínky
•K.T. podm.: Ñx F(x, y) ≤ 0 Ñy F(x, y) ≥ 0
• xTÑxF(x, y) = 0 y ÑyF(x, y) = 0
• x ³ 0   y ³ 0
•Lagrangián:
•F(x1, x2, ... ,xn, y) = f(x1, x2,...,xn) – y (p1x1+…+ pnxn -  b)
•     F(x, y) = f(x) – y (pTx -  b)
•
•K.T. podm.:
• Ñf(x) ≤ y pT   pTx ≤ b
• xT Ñ f(x) = y pTx y pTx = y b
• x ³ 0 y ³ 0

EMM4
31
Příklad: Maximalizace užitku spotřebitele
při důchodovém omezení
•
• f(x1, x2) = x1. x2 ® MAX;
•za podmínek
• x1+ x2 £  6
• xj ≥ 0 , j =1,2.
•
•
K.T. podm.:
Ñf(x) ≤ y pT   pTx ≤ b
xT Ñ f(x) = y pTx y pTx = y b
x ³ 0 y ³ 0

EMM4
32
Příklad: Maximalizace užitku spotřebitele
při důchodovém omezení
•
• f(x1, x2) = x1. x2 ® MAX;
•za podmínek
• x1+ x2 £  6
• xj ≥ 0 , j =1,2.
•
•
K.T. podm.:
Řešení:

EMM4
33
Kuhn-Tuckerovy podmínky
a dualita v LP …
• Lagrangián k (P):
•
• F(x,y)  =    cTx + yT(b - Ax)
•
• K.T. podmínky (*) a (**):
•
• ÑxF(x,y) = c - ATy £ 0  Þ   ATy ³ c
• ÑyF(x,y) =   b - A x ³ 0  Þ A x  £  b
• xT ÑxF(x,y) = xT(c - ATy) = 0
• yT ÑyF(x,y) = yT (b – A x) = 0
• x ≥ 0 , y ≥ 0