Методы оптимизации и исследование операций для бакалавров информатики. Часть 2

УДК 517.8 Г 522

Гладких Б. А. Методы оптимизации и исследование

Г522 операций для бакалавров информатики. Ч. II. Нелинейное и динамическое программирование: учебное пособие.

— Томск: Изд-во НТЛ, 2011. — 264 с.

ISBN 978-5-89503-483-5

Книга написана на основе лекций, в течение ряда лет читавшихся автором на факультете информатики Томского государственного университета.

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

Учебное пособие соответствует Государственному образовательному стандарту по направлениям «информационные технологии» и «прикладная информатика», но может быть использовано для студентов, обучающихся по другим инженерным и экономическим

направлениям.

УДК 517.8

Р е ц е н з е н т ы:

доктор техн. наук, профессор В. В. Поддубный, кандидат техн. наук, доцент А. П. Рыжаков

Оглавление

Введение

Общая задача математического программирования имеет вид

где (1) — целевая функция (objective function), (2) — ограничения

(constrains).

→−

Размерность вектора переменных X = (x1, . . . , xn)T предполагается конечной, поэтому задачу математического программирования называют конечномерной оптимизацией в отличие от бесконечномерных задач вариационного исчисления (variational calculus).

В случае, когда когда f и gi являются линейными функциями, математическое программирование превращается в линейное (linear programming — LP), которому мы посвятили всю первую часть нашего курса, a когда хотя бы одна из функций f и gi нелинейна, мы имеем дело с задачей нелинейного программирования (nonlinear programming — NLP).

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

[23, кн. 2, с. 273] описывается нелинейная модель оптимизации химического процесса синтеза этиленгликоля, имеющая 22 переменные, 7 ограничений-равенств, 12 ограничений-неравенств и полный набор ограничений переменных сверху и снизу.

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

Вреальных задачах целевая функция может быть задана:

•аналитическим выражением, которое может быть сколь угодно сложным;

•алгоритмом вычисления, в том числе программой имитационного моделирования некоторого процесса;

•натурным экспериментом.

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

Множество D Rn, определяемое совокупностью ограничений (2), называется множеством допустимых решений (feasible decisions set) или (в русскоязычной литературе) множеством планов.

Когда число переменных равно двум, задачу математического программирования легко интерпретировать геометрически. Множество допустимых решений будет представлять собой некоторую область на плоскости, а целевая функция f (x1, x2) имеет вид неровной поверхности с холмами и впадинами. Ее можно изобразить

ввиде трехмерной картинки или, подобно тому, как на географических картах изображается рельеф местности, семейством линий равных значений — изоцелевых линий (рис. 1). Как мы увидим

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

Рис. 2. Трудности, порождаемые нелинейностью

Во-вторых, экстремум может находиться как на границе, так и внутри области. В примере на рис. 2, б целевая функция представляет собой простейшую квадратичную форму двух перемен-

ных, изоцелевые линии которой являются концентрическими ок-

→−

ружностями с общим центром в точке X = (a, b)T :

f1(x1, x2) = (x1 − a)2 + (x2 − b)2 → min, g(x1, x2) = x1 + x2 1,

x1, x2 0.

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

планов.

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

десятичной точкой. Запятые будут использоваться для отделения чисел друг от друга. Так значительно удобнее записывать векторы с нецелыми компонентами.

Классификация

В связи с указанными трудностями общих ме-

тодов решения любых задач математического задач и методов. программирования не существует. Изобрете-

Структура книги

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

Математическое программирование

Рис. 3. Классификация задач математического программирования

К настоящему времени наиболее изученным является класс задач выпуклого программирования (convex programming), в которых целевая функция и ограничения задаются выпуклыми функциями. Важнейшим свойством таких задач является единственность экстремума, то есть совпадение локального экстремума с глобальным. Для выпуклых задач удается построить общую теорию, которую мы будем изучать в гл. 9. Она обобщает классический метод множителей Лагранжа и сводит задачу нахождения экстремума при наличии ограничений к решению некоторой системы уравнений и неравенств (условий Куна — Таккера).

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