III тарау. Үлестіру түріндегі есепті моделдеу

Осыған дейін көптеген сызықтық программалау есептерінің ішінен симплекстік әдіспен шешуі сондай қиындық туғызбайтын арнайы есептерді ғана қарастырдық. Осыған байланысты симплекс әдіспен шешуі күрделі болатын есептер үшін арнайы әдістер құрастырылған. Мұндай шешуі қиын есептердің бірі транспорттық есептер. Транспорттық есептер үлестіру есептер класына жатады [2-8, 10, 11].

Транспорттық есептің математикалық моделі және оның бірінші тіреулік жоспарын табу әдістері

I. Транспорттық есептің экономикалық қойылымы.

m жабдықтаушысында қандай да бір () біртекті өнім бар болсын. Осы өнімді n тұтынушыға () көлемінде жеткізу қажет. i пунктінен j пунктіне дейін жүктің тасымалдау құны белгілі. Тұтынушыларды толық қанағаттандыратындай етіп, барлық жүкті тасудың құны минимальды болатын тиімді жоспарды табу керек.

II. Есептің математикалық моделі

Айталық, х_ij–i-жабдықтаушыдан j- тұтынушы пунктіне жіберілетін жүк бірлігінің саны болсын. Онда есеп шартынан келесі жүйені аламыз:

(3.1)

(3.2)

(3.3)

(3.4)

(3.1) – (3.4) - транспорттық есептің классикалық математикалық моделі болады.

Анықтама 3.1. (3.2) және (3.3) шарттарын қанағаттандыратын

кез-келген матрица транспорттық есептің тіреулік жоспары деп аталады.

Анықтама 3.2. (3.1) мақсаттық функциясына ең аз мән беретін, транспорттық есептің () тіреулік жоспары тиімді жоспар деп аталады.

Тұжырым. Транспорттық есептің шешілуі үшін келесі шарттың орындалуы қажетті және жеткілікті:

, (3.5)

яғни, экономикалық мағынасы бойынша «сұраныс» = «ұсыныс».

Анықтама 3.3. (3.5) шарты бар транспорттық есеп жабық модель деп аталады, ал керсінше жағдайда ашық модель болады.

Транспорттық есептің қасиеттері.

1. Тек (3.5) шарты орындалған жағдайда ғана, (3.1)-(3.4) транспорттық есептің тиімді шешімі бар болады.

2. Егер және -бүтін сандар болса, онда транспорттық есептің оптималды шешуінің координаталары да бүтін болады.

3. (3.1)-(3.4) транспорттық есептің шарттарының векторлық жүйесінің рангісі (m+n-1) тең болады, мұндағы m-жабдықтаушылар саны, n-тұтынушылар саны.

III. Транспорттық есептің бірінші тіреулік жоспарын табу әдістері.

Бірінші тіреулік жоспарды табудың бірнеше әдістері бар: «Cолтүстік-батыс бұрыш» әдісі, ең кіші құн әдісі (минимальдық тариф) және басқалар.

Бұл әдістердің мағынасы мынада жоспарды тізбектеп (n+m-1) қадам бойынша табуға болады. Мұндағы әрбір қадамында есеп шарттарының кестесіндегі бір тор толтырылады, оны бос емес деп атайды.

Транспорттық есептің шешуін келесі мысал түрінде қарастырайық [6].

1-мысал. Есептің экономикалық қойылымы. Біртекті жүк екі қоймада сақталған. Бұл жүкті үш тұтынушыға жеткізу қажет. Тасымалдау тарифтері С матрицасы түрінде берілген. Қоймадағы жүк қорлары және қажетті жүк мөлшерлері сәйкесінше А және В векторлар түрінде берілген.

Жалпы транспорттық шығын ең аз болатындай етіп берілген жүкті тасымалдау жоспарын табу керек.

Шешуі. – і пунктінен j пунктіне дейін таситын жүк саны. Онда есептің шарты бойынша математикалық модель келесі түрде жазылады

(3.1) формуланың қасиеті бойынша мақсаттық функция келесі түрде болады:

(3.2) және (3.3) формуласынан шектеулер жүйесі келесі түрдегідей болады:

(3.4) формуланың қасиетінен болатындығын көреміз.

Бірінші тіреулік жоспарды «солтүстік-батыс бұрыш» әдісімен табамыз.

Таблицаны толтыруды х₁₁белгісіз торынан бастаймыз, яғни бірінші тұтынушының қажеттілігін бірінші жабдықтаушының қоры арқылы қанағаттандыруға тырысамыз.

3.1-кесте

Жабдықтаушы	Тұтынушы			Қор
Жабдықтаушы	В₁	B₂	B₃	Қор
А₁	4 30	1 20	3	50
А₂	2	3 10	5 40	50
Қажеттілік	30	30	40	100

В₁ пунктінің қажеттілігінен, A₁ пунктінің қоры көп болғандықтан, х₁₁=30 болады, бұл мәнді сәйкесінше 3.1 кестенің сәйкес торына жазамыз және уақытша В₁ бағанын қарастырмаймыз. Бұл жағдайда А₁ пунктіндегі қордың мәні 20 тең екендігін ескереміз.

Енді А₁ бірінші пунктінен В₂ тұтынушыға жіберілетін жүкті анықтаймыз. В₂ тұтынушының қажеттілігі А₁ пунктіндегі қордан көп._.x₁₂ = 20 деп алып, оны 3.1 кестедегі сәйкес торға жазамыз және А₁ жолын уақытша қарастырмаймыз.

Енді х₂₂ белгісізінің торын толтыруға көшеміз. А₂ жабдықтаушының қоры В₂ тұтынушының қажеттілігінен көп болғандықтан х₂₂=10 деп алып, оны 3.1-кестенің сәйкес торына жазамыз және В₂ бағаның уақытша қарасытрмаймыз. Бұл жағдайда А₂ жабдықтаушысының қоры 40 ш.б. Сонымен 40 ш.б. қажеттілігі бар бір тұтынушы В₃ және 40 ш.б. қоры бар бір жабдықтаушы қалады. Оны х₂₃=40 деп алып, 3.1-кестедегі сәйкес торға жазамыз.

Нәтижесінде бірінші тіреулік жоспарды аламыз

Бұл тіреулік жоспардағы мақсаттық функцияның мәнің келесі түрде есептеймәз: бос емес тордағы жүктердің саның сәйкес тарифке көбейтіп қосамыз. Онда

Ең кіші құн әдісінің мәңі тордағы ең кіші тарифті таңдауға негізделген.

Бірінші тіреулік жоспарды ең кіші құн әдісімен табайық.

Бастапқы берілгендерді 3.2-кестеге жазамыз. Ең кіші құн 1-ге тең және ол х₁₂ айнымалысына сәйкес келеді. х₁₂=30 деп алып, оны 3.2-кестенің сәйкес тоорына жазамыз және В₂ бағаның уақытша қарастырмаймыз. А₁ жабдықтаушысының қоры 20-ға тең болады. Келесі ең кіші құн 2-ге тең. А₂ жабдықтаушысының қоры В₁ тұтынушының қажеттілігінен көп. Сондықтан х₂₁=30 деп алып, оны 3.2-кестесінің сәйкес торына жазамыз және В₁ бағаның уақытша қарастырмаймыз. Тура осылай қалған торларды толытармыз.

Таблица 3.2

Жабдықтаушы	Тұтынушы			Қор
Жабдықтаушы	В₁	B₂	B₃	Қор
А₁	4	1 30	3 20	50
А₂	2 30	3	5 20	50
Қажеттілік	30	30	40	100

Онда бірінші тіреулік жоспар келесі түрде болады:

Бұл жағдайда мақсаттық функцияның мәні келесі түрде болады: