Аддитивный метод
Применяется к задачам с булевыми переменными. Операции только сложения и вычитания. Не происходит накопления ошибок. Реализация одного из методов частичного перебора. Модель задачи должна быть представлена в стандартной форме: L = При этом " cj ³ 0, что означает выполнение признака оптимальности симплекс-метода в начальном решении (в задачах на минимум): т.к. коэффициенты дополнительных переменных ci =0, то zj =0 и Dj = zj - cj £0. Поэтому, если еще и " bi ³ 0, то сразу имеем оптимальное решение задачи: все n исходных переменных и критерий равны нулю. Однако обычно не все bi положительны и нулевое начальное решение оказывается недопустимым. Если в критерии есть отрицательные коэффициенты, то модель преобразуется: переменные хk с ck <0 всюду в модели заменяются на xk =1- хk’ и образующаяся в критерии константа отбрасывается (после получения решения она добавляется к оптимальному значению критерия). Если есть равенства, они преобразуются в неравенства. Неравенства ³ преобразуются в неравенства £. Любая исходная модель может быть приведена к стандартному виду с " cj ³ 0.
Представим условия в канонической форме: 1. Для каждой свободной переменной xr проверяются коэффициенты air в строках с Sit <0. Если во всех таких строках air ³0, переменная xr исключается, так как изменение ее значения с 0 на 1 не приведет к положительности хотя бы одной из рассматриваемых Sit. 2. Анализируется возможность улучшения критерия. Если для свободной переменной xr выполняется неравенство Cr + Lt ³ z, изменение ее значения не может привести к уменьшению рекорда. Поэтому она исключается. Оставшиеся после этих проверок свободные переменные образуют множество P t. Если оно пустое, то текущее частичное решение не перспективно, то есть считается прозондированным. 3. Выясняется возможность получения допустимого решения на основе данного частичного. В строках с Sit <0 проверяется условие 4. При P t ¹ Æ ветвь продолжается. Для получения нового частичного решения из I t вычисляются оценки каждой переменной из P t: Если vkt =0, то изменение xk с 0 на 1 дает допустимое решение с меньшим значением критерия. Поэтому рекорду z присваивается значение Lt + Ck, а новое частичное рещение I t +1={I t, k } считается прозондированным. Если же vkt < 0, то допустимое решение не достигнуто и частичное решение I t +1={I t, k } подвергается всем проверкам. Если в результате проверок оно окажется прозондированным, новое частичное решение получают из I t +1 изменением знака индекса введенной переменной: I t +2={I t, - k } - фиксацией xk со значением 0.
Пример: L=- 3 x 1 -2 x 2+5 x 3+2 x 4 -3 x 5 ® min; x 1 +x 2 +x 3 + 2 x 4 +x 5£ 4; 7 x 1 + 3 x 3 - 4 x 4 + 3 x 5£ 8; 11 x 1 - 6 x 2 + 3 x 4 - 3 x 5³ 3;. Так как C 1, C 2и C 5 отрицательные, производим замены: xj= 1 -xj’, j= 1, 2, 5. Модель принимает вид L 1 = 3 x 1 ’ +2 x 2 ’ +5 x 3+2 x 4 +3 x 5 ’® min; -x 1 ’-x 2 ’+x 3 + 2 x 4 -x 5 ’ £ 1; - 7 x 1 ’+ 3 x 3 - 4 x 4 - 3 x 5 ’ £ -2; 11 x 1 ’- 6 x 2 ’- 3 x 4 - 3 x 5 ’ £ -1. Приводим усл-я к =: -x 1 ’-x 2 ’+x 3 + 2 x 4 -x 5 ’+ S 1= 1; - 7 x 1 ’+ 3 x 3 - 4 x 4 - 3 x 5 ’+ S 2 = -2; 11 x 1 ’- 6 x 2 ’- 3 x 4 - 3 x 5 ’+ S 3 = -1.
Полученную модель представляем в табличном виде. В исходном состоянии все переменные свободны и равны 0. Поэтому начальное частичное решение I(0 ) = Æ, z= ¥, L 1(0 ) = 0, S(0)=(1, -2, -1). Так как есть отрицательные Si, начальное решение неоптимально и необходимо проводить проверки (ниже они обозначены соответствующими им номерами). Итерация 1. 1. Поскольку " ai 3³0, переменная x 3 исключается. 2. Для всех переменных Сj + L 1(0 ) < z, поэтому не отвергается ни одна переменная. 3. P0 ={1, 2, 4, 5} – множество свободных переменных, которые прошли через первые две проверки. Для строк с отрицательными Si по таблице проверяем условие: i= 2: Условия не выполняются и все переменные остаются.
Очередное частичное решение получается изменением знака индекса в I1. Итерация 2. I2={-5}, L 12 = 0, S2=(1, -2, -1), z= 3. 1. Исключается x 3. 2. Исключается x 1 ’ , так как C 1+ L 12=0+3= z. 3. P2={2, 4}. i =2: 0 - 4= -4 < -2; i =4: - 6 – 3 = -9 < -1. 4. v 22= 0+ (-2)+ 0= -2, v 42= -1+ 0+ 0= -1, max v i2= v 42= -1. Следовательно, k =4 и новое решение I3={-5, 4} недопустимое. Итерация 3. I3={-5, 4}, L 13= C 4=2, S3=(-1, 2, 2), z =3. Свободными являются первые 3 переменные. 1. Исключается х 3. 2. Исключаются x 1 ’ и x 2 ’ , так как L 13 +C1= 5 >;3 и L 13 +C2=4>;3. P3=Æ, значит, решение I3 прозондировано. Так как есть частичное решение I3 с положительным индексом, образуем из него решение I4, заменив 4 на –4. Итерация 4. I4={-5, - 4}, L 13 =0, S4={1,- 2,-1}, z= 3.. 1. Исключается х 3. 2. Исключается х 1 ’. 3. P4={2}. i= 2: 0 > -2, следовательно, x 2 ’ исключается и I4 прозондировано. Больше нет частичных решений с положительными индексами, итерации завершены и оптимальным является решениеI1: x 1 ’=x 2 ’=x 3 =x 4 = 0, x 5 ’= 1. Исходные переменные: x 1 *= x 2 *= 1, x 3 *=x 4 *=x 5 *= 0, L*= 5. 36. Нелинейное программирование (НЛП): постановка, классы задач НЛП, условия оптимальности.
|
, где Si – дополнительные переменные.Тогда начальное решение: " хj =0 и Si = bi. Если " Si ³ 0, оно оптимально. В противном случае осуществляется частичный перебор решений. Для пояснения алгоритма - табл., которая аналогична симплексной. В алгоритме переменные разделяются на фиксированные и свободные. Переменная, которой присвоено определенное значение - фиксированная. Значение свободной переменной можно изменять. Основным объектом алгоритма является частичное решение – решение, в котором часть переменных фиксирована. Оно описывается упорядоченным множеством индексов фиксированных переменных. При этом индекс переменных, равных нулю, записывается со знаком "минус". Например, если на t -й итерации фиксированы х 2 = 0, х 4 = 1, точастичное решение представляется как множествоI t ={-2, 4}. Первоначальное частичное множество всегда пустое (I0=Æ), а значение рекорда z =¥. Алгоритм состоит из четырех проверок, которые выполняются для того, чтобы определить наличие перспективных свободных переменных. Если такая переменная находится, то изменяя ее значение, можно улучшить результат. По умолчанию принято, что свободные переменные находятся на нижнем уровне (равны нулю). Частичное решение считается прозондированным, если оно не может привести к допустимому решению и уменьшению значения критерия. Пусть имеем частичное решение I t с критерием Lt и вектором дополнительных переменных S t =(S 1t, S 2t,..., Smt). Проверки:
Если оно выполняется хотя бы для одной строки, все переменные из P t исключаются, так как изменение даже всех этих переменных с 0 на 1 не обеспечит допустимость решения (неотрицательности вектора S). В этом случае решение I t считается прозондированным (ветвь обрывается). Если условия не выполняются, проводится проверка 4.
Оценка дает суммарную величину недопустимости, остающейся после изменения значения переменной xj Î P t c 0 на 1. Отрицательная оценка свидетельствует о наличии недопустимости. Из полученных оценок определяется максимальная 
В общем случае прозондированное частичное решение может содержать положительные и отрицательные индексы. Для получения нового частичного решения изменяется знак самого правого положительного индекса, а стоящие за ним индексы отбрасываются. Так из решения {2, -1,-3, 5,-7, -6} следует частичное решение {2, -1, -3, -5}. Если представить весь процесс решения в виде дерева (подобно методу ветвей и границ), то отбрасывание l последних индексов означает возврат на l уровней вверх. Условием окончания работы аддитивного алгоритма является отсутствие положительных индексов в частичном решении.
= -7+ 0 - 4 - 3= -14 < S 2 = -2; i= 3: 
=0 – 6 – 3 – 3 = -12 < S 3 = -1.
4. v 1 0= min(0, 1 +1)+min(0, -2+7)+min(0, -1-11)=0+0+(-12)=-12; аналогично v 2 0= 0+(-2)+0= -2, v 4 0 = -1+0+0= -1, v 5 0= 0+0+0=0. Находим max vj0 = v 5 0 = 0. Отсюда следует, что k =5 и новое частичное решение с x 5 ’ = 1 является допустимым. В итоге имеем:I1={5}, L 11 = 3, z= L 11 = 3 и S1=(2, 1, 2), так как S 11= S 10 – a 15=1-(-1)=2, S 21= S 20- a 25= -2-(-3)=1, S 31= S 30- a 35=-1-(-3)=2, то есть действительно все Si >0, что означает допустимость решения. Вывод: решение I1 прозондировано.
