Ишдан мақсад: Транспорт тизими: транспорт масаласини потенциаллар усули ёрдамида ечиш ва тахлил килиш

Сэвиджнинг минимакс мезони. Бу мезон ҳам худди Валд мезони каби ута пессимистик мезон хисобланади. Бу мезон буйича ута ёмон шароитларда таваккал қийматининг минимумини таъминлайдиган стратегияни танлаш тавсия этилади:
(5)
Гурвиц мезони. Бу мезон – умумлашган максимум мезони деб юритилади. У қуйидаги кўринишга эга:

бунда . коэффициент қандайдир вазиятларни эътиборга олган ҳолда танланади. Кўриниб турибдики, да Гурвиц мезони Вальднинг пессимистик мезонига, да эса ўта оптимистик мезонга айланади ( да )
Энди шу мезонларнинг қўлланишга доир мисоллар қараймиз.
4-мисол. Ўйиннинг ютуқлар матрицаси 3-жадвалда берилган. Лаплас принципини қўллаб И ўйинчи оптимал стратегияси топилсин.

3-жадвал

Т И	Т1	Т2	Т3	Т4
А1	1	3	1	4
А2	4	1	3	2
А3	3	1	3	1
А4	3	0	2	3

(3) формулага кўра Қ₁= Қ₂= Қ₃= Қ₄= . У вақтда а₁=(1+3+1+4)/4=2,25; а₂=(4+1+3+2)/4=2,5; а₃=(3+1+3+1)/4=2; а₄=(3+0+2+3)=2.

Ютуқнинг максимал ўртача қиймати а=
Демак, табиат ҳолатлари эҳтимоллари бир хил бўлганда 3-жадвал билан берилган ўйинда А₂ стратегия оптимал бўлади.
Агар табиат стратегиялари уларни муқаррарлиги камайиб бориш тартибида жойлаштирилганда Т₃, Т₁, Т₂, Т₄ кетма-кетликни ҳосил қилса, уларни янгидан Т₁¹, Т₂¹, Т₃¹, Т₄¹ деб белгилаб, ютуқлар матрицаси 4-жадвал кўринишда бўлган ўйинга келамиз.
4-жадвал

Т И	Т1^|	Т2^|	Т3^|	Т4^|	āи
А1	1	1	3	4	1,7
А2	3	4	1	2	2,8
А3	3	3	1	1	2,3
А4	2	3	0	3	2,0

(4) формуладан фойдаланиб, н=4 учун Қ₁^|= ; Қ₂^|= , Қ₃^|= , Қ₄^| = бўлишини топамиз. ўртача ютуқлар 4-жадвалнинг охирги устунида келтирилган. Бу устун элементларидан , ни ва И ўйинчининг оптимал А₂ стратегиясини топамиз.
5-Мисол. Универмаг раҳбарияти А турдаги молдан буюртма бермокда. Бунда молга бўлган талаб 6 дан 9 бирликката оралиқда эканлиги маълум. Агар буюртма буйича олинган мол талабни қондириш учун етарли бўлмай қолса раҳбарият етишмай қолган молга шошилинч буюртма бериши ва олиб келиш мумкин. Агар талаб молнинг мавжуд миқдоридан кам бўлса, сотилмаган мол универмаг омборида сақланади.
Молга бериладиган буюртманинг шундай ҳажмини топиш керакки, бунда агар бир бирлик молни омборда сақлаш харажати 10 сўмни, шошилинч буюртма бериш ва олиб келиш харажати эса 20 сўмни ташкил этса, омборда сақлаш ва шошилинч буюртма бериш билан боғлиқ қўшимча чикимлар минимал бўлсин.
Ушбу мисолда харидорлар талаби иккинчи ўйинчи сифатида намоён бўлмокдаки, унинг стратегиялари – талаб миқдорлари Т₁=6 бирлик, Т₂=7 бирлик, Т₃=8 бирлик, Т₄=9 бирлик билан белгиланади.
И ўйинчи стратегиялари – универмаг раҳбариятининг буюртмалари А₁=6, А₂=7, А₃=8, А₄=9 бирлик мол миқдоридан иборат.
Ўйиннинг тўлов матрицаси 5-жадвалда келтирилган. 5-жадвал

^Т И	Т1= 6	Т2= 7	Т3= 8	Т4= 9	āи
А1=6	0	-20	-40	-60	-60
А2=7	-10	0	-20	-40	-40
А3=8	-20	-10	0	-20	-20
А4=9	-30	-20	-10	0	-30

Матрица элементларини ҳисоблашда фақат молни омборда сақлаш ва шошилинч олиб келиш билан боғлиқ қўшимча чиқимлар эътиборга олинган. Масалан, буюртма 8 мол бирлигига, талаб эса 7 бирликка тенг бўлганда 1 бирлик молни омборда сақлаш харажатлари 10 сўмни ташкил этади. Буюртманинг худди шу ҳажмида талаб 9 бирликка тенг бўлса, у ҳолда етишмаган 1 бирлик молни шошилинч олиб келиш учун қилинадиган харажат 20 сўмни ташкил этади.
Ўйиннинг ечимини Валд, Сэвиж ва =0,2 да Гурвиц мезонлари бўйича топамиз.
А) Валд мезонини қўллаш. и=1,2,3,4 элементларни топамиз ва уларни 5-жадвал-нинг қўшимча устунига ёзиб қўямиз. лардан энг каттаси =-20, яъни .
Демак, А₃-оптимал стратегиядир, яъни молдан 8 бирлик буюртма бериш керак.
В) Сэвиж мезонини қўллаш. Ютуқлар матрицаси асосида таваккалар матрицасини тузамиз (6-жадвал) ва қўшимча устунга максимал тавакалларни жойлаштирамиз.
6-жадвал

^ИИ И	Т1= 6	Т2= 7	Т3= 8	Т4= 9
А1=6	0	20	40	60	60
А2=7	10	0	20	40	40
А3=8	20	10	0	20	20
А4=9	30	20	10	0	30

(5) формулага кура р_и сонлардан минималини топамиз: .
Демак, Сэвиж мезони бўйича ҳам А₃ – оптимал стратегия бўлар экан.
С) Гурвиц мезонини қўллаш. 7-жадвал тўлов матрицасининг ўнг томонидаги учта устунга қуйидаги баҳоларни ёзиб қўямиз: а_и =мин а_иж , W_и =мах а_иж, ҳ_и= а а_и+(1- ) W_и
^{ж ж}
7-жадвал

ИИ И	Т1= 6	Т2= 7	Т3= 8	Т4= 9	Wи	āи	ҳи
А1=6	0	-20	-40	-60	0	-60	-12
А2=7	-10	0	-20	-40	0	-40	-8
А3=8	-20	-10	0	-20	0	-20	-4
А4=9	-30	-20	-10	0	0	-30	-6

=0,2 да ҳ_и нинг қийматларидан энг каттаси ҳ₃=-4 бўлиб, у А₃ стратегияга мосдир.

Демак, қаралаётган мисол учун ечим қуйидагича: универмаг раҳбарияти 8 бирлик молга буюртма бериш учун ҳамма асосга эга, чунки учала мезон ҳам масалани, А₃ стратегия фойдасига ҳал қилинмокда Гурвиц мезони буйича 0а а а1 бўлганда А₃ стратегия оптимал бўлишини қўриш қийин эмас. Факат а=0 (ўта оптимизм)дагина ҳамма стратегиялар тенг кучлидир.

4-лаборатория иши. Объектни моделлаштириш ва тартиблашни ўрганиш


Ишдан мақсад: Жадваллар назарияси масаласи. Джонсон алгоритми


Масалани қўйилиши: Жадваллар назарияси масаласи. Джонсон алгоритмидан фойдаланиб масалани операцияларни оптимал тартиблаш
Назарий қисм.


Ишни бажариш тартиби.

1. 
   Бир машина учун жадвал тузиш масаласи. Масалани ечиш алгоритми.
   
2. 
   Кетма-кет хизмат килувчи бир неча машиналар учун жадвал тузиш масаласи.
   
3. 
   Икки машина учун жадвал тузиш масаласини ечиш алгоритми (Джонсон алгоритми).
   

1. Бир машина учун жадвал тузиш масаласи. Жадваллар назариясида осон хал килинадиган, амалий жихатдан мухим булган бир катор масалалар мавжуд. Бир машина учун жадвал тузиш масаласи бунга мисол була олади. Шундай масаланинг «машина – операция» терминида куйилишини караб чикамиз.
Фараз килайлик, бир машинада бажарилиши учун бир вактда
операциялар берилган булсин. Хар бир операцияни машинада бажариш вакти хам берилган. Машинада операцияларни бажариш жадвалини тузиш масаласи деганда операцияларни бажаришнинг шундай тартибини аниклашни тушунамизки, бунда кандайдир самарадорлик критерияси оптимал киймат кабул килсин.
Бундай масалани хал килиш алгоритми самарадорлик критериясига бођлик булади.
Куйидаги критерияни караймиз:
, бунда – операцияни бажариш учун кутишга кетган вакт бирлигига бођлик булган жарима микдори (ёки операцияни бажариш учун керакли булган маблађ киймати),
– операциянинг кечикиши ,
,
– операцияни тугатиш вакти, – операцияни тугатиш учун керакли булган директив вакт.
Кўпчилик масалаларда га минимал қиймат берадиган жадвал тузиш талаб килинади.


Масалани ечиш алгоритми.
Дастлабки кадам. Барча операцияларни бажариш вакти Т ни аниклаймиз ва биринчи кадамга утамиз.
Биринчи кадам. Тартибланмаган операциялар ичидан шундай - операцияни топамизки, булсин, бунда . Бу ерда факат тартибланмаган индексли операциялар учун аникланади. Иккинчи кадамга утамиз.
Иккинчи кадам. номерли операцияни каралаётган операциялар тупламининг энг охирида бажарамиз. – операцияни бошка карамаймиз, яъни уни операциялар тупламидан чикарамиз. Агар операциялар туплами буш булса, масала ечилди. Акс холда, Т ни га алмаштириб, биринчи кадамга кайтамиз.
Биринчи ва иккинчи кадамларни марта кайтаргандан сунг критерий буйича оптимал жадвал тузилади.
2. Кетма-кет хизмат килувчи курилма (машина) лар учун жадваллар тузиш масаласи.
Кетма-кет хизмат килувчи курилма(машина)лар учун жадвал тузиш масласининг умумий холини караб чикамиз.
тупламдан иборат операциялар та машиналарда бажарилиш керак. – операцияни машинада бажариш вакти , аввалдан берилган. Операцияларни бажариш тартиби турли ишлар учун бир хил хам, турли хил хам булиши мумкин. Машиналарнинг бекор туриш вактлари йиђиндиси минимал буладиган операцияларни бажариш тартиби жадвалини тузиш масаласи жадваллар назарияси масаласидан иборатдир.
Исталган жадвални тузишда, хусусан оптимал жадвал тузишда куйидаги шартлар каноатлантирилиши керак:

1. 
   Хар бир машинада исталган вакт моментида биттадан ортик иш бажарилмайди.
   
2. 
   Белгиланган вакт моментида бир иш факат битта машинани банд килади.
   

Умумий холда оптимал жадвал тузиш коидаси йук. Шунинг учун машиналар сони иккита булган холни караймиз. Хар бир иш иккита операциядан ташкил топган булиб, улар олдин биринчи машинада, кейин иккинчи машинада мос равишда ва вактларда бажарилади.
Джонсон алгоритми.