Получение оптимального плана транспортной задачи с помощью метода потенциалов.

Шаг 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, происходит следующим образом. Строят цикл, начинающийся и заканчивающийся в выбранной свободной клетке.

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

1) все её вершины, кроме начальной, расположены в занятых клетках;

2) звенья (стороны) цикла расположены в строках и столбцах таблицы;

3) в каждой вершине звенья соединяются под прямым углом;

4) на звеньях цикла могут быть занятые клетки, но они не являются вершинами цикла;

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

В свободной клетке условно ставят знак «+», а в остальных вершинах цикла чередуя ставят «-» и «+». Затем происходит перераспределение продукции по циклу. Для этого выбирают клетку со знаком «-», которой соответствует наименьшее число единиц продукции. Это значение прибавляют к значениям, стоящим в клетках со знаком «+», и отнимают от значений, стоящих в клетках со знаком «-». При таком перераспределении общий баланс не изменяется. Свободная клетка заполняется, а клетка со знаком «-», которой соответствует наименьшее количество продукции, становится свободной; соответствующую ей переменную исключают из списка базисных.

Для нового плана повторяют все действия, т.е. переходят к шагу 2.

Дата добавления: 2014-01-07