Итерационный алгоритм решения транспортной задачи

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

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

Шаг 2. С помощью симплексного условия допустимости определяется исключаемая из базиса переменная. Происходит изменение базиса и возврат к первому шагу.

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

Решим транспортную задачу из примера, используя начальное решение (рис.2.9), полученное методом северо-западного угла.

Рисунок 2.9 – Начальное базисное решение методом
северо-западного угла

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

В методе потенциалов каждой строке i и каждому столбцу j транспортной таблицы ставятся в соответствие числа (потенциалы) и_i и v_j. Для каждой базисной переменной x_ij потенциалы и_i и v_j удовлетворяют уравнению

Таблица 2.2 – Определение значений потенциалов

Базисные переменные	Уравнения относительно потенциалов	Решение
x11
x12
x22
x23
x24
x34

В рассматриваемой задаче имеем 7 неизвестных переменных (потенциалов) и 6 уравнений, соответствующих шести базисным переменным. Чтобы найти значения потенциалов из этой системы уравнений, нужно присвоить одному из них произвольное значение (обычно полагают ) затем последовательно вычислять значения остальных потенциалов (табл. 2.2).

Итак, имеем

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

Результаты вычисления этих величин приведены в следующей таблице 2.3.

Таблица 2.3 – Значения потенциалов для небазисных переменных

Небазисные переменные	Значения
x13
x14
x21
x31
x32
x33

Вычисленные значения совместно с нулевыми значениями для базисных переменных (поскольку = 0 для любой базисной переменной x_ij) фактически являются коэффициентами z - строки симплекс-таблицы.

Поскольку в транспортной задаче ведется поиск минимума стоимости перевозок, вводимой в базис будет переменная, имеющая наибольший положительный коэффициент в z - строке. В данном случае вводимой переменной будете x₃₁.

Описанные вычисления обычно выполняются непосредственно в транспортной таблице, как показано на рис.2.10. В этом случае нет необходимости в явном виде выписывать уравнения для потенциалов. Вычисления в транспортной таблице начинаются с присвоения потенциалу , нулевого значения: . Затем вычисляются v -потенциалы для всех столбцов, имеющих базисные переменные в первой строке. Далее на основании уравнения для потенциалов, соответствующего переменной х₂₂, вычисляется величина потенциала и₂. Зная значение потенциала и₂, вычисляем потенциалы v ₃ и v₄, что позволяет найти потенциал и₃. Поскольку все потенциалы определены, далее вычисляются величины для каждой небазисной переменной x_ij. Эти величины показаны на рис. 2.10 в правом нижнем углу ячеек транспортной таблицы.

Рисунок 2.10 – Метод потенциалов представленный
в транспортной таблице

Определив вводимую в базис переменную x₃₁, далее следует определить исключаемую из базиса переменную. Напомним, если какая-либо переменная вводится в базис, одна из текущих базисных переменных должна стать небазисной (и равной нулю), чтобы количество базисных переменных оставалось постоянным (в данном примере количество базисных переменных равняется 3+4–1=6).

Исключаемая из базиса переменная определяется следующим образом. Выбрав в качестве вводимой переменную x₃₁, мы хотим, чтобы перевозки по маршруту, соответствующему этой переменной, уменьшили общую стоимость перевозок. Какой объем груза можно перевести по этому маршруту? Обозначим через m количество груза, перевозимого по маршруту (3:1) (т.е. x₃₁ = m). Максимально возможное значение m определяем из следующих условий.

1. Должны выполняться ограничения на спрос и предложение.

2. Ни по какому маршруту не должны выполняться перевозки с отрицательным объемом грузов.

Эти условия позволяют найти значение m и определить исключаемую переменную. Сначала построим замкнутый цикл, который начинается и заканчивается в ячейке, соответствующей вводимой переменной (в данном примере – это ячейка (3:1). Цикл состоит из последовательности горизонтальных и вертикальных отрезков (но не диагональных), соединяющих ячейки, соответствующие текущим базисным переменным, и ячейку, соответствующую вводимой переменной. На рис. 2.11 показан цикл для вводимой переменной x₃₁. Для любой вводимой переменной можно построить только один замкнутый цикл.

Теперь найдем значение m. Для того чтобы удовлетворить ограничениям по спросу и предложению, надо поочередно отнимать и прибавлять m к значениям базисных переменных, расположенных в угловых ячейках цикла, как показано на рис. 2.11 (не имеет значения направление обхода цикла: по часовой стрелке или против). Новые значения базисных переменных останутся неотрицательными, если будут выполняться следующие неравенства:

Рисунок 2.11 – Цикл для вводимой переменной

Отсюда следует, что наибольшее значение, которое может принять m, равно 5, при этом переменные x₁₁ и x₂₂ обращаются в нуль. Поскольку только одна переменная исключается из базиса, в качестве исключаемой можно выбрать как x₁₁, так их x₂₂. Остановим свой выбор на x₁₁.

Определив значение для вводимой переменной (x₃₁ = 5) и выбрав исключаемую переменную, далее следует откорректировать значения базисных переменных, соответствующих угловым ячейкам замкнутого цикла, как показано на рис. 2.10. Поскольку перевозка единицы груза по маршруту (3:1) уменьшает общую стоимость перевозок на 9 грн (), суммарная стоимость перевозок будет на 9×5 = 45грн меньше, чем в предыдущем решении. Таким образом, новая суммарная стоимость перевозок будет равна 520 – 45 = 475грн.

Имея новое базисное решение, следует повторить вычисления потенциалов, как показано на рис. 2.12.

Новой вводимой в базис переменной будет x₁₄. Замкнутый цикл, соответствующий этой переменной, позволяет найти ее значение (x₁₄ = 10) и исключаемую переменную х₂₄.

Рисунок 2.12 – Новое базисное решение и вычисление потенциалов

Новое решение (рис. 2.13) на 4 х 10 = 40 грн уменьшает значение целевой функции.

Рисунок 2.13 – Оптимальное решение транспортной задачи

Таким образом, новая суммарная стоимость перевозок составляет 475 – 40 = 435грн. Теперь новые значения величин для всех небазисных переменных x_ij отрицательные. Поэтому решение, представленное на рис. 2.13, оптимально.

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

Таблица 2.4 – Результаты решения транспортной задачи

От склада	До завода	Количество тонн

Минимальная стоимость всех перевозок равна 435грн.