Pomocné texty pro přípravu ke státním zkouškám
Jindřich Klapka, Vítězslav Ševčík
1. března 2014
15 Lineární programování, simplexová metoda, způsoby převádění optimalisačního problému na kanonický tvar
(Zde je třeba nastudovat učební texty J. Klapka, J Dvořák, P. Popela: Metody operačního
výzkumu VUTIUM Brno 2001, str. 6–36)
Aby bylo možno problém lineárního programování řešit simplexovou metodou, musí
být převeden na kanonický tvar.
15.1 Jak jej převedeme, když je zadán s omezujícími podmínkami ve tvaru nerovností?
Příklad zadání problému:
Nalézt
Nalézt
Za podmínek
max{3x1 + 2x2 }
27x1 + 36x2 ≤ 128
13x1 + 15x2 ≤ 336
x1 ≥ 0,
x2 ≥ 0
Převedení na kanonický tvar:
max{3x1 + 2x2 } = max{3x1 + 2x2 + 0x3 + 0x4 }
27x1 + 36x2 + 1x3
= 128
13x1 + 15x2
+ 1x4 = 336
x1 ≥ 0,
x2 ≥ 0,
x3 ≥ 0,
(1)
x4 ≥ 0
Proměnné x3 , x4 nazýváme přídatné (doplňkové) proměnné. V případě výrobkového problému mohou vyjadřovat nevyužité části zdrojů, jejichž kapacity jsou vyjádřeny pravými
stranami omezujících podmínek.
Proměnné x1 , x2 , x3 , x4 rozdělíme na dvě skupiny: Bázické a nebázické. Nebázické
zde zvolíme x1 , x2 , bázické pak budou x3 , x4 . Nebázické položíme rovny nule. Pak bázické
jsou rovny pravým stranám.
Výchozí bázické řešení, které je jedním z přípustných řešení problému, které nemusí
být optimální, je: x1 = 0, x2 = 0, x3 = 128, x4 = 336.
1
Následuje řešení tohoto problému simplexovou metodou. Základní myšlenka simplexové metody spočívá v postupné transformaci systému lineárních algebraických rovnic
vyjadřujících omezující podmínky optimalisačního problému (v našem případě systému
(1)), která je provedena tak, aby transformovaný systém splňoval tyto požadavky:
a) aby měl stejnou množinu přípustných řešení jako před transformací
b) aby byl též v kanonickém tvaru
c) aby kriteriální funkce (v našem případě výraz 3x1 + 2x2 ) neměla menší hodnotu než
před transformací.
Kdy má systém po transformaci stejnou množinu přípustných řešení?
Je to tehdy, když jej transformujeme tak, že libovolný jeho řádek násobíme libovolnou nenulovou reálnou konstantou, nebo libovolný jeho řádek upravíme tak, že k němu
přičteme kterýkoliv jiný řádek tohoto systému, násobený libovolnu reálnou konstantou,
případně provedeme libovolné množství úprav tohoto druhu v libovolném pořadí.
Tyto vlastnosti má simplexová transformace v citované knize Metody operačního
výzkumu 2001 (vzorce (2.33), (2.34)), kde je též uvedeno kriterium optimality, podle
něhož poznáme, která z těchto transformací je již poslední, tj. poskytující optimální
řešení.
15.2 Jak problém převedeme na kanonický tvar, když je zadán s omezujícími podmínkami ve tvaru rovnic?
Nalézt
max{30x1 + 20x2 }
Za podmínek
270x1 + 360x2 = 1280
(2)
130x1 + 150x2 = 3360
x1 ≥ 0,
x2 ≥ 0
Převedeme na kanonický tvar převedením na rozšířený problém:
max{30x1 + 20x2 + 0x3 + 0x4 }
270x1 + 360x2 + 1x3
= 1280
130x1 + 150x2
+ 1x4
= 3360
−30x1 − 20x2
+z=0
x1 ≥ 0,
x2 ≥ 0,
x3 ≥ 0,
x4 ≥ 0
x3 , x4 nazýváme pomocné proměnné. Nemají věcný význam. Pouze rozšiřují problém
na jiný problém, který je v kanonickém tvaru. Náš problém nyní řešíme dvoufázovou
simplexovou metodou:
2
1. fáze: min{x3 + x4 }, tj. max{−x3 − x4 } (minimalisace pomocné kriteriální funkce).
| {z }
z0
Pokud má náš původní problém řešení, dosáhneme stavu, kdy z 0 = 0. nejprve však
musíme pomocné proměnné x3 , x4 vyjádřit pomocí ostatních proměnných, abychom
měli jistotu, že se nestanou bázickými.
Tím máme problém převeden na náš původní problém (2), který je však již v kanonickém tvaru, takže ho již můžeme řešit simplexovou metodou, což je úkolem druhé
fáze:
2. fáze:
max{30x1 + 20x2 } .
Tato původní kriteriální funkce však již bude transformována, tj. bude mít jiné cenové koeficienty, neboť v 1. fázi měla úlohu omezující podmínky, takže její koeficiety
se transformovaly simplexovou transformací spolu s koeficienty ostatních omezujících
podmínek rozšířeného problému. Má však stejnou hodnotu maxima i stejné optimalisující hodnoty nezávisle proměnných takže druhá fáze dvoufázové simplexové metody
nám poskytne optimální řešení původního problému.
Pokud je pomocných proměnných malý počet, můžeme je anulovat i jinak než využitím dvoufázové simplexové metody. Spočívá to ve využití tzv. prohibitivní ceny. Je
to záporná cena (cenový koeficient) −M , kde M je vhodně zvolené velké kladné číslo.
Simplexová metoda pracuje tak, že pokud má problém přípustné řešení, pak pomocná
proměnná, která je v kriteriální funkci oceněná dostatečně velkou zápornou cenou, nebude
na konci výpočtu bázickou proměnnou. Jako nebázická je pak anulována automaticky.
Pokud na některou proměnnou xi není kladena podmínka nezápornosti, můžeme použít simplexovou metodu, použijeme-li substituce
−
xi = x+
i − xi ,
x+
i ≥ 0,
x−
i ≥ 0,
jak v kriteriální funkci, tak i v omezujících podmínkách, čímž místo této proměnné zavedeme dvě nové proměnné.
15.3 Duální problém a jeho využítí v analyse citlivosti řešení problému
Zde je potřeba vycházet z přednášky. V dalším připomenu jen základní myšlenku:
V oblasti symetrického duálního problému považujeme za vzájemně duálně sdružené
tyto dva optimalisační modely:
Primární model
Nalézt
Za podmínek
Duální model
max cT x
Ax ≤ b
x≥0
Nalézt
Za podmínek
kde
3
min bT u
AT u ≥ c
u≥0
,

a11
 a21

A= .
 ..
a12
a22
..
.
...
...
..
.

a1n
a2n 

..  ,
. 

x1
 x2 
 
x =  . ,
 .. 

cn
xn
am1 am2 . . . amn
 
c1
 c2 
 
c =  . ,
 .. 

b1
 b2 
 
b =  . ,
 .. 


u1
 u2 
 
u= . 
 .. 

um
bm
Věta o dualitě (tzv. hlavní věta o dualitě):
Má-li jeden ze sdružených matematických modelů optimální řešení s konečnou hodnotou
kriteriální funkce, pak má i druhý model optimální řešení s konečnou hodnotou kriteriální
funkce a optimální hodnoty kriteriálních funkcí obou modelů jsou si rovny.
15.3.1 Využití k analyse citlivosti
Jak se změní optimální hodnota kriteriální funkce z = cT x(o) při změně pravé strany bi
o jedničku?
(o)
(o)
(o)
(o)
(o)
(o)
Označme z(bi ) = c1 x1 + c2 x2 + · · · + cn xn = b1 u1 + b2 u2 + · · · + bm um , což
platí podle věty o dualitě.
Pak platí též:
(o)
(o)
z(bi + 1) = b1 u1 + · · · + (bi + 1)ui + · · · + bm u(o)
m .
Z toho plyne:
(o)
∆z(bi ) = z(bi + 1) − z(bi ) = ui
.
(o)
To znamená, že při změně bi o jedničku vzroste maximální hodnota z právě o ui .
4
16 Konvexní a kvazikonvexní optimalisační problémy. Lineární lomené
programování. Maximalisace haléřového ukazatele firmy.
Je třeba vyjít z přednášky. Máme-li se rozhodnout, zda můžeme pro optimalisaci dané
funkce použít např. firemní program určený pro optimalisaci konvexní funkce, musíme
umět zjistit, zda je tato funce konvexní. K tomu používáme analysy minorů Hessovy
matice.
Množina M je konvexní, jstliže s každými dvěma body (vektory) x, y ∈ M do ní patří
i každá jejich konvexní kombinace k1 x + k2 y, kde
k1 + k2 = 1,
k1 ≥ 0,
k2 ≥ 0 ,
(3)
tj. každý bod ležící na úsečce spojující body x, y.
Funkce f je konvexní na konvexní množině M , jestliže pro všechny body x, y ∈ M
platí
f (k1 x + k2 y) ≤ k1 f (x) + k2 f (y)
(4)
pro všechna k1 , k2 splňující (3).
Jestliže v (4) platí místo ≤ ostrá nerovnost < při k1 > 0, k2 > 0, říkáme, že f je ryze
konvexní.
Má-li f na M druhé derivace, můžeme rozhodnout o konvexnosti funkce f tak, že
2f
sestavíme čtvercovou matici D z prvků dij = ∂x∂i ∂x
(i, j = 1, 2, . . . , n), tj. Hessova
j
matice (Hessián).
Funkce f je ryze konvexní v M , jestliže všechny rohové minory matice D jsou v M
kladné.
Funkce f je konvexní v M , jestliže všechny 2n − 1 možné hlavní minory matice D
jsou v M nezáporné. Přitom hlavním minorem matice D nazýváme každý determinant
tvaru
di1 i1 di1 i2 . . . di1 ip di i di i . . . di i 2 2
2 p
21
..
..
.. ,
..
.
.
.
. di i di i . . . di i p 1
p 2
p p
kde platí 1 ≤ i1 < i2 < · · · < ip ≤ n.
Takový determinant dostaneme, když v matici D vyškrtáme všechny řádky a sloupce
kromě řádků a sloupců i1 , i2 , . . . , ip a z nepřeškrtaných prvků sestavíme determinant,
aniž bychom přitom měnili vzájemné postavení prvků.
Funkce f je (ryze) konkávní v M , je-li funkce −f (ryze) konvexní v M
16.1 Lineární lomené programování
Účelová funkce
Pn
ci xi
c1 x1 + c2 x2 + · · · + cn xn
= Pni=1
f (x) =
d1 x1 + d2 x2 + · · · + dn xn
i=1 di xi
5
udává například hodnotu hrubé produkce vztaženou na jednotku výrobních nákladů
xi = úroveň výroby výrobku i
kde
ci = cena jednotky výrobku i
di = náklady na výrobu jednotky výrobku i (i = 1, 2, . . . , n) .
Hledáme
za podmínek
max f (x)
n
P
aji xi = bj
(j = 1, 2, . . . , m)
i=1
xi ≥ 0
(i = 1, 2, . . . , n)
kde aji je množství j-tého zdroje, potřebné k výrobě jedné jednotky i-tého výrobku.
Převedení na lineární programování lze provést za podmínek:
1) Pro všechna přípustná x platí
Pn
i=1 di xi
> 0. Tento výraz je tedy nenulový.
2) Žádné aji nesmí být záporné. Tj. když jsou nulové kapacity zdrojů, pak nic nevyrábíme. Jinak bychom vyrobili zdroje, což nechceme. Je to ekvivalentní předpokladu,
že množina přípustných řešení je omezená.
Metoda řešení: Upravíme kriteriální funkci do tvaru:
f (x) = c1
x1
x2
+ c2
+ ···
d1 x1 + d2 x2 + · · · + dn xn
d1 x1 + d2 x2 + · · · + dn xn
xn
· · · + cn
d1 x1 + d2 x2 + · · · + dn xn
a položíme
zi = Pn
xi
(i = 1, 2, . . . , n) ,
i=1 di xi
zn+1 = Pn
1
i=1 di xi
.
Linearisace se tedy provádí za cenu zavedení další proměnné zn+1 , a musíme též zavést
o jednu omezující podmínku více.
Provedeme-li tuto substituci, dostaneme úlohu lineárního programování maximalisovat
n
X
ci zi
i=1
6
za podmínek
n
X
aji zi − bj zn+1 = 0
i=1
n
X
di zi = 1,
zi ≥ 0
(j = 1, 2, . . . , m)
(i = 1, 2, . . . , n + 1) .
i=1
Hledaný výrobní program dostaneme po vyřešení úlohy lineárního programování zpětnou
zi
substitucí xi = zn+1
(i = 1, 2, . . . , n).
Zde používaná lineární lomená kriteriální funkce patří mezi tzv. kvazikonkávní funkce.
Definice 1 Funkce f je kvazikonkávní na konvexní množině M , jestliže pro každé reálné
číslo α je množina {x; x ∈ M, f (x) ≥ α} konvexní.
Funkce f je kvazikonvexní, jestliže −f je kvazikonkávní.
Pro maximalisační úlohy s kvazikonkávní účelovou funkcí a pro minimalisační úlohy
s kvazikonvexní účelovou funkcí a konvexní množinou přípustných řešení se používá souhrnného názvu kvazikonvexní úlohy.
7
17 Kuhn-Tuckerova věta a její aplikace v gradientních metodách a v
kvadratickém programování
V této otázce je třeba vycházet z přednášky.
Hledejme maximum funkce f (x) při omezeních
g1 (x) ≥ 0
..
.
gm (x) ≥ 0,
x≥0.
Zaveďme nyní m nových proměnných u = [u1 , u2 , . . . , um ], z nichž každá odpovídá jedné
omezující podmínce, a pomocí nich zaveďme novou pomocnou funkci n + m proměnných
x1 , . . . , xn , u1 , . . . , um , tzv. Langrangeovu funkci, čili Lagrangián
ϕ(x, u) = f (x) +
m
X
uj gj (x) .
j=1
Předpokládejme, že funkce f, g1 , g2 , . . . , gm jsou konkávní a spojitě derivovatelné, a
že pro každý nezáporný a nenulový bod u existuje nezáporný bod x takový, že platí
m
X
uj gj (x) > 0
(podmínka regularity)
j=1
Od podmínky regularity lze upustit, jsou-li omezení lineární.
Pak platí věta Kuhn-Tuckerova:
Nezáporný bod x je řešením maximalisačního problému nelineárního programování,
uvedeného výše, tehdy a jen tehdy, existuje-li nezáporný bod u takový, že platí
∂ϕ
xi = 0
∂xi
∂ϕ
uj = 0
∂uj
∂ϕ
≤0,
∂xi
∂ϕ
≥0,
∂uj
(i = 1, 2, . . . , n)
(j = 1, 2, . . . , m)
Všechny derivace se berou v bodě optima.
Tyto 4 podmínky se nazývají Kuhn-Tuckerovy podmínky. Bod x
¯, u
¯, splňující tyto 4
vztahy, se nazývá sedlový bod.
Pro něj platí
ϕ(x, u
¯) ≤ ϕ(¯
x, u
¯) ≤ ϕ(¯
x, u)
ϕ(¯
x, u
¯) = max ϕ(x, u
¯) = min ϕ(¯
x, u) .
x≥0
u≥0
Věta Kuhn-Tuckerova tedy převádí problém konvexního programování na problém nalezení nezáporného sedlového bodu Lagrangiánu ϕ.
Na tom jsou založeny: a) nepřímé gradientní metody
b) Wolfeho metoda kvadratického programování.
8
Nepřímé gradientní metody konvergují k maximu funkce f hledáním směru nejprudšího vzestupu Lagrangiánu ϕ podle vektoru x, a jeho nejprudšího klesání podle vektoru
u, tedy hledáním sedlového bodu Lagrangiánu ϕ(x, u).
Ve Wolfeho metodě se počítá max f (x), kde f (x) = pT x − xT Cx
Princip Wolfeho metody: Kvadratická kriteriální funkce se derivováním v Kuhn-Tuckerových podmínkách linearisuje. Dále v problému přibude jedna nová kvadratická omezující podmínka, která vznikne takto:
Vyjdeme z první Kuhn-Tuckerovy podmínky, kterou převedeme na rovnici zavedením
přídatné proměnné vi :
∂ϕ
∂ϕ
+ vi = 0 ⇒
= −vi .
∂xi
∂xi
∂ϕ
do druhé Kuhn-Tuckerovy podmínky a sečtením
přes všech n proměnDosazením za ∂x
i
P
ných dostaneme novou kvadratickou omezující podmínku ni=1 xi vi = 0. Platnost této
podmínky se ve Wolfeho metodě zajišťuje takto: Je-li v dané etapě výpočtu proměnná
xk proměnnou bázickou, pak ponecháme proměnnou vk mimo bázi (tedy vk = 0). Jestliže
naopak je v bázi vk , nevezmeme do báze proměnnou xk (tedy platí xk = 0).
9
18 Dynamické programování deterministických rozhodovacích procesů.
K této otázce je třeba prostudovat stránky 121–135 učebních textů Metody operačního
výzkumu 2001 (VUTIUM Brno). Zde připomenu pouze základní myšlenku tohoto přístupu k tvorbě matematických optimalisačních metod:
Zkoumejme víceetapový rozhodovací proces vývoje zkoumaného systému, jehož počáteční stav je dán vektorem p. Zaměříme-li se na speciální případ diskretního stacionárního
deterministického rozhodovacího procesu a aditivní kriteriální funkce, můžeme jeho stavy,
následující v jednotlivých etapách v čase za sebou, popsat, je-li dána transformační funkce
T (p, q) pro kterou platí
p1 = T (p, q)
p2 = T (p1 , q1 )
..
.
pn+1 = T (pn , qn ) ,
kde p = p0 je stav systému v počáteční (nulté) etapě, p1 je stav po provedení jedné
transformace, p2 stav po provedení dvou transformací (čili v etapě číslo 2), atd. Předpokládáme, že můžeme tento proces natolik ovlivnit, že jeho i-té etapě pro i = 0, 1, 2, . . . , n
můžeme přiřadit vektor qi , příslušný dané množině S(pi ) přípustných vektorů, a tím
ovlivnit tvar transformace, kde q = q0 ∈ S(p), q1 ∈ S(p1 ), . . . , qn ∈ S(pn ). Vektor qi se
nazývá rozhodovací vektor nebo rozhodovací proměnná. Volbu qi nazveme rozhodnutím.
Zkoumejme problém maximalisace účelové funkce
F (p, p1 , . . . , q, q1 , . . .) =
N
X
g(pi , qi ) .
(5)
i=0
Předpokládejme, že maximum existuje, že funkce g(x, y) je omezená, a že veličiny pi ,
qi mohou nabývat pouze konečného množství hodnot.
Označme maximální hodnotu funkce F pro daný počáteční stav a pro počet etap N
symbolem fN (p). Je tedy fN (p) účelová funkce N -etapového procesu, jehož počáteční
stav je p, a u něhož je použito optimální strategie, tj. takové posloupnosti proměnných
q, q1 , . . . , qN , která poskytuje funkci F maximální hodnotu.
Platí-li tedy
h
i
fN (p) = max g(p, q) + g(p1 , q1 ) + · · · + g(pN , qN ) ,
q,q1 ,...,qN
pak lze snadno odvodit základní funkcionální rovnici dynamického programování N etapového diskretního deterministického procesu s účelovou funkcí (5):
h
i
fN (p) = max g(p, q) + fN −1 T (p, q) .
(6)
q∈S(p)
10
K této rovnici přísluší podmínka
f0 (p) = max g(p, q)
q∈S(p)
Řešení rekurentní rovnice (6) spočívá v nalezení optimální hodnoty fN (p) kriteriální
funkce F , a optimální strategie rozhodnutí ve formě posloupnosti rozhodovacích proměnných {q, q1 , . . . , qN } vztažených k jednotilivým etapám procesu, se snahou nalézt funkční
závislost rozhodnutí q(p) na stavu, v němž se zkoumaný systém v dané etapě nachází.
Z praktických aplikací dynamického programování stačí znát alespoň optimální průchod dopravního prostředku dopravní sítí, kde hledáme cestu s minimální dobou trvání,
spojující dané dva uzly. Zkoumaným systémem je zde dopravní prostředek, stavem systému je číslo uzlu, v němž je tento prostředek přítomen, rozhodnutí spočívá ve volbě
uzlu, který má bezprostředně následovat.
Jinou důležitou aplikací je optimalisace strategie obnovy strojů, kde maximalisujeme
celkový užitek stroje z několikaletého procesu přičemž roční zisk stroje klesá s jeho stárnutím. Považujeme-li za stav systému stáří stroje, který je na počátku etapy, na daném
pracovišti v provozu, pak rozhodnutí na začátku každé etapy spočívá ve volbě zda stroj
nahradíme novým strojem téhož typu, nebo jej necháme dále pracovat. Transformace
stavu systému pak spočívá v tom, že za rok stáří stroje buďto stoupne o jedničku, nebo
se stane rovným jedné.
Ve zmíněných učebních textech je z praktických aplikací dynamického programování
též popsáno řešení optimálního rozdělování zdrojů, což je v současné době jedna z nejaktuálnějších ekonomických úloh.
11
19 Vícekriteriální optimalisace. Fuzzy-vícekriteriální optimalisace. Vícekriteriální selekce portofolia
K této otázce doporučuji nastudovat ze zmíněných skript Metody operačního výzkumu
2001 stránky 145–153.
V následujícím textu připomenu základní myšlenku vícekriteriálního výběru skupiny
projektů:
Nechť pro výběr do plánu přichází v úvahu s projektů. Nechť i je číslo (index) projektu
(i = 1, 2, . . . , s). Cílem řešení je nalézt pro všechna i hodnoty bivalentních proměnných
δi , pro něž
(
1 (je-li úkol vybrán do plánu)
δi =
0 (v opačném případě) ,
tak aby byly splněny požadavky na řešení, k nimž patří
a) splnění zdrojových omezení
X
aij δi ≤ bj
(j = 1, 2, . . . , m) ,
i
kde
aij = množství j-tého zdroje, které potřebuje i-tý projekt
bj = disponibilní množství (kapacita) j-tého zdroje (j = 1, 2, . . . , m)
b) snaha o dosažení co nejvyšších hodnot kriteriálních funkcí o počtu p
"max"
s
X
cij δi = "max"zj
(j = 1, 2, . . . , p) ,
i=1
kde cij = příspěvek i-tého projektu k j-té kriteriální funkci.
Pro každou kriteriální funkci zj se stanoví její „ideální“ hodnota Ij , tj. horní mez optimální hodnoty veličiny zj , což může být např. maximální hodnota funkce zj , stanovená za
uvedených podmínek s ignorováním vlivu ostatních kriteriálních funkcí. Dále se pro každé
zj analogicky stanoví jeho nejmenší možná hodnota Nj . Platí tedy Nj ≤ zj ≤P
Ij . Pro
kriteriální ziskové funkce můžeme lehce odvodit jednoduchou horní hranici Ij = si=1 cij
a dolní hranici Nj = 0. Třetím odhadem kriteriální funkce zj je její realistický odhad
(„referenční hodnota“ ) Rj . Platí Nj ≤ Rj ≤ Ij .
Dostáváme se nyní k otázce, jak sestavit z jednotlivých dílčích zj (j = 1, 2, . . . , p)
společnou „skalarizující funkci“ , převádějící náš problém na monokriteriální optimalisaci.
Pro řešení úloh velkého rozsahu se osvědčila funkce
p X
Ij − zj h
σ(z, R) =
,
Ij − Rj
j=1
12
kde h > 0, a dále z = [z1 , z2 , . . . , zp ], R = [R1 , R2 , . . . , Rp ] . Řešení spočívá v nalezení
min σ(z, R) za výšeuvedených podmínek. Pro simultánní výběr stovek projektů při desítkách kriteriálních funkcí a desítkách zdrojových omezení se osvědčila heuristická „metoda
efektivního gradientu“ , přičemž z kompromisu mezi citlivostí metody a vlivem zaokrouhlovacích chyb vyplývá doporučení volby h = 4.
Takto stanovená skalarizující funkce je tedy v podstatě součtem měr relativních odchylek jednotlivých kriteriálních funkcí od jejich ideálních (nejvyšších hypoteticky možných) hodnot. Relativní odchylkou zde rozumíme odchylku vztaženou na jednotku intervalu dostatečně uspokojivých hodnot kriteriální funkce. Ze struktury jednotlivých sčítanců skalarizující funkce je tedy patrno, že váhově jsou preferovány ty z nich, u nichž
Rj je blízké k Ij .
Fuzzy dvoukriteriální optimalisaci tvorby časových rozvrhů projektů je třeba nastudovat ze zmíněných skript Metody operačního výzkumu 2001, str. 152–153. Vícekriteriální
výběr projektů, respektující synergické efekty druhého a třetího řádu a vzájemnou hierarchickou závislost projektů je popsán v práci Jindřich Klapka, Petr Piňos: Decision
Support System for Multicriterial R&D and Information Systems Projects Selection.
European Journal of Operational Research 140 (2002), str. 434–446.
13
20 Základní pojmy síťové analysy. Metoda kritické cesty.
Základní pojmy síťové analysy je třeba čerpat z přednášky. Zde připomenu alespoň tři
základní vzorce metody kritické cesty:
Nejdříve možný okamžik začátku zpracování činnosti, která vychází z uzlu j je dán vztahem:
i
(0)
tj
(0)
= max ti + yij ,
i
j
kde i jsou indexy bezprostředních předchůdců uzlu j, tj. uzlů, z nichž vystupují hrany
představující činnosti (i, j), yij je doba trvání činnosti (i, j).
Nejpozději přípustný okamžik ukončení činnosti, která vstupuje do uzlu i je dán vztahem:
(1)
ti
(1)
= min tj − yij ,
i
j
j
kde j jsou indexy bezprostředních následníků uzlu i, tj. uzlů, do nichž vstupují hrany
představující činnosti (i, j) vystupující z uzlu i, yij je doba trvání činnosti (i, j).
celková rezerva činnosti (i, j) je dána vztahem:
(1)
(0)
(1)
(0)
CRij = tj − ti + yij = tj − tj ,
tj. nejpozději přípustný okamžik ukončení činnosti (i, j) minus nejdříve možný okamžik
jejího ukončení.
14
Download

Pomocné texty pro přípravu ke státním zkouškám