§ 6. Задачи с линейными ограничениями и выпуклыми (вогнутыми) функциями цели

Рассмотрим теперь решение еще одного вида упрощенных задач, у которых нелинейной (выпуклой или вогнутой) является только функция цели.

Будем, например, искать решение задачи с линейными ограничениями вида

(2.28)

обращающее в максимум вогнутую функцию цели f (X) = f(x₁, ..., x_n).

Предположим, что функция f (X) имеет непрерывные первые частные производные в каждой точке множества допустимых решений. Выберем некоторое допустимое решение X₀ и определим градиент функции f (X). Напомним, что если = 0, то уже точка X₀ может являться решением задачи. Предположим, однако, что градиент отличен от нуля, т. е. выбранная точка X₀ заведомо не является решением задачи. Необходимо найти Такую последовательность точек X₁, X₂, ..., чтобы каждая следующая точка была ближе к оптимальному решению, т. е. последовательность точек, для которых f (X₁)>f(X₀), f(X₂)>f(X₁) и т. д.

Будем искать точку X₁, обеспечивающую лучшее приближение к оптимальному решению, чем точка X₀, следующим образом. Положим X₁ = X₀ + αd₀, где α - некоторое число, d₀ = - градиент функции f в точке X₀, т. е. потребуем, чтобы перемещение из точки X₀ в точку x₁ происходило по направлению градиента на расстояние, пропорциональное величине градиента. Если ищется максимум f (X), то следует брать α>0.

При переходе от X₀ к X₁, очевидно, имеются две возможности:

Случай 1. Существует такое ε, что X₁ = X₀ + αd₀ является допустимым решением при всех α, определяемых неравенством 0≤α≤ε.

Случай 2. Не существует α>0 такого, чтобы X₁ = X₀ + αd₀ было допустимым решением.

Рассмотрим сначала первый случай и покажем, что существует α>0, при котором X₁ = X₀ + αd₀ является допустимым решением и f (X₁)>f(X₀). По условию X₁ = X₀ + αd₀ - допустимое решение для всех 0≤α≤ε; однако это еще не значит, что для всех этих αf (X₁)>f(X₀). Согласно теореме Лагранжа можно написать [см. 16]:

где ξ = X₁ = X₀ + αθd₀, 0≤θ≤1.

Неравенство f (X₁)>f(X₀) выполняется, если ∇f (ξ) d₀>0, что справедливо в задаче на максимум по крайней мере для X₁ и некоторого δ>0, таких, что |X₁-X₀|<δ. Следовательно, если α удовлетворяет соотношению 0<α< min (ε, δ), то X₁ ≡ X₀ + αd₀ является допустимым решением и f (X₁)>f(X₀).

Ясно, что желательно получить возможно большее значение f (X₁), но так, чтобы X₁ оставалось допустимым решением. Поэтому найдем наибольшее α_max ≡ ε₀, для которого X₁ ≡ X₀ + ε₀d₀ является еще допустимым решением. Для этого подставим X₁ в ограничения задачи и условие x_j≥0:

(2.29)

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

Поэтому из (2.29) получаем два условия, которым должна удовлетворять максимальная величина α:

(2.30)

Очевидно, следует принять ε₀ = min (ρ, γ). Однако неправильно было бы сразу положить α = ε₀, поскольку ∇f (X) меняется при разных X₁ и может случиться, что при большом а, когда |X₁ - X₀|>δ, будет f (X₀ + αd₀)<f (X₀). Поэтому следует взять такое α, 0<α<ε₀0, которое максимизирует f (X₀ + αd₀).

Самый простой метод определения необходимого α состоит в делении интервала 0<α≤ε₀ на равные части по Δα точками α_k = kΔα и вычислении f (X₀ + α_kd₀) для каждого k. Из всех f (X₀ + α_kd₀) следует выбрать наибольшее, и α_k, дающее этот максимум, как раз и является искомым. В частности, для задачи линейного программирования, когда величина ∇f (X) не зависит от X, и можно положить α = ε₀, так как f (X₀ + αd₀) линейно возрастает по α. Таким образом, когда функция цели линейна, следует двигаться до границы области допустимых решений, и максимум достигается в экстремальной точке.

Вернемся теперь ко второму случаю, когда сразу не существует α>0, при котором X₁ = X₀ + αd₀ является допустимым решением, т. е. решение X₀ находится на границе множества допустимых решений. При этом некоторые из ограничений или условий неотрицательности x_j будут сразу нарушаться, если пытаться двигаться по направлению градиента. Определим, в каком направлении нужно двигаться, чтобы ограничения не нарушались, а значения функции цели f увеличивались. Отметим, что к случаю 2 можно прийти также после одного или нескольких изменений значений x_j, согласно процедуре случая 1.

Поскольку в случае 2 мы лишены возможности двигаться вдоль направления ∇f (X), выберем другое направление, задаваемое некоторым вектором r, |r| = 1, r ≡ (r₁, ..., r_n). Скорость изменения функции f (X) при движении из точки X₀ в направлении r определяется выражением

т. е. скалярным произведением векторов и r; величина есть косинус угла между и r.

Запишем изменение переменной X в виде X₁ = X₀ + αr, считая, что α>0. Поскольку X₁ должно быть допустимым решением, можно написать:

(2.31)

Так как точка X₀, по определению, находится на границе множества допустимых решений, т. е. (для некоторого i), переход в точку X₁ осуществляется таким образом, чтобы X₁ также находилась на границе этого множества, поэтому

(2.32)

Теперь для того чтобы определить направление возрастания f (X) без нарушения ограничений, необходимо решить следующую задачу:

(2.33)

найти максимум z = *r, т. е. найти такой вектор r, который образует наименьший угол с .

Можно использовать и более простые способы нахождения возможного r, например, потребовать выполнения условия

(2.34)

Предположим, что найден некоторый вектор r₀, удовлетворяющий задаче (2.33) или условию (2.34) с ограничениями (2.32) Далее необходимо определить ρ и γ в соответствии с (2.30) и найти ε₀, чтобы x₁ = x₀ + αr₀ было допустимым решением задачи (2.28). Процесс движения из точки x₁ в точку x₂ продолжается, если из точки x₁, можно найти направление, для которого ∇f(X₁)r₁>0. Когда некоторой точке окажется, что ∇f(X_k)r_k≤0 для любого r_k, которое не приводит к нарушению ограничений,процесс решения заканчивается.

Исписанную картину итерационного процесса можно проиллюстрировать геометрически на примере задачи с двумя переменными. Пусть надо найти максимум вогнутой функции f (X) на множестве М переменных (x₁, x₂). Линии уровня функции f (X) = const (c₁<c₂<c₃) на плоскости переменных (x₁, x₂) изображены на рис. 2.5.

Рис. 2.5

Пусть за исходную точку взята точка X₀. Градиент или d₀ является вектором, нормальным к прямой, касательной линии уровня f (X) = C₀ в точке X₀, Из этой точки можно двигаться как можно дальше, пока не достигнем границы области допустимых решений. Как указывалось выше, это можно делать не всегда, однако в данном примере функция f (X) возрастает с увеличением а вплоть До границы области. Поэтому можно сразу двигаться в точку X₁ = X₀ + αd₀, находящуюся на границе области допустимых решений.

Из точки X₁ уже нельзя двигаться в направлении градиента d₁, так как при этом мы выйдем из области допустимых решений. Поэтому ищем вектор r₁, решая задачу (2.33), вторая для точки X₁ имеет только одно ограничение, задаваемое уравнением прямой, на которой находится эта точка.

На рис. 2.5 легко видеть, что вектор r₁, составляющий меньший угол с d₁, направлен вдоль соответствующего ограничения. Двигаясь в этом направлении, мы приходим в точку X₂, где необходимо выбрать другой вектор r₂. Далее, двигаясь вдоль вектора r₂, приходим в точку X₃ = X₂ + αr₂, в которой f (X) достигает максимума. Процедура определения величины α, для которого решение X₃ является оптимальным, описана ранее.

Поясним сказанное выше численным примером. Возьмем уже рассматривавшуюся выше (см. § 6, гл. I и § 5, гл. II) задачу распределения ресурсов. Пренебрежем нелинейностью в ограничениях, сохранив нелинейность в функции цели. В результате имеем следующую задачу:

при ограничениях

Выбираем в области допустимых решений начальную точку x₀₁ = 1, x₀₂ = 1, для которой f₀ = 4,8. Вектор градиента в этой точке имеет компоненты

Движемся из точки (x₀₁, x₀₂) в направлении градиента:

где α₁ выбирается так, чтобы не нарушались ограничения:

В соответствии с (2.30) При таком движении мы прежде всего достигнем первого ограничения (проверка при значениях α<0,946 показывает, что двигаться можно вплоть до границы области допустимых решений). Итак, имеем x₁₁ = 1 + 1,8*0,946 = 2,703, x₁₂ = 1 + 2,8*0,946 = 3,649, f₁ = 14,290. Далее следует двигаться вдоль первого ограничения. Задача определения направления движения (2.33) в данном случае имеет вид:

при ограничениях

где r₁ и r₂ - компоненты вектора направления r. Решение этой задачи есть r₁ = 0,894, r₂ = -0,447. Таким образом, следует продолжать движение вдоль r, определяя α₂ = 1,975 согласно (2.30), а также из второго и третьего ограничений, в которые подставляются значения x₂₁ = 2,703 + 0,894α₂ и x₂₂ = 3,649 - 0,447α₂. для различных значений α₂ имеем:

Таким образом, мы видим, что максимум f достигается где-то в окрестности α₂ ≈ 1,5, причем само значение максимума очень слабо зависит от конкретных величин x₁ и x₂. Значение (α₂)_max, соответствующее этому максимуму, проще найти из условия ∇f*r = 0, или в нашем случае из выражения (2 - 0,2x₁)*0,894 - (3 - 0,2x₂)*0,447 = 0, где x₁ = 2,703 + 0,894α₂, x₂ = 3,649 - 0,447α₂.

Решая это уравнение относительно α₂, имеем (α₂) = 1,452, x₁ = 4,001, x₂ = 3,069, f_max = 14,666. На этом процесс решения заканчивается.

Итак, мы в общих чертах рассмотрели метод решения задачи максимизации вогнутой функции при линейных ограничениях. Решение подобной задачи минимизации выпуклой функции проводится аналогично, с той лишь разницей, что для минимизации функции цели приходится двигаться в сторону, противоположную градиенту, т. е. брать α<0.