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