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

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

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

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

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

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

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

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

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

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

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

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

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

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

(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) имеют блочную структуру

$\left(\begin{array}{cccc}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{array}\right)$

Задача (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]$

Литература

• Шаблон:Книга

• Шаблон:Книга

• Шаблон:Книга