Obsah
1 Přípravné poznámky 2
1.1 Používaná symbolika . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Některé pojmy a tvrzení z prerekvizitního předmětu M5171 . . . . . . . . . . 3
2 Lineární programování 4
2.1 Dvě motivační úlohy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.2 Formulace úlohy lineárního programování . . . . . . . . . . . . . . . . . . . . 5
2.3 Ilustrační příklady . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.4 Označení, definice, základní vlastnosti . . . . . . . . . . . . . . . . . . . . . . 8
2.5 Simplexová metoda . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3 Lineární lomené a hyperbolické programování 17
3.1 Motivační úloha . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
3.2 Formulace úloh . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
3.3 Transformace úlohy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
4 Separovatelné úlohy 21
4.1 Motivační úlohy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
4.2 Aproximace separovatelné úlohy úlohou lineárního programování . . . . . . . 23
4.3 Řešení metodami dynamického programování . . . . . . . . . . . . . . . . . . 27
1
1 Přípravné poznámky
1.1 Používaná symbolika
Číselné množiny: R, N, Z -- množina reálných, přirozených a celých čísel.
R+ = {x  R : x > 0} -- kladná reálná čísla
R+ = {x  R : x  0} -- nezáporná reálná čísla
Body, vektory: Množinu Rn budeme vždy uvažovat také jako vektorový prostor.
x -- vektor nebo bod z prostoru Rn. Vektory vždy uvažujeme jako sloupcové,
složky vektoru x  Rn jsou x1, x2, . . . , xn.
(x)i -- i-tá složka vektoru x, tj. (x)i = xi.
o -- nulový vektor.
1 -- vektor, jehož všechny složky jsou jedničky.
ej -- j-tý vektor standardní báze, (ej)i = ij =
1, i = j
0, i = j
(Kroneckerovo delta).
x  y -- (i  {1, 2, . . . , n}) xi  yi a podobně.
x  y -- (i  {1, 2, . . . , n}) xi  y a podobně.
Matice: M(m, n) -- množina matic o m řádcích a n sloupcích. Vektory z množiny Rn
považujeme za matice z množiny M(n, 1).
A -- matice, jejíž složka v i-tém řádku a j-tém sloupci je aij.
aj -- j-tý sloupec matice A.
E -- jednotková matice.
O -- nulová matice.
AT -- matice transponovaná k matici A.
h(A) -- hodnost matice A.
Gradient: Nechť f : Rn  R, g : Rn+m  R.
f(x) =

x1
f(x),

x2
f(x), . . . ,

xn
f(x)
T
xg(x, y) =

x1
g(x, y),

x2
g(x, y), . . . ,

xn
g(x, y)
T
|M| -- mohutnost množiny M. Je-li množina M konečná, je |M| počet jejích prvků.
Příklady:
(Ax)i =
n
j=1
aijxj = eiT
Ax
xT
y =
n
i=1
yixi skalární součin vektorů x a y
aij = (aj
)i = eiT
Aej
x < 1  (i  {1, 2, . . . , n}) xi < 1  (i  {1, 2, . . . , n}) eiT
x < 1
2
1.2 Některé pojmy a tvrzení z prerekvizitního předmětu M5171
Nechť f : Rn  R, g = (g1, g2, . . . , gm)T : Rn  Rm, s  {0, 1, 2, . . . , n}, k  {0, 1, 2, . . . , m}.
Položme
P = Rs
+ × Rn-s
= {x  Rn
: x1  0, x2  0, . . . , xs  0} ,
Q = Rk
+ × Rm-k
= {y  Rm
: y1  0, y2  0, . . . , yk  0} ,
1.2.1 Optimalizační úloha
Přípustná množina je definována jako
X = {x  P : gi(x)  0, i = 1, 2, . . . , k,
gi(x) = 0, i = k + 1, k + 2, . . . , m}.
Základní úloha je tvaru
f(x)  min, x  X.
f = inf {f(x) : x  X} se nazývá hodnota úlohy.
Pokud úloha má řešení x  X, pak f = f(x), v opačném případě je f = -.
1.2.2 Kuhnova-Tuckerova věta
Definice 1. Podmínky regularity:
* Slaterova: k = m (omezení jsou pouze ve tvaru nerovností), (x  P) g(x) < 0.
* Linearity: funkce g1, q2, . . . , gk jsou afinní (lineární).
Věta 1. Nechť
-- funkce f, g1, g2, . . . , gk jsou konvexní a diferencovatelné,
-- funkce gk+1, gk+2, . . . , gm jsou afinní (lineární),
-- je splněna aspoň jedna podmínka regularity.
Pro x  Rn, y  Rm položme
L(x, y) = f(x) +
m
i=1
yigi(x) = f(x) + yT
g(x).
Pak x  X je řešením základní úlohy právě tehdy, když existuje y  Q tak, že
(x  P) (x - x
)T
xL(x
, y
)  0, (1)
yT
g(x
) = 0. (2)
Poznámka 1. Pokud s = n, je podmínka (1) ekvivalentní s dvojicí podmínek
xL(x
, y
)  0, (3)
xT
xL(x
, y
) = 0, (4)
pokud s = 0, je podmínka (1) ekvivalentní s podmínkou
xL(x
, y
) = 0. (5)
3
1.2.3 Dualita
Nechť funkce  : Q  R  {-} je definována rovností
(y) = inf {L(x, y) : x  P} = inf f(x) + yT
g(x) : x  P .
Položme
Y = {y  Q : (y) > -} .
Platí: množina Y je konvexní, funkce  je konkávní.
Duální úloha k základní (primární) úloze je optimalizační úloha ve tvaru
(y)  max, y  Y.
 = sup {(y) : y  Y } se nazývá hodnota duální úlohy.
Věta 2. Nechť jsou splněny předpoklady Věty 1. Pokud f > -, pak f =  a množina
všech řešení duální úlohy je {y  Q : (x  P) L(x, y)  f}.
Stručně řečeno: Má-li jedna z úloh řešení, má řešení i druhá z nich a hodnoty obou úloh
jsou stejné.
2 Lineární programování
2.1 Dvě motivační úlohy
2.1.1 Výrobní problém
Představme si firmu, vyrábějící n druhů produktů, ke kterým potřebuje m zdrojů (surovin,
dodavatelů ap.). Označme
cj . . . cena jednotkového množství j-tého produktu,
bi . . . množství i-tého zdroje (zásobu suroviny, kapacitu dodavatele ap.),
aij . . . množství i-tého zdroje potřebného k výrobě jednotkového množství j-tého produktu,
xj . . . vyrobené množství j-tého produktu.
Cena celkové produkce tedy je
n
j=1
cjxj = cTx a celkové množství i-tého zdroje spotřebovaného
při výrobě je
n
j=1
aijxj = (Ax)i. Je třeba najít takové uspořádání výroby, tj. množství
jednotlivých druhů produktů, aby jejich cena byla maximální,
cT
x  max
při respektování daných omezení
(Ax)i  bi pro i = 1, 2, . . . , m, tedy Ax  b
(nelze spotřebovat více z každého zdroje, než kolik ho je) a
xj  0, pro j = 1, 2, . . . , n, tedy x  0
(nelze vyrábět méně než nulové množství každého z produktů).
4
2.1.2 Směšovací problém
Představme si, že z n surovin (např. druhů ropy), z nichž každá obsahuje některé (případně
všechny) z m různých složek (např. frakcí ropy). Z těchto surovin se má namíchat směs
požadovaného složení (např. lehký topný olej). Označme
cj . . . cena j-té suroviny,
bi . . . požadované množství i-té složky ve výsledné směsi,
aij . . . množství i-té složky v jednotkovém množství j-té suroviny,
xj . . . nakoupené množství j-té suroviny.
Celková cena nakoupených surovin tedy je
n
j=1
cjxj = cTx a celkové množství i-té složky ve
výsledné směsi je
n
j=1
aijxj = (Ax)i. Je třeba nakoupit taková množství surovin, aby jejich
cena byla nejmenší,
cT
x  min
a přitom ve výsledné směsi byla poždovaná množství jednotlivých složek,
(Ax)i = bi pro i = 1, 2, . . . , m, tedy Ax = b.
Na množství nakoupených surovin je kladeno omezení
xj  0, pro j = 1, 2, . . . , n, tedy x  0
(nelze nakoupit méně než nic).
2.2 Formulace úlohy lineárního programování
Nechť c  Rn, A  M(m, n), b  Rm, s  {0, 1, 2, . . . , n}, k  {0, 1, 2, . . . , m}. Položme
P = Rs
+ × Rn-s
= {x  Rn
: x1  0, x2  0, . . . , xs  0}
Úloha lineárního programování je optimalizační úloha ve tvaru
f(x) = cT
x  min, x  {x  P : (Ax)i  bi, i = 1, 2, . . . , k,
(Ax)j = bj, j = k + 1, k + 2, . . . , m}
Speciální případy:
s = n, k = 0 úloha v kanonickém tvaru,
cT
x  min Ax = b, x  0. (6)
s = n, k = m úloha ve standardním tvaru,
cT
x  min, Ax  b, x  0. (7)
5
s = 0, k = m úloha v základním tvaru,
cT
x  min, Ax  b. (8)
Tvrzení 1. Obecnou úlohu lineárního programování lze přepsat do základního tvaru.
Zavedeme pomocný neznámý vektor w  Rm-k a podmínky přepíšeme ve tvaru
(Ax)i  bi, i = 1, 2, . . . , k,
(Ax)k+j-wj  bk+j, j = 1, 2, . . . , m - k,
-x  0,  = 1, 2, . . . , s,
-wj  0, j = 1, 2, . . . , m - k.
To znamená, že při označení
~aij =



aij, i  m, j  n,
0, i  k, j > n,
-i-k,j-n, k < i  m, j > n,
-i-m,j, m < i  m + s,
-i-m-s,j-n, i > m + s,
~bi =
bi, i  m,
0, i > m
, ~cj =
cj, j  n,
0, j > n
, ~xj =
xj, i  n
wj-n, j > n
i = 1, 2, . . . , n + m + s - k, j = 1, 2, . . . , n + m - k
můžeme úlohu zapsat ve tvaru
~cT
~x  min, ~A~x  ~b.
Tvrzení 2. Úlohu s parametrem s = n lze přepsat do kanonického tvaru. Zejména tedy úlohu
ve standardním tvaru můžeme zapsat ve tvaru kanonickém.
Podobně jako v předchozím tvrzení zavedeme pomocný neznámý vektor w  Rm-k a
podmínky přepíšeme ve tvaru
(Ax)i + wi = bi, i = 1, 2, . . . , k,
(Ax)j = bj, j = k + 1, k + 2, . . . m,
x  0, w  0.
Takže při označení
~aij =



aij, i  m, j  n,
i,j-n, i  k, j > n,
0, i > k, j > n,
~cj =
cj, j  n,
0, j > n
, ~xj =
xj, i  n
wj-n, j > n
pro i = 1, 2, . . . , m, j = 1, 2, . . . , n + m - k můžeme úlohu zapsat ve tvaru
~cT
~x  min, ~A~x = b, ~x  0.
Úlohu ve standardním tvaru lze do tvaru kanonického přepsat ještě stručněji
cT
x  min, (A, E)
x
w
= b,
x
w
 0.
6
Tvrzení 3. Úloha duální k úloze v kanonickém tvaru je úloha v základním tvaru.
V tomto případě je
Q = Rm
,
L(x, y) = cT
x + yT
(b - Ax) = (cT
- yT
A)x + yT
b,
(y) = inf
xP
{L(x, y)} = inf
xRn
+
(cT
- yT
A)x + yT
b =
yTb, cT - yTA  0,
-, cT - yTA < 0.
Duální úloha tedy je
yT
b  max, AT
y  c. (9)
Z tvrzení 1, 2 a 3 plyne, že stačí vybudovat teorii pro úlohy v kanonickém tvaru. Libovolnou
úlohu totiž převedeme na základní tvar a k němu je úloha v kanonickém tvaru duální. Úlohu
v kanonickém tvaru vyřešíme a řešení úlohy v základním tvaru se redukuje na řešení systému
lineárních rovnic. Úlohu ve standardním tvaru převedeme na kanonický tvar přímo.
V dalším textu se tedy budeme zabývat úlohou v kanonickém tvaru
cT
x  min, Ax = b, x  0.
Bez újmy na obecnosti lze předpokládat, že
* b  0 (v opačném případě bychom řádky systému rovnic odpovídající záporným složkám
vynásobili číslem -1),
* m  n, h(A) = m (v opačném případě bychom ze systému rovnic eliminovali závislé
rovnice).
2.3 Ilustrační příklady
2.3.1 f(x1, x2, x3) = c1x1 + c2x2 + c3x3  min, x1+x2+x3 = 1,
2x2-x3 = 0,
x1  0, x2  0, x3  0,
tj.
n = 3, m = 2, s = 3, k = 0, c =


c1
c2
c3

 , b =
1
0
, A =
1 1 1
0 2 -1
.
Přípustné hodnoty jsou nezáporná řešení soustavy rovnic Ax = b, tj.
X = (1 - 3s, s, 2s) : 0  s 
1
3
,
takže účelová funkce na přípustné množině je
f(1 - 3s, s, 2s) = c1 + (-3c1 + c2 + 2c3) s.
7
To je funkce lineární, nabývá svých extrémních hodnot v krajních bodech intervalu, na němž
je definovaná. Tato funkce je rostoucí pro -3c1+c2+2c3 > 0 a klesající pro -3c1+c2+2c3 < 0.
Z této úvahy plyne, že řešení úlohy a její hodnota jsou
(x
1, x
2, x
3)



= (1, 0, 0), -3c1 + c2 + 2c3 > 0,
 X libovolný bod, -3c1 + c2 + 2c3 = 0,
= 0, 1
3, 2
3 , -3c1 + c2 + 2c3 < 0,
f
=
c1, -3c1 + c2 + 2c3  0,
1
3 (c2 + c3) , -3c1 + c2 + 2c3 < 0.
2.3.2 f(x1, x2, x3) = c1x1 + c2x2 + c3x3  min, x1 = 1,
-x2+x3 = 1,
x1  0, x2  0,x3  0,
tj.
n = 3, m = 2, s = 3, k = 0, c =


c1
c2
c3

 , b =
1
1
, A =
1 0 0
0 -1 1
.
Přípustné hodnoty jsou opět nezáporná řešení soustavy rovnic Ax = b, tj.
X = {(1, t, 1 + t) : t  0}
a účelová funkce na přípustné množině je
f(1, t, 1 + t) = c1 + c3 + (c2 + c3)t.
To je opět funkce lineární, která roste pro c2+c3 > 0 a klesá pro c2+c3 < 0. Poněvadž parametr
t může nabývat libovolně velké hodnoty, je účelová funkce, pokud klesá, zdola neomezená.
V takovém případě tedy úloha nemá řešení. V případě c2 + c3  0 řešení úlohy a její hodnota
jsou
(x
1, x
2, x
3)
= (1, 0, 1), c2 + c3 > 0,
 X libovolný bod , c2 + c3 = 0,
f
= c1 + c3.
2.4 Označení, definice, základní vlastnosti
Na ilustračních příkladech si všimneme následujících vlastností úlohy lineárního programování
v kanonickém tvaru:
* Pokud úloha má jednoznačné řešení, pak toto řešení je krajním bodem přípustné množiny
X. (Krajní bod konvexní množiny je ten, který není konvexní kombinací jiných
bodů této množiny.)
* Pokud úloha má více řešení, pak tato řešení jsou konvexní kombinací krajních bodů
přípustné množiny.
* Řešení úlohy, které je krajním bodem, má nejvýše m nenulových složek (v příkladech
dvě).
8
ˇ Sloupce matice A se slupcovými indexy odpovídajícími indexům nenulových složek krajních
bodů přípustné množiny jsou lineárně nezávislé. (V příkladu 2.3.1 odpovídá krajnímu
bodu (1, 0, 0) první sloupec
1
0
matice a krajnímu bodu (0, 1
3, 2
3 ) odpovídají
druhý
1
2
a třetí
1
-1
sloupec. V příkladu 2.3.2 odpovídají krajnímu bodu (1, 0, 1)
první
1
0
a třetí
0
1
sloupec matice.
Tato pozorování motivují zavedení následujících pojmů.
* Nosič vektoru x  P = R+ je množina suppx = {j  {1, 2, . . . , n} : xj > 0}.
* Množina basických přípustných bodů
B =



x  X :
jsupp x
jaj
= 0  (j  suppx)j = 0



.
Basický přípustný bod je tedy takový bod x  X, že sloupce matice A se sloupcovými indexy
shodujícími se s indexy nenulových složek vektoru x, tj. všechny vektory z množiny
aj : j  supp x jsou lineárně nezávislé. Poněvadž předpokládáme, že h(A) = m  n,
je nosič každého basického přípustného bodu nejvýše m-prvková množina.
* Indexová base basického přípustného bodu x  B je m-prvková podmnožina J (x) množiny
{1, 2, . . . , n} taková, že suppx  J (x) a množina aj : j  J (x) je množinou
lineárně nezávislých vektorů, tj.
suppx  J (x)  {1, 2, . . . , n}, |J (x)| = m,
jJ (x)
jaj
= 0  j  J (x) j = 0.
To také znamená, že množina aj : j  J (x) sloupců matice A tvoří bázi vektorového
prostoru Rm. Z předpokladu h(A) = m plyne, že indexová base každého basického
přípustného bodu existuje; nemusí být ovšem určena jednoznačně.
Base basického přípustného bodu x  B je množina
B(x) = {xj : j  J (x)} .
* Basický přípustný bod x  B je nedegenerovaný, pokud supp x = J (x). Úloha je
nedegenerovaná, pokud každý basický přípustný bod je nedegenerovaný, tj.
(x  B) supp x = J (x) .
* Basické přípustné body x1, x2 nazveme sousední, pokud existují jejich base J (x1) a
J (x2) takové, že množina J (x1)  J (x2) je (m - 1)-prvková, tj. base bodů x1 a x2
se od sebe liší v jediném prvku.
Degenerovaný basický přípustný bod je sousední sám se sebou.
9
Ilustrace: V příkladu 2.3.1 je
B = (1, 0, 0), (0,
1
3
,
2
3
) , supp(0,
1
3
,
2
3
) = {2, 3} = J (0,
1
3
,
2
3
) ,
supp(1, 0, 0) = {1} , J ((1, 0, 0)) = {1, 2} nebo J ((1, 0, 0)) = {1, 3} ,
basický přípustný bod (0, 1
3 , 2
3) je nedegenerovaný, bod (1, 0, 0) je degenerovaný a tyto body
jsou sousední.
V příkladu 2.3.2 je B = {(1, 0, 1)}, supp(1, 0, 1) = {1, 3} = J ((1, 0, 1)) a basický přípustný
bod (1, 0, 1) je nedegenerovaný.
Věta 3. Bod x je basický přípustný právě tehdy, když je krajním bodem množiny X.
Věta 4. Je-li přípustná množina X neprázdná, pak množina basických přípustných bodů je
konečná a ke každému přípustnému bodu x  X existuje basický přípustný bod x  B takový,
že supp x  supp x. Zejména tedy množina basických přípustných bodů je neprázdná.
Věta 5. Pokud má úloha (6) řešení, pak je toto řešení basickým přípustným bodem.
Z vět 3, 4 a 5 plyne jednoduchý návod, jak řešit úlohu (6):
1. Najdeme všechny basické přípustné body, tj. najdeme nezávislá řešení systému lineárních
rovnic Ax = b. Je jich konečně mnoho.
2. Vypočítáme hodnotu účelové funkce cTx pro každý basický přípustný bod x.
3. Najdeme mezi nimi nejmenší hodnotu.
Pokud má úloha řešení, vede tento postup k jeho nalezení. Avšak pokud je úloha neřešitelná
a množina basických přípustných bodů je neprázdná, dojdeme uvedeným postupem k bodu,
který není řešením (v příkladu 2.3.2 v případě c2 + c3 < 0 vybere dokonce bod maxima
účelové funkce). I u řešitelných úloh by však použití tohoto postupu u ,,velkých úloh bylo
příliš zdlouhavé. Proto byla vyvinuta metoda efektivnější.
Před jejím uvedením se však zmíníme o řešení úlohy (9) duální k primární úloze (6)
v kanonickém tvaru.
Věta 6. Nechť Ax = b.
* Vektor x je řešením (primární) úlohy (6) v kanonickém tvaru a vektor y je řešením
duální úlohy (9) právě tehdy, když (ATy - c)Tx = 0.
* Pokud
(j  J (x
)) yT
aj
= cj,
(j  {1, 2, . . . , n} J (x
)) yT
aj
 cj
pak y je řešením duální úlohy (9).
Důkaz: První tvrzení je ekvivalentní s rovností cTx = yT
b a za předpokladu Ax = b
jsou následující úpravy také ekvivalentní
cT
x
= yT
b,
cT
x
= yT
Ax
,
0 = (AT
y
- c)T
x
.
10
Druhé tvrzení plyne z prvního, neboť
AT
y
- c
T
x
=
n
j=1
(AT
y
)j - cj x
j =
jJ (x)
(AT
y
)j - cj x
j =
=
jJ (x)
n
i=1
aijy
i - cj x
j =
jJ (x)
(aj
)T
y
- cj x
j = 0.
2.5 Simplexová metoda
2.5.1 Jeden krok simplexové metody
Simplexová metoda je algoritmus, který pro basický přípustný bod rozhodne, zda se v něm
realizuje řešení úlohy. Pokud nikoliv, rozhodne zda řešení neexistuje a v opačném případě
najde sousední basický přípustný bod, v němž je hodnota účelové funkce menší.
Nechť x  B. Sloupce aj : j  J (x) matice A tvoří bázi vektorového prostoru Rm.
Libovolný sloupec matice tedy lze vyjádřit jako lineární kombinaci sloupců matice A z množiny
aj : j  J (x) , tj.
ap
=
jJ (x)
jpaj
, p = 1, 2, . . . , n. (10)
Pro p  {1, 2, . . . , n} nyní položíme
p =
jJ (x)
jpcj - cp. (11)
Je zřejmé, že pro p  J (x) je jp = jp a tedy
p =
jJ (x)
jpcj - cp =
jJ (x)
jpcj - cp = cp - cp = 0.
Ilustrace: V příkladu 2.3.1 vezmeme x = (0, 1
3 , 2
3)  B. Pak je J (x) = {2, 3} a
1
0
=
1
3
1
2
+
2
3
1
-1
,
tedy a1 = 1
3a2 + 2
3a3 a 1 = 1
3c2 + 2
3c3 - c1. Celkem máme
21 = 1
3 22 = 1 23 = 0 x2 = 1
3
31 = 2
3 32 = 0 33 = 1 x3 = 2
3
1 = 1
3(-3c1 + c2 + 2c3) 2 = 0 3 = 0 f(x) = 1
3(c2 + 2c3)
(12)
V příkladu 2.3.2 je B = {(1, 0, 1)}, vezmeme tedy x = (1, 0, 1). Pak je J (x) = {1, 3} a
0
-1
= -
0
-1
,
11
tedy a2 = 0a1 + (-1)a3 a 2 = -c3 - c2. Celkem máme
21 = 1 22 = 0 23 = 0 x1 = 1
31 = 0 32 = -1 33 = 1 x3 = 1
1 = 0 2 = -(c2 + c3) 3 = 0 f(x) = c1 + c2
(13)
Věta 7. Buď x  B. Nechť čísla jp, j  J (x), p  {1, 2, . . . , n} jsou definována vztahy (10)
a čísla p, p  {1, 2, . . . , n} jsou definována vztahy (11). Mohou nastat případy
(i) p  {1, 2, . . . , n} p  0,
(ii) p  {1, 2, . . . , n} p > 0.
Pokud nastane případ (i), je bod x řešením úlohy (6).
Nechť nastane případ (ii). Položíme q  {1, 2, . . . , n} takové, že
q = max {p : p > 0, p = 1, 2, . . . , n} > 0.
Pak je q  J (x) a opět mohou nastat dva případy
(ii1) j  J (x) jq  0,
(ii2) j  J (x) jq > 0.
Pokud nastane případ (ii1), úloha (6) nemá řešení.
Nechť nastane případ (ii2). Položíme
 = min
xj
jq
: j  J (x) , jq > 0
a r  J (x) takové, že
xr
rq
= . Pak bod ~x  Rn definovaný rovnostmi
~xj =



xj - jq, j  J (x) ,
, j = q,
0, j  J (x)  {q}.
je basický přípustný bod sousední s bodem x, J (~x) = J (x) {r}  {q} a platí pro něho
f(~x) = cT
~x  cT
x = f(x);
pokud je basický přípustný bod nedegenerovaný, je tato nerovnost ostrá.
S ,,novým basickým přípustným bodem ~x můžeme provádět stejné operace, jako se ,,starým
basickým přípustným bodem x, tedy libovolný sloupec matice A vyjádřit jako lineární
kombinaci sloupců z množiny aj : j  J (~x) a vypočítat příslušné hodnoty ~,
ap
=
jJ (~x)
~jpaj
, ~p =
jJ (~x)
~jpcj - cp, p = 1, 2, . . . , n.
12
Podle věty 7 rozhodneme, zda basický přípustný bod ~x je řešením úlohy (6), zda řešení neexistuje,
nebo přejdeme do sousedního basického přípustného bodu, v němž je hodnota účelové
funkce menší. Pokud je úloha nedegenerovaná, po konečném počtu kroků takto dojdeme k řešení
úlohy.
V případě degenerovaného basického přípustného bodu x může dojít k zacyklení, metoda
pouze vybírá různé base bodu x. Pravděpodobnost, že k tomuto jevu dojde v praktických
úlohách je však nulová (což ovšem neznamená, že se jedná o jev nemožný).
Ilustrace: Případy (i) je ilustrován tabulkou (12) s vektorem c, jehož složky splňují
nerovnost -3c1+c2+2c3 < 0. Případ (ii1) je ilustrován tabulkou (13) s parametry vyhovujícími
nerovnosti c1 + c2 < 0.
Uvažujme příklad 2.3.1 s vektorem c splňujícím nerovnost -3c1 + c2 + 2c3 > 0. Hodnoty
koeficientů jp a veličin p pro basický přípustný bod (0, 1
3, 2
3) jsou v tabulce (12). V tomto
případě je q = 1 a obě hodnoty 2q = 21 = 1
3, 3q = 31 = 2
3 jsou kladné. Nastává tedy
možnost (ii2). Dále je
x2
21
=
1
3
1
3
= 1,
x3
31
=
2
3
2
3
= 1,
takže  = 1. Index r není určen jednoznačně, zvolíme r = 2. Bod ~x má souřadnice
~x1 = ~xq = 1, ~x2 = x2 - 21 = 0, ~x3 = x3 - 31 = 0.
Bod ~x = (1, 0, 0) je skutečně basický přípustný bod sousední s bodem x. Za jeho indexovou
basi považujeme množinu J (~x) = {1, 2}. Pro basický přípustný bod (1, 0, 0) s uvedenou basí
určíme koeficienty ~jp a hodnoty ~p. Platí
1
-1
=
3
2
1
0
-
1
2
1
2
,
tedy a3 = 3
2a1 - 1
2a2, takže ~13 = 3
2, ~23 = -1
2, ~3 = 3
2c1 - 1
2 c2 - c3. Celkem máme
~11 = 1 ~12 = 0 ~13 = 3
2 ~x1 = 1
~21 = 0 ~22 = 1 ~23 = -1
2 ~x2 = 0
~1 = 0 ~2 = 0 ~3 = -1
2(-3c1 + c2 + 2c3) f(~x) = c1
(14)
Nastává tedy případ (i) z věty 7 a bod (1, 0, 0) je řešením úlohy 2.3.1 s parametry splňujícími
nerovnost -3c1 + c2 + 2c3 > 0.
Tabulky (12) a (14) zapíšeme ve formě matic:
S =



1
3 1 0 1
3
2
3 0 1 2
3
1
3(-3c1 + c2 + 2c3) 0 0 1
3(c2 + 2c3)


 , ~S =



1 0 3
2 1
0 1 -1
2 0
0 0 -1
2(-3c1 + c2 + 2c3) c1



Vidíme, že
~S =



0 3
2 0
1 -1
2 0
1
2(-3c1 + c2 + 2c3) 0 1


 S.
První řádek matice ~S je 3
2-násobkem druhého řádku matice S, druhý řádek matice ~S je prvním
řádkem matice S zmenšeným o polovinu druhého řádku matice S, třetí řádek matice ~S je roven
třetímu řádku matice S zvětšenému o polovinu prvního řádku matice S násobenému výrazem
-3c1 + c2 + 2c3. Jinak řečeno, od matice S lze k matici S přejít Gaussovou eliminací.
13
2.5.2 Simplexová tabulka
Simplexová tabulka slouží k přehlednému zápisu výpočtů s basickým přípustným bodem x a
jeho indexovou basí J (x) = {j1, j2, . . . , jm}. Má n + 2 sloupců a m + 1 řádků a je doplněna
záhlavím a označením sloupců. První sloupec je pomocný, v prvních m řádcích posledního
sloupce jsou j1 až jm-tá souřadnice basického přípustného bodu x (odpovídající indexům
z base), ve druhém až n + 1-ním sloupci jk-tého řádku jsou koeficienty jkp, na posledním
řádku ve druhém až n + 1-ním sloupci jsou veličiny p, p = 1, 2, . . . , n. V posledním sloupci
na posledním řádku je hodnota účelové funkce v basickém přípustném bodě x.
z x1 x2 . . . xn
xj1 0 j11 j12 . . . j1n (x)j1
xj2 0 j21 j22 . . . j2n (x)j2
...
...
...
...
...
...
...
xjm 0 jm1 jm2 . . . jmn (x)jm
z 1 1 2 . . . n f(x)
Je-li jk  J (x), pak z definice hodnot jkp a p plyne, že ve sloupci označeném xjp jsou samé
nuly s výjimkou řádku označeného stejně, ve kterém je jednička. V prvním sloupci označeném
z jsou nuly s výjimkou posledního řádku označeného stejně, kde je jednička.
Postup výpočtu:
* Pokud jsou všechny prvky v posledním řádku ve druhém až předposledním sloupci
nekladné, je basický přípustný bod x řešením úlohy (6) a hodnota této úlohy je na
poslední pozici posledního řádku.
* Pokud se v posledním řádku ve druhém až předposledním sloupci vyskytuje kladná
hodnota, vybereme sloupec, v němž je tato hodnota největší. Tento sloupec nazveme
klíčový sloupec. (Při označení z věty 7 se jedná o sloupec nadepsaný xq.)
* Mezi prvními m řádky najdeme všechny takové, že v tomto řádku a klíčovém sloupci je
kladná hodnota. Pokud takový řádek neexistuje, úloha nemá řešení. V opačném případě
pro takové řádky vypočítáme podíl hodnoty v posledním sloupci a hodnoty v klíčovém
sloupci (tyto podíly můžeme zapsat do přidaného dalšího sloupce tabulky) a najdeme
mezi nimi nejmenší hodnotu. Řádek, v němž se tento minimální podíl nachází, nazveme
klíčový řádek. (Při označení z věty 7 se jedná o řádek označený xr.) Prvek na průsečíku
klíčového řádku a klíčového sloupce nazveme klíčový prvek.
* Tabulku upravíme: Klíčový řádek označíme symbolem ze záhlaví klíčového sloupce.
Hodnoty v klíčovém řádku vydělíme hodnotou klíčového prvku. Od každého dalšího
řádku odečteme takto upravený klíčový řádek násobený hodnotou v klíčovém sloupci
upravovaného řádku.
* Upravená tabulka by měla mít stejnou vlastnost jako tabulka výchozí, tj. ve sloupci označeném
xjp jsou samá nuly s výjimkou řádku označeného stejně, ve kterém je jednička,
a v prvním sloupci označeném z jsou nuly s výjimkou posledního řádku označeného
stejně, kde je jednička. Ověření, že tabulka má skutečně tento tvar slouží ke kontrole
výpočtu.
14
Ilustrace: Provedeme úpravu simplexové tabulky pro úlohu 2.3.1 s basickým přípustným
bodem (0, 1
3, 2
3) a vektorem c = (1, 2, 3)T. Klíčový prvek je při výpočtu označen zarámováním.
z x1 x2 x3
x2 0 1
3 1 0 1
3 1
x3 0 2
3 0 1 2
3 1
z 1 1
3 0 0 4
3
x1 0 1 3 0 1
x3 0 0 -2 1 0
z 1 0 -1 0 1
Dostali jsme řešení úlohy x = (1, 0, 0), jeho indexová base je {1, 3} a hodnota úlohy je f = 1.
2.5.3 Volba počátečního basického přípustného bodu
Dosavadní popis simplexové metody se věnoval rozhodnutí, zda jistý basický přípustný bod
je řešením úlohy a pokud ne, zda úloha řešení má. V případě, že úloha je řešitelná a zvolený
basický bod nebyl řešením, metoda nalezla sousední basický přípustný bod, v němž hodnota
účelové funkce nebyla větší. Zbývá popsat ,,nastartování metody.
Samozřejmě, že je možné najít jedno nezáporné řešení soustavy rovnic Ax = b a k němu
spočítat hodnoty jp a p, p = 1, 2, . . . , n. Rychlejší ale je tzv. metoda umělé báze.
Uvažujme úlohu
m
i=1
wi  min, Ax + w = b, x  0, w  0, (15)
neboli
f(x, w) = (oT
, 1T
)
x
w
 min, (A, E)
x
w
= b.
Účelová funkce f(x, w) je zdola omezená nulou. To znamená, že řešení (x^, w^) této úlohy
existuje. Pokud f(x^, w^) = 0, pak J ((x^, w^))  {n + 1, n + 2, . . . , n + m} =  a bod x^je
basickým přípustným bodem původní úlohy (6). Pokud f(x^, w^) > 0, nemá původní úloha
řešení.
Poněvadž sloupce jednotkové matice E jsou lineárně nezávislé a stále předpokládáme, že
b  0, je bod (o, b) basickým přípustným bodem úlohy (15) a
J ((o, b)) = {n + 1, n + 2, . . . , n + m}.
Označme
~A = (A, E), ~c =
o
1
.
Platí
~ap
= ep-n
, p = n + 1, n + 2, . . . , n + m,
~ap
= ap
=
m
j=1
ajpej
=
n+m
j=n+1
aj-n,p~aj
, p = 1, 2, . . . , n,
15
takže
p = 0, p = n + 1, n + 2, . . . , n + m,
p =
n+m
j=n+1
aj-n,p - 0 =
m
j=1
ajp, p = 1, 2, . . . , n,
f(o, b) = ~c
o
b
= (oT
, 1T
)
o
b
=
m
j=1
bj.
Spolu s úlohou (15) budeme uvažovat rovnici
z - cT
x = 0;
proměnná z vyjadřuje hodnotu účelové funkce původní úlohy (6). Řádek odpovídající této
rovnici zapíšeme do simplexové tabulky řešené úlohy. Budeme tedy upravovat tabulku
wi z x1 x2 . . . xn w1 w2 . . . wm
w1 0 0 a11 a12 . . . a1n 1 0 . . . 0 b1
w2 0 0 a21 a22 . . . a2n 0 1 . . . 0 b2
...
...
...
...
...
...
...
...
...
...
...
...
wm 0 0 am1 am2 . . . amn 0 0 . . . 1 bm
z 0 1 -c1 -c2 . . . -cn 0 0 . . . 0 0
wi 1 0
m
j=1
aj1
m
j=1
aj2 . . .
m
j=1
ajn 0 0 . . . 0
m
j=1
bj
Při úpravách této simplexové tabulky vybíráme klíčový řádek pouze z prvních m řádků tabulky.
Po nalezení minima účelové funkce pomocné úlohy pokračujeme s upravenou simplexovou
tabulkou, ve které vynecháme poslední řádek a sloupce označené wi, w1, w2, . . . wn.
Ilustrace: Vyřešíme úlohu 2.3.1 s vektorem c = (1, 2, 3)T simplexovou metodou. Klíčový
prvek je označen zarámováním.
wi z x1 x2 x3 w1 w2
w1 0 0 1 1 1 1 0 1 1
w2 0 0 0 2 -1 0 1 0 0
z 0 1 -1 -2 -3 0 0 0
wi 1 0 1 3 0 0 0 1
w1 0 0 1 0 3
2 1 -1
2 1
x2 0 0 0 1 -1
2 0 1
2 0
z 0 1 -1 0 -4 0 1 0
wi 1 0 1 0 3
2 0 -3 1
x3 0 0 2
3 0 1 2
3 -1
3
2
3
x2 0 0 1
3 1 0 1
3
1
3
1
3
z 0 1 5
3 0 0 8
3 -1
3
8
3
wi 1 0 0 0 0 -1 -1 0
16
Pomocná uloha tedy má řešení w1 = w2 = 0. Počáteční basické řešení původní úlohy je
(0, 1
3, 2
3). Budeme pokračovat úpravou simplexové tabulky, která vznikne ze získané výsledné
tabulky vynecháním sloupců označených wi, w1, w2 a řádku označeného wi.
z x1 x2 x3
x3 0 2
3 0 1 2
3 1
x2 0 1
3 1 0 1
3 1
z 1 5
3 0 0 8
3
x1 0 1 0 3
2 1
x2 0 0 1 -1
2 0
z 1 0 0 -5
2 1
Dostali jsme opět řešení (1, 0, 0), za jeho indexovou basi tentokrát považujeme množinu {1, 2}.
3 Lineární lomené a hyperbolické programování
3.1 Motivační úloha
3.1.1 Optimální poměr zisku a nákladů
Uvažujme výrobní problém 2.1.1. Výroba každého z produktů může mít své náklady. Označme
proto dj náklady na výrobu jednotkového množství j-tého produktu. Celkové náklady na
produkci pak jsou
n
j=1
djxj = dT
x.
Hledáme optimální poměr ceny produkce a nákladů na ni při daných omezeních, tedy řešíme
úlohu
f(x) =
cTx
dT
x
 max, Ax  b, x  0.
3.2 Formulace úloh
Nechť c, d  Rn, A  M(m, n), b  Rm, s  {0, 1, 2, . . . , n}, k  {0, 1, 2, . . . , m}. Položme
P = Rs
+ × Rn-s
= {x  Rn
: x1  0, x2  0, . . . , xs  0}
Úloha lineárního lomeného programování je optimalizační úloha ve tvaru
f(x) =
cTx
dT
x
 min, x  X = {x  P : (Ax)i  bi, i = 1, 2, . . . , k,
(Ax)j = bj, j = k + 1, k + 2, . . . , m}
Budeme předpokládat, že funkce f je definována pro každé přípustné x  X. To znamená,
že výraz dT
x nemění na přípustné množině X znaménko. Bez újmy na obecnosti můžeme
předpokládat, že dT
x > 0 pro každé přípustné x  X.
17
Nechť dále C : X  R je spojitá funkce. Úloha hyperbolického programování je optimalizační
úloha tvaru
f(x) =
C(x)
dT
x
 min, x  X = {x  P : (Ax)i  bi, i = 1, 2, . . . , k,
(Ax)j = bj, i = k + 1, k + 2, . . . , m}
3.3 Transformace úlohy
Definujme zobrazení h : X  Rn+1 takto
z = h(x); zj = h(x) j
=
xj
dT
x
pro j = 1, 2, . . . , n, zn+1 = h(x) n+1
=
1
dT
x
. (16)
Pak platí
xj  0  zj  0 pro j = 1, 2, . . . , n,
zn+1 > 0,
n
j=1
djzj =
n
j=1
dj
xj
dT
x
=
dT
x
dT
x
= 1,
n
j=1
aijzj - bizn+1 =
n
j=1
aij
xj
dT
x
- bi
xn+1
dT
x
=
1
dT
x


n
j=1
aijxj - bi

 =
1
dT
x
(Ax - b)i ,
Označme nyní
R = z  Rn+1
: z1  0, z2  0, . . . , zs  0, zn+1  0 ,
~A =
A -b
dT
0
, ~c =
c
0
, ~b = (0, 0, . . . , 0
n krát
, 1)T
. (17)
Z předchozích výpočtů plyne, že zobrazení h zobrazuje přípustnou množinu X úlohy lineárního
lomeného (hyperbolického) programování na množinu
Z = {z  R : (~Az)i  0, i = 1, 2, . . . , k,
(~Az)j = 0, j = k + 1, k + 2, . . . , m, (18)
(~Az)m+1 = 1}.
Věta 8. Nechť ve formulaci úlohy lineárního lomeného programování je s = n, k = 0, tj.
přípustná množina úlohy je X = {x  Rn
+ : Ax = b}. Je-li množina X omezená, pak
zobrazení h : X  Rn+1 definované vztahy (16) je bijekcí přípustné množiny X na množinu Z
definovanou vztahem (18). Inverzní zobrazení h-1
: Z  X je dáno vztahem
x = h-1
(z) =
z1
zn+1
,
z2
zn+1
, . . . ,
zn
zn+1
T
, tj. xj =
zj
zn+1
. (19)
18
Důkaz: Snadno nahlédneme, že pro každý vektor z  Rn+1, který splňuje rovnost
A -b
dT
0
z =
o
1
,
platí zn+1 = 0. V takovém případě totiž je
A





z1
z2
...
zn





= o
a z omezenosti množiny {x  Rn
+ : Ax = b} plyne z1 = z2 =    = zn = 0. Kdyby zn+1 = 0,
pak by také (dT
, 0)z = 0 = 1, což by byl spor.
Důsledek: Nechť jsou splněny předpoklady předchozí věty, matice ~A a vektory ~b, ~c jsou
dány vztahy (17) a zobrazení h je definováno vztahy (16). Je-li z řešením úlohy lineárního
programování
~cT
z  min, ~Az = ~b, z  0,
pak x = h-1
(z) je řešením úlohy lineárního lomeného programování s hodnotami s = n,
k = 0.
Důkaz: Tvrzení plyne z výpočtu
~cT
z =
n+1
j=1
~cjzj =
n
j=1
cjzj + 0zn+1 =
n
j=1
cjzj =
n
j=1
cj
xj
dT
x
=
cTx
dT
x
.
Příklad:
x1 + x2
2x1 + x2
 min, x1 + 3x2 = 5, x1  0, x2  0.
V tomto případě je
c =
1
1
, d =
2
1
, A = 1 3 , b = 5,
takže
R = R3
+, ~A =
1 3 -5
2 1 0
, ~c =


1
1
0

 , ~b =
0
1
.
Řešíme tedy úlohu lineárního programování
z1 + z2  min, z1 + 3z2 - 5z3 = 0,
2z1 + z2 = 1,
z1  0, z2  0, z3 0.
19
Věta 9. Nechť funkce C : X  R je konvexní a dvakrát diferencovatelná, funkce
f(x) =
C(x)
dT
x
je účelovou funkcí úlohy hyperbolického programování a zobrazení h : X  Rn+1 dané vztahem
(16) je prosté (takže existuje zobrazení h-1
k němu inverzní a je definováno rovnostmi
(19)). Pak funkce g : h(X)  R definovaná vztahem
g(z) = f h-1
(z) = zn+1C
z1
zn+1
,
z2
zn+1
, . . . ,
zn
zn+1
je konvexní.
Důkaz: Buď z  Rn+1 libovolný a x = h-1
(z) =
z1
zn+1
,
z2
zn+1
, . . . ,
zn
zn+1
T
. Pak
x
zj
=
j
zn+1
= jdT
x,
x
zn+1
= -
z
z2
n+1
= -
x
zn+1
= -dT
x x, , j = 1, 2, . . . , n.
Při výpočtu derivací složené funkce g budeme pro stručnost používat označení typu:

|i(y) . . . parciální derivace funkce  podle i-té proměnné v bodě y,

|i,j(y) . . . druhá parciální derivace funkce  podle i-té a podle j-té proměnné v bodě y,
(y) . . . matice druhých parciálních derivací funkce  v bodě y.
Dostáváme
g(z)
zi
= zn+1
n
=1
C
|(x)
x
zi
= C
|i(x), i = 1, 2, . . . , n,
g(z)
zn+1
= C(x) + zn+1
n
=1
C
|(x)
x
zn+1
= C(x) -
n
=1
xC
|(x),
2g(z)
zizj
=
n
=1
C
|i,(x)
x
zj
= dT
xC
|i,j(x), i, j = 1, 2, . . . , n,
2g(z)
zizn+1
=
n
=1
C
|i,(x)
x
zn+1
= -dT
x
n
=1
xC
|i,(x) = -dT
x C
(x)x i
, i = 1, 2, . . . , n,
2g(z)
z2
n+1
=
n
=1
C
|
x
zn+1
-
n
=1

 x
zn+1
C
|(x) + x
n
p=1
C
|,p(x)
xp
zn+1

 =
= -dT
x


n
=1
xC
(x) -
n
=1

xC
|(x) + x
n
p=1
xpC
|,p(x)



 =
= dT
x
n
=1
n
p=1
xC
|,p(x)xp = dT
x xT
C
(x)x,
20
tedy
g
(z) = dT
x
C(x) -C(x)x
-xTC(x) xTC(x)x
.
Pro libovolný vektor (v, vn+1)  Rn+1 platí
vT vn+1 g
(z)
v
vn+1
= dT
x vT vn+1
C(x) -C(x)x
-xTC(x) xTC(x)x
v
vn+1
=
= dT
x vT vn+1
C(x)v - C(x)(vn+1x)
-xTC(x)v + xTC(x)(vn+1x)
=
= dT
x vT
C
(x)v - vT
C
(x)(vn+1x) - (vn+1x)T
C
(x)v + (vn+1x)T
C
(x)(vn+1x) =
= dT
x vT
C
(x)v(v - vn+1x) - (vn+1x)T
C
(x)(v - vn+1x) =
= dT
x(v - vn+1x)T
C
(x)(v - vn+1x)  0,
neboť matice C(x) je pozitivně semidefinitní. To znamená, že také matice g(z) je pozitivně
semidefinitní a funkce g je na množině h(X) konvexní.
Z vět 8 a 9 dostáváme
Důsledek: Nechť množina X = x  Rn
+ : Ax = b , je omezená, funkce C : X  R je
konvexní a dvakrát spojitě diferencovatelná a h : X  Rn+1 je zobrazení definované vztahy
(16). Pak úloha hyperbolického programování
f(x) =
C(x)
dT
x
 min, Ax = b, x  0 (20)
je ekvivalentní s úlohou konvexního programování
g(z) = f h-1
(z)  min,
A -b
dT
0
z =
o
1
, z  0, (21)
tj. x je řešením úlohy (20) právě tehdy, když z = h(x) je řešením úlohy (21).
4 Separovatelné úlohy
4.1 Motivační úlohy
4.1.1 Modifikovaný výrobní problém
Ve výrobním problému 2.1.1 nebyl úplně realistický předpoklad, že cena produktu nezávisí na
produkci. Zvětšení výroby totiž znamená zvýšení nabídky a následný pokles ceny. V modelu
tedy budeme předpokládat, že cena ci(xi) jednotkového množství i-tého produktu je klesající
funkcí celkového vyrobeného množství. Za tohoto předpokladu vede hledání výrobního
programu maximalizujícího cenu produkce na řešení úlohy
f(x) =
n
i=1
xici(xi)  max
při omezeních
Ax  b, x  0.
21
Pokud cena klesá s rostoucí produkcí lineárně, tj.
ci(xi) = Pi0 1 -
1
Li
xi ,
kde Pi0, Li, i = 1, 2, . . . , n jsou kladné konstanty, dostaneme úlohu kvadratického programo-
vání
n
i=1
Pi0xi -
Pi0
Li
x2
i  max;
zejména všechny funkce ci(xi) = Pi0xi -
Pi0
Li
x2
i jsou konvexní. Řešení má smysl uvažovat
pouze pro 0  xi  Li, i = 1, 2, . . . , n.
4.1.2 Problém pevných nákladů
U modifikovaného výrobním problému 4.1.1 budeme dále předpokládat, že s výrobou i-tého
produktu jsou spojeny fixní náklady pi  0. Čistý zisk za i-tý výrobek vyprodukovaný v množství
xi tedy bude dán nespojitou funkcí
fi(xi) =
0, xi = 0,
xici(xi) - pi, xi > 0.
Hledání optimálního výrobního programu, tj. takového, který maximalizuje celkový čistý zisk,
je řešením úlohy
n
i=1
fi(xi)  max
při omezeních
Ax  b, x  0.
4.1.3 Optimalizace užitku
Uvažujme i druhů zboží (může jít o nějaké výrobky, služby, kulturní statky a podobně). Cena
jednotkového množství zboží i-tého druhu je ai, spotřebitel má k dispozici částku b a chce
maximalizovat svůj užitek z nákupu.
Nechť i-tý druh zboží je v ,,portfoliu v množství xi. Celkový užitek označíme
U(x1, x2, . . . , xn) = U(x).
Funkce užitku U je definována na Rn
+, je nezáporná a je rozumné o ní předpokládat, že má
následující vlastnosti:
* Funkce U je homogenní prvního řádu, tj. pro každé   R platí
U(x) = U(x) neboli U(x1, x2, . . . , xn) = U(x1, x2, . . . , xn).
(Zhruba řečeno, pokud spotřebitel bude mít každého z druhů zboží dvojnásobek, zdvojnásobí
se i jeho užitek.) Důsledkem homogenity je vlastnost U(o) = 0. (Není-li žádné
zboží, není ani užitek.)
22
ˇ Pro každé i  {1, 2, . . . , n} je funkce U(x1, x2, . . . , xi-1,  , xi+1, xi+2, . . . , xn) neklesající,
tj. funkce užitku je neklesající v každé z proměnných. (S rostoucím množstvím zboží
jeho užitek neklesá.)
* Pro každé i  {1, 2, . . . , n} je funkce U(x1, x2, . . . , xi-1,  , xi+1, xi+2, . . . , xn) konkávní.
(Zhruba řečeno, při nadbytku nějakého zboží jeho užitečnost s rostoucím množstvím
příliš neroste. Pokud nějaké zboží chybí, s jeho objevením velice vzroste užitek.)
Často používanou funkcí užitku je funkce Cobbova-Douglasova
U(x1, x2, . . . , xn) = Bx1
1 x2
2    xn
n ,
kde B > 0, 1  0, 2  0, . . . , n  0,
n
i=1
i = 1. Maximalizovat užitek vyjádřený touto
funkcí znamená řešit úlohu
Bx1
1 x2
2    xn
n  max,
při omezení
aT
x  b, x  0.
Tato úloha je ekvivalentní s úlohou
n
i=1
i ln(xi)  max, aT
x  b, x  0.
4.2 Aproximace separovatelné úlohy úlohou lineárního programování
Nechť Ki,0, Li jsou reálná čísla taková, že Ki,0 < Li pro i = 1, 2, . . . , n a nechť funkce fi, gij
jsou definovány a spojité na intervalu [Ki,0, Li], i = 1, 2, . . . , n, j = 1, 2 . . . , m. Řešíme úlohu
f(x) =
n
i=1
fi(xi)  min (22)
při omezeních
x  X = x  [K1,0, L1] × [K2,0, L2] ×    × [Kn,0, Ln] :
n
i=1
gij(xi)  0, j = 1, 2, . . . , m
(23)
Poněvadž přípustná množina je kompaktní, má tato úloha řešení.
Každý z intervalů [Ki,0, Li] rozdělíme pi dělícími body Ki,1, Ki,2, . . . , Ki,pi na pi + 1 subintervalů.
Při označení Ki,pi+1 = Li tedy máme
Ki,0 < Ki,1 < Ki,2 <    < Ki,pi < Ki,pi+1 = Li,
viz obr. 1. Položme
si =
fi(Ki,+1) - fi(Ki,)
Ki,+1 - Ki,
, i = 1, 2, . . . , n,  = 0, 1, 2, . . . , pi,
rij =
gij(Ki,+1) - gij(Ki,)
Ki,+1 - Ki,
, i = 1, 2, . . . , n, j = 1, 2 . . . , m,  = 0, 1, 2, . . . , pi;
23
fi
xiKi,0 Ki,1 Ki,2 . . . . . . Ki,q Ki,q+1 . . . Ki,pi Li
Obrázek 1: Dělení přípustného definičního intervalu funkce fi. Povšimněme si, že graf funkce
fi na subintervalu [Ki,q, Ki,q+1] téměř splývá s její lineární aproximaxí.
veličina si aproximuje derivaci funkce fi na intervalu [Ki,, Ki,+1], veličina rij aproximuje
derivaci funkce gij na stejném intervalu.
Nechť xi  [Ki,q, Ki,q+1) pro nějaké q  {1, 2, . . . , pi}. Zavedeme proměnné
xi, =



Ki,+1 - Ki,,  = 0, 1, . . . , q - 1,
xi - Ki,q,  = q,
0,  = q + 1, q + 2, . . . , pi.
Pak
fi(xi)  fi(Ki,q) + siq(xi - Ki,q) =
q
=0
fi(Ki,) -
q-1
=0
fi(Ki,) + siqxi,q =
= fi(Ki,0) +
q-1
=0
fi(Ki,+1) - fi(Ki,) + siqxi,q = fi(Ki,0) +
q-1
=0
sixi, + siqxi,q =
= fi(Ki,0) +
q
=0
sixi, = fi(Ki,0) +
pi
=0
sixi,
a podobně
gij  gij(Ki,0) +
pi
=0
rijxi,.
Úlohu (22), (23) tedy můžeme aproximovat úlohou
n
i=1
fi(Ki,0) +
pi
=0
silxi,l  min
při omezeních
n
i=1
gij(Ki,0) +
pi
=0
rijxi,l  0, j = 1, 2, . . . , m,
0  xi,  Ki,+1 - Ki,, i = 1, 2, . . . , n,  = 0, 1, 2, . . . , pi,
24
nebo ekvivalentně
n
i=1
pi
=0
silxi,l  min (24)
n
i=1
pi
=0
rijxi,  -
n
i=1
gij(Ki,0), j = 1, 2, . . . , m, (25)
0  xi,  Ki,+1 - Ki,, i = 1, 2, . . . , n,  = 0, 1, 2, . . . , pi. (26)
To je úloha lineárního programování, kterou lze zapsat ve tvaru
cT
y  min, Ay  b, y  0,
kde
c = (s11, s12, . . . , s1p1 , s21, s22, . . . , s2p2 , . . . , sn1, sn2, . . . , snpn )T
,
y = (x1,1, x1,2, . . . , x1,p1 , x2,1, x2,2, . . . , x2,p2 , . . . , xn,1, xn,2, . . . , xn,pn )T
,
A =



































r111 r112 . . . r11p1 r211 r212 . . . r21p2 . . . rn11 rn12 . . . rn1pn
r121 r122 . . . r12p1 r221 r222 . . . r22p2 . . . rn21 rn22 . . . rn2pn
...
...
...
...
...
...
...
...
...
...
...
...
...
r1m1 r1m2 . . . r1mp1 r2m1 r2m2 . . . r2mp2 . . . rnm1 rnm2 . . . rnmpn
1 0 . . . 0 0 0 . . . 0 . . . 0 0 . . . 0
0 1 . . . 0 0 0 . . . 0 . . . 0 0 . . . 0
...
...
...
...
...
...
...
...
...
...
...
...
...
0 0 . . . 1 0 0 . . . 0 . . . 0 0 . . . 0
0 0 . . . 0 1 0 . . . 0 . . . 0 0 . . . 0
0 0 . . . 0 0 1 . . . 0 . . . 0 0 . . . 0
...
...
...
...
...
...
...
...
...
...
...
...
...
0 0 . . . 0 0 0 . . . 1 . . . 0 0 . . . 0
...
...
...
...
...
...
...
...
...
...
...
...
...
0 0 . . . 0 0 0 . . . 0 . . . 1 0 . . . 0
0 0 . . . 0 0 0 . . . 0 . . . 0 1 . . . 0
...
...
...
...
...
...
...
...
...
...
...
...
...
0 0 . . . 0 0 0 . . . 0 . . . 0 0 . . . 1



































,
b = -
n
i=1
gi1(Ki,0), -
n
i=1
gi2(Ki,0), . . . , -
n
i=1
gim(Ki,0),
K1,1 - K1,0, K1,2 - K1,1, . . . , K1,p1 - K1,p1-1, L1 - K1,p1 , . . .
. . . , Kn,1 - Kn,0, Kn,2 - Kn,1, . . . , Kn,pn - Kn,pn-1, Ln - K1,pn
T
.
25
Věta 10. Nechť jsou všechny funkce fi, gij, i = 1, 2, . . . , n, j = 1, 2, . . . , m spojité a konvexní.
Pak existuje řešení aproximující úlohy (24), (25), (26) takové, že
xiq > 0    {0, 1, 2, . . . , q - 1} xi, = Ki,+1 - Ki,.
Důkaz: Z podmínek
0  xi,l  Ki,+1 - Ki., i = 1, 2, . . . , n,  = 0, 1, 2, . . . , pi
plyne, že přípustná množina úlohy (24), (25), (26) je kompaktní a tedy že řešení existuje.
Předpokládejme, že existuje řešení y = (x1,1, x1,2, . . . , xn,pn) takové, že existují i0, q1, q2,
pro něž
q1 < q2 a xi0,q2 > 0, xi0,q1 < Ki0,q1+1 - Ki0,q1 . (27)
Pak
 = min {xi0,q2 , Ki0,q1+1 - Ki0,q1 - xi0,q1} > 0.
Poněvadž všechny funkce fi, gij jsou konvexní, platí
ri0jq1 - ri0jq2  0, si0q2 - si0,q1  0. (28)
Položme dále
~xi,j =



xi,j, i = i0 nebo j = q1, j = q2,
xi0,q1 + , i = i0, j = q1,
xi0,q2 - , i = i0, j = q2,
tj. složku xi0,q1 zvětšíme o , složku xi0,q2 o  zmenšíme. Podle definice čísla  je
0  ~xi0,q1  Ki0,q1+1 - Ki0,q1 a 0  ~xi0,q2  xi0,q2  Ki0,q2+1 - Ki0,q2 ,
neboť xi0,q2 je souřadnice přípustného bodu. Podle první z nerovností (28) dále platí
n
i=1
p1
l=0
rij~xil =
=
n
i=1
i=i0
pi
=0
q1==q2
rijxi +
pi
=0
q1==q2
ri0jxi0 + ri0jq1 ~xi0,q1 + ri0jq2 ~xi0,q2 =
=
n
i=1
i=i0
pi
=0
q1==q2
rij xi +
pi
=0
q1==q2
ri0j xi0 + ri0jq1 (xi0,q1 + ) + ri0jq2(xi0,q2 - ) =
=
n
i=1
pi
l=0
rijxil + (ri0jq1 - ri0jq2 )  -
n
i=1
gij(0) + (ri0jq1 - ri0jq2 )  -
n
i=1
gij(0),
takže ~y = (~x1,1, ~x1,2, . . . , ~xn,pn ) je přípustným bodem úlohy (24), (25), (26). Podle druhé
z nerovností (28) dostaneme
n
i=1
pi
=0
si~xi, =
n
i=1
i=i0
pi
=0
q1==q2
si xi +
pi
=0
q1==q2
si0 xi0 + si0q1 ~xi0,q1 + si0q2 ~xi0,q2 =
=
n
i=1
pi
=0
si xi, - (si0q2 - si0q1 ) 
n
i=1
pi
=0
sixi,.
26
V poslední neostré nerovnosti musí nastat rovnost, neboť v opačném případě by v přípustném
bodě ~y byla hodnota účelové funkce menší než v bodě y a to by bylo ve sporu s tím, že y je
řešením úlohy. To znamená, že jsme našli jiné řešení ~y úlohy (24), (25), (26), které již nemá
nežádoucí vlastnost (27).
4.3 Řešení metodami dynamického programování
Řešíme úlohu (22) při omezení
x  X = x  Rn
+ : x1 + x2 +    + xn = b . (29)
Minimum budeme postupně hledat tak, že zvolíme hodnotu poslední proměnné, s touto zvolenou
hodnotou minimalizujeme prvních n-1 sčítanců v separovatelné účelové funkci a nakonec
optimalizujeme volbu poslední proměnné, tj. hledáme minimum funkce fn. Hledáme tedy
min {f(x) : x  X} =
= min fn(xn) + min
n-1
i=1
fi(xi) : x1  0, . . . , xn-1  0,
n-1
i=1
xi = b - xn : 0  xn  b .
Pokud označíme
F(n, b) = min {f(x) : x1  0, x2  0, . . . , xn  0, x1 + x2    + xn = b} a bn = b,
můžeme předchozí rovnost přepsat ve tvaru
F(n, bn) = min {fn(xn) + F(n - 1, bn - xn) : 0  xn  b} .
Označme xn bod, v němž se realizuje minimum, tj. bod, pro nějž platí
F(n, bn) = fn(xn) + F(n - 1, bn - xn).
Položme dále bn-1 = bn - xn. Pak
F(n - 1, bn-1) = min
n-1
i=1
fi(xi) : x1  0, x2  0, . . . , xn-1  0, x1 + x2    + xn-1 = bn-1 =
= min fn-1(xn-1) +
+ min
n-2
i=1
fi(xi) : x1  0, . . . , xn-1  0,
n-2
i=1
xi = bn-1 - xn-1 : 0  xn-1  bn-1 =
= min {fn-1(xn-1) + F(n - 2, bn-1 - xn-1) : 0  xn-1  bn-1} .
Označme opět xn-1 bod, v němž se minimum realizuje, tj. bod, pro nějž platí
F(n - 1, bn-1) = fn-1(xn-1) + F(n - 2, bn-1 - xn-1) = fn-1(xn-1) + F(n - 2, b - xn - xn-1).
Tak můžeme postupovat dále. Obecně dostaneme
F(k, bk) = min {fk(xk) + F(k - 1, bk - xk) : 0  xk  bk} =
= fk(xk) + F(k - 1, b - xn - xn-1 -    - xk).
27
Postupně dojdeme až k rovnosti
F(1, b1) = min {f1(x1) : 0  x1  b1} ,
takže F(1, b1) = f1(x1), přičemž
x1 = b - xn - xn-1 -    - x2 = b1, (30)
tedy F(1, b1) = f1(b1). Tuto hodnotu dosadíme do předchozího vztahu, tj.
F(2, b2) = min {f2(x2) + f1(b1) : 0  x2  b2}
a vyjádříme x2 v závislosti na b2. Tak postupujeme dále až k vyjádření xn v závislosti na
bn = b, tedy hodnotu xn již vypočítáme. Pomocí ní vypočítáme xn-1 = xn-1(bn-1) atd. Tak
postupujeme až k x2. Hodnotu x1 nakonec vypočítáme z rovnosti (30).
Celkem uvedeným postupem provádíme n - 1 minimalizací funkcí jedné proměnné.
Příklad: x2
1 + 2x2
2 + x2
3  min, 2x1 + x2 + x3 = 10, x1  0, x2  0, x3  0.
Položíme y1 = 2x1, y2 = x2, y3 = x3 a řešíme úlohu
1
4
y2
1 + 2y2
2 + y2
3  min, y1 + y2 + y3 = 10, y1  0, y2  0, y3  0,
která je ekvivalentní s úlohou původní. Máme
F(1, b1) =
1
4
b2
1,
F(2, b2) = min 2y2
2 + F(1, b2 - y2) : 0  y2  b2 =
= min 2y2
2 +
1
4
(b2 - y2)2
: 0  y2  b2 =
= min
9
4
y2
2 -
1
2
b2y2 +
1
4
b2
2 : 0  y2  b2 =
2
9
b2
2,
y2 =
1
9
b2,
F(3, b3) = min y2
3 + F(2, b3 - y3) : 0  y3  b2 =
= min y2
3 +
2
9
(b3 - y3)2
: 0  y3  b3 =
= min
11
9
y2
3 -
4
9
b3y3 +
2
9
b2
3 : 0  y3  b3 =
2
11
b2
3,
y3 =
2
11
b3 =
2
11
 10 =
20
11
,
takže
y2 =
1
9
b2 =
1
9
(10 - y3) =
10
11
,
y1 = 10 - y3 - y2 = 10 -
10
11
-
20
11
=
80
11
.
Návratem k původním proměnným dostaneme řešení zadané úlohy
x
1 =
40
11
, x
2 =
10
11
, x
3 =
20
11
, f(x
1, x
2, x
3) =
200
11
.
28