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


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



Download 1,41 Mb.
bet9/27
Sana12.07.2022
Hajmi1,41 Mb.
#782060
1   ...   5   6   7   8   9   10   11   12   ...   27
Bog'liq
АТЖМ маъруза матни

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

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


Режани кетма-кет яхшилаш усулининг моҳияти шундан иборатки, тузилган бошланғич базис режадан бошлаб кейинги ҳар бир яхшиланган режада берилган чеклов шартлари бажарилади, яъни ҳар бир юк жўнатувчи ва қабул қилувчининг юк жўнатиш ва олиш ҳажми бажарилади, белгиланган мақсад функцияси Z эса (умумий транспорт иши ёки харажатлар ёхуд вақтлар) камаяди.
Чизиқли дастурлаштириш назариясида олинган ҳар қандай режанинг белгиланган мезон нуқтаи назаридан оптималлигини аниқлаш усули асослаб берилган. Агар олинган режа оптимал бўлмаса, уни шундай ўзгартириш йўли ҳам кўрсатилганки, натижада ўзгартирилган янги режада Z нинг қиймати олдинги режага нисбатан яхшиланади (агар мезон минималлаштиришни тақозо қилса камаяди ёки мезон максималлаштиришга қаратилган бўлса кўпаяди). Режанинг ҳар бир ўзгартириши билан бўлган операциялар итерация деб аталади ва чекланган сондаги итерациялардан кейин оптимал режани аниқлаш мумкин бўлади.
Энди бошланғич базис режанинг оптималлигини текшириб кўрамиз.
5-жадвалда келтирилган бошланғич базис режа учун матрицадаги юкланган катаклар сонини ҳисоблаймиз ва бу сон барча ui ва vj потенциалларни аниқлай олиш учун m+n-1 га тенг бўлиши керак, бу ерда m, n мос равишда матрицадаги қаторлар ва устунлар сони. Юқоридаги 4.5 жадвалдаги базис режа да юкланган катаклар сони 7та, m+n-1 қиймати эса 8. Демак, барча потенциалларни аниқлаш учун юкланган катаклар сонини 1 га кўпайтириш керак. Юкланган катаклар сонини юкламаларни қаторлар ёки устунлар бўйича силжитиш йўли билан ёки керакли катакка қиймати 0 га тенг шартли юклама бериш йўли билан кўпайтириш мумкин. Мазкур ўзгартиришни 4- жадвалда амалга оширамиз ва олинган янги бошланғич базис режани 5- жадвалга ўтказамиз. 4-жадвалда III.2 катакнинг юкламаси XIII.2=250 тоннани III.1 катакка ўтказамиз (бунда юкламани силжитиш қатор бўйича чапга, яъни III.2 катакдан III.1 катакка ўтказишдан иборатдир). Энди силжитиш натижасида устунларнинг bj қийматидаги ўзгаришларни тузатиш учун 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- жадвалда аниқланган бошланғич базис режанинг оптималлигини текшириш учун қаторлар ва устунлар потенциаллари Ui ва Vi лар қийматларини ҳисоблаймиз. Бунда матрицанинг ҳар бир юкланган катаги учун устун потенциали Vj ва қатор потенциали ui айирмаси (Vi –Ui) шу катак масофасига тенг бўлиши керак: Vj–Ui=lij. Мазкур тенгликдан фойдаланиб, потенциаллар қуйидагича аниқланади (5- жадвал).
Матрицанинг қай бир устуни потенциали Vj ни нолга тенг деб қабул қиламиз: айтайлик V1=0. Қолган потенциаллар қийматларини матрицанинг юкланган катаклари бўйича қуйидаги формулалар асосида аниқлаймиз:
- устунлар учун Vj = Uilij;
- қаторлар учун Ui = Vj + lij.
Биринчи устундаги V1=0 қиймати ва lII.1=9 км, lIII.1=6 км бўйича UII ИИ ва UIII қаторлар потенциалларини аниқлаймиз:
UII = V1+ lII.1 = 0+9 = 9; UIII = V1+ lIII.1 = 0+6 = 6.
Аниқланган UII ва UIII қийматларига асосланиб, j=2,3,4 устунларнинг потенциалларини ҳисоблаймиз:
V2 = UIIlII.2 = 9 – 8=1; V3 = UIIIlIII.3 = 6 – 5 =1; V4= UIII.4 lIII.4 = 6 – 8 = 2.
Шу тарзда UI, UIV, V5 потенциаллари қийматларини ҳам аниқлаймиз:
UI = V3+ l13 = 1 +8 = 9; UIV = V2+ lIV,2 = 1 + 1 = 2; V5 = U1+ lI,5 = 9 – 14 = –5.
Бошланғич базис режа учун барча Ui ва Vj потенциаллар аниқлангач мазкур режанинг оптималлигини текшириш мумкин. Бунинг учун матрицанинг барча юкланмаган катаклари учун қуйидаги шарт бажарилиши керак, яъни
Ui - Vjlij.
Агар қайси бир бўш катак учун юқоридаги шарт бажарилмаса, яъни унинг учун Ui - Vj > lij бўлса, бундай катаклар учун dij= Ui - Vj - lij сонининг қиймати аниқланади. Энди 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 катаклар учун оптималлик шартлари бажарилмади. Улар учун dij лар қийматларини ҳисоблаймиз:
d I,2=UII V2 l II,2=9–1–5=+3.
d II,2=UII –V5 lII,5=9+5–13=+1.
d III,2=UIII –V2lIII,2=6–1–4=+1.
Юқорида ҳисобланган dij қийматларини матрицанинг тегишли катакларига киритамиз ва уларни бошқа сонлардан фарқлаш учун доира ичига олиб қўямиз.( 5- жадвал). Бошланғич базис режада бундай катаклар мавжудлиги унинг ҳали оптимал эмаслигини ва катакни яхшилаш лозимлигини ифодалайди.
Олинган режани яхшилаш учун матрицада энг катта dij қийматига эга катак аниқланади (dI,3 = +3) ва шу катакдан бошлаб ёпиқ контур чизилади. Ёпиқ контур горизонтал ва вертикал чизиқлардан иборат бўлиб, унинг учлари юкланган катакларда ётади ва у танлаб олинган dij катакдан тўғри чизиқ (горизонтал ёки вертикал) кейинги юкланган катаккача ўтказилади, кейин эса тўғри бурчак остида тепага ёки пастга, ўнгга ёки чапга яна кейинги юкланган катаккача ўтказилади ҳамда шу тарзда ёпиқ контур ўзи
бошланган dI,3 катакка қайтиб келади. Ёпиқ контур кўриниши турлича бўлиши мумкин (3-расм).
Таъкидлаш лозимки, ёпиқ контурнинг учлари сони доимо жуфт сондан иборат бўлади. Бунда горизонтал ва вертикал чизиқлар кесишадиган катаклар контурнинг учлари ҳисобланмайди. Контурнинг учларида горизонтал ва вертикал чизиқлар фақат битта тўғри бурчакни ташкил этади.
5-жадвалда I,2 катакдан (dI,2=+3) бошлаб қурилган ёпиқ контур кўрсатилган, унинг учлари соат стрелкаси бўйича қуйидаги катаклардан ўтади:
I,2 - I,3 - III,3 - III,1- II,1 – II,2 – I,2.




3-расм. Ёпиқ контурнинг турли кўринишлари.
Энди ёпиқ контурнинг учларига унинг бошланғич dij қийматли учидан бошлаб кетма-кет равишда “ - “ ва “ + “ ишораларини бериб чиқамиз. Ёпиқ контурнинг “+“ ишораси билан белгиланган, контур учларидаги катакларнинг юкланган қийматларидан энг кичигини танлаб оламиз. Бизнинг мисолимизда бундай қийматлар III,1 катакда +250 ва II,2 катакда эса +250. Мазкур қийматни контур учлари бўйича “–“ ишораси билан белгиланган катаклардаги юкламалар қийматига қўшамиз ва “+“ ишорали катаклардагидан эса айирамиз. Натижада яхшиланган янги 1-режани оламиз (6- жадвал).
Кейинги босқичда такомиллашган режа учун яна Ui ва Vj потенциаллар қийматини аниқлаймиз ва улар асосида янгиланган режа оптималлигини текширамиз (4.6- жадвал). Бундай таҳлиллар асосида янгиланган режанинг икки катагида dij сони мавжудлигини топамиз. Улар dII,4=+2 ва dII,5=+4. Энг катта dij қийматга эга бўлган dII,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- режа учун яна Ui ва Vj потенциалларни аниқлаймиз ва бўш катакларда оптималлик шарти Ui - Vjlij нинг бажарилишини текширамиз. Таҳлиллар натижасида II,4 бўш катак учун оптималлик шарти бажарилаётганини аниқлаймиз. Бу катак учун dij параметр қийматини ҳисоблаймиз: dII,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


Download 1,41 Mb.

Do'stlaringiz bilan baham:
1   ...   5   6   7   8   9   10   11   12   ...   27




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