dnes je 3.12.2024

Input:

Typické úlohy lineárního programování

13.10.2008, , Zdroj: Verlag Dashöfer

17.4.1
Typické úlohy lineárního programování

Doc. Ing. Alois Fiala, CSc.

Úlohy LP

Úlohy lineárního programování (LP) se vyznačují tím, že účelová funkce i všechny omezující podmínky jsou lineární. Lineární programování patří k nejstarším a nejpropracovanějším částem operačního výzkumu. K jeho významu přispívá i to, že v řadě jiných typů úloh operačního výzkumu se při řešení různým způsobem využívá metod lineárního programování.

Strukturu úlohy LP můžeme popsat následujícími vztahy (složené závorky znamenají, že nastává pouze jedna z možností v nich uvedených):

Účelová funkce se tedy může maximalizovat nebo minimalizovat, omezující podmínky mohou mít tvar rovnic nebo nerovnic typů ˜ či ˛ a některé proměnné mohou být nekladné nebo nezáporné.

Mezi typické úlohy LP patří sortimentní problémy (úlohy optimalizace výrobního plánu), směšovací problémy, řezné problémy a dopravní a distribuční problémy.

Sortimentní problém

Obecná formulace sortimentního problému (problému optimalizace plánu výroby) a jeho modifikací je uvedeno v tomto díle. Následující příklad obsahuje jednoduchou ukázku kvantifikované verze tohoto problému.

Příklad 1

Podnik vyrábí dva druhy výrobků V1 a V2, přičemž limitujícími výrobními zdroji jsou surovina S a výrobní zařízení M. V daném období je surovina S k dispozici v množství 2100 kg, přičemž se spotřebují 3 kg suroviny na výrobu 1 ks výrobku V1 a 3 kg suroviny na výrobu 1 ks výrobku V2. Zařízení M je v daném období schopno vyrobit buď 1000 ks výrobku V1 (kdyby nevyrábělo už nic jiného) nebo 500 ks výrobku V2. V daném období je zajištěn odbyt 600 ks výrobku V1 a 400 ks výrobku V2. Výrobky se dodávají v celcích po 10 kusech. Zisk za kus je u výrobku V1 400 Kč a u výrobku V2 600 Kč. Je třeba určit, kolik kterých výrobků má podnik v daném období vyrábět, aby dosáhl maximálního zisku.

Veličiny modelu (jde o rozhodovací proměnné a výsledkovou proměnnou; 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 ... celkový zisk (1000 Kč).

Volba jednotek u rozhodovacích proměnných vyplývá ze zadání (výrobky se prodávají v celcích po 10 ks), kdežto volba jednotky u výsledkové proměnné je vedena snahou o zjednodušení modelu.

Matematický model:

                       
z = 4 x1 + 6 x2 max
3 x1 + 3 x2 210 (10 kg)
x1 + 2 x2 100 (%)
x1 60 (10 ks)
x2 40 (10 ks)
x1 , x2 0
x1 , x2 ε Z

Pokud bychom celkový zisk vyjádřili v Kč, pak by účelová funkce měla tvar z = 4000 x1 + 6000 x2 (zisk za 1 ks je 400, resp. 600 Kč, a tedy za 10 ks je to 4000, resp. 6000 Kč). Prvá podmínka zohledňuje omezenou zásobu suroviny S. Zde jsme změnili jednotku množství suroviny z 1 kg na 10 kg (jinak by omezení mělo tvar 30 x1 + 30 x2 ≤ 2100). Druhé omezení se týká kapacity zařízení M. Jestliže kapacita zařízení je 100 %, pak 10 ks výrobku V1 spotřebuje 1/100 této kapacity a 10 ks výrobku V2 spotřebuje 1/50 této kapacity (zařízení je schopno vyrobit buď 1000 ks V1, nebo 500 ks výrobku V2). Další dvě podmínky zohledňují odbytová omezení. Poslední dvě podmínky předepisují nezápornost (nemůžeme vyrábět záporná množství výrobků) a celočíselnost (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. Velmi často se však takové úlohy převedou na úlohy normálního lineárního programování zanedbáním podmínek celočíselnosti. Pokud jsou složky optimálního řešení takto upravené úlohy neceločíselné, provede se jejich úprava na nejbližší celočíselné hodnoty tak, aby byly dodrženy všechny omezující podmínky.

Vytvořený model je možno po zanedbání podmínek celočíselnosti řešit graficky nebo pomocí jednofázové 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 = 340. 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í. Odpověď na zadaný úkol je tedy následující: 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. Prvá dvě omezení jsou splněna jako rovnice, což znamená, že kapacity výrobních zdrojů jsou plně využity. Nevyužité zůstávají možnosti odbytu - na trhu by bylo možno ještě uplatnit 200 ks výrobku V1 a 100 ks výrobku V2.

Směšovací problém

Směšovací problém lze obecně charakterizovat tak, že z daných komponent se má co nejlevněji vytvořit směs požadovaných vlastností. Pro jednoduchost zde předpokládejme, že požadované vlastnosti se týkají obsahu 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. Zaveďme dále tato označení:

n... počet komponent,

aij... procento i -té látky v jednotce j -té komponenty,

cj... cena jednotky j -té komponenty,

xj... podíl j -té komponenty v jednotce výsledné směsi,

z... cena jednotky výsledné směsi,

Matematický model:

(1)
(2)
(3)
(4)
(5)
(6)
(7)
xj ≥ 0, j = 1, 2, ..., n. (8)

Podmínky (2) - (6) zajišťují splnění požadavků na obsah látek Li ve výsledné směsi. Neřiditelné veličiny v těchto omezeních jsou vyjádřeny v procentech. Pokud bychom je chtěli převést do jednotek, v nichž měříme množství komponent ve výsledné směsi, museli bychom je podělit stem. Podmínka (7) je nutná k tomu, abychom jako součet podílů komponent v jednotce směsi dostali celou jednotku. Kdyby se však komponenty skládaly pouze z uvedených čtyř látek (tedy by neobsahovaly žádnou jinou látku) a bylo by pro každou látku požadováno, že směs musí obsahovat právě bi % látky Li, pak by podmínka (7) byla zbytečná a omezení (2) - (6) by byla nahrazena podmínkami

Směšovací problém může být modifikován také tak, že se má vyrobit co nejlevněji právě w jednotek výsledné směsi. Specifikaci proměnných a matematický model je pak třeba upravit takto:

xj... množství j-té komponenty ve výsledné směsi,
z... celková cena výsledné směsi.

Veličiny aij, bi, di, hi se nahradí veličinami a'ij = aij / 100, b'i = wbi / 100, d'i = wdi / 100, h'i = whi / 100 a podmínka (7) se nahradí podmínkou:

Příklad 2

Při výrobě směsi S se používají tři komponenty K1, K2, K3 . Jakost výsledné směsi je určena přípustným množstvím prvků P1 a P2 : obsah prvku P1 se musí pohybovat v rozmezí 4 % až 4,5 % a obsah prvku P2 může být nejvýše 2 %. Obsah prvků P1 a P2 v jednotlivých komponentách a ceny komponent udává následující tabulka:

   
Obsah prvku v %
K1 K2 K3
P1 5 2,5 6
P2 1 2 4
Cena (Kč/kg) 15 10 25

Komponenty jsou v plánovaném období k dispozici v omezeném množství: 400 kg K1, 500 kg K2 a 300 kg K3. Je zapotřebí vyrobit 1000 kg směsi tak, aby celkové náklady na spotřebované komponenty byly minimální.

Veličiny modelu:

xj... množství komponenty Kj ve výsledné směsi (kg),
z ... celková cena spotřebovaných komponent (Kč).

Matematický model:

                                                   
z = 15 x1 + 10 x2 + 25 x3 min
0,05 x1 + 0,025 x2 + 0,06 x3 40 (kg)
0,05 x1 + 0,025 x2 + 0,06 x3 45 (kg)
0,01 x1 + 0,02 x2 + 0,04 x3 20 (kg)
x1 + x2 + x3 = 1000 (kg)
x1 400 (kg)
x2 500 (kg)
x3 300
x1, x2, x3 0

Optimálním řešením je vektor xopt = (400; 457,14; 142,86)T a optimální hodnota účelové funkce zopt = 14142,9. K výrobě 1000 kg směsi se tedy použije 400 kg komponenty K1, 457,14 kg komponenty K2 a 142,86 kg komponenty K3. Celková cena spotřebovaných komponent bude 14 142,90 Kč.

Řezný problém

Z výchozích tyčí dané délky d je třeba optimálním způsobem nařezat požadované počty přířezů o délkách di (i = 1, ..., m). Každou výchozí tyč je možno rozřezat konečně mnoha způsoby, které nazýváme řeznými plány. Počet těchto řezných plánů je obvykle velmi vysoký, a proto se většinou omezujeme pouze na tzv. přípustné řezné plány. Nejjednodušší podmínkou přípustnosti řezného plánu je požadavek, že odpad vzniklý rozřezáním jedné tyče nesmí být delší, než je nejkratší z délek požadovaných přířezů. Předpokládejme, že existuje n přípustných řezných plánů. Zaveďme následující označení:

aij... počet přířezů i-tého druhu získaných rozřezáním výchozí tyče podle j-tého řezného plánu,
bi... požadovaný počet přířezů i-tého druhu,
cj... délka odpadu vzniklého rozřezáním 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.

Účelová funkce pro tento problém může být zkonstruována dvěma způsoby:

  1. Chceme minimalizovat celkové množství odpadu

    (1)
  2. Chceme minimalizovat celkový počet rozřezaných výchozích tyčí

    (2)

Omezující podmínky:

i = 1, 2, ..., m, (3)
xj ≥ 0, xj ε Z, j = 1, 2, ..., n, (4)

kde Z označuje množinu celých čísel. Může se stát, že úloha 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 ≥. Při této úpravě však není vhodné použít účelovou funkci (1), protože při snaze minimalizovat odpad by to mohlo vést ke zbytečnému nárůstu počtu některých přířezů.

Řezný problém patří také do kategorie úloh celočíselného LP, ale obvykle se řeší po zanedbání podmínek celočíselnosti jako úloha normálního LP.

Příklad 3

Strojírenský závod potřebuje ke své výrobě 3 druhy kovových tyčí T1, T2, T3, přičemž tyče T1 mají délku 80 cm, tyče T2 mají délku 70 cm a tyče T3

Nahrávám...
Nahrávám...