- Stahuj zápisky z přednášek a ostatní studijní materiály
- Zapisuj si jen kvalitní vyučující (obsáhlá databáze referencí)
- Nastav si své předměty a buď stále v obraze
- Zapoj se svojí aktivitou do soutěže o ceny
- Založ si svůj profil, aby tě tví spolužáci mohli najít
- Najdi své přátele podle místa kde bydlíš nebo školy kterou studuješ
- Diskutuj ve skupinách o tématech, které tě zajímají
Studijní materiály
Hromadně přidat materiály
cvičebnice
EAE99E - Matematické metody v ekonomii a managementu (Hradec Králové)
Hodnocení materiálu:
Zjednodušená ukázka:
Stáhnout celý tento materiál10
2
0 / 2
///// //////
11
5 /
VI.
I.//
3 11
// 6 II.
///
//
7 5
///
II.
6
10 5 15 8
4 7 15
15 5 1010 0 10815 15
5 3 10 10 4 10 10 25 10
5 5 3 5 15 10 5 09 9 25
1 15 30 30
0 10 10
7 3 3 2 3 25 25
0 3 10 25
0 0 20
17
0 11 5
5 3
15 30
3
3 251311
30 30
3 20 2013
20 100
610
530
7 10 13 300
13
630
13 30
Červeně jsou napsány činnosti; Délka projektu 30 dní; Kritická cesta : činnosti 1-3-4-8-10-11
Příklad 5 (c) K. Bolková
Kancel
Úřad
Pošta
Banka
Kancel
-------
200
500
300
100
200
200
Úřad
200
-------
400
700
200
---
---
Pošta
500
400
------
500
100
100
0
Banka
300
700
500
------
200
200
---
100
200
100
200
300
---
300
0
200
---
---
300
Žlutá – vyřazeno jako první
Zelená – vyřazeno jako druhé
Optimální cesta:
Cesta začne z kanceláře
300 500 400 200
Kancelář ---------- banka ---------- pošta ----------- úřad ----------- kancelář
Sekretářka ujde 1 400 m.
Elementární (ekvivalentní) operace.
součet řádků
násobení řádku skalárem (skalár nesmí být 0)
výměna řádků
vynechání řádku pouze v případě, že je ze samých nul
Soustava lineárních rovnic:
x1+x2+x3 = 4
2x1+x2+x3 = 6
-3x1+2x2-x3 = -5
převedeme do matice soustavy
1 1 1 4
2 1 1 6
-3 2 -1 -5
Jordanova eliminační metoda:
Příklad:
x1+x2+x3+x4 = 4
2x1+x2+x3-x4 = 6
-3x1+2x2-x3+3x4 = 4
*(-2)/(3)
1 1 1 1 4 1 1 1 1 4 1 0 0 - 2 2
2 1 1 -1 6 ~ 0-1-1-3 -2 *(-1) ~ 0 1 1 3 2 *(-1)/(-5) ~
-3 2-1 3 -5 0 5 2 6 7 0 0 -3 -9 -3 /(-3)/ *(-1)
-2-2-2-2/ -8 0 0 -1 -3 /-1
3 3 3 3 / 12
1 0 0 -2 2 kontrola: x1= 2, x2= 1, x3 =1, x4 =0 .. protože není bázická proměnná
0 1 0 0 1
0 0 1 3 1
Pozn. První řádek vynásobíme vhodným číslem tak, abychom po součtu řádků dostaly na pozici x12=0, sčítáme zelené řádky,
Postup opakujeme i pro získání 0 na pozici x13
tento postup uplatňuje i na řádek dva a tři
Základy lineárního programování:
Matematický model musí obsahovat:
účelovou funkci - z
omezující podmínky
podmínky nezápornosti – x1,2,..n≥ 0
Příklad:
Malá firma vyrábí náhrdelníky a prsteny. Za jeden den dokáže vyrobit celkem nejvýše 24 ks klenotů. Každý náhrdelník se vyrábí jednu hodinu, prsten půl hodiny. Celkem má firma k dispozici 16 hodin denně a chce vyrobit každý den nejméně 10 náhrdelníků. Průměrná cena náhrdelníku je 1 500 Kč, prstenu 2 000 Kč. Kolik kusů jednotlivých klenotů by měla firma vyrobit, aby maximalizovala svoje denní tržby?
Matematický model:
x1= náhrdelníky proměnné
x2= prsteny
x1+x2 ≤ 24 (ks)
x1+x2 ≤ 16 (hodin) omezující podmínky
x1 ≥ 10 (ks)
z = 1,5 x1 + 2x2 MAX (1000,-Kč) – účelová funkce
X1,2 ≥ 0 - podmínky nezápornosti
Simplexový algoritmus:
Převod do kanonické rovnice
x1+x2+d1 = 24
x1+ x2 + d2 = 16
x1 - d3 + p3 = 10
d1,2,3 – doplňková proměnná, která slouží k převodu nerovnice na rovnici a je = 0
p3 – pomocná proměnná, která nám poslouží k vytvoření bazického tvaru a musí být dostatečně nevýhodná, většinou se dává o řád větší ( v tomto případě bude -10)
cj – cena jednotky
zj-cj – test optimality
cj
1,5
2
0
0
0
-10
Pravá strana
x1
x2
d1
d2
d3
p3
b
Ω
0
d1
1
1
1
0
0
0
24
24/1
0
d2
1
˝
0
1
0
0
16
16/1
-10
p3
1
0
0
0
-1
1
10
10/1
zj-cj
-11,5
-2
0
0
10
0
-100
Test optimality provedeme tak, že z1-c1 = (d1* x11)+ (d2* x12)+ (p3* x13)- c1 = (0*1)+ (0*1)+ (-10*1) – 1,5 = -10-1,5 = 11,5, a stejným způsobem pokračujeme u všech proměnných a na pravé straně.
Klíčový sloupek – vybereme sloupek s nejvyšší hodnotou v našem případě s nejvyšší zápornou hodnotou, protože máme maximalistické zadání.
Klíčový řádek získáme jako podíl čísla ve sloupci b a hodnoty čísla uvedenou v klíčovém sloupci.
Po stanovení klíčového řádku tento řádek z řešení vypustíme a nahradíme ho proměnnou v klíčovém sloupku.
Vypíšeme si hodnoty proměnných:
x1 = 0, x2 =0, d1= 24, d2=16, d3= 0, p3 = 10, z = 0
cj
1,5
2
0
0
0
-10
Pravá strana
x1
x2
d1
d2
d3
p3
b
Ω
0
d1
0
1
1
0
1
-1
14
14/1
0
d2
0
1/2
0
1
1
-1
6
12/1
1,5
x1
1
0
0
0
-1
1
10
nelze
zj-cj
0
-2
0
0
-1,5
11,5
15
x1 = 10, x2 =0, d1= 14, d2=6, d3= 0, p3 = 0, z = 15
cj
1,5
2
0
0
0
-10
Pravá strana
x1
x2
d1
d2
d3
p3
b
Ω
0
d1
0
0
1
-2
-1
1
2
2
x2
0
1
0
2
2
-2
12
1,5
x1
1
0
0
0
-1
1
10
zj-cj
0
0
0
4
2,5
7,5
39
x1 = 10, x2 =12, d1= 0, d2=0, d3= 0, p3 = 0, z = 39
V testu optimality nemáme žádnou zápornou hodnotu a proto je toto řešení optimální.
Optimální řešení jsme získali za pomocí rovnoběžky, která protíná množinu přípustných řešení a má body na x1 = 15 na x2 = 20.
Dopravní úloha
Dodavatel ……… D1 … má přepravní kapacitu 50 (t substrátu)
Dodavatel ……… D2 … má přepravní kapacitu 30 (t substrátu)
Dodavatel ……… D3 … má přepravní kapacitu 60 (t substrátu)
Spotřebitel ……..S1… požaduje 100 (t substrátu)
Spotřebitel ……..S2… požaduje 20 (t substrátu)
x11 = trasa od dodavatele D1 k spotřebitelovi S1
x11 = 0, nebude se realizovat
cena za vykonanou trasu:
x11=10 (Kč), x12=12(Kč), x21=8(Kč), x22=10(Kč), x31=15(Kč), x32=18(Kč)
x11 + x12 ≤ 50 (t)
x12 + x21 ≤ 30 (t) omezující podmínky dodavatelů
x31 + x32 ≤ 60 (t)
x11+x21+x31≥ 100 (t) omezující podmínky spotřebitelů
x12+x22+x32≥ 20 (t)
xij ≥ 0 - podmínka nezápornosti
z – účelová funkce, z = 10 x11+ 12 x12 + 8x21 + 10 x22 + 15 x31+ 18 x32 MIN
Zkontrolujeme zda je úloha vyvážená.
∑ ai = (50+30+60) = 140
i
∑ bj = (100+20) = 120
j
∑ ai ≠ ∑ bj úloha je nevyvážená
j i
Doplníme do řešení vhodné číslo (SF – fiktivní spotřebitel), abychom dostali vyvážené řešení.
S1
S2
SF
ai
D1
10
12
0
50
D2
8
10
0
30
D3
15
18
0
60
bj
100
20
20
2) Základní řešení:
Metoda severozápadního rohu
doplníme maximální hodnotu do políčka vlevo nahoře (D1 x S1)
tímto je vyčerpána kapacita prvního dodavatele (D1)
doplníme maximální hodnotu do políčka (D2 x S1)
tímto je vyčerpána kapacita druhého dodavatele (D2)
doplníme maximální hodnotu do políčka (D3 x S1)
tímto je splněn požadavek spotřebitele (S1)
doplníme maximální hodnotu do políčka (D3 x S2)
tímto je splněn požadavek spotřebitele (S2)
doplníme maximální hodnotu do políčka (D3 x S3)
do posledního políčka doplníme zbývající hodnotu a tím je splněn požadavek fiktivního spotřebitele
S1
S2
SF
ai
D1
50 10
-- 12
-- 0
50
D2
30 8
-- 10
-- 0
30
D3
20 15
20 18
20 0
60
bj
100
20
20
z = 500+240+300+360+0 = 1400,- Kč
Metoda indexová - v dopravní tabulce najdeme nejmenší cenu a buňku, která tuto cenu obsahuje, obsadíme maximálním množstvím zboží
S1
S2
SF
ai
D1
50 10
-- 12
-- 0
50
D2
30 8
-- 10
-- 0
30
D3
20 15
20 18
20 0
60
bj
100
20
20
tedy odsadíme políčko (D2 x S1) – tímto je vyčerpána kapacita dodavatele D2
dále odsadíme políčko (D1 x S1) – tímto je vyčerpána kapacita dodavatele D1
dále odsadíme políčko (D3 x S1) – tímto je splněn požadavek spotřebitele S1
dále odsadíme políčko (D3 x S2) – tímto je splněn požadavek spotřebitele S2
do posledního možného pole doplníme zbývající hodnotu
z = 240+500+300+360+0 = 1400,- Kč
C) Vogelova aproximační metoda
- každém řadě (řádku i sloupci) vypočítáme diference mezi dvěma nejvýhodnějšími sazbami
- v řadě s největší diferenciací určíme políčko s nejvýhodnější sazbou a obsadíme ho maximálně možným množstvím. Po vyčerpání kapacity dodavatele vyškrtneme příslušný řádek a přepočítáme sloupcové diference. Při uspokojení požadavku spotřebitele vyškrtneme příslušný sloupec a přepočítáme řádkové diference
- tento postup opakujeme i v dalším kroku, tímto jsme vyčerpali kapacitu dodavatele D3
- znovu opakujeme postup ad 2, tímto jsme vyčerpali kapacitu dodavatele D2
- naposledy aplikuje předchozí pravidlo a obsadíme poslední pole, kam dosadíme zbývající hodnotu, tímto splníme požadavek spotřebitele S1
- na poslední pole doplníme zbývající hodnotu, která nám naplní kapacitu dodavatele D1 a splní požadavek spotřebitele S2
S1
S2
SF
ai
di
D1
30 10
20 12
* 0
50
10 -0
10
12-10
2
D2
30 8
* 10
* 0
30
8-0
8
10-8
2
D3
40 15
* 18
20 0
60
15-0
15
18-15
3
bj
100
20
20
bj
2
2
0
Z = 0+600+240+300+240 = 1380,- Kč
Hledání optimálního řešení
S1
S2
SF
ai
ui
D1
50 10
* 12
* 0
50
-5
D2
30 8
* 10
* 0
30
-7
D3
20 15
20 18
20 0
60
0
bj
100
20
20
vj
15
18
0
ui, vj – duální hodnoty
* duální hodnoty volíme tak, abychom u řádku s nejvíce obsazenými poli měli hodnotu = 0 ( je to nejvhodnější, jinak může použít jakýkoliv řádek a jakékoliv číslo)
* pro obsazené pole platí, že součet duální hodnoty v řádku i sloupci dá cenu políčka
ui + vj = cij
Hodnotu duální hodnoty v poli (S1;vj1) vypočítáme: vj1 = cij1 - ui3 = 15-0 = 15
Hodnotu duální hodnoty v poli (S2;vj2) vypočítáme: vj2 = cij2 - ui3 = 18-0 = 18
Hodnotu duální hodnoty v poli (SF;vj3) vypočítáme: vj3 = cij3 - ui3 = 0- 0 = 0
Hodnotu duální hodnoty v poli (D1;uj1) vypočítáme: ui1 = cij1 - vj1 = 10-15 = -5
Hodnotu duální hodnoty v poli (D2;uj2) vypočítáme: ui3 = cij2 - vj2 = 8-15 = -7
Dále si musíme určit pomocné proměnné, které nám pomůžou zjistit, jaké políčko si zaslouží zařadit do řešení nebo zda takové políčko vůbec existuje, pomocná hodnota se zjišťuje pouze u neobsazených polí a platí zde ui + vj - cij = pomocná hodnota
S1
S2
SF
ai
ui
D1
50 10
1 12
-5 0
50
-5
D2
30 8
1 10
-7 0
30
-7
D3
20 15
20 18
20 0
60
0
bj
100
20
20
vj
15
18
0
Pomocná hodnota pro pole (S2,D1) ui1 + vj2 - cij = (-5+18)-12= 1
Pomocná hodnota pro pole (SF,D1) ui1 + vj3 - cij = (-5+ 0)- 0 =-5
Pomocná hodnota pro pole (S2,D2) ui2 + vj2 - cij = (-7+18)-10= 1
Pomocná hodnota pro pole (SF,D2) ui2 + vj3 - cij = (-7+ 0)- 0 =-7
Vzhledem k tomu, že máme zadáno minimalistické řešení (úkolem je minimalizovat náklady na přepravu), tak za pomocnou hodnotu si zvolíme nejvyšší kladnou hodnotu pomocného ukazatele.
V našem případě jsou oba stejné, a proto máme dvě optimální řešení. Pro názornost jsme si vybrali pole (S2,D1). Za pomoci Dantzigova uzavřeného obvodu přesuneme z pole (S2,D3) = 20 na pole (S2,D1), protože jsme tímto krokem porušili podmínky rovnosti v jednotlivých řádcích a sloupcích, musíme řešení upravit tak, aby bylo pravdivé. Tedy od pole (S2,D1) musíme odečíst hodnotu -20, pole (S1,D2) upravovat nemusíme, neboť zde k porušení rovnosti nedošlo, poslední pole, které musíme upravit je pole (S1,D3) k jehož hodnotě přičteme hodnotu +20
S1
S2
SF
ai
ui
D1
50-20 10
+20 12
0
50
-5
D2
30 8
10
0
30
-7
D3
20+20 15
20 18
20 0
60
0
bj
100
20
20
vj
15
18
0
Tedy tímto jsme vytvořili jedno ze dvou optimálních řešení:
S1
S2
SF
ai
ui
D1
30 10
20 12
0
50
-5
D2
30 8
10
0
30
-7
D3
40 15
0 18
20 0
60
0
bj
100
20
20
vj
15
18
0
Toto tvrzení si ověříme:
z = 30*10+30*8+40*15+20*12= 300+240+600+240 =1380
Toto by mělo být druhé optimální řešení:
S1
S2
SF
ai
ui
D1
50 10
0 12
0 0
50
-5
D2
10 8
20 10
0 0
30
-7
D3
40 15
0 18
20 0
60
0
bj
100
20
20
vj
15
18
0
Z = 50*10+10*8+40*15+20*10 = 500+ 80+ 600+200 = 1380
Vloženo: 28.03.2011
Velikost: 121,17 kB
Komentáře
Tento materiál neobsahuje žádné komentáře.
Mohlo by tě zajímat:
Skupina předmětu EAE99E - Matematické metody v ekonomii a managementu (Hradec Králové)
Reference vyučujících předmětu EAE99E - Matematické metody v ekonomii a managementu (Hradec Králové)
Podobné materiály
- ENE04E - Obecná ekonomie I. - Cvičebnice z mikra
- ENE05E - Obecná ekonomie II. - Cvičebnice
- ENE15E - Obecná ekonomie III. - Cvičebnice
- EHE12E - Politologie - PAA - testy ze cvičebnice
- ERE07E - Kybernetika v řízení PAE - vyplněná cvičebnice
- ERE07E - Kybernetika v řízení PAE - cvičebnice
- EUE33E - Základy účetnictví - VSRR - Cvičebnice
- EUE21Z - Teorie účetnictví - PAA, INFO - Cvičebnice
- EAE26E - Matematické metody v ekonomii a managementu - cvicebnice
- EAE82E - Matematické metody v ekonomii a managementu (Cheb) - cvičebnice
- EAE96E - Matematické metody v ekonomii a managementu (Jičín) - cvičebnice
- EAE98E - Matematické metody v ekonomii a managementu (Klatovy) - cvicebnice
- EAE97E - Matematické metody v ekonomii a managementu (Litoměřice)) - cvicebnice
- EAEA1E - Matematické metody v ekonomii a managementu (Most) - cvicebnice
- EAEA7E - Matematické metody v ekonomii a managementu (Sezimovo Ústí) - cvicebnice
- EAEA9E - Matematické metody v ekonomii a managementu (Šumperk) - cvicebnice
Copyright 2024 unium.cz