Исследование линейной и нелинейной моделей планирования производства

Рис.1.2. График функции

Эта функция  имеет максимум в начале координат; ему соответствует вершина M полусферы. Если линия L есть прямая, проходящая через точки А и В (ее уравнение x+y-1=0), то геометрически ясно, что для точек этой линии наибольшее значение функции достигается в точке , лежащей посередине между точками А и В. Это и есть точка условного экстремума (максимума) функции на данной линии; ей соответствует точка M₁ на полусфере, и из рисунка видно, что ни о каком обычном экстремуме здесь не может быть речи.

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

 Приступим  теперь к практическому отысканию  точек условного экстремума функции  Z= f(x, y) при условии, что переменные x и y связаны уравнением j(x, y) = 0. Это соотношение будем называть уравнение связи. Если из уравнения связи y можно выразить явно через х: y=j(x), мы получим функцию одной переменной Z= f(x, j(x)) = Ф(х).

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

Так, в  вышеприведенном примере из уравнения  связи x+y-1=0 имеем y=1-х. Отсюда

Легко проверить, что z достигает максимума при х = 0,5; но тогда из уравнения связи y=0,5, и мы получаем как раз точку P, найденную из геометрических соображений.

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

Если  уравнение связи имеет более  сложный вид и нам не удается  ни явно выразить одну переменную через  другую, ни заменить его параметрическими уравнениями, то задача отыскания условного  экстремума становится более трудной. Будем по-прежнему считать, что в  выражении функции z= f(x, y) переменная j(x, y) = 0. Полная производная от функции z= f(x, y) равна:

Где производная  y`, найдена по правилу дифференцирования неявной функции. В точках условного экстремума найденная полная производная должна ровняться нулю; это дает одно уравнение, связывающее х и у. Так как они должны удовлетворять еще и уравнению связи, то мы получаем систему двух уравнений с двумя неизвестными

Преобразуем эту систему к гораздо более  удобной, записав первое

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

f`<sub>x</sub>=(x,y)+lj`_x(x,y)=0, f`<sub>y</sub>(x,y)+lj`_y(x,y)=0 (*),

которая вместе с уравнением связи j(x, y) = 0 образует систему трех уравнений с неизвестными х, у и l.

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

Z= f(x, y) при уравнении связи j(x, y) = 0, нужно образовать вспомогательную функцию

Ф(х,у)=f(x,y)+lj(x,y)

Где l-некоторая постоянная, и составить уравнения для отыскания точек экстремума этой функции.

 Указанная  система уравнений доставляет, как  правило, только необходимые условия,  т.е. не всякая пара значений  х и у, удовлетворяющая этой системе, обязательно является точкой условного экстремума. Достаточные условия для точек условного экстремума я приводить не стану; очень часто конкретное содержание задачи само подсказывает, чем является найденная точка. Описанный прием решения задач на условный экстремум называется методом множителей Лагранжа. [2, стр. 177-179, 183-187]

 

 

Необходимое условие экстремума

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

f'_xi(X^*) = 0, 1 = 1,2,..., n.

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

 

Как и в случае одной переменной, необходимое условие не является достаточным для того, чтобы стационарная точка была точкой экстремума. Для получения достаточных условий следует определить в стационарной точке знак дифференциала второго порядка. Дифференциал второго порядка обозначается d²f(x_l,x₂,...,x„) и равен сумме произведений частных производных второго порядка на соответствующие приращения аргументов.  Если  от частной производной f’_xi(X) найти частную производную по переменной X_j, то получим частную производную второго порядка по переменным X_i, X_j, которая обозначается f’’x_ix_j (X). В этом случае

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

 

а) в стационарной точке Х⁰ функция z = f(X) имеет максимум, 
если d²f(X°) < 0, и минимум, если d²f(X°) > 0, при любых , и 
(в этих случаях Х⁰ = X^*), не обращающихся в нуль одновременно;

б) если d²f(X )может принимать в зависимости от   и

и положительные, и отрицательные  значения, то в точке Х⁰ экстремума нет;

в) если d²f(X°) может обращаться в нуль не только при нулевых приращениях и , то вопрос об экстремуме остаетсяоткрытым.

Для функции двух переменных z = f(x_1,x₂) достаточные условия еще не очень сложны. Существуют четыре частные производные второго порядка:  , , , . Из них две смешанные производные и ,  если непрерывны, то равны.

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

; ; ;

(можно убедиться, что а₁₂=а₂₁)- Обозначим через определитель, составленный из а_ij для i,j = 1, 2:

 

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

а) если >0 и a₁₁ < 0 (a₂₂ < 0), то в точке Х⁰ функция имеет 
максимум: если >0 и a₁₁ > 0 (a₂₂ > 0), то в точке Х° — минимум (в этих случаях Х⁰ = X^*);

б) если <0, то экстремума нет;

в) если =0, то вопрос об экстремуме остается открытым.

Схема определения экстремума функции п переменных совпадает с правилами определения локального экстремума функции одной переменной.[3, стр. стр. 202-204]

 

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

Задача нелинейного  программирования (задача НП) в общем  виде формулируется так:

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

где функции  нелинейны.

В отличие  от задачи ЛП для задач НП нет  универсального метода решения.

В задаче ЛП допустимое множество R всегда является выпуклым с конечным числом крайних  точек. Поэтому воспользовавшись симплекс-методом  и перебрав только крайние точки, можно за конечное число шагов  найти оптимальное решение. В  задачах НП, наоборот, выпуклость допустимого  множества и конечность числа  его крайних точек совсем необязательны. Это и служит причиной основной трудности  решения задач НП.

Для определения  условного экстремума (то есть экстремума при ограничениях) можно воспользоваться  методами дифференциального исчисления, когда функция  имеет не ниже второй производной. [4]

1.4 Метод Лагранжа

Метод нахождения условного экстремума функции f(x), где , относительно m ограничений φ_i(x) = 0, i меняется от единицы до m.

Пусть задана задача НП при ограничениях-равенствах вида

 

Минимизировать  (1.4.1)

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

(1.4.2)

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

        (4.2.3)

Справедливо такое утверждение  для того чтобы вектор являлся решением задачи (1.4.1) при ограничениях, необходимо, чтобы существовал такой вектор , что пара векторов удовлетворяла бы системе уравнений

         (1.4.4)

         (1.4.5)

 Покажем необходимость условий  (1.4.4), (1.4.5) на простом примере:

минимизировать         (1.4.6)

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

          (1.4.7)

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

Допустим, что рассматриваемая  задача имеет точку минимума в  : , функции имеют непрерывные производные первого порядка на некотором открытом множестве и градиенты

линейно независимы.

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

минимизировать  . (4.2.8)

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

Приведенный подход можно в принципе распространить и на случай функции  переменных при наличии ограничений-равенств:

        (1.4.9)

Если функции  удовлетворяют условиям теоремы о неявной функции, то из переменных уравнений (1.4.9) можно выразить через остальные переменных, подставить их в и таким образом преобразовать задачу минимизации с ограничениями в задачу безусловной минимизации с переменными. Однако такой подход трудно реализовать на практике, поскольку очень трудно разрешить уравнения (4.2.9) относительно некоторых переменных. В общем случае это совсем невозможно. [5]

Поэтому рассмотрим другой подход, который  базируется на методе множителей Лагранжа.

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

                (1.4.10)

Аналогичные соотношения получим  для ограничений

                        (1.4.11)

Запишем уравнения (1.4.10), (1.4.11) совместно в виде

                            (1.4.12)

где

.

Поскольку вектор не является нулевым, то из (1.42.12) следует, что . Из этого следует, что вектора-строки 
матрицы A должны быть линейно зависимы. Следовательно, существуют три таких скаляра не все равные 0, что

.                (1.4.13)

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

                (1.4.14)

Таким образом, для задачи минимизации с ограничениями (1.4.6) существуют такие , для которых справедливо уравнение (1.4.14) и которые одновременно не обращаются в нуль. Итак, справедливость условий (1.4.4) для случая n=3 показана.

Таким образом, для отыскания минимума (1.4.6) при условиях (1.4.7) необходимо найти стационарную точку функции Лагранжа:

Для того чтобы найти искомые  значения , необходимо решить совместно систему уравнений (1.4.14), (1.4.5). С геометрической точки зрения условие (1.4.14) означает, что лежит в плоскости, натянутой на векторы

Теперь рассмотрим общий случай для произвольных . Пусть задана задача НП в виде (1.4.1), (1.4.2), все функции имеют непрерывные частные производные на множестве . Пусть -подмножество множества , на котором все функции , то есть . Тогда справедлива такая теорема о множителях Лагранжа.

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

                  (1.4.15)

Эта теорема обосновывает метод  множителей Лагранжа, который состоит  из следующих шагов.

Составляют функцию Лагранжа

Находят частные производные 

Решают систему уравнений 

                 (4.2.16)

и отыскивают точки  , удовлетворяющие системе (1.4.16).

 Найденные точки  дальше исследуют на максимум (или минимум).[6, стр. 148-155]

 

Глава II. Исследование линейной и нелинейной моделей планирования производства