Критерий оптимальности базисного распределения поставок

Подход к решению вопроса об оптимальности базисного решения был детально разобран в гл. 5, посвященной симплексному методу. Прежде всего, следует выразить линейную функцию задачи через неосновные (свободные) переменные. Транспортная задача — задача на минимум, поэтому оптимум достигнут тогда и только тогда, когда все коэффициенты при неосновных (свободных) переменных в выражении линейной функции неотрицательны. В транспортной задаче произвольная переменная x_ij отождествляется с содержимым соответствующей клетки (i, j) таблицы поставок. Коэффициент при свободной переменной х_ij в выражении линейной функции F через неосновные переменные называется оценкой свободной клетки (i,j). Тогда критерий оптимальности формулируется следующим образом: базисное распределение поставок оптимально тогда и только тогда, когда оценки всех свободных клеток неотрицательны.

Таким образом, на первый план выходит задача о нахождении оценок свободных клеток для фиксированного базисного распределения поставок.

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

(7.12)

где многоточием обозначены слагаемые, отвечающие свободным переменным, отличным от x_ij, F ₀ - суммарные затраты на перевозку данного распределения поставок. Тогда из выражения (7.12) следует, что оценка свободной клетки (i,j) равна приращению F суммарных затрат на перевозку при переводе в клетку (i,j) единичной поставки (увеличении переменной х_ij от 0 до 1). Очевидно, что F > 0, если > 0; F < 0, если < 0. Последнее косвенное определение оценки свободной клетки обычно называют экономическим смыслом оценки свободной клетки.

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

Пример 7.5. Установить, является ли оптимальным базисное распределение поставок, найденное в примере 7.3 (табл. 7.9).

Таблица 7.9

Решение. Найдем, например, оценку свободной клетки (1,3). Для этого дадим в клетку (1,3) единичную поставку. При этом потребуется изменить поставки в заполненных клетках так, чтобы сохранился баланс по строкам и столбцам. Будем полагать, что во всех свободных клетках, отличных от клетки (1,3), поставка останется нулевой. Так, чтобы третий потребитель получил по-прежнему 40 единиц груза, поставку в клетке (3,3) следует уменьшить на 1. Для того, чтобы третий поставщик отправил по-прежнему 100 единиц груза, поставку в клетке (3,2) увеличиваем на 1. Так как второму потребителю нужно только 100 единиц груза, то поставку в клетке (1,2) придется уменьшить на 1. Существенно, что найденный вариант перераспределения поставок, затрагивающий заполненные клетки и увеличивающий на 1 поставку клетки (1,3), — единственный. Полученное распределение поставок изображено в табл. 7.10.

Найдем изменение F суммарных затрат при указанном перераспределении поставок.

Первоначально затраты на перевозку (табл. 7.9) .

После перераспределения (табл. 7.10) .

Таблица 7.10

Тогда, учитывая экономический смысл оценки свободной клетки, получаем, что . Так как среди клеток табл. 7.9 поставок есть клетка с отрицательной оценкой, то распределение поставок не оптимально.

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

При вычислении F многие слагаемые из F _nи F _нвзаимно уничтожаются, не влияя на значение F: существенны лишь коэффициенты затрат тех клеток, в которых поставка при рассматриваемом перераспределении изменится. При этом в выражение для F некоторые из них входят со знаком "+", а некоторые - со знаком "-". Для нахождения "правила знаков" удобен следующий чертеж (рис. 7.1), включающий клетки, в которых будет изменена поставка (слева и сверху от каждой клетки написан ее номер: клетки, соответствующие базисным переменным, перечеркнуты).

(1,3)   (3,3)

5 +

2 -

(1,2)

7 -

3 +

(3,2)

Рис.7.1

При этом знаком "+" помечены те клетки, поставка в которых увеличится. Видно, что именно их коэффициенты затрат войдут в выражение для F со знаком "+". В остальных клетках рис. 7.1 поставка уменьшится (в них вписан знак "-"), их коэффициенты затрат войдут в выражение для F со знаком "-". Ломаную на рис. 7.1, соединяющую клетки с изменяемой поставкой, будем называть означенным циклом пересчета.

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

Аналогично, составляя означенный цикл пересчета для каждой свободной клетки, можно найти ее оценку. При этом, конечно, цикл не всегда будет получаться таким простым, как в разобранном примере для клетки (1,3).

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

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

1. Ломаная должна быть связной, т.е. из любой ее вершины можно попасть в любую другую вершину по звеньям ломаной.

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

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

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

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

Теорема 7.3 (опотенциалах). Оценка свободной клетки не изменится, если к коэффициентам затрат, некоторой строки (столбца) таблицы поставок прибавить некоторое число. Это число, прибавляемое к коэффициентам затрат выделенной строки (столбца), будем называть потенциалом данной строки (столбца).

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

Пример 7.6. Найти оценки свободных клеток базисного распределения поставок, найденного в примере 7.3.

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

Начнем с первого столбца. Пусть потенциал этого столбца равен нулю (табл. 7.11). Рядом с потенциалом в скобках записываем номер шага; поставки опускаем.

Таблица 7.11 0(1) 0(6) -4(5) -1(3)

(7.13)

После прибавления этого потенциала к коэффициентам затрат первого столбца коэффициент затрат заполненной клетки (2,1) не изменится; чтобы полученный после сложения коэффициент стал равен нулю, потенциал второй строки табл. 7.11 должен быть равен - 1. Для обнуления коэффициента затрат клетки (2,4) потенциал четвертого столбца должен быть равен -1 и т.д. Измененные коэффициенты затрат удобно выписать в виде отдельной матрицы оценок (7.13). Элементы матрицы оценок, соответствующие свободным клеткам таблицы поставок, равны оценкам этих свободных клеток.

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