Ekonomicko - matematické metody I (cvičení)
Jiří Polanský
Department of Applied Mathematics and Computer Science
Faculty of Economics and Administration
Masaryk University
Brno
Jiří Polanský (ESF MU) EMM I podzim 2007 1 / 1
Content
Jiří Polanský (ESF MU) EMM I podzim 2007 2 / 1
Úvodní informace
Jiří Polanský (ESF MU) EMM I podzim 2007 3 / 1
Úvodní informace
Úvodní informace
Jiří Polanský
KAMI, 6. patro, dveře č. 646
polansky@econ.muni.cz, jirka.polansky@gmail.com
konzultační hodiny dle dohody
účast na cvikách povinná, povoleny 2 neomluvené absence
Jiří Polanský (ESF MU) EMM I podzim 2007 4 / 1
Úvodní informace
Podklady ke cvičením
Podklady ke cvičením od Hanky Fitzové (jsou v ISu)
sylabus k několika prvním cvičením od Michala Kvasničky
http://www.econ.muni.cz/ qasar/vyuka/emm1/sylabusemm1.pdf
mé slidy (pouští se ctrl+L), některá zadání, matematické věty atd.
http://www.econ.muni.cz/ polansky/emm
zájem o ekonomii:
Chiang: Fundamental Methods of Mathematical Economics
Simon - Blume: Mathematics for Economists
Jiří Polanský (ESF MU) EMM I podzim 2007 5 / 1
Úvodní informace
Testy
budou dva (7. a 12. týden)
pokud student nebude moci fyzicky absolvovat seminární test
(omluvenka), napíše náhradní test (dle dohody)
za každý test je možno dostat maximálně 10 bodů. Pro připuštění ke
zkoušce je nutné získat z každého testu alespoň 5 bodů. Při menším
počtu má student možnost napsat opravný test
Jiří Polanský (ESF MU) EMM I podzim 2007 6 / 1
Úvodní informace
Projekt
zadání úlohy studenti obdrží ve 4. týdnu výuky
úkolem bude formulace matematického modelu, jeho vyřešení v
Excelu a interpretace získaného řešení
za vypracovaný projekt je možno dostat maximálně 10 bodů, pro
připuštění ke zkoušce je zapotřebí získat alespoň 5 bodů
body získané za semestrální projekt se budou plně započítávat do
výsledného hodnocení
Jiří Polanský (ESF MU) EMM I podzim 2007 7 / 1
Opakování lineární algebry
Jiří Polanský (ESF MU) EMM I podzim 2007 8 / 1
Opakování lineární algebry
Matice I
sčítání a odčítání
matice stejného typu, sčítají (odčítají) se odpovídající si prvky
komutativní, asociativní zákon
násobení matic
skalárem (číslem)  je komutativní
maticí  je komutativní jen ve dvou případech (jednotková matice a
inverzní matice)
Jiří Polanský (ESF MU) EMM I podzim 2007 9 / 1
Opakování lineární algebry
Matice II
jednotková matice
transpozice matice AT
výměna prvků podle hlavní diagonály
vlastnosti
inverzní matice A-1
vlastnosti
využití například pro řešení soustavy atd.
příklad výpočtu pomocí Gaussovy eliminační metody
determinant matice D
matice 2x2, 3x3, Laplace expansion law
vlastnosti
Jiří Polanský (ESF MU) EMM I podzim 2007 10 / 1
Opakování lineární algebry
Gaussova eliminační metoda
soustava rovnic
povolené úpravy
záměna řádků, sloupců
vynásobení řádku (sloupce) nenulovým číslem
sečtení dvou řádků (sloupců)
na hodnosti matice závisí výsledek
výpočet inverzní matice
Jiří Polanský (ESF MU) EMM I podzim 2007 11 / 1
Formulace úloh lineárního programování
Jiří Polanský (ESF MU) EMM I podzim 2007 12 / 1
Formulace úloh lineárního programování
Postup
slovní zadání
definování veličin (výsledková veličina, rozhodovací veličiny)
sestavení tabulky (pokud to je účelné)
matematický zápis
Jiří Polanský (ESF MU) EMM I podzim 2007 13 / 1
Formulace úloh lineárního programování
Úloha 1 - zadání
Výživa (dieta)
(minimalizační úloha lineárního programování)
Zadání: Výživné látky (pro jednoduchost jen 3 - kalcium, bílkoviny,
vitamín A), u kterých jsou stanoveny požadované minimální denní dávky,
dva typy jídel (I a II), které tyto látky obsahují, ceny jídel.
Cíl: Nalezení kombinace jídel I a II, která minimalizuje náklady a zároveň
splňuje požadovaná omezení.
Jiří Polanský (ESF MU) EMM I podzim 2007 14 / 1
Formulace úloh lineárního programování
Úloha 1 - tabulka
Food I Food II
Cena 0.50 1.00 min.den.pož.
Kalcium 10 4 20
Bílkoviny 5 5 20
Vitamin A 2 6 12
Výsledková veličina ... náklady ( MIN)
Rozhodovací veličina ... volba jídel (x1, x2)
Jiří Polanský (ESF MU) EMM I podzim 2007 15 / 1
Formulace úloh lineárního programování
Úloha 1 - matematický zápis
Účelová funkce (objective function)  Minimalizace
C = 0.5x1 + x2
omezující podmínky (kalcium, bílkoviny, vitamín A, nezápornost)
10x1 + 4x2  20
5x1 + 5x2  20
2x1 + 6x2  12
x1, x2  0
Jiří Polanský (ESF MU) EMM I podzim 2007 16 / 1
Formulace úloh lineárního programování
Úloha 1 - grafické řešení
rozhodovací veličiny na osy (Food I, II)
podmínka nezápornosti x1, x2  0
omezující podmínky (jako rovnost, u přímky stačí najít 2 body a
spojit, pak přidáme nerovnost)
najdeme společnou oblast
hledáme min náklady x2 = C - 0.5x1
 bod [3,1], C = 2.50
Jiří Polanský (ESF MU) EMM I podzim 2007 17 / 1
Formulace úloh lineárního programování
Úloha 2 - zadání
Výroba
(maximalizační úloha lineárního programování)
Zadání: Závod vyrábí 2 komodity, využívá 3 oddělení (lisovna, válcovna a
montáž), kapacita lisovny a válcovny je 8 hodin a montáže je 3 hodiny
denně. Komodita 1 se lisuje a poté montuje (každá tuna využívá 30 min
kapacity lisovny a 10 minut kapacity montáže); komodita 2 se válcuje a
pak montuje (každá tuna využívá 60 min kapacity válcovny a 20 minut
kapacity montáže). Čistý zisk na tunu u výrobku I je 1, u výrobku II je 2.
Cíl: Jakou kombinaci výstupu by měl podnik zvolit, aby maximalizoval zisk.
Jiří Polanský (ESF MU) EMM I podzim 2007 18 / 1
Formulace úloh lineárního programování
Úloha 2 - tabulka
Výrobek I Výrobek II denní kapacita
Lisovna 30 min (1/2h) 0 8h
Válcovna 0 60min (1h) 8h
Montáž 10min (1/6h) 20min (1/3h) 3h
Zisk na tunu 1 2
Výsledková veličina ... čistý zisk ( MAX)
Rozhodovací veličina ... volba výstupu (x1, x2)
Jiří Polanský (ESF MU) EMM I podzim 2007 19 / 1
Formulace úloh lineárního programování
Úloha 2 - matematický zápis
Účelová funkce  Maximalizace
 = x1 + 2x2
omezující podmínky
1/2x1  8
x2  8
1/6x1 + 1/3x2  3
x1, x2  0
Jiří Polanský (ESF MU) EMM I podzim 2007 20 / 1
Formulace úloh lineárního programování
Úloha 2 - matematický zápis (po úpravě)
Účelová funkce  Maximalizace
 = x1 + 2x2
omezující podmínky
x1  16
x2  8
x1 + 2x2  18
x1, x2  0
Jiří Polanský (ESF MU) EMM I podzim 2007 21 / 1
Formulace úloh lineárního programování
Úloha 2 - grafické řešení
rozhodovací veličiny na osy (Výrobek I, II)
podmínka nezápornosti x1, x2  0
omezující podmínky (jako rovnost, u přímky stačí najít 2 body a
spojit, pak přidáme nerovnost)
najdeme společnou oblast
hledáme max zisk x2 = /2 - 1/2x1
 úsečka vymezená body [2,8] a [16,1],  = 18
Jiří Polanský (ESF MU) EMM I podzim 2007 22 / 1
Formulace úloh lineárního programování
Úloha 3 - zadání
Výroba kalhot
(maximalizační úloha lineárního programování)
Zadání: Závod vyrábí 3 druhy kalhot (jednobarevné JED, kostkované KOS
a kombinované KOM); kapacitní omezení jsou 12000 metrů jednobarevné
látky a 9000 metrů kostkované látky; na výrobu jednobarevných kalhot
(JED) se použije 1,4 metru jednobarevné látky, na KOS 1,4 metru
kostkované látky a na KOM 0,8 metru jednobarevné látky a 0,65 metru
kostkované látky; maximální odbyt je u KOS 3000ks a u KOM 5000ks;
zisk z JED je 400, z KOS 450 a z KOM je 500.
Cíl: Jakou kombinaci výstupu (kalhot) by měl podnik zvolit, aby
maximalizoval zisk.
Jiří Polanský (ESF MU) EMM I podzim 2007 23 / 1
Formulace úloh lineárního programování
Úloha 3 - tabulka
JED KOS KOM kapacita
Látka jednobar. 1,4 0 0,8 12000
Látka kostkov. 0 1,4 0,65 9000
Max odbyt - 3000 5000
Zisk 400 450 500
Výsledková veličina ... čistý zisk ( MAX)
Rozhodovací veličina ... volba výstupu (kalhot) (x1, x2, x3)
Jiří Polanský (ESF MU) EMM I podzim 2007 24 / 1
Formulace úloh lineárního programování
Úloha 3 - matematický zápis
Účelová funkce  Maximalizace
 = 400x1 + 450x2 + 500x3
omezující podmínky
1, 4x1 + 0, 8x3  12000
1, 4x2 + 0, 65x3  9000
x2  3000
x3  5000
x1, x2, x3  0
Jiří Polanský (ESF MU) EMM I podzim 2007 25 / 1
Formulace úloh lineárního programování
Úloha 4 - zadání
Chemická úloha
(minimalizační úloha lineárního programování)
Zadání: Závod nakupuje sloučeniny (I,II,III,IV) s cílem získat cílové
množství chemických prvků (A,B,C), které tyto sloučeniny obsahují a které
z nich získá. Ve sloupcích 2-5 je množství prvku v gramech, které lze
získat z 1kg sloučeniny.
Cíl: Jakou kombinaci sloučenin by měl podnik nakoupit, aby získal
požadované množství prvků a minimalizoval náklady.
název prvku I II III IV cíl.množ. prvků (v kg)
A 0 2 4 5 5
B 2 2 0 4 6
C 10 5 4 10 18
cena slouč. (Kč/kg) 15 10 12 25
Jiří Polanský (ESF MU) EMM I podzim 2007 26 / 1
Formulace úloh lineárního programování
Úloha 4 - matematický zápis
Účelová funkce  Minimalizace
C = 15x1 + 10x2 + 12x3 + 25x4
omezující podmínky
2x2 + 4x3 + 5x4 = 5000
2x1 + 2x2 + 4x4 = 6000
10x1 + 5x2 + 4x3 + 10x4 = 18000
x1, x2, x3, x4  0
Jiří Polanský (ESF MU) EMM I podzim 2007 27 / 1
Formulace úloh lineárního programování
Úloha 5 - zadání
Krmná směs
(minimalizační úloha lineárního programování)
Zadání: Krmná směs musí obsahovat alespoň 60 jednotek látky L1, 160
jednotek L2 a 180 jednotek L3; směs lze vyrobit ze dvou krmovin K1 a K2,
přičemž 1kg K1 obsahuje 3 jednotky L1, 4 jednotky L2 a 2 jednotky L3;
1kg krmoviny K2 obsahuje 1 jednotku L1, 3 jednotky L2 a 4 jednotky L3;
cena za 1kg krmoviny K1 je 14 Kč, za 1 kg K2 je 13 Kč.
Cíl: Jakou kombinaci K1 a K2, abychom smícháním získali krmnou směs s
požadovaným obsahem látek a minimalizovali náklady.
Jiří Polanský (ESF MU) EMM I podzim 2007 28 / 1
Formulace úloh lineárního programování
Úloha 5 - tabulka
K1 K2 požadované množ. látek
L1 3 1 60
L2 4 3 160
L3 2 4 180
Cena (za kg) 14 13
Výsledková veličina ... náklady ( MIN)
Rozhodovací veličina ... volba krmoviny (x1, x2)
Jiří Polanský (ESF MU) EMM I podzim 2007 29 / 1
Formulace úloh lineárního programování
Úloha 5 - matematický zápis
Účelová funkce  Minimalizace
C = 14x1 + 13x2
omezující podmínky
3x1 + x2  60
4x1 + 3x2  160
2x1 + 4x2  180
x1, x2  0
Jiří Polanský (ESF MU) EMM I podzim 2007 30 / 1
Formulace úloh lineárního programování
Úloha 6 - zadání
Řezný plán
(minimalizační úloha lineárního programování)
Zadání: Závod k výrobě využívá tyče (T1 = 90cm, T2 = 70cm, T3 =
50cm); nakupuje pouze tyče délky 190 cm, které si musí sám rozřezat do
požadovaných velikostí; odpad z jedné tyče nesmí být větší než 40cm.
Závod k výrobě požaduje 400ks T1, 400 ks T2 a 1300ks T3.
Cíl: minimální počet použitých tyčí standardní délky (190cm)
(alternativně: minimalizace odpadu)
Jiří Polanský (ESF MU) EMM I podzim 2007 31 / 1
Formulace úloh lineárního programování
Úloha 6 - tabulka
způsob 1 2 3 4 5 6 požadavek
T1 2 1 1 0 0 0 400
T2 0 1 0 2 1 0 400
T3 0 0 2 1 2 3 1300
odpad (cm) 10 30 0 0 20 40
Výsledková veličina ... min počet tyčí ( MIN)
Rozhodovací veličina ... volba způsobu řezání (x1, ..., x6)
Jiří Polanský (ESF MU) EMM I podzim 2007 32 / 1
Formulace úloh lineárního programování
Úloha 6 - matematický zápis
Účelová funkce  Minimalizace
z = x1 + x2 + x3 + x4 + x5 + x6
(z = 10x1 + 30x2 + 20x5 + 40x6)
omezující podmínky
2x1 + x2 + x3 = 400
x2 + 2x4 + x5 = 400
2x3 + x4 + 2x5 + 3x6 = 1300
xi  0
Jiří Polanský (ESF MU) EMM I podzim 2007 33 / 1
Formulace úloh lineárního programování
Úloha 7 - zadání
Směny
(minimalizační úloha lineárního programování)
Zadání: Směny po 8 hodinách, nástup vždy o půlnoci, ve 4, ... (vždy po 4
hodinách), minimální počet osob ve službě viz tabulka.
Cíl: kolik osob má nastoupit do služby v každou nástupní dobu, aby služby
byly zajištěny s min počtem osob
Jiří Polanský (ESF MU) EMM I podzim 2007 34 / 1
Formulace úloh lineárního programování
Úloha 7 - tabulka
hodiny osoby
0-4 3
4-8 8
8-12 10
12-16 8
16-20 14
20-24 5
Výsledková veličina ... min počet osob ( MIN)
Rozhodovací veličina ... počet osob (x1, ..., x6)
Jiří Polanský (ESF MU) EMM I podzim 2007 35 / 1
Formulace úloh lineárního programování
Úloha 7 - matematický zápis
Účelová funkce  Minimalizace
z = x1 + x2 + x3 + x4 + x5 + x6
omezující podmínky
x1 + x6  3
x1 + x2  8
x2 + x3  10
x3 + x4  8
x4 + x5  14
x5 + x6  5
xi  0
Jiří Polanský (ESF MU) EMM I podzim 2007 36 / 1
Formulace úloh lineárního programování
Úloha 8 - zadání
Doprava
(minimalizační úloha lineárního programování)
Zadání: dva sklady (S1, S2), tři zákazníci (Z1, Z2, Z3), v tabulce jsou
měsíční zásoby cementu, měsíční požadavky zákazníků, náklady na
dopravu 1 tuny cementu ze skladu S k zákazníkovi Z
Cíl: minimální náklady na dopravu při splnění požadavků zákazníků a
plném využití kapacity skladů
Jiří Polanský (ESF MU) EMM I podzim 2007 37 / 1
Formulace úloh lineárního programování
Úloha 8 - tabulka
sklady Z1 Z2 Z3 zásoby
S1 5 2 3 30
S2 2 1 1 75
požadavky 35 25 45
Výsledková veličina ... min náklady ( MIN)
Rozhodovací veličina ... dopravené množství (xsz)
Jiří Polanský (ESF MU) EMM I podzim 2007 38 / 1
Formulace úloh lineárního programování
Úloha 8 - matematický zápis
Účelová funkce  Minimalizace
C = 5x11 + 2x12 + 3x13 + 2x21 + x22 + x23
omezující podmínky
x11 + x12 + x13 = 30
x21 + x22 + x23 = 75
x11 + x21 = 35
x12 + x22 = 25
x13 + x23 = 45
xsz  0
Jiří Polanský (ESF MU) EMM I podzim 2007 39 / 1
Formulace úloh lineárního programování
Úloha 9 - zadání
Výroba
(minimalizační úloha lineárního programování)
Zadání: závod vyrábí 4 typy výrobků (V1, V2, V3, V4), kapacita vstupů
(zařízení Z má kapacitu 1200 hodin, suroviny 1400 tun), výrobky V1 a V2
mohou být použity jako vstupy (meziprodukty, polotovary) pro statky V2,
V3, V4, či mohou být prodávány samostatně. Odbytové ceny jsou
V1=300, V2=600, V3=1000, V4=3000.
Cíl: maximalizace tržeb (výnosů z prodaného množství)
Jiří Polanský (ESF MU) EMM I podzim 2007 40 / 1
Formulace úloh lineárního programování
Úloha 9 - tabulka
V1 V2 V3 V4 kapacita
Z 1,5 - 2 2,5 1200
S 2 1,5 2 - 1400
V1 (vstup) - 0,5 - 1
V2 (vstup) - - 0,5 2
ceny 300 600 1000 3000
Výsledková veličina ... výnosy(tržby) ( MAX)
Rozhodovací veličina ... množství výrobků (xi )
!!!! je nutné rozlišit vyrobené množství x a prodané množství ~x
Jiří Polanský (ESF MU) EMM I podzim 2007 41 / 1
Formulace úloh lineárního programování
Úloha 9 - matematický zápis
Účelová funkce  Maximalizace
 = 300x1 + 450x2 + 700x3 + 1500x4
omezující podmínky
1, 5x1 + 2x3 + 2, 5x4  1200
2x1 + 1, 5x2 + 2x3  1400
x1  0, 5x2 + x4
x2  0, 5x3 + 2x4
xi  0
Jiří Polanský (ESF MU) EMM I podzim 2007 42 / 1
Formulace úloh lineárního programování
Úloha 10 - zadání
Výroba
(minimalizační úloha lineárního programování)
Zadání: závod vyrábí 2 typy zaměnitelných výrobků (I, II), kapacita
slévárny je max 80 ks I nebo 100 ks II či nějakou jejich kombinaci,
kapacita lisovny je 200 ks I nebo 60 ks II nebo jejich kombinace, montáž
typu I má kapacitu 60 ks, montáž typu II má kapacitu 80 ks, ceny za oba
statky je 28000.
Cíl: maximalizace hodnoty výstupu (max hodnota produkce)
Jiří Polanský (ESF MU) EMM I podzim 2007 43 / 1
Formulace úloh lineárního programování
Úloha 10 - postup
Postup:
xi se v jednotlivých úsecích dělí maximálním možným vyrobeným počtem
kusů  jaký podíl kapacity úseku vezme výroba xi (po vynásobení 100 je
podíl v procentech)
Výsledková veličina ... hodnota produkce ( MAX)
Rozhodovací veličina ... množství výrobků (xi )
Jiří Polanský (ESF MU) EMM I podzim 2007 44 / 1
Formulace úloh lineárního programování
Úloha 10 - matematický zápis
Účelová funkce  Maximalizace
 = 28000x1 + 28000x2
omezující podmínky
5x1 + 4x2  400
3x1 + 10x2  600
x1  60
x2  80
xi  0
Jiří Polanský (ESF MU) EMM I podzim 2007 45 / 1
Jednofázová simplexová metoda
Jiří Polanský (ESF MU) EMM I podzim 2007 46 / 1
Jednofázová simplexová metoda
Zadání I
Výroba
(maximalizační úloha lineárního programování)
Zadání: Závod vyrábí 2 komodity, využívá 3 oddělení (lisovna, válcovna a
montáž), kapacita každého oddělení je 8 hodin denně. Komodita 1 se
lisuje a poté montuje (každá tuna využívá 30 min kapacity lisovny a 20
minut kapacity montáže); komodita 2 se válcuje a pak montuje (každá
tuna využívá 60 min kapacity válcovny a 40 minut kapacity montáže).
Čistý zisk na tunu u výrobku I je 40, u výrobku II je 30.
Cíl: Jakou kombinaci výstupu by měl podnik zvolit, aby maximalizoval zisk.
Jiří Polanský (ESF MU) EMM I podzim 2007 47 / 1
Jednofázová simplexová metoda
Tabulka
Výrobek I Výrobek II denní kapacita
Lisovna 30 min (1/2h) 0 8h
Válcovna 0 60min (1h) 8h
Montáž 20min (1/3h) 40min (2/3h) 8h
Zisk na tunu 40 30
Výsledková veličina ... čistý zisk ( MAX)
Rozhodovací veličina ... volba výstupu (x1, x2)
Jiří Polanský (ESF MU) EMM I podzim 2007 48 / 1
Jednofázová simplexová metoda
Matematický zápis
Účelová funkce  Maximalizace
 = 40x1 + 30x2
omezující podmínky
1/2x1  8
x2  8
1/3x1 + 2/3x2  8
x1, x2  0
Jiří Polanský (ESF MU) EMM I podzim 2007 49 / 1
Jednofázová simplexová metoda
Matematický zápis (po úpravě)
Účelová funkce  Maximalizace
 = 40x1 + 30x2
omezující podmínky
x1  16
x2  8
x1 + 2x2  24
x1, x2  0
Jiří Polanský (ESF MU) EMM I podzim 2007 50 / 1
Jednofázová simplexová metoda
Grafické řešení
rozhodovací veličiny na osy (Výrobek I, II)
podmínka nezápornosti x1, x2  0
omezující podmínky (jako rovnost, u přímky stačí najít 2 body a
spojit, pak přidáme nerovnost)
najdeme společnou oblast
hledáme max zisk x2 = /30 - 4/3x1
 bod [16,4],  = 760
Jiří Polanský (ESF MU) EMM I podzim 2007 51 / 1
Jednofázová simplexová metoda
Postup řešení pomocí jednofázové simplexové metody I
přepis úlohy do kanonického tvaru (matice A musí obsahovat
libovolně umístěnou jednotkovou submatici)
ZATÍM postup pro MAXIMALIZAČNÍ úlohu
ZATÍM všechny omezení jsou ve tvaru  (pokud budou ve tvaru =
nebo , je nutné použít dvoufázovou metodu)
 pro tento případ model doplníme o doplňkové proměnné si
tyto proměnné mají ekonomický význam (omezení je zcela využito
pokud je tato proměnná rovna nule, omezení není zcela využito, pokud
je proměnná větší než nula)
používám značení pomocí písmena s (s ... slack variables, surplus
variables)
Jiří Polanský (ESF MU) EMM I podzim 2007 52 / 1
Jednofázová simplexová metoda
Kanonický tvar
Účelová funkce  Maximalizace
 = 40x1 + 30x2(+0s1 + 0s2 + 0s3)
omezující podmínky
x1 + s1 = 16
x2 + s2 = 8
x1 + 2x2 + s3 = 24
x1, x2, s1, s2, s3  0
(v účelové fci mají doplňkové proměnné koeficienty rovny 0, neboť
nevyužité kapacity nezvýší zisk)
Jiří Polanský (ESF MU) EMM I podzim 2007 53 / 1
Jednofázová simplexová metoda
Postup řešení pomocí jednofázové simplexové metody II
musíme najít PIVOT ( klíčový prvek v simplexové tabulce)
klíčový sloupec: v řádku účelové fce jde o zápornou hodnotu, jež je
největší v absolutní hodnotě (to znamená, že pro maxim. úlohu jde
vlastně o největší zápornou hodnotu)
klíčový řádek: hledáme minimální hodnotu  = b/a (může být i
nulová); a je klíčový sloupec, v němž nás zajímají pouze kladné prvky
počítáme Gaussovskou eliminační metodou, aby na pivotní pozici byla
jednička a v celém sloupci nuly
!!! vždy přičítáme násobky klíčového řádku k ostatním řádkům, nikdy
ne naopak
výměna otočením proměnné v bázi podle pivotního prvku
postup opakujeme v dalších simplexových tabulkách, dokud je v řádku
účelové fce alespoň jedna záporná proměnná (záporná proměnná v
řádku účelové fce u maximalizační úlohy znamená, že hodnota
účelové fce (např. zisk) poroste...)
Jiří Polanský (ESF MU) EMM I podzim 2007 54 / 1
Jednofázová simplexová metoda
Gaussovká eliminační metoda - tabulka I
řádek s1: jednička tam už je, stačí jen opsat (jinak bychom dělili
odpovídajícím číslem)
s2: nula tam už je, stačí opsat
s3: (-1)  s1 + s3 (!! Vždy násobíme klíčový řádek a sčítáme s
ostatními, nikdy ne naopak !!)
: 40  s1 + 
Vyměníme klíčový sloupec x1 za klíčový řádek s1
Jiří Polanský (ESF MU) EMM I podzim 2007 55 / 1
Jednofázová simplexová metoda
Gaussovká eliminační metoda - tabulka II
řádek s3: dělíme 2
x1: nula už tam je, stačí opsat
s2: (-1)  s3 + s2
: 30  s3 + 
Vyměníme klíčový sloupec (x2) za klíčový řádek (s3)
Jiří Polanský (ESF MU) EMM I podzim 2007 56 / 1
Jednofázová simplexová metoda
Řešení
Výsledek vyčteme z tabulky - první sloupec udává veličiny, sloupec b
hodnoty: [x1, x2, s1, s2, s3]
 [16, 4, 0, 4, 0]
Jiří Polanský (ESF MU) EMM I podzim 2007 57 / 1
Jednofázová simplexová metoda
Poznámky
na počátku volíme bázi takovou, aby v ní byly jen doplňkové
proměnné (nevyrábíme žádný výrobek)
MINIMALIZAČNÍ ÚLOHA  hledáme v řádku účelové fce největší
kladný prvek, poté opět minimální 
omezení typu = nebo   dvoufázová metoda (viz příští cviko)
Jiří Polanský (ESF MU) EMM I podzim 2007 58 / 1
Jednofázová simplexová metoda
Zadání II
Účelová funkce  Maximalizace
 = 15000x1 + 5000x2 + 10000x3 + 10000x4 + 30000x5
omezující podmínky
2x1 + x3 + x4 + 2x5  400
0.5x1 + x2 + 2x3  120
x1 + 2x2 + x4 + 0.5x5  200
x1, x2, x3, x4, x5  0
Jiří Polanský (ESF MU) EMM I podzim 2007 59 / 1
Jednofázová simplexová metoda
Zadání III
Účelová funkce  Maximalizace
 = 300x1 + 450x2 + 700x3 + 1500x4
omezující podmínky
1, 5x1 + 2x3 + 2, 5x4  1200
2x1 + 1, 5x2 + 2x3  1400
x1  0, 5x2 + x4
x2  0, 5x3 + 2x4
xi  0
Jiří Polanský (ESF MU) EMM I podzim 2007 60 / 1
Dvoufázová simplexová metoda
Jiří Polanský (ESF MU) EMM I podzim 2007 61 / 1
Dvoufázová simplexová metoda
Postup řešení pomocí dvoufázové simplexové metody
pokud jsou omezení typu = nebo   nemáme v matici A
jednotkovou submatici  nemáme bazické proměnné pro počáteční
řešení
do omezení (do rovnic, neboť jsme odstranili znaménka < a >), kde
chybí +1 doplníme pomocnou neekonomickou veličinu
k původnímu modelu přidáme pomocnou účelovou fci, která
minimalizuje součet pomocných proměnných
řešíme pomocný model - pokud existuje řešení, budou všechny
pomocné proměnné rovny nule (jinak řešení neexistuje)
řešíme původní model
Jiří Polanský (ESF MU) EMM I podzim 2007 62 / 1
Dvoufázová simplexová metoda
Zadání (4.8 ze Syllabu Hanky Fitzové)
Účelová funkce  Maximalizace
 = 2x1 + x2
omezující podmínky
3x1 - x2  12
x1 + x2  6
-x1 + 2x2 = 9
x1, x2  0
Jiří Polanský (ESF MU) EMM I podzim 2007 63 / 1
Dvoufázová simplexová metoda
Řešení I - přidání ekonomických proměnných
Účelové funkce
 = 2x1 + x2
omezující podmínky
3x1 - x2 + s1 = 12
x1 + x2 - s2 = 6
-x1 + 2x2 = 9
x1, x2, s1, s2  0
Jiří Polanský (ESF MU) EMM I podzim 2007 64 / 1
Dvoufázová simplexová metoda
Řešení II - přidání neekonomických proměnných
Účelové funkce
 = 2x1 + x2
z = 15 - 3x2 + s2
omezující podmínky
3x1 - x2 + s1 = 12
x1 + x2 - s2 + u1 = 6
-x1 + 2x2 + u2 = 9
x1, x2, s1, s2, u1, u2  0
Jiří Polanský (ESF MU) EMM I podzim 2007 65 / 1
Dvoufázová simplexová metoda
Gaussovká eliminační metoda - tabulka I
řádek u2 dělíme 2
(+1)  u2 + s1
(-1)  u2 + u1
(+1)  u2 + 
(-3)  u2 + z
Vyměníme klíčový sloupec x2 za klíčový řádek u2
Jiří Polanský (ESF MU) EMM I podzim 2007 66 / 1
Dvoufázová simplexová metoda
Gaussovká eliminační metoda - tabulka II
řádek u1 dělíme 3/2
(-5/2)  u1 + s1
(+1/2)  u1 + x2
(+5/2)  u1 + 
(-3/2)  u1 + z
Vyměníme klíčový sloupec x1 za klíčový řádek u1
Jiří Polanský (ESF MU) EMM I podzim 2007 67 / 1
Dvoufázová simplexová metoda
Gaussovká eliminační metoda - tabulka III
řádek s1 dělíme 5/3
(+2/3)  s1 + x1
(+1/3)  s1 + x2
(+5/3)  s1 + 
Vyměníme klíčový sloupec s2 za klíčový řádek s1
Jiří Polanský (ESF MU) EMM I podzim 2007 68 / 1
Dvoufázová simplexová metoda
Zadání (4.7 ze Syllabu Hanky Fitzové)
Účelová funkce  Maximalizace
 = 200x1 + 250x2 + 250x3 + 300x4
omezující podmínky
x1 + 2x3 + 2x4  400
3x1 + 2x2 + x3 = 400
2x2 + 2x3 + 3x4 = 430
x1, x2, x3, x4  0
Jiří Polanský (ESF MU) EMM I podzim 2007 69 / 1
Dvoufázová simplexová metoda
Řešení
Účelové funkce
 = 200x1 + 250x2 + 250x3 + 300x4
z + 3x1 + 4x2 + 3x3 + 3x4 = 830
omezující podmínky
x1 + 2x3 + 2x4 + s1 = 400
3x1 + 2x2 + x3 + u1 = 400
2x2 + 2x3 + 3x4 + u2 = 430
x1, x2, x3, x4, s1, u1, u2  0
Jiří Polanský (ESF MU) EMM I podzim 2007 70 / 1
Zakončení simplexové metody
Jiří Polanský (ESF MU) EMM I podzim 2007 71 / 1
Zakončení simplexové metody
viz syllabus Michala Kvasničky, kapitola 4
úloha nemá žádné přípustné řešení
úloha nemá konečné optimální řešení
úloha má jediné optimální řešení
úloha má nekonečně mnoho řešení, z toho dvě bazická
úloha má nekonečně mnoho řešení, z toho jedno bazické
degenerovaná úloha (jedno optimální řešení ve více bázích)
Jiří Polanský (ESF MU) EMM I podzim 2007 72 / 1
Dualita
Jiří Polanský (ESF MU) EMM I podzim 2007 73 / 1
Dualita
Koncept duality
dosud jsme chápali MAX a MIN úlohy jako oddělené koncepty
ale: každé MAX úloze odpovídá MIN úloha a naopak (duálně
sdružené úlohy)
Jiří Polanský (ESF MU) EMM I podzim 2007 74 / 1
Dualita
Značení
x - rozhodovací veličiny v původní (primární) úloze
y - rozhodovací veličiny v duální úloze
s - doplňkové veličiny v původní (primární) úloze
t - doplňkové veličiny v duální úloze
pomocné veličiny nejsou relevantní (budeme se bavit o optimu)
Jiří Polanský (ESF MU) EMM I podzim 2007 75 / 1
Dualita
Obecný návod
Hanky sylabus strana 21
pozor na převod z MIN do MAX úlohy (měníme rozhodovací veličiny)
Jiří Polanský (ESF MU) EMM I podzim 2007 76 / 1
Dualita
Pravidla
MAX  MIN a naopak
znaménka (, , =) viz tabulka v sylabu
matice koeficientů u duální úlohy je transponovaná matice u původní
úlohy
Jiří Polanský (ESF MU) EMM I podzim 2007 77 / 1
Dualita
Výhody
můžeme si zvolit, jaká úloha má méně omezujících podmínek a tu
počítat (menší velikost báze - zavádíme méně doplňkových či
pomocných veličin)
často může být snazší maximalizovat..., neboť taková úloha má velmi
často omezení typu , což se dá spočítat jednofázovou metodou
(nezavádíme pomocné veličiny)
Jiří Polanský (ESF MU) EMM I podzim 2007 78 / 1
Dualita
Duality theorems
pokud má úloha optimum, má optimum i duální úloha, navíc hodnoty
účelových fcí jsou stejné, tj.  = 
D, C = C
D
jestliže je v optimu rozhodovací veličina úlohy nenulová (y
i > 0)
nebo (x
i > 0), pak odpovídající doplňková veličina u k ní duální úlohy
je nulová (s
i = 0) nebo (t
i = 0)
jestliže je v optimu doplňková veličina úlohy nenulová (s
i > 0) nebo
(t
i > 0), pak odpovídající rozhodovací veličina u k ní duální úlohy je
nulová (y
i = 0) nebo (x
i = 0)
Jiří Polanský (ESF MU) EMM I podzim 2007 79 / 1
Analýza citlivosti
Jiří Polanský (ESF MU) EMM I podzim 2007 80 / 1
Analýza citlivosti
Analýza citlivosti pravých stran omezení
jak se může b změnit, aby se zachovalo přípustné řešení určené
stávajícími proměnnými
vždy jen změny jedné složky vektoru b (ostatní jsou neměnné)
 intervaly stability (v tomto intervalu zůstanou v optimu stávající
veličiny a hodnoty stínových cen se nezmění)
Jiří Polanský (ESF MU) EMM I podzim 2007 81 / 1
Analýza citlivosti
Analýza citlivosti cenových koeficientů
jak se může c změnit, aby stávající řešení zůstalo optimální
vždy jen změny jedné složky vektoru c (ostatní jsou neměnné)
 intervaly stability (v tomto intervalu zůstanou v optimu stávající
veličiny)
Jiří Polanský (ESF MU) EMM I podzim 2007 82 / 1