Модификация метода возможных направлений для задачи оптимизации размещения объектов специального вида
Рассмотрена задача оптимизации размещения объектов в выпуклой области, каждый из которых может быть разбит на взаимно-ориентированные прямоугольники. Разработана модификация метода возможных направлений и метод направленного перехода. Для оценки эффективности методов приведены результаты численых эк...
Збережено в:
| Опубліковано в: : | Электронное моделирование |
|---|---|
| Дата: | 2007 |
| Автори: | , |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України
2007
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/101666 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Модификация метода возможных направлений для задачи оптимизации размещения объектов специального вида / С.И. Яремчук, Ю.А. Шаповалов // Электронное моделирование. — 2007. — Т. 29, № 2. — С. 29-38. — Бібліогр.: 8 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-101666 |
|---|---|
| record_format |
dspace |
| spelling |
Яремчук, С.И. Шаповалов, Ю.А. 2016-06-06T15:46:21Z 2016-06-06T15:46:21Z 2007 Модификация метода возможных направлений для задачи оптимизации размещения объектов специального вида / С.И. Яремчук, Ю.А. Шаповалов // Электронное моделирование. — 2007. — Т. 29, № 2. — С. 29-38. — Бібліогр.: 8 назв. — рос. 0204-3572 https://nasplib.isofts.kiev.ua/handle/123456789/101666 519.67 Рассмотрена задача оптимизации размещения объектов в выпуклой области, каждый из которых может быть разбит на взаимно-ориентированные прямоугольники. Разработана модификация метода возможных направлений и метод направленного перехода. Для оценки эффективности методов приведены результаты численых экспериментов. Розглянуто задачу оптимізації розміщення об’єктів у опуклій області. Кожен з об’єктів можна розкласти на взаємо-орієнтовані прямокутники. Розроблено модифікацію метода можливих напрямків та метод спрямованого переходу. Для оцінки ефективності методів наведено результати чисельних експериментів. A problem of the object arrangement optimization in convex domain is considered. Here each of them may be divided in mutually oriented rectangles. A modification of the possible directions method and the method of directed transition are developed. The results of numerical experiments are presented for estimation of the method efficience. ru Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України Электронное моделирование Математические методы и модели Модификация метода возможных направлений для задачи оптимизации размещения объектов специального вида Modification of Possible Direction Method for the Problem of Arrangement Optimization of Objects of Special Kind 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 |
2007 |
| language |
Russian |
| container_title |
Электронное моделирование |
| publisher |
Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України |
| format |
Article |
| title_alt |
Modification of Possible Direction Method for the Problem of Arrangement Optimization of Objects of Special Kind |
| description |
Рассмотрена задача оптимизации размещения объектов в выпуклой области, каждый из которых может быть разбит на взаимно-ориентированные прямоугольники. Разработана модификация метода возможных направлений и метод направленного перехода. Для оценки эффективности методов приведены результаты численых экспериментов.
Розглянуто задачу оптимізації розміщення об’єктів у опуклій області. Кожен з об’єктів можна розкласти на взаємо-орієнтовані прямокутники. Розроблено модифікацію метода можливих напрямків та метод спрямованого переходу. Для оцінки ефективності методів наведено результати чисельних експериментів.
A problem of the object arrangement optimization in convex domain is considered. Here each of them may be divided in mutually oriented rectangles. A modification of the possible directions method and the method of directed transition are developed. The results of numerical experiments are presented for estimation of the method efficience.
|
| issn |
0204-3572 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/101666 |
| citation_txt |
Модификация метода возможных направлений для задачи оптимизации размещения объектов специального вида / С.И. Яремчук, Ю.А. Шаповалов // Электронное моделирование. — 2007. — Т. 29, № 2. — С. 29-38. — Бібліогр.: 8 назв. — рос. |
| work_keys_str_mv |
AT âremčuksi modifikaciâmetodavozmožnyhnapravleniidlâzadačioptimizaciirazmeŝeniâobʺektovspecialʹnogovida AT šapovalovûa modifikaciâmetodavozmožnyhnapravleniidlâzadačioptimizaciirazmeŝeniâobʺektovspecialʹnogovida AT âremčuksi modificationofpossibledirectionmethodfortheproblemofarrangementoptimizationofobjectsofspecialkind AT šapovalovûa modificationofpossibledirectionmethodfortheproblemofarrangementoptimizationofobjectsofspecialkind |
| first_indexed |
2025-11-25T21:07:21Z |
| last_indexed |
2025-11-25T21:07:21Z |
| _version_ |
1850550016820641792 |
| fulltext |
ÓÄÊ 519.67
Ñ. È. ßðåì÷óê, êàíä.ôèç.-ìàò. íàóê, Þ. À. Øàïîâàëîâ
Æèòîìèðñêèé ãîñóäàðñòâåííûé òåõíîëîãè÷åñêèé óíèâåðñèòåò
(Óêðàèíà, 10005, Æèòîìèð, óë.×åðíÿõîâñêîãî 103,
òåë.: (0412) 418542, E-mail: yuri-ua@yandex.ru)
Ìîäèôèêàöèÿ ìåòîäà âîçìîæíûõ
íàïðàâëåíèé äëÿ çàäà÷è îïòèìèçàöèè
ðàçìåùåíèÿ îáúåêòîâ ñïåöèàëüíîãî âèäà
Ðàññìîòðåíà çàäà÷à îïòèìèçàöèè ðàçìåùåíèÿ îáúåêòîâ â âûïóêëîé îáëàñòè, êàæäûé èç
êîòîðûõ ìîæåò áûòü ðàçáèò íà âçàèìíî-îðèåíòèðîâàííûå ïðÿìîóãîëüíèêè. Ðàçðàáîòàíà
ìîäèôèêàöèÿ ìåòîäà âîçìîæíûõ íàïðàâëåíèé è ìåòîä íàïðàâëåííîãî ïåðåõîäà. Äëÿ
îöåíêè ýôôåêòèâíîñòè ìåòîäîâ ïðèâåäåíû ðåçóëüòàòû ÷èñëåíûõ ýêñïåðèìåíòîâ.
Ðîçãëÿíóòî çàäà÷ó îïòèì³çàö³¿ ðîçì³ùåííÿ îá’ºêò³â ó îïóêë³é îáëàñò³. Êîæåí ç îá’ºêò³â
ìîæíà ðîçêëàñòè íà âçàºìî-îð³ºíòîâàí³ ïðÿìîêóòíèêè. Ðîçðîáëåíî ìîäèô³êàö³þ ìåòîäà
ìîæëèâèõ íàïðÿìê³â òà ìåòîä ñïðÿìîâàíîãî ïåðåõîäó. Äëÿ îö³íêè åôåêòèâíîñò³ ìåòîä³â
íàâåäåíî ðåçóëüòàòè ÷èñåëüíèõ åêñïåðèìåíò³â.
Ê ë þ ÷ å â û å ñ ë î â à: îïòèìèçàöèÿ ðàçìåùåíèÿ, ìåòîä âîçìîæíûõ íàïðàâëåíèé, ìåòîä
íàïðàâëåííîãî ïåðåõîäà.
Çàäà÷è îïòèìèçàöèè ðàçìåùåíèÿ âîçíèêàþò â ðàçíûõ ñôåðàõ äåÿòåëüíîñ-
òè ÷åëîâåêà. Óíèâåðñàëüíîãî ýôôåêòèâíîãî ìåòîäà èõ ðåøåíèÿ íå ñóùåñò-
âóåò. Áîëüøèíñòâî ðàçðàáîòàííûõ ìåòîäîâ ðàññ÷èòàíû íà âûïóêëûå îáúåê-
òû èëè íà ëèíåéíîñòü ôóíêöèé öåëè. Äàæå â ñëó÷àå âûïîëíåíèÿ ýòèõ
óñëîâèé ðåøåíèå ïðàêòè÷åñêèõ çàäà÷ îïòèìèçàöèè ðàçìåùåíèÿ òðåáóåò
çíà÷èòåëüíûõ âðåìåííûõ è âû÷èñëèòåëüíûõ ðåñóðñîâ. Ïîýòîìó ïðîáëåìà
ðàçðàáîòêè íîâûõ è óñîâåðøåíñòâîâàíèÿ ñóùåñòâóþùèõ ìåòîäîâ îïòèìè-
çàöèè, êîòîðûå ìîãóò áûòü èñïîëüçîâàíû äëÿ ðåøåíèÿ òàêèõ çàäà÷ íà
ÝÂÌ, îñòàåòñÿ àêòóàëüíîé.
Ïîñòàíîâêà çàäà÷è. Ðàññìîòðèì çàäà÷ó îïòèìèçàöèè ðàçìåùåíèÿ
îáúåêòîâ ñïåöèàëüíîé ôîðìû. Ðàçìåùåíèå ÿâëÿåòñÿ äîïóñòèìûì, åñëè
âñå îáúåêòû ïîïàðíî íå ïåðåñåêàþòñÿ è íå âûõîäÿò çà ïðåäåëû çàäàííîé
îáëàñòè. Ñðåäè âñåõ äîïóñòèìûõ ðàçìåùåíèé íåîáõîäèìî íàéòè òàêîå,
ïðè êîòîðîì çàäàííàÿ ôóíêöèÿ öåëè äîñòèãàåò ñâîåãî ìèíèìóìà. Îáúåêòû
ìîãóò áûòü íåâûïóêëûìè, à ôóíêöèÿ öåëè — íåëèíåéíîé.
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2007. Ò. 29. ¹ 2 29
Ïàðàìåòðû çàäà÷è óäîâëåòâîðÿþò ñëåäóþùèì òðåáîâàíèÿì.
1. Îáëàñòü ðàçìåùåíèÿ — âûïóêëàÿ, çàäàíà ñèñòåìîé íåðàâåíñòâ âèäà
� ñ âûïóêëûìè íåïðåðûâíî-äèôôåðåíöèðóåìûìè ôóíêöèÿìè.
2. Ôóíêöèÿ öåëè — íåïðåðûâíî-äèôôåðåíöèðóåìàÿ.
3. Êàæäûé îáúåêò ìîæíî ïðåäñòàâèòü â âèäå îáúåäèíåíèÿ âçàèìíî-
îðèåíòèðîâàííûõ ïðÿìîóãîëüíèêîâ. Ñòîðîíû âñåõ ïðÿìîóãîëüíèêîâ ïà-
ðàëëåëüíû êîîðäèíàòíûì îñÿì.
Àíàëèç èñòî÷íèêîâ èññëåäîâàíèÿ. Çàäà÷àì îïòèìèçàöèè ðàçìåùå-
íèÿ ïîñâÿùåíî ìíîæåñòâî èññëåäîâàíèé. Íàèáîëåå ïîïóëÿðíûìè ÿâëÿþò-
ñÿ çàäà÷è ïëîòíîãî ðàçìåùåíèÿ.  ðàáîòå [1] ðàññìîòðåíà çàäà÷à ïëîòíîãî
ðàçìåùåíèÿ ñ ó÷åòîì çàäàííûõ ìèíèìàëüíî äîïóñòèìûõ ðàññòîÿíèé ìåæ-
äó îáúåêòàìè. Äëÿ íàõîæäåíèÿ òî÷íîãî ðåøåíèÿ çàäà÷è èñïîëüçîâàí ìå-
òîä âåòâåé è ãðàíèö.
 ðàáîòå [2] ðàññìîòðåíà çàäà÷à îïòèìèçàöèè ðàçìåùåíèÿ ïðÿìî-
óãîëüíèêîâ â ïðÿìîóãîëüíîé îáëàñòè. Êðèòåðèé êà÷åñòâà îïèñàí äèôôå-
ðåíöèðóåìîé ôóíêöèåé. Äëÿ ðåøåíèÿ ïîäçàäà÷ ðàçðàáîòàí ìåòîä G-ïðîåê-
öèé, îñíîâàííûé íà ìåòîäå ïðîåêöèè ãðàäèåíòà Ðîçåíà.
Äàííîå èññëåäîâàíèå ÿâëÿåòñÿ ïðîäîëæåíèåì ðàáîò [3, 4]. Â [3] ðàñ-
ñìîòðåíà çàäà÷à îïòèìèçàöèè ðàçìåùåíèÿ ïðÿìîóãîëüíèêîâ íà ïðÿìî-
óãîëüíîé îáëàñòè. Íåâûïóêëîå, ìíîãîñâÿçíîå, íåñâÿçíîå ìíîæåñòâî äî-
ïóñòèìûõ ðåøåíèé çàäà÷è ïðåäñòàâëåíî â âèäå îáúåäèíåíèÿ âûïóêëûõ
ïîäìíîæåñòâ. Èñõîäíàÿ çàäà÷à ðåøàåòñÿ ïóòåì ðåøåíèÿ ïîñëåäîâàòåëü-
íîñòè ïîäçàäà÷ íà ïîëó÷åííûõ ïîäìíîæåñòâàõ.  ðàáîòå [4] ðàññìîòðåíà
çàäà÷à îïòèìèçàöèè ðàçìåùåíèÿ ïðÿìîóãîëüíèêîâ íà âûïóêëîé îáëàñòè,
çàäàííîé ñèñòåìîé íåëèíåéíûõ îãðàíè÷åíèé. Äëÿ åå ðåøåíèÿ ðàçðàáîòàíà
ìîäèôèêàöèÿ ìåòîäà âîçìîæíûõ íàïðàâëåíèé è ìåòîä íàïðàâëåííîãî
ïåðåõîäà ìåæäó ïîäìíîæåñòâàìè.
Öåëü äàííîãî èññëåäîâàíèÿ — ïîñòðîåíèå ìîäåëè çàäà÷è îïòèìèçàöèè
ðàçìåùåíèÿ îáúåêòîâ, êàæäûé èç êîòîðûõ ìîæíî ðàçáèòü íà îðèåíòèðî-
âàííûå ïðÿìîóãîëüíèêè, è ðàçðàáîòêà àëãîðèòìà ðåøåíèÿ ýòîé çàäà÷è.
Ìàòåìàòè÷åñêàÿ ìîäåëü çàäà÷è. Çàäàíû m îáúåêòîâ Fi , i m�1, ,
îáëàñòü ðàçìåùåíèÿ � è ôóíêöèÿ öåëè � ( )Z , çíà÷åíèå êîòîðîé çàâèñèò îò
ïîëîæåíèÿ îáúåêòîâ íà îáëàñòè ðàçìåùåíèÿ. Íà ðèñ. 1 ïðèâåäåí ïðèìåð
äîïóñòèìîãî ðàçìåùåíèÿ ÷åòûðåõ îáúåêòîâ â ðåçóëüòàòå ðåøåíèÿ çàäà÷è
îïòèìèçàöèè.
Êàæäûé èç îáúåêòîâ Fi , i m�1, , ìîæíî ðàçáèòü íà ïðÿìîóãîëüíèêè
D D Di i im1 2
, ,..., . Ïîëîæåíèå îáúåêòà Fi , i m�1, , íà îáëàñòè � îïðåäåëÿåòñÿ
êîîðäèíàòàìè åãî ïîëþñà [5]. Ïîëþñîì îáúåêòà Fi íàçîâåì ãåîìåòðè-
÷åñêèé öåíòð îäíîãî èç åãî ïðÿìîóãîëüíèêîâ (D D Di i im1 2
, ,..., ). Äëÿ îïðåäå-
ëåííîñòè ïóñòü ïîëþñîì Zi i i
( , )� �
� 2
îáúåêòà Fi áóäåò öåíòð ïåðâîãî ïðÿ-
Ñ. È. ßðåì÷óê, Þ. À. Øàïîâàëîâ
30 ISSN 0204–3572. Electronic Modeling. 2007. V. 29. ¹ 2
ìîóãîëüíèêà Di1, i m�1, .  ñâîþ î÷åðåäü, ïîëþñîì ïðÿìîóãîëüíèêà Dij ,
i m�1, , j mi�1, , áóäåì ñ÷èòàòü åãî ãåîìåòðè÷åñêèé öåíòð. Òîãäà, äëÿ îïèñàíèÿ
îáúåêòîâ Fi , i m�1, , äîñòàòî÷íî óêàçàòü ðàçìåðû L l lij ij ij
( , )
1 2
âñåõ ïðÿìîóãîëü-
íèêîâ Dij , j m�1, , è ïîëîæåíèå C c cij ij ij
( , )
1 2
ýòèõ ïðÿìîóãîëüíèêîâ â ïîäâèæ-
íîé ñèñòåìå êîîðäèíàò, öåíòð êîòîðîé ñîâïàäàåò ñ ïîëþñîì Zi i i
( , )� �
� 2
ñîîò-
âåòñòâóþùåãî îáúåêòà Fi , à îñè ïàðàëëåëüíû ñòîðîíàì ïðÿìîóãîëüíèêîâ.
Òàêèì îáðàçîì, êàæäûé îáúåêò Fi , i m�1, , çàäàåòñÿ ïàðàìåòðàìè L l lij ij ij
( , )
1 2
,
C c cij ij ij
( , )
1 2
, i m�1, , j mi�1, . Ïîëîæåíèå îáúåêòîâ íà îáëàñòè � îïðåäåëÿåòñÿ
êîîðäèíàòàìè âåêòîðà Z Z Z Zm m m
( , , ..., ) ( , , , , ..., , )
1 2 1
2
1
1
2
2
2
1 2
� � � � � � �
�
.
Òàêèì îáðàçîì, èìååòñÿ çàäà÷à óñëîâíîé îïòèìèçàöèè
�( ) minZ � , Z G , (1)
ãäå Z Z Z Zm
( , , ..., )
1 2
— ïàðàìåòð ðàçìåùåíèÿ îáúåêòîâ Fi , i mi�1, ; G —
ìíîæåñòâî äîïóñòèìûõ ðåøåíèé çàäà÷è; � ( )Z — ôóíêöèÿ öåëè, íåïðå-
ðûâíî-äèôôåðåíöèðóåìàÿ íà âûïóêëîì ìíîæåñòâå X G
.
Ìíîæåñòâî G îïðåäåëÿåòñÿ óñëîâèÿìè ïðèíàäëåæíîñòè îáúåêòîâ îáëàñ-
òè � è óñëîâèÿìè âçàèìíîãî íåïåðåñå÷åíèÿ îáúåêòîâ.
Äëÿ òîãî ÷òîáû îáúåêò Fi , i m�1, , ïðèíàäëåæàë âûïóêëîé îáëàñòè
ðàçìåùåíèÿ, äîñòàòî÷íî íàëîæèòü îãðàíè÷åíèÿ íà êîîðäèíàòû òîëüêî òåõ
âåðøèí îáúåêòà, êîòîðûå ÿâëÿþòñÿ óãëîâûìè òî÷êàìè âûïóêëîé îáîëî÷-
êè âåðøèí åãî ïðÿìîóãîëüíèêîâ Dij , j mi�1, . Âèä è ÷èñëî îãðàíè÷åíèé
çàâèñÿò îò ôîðìû îáëàñòè �, ÷èñëà è ôîðìû îáúåêòîâ Fi , i m�1, .  îáùåì
âèäå ýòè îãðàíè÷åíèÿ çàïèøåì òàê:
� p Z( ) � 0, p v�1, , (2)
Ìîäèôèêàöèÿ ìåòîäà âîçìîæíûõ íàïðàâëåíèé äëÿ çàäà÷è îïòèìèçàöèè
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2007. Ò. 29. ¹ 2 31
2
1
3,1
2
1,1
2
1,1
1
2,1
2
2,2
2
2,3
2
2,1
1
2,2
1
2,3
1
3,1
1
4
F
1
F
2
F
3
F
4,1
1
4,1
2
Ðèñ. 1. Ïðèìåð äîïóñòèìîãî ðàçìåùåíèÿ ÷åòûðåõ îáúåêòîâ
ãäå� p Z( ) — ôóíêöèè, íåïðåðûâíî-äèôôåðåíöèðóåìûå, âûïóêëûå íà âû-
ïóêëîì ìíîæåñòâå X G
.
Äëÿ òîãî ÷òîáû îáúåêòû Fi , Fk , i m� �1 1, , k i m�
1, , íå ïåðåñåêàëèñü,
íåîáõîäèìî îáåñïå÷èòü íåïåðåñå÷åíèå âñåõ ïàð ïðÿìîóãîëüíèêîâ Dij , Dkl ,
j mi�1, , l mk�1, . Óñëîâèÿ íåïåðåñå÷åíèÿ èìåþò âèä
� � � �
� � � �
� �
� �
i ij k kl
ij kl
i ij k klc c
l l
c c
�
�
�
�
( ) ( )
2
2 2
�
l lij kl
2 2
2
,
i m� �1 1, , j mi�1, , k i m�
1, , l mk�1, . (3)
Òàêèì îáðàçîì, ìíîæåñòâî G îïèñûâàåìîå îãðàíè÷åíèÿìè (2), (3), —
íåâûïóêëîå, ìíîãîñâÿçíîå, ìîæåò áûòü íåñâÿçíûì ñ áîëüøèì ÷èñëîì
êîìïîíåíò ñâÿçíîñòè.
Ïðåäñòàâèì ìíîæåñòâî äîïóñòèìûõ ðåøåíèé çàäà÷è (1) â âèäå îáúå-
äèíåíèÿ âûïóêëûõ ïîäìíîæåñòâ Gs:
G G
s
r
s� �
�1
,
(4)
ãäå r C
� 4 [6]. Òîãäà ðåøåíèå èñõîäíîé çàäà÷è ìîæíî çàìåíèòü ðåøåíèåì
ïîñëåäîâàòåëüíîñòè ïîäçàäà÷ îïòèìèçàöèè. Êàæäàÿ ïîäçàäà÷à — ýòî çà-
äà÷à îïòèìèçàöèè ôóíêöèè öåëè èñõîäíîé çàäà÷è (1) íà âûïóêëûõ ïîä-
ìíîæåñòâàõ Gs, s r�1, , èìåþùàÿ âèä
� ( ) minZ � , Z Gs , s r�1, . (5)
 êà÷åñòâå ðåøåíèÿ èñõîäíîé çàäà÷è (1) ïðèíèìàåòñÿ ëó÷øåå èç ðåøåíèé
ïîäçàäà÷ (5).
Äåêîìïîçèöèÿ (4) îñóùåñòâëÿåòñÿ ñëåäóþùèì îáðàçîì. Îãðàíè÷åíèå
íåïåðåñå÷åíèÿ ïàðû ïðÿìîóãîëüíèêîâ Dij , Dkl , i m� �1 1, , j mi�1, , k i m�
1, ,
l mk�1, , ïðè óñëîâèÿõ (3) ìîæíî çàïèñàòü â âèäå ñòðóêòóðû ëèíåéíûõ
íåðàâåíñòâ
( ) ( ) ( ) (� � � �
� � � �
� �
� �
i ij k kl
ij kl
i ij kc c
l l
c c
�
�
�
�
2
2 2
2 2
2
2
kl
ij kl
k kl i ij
ij kl
l l
c c
l l
) ,
( ) ( ) (
�
�
�
�� �
� � � �
� �
� �
� �
k kl i ij
ij kl
c c
l l
�
�
�
�
�
�
�
� 2 2
2 2
2
) ( ) ,
(6)
ò.å. äëÿ íåïåðåñå÷åíèÿ îáúåêòîâ Fi , Fk , i m� �1 1, , k i m�
1, , äîñòàòî÷íî,
÷òîáû äëÿ êàæäîé ïàðû ïðÿìîóãîëüíèêîâ Dij , Dkl , ïðèíàäëåæàùèõ ðàç-
íûì îáúåêòàì Fi , Fk , âûïîëíÿëîñü õîòÿ áû îäíî èç íåðàâåíñòâ (6).
Òàêèì îáðàçîì, ñèñòåìà îãðàíè÷åíèé, çàäàþùàÿ âûïóêëûå ïîäìíî-
æåñòâà Gs, s r�1, , ñîñòîèò èç ëèíåéíûõ íåðàâåíñòâ, îáåñïå÷èâàþùèõ íå-
Ñ. È. ßðåì÷óê, Þ. À. Øàïîâàëîâ
32 ISSN 0204–3572. Electronic Modeling. 2007. V. 29. ¹ 2
ïåðåñå÷åíèå îáúåêòîâ (ïî îäíîìó äëÿ êàæäîé ïàðû ïðÿìîóãîëüíèêîâ,
ïðèíàäëåæàùèõ ðàçíûì îáúåêòàì), è îãðàíè÷åíèé (2), êîòîðûå îáåñïå÷è-
âàþò íåâûõîä îáúåêòîâ çà ãðàíèöû îáëàñòè �.
Îãðàíè÷åíèÿ, çàäàþùèå Gs, çàïèøåì â âèäå � i Z( ) � 0, i q�1, , ãäå q —
îáùåå ÷èñëî îãðàíè÷åíèé, çàâèñÿùåå îò ôîðìû è ÷èñëà îáúåêòîâ Fi , à
òàêæå îò ôîðìû îáëàñòè �.
Äëÿ ðåøåíèÿ ïîäçàäà÷ (5) ïðèìåíÿåòñÿ ìåòîä âîçìîæíûõ íàïðàâ-
ëåíèé [7, 8].  ýòîì ìåòîäå âåêòîð ñïóñêà h â òî÷êå Zk
èìååò ñëåäóþùèå
ñâîéñòâà:
1) h ÿâëÿåòñÿ íàïðàâëåíèåì óìåíüøåíèÿ ôóíêöèè öåëè;
2) óãîë ìåæäó h è ãðàäèåíòàìè �-àêòèâíûõ îãðàíè÷åíèé — òóïîé.
Îãðàíè÷åíèå íàçûâàåòñÿ �-àêòèâíûì â òî÷êå Zk
, åñëè äëÿ íåãî ñïðà-
âåäëèâî íåðàâåíñòâî
� � �� �k i
kZ( ) 0, (7)
ãäå � k �0 — ïàðàìåòð ìåòîäà. Ïåðâîå ñâîéñòâî îáåñïå÷èâàåòñÿ ïðè âû-
ïîëíåíèè óñëîâèÿ
��� ( ), )Z h yk
� , y k� �� .
Äëÿ îáåñïå÷åíèÿ âòîðîãî ñâîéñòâà íà íàïðàâëåíèå ñïóñêà íàëîæåíî
îãðàíè÷åíèå
�� �� i
kZ h y( ), ) , y k� �� , i I Zk
k ( , )� , (8)
ãäå I Zk
k( , )� — ìíîæåñòâî íîìåðîâ �-àêòèâíûõ îãðàíè÷åíèé.
Óñëîâèå (8) ïðèìåíÿåòñÿ â ñëó÷àå, åñëè â �-àêòèâíîì îãðàíè÷åíèè (7)
ôóíêöèÿ � i Z( )— íåëèíåéíàÿ. Äëÿ ëèíåéíûõ �-àêòèâíûõ îãðàíè÷åíèé ýòî
òðåáîâàíèå ÿâëÿåòñÿ ëèøíèì. Åñëè ðåøåíèå çàäà÷è íàõîäèòñÿ íà ãðàíèöå
ìíîæåñòâà Gs, s r�1, , íàëîæåíèå óñëîâèÿ (8) ïðèâîäèò ê çíà÷èòåëüíîìó
óìåíüøåíèþ ñêîðîñòè ñõîäèìîñòè ìåòîäà, ò. å. ê óâåëè÷åíèþ âðåìåíè
ðåøåíèÿ çàäà÷è. Ïîýòîìó äëÿ ëèíåéíûõ îãðàíè÷åíèé óñëîâèå (8) ïðåä-
ëàãàåòñÿ îñëàáèòü, çàïèñàâ åãî â ñëåäóþùåì âèäå:
�� �� i
kZ h( ), ) 0, i I Zk
k ( , )� . (9)
Î÷åâèäíî, âäîëü �-àêòèâíîãî ëèíåéíîãî îãðàíè÷åíèÿ, â íàïðàâëåíèè h,
óäîâëåòâîðÿþùåì (9), ìîæíî ñäåëàòü ñêîëü óãîäíî áîëüøîé øàã, áåç åãî
íàðóøåíèÿ.
×èñëî ïîäìíîæåñòâ Gs ïðè óâåëè÷åíèè ÷èñëà îáúåêòîâ âîçðàñòàåò
î÷åíü áûñòðî [5]. Òàê, äëÿ çàäà÷è îïòèìèçàöèè ðàçìåùåíèÿ øåñòè îáúåê-
òîâ íà ðåøåíèå âñåõ ïîäçàäà÷ (5) òðåáóþòñÿ îãðîìíûå âðåìåííûå çàòðàòû.
Ïîýòîìó äëÿ ðåøåíèÿ çàäà÷è (1) ðàçðàáîòàí ìåòîä íàïðàâëåííîãî ïåðå-
õîäà ìåæäó âûïóêëûìè ïîäìíîæåñòâàìè.
Ìîäèôèêàöèÿ ìåòîäà âîçìîæíûõ íàïðàâëåíèé äëÿ çàäà÷è îïòèìèçàöèè
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2007. Ò. 29. ¹ 2 33
Èäåÿ ìåòîäà ñîñòîèò â ñëåäóþùåì. Ïîäìíîæåñòâà Gs, s r�1, , îòëè-
÷àþòñÿ ìåæäó ñîáîé òîëüêî òåì, êàêîå èç ÷åòûðåõ âîçìîæíûõ ëèíåéíûõ
íåðàâåíñòâ (6) äëÿ êàæäîé ïàðû ïðÿìîóãîëüíèêîâ Dij , Dkl , j mi�1, , l mk�1, ,
i m� �1 1, , k i m�
1, , âõîäèò â ñèñòåìó îãðàíè÷åíèé. Ïðåäëàãàåòñÿ íà êàæäîé
èòåðàöèè ìåòîäà âîçìîæíûõ íàïðàâëåíèé ïîñëå ïåðåõîäà â òî÷êó Zk
â
ñëó÷àå íàëè÷èÿ �-àêòèâíîãî îãðàíè÷åíèÿ � i
kZ( ) � 0 íåïåðåñå÷åíèÿ ïàðû
ïðÿìîóãîëüíèêîâ Dij , Dkl ïðîâåðÿòü âûïîëíåíèå îäíîãî èç äâóõ óñëîâèé
íåïåðåñå÷åíèÿ ýòèõ ïðÿìîóãîëüíèêîâ ïî äðóãîé êîîðäèíàòå. Åñëè ñó-
ùåñòâóåò ñîîòâåòñòâóþùåå îãðàíè÷åíèå � i
kZ*
( ) � 0 íåïåðåñå÷åíèÿ Dij , Dkl ,
äëÿ êîòîðîãî âûïîëíÿåòñÿ óñëîâèå � �i
k
kZ*
( ) � � , òî â ñèñòåìå îãðàíè-
÷åíèé çàäà÷è, âûïîëíÿåòñÿ çàìåíà �-àêòèâíîãî îãðàíè÷åíèÿ � i Z( ) � 0 íå
�-àêòèâíûì � i Z*
( ) � 0. Òàêèì îáðàçîì ðàñøèðÿåòñÿ ìíîæåñòâî âîçìîæíûõ
íàïðàâëåíèé h â òî÷êå Zk
, îñóùåñòâëÿåòñÿ ïåðåõîä ê ñëåäóþùåìó ïîä-
ìíîæåñòâó Gs è ñîêðàùàåòñÿ âðåìÿ, çàòðà÷èâàåìîå íà ðåøåíèå èñõîäíîé
çàäà÷è.
Àëãîðèòì ðåøåíèÿ çàäà÷è îïòèìèçàöèè ðàçìåùåíèÿ îáúåêòîâ,
êîòîðûå ìîæíî ðàçëîæèòü íà ïðÿìîóãîëüíèêè.
1. k �0. Âûáèðàåòñÿ íà÷àëüíîå ðàçìåùåíèå Z0 1
2
1
1
2
2
2
� ( , , , , ...� � � �
�
..., , )� �
1 2
m m
sG G � , s r�1, , ïàðàìåòðû ìåòîäà � �0, � �
0
� , 0 1� �� .
2. Èìååòñÿ k-å ïðèáëèæåíèå ðåøåíèÿ çàäà÷è Zk
, � k �0, k �0 1, ,...
2.1. Ïðîâåðÿþòñÿ îãðàíè÷åíèÿ, çàäàþùèå óñëîâèÿ âçàèìíîãî íåïåðå-
ñå÷åíèÿ îáúåêòîâ. Åñëè äëÿ îãðàíè÷åíèÿ � i
kZ( ) � 0, îáåñïå÷èâàþùåãî
íåïåðåñå÷åíèå ïðÿìîóãîëüíèêîâ D jl , Dks, j k� , âûïîëíÿåòñÿ óñëîâèå
� �� � �k i
kZ( ) 0, ò. å. îãðàíè÷åíèå � i
kZ( ) � 0 ÿâëÿåòñÿ �-àêòèâíûì, òî âû-
ïîëíÿåòñÿ ïðîâåðêà: åñëè äëÿ ýòîé ïàðû îáúåêòîâ D jl , Dks âûïîëíÿåòñÿ
îãðàíè÷åíèå èõ íåïåðåñå÷åíèÿ ïî äðóãîé êîîðäèíàòå � i
kZ*
( ) � 0, ïðè÷åì
� �i
k
kZ*
( ) � � (ò. å. îãðàíè÷åíèå � i
kZ*
( ) � 0 â òî÷êå Zk
íå ÿâëÿåòñÿ �-àêòèâ-
íûì), òî â ñèñòåìå îãðàíè÷åíèé ïîäçàäà÷è îñóùåñòâëÿåòñÿ çàìåíà� i
kZ( ) � 0
íà � i
kZ*
( ) � 0.
2.2. Ñòðîèòñÿ ìíîæåñòâî íîìåðîâ �-àêòèâíûõ îãðàíè÷åíèé çàäà÷è
I Z i q Zk
k k i
k
( , ) { , : ( ) }� � �� � � �1 0 .
2.3. Íàõîäèòñÿ âåêòîð ñïóñêà â òî÷êå Zk
. Äëÿ ýòîãî ðåøàåòñÿ âñïî-
ìîãàòåëüíàÿ çàäà÷à ëèíåéíîãî ïðîãðàììèðîâàíèÿ
�( , ,..., , ) minh h h y ym1 2 2
� �
Ñ. È. ßðåì÷óê, Þ. À. Øàïîâàëîâ
34 ISSN 0204–3572. Electronic Modeling. 2007. V. 29. ¹ 2
( ( ), ) ,
( ( ), ) , ( , ), ( )
� �
� � � �
�
� � �
Z h y
Z h y i I Z Z
k
i
k k
k iåñëè íåëèíåéíàÿ,
åñëè ëè( ( ), ) , ( , ), ( )� � � �� � �i
k k
k iZ h i I Z Z0 íåéíàÿ,
h i mi � �
!
"
"
#
"
"
1 12, ,
( ( , , ..., ), )h h h h yk k k
m
k
k1 2 2
— ðåøåíèå âñïîìîãàòåëüíîé çàäà÷è.
Åñëè yk k� �� è � �k � , òî ïðîöåññ ïðåêðàùàåòñÿ, Zk
ÿâëÿåòñÿ ðåøå-
íèåì çàäà÷è.
Åñëè yk k� �� è � �k � , òî Z Zk k
�
1
, � ��k k
�
1
, k ïðèñâàèâàåòñÿ k
1è
îñóùåñòâëÿåòñÿ ïåðåõîä ê ï. 2.
Åñëè yk k� �� , òî hk
— âåêòîð ñïóñêà.
2.4. Ïîèñê k
1-ãî ïðèáëèæåíèÿ, Z Z hk k
k
k
�
1
$ , ãäå$ �
$
k
B
k
k
Z�
� �
argmin (
0
$hk
); Bk — ìàêñèìàëüíî äîïóñòèìîå $, ïðè êîòîðîì âûïîëíÿþòñÿ âñå
íåðàâåíñòâà � $i
k kZ h( )
� 0, i q�1, , ñèñòåìû îãðàíè÷åíèé ïîäçàäà÷è. Ïå-
ðåìåííîé k ïðèñâàèâàåòñÿ çíà÷åíèå k
1è îñóùåñòâëÿåòñÿ ïåðåõîä ê ï. 2.
Ðàçðàáîòàííûé àëãîðèòì ïðîãðàììíî ðåàëèçîâàí. Íà÷àëüíîå ïðèáëè-
æåíèå Z0
íàõîäèòñÿ ìåòîäîì øòðàôíûõ ôóíêöèé. Øàã $k âû÷èñëÿåòñÿ
ìåòîäîì ïðîñòåéøåãî ïåðåáîðà îäíîìåðíîé îïòèìèçàöèè [8].
Äëÿ îöåíêè ýôôåêòèâíîñòè ìîäèôèêàöèè (9) ðåøåíèÿ ïîäçàäà÷ (5)
ïðîâåäåí ÷èñëåííûé ýêñïåðèìåíò. Ïîñêîëüêó ìîäèôèêàöèÿ (9) âëèÿåò íà
ðåøåíèå çàäà÷è òîëüêî â ñëó÷àå íàëè÷èÿ �-àêòèâíûõ ëèíåéíûõ îãðàíè-
÷åíèé, áûëà âûáðàíà òåñòîâàÿ çàäà÷à ìèíèìèçàöèè ñóììû êâàäðàòîâ ðàñ-
Ìîäèôèêàöèÿ ìåòîäà âîçìîæíûõ íàïðàâëåíèé äëÿ çàäà÷è îïòèìèçàöèè
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2007. Ò. 29. ¹ 2 35
100
200
300
400
500
600
0 4 8 12 16 20
×èñëî îáúåêòîâ, m
0
1
2
3
4 8 12 16 20
Â
ð
å
ì
ÿ
ð
å
ø
å
í
è
ÿ
,
ñ
à á
Ðèñ. 2. Ãðàôèêè çàâèñèìîñòè âðåìåíè ðåøåíèÿ ïîäçàäà÷ ìåòîäîì âîçìîæíûõ íàïðàâ-
ëåíèé (à) è ìîäèôèöèðîâàííûì ìåòîäîì (á) îò ÷èñëà îáúåêòîâ
ñòîÿíèé îò ïîëþñîâ îáúåêòîâ äî çàäàííîé âíóòðåííåé òî÷êè îáëàñòè �,
èìåþùåé ôîðìó ïðÿìîóãîëüíèêà. Íà ðèñ. 2 ïðèâåäåíû ïîëó÷åííûå çàâè-
ñèìîñòè âðåìåíè ðåøåíèÿ ïîäçàäà÷ îò ÷èñëà ïðÿìîóãîëüíèêîâ.
Äëÿ îöåíêè òî÷íîñòè ïîëó÷åííûõ ðåøåíèé ïîñòðîåíà çàâèñèìîñòü
(ðèñ. 3) ïîãðåøíîñòè ìåòîäà Çîéòåíäåéêà îò ðåøåíèé, ïîëó÷åííûõ ñ èñïîëü-
çîâàíèåì ìîäèôèêàöèè (9). Îöåíêà òî÷íîñòè ìåòîäîâ ïðîâîäèëîñü ïî çíà÷å-
íèþ ôóíêöèè öåëè, ñîîòâåòñòâóþùåìó êîíå÷íîìó ðàçìåùåíèþ, ïî ôîðìóëå
� �
% �� �
�
( ) ( )
( )
%
*
*
Z Z
Z
100 ,
Ñ. È. ßðåì÷óê, Þ. À. Øàïîâàëîâ
36 ISSN 0204–3572. Electronic Modeling. 2007. V. 29. ¹ 2
0
20
40
60
80
100
0 5 10 15 20 m
Î
ò
ë
è
÷
è
å
ï
î
ë
ó
÷
å
í
í
û
õ
ð
å
ø
å
í
è
é
,
%
Ðèñ. 3. Îöåíêà òî÷íîñòè ìåòîäîâ
1.1
2.1
2.2
2.3
3.1
3.2
3.3
4.1
4.2 4.3
5.1
6.1
6.2
7.1
7.2
8.1
1.1
2.1
2.2
2.3
3.1
3.2
3.3
4.14.2 4.3
5.1
6.16.2
7.1
7.2 8.1
282.262
à á
Ðèñ. 4. Ïðèìåð ðåøåíèÿ òåñòîâîé çàäà÷è: à — íà÷àëüíîå ïðèáëèæåíèå, á — ïîëó÷åííîå
ðàçìåùåíèå
ãäå �( )%Z è �( )
*Z — çíà÷åíèÿ ôóíêöèè öåëè, ñîîòâåòñòâóþùèå ðàçìåùå-
íèþ, ïîëó÷åííîìó ìåòîäîì Çîéòåíäåéêà, è ìîäèôèöèðîâàííûì ìåòîäîì.
Íà ðèñ. 4 ïðèâåäåí ïðèìåð ðåøåíèÿ òåñòîâîé çàäà÷è
� � �( ) (( ( )) ( ( )) ) minZ x c x ci ij i ij
j
m
i
� �
�
�
�
& 1 1 1
2
2 2 2
2
1�
&
1
m
, Z G ,
ãäå x x x( , )
1 2
�— çàäàííàÿ òî÷êà. ×èñëî îáúåêòîâ — 8. Îáúåêòû ðàçáèòû
íà ïðÿìîóãîëüíèêè. Îáùåå ÷èñëî ïðÿìîóãîëüíèêîâ — 16. Ôóíêöèÿ öåëè
ïðè íà÷àëüíîì ðàçìåùåíèè �( ) ,Z0
282 262� , ïðè êîíå÷íîì ðàçìåùåíèè
�( ) ,Z60
67 234� . Ðåøåíèå çàäà÷è íà ìàøèíå ñ ïðîöåññîðîì AMD Athlon XP
2400+ ïîëó÷åíî çà 0,2 ñ. ×èñëî èòåðàöèé — 60, ïåðåõîäîâ ìåæäó ïîäìíî-
æåñòâàìè — 14.
Äëÿ óëó÷øåíèÿ ïîëó÷åííîãî ðàçìåùåíèÿ öåëåñîîáðàçíî ðåøèòü çàäà-
÷ó íåñêîëüêî ðàç, èñïîëüçóÿ ðàçëè÷íûå íà÷àëüíûå ïðèáëèæåíèÿ, è âûá-
ðàòü ëó÷øåå èç ïîëó÷åííûõ ðåøåíèé.
Âûâîäû. Â ðåçóëüòàòå äàííîãî èññëåäîâàíèÿ
îñóùåñòâëåíà äåêîìïîçèöèÿ íåâûïóêëîãî ìíîãîñâÿçíîãî ìíîæåñòâà
äîïóñòèìûõ ðåøåíèé çàäà÷è íà âûïóêëûå ïîäìíîæåñòâà, ÷òî ïîçâîëèëî
ïðèìåíèòü äëÿ ðåøåíèÿ çàäà÷è ìåòîä âîçìîæíûõ íàïðàâëåíèé;
ðàçðàáîòàíà ìîäèôèêàöèÿ ìåòîäà âîçìîæíûõ íàïðàâëåíèé è ìåòîä
íàïðàâëåííîãî ïåðåõîäà ìåæäó ïîäìíîæåñòâàìè;
ïîñòðîåíû êðèâûå, õàðàêòåðèçèðóþùèå âðåìåííóþ ñëîæíîñòü è îòíî-
ñèòåëüíóþ òî÷íîñòü ðàçðàáîòàííîãî àëãîðèòìà.
Ïî ðåçóëüòàòàì âû÷èñëèòåëüíîãî ýêñïåðèìåíòà ìîæíî ñäåëàòü ñëåäóþ-
ùèé âûâîä: ïî ñðàâíåíèþ ñ ìåòîäîì Çîéòåíäåéêà ìîäèôèöèðîâàííûé ìåòîä
ïðè îäèíàêîâûõ ïàðàìåòðàõ ïîçâîëÿåò ðåøàòü ïîäçàäà÷è íà âûïóêëûõ ïîä-
ìíîæåñòâàõ çà ìåíüøåå âðåìÿ è ïîëó÷àòü ïðè ýòîì ëó÷øèå ðàçìåùåíèÿ.
A problem of the object arrangement optimization in convex domain is considered. Here each of
them may be divided in mutually oriented rectangles. A modification of the possible directions
method and the method of directed transition are developed. The results of numerical experi-
ments are presented for estimation of the method efficience.
1. ßñüêîâ Ã. Ì. Ìàòåìàòè÷íà ìîäåëü òà ìåòîäè ðîçâ’ÿçàííÿ çàäà÷³ ðîçì³ùåííÿ ïðÿ-
ìîêóòíèê³â ç óðàõóâàííÿì ïðèïóñòèìèõ â³äñòàíåé: Äèñ...êàíä. òåõí. íàóê. — ²í-ò
ïðîáë. ìàøèíîáóä. ³ì. À.Ì. ϳäãîðíîãî ÍÀÍ Óêðà¿íè. — Õàðêiâ, 2000. — 128 c.
2. ßðåì÷óê Ñ. ²., Ðóäþê Ë. Â. Àëãîðèòìè ðîçâ’ÿçàííÿ çàäà÷³ ðîçì³ùåííÿ ïðÿìîêóòíèê³â â
ïðÿìîêóòí³é îáëàñò³ // ³ñíèê Êè¿âñüêîãî óí-òó ³ì. Òàðàñà Øåâ÷åíêà. — 2005. — ¹ 2 —
Ñ. 339 — 343.
3. ßðåì÷óê Ñ. ²., Æîâíîâñüêèé Ä. Î., Ñï³âàê À. Â. Ìîäèô³êàö³ÿ ìåòîäó óìîâíîãî ãðà-
䳺íòó äëÿ ðîçâ’ÿçàííÿ çàäà÷ îïòèìàëüíîãî ðîçì³ùåííÿ äæåðåë ô³çè÷íèõ ïîë³â //
³ñíèê ƲҲ. Òåõí³÷í³ íàóêè.— 1999. — ¹ 9.— Ñ. 248—253.
Ìîäèôèêàöèÿ ìåòîäà âîçìîæíûõ íàïðàâëåíèé äëÿ çàäà÷è îïòèìèçàöèè
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2007. Ò. 29. ¹ 2 37
4. ßðåì÷óê Ñ. ²., Øàïîâàëîâ Þ. Î. Ìîäèô³êàö³ÿ ìåòîäó ìîæëèâèõ íàïðÿìê³â äëÿ çàäà÷³
îïòèì³çàö³¿ ðîçì³ùåííÿ // ³ñíèê Õìåëüíèöüêîãî íàö³îíàëüíîãî óí³âåðñèòåòó. —
2005. — ¹ 5, ×.1, Ò.2. — Ñ.146—151.
5. Ñòîÿí Þ. Ã., Ãèëü Í. È. Ìåòîäû è àëãîðèòìû ðàçìåùåíèÿ ïëîñêèõ ãåîìåòðè÷åñêèõ
îáúåêòîâ. — Êèåâ : Íàóê. äóìêà, 1976. — 248 ñ.
6. Âëàñåíêî Î. Â., Ñï³âàê À. Â., ßðåì÷óê Ñ. ². Ìåòîä óìîâíîãî ãðà䳺íòà äëÿ îïòè-
ìàëüíîãî ðîçòàøóâàííÿ äæåðåë ô³çè÷íèõ ïîë³â // ³ñíèê ƲҲ. Òåõí³÷í³ íàóêè. —
1998. — ¹ 7. — Ñ. 248—253.
7. Âàñèëüåâ Ô. Ï. ×èñëåííûå ìåòîäû ðåøåíèÿ ýêñòðåìàëüíûõ çàäà÷. — Ì. : Íàóêà, 1980. —
518 ñ.
8. ßðåì÷óê Ñ. ². Ââåäåííÿ â ìàòåìàòè÷í³ ìåòîäè äîñë³äæåííÿ îïåðàö³é: Ó÷. ïîñ³á. —
Æèòîìèð : ƲҲ, 2002. — 300 ñ.
Ïîñòóïèëà 05.06.06;
ïîñëå äîðàáîòêè 17.01.07
ßÐÅÌ×ÓÊ Ñâåòëàíà Èâàíîâíà, êàíä. ôèç.-ìàò. íàóê, äîöåíò, ïðîôåññîð êàôåäðû ïðîãðàì-
ìíîãî îáåñïå÷åíèÿ âû÷èñëèòåëüíîé òåõíèêè Æèòîìèðñêîãî ãîñóäàðñòâåííîãî òåõíîëîãè÷åñ-
êîãî óíèâåðñèòåòà, êîòîðûé îêîí÷èëà â 1970 ã. Îáëàñòü íàó÷íûõ èññëåäîâàíèé — ýêñòðå-
ìàëüíûå çàäà÷è, ìàòåìàòè÷åñêîå ìîäåëèðîâàíèå.
ØÀÏÎÂÀËΠÞðèé Àëåêñàíäðîâè÷, äîöåíò êàôåäðû ïðîãðàììíîãî îáåñïå÷åíèÿ âû÷èñëèòåëü-
íîé òåõíèêè Æèòîìèðñêîãî ãîñóäàðñòâåííîãî òåõíîëîãè÷åñêîãî óíèâåðñèòåòà, êîòîðûé îêîí÷èë
â 2002 ã. Îáëàñòü íàó÷íûõ èññëåäîâàíèé — ìåòîäû îïòèìèçàöèè, êîìïüþòåðíîå ìîäåëèðîâàíèå.
Ñ. È. ßðåì÷óê, Þ. À. Øàïîâàëîâ
38 ISSN 0204–3572. Electronic Modeling. 2007. V. 29. ¹ 2
|