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

Пример 4.

max Z = x₁²+x₂²

x₁x₂ £ 4

x₁ + x₂ ³ 5

x₁ £ 7

x₂ £ 6

x₁³ 0, x₂ ³ 0

Область допустимых решений состоит из двух отдельных частей: АВСD и KLMN (рис.4).

Если Z = 1, то x₁²+x₂² =1 - окружность с центром в точке (0;0) и радиусом, равным 1. Пусть Z = 4, тогда - окружность с центром в точке (0;0) и радиусом, равным 2. Увеличивая значение Z, мы видим, что максимальное значение функция достигает в точках С и М соответственно в частях ОДР АВСD и KLMN. В них имеем локальный максимум. Найдем координаты точек.

Найдем координаты точки С и вычислим в ней значение Z.

; С (; 6).

Найдем координаты точки М и вычислим в ней значение Z.

; М .

 

Рис. 4. Область допустимых решений состоит из двух отдельных частей: АВСD и KLMN. Глобальный максимум в точке М , max Z = .

Оптимальное решение для части ABCD – точка C(2/3;6), а для части KLMN оптимальное решение - точка М(7;4/7). Сравнив значения целевой функции в этих точках, можно найти глобальный максимум.

Сравнивая значения Z в точках С и М делаем вывод, что максимальное значение целевой функции достигается в точке М , max Z = . Это глобальный максимум.

Определение 1. Функция f(Х) достигает локального максимума в точке , если для всех точек , лежащих в малой окрестности точки , имеет место неравенство .

Определение 2. Функция f(Х) достигает глобального (абсолютного) максимума в точке , если для всех точек , принадлежащих области допустимых решений, справедливо неравенство .

Контрольные вопросы

1. Какие задачи относятся к задачам нелинейного программирования?

2. По каким признакам и как можно классифицировать задачи нелинейного программирования?

3. Как в общем виде формулируется задача нелинейного программирования?

4. Какие особенности области допустимых решений задач нелинейного программирования можно отметить?

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

6. Чем отличается локальный экстремум от глобального?

 

Экстремум функции[1]

Определение 1. Точка называется точкой максимума функции f(x), если в некоторой окрестности точки выполняется неравенство f(x) f() (см. рис. 5).

Определение 2. Точка называется точкой минимума функции f(x), если в некоторой окрестности точки выполняется неравенство f(x) f() (см. рис. 5).

Значения функции в точках и называются соответственно максимумом и минимумом функции. Максимум и минимум функции объединяются общим названием экстремума функции.

Для того, чтобы функция y=f(x) имела экстремум в точке , необходимо, чтобы ее производная в этой точке равнялась нулю f’() = 0 или не существовала.

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

Первое достаточное условие экстремума. Теорема. Если при переходе через точку производная дифференцируемой функции y=f(x) меняет свой знак с плюса на минус, то точка есть точка максимума функции y=f(x), а если с минуса на плюс, - то точка минимума.

Второе достаточное условие экстремума. Теорема. Если первая производная f ¢(x) дважды дифференцируемой функции равна нулю в некоторой точке , а вторая

Рис. 5. Экстремум функции

 

производная в этой точке f ²() положительна, то есть точка минимума функции f(x); если f ²(x) отрицательна, то - точка максимума.

Алгоритм исследования функции y=f(x) на экстремум.

1. Найти производную функции y¢=f’(x).

2. Найти критические точки функции, в которых производная f¢(x)=0 или не существует.

3. Исследовать знак производной слева и справа от каждой критической точки и сделать вывод о наличии экстремумов функции.

4. Найти экстремумы (экстремальные значения) функции.

Схема исследования на экстремум функции y=f(x) с помощью второго достаточного условия в целом аналогична схеме, приведенной выше (совпадают полностью пункты 1,2,4). Отличие в пункте 3, устанавливающем наличие экстремума: здесь необходимо найти вторую производную f ²(x) и определить ее знак в каждой критической точке.

Пример 5. Производитель реализует свою продукцию по цене p за единицу, а издержки при этом задаются кубической зависимостью (a < p, λ > 0). Найти оптимальный для производителя объем выпуска продукции и соответствующую ему прибыль.

Р е ш е н и е. Обозначим объем выпускаемой продукции x. Составим функцию прибыли где px – доход от реализуемой продукции.

1. Находим

2. Находим критические точки: откуда (вторую критическую точку не рассматриваем по смыслу задачи).

3. Находим и определяем знак второй производной при

(в данном случае при любом ), следовательно, при прибыль C(x) максимальна.

4. Находим максимум функции (т.е. максимальный размер прибыли)

.

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

Рассмотрим, например, функцию . Имеем . В критической точке x=0 вторая производная также обращается в нуль. Но x=0 – точка экстремума, а именно – минимума. Так что в отличие от первого второе достаточное условие является именно только достаточным, но не необходимым. Поэтому, если в критической точке , то рекомендуется перейти к первому достаточному условию экстремума.

Пример 6. Производитель реализует свою продукцию по цене 350 ден. ед. за единицу, а издержки при этом задаются кубической зависимостью . Найти оптимальный для производителя объем выпуска продукции и соответствующую ему прибыль.

Р е ш е н и е. Обозначим объем выпускаемой продукции x. Составим функцию прибыли где 350x – доход от реализуемой продукции.

1. Находим

2. Находим критические точки: откуда (вторую критическую точку не рассматриваем по смыслу задачи).

3. Находим и определяем знак второй производной при

(в данном случае при любом ), следовательно, при , т.е. х = 1,354007 прибыль C(x) максимальна.

4. Находим максимум функции (т.е. максимальный размер прибыли)

.

Таким образом при оптимальном объеме выпуска продукции равном 1,354007, максимальная прибыль будет равна 198, 59 ден. ед.

Характеристика задачи

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

Рассмотрим простейшую задачу экономической динамики.

Пусть y(t) – объем продукции некоторой отрасли, реализованной к моменту времени t. Будем полагать, что вся производимая отраслью продукция реализуется по некоторой фиксированной цене p, т.е. выполнено условие ненасыщаемости рынка. Тогда доход к моменту времени t составит Y(t)=py(t). Обозначим через I(t) величину инвестиций, направляемых на расширение производства. В модели естественного роста полагают, что скорость выпуска продукции (акселерация) пропорциональна величине инвестиций, т.е y¢(t)= l I(t) (1)

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

Полагая, что величина инвестиций I(t) составляет фиксированную часть дохода, получим

I(t)=mY(t)=mpy(t) (2),

где коэффициент пропорциональности m (так называемая норма инвестиций) – постоянная величина, 0<m<1.

Подставляя последнее выражение I(t)=mY(t)=mpy(t) в уравнение y¢(t)=lI(t), получим

y¢=ky, (3), где k=mpl.

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

y¢=mlp(y)y (4).

Так как все сомножители в правой части последнего уравнения положительны, то y¢>0, и это уравнение описывает возрастающую функцию y(t). При исследовании функции y(t) на выпуклость естественно используется понятие эластичности функции. Действительно, из равенства y¢=mlp(y)y следует, что

y²=mly¢ .

Эластичность спроса (относительно цены) определяется формулой . Тогда выражение для y можно записать в виде y²=mly¢p и условие равносильно равенству .

Таким образом, если спрос эластичен, то функция y(t) выпукла вниз; в случае, если спрос не эластичен, то функция y(t) выпукла вверх.

Алгоритм

У нас дано выражение кривой спроса p(y)=a+by, тогда уравнение (4) принимает вид y¢=mlp(y)y, где m-норма инвестиций, l- норма акселерации или

(5)

Для решения данного дифференциального уравнения необходимо левую часть уравнени (5) представить как сумму двух дробей.

(6)

В равенстве (6), приведя две дроби в правой части к общему знаменателю, получим

Чтобы правая и левая часть в уравнении (6) были равны необходимо, чтобы числители дробей были равны.

Ay + aB + Bby = 1

(A + Bb)*y + aB = 1 <=>

(7)

 

Уравнение (5) принимает вид

Умножим обе части уравнения на (-а)

Прологарифмируем обе части уравнения

(8)

 

, где С= (9)

(10).

 

Уравнение (10) – искомое уравнение объема реализованной продукции.

При известном количестве реализованной продукции в начальный момент времени, т.е. у(0), из уравнения (9) можно найти С.

Пример 7. Найти выражение для объема реализованной продукции y=y(t), если известно, что кривая спроса p(y) задается уравнением p(y)=2-y, норма акселерации l=2, норма инвестиций m=0,5, y(0)= 0,5.

Решение.

Уравнение y ¢=mlp(y)y в этом случае принимает вид

y’=(2-y)y

или

Выполняя почленное интегрирование, получим

Или

, где

Рис. 6. Логистическая кривая

Учитывая, что y(0)=0,5, получаем, что C=3. Выражая теперь y из , окончательно имеем . График данной функции схематично изображен на рис.6.