МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ УКРАИНЫ
НАЦИОНАЛЬНЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ
«ХАРЬКОВСКИЙ ПОЛИТЕХНИЧЕСКИЙ ИНСТИТУТ»
Факультет информатики и управления
Кафедра экономической кибернетики и маркетингового менеджмента
КУРСОВАЯ РАБОТА
По математическому программированию
Исследование методов оптимизации
Харьков 2009
РЕФЕРАТ
Данная курсовая работа содержит: 41 страницу, 16 таблиц, 6 графиков.
В курсовой работе рассмотрены теоретические основы двух методов оптимизации математического программирования :
— метод Нелдера-Мида ;
— градиентный метод с дроблением шага.
Произведена минимизация исследуемой функции указанными методами. Выявлена зависимость числа итераций от заданной точности. Сопоставлена трудоемкость и эффективность оптимизации заданной функции различными методами (градиентным и методом Нелдера-Мида).
Ключевые термины:
Градиент – вектор первых частных производных функции.
Линии уровня – множества точек, в которых функция />принимает постоянные значения, т.е. />
Методы нулевого порядка – методы, которые не предполагают вычисления производной для поиска оптимума.
Методы первого порядка – методы, в которых кроме вычисления функции в любой точке предлагается вычисление первых производных.
СОДЕРЖАНИЕ
1. Введение
2. Математическое описание методов оптимизации
2.1 Метод Нелдера-Мида
2.2 Градиентный метод с дроблением шага
3. Решение задачи минимизации для каждого из методов
3.1 Метод Нелдера-Мида
3.2 Градиентный метод с дроблением шага
4. Графическая интерпретация решения задачи
5. Аналитическое исследование методов
6. Заключение
7. Приложение
8. Список литературы
СПИСОК УСЛОВНЫХ ОБОЗНАЧЕНИЙ
/>— точка
/>— длинна шага
/>— вектор градиент
E — точность
N – количество итераций
Д – матрица координат симплекса
t – длинна ребра симплекса
1. ВВЕДЕНИЕ
Объектом исследования предмета математическое программирование являются задачи оптимизации.
Оптимизация подразумевает нахождение наилучшего варианта среди всех существующих. В любой практической оптимизационной задаче существует много совпадающих этапов. Наиболее важным этапом является моделирование рассматриваемой физической ситуации с целью получения математической функции, которую необходимо минимизировать, а также определения ограничений, если таковые существуют. Затем следует выбрать подходящую процедуру для осуществления минимизации. Эта процедура должна быть реализована на практике, что во многих реальных случаях вынуждает использовать ЭВМ для выполнения большого объема вычислений.
Универсальных методов, подходящих для поиска экстремума абсолютно любой функции не существует. Данная курсовая работа ставит себе целью исследовать метод оптимизации нулевого порядка – метод Нелдера-Мида, а также метод оптимизации первого порядка – градиентный метод с дроблением шага на примере конкретной функции. Таким образом, получив практические результаты, можно будет сравнить эффективность рассматриваемых методов, применяемых к исследуемой функции.
ПОСТАНОВКА ЗАДАЧИ ( Вариант задания 1)
Исследовать функцию типа :
/>
Используемые методы минимизации />:
Метод: Нелдера-Мида.
Метод: Градиентный с дроблением шага.
Необходимо :
Решить задачу минимизации />, начав итерации из выбранной начальной точки x0=(1;1) заданными по варианту методами, необходимая точность решения />. Привести таблицу результатов расчета типа: Итерация: /> — точка: />значение: />критерий: />.
Рассчитать 3 линии уровня функции и изобразить их на графике.
Отобразить на графиках линий уровня для каждого из заданных методов траекторию движения по итерациям (траекторию спуска).
Выявить зависимость числа итераций N от заданной точности E, значения точности: />, />, />, />, />, />. Привести таблицу результатов как в п.1 для каждого значения E.
5. Сравнить эффективность рассмотренных в варианте методов по числу итераций N, построить графики N=F(E).
2. МАТЕМАТИЧЕСКОЕ ОПИСАНИЕ МЕТОДОВ ОПТИМИЗАЦИИ
2.1 Метод Нелдера-Мида
Вводится симплекс, координаты вершин которого заданы таблицей (одна из вершин в начале координат).
/>
/>/>
/>/>
t – некоторое выбранное число.
Если n = 2, то при t = 1 имеем
/>
/>
Расположение симплекса показано на рисунке 2.1
Рисунок 2.1- Начальное расположение симплекса
Легко убедиться в том, что если координаты вершин симплекса задать в соответствии с матрицей Д0, то расстояние между двумя любыми вершинами симплекса всегда будет равно выбранной константе t независимо от размерности задачи n .
Действительно, расстояние между любой вершиной xj, j= 2,3,.., n+1, и вершиной x1 равно
/>
С другой стороны, расстояние между любой парой вершин />, />, />, равно />Зададим начальную точку процедуры поиска минимума вектором />Перенесем исходный симплекс таким образом, чтобы вершина, находившаяся в начале координат, оказалась в точке />. Получим матрицу--PAGE_BREAK--
/>
Вычислим значения оптимизируемой функции в точках />и переномеруем точки так, чтобы выполнялись неравенства :
/>.
Найдем координаты центра тяжести фигуры, получающейся в результате удаления вершины />:
/>
Осуществим отражение вершины />относительно центра тяжести. Получим точку
/>.
Если a=1, то получим зеркальное отражение. В одномерном случае процедура отражения, обеспечивающая получение точки />, симметричной точке />относительно />иллюстрируется рис. 2.2
/>
/>
Рисунок 2.2 — Построение точки />
Сравним теперь между собой значения />
Возможны следующие варианты
а)/>. В этом случае выполняется растяжение симплекса и отыскивается точка/>
Параметр />обычно принимается равным 1,5.
Полученная точка />заменяет />, если />. В противном случае для замены />используется точка />.
б) />. При этом реализуется отражение. Точка />заменяет />.
в) />. В этом случае осуществляется сжатие и отыскивается точка/>
Параметр />обычно принимается равным 0,5. Точка />заменяет />.
г) />. При этом осуществляется редукция (уменьшение размера симплекса путем приближения всех его вершин к вершине />). Координаты вершин нового симплекса рассчитываются по формулам
/>
Критерий останова вычислительной процедуры имеет вид :
/>
/>
Критерий останова J является составным. При этом его компоненты имеют различный вес в зависимости от того, каков характер поведения оптимизируемой функции в окрестности экстремума. Если в районе экстремума оптимизируемая функция изменяется по типу «глубокая впадина», то больший вклад в численное значение критерия J вносит первое слагаемое, а второе при этом быстро уменьшается. Напротив, если оптимизируемая функция изменяется по типу «пологое плато», то первое слагаемое быстро становится малым и поэтому второе слагаемое вносит больший вклад в величину критерия J.
Модификация метода
Описанный «классический» вариант построения алгоритма метода Нелдера-Мида обладает конструктивным недостатком, который состоит в следующем. Предположим, что оптимизируемая функция, для простоты, двух переменных имеет вид глубокого оврага с очень пологим дном. Тогда может случиться так, что симплекс, который в рассматриваемом случае представляет собой треугольник, в какой-то момент двумя вершинами ляжет на дно оврага, а третья окажется на его склоне. При этом на очередном шаге произойдет переброс этой вершины на другой склон, а затем редукция или сжатие симплекса. Если склон оврага крутой, то эта процедура повторится много раз, в результате чего симплекс сожмется и может сработать критерий останова, хотя до точки минимума еще может быть очень далеко. Естественное усовершенствование алгоритма состоит в следующем. После срабатывания критерия останова целесообразно построить над центром тяжести сжавшегося симплекса новый, размеры которого соответствуют исходному симплексу. Пусть координаты центра тяжести сжавшегося симплекса образуют вектор
/>.
Найдем теперь координаты точки />такой, что центр тяжести симплекса с длиной ребра, равной t, использующего вершину />в качестве начальной, совпадал бы с />. Матрица координат указанного симплекса имеет вид
/>(2.1)
Координаты центра тяжести этого симплекса образуют вектор
/>
Теперь координаты точки />найдем из равенства />=/>, откуда
/>
где />
Подставляя вычисленные значения /> в выражение (2.1), получим требуемый симплекс, используя который продолжим процедуру поиска минимума. С другой стороны, для продолжения процедуры в качестве начальной точки может быть использован центр тяжести «сжавшегося» симплекса. Возникающее при этом смещение нового симплекса относительно сжавшегося (точки предполагаемого останова) во многих случаях может даже оказаться полезным. Эту процедуру считаем законченной, если после очередного сжатия алгоритм приведет в точку, расстояние от которой до точки предыдущего сжатия />не превосходит некоторого достаточно малого />.
2.2 Градиентный метод с дроблением шага
Большей эффективностью обладают итерационные процедуры, в которых приближение к минимуму осуществляется сразу по всем переменным. При этом задача состоит в нахождении последовательности векторов />таких, что
/>(2.2)
Методы построения таких последовательностей называют методами спуска. Пусть />Поставим задачу отыскания последовательности />., сходящейся к />.
Выберем произвольным образом точку />, направление />и сконструируем луч
/>. (2.3)
Рассмотрим вопрос о выборе направления />, обеспечивающего (2.2). Для этого изучим поведение />вдоль луча />. Имеем />
Введем
/>(2.4)
Здесь />
В соответствии с (2.3)
/>
Тогда />
Вычислим/>(2.5)
Теперь, чтобы для любого />обеспечить отрицательность (2.5), достаточно положить />, где />произвольная положительно определенная />матрица. Тогда продолжение
--PAGE_BREAK--
/>
При этом/>(2.6)
Выбрав каким-либо образом />, получим />Затем аналогично рассчитаем />
Общее рекуррентное соотношение имеет вид :
/>(2.7)
Различные варианты градиентных процедур отличаются друг от друга способом выбора />.
Полученное соотношение (2.7) обеспечивает построение последовательности точек />, сходящейся к точке />, минимизирующей />. Понятно, что каждая из точек этой последовательности может рассматриваться как некоторое приближение к точке минимума />, положение которого, вообще говоря, остается неизвестным в ходе всей процедуры спуска. Поэтому для всех таких процедур принципиальной остается проблема останова. В вычислительной практике часто используются следующие критерии останова:
/>(2.8)
/>(2.9)
где />и />-некоторые достаточно малые числа .
Понятно, что критерий (2.8) хорош в тех случаях, когда функция />в окрестности минимума, используя ранее введенную классификацию, имеет характер «глубокой» впадины. С другой стороны, если функция />ведет себя как «пологое плато», то более предпочтительным является критерий (2.9).Аналогом критерия (2.8) является другое часто применяемое правило останова :
/>, (2.10)
использующее необходимое условие экстремума функции.Очевидным недостатком критериев (2.8)-(2.10) является то, что их качество существенно зависит от абсолютных значений величины />и компонентов векторов />,/>.Более универсальными являются относительные критерии :
/>(2.11)
/>(2.12)
/>(2.13)
Заметим, что очень часто на практике используются составные критерии, представляющие собой линейную комбинацию критериев (2.11)-(2.13), например,
/>
/>
Иногда применяют другой вариант построения составного критерия :
/>
При реализации градиентного метода с дроблением шагав качестве />выбирают единичную матрицу, то есть
/>
а длину шага определяют путем проверки некоторого неравенства. При этом основное рекуррентное соотношение (2.7) приобретает вид :
/>
Ясно, то если />, выбирать достаточно малым, то это обеспечит убывание />, но потребуется весьма большое число шагов. Если же неосторожно выбрать /> большим, то можно проскочить минимум, а это опасно в связи с возможным осциллированием. Для выбора шага используется правило Голдстейна-Армийо :
а) /> (2.14)
б) /> (2.15)
Выполнение условия а) обеспечивает выбор /> не слишком большим. Выполнение условия б) не дает возможность выбрать /> слишком малым.
Практическая процедура строится следующим образом. Выбирается начальная точка />и некоторое начальное значение />, проверяется (2.14) и, если оно выполняется, то делается шаг в направлении />В новой точке />вычисляется градиент />и вновь проверяется условие (2.14). В случае его удовлетворения продвижение к минимуму продолжается с тем же шагом. Если же оно не удовлетворяется, то параметр />, определяющий длину шага, делят пополам до тех пор, пока это неравенство не будет выполнено. Затем выполняется очередной шаг. Процедура продолжается до выполнения критерия останова.
РЕШЕНИЕ ЗАДАЧИ МИНИМИЗАЦИИ ДЛЯ КАЖДОГО ИЗ МЕТОДОВ
Метод Нелдера-Мида
Построим симплекс состоящий из 3-х вершин. Длину ребра t возьмем равной 1 .
Начальные координаты симплекса :
/>
Проводим сортировку по значениям функции для поиска точки с наименьшей функцией. Далее записываем симплекс таким образом, чтобы первая точка была лучшей, а каждая последующая – хуже.
Для осуществления оптимизации вычислим новую точку как отражение самой «плохой» вершины относительно центра тяжести симплекса. Формула для вычисления новой точки:
/>
Затем, после сравнения значения функции в новой точке со значениями функции в остальных трех, а также после осуществления одного из четырех действий (замены, сжатия, растяжения и редукции), строится новый симплекс.
Одно из четырех действий, указанных выше, выполняется в соответствии с значением функции в новой точке, по отношению к значению функции в старых точках.
Замена происходит в случае, если новая точка лучше чем лучшая.
Если выполняется условие />, то при этом реализуется отражение. Точка />заменяет />.
При выполнении условия />осуществляется сжатие и отыскивается точка />:
/>
Параметр />принимается равным 0,5. Точка />заменяет />. Таким образом полученная точка заменяет самую «плохую»
Если новая точка окажется самой «плохой», необходимо осуществить редукцию (уменьшение размера симплекса путем приближения всех его вершин к лучшей вершине)
После выполнения указанных действий проверяется параметр останова. В случае, если он признан большим, чем выбранное значение точности, действия повторяются снова. Параметр останова рассчитывается по формуле :
/>
/>
Результат работы метода представлен в таблице 3.1
Таблица 3.1 – Решение задачи минимизации при помощи метода Нелдера-Мида
Номер итерации
Х1
Х2 продолжение
--PAGE_BREAK--
Функция
Параметр останова
1
0,4066667
0,4066667
45,631123492267
14,5885289
2
0,4433333
0,2683333
29,870063661634
2,8471538
3
0,3141667
0,2704167
16,456883364840
0,8308005
4
0,2495833
0,2714583
13,667862520021
0,3301516
5
0,2194792
0,2030729
12,662220410942
0,1540974
6
0,1796615
0,1864974
12,281326901893
0,0870517
7
0,1546549
0,1481608
12,136891733007
0,0558708
8
0,1284945
0,1302889
12,072845463097
0,0394655
9
0,1094511
0,1066526
12,044325208099
0,0355389
10
0,0380868
0,0472725
12,032057545239
0,0204381
11
0,0107240
0,0206094
12,021017539213
0,0124410
12
0,0217244
0,0287886
12,011093940034
0,0130068
13
-0,0220008
-0,0163585
12,008732867306
0,0089109
14
-0,0274319
-0,0235556
12,005248404276
0,0053110
15
-0,0178584
-0,0140681
12,003293104515
0,0042019
16
-0,0191470
-0,0189750
12,002069416305
0,0030794
17
-0,0146824
-0,0154579
12,001121615618
0,0025320
18
-0,0132441
-0,0133520
12,000655246493
0,0026725
19
-0,0028766
-0,0042119
12,000504634754
0,0015212
20
0,0004344
-0,0008739
12,000339347268
0,0009248
21
-0,0013297
-0,0023245
12,000183034613
0,0009948
22
0,0035282
0,0029010
12,000137117579
0,0007582
23
0,0038607
0,0034821
12,000078476732
0,0004900
24
0,0027293
0,0023210
12,000050320679
0,0004156
25
0,0022628
0,0023222
12,000031684386
0,0002830
26
0,0015804
0,0017419
12,000017894979
0,0002411
27
0,0015265
0,0015966
12,000009969113
0,0002705
28
0,0001079
0,0002907
12,000008036464
0,0001594
29
-0,0002737
-0,0001084
12,000005403290
0,0000921
В результате решения задачи минимизации с помощью метода Нелдера-Мида получено следующее значение функции: />. Данный оптимум достигается в точке />. Этот метод позволяет найти минимум (при начальной точке Х (1; 1)) за 29 итераций при точности решения />. При этом параметр останова равен 0,0000921.
Градиентный метод с дроблением шага
Для реализации процедуры необходимо вычислить градиент:
/>
В процедуре используется критерий останова, который вычисляется по формуле:
/>,
где E – заданная точность решения (в данной задаче E=/>).
Результат работы метода представлен в таблице 3.2
Вследствие того, что таблица содержит 1263 итерации, целесообразно предоставить первые и последние 25 итераций. продолжение
--PAGE_BREAK--
Таблица 3.2 – Решение задачи минимизации при помощи градиентного метода
Номер итерации
Х1
Х2
Функция
Параметр останова
1
0,992187500
0,976562500
14,872248322711100
5,725771436
2
0,972112596
0,966700991
14,755778561425900
5,391343315
3
0,960252606
0,949298075
14,647453457158200
5,170831157
4
0,944120479
0,937143394
14,545808827169400
4,999364954
5
0,931250704
0,922455245
14,450015755630300
4,851038521
6
0,917052669
0,909905567
14,359522419103900
4,715343849
7
0,904265341
0,896648294
14,273894939963900
4,588117156
8
0,891210499
0,884368998
14,192768112137200
4,467486611
9
0,878869537
0,872030350
14,115817843495700
4,352565782
10
0,866628626
0,860230552
14,042753034754000
4,242801681
11
0,854831609
0,848589700
13,973308662686200
4,137814211
12
0,843250897
0,837314037
13,907242987828300
4,037283606
13
0,832001542
0,826261206
13,844334505896600
3,940936337
14
0,820995553
0,815497743
13,784380045189000
3,848521743
15
0,810266979
0,804966957
13,727192808899800
3,759812059
16
0,799778396
0,794686358
13,672600853099300
3,674595835
17
0,789535800
0,784630345
13,620445636362400
3,592677880
18
0,779520366
0,774799711
13,570580790710000
3,513876598
19
0,769728817
0,765180416
13,522870992857600
3,438023378
20
0,760149472
0,755767918
13,477190974079800
3,364961115
21
0,750776352
0,746552749
13,433424623226000
3,294543452
22
0,741600798
0,737528983
13,391464187766000
3,226633778
23
0,732616368
0,728689198
13,351209552529500
3,161104506
24
0,723815911
0,720027406
13,312567592195300
3,097836320
25
0,715193248
0,711537292
13,275451586431100
3,036717546
1239
0,000042461
0,000042461
12,000000003605800
0,000120097
1240
0,000042129
0,000042129
12,000000003549700
0,000119159
1241
0,000041800
0,000041800
12,000000003494500
0,000118228
1242
0,000041473
0,000041473
12,000000003440100
0,000117304
1243
0,000041149
0,000041149
12,000000003386500
0,000116388
1244
0,000040828
0,000040828
12,000000003333800
0,000115479
1245
0,000040509
0,000040509
12,000000003281900 продолжение
--PAGE_BREAK----PAGE_BREAK----PAGE_BREAK----PAGE_BREAK----PAGE_BREAK----PAGE_BREAK----PAGE_BREAK----PAGE_BREAK----PAGE_BREAK----PAGE_BREAK----PAGE_BREAK----PAGE_BREAK----PAGE_BREAK----PAGE_BREAK----PAGE_BREAK----PAGE_BREAK--
0,000001077
1841
0,000000378
0,000000378
12,000000000000300
0,000001069
1842
0,000000375
0,000000375
12,000000000000300
0,000001061
1843
0,000000372
0,000000372
12,000000000000300
0,000001052
1844
0,000000369
0,000000369
12,000000000000300
0,000001044
1845
0,000000366
0,000000366
12,000000000000300
0,000001036
1846
0,000000363
0,000000363
12,000000000000300
0,000001028
1847
0,000000361
0,000000361
12,000000000000300
0,000001020
1848
0,000000358
0,000000358
12,000000000000300
0,000001012
1849
0,000000355
0,000000355
12,000000000000300
0,000001004
1850
0,000000352
0,000000352
12,000000000000200
0,000000996
Данные по количеству итераций и заданным точностям для градиентного метода сведены в таблицу 5.14
Таблица 5.14 — Зависимость числа итераций от точности
Точность
Количество итераций
0,1
382
0,01
676
0,001
969
0,0001
1263
0,00001
1556
0,000001
1850
/>
Рисунок 5.2 – Графическое представление зависимости количества итераций N от точности E для градиентного метода.
Таким образом, анализируя полученные зависимости можно сделать вывод о том, что метод Нелдера-Мида является более эффективным. Так же следует отметить, что градиентный метод быстро приближается к экстремуму, когда текущая точка находится далеко от него, и резко замедляется вблизи экстремума.
Следует заметить, что эффективность применения методов оптимизации прежде всего обусловлена видом функции.
6. ЗАКЛЮЧЕНИЕ
В курсовой работе произведена минимизации функции />с помощью метода оптимизации нулевого порядка – метода Нелдера-Мида и метода оптимизации первого порядка – градиентного метода с дроблением шага.
В результате решения задачи минимизации с помощью метода Нелдера-Мида получено следующее значение функции: />. Данный оптимум достигается в точке />. Этот метод позволяет найти минимум (при начальной точке Х (1; 1)) за 29 итераций при точности решения />. При этом параметр останова равен 0,0000921.
В результате реализации градиентного метода минимальное значение функции составляет />. Данный оптимум достигнут в точке />. Этот метод позволяет найти минимум (при начальной точке Х(1;1)) за 1263 итерации при точности решения />. При этом параметр останова равен 0,000099491.
Для каждого из методов была установлена зависимость числа итераций от заданной точности. Анализируя полученные результаты, можно сделать вывод о том, что по числу итераций более эффективным является метод Нелдера-Мида. Однако следует отметить, что эффективность этих методов может изменяться в зависимости от выбора начального приближения и вида функции. Следует также учесть, что градиентный метод может быть непригоден в тех случаях, если расчет производных вызывает затруднение.
7. ПРИЛОЖЕНИЕ
В таблицах представлены координаты точек, образующих линии уровня
/>
/>
/>
/>
/>
/>
В настоящем приложении представлена реализация программного кода для каждого из методов оптимизации. Используемый язык программирования – VisualStudio C# 2005. продолжение
--PAGE_BREAK--
Градиентный метод с дроблением шага
namespace GradientL
{public partial class Form1: Form
{public Form1()
{InitializeComponent();}
public static string[] str = new string[100000];
struct Tk
{public double x1, x2;
public Tk(double X, double Y)
{x1 = X;
x2 = Y;}
public static Tk operator /(Tk v1, double q)
{return new Tk(v1.x1 / q, v1.x2 / q);}
public static Tk operator *(Tk v, double d)
{return new Tk(v.x1 * d, v.x2 * d);}
public static Tk operator *(Tk v1, Tk v2)
{return new Tk(v1.x1 * v2.x1, v1.x2 * v2.x2);}
public static Tk operator -(Tk v1, Tk v2)
{return new Tk(v1.x1 — v2.x1, v1.x2 — v2.x2);}
public static Tk operator +(Tk v1, Tk v2)
{return new Tk(v1.x1 + v2.x1, v1.x2 + v2.x2);}
public static double Dist(Tk v1, Tk v2)
{return Math.Sqrt((v1.x1 — v2.x1) * (v1.x1 — v2.x1) + (v1.x2 — v2.x2) * (v1.x2 — v2.x2));}
public override string ToString()
{return "(" + this.x1.ToString(«f5») + ";" + this.x2.ToString(«f5») + ")";}}
class Pr
{public static double f(Tk c)
{return 12 + c.x1 * c.x1 + (1 + c.x2 * c.x2) * c.x2 * c.x2 + (c.x1 * c.x1 * c.x2 * c.x2 + 100) * (c.x1 — c.x2) * (c.x1 — c.x2);}
static Tk gradient(Tk c)
{Tk N = new Tk(2 * c.x1 + 2 * c.x1 * c.x2 * c.x2 *
( c.x1 — c.x2)*(c.x1 — c.x2) + 2 * (c.x1 * c.x1 * c.x2 * c.x2 + 100) * (c.x1 — c.x2),
2 * c.x2*c.x2*c.x2+2*c.x2*(1+c.x2*c.x2)+
2*c.x2*c.x1*c.x1*(c.x1-c.x2)*(c.x1-c.x2)-2*(c.x1-c.x2)*
(c.x1*c.x1*c.x2*c.x2+100));
return N;}
public static double Dl(Tk c)
{return Math.Sqrt(c.x1 * c.x1 + c.x2 * c.x2);}
public static void Tr(double eps, ref Tk ca, out double fn, out int i)
{Tk cb = new Tk(1, 1), st = new Tk(0.5, 0.5);
Tk step = new Tk(1, 1), eq; i = 0;
do
{while (true)
{cb = ca — step * gradient(ca);
eq = st * step * gradient(cb) * gradient(cb);
if (f(cb — step * gradient(cb)) >= (f(cb) — Dl(eq)))
{ step.x1 /= 2;
step.x2 /= 2;}
else break;}
fn = f(ca);
i++;
str[i] = String.Format("{0}" + ") " + "{1}" + "; " +
"{2}" + "; " + "{3}" + ".", i.ToString(), ca.ToString(), fn.ToString(«f6»), Dl(gradient(cb)).ToString(«f6»));
ca = cb;}
while (Dl(gradient(cb)) >= eps);
fn = f(cb);}}
private void button1_Click(object sender, EventArgs e)
{listBox1.Items.Clear();
double Et = Convert.ToDouble(textBox3.Text);
double fn;
int j;
Tk mas = new Tk(Convert.ToDouble(textBox1.Text), Convert.ToDouble(textBox2.Text));
Pr.Tr(Et, ref mas, out fn, out j);
Min.Visible = true;
Min.Text = String.Format("{0}" + "; " + "{1}" + "; " +
"{2}", mas.ToString(), fn.ToString(), j.ToString());
for (int i = 1; i
listBox1.Items.Add(str[i]);}
private void Form1_Load(object sender, EventArgs e){}}}
Метод Нелдера-Мида
namespace Nelder_Method
{public partial class Form1: Form
{public Form1()
{InitializeComponent();}
static double Al = 1.0;
static double Bt = 0.5;
static double Gm = 2.0;
static int n=0;
static string[] op = new string[1000];
const int cap = 2;
struct Tk
{public double x1, x2;
public Tk(double X, double Y)
{x1 = X;
x2 = Y;}
public static Tk operator /(Tk v1, double q)
{return new Tk(v1.x1 / q, v1.x2 / q);}
public static Tk operator *(Tk v, double d)
{return new Tk(v.x1 * d, v.x2 * d);}
public static Tk operator *(Tk v1, Tk v2)
{return new Tk(v1.x1 * v2.x1, v1.x2 * v2.x2);}
public static Tk operator -(Tk v1, Tk v2)
{return new Tk(v1.x1 — v2.x1, v1.x2 — v2.x2);}
public static Tk operator +(Tk v1, Tk v2)
{return new Tk(v1.x1 + v2.x1, v1.x2 + v2.x2);}
public static double Dist(Tk v1, Tk v2)
{return Math.Sqrt((v1.x1 — v2.x1) * (v1.x1 — v2.x1) + (v1.x2 — v2.x2) * (v1.x2 — v2.x2));} продолжение
--PAGE_BREAK--
public override string ToString()
{return "(" + this.x1.ToString(«f5») + ";" + this.x2.ToString(«f5») + ")";}}
class Cnt
{public static double function(Tk c)
{return 12 + c.x1*c.x1 + (1+c.x2*c.x2)*c.x2*c.x2 + (c.x1*c.x1*c.x2*c.x2+100)*(c.x1-c.x2)*(c.x1-c.x2);}
public static void Pr(ref Tk[] c, ref double[] ot)
{double fir; Tk tk;
for (int k = 1; k
for (int l = k; l >= 1; l--)
if (ot[l — 1] > ot[l])
{fir = ot[l];
tk = c[l];
ot[l] = ot[l — 1];
c[l] = c[l — 1];
ot[l — 1] = fir;
c[l — 1] = tk;}
else break;}
public static bool Ostanov(Tk[] w, double E, double n, Tk c, out double Ost)
{double Lp;
double d = 0.5;
double p1 = 0;
Tk p2 = new Tk(0, 0);
for (int i = 0; i
{p1 += (function(w[i]) — function(c)) * (function(w[i]) — function(c));
p2 += (w[i] — c) * (w[i] — c);}
Lp = Math.Sqrt(p2.x1 * p2.x1 + p2.x2 * p2.x2);
Ost = d * (Math.Sqrt((1 / (n + 1)) * p1)) + (1 — d) * (Math.Sqrt((1 / (n + 1)) * Lp));
if (Ost
return true;
else return false;}
public static double Met(Tk[] c, double tchn)
{double[] f = new double[cap + 1];
double val1=0, val2=0, val3 = 0, val4, val5, val6, val7;
Tk sim1, sim2, sim3, sim4, sim5, sim6, sim_cen, sim7;
sim_cen.x1 = sim_cen.x2 = 0;
int i;
double J1;
bool flag;
for (i = 0; i
f[i] = function(c[i]);
while (!Ostanov(c, tchn, n, sim_cen, out J1))// Проверка на условие выхода
{n++;
// Шаг 1. Сортировка
Pr(ref c, ref f);
sim1 = c[cap]; val1 = f[cap];
sim2 = c[cap — 1]; val2 = f[cap — 1];
sim3 = c[0]; val3 = f[0];
// Шаг 2. Вычисление центра тяжести симплекса
sim_cen.x1 = sim_cen.x2 = 0;
for (i = 0; i
sim_cen = sim_cen + c[i];
sim_cen = sim_cen / cap;
// 3Шаг. Отражение
sim4 = sim_cen * (1 + Al) — sim1 * Al; val4 = function(sim4);
// Шаг 4.
if (val4
{ // Шаг 4a.
sim5 = sim_cen * (1 — Gm) + sim4 * Gm;
val5 = function(sim5);
if (val5
{c[cap] = sim5;
f[cap] = val5;}
else
{c[cap] = sim4;
f[cap] = val4;}}
if ((val3
{ // Шаг 4.b
c[cap] = sim4;
f[cap] = val4;}
flag = false;
if ((val1 >= val4) && (val4 > val2))
{ // Шаг 4c.
flag = true;
val7 = val1;
sim7 = sim1;
c[cap] = sim4;
f[cap] = val4;
sim4 = sim7;
val4 = val7;}
// Шаг 4d.
if (val4 > val1) flag = true;
if (flag)
{ // Шаг 5. Сжатие
sim6 = sim1 * Bt + sim_cen * (1 — Bt);
val6 = function(sim6);
if (val6
{ // Шаг 6.
val7 = val1;
sim7 = sim1;
c[cap] = sim6;
f[cap] = val6;
sim6 = sim7;
val6 = val7;}
else
{ // Шаг 7. Глобальное сжатие
for (i = 0; i
c[i] = sim3 + (c[i] — sim3) / 2;}}
op[n — 1] = Convert.ToString(n) + "; " + sim1.ToString() +
"; " + sim2.ToString() + "; " + sim3.ToString();}
return (val3 + val1 + val2) / 3;}}
private void button1_Click(object sender, EventArgs e)
{Tk ta = new Tk(0, 0);
Tk tb = new Tk(0.26, 0.96);
Tk tc = new Tk(0.96, 0.26);
Tk[] t = new Tk[3] { ta, tb, tc };
listBox1.Items.Clear();
n = 0;
op = new string[200];
double eps1 = Convert.ToDouble(textBox2.Text);
label4.Text = Cnt.Met(t, eps1).ToString(«f5») + "; " + Convert.ToString(n) + ".";
for (int i = 0; i
listBox1.Items.Add(op[i]);}
private void Form1_Load(object sender, EventArgs e){}}
8. СПИСОК ИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫ
Агуров П.В. C# в подлиннике (программирование на языке С#) – Петербург, 2006
Агуров П.В. Сборник рецептов по C# — Петербург,2006
Банди Б. Методы оптимизации – Москва, 1988
Базара М, Шетти К. Нелинейное программироваине. Теория и алгоритмы – М.: Мир, 1988
Поляк Б.Т. Введение в оптимизацию. — М.: Наука, 1983
Раскин Л.Г. Математическое программирование: Учебное пособие – Харьков: НТУ «ХПИ», 2002
Рихтер Д. Программирование на платформе Microsoft. NET Freamework для профессионалов – М.Microsoft Press, 2003
Серая О.В. Методические указания для проведения лабораторных работ по курсу «Математическое программирование» — Харьков: НТУ «ХПИ», 2003
Сухарев А.Г., Тимохов А.В Курс методов оптимизации – М.: Наука, 1986
Химмельблау Д. Прикладное нелинейное программирование М.: Мир, 1989