MMTS_Lectures_M

5) если результат с заданной точностью получен, то решение закончено или иначе по последнему и предпоследнему приближениям находится новое направление поиска и делается переход на пункт 4.

Для выполнения поворота осей используют ортогонализацию по Граму-Шмидту.

Рисунок 3.13 – Графическая интерпретация метода Розенброка

Метод Пауэлла основан на определении направлений поиска путем проведения касательных к изолиниям (изоповерхностям), параллельных друг другу. Линия, соединяющая точки касания определяет текущее направление поиска Z1. Графическое представление метода приведено на рисунке 3.14.

Рисунок 3.14 – Графическая интерпретация метода Пауэлла

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

Метод наискорейшего спуска – один из методов с переменным шагом (рисунок 3.15). Шаг принимается с учетом степени изменения целевой функции в направлении поиска:

Hi = h Si Gi,

где i – номер переменной;

Hi – величина шага поиска;

h – относительное значение шага поиска;

Si – принятая шкальность изменения переменных; Gi – значение антиградиента функции по хi.

Шаг Hi остается постоянным до тех пор, пока значение функции убывает (растет).

Рисунок 3.15 – Графическая интерпретация метода наискорейшего спуска

Шкальность определяется зависимостью Si = (xв – xн)i bш , где xн, xв – соответственно принятая нижняя и верхняя граница интервала поиска; bш – коэффициент, определяющий шкальность по переменным.

Имеется ряд методов оптимизации на основе случайного поиска. Ниже приведен алгоритм метода случайного поиска с пересчетом. В алгоритме приняты обозначения: r – псевдослучайное число с равномерным законом распределения в интервале от 0 до 1.0; Si – шкальность изменения xi ; Xт = {xтi} – текущее значение X; Xп = {xпi} – текущее приближение

крешению X.

3.3.Оптимизация при наличии ограничений

Вотличие от безусловной оптимизации в данном случае установлены ограничения в виде равенств и (или) неравенств в зависимости от X.

Вэтом случае задача состоит в поиске экстремума функции

при выполнении ограничений вида

Oj = j(X ) <= >bj, j 1,n .

Аналитическое решение задачи при ограничениях типа равенства и дифференцируемости оптимизируемой функции возможно по методу Лагранжа. Для этого вводятся множители Лагранжа j и с их применением формируется функция L по выражению:

n

L= f(X) - j j(X),

j=1

где j(X )=0.

Оптимальные значения вектора X определяются системой m+n уравнений:

Без учета ограничений аналитический метод дает решение в точке x1 = 1.0 ; x2 = 1.0. Графическое представление полученных решений приведено на рисунке 3.16.

В случае, если ограничения имеют вид неравенств, необходимые условия нахождения экстремума (минимума) функции f(X) при ограничениях j (X) bj следующие:

ограничения в виде неравенств преобразуются в ограничения в виде равенств путем добавления дополнительных (ослабляющих) переменных u2j (u2j > 0) к виду:

и система уравнений, решение которой определяет точку оптимума

Условия решения такой задачи известны как условия Куна-Такера.

Рисунок 3.16 – Графическое представление решения по методу Лагранжа

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

Для получения эффективных и надежных методов требуются более сложные процедуры. Одним из методов решения является модификация метода Нелдера-Мида, разработанная Боксом (назван комплексным методом). Метод основан на выборе 2m точек, удовлетворяющих ограничениям, и называемых комплексом.

Метод прямого учета ограничений успешно может быть применен при оптимизации

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

Например, на Бейсике подпрограмма без учета ограничений и с учетом ограничений будет при оптимизации на минимум следующей:

Задача с ограничениями может быть сведена к задаче без ограничений с помощью "штрафных" функций. Идея внутренних штрафных функций состоит в формировании

целевой функции Zш по Z = f(X)= min и ограничений j (X) > 0 ( j 1,n ):

n

Zш = f(X) + Pш =min; Pш = r 1/ j(X);

j=1

n

Zш = f(X)+ r 1/ j (X) =min,

j=1

где r – положительная малая величина; Pш – дополнительная штрафная функция.

Если значения Х близкие или равные ограничению, то происходит резкое изменение (увеличение) функции Zш (образуется "гребень" с крутыми краями). Графическая интерпретация приведена ниже на рисунке 3.18.

2 1

Zш

3

x

Рисунок 3.18 – Графическая интерпретация метода штрафных функций:

1 – линия ограничения; 2 – функция Zш при большем значении r; 3 – функция Zш при меньшем значении r

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

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

3.4. Задача линейного программирования

Задача линейного программирования – это оптимизационная задача с линейной целевой функцией и линейными ограничениями в виде равенств или неравенств:

целевая функция

m

Z= ci xi max(min), i 1,m

i 1 xi

и ограничения

где xi, i 1,m – вектор оптимизируемых управляемых параметров; сi – удельные эффекты или затраты, приходящиеся на единицу xi ; aij и bi – параметры (коэффициенты) ограничений;

m – общее число оптимизируемых параметров; n – общее число ограничений.

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

Пример.

Автомобиль при работе на объекте 1 имеет производительность 20 единиц, на объекте 2 – 25 единиц. На этих объектах необходимо освоить объем перевозок не более чем 175 единиц. Общее число автомобилей, задействованных на перевозках, не должно превышать 8 единиц. Эффект от работы автомобиля на 1-м объекте составляет 5 единиц; на 2-м – 6 единиц. Требуется найти оптимальный вариант распределения автомобилей по объектам перевозок.

Пусть x1 – число автомобилей для работы на 1-м объекте и x2 – на 2-м объекте. Тогда задача в математической форме имеет вид:

5 x1 + 6 x2 = max – целевая функция.

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

Алгоритм графического метода следующий:

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

2)строится изолиния целевой функции для произвольного ее значения;

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

Рассмотрим графическое решение на вышеприведенном примере (рисунок 3.19). Строим линии ограничений и исключаем запрещенные области.

1 ограничение:

x1 = 0; x2 = 175/25 = 7; x2 = 0; x1 = 175/20 = 8.75. 2 ограничение:

x1 = 0; x2 = 8; x2 = 0; x1 = 8.

Кроме того, ограничениями являются оси координат, так как x1 0; x2 0 .

Полученная незапрещенная область (на рисунке затемненная) – область допустимых решений.

Строим изолинию целевой функции. Пусть Z = 30, тогда

x1 = 0; x2 = 5 ; x2 = 0; x1 = 6.

Перемещая изолинию параллельно все выше и выше, находим наибольшее значение Z, когда изолиния только касается многоугольника допустимых решений и имеется хотя бы одна общая точка с ним. Точка "В", в которой x1 = 5 и x2 = 3 соответствует оптимальному

77

решению поставленной задачи. Если линия уровня целевой функции касалась бы многоугольника допустимых решений не в точке, а по линии – то мы имели бы случай, когда задача имеет множество решений. Если ограничения задачи противоречивы, то задача не имеет решения (например, 1-е ограничение 20 х1 + 25 х2≥ 500).

При изменениях коэффициентов целевой функции оптимальное решение может

5x1 + 5 x2 = max – множество точек отрезка [В, C] и при функции 10x1 + 6 x2 = max решение в точке С.

При числе оптимизируемых параметров более двух мы имеем дело с выпуклым многогранником ограничений (при m = 3 ограничения определяются плоскостями, допустимая область – выпуклым многогранником, уровень целевой функции – плоскостью, решение – касание допустимой области плоскостью целевой функции).

Для решения задачи в m-мерном пространстве применяется симплекс-метод.

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

x2

8

6

изолиния целевой функции

5

4

ВВ

3

1-е ограничение

2

1

Рисунок 3.19 – Графическое решение общей задачи линейного программирования

Для применения симплекс-метода исходная задача приводится к каноническому (стандартному) виду путем ввода дополнительных переменных по числу ограничений в виде неравенств из общего числа n. Цель – заменить ограничения типа неравенств ограничениями типа равенств. Стандартная форма задачи имеет вид:

целевая функция

M

Z = ci xi max (min),

i 1

ci = 0 для i m 1,M;

ограничения

Например, стандартная форма для ранее приведенной задачи следующая:

20 x1+ 25 x2 + 1 x3+ 0 x4 = 175 x1 + x2 + 0 x3+ 1 x4 = 8

Z = 5 x1+ 6 x2 + 0 x3+ 0 x4 = max.

Основные шаги решения задачи (после представления исходной системы в стандартном виде):

1)формируется первоначальное базисное решение;

2)выражается Z через небазисные переменные;

3)проверяется базисное решение на оптимальность. Если оптимально, то на п.10;

4)проверяется задача на наличие решения. Если решения нет, то выход;

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

6)определяется базисная переменная, которая должна выводится из базиса;

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

8)алгебраически выражаются другие базисные переменные через небазисные;

9)переход на п. 2;

10)определяются значения базисных переменных. Они являются решением задачи. Итерационный процесс (шаги 2–9) повторяются до тех пор, пока не произойдет выход на

шаге 3 или 4.

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

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

качестве небазисных – основные, т.е. u m 1,M и p 1,m. Базисные переменные xu выражаются через небазисные xp из равенств, в которые они входят через значимые коэффициенты. При этом небазисные переменные принимаются нулевыми. Тогда первое базисное решение

xm+1 = b1;

xm+2 = b2;

. . .

xM = bn; x1 = 0; x2 =.0;. . xm = 0.

Шаг 2 – алгебраически выражается целевая функция Z через небазисные переменные

Z= cpxp max .

p

Шаг 3 – проверяется все ли сp≤0. Если да, то решение оптимально.

Шаг 4 – оценка наличия решения. Если при хp, имеющем сp >0, во всех уравнениях apj<0

( j 1,n ), то решение отсутствует (выход из программы с соответствующим сообщением). Шаг 5 – определяется та небазисная переменная, которую наиболее целесообразно ввести

в базис, по максимуму положительного коэффициента в текущем выражении для целевой

функции max cp cs , где s– номер переменной, вводимой в базис.

p

Шаг 6 – определяется одна из базисных переменных для вывода ее из базиса. Для этого во всех текущих j-х равенствах для хs вычисляется отношение свободного члена bj к соответствующему коэффициенту asj (asj >0), т.е. bj/asj. Минимальное из отношений указывает на j-е равенство и соответственно на выводимую переменную из базиса.

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

3)поскольку 5>0 и 6>0, то решение неоптимально;

4)так как a1.1 > 0 , a1.2 > 0 , a2.1 > 0 и a2.2 > 0, то не следует, что решения нет;

5) поскольку 6>5 и поиск на max, то вводим в базис x2 ;

6)исходя из минимума соотношений (175/25=7 в первом уравнении и 8/1=8 во втором) необходимо выводить из базиса переменную x3 (1-е уравнение);

7)выражаем x2 = (175-20.x1 -x3 )/25 = 7-0.8.x1-0.04.x3 (уравнение 0.8.x1+0.04.x3+ x2 =7);

8)выражаем другие базисные через небазисные x4 = 8 - x1 -x2 = 8 -x1 -(7- 0.8.x1 - 0.04.x3) = = 1- 0.2.x1 + 0.04.x3 (уравнение 0.2.x1 - 0.04.x3 + x4 =1);

9)переход на шаг 2.

2-я итерация:

2)целевая функция Z = 5 x1 + 6 x2 = 5 x1 + 6 ( 7- 0.8.x1 - 0.04.x3) = 42 + 0.2.x1 - 0.24.x3;

3)поскольку 0.2>0, то решение неоптимально;

4)так как при x1 (c1> 0) a1.1 > 0 и a1.2 > 0 (для текущих уравнений, приведенных к основному виду со свободным членом в правой части), то не следует, что решения нет;

5)поскольку 0.2>-0.24 и поиск на max, то вводим в базис x1 ;

6)исходя из минимума соотношений 7/0.8=8.75 в первом уравнении и 1/0.2=5 во втором необходимо выводить из базиса переменную x4;

7)выражаем x1: x1 = (1+ 0.04.x3 -x4 )/0.2 = 5 + 0.2.x3 - 5.x4;

8)выражаем другие базисные переменные через небазисные

x2 = 7- 0.8.x1 - 0.04.x3 =7 - 0.8.(5 + 0.2.x3 - 5.x4)- 0.04.x3 = 3 - 0.20.x3 + 4.x4;

9) переход на шаг 2.

3-я итерация:

2)целевая функция Z=5 x1 + 6 x2 = 5 (5 + 0.2.x3 - 5.x4)+6 (3 - 0.20.x3 + 4.x4) = 43 - 0.2.x3 - 1.x4;

3)поскольку -0.2 <0 и -1 <0, то решение оптимально;