Úvod. Matematická ekonomie 1. Jan Zouhar. 20. zá í 2011

Úvod Matematická ekonomie 1

Jan Zouhar

20. zá°í 2011

Obsah

1

Organizace kurzu

2

Nápl¬ kurzu

3

Motiva£ní p°íklad na úvod

4

Úvod do matematického programování

5

Úvod do lineárního programování

6

Základní pojmy LP a jejich gracká interpretace

Matematická ekonomie 1: Úvod

snímek 2/36

Obsah

1

Organizace kurzu

2

Nápl¬ kurzu

3


4


5


6



snímek 3/36

Vyu£ující

Garant kurzu, p°edná²ející a zkou²ející: Prof. Ing.

Josef Jablonský,

e-mail:

[email protected]

KH:

st°eda 13:0015:00,

CSc.

NB436 (VE, iºkov)

Druhý p°edná²ející a zkou²ející: Ing.

Jan Zouhar,

e-mail: KH:

Ph.D.

[email protected] pond¥lí 16:0017:30, NB431 (VE, iºkov) st°eda 10:3012:00,


NB431 (VE, iºkov)

snímek 4/36

Dal²í administrativní informace

Dal²í administrativní informace dodá prof. Jablonský na p°í²tí p°edná²ce. Ode mne uº snad jen. . .

Doporu£ená literatura: Jablonský, J.: Opera£ní výzkum. Praha: Professional publishing, 2003. Pozor, neobsahuje v²e!


snímek 5/36

Obsah

1

Organizace kurzu

2

Nápl¬ kurzu

3


4


5


6



snímek 6/36

Pár slov o kurzech Matematická ekonomie 1 a 2 kurzy nazvané Matematická ekonomie mívají na r·zných oborech zcela r·zný obsah tento kurz: skoro nic spole£ného s obecnou ekonomií (bohudík?) viz kurzy mikro/makroekonomie zam¥°ení na vyuºití matematických model· p°i rozhodovacích problémech v ekonomické (podnikové) praxi dle sylabu (pro Matematickou ekonomii 1 i 2): úvod do vybraných model· a metod pro ekonomické rozhodování nejblíºe v¥dnímu oboru nazývanému

opera£ní výzkum

(OV)

anglická synonyma:

operations (nebo operational) research management science decision science Matematická ekonomie 1: Úvod

snímek 7/36

Opera£ní výzkum Nástroje studované a vyuºívané v rámci opera£ního výzkumu: optimalizace pravd¥podobnost a statistika teorie graf· teorie front simula£ní modely N¥které typické aplika£ní oblasti: optimalizace produk£ních systém· optimalizace v logistice podpora rozhodování p°i °ízení projekt· modely °ízení zásob modely hromadné obsluhy


snímek 8/36

Opera£ní výzkum Nástroje studované a vyuºívané v rámci opera£ního výzkumu: optimalizace pravd¥podobnost a statistika teorie graf· teorie front simula£ní modely N¥které typické aplika£ní oblasti: optimalizace produk£ních systém· optimalizace v logistice podpora rozhodování p°i °ízení projekt· modely °ízení zásob modely hromadné obsluhy


snímek 8/36

Zam¥°ení kurzu Matematická ekonomie 1 V¥t²inu semestru se budeme zabývat nejpropracovan¥j²í optimaliza£ní technikou

lineárním programováním

(LP):

má jen málo spole£ného s programováním (v IT pojetí) v praxi nejpouºívan¥j²í OV technika (podle jednoho výzkumu pouºívá aº 80% rem, které vyuºívají n¥jaké matematické modely pro podporu rozhodování) dobrá dostupnost SW pro °e²ení úloh znalost LP dobrým odrazovým m·stkem pro sloºit¥j²í optimaliza£ní modely a metody Ke konci semestru p°ejdeme k jistému roz²í°ení ke

celo£íselnému lineárnímu programování

smí²enému

(mixed integer linear

programming, MILP)


snímek 9/36

Sylabus kurzu 1

Ekonomické rozhodování úvod

2

Formulace úloh mat. programování, typické úlohy LP

3

Základní pojmy LP a gracké °e²ení úloh LP

4

Simplexová metoda podstata algoritmu

5

Dvoufázová simplexová metoda

6

Dualita v úlohách LP

7

Stabilita °e²ení úloh LP

8

Postoptimaliza£ní analýza

9

Distribu£ní úlohy LP

10

Dopravní problém a jeho °e²ení

11

P°i°azovací a okruºní dopravní problém

12

Celo£íselné programování formulace typických úloh

13

Metody se£ných nadrovin a metody v¥tvení a mezí


snímek 10/36

Obsah

1

Organizace kurzu

2

Nápl¬ kurzu

3


4


5


6



snímek 11/36

P°íklad

Koktejly

Recepty:

Zásoby:

Mojito

Cuba libre

4 cl kubánského rumu 1 dl vody 8 kostek ledu (t°í²´) 1/2 limetky 1 lºi£ka cukru (t°tinového) 3 lístky £erstvé máty

8 cl kubánského rumu 2 dl Coca-coly 2 kostky ledu 1/4 limetky

1 l kubánského rumu, 2 l Coca-coly, 120 kostek ledu (3 plata 8 ks limetek;

po 40),

dostatek cukru, máty a vody Cíl: Namíchat z níºe uvedených zásob co nejvíce koktejl· (jde o celkový po£et, je t°eba se drºet p°esn¥ recept·). N¥jaké tipy? Matematická ekonomie 1: Úvod

snímek 12/36

P°íklad

Koktejly

(pokra£ování)

Poznámky k p°íkladu: podobné úlohy lze °e²it i metodou pokus-omyl (a v praxi tomu tak bohuºel £asto bývá) o získaném °e²ení se v²ak nedá obecn¥ °íci nic dobrého p°edev²ím nevíme, zda je nalezené °e²ení nejlep²í moºné, tj. optimální jinou moºností je sestrojit po°ádný matematický model rohodovacího problému a najít opravdu optimální °e²ení v tomto p°ípad¥ se bude jednat o úlohu LP


snímek 13/36

Obsah

1

Organizace kurzu

2

Nápl¬ kurzu

3


4


5


6



snímek 14/36

Matematické programování Denice (úloha matematického programování) Nech´ jsou dány: 1

mnoºina X , ozna£ovaná jako mnoºina p°ípustných °e²ení,

2

funkce f

: X → R,

ozna£ovaná jako ú£elová funkce.

Úlohou matematického programování (ÚMP) pak ozna£ujeme problém nalezení bu¤ minima nebo maxima funkce f na mnoºin¥ X .

V p°íkladu Koktejly: X v²echny kombinace po£tu Mojito a Cuba libre, které lze p°i daných zásobách namíchat (nap°. (5,5), (10,1) apod.) f

celkový po£et koktejl· p°i daném po£tu Mojito a Cuba libre (nap°. 10, 11 apod.)


snímek 15/36

Matematické programování

(pokra£ování)

P°edchozí denice je trochu moc obecná X je libovolná abstraktní mnoºina. Zpravidla vyºadujeme, aby X byla. . . 1

podmnoºina n-rozm¥rného euklidovského prostoru, tj. X

2

vymezená pomocí soustavy rovnic a/nebo nerovností

⊆R

n

Standardní vymezení ÚMP Uvaºujme n¥jaké funkce f

, g1 , g2 , . . . , g : R → R . n

Úlohu

m

matematického programování lze zadat ve tvaru maximalizovat za podmínek

f (x1 , x2 , . . . , xn )

≤ 0, ) ≤ 0,

g1 (x1 , x2 , . . . , xn ) g2 (x1 , x2 , . . . , xn

(1)

. . .

≤ 0, (x1 , x2 , . . . , x ) ∈ R .

gm (x1 , x2 , . . . , xn )

n

n


snímek 16/36

Poznámky k standardnímu vymezení ÚMP Zápis chápeme tak, ºe v²echny omezující podmínky musí být spln¥ny sou£asn¥. Fakt, ºe jsem v (1) zvolil zrovna maximalizaci ú£elové funkci, není nijak limitující: minimalizovat f je totiº totéº, co maximalizovat

−f .

Stejn¥ tak neubírá zápisu na obecnosti to, ºe jsem v²echny omezující podmínky vyjád°il ve tvaru nerovností: rovnici g (x1 , x2 , . . . , xn )

=0

lze nahradit dv¥ma nerovnostmi g (x1 , x2 , . . . , x ) ≤ 0, −g (x1 , x2 , . . . , x ) ≤ 0. n

n


snímek 17/36

Poznámky ke zna£ení Matematik·m zpravidla p°ipadá obecný zápis ÚMP v podob¥ (1) p°íli² upovídaný. Nabízí se psát: maximalizovat za podmínek

f (x1 , x2 , . . . , xn )

≤ 0, (x1 , x2 , . . . , x ) ∈ R .

gi (x1 , x2 , . . . , xn )

i

= 1, 2, . . . , m ,

n

n

x = (x1 , x2 , . . . , x

Lze také zavést vektor (£i chcete-li, n-tici) psát maximalizovat za podmínek

f

(x ) x ) ≤ 0, x ∈R .

gi (

i

n

)

a

= 1, 2, . . . , m ,

n

nebo nejstru£n¥ji (ale pon¥kud mén¥ p°ehledn¥) max{f

(x ) |


x ∈R

n

&

x ) ≤ 0,

gi (

i

= 1, 2, . . . , m}. snímek 18/36

Klasikace ÚMP

Podle toho, jaké dodate£né poºadavky klademe na funkce f a gi , rozli²ujeme r·zné t°ídy ÚMP, které se zna£n¥ li²í co do sloºitosti pouºívaných výpo£etních technik: lineární programování kvadratické programování konvexní programování nelineární programování . . . a dal²í Zdaleka nejjednodu²²í t°ídou je lineární programování; spadá sem nap°. matematický model pro p°íklad Koktejly.


snímek 19/36

P°íklad

Koktejly

Recepty:

Zásoby:

Mojito

Cuba libre

4 cl kubánského rumu 1 dl vody 8 kostek ledu (t°í²´) 1/2 limetky 1 lºi£ka cukru (t°tinového) 3 lístky £erstvé máty

8 cl kubánského rumu 2 dl Coca-coly 2 kostky ledu 1/4 limetky

1 l kubánského rumu, 2 l Coca-coly, 120 kostek ledu (3 plata 8 ks limetek;

po 40),

dostatek cukru, máty a vody Cíl: Namíchat z níºe uvedených zásob co nejvíce koktejl· (jde o celkový po£et, je t°eba se drºet p°esn¥ recept·). N¥jaké tipy? Matematická ekonomie 1: Úvod

snímek 20/36

P°íklad

Koktejly jako ÚMP

O £em rozhodujeme? O po£tu koktejl· Mojito a Cuba libre

→

to budou na²e dv¥ prom¥nné.

eho chceme docílit? Co nejv¥t²ího po£tu koktejl·, tzn. maximalizujeme výraz Mojito

+ Cuba

libre.

Co nás omezuje? Na²e zásoby. Nap°. nesmí dojít kubánský rum jeho celková spot°eba nesmí p°esáhnout disponibilní mnoºství: 4 Mojito

|

+ 8 Cuba {z

libre

}

celková spot°eba rumu (cl)

≤

100 |{z}

zásoba (cl)

Analogicky pro zbylé suroviny. Dále z°ejm¥ musí být Mojito, Cuba libre


≥ 0. snímek 21/36

P°íklad

Koktejly jako ÚMP

(pokra£ování)

Celkem máme:

maximalizovat za podmínek

Mojito

+ Cuba

libre

1/4 Cuba libre

≤ ≤ ≤ ≤

8,

Mojito, Cuba libre

≥

0.

4 Mojito

+

8 Cuba libre 2 Cuba libre

8 Mojito 1/2 Mojito

Úkol: Najd¥te funkce f

+ +

2 Cuba libre

, g1 , g2 , . . . , g

m

100, 20, 120,

tak, aby zápis ÚMP

ve tvaru (1) odpovídal matematickému modelu pro p°íklad Koktejly.


snímek 22/36

Postup p°i pouºití optimaliza£ního modelu Implementace Rozpoznání problému

Ekonomický model

Matematický model

Cíl analýzy

Ú£elová funkce

(zisk, náklady)

Procesy (výroba, p°eprava)

initele (technologie)


Výpo£et a verikace

Prom¥nné Omezující podmínky

snímek 23/36

Obsah

1

Organizace kurzu

2

Nápl¬ kurzu

3


4


5


6



snímek 24/36

Denice úlohy lineárního programování (ÚLP) Zobecníme-li matematický model z p°íkladu Koktejly, dostaneme obecný zápis úlohy lineárního programování (ÚLP). Budeme pouºívat následující zna£ení pro prom¥nné a parametry: m po£et tzv. vlastních omezení n po£et prom¥nných xj j -tá prom¥nná aij strukturní koecient v i -tém omezení u j -té prom¥nné bi pravá strana i -té omezující podmínky cj cenový koecient (tj. koecient v ú£elové funkci) u j -té prom¥nné


snímek 25/36

Denice úlohy lineárního programování (ÚLP)

(pokra£ování)

Denice (standardní maximaliza£ní ÚLP) M¥jme dány reálné koecienty aij , bi a cj pro i j

= 1, 2, . . . , n.

= 1, 2, . . . , m

a

Úlohou lineárního programování rozumíme problém


z

= c1 x1 + c2 x2 + . . . + c

xn

+ a12 x2 + . . . + a1 a21 x1 + a22 x2 + . . . + a2

n

xn

n

xn

n

a11 x1

≤ b1 , ≤ b2 , . . .

am1 x1

+a

m

2 x2

+ ... + a

mn

xn

≤b ,

xj

≥ 0,

m

j

= 1, . . . , n ,

kde x1 , x2 , . . . , xn jsou reálné prom¥nné.


snímek 26/36

Denice úlohy lineárního programování (ÚLP)

(pokra£ování)

Dv¥ p°irozené otázky: Pro£ to ozna£ení lineární? Jak p°esn¥ souvisí denice ÚLP s denicí ÚMP? Odpov¥¤ na ob¥ otázky lze snadno vy£íst z následující denice:

Denice (lineární funkce více prom¥nných) : R → R. n

M¥jme funkci f vyjád°it na

n

R

ekneme, ºe f je lineární, pokud lze f

p°edpisem

f (x1 , x2 , . . . , xn )

= c1 x1 + c2 x2 + . . . + c

n

xn

pro n¥jaká reálná £ísla c1 , c2 , . . . , cn .

Poznámka: Máte-li v tomto semestru lineární algebru, srovnejte p°edchozí denici s pojmem homomorsmu. Matematická ekonomie 1: Úvod

snímek 27/36

Poznámky k denici ÚLP 1

A£koli v denici jsme úlohu zavedli jako maximaliza£ní, budeme n¥kdy uvaºovat i úlohy minimaliza£ní lze je ostatn¥ mezi sebou p°evád¥t:

Pozorování Minimalizovat z je totéº, jako maximalizovat

2

−z .

Není rovn¥º limitující, ºe se v denici vyskytují pouze omezení typu ≤; snadno bychom z nich p°ípadn¥ vytvo°ili omezení typu ≥ nebo =:

Pozorování g (x )

≥ b ⇐⇒ −g (x ) ≤ −b

g (x )

= b ⇐⇒


i

i

g (x )

i

≤ b & − q (x ) ≤ −b i

i

snímek 28/36

Poznámky k denici ÚLP 3

(pokra£ování)

Budeme proto za ÚLP automaticky povaºovat úlohy maximaliza£ní i minimaliza£ní, kde se vyskytují omezení libovolného typu ( ≤, ≥ =); podstatné je, ºe v ú£elové funkci i omezeních jsou p°ítomny pouze lineární funkce prom¥nných

4

Zápis matematického modelu je op¥t p°íli² upovídaný. Lze jej zestru£nit bu¤ pouºitím suma£ního operátoru a indexace omezení: n

maximalizovat

z

=

X j

cj xj

=1

n

za podmínek

X j

aij xj

i

i

= 1, . . . , m,

≥ 0,

j

= 1, . . . , n,

=1 xj


≤b,

snímek 29/36

Poznámky k denici ÚLP

(pokra£ování)

. . . nebo pouºitím maticového zápisu. Ozna£íme-li



a

··· ···

a1n

. . .

..

. . .

am 2

···

a11

a12

a A =  21 . . .

a22

am 1

c> = (c1 , c2 , . . . , c

n

a2n  

.

),



 , 

b

b1

 



 b2    =  . ,  .. 

x1

x

x2    =.  .. 

bm

amn

xn

m·ºeme ÚLP vyjád°it ve tvaru


c>x Ax ≤ b, x ≥0

z

=

nebo je²t¥ úsporn¥ji jako

c>x | Ax ≤ b

max{ Matematická ekonomie 1: Úvod

&

x ≥ 0}. snímek 30/36

Poznámky k denici ÚLP

5

(pokra£ování)

(Terminologická poznámka) Omezení, kde se vyskytují strukturní koecienty aij , se nazývají vlastní omezení, omezení typu xj

≥0


ozna£ujeme jako podmínky nezápornosti.

snímek 31/36

Maticový zápis p°íkladu

Koktejly

V p°íkladu Koktejly jsme se dopracovali k následujícímu matematickému modelu:


Mojito

+ Cuba

libre

1/4 Cuba libre

≤ ≤ ≤ ≤

8,

Mojito, Cuba libre

≥

0.

4 Mojito

+

8 Mojito

+ +

8 Cuba libre 2 Cuba libre

1/2 Mojito

2 Cuba libre

100, 20, 120,

A, vektor pravých b, vektor cenových koecient· c a vektor prom¥nných x .

Úkol: Zapi²te matici strukturních koecient· stran


snímek 32/36

Maticový zápis p°íkladu

Koktejly

(pokra£ování)

Výsledek:



4

8

 A = 

0

2

8

2

1 2

1 4

/

a

c> = [ 1

/

  , 



100

b



 20   = 120 ,

x=

Mojito

Cuba libre

8

1 ].


snímek 33/36

Obsah

1

Organizace kurzu

2

Nápl¬ kurzu

3


4


5


6



snímek 34/36

Mnoºina p°ípustných °e²ení p°i 2 prom¥nných

P°ípustné °e²ení Bude dopn¥no. Optimální °e²ení Bude dopln¥no. Gracké znázorn¥ní omezení: viz tabule.


snímek 35/36

Ekvivalentní soustava rovnic, základní °e²ení ÚLP

Bude dopln¥no.


snímek 36/36

Úvod. Matematická ekonomie 1. Jan Zouhar. 20. zá í 2011

Recommend Documents