Министерство образования и науки Российской Федерации Сибирский федеральный университет

МАТЕМАТИЧЕСКИЕ ОСНОВЫ КИБЕРНЕТИКИ

Методы оптимизации Часть II

Учебное пособие

Электронное издание

Красноярск

СФУ

2014

УДК 519.7(07)

ББК 22.18.73 М 34

Составитель: Масальский Геннадий Борисович

М 34 Математические основы кибернетики. Методы оптимизации: учебнометодическое пособие [Электронный ресурс] / сост. Г.Б. Масальский. – Электрон. дан. – Красноярск: Сиб. федер. ун-т, 2014. – Систем. требо-

вания: PC не ниже класса Pentium I; 128 Mb RAM; Windows 98/XP/7; Adobe Reader V8.0 и выше. – Загл. с экрана.

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

Предназначено студентам направления подготовки 220000 "Автоматика и управление", специальности 220402.65 "Роботы и робототехнические системы", а также для направления подготовки бакалавров 15.03.06 (221000.62) "Мехатроника и робототехника". Может служить пособием магистрам, аспирантам и инженерно-техническим работникам при формализации стохастических объектов управления и решении задач статической оптимизации.

УДК 519.7(07)

ББК 22.18.73 © Сибирский федеральный

университет, 2014

Электронное учебное издание

Подготовлено к публикации ИЦ БИК СФУ

Подписано в свет 24.11.2014. Заказ № 2678 Тиражируется на машиночитаемых носителях

Издательский центр Библиотечно-издательского комплекса Сибирского федерального университета 660041, г. Красноярск, пр. Свободный, 79

Тел/факс [phone]. E-mail [e-mail] http://rio.sfu-kras.ru

		ОГЛАВЛЕНИЕ
Введение...............................................................................................................			4
1. Введение в задачи оптимизации..................................................................			5
	1.1.	Функции одной переменной ..............................................................	5
	1.2.	Функции многих переменных ...........................................................	11
	Задачи .............................................................................................................		15
2. Классическая задача математического программирования .....................			16
	2.1.	Задачи оптимизации при отсутствии ограничений .........................	17
	2.2.	Метод множителей Лагранжа............................................................	21
	Задачи .............................................................................................................		26
3.	Нелинейное программирование ..................................................................		27
	3.1.	Постановка задачи ..............................................................................	27
	3.2.	Условия Куна-Таккера........................................................................	29
	3.3.	Методы решения задач нелинейного программирования ..............	34
	3.4.	Градиентные методы оптимизации...................................................	35
	3.5.	Квадратичные методы оптимизации.................................................	40
	3.6.	Учет ограничений в градиентных методах оптимизации...............	48
	3.7.	Последовательный симплексный метод...........................................	58
	3.8.	Метод Нелдера-Мида .........................................................................	72
	3.9.	Комплекс-метод Бокса........................................................................	76
	3.10. Методы случайного поиска ...............................................................		78
	3.11. Глобальный поиск...............................................................................		82
	3.12. Многокритериальные задачи .............................................................		84
	Задачи .............................................................................................................		87
4.	Линейное программирование ......................................................................		89
	4.1.	Постановка задачи ..............................................................................	89
	4.2.	Двойственные задачи ЛП ...................................................................	91
	4.3. Методы решения задачи линейного программирования................		94
	4.4. Идея симплекс-метода линейного программирования ...................		98
	Задачи .............................................................................................................		104
5. Специальные задачи линейного программирования.................................			110
	5.1.	Транспортные задачи..........................................................................	110
	5.2.	Задачи целочисленного программирования.....................................	115
	5.3.	Задача выбора вариантов ...................................................................	119
	5.4.	Дискретное программирование .........................................................	126
	5.5.	Задача коммивояжера .........................................................................	129
	Задачи .............................................................................................................		134
Библиографический список ...............................................................................			135
Список используемых аббревиатур и обозначений ........................................			136

3

ВВЕДЕНИЕ

Многие задачи производственной деятельности связаны с поиском оптимального варианта, например, задача выбора оптимальной программы производства, рациональных способов транспортировки грузов, поиск оптимального проектного решения конструкции в условиях ограничений и выбранного критерия эффективности. Для решения таких задач разработаны методы оптимизации, используемые в математическом программировании (статическая оптимизация). Большинство приведенных в учебном пособии методов оптимизации реализованы в виде стандартных процедур в программных средах Mathcad и Matlab и других специализированных математических средах. Для выполнения инженерных задач статической оптимизации важно корректно осуществить постановку задачи, выбрать соответствующий метод оптимизации и оценить полученный результат. Этому посвящена 2-я часть учебного пособия.

Впервой главе дана постановка общей задачи математического программирования и некоторые геометрические и практические аспекты ее решения для функции одной и многих переменных.

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

де Mathcad.

Третья глава посвящена рекуррентным методам решения задач нелинейного программирования, в том числе в условиях ограничений. Подробно рассмотрены алгоритмы последовательного симплексного метода, разработанные сотрудниками кафедры «Робототехника и техническая кибернетика» политехнического института СФУ.

Вчетвертой главе дана постановка задачи линейного программирования и методы ее решения с использованием стандартных функций Mathcad и Matlab.

Впятой главе приведены постановки специальных задач линейного программирования (транспортные задачи, целочисленного программирования, выбора вариантов) и методы их решения в среде Mathcad и Matlab.

4