VYSOKÁ ŠKOLA FINANČNÍ A SPRÁVNÍ, o.p.s. Fakulta ekonomických studií
Denisa Kaderková
Matematická optimalizace v podniku potravinářského průmyslu
DIPLOMOVÁ PRÁCE
Praha 2011
VYSOKÁ ŠKOLA FINANČNÍ A SPRÁVNÍ, o.p.s. Katedra podnikové ekonomiky Navazující magisterské studium prezenční
Denisa Kaderková
Matematická optimalizace v podniku potravinářského průmyslu Optimization modeling in a food company
DIPLOMOVÁ PRÁCE
Praha 2011
Vedoucí diplomové práce: Ing. Václav Janoušek
Poděkování Zde bych ráda poděkovala vedoucímu své diplomové práce Ing. Václavu Janouškovi za jeho přístup, trpělivost, cenné a odborné rady, které velikou měrou přispěly k vytvoření této diplomové práce. Dále bych tu ráda poděkovala panu Doc. Ing. Jaroslavu Švastovi, CSc. za jeho odborné konzultace. Nesmím
opomenout
poděkovat
pracovníkům
společnosti
United Bakeries a.s. za jejich vstřícnost. A mé poslední poděkování patří Věře Cupalové, Anetě Lazarové a Ing. Lence Lazarové za jejich neustálou motivaci a podporu během celého studia a zejména při vzniku této práce.
2
Prohlášení P r o h l a š u j i,
ţe jsem tuto závěrečnou práci vypracovala zcela samostatně a veškerou pouţitou literaturu a další podkladové materiály, které jsem pouţila, uvádím v seznamu literatury a ţe svázaná a elektronická podoba práce je shodná.
12.4.2011
3
Denisa Kaderková
Abstrakt V diplomové
práci
se
zabývám
ekonomicko-matematickými
optimalizačními metodami známých jako operační analýza nebo operační výzkum, jejímţ cílem je optimalizace ekonomických procesů. Tyto metody byly vyvíjeny po druhé světové válce jak v západních zemích, tak v zemích tehdejšího Sovětského svazu. Na
Vysoké
metody
doposud
škole
finanční
neprosadily,
a
správní
proto
je
o.p.s. moje
se
tyto
práce
svým
způsobem pionýrským projektem. V práci
konkrétně
zpracovávám
řešení
jedné
z těchto
metod – okruţní dopravní problém.
Abstract This research work deals with the mathematical economics optimization methods known as operational research methods - aimed at optimizing economic processes. These methods were
developed
Western In
after the
countries
the
University
Second
and of
the
Finance
World former
and
War in
both
Soviet
Administration
the
Union. o.p.s.
these methods have still not been adopted. That is why this thesis
can
be
considered
as
an
innovative,
pioneering
project. The
practical
part
of
the
thesis
is
specifying
the
processing solution for one of these methods and applying it to the sightseeing transportation problem.
4
Klíčová slova Operační analýza, Maďarská metoda, Okruţní dopravní systém, Simplexová metoda
Keywords Operational
analysis,
hungarien
transportation sproblem, simplex method
5
method,
orbital
Obsah Prohlášení ............................................... 3 Abstrakt ................................................. 4 Klíčová slova ............................................ 5 Keywords ................................................. 5 Obsah .................................................... 6 Úvod ..................................................... 8 1
Operační analýza ..................................... 11 1.1
Úvod do operační analýzy .......................... 11
1.2
Podstata operačního výzkumu ....................... 12
1.3
Vlastnosti operační analýzy ....................... 13
2
Teorie modelování ekonomických systémů ............... 15
3
Teorie modelování matematického modelu ............... 17
4
Řešení matematického modelu .......................... 19 4.1
5
Klasifikace disciplín operační analýzy ............ 19
Matematické programování ............................. 21 5.1
Lineární programování ............................. 21
5.1.1 Kanonický tvar ................................. 22 5.1.2 Standardní tvar ................................ 23 5.1.3 Obecná úloha lineárního programovaní - převody . 23 5.1.4 Lin-Kerninghan metoda .......................... 25 6
Input – output modely ................................ 26 6.1
Identifikace jednotlivých prvků bilančního modelu . 27
6.2
Identifikace vazeb bilančního modelu .............. 28
6.3
Definice parametrů a proměnných bilančního modelu . 28
6.4
Formulace bilančního modelu a jeho kvantifikace ... 29
6.4.1 Model mezivýrobkových vztahů ................... 29 6.4.2 Materiálové vstupy do bilančního modelu ........ 30 6.5 7
Nalezení vlastního řešení bilančního modelu ....... 32
Modely hromadné obsluhy .............................. 34 7.1
Exponenciální model jednoduché obsluhy ............ 37
7.1.1 Základní charakteristiky exponenciálního sytému 41 8
Počítačové simulace .................................. 42 8.1
9
6
Metodika tvorby počítačových simulačních modelů ... 43
Řízení zásob ......................................... 44 9.1
Význam zásob ...................................... 44
9.2
Členění zásob ..................................... 45
9.3
Funkce zásob ...................................... 46
10 Systémy řízení zásob poloţek s náhodnou proměnlivou poptávkou v čase ........................................ 47 10.1 Q Systémy ......................................... 48 10.2 P - systémy ....................................... 53 11
Teorie grafů ....................................... 55
11.1 Kostra grafu ...................................... 56 12
Formulace obecného dopravního problému ............. 58
12.1 VAM metoda ........................................ 58 13
Okruţní dopravní systém ............................ 60
13.1 Obecný návrh postupu řešení ....................... 61 13.2 Metody řešení okruţní dopravní úlohy .............. 62 13.2.1 Metoda nejbliţšího souseda ..................... 62 13.2.2 Hamiltonova kruţnice ........................... 62 13.2.3 Heuristické algoritmy .......................... 63 13.2.4 Kimova metoda .................................. 64 13.2.5 Úloha optimálního trasování .................... 65 13.2.6 Swamm metoda ................................... 65 14
Praktická část ..................................... 67
15
Dopravní distribuční problém ve společnosti United bakeries a.s. ...................................... 68
15.1 Představení společnosti United bakeries a.s. ...... 68 15.2 Navrţený matematický algoritmus vztahující se k problematice dopravního okruţního problému ........ 69 15.2.1 Úvod ........................................... 69 15.2.2 Algoritmus ..................................... 71 15.2.3 Jednotlivé kroky algoritmu ..................... 72 15.2.4 Příklad řešení obecného příkladu ............... 75 15.2.5 Maďarská metoda ................................ 80 15.3 Zdání distribuční úlohy ve společnosti United Bakeries a.s. ..................................... 82 15.3.1 Sestavení matice vzdáleností ................... 83 15.3.2 Nalezení optimální cesty ....................... 84 16 Dopravní okruţní distribuční problém navrţený panem Doc.Švastou .......................................... 86 16.1 Zadání dopravní úlohy ............................. 86 17
Závěr .............................................. 88
Seznam pouţité literatury ............................... 90 Přílohy ................................................. 92
7
Úvod Předloţená
diplomová
práce
se
zabývá
zajímavým
tématem
operační analýzy a jejími jednotlivými metodami, kterými se daná problematika řeší. Vědní disciplína operační analýza, jinými slovy operační výzkum, se začala vyvíjet po druhé světové válce ve vojenském odvětví, protoţe bylo nezbytné koordinovat zásobování na jednotlivých válečných frontách. Dalším
důleţitým
Rychlý
rozvoj
mezníkem
byl
informačních
vývoj
výpočetní
technologií
techniky,
způsobil,
ţe
se
metody operační analýzy staly přístupnější širšímu okruhu uţivatelů.
S nadsázkou
se
můţe
říci,
ţe
vyřešení
úlohy
operační analýzy se stalo z části technickou záleţitostí (např. naprogramované funkce v tabulátoru Excel). Téma
operační
analýzy
jsem
si
vybrala
vzhledem
ke
svému bakalářskému vzdělání, které jsem získala na Vysoké škole chemicko-technologické v Praze, kde jsem matematickou optimalizaci a s ní spojenou operační analýzu studovala a řešila po celou dobu svého bakalářského stupně vzdělání. V dnešní době operační analýza není primárně zaměřena na vojenství, ale na koordinaci, transport a alokaci výstupů průmyslové výroby (obzvláště v potravinářském a chemickém průmyslu) či na koordinaci sluţeb. Bez rozpaků je moţné tvrdit,
ţe
pouţití
metod
operační
analýzy
má
schopnost
sníţit náklady podniku aţ o několik procent. Tuto tezi se budu snaţit dokázat v této diplomové práci. Tématem operační analýzy se zabývají spousty autorů. Ze zahraničních
autorů
se
nesmí
opomenout
uvést
Steven
Nahmais. Z českého prostředí se tématikou zabývá pan prof. Stanislav
Gros,
který
o
problematice
publikoval
několik
rozsáhlých prací např. Kvantitativní metody v manaţerském rozhodování I, II. Dále se tématem zabývá pan. Doc. Švasta, který publikoval rovněţ nespočet publikací týkajících se 8
operační
analýzy,
ale
hlavně
se
téměř
celou
svoji
akademickou kariéru věnuje dopravnímu okruţnímu problému neboli problému obchodního cestujícího. Problém obchodního cestujícího je taková úloha, kdy existuje n měst, mezi nimi existuje
ohodnocené
kilometrů) prochází
a
Okruţní
úkolem
všemi
výchozího
spojení je
městy
bodu.
dopravní
nalezení
právě
Hledá
(cesta,
se
problém
nejkratší
jednou tedy
je
silnice
a
vrátí
cesty, se
Hamiltonovská
shledáván
s počty jeţ
zpět
do
kruţnice.
problematikou
pro
třetí tisíciletí. A to z toho důvodu, protoţe zatím nebyl publikován
obecný
s konečným
tzn.
algoritmus,
nejefektivněji
jak
danou
moţným
úlohu
řešením.
vyřešit Aby
bylo
moţné operační analýzu úspěšně pouţívat, aniţ bychom se omezili
na
automatické
pouţívání
přednastavených
funkcí
v Excelu, je zapotřebí znát matematické operace matic a vektorů z matematiky a zároveň znát principy metody, kterou jsme se rozhodli pouţít. Cílem práce je popsat a vytvořit stručný přehled o uţívaných metodách operační analýzy. Dále v praktické části je
tato
diplomová
práce
zaměřena
na
okruţní
dopravní
problém. V rámci této diplomové práce se podařila navázat spolupráce s největší pekárenskou firmou v České republice a jednou z největších pekárenských firem ve střední Evropě a
to
firmou
United
Bakeries
a.s.
Díky
spolupráci
logistického oddělení firmy, konkrétně pana Ing. Hurába, v této
práci
s praxí.
byly
Hlavním
zpracovány cílem
této
a
porovnány práce
bylo
výsledky
teorie
nalezení
takové
optimální trasy, která bude nejoptimálnější pro daný okruh. Nalezne
se
tedy
Hamiltonovská
kruţnice.
United
Bakeries
a.s. kaţdý den uţívá trasu, kterou povaţuje za optimální a tato práce se pokusila nalézt cestu ještě optimálnější. Diplomová práce obsahuje popis algoritmu, který se na řešení problematiky okruţního dopravního problému pouţil. Algoritmus je vlastně modifikovaná Maďarská metoda, která 9
je
upravena
problém.
10
tak,
aby
byla
vhodná
na
okruţní
dopravní
1
Operační analýza
1.1
Úvod do operační analýzy
V moderní společnosti existuje několik důleţitých mezníků, které
poloţily
základ
k formulování
vědního
oboru
-
operační analýzy: o
Druhá světová válka – do období druhé světové války výzkum
a
věda
pracovníky
dostatečně
průmyslové
nespolupracovaly
praxe
a
s řídícími
průmyslová
praxe
neefektivně spolupracovala s vědou a výzkumem, protoţe nedokázala přesně formulovat a definovat své poţadavky. Avšak průběh druhé světové války dal vzniknout potřebě řízení
vojenského
zásobování
a
koordinaci
vojenských
činností. Tím
byl
logistiky. dali
poloţen
základ
Armáda
zahájila
vzniknout
prvním
nové
vědní
spolupráci
skupinám
disciplíny s vědci,
vojenského
–
kteří
operačního
výzkumu. [P.Pernica 1998], [Karas, Gros, Sokolová 1992] o
50.
Léta
praktická
–
bouřlivý
potřeba
ekonomický
jeho
rozvoje.
poválečný A
rozvoj
rozvoj, výpočetní
techniky Toto v oblasti
vše
vedlo
hmotné
k mohutnému
výroby
a
s tím
znásobování spojené
se
vazeb
zvyšující
se
poţadavky na náročnost v řídících a rozhodovacích procesech [Karas, Gros, Sokolová 1992]. Aby řešení ekonomických otázek bylo účelné a efektivní je zapotřebí sesbírat a hlavně vhodně uspořádat informace s řídícím
a
rozhodovacím
procesem
spojené.
Na
základě
těchto informací se musí stanovit varianty rozhodnutí a
11
správně vyhodnotit a zejména interpretovat jejich důsledky. [Karas, Gros, Sokolová, 1992] Proces
rozhodování
Zodpovědnost problém
a
řídí
poté
je
manaţer,
řízení
který
formuluje
cesty,
zodpovědnosti.
identifikuje jak
nejdříve
postupovat
v jeho
následném řešení. Jedná se svým způsobem o proces analýzy identifikovaného
problému,
který
má
dvě
základní
formy:
kvantitativní a kvalitativní [Římánek, 1979]. Kvalitativní přístup je spojen s úsudkem manaţera či jeho
osobní
minulou
rozhodování, Mnohokrát
které
je
s rostoucí
zkušeností. není
spojeno
kvalitativní
sloţitostí
kombinovat
Jedná
a
intuitivní výpočty.
postačující.
produkce
kvalitativní
o
s empirickými
přístup
výroby
se
je
Avšak
zapotřebí
přístupy
s přístupy
kvantitativními. Kvantitativní analýza je zapotřebí, pokud si manaţer nevystačí
s intuitivními
metodami
a
vlastní
zkušeností.
Pokud je problém komplexní a je potřebné uţít důkladnou analýzu
zaloţenou
na
vědeckých
základech.
Josef
Římanek
s kolektivem ve své publikaci uvádí: „Znalost kvantitativní analýzy
problému
všeobecné
zvyšuje
kvalitu
řídících
schopností manaţerů na všech stupních řízení“[J. Římánek, 2002,
s.
46].
ekonomických
Výhodou jevů
kvantitativních
je
vztazích
matematického moţnost mezi
přístupu
zpřesnit
jednotlivými
v oblasti
znalosti
o
ekonomickými
kategoriemi. (Karas, Gros, Sokolová 1992)
1.2
Podstata operačního výzkumu
Jedna z definic operačního výzkumu říká: „Operační výzkum představuje způsob týmové spolupráce, při kterém skupina specialistů
12
různého
odborného
zaměření
komplexně
řeší
sloţitý ekonomický, technický, organizační nebo vojenskostrategický problém.“ [J. Římánek, 2002, s. 46] Základní
nástroj
operačního
výzkumu
je
matematické
modelování [J. Jablonský 2002]. Matematické modelování ekonomických procesů slouţí jako nástroj
pro
řízení
automatizace
v řízení,
bez
které
je
dnešní fungování ekonomických organismů nepředstavitelné. [Římánek 1994]. Z operačního
výzkumu
se
postupně
vydělila
operační
analýza. [P. Pernica 1998]
1.3
Vlastnosti operační analýzy
Čtyři základní vlastnosti operační analýzy dle doc. Grose jsou: a) Vyuţití matematických a statistických metod b) Uţití matematického modelování c) Skupinová spolupráce d) Komplexní (systémový) přístup
Ad a.) Za posledních padesát aţ šedesát let se vyvinula řada samostatných
disciplín,
které
se
zabývají
úkoly
efektivnějšího plánování a řízení v podniku. Tyto úkoly se řeší v okolí neustálého pohybu a technického pokroku, coţ vede ke stále sloţitějšímu a důleţitějšímu řešení úkolů. [ J.Walter - J.Lauber, 1975]. o Modely 1975]
13
hromadné
Mezi pouţívané metody patří:
obsluhy
[
J.Walter
-
J.Lauber,
o Paralelně
řazené
kanály
[
J.Walter
-
J.Lauber,
1975] o Sériově řazené kanály [ J.Walter - J.Lauber, 1975] o Modely dopravních proudů [ J.Walter - J.Lauber, 1975] o Zásobovací modely [ J.Walter - J.Lauber, 1975] o Lineární programování [Gros, Karas, Sokolová 1987] o Nelineární
programování
[Gros,
Karas,
Sokolová
Gros,
Karas,
Sokolová
1987] o Dynamické
programování
[
1987] o Síťová
analýza
[
J.Walter
-
J.Lauber,
1975],
[Gros, Karas, Sokolová, 1987] Ad c.) K získání
poţadovaného
a
interpretovatelného
výstupu
z operační analýzy je důleţité pracovat se správnými daty. Sběr dat je spojen s týmovou spoluprací, kdy spolupracuje technologické
oddělení
a
oddělení
managementu.
Jedním
z důleţitých aspektů je přítomnost pracovníků, kteří jsou s objektem zkoumání v denním kontaktu tzn. dělníci, mistři, procesní inţenýři. Dále musí být přítomen odborník, který je znalý v modelování tzn. pracovník, který umí sestavit model
a
zároveň
umí
interpretovat
výsledky.
[Christof
Schulte, 1991], [J.Walter - J.Lauber, 1975], [Gros, Karas, Sokolová, 1987]
14
2
Teorie modelování ekonomických systémů
Modelem
se
rozumí
systému.
Zobrazují
důleţité
při
zjednodušení
simplifikované se
řešení např.
pouze
ty
problému. fyzikální
zobrazení
vlastnosti,
Model modely
reálného
které
předpokládá a
jejich
jsou
spousty
zanedbání
tření atd. Zobrazení reálného systému modelem můţe být izomorfní či homomorfní. Definice izomorfního modelu zní: „ Model a systém jsou vzájemně izomorfní, kdyţ jde o přesný obraz, tedy kaţdému prvku a vazbě v systému odpovídá prvek a vazba v modelu“[
I.Gros,
2003,
s.18].
Homomorfní
model
je
naproti tomu definován: „ Při homomorfním zobrazení platí tento vztah pouze jednostranně, a to ve směru model-systém, tedy ke kaţdému prvku a vazbě v modelu existuje ekvivalent v systému“ [ I.Gros, 2003, s.18]. Ekonomické homomorfním
systémy
jsou
zobrazením.
povětšinou
Ekonomický
model
zobrazovány
tedy
zobrazuje
zjednodušený reálný model, který obsahuje pouze prvky a vazby,
jenţ
jsou
důleţité
pro
řešený
problém
[Josef
Jablonský, 2002]. Dle J. Jablonského ekonomický model musí obsahovat: o Cíl
analýzy
–
bez
určení
cíle
neexistuje
interpretovatelný výsledek. Cíl musí být definován jednoznačně, např. maximalizace zisku, minimální počet
kilometrů
v distribuční
cestě,
optimální
alokace skladů, nejmenší výrobní dávka atd. o Popis procesů, které v systému probíhají – myslí se tím procesy, které v reálném systému probíhají s určitou 15
intenzitou
a
které
mají
vliv
na
ekonomický
model.
Procesy
se
například
myslí
výroba určitého výrobku, o Popis činitelů, kteří ovlivňují proces výroby – realizace procesů je popsána a limitována mnohými veličinami,
které
je
moţné
měřit,
např.
čas,
mnoţství kusů apod. o Popis vzájemného vztahu mezi procesy, veličinami a cílem analýzy Model
můţe
mít
různé
znázornění,
např.
grafické,
číselné, verbální. Na ekonomický model bezprostředně navazuje matematický model.
16
3
Teorie modelování matematického modelu
Na
ekonomický
model.
Můţe
model se
bezprostředně
říci,
ţe
navazuje
matematický
matematický
model
převádí
ekonomický model do jazyku matematiky. Historie
matematického
modelování
u
nás,
v tehdejší
Československé socialistické republice, začíná v šedesátých letech
20.
století.
bezprostředně Výpočetní
Rozvoj
souvisí
technika
matematického
s rozvojem
umoţnila
modelování
výpočetní
urychlení
techniky.
řešení
náročných
matematických algoritmů a zároveň eliminovala moţnost chyby způsobené lidským faktorem. Ekonomický
model
řešeného
problému.
zapotřebí
zápis
je
Aby
numerické bylo
moţné
ekonomického
či
slovní
problém
modelu
vyjádření
vyřešit,
je
formalizovat.
O
Formalizaci se právě stará matematický model. Matematický model se následně řeší stanovenými postupy. Dle Jankulovského matematický model musí obsahovat: o Cíl
–
zpravidla
vyjádřen
jako
lineární
či
nelineární funkce n proměnných. o V ekonomickém aktivity,
modelu
které
intenzitou.
jsou
v procesu
Matematický
probíhají
model
přiřadí
proměnnou
a
Hodnota
proměnné
vyjadřuje
definovanou
definovány
následně
v ekonomickém
reálné
s určitou
těmto
aktivitám
hodnotu
proměnné.
intenzitu
aktivity
modelu
[Jankulovský,
2007]. Při stanovení proměnných je důleţité určit měrnou
jednotku,
[J.Římánek, 1994]
17
věcný
význam
a
dimenzi
o „
Obecně
řečeno,
proměnné
vyjadřují
neznámé
a
hledané úrovně, na nichţ jsou prováděny činnosti (uskutečňovány procesy).“ [J.Římánek, 1994, s.51] o Činitelé
vyjádřené
v ekonomickém
modelu
matematický model vyjádří jako soustavu lineárních rovnic, nelineárních rovnic, lineárních nerovnic anebo nelineárních nerovnic. o Lineární rovnice či nerovnice vyjadřují omezení úlohy. Na pravé straně rovnice či nerovnice stojí poţadované
mnoţství
vstupu
či
výstupu.
Na
levé
straně je potřebné mnoţství vstupu či výstupu. o Vazby mezi procesy definované v ekonomickém modelu se
matematickém
parametry.
18
modelu
vyjádří
neměnnými
4
Řešení matematického modelu
Řešení
matematického
technice
spíše
jen
modelu
je
technickou
díky
novodobé
záleţitostí.
počítačové
Lze
pro
něj
pouţít celou řadů definovaných postupů a metod.
4.1
Klasifikace disciplín operační analýzy
Modely
operační
ekonomického
analýzy
ţivota.
se
zabývají
Z tohoto
rozdílnými
důvodu
oblastmi
existuje
několik
různých modelů operační analýzy a postupem času se z nich staly
jednotlivé
samostatné
vědní
disciplíny
operační
analýzy. [Broţová, Houška, 2003], [Jablonský 2007] Jablonský disciplíny operační analýzy člení následovně: a. Matematické
programování
optimalizační
úlohy.
–
úlohy,
Patří
sem
které
řeší
lineární,
nelineární či dynamické programování, stochastické programování, [Broţová, Houška, 2003] b. Teorie
grafů
–
jedná
se
o
modely,
které
jsou
v praxi často uţívané. Často se tímto modelem řeší nalezení nejkratší distribuční cesty c. Teorie
zásob
zásobovacího
–
model,
procesu
a
který
se
zabývá
optimalizací
řízením
skladových
zásob. d. Teorie her – model, který se zabývá rozhodováním. Model se snaţí pro určité rozhodovací typy situací definovat
19
pouţitelnou
definici
optimálního
rozhodnutí
viz.
vězňovo
dilema
z makroekonomie.
[Maňas, 1983] e. Teorie hromadné obsluhy = teorie front – zabývá se systémy, které osahují požadavky a obslužné linky. Poţadavky
poţadují
realizují. front,
obsluhu
Alternativou
který
se
a
obsluţné
názvu
odvodil
linky
modelu
od
je
ji
Teorie
skutečnosti,
ţe
obsluţné linky vytvářejí fronty. [Jablonský, 2007] f. Vícekriteriální rozhodování – disciplína, která se zabývá řešením rozhodovacích úloh. Rozhoduje se mezi
variantami,
které
jsou
jiţ
k dispozici
a
které se hodnotí dle několika kritérií. Podstatou je
v\řešení
konfliktu
mezi
jednotlivými
protikladnými kritérii. [Jablonský 2007] g. Modely
obnovy
–
řeší
a
předpovídají
počty
jednotek, které v systému selţou a budou muset být v procesu nahrazeny. h. Markovské rozhodovací procesy – popisují dynamické systémy i. Simulace – nástroj pro analýzu sloţitých systémů. Na
počítači
se
simulují
ekonomické
procesy
a
porovnávají se s reálnými systémy. Při simulaci se mění jednotlivé parametry a následně se sledují změny
systému,
procesu.
Je
příslušného
za
účelem
zapotřebí softwaru.
optimalizace výkonných
Příslušný
poměrně drahý [ Jablonský, 2007].
20
takového
počítačů software
a je
5
Matematické programování
Úlohy matematické optimalizace dvojice autorů Walter-Lauber charakterizuje následujícími slovy: „ Pro řešení některých problémů
matematické
programování,
které
lze
stručně
charakterizovat jako úlohy hledání takového řešení prostoru přípustných řešení, které extremalizuje účelovou funkci, byla vtvořena řada speciálních algoritmů.“ [Walter-Lauber, 1975, s.71 ] Mezi speciální algoritmy patří: a. Metody lineárního programování b. Metody nelineárního programování c. Metody dynamického programování
5.1
Lineární programování
Název
lineárního
s programováním [Turzík, znamená,
počítačů,
2006].
souvislosti
programování Pojem
plánování
ţe
všechny
či
jak
nemá
je
nic
společného
dnes
všeobecně
vnímáno
programování
znamená
v této
rozhodování.
pouţité
Pojem
matematické
lineární
funkce
jsou
lineární. Je zapotřebí definovat účelovou (kriteriální) funkci. Jablonský definuje
v publikaci takto:
„
Cíl
Operační analýzy
výzkum je
účelovou
funkci
v matematickém
modelu
vyjádřen jako lineární funkce z=f(x), jejíţ extrém (maximum či minimum) je třeba nalézt. Tato funkce se označuje jako účelová nebo kriteriální funkce.“ [Jablonsky, 2007, s. 44]
21
V úlohách
lineárního
základních úloh:
programování
[ Turzík, 2006]
o V kanonickém tvaru o Ve standardním tvaru
5.1.1. Kanonický tvar V úloze se poţaduje určit: max(c1x1 + c2x2 + …..cnxn) nebo min(c1x1 + c2x2 + …..cnxn) (1) pro x1,…..,xn splňující podmínky: a11x1+a12+………..+a!nxn
≤ b1
a21x1+a22+………..+a2nxn
≤ b2
a31x1+a32+………..+a3nxn
≤ b3
am1x1+am2+………..+amnxn
≤ bm
x1, x2,…,xn ≥ 0 , kde cj,bi, aij, ……………..jsou reálná čísla (2) Úlohu lze stručně zapsat ve tvaru: max Σ cjxj Σ aijxj Xj ≥ 0,
≤ bi, i = 1,….,m i = 1,….,n. (3)
22
existují
2
typy
5.1.2. Standardní tvar V úloze se poţaduje určit: max(c1x1 + c2x2 + …..cnxn) nebo min(c1x1 + c2x2 + …..cnxn) (4) pro x1,…..,xn splňující podmínky: a11x1+a12+………..+a!nxn
= b1
a21x1+a22+………..+a2nxn
=b2
a31x1+a32+………..+a3nxn
= b3
am1x1+am2+………..+amnxn = bm x1, x2,…,xn ≥ 0 , (5) max Σ cjxj Σ aijxj
= bi, i = 1,….,m
Xj ≥ 0,
i = 1,….,n. (6)
5.1.3. Obecná úloha lineárního programovaní - převody Obecná
úloha
lineárního
programování
můţe
být
zadána
v
kanonickém či standardním tvaru. Kaţdou úlohu lineárního programování
lze
převést
z
kanonického
tvaru
na
tvar
standardní a ze standardního tvaru na kanonický tvar. Při převodu z kanonického tvaru na standardní tvar se pouţívá doplňkové proměnné xn+1, pro kterou platí: xn+1 ≥ 0 [Turzík, 2006].
23
Např:
a1x1+ a2x2 +a3x3………..+anxn ≤ b (7)
a1x1+ a2x2 +a3x3………..+anxn +anxn
+1=b
(8) Věta
1.1
[Turzík,
2006]
Nechť
je
dána
úloha
v
kanonickém tvaru max Σ cjxj Σ aijxj
≤ bi, i = 1,….,m
Xj ≥ 0,
i = 1,….,n
s proměnnými x1,…,xn. Zavede se m doplňkových proměnných a uvaţuje se úloha ve standardním tvaru max Σ cjxj Σ aijxj
= bi, i = 1,….,m
Xj ≥ 0,
i = 1,….,n.
s proměnnými x1,…,xn+m. Potom platí: Je-li x1,…,xn optimální řešení úlohy v kanonickém tvaru je x1,…,xn+m , kde Xn+I = bi – Σaijxj, i = 1,……,m, optimální řešení úlohy ve standardním tvaru.
V zadání úlohy se můţe hledat minimum nebo maximum. Úlohy je moţné mezi sebou převádět. Základem pro převod je Věta 1.2 [Turzík, 2006] Věta 1.2 Nechť funkce f definovaná na mnoţině M Rn má v bodě x M lokální maximum, resp. minimum. Pak funkce g definovaná na M předpisem: g(y)= -f(y) má v bodě x lokální minimum, resp. lokální maximum. 24
Dle této věty platí: Min {cTx: Ax≤b, x≥0} = - max { - cT: Ax≤b, x≥0} Proměnné
v úloze
lineárního
programování
mohou
být
omezené či neomezené. Kaţdá neomezená proměnná se nahradí 2 novými proměnnými. Převod je zaloţen na skutečnosti, ţe kaţdé reálné číslo x lze zapsat jako rozdíl dvou čísel, která jsou nezáporná, tj. x = x V
+
- x
kaţdé
proměnná
-
, x
+
úloze
bude
≥ 0, x
-
≥ 0
lineárního
nahrazena
programování
dvojicí
nezáporných
neomezená čísel
dle
uvedeného vztahu.
5.1.4 Lin-Kerninghan metoda Metoda větví a mezí je obecný algoritmus v problematice lineárního různých
programování optimalizačních
při
hledání
úkolů,
optimálních
zejména
řešení
v diskrétní
optimalizaci a kombinatorické optimalizaci. Princip
metody
spočívá
v systematickém
procházení
potencionálních řešení. Uţívají se horní a dolní hodnoty, které jsou optimalizovány [Ing. L. Rychetík,, CSc., 1968].
25
6
Input – output modely
Základní principy Input-output modelů byly definovány jiţ v roce 1758 ekonomem francouzského původu, Francoisa Quesnay, který ve své Ekonomické tabulce znázornil tok peněţních důchodů mezi jednotlivými třídami (mezi vlastníkem půdy – podnikateli
–
zaměstnanci
v
národním
hospodářství).
Modifikovaný model ekonomické tabulky pouţil I Karol Marx ve
své
publikaci
Kapitál
(Marián
Goga,
Input-output
analýza). Input-output modely neboli bilanční modely jsou však nejvíce spjaty se jménem W. Leontiefa a jeho publikace The Structure of American Economy 1919-1939. V knize byly popsány vztahy v reprodukčním procesu na národohospodářské úrovni. Pouţité matematické balance poté byly pouţity na vnitropodnikové úrovni [Ivan Gros, 2003]. Ivan
Gros
v
publikaci
Kvantitativní
metody
v
manaţerském rozhodování podnikové bilanční modely definuje: „
Bilanční
modely
formalizujeme
na
podnikové
i
vnitropodnikové úrovni varianty základních materiálových, energetických
nebo
hodnotových
vazeb
mezi
prvky
modelovaného systému, jejichţ realizace je podmínkou pro transformaci jeho vstupů na poţadované výstupy“ [I.Gros, 2003, s.31]. Bilanční procesu,
kde
algoritmizace
modely je
jsou
díky
bilančních
pouţity
na
input-output propočtů
úrovni
plánování
modelům
zajištěna
důleţitých
k vytvoření
plánu zásobování, distribuce, operativních výrobních úkolů, změn
ve
výrobě
či
pouţitých
surovin.
[I.Gros,
2003].
Bilanční modely jsou rovněţ důleţité k posouzení vlivu změn v materiálových tocích. Formalizovaný bilanční model je tedy matematický model tvořený
26
soustavou
rovnic
(zpravidla
lineárních
rovnic).
Cílem
zadaného
matematického
modelu
je
nalezení
hodnot
definovaných veličin ze zadaných parametrů. Základním nástrojem pro input-output modely neboli pro strukturní analýzu jsou symetrické input-output tabulky. Tabulky
jsou
pouţity
hlavně
k
popisu
technologicko-
ekonomických vazeb. V symetrické input-output tabulce jsou zobrazeny číselné vztahy mezi vstupy (náklady) jednotlivých odvětví a jejich výstupy (produkcí). Jednotlivé kroky bilančního modelu: o Identifikace jednotlivých prvků bilančního modelu o Identifikace vazeb bilančního modelu o Definice parametrů a proměnných bilančního modelu o Formulace bilančního modelu a jeho kvantifikace o Nalezení řešení bilančního modelu
6.1
Identifikace jednotlivých prvků bilančního modelu
V
bilančním
modelu
výrobního
podniku
jsou
jako
prvky
shledány suroviny vstupující do výroby, polotovary, obaly, energie, palivo, výrobky vstupující do výroby či výrobky vznikající
jako
meziprodukt,
který
můţe
být
pokračující
surovinou ve výrobním procesu anebo nemusí, katalyzátory atd. Je důleţité uvést jednotky jednotlivých surovin, aby získané výsledky měly vypovídací hodnotu. V rozsáhlých výrobách např. v chemických výrobách – výroba pneumatik je pouţito procesu agregace jednotlivých prvků, protoţe můţe být identifikováno aţ několik tisíc prvků. Agreguje se na základě společných identifikovaných rysů
27
či
vlastností,
které
pro
účely
bilančního
modelu
nejsou směrodatné např. prvky, ze kterých vznikají různé směsi.
6.2
Identifikace vazeb bilančního modelu
Vazby ve výrobním procesu pro účely bilančního modelu mohou být
identifikovány
z
jednotlivých
předpisů,
receptur,
postupů výroby. Je vhodné tento krok znázornit graficky se všemi tokovými veličinami a zároveň uvést směr toku.
6.3
Definice parametrů a proměnných bilančního modelu
Dle prof. Grose je ustálena praxe pouţívat pro vypočítávané mnoţství výrobků a polotovarů tři veličiny zabývající se produkcí
a
definovaná
spotřebou další
výrobků
veličina
či
polotovarů.
zabývající
se
Dále
je
mnoţstvím
materiálových vstupů: a. yj
- produkce j-tého výrobku, polotovaru určeného
ke spotřebě mimo bilancovaný systém, u podnikových procesů jde o poţadavky zákazníků b. xj
–
celková
produkce
j-tého
výrobku
nebo
polotovaru bez ohledu na další určení c. xij
–
spotřeba
i-tého
výrobku,
polotovaru
na
výrobu xj jednotek j-tého výrobku d. si
–
mnoţství
suroviny
potřebné
pro
splnění
poţadavků zákazníků e. Pro výpočet xij a sij jsou pouţity následující vztahy: 28
xij= aij . xj (9) si = sij . xj (10) kde aij – specifické spotřeby i-tého polotovaru sij – specifické spotřeby materiálových vstupů na jednotkové mnoţství j-tého výrobku, polotovaru. Jejich hodnoty
jsou
často
normovány
pro
definovaná
období.
Přesnost modelu je závislá na hodnotě sij.
6.4
Formulace bilančního modelu a jeho kvantifikace
Nejtěţší částí strukturní analýzy jsou předešlé kroky tj. správně definovat prvky a vazby v bilančním modelu. Pokud se
postupovala
zodpovědně
a
pečlivě
vlastní
formulace
bilančního modelu není obtíţná. Postupuje se ve 2 na sebe navazujících
etapách:
model
mezivýrobkových
vztahů
a
sestavení materiálových vstupů bilančního modelu.
6.4.1 Model mezivýrobkových vztahů Model
mezivýrobkových
kritéria,
aby
vztahů
mnoţství
je
zaloţen
vyrobených
výrobků
na
splnění
odpovídalo
mnoţství výrobků, které je poţadováno zákazníky [I. Gros, 2003].
Tedy
vytvářel
aby
zásoby,
nebyla které
nadvýroba, jsou
spojeny
protoţe s
by
podnik
náklady
navíc.
Zmíněné kritérium lze vyjádřit matematickým zápisem: xk
= xk1 + xk2 + xk3.........+ xkn (11)
29
Pokud do předchozího vztahu 11se dosadí vztah č. 9 z kapitoly 6.3 vznikne: xk
= ak1x1 + ak2x2 + ak3x3.........+ aknxn (12)
Celková balance mezivýrobkových vztahů má následující maticový zápis [Gros, 2003]: X1
= a11x1 + a12x2 + a13x3.........+ a1nxn
X2
= a21x1 + a22x2 + a23x3.........+ a2nxn
X3
= a31x1 + a32x2 + a33x3.........+ a3nxn
Xn
= an1x1 + an2x2 + an3x3.........+ annxn,
kde n je počet výrobků a polotovarů (13)
6.4.2 Materiálové vstupy do bilančního modelu Výrobní proces je limitován materiálovými vstupy, proto je důleţité sestavit matici pro materiálové vstupy. Postupuje se analogicky s modelem mezivýrobkových vztahů. Uvaţuje se d-tá surovina. Sd = sd1x1+ sd2x2+ sd3x3…..+ sdnxn, kde
n je počet vstupujících surovin (14)
Soustava rovnic vyjadřující bilancí všech materiálových vstupů je formulována: [I. Gros, 2003] S1 = s11x1+ s12x2+ s13x3…..+ s1nxn S2 = s21x1+ s22x2+ s23x3…..+ s2nxn S3 = s31x1+ s32x2+ s33x3…..+ s3nxn .
Sn = sn1x1+ sn2x2+ sn3x3…..+ snnxn
30
(15)
Modely č. 14 a 15 lze vyřešit v programu Excel. Pro řešení je výhodné modely č. 14 a 15 vyjádřit v maticovém tvaru: x
y
A
x
x1
y1
0
0
0
0
0
0
0
0
0
0
x1
x2
y2
0
0
0
0
0
0
0
0
0
0
x2
x3
y3
0
0
0
0
0
0
0
0
0 0,01
x3
x4
y4
0,03
0
0
0 0,64
0
0
0
0
x4
x5
= y5
0 0,09
0
0
0
0
0
0
0 0,02 * x5
x6
y6
0
0 0,07
0
0
0
0
0
0
0
x6
x7
y7
0
0
0 0,08
0
0
0
0
0
0
x7
x8
y8
0
0
0
0 0,41
0
0
0
0
0
x8
x9
y9
0
0
0
0
0 0,67
0
0
0
0
x9
x10 y10 0 0 0 0 0 0 0,76 Model mezivýrobkových vztahů – vlastní vyjádření
0
0
0
x10
+
s
0
B
x
s1
0
0
0
0
0
0
0
0
0
0
x1
s2
0,007
0
0
0
0
0
0
0
0
0
x2
s3
0
0
0
0
0
0
0
0
0 0,01
x3
s4
0,5
0
0
0 0,54
0
0
0 0,02
0 0,09
0
0
0
0
0
0
0 0,03 * x5
0
0
0
0
0
0
0
x6
0
0
0
0
0
0
x7
0
0
0
0
0
x8
0 0,67
0
0
0
0
x9
0
0
x10
s5
=
s6
0
0 0,07
s7
0
0
0 0,08
s8
0
0
0
0 0,41
s9
0
0
0
0
s10 0 0 0 0 0 0 0,76 0 Bilanční model spotřeby surovin – vlastní vyjádření
0
x4
matice A – čtvercová matice, která je tvořena měrnými spotřebami protoţe
jen
aij.
Matice
některé
obsahuje
polotovary
veliké
se
mnoţství
pouţívají
pro
nul, výrobu
jednotlivých výrobků. Prvky matice mají pouze nezápornou hodnotu. matice B – nemusí být čtvercová matice tvořena měrnými spotřebami
materiálových
vstupů
na
jednotlivé
výrobky,
polotovary. Prvky matice mají pouze nezápornou hodnotu.
31
vektor x – vektor celkové produkce všech výrobků xj. [I.Gros, 2003. Prvky vektory jsou nezáporné. vektor y – vektor všech produkcí určené k jiné spotřebě neţ ke spotřebě v modelovaném systému. Hodnota můţe být i záporná
a
to
v
případě,
ţe
ve
sledovaném
období
spotřebovávaná surovina bude vytvořená zásoba (o vytvořenou zásobu se musí sníţit mnoţství výrobku, které je potřeba vyrobit) [I.Gros, 20003]. vektor s – vektor poţadujících poţadavků na materiálové vstupy sj. [ I.Gros, 2003] tj. energie, suroviny Maticový zápis vzorců 13 a 15 jsou následující: X=y+Ax, Ax…..vlastní spotřeba uvnitř modelovaného systému Y…….produkce ke spotřebě mimo modelovaný systém x……..celková produkce výrobku, polotovaru (16) B.x=s (17)
6.5
Nalezení vlastního řešení bilančního modelu
Vychází se ze vzorce číslo 16 tj. X= y + Ax. Kdy je k dispozici n počet rovnic o 2n neznámých.Hledá se x. x= y + Ax x– Ax = y [E-A] x = y x =[E-A]-1 × y ………v tomto případě jsou známy poţadavky zákazníků, vyrobí se tedy, co je poţadováno (18)
32
E - jednotková matice x,y - vektory Pokud nejsou známy přesné poţadavky zákazníků, vzorec č. 18 se upraví na tvar: y =[E-A]-1 × x,
x,y - vektory (19)
Po vyřešení rovnic v program Excel je důleţité výsledky správně interpretovat a pouţít odpovídající jednotky.
33
7
Modely hromadné obsluhy
Systémy hromadné obsluhy mají různé úrovně struktury. Od nejjednodušších, kde je pouze jedna jediná linka aţ po sloţité několikastupňovité struktury (např. výrobní linka) [J.Jablonský, 2007]. Teorie
hromadné
obsluhy
zkoumá
systémy,
ve
kterých
dochází k uskutečnění obsluhy poţadavků, jeţ přicházejí do systému
[V.
Kořenář,
2010].
V
těchto
systémech
můţe
docházet ke vzniku front (k hromadění) z důvodu omezených kapacit linek. Tato skutečnost dala vzniku alternativnímu názvu teorie – Modely front [ Jablonský, 2007]. Modely front se snaţí celý proces analyzovat a zefektivnit takovým způsobem, aby vzniku front bylo předejito a zároveň aby nedocházelo k velikým prolukám mezi jednotlivými výrobními operacemi uvnitř výrobního procesu. V případech, ve kterých je moţné proluky či fronty nákladově ohodnotit je moţné proces optimalizovat. Teorie rozlišuje dva subjekty [V. Kořenář, 2010]: požadavky
–
od
zákazníků,
potřebují
obsluhu.
Zdroj
poţadavků lze uvaţovat za nekonečný i konečný. Nekonečný je většinou v případě jednoduchého systému např. poţadavky v bance, v supermarketu, protoţe registrace zákazníků je v tomto
případě
nemoţná
či
příliš
obsáhlá.
Konečný
zdroj
poţadavků je typický pro rozsáhlé struktury např. výrobní linky, které obsahují spočetně hodně strojů a zařízení. obslužná zařízení – poskytují obsluhu Model
má
převáţně
stochastický
charakter.
Přístup,
který se uţívá při řešení problém je shodný s principy, které jsou pouţívány v jiných disciplínách operační analýzy [ V.Kořenář, 2010]. 34
Systém hromadné obsluhy Příchod do systému
Obslužné linky Odchod ze systému
Zdroj požadavků
..... Fronta požadavků Realizace obsluhy
obr. 1 - Schéma hromadné obsluhy – J.Jankulovský 2007
Obr. 1 znázorňuje, ţe systémem hromadné obsluhy je myšleno
vše,
co
se
nachází
mezi
odesláním
poţadavku
zákazníka a odchodem ze systému. Jsou to tedy hlavně fronty poţadavků, které modely musí efektivně optimalizovat. Popis schématu hromadné obsluhy [ I.Gros, 2003]: Vstupní poţadavky na obsluhu vytváří vstupní proud m. V případě, ţe jsou obsluţná místa obsazena, se buď poţadavky řadí
do
fronty
anebo
se
míjejí
–
obsluţný
systém
se
ztrátami. S čekající frontou poţadavků se zavadí termín – disciplína
fronty,
jeţ
charakterizuje
způsob,
jakým
poţadavky vystupují z fronty a zařazují se zpět do procesu obsluhy. Disciplína fronty obsahuje několik způsoby obsluhy: o FIFO
(
first
in
first
out)
–
Poţadavky
jsou
obsluhovány v pořadí, v jakém do systému vstoupily [Gros, 1996].
35
o LIFO ( last in first out) – Poslední poţadavek je obslouţen jako první [Gros, 1996]. o PRI (priorita) – Pevné pořadí vstupu poţadavků není stanoveno.
K
obsluze
jsou
vybírány
poţadavky
dle
ohodnoceného stupně priority [ Kořenář, 2010]. o SIRO
(selection
vstupních
in
poţadavků
random není
order)
–
stanoveno.
K
Pevné
pořadí
obsluze
jsou
poţadavky vybírány náhodně [ Kořenář, 2010]. U vstupního proudu je při modelování důleţité popsat dobu
trvání
obsluhy
jednotlivých
poţadavků.
Lze
ji
povaţovat za náhodnou veličinu, protoţe je ovlivněna řadou náhodných jevů. V Empiricky zjištěném rozdělení dob trvání obsluhy
se
často
uţívá
principů
exponenciálního
zákonu
rozdělení pravděpodobnosti [Kořenář, 2010]. Další příchodů poţadavků,
důleţitá λ.
charakteristika
Charakteristika
které
vstupují
se
nazývá
popisuje
do
systému
intenzita
průměrný
počet
určité
časové
za
období. [Jablonský, 2007] Dle rozdělení dob obsluhy se rozlišují modely obsluhy: ke
klasifikaci
modelů
je
uţíváno
mezinárodně
standardizované označení [Jablonský, 2007; Kořenář 2010]: o D – deterministické rozdělení o M – exponenciální rozdělení o Ek – Erlangovo k-fázové rozdělení o GI – obecné nezávislé rozdělení o G – obecné rozdělení Např.M/M/1 znamená: system s exponenciálním rozdělením interval zařízením.
36
mezi
dobou
obsluhy
s
jedním
obsluhujícím
7.1
Exponenciální model jednoduché obsluhy
Nejjednodušší
model
procesu
hromadné
obsluhy
je
exponenciální model. Rozdělení náhodných četností neboli don trvání obsluhy poţadavků má charakter exponenciálního rozdělení. Jedná se o otevřený systém s jedním obsluţným zařízením. [V. Kořenář, 2010]. Je uvaţován předpoklad, ţe v případě existence front poţadavky čekají ve frontě na obsluhu a jsou zpracovány v pořadí, ve kterém přišly. Odvození
charakteristik
modelu
[V,
Kořenář,
2010],
[Gros, 1996]: Předpoklad:
Poissonovo
rozdělení
počtu
vstupujících
poţadavků, n počet jednotek v interval T=(0, t) Pn(T)= (λT)n × (n!)-1 × e-λT (20) A
zároveň
je-li
rozdělení
dob
mezi
příchody
t
exponenciální rozdělení, pak je hustota vyjádřena Q(t)=λe-
λT
(21) Dalším
uvaţovaným
předpokladem
je
fakt,
ţe
proces
hromadné obsluhy má charakter Markova procesu. Míní se tím, ţe
stav
jednotky
nezávisí
na
jiném stavu
neţ
na
stavu
předešlém. Sn
–
stav,
ve
kterém
je
n
jednotek.
V
intervalu
(t,t+Δt) jsou uskutečněny pouze následující přechody: (Kořenář, 2010) S0→ S0, S0 → S1, S1 → S0 …………… výchozí stav Sn→ Sn, Sn → Sn+1, Sn+1 → Sn-1 ……. Pro n ≥ 1.; 37
Pravděpodobnost
přechodů
exponenciálního
rozdělení
mezi stavy, které spolu nesousedí, jsou nekonečně malé, protoţe
pravděpodobnost
v časovém
intervalu
pravděpodobnost
obsluhy
Δt
pn(t)
je
více
moţné
určuje
jak
jedné
zanedbat.
skutečnost,
jednotky
Nepodmíněná
ţe
se
systém
nachází v okamţiku t ve stavu Sn. [Kořínek, 2010] Pravděpodobnost příchodu jednotky v časovém intervalu (t, t+ Δt) je značena λΔt. Pravděpodobnost, ţe obsluha bude ukončena
v intervalu
(t,
t+
Δt)
je
značena
μdt.
Po
uplynutí doby Δt, se tedy pravděpodobnost pn(t) změní na pn(t+ Δt). Intenzity přechodu mezi jednotlivými stavy jsou vyjádřeny veličinami λ a μ. Po vyjádření všech důleţitých stavů
tzv.
stavy,
je
pravděpodobností moţné
přechodů
nadefinovat
matici
mezi
jednotlivými
pravděpodobností
P
[Kořenář, Stochastické procesy, 2010]: 1-λΔt P=
λΔt
λΔt 1-λΔtλΔt
0 ….
λΔt ….
0
…..
0
0
λΔt 1-λΔtλΔt
……
0
0
…… …..
0 …….
0 ……
….
Popis významu matice: o Výrazy
na
úhlopříčce
odpovídají
pravděpodobnostem
odpovídají
pravděpodobnostem
setrvání ve stavu o Výrazy
nad
úhlopříčkou
příchodu poţadavky o Výrazy pod úhlopříčkou odpovídají pravděpodobnostem o ukončení obsluhy o Nulové
prvky
vyjadřují
fakt,
ţe
neexistuje
moţnost přechodu mezi nesousedícími stavy
38
jiná
Vektor
nepodmíněných
pravděpodobností
pn(t)
je
v okamţiku t dán výrazem: p(t)=[p0(t), p1(t),….,pn(t),…]. Po uplynutí intervalu Δt platí rovnice [Kořenář, 2010]: p( t + Δt)=p(t)×P (22) Po
dosazení
pravděpodobností
do
vztahu
č.
22
vznikne
soustava rovnic [Kořenář, 2010]:
p0(t+ Δt)=(1-λΔt) p0(t )+ μΔtp1(t),
n=0
p0(t+ Δt)= λΔtpn-1(t) + (1-λΔt-μΔt)pn(t) + μΔtpn+1(t), n≥1. (23) Přechod k limitě pro Δt → 0 : ,
n = 0 ),
n ≥ 1 (24)
Soustava lineárních diferenciálních homogenních rovnic č. 24 se nazývá Erlangova soustava.
Řešením soustavy č. 24
se určí pn(t) jako funkce parametrů μ a λ. Pro ulehčení výpočtu se nebude soustava integrovat, ale bude se zkoumat stabilizace systému, tzn. zda se systém po určité dlouhé časové době stabilizuje, neboli zda přestane být systém závislý na čase a na výchozích podmínkách. Podmínka stabilizace systému [Kořenář, 2010] : n = 0,1,…. (25) Pokud
je
podmínka
č.
25
splněna,
soustavě diferenciálních rovnic č. 24 pro
potom
v
t → ∞ se budou
blíţit k nule a je moţné výraz zjednodušit na:
39
derivace
λp0
=
μp1
(λ + μ)pn
n = 0 =
λpn-1 + μpn+1
n ≥ 1. (26)
Po rozepsání rovnic č. 26 vznikne: P1 = P2 = Pn= (27) Součet pravděpodobností je roven 1 [ J.Pavlík, 2005]: , tedy:
1-p0 = p0
λ > μ (28)
Vznikne [Kořenář, 2010] P0 = 1 -
= 1 – ς, (29)
ς......průměrná intenzita provozu, neboli vytíţení systému hromadné obsluhy ς =
40
7.1.1 Základní charakteristiky exponenciálního sytému [Kořenář, Stochastické procesy, 2010], [Gros, Kvantitativní metody v manaţerském rozhodování] o
Průměrný
počet
poţadavků
v systému-
frekventovaný
ukazatel systému
(30) nebo
(31) o Průměrný počet požadavků ve frontě – zákazník si někdy přeje znát tuto charakteristiku ) (32) nebo
(33) o Průměrná doba strávená v systému z Littleovy formule se dostane:
41
(34)
8
Počítačové simulace
Charakteristika nedostatečná
klasických
dynamičnost
modelových
aţ
postupů
statičnost
je
[Gros,
jejich
2003].
V
klasických modelových postupech se přijímají rozhodnutí na předem určené časové období. V praxi však tento přístup není
v
neustále
ţádném se
zvyšujících
případě
zvyšujícím se
nároků
postačující.
V
tempu
neustálých
na
růstu
přesnost
současnosti
řízení,
při
změn
je
a
nezbytné
zachytit dynamiku sledovaného či řízeného systému. Zmiňovaná metoda simulace prochází neustálým vývojem a to
hlavně
díky
rychlému
vývoji
výpočetní
techniku
a
informačních technologií a zejména úzce specializovaných softwarových produktů, na jejímţ vzniku se podílelo veliko mnoţství expertů. V současnosti tedy mluvíme o počítačové simulaci. Díky tomuto faktu, je tato metoda široce dostupná vysokému
počtu
řídících
pracovníků
na
různých
úrovních
řízení a v různých oborech výroby produktu či sluţeb. Počítačové
simulace
tedy
znázorní
chování
reálného
systému na počítači. Pan prof. Ivan Gros ve své publikaci Kvantitativní
metody
v manaţerském
rozhodování
(2003)
simulace definuje následovně: „ Simulace je proces tvorby logicko-matematického modelu reálného objektu, systému na něm
definovaného,
velkého
mnoţství
nebo
procesu
experimentů
rozhodování
s ním,
jejichţ
a
realizace cílem
je:
[Gros, 2003, s. 380] o popis systému, o poznání jeho funkce, o odhad jeho budoucího chování, o nalezení řešeného problému, který mnohdy ústí do o návrhu a ověření funkce nové struktury systému.“ 42
Pracovní
tým,
který
se
simulacemi
zabývá,
musí
být
sloţen z velikého mnoţství specialistů, protoţe sestavení simulačního modelu vyţaduje výbornou znalost modelovaného procesu. Zásadní
vlastností
simulovaného
systému
je
jeho
neuniverzálnost. Tímto pojmem je myšlen fakt, ţe sestavený model není aplikovatelný na další modelu, ale je pouze aplikovatelný
na
určitý
model,
pro
jehoţ
potřeby
byl
simulační model sestaven. Další vlastností dle prof. Grose je nutnost identifikovat a následně vybrat takové proměnné, které
jsou
pro
správnou
funkčnost
modelu
nezbytné,
a
nepracovat s proměnnými, které na daný proces nemají ţádný či zanedbatelný vliv.
8.1
Metodika tvorby počítačových simulačních modelů
Sestavení počítačového simulačního modelu zahrnuje několik na sebe navazujících kroků: o Formulace
cíle
–
tomuto
kroku
je
potřeba
věnovat
mimořádnou pozornost. Správná formulace cíle usnadní konkrétizaci poţadavků na výstupy. o Stupeň podrobnosti – porobnost modelu musí být taková, aby
výstupy
splňovaly
zadání
formulovaného
cíle.
Podrobnost by neměla být větší. o Rámec modelu – jsou tím myšleny podmínky (hranice), ve kterých má vytvořený model pracovat. Pokud je rámec modelu příliš široký, sniţuje se tím podrobnost modelu
43
9
Řízení zásob
Řízení zásob pojednává o tom, kolik, kdy a čeho ve výrobním procesu objednávat a posílat dále. Na problematiku účelného skladování se naráţí téměř na kaţdém kroku. Lidé potřebují, aby
vše
bylo
Dosáhnout
ve
těchto
správném podmínek
mnoţství, je
hlavní
kvalitě úkolem
a
včas.
skladového
managementu. V dnešní době se můţe hovořit o úspěšném zvládnutí management výrobních a zároveň provozních činností, aniţ by se nevěnovala dostatečná pozornost řízení zásob.
Existuje
pro to několik nemálo důvodů, mezi něţ patří především skutečnost, ţe zásoby reprezentují veliké mnoţství nevhodně uloţených finančních prostředků. [Kavan, 2002]. Velikost finančních dosahuje
prostředků, od
10
%
do
které
jsou
vázány
25
aktiv
podniku,
%
v zásobách, coţ
není
zanedbatelná výše. Tedy I nepatrné sníţení zásob v podniku můţe
mít
významný
ekonomický
efekt
a
zároveň
ovlivňuje
úroveň sluţeb zákazníkům. [Gros, 1996].
9.1
Význam zásob
Zásoby jsou důleţitou sloţkou pro podnik. Zde je několik argument, které jsou pro jejich drţení [Kavan, 2002]: o Vyhovět předpokládané poptávce, jeţ prozatím není o Vzhledem k nepravidelné poptávce vyhovět poţadavkům rovnoměrné výroby o
Odděluje výrobní a distribuční sloţku [Gros, 1996]
o Usnadňuje flexibilitu o Chrání
mít
zákazníka 44
co
nejméně
neuspokojených
poţadavků
od
o Zhromadňuje výrobu a umoţňuje vzniku souboru zakázek a výrobních dávek o Brání
růstu
cen,
jelikoţ
souvisí
s
kvantitativní
slevou
9.2 Za
Členění zásob
zásoby
je
polotovary,
povaţován:
výrobky,
materiál,
zvířata
a
nedokončená
zboţí.
výroba,
[Louša,
2007]
Z účetního hlediska zásoby představují oběţný majetek. Materiál představuje nakoupené zásoby do spotřeby. Do této skupiny jsou řazeny: suroviny, pohonné a mazací hmoty, náhradní díly, ruční nářadí a jiné drobné předměty postupné spotřeby,
které
nejsou
řazeny
do
kategorie
dlouhodobého
majetku. [ Rubáková, 2007] Nedokončená polotovarů, polotovarů
výroba
které
je
byly
dodávaných
pojem
vyrobeny
v rámci
pro
zásobu
vlastních
v předchozí
jedné
firmy,
fázi,
které
a
jsou
dočasně, při neplánovaném či plánovaném přerušení výrobního procesu,
skladovány
v příručních
skladech
ve
výrobních
jednotlivých
meziskladech, výrobních
popř.
středisek
[Gros, 1996]. Hotové výrobky jsou výsledkem výrobního procesu. Jsou převzaty od výstupní kontroly jako výrobky určené k dodávce odběrateli [G. Tomek, V. Vávrová, 2007]. U zvířat jsou míněna ta ve výkrmu či mlada chovná zvířata. Dále pak koţešinová zvířata, ryby, včelstvo, hejno slepic apod. Za zboţí jsou pokládány movité věci pořízené za účelem dalšího následného prodeje v nezměněné podobě [V. Rubáková, 2007].
45
9.3
Funkce zásob
Zásoby
drţené
na
jednom
místě
drţené
na
jednom
místě
logistického řetězce mají několik sloţek. o Za běţnou zásobu je povaţována ta část zásob, která se mění
v čase
a
jejíţ
velikost
se
s časem
mění
a
velikost hlavně závisí na způsobu jejího doplňování a průběhu její spotřeby. o
Havarijní zásoba je tvořena tam, kde by nedostatek materiálu
mohl
způsobit
závaţné
poruchy
v celém
výrobním procesu. o Technická zásoba je takové mnoţství materiálu, které má pokrýt potřebu nezbytných technologických poţadavků na přípravu materiálu před jeho pouţitím ve vlastním výrobním procesu transformace zásoby na výrobek. Tato zásoba musí splňovat parametry technologických zásad [M. Synek, 2007]. o U zásob surovin nebo výrobků v přepravních zařízeních jako
jsou
ještě 1996].
46
plynovody,
rozlišují
zásoby
ropovody, výrobků
produktovou na
cestě
aj.
[I.
se
Gros,
10
Systémy řízení zásob položek s náhodnou proměnlivou poptávkou v čase Při řízení zásob je důleţité respektovat vedle náhodných změn
poptávky
zásoby
rovněţ
neprobíhá
skutečnost,
rovnoměrně
ţe
spotřeba
v určitém
vytvořené
časovém
úseku.
Suroviny, polotovary i výrobky jsou ze skladu expedovány po určitých
jednorázových
mnoţstvích
a
jen
v případě
kontinuální výroby lze pokles zásoby přijmout. V takových případech je potřebné zvolit postup, kterým je
moţné
jednorázová
rozhodovacích
aktů
rozhodnutí
v čase,
nahradit
posloupností
umoţňují
korigovat
která
a
upravovat předcházející chybná rozhodnutí podle měnící se situace. Pro v čase
řízení
je
opět
zásob
v podmínkách
potřeba
najít
měnící
odpověď
na
se
spotřeby
dvě
základní
otázky: o Kdy se musí zásoby doplňovat o V jak velikých dávkách se musí zásoby doplňovat Existují
dvě
moţnosti,
jak
nalézt
odpověď
na
první
otázku: o Na ose y je určena nějaká spodní mez xs, tzv. spodní objednávací úroveň, nebo signální stav zásob. Jakmile poklesne skutečný stav pod stanovenou objednávací mez, je
to
okamţitý
signál
pro
doplnění
zásob.
Takto
pracují systémy označené jako Q systémy. Symbol Q je pouţit
47
proto,
ţe
většinou
je
doplňovaná
zásoba
konstantní
velikosti
objednávek
o
velikosti
Q
[I.
Gros, 1996]. o Číselná
osa
je
rozdělena
na
intervaly
o
stejné
velikosti a stejné šířce ΔT, např. týden, měsíc. Kaţdý vybraný den v týdnu, např. kaţdý pátek, je zjištěn skutečný
stav
mnoţství
Q=
objednávací
zásob xh
–
mez.
x
na
x,
Tyto
skladě
přičemţ systému
a
xh
je
je
jsou
objednáno
tzv.
značeny
horní jako
P
systémy [I. Gros, 1996] Z obou dvou řešení je vidět, ţe úspěšná funkce obou systémů
řízení
je
závislá
na
správném
stanovení
spodní
objednávací úrovně či horní objednávací úrovně [I. Gros, 2003].
10.1 Q Systémy Tímto
systémem
je
nepřetrţitě
monitorována
úroveň
zásob
kaţdé poloţky. Funkce systému je taková, ţe je objednáváno v různých
časových
nakupované
poloţky.
okamţicích
stále
Výhodou
systému
Q
stejné je
mnoţství
nepřetrţitá
znalost stavu zásob kaţdé poloţky a rovněţ moţnost stanovit ekonomické
mnoţství
Q.
Nevýhodou
Q
systému
jsou
vyšší
náklady [M. Kavan, 2002]. Kritickým časovým úsekem, tzv. intervalem nejistoty, pro funkci systému jsou termíny vyřízení objednávek t0. V nich
můţe
dojít
k předčasnému
takový
stav
nenastal,
je
vyčerpání
nezbytné,
aby
zásoby. signální
zásobil schopen pokrýt o Poptávku po poloţce po t0 časových jednotek o Případné náhodné výkyvy v poptávce
48
Aby stav
K tomu je třeba určit rozdělení pravděpodobnosti f(s), náhodné
poptávky
s jednotek
po
dobu
t 0,
odhadnout
její
střední hodnotu a směrodatnou odchylku. Obvyklým zdrojem informací jsou údaje o průběhu poptávky si za dostatečně dlouhé uplynulé období T. Výhodné je zatřídění dat např. data o denní poptávce do tabulky rozdělení četností. Z ní pak lze určit poţadované hodnoty [Gros, 1996]
(35)
(36)
ni……četnosti hodnot v jednotlivých intervalech si….středy intervalů Znalost těchto charakteristik umoţňuje určit velikost poptávky po poloţce během termínu vyřízení objednávky jako součin: (37) Pro pokrytí náhodných výkyvů v poptávce je ještě nitné určit potřebnou výši pojistné zásoby xp. K tomu je potřeba otestovat,
zda
náhodná
poptávka
rozdělení
pravděpodobností.
rozdělení
pravděpodobností,
vyhovuje
K tomu které
je bylo
normálnímu
třeba
empirické
získáno
analýzou
poptávky za uplynulé období, vyrovnat. Nejdříve se vypočítají normované proměnné normálního rozdělení pro horní hranice intervalů ve tvaru [Gros, 1996]
(38)
Naleznou
se
hodnoty
distribuční
funkce
normálního
rozdělení pro horní hranice intervalů ve tvaru [Gros, 1996] = 49
-
(39) Výpočet teoretické četnosti [Gros, 1996]
(40) Výpočet hodnoty rozdělení [Gros, 1996].
(41) Ve
statistických
tabulkách
kvantilů
rozdělení
kvadrát lze nalézt pro zvolenou hladinu významnosti
-
χ pro
praxi 95% - počet stupňů volnosti c-3. Kde c je počet intervalů, příslušný kvantil q. Pokud
bude
platit,
ţe
vypočtené
χ
≤
q,
nelze
předpoklad normality zamítnout. Pokud odhadnout
vyhovuje výši
poptávka
pojistné
normálnímu
zásoby
–
zatím
rozdělení, bez
ohledu
lze na
náklady spojené s jejím udrţováním – na hodnotu (42) Pokud je moţné určit typ rozdělení pravděpodobnosti poptávky, lze zapsat sumu nákladů spojených s pořizováním poloţky,
jejím
skladováním
a
případnými
ztrátami
z nedostatku poloţky na skladě jako funkci pojistné zásoby a průměrného dodacího cyklu. Pořizovací
náklady
jsou
formulovány
1996]
(43)
50
vztahem
[Gros,
Náklady
na
udrţení
běţné
zásoby
na
skladě
[Gros,
1996].
(44) Náklady na udrţení pojistné zásoby [Gros, 1996].
(45) Ztráty vzniklé z případného nedostatku zásob na skladě [Gros, 1996].
Kde xs= xp + t0 (46) Hodnota
integrálu
představuje
pravděpodobnost,
ţe
spotřeba bude větší neţ stanovený signální stav zásob, nz je
uţ
jednou
v modelu
pouţitý
odhad
ztrát
spojených
s nedostatkem zásob, podíl T/tc je počet dodacích cyklů, situací, v nichţ k nedostatku zásob můţe dojít. Funkce pak má tvar [Gros, 1996]
(47)
Derivace funkce podle
se poloţí rovna nule a vznikne
výraz [Gros, 1996]
(48) 51
Derivace funkce podle xp se opět poloţí nule a vznikne výraz [Gros, 1996]
(49) Dosadí-li se do rovnice číslo 49 za tc z rovnice 48 a po dosazení xs=xp +t0 vznikne následující rovnice
(50) Z rovnice číslo 50 je potřeba vhodnou metodou určit výši
pojistné
zásoby
uţ
při
respektování
nákladových
kritérií. S výhodou lze vyuţít opět normovaných proměnných normálního
rozdělení.
Stačí
dosadit
do
vztahu
pro
neomezovanou proměnnou [Gros, 1996]
(51) Za
hodnotu
pravděpodobnosti
s,
pro
f
a
kterou
je
distribuční
potřeba funkci
F,
znát
hustotu
lze
dosadit
[Gros, 1996] S= xs= xp + t0
=
kσs + t0 (52)
Pak
se
dostane
rovnice
pro
t0=1
(za
se
dosadí
průměrná spotřeba během objednacího termínu),[Gros, 1996]
52
u =
= k (53)
Protoţe
mezi
hustotami
pravděpodobností
původních
hodnot f a normovaných proměnných platí vztah [Gros, 1996]
(54) Postupným dosazováním se nalezne takové k, pro které bude rovnice platit. Z něho se pak relativně lehce určí velikost pojistné zásoby [Gros, 1996] xp = k (55) Jejím dodacího
dosazením cyklu
do
rovnice
tc, z něhoţ
č.
počet
49
se
nalezne
objednávek
jako
délka podíl
o=T/tc a následně velikost objednávek Q=S/o.
10.2 P - systémy Fyzický
součet
v pravidelných
skladovaných
intervalech
poloţek
(týdně,
je
prováděn
měsíčně,..),
s cílem
rozhodnout, kolik které poloţky objednat na příští období. Po kontrole se provede prognóza poptávky na příští období, aby bylo moţné se rozhodnout, jaké mnoţství objednávky se objedná. Výhodou systému je jednoduchost a nízké náklady. Mezi
nevýhody
zásob
mezi
systému
periodami
patří
nedostatečná
nebo
potřebná
kontrola
zabezpečení
stavu proti
moţnosti vzniku nedostatku. [M. Kavan, 2002] U P - systémů jsou objednávky prováděny předem ve stejných časových okamţicích různá mnoţství nakupovaných poloţek. Interval nejistoty je u tohoto systému podstatně 53
delší. Jestliţe se v jednom termínu objedná zboţí, které není dostatečné, chyby mohou být napraveny teprve v dalším pevně stanoveném termínu. Interval nejistoty pak bude roven součtu průměrného termínu vyřízení objednávky a průměrného dodacího cyklu. Horní objednací úroveň je rovna xh=xp
+
(56) Při sestavování nákladové funkce, která umoţní určit řídící veličiny systému, se naráţí na problém, spočívající v tom, ţe se nezná průměrná délka dodacího cyklu, která by byla potřeba pro charakteristiku rozdělení pravděpodobností poptávky v celém intervalu nejistoty rovném součtu
.
[Gros, 2003] Je
moţné
binomické, nalezne
konstatovat,
Poissonovo
průměrná
ţe
apod.
spotřeba
pro
lze
a
normální
postupovat
směrodatná
rozdělení, tak,
odchylka
ţe ss
se pro
nějaké předem stanovené období a pak je moţné psát, ţe spotřeba v období k-krát delším je rovna k odchylka σs předpokladu
a směrodatná
Hustota pravděpodobnosti je rovna řízení
poptávky
normálním
. Za
rozdělením,
je
nákladová funkce
(57) Další Problém
postup můţe
nastat
pravděpodobností.
54
výpočtu při
je
podobný
naznačeném
jako
u
odhadu
Q-systému. rozdělení
11 Za
Teorie grafů
zakladatele
v roce
1737
grafu řešil
je
povaţován
úlohu,
Leonard
Euler,
který
projít
sedm
mostů
jak
v Konigsbergu, přičemţ kaţdý most můţe být projit pouze jednou, a vrátit se zpátky do výchozího bodu. Přibliţně o sto
let
později
Gustaf
Kirchoff
formuloval
Kirchhoffovy
zákony, které popisují elektrický jev ve fyzikální chemii. Teorie grafů se zabývá vlastností grafů. Grafy jsou tvořeny
vrcholy.
znázornění
grafu
Vrcholy je
jsou
spojeny
mnoţina
bodů
hranami. spojených
Obvyklé čárami.
Struktury a úlohy z různých oborů mohou být reprezentovány právě grafy. Graf je formálně uspořádán dvojicí mnoţiny vrcholů V a mnoţiny hran E: G = (V, E) Definice grafu: „ Graf G je dvojice (V,E), kde V je mnoţina a E je mnoţina některých dvojic prvků mnoţiny V. Prvky mnoţiny V nazýváme vrcholy grafu G a prvky mnoţiny E hrany grafu G. Je-li E mnoţina uspořádaných dvojic prvků z V, říkáme, ţe graf G je orientovaný. Je-li E mnoţina neuspořádaných
dvojic
prvků
z V,
říkáme,
ţe
graf
G
je
neorientovaný“[ Doc. RNDr. Daniel Turzík, 2006, s.65]. Struktura grafu bývá někdy rozšířena o ohodnocení hran či vrcholu (neboli je přiřazena váha, která reprezentuje např.
počet
ujetých
kilometrů,
kilogramy
spotřebované
suroviny či čas trvání jedné výrobní operace). Výstupem takového přiřazení vah je model skutečné sítě.
55
11.1 Kostra grafu Kostrou zároveň
grafu
je
stromem.
míněn
Stromem
faktorový se
podgraf,
nazývá
graf,
který který
je je
neorientovaný, souvislý a neobsahuje ţádnou kruţnici. Jedná se o souvislý graf, který obsahuje vrcholy původního grafu Pro další vysvětlení problematiky je důleţité uvést několik pojmů: o Strom - „ Neorientovaný graf nazýváme stromem, jestliţe je souvislý a neobsahuje ţádnou kruţnici. Kaţdý strom s alespoň dvěma vrcholy má alespoň dva vrcholy stupně právě 1“ [Doc. RNDr. Daniel Turzík, 2006, s. 72]. U stromu je v platnosti, ţe mezi kaţdými dvěma vrcholy existuje cesta, kaţdá hrana je mostem a ţe počet hran ve stromu je o jeden počet niţší neţ je počet vrcholů. o Minimální
kostra
–
kostra
grafu,
která
má
minimální
součet ohodnocení hran. Pro vyhledání minimální kostry grafu existuje několik algoritmů. V této práci bude uveden algoritmus, který se nazývá Kruskallův algoritmus a jeţ je někdy znám pod pojmem hladový algoritmus. Kruskallův algoritmus je sloţen z po sobě následujících kroků [ Kruskal, 1956]: a. Vytvoření
vzestupné
posloupnosti
hran
dle
jejich
ohodnocení. Pokud se některých hran vyskytne stejné ohodnocení, nebude vzájemné pořadí mezi nimi důleţité. b. Ze
vzestupné
s minimálním
posloupnosti ohodnocením.
úseků
je
Podmínkou
vybrán je,
ţe
úsek nesmí
s předchozími vybranými úseky do kostry grafu vytvořit kruţnici) c. Algoritmus je u konce, pokud je počet zařazených hran do kostry větší neţ n-1. Pokud je počet zařazených 56
hran do kostry menší neţ n-1, je nutné pokračovat v předešlém kroku č. 2. Symbolem n je míněn počet vrcholů grafu.
57
12
Formulace obecného dopravního problému
Distribuční úlohy tvoří specifickou skupinu rozhodovacích situací, jejichţ řešení vede k formulaci úloh lineárního programování. Úlohy jsou formulovány následovně [Gros, I., 2003]: o Klasické způsob
dopravní přepravy
úlohy
–
výstupů
hledá
se
(výrobků
nejvýhodnější či
sluţeb)po
zákaznických centrech. o Rozšířené dopravní úlohy – je řešen problém distribuce výstupů, které jsou distribuovány v několika úrovních (na sebe navazujících systémech) např. svoz výrobků do centrálního skladu a jejich následný odvoz do sítě maloobchodů či prodejen. o Přiřazovací úlohy – přiřazují se jednotlivé pracovní úkony na jednotlivá pracovní stanoviště Obecné Řešitele
distribuční
v tabulkovém
úlohy
lze
procesoru
efektivně Excel.
řešit
Tohoto
pomocí
řešení
se
uţívá pro malé anebo střední podniky. Pokud se jedná o velké podniky, algoritmy se modifikují např. modifikovaná simplexová metoda
12.1
VAM metoda
Synonymen pro VAM metodu je Vogelova aproximační metoda. Je řazena mezi základní metody při řešení dopravního okruţního problému. Vogelova aproximační metoda zdůrazňuje diference jednotlivých sazeb.
58
Pro kaţdý řádek a sloupec je vypočten rozdíl neboli Vogelova
diference.
Princip
metody
spočívá
ve
volbě
nejkratší trasy v řádku s největší Vogelovou diferencí a jsou ohodnocena sazbou. Následně je vyřazena trasa, která předčasně uzavírá okruh. Tento způsob je opakován, dokud nejsou všechna místa zařazena v okruhu. V případě, ţe jsou nalezeny
řádky
se
stejnou
Vogelovou
diferencí,
jsou
obsazena nejniţší sazbou [L. Rychetník, 1968]. Výsledkem této metody jsou velmi dobré výstupy, kdy odchylku účelové funkce od optimálního řešení je moţné zanedbat. Postup sestavení VAM metody: o V kaţdém řádku a sloupci se vypočte Vogelova diferenciace tj. rozdíl mezi dvěma nejniţšími sazbami v příslušném řádku či sloupci) o Vyhledá se řada, u které v předchozím kroku byla nalezena nejvyšší diference v řádku. V této řadě je vyhledáno pole s nejniţší
sazbou,
které
se
obsadí
maximálním
mnoţným
objemem přepravy. Pokud je nalezeno více jak jeden řádek s maximální zjištěna
diferencí,
nejniţší
je
sazba,
ze
vybrána všech
řada,
ve
které
je
řad.
Na
pozorovaných
vybrané je pole je umístěn největší moţný maximální objem přepravy. o Řada či sloupec, ve kterém jiţ byla kapacita či maximální poţadavek vyčerpána se jiţ při přepočítávání sazeb a řad nebere v úvahu. o Jsou
postupně
hodnotám.
59
obsazena
pole,
která
odpovídají
zbylým
13
Okružní dopravní systém
Alternativní název pro okruţní dopravní problém je „problém obchodního
cestujícího“.
obchodního
cestujícího
obtíţnost
jeho
řešení,
Typickou
je
jeho
pokud
se
vlastností
problému
snadná
formulace,
v úloze
nachází
ale
vysoký
počet dopravních uzlů. Jedná se o úlohy, jejímţ úkolem je nalézt nejlepší způsob dopravy nikoliv izolovaným spojením dvojic
míst,
ale
spojením
okruţním,
tzn.
sestavení
posloupností všech míst tak, aby se v ní kaţdý bod vyskytl právě
jednou.
Pouze
počáteční
bod
se
v uzlu
vyskytne
dvakrát, protoţe se objeví na začátku a na konci uzlu, aby se
jednalo
o
okruţní
dopravní
systém.
Pro
uvedenou
posloupnost musí být součet sazeb minimální. Z hlediska zadání výchozích podmínek existují dva typy dopravních úloh: o Jednostupňová
(dvourozměrná)
dopravní
úloha
–
od
obecného vyjádření dopravní úlohy se liší tak, ţe se její omezující podmínky rovnají. o Víceokruhový
dopravní
jednookruhového
problém
dopravního
–
úkolu
vznikne o
rozšířením
podmínky
(často
kapacitní podmínky), které zapříčiní, ţe jeden okruh není dostačující. Kaţdé místo má konkrétní poţadavek na
kapacitu
kapacitu
okruhu
a
zároveň
jednotlivých
okruhů.
je
zadána
celková
Přesáhne-li
suma
poţadavků jednotlivých míst kapacitu jednoho okruhu, musí být vytvořen další okruh.
60
13.1 Obecný návrh postupu řešení o Existuje m bodů (uzlů). Nejmenší počet spojnic, jimiţ lze uzavřeným okruhem jednotlivé body propojit je právě m. o Do bodu jedna cesta vstupuje (spotřebitel) a jedna cesta z něj vystupuje (dodavatel) o Matice M. Hledá se m cest tj. obsazených polí. V klasické dopravní
úloze
existuje
M2
moţných
cest.
Musí
se
ale
vyloučit prvky hlavní diagonály, aby byla vyloučena zpětná vazba. Bude tedy existovat v okruţní dopravní úloze (m2 – m) cest. o Musí být eliminována moţnost duplicity cest. Duplicita cest – jeden úsek je znázorněn dvěma směry. o
Volbou cesty Xkp, musí být současně zablokována cesta Xpk. Při volbě m cest je současně blokováno m zpětných cest.
o
Vzhledem k tomu, ţe jde o silně degenerovaný dopravní problém
m
proměnných v řešení, je předpoklad moţností
řešení jako přiřazovací dopravní [ Souček, 1966]. o
Při předpokladu shodné vzdálenosti mezi uzly Ua a Ub se pracuje
s horní
trojúhelníkovou
maticí
a
s dolní
trojúhelníkovou maticí, které jsou navzájem symetrické, dle hlavní diagonály. o
Pokud existují dvě alternativy přímého spojení Ua a Ub, horní trojúhelníková matice a dolní trojúhelníková matice jsou nesymetrické
61
13.2 Metody řešení okružní dopravní úlohy 13.2.1 Metoda nejbližšího souseda Jedná se o nejjednodušší metodu pro řešení jednoduchého dopravního okruţního problému. Na počátku úlohy je zvoleno výchozí místo. Ze zvoleného výchozího místa se vyhledává nejvýhodnější dopravní spojení do druhého místa. Z druhého místa
se
hledá
další
nejvýhodnější
spojení
do
třetího
místa. Tímto způsobem zřetězování se vypočítá celá úloha. V okamţiku, kdy jsou všechna místa propojena, je nezbytné zařadit ještě jednu trasu zpět do výchozího místa.
13.2.2 Hamiltonova kružnice Pojmem
Hamiltonova
cesta,
která
hran,
kolik
kruţnice
prochází je
všemi
v grafu
je
myšlena
uzly
grafu.
uzlů.
taková
uzavřená
Obsahuje
Předpoklady
tolik
pouţití
Hamiltonovy kruţnice jsou následující: o Obslouţení všech vrcholů – kaţdý vrchol bude pouţit pouze jednou. o Suma všech zákazníků nepřekročí kapacitu obsluţného zařízení Existence Hamiltonovy kruţnice v neorientovaném grafu je závislá na splnění nutných podmínek. Mezi nutné podmínky je řazen
souvislý
graf,
obyčejný
graf,
konečný
graf.
Tyto
grafy musí obsahovat alespoň 3 vrcholy a nesmí obsahovat mosty 62
a
artikulace.
Splnění
těchto
podmínek
však
není
dostačující k existenci Hamiltonovy kruţnice. Je nezbytná existence
dalších
3
podmínek:
Diracova
podmínka,
Oreho
podmínka, Posova podmínka. o Diracova
podmínka
–
Hamiltonova
kruţnice
je
obsaţena
v síti, má-li kaţdý vrchol stupeň roven alespoň n/2, kde n znamená počet vrcholů v síti. o Oreho
podmínka
pokud
je
–
síť
součet
obsahuje
stupňů
kaţdé
Hamiltonovu dvojice
kruţnici,
nesousedních
vrcholů roven alespoň počtu uzlů v síti n. o Posova podmínka – síť obsahuje Hamiltonovu kruţnici, jeli splněna podmínka
σk < k, kde k je přirozené číslo
z intervalu (0, n/2), σk znamená počet vrcholů grafu se stupněm max. k. o Artikulace – vrchol, jehoţ odstraněním je zvýšen počet komponentů grafu alespoň o jeden. o Most
–
hrana,
jejímţ
odstraněním
je
zvýšen
počet
komponentů grafu o jeden. o Komponent grafu – maximální souvislý podgraf grafu. o Pravidelný
graf
–
graf,
který
má
všechny
vrcholy
stejného stupně
13.2.3 Heuristické algoritmy Existují úlohy, pro které je typická skutečnost, ţe při pouţití exaktních algoritmů je moţné nalézt řešení pouze pro
málo
stovkami
obsáhlé uzlů.
dopravní
Je
tomu
problémy
tak
i
s maximálně
přesto,
ţe
je
několika pouţívána
vyspělá výpočetní technika. Je tomu tak z toho důvodu, ţe počet nezbytných operací potřebných k získání optimálního řešení
roste
exponenciálně
důvodu
se
praxi
v
s velikostí
vyuţívají
algoritmy,
úlohy.
Z tohoto
které
naleznou
pseudooptimální řešení. Pseudooptimální řešení je přípustné a vyhovující, ale zřídkakdy nejlepší moţné. Pseudooptimální 63
řešení ani neumoţní porovnat, jaká je jeho odchylka od optimálního řešení. Výhodou tohoto způsobu řešení je úspora času.
Suboptimální
řešení
vyuţívají
metody
lokálních
vlastností účelových funkcí, které platí pouze v omezeném prostoru přípustných řešení [ Tuzar, 1977]. Heuristické modely jsou zaloţeny na 2 principech: o Je
vytvořeno
libovolné
přípustné
řešení,
které
je
zlepšováno, aniţ by byly narušeny podmínky přípustnosti. Proces
je
ukončen
v okamţiku,
kdy
je
dosaţeno
přípustného řešení, které uţ nelze nadále zlepšit. o Je
vytvořeno
nepřípustné
výchozí
řešení,
které
má
hodnotu účelové funkce lepší, neţ můţe nabývat přípustné řešení
a
dodrţení
které
je
podmínek
upravováno
tak,
přípustnosti
při
aby co
bylo
dosaţeno
nejmenší
změně
hodnoty účelové funkce. Proces je ukončen v okamţiku, kdy je dosaţeno nějakého optimálního řešení.
13.2.4 Kimova metoda Heuristická metoda, která slouţí pro vyhledání suboptimální trasy. Trasa musí projít všemi uzly sítě. Název metody je dle jejího autora C. Kima. Postup Kimovi metody [Tuzar, 1977] o Je dána síť S=(V,H). Daná síť je doplněna na úplnou síť S´=(V´,H´) tak, ţe kaţdému existujícímu úseku je přiřazena vzdálenost trasy a, jeţ odpovídá příslušné dvojici uzlů původní sítě S. o V síti S´ se nalezne minimální kostra K (S´). Úseky kostry se zdvojí, čímţ se získá eulerovská síť.
64
o Pro zdvojenou kostru K(S´) se nalezne eulerovský tah. Eulerovský tah je takový tah, který spojuje všechny vrcholy grafu jedním tahem o Eulerovský tah v síti S nezkracován tak, ţe pokud přes nějakou skupinu uzlů Vi,..Vj, kde i<j prochází tento tah více neţ jednou a existuje-li úsek
(Vi-1,Vj+1),je
zkrácena
část
tak,
vynechán
úsek
tahu
(Vi-1,Vi,…
Vi,..Vj.
Vj,Vj+1)
Tím
je
ţe
zkrácena
je
hodnota
dosavadního řešení, jeţ se označí např. Z o Dokud je Z>0 opakuje se předcházející bod
13.2.5 Úloha optimálního trasování Okruţní dopravní problém je rozšířen a při obsluze uzlů sítě se uvaţuje omezená kapacita dopravního vozidla a doba trvání,
ve
které
mohou
tyto
vozidla
obsluhu
vykonávat
s ohledem na pracovní dobu obsluhovaných míst v síti. Je tedy
nutné
V závislosti vozidlo
trasu na
vozidla
velikosti
uskutečnit
více
omezit
určitým
poţadavků
v uzlech
jízd
nebo
můţe
být
způsobem. sítě
můţe
uţito
více
vozidel či některé uzly mohou být navštíveny vícekrát. Patří sem Clarkeova – Wrighetova metoda.
13.2.6 Swamm metoda V 80. SWAMM, svozu
letech
dvacátého
která
vycházela
dokumentů
pro
století
byla
z podmínek centrální
formulována
konkrétního
středisko
problému
zemědělského
podniku [ Švasta, 1977]. Metoda SWAMM vychází z několika předpokladů: 65
metoda
o Je moţné kombinovat 4 přístupy k řešení daného problému z hlediska forem zobrazení. Tyto formy jsou: zavedení dynamiky
do
incidenční
distribuční
matice
úlohy,
síťového,
vyuţití
orientovaného
vlastností grafu,
ale
musí být vyloučeny prvky hlavní diagonály. Tato matice je rovněţ matice přiřazovacího problému. Takto vytvořená matice
zobrazuje
úlohu
jednookruhového
dopravního
problému se značným mnoţstvím modifikací. o Přístupy v předchozím bodě byly odvozeny z následujících predikcí
pouţitých
metod,
kterými
jsou:
incidenční
matice síťového grafu, přiřazovací problém, jednoduché grafické
optimalizační
doplňkových nacházející
koeficientů se
ve
kritérium vazeb,
výchozí
zobrazitelné
čtvercová podobě
matice
bez
pomocí úlohy
okrajových
podmínek, silně degenerované řešení obecné distribuční úlohy. o Okruţní dopravní problém
66
14
Praktická část
Pro účel praktické části této diplomové práce byly navrţeny a vypočteny dvě konkrétní úlohy: 1. Dopravní
distribuční
problém
ve
společnosti
United
Bakeries a.s. 2. Dopravní úloha navrţená panem Doc. Švastou z České zemědělské university v Praze První úloha byla zvolena z odvětví pekařského průmyslu, v němţ je distribuce výrobků důleţitým elementem ve výši nákladů. Pro účely této diplomové práce se podařilo navázat spolupráci s přední pekařskou firmou v České republice a ve střední Evropě - United Bakeries a.s.
Spolupráce s United
Bakeries a.s. mi umoţnila pracovat s reálnými daty z praxe, coţ povaţuji za skutečný přínos této diplomové práce. Druhá úloha, která byla navrţena panem Doc. Švastou, se zabývá
rozvozem
benzínu
cisternou
po
jednotlivých
benzínových pumpách. Zmíněná úloha je úlohou teoretickou, která se neopírá o skutečná data z praxe. Úlohy se zabývají řešením okruţního dopravního problému, který je shledáván jako problematika nového tisíciletí.
67
15
Dopravní distribuční problém ve společnosti United bakeries a.s.
15.1 Představení společnosti United bakeries a.s. Společnost na svých webových stránkách a ve svém firemním časopise uvádí, ţe patří mezi největší pekárenskou firmu ve střední Evropě. Mateřskou firmou akciové společnosti United Bakeries a.s. je lucemburská European United Bakeries a.s. United Bakeries a.s. vznikla sloučením dvěma velikými českými firmami, které měly vedoucí postavení na českém trhu.
Jedná
se
o
společnosti
Odkolek
a
Delta
Pekárny.
United bakeries a.s. rovněţ zastřešuje dceřiné zahraniční firmy. První z firem je slovenská pekařská firmu Delta Pekárne. Druhou, a zároveň poslední zahraniční firmou je maďarský Interback Csopre. Firma je také významným regionálním zaměstnavatelem, jak
uvádí
na
svých
webových
stránkách.
Ve
třech
středoevropských státech zaměstnává aţ 4 000 zaměstnanců. United bakeries a.s. má několik vytyčených cílů a plánů do budoucna: o Stát se jednou z nejvýznamnějších pekařských firem v region Evropská Unie, V této ambiciózní vizi je určitě nezbytné vyuţívat nejefektivnější distribuční cesty. A to takovým způsobem, aby byl dodavatel schopen doručit své výrobky včas a s co nejmenšími dopravními náklady. 68
o Nabízet špičkový servis a široké portfolio výrobků. Je zřejmé,
ţe
špičkový
servis
se
neobejde
bez
přesné
koordinace distribuce výrobků. A jak jiţ bylo v této práci zmíněno, je přesná koordinace distribuce výrobků tématem praktické části této diplomové práce. o Sledovat
nejnovější
trendy
v odvětví.
Rovněţ
s tímto
cílem souvisí tato diplomová práce. Nejnovější trendy v oblasti logistiky jsou v potravinářských a chemických firmách pod neustálým dohledem. o Být zodpovědnou firmou vůči svým zaměstnancům. Pokud se sníţí počet najetých kilometrů, bude mít tato skutečnost pozitivní vliv a ţivotní prostředí.
15.2 Navržený matematický algoritmus vztahující se k problematice dopravního okružního problému Pro
účely
navrţený
této
panem
diplomové Ing.
práce
Václavem
byl
pouţit
Janouškem
z
algoritmus
Vysoké
školy
bodů.
Body
finanční a správní o.p.s.
15.2.1 Úvod Existuje
uzavřená,
definovaná
mnoţina
představují různá místa, města, uzly, depozity. Tyto body jsou spojeny ohodnocenými hranami. Kaţdá ohodnocená hrana představuje náklady, které vzniknou v důsledku přemístění mezi oběma body. Těmito náklady mohou být myšleny například vzdálenosti, avšak konkrétních interpretací můţe být více.
69
V ekonomické praxi je často řešena úloha, ve které je třeba projít všemi uvedenými body tak, aby celkové náklady spojené s realizací tohoto průchodu byly minimální. Matematicky cyklu
se
v obecně
jedná
o
úlohu
neorientovaném
nalezení
grafu
Hamiltonova
G=(U,H),
kde
U
je
mnoţina uzlů grafu a H je mnoţina ohodnocených hran, které tyto
body
Hamiltonova grafu
a
spojují. cyklu
zároveň
Nutnou
podmínkou
v neorientovaném podmínka
deg
pro
existenci
je
souvislost
grafu
(ui)>=2
pro
všechny
uzly
v grafu. Princip řešení okruţního dopravního problému spočívá v nalezení takového Hamiltonova cyklu ze všech existujících Hamiltonových cyklů grafu tak, aby součet ohodnocení hran cyklu byl minimální. Matematická formulace: Z = ∑ ∑ cij.xij minimalizovat i=1
i=1
kde cij je ohodnocení hran grafu a xij je počet přemístění (cest) z bodu i do uzlu j a můţe nabývat pouze hodnot 0 nebo 1. Základní
dva
typy
okruţních
dopravních
úloh
se
liší
s úplnou
sítí
spojení
mezi
charakterem cestní sítě: o První cest,
dopravní ve
problém
kterém
se
vyznačuje
existuje
přímé
libovolnými dvěma uzly. o Druhý
dopravní
cest,
v němţ
přímé
spojené
problém nelze kaţdé
průchodu uzlem dalším. 70
se
vyznačuje neúplnou
realizovat dvojice
v libovolném uzlů
bez
sítí směru
nutnosti
15.2.2 Algoritmus Dle
pana
Ing.
Václava
Janouška
je
exaktní
matematické
řešení problému velmi obtíţné. Ale i přesto byla vyvinuta řada heuristických algoritmů, které naleznou: o Přímo optimální řešení o Suboptimální řešení, které se optimálnímu řešení velmi přibliţuje a pro praktické účely je zcela postačující. V této z maďarské
práci metody
je pro
popsán řešení
algoritmus
vycházející
přiřazovacího
problému.
A
který je upraven pro okruţní dopravní problém. Vzdálenosti (ohodnocení) mezi jednotlivými uzly můţeme vyjádřit
pomocí
matice
vzdáleností
VZDALEN.
Kaţdý
prvek
této matice VZDALEN(i,j) představuje hodnotu přináleţející hraně,
která
vede
z uzlu
i
do
uzlu
j.
Cyklus
v grafu
vyjádříme pomocí matice OBSAZ, kde prvek matice OBSAZ(i,j) = 1 bude znamenat, ţe se v daném cyklu pouţívá cesta z uzlu i do uzlu j. Tedy nepouţívané cesty budou mít OBSAZ(i,j) = 0.
Je
zřejmé,
ţe
jednotkové
prvky
matice
OBSAZ
musí
vytvářet v grafu Hamiltonův cyklus. Jako
další
pomocnou
matici
pouţíváme
matici
MOZNO,
jejíţ prvky MOZNO(i,j) nabývají logických hodnot TRUE nebo FALSE a indikují, zda je moţné danou cestu obsadit. Na počátku řešení jsou všechny prvky matice MOZNO nastaveny na hodnotu
TRUE,
s výjimkou
diagonály.
Na
hodnoty FALSE, protoţe okruh nemá smyčky.
71
diagonále
jsou
15.2.3 Jednotlivé kroky algoritmu Jednotlivé kroky dle pana Ing. Václava Janouška: 1. Redukce matice sazeb Optimální
řešení
úlohy
se
nezmění,
jestliţe
v matici
VZDALEN provedeme redukci podle následujícího schématu: o Upravíme matici VZDALEN tak, aby obsahovala v kaţdém řádku a sloupci alespoň jednu nulovou sazbu. Přičemţ tyto sazby nesmějí nabývat záporných hodnot. o Vyhledáme v kaţdém řádku matice řádkové minimum přes všechna políčka, která je moţné obsadit: MinVZDALEN(i,j)= VZDALEN(i,k),j=1,2....n a MOZNO(i,j)= TRUE o a odečteme od příslušného řádku matice VZDALEN. o Dostaneme: VZDALEN‘(i,j) = VZDALEN(i,j) – VZDALEN(i,k) o Tentýţ postup zopakujeme i pro sloupce matice. o Vyhledáme v kaţdém sloupci matice sloupcové minimum: Min VZDALEN(i,j) = VZDALEN(k,j)
i=1,2....n a
MOZNO(i,j) = TRUE o a odečteme od příslušného sloupce matice VZDALEN. o Dostaneme: VZDALEN‘‘(i,j) = VZDALEN‘(i,j) – VZDALEN‘(i,k).
72
o Součet všech odečtených hodnot zaznamenáme. Jedná se o první odhad hodnoty Hamiltonova cyklu. 2. Zvýšení Jakmile máme redukci matice VZDALEN provedenou, přistoupíme k dalšímu kroku algoritmu a tím krokem je výpočet zvýšení hodnoty
účelové
funkce
v případě,
ţe
neobsadíme
políčko
s redukovanou nulovou hodnotou. V kaţdém
řádku
matice
VZDALEN‘‘
vyhledáme
ke
kaţdému
uvaţovanému políčku s redukovanou nulovou sazbou VZDALEN (k,l) řádkové i sloupcové minimum: Min1 = Min VZDALEN‘‘(k,j)
pro j=1,2...n; j<>l a MOZNO(k,j)
= TRUE Min2 = Min VZDALEN‘‘(i,l) pro i=1,2...n; i<>k a MOZNO(i,l) = TRUE Pro kaţdé políčko s redukovanou sazbou sečteme hodnoty Min1 a Min2. Hodnoty Min1 a Min2 zapíšeme do matice ZVYS jako prvek matice ZVYS(k,l). 3. Obsazení políčka Nyní
obsadíme
to
políčko
s redukovanou
nulovou
sazbou
VZDALEN‘‘(k,l), které má nejvyšší hodnotu ZVYS(k,l). Je to políčko, jehoţ případným neobsazením by došlo k nejvyššímu minimálně moţnému zvýšení hodnoty účelové funkce. 4. Úprava matice MOZNO a vyhledání neúplných cyklů Jakmile
jsme
provedli
obsazení
určitého
políčka
(OBSAZ(k,l)=1), musíme provést úpravy matice MOZNO. Jednak není moţné, aby bylo moţné obsadit další políčko na daném řádku nebo sloupci – daným uzlem se prochází pouze jednou, 73
tudíţ je třeba nastavit všechny prvky matice MOZNO na daném řádku i sloupci na hodnotu FALSE. MOZNO(k,j) = FALSE
j=1,2....n (z uzlu k jiţ vede
obsazená cesta do uzlu l a jiná cesta se z uzlu k obsazovat nebude) MOZNO(i,l) = FALSE
i=1,2....n (do uzlu l jiţ vede
obsazená cesta z uzlu k a jiná cesta vedoucí do uzlu l se obsazovat nebude) Dále je nutné vyhledat všechny neúplné cykly a zabránit tomu, aby byla obsazena políčka vytvářející tyto neúplné cykly. To provedeme tak, ţe ke kaţdému obsazenému políčku vyhledáme další obsazená políčka tvořící s ním souvislou cestu
a
znepřístupníme
v rámci
této
cesty
všechna
neúplný
políčka,
cyklus.
která
vytvářejí
Například,
máme-li
obsazená políčka 1 – 6 a 6 – 3, pak je nutné nastavit hodnotu
FALSE
v matici
MOZNO
pro
políčka
MOZNO(6,1),
MOZNO(3,6) a MOZNO(3,1). Pouze je-li souvislá cesta tvořená jiţ
všemi
uzly
daného
grafu,
povolíme
obsazení
políčka
vedoucího z posledního uzlu této cesty do uzlu výchozího – bude se jednat o úplný, Hamiltonovský cyklus. 5) Opakování kroků 1 – 4 až do nalezení řešení Kroky 1 – 4 opakujeme tolikrát, kolik je v daném grafu uzlů. V kaţdém kroku přičteme vypočtenou hodnotu redukce sazeb
k hodnotě
stávající.
Splňuje
–
li
úloha
podmínky
řešitelnosti, obsadíme v kaţdém opakování jedno políčko, takţe cyklus
po
n
opakováních
s optimální
budeme
hodnotou
mít
vytvořený
účelové
funkce.
Hamiltonův Vypočtená
celková redukce je pak hodnotou účelové funkce a musí se rovnat součtu původních hodnot obsazených políček. redukce 74
je pak hodnotou účelové funkce a musí se rovnat součtu původních hodnot obsazených políček.
15.2.4 Příklad řešení obecného příkladu Popsaný
algoritmus
ilustrován
na
v podkapitole
jednoduchém
11.2.3
příkladě,
který
nyní
bude
navrhl
Ing.
Václav Janoušek. Mějme nalézt optimální okruţní cestu v grafu, jenţ má 4 uzly s ohodnocenými hranami danými maticí VZDALEN:
Uzel č. 1 2 3 4
1 0 1 2 5
2 1 0 2 3
Výchozí nastavení matice MOZNO je: Uzel č. 1 2 1 FALSE TRUE 2 TRUE FALSE 3 TRUE TRUE 4 TRUE TRUE
3 2 2 0 1
4 5 3 1 0
3 TRUE TRUE FALSE TRUE
4 TRUE TRUE TRUE FALSE
Krok č.1 řešeného algoritmu Řádková redukce. Podle výše popsaného postupu je: Min VZDALEN(1,j) = VZDALEN(1,2) = 1
pro všechna j kde
MOZNO (1,j)=TRUE, tedy j
pro j=2,3,4
Min VZDALEN(2,j) = VZDALEN(2,1) = 1
pro všechna j kde
MOZNO (2,j)=TRUE, tedy j
pro j=1,3,4
Min VZDALEN(3,j) = VZDALEN(3,4) = 1 MOZNO (3,j)=TRUE, tedy j 75
pro j=1, 2, 4
pro všechna j kde
Min VZDALEN(4,j) = VZDALEN(4,3) = 1
pro všechna j kde
MOZNO (4,j)=TRUE, tedy j
pro j=1, 2, 3
Po provedené řádkové redukci dostáváme redukovanou matici VZDALEN‘:
Uzel č. 1 2 3 4
1 0 0 1 4
2 0 0 1 2
3 1 1 0 0
4 4 2 0 0
Analogickým způsobem nyní provedeme sloupcovou redukci: Min VZDALEN(i,1) = VZDALEN(2,1) = 0
pro všechna i kde
MOZNO (i,1)=TRUE, tedy i
pro i=2,3,4
Min VZDALEN(i,2) = VZDALEN(1,2) = 0
pro všechna i kde
MOZNO (i,2)=TRUE, tedy i
pro i=1,3,4
Min VZDALEN(i,3) = VZDALEN(4,3) = 0
pro všechna i kde
MOZNO (i,1)=TRUE, tedy i
pro i=1,2,4
Min VZDALEN(i,4) = VZDALEN(3,4) = 0
pro všechna i kde
MOZNO (i,1)=TRUE, tedy i
pro i=1,2,3 Vidíme, ţe další redukci jiţ není moţné provést a ţe
matice VZDALEN‘‘ =VZDALEN‘. Hodnota celkové redukce je 4. Krok 2 algoritmu Výpočet zvýšení Podle výše uvedeného algoritmu vypočteme zvýšení hodnoty účelové funkce pro případ, ţe se neobsadí políčka s nulovou redukovanou hodnotou. Jedná se o tato políčka: VZDALEN(1,2), VZDALEN(2,1), VZDALEN(3,4) a VZDALEN(4,3).
76
Výpočet zvýšení pro políčko VZDALEN(1,2): Min1 = Min VZDALEN‘‘(1,j)
pro j=1,2...n; j<>2 a MOZNO(k,j)
= TRUE tedy pro j=3,4 Min1 = VZDALEN(1,3) = 1 Min2 = Min VZDALEN‘‘(i,2) pro i=1,2...n; i<>1 a MOZNO(i,l) = TRUE tedy pro i=3,4 Min2 = VZDALEN(3,2) = 1 Zvýšení pro políčko VZDALEN‘‘(1,2) je tedy rovno 2. Analogicky vypočteme i zvýšení pro zbývající 3 políčka a dostaneme: ZVYS(1,2) = 2 ZVYS(2,1) = 2 ZVYS(3,4) = 3 ZVYS(4,3) = 3 Krok 3 algoritmu obsazení políčka Podle
kroku
3
popsaného
algoritmu
obsadíme
to
políčko,
jehoţ zvýšení je nejvyšší. V našem případě se jedná o dvě políčka: (3,4) a (4,3), která obě mají zvýšení rovno 3. Mezi nimi můţeme libovolně volit. Vybereme políčko (3,4) a obsadíme jej. Dostaneme matici OBSAZ: Uzel č.
77
1
2
3
4
1
0
0
0
0
2
0
0
0
0
3
0
0
0
1
4
0
0
0
0
Krok 4 algoritmu Úprava matice MOZNO Nyní musíme upravit matici MOZNO. Nejprve poloţíme hodnotu MOZNO všech cest vedoucí z uzlu 3 do všech dalších uzlů rovnu FALSE. Totéţ provedeme se všemi cestami vedoucími ze všech
uzlů
neúplného
do
uzlu
cyklu.
4.
Dále
V našem
musíme
případě
znemoţnit
vytvoření
znamená
poloţit
to
hodnotu MOZNO cesty vedoucí z uzlu 4 do uzlu 3 rovnu FALSE. Po provedených úpravách dostáváme novou matici MOZNO: Uzel č.
1
2
3
4
1
FALSE
TRUE
TRUE
FALSE
2
TRUE
FALSE
TRUE
FALSE
3
FALSE
FALSE
FALSE
FALSE
4
TRUE
TRUE
FALSE
FALSE
Nyní
se
vracíme
zpět
k 1.
kroku
algoritmu.
Matice
3
4
VZDALEN má nyní tyto hodnoty: Uzel č.
Po
1
2
1
0
0
1
4
2
0
0
1
2
3
1
1
0
0
4
4
2
0
0
provedení
řádkové
redukce
podle
výše
uvedeného
a
popsaného postupu dostaneme tuto matici VZDALEN‘: Uzel č.
78
1
2
3
4
1
0
0
1
4
2
0
0
1
2
3
1
1
0
0
4
2
0
0
0
Hodnota celkové redukce se zvýší o 2, nyní tedy bude rovna 6. Po
provedení
sloupcové
redukce
dostaneme
tuto
matici
VZDALEN: Uzel č.
1
2
3
4
1
0
0
0
4
2
0
0
0
2
3
1
1
0
0
4
2
0
0
0
Hodnota celkové redukce se zvýší o 1, nyní bude rovna 7. Po výpočtu zvýšení pro políčka s redukovanou nulovou sazbou a hodnotou MOZNO=TRUE dostáváme: ZVYS(1,2) = 0 ZVYS(1,3) = 0 ZVYS(2,3) = 0 ZVYS(4,2) = 2 Obsadíme tedy políčko (4,2) Matice OBSAZ má nyní tyto hodnoty: Uzel č.
1
2
3
1
0
0
0
0
2
0
0
0
0
3
0
0
0
1
4
0
1
0
0
Nyní musíme opět upravit matici MOZNO:
79
4
Uzel č.
1
2
3
4
1
FALSE
FALSE
TRUE
FALSE
2
TRUE
FALSE
FALSE
FALSE
3
FALSE
FALSE
FALSE
FALSE
4
FALSE
FALSE
FALSE
FALSE
Je zřejmé, ţe nyní je moţné obsadit jiţ jen políčka (1,3) a (2,1). Obě jiţ mají redukovanou sazbu nulovou, hodnota celkové redukce se jiţ nezvýší a zůstává rovna 7,. coţ je také hodnota účelové funkce. Optimální cyklus má tedy tuto podobu: Matice OBSAZ: Uzel č. 1 2 3 4
1
2 0 1 0 0
3 0 0 0 1
Cesta grafem bude tedy vypadat takto: Z uzlu Do uzlu 1 3 3 4 4 2 2 1 CELKEM
4 1 0 0 0
0 0 1 0
Hodnota 2 1 3 1 7
15.2.5 Maďarská metoda Algoritmus navrţený panem Ing. Václavem Janouškem vychází z Maďarské metody. Jedná se tedy o modifikovanou maďarskou metodu, která je upravena pro potřeby okruţního dopravního problému. Pro snazší pochopení algoritmu pana Ing. Václava Janouška v této práci popíši princip Maďarské metody.
80
15.2.5.1
Algoritmus Maďarské metody
Maďarská metoda je vhodná pro řešení vysoce degenerovaných dopravních problémů. Algoritmus [ Rychetník, 1968]: a. V přípravné etapě se upraví matice cen obsahovala
v kaţdém
řádku
a
sloupci
cij tak, aby alespoň
jednu
nulovou sazbu, zároveň sazby nesmí nabývat záporných hodnot b. Zkontroluje se, zda jsou všechny nuly překryty. Jsouli
všechny
nulové
sazby
překryty,
je
vybrán
počet
nezávislých nul, kdy řešení zatím není moţné měnit. Jsou-li
nějaké
nuly
nepokryty,
je
třeba
změnit
soustavu provizorních krycích čar. Kontrolují se tedy nepokryté nuly. Vezme-li se libovolná nepokrytá nula z k-tého řádku a v případě, ţe ak = 0, překryje se řádek krycí čárou. Dojde–li k řadě, kde ak´>0, znamená to,
ţe
soustava
identifikována
a
nezávislých vybrána,
nul
počet
nebyla
vybraných
správně nul
není
maximální. Nalezená nula se označí symbolem „ ´ “a přejde se k následujícímu bodu algoritmu c. V jiném případě se opakuje postup bodu b, dokud není nalezena nepokrytá nula v řádku, kde aj´ a poté se přechází k následujícímu bodu c. Jsou-li všechny nuly překryty, přechází se k poslednímu kroku algoritmu d. c. V případě,
ţe
nebyl
pouţit
v dané
etapě
vybrán
maximální počet nul, vytvoří se nejdříve graf. d. Protoţe byl vyhledán maximální počet nezávislých nul je potřeba redukovat matici sazeb
81
15.3 Zdání distribuční úlohy ve společnosti United Bakeries a.s. Ze společnosti United Bakeries a.s. jsem po osobním setkání na
logistickém
zadání
jednoho
oddělení reálného
s panem
Ing.
Hurábem
distribučního
okruhu
obdrţela rozvozních
linek, který společnost kaţdý den pouţívá při rozváţení pečiva. Pekárna, ze které se rozváţí výrobky, se nachází ve městě Ţatec a rozváţí své výrobky na území města Ţatec, města Chomutov a jeho okolí (např. Údlice). Mým úkolem v této diplomové práci bylo najít takovou optimální cestu, která by zajistila menší počet ujetých denních Délka
kilometrů
diskutované
diskutovaného
dopravního
konkrétní cyklu
rozvozní
rozvozní
linky.
linky
na
Ţatecku, kterou rozvozní linka denně ujede, je 82,6 km. Seznam
jednotlivých
stanovišť
rozvozní
linky
nenásledující: o Pekárna Ţatec o Chládek Jan, Náměstí 11, Údlice o ProVektor, spol s.r.o, Náměstí 71, Údlice o MZK Chomutov s.r.o., Čelakovská 4874, Chomutov o Pepeso, Ing. Meissnera 4540, Chomutov o Firáková Alena, Kosmonautů 4063, Chomutov o Jolana Virágová, Ţiţkova 483, Jirkov o Jatky Jirkov s.r.o., Obchodní dům Bohemia, Chomutov o Kocourek Roman, K.H.Máchy 721, Jirkov o Balogová Hermína, Zahradní 5171, Chomutov o Gončár Ivan, Zahradní 5165, Chomutov o Zapletal Roman, Jiráskova 4170, Chomutov o 21.Mateřská škola Chomutov, Zahradní 5185, Chomutov
82
je
o EDOZ PLUS s.r.o., Dr. Farského 4732, Chomutov o Hung Nguyen Sy, Náměstí 85, Údlice o NORMA K.S., Dřínovská 4887, Chomutov o 27. Mateřská škola Chomutov, Otvice o TESCO STORES ČR a.s., Zadní Vinohrady 5353, Chomutov o 4. Mateřská škola Chomutov, Blatenská 4893, Chomutov o Pekárna Ţatec
15.3.1 Sestavení matice vzdáleností Aby bylo moţné porovnat kilometry, které rozvozní linka skutečně pomocí
ujede
s počty
postupu,
který
kilometrů, je
uveden
které
budou
v této
spočítány
diplomové
práci
v kapitole 13.2, je nezbytné sestavit matici vzdáleností. Matici vzdáleností pro potřeby této diplomové práce jsem sestavila
způsobem,
který
nyní
popíši
v následujícím
odstavci. Na mapě Ţatecka a Chomutovska jsem přesně vyznačila všechna jednotlivá stanoviště. Jednotlivá stanoviště jsem očíslovala písmeny 1- 19. Tedy matice vzdáleností bude mít tvar 19x19. Následně jsem graficky vyznačila všechny moţné jednotlivé
cesty
Podmínkou
z bodu
vyznačení
skutečnost,
ţe
1
cesty
cesta
do je
neprochází
všech její
ostatních
přímý
jiným
bodů.
směr,
vyznačeným
tzn. bodem.
V teorii grafů se pouţívá termín přímá cesta. Nyní vznikl neorientovaný protoţe
graf.
mnoţina
neuspořádanou
Neorientovaný bodů
mnoţinu.
z neuspořádaných
graf
vyznačených Neuspořádaná
dvojic.
z toho
důvodu,
stanovišť mnoţina
Neuspořádané
se
dvojice
tvoří skládá mají
následující tvar: (a,b) = (b, a) pro b ≠ a. V následujícím kroku bylo důleţité jednotlivé spojnice hran vzniklého
grafu
vzniklého
grafu
83
ohodnotit. se
Hodnota
ohodnotila
počtem
jednotlivých
hran
kilometrů,
které
skutečně leţí mezi jednotlivými reálnými stanovišti. Tyto hodnoty mi pomohl zpřesnit program, který se věnuje mapám na
stránkách
Seznam.cz.
internetového
Pro
další
potřeby
vyhledávače úlohy
je
Google.cz
nyní
a
k dispozici
graf, jehoţ hrany jsou ohodnoceny. Ke vzniklému grafu jsem následně byla schopna sestavit matici vzdálenosti. Matice vzdáleností má velikosti 19x19. (viz. Příloha 1) Vlastnosti matice vzdáleností: o Na hlavní diagonále jsou pouze nuly (protoţe z jednoho bodu je nulová vzdálenost do toho samého bodu) o Matice
je
symetrická
podél
hlavní
diagonály.
Tato
vlastnost slouţí jako kontrola, zda sestavený graf byl sestrojen
správně
a
zda
hodnoty
stran
grafu
byly
nalezeny správně. o Matice
vzdálenosti
obsahuje
veliký
počet
buněk
s hodnotou nula. Je tomu tak proto, ţe mezi velikým počtem uzlů neexistuje přímé spojení. o Rozměry čísel uvedených v jednotlivých buňkách jsou udány v kilometrech
15.3.2 Nalezení optimální cesty V praxi zřídkakdy existuje případ, ţe kaţdý uzel v úloze je spojen s kaţdým dalším uzlem přímou cestou. Je tedy nutné spojení
mezi
dvěma
uzly
realizovat
pomocí
další
cesty,
která prochází jiným uzlem. Z výpočetních důvodů se pro uzly, mezi nimiţ neexistuje přímé spojení, zavádí fiktivní cesta. Fiktivní cesta je spojení dvou uzlů, přes další uzel při
neexistujícím
přímém
spojení
a
vyjadřuje
moţné
nejkratší spojení mezi těmito uzly. Tímto způsobem se získá
84
další matice, která se nazývá úplnou maticí spojení (viz. Příloha 2: úplná matice spojení 1). Vlastnosti úplné matice spojení: o Kromě
prvků
hlavní
diagonály
jsou
všechny
hodnoty
vylučují
zpětnou
větší neţ nula o Nulové
prvky
na
hlavní
diagonále
vazbu o Matice je symetrická podél hlavní diagonály S vytvořenou
matice
vzdáleností
se
dále
vloţím
do
vytvořeného programu a dostanu poţadované výsledky:
Z uzlu 1 2 3 16 5 10 11 9 7 8 17 18 6 14 4 12 19 13 15
Do uzlu 2 3 16 5 10 11 9 7 8 17 18 6 14 4 12 19 13 15 1
Vzdálenost,
vzdálenost 16,80 0,50 3,50 0,25 1,30 0,12 5,90 0,50 0,50 3,30 3,40 0,70 0,60 0,60 1,70 2,10 0,50 2,80 17,08 62,15
kterou
přes uzly přímá přímá 10 přímá přímá přímá 17,7 přímá přímá 7 přímá přímá přímá přímá přímá přímá přímá 10,3 přímá
algoritmus
našel
je
62,15
km.
Tato
vzdálenost je o 20, 45 km kratší. Coţ podniku ušetří značné náklady za dopravu, pokud uvaţujeme, ţe podobných okruhů firma denně uskutečňuje desítky.
85
16
Dopravní okružní distribuční problém navržený panem Doc.Švastou
16.1 Zadání dopravní úlohy Cisterna rozváţí benzín po benzínových pumpách. Okruh se skládá z 15 stanovišť. Cisterna vyjíţdí ze své centrály. Vzdálenost jednotlivých stanovišť je zadána pomocí maticí vzdáleností (viz. Příloha 3: matice vzdáleností 2) Úloha pracuje s předpokladem, ţe mezi všemi uzly existují přímé cesty. Uzly v úloze jsou spojeny pouze přímými cestami, proto se v tomto
případě
vzdálenosti
se
nevytváří pouţije
úplná
v popisovaném
následující výsledky: Z uzlu 1 4 2 3 7 8 12 13 14 15 11 10 9 5 6
86
Do uzlu 4 2 3 7 8 12 13 14 15 11 10 9 5 6 1 součet
matice
vzdálenost 100 20 10 120 5 10 100 5 10 102 10 5 10 5 115 627
spojení.
programu
a
Matice získám
Algoritmus
nejkratší
kilometrů.
Jelikoţ
se
moţnou jedná
cestu o
našel
smyšlený
o
délce
příklad,
627 nelze
výsledky porovnat s reálnými daty a posoudit, zda se jedná o nejlepší doposud nalezenou distribuční cestu.
87
17
Závěr
Z výsledků této diplomové práce, z konzultací na České zemědělské univerzitě v Praze (s panem Doc. Ing. Jaroslavem Švastou,
CSc.)
i
s
odborníky
z
praxe
z
firmy
United
Bakeries a.s. jednoznačně vyplývá, ţe vyuţití těchto metod přináší
významné
úspory
rozvoj.
Zavádění
do
pro
praxe
daný
lze
podnik
a
jednoznačně
jeho
další
doporučit.
S
tímto zaváděním do praxe jsou spojeny jednoznačné problémy, jejichţ
těţiště
nespočívá
ani
tak
v
technické
jako
v
personální a psychické oblasti. Ačkoliv se odpor proti zavádění těchto systémů zdá na první pohled iracionální, má svoji logiku. Logiku vztahů a zájmů na pracovištích. Jaké tedy tyto problémy konkrétně jsou? V první
řadě
se
jedná
o
charakteristiky
osobností
jednotlivých odpovědných pracovníků. Velkou překáţkou jsou mezilidské vztahy a konflikty, které jsou nedílnou součástí vztahů
na
kaţdém
pracovišti.
S tímto
úzce
souvisí
nevyjasněné rozhodovací kompetence a komunikační bariéry. Je – li zavedení zmíněných systémů nařízeno
nadřízenými
činiteli, často se stává, ţe odpovědní pracovníci na první pohled tyto systémy usilovně zavádějí, ale ve skutečnosti jejich
opravdové
zavádění
ze
všech
sil
sabotují.
Tyto
problémy v mezilidských vztazích jsou velice úporné, neboť mají tendenci se vynořit v okamţiku, kdy se zdá, ţe všechny překáţky
jiţ
byly
odstraněny.
Někdy
stačí
jiţ
jediný
pracovník na rozhodujícím místě, aby se celý proces zadrhl, ne
–
s tím,
li přímo zhatil. jak
noví
Tyto
pracovníci
problémy
se
přicházejí
dále
do
recyklují
organizace
a
staří pracovníci odcházejí. Informace jsou moc a přístup k informacím rozhoduje o tom,
který
autoritu 88
pracovník
potřebnou
bude
k tomu,
mít aby
formální
či
neformální
ovlivňoval
rozhodnutí
nadřízených
pracovníků.
I
neformální
autorita
oslabuje
pozici nadřízeného a vţdy v sobě obsahuje potenciál pro přeměnu
v autoritu
formální
(a
dosavadního vedouc9ho pracovníka). těchto
systémů
ohroţuje
tedy
ztrátu
pozice
Jinými slovy, zavádění
mocenskou
pozici
dotyčné
organizace. Další
obavou
zprůhlednění
vedoucích
minulých,
pracovníků
chybných
či
je
obava
alespoň
ne
ze
zcela
správných, rozhodnutí. Tyto systému poskytují strukturované a průhledné informace, které nebyly dostupné nebo alespoň zřejmé
v dobách
před
zavedením
těchto
systémů.
Vedoucí
pracovníci mají obavy z toho, ţe jejich dřívější rozhodnutí se
ukáţou
jako
nesprávná
a
nekompetentní,
nebo
se
přinejmenším ukáţe, ţe tato rozhodnutí nebyla tak správná, jak se tito sami pracovníci snaţili prezentovat. Další překáţkou je všeobecně zaţitý odpor ke změnám, inovacím
a
pracovníci nemají
novotám mnohdy
potřebnou
potřebnou
k tomu,
všeho
druhu.
neovládají
moderní
počítačovou aby
Zejména
zvládli
či
starší
metody
řízení,
jazykovou
nové
výzvy
vedoucí ani
vybavenost a
pracovní
postupy. Z výše vyjmenovaných příčin je tedy zavedení operační analýzy
jako
samozřejmého
instrumentu
do
řízení
podniku
činností, která teprve čeká na své zaslouţené uznání.
89
Seznam použité literatury I.
Gros I.: Logistika, Praha: Vydavatelství VŠCHT, 1996, ISBN 80 – 7080-262-6
II.
Gros
I.:
Kvantitativní
metody
v manaţerském
rozhodování, Praha: Grada Publishing, 2003, ISBN 80247-0421-8 III.
Louša F.: Zásoby, Praha: Grada Publishing, 2007, ISBN 978-80-247-2117-0
IV.
Rubáková V.: Účetnictví pro úplné začátečníky,Praha: Grada Publishing, 2002, ISBN 978-80-247-2003-6
V.
Synek
M.:
Manaţerská
ekonomika.
Praha:Grada
Publishinmg, 2007, ISBN 978-80-247-1992-4 VI.
Tomek G., Vávrová V.: Řízení výroby a nákupu, Grada Publishing, Praha 2007, ISBN 978-80-247-1479-0
VII.
RNDr. Antonín Tuzar, CSc, Ing. Petr Maxa, Doc.Ing. Vladimír Svoboda, CSc. 1997. Teorie dopravy. Praha: Vydavatelství ČVUT, 1997. ISBN 80-01-01637-4
VIII.
Doc. RNDr. Daniel Turzík, CSc. 2006. Matematika III Základy matematické optimalizace. Praha: vydavatelství VŠCHT, 2006. ISBN 80-7080-363-0
IX.
Ing.
Luděk
CSc.,
Ing.
Rychetník, Věra
CSc.,
Doc.Ing.
Pelzbauerová.
Jan
Sbírka
Zelinka, příkladů
z lineárního programování. Praha: SNTL, 1968. ISBN 04308-68 X.
Josef
Římánek,
Moravcová,
Jana
Zdeňka
Hančlová,
1979, ISBN 80 – 7078 XI.
Václav
Kořenář,
Zonková,
EvaPoštová,
Operační
výzkum,
Eva
Praha:
-188 – 2 Stochastické
procesy,
Praha:
Nakladatelství Oeconomica, 2010. ISBN 978-80-245-16462 XII.
Kruskal, J. Proceedings of the American Mathematical Society, 1956, s. 48-50
90
XIII.
Jablonský J., Operační výzkum – kvantitativní modely pro ekonomické rozhodování, 2002, Praha: Professional Publishing, 2002. ISBN 80-86419-23-1
XIV.
KUBÁT,
J.,
HORÁKOVÁ,
H.
Řízení
zásob.
Logistické
pojetí, metody, aplikace, praktické úlohy. 3. přeprac. vydání.
Praha:
Profess
Consulting,
1999.
ISBN
80-
85235-55-2 XV.
Pernica Petr, Logistický management:teorie a podniková praxe. Praha: Radix, 1998. ISBN 80-86031-13-6
XVI.
Maňas M., Teorie her a její aplikace. Praha: SNTL, 1991. ISBN 80-03-00358-X
XVII.
Pavlík J., Aplikovaná statistika. Praha: vydavatelství VŠCHT, 2005. ISBN 80-7080-569-2
XVIII.
Kavan M., Výrobní a provozní management. Praha: Grada, 2002. ISBN 80-247-0199-5
XIX.
Souček,
E.
a
kol.,
Lineární
programování,
Praha:
učební pomůcka VU 401 XX.
Švasta
J.,
K jednomu
dopravnímu
problému,
sborník,
Operační
analýza,
Řízení VTR v zemědělství č 2/1977 XXI.
G.
Karas,
I.
Gros,
I.
Sokolová,
Bratislava: Slovenská technická univerzita, 1992, ISBN 80-227-0507-1 XXII.
Walter J., Lauber J., Simulační modely ekonomických procesů, Praha:SNTL, 1975, Vysokoškolská učebnice
XXIII.
Schulte
Christof,
Logistika,
Publishing, 1994, ISBN 80-85605-87-2
91
Praha:
Victoria
Přílohy Seznam příloh I.
Příloha 1: Matice vzdáleností 1
II.
Příloha 2: Úplná matice spojení
III.
Příloha 3: Matice vzdáleností 2
92
93
