Алгоритм решения нелинейной непрерывной многопродуктовой задачи оптимального разбиения множеств с размещением центров подмножеств
Наведено метод і алгоритм розв’язання нелінійної неперервної багатопродуктової задачі оптимального розбиття множини з nnn-вимірного евклідового простору на її неперетинні підмножини з розміщенням їх центрів при обмеженнях. Функції попиту та вартості транспортування продукції можуть бути різними для...
Gespeichert in:
| Datum: | 2012 |
|---|---|
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | Russian |
| Veröffentlicht: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2012
|
| Schriftenreihe: | Проблемы управления и информатики |
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/207446 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Алгоритм решения нелинейной непрерывной многопродуктовой задачи оптимального разбиения множеств с размещением центров подмножеств / Е.М. Киселева, В.А. Строева // Проблемы управления и информатики. — 2012. — № 1. — С. 40–53. — Бібліогр.: 21 назв. - рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-207446 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-2074462025-10-08T00:16:28Z Алгоритм решения нелинейной непрерывной многопродуктовой задачи оптимального разбиения множеств с размещением центров подмножеств Алгоритм розв’язання нелінійної неперервної багатопродуктової задачі оптимального розбиття множин з розташуванням центрів підмножин Algorithm for Solving Nonlinear Continuous Multi-Product Problem of Optimal Partitioning with Allocation of Subset Centers Киселева, Е.М. Строева, В.А. Оптимальное управление и методы оптимизации Наведено метод і алгоритм розв’язання нелінійної неперервної багатопродуктової задачі оптимального розбиття множини з nnn-вимірного евклідового простору на її неперетинні підмножини з розміщенням їх центрів при обмеженнях. Функції попиту та вартості транспортування продукції можуть бути різними для різних видів продукції. The method and algorithm for solving a nonlinear continuous multi-product problem of optimal partitioning of a set from nnn-dimensional Euclidean space into its non-intersecting subsets with allocation of their centers under constraints are presented. Functions of demand and transportation costs of products can vary for different types of products. 2012 Article Алгоритм решения нелинейной непрерывной многопродуктовой задачи оптимального разбиения множеств с размещением центров подмножеств / Е.М. Киселева, В.А. Строева // Проблемы управления и информатики. — 2012. — № 1. — С. 40–53. — Бібліогр.: 21 назв. - рос. 0572-2691 https://nasplib.isofts.kiev.ua/handle/123456789/207446 519.8 10.1615/JAutomatInfScien.v44.i2.20 ru Проблемы управления и информатики application/pdf Інститут кібернетики ім. В.М. Глушкова НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Оптимальное управление и методы оптимизации Оптимальное управление и методы оптимизации |
| spellingShingle |
Оптимальное управление и методы оптимизации Оптимальное управление и методы оптимизации Киселева, Е.М. Строева, В.А. Алгоритм решения нелинейной непрерывной многопродуктовой задачи оптимального разбиения множеств с размещением центров подмножеств Проблемы управления и информатики |
| description |
Наведено метод і алгоритм розв’язання нелінійної неперервної багатопродуктової задачі оптимального розбиття множини з nnn-вимірного евклідового простору на її неперетинні підмножини з розміщенням їх центрів при обмеженнях. Функції попиту та вартості транспортування продукції можуть бути різними для різних видів продукції. |
| format |
Article |
| author |
Киселева, Е.М. Строева, В.А. |
| author_facet |
Киселева, Е.М. Строева, В.А. |
| author_sort |
Киселева, Е.М. |
| title |
Алгоритм решения нелинейной непрерывной многопродуктовой задачи оптимального разбиения множеств с размещением центров подмножеств |
| title_short |
Алгоритм решения нелинейной непрерывной многопродуктовой задачи оптимального разбиения множеств с размещением центров подмножеств |
| title_full |
Алгоритм решения нелинейной непрерывной многопродуктовой задачи оптимального разбиения множеств с размещением центров подмножеств |
| title_fullStr |
Алгоритм решения нелинейной непрерывной многопродуктовой задачи оптимального разбиения множеств с размещением центров подмножеств |
| title_full_unstemmed |
Алгоритм решения нелинейной непрерывной многопродуктовой задачи оптимального разбиения множеств с размещением центров подмножеств |
| title_sort |
алгоритм решения нелинейной непрерывной многопродуктовой задачи оптимального разбиения множеств с размещением центров подмножеств |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| publishDate |
2012 |
| topic_facet |
Оптимальное управление и методы оптимизации |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/207446 |
| citation_txt |
Алгоритм решения нелинейной непрерывной многопродуктовой задачи оптимального разбиения множеств с размещением центров подмножеств / Е.М. Киселева, В.А. Строева // Проблемы управления и информатики. — 2012. — № 1. — С. 40–53. — Бібліогр.: 21 назв. - рос. |
| series |
Проблемы управления и информатики |
| work_keys_str_mv |
AT kiselevaem algoritmrešeniânelinejnojnepreryvnojmnogoproduktovojzadačioptimalʹnogorazbieniâmnožestvsrazmeŝeniemcentrovpodmnožestv AT stroevava algoritmrešeniânelinejnojnepreryvnojmnogoproduktovojzadačioptimalʹnogorazbieniâmnožestvsrazmeŝeniemcentrovpodmnožestv AT kiselevaem algoritmrozvâzannânelíníjnoíneperervnoíbagatoproduktovoízadačíoptimalʹnogorozbittâmnožinzroztašuvannâmcentrívpídmnožin AT stroevava algoritmrozvâzannânelíníjnoíneperervnoíbagatoproduktovoízadačíoptimalʹnogorozbittâmnožinzroztašuvannâmcentrívpídmnožin AT kiselevaem algorithmforsolvingnonlinearcontinuousmultiproductproblemofoptimalpartitioningwithallocationofsubsetcenters AT stroevava algorithmforsolvingnonlinearcontinuousmultiproductproblemofoptimalpartitioningwithallocationofsubsetcenters |
| first_indexed |
2025-10-08T01:09:53Z |
| last_indexed |
2025-10-09T01:05:25Z |
| _version_ |
1845464321324220416 |
| fulltext |
© Е.М. КИСЕЛЕВА, В.А. СТРОЕВА, 2012
40 ISSN 0572-2691
ОПТИМАЛЬНОЕ УПРАВЛЕНИЕ
И МЕТОДЫ ОПТИМИЗАЦИИ
УДК 519.8
Е.М. Киселева, В.А. Строева
АЛГОРИТМ РЕШЕНИЯ НЕЛИНЕЙНОЙ
НЕПРЕРЫВНОЙ МНОГОПРОДУКТОВОЙ ЗАДАЧИ
ОПТИМАЛЬНОГО РАЗБИЕНИЯ МНОЖЕСТВ
С РАЗМЕЩЕНИЕМ ЦЕНТРОВ ПОДМНОЖЕСТВ
Введение
Широкий класс теоретических и практических задач оптимизации сводится к
непрерывным задачам оптимального разбиения множеств (ОРМ). Таким, напри-
мер, как бесконечномерные задачи размещения предприятий с одновременным
разбиением данного региона, непрерывно заполненного потребителями, на обла-
сти потребителей, каждая из которых обслуживается одним предприятием, в це-
лях минимизации транспортных и производственных затрат; или частный случай
таких задач — бесконечномерные транспортные задачи и многие другие. Потре-
бителями могут быть телефонные абоненты, избиратели, школьники, клиенты
финансовых учреждений, диагностируемые пациенты т.д.
В [1] излагается математическая теория непрерывных линейных задач ОРМ
n-мерного евклидова пространства, которые являются неклассическими задачами
бесконечномерного математического программирования с булевыми значениями
переменных.
Предложенная в [1] математическая теория непрерывных задач ОРМ состоит
в сведении начальных бесконечномерных задач оптимизации через функционал
Лагранжа к негладким, как правило, конечномерным. Для численного решения
негладких конечномерных задач применяются современные эффективные методы
недифференцируемой оптимизации, а именно, различные варианты r-алгоритма,
разработанного в Институте кибернетики им. В.М. Глушкова НАН Украины под
руководством Н.З. Шора.
В [2–4] задачи из [1] обобщаются на нелинейный случай. В данной работе
рассматривается нелинейная непрерывная многопродуктовая задача ОРМ с раз-
мещением центров при ограничениях в виде равенств и неравенств, постановка
которой, по сравнению с задачей из [4], усложнена тем, что функции спроса и
стоимости транспортировки единицы продукции от предприятия к потребителю
задаются разными для разных видов продукции. Целью работы является приведе-
ние и теоретическое обоснование метода решения поставленной задачи, разработ-
ка алгоритма решения и его программная реализация, а также иллюстрация этого
алгоритма на нескольких модельных задачах.
1. Постановка задачи
Задача А. Пусть — ограниченное, измеримое по Лебегу, выпуклое множе-
ство в n-мерном евклидовом пространстве .nE Необходимо разбить его на NM
измеримых по Лебегу подмножеств 11
1 ,, N ;
22
1 ,, N ; ;
M
N
M ,,1
Международный научно-технический журнал
«Проблемы управления и информатики», 2012, № 1 41
(среди которых могут быть и пустые) и разместить «центры» N ,, , 21 этих
подмножеств в области , т.е. найти неизвестные заранее координаты центров
N ,, , 21 (каждый центр i является общим для подмножеств M
ii ,,1 )
так, чтобы
,...,,1 ,,,1, ,,0)(mes MjNkiki
j
k
j
i
где )(mes — мера Лебега,
M
j
i
j
N
i
j
i
j
i
pibdxxMj
11
,...,,1,)( ,...,,2,1,
M
j
i
j
j
i
Npibdxx
1
,...,,1,)(
и при этом функционал
)),,,(),...,,,...,,...,;...,,(( 211
22
1
11
1 N
M
N
M
NNF
dxxxcdxx j
i
j
M
j
N
i
jj
i
j
i
j
i
)(),()(
1 1
достигал своего минимального значения.
Здесь и в дальнейшем интегралы понимаются в смысле Лебега. Будем считать,
что мера множества граничных точек подмножеств ,
j
i ,,,1 Ni ,,,1 Mj
равна нулю. Под центром ),,(
)()1( n
iii понимается некоторая неизвестная
заранее эталонная точка для подмножества ,,,1,,,1, MjNi
j
i называе-
мая «центром» этого подмножества.
Функции ),( i
j xc действительные, ограниченные, определенные на ,
измеримые по аргументу x при любом фиксированном ),,(
)()1( n
iii из ,
;...,,1 Ni функции )(xj действительные, ограниченные, измеримые и неот-
рицательные на для всех ;,,1 Mj точка ),,(
)()1( n
iii — центр, об-
щий для подмножеств ,,,1 M
ii ,,,1 Ni один и тот же для всех ;,,1 Mj
,,,1,,,1 ),( MjNi
j
i — действительные, ограниченные, выпуклые,
дважды непрерывно-дифференцируемые функции своего аргумента, Nbb ,,1 —
заданные неотрицательные числа, причем
.,,1,0,)(
11
NiSbbdxxS i
N
i
i
M
j
j
(1)
На рис. 1 изображено
возможное разбиение множе-
ства 2E на три подмно-
жества по каждому из двух
видов продукции. Сплошной
линией обозначена граница
по первому виду продукции,
пунктирной — граница по
второму виду продукции,
i — общий центр для под-
множеств ,1
i .3,2,1,2 ii
1
1
1
2
2
2
2
1
1
3
2
3
),(
)2(
3
)1(
33
),(
)2(
1
)1(
11
),(
)2(
2
)1(
22
Рис. 1
42 ISSN 0572-2691
Введем характеристическую функцию подмножества :
j
i
,,,1,,,1
,\,0
,,1
)( MjNi
x
x
x
j
i
j
ij
i
и рассмотрим функционал
,)()(),()()( )),((
1 1
M
j
N
i
j
i
j
i
jj
i
jj
i dxxxxcdxxxI (2)
где вектор-функция )(x имеет вид )).(,),(;);(),....,(()( 1
11
1 xxxxx M
N
M
N
Очевидно, ).),,,(()),(( 1
1 M
NFI
Перепишем задачу А в следующем виде.
Задача В. Найти пару элементов )),((
**
x 1*
)(( x почти всюду (п.в.)
для ),
*
Nx такую, что
),),((min)),((
1)),((
**
IxI
N
; дляп.в. ))(,),(;);(,),.(()( :)( 11
11
11
xxxxxxx M
N
M
N
M
j
i
j
i
j
M
j
i
j
i
j Npibdxxxpibdxxx
11
,,,1,)()(,,,1,)()(
где 10)(:))(,),(;);(,),(()( 1
11
11
xxxxxx
j
i
M
N
M
N п.в. для x ,
,,...,1,,,1 MNi 1)(
1
N
i
j
i x п.в. для ,x ;,,1
Mj .),,( 1
N
N
От бесконечномерной задачи В с булевыми значениями переменных ),(
j
i
,,,1 Ni ,,,1 Mj перейдем к соответствующей задаче со значениями
),(
j
i ,,,1 Ni ,,,1 Mj из отрезка .]1 ,0[
Задача С. Найти пару элементов )),((
**
x , где ,)( 2*
x ,
*
N та-
кую, что
),),((min)),((
2)),((
**
IxI
N
M
j
i
j
i
j pibdxxxxxx
1
2 ,,,1,)()(; для п.в. )( :)(
M
j
i
j
i
j Npibdxxx
1
.,,1,)()(
Здесь ,,1)(0:))(,),(;);(,),(()( 1
11
1
xxxxxxx
j
i
M
N
M
N ,,,1 Ni
,,,1 Mj 1)(
1
N
i
j
i x п.в. для ,x .,,1
Mj
Международный научно-технический журнал
«Проблемы управления и информатики», 2012, № 1 43
2. Обоснование метода решения задачи
Для задачи С введем функционал Лагранжа следующим образом:
M
j
i
j
i
j
N
i
i bdxxxIh
11
)()()),(()),),(((
,)()()),(()()(
1 11
M
j
N
i
j
i
j
ii
jj
i
jj
ii
N
i
i dxxxxcdxxxb (3)
где ),,( 1 N — N-мерный вектор с действительными компонентами,
причем p ,,1 произвольны по знаку, а Np ,,1 неотрицательны;
)(x для ;x .),,( 1
N
N
Пару элементов )),),((( *
** назовем седловой точкой функционала (3) на
множестве ,)( N
где ),,,1,0:),,(( 1 NpiE iNN
если
)),),((()),),((())),),(((( **
****
hhh (4)
для всех , ,N , или
)),),(((maxmin)),),(((
)),((
*
**
hh
N
).),),(((minmax
)),((
h
N
(5)
Перейдем к решению задачи
.)),),(((minmax)),),(((
)),((
*
**
hh
N
(6)
Обозначим ),),),(((min)(
)),((
hG
N
, тогда двойственной к
задаче С будет задача
max,)( G . (7)
По аналогии с работой [2] для нахождения )),),(((min
)),((
h
N
перей-
дем к следующей задаче:
)),),(((minmin
)(
h
N
, при . (8)
Обозначим в (8)
),),),(((min),(
)(
1
hG ,N , (9)
тогда, учитывая в (9) выражение для )),),((( h из (3), получим
),(1G
,)()()),(()()( min
1 1)(1
M
j
N
i
j
i
j
ii
jj
i
jj
ii
N
i
i dxxxxcdxxxb (10)
,N .
44 ISSN 0572-2691
Обозначим в (10)
dxxxxcdxxx
j
i
j
ii
jj
i
jj
iii
j
i
j
i )()()),(()()(),),((
и рассмотрим задачу
,),),((min),),((min
1 1)(
M
j
N
i
ii
j
i
j
i ,N . (11)
Согласно [2] функционал ),),(( выпуклый по )( на ),(2 MNL если
),(
j
i ,,...,1,...,,1 MjNi — выпуклые функции своего аргумента, и минимум
по )( функционала ),),(( достигается на множестве . В свою очередь,
субградиент такого функционала при каждых фиксированных N и
будет иметь вид
...),,),(((),),((sgrad 11
1
11
1
)),,),((...,),,),((...;);,),((..., 111
1
1
1 NN
M
N
M
NNN M
N
M
N
где ),()),(()()()(),),(( xxcxdxxx j
ii
jjj
i
jj
iY
ii
j
i j
i
j
i
,,...,1 Ni
.,...,1 Mj
Для упрощения записи введем обозначение
....,,1,...,,1,)()( MjNidxxxY
j
i
jj
i
(12)
Согласно [6] необходимым и достаточным условием минимума по )( вы-
пуклого по )( функционала ),),(( на является условие
,0)))()((),,),((sgrad(min **
)(
dxxx
которое можно записать
.))(),,),((sgrad(min))(),,),((sgrad( *
)(
** dxxdxx
(13)
Из [6] также известно, что если для оптимальной вектор-функции )(* (за-
дачи минимизации без ограничений функционала ),),(( из (11)) ни на од-
ном множестве точек x ненулевой меры не удовлетворяется ни одно из урав-
нений Эйлера ,...,,1,...,,1,0),),((
*
MjNiii
j
ij
i
то для функционала
),),(( по переменной )( , при каждых фиксированных N и ,
выполняется условие сильной регулярности, которое можно записать так:
,00)()()(),(:mes
*
xdxxxxcx jj
i
jj
iY
ii
j
j
i
(14)
где
j
iY имеет вид (12).
Международный научно-технический журнал
«Проблемы управления и информатики», 2012, № 1 45
Следуя [1, 5, 6], если условие сильной регулярности (14) выполняется, то вектор-
функция )(* , которая доставляет минимум линейному функционалу правой части
формулы (13), определяется при каждых фиксированных N и из следу-
ющего операторного уравнения:
,0)()()(),(если ],1 ,0[
,0)()()(),(если ,1
,0)()()(),(если ,0
)(
*
*
*
*
xdxxxxc
xdxxxxc
xdxxxxc
x
jj
i
jj
iY
ii
j
jj
i
jj
iY
ii
j
jj
i
jj
iY
ii
j
j
i
j
i
j
i
j
i
,...,,1,...,,1 MjNi
а так как мера множества граничных точек подмножеств ,
j
i ,,...,1 Ni ,,...,1 Mj
равна нулю, и учитывая (14), имеем
)(
*
x
j
i
случаях,остальныхв0
),...,,1,,ивамиподмножестмеждуграницыточкахвт.е.
,0мерымножественатолькословамидругими(
дляп.в.,)()(),(
)()(),(,1
*
k
*
Nki
ki
xkidxxxxc
dxxxxc
j
k
j
i
jjj
kY
kk
j
j
i
jj
iY
ii
j
j
k
j
i
(15)
.,...,1 Mj
В выражении (10) (под знаком суммы) прибавим и вычтем
dxxx
j
i
jj
iY j
i
)()( ,
после чего получим
M
j
N
i
j
i
jj
ii
N
i
i dxxxbG
1 1)(1
1 )()( min),(
dxxxdxxx
j
i
jj
i
jj
iY j
i
)()()()(
,)()()()(),(
dxxxdxxxxc
j
i
jj
i
jj
iY
ii
j
j
i
,N . (16)
Учитывая выражение (15), перепишем (16) в части, которая линейно зависит
от ),(
j
i согласно ограничениям задачи С:
i
N
i
ibYG
1
2 ),,(
46 ISSN 0572-2691
,,
,)())(),((min )()(
1 1 ,1
N
M
j
N
i
jj
k
j
kY
kk
j
Nk
j
i
j
i
j
iY
j
i
j
i dxxYxcYYY
j
k
j
i (17)
.,...,1,0:)...,,;...;,...,(
1
1
11
1
M
j
i
j
iMN
M
N
M
N NibYEYYYYYUY
Итак, задачу (7), двойственную к задаче С, приведем к виду
j
i
j
i
j
iY
j
i
j
i
M
j
N
i
i
N
i
i
UY
YYYb j
i
N
)()( maxmin
1 11
,
max, )())(),((min
,1
dxxYxc jj
k
j
kY
kk
j
Nk
j
k (18)
.),...,1,0:)...,,;...;...,,(
1
1
11
1
M
j
i
j
iMN
M
N
M
N NibYEYYYYYUY
Таким образом, если ),(
j
i ,,...,1,,...,1 MjNi выпуклые, дважды непре-
рывно-дифференцируемые функции своего аргумента, и при каждых фиксиро-
ванных N и . Имеет место условие сильной регулярности:
,00)()()(),(:mes
*
xdxxxxcx jj
i
jj
iY
ii
j
j
i
,)()( dxxxY
j
i
jj
i
,,...,1 Ni .,...,1 Mj
Тогда седловая точка )),),((( *
** (где первая компонента является оптималь-
ным решением задачи С) функционала (3) на множестве )( N
определя-
ется для MjNi ,...,1,,...,1 и почти всех x следующим образом:
, при0
,, и при1
)(
*
***
j
i
j
q
j
ij
i
x
iqxx
x
где
dxxxxcx
j
i
jj
iY
ii
jj
i j
i
)()(),(:
***
*
,,...,1 , для п.в. ,)()(),((min
***
,1
Mjxkidxxxxc
j
k
jj
kY
kk
j
Nk
j
k
(19)
а в качестве
**
1
**
1
**
1 ...,, ,...,, ,...,, NNNYY выбирается оптимальное решение
двойственной задачи (7), которая приведена к виду
M
j
N
i
j
i
j
i
j
iY
j
i
j
ii
N
i
i
UY
YYYbG j
i
N
1 11
)()( maxmin)(
,
max,)())(),((min
,1
dxxYxc jj
k
j
kY
kk
j
Nk
j
k (20)
Международный научно-технический журнал
«Проблемы управления и информатики», 2012, № 1 47
M
j
i
j
iMN
M
N
M
N NibYEYYYYYUY
1
1
11
1 ),...,1,0:),...,;...;,...,(
при условиях
....,,1,0 Npii (21)
Поскольку, согласно [2], множества оптимальных решений задач В и С сов-
падают, перейдем к формулированию алгоритма решения задачи В, используя
формулы (19)–(21).
3. Алгоритм решения задачи
Для решения задачи (20), (21) используем эвристический алгоритм обобщенных
псевдоградиентов с растяжением пространства, близкий к r-алгоритму Шора [7].
Этот алгоритм описан в [2] для однопродуктовой задачи, а здесь он обобщен и
применен для случая многопродуктовой задачи.
От задачи (20), (21) перейдем к задаче безусловной оптимизации по с помо-
щью введения в целевую функцию (17) негладких штрафных функций множеств
),...,1,0( Npii , ),...,1,,...,1,0( MjNiY
j
i ,
M
j
i
j
i NibY
1
,...,1, :
),,,(maxminmax
YP
MN
N
N EYE
(22)
где
),,(),,( 2 YGYP
,,0max),0max( )max(0,
1 1
3
1 1 1
21
N
i
i
M
j
j
i
N
pi
M
j
N
i
j
ii bYSYSS (23)
321 , , SSS — достаточно большие положительные числа, значительно больше
максимальных значений множителей Лагранжа для функции (17). Возможность
перехода от задачи (20), (21) к (22), (23) рассматривается в [1, 7, 8].
Обобщенный псевдоградиент функции (23) в точке
),...,;,...,;...,,...,;...,,(),,( 111
11
1 NN
M
N
M
N YYYYY
имеет вид
)),,,(),...,,,( );,,(),...,,,(
);,,(...,),,,(...;);,,(...,),,,((
)),,(),,,(),,,((),,(
11
1
11
1
YgYgYgYg
YgYgYgYg
YgYgYgYg
NN
M
N
M
N
pppp
Y
p
Y
p
Y
p
Y
p
pp
Y
pp
а его компоненты определяются следующим образом:
— по :
j
iY
dxxxYYYYg
j
i
jj
i
j
YiY
j
i
j
i
j
YiY
Y
p j
i
j
i
j
i
j
i
j
i )()()()(),,(
,sign,0max))(sign,0max(
1
32
i
M
j
j
i
j
i bYSYS (24)
MjNi ...,,1,...,,1 ;
48 ISSN 0572-2691
— по :i
,,...,1,)(),()( ),,(
1
NidxxxgxYg
j
ii
c
M
j
j
p
i
j
i
(25)
где ),(
xg i
jc
— i-я компонента N-мерного вектора обобщенного градиента ),( xg jc
функции ),,( i
j xс ,,...,1 Mj в точке ),,...,,...,( 1 Ni где )...,,(
)()1( n
iii
при фиксированном x имеет вид
;,...,1 ,
),(
...............
),(
),(
)(
)1(
Mj
xg
xg
xg
n
i
j
i
j
i
j
c
c
c
— по :i
M
j
ii
j
i
j
M
j
i
j
i
j
p
NpiSbdxxx
pibdxxx
Yg i
1
1
1
....,,1)),(signmax(0,)()(
,...,,1,)()(
),,( (26)
В формулах (24)–(26) ),(x
j
i ,...,,1,...,,1 MjNi определяются следую-
щим образом:
случаях,остальных в0
, дляп.в.
)),(),((min)(),( если,1
)(
,1
xki
YxcYxc
x
j
k
j
kY
kk
j
Nk
j
i
j
iY
ii
j
j
i
j
k
j
i
(27)
Алгоритм. Область заключаем в n-мерный параллелепипед , стороны ко-
торого параллельны осям декартовой системы координат. Положим 0)( xj при
,\x ....,,1 Mj Параллелепипед покрываем прямоугольной сеткой и за-
даем начальное приближение ).,,(),,( )0()0()0( YY Вычисляем значение
)()0( x в узлах сетки по формулам (27) при ,)0(YY ,)0( ,)0( а значе-
ние ),,,( )0()0()0( YgY
p ),,,( )0()0()0( Yg p ),,( )0()0()0( Yg p в узлах сетки —
по формулам (24)–(26) при ,)0(YY ,)0( ,)0( ).()( )0( xx Выбираем
начальный шаг 00 h r-алгоритма.
Первый шаг алгоритма выполняем по формулам
),,,( )0()0()0(
0
)0()1( YghYY Y
p
)),,,((P )0()0()0(
0
)0()1(
Ygh p
),,,( )0()0()0(
0
)0()1( Ygh p
где P — оператор проектирования на .
Переходим ко второму шагу. Пусть в результате вычислений после k, ...,,2,1k
шагов алгоритма в узлах сетки получены значения ,)(kY ,)(k ,)(k )()1( xk .
Международный научно-технический журнал
«Проблемы управления и информатики», 2012, № 1 49
Опишем (k 1)-й шаг алгоритма.
1. Вычисляем значения )()( xk в узлах сетки по формулам (27) при
.,, )()()( kkkY
2. Вычисляем значения ),,( Yg p по формулам (24)–(26) при
),()( )( xx k ,)(kYY ,)(k .)(k
3. Проводим (k 1)-й шаг r-алгоритма обобщенных псевдоградиентов с рас-
тяжением пространства, близкого к r -алгоритму Шора в H-форме [7], короткая
схема которого имеет вид
,
)),,( ),,,((
),,(
)()()()()()(
1
)()()(
1)()1(
kkkY
p
kkkY
pk
kkkY
pk
k
kk
YgYgH
YgH
hYY
,
)),,( ),,,((
),,(
P
)()()()()()(
1
)()()(
1)()1(
kkk
p
kkk
pk
kkk
pk
k
kk
YgYgH
YgH
h
.
)),,(),,,((
),,(
)()()()()()(
1
)()()(
1)()1(
kkk
p
kkk
pk
kkk
pk
k
kk
YgYgH
YgH
h
Здесь 1kH — матрица растяжения пространства с коэффициентом в направле-
нии разности двух последовательных обобщенных градиентов, которая определя-
ется следующим образом:
,
),(
1
1
21
kkk
k
T
kkk
kk
H
HH
HH
),,(),,( )1()1()1()()()( kkkT
p
kkkT
pk YgYg
(здесь T — одна из переменных Y, или ). Шаговый множитель kh выбираем из
условия минимума разности
),,(),,( )1()()1(
2
)()1()(
2
kkkkkk YGYG
по направлению антипсевдоградиента ),,( Yg p в преобразованном пространстве.
4. Переходим к (k 2)-му шагу алгоритма, если условие
,),,(),,( )1()1()1()()()( kkkkkk YY ,0 (28)
не выполняется, в противном случае — к п. 5.
5. Полагаем ,)(* lYY ,)(
*
l ,)(* l ),()( )(
*
xx l где l — номер
итерации, на которой выполнилось условие (28).
6. Вычисляем оптимальное значение целевого функционала по формуле (23)
при ,*YY ,
*
* и для контроля правильности вычислений по формуле
.)()(),()()( )),((
1 1
*****
M
j
N
i
j
i
j
i
jj
i
jj
i dxxxxcdxxxI
Алгоритм описан.
4. Решение модельных задач
Приведенный алгоритм реализован для модельных бесконечномерных задач
размещения предприятий. В заданной области девять предприятий производят
50 ISSN 0572-2691
продукцию трех видов для размещенного в этой области с заданной плотностью
потребителя, с ограничениями на мощность предприятий в виде равенств и нера-
венств. Следует заметить, что стоимость транспортировки единицы продукции к
потребителю задается в виде евклидовой метрики, метрики Чебышева или ман-
хэттенской, в зависимости от вида продукции. В модельной задаче 1 функция
спроса )(xj на продукцию задается аналитически для каждого j-го, ,,...,1 Mj
вида продукции, а в модельной задаче 2 равна единице в каждой точке x .
Модельная задача 1. Задано множество потребителей продукции трех ви-
дов, которая может производиться девятью пунктами производства. Граница об-
ласти потребителей определена: .}100,100:),{( yxyx Стоимость
транспортировки единицы продукции с i-го, ,9 ,1i предприятия к потребителю
),( yx для каждого j-го, ,3 ,1 j вида продукции задается следующим образом:
.3если,
,2если),,(max
,1если,)()(
),,(
)2()1(
)2()1(
2)2(2)1(
jyx
jyx
jyx
yxc
ii
ii
ii
i
j
Спрос ),( yxj на продукцию j-го вида распределен по области с плотно-
стью .3 ,1,
003,110)(ln
1
),(
j
yx
yx
j
j
Графики функции спроса для каждого из трех видов продукции представле-
ны на рис. 2 (для первого вида продукции
003,110)(ln
1
:),(1
yx
yx — (а);
для второго вида продукции
003,110)(ln
1
:),(
2
2
yx
yx — (б); для третьего
вида продукции
003,110)(ln
1
:),(
3
3
yx
yx — (в)).
0,216
0,214
0,212
0,21
0
2
4
6
8
10 10
8
6
4
2
0
0,3
0 2 4 6 8 10 10
8
6
4
2
0
0,4
0,2
0 2 4 6 8 10 10
8
6
4
2 0
0,3
а б в
Рис. 2
Функции ),(
j
i
j
i Y описывающие зависимость стоимости производства про-
дукции j-го вида на i-м предприятии от его мощности ,
j
iY имеют вид
,)()( 2j
i
j
i
j
i YY ,9,1i где мощность
j
iY i-го предприятия по производству j-го
вида продукции определяется по формуле .),(
j
i
dydxyxY jj
i
Мощность i-го, ,9,1i пункта производства по всем видам продукции опре-
деляется суммарным спросом потребителей, которые принадлежат ,
j
i ,3 ,1 j
Международный научно-технический журнал
«Проблемы управления и информатики», 2012, № 1 51
и для пунктов производства с номерами 3, 6, 8 должна быть равна заданным объ-
емам, а для пунктов производства с номерами 1, 2, 4, 5, 7, 9 не должна превышать
заданных объемов:
3
1
,9,7,5,4,2,1,),( 0
j
i
j
j
i
ibdydxyx
,1007,1 b ,862 b ,804 b ,175 b ,259 b
3
1
,8,6,3,),(
j
i
j
j
i
ibdydxyx ,363 b ,56 b .158 b
Требуется разбить множество потребителей на их зоны обслуживания
j
i
девятью предприятиями по каждому виду продукции при условии, что ,
9
1
i
j
i
,3,1j ,0)(mes
j
k
j
i ,ki ,9,1, ki ,3,1j и разместить эти предприя-
тия в области так, чтобы минимизировать функционал суммарных затрат на
производство продукции и доставку ее к потребителю:
}),...,{ },,...,;,...,;,...,({ 91
3
9
3
1
2
9
2
1
1
9
1
1F
.),(),(),(
3
1
9
1
j
i
j
i
dydxyxxcdydxyx j
i
jjj
i
j i
Не исключается и тот случай, когда некоторые из подмножеств ,
j
i ,9 ,1i
,3 ,1j окажутся пустыми.
Множество покрывалось сеткой с узлами ),( ji , ,21,...,1i .21,...,1j
В качестве начальных значений двойственных переменных заданы ,0
)0(
i
9 ,1i ; начальные значения мощностей предприятий: ,10
)0(
1 Y ,100
)0(
2 Y
,10
)0(
3 Y ,10
)0(
4 Y ,100
)0(
5 Y ,10
)0(
6 Y ,10
)0(
7 Y ,100
)0(
8 Y 10
)0(
9 Y ;
начальные координаты размещения предприятий ,)0 ;0(
)0(
i .9,1i
Условием прекращения вычислений является выполнение неравенства
,),,(),,( )1()1()1()()()( kkkkkk YY .10 3
В результате работы алгоритма за 131-у итерацию получены:
максимальное значение функционала двойственной задачи ;92,1754* G
минимальное значение функционала прямой задачи ;89,1745
*
F
оптимальные мощности каждого из девяти предприятий: ,95,1*
1 Y ,54,0*
2 Y
,65,35*
3 Y ,73,1*
4 Y ,85,1*
5 Y ,96,4*
6 Y ,71,1*
7 Y ,98,14*
8 Y ;98,1*
9 Y
оптимальные координаты размещенных предприятий: ),07,3;93,8(*
1 *
2
),60,6;83,4( ),61,4;32,5(*
3 ),42,6;20,9(*
4 ),79,0;78,7(*
5 ),1,99;78,4(*
6
),97,0;05,1(*
7 ),53,7;67,3(*
8 ).9,07;26,9(*
9
Оптимальное разбиение множества потребителей на девять зон обслуживания
каждым из девяти предприятий по трем видам продукции представлено на рис. 3: для
первого вида (а); для второго вида (б); для третьего вида продукции (в).
52 ISSN 0572-2691
8
3
8
6
7 5
1
4
9
3
8
7
9
а б в
Рис. 3
Модельная задача 2. В постановке первой модельной задачи зададим функ-
цию спроса .3,1,1),( jyxj При таких условиях после 227-й итерации полу-
чим следующие результаты:
максимальное значение функционала двойственной задачи 77,13226* G ;
минимальное значение функционала прямой задачи ;41,13226
*
F
оптимальные мощности каждого из девяти предприятий: ,89,50*
1 Y
,57,49*
2 Y ,87,35*
3 Y ,91,50*
4 Y ,99,16*
5 Y ,99,4*
6 Y ,77,50*
7 Y ,89,14*
8 Y
;97,24*
9 Y
оптимальные координаты размещенных предприятий: ),55,2;14,6(*
1 *
2
),62,3;49,3( ),982, ;49,8(*
3 ),82,7;37,6(*
4 ),45,8;09,9(*
5 ),6,00;49,9(*
6
),98,7;06,2(*
7 ),61,4;91,1(*
8 ).1,75;73,1(*
9
Оптимальное разбиение множества потребителей на девять зон обслуживания
каждым из девяти предприятий по трем видам продукции для модельной задачи 2
представлено на рис. 4: для первого вида (а); для второго вида (б); для третьего вида
продукции (в).
Из результатов рассмотренных модельных задач можно сделать следующие
выводы:
1) для каждой из задач выполняются условия разрешимости (1) задачи А, т.е.
общая оптимальная мощность девяти предприятий, полученная по алгоритму реше-
ния (для модельной задачи 1 это 65,35, а для модельной задачи 2 это 299,85), не пре-
вышает S 464 — суммы заданных ограничений на объемы мощностей предприятий;
2) полученные оптимальные мощности третьего, шестого и восьмого пред-
приятий в каждой из задач отвечают ограничениям в виде равенств, т.е. равны за-
данным значениям, а именно: *
3Y 36, *
6Y 5, *
8Y 15;
3) в задаче 1 для ,1),( yxj
,3,1 j некоторые из подмножеств за счет ви-
да функции ),( yxj оказались пустыми, что не противоречит постановке исход-
ной задачи. Так, на рис. 3, а пустыми оказались подмножества с номерами 1, 2, 4,
5, 6, 7, 9 и т. п.
7
2
8
5
6
3
7
6
9
1
4
5
8
1
7
9
5
8
4
6
3
а б в
Рис. 4
Международный научно-технический журнал
«Проблемы управления и информатики», 2012, № 1 53
Описанный алгоритм реализован на языке Visual Fortran 6.5 в среде Microsoft
Visual Studio.
Заключение
Сформулирована нелинейная непрерывная многопродуктовая задача опти-
мального разбиения множества из n-мерного евклидова пространства на его не-
пересекающиеся подмножества с размещением их центров при ограничениях в
форме равенств и неравенств. В отличие от ранее рассмотренных задач, функции
спроса и стоимости транспортировки единицы продукции от предприятия до по-
требителя заданы разными для каждого вида продукции. На основе приведенного
метода решения поставленной задачи разработан алгоритм, который является эв-
ристическим алгоритмом обобщенных псевдоградиентов с растяжением про-
странства, близкий к r-алгоритму Шора. Результат программной реализации алго-
ритма проиллюстрирован на модельных задачах.
О.М. Кісельова, В.О. Строєва
АЛГОРИТМ РОЗВ’ЯЗАННЯ НЕЛІНІЙНОЇ
НЕПЕРЕРВНОЇ БАГАТОПРОДУКТОВОЇ ЗАДАЧІ
ОПТИМАЛЬНОГО РОЗБИТТЯ МНОЖИН
З РОЗТАШУВАННЯМ ЦЕНТРІВ ПІДМНОЖИН
Наведено метод і алгоритм розв’язання нелінійної неперервної багатопродук-
тової задачі оптимального розбиття множини з n-вимірного евклідового про-
стору на її неперетинні підмножини з розміщенням їх центрів при обмеженнях.
Функції попиту та вартості транспортування продукції можуть бути різними
для різних видів продукції.
E.M. Kiselova, V.A. Stroyeva
ALGORITHM OF THE SOLUTION
OF NONLINEAR CONTINUOUS MULTIGROCERY
PROBLEM OF OPTIMAL SET PARTITIONING
WITH ALLOCATION OF THE SUBSETS CENTERS
The method and algorithm of the solution of nonlinear continuous multigrocery prob-
lem of optimаl partitioning of а set from n-dimensional Euclidean space on its
nonintersecting subsets with allocation of their centers at the presence of restrictions
are presented. Functions of demand and cost of transportation of production are sup-
posed to be different for different kinds of products.
1. Киселева Е.М., Шор Н.З. Непрерывные задачи оптимального разбиения множеств: теория,
алгоритмы, приложения. — Киев : Наук. думка, 2005. — 564 с.
2. Киселева Е.М., Дунайчук М.С. Решение непрерывной нелинейной задачи оптимального
разбиения множеств с размещением центров подмножеств для случая выпуклого целевого
функционала // Кибернетика и системный анализ. — 2008. — № 2. — С. 134–152.
3. Кісельова О.М., Дунайчук М.С. Теорема Куна–Таккера для нелінійної неперервної задачі
оптимального розбиття множин // Математичне моделювання. — 2007. — № 2 (17). —
С. 41–45.
4. Киселева Е.М., Дунайчук М.С. Об алгоритме решения непрерывной нелинейной многопро-
дуктовой задачи оптимального разбиения множеств // Математика. Компьютер. Образова-
ние : XV междунар. конф., г. Дубна, 28 янв.–2 фев., 2008 г. : Тез. докл. — М., 2008. —
С. 445.
5. Васильев Ф.П. Методы решения экстремальных задач. — М. : Наука, 1981. — 400 с.
6. Трухаев Р.Н., Хоменюк В.В. Теория неклассических вариационных задач. — Л. : ЛГУ, 1971.
— 168 с.
7. Шор Н.З. Методы минимизации недифференцируемых функций и их приложение. — Ки-
ев : Наук. думка, 1979. — 200 с.
8. Федоров В.В. Численные методы максимина. — М. : Наука, 1979. — 280 с.
Получено 08.08.2011
|