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

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

Тогда условия задачи записываются: А ⁽⁰⁾ Х = В ⁽⁰⁾; А ⁽¹⁾ Х = В ⁽¹⁾; Х ³0.

1 условия, включающие m₀ равенств, порождают допустимое множество D₀, а система содержит m₁ равенств и вместе с Х ³0 задает множество D₁. Очевидно, что m=m₀+m₁, D = D₀ Ç D₁. При этом выделение подматриц выполняется так, что m₁ >> m₀.

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

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

Х = z _n X ⁿ; S z _n=1; z _n³0, " v. Так как все решения Х принадлежат D₁, то данное описание эквивалентно первому. L = C ^T z _n X ⁿ; S A ⁽⁰⁾ X ⁿ z _n= B ⁽⁰⁾. Считая X ⁿ известными: С ^Т Х ⁿ= s_n; А ⁽⁰⁾ Х ⁿ= Р _n. Тогда: L = s _n z _nàmax; P _n z _n= B ⁽⁰⁾; z _n=1; " z _n³0.

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

Тогда получим (координирующая/основная задача): L = s_n z _nàmax; z _n = ; " z _n³0.

Отличие этой задачи от исходной в меньшем числе условий (m₀ +1<< m). Если мы сможем найти Z ^*, то получим решение и исходной задачи: Х *= z _n^* X ⁿ.

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

В обозначениях координирующей задачи:

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

Задача состоит в следующем: D_nàmin. или (p^TA⁽⁰⁾-C^T)Xⁿ®

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

Подзадачу заменяем эквивалентной (вспомогательная задача):

L_всп =(p^TA⁽⁰⁾-C^T)X® A⁽¹⁾X = B⁽¹⁾; X ³ 0. Если вспомогательная задача неразрешима, то и исходная задача не имеет решения. Пусть оптимальное решение вспомогательной задачи достигается в вершине r. Т.е. становятся известны координаты вершины X^r и оптимальное значение критерия . Вычисляем минимальную оценку Если D _r ³0, то и все оценки неотрицательны, и решение коорд. задачи завершено. При отрицательной D _r в базис основной задачи вводится вектор :

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

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

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

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