Добавил:
Studfiles2 Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:

/ Методичка по методам оптимизации

.doc
Скачиваний:
34
Добавлен:
02.05.2014
Размер:
1.18 Mб
Скачать

Если N стремится к бесконечности, полученная оценка за вероятностью совпадает к глобальному минимуму функции, что рассматривается.

При решении задачи максимизации функции F(x) необходимо заменить ее на функцию–F(x).

Метод Фибоначчи.

Метод Фибоначчи (МФ) применяется для поиска минимума унимодальной функции одной переменнойy=F(x), что задана на промежутке [A,B].

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

В начале вычислений возлагают А{0}= А, B{0}= B.

На s-у шаге определяют величины

L{s}= B{s} G{s}(B{s} А{s})

R{s}= А{s}+ G{s}(B{s} А{s})

где G{s}=Fi(Ns1)Fi(Ns), s=0...,N3, G{N2}=(1+)2 или (1)2, N—заданное число итераций>0,Fi(j) —числа Фибоначчи, что задаются рекуррентным соотношением

Fi(j)= Fi(j1) + Fi(j2), j 2, Fi(0)= Fi(1)= 1.

Возлагают

А{s+1}= А{s}, B{s+1}=R{s}, если F(L{s})  F(R{s})

А{s+1}= L{s}, B{s+1}=B{s}, если F(L{s})> F(R{s}).

За приближенное решение задачи принимают

x* = (А{N}+ B{N})2, y* = F(x*).

Для МФ в случае предварительно фиксированного числа итераций длина конечного интервала поиска минимальная.

При решении задачи максимизации функции F(x) необходимо заменить ее на функцию–F(x).

Метод дихотомии (половинного деления).

Метод дихотомии (МД) применяется для поиска минимума унимодальной функции одной переменнойy=F(x), что задана на промежутке[A,B].

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

В начале вычислений возлагают А{0}= А, B{0}= B.

На s-у шаге определяют величины

L{s} = (А{s}+ B{s} )2

R{s}= (А{s}+ B{s}+ )2

где >0—достаточно малое число. Возлагают

А{s+1}= А{s}, B{s+1}=R{s}, если F(L{s})  F(R{s})

А{s+1}= L{s}, B{s+1}=B{s}, если F(L{s})> F(R{s}).

Итерации продолжают до тех пор, пока не будет выполняться неравенство

B{s} А{s} ,

где >0—заданное число, которое определяет погрешность решения задачи.

За приближенное решение задачи принимают

x* = (А{s}+ B{s})2, y* = F(x*).

При решениизадачи максимизации функцииF(x) необходимо заменить ее на функцию–F(x).

Программное обеспечение.

Обучающий модуль, с помощью которого задачи одномерной оптимизации Решаются в диалоге с пользователем за выложеннымиалгоритмами, вызывается из раздела «НЕЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ» главного меню пакетаПОМО.

Задание.

Решить методами золотого пересечения, случайного поиска, Фибоначчи и дихотомии задачи одномерной оптимизации, условия которых задаются модулем с помощью команды «Данные» главного меню, а также найти наибольшее и наименьшее значение следующих функций на указанных промежутках:

1)F(x)= |||x21|1|1| x  [2, 2];

2)F(x)= 2x33x212x+1++x  [2, 2];

3) F(x)= (x+1)2 ln(x+1)+x exp(x) x  [0, e];

4) F(x)= sin(x) sin(2x)+ arccos(x2) x  [0.75, 0.75];

5) F(x)= arctg(x) ln(x) /2 x  [0.65, 1.75];

6) F(x)= x+ + ехp(x) x2 x  [0, 4];

7) F(x)= 4 x(x2 + 4)[x2 (x 2)](2/5) x  [2, 2].

Лабораторная работа 18.

ЗАДАЧА ВЫПУКЛОГО КВАДРАТИЧНОГО ПРОГРАММИРОВАНИЯ.

КВАДРАТИЧНЫЙ СИМПЛЕКС-МЕТОД

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

Найти вектор x=(x1...,xn), что минимизирует (максимизирует) функцию

F(x)= F(x1...,xn)(18.1)

и удовлетворяет систему ограничений

Gi(x1...,xn) Ri 0, i=1...,m (18.2)

где символ Riзаменяет один из знаков , =, .

Если хотя бы одна из функций F,Gi(i=1...,m) является нелинейной, то указанная постановка определяетзадачу нелинейного программирования(ЗНЛП).

Совокупность точек (векторов) x, которые удовлетворяют (18.2), называетсядопустимой областью (множеством) и отражается черезD.

Произвольная точка D зоветсядопустимым решением (точкой, планом, вектором).

Функция F(x) соотношения (18.1) называется целевойфункцией.

Постановка задачи выпуклого программирования.

Найти вектор x=(x1...,xn), что минимизирует целевую функцию

F(x)= F(x1...,xn)(18.3)

и удовлетворяет систему ограничений

Gi(x1...,xn)0, i=1...,m (18.4)

xj0, j=1...,n (18.5)

где функции F, Gi(i=1...,m)—выпуклые.

Таким образом, для задачи выпуклого программирования (ЗОП) целевая функция (18.3)—выпуклая, ограничение (18.4)(18.5) определяют выпуклое допустимое множество.

Постановка задачи выпуклого квадратичного программирования.

Найти вектор x, что минимизирует целевую функцию

F(x)= x D xТ+c xТ (18.6)

и удовлетворяет систему ограничений

А xТ,x0(18.7)

где c=(c1...,cn),x=(x1...,xn),D=||dkl||,k,l=1...n,A=||aij||,i=1...,m,j=1...,n,b=(b1...,bm), матрицаD симметричная и неотъемлемо определена.

Таким образом, для задачи выпуклого квадратичного программирования (ЗОКП) целевая функция (18.6)—выпуклая квадратичная, ограничение (18.7)—линейные и определяют выпуклое многогранное допустимое множество.

Заметим, что для случая n=2, m=1ЗОКП имеет вид:

d11 x12 + d22 x22 + 2 d12 x1 x2 + c1 x1 + c2 x2  min

a11x1 + a12x2a10, xj0, j=1,2

к тому же D=||dkl||,k,l=1,2,d12= d21.

Основные утверждения.

Определение.МножествоW зовется выпуклым, если для произвольных точекx,yW, иt[0,1] выполняетсяtx+(1t)yW.

Определение.ФункцияH(x),xWEn, гдеW—выпуклое множество, зовется выпуклой, если для произвольных точекx,yW иt[0,1] выполняется неравенствоH(tx+(1t)y)tH(x)+(1t)H(y).

Теорема.Множество {x:H(x)0},где функция H(x)выпуклая, является выпуклым.

Теорема. Пересечение выпуклых множеств является выпуклым множеством.

Теорема. Квадратичная функция F(x)=xDxТ+cxТ выпуклая, если матрица Dнеотъемлемо определена.

Теорема. Матрица Dнеотъемлемо определена, если все ее диагональные миноры неотъемлемые:

det(D(k))0,D(k)=||dij||,і,j=1...k.

Теорема Куна-Таккера.

Пусть допустимая область D={xEn:Gi(x)0,i=1...,m,x0}задачи выпуклого программирования (18.3)(18.5)удовлетворяет условие Слейтера: существует xD такое, что для всех i=1...,mGi(x)<0,то есть множество D имеет внутренние точки.

Тогда для того, чтобы вектор x* был оптимальным решением задачи выпуклого программирования, необходимо и достаточно, чтобы существовал вектор u*0 такой, что пар (x*,u*)является точкой седла функции Лагранжа:

L(x,u)= F(x)+(u1G1(x)+...+umGm(x))

x=(x1...,xn)0,u=(u1...,um)0.

Говорят, что точка (x*,u*) являетсяточкой седла функцииL(x,u), если для всех x0,u0 имеют место неравенства

L(x*,u)L(x*,u*)L(x,u*).

Теорема Куна-Таккера.

Для непрерывно дифференцированных функций F(x), Gi(x),i=1...,m, теорема Куна - Таккера может быть сформулированна так.

Вектор x* является оптимальным решением задачи выпуклого программирования (18.3)–(18.5)тогда и только тогда, когда существует вектор u*0 такой, что для пары (x*,u*)выполняются условия:

xL(x*,u*)0xL(x*,u*)(x*) Т=0, j=1...,n

uL(x*,u*)0uL(x*,u*)(u*) Т=0, i=1...,m.

Для задачи (18.6)–(18.7) выпуклое квадратичное программирование последние соотношения приобретают виду

c+2xD+uA0(18. 8)

(c+2xD+uA)xТ=0(18. 9)

xAТb0(18.10)

(xAТb)uТ =0(18.11)

x0,u0.

Вспомогательная ЗЛП для ЗВКП.

Если ввести векторы y=(y1...,yn)0 таv=(v1...,vm)0, то соотношение (18.8)–(18.11) будут иметь вид:

c+2 x D+u Ав=0(18.12)

x АО b+v=0(18.13)

в xТ=0,v uТ=0(18.14)

x0,u0,в0,v0.

Заметим, что для случая n=2, m=1 будем иметь

2 d11 x1 + 2 d12 x2 + a11 u y1 = c1

2 d12 x1 + 2 d22 x2 + a12 u y2 = c2

a11x1+ a12x2+ v = a10

x1 y1=0,x2 y2=y2,u v = 0

x1, x2, u, y1, y2, v0.

Система (18.12)–(18.13) состоит из n+mлинейных уравнений относительно 2(m+n) неизвестных xj, yj (j=1...,n), ui, vi (i=1...,m).

Кроме того, как следует из условий (18.14), должно быть:

если xj>0, тоyj=0(18.15)

если yj>0, тоxj=0(18.16)

если ui>0, тоvi=0(18.17)

если vi>0, тоui=0. (18.18)

Следовательно, искомым решением системы (18.12)–(18.13) может быть произвольное неотъемлемое базисное ее решение, но такой, что переменные xjи yj (а также uiи vi) с одинаковыми индексами не могут быть в то же время базисными. Для отыскивания такого решения можно применить любой из известных методов ЛП, в частности, метод искусственного базиса. С этой целью запишем систему (18.12)–(18.13) в виде

2 x D+u Ав=–c(18.19)

x АО+v=b. (18.20)

Не ограничивая всеобщности, будем считать, что правые части этой системы неотъемлемые: –c0,b0(поскольку, в другом случае соответствующие уравнения, их правую и левую часть, достаточно умножить на–1). Согласно метода искусственного базиса в каждое уравнение системы (18.19)–(18.20), которое не содержит базисной переменной, вводим искусственную переменную. Поскольку переменныеvi(i=1...,m) можно считать базисными, то искусственные переменныеz=(z1...,zn)0 вводим только в уравнение (18.19) и рассматриваем вспомогательнуюКЗЛП

z iТ min (18.21)

2 x D+u Ав+z=–c(18.22)

x AТ+v = b (18.23)

x 0,u 0,в0,v0,z0(18.24)

где i=(1,1...,1)—n-мерный единичный вектор.

Квадратичный симплекс-метод.

Задача (18.21)–(18.24) решается симплекс-методом.

Если найденный ДБР этой задачи удовлетворяетусловиям дополняющей нежесткости(18.15)–(18.18), то он определяет оптимальное решение исходной ЗВКП. Иначе нужно перейти к новомуДБР. При этом в базисные включается новая переменная с нулевой оценкой.

Симплекс-метод с условиями (18.15)–(18.18) для решения вспомогательнойКЗЛП(18.21)–(18.24), построенной на основе задачи выпуклого квадратичного программирования (18.6)–(18.7), и называютквадратичным симплекс-методом(алгоритм обычного симплекс-метода, а также все связанные с ним определения и утверждения приведены в методических указаниях к лабораторной работе №2).

Если в оптимальном решении вспомогательной КЗЛП (18.21)–(18.24) все искусственные переменныеzj(j=1...,n) принимают нулевые значения, то, отбрасывая их, получимДБР системы (18.19)–(18.20). Та его часть, которая отвечает переменным начальной задачи выпуклого квадратичного программирования (18.6)–(18.7), и будет ее оптимальным решением.

Если же в оптимальном решении вспомогательной КЗЛП(18.21)–(18.24) значение хотя бы одной из искусственных переменных отличное от нуля, то система (18.19)–(18.20) решений не имеет, а, следовательно, множество седловых точек функции Лагранжа начальной задачи выпуклого квадратичного программирования пустое.

Программное обеспечение.

Обучающий модуль, с помощью которого задача выпуклого квадратичного программирования Решается в диалоге с пользователем за выложеннымалгоритмом, вызывается из раздела «НЕЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ» главного меню пакетаПОМО.

Геометрическая интерпретация задачи нелинейного программирования осуществляется модулем, который вызывается из того же самого раздела.

Задание.

Решить квадратичным симплекс-методом задачи выпуклого квадратичного программирования, условия которых задаются модулем с помощью команды «Данные» главного меню (задачи №1–№9), а также следующие задачи.

Во всех задачах выполняются условия: x10,x20.

1)

x12 + x222 x1 4 x2min

2)

2 x12 3 x22+4 x1 x2 +12 x2max

2 x1+3 x26;

3 x1 +4 x212;

3)

2 x12 + x22x1 x2x1min

4)

x12+3 x22x12 x2min

x1+2 x21;

x1+4 x27;

5)

2x12 3x22+16x1+24 x2 max

6)

x12 + x223 x18 x2  min

2 x1+x24;

x1+2 x24;

7)

x12x22+x1+2 x2max

8)

x12x22+x1x2+5 x1+2 x2max

x1+2 x216;

2 x1+3 x215.

Ответы:

1)x* = (0.69; 1.54).2) x* = (1.23; 2.07).3) x* = (0.29; 0.14).4) x* = (0.5; 0.33).

5)x* = (0.57; 2.86).6) x* = (0.4; 1.8). 7) x* = (0.5; 1). 8) x*= (3.63; 2.58).

Лабораторная работа 19.

ЗАДАЧА БЕЗУСЛОВНОЙ ОПТИМИЗАЦИИ.

МЕТОД САМОГО БЫСТРОГО СПУСКУ

Постановка задачи безусловной оптимизации.

Найти вектор x=(x1...,xn), что минимизирует (максимизирует) функцию

F(x)=F(x1...,xn).

Градиентные методы безусловной оптимизации.

Для задачи безусловной минимизации метод заключается в вычислении последовательности приближений x[s] по правилу

x[s+1]= x[s] [s] F(x[s])

где F(.) — градиент функцииF(.),который задается соотношением

[s]>0—шаг, величина которого определяется конкретным градиентным методом. Начальное решениеx[0] выбирается произвольно. Итерации прекращают, если на некотором шагеs выполняется неравенство

||F(x[s])|| <,

где норма градиента определяется формулой

а >0—некоторая заранее заданная величина, что определяет точность решения.

Метод самого быстрого спуска.

Метод самого быстрого спуска представляет собой градиентный метод, в котором величина шага [s]выбирается по правилу

F(x[s] [s]F(x[s])) = min(F(x[s]–F(x[s])))

где минимум берется по всем >0.

При некоторых условиях x[s]следует к стационарной точке функцииF(x), еслиs следует к бесконечности.

Программное обеспечение.

Обучающий модуль, с помощью которого задача безусловной оптимизации решается в диалоге с пользователем методом самого быстрого спуска, вызывается из раздела «НЕЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ» главного меню пакета.

Задание.

Решить методом самого быстрого спуска задачи безусловной оптимизации, условия которых задаются модулем с помощью команды «Данные» главного меню (задачи №1№9).

Лiтература

1.Ю.М.Ермольев, И.И.Ляшко, В.С.Михалевич, В.И.Тюптя. Математические методы исследования операций. Киев, «Высшая школа», 1979.

2.Ю.Д.Попов.Линейное и нелинейное программирование. Киев, УМК ВО, 1988.

3.Ф.П.Васильев.Численные методы решения экстремальных задач. Москва, «Наука», 1980.

4.И.Л.Калихман.Сборник задач по математическому программированию. Москва, «Высшая школа», 1975.

5.В.Ф.Капустин.Практические занятия по курсу математического программирования. Издательство Ленинградского университета, 1976.

6.Ю.П.Зайченко, С.А.Шумилова.Исследование операций, сборник задач. Киев, «Высшая школа», 1990.

7.В.Э.Фигурнов.IBM PC для пользователя. Москва, «Финансы и статистика», 1992.

Соседние файлы в предмете Методы оптимизации