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

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

Z(X3)=0·1+100·1+100·2+100·4+100·4+200·7+200·0=2500.

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

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

Таблица 6.18

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

Z(X4)=0·1+100·1+200·4+100·3+100·4+100·7+200·0=2300.

. Проверяем решение X4 на оптимальность. Находим потенциалы и оценки. Они приведены в табл. 6.18. Положительными являются оценки ∆13=2, ∆42=1 и ∆43=4. Для клетки (4,3), которой соответствует наибольшая оценка, строим цикл (табл. 6.18) и находим величину груза для перераспределения по циклу

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

Таблица 6.19