Курсовой проект По дисциплине: «Логистика на транспорте» Студент 5 курса
жүктеу/скачать 0,68 Mb.
|
Логистика ПЗ
- Бұл бет үшін навигация:
- 2.3 Метод северно-западного угла
| 2.2 Определение опорного плана.
Опорный план транспортной задачи находим следующим образом. На каждом шаге в таблице условий задачи заполняем одну клетку, которая называется занятой. Обозначим через Kij клетку, где i -номер пункта отправления (строка), j-номер пункта назначения (столбец). Клетку Kij заполняем так, чтобы удовлетворялись полностью потребности пункта назначения j, либо обеспечивался полный вывоз груза из пункта отправления i. В первом случае временно исключаем из рассмотрения столбец j и изменяем запас груза пункта отправления i. Во втором случае временно исключаем из рассмотрения строку i и изменяем потребность груза пункта назначения j. Далее повторяем процедуру с таблицей условий с исключенной строкой или столбцом. В m+n−1-ом шаге получаем задачу с одним пунктом отправления и одним пунктом назначения. Остается свободной одна клетка. Запасы оставшегося пункта отправления будут равны потребностям пункта назначения. Заполнив эту клетку заканчиваем m+n−1-ый шаг и получаем опорный план. Если на некотором шаге (но не на последнем) потребности очередного пункта назначения равны запасам пункта отправления, то временно исключаем из рассмотрения либо столбец, либо строку (только одно из двух). Тогда либо запасы данного пункта отправления, либо потребности данного пункта назначения считаем равным нулю. Этот нуль при очередном шаге записываем в очередную заполняемую клетку. Данный подход обеспечивает ровно m+n−1 занятых клеток, что обеспечивает возможность проверки полученного опорного плана на оптимальность и нахождение оптимального плана. 2.3 Метод северно-западного угла При нахождении опорного плана транспортной задачи методом северно-западного угла, заполнение клеток таблицы условий начинают с верхней левой клетки K11 поэтому метод и называется "метод северно западного угла"). Рассмотрим метод на конкретном примере. Пример 1. На три базы A1, A2, A3 поступил очередной груз в количествах равных 140, 160, 120 ед. Этот груз требуется перевезти в четыре пунктов назначения B1, B2, B3, B4 в количествах 150, 90, 100, 80. Тарифы перевозок представлена матрицей
Найти план перевозок данной транспортной задачи методом северно-западного угла. Решение. Запишем все данные в таблицу условий:
Число пунктов отправления m=3, а число пунктов назначения n=4. Следовательно опорный план задачи определяется числами, стоящими в m+n−1=3+4−1=6 заполненных клетках таблицы. Наличие груза у поставщиков равно: ∑Ai=140+160+120=420. Общая потребность в грузе в пунктах назначения равна: ∑Bj=150+90+100+80=420. ∑Ai=∑Bj. Модель транспортной задачи является закрытой. Следовательно она разрешима. Найдем опорный план задачи методом северно-западного угла. A1≤B1. Следовательно в клетку (A1, B1 ) помещаем число min(A1, B1)=140. Запасы пункта A1 полностью исчерпаны. Поэтому исключаем из рассмотрения строку A1 и будем считать потребности пункта B1 равными 150−140=10.
A2>B1. Следовательно в клетку (A2, B1) помещаем число min(A2, B1)=10. Потребности пункта B1 полностью удовлетворены. Поэтому исключаем из рассмотрения столбец B1 и будем считать запасы пункта A2 равными 160−10=150.
Таким образом, продолжая процедуру в m+n−1-ом шаге получим:
Запишем полученный опорный план:
При этом плане стоимость перевозок вычисляется так: F=2·140+8·10+4·90+ 1·60+3·40+6·80=1380. жүктеу/скачать 0,68 Mb. Достарыңызбен бөлісу:
|