Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
12
Лекция 5.2. Методы оптимизации на компьютерных моделях.
Экономические задачи привели к возникновению линейного программирования. Большинство экономических моделей являются линейными, например, задачи:
В экономических задачах переменные интерпретируются как цены на ресурсы и продукцию. Для этих задач характерна высокая размерность (сотни и тысячи переменных ).
Технические задачи линейного программирования:
Математические постановки задач линейного программирования могут отличаться лишь ограничениями.
Виды задач линейного программирования:
1.Общая задача линейного программирования - определение набора значений варьируемых переменных ХJ, при которых достигается максимум или минимум линейной целевой функции
F() =(min) , (1)
при условиях - ограничениях в виде равенств
(2)
и в виде неравенств
(3)
При этом обязательно соблюдаются условия неотрицательности оптимальных значений варьируемых переменных:
(4)
Любое решение, удовлетворяющее системе ограничений, является допустимым решением ( допустимым планом ). Допустимое решение, доставляющее минимум (максимум) целевой функции - оптимальное решение.
2. Стандартная ( симметричная ) задача линейного программирования - определение максимума целевой функции при ограничениях, заданных в виде неравенств.
3. Каноническая ( основная ) задача линейного программирования - определение максимума при ограничениях заданных в виде равенств.
Эти три задачи могут быть преобразованы одна в другую. Необходимое преобразование зависит от выбранного метода решения. Для преобразования видов задач нужно:
1. свести задачу минимизации к задаче максимизации:
min F=-max(-F)
2. преобразовать ограничения типа неравенств:
(3)
в равенства (2)
Вводимые дополнительные переменные имеют экономический смысл. Так, если в ограничениях исходной задачи линейного программирования отражены расходы и наличие производственных ресурсов, то дополнительная переменная - неиспользуемый ресурс.
3. преобразовать все переменные в неотрицательные:
если Xk не подчинена условиям неотрицательности, то она заменяется двумя неотрицательными переменными:
Xk = Uk - Vk
Примеры задач линейного программирования.
Определение объема производства. Общая постановка задачи планирования производства: необходимо определить план произ водства одного или нескольких видов продукции, который обес печивает наиболее рациональное использование имеющихся ма териальных, финансовых и других видов ресурсов. Такой план бу дет оптимальным с точки зрения какого-либо выбранного крите рия — максимума прибыли, минимума затрат на производство и т.д.
Задачи планирования производства возникают на разных уров нях в системе экономического управления: на уровне отдельных производственных цехов, участков и бригад, предприятий, отраслей, на уровне народного хозяйства в целом:
Тогда смысл обозначений в выражениях (1)-(4):
n— количество видов выпускаемой продукции;
m — количество видов производственных ресурсов (производственные мощности, сырье, рабочая сила);
аij — объем i-го ресурса на выпуск единицы j-й продукции;
сj — прибыль от выпуска единицы j-й продукции;
bi — количество имеющегося ресурса i-го вида;
Xj— объем выпуска j-й продукции (переменная);
(1) — целевая функция (максимум прибыли);
(2) – (3)— группа ограничений на объем имеющихся в наличии ресурсов.
Пример . Предприятие располагает ресурсами сырья, рабочей силы и оборудования, необходимыми для производства любого из четырех видов продукции. Затраты ресурсов на изготовление единицы данного вида продукции, прибыль, полу чаемая предприятием, а также запасы ресурсов указаны в следую щей таблице.
Долж но быть выпущено не менее 1 ед. продукции первого вида и 5 ед. — второго вида.
Необходимо определить, сколько продукции каждого вида надо выпускать, чтобы прибыль была максимальной, и на какой вид продукции (первый или второй) выгоднее всего принимать до полнительный заказ?
|
Виды ресурсов |
В |
иды пр |
одукци |
и |
Запасы |
|
1 |
2 |
3 |
4 |
ресурсов |
|
|
Сырье, кг Рабочая сила, ч Оборудование, станко-ч |
3 22 10 |
5 14 14 |
2 18 8 |
4 30 16 |
60 400 128 |
|
Прибыль на единицу продукции, тыс.р. |
30 |
25 |
56 |
48 |
— |
Модель линейного программирования:
Зох1 + 25х2+ 56х3 + 48х4 mах,
при Зx1 + 5х2 + 2х3+ 4х4 60,
22х1+ 14х2+ 18х3+ З0х4 400,
10х1+ 14х2 + 8Х3 + 16Х4 128,
Х1 1, Х2 5, Х3 0, Х4 0.
Оптимальное решение задачи: Х1 = 1, Х2 = 5, Х3 = 6, Х4 = 0.
Задачи о смесях. Такие задачи возникают при выборе наиболее рационального способа смешения исходных ингредиентов для получения смеси с заданными свойствами. Смесь должна содержать определенное количество компонентов, входящих в состав исходных ингредиентов. Известны стоимостные характеристики ингредиентов. Тре буется получить искомую смесь с наименьшими затратами.
Задачи такого типа встречаются во многих отраслях промыш ленности (металлургия, парфюмерия, пищевая промышленность, фармакология, сельское хозяйство). Примерами задач о смесях могут служить, определение состава шихты в доменном или сталеплавильном производствах.
За неизвестные в моделях оптимального смешения принима ются доли или количества ингредиентов, идущие на приготовле ние смеси. Различаются типы моделей, а) с одной или с большим числом смесей, б) с ограниченным или неограниченным количе ством ингредиентов; в) по критерию производства смеси.
Пример .Однопродуктовая модель оптимального смешения'.
Здесь смысл обозначений в выражениях (1) – (4):
n — количество исходных ингредиентов;
m — количество компонентов в смеси;
л — удельный вес 1-го компонента в j-м ингредиенте;
с — стоимость единицы j-го ингредиента;
b. — минимально допустимое количество i-го компонента в смеси;
x. — количество j-го ингредиента, входящего в смесь;
(1) — целевая функция (минимум затрат на получение сме си);
(2) — группа ограничений на содержание в смеси заданного количества компонентов;
(3) — ограничения на неотрицательность переменных.
Оптимальный раскрой материалов. Большинство материалов, используемых в промышленности, поступает на производство в виде стандартных форм. Непосред ственное использование таких материалов, как правило, крупных размеров, обычно невозможно. Предварительно их нужно разде лить на заготовки необходимых размеров. При этом возникает не обходимость выбора способа раскроя и интенсивности его приме нения. Задачи такого типа, называемые задачами оптимального раскроя материалов, возникают в металлургии и машинострое нии, лесной и лесообрабатывающей, легкой промышленности и других отраслях и используются по отношению к технологичес ким процессам, где большая вариантность позволяет достигнуть значительного эффекта благодаря оптимизации.
В разработке плана раскроя тесно переплетаются две задачи:
Рациональный вариант раскроя. В задачах оптимального раскроя рассматриваются так называемые рациональные способы раскроя, т.е. такие, для которых увеличение коли чества заготовок любого типа возможно только за счет сокраще ния числа заготовок какого-либо другого типа.
Пример 1. Требуется определить все рациональные способы раскроя металлического стержня длиной 100 см на заготовки трех типов длиной 20, 30 и 50 см.
|
Способы |
3 |
агото |
вки |
Отходы |
|
А=50 |
В=30 |
С=20 |
||
|
1 |
2 |
0 |
0 |
0 |
|
2 |
1 |
1 |
1 |
0 |
|
3 |
1 |
0 |
2 |
10 |
|
4 |
0 |
3 |
0 |
10 |
|
5 |
0 |
2 |
2 |
0 |
|
6 |
0 |
1 |
3 |
10 |
|
7 |
0 |
0 |
5 |
0 |
Таким образом, в данном случае существует семь различных рациональных способов раскроя.
Определение интенсивности использования варианта раскроя.
Обозначения:
j — индекс типа поставляемых материалов, j = 1, 2, ..., s;
i — индекс способа раскроя, i = 1, 2, ..., р;
bk — число заготовок вида k в комплекте, k = 1,2, ..., q;
аijk — количество заготовок вида k, полученных при раскрое единицы материала j-го типа i-м способом;
dj — количество поступившего материала j-го вида;
хij — количество единиц j-го материала, раскраиваемых по i-му способу (интенсивность использования способа);
сij — величина отхода, полученного при раскрое единицы ма териала j-го типа по i-му способу;
у — число комплектов заготовок различного типа.
Модель:
Y – max (5)
Xij 0, i=1,..p; j=1,..s (6)
(7)
(8)
(5) — целевая функция — максимум комплектов изготавливаемых изделий;
(6) — неотрицательность переменных;
(7) — учет ограниченности ресурсов;
(8) — учет выполнения плана.
Целевая функция в зависимости от условий задачи может за писываться и в другом виде.
Например, если требуется производить не максимум комп лектов, а просто максимум деталей, то целевая функция:
а неравенство (7) исключится из условий.
Если требуется ориентировать производство на минимум отходов, то функционал будет выглядеть следующим образом:
Решим задачу:
F=c1 X1+ c2 X2 max
при условии
ai1 X1+ ai2 X2 bi
Каждое неравенство определяет полуплоскость с граничными прямыми ai1 X1+ ai2 X2 = bi (i=1,…k) , а условия неотрицательности определяю положение области допустимых планов в первом квадранте. Если система ограничений совместна , то область решений есть множество точек, принадлежащих указанным полуплоскостям. Область допустимых решений лежит в многоугольнике, образованном ограничениями - неравенствами.Для пространства, когда параметров больше двух, многоугольник превращается в многогранник.. или в гипермногогранник. Поскольку целевая функция является функцией от x,y, то даже для двух варьируемых параметров задача становиться трехмерной.
Многогранник решений в задачах линейного программирования всегда выпуклый. Это значит, что между любыми двумя его точками можно провести прямую, не пересекающую его границу..Максимум ( минимум ) целевой функции всегда находится в вершинах многогранника решений, или на его грани, или на одной из ограничивающих его гиперплоскостей.
Задача линейного программирования сводится к поиску вершины, где целевая функция минимальна или максимальна.
Последовательность решений:
1. на координатной плоскости строят прямые, соответствующие границам неравенств;
2. отштриховывают соответствующие полуплоскости;
3. строят многоугольник ограничений;
4. строят прямую F(X1 , X2) =h (h-произвольное );
5. передвигают прямую параллельно себе в направлении, соответствущем увеличению или уменьшению h, до касания с крайней точкой многоугольника ограничений. Эта точка соответствует оптимальному плану.
6. определяют значение параметров оптимального плана, т.е. X
Геометрический метод работает при 2-3 переменных. При увеличении размерности в разумных пределах определяют все вершины n-мерного многогранника решений, вычисляют целевую функцию в этих вершинах, а потом сравнивают их путем полного перебора. Это метод полного перебора вершин.
СИМПЛЕКС - МЕТОД РЕШЕНИЯ
Симплекс - метод использует ту же идею, что и предыдущие методы (оптимальное решение находится в одной из вершин), но в нем
- просмотр вершин ведется по соседним вершинам;
- просмотр ведется таким образом, что значение целевой функции возрастает шаг за шагом ( для задач максимизации ),
Схема метода:
1. принимаем в качестве начального приближения координату любой вершины;
2. находим все ребра, выходящие из нее;
3. определяем "наклоны" всех ребер;
4. двигаемся вдоль того ребра, где целевая функция возрастает быстрее, и приходим в новую вершину;
5. далее процедура повторяется до прихода в максимальную вершину, движение из нее по любому ребру приводит к убыванию целевой функции.
Данный метод применяется:
1. для пространств любой размерности;
2. всегда дает оптимальное решение за n или 2n шагов;
3. оптимальное решение на выпуклом многограннике ограничений всегда
единственно.
Практически для решения задач используют готовые программы. Кроме поиска оптимального плана, эти пакеты программ позволяют произвести анализ решения:
определить в каких пределах могут меняться коэффициенты целевой функции, чтобы оптимальный план еще сохранялся;
оценить устойчивость оптимального плана к изменению коэффициентов и свободных членов системы уравнений - ограничений.
.
Существует достаточно большое количество численных ме тодов оптимизации. Они классифицируются следующим образом:
1. По размерности решаемой задачи: одномерные и многомерные.
2. По способу формирования шага многомерные методы делятся на следующие виды:
2.1. Градиентные.
2.2. Безградиентные: с поочередным изменением переменных и с одновременным изменением переменных.
2.3. Случайного поиска: с чисто случайной стратегией и со смешанной стратегией.
3. По наличию ограничений.
3.1. Без ограничений (безусловные).
3.2. С ограничениями (условные):
• с ограничениями типа равенств;
• с ограничениями типа неравенств;
• смешанные.
Методы одномерной оптимизации являются базой для не которых "многомерных" методов. В многомерной градиентной оптимизации строится улучшающая последовательность в зависимости от скорости изменения критерия по различным направ лениям. При этом под улучшающей последовательностью пони мается такая последовательность х0, x1, ..., хi,. , в каждой точке которой значение критерия оптимальности лучше, чем в преды дущей. В безградиентных методах величина и направление шага к оптимуму при построении улучшающей последовательности формируется однозначно по определенным детерминированным функциям в зависимости от свойств критерия оптимальности в окрестности текущей точки без использования производных (т.е. градиента). Случайные методы используются в задачах высокой размерности. Многомерная условная оптимизация учитывает ак тивные ограничения, выраженные в виде равенств и неравенств. В каждом из рассмотренных направлений имеется большое число методов, обладающих своими достоинствами и недостатками, ко торые зависят прежде всего от свойств тех функций, экстремум которых ищется. Одним из сравнительных показателей качества метода является количество значений функции, которое нужно вычислить для решения задачи с заданной погрешностью. Чем это число меньше, тем при прочих равных условиях эффективнее метод.
МЕТОД СКАНИРОВАНИЯ
Метод заключается в последовательном переборе всех значений а х b с шагом (погрешность решения) с вычислением крите рия оптимальности R в каждой точке. Путем выбора наибольшего из всех вычисленных значений R и находится решение задачи х*.
Достоинство метода в том, что можно найти глобальный мак симум критерия, если R(x) — многоэкстремальная функция. К недостаткам данного метода относится значительное число пов торных вычислений R(x), что в случае сложной функции R(x) требует существенных затрат времени.
На практике можно реализовать одну из основных модифи каций метода — последовательное уточнение решения, или сканирование с переменным ша гом (рис.13)
.
На первом этапе сканирование осуществляют с крупным шагом, затем отрезок, внутри которого получено наибольшее значение - R(x), разбивается на более мелкие отрезки, ищется новый отрезок, внутри которого находится уточненное значение максимума. Он (новый отрезок) опять делится на более мелкие и т.д., до тех пор, пока величина отрезка, содержащего максимальное значение R(x), не будет меньше заданной погрешности. Главный недостаток этого вари анта метода — возможность пропуска "острого" глобального максимума R(x).
Метод основан на делении текущего отрезка [о b,], где содержится искомый экстремум, на две равные части с последующим выбором одной из половин, в которой локализуется максимум в качестве следующего текущего отрезка. Экстремум локализуется путем сравнения двух значений критерия оптимальности в точ ках, отстоящих от середины отрезка на е / 2, где е — погрешность решения задачи оптимизации.
Если R(x + е /2) > R(x - е /2), то максимум располагается на правой половине текущего отрезка [а, b], в противном случае — на левой.
Процесс поиска завершается при достижении отрезком [а, b ] величины заданной погрешности е.
К недостаткам метода относится его работоспособность только для одноэкстремальных функций R(x) (т.е. таких, которые содержат один экстремум того типа, который мы ищем в задаче), так как в других случаях при сравнении двух критериев в сосед них точках невозможно правильно выбрать следующий интервал, где находится максимум.
На рис. 14 приведены три этапа метода половинного деления. Сплошными вертикальными линиями отмечены середины отрезков, а пунктирными — вычисляемые значения критерия оптимальности слева и справа на е/2 от середин.
МНОГОМЕРНАЯ БЕЗУСЛОВНАЯ ГРАДИЕНТНАЯ ОПТИМИЗАЦИЯ
КОНЦЕПЦИЯ МЕТОДОВ
Рассматриваются методы построения улуч шающих последовательностей при отыскании экстремума функции R(x) без активных ограничений. Активными принято называть такие ограничения, на границе которых находится решение. Если известно, что решение лежит строго внутри допустимой области, например, в случае ограничений типа неравенств, то такие ограничения лучше выводить из задачи на этапе ее постановки. Кстати, следует отметить, что ограничения типа равенств всегда активные.
Величина шага х в рекуррентном соотношении
Xi+1 =хi +хi
вычисляется с использованием градиента целевой функции R(x), т.е.
хi = f (grad R(xi)),
при этом шаг может определяться с использованием градиента в одной (текущей) или в двух (текущей и предыдущей) точках. Направление градиента, как известно, показывает направления наискорейшего возрастания функции, а его модуль — скорость этого возрастания.
Рис. 17. Иллюстрация траекторий поиска минимума функции градиентными методами: 1 — оптимум; 2 — траектория метода градиента; 3 — траектория метода тяжелого шарика; 4 — траектория метода наискорейшего спуска;
5 — траектория метода сопряженных градиентов; 6 — начальные точки траекторий
лишь одна из возможных траекторий.
Кроме того, для всех приве денных траекторий выбраны различные начальные условия, с тем чтобы не загромождать построения. На этом и последующих рисунках зависимость R(x1,x2) приведена в виде линий уровня на плоскости в координатах x1 –x2.
МЕТОД ГРАДИЕНТА
Метод градиента в чистом виде формирует шаг по переменным как функцию от градиента R(x) в текущей точке поиска. Простейший алгоритм поиска minR(x) записывается в векторной форме следующим образом:
xi+1 =xi-hgradR(xi),
или в скалярном виде:
Величина рабочего шага в направлении градиента h grad R(x) зависит от величины градиента, который заранее учесть трудно, и от коэффициента пропорциональности шага h, с помощью которого можно управлять эффективностью метода.
Поиск каждой новой точки состоит из двух этапов:
1) оценка градиента R(x) путем вычисления частных производных от R(x) по каждой переменной хj;
2) рабочий шаг по всем переменным одновременно.
Величина h сильно влияет на эффективность метода. Большей эффективностью обладает вариант метода, когда шаг по каждой переменной определяется направляющими косинусами градиента
В этом случае величина рабочего шага не зависит от величины модуля градиента, и ею легче управлять изменением h. В районе оптимума может возникать значительное "рыскание", поэтому используют различные алгоритмы коррекции h.
Наибольшее распространение получили следующие алгоритмы:
1. hi =const =h (без коррекции);
2. hi =hi-1/2, еслиР(хi)< R(xi-1); hi =hi-1, ecлиR(xi)>R(xi-1);
3. hi=hi-1, если 1 2; hi=2hi-1, если 1 ; ,
где — угол между градиентами на предыдущем и текущем шаге; 1, и 2; — заданные пороговые значения выбираются субъективно (например, 1 =П/6, 2 = П /3).
Вдали от оптимума направление градиента меняется мало, по этому шаг можно увеличить (второе выражение), вблизи от опти мума направление резко меняется (угол между градиентами R(x) большой), поэтому h сокращается (третье выражение).
Для оценки частных производных используются разностные методы:
1. Алгоритм с центральной пробой
2. Алгоритм с парными пробами
где gi — пробный шаг по i-й переменной, выбираемый достаточно малым для разностной оценки производной.
Первый алгоритм требует меньших затрат по сравнению со вторым (обычно затраты выражаются количеством вычислений критерия оптимальности), но позволяет получить решение менее точно, чем второй, и эта погрешность зависит от величины пробного шага.
На рис. 17 приведена одна из возможных траекторий поиска минимума двумерной функции градиентным методом (наряду с другими ниже рассматриваемыми методами).
Условием окончания поиска может являться малость модуля градиента R(x), т.е. |grad R(x)\< .
Основным недостатком градиентного метода является необходимость частого вычисления производннх от R(х). Этого недостатка лишен метод наискорейшего спуска, который заключается в следующем.
В текущей точке вычисляется grad R(х), и затем в направлении градиента ищется тinR(х). Практически зто может быть осуществлено любым методом одномерной оптимизации (поиск по одному направленню — направленню градиента), наиболее часто используется сканирование до первого локального минимума по направлению grad R(х).
В результате вдали от оптимума эффективность метода повышается, мы быстреє попадаем в район оптимума, в окрестности которого зффективность метода снижается из-за частой смены направлення поиска й приближается к зффективности метода гра диента.
Метод, как и все градиентные метод, обладает невьісокой зффективностью в овражньїх функциях. В ряде случаев можно повисить скорость вихода в район оптимума предьявлением невисоких требований к точности поиска шіп по направлению (задается величиной h — шагом поиска по направлению).
Условием окончания может являться малость модуля градиента R(х) |gгаd R(x)|< . Можно также использовать и малость приращений по переменннм в результате шага, но только в том случае, если на данном шаге мы "проскочили" оптимум, иначе может сказаться, что малость шага обусловлена не близостью к оптиму му, а малостью коэффициента пропорциональности шага h.
В ряде случаев используют уменьшение шага поиска оптиму ма по направлению после каждой смены направлення. Это позво-ляет с большей точностью каждьій раз находить оптимум, но рез-ко снижает зффективность поиска в овражньїх функциях. Метод используется для локализации "дна оврага" в специальньїх ов ражньїх методах. Условием окончания поиска в зтом случае явля ется достижение заданной малой величини шага.
Одна из возможнмх траекторий поиска минимума двумерной функции методом наискорейшего спуска приведена на рис. 17.
Метод базируется на аналогии с движением "тяжелого" материального шарика по наклонной поверхности. Скорость шарика при движении вниз будет возрастать, и он будет стремиться занять нижнее положение, т.е. точку минимума. При выводе дифференциального уравнения движения шарика учитывается его масса и вязкость среды, которые влияют на характер его движения, т.е. поиска min R(x).
В дискретном варианте траектория поиска описывается сле дующим алгоритмом:
При = 0 метод превращается в обыкновенный градиентный. При = 1 поиск не затухает, следовательно, при 0 < < 1 можно получать различную эффективность метода, которая будет зависеть и от h. Вдали от оптимума поиск будет ускоряться, а вблизи возможны колебания около точки min R(x).
К недостаткам метода относится необходимость задания сразу двух неформальных параметров, определяющих эффективность поиска. К достоинствам метода, помимо ускорения движения вдали от оптимума, относится возможность "проскока" мелких локальных "ямок" (минимумов) за счет "инерционности шарика", т.е. можно решать и задачу глобальной оптимизации для функции R(x) с одним явно выраженным минимумом и многими "мелкими".
Одна из возможных траекторий поиска минимума двумерной функции методом тяжелого шарика приведена на рис. 17.
МНОГОМЕРНАЯ БЕЗГРАДИЕНТНАЯ ОПТИМИЗАЦИЯ
В данном разделе рассматриваются численные методы опти мизации, у которых величина и направление шага к оптимуму формируются однозначно по определенным детерминированным функциям в зависимости от свойств критерия оптимальности в окрестности текущей точки без использования производных (т.е. градиента). Все алгоритмы имеют итерационный характер и вы ражаются формулой
Основная особенность рассматриваемой группы методов — отсутствие вычисления градиента критерия оптимальности. Ряд методов прямого поиска ба зируется на последователь ном применении одномер ного поиска по переменным или по другим задаваемым направлениям, что облегча ет их алгоритмизацию применение. Как и для градиентных методов, на рис.18 приводятся лишь по одной из возможных траекторий поиска каждым из ниже рассматриваемых методов. Кроме того, также для всех приведенных траекторий выбраны различные начальные условия, с тем чтобы не загромождать построения.
Рис. 18. Иллюстрация траекторий поиска минимума функции безградиентными детерминированными методами: 1 — оптимум; 2 — траектория метода параллельных ка сательных; 3 — траектория метода Гаусса — Зайделя; 4 — траектория метода Розенброка; 5 — траектория симплексного метода; 6 — начальные точки поиска
МЕТОД ГАУССА — ЗАЙДЕЛЯ
Метод Гаусса — Зайделя (в математической литературе ис пользуется и другое название — метод покоординатного спуска) заключается в последовательном поиске оптимума R(x) пооче редно по каждой переменной. Причем после завершения перебора всех переменных (т.е. после завершения одного цикла) опять в общем случае приходится перебирать все переменные до тех пор, пока не придем к оптимуму.
В ряде случаев (для сепарабельных критериев оптимальности, т.е. таких R(x1 , x2,,..,xi,...,хn), которые можно представить в виде
удается получить решение всего за один цикл. В случае тесной нелинейной взаимосвязи переменных (например, при наличии произведения переменных и т.п.) для получения решения приходится делать очень много циклов.
Метод обладает низкой эффективностью в овражных функциях, может застревать в "ловушках", особенно при сравнительно больших шагах h при поиске оптимума по каждой переменной, очень чувствителен и к выбору системы координат. Метод прост в реализации. На эффективность метода влияет порядок чередо вания переменных.
Условием окончания поиска является малость изменения критерия оптимальности за один цикл или невозможность улучшения критерия оптимальности ни по одной из переменных.
В двумерных задачах метод Гаусса — Зайделя фактически сводится к методу наискорейшего спуска, так как в обоих методах траектория поиска представляет собой последовательность вза-имноортогональных отрезков.
МНОГОМЕРНАЯ УСЛОВНАЯ ОПТИМИЗАЦИЯ
В данном разделе рассматриваются численные методы построения улучшающих последовательностей при наличии огра ничений типа равенств (связей) и типа неравенств (ограничений) (рис. 20). Сюда не входят методы, использующие условия оптимальности. Во всех методах строится в допустимой области последовательность точек, в которых значения критерия улучшаются. Поиск осуществляется градиентным методом. При этом предполагается, что учащийся знаком с особенностями и усло виями работы этого метода по крайней мере в объеме соответ ствующего раздела настоящего пособия.
Допустимая область может формироваться автономными ог раничениями
Xi min Xi Xi max,
связями f (x1, x2, ..., xn) = 0 (j = 1,..., т)
и. ограничениями Fj(x1, x2, ..., xn) 0, для j = 1,...,p.
Рис. 20. Иллюстрация траекторий поиска минимума функции при наличии ограничений типа неравенств: 7 — допустимая область; 2 — запрещенная область; 3 — траектория метода проектирования градиента; 4 — оптимум 1; 5 — траектория метода штрафов; 6 — траектория прямого метода с возвратом; 7 — оптимум 2; 8 — начальные течки поиска
Функции, задающие ограничения, могут формировать допустимую область с различными свойствами: монотонными, колебательными, с большой и малой кривизной и т.д., что оказывает влияние на эффективность методов поиска.
Метод штрафов позволяет перейти от исходной задачи с ограничениями к другой задаче без ограничений путем формирования новой структуры критерия оптимальности. Оптимальное решение новой задачи совпадает с решением исходной задачи и принадлежит исходной допустимой области.
Пусть имеем задачу
Формируется новый критерий, например с квадратичным "штрафом" для ограничений типа равенств:
с модульным "штрафом":
с комбинированным "штрафом":
(индексы суммирования для простоты опущены), где — коэффициент "штрафа". Он характеризует вклад в общий критерий оптимальности. Rp — новый критерий, F_(x) — срез функции F(x); он определяется по следующему правилу:
Отклонения от ограничений увеличивают критерий Rp, т.е. как бы накладывают "штраф" Н на Rp. Уменьшение Rp происходит как за счет уменьшения R(x}, так и за счет уменьшения величины нарушения ограничения.
В точке минимума ограничения будут справедливы, т.е. равны нулю, и поэтому R * = Rp*. Однако это соотношение будет справедливо только при коэффициенте "штрафа", стремящемся к бесконечности.
Увеличение , с одной стороны, не допускает больших откло нений в "запретные" стороны от ограничений (это хорошо), а с другой — увеличивает "овражность" Rp (овраг размерности m имеет место вдоль ограничений), что резко усложняет поиск оп тимума Rp (это плохо).
Поэтому целесообразно решать задачу сначала с маленьким значением , потом его увеличивать. Это будет способствовать более быстрому выходу в область условного оптимума и точному его определению.
Существуют и другие структуры Rp, в частности учитываю щие сравнительную важность отдельных ограничений. При этом каждое ограничение может иметь свой коэффициент штрафа.
При решении практических задач можно сначала задавать меньшее значение , при этом поиск быстрее выйдет в район оп тимума, а затем увеличивать коэффициент штрафа, что позволит точнее найти решение.