Решебник_МО

6. Дана следующая функция Экли (n = 30):

(30, 200)-селекция. Алгоритм эволюционных стратегий. Останов после 200000 оценок функции.

7. Дана следующая функция Экли (n = 30):

Размер популяции 200. Применить алгоритм эволюционного программирования. Останов после 200 000 оценок функции.

8.Исследовать задачу многокритериальной оптимизация, состоящую в получении эффективных или Парето-оптимальных решений, из которых затем с учетом субъективных или иных предпочтений принимается к реализации единственное решение в предположении, что заданы g целей. Одна из возможных эволюционных стратегий состоит в том, что селекция новой популяции разделяется на g отдельных этапов для каждой целевой функции. Если выбирать μ/g индивидов, характеризующих отдельную цель в предположении одинаковой важности целей, то это соответствует (μ, λ)-селекции. Учесть, что важность («вес») отдельных целей может быть различной, изменяя долю селектируемых индивидов в популяции в соответствии с «весом» той или иной цели.

9.Решить с помощью эволюционного алгоритма задачу о размещении на шахматной доске 8 ферзей.

111

ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ

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

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

ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Совокупность ограничений-неравенств в задаче ЛП определяет некоторую многоугольную область G. Область G называется областью решений системы ограничений-неравенств и является выпуклой областью.

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

Если задана функция Z = с1х1+c2x2 и совместная система линейных неравенств с двумя переменными, то решением задачи линейного программирования будут такие точки Х* = (х1,x2) среди множества точек из области решений совместной системы неравенств, которые придают линейной функции Z наименьшее (наибольшее) значение. Для каждой точки плоскости функция Z принимает фиксированное значение Z=Z1. Множество всех таких точек есть прямая с1х1+c2x2 = Z1, перпендикулярная вектору С(c1,c2), выходящему из начала координат. Если эту прямую передвигать параллельно самой себе в положительном направлении вектора С, то функция Z=c1x1+c2x2=Z1, будет возрастать, а в противоположном направлении – убывать.

Минимизация и максимизация функции Z = с1x1+c2х2 на многоугольнике решений достигается в точках пересечения этого

112

СИМПЛЕКС-МЕТОД

Симплекс-метод является универсальным методом решения n- размерных задач линейного программирования.

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

ПРОЦЕДУРА ЗАМЕНЫ ПЕРЕМЕННЫХ

Каждую задачу ЛП можно задать в виде матрицы условий, где i-й столбец соответствует независимой переменной хi, i=l,n, крайний правый столбец содержит свободные члены bj ограничений хj (xj=

n

a ji xi b j , j = n+1,…,n+m), Каждая j-я строка, соответствующая

i 1

зависимой переменной хj, содержит коэффициенты j-го ограничения хj (aji), а последняя Z-строка содержит коэффициенты сi, входящие в целевую функцию Z.

Матрица условий имеет вид (табл. 10):

Таблица 10

В задаче ЛП точками, подозрительными на экстремум, являются все вершины многогранника допустимой области G. Симплекс-метод позволяет находить экстремальное значение целевой функции за конечное число шагов, причем каждый последующий шаг улучшает значение целевой функции, полученное на предыдущих шагах. Под шагом понимается процедура замены переменных, когда в качестве r-й независимой переменной принимается не xr, а некоторая зависимая переменная, скажем, xn+s. Такая процедура замены одной независимой переменной называется шагом жорданова исключения (ЖИ). Если провести замену независимой переменной xr, на

114

зависимую xn+s, то матрица условий изменится и будет иметь вид

(табл. 11):

Таблица 11

Элемент asr называется разрешающим элементом, r-й столбец – разрешающим столбцом, а s-я – разрешающей строкой. Элементы а`ji и

Правила перехода от табл. 9 к табл.10 следующие:

1)разрешающий элемент заменяется единицей;

2)остальные элементы разрешающего r-го столбца остаются без изменений;

3)остальные элементы разрешающей s-й строки меняют лишь свои знаки;

4)элементы a`ji и b`j, не принадлежащие разрешающей строке или столбцу, вычисляются по формулам (6);

5)все полученные элементы делятся на разрешающий элемент asr, Совокупность независимых переменных определяет собой

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

системой уравнений {xs+n = 0, xi = 0, i r }.

Можно говорить, что при замене независимой переменной xr на зависимую xs+n = 0 происходит движение из начала координат по оси х до встречи с гиперплоскостью xs+n = 0, и полученная точка определяет новое начало координат. При этом значение xs+n теперь определяется выражением xs+n = asr,xr+bs, Величина xr выбирается

такой, чтобы оказалось xs+n = 0, т.е. xr = –bs/asr, что и показано в столбце свободных членов табл.11. Переход от одной системы координат к

115

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

ОСНОВНЫЕ ИДЕИ СИМПЛЕКС-МЕТОДА

Пусть в Rn заданы (n+m) переменных, из которых первые n являются независимыми (базисными), а остальные m зависимыми:

n

x j a ji xi b j , j=n+1, …, n+m,

i 1

n

Необходимо найти max Z= ci xi , при ограничениях xj>0,

i 1

j = n+1,…,n+m.

Составим матрицу условий задачи (см. табл. 10).

В точке xi = 0, i = 1,2,...,n, которая является началом координат, зависимые переменные xj имеют значения xj = bj. Если в табл. 10 все ci 0, тогда maxZ достигается именно в начале координат, поскольку любое положительное приращение xi может только уменьшить величину Z. Значит, признаком оптимальности точки начала координат является неположительность всех коэффициентов Z-строки соответствующей матрицы условий. Однако не каждая такая точка является вершиной многогранника G. Если некоторые свободные члены bj < 0, то не выполняются ограничения xj 0. Следовательно, признаком того, что начало координат является опорным решением ЗЛП, т.е. находится в вершине многогранника G, служит неотрицательность коэффициентов столбца свободных членов матрицы условий.

Решением задачи ЛП будет такое пересечение n граничных гиперплоскостей, при котором все коэффициенты столбца свободных членов будут неотрицательны, а все коэффициенты Z-строки неположительны.

Алгоритм решения ЗЛП симплекс-методом включает три

этапа:

1.Приведение задачи к каноническому виду.

2.Поиск опорного решения.

3.Поиск оптимального решения.

116

СИМПЛЕКС-МЕТОД. ПРИВЕДЕНИЕ ЗЛП К КАНОНИЧЕСКОМУ

ВИДУ

Пусть задана задача ЛП в самом общем случае, когда требуется

n

найти максимум или минимум линейной формы W ciui при

i 1

при ограничениях-равенствах:

n

u j n a ji ui b j 0 , j=l+1, …,m. i 1

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

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

нижней строке коэффициенты целевой функции. В правом нижнем углу матрицы записать 0.

3.Инвертировать знаки во всех i-х столбцах для i=s+1,...,k .

4.Инвертировать знаки во всех j-х строках для j=р+1,...,l.

5.Если требуется найти minW, то инвертировать знаки во всей последней строке матрицы.

6.Переобозначить все независимые переменные, назвав их x1,x2,…,xn, зависимые переменные, назвав их xn+1,xn+2,…,xn+m, и значение

117

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

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

Предположим вначале, что независимые переменные xi, i=k+1,...,n; k n-1 являются свободными, а на все зависимые наложено требование неотрицательности (l = m). Выберем в качестве разрешающего любой отличный от нуля элемент аij в столбце какойлибо свободной переменной xi0 и произведем шаг жорданова исключения. В результате получим новую матрицу со строкой xi0. Выпишем отдельно зависимость xi0 от новой совокупности независимых переменных, после чего i0-ю строку из матрицы можно вычеркнуть. Действительно, после того, как будут определены оптимальные значения несвободных переменных, значение xi0 однозначно определится из выписанного выражения. Это значение будет допустимым; поскольку на xi0 не накладывались никакие ограничения. После k аналогичных шагов жорданова исключения (ЖИ) число зависимых переменных уменьшится на k, а все независимые переменные окажутся несвободными.

Пусть теперь все независимые переменные несвободны (k = n),

n

но условия задачи содержат ограничения-равенства a ji xi b j 0 ,

i 1

т.е. l < m. Без потери общности можно считать, что все свободные члены в равенствах положительны, поскольку соответствующую линейную форму всегда можно умножить на (1).

Сделаем шаг ЖИ с разрешающим элементом asr 0. При этом мы должны двигаться по оси xr в положительном направлении пока не

положительным, a bs>0, то asr должно быть отрицательным. Значит, двигаться можно только по тем осям, которым в s-й строке соответствуют отрицательные коэффициенты. Выбрав любой такой элемент в качестве разрешающего, сделаем шаг ЖИ и перебросим 0-

118

строку наверх матрицы. Это позволит вычеркнуть соответствующий столбец, сократив тем самым число независимых переменных.

Если в s-й строке не оказалось отрицательных переменных, то задача несовместна, так как при asr ≥ 0 и bs ≥ 0 линейная форма не может обратиться в 0.

Если bs = 0, а все неравные нулю asr имеют одинаковые знаки,

которых as i ≠ 0. Поэтому из матрицы следует вычеркнуть все столбцы, содержащие asi ≠ 0, и s-ю строку, полагая для вычеркнутых независимых переменных хi0 = 0. Если же asi имеют разные знаки, то в качестве разрешающего элемента можно выбрать любой

этом случае мы можем вычеркнуть s-столбец. Освобождаясь от 0-строк, мы либо убедимся в несовместности задачи, либо уменьшим количество независимых переменных на число, не меньшее ограничений-равенств.

СИМПЛЕКС-МЕТОД. ПОИСК ОПОРНОГО РЕШЕНИЯ

Упростим матрицу канонической ЗЛП (каноническую матрицу) за счет исключения «слабых» ограничений.

Если в s-й строке все коэффициенты, включая свободный член,

119

несущественным и может быть вычеркнуто из матрицы.

Выявив и исключив из канонической матрицы слабые ограничения, рассмотрим столбец свободных членов. Если все его элементы неотрицательны, то начало координат удовлетворяет всем ограничениям xi 0, i = 1,2,..,n+m, и является опорным решением ЗЛП.

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

Чтобы попасть в новое начало координат, расположенное, по крайней мере, ближе к допустимой области, чем старое, будем двигаться по какой-нибудь координатной оси xr из точки начала координат в направлении к допустимой области до встречи с некоторой гиперплоскостью xs+n = 0. Тогда xs+n = asrxr+bs = 0, откуда

направлении оси xr, то коэффициенты bs и asr в разрешающем столбце должны иметь разные знаки. Чтобы найти такой столбец, достаточно в строке с отрицательным свободным членом bs выбрать любой положительный коэффициент asr и r-й столбец считать разрешающим.

Приближение ко всем отделяющим гиперплоскостям при движении по оси xr будет обеспечено лишь в том случае, если в разрешающем столбце xr отсутствуют отрицательные коэффициенты аνμ < 0 в строках с отрицательным свободным членом bν < 0. В

противном случае при xr > 0 получим xν+n = – aνr xr – bν < – bν, т.е. новое начало координат отдалится от гиперплоскости хν+μ = 0, и на оси xr

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

Если в s-й строке с отрицательным свободным членом bs< 0 все asi ≤ 0, i = 1,2,...,n, то задача ЛП является недопустимой (несовместной), поскольку при любых неотрицательных значениях хi 0, i = 1,2,...,n величина xn+s = – |as1|х1 – |as2|х2 –...– |asn|xn| – |bs|<0, а это

120