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

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

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

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

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

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

(14)

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

Пример. Проверим на оптимальность первоначальное базисное распределение поставок методом наименьших затрат. Установить является ли оптимальным базисное распределение поставок найденное в задаче таб. 5 (см. таб. 9).

Табл.9

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

Табл.10

Найдем изменение ∆F суммарных затрат при указанном перераспределении поставок. Первоначальные затраты (табл. 9).

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

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

β₁₃ = ∆F = F_n – Fн = 2 ∙ (-1) + 5 ∙ 1 + 3 ∙ 1 + 7 ∙ (-1) = -1

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

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

При вычислении ∆F многие слагаемые из F_П и F_Н взаимно уничтожаются не влияя на значения ∆F: существенны лишь коэффициенты затрат тех клеток, в которых поставка при рассматриваемом перераспределении изменится. При этом в выравнивании для ∆F некоторые из них входят со знаком +, а некоторые со знаком -. Для удобства покажем это на рис. 1.

Рис. 1

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

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

Например, клетка (1,1)

		+		-
		-						+
				+				- -

Оценка клетки:

Нахождение оценок свободных клеток можно упростить.

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

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

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

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

Табл.10

							-2(7)
							-1(2)
							-3(4)
0(1)	0(6)		-4(5)			-1(3)

(16)

После прибавления этого потенциала к коэффициентам затрат первого столбца коэффициент затрат заполненной клетки (2,1) не изменяется; чтобы полученный после сложения коэффициент стал равен 0, потенциал 2-ой строки таблице 10 должен быть равен -1; для обнуления коэффициента затрат (2,4) потенциала 4-го столбца должен быть равен -1 и т.д. Измененные коэффициенты затрат записываем в виде матицы(16).

Элементы матрицы оценок, соответствующие свободным клеткам таблицы поставок, равны оценкам этих свободных клеток.

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