Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Правила построения двойственной задачи к исходной задаче ЛП в общем виде


Помощь в написании учебных работ
1500+ квалифицированных специалистов готовы вам помочь

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

С любой задачей ЛП тесно связана другая линейная задача, называемая двойственной. Первоначальная задача называется прямой (или исходной). Пара симметричных двойственных задач имеет вид

Прямая задача , , . Двойственная задача , , .

Экономически пара взаимно двойственных задач может быть интерпретирована, например, так.

Прямая задача. Сколько и какой продукции , надо произвести, чтобы при заданных стоимостях единицы продукции , и объемах имеющихся ресурсов , и нормах расходов , , максимизировать выпуск продукции в стоимостном выражении?

 

Двойственная задача. Какова должна быть оценка единицы каждого из ресурсов , , чтобы при заданных количествах ресурсов , величина стоимости единицы продукции , и нормах расходов , , минимизировать общую оценку затрат на все ресурсы?

Переменные , называют оценками или учетными (неявными, теневыми) ценами.

Прямая задача , , , - произвольные, Двойственная задача ,   - произвольные, , ,

1.Упорядочивается запись исходной задачи: если целевая функция задачи исследуется на max, то ограничения должны иметь знак или =, а если на min, то ограничения должны иметь знак или =.

2. Каждому ограничению исходной задачи ставится в соответствие двойственная переменная , , и, наоборот, т.е. число переменных двойственной задачи равно числу ограничений прямой задачи, а число ограничений двойственной задачи равно числу переменных прямой задачи.

3. Если целевая функция прямой задачи исследуется на max, то целевая функция двойственной задачи используется на min, и наоборот.

4. Коэффициенты целевой функции прямой задачи становятся свободными членами системы ограничений двойственной задачи.

5. Свободные члены системы ограничений прямой задачи становятся коэффициентами целевой функции двойственной задачи.

6. Матрицы коэффициентов систем ограничений прямой и двойственной задач являются транспонированными друг к другу.

7. Если на переменную , прямой задачи наложено ограничение на знак, то j-е ограничение двойственной задачи записывается в виде неравенства и наоборот.

8. Если переменная , исходной задачи произвольная, то j-е огарничение двойственной задачи имеет знак равенства.

9. Если в прямой задаче имеются ограничения-равенства, то на соответствующие переменные двойственной задачи не налагаются условия неотрицательности.

Пример 6.

<== предыдущая лекция | следующая лекция ==>
Метод искусственного базиса | Пусть имеется симметричная пара взаимно двойственных задач

Дата добавления: 2013-12-13; Просмотров: 845; Нарушение авторских прав?;


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



ПОИСК ПО САЙТУ:


Читайте также:
studopedia.su - Студопедия (2013 - 2022) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.013 сек.