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

Лабораторная работа №4

тема: “Решение транспортной задачи линейного программирования. Составление оптимального плана транспортной задачи”

Цель работы: получение практических навыков решения транспортной задачи линейного программирования с помощью методов составления оптимальных планов.

Теоретические сведения

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

Потенциальным называют такой план перевозок { X _ij}, которому соответствует (m + n) чисел U ₁, U ₂, …, U _m, V ₁, V ₂, …, V _n, которые удовлетворяют условиям:

V _j – U _i ≤ C _ij для незаполненных клеток (X _ij = 0), i = 1, 2… m, j = 1, 2… n (1)

V _j – U _i = C _ij для заполненных клеток (X _ij > 0), i = 1, 2… m, j = 1, 2… n (2)

Алгоритм метода потенциалов:

1) Предварительный шаг:

– составление первоначального плана перевозок;

– вычисление потенциалов;

– проверка первоначального плана на потенциальность.

Первоначальный план составляется любым из известных методов. Вычисление потенциалов производится на основе выражения (1) для заполненных клеток. При этом если план невырожденный (количество заполненных клеток равно m + n – 1), то одной из переменных можно задаться (например, U _i = 0). Если план вырожденный (количество заполненных клеток < m + n – 1), то необходимо проставить в таблице столько значащих нулей, сколько их не хватает до m + n – 1. Эти нули проставляются таким образом, чтобы они не составляли замкнутого цикла с остальными заполненными клетками.

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

2) Повторяющийся шаг:

– исправление первоначального плана;

– исправление потенциалов;

– проверка плана на потенциальность.

Для исправления плана перевозок выбирается клетка с наибольшим невыполнением условия (2), т.е. клетка с наибольшим α _ij = V _j – U _i – C _ij. К этой клетке составляется цикл. В исходной клетке проставляется знак «+», в следующей – знак «–» и т.д. Далее из клеток со знаком «–» выбирается наименьшая поставка P и исправляется план перевозок:

– для клеток со знаком «+» X _ij = X _ij + P;

– для клеток со знаком «–» X _ij = X _ij – P.

После этого выполняется исправление потенциалов. Поскольку исходная клетка стала заполненной, необходимо исправить один из ее потенциалов. Как правило, исправляется тот, который приведет к наименьшему исправлению остальных потенциалов. В общем случае, потенциалы могут быть пересчитаны заново.

Далее выполняется проверка условия потенциальности по выражению (2). Если выражение (2) выполняется для всех незаполненных клеток, то план потенциален, а следовательно, оптимален, и решение найдено, иначе переходим к исправлению плана перевозок.