Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Распределительный метод
Алгоритм решения транспортной задачи распределительным методом состоит в следующем: 1. Находится начальный план (любым методом). 2. Для каждой свободной клетки () находится оценка . 3. Если все , то это распределение перевозок является оптимальным, т.е. дает минимальную стоимость перевозок. Если среди есть хотя бы одна отрицательная оценка, то переходим к новому распределению перевозок. Для этого выбирается наибольшая по модулю отрицательная оценка свободной клетки . Среди перевозок, стоящих в отрицательных клетках цикла для , выбираем наименьшую перевозку. Пусть это будет . Производим сдвиг по циклу на . При этом клетка выходит из базиса (становится свободной). После получения нового базиса переходим к выполнению п.2 и так до тех пор, пока не получим оптимальное распределение перевозок. Замечание. Если в нескольких клетках, то выбираем клетку с наибольшей по модулю отрицательной оценкой. Пример 2. Найти оптимальное распределение перевозок распределительным методом. Таблица 1.7.1
Найдем начальный план методом северо-западного угла (табл. 1.7.2) Таблица 1.7.2
Стоимость перевозок по найденному плану будет ед. Найдем оценки свободных клеток. Для этого составим для каждой свободной клетки цикл, содержащий ее и базисные клетки. Причем свободной клетке припишем знак “+”.
Наибольшая по модулю отрицательная оценка . Сдвиг по циклу производим на (см. определение 5).
Полученное распределение перевозок записываем в (табл. 1.7.3)
Таблица 1.7.3
Стоимость перевозок по найденному плану ед., и, как видно, она уменьшается. Проверим оптимальность плана, вычислив оценки свободных клеток. Самостоятельно укажите циклы, с помощью которых найдены оценки свободных клеток во всех остальных матрицах перевозок. Эти оценки приводятся ниже. , , , , . План не оптимальный, так как имеются отрицательные оценки. Наибольшая по модулю отрицательная оценка . Сдвиг по циклу производим на . Полученное распределение перевозок записываем (табл. 1.7.4). Таблица 1.7.4
Стоимость перевозок по плану стала равной ед. Находя далее оценки свободных клеток, получим, что наибольшая по модулю отрицательная оценка . Произведем сдвиг по циклу, содержащему клетку (4, 2), на 90. Из базиса выведем клетку (4, 4), в то время, как клетка (3, 2) останется базисной клеткой с перевозкой, равной 0. Полученное распределение перевозок запишем (табл. 1.7.5). Таблица 1.7.5
Величина стоимости перевозок стала равной ед. На четвертом шаге имеем: . Сдвиг по циклу на 50ед. Полученное распределение запишем (табл. 1.7.5). Таблица 1.7.6
Стоимость перевозок на четвертом шаге равна ед. На пятом шаге: , , , , , , , , , Таким образом, полученный план является оптимальным, так как все оценки стали положительными. Минимальная стоимость перевозок равна ед. Оптимальный план перевозок представлен в табл.10. Замечание. При решении транспортной задачи распределительным методом наибольшие трудности вызывает построение цикла. Метод потенциалов позволяет свести построение циклов к минимуму.
|