Algebra

3x11 + 12x12 + 5x13 + 4x14 + 20x21 + 7x22 +...+ 15x33 + 6x34.
Omezující podmínky jsou pak trojího druhu:
1) podmínky nezápornosti (nemůže být převáženo záporné množství mouky), tj.
∀i = 1,2,3;∀j = 1,2,3,4 : xij≥0,
2) žádný mlýn nemůže dodat víc mouky než vyrobí, tj.
x11 +x12 +x13 +x14 ≤ 1 000,
x21 +x22 +x23 +x24 ≤ 800,
x31 +x32 +x33 +x34 ≤ 700,
3) každá pekárna musí dostat právě tolik, kolik potřebuje, tj.
x11 +x21 +x31 = 320,
x12 +x22 +x32 = 540,
x13 +x23 +x33 = 480,
x14 +x24 +x34 = 280.
16
Úloha má řešení jen v případě, že mlýny dohromady semelou aspoň tolik mouky, kolik pekárny dohromady potřebují.
3.3.3 Řezný plán
Je třeba nařezat tři typy kovových tyčí o délce 110 cm, 90 cm a 60 cm. K dispozici jsou standardní tyče o délce
240 cm, které je třeba rozřezat. Odpad Při řezání nesmí přesáhnout 40 cm z jedné rozřezané tyče. Je třeba nařezat
700 tyčí první délky, 400 druhé a 1500 třetí. Jakým způsobem standardní tyče rozřezat, aby bylo 1) použito co
nejmenší množství standardních tyčí, nebo 2) byl minimalizován celkový odpad?
Existuje šest způsobů řezání, při kterých není odpad ze standardní tyče větší než 40 cm. Tabulka 3 udává, kolik
kterého typu tyče bude při kterém způsobu řezání vyrobeno a jaký při něm vznikne odpad.
Tyč délky I. II. III. IV. V. VI Počet kusů
110 2 1 1 — — — 700
90 — 1 — 2 1 400
60 — — 2 1 2 4 1500
Odpad v cm 20 40 10 0 30 0
Tabulka 3: Řezný plán –podklady
Řešení: Za neznámé x1,x2,...,x6 zvolíme počet standardních tyčí rozřezaných příslušným způsobem I až VI.
Pokud chceme minimalizovat počet rozřezaných tyčí, sestavíme účelovou funkci
z = x1 +x2 +x3 +...+x6 →min.
Pokud bychom alternativně chtěli minimalizovat odpad, zapíšeme účelovou funkci
z = 20x1 + 40x2 + 10x3 + 30x5 →min.
Systém omezení musí jednak zajistit, aby bylo nařezáno správné množství jednotlivých tyčí, jednak, aby nebylo
nebylo řezáno ”méně než vůbec“. Tedy
2x1 + 1x2 + 1x3 = 700
1x2 + + 2x4 + 1x5 = 400
2x3 + 1x4 + 2x5 + 4x6 = 1 500
x1,x2,...,x6 ≥ 0
3.3.4 Nutriční problém
Pro výkrm dobytka potřebujeme směs, která obsahuje minimálně 2,5 krmných jednotek a 250 g bílkovin na kus
denně. Směs vznikne smícháním pokrutin a kukuřice. V jakém poměru je smíchat, aby krmná směs měla dostatečný
nutriční obsah a byla co nejlacinější? Obsah látek v 1 kg jednotlivých složek a jejich cenu uvádí tabulka .
Krmivo krm. jednotek bílkovin v g. jednotková cena
pokrutiny 1 400 0,5
kukuřice 1,25 80 0,4
Tabulka 4: Nutriční problém – podklady
17
Řešení: Za neznámé x1 a x2 si zvolíme množství pokrutin, resp. kukuřice ve směsi na jeden kus dobytka. Účelová
funkce má pak minimalizovat náklady, tedy
z = 0,5x1 + 0,4x2 →min.
Zároveň musí být dosaženo požadovaného nutričního složení
1x1 + 1,25x2 ≥ 2,5,
400x1 + 80x2 ≥ 250,
x1,x2 ≥ 0.
18
4 Výpočet v simplexové tabulce
V tomto oddílu ukážeme šest možných typů výsledků řešní úloh lineárního programování, a to jak v simplexové
tabulce, tak řešené graficky.
4.1 Úloha nená žádné přípustné řešení
Uvažujme maximalizační úlohu z = x1−x2 za omezení
−2x1 +x2 ≥ 2,
x1−2x2 ≥ 2,
2x1 + 2x2 ≥ 3,
x1,x2 ≥ 0.
Kanonický tvar vlastních omezení vypadá takto:
−2x1 +x2−x3 +x6 = 2,
x1−2x2−x4 +x7 = 2,
2x1 + 2x2−x5 +x8 = 3.
Protože jsme do úlohy přidali umělé proměnné x6,x7,x8 musíme je nejprve eliminovat. Nejdříve tedy budeme
optimalizovat podle pomocné účelové funkce zprime = x6 +x7 +x8, která je minimalizační.
x1 x2 x3 x4 x5 x6 x7 x8 bi λi
x6 −2 1 −1 0 0 1 0 0 2 –
x7 1 −2 0 −1 0 0 1 0 2 2
x8 2 2 0 0 −1 0 0 1 3 3/2
z −1 1 0 0 0 0 0 0 0
zprime 1 1 −1 −1 −1 0 0 0 7
x1 x2 x3 x4 x5 x6 x7 x8 bi λi
x6 0 3 −1 0 −1 1 0 1 5
x7 0 −3 0 −1 1/2 0 1 −1/2 1/2
x1 1 1 0 0 −1/2 0 0 1/2 3/2
z 0 2 0 0 −1/2 0 0 1/2 3/2
zprime 0 0 −1 −1 −1/2 0 0 −1/2 11/2
Pomocná účelová funkce nabyla svého minima při bazickém řešení, při kterém nejsou všechny umělé proměnné
eliminovány z báze. Nelze tedy najít počáteční přípustné bazické řešení původní úlohy – tako úloha nemá žádné
řešení.
Grafická interpretace úlohy viz obrázek 5.
4.2 Úloha nemá konečné optimální řešení
Uvažujme maximalizační úlohu z = x1−x2 za omezení
−2x1 +x2 ≤ 2,
x1−2x2 ≤ 2,
x1,x2 ≥ 0.
19
x1
x2
−1
2
−1
21.5
1.5
−2x1 +x2 ≥2
x1−2x2 ≥2
2x1 + 2x2 ≥3
Obrázek 5: Úloha, která nemá přípustné řešení
Kanonický tvar omezení
−2x1 +x2 +x3 = 2,
x1−2x2 +x4 = 2
umožňuje přímý přepis do simplexové tabulky:
x1 x2 x3 x4 bi λi
x3 −2 1 1 0 2 –
x4 1 −2 0 1 2 2
z −1 1 0 0
x1 x2 x3 x4 bi λi
x3 0 −3 1 2 6 –
x1 1 −2 0 1 2 –
z 0 −1 0 1 2
Soudě podle transformovaných hodnot účelové funkce, zařazení x2 do báze zlepšuje hodntu účelové funkce. Úloha
však není v tomto směru omezená (neexistuje λi nezáporné). Množina přípustných řešení není ve směru růstu hodnot
účelové funkce omezená, tj. nemá optimum, neboť ke každému přípustnému řešení existuje také jiné přípustné řešení
s lepší hodnotou účelové funkce.
Grafická interpretace úlohy viz obrázek 6.
20
x1
x2
−1
2
−1
2
−2x1 +x2 ≤2
x1−2x2 ≤2
Obrázek 6: Úloha bez optimálního řešení
4.3 Úloha má jediné optimální řešení
Uvažujme maximalizační úlohu s účelovou funkcí z = x1−x2 a omezeními
−2x1 +x2 ≤ 2,
x1−2x2 ≤ 2,
x1 +x2 ≤ 5,
x1,x2 ≥ 0.
Přepis úlohy do kanonického tvaru přidáním tří doplňkových proměnných x3,x4,x5 umožňuje přímo konstrukci
simplexové tabulky:
x1 x2 x3 x4 x5 bi λi
x3 −2 1 1 0 0 2 –
x4 1 −2 0 1 0 2 2
x5 1 1 0 0 1 5 5
z −1 1 0 0 0 0
x1 x2 x3 x4 x5 bi λi
x3 0 −3 1 2 0 6 –
x1 1 −2 0 1 0 2 –
x5 0 3 0 −1 1 3 1
z 0 −1 0 1 0 2
21
x1 x2 x3 x4 x5 bi λi
x3 0 0 1 1 1 9
x1 1 0 0 1/3 2/3 4
x2 0 1 0 −1/3 1/3 1
z 0 0 0 2/3 1/3 3
Úloha má optimální řešení x∗1 = 4, x∗2 = 1. Maximální hodnota účelové funkce je z∗ = 3.
Toto řešení je jediné: koeficienty transformované účelové funkce jsou pro nebazické prvky nenulové.
Grafická interpretace úlohy viz obrázek 7.
x1
x2
−1
2
−1
2
5
5
−2x1 +x2 ≤2
x1−2x2 ≤2
x1 +x2 ≤5
Obrázek 7: Úloha s jedinným optimálním řešením
4.4 Úloha má nekonečně mnoho řešení, z toho dvě bazická
Uvažujme úlohu s maximalizační účelovou funkcí z = x1−x2 a systémem omezení
−2x1 +x2 ≤ 2,
x1−x2 ≤ 2,
x1 +x2 ≤ 5,
x1,x2 ≥ 0.
Přepis úlohy do kanonického tvaru zařazením tří doplňkových proměnných x3,x4,x5 umožňuje konstrukci simple-
xové tabulky:
x1 x2 x3 x4 x5 bi λi
x3 −2 1 1 0 0 2 –
x4 1 −1 0 1 0 2 2
x5 1 1 0 0 1 5 5
z −1 1 0 0 0 0
22
x1 x2 x3 x4 x5 bi λi
x3 0 −1 1 2 0 6 –
x1 1 −1 0 1 0 2 –
x5 0 2 0 −1 1 3 3/2
z 0 0 0 1 0 2
Úloha má optimální řešení x∗1 = 2, x∗2 = 0. Maximální hodnota účelové funkce je z∗ = 2. Toto řešení však není
jediné: existuje nekonečně mnoho řešení, neboť pokud nebazická proměnná x2 vstoupí do báze, hodnota účelové
funkce se nezmění (příslušná hodnota v řádku z je nulová). Můžeme tedy spočítat i jiné bazické řešení:
x1 x2 x3 x4 x5 bi λi
x3 0 0 1 3/2 1/2 15/2
x1 1 0 0 1/2 1/2 7/2
x2 0 1 0 −1/2 1/2 3/2
z 0 0 0 1 0 2
Příslušné řešení (x∗∗1 = 7/2, x∗∗2 = 3/3) má stejnou hodnotu účelové funkce. Je tedy také optimální. Dále jsou
optimálními řešení úlohy také všechny konvexní kombinace obou řešení. Je-li x∗ první optimální bazické řešení (ze
druhé tabulky) a x∗∗ druhé optimální bazické řešení (ze třetí tabulky), pak je optimálním řešením také každé řešní
x = kx∗+ (1−k)x∗∗, k∈〈0,1〉.
Množina všech optimálních řešení je přímka. To lze poznat už ve druhé tabulce podle toho, že nebazická proměnná
x2 může vzrůst maximálně na hodnotu 3/2 (to je hodnota nejmenší nezáporné λi).
Grafická interpretace úlohy viz obrázek 8.
x1
x2
−1
2
−2
2
5
5
−2x1 +x2 ≤2
x1−x2 ≤2
x1 +x2 ≤5
Obrázek 8: Úloha se dvěma bazickými optimálními řešeními
23
4.5 Úloha má nekonečně mnoho řešení, z toho jedno bazické
Uvažujme úlohu s maximalizační funkcí z = x1−2x2 a systémem omezení
−2x1 +x2 ≤ 2,
x1−2x2 ≤ 2,
x1,x2 ≥ 0.
Úloze odpovídá simplexová tabulka:
x1 x2 x3 x4 bi λi
x3 −2 1 1 0 2 –
x4 1 −2 0 1 2 2
z −1 2 0 0 0
a
x1 x2 x3 x4 bi λi
x3 0 −3 1 2 6 –
x1 1 −2 0 1 2 –
z 0 0 0 1 2
Úloha má jedno optimální bazické řešení x∗1 = 2, x∗2 = 0 o hodnotě účelové funkce z∗ = 2. Kromě něho existuji
i nekonečně mnoho dalších nebazických řešení. Bazické řešení je pouze jedno, neboť při zařazení x2 do báze může
proměnná x2 růst nade všechny meze.
Grafická interpretace úlohy viz obrázek 9.
x1
x2
−1
2
−1
2
−2x1 +x2 ≤2
x1−2x2 ≤2
Obrázek 9: Úloha s jedním bazickým řešením a nekonečně mnoha nebazickými
24
4.6 Degenerovaná úloha
Uvažujme úlohu s maximalizační účelovou funkcí z = x1−x2 a systémem omezení
x1−x2 ≤ 2,
x1 + 2x2 ≤ 2,
x1,x2 ≥ 0.
Této úloze odpovídá simplexová tabulka:
x1 x2 x3 x4 bi λi
x3 1 −1 1 0 2 2
x4 1 2 0 1 2 2
z −1 1 0 0 0
Do báze zařadíme proměnnou x1; z báze může vypadnout buď proměnná x3 nebo x4. Podle toho dostaneme dvě
zdánlivě odlišná řešení:
x1 x2 x3 x4 bi λi
x3 0 −3 1 −1 0
x1 1 2 0 1 2
z 0 3 0 1 2
x1 x2 x3 x4 bi λi
x1 1 −1 1 0 2
x4 0 3 −1 0
z 0 0 1 0 2
Ve skutečnosti mají obě řešení stejný tvar x∗ = (2,0,0,0). Hodnota účelové funkce v bodě maxima je z∗ = 2.
Grafická interpretace úlohy viz obrázek 10.
25
x1
x2
−1
2
−1
2
x1−x2 ≤2
x1 + 2x2 ≤2
Obrázek 10: Degenerovaná úloha
26