Лекция: Аддитивный алгоритм

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

Модель задачи должна быть представлена в стандартной форме. Далее будем рассматривать алгоритм применительно к следующей задаче:

L= (7.10)

(7.11)

(7.12)

При этом "cj ³ 0, что означает выполнение признака оптимальности симплекс-метода в начальном решении (в задачах на минимум). Действительно, так как коэффициенты дополнительных переменных ci=0, то zj=0 и Dj= zj-cj £0. Поэтому, если еще и "bi ³ 0, то сразу имеем оптимальное решение задачи: все n исходных переменных и критерий равны нулю. Однако обычно не все biположительны и нулевое начальное решение оказывается недопустимым.

Если в критерии есть отрицательные коэффициенты, то модель преобразуется: переменные хk с ck <0 всюду в модели заменяются на xk=1- хk’и образующаяся в критерии константа отбрасывается (после получения решения она добавляется к оптимальноу значению критерия). Если есть равенства, они преобразуются в неравенства. Неравенства ³ преобразуются в неравенства £. Таким образом, любая исходная модель может быть приведена к виду (710)-(7.12) с "cj ³ 0.

Представим условия (7.11) в канонической форме:

, (7.13)

где Si – дополнительные переменные.Тогда начальное решение очевидно: "хj=0 и Si=bi. Как уже говорилось, если "Si³ 0, оно оптимально. В противном случае осуществляется частичный перебор решений. Для пояснения алгоритма восполььзуемся табл. 7.7, которая аналогична симплексной.

Таблица 7.7

В алгоритме переменные разделяются на фиксированные и свободные. Переменную которой присвоено определенное значение, называют фиксированной. Значение свободной переменной можно изменять. Основным объектом алгоритма является частичное решение – это решение, в котором часть переменных фиксирована. Оно описывается упорядоченным множеством индексов фиксированных переменных. При этом индекс переменных, равных нулю, записывается со знаком «минус». Например, если на t-й итерации фиксированы х2=0, х4=1, точастичное решение представляется как множествоIt={-2, 4}.

Первоначальное частичное множество всегда пустое (I0=Æ), а значение рекорда z=¥. Алгоритм состоит из четырех проверок, которые выполняются для того, чтобы определить наличие перспективных свободных переменных. Если такая переменная находится, то изменяя ее значение, можно улучшить результат. По умолчанию принято, что свободные переменные находятся на нижнем уровне (равны нулю). Частичное решение считается прозондированным, если оно не может привести к допустимому решению и уменьшению значения критерия.

Пусть имеем частичное решение It с критерием Ltи вектором дополнительных переменных St=(S1t,S2t, ...,Smt). К нему применяются следующие проверки.

1. Для каждой свободной переменной xr проверяются коэффициенты air в строках с Sit<0 (табл.7.7). Если во всех таких строках air³0, переменная xr исключается, так как изменение ее значения с 0 на 1 не приведет к положительности хотя бы одной из рассматриваемых Sit.

2. Анализируется возможность улучшения критерия. Если для свободной переменной xr выполняется неравенство Cr+ Lt³ z, изменение ее значения не может привести к уменьшению рекорда. Поэтому она исключается.

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

3. Выясняется возможность получения допустимого решения на основе данного частичного. В строках с Sit<0 проверяется условие

(7.14)

Если оно выполняется хотя бы для одной строки, все переменные из Ptисключаются, так как изменение даже всех этих переменных с 0 на 1 не обеспечит допустимось решения (неотрицательности вектора S). В этом случае решение It считается прозондированным (ветвь обрывается).

Если условия (7.14) не выполняются, проводится проверка 4.

4. При Pt ¹ Æ ветвь продолжается. Для получения нового частичного решения из It вычисляются оценки каждой переменной из Pt:

(7.15)

Оценка дает суммарную величину недопустимости, остающейся после изменения значения переменной xjÎ Pt c 0 на 1. Как видно из (7.15), отрицательная оценка свидетельствует о наличии недопустимости. Из полученных оценок определяется максимальная

. (7.16)

Очевидно, что если vkt=0, то изменение xk с 0 на 1 дает допустимое решение с меньшим значением критерия. Поэтому рекорду z присваивается значение Lt+Ck, а новое частичное рещение It+1={It, k} считается прозондированным. Если же vkt< 0, то допустимое решение не достигнуто и частичное решение It+1={It, k} подвергается всем проверкам. Если в результате проверок оно окажется прозондированным, новое частичное решение получают из It+1 изменением знака индекса введенной переменной: It+2={It, -k}, то есть фиксацией xk со значением 0.

В общем случае прозондированное частичное решение может содержать положительные и отрицательные индексы. Для получения нового частичного решения изменяется знак самого правого положительного индекса, а стоящие за ним индексы отбрасываются. Так из решения {2, -1,-3, 5,-7, -6} следует частичное решение {2, -1, -3, -5}. Если представить весь процесс решения в виде дерева (подобно методу ветвей и границ), то отбрасывание l последних индексов означает возврат на l уровней вверх. Условием окончания работы аддитивного алгоритма является отсутствие положительных индексов в частичном решении.

Пример 7.4 (Таха). Решим с помощью аддитивного алгоритма следующую задачу.

L=-3x1 -2x2+5x3+2x4 -3x5® min;

x1+x2+x3+2x4+x5£ 4;

7x1+3x3-4x4+3x5£ 8;

11x1-6x2+3x4-3x5³ 3;

.

Так как C1, C2и C5 отрицательные, производим замены:

xj=1-xj’, j=1, 2, 5.

После простых преобразований модель принимает вид

L1=3x1’ +2x2’+5x3+2x4 +3x5’® min;

-x1’-x2’+x3+2x4-x5’£ 1;

-7x1’+3x3-4x4-3x5’£ -2;

11x1’-6x2’-3x4-3x5’£ -1.

Приводим условия к равенствам:

-x1’-x2’+x3+2x4-x5’+ S1= 1;

-7x1’+3x3-4x4-3x5’+ S2= -2;

11x1’-6x2’-3x4-3x5’+ S3= -1.

Полученную модель представляем в табличном виде (табл. 7.8).

Таблица 7.8

В исходном состоянии все переменные свободны и равны нулю. Поэтому начальное частичное решение I(0)=Æ, z=¥, L1(0)=0, S(0)=(1, -2, -1).

Так как есть отрицательные Si, начальное решение неоптимально и необходимо проводить проверки (ниже они обозначены соответствующими им номерами).

Итерация 1.

1. Поскольку "ai3³0, переменная x3 исключается.

2. Для всех переменных Сj+L1(0)<z, поэтому не отвергается ни одна переменная.

3. P0={1, 2, 4, 5} – множество свободных переменных, которые прошли через первые две проверки. Для строк с отрицательными Si по табл. 7.8 проверяем условие (7.14):

i=2: = -7+ 0 — 4 — 3= -14 <S2= -2;

i=3: =0 – 6 – 3 – 3 = -12 <S3= -1.

Условия не выполняются и все переменные остаются.

4. По формуле 7.15 вычисляем:

v10=min(0, 1 +1)+min(0, -2+7)+min(0, -1-11)=0+0+(-12)=-12;

аналогично v20=0+(-2)+0= -2,

v4= -1+0+0= -1,

v50=0+0+0=0.

Находим maxvj0= v50 = 0. Отсюда следует, что k=5 и новое частичное решение с x5’ = 1 является допустимым. В итоге имеем:

I1={5}, L11=3,z= L11=3 и S1=(2, 1, 2), так как S11=S10 – a15=1-(-1)=2,S21= S20-a25= -2-(-3)=1, S31=S30-a35=-1-(-3)=2, то есть действительно все Si>0, что означает допустимость решения. Вывод: решение I1 прозондировано.

Очередное частичное решение получается изменением знака индекса в I1.

Итерация 2.

I2={-5}, L12=0, S2=(1, -2, -1),z=3.

1. Исключается x3.

2. Исключается x1’, так как C1+L12=0+3= z .

3. P2={2, 4}.

i=2: 0 — 4= -4 < -2;

i=4: — 6 – 3 = -9 < -1.

4. v22= 0+ (-2)+ 0= -2, v42= -1+ 0+ 0= -1, max vi2=v42= -1. Следовательно, k=4 и новое решение I3={-5, 4} недопустимое.

Итерация 3.

I3={-5, 4}, L13=C4=2, S3=(-1, 2, 2), z=3. Свободными являются первые 3 переменные.

1. Исключается х3.

2. Исключаются x1’ и x2’, так как L13+C1=5>3 иL13+C2=4>3.

P3=Æ, значит, решение I3 прозондировано.

Так как есть частичное решение I3 с положительным индеком, образуем из него решение I4, заменив 4 на –4.

Итерация 4.

I4={-5, — 4},L13=0, S4={1,- 2,-1}, z=3..

1. Исключается х3.

2. Исключается х1’.

3. P4={2}.

i=2: 0 > -2, следовательно, x2’ исключается и I4 прозондировано (оно не может привести к допустимому решению).

Больше нет частичных решений с положительными индексами, из чего заключаем, что итерации завершены и оптимальным является решениеI1: x1’=x2’=x3=x4=0, x5’=1. Возвращаясь к исходным переменным, получаем

x1*= x2*=1, x3*=x4*=x5*=0, L*=5.

Дерево решений рассмотренного примера показано на рис. 7.12. Здесь хорошо видна аналогия с методом ветвей и границ.