Optimalizace výrobního procesu podniku Zámečnictví Martin Bartl

Mendelova univerzita v Brně Provozně ekonomická fakulta

Optimalizace výrobního procesu podniku Zámečnictví Martin Bartl Bakalářská práce

Vedoucí práce: doc. Ing. Josef Holoubek, Csc.

Brno 2013

Martin Šimiček, DiS.

Tímto bych chtěl poděkovat doc. Ing. Josefu Holoubkovi, CSc. za jeho podnětné připomínky, které mi pomohly ve vypracování mojí bakalářské práce. Můj díky patří i Martinu Bartlovi, který mi dodal podkladová data a umoţnil konzultace ohledně procesu výroby.

Prohlašuji, ţe jsem tuto práci vypracoval samostatně s vyuţitím zdrojů, které jsou uvedeny v kapitole Literatura. V Brně dne 24. května 2013

__________________

Abstract This bachelor thesis deals with optimization of costs in company Zámečnictví Martin Bartl. For this it uses linear programming, namely cutting problems that provide optimal material dividing. The goal is to minimize the purchase costs for base material and to minimize waste material. The tasks are solved using Solver, which is part of MS Excel. Keywords Operations research, costs, optimization, linear programming, simplex method

Abstrakt Tato bakalářská práce se zabývá optimalizací nákladů v podniku Zámečnictví Martin Bartl. K tomuto účelu vyuţívá metod lineárního programování, konkrétně řezných úloh, které stanovují optimální dělení materiálu. Cílem práce je minimalizace nákladů, které jsou vynaloţeny na nákup materiálu a minimalizace odpadního materiálu, který dělením výchozího materiálu vzniká. Úlohy jsou řešeny pomocí doplňku Řešitel, který je součástí programu MS Excel. Klíčová slova Operační výzkum, náklady, optimalizace, lineární programování, simplexová metoda

10

Obsah

Obsah 1

Úvod

15

2

Cíl práce a metodika

16

3

2.1

Cíl práce ................................................................................................... 16

2.2

Metodika .................................................................................................. 16

2.2.1

Studium literatury ........................................................................... 16

2.2.2

Sběr dat ............................................................................................ 16

2.2.3

Tvorba modelu ................................................................................. 16

2.2.4

Řešení modelu ................................................................................. 17

2.2.5

Vyhodnocení výsledků ..................................................................... 17

2.2.6

Případná aplikace výsledků ............................................................. 17

Literární rešerše 3.1

18

Operační výzkum ..................................................................................... 18

3.1.1

Vývoj ................................................................................................ 18

3.2

Disciplíny operačního výzkumu .............................................................. 19

3.3

Matematické programování ................................................................... 20

3.3.1

Matematický model ........................................................................ 20

3.4

Základní typy úloh lineárního programování ......................................... 21

3.5

Základní pojmy úlohy lineárního programování ....................................22

3.6

Moţná řešení úloh lineárního programování .........................................23

3.7

Základní tvar úlohy lineárního programování ........................................24

3.8

Řezné úlohy .............................................................................................24

3.9

Simplexová metoda .................................................................................25

3.9.1

Normované tvary .............................................................................25

3.9.2

Postup simplexové metody .............................................................. 27

3.10 Celočíselné programování .......................................................................29 3.10.1

Metoda větvení a mezí .................................................................... 30

3.11 Zpracování úloh matematického programování na PC ......................... 30 3.12 Optimalizace v programu MS Excel 2007.............................................. 30

Obsah

4

5

6

11

Charakteristika podniku a současného stavu výroby

33

4.1

Zámečnictví Martin Bartl ....................................................................... 33

4.2

Výrobní proces ........................................................................................ 33

4.3

Zakázka ................................................................................................... 35

4.4

Volba výchozích polotovarů .................................................................... 35

4.5

Tvorba řezného plánu bez vyuţití metod operačního výzkumu ............ 36

4.6

Klady současného systému ..................................................................... 38

4.7

Nevýhody současného systému .............................................................. 38

Formulace matematického modelu

39

5.1

Rozřezávací schémata ............................................................................. 39

5.2

Matematický model ................................................................................ 39

5.3

Plochý profil 50×10 mm ......................................................................... 39

5.4

Plochý profil 50×5 mm ........................................................................... 40

5.5

Hranol 10×10 mm .................................................................................... 41

Řešení matematického modelu 6.1

42

Řešení modelu pro plochý profil 50×10 mm.......................................... 42

6.1.1

Počet výchozích polotovarů ............................................................ 42

6.1.2

Minimalizace odpadu ...................................................................... 43

6.2

Řešení modelu pro plochý profil 50×5 mm ........................................... 45

6.2.1


6.2.2


6.3

Řešení modelu pro hranol 10×10 mm .................................................... 46

6.3.1


6.3.2


7

Závěr práce

49

8

Literatura

50

12

Seznam obrázků

Seznam obrázků Obr. 1

Parametry Řešitele

31

Obr. 2

Omezující podmínky

32

Obr. 3

Teplovodní krbová vložka Alfa 1

33

Seznam tabulek

13

Seznam tabulek Tab. 1

Simplexová tabulka

28

Tab. 2

Alfa 1 – druhy profilů

34

Tab. 3

Výchozí polotovary

35

Tab. 4

Rozřezávací schéma pro plochý profil 50×10 mm

36

Tab. 5


37

Tab. 6

Rozřezávací schéma pro hranol 10×10 mm

37

Tab. 7 Počet výchozích polotovarů – profil 50×10 mm – optimální řešení 42 Tab. 8

Odpad – profil 50×10 mm – optimální řešení

43

Tab. 9

Vyhodnocení modelů pro profil 50×10 mm

44

Tab. 10 Počet výchozích polotovarů – profil 50×5 mm – optimální řešení 45 Tab. 11


45

Tab. 12


46

Tab. 13 Počet výchozích polotovarů – profil hranol 10×10 mm – optimální řešení 47 Tab. 14

Odpad – profil hranol 10×10 mm – optimální řešení

47

Tab. 15

Vyhodnocení modelů pro profil hranol 10×10 mm

48

14

Úvod

15

1 Úvod Maximalizace zisku, jeden z hlavních cílů drtivé většiny podnikatelů. Zisk je motivační silou, která nás v kombinaci s dobrým nápadem na produkt můţe přimět k myšlence o zaloţení společnosti. Co však dělat pokud se nám nedaří?. Jakým způsobem zisk zvyšovat? Cestou k prosperitě můţe být neustálá snaha o zvyšování kvality nabízených výrobků a jejich inovace, ale i zlepšování a rozšiřování doprovodných sluţeb jako jsou včasný dodej, záruční a poradenský servis a jiné. Dále je vhodné zaměřit se na efektivitu výroby ve smyslu sniţování nákladů a zrychlování procesů bez toho, aby se zhoršovala výsledná kvalita produkce. Podporu v této oblasti můţe představovat mimo jiné i vyuţití poznatků lineárního programování. V této práci jsou představeny řezné úlohy, které pomáhají nalézt optimální řešení v oblasti dělení materiálu. K tomu vyuţívají matematických modelů, vytvořených na základě dat získaných od majitele společnosti Zámečnictví Martin Bartl. Dělení materiálu je první činností, která po nákupu polotovarů v zámečnické dílně nastává. Při této operaci vzniká odpadní materiál, který je pro další zpracování nevyuţitelný. V letních měsících, kdy je nápor objednávek nejvyšší, se díky dobrým kamarádským vztahům a mé zálibě v technice stávám sezonním pracovníkem v zámečnické dílně pana Bartla i já. Mým úkolem bývá obsluha pásové pily a příprava profilů ke svařování i další drobnější práce. Z tohoto důvodu jsem si vybral zvolené téma své bakalářské práce.

16


2 Cíl práce a metodika 2.1 Cíl práce Cílem práce je prezentovat vyuţití metod lineárního programování v praxi a ověřit tak jejich skutečný přínos v reálných podmínkách, přesněji k optimalizaci nákladů v provozu zámečnické dílny. Tato optimalizace je prováděna ze dvou hledisek:  stanovení minimálního počtu výchozích polotovarů, ze kterých se vyřezávají profily poţadovaných délek,  minimalizace odpadu, který vzniká rozřezáváním výchozích polotovarů na jednotlivé profily. Modely lineárního programování budou řešeny dostupným softwarovým vybavením. V závěru práce bude srovnán stávající způsob tvorby rozřezávacích schémat s výstupem z modelů lineárního programování.

2.2 Metodika 2.2.1

Studium literatury

Prvním úkolem je studium důleţitých poznatků, které souvisí s tvorbou modelů lineárního programování. Jde zejména o seznámení se s oblastí operačního výzkumu, objasnění základních pojmů, definování postupu tvorby modelu, pochopení simplexové metody, seznámení se s počítačovou podporou v řešení úloh lineárního programování. Tyto informace budou získány studiem odborné literatury a uvedeny v kapitole Literární rešerše. 2.2.2

Sběr dat

Tato část zahrnuje analýzu výrobního procesu ve společnosti Zámečnictví Martin Bartl. Ve spolupráci s majitelem podniku bude definován postup, jakým dochází k dělení materiálu za současných podmínek. Bude navrţen cíl, kterého chceme dosáhnout a určeno, jaká jsou omezení pro dosaţení tohoto cíle. 2.2.3

Tvorba modelu

Získaná data budou zpracována do tabulek v programu MS Excel. Tyto tabulky poslouţí zároveň jako základ pro tvorbu modelů lineárního programování. Z minulé fáze je definován cíl úlohy a omezení, která je třeba brát v úvahu. S vyuţitím tabulek a funkcí programu MS Excel budou tyto informace převedeny do matematických výrazů. Pro kaţdý profil budou vytvořeny dva modely. První z nich bude definovat, kolik kusů výchozích polotovarů bude potřeba k tomu, aby z nich bylo moţné vyříznout potřebný počet profilů k výrobě poţa-


17

dovaného počtu krbových vloţek Alfa 1. Druhý model bude vybírat vhodné rozřezávací schéma tak, aby byl minimalizován odpadní materiál. Oba modely budou obsahovat shodné omezující podmínky. Lišit se budou pouze v účelové funkci. Omezujícími podmínkami budou poţadované počty profilů, které chceme z výchozích polotovarů získat. 2.2.4

Řešení modelu

Model bude řešen v programu MS Excel za vyuţití doplňku Řešitel. Účelová funkce i omezující podmínky budou vytvořeny za pomoci funkce Skalární součin, poté budou v řešiteli definovány jednotlivé parametry a moţnosti. Pro kaţdý profil budou připraveny dva sešity. První bude řešit počet kusů výchozího polotovaru, druhý minimální odpad. Toto řešení bude zvoleno díky tomu, ţe konfigurace doplňku Řešitel je poměrně zdlouhavá a v jednom sešitě ji nelze vytvořit pro více úloh najednou. 2.2.5

Vyhodnocení výsledků

Po výpočtu jednotlivých modelů bude provedeno zhodnocení výsledků a jejich srovnání s postupem, který v současnosti pouţívá pan Bartl. 2.2.6

Případná aplikace výsledků

Ve finální části práce bude zhodnoceno, zda je vhodné zavádět metody operačního výzkumu do výroby v podniku Zámečnictví Martin Bartl. Tato práce je vypracována za účelem ověření pouţitelnosti těchto metod v praxi. Pokud budou výsledky vést k úsporám, bude pan Bartl navrhnutý systém implementovat.

18

Literární rešerše

3 Literární rešerše 3.1 Operační výzkum Operační výzkum je vědou o rozhodování (Gass, Assad, 2011, s. 2). V běţném ţivotě se velmi často setkáváme s rozhodováním, kterou variantu řešení určitého problému zvolit. Předmětem takového rozhodování je manaţerský problém (Plevný, Ţiţka, 2005, s. 10). Ten je moţné analyzovat ze dvou základních hledisek:  kvalitativní analýza – je zaloţena na zkušenostech a znalostech rozhodujícího,  kvantitativní analýza – je zaloţena na popisu problému pomocí numerických dat. Operační výzkum (jiným názvem operační analýza nebo ekonomicko-matematické metody) je mnoţina samostatných disciplín, které nachází své uplatnění právě v oblasti rozhodování o nějakém problému (Jablonský, 2007, s. 9; Dudorkin, 1988, s. 5). Přesněji lze říci, ţe operační výzkum nachází své uplatnění všude tam, kde dochází ke koordinaci či optimalizaci činností v rámci nějakého systému. Podstatou pouţití metod operačního výzkumu je omezení intuitivního rozhodování a odstranění subjektivního řešení problémů s jeho případnými negativními důsledky (Gros, 2003, s. 9). Cílem operačního výzkumu je nalezení mnoţiny řešení a identifikace nejlepšího z nich, tedy určení optimálního řešení (Holoubek, 2010, s. 5). Nalezené řešení můţe být řešením konečným nebo můţe slouţit pouze jako podklad pro další rozhodování řídícího pracovníka (Dudorkin, 1988, s. 5–6). 3.1.1

Vývoj

Počátky operačního výzkumu sahají do 30. let 20. století a jsou s nimi spojována zejména jména G. B. Danztig či L. V. Kantorovič. V této době byly formulovány první ekonomické optimalizační modely, které měly řešit tehdejší problémy plánovaného hospodářství v SSSR (Laščiak, 1990, s. 31). Rozmach přichází v období 2. světové války a to především ve Velké Británii a USA, kdy se těchto metod uţívalo v oblasti vojenských operací (Gass, Assad, 2011, s. 1). Další vývoj byl ovlivněn nástupem výpočetní techniky, která značně usnadnila výpočty a především minimalizovala čas, který je k výpočtům sloţitějších matematických problému zapotřebí (Jablonský, 2007, s. 9). V letech 1947–1949 vyvinul Dantzig společně se svými kolegy algoritmus, který slouţí k řešení úloh lineárního programování – simplexovou metodu. Počátky softwarového řešení úloh lineárního programování sahají do roku 1952, kdyby byl představen první program pro počítače IBM (Laščiak, 1990, s. 32–33). Dnes jiţ existuje široká škála programů, které nabízí příjemné uţiva-


19

telské rozhraní a jednoduchý systém definice modelů. Motivace k softwarovému řešení úloh lineárního programování, které minimalizuje matematickou sloţku modelování, je dána především urychlením procesu řešení, ale také snahou o rozšíření těchto metod mezi co největší okruh řídících pracovníků (Gros, 2003, s. 9).

3.2 Disciplíny operačního výzkumu Operační výzkum se zabývá mnoha typy rozhodovacích problémů. Díky tomu se postupně vyvinuly specifické metody řešení, ze kterých se staly relativně samostatné oblasti operačního výzkumu. Uvádí je následující výčet: 1.

Matematické programování – řeší problémy, ve kterých se jedná o nalezení optimálního řešení, které je dáno dosaţením extrému příslušné kriteriální funkce s přihlédnutím k omezujícím podmínkám.

2.

Vícekriteriální rozhodování – nalezení řešení úlohy je podmíněno více kriteriálními funkcemi, které nejčastěji stojí proti sobě. Snaţíme se o nalezení kompromisu mezi takovými funkcemi. Teorie grafů – grafy mohou prezentovat fungování určitého systému. Na jejich základě jsme schopni řešit úlohy, jako jsou nalezení nejkratší cesty v grafu, stanovení kritické cesty apod. Jejich vyuţití je především v oblasti plánování a řízení projektů. Teorie zásob – optimalizace zásob ve skladech především za účelem minimalizace nákladů, které jsou spojeny s přijímáním, udrţováním a vyskladňováním. Teorie hromadné obsluhy – předpokládá existenci poţadavků, které jsou v systému kladeny na obsluţné linky, které tyto poţadavky mají uspokojovat. Obsluţné linky mohou být poţadavky zahlceny a tak vznikají fronty. Smyslem optimalizace je v tomto případě určení poměru mezi stupněm vyuţití obsluţných linek a časem, kdy poţadavek čeká na uspokojení. Modely obnovy – uvaţuje systémy, ve kterých existují jednotky, které se postupně spotřebovávají nebo opotřebovávají a je nutné je po čase nahradit, případně opravit. Cílem optimalizace je v tomto případě odhadovat, kolik jednotek bude třeba nahradit v různých časových úsecích. Markovské rozhodovací procesy – zaměřuje se na systémy, které mohou nabývat v čase různých stavů. Pomocí této metody se snaţíme předpovědět, v kterém ze stavů se bude systém nacházet, neboli jak se bude systém chovat v konkrétním čase. Teorie her – popisuje systém jako hru, kde jednotlivé subjekty s protichůdnými zájmy upravují svoji strategii a chování v závislosti na ostatních.

3.

4.

5.

6.

7.

8.

(Jablonský, 2007, s. 13–15; Rašovský, 1990, s. 15)

20


3.3 Matematické programování Jestliţe analyzujeme a následně řešíme určitý problém pomocí metod operačního výzkumu, vyuţíváme u toho model tohoto systému. Při pouţití metod operačního výzkumu postupujeme obecně následujícím způsobem: 1. Pozorování systému – pro odhalení problému, který je třeba řešit, musíme celý systém prostudovat a pochopit fungování procesů, které v něm probíhají. Dudorkin tuto fázi přirovnává k vyšetření pacienta před zahájením léčby. Systém je třeba důkladně popsat a zváţit všechny relevantní okolnosti, které problém ovlivňují. 1. Formulace úlohy – stanovujeme cíl analýzy, tzn., definujeme cílový stav systému, kterého chceme dosáhnout. Stanovujeme kriteria pro hodnocení alternativ. V této fázi získáváme představu o tom, jak systém funguje a které faktory jej ovlivňují. Formulujeme tedy tzv. ekonomický model. 2. Tvorba matematického modelu a jeho verifikace – jde o činnost, na kterou neexistuje jednoznačný návod. Velmi záleţí na kreativitě a zkušenostech řešitele. Procesům, které v systému probíhají, přiřadíme proměnné, které nazýváme strukturní. Jejich význam musí být jasně definován. Na základě těchto proměnných sestavíme účelovou funkci. Okolnosti, které problém ovlivňují, nazýváme vlastní omezení modelu. 3.

Řešení modelu – výběr nejvhodnější varianty, tedy nalezení optimálního řešení. V praxi se vyuţívá počítačových programů, v nichţ jsou implementovány různé metody.

4.

Interpretace výsledků – výstupem procesu řešení bývají číselné hodnoty, které je třeba interpretovat, abychom pochopili jejich skutečný význam. Získané řešení můţeme srovnat s našimi předpoklady, zkušenostmi, zavedenými hypotézami. Implementace řešení – přímé pouţití získaných výsledků v praxi není příliš obvyklé. Nejčastěji slouţí nalezené řešení jako podklad pro změny, které se v systému realizují.

5.

(Plevný, Ţiţka, 2005, s. 11–12, 28–30; Jablonský, 2007, s. 10–13, 21–22; Dudorkin, 1988, s. 8; Rašovský, 1990, s. 17) 3.3.1

Matematický model

Matematický model je obrazem podstatných znaků a charakteristik reality, které jsou důleţité pro dosaţení řešení pomocí matematického aparátu (Laščiak, 1990, s. 15). Takový model přináší mnohdy jistá zjednodušení oproti realitě, všechny prvky totiţ není nutné uvaţovat. Model však musíme neustále kontrolovat, abychom nevyřadili i prvky reality, bez kterých by byl výpočet zkreslený. Čím je model blíţe realitě, tím je přesnější a náročnější na výpočet. Některé sloţité modely mohou být aţ neřešitelné (Laščiak, 1990, s. 11). Naopak jednoduché


21

modely jsou snazší na výpočet, ale jejich vypovídací hodnota bývá realitě velmi vzdálená. Výsledkem takového modelu můţe být i řešení zcela nepřijatelné. Dle Jablonského (2007, s. 10) patří mezi hlavní výhody matematického modelu oproti reálnému experimentu to, ţe:  Pouţitím modelu jsme schopni popsat veškeré moţnosti řešení, které mohou nastat.  Pouţití modelu značně sniţuje čas potřebný k získání řešení, toho je docíleno především díky vyuţití výpočetní techniky.  Parametry modelu lze snadno měnit a tím reagovat například na změnu omezujících faktorů, popřípadě doplnit proměnné, které jsme na počátku opomněli.  Hodnota nákladů vynaloţených na model můţe být vysoká, na experiment s reálným systémem by však byla několikanásobně vyšší. Matematický model je chápán jako jedna nebo více funkcí, ke které existují podmínky rozhodování (vlastní omezení) a to ve formě rovnic nebo nerovnic (Laščiak, 1990, s. 15). Cílem je nalezení extrémní hodnoty dané kriteriální funkce, respektive funkcí, na mnoţině všech přípustných řešení soustavy. Modely řešené v této práci jsou deterministické a statické, tzn., neobjevuje se v nich prvek náhody a v čase se nemění (Rašovský, 1990, s. 9). Dle Plevného a Ţiţky (2005, s. 16–17) můţeme v matematickém modelu vstupy rozdělit na řiditelné – rozhodovací proměnné a neřiditelné vstupy – faktory prostředí. Řiditelné vstupy můţeme ovlivňovat a nastavit je tak, abychom dosáhli poţadovaného cíle. Jedná se například o počet výrobků, které budeme vyrábět. Neřiditelné vstupy není moţné ovlivňovat. Jde například o spotřebu času, surovin, případně o kapacity, kterých je moţno vyuţít apod. Řešením úlohy je pak nalezení konkrétních hodnot řiditelných proměnných, které vedou k dosaţení cílového stavu.

3.4 Základní typy úloh lineárního programování Úlohy matematického programování dělíme na úlohy lineárního a nelineárního programování (Plevný, Ţiţka, 2005, s. 14). Úlohu můţeme nazvat lineární, pouze pokud všechny kriteriální funkce i omezující podmínky tvoří lineární výrazy. To znamená, ţe proměnné jsou pouze v první mocnině, netvoří argument ţádné funkce a nesmí se mezi sebou násobit (Plevný, Ţiţka, 2005, s. 27). Pokud je alespoň jedna rovnice či nerovnice tvořena nelineárním výrazem, nazýváme úlohu nelineární. Řešení takových úloh je velmi sloţité a získaná řešení bývají pouze přibliţná (Plevný, Ţiţka, 2005, s. 14–15).

22


Typickými úlohami, které se v oblasti lineárního programování objevují, jsou:  Úlohy o optimálním vyuţití výrobních činitelů (optimální alokaci zdrojů) – jde o nalezení optimální struktury výroby s přihlédnutím k omezeným zdrojům, za cíl si klademe minimalizaci nákladů nebo maximalizaci zisku.  Úlohy finančního plánování – za cíl si klademe nalezení optimální struktury investic, která bude maximalizovat výnos nebo minimalizovat riziko ztráty.  Plánování reklamy – hledáme optimálním alokaci finančních zdrojů mezi jednotlivá media, která nám umoţní oslovit poţadovaný počet potenciálních zákazníků.  Úlohy o optimální směsi – hledáme optimální poměr jednotlivých surovin pro výslednou směs, kriteriem bývá minimální cena výsledné směsi.  Úlohy o optimálním řezání materiálu (řezné úlohy) – řezání výchozího materiálu na kratší části s minimálním počtem pouţitých polotovarů, odpadem nebo počtem řezů.  Rozvrhování pracovníků – přiřazování pracovníků na pracovní místa s přihlédnutím k jejich vzdělání, minimálnímu potřebnému počtu pracovníků na směně apod.  Úlohy dopravní (distribuční) – uspokojení poţadavků odběratelů s ohledem na omezené kapacity dodavatelů a co nejniţšími přepravními náklady. (Laščiak, 1990, s. 18–24; Dudorkin, 1988, s. 13; Jablonský, 2007, s. 26–28)

3.5 Základní pojmy úlohy lineárního programování Lineární programování je proces, pomocí kterého hledáme optimální řešení daného problému za předpokladu existence více moţných řešení a konečného počtu omezujících podmínek, které představují nutnost splnění určitého poţadavku (Rašovský, 1990, s. 11). Důleţitá je rovněţ definice optimalizačního kriteria, podle kterého můţeme jednotlivá řešení vyhodnotit. Cílem úlohy lineárního programování je určení vektoru řešení

 x ( x1 , x2 ,, xn )

(1)

který minimalizuje nebo maximalizuje hodnotu z hlediska funkce

z  f ( x1 , x2 ,, xn )

(2)


23

za podmínek

g1 ( x1 , x 2 ,, x n )  b1 g 2 ( x1 , x 2 ,, x n )  b2  g m ( x1 , x 2 ,, x n )  bm xj  0

(3)

(4)

pro 𝑖 = 1, 2, … , 𝑚 a 𝑗 = 1, 2, … , 𝑛 (Laščiak, 1990, s. 28–29; Rašovský, 1990, s. 11). V modelu představuje 𝑛 počet řiditelných (strukturních) proměnných 𝑥𝑗 a 𝑚 počet omezujících podmínek, 𝑏𝑖 představují hodnoty vlastních omezení (Plevný, Ţiţka, 2005, s. 18; Jablonský, 2007, s. 23). Funkci 𝑓 (2) říkáme funkce účelová (optimalizační, preferenční) a její hodnota je pro nás kriteriem pro výběr optimálního řešení (Dudorkin, 1988, s. 6). Úlohu, kde je třeba dosáhnout co nejvyšší (extremní) hodnoty účelové funkce 𝑓 (2), nazveme úlohou maximalizační. V případě, ţe poţadujeme naopak co nejniţší hodnotu účelové funkce 𝑓 (2), nazýváme úlohu minimalizační (Laščiak, 1990, s. 30). Funkce 𝑔1 , 𝑔2 , … , 𝑔𝑚 (3) představují vlastní omezení, která jsou v řešení problému důleţitá a nazýváme je omezující podmínky (Plevný, Ţiţka, 2005, s. 18). Relační operátory v těchto podmínkách mohou nabývat tří podob a to ≤, ≥ nebo =. Poslední součástí modelu je podmínka nezápornosti (4), pokud by v modelu nebyla uvedena, výsledek by mohl být nesmysl. Nelze totiţ vyrábět záporné mnoţství výrobků apod. Podmínku nezápornosti řadíme mezi tzv. obligátní podmínky, tedy takové, které určují obor hodnot jednotlivých proměnných.

3.6 Možná řešení úloh lineárního programování Vektor 𝑥 = 𝑥1 , 𝑥2 , … 𝑥𝑛 , který vyhovuje podmínkám (3) i (4), tedy všem podmínkám modelu, je přípustným řešením dané úlohy. Takových řešení můţe být více, poté tvoří mnoţinu přípustných řešení (Laščiak, 1990, s. 28). Podmnoţinou přípustných řešení jsou řešení bazická, poznáme je podle toho, ţe obsahují ve vektoru řešení 𝑥 nejvýše 𝑚 kladných proměnných, kde 𝑚 je počet omezujících podmínek v modelu (3) (Laščiak, 1990, s. 112). Dle Holoubka (2010, s. 18) označujeme bazická řešení jako degenerovaná v případě, ţe obsahují ve vektoru řešení 𝑥 méně neţ 𝑚 kladných sloţek. Bazické řešení bude nedegenerované, je-li počet kladných sloţek ve vektoru řešení roven právě 𝑚. Optimálním řešením úlohy označíme takové bazické řešení, při kterém dosahuje účelová funkce 𝑓 poţadovaného extrému (Plevný, Ţiţka, 2005, s. 50). Vektor 𝑥 = 𝑥1 , 𝑥2 , … 𝑥𝑛 , který nevyhovuje alespoň jedné podmínce (3) nebo (4) je řešením nepřípustným.

24


V případě, ţe je mnoţina přípustných řešení prázdná, říkáme, ţe úloha je neřešitelná.

3.7 Základní tvar úlohy lineárního programování Základní tvar úlohy lineárního programování můţeme zapsat v tomto tvaru

z( x)  c1 x1  c2 x2    cn xn

(5)

za podmínek

a11 x1  a12 x2    a1n xn  b1 a 21 x1  a 22 x2    a 2 n xn  b2  a m1 x1  a m 2 x2   a mn xn  bm xj  0

(6)

(7)

pro 𝑖 = 1, 2, … , 𝑚 a pro 𝑗 = 1, 2, … , 𝑛 (Laščiak, 1990, s. 67). Lineární rovnice (5) představuje účelovou funkci, rovnice, častěji nerovnice, (6) jsou omezující podmínky a poslední podmínkou je opět podmínka nezápornosti (7). Abychom mohli model sestavit, musíme znát určité konstanty, které budeme označovat jako:  𝑐𝑗 – pro 𝑗 = 1,2, … , 𝑛 označujeme jako koeficienty účelové funkce a přiřadíme je kaţdé strukturní proměnné v účelové funkci,  𝑎𝑖𝑗 – pro 𝑖 = 1,2, … , 𝑚 a 𝑗 = 1,2, … , 𝑛 budeme nazývat koeficienty podmínek (strukturní koeficienty), vyskytují se u proměnných v omezujících podmínkách a vyjadřují vztahy mezi 𝑗-tou proměnnou a 𝑖-tou omezující podmínkou,  𝑏𝑖 – pro 𝑖 = 1,2, … , 𝑛 jsou hodnoty pravé strany omezujících podmínek a vyjadřují velikost příslušného omezení. (Plevný, Ţiţka, 2005, s. 50), (Jablonský, 2007, s. 23)

3.8 Řezné úlohy V těchto úlohách chceme nejčastěji dosahovat co nejniţších nákladů na pouţitý materiál. Z toho logicky odvodíme, ţe takového materiálu potřebujeme spotřebovat co nejméně. Za kriterium účelové funkce můţeme tedy dosadit počet rozřezaných polotovarů výchozího materiálu (Plevný, Ţiţka, 2005, s. 45–46). Abychom výchozího materiálu spotřebovali co nejméně, je třeba vypracovat rozřezávací schéma. Tím definujeme způsob, jakým polotovar dané délky bu-


25

deme řezat. Kaţdé variantě řezu v rozřezávacím schématu přiřadíme proměnnou 𝑥𝑖 , která bude reprezentovat, kolikrát 𝑖-tou variantu řezného plánu vyuţijeme. Pokud chceme minimalizovat počet rozřezaných polotovarů, musí být logicky účelová funkce minimalizační. Jejím výstupem bude celkový počet výchozích polotovarů, které budou rozřezány. Tedy proměnná 𝑥1 bude představovat počet kusů polotovaru rozřezaných dle první varianty řezu, 𝑥2 bude počet kusů polotovarů rozřezaných dle druhé varianty aţ proměnná 𝑥𝑛 ,která bude představovat počet kusů polotovarů rozřezaných dle varianty 𝑛. V omezujících podmínkách je nutné definovat, kolik kusů profilů, které chceme z výchozího polotovaru získat, budeme potřebovat. Poté zohledníme podmínku nezápornosti, a protoţe výsledek by měl být v celých kusech, zavedeme rovněţ podmínku celočíselnosti.

3.9 Simplexová metoda Základní věta lineárního programování říká, ţe pokud má úloha optimální řešení, je takové řešení jedním z přípustných bazických řešení (Plevný, M., Ţiţka, M., 2005, s. 77). Pří hledání optimálního řešení se tedy stačí soustředit pouze na ta bazická, coţ je principem simplexové metody. Simplexová metoda je nejznámější a nejpouţívanější algoritmus k řešení úloh lineárního programování. (Laščiak, 1990, s. 109; Plevný, Ţiţka, 2005, s. 71). Předpokladem je určení alespoň jednoho přípustného bazického řešení. Zároveň musíme znát pravidlo, podle kterého definujeme, zda se jedná jiţ o řešení optimální. Pokud takto nalezené řešení optimální nebude, přejdeme k jinému bazickému řešení, které bude optimálnímu bliţší. Po konečném počtu kroků tedy optimální řešení nalezneme nebo budeme konstatovat, ţe úloha je neřešitelná (Laščiak, 1990, s. 110). 3.9.1

Normované tvary

Všechny úlohy lineárního programování lze převést na soustavu lineárních rovnic (5) (6), řešením takové soustavy získáme řešení celé úlohy (Laščiak, 1990, s. 111). Jakoukoliv úlohu matematického (lineárního) programování je moţné převést na normované tvary. Jedná se o převod na:  standardní tvar,  kanonický tvar. Standardní tvar získáme jednoduchou úpravou tím, ţe zavedeme doplňkové proměnné. Obecně lze postup popsat následujícím způsobem.

26


Z nerovnice

a11x1  a12 x2    a1n xn  b1

(8)

vytvoříme rovnici odečtením doplňkové proměnné od levé strany, tedy

a11x1  a12 x2    a1n xn  xn1  b1

(9)

případně k nerovnici

a11x1  a12 x2    a1n xn  b1

(10)

doplňkovou proměnnou naopak přičteme, získáme tedy

a11x1  a12 x2    a1n xn  xn1  b1

(11)

V účelové funkci se doplňková proměnná objevuje s nulovým koeficientem účelové funkce 𝑐𝑗 . Tato proměnná představuje rozdíl mezi levou a pravou stranou nerovnice, z ekonomického hlediska ji můţeme interpretovat jako nespotřebované mnoţství některého ze zdrojů (při původním tvaru omezující podmínky 𝑎𝑖 𝑥𝑗 ≤ 𝑏𝑖 ) nebo naopak mnoţství, které jsme spotřebovali nad minimální limit stanovený omezující podmínkou (při tvaru 𝑎𝑖 𝑥𝑗 ≥ 𝑏𝑖 ) (Plevný, Ţiţka, 2005, s. 71–76; Jablonský, 2007, s. 46). Pro aplikaci simplexové metody je dále nutné model převést na kanonický tvar. Ten vychází z tvaru standardního, to znamená, ţe všechny omezující podmínky jsou ve tvaru rovnic. Kanonický tvar musí zaručovat, ţe všechny pravé strany omezujících podmínek 𝑏1 , … , 𝑏𝑚 jsou nezáporné a v matici koeficientů podmínek se vyskytuje jednotková matice. Nezápornost pravých stran zajistíme tak, ţe příslušnou rovnici omezující podmínky v případě potřeby vynásobíme hodnotou −1. Jestliţe výsledný tvar neobsahuje jednotkovou matici, získáme ji přidáním umělé proměnné. Tu doplníme do všech rovnic omezujících podmínek, které neobsahují jednotkový vektor. Tato proměnná však nemá na rozdíl od doplňkové ţádný ekonomický význam. Společné mají to, ţe nesmí ovlivnit účelovou funkci. Koeficientům umělých proměnných v kriteriální funkci tedy musíme přiřadit velmi nevýhodné hodnoty, tzv. prohibitivní sazby. Ty zajistí, ţe v průběhu výpočtu budou umělé proměnné z báze vyřazeny (Holoubek J., 2010, s. 41). Pokud řešíme problém bez vyuţití softwaru, není třeba konkrétní hodnoty stanovovat, dosadíme za něj například řecké písmeno ω (Dudorkin, 1988, s. 31). Z výše uvedeného je logické, ţe při nalezení řešení modelu musí mít všechny umělé proměnné hodnotu nula, jinak budou mít na účelovou funkci vliv (Plevný, Ţiţka, 2005, s. 74–76). Pokud je alespoň jedna z nich nenulová, znamená to, ţe úloha nemá řešení.


27

Úloha v kanonickém tvaru poté obsahuje kupř. takovýto tvar omezujících podmínek  1x1  1x 2  1x3  0 x 4  0 x5  0 x6  3 2 x1  1x 2  0 x3  1x 4  1x5  0 x6  4

(12)

1x1  2 2  0 x3  0 x 4  0 x5  1x6  4

který vyuţijeme k určení výchozího přípustného bazického řešení. Všem proměnným, které netvoří jednotkovou submatici v kanonickém tvaru, přiřadíme hodnotu nula. V našem případě (12) se jedná o proměnné 𝑥1 , 𝑥2 , 𝑥4 . Tím nalezneme jedno z mnoha moţných přípustných řešení, kterým je vektor  x  (0,0,3,0,4,4)

(13)

Zároveň se jedná o řešení bazické – nedegenerované, protoţe vektor řešení obsahuje právě tři kladné proměnné. Tyto proměnné nazveme bazické, ostatní nebazické (Rašovský, 1990, s. 49). 3.9.2

Postup simplexové metody

Přechod od jednoho získaného bazického řešení k jinému je realizován prostřednictvím výměny vektorů v bázi (Dudorkin, 1988, s. 22). Vektor, který není optimálním řešením, vyloučíme a zařadíme jiný, který testujeme. Plevný a Ţiţka (2005, s. 78) obecný postup simplexové metody formulují takto: 1. 2. 3. 4. 5.

Nalezení výchozího přípustného bazického řešení. Provedení testu optimality, tj. určení, zda je nalezené řešení optimální. Pokud není, pokračujeme bodem č. 3, jinak výpočet ukončíme. Určení proměnné, která bude do báze vstupovat. Určíme proměnné, která bude z báze vystupovat. Přepočet simplexové tabulky na novou bázi a opakování postupu od bodu 2.

Přechod k jinému bazickému řešení je realizován pomocí úprav v simplexové tabulce, ve které je zapsán matematický model problému (Plevný, Ţiţka, 2005, s. 78). Hodnoty 𝐶𝐵 v simplexové tabulce reprezentují koeficienty účelové funkce jednotlivých bazických proměnných 𝑥1 … 𝑥𝐵𝑚 , 𝛽1 … 𝛽𝑚 představují hodnoty bazických proměnných. Hodnoty 𝑎11 aţ 𝑎𝑚𝑛 zapisujeme dle řádků jednotlivých omezujících podmínek a představují strukturní koeficienty příslušného kanonického tvaru úlohy. Algoritmus simplexové metody je sestaven tak, ţe nepočítá se zápornými hodnotami proměnných, proto v simplexové tabulce není obsaţena podmínka nezápornosti (Plevný, Ţiţka, 2005, s. 78–79; Laščiak, 1990, s. 127). Poslední řádek tabulky obsahuje krok úlohy, hodnotu účelové funkce

28


v daném kroku a hodnoty indexních čísel. Nazýváme jej indexní řádek (Rašovský, 1990, s. 55). Tab. 1

Simplexová tabulka

𝐶𝐵

báze

𝑐1

𝑐2

…

𝑐𝑛

𝑥1

𝑥2

…

𝑥𝑛

𝐶𝐵1

𝑥1 = 𝛽1

𝑎11

𝑎12

…

𝑎1𝑛

𝐶𝐵2

𝑥2 = 𝛽2

𝑎21

𝑎22

…

𝑎2𝑛

⋮

⋮

⋮

⋮

𝐶𝐵𝑚

𝑥𝐵𝑚 = 𝛽𝑚

0. krok Hodnota ÚF

⋮

𝑎𝑚1 𝑎𝑚2 … 𝑎𝑚𝑛 ∆1

∆2

…

∆𝑛

(Holoubek, 2010, s. 41; Plevný, Ţiţka, 2005, s. 78) Přechod k jinému bazickému řešení provedeme tak, ţe jeden ze sloupců, který je v jednotkové submatici nahradíme jiným, který musíme do jednotkové podoby přetransformovat (Jablonský, 2007, s. 54). Který ze sloupců bude do báze vstupovat, určíme dle hodnoty indexního čísla ∆𝑗 (Plevný, Ţiţka, 2005, s. 79). Tato hodnota určuje, o kolik by se změnila hodnota účelové funkce, kdybychom do báze přidali jednu jednotku nebazické proměnné 𝑥𝑗 a vypočítáme ji pomocí vztahu (14)  j  C Bm  amn  c j

(14)

pro 𝑗 = 1, 2, … , 𝑛 (Laščiak, 1990, s. 134; Holoubek 2010, s. 41–42). Po provedení testu optimality a konstatování, ţe dané řešení není optimální, volíme proměnnou, která nejvíce test optimality porušuje (Rašovský, 1990, s. 55–56). Určíme ji pomocí indexního čísla a sloupec, ve kterém se nachází, nazveme klíčový. Pro minimalizační funkci je to taková proměnná, které přísluší maximální kladná hodnota indexního čísla. U maximalizační funkce naopak minimální záporná hodnota indexního čísla. Klíčový sloupec představuje proměnnou, kterou budeme do báze zařazovat a musíme jej tedy transformovat do jednotkové podoby (Plevný, Ţiţka, 2005, s. 80). K tomu je potřeba určit pivot, neboli pozici v zařazovaném sloupci, na které chceme vytvořit hodnotu 1. Tím zároveň určíme i vystupující proměnnou. Hledáme tedy ve všech řádcích simplexové tabulky takovou hodnotu 𝑎𝑖𝑗 , která je kladná a zároveň je v poměru k hodnotě 𝑖-té bazické proměnné, tedy v poměru 𝛽𝑖 𝑎𝑖𝑗 , minimální. Toto pravidlo platí pro maximalizační i minimalizační úlohy. Pivot musí být nezáporný, jinak by při jeho transformaci na hodnotu 1 došlo k tomu, ţe by se příslušná bazická proměnná 𝛽𝑖 stala zápornou, coţ by vedlo


29

k porušení podmínky nezápornosti. Řádek, ve kterém se pivot nachází, nazveme klíčový řádek. Pokud nelze klíčový řádek nebo klíčový sloupec určit jednoznačně, zvolíme jej libovolně (Rašovský, 1990, s. 56). Nyní provedeme transformaci sloupce do jednotkové podoby. Řádek, ve kterém se nachází pivot (klíčový řádek), vynásobíme převrácenou hodnotou tak, abychom na místě pivotu získali jedničku (Laščiak, 1990, s. 114). Jednotkovou podobu klíčového sloupce vytvoříme aplikací Gaussovy eliminační metody, určujícím prvkem bude pivot (Rašovský, 1990, s. 56). Po transformaci sloupce do jednotkové podoby zbývá provést opět test optimality (Plevný, Ţiţka, 2005, s. 81). Pokud se v indexním řádku nevyskytuje indexní číslo, které test optimality porušuje, nemůţeme určit další proměnnou, kterou bychom do báze zařadili. Pro maximalizační úlohu je tedy optimální řešení takové, kdy jsou všechny hodnoty indexních čísel pro nebazické proměnné ∆𝑗 ≥ 0 a hodnoty indexních čísel pro bazické proměnné ∆𝑗 = 0. Pro minimalizační funkci nacházíme optimální řešení, pokud jsou všechny hodnoty indexních čísel pro nebazické proměnné ∆𝑗 ≤ 0, tedy nekladné a hodnoty indexních čísel pro bazické proměnné ∆𝑗 = 0 (Laščiak, 1990, s. 128–129). V opačném případě měníme bázi a pokračujeme ve výpočtu. V případě, ţe je indexní číslo pod nebazickou proměnnou rovno nule, má úloha další bazické přípustné optimální řešení a nekonečně mnoho nebazických optimálních řešení (Rašovský, 1990, s. 51). Další řešení zjistíme tak, ţe nebazickou proměnnou, pod kterou se nachází nulové indexní číslo, zařadíme do báze. Pokud se při řešení úlohy pomocí simplexové metody vyskytne degenerace, můţe se objevit problém zacyklení (Dudorkin, 1988, s. 29). Projeví se tak, ţe zařazením nového vektoru do báze se dostáváme k řešení, které jsme jiţ podrobili testu optimality a zjistili jsme, ţe není optimální. V praxi je však tento problém poměrně vzácný.

3.10 Celočíselné programování Poţadavek celočíselnosti bývá kladen v úlohách, kde jednotlivé proměnné představují takové faktory, které není moţné dělit. Jedná se zejména o počty zvířat, osob, strojů, ale např. i polotovarů (Dudorkin, 1988, s. 46). Smíšené celočíselné úlohy obsahují poţadavek celočíselnosti pouze pro některé proměnné, úplné (ryzí) celočíselné úlohy kladou poţadavek celočíselnosti na veškeré v nich obsaţené proměnné. Speciálním typem jsou úlohy bivalentní, kde proměnné nabývají pouze hodnot 0 a 1. Jak získat řešení, které by respektovalo podmínku celočíselnosti? Tzv. naivních metod, které výsledek zaokrouhlují, není moţné pouţít. Jejich prostřednictvím bychom se mohli dostat do oblasti nepřípustných řešení nebo by řešení bylo zkreslené (Dudorkin, 1988, s. 47). Rozlišujeme dva základní typy metod pro stanovení celočíselného řešení:  metody přesné – řadíme sem metodu sečných nadrovin, metodu větvení a mezí,

30


 metody přibliţné – jsou vytvořeny za účelem řešení speciálních druhů úloh matematického programování, např. Vogelova aproximační metoda pro řešení dopravních úloh. 3.10.1

Metoda větvení a mezí

Holoubek (2010, s. 74–75) definuje obecný postup tak, ţe pokud nebude řešení získané simplexovou metodou celočíselné, přidáme do úlohy další omezující podmínky pro některou z neceločíselných proměnných. To rozdělí původní úlohu lineárního programování na dvě, které následně řešíme zvlášť. Pokud nalezneme optimální celočíselné řešení u obou těchto úloh, výpočet končí, pokud ne, postup opakujeme, přidáváme opět další omezující podmínky. Takto pokračujeme do té doby, neţ určíme celočíselné řešení nebo dospějeme ke tvrzení, ţe úloha celočíselné řešení nemá.

3.11 Zpracování úloh matematického programování na PC První programy na řešení úloh operačního výzkumu se sestavovaly individuálně a vyznačovaly se omezeným pouţitím (Laščiak, 1990, s. 611–612). Změna nastala aţ teprve s příchodem počítačů třetí generace, kdy se objevily programové systémy, které byly schopny komplexní analýzy úlohy a pruţné změny omezujících podmínek. Plevný a Ţiţka (2005, s. 19–24) dělí software pro zpracování úloh operačního výzkumu na dvě základní skupiny:  Software podporující optimalizační výpočty – do této skupiny řadíme např. tabulkové procesory, které obsahují nástavbu v podobě balíčku nástrojů k řešení úloh matematického programování. Dále sem spadají systémy DSS (Decision Support Systems), které představují sbírku modelů a dat vhodných pro různé rozhodovací situace. Tyto systémy jsou však velmi drahé na pořízení i na údrţbu.  Software specializovaný pro řešení optimalizačních modelů – profesionální programy. Mezi tuto skupinu řadíme STORM, LINDO, LINGO, DecisionPro, What'sBest!.

3.12 Optimalizace v programu MS Excel 2007 Součástí běţné instalace MS Excelu je i doplněk označovaný jako Řešitel (Solver). Jeho základní verze je určena spíše k řešení jednodušších úloh. V případě náročnějších problémů je výhodnější vyuţít výkonnějších verzí Premium Solver nebo Premium Solver platform, které jsou však na rozdíl od Řešitele zpoplatněny (Plevný, Ţiţka, 2005, s. 21–22). Funkcí doplňku Řešitel je řešení úloh lineárního i nelineárního programování (Lauber, Jablonský, 1997, s. 7–12).


31

Na začátku je třeba definovat data v novém sešitě. Uspořádání dat záleţí pouze na uţivateli. Jedinou podmínkou je samozřejmě to, ţe musíme do programu zadat veškeré hodnoty, které jsou pro výpočet modelu potřebné. Strukturním proměnným přiřazujeme nulové počáteční hodnoty. Omezující podmínky potřebujeme zapsat tak, jak jsou uvedeny v matematickém modelu. K tomu nám poslouţí funkce Excelu Skalární součin, která dokáţe vynásobit zadané strukturní koeficienty s proměnnými. Tím vznikne levá strana omezující podmínky. Pravé strany definujeme vstupem z klávesnice do příslušné buňky. Definice účelové funkce pak probíhá podobným způsobem, opět vyuţíváme funkce Skalární součin, mezi sebou tedy násobíme hodnoty proměnných a koeficienty účelové funkce podle zadání příslušného modelu. Po zapsání dat přistoupíme k aktivaci doplňku Řešitel. V programu Excel 2007 se nachází pod kartou Data v oddílu Analýza. Pokud tam doplněk není, je třeba jej doinstalovat. To provedeme klikem na Tlačítko Office – Moţnosti aplikace Excel – Doplňky – zde v dolní části okna vybereme Spravovat: Doplňky aplikace Excel a klikneme na Přejít… V novém okně Doplňky zaškrtneme pole Řešitel a stiskneme OK. Doplněk tím nainstalujeme a nyní jej jiţ najdeme na příslušné záloţce.

Obr. 1

Parametry Řešitele

Po spuštění doplňku je třeba nastavit jeho parametry (Lauber, Jablonský, 1997, s. 12–15), především se jedná o:  Nastavit buňku – zvolíme buňku, do které jsme umístili vzorec účelové funkce.  Rovno neboli charakter kriteria optimality – volíme minimalizační nebo maximalizační funkci. Pokud zvolíme moţnost Hodnota, definujeme, jakou hodnotu by měla účelová funkce příslušného modelu nabývat.  Měněné buňky – volíme oblast strukturních proměnných modelu.

32


 Omezující podmínka – definujeme veškeré omezující podmínky, které se v modelu nachází. Nejprve klikneme na Přidat, poté v novém okně s názvem Přidat omezující podmínku do pole Odkaz na buňku vybereme buňku, která obsahuje vzorec příslušné omezující podmínky, který jsme definovali jiţ dříve nebo konkrétní proměnnou, ke které se podmínka vztahuje. Dále vybereme příslušný relační operátor a vstupem z klávesnice zadáme do pole Omezující podmínka pravou stranu omezující podmínky, případně zvolíme buňku, která tuto hodnotu obsahuje. Při výběru relačního operátoru můţeme vybrat volbu celé, která definuje podmínku celočíselnosti. Doplněk Řešitel pouţívá pro stanovení celočíselných řešení metodu větvení a mezí.

Obr. 2

Omezující podmínky

 Menu Moţnosti – obsahuje nastavení doplňku Řešitel. V našem případě je vhodné nastavit hodnoty Maximální čas a Iterace na 32767, tedy na maximum. Limitní čas určuje dobu, po které je výpočet přerušen a uţivatel je nucen potvrdit pokračování. Iterace určuje počet iterací, po kterých je výpočet přerušen a uţivatel musí potvrdit jeho pokračování. Dále je vhodné zaškrtnout volbu Lineární model, která výrazně urychluje výpočet úloh lineárního programování. Implicitně je tato volba vypnuta. Pro lineární úlohy pouţívá program standardní simplexovou metodu. Zároveň zaškrtneme volbu Nezáporná čísla, která definuje podmínky nezápornosti. Ostatní volby nejsou pro cíl této práce důleţité. Nyní můţeme přistoupit k vlastnímu řešení modelu, zahájíme jej stisknutím tlačítka Řešit. Výstupem je další dialogové okno s názvem Výsledky řešení. V tomto okně vidíme zprávu o tom, zda bylo nalezeno optimální řešení, tedy takové, které splňuje všechny omezující podmínky. Volbou Uchovat řešení a stisknutím OK vypíše program jednotlivé hodnoty proměnných do buněk sešitu, které jsme v nastavení zadali do pole Měněné buňky. V návaznosti na tom se díky definovaným vzorcům vypočtou hodnoty omezujících podmínek a hodnota účelové funkce.


33

4 Charakteristika podniku a současného stavu výroby 4.1 Zámečnictví Martin Bartl Zámečnictví Martin Bartl je malý podnik, sídlící ve městě Dolní Kounice, které se nachází asi 30 km od Brna. Jeho specializací je výroba teplovodních krbových vloţek, krbových vloţek se zadním přikládáním, teplovzdušných, krbových a horkovzdušných kamen, grilů s udírnou i větších grilů na sele. Lze domluvit i výrobu na zakázku. Více o produktech najdeme na internetových stránkách http://www.zamecnictvi-bartl.cz/. Podnik je situován v dílně, jejíţ prostory má majitel podniku v nájmu. V současné době zaměstnává tři zaměstnance na plný úvazek. Výroba probíhá pomocí vlastních strojů i nástrojů. Díky tomu, ţe podnik rozjel teprve nedávno internetové stránky a začal se více zaměřovat na marketingovou činnost, je logické, ţe nebylo třeba přemýšlet o vyuţití metod operačního výzkumu. V dřívějším období byly běţně přijímány maximálně dvě objednávky týdně. Nyní se jiţ začíná projevovat dobré jméno, které společnost u svých spokojených zákazníků vybudovala. Objednávek rapidně přibývá a mezi zákazníky se začínají vyskytovat i společnosti. Objevují se zakázky, které jiţ nepředstavují pouze kusovou výrobu, ale i série stejných výrobků. V této oblasti jiţ metody operační výzkumu mohou nalézt své uplatnění.

4.2 Výrobní proces Výroba teplovodních krbových vloţek je sofistikovaný proces, který vyţaduje mnoho zkušeností a znalostí. V práci se zaměříme na teplovodní krbovou vloţku Alfa 1. Ta je předmětem zakázky, kterou Zámečnictví Martin Bartl očekává v letních měsících.

Obr. 3

Teplovodní krbová vloţka Alfa 1

Alfa 1 je vyráběna z pěti různých profilů. Jejich popis je uveden v tabulce č. 2.

34


Mimo těchto profilů jsou k výrobě pouţity i další polotovary, jako nerezová kulatina pro kliku dvířek a ovládání klapky kouřovodu či ocelové deskové profily, které tvoří vlastní tělo krbové vloţky. Těmi se v práci zabývat nebudeme, jejich rozměry jsou tak malé, ţe se všechny dají vyříznout z jednoho polotovaru nebo se nakupují přesně na míru. Tab. 2

Alfa 1 – druhy profilů

Profil (mm) Čtvercový profil (jekl) 50 × 50 Čtvercový profil (jekl) 100 × 100 Plochý profil 50×10 Plochý profil 50×5 Hranol 10×10

Počet profilů potřebných na výrobu jedné krbové vloţky Alfa 1 (ks)

Poţadovaný rozměr jednoho profilu (mm)

Potřebný počet profilů na výrobu 24 kusů krbových vloţek Alfa 1 (ks)

4

450

96

3

600

72

2 2 2 1

600 450 530 650

48 48 48 24

2

400

48

2 1 2

400 320 100

48 24 48

Polotovary jsou nakupovány od dvou dodavatelů. Těmi jsou Eika Znojmo, a. s., Brno a Hutní materiál Fe-Besta, Pohořelice. V současnosti se materiál nakupuje do malých zásob, které jsou doplňovány v náhodných časových intervalech podle potřeby výroby. K získání profilů poţadovaných délek se musí polotovary rozřezat. Materiál se řeţe na poloautomatické kloubové pásové pile. Obsluha musí polotovar upnout do čelistí, zvolit posuv, tedy rychlost, kterou bude řezný pás zajíţdět do materiálu a pak čekat, dokud se materiál neuřízne. Poté se řezný pás sám zastaví a rameno pily se vysune. Obsluha uvolní výchozí polotovar z čelistí, posune jej o poţadovanou délku profilu a opět materiál upne. Pak se celý proces můţe opakovat. Před samotným řezáním se sestavuje řezný plán neboli rozřezávací schéma. Sestavuje se zpravidla v pondělí, kdy se rozvrhuje výroba a nakupuje materiál na celý týden. Vedoucí dílny zkontroluje objednávky produktů, tj. finálních výrobků a podle toho vyhodnotí, kolik a jaké druhy profilů budou potřeba. S přihlédnutím k aktuálnímu stavu zásob se poté zakoupí výchozí polotovary.


35

Na základě získaných informací o výrobním plánu na daný týden se sestavuje řezný plán. Ten pak dostane obsluha pily a řeţe podle něj jednotlivé polotovary. Nařezané profily se dále odevzdají svářeči a ten z nich vytváří těla objednaných výrobků.

4.3 Zakázka Na srpen roku 2013 je rozjednána zakázka na výrobu 24 kusů teplovodních krbových vloţek Alfa 1. Uvedená situace představuje šanci, jak prakticky prokázat přínos implementace metod operačního výzkumu. K tvorbě matematického modelu je však potřeba mnoţství času a především znalostí v příslušném oboru. Je tedy mým úkolem dokázat panu Bartlovi, ţe tyto metody opravdu fungují a seznámit ho prostřednictvím této práce s postupem tvorby optimálního řezného plánu.

4.4 Volba výchozích polotovarů Na počátku výrobního procesu je třeba zvolit, jakou délku výchozího polotovaru budeme vyuţívat. Standardně jsou objednávány dvě délky výchozích polotovarů a to 6000 mm nebo 2000 mm. V případě čtvercového profilu 50×50 mm bude při pouţití výchozího polotovaru délky 6000 mm vznikat odpad 150 mm, který je menší neţ při vyuţití výchozího polotovaru v délce 2000 mm. V obou případech se vzniku odpadu nevyhneme. Pro další profil, tedy 100×100 mm, volíme délku výchozího polotovaru 6000 mm, při jehoţ vyuţití ţádný odpad nevzniká. Pro zbylé typy profilů budeme uvaţovat oba typy polotovarů. Tab. 3

Výchozí polotovary

Profil (mm) Čtvercový profil (jekl) 50×50 Čtvercový profil (jekl) 100×100 Plochý profil 50×10 Plochý profil 50×5 Hranol 10×10

Výchozí polotovar (mm)

Cena za kus (Kč) 2000 mm / 6000 mm

2000/6000

480 /1140

2000/6000

800/2400

2000/6000 2000/6000 2000/6000

365/1095 490/1470 345/1035

36


4.5 Tvorba řezného plánu bez využití metod operačního výzkumu V současnosti řezné plány vznikají vytipováním nejvhodnější kombinace profilů pomocí jednoduchých vzorců v programu MS Excel tak, aby vznikal co nejmenší odpad. Pro plánovanou zakázku navrhl majitel podniku následující řezná schémata. Tab. 4


Plochý profil 50×10 mm Délka profilu (mm) Počet profilů ve výchozím polotovaru (ks)

Odpad 600 450 530 (mm) 10 1 2 0 0

0 12 0 0 0

0 0 9 11 8

0 0 30 170 1760

Počet profilů 48 48 48 ∑ 400 celkem (ks) Celková cena za objednané polotovary (Kč)

Počet spotřebovaných výchozích polotovarů délky 6000 mm (ks) 4 4 2 2 1 ∑ 13 13 * 1095 = 14235

Byl zvolen výchozí polotovar délky 6000 mm, který představuje více moţností řezu s niţším odpadem, neţ je tomu u polotovaru délky 2000 mm. Abychom dosáhli co nejmenšího odpadu, zaměříme se nejprve na nejdelší profil, tedy 600 mm. Ten z výchozího polotovaru vyřízneme desetkrát bez vzniku odpadního materiál. Tímto způsobem vyrobíme maximum těchto profilů, spotřebujeme tedy čtyři kusy výchozího polotovaru. Z důvodu zamezení vzniku odpadu, budeme v dalším kroku rozřezávat výchozí polotovar na jeden profil délky 600 mm a dvanáct profilů délky 450 mm. Pro tuto operaci pouţijeme také čtyři kusy výchozího polotovaru. Dále postupujeme tak, ţe hledáme takovou kombinaci profilů, při které vzniká co nejniţší odpad. Tímto způsobem budeme řezat aţ do posledního kroku, kdy jiţ výchozí polotovar nedořízneme celý. Zbude 1760 mm výchozího polotovaru. Taková délka je však ještě pouţitelná a proto se odloţí pro další pouţití, do odpadu ji uvaţovat nebudeme. Výsledkem je tedy třináct spotřebovaných polotovarů s celkovým odpadem 400 mm a celkovou cenou 14235 Kč.

Charakteristika podniku a současného stavu výroby Tab. 5

37


Plochý profil 50×5 mm Délka profilu (mm) Počet profilů ve výchozím polotovaru (ks)

Počet spotřebovaných výchozích polotovarů délky 6000 mm (ks)

Odpad 650 400 (mm) 8

2

0

3

0 0

15 12

0 1200

2 1

Počet profilů celkem 24 48 ∑0 (ks) Celková cena za objednané polotovary (Kč)

∑6 6 * 1470 = 8820

V případě plochého profilu 50×5 mm zjišťujeme, ţe optimální je řezat profily v poměru, který je uveden v tabulce č. 5. V posledním kroku dořízneme zbývajících dvanáct kusů profilu délky 400 mm. Z výchozího polotovaru zbude 1200 mm, které přidáme k zásobám a vyuţijeme v další zakázce. Pro poslední krok volíme rovněţ polotovar délky 6000 mm, který nemusíme znovu upínat a ušetříme tak čas nutný pro manipulaci s materiálem. Pokud bychom na vyříznutí zbývajících dvanácti profilů vyuţili tři kusy polotovaru délky 2000 mm, zbyl by rovněţ výchozí polotovar v délce 1200 mm. Tab. 6

Rozřezávací schéma pro hranol 10×10 mm

Hranol 10×10 mm Délka profilu (mm)

Odpad 400 320 100 (mm)

3 15 0 0 Počet 15 0 0 0 profilů ve výchozím 11 5 0 0 polotovaru 4 4 31 20 (Ks) 0 0 17 300 Počet profilů 48 24 48 ∑ 20 celkem (ks) Celková cena za objednané polotovary (Kč)

Počet spotřebovaných výchozích polotovarů délky 6000 mm(ks)

Počet spotřebovaných výchozích polotovarů délky 2000 mm (ks) 1 2 1 1 0

0 0 0 0 1

∑5

∑1

5 * 1035 + 345 = 5520

Potřebný počet profilů typu hranol 10×10 mm získáme rozřezáním pěti kusů výchozího polotovarů délky 6000 mm a jednoho kusu výchozího polotovaru délky 2000 mm., přičemţ vzniká odpad v délce 20 mm z výchozího polotovaru délky 6000 mm a 300 mm z výchozího polotovaru délky 2000 mm. Z odpadu

38


délky 300 mm můţeme později vyříznout tři profily 100 mm, proto jej přidáme k zásobám a do odpadu jej uvaţovat nebudeme. Řešení je zapsáno v tabulce č. 6. Rozřezávací schémata sestavená majitelem podniku jsou pro všechny profily k dispozici na přiloţeném CD ve sloţce Přílohy v souboru Rozřezávací schéma MB.xls.

4.6 Klady současného systému  přehlednost  opakovatelnost pouţití šablon v programu MS Excel  ideální pro kusovou výrobu

4.7 Nevýhody současného systému  vznikající odpadní materiál  časová náročnost tvorby řezného plánu při větších sériích výrobků  nalezené řešení nemusí být vţdy optimální


39

5 Formulace matematického modelu 5.1

Rozřezávací schémata

V této fázi známe všechna potřebná data k tomu, abychom mohli sestavit jednotlivá rozřezávací schémata pro dané profily. Čtvercové profily můţeme v tomto kroku jiţ vynechat, protoţe se jedná o profily pouze jedné délky a uplatnění metod operačního výzkumu je zde tedy zbytečné. Protoţe kaţdý ze zbývajících profilů vychází z jiného výchozího polotovaru, budeme muset sestavit matematický model pro kaţdý z profilů zvlášť. Při tvorbě schémat postupujeme systematicky tak, ţe nejprve řeţeme pouze polotovar jedné délky a postupně ubíráme jeho mnoţství s tím, ţe přidáváme další rozměry. Tím zajistíme nalezení všech moţných kombinací. Pro vyšší přehlednost a snazší orientaci v tabulce pouţijeme nástroj Ukotvit příčky. V programu Excel 2007 jej najdeme na kartě Zobrazení v části Okno. Po rozevření nabídky klikneme na poloţku Ukotvit první sloupec. To zajistí, ţe při rolování tabulkou budeme mít na obrazovce vţdy potřebné informace. Rozřezávací schémata uvaţují oba typy výchozích polotovarů, tedy délky 6000 mm i 2000 mm a všechny moţné kombinace, které lze vytvořit. Po vytvoření rozřezávacího schématu pro obě délky výchozích polotovarů dospějeme v případě plochého profilu 50×10 mm k počtu 79 moţných variant rozřezání výchozích polotovarů. V případě plochého profilu 50×5 mm je situace podstatně jednodušší. Především díky tomu, ţe z výchozího polotovaru potřebujeme vyříznout jen dvě délky profilů. Rozřezávací schéma tvoří 14 variant. Po vytvoření rozřezávacího schématu profilu typu hranol 10×10 mm, je k dispozici 183 variant řezu výchozího polotovaru. Rozřezávací schémata pro kaţdý profil se nachází na přiloţeném CD ve sloţce Modely, kde je třeba zvolit sloţku příslušného profilu.

5.2 Matematický model Nejprve sestavíme modely pro určení toho, kolik výchozích polotovarů budeme potřebovat, v dalším kroku sestavíme modely pro minimalizaci odpadního materiálu. Kaţdý z modelů se nachází v samostatném sešitě na přiloţeném CD ve sloţce Modely a dále ve sloţce příslušného profilu.

5.3 Plochý profil 50×10 mm Určení potřebného počtu výchozích polotovarů

z min  x1  x2  x3  x4    x79 ks

(15)

40


za podmínek 3x1  2 x 2  2 x3  x 4  x5    x67  48ks x 2  3x 4  x5  4 x7  3x8    x78  48ks

x3  x5  2 x6  x8  2 x9    11x79  48ks

x1 , x2 , x3 ,, x79  0, celá

(16)

(17)

Účelová funkce (15) je minimalizační, protoţe chceme dosáhnout co nejniţšího počtu výchozích polotovarů, abychom minimalizovali náklady. Jejím výsledkem bude počet výchozích polotovarů, které budeme potřebovat. Omezující podmínky (16) vyjadřují na levých stranách jednotlivé varianty rozřezávacího schématu a na pravých stranách celkový počet jednotlivých profilů, který potřebujeme k výrobě 24 kusů krbových vloţek Alfa 1. Poslední součástí modelu je podmínka nezápornosti a celočíselnosti (17). Nyní se zaměříme na minimalizaci odpadu:

z min  200 x1  350 x2  270 x3  50 x4    170 x79 mm

(18)

za podmínek 3x1  2 x 2  2 x3  x 4  x5    x67  48ks x 2  3x 4  x5  4 x7  3x8    x78  48ks

x3  x5  2 x6  x8  2 x9    11x79  48ks

x1 , x2 , x3 ,, x79  0, celá

(19)

(20)

Účelová funkce (18) je opět minimalizační, protoţe chceme dosáhnout co nejmenšího mnoţství odpadního materiálu. Jejím výsledkem bude celkový odpad v milimetrech. Koeficienty účelové funkce představují hodnoty odpadního materiálu pro konkrétní variantu rozřezávacího schématu. Zbytek modelu je stejný jako v předešlém případě.

5.4 Plochý profil 50×5 mm Určení potřebného počtu výchozích polotovarů

z min  x1  x2  x3  x4    x14 ks

(21)


41

za podmínek 3x1  2 x2  x3  9 x5  8 x6   x13  24ks

x2  3x3  5 x4  2 x6  3x7    15 x14  48ks

(22)

x1 , x2 , x3 ,, x14  0, celá

(23)

z min  50 x1  300 x2  150 x3  150 x5    150 x13 mm

(24)

Minimalizace odpadu:

zbytek modelu je stejný, jako při určení počtu výchozích polotovarů.

5.5 Hranol 10×10 mm Určení potřebného počtu výchozích polotovarů

z min  x1  x2  x3  x4    x183ks

(25)

za podmínek 5 x1  4 x 2  4 x3  3x 4  3x5    x164  48ks

x 2  2 x 4  x5  3x7  2 x8    x182  24ks

4 x3  x 4  4 x5  8 x6  2 x7    60 x183  48ks

(26)

x1 , x2 , x3 ,, x183  0, celé

(27)

z min  80 x2  60 x4  80 x5  40 x7    80 x182mm

(28)

Minimalizace odpadu:

Zbytek modelu je totoţný jako v případě určení počtu polotovarů.

42

Řešení matematického modelu

6 Řešení matematického modelu Pro řešení matematických modelů jsem zvolil doplněk Řešitel, který je součástí programu MS Excel 2007. Výhodou je, ţe majitel podniku Excel jiţ pouţívá k tvorbě řezných schémat, proto by pro něj práce v tomto programu neměla představovat problém. Dalším důvodem pro zvolení Excelu je fakt, ţe doplněk Řešitel je zahrnut jiţ v ceně licence balíku MS Office a jeho vyuţití tedy nepředstavuje, na rozdíl od ostatních programů, dodatečné náklady. Modely profilů jsou řešeny v samostatných sešitech a jsou vytvořeny tak, aby byly snadno modifikovatelné pro budoucí pouţití.

6.1 Řešení modelu pro plochý profil 50×10 mm 6.1.1

Počet výchozích polotovarů

Při tvorbě modelu v programu MS Excel 2007 vycházíme z modelu, který je definován v kapitole 5.3. Do tabulky rozřezávacího schématu doplníme několik buněk. Jde o buňky VOP, kde budeme definovat jednotlivé omezující podmínky modelu a buňku ÚF, kde definujeme vzorec účelové funkce modelu. První omezující podmínku definujeme jako skalární součin řádku č. 4 a řádku č. 9, který obsahuje proměnné. Těm ze začátku přiřadíme nulové hodnoty. Podobně postupuje i v případě zbývajících omezujících podmínek. Takto vytvořené vzorce umístíme postupně do buněk B11 aţ B13. Protoţe účelová funkce musí být pro účely doplňku Řešitel definována jako vzorec, vytvoříme řádek č. 8 s pomocnými proměnnými, který bude obsahovat konstanty 1. Účelová funkce umístěná v buňce B14, bude skalárním součinem pomocných proměnných na řádku č. 8 a strukturních proměnných na řádku č. 9. Tab. 7

Počet výchozích polotovarů – profil 50×10 mm – optimální řešení

Varianta č. Délka výchozího polotovaru (mm) Délka profilu (mm) 600 450 530 Počet vyuţití varianty

10

11

13 17 22 56 57 69

2000 0 10 0 0 3 0 3 2

77 Počet profilů (ks)

6000 9 0 1 1

7 4 0 1

6 4 1 1

2 1 0 12 9 0 2 2

Odpad (mm) 410 0 70 0 70 30 Celkový počet výchozích polotovarů 2000 mm (ks) Celkový počet výchozích polotovarů 6000 mm (ks)

0 12 1 1

0 2 9 2

48 48 48

0 70 330

∑ 2160 3 12


43

V poslední řadě zadáme do buněk C11 aţ C13 pravé strany omezujících podmínek, tedy potřebné počty profilů. Nyní zbývá zapnout doplněk Řešitel a definovat jednotlivá pole a moţnosti tak, jak je to popsáno v kapitole 3.12. Podobným způsobem postupuje i v případě ostatních typů profilů. V případě modelu pro plochý profil 50×10 mm nalezl Řešitel optimální celočíselné řešení. Jako optimální je určeno pouţití tří kusů výchozího polotovaru délky 2000 mm a dvanácti kusů výchozího polotovaru délky 6000 mm. Při vyuţití příslušných variant řezu docílíme poţadovaného počtu profilů. Variantu č. 10 vyuţijeme tedy třikrát, tzn. proměnná 𝑥10 nabývá hodnoty 3 atd. Získané řešení je popsáno v tabulce č. 7. 6.1.2

Minimalizace odpadu

Vycházíme opět z modelu, který je definován v kapitole 5.3. Omezující podmínky jsou v případě minimalizace odpadu stejné, jako při minimalizaci potřebného počtu polotovarů. Při minimalizaci odpadu se mění účelová funkce, kterou nyní definujeme jako skalární součin řádku proměnných a řádku s odpadním materiálem tedy řádků č. 8 a č. 7. Při řešení tohoto modelu řešitel nenalezl optimální celočíselné řešení. Je tedy třeba uvolnit některou z omezujících podmínek. Tím získáme vyšší neţ poţadovaný počet profilů, ale ty můţeme uloţit do zásob a vyuţít je při další objednávce krbové vloţky Alfa 1. Tab. 8



17 32 46

55 56 57

67

75 Počet profilů (ks)

6000 7 4 0 5

4 8 0 1

3 1 7 2

2 1 8 1

2 1 0 12 9 0 1 1

Odpad (mm) 0 0 40 110 30 Celkový počet výchozích polotovarů 2000 mm Celkový počet výchozích polotovarů 6000 mm

1 0 10 1

0 5 7 1

51 48 48

0 100 40

∑ 360 0 13

Nejvhodnější je dle mého názoru uvolnění první omezující podmínky pro profil délky 600 mm. Tento profil je nejdelší a dá se v případě potřeby zkrátit na jiný rozměr. Omezující podmínku pro profil délky 600 mm tedy transformujeme do podoby, která je uvedena v následujícím výrazu (29):

44


3x1  2 x 2  2 x3  x 4  x5    x67  48ks

x 2  3x 4  x5  4 x7  3x8    x78  48ks

(29)

x3  x5  2 x6  x8  2 x9    11x79  48ks

Po této úpravě Řešitel určil optimální celočíselné řešení, které je popsáno v tabulce č. 8. Celkový odpadní materiál, který nelze dále vyuţít, představuje 360 mm. Vyrobeno je 51 kusů profilu délky 600 mm, namísto poţadovaných 48 kusů. Zbylé omezující podmínky jsou splněny přesně. Řešení vyuţívá pouze výchozí polotovary délky 6000 mm. Tab. 9


Typ úlohy

Minimalizace počtu výchozích polotovarů

Počet pouţitých výchozích polotovarů délky 6000 mm (ks) Počet pouţitých výchozích polotovarů délky 2000 mm (ks) Celkový odpadní materiál (mm) Celkový nevyuţitelný odpadní materiál (mm) Celková cena za výchozí polotovary (Kč)

Řešení navrţené majitelem podniku

Minimalizace odpadního materiálu 12

13

13

3

0

0

2160

2160

2160

2160

360

400

12 ∗ 1095 + 3 ∗ 365 = 14235

13 ∗ 1095 = 14235

13 ∗ 1095 = 14235

Závěrem zbývá určit, kterou účelovou funkci zvolit jako výchozí. V případě minimalizace počtu výchozích polotovarů získáme stejnou celkovou cenu za výchozí polotovary jako při minimalizaci odpadního materiálu. Hodnotícím kriteriem je tak mnoţství dále nevyuţitelného odpadního materiálu. Z tohoto hlediska budeme vyuţívat účelovou funkci pro minimalizaci odpadního materiálu. Navíc ušetříme 40 mm odpadu oproti návrhu rozřezávacího schématu majitele podniku. Příslušné modely jsou v elektronické podobě na přiloţeném CD ve sloţce Modely/Plochý 50×10. Rozřezávací schéma navrţené majitelem podniku se nachází ve sloţce Přílohy/Rozřezávací schéma MB.xls.


45

6.2 Řešení modelu pro plochý profil 50×5 mm 6.2.1


Řešitel určil celočíselné řešení, které je popsáno v tabulce č. 10. Celkový počet potřebných výchozích polotovarů představuje šest kusů polotovarů délky 6000 mm. Tab. 10

Počet výchozích polotovarů – profil 50×5 mm – optimální řešení

Varianta č. Délka výchozího polotovaru (mm) Délka profilu (mm) 650 400 Počet vyuţití varianty

8 6 5 1

9 11 14 6000 Počet profilů (ks) 5 3 0 6 10 15 3 1 1

Odpad (mm) 100 350 50 Celkový počet výchozích polotovarů 2000 mm (ks) Celkový počet výchozích polotovarů 6000 mm (ks)

6.2.2

Minimalizace odpadu

Tab. 11


Varianta č. Délka výchozího polotovaru (mm) Délka profilu (mm) 650 400 Počet vyuţití varianty Odpad (mm)

2 3 2000 2 1 2

1 3 1

0

24 48 ∑ 1200 0 6

7 11 6000 Počet profilů (ks) 7 3 1

3 10 4

24 48

300 150 250 50

∑ 1200

Celkový počet výchozích polotovarů 2000 mm (ks)

3

Celkový počet výchozích polotovarů 6000 mm (ks)

5

Řešitel nalezl optimální řešení, které je zapsané v tabulce č. 11. Řešením je vyuţití tří kusů výchozího polotovaru o délce 2000 mm a pěti kusů výchozího polotovaru o délce 6000 mm. Celkový nevyuţitelný odpad představuje 1200 mm materiálu.

46 Tab. 12

Řešení matematického modelu Vyhodnocení modelů pro profil 50×5 mm

Typ úlohy Počet pouţitých výchozích polotovarů délky 6000 mm (ks) Počet pouţitých výchozích polotovarů délky 2000 mm (ks) Celkový odpadní materiál (mm) Celkový nevyuţitelný odpadní materiál (mm) Celková cena za výchozí polotovary (Kč)




5

6

0

3

0

1200

1200

1200

1200

1200

0

6 ∗ 1470 = 8820

5 ∗ 1470 + 3 ∗ 490 = 8820

6 ∗ 1470 = 8820

Obě řešení získaná metodou lineárního programování, nabízí stejnou hodnotu odpadního materiálu, avšak úloha pro minimalizaci počtu výchozích polotovarů představuje, díky vyuţití pouze šestimetrových polotovarů, časovou úsporu z hlediska upínání a manipulace s materiálem. Ve srovnání s řešením navrţeným majitelem podniku získáváme stejnou cenu za nákup výchozích polotovarů. Při řešení metodou lineárního programování však odpadní materiál nezůstává v celku jako v případě rozřezávacího schématu majitele podniku, nýbrţ je rozdroben na menší nevyuţitelné kusy. V tomto případě je vhodné drţet se původního návrhu pana Bartla, kde 1200 mm materiálu ušetříme pro další vyuţití. Příslušné modely nalezneme na přiloţeném CD ve sloţce Modely/Plochý 50×5. Rozřezávací schéma navrţené majitelem podniku se nachází ve sloţce Přílohy/Rozřezávací schéma MB.xls.

6.3 Řešení modelu pro hranol 10×10 mm 6.3.1


Při řešení modelu pro hranol 10×10 mm nalezl Řešitel optimální celočíselné řešení, které je uvedeno v tabulce č. 13. Optimální řešení představují čtyři kusy výchozího polotovaru délky 2000 mm a čtyři kusy výchozího polotovaru délky 6000 mm. Vzniká dále nevyuţitelný odpadní materiál v délce 320 mm.

Řešení matematického modelu Tab. 13

47

Počet výchozích polotovarů – profil hranol 10×10 mm – optimální řešení

Varianta č. 17 26 29 33 54 Délka výchozího polotovaru (mm) 2000 6000 Počet profilů (ks) Délka profilu (mm) 400 0 14 13 12 9 48 320 6 0 0 0 0 24 100 0 4 8 12 24 48 Počet vyuţití varianty 4 1 1 1 1 Odpad (mm) 80 0 0 Celkový počet výchozích polotovarů 2000 mm (ks) Celkový počet výchozích polotovarů 6000 mm (ks)

6.3.2

Minimalizace odpadu

Tab. 14

Odpad – profil hranol 10×10 mm – optimální řešení


0

0

∑ 320 4 4

10 16 17 24 26 Počet profilů 2000 6000 (ks) 2 1 0 0 12 16 1 2

0 6 0 4

15 0 0 2

14 0 4 1

48 24 48

Odpad (mm) 0 0 80 Celkový počet výchozích polotovarů 2000 mm Celkový počet výchozích polotovarů 6000 mm

0

0

∑ 320 7 3

Optimální řešení pro minimalizaci odpadního materiálu je zřejmé z tabulky č. 14, celkový dále nevyuţitelný odpad tvoří 320 mm výchozího polotovaru. Pro vyříznutí profilů je vyuţito sedmi kusů výchozího polotovaru o délce 2000 mm a tří kusů výchozího polotovaru o délce 6000 mm. Příslušné modely nalezneme na přiloţeném CD ve sloţce Modely/Hranol 10×10. Rozřezávací schéma navrţené majitelem podniku se nachází ve sloţce Přílohy/Rozřezávací schéma MB.xls.

48 Tab. 15

Řešení matematického modelu Vyhodnocení modelů pro profil hranol 10×10 mm

Typ úlohy Počet pouţitých výchozích polotovarů délky 6000 mm (ks) Počet pouţitých výchozích polotovarů délky 2000 mm (ks) Celkový odpadní materiál (mm) Celkový nevyuţitelný odpadní materiál (mm) Celková cena za výchozí polotovary (Kč)




7

5

4

3

1

320

320

320

320

320

20

4 ∗ 345 + 4 ∗ 1035 = 5520

7 ∗ 345 + 3 ∗ 1035 = 5520

1 ∗ 345 + 5 ∗ 1035 = 5520

Celková cena za výchozí polotovary je stejná, hodnota odpadního materiálu se pro oba druhy účelových funkcí rovněţ neliší. Kriteriem pro rozhodování je v tomto případě počet polotovarů. Tím, ţe je počet polotovarů při funkci pro jejich minimalizaci niţší neţ v případě řešení funkcí pro minimalizaci odpadního materiálu, ušetříme čas při upínání a manipulaci s výchozími polotovary. Ve srovnání s řešením navrţeným majitelem podniku zjišťujeme, ţe celková cena výchozích polotovarů je stejná jako v případě vyuţití lineárního programování. Celkový dále nevyuţitelný materiál však představuje pouze 20 mm, zbylých 300 mm výchozího polotovaru je v celku a tím tedy pouţitelných v budoucnu. Implementace lineárního programování v tomto případě tedy nepřináší úsporu.

Závěr práce

49

7 Závěr práce Předloţená bakalářská práce se zabývá problémem optimalizace nákladů v podniku Zámečnictví Martin Bartl, které má být dosaţenou úsporou v počtu nakupovaných výchozích polotovarů a minimalizací odpadního materiálu, který vzniká při jejich dělení. Pro řešení tohoto problému bylo vyuţito poznatků z prostředí operačního výzkumu, přesněji metod lineárního programování a doplňku Řešitel v programu MS Excel 2007. Ten k řešení vyuţívá simplexovou metodu, která je základním algoritmem k řešení úloh lineárního programování. Výsledky sestavených modelů byly srovnány z hlediska obou kriterií, tedy minimalizace počtu výchozích polotovarů a minimalizace odpadního materiálu a dále porovnány s řešením, které vypracoval majitel podniku. Je nutno zmínit, ţe metody operačního výzkumu je vhodné pouţívat pouze v souladu s lidským faktorem. Výsledky operačního výzkumu by měly slouţit jako podklad k rozhodování, nebývají zcela jistým východiskem. To se projevilo u dvou modelů – pro plochý profil 50×5 mm a hranol 10×10 mm. V těchto případech dostáváme stejné hodnoty odpadního materiálu jako v případě návrhu rozřezávacího schématu od majitele podniku, ale tento odpadní materiál není v celku a není tedy moţné jej vyuţít pro další zakázky. To je dáno existencí více optimálních řešení daných úloh lineárního programování. Takových řešení bude tím více, čím více moţných kombinací řezu výchozího polotovaru bude vznikat. Panu Bartlovi bych v prostředí jeho zámečnické dílny vyuţití metod lineárního programování doporučil. I kdyţ má zaveden svůj systém tvorby rozřezávacích schémat, který se ve dvou modelech ze tří osvědčil, ne vţdy musí být takové řešení optimální. Proto by mnou navrţený systém mohl slouţit pro kontrolu optimality rozřezávacích schémat navrţených majitelem podniku. Za kriterium hodnocení optimality bychom v takovém případě povaţovali celkové mnoţství odpadního materiálu. V práci jsem si ověřil, ţe lineární programování je skutečně vhodným nástrojem pro podporu v rozhodování a jeho metody jsou vyuţitelné nejen v oblasti podnikání, ale i v kaţdodenním ţivotě, kde jej budu příleţitostně vyuţívat i já.

50

Literatura

8 Literatura DUDORKIN, Jiří. Operační výzkum. 1. vyd. Praha: České vysoké učení technické, 1988, 296 s. GASS, Saul I. a Arjang A. ASSAD. History of operations research. Hanover: INFORMS, 2011. ISBN 978-0-9843378-2-8. Dostupné z: http://s12.middlebury.edu/MATH0318A/History%20of%20OR.pdf GROS, Ivan. Kvantitativní metody v manažerském rozhodování. 1. vyd. Praha: Grada, 2003, 432 s. ISBN 80-247-0421-8. HOLOUBEK, Josef. Ekonomicko-matematické metody. 2., nezměn. vyd. V Brně: Mendelova univerzita, 2010, 153 s. ISBN 978-80-7375-411-2. JABLONSKÝ, J. Operační výzkum: kvantitativní modely pro ekonomické rozhodování. 3. vyd. Praha: Professional Publishing, 2007. 323 s. ISBN 97880-86946-44-3. LAŠČIAK, A., Adam. Optimálne programovanie: celoštátna vysokoškolská učebnica pre vys. školy ekonomické. 2. upr. vyd. Bratislava: Alfa, 1990, 655 s. LAUBER, Josef a Josef JABLONSKÝ. Programy pro matematické modelování. 1. přeprac. vyd. Praha: Vysoká škola ekonomická, 1997, 233 s. ISBN 807079-296-5. LIŠKA., Miroslav. Operační výzkum. Matematické metody v podnikání [online]. 11. 12. 2006 [cit. 2013-05-04]. Dostupné z: http://www.volny.cz/miroslav.liska/mmp/aspekty.htm#Beg PLEVNÝ, Miroslav a Miroslav ŢIŢKA. Modelování a optimalizace v manažerském rozhodování. 1. vyd. V Plzni: Západočeská univerzita, 2005, 296 s. ISBN 80-7043-435-x. RAŠOVSKÝ, Miroslav. Ekonomicko-matematické metody. 3. vyd. Brno: Vysoká škola zemědělská, 1990, 244 s. Zámečnictví Brno | zámečnictví Bartl. [online]. [cit. 2013-03-07]. Dostupné z: http://www.zamecnictvi-bartl.cz/

Optimalizace výrobního procesu podniku Zámečnictví Martin Bartl

Recommend Documents