Жүк тасымалдау есебінің негізгі ұғымы

«Түркістан гуманитарлық-техникалық колледжі» МКҚК
арнайы пәндер оқытушысы
Абилхаирова Меруерт Абилхаирқызы

Жүкті  тасымалдау туралы есептің жалпы қойылымы мынадай. Біртектес жүкті жүк жіберуші пункттер А₁, А₂, ..., А_n мен жүкті қабылдаушы пункттер В₁, В₂, ..., В_m-ге жеткізудің ең тиімді жоспарын табу қажет. Ең тиімді жоспардың критериі ретінде берлық жүкті тасуға кететін шығынның ең аз болуы немесе барлық жүкті тасуға кететін уақыттың аз болуы. Біз қарастыратын жүк тасымалы туралы есепте ең тиімді жоспардың критериі ретінде барлық жүкті тасуға кететін шығынның барынша аз болуы. Мынадай белгілеулер енгізейік.

С_ij – тариф. Жүкті A_i пунктінен B_j пуктіне жеткізуге кететін шығын.

a_i – жүктің қоры. A_i пуктінде

b_j – жүкке сұраныс. B_j пунктінде

x_ij – жүк мөлшері. A_i пунктінен B_j пунктіне жеткізетін жүк мөлшері.

Сонда жүк тасымалы туралы есептің математикалық қойылымы мынадай болады:

           (1)

шарттары

Сызықты программалаудың жүк тасымалдау есебі экономиканың әр түрлі құбылыстары мен процестерді зерттеуге және теориялық ізденістерде кеңімен қолданылады. Әсіресе бұл есептер өнеркәсіп және ауыл шаруашылық өнімдерін тасымалдаудың ұтымды жоспарын анықтау үшін жиі қолданылады.

Егер есептің берілуі бойынша барлық жабдықтаушылардағы (тасымалдаушы) жүк қорларының қосындысы мен тұтынушылардың қажеттіліктерінің (сұраныс) қосындысы тең болатын болса, яғни ∑a_i=∑b_j, онда бұл жүк тасымалдау есебі жабық есеп деп аталады. Егер ∑a_i≠∑b_j, онда жүк тасымалдау есебі ашық деп аталады.

 Егер ∑a_i>∑b_j, онда жалған тұтынушы енгізу арқылы ашық жүк тасымалдау есебінен өтуге болады, бұл кезде осы барлық жабдықтаушыдан жасанды тұтынушыға апаратын жүктердің 1 данасына кететін шығын, яғни c_n+1j=0 және керісінше.

Егер ∑a_i<∑b_j, онда жасанды жабдықтау пайда болады, ол тұтынушы жүгінің көлемі a_m+1=∑b_j-∑a_i

Жүк тасымалдау жоспары келесі талаптарға сай болу тиіс:

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

Сызықты программалау есебінің симплекс әдісімен ең тиімді жоспарын іздегендей жүк тасымалы туралы есептің ең тиімді жоспарын табу үшін әуелі оның тірек жоспарын анықтау қажет. Ол үшін жоғарыда айтқандай солтүстік-батыс бұрыш әдісі, ең кіші элементтер әдісі немесе Фогел әдісі қолданылады. Бұл әдістердің неізгі идеясы мынада: тірек жоспары n+m- 1 қадам жаслғаннан кейін табады. Және әрбір қадам сайын есептің шарты жазылған кестенің бір торы ғана толтырылады. Оны бос емес тор деп атайды. Бір торды толтырудың нәтижесінде жүк қабылдаушы бір пункттің қоры толғанымен тасылып әкелінеді.

Бірінші жағдайда толтырылған торы бағананы әрі қарай қарастырмайды. Нәтижесінде есептің шарты жазылған кестеде бір бағананың саны кемиді, бірақ жолдардың саны өзгеріссіз қалады, соның нәтижесінде жіберуші пунттің біреуінде жүктің қоры өзгереді. Екінші жағдайда толтырылған кесте орналасқан бір жолды әрі қарай қарастырмайды, нәтижесінде есептің шарты жазылған кетенің жолдарының саны бірге азаяды да, бағаны өзгермейді.

Осылайша n+m- 2 қадам жасалғаннан кейін шыққан есепте бір ғана жүк қабылдаушы болады. Ал толтырылған тордың саны да біреу ғана болады. Толтырылған бір тордың n+m-1 қадам жасап толтырылғаннан кейін жүк тасымалы туралы есептің тірек жоспары табылады. Қабылдаушы пукттің қажеттілігі, жіберуші пункттің қорына тең болуы мүмкін. Осы жағдайда жолды немесе бағананы уақытша қарстырмаймыз (екеуінің біреуін). Осыған сәйкес жіберуші пунктің қоры немесе берілген қабылдаушы пункттің қажеттіліктері нолге тең деп санауға болады. Осы нолді кезкекті толтырып жатқан торға жазады. Жоғарыда көрсетілген шарттар тірек жоспарының компоненттері тұратын  n+m- 1 бос емес торын табуға кепілдеме береді. Тиімді жоспарын табу және соңғысының тиімділігін тексеру бастапқы шарты болып табылады.  

Есеп 1. Төрт мекеме өнім дайындау үшін шикізат ресурстарының үш түрін пайдаланады. Әр мекеменің шикізат ресурстарына деген сұранысы сәйкесінше 120, 50, 190 және 110 бірлік. Шикізат ресурстарының қоры сәйкесінше 160, 140, 170 бірлік. Әр мекемеге шикізат ресурстары әрбір тасымалдаушыдан жеткізілуі мүмкін. Жүк тасымалдау құны белгілі және келесі матрицамен анықталады.

Жүк тасымалдаудың құны минималды болатындай, жүк тасымалдау жоспарын анықтау.

Шешімі:

i-ші тасымалдаушыдан  j-ші тұтынушыға (мекемеге) жеткізілетін шикізат ресурстарын x_ij деп белгілейік. Онда келесі шарттар орындалуы тиіс:

(1)

Осы жоспар бойынша  жүк тасымалдау құны келесі

(2)

Сонымен, берілген жүк тасымалдау есебінің математикалық қойылымы келесіде: (2) мақсатты функция минималды мәніне жететін (1) теңдеулер жүйесінің теріс емес шешімін табу.  

Бастапқы есептің берілгендерін 5.1. кесте түрінде жазамыз. 1-ге тең минималды элемент, х₁₃ айнымалының торында орналасқан. Х₁₃=160 қа теңестіріп 5.1. кестесінің сәйкес торына жазып, А₁ жолын уақытша қарастырмайық. В₃ қабылдаушы пункттін қажеттіліктерін 30 бірлікке теңестіреміз.

Кестенің қалған A₂ мен A₃  жолдары мен В₁, В₂, В₃және В₄ төрт бағанында тарифінің ең аз с_ij торы А жолы мен В бағанының қиылысында с₃₂=2 орналасқан. Х₃₂=50 деп 5.1 кестесінің сәйкес торына жазамыз. 

В₂ бағананы уақытша қарастырмай А₃ пуктінің қоры 120 бірлік беп санайық. Бұдан кейін А₂, А₃ қалған екі жолынмен В₁, В₂, В₃ бағаналарын қарастырамыз. Мұндағы минималды тариф с_ij А₃ пен В₃-тің қиылысқан жерінде орналасқан және 3-ке тең. А₂ жолы мен В₁ бағанасының қиылысуында, А₃ пен В₄ қиылысуында орналасқан, торды жоғарда айтылып кеткендей толтырып, қалған торларды сол сияқты толтырамыз. Осылайша тірек жоспарын аламыз.

Берілген жоспарында  Жүк тасымалдың жалпы бағасы мынаны құрайды

S=1*160+4*120+8*20+2*50+3*30+6*90=1530.