Разлажэнне Данцыга - Вулфа

Метад декомпозиции Данцыга - Вулфа ўяўляе сабой спецыялізаваны варыянт сімплекс-метаду
У 1960 г Джордж Данцыг і Філіп Вулфruen распрацавалі метад декомпозиции для вырашэння задач высокай памернасці са спецыяльнай структурай матрыцы абмежаванняў [1]
Гэты метад аказаўся найбольш эфектыўным для вырашэння задач , матрыца абмежаванняў якіх мае блокава-Дыяганальны выгляд з невялікім лікам зменных Аднак, як паказалі далейшыя даследаванні, метад выкарыстоўваецца і ў дачыненні таксама і для задач лінейнага праграмавання з матрыцай агульнага выгляду соотв тствующий метад прапанаваны Д Б Юдзін і Э Г Гальштэйн і называецца блокавым праграмаваннем
Адметнай асаблівасцю метаду декомпозиции з'яўляецца выкарыстанне каардынуючай задачы, якая мае, у параўнанні з зыходнай, невялікі лік радкоў і вялікі лік слупкоў
Змест
1 Метад генерацыі слупкоў
2 Прынцып декомпозиции
3 Алгарытм
4 Блокавыя задачы
5 Заўвагі
6 Літаратура
Метад генерацыі слупкоў
Істотным з'яўляецца тое, што для вырашэння каардынуючай задачы не патрабуецца заданні
ўсіх слупкоў ў відавочным ві дэ Яны генеруюцца ў працэсе выкарыстання сімплекс-метаду Такі падыход называюць метадам генерацыі слупкоў
Дастаткова ўмець генераваць слупок і мець працэдуру, выбіраю слупок для ўводу ў базіс
Часта такая працэдура зводзіцца да вырашэння пэўнай подзадачи не абавязкова лінейнага праграмавання
прынцып декомпозиции
лема Няхай



R




- непустым замкнёнае абмежаваную мноства ў эўклідавай прасторы і валодае канчатковым лікам



K




крайніх т очек, якія тут будуць пазначацца




z

k
=
1
:
K




}

Тады любая кропка



z




мноства



R




можа быць прадстаўлена ў выглядзе выпуклай камбінацыі крайніх кропак мноства R, тыя для



z




знойдуцца неадмоўныя колькасці




& # x03B4;

k




}

з агульнай сумай адзінка




& # x2211;

k
=
1


K



& # x03B4;

m


=
1


^ delta _ = 1}

і такія, што
1



z
=

& # x2211;

k
=
1


K



& # x03B4;

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
]
& # x22 65;
0
[
N
]




Абмежаванні 3 задаюць сімплекс S, хай



z
[
K
]




- яго крайнія кропкі
Няхай x - дапушчальнае рашэнне
Па лема



x
=
z
[
N
,
K
]
& # x22C5;
& # x03B4;
[
K
]




Падставім апошняе выраз у 2 і 3
Задача прыме выгляд
Максымізаваць
6




c
[
N
]
& # x22C5;
z
[
N
,
K
]

& # x22C5;
& # x03B4;
[
K
]
=
g
[
k
]
& # x22C5;
& # x03B4;
[
K
]




пры абмежаваннях
7




A
[

M

1


,
N
]
& # x22C5;
z
[
N
,
K
]

& # x22C5;
& # x03B4;
[
K
]
=
D
[

M

1


,
K
]
& # x22C5;
& # x03B4 ;
[
K
]
=
b
[

M

1


]


, N] cdot z cdot delta = D cdot delta = b}


8



& # x03B4;
[
k
]
& # x22C5;
1
[
K
]
=
1




Гэтая задача эквівалентная зыходнай 2-5 і называецца каардынуючай задачай
Яна мае толькі




|


M

1



|

+
1


| +1}

радкоў абмежаванняў у параўнанні з




|


M

1



|

+

|


M

2



|



| + | M_ |}

радкамі зыходнай задачы, і вельмі вялікі лік слупкоў




|

K

|





, роўнае ліку крайніх кропак мноства



S




Каб не захоўваць усе гэтыя слупкі ў памяці ЭВМ, будзем атрымліваць іх па меры неабходнасці, карыстаючыся метадам генерацыі слупкоў
Алгарытм
Вырашаем задачу 6-8 сімплекс-метадам з выкарыстаннем метаду генерацыі слупкоў
Для прастаты выкажам здагадку, што ўжо вядома некаторы дапушчальнае базіснае рашэнне
Пазначым праз



& # x03B4;




абмежаванне 8, тады дваістыя зменныя - гэта вектар



d
[

M

1


& # x222A;

& # x03B4;

]


cup]}

Для ўводу ў базіс неабходна знайсці



z
[
N
,
m
]




, такі, што



d
[

M

1


]
D
[

M

1


,
K
]
+
d
[
& # x03B4;
]
& lt;
g
[
m
]


] D + d & lt; g}

Такім чынам досыць знайсці m, на якім дасягаецца мінімум
9



d
[

M

1


]
A
[

M

1


,
N
]
& # x22C5;
z
[
N
,
m
]
+
d
[
& # x03B4;
]
& # x2212;
c
[
N
]
z
[
N
,
m
]


] A cdot z + d-cz}

што эквівалентна вырашэння задачы
мінімізаваць
10




d
[

M

1


]
A
[

M

1


,
N
]
& # x2212;
c
[
N
]

& # x22C5;
x
[
N
]



] Ac cdot x}


пры абмежаваннях 4 і 5
Калі знойдзены мінімум не будзе больш



& # x2212;
d
[
& # x03B4;
]



, задача вырашана
У адваротным выпадку слупок



D
[

M

1


,
k
]


, k]}

, адпаведны знойдзенаму рашэнню, ўводзім ў базіс
Блокавыя задачы
Няхай абмежаванні 4 маюць блокавую структуру









A
[

M

1


,

N

1


]


0
[

M

1


,

N

2


]


& # x22EF;


0
[

M

1


,

N

n


]




0
[

M

2


,

N

1


]


A
[

M

2


,

N

2


]


& # x22EF;


0
[

M

2


,

N

n


]




& # x22EF;


& # x22EF;


& # x22EF;


& # x22EF;





0
[

M

n


,

N

1


]


0
[

M

n


,

N

2


]


& # x22EF;


A
[

M

n


,

N

n


]








A & amp; 0 & amp; cdots & amp; 0 \ 0 & amp; A & amp; cdots & amp; 0 \ cdots & amp; cdots & amp; cdots & amp; cdots & amp; \ 0 & amp; 0 & amp; cdots & amp; A \ end}}

Задача 10,4,5 распадаецца на асобныя подзадачи
Знайсці мінімум
11




d
[

M

k


]
A
[

M

k


,

N

k


]
& # x2212;
c
[

N

k


]

z
[

N

k


]
+
d
[
& # x03B4;
]


] A-cz + d}

пры ўмовах
12



A
[

M

k


,

N

k


]
z
[

N

k


]
=
b
[

M

k


]


, N_] z = b}

Заўвагі
↑ 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
метады оптимизацииОдномерные
Метад залатога перасеку
дыхатамію
Метад парабалы
Перабор па сетцы
Метад раўнамернага блокавага пошуку
Метад Фібаначы
трынітарнай пошук
Метад Пиявского
Метад Стронгина
Прамыя метады
Метад Гаўса
Метад Нелдера - МЗС
Метад Хука - Джівса
Метад канфігурацый
Метад Розенброка
ервого парадку
Градыентнае спуск
Метад Зойтендейка
Покоординатный спуск
Метад спалучаных градыентаў
Квазиньютоновские метады
Алгарытм Левенберга - Марквардт
Другога парадку
Метад Ньютана
Метад Ньютана - Рафсона
алгарытм Бройдена - Флетчара - Гольдфарба - Шанно BFGS
стахастычнага
Метад Монтэ-Карла
Імітацыя адпалу
Эвалюцыйныя алгарытмы
Дыферэнцыяльная эвалюцыя
мурашыных алгарытм
Метад роя часціц
Алгарытм пчалінай калоніі
Метад выпадковых блуканняў
Метады линейногопрограммирования
Сімплекс -метод
Алгарытм гаморам
Метад эліпсоід
Метад патэнцыялаў
Метады нелинейногопрограммирования
Паслядоўнае квадратычны праграмаванне
Гэта пачатак артыкула па матэматыцы Вы можаце дапамагчы праекту, пашырыўшы яго
Для паляпшэння артыкула пажадана:
праставіць зноскі, занесці больш дакладныя ўказанні на источникиВикифицировать артыкул


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

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

Громов, Евгений Иванович

Громов, Евгений Иванович

Евгений Иванович Громов (10 февраля 1909(19090210) — 21 ноября 1981, Москва) — советский п...
J

J

J: J — буква латиницы Ј — буква кириллицы j — обозначение палатального сонорного сог...
Пайдейя

Пайдейя

Пайдейя (др.-греч. παιδεία — воспитание детей; от παιδος — мальчик, подросток) — категория...
Каделл ап Грифид

Каделл ап Грифид

Ка́делл ап Гри́фид (валл. Cadell ap Gruffydd) (умер в 1175 году) — правитель королевства Дехейб...