Бұл әдіс үш дәйекті қадамды қамтиды:
Негізгі жоспарды қалыптастыру;
Негізгі жоспардың оңтайлылығын тексеру;
Алдыңғы оңтайлы болмаса, жаңа базалық сызыққа көшу.
1-сурет – Потенциалды әдіс алгоритмінің құрылымдық сұлбасы
II . Негізгі тасымалдау жоспарын қалыптастыру
Солтүстік-батыс (СБ) бұрыш әдісі деп аталатын тасымалдау тапсырмасының бастапқы анықтамалық жоспарын алу әдісін қарастырайық. Әдіс m×n кестесінің ұяшықтарын x ij айнымалысының мәндерімен есептің шарттары орындалатындай етіп толтырудан тұрады. Бұл жағдайда X[m, n] шешу жоспары оңтайлы болмауы мүмкін, бірақ ол рұқсат етілген болуы керек . Бұл әдісте тірек жоспар кесте бойымен қозғалу арқылы қалыптасады: сызықтар бойымен жоғарыдан төменге және сызық бойымен солдан оңға қарай. Олар жоғарғы сол жақ бұрыштан (ұяшық) басталады, мұнда x 11 \u003d min { a 1 , b 1 мәнін енгізеді.}. Бірінші жол мен баған одан әрі қараудан шығарылады.
Содан кейін, егер a 1 > b 1 , онда өнімнің бірінші жөнелту нүктесіндегі қалдығы ( a 1 – b 1 ) анықталады және оның қоры 2-ші пунктте сатылады. 2-ші бағыттың қалған қажеттіліктерін 2-ші шығу қанағаттандырады, қалғаны 3-ші бағытқа жіберіледі және т.б. Әдіс төменде сандық мысалмен суреттелетін болады.
Мысал 1. Солтүстік-батыс бұрыш әдісі арқылы тірек жоспарды құру
Берілген мәндер: m = 3, n = 4; a 1 = 60, a 2 = 80, a 3 = 100, b 1 = 40, b 2 = 60, b 3 = 80, b 4 = 60. Сол жақта кестеде d ij тасымалдау бірлігінің шығындары берілген; оң - In ij шығындарымен бірге ұсыныстар a i және қажеттіліктер b j .
Q есебінің Q ij айнымалылары мен Q мақсаттық функциясының шарттарын қанағаттандыратын Х [m,n] тасымалдау жоспарын табу талап етіледі .
ШЕШІМ Солтүстік-батыс бұрыш әдісін қолдана отырып, бастапқы тірек жоспарын құрастырыңыз. Симплекс кестесін құрастырамыз: Кесте 3. Негізгі тапсырма жоспары
Кестеде солтүстік-батыс бұрыш әдісі арқылы тірек жоспар алынды. Негізгі айнымалылар (олардың саны = 6): x 11 = 40, x 12 = 20, x 22 = 40, x 23 = 40, x 33 = 40, x 34 = 60. Бос айнымалылар: x 13 = x 14 = x 21 \u003d x 24 \u003d x 31 \u003d x 32 \u003d 0 (олардың саны 6 ).
Кестенің негізгі айнымалыларға сәйкес ұяшықтары негізгі деп аталады, қалғандары бос. Әрі қарай алгоритмде симплекс әдісі идеясын ұстанамыз. X [ m,n ] жоспарына сәйкес келетін тасымалдаудың жалпы құны Q , ұсынуды алады.
Достарыңызбен бөлісу: |
