Получение оптимального плана транспортной задачи с помощью метода потенциалов.
Шаг 1. Получение начального плана перевозок по методу «северо-западного» угла или минимального элемента.
Шаг 2. Проверка плана на невырожденность. Если полученный план вырожденный, формально заполняют нулями некоторые из свободных клеток так, чтобы общее число занятых клеток было равно . Нули надо расставлять так, чтобы не образовался замкнутый цикл из занятых клеток.
Шаг 3. Проверка плана на оптимальность.
3.1.
Определение потенциалов поставщиков
и потребителей. Составляют систему
уравнений для заполненных клеток
транспортной таблицы:
,
где i,
j
– номера строк и столбцов, на пересечении
которых стоят занятые клетки,
- потенциал i–того
поставщика,
- потенциал j–того
потребителя,
- тариф на перевозку из пункта i
в
пункт
j.
Число уравнений в системе равно
,
а число неизвестных
и
равно
.
Для решения данной системы одно из
неизвестных выбирают произвольно.
Обычно полагают
=
0. Решая систему уравнений, находят
значения потенциалов
и
.
3.2.
Определение суммы потенциалов (косвенных
тарифов) для свободных клеток:
+
,
где
q
и
p
– номера строк и столбцов, на пересечении
которых стоит свободная клетка,
- потенциал q
–того
поставщика,
- потенциал p-того
потребителя.
3.3. Проверка на оптимальность. Для каждой свободной клетки транспортной таблицы составляется разность
=
+
-
.
Если все ≤ 0, то полученный план оптимален. Если хотя бы для одной свободной клетки > 0, то план может быть улучшен. Переход к шагу 4.
Шаг 4. Улучшение плана.
4.1. Выбор переменной, вводимой в список базисных переменных. Выбирают клетку, которой соответствует максимальное положительное значение разности = + - . Если имеется несколько одинаковых значений, то из них выбирают любое или клетку с минимальным тарифом. Переменная транспортной задачи, соответствующая этой клетке, вводится в список базисных переменных, т.е. данная клетка транспортной таблицы заполняется.
4.2. Выбор переменной, выводимой из списка базисных переменных. Заполнение клетки, выбранной на шаге 4.1, происходит следующим образом. Строят цикл, начинающийся и заканчивающийся в выбранной свободной клетке (Циклом с начальной вершиной в данной клетке называется замкнутая ломаная, обладающая характерными свойствами)…
Алгоритм улучшения плана транспортной задачи. Понятие цикла, пересчет по циклу. Снятие вырожденности плана.
Циклом с начальной вершиной в данной клетке называется замкнутая ломаная, обладающая следующими свойствами:
все её вершины, кроме начальной, расположены в занятых клетках;
звенья (стороны) цикла расположены в строках и столбцах таблицы;
в каждой вершине звенья соединяются под прямым углом;
на звеньях цикла могут быть занятые клетки, но они не являются вершинами цикла;
два звена могут пересекаться в какой-либо клетке, но эта клетка не должна быть занятой (иначе она является вершиной).
В свободной клетке условно ставят знак «+», а в остальных вершинах цикла чередуя ставят «-» и «+». Затем происходит перераспределение продукции по циклу. Для этого выбирают клетку со знаком «-», которой соответствует наименьшее число единиц продукции. Это значение прибавляют к значениям, стоящим в клетках со знаком «+», и отнимают от значений, стоящих в клетках со знаком «-». При таком перераспределении общий баланс не изменяется. Свободная клетка заполняется, а клетка со знаком «-», которой соответствует наименьшее количество продукции, становится свободной; соответствующую ей переменную исключают из списка базисных.