Метод декомпозиции Данцига - Вулфа

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

Одним из эффективных методов блочного программирования применительно к линейным задачам является метод декомпозиции Данцига – Вулфа. По данным авторов метод позволяет решать задачи с размерностью n~ 10⁶, m~ 10⁵.

 

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

Пусть имеется следующая модель задачи:

L= C ^T X àmax; (6.1)

AX = B; (6.2)

X ³0, (6.3)

где вектор X имеет размерность n, а вектор B – m.

Условия (6.2), (6.3) определяют допустимое множество задачи D. Представим матрицу А и вектор В в виде двух подматриц:

Тогда условия задачи (6.2)-(6.3) записываются следующим образом:

А ⁽⁰⁾ Х = В ⁽⁰⁾; (6.4)

А ⁽¹⁾ Х = В ⁽¹⁾; (6.5)

Х ³0 (6.6)

Условия (6.4), включающие m₀ равенств, порождают допустимое множество D₀, а система (6.5) содержит m₁ равенств и вместе с (6.6) задает множество D₁. Очевидно, что m=m₀+m₁, D = D₀ Ç D₁. При этом выделение подматриц выполняется так, что m₁ >> m₀.

Далее будем полагать, что множество D₁ ограниченное и, значит, является выпуклым многогранником. В противном случае его легко сделать ограниченным добавлением ограничений сверху на переменные так, что они не повлияют на исходное множество D.

Предположим, что нам известны вершины множества D₁. Обозначим их координаты через Х ¹, Х ²,…, Х ^N, где N – число вершин. Поскольку D₁ – выпуклый многогранник, то любую его точку можно представить в виде линейной комбинации вершин:

Х = z _n X ⁿ; (6.7)

S z _n=1; (6.8)

z _n³0, " v. (6.9)

Так как все решения Х, определяемые по (6.7)-(6.9), принадлежат D₁, то описание (6.7)-(6.9) эквивалентно (6.5), (6.6).

Подставим Х в виде (6.7) в (6.1) и (6.4):

L = C ^T z _n X ⁿ;

S A ⁽⁰⁾ X ⁿ z _n= B ⁽⁰⁾.

Считая X ⁿ известными, введем обозначения:

С ^Т Х ⁿ= s_n; (6.10)

А ⁽⁰⁾ Х ⁿ= Р _n. (6.11)

Тогда преобразованная модель задачи запишется в виде

L = s _n z _nàmax;

P _n z _n= B ⁽⁰⁾;

z _n=1;

" z _n³0.

В этой модели неизвестными являются z _n, число которых равно числу вершин многогранника D₁. Последнее равенство модели можно объединить со всеми остальными, используя обозначения расширенных векторов

. (6.12)

Тогда окончательно получим:

L = s_n z _nàmax; (6.13)

z _n = ; (6.14)

" z _n³0. (6.15)

Задача в виде (6.13) – (6.15) называется координирующей или основной задачей. Главное отличие этой задачи от исходной в несравнимо меньшем числе условий (m₀ +1<< m).

Если мы сможем ее решить, то есть найти Z ^*, то получим решение и исходной задачи, воспользовавшись (6.7):

Х *= z _n^* X ⁿ. (6.16)

Для решения основной задачи применим модифицированный симплекс-метод. Начальное решение можно построить, не зная ни одной вершины, с помощью искусственных переменных z_N+i.

Согласно модифицированному методу после получения очередного базисного решения вычисляются относительные оценки. В разд. 4.10 получены формулы:

Перепишем их в обозначениях координирующей задачи:

(6.17)

или окончательно

(6.18)

Мы не можем вычислить все оценки, так как нам не известно даже их число. Но этого и не требуется, достаточно только определить: есть или нет среди них отрицательные. Для ответа на этот вопрос будем искать наименьшую оценку. Если она отрицательная, текущее решение координирующей задачи может быть улучшено введением переменной с этой оценкой. В противном случае констатируется выполнение признака оптимальности.

Итак, задача состоит в следующем:

D_nàmin.

Отбросив в (6.18) константу, запишем ее в виде

(p^TA⁽⁰⁾-C^T)Xⁿ® (6.19)

Решение задачи (6.19) проблематично, так как минимум ищется на дискретном множестве вершин многогранника D₁. Учитывая, что минимизируемая функция линейная, будем искать решение не на вершинах, а на всем многограннике. Известно, что если решение существует, то оно будет достигаться в вершине. Поэтому решение на всем (непрерывном) множестве D₁ совпадет с решением задачи (6.19).

Таким образом, задачу (6.19) заменяем эквивалентной:

L_всп =(p^TA⁽⁰⁾-C^T)X® (6.20)

A⁽¹⁾X = B⁽¹⁾; (6.21)

X ³ 0. (6.22)

Эта задача называется вспомогательной. Если она неразрешима, то и исходная задача не имеет решения. Пусть оптимальное решение вспомогательной задачи (6.20)-(6.22) достигается в вершине r. Это означает, что нам становятся известны координаты вершины X^r и оптимальное значение критерия . Тогда согласно формуле (6.18) вычисляем минимальную оценку

(6.23)

Очевидно, что если D _r ³0, то и все оценки неотрицательны, и решение координирующей задачи завершено. При отрицательной D _r решение продолжается. В базис основной задачи вводится вектор , определяемый по формуле

(6.30)

Направляющий столбец находится разложением этого вектора по текущему базису:

. (6.31)

После определения направляющего элемента и симплекс-преобразования получаем новое решение основной задачи. Коэффициент критерия (6.13) при переменной, введенной в базисное решение, вычисляется согласно (6.10):

s_r = C ^T X ^r. (6.32)

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

Таким образом, решение исходной задачи заменяется многократным решением основной и вспомогательной задач. При этом порядок размерности вспомогательной задачи такой же, как у исходной. Поэтому естественнен вопрос: в каких случаях такой метод эффективен?

Ответ очевиден: в тех случаях, когда сложность решения вспомогательной задачи намного ниже, чем исходной. Такие случаи имеют место, когда матрица условий задачи (после упорядочения строк и столбцов) оказывается почти-блочно-диагональной, как показано на рис. 6.1. Примером может служить задача планирования производства продукции в крупной фирме или холдинге, когда у каждого предприятия своя номенклатура продукции, а некоторые ресурсы являются общими. Подматрица А ⁽⁰⁾, входящая в параметры координирующей задачи,соответствует ограничениям по общим ресурсам. Такие условия называют связующими. Их относят к основной задаче.

Остальные условия образуют вспомогательную задачу. При этом подматрица А ⁽¹⁾ имеет блочно-диагональную структуру, что позволяет разбить вспомогательную задачу на p независимых задач:

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

Таким образом, решение вспомогательной задачи существенно упрощается, если структура матрица условий может быть приведена к блочно-диагональной.

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

Применение рассмотренного метода может быть целесообразно и тогда, когда вспомогательная задача имеет особенности, позволяющие решать ее специальными методами.