Меню
Главная
Авторизация/Регистрация
 
Главная arrow Экономика arrow Исследование операций в экономике

Модели нелинейного программирования

Глава 9. Классические методы оптимизации

Глава 10. Модели выпуклого программирования

Глава 11. Модели динамического программирования

Классические методы оптимизации

Классические методы определения экстремумов

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

Можно выделить класс нелинейных задач, которые относятся к классическим методам оптимизации. Допустим, что среди ограничений (0.1) нет неравенств, не обязательны условия неотрицательности, переменные нс являются дискретными, т<п, а функции φ,(Χ) и f(X) непрерывны и имеют частные производные по крайней мере второго порядка. В этом случае задачу оптимизации можно сформулировать так: найти переменные х{, х2, ..., хП, удовлетворяющие системе уравнений

(9.1)

и обращающие в максимум (минимум) целевую функцию

(9.2)

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

Примером типичной и простой нелинейной задачи является следующая: данное предприятие для производства какого-то продукта расходует два средства в количестве x↑ и х2 соответственно. Это факторы производства, например машины и труд, два различных вида сырья и т.п., а величины ж, и х2 – затраты факторов производства. Факторы производства впредь будем считать взаимозаменяемыми. Если это "труд" и "машины", то можно применять такие методы производства, при которых величина затрат машин в сопоставлении с величиной затрат труда оказывается больше или меньше (производство более или менее трудоемкое). В сельском хозяйстве взаимозаменяемыми факторами могут быть посевные площади или минеральные удобрения (экстенсивный или интенсивный метод производства).

Объем производства (выраженный в натуральных или стоимостных единицах) является функцией затрат производства г = f(xvx2). Эта зависимость называется производственной функцией. Издержки зависят от расхода обоих факторов (ж, и х2) и от цен этих факторов (с, и с,). Совокупные издержки выражаются формулойТребуется при данных совокупных издержках определить такое количество факторов производства, которое максимизирует объем продукции z.

Математическая модель этой задачи имеет вид: определить такие переменные х{ и хТ удовлетворяющие условиям

(9.3)

при которых функция

(9.4)

достигает максимума.

Как правило, функция (9.4) может иметь произвольный нелинейный вид.

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

Будем полагать, что функция дважды дифференцируема в точке, J и в некоторой ее окрестности. Если для всех точек X этой окрестности или , то говорят, что функцияимеет экстремум в X' (соответственно максимум или минимум).

Точка, в которой все частные производные функции равны нулю, называется стационарной точкой.

Необходимое условие экстремума. Если в точке функция z = f(x) имеет экстремум, то частные производные функции в этой точке равны нулю:

Следовательно, точки экстремума функции z = f(X) удовлетворяют системе уравнений:

(9.5)

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

Достаточные условия экстремума:

а) в стационарной точке Х° функция z = f(X)имеет

максимум, если, и минимум, если,

при любых Δ.Γ и AXj Xв э́тих случаях Х° = X'), не оораща- ющихся в нуль одновременно;

  • б) если i/2/[X°j может принимать в зависимости от Ах. и Ах, и положительные, и отрицательные значения, то в точке экстремума нет;
  • в) если (12/(А́'° I может обращаться в нуль не только при нулевых приращениях Axj и Ах , то вопрос об экстремуме остается открытым.

Для функции двух переменных z = /(хх,хЛ достаточные условия еще не очень сложны. Существуют четыре частные производные второго порядка;

. Из них две смешанные производные и ”2 если непрерывны, то равны.

Найдем значения частных производных второго порядка в стационарной точке:

(можно убедиться, что ανι =а21). Обозначим через Δ определитель, составленный из й.. для i,j =1,2:

Тогда достаточные условия экстремума функции двух переменных имеют вид:

  • а) если А > 0 и "„ <0 ( а.п < 0 ), то в точке Х° функция имеет максимум: если Δ>0 и аи >0 (а22 >0 ), то в точке Х° – минимум (в этих случаях Х° = Х');
  • б) если А <0, то экстремума нет;
  • в) если А = 0, то вопрос об экстремуме остается открытым.

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

9.1. Исследовать на экстремум функцию

Решение. Находим частные производные:

(9.6)

Приравниваем частные производные нулю:

(9.7)

Решаем систему уравнений (9.7). Вычитая из первого уравнения второе, получим, поэтому = х2, и из первого уравнения найдем>, откуда х. = О или

_Имеем три стационарные точки X1 = (О; 0); X2 = (l; l);

Найдем вторые частные производные, используя (9.6):

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

В точке

Вопрос об экстремуме остается открытым (такая точка называется седловой).

В точкеа также и в точке:

Функция в этих точках имеет минимум, так как Δ > 0 и а >0• Zmin =-21. ►

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

Говорят, что функция z = /(X) имеет в точке Х° заданной области D глобальный максимум (наибольшее значение) или глобальный минимум (наименьшее значение), если неравенствоI или соответственно выполняется для люоой точки леи.

Если область D замкнута и ограничена, то дифференцируемая функция 2 = f(x) достигает в этой области своих наибольшего и наименьшего значений или в стационарной точке, или в граничной точке области (теорема Вейерштрасса)2.

Следовательно, чтобы найти наибольшее (наименьшее) значение функции 2 = f(x) в области D, нужно:

  • 1) найти все стационарные точки внутри области D и вычислить значения функции в них;
  • 2) исследовать функцию на экстремум на границе области D;
  • 3) сравнить значения функции, полученные в π. 1 и 2: наибольшее (наименьшее) из этих чисел и будет наибольшим (наименьшим) значением функции во всей области.

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

Условный экстремум. Пусть необходимо найти экстремум функции 2 = /(х,,х2, ..., хп) при условии, что переменные X,, х2,..., хп удовлетворяют уравнениям

(9.8)

Предполагается, что функции ∕ и φ; имеют непрерывные частные производные по всем переменным. Уравнения (9.8) называют уравнениями связи.

Говорят, что в точке, удовлетворяющей уравнениям связи (9.8), функцияимеет ус

ловный максимум (минимум), если неравенство

имеет место для всех точек X, координаты которы́х удовлетворяют уравнениям связи.

Легко заметить, что задача определения условного экстремума совпадает с задачей нелинейного программирования (9.1), (9.2).

Один из способов определения условного экстремума применяется в том случае, если из уравнений связи (9.8) т переменных, напримерможно выразить через оставшиеся п-т переменных:

(9.9)

Подставив полученные выражения для xi в функцию z, получим

или

(9.10)

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

9.2. Решить задачу (9.3), (9.4), предположив, что производственная функция

Решение. Необходимо найти переменные хх и х.г, удовлетворяющие уравнению

(9.11)

(уравнение связи), условию неотрицательности х,>0 и .г, > 0 и обращающие в максимум функцию

(9.12)

Рис. 9.1

Ограничение (9.11) вместе с условиями неотрицательности определяют на плоскости Οχχχ2 отрезок АВ, образующий замкнутую ограниченную область (рис. 9.1).

Согласно теореме Вейерштрасса максимум функции может достигаться либо внутри этого отрезка, либо в граничных точках: А (4; 0) или В (0; 2).

Следовательно, необходимо найти условный экстремум функции (9.12), если уравнение связи имеет вид (9.11).

Из уравнения связи найдем, например, х, и подставим в (9.12):

Упростив это выражение, получим

(9.13)

При этом. Найдем глобальный экстремум

функции (9.13) на отрезке [0; 2]. Производная этой функции равна

Стационарные точки:I. Одна из них,

, лежит внутри отрезка, две другие совпадают с концами. Найдем значения функции (9.13) в стационарной точке и на концах отрезка:

Следовательно, zmax = 4 и достигается при х2 = 1 .г, = = 4-2х2 = 2, т.е. в точке (2; 1).

Максимальный объем производства, равный zmax = 4 ед., достигается при условии, что затраты производственных факторов х1 и х2 равны соответственно 2 ед. и 1 ед. ►

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

Пусть решается задача определения условного экстремума функции г = /(Х) при ограничениях (9.8).

Составим функцию

(9.14)

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

2-го ресурса, соответствующие этому плану, то– цена (оценка) г-го ресурса, характеризующая изменение экстремального значения целевой функции в зависимости от изменения размера 2-го ресурса (маргинальная опенкаV L(X) – функция 22 + 222 переменных.

Определение стационарных точек этой функции приводит к решению системы уравнений:

(9.15)

Легко заметить, что =<р;(х), т.е. в (9.15) входят уравнения связи. Таким образом, задача нахождения условного

  • [1] Ж. Л. Лагранж (1736–1813) – французский математик и механик.
 
Если Вы заметили ошибку в тексте выделите слово и нажмите Shift + Enter
< Предыдущая   СОДЕРЖАНИЕ   Следующая >
 

Популярные страницы