Úvod do lineárního programování 1) Definice úlohy Jedná se o optimaliza ní problémy, které jsou popsány soustavou lineárních rovnic a nerovnic. Kritéria optimalizace jsou rovn ž lineární. Prom nné v této úloze nabývají reálných hodnot, které leží v ur itých mezích. Takové optimaliza ní úlohy nazýváme lineárním programováním. Úloha lineárního programování je definována jako min, max{c T x : A1 x ≤ b1 , A2 x ≥ b2 , A3 x = b3 , x ≥ 0}, kde f(x) = cT x je ú elová funkce (kritérium) ve tvaru f ( x ) = c1 x1 + c 2 x 2 + ....... + c n x n ,
x = [ x1 , x 2 ,.... x n ]T ,
omezení ešení je ve tvaru a11 x1 + a12 x 2 + ........... + a1n x n ≤≥ b1 ,
a 21 x1 + a 22 x 2 + ........... + a 2 n x n ≤≥ b2 , ........................................................ a m1 x1 + a m 2 x 2 + ........... + a mn x n ≤≥ bm , x1 , x 2 ,...., x n ≥ 0.
2) Úlohy vedoucí na lineární programování • Optimální výrobní program – Vyrábíme n r zných výrobk a každý z nich pot ebuje m r zných zdroj (surovin a pod.). Na výrobu jednoho výrobku j-tého druhu pot ebujeme aij jednotek i-tého zdroje. Zdroje jsou omezené a máme k dispozici bi jednotek i-tého zdroje. Zisk p i výrob jednoho výrobku j-tého typu je cj. Po ty výrobk j-tého typu ozna íme xj. Naší úlohou je maximalizovat zisk p i respektování omezení na zdroje surovin. Potom hledáme ešení problému max{c T x : Ax ≤ b, x ≥ 0}.
• Sm šovací problém – Máme n základních surovin. Úkolem je namíchat suroviny tak, aby výsledný výrobek m l p edepsané složení a surovinové náklady minimální. Množství jednotek suroviny j-tého druhu ozna íme xj, její cena za jednotku je cj. Požadované složení výsledného produktu je popsáno vektorem b, jehož složky bi jsou rovny požadovanému obsahu látky i ve výsledném produktu. Jednotkové množství základní suroviny jtého typu obsahuje aij jednotek látky typu i. Hledáme tedy min{c T x : Ax = b, x ≥ 0}.
• Dopravní problém – Máme m výrobc a n spot ebitel . Snažíme se rozvést zboží od výrobc ke spot ebitel m s minimálními náklady p i respektování omezení. • Distribu ní problém – Jedná se o optimální rozpis (resp. plánování) výroby na stroje i jiná za ízení. • Optimální ízení dynamických systém – Mnoho problému optimálního ízení lze p evést na úlohu lineárního programování. P íkladem je optimální ízení lineárního diskrétního dynamického systému s omezením velikosti vstupních veli in a lineárním kritériem ( asov optimální diskrétní ízení).
P íklad úlohy lineárního programování P íklad je z prost edí optimálního výrobního programu. Vyrábíme výrobky A a B ze surovin S1 a S2. Zásoby surovin jsou omezené skladem: Výrobek A Výrobek B Sklad
Surovina S1 3 kg / výrobek 6 kg / výrobek 1 500 kg
Surovina S2 4 kg / výrobek 2 kg / výrobek 800 kg
Cena 5 USD / výrobek 8 USD / výrobek MAX
Kolik výrobk A a B máme vyrobit, aby byl maximální zisk p i respektování skladových zásob surovin?
• Formulace úlohy Ozna me x1 množství výrobku A a x2 množství výrobku B. Ú elová funkce bude vyjad ovat hodnotu množství obou výrobk a omezení skladové zásoby: f ( x) = 5 x1 + 8 x 2 , 3x1 + 6 x 2 ≤ 1500, 4 x1 + 2 x 2 ≤ 800, x1 ≥ 0, x 2 ≥ 0. • Grafické ešení Do grafu na rtneme ob omezení a ú elovou funkci a hledáme maximum funkce f(x).
ešení úlohy leží na hranici p ípustných hodnot ešení ( ty úhelníku ABCD). Vzhledem k lineární ú elové funkci lze ešení hledat na vrcholech množiny p ípustných ešení. V našem p ípad dostáváme optimální ešení: x1 = 100 a x2 = 200.
3) Simplexová metoda Budeme ešit základní úlohu lineárního programování max{c T x : Ax ≤ b, x ≥ 0} .
ešení úloh lineárního programování pomocí simplexové metody ukážeme na p edchozím p íkladu: f ( x ) = 5 x1 + 8 x 2 → MAX ,
3x1 + 6 x 2 ≤ 1500, 4 x1 + 2 x 2 ≤ 800, x1 ≥ 0, x 2 ≥ 0. • Prvním krokem simplexové metody je p epis úlohy do kanonického tvaru. Zavedením dalších prom nných x3 a x4, které nazýváme dopl kovými, dostaneme z nerovnosí rovnosti f ( x ) = 5 x1 + 8 x 2 → MAX , 3x1 + 6 x 2 + x3 = 1500, 4 x1 + 2 x 2 + x 4 = 800, x1 ≥ 0, x 2 ≥ 0, x3 ≥ 0, x 4 ≥ 0. • Dalším krokem je tvorba tzv. simplexové tabulky, do které se zapisuje omezení a upravené kritérium (v tomto p ípad f(x) = -5 x1 - 8 x2): x1 3 4 -5
x2 6 2 -8
x3 1 0 0
x4 0 1 0
b 1500 800 0 = f(x)
Simplexová tabulka popisuje v prvních dvou ádcích naše dv omezení. Z prvního omezení plyne x3 = 1500 - (3x1 + 6x2) a z druhého omezení zase plyne x4 = 800 - (4x1 + 2x2). Odtud dostaneme základní ešení x3 = 1500 a x4 = 800 (ostaní prom nné jsou nulové x1 = x2 = 0). Poslední ádek vyjad uje kritérium, které je nulové. Tento krok znamená, že jsme v bodu A na obrázku (viz. grafické ešení). Nyní musíme ur it prom nnou (která odpovídá sloupci), pomocí které budeme rozvíjet ešení. Vybíráme tu prom nnou, která má nejnižší hodnotu v posledním ádku (ú elové funkci) a vyskytuje se v ú elové funkci (tato prom nná nejvíce zvýší hodnotu ú elové funkce). Tímto postupem ur íme tzv. klí ový sloupec, který v našem p ípad odpovídá prom nné x2. Dále musíme ur it tzv. klí ový ádek, kterým budeme ostatní ádky upravovat (respektive eliminovat) tak, abychom v ostatních ádcích dostali v klí ovém sloupci nulové hodnoty. Klí ový ádek je takový ádek, který má minimální podíl len bj / aj pro všechny ádky omezení j = 1,...,m, kde aj symbolizuje prvek v klí ovém sloupci. V našem p ípad je klí ovým ádkem první ádek protože podíl 1500/6 = 250 je menší, než podíl 800/2 = 400, ve druhém ádku. Po úprav ádk ádkem klí ovým dostaneme
x1 1/2 3 -1
x2 1 0 0
x3 1/6 -1/3 4/3
x4 0 1 0
b 250 300 2000 = f(x)
Z upravené simplexové tabulky lze p e íst ešení (ve tvaru x* = [x1, x2, x3, x4]) x* = [0, 250, 0, 300], které ješt není optimální, protože v posledním ádku se vyskytuje záporná hodnota v prvním sloupci tabulky. Tato druhá iterace odpovídá bodu B na obrázku pro grafické ešení. Obdobn provedeme ješt jednu iteraci, tentokrát klí ový sloupec je sloupec odpovídající prom nné x1, klí ový ádek bude druhý ádek. Po provedení další úpravy dostaneme x2 1 0 0
x1 0 1 0
x3 2/3 -1 1/3
x4 -1/6 1/3 1/3
b 200 100 2100 = f(x)
Tato iterace byla poslední, protože poslední ádek obsahuje nezáporná ísla ve sloupcích odpovídající prom nným v kriteriu (tedy x1 a x2). Z poslední tabulky lze ode íst optimální ešení (x1 obsahuje bázi [0,1], které odpovídá sloupec b = [200,100], platí x1 = 100) x* = [100, 200, 0, 0]. Zmín né ešení odpovídá bodu C na obrázku.
4) Speciální p ípady • Alternativní ešení V p ípad , že úloha lineárního programování nemá jednozna né ešení, ale má jich nekone n mnoho, jedná se o alternativní ešení. Tento p ípad ukážeme na jednoduchém p íkladu
P íklad:
f ( x ) = 2 x1 + 4 x 2 → MAX , x1 + x 2 ≤ 4, x1 + 2 x 2 ≤ 6, x1 ≥ 0, x 2 ≥ 0.
Vytvo íme simplexovou tabulku s dopl kovými prom nnými x1 1 1 -2
x2 1 2 -4
x3 1 0 0
x4 0 1 0
b 4 6 0 = f(x)
Provedeme úpravu klí ovým ádkem a dostaneme x1 1/2 1/2 0
x2 0 1 0
x3 1 0 0
x4 -1/2 1/2 2
b 1 3 12 = f(x)
V posledním ádku jsme po první iteraci dostali nezáporné prvky, tudíž jsme dosáhli optimálního ešení x* = [0, 3, 1, 0]. Všimn me si ale prvního sloupce, který sice neobsahuje bázi (a proto x1 = 0), ale v ádku reprezentující kriterium je nula. Z toho plyne, že lze upravit tabulku tak, aby první prom nná byla bázová - vynásobíme první ádek 2 a eliminujeme druhý ádek (poslední ádek neupravujeme!). Potom dostaneme x1 1 0 0
x2 0 1 0
x3 2 -1 0
x4 -1 1 2
b 2 2 12 = f(x)
Z tabulky ode teme další optimální ešení x* = [2, 2, 0, 0]. Dostali dv krajní optimální ešení x1* = [0, 3] a x2* = [2, 2]. Optimální ešení x* lze parametrizovat
x * = λx1* + (1 − λ ) x2* = λ
0 3
+ (1 − λ )
2 2
, λ ∈ 0,1 .
• Neomezené ešení V p ípad , že úloha lineárního programování nemá omezené ešení, potom m že jedna nebo n kolik prom nných nabývat libovolných hodnot, ú elová funkce roste a prom nná spl uje omezující podmínky.
P íklad:
f ( x ) = x1 + 3 x 2 → MAX , − 2 x1 + x 2 ≤ 4, x1 ≥ 0, x 2 ≥ 0.
Vytvo íme simplexovou tabulku s dopl kovými prom nnými x1 -2 -1
x2 1 -3
x3 1 0
b 4 0 = f(x)
Provedeme úpravu klí ovým ádkem a dostaneme x1 -2 -7
x2 1 0
x3 1 3
b 4 12 = f(x)
Po první iteraci dostáváme ešení x* = [0, 3, 0] (bod A na následujícím obrázku). Dále nám zbývá optimalizovat ešení podle prom nné x1. Ale prvek odpovídající omezení pro tuto prom nnou je záporný (-2) a tudíž prom nná m že r st nade všechny meze, p i emž ú elová funkce také roste, omezující podmínka je p itom spln na. Potom pro ešení platí x* = [∞,∞, 0] a f(x) = ∞.
Úlohy Úloha 8.1: a)
ešte úlohy lineárního programování
f ( x ) = 3.5 x1 + 5 x 2 + 4 x3 → MAX , x1 + 2 x 2 + x3 ≤ 1000, x1 + x 2 + x3 ≤ 900, 2 x1 + x 2 + 4 x3 ≤ 1900,
b)
x1 ≥ 0, x 2 ≥ 0, x3 ≥ 0. f ( x ) = 2 x1 + 3 x 2 + 7 x3 + 9 x 4 → MAX , x1 + x 2 + x3 + x 4 ≤ 9, x1 + 2 x 2 + 4 x3 + 8 x 4 ≤ 24,
c)
x1 ≥ 0, x 2 ≥ 0, x3 ≥ 0, x 4 ≥ 0. f ( x) = 2 x1 + 3 x2 + 4 x3 → MAX , x1 + x2 + x3 ≤ 10, x1 + 2 x2 + 3 x3 ≤ 21, x1 ≥ 0, x2 ≥ 0, x3 ≥ 0.
Úloha 8.2: Optimální výrobní program Spole nost vyrábí 3 druhy balených aj (A, B a C), každý se skládá ze t í surovin ( aj S1, S2 a S3). Formulujte úlohu jako úlohu lineárního programování a ur ete, kolik kus aje A, B a C se má vyrobit, abychom maximalizovali zisk z prodeje s respektem na skladové zásoby surovin S1, S2 a S3. Ur ete zisk z prodeje. aj A aj B aj C Sklad
S1 10 g/kus 10 g/kus 20 g/kus 40 kg
S2 20 g/kus 10 g/kus 20 g/kus 50 kg
S3 10 g/kus 30 g/kus 20 g/kus 60 kg
Cena 4 K /kus 7 K /kus 8 K /kus MAX
Úloha 8.3: Distribu ní (plánovací) problém Spole nost vlastní dva stroje S1, S2 a vyrábí dva druhy výrobk V1 a V2. Denní vytíženost obou stroj má být maximáln 10 hodin. Za den se musí vyrobit 60 kus výrobk V1 a 80 kus výrobk V2. Výrobek V1 stojí 100 K , výrobek V2 50 K . Formulujte úlohu jako úlohu lineárního programování a ur ete kolik hodin se budou vyráb t výrobky V1 na prvním stroji S1 a druhém stroji S2, a kolik hodin se budou vyráb t výrobky V2 na prvním stroji S1 a druhém stroji S2. V p ípad , že v plánu rozvrhu výroby stroj budou prostoje, upravte rozvrh s ohledem na zisk tak, aby výsledný rozvrh prostoje neobsahoval. Ur ete tento zisk. Výkon stroj lze popsat tabulkou: Stroj S1 Stroj S2
Výrobek V1 Výrobek V2 5 ks/hod 10 ks/hod 10 ks/hod 10 ks/hod
Úloha 8.4: Sm šovací problém Ze t í složek je t eba namíchat 20 kg sm si. První složka stojí 10 K /kg, druhá 10 K /kg a t etí 30 K . P itom sm s musí obsahovat alespo 50 procent druhé složky, maximáln 60 procent druhé složky a minimáln 15 procent t etí složky. Formulujte úlohu jako úlohu lineárního programování a ur ete hmotnostní podíl složek ve sm si tak, aby byly surovinové náklady minimální.
