а) Небазисная переменая
Изменение коэффициента целевой функции небазисной переменной влияет на относительную оценку только этой переменной. Пусть коэффициент целевой функции изменится на величину 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)
D3 = 0. 1 + q*(-1. 0)
D5 = 0. 25 + q*(+1. 0)
Заметим что величины Aij имеют знаки противоположные тем, что приведены выше.
Диапазон значений для q вычисляется в соответствии с формулой:
(0. 25/-1. 0) <= q <= MIN (3. 5/0. 5, 0. 1/1)
-0. 25 <= q <= 0. 1
Если q принимает значение равное одной из двух границ то относительная оценка некоторой небазисной переменной становится равной нулю Предельное значение до которого можно увеличивать такую переменную вычисляется как и в предыдуащем примере с небазисными переменными
Так в нашем примере при q = 0. 1 относительная оценка переменной X3 равна нулю так что если коэффициент целевой функции переменной X2 увеличится на 0. 1 или более станет выгодно производить X3 и мы сможем производить MIN {3. 2/0. 5, 5. 6/0. 5} = 6. 4 единиц X3 когда X1 обратится в нуль и потребуется изменение базиса.
1. Существует диапазон изменения q коэффициентов целевой функции как базисных так и небазисных переменных в которых текущее оптимальное решение остается оптимальным. Для небазисных переменных существует только верхняя граница диапазона изменения q; для базисных переменных обычно существует и нижняя и верхняя граница.
При значении коэффициента целевой функции, выходящем за пределы этого диапазона текущее оптимальное решение становится неоптимальным, так как появится небазисная переменная с отрицательной относительной оценкой.
2. Изменение коэффициента целевой функции базисной переменной приводит к изменению значения целевой функции.
3. Эффект от изменения коэффициентов целевой функции можно рассматривать с двух позиций: с точки зрения сбыта нас интересуют равновесные цены; с точки зрения производства нас интересует диапазон изменения коэффициентов целевой функции, в пределах которого текущий план (представленный текущим базисом) остается оптимальным.