Методические указания по изучению дисциплины и выполнению контрольной работы (стр. 12 из 14)

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

Граница области Ф аналитически может быть задана системой уравнений (условий) относительно переменных

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

Условный экстремум. Пусть необходимо найти экстремум функции

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

)=0, (6.9)

Предполагается, что функции

и имеют непрерывные частные производные по всем переменным. Уравнения (6.9) называются уравнениями связи.

Говорят, что в точке

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

Для задач линейного программирования характерно следующее:

- Множество допустимых решений выпукло. Это выпуклое множество имеет конечное число вершин, называемых обычно крайними (угловыми( точками.

- Множество всех точек

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

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

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

У произвольной задачи нелинейного программирования некоторые или все приведенные выше свойства ЗЛП отсутствуют. Поэтому ЗНП гораздо сложнее задач линейного программирования и для них не существует общего универсального метода решения (аналогично симплексному методу).

4.4.Метод множителей Лагранжа

Среди задач (4.1)-(4.3) особое место занимают задачи типа

(6.10)

, (6.11)

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

и непрерывны вместе со своими первыми частными производными.

Можно указать следующий порядок решения задачи (6.10)-(6.11) методом множителей Лагранжа:

1) составить функцию Лагранжа:

L

(6.12)

здесь

- множители Лагранжа;

2)Найти частные производные функции Лагранжа по всем переменным

и приравнять их нулю. Тем самым получим систему:

(6.13)

Эта система состоит из m + n уравнений. Решить эту систему (если это окажется возможным) и найти таким образом все стационарные точки функции Лагранжа;

3) из стационарных точек, взятых без координат

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

В основе метода Лагранжа решения классической задачи оптимизации (6.10)-(6.11) лежит утверждение, что если

в точке имеет экстремум, то существует такой вектор , что точка

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

Множителям Лагранжа можно придать следующий экономический смысл. Если

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

Пример 6.4. По плану производства продукции предприятию необходимо изготовить 200 изделий. Эти изделия могут быть изготовлены двумя технологическими способами. Производственные затраты на изготовление n изделий первым способом равны 4n+n², а для второго способа - 8n+n². Сколько изделий надо изготовить каждым способом, чтобы общие затраты на производство продукции были бы минимальными.

Решение.

Обозначим число изделий, изготовленных первым способом через х₁, вторым способом - х_2. Тогда суммарные затраты на изготовление продукции по плану составят:

f (x₁,x₂)=4x₁+x₁²+8x₂+x₂²

При этом общее число изделий должно быть равно 200, т.е.

x₁+x₂=200

Получим математическую модель задачи:

f(x₁,x₂)=4x₁+x₁²+8x₂+x₂²

x₁+x₂=200

x₁

x₂

Для ее расчета применим метод множителей Лагранжа.

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

L(x_1,x₂,

)=4x₁+x₁²+8x₂+x₂²+ (200-x₁-x₂)

Найдем частные производные функции L по x₁,x₂,

и приравняем их к нулю:

имеем систему:

Исключим из этой системы

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

Таким образом, по необходимому условию экстремума дифференцируемой функции получим стационарную точку М(101,99) возможного условного экстремума функции f(x₁,x₂).

Дальнейшее исследование этой точки будем проводить как и в случае безусловного экстремума.

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

Для рассматриваемого примера производные постоянны и не зависят от значений х₁ и х₂. Поэтому a₁₁=2, a₁₂=a₂₁=0, a₂₂=2 (см. 6.8). Вычислим определитель