Область устойчивости решения при изменении коэффициентов функции цели

В данном случае легко видеть, что изменение коэффициентов c1,c2,...,cn на некоторые величины g1,g2,...,gn влияет только на оценки столбцов матрицы условий, и следовательно, на выполнение условий оптимальности.

Отсюда вытекает, что значения вектора g = (g1,...,gn) должны в области устойчивости удовлетворять соотношениям:

Δj + Δj пр. = (Сбаз+gбаз)* B*Аj-(cj+gj) ³ 0, j=1,...,n

Так как произведение BAj, j=1,...,m (для базисных столбцов) дает единичную матрицу, то соответствующие оценки равны 0 и систе­му неравенств следует решать только для небазисных векто­ров-столбцов матрицы условий.

Область устойчивости решения задачи ЛП при изменении эле­ментов вектора ограничений.

В результате решения задачи ЛП (сведенной к каноническому ви­ду - к форме равенств) получим информацию: вектор Х=(x₁,x₂,...,x_m) оптимальных значений базисных переменных (значения небазисных пе­ременных равны 0); вектор оптимальных двойственных оценок ограни­чений задачи Y=(y₁,y₂,...,y_m); матрицу, обратную к оптимальной ба­зисной В; вектор оценок векторов-столбцов матрицы условий Δ=(Δ₁, Δ₂,..., Δ_m,..., Δ_n); при этом все оценки для базисных векторов равны 0, для небазисных – неотрицательны (Δj ³ 0). Мы предполага­ем, что порядок следования векторов матрицы условий, а значит и искомых переменных x_j, коэффициентов функции цели c_j изменен в со­ответствии с их позицией в оптимальном решении; как известно, это не влияет на результаты.

Базисная матрица В размерности (m * m); обратная к ней (обозначим ее через В^-1) служит основой для расчета всех параметров конечной симплексной таблицы; так, из ра­венства ВX = b следует Х = Вb; где Х – вектор базисных компонент опти­мального решения, b - вектор правых частей ограничений задачи; кроме этого, известно:

Δ_j = Сбаз*B*Аj - c_j, где Сбаз=(c₁,c₂,...,c_m) – вектор базисных коэффициентов функции цели; Аj – j-ый столбец матрицы условий; Δ_j - оценка вектора-столбца матрицы условий.

Так как план оптимален, то выполняются условия:

Δ_j ³ 0, j =1,2,...,n – условия оптимальности;

X = Bb ³ 0, – условия допустимости решения.

Пусть вектор правых частей b = (b1,b2,...,bm) не является фиксированным – некоторые из его компонент (или все) изменяются; эти изменения можно задать вектором h = (h₁,h₂,...,h_m), так что правые части ограничений принимают вид: b₁+h₁, b₂+h₂,...,b_m+h_m или в фор­ме вектора b+h, где величины h₁,h₂,...,h_m должны быть такими, что­бы новое решение имело ту же структуру (базис), что и исходное. Отсюда следует, что такие значения вектора h и определяют область устойчивости исходного плана (базиса). Действительно, условия оп­тимальности решения в этой области не зависят от вектора h (базис не меняется), а для выполнения условий допустимости необходимо: X+Xпр = B(b+h) ³ 0

Эти соотношения (система из m линейных неравенств и задают область устойчивости решения относительно изменения правых частей ограничений.

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

dF(b₁,b₂,...,b_m)

–––––––––––––– = y_i, i=1,2,...,m

db_i

следовательно, dF = F(b₁+h₁,b₂+h₂,...,b_m+h_m)-F(b₁,b₂,...,b_m) = y₁*h₁+y₂*h₂+...+y_m*h_m= (Y,h) = SUM y_i*h_i