Differentsial rentalar usuli (Brudno usuli)


Download 102.89 Kb.
Sana30.06.2020
Hajmi102.89 Kb.

Differentsial rentalar usuli (Brudno usuli)
Rus olimi A.L.Lure 1959 yilda transport masalasini echish uchun optimal echimga shartli optimal echimlar ¸rdami bilan yaqinlashish usulini yaratdi. A.L.Brudno bu usulni modifitsirlab (o’zgartirib), uni differentsial rentalar usuli deb ataydi. Differentsial rentalar usuli va shartli optimal echimlar bilan yaqinlashish usulining g’oyasi bir xil bo’lishiga qaramay, ular bir-biridan farq qiladi. Ular orasidagi asosiy farq shundan iboratki, differentsial rentalar usuli elektron hisoblash mashinasida qo’llanish uchun qulay bo’lib, shartli optimal rejalar ¸rdami bilan yaqinlashish usuliga nisbatan ikki marta kam vaqt talab qiladi.

Ma’lumki, transport masalasini potentsiallar usuli bilan echishda eng avval ishlab chiqarilgan hamma mahsulot to’la taqsimlanadi, ya’ni bazis reja topiladi. So’ngra topilgan bazis reja optimal rejaga ketma ket yaqinlashtirilib boriladi. Differentsial rentalar usulida esa dastlab mahsulotning bir qismi taqsimlana-

di, lekin taqsimlangan mahsulot optimal rejaning qismini tashkil qiladi. Echish jara¸ni mahsulot to’la taqsimlanguncha davaom ettiriladi.

Differentsial rentalar usulining algoritmini ko’rishdan avval ba’zi qo’shimcha tushunchalar bilan tanishchamiz.

Faraz qilaylik, X=(xij) bazis echimga shunday ikki o’lchovli (nxm) jadval mos kelsinki, unda har bir xij bazis o’zgaruvchi joylashgan katakchaga belgi (kvadratcha) qo’yilgan bo’lsin.

1-ta’rif. Agar belgi o’zining ustunida (qatorida) yagona bo’lsa, u tartiblanuvchi deb ataladi. Berilgan jadvaldagi belgilarning har birini quyidagi algoritm yordamida tartiblash mumkin bo’lsa, bu belgilar sistemasi tartiblanuvchi deb ataladi.

Belgilarni tartiblash uchun transport jadvalining birinchi ustunidan boshlab tartib bilan barcha ustunlar qarab chiqiladi va belgilarga 1 nomerdan boshlab tartib nomerlar qo’yiladi. Qarala¸tgan ustunda (qatorda) yagona nomerlanmagan belgi qatnashsa unga navbatdagi tartib nomeri qo’yiladi, aks holda bu ustundagi (qatordagi) belgilar vaqtincha nomerlanmay o’tkazib yuboriladi. Belgilar ustunlar bo’yicha nomerlanib bo’lmagan holda 1-qatordan boshlab nomerlanish tatibi davom ettiriladi. Shunday qilib, belgilarning hammasi nomerlanguncha ketma-ket ustun va qator bo’ylab belgilar qarab chiqiladi.



Lemma. Ikki o’lchovli (nxm) jadvaldagi belgilar sistemasi tartiblanuvchi bo’lishi uchun bu jadvalning ixti¸riy (n'xm') qismidagi belgilar soni n'+m'-1 ta bo’lishi zarur va etarlidir.

Zarurligi. Faraz qilaylik, belgilar sistemasi tartiblanuvchi bo’lsin. U holda berilgan (nxm) jadvalning ixti¸riy (n'xm') qismi kamida bitta nomerlanuvchi belgini o’z ichiga olishini isbot qilish mumkin. (n'xm') jadvalda bitta ham nomerlanuvchi belgi bo’lmasin deylik. U holda bu jadvalning har bir ustun va qatorida kamida ikitadan belgi joylashgan bo’ladi, ya’ni (n'xm') jadvaldagi belgilar sistemasi ham tartiblanuvchi bo’lmaydi. Demak, bunday zidlikda (nxm) jadvaldagi belgilar sistemasi ham tartiblanuvchi bo’lmaydi, chunki tartiblanuvchi belgilar sistemasini o’z ichiga olgan jadvalning ixti¸riy qismidagi belgilar sistemasi ham tartiblanuvchi bo’lishi kerak.

Etarliligi. Faraz qilaylik, (nxm) jadvalning ixti¸riy (n'xm') qismi kamida bitta nomerlanuvchi belgini o’z ichiga olsin. Bu holda (n'xm') jadvaldagi hamma belgilarni va demak, (nxm) jadvaldagi belgilarni birin-ketin nomerlash mumkin bo’ladi.

Transport masalasini differentsial rentalar usuli bilan echish uchun masalaning berilganlarini ushbu jadvalga joylashtiramiz



bi

ai

b1

b2

...

bn

a1

c11

1

c12

...

c1n

x11

a2

c21

c22

2

...

c2n

x22

...

...

...

...

...

am

cm1

cm2

...

cmn

n

xmn

So’ngra quyidagi ishlarni amalga oshiramiz.







  1. Har bir j, ( j 1, n)

uchun


min cij=ckj (5.24)

i

topiladi va (k,j) katakchaning yuqori o’ng burchagiga belgi (kvadratcha) kiritiladi. Agarda j-ustunda (5.24) shartni qanoatlantiruvchi cij lar bittadan ko’p bo’lsa, u holda ulardan faqat bittasiga mos keluvchi katakchaga belgi kiritiladi.



  1. Yuqoridagi algoritm bo’yicha belgilar nomerlanadi.

  2. Birinchi nomerli belgidan boshlab, tartib bilan har bir belgi joylashgan (k,l) katakchaga mahsulot taqsimlanadi


Xkl=min (ak,bl)
Agar blk bo’lsa, xkl=bl bo’ladi va ak ning qiymati ak-bl ga o’zgaradi. Agarda akl bo’lsa,

xkl=ak bo’lib, bl ning qiymati bl-ak ga o’zgaradi.

  1. Har bir j-ustun uchun


x ,
m


b
t (t )

j ij

i1

(5.27)

ya’ni j-iste’mol qiluvchi punktga keltirilgan mahsulotlar yig’indisi topiladi, bu erda t-tsiklning nomeri.

  1. Ustun xarakteristikasi (y.x.) topiladi. Agar j-ustun uchun


b

j

j
t b

bo’lsa, ya’ni j-punktning mahsulotga bo’lgan talabi qondirilmagan bo’lsa, u holda jadvaldagi ustun xarakteristikasi (y.x.) ni ifodalovchi qatorda j-ustun uchun (-) ishora qo’yiladi.



  1. Qator xarakteristikasi (q.x) topiladi buning uchun belgilarni teskari tartibda bir marta qarab chiqib, minus ishorali ustundagi belgi joylashgan qatorga minus ishora qo’yiladi.

Agar belgi minus ishorali i-qatorda joylashgan bo’lib, bu belgi joylashgan (i,j) katakchadagi xij>0 bo’lsa, j-ustunga ham minus ishora qo’yiladi. Hamma belgilarni bir marta qarab chiqqandan so’ng qolgan qator va ustunlarga plyus ishora qo’yiladi.

  1. Har bir minus ishorali j-ustun uchun differentsial renta

  min cc[]
j i ij ij

topiladi, bu erda c - plyus ishorali qatordagi transport xarajatlarini va c[] - belgisi bor katakchadagi



ij ij

transport xarajatini ko’rsatadi.



  1. min j i

k

shartni qanoatlantiruvchi k-ustundagi minimal xarajat joylashgan (l,k)





katakchaga qo’shimcha belgi kiritiladi. So’ngra yangi tsiklga o’tiladi. Yangi tsiklga o’tish uchun yana jadval tuziladi. Yangi jadvalga ai, bj lar va musbat ishorali qatordagi cij lar oldingi jadvaldan o’zgarmasdan ko’chirildi. Minus ishorali qatordagi transport xarajatlari (cij) ga k qo’shiladi, ya’ni

(cij )'  cij   k .

Yangi jadvalga belgilar nomersiz ko’chiriladi. Agar birorta j-ustunda ikkita belgi joylashgan bo’lib ulardan biri musbat qatorda, ikkinchisi esa minus ishorali qatorda ¸tsa, minus ishorali belgi yangi jadvalga ko’chirilmaydi.

Yangi tsikl belgilarni nomerlashdan boshlanadi va yuqoridagi 2-8 punktlarda qilingan ishlar yana qaytadan takrorlanadi. Bunday takrorlanish masalaning optimal echimi topilguncha, ya’ni



b

j j
barcha j lar uchun b t

yoziladi.

Faraz qilaylik,

tenglik bajarilguncha davom etadi. So’ngra masalaning optimal echimi



x*11, x*21, ..., x*mn

masalaning optimal echimi bo’lsin, u holda bu echimdagi umumiy transport xarajatlari quyidagiga teng bo’ladi:
Ymin=c11x*11+c21x*21+...+cmnx*mn


bi

ai

200

200

100

100

250

q.X.

100

10

7

4

1

4

4

+

100

250

2

1

7

10

6

11

+

200

200

8

5

2

3

3

2

2

5

-

200

0

0




300

11

8

12

16

13

+

b1j

200

200

0

100

0




U.X.

+

-

-

+

-




j




2

1




2

 min=1



Misol. Differentsial rentalar usuli bilan quyidagi masalani echamiz. I.



II.


bi

ai

200

200

100

100

250

q.X.

100

10

7

4

5

1

3

4

-

0

100

250

2

1

7

3


10

6

11

+

200

200

9

6

2

4

6

3

3

4

-

200

0

0




300

11

8

12

16

13

+

b2j

200

200

0

100

0




U.X.

+

-

-

-

-




j



1

6

5

8

 min=1

III.


bi

ai

200

200

100

100

250

q.X.

100

11

8

5

4

2

2

5

-

0

100







250

2

1

7

5

10

6

11

-

200

50













200

10

7

6

5

7

4

4

3

-

0

0




200




300

11

8

12

16

13

+

b3j

200

50

0

100

200




U.X.

-

-

-

-

-




j

9

1

7

14

9

 min=1






bi

ai

200

200

100

100

250

q.X.

100

12

9

6

4

3

2

6

-

0

100

250

3

1

8

5

11

7




12

+

200

0




200

1

8

6

6

5

5

3

-

0

200

300

11

8

4

12

16

13

+

200

b4j

200

200

0

100

200




U.X.

+

+

-

-

-




 j







5

4

7

 min=4


V.

bi

ai

200

200

100

100

250

q.X.

100

16

13

10

6

7

7

10

-

100

0







250

3

1

8

5

11

7

8

12

-

200

0




50







200

15

12

10

3

9

9

2

-

0

200

300

11

8

4

12

16

13

+

200

b5j

200

200

100

50

200




U.X.

-

+

-

-

-




j

8



2

9

4

 min=2

VI.

bi

ai

200

200

100

100

250

q.X.

100

18

15

12

7

9

8

12

+

0

50

250

5

1

10

13

9

4

14

+

200

50

200

17

14

12

5

11

11

3

-

0

200

300

11

8

2

12

6

16

13

+

200

100

b6j

200

200

100

100

200




U.X.

+

+

+

+

-




j













1

 min=1

VII.

bi

ai

200

200

100

100

250

q.X.

100

18

15

12

6

9

7

12

8




0

50

50

250

5

1

10

13

9

3

14




200

50

200

18

15

13

12

12

4




200

300

11

8

2

12

5

16

13




200

100

b7j

200

200

100

100

250




U.X.


















Shunday qilib, VII tsiklda optimal echim topildi. Masalaning javobini ¸zish uchun topilgan optimal rejani dastlabki jadvalga joylashtiramiz:




10

7

4

0


1

50


4

50


2

200


7

10

6

50


11

8

5

3

2

2

200


11

8

200


12

100


16

13

Optimal reja

x14=50, x15=50, x15= 0 x21=200, x24=50, x35=200,

x42=200, x43=100, Ymin=150+450+650+2200+2200+8200+12100=4150
Download 102.89 Kb.

Do'stlaringiz bilan baham:




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2020
ma'muriyatiga murojaat qiling