Решение задачи методом потенциалов

Задача. Найти оптимальное решение транспортной задачи с матрицей стоимостей перевозок

,

запасами в пунктах отправления a₁=100, a₂=150, a₃=50 и заказами в пунктах назначения b₁=75, b₂=80, b₃=60, b₄=85.

Решение.

Задать нумерацию элементов массивов с единицы:

Задать матрицу стоимостей перевозок:

0 итерация. Составить опорный план:

Вычислить значение целевой функции:

Задать начальные нулевые значения элементов массива платежей:

I итерация. Рассчитать значения платежей из условия равенства стоимостей и псевдостоимостей в базисных ячейках таблицы, для чего записать уравнения:

Используя функцию Find, найти решение системы:

Найденный вектор Y является блочным: первым блоком является вектор a, вторым – вектор b. Чтобы получить их значения, необходимо выполнить присваивание:

Рассчитать значения псевдостоимостей во всех ячейках таблицы (матрица S) и разности между стоимостями и псевдостоимостями (матрица D):

Анализ элементов матрицы D позволяет заключить, что из двух ячеек с отрицательной разностью стоимости и псевдостоимости более перспективна ячейка (3, 2).

I I итерация. Организовать цикл по переброске 5 единиц груза:

Полученная матрица перевозок будет иметь вид:

,

значение целевой функции .

Рассчитать новые значений платежей:

Рассчитать новые значения псевдостоимостей и элементов матрицы D.

Поскольку полученная матрица D не содержит отрицательных элементов, найденное решение X1 является оптимальным.

Случай вырожденного опорного плана

Пусть при нахождении опорного плана методом северо-западного угла он получился следующим:

.

Здесь число базисных ячеек равно четырем, в то время как в невырожденном плане их должно быть n+m-1=5. Запишем в ячейку (1,2) некую малую величину e (например, e=0,1) и для сведения баланса отнимем ее от содержимого ячейки (2,2):

.

В ходе дальнейшего решения задачи методом потенциалов оказывается выгодным перебросить 20 единиц из ячейки (1,2) в ячейку (2,2), а затем – в ячейку (3,2). Соответствующие преобразования выглядят следующим образом:

.

После получения оптимального решения величину e нужно округлить до нуля.