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

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

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

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

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

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

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

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

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

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

Лемма Пусть - непустое замкнутое ограниченное множество в евклидовом пространстве и обладает конечным числом крайних точек, которые здесь будут обозначаться . Тогда любая точка множества может быть представлена в виде выпуклой комбинации крайних точек множества R, т.е. для найдутся неотрицательные числа с общей суммой единица () и такие, что

(1) .

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

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

(2)

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

(3)

(4)

(5)

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

Пусть x – допустимое решение По лемме

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

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

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

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

(7)

(8) .

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

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

Алгоритм

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

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

Обозначим через ограничение (8), тогда двойственные переменные - это вектор .

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

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

(9)

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

минимизировать (10)

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

Если найденный минимум не будет больше , задача решена.

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

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

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

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

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

(11)

при условиях

(12)

Примечания

  1. George B. Dantzig; Philip Wolfe. Decomposition Principle for Linear Programs (неопр.) // Operations Research. — 1960. Т. 8. С. 101—111.

Литература

  • Хемди А. Таха. Глава 3. Симплекс-метод // Введение в исследование операций = Operations Research: An Introduction. — 7-е изд. М.: «Вильямс», 2007. — С. 95-141. — ISBN 0-13-032374-8.
  • Гольштейн E. Г., Юдин Д. Б. Новые направления в линейном программировании.. М.: Советское радио, 1966.
  • Юдин Д. Б., Гольдштейн Е. Г. Линейное программирование (теория, методы и приложения). М.: Наука, 1969.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.