Чизиқли дастурлашнинг транспорт масаласи
Режа:
Транспорт масаласининг қўйилиши ва унинг математик модели.
Ёпиқ транспорт масаласи
Бошланғич режалар тузиш усуллари.
Шимолий -Ғарбий усул.
Минимал қиймат усули
Транспорт масаласи – чизиқли дастурлашнинг алоҳида хусусиятли масаласи бўлиб бир жинсли юк ташишнинг энг тежамли режасини тузиш масаласидир. Бу масала хусусийлигига қарамай қўлланиш соҳаси жуда кенгдир. Масаланинг қўйилиши ва унинг математик модели
m-та Ai (i = 1,2,…, m) таъминотчиларда йиғилиб қолган бир жинсли ai миқдордаги маҳсулотни n-та Bj истеъмолчиларга мос равишда bj (j=1,2,…,n) миқдорда етказиб бериш талаб қилинади.
Ҳар бир i-таъминотчидан ҳар бир j-истеъмолчига бир бирлик юк ташиш йўл харажати маълум ва у cij – сўмни ташкил қилади.
Юк ташишнинг шундай режасини тузиш керакки, таъминотчилардаги барча юклар олиб чиқиб кетилсин, истеъмолчиларнинг барча талаблари қондирилсин ва шу билан бирга йўл харажатларининг умумий қиймати энг кичик бўлсин.
Масаланинг математик моделини тузиш учун i-таъминотчидан j-истеъмолчига етказиб бериш учун режалаштирилган юк миқдорини xij орқали белгилаймиз, у ҳолда масаланинг шартларини қуйидаги жадвал кўринишда ёзиш мумкин:
Таъминотчилар
|
Истеъмолчилар
|
Заҳиралар
|
|
B1
|
B2
|
…
|
Bn
|
|
A1
|
c11
x11
|
c12
x12
|
…
|
C1n
X1n
|
a1
|
A2
|
c21
x21
|
c22
x22
|
…
|
C2n
X2n
|
a2
|
…
|
…
|
…
|
…
|
…
|
…
|
Am
|
cn1
xn1
|
cn2
xn2
|
…
|
Cnm
xnm
|
am
|
Талаблар
|
b1
|
b1
|
…
|
b1
|
ai = bj
|
Жадвалдан кўринадики, i-таъминотчидан j-истеъмолчига режадаги xij – бирлик юк етказиб бериш йўл харажати cij xij – сўмни ташкил қилади. Режанинг умумий қиймати эса,
га тенг бўлади.
Масаланинг биринчи шартига кўра, яъни барча юклар олиб чиқиб кетилиши шарти учун
тенгликларга эга бўламиз;
иккинчи шартга кўра, яъни барча талаблар тўла қондирилиши учун
тенгликларга эга бўламиз;
Шундай қилиб масаланинг математик модели қуйидаги кўринишни олади:
чизиқли тенгламалар системасининг
(3) xij ? 0, i=1,2,…,m; j=1,2,…,n
шартларни қаноатлантирувчи шундай ечимини топиш керакки, бу ечим (3)
чизиқли функцияга энг кичик қиймат берсин.
Бу моделда
тенглик ўринли деб фараз қилинади. Бундай масалалар «ёпиқ моделли транспорт масаласи» дейилади.
Теорема. Талаблар ҳажми заҳиралар ҳажмига тенг бўлган исталган транспорт масаласининг оптимал ечими мавжуд бўлади.
Бошланғич таянч ечимни қуриш.
Маълумки, ихтиёрий чизиқли дастурлаш масаласининг оптимал ечимини топиш жараёни бошланғич таянч ечимини кўришдан бошланади.
Масаланинг (1) ва (2) системалари биргаликда mn – та номаълумли m+n – та тенгламаларда иборат. Агар (1) системанинг тенгламаларини ҳадма-ҳад қўшсак, ва алоҳида (2) системанинг тенгламаларини ҳадма-ҳад қўшсак, иккита бир хил тенглама ҳосил бўлади. Бу эса (1) ва (2) дан иборат системада битта чизиқли боғлик тенглама борлигини кўрсатади. Бу тенглама умумий системадан чиқариб ташланса, масала m+n-1 та чизиқли боғлиқ бўлмаган тенгламалар системасидан иборат бўлиб қолади. Демак, масаланинг бузилмайдиган таянч ечими m+n-1 та мусбат компоненталардан иборат бўлади.
Шундай қилиб, транспорт масаласининг бошланғич таянч ечими бирор усул билан топилган бўлса,
Do'stlaringiz bilan baham: |