- 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
Návod na výpočty příkladů
EAE02E - Ekonomicko matematické metody II.
Hodnocení materiálu:
Zjednodušená ukázka:
Stáhnout celý tento materiálSimplexová tabulka
1) Ze zadání vypíšeme nerovnice a omezující funkci.
2) Převedeme na kanonický tvar tzn.
a) všechny nerovnice jsou ≤ , nerovnost se změní na rovnost, přidáme doplňkové proměnné je jich tolik, kolik nerovnic máme , ke každé přidáváme pouze 1, znaménka před nimi jsou +
b) všechny nerovnice jsou ≥, nerovnost se změní na rovnost, přidáme doplňkové proměnné je jich tolik, kolik nerovnic máme , ke každé přidáváme pouze 1, znaménka před nimi jsou - , toto však není kanonický tvar, ten dostaneme přidáním pomocných proměnných, je jich tolik, kolik máme nerovnic, indexy se číslují až po doplňkových proměnných, přidáváme ke každé nerovnici 1
c)nerovnice jsou smíšené , nejdříve doplníme doplňkové proměnné při ≤ dáváme +
při ≥ dáváme -, poté doplníme pomocné proměnné s parametrem M, doplňujeme je k rovnicím kde se vyskytuje nerovnost ≥ , nebo rovnost. Znaménko je při maximalizaci – a při minimalizaci +. Prohibitivní sazbu M volíme jako desetinásobek cen u strukturních proměnných (10,100,1000,10000)
3) a) doplníme do simplexové tabulky viz příklad:
x1, x2 , x3 – strukturální proměnné
x4, x5, x6 – doplňkové proměnné
červená čísla jsme doplnili z rovnic v kanonickém tvaru včetně pravých stran, které jsou ve sloupci b , zelená čísla jsme doplnily z omezující podmínky z = 10x1 + 5x2 +
4 x3 - 0 x4 + 0 x5 + 0 x6 → max
b) spočítáme zj - cj tak , že v příslušném sloupci vynásobíme první červené číslo s prvním modrým číslem k tomu přičteme násobek druhé červené číslo s druhým modrým číslem atd.nakonec od tohoto součtu odečteme zelené číslo v našem případě první sloupec zj - cj = 1*0 + 2*0 + 1*0 – 10 = -10 takto spočteme i sloupec b
c) určíme sloupec podle kterého budeme počítat a to tak, že při minimalizaci jde o sloupec s největším číslem kladným zj - cj a při maximalizaci s největším číslem záporným zj - cj v našem případě první sloupec
10
5
4
0
0
0
CBT
B
x1
x2
x3
x4
x5
x6
b
0
x3
1
1
1
0
0
0
9
9
0
x6
2
1
0
-1
0
1
45
22,5
0
x5
1
0
0
0
1
0
6
6
zj - cj
-10
-5
-4
0
0
0
0
d) dopočítáme a to tak, že b vydělíme číslem z námi označeného sloupce , v našem případě 9/1, 45/2, 6/1 což jsou fialová čísla v tabulce. Nejmenší číslo nám udává požadovaný řádek
4) přepíšeme simlexovou tabulku a to tak, že do šedivého řádku dáme do sloupečku CBT zelené číslo z šedivého sloupečku a v sloupci B změníme proměnnou z šedivého sloupečku. Dále pak musíme přepočítat hodnoty v matici včetně pravých stran tak, abychom dostali v šedivém sloupečku na kříži 1 a ostatní 0.V našem případě 3 řádek vynásobíme -2 a sečteme s řádkem druhým a třetí řádek odečteme od prvního.Dopočítáme podle stejného vzorce jako v bodě 3) určíme sloupec, spočítáme , určíme řádek.Takto pokračujeme dokud nemáme v řádku zj - cj 0 nebo kladná čísla u maximalizace, respektive 0 nebo záporné při minimalizaci
10
5
4
0
0
0
CBT
B
x1
x2
x3
x4
x5
x6
b
0
x3
0
1
1
0
-1
0
3
3
0
x6
0
1
0
-1
-2
1
33
33
10
x1
1
0
0
0
1
0
6
---
zj - cj
0
-5
-4
0
10
0
60
10
5
4
0
0
0
CBT
B
x1
x2
x3
x4
x5
x6
b
5
x2
0
1
1
0
-1
0
3
0
x6
0
0
-1
-1
-1
1
30
10
x1
1
0
0
0
1
0
6
zj - cj
0
0
1
0
5
0
75
5) Interpretace výsledku:
a) Zmax = 75 tyrkysové číslo
b) X(0) = ( 6; 3; 0; 0; 0; 30) opsaná čísla z sloupce b přiřazená ke koeficientům ve sloupci B (pokud se číslo nevyskytuje je 0 )
Suboptimální řešení:
Od pravé strany (b) odečteme vynásobený koeficient s zadaným číslem
Např. x2 =1 , x3 = 2
3 - 1*1 – 1*2 = 0
30 – 0*1 – (-1*2) = 32
6 – 0*1 – 0*2 = 6
75 – 0*1 – 1*2 = 73
Analýza citlivosti
intervaly přípustných hodnot pro parametry λk spočítáme z výchozí a výsledné simplexové tabulky. Parametry λk počítáme pro x-ka ve výchozí tabulce sloupec B ,jako koeficienty
výchozí
10
5
4
0
0
0
CBT
B
x1
x2
x3
x4
x5
x6
b
0
x4
1
1
1
1
0
0
9
9
0
x5
2
1
0
0
1
0
45
22,5
0
x6
1
0
0
0
0
1
6
6
zj - cj
-10
-5
-4
0
0
0
0
výsledná
10
5
4
0
0
0
CBT
B
x1
x2
x3
x4
x5
x6
b
5
x2
0
1
1
0
-1
0
3
0
x6
0
0
-1
-1
-1
1
30
10
x1
1
0
0
0
1
0
6
zj - cj
0
0
1
0
5
0
75
používáme koeficienty ve výsledné tabulce , podle vzorce λk = (- βr / αrk ) pokud je αrk > 0 pak děláme maximum pro αrk < 0 děláme minimum, pokud neexistuje αrk > 0 pak klademe -∞
pokud neexistuje αrk < 0 pak klademe ∞
V našem případě
λ1
x4
b
α 4
λ1
1
3
0
-----
0
30
-1
30
0
6
0
----
pokud neexistuje αrk > 0 pak klademe -∞
λ1 < - ∞ ; 30 >
λ2
x5
B
α 5
λ2
0
3
-1
3
1
30
-1
30
0
6
1
-6
pro αrk < 0 děláme minimum
λ2 < -6 ; 3 >
λ3
x6
B
α 6
λ3
0
3
0
----
0
30
1
- 30
1
6
0
----
pokud neexistuje αrk < 0 pak klademe ∞
λ1 < - 30 ; ∞ >
intervaly přípustných změn složek bi spočteme tak, že k b ve výchozí tabulce při čteme horní a dolní mez λk
b1 = < - ∞ ; 9 + 30 > = < - ∞ ; 39 >
b2 = < 45 - 6 ; 45 + 3 > = < 39 ; 48 >
b2 = < 6 - 30 ; ∞ > = < - 24 ; ∞ >
oblast přípustných hodnot pro parametry λk spočteme tak, že modrá čísla ve výsledné tabulce přiřadíme k λk a dáme ≥ - zelená čísla ve sloupci b ve výsledné tabulce
0 λ1 – 1 λ2 + 0 λ3 ≥ -3
-1 λ1 - 1 λ2 + 1 λ3 ≥ -30
0 λ1 +1 λ2 + 0 λ3 ≥ -6
Dualita
a) Ax ≤ b
Ax ≤ b ( y ≥ 0
x ≥ 0 ( A(transponované)y ≥ c
cy = zmax ( by = fmin
b) Ax ≥ b vynásobíme celé -1
- Ax ≤ - b ( y ≥ 0
x ≥ 0 ( A(transponované)y ≥ c
cy = zmax ( by = fmin
c) Ax = b
Ax = b ( y = libovolné
x ≥ 0 ( A(transponované)y ≥ c
cy = zmax ( by = fmin
příklad
x1
+
3x2
≥
8
x1
+
3x2
≤
8
2x1
+
5x2
=
8
x1
≥
0
x2
libovolné
z = 2x1 + 4x2 … max
První rovnici děláme podle b)
Druhou rovnici děláme podle a)
Třetí rovnici děláme podle c)
- x1 - 3 x2 ≤ -8 y1- y1 + y2 + 2 y3 ≥ 2
+ x1 + 3 x2 ≤ 8 y2- 3 y1 + 3 y2 + 5 y3 = 4
2 x1 + 5 x2 = 8 y3y1,2 ≥ 0
x1 ≥ 0 y3 = libovolné
x2 = libovolné
z = 2 x1 + 4 x2 … maxf = - 8 y1 + 8 y2 + 8 y3 … min
čísla se v nerovnicích mění podle barev
duální simplexové metoda
řeší se stejně jako simplexová tabulka akorát nesnažíme se změnit čísla v řádku zj - cj , ale měníme čísla ve sloupci b ( při minimalizaci musíme dostat čísla kladná nebo 0, při maximalizaci záporná nebo 0 )
dopravní úloha
Metoda Severozápadního rohu
Objekty
Hony
Kapacity
1.
2.
3.
4.
1.
9
8
9
4
50
2.
7
6
5
8
76
3.
7
7
4
8
96
4.
5
4
9
7
84
Požadavky
88
62
84
72
1) nejdříve si ověříme, že součet kapacit se rovná součtu požadavků
Kapacity: 50 + 76 + 96 + 84 = 306
Požadavky: 88 + 62 + 84 + 72 = 306
2) pak zapíšeme nejvyšší možné číslo do levého horního rohu (číslo nesmí být větší než kapacity nebo požadavky) v našem případě 50 .
3)Pokud jsou vyčerpány kapacity v prvním řádku napíšeme rozdíl mezi požadavky a kapacitami do 1 sloupečku druhého řádku, v případě, že jsou vyčerpány požadavky píšeme do rozdíl do prvního řádku a druhého sloupce. V našem příkladě byly vyčerpány kapacity, rozdíl činí 88-50 = 38 , který napíšeme do prvního sloupce a druhého řádku.
4)Takto pokračujeme až do posledního řádku a sloupce tabulky.V našem příkladě jsme v třetím kroku vyčerpali požadavky prvního sloupce, proto rozdíl 76 – 38 = 38 napíšeme do druhého sloupce a druhého řádku.
hony
objekty
1
2
3
4
kapacity
1
50 9
8
9
4
50
2
38 7
38 6
5
8
76
3
7
24 7
72 4
8
96
4
5
4
12 9
72 7
84
požadavky
88
62
84
72
306
5) provedeme kontrolu počtu spojů, musí jich být m + n – 1
v našem příkladě 4 + 4 – 1 = 7
6) spočteme řešení
z = 50*9 + 38* 7 + 38*6 + 24*7 + 72*4 + 12*9 + 72*7 = 2012
Indexová metoda
Objekty
Hony
Kapacity
1.
2.
3.
4.
1.
9
8
9
4
50
2.
7
6
5
8
76
3.
7
7
4
8
96
4.
5
4
9
7
84
Požadavky
88
62
84
72
1) nejdříve si ověříme, že součet kapacit se rovná součtu požadavků
Kapacity: 50 + 76 + 96 + 84 = 306
Požadavky: 88 + 62 + 84 + 72 = 306
2) Najdeme v dopravní tabulce číslo s nejmenší cenou, toto místo obsadíme nejvyšším možným množstvím zboží. V našem případě je to buňka 1- 4 s cenou 4 a číslo 50 což je maximální kapacita, v tomto kroku vypíšeme i buňky 3 – 3 také s cenou 4 a číslem 84
spotřebujeme všechny požadavky a u buňky 4 – 2 s cenou 4 číslo 62 což je maximální požadavek
hony
objekty
1
2
3
4
kapacity
1
9
8
9
50 4
50
2
6
5
8
76
3
7
84 4
8
96
4
62 4
9
7
84
požadavky
88
62
84
72
306
3) Vyškrtneme řádky a sloupce, v kterých jsme vyčerpali požadavky nebo kapacity a spočteme zůstatky
hony
objekty
1
2
3
4
kapacity
1
9
8
9
50 4
0
2
6
5
8
76
3
7
84 4
8
12
4
62 4
9
7
22
požadavky
88
0
0
22
306
4) pokračujeme podle bodu 2) dokud nevyčerpáme všechny kapacity a požadavky
hony
objekty
1
2
3
4
kapacity
1
9
8
9
50 4
0
2
54 7
6
5
22 8
0
3
12 7
7
84 4
8
0
4
22 5
62 4
9
7
0
požadavky
0
0
0
0
306
5) provedeme kontrolu počtu spojů, musí jich být m + n – 1
v našem příkladě 4 + 4 – 1 = 7
6) spočteme řešení
z = 54*7 + 12*7 + 22*5 + 62*4 + 84*4 + 50*4 + 22*8 = 1532
Metoda VAM
Objekty
Hony
Kapacity
1.
2.
3.
4.
1.
9
8
9
4
50
2.
7
6
5
8
76
3.
7
7
4
8
96
4.
5
4
9
7
84
Požadavky
88
62
84
72
1) Data přepíšeme do tabulky, kterou rozšíříme o sloupec ∆r a řádek ∆s do tohoto sloupce a řádku zapisujeme rozdíly mezi nejnižší cenou v řádku respektive sloupci a jejím nejmenším sousedem.V našem případě červená čísla. Pak vybereme největší rozdíl z ∆r a ∆s a zároveň nejmenší sazbu. V našem případě zelenou čtyřku. Do tohoto pole napíšeme největší možné číslo, abychom pokryli kapacity nebo požadavky.V našem případě jde o hnědé číslo 50. Pokud jsme vyčerpali požadavky vyškrtneme sloupec, pokud kapacity vyškrtneme řádek.V našem případě řádek 1.
hony
objekty
1
2
3
4
kapacity
∆r
1
9
8
9
50 4
50
5=9-4
2
7
6
5
8
76
1=6-5
3
7
7
4
8
96
3=7-4
4
5
4
9
7
84
1=5-4
požadavky
88
62
84
72
306
∆s
2=7-5
3=7-4
1=5-4
4=8-4
2) Takto pokračujeme dokud nemáme doplněnou celou tabulku.Vyškrtnutý sloupec respektive řádek vynecháváme. Kapacity a požadavky přepočítáme.V našem případě jde o zelenou čtyřku v 3 řádku.Doplnili jsme hnědé číslo 84, čímž jsme vyškrtli sloupec 2.
Hony
objekty
1
2
3
4
kapacity
∆r
1
9
8
9
50 4
0
2
7
6
5
8
76
1=6-5
3
7
7
84 4
8
96
3=7-4
4
5
4
9
7
84
1=5-4
požadavky
88
62
84
22
306
∆s
2=7-5
3=7-4
1=5-4
1=8-7
Hony
objekty
1
2
3
4
kapacity
∆r
1
9
8
9
50 4
0
2
7
6
5
8
76
1=7-6
3
7
7
84 4
8
12
0=7-7
4
5
62 4
9
7
84
1=5-4
požadavky
88
62
0
22
306
∆s
2=7-5
3=7-4
1=8-7
Hony
objekty
1
2
3
4
kapacity
∆r
1
9
8
9
50 4
0
2
7
6
5
8
76
1=8-7
3
7
7
84 4
8
12
1=8-7
4
22 5
62 4
9
7
22
2=7-5
požada
Vloženo: 26.04.2009
Velikost: 1007,00 kB
Komentáře
Tento materiál neobsahuje žádné komentáře.
Mohlo by tě zajímat:
Skupina předmětu EAE02E - Ekonomicko matematické metody II.
Reference vyučujících předmětu EAE02E - Ekonomicko matematické metody II.
Podobné materiály
Copyright 2024 unium.cz