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

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

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

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

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

Метод генерации столбцов

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

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

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

Принцип декомпозиции

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

(1) [math]\displaystyle{ z = \sum_{k=1}^K \delta_k z_k }[/math].

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

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

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

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

(3) [math]\displaystyle{ A[M_1,N] x[N] = b[M_1] }[/math]

(4) [math]\displaystyle{ A[M_2,N] x[N] = b[M_2] }[/math]

(5) [math]\displaystyle{ x[N] \ge 0[N] }[/math]

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

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

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

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

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

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

(7) [math]\displaystyle{ (A[M_1,N] \cdot z[N, K]) \cdot \delta[K] = D[M_1, K] \cdot \delta[K] = b[M_1] }[/math]

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

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

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

Алгоритм

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

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

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

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

[math]\displaystyle{ d[M_1] D[M_1,K] + d[\delta] \lt g[m] }[/math]

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

(9) [math]\displaystyle{ d[M_1] A[M_1,N] \cdot z[N, m] + d[\delta] - c[N] z[N, m] }[/math]

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

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

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

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

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

Блочные задачи

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

[math]\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} }[/math]

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

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

(11) [math]\displaystyle{ (d[M_k] A[M_k,N_k] - c[N_k]) z[N_k] + d[\delta] }[/math]

при условиях

(12) [math]\displaystyle{ A[M_k,N_k] z[N_k] = b[M_k] }[/math]

Литература

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

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

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