FAKULTA INFORMATIKY A MANAGEMENTU UNIVERZITA HRADEC KRÁLOVÉ
MOV 1 SEMESTRÁLNÍ PRÁCE
Vypracoval: Studijní obor: Emailová adresa: Datum vypracování:
Lenka Novotná K-Informační management
[email protected] Březen 2013
1 Obsah
1
Obsah ....................................................................................................................... 2
2
Optimalizační úloha – úloha výrobního plánování .................................................. 3 2.1
Ekonomický model ........................................................................................... 3
2.2
Matematický model.......................................................................................... 4
2.3
Řešení pomocí optimalizačního systému Lingo ................................................ 4
2.4
Interpretace získaných výsledků....................................................................... 6
3
Maximalizační úloha LP ............................................................................................ 7
4
Neorientovaný graf .................................................................................................. 9
5
Orientovaný graf (metoda CPM)............................................................................ 10
6
Exponenciální model .............................................................................................. 12
7
Vícekriteriální hodnocení variant ........................................................................... 13
2
2 Optimalizační úloha – úloha výrobního plánování 2.1 Ekonomický model Malá soukromá firma se zabývá ruční výrobou hraček z přírodního materiálu. Plánuje uvést na trh pět nových hraček a to vláček, autíčko, traktor, kombajn a popelářské auto. Výroba uvedených hraček zahrnuje fázi hrubé opracování dřeva, broušení, montáž a barvení. Cílem je naplánovat měsíční výrobu tak, aby přinesla co největší zisk. Hračka/
Hrubé
Fáze výroby
opracování
Mašinka
2,0
Autíčko
Broušení
Prodejní
Typ
cena v Kč
omezení
2,1
230
Min. 100
1,2
1,1
200
1,1
1,7
1,8
250
Min. 150
1,6
1,3
1,6
1,0
280
Max. 80
1,8
1,1
1,5
1,4
240
Max. 60
5000
3500
4500
4500
Montáž
Barvení
1,2
1,5
1,5
1,0
Traktor
1,8
Kombajn Popeláři Max. hod/měsíc
Mašinka: na jednotlivé fáze výroby jsou zapotřebí jednotky času 2,0; 1,2; 1,5; a 2,1. Prodejní cena je 230,- Kč/ks. S odběrateli jsou již uzavřené objednávka na 100 ks. Autíčko: na jednotlivé fáze výroby jsou zapotřebí jednotky času 1,5; 1,0; 1,2 a 1,1. Prodejní cena je 200,- Kč/ks. Traktor: na jednotlivé fáze výroby jsou zapotřebí jednotky času 1,8; 1,1; 1,7 a 1,8. Prodejní cena je 250,- Kč. S odběrateli jsou již uzavřené objednávky na 150 ks. Kombajn: na jednotlivé fáze výroby jsou zapotřebí jednotky času 1,6; 1,3; 1,6 a 1,0. Prodejní cena je 280,- Kč. Z důvodu skladových zásob sekacího zařízení ke kombajnu, je množství omezeno na max. 80 ks. Popeláři: na jednotlivé fáze výroby jsou zapotřebí jednotky času 1,8; 1,1; 1,5 a 1,4. Prodejní cena je 240,- Kč/ks. Z důvodu zvedacího zařízení u popelářského auta je množství omezeno na 60 ks.
3
2.2 Matematický model Proměnné: x1, x2, x3, x4, x5 .
Účelová (kriteriální) funkce: z = 230*x1 + 200*x2 + 250*x3 + 280*x4 + 240* x5 . (maximalizace zisku)
Vlastní omezení: Hrubé opracování
2,0*x1 + 1,5*x2 + 1,8*x3 + 1,6*x4+ 1,8*x5 <= 5000 ;
Broušení
1,2*x1 + 1,0*x2 + 1,1*x3 + 1,3*x4 + 1,1*x5 <= 3500 ;
Montáž
1,5*x1 + 1,2*x2 + 1,7*x3 + 1,6*x4 + 1,5*x5 <= 2500 ;
Barvení
2,1*x1 + 1,1*x2 + 1,8*x3 + 1,0*x4 + 1,4*x5 <= 4500.
Mašinka
x1 >= 100
Traktor
x2 >= 150
Kombajn
x4 <= 80
Popeláři
x5 <= 60
Omezení nezápornosti: x1 >= 0
x2 >= 0
x3 >= 0
x4>= 0
x5>= 0.
2.3 Řešení pomocí optimalizačního systému Lingo Zadaní v sytému Lingo bez podmínky celočíselnosti
4
Zadání v systému Lingo s podmínkou celočíselnosti
Výsledek bez podmínky celočíselnosti
5
Výsledek s podmínkou celočíselnosti
2.4 Interpretace získaných výsledků Optimální řešení zadané úlohy získané pomocí systému Lingo je následující: Maximální zisk 684. 650,- Kč, při následující kombinaci výroby: Mašinka 100 ks, což je minimální potřebné množství, na které existující uzavřené objednávky. Autíčko 1.155 ks, neomezenost výroby, významný produkt pro výrobu z důvodu ceny. Traktor 1.633 ks, což je o 1483 ks více než jsou uzavřené objednávky, významný produkt pro výrobu z důvodu ceny. Kombajn 80 ks, což je maximální množství z důvodu skladových zásob sekacího zařízení ke kombajnu. Popelářské auto 0 ks. Tento produkt není výhodné vyrábět a to z důvodu jeho ceny. 6
Z výsledků bez podmínky celočíselnosti získáváme informace o využitých/nevyužitých časových kapacitách. Pro fáze výroby (proměnné) opracování a barvení byla využita veškerá časová kapacita. U fáze broušení nebylo využito 324,6389 hodin, u fáze montáž zůstává nevyužito 59,80556 hodin. Dle redukovaných cen bychom cenu popelářského auta museli zvýšit o 1,667 Kč, aby se vyplatilo tento výrobek vyrábět. Stínové ceny. Jedno opracování výrobku se podílí na zisku částkou 118,0556 Kč, jedno barvení výrobku se podílí na zisku částkou 20,83333 Kč. Na fáze výroby broušení a montáž je dostatek času, z toho důvodu nemají na výrobu vliv.
3 Maximalizační úloha LP Vymyslete si sami zadání maximalizační úlohy lineárního programování – 2 strukturní proměnné a alespoň 3 omezující podmínky – tak, aby množina přípustných řešení měla alespoň 5 krajních bodů. Zadání stačí vymyslet numericky, nemusí být k tomu věcná interpretace. Nalezněte graficky optimální řešení této úlohy. Dále vypočtěte souřadnice všech krajních bodů a vypočtěte hodnoty účelové funkce pro tyto krajní body.
X1
X2
Omezení Funkce:
K1
2
2
60
60
X1
X2
K2
2
4
80
80
20
10
K3
0
3
48
30
Zisk
50
62
1620
Údaje získány pomocí řešitele.
Celková spotřeba:
Účelová funkce:
K1:
2x1+2x2 <=60
MAX: z = 50x1+62x2
K2:
2x1+4x2<=80
K3:
3x2<=48
Řešení řešení 1 řešení 2 řešení 3 řešení 4 řešení 5
proměnné X1 0 0 30 20 8
Optimální řešení:
Podmínka nezápornosti: =0
x1 ≤ 0, x2 ≤ 1
Zisk MAX
zbytek (+) / nedostatek (-)
X2 0 16 0 10 16
K1
K2
K3
60
80
48
28
16
0
0
20
48
0
0
18
12
0
0
0 992 1500 1620 1392
7
Grafické znázornění:
Hodnota účelové funkce je 1620,- Kč. Optimální řešení je znázorněno přímkou Z = Max, maximum účelové funkce je v bodě C.
Citlivostní zpráva Měněné buňky Konečná Redukovaný Buňka Název hodnota Gradient $F$3 K1 X1 20 0 $G$3 K1 X2 10 0 Omezující podmínky Konečná Lagrangeův Buňka Název hodnota multiplikátor $E$3 K1 60 19 $E$4 K2 80 6 $E$5 K3 30 0
8
4 Neorientovaný graf
Hodnoty uzlů vypočítáme postupně dle pravidel tk = mini,j (ti + yij), kdy k=2,3,4,5,6,7, i=index uzlů, pro něž hodnotu ti známe a j je index uzlů, pro které t j neznáme, ale z uzlu i vede do uzlu j hrana s ohodnocením Yij. Hodnoty t znamenají délku nejkratší cesty z uzlu 1. i
1
t
0
j(yij) 2(7)
2
3
3(4) 2(4)
4 2(6)
5 2(2)
6
7
3(4)
i
1
2
t
0
7
j(yij) 2(7)
3(12) 4(6) 4(12) 3(12) 4(14) 4(9) 5(2) 6(4) i
1
2
3
t
0
7
11
j(yij) 2(7)
3(4) 2(4)
5(14) 6(6)
5(6)
6(9)
7(14)
7(6) 4
2(6)
5 2(2)
6
5(6)
6(9)
7(14)
7(6)
i
1
2
3
4
5
t
0
7
11
13
9
j(yij) 2(7)
3(4) 2(4)
2(6)
2(2)
6 3(4)
3(12) 4(6) 4(12) 3(12) 4(14) 4(9) 5(2) 6(4)
5(14) 6(6)
5(6)
6(9)
7(14)
7(6)
2(6)
5(2) 6(4) 7
3(4)
5(14) 6(6)
3(4) 2(4)
4
5 2(2)
6
7
3(4)
3(12) 4(6) 4(12) 3(12) 4(14) 4(9) 5(14) 6(6)
5(6)
6(9)
7(14)
7(6)
i
1
2
3
4
t
0
7
11
13
j(yij) 2(7)
3(12) 4(6) 4(12) 3(12) 4(14) 4(9) 5(2) 6(4)
3
3(4) 2(4)
2(6)
5 2(2)
6
7
3(4)
3(12) 4(6) 4(12) 3(12) 4(14) 4(9) 5(2) 6(4) 7
5(14) 6(6)
5(6)
6(9)
7(14)
7(6)
i
1
2
3
4
5
6
7
t
0
7
11
17
9
15
15
j(yij) 2(7)
3(4) 2(4)
2(6)
2(2)
3(4)
3(12) 4(6) 4(12) 3(12) 4(14) 4(9) 5(2) 6(4)
5(14) 6(6)
5(6)
6(9)
7(14)
7(6)
Výsledek nejkratších cest grafu je popsán následující tabulkou:
9
5 Orientovaný graf (metoda CPM)
Výpočet kritické cesty pomocí minimálně možné cesty provádíme z výchozího uzlu 1 do koncového uzlu 7. Výpočet má 3- 4 fáze.
1. Fáze Výpočet nejdříve možných začátků a konců provádění činností. Vzorec:
tj0 = maxi (ti0 + yij) .
kde t10 = 0 (výchozí hodnota uzlu 1) yij je doba činnosti z uzlu i do uzlu j. Hodnota T = t70 je nejkratší možná doba, za jakou můžeme projekt uskutečnit (délka nejdelší cesty z uzlu 1 do uzlu 7), v níže uvedeném příkladě je T=47.
10
2. Fáze Nejpozději přípustné začátky a konce provádění činností. Vzorec: tj1 = mini (ti1 + yij) . i = 7, t71 = 0 (výchozí hodnota uzlu 7) yij je doba činnosti z uzlu i do uzlu j.
3. Fáze Jedná se o výpočet celkových časových rezerv. To je rozdíl mezi nejpozději přípustným koncem, nejdříve možným začátkem a dobou trvání činnosti podle vzorce CRij = T1j – t0i – yij . Časové rezervy jsou uvedeny v závorkách u jednotlivých dob činností. Kritická cesta je znázorněna červenou barvou. Jedná se o posloupnost činností, jejichž hodnota rezervy je nulová, tedy minimální. Kritická cesta je 1-3-4-5-6-7. Doba trvání je 58 časových jednotek.
11
4. Fáze Rozvržení činností
6 Exponenciální model Model hromadné obsluhy M/M/1 s parametry: 1 pracovnice, DD/2 = 14 turistů za hodinu (intervaly mezi příchody jsou exponenciálně rozděleny). Doba obsluhy průměrně 3 minuty – exponenciální rozdělení.
Vypočítat:
Průměrný počet jednotek v systému a ve frontě Průměrný čas stráveny v systému a ve frontě Pravděpodobnost, že ve frontě budou 3 a více turistů.
= 14
počet příchodů za časovou jednotku (hod)
1/ = 1/14 = 0,07
střední doba mezi příchody v hod
4,285 střední doba mezi příchody v min
= 1/0,05=
0,05
střední doba obsluhy v hod
3
střední doba obsluhy v min
20
počet odbavených turistů za hod
Průměrný počet jednotek v systému (N) N = T = / ( - )
N = 2,33 hod
Průměrný počet jednotek ve frontě (Nf) Nf = Tf = 2 / ( - )
Nf = 1,63 hod
Průměrný čas strávený v systému T = 1 / ( - )
T = 0,166 hod 12
Průměrný čas strávený ve frontě Tf = T – (1 / ) = / ( - )
Tf = 0,116 hod
Pravděpodobnost, že ve frontě budou 3 a více turistů P = / < 1 podmínka stabilizace (0,7 < 1) = splňuje podmínku. V centru bude 1 turista u přepážky a 3 a více ve frontě. N>=4
p = / - 0,7 (pravděpodobnost, že v systému je alespoň jeden požadavek.
Pn = p0 pn = (1 – p) * pn (pravděpodobnost, že jeden požadavek je obsluhován a (n-1) je ve frontě.
Pravděpodobnost, že ve frontě budou 3 a více turistů je 0,23 až 0,24 %.
7 Vícekriteriální hodnocení variant Cílem je výběr automatické pračky. Následující tabulka zobrazuje modely. U každé pračky hodnotíme největšími váhami cenu, poté spotřebu energie a vody, dále pak hlučnost a v poslední řadě počet otáček za minutu při procesu odstřeďování a náplň prádla. Údaje jsou převzaty z nabídky firmy Electroworld. Y zadání: Spotřeba Spotřeba Hlučnost energie vody (dB) (kW/rok) (l/rok)
Počet otáček /min
Náplň (kg)
MIN
MAX
MAX
7
6
5
5
8900 8999 8200 8790 7980 8900
57 59 59 57 59 59
1200 1400 1200 1400 1200 1200
6 7 6 6 5 4,5
Výrobce
Cena (v Kč)
MIN/MAX
MIN
MIN
MIN
Váhy
8
7
5 999 9 999 6 999 7 999 5 888 7 999
196 167 147 167 165 152
Candy AEG Whirpool Eletrolux LG Bosch
13
Y max: Spotřeba Spotřeba Hlučnost energie vody (dB) (kW/rok) (l/rok)
Počet otáček /min
Náplň (kg)
Výrobce
Cena (v Kč)
min/max Váhy
max* 8
max* 7
max* 7
MIN 6
MAX 5
MAX 5
Candy AEG Whirpool Eletrolux LG Bosch
4 000 0 3 000 2 000 4 111 2 000
0 29 49 29 31 44
99 0 799 209 1019 99
57 59 59 57 59 59
1200 1400 1200 1400 1200 1200
6 7 6 6 5 4,5
Transformace vah na jednotkový součet (součet původních vah 38): Váhy původní Váhy transformované
8
7
7
6
5
5
0,211
0,184
0,184
0,158
0,132
0,132
Přepočtení vah: Spotřeba Spotřeba Hlučnost energie vody (dB) (kW/rok) (l/rok)
Počet otáček /min
Náplň (kg)
Výrobce
Cena (v Kč)
min/max Váhy
max* 0,211
max* 0,184
max* 0,184
MIN 0,158
MAX 0,132
MAX 0,132
Candy AEG Whirpool Eletrolux LG Bosch
0,973 0,000 0,730 0,486 1,000 0,486
0,000 0,592 1,000 0,592 0,633 0,898
0,097 0,000 0,784 0,205 0,097 0,097
0 1 1 0 1 1
0 1 0 1 0 0
0,6 1,0 0,6 0,6 0,2 0,0
14
Výsledek hodnocení metody váženého součtu: Spotřeba Spotřeba Hlučnost energie vody (dB) (kW/rok) (l/rok)
Počet otáček /min
Náplň (kg)
MIN
MAX
MAX
0,184
0,158
0,132
0,132
0,018 0,000 0,144 0,038 0,018 0,018
0,000 0,158 0,158 0,000 0,158 0,158
0,000 0,132 0,000 0,132 0,000 0,000
0,079 0,132 0,079 0,079 0,026 0,000
Výrobce
Cena (v Kč)
min/max
max*
max*
max*
Váhy
0,211
0,184
0,205 0,000 0,154 0,102 0,211 0,102
0,000 0,109 0,184 0,109 0,117 0,165
Candy AEG Whirpool Eletrolux LG Bosch
Jako nejlepší byla vyhodnocena pračka od firmy
u (Xi)
0,302 0,530 0,719 0,460 0,529 0,444
Whirpool,
následuje
AEG,
poté
LG,
dále pak
Eletrolux
předposlední Bosch a poslední
Candy;
(čím více se číslo blíží 1, tím produkt více vyhovuje zvoleným vahám podmínek).
15
