Диапазоны устойчивости

Мы видели, что задачи линейного программирования возникают во многих практических ситуациях. Примеры и упражнения предыдущих лекций могут дать представление об области применения симплекс-метода. Коэффициенты, входящие в математическую формулировку задачи, часто имеют физический смысл в практических задачах. Коэффициенты целевой функции могут выражать прибыль при коммерческих операциях. Значения, входящие в правые части ограничений, могут выражать ограниченность доступных ресурсов. Можно ожидать, что в подобных случаях эти значения будут меняться, что, в свою очередь, приведет к изменению формулировок математических задач. Например, благодаря повышению производительности труда может увеличиться доступное производительное время станков; пожар на складе может снизить поставки сырья; трудности, связанные с плохой погодой, могут привести к увеличению прибыли от продажи некоторых наименований товаров. Как действовать в подобных ситуациях?

Один из самых примитивных способов состоит в том, чтобы учесть возникающие физические изменения, поставить новую математическую задачу и решить ее с начала. Однако этот способ может быть весьма неэффективен; он не учитывает полезную работу, проведенную при решении задачи до изменений.

Давайте последовательно рассмотрим:

1) изменения в b_i (значения правых частей);

2) изменения в с_j (коэффициенты целевой функции);

3) включение дополнительных ограничений.

1) Изменения в b_i

Пусть исходные ограничения заданы в виде Ax=b и функция z=c^Tx должна быть минимизирована.

Пусть новая задача формулируется так:

с той же целевой функцией z=c^Tx.

Предположим, что исходная задача решена. Пусть в оптимальном базисе соответствующая подматрица матрицы В имеет обратную матрицу B^-1. Пусть π₁, π₂,…., π_m являются симплекс-множителями, а значения базисных переменных исходной задачи задаются формулой

(3.10)

Из уравнения (3.5) значение целевой функции выражается следующим образом:

(3.11)

причем все

(3.12)

(коэффициенты при базисных переменных равны 0, при небазисных переменных ≥0).

Теперь при изменении только коэффициентов b_i, уравнение (3.12) для новой задачи останется неизменным. Поэтому если базисное решение остается допустимым и для новой формулировки задачи, то оно будет и оптимальным базисным допустимым решением для этой задачи. Новые значения для базисных переменных находятся по формуле

(3.13)

Если х* > 0, то оно будет базисным допустимым значением для новой задачи, а также оптимальным решением уравнения (3.12). Новым значением функции z будет

(3.14)

Таким образом из уравнения (3.11) можно получить

(3.15)

где z^opt рассматривается как функция от b₁, b₂,…, b_m. Разумеется, если сильно изменить b_i, то точка , определяемая уравнением (3.13), будет неоптимальна и задачу придется решать сначала.