А). Изменение коэффициента в целевой функции при переменной, входящей в базис оптимального решения

Пусть коэффициент при переменной Х₁ изменятся следующим образом:

С₁^’ = С₁ + DC,

где DC - вариация коэффициента, которая может принимать как положительные, так и отрицательные значения.

Если решить задачу с новым значением коэффициента, то изменение потерпит только индексная строка, причем новое значение любого элемента, соответствующего небазисной переменной, определится соотношением:

(Z_j – C_j)^’ = (Z_j – C_j) + A_6j + DC, (14)

где A_6j - коэффициенты замещения, расположенные в последней симплекс-таблице в строке, соответствующей переменной Х₁.

Таким образом, приведенные соотношения позволяют на основе по­следней симплекс-таблицы вычислить новые значения элементов индексной строки, соответствующих небазисным переменным. Эта же формула справедлива для начального элемента индексной строки, то есть для преобразования значений целевой функции - (Z₀-С₀).

Элементы индексной строки, соответствующие базисным переменным, сохраняют нулевые значения.

Из соотношения (14) можно установить допустимые пределы изменения коэффициентов С₁. Действительно, для сохранения решения, зафиксированного в последней симплекс-таблице, необходимо, чтобы элементы индексной строки, соответствующие небазисным переменным, не были отрицательными.

Следовательно, для любого такого элемента должно выполниться условие:

(Z_j - C_j) + A_6j * DC 0 (15)

В соответствии с этим условием алгоритм определения допустимых значений вариации DC таков (рассмотрим его на примере задачи ДЗ-1 - табл.4).

Для выбранной базисной переменной (например, X₁) переберем все ненулевые коэффициенты замещения, стоящие в столбцах, соответствующих небазисным переменным. Делим соответствующие элементы индексной строки на выбранные коэффициенты замещения и результаты деления берем с обратным знаком:

X₅: -221/0.92 = -240

X₇: -2.39/0.0025 = -955

X₈: -269/0.92 = -292

X₁₁: -5.39/0.018 = -299

X₁₂: -12.3/(-0.049) = +251

Из полученных чисел выбираем наименьшего по модулю отрицательные и положительные числа. Они и задают диапазон допустимых значений вариации DC. Для рассмотренного примера этот диапазон составляет (-240,+251).

В). Изменение коэффициента в целевой функции при пе­ременной, не входящей в базис оптимального решения.

Для данного случая, не приводя подробного описания алгоритма, отметим только, что если, например, коэффициент при небазисной переменной Х5 (см. табл.4) изменить по фopмyле:

С₅^’ = C₅ + DC, (16)

то это приведет к изменению только элемента индекс­ной строки, соответствующего этой переменной:

(Z₅ – C₅)^’ = (Z₅ – C₅) – DC. (17)

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

DC (Z₅ – С₅).