EKO210 Kvantitativní management. Creative Commons. Attribution-NonCommercial-ShareAlike 2.0. You are free:

EKO210 – Kvantitativní management Creative Commons

Attribution-NonCommercial-ShareAlike 2.0 You are free: •

to copy, distribute, display, and perform the work • to make derivative works Under the following conditions:

Attribution. You must give the original author credit.

Noncommercial. You may not use this work for commercial purposes.

Share Alike. If you alter, transform, or build upon this work, you may distribute the resulting work only under a license identical to this one. •

For any reuse or distribution, you must make clear to others the license terms of this work. • Any of these conditions can be waived if you get permission from the copyright holder.

Your fair use and other rights are in no way affected by the above. This is a human-readable summary of the Legal Code (the full license). Disclaimer

1

EKO210 – Kvantitativní management Prof. Jan Pelikán 407 n.b. Jablonský: Operační výzkum Výborná: Příklady Pelikán: Praktikum z OV Pelikán: Diskrétní modely Zkouška: Zadání praktické úlohy a jak budu postupovat při řešení daného problému. Když vyhovuje tak bez ústní. Na cvičeních se píší testy, které se započítávají do zkoušky. Osnova: - lineární programování (lineární optimalizační modely) - aplikace teorie grafů - teorie obnova (praktické návody kdy a za jakých podmínek obnovovat) - zásoby (jak optimalizovat zásobovací proces) - teorie front - vícekriteriální rozhodování

Lineární programování Př. Mám malý výrobní podnik truhlářskou dílnu, která zaměstnává 2 dělníky – truhlář a pomocný dělník. Truhlář je nasmlouván na 6 hodin denně. Pomocný dělník na 8 hodin denně. Předpokládáme výrobu skříněk a stolků. Všeho máme dostatek (materiálu). Trh vezme cokoliv a tak neomezuje počet výrobků vyrobených za den. Úkol: Naplánovat výrobu, kolik kterého výrobku denně vyrábět. Připouští se i zlomková hodnota, která představuje rozpracovanou výrobu. Nedokončený výrobek se dokončí druhý den. Cílem je maximalizace zisku Truhlář na V1 stráví 2 hodiny času a dělník také. Truhlář vyrábí stolek V2 1 hodinu a expedice a ostatní úkoly, které dělá dělník zabere 2 hodiny. Truhlář Dělník zisk

Skříňka V1 2 2 3 tis/ks

Stolek V2 1 2 2 tis/ks

6 h/den 8 h/den → max

Chceme 2 čísla: počet stolků a skříněk, nemusí být celá, ale nesmí být záporná, tak aby zisk byl maximální. Čísla musí být taková, aby truhlář tyto výrobky stihl vyrobit a dělník expedovat. Řešení: Lineární programování a metoda Simplexová. kroky: 1. napsat model (ten nelze automatizovat), převedení do matematické interpretace (matematického modelu) 2. předání počítači (simplexové metodě) 3. zhodnocení výsledků a jejich předání – Všechno je OK a tak se může pracovat, nebo není to v pořádku a tak se provede znova od začátku

2

EKO210 – Kvantitativní management Sestavení matematického modelu: - např. proměnné x1 a x2. - x1≥ 0 a x2 ≥ 0 === podmínka nezápornosti - cíl, ke kterému model bude směřovat. Musíme mu to předat ve tvaru matematické funkce. Můžu značit např: Z o Z = 3x1 + 2x2 → max - účelová funkce - .musíme zadat omezující podmínky: omezení truhláře je 6 – bilancuje spotřebu pracovních hodin truhláře s kapacitou hodin truhláře o 2x1 + 1x2 ≤ 6 - celkové zatížení truhláře (nepředepisujeme, že musí být maximálně vytížen, cílem je maximalizace zisku nikoliv kapacity) - musíme zadat omezení: omezení dělníka je 8 – bilancuje spotřebu pracovních hodin dělníka s kapacitou hodin dělníka o 2x1 + 2x2 ≤ 8 - celkové zatížení dělníka - pokud by byli v zadání další omezení, tak bychom je přidali i do matematického modelu.

Teorie: -

-

přípustné řešení x = (x1;x2) – vektor x je dvojice čísel, které jsou nezáporné a splňují naše podmínky. Nejde o maximalizaci, ale musí být splněny podmínky a cíl. Jakákoliv dvojice čísel splňující zatížení i podmínku nezápornosti. o (0;0) je přípustné řešení, (1;1) také přípustné, (100;100) jíž přípustné není, protože se přesáhne celkové zatížení optimální řešení je přípustné řešení, které maximalizuje zisk (účelovou funkci) to nejlepší možné řešení o Přípustné řešení x0 je optimální, jestliže pro všechna x přípustná je Z(x) ≤ 7(x0)

Grafické řešení: x2 Simplexová metoda – porovnává vrcholy a to jen některé

6

3

x1

každý bod bude vyjadřovat přípustná řešení, která splňují nerovnost 2x1 + 1x2 ≤ 6 (polorovina) a já to musím převést na přímku 2x1 + 1x2 = 6. Nejdříve dosadím za x1 nulu a

3

EKO210 – Kvantitativní management pak za x2 dosadím nulu. Hraniční přímka ukazuje, co je schopen vyrobit truhlář, když je plně vytížen. (3;0), (0;6) Omezení pro dělníka je hraniční přímka 2x1 + 2x2 = 8 dosadím (0;4), (4;0) P = množina přípustných řešení = včetně hranic - Množina je vypuklá a patří do ní vše, v daném 4 úhelníku. - Množina je ohraničena úsečkami. - vrcholy = význačné body, kde se hranice lomí - přípustných řešení je nekonečně mnoho Vrstevnice nám představují body se stejnou hodnotou účelové funkce účelová fce má tvar např: 3x1 + 2x2 = 0, jde o body např: (0;0) a zároveň (3;2), protože to je vektor kolmý k této fci. 3x1 + 2x2 = 1 Optimální řešení je první. Z není uvnitř, ani na hranici, ale ve vrcholu.

U tohoto patologického řešení není řešení jedno, ale je jich nekonečně mnoho a je vymezena 2 vrcholy, které jsou optimální (alternativní vrcholy) x = λxa + (1- λ)xb 1≥λ≥0 Další možnost:

Tato úloha má množinu P prázdnou, protože průnik mají v jiném kvadrantu P = 0. Např. mám špatné zvolené koeficienty ---> uvolnit nějaké kapacity. 4

EKO210 – Kvantitativní management

Množina přípustných řešení je neomezená, možných řešení je nekonečno a nelze najít optimální řešení. Řešením je, že jsme zapomněli na nějaké omezení (voda, dělníci). Musíme přezkoumat model, správné a všechny údaje Další možnost. existuje jen jediný výrobní program, který mohu vyrábět.

Věta (vlastnost) 1: Množina přípustných řešení je konvexní Věta 2 (základní věta): má-li úloha lineárního programování optimální řešení ==> má optimální řešení ve vrcholu D. Významy: a) neexistuje optimální řešení b) existuje optimální řešení, které je jediné a pak je ve vrcholu, nebo není jediné pak je ve více vrcholech i mimo vrcholy. optimální řešení nemá smysl hledat uvnitř množiny přípustných řešení. Je dobré ho hledat ve vrcholech. Budu porovnávat tedy jen těch několik vrcholů a to dělá Simplexová metoda. Z(x1;x2;...;x3) = c1x1 + c1x2 + ...+cnxn

x se buď maximalizuje nebo minimalizuje c se nazývá ceny omezující podmínky x1 ≥ 0, x2 ≥ 0, ..., xn ≥ 0 a11x1 + a12x2+...+a1nxn ≤ b1 první omezení a21x1 + a22x2+...+a2nxn ≤ b2 druhé omezení omezení může být n. Libovolný počet rovnic naprosto nezávisí na počtu proměnných

5

EKO210 – Kvantitativní management Počítač a Simplexová metoda: - simplexová metoda požaduje soustavu rovnic 1. upravíme data tak, aby pouze rovnice, neumí používat nerovnice přídavná proměnná: x1´ 2x1 + x2 + x1´ = 6 2x1 + 2x2 + x2´ = 8 x2´≥ 0 x1´ přídavná proměnná (je to nevyužitá pracovní doba) x1´≥ 0 Z=3x1+2x2 ----z je jak funkce tak proměnná, definuje hodnotu zisku z – 3x1 – 2x2 = 0. x1, x2 jsou strukturní proměnné ze zadání čísla v matici jsou opsané koeficienty z jednotlivých rovnic 2x1 + x2 + x1´ = 6 2x1 + 2x2 + x2´ = 8 z – 3x1 – 2x2 = 0 matice soustavy rovnic a matice rozšířená z X1 X2 X1´ X2´ B 2 1 6 0 1 0 2 2 8 0 0 1 -3 -2 0 1 0 0 charakteristické pro matici je, že na pravé straně jsou všechna čísla nezáporná a má 3 jednotkové sloupce. Kanonický tvar soustavy lineárních rovnic - máme-li 3 rovnice a 3 jednotkové sloupce, pak matice je v kanonickém tvaru. Kanonické tvary nás vedou k vrcholům (obsahují informace o vrcholu). - je-li v kanonickém tvaru, je možné snadno spočítat řešení z 0 0 1

X1´ X2´ Z

-

t X1 2 2 -3

s X2 1 2 -2

X1´ 1 0 0

X2´ 0 1 0

B 6 8 0

x1´= 6 – 2t – s x2´= 8 – 2t – 2s z = 3t + 2s pro každé t a s spočítám řešení. 2 druhy proměnných proměnné základní, které dopočítáváme (x1´, x2´ a z) a proměnné nezákladní, za které dosazujeme za proměnné lze dosadit nuly, pak základní proměnné se rovnají přímo pravým stranám – toto řešení se nazývá základní řešení a týká se vrcholů, protože ty hledáme. - základní řešení (0,0,6,8)z = 0, doplnily jsme za t a s nulu. Našli jsme vrchol (0,0), pokud bychom zvyšovali t, tak jdeme po ose x, pokud bychom zvyšovali parametr s, tak se pohybujeme po ose y. Dosazujeme-li za s i t, tak budu uvnitř. -Simplexová metoda postupuje po hranách, nemá tedy smysl zároveň zvyšovat s i t.

- pokud budu zvyšovat t, tak zisk se zvyšuje o 3 tisíce, v případě zvyšování s se zisk zvyšuje zisk o 2 tisíce. Preferuji ziskovější cestu a tedy zvyšuju t (tedy x1). o x1´= 6-2t ≥ 0 všechny hodnoty musí být nezáporné a snažíme se o x2´= 8-2t ≥ 0 dosadit za t co největší číslo o z´ = 0+3t t≥0 6

EKO210 – Kvantitativní management o 6 – 2t ≥ 0, tedy 6 ≥ 2t a tedy 3 ≥ t. Můžeme tedy při maximálním využití truhláře vyrábět kusů. o dělník: 8 – 2t ≥ 0 tedy 8 ≥ 2t a 4 ≥ t o Za t můžu dosadit maximálně 3, protože musím brát ohled na oba dělníky. V tuto chvíli vyrábíme 3 kusy stolku a žádný druhý výrobek K tomuto vrcholu však zase musím najít kanonický tvar. Nová kanonická soustava, která bude odpovídat vrcholu [3;0] výpočet: Dosazuju za x1, rovnice od sebe odečíbám 2. od první, 3 od první. 2x1 + x2 + x1´ = 6 dělím 2 x1 + 1/2x2 + 1/2x1´ = 3 2x1 + 2x2 + x2´ = 8 x2 + x1´+ x2´ = 2 z – 3x1 – 2x2 = 0 z – 1/2x2 + 3/2x1´= 9 Simplexová tabulka: z X1 X2 X1´ X2´ B 1 1/2 1/2 0 3 X1 0 0 1 1 1 2 X2´ 0 0 -1/2 3/2 0 9 Z 1 - (3;0;0;2)z=9. Zisk je 9, zisk vzrostl, je něco lepšího? - přepíšu z řádek do tvaru z = 9 + ½x2 – 3/2x1´, za tyto základní proměnné můžu dosazovat, pokud za ně dosadím nuly, tak zisk je devět, zisk poroste při dosazování za x2, pokud budu dosazovat za x1´ bude zisk klesat, závěr je, že řešení není optimální. Pokud budu zvyšovat x2, tak zisk poroste a při zvyšování x1, tak zisk bude klesat, proto není optimální. Zjistili jsme bod [3;0] se ziskem devět není optimální a proto budu zvětšovat x2. Pokud je v Z záporné číslo, tak není splněna podmínka optimality. Pokud by byla všechna čísla kladná, tak je splněna podmínka optimality a můžu skončit. - Máme dvojí možnost výběru buď x1 nebo x2´ Z nikdy nevybírám. Budu hledat tu, která se anuluje. z X1 X1´ X2´ B X2 0 1 1/2 0 3 1/2 X1 0 0 -1 1 2 X2´ 1 1 0 3/2 0 9 Z -1/2 o x1 = 3 - 1/2t ≥ 0 neboli 3 ≥ ½ t t ≤6 neboli t ≤ 2 o x2´= 2 – t Platí že t ≤ 2. Pokud za t = 2, tak x1 = 3 – 1 x2´= 1, a tak bude vystupovat, protože v kanonickém tvaru považujeme za základní. Chci aby byl X2 jednotkový. Opět vytvářím nový kanonický tvar. S druhým řádkem není potřeba dělat, protože je v kanonickém tvaru. Kromě x2´, které píšu x2. Pro úpravu používat výstupní (klíčový) řádek, ten, který je červeně. Přičítám (-1/2) druhého řádku k prvnímu. V třetím řádku je (-1/2), tak opět použiju klíčový řádek (2. řádek) a přičtu (1/2) druhého řádku k řádku třetímu nezákl. nezákl z X1 X2 X1´ X2´ B 0 1 1 -1/2 2 0 X1 0 0 -1 1 2 X2 1 1 0 1 ½ 10 Z 0 Dosadím za x1á x2´dosadím nuly, (2,2,0,0) z = 10. Pokud v z řádku jsou jen kladná čísla, tak dané řešení je optimální. z = 10 – x1´- ½ x2´ budu-li měnit některou 7

EKO210 – Kvantitativní management proměnnou, tak se pohybuji po hranách, měním-li obě najednou, tak jdu dovnitř a zisk se snižuje. - Proměnná z byla ve všech tabulkách jednotková. Zisk se vždycky počítá a nikdy se za něj nedosazuje, proto se tento sloupec vynechává. - při hledání klíčového řádku bi – aikt ≥ 0, mohou nastat, že aik ≤ 0 = není třeba řešit o aik > 0 pak bi ≥ aikt, pak bi/aik ≥ t. Stačí tedy spočítat podíl bi/aik, který je horní mezí pro parametr t X1 X2 X1´ X2´ B Bi/aik 1 6 6/2 = 3 X1´ 2 1 0 2 2 8 8/2 = 4 X2´ 0 1 -3 -2 0 Z 0 0 o podíly neděláme, jestliže tam je 0 nebo záporné číslo - Podmínky použití Simplexové metody: o algoritmus lze používat jen na rovnicích, které mají nezápornou pravou stranu (b ≥ 0) a musí být v kanonickém tvaru o krok č. 1: výpočet základního řešení. (seznam základních proměnných rovnají se b, seznam nezákladních proměnných položíme rovné nule, tím dostanu vrchol) + test optima. Tím ověřím optimálnost vrcholu. Je optimální, jestliže všechny koeficienty v z řádku jsou větší nebo rovny 0 (to platí pro maximalizaci) – jestliže splněn, tak výpočet končí jestliže existuje alespoň jeden záporný sloupec v z řádku, tak vyberu tu s největším záporem. o krok č. 2: jak jsem zjistil klíčový řádek? t = minimum bi/aik, ale jen pro aik>0, řádek, který je klíčový – l-tý řádek, tak tato proměnná bude vystupovat z báze pokud aik ≤ 0 pro všechna i, pak neexistuje optimální řešení a je konec, protože nemá smysl hledat jde o případ nekonečnosti (graf s 2 vodorovnými přímkami) – zřejmě chyba modelu o krok č.3: eliminace Gauss (klíčový řádek, který je červený dělím, abych dostal jedničku a upravuji ostatní řádky. červený je jedna) návrat na krok 1 Poznámky: - týká se výsledné tabulky (té poslední) – jde o redukované cenové koeficienty zj. Tyto koeficienty mají i další využití. Pokud je zj ≥ 0 odpovídá nějakému výrobku, který by se neměl vyrábět. Jestliže jsem donucen tento výrobek vyrábět, tak mě stojí zkoeficient, o toto číslo mi sníží zisk. Nedodržím optimální řešení simplexové metody. - x1´ a x2´ jsou nevyužité doby truhláře a dělníka. V případě, že bych zkrátil pracovní dobu truhláře o jednu hodinu, tak x1´ bych o 1 zvýšil a zisk bych si snížil o 1000 a optimální zisk by klesl o 1000. V případě x2´to bude méně o 500 Kč. Platí i opačně, pokud bych přemluvil truhláře nebo dělníka, aby dělal více, tak zisk stoupne. Přídavné proměnné v z se nazývají stínové ceny (shadow, dual price), které oceňují zdroje (pracovní dobu truhláře a dělníka). Není to cena pracovní síly, ale je to marginální změna zisku při změně pracovní síly o jednotku. - Program by neměl cyklovat, protože máme konečný počet vrcholů. Simplexová metoda má vždy optimum po určitém počtu kroků. Výjimkou je degenerace

8


1 10 10/1 -3 5 nepočítáme 5 0 0/5 = 0 = t 5 50 50/5 - t = 0, tedy přírůstek zisku je nulový a pouze se mění báze a zisk se nemění. Protože vybírám řádek s nejmenším podílem. Minimalizace: - sousta lineárních rovnic v kanonickém tvaru (jednotkových sloupců, kolik je rovnic) - pravé strany lineárních rovnic jsou nezáporné - krok 1: o (test optima) – všechna čísla zj ≤ 0, jestliže splněné, tak účelová funkce nabývá svého minima (stejně jako při maximalizaci), pokud existuje zj kladné, tak se vybere to největší zj větší než nula, jde o pokles účelové funkce - krok 2: o hledá se přípustnost řešení (naprosto stejné jako u maximalizace) o bi /aik (hledáme minimum) - krok 3: o klíčový sloupec musí být jednotkových (vše je stejné jako u maximalizace)

Intervaly stability Příklad: (zadání jako v lineárním programování) Výchozí tabulka z X1 X2 2 1 X1´ 0 2 2 X2´ 0 -3 -2 Z 1

X1´ 1 0 0

X2´ 0 1 0

Poslední tabulka X1 1 X1 0 X2 0 Z

X2´ -1/2 1 ½

b 2 2 10

X2 0 1 0

X1´ 1 -1 1

b 6 8 0

opt. (2,2,0,0)=10 intervaly stability pravé strany - jak je řešení citlivé na změny vstupních parametrů (disponibilní pracovní fond) intervaly stability cen – říká, v jakém intervalu se cena může pohybovat aniž se změní řešení intervaly stability pravé strany b b= ( 6 nad 8) bi = (6+t nad 8) - spočítáme to pomocí inverzní matice báze - počítáme to z poslední tabulky a jsou to sloupce x1á x2á řádek x1 a x2 a pravá strana v poslední tabulce b´ b´= B-1 . b = 1 -1/2 6 2 -1 1 8 2

9

EKO210 – Kvantitativní management v případě že by v první tabulce bylo bt = (6+t nad 8), t se nesmí objevit na pravé straně bt´ = B-1 bt = 1 -1/2 6+t 6+t -4 2+t -1 1 8 -6-6 +8 2-t - jestliže přidáme 2 kusy, tak se na druhé straně 2 kusy odeberou - když tam budou i váhy, tak je to 10+t - t = změna rozsahu pracovní doby truhláře, takže pokud jednu hodinu přidá, tak se zisk zvýší o 1000 Kč - 2+t ≥ 0 takže t ≥-2 - 2-t ≥0 takže t ≥ 2 - t je součástí <-2,2> - b1 je součástí <4,8> tabulka stále obsahuje optimální řešení pohybuje-li se pracovní doba truhláře v tomto intervalu, tak jde o optimální řešení b 6 8 0

bt 6 8+t 0

b´ 2 2 10

b´t 2 – 1/2t 2+t 10 + 1/2T

≥0 ≥0

bt´ = B-1 bt = 1 -1/2 6 6 – 4 – 1/2t 2 – 1/2t -1 1 8+t -6 + 8 + t 2+t zisk --- 3(2 – 1/2t) + 2(2 + t) = 6 - 3/2t + 4 + 2t = 10 + 1/2t - 2 – 1/2t ≥ 0 takže t ≤ 4 - 2 + t ≥ 0 takže t ≥ -2 t je součástí <-2, 4> - b2 je součástí <6,12> b2 znamená druhý dělník (nesmíme měnit pracovní dobu prvního dělníka) Intervaly stability cen Příklad: (zadání jako v lineárním programování) Výchozí tabulka z X1 X2 2 1 X1´ 0 2 2 X2´ 0 -3 -2 Z 1 -3+t Poslední tabulka CB X1 X2 X1´ 3+t X1 1 1 0 2 X2 0 -1 1 0 = z1 1 Z 0 z1 z2 z3 opt. (2,2,0,0)=10

X1´ 1 0 0

X2´ 0 1 0

X2´ -1/2 1 ½

b 2 2 10 z4

b 6 8 0

z0

Zkoumáme interval stability první ceny nezávisle na změnách druhé ceny. t se nedostane z levé strany na stranu pravou. t se objeví pouze v z-řádku. Když v z-řádku se objeví záporné číslo, tak řešení přestane být optimální c1 = 3 a my dáme c1 = 3+t c2 = 2 nemění se

zj = CB * aj´ - cj

z3 = (3,2) * (1 nad -1) – 0 = 1

10

EKO210 – Kvantitativní management z1 = (3+t,2) *(1 nad 0) – (3+t) =0 z2 = (3+t,2) *(0 nad 1) – 2 = 0 z3 = (3+t,2) * (1 nad -1) – 0 = 1+ t 0 beru ze zadání, kde c = (3+t,2,0,0) z1 = (3+t,2) *(-1/2 nad 1) – 0 = -3/2 – 1/2t + 2 = ½ - ½t z0 = (3+t)*2 + 2*2 =10 + 2t kontrola nezápornosti z-koeficientů: z1 a z2 jsou nezáporné, ale z3= 1+t a to je nezáporné jen když t ≥ -1, z4 = ½ - 1/2t takže nezáporné jen když t ≤ 1 - výsledný interval je <-1,1> řešení x = (2,2,0,0) takže v dílně se nic neděje, ale zisk se změní o 2t tedy ∆z0 = 2t c1 je v intervalu <2,4>, pokud cena překročí hranice, tak tabulka není optimální Interval stability cen druhého výrobku X1 X2 X1´ 2 1 X1´ 1 2 2 X2´ 0 -3 -2 Z 0 -2+t Poslední tabulka CB X1 X2 X1´ 3 X1 1 0 1 2+t X2 0 1 -1 0 0 1-t Z

X2´ 0 1 0

b 6 8 0

X2´ -1/2 1 ½+t

b 2 2 10+2t

- první výrobek stojí 3*2 = 6000 - druhý výrobek stojí 2(2+t) = 4+2t dohromady 10 + 2t růst je 2t (takže o 2000 na jednotku) - c = (3, 2+t, 0, 0) 1 nad 0 je sloupec X1 - z1 = (3,2+t)(1 nad 0) – 3 = 0 - z2 = (3,2+t)(0 nad 1) – (2+t) = 0 takže t ≤ 1 - z3 = (3,2+t)(1 nad -1) – 0 =3 – 2 – t = 1 – t - z4 = (3,2+t)(-1/2 nad 1) – 0 = -3/2 + 2 + t = ½ + t takže t ≥ -1/2 - platí že t je součástí <-1/2,1> - c2 je součástí <3/2,3> v tomto intervalu se nemění první, třetí a čtvrtá cena a nemění se ani kapacity a pak se cena může pohybovat v tomto intervalu, aby bylo optimum -

jestliže je v optimálním z-řádku z-koeficient rovný nule, tak je i další tabulka optimální a optimálních řešení je nekonečně mnoho. V grafické podobě jde o omezení ve dvou vrcholech a řešením jsou všechny body na přímce mezi těmito vrcholy.

11

EKO210 – Kvantitativní management Příklad: x1 + 4x2 ≤ 12 2x1 + 2x2 ≥ 4 Z = 2x1 + 4x2 – max

x1 + 4x2 + x´1 = 12 2x1 + 2x2 – x´2 = 4 2 – 2x1 – 4x2 = 0

x1,x2 ≥ 0

x´1 ≥0 x´2 ≥0

x´2 je záporné, protože rovnice je ≥ 4

pomocná proměnná X1 X2 X´1 X´2 X´´1 B X´1 1 4 1 0 0 12 12/1 X´´1 2 0 -1 1 4 12/2 2 Z -2 -4 0 0 0 0 Z´´ 0 0 0 0 -1 0 2 2 0 -1 0 4 tady nejde použít simplexová metoda, protože není jednotkový sloupec u X´2, není tedy kanonický tvar. Avšak, můžeme přidat další sloupec v jednotkovém tvaru, ale hrubě jsme porušili zadání. Výchozí základní řešení, které jsme udělali přidáním dalšího sloupce: x= (0,0,12,0,4). Toto řešení není přípustným řešením úvodní úlohy. I pokud by počítač zjistil, že je optimální, tak jej nelze přijmout. Prvním úkolem dvoufázové metody je anulovat proměnnou, kterou jsme přidali. Tuto proměnnou můžeme vyškrtnou pomocí minimalizace x´´1. Stahujeme ji z hodnoty 4 na hodnotu 0. min x´´1 z´´ = x´´1 ---- min. A přidáme do tabulky. Opět ověřujeme podmínky simplexové metody nezápornost pravé strany a jednotkové sloupce, což nejsou, ale přičteme řádek X´´1 k řádku Z´´. Klíčový sloupec je ten, který je v případě minimalizace kladný a pak podíly B/x. Jako klíčový sloupec vybral první sloupec. Klíčový prvek je ten červený.

X´1 X1 Z Z´´

X1 0 1 0 0

X2 3 1 -2 0

X´1 1 0 0 0

X´2 ½ -1/2 -1 0

X´´1 -1/2 ½ 1 -1

B 10 2 4 0

10/3 2/1

12

EKO210 – Kvantitativní management Test optima je splněn, protože jde o minimalizace a tedy hodnoty musí být záporné. Řádek Z´´ se už nezmění, neboť jsme se dostali na množinu přípustných řešení. Největší záporná je ve sloupci X2. Nejmenší poměr je u řádku X1. X1 X2 X´1 X´2 B X´1 -3 0 1 2 4 X1 1 1 0 -1/2 2 Z 2 0 0 -2 8 Toto řešení není optimální, neboť v Z řádku je záporné číslo. Řešení je teď v grafu (0,2) Vystupuje X´1 a vstupuje X´2. Pořád musím být v kanonickém tvaru X1 X2 X´1 X´2 B X´1 -3/2 0 ½ 1 2 X1 ¼ 1 ¼ 0 3 Z -1 0 1 0 12 Hodnota Z opět vzrostla, ale řešení konečné to není, protože v Z-řádku je záporné číslo.

X´1 X1 Z

X1 0 1 0

Příklad: x1 + x2 ≤ 1 x2 ≥ 2 Z = x1 + x2

Řešení: x1 + x2 x´1 ≤ 1 x2 – x´2 ≥ 2 Z - x1 - x2 = 0 X1 X´1 1 X´´1 0 Z -1 Z´´ 0

X2 0 4 4

X´1 2 2 2

max

X´2 1 0 0

B 20 12 24

V tuhle chvíli zde není žádné řešení.

max X2 1 1 -1 0 0

1

X´1 1 0 0 0 0

X´2 0 -1 0 0

X´´1 0 1 0 -1 -1

B 1 2 0 0 0

1/1 2/1 2

Vystupuje x´1.

13


X1 X2 X´1 X´2 X´´1 B X´1 1 1 1 0 0 1 X´´1 -1 0 -1 -1 1 1 Z 0 0 1 0 0 1 Z´´ -1 0 -1 -1 0 1 Z´´ vystoupit stále nemůže, i když má všechny proměnné -1, ale B-sloupec není rovný nule. Test optima však říká, že dál to už nejde. Hodnoty nula není možné dosáhnout, protože zde neexistuje žádné přípustné řešení.

Cílová programování (GOAL prog.) 4x1 + 2x2 ≤ 12 x ≥ 0 x1 + 2x2 ≤ 8 max z = 2x1 + 3x2 x = (1,33; 3,33) z = 12,6 jak, ale dosáhnout zisku 13? Účelová funkce je 12,6 a ta je optimální, ale oni chtějí, aby byla 13. Naše odpověď? S těmito kapacitami není možné dosáhnout zisku 13. Pokud však dojde k uvolnění, pak je možné řešení 13 dosáhnout a tím se zabývá cílové programování. 2x1 + 3x2 ≥ 13 4x1 + 2x2 ≤ 12, jenže já to musím změkčit. 4x1 + 2x2 + d+1 – d-1= 12 d+1 – kolik suroviny ušetřím d-1- kolik suroviny bude potřebovat navíc d+1*d-1 = 0, d+1, d-1≥ 0 x1 + 2x2 + d+2 – d-2= 8 d+2*d-2 = 0 Z = d+1 + d-1 ---Z = 13 x = (1,25; 3,5)

d+2, d-2≥ 0

min d+1= 0 d-1= 0,25

14

EKO210 – Kvantitativní management f*1 = 44 [mil] f2 = 16

Vícekriteriální programování 0 ≤ x1 ≤ 6 0 ≤x2 ≤7 x1 + x2 ≤ 10 f1 = 3x1 + 5x2 --- max f2 = 3x1 + x2 ---- max

39,6

A [3;7]

7 D

[6;4] f1 = 38 f*2 = 22

B 6 3 ks prvního výrobku, 7 ks druhého výrobku f*1 = 44 optimum – f2 = 16

pouze optimazilazce f1 [3;7]( do f2 jsem pouze dosadil – neoptimalizoval jsem f2, ale f1) 2 pokusím se zoptimalizovat f2 ale zadání optim pro obě funkce. Co to je optimální řešení pro více funkcí – nelze porovnat 2 řešení a porovnat je a říct to nejlepší = není tato množina uspořádaná – z tohoto hlediska jeto nesmysl. Ale v praxi má smysl – když ne obě max, tak kompromis aby nebyli extrémně velké a malé hodnoty a 1 řešení bude dominovat c: f1 = 20, f2 = 20 toto řešení je dominováno bodem B (B dominuje C), v obou kritériích je řešení B lepší než v kritériu C (jednou je v B 44 a jednou 22 což je větší než 20). Výsledný bod C bych nikdy neměl předávat,protože je dominován. Pokud bych doporučil dominovaný bod, tak bych doporučoval špatné řešení. K dominovaným kritériím existují lepší řešení. My se bavíme jen o nedominovaných. Nedominované jsou takové, ke kterým neexistuje lepší řešení. 44 je nejlepší možné a pokud budu zvyšovat 16, tak si maximálně můžu v f*1 pohoršit. Nedominované můžeme nahradit slovem dobré řešení. hledáme „dobré kompromisní nedominované řešení“ je mnoho metod např: Metoda vah - simplexova metoda – pouze 1 kritérium – nejjednodušší sečíst, pokud jsou rozdílné parametry: váhy a sumu váha 0,7 f1 = 3x1 + 5x2 --- max váha 0,3 f2 = 3x1 + x2 ---- max - f = 0,7 (3x1 + 5x2) + 0,3(3x1 + x2) = 3x1 + 3,8x2 --- max (to už budu dopočítávat v lingu) Problém je, kde sehnat váhy - metoda přináší funkci, která má již trochu jiné koeficienty a to 3 a 3,8, ale opět končí ve vrcholech jako v předcházejícím obrázku. Metod ústupků - ve výsledku už dává kompromis mezi bodem A a bodem B (první maximalizuje produkt, druhý maximalizuje vývoz). My nechceme maximalizovat, my chceme něco mezi. Jestli chci maximalizovat první, pak nemůžu chtít maximum na druhém... - Nejdříve musíme zjistit, o kolik můžeme klesnou s první účelovou funkcí. On navrhuje 10% ze 44 mil, což je 39,6 mil. Pokles f1 je možný na hodnotu 39,6. Musíme najít všechny přípustné body, které dosahují hranice 39,6, vyjádřím matematicky: o 3x1 + 5x2 ≥ 39,6 15


-

o D = [5,2; 4,8] f1 = 39,6 f2 = 20,9 Maximalizaci převedu na minimalizaci tak, že vezmu(udělám) mínus funkci, jinak je to totéž.

Celočíselné programování problém batohu V1 500 Zisk 4

V2 700 7

V3 300 11

V4 100 8

V5 220 9

≤ 1000 maximal

jsme na aukci, kde auto má nosnost maximálně 1000 kg a nabízejí nám 5 věcí z aukce. U každého výrobku se máme rozhodnout, jestli ho budeme brát. Bude 5 proměnných. x1 může nabývat hodnoty 0 nebo 1. x2 = 0 x 1 x3 = 0 x 1 x4 = 0 x 1 x5 = 0 x 1 Z = 4x1 + 7x2 + 11x3 + 8x4 + 9x5 ---- max - to je účelová funkce. 500x1 + 700x2 + 300x3 + 100x4 + 220x5 ≤ 1000 ..... Omezením je nosnost vozidla Má jen jedno omezení a výběr ano/ne. Když by tam byl odvoz stolků, tak by tam byly podmínky celočíselnosti. V1 4 1 2

V2 2 2 3

1200 800

4x1 + 2x2 ≤1200 x1 + 2x2 ≤ 800 2x1 + 3x2 – max x≥0 dopisuji později: x1 = 100 y1 + 500y2 y1 + y2 ≤ 1 y1;y2 € {0;1} x1,2 ≥ 0 Nyní jde o diskrétní proměnné, protože mohou nabývat jen určité hodnoty. optimální x = (133;333). Představme si, že jsme toto řešení předali, ale řekli nám že to není možné protože x1 může být vyráběn jen v množství 0, 100, 500, tedy x1 € {0; 100; 500} rozhoduje, kolik se budr vyrábět výrobků y1 = 1 (vyrábí se 100 ks V1) x 0 nebude se vyrábět y2 = 1 (vyrábí se 500 ks V1) x 0 nebude se vyrábět na základě proměnných y platí že: x1 = 100y1 + 500y2. Jeho řešení: V1 V2 X1 0 0 0 1 0 100 0 1 500 1 1 Chyba (600 je moc) y1 + y2 ≤ 1

16


Výrobní problém fixní náklady

Z Fix X dolní X horní

V1 4 1 2 500 50 300

V2 2 2 3 1000 30 400

1200 800

Jestliže výrobek V1 nevyrábím, tak se 500 neplatí a pokud vyrábím tak se platí, to platí i pro V2. x dolní je minimální velikost výroby, jestliže se vyrábí x1, x2 znamená, kolik ks se vyrábí 4x1 + 2x2 ≤1200 x1 + 2x2 ≤ 800 z = 2x1 + 3x2 – 500y1 – 1000y2 y1 = 1 (jestliže se vyrábí V1) nebo 0 (pokud se V1 nevyrábí) y2 = 1 (jestliže se vyrábí V2) nebo 0 (pokud se V2 nevyrábí) x≥0 x1 > 0 pak y1 = 1 x1 = 0 pak y1 = 0 x2 > 0 pak y2 = 1 x2 = 0 pak y2 = 0 50y1 ≤ x1 ≤ 300y1 30y2 ≤ x2 ≤ 400y2

Bin packing problem V1 V2 V3 Váha 50 86 63 Kusů 65 68 150 Y = 8000 kg. Jde o to, kolik jízd se má provést (kolikrát se auto bude točit), aby jízd bylo co nejméně. Jak to naložit. xij ≥ 0 počed ks Vi, které naložíme do vozidla (kontejneru) kj ∑x1j = 65 počet kusů které se dají do prvního vozidla a odvézt musím 65 kusů. ∑x2j = 68 počet kusů které se dají do druhého vozidla a odvézt musím 68 kusů. ∑x3j = 150 počet kusů které se dají do třetího vozidla a odvézt musím 150 kusů. Tohle mi zajistí, že budou odvezeny všechny výrobky. Ten plán však může být nepřijatelný a proto musím bilancovat vozidla. 1. kontejner: 50x11 + 86x21 + 63x31 ≤ 8000 y1 1. výrobek do 1. kont., 2. v do 1. kont. 2. kontejner: 50x12 + 86x22 + 63x32 ≤ 8000 y2 j-tý kontejner: 50x1j + 86x2j + 63x3j ≤ 8000yj j = 1,2...m (kde m je max. počet jízd) Není účelová funkce – zatím dá plán rozvozu, potřebujeme však minimalizovat počet vozidel. opět proměnné y1 = 1 x 0, y2 = 1 x 0, ym = 1 x 0; ∑yi ---- min = y1 + y2 + ... + ym Simplexovou metodu zatím nelze použít, protože tyto příklady nejsou celočíselné. řešení:

17


Branch and Band method – metoda větvení a hranic jde o dělení jednotlivých řešení, na stále menší a menší části a výběr toho nejlepšího 3x1 + 2x2 ≤ 1 x1 + 2x2 ≤ 7 x je celé z = 2x1 + 3x2 ---- max tahle metoda se snaží ten páse mezi 2 a 3 vymazat. Bude se mi dělat strom x2 položím ≤ 2 x2 ≥ 3

[3;2,5]

x2

[2,3;2]

[3,1] Mám množinu řešení a hledám optimum [2;2,5]. Celý pás od 2 do 3 vynechávám. Teď spodní 4úhelník. z – 2x1 + 3x2 ---- max 3x1 + 2x2 ≤11 x1 + 2x2 ≤ 7 x≥0 x2 ≤ 2 x2 ≥ 3 Opět vzniknou 1 čtyřúhelník a 1 trojúhelník optimum je [2,3;2] z = 10,6. Protože není celočíselné tak pás mezi 2 a 3 vynecháme x1 ≤ 2

7

x= (2,2) z = 10 Nemůžu ukončit práci, protože je tu možnost ještě na lepší řešení, teď malý trojúhelníček v pravo. pro x ≥ 3 [3,1]z=9 toto řešení je nejlepší, které simplexová metoda našla. Toto řešení mě nezajímá. Teď se přesunuji na ten malý3-úhelník nahoře. z – 2x1 + 3x2 ---- max 3x1 + 2x2 ≤11 x1 + 2x2 ≤ 7 x≥0 x2 ≥ 3 řešením je: [1,3] z = 11. Teď škrtám původní řešení, protože toto je lepší. Teď už končím protože nemám co řešit.

18

EKO210 – Kvantitativní management Přiklad: 4x1 + 2x2 ≤ 9 x1 + 2x2 ≤ 7 x1,2 ≥ 0 a celé z = 2x1 + 3x2 ---- max

[0,6;3,1]z=10,8 [1;2,5]z=9,5

Jako první věc se spouští simplexový mechanismus Celečíselné ptimum bude mí z menší než 10,8, v některém z možných bodů (metoda větvení a hranic (hranice je ta horní mez) 1) není celočíselné optimum – provedeme dělení podle větve (0,6 = 1 nebo 0), jedno podle které proměnné provedeme větvení – větvící proměnná; pás mezi (0;1) vynecháme z větvení, oželíme, protože nejsou celočíselné z=10,8[0,6;3,1] optim řeš ze simplexu x1≤0 (lze x1=0) x1≥1 z = 9,5 4x1 + 2x2 ≤9 [1;2,5] z = 9,5 x1+2x2≤7 x1x2 ≥ 0 celé x1 ≤ 2 x2 ≥ 3 z=2x1 + 3x2 ---max [1,25;2] prázdné řešení x1=0 z=8,5 (horní mez) – proto nemusím simplex řeše: [0;3,5] neceločíselné, hledat ani počítat, protože řešení opět větvím jsou pod úrovní 9 z druhého sloupce, které už máme x2 ≤ 3 x2 ≥ 4 [0;3] prázdné řešení z=9

19


Metoda B and B – algoritmus: 1.

2. 3. 4.

pracuje s množinou neprozkoumaných větví – na začátku obsahuje jen jedinou větev a to zadání úlohy z* = průběžné nejlepší řešení účelové funkce a příslušná hodnota bude x* výběr neprozkoumané větve o řešíme standardně simplexovou metodou a) větev nemá řešení – pak se vracím zpět na jedničku a větev smažu z množiny neprozkoumaných větví, abych ji nedělal znovu. Metoda končí, když prozkoumám všechny větve a nic nenajdu b) optimální řešení x0 a z0 je-li z0 ≤ z* - znovu se vracím na jedničku je-li x0 celočíselné – pak za x* dosadím x0 a za z* dosadím z0 není –li x0 celočíselné – větvíme – vytvoříme další 2 větve, které přidáme do množiny neprozkoumaných řešení a) volba celočíselné proměnné x0k která není celá větev 1: xk ≤ [x0k] větev 2: xk ≥ [xk0]+1 obě větve – množině neprozkoumané větve – jde se na jedničku, končíme až prozkoumáme všechny větve

n-člených binárních vektorů je 2n – a to je maximální počet řešení, které budeme muset řešit – tedy 2n modelů (úloh lineárního programování) – když je to bez podmínky celočíselnosti, tak se říší jen jeden model.

Výpočetní složitosti -

popisuje nebezpečí metody větvení a hranic zabývá se dobou, která uplyne od počátku do konce algoritmu. – počítá se horní odhad v závislosti na rozsahu úlohy (např. počet celočíselných proměnných n) n je rozsah modelu, u matice je to počet řádků a sloupců výpočetní složitosti je funkce f(n), která představuje řád horní meze výpočtu – tuto funkci počet kroků nepřekročí rozeznáváme algoritmy lineární (násobek daného počtu prvků – horní hranice je n) logaritmus n – n log n – řazení pole podle velikosti nějakého klíče (quick sort) n2 – buble sort polynomiální n3 – inverze matice inverze operací říkají jak roste náš algoritmus až 2n exponenciální

Příklad: doba operace 1 mikrosekunda: 20operaci n 20 n log n 86 mikrosek 2 n 0,4 milisek n3 8 milisek

40 40 0,3 mili sek 1,6 mili sek 64 mili sek

100 100 0,4 mili. sek 10 mili sek 1 sek

2n

11 dní

36 000 let

1 sekunda

1000 1s 10 sek 20 sek 17 minut

20

EKO210 – Kvantitativní management teorie se zabývá fungováním rychlosti algoritmů suboptimální řešení – po určitém čase či počtu kroků řešení zastavím a předám jen tyto částečná řešení – optim. řešení většinou hned na začátku a pak už jen ověřování, že tomu tak je LINGO: model: MAX= 2*x1 + 3*x2; 4*x1 + 2*x2 <= 9; x1 + 2*x2 <=7; @GIN(x1); @GIN(x2); end SETS – zabývá se poli a to jedno a více rozměrnými (popis matic) SETS: DOD/1..4/: A; dodavatelé a jsou 4 složky A(1), A(2), A(3), A(4) ODB/1..5/: B; odběratelé a je vyhrazeno 5 míst B(1), B(2),...,B(5) MAT(DOD,ODB):X,C; matic z dodavatelů a odběratelů (řádky, sloupce) X(1,1), X(1,2) ENDSETS; C je další matice DATA: A=100,50,40,70; dosadí za A konstanty B=20,40,80,100,60; C=68415 (4 řádky a 5 sloupců ... ; ENDDATA; 1. řádek ∑ i

∑c

i, j

xi , j − −− > min

xij ≥ 0

j

2. řádek ∑ xij ≤ Ai − − pro − všechna − i j

3. řádek ∑ xij = B j − − pro − všechna − j i

Model v lingu: MIN= C(1,1) * X(1,1) + C(1,2)*X(1,2)... nebo jednodušší varianta: MIN=@SUM(MAT: C*X); toto je účelová funkce, první řádek výše @FOR(DOD(I) : @SUM(ODB(J):X(I,J)) <= A(I);); 2. řádek @FOR(ODB(J) : @SUM(DOD(I):X(I,J)) <= B(J);); 3. řádek STATOS WINDOW – průběžný výpis informací, k čemu zatím došel, jaké je zatím nejlepší řešení, hodnota účelové funkce nejlepšího základního řešení, odhad účelové funkce nejlepšího základního řešení REPORT WINDOW – jsou tu i redukované ceny, (proměnné (omezení, duální hodnoty (duální ceny) ILP – integer linear model

21

EKO210 – Kvantitativní management NLP – non linear model OPTIONS: - nastavování parametrů: TOL integrality |10 - X|≤ 10-6 tak OK – to je v toleranci – lze nastavit

Grafy (teorie grafů): V= {1,2,...,n} – množina grafů, je to množina, která je konečná H € VxV – podmnožina kartézského součinu - jde o kolečka s čísly, umístění na papíře je libovolné - druhý grafický prvek je dvojice a to tak, že kolečka s čísly spojíme například úsečkami ve dvojice

V = {1,2,3,4} H = {(1,2);(1,5);(1,4);(3,4)} grafy orientované (di graf – každá hrana má svou orientaci) grafy neorientované Problémy, které se prostřednictvím algoritmů vytvořenými pro grafy řeší graf je úplný, pokud všechny dvojice, které existují jsou spojeny cesta grafu je cesta z jednoho bodu do jiného ceta z 1 do 5 je cesta z 1 do 2 a z 2 do 5 uzavřená cesta = cyklu, jde o posloupnost hran, které na sebe navazují a první začíná tam, kde poslední končí cyklus hamiltonův – prochází všechny uzly právě jednou eulerův – obsahuje všechny hrany právě jednou, začíná, kde končí (nekonečná smyčka) graf - souvislý – z každého uzlu se dostanu po hranách do každého uzlu graf – nesouvislý – například 1 graf, který má 2 oddělené části strom – graf, který je souvislý a neobsahuje žádný cyklus

CPM – Critical path method

CPM/PERT

Analýza projektů – projekt se nejdříve namodeluje a pak teprve počítá graf obsahuje určité milníky (splněné etapy) a hrany, mohou tam být názvy činností (abychom věděli o co jde) Analýza projektu, který má zajistit závod, kde bude administrativní budova a tovární hala. K tomuto závodu povede železniční vlečka. Tento projekt někdo namaloval a tím vytvořil síťový graf.

22


Obsahuje 9 milníků – 1. milník všechny plány schváleny a může se začít kopat a 9 milník, znamená zahájení výroby. Každý milník znamená ukončení činností, které do něj směřují (prohlásím za hotovou, pokud jsou všechny činnosti ukončeny) Není možné, aby začal další milník, pokud není ukončen předcházející (milníky, které do něj vstupují - jsou na sobě závislé). Z počátku může jít i více samostatných větví. Mohou být i fiktivní uzly, které zajistí že se 2 nezávislé větve v určitém místě setkají. (nelze instalovat technologii, pokud není hotová vlečka) Časová analýzy (síťový graf) - analýza toho, kdy mají jednotlivé firmy na jednotlivé části práce nastoupit a vykonávat je - dělá se buď ručně nebo tabulkově 3 1 0

3 0

8

17

2 3

6 20

21

3 8

10

CPM – skládá se ze 2 etap 1. etapa - do uzlu číslo 1 dosadím nulu (připravena k termínu nula pro přípravu realizace) Nejdříve skončí v termínu 3. Pak to postupně přičítám. Jestliže se u některých sbíhají různé větve, tak se bere ta pozdější doba zahájení, aby byly připraveny obě dvě a ne třeba jen jedna. T= XXX, = nejbližší možný termín, kdy se bude moc při nejlepším možném případě začít vyrábět 2. etapa – horní hranice (kdy nejpozději). Nejzazší termíny jsou v pravo. V příkladě vyšlo optimálně za 23, my si nastavíme, že chceme, aby to bylo nejdéle za 23 a to z důvodu, abych začal co nejdříve splácet dluhy. Časové rezervy – případě, kdy se sbíhají jednotlivé uzly a jsou zde různé doby dokončení. Nekritická činnost – jsou zde rezervy pro dokončení U kritických činností se kreslí dvojitá čára nebo barevná (je zde nulová nebo minimální rezerva) Odečítám od opti málního času následujícího milníku dobu trvání předcházejícího (jdu zpětně) a rozdíl levé strany a čísla na čáře nám dá rezervu Řešení tabulkově na počítači. - každý řádek tabulky představuje jednu čáru v grafu

23

EKO210 – Kvantitativní management správný graf by neměl obsahovat cyklus (síťový graf je acyklický), měl by mít jeden začátek a jeden konec. Začátek je uzel, do kterého nevede žádná hrana. 1 není v druhém sloupci a 9 není v prvním sloupci (takže 9 je poslední) dvojka je pouze v pravé straně a proto ji mohu Ti0 Ti0+tj Tj1-tij Tj1 rezerva i, j tij řešit. Do pětky vede jen jedna činnost a proto ji 1,2 3 0 3 0 3 C teď řeším 1,3 8 0 8 2 10 2 2,5 12 3 15 3 15 C Jako poslední bude 9. uzel, který ze všech 2,6 17 3 20 4 21 1 devítek vyberu ten s největším číslem a to je 3,4 10 8 18 10 20 2 naším řešením. 4,8 0 18 18 20 20 2 4,9 1 18 19 22 23 4 C = kritická činnost 5,7 3 15 18 15 18 C 6,9 2 20 22 21 23 1 7,8 2 18 20 18 20 C 8,9 3 20 23 20 23 C Rezervy: -

5

2 13

j

16

22

24

Ti1 Ti0

Tj0

Tj1

RVij = 4

RCij = 6 13

16

RNij = 1

22

24

RZij = 3 RV = volná rezerva RN = nezávislá rezerva RZ = rezerva závislá horní část je optimální spodní část jsou nejpozdější doby nastoupení RCij = Tj1 – (Ti0 + tij) RVij = Tj0 –(Ti0 + tij) RZij = Tj1 – (Tj1 + tij) RNij = Tj0 –(Ti1 + tij)

24


Zkracování kritické cesty

4-5

2

3-5

T=10

5

1

4

0

10

1-2, 400 tis 4-6 100tis

3

2, nelze zkrátit

7

Pokud chci zkrátit projekt, tak se musím dohodnout s dodavateli, zdali to půjde, ale to zřejmě bude spojeno s vyššími náklady (více pracovníků, mimořádné změny. Například u činnosti 1 je možné zkrátit z 5 na 3 měsíce a to bude stát o 200 tis. víc. Zkrácení činnosti 2-4 lze o 1 měsíc a stát to bude 300 tis. Činnost 3-4 nelze zkrátit z technologických důvodů. Cílem je zkrátit T=8, ale půjde to. Při zkracování si musíme všímat kritické cesty a tu po nejmenších možných dobách zkracovat. V našem případě zkracování po měsících. Zkracovat postupně. Nejdříve jednu činnost a uvidí se, co to udělá. Nejdříve zkrátíme činnost 1-2, protože je nejlevnější. 5 2 4 T=9 4 4 1 9 0 2 6

3

2

6 Kritická cesta zůstala, ale doba se zkrátila na 9. Celková doba je součet dob trvání na kritické cestě. Náklady jsou o 200 000 vyšší, protože jsme zkrátily činnost 1-2. Další zkrácení se provede stejným algoritmem, protože opět činnost 1-2 je levnější než činnost 2-4, které jsou obě na kritické cestě. Činnost 1-2 teď zkracujeme na 3 měsíce a zaplatíme proto dalších 200 tis. navíc, což znamená celkem už 400 tisíc 5

2

3 3

1

4

0

8

2 6

3

T=8 N=400

2

6 25


Cíl jsme splnily,protože jsme zkrátili původní dobu 10 měsíců na 8 měsíců. Celkové řešení však stojí o 400 tisíc více

Metoda Pert -

je to zobecnění a rozšíření metody CPM. Počítá s tím, že předem nevíme přesně doby trvání činností

-

u každé činnosti by mělo být doba trvání, ale zde tomu tak není a my se ho dozvíme až ve chvíli, kdy se uskuteční. Má beta rozdělení doby trvání činnosti mezi uzlem i a j. Má nejmenší a největší možnou hodnotu, nejmenší číslo je optimistický odhad. Pesimistický odhad je trvání za nejhorších podmínek. Největší pravděpodobnost má modální hodnota. My chceme tyto tři údaje od dodavatele.

-

t0ij

tmij

tpij

Střední hodnota tij = (t0ij + 4*tmij + tpij) / 6 rozptyl - σ2ij = ((tpij – t0ij)/6)2 = ((3-1)/6)2 = (2/6)2 = 1/9 Metoda Pert počítá celkovou dobu trvání, jenže tu nelze takže počítáme střední hodnotu a rozptyl. Střední hodnotu trvání činností spočítáme prostřednictvím metody CPM. Teď bereme čísla před závorkou a spočítáme celkovou dobu (čísla před závorkou je střední hodnota z čísel nad čárou). Celková doba má normální gaussovo rozdělení.

26


T=39

T90

Na celkovou dobu má vliv jen kritická činnost. Nekritické činnosti mají rezervy a proto kritickou dobu neovlivní neboť výkyvy se pokryjí rezervou. Celková doba je ovlivňována jen kritickými činnostmi, její střední hodnotou a směrodatnou odchylkou. σ2T = σ213 + σ235 + σ256 = 100/9 + 16/9 + 16/9 = 132/9 = 14,6 = cca 4 Střední hodnota je 39 měsíců a směrodatná odchylka je 4 měsíce T = N(39;4) Jaká je však pravděpodobnost, že celková doba T za 39 měsíců vskutku bude? Pravděpodobnost je plocha pod 39 na grafu. Pravděpodobnost je 50%. P(T≤39)=0,5. T90 = chci to s pravděpodobností 90%. Používá se normované normální rozdělení. Podle tabulek T90 = 1,3. (T-T´)/σT = Z T90 = Z90 * 4 + 39 T90 = 39 + 4*1,3 T90 = 44,2 (T90 – 39) / 4 = Z90 = 1,3. Chci to mít hotové za 43 měsíců. Jaká je pravděpodobnost, že to do 43 měsíců stihnu? P(T≤43) = P((T-T´) / σT ≤ (43 – T´) / σ) = P ( Z ≤ (43-39) / 4) = 0,84. Termín do 43 měsíců splním s pravděpodobností 84%. Nákladová analýza z časové analýzy odvodí, kolik potřebuji peněz v jednotlivých rocích (měsících...). Je to součet všech nákladů, které se provádějí podle časové analýzy v daném časovém období. Některé jsou schopné podle limitů finanční prostředků stanovit časovou analýzu. Grafy typu MPM - uzlově definovaný graf - my jsme dělali hranově orientovaný graf, kde hrana představovala činnost a v tomto typu je činností uzel

27


stavba adm. budovy Zemní práce, trvají 3 měsíce

0

Začátek

stavba haly

terénní. úpravy

Konec

hrany představují logické a časové vazby. Vazba může mít časové ohodnocení, které říká, kdy se může začít další práce. Když je nula, tak se může začít hned. Když je kladná, tak říká, jak dlouho se musí čekat, než započnou další práce v dalším čtverečku. Pokud je záporná, tak říká, že určitý čas před ukončením se může začít už další činnost

Neorientované grafy -

grafy na modelování sítí (komunikační, silniční, teplovodní...) P5: hrany = silnice – ohodnocení v km uzly = města – model mapy

Hledáme nejkratší cestu z Kralup do Vraného. Metoda hledání nejkratší cesty z grafu. Není rozhodující kudy jedeme, ale rozhoduje, kolik kilometrů najedeme. Řeší se to tabulkou, která má stejný počet sloupců jako je uzlů v grafu. Nejkratší 0 4 16 8 18 25 17 1 2 3 4 5 6 7 cesta 1 (16) 1 (8) 3 (7) 5 (7) 2 (13) 2 (4 km) 1 (4) 2 (12) 4 (10) 7 (15) 4 (10) 3 (16km) 4 (12km) 4 (12) 5 (7) 3 (12) 5 (10) 4 (8 km) 7 (13) 6 (7) 7 (10) 6 (15) 5 (10) 7 (10) 27 číslo platí pro 23 18 32 5. uzel

28

EKO210 – Kvantitativní management V celém výpočtu hrají vliv 2 množiny. Množina uzlů kam znám cestu a množina uzlu z kterých cestu neznám. Nejkratší cesta je z bodu 1 do bodu 1. Druhou množinu tvoří zbylá čísla. Nejdříve vyškrtám všechny cesty do jedničky, protože tam jistě nepojedu, když tam jsem. Následuje cesta do dvojky. Tvrdí, že do dvojky se nedostane kratší cestou než 4 km. Do 2 uzlů umím cestovat optimálně. Z uzlu 1 do uzlu 1 vzdálenost 0 km. Z uzlu jedna do uzlu 2 se vzdáleností 4 km. Všechny ostatní dvojky vyškrtám, protože to jsou delší cesty. Z těchto 2 míst se posouvám do uzlu 4 a nejmenší vzdálenost je 8(km). Jako první jsem jel do Velvar, pak do Veltrus a teď jedu do Slaného (což je číslo 3). Z trojky je možné jet třeby do 5 a to je 16 km, které mám z jedničky a přičtu 7 km, které jsou do pětky. Vždycky vybírám ty nejkratší činnosti Hlavní cíl byl dostat se do vraného. Nás zajímají hrany (tučné a kurzívou) a ta je nejkratší, což je hrana končící v 6 a před ní předchází uzel 5. Najdeme kde je v rámečku pětka a vezmeme kilometry a jí předchází nějaký uzel a ten znovu budu hledat 1 --- 8 km ---- 4 ---- 10 km ---- 5 ----- 7 km ---- 6 N0 –nejkratší cesta z výchozího bodu N1 – ostatní uzly Algoritmus: - N1 prázdná ---- konec - na množinu N0 : sečteme ohodnocené Vj (číslo nad sloupcem) + délky hran příslušných sloupců - Vybereme minimum – a ta která je nejmenší tu dáme do rámečku (tučný) Pozn: Sčítám postupně horní číslo s každým spodním a ten součet, který je nejmenší se dá do rámečku. Tahle cesta vede do nějakého čísla např. 1 a jedničky tedy ve všech jiných umístěních vyškrtám. Znovu se jde na bod 2 a opakuje se takhle dokola. Výsledkem je matice délky nejkratších cest, kterou se dostanu z bodu A do cílového bodu. Forma tabulky.

Rozmisťovací problém – umístění skladu Příklad: Mám 7 závodů a v jednom z nich chci umístit sklad, ten může být v kterémkoliv z těchto závodů. Podmínkou je že bude uvnitř jednoho ze závodů.Úkolem je z těchto sedmi variant vybrat tu lepší. Hledáme místo pro umístění skladu. Kritérium: jediné kritérium, aby byl sklad blízko Kralupy Kralupy 0 Veltrusy 4 16 Slaný Velvary 8 Zlonice 18 25 Vraný 17 Bříza XXXX

Veltrusy 4 0 20 12 22 28 13 6

Slaný 16 20 0 12 7 14 17 5

Velvary 8 12 12 0 10 17 10 7

Zlonice 18 22 7 10 0 7 10 5

Vraný 25 28 14 17 7 0 15 4

Bříza 17 13 17 10 10 15 0 3

suma 80 99 86 69 74 106 82 30

MAX 25 28 20 17 22 28 17

29

EKO210 – Kvantitativní management V = 15 Medián grafů minimalizuje součet vzdáleností do všech ostatních uzlů. Matice nejkratších vzdáleností. Součet v řádku, který je minimální je nejlepší. Vážený medián – tam kde pojedeme dvakrát, tak sloupec násobíme dvěma atd. Provozovny, kde se jede vícekrát, vynásobíme a pak se opět sečtou data v řádku a najde se minimum. Pokud uvolníme předpoklad, že sklad musí být v uzlu, pak řešení je nekonečně mnoho. Bylo dokázáno, že na hranách neleží žádné lepší řešení. Dvoumedián – firma je bohatá a může si dovolit dva sklady. Pak je zbytečné aby všichni jezdily do jednoho skladu, ale rozdělíme je tak, aby jezdily do jednoho z dvou skladů, mohou si vybrat. Možností je celkem 7 nad dvěma Příklad: Zadání stejné jako u předchozího příkladu. Kralupy Veltrusy Slaný Velvary 4 16 8 Kralupy 0 0 20 12 Veltrusy 4 16 20 0 12 Slaný 12 12 0 Velvary 8 22 7 10 Zlonice 18 25 28 14 17 Vraný 17 13 17 10 Bříza XXXX 6 5 7 Řešení: Počet řešení je 7 nad 2. 1 2 Kralupy Veltrusy 0 0 (1,2) 0 4 (1,3) (1,4) 0 4 (1,5) ... ... (6,7)

Zlonice 18 22 7 10 0 7 10 5

Vraný 25 28 14 17 7 0 15 4

Bříza 17 13 17 10 10 15 0 3

3 Slaný 16 0

4 Velvary 8 8

5 Zlonice 18 7

6 Vraný 25 14

7 Bříza 13 17

7

8

0

7

10

suma 80 99 86 69 74 106 82 30

suma 80 50 43 36 48 54 50

MAX 25 28 20 17 22 28 17

MAX

Počítám nejkratší vzdálenosti do dvojskladu. Vzdálenost do jedničky je nula, protože jednička jezdí z jedničky do jedničky. V dvojce je nula, protože dvojka jezdí do dvojky. Trojka jezdí do Kralup (jedničky), která je blíž než Veltrusy. Pokud se jezdí z některého skladu vícekrát, tak ten sloupec násobím příslušným počtem jízd.

30


Centr graf nejde o sklad, ale například o nemocnici, hasiče... Nevíme, kolikrát se pojede. Dopravní náklady zde nerozhodují, protože jde o životy, majetek... Mám 7 vesnic tak, jak je v grafu. Na penězích nezáleží. Jde pouze o to, aby všichni měli záchranku blízko. Mám 7 variant. Kralupy Veltrusy Slaný Velvary Zlonice Vraný Bříza MAX 4 16 8 18 25 17 25 Kralupy 0 0 20 12 22 28 13 28 Veltrusy 4 16 20 0 12 7 14 17 20 Slaný Velvary 8 12 12 0 10 17 10 17 22 7 10 0 7 10 22 Zlonice 18 25 28 14 17 7 0 15 28 Vraný Bříza 17 13 17 10 10 15 0 17

Maximální rádius je 25 kilometrů u varianty Kralupy. Dojezdová vzdálenost je právě rozhodující kritérium Varianta Veltrusy – dojezdová vzdálenost je maximálně 28 kilometrů. Vybírám variantu Velvary a Břízu. Z těchto můžu dalším výběrem vybrat konkrétní město. Volný (absolutní) centr, který je na hranici a může dát lepší výsledek. Špatně se řeší, protože na hraně může být nekonečně mnoho bodů. Může být tedy lepší než prostý centr graf. Vícecentr - Počítá se stejně jako medián, ale narozdíl od něj nesčítáme, ale v řádku hledáme maximum. Příklad: Cílem položit kabely z každého uzlu do každého. Nejde ze každého do každého, protože nemáme tolik peněz. Cílem propojit všechny uzly, aby se každý účastník domluvil s každým účastníkem, ale aby byl počet kabelů minimální – jde o MINIMÁLNÍ KOSTRU GRAFU. MINIMÁLNÍ KOSTRA GRAFU Postupně do grafu propojuji uzly s nejkratšími vzdálenostmi. OBRÁZEK: Celkový počet hran je 46 kilometrů a on tvrdí, že graf je souvislý – tedy z každého uzlu existuje propojení do každého uzlu. Otázkou je, jestli je řešení nejlepší. Tento postup dává optimální řešení.

31


Úloha obchodního cestujícího Přklad: Máme sklad, který je v Kralupech. Z tohoto skaldu vyjíždí dodávka, která má objet všechny města a má se vrátit zpět. V každém městě má být právě jednou a najetý počet kilometrů má být minimální. Řešením je pořadí navštívených měst. Opět vycházím z matice Kralupy Veltrusy Slaný Velvary Zlonice Vraný Bříza suma MAX 4 16 8 18 25 17 80 25 Kralupy 0 0 20 12 22 28 13 99 28 Veltrusy 4 16 20 0 12 7 14 17 86 20 Slaný 12 12 0 10 17 10 69 17 Velvary 8 22 7 10 0 7 10 74 22 Zlonice 18 25 28 14 17 7 0 15 106 28 Vraný 17 13 17 10 10 15 0 82 17 Bříza XXXX 6 5 7 5 4 3 30 Matematický model a hledám optimální řešení: - nejdříve naplánujeme proměnné, budeme značit písmenem Xij. Nejde ani o km či kg, ale jde o rozhodnutí a proto mají hodnotu 1 nebo 0 a znamenají, zdali do daného uzlu pojedu či nepojedu. Jednička znamená že jedu z uzlu i do uzlu j. Průjezdy uzlů neberu v úvahu. Matice se značí C a C = {cij} vzdálenost kilometrů. Skutečně najeté kilometr lze vyjádřit: ∑∑cijxij ---- min. Pro i ≠ j nemá smysl řešit - Musíme zajistit, že se do každého uzlu pojede a že se z každého uzlu pojede. - Řádky znamenají odkud jedu a sloupec kam jedu. Jedu z 1 do 3. 1 2 3 1 1 - ∑xij = 1,pro všechny i = 1,2,...,n, - dělá se i součet ve sloupci ∑xij = 1,pro všechny j = 1,2,...,n Matice: 1 2 3 4 5

1 X 0 0 0 0

2 1 X 0 0 0

3 0 1 X 0 0

4 0 0 0 X 1

5 0 0 0 1 X

Jsou zde particální cykly a proto toto řešení nelze přijmout, protože to není nejlepší řešení. Naším cílem, aby nebyly cykly a k tomu slouží Smyčkové podmínky, které nepropustí toto řešení. Podmínek je tolik, kolik je hran. Pro každou hranu vytvářím smyčku ve tvaru: ui + 1 – n(1- xij) ≤ uj, i,j = 2,...,n, i ≠ j. Tato podmínky je vytvořena pro každou hranu. Jedeme z uzlu i do uzlu j. Pak má podmínka tvar ui + 1 ≤ uj.----- ui + 1 – n ≤ uj. Podmínka platí vždy, protože n je dostatečně velké. Jde u Tuckerovy smyčky.

32

EKO210 – Kvantitativní management Tuckerova podmínka pro hranu 4, 5 je to u4 + 1 ≤ u5. Tento cyklus neprojde pře pro hranu 5, 4 je to u5 + 1 ≤ u4. podmínku, protože nenajdu žádná dvě stejná čísla, která by to splnily. pro 30 uzlů to je 1032 možností. Pokud n bude dost vysoké, tak dostaneme obrovský model (velké množství rovnic a proměnných), výpočet pak může trvat velmi dlouhou dobu. Model je vhodný pro malé množství n.

Metody heuristického algoritmu představují výpočetní postup o kterém nikdo nedokázal, že je optimální. Je to náhražka. Nejde o matematicky optimalizační řešení.

Metoda nejbližšího souseda

Výjezd z Kralup a jedu tam, kam je to nejblíže, tedy do Veltrus. Sloupce, kde už jsem byl znovu vyškrtám. Z Veltrus opět hledám nejbližší místo, které je Velvary. Z Velvar je to nejblíže do Zlonic a ze Zlonic jedu do Slaného. Ze Slanéhé do Vraného (který je 14 km) a z Vraného jedu do Břízi a odtud se ještě vracím do jedničky. 1 --- 4 --- 2 --- 12 --- 4 --- 10 --- 5 --- 7 ---- 3 --- 14 --- 6 --- 15 --- 7a zpět do jedničky 17 km Celkem je délka 79, L=79 Savings Algorithm – Výhodnostní čísla – pořád patří k obchodnímu cestujícímu - příklady, kdy 2 města spojím mezi sebou a budu je procházet tímto způsobem - výhodnostní propojení měst

i

1

j Sij = 2C1i + 2C1j – (C1i + Cij + C1j) = C1i + C1j - Cij S34 = C13 – C34 + C14 = 16 – 12 + 8 = 24 – 12 = 12

33

EKO210 – Kvantitativní management 2 x 0 4 4 4 8

2 3 4 5 6 7

3 0 x 12 27 27 16

4 4 12 x 16 16 15

5 4 27 16 x 36 25

6 4 27 16 36 x 27

7 8 16 15 25 27 x

Nejdůležitější je propojit měst 5 a 6, protože zde je největší číslo. Začínáme zprostředka, propojíme město 5 a 5 což je 7 km, tímto se vyškrtne řádek 5 a sloupec 6, protože sem už nepojedu. Ze zbytku zas vybírám největší číslo. Další je číslo 27, čímž budu propojovat 3 s 5. Kilometrů to je 7. 3 ---- 7 ---- 5 --- 7 ---- 6 ---- 15 ---- 7 ----- 10 ---- 4 ----12 ---- 2 ---- a přes jedničku zpět do 3

Insert Algoritmus -

jedu do nejvzdálenějšího čísla od jedničky

1 ---- 25 --- 6 ---- 25--- 1 ---- to je první minitrasa, která měří 50 km pokus č. 1 – vezmu hranu z 1 do 6 a zkusím z ní odbočit do jednotlivých směrů 1-6 2 (1-2)=4 (2-6)=28 – (1-6) =25 == 7 3 4 5 6

(1-3) (3,6) – (1,6) == 5 (1-4)(4,6) – (1,6) == 0 == 0 == 7

další minitrasa je 1 --- 8---4 ---- 17 ---6 --- 25---1. Délka L=50km.Šestku jsem zrušil a místo ní je hrana 4,6, ale tato trasa ještě neobsahuje všechny uzly a proto totéž budu opakovat dál. další hrana je 1---8 ---4---10----5 ---7---6---25 ---1 na každou hranu vždycky vkládám zbývající uzly a ono to nějak vyjde. Další pokračování je: 1---8 ---4---10----5 ---7---6-----3---1 délka je už L=55 Další pokračování je: 1---4---2----12---4---10----5 ---7---6-----3---1

Teď je délka 63 km.

Finální trasa je: 1---4---2----12---4---XXX----7----XXX---5---7---6-----3---1

34


Rozvozní úloha V (nosnost) = 15, požadavky: 0, 4, 5, 7, 5, 4, 6, Všechny jízdy vyjíždějí z jedničky. Z jedničky vyjedu a objedu pár měst, pak se vrátím zpět do jedničky, abych nabral další náklad a rozvezu ho dál a tak pořád dokola. Model: - ∑∑cijxij ---- min. Pro i ≠ j nemá smysl řešit - ∑xij = 1,pro všechny i = 1,2,...,n, - dělá se i součet ve sloupci ∑xij = 1,pro všechny j = 1,2,...,n ui + qj – V(1-xij)≤ uj ui ≤ V Nová proměnná ui představuje obsah nákladu. Při 100 uzlech už neřešitelné, jde o exponenciální složitost.

Všechny předcházející tři způsoby jsou heuristické metody. Příklad. Kapacita vozu je 15 kontejnerů. Vyjeď z Kralup a najdi nejbližšího souseda, takže 1---4--- 2(požadováno 4 kontejnerů). Ale než to napíšu, tak se musím podívat na kapacitu, která je 15 a tedy 4 ≤ 15. Z dvojky je nejbližší soused číslo 4 a délka 2---12 ---4 (7). Dalším sousedem by měla být 5, ale zde požadují 5 sudů, což přesahuje kapacitu. Řešením je vybrat další uzel, který se vejde do počtu uzlů nebo se vrátit zpět do jedničky, naložit auto a jet znovu do nejbližšího souseda, což je 3, 1---16 --- 3(5). Z 3 jedu do 5, 3----XXX---5(5). Z 5 můžu do 6, je 5---XXX----6(4), tímto uzel končí,protože už nemám co dát. Zbývá uzel 7, který beru už samostatnou jízdou. Tedy 1---7.

35


Úloha čínského listonoše -

úkol není navštívit všechny uzly, ale projít všechny hrany (význam pro posyp silnic, odklízení ulic...) stupe%n uzlů. je-li každý uzel spojen se sudým počtem hran.

Toky GRAFEM: obrázek: kij

xij

to hranou (ij)

0 ≤ xij ≤ kij

∑ xij = ∑xik i k vtok do uzlu j, odtok z uzlu j

kapacita hrany (nij) Účelová funkce: ∑xij což je to samé jako ∑xj6 --- obojí se musí maximalizovat zobecněním jsou úlohy nejlevnějšího toku.

36


Teorie zásob ztráta na kus = 1,5 1.5 7 5,5 = zisk/ks q = počet kusů poptávky, p(q) = pravděpodobnost, kolik lidí se na tento časopis zeptalo 0 1 2 3 4 5 6 7 q 0 0 0,05 0,15 0,25 0,3 0,15 0,1 p(q) průměrná poptávka je 4,65 sigma je = 1,7 efektivita výtisků: objednávám x výtisků

1 ks 2 ks 3 ks 4 ks 5 ks 6 ks 7 ks

Prodáno (pravděpodobn) 1 1 0,95 0,8 0,55 0,25 0,1

neprodáno 0 0 0,05 0,2 0,25 0,75 0,9

Středni h. na výhos 5,5 5,5 5,25 4,4 3,025 1,375 0,55

Střední hodn. ztráta 0 0 0,075 0,3 0,375 1,125 1,35

Zisk 5,5 5,5 5,175 4,1 2,65 0,25 -0,8

MP = 5,5 ML = 1,5 MP*Pq ≥ ML (1-Pq) = ML – ML*Pq – (MP + ML)Pq ≥ ML Py ≥ ML / (MP + ML) 1,5 / 7 ≥ 0,21, zastavím se u nákupu ve chvíli, kdy je pravděpodobnost nižší než 0,21

Modeling zásob -

velikost zásob MP (marginal profit – zisk na 1 kuse) – ztrátou když nemám výtisk, ale mám zákazníka ML (marginal lost – ztráta na 1 kuse) – vyplívá z faktu, že objednám zboží a nepřijde zákazník a nemám možnost ho prodat. MP . Pq >= ML (1-Pq) Pq >= ML / (MP + ML)

ML = 4000 Kč/kg MP = 6000 Kč/kg C = 50 kg Sigma = 10 kg Py = ML / (MP + ML) = 4000 /(6000 + 4000) = 0,4

37 0,6


q60 = ? Z60 = q60 – q´ / sigmaq 0,25 = Z60 = (q60 – q´) / sigmaq = (q60 – 50) /10 = 50 + 10.0,25 = 52,5 Doporučuje objednat 52,5 kg.

Dynamický model -objednávám pravidelně – objednací dávky Q = 36000 t C1 = 24 Kč/1 t za rok C2 = 12000 Kč stojí vyřízení objednávky 1 varianta (1 dodávka) 36000 1 rok 18 000

Q t Průměr velik. skladu Půrm. Skl . 432 000 24 objednávka 12 000 Suma 444 000

2. var (2 dodávky)

3. var.

4. var

5. var.

6. var.

7. var

18 000 ½ 9 000

12 000 1/3 6 000

9 000 ¼

7200 1/5

6000 2 měs

5192 1/7

216 000

144 000

24 000 240 000

36 000 180 000

156 000

146 000

144 600

146 000

38

EKO210 – Kvantitativní management Průměrná velikost skladu = (začátek + konec) /2 = q/2 Náklady skladovací = c1*q/2 Objednací náklady = Q/q*c2 N(q) = C1*q/2 + Q/q*c2 ---- min Q/q*c2

C1, q/2

dN /dq = 0

Má jediné globální minimum dN /dq c1/2 – 1c2 /q2 = 0 q2 = 2Qc2/c1 c1/2 = Qc2 / q2 q* = odmocnina ((2Qc2)/c1) = odmě ((2.36000.12000) / 24) = 6000

6000

r

d

Stanovení signální úrovně skladu a velikost předstihu objednávky -

kdy vyslal signál na novou dodávku s dostatečným předstihem

d…doba předstihu objednávky = např. 14 dní = 1/24 roku Var A d = 14 dní: r … velikost spotřeby během 14 dnů, r = Q*d = 36000*1/24 = 1500 tun

Var B: d = 3 měsíce = ¼ roku r = Q*d = 36000*1/3 = 9000 – 6000 = 3000

39

EKO210 – Kvantitativní management Systém nefunguje, protože zásoba by měla klesnou pod úroveň na kterou se nikdy nedostanu maximální zásoba je 6000 tun a my chceme aby, když klesne pod 9 tisíc, aby se ozval. Vzoreček je špatně. Od výsledku musíme odečíst velikost dodávky, která je na cestě. Čerpání takhle nefunguje,protože čerpání není rovnoměrné (jiná spotřeba uhlí v létě a jiná v zimě).

Stochastická poptávka Odhaduje jaká bude spotřeba a až na konci roku zjistím skutečná data. Stejná jako předchozí, ale liší se v bodě, kdy se bude objednávat. - vychází ze střední hodnoty poptávky = q q = 6000 tun W q

r+W

d Když na konci měsíce nic není, tak to je optimální. Realita je ovšem taková, že na konci většinou něco zůstane, ale může nastat i situace, že na konci bude nějaká zásoba chybě (nepříznivý případ). Řešením je pojistná zásoba (pojistím se na případné výpadky) = W. Má překlenou případ, kdy na konce období chybí zásoba. Když bude W velká, tak bude vysoká jistota, že problémy nebudou, ale když bude malá, tak problémy pokrýt nemusí. Avšak velké W znamená velké náklady. Pojistná zásoba ať je jakákoliv, tak je teoretická možnost že dojde k nepříznivé situaci. γ = pravděpodobnost, že nedojde k přerušení zásobování. Např. γ = 0,95 pojistná zásoba hraje roli jen v intervalu d γ = 1500 tun = Q*d qd = náhodná veličina, která představuje poptávku v intervalu <0;d>

qd´= r = 1500 tun δd = 200 tun – odchylka

qd´ = znamená střední hodnota, alias qd s čarou

P (qd <= (qd´ + W)) = 0,95

40


qd95 1500 Z95 = (qd95 - qd´)/ δd = 1.645 = (qd95 – 1500) / 200

qd95 = 1500 + 1.645*200 = qd´ + Z95*δd = 1829 tučné je pojistná zásoba W = Z95*δd Signální úroveň jsme posunuli na 1829 tun. Pojistná zásoba nás však stojí jisté náklady. DeltaNáklady = c1W = 24 * 329 = 7896. Průměrné náklady na 3 jsou 7896 Kč.

δd = Směrodatná odchylka spotřeby během 14 dnů γ = 0,99 W = δd*Z99 = 200*2.35 = 466, takže W se zvětšilo oproti původnímu příkladu Změna nákladů = c1*W = 24*466 = 11 184 Kč.

Produkční model zásob – nebude u zkoušky q

p>h

p*t - výroba

ht spotřeba Prům. sklad

Sklad

t Vypínám stroj a jedujen ze zásob

41

EKO210 – Kvantitativní management N(q) = c1*(prům.velikost.zásoby) + Q/q*c2 ---min Problém s určením průměrné velikost zásob (prům. sklad) q* = odmocnina ((2Qc2)/c1) * odmocnina ((p/(p-h)))

Model obnovy - obnova zařízení, stroje - rozhodující je, kdy se bude obnovovat K = 40 000 – nákupní cena nového zařízení, stroje Ci – náklady na údržbu Zi – zůstatková cena Ci Zi

1. rok 5 30

2. rok 6 25

3. rok 7 20

4. rok 9 17

5. rok 14 8

6. rok 18 6

7.rok 25 4

Nejdůležitější je úvaha, kterou funkci budu brát jako rozhodující pro dobu výměny. Budeme sledovat průměrné roční náklady a v okamžiku, kdy tyto náklady začnou růst, tak stroj vyměnit. Ei = průměrné roční náklady E1 = 5000 + 10 000 = 15 000 E2 = ((5000 + 6000) + 15 000) /2 = 26 000 / 2 = 13 000 E3 = ((5000 + 6000 + 7000) + 20 000) / 3 = 38 000 / 3 = 12 680 E4 = …. = 12 250 E5 = …. = 14 600 Vyměním po čtvrtém roce, protože do čtvrtého roku náklady klesají a od čtvrtého roku začnou stoupat. Ei = ((K-Zi + c1 + c2 + ci)) / i

Teorie hromadné obsluhy (teorie front) - 2 základní prvky: požadavky a obslužné linky (obslužné kanály) - požadavky: pacient, který chce ošetřit - obslužná linka: lékař - prochází systémem, chtějí obsloužit požadavek konečný a nekonečný: pacienti jsou nekonečný zdroj (mohou přijít klidně dvakrát), konečný zdroj (v továrně pracuje 20 strojů a jak se porouchávají, tak opravář líté okolo nich pořád dokola) - vstup požadavků: mohou vstupovat jednotlivě nebo hromadně - fronta: FIFO, LIFO, SIRO (náhodně se vybere, kdo přijde na řadu – jakási loterie), PRI (priority, první šli na řadu ženy a děti...) obslužné linky: uspořádání 1. jednoduchý systém – jedno obslužné zařízení (linka) 2. paralelní systém – více obslužných linek, záleží na tom, jaké ty linky jsou:

42

EKO210 – Kvantitativní management a) identické (poskytují stejné služby – obsluhu). V bance přijdou lidé, kteří se řadí do jediné fronty a ten kdo je první na řadě jde k okénku

b) požadavky se hromadí před každou identickou linkou, pokladny v maloobchodu

c) neidentické linky, před každou se tvoří individuální fronta, která poskytuje jinou službu, banka, expresní pokladny v hypermarketu

3. sériové uspořádání – za sebou řazeny linky, tedy člověk musí proházet postupně všechny části

4. kombinace předchozích (2 a 3) např. benzinka (stojany, parkovací místa, myčka) Kendallova klasifikace modelů hromadné obsluhy - model se specifikuje 6 místným kódem (A/B/C/D/E/F) - na místě A – se specifikuje pravděpodobností rozdělení intervalů mezi příchody požadavků (nejčastěji zde bývá M – což znamená exponenciální rozdělení, nebo N – normální rozdělení, U – rovnoměrné rozdělení, G – obecné rozdělení, D – nějaké konstanta, stejný klíč platí i pro B) - na místě B – se specifikuje pravděpodobnostní rozdělení doby obsluhy - na místě C – počet paralelně uspořádaných výrobních linek - na místě D – se uvádí kapacita systému, pokud nekonečno = kapacita systému je neomezená. Když je nějaké číslo tak udává tu kapacitu (např. 20) - na místě E – se uvádí zdroje požadavků (nekonečné znamená neomezené zdroje), když např.20, tak mám možnost jen 20 požadavků - na místě F- se uvádí řád fronty (FIFO, LIFO, SIRO, PRI) nejčastější případy např: M/M/1/nekonečno/nekonečno/FIFO, pokud uvedu pouze M/M/1, tak se očekává že zbytek je ten výše uvedený analytické modely – exaktní přístup – mám teorii a odvodím vzoreček a parametry, které k systému mám dosadím do vzorce simulační modely – odkoukám parametry od nějakého jiného systému a tyto parametry pak dosadím do vzorce a odzkouším

43

EKO210 – Kvantitativní management jednoduchý exponenciální kanál:

- požadavky přichází tak, že rozdělení se řídí poissonovým rozdělením, n... počet požadavků (λT )n e −λT přicházejících do systému v určitém časovém intervalu <0;T> p(n ) = n! - lambda = intenzita přechodu požadavku pro <0;1> p(n ) =

(λ )n e −λ

určitý počet požadavků, které přicházejí do systému, popis vstupu n! E(n) = lambda, D(n) = lambda lambda = střední průměrný počet požadavků, které do systému za určitou časovou jednotku t.. veličina, která představuje intervaly mezí příchody požadavku f (t ) = e − λt - spojité má hustotu pravděpodobnosti f(n), t>0, jde o exponenciální rozdělení při příchodu 60 požadavků je průměrná doba 1 požadavku 1/60 hodiny 1 1 E (t ) = D(t ) = 2 popis vstupu distribuční fuknce F (t ) = 1 − e − λt

λ

λ

lambda = intenzita vstupu, průměrný počet, který vstoupí do systému za čas. jednotku mí – intenzita obsluhy, průměrný počet požadavků obsloužených za čas jednotku. Můžeme odvodit f (t ) = µe − µt

podíl intenzit:

ρ=

λ - intenzita provozu, průměrný počet pacientů, kteří přijdou / průměrný počet, který je µ

schopen obsloužit. Podíl vstupu požadavku / schopnost obsluhy platí že ró < 1, pokud by tomu nebylo, nebylo by možné řešit s uspokojením. 1

= průměrná doba obsluhy

µ µ = průměrný počet obsloužených zákazníků Příklad: Máme prodejnu s jedním pultem. Do prodejny přichází průměrně 18 zákazníků. Za hodinu je schopen obsloužit 25 zákazníků. lambda = 18, mí = 15 ró = 18 /25 = 0,72 což je < 1, 0,72 nám udává intenzitu provozu a jak je využit. Je využit ze 72%. 0,72 je i pravděpodobnost, že linka pracuje. Je to také pravděpodobnost, že požadavek bude muset čekat.

p0 = že nebude žádný požadavek v systému. ró = pravděpodobnost že bude muset čekat p0 = 1 – ró, takže v příkladu to je p0 = 1- 0,72 = 0,28. pn = p0 . rón = (1-ró)rón

- pravděpodobnost, že v systému je n požadavků

44

EKO210 – Kvantitativní management T´ = průměrný čas, který stráví požadavek v systému T =

1 µ −λ

minuty

průměrná doba, kterou stráví požadavek ve frontě T f = T − T´f = 0,103 hodiny = 6,2 minut N = λ T N f = λT f - littleovy vztahy N=

λ µ −λ

λ2 Nf = µ (µ − λ )

1

µ

=

T´= 0,143 hod = 8,6

1 1 λ − = µ − λ µ µ (µ − λ )

pamatovat!!!

pamatovat!!!

N´ = průměrný počet požadavků v systému N´f = průměrný počet požadavků ve frontě N´ = 2,57 lidí je v té prodejně N´f = 1,85 lidí Závěry: Průměrný počet zákazníků, včetně jednotky v obsluze je N (nebo N s pruhem...)

N=

λ

µ −λ

λ2 průměrná délka fronty N f = µ (µ − λ ) 1 µ −λ 1 1 1 λ průměrná doba, kterou stráví požadavek ve frontě T f = T − = − = µ µ − λ µ µ (µ − λ )

T´ = průměrný čas, který stráví požadavek v systému T =

Pokud opustím předpoklad, že jde o exponenciální rozdělení, tak jsou teorie mnohem složitější a nejsou tak prozkoumané. Paralelní systém hromadné obsluhy s paralelním uspořádáním linek Model M/M/c c = počet obslužných linek s paralelním uspořádáním

c

intenzita provozu ρ =

λ pamatovat, a zase platí že je to menší než 1 cµ

45

EKO210 – Kvantitativní management mí = intenzita obsluhy u jedné linky c.mí = je intenzita obsluhy celého systému Optimalizace systémů hromadné obsluhy - jde o minimalizace nějakých celkových nákladů, které souvisí s hromadnou obsluhou. N(c), například benzínové pumpy... - kc, kde k jsou náklady na jednu obslužnou jednotku + náklady na pobyt zákazníků v systému, a k3, jsou ztráty ušlého zisku N(c) = c*k1 + N´*k2 + (lambda*pk*k3) ------ min

c*k1 = celkové fixní náklady (plat všech pokladních v krámě) k2 = jednotkový náklad související s pobytem jednoho požadavku v systému. N´*k2 = celkové náklady na pobyt požadavku v systému k3 = pokud je omezená kapacita systému, tak k3 je maximální počet omezení v systému, nás pak zajímá pravděpodobnost že v systému je počet požadavků ... pk (lambda*pk = kolik lidí systém opustí z důvodu přeplněnosti), k3 = kolik lidí nepřjjde funkce je diskrétní a má konvexní tvar

Simulační modely -

nejdříve začíná pozorování a po něm následuje převedení systému do počítače.

P: příchod požadavku U: ukončení obsluhy Simulační modely počítají s proměnlivým časovým krokem (diskrétní simulace) Pokud přijde požadavek do systému a obslužná linka je prázdná tak pak se vygeneruje doba obsluhy a čeká se na ukončení obsluhy.... P: prázdná --- U Jestliže je fronta, tak se čeká až se uvolní a navíc se fronta o 1 zvýší: P: fronta --- F: = F+1 U: je někde ve frontě F ---- vygeneruje se doby obsluhy ---- F = F-1 (přikročí se k obsluze) U: ve frontě nikdo není ---- pak se eviduje prostoj a čeká se na další požadavek Intervaly mezi příchody požadavků i doby obsluhy se musí vygenerovat. Generují se náhodná čísla z rovnoměrného rozdělení <0;1> nechť r je náhodné číslo vzore pro počítač: t =

k (1 − r )

λ

exponenciální rozdělení lambda

Model obnovy: Ei = (K – zi + (c1 + c2 + ...+ci))/i ve chvíli kdy náklady začnou růst, tak je vhodné zařízení obnovit

46


2-) predikční model – kolik náhradních dílů budeme potřebovat n = počet dílů = 100 (žárovek) charakter poruch = během 1. měsíce se porouchá 10 % 1 2 3 4 5 6 pi 0,1 0,3 0,35 0,15 0,05 0,04 Přežití - ri 0,9 0,6 Suma = 1 Průměrná životnost = 1*0,1 + 2*0,3 + 3* 0,35...7*0,1 = 2,91

7 0,01

Jakou mám strukturu souboru zářivek za jednotlivé měsíce – na začátku mám všechny zářivky nové (je jich 100), vytváří se věková struktura souboru Pravděpodobnost přežití nové žárovky jeden měsíc (u0*r2) = střední hodnota 0 0 1 (u) 2 Nové 100 10 (u0*p1) 31 u2 u3 1 měs 90u (u0*r1) 9 (u1*r1) u2*r1 2 měs 60 (u0*r2) u1*r2 3 u0*r3 4 u2 = u1*p1 + u0*p2 = 31 – to musím mít na skladě u3 = průměrný počet jednotek, které budou ve 3. měsíci potřeba na výměnu u3 = u2*p1 + u1*p2 + u0*p3

Vícekriteriální rozhodování jde o maximalizační kritérium Výkon vzdálenost Náklady P1 40 8 10 (40) P2 60 15 20 (30) P3 80 20 20 (30) P4 30 3 0 (50) max3 0-80 max 3-20 (min 30-50) max 0-20 P5 40 7 10

Živ. prost. 1 2 3 0 max 0-3 1

Kvalita 5 4 3 5 max 3-5 – nejlepší je 5 4

ideální varianta – všechny kritéria nejlepší dominovaná variata – to je ta, která je ve všech nejhorší – P5 je horší než P1 – dominované varianty hned vyškrtáváme. P1 není dominována p2 – je alespoň v jednom kritériu lepší P1 dominuje P4, protože P4 je horší ve všech kritériích Výkon vzdálenost Náklady Živ. prost. Kvalita P1 40 8 10 (40) 1 5 P2 60 15 20 (30) 2 4 P3 80 20 20 (30) 3 3 Tyto tři se nazývají nedominované varianty – je nedominovaná, jestliže nenajdeme výrazně lepší ve všech kritériích

47


Metody řešení – metoda aspiračních úrovní -

aspirační úroveň je síto, kterým se prosejí jednotlivé návrhy aspirační úroveň (40, 8, 10, 1, 4) P1 – splňuje, P2 – splňuje, P3 – nesplňuje, protože zbyly 2 varianty, tak se komise musí dohodnout na zpřísnění alespoň jedné podmínky, nová aspirační úroveň (40, 10, 1, 4) P1 – neprošla, P2 – prošla

Metoda Vah hodnoty v jednotlivých sloupcích vynásobím vahami a tyto čísla pak sečtu a výsledek rozhodne normalizace hodnot – snaha o čísla mezi 0 a 1 váhy 0,3 0,2 0,2 0,2 0,1 K1 K2 K3 K4 K5 Suma P1 0,2 0,3 0,5 0,3 1 0,38 P2 0,6 0,7 1 0,6 0,5 0,7 P3 1 1 1 1 0 0,9 P4 0 0 0 0 1 0,1 normalizace: yij = (xij – Lj) / (Uj – Lj) Lj = nejmenší hodnota ve sloupci j Uj – největší hodnota ve sloupci j

Jak udělat váhy? – Jak stanovit váhy? -

seřadit jednotlivá kritéria – a daný člověk řekne co je jak pro něj důležité K1 K2 K3 K4 K5 pořadí 3 5 4 1 2 Opač. poř. 3 1 2 5 4 – Suma 15 váhy 3/15 1/15 2/15 5/15 4/15 Další možností je párové porovnání kritérií tučné jsou vybrané varianty: K1 K1 K1 K1 K4 K5 K2 K3 K2 K2 K2 K4 K5 K3 K3 K3 K4 K5 K4 K5

kolikrát zvolil danou variantu K1 K2 K3 K4 K5 2 1 0 3 4 Suma=1 2/10 1/10 0/10 3/10 4/10 Teď to jsou váhy, protože ty nejdůležitější zvolil v největším počtu

48


Saatyho metoda -

porovnává kritéria mezi sebou, ale je jemnější 1 znamená že jsou stejně důležité, rozsah hodnot je 1-9 Sij – jsou buď >1 = 1 obě kritéria jsou stejná <1 Sij = 1/Sji

K1 K2 K3 K4 K5

K1

K2

K3

K4

K5

5 ΠS ij

1 5 3 1/6 1/8

1/5 1 ½ ½ 1/5

1/3 2 1 3 3

6 2 1/3 1 1/2

8 5 1/3 2 1

1,26 2,51 0,58 0,87 0,518

Sij = Vi / Vj 5 ΠS ij

49

EKO210 Kvantitativní management. Creative Commons. Attribution-NonCommercial-ShareAlike 2.0. You are free:

Recommend Documents