![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
4.9.1. Харатеристика метода
Данный метод является основополагающим среди универсальных методов. Он разработан Данцигом в 1947 году. В одной из первых задач, решенных этим методом, допустимое множество представляло собой симплекс – выпуклый многогранник, у которого число вершин на единицу больше размерности пространства. Отсюда и произошло название метода. В некоторых отечественных монографиях (авторы Гольштейн Е.Г., Юдин Д.Б. и др.) его называют методом последовательного улучшения плана.
Симплекс-метод реализует направленный перебор допустимых базисных решений в виде итеративного процесса. На каждой итерации осуществляется переход по ребру допустимого множества от одной вершины (крайней точки) к другой, смежной исходной, в которой значение критерия лучше или, в редких случаях, не хуже, чем в исходной. Поскольку число крайних точек конечно, а целевая функция линейна, то такой процесс сходится за конечное число шагов к глобальному оптимуму (для разрешимой задачи).
В результате симплекс метод позволяет отыскать оптимальное решение, просматривая значительно меньше вершин по сравнению с их общим числом. Строгих оценок достаточного числа итераций для достижения оптимального решения нет. Однако экспериментально установлено, что реальное число итераций находится в пределах m ¸3 m, а наиболее вероятно (1,5¸2) m. Так, для вышерассмотренного примера вместо десятков тысяч вершин метод “пройдет” не более 30.
В симплекс-методе можно выделить три основные компоненты:
1) Способ построения начального базисного решения.
2) Процедуру перехода от одного базисного решения к другому.
3) Признак оптимальности.
Неразрешимость задачи определяется по ходу работы алгоритма.
4.9.2. Переход от одного базисного решения к другому
Здесь нам понадобятся некоторые понятия линейной алгебры..
Векторы А 1, А 2, …, АS являются линейно-независимыми, если равенство k 1 A 1 +k 2 A 2 +…+kSAS =0 выполняется только при k 1 =k 2 =…=kS= 0. Признаком линейной независимости векторов является ненулевое значение определителя, составленного из этих векторов, так как однородная система имеет единственное (нулевое) решение только при таком определителе.
Если есть система линейно-независимых векторов, то любой другой вектор может быть выражен в виде их линейной комбинации и притом единственным образом:
Ap=a 1 A 1 +a 2 A 2 +…+aSAS, pÏ[1, S].
В канонической форме условия записываются в виде
(4.4)
Пусть система (4.4) имеет базисное решение:
(4.5)
Тогда из (4.4) следует
(4.6)
Так как система (4.6) совместна, то ее определитель не равен нулю и, значит, векторы, входящие в (4.6), являются линейно-независимыми. Для их обозначения введем следующее понятие: система m линейно-независимых векторов, соответствующих базисным переменным, называется базисом. Таким образом, каждой экстремальной точке соответствует своё базисное решение и свой базис.
Теперь, имея исходные базисное решение (4.5) и базис , построим новое базисное решение. Как следует из геометрических представлений, смежные вершины отличаются по составу базисных переменных только одной. Поэтому новое решение можно получить вводом в исходное небазисной переменной с одновременным переводом одной базисной переменной в небазисные.
Пусть вводимой будет переменная с индексом rÏ[1,m], принимающая в новом решении некоторое положительное значение
В новом решении, как в любом допустимом, условия (4.4) также должны выполняться, поэтому имеем:
(4.7)
Задача состоит в том, чтобы определить X (1) по X( 0). С этой целью сделаем несложные преобразования. Выразим вектор Ar через исходный базис:
Ar=A 1 a 1 r +A 2 a 2 r +…+Amamr .(4.8)
Так как известен базис, то известны (или находятся решением этой ситстемы) коэффициенты разложения air. Умножим левую и правую части равенства (4.8) на q:
qAr=qA 1 a 1 r +qA 2 a 2 r +…+qAmamr. (4.9)
Вычитая (4.9) из (4.6), получим:
или окончательно:
(4.10)
Сравнивая равенства (4.7) и (4.10), видим, что правые части равны, а левые содержат одну и ту же ситстему векторов. Поэтому коэффициенты при одноименных векторах должны совпадать. Приравнивая их, получаем искомые соотношения:
(4.11)
Однако решение (4.11) может быть недопустимым, если не оговорить возможные значения q. Предположим, что среди коэффициентов air есть положительные. Тогда с увеличением значения q соответствующие переменные могут стать отрицательными. Поэтому для допустимости решения X (1) необходимо, чтобы q было ограничено сверху:
(4.12)
С учетом (4.12) решение (4.11) всегда будет допустимым, но число ненулевых переменных в нем может превышать m, так как добавлена xr , а значит, оно может быть небазисным. Если же в качестве значения q выбрать q0, то одна из переменных станет равной нулю, а решение (4.11) - базисным.
Пусть минимум в (4.12) достигается на переменной xk. Тогда базисные переменные в новом опорном решении будут вычисляться по формулам:
(4.13)
Этому решению соответствует новый базис {Ai}(1)={A 1 ,…,Ak- 1 ,Ar, Ak+ 1 ,…,Am}. Таким образом, переход к новому базисному решению произошел путем замены переменной Xk на Xr, соответсвенно в базисе - Ak на Ar.
Рассмотрим возможные ситуации при переходе от одного решения к другому. Как было показано выше, при существовании положительных коэффициентов air достигается новое базисное решение (смежная вершина), что иллюстрируется рис. 4.6-а. Если же все air неположительны, величина q, а это значениевводимой переменной, не ограничена сверху. Следовательно, введение такой переменной не приведет к получению базисного решения (достижению новой вершины). Это признак того, что соответствующее ребро допустимого множества, а значит, и само множество оказываются неогранниченными (рис. 4.6-б).
![]() |
При вычислении q0 минимум может достигаться более чем на одном индексе. При этом обнуляется более одной переменной из входящих в исходное решение. Следовательно, в новом решении будут базисные переменные с нулевым значением, что означает попадание в вырожденное базисное решение.
Если исходное решение вырожденное и нулевой переменной соответствует коэффициет akr >0, то согласно (4.12) q0 =0 и значения переменных не изменяются. Однако состав базиса и базисных переменных изменится - произойдет замена на
При высокой степени вырожденности теоретически возможно зацикливание, то есть возврат к старому базису, но на практике такие случаи не встречались.
Дата публикования: 2015-01-23; Прочитано: 244 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!