Obsah Pouºité zna£ení
1
1 Úvod
3
1.1
Opera£ní výzkum a jeho disciplíny
. . . . . . . . . . . . . . . . . . . . . . . . . .
1.2
Úlohy matematického programování
1.3
Standardní maximaliza£ní úloha lineárního programování
1.4
Gra cké °e²ení úloh se dv¥ma prom¥nnými
1.5
Geometrický a algebraický popis mnoºiny p°ípustných °e²ení ÚLP
. . . . . . . . . . . . . . . . . . . . . . . . .
i
. . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3 3 5 6 6
Pouºité zna£ení Typogra cké rozli²ení názv· podle typu objektu a, f, x, i X, N, B x, b A, B
(malá písmena)
skaláry (£ísla), funkce, prom¥nné, indexy
(velká písmena)
mnoºiny (krom¥ speciálních, viz níºe)
(malá tu£ná písmena)
vektory (vºdy sloupcové), reálné
(velká tu£ná písmena)
matice
n-tice
Speciální mnoºiny N Z Z+ R R+ R++ Rn
p°irozená £ísla celá £ísla nezáporná celá £ísla reálná £ísla nezáporná reálná £ísla kladná reálná £ísla mnoºina v²ech reálných
n-tic
(tj.
n-rozm¥rný
euklidovský prostor)
Matice, vektory A m×n 0 m×n In A> |A|
m × n (pouºito v p°ípad¥, ºe je t°eba zd·raznit m × n (tj. matice tvo°ená samými nulami) jednotková matice typu n × n transpozice matice A determinant matice A
matice
A
typu
typ matice)
nulová matice typu
Zkratky Zkratky jsou vºdy zavedeny ve vlastním textu, tento seznam pouze slouºí pro rychlej²í orientaci.
DP
dopravní problém
ESR
ekvivalentní soustava rovnic
LP
lineární programování
MILP
smí²ené celo£íselné programování (mixed
O
optimální °e²ení
P
p°ípustné °e²ení
ÚLP
úloha linaárního programování
Z
základní °e²ení
integer linear programming )
Kapitola 1
Úvod 1.1 Opera£ní výzkum a jeho disciplíny Nástroje studované a vyuºívané v rámci opera£ního výzkumu:
• • • • •
optimalizace, pravd¥podobnost a statistika, teorie graf·, teorie front, simula£ní modely.
N¥které typické aplika£ní oblasti:
• • • • •
optimalizace produk£ních systém·, optimalizace v logistice, podpora rozhodování p°i °ízení projekt·, modely °ízení zásob, modely hromadné obsluhy.
1.2 Úlohy matematického programování De nice 1.1 (úloha matematického programování). • •
Nech´ jsou dány:
X , ozna£ovaná jako mnoºina p°ípustných °e²ení, f : X → R , ozna£ovaná jako ú£elová funkce.
mnoºina funkce
Úlohou matematického programování (ÚMP) pak ozna£ujeme problém nalezení bu¤ minima nebo maxima funkce
f
na mnoºin¥
X.
Mluvíme pak o minimaliza£ní, resp. maximaliza£ní ÚMP.
P°edchozí de nice je trochu moc obecná, jako úlohu matematického programování lze v této podob¥ formulovat i problémy, které jsou zavedeny velmi podivným zp·sobem. Nap°íklad úloha hledání královny krásy. V tomto p°ípad¥ máme mnoºinu
R.
Zpravidla proto vyºadujeme, aby
• •
podmnoºina
n-rozm¥rného
X
X = ºeny,
a funkci
f : ºena 7→ krása ∈
byla. . .
euklidovského prostoru, tj.
X ⊆ Rn ,
vymezená pomocí soustavy rovnic a/nebo nerovností.
P°íklad 1.2 (koktejly).
Cílem je namíchat co nejvíce koktejl· podle recept· z tabulky níºe. Záleºí
pouze na celkovém po£tu namíchaných koktejl·, je nám zcela lhostejné, kolik z nich bude Mojito a kolik Cuba Libre.
4
Úvod
Mojito
Cuba libre
4 cl kubánského rumu
8 cl kubánského rumu
1 dl vody
2 dl Coca-coly
8 kostek ledu (t°í²´) 1/2 limetky
2 kostky ledu 1/4 limetky
1 lºi£ka cukru (t°tinového) 3 lístky £erstvé máty Disponibilní mnoºství surovin jsou následující: 100 cl kubánského rumu, 20 dl Coca-coly, 120 kostek ledu a 8 limetek; vody, cukru a máty je dostatek (nehrozí, ºe dojdou). Celkem vzato, m·ºeme úlohu popsat následujícím zp·sobem:
Mojito
maximalizovat
+ Cuba
4 Mojito
za podmínek
+
Libre 8 Cuba Libre 2 Cuba Libre
8 Mojito
1/2 Mojito
+ +
2 Cuba Libre
1/4 Cuba Libre
Mojito, Cuba Libre V tomto p°ípad¥ je
X
≤ ≤ ≤ ≤
100, 20, 120, 8,
≥ 0.
mnoºina v²ech kombinací po£t· koktejl· Mojito a Cuba Libre, které jsme
schopni p°i daných zásobách namíchat (£ili kombinací hodnot prom¥nných Mojito a Cuba Libre, které sou£asn¥ spl¬ují v²echny vý²e uvedené omezující podmínky). Formáln¥ je tedy
X ⊂ R2 ,
vymezená pomocí soustavy lineárních nerovnic o dvou prom¥nných.
De nice 1.3 (standardní ÚMP). Rn → R .
Nech´ jsou dána reálná £ísla b1 , . . . , bm a reálné funkce Standardní úlohou matematického programování rozumíme úlohu ve tvaru maximalizovat za podmínek
f, g1 , . . . , gm :
f (x1 , . . . , xn ) g1 (x1 , . . . , xn ) b1 , g2 (x1 , . . . , xn ) b2 ,
(1.1)
. . .
gm (x1 , . . . , xn ) bm , (x1 , . . . , xn ) ∈ Rn , kde
p°edstavuje zástupný symbol za jedno z rela£ních znamének
Poznámka (ke zna£ení).
≤, =
nebo
≥.
Matematik·m zpravidla p°ipadá obecný zápis ÚMP v podob¥ (1.1)
p°íli² upovídaný. Nabízí se psát:
f (x1 , . . . , xn )
maximalizovat za podmínek
Lze také zavést vektor (£i chcete-li,
gi (x1 , . . . , xn ) bi , i = 1, . . . , m, (x1 , . . . , xn ) ∈ Rn . n-tici) x = (x1 , . . . , xn )
maximalizovat za podmínek
a psát
f (x) gi (x) bi , i = 1, . . . , m, x ∈ Rn .
nebo nejstru£n¥ji (ale pon¥kud mén¥ p°ehledn¥)
max{f (x) | x ∈ Rn , gi (x) bi , i = 1, . . . , m}.
Poznámka (klasi kace ÚMP). gi ,
Podle toho, jaké dodate£né poºadavky klademe na funkce
f
a
rozli²ujeme r·zné t°ídy ÚMP, které se zna£n¥ li²í co do sloºitosti pouºívaných výpo£etních
technik:
•
lineární programování,
1.3
5
Standardní maximaliza£ní úloha lineárního programování
• • • •
kvadratické programování, konvexní programování, nelineární programování, . . . a dal²í.
Zdaleka nejjednodu²²í t°ídou je lineární programování; spadá sem nap°. matematický model pro p°íklad Koktejly.
De nice 1.4 (lineární reálná funkce). lineární, pokud lze
f
vyjád°it na
R
n
M¥jme reálnou funkci
f : Rn → R .
ekneme, ºe
f
je
p°edpisem
f (x1 , . . . , xn ) = c1 x1 + . . . + cn xn pro n¥jaká reálná £ísla
c1 , . . . , cn .
De nice 1.5 (úloha lineárního programování). funkce
f, g1 , . . . , gm
Úlohu ve tvaru (1.1), ve které jsou navíc v²echny
lineární, nazveme (maximaliza£ní) úlohou lineárního programování (ÚLP).
1.3 Standardní maximaliza£ní úloha lineárního programování De nice 1.6 (standardní maximaliza£ní ÚLP). xj pro i = 1, . . . , m a vektor· b, c a x ve tvaru a11 a12 a21 a22 A= . . . .. . am1 am2 m¥nné
M¥jme dány reálné koe cienty
j = 1, . . . , n, a1n a2n . , . . amn
··· ··· ..
.
···
aij , bi
a
cj
a pro-
které budeme p°ípadn¥ zapisovat do matice
b1 b2 b = . , .. bm
c1 c2 c = . , .. cn
A
a
x1 x2 x = . . .. xn
Standardní maximaliza£ní úlohou lineárního programování rozumíme problém
c1 x1 + c2 x2 + . . . + cn xn
maximalizovat
a11 x1 + a12 x2 + . . . + a1n xn ≤ b1 , a21 x1 + a22 x2 + . . . + a2n xn ≤ b2 ,
za podmínek
. . .
(1.2)
am1 x1 + am2 x2 + . . . + amn xn ≤ bm , xj ≥ 0, kde
x1 , x2 , . . . , xn
j = 1, . . . , n,
jsou reálné prom¥nné. Za pouºití suma£ního operátoru a indexace omezení lze
(1.2) vyjád°it ekvivalentn¥ jako maximalizovat za podmínek
Pn
Pj=1 n j=1
cj xj aij xj ≤ bi , i = 1, . . . , m, xj ≥ 0, j = 1, . . . , n,
(1.3)
p°ípadn¥ v maticovém zápisu je²t¥ úsporn¥ji jako maximalizovat za podmínek
c>x Ax ≤ b, x ≥ 0,
p°íp. zcela krátce jako problém nalezení
max{c>x | Ax ≤ b, x ≥ 0}.
(1.4)
6
Úvod
P°íklad 1.7.
V p°íkladu Koktejly bychom zapsali
4 0 A= 8 1/2
P°íklad 1.8.
8 2 , 2 1/4
100 20 b= 120 , 8
c=
1 , 1
x=
Mojito
Cuba Libre
.
K úloze minimalizovat
2u + v − 4w
za podmínek
5(u − v) 2u + v − 2w 3u − v + 2w u, v w
≤ 2(v − w) − 6v + 1, ≥ −2, = 3, ≥ 0, ∈R
najdeme ekvivalentní ÚLP ve standardním maximaliza£ním tvaru. Jedno z moºných °e²ení vypadá následovn¥: maximalizovat
−2x1 − x2 + 4x3 − 4x4
za podmínek
5x1 − x2 + 2x3 − 2x4 −2x1 − x2 + 2x3 − 2x4 3x1 − x2 + 2x3 − 2x4 −3x1 + x2 − 2x3 + 2x4 xj
≤ 1, ≤ 2, ≤ 3, ≤ −3, ≥0
p°i£emº mezi prom¥nnými obou model· je následující vztah:
pro
j = 1, . . . , 4,
u = x1 , v = x2
a
w = x3 − x4 .
Lemma 1.9 (o univerzálnosti standardní maximaliza£ní ÚLP). Ke kaºdé ÚLP lze najít ekvivalentní úlohu ve tvaru standardní maximaliza£ní ÚLP, tj. úlohu, která je maximaliza£ní, má v²echna omezení typu ≤ a v²echny její prom¥nné jsou nezáporné.
1.4 Gra cké °e²ení úloh se dv¥ma prom¥nnými Viz p°edná²ky.
1.5 Geometrický a algebraický popis mnoºiny p°ípustných °e²ení ÚLP De nice 1.10 (konvexní kombinace v Rn ).
Konvexní kombinací bod·
x1 , . . . , xk
v
Rn
je bod,
který lze vyjád°it ve tvaru
α1 x1 + . . . + αk xk , kde
α1 , . . . , αk
P°íklad 1.11. n¥jaké
jsou nezáporná reálná £ísla spl¬ující Konvexní kombinaci dvou bod·
α ∈ [0, 1].
x, y
α1 + . . . + αk = 1. m·ºeme zapsat ve tvaru
αx + (1 − α)y
je bod na úse£ce mezi nimi. Obrázek 1.1 ilustruje výsledek r·zné hodnoty
De nice 1.12 (konvexní mnoºina).
ekneme, ºe mnoºina
X ⊆ Rn
α.
je konvexní, je-li uzav°ená na
konvexní kombinace, tj. pokud libovolná konvexní kombinace libovolných bod· leºí v
pro
Geometricky vzato, konvexní kombinace dvou bod· v euklidovském prostoru
x1 , . . . , xk ∈ X
X.
P°íklad 1.13.
P°íkladem konvexních mnoºin v rovin¥ jsou nap°íklad £tverec, kruh, nebo úse£ka.
P°íklady nekonvexních mnoºin ukazuje obrázek 1.2.
1.5
7
Geometrický a algebraický popis mnoºiny p°ípustných °e²ení ÚLP
α = 0.75
α=1 x
Obrázek 1.1
x1
R·zné konvexní kombinace bod·
x, y .
x2
X
Y
Obrázek 1.2
nenáleºí
X.
Mnoºina
Z
X,
i=1
Úse£ka mezi body
Konvexním obalem mnoºiny
konvexních kombinací kone£ných podmnoºin
Pk
X, Y, Z .
X,
αi xi xi ∈ X, αi ≥ 0
X.
X ⊆ Rn
rozumíme mnoºinu v²ech
neboli mnoºinu pro
i = 1, . . . , k,
Snadno nahlédneme, ºe konvexní obal mnoºiny
která obsahuje
x1 , x2 ∈ X
tedy existuje konvexní kombinace t¥chto bod·, která
je tvo°ena p¥ti izolovanými body.
De nice 1.14 (konvexní obal). conv(X) =
Z
P°íklady nekonvexních mnoºin
není obsaºena v mnoºin¥
Poznámka.
α=0 y
α = 0.25
α = 0.5
X
Pk
i=1
αi = 1, k ∈ N .
je nejmen²í konvexní mnoºina,
(D·kaz tohoto tvrzení p°enechávám £tená°i jako cvi£ení.) V p°ípad¥, ºe
je konvexní mnoºina, je z°ejm¥
conv(X) = X .
X
P°íklady konvexních obal· nekonvexních mnoºin
zachycuje obrázek 1.3.
conv(Y ) Obrázek 1.3
conv(Z)
Konvexní obaly mnoºin
De nice 1.15 (konvexní polyedr, omezený). polyedr (nebo téº polytop ), lze-li
De nice 1.16 (krajní bod).
X
X, Y, Z
z obrázku 1.2.
ekneme, ºe mnoºina
X ⊆ Rn
je omezený konvexní
vyjád°it jako konvexní obal kone£né mnoºiny bod· z
R.
x ∈ X ⊆ Rn nazveme krajním bodem mnoºiny X , pokud x není konvexní kombinací dvou jiných bod· z X , tj. pokud neexistují y1 , y2 ∈ X a α ∈ (0, 1) takové, ºe y1 6= x 6= y2 a αy1 + (1 − α)y2 = x.
P°íklad 1.17.
Bod
Ur£ete krajní body p¥ticípé hv¥zdy, £tverce a kruhu. Které z t¥chto mnoºin jsou
omezené konvexní polyedry?
8
Úvod
Lemma 1.18 (o extrému lineární funkce na omezeném konvexním polyedru). Lineární funkce nabývá svého extrému na omezeném konvexním polyedru v n¥kterém z jeho krajních bod·.
De nice 1.19 (uzav°ený poloprostor v Rn ). v
R
n
, lze-li
X
ekneme, ºe mnoºina
X ⊂ Rn je uzav°ený poloprostor
vyjád°it jako mnoºinu v²ech °e²ení n¥jaké (netriviální) lineární nerovnice, tj.
existují-li reálná £ísla
a1 , . . . , an ,
ne v²echna nulová, a £íslo
b,
pro n¥º platí
X = (x1 , . . . , xn ) ∈ Rn a1 x1 + . . . + an xn ≤ b .
De nice 1.20 (konvexní polyedr, ne nutn¥ omezený). polyedr, lze-li
X
ekneme, ºe mnoºina
X ⊆ Rn
je konvexní
vyjád°it jako pr·nik kone£n¥ mnoha uzav°ených poloprostor·.
Zdánliv¥ se tato de nice velmi li²í od de nice omezeného konvexního polyedru uvedené vý²e. Jak ale postupn¥ ukáºeme, mezi ob¥ma de nicemi je t¥sná souvislost. Zatímco omezený konvexní polyedr lze vyjád°it jako konvexní obal jeho vrchol·, neomezený kovexní polyedr m·ºeme podobn¥ popsat pomocí jeho vrchol· a p°ípustných sm¥r· (viz níºe). Budeme k tomu ale pot°ebovat je²t¥ n¥kolik pojm·.
Poznámka (o geometrické interpretaci reálných n-tic).
Reálnou
n-tici
m·ºeme chápat bu¤ jako
bod v euklidovském prostoru, který pro nás zachycuje n¥jaký údaj o poloze, nebo jako sm¥r, který nese informaci o posunu ; viz obrázek 1.4.
y
y
x
x
(0, 0) Obrázek 1.4
(0, 0)
Reálné dvojice
x = (3, 1)
a
y = (1, 2)
interpretovány jako body (vlevo)
a sm¥ry (vpravo).
De nice 1.21 (kónická kombinace, kónický obal).
Kónickou kombinací sm¥r·
x1 , . . . , xk
v
Rn
je
sm¥r, který lze vyjád°it ve tvaru
β1 x 1 + . . . + βk x k , kde
β1 , . . . , β k
jsou nezáporná reálná £ísla. Kónickým obalem mnoºiny
ºinu v²ech kónických kombinací kone£ných podmnoºin
con(X) =
P°íklad 1.22.
Pk
i=1
βi xi xi ∈ X, βi ≥ 0
X,
X ∈ Rn
rozumíme mno-
neboli mnoºinu
pro
i = 1, . . . , k, k ∈ N .
Obrázek 1.5 ilustruje pojem kónického obalu na p°íkladu t°í sm¥r· v
x3
x2 (0, 0) Obrázek 1.5
x1
T°i sm¥ry
(0, 0) x1 , x1 , x3 ∈ R 2
(vlevo) a jejich kónický obal (vpravo).
R2 .
1.5
9
Geometrický a algebraický popis mnoºiny p°ípustných °e²ení ÚLP
V¥ta 1.23 (o reprezentaci konvexního polyedru pomocí vrchol· a krajních p°ípustných sm¥r·).
n Konvexní polyedr X ⊆ R lze reprezentovat pomocí kone£né mnoºiny bod· V = {v1 , . . . , vk } ⊂ n R a mnoºiny sm¥r· S = {s1 , . . . , sl } ⊂ Rn v tom smyslu, ºe libovolný bod z X lze vyjád°it jako
S , tj. Pk Pl Pk X= i=1 αi vi + j=1 βj sj αi ≥ 0, βj ≥ 0, i=1 αi = 1 .
sou£et konvexní kombinace prvk·
Navíc platí, ºe za
V
V
a kónické kombinace prvk·
lze volit mnoºinu krajních bod· (vrchol·)
X,
a podobn¥ kaºdá mnoºina
spl¬ující vý²e uvedené tvrzení nutn¥ obsahuje mnoºinu vrchol·. Dále, z kaºdé mnoºiny
S
V
spl¬ující
vý²e uvedené tvrzení lze vybrat mnoºinu s nejmen²ím po£tem prvk· (krajní p°ípustné sm¥ry), která je ur£ena jednozna£n¥ aº na kladné násobky.
