Добро пожаловать на наш портал !

Методы компьютерного моделирования экономических процессов

Метод допустимых направлений

Метод допустимых направлений. Данный метод также называется методом возможных направлений или же по имени автора—методом Зойтендейка, см. [16]. Его основную идею будет удобно продемонстрировать на примере ЗНП с ограничениями в форме неравенств:

В указанном методе так же, как и в градиентных методах, находится последовательность точек х(0) х(1),..., х(q)..., таких, что f(х(q+1)) ≥ f(x(q)) *. При этом переход от точки x(q)) к точке х(q+1)) происходит по некоторому выбранному направлению s(q) с шаговым множителем λq:

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

По отношению к векторам, задающим направления перемещения, вводятся два фундаментальных понятия.

F Направление s называется допустимым (возможным) в точке x(q) D, если существует такое

λ > 0, что x(q+1) = x(q) + λs D.

F Направление s называется прогрессивным в точке x(q) D, если существует такое λ >0, что

f(x(q) + λs)> > f(x(q)) для задачи максимизации и f(x(q) + λs) < f(x(q)) для задачи минимизации.

На основе данных определений достаточно просто сформулировать критерий проверки оптимальности точки (так называемый критерий оптимальности в терминах допустимых и прогрессивных направлений):

F точка х* является оптимальным планом задачи (2.16), если в ней ни одно допустимое

направление не является прогрессивным.

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

1°. Точка х(q) лежит внутри области D, т. е. для всех i 1: m gi(х(q)) < 0 (см. рис. 2.4). Очевидно, что для внутренней точки любое направление будет допустимым (при выборе достаточно малого шага), поэтому естественным представляется движение в сторону «гарантированного» возрастания значения функции, а именно в направлении градиента. Значит, для внутренней точки х(q) целесообразно выбрать s(q) = f(х(q)).

Шаговый множитель λq выбирается так, чтобы, с одной стороны, новая точка х(q+1) принадлежала D, а с другой — значение целевой функции в ней f(х(q+1)) было как можно большим.

С этой целью сначала найдем промежуток [0, ] из условия для чего необходимо решить систему неравенств:

Зная промежуток [0, ], определяем значение шагового множителя λq из условия максимизации значения функции в направлении s(q):

Вновь найденная точка x(q+1) может находиться или внутри области D, или на ее границе. В первом случае (на рис. 2.4 ему соответствует точка (q+1) переходим к началу данного пункта и повторяем вышеописанные действия, а во втором (точка (q+1) на рис. 2.4) — действуем по рассматриваемой далее схеме.

2°. Точка x(q) находится на границе области (см. рис. 2.5). Это означает, что одно или несколько неравенств из системы ограничений задачи (2.16) выполняются как строгие равенства: gi(x(q)) = 0. Например, на рис. 2.5 и g1(x(q)) = 0 и g3(x(q)) = 0.

Ограничение, которое в текущей точке выполняется как равенство, называют активным. Множество номеров активных ограничений в точке x(q) будем обозначать как I(x(q)). В примере, изображенном на рис. 2.5, I(x(q)) = {1, 3}. Также из рисунка видно, что все допустимые направления, исходящие из точки x(q), должны образовывать тупые углы с векторами градиентов функций, задающих активные ограничения в данной точке. Последнее условие может быть выражено через задание ограничений на значения скалярных произведений вектора направления s на градиенты функции ограничений:

где Iл — множество номеров индексов линейных ограничений, Iн — множество номеров индексов нелинейных ограничений. Соответственно, I(x(q))◠Iл —номера линейных активных ограничений, а I(x(q))◠Iн — номера нелинейных активных ограничений. Отличие условий (2.20) от условий (2.21) заключается в том, что в случае линейного ограничения направление, образующее прямой угол с градиентом ограничивающей функции (т. е. их скалярное произведение равно нулю), будет заведомо допустимым, а в случае нелинейного ограничения — возможно, нет.

Все возможные направления в точке x(q) образуют так называемый конус допустимых направлений, и из них для следующего перехода, очевидно, нужно выбрать прогрессивное. Если такового не существует, то согласно сформулированному выше критерию точка x(q) является оптимальной! Для ускорения максимизации функции желательно, чтобы угол между искомым допустимым прогрессивным направлением s(q) и градиентом целевой функции ∇f(x(q)) был как можно меньше или, что то же самое, как можно большей была бы проекция s на ∇f(x(q)) (при условиях нормировки вектора s(q)). Иными словами, желательно, чтобы неравенство s(q)f(x(q))+σ≥0 выполнялось при минимально возможном σ ∈ R. Тогда задачу отыскания наилучшего допустимого прогрессивного направления s(q) можно свести к задаче минимизации параметра σ:

при условиях

где s12 +s22 +...+sn2, ≤ l —условие нормировки, обеспечивающее ограниченность решения;

τ — некоторое достаточно малое число, характеризующее «строгость» выполнения неравенств.

В отличие от всех остальных, последнее условие в системе (2.23) является нелинейным, что существенно усложняет процесс решения задачи (2.22)-(2.23). Поэтому на практике для определения направления s(q) (возможно, не лучшего) переходят от данной задачи к задаче линейного программирования путем замены указанных выше условий нормировки на ограничения вида –l ≤ sj, ≤ 1:

После того как прогрессивное направление s(q) найдено, шаговый множитель определяется по методу, описанному в п. 1°.

В заключение отметим, что при практических расчетах алгоритм завершается при достижении такой точки х*, в которой |∇f(x*)|<ε, где ε —достаточно малое число.

Представляется полезным обратить внимание читателя и на то, что применяемый для решения задач линейного программирования симплекс-метод может быть рассмотрен как частный случай метода допустимых направлений. В частности, этап выбора столбца, вводимого в очередной базис, соответствует определению допустимого прогрессивного направления. Более подробно о такой концепции симплекс-метода можно прочесть в [1].