Разложение Данцига — Вулфа

Метод декомпозиции Данцига — Вулфа представляет собой специализированный вариант симплекс-метода.

В 1960 г. Джордж Данциг и Филип Вулф^[англ.] разработали метод декомпозиции для решения задач высокой размерности со специальной структурой матрицы ограничений^[1].

Этот метод оказался наиболее эффективным для решения задач, матрица ограничений которых имеет блочно-диагональный вид с небольшим числом переменных. Однако, как показали дальнейшие исследования, метод применим также и для задач линейного программирования с матрицей общего вида. Соответствующий метод предложен Д. Б. Юдиным и Э. Г. Гольштейном и называется блочным программированием.

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

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

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

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

Лемма Пусть ${\displaystyle R}$ - непустое замкнутое ограниченное множество в евклидовом пространстве и обладает конечным числом ${\displaystyle K}$ крайних точек, которые здесь будут обозначаться ${\displaystyle z_{k=1:K}}$. Тогда любая точка ${\displaystyle z}$ множества ${\displaystyle R}$ может быть представлена в виде выпуклой комбинации крайних точек множества R, т.е. для ${\displaystyle z}$ найдутся неотрицательные числа ${\displaystyle \delta _{k}}$ с общей суммой единица (${\displaystyle \sum _{k=1}^{K}\delta _{m}=1}$) и такие, что

(1) ${\displaystyle z=\sum _{k=1}^{K}\delta _{k}z_{k}}$.

Пусть поставлена задача

Максимизировать

(2) ${\displaystyle c[N]x[N]}$

при ограничениях

(3) ${\displaystyle A[M_{1},N]x[N]=b[M_{1}]}$

(4) ${\displaystyle A[M_{2},N]x[N]=b[M_{2}]}$

(5) ${\displaystyle x[N]\geq 0[N]}$

Ограничения (3) задают симплекс S, пусть ${\displaystyle z[K]}$ - его крайние точки.

Пусть x – допустимое решение По лемме ${\displaystyle x=z[N,K]\cdot \delta [K]}$

Подставим последнее выражение в (2) и (3).

Задача примет вид

Максимизировать (6) ${\displaystyle (c[N]\cdot z[N,K])\cdot \delta [K]=g[K]\cdot \delta [K]}$

при ограничениях

(7) ${\displaystyle (A[M_{1},N]\cdot z[N,K])\cdot \delta [K]=D[M_{1},K]\cdot \delta [K]=b[M_{1}]}$

(8) ${\displaystyle \delta [K]\cdot 1[K]=1}$.

Эта задача эквивалентна исходной (2)-(5) и называется координирующей задачей.

Она имеет только ${\displaystyle |M_{1}|+1}$ строк ограничений по сравнению с ${\displaystyle |M_{1}|+|M_{2}|}$ строками исходной задачи, и очень большое число столбцов ${\displaystyle |K|}$, равное числу крайних точек множества ${\displaystyle S}$. Чтобы не хранить все эти столбцы в памяти ЭВМ, будем получать их по мере необходимости, пользуясь методом генерации столбцов.

Решаем задачу (6)-(8) симплекс-методом с использованием метода генерации столбцов.

Для простоты предположим, что уже известно некоторое допустимое базисное решение.

Обозначим через ${\displaystyle \delta }$ ограничение (8), тогда двойственные переменные - это вектор ${\displaystyle d[M_{1}\cup {\delta }]}$.

Для ввода в базис необходимо найти ${\displaystyle z[N,m]}$, такой, что

${\displaystyle d[M_{1}]D[M_{1},K]+d[\delta ]<g[m]}$

Таким образом достаточно найти m, на котором достигается минимум

(9) ${\displaystyle d[M_{1}]A[M_{1},N]\cdot z[N,m]+d[\delta ]-c[N]z[N,m]}$

что эквивалентно решению задачи

минимизировать (10) ${\displaystyle (d[M_{1}]A[M_{1},N]-c[N])\cdot x[N])}$

при ограничениях (4) и (5).

Если найденный минимум не будет больше ${\displaystyle -d[\delta ]}$, задача решена.

В противном случае столбец ${\displaystyle D[M_{1},k]}$, соответствующий найденному решению, вводим в базис.

Пусть ограничения (4) имеют блочную структуру

${\displaystyle {\begin{pmatrix}A[M_{1},N_{1}]&0[M_{1},N_{2}]&\cdots &0[M_{1},N_{n}]\\0[M_{2},N_{1}]&A[M_{2},N_{2}]&\cdots &0[M_{2},N_{n}]\\\cdots &\cdots &\cdots &\cdots &\\0[M_{n},N_{1}]&0[M_{n},N_{2}]&\cdots &A[M_{n},N_{n}]\\\end{pmatrix}}}$

Задача (10),(4),(5) распадается на отдельные подзадачи

Найти минимум

(11) ${\displaystyle (d[M_{k}]A[M_{k},N_{k}]-c[N_{k}])z[N_{k}]+d[\delta ]}$

при условиях

(12) ${\displaystyle A[M_{k},N_{k}]z[N_{k}]=b[M_{k}]}$

• Хемди А. Таха. Глава 3. Симплекс-метод // Введение в исследование операций = Operations Research: An Introduction. — 7-е изд. — М.: «Вильямс», 2007. — С. 95-141. — ISBN 0-13-032374-8.

• Гольштейн E. Г., Юдин Д. Б. Новые направления в линейном программировании.. — М.: Советское радио, 1966.

• Юдин Д. Б., Гольдштейн Е. Г. Линейное программирование (теория, методы и приложения). — М.: Наука, 1969.

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