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

Пример 1:

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

Решение от преподавателя:

Переменные x₃ и x₄ можно считать базисными, так как каждая из них входит только в одно уравнение, причем с единичным коэффициентом. Выразим базисные переменные через свободные:

Подставим эти выражения в целевую функцию и запишем условия неотрицательности всех переменных. У нас получится система:

Если наша задача разрешима, то целевая функция z достигает своих экстремумов в тех же точках, что и функция . Поэтому рассмотрим задачу с целевой функцией z′:

Решаем полученную задачу линейного программирования: строим допустимое множество, ограниченное соответствующими прямыми, градиент целевой функции c и линию уровня функции z′. Передвигая эту линию уровня параллельно себе вплоть до касания с допустимым множеством, получаем точку минимума a и точку максимума b.

Точка минимума получена при пересечении прямой с осью x₁, поэтому x₂ = 0, и, следовательно, x₁ = 4. Таким образом, координаты точки a равны (4, 0). Для нахождения координат точки максимума достаточно решить систему, которая состоит из уравнений, определяющих прямые (1) и (2):

x₂ = −4. Из нее находим координаты точки b = (1, 3). Осталось вычислить для этих точек значение целевой функции и оставшиеся две координаты x₃, x₄. В результате получим следующий