Теория и методы принятия решений

Решение задач нелинейного программирования в Microsoft Excel

Задачи нелинейного программирования в Microsoft Excel решаются так же как и задачи линейного программирования (см. 1.2), с той лишь разницей, что в окне "Параметры поиска решения" необходимо сбросить флаги "Линейная модель" и, если это необходимо, "Неотрицательные значения".

Пример. Решить в Microsoft Excel следующую задачу нелинейного программирования:

найти при условии

В данной модели система ограничений состоит из одного линейного уравнения и нелинейной целевой функции.

Решение.

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

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

3. После нажатия кнопки "Выполнить" получаем ответ:

из которого следует, что минимальное значение целевой функции равно 17278 и достигается при x1 = 91 и x2 = 89.

Решение задач нелинейного программирования методом Лагранжа

Метод Лагранжа заключается в выполнении следующих действий.

1. Если в системе ограничений встречаются неравенства, то, вводя дополнительные переменные, преобразовать неравенства в равенства.

2. Для заданной системы ограничений и целевой функции составить функцию Лагранжа:

где есть неопределённые коэффициенты[2].

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

4. Решить полученную систему и, тем самым, найти все стационарные точки функции , то есть такие точки, в которых функция может иметь экстремумы (минимумы или максимумы).

5. Исследовать каждую точку на наличие в ней экстремума функции , применяя следующую теорему:

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

минимум, если все числа ?1, ?2, …, ?n являются положительными,

максимум, если знаки чисел ?1, ?2, …, ?n чередуются, начиная с минуса,

где

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

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

Пример. Решить методом Лагранжа в системе MathCad следующую задачу нелинейного программирования: