Поиск нормальных решений СЛАУ при двусторонних ограничениях на переменные методом внутренних точек

Рассмотрены варианты прямых алгоритмов внутренних точек для нахождения нормальных решений систем линейных уравнений при двусторонних ограничениях на переменные. Изучение данной проблемы и методов ее решения актуально для развития теории математического моделирования (в частности, для решения задач э...

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2015
Hauptverfasser:	Зоркальцев, В.И., Пержабинский, С.М., Стецюк, П.И.
Format:	Artikel
Sprache:	Russian
Veröffentlicht:	Інститут кібернетики ім. В.М. Глушкова НАН України 2015
Schriftenreihe:	Кибернетика и системный анализ
Schlagworte:	Системный анализ
Online Zugang:	http://dspace.nbuv.gov.ua/handle/123456789/124929
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:	Поиск нормальных решений СЛАУ при двусторонних ограничениях на переменные методом внутренних точек / В.И. Зоркальцев, С.М. Пержабинский, П.И. Стецюк // Кибернетика и системный анализ. — 2015. — Т. 51, № 6. — С. 71-80. — Бібліогр.: 8 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-124929
record_format	dspace
spelling	irk-123456789-1249292017-10-13T03:03:19Z Поиск нормальных решений СЛАУ при двусторонних ограничениях на переменные методом внутренних точек Зоркальцев, В.И. Пержабинский, С.М. Стецюк, П.И. Системный анализ Рассмотрены варианты прямых алгоритмов внутренних точек для нахождения нормальных решений систем линейных уравнений при двусторонних ограничениях на переменные. Изучение данной проблемы и методов ее решения актуально для развития теории математического моделирования (в частности, для решения задач энергетики), создания эффективных вычислительных алгоритмов. Представлены результаты экспериментальных исследований алгоритмов на тестовых задачах. Определены способы ускорения вычислительного процесса. Розглянуто варіанти прямих алгоритмів внутрішніх точок для знаходження нормальних розв’язків систем лінійних рівнянь при двосторонніх обмеженнях на змінні. Вивчення цієї проблеми і методів її розв’язання є актуальним для розвитку теорії математичного моделювання (зокрема, для розв’язання задач енергетики), створення ефективних обчислювальних алгоритмів. Наведено результати експериментальних досліджень алгоритмів на тестових задачах. Виявлено способи прискорення обчислювального процесу. The authors consider primal interior point algorithms to find normal solutions to systems of linear equations with bilateral constraints on variables. The analysis of this problem and the methods of its solution is important to develop the theory of mathematical modeling (in particular, to solve problems in power engineering) and to create efficient computational algorithms. The paper contains the results of experimental analysis of the algorithms using test problems and identifies the ways to accelerate the computational process. 2015 Article Поиск нормальных решений СЛАУ при двусторонних ограничениях на переменные методом внутренних точек / В.И. Зоркальцев, С.М. Пержабинский, П.И. Стецюк // Кибернетика и системный анализ. — 2015. — Т. 51, № 6. — С. 71-80. — Бібліогр.: 8 назв. — рос. 0023-1274 http://dspace.nbuv.gov.ua/handle/123456789/124929 519.6 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	2015
topic_facet	Системный анализ
url	http://dspace.nbuv.gov.ua/handle/123456789/124929
citation_txt	Поиск нормальных решений СЛАУ при двусторонних ограничениях на переменные методом внутренних точек / В.И. Зоркальцев, С.М. Пержабинский, П.И. Стецюк // Кибернетика и системный анализ. — 2015. — Т. 51, № 6. — С. 71-80. — Бібліогр.: 8 назв. — рос.
series	Кибернетика и системный анализ
work_keys_str_mv	AT zorkalʹcevvi poisknormalʹnyhrešenijslaupridvustoronnihograničeniâhnaperemennyemetodomvnutrennihtoček AT peržabinskijsm poisknormalʹnyhrešenijslaupridvustoronnihograničeniâhnaperemennyemetodomvnutrennihtoček AT stecûkpi poisknormalʹnyhrešenijslaupridvustoronnihograničeniâhnaperemennyemetodomvnutrennihtoček
first_indexed	2025-07-09T02:16:43Z
last_indexed	2025-07-09T02:16:43Z
_version_	1837133888289243136
fulltext	ÓÄÊ 519.6 Â.È. ÇÎÐÊÀËÜÖÅÂ, Ñ.Ì. ÏÅÐÆÀÁÈÍÑÊÈÉ, Ï.È. ÑÒÅÖÞÊ ÏÎÈÑÊ ÍÎÐÌÀËÜÍÛÕ ÐÅØÅÍÈÉ ÑËÀÓ ÏÐÈ ÄÂÓÑÒÎÐÎÍÍÈÕ ÎÃÐÀÍÈ×ÅÍÈßÕ ÍÀ ÏÅÐÅÌÅÍÍÛÅ ÌÅÒÎÄÎÌ ÂÍÓÒÐÅÍÍÈÕ ÒÎ×ÅÊ1 Àííîòàöèÿ. Ðàññìîòðåíû âàðèàíòû ïðÿìûõ àëãîðèòìîâ âíóòðåííèõ òî÷åê äëÿ íàõîæäå- íèÿ íîðìàëüíûõ ðåøåíèé ñèñòåì ëèíåéíûõ óðàâíåíèé ïðè äâóñòîðîííèõ îãðàíè÷åíèÿõ íà ïåðåìåííûå. Èçó÷åíèå äàííîé ïðîáëåìû è ìåòîäîâ åå ðåøåíèÿ àêòóàëüíî äëÿ ðàçâè- òèÿ òåîðèè ìàòåìàòè÷åñêîãî ìîäåëèðîâàíèÿ (â ÷àñòíîñòè, äëÿ ðåøåíèÿ çàäà÷ ýíåðãåòèêè), ñîçäàíèÿ ýôôåêòèâíûõ âû÷èñëèòåëüíûõ àëãîðèòìîâ. Ïðåäñòàâëåíû ðåçóëüòàòû ýêñïåðè- ìåíòàëüíûõ èññëåäîâàíèé àëãîðèòìîâ íà òåñòîâûõ çàäà÷àõ. Îïðåäåëåíû ñïîñîáû óñêîðå- íèÿ âû÷èñëèòåëüíîãî ïðîöåññà. Êëþ÷åâûå ñëîâà: ñèñòåìà ëèíåéíûõ àëãåáðàè÷åñêèõ óðàâíåíèé, àëãîðèòìû âíóòðåííèõ òî÷åê, íîðìàëüíîå ðåøåíèå, äâóñòîðîííèå îãðàíè÷åíèÿ íà ïåðåìåííûå. ÏÎÑÒÀÍÎÂÊÀ ÇÀÄÀ×È Ïóñòü çàäàíû: âåêòîðû b R nÎ , x R x R n nÎ Î, , ìàòðèöà A ðàçìåðà m n´ , äèà- ãîíàëüíàÿ ìàòðèöà W ðàçìåðà n ñ ïîëîæèòåëüíûìè êîýôôèöèåíòàìè w j , j n=1, ... , , íà äèàãîíàëè. Ïåðåìåííûå ñîñòàâëÿþò âåêòîð x R nÎ . Ðàññìàòðèâà- åòñÿ çàäà÷à 1 2 x Wx T ® min (1) ïðè îãðàíè÷åíèÿõ Ax b= , (2) x x x£ £ . (3) Çäåñü x x> , ò.å. x xj j> äëÿ âñåõ j n=1, ,K . Ñôîðìóëèðîâàííàÿ çàäà÷à (1)–(3) ðàâíîñèëüíà ïðîáëåìå ïîèñêà íîð- ìàëüíûõ, ò.å. c íàèìåíüøåé íîðìîé, ðåøåíèé ñèñòåìû ëèíåéíûõ óðàâíåíèé è íåðàâåíñòâ (2), (3). Íîðìîé áóäåì ñ÷èòàòü åâêëèäîâó íîðìó \| \| \| \| ( ) / x w xW j j n j= æ è ç ç ö ø ÷ ÷ = å 1 2 1 2 ñ âåñàìè w j . Çàäà÷è ïîèñêà íàèìåíåå óäàëåííûõ îò íà- ÷àëà êîîðäèíàò ðåøåíèé ñèñòåì ëèíåéíûõ íåðàâåíñòâ (ëèíåéíûå óðàâíåíèÿ — ÷àñ- òíûé ñëó÷àé ëèíåéíûõ íåðàâåíñòâ) ÷àñòî èñïîëüçóþòñÿ ïðè ìàòåìàòè÷åñêîì ìîäåëèðîâàíèè è ÿâëÿþòñÿ ñîñòàâíîé ÷àñòüþ ìíîãèõ âû÷èñëèòåëüíûõ ìåòîäîâ. Êàê îáîáùåíèå äàííîé çàäà÷è ðàññìàòðèâàåòñÿ ïðîáëåìà ïîèñêà ðåøåíèÿ ñèñòå- ìû ëèíåéíûõ íåðàâåíñòâ, íàèìåíåå óäàëåííîãî îò çàäàííîãî âåêòîðà x R n0 Î . Â ÷àñòíîñòè, â [1] èññëåäóåòñÿ çàäà÷à ïîèñêà âåêòîðà x R nÎ èç óñëîâèé ( ) ( ) minx x W x x- - ®0 0T (4) ïðè îãðàíè÷åíèÿõ (2), (3). Äàííàÿ çàäà÷à çàìåíîé ïåðåìåííûõ ñâîäèòñÿ ê çà- äà÷å âèäà (1)–(3). Öåëåâàÿ ôóíêöèÿ (4) â ðåçóëüòàòå âîçðàñòàþùåãî ïðåîá- ðàçîâàíèÿ ñâîäèòñÿ ê åâêëèäîâîìó ðàññòîÿíèþ ìåæäó âåêòîðàìè r( , )x x0 = = - -(( ) ( )) / x x W x x 0 0 1 2T . ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 6 71 1 Ðàáîòà âûïîëíåíà ïðè ïîääåðæêå ÐÔÔÈ, ïðîåêò ¹ 15-07-07412à, è ÍÀÍÓ, ïðîåêò ¹ 0114U001055. Ó Â.È. Çîðêàëüöåâ, Ñ.Ì. Ïåðæàáèíñêèé, Ï.È. Ñòåöþê, 2015 Ñèñòåìà ëèíåéíûõ óðàâíåíèé è íåðàâåíñòâ âèäà (2), (3) èìååò ðÿä ýôôåêòèâíûõ â âû÷èñëèòåëüíîì îòíîøåíèè ñâîéñòâ [2–5]. Îíè îáóñëîâëåíû òåì, ÷òî âñå ïå- ðåìåííûå ñèñòåìû ëèíåéíûõ óðàâíåíèé (2) èìåþò äâóñòîðîííèå îãðàíè÷åíèÿ, ÷òî ñôîðìóëèðîâàíî â óñëîâèè (3). Äëÿ äàëüíåéøåãî öåëåñîîáðàçíî ïðåäñòàâèòü äâóñòîðîííèå îãðàíè÷åíèÿ (3) êàê îãðàíè÷åíèÿ-íåðàâåíñòâà - ³ -x x, (5) x x³ . (6) Â ðàáîòàõ [2, 3, 6] ðàññìàòðèâàëàñü ïðîáëåìà ïîèñêà ðåøåíèé ñèñòåìû ëè- íåéíûõ íåðàâåíñòâ (2), (3) â âèäå çàäà÷è ëèíåéíîãî ïðîãðàììèðîâàíèÿ ñ ôèêòèâ- íîé öåëåâîé ôóíêöèåé (òîæäåñòâåííî ðàâíîé íóëþ). Ýòîé çàäà÷å ñîîòâåòñòâóåò èíòåðåñíàÿ â âû÷èñëèòåëüíîì îòíîøåíèè äâîéñòâåííàÿ çàäà÷à ëèíåéíîãî ïðî- ãðàììèðîâàíèÿ ñ «ðåàëüíîé» (íå ðàâíîé òîæäåñòâåííî êîíñòàíòå) öåëåâîé ôóíê- öèåé ïðè óäîáíûõ â âû÷èñëèòåëüíîì îòíîøåíèè îäíîðîäíûõ îãðàíè÷åíèÿõ-íå- ðàâåíñòâàõ. Â ðàáîòàõ [2, 7] ïðåäñòàâëåíû ñðàâíèòåëüíûå ýêñïåðèìåíòàëüíûå èññëåäî- âàíèÿ «ïðÿìûõ» è «äâîéñòâåííûõ» àëãîðèòìîâ âíóòðåííèõ òî÷åê äëÿ ðåøåíèÿ ñèñòåì âèäà (2), (3) íà òåñòîâûõ ïðèìåðàõ è çàäà÷àõ âûáîðà äîïóñòèìûõ ðåæè- ìîâ ôóíêöèîíèðîâàíèÿ ýëåêòðîýíåðãåòè÷åñêèõ ñèñòåì. Â ïðÿìûõ àëãîðèòìàõ âíóòðåííèõ òî÷åê èòåðàòèâíî âûðàáàòûâàåòñÿ ïîñëåäîâàòåëüíîñòü âåêòîðîâ x k , óäîâëåòâîðÿþùèõ íåðàâåíñòâàì x x x k< < . Çäåñü k — íîìåð èòåðàöèè, k = 0 1 2, , , ... Ïðè ýòîì ïðîèñõîäèò ìîíîòîííîå ñîêðàùåíèå íåâÿçîê áàëàíñîâûõ îãðàíè÷åíèé r b Ax k = - ïî ïðàâèëó r r k k k+ = -1 1( )l , ãäå l k — øàã êîððåêòèðîâêè ðåøåíèÿ íà èòåðàöèè k, l k Î( , ]0 1 . Íà êàæäîé èòåðàöèè âûðàáàòûâàþòñÿ òàêæå ïðèáëèæå- íèÿ ê ìíîæèòåëÿì Ëàãðàíæà îãðàíè÷åíèé (2), (3) ôèêòèâíîé çàäà÷è ëèíåéíîãî ïðî- ãðàììèðîâàíèÿ. Êàê ïîêàçàëè ðåçóëüòàòû ýêñïåðèìåíòàëüíûõ èññëåäîâàíèé [2], ýòè ìíîæèòåëè ýôôåêòèâíû äëÿ áûñòðîé èäåíòèôèêàöèè ñëó÷àåâ íåñîâìåñòíîñòè (ïðîòèâîðå÷èâîñòè) óñëîâèé (2), (3). Âåêòîðû íåîïðåäåëåííûõ ìíîæèòåëåé Ëàãðàíæà îãðàíè÷åíèé (2), (5), (6) îáîçíà÷èì u, h, g, ïðè ýòîì u R mÎ , h R nÎ , g R nÎ . Äàëåå â êà÷åñòâå ðàñøè- ðåííîãî ðåøåíèÿ çàäà÷è (1)–(3) ðàññìîòðèì íàðÿäó ñ îïòèìàëüíûì çíà÷åíèåì âåê- òîðà x êîíêðåòíûå çíà÷åíèÿ âåêòîðîâ ìíîæèòåëåé Ëàãðàíæà u, h, g è âåêòîð y Wx= . ÄÂÎÉÑÒÂÅÍÍÀß ÇÀÄÀ×À Îáîçíà÷èì V äèàãîíàëüíóþ ìàòðèöó ðàçìåðà n n´ ñ êîýôôèöèåíòàìè v w j j = 1 , j n=1, ,K , íà äèàãîíàëè, ò.å. îáðàòíóþ ê ìàòðèöå âåñîâûõ êîýôôèöèåíòîâ V W= -1. Ââåäåì ôóíêöèþ îò âåêòîðîâ y R nÎ , u R mÎ , h R nÎ , g R nÎ F( , , , )y u h g y Vy b u x h x g= - + - 1 2 T T T T . (7) Ðàññìîòðèì çàäà÷ó, â êîòîðîé ïåðåìåííûìè ÿâëÿþòñÿ êîìïîíåíòû âåêòî- ðîâ-àðãóìåíòîâ ââåäåííîé ôóíêöèè (7) F( , , , ) miny u h g ® (8) ïðè îãðàíè÷åíèÿõ y A u h g- + - =T 0, (9) h g³ ³0 0, . (10) 72 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 6 Äàííóþ çàäà÷ó íàçîâåì äâîéñòâåííîé (ê èñõîäíîé çàäà÷å (1)–(3)). Îòìåòèì, ÷òî äâîéñòâåííîé ê ýòîé çàäà÷å áóäåò èñõîäíàÿ çàäà÷à (1)–(3), ò.å. èìååò ìåñòî ñëó÷àé ñèììåòðè÷íîé äâîéñòâåííîñòè. Ðàñøèðåííûì ðåøåíèåì äâîéñòâåííîé çàäà÷è íàçîâåì íàáîð èç óêàçàííûõ âåêòîðîâ y, u, h, g ñ äîáàâëåíèåì âåêòîðà x R nÎ , êîòîðûé ðàññìàòðèâàåòñÿ â êà- ÷åñòâå âåêòîðà ìíîæèòåëåé Ëàãðàíæà îãðàíè÷åíèé (9). Ïî ñîñòàâó âåêòîðîâ ðàñ- øèðåííîå ðåøåíèå èñõîäíîé çàäà÷è (1)–(3) è äâîéñòâåííîé çàäà÷è (8)–(10) ñîâïàäàþò. Ñïðàâåäëèâà ñëåäóþùàÿ òåîðåìà [8]. Òåîðåìà 1. Íàáîð âåêòîðîâ x R nÎ , y R nÎ , u R mÎ , h R nÎ , g R nÎ ÿâëÿåòñÿ ðàñøèðåííûì ðåøåíèåì çàäà÷è (1)–(3) â òîì è òîëüêî â òîì ñëó÷àå, åñëè îí ÿâ- ëÿåòñÿ ðàñøèðåííûì ðåøåíèåì çàäà÷è (8)–(10). Ýòà òåîðåìà ïîçâîëÿåò èñïîëüçîâàòü àëãîðèòìû ðåøåíèÿ çàäà÷è (8)–(10) äëÿ ïîèñêà ðåøåíèÿ çàäà÷è (1)–(3). Äâîéñòâåííàÿ çàäà÷à èìååò íåêîòîðûå ïðåèìó- ùåñòâà. Â ÷àñòíîñòè, äëÿ íåå ìîæíî îïðåäåëèòü äîïóñòèìûå ïî âñåì îãðàíè÷å- íèÿì ðåøåíèÿ. Ïðè ïðîèçâîëüíûõ y R nÎ , u R mÎ ïîëîæèì h A u y= - +( )T , g y A u= - +( )T . (11) Ïîëó÷åííàÿ ÷åòâåðêà âåêòîðîâ óäîâëåòâîðÿåò óñëîâèÿì (9), (10). Çäåñü ()+ — îïåðàöèÿ íåîòðèöàòåëüíîé ñðåçêè: ( ) max ,a a+ = { }0 äëÿ ëþáîãî âåùåñòâåííîãî a. Â âûðàæåíèÿõ (11) ïîäðàçóìåâàåòñÿ, ÷òî òàêàÿ ñðåçêà îñóùåñòâëÿåòñÿ äëÿ êàæäîé êîìïîíåíòû óêàçàííûõ âåêòîðîâ. Äâîéñòâåííàÿ çàäà÷à òàêæå ïîëåçíà äëÿ âûÿâëåíèÿ â ïðîöåññå ñ÷åòà âîçìîæ- íîé ñèòóàöèè íåñîâìåñòíîñòè îãðàíè÷åíèé èñõîäíîé çàäà÷è. Â ýòîì è òîëüêî â ýòîì ñëó÷àå äâîéñòâåííàÿ çàäà÷à íå èìååò ðåøåíèÿ èç-çà òîãî, ÷òî åå öåëåâàÿ ôóíêöèÿ (8) íå îãðàíè÷åíà ñíèçó íà ìíîæåñòâå äîïóñòèìûõ ïî óñëîâèÿì (9), (10) ðåøåíèé. Ýòî ðàâíîñèëüíî ñëåäóþùåìó óòâåðæäåíèþ, âûòåêàþùåìó èç òåîðåì îá àëüòåðíàòèâíûõ ñèñòåìàõ ëèíåéíûõ íåðàâåíñòâ. Òåîðåìà 2. Ñèñòåìà ëèíåéíûõ óðàâíåíèé è íåðàâåíñòâ (2), (3) íåñîâìåñòíà â òîì è òîëüêî â òîì ñëó÷àå, åñëè ñóùåñòâóþò âåêòîðû u R mÎ , h R nÎ , g R nÎ òà- êèå, ÷òî âûïîëíÿþòñÿ íåðàâåíñòâà h g³ ³0 0, , x h x g b u T T T- - < 0, (12) A u h g T + - = 0. (13) ÑÀÌÎÑÎÏÐßÆÅÍÍÀß ÇÀÄÀ×À È ÊÐÈÒÅÐÈÈ ÎÏÒÈÌÀËÜÍÎÑÒÈ ÐÅØÅÍÈß Ââåäåì ôóíêöèþ îò âåêòîðîâ ñóìì öåëåâûõ ôóíêöèé èñõîäíîé è äâîéñòâåí- íîé çàäà÷ F x y u h g x Wx y u h g( , , , , ) ( , , , )= + 1 2 T F . Ðàññìîòðèì çàäà÷ó ìèíèìèçà- öèè ââåäåííîé ôóíêöèè F x y u h g( , , , , ) min® (14) ïðè îãðàíè÷åíèÿõ (2), (3), (9), (10). Õîòÿ òàêàÿ çàäà÷à ÿâëÿåòñÿ ïðîñòûì ñîå- äèíåíèåì èñõîäíîé è äâîéñòâåííîé çàäà÷, îíà îáëàäàåò íîâûìè ïîëåçíûìè ñâîéñòâàìè. Â ÷àñòíîñòè, ýòà çàäà÷à äâîéñòâåííà ê ñàìîé ñåáå. Ïîýòîìó çàäà- ÷ó (14), (2), (3), (9), (10) íàçîâåì ñàìîñîïðÿæåííîé çàäà÷åé. Ñïðàâåäëèâà ñëå- äóþùàÿ òåîðåìà [8]. ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 6 73 Òåîðåìà 3. Åñëè âåêòîð x óäîâëåòâîðÿåò óñëîâèÿì (2), (3), âåêòîðû y, u, h, g óäîâëåòâîðÿþò óñëîâèÿì (9), (10), òî ôóíêöèÿ F îò ýòèõ âåêòîðîâ èìååò íåîòðè- öàòåëüíîå çíà÷åíèå. Äàííàÿ ôóíêöèÿ èìååò íóëåâîå çíà÷åíèå â òîì è òîëüêî â òîì ñëó÷àå, åñëè âåêòîðû x, y, u, h, g ÿâëÿþòñÿ îïòèìàëüíûì ðàñøèðåííûì ðå- øåíèåì èñõîäíîé è äâîéñòâåííîé çàäà÷. Èç òåîðåìû 3 ñëåäóåò, ÷òî ðàñøèðåííîå ðåøåíèå ïðÿìîé è äâîéñòâåííîé çà- äà÷ áóäåò îïòèìàëüíûì ðåøåíèåì ýòèõ çàäà÷ â òîì è òîëüêî â òîì ñëó÷àå, åñëè äëÿ ðàñøèðåííîãî ðåøåíèÿ âûïîëíÿþòñÿ îãðàíè÷åíèÿ îáåèõ çàäà÷ è ñóììà çíà- ÷åíèé èõ öåëåâûõ ôóíêöèé ðàâíà íóëþ: F x y u h g( , , , , ) = 0. Èñõîäÿ èç òåîðåìû 3, ïðåäëîæèì ñëåäóþùèé êðèòåðèé äëÿ ïðåêðàùåíèÿ ðàñ÷åòîâ ïðè ïîëó÷åíèè ðåøåíèé, áëèçêèõ ê îïòèìàëüíîìó. Ïóñòü èìååòñÿ (ïî- ëó÷åí â ðåçóëüòàòå êàêîãî-ëèáî âû÷èñëèòåëüíîãî ïðîöåññà) íàáîð âåêòîðîâ ~x , ~y, ~u , ~ h , ~g , óäîâëåòâîðÿþùèõ (9). Íàõîäèì âåêòîð íåâÿçîê áàëàíñîâûõ îãðàíè÷å- íèé (2) ~ ~r b Ax= - . Âû÷èñëÿåì çíà÷åíèå ñóììû ôóíêöèé èñõîäíîé è äâîéñòâåí- íîé çàäà÷ äëÿ âåêòîðîâ ~x , ~y, ~u , ~ h , ~g . Åñëè âûïîëíÿþòñÿ íåðàâåíñòâà \| \| ~\| \|r £ e1, (15) \| (~, ~, ~, ~ , ~ )\|F x y u h g £ e2 , (16) òî ïîëàãàåì, ÷òî ïîëó÷åííûé íàáîð ñîñòàâëÿåò îïòèìàëüíîå ðåøåíèå ñ òðåáóå- ìîé òî÷íîñòüþ. Çäåñü e1, e2 — çàäàííûå ïîëîæèòåëüíûå ìàëûå âåëè÷èíû, õà- ðàêòåðèçóþùèå íåîáõîäèìóþ òî÷íîñòü âûïîëíåíèÿ áàëàíñîâûõ îãðàíè÷åíèé (2) è ðàâåíñòâà íóëþ ñóììû öåëåâûõ ôóíêöèé èñõîäíîé è äâîéñòâåííîé çàäà÷. Êðèòåðèé îñòàíîâà âû÷èñëèòåëüíîãî ïðîöåññà ìîæíî ïîñòðîèòü íà îñíîâå íåîáõîäèìûõ è äîñòàòî÷íûõ óñëîâèé îïòèìàëüíîñòè Êóíà–Òàêêåðà. Â ýòîì ñëó- ÷àå íàðÿäó ñ (15) íåîáõîäèìà ïðîâåðêà äëÿ ~x , ~y, ~u , ~ h , ~g âûïîëíåíèÿ ñëåäóþùèõ óñëîâèé äîïîëíÿþùåé íåæåñòêîñòè ñ çàäàííîé òî÷íîñòüþ e2 0> : \| ( )\|g x xj j j- £ e2 , j n=1, ... , , (17) \| ( )\|h x xj j j- £ e2 , j n=1, ... , . (18) ÏÐßÌÛÅ ÀËÃÎÐÈÒÌÛ ÂÍÓÒÐÅÍÍÈÕ ÒÎ×ÅÊ Â àëãîðèòìàõ íà èòåðàöèÿõ k = 0 1 2, , , ... ñòðîèòñÿ ïîñëåäîâàòåëüíîñòü âåêòîðîâ x k èç R n , äëÿ êîòîðûõ íåðàâåíñòâà (3) âûïîëíÿþòñÿ â ñòðîãîé ôîðìå x x x k< < , k = 0 1 2, , , ... (19) Â êà÷åñòâå ñòàðòîâîé òî÷êè ìîæíî èñïîëüçîâàòü, íàïðèìåð, âåêòîð x x x 0 1 2 = +( ) . Êàæäàÿ èòåðàöèÿ àëãîðèòìà âêëþ÷àåò ñåìü ýòàïîâ âû÷èñëåíèé. 1. Îïðåäåëåíèå âåñîâûõ êîýôôèöèåíòîâ. Ñíà÷àëà ðàññìîòðèì «êëàññè÷åñ- êèé» âàðèàíò àëãîðèòìà âíóòðåííèõ òî÷åê [4], â êîòîðîì âåñîâûå êîýôôèöèåíòû îïðåäåëÿþòñÿ ïî ïðàâèëó d x x x xj k j k j j j k= - -min ( ) , ( ){ }2 2 , j n=1, ... , . (20) 74 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 6 Îáîçíà÷èì d k âåêòîð èç R n , ñîñòàâëåííûé èç äàííûõ âåñîâûõ êîýôôèöèåí- òîâ. Ïóñòü Dk — äèàãîíàëüíàÿ ìàòðèöà ðàçìåðà n ñ ââåäåííûìè âåñîâûìè êîýô- ôèöèåíòàìè íà äèàãîíàëè D dk k= diag ( ). 2. Îïðåäåëåíèå âåêòîðà íåâÿçîê áàëàíñîâûõ îãðàíè÷åíèé. Âû÷èñëÿåì âåêòîð ~r b Ax k k= - . (21) Åñëè äëÿ íåãî âûïîëíÿåòñÿ (15), ò.å. \| \| ~ \| \|r k £ e1, (22) òî ïîëàãàåì r k = 0, (23) ãäå r k — âåêòîð èç R m . Áóäåì ñ÷èòàòü, ÷òî ïðè âûïîëíåíèè (23) îñóùåñòâëÿ- åòñÿ ïðîöåññ îïòèìèçàöèè â îáëàñòè äîïóñòèìûõ ðåøåíèé çàäà÷è (1)–(3). Åñëè äëÿ ~r k íåðàâåíñòâî (22) íå âûïîëíÿåòñÿ, òî ïîëàãàåì r r k k= ~ . (24) Åñëè èìååò ìåñòî ðàâåíñòâî (24), òî îñóùåñòâëÿåòñÿ ïðîöåññ ââîäà â îáëàñòü äîïóñòèìûõ ðåøåíèé çàäà÷è (1)–(3). 3. Âñïîìîãàòåëüíàÿ çàäà÷à ïîèñêà íàïðàâëåíèÿ ðåøåíèÿ. Îáîçíà÷èì Dx k âåêòîð èç R n , ÿâëÿþùèéñÿ ðåøåíèåì ñëåäóþùåé âñïîìîãàòåëüíîé çàäà÷è îòíîñèòåëüíî âåêòîðà ïåðåìåííûõ Dx: 1 2 1 2 1( ) ( ) minx x W x x x D x k k k + + + ®-D D D DT T (25) ïðè óñëîâèè A x r kD = . (26) Èç óñëîâèé îïòèìàëüíîñòè Ëàãðàíæà ñëåäóåò, ÷òî äëÿ îïòèìàëüíîñòè âåêòî- ðà Dx âî âñïîìîãàòåëüíîé çàäà÷å (25), (26) íåîáõîäèìî âûïîëíåíèå ðàâåíñòâà ( )W D x Wx A u k k+ + =-1 D T . (27) Çäåñü u — âåêòîð èç R m , ñîñòîÿùèé èç ìíîæèòåëåé Ëàãðàíæà îãðàíè÷åíèÿ (26). Óñëîâèå (27) ñòàíîâèòñÿ äîñòàòî÷íûì, åñëè Dx óäîâëåòâîðÿåò è óñëîâèþ (26). Âûðàçèì èç (27) âåêòîð D x ÷åðåç u: D x W D A u Wx k k= + -- -( ) ( )1 1 T . (28) Ïîäñòàâèâ äàííîå âûðàæåíèå â (26), ïîëó÷èì ñèñòåìó ëèíåéíûõ óðàâíåíèé îòíîñèòåëüíî âåêòîðà u B u r ck k k= + , (29) ãäå B A W D Ak k = + - -( )1 1 T , c A W D Wx k k k= + - -( )1 1 . Ìàòðèöà Bk ñèììåòðè- ÷åñêàÿ ïîëîæèòåëüíî-îïðåäåëåííàÿ. Äëÿ ðåøåíèÿ ñèñòåìû (29) ìîæåò èñïîëü- çîâàòüñÿ ìåòîä êâàäðàòíîãî êîðíÿ. Ïóñòü u k — ðåøåíèå ñèñòåìû (29). Ïîä- ñòàâèâ ýòîò âåêòîð âìåñòî u â (28), ïîëó÷èì çíà÷åíèå Dx k . 4. Ïðîâåðêà íà ñîâìåñòíîñòü îãðàíè÷åíèé (2), (3). Ñîãëàñíî òåîðåìå 2 óñëîâèÿ (2), (3) ïðîòèâîðå÷èâû è äàëüíåéøèå ðàñ÷åòû äîëæíû áûòü ïðåêðàùå- íû, åñëè äëÿ âåêòîðîâ h g u k k k, , âûïîëíÿþòñÿ óñëîâèÿ (12), (13). Ïîëîæèì h A u k k= +( )T , g A u k k= - +( )T . ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 6 75 Åñëè x h x g b u k k kT T T- - < 0, òî ðàñ÷åòû ïðåêðàùàþòñÿ. 5. Âû÷èñëåíèå øàãà êîððåêòèðîâêè ðåøåíèÿ. Ïðè çàäàííîì ïàðàìåòðå àëãîðèòìà g Î( , )0 1 âû÷èñëÿåì ~ max :l g l lk k k x x x x= £ + £{ }D . (30) Ìîæíî èñïîëüçîâàòü g ðàâíûì 2 3/ . Èñõîäÿ èç (30), âåëè÷èíó øàãà íàõîäèì ïî ôîðìóëå ~ min min , min : : l gk j x j j k j k j x j j k jj k j k x x x x x x = - - < >D DD D0 0 k ì í ï îï ü ý ï þï . Åñëè îñóùåñòâëÿåòñÿ ïðîöåññ ââîäà â îáëàñòü äîïóñòèìûõ ðåøåíèé, òî ïîëàãàåì l lk k= min ~ ,{ }1 . (31) Åñëè âûïîëíÿåòñÿ ïðîöåññ îïòèìèçàöèè â îáëàñòè äîïóñòèìûõ ðåøåíèé, òî âû÷èñëÿåì $ min ( ) ( )l l l l k k k k k x x W x x= + + ³ arg T 0 1 2 D D . (32) Îòñþäà $ ( ) ( ) l k k k k k x W x x W x = - T T D D D . Çàòåì ïîëàãàåì l l lk k k= min ~ , ${ }. (33) 6. Èòåðàòèâíûé ïåðåõîä. Òàêîé ïåðåõîä îñóùåñòâëÿåòñÿ ïî ôîðìóëå x x x k k k k+ = +1 l D . (34) Ïðàâèëà âû÷èñëåíèÿ øàãà (30)–(33) ãàðàíòèðóþò, ÷òî èç âûïîëíåíèÿ íåðà- âåíñòâ (19) äëÿ âåêòîðà x k ñëåäóåò âûïîëíåíèå ýòèõ íåðàâåíñòâ äëÿ âåêòîðà x k+1. Èç (21) è óñëîâèÿ (26) ïðè âûáîðå íàïðàâëåíèÿ êîððåêòèðîâêè ðåøåíèÿ ñëå- äóåò, ÷òî â ïðîöåññå ââîäà â îáëàñòü äîïóñòèìûõ ðåøåíèé äîëæíî âûïîëíÿòüñÿ íåðàâåíñòâî ~ ( )~ .r r k k k+ = -1 1 l Ýòèì îáúÿñíÿåòñÿ èñïîëüçîâàíèå ïðàâèëà (31). Èç (26) òàêæå âûòåêàåò, ÷òî ïðè îïòèìèçàöèè â îáëàñòè äîïóñòèìûõ ðåøå- íèé ïîñëå èòåðàöèè ïåðåõîäà (34) âûïîëíÿåòñÿ ðàâåíñòâî ~ ~r r k k+ =1 . Îíî îçíà- ÷àåò, ÷òî âåêòîð ~r k+1 áóäåò íóëåâûì, ò.å. è íà ñëåäóþùåé èòåðàöèè îñóùåñòâëÿ- åòñÿ ïðîöåññ îïòèìèçàöèè â îáëàñòè äîïóñòèìûõ ðåøåíèé. 7. Ïðîâåðêà ïîëó÷åííîãî ðåøåíèÿ íà îïòèìàëüíîñòü (òîëüêî äëÿ èòåðà- öèè k ³ 1). Åñëè îñóùåñòâëÿåòñÿ ïðîöåññ îïòèìèçàöèè â îáëàñòè äîïóñòèìûõ ðå- øåíèé, r k = 0, òî ïîëàãàåì ~x x k= , ~ , ~y Wx u u k k= = -1. Çäåñü u k-1 — ïðèáëèæåíèå ê çíà÷åíèþ âåêòîðà ìíîæèòåëåé Ëàãðàíæà, âû÷èñëåííîå â ðåçóëüòàòå ðåøåíèÿ ñèñòåìû (29) íà ïðåäûäóùåé èòåðàöèè (ïîýòîìó äàííûé ýòàï âû÷èñëåíèé îñó- ùåñòâëÿåòñÿ òîëüêî ïðè k ³ 1). 76 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 6 Ïî ïðàâèëàì (11) âû÷èñëÿåì, èñõîäÿ èç óêàçàííûõ çíà÷åíèé ~y, ~u , âåêòî- ðû ~ h , ~g . Åñëè âûïîëíÿåòñÿ íåðàâåíñòâî (16) èëè íåðàâåíñòâà (17), (18), òî ðàñ÷å- òû ïðåêðàùàþòñÿ â ñâÿçè ñ ïîëó÷åíèåì ðåøåíèÿ, áëèçêîãî, ñ òðåáóåìîé òî÷íîñ- òüþ, ê îïòèìàëüíîìó. Äðóãîé âàðèàíò àëãîðèòìà ñîñòîèò â òîì, ÷òî âìåñòî (20) èñïîëüçóåòñÿ ñëå- äóþùåå ïðàâèëî çàäàíèÿ âåñîâûõ êîýôôèöèåíòîâ: d x x h x x g j k j j k j k j k j j k = - -ì í ï îï ü - - min max , , max ,{ } { }b b1 1 ý ï þï =, , ,j n1 K , ãäå b — çàäàííàÿ ìàëàÿ ïîëîæèòåëüíàÿ âåëè÷èíà. Ïðè k = 0 ñ÷èòàåì h 0 0= , g 0 0= . ÝÊÑÏÅÐÈÌÅÍÒÀËÜÍÛÅ ÈÑÑËÅÄÎÂÀÍÈß Ýêñïåðèìåíòàëüíûå èññëåäîâàíèÿ ðàññìàòðèâàåìûõ âàðèàíòîâ àëãîðèòìîâ âíóòðåííèõ òî÷åê ïðîâîäèëèñü íà çàäà÷àõ âèäà (1)–(3), îòëè÷àþùèõñÿ ðàçìåð- íîñòüþ è ãðàíèöàìè âàðüèðîâàíèÿ ïåðåìåííûõ. Òåñòîâûå çàäà÷è ðåøàëèñü äâóìÿ âàðèàíòàìè ïðÿìûõ àëãîðèòìîâ âíóòðåííèõ òî÷åê. Àëãîðèòìû óñëîâíî îáîçíà÷èì Primal_1 è Primal_2. Â Primal_1 âåñîâûå êîýôôèöèåíòû âûáèðàëèñü ïî ïðàâèëó (20), â Primal_2 — àëüòåðíàòèâíûì ñïîñîáîì. Â àëãîðèòìàõ ïðè íàõîæäåíèè øàãà êîððåêòèðîâêè (ñîãëàñíî ïðàâèëó (30)) ïàðàìåòð g ðàâíÿë- ñÿ 0,9, ïðè âû÷èñëåíèè âåñîâûõ êîýôôèöèåíòîâ èñïîëüçîâàëîñü b = 01, . Äëÿ ïðîâåðêè îïòèìàëüíîñòè ïîñòðîåííûõ àëãîðèòìîì ïðèáëèæåíèé ïðèìåíÿëèñü êðèòåðèè (15), (16) è (15), (17), (18), â êîòîðûõ e1 0 001= , , e2 0 01= , . Öåëåâûå ôóíêöèè òåñòîâûõ çàäà÷ ôîðìèðîâàëèñü ïî ïðàâèëó 1 2 2 1 ixi i n = å , (35) îãðàíè÷åíèÿ âèäà (2) — ïî ôîðìóëàì x x n m i mi j j m n + = - = = + å 1 2 1, , ,K . (36) Ãðàíèöû èçìåíåíèÿ ïåðåìåííûõ çàäàâàëèñü óñëîâèÿìè 0 2 1£ £ - =x n m j nj , , ,K , (37) 0 1 1 1, , , ,£ £ =x j nj K . (38) Òåñòîâûå ïðèìåðû ðàçäåëèì íà äâå ãðóïïû: ïîèñê ìèíèìóìà ôóíêöèè (35) ïðè îãðàíè÷åíèÿõ (36), (37) (ìèíèìóì ôóíêöèè — âíóòðè îáëàñòè äîïóñòèìûõ ðåøåíèé); ìèíèìèçàöèÿ ôóíêöèè (35) ïðè îãðàíè÷åíèÿõ (36), (38) (ìèíèìóì ôóíêöèè — íà ãðàíèöå îáëàñòè äîïóñòèìûõ ðåøåíèé). Â òàáë. 1 ïðåäñòàâëåíû ðåçóëüòàòû ðåøåíèÿ çàäà÷ âàðèàíòàìè ïðÿìîãî àëãî- ðèòìà âíóòðåííèõ òî÷åê (Primal_1, Primal_2) ïðè èñïîëüçîâàíèè êðèòåðèÿ îñòà- íîâà (15), (16), â òàáë. 2 — êðèòåðèÿ îñòàíîâà (15), (17), (18). Â òàáëèöàõ óêàçàíî ÷èñëî èòåðàöèé, çà êîòîðîå áûëà ðåøåíà òåñòîâàÿ çàäà÷à. Â ñêîáêàõ ïðèâåäåíî êîëè÷åñòâî èòåðàöèé, ïîòðåáîâàâøèõñÿ äëÿ ââîäà â îáëàñòü äîïóñòèìûõ ðåøåíèé. ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 6 77 Â òàáë. 3 è òàáë. 4 ïðèâåäåíû ðåçóëüòàòû ðàñ÷åòîâ òåñòîâûõ çàäà÷ ìîäèôè- öèðîâàííûìè âàðèàíòàìè àëãîðèòìîâ Primal_1 è Primal_2 (MPrimal_1 è MPrimal_2), â êîòîðûõ øàã êîððåêòèðîâêè $l k , âû÷èñëÿåìûé ïðè îïòèìèçàöèè â îáëàñòè äîïóñòèìûõ ðåøåíèé, íàõîäèëñÿ ïî ôîðìóëå $ , ( ) ( ) l k k k k k x W x x W x = -0 99 T T D D D . Èç òàáëèö âèäíî, ÷òî ïðè èñïîëüçîâàíèè êðèòåðèÿ îñòàíîâà (15), (16) (òàáë. 3) àëãîðèòìàì òðåáóåòñÿ çíà÷èòåëüíî áîëüøåå êîëè÷åñòâî èòåðàöèé äëÿ ïîëó÷åíèÿ ðåøåíèÿ, áëèçêîãî ê îïòèìàëüíîìó, ÷åì â ñëó÷àå ïðèìåíåíèÿ êðèòå- ðèÿ (15), (17), (18) (òàáë. 4). Íàèëó÷øèå ðåçóëüòàòû ïî ÷èñëó èòåðàöèé ïîêàçàë àëãîðèòì Primal_2 è åãî ìîäèôèêàöèÿ. Îòìåòèì, ÷òî ýòîò àëãîðèòì áûë ââåäåí â [6] äëÿ ïðåîäîëåíèÿ íåãàòèâíûõ ýôôåêòîâ âëèÿíèÿ ïîãðåøíîñòåé âû÷èñëåíèé èñõîäíîãî àëãîðèòìà âíóòðåííèõ òî÷åê (Primal_1) â êîíöå âû÷èñëèòåëüíîãî ïðî- öåññà. Ìîäèôèêàöèÿ ïðàâèëà âû÷èñëåíèÿ øàãà $l k ïîçâîëèëà â ñðåäíåì ñîêðà- òèòü âðåìÿ âû÷èñëåíèé, îñîáåííî â ñëó÷àå àëãîðèòìà Primal_1. Íåîáõîäèìî òåî- ðåòè÷åñêîå èññëåäîâàíèå äàííîãî ôàêòà. Ñîïîñòàâèâ ðåçóëüòàòû ðåøåíèÿ äâóõ òèïîâ çàäà÷, îòìåòèì, ÷òî çàäà÷è ñ áî- ëåå «æåñòêèìè» îãðàíè÷åíèÿìè-íåðàâåíñòâàìè íà ïåðåìåííûå (ïðè óñëîâèè (37)) ðåøàþòñÿ àëãîðèòìàìè ñ êâàäðàòè÷íûìè âåñàìè ñóùåñòâåííî áûñòðåå, ÷åì çàäà- ÷è ñ áîëåå «ñëàáûìè» îãðàíè÷åíèÿìè-íåðàâåíñòâàìè (ïðè óñëîâèè (38)). Àëãîðèòìû ñ àëüòåðíàòèâíûì ñïîñîáîì çàäàíèÿ âåñîâûõ êîýôôèöèåíòîâ äåìîíñòðè- ðóþò ïðîòèâîïîëîæíûå ðåçóëüòàòû. Ýòî òàêæå òðåáóåò òåîðåòè÷åñêîãî îáîñíîâàíèÿ. 78 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 6 Ðàçìåðíîñòü çàäà÷è Êîëè÷åñòâî èòåðàöèé, íåîáõîäèìûõ äëÿ ðåøåíèÿ çàäà÷è (35)–(37) çàäà÷è (35), (36), (38) Primal_1 Primal_2 Primal_1 Primal_2 n m= =125 100, 6 (3) 7 (2) 119 (2) 5 (2) n m= =150 100, 182 (3) 9 (2) 394 (2) 5 (2) n m= =300 100, 21 (3) 13 (3) 3925 (2) 6 (2) n m= =400 100, 44 (4) 12 (4) 4462 (2) 9 (2) n m= =225 200, 5 (3) 5 (2) 75 (2) 6 (2) n m= =250 200, 85 (3) 9 (2) 211 (2) 6 (2) n m= =400 200, 377 (4) 12 (3) 3948 (2) 6 (2) n m= =600 200, 180 (4) 13 (4) 8110 (2) 7 (2) n m= =800 200, 72(4) 25(5) 8474(2) 10(2) Ò à á ë è ö à 1 Ðàçìåðíîñòü çàäà÷è Êîëè÷åñòâî èòåðàöèé, íåîáõîäèìûõ äëÿ ðåøåíèÿ çàäà÷è (35)–(37) çàäà÷è (35), (36), (38) Primal_1 Primal_2 Primal_1 Primal_2 n m= =125 100, 5 (3) 5 (2) 31 (2) 4 (2) n m= =150 100, 16 (3) 8 (2) 186 (2) 4 (2) n m= =300 100, 17 (3) 10 (3) 669 (2) 4 (2) n m= =400 100, 28 (4) 11 (4) 114 (2) 5 (2) n m= =225 200, 5 (3) 5 (2) 5 (2) 4 (2) n m= =250 200, 5 (3) 7 (2) 1497 (2) 4 (2) n m= =400 200, 171 (4) 11 (3) 64 (2) 4 (2) n m= =600 200, 118 (4) 12 (4) 78 (2) 5 (2) n m= =800 200, 32 (4) 13 (5) 130 (2) 6 (2) Ò à á ë è ö à 2 Â ðàáîòå ïðåäñòàâëåíû âàðèàíòû ïðÿìûõ àëãîðèòìîâ âíóòðåííèõ òî÷åê äëÿ íàõîæäåíèÿ íîðìàëüíûõ ðåøåíèé ñèñòåì ëèíåéíûõ óðàâíåíèé ïðè äâóñòîðîí- íèõ îãðàíè÷åíèÿõ íà ïåðåìåííûå. Ïðîâåäåííûå ýêñïåðèìåíòàëüíûå èññëåäîâà- íèÿ àëãîðèòìîâ íà òåñòîâûõ çàäà÷àõ âûÿâèëè ñëåäóþùèå èõ îñîáåííîñòè: · àëãîðèòìû ñ êâàäðàòè÷íûìè âåñîâûìè êîýôôèöèåíòàìè èìåþò ïëîõóþ óñòîé÷èâîñòü (÷èñëî èòåðàöèé, íåîáõîäèìûõ äëÿ ðåøåíèÿ çàäà÷, ñèëüíî îòëè÷à- åòñÿ è íå çàâèñèò îò ðàçìåðíîñòè çàäà÷è); · àëãîðèòìû âíóòðåííèõ òî÷åê ñ àëüòåðíàòèâíûì ñïîñîáîì çàäàíèÿ âåñîâûõ êîýôôèöèåíòîâ ïîêàçàëè íàèáîëüøóþ âû÷èñëèòåëüíóþ ýôôåêòèâíîñòü (ìàëîå êîëè÷åñòâî èòåðàöèé, óñòîé÷èâîñòü âû÷èñëåíèé); · ìîäèôèêàöèÿ ïðàâèëà íàõîæäåíèÿ øàãà êîððåêòèðîâêè ïîâûøàåò ñòàáèëü- íîñòü ðàáîòû àëãîðèòìîâ, â îñîáåííîñòè ñ êâàäðàòè÷íûìè âåñîâûìè êîýôôèöè- åíòàìè; · ïðè èñïîëüçîâàíèè êðèòåðèÿ îñòàíîâà (15), (16) àëãîðèòìàì òðåáóåòñÿ çíà- ÷èòåëüíî áîëüøåå êîëè÷åñòâî èòåðàöèé äëÿ ïîëó÷åíèÿ ðåøåíèÿ, áëèçêîãî ê îïòèìàëüíîìó, ÷åì â ñëó÷àå ïðèìåíåíèÿ êðèòåðèÿ (15), (17), (18); · çàäà÷è ñ áîëåå «æåñòêèìè» îãðàíè÷åíèÿìè-íåðàâåíñòâàìè íà ïåðåìåííûå ðåøàþòñÿ àëãîðèòìàìè ñ êâàäðàòè÷íûìè âåñàìè ñóùåñòâåííî áûñòðåå, ÷åì çàäà- ÷è ñ áîëåå «ñëàáûìè» îãðàíè÷åíèÿìè-íåðàâåíñòâàìè (äëÿ àëãîðèòìîâ ñ àëüòåð- ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 6 79 Ðàçìåðíîñòü çàäà÷è Êîëè÷åñòâî èòåðàöèé, íåîáõîäèìûõ äëÿ ðåøåíèÿ çàäà÷è (35)–(37) çàäà÷è (35), (36), (38) ÌPrimal_1 ÌPrimal_2 ÌPrimal_1 ÌPrimal_2 n m= =125 100, 11 (3) 7 (2) 148 (2) 5 (2) n m= =150 100, 19 (3) 9 (2) 142 (2) 5 (2) n m= =300 100, 21 (3) 11 (3) 571 (2) 6 (2) n m= =400 100, 22 (4) 14 (4) 509 (2) 9 (2) n m= =225 200, 23 (3) 7 (2) 42 (2) 6 (2) n m= =250 200, 13 (3) 9 (2) 237 (2) 6 (2) n m= =400 200, 30 (4) 27 (3) 236 (2) 6 (2) n m= =600 200, 59 (4) 35 (4) 397 (2) 7 (2) n m= =800 200, 32 (4) 52 (5) 615 (2) 10 (2) Ò à á ë è ö à 3 Ðàçìåðíîñòü çàäà÷è Êîëè÷åñòâî èòåðàöèé, íåîáõîäèìûõ äëÿ ðåøåíèÿ çàäà÷è (35)–(37) çàäà÷è (35), (36), (38) ÌPrimal_1 ÌPrimal_2 ÌPrimal_1 ÌPrimal_2 n m= =125 100, 7 (3) 5 (2) 15 (2) 4 (2) n m= =150 100, 11 (3) 8 (2) 48 (2) 4 (2) n m= =300 100, 15 (3) 10 (3) 91 (2) 4 (2) n m= =400 100, 18 (4) 11 (4) 40 (2) 5 (2) n m= =225 200, 11 (3) 7 (2) 15 (2) 4 (2) n m= =250 200, 7 (3) 7 (2) 7 (2) 4 (2) n m= =400 200, 22 (4) 11 (3) 26 (2) 4 (2) n m= =600 200, 26 (4) 12 (4) 30 (2) 5 (2) n m= =800 200, 18 (4) 13 (5) 42 (2) 6 (2) Ò à á ë è ö à 4 íàòèâíûì ñïîñîáîì âû÷èñëåíèÿ âåñîâûõ êîýôôèöèåíòîâ ïîëó÷åíû ïðîòèâîïî- ëîæíûå ðåçóëüòàòû). Ìîæíî ïðîãíîçèðîâàòü ñîêðàùåíèå îáúåìà âû÷èñëåíèé äëÿ ðåøåíèÿ óêà- çàííîé çàäà÷è îò ïðèìåíåíèÿ äâîéñòâåííûõ àëãîðèòìîâ âíóòðåííèõ òî÷åê. Ïðè èõ èñïîëüçîâàíèè îñóùåñòâëÿåòñÿ ìîíîòîííîå óëó÷øåíèå ïî èòåðàöèÿì öåëåâîé ôóíêöèè äâîéñòâåííîé çàäà÷è. Íà êàæäîé èòåðàöèè âûðàáàòûâàþòñÿ ïðèáëèæå- íèÿ ê ðåøåíèþ èñõîäíîé ñèñòåìû (2), (3). Õîòÿ ýòè ïðèáëèæåíèÿ íå îáëàäàþò ñâîéñòâîì ìîíîòîííîãî óëó÷øåíèÿ ðåøåíèÿ èñõîäíîé ñèñòåìû, îíè, êàê ïîêà- çûâàþò ìíîãî÷èñëåííûå ýêñïåðèìåíòû è íåêîòîðûå òåîðåòè÷åñêèå [7] ðåçóëüòà- òû, íàìíîãî áûñòðåå ïðèâîäÿò ê ðåøåíèþ ñèñòåìû (2), (3), ÷åì «ïðÿìûå» àëãî- ðèòìû âíóòðåííèõ òî÷åê. Äâîéñòâåííûå àëãîðèòìû òàêæå çíà÷èòåëüíî áûñòðåå (ñ ìåíüøèì îáúåìîì âû÷èñëåíèé) èäåíòèôèöèðóþò ñëó÷àè íåñîâìåñòíîñòè ñèñ- òåì (2), (3). Â ðàáîòå [8] ïðåäñòàâëåíû ðåçóëüòàòû ñðàâíèòåëüíûõ èññëåäîâàíèé, äåìîíñòðèðóþùèå ýôôåêòèâíîñòü äâîéñòâåííûõ àëãîðèòìîâ âíóòðåííèõ òî÷åê äëÿ ðåøåíèÿ ñèñòåì âèäà (2), (3) íà òåñòîâûõ ïðèìåðàõ è çàäà÷àõ âûáîðà äîïóñ- òèìûõ ðåæèìîâ ôóíêöèîíèðîâàíèÿ ýëåêòðîýíåðãåòè÷åñêèõ ñèñòåì. ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ 1. Ñ ò å ö þ ê Ï . È . , Í ó ð ì è í ñ ê è é Å . À . , Ñ î ë î ì î í Ä . È . Òðàíñïîðòíàÿ çàäà÷à è îðòîãîíàëü- íîå ïðîåêòèðîâàíèå íà ëèíåéíûå ìíîãîîáðàçèÿ // Ìàòåðèàëû V-é ìåæäóíàð. íàó÷. êîíô. «Òðàí- ñïîðòíûå ñèñòåìû è ëîãèñòèêà», Êèøèíýó, 11–13 äåêàáðÿ 2013 ãîäà. — Êèøèíýó: Ýâðèêà, 2013. — Ñ. 251–263. 2. Ô è ë à ò î â À . Þ . Ðàçâèòèå àëãîðèòìîâ âíóòðåííèõ òî÷åê è èõ ïðèëîæåíèé ê ñèñòåìàì íåðàâåíñòâ: Àâòîðåô. äèñ. ... êàíä. ôèç-ìàò. íàóê. — ÈÃÓ: Èðêóòñê, 2001. — 19 ñ. 3. Ç î ð ê à ë ü ö å â Â . È . Ðåøåíèÿ ñèñòåì ëèíåéíûõ íåðàâåíñòâ àëãîðèòìàìè âíóòðåííèõ òî÷åê // Ñîâ- ðåìåííûå ìåòîäû îïòèìèçàöèè è èõ ïðèëîæåíèÿ ê ìîäåëÿì ýíåðãåòèêè. — Íîâîñèáèðñê: Íàóêà, 2003. — Ñ. 110–141. 4. Ä è ê è í È . È . , Ç î ð ê à ë ü ö å â Â . È . Èòåðàòèâíîå ðåøåíèå çàäà÷ ìàòåìàòè÷åñêîãî ïðîãðàììèðî- âàíèÿ (àëãîðèòìû ìåòîäà âíóòðåííèõ òî÷åê). — Íîâîñèáèðñê: Íàóêà, 1980. — 144 ñ. 5. Ç î ð ê à ë ü ö å â Â . È . , Ê è ñ å ë å â à Ì . À . Ñèñòåìû ëèíåéíûõ íåðàâåíñòâ. — Èðêóòñê: Èçä-âî Èðêóò. ãîñ. óí-òà, 2007. — 127 ñ. 6. Z o r k a l ’ t s e v V . I . Algorithms of projective optimization which use the multipliers of previous iterations // Comp. Math. Phys. — 1994. — 34, N 7. — P. 943–950. 7. Â î é ò î â Î . Í . , Ç î ð ê à ë ü ö å â Â . È . , Ô è ë à ò î â À . Þ . Îïðåäåëåíèå äîïóñòèìûõ ðåæèìîâ ýëåêòðîýíåðãåòè÷åñêèõ ñèñòåì àëãîðèòìàìè âíóòðåííèõ òî÷åê // Ñèá. æóðí. èíäóñòð. ìàòåìàòèêè. — 2000. — 3, ¹ 1. — Ñ. 57–65. 8. Ç î ð ê à ë ü ö å â Â . È . , Ì å ä â å æ î í ê î â Ä . Ñ . ×èñëåííûå ýêñïåðèìåíòû ñ âàðèàíòàìè àëãîðèò- ìîâ âíóòðåííèõ òî÷åê íà íåëèíåéíûõ çàäà÷àõ ïîòîêîðàñïðåäåëåíèÿ // Óïðàâëåíèå áîëüøèìè ñèñòå- ìàìè. — Ì.: ÈÏÓ ÐÀÍ, 2013. — ¹ 46. — Ñ. 68–87. Ïîñòóïèëà 27.02.2015 80 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 6

Поиск нормальных решений СЛАУ при двусторонних ограничениях на переменные методом внутренних точек

Institution

Ähnliche Einträge