2. Лекции Практические и лабораторные занятия
жүктеу/скачать 0,77 Mb.
|
- Бұл бет үшін навигация:
- Лекция 6. Двойственные задачи линейного программирования Содержание лекционного занятия
| Вопросы для самоконтроля:
1.Основные элементы линейной алгебры. Их роль при построении модели. 2.Анализ моделей на чувствительность. Виды моделей.
1.Ашманов С.А. Линейное программирование. —М.: Наука, 1981. 2.Айсагалиев А.С., Айсагалиева С.С. Лекции по методам оптмизации.-Алматы:Гылым,1996
Прямая задача Двойственная задача Одним из центральных и наиболее значительных мест в теории линейного программирования является двойственность, которая состоит в том, что каждой исходной (прямой) задаче, в которой целевая функция стремится к максимуму (минимуму): F = c1,x1,+с2х2+с3х3+... + сnхn ->max(min), (1) система функциональных ограничений представляет собой систему неравенств: () система прямых ограничений также представляет собой систему неравенств: (3) соответствует двойственная задача, в которой: целевая функция стремится к минимуму (максимуму): Z(y) = y1,b1, +y2b2+...+ ymbm -»min(max) (4) система функциональных ограничений, представляет собой систему неравенств: (5)
• система прямых ограничений также представляет собой систему неравенств: у10,У20,Уз0...Уm0. (6) Общим для прямой и двойственной задач является то, что в каждой из них отыскивается экстремум линейной функции, а искомые переменные должны удовлетворять системам функциональных и прямых ограничений. Кроме того, в обеих задачах используются одни и те же параметры: элементы матрицы А, вектор В, вектор С. Отличие между прямой и двойственной задачей состоит в том, что в прямой задаче определяются значения n переменных x1,x2,...,xn, а в двойственной — m переменных: y1, y2,…, ym в исходной задаче ищется максимум, а в двойственной — минимум целевой функции, знаки неравенств в этих задачах противоположны, компоненты вектора ограничений в одной из задач являются коэффициентами при переменных в целевой функции другой задачи. Чтобы к заданной прямой задаче сформировать двойственную, целесообразно пользоваться определенной системой формальных правил. Число переменных в двойственной задаче равно количеству функциональных ограничений в прямой задаче (т.е., если в прямой задаче вектор переменных записывается, как n-мерный вектор-столбец, то в двойственной задаче вектор переменных будет представлять собой m-мерный вектор — строку и наоборот). 2. Если прямая задача ставится как задача максимизации, то двойственная — как задача минимизации и наоборот. 3. Компоненты вектора функциональных ограничений В=(bi,b2,...bm) в прямой задаче становятся коэффициентами целевой функции в двойственной задаче. Применение этих трех правил позволяет сформировать целевую функцию двойственной задачи: Z(y) = y1 b1 + у2b2 +...+ yrabm -> min . Матрица коэффициентов при переменных в системе функциональных ограничений двойственной задачи получается транспонированием матрицы коэффициентов при переменных в системе функциональных ограничений прямой задачи. 5. Знак неравенств функциональных ограничений в прямой задаче меняется на обратный в двойственной, т.е. « » на « ». 6. Коэффициенты целевой функции прямой задачи c1,c2,...,cn, становятся вектором ограничений в двойственной задаче. Применяя правила 4, 6 мы можем сформировать систему функциональных ограничений обратной задачи: 7. Прямые ограничения на неотрицательность переменных для двойственной задачи сохраняются. У10,у20,у30...уm0 Таким образом, исходную и двойственную к ней задачу можно представить следующим образом: Прямая и двойственная задача, построенная в соответствии с рассмотренными выше правилами, называются симметричными взаимодвойственными задачами. Если к двойственной задаче снова построить двойственную задачу, то получим прямую (т.е. исходную) задачу. Необходимо отметить, что ни одна из двойственных задач не является основной, так как если поставлена одна из задач, то другая может быть сформулирована как двойственная и каждая из них является двойственной по отношению к другой. жүктеу/скачать 0,77 Mb. Достарыңызбен бөлісу:
|