Бронов С.А. Методы оптимизации в САПР

Подождите немного. Документ загружается.

Федеральное агентство по образованию

Федеральное государственное автономное образовательное учреждение

высшего профессионального образования

"Сибирский федеральный университет"

Научно-учебная лаборатория

систем автоматизированного проектирования

Бронов Сергей Александрович

Методы оптимизации в САПР

Конспект лекций для специальности

230104.65 — системы автоматизированного проектирования

Красноярск — 2011

УДК

Бронов, С. А. Методы оптимизации в САПР : конспект лекций для спец.

230104.65 / С. А. Бронов. — Красноярск, 2011. — 122 с.

Курс лекций основан на учебном пособии [1]. В курсе лекций использо-

ваны методические решения из указанного учебного пособия, более подроб-

но рассмотрены примеры, добавлены разъяснения и комментарии.

Содержание

Содержание .......................................................................................................... 3

Обозначения и сокращения ................................................................................. 5

Введение ............................................................................................................... 6

1 Основные понятия теории оптимизации.......................................................... 8

1.1 Примеры оптимизационных задач ............................................................. 8

1.2 Формальная постановка задачи оптимизации, базовые понятия и

определения ..................................................................................................... 12

1.3 Выпуклые множества и функции ............................................................. 21

2 Аналитические методы оптимизации ............................................................ 26

2.1 Необходимые и достаточные условия оптимизации .............................. 26

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

2.3 Необходимые и достаточные условия условной оптимизации .............. 34

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

2.3.2 Задача условной оптимизации с ограничениями-равенствами ................. 40

2.3.3 Задача условной оптимизации с ограничениями-неравенствами ............. 49

2.3.4 Задача условной оптимизации со смешанными ограничениями

(равенствами и неравенствами) ........................................................................... 58

3 Численная оптимизация .................................................................................. 68

3.1 Общие принципы численной оптимизации ............................................. 68

3.2 Оценка качества метода оптимизации ..................................................... 71

3.3 Условия остановки счёта .......................................................................... 73

3.4 Установление начальных границ интервала ........................................... 74

3.5 Исключение интервалов ........................................................................... 76

4 Численные методы безусловной оптимизации .............................................. 77

4.1 Принципы построения численных методов безусловной оптимизации 77

4.2 Методы нулевого порядка ........................................................................ 80

4.2.1 Общая характеристика методов нулевого порядка .................................... 80

4.2.2 Метод равномерного поиска ....................................................................... 80

5 Линейное программирование ......................................................................... 83

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

программирования .......................................................................................... 83

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

5.3 Симплекс-метод решения задачи линейного программирования ........ 100

5.4 Двойственность задачи линейного программирования и её

использование ............................................................................................... 112

5.5 Решение задачи линейного программирования с использованием

программных средств ................................................................................... 114

5.5.1 Решение задачи линейного программирования с помощью программы

Excel .................................................................................................................... 114

Список источников .......................................................................................... 122

Обозначения и сокращения

ОДР — область допустимых решений

ЛП — линейное программирование

— вектор переменных

)

(

— целевая функция

)

(

— ограничение

— область допустимых решений

— функция Лагранжа

— число переменных (размерность вектора

)

— число ограничений-равенств

— общее число ограничений-равенств и ограничений-неравенств



— коэффициенты Лагранжа

— дополнительные переменные при преобразовании неравенств в ра-

венства

Введение

Учебная дисциплина "Методы оптимизации" (шифр ЕН.Ф.01.7) является

федеральным компонентом цикла общих математических и естественно-

научных дисциплин для направления подготовки бакалавров 230100.62 "Ин-

форматика и вычислительная техника", а также (шифр ЕН.Р.01) является

национально-региональным (вузовским) компонентом цикла общих матема-

тических и естественно-научных дисциплин для группы специальностей

230100.65 этого же направления.

Дисциплина читается на 3 курсе в 6 (весеннем) семестре и включает 100

часов занятий, из которых 68 часов — аудиторные занятия (34 часа лекций и

34 часа лабораторных занятий), 32 часа — самостоятельная работа. Форма

промежуточного контроля — зачёт.

Минимальное содержание учебной дисциплины "Методы оптимизации"

в соответствии с государственным образовательным стандартом подготовки

бакалавров (от 2000 года) включает:

"Необходимые и достаточные условия минимума гладких функций одной и несколь-

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

вого, первого и второго порядка); задача выпуклого программирования; функция Лагран-

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

граммирования; оптимизация на графах; простейшая задача вариационного исчисления;

уравнение Эйлера".

Оптимизацией в общем случае называют поиск наилучшего в некотором

смысле решения, а методы оптимизации являются соответствующим мате-

матическим инструментом. Задача оптимизации возникает тогда, когда жела-

емый эффект какого-то процесса сложным образом зависит от некоторой пе-

ременной: например, при её изменении эффект вначале увеличивается, а за-

тем уменьшается. Поэтому оптимизация всегда связана с поиском экстрему-

ма (максимума или минимума) некоторой функции, отражающей зависи-

мость эффекта от искомой переменной.

При поиске оптимального решения анализируемый процесс обычно

представляют с помощью некоторой математической модели в виде системы

уравнений и неравенств. Для её решения необходимы специальные матема-

тические методы, которые и называются методами оптимизации. Они бази-

руются на сочетании методов математического анализа (понятие функции,

производной, системы уравнений и неравенств) и вычислительной математи-

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

Объектом изучения является совокупность методов поиска наилучших

решений.

Предметом изучения являются алгоритмы нахождения оптимальных

решений, оценка их применимости и эффективности.

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

"Математический анализ" — дифференциальное и интегральное исчис-

ления; обыкновенные дифференциальные уравнения, дифференциальные

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

нального анализа;

"Вычислительная математика" — численное решение нелинейных урав-

нений и систем, интерполяция функций;

"Теория вероятностей, математическая статистика и случайные процес-

сы" — случайная величина, ее функция распределения, математическое ожи-

дание и дисперсия; распределение монотонной функции от случайной вели-

чины.

"Математическое программное обеспечение" — работа в программах

MathCAD и Matlab, использование численных алгоритмов и символьных

процессоров;

"Программирование на языке высокого уровня", "Лингвистическое и

программное обеспечение САПР" — умение алгоритмизировать математиче-

скую задачу и записать её на одном из языков программирования.

В результате изучения данного курса студент должен:

знать — модели, методы и средства анализа и разработки математиче-

ского, лингвистического, информационного и программного обеспечения ВС

и автоматизированных систем; численные методы решения систем алгебраи-

ческих и дифференциальных уравнений большой размерности, эвристиче-

ские методы решения комбинаторных задач, методы поиска экстремумов в

задачах проектирования;

владеть — методами и средствами анализа, моделирования и оптимиза-

ции объектов профессиональной деятельности и их компонентов; програм-

мированием на алгоритмических языках с использованием различных техно-

логий синтеза программных систем.

Знания, полученные при изучении учебной дисциплины "Методы опти-

мизации" будут использованы далее в учебных дисциплинах: "Исследование

операций", "Промышленная логистика", "Модели и методы анализа проект-

ных решений".

1 Основные понятия теории оптимизации

1.1 Примеры оптимизационных задач

Очень часто на практике приходится сталкиваться с задачами выбора,

когда существует несколько вариантов решения одной и той же задачи, но с

разным эффектом. Т. е. в каждом варианте задача будет решена, но резуль-

таты решения могут различаться. Иллюстрацией такого обстоятельства явля-

ется часто приводимая в литературе задача [3], рассматриваемая ниже.

Пример 1.1. В море на некотором расстоянии от берега стоит корабль,

на берегу в стороне имеется посёлок, в который необходимо попасть

(Рисунок 1.1). Известно кратчайшее расстояние

до берега и расстояние

по берегу от этой точки (

) до посёлка. Скорость перемещения по воде от-

личается от скорости перемещения по суше. Где нужно причалить, чтобы

пассажиры смогли быстрее попасть в посёлок?

Суша

Посёлок

Начало

координат

Море

Рисунок 1.1 — Задача о минимальном времени попадания в посёлок

Если скорость перемещения по воде больше или равна скорости пере-

мещения по суше, то задача решается просто: необходимо плыть прямо к по-

сёлку. Но если скорость перемещения по воде меньше скорости перемещения

по суше, то возникает некоторое противоречие. С одной стороны, в этом слу-

чае желательно бóльшую часть пути проделать по берегу, где скорость выше.

Но если пристать к берегу в точке

, то придётся дополнительно преодоле-

вать расстояние между точками

. Очевидно, что в прямоугольном тре-

угольнике

ADB

длина гипотенузы

меньше суммы катетов

поэтому движение по гипотенузе выгоднее и точка

, где следует пристать к

берегу, располагается где-то между точками

(её положение определя-

ется координатой

), требуется найти её точное положение. Чтобы решить

задачу, необходимо составить математическую модель исследуемого про-

цесса перемещения от корабля к посёлку.

Расстояние между точками будем обозначать через

с соответствую-

щими индексами.

Весь путь:

BCABAC

SSS





где

S — часть пути по воде;

S — часть пути по суше.

Расстояние между точками

можно определить через известное

расстояние до берега

и расстояние

по берегу до точки

по формуле

Пифагора:

2222

xHSSS

DBADAB

 .

Расстояние между точками

можно определить через известное

расстояние по берегу

и расстояние

по берегу до точки

xLS





Тогда весь путь:

)()(

xLxHxS

 ,

где путь записан как функция от

, так как необходимо решить задачу отно-

сительно

(определить положение точки

Если известны скорости перемещения по воде

вод

v и по суше

суш

v , то

время прохождения всего пути:

сушводсуш

вод

сушвод

xTxTxT

)(

)()()(





 . (1.1)

Можно рассчитать функцию в зависимости от

для конкретных пара-

метров. Пусть задано:

 расстояние по воде до берега

= 9 км;

 расстояние по суше до посёлка

= 15 км;

 скорость по воде

вод

v = 4 км/час;

 скорость по суше

суш

v = 6 км/час.

Зависимость времени )(xT движения к посёлку от расстояния до точки

причаливания

приведена на графике (Рисунок 1.2).

0 2 4 6 8 10 12 14 16 18 20

Рисунок 1.2 — График зависимости времени движения

)

(

(целевой функции) от точки причаливания (x)

Видно, что кривая имеет минимум в окрестности точки



км. Чтобы

определить точное значение

, необходимо исследовать полученную кривую

на экстремум (в данном случае — минимум) методами математического

анализа. Для этого следует продифференцировать уравнение (1.1), в резуль-

тате чего будет получено новое уравнение, которое затем следует приравнять

нулю:

1)()(

























суш

вод

сушвод

xHv

xdT

Это уравнение решается следующим образом:





суш

вод

xHv

 xHvxv

водсуш

;

xHvxv

водсуш

 ,





222

)( xHvxv

водсуш

 ;

)(

22222

xHvvx

водсуш

 ,

0)(

 xH

вод

суш

;

 xH

вод

суш















 H

вод

суш

;