Министерство образования Республики Беларусь

БЕЛОРУССКИЙ НАЦИОНАЛЬНЫЙ ТЕХНИЧЕСКИЙ

УНИВЕРСИТЕТ

Кафедра «Системы автоматизированного проектирования»

Методы однокритериальной оптимизации

Лабораторный практикум

по дисциплине «Методы исследования операций»

для студентов специальности 40 01 02 -

«Информационные системы и технологии (по направлениям)»

направления 40 01 02-01 -

«Информационные системы и технологии в проектировании и производстве»

Минск 2005

Составители:

Придухо В.Т.

Кадач Т.В.

Белорусский национальный технический университет

Республика Беларусь, г.Минск, пр-т Скорины, 65

Тел.[phone] факс [phone]

Компьютерная сеть БНТУ

CОДЕРЖАНИЕ

CОДЕРЖАНИЕ 3

Лабораторная работа №1 4

МЕТОД ПРЯМОГО ПЕРЕБОРА ПО СЕТКЕ 4

Лабораторная работа №2 5

МЕТОД МОНТЕ-КАРЛО 5

Лабораторная работа № 3 6

МЕТОД ХУКА-ДЖИВСА 6

Лабораторная работа № 4 8

МЕТОД ШТРАФНЫХ ФУНКЦИЙ 8

Лабораторная работа № 5 9

СЛУЧАЙНЫЙ ПОИСК С линейной и НЕЛИНЕЙНОЙ ТАКТИКОЙ 9

Лабораторная работа № 6 12

ЭВОЛЮЦИОННЫЙ БИОНИЧЕСКИЙ АЛГОРИТМ 12

ЛИТЕРАТУРА 14

Варианты заданий 16

Лабораторная работа №1

МЕТОД ПРЯМОГО ПЕРЕБОРА ПО СЕТКЕ

Цель работы: Изучение одного из простейших методов поиска экстремума функции нескольких переменных нулевого порядка; графическое построение и исследование области поиска.

1. Описание метода

1. Разбить отрезки [х_imin, x_imax], i=1,2,..n (где х_i – оптимизируемые параметры)

на равные части.

2. Вычислить значения функции в узлах сетки (на пересечениях координат).

3. По полученным значениям функции в узлах сетки методом линейной интерполяции построить линии уровней функции (линии равных значений) и получить представление о поведении функции.

4. Найти экстремум функции.

2. Порядок выполнения лабораторной работы

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

x_1min=x_2min= -1

x_1mах=x_2mах= 4

Принять шаг сетки х₁=х₂=0,5.

2. Построить область поиска экстремума и линии уровней минимизируемой функции.

3. Задать область допустимых решений, включив в программу функциональные ограничения в виде неравенств, приведенные в задании, выданном преподавателем. Найти минимум функции с учетом введенных ограничений.

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

3. Требования к защите лабораторной работы

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

Контрольные вопросы:

1. Структура оптимизационной модели.

2. Задачи анализа и синтеза в общей схеме оптимизации.

3. Классификация задач оптимизации.

4. Классификация методов оптимизации.

Лабораторная работа №2

МЕТОД МОНТЕ-КАРЛО

Цель работы: Изучение наиболее распространенного из простейших методов поиска экстремума функции нескольких переменных нулевого порядка; графическое построение и исследование области поиска.

1. Описание метода

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

1. Многократно смоделировать независимые случайные варианты решений из допустимой области с координатами

х_ij=x_imin+ksi_ij(x_imax-x_imin),

где i=1,2,..n (n – число параметров)

j=1,2,..m (m – число испытаний)

ksi – случайное число в диапазоне [0,1].

1. Вычислить в каждом из вариантов значение заданной функции.

2. Выбрать вариант с минимальным значением функции.

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