<<
>>

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

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

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

Решим исходную задачу графическим методом, получим опт = (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.

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

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

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

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

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

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

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

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

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

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

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

Из таблицы следует, что опт = (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–й теореме двойственности первое и третье ограничения двойственной задачи выполняются в виде равенств:

<< | >>
Источник: Архаров Евгений Валерьевич. Учебно–методический комплекс по дисциплине Математика Нижний Новгород, 2011. 2011

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

  1. Глава V«РУССКАЯ ИДЕЯ», ИЛИ СВЕРХЗАДАЧА СОВРЕМЕННОЙ РОССИИ (Вместо заключения)
  2. Задача о кратчайшем пути.
  3. 7.7. Экономическая интерпретация решения задачи линейного программирования
  4. 7.8. Двойственные задачи линейного программирования
  5. 7.9. Экономико-математический анализ полученных оптимальных решений
  6. 9.4. Принятие решений в условиях неопределенности
  7. § 66. Двойственные задачи .линейного программирования и решение их двойственным симплексным методом
  8. § 67, Транспортная задача
  9.   Письмо шестнадцатое ТЕОРИЯ И ПРАКТИКА ПРОГРЕССА [†††] 1. Двойственность вопроса о прогрессе 
  10. ОБЩИЕ ПРОБЛЕМЫ И ЗАДАЧИ ИЗУЧЕНИЯ ЯЗЫКА РУССКОЙ ХУДОЖЕСТВЕННОЙ ЛИТЕРАТУРЫ
  11. 1. Постановка задачи исследования Марксом
  12. Основные теоремы двойственности
  13. Решение двойственных задач
  14. Экономический анализ задач с использованием теории двойственности
  15. Симплекс-метод. Основная идея, этапы поиска решений, алгоритм метода.
  16. Новые задачи американской разведки
  17. Использование линейной оптимизации при решении матричных игр
  18. Решение матричных игр в смешанных стратегиях с помощью Excel
  19. 4.2.2 Решение задачи симплекс-методом
  20. § 2. Обнаружение и фиксация источников и носителей доказательственной информации как основная задача первоначального этапа расследования преступлений