Главная / Основы оптимизационных методов / Основы оптимизационных методов в системах телекоммуникаций

Основы оптимизационных методов в системах телекоммуникаций

Методические указания посвящены методу оптимизации как средству принятия оптимальных решений. Принятие оптимальных решений базируется на "трех китах": математической модели; решении задач на компьютере; исходных данных.

Математическое моделирование имеет 2 существенных преимущества:

1) дает быстрый ответ на поставленный вопрос, на что в реальной обстановке могут потребоваться иногда даже годы;

2) предоставляет возможности широкого экспериментирования, осуществить которое на реальном объекте зачастую просто невозможно.

Чтобы моделирование было успешным, надо выполнить три правила: учитывать главные свойства моделируемого объекта; пренебрегать его второстепенными свойствами; уметь отделить главные свойства от второстепенных.

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

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

Никто не смешивает диагноз заболевания с методом лечения. Так же и здесь. Можно считать, что математическая модель — это аналог диагноза, а алгоритм — метода лечения.

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

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

И, наконец, "третий кит" — исходные данные. Никакая хорошая сходимость алгоритма, никакое быстродействие и оперативная память компьютера не заменят достоверности исходных данных. Известная пословица гласит: что посеешь, то и пожнешь!

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

Количественная мера качества называется показателем качества. Показатель качества, экстремальное значение которого ищется в процессе оптимизации, называется критерием оптимальности.

ЦФ — целевая функция или критерий оптимизации, показывает, в каком смысле решение должно быть оптимальным, т. е. наилучшим. При этом возможны три вида назначения целевой функции: максимизация, минимизация и назначение заданного значения.

ОГР — ограничения устанавливают зависимости между переменными. Они могут быть как односторонними, так и двусторонними.

ГРУ — граничные условия показывают, в каких пределах могут быть значения искомых переменных в оптимальном решении.

Решение задачи, удовлетворяющее всем ограничениям и граничным условиям, называется Допустимым.

Любая оптимизационная задача включает в себя следующие этапы.

1. Постановка задачи. Сначала задачу формулируют в обычных терминах. Определяют цели, варианты различных действий и их влияние на характеристики управляемого объекта или процесса. Устанавливают управляемые Х=(Х1,Х2,…Хn) и неуправляемые переменные и самое главное устанавливают ограничения на переменные.

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

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

Зависимость критерия оптимальности F (x) от управляемых переменных Х=(х1,Х2,.Хn) называют целевой функцией F(X)=F(X1,X2,.Xn)

3. Отыскание оптимальных решений. На этом этапе с помощью конкретного метода программирования ведут поиск переменных Х1,..Xn, при котором целевая функция принимает экстремальное значение

F(X)=F(X1, X2,.Xn) = > extr при условии, что выполняются эти ограничения.

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

Классические методы оптимизации

На практике часто необходимо найти минимум некоторой функции F(X1,..Xп) п переменных Xi (проектных параметров). Такая функция описывает (п+1) — мерную поверхность. Соответственно функция F(X) одного параметра X1=X описывает некоторую кривую на плоскости. Поиск минимума функции одной переменной является самостоятельной, часто встречаемой задачей. К нему сводится более сложная задача поиска минимумов функций n переменных.

Согласно определению признака экстремума функция f(x) имеет максимум (минимум) в точке X*, если в достаточной близости от этой точки всем значениям х соответствуют значения f(x) меньше (больше), чем f(X*). Максимум и минимум функции объединяются понятием экстремум. В общем случае функция f(x) может иметь несколько экстремумов. Из них главный (оптимальное решение для пространства проектирования) называется глобальным. Задача поиска экстремумов сводится к их локализации и уточнению значений x, f(x) в точке экстремума.

При исследования функции одной переменной существует Правило:

Если функция f(x) и ее производные непрерывны, то точка Хо является точкой экстремума тогда, и только тогда, когда n четное, где n — порядок первой необращающейся в ноль в точке Хо производной.

Если F^n(Xo)<0, то в точке Хо достигается максимум, если F^n(Xo) > 0, то в точке Хо достигается минимум. Наибольшее или наименьшее значение функции без учета того, где

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

Существующие методы дают возможности находить Только локальные оптимумы. Если же есть подозрение, что в заданном интервале a<=x<=b целевая функция может иметь несколько оптимумов, то этот интервал следует разбить на n интервалов, в каждом интервале определить свои локальные оптимумы, а затем из всех локальных оптимумов выбрать глобальный. В дальнейшем мы будем рассматривать нахождением только локального оптимума. Следует отметить, что в подавляющем большинстве практических экономических и технических задач оптимизации существует только один оптимум. Задачи нелинейной оптимизации с точки зрения методов решения делятся на 2 класса: задачи безусловной оптимизации, задачи условной оптимизации.

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

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

Для функции одной переменной классический подход при поиске значений х состоит в решении уравнения f'(x)=0. На практике при нахождении минимума функции используют метод Ньютона, где доказывается, что X1=X0-f'(X0)/f»(X0); X2=X1-f'<X1)/f»(X1).

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

Пример. Найти минимум функции y=(x*х)/2-sinx Методом Ньютона. 10 print "Программа поиска точек перегиба функции F(x)" 15 input "Введите начальное значение, точность вычислений" Z, E 20 print "Последовательные аппроксимации"

25 REM Первая производная f'(x) вычисляется в строке 100

30 REM Вторая производная f»(x) вычисляется в строке 150

35 REM Функция f(x) вычисляется в строке 200

40 X=Z

45 gosub 100; gosub 150

50 Z=X-F/D

55 print X, Z

60 if ABS (X-Z)>E then 40

65 X=Z

70 gosub 100; gosub 150; gosub 200

75 if D>0 then print "минимум равен"FF"в точке "X""

80 goto 95

85 if D<0 then print "максимум равен"FF "в точке "X""

90 goto 95

95 END

100 F=X-cos(X)

110 Return

150 D=1+sin(X)

160 Return

200 FF=X*X/2-sin(X)

210 Return

Исходные данные: Xo=.5, E=.000001 Результаты расчета:

.5 .7552225

.7552225 .7391416

.7391416 .7390851

Fmin= .4004886; xmin=.7390851 .7390851 .7390851

Итак видим f'(x)=x-cosx=0 при x=.7391 f»(x)=1+sinx положитеЛьна при x=.7391. Следовательно, минимум функции у=-.4005 достигаЕтся при х=.7391 с точностью до четырех десятичных знаков.

Применение метода Ньютона будет неудачным, если первая аппроксимация корня такова, что отношение f'(Xo) / f»(Xo) недостаточно мало. Для того, чтобы итерация сходилась, в общем случае необходимо улучшить начальную аппроксимацию корня.

Теперь попробуем решить методом Ньютона такую задачу. Найти минимум функции f(x)= x^4-14x^3+60x^2-70x. Требуется решить уравнение f'(x)=0. В данном случае оно является кубическим уравнением, которое не так просто раскладывать на множители.

Уравнение f'(x)=0 не решается простым способом, и поэтому существуют специальные методы оптимизации, которые и изучаются в курсе "Основы оптимизационных методов".

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

1) нахождение безусловного минимума функции одной переменной;

2) нахождение условного минимума функции одной переменной;

3) нахождение безусловного минимума функции n переменных;

4) нахождение условного минимума функции n переменных.

В дальнейшем для функций одной переменной под экстремумом будем подразумевать минимум F(X). Поскольку минимуму функции F(X) соответствует максимум функции — F(X), то, сменив знак функции, программами для поиска минимума можно воспользоваться и для поиска максимума. Будем полагать, что на изменения X (если это особо не оговорено) накладываются ограничения в виде неравенств а <= X <=в,

Где а и в — границы интервала поиска. В пределах отрезка [а, в]

Функцию считаем унимодальной, т. е. содержащей один минимум.

Одномерные методы оптимизации разбиты на два класса:

1. методы уточнения минимума на заданном интервале [a, b]: деления пополам (дихотомии), Фибоначчи, золотого сечения;

2. методы спуска к минимуму из некоторой начальной точки: равномерного поиска, последовательного перебора, квадратичной интерполяции, квадратичной интерполяции — экстраполяции, Параболы.

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