E Aij*Xj <= Bi можно рассматривать как равенство в точке оптимума, т. е. E Aij*Xj = Bi
Теперь по определению относительная оценка этой небазисной переменной - это величина на которую может возрасти целевая функция при увеличении этой переменной на единицу. Так как решение оптимально то относительная оценка положительна (неотрицательна) и поэтому целевая функция должна уменьшаться если дополнительная переменная возрастает и возрастать если дополнительная переменная уменьшается Пусть например i-я компонента вектора ограничений увеличилась на единицу, так что ограничение примет вид
_
E Aij*Xj = Bi + 1
или после перестановки _
E Aij*Xj +(-1) = Bi
то есть дополнительная переменная Xs должна принять значение равное -1 чтобы i-ое ограничение оставалось равенством а относительная оценка даст соответствующее приращение целевой функции. Таким образом относительная оценка i-ой дополнительной переменной дает величину прироста целевой функции на единицу увеличения элемента Bi вектора ограничений. Так как элемент Bi обычно представляет собой объем i-го ресурса то относительная оценка равная Yi называется оценкой ресурса (оценкой единицы i-го ресурса) ибо она представляет относительную ценность единицы дополнительного ресурса. Эти относительые оценки являются маргинальными оценками в том смысле что они действительны лишь при таком диапазоне изменения ресурсов Bi когда текущий базис остается оптимальным. в) Если дополнительная переменная является базисной в точке оптимума то ее относительная оценка по определению равна нулю. Это также имеет смысл так как если ресурс использован не полностью
_
E Aij*Xj < Bi то цена которую мы должны были бы заплатить за дополнительную единицу этого ресурса равна нулю. Это приводит к условию дополняющей нежесткости:
В оптимальном решении или E Aij*Xj = Bi или Yi = 0 (либо и то и другое)
или E Aij*Yi = Cj или Xj = 0 (либо и то и другое)
Заметим что переменные Y недопустимы на протяжении всех итераций симплекс-метода до тех пор пока не будет достигнуто оптимальное решение.
МАРГИНАЛЬНЫЕ ОЦЕНКИ
Оценки ресурсов связаны скорее с ограничениями а не с переменными.
Однако они часто используются для вычисления оценочных или стоимостных показателей, связанных с переменными прямой задачи. Рассмотрим пример. Пусть в задаче связанной с суточной переработкой нефти некоторая переменная Xj соответствует объему неочищенной нефт закупаемой по цене 12. 65 долл/баррель (Сj = -12. 65) Существует ограничение сверху на объем закупаемой по этой цене неочищенной нефти равный 50 тыс. баррель/день.
Это можно записать уравнением: Xj + Xs = 50
Где Xs - это дополнительная переменная. Пусть она имеет относительную оценку равную 1. 04 долл/баррель в оптимальном решении - что это означает ? Оценка ресурса неочищенной неочищенной нефти равна 1. 04 долл/баррель, но это вовсе не означает, что мы должны были заплатить только 1. 04 долл за каждый дополнительный баррель неочищенной нефти. Это означает что мы должны быть готовы заплатить еще по 1. 04 долл/баррель за возможность покупать дополнительный объем этой нефти при условии, что последующие закупки будут осуществляться по цене 12. 65 долл/баррель: то есть целевая функция будет увеличиваться на 1. 04 долл за каждый дополнительный баррель, который мы сможем купить по цене Сj уже учтенной в целевой функции. Это означает, что м должны быть готовы к повышению цены до 12. 65 + 1. 04 = 13. 69 долл/баррель за дополнительную поставку неочищенной нефти.
Заметим, что 13. 69 долл/баррель - это равновесная цена при которой мы будем увеличивать нашу целевую функцию Р, если будем покупать по более дешевой цене чем эта: будем уменьшать Р если будем покупать за большую цену: сохраним Р неизменной если будем покупать точно за 13. 69 долл/баррель.
Если мы определим что МАРГИНАЛЬНАЯ ОЦЕНКА = РАВНОВЕСНАЯ ЦЕНА
ДЕЙСТВИТЕЛЬНАЯ ЦЕНА, то в нашем примере МАРГИНАЛЬНАЯ ОЦЕНКА = 13. 69 - 12. 65 = 1. 04 долл/баррель.
Маргинальная оценка переменной Xj - мэто чистый доход, который может быть получен за каждую единицу Xj закупленную сверх существующего
лимита и равна оценке ресурса, то есть двойственной переменной того условия задачи которое ограничивает количество имеющегося ресурса
Маргинальная оценка остается постоянной только внутри некоторой окрестности существующего оптимума, соответствующей пределам, внутри
которых текущий базис остается оптимальным как при увеличении так и при уменьшении объема ресурсов (объема закупок). Относительную оценку которая отвечает небазисной переменной равной своей нижней границе часто рассматривают как чистый эффект этой переменной. Если принимают решение (неоптимальное) увеличить небазисную переменную равную своей нижней границе то эта относительная оценка показывает уменьшение Р на единицу увеличения переменной (до некоторых пределов). Здесь относительные оценки указывают на эффект (убытки), обусловленный отклонением от оптимального решения.
Так как компоненты вектора Aj (где j - номер небазисной переменной)
показывают величину изменения значений текущих базисных переменных
то их часто называют (маргинальными) нормами замещения, так что Aij
- это норма замещения способа производства i на способ
производства j.
ДИАПАЗОНЫ УСТОЙЧИВОСТИ
Часто говорят, что постоптимальный анализ - наиболее важная часть линейного программирования и нетрудно понять почему делается такой вывод. Большая часть параметров задачи ЛП точно не известна и на практике обычно берутся приближенные значения, которым должны быть равны эти параметры. Таким образом нас интересуют такие диапазоны изменения этих параметров, в которых оптимальное решение остается оптимальным в том смысле, что не меняется базис. Исследуем три класса параметров:
коэффициенты целевой функции Cj
компоненты вектора ограничений Bi
коэффициенты матрицы Aij
Изменения коэффициентов целевой функции
а) Небазисная переменая
Изменение коэффициента целевой функции небазисной переменной влияет на относительную оценку только этой переменной. Пусть коэффициент целевой функции изменится на величину q тогда
_ _
Cj = Cj + q отсюда Dj = Dj - q
Например пусть матрицей А задан производственный процесс и пусть переменная Xj представляет количество некоторого производимого продукта, который может быть продан по цене Cj = 20 долл/ед В оптимальном решении эта переменная небазисная (=0) и ее относительная оценка = 1. 40 долл/ед Таким образом если цен возрастет до 21. 40 долл/ед продукта то относительная оценка станет = 0 и дальнейшее увеличение цены приведет к отрицательной относительной оценке. Это означает что текущее решение перестает быть оптимальным. В таком случае выгодно производить продукт представленный переменной Xj Следовательно 21. 40 долл/ед продукта это равновесная цена для Xj , при любой более низкой цене оптимальное решение будет состоять в том чтобы совсем не производить этот продукт ( Xj остается небазисным) а при более высокой цене выгодно ввести Xj в базис. Для небазисной переменной диапазон устойчивости в котором Cj может меняться так чтобы текущее решение оставалось оптимальным задается выражением _
_ Cj + q, где -оо < q <= Dj
и где Dj - относительная оценка переменной Xj отвечающая оптимальному решению. Заметим что при любом отрицательном q относительная оценка этой переменной останется положительной. Многие ППП ЛП дают информацию и о диапазоне изменения переменной Xj (от нулевого до некоторого предельного_значения) при котором не происходит смены базиса. Если q = Dj то относительная оценка = 0 что означает что Xj можно увеличивать не меняя значения целевой функции. Предельное значение до которого можно увеличивать Xj определяется формулой MIN (B/Aj)i Например предположим что в оптимальном решении вектор базисных переменных, -1 -1 текущий вектор ограничений B=B * b и вектор Aj=B *aj заданы в виде:
X5 3. 2 0. 6
Xb = X1 B = 1. 5 Aj = 0. 3
X6 5. 6 -1. 2
Тогда получаем MIN (Bi/Aij) = 1. 5/0. 3 = 5. 0
Таким образом мы можем сделать вывод о том что при цене в 21. 40 долл/ед продукта или более становится выгодным производить продукт Xj то есть продукт которому отвечает переменная Xj ; на каждую единицу произведенного продукта Xj переменные X5 X1 X6 уменьшаются соответственно на 0. 6 0. 3 -1. 2 единиц. Если мы произведем 5. 0 ед продукта Xj то переменная X1 обратится в нуль и дальнейшее увеличение Xj потребует смены базиса. Заметим, что мы получили всю информацию не решая задачу заново, для продолжения анализа нам потребуется лишь выполнить операцию исключения соответствующую изменению базиса.
б) Базисная переменная
Изменение коэффициента целевой функции базисной переменной влияет на относительные оценки небазисных переменных Рассмотрим увеличение коэффициента целевой функции i-ой баисной переменной. В этом случае вектор коэффициентов целевой функции изменится следующим образом
_
Cb = Cb + q*Ei, где Ei - вектор специального вида i-ая компонента которого = 1 а остальные нулю. Например
E3 = 0
Относительная оценка j-ой небазисной переменной станет теперь равной
Dj = Dj + q*Aij
Для того чтобы решение оставалось оптимальным должно выполняться условие
Dj => 0 то есть Dj^ + q*Aij => 0, где Dj^ - относительная оценка соответствующая текущему оптимальному решению.
Для базисной переменной диапазон устойчивости в котором может изменяться Ci оставляя оптимальным текущее решение адается выражением Ci + q, где
MAX {Dj^/-Aij} <= q <= MIN {Dj^/-Aij}
i/Aij>0 i/Aij<0
Если отсутствуют коэффициенты Aij < 0 то q < +oo и аналогично если нет Aij > 0 то q > -oo
Например пусть оптимальное решение задано следующим образом:
Максимизировать Р= 31. 5 -3. 5X4 -0. 1X3 -0. 25X5
При условиях X1 = 3. 2 -1. 0X4 -0. 5X3 -0. 60X5
X2 = 1. 5 +0. 5X4 +1. 0X3 -1. 00X5
X6 = 5. 6 -2. 0X4 -0. 5X3 -1. 00X5
Если коэффициент целевой функции переменной X2 станет равным С2 + q то относительные оценки небазисных переменных изменятся следующим образом:
D4 = 3. 5 + q*(-0. 5)