Математическая модель и метод решения задачи упаковки максимального числа равных кругов в невыпуклую область с зонами запрета

Розглядається оптимiзацiйна задача упакування максимальної кiлькостi рiвних кiл у багатозв’язну область, границя якої складається з дуг кiл та вiдрiзкiв прямих. Побудовано математичну модель задачi. На пiдставi властивостей математичної моделi запропоновано метод розв’язання задачi. Метод складаєтьс...

Full description

Saved in:

Bibliographic Details
Date:	2009
Main Authors:	Стоян, Ю.Г., Чугай, А.М.
Format:	Article
Language:	Russian
Published:	Видавничий дім "Академперіодика" НАН України 2009
Subjects:	Інформатика та кібернетика
Online Access:	https://nasplib.isofts.kiev.ua/handle/123456789/18846
Tags:	Add Tag No Tags, Be the first to tag this record!
Journal Title:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Cite this:	Математическая модель и метод решения задачи упаковки максимального числа равных кругов в невыпуклую область с зонами запрета / Ю. Г. Стоян, А.М. Чугай // Доп. НАН України. — 2009. — № 10. — С. 45-52. — Бібліогр.: 12 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	nasplib_isofts_kiev_ua-123456789-18846
record_format	dspace
spelling	Стоян, Ю.Г. Чугай, А.М. 2011-04-11T13:58:52Z 2011-04-11T13:58:52Z 2009 Математическая модель и метод решения задачи упаковки максимального числа равных кругов в невыпуклую область с зонами запрета / Ю. Г. Стоян, А.М. Чугай // Доп. НАН України. — 2009. — № 10. — С. 45-52. — Бібліогр.: 12 назв. — рос. 1025-6415 https://nasplib.isofts.kiev.ua/handle/123456789/18846 519.85 Розглядається оптимiзацiйна задача упакування максимальної кiлькостi рiвних кiл у багатозв’язну область, границя якої складається з дуг кiл та вiдрiзкiв прямих. Побудовано математичну модель задачi. На пiдставi властивостей математичної моделi запропоновано метод розв’язання задачi. Метод складається з комбiнацiї алгоритму генерацiї початкових точок, модифiкацiї методу можливих напрямкiв та модифiкацiї методу звужувальних околiв для пошуку наближення до глобального максимуму. Наводиться чисельний приклад. The paper deals with the optimization packing problem of equal circles into a multiply connected region, whose frontier consists of arcs of circles and segments of straight lines. A mathematical model of the problem is constructed. On the ground of the characteristics of the mathematical model, a solution method is offered. The method consists of a combination of an algorithm generating starting points, a modification of the method of feasible directions to search for local maxima, and a modification of the decremental neighborhood method to search for an approximation to the global maximum. A numerical example is given. ru Видавничий дім "Академперіодика" НАН України Інформатика та кібернетика Математическая модель и метод решения задачи упаковки максимального числа равных кругов в невыпуклую область с зонами запрета A mathematical model and a solution method of the packing problem of a maximal number of equal circles into a non-convex region with prohibited areas Article published earlier
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
title	Математическая модель и метод решения задачи упаковки максимального числа равных кругов в невыпуклую область с зонами запрета
spellingShingle	Математическая модель и метод решения задачи упаковки максимального числа равных кругов в невыпуклую область с зонами запрета Стоян, Ю.Г. Чугай, А.М. Інформатика та кібернетика
title_short	Математическая модель и метод решения задачи упаковки максимального числа равных кругов в невыпуклую область с зонами запрета
title_full	Математическая модель и метод решения задачи упаковки максимального числа равных кругов в невыпуклую область с зонами запрета
title_fullStr	Математическая модель и метод решения задачи упаковки максимального числа равных кругов в невыпуклую область с зонами запрета
title_full_unstemmed	Математическая модель и метод решения задачи упаковки максимального числа равных кругов в невыпуклую область с зонами запрета
title_sort	математическая модель и метод решения задачи упаковки максимального числа равных кругов в невыпуклую область с зонами запрета
author	Стоян, Ю.Г. Чугай, А.М.
author_facet	Стоян, Ю.Г. Чугай, А.М.
topic	Інформатика та кібернетика
topic_facet	Інформатика та кібернетика
publishDate	2009
language	Russian
publisher	Видавничий дім "Академперіодика" НАН України
format	Article
title_alt	A mathematical model and a solution method of the packing problem of a maximal number of equal circles into a non-convex region with prohibited areas
description	Розглядається оптимiзацiйна задача упакування максимальної кiлькостi рiвних кiл у багатозв’язну область, границя якої складається з дуг кiл та вiдрiзкiв прямих. Побудовано математичну модель задачi. На пiдставi властивостей математичної моделi запропоновано метод розв’язання задачi. Метод складається з комбiнацiї алгоритму генерацiї початкових точок, модифiкацiї методу можливих напрямкiв та модифiкацiї методу звужувальних околiв для пошуку наближення до глобального максимуму. Наводиться чисельний приклад. The paper deals with the optimization packing problem of equal circles into a multiply connected region, whose frontier consists of arcs of circles and segments of straight lines. A mathematical model of the problem is constructed. On the ground of the characteristics of the mathematical model, a solution method is offered. The method consists of a combination of an algorithm generating starting points, a modification of the method of feasible directions to search for local maxima, and a modification of the decremental neighborhood method to search for an approximation to the global maximum. A numerical example is given.
issn	1025-6415
url	https://nasplib.isofts.kiev.ua/handle/123456789/18846
citation_txt	Математическая модель и метод решения задачи упаковки максимального числа равных кругов в невыпуклую область с зонами запрета / Ю. Г. Стоян, А.М. Чугай // Доп. НАН України. — 2009. — № 10. — С. 45-52. — Бібліогр.: 12 назв. — рос.
work_keys_str_mv	AT stoânûg matematičeskaâmodelʹimetodrešeniâzadačiupakovkimaksimalʹnogočislaravnyhkrugovvnevypukluûoblastʹszonamizapreta AT čugaiam matematičeskaâmodelʹimetodrešeniâzadačiupakovkimaksimalʹnogočislaravnyhkrugovvnevypukluûoblastʹszonamizapreta AT stoânûg amathematicalmodelandasolutionmethodofthepackingproblemofamaximalnumberofequalcirclesintoanonconvexregionwithprohibitedareas AT čugaiam amathematicalmodelandasolutionmethodofthepackingproblemofamaximalnumberofequalcirclesintoanonconvexregionwithprohibitedareas
first_indexed	2025-11-27T00:52:35Z
last_indexed	2025-11-27T00:52:35Z
_version_	1850789584149938176
fulltext	УДК 519.85 © 2009 Член-корреспондент НАН Украины Ю.Г. Стоян, А. М. Чугай Математическая модель и метод решения задачи упаковки максимального числа равных кругов в невыпуклую область с зонами запрета Розглядається оптимiзацiйна задача упакування максимальної кiлькостi рiвних кiл у ба- гатозв’язну область, границя якої складається з дуг кiл та вiдрiзкiв прямих. Побудовано математичну модель задачi. На пiдставi властивостей математичної моделi запропо- новано метод розв’язання задачi. Метод складається з комбiнацiї алгоритму генерацiї початкових точок, модифiкацiї методу можливих напрямкiв та модифiкацiї методу звужувальних околiв для пошуку наближення до глобального максимуму. Наводиться чисельний приклад. Задача размещения одинаковых кругов имеет важное теоретическое и прикладное значение. Рассмотрим постановку рассматриваемой задачи. Пусть имеются конгруэнтные круги Ci, i ∈ I = {1, 2, . . . , N}, радиусом r с центрами ui = (xi, yi) и замкнутое многосвязное множе- ство P , заданное следующим образом: P = cl ( P0\ β⋃ l=1 Al ) ⊂ R 2, Al = ( gl⋃ g=1 Clg )⋃( hl⋃ h=1 Mlh ) , intAl 6= ∅, l ∈ B = {1, 2, . . . , β}, Clg — круги с центрами (x0lg, y 0 lg) и радиусами ρ0lg, g ∈ ∈ Gl = {1, 2, . . . , gl}, Mlh — выпуклые многоугольники, h ∈ Hl = {1, 2, . . . , hl}. Граница P0 формируется отрезками прямых и дугами окружностей. Задача. Необходимо найти такой вектор u = (u1, u2, . . . , un) ∈ R 2n, который обеспечит размещение в области P максимального числа n 6 N кругов Ci, i ∈ I. В отличие от работы [1], которая также посвящена задаче упаковки одинаковых кру- гов, в данной работе рассматривается многосвязная область, граница которой формируется отрезками прямых и дугами окружностей. Кроме того, предлагается другая математиче- ская модель и разработан более эффективный метод решения задачи. Прежде чем построить математическую модель поставленной задачи, построим множе- ство G = cl(R2 \ P0) = ( j1⋃ j=1 Q1j ) ⋃ ( j2⋃ j=1 Q2j ) ⋃ ( j3⋃ j=1 Q3j ) ⋃ ( j4⋃ j=1 Q4j ) , где Q1j = {(x, y) ∈ R 2 : χ1j(x, y) > 0}, j ∈ J1 = {1, 2, . . . , j1}, χ1j(x, y) = a1jx+ b1jy + c1j ; Q2j = {(x, y) ∈ R 2 : χ2jl(x, y) > 0, l = 1, 2}, j ∈ J2 = {1, 2, . . . , j2}, χ2jl(x, y) = a2jlx+ b2jly + c2jl; Q3j = {(x, y) ∈ R 2 : ω ⌢ 3j(x, y) > 0}, j ∈ J3 = {1, 2, . . . , j3}, ω ⌢ 3j(x, y) = r ⌢2 j − (x− x ⌢ j) 2 − (y − y ⌢ j) 2; ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2009, №10 45 Рис. 1. Представление множества G Q4j = {(x, y) ∈ R 2 : χ4jl(x, y) > 0, ω ⌣ 4j(x, y) > 0, l = 1, 2}, j ∈ J4 = {1, 2, . . . , j4}, χ4jl(x, y) = a4jlx+ b4jly + c4jl, ω ⌣ 4j(x, y) = (x− x ⌣ j) 2 + (y − y ⌣ j) 2 − r ⌣2 j , при этом ρ(A,B) > 2r, ρ(A,B) — расстояние между точками A и B (рис. 1), r ⌣ > r. Например, для области P0, представленной на рис. 1, множество G имеет вид G = ( 2⋃ j=1 Q1j ) ⋃ ( 2⋃ j=1 Q2j ) ⋃ ( 2⋃ j=1 Q3j ) ⋃ ( 1⋃ j=1 Q4j ) . Решение поставленной задачи сводится к решению следующей последовательности за- дач: Fn(X n∗) = max Xn∈Wn Fn(X n), n ∈ In = {1, 2, . . . , τ 6 N}, (1) Wn = {Xn ∈ R 3n : Φij(ui, uj , ri, rj) > 0, i, j ∈ In, i < j,Φi(ui, ri) > 0, r − ri > 0, ri > 0, i ∈ In}, (2) где Fn(X n) = n∑ i=1 ri, Xn = (un, vn), un = (u1, u2, . . . , un) ∈ R 2n, vn = (r1, r2, . . . , rn) ∈ R n, ri — радиус Ci, Φij(ui, uj , ri, rj) = (xi − xj) 2 + (yi − yj) 2 − (ri + rj) 2 > 0, Φi(ui, ri) = min{ΦCC ilg (ui, ri),Φ CM ilh (ui, ri),Φ CG i (ui, ri), l ∈ B, g ∈ Gl, h ∈ Hl}, ΦCC ilg (ui, ri) = (xi − x 0 lg) 2 + (yi − y 0 lg) 2 − (ri + ρ0lg) 2, ΦCM ilh (ui, ri) = max k=1,2,...,mlh {max{min{ψilhk(ui, ri), ωilhk(ui, ri)}, χ ∗ ilhk(ui, ri)}}, ΦCG i (ui, ri) = min{ΦCQ1 ij (ui, ri), j ∈ J1,Φ CQ2 ij (ui, ri), j ∈ J2,Φ CQ3 ij (ui, ri), j ∈ J3, ΦCQ4 ij (ui, ri), j ∈ J4}, ΦCQ1 ij (ui, ri) = χ∗ i1j(ui, ri) = −χ1j(ui)− ri, 46 ISSN 1025-6415 Reports of the National Academy of Sciences of Ukraine, 2009, №10 ΦCQ2 ij (ui, ri) = max{min{ψij(ui, ri), ωij(ui, ri)}, χ ∗ i2j1(ui, ri), χ ∗ i2j2(ui, ri)}, ΦCQ3 ij (ui, ri) = (xi − x ⌢ j) 2 + (yi − y ⌢ j) 2 − (ri + r ⌢ j) 2, ΦCQ4 ij (ui, ri) = max{φij1(ui, ri), φij2(ui, ri), φij3(ui, ri), ωij3(ui, ri), χ ∗ i4j1(ui, ri), χ∗ i4j2(ui, ri)}, φij1(ui, ri) = min{ωij1(ui, ri), ωij2(ui, ri), ψij1(ui, ri), ψij2(ui, ri), ψij3(ui, ri)}, φij2(ui, ri) = min{ωij1(ui, ri), ψij4(ui, ri)}, φij3(ui, ri) = min{ωij2(ui, ri), ψij5(ui, ri)}, ωij1(ui, ri) = (xi − xj1) 2 + (yi − yj1) 2 − r2i , ωij2(ui, ri) = (xi − xj2) 2 + (yi − yj2) 2 − r2i , ωij3(ui, ri) = ( r ⌣ j − ri) 2 − (xi − x ⌣ j) 2 − (yi − yj) 2, ψij1(ui, ri) = aj1xi + bj1yi + cj1, a1j = yj4 − yj3, bj1 = −(xj4 − xj3), c1j = −(a1jxj3 + b1jyj3), ψij2(ui, ri) = aj2xi + bj2yi + cj2, aj2 = yj6 − yj5, bj2 = −(xj6 − xj5), cj2 = −(aj2xj5 + bj2yj5), ψij3(ui, ri) = aj3xi + bj3yi + cj3, aj3 = yj5 − yj4, bj3 = −(xj5 − xj4), cj3 = −(aj3x5 + bj3y5), ψij4(ui, ri) = aj4xi + bj4yi + cj4, aj4 = yj3 − yj7, bj4 = −(xj3 − xj7), cj4 = −(aj4xj3 + bj4yj3), ψij5(ui, ri) = aj5xi + bj5yi + cj5, aj5 = yj8 − yj6, bj5 = −(xj8 − xj6), cj5 = −(aj5xj6 + bj5yj6), χ∗ i4j1(ui, ri) = −χ4j1(ui)− ri, χ∗ i4j2(ui, ri) = −χ4j2(ui)− ri, (xj1, yj1), (xj2, yj2), (xj3, yj3), (xj4, yj4), (xj5, yj5), (xj6, yj6), (xj7, yj7) и (xj8, yj8) — коор- динаты точек A, B, D, E, F , G, M и N соответственно (рис. 2), Φi(ui, ri), ΦCG i (ui, ri), ΦCQ1 ij (ui, ri), Φ CQ2 ij (ui, ri), Φ CQ3 ij (ui, ri), Φ CQ4 ij (ui, ri), Φ CC ilg (ui, ri), Φ CM ilh (ui, ri) — Ф-функции [2] для Ci и cl(R2 \ P ), Ci и G [3], Ci и Q1j; Ci и Q2j [4]; Ci и Q3j ; Ci и Q4j ; Ci и Clg; Ci и Mlh [4] соответственно. Если Fn(X n∗) < nr и Fn−1(X (n−1)∗) = Fn−1(u (n−1)∗, v(n−1)∗) = (n − 1)r, где v(n−1)∗ = = (r, r, . . . , r), то решение задачи (1)–(2) достигается в точке u∗ = u(n−1)∗. Рассматриваемая задача относится к классу NP-трудных задач [4]. Для построения начальных точек область P покрывается многоугольной решеткой, у ко- торой основной параллелограмм является квадратом S с длиной сторон, равной r. Пусть k > n — количество квадратов, таких, что Si = { (x, y) ∈ R 2 : ai − 1 2 r 6 x 6 ai + 1 2 r, bi − 1 2 r 6 y 6 bi + 1 2 r } ⊂ P, где (ai, bi) — координаты центра Si, i ∈ K = (1, 2, . . . , k). Каждому Si поставим в со- ответствие номер i, i ∈ K. Сформируем вектор pi = (pi1 , pi2 , . . . , pin , . . . , pik) ∈ R 2k, где ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2009, №10 47 Рис. 2. 0-Уровень ΦCQ4 ij (ui) pij = (aij , bij ). Для того чтобы получить точку Xni ∈ Wn, зададим vni = (r/2, r/2, . . . , r/2) и сформируем вектор uni = (ui1, u i 2, . . . , u i n) ∈ R 2n, приравняв компоненты uni первым n компонентам pi = (pi1 , pi2 , . . . , pin︸︷︷︸ n , . . . , pik), т. е. uni = ((ai1 , bi1), (ai2 , bi2), . . . , (ain , bin)) ∈ R 2n. Таким образом, взяв (aij , bij ) в качестве координат центра Cj , мы получим размещение Cj радиуса r/2, j ∈ In, в P без пересечений. Очевидно, что число векторов pi ∈ R 2k равно k!, т. е. все pi формируют множество Π ⊂ R 2k перестановок без повторений. Множеству Π ⊂ R 2k соответствует множество T ⊂ ⊂ R 3n начальных точек и, следовательно, множество L ⊂ R 3n локальных максимумов за- дачи (1)–(2). Поэтому перебор локальных максимумов на множестве L может быть сведен к перебору точек на множестве Π ⊂ R 2k. Для того чтобы осуществить “направленный” пе- ребор на множестве Π ⊂ R 2k, используется следующая модификация метода сужающихся окрестностей (МСО) [6]. Этап настройки МСО. На данном этапе осуществляется поиск перспективных центров для следующего итерационного этапа. Шаг 1. Генерируется случайная выборка Π0 ⊂ Π, card(Π0) = λ, строится соответству- ющее множество T0 = {Xnj , j ∈ Jλ = (1, 2, . . . , λ)} ⊂ T начальных точек и формируется соответствующее множество L0 = {Xnj∗, j ∈ Jλ} ⊂ L локальных максимумов. Шаг 2. Выбираются точки Xnjl∗ ∈ L0, l ∈ Ω = {1, 2, . . . , ω}, такие, что Fn(X nj1∗) > > Fn(X nj2∗) > · · · > Fn(X njω∗) > max{Fn(X n∗) : Xn∗ ∈ L0 \ {X njl∗, l ∈ Ω}}. Таким образом, каждому локальному максимуму Xnjl∗ соответствует точка pjl ∈ Π0, l ∈ Ω. Точки pjl ∈ Π0 принимаются в качестве центров окрестностей N0l ⊂ Π0, l ∈ Ω, радиуса ρ0 < β∗, где β∗ — оценка диаметра множества Π. Расстояние между точками pi и pj вычисляется согласно ев- клидовой метрике. Для того чтобы определить перспективные центры, генерируются слу- чайные выборки S0l ⊂ N0l, l ∈ Ω, card(S0l) = λ. Значение ρ0 = 0,25β∗ позволяет определить “поведение” Fn вблизи локальных максимумов, соответствующих центрам pjl окрестностей N0l ⊂ Π0, l ∈ Ω. Шаг 3. Формируются множества T0l ⊂ T и L0l ⊂ L, которые соответствуют S0l ⊂ N0l, l ∈ Ω. 48 ISSN 1025-6415 Reports of the National Academy of Sciences of Ukraine, 2009, №10 Шаг 4. Для каждого L0l вычисляется математическое ожидание m0l и среднеквадрати- ческое отклонение σ0l, l ∈ Ω, значений Fn. Шаг 5. Определяется точка p̃0, которая соответствует локальному максимуму X̃n0∗, такому, что Fn(X̃ n0∗) = max { Fn(X n∗),Xn∗ ∈ ω⋃ l=1 L0l } . Итерационный этап МСО. Итерационный процесс начинается со счетчика итераций, равного k = 1. Будем считать, что после k-итерации сформировано множество Lki, вычисле- ны mki, σki, i = 1, 2, 3, и получена точка p̃k, которая соответствует локальному максимуму X̃nk∗, такому, что Fn(X̃ nk∗) = max { Fn(X n∗),Xn∗ ∈ 3⋃ i=1 Lki } . Шаг 1. Выбираются центры cki окрестностей Nki, i = 1, 2, 3, следующим образом: 1) ck1 = { p̃k−1, если Fn(X̃ n(k−1)∗) > Fn(X̃ n(k−2)∗), p̃k−2, если Fn(X̃ n(k−1)∗) 6 Fn(X̃ n(k−2)∗), если k = 1, то ck1 = p0; 2) ck2 =    c(k−1)1, если ck1 = p̃k−1 и X̃n(k−1)∗ ∈ L(k−1)1, c(k−1)2, если или ck1 = p̃k−1 и X̃n(k−1)∗ ∈ L(k−2)2, или ck1 = p̃k−2, c(k−1)3, если ck1 = p̃k−1 и X̃nk∗ ∈ L(k−1)3, если k = 1, то ck2 = pjl , где pjl — центр окрестности N0l, в которой получена точка p0; 3) ck3 = c(k−1)i, где c(k−1)i — центр окрестности N(k−1)i, в которой получено значение max{m(k−1)i + θσ(k−1)i, i = 1, 2, 3}, 0 < θ 6 3, если k = 1, то i = 1, 2, . . . , ω (данный центр выбирается из гипотезы о том, что значения локальных максимумов Fn распределены по нормальному закону). Шаг 2. Определяются радиусы ρki новых окрестностей Nki, i = 1, 2, 3, следующим об- разом: ρki =    µρ(k−1)i, если m(k−1)i + θσ(k−1)i 6 f∗k−1, 1 µ ρ(k−1)i 6 ρk, если m(k−1)i + θσ(k−1)i > f∗k−1, где f∗k−1 = { Fn(X̃ n(k−1)∗), если Fn(X̃ n(k−1)∗) > Fn(X̃ n(k−2)∗), Fn(X̃ n(k−2)∗), если Fn(X̃ n(k−1)∗) 6 Fn(X̃ n(k−2)∗), ρk =    µ1ρk−1, если Fn(X̃ n(k−1)∗) 6 Fn(X̃ n(k−2)∗) 6 Fn(X̃ n(k−3)∗), 1 µ1 ρk−1 6 β∗, если Fn(X̃ n(k−1)∗) > Fn(X̃ n(k−2)∗), µ = 0,8 — коэффициент уменьшения (увеличения) радиуса окрестностей на каждом этапе МСО, µ1 = 0,6 — коэффициент, который гарантирует быстрое уменьшение радиуса окре- стностей в случае отсутствия улучшений X̃nk∗. Если k = 1, то ρk = ρk1 = ρk2 = ρk3 = β∗. Шаг 3. Генерируются случайные выборки Ski ⊂ Nki, строятся соответствующие множе- ства Tki ⊂ T, Lki ⊂ L, вычисляются mki, σki, i = 1, 2, 3, и определяется p̃k. Шаг 4. Проверяются условия критерия остановки. Если число одинаковых значений Fn в каждой Lki, i = 1, 2, 3, больше чем 0,6λ, то процесс поиска новых перестановок закан- чивается (следует отметить, что если радиус окрестностей приближается к минимальному, ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2009, №10 49 то количество локальных максимумов с равными значениями функции цели значительно увеличивается). Шаг 5. Увеличивается счетчик итераций: k ← k + 1. Точки вида Xni = (uni, vni) ∈ R 3n берутся в качестве начальных точек для вычисления локальных максимумов задачи (1)–(2). Вычисление локального максимума задачи (1)–(2) может быть сведено к решению последовательности задач нелинейного программирования вида Fn(X nj∗) = max Xn∈Wnij Fn(X n), j = 1, 2, . . . , m≪ η, (3) где Wnij ⊂ Wn, Wn = η⋃ i=1 Wni. Для решения задачи (3) используется модификация метода возможных направлений [7] вместе со стратегией ε-активных неравенств [8, 9]. Для отыскания локального максимума используется стандартный итерационный про- цесс Xn(k+1) = Xnk + tZk, k = 1, 2, . . . , ζ, где Zk ∈ R 3n — решение следующей задачи: max (αk ,Zk)∈Gk αk, (4) Gk = { (∇Fn(X nk), Zk) > αk, (∇Ψkj (X nk), Zk) > wkj , j = 1, 2, . . . , ςk(εk), −1 6 zki 6 1, i = 1, 2, . . . , 3n } , (5) где Ψkj (X nk) — левая часть ε-активных неравенств из системы, которая выделена из сис- темы (2) в точке Xnk и описывает текущую подобласть Wnij ; wkj = αk, если Ψkj(X nk) — вогнутая функция, иначе wkj = 0. Задача (4)–(5) решается методом внутренней точки [10]. Переход от одной задачи типа (3) к другой осуществляется следующим образом. Пусть Xn1 ∈ Wn — начальная точка. Тогда из системы (2) выбирается система, которая опре- деляет подобласть Wni1 ⊂ Wn, такую, что Xn1 ∈ Wni1 . Используя точку Xn1 в качестве начальной точки, решаем задачу Fn(X n1∗) = max Xn∈Wni1 Fn(X n). Полученная точка Xn1∗ может быть локальным максимумом либо относительно всей области Wn, либо только относительно подобласти Wni1 . Для того чтобы определить, явля- ется ли Xn1∗ локальным максимумом относительно Wn, необходимо исследовать все Wnij с Xn1∗ ∈ Wnij , j ∈ {1, 2, . . . , η}. Для этой цели из системы (2) выбираются все ε-активные неравенства в точке Xn1∗ и решается задача вида (4)–(5). В результате, если α > 0, то Xn1∗ не является локальным максимумом задачи (1)–(2) и тогда вычисляется новая точка Xn2 = (Xn1∗ + tZ) ∈ Wn, в которой Fn(X n1∗) < Fn(X n2). После этого формируется новая система неравенств, которая определяет подобласть Wni2 ⊂ Wn, такую, что Xn2 ∈ Wni2 . Используя Xn2 в качестве начальной точки, решаем задачу Fn(X n2∗) = max Xn∈Wni2 Fn(X n). Описанный процесс продолжается до тех пор, пока не будет получен локальный макси- мум задачи (1)–(2). 50 ISSN 1025-6415 Reports of the National Academy of Sciences of Ukraine, 2009, №10 Рис. 3. Заданная невыпуклая область с зоной запрета Рис. 4. Результат упаковки кругов, r = 1,5 Численный пример. Пусть даны равные круги и невыпуклая область P с одной зоной запрета (рис. 3). Вершины P0 (см. рис. 3) имеют такие координаты: A(10; 60), B(17,6; 75,19), C(28,15; 77,41), D(30; 70), E(60; 80), F (62,88; 70), G(80,26; 39,84), H(62,34; 30,95), I(45; 35), J(28; 25). Граница P0 формируется отрезками AB, CD, DE, EF , HI, IJ , JA прямых и следующими дугами: BC окружности радиусом 15 с центром K(20; 90), FG окружно- сти радиусом 20 с центром M(63; 50) и GH окружности с радиусом 13 и центром L(75; 28) (см. рис. 3). Зона запрета A1 задана объединением кругов радиусом 4 с центром O(45; 55) и треугольниками ONQ и OTS, заданными координатами вершин O(45; 55), N(50; 50), Q(40; 50) и O(45; 55), T (50; 60), S(40; 60) соответственно (рис. 3). На рис. 4, а показана упаковка кругов при r = 1,5, соответствующая точке u∗ = u290∗, а на рис. 4, б — упаковка кругов, соответствующая лучшему локальному максимуму X291∗ задачи (1)–(2). Радиусы затемненных кругов на рис. 4, б не равны 1,5. Таким образом, анализ исследований, посвященных задачам упаковки одинаковых кру- гов, показал, что большинство авторов в качестве области размещения рассматривают в основном области правильной формы, т. е. такие фигуры как квадрат, прямоугольник, тре- угольник и круг. Ни в одной из известных нам работ в качестве области размещения не рас- сматривается невыпуклая область с зонами запрета, граница которой образована отрезками прямых и дугами окружностей. Вычислительные эксперименты показали, что построенная математическая модель и предложенный метод решения позволяют получать результаты ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2009, №10 51 высокого качества. Сравнение полученных результатов с мировыми аналогами говорит об эффективности предложенного подхода. Следует отметить, что, используя разработанный подход, мы получили многие результаты, которые в мировой литературе приводятся как эталонные в задачах упаковки одинаковых кругов в квадрат и прямоугольник [11]. При этом, нам удалось улучшить результаты упаковок в трех задачах, приведенных в [12]. 1. Стоян Ю.Г., Чугай А.М. Оптимизация упаковки одинаковых кругов в многосвязную область // Доп. НАН України. – 2004. – № 12. – С. 64–68. 2. Stoyan Yu.G. Φ-function and its basic properties // Там само. – 2001. – No 8. – С. 112–117. 3. Stoyan Y., Scheithauer G., Gil M., Romanova T. Φ-function for complex 2D objects // 4OR Quarterly J. of the Belgian, French and Italian Operat. Research Societies. – 2004. – 2 (1). – P. 69–84. 4. Stoyan Y., Terno J., Scheithauer G. et al. Φ-function for 2D primary objects // Studia Informatica. – 2002. – 2 (1). – P. 1–32. 5. Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. – Москва: Мир, 1985. – 512 с. 6. Стоян Ю.Г., Соколовский В. З. Решение некоторых многоэкстремальных задач методом сужающи- хся окрестностей. – Киев: Наук. думка, 1980. – 208 с. 7. Зойтендейк Г. Методы возможных направлений. – Москва: Изд-во иностр. лит., 1963. – 176 с. 8. Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. – Москва: Мир, 1985. – 509 с. 9. Stoyan Yu., Chugay A. Packing cylinders and rectangular parallelepipeds with distances between them into a given region // Europ. J. of Operat. Research. – 2009. – 197. – P. 446–455. 10. Gondzio J. HOPDM (version 2.12) – A Fast LP Solver Based on a Primal-Dual Interior Point Method // Ibid. – 1995. – 85 (1). – P. 221–225. 11. Specht E., http://www.packomania.com. 12. Birgin E.G., Martinez J.M., Ronconi D.P. Optimizing the packing of cylinders into a rectangular contai- ner // Europ. J. of Operat. Research. – 2005. – 160 (1). – P. 19–33. Поступило в редакцию 17.04.2009Институт проблем машиностроения им. А.Н. Подгорного НАН Украины, Харьков Corresponding Member of the NAS of Ukraine Yu.G. Stoyan, A. M. Chugay A mathematical model and a solution method of the packing problem of a maximal number of equal circles into a non-convex region with prohibited areas The paper deals with the optimization packing problem of equal circles into a multiply connected region, whose frontier consists of arcs of circles and segments of straight lines. A mathematical model of the problem is constructed. On the ground of the characteristics of the mathematical model, a solution method is offered. The method consists of a combination of an algorithm generating starting points, a modification of the method of feasible directions to search for local maxima, and a modification of the decremental neighborhood method to search for an approximation to the global maximum. A numerical example is given. 52 ISSN 1025-6415 Reports of the National Academy of Sciences of Ukraine, 2009, №10

Математическая модель и метод решения задачи упаковки максимального числа равных кругов в невыпуклую область с зонами запрета

Institution

Similar Items