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

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

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

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

(7.12).

где многоточием обозначены слагаемые, отвечающие свободным переменным, отличным от .г.•, F0 — суммарные затраты на перевозку данного распределения поставок. Тогда из выражения (7.12) следует, что оценка (V свободной клетки (i, j) равна приращению AF суммарных затрат на перевозку при переводе в клетку (г, J) единичной поставки (увеличение переменной ?^ от 0 до 1). Очевидно, что AF > 0, если > 0; AF < 0, если (V < 0. Последнее косвенное определение оценки свободной клетки обычно называют экономическим смыслом оценки свободной клетки.

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

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

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

Таблица 7.10

			5 1

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

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

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

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

Так как среди клеток табл. 7.9 есть клетка с отрицательной оценкой, то распределение поставок не оптимально. >

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

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

Рис. 7.1.

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

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

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

Рис. 7.2.

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

Оценка клетки (1, 1) в этом случае равна.

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

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

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

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

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

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

С другой стороны, справедлива следующая теорема.

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

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

? Пусть для фиксированной свободной клетки построен цикл. Для каждого звена этого цикла, входящего в произвольную выделенную строку, имеем пару соседних вершин цикла. По определению означенного цикла пересчета одна из этих двух вершин имеет знак «+», другая — знак «-». Тогда вклад от этих двух вершин в значение искомой оценки определяется разностью коэффициентов затрат этих вершин. Очевидно, что если к каждому из этих коэффициентов затрат прибавить одно и то же число, то само значение разности не изменится. ¦

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

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

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

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

Таблица 7.11

!!!

(7.13).

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

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

Решение транспортной задачи в случае получения неоптимального распределения поставок рассмотрим в следующем параграфе.

• [1] Доказательство этого утверждения см., например, в [17].