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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

тогда

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

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

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

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

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

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

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

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

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

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

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

где

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

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

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

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

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

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