Метод лінеаризації та негладка оптимізація
Two modifications of nonstandard application of linearization method to solve unsmooth optimization problems are considered. On the basis of its modification for solve problems of back-convex programming, there has been developed an applied programs packet called Packing. The effectiveness of the pa...
Saved in:
| Date: | 2009 |
|---|---|
| Main Authors: | , |
| Format: | Article |
| Language: | Russian |
| Published: |
The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute"
2009
|
| Online Access: | https://journal.iasa.kpi.ua/article/view/107843 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | System research and information technologies |
| Download file: |  |
Institution
System research and information technologies| _version_ | 1866302005135278080 |
|---|---|
| author | Nenakhov, E. I. Sobolenko, L. A. |
| author_facet | Nenakhov, E. I. Sobolenko, L. A. |
| author_sort | Nenakhov, E. I. |
| baseUrl_str | http://journal.iasa.kpi.ua/oai |
| collection | OJS |
| datestamp_date | 2018-04-06T12:33:14Z |
| description | Two modifications of nonstandard application of linearization method to solve unsmooth optimization problems are considered. On the basis of its modification for solve problems of back-convex programming, there has been developed an applied programs packet called Packing. The effectiveness of the packet and its modifications is illustrated by examples of different packing and arrangement of the objects. |
| first_indexed | 2025-07-17T10:22:30Z |
| format | Article |
| fulltext |
© Э.И. Ненахов, Л.А. Соболенко, 2009
90 ISSN 1681–6048 System Research & Information Technologies, 2009, № 3
TIДC
МЕТОДИ ОПТИМІЗАЦІЇ, ОПТИМАЛЬНЕ
УПРАВЛІННЯ І ТЕОРІЯ ІГОР
УДК 519.853
МЕТОД ЛИНЕАРИЗАЦИИ И НЕГЛАДКАЯ ОПТИМИЗАЦИЯ
Э.И. НЕНАХОВ, Л.А. СОБОЛЕНКО
Рассматриваются две модификации нестандартного применения метода ли-
неаризации к решению негладких оптимизационных задач. На основе моди-
фикации для задач обратно-выпуклого программирования разработан па-
кет прикладных программ Packing. Показана эффективность работы пакета и
этой модификации на примерах различных задач упаковки и размещения
объектов.
ВВЕДЕНИЕ
Метод линеаризации [1], используемый на протяжении многих лет, показал
себя как один из самых эффективных методов решения общих задач мате-
матического программирования. При этом главным требованием к функци-
ям, описывающим оптимизационную задачу, является их гладкость. Однако
идеи, положенные в основу метода линеаризации, могут быть успешно ис-
пользованы при решении многих других задач, которые не вкладываются в
его первоначальную схему. Хотя метод создан для решения гладких задач
оптимизации, он сразу нашел применение к решению некоторых минимакс-
ных задач.
Для решения общей задачи выпуклого программирования в [2] разра-
ботан комбинированный метод, основанный на идеях трех методов: линеа-
ризации, отсечения и точных штрафных функций. Комбинированный метод
сходится при общих предположениях и позволяет оценить множители Лаг-
ранжа. При его модификации отбрасываются несущественные для решения
задачи ограничения, что позволяет значительно уменьшить размерность ре-
шаемой на каждой итерации вспомогательной квадратичной задачи. Стаби-
лизация штрафного коэффициента — основа быстрой сходимости постро-
енных алгоритмов.
Комбинированный метод решения общей задачи выпуклого програм-
мирования с негладкими функциями показал свою эффективность на слож-
ных тестовых задачах и достаточную конкурентоспособность по сравнению
с другими методами оптимизации [2].
Еще одним классом негладких оптимизационных задач являются зада-
чи обратно-выпуклого программирования. Эти задачи — многоэкстремаль-
ные. В работе [3] предложена эффективная модификация метода линеари-
зации для отыскания локальных экстремумов общей задачи обратно-
Метод линеаризации и негладкая оптимизация
Системні дослідження та інформаційні технології, 2009, № 3 91
выпуклого программирования. Ответить на вопрос, является ли полученное
решение глобальным экстремумом, в общей постановке крайне сложно. Од-
нако численные результаты показали, что при решении отдельных конкрет-
ных задач получение глобального экстремума небезуспешно.
В общую схему задачи обратно-выпуклого программирования вклады-
ваются многие формализованные математические модели задач упаковки и
размещения различных объектов в пространстве nR . Эти задачи широко
применяются. Поэтому так велик к ним интерес многих специалистов, в том
числе работающих в области численных методов оптимизации. В отличие
от традиционных методов классической математики решения этих задач
[4,5] при численном их решении появляется возможность значительно уве-
личивать размерности задач и снимать многие ограничения на формы и раз-
меры объектов.
Существуют различные подходы к численному решению таких задач.
Часто рассматриваются и решаются отдельные конкретные задачи упаковки
[6–8]. В данной работе используется подход, основанный на формулировке
проблемы упаковки в виде общей оптимизационной задачи обратно-
выпуклого программирования и решении ее модифицированным методом
линеаризации [3]. На основе этого метода разработан и реализован графиче-
ский пакет программ Packing [9], с помощью которого пользователь имеет
возможность, легко изменяя начальные положения рассматриваемых объек-
тов, получать различные локальные решения и выбирать из них наилучшее.
Удобная интерактивная среда Packing предоставляет в распоряжение поль-
зователя не только численные результаты, но и визуальные изображения
положений объектов (параллелепипедов, шаров и т. п.) в двумерном и трех-
мерном пространствах. Для пространств nR , где 3>n , предоставляются
только численные результаты.
Объем публикации не позволяет описать все множество решенных за-
дач. Для наглядности графического представления в работе не приводятся
примеры задач для пространств nR , где 3>n . Представлены лишь несколь-
ко задач, которые показались авторам интересными.
КОМБИНИРОВАННЫЙ МЕТОД РЕШЕНИЯ ЗАДАЧИ ВЫПУКЛОГО
ПРОГРАММИРОВАНИЯ
Рассмотрим задачу
{ }Mxmjxfxf j
x
∈=≤ ;,...,1;0)(|)(min , (1)
где nRx∈ , )(xf и )(xf j , mj ,...,1= — выпуклые непрерывные функции;
M — выпуклый многогранник. Через ∗x обозначим решение задачи (1).
При выполнении условия Слейтера ∗x множители Лагранжа задачи (1) ju ,
mj ,.,1 …= , существуют.
Для произвольной выпуклой функции )(xf ее субдифференциал в точ-
ке x существует. Обозначим его )(xf∂ . Элементы выпуклого компактного
множества )(xf∂ обозначим )(xf ′ . Предположим в дальнейшем, что
Э.И. Ненахов, Л.А. Соболенко
ISSN 1681–6048 System Research & Information Technologies, 2009, № 3 92
выбрано правило, которое ставит в соответствие точке x элемент
)()( xfxf ∂∈′ . Исследуемые алгоритмы могут отличаться правилом выбора
)(xf ′ , что влияет на эффективность конкретной реализации алгоритма, но
от этого не зависит его сходимость.
Если определить выпуклую функцию )(max)( xfx j
j
=φ , то задача (1)
эквивалентна задаче
{ }Mxxxf
x
∈≤ ;0)(|)(min φ . (2)
Введем штрафную функцию { } 0,)(,0max)()( >+=Φ NxNxfxN φ .
Лемма. Если число N достаточно велико, ∑
=
>
m
j
juN
1
, то задачи (1),
(2) и
{ } { }MxxxfNMxx
x
N
x
∈≥≤≤+=∈Φ ;0,)(,)(|min|)(min 22121
, 2,1
ξξφξξξ
ξξ
(3)
эквивалентны. Решение задачи (3) есть )(, 1
∗∗∗ = xfx ξ , 02 =∗ξ .
Опишем алгоритм решения задачи (1). Пусть заданы исходная точка
Mx ∈1 и число 0>N , а исходный массив 1X состоит из единственной точ-
ки 1x .
Если массив kX и число kN построены, то массив 1+kX и число
1+kN определяются по такому правилу. Вычисляем kx из условия
}|)({min kiiN Xxx
k
∈Φ . Полагаем kNN = и решаем вспомогательную за-
дачу квадратичного программирования в пространстве 2+nR
21
2
,, 2
1min
21
ξξ
ξξ
Nxx kx
++− ,
kixxxfxf iii ,...,1,)),(()( 1 =≤−′+ ξ , (4)
kixxxx iii ,...,1,)),(()( 2 =≤−′+ ξφφ , Mx∈≥ ,02ξ .
Здесь и далее . означает евклидову норму вектора, а (.,.) скалярное
произведение двух векторов. Полагаем { }11 ++ = kkk xXX ∪ ,
⎪⎩
⎪
⎨
⎧
>
=
=+ ,0если,2
,0если,
2
2
1 k
k
k
k
k N
NN
ξ
ξ
где 1+kx , k
1ξ , k
2ξ — решение задачи (4).
Начиная с некоторого достаточно большого номера k , kN будет кон-
стантой N и 02 =kξ .
Кроме того, справедливо равенство
0)]()([lim 21 =+−Φ
∞→
kk
kNk
Nx ξξ .
Отсюда, для вектора kkk xxp −= +1 выполняется 0lim =
∞→
kk
p . В пре-
дельной точке последовательности{ } Mxk ⊂ выполняются необходимые и
Метод линеаризации и негладкая оптимизация
Системні дослідження та інформаційні технології, 2009, № 3 93
достаточные условия экстремума, а критерием останова итерационного про-
цесса является ε≤kp , 0>ε [2].
Комбинированный метод может привести к большому накоплению ин-
формации, т.е. к неограниченному росту точек массива kX . Некоторые из
этих точек не играют роли в окончательном процессе нахождения решения
задачи. Поэтому предлагается процедура отбрасывания несущественных для
решения ограничений, которая позволяет существенно уменьшить размер-
ность решаемой на каждой итерации квадратичной задачи (4).
Если для точки ki Xx ∈ выполняется неравенство
0,)),(()( 2
11 >−≤−′+ + δδξ k
k
ikii pxxxfxf ,
то при решении задачи (4) на всех последующих итерациях соответствую-
щее ограничение в ней отбрасывается. Если же выполняется неравенство
0,)),(()( 2
21 >−≤−′+ + δδξφφ k
k
ikii pxxxx ,
то аналогично отбрасывается соответствующее ограничение в задаче (4). Но
неравенства, соответствующие точкам 1+kx и kx , всегда участвуют в реше-
нии вспомогательной задачи.
Построенный комбинированный метод, в отличие от хорошо известных
методов решения гладких задач, не содержат выбора шагового множителя
вдоль направления спуска.
МЕТОД РЕШЕНИЯ ЗАДАЧИ ОБРАТНО-ВЫПУКЛОГО
ПРОГРАММИРОВАНИЯ
Рассмотрим задачу
{ }mixfxf i
x
,...,1,0)(|)(max 0 =≥ , (5)
где nRx∈ , )(xfi , mi ,...,1,0= — выпуклые непрерывные функции. Несмот-
ря на то, что функции )(xfi выпуклы, задача (5) не является выпуклой в
обычном понимании, и нельзя утверждать о единственности ее решения.
Она многоэкстремальная.
Пусть { }mixfxD i ,...,1,0)(: =≥= — допустимое множество зада-
чи (5). Предположим, что начальная точка Dx ∈0 . Если точка kx уже по-
строена, то новая точка вычисляется так:
kkk pxx +=+1 . (6)
Вектор )( kk xpp = определяет направление движения в итерационном
процессе и является решением следующей задачи квадратичного програм-
мирования:
⎭
⎬
⎫
⎩
⎨
⎧ =≥++−
∈
mixfpxfppxf kikik
Rp n
,...,1,0)()),((|
2
1)),((min '2'
0 . (7)
Существенно, что шаговый множитель в направлении движения не вы-
числяется, а сразу полагается равным 1.
Э.И. Ненахов, Л.А. Соболенко
ISSN 1681–6048 System Research & Information Technologies, 2009, № 3 94
В работе [3] доказано, что все точки итерационной последовательно-
сти (6) Dxk ∈ , ...,1=k . В каждой из них вспомогательная задача (7) имеет
единственное решение )( kxp . При ∞→k , 0→kp и в любой предельной
точке последовательности (6) выполняются необходимые условия экстре-
мума и ограничения задачи (5). На основе этих утверждений итерационный
процесс (6) останавливается, когда ε≤kp , где ε — заданная точность
решения исходной задачи (5).
Пусть )( k
i xu , mi ,...,1= — множители Лагранжа, соответствующие
вспомогательной задаче (7). Они являются решением задачи, двойственной
к задаче (7).
⎪⎭
⎪
⎬
⎫
⎪⎩
⎪
⎨
⎧
=≥+′+′− ∑∑
==∈
miuxfuxfuxf i
ki
m
i
i
m
i
k
i
k
Ru iim
,...,1,0|)()()(
2
1min
1
2
1
. (8)
Решения задач (7) и (8) связаны соотношением
∑
=
′+′=
m
i
kk
i
kk xfxuxfxp
i
1
0 )()()()( . (9)
Задача (8) приводится к виду
{ }miuu i
Ru m
,...,1,0|)(min =≥
∈
φ , (10)
где ),(),(
2
1)( udCuuu +−=φ ; C — mm× -симметричная матрица с элемен-
тами )())(( T
, kjkiji xfxfc ′′= , mji ,...,1, = , а компоненты вектора d опреде-
ляются соотношением )()())(( T
0 kikik
i xfxfxfd +′′−= , mi ,...,1= . Здесь и
далее в формулах буква Т вверху означает знак транспонирования.
Очевидно, что задача (10) имеет более простые ограничения по сравне-
нию с задачей (7). Поэтому в рассматриваемом пакете программ решается
задача (10), а вектор направления kp вычисляется по формуле (9).
Метод решения задачи (10), реализованный в Packing, подробно описан
в работе [10]. Это конечный метод, который относится к методам активного
набора. Очень кратко суть его состоит в следующем.
Пусть }0|,...,1{ ≥== iumiJ — индексное множество ограничений за-
дачи (10), а }0|{ =∈= iuJiI — множество ее активных ограничений в те-
кущей точке.
Опишем кратко действия на одной итерации, начиная с допустимой
точки Jiu i ∈≥ ,00 . Вычисляем )( 0uI и градиент )( 0uφ′ . Если 0
)( 0 ≥
∂
∂
iu
uφ
,
для всех )( 0uIi∈ , а 0
)( 0 =
∂
∂
iu
uφ
для всех )( 0uIi∉ , то 0u — решение зада-
чи, так как выполняются необходимые и достаточные условия минимума
задачи (10). Если для какого-то индекса )( 0uIi∈ , 0
)( 0 <
∂
∂
iu
uφ
либо суще-
Метод линеаризации и негладкая оптимизация
Системні дослідження та інформаційні технології, 2009, № 3 95
ствуют индексы, для которых 0
)( 0 ≠
∂
∂
iu
uφ
, )( 0uIi∉ , то определяется мно-
жество
⎭
⎬
⎫
⎩
⎨
⎧ ≥
∂
∂
∈=′ 0|)( 0 iu
uIiI φ .
Удерживая нулевыми компоненты вектора 0u по Ii ′∈ , применяем из-
вестный метод сопряженных градиентов по остальным компонентам этого
вектора. При этом контролируется величина шагового множителя в направ-
лении метода сопряженных градиентов, чтобы новая точка оставалась до-
пустимой. Через конечное число шагов будет найдена точка 1+ku такая, что
в ней )(uφ достигает минимума при условии Iiu i ′∈= ,0 , либо новая до-
пустимая точка, для которой IuI k ′⊃+ )( 1 . В обоих случаях точка 1+ku счи-
тается начальной, и процесс повторяется.
ПРИМЕРЫ ЗАДАЧ
Все представленные в работе задачи решены с использованием пакета
программ Packing. С помощью меню, системы окон и панели инструментов
пакета пользователь указывает тип задачи, который определяется ее форма-
лизованной математической моделью, задает начальное положение рассмат-
риваемых объектов и указывает их размеры. Некоторые начальные данные,
например, размеры и начальное положение искомого оптимального объекта
пакет устанавливает сам по умолчанию. Эти данные пользователь может
отредактировать или оставить, если они для него приемлемы. При этом ав-
томатически происходит графическое отображение объектов на экране ком-
пьютера. Затем по указанию пользователя пакет решает задачу. Численные
результаты решения поступают в выходной файл пакета, а графическое изо-
бражение решения задачи отображается на экране компьютера. При описа-
нии задач здесь для графического представления результатов решения бу-
дем использовать средства Packing.
1. Задача определения шара наименьшего радиуса, объемлющего
заданные шары различных радиусов. Пусть имеется m шаров )( ir xS
i
,
mi ,...,1= , с центрами n
i Rx ∈ и радиусами ir . Требуется найти шар наи-
меньшего радиуса, объемлющий данные шары. Если R — искомый радиус
объемлющего шара, а x — его неизвестный центр, то формально задачу
можно записать так:
⎪⎩
⎪
⎨
⎧
=−≤−
=<+≥−
.,...,1,
,,...,1,,,|
min
,, mirRxx
mjijirrxxR
ii
jiji
xxR i
(11)
Здесь первые 2
mC (число сочетаний из m по 2) ограничений задачи
представляют условие не пересечения заданных шаров, а вторая группа
из m ограничений — условие не выхода заданных шаров за границы иско-
мого шара.
Э.И. Ненахов, Л.А. Соболенко
ISSN 1681–6048 System Research & Information Technologies, 2009, № 3 96
В результате решения задачи (11) мы должны получить значения ко-
ординат центров оптимального расположения упаковываемых шаров, ко-
ординаты центра и радиус объемлющего шара. Отсюда и из (8) видно, что
размерности задачи определяются по следующим формулам: число неиз-
вестных равно nmnn ×++= 11 , число ограничений — mCm m += 2
1 .
Рассмотрим сначала плоский случай в пространстве 2R . Пусть дано
девять кругов одинакового радиуса и один круг, радиус которого в два раза
больше. Нужно найти круг минимального радиуса, объемлющий эти круги.
Следовательно, задача имеет 23 неизвестных и 55 ограничений. Пусть ради-
ус седьмого круга равен 1, а для остальных кругов 5,0=ir ; 108,61 ……=i .
Числовые значения координат центров кругов в начальном положении и в
решении приведены в табл. 1.
Т а б л и ц а 1 . Центры кругов в начальном положении и в точках решения
Номер
круга
1
0x 2
0x 1
∗x 2
∗x
Номер
круга
1
0x 2
0x 1
∗x 2
∗x
0 0 0 3,17 3,91 6 7 7 4,48 4,64
1 1 3 1,70 3,61 7 3 4 3,17 3,91
2 3 2 3,15 2,41 8 4 8 3,73 5,30
3 3 6 2,73 5,34 9 2 6 1,92 4,74
4 5 4 4,65 3,66 10 1 2 2,21 2,75
5 6 1 4,11 2,74
В табл. 1 нулевой номер определен для внешнего круга, а дальше идут
номера упаковываемых
кругов. Для координаты
ix нижний индекс 0
дан для начальных дан-
ных, а «∗» — для ре-
зультатов решения. Этот
принцип заполнения
таблиц будет сохранен и
при описании остальных
задач. Начальное значе-
ние для радиуса объем-
лющего круга Packing
установил 40,100 =R .
Это значение 0R вполне
допустимо, так как все
круги в начальном по-
ложении оказываются
внутри объемлющего круга. Таким образом, предположение в алгоритме
Dx ∈0 удовлетворяется. Графические отображения кругов в начальном по-
ложении и положение кругов в точках решения, данные пакетом, показаны
на рис. 1. Начальное положение — левая часть рисунка, правая — положе-
ние кругов в решении. Здесь внешний объект (в данном случае круг) по ука-
Рис. 1. Упаковка 10-ти кругов разных радиусов в круг
минимального радиуса
10 разных кругов Решение задачи
Метод линеаризации и негладкая оптимизация
Системні дослідження та інформаційні технології, 2009, № 3 97
занию пользователя отображается только справа. Внешний объект Packing
всегда подается сероватым прозрачным фоном. Радиус наименьшего круга,
объемлющего данные круги, 00,2=∗R . Из рис. 1 очевидно, что получено
оптимальное решение с точностью 2105,0 −⋅≤kp на 26-й итерации.
Приведем пример упаковки 21-го шара одинакового радиуса в шар наи-
меньшего радиуса в трехмерном пространстве. Размерности этой задачи
следующие: число неизвестных — 67, ограничений — 231. Пусть радиусы
шаров 21,...,1, =iri равны 0,5, а начальное значение радиуса искомого ша-
ра 0R равно 12,71. Числовые значения координат центров шаров в началь-
ном положении и в решении приведены в табл. 2.
Т а б л и ц а 2 . Центры шаров в начальном положении и в точках решения
Номер
шара
1
0x 2
0x 3
0x 1
∗x 2
∗x 3
∗x Номер
шара
1
0x 2
0x 3
0x 1
∗x 2
∗x 3
∗x
0 0 0 0 2,58 3,23 2,04 11 4 4 3 2,76 3,26 2,24
1 2 2 5 2,55 2,37 2,94 12 3 7 5 1,74 3,97 2,57
2 3 6 1 2,24 4,40 1,83 13 5 6 5 2,68 4,12 2,90
3 2 4 6 2,00 3,18 3,13 14 –3 3 2 1,39 3,06 2,35
4 6 5 6 3,00 3,22 3,21 15 3 0 0 2,86 2,01 2,05
5 7 3 2 3,56 2,58 1,61 16 0 5 0 1,53 3,76 1,63
6 6 7 2 2,88 4,04 1,15 17 3 3 0 3,08 3,09 0,90
7 8 7 6 3,67 3,56 2,55 18 –2 –3 –3 2,48 2,33 1,18
8 6 4 4 3,47 2,58 2,61 19 –3 0 –5 2,14 3,43 0,89
9 5 7 5 3,21 4,30 2,06 20 0 –3 4 1,89 2,20 2,20
10 7 6 3 3,67 3,57 1,55 21 0 –3 4 1,61 2,76 1,42
На рис. 2 дано графическое отображение шаров: слева — начальное
положение, справа — положение шаров в решении и объемлющий их шар.
Радиус объемлющего шара 74,1=∗R . Число итераций, используемых мето-
Рис. 2. Упаковка 21-го шара в шар минимального радиуса
Э.И. Ненахов, Л.А. Соболенко
ISSN 1681–6048 System Research & Information Technologies, 2009, № 3 98
дом, — 194. На рисунке видно, что внешний шар очень плотно объемлет
заданные шары.
2. Задача упаковки шаров в параллелепипед с минимальной сум-
мой сторон. Требуется упаковать шары mixS iri ,...,1),( = , с центрами
n
i Rx ∈ и радиусами ir в параллелепипед, сумма сторон которого мини-
мальна. Если неизвестные стороны параллелепипеда обозначить kξ ,
nk ,...,1= , то формально задача сведется к оптимизационной задаче
⎪
⎭
⎪
⎬
⎫
⎪
⎩
⎪
⎨
⎧
==−≤≤
=<+≥−∑
=
.,...,1,,...,1,
,,...,1,,,
min 1,
nkmirxr
mjijirrxx
i
kk
ii
т
k
jiji
k
xi
k
ξ
ξ
ξ
. (12)
Здесь формулы для определения размерностей задачи имеют вид
nmnn ×+=1 , nmCm m ×+= 22
1 .
Эту задачу рассмотрим на примере упаковки 16-ти кругов одинакового
радиуса в прямоугольник с минимальной суммой сторон. Тогда 341 =n ,
1841 =m . Пусть радиусы ,ir 16,...,1=i , заданных кругов равны 0,5, а на-
чальные значения для сторон прямоугольника, в который упаковываются
шары, 251
0 =ξ , 262
0 =ξ . Координаты центров начального расположения за-
данных 16-ти кругов ix0 , 2,1=i , и их координаты в решении ix∗ , 2,1=i ,
приведены в табл. 3.
Т а б л и ц а 3 . Центры кругов в начальном положении и в точках решения
Номер
круга
1
0x 2
0x 1
∗x 2
∗x Номер
круга
1
0x 2
0x 1
∗x 2
∗x
1 7 1 3,5 1,5 9 9 0 3,5 0,5
2 3 8 1,5 3,5 10 3 6 1,5 2,5
3 1 10 0,5 3,5 11 4 4 2,5 3,5
4 2 2 1,5 0,5 12 0,5 0,5 0,5 0,5
5 4 3 2,5 2,5 13 9 2,5 3,5 2,5
6 6 3 3,5 3,5 14 1 6 0,5 2,5
7 4 2 2,5 1,5 15 1 4 0,5 1,5
8 5 1 2,5 0,5 16 3 5 1,5 1,5
Размеры полученного прямоугольника с минимальной суммой сторон,
содержащего заданные круги, такие: 0,41 =∗ξ , 0,42 =∗ξ . Для получения это-
го решения с заданной точностью 01,0=ε описанному методу решения за-
дачи обратно-выпуклого программирования потребовалось выполнить 61
итерацию. Графическое отображение начала и окончания итерационного
процесса (6), (7) дано на рис. 3. В левой части рисунка изображены круги в
начальном положении, справа — круги в точках решения и полученный оп-
тимальный прямоугольник, в который они упакованы.
Метод линеаризации и негладкая оптимизация
Системні дослідження та інформаційні технології, 2009, № 3 99
3. Задача оптимальной упаковки параллелепипедов. Пусть паралле-
лепипед в пространстве nR задается с помощью центра nRx∈ и вектора
полуосей nRa∈ , т.е. параллелепипед )(xCa определен системой неравенств
{ }niaxyRyxC iiin
a ,...,1,|)( =≤−∈= . (13)
Рассмотрим непересекающиеся параллелепипеды. Чтобы выразить ус-
ловие не пересечения двух параллелепипедов )(xCa и )(yCb , nRyx ∈, , в
работе [11] введено понятие квазирасстояния с помощью функции
( )∑
=
+−−=
n
k
kkkk
ba bayxfyCxC
1
)())(),(( εερ . (14)
Если обозначить )(|| kkkk bayxt +−−= , то
⎩
⎨
⎧
<
≥
=
,0,
,0,
)(
tt
tt
tf
εε
)1,0(∈ε . Два параллелепипеда )(xCa и )(yCb не пересекаются, когда
( ) 0)(),( ≥yCxC baερ .
При фиксированных значениях a и b ( ))(),(),( yCxCyx baεε ρρ = яв-
ляется выпуклой положительно однородной функцией аргументов yx, .
Следовательно, можно найти ее субградиенты.
Сформулируем задачу оптимальной упаковки параллелепипедов.
Пусть имеется m непересекающихся параллелепипедов )( ja xC
j
,
mj ,...,1= , и контейнер },...,1,0:{ nkAyRyC kkn
A =≤<∈= , в который
их нужно уложить. Здесь kA — компоненты вектора nRA∈ , определяюще-
го размеры контейнера. Предполагается, что параллелепипеды можно пере-
мещать только параллельным сдвигом. Обозначим kξ , nk ,...,1= , величины
Рис. 3. Упаковка 16-ти кругов в параллелепипед с минимальной суммой сторон
Э.И. Ненахов, Л.А. Соболенко
ISSN 1681–6048 System Research & Information Technologies, 2009, № 3 100
выхода параллелепипедов за границу контейнера по каждой из сторон
nkAk ,...,1, = . Тогда получим следующую оптимизационную задачу:
( )
⎪
⎪
⎪
⎭
⎪⎪
⎪
⎬
⎫
⎪
⎪
⎪
⎩
⎪⎪
⎪
⎨
⎧
==+≤+
==≥−
=<≥+−−∑∑
==
.,..,1,,...,1,
,,..,1,,...,1,0
,,...,1,,,0)(|||
min
11
,
nkmiAax
nkmiax
mjijiaaxxf
kkk
i
k
i
k
i
k
i
n
k
k
j
k
i
k
j
k
i
n
k
k
xi
k
ξ
ξ ε
ξ
(15)
Замечание. Из формул (15) следует, что для величин kξ , nk ,...,1= ,
допускаются как положительные, так и отрицательные значения. Это позво-
ляет не только найти центры оптимальной укладки параллелепипедов, но и
размеры самого контейнера, если они неизвестны. Для этого достаточно за-
дать значения kA ,, nk ,...,1= , произвольно, а затем, решив задачу, скоррек-
тировать их на основе полученных значений nkk ,...,1, =ξ .
Размерности задачи (15) определяются по формулам nmnn ×+=1 , а
число ограничений nmCm m ×+= 22
1 .
В качестве примера рассмотрим задачу в трехмерном пространстве.
Пусть задан контейнер следующих размеров: 31 =A , 22=A , 33=A и 10
непересекающихся параллелепипедов различной формы и ориентации. Раз-
меры параллелепипедов и координаты их центров в начальном положении
указаны в табл. 4, соответствующие функции ερ положительны. Их нужно
уложить в контейнер таким образом, чтобы сумма величин, обозначающих
нарушение границ контейнера, была минимальной.
Т а б л и ц а 4 . Размеры параллелепипедов и их центры в начальном
положении
Номер
паралл.
1
0x 2
0x 3
0x 1a 2a 3a Номер
паралл
1
0x 2
0x 3
0x 1a 2a 3a
1 3 3 4 0,5 1 0,5 6 4 5 0 1 1 0,5
2 6 3 5 0,5 1 0,5 7 6 0 0 0,5 0,5 0,5
3 5 2 1 1 0,5 0,5 8 1,5 1 5 0,5 1 0,5
4 6 4 3,5 0,5 0,5 0,5 9 2 2 2 0,5 1 0,5
5 6 4 0,5 0,5 0,5 0,5 10 4 4 2 0,5 0,5 0,5
Решение на рис. 4 справа получено с точностью 009,0≤kp на 32-й
итерации алгоритма (6), (7). При этом пакету программ Packing дано задание
изображать внешний объект (в данном случае контейнер). В левой части
рис. 4 виден контейнер и параллелепипеды в начальном положении. Внача-
ле ни один параллелепипед полностью не расположен внутри контейнера.
Следовательно, условие Dx ∈0 не выполнено. Однако это не является пре-
пятствием для метода, поскольку в точке 0x оказалась разрешимой вспомо-
гательная задача (7), и тогда сходимость алгоритма обеспечена [3].
Метод линеаризации и негладкая оптимизация
Системні дослідження та інформаційні технології, 2009, № 3 101
В правой части рис. 4 все параллелепипеды находятся внутри контей-
нера, а 059,01 =∗ξ ; 098,02 −=∗ξ ; 106,03 =∗ξ . Значения координат центров
параллелепипедов в решении даны в табл. 5.
Т а б л и ц а 5 . Оптимальные значения координат центров параллеле-
пипедов
Номер
паралл.
1
∗x 2
∗x 3
∗x Номер
паралл.
1
∗x 2
∗x 3
∗x
1 1,53 1,02 2,54 6 1,04 1,02 0,50
2 2,56 1,02 2,56 7 2,56 0,50 0,50
3 2,05 0,50 1,52 8 0,50 1,00 2,56
4 2,56 1,52 1,54 9 0,51 1,02 1,53
5 2,56 1,52 0,51 10 1,53 1,52 1,52
4. Задача оптимальной упаковки грузов в самолет. Пусть имеется
m грузов для перевозок самолетом. Известны массы грузов mimi ,...,1, = , и
центр тяжести самолета, определяемый вектором nRx ∈∗ . Для обеспечения
нормального маневра самолета грузы необходимо уложить в имеющийся в
самолете контейнер так, чтобы в результате увеличения нагрузки смещение
известного центра тяжести самолета ∗x было минимальным.
Предположим, что грузы и контейнер самолета являются параллелепи-
педами. Совместим начало координатных осей с точкой ∗x . Если ∗x не сов-
падает с центром контейнера, то полуоси контейнера не равны между собой.
Пусть 0≥kA , nk ,...,1= — полуоси контейнера, которые соответствуют
отрицательным осям координат, а 0≥kB , nk ,...,1= , положительным.
Грузы задаются своими центрами ix , mi ,...,1= , и полуосями ia , mi ,...,1= ,
т.е. },...,1,,...,1,||:{)( nkmiaxyRyxS k
i
k
i
k
i
n
iiai
==≤−∈= . В пространстве
грузы можно перемещать только параллельным сдвигом. Обозначим k
iξ ,
Рис. 4. Упаковка 10-ти разных параллелепипедов в заданный контейнер
Э.И. Ненахов, Л.А. Соболенко
ISSN 1681–6048 System Research & Information Technologies, 2009, № 3 102
2,1=i , nk ,...,1= , величины выхода грузов за границы контейнера по каж-
дой из сторон и введем в рассмотрение вектор α с компонентами, kα ,
nk ,...,1= , которые могут принимать значения 0 или 1.Тогда формально за-
дача об упаковке грузов в самолет сводится к следующей оптимизационной
задаче:
⎪
⎪
⎪
⎪
⎪
⎪
⎭
⎪
⎪
⎪
⎪
⎪
⎪
⎬
⎫
⎪
⎪
⎪
⎪
⎪
⎪
⎩
⎪
⎪
⎪
⎪
⎪
⎪
⎨
⎧
=<
≥+−−=
==+≤+
==−≥−
⎟
⎟
⎟
⎟
⎟
⎠
⎞
⎜
⎜
⎜
⎜
⎜
⎝
⎛
−++
∑
∑ ∑
∑
∑
=
= =
∗
=
=
,,..,1,,
,0))(|(|))(),((
,,...,1,,...,1,
,,...,1,,...,1,
,)(
min
1
2
1
1
2
1
1
1
2211
,
mjiji
aaxxfxSxS
minkBax
minkAax
x
m
xm
CCC
n
k
k
j
k
i
k
j
k
ijaia
kkk
i
k
i
kkkk
i
k
i
n
k
n
k
k
m
i
i
m
i
k
ii
kkkk
x
ji
k
ii
εε
ξ
ρ
ξ
ξα
ξξ
(16)
где C , k
iC , 2,1=i , nk ,...,1= — весовые коэффициенты. Первые две груп-
пы ограничений показывают, что грузы не должны выходить за границы
контейнера, а условия не пересечения грузов задаются с помощью функции
квазирасстояния ))(),((),( ySxSyx baεε ρρ = .
Алгоритм (6), (7) применим для любых nRx∈ . Поскольку грузы упа-
ковываются в самолет, то 3=n . Если начало координатной оси совместить
с проекцией ∗x на плоскость 21, xx , т.е. в (16) положить 01 === nnn αCA ,
то грузы будут укладываться на пол контейнера вокруг проекции центра
тяжести. Размерности задачи (16) определяются по формулам += nn 21
nm×+ , 2
1 2 mCnmm +×= .
В качестве примера рассмотрим задачу упаковки восьми грузов на пол
контейнера в самолет типа ИЛ-76. Задача имеет 30 неизвестных и 76 огра-
ничений. Пусть размеры контейнера в данной системе координат будут
91 =A ; 73,12 =A ; 03 =A ; 91 =B ; 73,12 =B ; 2,33 =B . Размеры грузов и
значения координат их центров в начальном положении указаны в табл. 6.
Координаты центра тяжести )6,1;0;0(=∗x , массы грузов im , mi ,...,1=
имеют значения 321 == mm , 2843 === mmm , 15 =m , 5,276 == mm . Ве-
совые коэффициенты принимают значения 03
1 =C , 1== k
iCC , 2,1, =ki .
Т а б л и ц а 6 . Размеры грузов и их центры в начальном положении
Номер
груза
1
0x 2
0x 3
0x 1a 2a 3a Номер
груза
1
0x 2
0x 3
0x 1a 2a 3a
1 –2 –15 –4 5 0,5 0,5 5 5 6 4,5 3 0,5 0,25
2 –6 –6 4 5 0,5 0,5 6 –6 5 –3 3 0,5 0,25
3 7 9 –5 4,5 0,5 0,25 7 –8 –4 –8 3 0,5 0,25
4 5 –5 –6 4,5 0,5 0,25 8 7 –4 6 2 0,5 0,25
Метод линеаризации и негладкая оптимизация
Системні дослідження та інформаційні технології, 2009, № 3 103
На рис. 5 дано графическое отображение положения грузов в начале
(слева) и в конце (справа) итерационного процесса (6). Видно, что сначала
все грузы лежат вне контейнера, а в конце — внутри. Полученные числен-
ные результаты также свидетельствуют об этом. В точках решения имеем
051,01
1 −=ξ ; 183,02
1 −=ξ ; 03
1 =ξ ; 934,11
2 −=ξ ; 117,02
2 −=ξ ; 130,23
2 −=ξ .
То, что 03
1 =ξ , означает, что грузы упакованы на пол контейнера. Значения
остальных k
iξ отрицательны, следовательно, все грузы находятся внутри
контейнера. Для нормального маневра самолета смещение центра тяжести
самолета ∗x , соответствующее оси 3x , не является столь существенным,
как смещения по осям 1x и 2x . В нашем случае смещение по координате 1x
равно 6107,0 −⋅ , по координате 2x — 2103,0 −⋅ , по 3x — 0,485. Следовате-
льно, упакованные грузы практически не изменили координат центра тяжес-
ти самолета по осям 21, xx . Координаты центров грузов в решении задачи
приведены в табл.7. Для получения решения с точностью 2102,0 −⋅≤kp ал-
горитму потребовалось выполнить 109 итераций.
Т а б л и ц а 7 . Координаты центров грузов в точках решения
Номер
груза
1
∗x 2
∗x 3
∗x Номер
груза
1
∗x 2
∗x 3
∗x
1 2,07 1,11 0,50 5 4,07 0,04 0,82
2 –3,95 0,05 0,50 6 4,07 0,02 0,25
3 2,53 –1,05 0,25 7 –5,95 1,13 0,25
4 –4,45 –1,05 0,78 8 5,07 –1,05 0,80
ВЫВОДЫ
1. На примерах задач выпуклого и обратно-выпуклого программирова-
ния показана возможность использования в негладкой оптимизации извест-
Рис. 5. Размещение 8-ми грузов в контейнер самолета
Э.И. Ненахов, Л.А. Соболенко
ISSN 1681–6048 System Research & Information Technologies, 2009, № 3 104
ного метода линеаризации, разработанного Б.Н. Пшеничным для решения
гладких оптимизационных задач.
2. Предложен пакет программ Packing для решения задач упаковки и
размещения различных объектов в конечномерном пространстве nR , разра-
ботанный на основе формализованных математических моделей задач упа-
ковки и модификации метода линеаризации.
3. Приведены расчеты конкретных задач упаковки и размещения объ-
ектов, которые демонстрируют эффективность работы описанной модифи-
кации метода линеаризации и разработанного на его основе пакета приклад-
ных программ Packing.
ЛИТЕРАТУРА
1. Пшеничный Б.Н. Метод линеаризации. — М.: Наука, 1983. — 136 с.
2. Пшеничный Б.Н., Ненахов Э.И., Кузьменко В.Н. Комбинированный метод ре-
шения общей задачи выпуклого программирования // Кибернетика и сис-
темный анализ. — 1998. — № 4. — С. 121–133.
3. Пшеничный Б.Н., Соболенко Л.А. Метод линеаризации для обратно-выпуклого
программирования // Кибернетика и системный анализ. — 1995. — № 6. —
С. 86–97.
4. Тот Л.Ф. Расположения на плоскости, на сфере и в пространстве. — М.: Физ-
матгиз, 1958. — 363 с.
5. Конвей Дж., Слоэн Н. Упаковка шаров, решетки и группы. — М.: Мир,
1990. — 1,2. — 791 с.
6. Стоян Ю.Г., Придатко Д.И. Упаковка различных круговых цилиндров в па-
раллелепипеде // Доп. НАН України. — 2004. — № 4. — С. 27–32.
7. Pinter J.D. Nonlinear optimization with GAMS/LGO // J. of Global Optimiza-
tion. — 2007. — 38, № 1. — P. 79–101.
8. Guanglu Zhou, Kim-Chuan Ton, Jie Sun. Efficient Algorithms for the Smallest En-
closing Ball Problem // Computational Optimization and Applications. —
2005. — 30, № 2. — P. 147–160.
9. Соболенко Л.А. Комплекс программ Packing для решения задач упаковки и
размещения объектов // Тези доп. 13-ї Міжнар. наук.-техн. конф. —Вінниця,
25–28 вересня 2006 р. — Вінниця, УНІВЕРСУМ. — 2006. — С. 362.
10. Пшеничный Б.Н., Данилин Ю.М. Численные методы в экстремальных зада-
чах. — М.: Наука, 1975. — 320 с.
11. Пшеничный Б.Н., Соболенко Л.А. Метод обратно-выпуклого программирования
и укладка параллелепипедов // Кибернетика и системный анализ. —
1996. — № 3. — С.16–26.
Поступила 08.02.2008
|
| id | journaliasakpiua-article-107843 |
| institution | System research and information technologies |
| keywords_txt_mv | keywords |
| language | Russian |
| last_indexed | 2025-07-17T10:22:30Z |
| publishDate | 2009 |
| publisher | The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" |
| record_format | ojs |
| resource_txt_mv | journaliasakpiua/2f/d49a12c945924047a8aac89bbd0a062f.pdf |
| spelling | journaliasakpiua-article-1078432018-04-06T12:33:14Z Linearization method and unsmooth optimization Метод линеаризации и негладкая оптимизация Метод лінеаризації та негладка оптимізація Nenakhov, E. I. Sobolenko, L. A. Two modifications of nonstandard application of linearization method to solve unsmooth optimization problems are considered. On the basis of its modification for solve problems of back-convex programming, there has been developed an applied programs packet called Packing. The effectiveness of the packet and its modifications is illustrated by examples of different packing and arrangement of the objects. Рассматриваются две модификации нестандартного применения метода линеаризации к решению негладких оптимизационных задач. На основе модификации для задач обратно-выпуклого программирования разработан пакет прикладных программ Packing. Показана эффективность работы пакета и этой модификации на примерах различных задач упаковки и размещения объектов. Розглядаються дві модифікації нестандартного застосування методу лінеаризації до розв’язування негладких оптимізаційних задач. На основі модифікації для задач обернено-опуклого програмування розроблено пакет прикладних програм Packing. Показано ефективність роботи пакета і цієї модифікації на прикладах різних задач пакування та розміщення об’єктів. The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" 2009-09-25 Article Article application/pdf https://journal.iasa.kpi.ua/article/view/107843 System research and information technologies; No. 3 (2009); 90-104 Системные исследования и информационные технологии; № 3 (2009); 90-104 Системні дослідження та інформаційні технології; № 3 (2009); 90-104 2308-8893 1681-6048 ru https://journal.iasa.kpi.ua/article/view/107843/102789 Copyright (c) 2021 System research and information technologies |
| spellingShingle | Nenakhov, E. I. Sobolenko, L. A. Метод лінеаризації та негладка оптимізація |
| title | Метод лінеаризації та негладка оптимізація |
| title_alt | Linearization method and unsmooth optimization Метод линеаризации и негладкая оптимизация |
| title_full | Метод лінеаризації та негладка оптимізація |
| title_fullStr | Метод лінеаризації та негладка оптимізація |
| title_full_unstemmed | Метод лінеаризації та негладка оптимізація |
| title_short | Метод лінеаризації та негладка оптимізація |
| title_sort | метод лінеаризації та негладка оптимізація |
| url | https://journal.iasa.kpi.ua/article/view/107843 |
| work_keys_str_mv | AT nenakhovei linearizationmethodandunsmoothoptimization AT sobolenkola linearizationmethodandunsmoothoptimization AT nenakhovei metodlinearizaciiinegladkaâoptimizaciâ AT sobolenkola metodlinearizaciiinegladkaâoptimizaciâ AT nenakhovei metodlínearizacíítanegladkaoptimízacíâ AT sobolenkola metodlínearizacíítanegladkaoptimízacíâ |