Определение диапазонов допустимых изменений коэффициентов при переменных в целевой функции F

Под допустимыми понимают такие изменения этих коэффициентов, при которых оптимальный базис рассматриваемой ЗЛП (т.е. базис при последней итерации симплекс – метода, соответствующий оптимальному решению) остается оптимальным.

Пусть изменениям подвергнется коэффициент . Обозначим через J_б, J_неб множество индексов базисных и небазисных векторов в оптимальном плане x0 соответственно.

Найдем значения оценок после изменения c_r для двух случаев:

1) rÎ J_неб, тогда

для всех j≠r;

для j=r; (5)

2) rÎ J_б,

jÎJ_неб (6)

Очевидно, что для сохранения оптимальности прежнего плана при изменениях коэффициента c_r необходимо и достаточно сохранение знаков оценок для всех небазисных переменных. Поэтому из условий ≥0 в соответствии с формулами (5) и (6) можно определить допустимые изменения коэффициента , при которых сохраняется прежнее оптимальное решение. Если одновременно изменяются несколько коэффициентов, то

получим соотношения, аналогичные (6), в которых оценки будут функциями уже нескольких параметров (δ₁, δ₂,., δ_r). Решая совместно систему неравенств вида (c₁, c₂,.,c_r)≥0, jÎJ_неб, находим условия для , при которых прежний оптимальный базис сохраняется.

1.2.2 Определение диапазонов допустимых изменений параметров , i=1,…,n.

В задачах распределительного типа величина характеризует предельно возможный объем потребления i-го ресурса. Изменение значений свободных членов приводит к увеличению или уменьшению F_max. Это изменение F_max определяется величиной решения двойственной задачи½y*½ и может быть оценено таким образом только тогда, когда при изменении величин b оптимальный план исходной задачи остается неизменным.

Обозначим через Ax матрицу оптимального базиса задачи ЛП при векторе ресурсов b. Очевидно соответствующее оптимальное решение

x_опт= A^-1 _x b.

Предположим, что мы изменили вектор ресурсов b=|| b_i || на b_н=b+ ∆b и хотим узнать, как это повлияет на оптимальное решение. Для этого найдем новое соответствующее базисное решение

x_н = А^-1 _х b_н = А^-1 _х (b+∆b).

Если все компоненты x_iн ≥ 0, то это решение x_н = [x_iн] оптимально (т.е. оптимальный базис не изменился).