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

3-мавзу: ЧИЗИҚЛИ ПРОГРАММАЛАШТИРИШНИНГ ТРАНСПОРТ МАСАЛАСИ. ЮК ОҚИМЛАРИНИ ОПТИМАЛЛАШТИРИШ

Режа:

1. 
   Чизиқли программалаштиришнинг транспорт масаласи умумий тушунчаси
   
2. 
   Масаланинг қўйилиши ва математик модели
   
3. 
   Бошланғич базис режани тузиш усуллари
   
4. 
   Режани кетма-кет яхшилаш усули
   

Таянч сўз ва иборалар:

1. 
   Чизиқли программалаштириш транспорт масаласининг умумий тушунчаси
   

Транспорт масаласи иқтисодий-математик усуллар ичида энг кенг тарқалгани ва кўп қўлланиладиганидир. Бу масала чизиқли программалаштиришнинг қадимий усули бўлиб, “транспорт” сўзи шартли равишда ишлатилади. Чунки ишлаб чиқаришга тегишли бўлган ҳар қандай масалани матрица ҳолига келтирилса, матрицанинг устуни (қаторлари)да жойлаштириладиган объектлардан бирини юк жўнатувчи, иккинчисини қабул қилувчи деб фараз қилиш лозим бўлиб қолади. Демак ўз-ўзидан “юк ташиш” сўзини “транспорт” сўзи билан алмаштириш мумкин. Бир хил юк юборувчи пунктларни қабул қилувчи пунктларга оптимал бириктириш масаласи “транспорт масаласининг худди ўзгинаси, аммо у ерда масалалага ишлаб чиқариш нуқтаи назаридан ёндошилади.

Математика фани нуқтаи назаридан қаралганда эса масалани умумий қилиб “транспорт масаласи” деб юритилади ва бунинг остида фақат юк ташиш эмас, балки бошқача ҳар қандай, лекин матриқа кўринишига келадиган ишлаб чиқариш масалалари тушунилади.

2. 
   Масаланинг қўйилиши ва математик модели
   

Юк оқимларини оптималлаштириш масаласи чизиқли дастурлаштиришнинг классик транспорт масаласи кўринишида қўйилиши ва унинг математик модели билан ифодаланиши мумкин. Бунда транспорт масаласини умумий қўйилиши ва унинг модели қуйидагича шаклланади.

Бир турдаги юк жўнатувчи i манзиллари (i=1,2,…,n), улардан юборилувчи юк ҳажми a_i ва юк қабул қилувчи j объектлар (j=1,2,…m), уларнинг истеъмол ҳажми b_j ҳамда ҳар бир i жўнатувчидан j-олувчига юк етказиш масофаси l_ij ёки вақти t_i ёки 1 т юк ташиш таннархи (S_ij) берилган. Ҳар бир i-жўнатувчидан ҳар бир j-қабул қилувчига юбориладиган юк оқимлари X_ij нинг шундай қийматларини аниқлаш лозимки, бунда қуйидаги шартлар бажарилсин:
(1)
барча оқимлар мусбат қийматларга эга бўлиши керак;
(2)
­­­­­­­­­­­­­ Ҳар бир i жўнатувчидан барча j олувчиларга ( ) юбориладиган юк оқимлари йиғиндиси унинг юк жўнатиш имконияти a_i га тенг бўлиши лозим;
(3)
Хар бир j олувчига барча i жўнатувчиларидан ( ) юбориладиган юк оқимлари йиғиндиси уни юк қабул қилиш эҳтиёжи bj га тенг бўлиши керак;
min (4)
умумий ташиш харажатлари ёки
min (5)
бажарилган умумий транспорт ишининг миқдори ёки
min (6)
ташишни бажаришга сарфланган умумий вақт энг кам миқдорда бўлиши керак.
Агар юқоридаги модел учун юборилувчи юк оқимларини йиғиндиси истеъмол этилувчи оқимлар йиғиндиси га тенг бўлса, яьни = унда у ёпиқ модел, аксинча улар ўзаро тенг бўлмас, яьни _> ёки _< бўлса, унда у очиқ модел бўлади.
Транспорт масаласи ўзининг маълум хусусиятларига эга.