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

Шаг1. Получение начального плана перевозок по методу "северо-западного" угла, минимального элемента, Фогеля или любым другим методом.

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

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

Шаг 3.1. Определение потенциалов производителей и потребителей. Составляют систему уравнений для заполненных клеток транспортной таблицы: , где – номера строк и столбцов на пересечении которых стоят заполненные клетки, –. потенциал -го поставщика, – потенциал -го потребителя, – тариф на перевозку из пункта в пункт . Число уравнений в системе равно , а число неизвестных и равно . Для решения данной системы одно из неизвестных выбирают произвольно. Обычно полагают =0. Решая систему уравнений, находят значения потенциалов и , .

Шаг 3.2. Определение суммы потенциалов (косвенных тарифов) для свободных клеток: , где и – номера строк и столбцов, на пересечении которых стоит свободная клетка, – потенциал -гo поставщика, – потенциал -го потребителя, – косвенные тарифы.

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

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

Шаг 4. Улучшение плана.

Шаг 4.1. Выбор переменной, вводимой в список базисных переменных.

Выбирают клетку, которой соответствует максимальное положительное значение разности, полученной на шаге 3.3. Если имеется несколько одинаковых значений, то из них выбирают любое.

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

Шаг 4.2. Выбор переменной, выводимой из списка базисных переменных.

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

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

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