Кафедра прикладной информатики

 

Лекции

по дисциплине:

“МЕТОДЫ ОПТИМИЗАЦИИ ”

 

Содержание:

1. Основные понятия

- понятие САПР

- процесс оптимизации

1. Методы одномерной оптимизации

- аналитический способ

- численный способ

1. Методы одномерного поиска

- метод “золотого сечения”

1. Одномерная оптимизация с использованием производных

- метод деление интервала пополам

- метод Ньютона (метод касательной)

1. Безусловная опртимизация
2. Квадратичная аппроксимация (или квадратичное приращение)
3. Методы прямого поиска

- приемущества

- недостатки

1. Метод координатного спуска
2. Градиентные методы

- метод наискорейшего спуска

- анализ метода

- метод Ньютона

- недостатки метода Ньютона

1. Задачи оптимизации с ограничениями – разностями (ЗОР)

- метод исключения

- метод множителей Лагранжа

1. Нелинейное программирование (НЛП)

- методы решения НЛП

1. Задачи линейного программирования (ЛП)

Основные понятия.

САПР – система автоматизированного проектирования. Проектирование сложный процесс, направленный на разработку отдельного объекта.

 

 

Способ уменьшения время проектирования – уменьшение числа разработчиков.

Система – совокупность людей, задач и программ, которые взаимосвязаны друг с другом.

Оптимизация – от латинского слова «оптимус» - наилучший – поиск наилучшего, поиск наилучшего проектного изделия.

 

Процесс оптимизации.

 

Имеется задача. Для решения задачи нужно формализовать объект и представить его в виде математической модели.

 

Модели:

- физические;

- геометрические (фотография, рисунок);

- математические.

 

Математическая модель, та которая определена с помощью математических формализмов. Математическая модель не является точной, а является идеализацией. Модель характеризуется параметрами, которые могут быть и числовыми . Их часть может характеризовать состояние объекта – параметры состояния , а другие могут относиться к процессу проектирования – переменные проектирования .

Определение параметров состояния - задача моделирования. Определение переменных проектирования – задачи проектирования или задачи оптимизации.

 

Допустим имеются 2 переменные . Задавая конкретные значения получаем точку.

R – множество чисел

R

G множество допустимых

вариантов

p₂ допустимое решение

p₁

недопустимое решение – не удовлетворяющее наложенным ограничениям

 

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

 

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

 

2 вида задач оптимизации:

- максимизации;

- минимизации.

 

Для оптимизационного решения задачи требуется:

1. Сформулировать задачу;
2. Построить математическую модель (определить множество переменных);
3. Определить ограничения на возможные решения;
4. Определить целевую функцию. Далее применим формальные математические методы, позволяющие найти решения.