3. Решение транспортной задачи методом потенциалов

Алгоритм:

1. Составляется начально допустимый вариант решения (можно любым приближённым методом или любым известным способом, например способ северо-западного угла).

2. Вариант проверяется на не вырожденность. Оптимальный вариант находится среди невырождённых вариантов. Количество базисных клеток должно равняться

.

Для базисного элемента ;

Для свободных и небазисных ;

Если вариант решения вырожденный, то от вырожденности избавляются (например при помощи заведения значащего нуля).

3. Рассчитывается потенциалы по базисным клеткам

;

где - потенциал i-ой строки,

- потенциал j-го столбца.

4. Рассчитываются характеристики для каждой свободной слетки, где Хij=0 по формуле

;

Характеристика означает величину экономии ресурсов на единицу груза, полученную в результате перераспределения ресурсов в данную свободную клетку, поэтому может выступать в качестве дополнительного критерия оптимальности.

5. Вариант решения проверяется на оптимальность. Для оптимального варианта, если для всех i,j; если для всех i,j.

6. Если вариант не является оптимальным находится максимальный элемент не оптимальности плана

7. На основании максимального элемента не оптимальности строится контур перераспределения ресурсов.

Правила построения контура

1. Все углы контура прямые.

2. Одна вершина находится в клетке с максимальным элементом не оптимальности, все другие в базисных клетках

8. Вершины контура последовательно разделяются на загружаемые и разгружаемые. В клетки с максимальным элементом загружаемая вершина.

9. Находится минимальный элемент контура перераспределения ресурсов кА минимум Х_ij в разгружаемых клетках.

10. Строится матрица следующей итерации Х_ij в которой остаются прежними, если не принадлежали контуру перераспределения

;

.

11. Алгоритм повторяется до получения оптимального варианта решения.

12. На каждой итерации вариант решения проверяется на допустимость и рассчитывается значение целевой функции. Для двух соседних итераций разница между целевыми функциями равна максимальному элементу не отрицательности умноженному на минимальный элемент контура перераспределения.

Рассмотрим пример варианта решения которого были получены ранее и в качестве начально допустимого варианта выберем план, полученный методом минимального элемента в матрице, так как при имеет наименьшую целевую функцию.

Рассчитываем потенциалы:

клетка 21:

;

клетка 24:

;

клетка 14:

;

клетка 12:

;

клетка 34:

;

клетка 33:

;

Рассчитаем характеристики для свободных клеток:

-

максимальный элемент неоптимальности плана при

Данный вариант решения не является оптимальным, т.к. присутствует положительная характеристика при .

На основании максимального элемента не оптимальности строим контур перераспределения ресурсов

Рассчитываем потенциалы:

клетка 21:

;

клетка 11:

;

клетка 12:

;

клетка 24:

;

клетка 34:

;

клетка 14:

;

у.е.

Данный вариант решения является оптимальным, так как для всех i и j; F=Fopt

у.е.

Результаты решения транспортной задачи занесём в таблицу