Метод потенциалов

Наиболее распространенным методом решения задач ЛП транспортного типа является метод потенциалов, состоящий из следующих этапов:

1) проверка сбалансированности запасов и потребностей;

2) разработка исходного опорного плана;

3) проверка вырожденности опорного плана;

4) расчет потенциалов;

5) проверка плана на оптимальность;

6) поиск «вершины максимальной неоптимальности» (ВМН);

7) построение контура перераспределения поставок;

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

9) получение нового опорного плана.

Этапы 3-9 повторяются, пока не будет найдено оптимальное решение.

Рассмотрим перечисленные этапы.