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

4. Режани кетма-кет яхшилаш усули

Бошланғич базис режани қай усул билан тузилганига қарамй оптимал режа дейиш мумкин эмас. Аввало унинг оптималлигини текшириш ва режа оптимал бўлмаса, яхшилаш, яъни оптималлик томон ўзгартириш лозим бўлади. Базис режани бундай яхшилаш учун махсус усул – режани кетма-кет яхшилаш усули ишлаб чиқилган.

Режани кетма-кет яхшилаш усулининг моҳияти шундан иборатки, тузилган бошланғич базис режадан бошлаб кейинги ҳар бир яхшиланган режада берилган чеклов шартлари бажарилади, яъни ҳар бир юк жўнатувчи ва қабул қилувчининг юк жўнатиш ва олиш ҳажми бажарилади, белгиланган мақсад функцияси Z эса (умумий транспорт иши ёки харажатлар ёхуд вақтлар) камаяди.
Чизиқли дастурлаштириш назариясида олинган ҳар қандай режанинг белгиланган мезон нуқтаи назаридан оптималлигини аниқлаш усули асослаб берилган. Агар олинган режа оптимал бўлмаса, уни шундай ўзгартириш йўли ҳам кўрсатилганки, натижада ўзгартирилган янги режада Z нинг қиймати олдинги режага нисбатан яхшиланади (агар мезон минималлаштиришни тақозо қилса камаяди ёки мезон максималлаштиришга қаратилган бўлса кўпаяди). Режанинг ҳар бир ўзгартириши билан бўлган операциялар итерация деб аталади ва чекланган сондаги итерациялардан кейин оптимал режани аниқлаш мумкин бўлади.
Энди бошланғич базис режанинг оптималлигини текшириб кўрамиз.
5-жадвалда келтирилган бошланғич базис режа учун матрицадаги юкланган катаклар сонини ҳисоблаймиз ва бу сон барча u_i ва v_j потенциалларни аниқлай олиш учун m+n-1 га тенг бўлиши керак, бу ерда m, n мос равишда матрицадаги қаторлар ва устунлар сони. Юқоридаги 4.5 жадвалдаги базис режа да юкланган катаклар сони 7та, m+n-1 қиймати эса 8. Демак, барча потенциалларни аниқлаш учун юкланган катаклар сонини 1 га кўпайтириш керак. Юкланган катаклар сонини юкламаларни қаторлар ёки устунлар бўйича силжитиш йўли билан ёки керакли катакка қиймати 0 га тенг шартли юклама бериш йўли билан кўпайтириш мумкин. Мазкур ўзгартиришни 4- жадвалда амалга оширамиз ва олинган янги бошланғич базис режани 5- жадвалга ўтказамиз. 4-жадвалда III.2 катакнинг юкламаси X_III.2=250 тоннани III.1 катакка ўтказамиз (бунда юкламани силжитиш қатор бўйича чапга, яъни III.2 катакдан III.1 катакка ўтказишдан иборатдир). Энди силжитиш натижасида устунларнинг b_j қийматидаги ўзгаришларни тузатиш учун II.1 катакнинг юкламаси х_II.1=400 дан 250 та сини II.2 катакка (ўнг томонга) силжитамиз ва бунда х_II.2= 250, х_II.1=400 – 250 = 150 тонна бўлади.

5-жадвал.

Бошланғич базис режанинг оптималлигини текшириш

	J	1	2	3	4	5
i	Vi Ui	0	1	1	-2	-5	ai
I	9	17	5 +3	8 600+	12	14 100	700
II	9	9 150	+ 8 250	13	12	13 +1	400
III	6	6 +250	4 +1	5 200–	8 400	14	850
IV	2	2	1 150	4	10	11	150
	bi	400	400	800	400	100	2100

Юқоридаги силжитишлардан кейин бошланғич базис режадаги юкланган катаклар сони m+n-1=8 тага тенг бўлди. Энди олинган бошланғич базис режа учун мақсад функцияси – бажарилиши лозим бўлган транспорт ишининг умумий ҳажмини ҳисоблаймиз:

Кейинги босқичда 5- жадвалда аниқланган бошланғич базис режанинг оптималлигини текшириш учун қаторлар ва устунлар потенциаллари U_i ва V_i лар қийматларини ҳисоблаймиз. Бунда матрицанинг ҳар бир юкланган катаги учун устун потенциали V_j ва қатор потенциали u_i айирмаси (V_i –U_i) шу катак масофасига тенг бўлиши керак: V_j–U_i=l_ij. Мазкур тенгликдан фойдаланиб, потенциаллар қуйидагича аниқланади (5- жадвал).
Матрицанинг қай бир устуни потенциали V_j ни нолга тенг деб қабул қиламиз: айтайлик V₁=0. Қолган потенциаллар қийматларини матрицанинг юкланган катаклари бўйича қуйидаги формулалар асосида аниқлаймиз:
- устунлар учун V_j = U_i – l_ij;
- қаторлар учун U_i = V_j + l_ij.
Биринчи устундаги V₁=0 қиймати ва l_II.1=9 км, l_III.1=6 км бўйича U_{II ИИ} ва U_III қаторлар потенциалларини аниқлаймиз:
U_II = V₁+ l_II.1 = 0+9 = 9; U_III = V₁+ l_III.1 = 0+6 = 6.
Аниқланган U_II ва U_III қийматларига асосланиб, j=2,3,4 устунларнинг потенциалларини ҳисоблаймиз:
V₂ = U_II – l_II.2 = 9 – 8=1; V₃ = U_III – l_III.3 = 6 – 5 =1; V₄= U_III.4 – l_III.4 = 6 – 8 = 2.
Шу тарзда U_I, U_IV, V₅ потенциаллари қийматларини ҳам аниқлаймиз:
U_I = V₃+ l₁₃ = 1 +8 = 9; U_IV = V₂+ l_IV,2 = 1 + 1 = 2; V₅ = U₁+ l_I,5 = 9 – 14 = –5.
Бошланғич базис режа учун барча U_i ва V_j потенциаллар аниқлангач мазкур режанинг оптималлигини текшириш мумкин. Бунинг учун матрицанинг барча юкланмаган катаклари учун қуйидаги шарт бажарилиши керак, яъни
U_i - V_j ≤ l_ij.
Агар қайси бир бўш катак учун юқоридаги шарт бажарилмаса, яъни унинг учун U_i - V_j > l_ij бўлса, бундай катаклар учун d_ij= U_i - V_j - l_ij сонининг қиймати аниқланади. Энди 5-жадвалнинг бўш катаклари учун юқоридаги оптималлик шарти бажарилишини текширамиз:
ij=I,1 да ( 9-0)<17; I,2 да (9-1)>5; I,4 - ( 9+2)<12; II,3 - (9-1)<13;
II,4 – (9+2)<12; II,5 – (9+5)>13; III,2 – (6-1)>4 ; III,5 – (6+5)<14 ;
IV,1 – (2-1)≤ 2; IV,3 – (2-1)<4; IV,4 – (2-4)≤ 10; IV,5 – (2+5)<11.
Кўриниб турибдики, I,2; II,5 ва III,2 катаклар учун оптималлик шартлари бажарилмади. Улар учун d_ij лар қийматларини ҳисоблаймиз:
d _I,2=U_II – V₂ – l _II,2=9–1–5=+3.
d _II,2=U_II –V₅– l_II,5=9+5–13=+1.
d _III,2=U_III –V₂–l_III,2=6–1–4=+1.
Юқорида ҳисобланган d_ij қийматларини матрицанинг тегишли катакларига киритамиз ва уларни бошқа сонлардан фарқлаш учун доира ичига олиб қўямиз.( 5- жадвал). Бошланғич базис режада бундай катаклар мавжудлиги унинг ҳали оптимал эмаслигини ва катакни яхшилаш лозимлигини ифодалайди.
Олинган режани яхшилаш учун матрицада энг катта d_ij қийматига эга катак аниқланади (d_I,3 = +3) ва шу катакдан бошлаб ёпиқ контур чизилади. Ёпиқ контур горизонтал ва вертикал чизиқлардан иборат бўлиб, унинг учлари юкланган катакларда ётади ва у танлаб олинган d_ij катакдан тўғри чизиқ (горизонтал ёки вертикал) кейинги юкланган катаккача ўтказилади, кейин эса тўғри бурчак остида тепага ёки пастга, ўнгга ёки чапга яна кейинги юкланган катаккача ўтказилади ҳамда шу тарзда ёпиқ контур ўзи
бошланган d_I,3 катакка қайтиб келади. Ёпиқ контур кўриниши турлича бўлиши мумкин (3-расм).
Таъкидлаш лозимки, ёпиқ контурнинг учлари сони доимо жуфт сондан иборат бўлади. Бунда горизонтал ва вертикал чизиқлар кесишадиган катаклар контурнинг учлари ҳисобланмайди. Контурнинг учларида горизонтал ва вертикал чизиқлар фақат битта тўғри бурчакни ташкил этади.
5-жадвалда I,2 катакдан (d_I,2=+3) бошлаб қурилган ёпиқ контур кўрсатилган, унинг учлари соат стрелкаси бўйича қуйидаги катаклардан ўтади:
I,2 - I,3 - III,3 - III,1- II,1 – II,2 – I,2.




3-расм. Ёпиқ контурнинг турли кўринишлари.
Энди ёпиқ контурнинг учларига унинг бошланғич d_ij қийматли учидан бошлаб кетма-кет равишда “ - “ ва “ + “ ишораларини бериб чиқамиз. Ёпиқ контурнинг “+“ ишораси билан белгиланган, контур учларидаги катакларнинг юкланган қийматларидан энг кичигини танлаб оламиз. Бизнинг мисолимизда бундай қийматлар III,1 катакда +250 ва II,2 катакда эса +250. Мазкур қийматни контур учлари бўйича “–“ ишораси билан белгиланган катаклардаги юкламалар қийматига қўшамиз ва “+“ ишорали катаклардагидан эса айирамиз. Натижада яхшиланган янги 1-режани оламиз (6- жадвал).
Кейинги босқичда такомиллашган режа учун яна U_i ва V_j потенциаллар қийматини аниқлаймиз ва улар асосида янгиланган режа оптималлигини текширамиз (4.6- жадвал). Бундай таҳлиллар асосида янгиланган режанинг икки катагида d_ij сони мавжудлигини топамиз. Улар d_II,4=+2 ва d_II,5=+4. Энг катта d_ij қийматга эга бўлган d_II,5=+4 катагидан бошлаб ёпиқ контур чизамиз. Контурнинг шакли ва учлари 6- жадвалда кўрсатилган. Контурнинг “+“ ишораси билан белгиланган учларидаги катаклар юкламаларидан энг кичик қийматга эга катакни белгилаймиз (х_I,5=100) ва бу қийматни “+“ ишораси қўйилган катаклар юкламаларидан айирамиз, “–“ ишора билан белгиланган юкламаларига қўшамиз. Натижада яхшиланган 2- режани аниқлаймиз.

6-жадвал
Яхшиланган 1- режа

	J	1	2	3	4	5
i	Vi Ui	2	3	0	-3	-6	ai
I	8	1 7	5 250	8 350	12	14 + 100	700
II	11	9 400	8	13	12	13	400
III	5	6	4	5 450	8 400	14	850
IV	4	2 0	+ 1 150	4	10	11	150
	bi	400	400	800	400	100	2100

Бу режа 7- жадвалда келтирилган. Яхшиланган 2- режа учун яна U_i ва V_j потенциалларни аниқлаймиз ва бўш катакларда оптималлик шарти U_i - V_j ≤ l_ij нинг бажарилишини текширамиз. Таҳлиллар натижасида II,4 бўш катак учун оптималлик шарти бажарилаётганини аниқлаймиз. Бу катак учун d_ij параметр қийматини ҳисоблаймиз: d_II,4=(13+1)-12.

Ана шу катакдан бошлаб ёпиқ контур чизамиз, уларнинг учларига “+“ ва “–“ ишораларини берамиз, “+“ ишорали юкламалар ичидан энг кичиги х_IV,2=+50 ни белгилаймиз ва бу қийматни барча “–“ ишорали юкламаларга қўшамиз ва “+“ ишорали юкламалардан айирамиз. Натижада кейинги такомиллашган режани оламиз (7- жадвал).
Режанинг оптималлигини текширишга оид юқорида баён этилган операцияларни яна олинган янги режа учун бажарамиз. Бунинг натижасида маълум бўладики, 8- жадвалдаги режанинг ҳамма бўш катакларида оптималлик шарти бажарилади.

7- жадвал

Яхшиланган 2-режа

	J	1	2	3	4	5
i	Vi Ui	4	5	2	-1	0	ai
I	10	17	5 350	8 350	12	14	700
II	13	-9 300	+ 8	13	12 +2	13 100	400
III	7	6	4	5 450	8 400	14	850
bj	6	2 100	+ 1 50	4	10	11	150
	bj	400	400	800	400	100	2100

8- жадвал

Оптимал юк оқимлари режаси

	J	1	2	3	4	5
i	Vi Ui	4	7	4	1	0	ai
I	12	17	5 400	8 300	12	14	700
II	13	-9 250	8	13	12 50	13 100	400
III	9	6	4	5 500	8 350	14	850
bj	6	2 150	1	4	10	11	150
	bj	400	400	800	400	100	2100