86045 (566113), страница 2

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

Текст из файла (страница 2)

L (х*, λ*) =max {L (x*,λ) ׀ λ ≥0}, (13)

g_i (x*) =0, i=1, 2,..., m, (14)

х*≥0,λ*≥0.

Условие (12) минимума функции Лагранжа по х эквивалентно выполнению в точке (х*, λ*) неравенства

≥0. (12′)

Условие (13) максимума функции Лагранжа по λ эквивалентно выполнению в точке (х*, λ*) неравенства

≤0. (13′)

Утверждение 2. х* - оптимальное решение задачи (3) в том и только в том случае, когда существует такой вектор λ* ≥0, что (х*, λ*) - седловая точка функции Лагранжа L (x,λ).

1.3 Решение задач квадратичного программирования методом седловой точки

Рассмотрим задачу квадратичного программирования, т.е.

f (x) = (Сx,x) + (d,x) min, (15), g (x) =Ax ≤ b,

где С - матрица размера n*n; d, х - векторы-столбцы n*1; А - матрица размера m*n; b - вектор-столбец m*1. Для задачи квадратичного программирования критерий существования седловой точки приобретает вид задачи решения СЛАУ. Действительно, функция Лагранжа в этом случае запишется в виде

L = d_kx_k+ c_kjx_kx_j+ λ_i ( a_ijx_j-b_i), (16)

где c_kj - элементы матрицы С; d_k - элементы вектора d; b_i - элементы вектора свободных членов b; a_ij - элементы матрицы А; λ_i - коэффициенты Лагранжа. Необходимые и достаточные условия оптимальности решения х* принимают вид

v_j d_j+2 c_kjx_k+ λ_ia_ij, v_j ≥0, (j=1,…,n), (17)

y_i a_ijx_j-b_{i, -} y_i ≤0, (i=1,...,m), (18)

x_jv_j=0, x_j≥0, (j=1,...,n), (19)

λ_i (-y_i) =0, λ_i≥0. (20)

Равенства (17), (18) образуют систему n+m линейных уравнений с 2 (n+m) неизвестными x_1,…,x_n,v₁,…,v_n, λ₁,…, λ_m,y_1,…,y_m. Решения этой системы, при которых выполняются равенства (19), (20), дают координаты седловой точки (х*,λ*). Соответственно n координат х* дают оптимальное решение задачи (15).

2. Порядок выполнения лабораторной работы

Построить допустимую область задачи и линии уровня.

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

Для каждой точки указать активные и пассивные ограничения. Проверить выполнение достаточных условий экстремума в найденных стационарных точках. Найти глобальный минимум функции. Используя критерий (утверждение 1), проверить, что найденная точка является седловой точкой функции Лагранжа.

Проверить справедливость оценки (9), решив задачу при положительных и отрицательных малых значениях приращения ∆b.

Решить задачу квадратичного программирования методом седловой точки. Для этого записать систему (17) - (18), найти ее решения, удовлетворяющие условиям (19) - (20).

3. Пример выполнения лабораторной работы

Минимизировать нелинейную функцию при условиях и , применяя метод функции Лагранжа. Проверить справедливость оценки изменения целевой функции (9).

Допустимая область - часть сферы , лежащая в подпространстве

, a= (1, 1,1).

Рассмотрим случай . Если при этом , то .

Из (21) - (23) , что противоречит (28).

Если , то (иначе получаем противоречия в (21) - (23)).

Из (21) - (23) . Подставим в (26): . Отсюда , что противоречит исходному предположению .

Рассмотрим теперь случай .

Если , то получаем точку (из (1′) … (3′), (7′)).

Остальные "симметричные" точки здесь и далее приводить не будем.

Если , , , то

,

,

.

Далее получаем точки

и . , .

Для значение

, для значение .

Если , , то

Если , то

и .

Следовательно, и . Однако, , значит, пришли к

противоречию.

Таким образом, .

Суммирование первых трех уравнений дает уравнение

,

в котором последнее слагаемое равно нулю, поэтому

.

С другой стороны,

и .

Следовательно, ,

откуда . Если , то .

Разделим равенства на : . Однако, если , то их произведение не может быть равно . Значит, . Если , получаем следующую систему:

.

Получаем точку

(в силу симметрии переменных х₁, х₂, х₃ координаты можно переставить),

, .

Предположив , получим те же результаты.

Найдены следующие точки:

, , ;

, , , ;

, , , ;

, , , .

Запишем второй дифференциал обобщенной функции Лагранжа.

, , ;

.

является активным ограничением только для точки .

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

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

.

Запишем матрицу квадратичной формы относительно приращений:

.

Для "верхнего" знака матрица

.

Для "нижнего" знака элементы матрицы меняют знак. Согласно критерию Сильвестра, в этой точке нет экстремума.

Сравним значения функции в остальных точках:

; ; .

Точкой глобального минимума является

,

значение функции в этой точке

-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. Стандарт предприятия: Общие требования и правила оформления дипломных и курсовых проектов (работ): СТП УГТУ - УПИ 1 - 96. Екатеринбург, 1996.

2. Акулич И.Л. Математическое программирование в примерах и задачах / И.Л. Акулич. М.: Высшая школа, 1993.335 с.

3. Аттетков А.В. Методы оптимизации / А.В. Аттетков, С.В. Галкин,

4. В.С. Зарубин. М.: МГТУ, 2004.432 с.

5. Васильев В.П. Численные методы решения экстремальных задач / В.П. Васильев. М.: Наука, 1980.518 с.

6. Габасов Р. Методы оптимизации / Р. Габасов, Ф.М. Кириллова. Минск: БГУ, 1981.350 с.

7. Дьяконов В. Matlab: учебный курс / В. Дьяконов. СПб.: Питер, 2001.560 с.

8. Еремин И.И. / И.И. Еремин, Н.Н. Астафьев. М.: Наука, 1976.192 с.

9. Пантелеев А.В. Методы оптимизации в примерах и задачах /

10. А.В. Пантелеев, Т.А. Летова. М.: Высшая школа, 2005.544 с.

11. МЕТОДЫ ОПТИМИЗАЦИИ ФУНКЦИЙ МНОГИХ ПЕРЕМЕННЫХ: методические указания к лабораторным работам / сост. С.Д. Чернина. Екатеринбург: УГТУУПИ, 2007.36 с.

Приложение

Рекомендации по использованию EXCEL и MATLAB

Построение графиков

Для построения графика функции y=f (x₁,x₂) могут быть использованы следующие инструменты:

1. В EXCEL - Мастер диаграмм, подтип Поверхность.

а. Используя автозаполнение, на листе EXCEL в столбец А и первую строку с выбранным шагом ввести соответственно значения переменных x₁ и x₂, для которых будут вычисляться значения функции.

б. В ячейку В2 ввести выражение для вычисления функции f (x₁,x₂) в точках $A2, B$1 (знак $ - признак абсолютной адресации, при которой будут зафиксированы первый столбец - перебор значений переменной x₁ и первая строка - перебор значений переменной x₂) и нажать одновременно три клавиши Ctrl, Shift, Enter, поскольку формула используется для обработки массивов. В строке формул должны появиться фигурные скобки.

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

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

2. В MATLAB - функции plot3, mesh, surf, surfl.

Характеристики

Список файлов лабораторной работы