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

Подставив
и
во второй
дифференциал
функции Лагранжа,
получим
.
Запишем матрицу квадратичной формы относительно приращений:
.
Для
"верхнего"
знака
матрица
.
Для "нижнего" знака элементы матрицы меняют знак. Согласно критерию Сильвестра, в этой точке нет экстремума.
Сравним значения функции в остальных точках:
;
;
.
Точкой глобального минимума является
,
значение функции в этой точке
-0,
192450.
.
Проверим
справедливость
оценки
для точки
,
.
Возьмем
вектор
,
ему соответствуют
множители
Лагранжа
.
Следовательно,
.
Перепишем
условие задачи,
введя приращение
:
;

.
Из
первых трех
уравнений
получаем
и подставим
в последнее
уравнение:
,
.
.
.
Возьмем,
например,
![]()
.
С другой стороны,
.
Аналогично
для
![]()
и
.
Решить задачу максимизации квадратичной функции
при условиях
15
и
1,2,3.
Перепишем условие следующим образом:

Функция Лагранжа имеет вид
.
Необходимые и достаточные условия минимума:
,
,
,
,
,
.
Получаем систему уравнений и неравенств:

Для решения промежуточной задачи ЛП воспользуемся средствами MS Excel. Введем формулы, соответствующие системе (рис.2), и начальное приближение для решения системы уравнений (рис.3).

Рис.2. Ввод данных задачи

Рис.3. Задание начального приближения
Заполним поля диалога "Поиск решения" (рис.4).

Рис.4. Экранная форма "Поиск решения"
В окне "Параметры" установим флажок "Неотрицательные значения".
В результате решения найдена седловая точка функции Лагранжа
(х*,λ*) = (15; 0; 0; 30) (рис.5).

Рис.5. Результаты поиска решения.
Оптимальное решение задачи: х* (15; 0; 0), f (x*) = 225.
4. Задания для лабораторного практикума
Решить задачу минимизации функции методом множителей Лагранжа.
Решить ЗНП методом седловой точки. Промежуточную задачу решения СЛАУ решить, используя EXCEL.
1.
.
2.
.
3.
.
4.
.
5.
.
6.
.
7.
.
8.
.
Ограничения (для всех вариантов):
.
Контрольные вопросы:
Активные и пассивные ограничения. Регулярная задача.
Теорема Куна-Такера.
Достаточные условия минимума в задачах математического программирования.
Седловая точка.
Метод седловой точки для задачи квадратичного программирования.
Библиографический список
Стандарт предприятия: Общие требования и правила оформления дипломных и курсовых проектов (работ): СТП УГТУ - УПИ 1 - 96. Екатеринбург, 1996.
Акулич И.Л. Математическое программирование в примерах и задачах / И.Л. Акулич. М.: Высшая школа, 1993.335 с.
Аттетков А.В. Методы оптимизации / А.В. Аттетков, С.В. Галкин,
В.С. Зарубин. М.: МГТУ, 2004.432 с.
Васильев В.П. Численные методы решения экстремальных задач / В.П. Васильев. М.: Наука, 1980.518 с.
Габасов Р. Методы оптимизации / Р. Габасов, Ф.М. Кириллова. Минск: БГУ, 1981.350 с.
Дьяконов В. Matlab: учебный курс / В. Дьяконов. СПб.: Питер, 2001.560 с.
Еремин И.И. / И.И. Еремин, Н.Н. Астафьев. М.: Наука, 1976.192 с.
Пантелеев А.В. Методы оптимизации в примерах и задачах /
А.В. Пантелеев, Т.А. Летова. М.: Высшая школа, 2005.544 с.
МЕТОДЫ ОПТИМИЗАЦИИ ФУНКЦИЙ МНОГИХ ПЕРЕМЕННЫХ: методические указания к лабораторным работам / сост. С.Д. Чернина. Екатеринбург: УГТУ-УПИ, 2007.36 с.
Приложение
Рекомендации по использованию EXCEL и MATLAB
Построение графиков
Для построения графика функции y=f (x1,x2) могут быть использованы следующие инструменты:
1. В EXCEL - Мастер диаграмм, подтип Поверхность.
а. Используя автозаполнение, на листе EXCEL в столбец А и первую строку с выбранным шагом ввести соответственно значения переменных x1 и x2, для которых будут вычисляться значения функции.
б. В ячейку В2 ввести выражение для вычисления функции f (x1,x2) в точках $A2, B$1 (знак $ - признак абсолютной адресации, при которой будут зафиксированы первый столбец - перебор значений переменной x1 и первая строка - перебор значений переменной x2) и нажать одновременно три клавиши Ctrl, Shift, Enter, поскольку формула используется для обработки массивов. В строке формул должны появиться фигурные скобки.
в. Выделить ячейку В2 и, протянув маркер заполнения сначала вниз, пробегая все ячейки, заполненные в столбце А, а затем вправо, пробегая все ячейки, заполненные в строке 1, заполнить массив значений функции в узловых точках области построения графика.
г. На вкладке "Стандартные" Мастера диаграмм выбрать подтип Поверхность. Поверхностная диаграмма дает трехмерное изображение функции, а контурная диаграмма представляет вид сверху на поверхностную диаграмму и является аналогом линий уровня исследуемой функции.
2. В MATLAB - функции plot3, mesh, surf, surfl.
а. С помощью функции meshgrid получить двумерные массивы координат узловых точек области построения графика: u=a: ∆1: b; v=c: ∆2: d; [x,y] =meshgrid (u,v).
б. Задать исследуемую функцию: f= f (х, у).
в. Применяя указанные выше функции, получить трехмерное изображение: plot3 (x,y,f) или mesh (x,y,f), surf (x,y,f), surfl (x,y,f).
Действия с матрицами
Для нахождения собственных значений и собственных векторов матрицы Гессе могут быть использованы следующие инструменты MATLAB:
λ = eig (a) - функция eig (a) возвращает собственные значения заданной матрицы a. Пример задания матрицы 4х4: a = [16 3 2 13; 5 10 11 8; 9 6 7 12; 4 15 14 1] ;
[v,d] = eig (a) - при таком обращении функция возвращает собственные векторы v и собственные значения как элементы диагональной матрицы d.
Для нахождения матрицы, обратной матрице Гессе, могут быть использованы следующие инструменты:
В EXCEL - функция МОБР возвращает обратную матрицу для матрицы, хранящейся в массиве.
В MATLAB - функция y=inv (a) возвращает обратную матрицу для матрицы a.
1 Лабораторная работа выполнена студентом Коневым С.