Задание 2. построить двойственную, решить исходную задачу симплекс-методом и получить оптимальное решение двойственной задачи.

Для задачи

F = 23x₁ + 40 x₂ +60 x₃ + 2x₄ - x₅ - 18 → max

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

;

;

x₁, x₂, x₃, x₄, x₅ ≥ 0

построить двойственную, решить исходную задачу симплекс-методом и получить оптимальное решение двойственной задачи.

Решение.

1.Построим двойственную задачу

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

А =

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

А_Т =

Двойственная задача примет вид

Z = 57y₁ + 9y₂ - 18 → min,

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

2. Решим исходную задачу симплекс – методом

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

Будем решать задачу с использованием надстройки EXCEL Поиск решения

Получим решение X* = (6, 0, 3, 0, 0) и F(X*) = 300.

Ненулевыми решениями являются х₁ и х₃ , поэтому из исходной задачи имеем

Р₀ = . С₀ = (23, 60).

Тогда, оптимальное решение двойственной задачи вычисляется по формуле

Y* = C₀ P₀^-1 .

P₀ ^-1 – получим с использованием EXCEL.

P₀^-1 = .

Y* = (23, 60) = (5, 5; 0, 5).

Тогда, для двойственной задачи

Z = 57 5, 5 + 9 0, 5 - 18 = 300, что совпадает с первой теоремой двойственности.