Minimalizace Odpadu pomocí Lineárního Programování

Lineární programování (LP) patří k nejstarším a nejpropracovanějším částem operačního výzkumu. Různým způsobem využívá metod lineárního programování. V LP jsou účelová funkce i všechny omezující podmínky lineární. Proměnné mohou být nekladné nebo nezáporné.

Úvod do Lineárního Programování

Přípustným řešením (pro n-rozměrnou úlohu LP) je každá n-tice [ x1 , x2 , x3 , ... čísel, která vyhovuje všem podmínkám zadané soustavy. V příkladu bude platit: přípustné řešení - řešení x1 = 0 , x2 = 0 - tj. dvojice [ 0 , 0 ], která po dosazení do obou podmínek jejich nerovnostem vyhovuje - nebo řešení [ 10 , 20 ] , [ 300 , 0 ] - atd.

Nepřípustným řešením (pro n-rozměrnou úlohu LP) je každá n-tice [ x1 , x2 , x3 , ... čísel, která nevyhovuje alespoň jedné podmínce zadané soustavy. Například, nepřípustné řešení - řešení [ -5 , 0 ] ... nevyhovuje podmínce nezápornosti čísel - řešení [ 200 , 150 ] ...nevyhovuje oběma nerovnostem v zadání. Optimální řešení [ 210 , 120 ] ... vyhovuje všem podmínkám a dává nejlepší hodnotu účelové funkce z požadovaného extrému.

Účelová Funkce

Účelové funkce mají tvar: z(x1 , x2) = c1 * x1 + c2 * x2. Jedná se o trojrozměrnou funkci (x1 , x2 , z), která představuje rovinu ve trojrozměrném prostoru. Řezem této funkce rovinou z(x1 , x2) = konst. získáme průmět účelové funkce do roviny (x1 , x2) = konst.

Typické Úlohy Lineárního Programování

Problém optimalizace (např. výroby) a jeho modifikací je uveden v tomto díle. Dále si uvedeme jednoduchou ukázku kvantifikované verze tohoto problému.

Čtěte také: Jak minimalizovat odpad?

Předpokládejme, že podnik vyrábí dva výrobky: V1 a V2, přičemž limitujícími výrobními zdroji jsou surovina S a výrobní zařízení M. Na výrobu 1 ks výrobku V1 je třeba 3 kg suroviny S a 0,02 hodiny kapacity zařízení M, na výrobu 1 ks výrobku V2 je třeba 3 kg suroviny S a 0,05 hodiny kapacity zařízení M. Podnik má k dispozici 2100 kg suroviny S a 100 hodin kapacity zařízení M. Dále je známo, že odběratel odebere maximálně 500 ks výrobku V1 a 400 ks výrobku V2. Zisk z 1 ks výrobku V1 je 400 Kč a z 1 ks výrobku V2 600 Kč. Určete, kolik kusů výrobků V1 a V2 má podnik v daném období vyrábět, aby dosáhl maximálního zisku.

Matematický model (rozhodovací proměnnou je objem výroby; neřiditelné veličiny jsou zadány v předchozím textu): x 1 ... množství výrobku V1 (10 ks),x 2 ... množství výrobku V2 (10 ks), z ... zisk (Kč). Zavedení proměnné jako množství výrobků po 10 kusech je vedena snahou o zjednodušení modelu. Účelová funkce má tvar z = 4000 x1 + 6000 x2 (zisk z 1 ks je 400, resp. 600 Kč, a tedy za 10 ks je to 4000, resp. 6000 Kč).

Omezující podmínky:

• 30 x1 + 30 x2 ≤ 2100 ... podmínka zohledňuje omezenou zásobu suroviny S. Zde je nutné upozornit, že jsme změnili jednotku množství suroviny z 1 kg na 10 kg (jinak by omezení mělo tvar 30 x1 + 30 x2 ≤ 2100).
• 0,2 x1 + 0,5 x2 ≤ 100 ... podmínka zohledňuje omezenou kapacitu zařízení M.
• x1 ≤ 50 ... další dvě podmínky zohledňují odbytová omezení.
• x2 ≤ 40
• x1, x2 ≥ 0 ... podmínky nezápornosti
• x1, x2 celočíselné ... podmínka celočíselnosti (vyrábět můžeme pouze v celcích po 10 ks).

Podmínka celočíselnosti znamená, že jde o problém celočíselného LP. Pokud bychom zanedbali podmínky celočíselnosti, jedná se o úlohu LP.

Řešením úlohy LP je nalezení takových hodnot proměnných x1 a x2, tak, aby byly dodrženy všechny omezující podmínky a zároveň bylo dosaženo maximální hodnoty účelové funkce. Úlohu je možné řešit graficky nebo pomocí jednofázové simplexové metody.

Čtěte také: Operační Výzkum v Minimalizaci Odpadu

Výsledkem řešení jsou optimální hodnoty rozhodovacích proměnných x1,opt = 40, x2,opt = 30 a optimální hodnota účelové funkce zopt = 340. Interpretace výsledků odpovídajících zadání: Podnik má týdně vyrábět 400 ks výrobku V1 a 300 ks výrobku V2 ; přitom bude dosahovat zisku 340 000 Kč. Dosazením vypočtených hodnot do modelu můžeme získat další užitečné informace. Například, surovina S i kapacita výrobního zařízení M jsou plně využity. Dále je zřejmé, že podnik může ještě uplatnit 200 ks výrobku V1 a 100 ks výrobku V2.

Minimalizace Nákladů na Míchání

Další typickou úlohou LP je problém, jak z daných komponent se má co nejlevněji vytvořit směs požadovaných vlastností. Předpokládejme, že máme vytvořit směs pouze čtyř látek L1, L2, L3 a L4 : ve výsledné směsi musí být právě b1 % látky L1, nejméně d2 % a nejvýše h2 % látky L2, alespoň d3 % látky L3 a nejvýše h4 % látky L4.

Označení: n... počet komponent, aij... procento i -té látky v jednotce j -té komponenty, cj... cena jednotky j -té komponenty, xj... množství j -té komponenty v jednotce výsledné směsi, z... cena jednotky výsledné směsi.

Matematický model:

• Účelová funkce: z = c1x1 + c2x2 + ... + cnxn → min

Omezující podmínky:

Čtěte také: Tlaková Myčka 14mm pro Odpady

• a11x1 + a12x2 + ... + a1nxn = b1 (2)
• d2 ≤ a21x1 + a22x2 + ... + a2nxn ≤ h2 (3)
• d3 ≤ a31x1 + a32x2 + ... + a3nxn (4)
• a41x1 + a42x2 + ... + a4nxn ≤ h4 (5)
• x1 + x2 + ... + xn = 1 (6)
• x1, x2, ..., xn ≥ 0 (7)

Podmínky (2) - (6) zajišťují splnění požadavků na obsah látek Li ve výsledné směsi. Vzhledem k tomu, že požadavky na obsah látek Li jsou vyjádřeny v procentech, rovnice (6) zajišťuje, že součtem množství jednotlivých komponent v jednotce směsi dostali celou jednotku. Pokud bychom chtěli zjistit, jak nejlevněji vyrobit právě w jednotek výsledné směsi, matematický model je pak třeba upravit takto: xj... množství j -té komponenty ve w jednotkách směsi, z... celková cena výsledné směsi.

Příklad

Máme tři komponenty K1, K2, K3 . Komponenta K1 musí tvořit nejméně 30 % výsledné směsi, komponenta K2 nejméně 20 % a komponenta K3 nejméně 15 % výsledné směsi. Komponenta K1 může obsahovat nejvýše 1 % příměsí, komponenta K2 nejvýše 1,5 % příměsí a komponenta K3 nejvýše 2 %. Celkový obsah příměsí ve směsi smí být nejvýše 2 %. Cena za 1 kg komponenty je následující: K1 - 20 Kč, K2 - 25 Kč a K3 - 30 Kč. Celkem je k dispozici následující množství: 400 kg K1, 500 kg K2 a 300 kg K3. Určete, jaké množství jednotlivých komponent je třeba použít, aby cena výsledné směsi byla minimální.

Veličiny modelu: xj... množství j-té komponenty ve výsledné směsi (kg),z ... celková cena spotřebovaných komponent (Kč).

Výsledkem je, že optimální je použít 400 kg komponenty K1, 500 kg komponenty K2 a 14142,9 kg komponenty K3. Minimální cena za 1 kg výsledné směsi je 2142,90 Kč. Celková cena za 100 kg výsledné směsi je 142,90 Kč.

Úloha o Optimálním Dělení Materiálu (Řezné Plány)

V praxi se často setkáváme s úlohami, kdy je třeba rozřezat určité výchozí materiály (např. tyče, desky, role papíru apod.) na polotovary (tzv. přířezy) požadovaných rozměrů. Cílem je minimalizovat odpad vzniklý při dělení materiálu. Každý způsob rozřezání výchozího materiálu na přířezy, které nazýváme řeznými plány. Počet všech možných řezných plánů bývá velmi vysoký, a proto se většinou omezujeme pouze na tzv. významné řezné plány. Úlohou je určit optimální kombinaci řezných plánů tak, aby byl minimalizován odpad a zároveň bylo vyrobeno požadované množství přířezů.

Zaveďme následující označení: aij... počet přířezů i-tého druhu vyrobených z jedné tyče podle j-tého řezného plánu, bi... požadované množství přířezů i-tého druhu, cj... odpad vzniklý rozřezáním jedné výchozí tyče podle j-tého řezného plánu, xj... počet výchozích tyčí rozřezaných podle j-tého řezného plánu.

Matematický model:

• Účelová funkce: z = c1x1 + c2x2 + ... + cnxn → min (1) (minimalizace celkového odpadu vzniklého rozřezáním tyčí)

Omezující podmínky:

• a11x1 + a12x2 + ... + a1nxn = b1 (2)
• am1x1 + am2x2 + ... + amnxn = bm (3) (počet vyrobených přířezů i-tého druhu se musí rovnat požadovanému počtu přířezů)
• x1, x2, ..., xn ≥ 0 (4)
• xj celé číslo (j = 1, 2, ..., n), kde Z označuje množinu celých čísel. (5)

Je třeba si uvědomit, že model s takto formulovanými omezujícími podmínkami nebude mít žádné přípustné řešení. V takovém případě je třeba rovnice (3) nahradit nerovnicemi typu ≥. Minimalizovat se pak nebude odpad, ale počet použitých výchozích tyčí. Popsaný model je modelem celočíselného LP.

Příklad z Diplomové Práce

Diplomová práce Ing. Darii Chernykh se zabývá optimalizací procesu nákupu a dělení hutního materiálu s použitím řešení úlohy o optimálním dělení materiálu, jednou z úloh lineárního programování. Cílem při řešení této úlohy je minimalizace odpadu a minimalizace nákladů na nákup výchozího materiálu. Návrh řešení je určen pro podmínky společnosti KULIČKOVÉ ŠROUBY KUŘIM,a.s. Základem práce je cyklus PDCA Edwardsa Deminga („plánuj-dělej-kontroluj-jednej“) jako základní způsob pro efektivní řešení a zlepšování výrobních aktivit, procesů a systému.

tags: #minimalizace #odpadu #lineární #programování

Oblíbené příspěvky:

• Cviky pro zdraví a energii
• Efektivní odpadkové řešení do kuchyně
• Vzor potvrzení o kontrole
• Živočišný protein z hmyzu
• Vítězslav Hálek – V přírodě