Смекни!
smekni.com

Динамическое программирование (стр. 9 из 10)

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 N

1.6.4 Алгоритм метода Балаша

.

Записываем: новый рекорд rec min rec, reck
для s 1 ; rec min( reck 1 , reck ) , записываем X N', Y . Идем на дерево ветвлений.