Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
метод Данцига.docx
Скачиваний:
35
Добавлен:
05.02.2016
Размер:
139.59 Кб
Скачать

10.1. Метод декомпозиции Данцига-Вульфа

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

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

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

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

                              (10.1.1)

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

                                (10.1.2)

Аj и b- m- мерные векторы-столбцы (m<n).

Допустим, что известно некоторое допустимое базисное решение (Д.Б.Р.) XB и соответствующая ему матрица из базисных векторов A. Допустим также, что XB был найден методом обратной матрицы. Тогда одновременно был найден и вектор относительных оценок  где Cx-вектор коэффициентов целевой функции для текущего базиса.

Чтобы определить возможность улучшения Д.Б.Р. XB для каждого небазисного вектора Aj вычисляется величина оценки

                (10.1.3)

Если то начальное решение может быть улучшено путем введения в базис переменной XS. Однако, если имеется большое число небазисных столбцов (n103), то нахождение Sпутем вычисления j для всех небазисных векторов  и последующего их сравнения практически невозможно. И что очень важно, оказывается, что это и не требуется.

 Будем предполагать, что все столбцы AS выбираются из некоторого выпуклого множества S, определяемого системой неравенств и равенств. Тогда вектор-столбец, который необходимо ввести в базис, можно определить в результате решения вспомогательной задачи вида:

минимизировать

                                   (10.1.4)

где  — некоторая заданная функция вектора Aj. В зависимости от структуры множества S и вида функции C(Aj) выбирается наиболее эффективный метод решения указанной задачи. Такой способ называют методом генерации столбцов, так как при решении задачи (10.1.4.) фактически используется лишь небольшое число столбцов, генерируемых по мере надобности. При этом значительно снижается требуемый объем памяти для хранения текущих результатов, что является существенным преимуществом при решении задач большой размерности.

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

Рассмотрим задачу ЛП, матрица ограничений которой имеет блочно-диагональную структуру вида

 .                            (10.1.5)

Строка  называется связывающей, так как она связывает вместе все переменные задачи в некотором ограничении или их группе. Соответствующая задача Л.П. записывается в виде:

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

                                   (10.1.6)

 при условиях

                               (10.1.7)

                       (10.1.8)

Заметим, что к виду (10.1.5) можно привести матрицу любой задачи ЛП при p=1 в результате соответствующего разбиения ограничений на два подмножества. Действительно, произвольную задачу можно записать в виде:

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

                                    (10.1.9)

при условиях

 (m1 ограничений),                           (10.1.10)

                                  (m2 ограничений),                     (10.1.11)

 .                                       (10.1.12)

Предположим, что выпуклое многогранное множество S2, определяемое условием (10.1.11), является ограниченным, т.е. представляет собой многогранник (это условие не является ограничительным). Тогда справедлива лемма о крайней точке, доказанная в приложении 1.

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

                      (10.1.3)

Обобщение этой леммы на случай, если множество является неограниченным, формулируется так: пусть — непусто. Любая точка принадлежит множеству R тогда и только тогда, когда она может быть представлена как выпуклая комбинация крайних точек и линейной комбинации с неотрицательными коэффициентами направляющих векторов неограниченных ребер множества, т.е.

                                    (10.1.14)

где

В соответствии с  леммой любой элемент S2 может быть представлен в виде

где                   xj - крайние точки многогранника S2.

Исходная задача (10.1.9)—(10.1.12) может быть сформулирована таким образом. Из всех решений (10.1.11)—(10.1.12) необходимо выбрать такое, которое удовлетворяет (10.1.10) и обращает функцию (10.1.9) в максимум. Подставляя (10.1.14) в (10.1.9), получим новое выражение для целевой функции

                               (10.1.15)

а подставив (10.1.14) в (10.1.10), получим

 .                                   (10.1.16)

Обозначим

                                (10.1.17)

С учетом (10.1.15)—(10.1.17) приходим к следующей задаче:

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

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

                                 (10.1.19)

                                     (10.1.20)

                                     (10.1.20)

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

                                   (10.1.22)

Представим вектор в виде  где вектор соответствует ограничениям (10.1.19) а  — единственному ограничению (10.1.20). Используя формулы (10.1.16), (10.1.17) для определения  и , получим

                 (10.1.23)

В соответствии с обычными правилами симплекс-метода для определения переменной , вводимой в базис, необходимо минимизировать

 .                            (10.1.24)

Так как оптимальное решение задачи ЛП (при условии, что допустимое множество — ограничено) достигается в крайней точке этого множества, то выполнение операции (10.1.24) эквивалентно решению подзадачи вида:

минимизировать

                        (10.1.25)

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

 .                    (10.1.26)

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

                                  (10.1.27)

а также соответствующий коэффициент в целевой функции

                                        (10.1.28)

Этот подход оказывается особенно эффективным, если  т.е. исходная задача записывается в виде

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

                             (10.1.29)

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

                     (10.1.30)

  

  

....                                       (10.1.31)

                             (10.1.32)

Для такой задачи подзадача (10.1.25)—(10.1.26) будет иметь вид:

минимизировать

                             (10.1.33)

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

                                       (10.1.34)

                               (10.1.35)

В силу аддитивности целевой функции (10.1.33) и независимости ограничений (10.1.34) задача (10.1.33) распадается на независимые задачи вида

                            (10.1.36)

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

                           (10.1.37)

Обозначим решение задачи (10.1.36) через а  Если  то вектор   может быть введен в базис координирующей задачи. Если же то текущее решение оптимально.