Анализ чувствительности решения к изменению правых частей ограничений

Рассматривается анализ чувствительности решения к изменению коэффициентов c_j и b_i (3.15), (3.16). Для исследования задач линейного программирования на чувствительность решения к изменению исходных параметров задачи используется понятие вектора устойчивости решения.

Решение задачи можно записать через матрицу перехода конечной симплекс-таблицы

, (6.17)

где [ X_B ] – матрица-столбец базисных переменных конечной симплекс-таблицы;

[ P ] – матрица перехода конечной симплекс-таблицы прямой задачи;

[ b₁,…,b_i,…,b_m_-1 ] ^T – матрица-столбец свободных членов исходной симплекс-таблицы;

[ B ] – матрица-столбец свободных членов конечной симплекс-таблицы.

Если для исследования на чувствительность коэффициентов b_i дать каждому из них в исходной симплекс-таблице некоторое приращение Db_i, то результат решения получит некоторое приращение:

. (6.18)

[ DB ] является вектором устойчивости опорного или оптимального решения к изменению коэффициентов b_i.

Тогда [DB] можно определить как

. (6.19)

Исходя из условия неотрицательности значений переменных [ X_B ] и, следовательно, неотрицательности [ DX_B ]= [ DB ] ³ 0 можно найти пределы изменения каждого коэффициента Db_i.

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

Вектор устойчивости решения прямой задачи к коэффициентам b_i запишется:

Условия неотрицательности компонент вектора [ DB ] приводят к системе неравенств:

или после приведения подобных членов:

. (6.20)

Анализ изменений всех коэффициентов одновременно затруднителен и требует решения сложных систем неравенств.

На практике предполагается изменение только одного коэффициента, например Db₁, и тогда Db₁ ¹0, а остальные Db_i =0, , при таких условиях решается рассмотренная выше система неравенств для определения допустимых пределов изменения b₁. Аналогично исследуются пределы изменения остальных коэффициентов b_i. Для определения пределов изменения целевой функции F прямой задачи, при соответствующих приращениях Db_i, используется полученное значение переменных двойственной задачи . Ранее установили, что каждому i -му ограничению прямой задачи соответствует переменная двойственной задачи. Если двойственная переменная в последней симплекс-таблице двойственной задачи находится в числе свободных и, следовательно, , то приращение целевой функции определяется как .