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

В данном случае легко видеть, что изменение коэффициентов 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 и систе­му неравенств следует решать только для небазисных векто­ров-столбцов матрицы условий.

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

В результате решения задачи ЛП (сведенной к каноническому ви­ду - к форме равенств) получим информацию: вектор Х=(x1,x2,...,xm) оптимальных значений базисных переменных (значения небазисных пе­ременных равны 0); вектор оптимальных двойственных оценок ограни­чений задачи Y=(y1,y2,...,ym); матрицу, обратную к оптимальной ба­зисной В; вектор оценок векторов-столбцов матрицы условий Δ=( Δ1, Δ2,..., Δm,..., Δn); при этом все оценки для базисных векторов равны 0, для небазисных – неотрицательны (Δj ³ 0). Мы предполага­ем, что порядок следования векторов матрицы условий, а значит и искомых переменных xj, коэффициентов функции цели cj изменен в со­ответствии с их позицией в оптимальном решении; как известно, это не влияет на результаты.

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

Δj = Сбаз*B*Аj - cj, где Сбаз=(c1,c2,...,cm) – вектор базисных коэффициентов функции цели; Аj – j-ый столбец матрицы условий; Δj - оценка вектора-столбца матрицы условий.

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

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

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

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

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

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

dF(b1,b2,...,bm)

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

dbi

следовательно, dF = F(b1+h1,b2+h2,...,bm+hm)-F(b1,b2,...,bm) = y1*h1+y2*h2+...+ym*hm= (Y,h) = SUM yi*hi

Наши рекомендации