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

1.3 МЕТОДЫ ВЕТВЕЙ И ГРАНИЦ

1.3.1 Схема метода ветвей и границ

1) Итераций K0 . Для расширенной ОДР X ⁽⁰⁾ полученной из исходной X исключением части ограничений определяется максимальное значение целевой функции задачи: f ( x) max, x X (1).

Обозначим максимальное значение f ( x) f ( x⁰ ) . Это значение одновременно является верхней границей функции цели на исходном множестве допустимых планов: M( X) f ( x0 ), x0 X (0) (2).

Если при этом план x⁽⁰⁾ удовлетворяет исходному множеству допустимых планов x⁽⁰⁾ X , то процесс

решения задачи (1) закончен и x⁽⁰⁾ - искомое решение. 2) K1,2,...

В соответствии с выбранным способом, отвечающим специфике задачи (1) производится разбиение перспективного подмножества допустимых планов (для K 1 такое подмножество одно, это X ⁽⁰⁾ ) на непересекающиеся подмножества:

Xr( k) , r 0,..., rk : Xt( k) Xsr( k) (3)

r -индекс подмножества, s - идентификатор множества предыдущего шага.

Причем известно, что в ^X_s0 оптимальных решений нет.

Помня, что в формуле (3) должен быть двойной индекс для дальнейшего упрощения изложения опустим его.

Тогда оценки M( ^x_r^{( k)} ), r 1, k ищутся как максимумы целевой функции на подмножествах Xr( k) , r 1, rk .

Если план xl^{( k)} , приносящий максимум f ( x) на некотором подмножестве ^X_l^{( k)} одновременно удовлетворяет исходной системе ограничений ^x_l^{( k)} X и является решением на итерации K , то этот план является претендентом на решение исходной задачи.

3) В процессе решения задачи подмножество ^X₀ увеличивается за счет включения в него ^X_t^{( k)} в следующих случаях:

а) если в результате сравнения оценок на разбиениях внутри итерации K хотя бы для одного подмноже-

ства ^X_r^{( k)} максимум f ( x) на подмножестве ^X_t^{( k)} меньше максимума f ( x) на подмножестве ^X_r^{( k)} :

X _t^{( k) X} ₀ : M( ^X_t^{( k)} ) M( ^X_r^{( k)} ), t, r R^{( k)} _{, где} R^{( k)} - подмножество индексов разбиений на итерации K .

б) если в результате сравнения оценок между итерациями K, P, KP хотя бы для одной итерации

Pнайдется такое подмножество ^X_l^{( p)}, что максимум f ( x) на подмножестве ^X_t^{( k)} меньше максимума f ( x) на подмножестве ^X_l^{( p)} , т.е.

Xtk X 0 : M( Xl( p) ) M( Xtk ), t R( k) , l R( p) , p k 1,...,1

Ветви, включенные в ^X₀ являются тупиковыми.

4) Решением задачи (1) является лучшее из решений-претендентов; если в результате разбиения последнее подмножества процесса решения оказалось пустым и решений-претендентов нет, то исходная задача (1) целочисленных решений не имеет.

Процесс решения задачи (1) с использованием методов ветвей и границ иллюстрируется так называемым деревом ветвлений.

Для реализации описанной выше схемы в виде конкретного алгоритма необходимо указать:

- способ расширения ОДР;

- правило ветвления (разбиения на подмножества); - правило вычисления границ (оценок).

1.3.2. Алгоритм Лэнда и Дойга

Алгоритм применяется для решения частично целочисленных задач. Конкретизация алгоритма в соответствии с схемой метода ветвей и границ следующая:

1) способ расширения ОДР.

В качестве расширения X ⁽⁰⁾ исходной области ограничений X используют область ограничений ЗЛП, соответствующая исходной ЗЦП. 2) правило ветвления.

Пусть ^X_s^{( k1)} - перспективное подмножества шага k 1 . Разбиение его на подмножества ^X_sr^{( k)} , r 1, ^r_k производится по правилам:

-

из плана ^x_s^{( k 1)} выбирается нецелочисленная компонента x^*_j ;

-

из ОДР, соответствующей этому плану ^x_s^{( k 1)} исключается значения x^*_j , лежащие в промежутке: ([ x* j ];[ x* j ] 1) . Таким образом, при разбиении Xs( k 1) получаем два подмножества X1( k) , X2( k) , где:

X₁( k) { x₁( k) : x₁( k) X _s( k 1) , x _j [ x* _j ]},

. (4) X ₂( k) { x₂( k) : x₂( k) X _s( k 1) , x _j [ x* _j ] 1}

Если оценки на некоторых подмножествах предыдущего шага одинаковы, то просматриваются все эти ветви с целью получения альтернативного решения. 3) Правило вычисления границ (оценок).

Способ разбиения множеств на подмножество на каждом шаге K0 генерирует две ЗЛП с целевыми функциями исходной задачи (1) и ОДР ^X₁^{( k)}, ^X₂^{( k)} .

_{Границами} M( ^X₁^{( k)}), M( ^X₂^{( k)}) являются максимальные значения исходной целевой функции на соответствующих ОДР f ( xr( k) ), r 1, rk .

Примечание 1. Если коэффициенты функции цели при переменных, на которые накладываются условия целочисленности целые, а при остальных равны нулю, то оценку можно усилить: Zr( k ) ] f ( xr( k) )[, r 1, rk . Здесь ] [ - наименьшее целое, не меньшее .

Примечание 2. При построении дерева ветвлений можно следовать по ветвям, приводящим к скорейшему получению 1-го претендента по решению исходной задачи – схема одностороннего обхода дерева. Ветви, не включенные в обход называются оборванными; их оценка вычисляется после первого рекорда. По другой схеме просматриваются и производятся ветвления одновременно по всем подмножествам итерации K .

Первый способ ветвления предпочтительнее, т.к. он нагляднее в интерпретации и экономичнее при программировании метода.

В вычислительном аспекте алгоритм Л. и Д. сводится к решению серий ЗЛП. Конечность алгоритма обеспечивается тем, что исходное множество дополнительных планов ограничено.

Альтернативные решения ищутся в том случае, если в условии задачи его требовалось найти.

1.3.3 Алгоритм Литтла

Алгоритм Литтла укладывается в схему методов ветвей и границ и предназначен для решения прикладных задач ЦП специальной структуры.

Классической постановкой такой задачи является задача о коммивояжере, алгоритм решения которой в терминах теории графов можно сформулировать так:

Среди множества допустимых гамильтоновых контуров (ГК) выбрать контур минимальной длины. Алгоритм Литтла реализует схему направленного частичного перебора вариантов ГК. Конечность алгоритма следует из конечного числа ГК в допустимой области рассматриваемой задачи.