Поиск

Полнотекстовый поиск:
Где искать:
везде
только в названии
только в тексте
Выводить:
описание
слова в тексте
только заголовок

Рекомендуем ознакомиться

'Программа-минимум'
В основу настоящей программы положены следующие дисциплины: автоматизация проектирования систем; системное программное обеспечение; алгоритмические яз...полностью>>
'Документ'
Особенности формирования двигательных умений и развития физических качеств у детей среднего школьного возраста в процессе направленного физического во...полностью>>
'Документ'
“Бухгалтерський облік операцій з цінними паперами здійснюється за такими балансовими та позабалансовими рахунками Плану рахунків бухгалтерського облі...полностью>>
'Документ'
“ВЗАИМОДЕЙСТВИЕ ГОСУДАРСТВЕННОЙ И МЕСТНОЙ АДМИНИСТРАЦИИ С ВОЕННОЙ БАЗОЙ, РАЗМЕЩЕННОЙ НА ИХ ТЕРРИТОРИИ. ЭКОНОМИЧЕСКИЕ, ПОЛИТИЧЕСКИЕ, ЭКОЛОГИЧЕСКИЕ И ЮР...полностью>>

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

Главная > Учебное пособие
Сохрани ссылку в одной из сетей:

– 32 –


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

В.Е. Усачов

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

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

УТВЕРЖДЕНО

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

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

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

Москва, 2007г.

содержание

содержание 2

Введение 3

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3. рекомендации по формированию заключения и Приложений к курсовой работе 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 отчета по КР должна иметь раздел, посвященный описанию методики решения задач условной оптимизации численными методами безусловной оптимизации с помощью метода «Штрафных функций»;

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

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

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

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

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

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

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

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

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

F(x,) = f (x) + T g(x)

(2.1)

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

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

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

(2.2)

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

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

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

(2.3)

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

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

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

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

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

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

То есть:

gj()<0, j  1,m

(2.4)

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

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

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

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

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

H(x)(х, ) = 

(2.5)

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

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

(2.6)

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

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

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

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

(2.7)

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

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

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

(2.8)

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

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

(2.9)

Где xугл – координаты «угловых» точек, определяемых n активными ограничениями из числа j1,…,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.



Скачать документ

Похожие документы:

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

    Учебное пособие
    Учебное пособие предназначено для студентов специальностей и направлений 080109 «Бухгалтерский учет, анализ и аудит», 080107 «Налоги и налогообложение», 080502 «Экономика и управление на предприятии», 080507 «Менеджмент организации»,
  2. Учебное пособие для выполнения курсовой работы в 7-м семестре Утверждено

    Учебное пособие
    Лебедев А.А., Бобронников В.Т., Красильщиков М.Н., Малышев В.В. Статистическая динамика и оптимизация управления летательных аппаратов.- М.: Машиностроение, 1985.
  3. Учебно-методическое пособие для выполнения курсовой работы

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

    Учебное пособие
    В учебном пособии к выполнению курсовой работы для студентов и дистанционной форм обучения представлены хозяйственные ситуации, отражающие деятельность условной производственной организации за месяц, а также перечень теоретических
  5. Учебно методическое пособие по выполнению курсовой работы студентами первого курса Экономического факультета направлений: «Менеджмент», «Экономика», «Бизнес информатика» по дисциплинам «Теория менеджмента» и«Менеджмент»

    Учебно-методическое пособие
    Московцев В.В.,Московцева Л.В., Лукьянова Ю.П., Провоторова Ю.С., Учебно – методическое пособие по выполнению курсовой работы студентами первого курса Экономического факультета направлений: «Менеджмент», «Экономика», «Бизнес – информатика»

Другие похожие документы..