Решение. Решение двойственной задачи графическим методом

Практическая часть

Решение двойственной задачи графическим методом

Задание 1. Решить задачулинейного программирования

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

x₁, x₂, x₃ 0

графическим методом

Решение

1. Анализируя формальную постановку задачи, можно констатировать, что напрямую данную задачу решить графическим методом не представляется возможным (в целевой функции три переменных).

Воспользуемся теоремой равновесия из теории двойственности и перейдем к двойственной задаче.

Исходная задача поставлена на максимум, а неравенства в ограничениях имеют вид ≤, следовательно никаких дополнительных преобразований делать нет необходимости.

2. Запишем расширенную матрицу системы

А =

Транспонируем матрицу А

А^Т =

3. Запишем двойственную задачу

Целевая функция Z = y₁ + 22y₂ + 19 → max,

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

;

.

y₁, y₂ ≥ 0.

В целевой функции двойственной задачи две переменные и поэтому ее можно решить графическим методом.

4. Решение двойственной задачи (самостоятельно, коллективно).

Получили решение Z*(y₁*, y₂*) = (9, 14), Z = 336.

5. На основании теоремы равновесия

имеем в развернутом виде:

,

,

,

Решив эту систему уравнений, получим X* = (2, 3, 0).

Подставим полученные значения в целевую функцию исходной 9прямой) задачи, получим

F = 22 x 2 + 91 x 3 - 37 x 0 + 19 = 336 (как и в двойственной задаче, что соответствует первой теореме двойственности).