TR | UK | KK | BE | EN |

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


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

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

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

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

Содержание

  • 1 Метод генерации столбцов
  • 2 Принцип декомпозиции
  • 3 Алгоритм
  • 4 Блочные задачи
  • 5 Примечания
  • 6 Литература

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

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

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

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

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

Лемма Пусть R - непустое замкнутое ограниченное множество в евклидовом пространстве и обладает конечным числом K крайних точек, которые здесь будут обозначаться z k = 1 : K } Тогда любая точка z множества R может быть представлена в виде выпуклой комбинации крайних точек множества R, те для z найдутся неотрицательные числа δ k } с общей суммой единица ∑ k = 1 K δ m = 1 ^\delta _=1} и такие, что

1 z = ∑ k = 1 K δ k z k ^\delta _z_}

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

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

2 c [ N ] x [ N ]

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

3 A [ M 1 , N ] x [ N ] = b [ M 1 ] ,N]x=b}

4 A [ M 2 , N ] x [ N ] = b [ M 2 ] ,N]x=b}

5 x [ N ] ≥ 0 [ N ]

Ограничения 3 задают симплекс S, пусть z [ K ] - его крайние точки

Пусть x – допустимое решение По лемме x = z [ N , K ] ⋅ δ [ K ]

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

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

Максимизировать 6 c [ N ] ⋅ z [ N , K ] ⋅ δ [ K ] = g [ k ] ⋅ δ [ K ]

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

7 A [ M 1 , N ] ⋅ z [ N , K ] ⋅ δ [ K ] = D [ M 1 , K ] ⋅ δ [ K ] = b [ M 1 ] ,N]\cdot z\cdot \delta =D\cdot \delta =b}

8 δ [ k ] ⋅ 1 [ K ] = 1

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

Она имеет только | M 1 | + 1 |+1} строк ограничений по сравнению с | M 1 | + | M 2 | |+|M_|} строками исходной задачи, и очень большое число столбцов | K | , равное числу крайних точек множества S Чтобы не хранить все эти столбцы в памяти ЭВМ, будем получать их по мере необходимости, пользуясь методом генерации столбцов

Алгоритм

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

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

Обозначим через δ ограничение 8, тогда двойственные переменные - это вектор d [ M 1 ∪ δ ] \cup ]}

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

d [ M 1 ] D [ M 1 , K ] + d [ δ ] < g [ m ] ]D+d<g}

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

9 d [ M 1 ] A [ M 1 , N ] ⋅ z [ N , m ] + d [ δ ] − c [ N ] z [ N , m ] ]A\cdot z+d-cz}

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

минимизировать 10 d [ M 1 ] A [ M 1 , N ] − c [ N ] ⋅ x [ N ] ]A-c\cdot x}

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

Если найденный минимум не будет больше − d [ δ ] , задача решена

В противном случае столбец D [ M 1 , k ] ,k]} , соответствующий найденному решению, вводим в базис

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

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

A [ M 1 , N 1 ] 0 [ M 1 , N 2 ] ⋯ 0 [ M 1 , N n ] 0 [ M 2 , N 1 ] A [ M 2 , N 2 ] ⋯ 0 [ M 2 , N n ] ⋯ ⋯ ⋯ ⋯ 0 [ M n , N 1 ] 0 [ M n , N 2 ] ⋯ A [ M n , N n ] A&0&\cdots &0\\0&A&\cdots &0\\\cdots &\cdots &\cdots &\cdots &\\0&0&\cdots &A\\\end}}

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

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

11 d [ M k ] A [ M k , N k ] − c [ N k ] z [ N k ] + d [ δ ] ]A-cz+d}

при условиях

12 A [ M k , N k ] z [ N k ] = b [ M k ] ,N_]z=b}

Примечания

  1. ↑ George B Dantzig; Philip Wolfe 1960 “Decomposition Principle for Linear Programs” Operations Research 8: 101—111mw-parser-output citecitationmw-parser-output qmw-parser-output codecs1-codemw-parser-output cs1-lock-free amw-parser-output cs1-lock-limited a,mw-parser-output cs1-lock-registration amw-parser-output cs1-lock-subscription amw-parser-output cs1-subscription,mw-parser-output cs1-registrationmw-parser-output cs1-subscription span,mw-parser-output cs1-registration spanmw-parser-output cs1-hidden-errormw-parser-output cs1-visible-errormw-parser-output cs1-subscription,mw-parser-output cs1-registration,mw-parser-output cs1-formatmw-parser-output cs1-kern-left,mw-parser-output cs1-kern-wl-leftmw-parser-output cs1-kern-right,mw-parser-output cs1-kern-wl-right

Литература

  • Хемди А Таха Глава 3 Симплекс-метод // Введение в исследование операций = Operations Research: An Introduction — 7-е изд — М: «Вильямс», 2007 — С 95-141 — ISBN 0-13-032374-8
  • Гольштейн E Г, Юдин Д Б Новые направления в линейном программировании — М: Советское радио, 1966
  • Юдин Д Б, Гольдштейн Е Г Линейное программирование теория, методы и приложения — М: Наука, 1969


Разложение Данцига — Вулфа Информацию О

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


  • user icon

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

    29.10.2014


Разложение Данцига — Вулфа
Разложение Данцига — Вулфа
Разложение Данцига — Вулфа Вы просматриваете субъект
Разложение Данцига — Вулфа что, Разложение Данцига — Вулфа кто, Разложение Данцига — Вулфа описание

There are excerpts from wikipedia on this article and video

Случайные Статьи

Высокое (Гурьевский городской округ)

Высокое (Гурьевский городской округ)

Высо́кое — посёлок в Гурьевском городском округе Калининградской области. Входит в состав Низов...
Ортилия

Ортилия

Orthilia Raf., 1840 Синонимы Ramischia Opiz ex Garcke — Рами́шия Типовой вид Orthili...
Жигулёвск

Жигулёвск

Жигулёвск — город в Самарской области Российской Федерации, расположенный на правом берегу среднего ...
Южная Остроботния

Южная Остроботния

Финляндия Финляндия Статус Маакунта (область) Входит в Финляндия Включает 19 общин ...