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

Пусть имеем задачу линейного программирования в канонической форме:

(2.1)

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

Симплекс-метод заключается в целенаправленном переборе допустимых базисных решений канонической задачи линейного программирования:

1. Ищется начальная базисная точка.

2. На последующих шагах переход от одного базисного решения к другому осуществляется по правилам.

Правило 1. В базис переводится переменная x_i, которая имеет в целевой функции коэффициент, максимальный по модулю среди отрицательных.

Правило 2. Из базиса исключается переменная x_i, для которой выполняется условие:

, (a_i,j > 0),

где x_i,j - коэффициент при x_i; b_i - свободный коэффициент, правая часть уравнения.

Правило 3. Если целевая функция не содержит отрицательных коэффициентов при х, то оптимальное решение найдено.

Правило 4. Если при c_i не существует x_i,j >0, то задача не имеет решения.

Задание. Исходные данные в приложении 2.

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

2. Решить задачу симплекс-методом.

3. Записать результат.