Методы одномерной оптимизации. Методы одномерной оптимизации на основе преобразования задач. Поисковые методы одномерной оптимизации, страница 14

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

 и т. д.

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

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

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

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

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

                                 (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)

.

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

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

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

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

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

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