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

Содержание

Введение…………………………………………………………………………...3

Глава I. Нахождение экстремумов функций многих переменных (нелинейное программирование)………………………………………………………………4

1. Понятие экстремумов………………………………………………………...5
2. Условия существования экстремумов……………………………………...6
3. Классический метод определения условного экстремума……………….16
4. Метод Лагранжа……………………………………………………………..17

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

2.1 Линейная модель оптимального  планирования производства…………...22

2.2 Нелинейная модель оптимального  планирования производства ………..25

Заключение………………………………………………………………………29

Список литературы……………………………………………………………...30

Приложение 1……………………………………………………………………31

Приложение 2……………………………………………………………………33

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение

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

Метод Лагранжа базируется на нескольких ключевых идеях. Одна из них состоит в том, как  искать минимум функции, если на функцию  заданы некоторые ограничения. Этот приём теперь носит название «правило множителей Лагранжа»

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

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

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

 

 

 

 

 

 

 

Глава I Нахождение экстремумов функций многих переменных (нелинейное программирование)

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

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

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

задают  ограничения в виде равенств

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

Тогда задача нелинейного программирования может  быть сформулирована следующим образом:

найти вектор , доставляющий минимум (максимум) целевой функции при m линейных и (или) нелинейных ограничений в виде равенств

и (p-m) линейных и (или) нелинейных ограничений в виде неравенств

  [1]

1.1 Понятие  экстремумов

Для начала рассмотрим необходимые условия  экстремума функции, также определим  понятие экстремума. Начнем с понятия  экстремума:

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

Определение: Точка называется точкой экстремума (максимума или минимума)

функции , если есть соответственно наибольшее или наименьшее значение функции в некоторой окрестности точки .

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

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

 

Рис.1.1 Вид поверхностей, изображающих поверхности функций в окрестности точек экстремума

 

1.2 Условия  существования экстремумов

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

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

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

, .

Доказательство: Допустим, что функция  имеет в точке экстремум.

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

.

Аналогично  функция  при постоянном , как функция одного , достигает экстремума при . Значит,

Что и  требовалось доказать.

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

Уравнение касательной плоскости к поверхности  :

для стационарной точки  принимает вид .

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

Для отыскания  стационарных точек функции  нужно приравнять нулю обе ее частные производные

, . (*)

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

Пример 1: Найдем стационарные точки функции

Система уравнений (*) имеет вид:

Из второго  уравнения следует, что или  , или .

Подставляя  по очереди эти значения в первое уравнение, найдем четыре стационарные точки:

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

 Иногда  удается, и, не прибегая к  достаточным условиям, выяснить  характер стационарной точки  функции. Так, если из условия  задачи непосредственно следует,  что рассматриваемая функция  имеет где- то максимум или  минимум и при этом системе  уравнений (*) удовлетворяет только одна точка (т. е. Одна пара значений x и y), то ясно, что эта пара и будет искомой точкой экстремума функции.

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

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

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

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

и устанавливаются необходимые условия экстремума. Именно: Дифференцируемая функция n переменных может иметь экстремумы только при тех значениях x, y, z,..., t, при которых равны нулю все ее n частных производных первого порядка:

Эти равенства  образуют систему n уравнений с n неизвестными.

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

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

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

Пусть точка  является стационарной точкой функции

, т. е. 

Вычислим  в точке  значение вторых частных производных функции и обозначим их для краткости буквами A, B и C:

Если  , то функция имеет в точке экстремум: при A<0 и C<0 и минимум при A>0 и C>0 (Из условия следует, что A и C обязательно имеют одинаковые знаки).

 Если , то точка не является точкой экстремума.

 Если , то неясно, является ли точка точкой экстремума и требуется дополнительное исследование.

Пример:

1) Ранее  в примере было установлено,  что функция 

имеет четыре стационарные точки:

Вторые  частные производные данной функции  равны

В точке  имеем: A=10, B=0, C=2. Здесь ; значит, точка является точкой экстремума, и так как A и C положительны, то этот экстремум - минимум.

В точке  соответственно будет A=-10, B=0, C=-4/3; .

Это точка  максимума. Точки  и не являются экстремумами функции (т.к. в них ).

2) Найдем  точки экстремума функции  ;

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

,

находим одну стационарную точку - начало координат. Здесь A=2, B=0, C= -2. Следовательно, и точка (0, 0) не является точкой экстремума.

Локальные экстремумы

Определение1: Говорят, что функция имеет в точке локальный максимум, если существует такая окрестность точки , для которой для всякой точки M с координатами (x, y) выполняется неравенство: . При этом, т. е. приращение функции меньше 0.

Определение2: Говорят, что функция имеет в точке локальный минимум, если существует такая окрестность точки , для которой для всякой точки M с координатами (x, y) выполняется неравенство: . При этом, т. е. приращение функции больше 0.

Определение 3: Точки локальных минимума и максимума называются точками экстремума.

Условные  экстремумы

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

 Пусть заданы функция и линия L на плоскости 0xy. Задача состоит в том, чтобы на линии L найти такую точку P(x, y), в которой значение функции является наибольшим или наименьшим по сравнению со значениями этой функции в точках линии L, находящихся вблизи точки P. Такие точки P называются точками условного экстремума функции на линии L. В отличие от обычной точки экстремума значение функции в точке условного экстремума сравнивается со значениями функции не во всех точках некоторой ее окрестности, а только в тех, которые лежат на линии L.

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

Рис.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. Исследование линейной и нелинейной моделей планирования производства