Аддитивный алгоритм

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

Модель задачи должна быть представлена в стандартной форме.

L = (10) (11) (12)

Требования: все условия неравенства; c_j – неотрицательны, если c_k < 0 x_k = 1-x_k; постоянная в критерии не влияет на решение.

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

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

В алгоритме переменные разделяются на фиксированные и свободные.Переменную которой присвоено определенное значение, называют фиксированной. Значение свободной переменной можно изменять. Основным объектом алгоритма является частичное решение – это решение, в котором часть переменных фиксирована. Оно описывается упорядоченным множеством индексов фиксированных переменных. При этом индекс переменных, равных нулю, записывается со знаком " минус" I _t ={-2, 4}.

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

Пусть имеем частичное решение I _t с критерием L^t и вектором дополнительных переменных S ^t =(S ₁^t, S ₂^t,..., S_m^t). К нему применяются следующие проверки.

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

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

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

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

Если оно выполняется хотя бы для одной строки, все переменные из P _t исключаются. В этом случае решение I _t считается прозондированным (ветвь обрывается).

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

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

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

Очевидно, что если v_k^t =0, то изменение x_k с 0 на 1 дает допустимое решение с меньшим значением критерия. Поэтому рекорду z присваивается значение L^t + C_k, а новое частичное рещение I _{t +1}={I _t, k } считается прозондированным. Если же v_k^t < 0, то допустимое решение не достигнуто и частичное решение I _{t +1}={I _t, k } подвергается всем проверкам. Если в результате проверок оно окажется прозондированным, новое частичное решение получают из I _{t +1} изменением знака индекса введенной переменной: I _{t +2}={I _t, - k }, то есть фиксацией x_k со значением 0.