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

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

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

Решим исходную задачу графическим методом, получим опт = (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 — обратная матрица для матрицы А, являющейся матрицей коэффициентов базисных переменных системы ограничений исходной задачи в оптимальном решении.

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