ОПТИМАЛЬНОСТЬ БАЗИСНОГО РЕШЕНИЯ

Рассмотрим нахождение оптимального решения транспортной задачи методом потенциалов на конкретном примере.

На складах А₁, А₂, А₃ имеются запасы продукции в количествах 90, 400, 100 т соответственно. Потребители В₁, В₂, В₃ должны получить эти продукцию в количествах 140, 300, 160 т соответственно. Найти такой вариант прикрепления поставщиков к потребителям, при котором сумма затрат на перевозки была бы минимальной. Расходы по перевозке 1 т продукции заданы матрицей (ден. ед.):

Проверим, является ли данная транспортная задача закрытой.

следовательно, данная транспортная задача закрытая. Найдем исходный опорный план по методу минимального тарифа.

Таблица 3.4

Число занятых клеток в таблице равно 5, m + n – 1 = 3 + 3 – 1 = 5, т.е. условие невырожденности выполнено.

Стоимость перевозки при исходном опорном решении составляет:

Z₁ = 90·2 + 300·1 + 100·5 + 50·3 + 60·8 = 1610 ден. ед.

Найденное исходный опорный план проверяется на оптимальность методом потенциалов по следующему критерию: если опорное решение транспортной задачи является оптимальным, то ему соответствует система m + n действительных чисел α_i и β_j, удовлетворяющих условиям для занятых клеток и для свободных (незанятых) клеток.

Числа α_i и β_j называют потенциалами. В распределительную таблицу добавляют строку β_j и столбец α_i.

Потенциалы α_i и β_j находят из равенства справедливого для занятых клеток. Одному из потенциалов дается произвольное значение, например α₁ = 0, тогда остальные потенциалы определяются однозначно. Так, если известен потенциал α_i, то β_j = c_ij – α_i, если известен потенциал β_j, то α_i = c_ij – β_j.

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

Проверим найденное опорное решение на оптимальность, добавив в распределительную таблицу столбец α_i и строку β_j.

Таблица 3.5

Полагаем α₁= 0, запишем это значение в последнем столбце первой строки таблицы.

Рассмотрим занятую клетку первой строки, которая расположена в первом столбце (А1;В1), для нее выполняется условие α₁ + β₁ = с₁₁ или 0 + β₁ = 2, откуда β₁ = 2. Это значение запишем в последней строке первого столбца таблицы. Далее надо рассматривать ту из занятых клеток таблицы, для которой один из потенциалов известен.

Рассмотрим занятую клетку (А₃; В₁): α₃ + β₁ = 3, где β₁ = 2, откуда α₃ = 1.

Для клетки (3, 3): α₃ + β₃ = 8, α₃ = 1, β₃ = 7.

Для клетки (2, 3): α₂ + β₃ = 5, α₃ = 7, β₂ = – 2.

Для клетки (2, 2): α₂ + β₂ = 1, α₂ = – 2, β₂ = 3.

Найденные значения потенциалов заносим в таблицу.

Вычисляем оценки свободных клеток:

Δ₁₂ = α₁ + β₂ – с₁₂ = 0 + 3 – 5 = – 2 < 0,

Δ₁₃ = α₁ + β₃ – с₁₃ = 0 + 7 – 2 = 5 > 0,

Δ₂₁ = α₂ + β₁ – с₂₁ = – 2 + 2 – 4 = – 4 < 0,

Δ₃₂ = α₃ + β₂ – с₃₂ = 1 + 3 – 6 = – 2 < 0.

Получили одну оценку Δ₁₃ = 5 > 0, следовательно, исходный опорный план не является оптимальным и его можно улучшить.

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

Для свободной клетки с Δ_ij > 0 строится цикл (цепь, многоугольник), все вершины которого кроме одной находятся в занятых клетках; углы прямые, число вершин четное. Около свободной клетки цикла ставится знак (+), затем поочередно проставляют знаки (–) и (+). У вершин со знаком (–) выбирают минимальный груз, его прибавляют к грузам, стоящим у вершин со знаком (+), и отнимают от грузов у вершин со знаком (–). В результате перераспределения груза получим новое опорное решение. Это решение проверяем на оптимальность, и т.д. до тех пор, пока не получим оптимальное решение.

Рассмотрим переход от одного опорного решения к другому на заданном примере.

Строим цикл для клетки (А₁; В₃), имеющий положительную оценку. У вершин цикла ставим знаки (+) и (–) и записываем грузы:

– +

+ –

У вершин со знаком (–) выбираем минимальный груз, он равен 60. Его прибавляем к грузам, стоящим у положительных вершин, и отнимаем от грузов, стоящих у отрицательных вершин. Получаем новый цикл:

30 60

110 0

Новое опорное решение:

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

Таблица 3.6

Имеем

Δ₁₂ = – 7, Δ₂₁ = 1 > 0, Δ₃₂ = – 7, Δ₃₃ = – 5.

Построим цикл для клетки с положительной оценкой Δ₂₁ = 1:

– +

+ –

Произведем перераспределение грузов:

0 90

30 70

Получим новое решение, которое занесем в табл. 3.7. Проверим его на оптимальность.

Таблица 3.7

Получим

Δ₁₁ = – 1, Δ₁₂ = – 1, Δ₃₂ = – 6, Δ₃₃ = – 4.

Все оценки свободных клеток отрицательные, следовательно, найденное решение оптимальное. Итак,

Стоимость транспортных расходов равна

Z_min = 90·2 + 30·4 + 300·1 + 70·5 + 110·3 = 1280 ден. ед.

По сравнению с исходным опорным планом транспортные расходы уменьшились на 1610 – 1280 = 330 ден. ед.

Альтернативный оптимум. Признаком наличия альтернативного оптимума в транспортной задаче является равенство нулю хотя бы одной из оценок свободных переменных в оптимальном решении (Х_опт1). Сделав перераспределение грузов относительно клетки, имеющей Δ_ij = 0, получим новое оптимальное решение (Х_опт2), при этом значение целевой функции (транспортных расходов) не изменится. Если одна оценка свободных переменных равна нулю, то оптимальное решение находится в виде