11-маъруза воšÅа ва операциянинг ваšт резервлари ќамда критик алгоритмлар. ЭЌтимолли тармоšлар

2. Воšеалар ва операциялар резервлари учун формулалар. Критик йœлни аниšлаш алгоритми. n та учга (воšеага) эга тармоš графиги берилган бœлсин. (i,j) деб i- учдан чиšиб j—учга кирувчи ёйни белгилаймиз. (i,j) ёй P_ij операция билдиради. P_ij операция (i)-воšеадан (j)-воšеага олиб келади. t_i ва - (i)-воšеанинг кутилаётган ва чегаравий ваšт моментлари бœлсин. U деб тармоšдаги барча ёйлар (операциялар) тупламини белгилаймиз.U^-_j- j-учга кирувчи ёйлар тœплами,
U_i⁺- i-учдан чиšувчи ёйлар тœплами, бœлсин. У ќолда:


, (4)
(5)
формулалар œринлидир, бу ерда t_n- операциялар комплексининг тœлиš бажарилиш вакти.
Тармоšнинг 1-номерли (бошланђич) учини j-номерли учи билан туташтирувчи йœллар тœпламини деб, j-номерли учни n-номерли (охирги) учи билан туташтирувчи йœллар тœпламини эса деб белгилаймиз. У ваšтда t_j ва ларни (4) ва (5) формулалар œрнига šуйидаги формулалар билан ќам ќисоблаш мумкин:
, (6)


. (7)
(4), (5) (ёки (6), (7)) формулалар билан t_j, ваšтлар ќисоблангандан сœнг воšеа ва операцияларнинг ваšт резервларини топамиз:
(i)- воšеа ваšт резерви: -t_i;
P_ij – операциянинг тœла ваšт резерви: S_ij = t -t_i-t_ij;

P_ij - операциянинг бœш ваšт резерви: М_ij=t_j-t_i-t_ij;

P_ij – операциянинг бођланмаган ваšт резерви:
Д_ij=t_j- -t_ij.
Энди тармоšдаги критик йœлни ва операциялар комплексининг тœлиš бажарилиш ваšти t_n ни топишда ишлатиладиган Беллман-Калаба усули алгоритмини келтирамиз. Тармоš учлари а₁,a₂,...,a_n деб белгиланган бœлсин. Беллман-Калаба усули.
Ќар бир (i,j) U учун t_ij=- деб оламиз ва ихтиёрий i=1,2,...,n учун t_ii=0 деб ќисоблаймиз. Шундай
(8)
йœлни топиш талаб šилинадики,
(9)
йиђинди максимал бœлсин. Бу топилган (8) йœл критик йœлдан, (9) йиђинди эса критик ваšтдан иборат бœлади. (9) йиђиндининг максимал šиймати операциялар комплексининг тœлиš бажарилиш ваšти t_n ни аниšлаб беради.
Критик йœлни аниšлаш учун šуйидаги системани ечиш етарлидир:
(10)
бу ерда -а_i учдан охирги а_n учгача бœлган оптимал (ваšт бœйича максимал) йœлга сарфланган критик ваšтни ифодалайди.
(10) системадан (8) критик йœлни šуйидаги алгоритм бœйича топиш мумкин:

1. 
   дастлаб
   

(11)
деб оламиз.
2)Кейин
(12)
šийматларни ќисоблаймиз.
3) Кейинги šадамларда
(13)
šийматларни топамиз (k=2,3,...).
Бирор k (k>2) учун


(14)

бœлиб šолса, ќисоблашлар тœхтатилади.

v бу сонларнинг энг каттаси бœлиб, у (9) максимал йигиндига тенг (v_n^(k)=0 бœлиши равшан). v_i^(k)(i=1,2,...,n) сонларни камайиш тартибида ёзамиз:

Уларга мос учлар (ёйлар) кетма-кетлиги (8) критик йœлни аниšлаб беради.
Агар тармоšдаги учлар сони n бœлса k=n-2 итерациядан сœнг критик йœл аниšланади.
Келтирилган Беллман-Калаба усулининг šœлланишига доир мисол šàраймиз.
2-расмда ифодаланган тармоš графиги берилган бœлсин. Унда ќар бир ёй устида операцияларнинг давомийлигини билдирувчи сонлар ёзилган. Тармоš учлари а₁,а₂,...,а₁₂ деб белгиланган.

а₁ ва а₁₂ учларни туташтирувчи критик йœлни аниšлаш учун šàралаётган тармоšка мос 1-жадвални тœлдирамиз. Бу жадвалда i-сатр ва j-устунлар кесишган (i,j) катакда P_ij операциянинг давом этиш ваšти t_ij ёзилган. Бунда, агар а_i дан а_j учга йуналган ёй мавжуд бœлмаса, t_ij=- деб олинган.
2-расм
Шу жадвалдан фойдаланиб, (11)-(14) формулалар асосида v_i⁽¹⁾, v_i⁽²⁾,...,v_i^(k) сонларни ќисоблаймиз ва 2-жадвални тœлдирамиз.
(11) формулага кœра

v =t_1,12=- , ,..., =- , v v v .

Бу топилган сонлар 2-жадвалда k=1 га мос биринчи сатрни тулдиради.
Иккинчи сатрга (12) формула буйича ќисобланадиган v_i⁽²⁾ сонлар ёзилади: