Транспорт логистикаси” кафедраси

1-хусусият. Агар транспорт масаласининг ёпиқ модели берилган
( ) бўлса, унинг биринчи m та тенгламалари йиғиндиси кейинги n та тенгламалар йиғиндисига тенг бўлади, улар ҳар қандай тенгламани қолган тенгламалар орқали ифодалаш мумкин.
2-хусусият. Транспорт масаласи моделини маълум матрица - жадвал кўринишида ҳам ифодалаш мумкин, бунда X_ij ўзгарувчи қийматлари ij матрицанинг i- қатори ва j -устини кесишишида ҳосил бўлган катакларда, биринчи m тенгламалар эркин ҳадларининг қийматлари a_i - охирги устинда колган n тенгламалар учун - b_j эса - охирги каторда берилади (2-жадвал).
3-хусусият. Транспорт масаласида доимо m+n -1 сондан катта бўлмаган X_ij оқимлар қийматларини ўз ичига олувчи ечим мавжуддир ва у Базавий ечим деб аталади.
Транспорт масаласининг чизиқли дастурлашни умумий масаласини ечувчи ҳар қандай усулда ечиш мумкин. Аммо унинг хусусиятларини ҳисобга олган ҳолда масалани ечишни, яъни катта сондаги мумкин бўлган ечимлар ичидан оптимал ечимни аниқлашни махсус усуллари ишлаб чиқилган.

2- жадвал

Транспорт масаласининг матрица кўриниши

j i	1	2	…	j	…	n	ai
1	l11 X11	l12 X12	…	lij X1j	…	l1n X1n	a1
2	l21 X21	l22 X22	…	l2j X2j	…	l2n X2n	a2
…	…	…	…	…	…	…	…
i	li1 Xi1	li2 Xi2	…	lij Xij	…	lin Xin	ai
…	…	…	…	…	…	…	…
m	lm1 Xm1	lm2 Xm2	…	lmj Xmj	…	lmn Xmn	am
bj	b1	b2	…	bj	…	bn	∑ai=∑bj

Транспорт масаласининг ечишнинг махсус усуллари турли тамойилларга асосланган бўлиб, улардан энг кўп тарқалгани сифатида ечим (режани)ни кетма-кет яхшилаш усулини кўрсатиш мумкин.

Мазкур усулда биринчи навбатда дастлабки базис режа (ечим) тузилади, кейин унинг оптималлиги текширилади. Агар режа оптимал бўлмаса, у яхшиланади ва такомилашган режанинг оптималлиги текширилади. Режани кетма-кет яхшилаш амалиёти оптимал ечим олгунча давом эттирилади.


3. Бошланғич базис режани тузиш усуллари

Бошланғич базис режани тузишнинг кўплаб усуллари мавжуд. Улардан энг кенг тарқалганлари қуйидагилар:

- минимал l_ij (C_ij) элемент усули;
- икки ёқлама афзал кўриш усули;
- абсолют икки ёқлама афзал кўриш усули ва бошқалар.
Минимал элемент усули билан бошланғич базис режа қуриш куйидаги босқичларни ўз ичига олади;
1. Масофалар (ёки таннархлар) матрицасида масофа l_ij лар ичида энг кичик қийматга эга бўлгани ни аниқлаймиз. Айтайлик, бундай қийматга эга бўлган катак r, s индекслари билан белгиланган бўлсин.
2. Биринчи базис ўзгарувчи X_rs нинг қиймати сифатида матрицанинг r- қаторидаги юк жўнатиш a_r ва s - устундаги қабул қилиш b_S ҳажмининг энг кичигини танлаб оламиз:

3. X_rs ўзгарувчига тегишли қиймат берилганидан сўнг ёки r- катор
(агар a_r < b_s бўлса) ёки S- устун (агар a_r b_s бўлса) кейинги қарашлардан олиб ташланади. Агар a_r = b_s бўлса, унда ёки r-қатор ёки s- устун кейинги қарашлардан олиб ташланади.
4. X_rs ўзгарувчига қиймат олганлиги муносабати билан a_r ва b_S параметрларнинг дастлабки қийматлари ўзгаради ва уларнинг янги қийматлари ( ) қуйидагича аниқланади:
(агар бўлса) ,
(агар булса ).

1. 
   Кўриш учун қолган катаклар ичидан энг кичик масофалисини
   

( ) яна танлаймиз ва мазкур катакни юкловчи базис ўзгарувчиси қийматини юқоридаги 2-бандда келтирилган қоидага мувофиқ аниқлаймиз.
Энди абсолют икки ёқлама афзал кўриш усули моҳиятини келтирамиз. Бунда қуйидаги босқичлар бажарилади:
1. Ҳар бир i қаторда минимал қийматга, яьни бўлган катак топилади. Бундай катакни * шакли билан белгилаймиз.
2. Энди ҳар бир j устунда қийматга эга катакни аниқлаймиз ва бундай катакларни ҳам * шакли билан белгилаймиз.
3. Икки марта шундай белги ** қўйилган катаклардан энг кичик қийматлисини аниқлаймиз ва уни қиймат билан юклаймиз. Матрицадан i қаторини, агар a_ij бўлса ёки j устунини, агар a_i>b_j бўлса ўчирамиз ва мазкур қатор (ёки устун) катаклари бундан кейинги процедураларда қаралмайди.
4. Агар қатор ўчирилган бўлса, унда устунлар бўйича қийматли катакни аниқлаймиз ва уни * шакли билан белгилаймиз.
5. Агар устун ўчирилган бўлса, унда қаторлар бўйича қийматли катакни аниқлаймиз ва уни * шакли билан белгилаймиз.
6. Яна ** шакли билан белгиланган катакни мумкин бўлган қиймат билан юклаймиз.
Юқоридаги 4-6-операциялар, барча юк олиш ва жўнатиш эҳтиёжлари қондирилгунча давом эттирилади.
Энди юқоридаги усуллардан биринчиси – минимал элементлар усули ёрдамида бошланғич базис режани қуриш мисолини кўриб чиқамиз. 3-жадвал – матрицада келтирилган маьлумотлар асосида юк оқимларини оптималлаштириш масаласининг дастлабки базис режаини тузамиз.
Матрица катаклари ичида энг кам l_ij қийматли катакни, яьни ни аниқаймиз. Бундай катак II, 4 катаги бўлиб унда ни ташкил этади. Бу катакни юклаймиз : =min (500, 200) = 200. Юклаш натижасида 4-устунга мос 4 исьтемолчининг юк олишга бўлган эҳиёжи қондирилди. Шу туфайли 4-устин кейинги қарашлардан чиқарилади. юклама берилганлиги муносабати билан параметрнинг янги қийматини аниқлаймиз:

Матрицадаги энг кичик l_ij қийматли катакни яна аниқлаймиз: l_III,1=10 км , кейин эса III,1 катакка уни юклаш қиймати тоннани берамиз. Энди i=III қатор учун a_III нинг янги қийматини аниқлаймиз:
минг тонна.
Энди яна минимал l_ij масофали катакларни белгилаймиз: l_I,3=l_II,5=20. Катакни юклашни I.3 дан бошлаймиз. Бунинг учун юкловчи қийматни аниқлаймиз: . Биринчи қатор эҳтиёжи қондирилганлиги туфайли уни ўчирамиз. X_I,3=100 юкловдан кейин i=3 устуннинг b₃ параметри янги қийматини ҳисоблаймиз: .
3- жадвал.
Минимал элемент усули билан базис режа тузиш.

j i	1	2	3	4	5	ai (минг тонна)
I	40	30	20 100	40	30	100
II	60	50	40 100	5 200	20 200	500
III	100 300	30 300	40 100	50	60	700
bj	300	300	300	200	200	1300 1300

Кейинги босқичда базис ўзгарувчиси X_II,5 нинг қийматини аниқлашга ўтамиз: . Кейинги таҳлилларда j=5- устун қаралмайди, чунки унинг эҳтиёжи b₅=200 тўла-тўкис қондирилди. a_II параметрининг янги қиймати тонна бўлади.

Матрицада кўриш учун қолган l_ij масофалардан энг кичик қийматлисини аниқлаймиз . Демак, бундай масофа l_III,2=30 км. Мазкур катакка юклаш ҳажмини аниқлаймиз: X_III,2 = min ( )=min(400,300)=300 тонна. Шундай қилиб i=2 устуннинг эҳтиёжи b_j=300 тонна қондирилди ва уни ўчирамиз. Энди колган II,3 ва III,3 катакларга мос равишда X_II,3= =100 ва X_III,3= тонна қийматларни юклаймиз, (4.3 жадвал)
Юк оқимларини оптималлаштириш масаласининг даcтлабки базис режасини бошқа усул - аболют икки ёқлама афзал кўриш усули билан ечиш усулини 4- жадвал мисолида кўриб чиқамиз.
4.4 жадвалдаги матрицанинг l_ij масофалари орасида қатор ва устунлар бўйича энг кичик l_ij ларни * шакли билан белгилаймиз. Натижада битта IV, 2 катак икки ёқлама афзаллик ** шаклига эга эканлигини аниқлаймиз. Мазкур катак учун юклаш қиймати X_IV,2 =150 тонна бўлади. Юклаш натижасида i=IV қаторнинг эҳтиёжи a_IV=150 қондирилди ва бу қатор катаклари бошқа қаралмайди. Энди устунлар бўйича қийматларни аниқлаймиз: l_III,1=6 км; l_III,2=4км; l_III,3=5км; l_III,4=8км; l_II,5=13км. Уларни * шакли билан белгилаб чиқамиз. Маьлум бўлдики, III,2 ва III,4 катакларида икки ёқлама афзаллик ** шакли мавжуд. Улардан кичик l_ij га эга бўлган III,2 катакни юклаймиз, яьни X_III,2=250 т. Кейин эса III,4 катакни юкловчи қийматни аниқлаймиз, яьни x_III,4=400 т. Юклашлар натижасида j=2,4 устунлар эҳтиёжи таьминланганлиги боис уларни ўчирамиз.
4 жадвал
Абсолют икки ёклама афзал кўриш усули билан базис режани қуриш

j i	1	2	3	4	5	ai
I	17	 5	 8 600	12	14 100	700
II	 9 400	 8	13	12	 13	400
II	 6	 4 250	 5 200	 8 400	14	850
IV	 2	 1 150	 4	10	 11	150
bj	400	400	800	400	100	2100 2100

Қаторлардаги min l_ij ларни белгилаймиз; l_I,3=8 км; l_II,1=9 км; l_III,3=5км. Уларни * шакли билан ифодалаймиз III,3 катакда икки ёқлама афзаллик белгиси ** борлигини аниқлаймиз ва уни юклаймиз X_III,3=200 т, l=III қаторни бошқа қарамаслик учун ўчириб ташлаймиз.

Энди устунлар бўйича min l_ij қийматларини ахтарамиз. Улар L_II,1=9 км; l_I.3=8км; l_II,5=13 км эканлигини аниқлаймиз. Айни пайтда бу катаклар , яъни II,1; I,3; II,5 катаклар ** шакли билан белгиланганига ва улар орасида l_I,3 энг кам қийматга эга эканлигига амин бўламиз. I,3 катакни юклаймиз : X_I,3=600. Кейин эса X_II,1=400 эканлигини топамиз. Охирги юклов I,5 катагига X_I,5=100 қийматга амалга оширилади.