ČESKÉ VYSOKÉ UČENÍ TECHNICKÉ V PRAZE FAKULTA STAVEBNÍ DIPLOMOVÁ PRÁCE

ČESKÉ VYSOKÉ UČENÍ TECHNICKÉ V PRAZE FAKULTA STAVEBNÍ

DIPLOMOVÁ PRÁCE

PRAHA 2015

Bc. Barbora FAITOVÁ

ČESKÉ VYSOKÉ UČENÍ TECHNICKÉ V PRAZE FAKULTA STAVEBNÍ OBOR GEOINFORMATIKA

DIPLOMOVÁ PRÁCE OPTIMALIZACE V PROMĚNLIVÉM PROSTŘEDÍ

Vedoucí práce: doc. RNDr. Jiří DEMEL, CSc. Katedra inženýrské informatiky

leden 2015

Bc. Barbora FAITOVÁ

ABSTRAKT Klasifikace typů optimalizačních úloh podle vztahu k měnícímu se prostředí. Navržení heuristických algoritmů pro vybrané typy úloh a testovacích prostředí pro jejich vyhodnocení. Provedení výpočetních experimentů.

KLÍČOVÁ SLOVA operační výzkum, optimalizace, lineární programování, simulace

ABSTRACT The classification of types of optimization problems by relation to changing environment. Creating heuristic algorithms for selected tasks and test environments for their assessment. Implementation of computational experiments.

KEYWORDS operation research, optimization, linear programming, simulation

PROHLÁŠENÍ Prohlašuji, že diplomovou práci na téma Optimalizace v proměnlivém prostředí jsem vypracovala samostatně. Použitou literaturu a podkladové materiály uvádím v seznamu zdrojů.

V Praze dne

...............

.................................. (podpis autora)

PODĚKOVÁNÍ Chtěla bych poděkovat vedoucímu diplomové práce doc. RNDr. Jiřímu Demelovi, CSc. za trpělivost, připomínky, pomoc a konzultace poskytované během psaní této práce.

Obsah Úvod

7

1 Co je optimalizace

8

2 Typy optimalizačních úloh 2.1

10

Lineární programování . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.1.1

Dopravní úloha . . . . . . . . . . . . . . . . . . . . . . . . . . 11

2.2

Modely řízení zásob

2.3

Optimalizace SQL dotazů . . . . . . . . . . . . . . . . . . . . . . . . 14 2.3.1

. . . . . . . . . . . . . . . . . . . . . . . . . . . 13

Optimalizátor Systému R . . . . . . . . . . . . . . . . . . . . 15

3 Scénáře použití optimalizačních úloh

18

3.1

Jednorázová optimalizace s jednorázovým použitím . . . . . . . . . . 18

3.2

Jednorázová optimalizace s opakovaným využitím . . . . . . . . . . . 18

3.3

3.4

3.5

3.2.1

Modely řízení zásob s přesnou znalostí pohybu zásob . . . . . 19

3.2.2

Modely řízení zásob s pravděpodobnostní znalostí pohybu zásob 21

Vícekroková jednorázová optimalizace . . . . . . . . . . . . . . . . . . 24 3.3.1

Dvoufázová optimalizace . . . . . . . . . . . . . . . . . . . . . 25

3.3.2

Vícefázová optimalizace . . . . . . . . . . . . . . . . . . . . . 25

Opakovaná optimalizace jedné úlohy . . . . . . . . . . . . . . . . . . 27 3.4.1

Opakovaná dopravní úloha . . . . . . . . . . . . . . . . . . . . 27

3.4.2

Lineární programování s nejistotou . . . . . . . . . . . . . . . 27

Klouzavá optimalizace . . . . . . . . . . . . . . . . . . . . . . . . . . 32

4 Úloha

35

4.1

Zadání úlohy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

4.2

Rozbor úlohy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

4.3

Způsob řešení . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

4.4

Simulace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 4.4.1

GNU Octave . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

4.4.2

Popis simulace

. . . . . . . . . . . . . . . . . . . . . . . . . . 38

4.5

4.6

Kód simulace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 4.5.1

Opakované provedení simulace . . . . . . . . . . . . . . . . . . 41

4.5.2

Samotná simulace . . . . . . . . . . . . . . . . . . . . . . . . . 43

4.5.3

Funkce na setřídění matice . . . . . . . . . . . . . . . . . . . . 52

Výsledky . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 4.6.1

Výsledky z vypisovacího souboru . . . . . . . . . . . . . . . . 58

Závěr

62

Požité zdroje

63

A CD

64

ČVUT v Praze

ÚVOD

Úvod Optimalizace je běžnou součástí mnoha technických a ekonomických oborů, při kterých se snažíme ušetřit náklady nebo zvýšit profit. K optimalizaci se přistupuje především u velkých a nákladných úloh nebo u úloh, které se často opakují. Například ve stavebnictví, které pracuje s velkým množstvím peněz, času i materiálu, je vhodné jednotlivým zakázkám věnovat pozornost, zvážit všechna fakta, která mohou mít dopad na výslednou cenu a čas věnovaný stavebnímu dílu. Na základě těchto znalostí můžeme sestavit model, který zohledňuje dostupná fakta, a nasadit na úlohu matematický aparát. Je důležité znát podmínky, které mají dopad na řešenou úlohu, nicméně je potřeba si ujasnit, co přesně optimalizujeme, tzn. co má být výsledkem těchto výpočtů. To mimo jiné záleží i na tom, kdo optimalizaci vyžaduje a na zvoleném přístupu osoby, která optimalizaci provádí. Například zadavatel zakázky se bude snažit o co nejnižší náklady nebo o nejkratší čas, na druhé straně dodavatel bude chtít na dané zakázce co nejvíc vydělat. V případě výběrových řízení pak dodavatel musí brát v potaz konkurenci, kterou nemusí znát a nemusí tudíž vědět nic o jejich strategii. Jedná se pak o omezení, které má přímý dopad na výsledné řešení, ale které nedokážeme přesně definovat. Někdy je možné úlohy zjednodušit, zanedbat vliv náhodných událostí a použít již existující metodu pro získání vhodného řešení. V takovém případě bývají způsoby zjištění optimálního řešení relativně jednoduché. V mnoha případech však není možné zanedbat různé výkyvy a náhodné vlivy. Řešení takových úloh se stává složitějším. Pro některé často se vyskytující situace byly publikovány různé postupy řešení. Existují však takové situace, které nelze „napasovat“ na dané postupy a je třeba přistoupit k novému způsobu řešení, jakým může být například simulace. Tato diplomová práce se bude věnovat takovým úlohám, které jsou ovlivňovány různými typy změn nebo neznalostí všech potřebných podmínek. Pokusí se tyto úlohy rozdělit a najít způsoby řešení.

7

ČVUT v Praze

1

1. CO JE OPTIMALIZACE

Co je optimalizace Optimalizace1 je vědní disciplína, která má za úkol nalézt takové hodnoty proměn-

ných, aby účelová funkce měla optimální řešení (minimum či maximum dané funkce, podle typu funkce). Vezmeme-li účelovou funkci 𝑓 : 𝐴 → R, hledáme v případě maximalizace funkce takové 𝑥0 ∈ 𝐴, že 𝑓 (𝑥0 ) ≥ 𝑓 (𝑥) pro všechna 𝑥 ∈ 𝐴. Množina 𝐴 se nazývá množinou přípustných řešení pro danou účelovou funkci a bývá vymezena omezujícími podmínkami. Prvek 𝑥0 se pak nazývá optimálním řešením, nemusí však být vždy jednoznačný. Tato disciplína vznikla během 2. světové války ve Velké Británii pro vojenské účely. Jelikož se tyto metody nebo jejich modifikace daly použít v civilních oborech, vznikl nový obor s názvem „Operations Research“2 , který se začal vyučovat na vysokých školách. Pro znázornění problému se využívají modely, které mají za úkol více či méně přesně znázornit část reálného světa. S jednoduššími modely se snáze pracuje, nemusí však dostatečně vypovídat o problému, který mají znázorňovat. Je proto potřeba vyhodnotit, které parametry jsou pro úlohu podstatné a které si můžeme dovolit zanedbat. Je též potřeba se rozhodnout, jakým způsobem bude model vyhodnocován, podle toho je pak možné vytvořit vhodný model. Neexistuje návod pro tvorbu modelu, záleží tedy na osobě, která model vytváří, jak k němu přistoupí, jak kvalitně ho zpracuje a jak ho vyhodnotí. Modely můžeme rozdělit na několik druhů: • Matematické modely popisují modelovaný problém matematickými vztahy, lze na ně tudíž použít matematické metody. • Vyhodnocovací modely mají často podobu vzorců či rovnic, slouží k získání neznámých veličin z veličin, které známe. • Optimalizační modely hledají nejlepší (tzv. optimální) řešení, jsou zobrazeny pomocí matematické optimalizační úlohy. 1 2

Tato kapitola vychází z informací uvedených v [1] a [7]. V češtině pak Operační výzkum.

8

ČVUT v Praze

1. CO JE OPTIMALIZACE

• Simulační modely napodobují skutečné události, simulace se provádí v čase. Na základě simulace je možné si s modelem „hrát“, zkoumat ho. Umožňuje měnit parametry modelu a zjistit jejich dopad na výsledek úlohy.

9

ČVUT v Praze

2

2. TYPY OPTIMALIZAČNÍCH ÚLOH

Typy optimalizačních úloh Existuje mnoho druhů optimalizačních úloh a mnoho způsobů, jak takové úlohy

dělit. Jedno z možných a pro tuto diplomovou práci zásadní rozdělení je na úlohy deterministické a stochastické, přičemž nás budou více zajímat úlohy stochastické. Deterministické modely pracují se stabilními veličinami, jejichž hodnoty jsou jisté, nebo se mění jen zanedbatelně a není proto nutné tuto skutečnost do modelu zahrnout. Deterministické úlohy jsou popsány a zpracovány ve všech učebnicích a základních kurzech operačního výzkumu. Mezi klasické deterministické úlohy operačního výzkumu se řadí lineární programování, dopravní úloha, některé úlohy z teorie grafů, aj. Ne vždy je možné popsat každou proměnnou v modelu jedinou neměnnou hodnotou. Jedná se o případy, kdy není jisté, jak se zachová okolí, které ovlivňuje modelovanou situaci. Někdy tuto nejistotu není možné zanedbat, protože následky použití takto získaného optimálního řešení by mohly být příliš nákladné. V takovém případě můžeme využít metod stochastického programování (SP), které dokáží pracovat s nejistotou některých proměnných. Existuje velké množství optimalizačních úloh. Pro tuto práci jsem vybrala následující: • Lineární programování • Teorie řízení zásob • Optimalizace SQL dotazů První uvedená úloha je deterministická, lze ji však použít jako základ pro různé typy stochastických modelů. Teorie řízení zásob využívá různé výpočetní modely a záleží na předpokladech, jestli se bude jednat o úlohu deterministickou či stochastickou. Optimalizace dotazů relační databáze je stochastická a snaží se minimalizovat časové náklady na získání výsledku zadaného dotazu. Pro získání optimálního řešení je možné využít různé heuristiky, je však potřeba vzít v úvahu možnost, že příliš usilovné hledání nejvýhodnějšího řešení může vést k vyšším časovým nákladům, než některé méně přesné postupy.

10

ČVUT v Praze

2.1


Lineární programování

Lineární programování se zabývá hledáním extrému daného kritéria pomocí účelové funkce na množině variant, které jsou určeny soustavou omezujících podmínek.1 Účelová funkce 𝐿(𝑥) je funkce 𝑛 proměnných, kterou můžeme maximalizovat či minimalizovat, zápis pak vypadá následovně max / min 𝐿(𝑥) = 𝑐1 · 𝑥1 + 𝑐2 · 𝑥2 + ... + 𝑐𝑛 · 𝑥𝑛 , hodnoty 𝑐1 , 𝑐2 , ..., 𝑐𝑛 jsou cenové koeficienty a jsou konstantní. Omezující podmínky určují množinu přípustných řešení.

𝑎11 · 𝑥1 + 𝑎12 · 𝑥2 + ... + 𝑎1𝑛 · 𝑥𝑛 R 𝑏1 𝑎21 · 𝑥1 + 𝑎22 · 𝑥2 + ... + 𝑎2𝑛 · 𝑥𝑛 R 𝑏2 .. . 𝑎𝑚1 · 𝑥1 + 𝑎𝑚2 · 𝑥2 + ... + 𝑎𝑚𝑛 · 𝑥𝑛 R 𝑏𝑚 Dále je ještě třeba určit podmínky pro jednotlivé proměnné, obvykle je vyžadována podmínka nezápornosti proměnných (𝑥𝑗 ≥ 0). V některých případech je potřeba, aby výsledek vycházel v celých číslech, pak se jedná o celočíselné lineární programování. Lineární programování se obvykle řeší simplexovou metodou, která je podrobněji popsána např. v [1].

2.1.1

Dopravní úloha

Dopravní úloha je speciální případ úlohy lineárního programování. Jedná se o přesun zboží mezi 𝑚 dodavateli a 𝑛 spotřebiteli. Známe ceny dopravy od každého dopravce ke každému spotřebiteli. Cílem úlohy je zajistit co nejlevnější způsob rozvozu zboží. V tomto typu úlohy známe následující parametry: 1

Tato kapitola vychází ze skript [1].

11

ČVUT v Praze


20

20

20

20

20 10

3

9

10

2

30 10

1

15

10

6

10

4

30

3

12

10

7

20

3

8

Tab. 2.1: Příklad dopravní tabulky • 𝑚 dodavatelů, kteří mají kapacitu 𝑎𝑖 , 𝑖 = (1, 2, ..., 𝑚), • 𝑛 spotřebitelů, kteří chtějí spotřebovat 𝑏𝑗 , 𝑗 = (1, 2, ..., 𝑛), • 𝑐𝑖𝑗 je cena zboží od 𝑖. dopravce k 𝑗. spotřebiteli, • 𝑥𝑖𝑗 značí množství zboží přepravovaného od 𝑖. dopravce k 𝑗. spotřebiteli. Dopravní úloha má pak následující tvar:

𝑛 𝑚 ∑︁ ∑︁

𝑐𝑖𝑗 𝑥𝑖𝑗

𝑖=1 𝑗=1 𝑛 ∑︁

𝑥𝑖𝑗 = 𝑎𝑖

𝑗=1 𝑚 ∑︁

𝑥𝑖𝑗 = 𝑏𝑗

𝑖=1

𝑥𝑖𝑗 ≥ 0 ∀𝑖, 𝑗 Řešení Dopravní úlohu můžeme počítat stejně jako úlohy lineárního programování. Jelikož má speciální tvar, byly odvozeny vhodnější metody výpočtu. Zadání i řešení úlohy se zapisuje do jedné tzv. dopravní tabulky. Řádky této tabulky odpovídají dodavatelům a jsou označeny kapacitou 𝑎𝑖 , sloupce pak odpovídají spotřebitelům a jsou označeny spotřebou 𝑏𝑗 . V pravém horním rohu každé buňky je uvedana cena 𝑠𝑖𝑗 , která se po čas výpočtu nemění, uprostřed buněk se zobrazuje přepravované množství 𝑥𝑖𝑗 , které se v průběhu výpočtu mění. Abychom mohli úlohu vypočítat, je potřeba, aby byla vyvážená. V případě, že dopravců není stejně jako spotřebitelů, je potřeba přidat fiktivní postavu, která bude mít ve všech případech stejné ceny.

12

ČVUT v Praze


Je-li potřeba, aby některému ze spotřebitelů nebylo dodáno zboží od konkrétního dodavatele, stanoví se cena 𝑐𝑖𝑗 příliš vysoká (tzv. prohibitivní ) - 𝑀 . V případě, že je větší požadavek než možnost dodavatelů a je potřeba některého zákazníka uspokojit přednostně, nastaví se u fiktivního dodavatele pro prioritního zákazníka prohibitivní cena. Postup výpočtu optimálního řešení je popsán např. v [1].

2.2

Modely řízení zásob

Teorie zásob2 hledá optimální velikost zásob a způsob jejich dodávání. Zásobou je myšlen pohotový zdroj, který je možné použít. Z hlediska optimalizace je důležité, jak velký tento zdroj má být, aby bylo zásob dostatek, ale aby po ukončení operací s danými zásobami, zůstalo zásob co nejméně. V teorii řízení zásob se rozlišují dva druhy nákladů, které jdou vzájemně proti sobě. První skupinu tvoří náklady rostoucí s udržováním zásob. Do této skupiny spadají následující náklady: • pořizování zásob • udržování zásob • nedostatek pohotových zásob • správa informací o stavu zásob Do druhé skupina spadají náklady spojené s nízkým množstvím zásob. Mezi tento typ nákladů patří například ušlý zisk z nedostatku pohotových zásob nebo náklady spojené s objednáním malého množství chybějících zásob. Otázkou pak je, jak stanovit optimální velikost pohotových zásob. Základem této úlohy jsou otázky, kdy objednat zásoby a kolik jich objednat. Modely pro řešení těchto otázek dělíme na statické a dynamické. V rámci této práce je relevantní se zabývat modely dynamickými. U statických modelů se jedná o jednorázové rozhodnutí. V případě dynamických modelů se o způsobu doplňování zásob rozhoduje ve formě posloupnosti rozhodnutí 2

Tento text i následné kapitoly na toto téma čerpá z [3].

13

ČVUT v Praze


v celém časovém období. Můžeme učinit všechna rozhodnutí předem nebo postupně, díky čemuž můžeme korigovat důsledky předchozích rozhodnutí. Můžeme využít dva hlavní způsoby, jak určit vhodné řešení: • „Optimální“ řešení se vypočte na základě předpokladů a zjednodušení parametrů. • Zkoumají se různé druhy řešení při změnách parametrů (změna délky časového intervalu, kolísání poptávky...). V dnešní době je zbytečné využívat první způsob, vhodnější výsledky může poskytnout druhý přístup. Blíže budou některé z modelů popsány v kapitole o optimalizačních scénářích.

2.3

Optimalizace SQL dotazů

Cílem optimalizace SQL dotazů je zajistit co nejrychlejší získání odpovědi v databázovém stroji. Tato problematika je rozebrána v článku [4], tato kapitola z něj vychází. Zadaný dotaz je obvykle možné přeložit několika způsoby. Databázový stroj vytvoří tzv. plány vyhodnocení a odhadne se jejich cena. Odhad ceny dotazů obvykle není možné vyhodnocovat přesně, závisí na mnoha faktorech od formulace dotazu, přes fyzické uložení dat, až po strukturu databáze, využívá existence indexů a statistik vyhledávaných dotazů. Úloha optimalizátoru je složitá, protože je obvykle možné postupovat několika způsoby: • Algebraická reprezentace dotazu může být vyjádřena několika ekvivalentními výrazy, výraz Join(Join(A,B),C) dává stejný výsledek jako Join(Join(A,C),B). • Zadanou algebraickou reprezentaci je možné vyjádřit pomocí několika stromů. Databázové systémy často mají několik podporovaných způsobů, jak jednotlivé tabulky propojit. Ačkoliv výsledek rozdílných reprezentací zadaného dotazu je totožný, liší se doba běhu dotazu. Aby bylo možné vyhledávání optimalizovat, je potřeba zajistit:

14

ČVUT v Praze


• množinu logických plánů dotazu, • techniku pro odhadování ceny každého logického plánu dotazu, • výpočetní algoritmus, který umožní vyhledávání.

2.3.1

Optimalizátor Systému R

Projekt Systém R probíhal v druhé polovině 70. let ve společnosti IBM a vycházel z teoretické práce E. F. Codda o relačním datovém modelu. Přispěl k rozvoji optimalizace SQL dotazů, jeho myšlenky byly dále zpracovány v mnoha komerčních databázových systémech. Některé důležité myšlenky si představíme na dotazech typu Select-Project-Join (SPJ). Vyhledávací prostor Systému R v kontextu SPJ dotazů obsahuje syntaktické stromy, které odpovídají lineárnímu vyjádření join operací (jako příklad je na obr. 2.1 znázorněna posloupnost Join(Join(Join(A,B),C),D)). Pro spojení můžeme použít nested-loop join nebo sort-merge. Každý prohlédnutý uzel může využít výběr podle indexu nebo sekvenční skenování. Předpovědi jsou určovány co nejrychleji. Nested-loop join spojuje tabulky procházením každé položky v 1. tabulce, ty pak porovnává s každou hodnotou v tabulce druhé. Jedná se tedy o dva for cykly, je proto vhodný pouze pro databáze s malým množstvím záznamů. Sort-merge join vyžaduje k vykonání možnost načtení obou relací do paměti. Po načtení se záznamy setřídí podle spojovacího atributu, pak se tyto záznamy „slijí“.3 Cenový model přiřadí jednotlivým plánům (částečným i úplným) ve vyhledávacím prostoru odhadované náklady. Model také určuje odhad velikosti datového toku pro výstup každého operátoru v plánu. Závisí to na: • souboru statistik, které jsou uchovávány v kontextu s indexy a vztahy, • vzorcích, které odhadnou vhodné předpovědi a promítnou velikost datového toku do každého uzlu, 3

Informace o obou joinech jsou uvedeny v diplomové práci [5].

15

ČVUT v Praze


Obr. 2.1: Linear join • vzorcích pro odhad CPU a vstupní a výstupní náklady na spuštění dotazu, které berou ohled na statistické vlastnosti vstupu, přístupné metody k danému vstupu a dostupné pořadí vstupu. Cenový model využívá tyto metody k výpočtu a spojuje následující informace zdola nahoru: • velikost datového toku reprezentované výstupním uzlem, • uspořádání n-tic vytvořené z výstupního datového toku uzlu, • odhad nákladů na provedení. Výpočetní algoritmus Systému R předvádí dvě důležité techniky - dynamické programování a tzv. „zajímavých pořadí“4 . Při použití dynamického programování se předpokládá, že cenový model splňuje podmínky optimality. Máme SPJ dotaz 𝑄, který obsahuje 𝑘 joinů. Chceme-li získat plán optimálního řešení, předpokládá se, že stačí, aby byl optimální částečný plán pro výraz s (𝑘 − 1) joiny. Tento plán pak rozšíříme o chybějící join. Výpočetní algoritmus probíhá odzdola nahoru. Na konci 𝑗 − 𝑡éℎ𝑜 kroku se vytvoří plán poddotazu velikosti 𝑗. Pro získání optimálního plánu poddotazu obsahující (𝑗 + 1) vztahů se vezmou v potaz všechna přípustné možnosti k vytvoření plánu poddotazu a vybere se nejvhodnější. 4

Z anglického interesting orders použitého v [4].

16

ČVUT v Praze


Dále optimalizátor Systému R zohledňuje tzv. „zajímavé pořadí“. Nyní si ukážeme spojení mezi {R1 , R2 , R3 }. Předpokládejme, že známe náklady plánů poddatazu {R1 , R2 }, kde 𝑥 jsou náklady pro nested-loop a 𝑦 jsou náklady pro sort-merge, přičemž 𝑥 < 𝑦. Pak pro plán {R1 , R2 , R3 } nebudeme uvažovat možnost sort-merge. Dva plány jsou porovnávány pouze v případě, že představují stejný výraz a zároveň mají stejné „zajímavé pořadí“. Tato myšlenka byla později zobecněna jako fyzická vlastnost a začala se používat v moderních optimalizátorech. Fyzická vlastnost je jakákoliv charakteristika plánu, která není společná s ostatními plány, které mají stejné logické vyjádření. Tyto charakteristiky pak mohou mít dopad na následující operace. Přístup Systému R představuje mechanismus, jak se vypořádat s narušením principu optimality. Navzdory tomu, že je framework Systému R elegantní, nelze jej jednoduše rozšířit o dalších logické transformace, které by rozšířily vyhledávací prostor. To vedlo k vývoji rozšiřitelných optimalizátorů. Nicméně dynamické programování, „zajímavé pořadí“ a využívání cen silně ovlivnily další vývoj optimalizací SQL dotazů.

17

ČVUT v Praze

3

3. SCÉNÁŘE POUŽITÍ OPTIMALIZAČNÍCH ÚLOH

Scénáře použití optimalizačních úloh Existuje mnoho variant použití optimalizačních úloh. Tyto scénáře můžeme rozdělit

následovně: • jednorázová optimalizace pro jednorázové použití, • jednorázová optimalizace, jejíž výsledek lze opakovaně používat, dokud se nezmění podmínky, • jednorázová optimalizace sestávající z více fází rozhodování, • opakovaná optimalizace téhož, • klouzavá optimalizace.

3.1

Jednorázová optimalizace s jednorázovým použitím

Do této kapitoly patří jednorázové případy, pro něž se jednou najde optimální řešení, jednou se aplikuje a úloha tím končí. Jako příklad může být potřeba výstavby nového objektu. Jedná se o úlohu, kterou je potřeba vyřešit jednou a po aplikaci řešení není možné jej znovu použít, stejně jako není potřebné použít model pro hledání dalšího řešení. Stejně tak se může jednat o jednorázovou výrobu produktu, které je potřeba vyrobit ve větším množství, ale pouze v limitované edici (jedná se o luxusní zboží nebo o zboží pro vědecké či armádní účely).

3.2

Jednorázová optimalizace s opakovaným využitím

Jednorázová optimalizace je vhodná v případech, kdy se dlouhodobě nemění podmínky. Na začátku se vypočítá optimální řešení a to je využíváno tak dlouho, dokud se některá z podmínek nezmění.

18

ČVUT v Praze


Může se jednat například o každodenní rozvoz zásob z centrálního skladu do jednotlivých poboček. Potřeba změnit optimální řešení zde nastává v případě, že přibude nová pobočka nebo výrazně vzroste poptávka vlivem sezóny. Dalším příkladem může být výroba zboží s ustálenou poptávkou. V takovéto úloze by mohlo dojít ke změně poptávky nebo technologickému pokroku ve výrobě, které by mohli vést k nové optimalizaci za takto změněných podmínek. Jako jednorázovou optimalizaci lze vnímat například i tvorbu jízdních řádů. Na začátku se vytvoří jízdní řády, ale v průběhu jejich platnosti může dojít z důvodu oprav na tratích k nutnosti některé linky upravit a vytvořit nové náhradní. Do této kategorie lze zahrnout dále zahrnout deterministické úlohy lineárního programování či dopravní úlohu nebo deterministické modely teorie řízení zásob.

3.2.1

Modely řízení zásob s přesnou znalostí pohybu zásob

Teorie řízení zásob byla nastíněna již v kapitole 2.2 na straně 13. Jedná se o modely, ve kterých je poptávka po zásobách v čase předem jasně definována a známe tento průběh na začátku rozhodování. Poptávka může být konstantní i proměnná, determinovaná i nedeterminovaná, ale musíme ji znát předem. V tomto případě není třeba uvažovat nedostatek či přebytek zásob. Je však třeba rozhodnout, v jakých okamžicích a v jakém množství je vhodné zboží objednat. Na jedné straně je třeba zaplatit náklady spojené s každou dodávkou, na straně druhé vznikají náklady se skladováním dodaného zboží. Je proto nutné najít takové množství objednávek, aby tyto náklady byly co nejnižší. Tento typ úlohy je však v praxi velmi vzácný. Je ale možné jej využít jako první aproximaci dalších typů modelů. Za časové období 𝑇 máme poptávku po dané zásobě 𝑄. Poptávka je rovnoměrná a budeme ji považovat za spojitou veličinu. Zásobu budeme doplňovat rovnoměrně, její velikost je 𝑥. Budeme předpokládat, že dodávka nemá žádnou časovou prodlevu. Na začátku každého časového intervalu jsou skladové zásoby na nule, při dodání vzrostou na hodnotu 𝑥 a po uplynutí intervalu klesnou zpět na nulu. Tento proces se opakuje a nemění, graficky je znázorněn na obrázku 3.1.

19

ČVUT v Praze


Obr. 3.1: Průběh dodávání zásob V tomto modelu uvažujeme jen náklady na vyřízení objednávky 𝐶𝑠 a náklady na skladování jednotkového množství zboží po dobu jednoho roku 𝐶1 . Snažíme se určit velikost zakázky 𝑥 = 𝑥* tak, aby náklady za období 𝑇 byly minimální.

𝑁 (𝑥) =

𝐶𝑠 𝑄 𝑇 𝐶1 + 𝑥 𝑥 2 √︃

2𝐶𝑠 𝑄 𝑇 𝐶1

√︁

2𝑄𝑇 𝐶𝑠 𝐶1

𝑥 = *

𝑁 (𝑥* ) =

Optimální délku cyklu pak dostaneme následovně: 𝑡*𝑐 𝑥* = 𝑇 𝑄 √︃

𝑡*𝑐

=

2𝑇 𝐶𝑠 𝑄𝐶1

Optimální počet objednávek pak tedy 𝑣 * je

𝑣* =

𝑄 𝑥*

Tento Wilsonův vzorec je velmi zjednodušený. Existují i další metody, které zanedbávají menší množství informací, ovšem pokud by tento byl používán jako možnost první aproximace, je možné ho považovat za dostatečný.

20

ČVUT v Praze

3.2.2


Modely řízení zásob s pravděpodobnostní znalostí pohybu zásob

Základní popis teorie řízení zásob byl nastíněn v 2.2 na straně 13. Tento typ úloh se vyznačuje tím, že jej lze charakterizovat pravděpodobnostně popsaným rozdělením poptávky. Lze jej využít u zásob s pravidelnou spotřebou. Ačkoliv náklady spojené s tímto typem modelu jsou shodné s těmi, které jsou uvedeny v kapitole 2.2, nemusí mít všechny nepříznivý dopad. Například náklady z nadbytku zásob zahrnují náklady na skladování, ale jejich přemíra bude vykompenzována v další objednávce, která bude o daný nadbytek opravena. Díky pravděpodobnostní charakteristice poptávky je možné počítat s kolísáním poptávky. Chceme-li se tedy vyvarovat možnému nedostatku pohotových zásob, můžeme objednávky navýšit o tzv. pojistnou zásobu. Díky tomuto opatření se vyhneme náhodným výkyvům, které by mohly mít výrazný vliv na náklady z nedostatku zásob. Na druhou stranu se tím zvyšují náklady na udržování zásob a jejich možnou expiraci, pokud by došlo k výkyvu poptávky na opačnou stranu. Oproti předchozímu modelu v tomto není interval pořízení zásob pevně daný. Navíc je třeba počítat s tím, že dodání zásob není nulové a je nutné během této doby poptávku uspokojovat z pojistných zásob. Stav zásob můžeme ovlivňovat buď volbou frekvence objednávek, nebo stanovením jejich velikosti. Vzhledem ke kolísání poptávky můžeme určit průměrnou hodnotu intervalu objednávání a velikosti objednávky, které nám mohou dát přibližnou představu. Účinky kolísání na stav zásob pak musíme vyrovnávat. Můžeme buď ponechat konstantní velikost objednávek a měnit jejich frekvenci, nebo naopak vzít konstantní frekvenci a měnit velikost. V prvním případě, kdy se mění interval objednávek, se obvykle stanoví velikost zásob, při jejíž úrovni se objednává další zboží a jejíž velikost (tzv. signální úroveň zásob) slouží k pokrytí poptávky v mezidobí, než dorazí nové zboží. Tento systém se označuje jako Q-systém (𝑄 značí kvantitu objednávaného zboží). Druhý způsob funguje tak, že máme stanovený pevný časový krok, po jehož uplynutí provádíme novou objednávku. Tato objednávka má pokaždé jinou velikost.

21

ČVUT v Praze


Tato velikost se obvykle určuje tak, aby její součet s aktuálním stavem na skladě měl předem stanovenou velikost. Tento způsob nevyžaduje neustálou kontrolu stavu zásob, ale stačí jejich kontrola po pevných časových úsecích. V dnešní době je možné skladové zásoby uchovávat v databázích, které nás mohou upozornit na jejich nedostatek, proto v mnoha případech nemusí být tento fakt nutně výhodou. Tento systém označujeme jako P-systém (𝑃 označuje periodu objednávaného zboží). P-systémy řízení zásob

Obr. 3.2: P-systém V tomto typu modelu se využívá konstantní délka objednacího cyklu a velikost objednávky se mění v závislosti na zůstatku zásob v době nové objednávky. Velikost objednávky se určí tak, aby bylo zboží doplněno do optimální úrovně zásob. Předmětem úlohy je tedy určit optimální úroveň zásob a délku objednacího cyklu. Hlavní rozdíl mezi P-systémem a Q-systémem je v tom, jak se vypořádávají s výkyvy v poptávce. V případě Q-systému vyšší poptávka zkrátí délku objednacího

22

ČVUT v Praze


cyklu a pojistná zásoba zde slouží k pokrytí vyšší poptávky v intervalu pořízení zásob. U P-systému musí pojistná zásoba pokrýt vyšší poptávku během celého cyklu. Pro zjednodušení modelu se u P-systému uvažuje, že pojistnou zásobu stačí stanovit pro jeden objednací cyklus zvětšený o jeden interval pořízení zásob. Q-systémy řízení zásob

Obr. 3.3: Q-systém Q-systémy fungují tak, že se objednává vždy stejné množství zásob po různě dlouhých časových intervalech a to v okamžiku, kdy skutečný stav zásob klesne na tzv. signální úroveň. Je tedy potřeba stanovit signální úroveň zásob a konstantní velikost objednávaných zásob. U tohoto systému není nutné vytvářet pojistné zásoby během objednacího cyklu, neboť náhodné zvýšení poptávky bude mít pouze takový vliv, že časové období, po kterém bude potřeba objednat zboží, bude menší než průměrná hodnota. Po objednání zásob trvá konstantní časový úsek, než jsou zásoby dodány, a po tuto dobu je poptávka pokrývána ze zbylého množství zásob.

23

ČVUT v Praze

3.3


Vícekroková jednorázová optimalizace

Jedná se o jednorázovou optimalizaci, jejíž výsledek se použije jen jednou a optimalizace se nebude provádět znovu. Jedná se však o úlohu, při níž na počátku známe jen některé proměnné a na jejich základě musíme učinit částečné rozhodnutí. Zbytek proměnných se dozvíme později, přičemž jsme limitováni předchozím rozhodnutím.1 Jako příklad si můžeme uvést situaci, kdy musíme nakoupit materiál, ačkoliv nevíme, jaká bude poptávka po jednotlivých výrobcích. Abychom minimalizovali případné ztráty, můžeme navrhnout několik možných scénářů vývoje (𝜔) a určit pravděpodobnosti (𝑝𝜔 ), s jakými daný scénář nastane.

Obr. 3.4: Strom dvoufázové optimalizace Pokud si scénáře zobrazíme jako strom, který je znázorněn na obrázku 3.4, pak kořenem stromu je situace, ve které je třeba učinit část rozhodnutí, a každý scénář představuje jeden list. Každý list je spojen s kořenem větví. 1

Následující text vychází z článku [6].

24

ČVUT v Praze

3.3.1


Dvoufázová optimalizace

Dvoufázovou optimalizaci je možné si představit na modelu lineárního programování, kdy známe jen část podmínek a musíme učinit rozhodnutí. V okamžiku, kdy se dozvíme zbytek podmínek, jsme již vázáni rozhodnutím z předchozího kroku. Takováto úloha má pak následující tvar:

max 𝑐 · 𝑥 + 𝐸[ℎ(𝑥, 𝜔 ˜ )] o.p.

𝐴·𝑥≥𝑏 𝑥≥0

kde ℎ(𝑥, 𝜔) = min 𝑔𝜔 · 𝑦 o.p.

𝑊𝜔 · 𝑦 ≥ 𝑟𝜔 − 𝑇𝜔 · 𝑎 𝑦≥0

Hodnoty 𝑥 se nemění podle jednotlivých scénářů, zůstávají stejné pro kteroukoli variantu, která v budoucnu nastane. Vektor 𝑟𝜔 je vektor pravých stran, který obsahuje prvky pro specifické scénáře 𝜔. Stejně tak matice 𝑇𝜔 a 𝑊𝜔 jsou matice s koeficienty, které jsou odlišné pro každý scénář.

3.3.2

Vícefázová optimalizace

Tento typ úlohy má za základ dvoufázový model. Jedná se o případ, kdy se musíme rozhodnout, dozvíme se, jak situace vypadá, a musíme se rozhodnout znovu. Jedná se o zřetězený dvoufázový model, který můžeme řetězit donekonečna, nicméně z výpočetního hlediska je vhodné udržovat množství fází na co nejnižším počtu. Pro každý scénář 𝜔 ∈ Ω bude 𝑐𝜔 představovat koeficienty účelové funkce odpovídající scénáři. 𝑋(𝜔) pak označuje sadu řešení, které jsou pro daný scénář proveditelné. Pokud sadu řešení označíme 𝒩 , potom vícefázový model můžeme vyjádřit následovně:

25

ČVUT v Praze


Obr. 3.5: Scénářový strom

min

∑︁

𝑝 𝜔 𝑐𝜔 𝑥 𝜔

𝜔

o.p. 𝑥𝜔 ∈ 𝑋(𝜔)

∀𝜔 ∈ Ω

{𝑥𝜔 }𝜔∈Ω ∈ 𝒩 Povaha nejistých omezujících podmínek má vliv na strukturu scénářového stromu. Vezmeme-li jako příklad strom zobrazený na obrázku 3.5, máme zde vyobrazen model čtyřfázové úlohy. Uzel 𝑛 odpovídá fázi 𝑡(𝑛)4 v úloze. Každý uzel zde zobrazuje jednu fázi modelu a scénáře, které se k dané fázi váží. Scénáře, které prošly uzlem 𝑛, jsou na obrázku 3.5 zvýrazněny a označeny jako ℬ(𝑛). Z dostupných dat je možné určit, že první fáze bude směřovat k rozhodnutí 𝑛, ale další rozhodnutí z ℬ(𝑛) se předpovědět nedají. Abychom dokázali úlohu vyřešit, musíme zajistit, aby proměnné z fáze 𝑛 přinášeli stejné hodnoty. Můžeme toho dosáhnout přidáním následujících omezujících podmínek:

𝑥𝑡(𝑛)𝜔 − 𝑥𝑛 = 0

∀ 𝜔 ∈ ℬ(𝑛)

Pokud označíme všechny uzly, které mají potomky, jako 𝑁 , pak sada řešení je reprezentována následovně:

26

ČVUT v Praze


𝒩 = {{𝑥𝜔 }𝜔∈Ω | 𝑥𝑡(𝑛),𝜔 − 𝑥𝑛 = 0 ∀ 𝜔 ∈ ℬ(𝑛), ∀𝑛 ∈ 𝑁 }

3.4

Opakovaná optimalizace jedné úlohy

Opakovaně optimalizovat jednu úlohu je vhodné v případě, že se vstupní hodnoty průběžně mění a mohou tak mít vliv na optimální řešení. Na základě těchto průběžných optimalizací je pak možné určit, jestli je vhodné zavádět změny, které s sebou nesou další náklady, nebo se spokojit s „méně vhodným“ řešením, kvůli kterému nemusíme vynakládat žádné další prostředky. Opakovanou optimalizací je možné řešit například dopravní úlohu nebo úlohy lineárního programování, které jsou zasaženy nejistotou.

3.4.1

Opakovaná dopravní úloha

Pokud dodavatelé denně dodávají stejné množství zboží stejným zákazníkům, není denní optimalizace potřeba a je možné přistoupit ke změně řešení pouze v případě, že nastane změna. Na druhé straně jsou případy, kde je potřeba denně provést výpočet optimálního řešení, protože i malá změna může výrazně změnit řešení. Takovou změnu může představovat předem ohlášená uzavírka silnice, přestěhování některého z dodavatelů či spotřebitelů, změna ceny dopravy nebo velikost či množství přepravovaného zboží.

3.4.2

Lineární programování s nejistotou

Lineární programování s nepřesnými vstupními daty a analýza citlivosti Máme-li počítat úlohu lineárního programování, může se stát, že dostupná data nereprezentují přesně skutečnost. Získání přesnějších dat však není zadarmo a vyžaduje dodatečné náklady, které je třeba vzít v úvahu. Náklady na získání dat nemusí být vyjádřeny jen cenou, kterou je nutné za data zaplatit, ale projeví se zde i časová nákladnost, možnost ušlých zisků, penalizace z prodlení a další situace, případně jejich kombinace.

27

ČVUT v Praze


Analýza citlivosti2 zkoumá, jaké dopady na řešení mají změny vstupních dat, můžeme ji provádět na vektorech pravých stran, nebo na cenových koeficientech. • Pokud uvažujeme analýzu citlivosti pravých stran, zkoumáme, jak můžeme změnit jednotlivou složku vektoru, aby řešení zůstalo přípustné. Uvažujeme však vždy změnu jen jedné složky 𝑏𝑖 , ostatní složky necháme nezměněné. Pro každou složku vypočítáme tzv. interval stability, to je hodnotu, ve které se může složka pohybovat, aby řešení zůstalo přípustné. Jelikož v s-tém kroku výpočtu je pravá strana B−1 𝑠 𝑏, kde B𝑠 je báze matice v s-tém kroku a b je původní vektor pravých stran, musí platit B−1 ≥ 0, aby 𝑠 bylo řešení přípustné. Pokud bychom chtěli vypočítat interval stability první složky vektoru b, musíme vyřešit soustavu nerovnic ⎛

⎜ 𝑏1 ⎜ ⎜ ⎜ ⎜ B−1 𝑠 ⎜ ⎜ ⎜ ⎝

⎞

+ Δ𝑏1 ⎟ ⎟ ⎟ 𝑏2 ⎟ ⎟ ≥ 0. ⎟ .. ⎟ . 𝑏𝑚

⎟ ⎠

B−1 𝑠 je inverzní matice báze v s-tém kroku, 𝑏𝑖 (pro 𝑖 = 1, 2, ..., 𝑚) jsou prvky vektoru b a Δ𝑏1 je přípustná změna hodnoty 𝑏1 .

Obr. 3.6: Analýza citlivosti pro změnu koeficientů pravých stran. 2

Text vychází z [8].

28

ČVUT v Praze


• Druhá metoda citlivostní analýzy zkoumá, jak se mohou měnit jednotlivé složky vektoru c, aby stávající řešení zůstalo optimální. Stejně jako v prvním případě se uvažuje změna vždy jen jedné položky. Určujeme interval stability složek vektoru cenových koeficientů. Aby řešení zůstalo optimální, musí v případě maximalizační úlohy platit

𝑧𝑗 = c𝑇𝐵 B−1 a𝑗 − 𝑐𝑗 ≥ 0 (𝑗 = 1, 2, ..., 𝑚) ∧ 𝑢𝑖 = c𝑇𝐵 B−1 𝑠 ≥ 0 (𝑖 = 1, 2, ..., 𝑚). Pokud tedy máme nějaká data a máme k nim nějaké upřesňující údaje (například informaci o tom, jak byla data získaná, jaká je jejich odchylka, apod.), můžeme zvolit následující postup: • vypočítáme optimum z dostupných dat, • spočítáme optimum pro různě pozměněná vstupní data, • odhadneme, kolik by stálo upřesnění dat, • porovnáme rozdíl mezi cenou dat a možným zlepšením optimálního řešením. Se změnou vstupních dat souvisí tzv. citlivostní analýza, která byla nastíněna na začátku této podkapitoly. Pokud tedy vyjde získání přesnějších dat dráž, než předpokládané nejhorší řešení, není třeba investovat do získání takových dat prostředky. Vyjde-li získání dat jako výhodnější varianta, je vhodné nechat data upřesnit. Pokud však vyjde získání dat výhodněji jen zanedbatelně, je vhodné zvážit další postup. Lineární programování s měnícími se omezujícími podmínkami Další možnou variantou klasického lineárního programování je případ, kdy nejsou přesně definované omezující podmínky, které se například mohou měnit v čase, nebo je známe jen s určitou pravděpodobností. Jedná se o náhodný proces, který nelze ovlivnit, ale můžeme se snažit mu přizpůsobit. Příklad podmínek měnících se v čase může být například cena energií a surovin, množství zaměstnanců (z důvodu dovolené či nemoci), apod. Na druhé straně omezující podmínky známé s určitou pravděpodobností může být například poptávka odvozená na základě statistiky, kterou si podnikatel vede.

29

ČVUT v Praze


Obr. 3.7: Příklad změny optimálního řešení podle změny vstupních dat. Na základě takové statistiky je možné vypozorovat trendy, které se v uplynulém čase objevily, a ty do modelu zahrnout. Lineární programování s měnící se účelovou funkcí Během času se může měnit účelová funkce v závislosti na aktuálních podmínkách. Může docházet k jednorázovému náhodnému šumu, nebo je možné ve změnách vysledovat určitý trend. Změna účelové funkce ve 4 krocích je pro ilustraci znázorněna na obrázcích 3.8 - 3.11. V takovém případě je potřeba optimalizovat průběžně v čase. Podle výsledků je pak možné vypozorovat vliv změny účelové funkce na optimální řešení a přizpůsobit se. Jedna varianta je znázorněna na obrázku 3.12. Jedná se o situaci, kdy optimální řešení vlivem změn účelové funkce přeskakuje mezi několika řešeními. Jedno řešení však převládá a v takovém případě je možné využít tuto hodnotu s ohledem na to, že někdy bude optimální řešení ziskové a jindy naopak ztrátové, v průměru se však tyto hodnoty vyrovnají.

30

ČVUT v Praze


Obr. 3.8: účelová funkce v čase 𝑡1




31

ČVUT v Praze


Obr. 3.12: Optimální řešení kolísá kolem průměrné hodnoty

Obr. 3.13: Optimální řešení obsahuje náhodný šum Na obrázku 3.13 je zobrazena další možnost, jak se vyvíjí optimální řešení při změnách účelové funkce. Optimální řešení kopíruje nebo se jen s malými odchylkami oddaluje od jedné hodnoty, ale náhodně se občas v účelové funkci objeví šum, který není možné předvídat. Takovéto výkyvy je třeba z určení optimálního řešení vyřadit. Optimální řešení může mít vlivem změn v účelové funkci s postupujícím časem stoupající (nebo naopak klesající) tendenci, jak je znázorněno na obrázku 3.14. Pokud je tento trend patrný v dlouhodobém časovém intervalu, je vhodné ho zahrnout do budoucích plánů.

3.5

Klouzavá optimalizace

Klouzavou optimalizací je míněna situace, kdy plánujeme na delší období v kratších časových intervalech.

32

ČVUT v Praze


Obr. 3.14: Optimální řešení má stoupající tendenci Po vybraném intervalu vždy provedeme novou optimalizaci s ohledem na události, které mají v budoucnu nastat. Výsledek této optimalizace pak používáme, dokud neuplyne časový interval. Při nové optimalizaci předchozí řešení „zapomeneme“ a provedeme novou optimalizaci. Můžeme optimalizovat s ohledem na všechny nadcházející události, nebo můžeme stanovit časový úsek, který bude brán v úvahu při každé optimalizaci. Tento scénář je zobrazen na obrázku 3.15, kde jsou brány v potaz všechny události bez ohledu na to, jak vzdálené v čase jsou. V čase 𝑡1 optimalizujeme s výhledem na 𝑡′1 , v čase 𝑡2 stávající řešení zahodíme a optimalizujeme s výhledem na 𝑡′2 , atd.

33

ČVUT v Praze


Obr. 3.15: Klouzavá optimalizace

34

ČVUT v Praze

4

4. ÚLOHA

Úloha

4.1

Zadání úlohy

Lékárník vyrábí 3 druhy čerstvých mastí, které je možné prodat maximálně 30 dní od výroby. Pokud je do 30 dnů neprodá, musí je zlikvidovat, přijde tím o peníze, které do výroby byly vloženy. S každou výrobou jsou na druhou stranu spojeny náklady, které nezávisí na vyráběném množství. Tyto náklady jsou spojeny s časem potřebným k výrobě a energiemi a činí 1000 Kč na každou mast. Druh masti

Cena

Náklady

Mast proti akné

550

470

Mast proti lupence

1020

880

Mast proti ekzému

930

760

Tab. 4.1: Ceny jednotlivých druhů mastí a náklady na jejich výrobu Lékárník se průběžně dozvídá objednávky na množství mastí. Masti odesílá vždy v den, na který je objednávka určena, v tento den již není možné objednávku zrušit. Pokud lékárník nemůže dodat daný den mast, protože jich nemá dostatek, dodá množství, které má. Za každou nedodanou položku však zaplatí odběrateli penále ve výši 50 Kč. Každý den přijdou průměrně 4 nové zakázky, výjimečně jich může být až 10 nebo nemusí přijít žádná. Den, kdy musí být objednávka odeslána, je obvykle v rozmezí od 0 do 30 dní, bližší dny mají častější výskyt něž ty vzdálenější. Poptávka po jednotlivých druzích masti je následující: • mastí proti akné se prodá průměrně 6 ks denně, • mastí proti lupence se prodá průměrně 3 ks denně, • mastí proti ekzému se prodá průměrně 3 ks denně. V průměru jsou rušeny 2 objednávky ze 100, vždy jsou zrušeny celé, nelze zrušit jen jejich část.

35

ČVUT v Praze

4. ÚLOHA

Nasimulujte, jak přichází objednávky, na kdy jsou určeny, jaká je jejich velikost, jak jsou rušeny, a zvolte vhodnou strategii pro výrobu.

4.2

Rozbor úlohy

Úloha se dá chápat jako úloha teorie řízení zásob s pravděpodobnostní znalostí poptávky, která je popsána v kapitole 3.2.2 na straně 21, konkrétně jako určitý druh P-systému, protože se optimalizuje po pevně daných časových intervalech. Není zde však dáno omezení velikosti skladovaných zásob. Částečně lze tuto úlohu pojmout jako klouzavou optimalizaci, která je popsána v kapitole 3.5 na straně 32, protože po uplynutí časového intervalu zhodnotíme zásoby a nové objednávky a podle nich se rozhodneme, jestli budeme vyrábět další produkty a případně kolik jich vyrobíme. Ze zadání známe následující hodnoty: • průměrný počet nových objednávek během jednoho dne, • průměrnou velikost každé nové objednávky, • průměrná denní poptávka po jednotlivých druzích mastí • den vyřízení objednávky, • jak často jsou objednávky rušeny, • cenu, za kterou lékárník jednotlivé masti prodá, • náklady na každou vyrobenou mast, • náklady spojené s výrobou libovolného množství mastí, • penále za nedodání objednávky, • „trvanlivost“ mastí. Přehled těchto hodnot je v tabulce 4.3 na straně 38.

4.3

Způsob řešení

Pro zadanou úlohu byl zvolen postup, při němž se po zvoleném časovém intervalu provede

36

ČVUT v Praze

4. ÚLOHA

Proměnná

Hodnota

průměr objednávek

4 objednávky

průměrná velikost celé objednávky

3 ks

denní poptávka po 1. masti

6 ks


3 ks


3 ks

průměrný interval, za kdy má být objednávka vyřízena

15

pravděpodobnost zrušení objednávky

2%

prodejní cena 1. masti

550 Kč


1020 Kč


920 Kč

náklady na výrobu 1. masti

470 Kč


880 Kč


760 Kč

jednorázové náklady na výrobu jednoho druhu masti

1000 Kč

penále za každou nedodanou položku z objednávky

50 Kč

„trvanlivost“ masti

30 dní

Tab. 4.2: Přehled hodnot, které byly uvedeny v zadání úlohy • zkontrolování množství zásob, • zhodnocení velikosti budoucích objednávek, • výroba produktů. Při hodnocení budoucích objednávek je omezeno množství objednávek časovým úsekem, za nímž nás nově příchozí objednávky již nezajímají. Simulace proběhla pro 5 velikostí intervalu a pro 3 velikosti období, na které bylo optimalizováno.

37

ČVUT v Praze

4. ÚLOHA

velikost intervalu

velikost období

[dny]

optimalizace [dny]

2

10

4

20

6

30

8

-

10

-

Tab. 4.3: Přehled hodnot, které byly uvedeny v zadání úlohy

4.4

Simulace

Simulace byla provedena v programu GNU Octave. Prováděla se po dnech na 500 dní s 50 opakováními. V simulaci byly použity různé vstupní hodnoty pro interval optimalizace a pro dobu, na kterou se optimalizuje.

4.4.1

GNU Octave

GNU Octave je otevřený software a programovací jazyk pro numerické výpočty. Základ struktury tvoří matice. GNU Octave vznikl v roce 1988, od roku 1992 se začal vyvíjet. Je napsán v jazyce C++ s využitím knihoven C++. Je z velké části kompatibilní s programem MATLAB.

4.4.2

Popis simulace

∙ nastav výdělek a ztráty na hodnotu 0; ∙ zvol interval, po kterém se bude určovat, kolik je třeba vyrobit nových mastí; ∙ zvol dobu, na jakou se bude brát ohled při optimalizaci v první den intervalu; ∙ proveď následující simulaci pro 500 dní a opakuj ji 50x: ∘ vygeneruj, kolik přišlo nových objednávek (generuj z normálního rozdělení s 𝜇 = 4 a 𝜎 = 2, hodnotu zaokrouhli); ◇ pokud je vygenerovaná hodnota záporná, oprav ji na 0;

38

ČVUT v Praze

4. ÚLOHA

◇ vygeneruj velikost každé nové objednávky (generuj z normálního rozdělení s 𝜇 = 3 a 𝜎 = 2, hodnotu zaokrouhli); ∙ pokud je vygenerovaná hodnota menší než jedna, oprav ji na 1; ◇ rozděl velikost objednávky mezi nabízené produkty; ∙ vygeneruj hodnotu poptávky po 1. položce (generuj z rovnoměrného rozdělení na intervalu od 1 do velikosti objednávky, zaokrouhli na celé číslo), odečti ji od velikosti objednávky; ∙ vygeneruj hodnotu poptávky po 2. položce (generuj z rovnoměrného rozdělení na intervalu od 1 do nové velikosti objednávky, zaokrouhli na celé číslo), odečti ji od velikosti objednávky; ∙ zbylá velikost objednávky tvoří poptávku po 3. položce; ∘ vygeneruj, kolik přišlo žádostí na zrušení objednávky (generuj z normálního rozdělení s 𝜇 = 0.1 a 𝜎 = 0.2, hodnotu zaokrouhli); ◇ pokud je hodnota záporná, oprav ji na 0; ◇ vygeneruj index dne, kdy má být objednávka zrušena (generuj z rovnoměrného rozdělení od 1 do množství objednávek, které znáš, hodnotu zaokrouhli); ∙ pokud je objednávka v budoucnu, zruší se; ∙ pokud je objednávka v aktuální den, nelze ji zrušit; ∘ vygeneruj den, kdy mají být jednotlivé objednávky odeslány (generuj z 𝜒2 (𝑛), kde 𝑛 = 15); ∘ přidej nové objednávky ke stávajícím; ∘ seřaď dny od nejbližšího po nejvzdálenější, promíchej i objednávky tak, aby odpovídaly dnům, ke kterým byly vygenerovány, použij k tomu vytvořenou funkci serad.m; ∘ pokud nastal den, kdy se rozhoduje, kolik se má vyrobit dalších mastí: ◇ vyber zakázky, které mají být vyřízeny během období, na které optimalizujeme; ◇ sečti objednávky pro danou položku v optimalizovaném období; ◇ pro každou mast proveď:

39

ČVUT v Praze

4. ÚLOHA

∙ pokud je poptávka po dané masti větší, než množství mastí, které zbyly z minulé výroby: ∘ pokud je denní poptávka po dané masti vyšší než je průměr, vyrob tolik mastí, kolik jich chybí k pokrytí této poptávky; ∘ pokud je denní poptávka menší než je průměr, vyrob tolik mastí, abys s již vyrobenými mastmi pokryl průměrnou poptávku; ∘ přičti fixní náklady na výrobu masti k celkovým nákladům; ∙ pokud je poptávka po menší, než kolik mastí zbývá z minulých výrob, nevyráběj nic; ◇ množství jednotlivých vyrobených mastí přidej do seznamu a přiřaď k nim den expirace; ◇ pro každou objednávku s hodnotou dne 0 proveď pro každou mast zvlášť: ∙ uspokoj objednávku výrobky s nejnižší hodnotou expirace; ∙ pokud je objednávka nižší, než množství výrobků s nejnižší expirací: ∘ za každou uspokojenou položku přičti k výdělku marži na danou mast; ∘ sniž množství výrobků o velikost objednaných mastí; ∘ přepiš hodnotu poptávky na 0; ∙ pokud je objednávka vyšší, než množství výrobků s nejnižší expirací: ∘ použij výrobky s následující nejnižší expirací, opakuj, dokud není uspokojena celá objednávka nebo nedojdou výrobky; ∘ za každou uspokojenou položku přičti k výdělku marži na danou mast; ∘ uprav velikost poptávky a zásoby výrobků; ∘ za každou neuspokojenou položku v případě, že není dostatečná zásoba mastí, zaplať penále; ∘ od každého dne objednávky a od každého dne expirace odečti 1; ∘ pokud hodnota expirace klesne na 0:

40

ČVUT v Praze

4. ÚLOHA

◇ přičti ke ztrátě náklady za každou položku, která prošla expirací ◇ vymaž zásoby s prošlou expirací ∘ pokud hodnota dne klesne pod nulu: ◇ přičti k výdělku výnos z dané objednávky; ◇ vymaž objednávku ze seznamu; ∘ vrať se na začátek a postup opakuj; ∙ v každém kroku přičti ke ztrátám a výdělkům jejich hodnoty z proběhlé simulace; ∙ po provedení celého postupu vypočítej průměr ztrát a výdělků; ∙ změň vstupní parametry a celý postup opakuj;

4.5 4.5.1

Kód simulace Opakované provedení simulace

Tento kód spouští simulaci, počítá průměrné hodnoty výdajů a ztrát/nákladů a zapisuje výsledky do samostatného textového souboru vysledky.txt. ...

for j=1:size(intervaly)(1,2) fprintf(soubor, ’INTERVAL OPTIMALIZACE JE ’) fprintf(soubor, ’%.0f’, intervaly(j)) fprintf(soubor, ’\n’) for k=1:size(vyhledy)(1,2) fprintf(soubor, ’VYHLED PRO OPTIMALIZACI JE ’) fprintf(soubor, ’%.0f’, vyhledy(k)) fprintf(soubor, ’\n’)

interval = intervaly(j); vyhled = vyhledy(k);

41

ČVUT v Praze

4. ÚLOHA

vydelek1 = 0; ztrata1 = 0; ztrata_nedostatek1 = 0; vydaje1 = 0; celkem1 = 0;

for i=1:opakovani [vydelek,ztrata,ztrata_nedostatek,vydaje,celkem] =... ...simulace(obdobi,interval,cena,naklady,vyhled,rozloz_zak,... ...prum_zakazek,vyrobni_naklady,prum_poptavka, penale);

vydelek1 = vydelek1+vydelek/obdobi; ztrata_nedostatek1 = ztrata_nedostatek1... ...+ztrata_nedostatek/obdobi; ztrata1 = ztrata1+ztrata/obdobi; vydaje1 = vydaje1+vydaje/obdobi; celkem1 = celkem1+celkem/obdobi; end

%%vypis vysledku do souboru fprintf(soubor, ’prumerny vynos z prodanych polozek = ’) fprintf(soubor, ’%.4f ’, vydelek1) fprintf(soubor, ’\n’) fprintf(soubor, ’prumerny celkovy obrat = ’) fprintf(soubor, ’%.4f’, celkem1) fprintf(soubor, ’\n’) fprintf(soubor, ’prumerna ztrata za prosle vyrobky = ’) fprintf(soubor, ’%.4f’, ztrata1) fprintf(soubor, ’\n’) fprintf(soubor, ’prumerna ztrata z nedostatku zasob = ’) fprintf(soubor, ’%.4f’, ztrata_nedostatek1)

42

ČVUT v Praze

4. ÚLOHA

fprintf(soubor, ’\n’) fprintf(soubor, ’prumerne vydaje za vyrobu masti = ’) fprintf(soubor, ’%.4f’, vydaje1) fprintf(soubor, ’\n’) fprintf(soubor, ’====================================’) fprintf(soubor, ’\n’) end end

fclose(soubor); %%zavre soubor, do ktereho byly vepsany vysledky

4.5.2

Samotná simulace

Protože je simulace napsána jako funkce, jsou na začátku definovány vstupní a výstupní parametry. Pod nimi jsou pak iniciovány hodnoty, které jsou potřebné pro správný běh funkce a výpočet hodnot, které nás zajímají (výdělek a ztráty rozdělené podle toho, za co byly utržené). function[vydelek,ztrata,ztrata_nedostatek,vydaje,celkem]... ...=simulace(obdobi,interval,cena,naklady,vyhled,rozloz_zak,... ...prum_zakazek,vyrobni_naklady,prum_poptavka, penale) vydelek = 0; celkem = 0; ztrata = 0; vydaje = 0; ztrata_nedostatek = 0; den = [0 0 0 0]; vyrob = [0 0 0 0]; ... V následujícím kódu začíná simulace po dnech pro námi zvolené období).

43

ČVUT v Praze

4. ÚLOHA

Nejprve jsou vygenerovány pro každý den nové zakázky. Pro každou novou zakázku se pak generuje její velikost (kolik mastí celkem je třeba vyrobit) a poté se tato hodnota rozdělí mezi tři nabízené produkty vygenerováním hodnoty z rovnoměrného rozdělení a jejím zaokrouhlením na celé číslo. ... for i=1:obdobi p = []; %%VYGENEROVANI NOVYCH ZAKAZEK nove = round(normrnd(prum_zakazek,2)); if nove > 0 for m=1:nove velikost_zakazky(m) = round(normrnd(3,2));

if velikost_zakazky(m) < 1 velikost_zakazky(m) = 1; end p(m,2) = round(rand(1)*velikost_zakazky(m)); velikost_zakazky(m) = velikost_zakazky(m)-p(m,2); p(m,3) = round(rand(1)*velikost_zakazky(m)); velikost_zakazky(m) = velikost_zakazky(m)-p(m,3); p(m,4) = velikost_zakazky(m); end else nove = 0; end %%NOVE OBJEDNAVKY JSOU VYGENEROVANY ...

44

ČVUT v Praze

4. ÚLOHA

V dalším kroku se vygeneruje, kolik přišlo žádostí o zrušení objednávky. Generuje se z náhodného rozdělení a výsledná hodnota se zaokrouhlí na celé číslo. Pokud je toto číslo záporné, přepíše se na 0. Pokud by vygenerovaných žádostí o zrušení bylo víc, než kolik je objednávek, nastaví se množství pro zrušení na množství objednávek. Poté se vygeneruje index objednávky ke zrušení, generuje se z rovnoměrného rozdělení a vygenerovaná hodnota se zaokrouhlí na celé číslo. Zkontroluje se den, kdy má být objednávka zrušena. Pokud se jedná o aktuální den, objednávku nelze zrušit. ... %%VYGENERUJE SE ZRUSENI OBJEDNAVEK if i > 1 zrus = round(normrnd(0.1,0.2)); if zrus < 0 zrus = 0; end

if zrus > size(den)(1,1) zrus = size(den)(1,1) end

den_zrus = [];

if zrus > 0 for o=1:zrus den_zrus(o,1) =... ...round((size(den)(1,1)-1)*rand(1))+1; end den_zrus = sort(den_zrus); end

45

ČVUT v Praze

4. ÚLOHA

for k=1:zrus if den_zrus(zrus+1-k,1) > size(den)(1,1) den_zrus(zrus+1-k,1) = size(den)(1,1); end

if den(den_zrus(zrus+1-k),1) > 0 den(den_zrus(zrus+1-k),:) = []; else den(den_zrus(zrus+1-k),:) =... ...den(den_zrus(zrus+1-k),:) ; end end end %%OBJEDNAVKY JSOU ZRUSENY ...

Dále se vygeneruje ke každé nové objednávce den, ve kterém má být objednávka odeslána. Generuje se z rozdělení 𝜒2 s průměrným dnem zakázky 𝑛. Poté se nové zakázky přiřadí k zakázkám stávajícím. Protože vygenerované dny nejsou setříděné, je třeba je seřadit a spolu s nimi seřadit i objednávky, které k nim náleží. K tomu je napsána vlastní funkce serad.m, která je uvedena v následující podkapitole na straně 52. ... %%PRIPOJI NOVE OBJEDNAVKY KE STAVAJICIM if nove > 0 p1 = p(:,2); p2 = p(:,3); p3 = p(:,4); zakazky = round(chi2rnd(rozloz_zak,[1,nove])); den1 = [zakazky’ p1 p2 p3];

46

ČVUT v Praze

4. ÚLOHA

if i == 1 den = den1; else den = [den;den1]; end [den] = serad(den); end %%OBJEDNAVKY JSOU POHROMADE ...

V následujícím kódu se vždy v den výroby určuje, kolik (popřípadě jestli) se má vyrábět mastí. Nejprve se vyberou zakázky, které jsou poptávány v období, na které jsme se rozhodli brát zřetel. Pak se zjistí poptávka po jednotlivých produktech v tomto období a stav zásob z předchozích výrob. Pokud je stav zásob vyšší než průměrná poptávka po dané masti, nebude se v tomto období vyrábět vůbec. V opačném případě se poptávka po každé masti porovná s průměrnou poptávkou. Pokud je skutečná poptávka vyšší, než poptávka průměrná, vyrobí se tolik mastí, aby se doplnil stav zásob na hodnotu skutečné poptávky. Pokud je skutečná poptávka naopak menší, vyrobí se tolik mastí, aby se doplnil stav zásob na hodnotu průměrné poptávky. ... %%PRVNI DEN V OBDOBI SE URCUJE, KOLIK SE VYROBI KTERE POLOZKY if rem(i,interval) == 1 || interval == 1 %vydaje = vydaje+vyrobni_naklady; k = size(den)(1,1); s1 = den(:,2); s2 = den(:,3); s3 = den(:,4);

47

ČVUT v Praze

4. ÚLOHA

while den(k,1) > vyhled if k > 1 s1(k) = []; s2(k) = []; s3(k) = []; k = k-1; else break end end pol1 = round(sum(s1)/vyhled); pol2 = round(sum(s2)/vyhled); pol3 = round(sum(s3)/vyhled); if sum(vyrob(:,2)) < pol1*interval vydaje = vydaje+vyrobni_naklady; if pol1 > prum_poptavka(1) vy1 = round(pol1*interval)-sum(vyrob(:,2)); elseif pol1 <= prum_poptavka(1) vy1 =

round(prum_poptavka(1)*interval)...

...-sum(vyrob(:,2)); end elseif sum(vyrob(:,2)) >= pol1*interval vy1 = 0; end

if sum(vyrob(:,3)) < pol2*interval vydaje = vydaje+vyrobni_naklady; if pol2 > prum_poptavka(2) vy2 = round(pol2*interval)-sum(vyrob(:,3)); elseif pol2 <= prum_poptavka(2) vy2 =


48

ČVUT v Praze

4. ÚLOHA

...-sum(vyrob(:,3)); end elseif sum(vyrob(:,3)) >= pol2*interval vy2 = 0; end

if sum(vyrob(:,4)) < pol3*interval vydaje = vydaje+vyrobni_naklady; if pol3 > prum_poptavka(3) vy3 = round(pol3*interval)-sum(vyrob(:,4)); elseif pol3 <= prum_poptavka(3) vy3 =


...-sum(vyrob(:,4)); end elseif sum(vyrob(:,4)) >= pol3*interval vy3 = 0; end vyrob(size(vyrob)(1,1)+1,:) = [30 vy1 vy2 vy3]; end %%KONEC VYROBY ...

V této části se vyřizují objednávky. Pokud je hodnota dne 0, znamená to, že má být zakázka vyřízena. Pro každou položku v matici, kde den == 0, se tedy vyřídí objednávka. Nejprve se sáhne do zásob s nejmenší dobou vhodnou k prodeji. Pokud nemůže být celá zakázka uspokojena z této várky, sáhne se do várky následující. Pokud nemůže být uspokojena celá poptávka, vyřídí se z ní taková část, která je k dispozici. Za každou nevyřízenou položku je naúčtováno penále ve výši 50 Kč. ... %%ODESLANI OBJEDNAVKY

49

ČVUT v Praze

4. ÚLOHA

delka = size(den)(1,1); if delka == 1 den; end j = 1; while

j <= delka

if den(j,1) == 0 vel_vyrob = size(vyrob)(1,1); for m=2:4 if den(j,m) <= vyrob(1,m) vydelek = vydelek+den(j,m)*(cena(m-1)... ...-naklady(m-1)); vyrob(1,m) = vyrob(1,m) - den(j,m); den(j,m) = 0; else k = 1; while k <= vel_vyrob if den(j,m) > 0 if

den(j,m)

<= vyrob(k,m)

vydelek = vydelek+den(j,m)*... ...(cena(m-1)-naklady(m-1)); vyrob(k,m) = vyrob(k,m)-den(j,m); den(j,m) = 0; else vydelek = vydelek+vyrob(k,m)... ...*(cena(m-1)-naklady(m-1)); den(j,m) = den(j,m) - vyrob(k,m); vyrob(k,m) = 0; if vyrob(k,m) == 0 if k==vel_vyrob ztrata_nedostatek =...

50

ČVUT v Praze

4. ÚLOHA

...ztrata_nedostatek... ...+den(j,m)*penale; end end end else k = vel_vyrob; end k = k+1; end end end else j = delka; end j = j+1; end %%OBJEDNAVKY VYRIZENY ...

V následující části kódu se aktualizují objednávky a stav zásob - od každého dne objednávky i „trvanlivosti“ výrobku se odečte jeden den. Pokud pak hodnota dne objednávky klesne pod 0, znamená to, že byla objednávka vyřízena a je tedy vymazána ze seznamu aktuálních objednávek. Totéž platí pro seznam vyrobených mastí. V případě, že existují zásoby, které musí být vyřazeny ze seznamu, jedná se o ztrátu, kterou je potřeba započítat k dosud vzniklým ztrátám (díky vhodně zvoleným intervalům optimalizace, výhledového období a velikostem výroby však k těmto ztrátám nedochází). ... %%AKTUALIZACE OBJEDNAVEK A ZASOB

51

ČVUT v Praze

4. ÚLOHA

den(:,1) = den(:,1)-1; vyrob(:,1) = vyrob(:,1)-1; for k=1:delka if den(delka+1-k) < 0 den(delka+1-k,:) = []; end end

for j=1:size(vyrob)(1,1) if vyrob(size(vyrob)(1,1)+1-j,1) < 0 ztrata = ztrata... ...+naklady(1)*vyrob(size(vyrob)(1,1)+1-j,2)... ...+naklady(2)*vyrob(size(vyrob)(1,1)+1-j,3)... ...+naklady(3)*vyrob(size(vyrob)(1,1)+1-j,4); vyrob(size(vyrob)(1,1)+1-j,:) = []; end end %%OBJEDNAVKY A ZASOBY JSOU AKTUALIZOVANY end end

4.5.3

Funkce na setřídění matice

Ačkoliv Octave disponuje funkcí sort(), bylo nutné naprogramovat vlastní funkci pro třídění. Funkce sort() seřadí prvky v celé matici nebo ve vybraném sloupci. Pro tuto simulaci však bylo potřeba setřídit vzestupně jen první sloupec matice a s tímto prvkem prohodit celý řádek matice. Pro setřídění byl pro svou jednoduchost zvolen zvolen algoritmus bubble-sort. function[serazeno]=serad(den) X = den(:,1); Y1 = den(:,2);

52

ČVUT v Praze

4. ÚLOHA

Y2 = den(:,3); Y3 = den(:,4); for i=1:(length(X)-1) for j=1:(length(X)-i) if(X(j) > X(j+1)) x = X(j); X(j) = X(j+1); X(j+1) = x; y1 = Y1(j); Y1(j) = Y1(j+1); Y1(j+1) = y1; y2 = Y2(j); Y2(j) = Y2(j+1); Y2(j+1) = y2; y3 = Y3(j); Y3(j) = Y3(j+1); Y3(j+1) = y3; end end end serazeno(:,1) = X’; serazeno(:,2) = Y1’; serazeno(:,3) = Y2’; serazeno(:,4) = Y3’; serazeno; end

4.6

Výsledky

V tabulce 4.6 jsou uvedeny výsledky simulace pro 5 optimalizačních intervalů a pro 3 období, která jsou brána v potaz při optimalizaci výroby.

53

ČVUT v Praze

4. ÚLOHA

Na obrázku 4.1 na straně 55 je pak pro zpřehlednění graf, který pro všechny vstupní kombinace, znázorňuje následující hodnoty: • průměrný denní výdělek za prodané masti, • průměrný denní obrat, • průměrná denní ztráta za nedostatek zboží.

Interval

Optimali-

Denní

Celkový

Denní ztráta

Denní nákla-

optimali-

zační

výdělek

denní pří-

z nedostatku

dy na výrobu

zace [d]

období [d]

[Kč]

jem [Kč]

zboží [Kč]

[Kč]

2

10

12101.40

-3117.10

848.50

14370.00

2

20

10843.96

-4410.14

1450.10

13804.00

2

30

10483.76

-3704.64

1608.40

12580.00

4

10

12958.56

5211.66

440.90

7306.00

4

20

11680.88

3458.38

998.50

7224.00

4

30

11416.24

3414.74

1147.50

6854.00

6

10

13521.52

8323.92

257.60

4940.00

6

20

12149.36

6385.06

866.30

4898.00

6

30

11501.92

6004.82

869.10

4628.00

8

10

13770.16

9916.26

141.90

3712.00

8

20

12301.96

7909.46

706.50

3686.00

8

30

12102.52

7663.32

849.20

3590.00

10

10

13913.64

10919.94

55.70

2938.00

10

20

12527.76

8905.76

690.00

2932.00

10

30

12247.16

8587.56

787.60

2872.00

Tab. 4.4: Výsledky simulace pro různé vstupní hodnoty Jelikož z tohoto přehledu není na první pohled patrné, který přístup je vhodný a který nevhodný, byly výsledky seřazeny podle dvou parametrů. V tabulce 4.5 na straně 56 jsou seřazeny hodnoty podle průměrného denního obratu. Všechny verze s velikostí intervalu 2 jsou ztrátové. Je to způsobeno především

54

ČVUT v Praze

4. ÚLOHA

Obr. 4.1: Přehled výsledků simulace vysokými náklady na jednorázové vyrobení mastí a z důvodu krátkého intervalu malého množství vyráběných kusů. Všechny ostatní intervaly již byly ziskové, přesto jsou mezi nimi poměrně velké rozdíly v průměrném denním zisku. Hodnoty jsou zobrazeny v grafu na obrázku 4.2 na straně 56. Nejlépe se umístila varianta s intervalem 10 dní s výhledem na 10 dní. Následující varianta s intervalem 8 dní s výhledem na 10 dní měla přibližně o 10 % horší výsledek. Pokud by nás více než zisk zajímalo dobré jméno firmy, které se dá stavět například na spolehlivosti vyřízení zakázky, můžeme výsledné hodnoty seřadit podle průměrné denní ztráty z nedostatku zboží. Čím nižší tato hodnota je, tím méně objednávek se nepodařilo uspokojit. Takto seřazené hodnoty jsou zobrazeny v tabulce 4.6 na straně 57 a v grafu na obrázku 4.3 na straně 57. Z výsledků vyplývá, že i podle tohoto kritéria je nejvhodnější přístup optimalizovat po 10 dnech s výhledem na dalších 10 dní. Průměrná denní ztráta za nevyřízenou objednávku v tomto případě činí 56 Kč, druhý nejvhodnější přístup má tuto hodnotu téměř trojnásobnou. Z vybraných analyzovaných hodnot intervalu a výhledového období vychází jako nejvýhodnější kombinace 10 dní a 10 dní.

55

ČVUT v Praze

4. ÚLOHA

Interval

Optimalizační

Celkový denní

optimalizace [d]

obdobé [d]

příjem [Kč]

2

20

-4410.10

2

30

-3704.60

2

10

-311710

4

30

3414.70

4

20

3458.40

4

10

5211.70

6

30

6004.80

6

20

6385.10

8

30

7663.30

8

20

7909.50

6

10

8323.90

10

30

8587.60

10

20

8905.80

8

10

9916.30

10

10

10920.00

Tab. 4.5: Seřazené výsledné hodnoty podle průměrného denního obratu

Obr. 4.2: Seřazené hodnoty průměrného denního obratu

56

ČVUT v Praze

4. ÚLOHA

Interval

Optimalizační

Denní ztráty z nedostat-

optimalizace [d]

obdobé [d]

ku zboží [Kč]

10

10

55.70

8

10

141.90

6

10

257.60

4

10

440.90

10

20

690.00

8

20

706.50

10

30

787.60

2

10

848.50

8

30

849.20

6

20

866.30

6

30

869.10

4

20

998.50

4

30

1147.50

2

20

1450.10

2

30

1608.40

Tab. 4.6: Seřazené výsledné hodnoty podle průměrné denní ztráty z nedostatku zboží

Obr. 4.3: Seřazené hodnoty průměrné denní ztráty z nedostatku zásob

57

ČVUT v Praze

4.6.1

4. ÚLOHA

Výsledky z vypisovacího souboru

INTERVAL OPTIMALIZACE JE 2 VYHLED PRO OPTIMALIZACI JE 10 prumerny vynos z prodanych polozek = 12101.40 prumerny celkovy obrat =

-3117.10

prumerna ztrata z nedostatku zasob = prumerne vydaje za vyrobu masti =

848.50 14370.00

==================================== VYHLED PRO OPTIMALIZACI JE 20 prumerny vynos z prodanych polozek = 10843.96 prumerny celkovy obrat =

-4410.14


1450.10 13804.00


-3704.64


1608.40 12580.00

==================================== INTERVAL OPTIMALIZACE JE 4 VYHLED PRO OPTIMALIZACI JE 10 prumerny vynos z prodanych polozek = 12958.56 prumerny celkovy obrat =

5211.66


440.90 7306.00


3458.38

prumerna ztrata z nedostatku zasob =

58

998.50

ČVUT v Praze

4. ÚLOHA

prumerne vydaje za vyrobu masti =

7224.00


3414.74

prumerna ztrata z nedostatku zasob =

1147.50

prumerne vydaje za vyrobu masti =

6854.00


8323.92


257.60 4940.00


6385.06


866.30 4898.00


6004.82


869.10 4628.00


9916.26

59

ČVUT v Praze

4. ÚLOHA


141.90 3712.00


7909.46


706.50 3686.00


7663.32


849.20 3590.00


10919.94


55.70 2938.00


8905.76


690.00 2932.00


8587.56

60

ČVUT v Praze

4. ÚLOHA


787.60 2872.00

====================================

61

ČVUT v Praze

ZÁVĚR

Závěr Tato práce představila některé vybrané optimalizační úlohy a jejich aplikaci v prostředí, které není deterministicky definovatelné. V příkladu pak bylo takové náhodné prostředí použito, v programu GNU Octave pak vznikla simulace, která reprezentovala náhodně přicházející objednávky, jejich velikost, rozložení a případné rušení. Dále byl navržen postup, jak tyto objednávky uspokojovat a kdy vyrábět poptávané zboží. Pro vybrané časové intervaly a vybraná období, na která bude brán zřetel, byla provedena navržená simulace. Výsledky pro tyto vybrané hodnoty pak byly vzájemně porovnány.

62

ČVUT v Praze

POŽITÉ ZDROJE

Požité zdroje [1] DEMEL, Jiří. Operační výzkum. [online]. 2011 [cit. 2014-04-14]. Dostupné z: . [2] KOŘENÁŘ, Václav. Stochastické procesy. Vysoká škola ekonomická v Praze, 2002. ISBN 80-245-0311-5. [3] TER-MANUELIANC, A. Matematické modely řízení zásob. Praha, 1976. Institut řízení Praha. [4] CHAUDHURI, Surajit. An Overview of Query Optimization in Relational Systems. [online]. [cit. 2014-11-11]. Dostupné z: . [5] PETR, Václav. Optimalizace dotazů v relační databázi. [online]. 2009 [cit. 2014-11-11]. Dostupné z: . [6] HIGLE, Julia L. Stochastic Programming: Optimization When Uncertainty Matters. [online]. 2005 [cit. 2014-12-16]. Dostupné z: . [7] Optimalizace (matematika). In: Wikipedia: the free encyclopedia [online]. San Francisco (CA): Wikimedia Foundation, 2001- [cit. 2014-12-16]. Dostupné z: . [8] JABLONSKÝ, Josef. Operační výzkum: kvantitativní modely pro ekonomické rozhodování. 1. vyd. Praha: Professional Publishing, 2002, 323 s. ISBN 80-8641923-1.

63

ČVUT v Praze

A

A. CD

CD

64

ČESKÉ VYSOKÉ UČENÍ TECHNICKÉ V PRAZE FAKULTA STAVEBNÍ DIPLOMOVÁ PRÁCE

Recommend Documents