Вторая транспортная теорема

Х – невырожденный опорный план, который не является оптимальным, т.е. среди свободных клеток есть положительные. Тогда:

1) среди положительных оценок свободных клеток выбираем наибольшее, и для этой клетки строим цикл, в котором выставляем чередующие знаки – и +, начиная со свободной клетки.

2) среди всех поставок положительных клеток цикла выбирается наименьшая, которая затем прибавляется к поставкам в отрицательных клетках цикла и вычитается из поставок положительных клеток цикла. В результате такого преобразования получаем новый опорный план, который может быть вырожденным (это возможно если наименьшая «положительная» поставка находится в двух или более клетках цикла). И тогда прежде чем проверять полученный план на оптимальность, его следует сделать не вырожденным.

Замечание: если клеток с наибольшей положительной оценкой несколько, то для каждой из них следует построить цикл, расставить знаки и определить величину минимальной положительной поставки. Выбираем клетку для перераспределения, для которой найденная положительная поставка цикла будет наибольшей, и именно по данному циклу осуществляем переход к новому опорному плану.

Метод потенциалов (Канторович)

Идея: Метод основан на вычислении специальных показателей (для баз и магазинов), названных Канторовичем потенциалами, удовлетворяющих следующему определению:

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

1. для всех занятых клеток разность потенциалов равна тарифу:

(*) (i;j) (x_ij>0),

2. для свободных клеток разность потенциалов не должна превышать тарифов:

(**) (x_ij=0)

В случае если х= х_ij оптимальный план, через _ij = v_j - u_i - c_ij (для оптимального плана должна быть не положительна).

Алгоритм решения

Определим исходное базисное решение:

Из условия (*) вычисляем потенциалы всех баз и магазинов. При этом число уравнений, получаемых в системе, для занятых клеток будет m+n-1, а число переменных m+n. Следовательно, система является не определенной (т.к. число неизвестных больше числа переменных) и имеет бесконечное множество решений. В этой связи обычно полагают u₁=0 и последовательно вычисляют все оставшиеся потенциалы.

После вычисления потенциалов проверяют условие (**) для свободных клеток. Если оно выполняется для всех свободных клеток, то план оптимальный. В противном случае для клеток, в которых условие нарушается, вычисляют оценки _ij, и среди них выбирают наибольшую, и для данной клетки строят цикл и осуществляют перераспределение поставок согласно второй транспортной теореме.

Задача о назначениях. Венгерский алгоритм.

Требуется распределить m работ (или исполнителей) по n станкам (рабочим местам). i-я работа, выполняемая на j-м станке, связана с затратами c_ij. Задача состоит в таком распределении работ по станкам (одна работа на один станок), которое соответствует минимуму суммарных затрат.

Это частный случай транспортной задачи. Работы - пункты отправления, станки - пункты назначения. Предложение в каждом пункте отправления равно 1, спрос в каждом пункте назначения равен 1. Стоимость «перевозки» (прикрепления) i работы к j станку - c_ij. Если некоторую работу нельзя выполнить на некотором станке, то соответствующая стоимость полагается равной бесконечности (c_{ij =} ).

Прежде, чем решать задачу в рамках транспортной модели, необходимо устранить дисбаланс, добавив фиктивные работы или фиктивные станки в зависимости от начальных условий; поэтому, не ограничивая общности в дальнейшем, полагаем n = m.

Математическая модель:

Пусть -Булева переменная.

0, если i-я работа не выполняется на j-м станке и 1 в противном случае.

Тогда

при ограничениях

(кто-то должен выполнять работу)

(работа должна быть выполнена)

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

Теорема 1. Оптимальное решение не изменится, если ко всем элементам любой строки (столбца) матрицы стоимости прибавить или вычесть постоянную величину (возможно различную для каждой строки (столбца)).

На основании этой теоремы можно построить новую матрицу с нулевыми элементами, и если это множество нулевых элементов (или их подмножества) будут соответствовать допустимому решению, то такое решение будет оптимальным, так как стоимость не может быть отрицательной.