Общая характеристика симплекс-метода. Пример итерационных вычислений, используемых при решении большинства оптимизационных задач. Решение различных задач симплекс-методом. Переход к итерациям. Метод полного исключения. Табличный симплекс-метод.
Аннотация к работе
В вычислительной схеме симплекс-метода реализуется упорядоченный процесс, при котором, начиная с некоторой исходной допустимой угловой точки (обычно начало координат), осуществляются последовательные переходы от одной допустимой экстремальной точки к другой до тех пор, пока не будет найдена точка, соответствующая оптимальному решению.Общая идея симплексного метода (метода последовательного улучшения плана) для решения ЗЛП (задачи линейного программирования) состоит Говорят, что ограничение ЗЛП имеет предпочтительный вид, если при неотрицательной правой части левая часть ограничений содержит переменную, входящую с коэффициентом, равным единице, а в остальные ограничения равенства - с коэффициентом, равным нулю. Однако теперь система ограничений не имеет предпочтительного вида, так как дополнительные переменные входят в левую часть (при ) с коэффициентами, равными-1. В целевую функцию переменные , вводят с коэффициентом М в случае решения задачи на минимум и с коэффициентом-М для задачи на максимум, где М - большое положительное число. Для того чтобы решить задачу с ограничениями, не имеющими предпочтительного вида, вводят искусственный базис и решают расширенную М-задачу, которая имеет начальный опорный планБазис {A1,.,Am}образует m-мерное пространство, а потому каждый из векторов Am 1,.,Am n единственным образом выражается через этот базис. Такой переход от одного базиса к другому позволяет находить решения почти всех задач ЛП. 3) вводят в базис наиболее "выгодную" переменную с максимальной положительной симплексом-разностью; ее значение xrmax определяют из соотношения для всех xir > 0, 4) выводят из базисного решения переменную xj, соответствующую а из базиса - вектор Итак переменная х2 вводится в базис со значением x2*= 300, переменная x4 выводится из базисного решения, а вектор Представим каждый из векторов A1, A4 ,не вошедших в базис, в виде линейной комбинации A2,A3,A5 .Так как вектор A4 был выведен из базиса, рассмотрим только векторСимплекс-метод, известный также в нашей литературе под названием метода последовательного улучшения плана, впервые разработал Г.Данциг в 1947 г. Этот метод позволяет переходить от одного допустимого базисного решения к другому, причем так, что значения целевой функции непрерывно возрастают. Симплекс-метод прост как для математического интуитивного понимания, так и для реализации, и преподается ныне в базовых вузовских курсах оптимальных задач. Симплекс-метод был прост и понятен, но оказался экспоненциальным - для разных эвристик выбора следующей вершины обхода исследователи сумели построить набор задач, для решения которых симплекс-методу было необходимо экспоненциально большое число итераций. Хачиян (везло нашим соотечественникам на фундаментальные открытия в этой области) построил алгоритм, который решает задачу линейного программирования за полиномиальное число шагов - так называемый метод эллипсоидов Хачияна.