Система ограничений в каноническом виде

Рассмотрим общую задачу линейного программирования с ограничениями и переменными, записанную в стандартной форме

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

Как правило, число уравнений задачи меньше числа переменных (), поэтому множество ее допустимых решений бесконечно. Следовательно, выбор наилучшего допустимого решения, максимизирующего , нетривиален.

Идея симплекс-метода опирается на известный метод решения систем линейных алгебраических уравнений Жордана-Гаусса, основная идея которого заключается в приведении системы уравнений с неизвестными к каноническому или ступенчатому виду при помощи элементарных операций над строками. Предположим, что выражаются первые неизвестных через остальные, тогда каноническая система имеет вид:

(2.7)

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

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

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

1. Умножение любого уравнения системы на положительное или отрицательное число.

2. Прибавление к любому уравнению другого уравнения системы, умноженного на положительное или отрицательное число.

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

Определение 2.9. Базисным решением системыв каноническом виде называется решение, полученное при нулевых значениях небазисных переменных.

Например, в системе (2.7) одно из базисных решений задается как …, . Если при этом неотрицательные, то полученное решение называется допустимым базисным решением.

Определение 2.10. Базисное решение называется допустимым, если значения входящих в него переменных неотрицательны.

В системе (2.7) для удобства записи в качестве базисных используются первые переменных. В действительности для получения канонической системы уравнений и базисного решения любые из переменных можно выбрать в качестве базисных. Это означает, что максимальное количество базисных решений задачи линейного программирования с ограничениями и переменными, записанной в стандартной форме конечно и выражается следующим образом (число сочетаний из по ):

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

Уже отмечалось выше, что если задача линейного программирования имеет оптимальное решение, то это решение достигается хотя бы в одной из вершин допустимой области. Можно показать, что каждая вершина допустимой области соответствует некоторому допустимому решению системы ограничений. Поэтому оптимальное решение задачи линейного программирования можно найти путем перебора допустимых базисных решений. Этот процесс будет конечным, так как число допустимых базисных решений не превосходит величины .

В соответствии с вышесказанным, для нахождения оптимального решения задачи линейного программирования представляется достаточным найти с помощью метода Жордана-Гаусса все возможные допустимые базисные решения и затем выбрать из них то, которому соответствует наилучшее значение целевой функции. Однако решение задач линейного программирования симплекс-методом оказывается более эффективным, поскольку при этом анализируется лишь часть всех допустимых базисных решений.