Методы оптимизации организационно-технических систем

Московский авиационный институт
(государственный технический университет)
–––––––––––––––
Аэрокосмический факультет
––––––––––––––––
кафедра «системный анализ и управление»

Методы оптимизации
организационно-технических систем

Учебное пособие для выполнения курсовой работы

УТВЕРЖДЕНО

на заседании кафедры 604,

«Системный анализ и управление»,

протокол №13, 20.12.2007

Москва, 2007г.

содержание

Введение.. 3

3. Содержание и требования к выполнению курсовой работы 4

3.1. Содержание курсовой работы.. 4

3.2. Общие требования к проведению и оформлению курсовой работы.. 7

2. Методическое Обеспечение курсовой работы... 10

2.1. Методика аналитического решения задачи условной оптимизации с ограничениями типа неравенств.. 10

1. Формирование функции Лагранжа. 10

2. Применение необходимых условий (НУ) в форме Куна и Таккера для определения условных стационарных точек для задачи (1.1, 1.2). 10

3. Исключение всех стационарных точек, не удовлетворяющих пассивным ограничениям. 11

4. Исключение стационарных точек, не удовлетворяющих условиям неотрицательности множителей Лагранжа. 12

5. Проверка оставшихся стационарных точек на достаточные условия локального минимума функции. 12

6. Определение условного глобального минимума. 13

2.2. Методические рекомендации по численному решению задачи условной оптимизации с ограничениями типа неравенств.. 15

3. Варианты Заданий к курсовой работе.. 21

3.1. Задания по аналитической части курсовой работы.. 21

3.2. Задания по методам численной оптимизации для выполнения второй части курсовой работы.. 27

4. рекомендации по формированию заключения и Приложений к курсовой работе.. 32

Введение

Учебное пособие предназначено для студентов, выполняющих курсовую работу по дисциплине: «Методы оптимизации организационно-технических систем», читаемой в рамках специальности 0722: «Моделирование и исследование операций в организационно – технических системах».

Целями курсовой работы являются:

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

приобретение навыков применения широкого спектра современных методов математического программирования, включая детерминированные методы нулевого, первого и второго порядков, а также методы поиска экстремумов целевых функций, учитывающие элементы случайности;

развитие способностей к проведению аналитических исследований на примере сравнительного анализа свойств сходимости различных численных методов условной оптимизации целевых функций;

умение ставить задачу, конкретизировать методику ее решения, формировать и разрабатывать программное обеспечение, а также формулировать выводы по результатам проделанной работы;

накопление опыта объектно-ориентированного программирования.

В пособии описано содержание выполнения курсовой работы, сформулированы требования к ней, представлены варианты заданий, приведены теоретические сведения, необходимые для выполнения работы.

1. Содержание и требования к выполнению курсовой работы

1.1. Содержание курсовой работы

Курсовая работа состоит из двух логически связанных частей, соответствующих содержанию лекций, читаемых по дисциплине «Методы оптимизации организационно-технических систем».

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

f (x)

(1.1)

Где х – вектор аргументов (параметров), имеющий в общем случае размерность [n´1], f(x) – скалярная унимодальная дифференцируемая функция, Х – множество допустимых значений аргументов х, заданное совокупностью ограничений типа неравенств:

(1.2)

Где gj(x) - дифференцируемая функция векторного аргумента, j - число ограничивающих функций.

Задача (1.1) считается поставленной корректно, если ограничения gj(x)≤0, j=1,…,m совместимы и образуют непустое множество Х , на котором существует целевая функция f(x) .

Аналитическое решение задачи условной оптимизации следует найти с помощью необходимых условий оптимальности – теоремы Куна и Таккера. Существо этой теоремы и построенный на ее основе алгоритм решения поставленной задачи излагаются в разделе 2.1.

В результате аналитического решения задачи типа должен быть получен набор локальных условных минимумов, из которых путем сравнения выбирается решение. Кроме того, полученное решение необходимо сопроводить графической иллюстрацией т. е. построить линии уровня целевой функции, ограничения и найденных точек глобального и локальных минимумов. Для графических построений рекомендуется использовать доступные математические пакеты, например MatCAD, MatLab и др.

Во второй части работы та же самая задача должна быть решена с помощью численных методов безусловной оптимизации. Для этого задачу условной оптимизации следует свести к безусловной с помощью метода штрафных функций.

Перечень методов безусловной оптимизации определяется индивидуально для каждого задания. В данной работе рассматриваются численные методы безусловной оптимизации, приведенные в классификации (см. раздел 2.2).

В процессе решения поставленной задачи с помощью задаваемых численных методов должны быть решены следующие подзадачи:

1.  Разработка алгоритмов (блок-схем) и подпрограмм численных методов безусловной оптимизации, определенных индивидуальным заданием;

2.  Разработка основной программы, в которой задаются все исходные данные, связанные с конкретной задачей условной оптимизации и фиксируются параметры соответствующих численных методов безусловной оптимизации;

3.  Разработка подпрограммы, реализующей метод «штрафных функций», из которой происходит непосредственный вызов подпрограммы конкретного численного метода безусловной оптимизации;

4.  Отладка и тестирование сформированной программы численного решения конкретной задачи условной оптимизации одним из заданных численных методов безусловной оптимизации (эта задача повторяется для каждого заданного метода отдельно);

5.  Решение задачи условной оптимизации одним из заданных численных методов безусловной оптимизации (эта задача повторяется для каждого заданного метода отдельно);

6.  Исследование влияния варьируемых параметров методов безусловной оптимизации (задаваемых в основной программе) на скорость сходимости к искомому решению, фиксируемому с заданной точностью;

7.  Проведение сравнительного анализа заданных методов безусловной оптимизации по скоростям сходимости к искомому решению;

8.  Написание выводов по проделанной работе.

Основные рекомендации по выполнению курсовой работы даются в разделе 2.

1.2. Общие требования к проведению и оформлению курсовой работы

Каждый студент получает индивидуальный вариант задания, в который включаются:

по части I работы - конкретные виды целевой функции, подлежащей минимизации, и ограничений типа неравенств;

по части II работы – численные методы безусловной оптимизации и методы одномерной оптимизации (если они входит в задание), с помощью которых необходимо решить (поочередно) поставленную задачу.

Процесс проведения курсовой работы строго регламентирован и должен выполняться согласно плану, представленному в табл 1.1. При этом задание по части II работы выдается только после выполнения части I.

Таблица 1.1

№ п/п	содержание	продолжитель-ность	основная литература
1	постановка конкретной задачи, оформление раздела в отчет по КР	1 неделя	конспект лекций
2	Изучение методики аналитического решения задачи, оформление раздела в отчет по КР	1 неделя	[1, 2], конспект лекций и семинарских занятий
3	решение задачи в черновом виде	1 неделя	конспект семинарских занятий

Продолжение Таблицы 1.1

4	оформление части I КР, построение геометрической интерпретации результатов аналитического решения задачи	1 неделя	конспект семинарских занятий
5	Изучение методов численного решения задачи (согласно заданию), оформление раздела в отчет по КР	1 неделя	[1, 2, 3], конспект лекций и семинарских занятий
6	Формирование алгоритмов (блок-схем), программирование и отладка программного обеспечения	1,5 недели	[1, 2, 3], конспект лекций и семинарских занятий
7	Проведение численных исследований с помощью созданного программного обеспечения	1,5 недели
8	Построение геометрической интерпретации результатов численного решения задачи и оформление части II отчета по КР	0,5 недели
9	Анализ результатов и формулировка выводов по КР	0,5 недели

Как видно из плана проведения КР ее реализация рассчитана на ~ 9 недель, что составляет по продолжительности около 55 % семестра.

Отчет по КР должен быть оформлен согласно действующему ГОСТу на оформление научно-технических отчетов и удовлетворять следующим требованиям.

·  Отчет по КР должен иметь титульный лист, на котором должны быть указаны: дисциплина, в рамках которой выполняется КР, учебное заведение, факультет и кафедра, где выполнялась КР, автор и руководители КР, а также год выполнения КР;

·  Вслед за титульным листом Отчет по КР должен иметь лист - «Задание на КР», на котором компактно излагаются индивидуальные целевые функции, ограничения и численные методы, задаваемые преподавателем, контролирующим выполнение КР;

·  Вслед за листом «Задание на КР» должно следовать Содержание отчета по КР;

·  Часть I отчета по КР должна иметь раздел, посвященный общей и частной постановке задачи с привлечением принятой в данной дисциплине терминологии и математических обозначений;

  должна иметь раздел, посвященный методике и алгоритму аналитического решения поставленной задачи (формализм Куна и Таккера);

  должна иметь раздел, в котором описано (детально) конкретное решение поставленной задачи, оформленное согласно алгоритму аналитического решения;

·  Часть II отчета по КР должна иметь раздел, посвященный описанию методики решения задач условной оптимизации численными методами безусловной оптимизации с помощью метода «Штрафных функций»;

  должна иметь раздел, посвященный описанию алгоритмов (блок-схем) конкретных численных методов, определенных заданием;

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

·  В заключении КР должны быть сформулированы выводы по проделанной исследовательской работе с учетом сравнительного анализа заданных численных методов безусловной оптимизации;

·  В Приложении к КР должны быть помещены: распечатки модулей программного обеспечения, соответствующие блок-схемам заданных численных методов; результаты тестирования методов безусловной оптимизации; предложения по повышению эффективности заданных численных методов оптимизации.

2. Методическое Обеспечение курсовой работы

2.1. Методика аналитического решения задачи условной оптимизации с ограничениями типа неравенств

Для аналитического решения задачи типа (1.1, 1.2) предлагается использовать методику, в основе которой лежит теорема Куна и Таккера (H. W. Kuhn, A. W. Tucker) [1], представляющая собой в общем случае необходимые условия минимума целевой функции при наличии ограничений типа неравенств на множество допустимых значений векторного аргумента функции (см.(1.2)). В рассматриваемом приложении эту методику целесообразно представить в виде следующего расширенного алгоритма.

1. Формирование функции Лагранжа.

Исходя из обозначений принятых в постановке (1.1, 1.2), функция Лагранжа будет иметь вид:

F(x, l) = f (x) + lT g(x)

(2.1)

где l - вектор множителей Лагранжа размерности [m´1], соответствующей количеству ограничений gj(x)≤0, j=1,…,m .

2. Применение необходимых условий (НУ) в форме Куна и Таккера для определения условных стационарных точек для задачи (1.1, 1.2).

В компактной форме для случая минимизации функции условия Куна и Таккера могут быть записаны в виде:

(2.2)

Где - координаты стационарных точек.

При рассмотрении конкретных задач, в которых количестве ограничений более одного, то есть при m >1 возможны различные сочетания активных и пассивных ограничений:

gi(x)=0, i Î I1 ; gj(x)<0, j Î I2

(2.3)

Где I1 – множество номеров индексов активных ограничений, I2 – множество номеров индексов пассивных ограничений (сумма элементов этих множеств всегда равна m).

Очевидно, что в этих случаях НУ (2.2) должны быть применены при всех возможных сочетаниях активных и пассивных ограничений, включая крайние случаи:

когда множество номеров активных ограничений I1 пусто (l = 0 ), то есть фактически рассматривается задача безусловной оптимизации;

и когда количество активных ограничений, то есть количество элементов множества I1 равно размерности вектора х – [n´1] (так называемые «угловые» точки), тогда эта точка фиксируется активными ограничениями и не допускает вариации целевой функции (имеется ввиду корректная постановка задачи (1.1, 1.2)).

В результате применения НУ для всех возможных сочетаний активных ограничений будут получены варианты стационарных точек - , в которых могут оказаться условные локальные минимумы и, в конечном итоге, - условный глобальный минимум, являющийся решением поставленной задачи.

3. Исключение всех стационарных точек, не удовлетворяющих пассивным ограничениям.

То есть:

gj()<0, j Î 1,m

(2.4)

4. Исключение стационарных точек, не удовлетворяющих условиям неотрицательности множителей Лагранжа.

Из оставшегося числа вариантов стационарных точек необходимо исключить все точки, не удовлетворяющие условиям неотрицательности соответствующих множителей Лагранжа - , в которых согласно НУ не могут находиться условные локальные минимумы целевой функции.

5. Проверка оставшихся стационарных точек на достаточные условия локального минимума функции.

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

Одним из широко распространенных вариантов ДУ нахождения в исследуемой стационарной точке условного локального минимума является положительная определенность матрицы Гессе, размера [n´n] (матрицы вторых частных производных) для функции Лагранжа F(х, l) по вектору х – [n´1].

H(x)(х, l) =

(2.5)

Известно, что матрица положительно определена, если составленная с ее помощью квадратичная форма положительно определена [1], то есть:

yTH(x)(х, l) y > 0

(2.6)

Где H(x)(х, l) - матрица Гессе (Гессиан) по вектору х; y – любой вектор с фиксированными значениями, размера [n´1].

Для проверки положительной определенности квадратичной формы (2.6) предлагается применить критерий Сильвестра [2, 4]. Суть его заключается в следующем.

Для того, чтобы квадратичная форма (2.6) была положительно определенной, необходимо и достаточно, чтобы матрица H(x)(х, l) имела все положительные угловые миноры, нарастающие вдоль главной ее диагонали, то есть были бы положительными определители матриц:

∆1 = h11> 0; ∆2 = > 0;…; ∆n =  > 0

(2.7)

Где hij – элементы матрицы Гессе H(x)(х, l) .

Таким образом, при подтверждении положительной определенности матрицы Гессе в стационарных точках, в которых согласно НУ возможно было нахождение условного локального минимума, то есть при  > 0 , такие стационарные точки переводятся в число точек условного локального минимума целевой функции f(x) при условиях gj(x) ≤ 0, j=1,…,m :

для номеров «s», удовлетворяющих НУ и ДУ

(2.8)

6. Определение условного глобального минимума.

Сравнение значений целевой функции f(x) в точках условного локального минимума и в «угловых» точках позволяет выявить условный глобальный минимум:

(2.9)

Где xугл – координаты «угловых» точек, определяемых n активными ограничениями из числа jÎ1,…,m (см. пункт 2).

Таким образом условный глобальный минимум целевой функции равняется f(xmin ).

В соответствии с требованиями к КР (см. раздел 1.2) полученный результат необходимо представить графически и прокомментировать его с помощью поясняющих подписей и отдельных пояснений, следующих после рисунка (масштаб рисунка должен выбираться из соображений его наглядности). Пример графического представления результата аналитического решения задачи типа (1.1, 1.2) изображен на рис. 2.1.

Рис	2.1

В частности, на рис. 2.1 изображены: целевая функция f(x) с помощью линий уровня C1, C2, C3, …., причем C1 < C2 < C3 и т. д.; ограничения gj ≤ 0, j =1,2,3 , выделяющие множество допустимых аргументов (параметров) - Х (запретные области условно заштрихованы); точки условного локального минимума определены номерами №1, №2, №3, №4, причем на рисунке видно, что точки №1 и №3 не удовлетворяют всем ограничениям gj ≤ 0 ; «угловые» точки: №5, №6, №7.

Как следует из рассмотренной выше методики в результате сравнения значений функций в точках условного локального минимума №2, №4 и в «угловых» точках №5, №6, №7 определяются координаты условного глобального минимума, которые на рисунке обозначены №2.

2.2. Методические рекомендации по численному решению задачи условной оптимизации с ограничениями типа неравенств

Численное решение задачи условной оптимизации с ограничениями типа неравенств должно осуществляться посредством нескольких методов с цель последующего сравнительного анализа соответствующих реализаций решения. Сравнение должно осуществляться как с точки зрения эвристических оценок показателей сходимости методов, так и с точки зрения затрат машинного времени на реализацию численного решения конкретной задачи с заданной точностью.

Выбор и фиксация вариантов численных методов безусловной оптимизации осуществляется исходя из их классификации (см. рис. 2.2).

Рис	2.2

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

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

Для численного поиска условного минимума целевой функции (1.1) при условиях (1.2) предлагается применить метод «Штрафных функций» [1, 2], позволяющий свести задачу условной минимизации к последовательности итеративно решаемых задач безусловной минимизации. Суть этого метода заключается в следующем.

На основе целевой функции формируется функция вида:

Φ(x, α) = f(x) + αТ s((g(x))

(2.10)

Где s(g(x)) – сложная функция вектора х, называемая функцией «штрафа» (или «штрафной» функцией), α – вектор коэффициентов «штрафа», размера [m´1].

Функция s(g(x)) должна иметь следующие свойства.

s((g(x)) =

(2.11)

То есть, если ограничения типа неравенств не нарушаются (g(x) < 0) , то функция «штрафа» не должна никак себя проявлять в функции (2.10), и если это ограничение нарушено, то с ростом этого нарушения должен расти «штраф» за него, вплоть до бесконечности. При этом в точках g(x) = 0 функция «штрафа» должна быть непрерывной справа.

Обоснованием для применения метода штрафных функций является принятие следующей принципиально важной гипотезы:

Предполагается, что последовательность аргументов решений задач безусловной оптимизации {x*i безусл}, i = 1, 2,….., а именно:

Φ(x, αi ) = [ f(x) + αi s((g(x))] = x*i безусл

(2.12)

стремится к решению задачи условной оптимизации (1.1, 1.2) при неограниченном росте последовательности коэффициентов «штрафа» {ai} , то есть:

x*i безусл (αi ) = x* усл Φ(x*i безусл (αi ), αi ) = f(x* усл)

(2.13)

Где x*i безусл – вектор безусловного минимума функции Φ(x, αi) , зависящий от конкретного значения коэффициента «штрафа» αi, x*усл - вектор координат условного минимума, соответствующего поставленной задачи.

Таким образом, согласно приведенной гипотезе алгоритм приближенного численного решения задачи (1.1, 1.2) должен включать следующие операции.

1)  Ввод в программу: конкретных целевой функции - f(x) и ограничений - g(x) < 0 .

2)  Определение и ввод в программу конкретной функции «штрафа» - s(g(x)) .

3)  Фиксация исходных значений коэффициентов «штрафа» - α0 и сопутствующих параметров (например, параметра итеративного роста коэффициентов «штрафа» и параметра допустимого числа итераций).

4)  Определение метода безусловной оптимизации.

5)  Фиксация параметров выбранного метода.

6)  Задание начального приближения вектора аргументов x(0) .

7)  Организацию с помощью программных средств «охватывающего» цикла перебора коэффициентов «штрафа» - αi , i = 1, 2, …. (с нарастанием до определенного значения).

8)  Организацию с помощью программных средств и в соответствии с выбранным методом безусловной оптимизации «внутреннего» цикла поиска минимума функции Φ(x, αi) для текущего значения αi и определение промежуточного значения x*i безусл (αi ). В случае применения в рамках заданного численного метода конкретной процедуры одномерной оптимизации, необходимо «внутри» этого цикла организовать еще один цикл - минимизации функции в заданном направлении.

9)  Проверка условий окончания процедуры поиска условного минимума целевой функции и в случае их выполнения – прекращение процедуры, в противном случае – назначение новых значений αi и x(0i) и переход к пункту 6 алгоритма (рекомендуется в качестве новых значений x(0i) выбирать последние значения этого вектора на предыдущей итерации «внутреннего» цикла, то есть - x(p)i-1 ).

Этот алгоритм может быть представлен в виде укрупненной блок-схемы (см. рис. 2.3).

Задание исходных данных (параметров, коэффициентов и др.)   вход
Рис	2.3

В качестве функции «штрафа» предлагается использовать следующую составную функцию.

s((g(x)) =

(2.14)

Где gj(x) одна из m функций ограничений.

В общем случае для каждой функции gj(x) должна быть определена своя функции «штрафа» - sj((gj(x)) типа (2.14). В результате функция Φ(x, α) приобретет более конкретный вид:

Φ(x, αi) = f(x) +  αij sj((gj(x))

(2.15)

Коэффициенты «штрафа» αij могут быть различны для каждого ограничения gj(x), однако, имея в виду абстрактность рассматриваемой задачи, они могут определяться одинаковой последовательностью значений {ai}, i = 1,2,…. Тогда (2.14) с учетом этого и (2.15) будет иметь вид:

Φ(x, αi) = f(x) +

(2.16)

Таким образом, в случае правильного подбора параметров используемых методов и рационального выбора последовательности коэффициентов «штрафа» {ai}, i = 1,2,…., значение которых увеличиваются с ростом номера последовательности i , каждое новое решение задачи на безусловный минимум функции Φ(x, αi), должно приближаться к решению задачи условной минимизации (1.1, 1.2).

3. Варианты Заданий к курсовой работе

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

3.1. Задания по аналитической части курсовой работы

Каждый вариант задания по аналитической части курсовой работы имеет индивидуальную постановку задачи типа (1.1, 1.2), включающую:

-  конкретный вид целевой функции – f(x1, x2) ;

-  несколько конкретных ограничений типа неравенств – gi (x1, x2) ≤ 0, i = 1,m.

вариант № 1

f(x1, x2)	gi (x1, x2) ≤ 0, i = 1,m
3(х1 – 1)2 + 9(х2 – 6)2	х1 +х2 - 3
-х1 - 2
-х2 - 1

вариант № 2

f(x1, x2)	gi (x1, x2) ≤ 0, i = 1,m
8(х1 – 1)2 + 2(х2 – 4)2	х1 +2х2 - 8
-х1 + 2
-х2 - 1

вариант № 3

f(x1, x2)	gi (x1, x2) ≤ 0, i = 1,m
5(х1 – 1)2 + 3(х2 – 3)2	х1 +3х2 - 9
-х1 + 3
-х2 - 2

вариант № 4

f(x1, x2)	gi (x1, x2) ≤ 0, i = 1,m
4(х1 – 1)2 + 16(х2 – 5)2	х1 +х2 - 3
-х1 - 1
-х2 - 3

вариант № 5

f(x1, x2)	gi (x1, x2) ≤ 0, i = 1,m
2(х1 – 5)2 + (х2 – 8)2	х1 + 2х2 - 6
-х1 - 3
-х2 - 4

вариант № 6

f(x1, x2)	gi (x1, x2) ≤ 0, i = 1,m
(х1 – 6)2 + 4(х2 – 3)2	3х1 + х2 - 6
-х1 – 2
-х2 – 1

вариант № 7

f(x1, x2)	gi (x1, x2) ≤ 0, i = 1,m
3(х1 – 5)2 + (х2 – 8)2	х1 + 3х2 - 6
-х1 – 1
-х2 – 2

вариант № 8

f(x1, x2)	gi (x1, x2) ≤ 0, i = 1,m
2(х1 – 4)2 + (х2 – 7)2	2х1 + х2 - 4
-х1 – 3
-х2 – 4

вариант № 9

f(x1, x2)	gi (x1, x2) ≤ 0, i = 1,m
2(х1 – 3)2 + (х2 – 2)2	х1 + х2 - 5
-х1 + 2х2 - 6
-х2 – 2

вариант № 10

f(x1, x2)	gi (x1, x2) ≤ 0, i = 1,m
(х1 – 2)2 + 2(х2 – 3)2	-х1 + х2 - 1
3х1 + 2х2 - 6
-х2 – 2

вариант № 11

f(x1, x2)	gi (x1, x2) ≤ 0, i = 1,m
(х1 – 2)2 + 6(х2 – 2)2	2х1 + х2 - 2
-х1 - 2
-х2 – 3

вариант № 12

f(x1, x2)	gi (x1, x2) ≤ 0, i = 1,m
(х1 – 2)2 + 4(х2 – 4)2	3х1 + 2х2 - 6
-4х1 + 3x2 - 12
-х2

вариант № 13

f(x1, x2)	gi (x1, x2) ≤ 0, i = 1,m
2(х1 – 3)2 + (х2 – 2)2	х1 + х2 - 2
-х1
-х2 - 3

вариант № 14

f(x1, x2)	gi (x1, x2) ≤ 0, i = 1,m
2(х1 – 3)2 + (х2 – 2)2	х1 + х2 - 2
-х1 + х2 - 1
-х2 - 3

вариант № 15

f(x1, x2)	gi (x1, x2) ≤ 0, i = 1,m
3(х1 – 4)2 + (х2 – 5)2	х1 + 2х2 - 2
-х1 – 4
х1 - х2 - 3

вариант № 16

f(x1, x2)	gi (x1, x2) ≤ 0, i = 1,m
(х1 – 5)2 + 2(х2 – 3)2	2х1 + х2 - 6
-2х1 + x2 – 4
- х2 - 3

вариант № 17

f(x1, x2)	gi (x1, x2) ≤ 0, i = 1,m
2(х1 – 2)2 + (х2 – 7)2	х1 + 2х2 - 8
-х1 - 2
- х2 - 3

вариант № 18

f(x1, x2)	gi (x1, x2) ≤ 0, i = 1,m
(х1 – 5)2 + (х2 + 3)2	2х1 - х2 - 4
-х1 - х2 - 1
х2 - 3

вариант № 19

f(x1, x2)	gi (x1, x2) ≤ 0, i = 1,m
(х1 + 4)2 + 2(х2 + 2)2	х1 – 2
-3х1 – х2 – 6
х2 – 1

3.2. Задания по методам численной оптимизации для выполнения второй части курсовой работы

Каждый вариант задания по второй части курсовой работы включает по два метода безусловной численной оптимизации в сочетании (если это необходимо) с методами одномерного поиска.

Численное решение конкретной задачи условной оптимизации, определяемой вариантом задания по первой части работы, должно осуществляться согласно методике сведения задачи условной оптимизации к последовательности задач безусловной численной оптимизации с помощью метода «Штрафных функций» (см. раздел 2.2).

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

Таблица 3.1

№ вар.	методы безусловной оптимизации	методы одномерной оптимизации
1	2	3
1	Метод покоординатного спуска	Метод «Золотого сечения»
Метод градиентной оптимизации с дроблением шага
2	Метод деформируемого многогранника
Метод простой градиентной оптимизации
3	Модифицированный метод наилучшей пробы
Оптимальный градиентный метод	Метод дихотомии
4	Метод простой случайной оптимизации
Метод сопряженных градиентов	Метод «Золотого сечения»

Продолжение Таблицы 3.1

1	2	3
5	Метод случайной оптимизации с направляющей сферой
Метод простой градиентной оптимизации
6	Модифицированный метод наилучшей пробы
Метод Ньютона
7	Метод случайной оптимизации с направляющим конусом
Метод градиентной оптимизации с дроблением шага
8	Метод покоординатного спуска	Метод дихотомии
Метод параллельных касательных	Метод дихотомии
9	Метод деформируемого многогранника
Метод Ньютона
10	Модифицированный метод наилучшей пробы
Метод сопряженных градиентов	Метод «Золотого сечения»

Продолжение Таблицы 3.1

1	2	3
11	Метод простой случайной оптимизации
Метод параллельных касательных	Метод простого перебора
12	Метод случайной оптимизации с направляющей сферой
Метод градиентной оптимизации с дроблением шага
13	Метод случайной оптимизации с направляющим конусом
Оптимальный градиентный метод	Метод простого перебора
14	Метод покоординатного спуска	Метод простого перебора
Метод сопряженных градиентов	Метод простого перебора
15	Метод деформируемого многогранника
Метод параллельных касательных	Метод дихотомии
16	Модифицированный метод наилучшей пробы
Метод простой градиентной оптимизации

Продолжение Таблицы 3.1

1	2	3
17	Метод простой случайной оптимизации
Модифицированный метод Ньютона
18	Метод случайной оптимизации с направляющей сферой
Оптимальный градиентный метод	Метод простого перебора
19	Метод случайной оптимизации с направляющим конусом
Метод параллельных касательных	Метод «Золотого сечения»

4. рекомендации по формированию заключения и Приложений к курсовой работе

В заключении к курсовой работе должны быть отражены следующие результаты работы.

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

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

3. Даны оценки сходимости итеративной процедуры условной оптимизации, использующей метод «Штрафных функций», в зависимости от «скорости» нарастания назначаемой последовательности коэффициентов «штрафа».

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

В Приложение к курсовой работе рекомендуется включить:

-  Распечатки модулей программного обеспечения, соответствующие блок-схеме приведенной в разделе 2.2;

-  Результаты тестирования заданных численных методов безусловной оптимизации;

-  Предложения по повышению эффективности численных методов оптимизации.