Студопедия.Орг Главная | Случайная страница | Контакты | Мы поможем в написании вашей работы!  
 

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



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

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

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

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

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

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

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

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

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

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

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

(3.10)

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

(3.11)

причем все

(3.12)

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

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

(3.13)

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

(3.14)

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

(3.15)

где zopt рассматривается как функция от b1, b2,…, bm. Разумеется, если сильно изменить bi, то точка , определяемая уравнением (3.13), будет неоптимальна и задачу придется решать сначала.





Дата публикования: 2015-01-10; Прочитано: 272 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!



studopedia.org - Студопедия.Орг - 2014-2024 год. Студопедия не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования (0.006 с)...