1.6.1 Описание идеи аддитивного алгоритма
Аддитивный алгоритм является методом частичного перебора. Он состоит в получении оптимального плана путем рассмотрения некоторого подмножества всех пробных планов - 2 n -штук. Это производится в рамках метода ветвей и границ.
Частичным или q -планом называется набор, состоящий из q фиксированных нулем или единицей значений xj, j N , N - подмножество индексов j . Дополнением частичного плана называется набор n q переменных, дополняющий q -план до плана исходной задачи. Если окажется, что конкретный q -план имеет дополнения или не имеет дополнения, приводящего к меньшему значению z, то из рассмотрения можно исключить 2 q планов и искать оптимальный план среди оставшихся.Анализ (зондирование) q -плана состоит в:
А) нахождении наилучшего дополнения, дающего значение Z меньше, чем полученное ранее; в этом случае определенным образом осуществляется переход к новому q 1 плану; такой план называется расширением q -плана; Б) установлении факта, что таких дополнений нет; в этом случае другие дополнения или расширения q плана рассматривать не нужно; присвоение последней переменной значения привело в тупик; осуществляется переход к q 1 плану.1.6.2 Общая схема алгоритма Балаша
В соответствии со схемой ветвей и границ будем считать шагом метода получение допустимого решения – рекорда k .
В соответствии с алгоритмом Балаша итерацией будем называть включение переменной в q -план.
Возьмем в качестве начальных условий:
X 0 0, Y 0 B, Z 0 0, U 0 X 0 , Y 0 0, B .
Этот план приносит минимальное значение Z , т.к. cj 0 , однако этот план имеет отрицательные ком- поненты вектора Y 0 , если решение не тривиально. Другими словами, те ограничения (5), для которых y i0 не выполняются. Переход от пробного плана к плану осуществляется последствием итерации S 1 , причем на каждой итерации S получается частичное решение в виде: U (8)Z (9)
Здесь:
x (10)J(11) y(13)
Z (14)
Таким образом, алгоритм Балаша должен иметь правила:
1)
формирования подмножеств J S , N \ J;2)
перехода от итерации S к S 1 ;3) определения оптимальности решения или неразрешимости исходной задачи.
Булева переменная x j называется свободной на S -ой итерации, если ее значение до S -ой итерации не зафиксировано ни нулем, ни единицей и подлежит определению в дальнейшем. Введем обозначения:
N- множество индексов j свободных на итерации s переменных;
M- множество индексов i ограничений, для которых дополнительные переменные yi0 ; j - индекс переменной, зафиксированной 1;j - индекс переменной, зафиксированной 0;
N' - подмножество индексов переменных, составляющих частичное решение;
Ni - множество индексов свободных переменных в ограничении i , которые могут быть включены в частичное решение;
J- индексы переменных, для которых было сделано назначение единицей.
1.6.3 Правила построения частичного решения
Правило 1.Правило по которому из числа свободных исключаются переменные, усиливающие недопустимости для данной итерации s или шага k .
Если на итерации s переменная xr , r N s i M i : yi 0 : air 0 , то присвоение xr : 1усиливает недопустимости во всех строках i M . В этом случае на итерацию S переменная x r , r
S исключается. В случае, когда air 0 i 1, m переменная xr исключатся насовсем. Правило 2. Запрет недопустимых вариантов ветвления, когда дополнение частичного решения не может быть получено, т.е. отрицательность yi не может быть устранена.Если на S хотя бы для одного i
не выполняется неравенство , где N i j : j N', aij 0 , то данный вариант ветвления отбрасывается и осуществляется переход к( q 1) плану или другому частичному решению.
Если неравенство выполняется, то данный вариант ветвления должен быть развит.
Правило 3. Запрет неперспективных в смысле улучшения рекорда направления ветвления на итерации S и для шага K .
Если был получен рекорд rec и значение целевой функции предыдущего шага z s 1 известно, то для переменной xl , l и при этом cl rec, то присвоение переменной xl : 1 на итерации S неулучшит z в сравнении с рекордом, т.е. xl не перспективно и развитие варианта по xl следует прекратить.
Если коэффициент при xlcl сам не меньше рекорда cl rec , то xl не может быть зафиксирован единицей до конца процесса решения задачи. Правила 1,2,3 формируют на основе N s 1 набор свободных переменных, которые могут быть зафиксированы на итерации S , т.е. N.Правило 4. Выбор направление ветвления.
Для выбора направления ветвления используется оценка j , которая есть сумма недопустимостей по пе- ременной j во всех ограничениях i 1, m, которая возникнет, если xj : 1 :m
min 0, y S 1 a j i ij . i 1
Из всех j , j N S выбирается та, которая приносит меньше суммарной недопустимости, т.е. учитывая, то j 0 выбирается максимальное: j* arg maxS j . j N1.6.4 Алгоритм метода Балаша
. Записываем: новый рекорд rec min rec, reck для s 1 ; rec min( reck 1 , reck ) , записываем X N', Y . Идем на дерево ветвлений.