korobov

221

Для построения контура допустимой области следует приравнять нулю функции gi(x1;x2) (6.14) и построить соответствующие нулевые линии уровня этих функций. Нулевые линии уровня g2(x1;x2) и g2(x1;x2) являются прямыми, способ построения их элементарен и поэтому не требует пояснений.

Нулевая линия уровня g1(x1;x2) = 0 — кривая. Для построения ее достаточно вычислить координаты трех-четырех точек этой кривой и провести с помощью лекала эту линию (рис. 6.6). В произвольных точках этих линий следует построить соответствующие градиенты и после этого заштриховать допустимую область, которая вполне определится (см. рис. 6.6).

Далее, задаваясь произвольным значением линейной целевой функции (6.11), например, равным 100, строим соответствующую прямую уровня (см. рис. 6.6). Затем по градиенту f определяем направление возрастания этой функции и строим допустимую линию уровня, соответствующую максимуму функции (6.11), которая проходит через точку М пересечения граничных линий g2(x1;x2)=0; g1(x1;x2)=0. Эта линия уровня не рассчитывается, а строится параллельным переносом линии уровня 4x1 + 5x2=100 в направлении вектора f, так как линии уровня всякой линейной функции параллельны. Координаты точки М, которая является пересечением кривой линии g1(x1;x2)=0. с прямой g2(x1;x2)=0, являются оптимальным планом задачи.

Для вычисления координат оптимальной точки М следует решит нелинейную систему уравнений:

222

обеспечения максимальной прибыли необходимо производить 10 единиц продукции вида PI и 23 единицы продукции вида Р2 При этом максимальная прибыль составит:

Вэтом случае чистая прибыль на единицу продукции уменьшается с увеличением

еевыпуска. Положим, что такой случай вызван, например, увеличением дополнительных

Построение ϕ в произвольной точке кривой ϕ (x1, x2) =80 показывает, что целевая функция (6.16) в допустимой области монотонно возрастает. Из рисунка ясно видно, что допустимая линия уровня, соответствующая максимуму этой функции, должна соприкасаться с граничной линией g1(x1;x2)=0 в некоторой точке N, в которой градиентыϕ (N) и g1(N) имеют одинаковое направление. Следовательно, координаты точки N должны удовлетворять нелинейной системе уравнений (6.10), которая для данного

x1=12,8; x2=17,9

является оптимальным планом выпуска продукции P1 и Р2 с нелинейной целевой функцией (6.16), при этом максимальная прибыль составляет:

Эта функция отличается от функции (6.16) только тем, что прибыль на единицу продукции уменьшается с увеличением количества ее быстрее, чем в предыдущем случае. Вычислим градиент этой функции

Решением этой системы является внутренняя точка D допустимой области (см. рис. 6.6) с координатами x1=16; x2=10. Эта точка и будет оптимальным планом выпуска продукции видов P1 и Р2, при этом

maxψ(x1, x2) = ψ(16,10) = 57 денежных единиц.

На этом примере мы рассмотрели все возможные случаи, которые могут встретиться при решении задачи графическим способом. Кроме того, этот пример наглядно показывает отличительные черты нелинейных задач по сравнению с линейными. В

223

линейном программировании допустимая область всегда является выпуклым многоугольником. Область называется выпуклой, если любой отрезок, соединяющий две точки области, целиком принадлежит этой области. В нелинейном программировании допустимая область может быть и не выпуклой. На рис. 6.6 криволинейный заштрихованный пятиугольник не выпуклый. Например, любой отрезок, соединяющий две точки граничной кривой g1(x1, x2)=0, не будет принадлежать области (кроме его концов). В линейном программировании экстремум целевой функции может достигаться только на границе допустимой области. В нелинейном же программировании он может достигаться и во внутренних точках области (см. рис. 6.6, точка D).

Наконец, в линейном программировании единственный экстремум целевой функции достигается только в угловой точке области. В нелинейном программировании он может быть в любой граничной точке как угловой, так и не угловой (см. рис. 6.6, точки

Ми N ) .

6.2.Понятие о классических методах оптимизации

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

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

Классические методы оптимизации применяются преимущественно по отношению к гладким функциям.

Вклассической теории максимума и минимума следует ясно понимать различие между абсолютным и локальным максимумом и минимумом, часто вместо термина «абсолютный» используется термин «глобальный».

Функцию от п переменных х1, x2, ..., хп мы будем обозначать кратко через f(X), где X=(х1, x2, ..., хп) вектор или точка n-мерного пространства.

Говорят, что функция f(X) достигает локального максимума в точке Х0, если

f(X)≤.f(X0) для любой точки X из сколь угодно малой окрестности точки Х0. Аналогично определяется локальный минимум функции f(X) в точке Х0. В окрестности этой точки должно быть f(X)≥f(X0 ).

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

Для объединения понятий максимума и минимума употребляется слово экстремум. Классическая теория экстремума не указывает на конкретные способы отыскания

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

Если локальный экстремум достигается в некоторой внутренней точке Х0 области, то в этой точке градиент функции равен нулю f(X0) = 0. Обратное утверждение не всегда

224

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

При решении экстремальных задач нас, конечно, интересует нахождение абсолютного экстремума.

Экстремальные задачи при отсутствии ограничений возникают в тех случаях, когда заранее известно, что абсолютный экстремум функции достигается внутри области или же когда функция задана на открытом (не замкнутом) множестве точек.

Процесс решения экстремальных задач при отсутствии ограничений заключается в

Далее следует найти все стационарные точки и вычислить значения функции f(X) в этих стационарных точках. Оптимальным решением задачи является та стационарная точка, в которой функция имеет наибольшее значение в случае задачи максимизации и наименьшее значение при минимизации функции.

Рассмотрим экстремальные задачи при наличии ограничений в виде уравнений. В общем задача такого типа формулируется следующим образом.

вообще говоря, нелинейной. Экстремум функции (6.23) при условиях (6.24) называется относительным экстремумом. Как уже говорилось выше, все функции f(X), gi(X) от X=(x1,

x2, . . ., хп) считаются гладкими.

Если точка Х0 является некоторой точкой локального экстремума функции (6.23) и если в этой точке градиенты g1(X0), g2(X0),…, gm(X0) линейно независимы, то в этой

где коэффициенты λ1,λ2,…, λm – действительные числа.

Таким образом, всякая точка локального минимума функции (6.23) должна удовлетворять системе, состоящей из п уравнений вида:

и m уравнений (6.24), представляющих условия задачи. Итак, мы имеем систему п + m уравнений (6.24) — (6.26) с п+m неизвестными x1, x2, . . ., хп, λ1,λ2,…, λm. Условия (6.24) — (6.26) являются только необходимыми, но недостаточными условиями локального

225

экстремума функции (6.23) при условиях (6.24). Это значит, что могут существовать точки, которые являются решениями системы (6.24) — (6.26), но в них функция (6.23) не будет иметь относительного локального экстремума. Поэтому для определения абсолютного экстремума целевой функции необходимо найти все решения системы (6.24)

— (6.26), затем подсчитать значения функции (6.23) для каждого из этих решений и выбрать среди них то, которое дает наибольшее (наименьшее) значение. Числа λi, которые не обязательно находить, называются множителями Лагранжа, а описанный метод нахождения относительного экстремума получил название метода множителей

Лагранжа.

Как в случае нахождения абсолютного экстремума функции при отсутствии ограничений, так и в случае нахождения абсолютного относительного экстремума, необходимо находить все решения в общем случае нелинейных систем уравнений.

К сожалению, не существует вычислительного метода для получения всех решений любых нелинейных систем, поэтому практическое применение классических методов оптимизации оказывается полезным лишь в случае, когда система имеет единственное решение. Это условие выполняется при минимизации выпуклых функций и максимизации вогнутых функций. Прежде чем дать определение выпуклой и вогнутой функции, уясним понятие выпуклого множества точек X=(x1, x2, . . ., хп) в n-мерном эвклидовом1 пространстве.

Всякая точка Х отрезка, соединяющего точки Х1, Х2, выражается через эти точки следующим образом:

Каждой точке отрезка соответствует определенное значение λ, заключенное между нулем и единицей. Выражение (6.27) называется выпуклой комбинацией точек

Х1, Х2.

Множество точек называется выпуклым, если оно содержит любую выпуклую комбинацию любых двух точек Х1 и Х2 из этого множества. Таким образом, выпуклое множество содержит отрезок, соединяющий любые две точки из этого множества.

Определение выпуклой и вогнутой функции имеет смысл только тогда, когда она задана на выпуклом множестве.

Функция f(X), заданная на выпуклом множестве, называется выпуклой, если для любых двух точек Х1 и Х2 этого множества и любого λ, заключенного между нулем и единицей (0≤λ≤1),значения функции от выпуклой комбинации Х = (1-λ)X1+λX2 не превосходит выпуклую комбинацию значений функции в точках X1 и Х2 при том же значении λ. Сказанное выражается в виде следующего неравенства:

Аналогичным образом определяется вогнутая функция. Функция f(X), заданная на выпуклом множестве, называется вогнутой, если для любых двух точек Х1 и Х2 этого множества и любого λ 0≤λ≤1

Если умножить обе части неравенства (6.28) на — 1, то оно превратится в неравенство вида (6.29). Из этого следует, что если f(X) — выпуклая функция, то — f(X) — вогнутая, и наоборот.

Если неравенства (6.28) или (6.29) выполняются на всем выпуклом множестве как строгие неравенства со знаками < или >, то функция называется строго выпуклой или

строго вогнутой.

226

является выпуклой (и вогнутой) на всем эвклидовом пространстве однако линейная функция не является ни строго выпуклой, ни строго вогнутой. Это значит, что условия (6.28) и (6.29) выполняются для линейной функции только со знаками равенства.

Сумма выпуклых (вогнутых) функций есть выпуклая (вогнутая) функция.

Существуют дифференциальные признаки выпуклости и вогнутости гладких функций. Эти признаки являются простыми только для функций одной и двух переменных.

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

f"(x)≤0,

Выпуклые и вогнутые функции представляют собой интерес в нелинейном программировании вследствие следующих свойств этих функций.

Любой локальный минимум выпуклой функции является ее абсолютным минимумом. Абсолютный минимум строго выпуклой функции достигается в единственной

точке выпуклого множества, на котором она задана.

Точка минимума выпуклой функции f(X) является одновременно точкой максимума вогнутой функции - f(X). Поэтому все, что сказано в отношении к минимуму выпуклой функции, справедливо по отношению к максимуму вогнутой функции.

Ценой увеличения расчетов можно oбoбщить метод множителей Лагранжа на случай, когда переменные ограничены. Такой случай рассмотрим на конкретном примере.

227

Пусть однородная лесопродукция может производиться на предприятиях П1, П2, ..., Пп. Прибыль, получаемая j-м предприятием от реализации произведенной продукции в количестве хj единиц, представляется в виде следующей нелинейной функции

f j (x j ) = (a j − k j x j )x j ,

где aj>0, kj>0 — постоянные коэффициенты.

Известны также производственные мощности Mj предприятий Пj.

Требуется распределить заказ по производству однородной лесопродукции в количестве N единиц между предприятиями так, чтобы получить наибольшую прибыль от ее реализации.

Математическая модель этой задачи будет следующей. Требуется найти абсолютный максимум целевой функции

[(a j − k j xj )xj ]''= −2k j < 0.

Поэтому функция (6.32) является строго вогнутой функцией, как сумма строго вогнутых функций, во всем n-мерном пространcтве. Эта функция имеет единственный максимум на любом выпуклом множестве точек Х= (x1, x2, ..., хп), в частности на выпуклом множестве, определяемом линейными ограничениями (6.33).

На первом этапе решим задачу (6.32) — (6.33) при отсутствии ограничений 0≤xj≤Mj. Точка максимума f(X) должна определиться по методу множителей Лагранжа, как результат решения системы уравнений

229

В качестве переменных x1, x2, x3, приняты искомые величины объема производства продукции каждого вида в тысячах единиц. Функция, отражающая суммарную прибыль от реализации продукции всех видов, имеет вид :

Фонд ресурса, необходимого для производства продукции составляет 4 тысячи единиц. Для выпуска единицы продукции первого и третьего вида требуется по одной единице ресурса, для выпуска единицы продукции второго вида - две единицы ресурса:

(6.38), равному 7,17. В то же время, следует указать на то, что точное оптимальное решение имеет вид х1=0,875, х2=0,625, х3=1,875 со значением (6.38) равным 7,25. Как видно, решение, полученное методами сепарабельного программирования, находится достаточно близко от точного решения.

230

Рассмотрим другой пример. В деревообрабатывающем производстве лесопромышленного предприятия планируется выпуск двух видов продукции. Искомые объемы производства - х1 и х2 в тысячах единиц. Себестоимость обеих видов продукции на единицу выпуска отражается функцией

x2 ≥ 150.

Это означает, что используются два вида ресурсов, и объем выпуска продукции первого вида ограничен сверху, а второго вида - снизу.

В задаче требуется найти объемы производства продукции обоих видов при условии минимальной суммарной себестоимости.

Таким образом, необходимо минимизировать целевую функцию (6.43) при условиях (6.44)

Пусть сетка точек для х1 и х2 имеет вид (0; 50; 125; 170; 200).

С целью линеаризации функцию (6.43) удобно представить в виде суммы двух функций одного аргумента

где

f1 (x1 ) = 0,05x1 − 0,00005x12 ;

f2 (x2 ) = 0,04x2 − 0,00005x22 .

Расчет коэффициентов Fk приведен в табл.6.4

Табл.6.4

где