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

1.6.1 Описание идеи аддитивного алгоритма

Аддитивный алгоритм является методом частичного перебора. Он состоит в получении оптимального плана путем рассмотрения некоторого подмножества всех пробных планов - 2 ⁿ -штук. Это производится в рамках метода ветвей и границ.

Частичным или q -планом называется набор, состоящий из q фиксированных нулем или единицей значений ^x_j, 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, Y ⁰ B, Z ⁰ 0, U ⁰ X ⁰ , Y ⁰ 0, B .

Этот план приносит минимальное значение Z , т.к. ^c_j 0 , однако этот план имеет отрицательные ком-

поненты вектора Y ⁰ , если решение не тривиально. Другими словами, те ограничения (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 ограничений, для которых дополнительные переменные ^y_i0 ; j - индекс переменной, зафиксированной 1;

j - индекс переменной, зафиксированной 0;

N' - подмножество индексов переменных, составляющих частичное решение;

^N_i - множество индексов свободных переменных в ограничении 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 исключается.

В случае, когда ^a_ir 0 i 1, m переменная ^x_r исключатся насовсем.

Правило 2. Запрет недопустимых вариантов ветвления, когда дополнение частичного решения не может быть получено, т.е. отрицательность ^y_i не может быть устранена.

Если на S хотя бы для одного i

не выполняется неравенство , где

N _i j : j N', ^a_ij 0 , то данный вариант ветвления отбрасывается и осуществляется переход к

( q 1) плану или другому частичному решению.

Если неравенство выполняется, то данный вариант ветвления должен быть развит.

Правило 3. Запрет неперспективных в смысле улучшения рекорда направления ветвления на итерации S и для шага K .

Если был получен рекорд rec и значение целевой функции предыдущего шага z ^{s 1} известно, то для переменной ^x_l , l и при этом ^c_l rec, то присвоение переменной ^x_l : 1 на итерации S не

улучшит z в сравнении с рекордом, т.е. ^x_l не перспективно и развитие варианта по ^x_l следует прекратить.

Если коэффициент при ^x_l^c_l сам не меньше рекорда ^c_l rec , то ^x_l не может быть зафиксирован единицей до конца процесса решения задачи.

Правила 1,2,3 формируют на основе N ^{s 1} набор свободных переменных, которые могут быть зафиксированы на итерации S , т.е. N.

Правило 4. Выбор направление ветвления.

Для выбора направления ветвления используется оценка _j , которая есть сумма недопустимостей по пе-

ременной j во всех ограничениях i 1, m, которая возникнет, если ^x_j : 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 . Идем на дерево ветвлений.