![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
Мы видели, что задачи линейного программирования возникают во многих практических ситуациях. Примеры и упражнения предыдущих лекций могут дать представление об области применения симплекс-метода. Коэффициенты, входящие в математическую формулировку задачи, часто имеют физический смысл в практических задачах. Коэффициенты целевой функции могут выражать прибыль при коммерческих операциях. Значения, входящие в правые части ограничений, могут выражать ограниченность доступных ресурсов. Можно ожидать, что в подобных случаях эти значения будут меняться, что, в свою очередь, приведет к изменению формулировок математических задач. Например, благодаря повышению производительности труда может увеличиться доступное производительное время станков; пожар на складе может снизить поставки сырья; трудности, связанные с плохой погодой, могут привести к увеличению прибыли от продажи некоторых наименований товаров. Как действовать в подобных ситуациях?
Один из самых примитивных способов состоит в том, чтобы учесть возникающие физические изменения, поставить новую математическую задачу и решить ее с начала. Однако этот способ может быть весьма неэффективен; он не учитывает полезную работу, проведенную при решении задачи до изменений.
Давайте последовательно рассмотрим:
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; Прочитано: 274 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!