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


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

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

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

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

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

Содержание

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

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

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

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

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

Лемма Пусть R - непустое замкнутое ограниченное множество, z_{m=1:r} - его крайние точки. Тогда любая точка z может быть представлена в виде выпуклой комбинации крайних точек множества R, т.е.

(1) z = \sum_{m=1}^r z_m \cdot \delta_m , где \delta_m \ge 0 , \sum_{m=1}^r \delta_m = 1.

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

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

(2) c[N] x[N]

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

(3) A[M_1,N] x[N] = b[M_1]

(4) A[M_2,N] x[N] = b[M_2]

(5) x[N] \ge 0[N]

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

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

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

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

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

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

(7) (A[M_1,N] \cdot  z[N, K]) \cdot \delta[K] = D[M_1, K] \cdot \delta[K] = b[M_1]

(8) \delta[k] \cdot  1[K] = 1.

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

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

Алгоритм

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

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

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

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

d[M_1] D[M_1,K] + d[\delta] < g[m]

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

(9) d[M_1] A[M_1,N] \cdot  z[N, m]  + d[\delta] - c[N] z[N, m]

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

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

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

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

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

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

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

\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) (d[M_k] A[M_k,N_k] - c[N_k]) z[N_k]  + d[\delta]

при условиях

(12) A[M_k,N_k] z[N_k] = b[M_k]

Примечания

  1. George B. Dantzig (1960). «Decomposition Principle for Linear Programs». Operations Research 8: 101–111.

Литература

  • Хемди А. Таха Глава 3. Симплекс-метод // Введение в исследование операций = Operations Research: An Introduction. — 7-е изд. — М.: «Вильямс», 2007. — С. 95-141. — ISBN 0-13-032374-8
  • Гольштейн E. Г., Юдин'Д Новые направления в линейном программировании.. — М.: Советское радио, 1966.
  • Юдин Д. Б., Голыптейн Е. Г. Линейное программирование (теория, методы и приложения). — М.: Наука, 1969.

Wikimedia Foundation. 2010.

Смотреть что такое "Разложение Данцига-Вулфа" в других словарях:

  • Транспортная задача — (задача Монжа  Канторовича)  математическая задача линейного программирования специального вида о поиске оптимального распределения однородных объектов из аккумулятора к приемникам с минимизацией затрат на перемещение.[1][2] Для… …   Википедия