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


Воšеалар ва операциялар резервлари учун формулалар. Критик йœлни аниšлаш алгоритми



Download 351,5 Kb.
bet3/4
Sana06.07.2022
Hajmi351,5 Kb.
#751248
1   2   3   4
Bog'liq
Algoritmlar

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


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


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

Pij - операциянинг бœш ваšт резерви: Мij=tj-ti-tij;


Pij – операциянинг бођланмаган ваšт резерви:
Дij=tj- -tij.
Энди тармоšдаги критик йœлни ва операциялар комплексининг тœлиš бажарилиш ваšти tn ни топишда ишлатиладиган Беллман-Калаба усули алгоритмини келтирамиз. Тармоš учлари а1,a2,...,an деб белгиланган бœлсин. Беллман-Калаба усули.
Ќар бир (i,j) U учун tij=- деб оламиз ва ихтиёрий i=1,2,...,n учун tii=0 деб ќисоблаймиз. Шундай
(8)
йœлни топиш талаб šилинадики,
(9)
йиђинди максимал бœлсин. Бу топилган (8) йœл критик йœлдан, (9) йиђинди эса критик ваšтдан иборат бœлади. (9) йиђиндининг максимал šиймати операциялар комплексининг тœлиš бажарилиш ваšти tn ни аниšлаб беради.
Критик йœлни аниšлаш учун šуйидаги системани ечиш етарлидир:
(10)
бу ерда -аi учдан охирги аn учгача бœлган оптимал (ваšт бœйича максимал) йœлга сарфланган критик ваšтни ифодалайди.
(10) системадан (8) критик йœлни šуйидаги алгоритм бœйича топиш мумкин:

  1. дастлаб

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


(14)

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


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

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

а1 ва а12 учларни туташтирувчи критик йœлни аниšлаш учун šàралаётган тармоšка мос 1-жадвални тœлдирамиз. Бу жадвалда i-сатр ва j-устунлар кесишган (i,j) катакда Pij операциянинг давом этиш ваšти tij ёзилган. Бунда, агар аi дан аj учга йуналган ёй мавжуд бœлмаса, tij=- деб олинган.
2-расм
Шу жадвалдан фойдаланиб, (11)-(14) формулалар асосида vi(1), vi(2),...,vi(k) сонларни ќисоблаймиз ва 2-жадвални тœлдирамиз.
(11) формулага кœра

v =t1,12=- , ,..., =- , v v v .


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


Download 351,5 Kb.

Do'stlaringiz bilan baham:
1   2   3   4




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish