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

1. Построение опорного плана.

Опорный план – решение задачи, построенное по какому- либо принципу и, как правило, далекое от оптимального.

Рассмотрим два метода построения опорного плана:

-метод северо-западного угла;

-метод двойного предпочтения.

Опишите методы самостоятельно.

11

2.Расчет потенциалов.

Впроцессе решения всегда должно выполняться следующее условие: число «занятых» клеток должно быть равно , где m – число поставщиков; n – число потребителей.

Если условие не выполняется, а именно, число «занятых» клеток меньше, чем , то план называется вырожденным, и в

этом случае в любые свободные клетки необходимо поставить перевозки объема «0» (нуль) в количестве, необходимом для того, чтобы план перестал быть вырожденным. При этом следует помнить, что в плане не должно получиться т.н. прямоугольной фигуры, т.е. такой фигуры, у которой все вершины - клетки «занятые».

После построения плана и проверки его на вырожденность переходим к определению потенциалов.

12

Пусть – потенциал i–ой строки,

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

Для занятых клеток должно выполняться условие оптимальности:

(*) ()

Это условие представляет собой систему уравнений с неизвестными. Поэтому для нахождения неизвестных (они же потенциалы) одно из них – потенциал строки, содержащей наибольшее число занятых клеток, – зафиксируем, т.е. присвоим ему значение «0».

Далее находим все остальные потенциалы.

13

3. Проверка плана на оптимальность.

Если план оптимален, то должно выполняться

условие оптимальности для пустых клеток:

(**)

()

Если проверка условия (**) показывает, что оно не нарушается, – план оптимален.

Если условие (**) нарушается, то необходима дальнейшая оптимизация плана.

Для этого переходим к следующему шагу.

14

4. Поиск клетки с максимальным нарушением условия оптимальности

Во всех клетках, в которых условие (**) нарушилось, следует вписать величину нарушения: [.

Клетку с наибольшей величиной отметить знаком «+» (плюс). Это будет клетка, в которую необходимо перераспределить груз.

5. Определение контура перераспределения

Найдем контур. Это – прямоугольная фигура, все вершины которой – «занятые» клетки, за исключением клетки, помеченной знаком «+».

!!! Число вершин контура – четное. В строке или столбце может находиться только 2 вершины контура.

15

6. Перераспределение ресурсов

Помечаем вершины контура знаками «–», «+», «–», «+», …, начиная от помеченной знаком «+» .

Среди клеток со знаком «–» находим клетку с минимальным объемом перевозки. Это и будет объем перераспределяемого груза.

На эту величину увеличится загрузка в клетках, помеченных знаком «+», и уменьшится в клетках, помеченных знаком «–».

Таким образом получен новый план перевозок, который требует дальнейшей проверки на оптимальность по уже известной схеме.

Процесс улучшения плана продолжается до тех пор, пока план не станет оптимальным.

16