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

1. Решение транспортной задачи

Так как транспортная задача является задачей линейного программирования, то основные этапы ее решения будут такими:

Iэтап. Нахождение начального допустимого решения.

IIэтап. Выделение из небазисных переменных вводимой в базис переменной (метод потенциалов). Если все небазисные переменные удовлетворяют условию оптимальности, то следует закончить вычисления; в противном случае — перейти к III этапу.

IIIэтап. Выбор выводимой из базиса переменной (используя условия допустимости) из числа переменных текущего базиса; затем нахождение нового базисного решения и возвращение ко II этапу.

Для лучшего понимания метода потенциалов, рассмотрим подробнее все этапы решения транспортной задачи, учитывая ее специфику.

I этап. Определение начального допустимого решения

Для сбалансированной транспортной задачи существует только m + n - 1 независимых уравнений. Таким образом, начальное базисное допустимое решение должно иметь m+n-1 базисных переменных.

Начальное базисное решение транспортной задачи получают непосредственно из транспортной таблицы. Для этого можно использовать три процедуры.

1. Правило "северо-западного угла"

При нахождении опорного плана транспортной задачи методом "северо-западного угла" на каждом шаге рассматривают первый из оставшихся пунктов отправления и первый из оставшихся пунктов назначения. Заполнение транспортной таблицы начинается с левого верхнего угла (северо-западного), двигаясь далее по строке вправо или по столбцу вниз (увеличение i, увеличение j). Переменной Х11 приписывают максимальное значение, допускаемое ограничениями на спрос и запасы.

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

Исходный опорный план, построенный по правилу "северо-западного угла", обычно оказывается весьма далеким от оптимального, так как при его формировании не учитывается стоимость перевозок (величина сij). Более совершенным правилом является правило "минимального элемента".

2.Правило "минимального элемента"