Решение экстремальных задач с дробно-линейными функциями цели на комбинаторной конфигурации перестановок при условии многокритериальности
Рассмотрена экстремальная задача оптимизации с дробно-линейными функциями цели на комбинаторной конфигурации перестановок при условии многокритериальности. Проанализированы методы решения дробно-линейных задач для выбора подхода к решению поставленной задачи. Предложен подход к решению таких задач н...
Gespeichert in:
| Datum: | 2017 |
|---|---|
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | Russian |
| Veröffentlicht: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2017
|
| Schriftenreihe: | Кибернетика и системный анализ |
| Schlagworte: | |
| Online Zugang: | http://dspace.nbuv.gov.ua/handle/123456789/144778 |
| 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: | Решение экстремальных задач с дробно-линейными функциями цели на комбинаторной конфигурации перестановок при условии многокритериальности / Л.Н. Колечкина, Е.А. Дверная // Кибернетика и системный анализ. — 2017. — Т. 53, № 4. — С. 113–123. — Бібліогр.: 10 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-144778 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1447782019-01-04T01:23:02Z Решение экстремальных задач с дробно-линейными функциями цели на комбинаторной конфигурации перестановок при условии многокритериальности Колечкина, Л.Н. Дверная, Е.А. Системний аналіз Рассмотрена экстремальная задача оптимизации с дробно-линейными функциями цели на комбинаторной конфигурации перестановок при условии многокритериальности. Проанализированы методы решения дробно-линейных задач для выбора подхода к решению поставленной задачи. Предложен подход к решению таких задач на основе теории графов. Описан алгоритм подпрограммы модифицированного координатного метода с оптимизацией поиска точек конфигурации, которая предназначена для формирования множества точек, удовлетворяющих дополнительным ограничениям задачи. Предложен общий алгоритм решения задачи, позволяющий избежать линеаризации функции, и его блок-схема. Приведены примеры работы алгоритма. Розглянуто екстремальну задачу оптимізації з дробово-лінійною функцією цілі на комбінаторній конфігурації переставлень за умови багатокритерійності. Проаналізовано методи розв’язування дробово-лінійних задач для вибору підходу до розв’язування поставленої задачі. Запропоновано підхід до розв’язування таких задач на основі теорії графів. Описано алгоритм підпрограми модифікованого координатного методу з оптимізацією пошуку точок конфігурації, яка призначена для формування множини точок, що задовольняють обмеженням задачі. Запропоновано загальний алгоритм розв’язування задачі, який дозволяє уникнути лінеаризації функції, та його блок-схему. Наведено приклади роботи алгоритму. The authors consider the extremum optimization problem with fractional-linear objective functions on combinatorial configuration of permutations under multicriteria condition. The solution methods for fractional-linear problems are analyzed to choose the approach to problem’s solution. A solution technique based on graph theory is proposed. The algorithm of the modified coordinate method’s subprogram with search optimization is described. This subprogram forms a set of points that satisfy additional constraints of the problem. The general solution algorithm without linearization of the objective function and it’s block diagram are proposed. Examples of the algorithm operation are described. 2017 Article Решение экстремальных задач с дробно-линейными функциями цели на комбинаторной конфигурации перестановок при условии многокритериальности / Л.Н. Колечкина, Е.А. Дверная // Кибернетика и системный анализ. — 2017. — Т. 53, № 4. — С. 113–123. — Бібліогр.: 10 назв. — рос. 0023-1274 http://dspace.nbuv.gov.ua/handle/123456789/144778 519.85 ru Кибернетика и системный анализ Інститут кібернетики ім. В.М. Глушкова НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Системний аналіз Системний аналіз |
| spellingShingle |
Системний аналіз Системний аналіз Колечкина, Л.Н. Дверная, Е.А. Решение экстремальных задач с дробно-линейными функциями цели на комбинаторной конфигурации перестановок при условии многокритериальности Кибернетика и системный анализ |
| description |
Рассмотрена экстремальная задача оптимизации с дробно-линейными функциями цели на комбинаторной конфигурации перестановок при условии многокритериальности. Проанализированы методы решения дробно-линейных задач для выбора подхода к решению поставленной задачи. Предложен подход к решению таких задач на основе теории графов. Описан алгоритм подпрограммы модифицированного координатного метода с оптимизацией поиска точек конфигурации, которая предназначена для формирования множества точек, удовлетворяющих дополнительным ограничениям задачи. Предложен общий алгоритм решения задачи, позволяющий избежать линеаризации функции, и его блок-схема. Приведены примеры работы алгоритма. |
| format |
Article |
| author |
Колечкина, Л.Н. Дверная, Е.А. |
| author_facet |
Колечкина, Л.Н. Дверная, Е.А. |
| author_sort |
Колечкина, Л.Н. |
| title |
Решение экстремальных задач с дробно-линейными функциями цели на комбинаторной конфигурации перестановок при условии многокритериальности |
| title_short |
Решение экстремальных задач с дробно-линейными функциями цели на комбинаторной конфигурации перестановок при условии многокритериальности |
| title_full |
Решение экстремальных задач с дробно-линейными функциями цели на комбинаторной конфигурации перестановок при условии многокритериальности |
| title_fullStr |
Решение экстремальных задач с дробно-линейными функциями цели на комбинаторной конфигурации перестановок при условии многокритериальности |
| title_full_unstemmed |
Решение экстремальных задач с дробно-линейными функциями цели на комбинаторной конфигурации перестановок при условии многокритериальности |
| title_sort |
решение экстремальных задач с дробно-линейными функциями цели на комбинаторной конфигурации перестановок при условии многокритериальности |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| publishDate |
2017 |
| topic_facet |
Системний аналіз |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/144778 |
| citation_txt |
Решение экстремальных задач с дробно-линейными функциями цели на комбинаторной конфигурации перестановок при условии многокритериальности / Л.Н. Колечкина, Е.А. Дверная // Кибернетика и системный анализ. — 2017. — Т. 53, № 4. — С. 113–123. — Бібліогр.: 10 назв. — рос. |
| series |
Кибернетика и системный анализ |
| work_keys_str_mv |
AT kolečkinaln rešenieékstremalʹnyhzadačsdrobnolinejnymifunkciâmicelinakombinatornojkonfiguraciiperestanovokpriusloviimnogokriterialʹnosti AT dvernaâea rešenieékstremalʹnyhzadačsdrobnolinejnymifunkciâmicelinakombinatornojkonfiguraciiperestanovokpriusloviimnogokriterialʹnosti |
| first_indexed |
2025-07-10T20:07:36Z |
| last_indexed |
2025-07-10T20:07:36Z |
| _version_ |
1837291871685050368 |
| fulltext |
ÓÄÊ 519.85
Ë.Í. ÊÎËÅ×ÊÈÍÀ, Å.À. ÄÂÅÐÍÀß
ÐÅØÅÍÈÅ ÝÊÑÒÐÅÌÀËÜÍÛÕ ÇÀÄÀ× Ñ ÄÐÎÁÍÎ-ËÈÍÅÉÍÛÌÈ
ÔÓÍÊÖÈßÌÈ ÖÅËÈ ÍÀ ÊÎÌÁÈÍÀÒÎÐÍÎÉ ÊÎÍÔÈÃÓÐÀÖÈÈ
ÏÅÐÅÑÒÀÍÎÂÎÊ ÏÐÈ ÓÑËÎÂÈÈ ÌÍÎÃÎÊÐÈÒÅÐÈÀËÜÍÎÑÒÈ
Àííîòàöèÿ. Ðàññìîòðåíà ýêñòðåìàëüíàÿ çàäà÷à îïòèìèçàöèè ñ äðîáíî-ëèíåé-
íûìè ôóíêöèÿìè öåëè íà êîìáèíàòîðíîé êîíôèãóðàöèè ïåðåñòàíîâîê ïðè
óñëîâèè ìíîãîêðèòåðèàëüíîñòè. Ïðîàíàëèçèðîâàíû ìåòîäû ðåøåíèÿ äðîáíî-
ëèíåéíûõ çàäà÷ äëÿ âûáîðà ïîäõîäà ê ðåøåíèþ ïîñòàâëåííîé çàäà÷è. Ïðåäëî-
æåí ïîäõîä ê ðåøåíèþ òàêèõ çàäà÷ íà îñíîâå òåîðèè ãðàôîâ. Îïèñàí àëãî-
ðèòì ïîäïðîãðàììû ìîäèôèöèðîâàííîãî êîîðäèíàòíîãî ìåòîäà ñ îïòèìèçàöè-
åé ïîèñêà òî÷åê êîíôèãóðàöèè, êîòîðàÿ ïðåäíàçíà÷åíà äëÿ ôîðìèðîâàíèÿ ìíî-
æåñòâà òî÷åê, óäîâëåòâîðÿþùèõ äîïîëíèòåëüíûì îãðàíè÷åíèÿì çàäà÷è.
Ïðåäëîæåí îáùèé àëãîðèòì ðåøåíèÿ çàäà÷è, ïîçâîëÿþùèé èçáåæàòü ëèíåàðè-
çàöèè ôóíêöèè, è åãî áëîê-ñõåìà. Ïðèâåäåíû ïðèìåðû ðàáîòû àëãîðèòìà.
Êëþ÷åâûå ñëîâà: ýêñòðåìàëüíûå çàäà÷è, êîìáèíàòîðíûå êîíôèãóðàöèè,
äðîáíî-ëèíåéíûå ôóíêöèè, óñëîâèå ìíîãîêðèòåðèàëüíîñòè, ìîäèôèöèðîâàí-
íûé êîîðäèíàòíûé ìåòîä, îïòèìèçàöèÿ ïîèñêà.
ÂÂÅÄÅÍÈÅ
Ìíîãîçàäà÷íîñòü áîëüøèíñòâà ñîâðåìåííûõ íàó÷íûõ ïðîáëåì, îòðàæàþùèõ
ïðàêòè÷åñêóþ äåÿòåëüíîñòü ïðîèçâîäñòâ è îðãàíèçàöèé, ñâÿçàíà ñ âåêòîðíîé
îïòèìèçàöèåé, èññëåäîâàííîé â [1, 5–10]. Ðàçðàáîòàíû ïîäõîäû ê ðåøåíèþ
âåêòîðíûõ çàäà÷, íàïðèìåð, ñ èñïîëüçîâàíèåì ãåíåòè÷åñêèõ àëãîðèòìîâ [1],
ñâîéñòâ ìíîæåñòâ, íà êîòîðûõ ðåøàåòñÿ çàäà÷à [5–9], äèàëîãîâûõ ïðîöåäóð,
ðàçëè÷íûõ êðèòåðèåâ îïðåäåëåíèÿ îïòèìàëüíîñòè ïîëó÷åííîãî ðåøåíèÿ [10]
è ò.ä. Âèä öåëåâûõ ôóíêöèé çàäà÷è è ìíîæåñòâî äîïóñòèìûõ ðåøåíèé èìåþò
áîëüøîå çíà÷åíèå ïðè âûáîðå ìåòîäà åå ðåøåíèÿ.
Ïðè ïîñòðîåíèè ìîäåëåé ýêîíîìè÷åñêèõ è òåõíè÷åñêèõ ïðîöåññîâ, ñâÿçàí-
íûõ ñ ïëàíèðîâàíèåì äåÿòåëüíîñòè êîìïàíèè, óïðàâëåíèåì ñòàòüÿìè áàíêîâñêî-
ãî áàëàíñà, îöåíêîé òðàíñïîðòíûõ ïåðåâîçîê, óïðàâëåíèåì äåÿòåëüíîñòüþ óíè-
âåðñèòåòîâ è ò.ä., âîçíèêàåò íåîáõîäèìîñòü â îïòèìèçàöèè íåêîòîðîãî îòíîñè-
òåëüíîãî ïîêàçàòåëÿ, êîòîðûé ìîæíî ïðåäñòàâèòü äðîáíî-ëèíåéíîé ôóíêöèåé
öåëè. Åñëè îáëàñòü äîïóñòèìûõ çíà÷åíèé òàêèõ ïðèêëàäíûõ çàäà÷ èìååò ñâîé-
ñòâà êîìáèíàòîðíîé êîíôèãóðàöèè, òî ðàññìàòðèâàåòñÿ ýêñòðåìàëüíàÿ êîìáèíà-
òîðíàÿ çàäà÷à, èññëåäîâàííàÿ â [2–9]. Äàííàÿ çàäà÷à â ñî÷åòàíèè ñ âåêòîðíîé
îïòèìèçàöèåé ïðèâîäèò ê óñëîâèþ ìíîãîêðèòåðèàëüíîñòè äëÿ çàäà÷è ñ äðîá-
íî-ëèíåéíûìè öåëåâûìè ôóíêöèÿìè.
ÏÎÑÒÀÍÎÂÊÀ ÝÊÑÒÐÅÌÀËÜÍÎÉ ÇÀÄÀ×È Ñ ÄÐÎÁÍÎ-ËÈÍÅÉÍÛÌÈ ÔÓÍÊÖÈßÌÈ
ÖÅËÈ ÏÐÈ ÓÑËÎÂÈÈ ÌÍÎÃÎÊÐÈÒÅÐÈÀËÜÍÎÑÒÈ
Ñôîðìóëèðóåì çàäà÷ó ñëåäóþùèì îáðàçîì: íàéòè òàêîå x D X� � � , ÷òî
x F x
x D X
�
� �
� arg extr ( ), (1)
ãäå F f f f n( , , , )1 2 � — âåêòîðíûé êðèòåðèé, êîòîðûé ñîñòîèò èç äðîáíî-ëè-
íåéíûõ ôóíêöèé öåëè
f
c x c
d x d
i N j Ni
x D X
ij j
j
m
ij j
j
m n m�
�
�
� �
� �
�
�
�
�
extr
0
1
0
1
, , , (2)
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 4 113
© Ë.Í. Êîëå÷êèíà, Å.À. Äâåðíàÿ, 2017
ïðè óñëîâèè d x dij j
j
m
� �
�
� 0
1
0, i N n� , j N m� ; D X� — ïîäìíîæåñòâî äîïóñ-
òèìûõ ðåøåíèé çàäà÷è, êîòîðîå ôîðìèðóåòñÿ èç ñèñòåìû äîïîëíèòåëüíûõ ëè-
íåéíûõ îãðàíè÷åíèé âèäà
a x b i N t Nit j t m k � �, , ; (3)
X — íåêàÿ êîìáèíàòîðíàÿ êîíôèãóðàöèÿ;
extr { }� min, max (4)
ÿâëÿåòñÿ íàïðàâëåíèåì îïòèìèçàöèè; n — êîëè÷åñòâî ôóíêöèé; m — êîëè÷å-
ñòâî ïåðåìåííûõ; k — êîëè÷åñòâî îãðàíè÷åíèé çàäà÷è.
Çàäà÷à (1)–(4) âåêòîðíàÿ, ñ äðîáíî-ëèíåéíûìè ôóíêöèÿìè öåëè íà êîìáèíà-
òîðíîì ìíîæåñòâå. Äëÿ âûáîðà ìåòîäà ðåøåíèé ïîñòàâëåííîé çàäà÷è ðàññìîò-
ðèì óæå ñóùåñòâóþùèå ïîäõîäû, íî àäàïòèðîâàííûå èìåííî äëÿ çàäà÷ ìíîãî-
êðèòåðèàëüíîé îïòèìèçàöèè.
ÂÛÁÎÐ ÏÎÄÕÎÄÀ Ê ÐÅØÅÍÈÞ ÊÎÌÁÈÍÀÒÎÐÍÎÉ ÇÀÄÀ×È Ñ ÄÐÎÁÍÎ-ËÈÍÅÉÍÎÉ
ÔÓÍÊÖÈÅÉ ÖÅËÈ ÏÐÈ ÓÑËÎÂÈÈ ÌÍÎÃÎÊÐÈÒÅÐÈÀËÜÍÎÑÒÈ
Ïðè ðåøåíèè çàäà÷ ñ äðîáíî-ëèíåéíûìè ôóíêöèÿìè ÷àùå èñïîëüçóþò ìåòîä
ïðåîáðàçîâàíèÿ ïåðåìåííûõ, êîòîðûé ñâîäèò ïåðâîíà÷àëüíóþ çàäà÷ó ê ëèíåé-
íîé (ëèíåàðèçàöèÿ). Ïðè ýòîì êîëè÷åñòâî ïåðåìåííûõ óâåëè÷èâàåòñÿ, ÷òî ïðè-
âîäèò ê ïðåîáðàçîâàíèþ äîïîëíèòåëüíûõ îãðàíè÷åíèé çàäà÷è.  ñëó÷àå êîì-
áèíàòîðíîé îïòèìèçàöèè òðåáóåòñÿ îòîáðàæåíèå çàäàííîé êîíôèãóðàöèè. Ïðè
âîçíèêíîâåíèè óñëîâèÿ ìíîãîêðèòåðèàëüíîñòè çàäà÷à ïðåîáðàçîâàíèÿ ïåðå-
ìåííûõ çíà÷èòåëüíî óñëîæíÿåòñÿ, ïîñêîëüêó çíàìåíàòåëè öåëåâûõ ôóíêöèé
ðàçíûå è îáùåïðèíÿòûå ôîðìóëû äëÿ ëèíåàðèçàöèè íåëüçÿ èñïîëüçîâàòü äëÿ
âñåõ êðèòåðèåâ îäíîâðåìåííî.
Ïðèìåíÿþò òàêæå ìåòîä îáíîâëåíèÿ öåëåâîé ôóíêöèè, êîòîðûé ïðåäóñìàò-
ðèâàåò ïåðèîäè÷åñêèé ïåðåñ÷åò ëîêàëüíîãî ãðàäèåíòà äðîáíî-ëèíåéíîé ôóíê-
öèè è ñâîäèò çàäà÷ó äðîáíî-ëèíåéíîãî ïðîãðàììèðîâàíèÿ ê ïîñëåäîâàòåëüíîñòè
ëèíåéíûõ çàäà÷ [10]. Äàííûé ìåòîä ðàçðàáîòàí äëÿ îäíîêðèòåðèàëüíîé îïòèìè-
çàöèè, ïðè óâåëè÷åíèè êîëè÷åñòâà ïåðåìåííûõ è âîçíèêíîâåíèè óñëîâèÿ ìíî-
ãîêðèòåðèàëüíîñòè âîçðàñòàåò åãî âû÷èñëèòåëüíàÿ ñëîæíîñòü è ïîÿâëÿåòñÿ íåîá-
õîäèìîñòü ìîäèôèêàöèè.
 ðàáîòå [4] ïðåäñòàâëåí ìåòîä ðåøåíèÿ çàäà÷ îïòèìèçàöèè ñ äðîáíî-ëèíåé-
íîé ôóíêöèåé íà ìíîæåñòâå ïåðåñòàíîâîê, îñíîâàííûé íà ìåòîäå êîìáèíàòîðíî-
ãî îòñå÷åíèÿ. Ïðåèìóùåñòâîì äàííîãî ìåòîäà ÿâëÿåòñÿ åãî ïðàêòè÷åñêàÿ ýôôåê-
òèâíîñòü äëÿ óêàçàííîãî êëàññà çàäà÷, à òàêæå èñïîëüçîâàíèå äðîáíî-ëèíåéíîé
ôóíêöèè ïðè ñâåäåíèè âåêòîðíûõ çàäà÷ ê ñêàëÿðíûì. Äàííûé ìåòîä ïðèìåíÿåò-
ñÿ äëÿ îäíîêðèòåðèàëüíîé îïòèìèçàöèè, à òàêæå èñïîëüçóåò ìåòîä ëèíåàðèçà-
öèè, ïîýòîìó ïðè âîçíèêíîâåíèè óñëîâèÿ ìíîãîêðèòåðèàëüíîñòè ïðèâîäèò ê òåì
æå ïðîáëåìàì, ÷òî è â ìåòîäå ïðåîáðàçîâàíèÿ ïåðåìåííûõ.
Òàêèì îáðàçîì, î÷åâèäíî, ÷òî ïîèñê óíèâåðñàëüíîãî àëãîðèòìà ðåøåíèÿ
êîìáèíàòîðíûõ âåêòîðíûõ äðîáíî-ëèíåéíûõ çàäà÷ ÿâëÿåòñÿ ïåðñïåêòèâíîé îá-
ëàñòüþ äëÿ èññëåäîâàíèÿ. Ñî÷åòàíèå ìíîãîêðèòåðèàëüíîñòè è êîìáèíàòîðíûõ
ñâîéñòâ óñëîæíÿåò çàäà÷ó, è äëÿ ðåøåíèÿ ìîäåëåé òàêèõ çàäà÷ íåîáõîäèìû
ñïåöèôè÷åñêèå ïîäõîäû.
 äàííîé ðàáîòå ïðåäëàãàåòñÿ èñïîëüçîâàòü ìîäèôèöèðîâàííûé êîîðäèíàò-
íûé ìåòîä, ïðèìåíÿåìûé ðàíåå ê ëèíåéíûì çàäà÷àì [3, 6]. Ýòîò ïîäõîä íå òðå-
áóåò âûïîëíåíèÿ ïðåîáðàçîâàíèé äðîáíî-ëèíåéíûõ êðèòåðèåâ â ëèíåéíûå, ïî-
ñêîëüêó ðàáîòàåò íåïîñðåäñòâåííî ñ ñèñòåìîé îãðàíè÷åíèé. Îí ïîçâîëÿåò îïðå-
äåëÿòü òîëüêî òå òî÷êè êîìáèíàòîðíîé êîíôèãóðàöèè, êîòîðûå óäîâëåòâîðÿþò
äîïîëíèòåëüíûì óñëîâèÿì çàäà÷è. Ìíîæåñòâî ðåøåíèé çàäà÷è ôîðìèðóåòñÿ
114 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 4
ñðàâíåíèåì çíà÷åíèé êðèòåðèÿ îïòèìàëüíîñòè â íàéäåííûõ òî÷êàõ çàäàííîé
êîíôèãóðàöèè, êîòîðûå óäîâëåòâîðÿþò ëèíåéíûì îãðàíè÷åíèÿì çàäà÷è.
Óñëîâèå ìíîãîêðèòåðèàëüíîñòè â çàäà÷àõ ñîïðÿæåíî ñ ðÿäîì ñëîæíîñòåé,
ïîñêîëüêó êðèòåðèè îïòèìàëüíîñòè çà÷àñòóþ ïðîòèâîðå÷èâû. Ïðè ðàçðàáîòêå
ìåòîäîâ âåêòîðíîé îïòèìèçàöèè âàæåí îòâåò íà âîïðîñ î òîì, êàêèå èìåííî ðå-
øåíèÿ íàõîäÿòñÿ â ðåçóëüòàòå åãî ïðèìåíåíèÿ. Êàê ïðàâèëî, ðåøåíèÿ ïðèíàäëå-
æàò îäíîìó èç ñëåäóþùèõ ìíîæåñòâ:
— îïòèìàëüíûõ ïî Ïàðåòî ýôôåêòèâíûõ ðåøåíèé P F X x X( , ) :� �{
�( , )x X �
}, �( , ) : ( ) ( ), ( ) ( )x X y X F y F x F y F x� � � �{ } (ïàðåòîâñêîå ìíîæåñ-
òâî). Ýòî ìíîæåñòâî ñîñòîèò èç ðåøåíèé, êîòîðûå íå ìîãóò óëó÷øèòü õîòÿ áû
îäèí èç êðèòåðèåâ, íå óõóäøèâ ïðè ýòîì äðóãîé;
— ñëàáî ýôôåêòèâíûõ ðåøåíèé (ìíîæåñòâî Ñëåéòåðà) Sl F X x X( , ) :� �{
�( , )x X �
}, �( , ) : ( ) ( )x X y X F y F x� � �{ };
— ñòðîãî ýôôåêòèâíûõ ðåøåíèé (ìíîæåñòâî Ñìåéëà) Sm F X x X( , ) :� �{
�( , )x X �
}, �( , ) \ : ( ) ( )x X y X x F y F x� � �{ { } }.
Äëÿ îïèñàííûõ ìíîæåñòâ î÷åâèäíî, ÷òî Sm F X P F X Sl F X( , ) ( , ) ( , )
[8].
Ïðåäëîæåííûé àëãîðèòì âêëþ÷àåò ýòàï ïîäáîðà âåñîâûõ êîýôôèöèåíòîâ íà
îñíîâå ýêñïåðòíûõ îöåíîê � ij , i j N n, � , îïèñûâàþùèõ ñîîòíîøåíèÿ âàæíîñòè öå-
ëåâûõ ôóíêöèé. Ïîñêîëüêó ýêñïåðòû îïðåäåëÿþò ïðåâîñõîäñòâî èëè ðàâåíñòâî âõî-
äÿùèõ â âåêòîðíûé êðèòåðèé ôóíêöèé, íà îñíîâàíèè ýòèõ äàííûõ ôîðìèðóåòñÿ
ìíîæåñòâî ðåøåíèé, êîòîðûå íåëüçÿ óëó÷øèòü, òàê êàê óëó÷øåíèå ïî îäíîé èç
ôóíêöèé íåèçìåííî âëå÷åò óõóäøåíèå ïî äðóãîé ôóíêöèè âåêòîðíîãî êðèòåðèÿ
îïòèìàëüíîñòè. Òàêèì îáðàçîì, ôîðìèðóåòñÿ ìíîæåñòâî îïòèìàëüíûõ ïî Ïàðåòî
ðåøåíèé x F x P F X
x D X
�
� �
� �arg extr ( ) ( , ), ò.å. íàéäåííîå ðåøåíèå èëè ìíîæåñòâî
ðåøåíèé áóäóò ýôôåêòèâíûìè äëÿ ðàññìàòðèâàåìîé â äàííîé ðàáîòå çàäà÷è.
ÀËÃÎÐÈÒÌÛ ÐÅØÅÍÈß ÇÀÄÀ×È
Äëÿ ðàáîòû àëãîðèòìà ðåøåíèÿ çàäà÷è (1)–(4) èñïîëüçóåòñÿ ïîäïðîãðàììà,
îñíîâàííàÿ íà ìîäèôèöèðîâàííîì êîîðäèíàòíîì ìåòîäå [6] ñ îïòèìèçàöèåé
ïîèñêà, àëãîðèòì êîòîðîé ïðèâåäåí äàëåå. Äëÿ ïðåäñòàâëåíèÿ àëãîðèòìà ïîä-
ïðîãðàììû íåîáõîäèìû ñëåäóþùèå ïîñíåíèÿ.
Ñâîéñòâà òî÷åê, îïðåäåëÿþùèõ ýëåìåíòû êîìáèíàòîðíûõ êîíôèãóðàöèé, ïî-
çâîëÿþò ðàçëîæèòü ãðàô çàäàííîé êîíôèãóðàöèè íà ïîäãðàôû, êîòîðûå ìîæíî
ïðåäñòàâèòü â âèäå ñõåì. Äëÿ ýòîãî ïîñëåäîâàòåëüíî âûáèðàåòñÿ îäèí èç øåñòè
òèïîâ âåðøèí, äëÿ îïðåäåëåíèÿ ïîñëåäíèõ èñïîëüçóåòñÿ ãðàô êîíôèãóðàöèè ïåðå-
ñòàíîâîê ðàçìåðíîñòè 3. Êîãäà ýëåìåíòû óïîðÿäî÷åíû, çíà÷åíèå ôóíêöèè íà
îïðåäåëåííîì ïîäãðàôå íàõîäèòñÿ ìåæäó çíà÷åíèÿìè â êðàéíèõ âåðøèíàõ ñõåìû.
Ãðàô — ýòî ñåòü, ãäå èñòîêîì (ãëàâíîé âåðøèíîé) ÿâëÿåòñÿ âåðõíÿÿ ëåâàÿ, à ñòî-
êîì — íèæíÿÿ ïðàâàÿ âåðøèíà. Òàêèì îáðàçîì, çíà÷åíèå ôóíêöèè â ãëàâíîé âåð-
øèíå äëÿ çàäàííîãî òèïà âåðøèíû è çàôèêñèðîâàííîé êîîðäèíàòû áóäåò ìàêñè-
ìàëüíûì, à â òî÷êå ñòîêà — ìèíèìàëüíûì äëÿ ïîñòðîåííîé ñåòè. Ïðàâèëà ïîñòðî-
åíèÿ ñõåì ïîäãðàôîâ äåòàëüíî ðàññìîòðåíû â [3, 6].
Àëãîðèòì ïîäïðîãðàììû ìîäèôèöèðîâàííîãî êîîðäèíàòíîãî ìåòîäà
ñ îïòèìèçàöèåé ïîèñêà.
Øàã 1. Çàäàòü íà÷àëüíûå çíà÷åíèÿ ïåðåìåííûì: t �1, k �1, i �1.
Øàã 2. Çàôèêñèðîâàòü òèï âåðøèíû � t i i i� ( , , )1 2 3 , ãäå i i i1 2 3 1 2 3� � � { }, , ,
i — íîìåð ïîäãðàôà.
Øàã 3. Îïðåäåëèòü çíà÷åíèÿ: x is � , x N xs s s� �1 max \{ }, xs� �2
� � �� �max \ ( , ) , , max \ ( , , , ){ } { }N x x x N x x xs s s s s s1 4 1 5� . ×èñëà { }N x x xs s s\ ( , , , )�1 4� óïî-
ðÿäî÷èòü ïî âîçðàñòàíèþ j j j1 2 3� � . Òîãäà x ji1 1
� , x ji2 2
� , x ji3 3
� — êîä ãëàâ-
íîé âåðøèíû, êîòîðóþ îáîçíà÷èì p1. Âû÷èñëèòü f p( )1 .
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 4 115
Øàã 4. Îïðåäåëèòü çíà÷åíèÿ: x is � , x N xs s s� �1 min \{ }, xs� �2
� � �� �min \ ( , ) , , min \ ( , , , ){ } { }N x x x N x x xs s s s s s1 4 1 5� . ×èñëà { }N x x xs s s\ ( , , , )�1 4�
óïîðÿäî÷èòü ïî âîçðàñòàíèþ j j j1 2 3� � . Òîãäà x ji1 1
� , x ji2 2
� , x ji3 3
� — êîä
ïðàâîé íèæíåé âåðøèíû (ñòîêà), êîòîðóþ îáîçíà÷èì pst1. Âû÷èñëèòü f pst( )1 .
Øàã 5. Îïòèìèçàöèÿ ïîèñêà: îïðåäåëèòü íàïðàâëåíèÿ ïîèñêà â ïîñòðîåííîé
ñåòè, êîòîðîå ïîçâîëèò óìåíüøèòü êîëè÷åñòâî îïåðàöèé, ñðàâíèâ çíà÷åíèÿ f p( )1
è f pst( )1 ñ çàäàííûì y� ïî ïðàâèëó, åñëè f p y y f p( ) ( )1 1� �� � , òî ïðîâåñòè
ïîèñê îò ãëàâíîé âåðøèíû ê ñòîêó (ïåðåéòè ê øàãó 6), èíà÷å — îò ñòîêà ê ãëàâ-
íîé âåðøèíå (ïåðåéòè ê øàãó 7).
Øàã 6. Ðàññìîòðåòü è óïîðÿäî÷èòü ïî óáûâàíèþ çíà÷åíèÿ x k Nk k, � :
j j jk k� � ��1 1� . Ðàçâåðíóòü ãðàô â íàïðàâëåíèè êîîðäèíàòû xk , âûïîëíèâ ïî-
ñëåäîâàòåëüíîñòü òðàíñïîçèöèé: j j jk k� � ��1 1� , êîòîðûå ïðèâîäÿò ê îáðà-
çîâàíèþ åùå k �1 êîäîâ âåðøèí p p pk2 3, , ,� . Ýòè êîäû âåðøèí ÿâëÿþòñÿ êîäà-
ìè óçëîâ âåðõíåé ëèíèè ñõåìû. Ïåðåéòè ê øàãó 8.
Øàã 7. Ðàññìîòðåòü è óïîðÿäî÷èòü ïî âîçðàñòàíèþ çíà÷åíèÿ x k Nk k, � .
Ðàçâåðíóòü ãðàô â íàïðàâëåíèè êîîðäèíàòû xk , âûïîëíèâ ïîñëåäîâàòåëüíîñòü
òðàíñïîçèöèé: j j jk k1 1� � ��� , êîòîðûå ïðèâîäÿò ê îáðàçîâàíèþ åùå k �1
êîäîâ âåðøèí p p pst st stk2 3, , ,� . Ýòè êîäû âåðøèí ÿâëÿþòñÿ êîäàìè óçëîâ íèæ-
íåé ëèíèè ñõåìû.
Øàã 8. Íàéòè çíà÷åíèå ôóíêöèè íà ýòèõ ïåðåñòàíîâêàõ, èñïîëüçîâàâ èõ êî-
îðäèíàòû f p f pn n n( ) ( )� �� �1 1� , � n n n n nj j c c� � �� � �1 1 1( )( )( )� , ãäå � �( ) —
íîìåð ìåñòà ÷èñëà j� â êîäå ïåðåñòàíîâêè pn�1.
Øàã 9. Ïðîâåðèòü âûïîëíåíèå ñëåäóþùèõ óñëîâèé:
à) åñëè f p ym( ) � � (èñêîìûå çíà÷åíèÿ ñóùåñòâóþò â ïîñòðîåííîì ïîäãðà-
ôå), òî âêëþ÷àåì m-þ ïåðåñòàíîâêó â ïîñëåäóþùèé ïîèñê. Ïåðåéòè ê øàãó 10
äëÿ äàëüíåéøåãî ðàññìîòðåíèÿ;
á) åñëè äëÿ âñåõ íàéäåííûõ êîäîâ f p ym( )� � è i � 1 1 (èñêîìûõ çíà÷åíèé
íå ñóùåñòâóåò â ïîñòðîåííîì ïîäãðàôå, íî íå âñå âîçìîæíûå ôèêñèðîâàííûå êî-
îðäèíàòû äëÿ âûáðàííîãî òèïà âåðøèí ðàññìàòðèâàëèñü), òî ïåðåéòè ê ïîä-
ãðàôàì ñî ñëåäóþùåé ôèêñèðîâàííîé êîîðäèíàòîé x is � , ïîñëå ÷åãî ïåðåéòè
ê øàãó 2;
â) åñëè äëÿ âñåõ íàéäåííûõ êîäîâ f p ym( )� � è i � �1 0 (èñêîìûõ çíà÷åíèé
íå ñóùåñòâóåò â ïîñòðîåííîì ïîäãðàôå, è âñå âîçìîæíûå ôèêñèðîâàííûå êîîð-
äèíàòû äëÿ âûáðàííîãî òèïà âåðøèí ðàññìàòðèâàëèñü), òî ïðèñâîèòü i � 6 è ïå-
ðåéòè ê ïîäãðàôàì ñ òèïîì âåðøèí � t�1, ïîñëå ÷åãî ïåðåéòè ê øàãó 9 ã);
ã) åñëè t � 1 6 (íå âñå òèïû âåðøèí ðàññìàòðèâàëèñü), ïåðåéòè ê øàãó 2,
èíà÷å (äëÿ âñåõ øåñòè òèïîâ âåðøèí óæå ïîñòðîåíû ïîäãðàôû) çàâåðøèòü ðîáî-
òó àëãîðèòìà äëÿ äàííîãî îãðàíè÷åíèÿ.
Øàã 10. Óâåëè÷èòü k íà åäèíèöó. Åñëè k s� , òî ïåðåéòè ê øàãó 11, èíà÷å ïå-
ðåéòè ê ðàññìîòðåíèþ ïîäãðàôîâ ñî ñëåäóþùåé ôèêñèðîâàííîé êîîðäèíàòîé
x is � , ò.å. ê øàãó 2. Åñëè i � �1 0, òî ïðèñâîèòü i � 6 è ïåðåéòè ê ðàññìîòðåíèþ
ïîäãðàôîâ ñ òèïîì âåðøèí � t�1 ïðè óñëîâèè, ÷òî t � 1 6 (ïåðåéòè ê øàãó 2),
èíà÷å çàâåðøèòü ðîáîòó àëãîðèòìà äëÿ äàííîãî îãðàíè÷åíèÿ.
Øàã 11. Ðàññìîòðåòü è óïîðÿäî÷èòü ïî óáûâàíèþ çíà÷åíèÿ x k Nk k, � :
j j jk k� � ��1 1� . Ðàçâåðíóòü ãðàô âäîëü êîîðäèíàòû xk , âûïîëíèâ ïîñëåäîâà-
òåëüíîñòü òðàíñïîçèöèé: j j jk k� � ��1 1� , êîòîðûå ïðèâîäÿò ê îáðàçîâàíèþ
åùå k �1 êîäîâ âåðøèí q q qk2 3, , ,� .
Øàã 12. Íàéòè çíà÷åíèå ôóíêöèè íà ýòèõ ïåðåñòàíîâêàõ, èñïîëüçîâàâ èõ êî-
îðäèíàòû f q f qn n n( ) ( )� �� �1 1� , � �n n n n nj j c c� � �� � �1 1 1( )( )( ) , ãäå � �( ) — íî-
ìåð ìåñòà ÷èñëà j� â êîäå ïåðåñòàíîâêè qn�1.
116 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 4
Øàã 13. Åñëè f q yn( ) * , òî çàïîìíèòü êîä âåðøèíû qn . Ïåðåéòè ê øàãó 10 —
ðàçâîðà÷èâàíèþ íîâîãî êîäà.
Äàííûé àëãîðèòì îòëè÷àåòñÿ îò îïèñàííîãî â ðàáîòàõ [3, 6] ýòàïîì îïòèìè-
çàöèè ïîèñêà, ïîçâîëÿþùèì óìåíüøèòü êîëè÷åñòâî ðàñ÷åòîâ, ÷òî ïðè çíà÷èòåëü-
íîé ðàçìåðíîñòè çàäà÷è ÿâëÿåòñÿ âåñîìûì âêëàäîì â ýêîíîìèþ ðåñóðñîâ. Îïè-
øåì îñíîâíîé àëãîðèòì ðåøåíèÿ ïîñòàâëåííîé çàäà÷è.
Àëãîðèòì ìîäèôèöèðîâàííîãî êîîðäèíàòíîãî ìåòîäà äëÿ ðåøåíèÿ âåê-
òîðíûõ çàäà÷ ñ äðîáíî-ëèíåéíîé ôóíêöèåé.
Øàã 1. Ââåñòè âõîäíûå äàííûå çàäà÷è (1)–(4): êîýôôèöèåíòû öåëåâûõ
ôóíêöèé, äîïîëíèòåëüíûõ îãðàíè÷åíèé, ýëåìåíòû êîìáèíàòîðíîé êîíôèãóðà-
öèè, ýêñïåðòíûå îöåíêè ïðåèìóùåñòâà êðèòåðèåâ îïòèìàëüíîñòè.
Øàã 2. Ñôîðìèðîâàòü ýëåìåíòû êîìáèíàòîðíîé êîíôèãóðàöèè.
Øàã 3. Äëÿ êàæäîãî èç k îãðàíè÷åíèé íàéòè ñîîòâåòñòâóþùèå åìó òî÷êè
êîíôèãóðàöèè ïåðåñòàíîâîê, èñïîëüçîâàâ ïîäïðîãðàììó ìîäèôèöèðîâàííîãî
êîîðäèíàòíîãî ìåòîäà ñ îïòèìèçàöèåé ïîèñêà, ÷òîáû ïîëó÷èòü k ïîäìíîæåñòâ
D Xi
, ãäå i N k� ìíîæåñòâà D * äîïóñòèìûõ ðåøåíèé.
Øàã 4. Íàéòè ïåðåñå÷åíèå D D D Dk
* � � � �1 2 � .
Øàã 5. Âû÷èñëèòü âåñîâûå êîýôôèöèåíòû íîâîãî êðèòåðèÿ îïòèìàëüíîñòè
ïî ôîðìóëå
�
�
i
s
m
is
r
m
s
m
rs
ni N� ��
� �
�
� �
1
1 1
, , ãäå � �is rs, — çàäàííûå â øàãå 1 ýêñïåðòíûå
îöåíêè.
Øàã 6. Ïåðåéòè îò âåêòîðíîãî êðèòåðèÿ ê îäíîêðèòåðèàëüíîé äðîáíî-ëè-
íåéíîé ôóíêöèè â âèäå f fi
k
i
i
k
�
�
� ��
1
extr .
Øàã 7. Âû÷èñëèòü çíà÷åíèå ôóíêöèè f � â òî÷êàõ x D� � .
Øàã 8. Ñðàâíèòü ïîëó÷åííûå íà øàãå 7 çíà÷åíèÿ, âûáðàâ ñîîòâåòñòâóþùåå
íàïðàâëåíèå îïòèìèçàöèè. Îïðåäåëèòü ýêñòðåìàëüíîå çíà÷åíèå èëè äîïóñòèìûå
çíà÷åíèÿ ôóíêöèè öåëè.
Øàã 9. Íàéòè çíà÷åíèå äðîáíî-ëèíåéíûõ ôóíêöèé, ñîñòàâëÿþùèõ âåêòîð-
íûé êðèòåðèé. Çàâåðøèòü ðàáîòó àëãîðèòìà.
Îïèñàííûé àëãîðèòì ïðåäñòàâèì â âèäå áëîê-ñõåìû (ðèñ. 1).
Ðàññìîòðèì ïðèìåðû ðåøåíèÿ çàäà÷ c ïîìîùüþ îïèñàííîãî àëãîðèòìà. Âñå
êîýôôèöèåíòû â ïðèâåäåííûõ äàëåå çàäà÷àõ âûáèðàëèñü ïðîèçâîëüíî.
Ïðèìåð 1. Íàéòè òàêèå çíà÷åíèÿ x X� � , ãäå X — ìíîæåñòâî ïåðåñòàíîâîê
èç ýëåìåíòîâ À � ( , , , , , )1 2 3 4 5 6 , êîòîðûå ÿâëÿþòñÿ îïòèìàëüíûìè äëÿ ðàâíîâåñ-
íûõ ôóíêöèé
f x
x x x x x x
x x x x x x
1
1 2 3 4 5 6
1 2 3 4 5 6
2 3 5 6 2
( ) max�
� � � � �
� � � � �
� ,
f x
x x x x x x
x x x x x x
2
1 2 3 4 5 6
1 2 3 4 5 6
2 3 4 2 3
( ) max�
� � � � �
� � � � �
� ,
f x
x x x x x x
x x x x x x
3
1 2 3 4 5 6
1 2 3 4 5 6
3 7 2 3 4
( ) max�
� � � � �
� � � � �
�
ïðè îãðàíè÷åíèÿõ
3 5 6 9 11 18 150
5 7 21 12 10
1 2 3 4 5 6
1 2 3 4
x x x x x x
x x x x
� � � � �
� � � �
,
x x5 62 247�
�
�
� .
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 4 117
Ðåøåíèå. Ðàññìîòðèì ïåðâîå îãðàíè÷åíèå 3 5 6 9 111 2 3 4 5x x x x x� � � � �
� 18 1506x . Íàéäåì ìàêñèìàëüíûå è ìèíèìàëüíûå çíà÷åíèÿ ôóíêöèè
g x x x x x x1 1 2 3 4 5 63 5 6 9 11 18� � � � � � â ïîäãðàôàõ, ïîñëåäîâàòåëüíî çàêðåïèâ
êîîðäèíàòó x6 , ïðîàíàëèçèðóåì ðåçóëüòàò (òàáë. 1).
Êàê âèäíî èç òàáë. 1, òî÷êè äîñòèæåíèÿ ìàêñèìóìà è ìèíèìóìà ôóíêöèè
ïðè çàêðåïëåííîé êîîðäèíàòå x6 îáðàçóþòñÿ ïåðåñòàíîâêîé äâóõ ýëåìåíòîâ. Ýòî
ïîçâîëÿåò èñïîëüçîâàòü ôîðìóëó êîîðäèíàòíîãî ìåòîäà íàõîæäåíèÿ èõ çíà÷åíèé
f q f qn n n( ) ( )� �� �1 1� , � �n n n n nj j c c� � �� � �1 1 1( )( )( ) , ãäå � �( ) — íîìåð ìåñòà
÷èñëà j� â êîäå ïåðåñòàíîâêè qn�1. Î÷åâèäíî, ÷òî ìèíèìàëüíûå çíà÷åíèÿ ôóíê-
öèè g1 áîëüøå 150 äëÿ x6 4 5 6� { }, , (ñì. òàáë. 1). Òàêèì îáðàçîì, ìîæíî îòáðî-
ñèòü âñå òî÷êè êîíôèãóðàöèè ïåðåñòàíîâîê, êîòîðûå èìåþò ñîîòâåòñòâóþùóþ
êîîðäèíàòó x6 .
Ïåðåéäåì ê äåòàëüíîìó ðàññìîòðåíèþ îñòàëüíûõ òî÷åê. Çàêðåïèì x6 3� ,
îïðåäåëèì òèï âåðøèíû (123). Íàéäåì çíà÷åíèÿ ôóíêöèè g1 â âåðõíåé ëåâîé
è íèæíåé ïðàâîé òî÷êàõ ñõåìû: g1 124563 202( ) � , g1 456213 156 150( ) � � , êîòîðûå
ÿâëÿþòñÿ ìàêñèìàëüíûì è ìèíèìàëüíûì çíà÷åíèÿìè ôóíêöèè g1 ñîîòâåòñòâåí-
íî äëÿ x6 3� è òèïà âåðøèíû (123). Ýòî îçíà÷àåò, ÷òî äàííûé ïîäãðàô íå ñîäåð-
118 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 4
Íà÷àëî
Ââåñòè èñõîäíûå
äàííûå çàäà÷è:
íàïðàâëåíèå
îïòèìèçàöèè,
m, n, k, X, �ij,
cij , c0 , dij , d0,
ait , bt
Íàéòè çíà÷åíèÿ f
�
âî âñåõ òî÷êàõ
ìíîæåñòâà D
�
t: � 1 Dt
Êîíåö
t: � t � 1 t k
Íàéòè f i (x
�
)
Îïðåäåëèòü
Ïîäïðîãðàììà ìîäèôèöèðîâàííîãî
êîîðäèíàòíîãî ìåòîäà ñ îïòèìèçàöèåé
ïîèñêà äëÿ îãðàíè÷åíèÿ aitxj bt
Ðèñ. 1. Áëîê-ñõåìà àëãîðèòìà ìîäèôèöèðîâàííîãî êîîðäèíàòíîãî ìåòîäà ñ îïòèìèçàöèåé ïîèñêà
�
�
i
s
m
is
r
m
s
m
rs
ni N� ��
� �
�
� �
1
1 1
,
D D D Dk
� � � � �1 2 �
f f
i
k
i
k
i
�
�
� ��
1
extr
x F x
x D X
�
� �
� arg extr ( )
Ò à á ë è ö à 1. Ìàêñèìàëüíûå è ìèíèìàëüíûå çíà÷åíèÿ ôóíêöèè g1 ñ ôèêñè-
ðîâàííîé êîîðäèíàòîé x6
x6
Òî÷êà äîñòèæåíèÿ
ìàêñèìóìà
Ìàêñèìàëüíîå
çíà÷åíèå ôóíêöèè g1
Òî÷êà äîñòèæåíèÿ
ìèíèìóìà
Ìèíèìàëüíîå
çíà÷åíèå ôóíêöèè g1
6 123456 230 543216 190
5 123465 223 643215 175
4 123564 214 653214 162
3 124563 202 654213 150
2 134562 189 654312 141
1 234561 174 654321 134
æèò òî÷åê, êîòîðûå áû óäîâëåòâî-
ðÿëè ïåðâîìó îãðàíè÷åíèþ.
Äëÿ x6 3� ïîñëåäîâàòåëüíî
îïðåäåëèì òèïû âåðøèí è íàéäåì
äëÿ íèõ ìàêñèìàëüíûå è ìèíè-
ìàëüíûå çíà÷åíèÿ. Ðåçóëüòàòû
ïðåäñòàâèì â òàáë. 2.
Î÷åâèäíî, ÷òî èñêîìûå çíà-
÷åíèÿ äëÿ x6 3� ìîãóò ñîäåðæàòü-
ñÿ òîëüêî â ïîäãðàôå ñ òèïîì âåð-
øèíû (321). Íàéäåì çíà÷åíèÿ
â ñîñåäíèõ òî÷êàõ ñ ïåðåñòàíîâ-
êîé (654213). Ïîëó÷èì ñëåäóþ-
ùèå çíà÷åíèÿ g1 654213 156( ) � ,
g1 654123 152( ) � . Ðàññìîòðèì ñõå-
ìó ïîäãðàôà G3 äëÿ òèïà âåðøèíû (321) (ðèñ. 2). Ó÷èòûâàÿ íàïðàâëåíèå èçìåíå-
íèÿ çíà÷åíèé ôóíêöèè îò ìàêñèìàëüíîãî äî ìèíèìàëüíîãî ïðè ïîñòðîåíèè
ñõåìû, äåëàåì âûâîä, ÷òî îãðàíè÷åíèÿì óäîâëåòâîðÿåò åäèíñòâåííàÿ òî÷êà
(654213).
Çàêðåïèì x6 2� . Íàéäåì ìàêñèìàëüíûå è ìèíèìàëüíûå çíà÷åíèÿ ôóíêöèè g1
äëÿ êàæäîãî òèïà âåðøèí (òàáë. 3).
Êàê âèäíî èç òàáë. 3, òî÷êè, óäîâëåòâîðÿþùèå ïåðâîìó îãðàíè÷åíèþ, íàõî-
äÿòñÿ â ïîäãðàôàõ ñî âñåìè òèïàìè âåðøèí. Ïîñëåäîâàòåëüíî çàäàâ âñå òèïû
âåðøèí, ðàññìîòðèì ïîäãðàô G2 . Äëÿ ïðèìåðà ïðèâåäåì ñõåìó ïîäãðàôà (ðèñ. 3)
äëÿ òèïà âåðøèíû (312).
Èç ðèñ. 3 âèäíî, ÷òî îãðàíè÷åíèþ çàäà÷è óäîâëåòâîðÿþò òîëüêî ÷åòûðå òî÷-
êè ïîäãðàôà G2 : (634512), (635412), (645312) è (645231). Îñòàëüíûå ïðåâûøàþò
150 è íå âõîäÿò âî ìíîæåñòâî D1.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 4 119
Ò à á ë è ö à 2. Ìàêñèìàëüíûå è ìèíèìàëüíûå çíà÷åíèÿ ôóíêöèè g1 äëÿ ñîîò-
âåòñòâóþùåãî òèïà âåðøèíû ïðè x6 3�
Òèï
âåðøèíû
Òî÷êà äîñòèæåíèÿ
ìàêñèìóìà
Ìàêñèìàëüíîå
çíà÷åíèå
ôóíêöèè g1
Òî÷êà äîñòèæåíèÿ
ìèíèìóìà
Ìèíèìàëüíîå
çíà÷åíèå
ôóíêöèè g1
123 124563 202 456213 156
213 214563 200 546213 152
132 142563 200 465213 155
312 412563 194 645213 151
231 241563 197 564213 152
321 421563 193 654213 150
152
156
150
193
x5 � 6 x5 � 5 x5 � 4 x5 � 2 x5 � 1
Ðèñ. 2. Ñõåìà ïîäãðàôà G3 äëÿ òèïà âåðøèíû (321)
Ò à á ë è ö à 3. Ìàêñèìàëüíûå è ìèíèìàëüíûå çíà÷åíèÿ ôóíêöèè g1 äëÿ ñîîò-
âåòñòâóþùåãî òèïà âåðøèíû ïðè x6 2�
Òèï
âåðøèíû
Òî÷êà äîñòèæåíèÿ
ìàêñèìóìà
Ìàêñèìàëüíîå
çíà÷åíèå
ôóíêöèè g1
Òî÷êà äîñòèæåíèÿ
ìèíèìóìà
Ìèíèìàëüíîå
çíà÷åíèå
ôóíêöèè g1
123 134562 189 456312 147
213 314562 185 546312 145
132 143562 188 465312 146
312 413562 182 645312 142
231 341562 182 564312 143
321 431562 180 654312 141
Àíàëîãè÷íî ïðîâîäèì ðàñ÷åòû
äëÿ äðóãèõ ïÿòè òèïîâ âåðøèí.
 ðåçóëüòàòå ïîëó÷àåì 65 òî÷åê,
êîòîðûå óäîâëåòâîðÿþò îãðàíè÷å-
íèþ g1. Îñòàëüíûå òî÷êè êîíôèãó-
ðàöèè ïåðåñòàíîâîê îòáðàñûâàåì.
Ïåðåõîäèì ê ðàññìîòðåíèþ
âòîðîãî îãðàíè÷åíèÿ 5 71 2x x� �
� � �21 123 4x x 10 2 2475 6x x� , ñîîò-
âåòñòâóþùåãî ôóíêöèè g2 �
� � � � � �5 7 21 12 101 2 3 4 5x x x x x
� 2 6x . Äëÿ ðàáîòû ñ àëãîðèòìîì
êîîðäèíàòíîãî ìåòîäà ïðåîáðàçó-
åì ôóíêöèþ g2 òàê, ÷òîáû åå êî-
ýôôèöèåíòû óïîðÿäî÷èâàëèñü ïî âîçðàñòàíèþ. Ïîëó÷èì ôóíêöèþ
g x x x x x x2 1 2 3 4 5 62 5 7 10 12 21� � � � � � � � � � � � . Íàéäåì ìàêñèìàëüíûå è ìèíèìàëüíûå
çíà÷åíèÿ ôóíêöèè g2 , ïîñëåäîâàòåëüíî çàêðåïèâ êîîðäèíàòó �x6 , è ïðîàíàëèçè-
ðóåì ðåçóëüòàò (òàáë. 4).
Èç òàáë. 4 âèäíî, ÷òî òî÷êè ïîäãðàôîâ G4 , G3 , G2 , G1 ïîëíîñòüþ óäîâëåòâî-
ðÿþò îãðàíè÷åíèþ, ïîñêîëüêó ìàêñèìàëüíîå çíà÷åíèå ôóíêöèè íå ïðåâûøàåò
çàäàííîãî. Ïîýòîìó äåòàëüíåå ðàññìîòðèì òîëüêî ïîäãðàôû G6 è G5 . Äëÿ ïîä-
ãðàôà G6 çàêðåïèì ïîñëåäíþþ êîîðäèíàòó � �x6 6 è îïðåäåëèì òèï âåðøèíû
(123). Ïî êîîðäèíàòíîìó ìåòîäó íàéäåì çíà÷åíèÿ ôóíêöèè îãðàíè÷åíèÿ è ïðåä-
ñòàâèì èõ íà ñõåìå (ðèñ. 4).
Èç ðèñ. 4 âèäíî, ÷òî âòîðîìó
îãðàíè÷åíèþ íå óäîâëåòâîðÿþò
ëèøü øåñòü òî÷åê. Àíàëîãè÷íî
èññëåäóåì ïîäãðàô G6 äëÿ äðó-
ãèõ òèïîâ âåðøèí è ïîäãðàô G5 .
Ïîëó÷àåì 24 òî÷êè, êîòîðûå íå
óäîâëåòâîðÿþò âòîðîìó îãðàíè-
÷åíèþ.  ðåçóëüòàòå èìååì ìíî-
æåñòâî D2 .
Íàéäåì D D D* � �1 2 , êîòî-
ðîå ñîñòîèò ëèøü èç 64 òî÷åê.
Ïîñêîëüêó ôóíêöèè ÿâëÿþòñÿ
ðàâíîâåñíûìè, òî èõ âåñîâûå êîýô-
ôèöèåíòû áóäóò a a a1 2 3 1 3� � � / .
120 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 4
152
146
142
182
x5 � 6 x5 � 5 x5 � 4 x5 � 3 x5 � 1
155
149
146
Ðèñ. 3. Ñõåìà ïîäãðàôà G2 äëÿ òèïà âåðøèíû (312)
Ò à á ë è ö à 4. Ìàêñèìàëüíûå è ìèíèìàëüíûå çíà÷åíèÿ ôóíêöèè g2 ñ ôèêñè-
ðîâàííîé êîîðäèíàòîé �x6
�x6
Òî÷êà äîñòèæåíèÿ
ìàêñèìóìà
Ìàêñèìàëüíîå
çíà÷åíèå
ôóíêöèè g1
Òî÷êà äîñòèæåíèÿ
ìèíèìóìà
Ìèíèìàëüíîå
çíà÷åíèå
ôóíêöèè g1
6 123456 259 543216 209
5 123465 250 643215 190
4 123564 239 653214 174
3 124563 225 654213 160
2 134562 209 654312 149
1 234561 190 654321 140
259
x5 � 6 x5 � 5 x5 � 4 x5 � 3 x5 � 1
256
251
243
257 252
251
246 239
249 242
245
237
Ðèñ. 4. Ñõåìà ïîäãðàôà G6 ñ òèïîì âåðøèíû (123)
Ïðè ïåðåõîäå ê ñêàëÿðíîé çàäà÷å ïîëó÷èì ôóíêöèþ f x* ( ) �
�
� � � � �
� � � � �
�
2 4 3 4 2 31 2 3 4 5 6
1 2 3 4 5 6
x x x x x x
x x x x x x
max. Èòàê, èìååì îäíîêðèòåðèàëüíóþ çàäà-
÷ó ñ äðîáíî-ëèíåéíîé öåëåâîé ôóíêöèåé. Íàéäåì çíà÷åíèå ôóíêöèè â êàæäîé èç
ïîëó÷åííûõ òî÷åê, îïðåäåëèì ìàêñèìàëüíîå f max
� � 3
2
7
.  ðåçóëüòàòå ïîëó÷àåì
òî÷êó (364521), êîòîðàÿ ÿâëÿåòñÿ ðåøåíèåì çàäà÷è.
Ïðèìåð 2. Íàéòè òàêèå çíà÷åíèÿ x X� � , ãäå X — ìíîæåñòâî ïåðåñòàíîâîê
èç ýëåìåíòîâ À � ( , , , , , )1 2 3 4 5 6 , êîòîðûå ÿâëÿþòñÿ îïòèìàëüíûìè äëÿ ðàâíîâåñ-
íûõ ôóíêöèé
f x
x x x x x x
x x x x x x
1
1 2 3 4 5 6
1 2 3 4 5 6
2 5 2 6 3
2 3 2 4 2
( ) �
� � � � �
� � � � �
� max,
f x
x x x x x x
x x x x x x
2
1 2 3 4 5 6
1 2 3 4 5 6
2 3 3 4 2
2 2 7 8 5
( ) �
� � � � �
� � � � �
� max,
f x
x x x x x x
x x x x x x
3
1 2 3 4 5 6
1 2 3 4 5 6
3 3 4 2 7
7 4 5 8
( ) �
� � � � �
� � � � �
� max
ïðè îãðàíè÷åíèÿõ
3 5 6 9 11 18 150
5 7 21 12 10
1 2 3 4 5 6
1 2 3 4
x x x x x x
x x x x
� � � � �
� � � �
,
x x
x x x x x x
x x x
5 6
1 2 3 4 5 6
1 2 3
2 247
4 15 3 7 5 120
2 4 4
�
� � � � �
� �
,
,
� � � �
� � � � � �
6 9 13 104
2 4 5 13 2 11 51
11
4 5 6
1 2 3 4 5 6
x x x
x x x x x x
,
,
x x x x x x
x x x x x x
1 2 3 4 5 6
1 2 3 4 5
5 9 3 4 18 161
3 3 13 9 7
� � � � �
� � � � �
,
6 93�
�
�
�
�
�
�
�
�
�
�
� .
Ðåøåíèå. Äâà ïåðâûõ îãðàíè÷åíèÿ çàäà÷è ñîâïàäàþò ñ îãðàíè÷åíèÿìè ïðè-
ìåðà 1, ïðèìåíåíèå ê íèì àëãîðèòìà ðàññìîòðåíî ðàíåå. Äàëüíåéøåå èññëåäîâà-
íèå òðåòüåãî îãðàíè÷åíèÿ 4 15 3 7 5 1201 2 3 4 5 6x x x x x x� � � � � äàåò 54 òî÷êè, íå
âõîäÿùèå â îáëàñòü äîïóñòèìûõ çíà÷åíèé, äåâÿòü èç êîòîðûõ ñîâïàäàþò ñ ìíî-
æåñòâîì D D1 2� , ñîñòîÿùèì èç 64 òî÷åê (ñì. ïðèìåð 1). Íàõîäèì ïåðåñå÷åíèå
D D D1 2 3� � , êîòîðîå áóäåò ñîñòîÿòü èç 55 òî÷åê.
Ïðîäîëæàåì èññëåäîâàíèå ïî àëãîðèòìó êîîðäèíàòíîãî ìåòîäà äëÿ ÷åòâåð-
òîãî îãðàíè÷åíèÿ 2 4 4 6 9 13 1041 2 3 4 5 6x x x x x x� � � � � � .  ðåçóëüòàòå ðàáîòû àë-
ãîðèòìà ïîëó÷àåì 22 òî÷êè, íå óäîâëåòâîðÿþùèå ýòîìó îãðàíè÷åíèþ. Íàõîäèì
íîâîå ïåðåñå÷åíèå D D D D1 2 3 4� � � . Ýòî ìíîæåñòâî ñîñòîèò èç 34 òî÷åê.
Äëÿ òàêîãî êîëè÷åñòâà òî÷åê ðàöèîíàëüíî ïðîâåðèòü âûïîëíåíèå â êàæäîé
òî÷êå ñëåäóþùåãî îãðàíè÷åíèÿ: � � � � � � 2 4 5 13 2 11 511 2 3 4 5 6x x x x x x . Òàêèì
îáðàçîì, ìíîæåñòâî D D D D D1 2 3 4 5� � � � áóäåò ñîñòîÿòü èç 23 òî÷åê. Äëÿ
íèõ ïîñëåäîâàòåëüíî ðàññìîòðèì âûïîëíåíèå îñòàëüíûõ îãðàíè÷åíèé, â ðåçóëü-
òàòå ïîëó÷èì èñêîìîå ìíîæåñòâî D D D D D D D D* � � � � � � �1 2 3 4 5 6 7 , ñî-
ñòîÿùåå èç ÷åòûðåõ òî÷åê: (356421), (456231), (426431), (356421).
Ñ ó÷åòîì ðàâíîãî âåñà ôóíêöèé, ñîñòàâëÿþùèõ âåêòîðíûé êðèòåðèé îïòè-
ìèçàöèè, âåñîâûå êîýôôèöèåíòû a a a1 2 3 1 3� � � / . Èñêîìûé ñêàëÿðíûé êðèòå-
ðèé çàïèøåì â âèäå
f
x x x x x x
x x x x x x
* � �
� � � � �
� � � � �
1
3
2 5 2 6 3
2 3 2 4 2
1 2 3 4 5 6
1 2 3 4 5 6
�
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 4 121
� �
� � � � �
� � � � �
�
1
3
2 3 3 4 2
2 2 7 8 5
1 2 3 4 5 6
1 2 3 4 5 6
x x x x x x
x x x x x x
1
3
3 3 4 2 7
7 4 5 8
1 2 3 4 5 6
1 2 3 4 5 6
�
� � � � �
� � � � �
x x x x x x
x x x x x x
.
Îïðåäåëèì çíà÷åíèå ôóíêöèè f * â íàéäåííûõ òî÷êàõ x D� * . Ðåçóëüòàò
ïðåäñòàâèì â òàáë. 5, èç êîòîðîé âèäíî, ÷òî ðåøåíèåì ÿâëÿåòñÿ òî÷êà (356421),
ïîñêîëüêó çíà÷åíèå âåêòîðíîãî êðèòåðèÿ â íåé ìàêñèìàëüíîå. Ðåøåíèå íàéäåíî.
Äàííûé àëãîðèòì ïðèìåíåí äëÿ ðåøåíèÿ çàäà÷ ñ äðîáíî-ëèíåéíûìè ôóíê-
öèÿìè íà êîìáèíàòîðíûõ êîíôèãóðàöèÿõ. Îí ïîñòðîåí òàêèì îáðàçîì, ÷òîáû ñî-
êðàòèòü êîëè÷åñòâî íåîáõîäèìûõ ðàñ÷åòîâ çà ñ÷åò âûáîðà íàïðàâëåíèÿ ðàçâåð-
òûâàíèÿ ïîäãðàôà â çàâèñèìîñòè îò çíà÷åíèÿ ôóíêöèè â ãëàâíîé âåðøèíå,
â òî÷êå ñòîêà è çàäàííîãî â îãðàíè÷åíèè.
Îòìåòèì, ÷òî ïðè óâåëè÷åíèè ÷èñëà îãðàíè÷åíèé çàäà÷è âàæåí ïîðÿäîê èõ ðàñ-
ñìîòðåíèÿ, êîòîðûé âëèÿåò íà ýôôåêòèâíîñòü ôîðìèðîâàíèÿ ìíîæåñòâà äîïóñòè-
ìûõ çíà÷åíèé çàäà÷è D D D Dk
� � � � �1 2 � . Òàêæå, åñëè íà îïðåäåëåííîì ýòàïå
ðàáîòû àëãîðèòìà êîëè÷åñòâî òî÷åê êîìáèíàòîðíîé êîíôèãóðàöèè çíà÷èòåëüíî ïðå-
âûøàåò êîëè÷åñòâî äîïóñòèìûõ ðåøåíèé ïî óæå ðàññìîòðåííûì îãðàíè÷åíèÿì,
âîçíèêàåò âîïðîñ î öåëåñîîáðàçíîñòè ïðîâåäåíèÿ ïîëíîìàñøòàáíîãî ïîèñêà ïî
îñòàëüíûì îãðàíè÷åíèÿì. Áîëåå ðàöèîíàëüíûì ïîäõîäîì â äàííîé ñèòóàöèè ÿâëÿ-
åòñÿ ïðîâåðêà âûïîëíåíèÿ îñòàëüíûõ îãðàíè÷åíèé â íàéäåííûõ òî÷êàõ. Ïðè÷åì
ñ êàæäîé íîâîé ïðîâåðêîé êîëè÷åñòâî òî÷åê ìîæåò óìåíüøàòüñÿ.
ÇÀÊËÞ×ÅÍÈÅ
Ïðåäëîæåí ìîäèôèöèðîâàííûé êîîðäèíàòíûé ìåòîä ñ îïòèìèçàöèåé ïîèñêà,
çíà÷èòåëüíî óïðîùàþùèé ïðîöåññ ðåøåíèÿ ýêñòðåìàëüíûõ çàäà÷ ñ äðîáíî-ëè-
íåéíûìè öåëåâûìè ôóíêöèÿìè íà êîìáèíàòîðíûõ êîíôèãóðàöèÿõ. Îïèñàííûé
àëãîðèòì ïîçâîëÿåò èçáåæàòü ïðîöåññà ïðåîáðàçîâàíèÿ ïåðåìåííûõ äëÿ ëèíåà-
ðèçàöèè ôóíêöèé, ÷òî ïîâûøàåò åãî ýôôåêòèâíîñòü. Òàêæå ïðåäëîæåí ïîäõîä
ê îïòèìèçàöèè ïîèñêà çàäàííîãî çíà÷åíèÿ â ìîäèôèöèðîâàííîì àëãîðèòìå êî-
îðäèíàòíîãî ìåòîäà. Äàëüíåéøàÿ ðàáîòà â äàííîì íàïðàâëåíèè ïðåäóñìàòðè-
âàåò èññëåäîâàíèå òàêîãî ðîäà çàäà÷ íà äðóãèõ êîìáèíàòîðíûõ êîíôèãóðàöè-
ÿõ è ïðèìåíåíèå ïðèâåäåííîãî ìåòîäà èõ ðåøåíèÿ.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. Studniarski M. Stopping criteria for genetic algorithms with applicationto multiobjective optimi-
zation. In “Parallel Problem Solving from Nature — PPSN XI” (eds. R. Schaefer et al.). Part I. Lect.
Notes Comput. Sci. 2010. Vol. 6238 P. 697–706.
2. Äîíåö Ã.À., Êîëå÷êèíà Ë.Í. Îá îäíîé çàäà÷å îïòèìèçàöèè äðîáíî-ëèíåéíîé ôóíêöèè öåëè íà
ïåðåñòàíîâêàõ. Ïðîáëåìû óïðàâëåíèÿ è èíôîðìàòèêè. 2010. ¹ 2. Ñ. 31–41.
3. Äîíåöü Ã.Ï., Êîëº÷ê³íà Ë.Ì. Åêñòðåìàëüí³ çàäà÷³ íà êîìá³íàòîðíèõ êîíô³ãóðàö³ÿõ. Ïîëòàâà:
ÏÓÅÒ, 2011. 362 ñ.
4. ªìåöü Î.Î., Êîëº÷ê³íà Ë.Ì. Çàäà÷³ êîìá³íàòîðíî¿ îïòèì³çàö³¿ ç äðîáîâî-ë³í³éíèìè ö³ëüîâèìè
ôóíêö³ÿìè. Êè¿â: Íàóê. äóìêà, 2005. 113 ñ.
5. Êîëå÷êèíà Ë.Í., Ðîäèîíîâà Å.À. Ìíîãîêðèòåðèàëüíûå êîìáèíàòîðíûå çàäà÷è îïòèìèçàöèè
íà ìíîæåñòâå ïîëèðàçìåùåíèé. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. 2008. ¹ 2. Ñ. 152–160.
122 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 4
Ò à á ë è ö à 5 . Çíà÷åíèå ôóíêöèé f f f f�, , ,1 2 3 â íàéäåííûõ òî÷êàõ x D� *
x D� �
f
*
f1 f2 f3
(356421) 0.9308 1.361702 0.854839 0.575758
(456231) 0.9733 1.387755 0.981132 0.55102
(426431) 0.9349 1.365385 0.80303 0.636364
(356421) 0.9783 1.411765 1.018519 0.504762
6. Êîëå÷êèíà Ë.Í., Äâåðíàÿ Å.À., Íàãîðíàÿ À.Í. Ìîäèôèêàöèÿ êîîðäèíàòíîãî ìåòîäà ðåøåíèÿ
ýêñòðåìàëüíûõ çàäà÷ íà êîìáèíàòîðíûõ êîíôèãóðàöèÿõ ïðè óñëîâèè ìíîãîêðèòåðèàëüíîñòè.
Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. 2014. Ò. 50, ¹ 4. Ñ. 154–161.
7. Êîëº÷ê³íà Ë.Ì. Âëàñòèâîñò³ çàäà÷ áàãàòîêðèòåð³àëüíî¿ îïòèì³çàö³¿ íà êîìá³íàòîðíèõ ìíîæè-
íàõ òà ìåòîäè ¿õ ðîçâ’ÿçàííÿ. Ïîëòàâà: ÐÂÂ ÏÓÑÊÓ, 2008. 162 ñ.
8. Ñåìåíîâà Í.Â., Êîëº÷ê³íà Ë.Ì. Âåêòîðí³ çàäà÷³ äèñêðåòíî¿ îïòèì³çàö³¿ íà êîìá³íàòîðíèõ ìíî-
æèíàõ: ìåòîäè äîñë³äæåííÿ òà ðîçâ’ÿçàííÿ. Êè¿â: Íàóê. äóìêà, 2009. 262 ñ.
9. Ñåìåíîâà Í.Â., Êîëå÷êèíà Ë.Í., Íàãîðíàÿ À.Í. Îá îäíîì ïîäõîäå ê ðåøåíèþ âåêòîðíûõ çà-
äà÷ ñ äðîáíî-ëèíåéíûìè ôóíêöèÿìè êðèòåðèåâ íà êîìáèíàòîðíîì ìíîæåñòâå ðàçìåùåíèé.
Ïðîáëåìû óïðàâëåíèÿ è èíôîðìàòèêè. 2010. ¹ 1. Ñ. 131–144.
10. Øòîéåð Ð. Ìíîãîêðèòåðèàëüíàÿ îïòèìèçàöèÿ. Òåîðèÿ, âû÷èñëåíèÿ è ïðèëîæåíèÿ: Ïåð.
ñ àíãë. Ìîñêâà: Ðàäèî è ñâÿçü, 1992 504 ñ.
Íàä³éøëà äî ðåäàêö³¿ 27.01.2017
Ë.Ì. Êîëº÷ê³íà, Î.À. Äâ³ðíà
ÐÎÇÂ’ßÇÓÂÀÍÍß ÅÊÑÒÐÅÌÀËÜÍÈÕ ÇÀÄÀ× Ç ÄÐÎÁÎÂÎ-˲ͲÉÍÈÌÈ
ÔÓÍÊÖ²ßÌÈ Ö²Ë² ÍÀ ÊÎÌÁ²ÍÀÒÎÐÍ²É ÊÎÍÔ²ÃÓÐÀÖ²¯ ÏÅÐÅÑÒÀÂËÅÍÜ
ÇÀ ÓÌÎÂÈ ÁÀÃÀÒÎÊÐÈÒÅвÉÍÎÑÒ²
Àíîòàö³ÿ. Ðîçãëÿíóòî åêñòðåìàëüíó çàäà÷ó îïòèì³çàö³¿ ç äðîáîâî-ë³í³éíîþ
ôóíêö³ºþ ö³ë³ íà êîìá³íàòîðí³é êîíô³ãóðàö³¿ ïåðåñòàâëåíü çà óìîâè áàãà-
òîêðèòåð³éíîñò³. Ïðîàíàë³çîâàíî ìåòîäè ðîçâ’ÿçóâàííÿ äðîáîâî-ë³í³éíèõ çà-
äà÷ äëÿ âèáîðó ï³äõîäó äî ðîçâ’ÿçóâàííÿ ïîñòàâëåíî¿ çàäà÷³. Çàïðîïîíîâàíî
ï³äõ³ä äî ðîçâ’ÿçóâàííÿ òàêèõ çàäà÷ íà îñíîâ³ òåî𳿠ãðàô³â. Îïèñàíî àëãî-
ðèòì ï³äïðîãðàìè ìîäèô³êîâàíîãî êîîðäèíàòíîãî ìåòîäó ç îïòèì³çàö³ºþ
ïîøóêó òî÷îê êîíô³ãóðàö³¿, ÿêà ïðèçíà÷åíà äëÿ ôîðìóâàííÿ ìíîæèíè òî-
÷îê, ùî çàäîâîëüíÿþòü îáìåæåííÿì çàäà÷³. Çàïðîïîíîâàíî çàãàëüíèé àëãî-
ðèòì ðîçâ’ÿçóâàííÿ çàäà÷³, ÿêèé äîçâîëÿº óíèêíóòè ë³íåàðèçàö³¿ ôóíêö³¿, òà
éîãî áëîê-ñõåìó. Íàâåäåíî ïðèêëàäè ðîáîòè àëãîðèòìó.
Êëþ÷îâ³ ñëîâà: åêñòðåìàëüí³ çàäà÷³, êîìá³íàòîðí³ êîíô³ãóðàö³¿, äðîáî-
âî-ë³í³éí³ ôóíêö³¿, óìîâà áàãàòîêðèòåð³éíîñò³, ìîäèô³êîâàíèé êîîðäèíàòíèé
ìåòîä, îïòèì³çàö³ÿ ïîøóêó.
L.M. Koliechkina, O.A. Dvirna
SOLVING EXTREMUM PROBLEMS WITH FRACTIONAL-LINEAR
OBJECTIVE FUNCTIONS ON COMBINATORIAL CONFIGURATION
OF PERMUTATIONS WITH MULTICRITERIALITY CONDITION
Abstract. The authors consider the extremum optimization problem with
fractional-linear objective functions on combinatorial configuration of
permutations under multicriteria condition. The solution methods for
fractional-linear problems are analyzed to choose the approach to problem’s
solution. A solution technique based on graph theory is proposed. The algorithm
of the modified coordinate method’s subprogram with search optimization is
described. This subprogram forms a set of points that satisfy additional
constraints of the problem. The general solution algorithm without linearization
of the objective function and it’s block diagram are proposed. Examples of the
algorithm operation are described.
Keywords: extremum problems, combinatorial configurations, fractional-linear
functions, multicriteriality condition, modified coordinate method, optimization
of search.
Êîëå÷êèíà Ëþäìèëà Íèêîëàåâíà,
äîêòîð ôèç.-ìàò. íàóê, ïðîôåññîð êàôåäðû äîêóìåíòîâåäåíèÿ è èíôîðìàöèîííîé äåÿòåëüíîñòè
â ýêîíîìè÷åñêèõ ñèñòåìàõ ÂÓÇ Óêîîïñîþçà «Ïîëòàâñêèé óíèâåðñèòåò ýêîíîìèêè è òîðãîâëè»,
e-mail: ludapl@ukr.net.
Äâåðíàÿ Åëåíà Àíàòîëüåâíà,
àññèñòåíò êàôåäðû äîêóìåíòîâåäåíèÿ è èíôîðìàöèîííîé äåÿòåëüíîñòè â ýêîíîìè÷åñêèõ ñèñòåìàõ
ÂÓÇ Óêîîïñîþçà «Ïîëòàâñêèé óíèâåðñèòåò ýêîíîìèêè è òîðãîâëè», e-mail: lenadvirna@gmail.com.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 4 123
|