VYSOKÁ ŠKOLA EKONOMICKÁ V PRAZE FAKULTA INFORMATIKY A STATISTIKY BAKALÁŘSKÁ PRÁCE Radka Luštincová

VYSOKÁ ŠKOLA EKONOMICKÁ V PRAZE FAKULTA INFORMATIKY A STATISTIKY

BAKALÁŘSKÁ PRÁCE

2013

Radka Luštincová

VYSOKÁ ŠKOLA EKONOMICKÁ V PRAZE FAKULTA INFORMATIKY A STATISTIKY

Název bakalářské práce:

Aplikace řezných úloh na výrobu lyží

Autor:

Radka Luštincová

Katedra:

Katedra ekonometrie

Obor:

Matematické metody v ekonomii

Vedoucí práce:

Mgr. Jana Sekničková, Ph.D.

Prohlášení: Prohlašuji, že jsem bakalářskou práci na téma „Aplikace řezných úloh na výrobu lyží“ zpracovala samostatně. Veškerou použitou literaturu a další podkladové materiály uvádím v seznamu použité literatury. V Praze dne 3. června 2013

................................ Radka Luštincová

Poděkování: Touto cestou bych ráda poděkovala Mgr. Janě Sekničkové, Ph.D. za vedení mé bakalářské práce a za podnětné návrhy, které ji obohatily. Rovněž děkuji jednateli firmy GALUS Industries s.r.o. Milanu Luštincovi za poskytnutí cenných rad a důležitých dat.

Abstrakt Název práce: Autor: Katedra: Vedoucí práce:

Aplikace řezných úloh na výrobu lyží Radka Luštincová Katedra ekonometrie Mgr. Jana Sekničková, Ph.D.

Tato bakalářská práce se zabývá jednou ze speciálních úloh lineárního programování a to jak z teoretické, tak i z praktické stránky. Jedná se o úlohu o optimálním dělení materiálu, tedy o řeznou úlohu. V úlohách o optimálním dělení materiálu jsou typické dva cíle. Minimalizace odpadu a minimalizace spotřebovaného materiálu. Tato práce obsahuje teoretickou část, která vysvětluje matematický model a různé modifikace řezných úloh. V reálné úloze, která je uvedena v poslední části mé práce se zabývám řešením konkrétního příkladu ve firmě GALUS Industries s. r. o. specializující se na výrobu lyží. Výsledky získané díky programu MS Excel jsou shrnuty v závěru práce. Výsledné hodnoty a postup řešení práce budou firmě předloženy. Klíčová slova: lineární programování, řezný plán, optimalizace výroby, MS Excel

Abstract Title: Author: Department: Supervisor:

Application of cutting jobs on the ski production Radka Luštincová Department of Econometrics Mgr. Jana Sekničková, Ph.D.

This bachelor´s work is dealing with one of the special linear programming problem, from the theoretical as well as from the practical aspect. It is about the role of optimal cutting of material, thus about the cutting task. In the tasks of optimal cutting of materials are typically two goals, one is a minimization of waste and the second one is minimization of used material. The work includes a theoretical part, which explains the mathematical model and various modifications of cutting problems. In the real aplication that is mentioned in the last part of my work, I am dealing with a solution of actual task in the company GALUS Industries Ltd., which is specialized in the production of ski. The results obtained from the Excel program are summarized in the conclusion of the work. The resulting values and the process of solutions tasks will be presented to the company. Keywords: linear programming, cutting plan, production of optimization, MS Excel

Obsah 1 ÚVOD...............................................................................................................................................1 2 CELOČÍSELNÉ PROGRAMOVÁNÍ ...........................................................................................2 2.1 METODA VĚTVÍ A MEZÍ ..............................................................................................................4 3 ÚLOHA O OPTIMÁLNÍM DĚLENÍ MATERIÁLU ..................................................................6 4 NETYPICKÉ CÍLE PŘI ŘEŠENÍ ÚLOH O OPTIMÁLNÍM DĚLENÍ MATERIÁLU ...........8 4.1 MINIMALIZACE PODÍLU ODPADU ...............................................................................................8 4.2 NÁKLADY NA SKLADOVÁNÍ ODPADŮ ....................................................................................... 10 4.3 NÁKLADY NA LIKVIDACI ODPADU ........................................................................................... 11 4.4 MINIMALIZACE POČTU ŘEZŮ.................................................................................................... 12 4.5 MINIMALIZACE NÁKLADŮ NA ŘEZÁNÍ ..................................................................................... 13 4.6 PROŘEZY.................................................................................................................................. 13 4.7 ÚLOHA O SVAŘOVÁNÍ .............................................................................................................. 14 4.8 CÍLOVÉ PROGRAMOVÁNÍ ......................................................................................................... 15 5 APLIKACE NA REÁLNÝ PŘÍKLAD – DĚLENÍ DESEK PŘI VÝROBĚ LYŽÍ................... 16 5.1 O FIRMĚ ................................................................................................................................... 16 5.2 VYSVĚTLENÍ POJMU „DŘEVĚNÉ JÁDRO“ .................................................................................. 16 5.3 EKONOMICKÝ MODEL .............................................................................................................. 17 5.4 MATEMATICKÝ MODEL ............................................................................................................ 20 5.5 ŘEŠENÍ ..................................................................................................................................... 21 5.5.1 Řešení s využitím pouze efektivních řezných plánů .................................................................. 21 5.5.2 Řešení ve tvaru rovnosti ........................................................................................................... 21 5.5.3 Řešení ve tvaru nerovnosti........................................................................................................ 22 5.5.4 Řešení ve tvaru nerovnosti s překročením požadovaného množství o 25 % a 50% .................... 23 5.5.5 Konečné řešení ......................................................................................................................... 24

5.6 HODNOCENÍ VÝSLEDKŮ ........................................................................................................... 25 5.7 PROGRAM V EXCELU ............................................................................................................... 26 ZÁVĚR ............................................................................................................................................... 29 SEZNAM POUŽITÉ LITERATURY............................................................................................... 30 PŘÍLOHY ........................................................................................................................................... 31

1 Úvod V každém výrobním podniku se setkáváme se spoustou problémů, které souvisí se zpracováním materiálu. Primárně se většina podniků snaží minimalizovat náklady a maximalizovat zisk, což s efektivním využíváním materiálu úzce souvisí. Snažíme se, abychom zbytečně nezpracovávali více materiálu než je nutné a aby odpady, které nám zbývají, byly co nejmenší, nebo abychom je dále efektivně využívali. K řešení takovýchto problémů nám slouží úlohy o optimálním dělení materiálu neboli „řezné úlohy“. Tyto úlohy mohou být dvojího druhu, buď se jedná o úlohy s typickými cíli (minimalizace spotřebovaného materiálu a minimalizace odpadu), nebo úlohy s netypickými cíli (úlohy zabývající se minimalizací skladovacích nákladů, minimalizací nákladů na likvidaci odpadu, minimalizací počtu řezů…). V první kapitole se věnuji celočíselnému programování. Jelikož u řešení úloh o optimálním dělení materiálu je obecně důležité, aby výsledné hodnoty (v našem případě počty řezů) byly v celých číslech, krátce jsem se zaměřila i na problematiku celočíselného programování. Stručně jsem popsala dvě z metod, které slouží k řešení úloh celočíselného programování (metoda větví a mezí, Gomoryho metoda). Druhá kapitola je zaměřena na úlohy s typickými cíli. Mezi tyto cíle patří minimalizace odpadu a minimalizace spotřebovaného materiálu. Podnik se snaží co nejefektivněji využívat spotřebovávaný materiál, aby případný odpad byl co nejmenší a nedocházelo ke zbytečnému plýtvání. Ve třetí kapitole se zaměřuji na úlohy s netypickými cíli. Jedná se například o úlohy se skladovacími náklady, kdy je snaha minimalizovat náklady na skladování případného odpadu, který vznikl při výrobě. Dále se jedná o náklady na likvidaci odpadu, neboť odpad může být nenávratně zlikvidován, ale také může být zařazen znovu do výroby (tuto problematiku jsem řešila i v praktické části práce) nebo může být využíván k další doplňkové činnosti. Dalšími netypickými cíli, které jsem zmínila je například cílové programování, minimalizace počtu řezů atd. Hlavním cílem mé bakalářské práce je aplikace úloh s typickými a netypickými cíli na řešení reálného příkladu. V mém případě se jedná o úlohu o optimálním dělení materiálu ve firmě GALUS Industries s.r.o. zabývající se výrobou lyží. Tuto úlohu jsem nejprve začala řešit jako úlohu s ryze typickými cíli, protože primárním úkolem bylo minimalizovat odpad. Postupem času jsem do výrobního procesu pronikala hlouběji a našla jsem nové možnosti zpracování odpadu. Tato problematika již ovšem byla řešitelná pouze s využitím úloh s netypickými cíli. V řešení jsem musela zohlednit síly řezu, což je vlastně úloha s prořezy. Dále jsem zde musela pojit menší části materiálu, tak aby mi vznikl finální výrobek větší velikosti. Zde se jedná o úlohu o svařování. Výsledné hodnoty všech variant řešení praktické části práce jsou uvedeny v příloze.

1

2 Celočíselné programování „Mezi speciální úlohy lineárního programování lze zařadit i úlohy celočíselného (lineárního) programování. Jedná se o standardní úlohy LP, které jsou však doplněny o tzv. podmínky celočíselnosti.“ (Citace z [4, str. 113]) Podmínka celočíselnosti zajišťuje, aby výsledné hodnoty všech nebo jen některých proměnných nabývaly pouze celých čísel. Podmínkami celočíselnosti se zabývá disciplína s názvem celočíselné programování. Pokud jsou všechny proměnné omezeny podmínkou celočíselnosti, jedná se o ryze celočíselné úlohy lineárního programování. Pokud se v úloze vyskytují jak celočíselné tak neceločíselné proměnné, jedná se o smíšené úlohy lineárního programování. Podmínky celočíselnosti je vhodné využít, pokud se v ekonomickém modelu vyskytují nedělitelné výrobky, počet opakování nějaké aktivity nebo počty použitých dopravních prostředků. Někdy se v úloze LP vyskytují proměnné, které nabývají pouze hodnot 0 a 1, takové proměnné se nazývají bivalentní (binární) proměnné. Pomocí těchto proměnných se zjistí, jestli daná situace nastane (hodnota 1) nebo nenastane (hodnota 0). Bivalentní proměnné jsou využívány například při řešení okružního dopravního problému, přiřazovacího problému a úlohy o pokrytí. „Pro řešení celočíselných úloh nelze použít standardní simplexovou metodu, neboť ta poskytuje obecně řešení neceločíselné.“ (Citace z [5, str. 250]) Jako nejjednodušší možnost se jeví vypočítat úlohy bez podmínek celočíselnosti a poté čísla zaokrouhlit. Tímto způsobem lze ale získat jen přibližné řešení. Může nastat situace, že zaokrouhlené řešení nebude přípustným řešením úlohy lineárního programování. Kdyby však bylo přípustným řešením, neznamená to, že je i optimálním řešením úlohy. „Proto byly navrženy speciální algoritmy pro řešení těchto úloh. Tyto algoritmy dělíme do několika skupin podle jejich charakteru.“ (Citace z [5, str. 250]) Skupiny algoritmů se dělí na: 1. Metody řezných (sečných) nadrovin jsou vhodné pro řešení ryze i smíšeně celočíselných úloh LP. Jsou uvažovány však pouze obecné podmínky celočíselnosti. „Nejsou vhodné pro řešení bivalentních úloh.“ (Citace z [5, str. 250]) Nejdříve je vypočteno optimální řešení běžnou simplexovou metodou (Simplexovou metodu popisuji v příloze č. 6). V každém dalším kroku se potom konstruuje další nové omezení, které z této množiny přípustných řešení vždy „odřízne“ podmnožinu, která nesmí obsahovat žádné přípustné řešení. Pro takto zúženou množinu se opět vypočte optimální řešení. „Po konečném počtu kroků vede tento postup k získání optimálního řešení celočíselné úlohy.“ (Citace z [5, str. 251]) Typickým reprezentantem těchto metod je Gomoryho algoritmus, pro řešení ryze celočíselných úloh, který bude popsán v příloze č. 7. 2. Kombinatorické metody vycházejí z optimálního řešení úlohy LP bez podmínek celočíselnosti. Postupně se potom prohledává množina přípustných řešení a vypouští se ty podmnožiny, které nejsou pro náš příklad efektivní, nevyskytuje se v nich optimální řešení. „Jednotlivé kombinatorické metody jsou většinou určeny pouze pro 2

řešení konkrétních typů úloh celočíselného programování, proto bližší obecný popis není možný.“ (Citace z [4, str. 115]) Nejznámějším zástupce kombinatorických metod je metoda větví a mezí, kterou popíši dále. 3. Metody dekompoziční řeší úlohy, u kterých jsou podmínky celočíselnosti kladeny jen na některé proměnné (smíšené celočíselné úlohy). „Řeší se rozkladem na dvě části – s podmínkami celočíselnosti a bez podmínek celočíselnosti.“ (Citace z [7, přednáška č. 10, str. 58]) 4. Heuristické metody řeší obzvláště obtížné úlohy ryze i smíšeně celočíselné. Heuristické metody je možné rozdělit do dvou skupin. První skupina metod řeší úlohy pouze přibližnými algoritmy, které nám poskytují relativně dobré řešení. Není však zaručeno, že je toto řešení optimální, jedná se například o úlohy obchodního cestujícího nebo dopravní problém. Druhá skupina řeší úlohy popsanými algoritmy, které zaručují optimální řešení. Patří sem například maďarská metoda, která se používá pro řešení přiřazovacího problému (podle [8, str. 143]). Mimo výše zmíněných algoritmů nebo modifikací simplexové metody mohou být využívány i různé programové systémy, kterými lze řešit úlohy lineárního ale i nelineárního programování. Bez těchto programů by bylo řešení reálných úloh prakticky nemožné. Na výběr máme z poměrně široké nabídky programů. Jako první a mně nejbližší bych uvedla doplněk Řešitel v tabulkovém kalkulátoru MS Excel, ve kterém jsem řešila úlohu v praktické části práce. Dále potom programy LINDO a LINGO, které se dají zařadit mezi profesionální optimalizační systémy. „LINGO je univerzálnější systém, protože vedle optimalizace nabízí i obecný nástroj pro podporu matematického modelování.“ (Citace z [5, str. 263]) Dalším programem pro podporu matematického modelování je třeba MPL for Windows. Dále bych ještě uvedla optimalizační systém XPLORE a XA. Podrobněji se těmto programům věnovat nebudu. S většinou těchto programů jsem se seznámila při výuce ve škole. Nyní popíši jeden z výše zmíněných algoritmů, kterým lze řešit můj příklad. Jedná se o metodu větví a mezí. MS Excel řeší podmínky celočíselnosti, podobně jako většina profesionálních systémů, které slouží pro řešení úloh lineárního programování právě metodou větví a mezí. Alternativou by bylo například použití Gomoryho metody, kterou uvádím v příloze č. 7.

3

2.1

Metoda větví a mezí

„V profesionálních programových systémech jsou pro řešení úloh celočíselného programování nejčastěji využívány tzv. metody větví a mezí (někdy větvení a mezí, angl. branches and bounds)“. (Citace z [4, str. 117) Tyto metody patří mezi kombinatorické algoritmy. Princip metod větví a mezí je velmi obecný, proto je možné použít jej po jisté úpravě k řešení celé škály úloh celočíselného programování. Metodami větví a mezí je možné řešit úlohy s obecnými podmínkami celočíselnosti, bivalentní úlohy, úlohy přiřazovacího problému nebo úlohy okružního dopravního problému. Metody větví a mezí jsou založeny na efektivním prohledávání množiny přípustných řešení, postupně jsou vybírány ty části, které jsou vhodné pro nalezení řešení. Metod na principu větví a mezí je velké množství. Ve své práci se zaměřím na metodu autorek Land a Doig. Tuto metodu lze využít jak pro řešení ryze celočíselných úloh lineárního programování tak i pro úlohy smíšeně celočíselné. Podmínkou této metody je, že koeficienty účelové funkce jsou vždy celá čísla. Úlohu lineárního programování bez podmínek celočíselnosti si označím jako LP ( 0) . Množinu přípustných řešení této úlohy označím X ( 0) . Dále se vypočte optimální řešení standardní simplexovou metodou bez podmínek celočíselnosti. Nalezené optimální řešení je 0 0 0 T označeno vektorem x (0)  x1 , x2 ,..., x n , a hodnota účelové funkce pro toto řešení je označena jako z ( 0) . Musí být otestováno, zda toto optimální řešení splňuje podmínky celočíselnosti. Pokud ano, jedná se o optimální řešení celé úlohy a výpočet končí, pokud tomu tak není, začneme proces větvení.





Větve Princip větvení spočívá v tom, že množina X ( 0) se rozdělí na dvě podmnožiny X (1) (levá větev) a X ( 2) (pravá větev). Z vektoru x ( 0) se vybere libovolně jedna proměnná, která nesplňuje podmínku celočíselnosti. Proměnná, která byla vybrána, je označena x k (této (0) proměnné se říká větvící proměnná) a její hodnota se značí jako xk . Levá větev je charakterizována přidáním podmínky xk  [ xk ( 0)

( 0)

],

(0)

kde [ xk ] představuje celou část z hodnot xk . Jedná se o největší celé číslo, jehož hodnota (0) je menší nebo rovna hodnotě xk . Touto úpravou nám vzniká nová úloha LP (1) . Pravá větev je vytvořena z množiny X ( 0) rozšířením o podmínku xk  [ xk

( 0)

]  1.

Tím vzniká nová úloha LP ( 2) . Tyto nově vzniklé úlohy se opět řeší standardní nebo duálně simplexovou metodou bez podmínek celočíselnosti. Pokud nalezené optimální řešení stále nesplňuje podmínky celočíselnosti, musíme celý postup znovu opakovat. 4

Meze V každé větvi je ještě odvozována horní mez (v případě maximalizace) pro hodnotu účelové funkce celočíselného řešení. U ryze celočíselných úloh se horní mez pro hodnotu celočíselného řešení na množině X(k) získá jako





h ( k )  z ( k )   , kde

k – index úlohy LP(k) (k-té větve), z (k ) – optimální hodnota účelové funkce úlohy LP(k) na množině řešení X(k),  – dostatečně malé kladné číslo (např. 10-8). Pokud máme zadanou minimalizační úlohu, je postup podobný, akorát naopak hledám dolní mez





d (k )  z (k )   .

U smíšeně celočíselné úlohy (ne všechny proměnné musí splňovat podmínky celočíselnosti) je horní mez (resp. dolní mez) přímo určena hodnotou účelové funkce. Pro další větvení musí být zvolena větev s nejvyšší horní (resp. nejnižší dolní) mezí. Tato větev je pro nalezení hledaného řešení nejlepší. Konec větve Celý postup pokračuje tak dlouho, dokud nejsou všechny vzniklé větve uzavřeny. Jsou tři způsoby uzavření větví: 1. Ve větvi je nalezeno takové řešení, které splňuje podmínky celočíselnosti. 2. Ve větvi neexistuje žádné přípustné řešení. 3. „Ve větvi je nalezeno neceločíselné řešení a horní mez pro hodnotu účelové funkce, odvozená z tohoto řešení, je nižší než hodnota účelové funkce celočíselného řešení, nalezeného již dříve v některé z ostatních větví.“ (Citace z [4, str. 118]) Když uzavřeme všechny větve, nejlepší nalezené celočíselné řešení (pokud existuje) je současně hledaným optimálním řešením úlohy celočíselného programování.

5

3 Úloha o optimálním dělení materiálu Každý výrobní podnik se snaží maximalizovat svůj zisk a využívat všechny zdroje co nejefektivněji. Především se pak snaží o to, aby náklady, které vynakládá na dosažení zisku, byly co nejmenší. Minimalizace se může ve výrobě projevit různými způsoby. Mezi typická omezení patří minimalizace odpadu, který vzniká při výrobě, nebo minimalizace spotřebovaného materiálu. Úlohy zabývající se touto problematikou se nazývají úlohy o optimálním dělení materiálu. V úlohách o dělení materiálu (někdy bývají nazývány jako řezné úlohy) se jedná o co nejefektivnější rozdělení velkých celků na určité počty menších dílů tak, aby odpad byl minimální nebo aby spotřeba výchozího materiálu byla co nejmenší. Musíme přitom však brát ohled na to, v jakém poměru mají být vzniklé menší díly rozřezány – kolik jich má minimálně nebo maximálně vzniknout. Základem úloh tohoto typu je vypracovat tzv. řezné schéma. Toto řezné schéma může být buď zadáno, nebo se musí sestavit. Jsou v něm přehledně uspořádány všechny možné kombinace rozdělení základního materiálu na požadované menší díly. Do řádků se zapíší požadované rozměry a do sloupců napíšeme možné způsoby dělení původního materiálu. Pokud sestavujeme řezný plán sami, postupujeme od maximálního počtu kusů největšího rozměru k maximálnímu počtu kusů nejmenšího rozměru. Do posledního řádku tabulky se potom zapíše odpad, který vznikne při řezání. Pokud využíváme pouze efektivní řezy, měl by být největší odpad vždy menší než nejmenší požadovaný kus. Můžeme však využívat i neefektivní řezy, kde toto neplatí. Každé variantě dělení, která nám vznikne po vytvoření řezného plánu, je přidělena proměnná x j , j = 1, 2, ...n. Proměnná x j vyjadřuje, kolik materiálu velkého rozměru, bude rozděleno na menší kusy podle varianty j (podle [5, str. 62]). Máme dva typy úloh o dělení materiálu – jednorozměrné a vícerozměrné. U jednorozměrné úlohy je dělení charakterizováno pouze jedním rozměrem. Jedná se například o trubky, tyče nebo provazy. Je přesně známa délka a počet dělených kusů. Jednorozměrný problém vede na úlohu lineárního programování. U vícerozměrných úloh se jedná o dělení plošných nebo prostorových předmětů. Jde o složitější úlohu, která již není úlohou lineárního programování. U úloh tohoto typu není na první pohled jasné, co jsou procesy, co tedy budou představovat proměnné. „Procesem je zde použití jednoho z možných způsobů dělení většího celku, hodnota proměnné ukazuje četnost jeho použití.“ (Citace z [7, přednáška č. 1, str. 45]) Procesům potom odpovídají proměnné a hodnoty těchto proměnných udávají, kolikrát je daný způsob dělení využit. Úlohu o optimálním dělení materiálu zařadíme do úloh celočíselného lineárního programování, neboť proměnná říká, kolikrát použijeme daný způsob řezu. Model úlohy o optimálním dělení materiálu, ve kterém se snažíme minimalizovat odpad, je možné zapsat ve tvaru:

6

účelová funkce: z  c1 x1  c2 x2  ...  cn xn  MIN (MAX ), soustava vlastních omezení: a11x1  a12 x2  ...  a1n xn Rb1 , a21x1  a22 x 2 ...  a2 n xn Rb2 , …. am1 x1  am 2 x 2 ...  amn xn Rbm , podmínky nezápornosti: j = 1, 2, …, n, x j  0 , celé bi  0

kde

i = 1, 2, …, n,

n – počet všech možných způsobů, jak můžeme rozřezat původní materiál, m – počet druhů nařezaného materiálu menších rozměrů, c j – odpad, který vznikne při využití j-tého řezného plánu,

bi – hodnota pravé strany, omezení materiálu menších rozměrů, aij – kolik kusů i-tého materiálu menších rozměrů získáme, pokud využijeme j-tý

řezný plán, R – relační znaménko ≤, ≥, = je určeno ze zadání ekonomického modelu, x j – kolikrát využiji daný způsob řezu. Pokud bychom chtěli řešit druhý typ úlohy a minimalizovat tedy spotřebovaný materiál, změnila by se pouze účelová funkce úlohy. Vlastní omezení úlohy a podmínky nezápornosti by zůstaly stejné. Účelová funkce vypadá takto: n

z   x j  MIN . j 1

7

4 Netypické cíle při řešení úloh o optimálním dělení materiálu V reálném světě se s typickými cíli při řešení úloh o optimálním dělení materiálu zmíněnými ve třetí kapitole setkáváme minimálně. Jedná se spíše o školní příklady, které jsou pro snadné pochopení zjednodušené. Ve většině reálných příkladů se setkáváme s netypickými cíli. Znamená to, že se v úloze vyskytuje nějaký problém související se zpracováním materiálu, který při řešení musíme zohlednit. Jak jsem již výše zmínila, chtějí všechny výrobní podniky minimalizovat náklady a maximalizovat zisk. Proto se v praxi setkáváme s požadavky firem, které řešíme právě využitím úloh s netypickými cíli. Jedná se například o úspory v oblasti nákladů na řezání materiálu, na skladování nebo likvidaci odpadu případně další využití tohoto odpadu. Dalším problémem může být například zohlednění síly řezu při dělení původního materiálu. Potom se jedná o úlohu s prořezy. Pokud například vyrábíme technologicky nebo materiálově náročný výrobek, může být zadán požadavek na co nejmenší počet řezů. Dalším požadavkem může být minimalizace podílu odpadu. Firma se snaží materiál maximálně využít, aby vzniklý odpad byl co nejmenší. 4.1

Minimalizace podílu odpadu

Jedním ze speciálních případů může být situace, kdy výrobní firma požaduje, aby procento odpadu z celkového množství použitého materiálu na výrobu výrobků bylo co nejmenší. Jednou z možností jak toto zajistit je, že v tabulce řezného plánu uvedeme podíl odpadu v poměru k celkovému materiálu. Toto číslo bude uvedeno ve tvaru zlomku nebo desetinného čísla a bude se pohybovat v intervalu 0,1 . Další složitější možností je minimalizovat místo standardní lineární účelové funkce podíl dvou lineárních funkcí. Model této úlohy je formulován takto (podle [3, str. 92]: účelová funkce: n

z

c x j

j 1 n

d j 1

j

j

  MIN ,

xj  

soustava vlastních omezení: n

a j 1

ij

x j Rbi

xj  0

i = 1, 2, …, m, j = 1, 2, …, n.

8

V čitateli účelové funkce je uvedena velikost odpadu a ve jmenovateli je uvedeno celkové spotřebované množství původního materiálu. Účelová funkce v takovémto tvaru není lineární. Na úlohu lineárního programování ji lze převést pomocí Charnesovy – Cooperovy transformace (podle [3, str. 92]). Je nutné do modelu zavést novou proměnnou t

1 n

d j 1

j

.

xj  

Tuto proměnnou dále upravíme na tvar n

d j 1

j

x j t  t  1.

Nově vzniklou podmínku je již možné zařadit do soustavy vlastních omezení modelu. „Touto proměnnou vynásobíme obě strany omezujících podmínek a současně upravíme účelovou funkci.“ (Citace z [3, str. 93]). Upravený matematický model úlohy vypadá takto: účelová funkce n

z   c j x j t    t  MIN , j 1

soustava vlastních omezení n

a j 1

n

d j 1

j

ij

x j t  bi t , i = 1, 2, …, m,

x j t   t  1,

podmínky nezápornosti tx j  0t ,

j = 1, 2, …, n,

t > 0. V nově vzniklém modelu provedeme substituci, x j t nahradíme y j . V úlohách lineárního programování nelze pracovat s ostrými nerovnostmi, proto podmínku t > 0 , nahradíme podmínkou t   , kde  je velmi malé číslo blízké nule (podle [3, str. 93]). Konečný tvar matematického modelu vypadá takto:

9

účelová funkce n

z   c j y j    t  MIN , j 1

soustava vlastních omezení n

a j 1

ij

n

d j 1

j

y j  bi t , i = 1, 2, …, m,

y j   t  1,

podmínky nezápornosti yj  0 ,

j = 1, 2, …, n,

t  .

Takto upravená úloha je již úlohou lineárního programování a tudíž i snadno řešitelná (např. simplexovou metodou).

4.2

Náklady na skladování odpadů

Mezi náklady, které musí podnik vynaložit na výrobu, musíme zahrnout například i skladovací náklady na případný vzniklý odpad. Ať už je tento odpad skladován v podniku nebo mimo něj, vždy je to spojeno s nějakými náklady, které musíme do modelu zahrnout. Jsou to například náklady na pronájem, na vytápění skladovacích prostor, energie nebo mzda skladníka. Skladovací náklady jsou dvojího druhu:  

náklady variabilní, které závisí na množství skladovaného odpadu, náklady fixní, které nezávisí na množství skladovaného odpadu (jsou to například nájem, energie nebo mzda skladníka).

Celkové náklady, které souvisí s realizací procesu j, lze vyjádřit takto (podle [3, str. 98]): C( x j )  f j y j  c j x j ,

kde

f j – fixní náklady, které souvisí s realizací j-tého procesu, y j – binární proměnná, která ukazuje, zda je j-tý proces použit (1) nebo ne (0), c j – variabilní náklady připadající na jednu jednotku procesu.

10

Matematický model by v této úloze vypadal takto: účelová funkce: n

z   f j y j  c j x j  MIN , j 1

soustava vlastních omezení: n

a j 1

ij

x j  bi

x j  My j

i = 1, 2, …, m, j = 1, 2, …, n,

(5.1.)

podmínky nezápornosti: j = 1, 2, …, n, xj  0

y j  0(1) kde

j = 1, 2, …, n,

n – počet všech možných způsobů, jak můžeme rozřezat původní materiál, m – počet druhů nařezaného materiálu menších rozměrů, bi – hodnota pravé strany, omezení materiálu menších rozměrů,

aij – kolik kusů i-tého materiálu menších rozměrů získáme, pokud využijeme j-tý

řezný plán, M – dostatečně velké kladné číslo, x j – kolikrát využiji daný způsob řezu. V účelové funkci je suma, protože musíme sečíst náklady pro všechny řezy. Podmínka (5. 1.) ze soustavy vlastních omezení zajišťuje, aby hodnoty proměnné yj nekonvergovaly k nule, z důvodu minimalizace celkových nákladů. Touto podmínkou zajistíme, aby yi j  1 (podle [3, str. 98]). 4.3

Náklady na likvidaci odpadu

Výrobní podniky musí brát v úvahu i náklady na likvidaci vzniklého odpadu, proto se jim vyplatí zabývat se i problematikou optimálního dělení materiálu, kdy je nutné sestavit řezné schéma. Po vyřešení jsou vybrány řezné plány, podle kterých je nejvýhodnější původní materiál rozřezat, tak aby úloha odpovídala zadaným podmínkám. Pokud jsou použity ty řezné plány, u kterých vzniká nějaký odpad, musí firma řešit, jak se vzniklým odpadem naložit. Jednou z možností je likvidace odpadu bez dalšího využití například na skládce. Další možností využití odpadu je zařazení zpět do výroby, pokud je to technologicky možné. Například při práci se dřevem nevznikají jen odřezky dřeva ale také piliny, které je možné dále zpracovat. Záleží však na množství pilin, které je vyprodukováno. Firma si pak může zakoupit různé technologie k jejich dalšímu využití. Při malém množství se z nich mohou vyrábět například brikety na topení nebo mohou sloužit v zemědělství jako podestýlka pod zvířata. Při větším množství vyprodukovaných pilin lze vyrábět například dřevotřískové desky, které mají velmi široké využití při výrobě nábytku. Matematický model pro tuto úlohu vypadá takto: 11

účelová funkce: n

z   l  c j  x j  MIN , j 1

soustava vlastních omezení: a11x1  a12 x2  ...  a1n xn Rb1 , a21x1  a22 x 2 ...  a2 n xn Rb2 , …. am1 x1  am 2 x2  ...  amn xn Rbm , podmínky nezápornosti: xj  0 , bi  0 , kde

j = 1, 2, …, n, i = 1, 2, …, n,

n – počet všech možných způsobů, jak můžeme rozřezat původní materiál, m – počet druhů nařezaného materiálu menších rozměrů, bi – hodnota pravé strany, omezení materiálu menších rozměrů, aij – kolik kusů i-tého materiálu menších rozměrů získám, pokud využiji j-tý řezný plán, c j – variabilní náklady připadající na jednu jednotku procesu, R – relační znaménko ≤, ≥, = je určeno ze zadání ekonomického modelu, x j – kolikrát využiji daný způsob řezu,

l – jednotkové náklady na likvidaci. 4.4

Minimalizace počtu řezů

Pokud firma vyrábí materiálově nebo technologicky náročné výrobky snaží se využít materiál i strojní zařízení co nejefektivněji, aby minimalizovala vzniklé náklady jak na materiálu, tak na opotřebení strojů. Pak může být do modelu zahrnuta další podmínka, a sice podmínka na minimalizaci počtu provedených řezů. Je nutno doplnit řezné schéma o další řádek, ve kterém bude uveden počet řezů u jednotlivých způsobů řezání. Matematický model bude vypadat takto: účelová funkce: z  c1 x1  c2 x2  ...  cn xn  MIN ,

soustava vlastních omezení: a11x1  a12 x2  ...  a1n xn Rb1 , a21x1  a22 x 2 ...  a2 n xn Rb2 , …. am1 x1  am 2 x2  ...  amn xn Rbm , podmínky nezápornosti: xj  0 j = 1, 2, …, n, bi  0 i = 1, 2, …, n, 12

kde n – počet všech možných způsobů, jak můžeme rozřezat původní materiál, m – počet druhů nařezaného materiálu menších rozměrů, c j – počet řezů příslušného způsobu řezání, bi – hodnota pravé strany, omezení pro materiál menších rozměrů, aij – kolik kusů materiálu menších rozměrů získáme, pokud využijeme j-tý řezný

plán, x j – kolikrát je využit daný způsob řezu, R – relační znaménko ≤, ≥, = je určeno ze zadání ekonomického modelu.

4.5

Minimalizace nákladů na řezání

Úloha, ve které je hlavním cílem minimalizace nákladů na řezání, je velmi podobná předchozí úloze (4.4), kde bylo cílem minimalizovat počet řezů. Pro takovýto typ úlohy je důležité znát cenu jednoho řezu, který musíme zahrnout do účelové funkce. Každému řezu přiřadíme cenu, kterou násobíme počtem řezů a dále celou tuto funkci minimalizujeme. Účelová funkce vypadá takto: účelová funkce: z  k  c1 x1  k  c2 x2  ...  k  cn xn  MIN , kde

c j – počet řezů příslušného způsobu řezání, n – počet všech možných způsobů, jak můžeme rozřezat původní materiál, x j – kolikrát využiji daný způsob řezu,

k – cena jednoho řezu. 4.6

Prořezy

Pro většinu školních příkladů je typická poznámka v zadání, že prořez je zanedbatelný a nemusí být zohledňován. Tato poznámka je zde pouze pro zjednodušení příkladu. Ve skutečných příkladech toto většinou není možné. Pokud pracujeme například s dřevěnými deskami jako původním materiálem, které jsou dále kráceny, musíme brát ohled na malou část, která se ztratí během řezání. U práce se dřevem se síla řezu liší podle použité technologie řezání a řezného nástroje, většinou od 2 do 5 mm. Je proto důležité brát tyto prořezy v úvahu. V řezném plánu musí být prořez zohledněn tak, že vzniklý odpad je vždy menší o sílu řezu. Pokud je například v rámci jednoho kusu původního materiálu více řezů, je vzniklý odpad menší vždy o součet všech řezů. Jedná se především o odpad vhodný k dalšímu využití, kdy potřebuji znát skutečný rozměr odpadu. U odpadu určeného k přímé likvidaci se řezy zohledňovat nemusí. Matematický model pro úlohu s prořezy vypadá takto:

13

účelová funkce: z  c1 x1  c2 x2  ...  cn xn  MIN (MAX ) , soustava vlastních omezení: a11x1  a12 x2  ...  a1n xn Rb1 , a21x1  a22 x2  ...  a2 n xn Rb2 , …. am1 x1  am 2 x2  ...  amn xn Rbm , podmínky nezápornosti: j = 1, 2, …, n, x j  0 , celé bi  0

kde

i = 1, 2, …, n,

n – počet všech možných způsobů, jak můžeme rozřezat původní materiál, m – počet druhů nařezaného materiálu menších rozměrů, c j – vzniklý odpad, ve kterém jsou zahrnuty i prořezy,

bi – hodnota pravé strany, omezení pro materiál menších rozměrů, aij – kolik kusů i-tého materiálu menších rozměrů získáme, pokud využijeme j-tý

řezný plán, x j – kolikrát využiji j-tý způsob řezu, R – relační znaménko ≤, ≥, = je určeno ze zadání ekonomického modelu.

4.7

Úloha o svařování

V úlohách o svařování dochází ke spojování vzniklého odpadu tak, aby vznikla potřebná délka desky větší velikosti. Jedná se o to, že mám k dispozici menší díly, ze kterých musím sestavit díl větší potřebný k další výrobě. Je možné opět sestavit schéma, které je využíváno i v úlohách o optimálním dělení materiálu. Úloha může směřovat ke dvěma cílům. Prvním je snaha o minimální počet spojů, jelikož s větším počtem spojů může finální výrobek ztrácet na kvalitě (například může dojít k přelomení v místě spoje). Účelová funkce pro tento případ by vypadala: minimalizovat

z  c1 x1  c2 x2  ...  cn xn , kde

c j – počet spojů pro příslušný způsob svařování (j = 1, 2, …, n), n – počet proměnných v modelu neboli počet způsobů svařování, x j – kolikrát využiji j-tý způsob svaření.

Druhým cílem úlohy o svařování může být maximální počet vzniklých finálních výrobků. Snažíme se vlastně maximalizovat součet všech strukturních proměnných modelu. Účelová funkce by v tomto případě vypadala takto: maximalizovat n

z   xj. j 1

14

4.8

Cílové programování

Jedná se spíše o speciální přístup k řešení úloh lineárního programování než o speciální typ úlohy lineárního programování. V úlohách lineárního programování, které jsem popisovala dosud, byla vždy zadána soustava omezujících podmínek (vlastní omezení úlohy a podmínky nezápornosti), která definovala množinu přípustných řešení úlohy (podle 4, str. 121). V této množině je potom hledáno optimální řešení úlohy s ohledem na zadané kritérium optimality. „V obecném modelu cílového programování je tato formulace poněkud pozměněna. V tomto modelu se více či méně stírají rozdíly mezi omezujícími podmínkami a kritériem optimality tak, jak byly tyto pojmy chápány ve standardním modelu lineárního programování.“ (Citace z [4, str. 121]) Termíny jako omezující podmínky a kritérium optimality jsou nahrazeny za volné a pevné cíle. Každému cíli je potom přiřazena cílová hodnota. Obecně lze tedy říci, že omezení modelu jsou formulována za pomoci cílových hodnot. U pevných cílů musí být cílová hodnota splněna, což je prakticky to samé jako klasické omezující podmínky u běžných úloh LP. U volných cílů stačí, když je cílová hodnota splněna alespoň přibližně. Skutečně dosažená hodnota by měla být blízko cílové hodnotě, ale nemusí být splněna přesně (podle 4, str. 121). Matematický model úlohy cílového programování vypadá takto: účelová funkce: m

z   (d i  d i )  MIN , 



i 1

soustava vlastních omezení:   a11x1  a12 x2  ...  a1n xn  d1  d1  b1 ,

a21x1  a22 x2  ...  a2n xn  d2  d2  b2 , 



….   am1x1  am2 x2  ...  amn xn  dm  dm  bm , podmínky nezápornosti:   di , di  0 ,

i = 1, 2, …, n,

xj  0 , kde

j = 1, 2, …, n,

n – počet strukturních proměnných v modelu, m – počet vlastních omezení v modelu, bi – hodnota pravé strany, která patří i-tému omezení,

ai j – strukturní koeficient, vztah mezi i-tým omezením a j-tou proměnnou, 

d i – kladná odchylka od cílové hodnoty, 

d i – záporná odchylka od cílové hodnoty.

Vlastní omezení ve tvaru rovnosti je nastaveno velmi přísně. Pokud se nepodaří toto omezení splnit, je možné ho upravit na tvar větší nebo rovno. Další možností je přidat k rovnici kladnou odchylku, která by byla v účelové funkci minimalizována. 15

5 Aplikace na reálný příklad – dělení desek při výrobě lyží 5.1

O firmě

Pro řešení reálného problému ve své práci jsem si vybrala úlohu o dělení materiálu, konkrétně „Dělení desek při výrobě lyží“. Všechny potřebné informace mi poskytla firma GALUS Industries s.r.o. „Firma se zabývá výrobou lyží a snowboardů již od roku 1993. Velká část produkce je prodávána přes rakouského partnera k odběratelům do USA, Kanady, Japonska, Německa, Norska a Rakouska. Od roku 2000 začala firma v malém množství vyrábět pro český trh vysoce výkonné závodní lyže pod značkou LUSTI. Na tento krok navázalo postupné rozšiřování sortimentu LUSTI i na ostatní kategorie lyží a snowboardů. V současné době již tvoří výroba a prodej značky LUSTI téměř polovinu z celkové produkce firmy GALUS Industries s.r.o.“ (Citace z [10]) 5.2

Vysvětlení pojmu „dřevěné jádro“

Lyže značky LUSTI se stejně jako lyže ostatních značek skládají z různých materiálů. Jedná se například o ocelové hrany, skluznici, nosné vrstvy jako je prepreg nebo titanal, antivibrační gumové pásky, dřevěná jádra, vrchní fólii atd. Ve své práci se zaměřím pouze na jednu konkrétní surovinu, a sice na dřevěné jádro, které tvoří výplň lyže mezi nosnými vrstvami. Někteří výrobci lyží z ekonomických důvodů nahrazují dřevěná jádra jinými materiály – například polyuretanovou pěnou. Takto vyrobené lyže a snowboardy nedosahují ovšem takové kvality jako výrobky, v nichž je použito dřevo. Pro lepší představu bych přirovnala skladbu lyže například k sádrokartonové desce (k materiálu, který podle mě většina lidí zná). Výplň desky tvoří sádra (v našem případě dřevěné jádro lyže), nosné vrstvy tvoří dva papírové kartony, z každé strany sádrové vrstvy jeden (v našem případě tvoří nosné vrstvy lyže sklolaminátové prepregy nebo titanaly). Pokud bychom vynechali sádru, vznikl by nám spojením dvou kartonů prakticky jen jeden silný karton, ale bez požadovaných vlastností. Pokud bychom vynechali jeden z kartonů, deska by nám praskala právě na straně, kde karton chybí. Pokud bychom dali sádrovou vrstvu moc tenkou, deska by byla velmi měkká a nevydržela by namáhání, pro které je určena. Na stejných principech funguje i konstrukce lyže. V místě, kde chceme mít lyži měkčí (například špička a patka) ztenčíme dřevěné jádro, čímž se nám nosné vrstvy přiblíží k sobě a lyže je v tomto místě měkčí. Na středu lyže naopak uděláme dřevěné jádro širší, čímž oddálíme nosné vrstvy a lyže je v tomto místě tvrdší. Různá tvrdost v různých místech lyže je důležitá pro ovládání, jelikož každou lyži můžeme ovládat pouze z jednoho místa – a to z místa, kde stojíme. Než bude dřevěné jádro připraveno k použití do konkrétní lyže, musí projít určitým výrobním procesem. Dřevěná jádra lze vyrábět různými způsoby i z různých druhů dřev. Nejběžnější variantou je použití klasických prken, která se lepí do bloků, z nichž se řežou

16

plátky v požadované tloušťce. Každé jádro se pak skládá z několika dílů proto, abychom zabránili možnému kroucení dřeva a následně i lyže. Ukázka dřevěného jádra na obrázku č. 1.

Obrázek 1-Složení lyže [dodáno zadavatelem]

Na výrobu lyží se nejvíce používá řezivo z topolu a buku, méně pak například z javoru, smrku, jasanu a olše. Měkká a lehká dřeva (topol, javor, smrk) se vždy používají jako základ a tvrdá dřeva se používají v místě požadovaného zpevnění. U tvrdých dřev je důležité, aby měla dlouhá vlákna a tudíž velkou podélnou pevnost a hlavně také pružnost. Proto se používá zejména buk nebo jasan, naopak není vhodný například dub, který je sice také tvrdý, ale má krátká vlákna a tak je poměrně křehký a snadněji se láme. Další variantou výroby dřevěných jader je například použití desek jednosměrné překližky (jsou to dřevěné desky slepené do požadované tloušťky z jednotlivých dýh daného dřeva – v našem případě dýh o tloušťce 2 mm). Základní podmínkou pro použití tohoto materiálu při výrobě lyží je, aby všechny vrstvy (dýhy) vedly jedním směrem (na rozdíl od klasické překližky, kde se vrstvy kvůli pevnosti v obou směrech kříží). Výhoda této varianty spočívá v maximálním zamezení kroucení výsledného produktu a navíc použití tenkých dýh zcela potlačuje i případné vady dřeva. 5.3

Ekonomický model

Firma GALUS Industries s.r.o. používá k výrobě dřevěných jader výše popsanou variantu s jednosměrnými překližkami, která je sice finančně výrazně náročnější, ale o to kvalitnější je výsledný produkt. Jelikož je tato varianta finančně náročnější, má firma z pochopitelných důvodů zájem na minimalizaci odpadu. Do firmy jsou dodávány překližkové desky o rozměru 244 cm x 122 cm x 1,3 cm. Tyto desky musí být dále rozřezány na čtyři pruhy o rozměru 244 cm x 30,3 cm x 1,3 cm (viz. obrázek č. 2) V tomto případě zohledňujeme tři řezy tenkým pilovým kotoučem na dělící pile o síle cca 3 mm na každý řez.

17

Obrázek 2 - Dřevěná deska [vlastní]

Každá takto nově vzniklá deska se pak zkrátí na délku potřebnou k výrobě jednotlivých lyží. Desky jsou kráceny podle řezného plánu, který je uveden v příloze č. 1. Dále se tyto desky lepí do bloku v předem určeném množství, jak jsem znázornila na obrázku č. 3. Lepí se na sebe vždy počet desek potřebný na daný typ lyže. Množství desek je odlišné, jelikož každá lyže je jinak široká.

Obrázek 3 - Blok [vlastní]

Při lepení desek na sebe se využívají jak celé desky, tak i vzniklé odpady. Mohou se tedy střídat celé desky a kratší (odpadové) desky poskládané vždy do požadované délky. U lyží do 100 cm (včetně) můžeme využívat pouze celé desky, nesmí se zde vyskytovat žádný spoj. U lyží delších než 100 cm můžeme využít jeden spoj, tedy spojit dvě “odpadové“ desky. U těchto odpadových desek musíme zohlednit větší sílu řezu zkracovací pily, která je v tomto případě 5 mm. V současné době řeší firma danou problematiku přípravou materiálu vždy na jeden konkrétní den, čímž vzniká zbytečně velké množství odpadu, který se sice po nějakou dobu skladuje k dalšímu zpracování, ale z důvodu omezené kapacity skladových prostor se po určité době odpad likviduje. Pokud firma nemá předem danou větší zakázku a vyrábí pouze na základě jednotlivých objednávek různé typy lyží, je tato metoda jediná možná. Jelikož firma získala velkou zakázku na konkrétní modely lyží s přesně danými počty, hledá způsob, jak co nejefektivněji využít materiál pro výrobu dřevěných jader.

18

Zadavatel požaduje vyřešení konkrétní zakázky na výrobu 4 520 párů lyží. Trvá na vyrobení přesného množství dřevěných jader a nepřeje si žádné hotové kusy navíc, jelikož pro ně nemá v tuto chvíli další uplatnění. To však neznamená, že se tyto lyže nebudou v budoucnu dále vyrábět. Požadavkům zadavatele vyhovím a omezující podmínky uvedu ve tvaru rovnosti. Pokusím se mu však také navrhnout řešení, kdy omezující podmínky nastavím jako nerovnost. To pravděpodobně povede k výrobě většího množství jednotlivých typů (ty však mohou být použity pro další zakázky), ale také by to mělo vést k výraznému snížení odpadu. Pro tuto konkrétní zakázku jsou potřeba délky lyží uvedené v tabulce č. 1 spolu s požadovanými počty (v kusech a párech). Délka lyže (cm) 75 85 100 140 150 160

Počet (pár) 950 320 1900 450 450 450

Počet (ks) 1900 640 3800 900 900 900

Tabulka č. 1-Počet lyží na zakázku

V tabulce č. 2 jsou uvedeny další parametry nutné pro zjištění potřebného počtu desek a výpočet počtu desek. Zde musíme zohlednit sílu řezu formátovací pily, která je 4 mm. Délka lyže

Počet desek na 1 blok

Šířka

Výška vč. řezu

Počet desek z 1 bloku

Počet desek na jednotlivé lyže

75 cm

8 ks

104 mm 9 mm

13 mm

23 ks

83 bloků x 8 desek = 664 desek

85 cm

11 ks

140 mm 9 mm

13 mm

23 ks

28 bloků x 11 desek = 308 desek

100 cm 9 ks

116 mm 11 mm 15 mm

20 ks

190 bloků x 9 desek = 1710 desek

140 cm 9 ks

108 mm 14 mm 18 mm

16 ks

57 bloků x 9 desek = 513 desek

150 cm 9 ks

108 mm 15 mm 19 mm

16 ks

57 bloků x 9 desek = 513 desek

160 cm 9 ks

108 mm 16 mm 20 mm

15 ks

607 bloků x 9 desek = 540 desek

Výška

Tabulka č. 2-Počet desek

19

5.4

Matematický model

Proměnné: x1 – x29 vyjadřují, kolikrát je využit plán číslo 1 – 29. Řezný plán je uveden v příloze číslo 1. Omezující podmínky pro případ rovnosti: x1  x13  x16  x17  x18  x19  x20  x21  x22  x23  540 ks, x2  x3  x14  x24  x25  x26  513 ks, x4  x5  x6  x15  x27  x28  x29  513 ks, x4  2 x7  x8  x9  1710 ks, x2  x5  x8  2 x10  x11  308 ks, x1  x3  x6  x9  2 x11  3x12  x20  x21  x22  x23  664 ks. x j  0, celé

j = 1,…, 29

Omezující podmínky pro případ nerovnosti: x1  x13  x16  x17  x18  x19  x20  x21  x22  x23  540 ks, x2  x3  x14  x24  x25  x26  513 ks, x4  x5  x6  x15  x27  x28  x29  513 ks, x4  2 x7  x8  x9  1710 ks, x2  x5  x8  2 x10  x11  308 ks, x1  x3  x6  x9  2 x11  3x12  x20  x21  x22  x23  664 ks. x j  0, celé

j = 1,…, 29

Účelová funkce: 8,5 x1 + 8,5 x2 + 18,5 x3 + 3,5 x4 + 18,5 x5 + 28,5 x6 + 43,5 (x7 - x27) + 58,5 (x8 - x22 - x25 x28) + 68,5 (x9 - x20 - x23 - x26 - x29) + 73,5 (x10 – x18 - x21 - x24 - x29) + 8,5 x11 + 18,5 x12 + 83,5 (x13 – x17 – x19 - x24 - x26 - x28) + 93,5 (x14 – x16 – x19 - x21 - x23 - x25) + 103,5 (x15 – x16 – x17 – x18 - x20 - x22 - x27) + 37 x16 + 27 x17 + 17 x18 + 17 x19 + 12 x20 + 7 x21 + 2 x22 + 2 x23 +7 x24 + 2 x25 +2 x26 +7 x27 +2 x28 +2 x29 → MIN. Pomocí účelové funkce zjistím, jak velký bude vzniklý odpad. Jelikož některý odpad bude dále zpracován, musela jsem tuto skutečnost v účelové funkci zohlednit. Každý zpracovatelný odpad může být však využit pro několik délek lyží. Musela jsem proto zajistit, aby odpad nebyl využíván duplicitně (pokud odpad použiji na jednu délku lyží, nemohu ten stejný odpad použít na jinou délku). Číselné hodnoty v účelové funkci vyjadřují velikost odpadu včetně prořezů. Tedy odpadu, který se může dále zpracovat. Velikost tohoto odpadu jsem zjistila sestavením řezného plánu, který je uveden v příloze č. 1. Proměnné xj vyjadřují, kolikrát je využit každý řezný plán. Účelová funkce je minimalizační, protože se snažím, aby

20

vzniklý odpad byl co nejmenší. Pro všechny varianty řešení (kromě 5.5.1) je účelová funkce stejná, mění se pouze omezující podmínky, proto účelovou funkci dále v řešení neuvádím. 5.5

Řešení

Úlohu jsem řešila v programu MS Excel, pomocí řešitele. Tento program je mi nejbližší a pro danou problematiku se mi jevil i jako nejvhodnější. Při řešení této úlohy jsem narazila na několik problémů ale i nesrovnalostí, které se mi však po konzultaci se zadavatelem podařilo vyřešit. Všechny možnosti řešení, ke kterým jsem došla, jsou přiloženy na CD a všechny výsledky jsou uvedeny v příloze. 5.5.1

Řešení s využitím pouze efektivních řezných plánů

Z počátku jsem při tvorbě řezného schématu uvažovala pouze efektivní řezné plány. To jsou plány s minimálním odpadem. V našem případě se jednalo o nezařazení plánů, kdy bychom z desky 244 cm uřízli jen jednu délku lyže nad 140 cm a zbylý odpad nevyužili, přestože by šel zpracovat na kratší lyže do 100 cm. A navíc v případě, kdy jsem vyhověla požadavkům zadavatele na přesný počet vyrobených jader a omezující podmínky nastavila jako rovnost (to znamená, že je vyroben přesný počet výrobků, který byl zadán, bez možnosti navýšení), neměla úloha přípustné řešení. Proto jsem pro další řešení zařadila možnost neefektivního rozřezání dřevěných desek (viz výše vysvětlené). Matematický model této úlohy: omezující podmínky: x1  540 ks,

x2  x3  513 ks, x4  x5  x6  x13  513 ks, x4  2 x7  x8  x9  1710 ks, x2  x5  x8  2 x10  x11  308 ks, x1  x3  x6  x9  2 x11  3x12  664 ks, x j  0, celé

j = 1,…,29,

účelová funkce: 8,5 x1 + 8,5 x2 + 18,5 x3 + 3,5 x4 + 18,5 x5 + 28,5 x6 + 43,5 x7 + 58,5 x8 + 68,5 (x9 – x13) + 73,5 (x10 – x13) + 8,5 x11 + 18,5 x12 + 2 x13 → MIN. 5.5.2

Řešení ve tvaru rovnosti

Ve druhé variantě jsem do řezného schématu zahrnula i neefektivní řezné plány. Tyto plány měly sice velký odpad, ale ten mohl být dále velmi dobře zpracován. V Excelu jsem tedy vytvořila dvě řezná schémata. V prvním schématu jsem rozřezala původní desky délky 244 cm a ve druhém schématu jsem k výrobě použila zbylé odpady. Jelikož se v lyžích může 21

vyskytovat pouze jeden spoj, musela jsem vždy sečíst maximálně dva odpady. V případě, že součet délek těchto odpadů byl větší než potřebný, musely být dále zkráceny na požadovanou délku (čímž sice vznikl další odpad, který ale byl již výrazně menší). Využití odpadů jsem musela zohlednit i v účelové funkci, protože není možné využít odpad vícekrát, než kolikrát vznikl. A opět jsem dle zadání nastavila všechny omezující podmínky ve tvaru rovnosti. Soustava omezení vypadala takto: x1  x13  x16  x17  x18  x19  x20  x21  x22  x23  540 ks, x2  x3  x14  x24  x25  x26  513 ks, x4  x5  x6  x15  x27  x28  x29  513 ks, x4  2 x7  x8  x9  1710 ks, x2  x5  x8  2 x10  x11  308 ks, x1  x3  x6  x9  2 x11  3x12  x20  x21  x22  x23  664 ks, x j  0, celé

j = 1,…,29.

V tomto případě úloha již řešení měla. Díky výrobě přesného množství desek vznikl ale příliš velký odpad. Činil 17 512 cm, což je součet zbytků desek 30,5 x 1,3 cm. Proto jsem zadavateli navrhla další variantu řešení ve tvaru nerovnosti, která vedla ke snížení odpadu. Výsledné hodnoty tohoto řešení včetně přídatných proměnných jsou uvedeny v příloze č. 2. 5.5.3

Řešení ve tvaru nerovnosti

Ve třetí variantě jsem „uvolnila“ omezující podmínky a omezení nastavila ve tvaru větší nebo rovno (což znamená možnost vyrobit více kusů, než bylo zadáno), tím došlo k velkému snížení odpadu. Nový odpad činil 3420 cm, což je pouhých 19,5 % odpadu z předchozí varianty (17 512 cm). Počet vyrobených a tím i použitelných desek se však velmi zvýšil. Důkaz je uveden v tabulce č. 3, kde jsou zapsány požadované a skutečné počty vyrobených desek, které jsem získala řešením v Excelu. Délky lyží 160 cm 150 cm 140 cm 100 cm 85 cm 75 cm

Skutečný Požadovaný počet(ks) počet ks desek 1710 1197 513 1710 513 1197

540 513 513 1710 308 664

Tabulka č. 3-Počet desek

22

Omezující podmínky této varianty řešení vypadají takto: x1  x13  x16  x17  x18  x19  x20  x21  x22  x23  540 ks, x2  x3  x14  x24  x25  x26  513 ks, x4  x5  x6  x15  x27  x28  x29  513 ks, x4  2 x7  x8  x9  1710 ks, x2  x5  x8  2 x10  x11  308 ks, x1  x3  x6  x9  2 x11  3x12  x20  x21  x22  x23  664 ks, x j  0, celé

j = 1,…,29.

Ačkoliv se řešení z hlediska minimálního odpadu jeví jako velmi výhodné, pro zadavatele příliš vhodné není. Některá přebytečná jádra je sice schopen využít pro další zakázky, neboť se jedná o prodávanou a oblíbenou délku lyže. Některá jsou pro něj ale naprosto zbytečná, neboť poptávka po lyžích této délky není tak velká a desky by zbytečně a bez dalšího využití v dohledné době zbývaly na skladě. Výsledné hodnoty této varianty řešení včetně přídatných proměnných jsou uvedeny v příloze č. 3. 5.5.4

Řešení ve tvaru nerovnosti s překročením požadovaného množství o 25 % a 50 %

Jelikož žádná z předchozích variant nebyla úplně ideální, ať už z důvodu nadměrného odpadu nebo přebytečného množství nepotřebných desek, navrhla jsem zadavateli ještě další možnost, a sice že je možné nastavit pouze určitý limit pro překročení vyrobeného počtu desek. Při konzultaci se zadavatelem bylo dohodnuto, že za únosné můžeme považovat překročení v první variantě maximálně o 25 % a ve druhé maximálně o 50 %. Soustava omezení pro maximální navýšení o 25 % by vypadal takto: x1  x13  x16  x17  x18  x19  x20  x21  x22  x23  1,25  540 ks, x2  x3  x14  x24  x25  x26  1,25  513 ks, x4  x5  x6  x15  x27  x28  x29  1,25  513 ks, x4  2 x7  x8  x9  1,25 1710 ks, x2  x5  x8  2 x10  x11  1,25  308 ks, x1  x3  x6  x9  2 x11  3x12  x20  x21  x22  x23  1,25  664 ks, x1  x13  x16  x17  x18  x19  x20  x21  x22  x23  540 ks, x2  x3  x14  x24  x25  x26  513 ks, x4  x5  x6  x15  x27  x28  x29  513 ks, x4  2 x7  x8  x9  1710 ks, x2  x5  x8  2 x10  x11  308 ks,

23

x1  x3  x6  x9  2 x11  3x12  x20  x21  x22  x23  664 ks, x j  0, celé

j = 1,…,29.

Pokud bychom požadovaný počet navýšili o maximálně 25 %, celkový odpad by činil 12 521 cm.

Soustava omezení pro maximální navýšení o 50 % by vypadal takto: x1  x13  x16  x17  x18  x19  x20  x21  x22  x23  1,50  540 ks, x2  x3  x14  x24  x25  x26  1,50  513 ks, x4  x5  x6  x15  x27  x28  x29  1,50  513 ks, x4  2 x7  x8  x9  1,50 1710 ks, x2  x5  x8  2 x10  x11  1,50  308 ks, x1  x3  x6  x9  2 x11  3x12  x20  x21  x22  x23  1,50  664 ks, x1  x13  x16  x17  x18  x19  x20  x21  x22  x23  540 ks, x2  x3  x14  x24  x25  x26  513 ks, x4  x5  x6  x15  x27  x28  x29  513 ks, x4  2 x7  x8  x9  1710 ks, x2  x5  x8  2 x10  x11  308 ks, x1  x3  x6  x9  2 x11  3x12  x20  x21  x22  x23  664 ks, x j  0, celé

j = 1,…,29.

Pokud bychom navýšili požadovaný počet dřevěných jader o maximálně 50 %, získali bychom odpad o velikosti pouze 7556 cm, což je odpad velmi přijatelný. Výhodou těchto dvou modelů je skutečnost, že přijatelné navýšení množství dřevěných jader výrazně sníží vzniklý odpad. Toto navýšení je však pro firmu výhodné pouze při možném zpracování jader v blízké budoucnosti. Výsledné hodnoty této varianty řešení včetně přídatných proměnných jsou uvedeny v příloze č. 4. 5.5.5

Konečné řešení

Přes uspokojivý výsledek výše uvedených variant jsem zadavateli navrhla konečné řešení, kdy si mohl přesně stanovit délky lyží, u kterých bude moci dojít k navýšení požadovaného množství. Na základě této informace mi zadavatel dodal přesné údaje,

24

u kterých délek lyží může dojít k navýšení množství a o kolik. Tato čísla jsem přehledně uspořádala do tabulky č. 5. Požadovaný počet ks desek

Délka 160 cm 150 cm 140 cm 100 cm 85 cm 75 cm

Nejvyšší možný počet ks desek

540 513 513 1710 308 664

540 850 850 1710 308 1000

Tabulka č. 4-Navýšení množství

Soustava omezení konečného řešení by vypadala takto: x1  x13  x16  x17  x18  x19  x20  x21  x22  x23  540 ks, x2  x3  x14  x24  x25  x26  513 ks, x2  x3  x14  x24  x25  x26  850 ks, x4  x5  x6  x15  x27  x28  x29  513 ks, x4  x5  x6  x15  x27  x28  x29  850 ks, x4  2 x7  x8  x9  1710 ks, x2  x5  x8  2 x10  x11  308 ks, x1  x3  x6  x9  2 x11  3x12  x20  x21  x22  x23  664 ks. x1  x3  x6  x9  2 x11  3x12  x20  x21  x22  x23  1000 ks. x j  0, celé

j = 1,…, 29

Po této úpravě jsem získala odpad o velikosti 8 173 cm. Což je vzhledem k zadaným podmínkám přijatelný výsledek. Výsledné hodnoty této varianty řešení včetně přídatných proměnných jsou uvedeny v příloze č. 5. 5.6

Hodnocení výsledků

Během řešení zadané práce jsem došla k několika různým výsledkům, ale ne všechny byly uspokojivé. Například v první variantě 5.5.1 jsem pracovala pouze s efektivními řeznými plány a omezení nastavila ve tvaru rovnosti. Tato varianta však neměla řešení. Proto jsem v další variantě 5.5.2 do řezného schématu zařadila i neefektivní řezné plány, u kterých sice vznikal velký odpad, ten byl ale dále zpracovatelný. Omezení jsem nastavila opět jako rovnost a vznikl odpad o velikosti 17 512 cm. Jelikož byl tento odpad příliš velký, vypracovala jsem variantu 5.5.3, kde jsou omezující podmínky nastaveny ve tvaru větší nebo rovno s tím, že jsem překročení nijak nelimitovala. Výsledný odpad v této variantě sice činil pouhých 3420 cm, ale počet desek na výrobu dřevěných jader se zvýšil nad množství 25

tolerované zadavatelem. Proto jsem ve variantě 5.5.4 přidala k omezujícím podmínkám překročení požadovaného množství o maximálně 25 % nebo o maximálně 50 %. Při překročení o max. 25 % vznikl odpad o velikosti 12 521 cm a při překročení o max. 50 % činil odpad 7 556 cm. Odpad u této varianty byl sice přijatelný, ale překročené množství desek bylo pro zadavatele akceptovatelné pouze u některých délek. Proto jsem navrhla konečnou variantu 5.5.5, kde zadavatel přesně určil, u kterých délek a na jakou hodnotu bude možné navýšit požadované množství. Tato varianta je pro konkrétní zakázku i následnou výrobu velmi výhodná a zadavatel ji proto využije. Při této variantě je spotřebováno 2 415 kusů desek rozměru 240 cm x 30,5 cm. Vznikl odpad o velikosti 8 173 cm, který nebude možné dále zpracovat a bude tedy zlikvidován. Oproti první variantě 5.5.2 kdy omezující podmínky byly nastaveny ve tvaru rovnosti, se odpad snížil o 53,3 %. 5.7

Program v Excelu

Jak jsem postupně procházela různými fázemi řešení, napadlo mě, že by se má bakalářská práce nemusela vztahovat pouze k této jedné zakázce, ale mohla by firmě pomoci při řešení každodenních problémů s řezáním desek. Proto jsem v Excelu vytvořila mini program, který může být zaměstnanci firmy denně využíván. Po několika méně povedených variantách jsem dospěla k závěru, že nejvhodnější bude řezný plán uspořádat do dvou tabulek. V jedné tabulce je základní rozřezání celých desek a ve druhé tabulce zpracování vzniklého odpadu z první tabulky. Pro přehlednost jsem vzniklý odpad z jednotlivých řezných plánů barevně rozlišila, čímž je na první pohled zřejmé, které odpady jsou vlastně zpracovávány. Tato varianta je důležitá také proto, že kombinací různých odpadů nám vznikají stejné délky výsledných desek a bez barevného rozlišení je obtížné se ve vzniklých odpadech orientovat. Názornou ukázku uvádím na obrázku č. 4.

Obrázek 4-Zpracování desek

Pro požadovaný počet kusů na konkrétní den jsem do programu vložila další tabulku. Tuto tabulku jako jedinou bude vyplňovat zaměstnanec firmy. Tabulka je vyobrazena na obrázku č. 5. 26

Obrázek 5-Počty kusů

Pro přehlednost jsem pomocí excelovské funkce „KDYŽ“ zajistila, aby se ve výsledku zobrazovala čísla pouze u využitých plánů, a u těch nevyužitých aby bylo místo nuly prázdné políčko. Bez této funkce byla tabulka nepřehledná, zejména u jednociferných výsledků, kdy čísla splývala s nulou a dala se tak lehce přehlédnout. Dále jsem na této stránce vytvořila tři tlačítka a pomocí Visual Basicu je napojila na makra. Jsou to tlačítka řešit, tisk a uložit. Zaměstnanec tedy jen vyplní počty dřevěných desek, které jsou na daný den naplánovány vyrobit. Poté klikne na tlačítko „Řešit“ a ve výše uvedených tabulkách (obrázek č. 4) se mu zobrazí, jak a v jakých počtech má desky nařezat a jakým způsobem zpracovat vzniklé odpady. Dále stiskne tlačítko „Tisk“ a na jeden papír se mu vytisknou všechny tabulky, které si odnese do své dílny. Nakonec ještě stiskne tlačítko „Uložit“ a tabulky se uloží do listu archiv, s datem vytvoření, kde jsou kdykoliv k nahlédnutí. Poté se všechny tabulky na listu řešení vynulují a jsou připraveny pro další použití. Uložené tabulky v archivu se dají v případě potřeby jednoduše smazat bez vlivu na funkci programu. Pole s datem na listu řešení jsem nastavila pomocí funkce „DNES“ tak, aby se při každém novém otevření programu nastavilo aktuální datum. Jak jsem již výše popsala, může mít zaměstnanec zadán přesný počet dřevěných desek, které mají být daný den a v daných rozměrech vyrobeny, ale také může dostat zadány jen počty lyží, které musí na počty desek teprve převést. Proto mě ještě napadlo tuto operaci zaměstnanci zjednodušit a pro případ potřeby jsem do výsledné aplikace vytvořila ještě převodní tabulku. Výše v tabulce č. 2 jsem srozumitelně popsala postup, jak ze zadaného počtu lyží získáme počet desek (tedy pravé strany omezení), které se musí vyrobit. Tuto tabulku jsem ve velmi zjednodušené formě převedla i do výsledné aplikace. Zaměstnanec tedy pouze v případě potřeby vyplní počty lyží, které mají být vyrobeny, a automaticky se mu vypočítá, kolik bude na množství lyží v dané délce potřebovat dřevěných desek. Tyto hodnoty zaměstnance už jen zadá do tabulky, která je k tomu určena (obrázek č. 5) a může nechat úlohu vyřešit. Tato nová tabulka není napojená na makra ani se neukládá spolu s dalšími tabulkami do archivu, neboť slouží jen jako pomocná pro případ potřeby a není důvod ji ukládat. Získané hodnoty, jsou vždy uvedeny v tabulce, kterou ručně vyplňuje zaměstnanec při řešení každé úlohy a tedy i uloženy. Přepočítací tabulka je vyobrazena na obrázku č. 6.

27

Obrázek 6-Přepočítací tabulka

Další problém, který jsem řešila na tomto listu, bylo nezobrazování celkového odpadu. Účelovou funkci jsem nastavila jako minimalizační a hodnotu vzniklého odpadu již na listu řešení nezobrazuji, protože při této variantě není důležitá. Pro případ potřeby je k nahlédnutí ve skrytém listu zadání. Naopak dle mého názoru je důležité, aby byl zobrazován celkový počet desek, které je nutné na danou zakázku vyskladnit. Konečná verze aplikace je zobrazena na obrázku č. 7.

Obrázek 7-Aplikace

Jelikož mé znalosti Visual Basicu nestačily na vytvoření některých částí této aplikace tak, aby odpovídala mým představám, byla jsem nucena je konzultovat. Jednalo se především o přenesení funkce řešitele z listu zadání na tlačítko „řešit“ na list řešení. Na základě těchto odborných rad jsem práci dokončila dle mých představ. Aplikace je přiložena na CD.

28

Závěr Tato bakalářská práce se primárně zabývá jednou z typických úloh lineárního programování, a sice úlohou o optimálním dělení materiálu. Jelikož je pro úlohy o optimálním dělení materiálu důležité, aby výsledky byly v celých číslech, věnovala jsem první kapitolu celočíselnému programování. Vysvětlila jsem, co vlastně je celočíselné programování, v jakých úlohách se využívá a jaké jsou metody pro řešení úloh celočíselného programování. V dalších dvou kapitolách jsem se zaměřila na typické a netypické cíle při řešení úloh o optimálním dělení materiálu. Mezi typické cíle patří minimalizace celkové odpadu a minimalizace spotřebovaného materiálu. Mezi netypické cíle zahrneme například úlohy s prořezy, úlohy o svařování a mnohé další. S některými z těchto úloh jsem se setkala i v praktické části práce. Nejdůležitější částí této práce je praktická úloha dělení materiálu ve firmě, zabývající se výrobou lyží. Od prvotních řešení s využitím pouze efektivních řezných plánů jsem se postupně dopracovala k řešením s využitím neefektivních plánů, u nichž je zase zpracováváno velké množství odpadu. Dále jsem se zabývala variantami řešení se změnami v omezujících podmínkách, ať už změny ve znaménku (v našem případě = nebo ) nebo změny pravých stran. Všechny tyto změny vedly v konečném důsledku ke zlepšení výsledných hodnot. Primárním cílem této práce bylo dělení dřevěných desek, používaných k výrobě lyží, tak aby vzniklý odpad byl co nejmenší. Po několika úpravách řešení jsem se ke konečné variantě úspěšně dopracovala a cíl práce byl splněn. Teoreticky možným rozšířením práce by mohla být minimalizace počtu použitých desek. Já jsem tuto úlohu nezpracovávala, protože počet desek na konkrétní lyže je již předem přesně zadán technologií výroby. Na základě nových poznatků jsem se navíc rozhodla vypracovat malou aplikaci v Excelu, která poslouží firmě pro řešení každodenních problémů při řezání dřevěných desek. Jedná se o mini program, kde zaměstnanec firmy vyplní počty lyží, které je potřeba vyrobit daný den. Program automaticky vypočítá kolik desek a v jakých délkách je na danou zakázku nutno nařezat. Zároveň zaměstnanci ukáže kolik desek velikosti 244x30,5 cm musí na danou zakázku vyskladnit. Výsledek každé úlohy si může zaměstnanec vytisknout a následně uložit do archivu. Po uložení se celý program vynuluje a připraví k dalšímu použití. Kromě vyřešení zadaného úkolu pokládám i toto za svůj přínos pro firmu. Práce mi dala spoustu nových znalostí a zkušeností. Při řešení praktické části práce jsem si vyzkoušela reálnou úlohu o optimálním dělení materiálu jak s typickými tak i netypickými cíli. Díky řešení tohoto problému jsem navíc získala nový pohled na problematiku nakládání s odpady ve firmě. Všechny výstupy, ke kterým jsem během řešení dospěla, jsou uvedeny v příloze a dále přikládám CD s aplikací v Excelu. 29

Seznam použité literatury [1] FÁBRY, Jan a Josef JABLONSKÝ. Matematické modelování: kvantitativní metody pro ekonomické rozhodování. Vyd. 1. Praha: Oeconomica, 2007, 146 s. ISBN 97880-245-1266-2. [2] FIALA, Petr. Modely a metody rozhodování. Vyd. 1. Praha: Oeconomica, 2003, 292 s. ISBN 80-245-0622-X. [3] JABLONSKÝ, Josef. Programy pro matematické modelování. Vyd. 1. Praha: Oeconomica, 2007, 258 s. ISBN 978-80-245-1178-8. [4] JABLONSKÝ, Josef. Operační výzkum: kvantitativní metody pro ekonomické rozhodování. 3. Vyd. Praha: Professional Publishing, 2007, 323 s. ISBN 978-8086946-44-3. [5] LAGOVÁ, Milada a Josef JABLONSKÝ. Lineární modely. Vyd. 1. Praha: Oeconomica, 2004, 286 s. ISBN 80-245-0816-8. [6] LAGOVÁ, Milada. Lineární modely v příkladech. 1.vyd. Praha: Vysoká škola ekonomická, 2002, 273 s. ISBN 80-245-0456-1. [7] LAGOVÁ, M., KALČEVOVÁ, J. Přednášky k předmětu 4EK213. 2009. [8] PELIKÁN, Jan. Diskrétní modely. Vyd. 1. V Praze: Vysoká škola ekonomická v Praze, 1999, 163 s. ISBN 80-707-9179-9.

Webové stránky [9] Otázky ke II. části písemné zkoušky [online]. 2007 [cit. 2013-03-23]. Dostupné z: http://econ.muny.cz/data/PMEMMI/PMEMMI_otazky_k_casti_II_p2007.pdf [10] LYŽE LUSTI [online]. ©1993 - 2011 [cit. 2013-03-15]. Dostupné z: www.lusti.cz

30

Přílohy

XIV.

XV.

XXIX.

XIII.

XXVIII.

XII.

XXVII.

XI.

XXVI.

X.

XXV.

IX.

XXIV.

VIII.

XXIII.

VII.

XXII.

VI.

0

0

0

0

0

0

0

0

0

0

1

0

0

1

1

1

1

1

1

1

1

0

0

0

0

0

0

150 cm

1

1

0

0

0

0

0

0

0

0

0

0

1

0

0

0

0

0

0

0

0

0

1

1

1

0

0

0

140 cm

0

0

0

1

1

1

0

0

0

0

0

0

0

0

1

0

0

0

0

0

0

0

0

0

0

0

1

1

1

100 cm

0

0

0

1

0

0

2

1

1

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

85 cm

0

1

0

0

1

0

0

1

0

2

1

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

75 cm Odpad vč. prořezů

1

0

1

0

0

1

0

0

1

0

2

3

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

9

9

19

4

19

29

44

59

69

74

9

19

84

94

104

37

27

17

17

12

7

2

2

7

2

2

7

2

2

8,5

8,5

18,5

3,5

18,5

28,5

43,5

58,5

68,5

73,5

8,5

18,5

83,5

93,5

103,5

37

27

17

17

12

7

2

2

7

2

2

7

2

2

Použitelný odpad

31

XXI.

V.

0

0

XX.

IV.

1

XIX.

III.

XVIII.

II.

160 cm

XVI.

I.

XVII.

Příloha č. 1: Řezné schéma

Příloha č. 2: Řešení ve tvaru rovnosti Proměnná x1 x2 x3 x4 x5 x6 x7 x8 x9 x10 x11 x12 x13 x14 x15 x16 x17 x18 x19 x20 x21 x22 x23 x24 x25 x26 x27 x28 x29

Hodnota 7 0 0 349 0 0 342 20 657 144 0 0 533 0 0 0 0 0 0 0 0 0 0 0 0 513 0 20 144

Hodnoty proměnné xj znamenají, že řezný plán x1 bude využit 7 krát, x4 349 krát, x7 342 krát, x8 20 krát, x9 657 krát, x10 144 krát, x13 533 krát, x26 513 krát, x28 20 krát, x29 144 krát a ostatní plány využity nebudou. Hodnota účelové funkce (celkový odpad) činí 17 512 cm.

32

Příloha č. 3: Řešení ve tvaru nerovnosti Proměnná x1 x2 x3 x4 x5 x6 x7 x8 x9 x10 x11 x12 x13 x14 x15 x16 x17 x18 x19 x20 x21 x22 x23 x24 x25 x26 x27 x28 x29

Hodnota 0 0 0 0 0 0 0 513 1197 0 0 0 513 1197 0 0 0 0 0 0 0 0 1197 0 0 0 0 513 0

Hodnoty proměnné xj znamenají, že řezný plán x8 bude využit 513 krát, x9 1197 krát, x13 513 krát, x14 1197 krát, x23 1197 krát, x28 513 krát a ostatní plány využity nebudou. Přídatné proměnné: 160 cm – chtěli jsme vyrobit 540 ks desek ale máme o 135 ks více, tedy 675 ks, 150 cm – chtěli jsme vyrobit 513 ks desek ale máme o 128 ks více, tedy 641 ks, 140 cm – chtěli jsme vyrobit 513 ks desek ale máme o 128 ks více, tedy 641 ks, 100 cm – chtěli jsme vyrobit 1710 ks desek a máme přesně 1710 ks, 85 cm – chtěli jsme vyrobit 308 ks desek ale máme o 76 ks více, tedy 384 ks, 75 cm – chtěli jsme vyrobit 664 ks desek ale máme o 152 ks více, tedy 816 ks. Hodnota účelové funkce (celkový odpad) činí 3 420 cm.

33

Příloha č. 4: Řešení ve tvaru nerovnosti s překročením požadovaného množství o 25 % Proměnná x1 x2 x3 x4 x5 x6 x7 x8 x9 x10 x11 x12 x13 x14 x15 x16 x17 x18 x19 x20 x21 x22 x23 x24 x25 x26 x27 x28 x29

Hodnota 0 0 0 432 0 0 214 34 816 175 0 0 34 641 0 0 0 0 0 0 0 0 641 0 0 0 0 34 175

Hodnoty proměnné xj znamenají, že řezný plán x4 bude využit 432 krát, x7 214 krát, x8 34 krát, x9 816 krát, x10 175 krát, x13 34 krát, x14 641 krát, x23 641 krát, x28 34, x29 175 krát a ostatní plány využity nebudou. Přídatné proměnné: 160 cm – chtěli jsme vyrobit 540 ks desek ale máme o 1170 ks více, tedy 1710 ks, 150 cm – chtěli jsme vyrobit 513 ks desek ale máme o 684 ks více, tedy 1197 ks, 140 cm – chtěli jsme vyrobit 513 ks desek a máme přesně 513 ks, 100 cm – chtěli jsme vyrobit 1710 ks desek a máme přesně 1710 ks, 85 cm – chtěli jsme vyrobit 308 ks desek ale máme o 205 ks více, tedy 513ks, 75 cm – chtěli jsme vyrobit 664 ks desek ale máme o 533 ks více, tedy 1197 ks. Hodnota účelové funkce (celkový odpad) činí 12 521 cm. 34

Příloha č. 5: Řešení ve tvaru nerovnosti s překročením požadovaného množství o 50 % Proměnná x1 x2 x3 x4 x5 x6 x7 x8 x9 x10 x11 x12 x13 x14 x15 x16 x17 x18 x19 x20 x21 x22 x23 x24 x25 x26 x27 x28 x29

Hodnota 0 0 0 519 0 0 85 40 981 211 0 0 40 770 0 0 0 0 0 0 0 0 70 0 0 0 0 40 211

Hodnoty proměnné xj znamenají, že řezný plán x4 bude využit 519 krát, x7 85 krát, x8 40 krát, x9 981 krát, x10 211 krát, x13 40 krát, x14 770 krát, x23 70 krát, x28 40, x29 211 krát a ostatní plány využity nebudou. Přídatné proměnné: 160 cm – chtěli jsme vyrobit 540 ks desek ale máme o 270 ks více, tedy 810 ks, 150 cm – chtěli jsme vyrobit 513 ks desek ale máme o 257 ks více, tedy 770 ks, 140 cm – chtěli jsme vyrobit 513 ks desek ale máme o 257 ks více, tedy 770 ks, 100 cm – chtěli jsme vyrobit 1710 ks desek a máme přesně 1710 ks, 85 cm – chtěli jsme vyrobit 308 ks desek ale máme o 154 ks více, tedy 462 ks, 75 cm – chtěli jsme vyrobit 664 ks desek ale máme o 317 ks více, tedy 981 ks. Hodnota účelové funkce (celkový odpad) činí 7 556 cm. 35

Příloha č. 6: Řešení s navýšením u určených typů lyží Proměnná x1 x2 x3 x4 x5 x6 x7 x8 x9 x10 x11 x12 x13 x14 x15 x16 x17 x18 x19 x20 x21 x22 x23 x24 x25 x26 x27 x28 x29

Hodnota 0 0 0 216 0 0 361 156 616 76 0 16 540 155 279 0 0 0 0 0 0 0 0 0 155 540 279 0 76

Hodnoty proměnné xj znamenají, že řezný plán x4 bude využit 216 krát, x7 361 krát, x8 156 krát, x9 616 krát, x10 76 krát, x12 16 krát, x13 540 krát, x14 155 krát, x15 279 krát, x25 155, x26 540, x27 279 krát, x29 76 krát a ostatní plány využity nebudou. Přídatné proměnné: 160 cm – chtěli jsme vyrobit 540 ks desek a máme přesně 540 ks, 150 cm – chtěli jsme vyrobit 513 ks desek ale máme o 337 ks více, tedy 850 ks, 140 cm – chtěli jsme vyrobit 513 ks desek ale máme o 337ks více, tedy 850 ks, 100 cm – chtěli jsme vyrobit 1710 ks desek a máme přesně 1710 ks, 85 cm – chtěli jsme vyrobit 308 ks desek a máme přesně 308 ks, 75 cm – chtěli jsme vyrobit 664 ks desek a máme přesně 664 ks. Hodnota účelové funkce (celkový odpad) činí 8 173 cm.

36

Příloha č. 6: Simplexová metoda Princip simplexové metody Simplexová metoda se často používá pro nalezení optimálního řešení 1 úloh lineárního programování. Je to metoda založená na iteračním postupu výpočtu. Umožňuje efektivněji využít základní větu LP („Jestliže má úloha LP optimální řešení, má také optimální řešení základní.“). Simplexová metoda prohledává množinu základních řešení2 úlohy lineárního programování a snaží se nalézt optimální řešení. Počet iterací je konečný, proto je výsledek na konci vždy přesně zjištěn. Buď může být nalezeno optimální řešení s nejlepší hodnotou účelové funkce (v případě maximalizace je hodnota účelové funkce co nejvyšší, v případě minimalizace je hodnota účelové funkce naopak co nejnižší), nebo se zjistí, že optimální řešení úlohy neexistuje. Není však nutné počítat všechna základní řešení, můžeme si vybírat pouze základní přípustná řešení3 a z nich potom jen taková, která jsou s ohledem na hledaný extrém přínosná. „Znamená to vlastně sledovat „cestu“, která vede přes základní přípustná řešení k základnímu optimálnímu řešení.“ (Citace z [7, přednáška č. 3, str. 8]) Výpočet pomocí simplexové metody můžeme rozdělit do dvou základních fází. První fáze se zaměřuje na nalezení nebo výpočet výchozího základního řešení úlohy lineárního programování. „Má-li úloha lineárního programování přípustné řešení, musí být alespoň jedno z nich základní. Pokud metoda žádné základní přípustné řešení úlohy LP nenajde, neexistuje ani přípustné řešení úlohy.“ (Citace z [1, str. 31]) Pokud však je simplexovou metodou nalezeno základní přípustné řešení úlohy LP, pokračuje výpočet druhou fází. Druhá fáze je iterační postup, který vede k samotné optimalizaci účelové funkce. Jedná se vlastně o postupné prozkoumávání množiny základních řešení zadané úlohy lineárního programování. Každá další iterace nám poskytne nové základní řešení, které nabízí lepší hodnotu účelové funkce. Při využití simplexové metody nezískáme v průběhu výpočtu nikdy horší řešení, než jaké již máme, proto je simplexová metoda nazývána efektivním algoritmem. Pokud ani toto nově vzniklé řešení není optimální, pokračujeme další iterací. Při řešení můžeme dojít ke dvěma závěrům. Optimální řešení úlohy buď existuje, nebo neexistuje. Pokud bylo pomocí simplexové metody nalezeno optimální řešení, je nutné otestovat, jestli se v úloze nachází pouze jediné optimální řešení, nebo jestli existuje tzv. alternativní optimální řešení. Úloha LP má buď jedno optimální řešení, nebo má nekonečně mnoho optimálních řešení. Na obrázku č. 8. vyobrazuji grafické znázornění, všech možností řešení.

1

2 3

Optimální řešení = přípustné řešení s nejlepší hodnotou účelové funkce. Základní řešení úlohy = takové přípustné řešení, které má maximálně tolik nenulových složek, kolik je lineárně nezávislých omezení. Přípustné řešení = vyhovuje všem omezujícím podmínkám úlohy (vlastním omezením a podmínkám nezápornosti).

37

Jediné optimální řešení

Alternativní optimální řešení

Úloha nemá optimální řešení

Úloha nemá přípustné řešení

Obrázek 8 - Možnosti řešení [1, str. 31]

Pro lepší představivost jsem princip simplexové metody zakreslila do schématu algoritmu na obrázku č. 9. Začátek Nalezení výchozího ZPŘ úlohy LP Ne Existuje? Úloha LP nemá přípustné řešení

Ano Ano

Je to optimální řešení?

Je to jediné optimální řešení?

Ne

Ne

Úloha LP má nekonečně mnoho optimálních řešení

Nalezení nového ZŘ úlohy LP s lepší hodnotou účelové funkce

Ano

Úloha LP má jediné optimálních řešení

Popis množiny optimálních řešení Ne Existuje? Ano

Úloha LP nemá optimální řešení Obrázek 9 – Schéma algoritmu [1, str. 32]

38

Konec

Pro řešení problému simplexovou metodou je využíván obecný tvar matematického modelu úlohy LP (podle [2, str. 34]). účelová funkce: z  c1 x1  c2 x2  ...  cn xn  MIN (MAX ), soustava vlastních omezení: a11x1  a12 x2  ...  a1n xn  b1 , a21x1  a22 x2  ...  a2 n xn  b2 , …. am1 x1  am 2 x2  ...  amn xn  bm , podmínky nezápornosti: j = 1, 2, …, n, xj  0 bi  0

kde

i = 1, 2, …, n,

n – počet strukturních proměnných modelu, m – počet vlastních omezení modelu, c j – cenový koeficient, který přísluší j-té proměnné,

bi – hodnota pravé strany, která přísluší i-tému vlastnímu omezení, aij – strukturní koeficient, který vyjadřuje vztah mezi i-tým omezením a j-tou

proměnnou. Jednofázová simplexová metoda Jednofázovou simplexovou metodu můžeme aplikovat pouze v případě, když jsou vlastní omezení ve tvaru nerovnic typu „≤“. Abychom tuto soustavu nerovnic převedli na ekvivalentní soustavu rovnic, musíme ke každé nerovnici přičíst přídatnou proměnnou. Omezení modelu musíme převést na tvar, kdy matice strukturních koeficientů obsahuje jednotkovou submatici koeficientů. Takto vzniklý tvar se nazývá kanonický. „Položíme-li všechny strukturní proměnné rovny nule, je přídatná proměnná rovna pravé straně svého omezení.“ (Citace z [7, přednáška č. 3, str. 14]) Pro zjednodušení budu v eliminačních vzorcích uvažovat matici transformovaných strukturních koeficientů A   i j , sloupec transformovaných pravých stran b   i 

 

a transformovaný řádek účelové funkce s koeficienty z j (podle [5, str. 100]). Algoritmus pro maximalizační úlohu (podle [5, str. 100-101]) 1. Test optima a určení vstupující proměnné Máme-li maximalizační úlohu, najdeme nejmenší koeficient zj v řádce účelové funkce g  min j ( z j )  z k

j = 1, 2, …, m+n,

Pokud je koeficient g nezáporný, hodnotu účelové funkce již není možné zvýšit, našli jsme optimální řešení a výpočet končí. Pokud je však koeficient záporný, hodnotu účelové 39

funkce je ještě možné zlepšit a proměnná se záporným koeficientem je vstupující proměnná a sloupec, ve kterém se proměnná nachází, je klíčový sloupec. 2. Určení vystupující proměnné Vypočteme

i , >0  ik

t  min  ik

kde

 i – pravá strana,  i j – kladné koeficienty klíčového sloupce.

Nejmenší z těchto vypočtených podílů určuje vystupující proměnnou a řádek, ve kterém se tato proměnná nachází, se nazývá klíčový řádek. Pokud by byly koeficienty v klíčovém sloupci nekladné, úlohy by měla neomezenou hodnotu účelové funkce. Optimální řešení by v takovém případě neexistovalo a výpočet by mohl skončit. 3. Transformace řešení  Matice A: Klíčový prvek

je prvek, který leží jak v klíčovém sloupci, tak v klíčovém řádku.

Tímto prvkem musíme vydělit celý klíčový řádek.

 i j 

 qj , j = 1, 2, ..., n + m.  qk

Transformace ostatních prvků potom vypadá takto:

 ij   ij   ik   qj , i =1, 2, ..., m, i≠q, j = 1, 2, ..., n+m.  Vektor b: Transformace pravé strany klíčového řádku se provádí obdobně jako transformace matice v klíčovém řádku:

 q 

q .  qk

Ostatní pravé strany se transformují takto:

 i    i   q   ik , i =1, 2, ..., m, i≠q, kde q – index klíčového řádku  Řádek z: Transformaci koeficientů účelové funkce přepočteme podle z j  z j  z k  aqj , kde k – index klíčového sloupce; j = 1, 2, ..., n+m. 40

Nová hodnota účelové funkce je ' z'  z  zk  q

Dvoufázová simplexová metoda Dvoufázovou simplexovou metodu použijeme, když má úloha LP některá omezení ve tvaru nerovnic typu „ “ nebo ve tvaru rovnic. Po vyrovnání soustavy vlastních omezení na rovnice není soustava v kanonickém tvaru. Matice strukturních koeficientů neobsahuje jednotkovou submatici koeficientů. Abychom získali výchozí řešení, musíme použít další proměnné, které se nazývají pomocné y i (i = 1, 2, …m), které přičteme tam, kde není proměnná s jednotkovým vektorem. Nerovnici typu „ “ převedeme na rovnici tak, že na levé straně rovnice odečteme přídatnou proměnnou a přičteme pomocnou proměnnou. Pokud máme omezení ve tvaru rovnosti, přičteme k levé straně rovnice pomocnou proměnnou. Soustava rovnic, která obsahuje pomocnou proměnnou, se nazývá rozšířená soustava rovnic. „Rozšířená soustava omezení je ekvivalentní původní soustavě, jestliže jsou všechny pomocné proměnné rovny nule.“ (Citace z [5, str. 110]) Abychom zajistili vynulování pomocných proměnných, můžeme buď zavést prohibitivní ceny4 nebo sestavit pomocnou účelovou funkci, ve které minimalizujeme součet pomocných proměnných. Pokud je však prohibitivní cena špatně zvolena, mohou být výsledky zkreslující, proto se tomuto způsobu systémy sloužící k řešení úloh LP vyhýbají a častěji se sestavuje pomocná účelová funkce

z  y1  y 2  ...  yp  min , kde p – počet pomocných proměnných v úloze LP. Pomocná účelová funkce musí být převedena do anulovaného tvaru

z  y1  y 2  ...  yp  0 a eliminací se převede na tvar, kdy se u pomocných proměnných vyskytují nulové koeficienty. Výpočet má dvě fáze. V první fázi hledáme přípustné řešení původní úlohy a minimalizujeme pomocnou účelovou funkci z  . Když jsou všechny pomocné proměnné rovny nule, pomocnou účelovou funkci můžeme vynechat. Ve druhé fázi potom minimalizujeme nebo maximalizujeme (dle zadání) původní účelovou funkci z a tím získáme optimální řešení původní úlohy. Pokud se nám ale nepovede všechny pomocné proměnné vynulovat, můžeme sice získat optimální řešení rozšířené úlohy, ale nejedná se o přípustné řešení zadané úlohy. Neexistuje tedy ani přípustné ani optimální řešení původní úlohy a výpočet končí v první fázi.

4

Prohibitivní ceny: pomocným proměnným jsou přiřazeny řádově velmi odlišné ceny např. u maximalizace je cena záporná) a 100 000 (u minimalizace je naopak cena kladná).

41

Příloha č. 7: Gomoryho metoda Jak jsem již zmiňovala, Gomoryho metoda se řadí do skupiny metod řezných nadrovin. Nejdříve je vypočteno optimální řešení úlohy lineárního programování pomocí simplexové metody bez podmínek celočíselnosti. Pokud by toto řešení splňovalo podmínky celočíselnosti, můžeme výpočet ukončit a vzniklé řešení je i optimálním řešením úlohy LP. Pokud však podmínky celočíselnosti nejsou splněny, je nutné k soustavě omezujících podmínek doplnit nové omezení, které musí mít tyto vlastnosti:  

pro optimální řešení bez podmínek celočíselnosti není splněna, pro libovolné přípustné řešení původního celočíselného problému je splněna.

Přidání tohoto omezení odpovídá geometricky zavedení nadroviny, která od množiny přípustných řešení spojitého problému „odřízne“ optimální neceločíselné řešení, přičemž nedojde ke ztrátě žádného přípustného řešení celočíselného problému. Postup se opakuje tak, že doplněný spojitý problém se opět řeší a splňuje-li získané řešení podmínky celočíselnosti, je řešení optimální a výpočet končí, pokud ale podmínky celočíselnosti nejsou splněny, přidá se další omezení a takto se proces opakuje, dokud nenalezneme optimální celočíselné řešení úlohy (podle [9, str. 12]). Při využití Gomoryho metody se soustava v každém kroku rozšiřuje o další nové omezení a novou proměnnou. Omezení představuje řádek simplexové tabulky a proměnná sloupec. Jelikož může být počet kroků velký, úloha se tím velmi rozroste a vypočítat takto rozměrnou úlohu může činit značný problém. Po získání optimálního řešení úlohy pomocí simplexové metody bez podmínek celočíselnosti budeme předpokládat, že proměnná, která je neceločíselná se nachází v i-tém řádku simplexové tabulky a má největší zbytek, to je řádek, který vybereme. Sestrojíme nové omezení (Gomoryho omezení) ve tvaru (podle [6, str. 247]): n

 (r )  x j 1

ij

ij

 xn1  ri 0 ,

kde

rij – celočíselné zbytky strukturních proměnných i-tého řádku simplexové tabulky, xn  1 – přídatná proměnná, kterou jsme doplnili k tomuto novému omezení, ri 0 – celočíselný zbytek hodnoty pravé strany i-tého řádku tabulky (hodnoty základní proměnné, která nesplňuje podmínku celočíselnosti). Po přidání nového omezení do simplexové tabulky je získáno primárně nepřípustné řešení. Dále se proto spočte nové optimální řešení upravené úlohy. Výpočet se provádí pomocí duálně simplexové metody. Jako klíčový řádek v simplexové tabulce je označeno právě toto nově přidané Gomoryho omezení. Po transformaci tabulky musí být opět otestováno, zda optimální řešení splňuje podmínky celočíselnosti. Pokud jsou podmínky celočíselnosti splněny, výpočet končí. Pokud 42

splněny nejsou, tak k soustavě doplníme další Gomoryho omezení a pokračujeme opět stejným způsobem, dokud nenalezneme optimální řešení. Nevýhodou této metody je, že koeficienty Gomoryho omezení jsou zvláště v dalších iteracích velmi malá čísla blízká nule. Při eliminaci proto mohou vzniknout zaokrouhlovací chyby, které mohou způsobit to, že výpočet nerozezná optimální řešení a výpočet zkrachuje. Proto programové systémy používají většinou kombinatorické metody. Další nevýhodou je již výše zmíněná rozměrnost úlohy způsobená přidáváním nových omezení (řádků a sloupců simplexové tabulky), což se však děje i u metody větví a mezí, kde s každým omezením přibude přídatná proměnná a někdy i pomocná proměnná.

43