Пример:

6	10	4	150
12	2	8	90
60	70	110

640	10	4110	150
1220	270	8	90
60	70	110

Этап 2: Проверка полученного распределения ресурсов на оптимальность.

Чтобы осуществить проверку оптимальности, необходимо определить, является ли начальное распределение перевозок базисным, т.е. находится ли полученное решение в крайней точке допустимого множества. Если распределение перевозок является базисным, каждому ограничению должна соответствовать одна базисная переменная. Задача для m поставщиков и n потребителей (включая фиктивных) содержит (m + n - 1) независимых ограничений.

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

В нашем примере случай невырожденный:

(m + n – 1)=2+3-1=4 и 4 заполненных клетки.

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

Теорема: Допустимое базисное решение (опорное) оптимально тогда и только тогда, когда:

для ,

для .

Проверка на оптимальность. Метод потенциалов.

1. Для начала рассмотрим только заполненные клетки.

Для этих клеток каждое значение единичной стоимости разделяется на 2 компоненты – u_i для строк и v_j для столбцов (потенциалы поставщиков и потенциалы потребителей). Например, для клетки (1,1), лежащей на пересечении 1 строки и 1 столбца, . Можно выделить компоненту u₁ и v_1, т. е. .

Итак, на примере нашей задачи построим систему потенциалов для заполоненных клеток:

Какой-либо из компонент присваивается некоторое значение, по которому из соответствующих уравнений рассчитываются значения остальных компонент. Положим .

Тогда

2) Теневые цены для каждой пустой (небазисной) клетки можно найти из соотношения . Эта теневая цена отражает дополнительную стоимость перевозки единицы изделия из пункта i в пункт j.

Приступаем к выбору клетки, в которую нужно послать перевозку (проверка на оптимальность для незаполненных клеток).

По теореме, решение не является оптимальным. Выбираем клетку (2,3) ( <0): в нее необходимо направить груз, построив цикл пересчета

Этап 3: Если полученное распределение ресурсов не является оптимальным, то ресурсы перераспределяются, снижая стоимость транспортировки.

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

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

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

Рис.2

Замечание: При правильном построении опорного плана для любой свободной клетки можно построить лишь один цикл.

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

Это перемещение производят по следующим правилам:

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

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

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

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

Следует отметить, что при сдвиге по циклу пересчета число занятых клеток остается неизменным, а именно остается равным m + n — 1.

min{20,110}=20

Этап 4: Повторная проверка оптимальности полученного распределения ресурсов.

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

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

Положим . Тогда

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

Z=6ּ60+4ּ40+2ּ70+8ּ20=1020 (ден.ед.)