Математические методы исследования операций в экономике (стр. 18 из 37)

Следовательно, для любой точки х, не равной х*, справедливо неравенствоf(x)-f(x)≤ 0 <=> f(x)≤ f(x*), т.е. х* — точка глобального максимума. -

Поскольку выпуклые функции обладают столь «полезными» оптимизационными качествами, они занимают исключительно важное место в теории исследования операций. Соответствующий раздел получил название выпуклого программирования, а общая задача выпуклого программирования формулируется как проблема поиска максимума вогнутой (минимума выпуклой) функции на выпуклом множестве.

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

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

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

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

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

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

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

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

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

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

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

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

1°. Точках^(q)лежит внутри областиD, т. е. для всехi Î 1: mg_i(х^(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) выполняются как строгие равенства:g_i(x^(q)) = 0. Например, на рис. 2.5и g₁(x^(q)) = 0 иg₃(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) можно свести к задаче минимизации параметра σ:

при условиях

гдеs₁² +s₂² +...+s_n², ≤ l —условие нормировки, обеспечивающее ограниченность решения;

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

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

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

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

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

2.1.6. Пример решения ЗНП методом допустимых направлений. Рассмотрим процесс применения метода допустимых направлений на конкретном примере. Пусть дана ЗНП:

Итерация 1. В качестве начального приближения возьмем точку х⁽¹⁾ = (0,0). Нетрудно заметить, что она удовлетворяетсистеме неравенств (2.27), т. е. х⁽¹⁾∈D. Для х⁽¹⁾ все неравенства выполняются как строгие, т. е. множество индексов активных ограничений I(х⁽¹⁾)=∅. Следовательно, в х⁽¹⁾ любое направление является допустимым, и нам остается определить, с каким шагом λ₁ можно двигаться вдоль градиента целевой функции s⁽¹⁾ =∇f(x⁽¹⁾)=(1, 1). Система неравенств типа (2.18), из решения которых определяется интервал допустимых значений для λ, для данной задачи примет вид: