Příklady modelů lineárního programování Příklad 1 Optimalizace výroby konzerv. Podnik vyrábí nějaký výrobek, který prodává v 1 kg a 2 kg konzervách, přičemž se řídí podle následujících velmi zjednodušených předpokladů. Na výrobním zařízení, na kterém se z nakoupených plechů zhotovují plechovky, trvá výroba 100 plechovek bez rozdílu velikosti 1 hodinu. Zařízení může být v provozu nejvýše 70 hodin týdně. Týdně lze k plnění do plechovek připravit 10000 kg výrobku a při plnění nevzniká žádný odpad. Prodejní oddělení může týdně zabezpečit odbyt 6000 kg výrobku v 1 kg konzervách a 8000 kg ve 2 kg konzervách. Konzervy se prodávají v celcích po 100 kusech. Zisk za kus je u 1 kg konzervy 2 Kč a u 2 kg konzervy 3 Kč. Kolik a kterých konzerv má podnik týdně vyrábět, aby za těchto předpokladů dosáhl maximálního zisku? Specifikace veličin modelu: •
Neřiditelné veličiny jsou zadány v předchozím textu. Jak uvidíme dále, v průběhu tvorby modelu u některých z nich dojde ke změně jednotek.
•
Rozhodovací proměnné (v závorkách jsou jednotky): x1 … množství 1 kg konzerv (100 ks) x2 … množství 2 kg konzerv (100 ks)
•
Výsledková proměnná: z … celkový zisk (100 Kč)
Pozn.: Volba jednotek u rozhodovacích proměnných vyplývá ze zadání (konzervy se prodávají v celcích po 100 ks), kdežto volba jednotky u výsledkové proměnné je vedena snahou o zjednodušení modelu. Často vhodnou volbou jednotek můžeme zlepšit výpočetní vlastnosti modelu. Účelová funkce: Kritériem rozhodování je hodnota celkového zisku a účelová funkce vyjadřuje závislost této veličiny na rozhodovacích proměnných. z = 2 x1 + 3 x2 Pozn.: Zde došlo ke změně jednotky neřiditelných veličin, jimiž jsou zisky za jednotku výrobku. Novou jednotkou hodnot 2 a 3 je 100 Kč /100 ks. Výrobní omezení: •
Omezení výroby plechovek (závorkách je jednotka): x1 + x2 ≤ 70 (hod) Výraz na levé straně představuje spotřebu kapacity zařízení na výrobu plechovek pro plán výroby konzerv určený hodnotami x1 a x2. Koeficienty 1 na levé straně mají jednotku hod /100 ks.
-1-
•
Omezení přípravy výrobku: 100 x1 + 200 x2 ≤ 10000 (kg) Na 100 ks 1 kg konzerv se spotřebuje 100 kg výrobku a na 100 ks 2 kg konzerv se spotřebuje 200 kg výrobku. Omezení můžeme zjednodušit volbou jednotky 100 kg pro kapacitu linky na přípravu výrobku. x1 + 2 x2 ≤ 100 (100 kg) Jednotkou koeficientů 1 a 2 je 100 kg / 100 ks.
Omezení rozhodovacích proměnných: •
Odbytová omezení: x1 ≤ 60 (100 ks) x2 ≤ 40 (100 ks) Zde došlo ke změně jednotky možností odbytu z kg na 100 ks.
•
Podmínky nezápornosti: x1 ≥ 0 x2 ≥ 0 Nemůžeme vyrábět záporná množství konzerv.
•
Podmínky celočíselnosti (Z označuje množinu celých čísel): x1 ∈ Z x2 ∈ Z Vyrábět můžeme pouze v celcích po 100 ks.
Matematický model: maximalizovat z = 2 x1 + 3 x2 za podmínek x2 ≤
x1 +
70
x1 + 2 x2 ≤ 100 ≤
60
x2 ≤
40
x1 ,
x2 ≥
0
x1 ,
x2 ∈
Z
x1
-2-
Tento model je možno řešit graficky nebo pomocí simplexové metody. Řešením modelu jsou optimální hodnoty rozhodovacích proměnných x1,opt = 40, x2,opt = 30 a optimální hodnota účelové funkce zopt = 170 Při interpretaci získaného řešení musíme specifikovat, co tyto hodnoty znamenají, a převést je do jednotek odpovídajících zadání. V případě potřeby musíme také předtím provést úpravy související se zjednodušením modelu či postupu řešení (např. úpravu na celočíselné hodnoty). Odpověď na zadaný úkol je tedy následující: podnik má týdně vyrábět 4000 ks 1 kg konzerv a 3000 ks 2 kg konzerv; přitom bude dosahovat zisku 17000 Kč. Dosazením vypočtených hodnot do modelu můžeme získat další užitečné informace. Prvá dvě omezení jsou splněna jako rovnice, což znamená, že kapacity výrobních zařízení jsou plně využity. Nevyužité zůstávají možnosti odbytu – na trhu by bylo možno ještě uplatnit 2000 ks 1 kg konzerv a 1000 ks 2 kg konzerv.
-3-
Příklad 2 Optimalizace výrobního programu Podnik vyrábí dva typy zaměnitelných výrobků za těchto podmínek: •
slévárna může vyrobit odlitky nejvýše buď pro 80 ks typu I nebo pro 100 ks typu II.
•
lisovna může vyrobit výlisky nejvýše pro buď pro 200 ks typu I nebo pro 60 ks typu II.
•
montáž typu I má kapacitu 60 ks
•
montáž typu II má kapacitu 80 ks.
Cena obou typů za 1 ks je 28000 Kč. Je třeba stanovit výrobní program, který zajistí maximální hodnotu produkce. Veličiny modelu: x1 … množství výrobků typu I (ks) x2 … množství výrobků typu II (ks) z
… celková hodnota produkce (1000 Kč)
V zadání nejsou explicitně zadány spotřeby kapacit slévárny a lisovny na jednotky výrobků I a II, můžeme je ale odvodit následujícím způsobem. Jestliže slévárna má kapacitu 100 %, pak na 1 ks výrobku typu I je zapotřebí 5/4 % kapacity (100/80) a na 1 ks výrobku typu II je zapotřebí 1 % kapacity (100/100). Jestliže lisovna má kapacitu 100 %, pak na 1 ks výrobku typu I je zapotřebí 1/2 % kapacity (100/200) a na 1 ks výrobku typu II je zapotřebí 5/3 % kapacity (100/60). Matematický model: maximalizovat z = 28 x1 + 28 x2 za podmínek
5 x1 + 4
x2 ≤ 100 (%)
1 x1 + 2
5 x2 ≤ 100 (%) 3 ≤
60 (ks)
x2 ≤
80 (ks)
x1 x1 ,
x2 ≥
0
x1 ,
x2 ∈
Z
-4-
Příklad 3 Optimalizace nákupu surovin
Tři prvky P1, P2, P3 jsou obsaženy ve čtyřech různých sloučeninách S1, S2, S3, S4 . Obsahy prvků v jednotlivých sloučeninách, jakož i ceny sloučenin a potřebná množství prvků jsou uvedeny v tabulce. Ve sloupcích 2 – 5 je množství prvku v g, které lze získat z 1 kg sloučeniny. V posledním sloupci je minimálně potřebné množství prvků v kg. množství prvku v g z 1kg sloučeniny
Název prvku
minimálně potřebné množství v kg
S1
S2
S3
S4
P1
0
2
4
5
5
P2
2
2
0
4
6
P3
10
5
4
10
18
cena sloučeniny v Kč/kg
15
10
12
25
Má se zjistit, které sloučeniny a v jakém množství je třeba nakoupit, aby bylo získáno potřebné množství prvků za nejnižší cenu. Veličiny modelu: xj
… množství suroviny Sj (kg)
z
… celková cena surovin (Kč)
Matematický model: minimalizovat z = 15 x1 + 10 x2 + 12 x3 + 25 x4
za podmínek 2 x2 + 4 x3 +
5 x4 ≥
5000 (g)
+
4 x4 ≥
6000 (g)
2 x1 + 2 x2
10 x1 + 5 x2 + 4 x3 + 10 x4 ≥ 18000 (g) x1 , x2 , x3 ,
x4
≥
0
Při tvorbě modelu je nutno si dát pozor na to, že jednotky v zadání nejsou konzistentní. Množství prvků, které lze získat ze sloučenin, jsou v gramech, kdežto potřeba prvků je udána v kilogramech. Vhodnější v tomto případě bylo upravit jednotky požadovaných množství prvků.
-5-
Příklad 4 Nutriční problém (jedná se o zvláštní případ směšovacího problému)
Krmná směs musí obsahovat alespoň 60 jednotek látky L1, 160 jednotek látky L2 a 180 jednotek látky L3. Směs lze vyrábět ze dvou surovin S1 a S2, přičemž •
1 kg suroviny S1 obsahuje 3 jednotky látky L1, 4 jednotky látky L2 a 2 jednotky látky L3;
•
1 kg suroviny S2 obsahuje 1 jednotku látky L1, 3 jednotky látky L2 a 4 jednotky látky L3.
•
1 kg suroviny S1 stojí 14 Kč a
•
1 kg suroviny S2 stojí 13 Kč.
Je třeba určit množství surovin S1 a S2, jejichž smícháním dostaneme krmnou směs s požadovaným obsahem látek L1, L2 a L3 tak, aby celkové náklady na použité suroviny byly co nejnižší. Veličiny modelu: xj
… množství suroviny Sj (kg)
z
… celková cena surovin (Kč)
Matematický model: minimalizovat z = 14 x1 + 13 x2
za podmínek 3 x1 + 1 x2 ≥
60 (j)
4 x1 + 3 x2 ≥ 160 (j) 2 x1 + 4 x2 ≥ 180 (j) x1 ,
x2 ≥
-6-
0
Příklad 5 Řezný problém
Strojírenský závod potřebuje pro svoji výrobu 3 druhy kovových tyčí T1, T2, T3, přičemž tyče T1 mají délku 90 cm, tyče T2 mají délku 70 cm a tyče T3 mají délku 50 cm. K dispozici jsou pouze tyče délky 190 cm, které je třeba rozřezat. Přípustné jsou pouze takové způsoby řezání tyčí standardní délky, při kterých nebude odpad větší než 40 cm. Požaduje se 400 tyčí T1, 400 tyčí T2 a 1300 tyčí T3. Má se určit takový řezný plán, při kterém budou splněny požadavky při použití co nejmenšího počtu kusů tyčí standardní délky. Než začneme sestavovat model, musíme nejdříve zjistit všechny možné přípustné způsoby rozřezání tyče standardní délky na požadované tyče. Tyto způsoby, neboli tzv. řezné plány, jsou uvedeny v následující tabulce řezné plány P1
P2
P3
P4
P5
P6
potřebné množství v ks
T1 (90 cm)
2
1
1
0
0
0
400
T2 (70 cm)
0
1
0
2
1
0
400
T3 (50 cm)
0
0
2
1
2
3
1300
odpad v cm
10
30
0
0
20
40
Požadované tyče
Veličiny modelu: xj
… počet standardních tyčí rozřezaných podle j-tého řezného plánu (ks)
z
… celkový počet rozřezaných tyčí (ks)
Matematický model: minimalizovat z = x1 + x2 + x3 + x4 + x5 + x6
za podmínek 2 x1 + x2 + x3 x2
+ 2 x4 + + 2 x3 + x4
x5
+ 2 x5
=
400 (ks)
=
400 (ks)
+ 3 x6 = 1300 (ks)
x1 , x2 , ... ,
x6 ≥
0
x1 , x2 , ... ,
x6 ∈
Z
Poznamenejme, že v této úloze máme ještě jednu možnost volby kritéria: můžeme požadovat, aby celkový odpad byl minimální. Pak účelová funkce vypadá takto (jednotkou jsou centimetry): z = 10 x1 + 30 x2 + 20 x5 + 40 x6
-7-
Příklad 6 Dopravní problém
Závod na výrobu cementu zásobuje ze dvou skladů S1 a S2 tři stálé zákazníky Z1, Z2 a Z3. Tabulka udává měsíční zásoby cementu na skladech (v tunách), měsíční požadavky zákazníků (v tunách) a náklady na přepravu 1 tuny cementu z každého skladu ke každému zákazníkovi. Je třeba určit takový plán rozvozu cementu, při kterém nebudou překročeny kapacity skladů, budou uspokojeny požadavky zákazníků a přepravní náklady budou co nejnižší. zákazníci Z1
Z2
Z3
zásoby v tunách
S1
5
2
3
30
S2
2
1
1
75
požadavky 35 v tunách
25
45
Sklady
Veličiny modelu: xij … množství cementu dopravené z i-tého skladu j-tému zákazníkovi (t) z
… celkové náklady na přepravu
Matematický model: minimalizovat z = 5 x11 + 2 x12 + 3 x13 + 2 x21 + x22 + x23
za podmínek ≤ 30 (t)
x11 + x12 + x13 x21
+
x11
+
x22
+
= 35 (t)
x21
+
x12
= ´25 (t)
x22
+
x13
x23 ≤ 75 (t)
x23 = 45 (t)
x11 , x12 , x13 , x21 , x22 , x23 ≥
0
Prvá dvě omezení se týkají skladů a vyjadřují, že celkové množství dodané z určitého skladu nesmí být větší než jeho kapacita. Další tři omezení vyjadřují, že každý zákazník dostane přesně to množství, které požaduje. Vzhledem k tomu, že součet požadavků zákazníků je roven součtu kapacit skladů (oba mají hodnotu 105), můžeme i prvá dvě omezení zapsat jako rovnice. V takovém případě říkáme, že dopravní problém je vyvážený.
-8-
