Задача 3. Решение транспортной задачи
 Скачать 90.93 Kb.
|
1 2 Найдем оптимальный план транспортной задачи методом потенциалов. Опорный план имеет следующий вид:
При этом плане стоимость перевозок вычисляется так:
Проверяем полученный опорный план на оптимальность. Для этого находим потенциалы пунктов отправления и назначения. Для заполненных клеток составляем систему из 5 уравнений с 6 неизвестными:
Полагая α1=0, находим β1=5 β2=1 α2=-1 α3=-3 β3=6 . Для каждой свободной клетки вычисляем число αij=βj−αi−cij: α13=3, α21=2, α23=0, α31=0. Полученные числа заключаем в рамки и записываем их в соотвестствующие клетки таблицы: .
Среди чисел αij есть положительные. Следовательно данный опорный план не является оптимальным. Наибольшее положительное число 3 находится в пересечении строки A1 и столбца B3. Для данной свободной клетки строим цикл пересчета. Для этого вставим в эту клетку знак "+" а остальные клетки цикла поочередно знаки "−" и "+".
Наименьшее из чисел в минусовых клетках равно 5. Клетка, в которой находится это число становится свободной. В новой таблице другие числа получаются так. Числам, находящимся в плюсовых клетках добавляется 5, а из чисел, находящихся в минусовых клентках вычитается это число.
Опорный план имеет следующий вид:
При этом плане стоимость перевозок вычисляется так:
Проверяем полученный опорный план на оптимальность. Для этого находим потенциалы пунктов отправления и назначения. Для заполненных клеток составляем систему из 5 уравнений с 6 неизвестными:
Полагая α1=0, находим β1=5 β3=3 α3=-6 β2=-2 α2=-4 . Для каждой свободной клетки вычисляем число αij=βj−αi−cij: α12=-3, α21=5, α23=0, α31=3. Полученные числа заключаем в рамки и записываем их в соотвестствующие клетки таблицы: .
Среди чисел αij есть положительные. Следовательно данный опорный план не является оптимальным. Наибольшее положительное число 5 находится в пересечении строки A2 и столбца B1. Для данной свободной клетки строим цикл пересчета. Для этого вставим в эту клетку знак "+" а остальные клетки цикла поочередно знаки "−" и "+".
Наименьшее из чисел в минусовых клетках равно 20. Клетка, в которой находится это число становится свободной. В новой таблице другие числа получаются так. Числам, находящимся в плюсовых клетках добавляется 20, а из чисел, находящихся в минусовых клентках вычитается это число.
Опорный план имеет следующий вид:
При этом плане стоимость перевозок вычисляется так:
Проверяем полученный опорный план на оптимальность. Для этого находим потенциалы пунктов отправления и назначения. Для заполненных клеток составляем систему из 5 уравнений с 6 неизвестными:
Полагая α1=0, находим β3=3 α3=-6 β2=-2 α2=-4 β1=0 . Для каждой свободной клетки вычисляем число αij=βj−αi−cij: α11=-5, α12=-3, α23=0, α31=-2. Полученные числа заключаем в рамки и записываем их в соотвестствующие клетки таблицы: .
Среди чисел αij нет положительных. Следовательно данный опорный план является оптимальным. Решение: Оптимальный план имеет следующий вид:
При этом плане стоимость перевозок вычисляется так:
1 2 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||