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

––––––––––––––––––––––––––––––––

Санкт-Петербургский государственный

электротехнический университет «ЛЭТИ»

––––––––––––––––––––––––––––––––––––

Программирование методов оптимизации

Методические указания

к лабораторным работам

Санкт-Петербург

Издательство СПбГЭТУ «ЛЭТИ»

2004

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

––––––––––––––––––––––––––––––––

Санкт-Петербургский государственный

электротехнический университет «ЛЭТИ»

––––––––––––––––––––––––––––––––––––

Программирование методов оптимизации

Методические указания

к лабораторным работам

Санкт-Петербург

Издательство СПбГЭТУ «ЛЭТИ»

2004

УДК 681.5.001: 621.396.6

Программирование методов оптимизации: Методические указания к лабораторным работам / Сост.: Г. Д. Дмитревич, А. И. Ларистов, В. А. Павлушин. СПб.: Изд-во СПбГЭТУ «ЛЭТИ», 2004. 44 с.

Содержат описания лабораторных работ по методам оптимизации, которые лежат в основе многих экономических, производственных задач и задач оптимального проектирования.

Предназначены для студентов специальностей 220300 – «Системы автоматизированного проектирования», 220100 – «Вычислительные машины, комплексы, системы и сети», 075200 – «Компьютерная безопасность», а также для бакалавров и магистров, обучающихся по направлению 552800 – «Информатика и вычислительная техника».

Утверждено

редакционно-издательским советом университета

в качестве методических указаний

© СПбГЭТУ «ЛЭТИ», 2004

Предисловие

Настоящие методические указания предназначены для обеспечения учебного процесса по курсу «Методы оптимизации», цель которого – научить разработке программ решения оптимизационных задач с применением современной технологии программирования. Изначально предполагается, что студенты владеют навыками программирования на языке C++, полученными в рамках следующих курсов: «Программирование» (250 ч) и «Структуры и алгоритмы обработки данных» (207 ч).

Курс лекций имеет четкую практическую направленность: основное внимание уделяется прикладным и вычислительным аспектам построения алгоритмов поиска оптимальных решений. Существует обширная литература [1]–[7] по вопросам доказательства сходимости методов, условий существования и единственности решения задач оптимизации, что определило отказ от изложения в лекциях теоретических вопросов в пользу удобных для реализации вычислительных схем, доведенных до уровня практических алгоритмов.

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

Лабораторная работа 1. Исследование методов одномерного поиска минимума унимодальных функций

1.1. Требования задания

Цель работы– изучение методов одномерной минимизации функций одной переменной:

М1 – метода Свенна – золотого сечения-1;

М2 – метода Свенна – золотого сечения-2;

М3 – метода Свенна – Фибоначчи-1;

М4 – метода Свенна – Фибоначчи-2;

М5 – метода Свенна – дихотомии – Ньютона;

М6 – метода Свенна – трехточечного поиска – линейной интерполяции;

М7 – метода Свенна – Больцано – золотого сечения-1;

М8 – метода Свенна – Больцано – Фибоначчи-2.

Таблица тестовых функций

№	Функция f(x)	Начальная точка x1	Точность локализации минимума 	Значение минимума x^*
(1)	2x^2 + 3e^–^x	1	10^–3	0.469150
(2)	–e^–^хln x	0	10^–4	1.763223
(3)	2x^2 – e^x	1	10^–3	0.357403
(4)	x^4 – 14x^3 + 60x^2 – 70x	2	10^–2	0.780884
(5)	4x^3– 3x^4, еслиx ≥ 0 4x^3+ 3x^4, еслиx < 0	0.4	10^–3	–1.000000
(6)	x^2+ 2x	4	10^–2	–1.000000
(7)	2x^2+ 16/x	1	10^–2	1.587401
(8)	(10x^3+ 3x^2+x+ 5)^2	2	10^–2	–0.859902
(9)	3x^2+ (12/x^3) – 5	0.5	10^–2	1.430969

Варианты задания

Вариант	1	2	3	4	5	6	7	8
Метод	М1	М2	М3	М4	М5	М6	М7	М8
Тестовая функция	(1)	(2)	(3)	(4)	(5)	(6)	(7)	(8)