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

17.4.1

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

Doc. Ing. Alois Fiala, CSc.

 NahoruÚ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.

 NahoruSortimentní 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.

Pokud bychom celkový zisk vyjádřili v Kč, pak by účelová funkce měla tvar z = 4000 x₁ + 6000 x₂ (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 x₁ + 30 x₂ ≤ 2100). Druhé omezení se týká kapacity zařízení M. Jestliže kapacita zařízení je 100 %, pak 10 ks výrobku V₁ spotřebuje 1/100 této kapacity a 10 ks výrobku V₂ spotřebuje 1/50 této kapacity (zařízení je schopno vyrobit buď 1000 ks V₁, nebo 500 ks výrobku V₂). 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 x_1,opt = 40, x_2,opt = 30 a optimální hodnota účelové funkce z_opt = 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 V₁ a 300 ks výrobku V₂ ; 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 V₁ a 100 ks výrobku V₂.

 NahoruSměš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 L₁, L₂, L₃ a L₄ : ve výsledné směsi musí být právě b₁ % látky L₁, nejméně d₂ % a nejvýše h₂ % látky L₂, alespoň d₃ % látky L₃ a nejvýše h₄ % látky L₄. Zaveďme dále tato označení:

n... počet komponent,

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

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

x_j... 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 L_i 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ě b_i % látky L_i, 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:

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

Veličiny a_ij, b_i, d_i, h_i se nahradí veličinami a'_ij = a_ij / 100, b'_i = wb_i / 100, d'_i = wd_i / 100, h'_i = wh_i / 100 a podmínka (7) se nahradí podmínkou:

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

 NahoruŘ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 d_i (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í:

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