Помощничек
Главная | Обратная связь


Археология
Архитектура
Астрономия
Аудит
Биология
Ботаника
Бухгалтерский учёт
Войное дело
Генетика
География
Геология
Дизайн
Искусство
История
Кино
Кулинария
Культура
Литература
Математика
Медицина
Металлургия
Мифология
Музыка
Психология
Религия
Спорт
Строительство
Техника
Транспорт
Туризм
Усадьба
Физика
Фотография
Химия
Экология
Электричество
Электроника
Энергетика

Глава 22. ДВОЙСТВЕННОСТЬ В ЛИНЕЙНОМ ПРОГРАММИРОВАНИИ



 

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

Различают симметричные, несимметричные и смешанные двойственные задачи.

Виды двойственных задач и составление их математических моделей

 

Симметричные двойственные задачи

 

Дана исходная задача

 

 

при ограничениях:

 

 

Задача дана в неканоническом виде. Составим математичес­кую модель двойственной задачи, для этого:

— каждому неравенству системы ограничений исходной за­дачи приводим в соответствие переменную yi;

— составляем целевую функцию, коэффициентами которой являются свободные члены системы ограничений исход­ной задачи;

— составляем систему ограничений. Коэффициенты систе­мы ограничений образуют транспонированную матрицу коэффициентов системы ограничений исходной задачи. Знаки неравенств меняются на противоположные;

— свободными членами системы ограничений являются ко­эффициенты целевой функции исходной задачи. Все пе­ременные двойственной задачи неотрицательные.

Математическая модель двойственной задачи имеет вид

 

 

при ограничениях:

 

 

Несимметричные двойственные задачи

 

Дана исходная задача

 

 

при ограничениях:

 

 

Задача дана в каноническом виде. Составим математичес­кую модель двойственной задачи.

Для ее составления пользуются тем же правилом, что и для составления симметричной задачи, с учетом следующих особенностей:

— ограничениями двойственной задачи будут неравенства. Если в целевой функции двойственной задачи требуется найти минимум, то знак неравенства ≥, если максимум, то ≤;

— переменные yi — произвольные по знаку.

Математическая модель двойственной задачи имеет вид

 

 

при ограничениях:

 

 

Смешанные двойственные задачи

 

Математическая модель исходной задачи имеет условия симметричных и несимметричных задач. При составлении двойственной задачи необходимо выполнять правила симмет­ричных и несимметричных задач.

 




©2015 studopedya.ru Все права принадлежат авторам размещенных материалов.