Линейное программирование Двойственность в линейном программировании. - презентация

1 Линейное программирование Двойственность в линейном программировании

2 Виды двойственных задач Симметричная Не симметричная Смешанные

3 Алгоритм построения двойственной симметричной задачи L(x) = b1y1 + b2y2 +…+bmym min Каждому неравенству системы ограничений исходной задачи поставим в соответствие переменную yi Построим целевую функцию, слагаемыми которых являются произведения свободных коэффициентов исходной системы на соответствующие новые Составим систему ограничений, коэффициентами которой являются коэффициентами матрицы, транспонированной из коэффициентов исходной задачи Свободными членами в системе ограничений являются коэффициенты целевой функции исходной задачи. Знаки неравенства меняются на противоположные, целевая функция стремиться к минимуму, все yi 0

4 Не симметричные двойственные задачи Не симметричные двойственные задачи – это задачи, в которых система ограничений является равенством (задачи в каноническом виде)

5 Основное неравенство двойственности C1x1 +C2x2 +…+Cnxn b1y1 +b2y2 +…+bmym Для произвольного допустимого плана исходной и двойственной задачи Доказательство Умножим каждое неравенство в двойственной задачи на соответствующую переменную Xj и сложим все неравенства перегруппировав их

6 Теоремы Если одна из двойственных задач имеет оптимальное решение, то и вторая имеет такое же по значению целевой функции L(x) оптимальное решение Для оптимальности допустимых решений x и y,пары двойственных задач необходимо и достаточно выполнение следующих ограничений система

7 Пример симметричной двойственной задачи L(x) = x1-x2 max L(y) = 2y1 + 2y2 + 5y3 min Пусть найдено решение исходной задачи. L(x) опт=3 опт (4; 1) Используя две теоремы двойственности, получим: L(y) min = L(x) max = 3 по Теореме 1

8 Пример симметричной двойственной задачи Для определения решения двойственной задачи можно использовать способ, основанный на взаимнооднозначном соответствие переменных в конечном решении симплекс таблицы. Основными переменными исходной задачи соответствуют балансовые переменные двойственной задачи и наоборот. Решением исходной системы является x1=4 (второе уравнение в симплекс таблице), ей соответствует введенная в исходной системе переменная x4 (y2). Элемент на пересечении соответствующей строки и столбца дает: аналогично

9 Экономический смысл двойственной задачи L(y)= Пусть bi=1 => L yi – для оптимального решения найденной значение yi обозначает ценность рассматриваемого продукта Yi -условная цена единицы i- того ресурса, с его помощью можно определить степень влияния ограничений на значение целевой функции. Предельное значение (верхняя и нижняя границы ресурсов) для которых yi остается неизменным определяется следующим образом - значение в оптимальном решении - соотв. базису матрицы в оптимальном решении Если в план производства включаются новые виды продукции, то эффективность их включения в план можно оценить по формуле Если j < 0, то план улучшается и новую продукцию выгодно выпускать Если j > 0 производство не выгодно