Основы симплекс-метода

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

Прямой перебор вершин выпуклого многогранника ограничений является трудоемким способом решения ЗЛП. Поэтому разработаны и разрабатываются алгоритмы направленного поиска оптимального решения. Наиболее распространенным методом поиска является симплекс-метод (метод последовательного улучшения плана). При использовании этого метода решение задачи распадается на два этапа:

1) отыскание координат первой вершины многогранника ограничений, или, в терминах линейного программирования, опорного решения (опорного плана, базисного решения);

2) отыскание координат вершины многогранника ограничений, соответствующей оптимальному значению (оптимального плана).

Таким образом, при использовании симплекс-метода вначале находят произвольную вершину многогранника, т.е. опорное решение ,определяют значение целевой функции в опорной вершине . Затем находят ребро многогранника ограничений, вдоль которого целевая функция наиболее быстро растет (если определяется максимум функции) или убывает (если отыскивается минимум), и находят следующую вершину многогранника ограничений вдоль этого ребра. Новую вершину принимают за опорную и всю процедуру повторяют, т.е.

и т. д.

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

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

Рассмотрим вычислительный аспект симплекс-метода.

Симплекс-метод является универсальным в том смысле, что позволяет решать задачу в общей постановке, хотя требует приведения ее к определенному (стандартному) виду:

Найти доставляющие минимум функции

(4.15)

при условиях

(4.16)

При m<n существует множество решений и это множество решений может быть представлено как

(4.17)

где – базисные переменные;

-свободные переменные;

-линейные функции свободных переменных.

Вследствие линейности функций равенства (4.14) могут быть приведены к виду

(4.18)

(4.19)

Здесь коэффициенты и свободные члены определяются величинами и , входящими в уравнения (4.16).

Системе уравнений (4.16) присуща следующая особенность: переменная входит только в уравнение с номером i=j, имея при этом коэффициент, равный единице, и не входят в остальные m-1 уравнений, для которых .

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

Частное решение системы (4.18), получаемое приравниваем свободных переменных к нулю, называется базисным. Оно имеет вид

(4.20)

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

1. Допустимое базисное решение системы уравнений (4.18) соответствует крайней точке области, определяемой системой линейных ограничений.

2. Если ЗЛП имеет оптимальное решение, то существует, по крайней мере, одно базисное оптимальное решение. Теперь симплекс-метод может быть определен как метод, предполагающий последовательный анализ базисных решений системы (4.16).

3. Базисное допустимое решение (4.20) является оптимальным тогда, когда коэффициенты при свободных переменных в функции (после ее выражения через свободные переменные) неотрицательны.

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

Допустим, что базисное решение (4.20) не является оптимальным, т.е. среди коэффициентов в функции есть отрицательные. Чтобы перейти от решения (4.20) к другому базисному решению нужно сделать отличной от нуля (ввести в базис) какую-то из свободных переменных , обратив в ноль одну из базисных переменных . Имея в виду ограничение , можно сказать, что при таком переходе уменьшится только тогда, когда вводимая в базис переменная будет иметь в выражении отрицательный коэффициент. Естественно, уменьшение будет тем заметнее, чем больше по модулю соответствующий коэффициент .

Обозначим через S тот номер j из m+1,…,n, для которого величина отрицательна и максимальна по модулю, т.е. . Вводим в базис и представим базисные переменные и в виде

(4.21)

Поскольку , нужно как можно больше увеличивать в стремлении минимизировать . Однако возрастание может продолжаться лишь до тех пор, пока какая-то из переменных не обратится в ноль. Это произойдет, если хотя бы один коэффициент в системе уравнений (4.21) положителен (по исходному условию (4.19) все ). Если же для нескольких индексов i из 1,2,…m, то при возрастании в ноль обратится первой та базисная переменная из (4.21), которой отвечает наименьшая величина отношения . Предположим, что эта переменная есть ,тогда предельное значение , до которого можно увеличить ,найдется как

(4.22)

.

При этом , так как , а .

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

Указанная процедура перехода может быть повторена, если новое базисное решение допускает дальнейшее улучшение (уменьшение) значения . Симплекс-алгоритм состоит в последовательном повторении подобных операций до тех пор, пока не будет найдено оптимальное решение ЗЛП.

ЗЛП имеет множество решений, если при достижении оптимальной вершины в выражении функции будет отсутствовать какая-нибудь из свободных переменных.

Если на каком-то этапе окажется, что все коэффициенты отрицательны и увеличение свободной переменной не ограничено, (область открытая), то оптимального решения не существует .

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

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

Рассмотрим исходную задачу (4.15),(4.16). Для нее построим вспомогательную задачу: найти

(4.23)

для известного вектора с m дополнительными переменными

и условиями

(4.24)

Система уравнений (4.24) является канонической системой. Принимая за свободные переменные, а - за базисные, получаем базисное допустимое решение вспомогательной задачи:

Затем, применяя последовательно шаги симплекс-алгоритма находим оптимальное решение вспомогательной задачи. Если это решение таково, что ,то оно определяет допустимое базисное решение исходной задачи; если , то исходная задача не имеет допустимых решений.

Применение симплекс-метода для решения задач с условиями типа неравенство. Пусть ограничения задаются не уравнениями, а неравенствами. Их число обозначим через d. Неравенства могут быть легко сведены к уравнениям, если ввести в таком же количестве дополнительные положительные переменные. Для неравенства

получим

Для неравенства

получим

Тогда задача оптимизации может быть записана в следующей форме:

при

при условиях

Таким образом, получили ЗЛП с условиями в форме равенств, которая решается симплекс-методом.