22-10-2023
Метод декомпозиции Данцига и Вульфа представляет собой специализированный вариант симплекс-метода.
В 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)
Методы оптимизации | |
---|---|
Одномерные | Метод золотого сечения • Дихотомия • Метод парабол • Перебор по сетке • Метод Фибоначчи • Троичный поиск • Метод Пиявского |
Прямые методы | Метод Гаусса • Метод Нелдера — Мида • Метод Хука — Дживса • Метод конфигураций • Метод Розенброка |
Первого порядка | Градиентный спуск • Метод Зойтендейка • Покоординатный спуск • Метод сопряжённых градиентов • Квазиньютоновские методы • Алгоритм Левенберга — Марквардта |
Второго порядка | Метод Ньютона • Метод Ньютона — Рафсона • Алгоритм Бройдена — Флетчера — Гольдфарба — Шанно (BFGS) |
Стохастические | Метод Монте-Карло • Имитация отжига • Эволюционные алгоритмы • Дифференциальная эволюция • Муравьиный алгоритм • Метод роя частиц |
Методы линейного программирования |
Симплекс-метод • Алгоритм Гомори • Метод эллипсоидов • Метод потенциалов |
Методы нелинейного программирования |
Последовательное квадратичное программирование |
Это заготовка статьи по математике. Вы можете помочь проекту, дополнив её. |
Разложение Данцига-Вулфа.