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

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

L=C^TXà max; (1) AX=B; (2) X³ 0, (3) где вектор X имеет размерность n, а вектор B – m. Условия (2), (3) определяют допустимое множество задачи D. Представим матрицу А и вектор В в виде двух подматриц: Тогда условия задачи (2)-(3) записываются следующим образом:

А ⁽⁰⁾ Х = В ⁽⁰⁾; (4) А ⁽¹⁾ Х = В ⁽¹⁾; (5) Х ³ 0(6)

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

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

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

Х = z _n X ⁿ; (7) S z _n=1; (8) z _n³ 0, " v. (9)

Так как все решения Х, определяемые по (7)-(9), принадлежат D₁, то описание (7)-(9) эквивалентно (5), (6). Подставим Х в виде (7) в (1) и (4): L = C ^T z _n X ⁿ;

S A ⁽⁰⁾ X ⁿ z _n= B ⁽⁰⁾. Считая X ⁿ известными, введем обозначения: С ^Т Х ⁿ= s_n; (10)

А ⁽⁰⁾ Х ⁿ= Р _n.(11) Тогда преобразованная модель задачи запишется в виде

L = s _n z _nà max; P _n z _n= B ⁽⁰⁾; z _n=1; " z _n³ 0.

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

Тогда окончательно получим: L = s_n z _nà max; (13) z _n = ; (14)" z _n³ 0. (15)

Задача в виде (13) – (15) называется координирующей или основной задачей. Главное отличие этой задачи от исходной в несравнимо меньшем числе условий (m₀ +1< < m). Если мы сможем ее решить, то есть найти Z ^*, то получим решение и исходной задачи, воспользовавшись (7): Х *= z _n^* X ⁿ.(16)

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

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

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

(18)

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

Задача состоит в следующем: D_nà min.

Отбросив в (18) константу, запишем ее в виде (p^TA⁽⁰⁾-C^T)Xⁿ® (19)

Решение задачи (19) проблематично, так как минимум ищется на дискретном множестве вершин многогранника D₁. Учитывая, что минимизируемая функция линейная, будем искать решение не на вершинах, а на всем многограннике. Известно, что если решение существует, то оно будет достигаться в вершине. Поэтому решение на всем (непрерывном) множестве D₁ совпадет с решением задачи (19). Задачу (19) заменяем эквивалентной: L_всп =(p^TA⁽⁰⁾-C^T)X® (20) A⁽¹⁾X = B⁽¹⁾; (21) X ³ 0. (22)

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

Если D _r ³ 0, то и все оценки неотрицательны, и решение координирующей задачи завершено. При отрицательной D _r решение продолжается. В базис основной задачи вводится вектор , определяемый по формуле (30) Направляющий столбец находится разложением этого вектора по текущему базису: . (31)

После определения направляющего элемента и симплекс-преобразования получаем новое решение основной задачи. Коэффициент критерия (13) при переменной, введенной в базисное решение, вычисляется согласно (10): s_r = C ^T X ^r. (32)