Скачать

Симплексный метод

Задача 1.

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

Вариант 3.

Найти наибольшее значение функции f(X) = - x₁ - x₂ + 2x₃ при ограничениях

2x₁ + x₂ + x₃ £ 2

x₁ - x₂ + x₃ £ 1,

x_j ³ 0, j = 1, 2, 3.

Решение.

Приведем задачу к каноническому виду, вводя дополнительные неотрицательные переменные x_4,5 ³ 0.

f(X) = - x₁ - x₂ + 2x₃ ® max

2x₁ + x₂ + x₃ + x₄ = 2

x₁ - x₂ + x₃ + x₅ = 1,

x_j ³ 0, j = 1, 2, 3, 4, 5.

Каноническая задача имеет необходимое число единичных столбцов, т. е. обладает очевидным начальным опорным решением.

Очевидное начальное опорное решение (0; 0; 0; 2; 1).

Решение осуществляется симплекс-методом с естественным базисом. Расчеты оформим в симплекс-таблицах