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
