книги / Математические основы теории систем. Методы оптимизации

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

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

В.А. Панов

МАТЕМАТИЧЕСКИЕ ОСНОВЫ ТЕОРИИ СИСТЕМ. МЕТОДЫ ОПТИМИЗАЦИИ

Издание второе, переработанное и дополненное

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

в качестве учебного пособия

Издательство Пермского национального исследовательского

политехнического университета

2011

1

УДК 517.977.5(075.8) ББК 22.18я73

П16

Рецензенты:

кандидат технических наук, профессор Н.Н. Матушкин (Пермский национальный исследовательский политехнический университет);

кандидат технических наук С.Л. Макаренко (Генеральный директор ООО «Форт-Телеком», г. Пермь)

Панов, В.А.

П16 Математические основы теории систем. Методы оптимизации: учебное пособие/ В.А. Панов. – 2-е изд., перераб. и доп. – Пермь: Изд-во Перм. нац. исслед. политехн.ун-та, 2011. – 148 с.

ISBN 978-5-398-00679-7

Изложены основы теории оптимизации. Рассмотрены методы решения задач линейного и нелинейного программирования, вариационного исчисления, оптимального управления. Для каждого типа оптимизационных задач представлены постановка задачи, решение в общем виде, примеры.

Предназначено для студентов электротехнических специальностей высших учебных заведений.

УДК 517.977.5(075.8) ББК 22.18я73

5

ВВЕДЕНИЕ

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

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

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

6

1.ОСНОВНЫЕ ПОНЯТИЯ И ОПРЕДЕЛЕНИЯ

Вэтом разделе даны определения основных понятий теории оптимизации.

1.1. Оптимизационная задача

Рассмотрим следующую задачу:

Имеется плата, на которой размещены 2 микросхемы и 2 разъема. Первая микросхема имеет 16 выводов, вторая – 24. У первого разъема 12 контактов, у второго – 36. Дано среднее расстояние от каждой микросхемы до каждого разъема. Требуется определить количество связей каждой микросхемы с каждым разъемом при условии, чтобы длина связей была минимальной.

Составим математическое описание задачи. Введем следующие обозначения:

x1 – количество связей первой микросхемы с первым разъемом; x2 – количество связей первой микросхемы со вторым разъемом; x3 – количество связей второй микросхемы с первым разъемом; x4 – количество связей второй микросхемы со вторым разъемом; l1 – среднее расстояние отпервоймикросхемы допервогоразъема; l2 – среднее расстояние отпервоймикросхемы довторогоразъема; l3 – среднее расстояние отвтороймикросхемыдопервогоразъема; l4 – среднее расстояние отвтороймикросхемыдовторогоразъема. Тогда формула, выражающая среднюю длину связей, имеет вид

x1, x2 , x3 ,x4 ≥ 0.

7

Здесь:

(1.1) – целевая функция (ЦФ, критерий оптимальности) – математическое выражение, характеризующее качество объекта;

(1.2) – ограничения – математические выражения, связывающие переменные объекта.

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

Формулировка оптимизационной задачи

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

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

1.2. Допустимое решение

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

Рис. 1.1. Область допустимых решений для двумерной задачи

8

1.3. Локальный экстремум

Локальный экстремум – это минимальное или максимальное значение функции в окрестности некоторой точки (рис. 1.2). Здесь x0 – локальный минимум (окрестность т. А), x1 – локальный максимум (окрестностьт. В).

Рис. 1.2. Локальные экстремумы функции одной переменной; x0 – локальный минимум, x1 – локальный максимум

1.4. Глобальный экстремум

Глобальный экстремум – минимальный из всех локальных минимумов или максимальный из всех локальных максимумов.

В этом курсе под понятием минимума (максимума) будет пониматься минимальное (максимальное) значение функции на заданном отрезке (рис. 1.3).

Рис. 1.3. Минимальное значение функции на отрезке [a, b]

1.5. Условный и безусловный экстремум

Условный экстремум – экстремум, удовлетворяющий ограничениям.

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

9

Пример задачи на поиск безусловного экстремума: найти минимум функции

f (x, y) = x2 + 2y2 − 2xy − 2x − 6y.

Добавив к этой постановке задачи ограничения, получим задачу на поиск условного экстремума:

f (x, y) = x2 + 2y2 − 2xy − 2x − 6y → min,

x1 + x2 ≤ 2,− + ≤

x1 2x2 2,≥

x1, x2 0.

1.6. Критерии оптимальности

Критерий оптимальности – это выражение, характеризующее качество объекта.

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

Основные параметры микросхемы: Р – потребляемая мощность;

tз – время задержки распространения сигнала (быстродействие); ∆U – максимально допустимая амплитуда помехи (помехоустой-

чивость).

Требуется оптимизировать микросхему по этим параметрам. Критерии оптимальности подразделяют на три группы: частные,

обобщенные и минимаксные.

1.6.1. Частные критерии

Частные критерии оптимальности делятся на две подгруппы:

оптимизация по какому-либо одному параметру (напри-

мер, минимальная потребляемая мощность, Р → min);

минимизация отклонения реальной характеристики от теоретической (рис. 1.4).

10