Сотүстік батыс бұрыш әдісі.
Жүк тасымалы туралы есептің тірек жоспарын сотүстік батыс бұрыш әдісімен табу кезінде әрбір қадам сайын қалған жүк қабылдаушы пункт қарастырылады. Есептің шарты жазылған кестені толтыру, оның ең жоғарғы солтүстік жақтағы торынан басталады х11 және белгісіз тормен аяқталады хmn,, яғни диагональ бойынша жүреді.
Ең кіші элемент әдісі.
Солтүстік батыс бұрыш әдісінде әрбір қадам сұранысында қалған жіберуші пункттердің біріншісі, бірінші қалған қабылдаушы пункттерді қанағаттандырады. Қабылдаушы пунктті таңдап алу мен жіберуді және жүк тасымалдау тарифіне сүйене отырып, толығырақ айтсақ ең кіші тарифке жауап беретін әрбір қадамда бір тордан таңдау керек, жіберу пунктті мен қабылдау пунктін таңдап алынған торға сәкес келтірейік. Ең кіші элемент әдісінің мағынасы минималды тарифтен тұратын торды таңдауда. Бұл әдіс жүк тасымал есебінің тиімді әдісін табуға көмектесетінің жүкті тасудың жалпы бағасы оны жоспар бойынша тасыған бағасынан аз, берілген есепті солтүстік батыс бұрыш әдісімен табамыз. Сондықтан жүк тасымадау есебінің тірек жоспрын минималды элементтер әдісімен тапқан дұрыс болады.
Мысал. Жүк тасымалдау есебінің тірек жоспарын минималды элементтер әдісімен тап.
Шешуі. Бастапқы есептің берілгендерін 5.1. кесте түрінде жазамыз. 1-ге тең минималды элемент, х13 айнымалының торында орналасқан. Х13=160 қа теңестіріп 5.1. кестесінің сәйкес торына жазып, А1 жолын уақытша қарастырмайық. В3 қабылдаушы пункттін қажеттіліктерін 30 бірлікке теңестіреміз.
Кестенің қалған A2 мен A3 жолдары мен В1, В2, В3және В4 төрт бағанында тарифінің ең аз сij торы А жолы мен В бағанының қиылысында с32=2 орналасқан. Х32=50 деп 5.1 кестесінің сәйкес торына жазамыз.
В2 бағананы уақытша қарастырмай А3 пуктінің қоры 120 бірлік беп санайық. Бұдан кейін А2, А3 қалған екі жолынмен В1, В2, В3 бағаналарын қарастырамыз. Мұндағы минималды тариф сij А3 пен В3-тің қиылысқан жерінде орналасқан және 3-ке тең. А2 жолы мен В1 бағанасының қиылысуында, А3 пен В4 қиылысуында орналасқан, торды жоғарда айтылып кеткендей толтырып, қалған торларды сол сияқты толтырамыз. Осылайша тірек жоспарын аламыз.
.
Берілген жоспарында Жүк тасымалдың жалпы бағасы мынаны құрайды
S=1*160+4*120+8*20+2*50+3*30+6*90=1530.
Фогельдің аппроксимация әдісі. Жүк тасымалдау жоспарын Фогельдің аппроксимация әдісімен анықтағанда, әрбір инерцияның барлық жол мен барлық бағанында екі жазудың айырмасының арасында минималды тариф орналасады. Бұл айырманы есептің шарты бойынша арнайы бөлінген жол мен бағанада жазылады. Көрсетілген айырмалардан минималдысын таңдап алады. Жолда немесе бағанада берілген айырманы минималды тарифпен анықтайды. Оның жазылған торын, берілген инерциямен толтырады.
Егер минималды тариф жолдағы (бағанадағы) бірнеше торларға бірдей болса, онда толтыру үшің екі минималды тарифтың арасындағы айырмасы ең аз бағананы (жолды) таңдаймыз.
Кесте 5.1
Жіберу пунктілері
|
Бағыттау пунктілері
|
Қор
|
В1
|
В1
|
В1
|
В1
|
А1
|
7
|
8
|
1
160
|
2
|
160
|
А2
|
4
120
|
5
|
9
|
8
20
|
140
|
А3
|
9
|
2
50
|
3
30
|
6
90
|
170
|
Қажеттіліктер
|
120
|
50
|
190
|
110
|
470
|
Жүк тасымалдау есебінің тиімді әдісін анықтау
Жүк тасымалдау туралы есепті анықтау үшін бірнеше әдіс шығарылған. Бірақ потенцалдар әдісі мен дифференциалдық рент әдісін көбірек қолданамыз.
Потенцалдар әдісі. Жүк тасымалы туралы есептің ең тиімді жоспарын табудың жалпы принципі сызықтық программалау есебінің симплекс әдісімен шешудің принципімен ұқсас. Дәлірек айтқанда, әуелі есептің тиімді жоспарын табамыз да, оны ең тиімді жоспар табылғанға дейін жақсарта береді.
Жүк тасымалдау туралы есептің тиімді жоспарын табу үшін адыңғы графада қарастырылған әдісті қолданамыз. Бұл әдіс бастапқы жоспардағы m+n-1 торларын анықтауға кепілдеме береді. Кейбіреуінде ноль тұруы мүмкін
Теорема. Егер жүк тасымалдау туралы есептің қандайда бір тірек жоспары Х*=(х*ij), i=, j= сандары табылып мына шарттар орындалса
Достарыңызбен бөлісу: |