Лекция 6: взаимно двойственные ЗЛП. Первая и вторая теоремы двойственности.
1. Взаимно двойственные задачи линейного программирования. 2. Первая теорема двойственности. 3.Вторая теорема двойственности. С каждой ЗЛП связана двойственная к ней задача. Из решения одной задачи находят решение другой. Пара взаимно двойственных ЗЛП имеет следующий вид.
Если ввести в рассмотрение матрицу из коэффициентов при неизвестных в системе (6.1), а также матрицы-столбцы
то получим другую (матричную) форму записи задач I и I¢:
Задачи I и I¢ называются двойственными друг другу. Смысл, который вкладывается в это название, состоит в следующем. 1. Если первая задача имеет размеры 2. Матрицы из коэффициентов при неизвестных в левых частях ограничений обеих задач являются взаимно транспонированными. Так, в задаче I матрица из коэффициентов при 3. В правых частях ограничений в каждой задаче стоят коэффициенты при неизвестных в целевой функции другой задачи. 4. В задаче I все ограничения представляют собой неравенства типа £, причем в этой задаче требуется достичь максимума f. Напротив, в задаче I¢ все ограничения суть неравенства типа ³, причем требуется достичь минимума j. Связь между оптимальными решениями двойственных задач устанавливается с помощью теорем двойственности.
Первая теорема двойственности. Если одна из взаимно двойственных задач (I) и (I¢) имеет оптимальное решение, то его имеет и другая, причем
Если в одной из задач (I) и (I¢) целевая функция не ограничена, то другая задача не имеет допустимых решений. Вторая теорема двойственности. Компоненты оптимального решения двойственной задачи равны абсолютным значениям коэффициентов при соответствующих неизвестных целевой функции исходной задачи, выраженной через свободные неизвестные ее оптимального решения. Связь между первоначальными неизвестными одной из двойственных ЗЛП и дополнительными неизвестными другой задачи в общем виде устанавливается следующей таблицей.
Перейдем к примерам. Пусть исходная задача – первая основная задача Лекции 3: Тогда двойственная ей задача имеет вид Решим ЗЛП М-методом. Сначала введем балансовые переменные Составим первую симплекс-таблицу
В последней строке четвертой симплекс-таблицы нет положительных чисел ( при Пользуясь теоремами двойственности нетрудно найти решение первой основной задачи.
Действительно, по первой теореме двойственности
Учитывая соотношения по второй теореме двойственности из последней строки четвертой симплекс-таблицы имеем т.е. Обратно, из последней строки симплекс-таблицы решение первой основной задачи легко находим решение двойственной задачи:
Экономический смысл рассмотренных взаимно двойственных ЗЛП. Задача I об использовании ресурсов Задачу I¢ можно трактовать следующим образом. Пусть на предприятии решили продать ресурсы Обозначим через
цена единиц ресурсов. Справедливое требование к ценам со стороны продающего предприятия состоит в следующем: если взять ресурсы, идущие на изготовление единицы товара Других требований к ценам Решения взаимно двойственных ЗЛП (I) и (I¢) имеет следующий экономический смысл: предприятию безразлично, производить ли продукцию по оптимальному плану (36; 16) и получить максимальную прибыль
Воспользуйтесь поиском по сайту: ![]() ©2015 - 2025 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...
|