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

Осуществляем сдвиг по циклу на величину θ=100. Получаем второе опорное решение X2 (табл. 6.16).

Таблица 6.16

В данном случае минимум перевозок в клетках, отмеченных знаком “-” достигался сразу в трех клетках, поэтому для того, чтобы число занятых клеток опорного решения было по-прежнему равно m+n-1=7, в клетки с номерами (1,1) и (2,3) поставлены нулевые базисные перевозки. Следует освобождать клетку с большей стоимостью перевозки, т.е. клетку (3.4).

Вычисляем значение целевой функции на втором опорном решении

Z(X2)=0·1+100·1+100·2+100·3+0·4+300·7+200·0=2700.

. Проверяем второе опорное решение X2 на оптимальность. Находим потенциалы и оценки. Они приведены в табл. 6.16. Решение не является оптимальным, так как имеются положительные оценки ∆31=2, ∆32=2, ∆42=1 и ∆43=2. Наибольшая из них равняется 2 одновременно для трех клеток (3,1), (3,2), (4,3). В одну из них, пусть в клетку (3,2), ставим знак “+”. Для этой клетки строим цикл (табл. 6.16), и находим величину груза для перераспределения по циклу:

Осуществляем сдвиг по циклу на величину θ=100. Получаем третье опорное решение X3 (табл. 6.17).

Таблица 6.17