Differentsial rentalar usuli (Brudno usuli)

Differentsial rentalar usuli (Brudno usuli)

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=(x_ij) bazis echimga shunday ikki o’lchovli (nxm) jadval mos kelsinki, unda har bir x_ij 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.