VII Международная студенческая научная конференция Студенческий научный форум - 2015

МЕТОД ДЕКОМПОЗИЦИИ Данцига-Вульфа

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

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

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

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

(1)

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

(2)

А_j и b- m- мерные векторы-столбцы (m