II. Решить транспортную задачу

Транспортная задача (ТЗ) формулируется следующим образом. В m пунктах отправления А ₁... A _m сосредоточен однородный груз в количествах соответственно а ₁... а _m единиц. Имеющийся груз необходимо доставить потребителям В ₁... В _n, спрос которых выражается величинами b ₁... b _п единиц. Известна стоимость с _ij перевозки единицы груза из i -го пункта отправления в j -й пункт назначения. Требуется составить план перевозок, который полностью удовлетворяет спрос потребителей в грузе, и при этом суммарные транспортные издержки минимизируются.

Для наглядности условия ТЗ можно представить таблицей (табл. 1.), которую будем называть распределительной. Распределительную таблицу называют иногда табличной или матричной моделью ТЗ.

Цель ТЗ — минимизировать общие затраты на реализацию плана перевозок.

Итерационный процесс по отысканию оптимального плана транспортной задачи начинают с опорного плана, который находят методом северо-западного угла.

Решение задачи осуществить методом потенциалов с помощью программы Optimal.

Представление транспортной задачи в матричной форме

Исходная таблица:

Транспортная задача имеет закрытый тип, так как суммарный запас груза равен суммарным потребностям.
Находим опорный план по правилу северо-западного угла:
Введем некоторые обозначения:
A_i^* - излишек нераспределенного груза от поставщика A_i
B_j^* - недостача в поставке груза потребителю B_j

Помещаем в клетку (1, 1) меньшее из чисел A₁^*=40 и B₁^*=30
Так как спрос потребителя B₁ удовлетворен, то столбец 1 в дальнейшем в расчет не принимается
Помещаем в клетку (1, 2) меньшее из чисел A₁^*=10 и B₂^*=25
Так как запасы поставщика A₁ исчерпаны, то строка 1 в дальнейшем в расчет не принимается
Помещаем в клетку (2, 2) меньшее из чисел A₂^*=30 и B₂^*=15
Так как спрос потребителя B₂ удовлетворен, то столбец 2 в дальнейшем в расчет не принимается
Помещаем в клетку (2, 3) меньшее из чисел A₂^*=15 и B₃^*=15
Так как запасы поставщика A₂ исчерпаны, то строка 2 в дальнейшем в расчет не принимается
Так как спрос потребителя B₃ удовлетворен, то столбец 3 в дальнейшем в расчет не принимается
Помещаем в клетку (3, 4) меньшее из чисел A₃^*=20 и B₄^*=20

Целевая функция F=130

Решаем задачу методом потенциалов:
Примем некоторые обозначения:
i - индекс строки;
j - индекс столбца;
m - количество поставщиков;
n - количество потребителей.

Этап 1

Опорный план является вырожденным, так как число занятых клеток меньше, чем m+n-1=7.

Сделаем его невырожденным, поместив базисные нули в клетки с координатами (i, j): (2, 4)

Полагая потенциал U₁=0, определяем остальные потенциалы из соотношения U_i+V_j=C_{i, j}(i=1..m, j=1..n), просматривая все занятые клетки.
Потенциалы U_i:
U₁=0
V₁=C_{1, 1}-U₁= 1
V₂=C_{1, 2}-U₁= 2
U₂=C_{2, 2}-V₂= -1
V₃=C_{2, 3}-U₂= 4
V₄=C_{2, 4}-U₂= 3
U₃=C_{3, 4}-V₄= -2

Определяем значения оценок S_{i, j}=C_{i, j}-(U_i+V_j) для всех свободных клеток:
S_{1, 3} = c_{1, 3} - (u₁ + v₃) = 0.
S_{1, 4} = c_{1, 4} - (u₁ + v₄) = 3.
S_{2, 1} = c_{2, 1} - (u₂ + v₁) = 3.
S_{3, 1} = c_{3, 1} - (u₃ + v₁) = 6.
S_{3, 2} = c_{3, 2} - (u₃ + v₂) = 7.
S_{3, 3} = c_{3, 3} - (u₃ + v₃) = 3.

Так как все оценки S_{i, j} > =0, то полученный план является оптимальным.
Транспортная задача решена.

Целевая функция F= 130