Lineární programování
- úvod
–
•
= optimalizace lineární funkce na množině, omezené lineárními funkcemi
Jsme schopni nalézt globální minimum.

Lineární programování
- příklad
–
•
Čokoládovna vyrábí 5 druhů výrobků. Jsou to výrobky V1, V2, V3, V4, a V5. Spotřebovává k tomu 3
základní surovniy: tuk, kakao a cukr. Tyto suroviny jsou k dispozici v omezených množstvích: 1500
kg tuku, 450 kg kakaa a 300 cukru na den.
Kapacita strojního zařízení je dostatečná, totéž se týká energie a pracovních sil, i další zdroje
jsou k dispozici v dostatečném množství.

Lineární programování
- příklad II
–
•
Spotřeba surovin na 1 kg výrobku je dána tabulkou:
V tabulce jsou uvedeny rovněž ceny 1 kg každého výrobku.

Lineární programování
- příklad
–
•
Výrobky jsou vyráběny technologicky nezávisle na sobě navzájem. Výroba se tedy uskutečňuje ve formě
pěti výrobních procesů, které však nejsou navzájem zcela izolované, neboť společně spotřebovávají
výrobní zdroje, jeden proces na úkor druhého.
Pro účely matematické formulace zaveďme 5 proměnných xj, popisujících množství výrobku Vj v kg (jen
vzhledem k našim 3 surovinám).

Lineární programování
- příklad
–
•
Matematická formulace úlohy:
Hledáme tedy nezáporné hodnoty proměnných xj ³ 0
    (j = 1, 2, ..., 5), vyhovující nerovnostem:
               0,4.x2 + 0,3.x3 + 0,6.x4 + 0,6.x5  £ 1500
0,05.x1 + 0,2.x2 + 0,1.x3 + 0,1.x4             £ 300
  0,1.x1 + 0,2.x2 + 0,2.x3 + 0,1.x4 + 0,2.x5  £ 450
a maximalizující účelovou funkci:
f(x) = 20.x1 + 120.x2 + 100.x3 + 140.x4 + 40.x5

Lineární programování
- příklad
–
•
Optimální řešení tohoto problému:
x1* = 0; x2* = 0; x3* = 1000; x4* = 2000; x5* = 0
Maximální hodnota účelové funkce:
f(x*) = 380 000 Kč
Poznámka: Úlohu lze také následovně rozšířit: Výrobku V1 musí být alespoň 100 kg a výrobku
V5 alespoň    200 kg. Pak nezměněná matematická formulace bude navíc obohacena dvěma nerovnostmi:
x1 ³ 100; x5 ³ 200

Lineární programování
- aplikace
–
•
Výrobní plán: Cílem je určit, kolik vyrábět kterého výrobku tak, abychom maximalizovali zisk. Víme,
kolik které suroviny potřebujeme na jednotlivé výrobky. Známe množství surovin, které máme k
dispozici.

Dopravní plán: Cílem je určit kolik kterých výrobků přepravovat po jednotlivých trasách od výrobce
ke spotřebitelům tak, abychom měli co nejnižší náklady.

Lineární programování
- aplikace II
–
•
Směšovací problém: Chceme vyrobit slitinu předepsaného složení ze surovin se známým složením tak,
abychom dodrželi metalurgické předpisy a minimalizovali náklady.

Řízení zásob: Cílem je plánovat nákupy tak, abychom uspokojili poptávku a přitom minimalizovali
náklady na uskladnění.

Lineární programování
- aplikace III
–
•

Regresní analýza: Cílem je proložit naměřenými hodnotami přímku tak, abychom minimalizovali
maximální absolutní odchylku.

Další aplikace: Lineární programování má aplikace především v technologii (řízení výroby),
ekonomice (finanční modely) a konstruování (návrh struktury).

Lineární programování
- historie
–
•
Starověk: V antice byly formulovány a pomocí geometrie řešeny některé izoperimetrické úlohy.
Například: Najděte rovnoběžník největšího obsahu při konstantním obvodu.

Středověk: Později byly formulovány zejména úlohy založené na rozkladu čísel na součet a součin
tak, aby určité kritérium mělo optimální hodnotu.

Lineární programování
- historie II
–
•

Novověk: S rozvojem infnitesimálního počtu se objevily nyní klasické metody pro analytické hledání
extrémů (průběh funkce aj.). Následovalo postupně rozpracování teoretických poznatků, které
připravilo nástroje pro 20.století.

Lineární programování
- historie III
–
•

20.století: Koncem třicátých let Kantorovič formuloval ekonomickou úlohu pomocí lineárních omezení.
Během druhé světové války byly rozpracovány základy matematických metod organizace vojenských
operací. V roce 1941 Hitchcock formuloval dopravní úlohu, v roce 1945 formuloval Stiegler dietní
problém. V roce 1947 Dantzig formuloval úlohu později nazvanou Koopmansem úlohou lineárního
programování. Navrhl algoritmus nazvaný simplexová metoda pro její řešení. V diskusi Dantziga a Von
Neumanna byl zaveden pojem duality a následovala desetiletí bouřlivého rozvoje optimalizačních
modelů a metod a jejich aplikací.

Lineární programování
- obecná formulace
–
•
Nechť jsou dány vektory ai, c Î Rn a čísla bi Î R (i = 1, 2, ..., m).
Poznámka: n je počet proměnných a m počet rovnic
Řešíme problém:
opt cTx opt Î {min, max}
Za předpokladů:
aiT.x £ bi  (i Î I1)
aiT.x ³ bi  (i Î I2)
aiT.x = bi  (i Î I - I1 - I2)
kde I = {1, 2, ..., m}; I1 Ì I; I2 Ì I

Lineární programování
- obecná formulace - příklad
–
•
Řešíme problém:
Příklad:
max f(x) f(x) = 20.x1 + 120.x2 + 100.x3 + 140.x4 + 40.x5
Obecně:
opt cTx opt Î {min, max}
Konkrétně:
max (20, 120, 100, 140, 40)T.x

Lineární programování
- obecná formulace - příklad
–
•
Za předpokladů:
Příklad: 0,4.x2 + 0,3.x3 + 0,6.x4 + 0,6.x5  £ 1500
0,05.x1 + 0,2.x2 + 0,1.x3 + 0,1.x4 £ 300
0,1.x1 + 0,2.x2 + 0,2.x3 + 0,1.x4 + 0,2.x5  £ 450
x1 ³ 100
x5 ³ 200
Obecně: aiT.x £ bi  (i Î I1)
aiT.x ³ bi  (i Î I2)
aiT.x = bi  (i Î I - I1 - I2)
kde I = {1, 2, ..., m}; I1 Ì I; I2 Ì I

Lineární programování
- obecná formulace - příklad
–
•
Konkrétně: (0, 0.4, 0.3, 0.6, 0.6)T.x £ 1500
(0.05, 0.2, 0.1, 0.1, 0)T.x £ 300
(0.1, 0.2, 0.2, 0.1, 0.2)T.x £ 450
(1, 0, 0, 0, 0)T.x ³ 100
(0, 0, 0, 0, 1)T.x ³ 200
Poznámka: n = 5
m = 5
I = {1, 2, 3, 4, 5}
I1 = {1, 2, 3}
I2 = {4, 5}

Lineární programování
- standardní tvar
–
•
Obecnou formulaci úlohy lze zapsat v tzv. standardním tvaru:
Řešíme problém:
min cTx
Za předpokladů:
A.x = b A Î Rm x n
x ³ 0

Lineární programování
- standardní tvar II
–
•
Vztahy, využité při přepsání na standardní tvar:
max -> min
max f(x) = - min -f(x)
Přepis rovnic:
 aiT.x ³ bi  => -aiT.x £ -bi

Lineární programování
- standardní tvar III
–
•
Nerovnost na rovnost:
aiT.x £ bi  => aiT.x + xn+1 = bi, kde: xn+1 ³ 0
kde xn+i je umělá proměnná, která se začlení do vektoru proměnných x
=> nový vektor obsahuje prvky x1, x2, ..., xn původního vektoru x a navíc pro každou i-tou
nerovnost člen xn+i
původní vektor x: (x1, x2, ..., xn)
nový vektor x: (x1, x2, ..., xn, xn+1, xn+2, ..., xn+m)

Lineární programování
- standardní tvar - příklad
–
•
Příklad:
(0, 0.4, 0.3, 0.6, 0.6)T.x £ 1500
(0.05, 0.2, 0.1, 0.1, 0)T.x £ 300
(0.1, 0.2, 0.2, 0.1, 0.2)T.x £ 450
Přepis rovnic na tvar A.x = b:
    x ³ 0

Lineární programování
- další definice
–
•
Množina přípustných řešení:
S = {x; A.x = b; x ³ 0}
V rámci této množiny minimalizujeme funkce cTx.
Přípustné řešení x* Î S nazveme optimálním řešením úlohy, jestliže:
cTx ³ cTx* " x Î S

Lineární programování
- řešení úlohy
–
•
Grafické řešení
Nejstarší metoda pro řešení úloh LP.
Lze použít pro úlohy se dvěma případně třemi proměnnými.
Přístup vhodný pro manuální řešení, obtížně automatizovatelný.
Simplexová metoda
Nejčastěji používaný přístup.
Lze implementovat pomocí vhodného progamovacího jazyka.

Lineární programování
- řešení úlohy - grafické řešení
–
•
Příklad:
Hledejte minimum funkce f(x) = x1 - x2 na množině nezáporných řešení soustavy:
2.x1  + x2  ³ 2
-3.x1 + 2.x2  £ 6
x1     + x2  £ 4

Lineární programování
- řešení úlohy - grafické řešení II
–
•
Výpočet průsečíků rovnic s osami:
 Rovnice 2.x1  + x2  ³ 2:
Px11 = (1, 0), Px21 = (0, 2)
 Rovnice -3.x1 + 2.x2  £ 6:
Px12 = (-2, 0), Px22 = (0, 3)
 Rovnice  x1     + x2  £ 4:
Px13 = (4, 0), Px23 = (0, 4)

Lineární programování
- řešení úlohy - grafické řešení III
–
•

Lineární programování
- řešení úlohy - grafické řešení IV
–
•
Množinu S tedy tvoří pětiúhelník s vrcholy:
[0, 2]; [0, 3]; [1, 0]; [4, 0] a průsečík rovnic:
 x1     + x2  £ 4
 -3.x1 + 2.x2  £ 6
=>
[2/5, 18/5]

Lineární programování
- řešení úlohy - grafické řešení V
–
•
Hledáme minimum funkce f(x) = x1 - x2 na množině S.
Znázorníme-li soustavu rovnoběžek:
x1 - x2 = k pro k Î S
zjistíme, že funkce f(x) = x1 - x2 nabývá nejmenší hodnoty na množině S ve vrcholu [2/5, 18/5].

Lineární programování
- řešení úlohy - grafické řešení VI
–
•

Lineární programování
- řešení úlohy - grafické řešení VII
–
•
Příklad 2:
Hledejte minimum funkce f(x) = x1 - x2 na množině nezáporných řešení soustavy:
2.x1  + x2  ³ 2
-3.x1 + 2.x2  £ 6
- x1    - x2  ³ 1
 x1 ³ 0
 x2 ³ 0

Lineární programování
- řešení úlohy - grafické řešení VIII
–
•

Lineární programování
- řešení úlohy - grafické řešení IX
–
•
Hledáme minimum funkce f(x) = x1 - x2 na množině S.
Ale z předchozího obrázku je jasné, že S = Æ
=> nelze najít optimální řešení

Lineární programování
- řešení úlohy - grafické řešení X
–
•
Příklad 3:
Hledejte minimum funkce f(x) = x1 - x2 na množině nezáporných řešení soustavy:
2.x1  + x2  ³ 2
-3.x1 + 2.x2  £ 6
 x1 ³ 0
 x2 ³ 0

Lineární programování
- řešení úlohy - grafické řešení XI
–
•

Lineární programování
- řešení úlohy - grafické řešení XII
–
•
Hledáme minimum funkce f(x) = x1 - x2 na množině S.
Ale z předchozího obrázku je jasné, že množina S je nekonečná
=> nelze najít optimální řešení

Lineární programování
- simplexová metoda - teorie
–
•
DEF:
Množina S Ì Rn je konvexní, pokud "x1, x2 Î S:
l × x1 + (1 - l) × x2 Î S pro každé l Î [0, 1].
DEF:
Bod l × x1 + (1 - l) × x2 pro l Î [0, 1] se nazývá konvexní kombinací x1 a x2.

Lineární programování
- simplexová metoda - teorie II
–
•
DEF:
Konvexní obal množiny S je nejmenší konvexní množina obsahující S. Označuje se conv(S).
DEF:
Množina P Ì Rn je konvexní polyedr, pokud P je konvexním obalem konečné množiny.

Lineární programování
- simplexová metoda - teorie III
–
•
DEF:
Simplex je konvexní polyedr P = conv {v0, ¼, vm} Ì Rn, kde vm – v0, ¼, v1 – v0 jsou lineárně
nezávislé. Pokud tedy m = n, jde o konvexní obal n + 1 bodů s nenulovým objemem v Rn.
DEF:
Polyedrická množina je průnikem konečného počtu poloprostorů (lze je zapsat ve tvaru {x Î Rn; aTx ³
a }, kde a Î Rn, a Î R).
Je zřejmé, že množina přípustných řešení každé úlohy lineárního programování je polyedrická.

Lineární programování
- simplexová metoda - teorie IV
–
•
DEF: Krajní bod konvexní množiny S Í Rn je prvek S, který není netriviální konvexní kombinací dvou
různých bodů z S. Neexistuje y1, y2 Î S, y1 ¹ y2, l Î (0, 1): x = l × y1 + (1 - l) × y2.

Lineární programování
- simplexová metoda - teorie IV
–
•
DEF: Směr (v bodě x Î S) v uzavřené konvexní množině S Í Rn je takový nenulový vektor d Î Rn, pro
který $ a > 0: x + a × d Î S.

Lineární programování
- simplexová metoda - teorie V
–
•
DEF:
Krajní směr je směr, který není kladnou lineární kombinací dvou různých směrů.

Lineární programování
- simplexová metoda - teorie VI
–
•
Věta:
Kladná lineární kombinace směrů je opět směrem:
Je-li a1, a2 > 0:
x + a1 × d1 Î S
Þ x + a1 × d1 + a2 × d2 Î S
Þ x + b × (a1 × d1 + a2 × d2) Î S pro b ³ 0.
DEF:
Krajní směr je směr, který není kladnou lineární kombinací dvou různých směrů.

Cvičení
- příklad I
–
•
Matematická formulace úlohy:
Podmínky:
- x1 + 3 x2 £  9
2x1 +  3 x2 £ 18
2x1  -     x2 £ 10
           x1 ³ 0
            x2 ³ 0
Maximalizace účelové funkce:
f(x) = 4 x1 + 2 x2

Cvičení
- příklad I - 2
–
•
Optimální řešení:
x1 = 6       x2 = 2       z = 28

Cvičení
- příklad II
–
•
Matematická formulace úlohy:
Podmínky:
 -x1 + 2x2 £ 4
2x1 -   x2 £ 4
  x1 +  x2 £ 5
            x1 ³ 0
            x2 ³ 0
Maximalizace účelové funkce:
f(x) = x1 + x2

Cvičení
- příklad II - 2
–
•
Optimální řešení:Úloha má nekonečně mnoho optimálních řešení - všechny body úsečky AB, pro které
účelová funkce z = 5.

Cvičení
- příklad III
–
•
Matematická formulace úlohy:
Podmínky:
 x1 + x2 ³ 4
-2x1 + x2 £ 2
   x1 -  x2 £ 0
           x1 ³ 0
           x2 ³ 0
Maximalizace účelové funkce:
f(x) = 2x1 + 4x2

Cvičení příklad III - 2
Optimální řešení: Úloha nemá konečné optimální řešení, účelová funkce může na neomezené množině
přípustných řešení nabývat libovolně velkých hodnot.
V případě, že bychom řešili minimalizační problém, tj. hledali minimum funkce z = 2x1 + 4x2 při
stejných omezujících podmínkách, optimální řešení by odpovídalo bodu B.

Cvičení
- příklad IV
–
•
Podnik vyrábí 4 druhů výrobků. Jsou to výrobky V1, V2, V3 a V4. Spotřebovává k tomu materiál m (kg)
a práci p (hodiny). Pro výrobky platí:
Každý den je k dispozici 30 kg materiálu a 50 hodin práce. V jakém množství vyrábět V1, V2, V3 a
V4 tak, aby byl maximální zisk.

Cvičení
- příklad IV - 2
–
•
Matematická formulace úlohy:
Hledáme tedy nezáporné hodnoty proměnných xj ³ 0
    (j = 1, 2, 3, 4), vyhovující nerovnostem:
4.x1 + x2 + 2.x3 +2.x4 ³ 30 (omezení na materiál)
2.x1 + 5.x2 + x3 + 3.x4 ³ 50 (omezení na práci)
a maximalizující účelovou funkci:
f(x) = 5.x1 + 8.x2 + 3.x3 + 4.x4

Cvičení
- příklad V
–
•
Matematická formulace úlohy:
Podmínky:
x1 ³ 0
x1 + x2 ³ 0
2.x1 - x2 £ 2
Maximalizace účelové funkce:
f(x) = x1 - x2

Cvičení
- příklad VI
–
•
Matematická formulace úlohy:
Podmínky:
x1, x2 ³ 0
x1 + x2 £ 40
2.x1 + x2 £ 60
Maximalizace účelové funkce:
f(x) = 4.x1 - 3.x2