Целевая функция 2 страница

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

Метод равномерного перебора

Пусть дана функция (см. рис 7.1).

Рис.7.1. Графическая иллюстрация метода равномерного перебора

В соответствии с данным методом алгоритм поиска заключается в следующем. Фиксируют величину шага . Вычисляют значения целевой функции в точках и и . Полученные значения сравнивают. Запоминают меньшее из этих двух значений. Далее выбирается точка и в ней вычисляется значения целевой функции . Сравнивается оставшееся на предыдущем шаге значение и значение . Наименьшее из них опять запоминают. Так поступают до тех пор, пока очередное значение не превысит . Последнее оставшееся значение является приближенным значением глобального минимума.

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

Метод золотого сечения

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

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

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

Рис.7.3. Иллюстрация обоснования исключения отрезков

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

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

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

Рис.7.4. Иллюстрация обоснования расположения точек на отрезке

Выбирая на первом шаге сравниваемые точки слишком близко к середине отрезка , мы исключим из рассмотрения большой отрезок для случая 1 или для случая 2. Но на втором шаге величина исключаемого отрезка значительно уменьшится (будет исключен отрезок для случая 1 или отрезок для случая 2).

Таким образом, с одной стороны, точки следует брать рядом с серединой отрезка, а, с другой стороны, слишком близко друг от друга их брать нельзя. Т.е. необходимо найти некую «золотую середину».Для этого рассмотрим для простоты вместо отрезка отрезок [0,1] единичной длины – рис.7.5.

Рис.7.5. Обоснование «золотой середины» расположения точек на отрезке

На этом рисунке .

Для того, чтобы точка B была «выгодной» как на данном , так и на следующем этапе (шаге), она должна делить отрезок AD в таком же отношении, как и AC: AB/AD = BC/AC. При этом в силу симметрии аналогичным свойством будет обладать и точка C: CD/AD = BC/BD. В обозначениях координаты x эти пропорции принимают вид: x/1 = (1 – 2x)/(1 – x). Решим эту пропорцию:

Корни этого уравнения равны:

не приемлем, т.е. уравнение имеет один корень.

О точке, которая расположена на расстоянии длины от одного из концов отрезка, говорят, что она осуществляет «золотое сечение» данного отрезка.

Очевидно, что каждый отрезок имеет две такие точки, расположенные симметрично относительно его середины.

Итак, алгоритм метода «золотого сечения» заключается в следующем (см. также рис.7.6). На исходном отрезке [a,b] выбираются две точки x₁ и x_{2 ,} так, чтобы выполнялось приведенное выше соотношение «золотого сечения» этого отрезка. Вычисляются значения целевой функции в этих точках – и . Они сравниваются, и из дальнейшего рассмотрения исключается отрезок, прилегающий к точке, дающей большее значение целевой функции (здесь отрезок [x₂,b] ). Т.е. исходный отрезок [a,b] «стягивается» до отрезка [a,b₁]. Для этого нового отрезка находится его середина, и по отношению к ней симметрично оставшейся точке x₁ ставится точка x₃. Для нее рассчитывается значение целевой функции и сравнивается с . Из дальнейшего рассмотрения опять исключается отрезок, прилегающий к точке с большим значением целевой функции, здесь это отрезок [a,x₃]. Текущий отрезок «стягивается» до нового отрезка, здесь это [a₁,b₁] и т.д.

Рис.7.6. Иллюстрация алгоритма метода «золотого сечения»

Метод «золотого сечения» прост, эффективен и широко применяется в практической оптимизации.

Лекция 8

Численные методы решения задач нелинейного программирования (поиск экстремума функции n – переменных)

Метод линеаризации (приведения задачи нелинейного программирования к задаче линейного программирования)

Данный метод строго не относится к численным методам решения задач оптимизации. Но он эффективен и часто используется для решения практических задач. Рассмотрим суть данного метода на примере, который решался в лекции 5. Напомним формулировку задачи:

найти и . Целевая функция , ограничения:

1 этап. Приводим данную задачу к задаче линейного программирования. Для этого проводим логарифмирование ограничений и целевой функции:

После вычислений получим:

(8.1)

(8.2)

(8.3)

После логарифмирования целевой функции:

Далее задача решается с применением симплекс - алгоритма или графо – аналитически (см. рис.8.1 и вычисления, сопровождающие построения). Для построения области допустимых решений (ОДР) в логарифмических координатах работаем с ограничениями (8.1) – (8.3). Ограничения (8.1) и (8.2) – это ограничения, графически представляющие собой прямые линии, параллельные соответственно осям и . Причем, левая ограничительная линия в ограничении (8.1) совпадает с осью . Ограничение (8.3) представляет собой прямую линию, наклонную под углом 45 градусов к осям, имеющая координаты пересечения осей «0-1». Для нахождения точки касания линии, соответствующей целевой функции, сначала строим «произвольную» линию для целевой функции, приравнивая ее выражение к произвольному числу в данном масштабе. Приравняем выражение для целевой функции к числу «1,2»:

		0,3
	1,2	1,5

Далее строим линию, параллельную данной линии и касающуюся границы ОДР. Находим координаты точки касания:

Если целевая функция стремится к минимуму, т.е. , то прямая линия, соответствующая ей, коснется границы ОДР в точке с координатами:

.

Рис.8.1. Графическая иллюстрация графо - аналитического решения задачи оптимизации методом линеаризации

Метод покоординатного спуска в задачах без ограничений

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

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

Согласно этому методу направления спуска выбирается параллельно координатным осям, т.е. сначала спуск осуществляется вдоль первой оси ОХ₁ затем вдоль второй оси ОХ₂ и т.д. до последней оси ОХ_n.

Пусть – начальная точка (см. рис. 8.2), a – некоторое положительное число. Вычисляют значение целевой функции в этой точке – . Далее вычисляют значение целевой функции при и проверяют выполнение неравенства

(8.4)

Если это неравенство справедливо, то вдоль направления оси OX₁ значение функции f уменьшилось, и поэтому полагают x⁽¹⁾ = x⁽⁰⁾ + a. Если неравенство (8.4) не выполняется, то делают шаг в противоположном направлении и проверяют выполнение неравенства

(8.5)

В случае выполнения этого неравенства полагают x⁽¹⁾ = x⁽⁰⁾ - a. Если оба неравенства и (8.4), и (8.5) не выполняются, то x⁽¹⁾ = x⁽⁰⁾.

Рис.8.2. Графическая иллюстрация поиска точки минимума методом покоординатного спуска

Второй шаг производят вдоль координатной оси OX₂. Вычисляют значение функции в точке (x⁽¹⁾ + a) и сравнивают его с предыдущим значением, т.е. проверяют выполнение неравенства

(8.6)

Если это неравенство выполняется, то полагают x⁽²⁾ = x⁽¹⁾ + a. Если оно не выполняется, то делают шаг в противоположном направлении и проверяют выполнение неравенства

(8.7)

В случае выполнения неравенства (8.7) считают, что x⁽²⁾ = x⁽¹⁾ – a. Если оба неравенства и (8.6), и (8.7) не выполняются, то принимают x⁽²⁾ = x⁽¹⁾.

Так перебирают все n – направлений координатных осей. На этом первая итерация закончена. На n - м шаге будет получена некоторая точка x⁽ⁿ⁾. Если , то аналогично, начиная с x⁽ⁿ⁾ осуществляют вторую итерацию. Если же x⁽ⁿ⁾ = x⁽⁰⁾ (это имеет место, если на каждом шаге ни одно из пары неравенств не окажется выполненным), то величину шага нужно уменьшить, взяв, например, a_n+1 = a_n/2, и в следующей итерации использовать новое значение величины шага.

Последующие итерации выполняют аналогично. На практике вычисления прекращают при выполнении какого – либо условия окончания счета, например

,

где f(x)_(k+1) – значение целевой функции на (к+1) итерации;

f(x)_(k) – значение целевой функции на к –ой итерации;

- некоторое положительное число, характеризующее точность решения исходной задачи

минимизации целевой функции.

Метод покоординатного спуска в задачах с ограничениями

Данный метод распространяется на задачи, с простыми ограничениями типа:

(8.8)

(8.9)

. . .

(8.10)

Основные процедуры данного метода аналогичны предыдущему методу. Различие заключается в том, что наряду с проверкой выполнения неравенств f(x⁽⁰⁾ + a) < f(x⁽⁰⁾) (f(x⁽⁰⁾ – a) < f(x⁽⁰⁾)), f(x⁽¹⁾ + a) < f(x⁽¹⁾) (f(x⁽¹⁾ – a) < f(x⁽¹⁾)) и т.д. осуществляют проверку выполнения неравенств (8.8) – (8.10). Выполнение или невыполнение этих неравенств приводит к тем же последствиям, что и выполнение или невыполнение неравенств, приведенных выше.

Лекция 9

Методы решения многокритериальных задач оптимизации

Эта задачи проектирования (оптимизации), в которых используется не один, а несколько критериев. На практике такие задачи возникают, когда проектируемый объект не может быть описан однокритериальной зависимостью, или объединить отдельные критерии в единый критерий не представляется возможным. Такое объединение критериев в единый критерий применяется, и оно будет рассмотрено ниже. Но это объединение, как правило, бывает формальным, искусственным. С математической точки зрения не существует идеального способа, метода решения таких задач. Каждый из них имеет преимущества и недостатки. Рассмотрим некоторые методы решения многокритериальных задач оптимизации.

Метод поиска Парето – эффективных решений

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

Пусть имеется множество вариантов решения. По каждому из вариантов определены значения всех критериев. Представим множество оценок вариантов решения в пространстве критериев (рис.9.1).

Рис.9.1. Иллюстрация поиска Парето – эффективных решений

На рис.9.1 приняты следующие обозначения:

К₁ и К₂ – критерии оценки вариантов решения;

Y = {y₁, y₂, …, y_m}- множество оценок альтернативных вариантов решения;

К₁₁, К₁₂, … , К_1m - значения первого критерия для 1, 2, … , m - го варианта решения;

К₂₁, К₂₂, … , К_2m – значения второго критерия для 1, 2, … , m - го варианта решения;

P(Y) – множество Парето – эффективных оценок решений.

Правило. Множество Парето – эффективных оценок P(Y’) представляет собой «северо – восточную» границу множества Y без тех его частей, которые параллельны одной из координатных осей или лежат в «глубоких» провалах .

Для случая, изображенного на рис.9.1, Парето – эффективные оценки состоят из точек кривой (bc), исключая точку (c), и линии (de).

Преимущества метода: 1) Критерии равнозначны; 2) Метод математически объективен.

Недостаток метода: 1) Одно окончательное решение получается только в частном случае, т.е. количество Парето – эффективных решений, как правило, более одного.

Пример. Имеется 10 вариантов металлорежущих станков, среди которых для проектируемого участка необходимо выбрать наилучший. Станки оценены экспертами по двум показателям (критериям): производительности и надежности. Оценивание производилось по 11 - бальной шкале от 0 до 10. Результаты оценки станков приведены в таблице 9.1.

Таблица 9.1 Экспертные оценки станков по критериям производительности и надежности

Представим множество оценок вариантов металлорежущих станков в пространстве критериев (рис.9.2):

Парето – эффективными решениями здесь являются варианты станков С₅, С₇ и С₉.

Рис.9.2. Пример поиска Парето – эффективных решений

Метод решения многокритериальных задач оптимизации с использованием обобщенного (интегрального) критерия

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

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

В зависимости от того, каким образом частные критерии объединяются в обобщенный критерий различают следующие виды обобщенных критериев:

1. Аддитивный критерий;

2. Мультипликативный критерий;

3. Максиминный (минимаксный) критерий.

Аддитивный критерий

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

где n – количество объединяемых частных критериев;

– весовой коэффициент – го частного критерия;

– числовое значение – го частного критерия;

– – й нормирующий делитель;

– нормированное значение – го частного критерия.

Частные критерии имеют различную физическую природу и поэтому различную размерность. А значит просто суммировать их некорректно. В связи с этим в предыдущей формуле числовые значения частных критериев делятся на некоторые нормирующие делители, которые назначается следующим образом:

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

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

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

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

Таблица 9.2. Исходные данные для определения оптимального варианта исполнения машины

Целевая функция на основе аддитивного критерия запишется следующим образом:

В качестве нормирующих делителей в данной задаче примем наилучшие (максимальные) значения частных критериев:

.

Значения обобщенного аддитивного критерия рассчитываются для каждого варианта машины:

Вариант 1.

F(X) = 0,6(1000/4000) + 0,4(1500/1500) = 0,55.

Вариант 2

F(X) = 0,6(2000/4000) + 0,4(1000/1500) = 0,558.

Вариант 3

F(X) = 0,6(4000/4000) + 0,4(500/1500) = 0,732.

Оптимальным является 3 вариант машины, т.к. ему соответствует максимальное значение обобщенного аддитивного критерия.

Один из недостатков этого метода заключается в том, что весовые коэффициенты назначает проектировщик. Разные проектировщики могут назначать разные весовые коэффициенты. Пусть, например, C₁ = 0,4; C₂ = 0,6. Определим теперь значения аддитивных критериев для вариантов машины:

Вариант 1.

Вариант 2.

Вариант 3.

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

Преимущество данного метода: как правило, всегда удается определить единственный оптимальный вариант решения.