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


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

Решение двойственных задач



Решение симметричных задач

 

Рассмотрим решение задач с использованием теорем двой­ственности.

 

 

Решим исходную задачу графическим методом, получим опт = (4, 1), при этом L( )mах = 3.

На основании 1-й теоремы двойственности

 

 

Так как x1, х2 > 0, то по 2-й теореме двойственности систе­му ограничений двойственной задачи можно записать в виде равенств:

 

 

Подставим опт в систему ограничений исходной задачи:

 

 

Тогда система ограничений двойственной задачи примет вид

 

 

Откуда опт = (0, 2/3, 1/3), при этом S( )min = 3.

Пусть дано решение двойственной задачи опт = (0, 2/3, 1/3), S( )min = 3, найдем решение исходной.

По 1-й теореме двойственности L( )max = S( )min = 3. Так как у2, y3 > 0, то по 2-й теореме двойственности второе и третье неравенства исходной задачи обращаются в равенства:

 

 

Откуда опт = (4,1), при этом L( )mах = 3.

Рассмотрим решение задач методом, основанным на взаимно однозначном соответствии между переменными: основным переменным исходной задачи соответствуют балансовые переменные двойственной, и наоборот. Для этого решим двойственную задачу симплексным методом:

 

 

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

 

 

Из табл. 22.1 следует, что опт = (0, 2/3, 1/3), S( )min = 3.

 

 

На основании 1-й теоремы двойственности получаем

 

 

Решение другой задачи найдем по соответствию между пе­ременными:

 

 

Значение xj определяем по последней симплексной таблице в строке Δi в соответствующем столбце, причем значения xj ­берем по модулю:

 

 

Таким образом, решение исходной задачи:

 

 

Если исходная задача решена симплексным методом, то ре­шение двойственной задачи может быть найдено по формуле

 

 

где С — матрица-строка коэффициентов при базисных пере­менных целевой функции в оптимальном решении исходной за­дачи; А-1 — обратная матрица для матрицы А, являющейся матрицей коэффициентов базисных переменных системы огра­ничений исходной задачи в оптимальном решении.

Решим симплексным методом исходную задачу вида

 

 

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

 

 

Из табл. 22.2 следует, что опт = (4,1), L( )max = 3. Мат­рицы записываются в виде

 

 

тогда

 

 

Таким образом, решение двойственной задачи следующее:

 

 

Решение несимметричных задач

 

Рассмотрим решение задач с использованием теорем двой­ственности.

 

 

Решив двойственную задачу графическим методом, полу­чим

 

 

По 1-й теореме двойственности L( )min = S( )max = 33/2.

Подставим опт в систему ограничений двойственной за­дачи:

 

 

Так как х3 = х4 = 0, то система ограничений исходной задачи примет вид

 

 

Решая данную систему, получим

 

 

Рассмотрим решение задач с использованием обратной матрицы.

Пусть решение исходной задачи

 

 

Решение двойственной задачи найдем по формуле

 

 

где

 

 

Таким образом, oпт = (1/2, 2), при этом S( )max = 33/2.

 

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

 

Смешанные двойственные задачи можно решать с исполь­зованием теорем двойственности.

 

 

Найдем оптимальное решение двойственной задачи:

 

 

По 1-й теореме двойственности

 

 

Так как х1 > 0, x3 > 0, то по 2-й теореме двойственности пер­вое и третье ограничения двойственной задачи выполняются в виде равенств:

 




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