FAKULTA INFORMATIKY A MANAGEMENTU UNIVERZITA HRADEC KRÁLOVÉ
SEMESTRÁLNÍ PRÁCE Modely operačního výzkumu 1
Vypracoval: Studijní obor: Emailová adresa: Datum vypracování:
Jana Pospíšilová IM2-KF
[email protected] 11. února
Obsah 1.
Zadání seminární práce ........................................................................................ 3
2.
1. příklad – Optimalizační úloha – Výrobní plánování.......................................... 5 2.1. Zadání .................................................................................................................. 5 2.2. Matematický model úlohy .................................................................................. 6 2.3. Optimalizační systém Lingo ................................................................................ 7 2.3.1 Model bez podmínky celočíselnosti .............................................................. 7 2.3.2 Model s podmínkou celočíselnosti ................................................................ 7 2.3.2 Výsledek bez podmínky celočíselnosti .......................................................... 8 2.3.2 Výsledek s podmínkou celočíselnosti ............................................................ 8 2.4. Interpretace získaných výsledků......................................................................... 9
3.
2. příklad – maximalizační úloha LP ................................................................... 10
4.
3. příklad – definovaný neorientovaný graf ....................................................... 11
5.
4. příklad – orientovaný graf .............................................................................. 12
6.
5. příklad – Jednoduchý exponenciální model ................................................... 15
7.
6. příklad – Úloha vícekriteriálního hodnocení variant ...................................... 16
1. Zadání seminární práce 2. Vymyslete si vlastní zadání optimalizační úlohy jednoho z následujících typů: úloha výrobního plánování, směšovací problém, úloha o dělení materiálu, tak, aby to vedlo na matematický model alespoň s pěti strukturními proměnnými a třemi omezujícími podmínkami (do tohoto počtu se nezahrnují případné dolní a horní meze proměnných, tj. omezující podmínky typu, že proměnná má být větší nebo naopak menší než zadaná hodnota). Udělejte následující: formulujte matematický model úlohy, vyřešte model na počítači pomocí některého optimalizačního systému (Excel, Lingo), podrobně interpretujte získané výsledky (včetně stínových a redukovaných cen). max. 8 b. 2. 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. max. 6 b. 3. V následující tabulce je definovaný neorientovaný graf – vždy počáteční uzel, koncový uzel a ohodnocení hrany: max. 6 b. 1 2 7
1 3 MM
2 3 4
2 4 6
2 5 2
3 4 12
3 6 4
4 5 DD/2
4 6 9
5 6 6
5 7 MM/2
6 7 14
Vypočtěte vhodným algoritmem nejkratší cestu mezi prvním uzlem a všemi ostatními uzly. Pozn. DD a MM je číslo odpovídající Vašemu dni a měsíci narození – případné výrazy zaokrouhlete na celé hodnoty nahoru. 4. V grafu, který je definovaný ve výše uvedené tabulce, uvažujte orientované hrany (orientace vždy z uzlu s nižším indexem do uzlu s vyšším indexem). Na tomto grafu vypočtěte kritickou cestu metodou CPM a navrhněte rozvržení činností. max. 6 b.
5. Do městského informačního centra, kde je jedna pracovnice, přichází průměrně DD/2 (den narození/2 zaokrouhlený na celá čísla nahoru) informací chtivých turistů za hodinu (intervaly mezi příchody mají exponenciální rozdělení). Doba obsluhy každého z nich je průměrně 3 minuty (exponenciální rozdělení). Vypočtěte základní charakteristiky
(průměrný počet jednotek v systému a ve frontě a průměrný čas strávený v systému a frontě) a dále pravděpodobnost, že ve frontě budou tři a více turistů. max. 6 b. 6. Definujte si vlastní reálnou úlohy vícekriteriálního hodnocení variant (součin počtu variant a počtu kritérií musí být alespoň 30) a uspořádejte varianty metodou váženého součtu – váhy kritérií si stanovte sami podle svých preferencí. max. 8 b.
Práci je třeba poslat elektronicky na adresu
[email protected] alespoň týden před termínem zkoušky. Ke zkoušce potom přinést práci vytištěnou.
2. 1. příklad – Optimalizační úloha – Výrobní plánování
2.1. Zadání Firma Nábytek s.r.o. je truhlářská firma, která se zabývá výrobou menšího nábytku: kuchyňský stůl, noční stolek, tv stůl, psací stůl 1 se 2 šuplíky, psací stůl 2 se 4 šuplíky, Pc stůl. K výrobě těchto produktů je potřeba rozvrhnout časovou jednotku výroby na několik fází. První fází je zpracování dřeva – tz. příprava konstrukce pro další použití. Druhou fází je broušení, 3. fází je sestavení a poslední fází je čištění a lakování.
Druh nábytku / Fáze výroby kuchyňský stůl
zpracování dřeva 2
1,1
2,5
čištění a lakování 1
broušení sestavení
zisk v závazné omezení Kč objednávky výroby 1000 100
noční stolek
1,5
0,5
2
0,8
500
Tv stůl
2,3
1,7
3
2
1200
psací stůl 1 - 2zásuvky
1,8
1,2
2,2
1,5
1000
psací stůl 2 - 4zásuvky
2,3
1,7
3,5
2
1200
Pc stůl
2,7
1,9
3,4
2,2
1300
8000
5000
9000
6000
max.počet hodin na jednotlivé fáze za měsíc
60 80 30 70
Popis tabulky: Kuchyňský stůl=x1: Na výrobu jednoho kuchyňského stolu jsou potřeba 2 jednotky času na první fázi zpracování dřeva, na druhou fázi broušení 1,1 jednotek času, na sestavení 2,5 jednotek času a na konečnou fázi čistění a lakování je potřeba 1 jednotka času. Zisk z jednoho prodaného kusu činí 1000Kč. Vzhledem k odbytu je výroba omezená na 100 kusů za měsíc. Noční stolek=x2: Na výrobu jednoho nočního stolku je potřeba 1,5 jednotek času na první fázi zpracování dřeva, na druhou fázi broušení 0,5 jednotek času, na sestavení 2 jednotky času a na konečnou fázi čistění a lakování je potřeba 0,8 jednotek času. Zisk z jednoho prodaného kusu činí 500Kč. Na tento výrobek je uzavřená závazná objednávka s odběratelem na 60 kusů za měsíc. Tv stůl=x3: Na výrobu jednoho televizního stolu jsou potřeba 2,3 jednotky času na první fázi zpracování dřeva, na druhou fázi broušení 1,7 jednotek času, na sestavení 3 jednotky času a na
konečnou fázi čistění a lakování jsou potřeba 2 jednotky času. Zisk z jednoho prodaného kusu činí 1200Kč. Psací stůl 1 – 2zásuvky =x4: Na výrobu jednoho psacího stolu č. 1 je potřeba 1,8 jednotek času na první fázi zpracování dřeva, na druhou fázi broušení 1,2 jednotek času, na sestavení 2,2 jednotek času a na konečnou fázi čistění a lakování je potřeba 1,5 jednotek času. Zisk z jednoho prodaného kusu činí 1000Kč. Vzhledem k odbytu je výroba omezená na 80 kusů za měsíc. Psací stůl 2 – 4zásuvky =x5: Na výrobu jednoho psacího stolu č. 2 je potřeba 2,3 jednotky času na první fázi zpracování dřeva, na druhou fázi broušení 1,7 jednotek času, na sestavení 3,5 jednotek času a na konečnou fázi čistění a lakování jsou potřeba 2 jednotky času. Zisk z jednoho prodaného kusu činí 1200Kč. Na tento výrobek je uzavřená závazná objednávka s odběratelem na 30 kusů za měsíc. PC stůl=x6: Na výrobu jednoho PC stolu je potřeba 2,7 jednotek času na první fázi zpracování dřeva, na druhou fázi broušení 1,9 jednotek času, na sestavení 3,4 jednotek času a na konečnou fázi čistění a lakování je potřeba 2,2 jednotek času. Zisk z jednoho prodaného kusu činí 1300Kč. Vzhledem k odbytu je výroba omezená na 70 kusů za měsíc.
2.2. Matematický model úlohy Proměnné: x1,x2,x3,x4,x5,x6
Účelová funkce: Max. zisku = 1000*x1 + 500*x2 + 1200*x3 + 1000*x4 + 1200*x5 + 1300*x6
Strukturální omezení: Zpracování
2*x1 + 1,5*x2 + 2,3*x3 + 1,8*x4 + 2,3*x5 + 2,7*x6
Broušení
1,1*x1 + 0,5*x2 + 1,7*x3 + 1,2*x4 + 1,7*x5 + 1,9*x6
Sestavení
2,5*x1 + 2*x2 + 3*x3 + 2,2*x4 + 3,5*x5 + 3,4*x6
Čištění a lakování
1*x1 + 0,8*x2 + 2*x3 + 1,5*x4 + 2*x5 + 2,2*x6
Kuchyňský stůl x1<=100 Psací stůl1 x4<= 80 PC stůl x6<= 70 Noční stolek x2>= 60 Psací stůl2 x5 >= 30 Podmínky nezápornosti: X1>=0
x4>=0
x2>=0
x5>=0
x3>=0
x6>=0
2.3. Optimalizační systém Lingo
2.3.1 Model bez podmínky celočíselnosti
2.3.2 Model s podmínkou celočíselnosti
2.3.2 Výsledek bez podmínky celočíselnosti
2.3.2 Výsledek s podmínkou celočíselnosti
2.4. Interpretace získaných výsledků Z výsledků, které jsme získali pomocí programu Lingo, jsme došli k optimálnímu řešení při maximálním zisku 3 576 900Kč měsíčně. Při kombinaci výroby: Kuchyňský stůl: 100ks, což je omezené množství výroby. Noční stolek: 88ks, což je 28ks nad potřebnou minimální výrobu. TV stůl: 2 763ks, je pro firmu nejvýhodnější vyrábět, z důvodu neomezenosti výroby, vzhledem k ceně a odbytu je pro firmu velice významným. Psací stůl 1: 80ks, což je zároveň omezené množství výroby. Psací stůl2: 30ks, jedná se pouze o výrobu na závaznou objednávku. PC stůl: 1ks, jedná se o téměř zanedbatelnou výrobu, mělo by se zde uvažovat, zda je vůbec výhodné tento produkt vyrábět.
Proměnné: Pro proměnné broušení a sestavení byla využita veškerá časová kapacita. U proměnné zpracování dřeva bylo nevyužito 1097.053hodin a u poslední fáze výrobku čištění a lakování nebylo využito 121.2421 hodin. Tyto výsledky jsou interpretovány z výsledků bez podmínky celočíselnosti.
Redukované ceny: Jelikož tato firma bude vyrábět všechny druhy výrobků, nejsou v tomto případě uvedeny žádné redukované ceny.
Stínové ceny: Jedno broušení se podílí na zisku částkou 473,6842 Kč a jedno sestavení částkou 131,5789 Kč. Na zpracování dřeva a konečné čistění a lakování je k dispozici dostatek času, z toho důvodu nemají na výrobu žádný vliv.
3. 2. příklad – maximalizační úloha LP Výroba dvou výrobků x1 a x2, maximální počet výrobků x2 je 30ks. Souřadnice krajních bodů přípustné oblasti zjistíme vždy pomocí řešení soustavy 2rovnic, které vycházejí z omezujících podmínek. výroba x1 (hod/ks) x2 (hod/ks)
3 1 30 Kč
K1 K2 K3 -limit zisk
řešení výroby
proměnné ks x1 x2
0 0 20 23,6 33,00
1 2 3 4 5
1 2 1 22 Kč
Kapacita (hod)
Účelová kriteriální funkce
99 80 30
z = 30x1 + 22x2 =0 Celková spotřeba
K1 → 3x1 + x2 ≤ 99 K2 → x1 + 2x2 ≤ 80 K3 → x2 ≤ 30
hodnota (z) 0 Kč 660 Kč 1 304 Kč 1 328,4 Kč 825 Kč
0 30 32 28,2 0
Podmínka nezápornosti
x1 ≤ 0, x2 ≤ 1 Údaje získány pomocí řešitele
Optimální řešení
x1 = x2 =
Hodnota účelové funkce z=
24 28
1336
max návrh
3
1
0
30
x1= 23,6
1
2
1
22
x2= 28,2
99 99
80 80
30 28,2
Hodnota účelové
1328,4
x2
100
3x1 + x2 ≤ 99
89
50
40
x2 ≤ 30
30
20
0
33
70
100
x1
x1 + 2x2 ≤ 80 z=0
z=1328
Hodnota účelové funkce je 1328,4, vzhledem v nutnosti celočíselného zpracování musíme optimální řešení (na grafu znázorněno přímkou z) zaokrouhlit na celé ks výrobků X1=24, x2=28 → hodnota účelové funkce je 1336,- Kč.
4. 3. příklad – definovaný neorientovaný graf
i
1
ti
0
j (yij) 2(7)
2
3(4)
3
6
3(4)
3(12) 4(6) 4(12) 3(12) 4(3)
4(9)
6(4)
5(6)
i
1
2
3
ti
0
7
11
3(4)
2(4)
j (yij) 2(7)
2(6)
5
2(2)
5(2)
2(4)
4
5(3)
6(6)
6(9)
7(6) 7(14)
4
6
2(2)
3(4)
3(12) 4(6) 4(12) 3(12) 4(3)
4(9)
6(4)
5(6)
5(2)
2(6)
5
5(3)
6(6)
6(9)
7(6) 7(14)
i
1
2
3
4
5
ti
0
7
11
12
9
3(4)
2(4)
2(6)
2(2)
3(4)
3(12) 4(6) 4(12) 3(12) 4(3)
4(9)
6(4)
5(6)
j (yij) 2(7)
5(2)
6
5(3)
6(6)
6(9)
7(6) 7(14)
7
i
1
2
3
4
5
6
ti
0
7 2(4)
2(6)
2(2)
3(4)
3(12) 4(6) 4(12) 3(12) 4(3)
4(9)
6(4)
5(6)
j (yij) 2(7)
3(4)
5(2)
7
6(6)
6(9)
7(6) 7(14)
i
1
2
3
4
5
6
ti
0
7
11
12
3(4)
2(4)
2(6)
2(2)
3(4)
3(12) 4(6) 4(12) 3(12) 4(3)
4(9)
6(4)
5(6)
j (yij) 2(7)
5(2)
7
5(3)
5(3)
6(6)
6(9)
7(6) 7(14)
7
7
i
1
2
3
4
5
6
7
ti
0
7
11
12
9
15
15
3(4)
2(4)
2(6)
2(2)
3(4)
3(12) 4(6) 4(12) 3(12) 4(3)
4(9)
6(4)
5(6)
j (yij) 2(7)
5(2)
5(3)
6(6)
6(9)
7(6) 7(14)
Jako výchozí hodnotu t1=0 si zvolíme uzel 1. Výchozí uzly hran najdeme v tabulce pod označením i=1,2,3,4,5,6,7. Dále pod nimi nalezneme koncové uzly hran. 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.
Výsledek nejkratších cest z grafu můžeme zapsat do následující tabulky. cesta
délka
cesta= jednotlivé cesty z uzlů 1 do
trasa
1
2
7
1
2
dalších uzlů
1
3
12
1
3
délka=délka cesty
1
4
13
1
2
4
1
5
9
1
2
5
1
6
16
1
3
6
1
7
15
1
2
5
trasa=posloupnost uzlů při cestě
7
5. 4. příklad – orientovaný graf
Výpočet kritické cesty pomocí metody CPM Výpočet kritické cesty neboli minimálně možné cesty provádíme z výchozího uzlu 1 do koncového uzlu 7. Tato metoda se skládá ze 4 fází.
1. Fáze Jedná se o výpočet nejdříve možných začátků a konců provádění činností, který je
t j0 max (ti0 yij ) . i
dán vzorcem
t01 = 0 – vstupní hodnota uzlu
yij - doba činností z u uzlu i do j T = t0n – nejkratší možná doba, ve které lze projekt realizovat -současně se jedná o ohodnocení nejdelší cesty, v našem případě T = 47
2. Fáze Tato fáze obsahuje nejpozději přípustné začátky a konce provádění činností dle vzorce:
ti1 min (t 1j yij .) j
i=7 tj.
t71
- výchozí hodnota uzlu 7
yij - doba činnosti z uzlu i do j
3. Fáze Souvisí se samotným výpočtem celkových časových rezerv, což je rozdíl mezi nejpozději přípustným koncem, nejdříve možným začátkem a dobou trvání činnosti podle 1 0 vzorce: CRij t j ti yij .
Časové rezervy jsou uvedeny v závorkách u jednotlivých dob činností. Kritická cesta je na grafu znázorněna červeně. Jedná se o posloupnost činností, jejichž hodnota časové rezervy je minimální tedy nulová. Kritická cesta je 1-3-4-6-7, jejíž doba trvání je T=47. 4. Fáze Rozvržení činností činnost 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 1 3 3 4 4 6 6 7 1 2 2 3 2 4 2 5 3 6 4 5 5 6 5 7 posloup. 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 1 1-3 3-4 4-6 6-7 2 1-2 2-3 3-6 4-5 5-6 3 2-5 2-4 5-7
6. 5. příklad – Jednoduchý exponenciální model Jedná se o model hromadné obsluhy typu M/M/I. Zadání: 1 pracovnice, průměrně DD/2=3turisti/hodinu, doba obsluhy průměrně 3minuty – exponenciální rozdělení. a)průměrný počet jednotek v systému a ve frontě b)průměrný čas strávený v systému a ve frontě c)pravděpodobnost, že ve frontě budou 3 a více turistů
= 3 (průměrný počet příchodů za hodinu) E(X) = 1/3 = 0,33 ( střední hodnota intervalů mezi příchody v hodinách) EX) = 20 (střední doba mezi příchody v minutách) E(X) = 3 (střední doba obsluhy v minutách) E(X) = 0,05 (střední doba obsluhy v hodinách) μ= 1/0,05 = 20 (počet odbavených turistů za hodinu) a) Průměrný čas strávený v systému (T) a ve frontě (Tf)
T
1
Tf T
T= 1/20-3 = 0,06 hod
1
( )
Tf = 0,06- 1/20= 0,01 hod
b) Průměrný počet jednotek (požadavků) v systému (N) a ve frontě (Nf)
N T N= 0,18
N f Tf
2 ( )
Nf=0,03
c)pravděpodobnost 3 a více turistů ve frontě
= / < 1 – podmínka stabilizace (0,15<1) = splňuje podmínku Počet turistů – 1 u přepážky, 3 a více ve frontě n>=4
= / - 0,15 (pravděpodobnost, že v systému je alespoň jeden požadavek)
pn = p0 n = (1 )n (pravděpodobnost, že v1požadavek je obsluhován a (n-1) je ve frontě n pn n+náledující
4 0,0430% 0,0430%
5 6 7 8 0,0065% 0,0010% 0,0001% 0,0000% 0,0495% 0,0505% 0,0506% 0,0506%
9 10 11 12 13 0,0000% 0,0000% 0,0000% 0,0000% 0,0000% 0,0506% 0,0506% 0,0506% 0,0506% 0,0506%
Pravděpodobnost, že ve frontě budou 3 a více turistů je okolo 0,05%.
7. 6. příklad – Úloha vícekriteriálního hodnocení variant Firma chce nakoupit notebook pro kancelářskou činnost, z tohoto důvodu nemá vysoké nároky na technické parametry. V následující tabulce můžeme vidět značky notebooků –HP, Packart Bell, Lenovo, Acer, Asus a Toshiba. Podle rozvržených vah můžeme vidět jak jsou pro nás důležité maximalizační a minimalizační kritéria.
Metoda váženého součtu - WSA
Y zadaná= cena v Kč paměť (GB) MIN/MAX MIN MAX Váhy 8 HP 6600 Packart Bell 6680 Lenovo 8000 Acer 7000 Asus 7000 Toshiba 8 500
výdrž baterie hmotnost velikost (hod) (kg) (úlopříčka) MAX
8 320 320 500 320 320 500
MIN 6 6 4.5 4 4 3 6
MIN 7 2.45 2.5 2.6 1.38 2.4 2.1
5 15.6 15.6 15.6 11.6 15.6 15.6
Ymax= výdrž hmotnost velikost cena v Kč paměť (GB) baterie (kg) (úlopříčka) (hod) min/max max* max max max* max* HP 1900 320 6 0.15 0 Packart Bell 1820 320 4.5 0.1 0 Lenovo 500 500 4 0 0 Acer 1500 320 4 1.22 4 Asus 1500 320 3 0.2 0 Toshiba 0 500 6 0.5 0
Z důvodu, že součet vah není roven jedné, je potřeba tyto váhy transformovat na jednotkový součet. Stačí váhy vydělit číslem 34(součtem původních vah). Váhy-původní Váhy-transformované
8 0.235
8 0.235
6 0.176
7 0.206
5 0.147
Výsledky úlohy vícekriteriálního hodnocení variant V následující tabulce můžeme vidět výsledky hodnocení podle metody váženého součtu. Tato metoda je založena na hodnocení na stupnici od 0 do 1. Čím více se číslo přibližuje k 1, tím více užitku nám přináší. Jako nejlepší varianta je varianta nákupu notebooku Acer, poté Toshiba, HP, Lenovo, Packart Bell a na posledním místě je notebook značky Asus. cena v Kč Váhy HP Packart Bell Lenovo Acer Asus Toshiba
0.235 1 0.958 0.263 0.789 0.789 0
paměť (GB) 0.235 0 0 1 0 0 1
výdrž baterie hmotnost velikost (hod) (kg) (úlopříčka) 0.176 0.206 0.147 1 0.123 0 0.5 0.082 0 0.333 0 0 0.333 1 1 0 0.164 0 1 0.41 0
u(Xi) 0.4370 0.3305 0.3560 0.5975 0.2195 0.4961
