Симплекс метод решения задач ЛП

Алгоритм решения задачи при помощи симплекс метода:

1. Вводятся переменные, позволяющие систему неравенств превратить в систему уравнений. (Ограничение-неравенство исходной задачи ЛП, имеющее вид « », можно преобразовать в ограничение-равенство добавлением к его левой части некоторой новой неотрицательной переменной, а ограничение-неравенство вида «» в ограничение равенство вычитанием из его левой части неотрицательной переменной. Переменные, вводимые для преобразования ограничений-неравенств в ограничения – равенства называют дополнительными. Их число равно числу преобразуемых неравенств.)

2. Выбирается переменная (рабочая переменная) входящая в целевую функцию с max коэффициентом (Уничтожать переменные целесообразно, начиная с самой «неподходящей для итогового вида», таким образом, выбирается переменная, входящая в уравнение с целевой функцией, которую уничтожим в первую очередь).

3. Сравниваются частные от деления свободных членов на коэффициенты при этой переменной и выбирается строка с min> 0 частным от деления (рабочее уравнение). (Выбирается уравнение, в котором рабочая переменная имеет «наибольший вес» относительно других переменных).

4. Рабочее уравнение нормируется (т.е. делится на коэффициент перед рабочей переменной), из остальных строк исключаем рабочую переменную методом Гаусса. (Проведение данной операции обусловлено необходимостью исключить возможность проявления уже исключенной из уравнения с целевой функцией переменной в дальнейшем при последующих преобразованиях.)

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

В качестве примера рассмотрим задачу решенную графическим методом, задачу про краски.

Решение

Введем свободные переменные x ₃, x ₄, x ₅, x ₆, для того, чтобы систему неравенств превратить в систему уравнений.

Выбираем переменную, входящую в целевую функцию с максимальным коэффициентом, это x ₁. Сравниваем частные от деления свободных членов на коэффициенты при x ₁ 6; 4; -1; +¥. Выбираем строку с min > 0 частным от деления и нормируем ее, из остальных строк исключаем x₁ методом Гаусса.

Выбираем переменную, входящую в целевую функцию с max коэффициентом, это x ₂. Сравниваем частные от деления свободных членов на коэффициенты при x₂ 4/3; 8; 10/3; 2. Выбираем строку с min > 0 частным от деления и нормируем ее, из остальных строк исключаем x ₂ методом Гаусса.

Так как все коэффициенты перед переменными в уравнении с целевой функцией < 0, то решение законченно.

В силу не отрицательности переменных из уравнения, содержащего целевую функцию следует, что она достигает максимального значения, в случае, когда x ₃ = 0 и x ₄ = 0, в этом случае