Kvantitativní metody v rozhodování
Marta Doubková
Seminární práce 2008
OBSAH 1
LINEÁRNÍ PROGRAMOVÁNÍ – KAPACITNÍ ÚLOHA .................................... 3
2
DISTRIBUČNÍ ÚLOHA ............................................................................................ 7
3
ANALÝZA KRITICKÉ CESTY – METODA CPM ............................................ 13
4
MODEL HROMADNÉ OBSLUHY ....................................................................... 16
1
LINEÁRNÍ PROGRAMOVÁNÍ – KAPACITNÍ ÚLOHA
Společnost Drevounia s. r. o. vyrábí 5 typů židlí, které se zhotovují ve 4 střediscích, jejichž měsíční kapacita je postupně 2 600 h, 3 300 h, 4 200 h a 3 900 h. Aby společnost mohla vyrábět jednotlivé typy židlí, musí počítat s hodinovou spotřebou času, jak je uvedeno v tabulce. Společnost Drevounia musí na základě smluv uzavřených s odběrateli měsíčně vyrábět minimálně 800 ks židlí typu 1, 500 ks židlí typu 3 a 600 ks židlí typu 4, maximálně však 3 600 ks každého typu židle. Hrubý zisk, který plyne z výroby těchto židlí je 1300, 1 200, 1 400, 1 600 a 2 000 Kč/ks. Úkolem je sestavit takový výrobní program, který bude maximalizovat celkový zisk. Tabulka 1 Spotřeba času na výrobu
1. Rozbor činitelů Vstupní činitelé: Strojové hodiny Výstupní činitelé: Ž1, Ž2, Ž3, Ž4, Ž5
2. Definice proměnných x1 … počet vyrobených kusů židlí typu 1 x2 … počet vyrobených kusů židlí typu 2 x3 … počet vyrobených kusů židlí typu 3 x4 … počet vyrobených kusů židlí typu 4 x5 … počet vyrobených kusů židlí typu 5
3. Omezení na vstupu 0,3 x1 + 0,2 x2 + 0,4 x3 + 0,4 x4 +0,5 x5 ≤ 2 600 0,3 x1 + 0,5 x2 + 0,5 x3 + 0,4 x4 + 0,6 x5 ≤ 3 300 0,7 x1 + 0,9 x2 + 0,8 x3 + 0,8 x4 + 0,5 x5 ≤ 4 200 0,4 x1 + 0,4 x2 + 0,5 x3 + 0,4 x4 + 0,8 x5 ≤ 3 900 4. Omezení na výstupu 800 ≤
x
≤
3 600
≤
3 600
≤
3 600
≤
3 600
≤
3 600
1
0 ≤
x 2
500 ≤
x 3
600 ≤
x 4
0 ≤
x 5
5. Účelová funkce z 1300 x1 1200 x2 1400 x3 1600 x4
6. Řešení pomocí programu WinQSB
2000 x5
MAX
7. Interpretace výsledku: Z hlediska primárního modelu vstupních a výstupních omezení, která firma Drevounia musí při své výrobě zohlednit, bude optimální výroba činit 1 044 ks židlí 2. typu (tržby 1 252 800 Kč) , 873 ks židlí 4. typu (tržby 1 396 800 Kč) a 3 204 ks židlí 5. typu (tržby 6 408 000). Dále musí zmíněná firma z důvodu smluvního omezení s odběrateli vyrábět 800 ks židle 1. typu (tržby 1 040 000 Kč) a 500 ks židlí 3. typu (tržby 1 600 000 Kč), i když je výroba ztrátová. Celkové měsíční tržby (tj. maximální hodnota účelové funkce) jsou ve výši 10 797 600 Kč. Z pohledu řešení duálního modelu můžeme vidět, že kapacity střediska 1, střediska 3 a střediska 4 jsou plně využity. Pouze kapacita střediska 2 není plně využita. Z tohoto důvodu není nutné u tohoto střediska rozšiřovat kapacitu. Naopak tomu je u střediska 1, kde pokud bychom zvýšili kapacitu o 1 hodinu, zvýšila by se nám hodnota účelové funkce o 2 240 Kč. Pokud bychom zvýšili kapacitu 3. střediska o 1 h, účelová funkce by se nám zvýšila o 480 Kč a v případě 4. střediska by se zvýšila o 800 Kč. V tomto případě je důležitá úvaha nad tím, jaké náklady jsou spojeny s 1 h kapacity ve střediscích 1, 3 a 4 a zda se vzhledem k těmto skutečnostem vyplatí navýšit hodinovou kapacitu při výrobě. Skladba výroby se nebude měnit, jestliže se kapacita bude pohybovat v rozmezí 2 554,445 – 2 837,273 h v 1. středisku, dále alespoň 3 283,6 h v 2 středisku, v rozmezí 3 705 – 4 258,571 h v 3. středisku a v rozmezí 3 378 – 3920,5 h v posledním, 4. středisku. Dále se kapacita nebude měnit, jestliže u ztrátového typu židle 1 dodržíme podmínku doporučené ceny 1 328 Kč a více a u 2. typu židle minimálně 1 680 Kč a více. Ceny ostatních druhů židlí, tj. židle typu 2, 4 a 5 by se měly postupně pohybovat v intervalech 1112,5 – 1 709,1 Kč;1 536,4 – 1 828,6 Kč a 1 766,7 – 2 600 Kč.
2
DISTRIBUČNÍ ÚLOHA
Metoda VAM (Vogelova aproximační metoda) Společnost SIT s. r. o. se zabývá nákupem a prodejem židlí, který je spojen i s jejich montáží. V ČR má pronajaty celkem 4 sklady, které se nacházejí v Ústí nad Labem, Českých Budějovicích, Brně a Vsetíně. Kapacita těchto skladů je 150, 210, 250 a 190 ks židlí. Z těchto skladů se židle distribuují do pěti prodejen v Hradci Králové, Táboře, Jihlavě, Olomouci a Zlíně. Podle uzavřených smluv společnost SIT postupně svým odběratelům dodá 110, 140, 210, 170 a 120 ks židlí. Z důvodu výpovědi nájemní smlouvy ve skladu v Ústí nad Labem, bude společnost SIT nucena tento sklad zcela vyprázdnit. Úkolem je sestavit takový distribuční plán, aby celkové náklady na přepravu byly minimální. Tabulka 2 Distribuční náklady na 1 ks židle ve stovkách Kč
Z důvodu nevyrovnanosti problému, kdy se požadavky prodejen nerovnají kapacitě skladů firmy SIT, jsme nuceni v řešení zavést fiktivní prodejnu. Při řešení musíme vzít rovněž v úvahu podmínku úplného vyprázdnění skladu v Ústí nad Labem. Z tohoto důvodu u fiktivní prodejny zvolíme vysokou sazbu tak, aby by se přeprava nemohla uskutečnit.
Z výše uvedené tabulky nám vyplývá výchozí základní řešení. Hodnota účelové funkce, znázorněné následujícím výpočtem, činí 409 000 Kč. z z
110 * 500 40 *1300 140 * 300 70 * 500 140 * 400 110 * 900 20 * 500 120 * 500 409000 Kč
Matice přeprav je následující:
110 0 0 40 0 0 0 140 70 0 0 0 0 0 140 110 0 0 0 0 0 20 120 50 Dalším bodem v řešení tohoto úkolu je provedení testu optimality, jehož úkolem je zjištění, jestli je výše uvedené řešení optimální popř. jestli existuje lepší řešení, s nižší hodnotou účelové funkce. Pro provedení testu je nutné nejdříve zjistit, zda-li je řešení nedegenerované, tzn. musí platit podmínka: (m + n - 1) ≤ počet obsazených polí. Příklad: m+n–1≤9 4+6–1≤9 9≤9 Z uvedeného výpočtu vyplývá, že podmínka je splněna, výchozí základní řešení je nedegenerované a lze tedy provést test optimality. Test optimality je založen na porovnání sazby cij s tzv. nepřímou sazbou c’ij v každém neobsazeném poli. Zavedou se pomocná řádková čísla ui a pomocná sloupcová čísla vj. Jestliže poté bude platit že c’ij - cij ≤ 0, bude řešení optimální. Jestliže c’ij - cij > 0, řešení optimální nebude.
Z výše uvedené tabulky vyplývá, že z důvodu platnosti podmínky, kdy c’ij - cij > 0, která platí pro 2 existující pole, řešení není optimální. V tomto případě budeme postupovat tak, že na neobsazené pole, kde je c’ij - cij > 0 největší (tj. pole České Budějovice a Pf), přesuneme určitou přepravu t (tzv. nově obsazované pole). K tomuto nově obsazovanému poli vyhledáme ve výchozím řešení taková obsazená pole, aby spolu tvořila uzavřený okruh. „t“ se přitom bude rovnat nejmenší přepravě z těch, které jsou umístěny na polích uzavřeného okruhu, kde se t odečítá (tj. pole Vsetín a Pf).
V tomto případě t = 50. Výše uvedenou tabulku přepočítáme a provedeme u ní test optimality.
Z výše uvedené tabulky nám vyplývá nové základní řešení. Hodnota účelové funkce, znázorněné následujícím výpočtem, činí 384 000 Kč. z z
110 * 500 40 *1300 140 * 300 20 * 500 50 * 0 190 * 400 60 * 900 70 * 500 120 * 500 384000 Kč
Matice přeprav je následující:
110 0 0 40 0 0 0 140 20 0 0 50 0 0 190 60 0 0 0 0 0 70 120 0
Jelikož v tomto případě již splňujeme podmínku kdy c’ij - cij ≤ 0, můžeme prohlásit toto řešení za optimální. Skutečnost, že předchozí řešení nebylo optimální se potvrdilo i ve snížení účelové funkce (ze 409 000 Kč na 384 000 Kč, tj. snížení o 25 000 Kč).
Alternativní řešení u tohoto příkladu neexistuje, protože zde neexistuje neobsazené pole, ve kterém by se rovnala sazba cij s nepřímou sazbou c´ij tj. c´ij= cij. Nové základní řešení je tedy jediné možné řešení, při kterém můžeme dosáhnout minimální hodnoty účelové funkce, tj. kdy náklady na přepravu jsou minimální.
Řešení pomocí programu WinQSB
Interpretace dosaženého výsledku: Jak lze vidět z výsledku řešení programu WinQSB, výpočet, který byl proveden pomocí samostatné úvahy, byl potvrzen. Řešení nám ukazuje pouze jednu vhodnou variantu distribuce, která při podmínce minimalizace nákladů činí 384 000 Kč. Společnost SIT s. r. o. bude židle distribuovat pomocí následujícího schématu: Sklad v Ústí nad Labem bude dodávat 110 ks židlí do prodejny v Hradci Králové a 40 ks židlí do Olomouce. Sklad v Českých Budějovicích bude dodávat 140 ks židlí do Tábora, 20 ks židlí do Jihlavy, přičemž 50 ks židlí zůstane na skladě. Sklad v Brně bude dodávat 190 ks židlí do Jihlavy a 60 ks židlí do Olomouce. Sklad ve Vsetíně bude dodávat 70 ks židlí do Olomouce a 120 ks židlí do Zlína.
3
ANALÝZA KRITICKÉ CESTY – METODA CPM
Příprava valašského frgálu V rámci plánované oslavy je třeba napéct cukroví a několik koláčů. Z množství různých receptů byl zvolen recept na valašský frgál, jehož příprava je relativně snadná a výsledek se vždy setká s velkým ohlasem stolujících. V rámci upečení tohoto frgálu bylo stanoveno několik následujících činností a rovněž byla odhadem stanovena doba trvání v minutách. Všechny potřebné informace jsou uvedeny v tabulce. Úkolem je sestrojit síťový graf a vypočítat nejkratší dobu pro přípravu a upečení valašského frgálu..
Výsledek síťového grafu: Kritická cesta: A
B
D
E
F
Doba trvání: 175 min = tj. 2 h 55 min
G
H
I
K
L
M
O
Řešení pomocí programu WinQSB
Interpretace výsledku: Ruční výpočet i softwarové řešení nám poskytlo řešení v podobě nalezení kritické cesty: A
B
D
E
F
G
H
I
K
L
M
O . V návaznosti na tyto údaje
jsme schopni zjistit nejkratší možnou dobu pro přípravu a následné zhotovení valašského frgálu. Tato doba stanovena na 175 min, tj. 2 h a 55 min. Celkovou časovou rezervu nacházíme v činnostech C – vymazání plechů (65 min), J – příprava posýpky (15 min) a N – příprava na polití (45 min).
MODEL HROMADNÉ OBSLUHY
4
Pobočka České pošty v Bystřici pod Hostýnem má v provozu celkem 4 přepážky pro peněžní služby. Dostavující se klienti se řadí do jedné fronty, přičemž přicházejí průměrně každé 1,5 minuty a tyto intervaly mají exponenciální rozdělení. Potřebná doba pro vyřízení požadavku klienta je náhodnou veličinou s exponenciálním rozdělením, se střední hodnotou cca 5 minut. Náklady na provoz jedné přepážky jsou 400 Kč/hod a náklady na pobyt jedné jednotky v systému je 160 Kč/hod. Úkolem je zvážit, zda bude za stávajících podmínek výhodné provozovat 5 přepážek nebo zda bude lepší i nadále zůstat u stávající situace. Kendellova notace: M / M / 4/
/
/ FIFO
M / M /5/
/
/ FIFO
Řešení: Nejprve určíme hodnoty λ, µ a ρ.
c1
60 1,5 60 5 4
c2
5
1
c*
2
c*
40 12
40 4 *12 40 5 *12
0,83 3
c*
1
0,66 6
λ – průměrný počet klientů, kteří přijdou na pobočku České pojišťovny za 1 hodinu µ - průměrný počet vyřízených klientů za 1 hodinu ρ – podmínka stabilizace je v obou situacích splněna, protože platí
1
Řešení pomocí programu WinQSB – Queuing analysis V případě 4 přepážek v provozu:
Celková využitelnost systému při provozu 4 přepážek je 83, 33 %. Průměrný počet klientů na přepážce za 1 hodinu je 6,62, průměrný počet klientů ve frontě je 3,29 a průměrný počet klientů ve frontě a v zaplněném systému je roven 5-ti. Klient stráví v systému průměrně 0,1655 hodiny (tj. cca 9,93 min), ve frontě stráví průměrně 0,0822 hodiny (tj. cca 4,9 min) a ve frontě a zaplněném systému stráví 0,1250 h (tj. cca 7,5 minuty). Pravděpodobnost, že přepážka nebude v provozu je 2,131 %. Pravděpodobnost, že příchozí klient bude čekat z důvodu zaplněnosti systému je 65,77 %. Celkové náklady na provoz jedné přepážky v provozu dosahují 1 333,33 Kč/hod, celkové náklady na čekajícího klienta dosahují 526,18 Kč/hod a celkové náklady na provoz celé pobočky za 1 hodinu činí 2 659,51 Kč.
V případě provozu 5-ti přepážek:
Celková využitelnost systému při chodu 5-ti přepážek je 66,67 %. Průměrný počet klientů na pobočce za 1 hodinu je 3,99, průměrný počet klientů ve frontě je 0,6533 a průměrný počet klientů ve frontě a v zaplněném systému je roven 2. Klient stráví v systému průměrně 0,0997 hodiny (tj. cca 5,982 min), ve frontě stráví průměrně 0,0163 hodiny (tj. cca 0,978 min) a ve frontě a zaplněném systému stráví průměrně 0,0500 h (tj. 3min). Pravděpodobnost, že přepážka nebude v provozu je 3,1752 %. Pravděpodobnost, že příchozí klient bude čekat z důvodu zaplněnosti systému je 32,67 %. Celkové náklady na provoz jedné přepážky v provozu dosahují 1 333,33 Kč/hod, celkové náklady na čekajícího klienta dosahují 104,53 Kč/hod a celkové náklady na provoz celé pobočky za 1 hodinu činí 2 637,87 Kč.
Interpretace výsledku: Zavedením 5-té přepážky dojde ke snížení celkové využitelnosti systému na 66,67 %. Z pohledu pobočky České pošty dojde k výraznému snížení čekajících klientů u jednotlivých přepážek i v zaplněném systému. Z pohledu klienta dojde k výraznému zlepšení poskytovaných služeb. Ve frontě a zaplněném systému stráví v konečném důsledku o 4,5 minuty méně času. I přes vyšší pravděpodobnost, že přepážky nebudou v provozu, celková pravděpodobnost, že klient bude čekat v důsledku zaplněnosti systému je o ½ nižší. Z pohledu celkových nákladů, zavedením 5-té přepážky nedojde k jejich výraznějšímu snížení, přesto bych však především z důvodu většího pohodlí pro klienty zavedla do provozu zmiňovanou 5-tou přepážku s celkovými hodinovými náklady na provoz 2 637,87 Kč.
