Об оценках числовых характеристик сложности постоптимального анализа дискретных задач оптимизации
Введено функцію, що характеризує складність постоптимального аналізу дискретних задач оптимізації. Для цієї функції отримано верхню оцінку і в класі методів гілок і меж для одновимірної задачі про ранець нижню оцінку. Виділено клас задач про покриття множинами з поліноміальною оцінкою заданої фун...
Збережено в:
| Дата: | 2010 |
|---|---|
| Автор: | |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2010
|
| Назва видання: | Кибернетика и системный анализ |
| Теми: | |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/45633 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Об оценках числовых характеристик сложности постоптимального анализа дискретных задач оптимизации / В.А. Михайлюк // Кибернетика и системный анализ. — 2010. — № 5. — С. 136-142. — Бібліогр.: 12 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-45633 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-456332013-06-17T03:18:02Z Об оценках числовых характеристик сложности постоптимального анализа дискретных задач оптимизации Михайлюк, В.А. Системный анализ Введено функцію, що характеризує складність постоптимального аналізу дискретних задач оптимізації. Для цієї функції отримано верхню оцінку і в класі методів гілок і меж для одновимірної задачі про ранець нижню оцінку. Виділено клас задач про покриття множинами з поліноміальною оцінкою заданої функції. A function is introduced that characterizes the complexity of postoptimality analysis of discrete optimization problems. For this function, the upper bound and the lower bound in the class of branch and bound methods for the knapsack problem are obtained. A class of set covering problems with the polynomial estimate of this function is observed. 2010 Article Об оценках числовых характеристик сложности постоптимального анализа дискретных задач оптимизации / В.А. Михайлюк // Кибернетика и системный анализ. — 2010. — № 5. — С. 136-142. — Бібліогр.: 12 назв. — рос. 0023-1274 http://dspace.nbuv.gov.ua/handle/123456789/45633 519.854 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 |
2010 |
| topic_facet |
Системный анализ |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/45633 |
| citation_txt |
Об оценках числовых характеристик сложности постоптимального анализа дискретных задач оптимизации / В.А. Михайлюк // Кибернетика и системный анализ. — 2010. — № 5. — С. 136-142. — Бібліогр.: 12 назв. — рос. |
| series |
Кибернетика и системный анализ |
| work_keys_str_mv |
AT mihajlûkva obocenkahčislovyhharakteristiksložnostipostoptimalʹnogoanalizadiskretnyhzadačoptimizacii |
| first_indexed |
2025-07-04T04:30:44Z |
| last_indexed |
2025-07-04T04:30:44Z |
| _version_ |
1836689336351850496 |
| fulltext |
ÓÄÊ 519.854
Â.À. ÌÈÕÀÉËÞÊ
ÎÁ ÎÖÅÍÊÀÕ ×ÈÑËÎÂÛÕ ÕÀÐÀÊÒÅÐÈÑÒÈÊ ÑËÎÆÍÎÑÒÈ
ÏÎÑÒÎÏÒÈÌÀËÜÍÎÃÎ ÀÍÀËÈÇÀ ÄÈÑÊÐÅÒÍÛÕ ÇÀÄÀ×
ÎÏÒÈÌÈÇÀÖÈÈ
Êëþ÷åâûå ñëîâà: ïîñòîïòèìàëüíûé àíàëèç, ñëîæíîñòü ìåòîäà âåòâåé è ãðà-
íèö, âïîëíå óíèìîäóëÿðíûå ìàòðèöû.
ÂÂÅÄÅÍÈÅ
Ïðîâåäåíèå ïîñòîïòèìàëüíîãî àíàëèçà äèñêðåòíûõ îïòèìèçàöèîííûõ çàäà÷ [1–5]
ïðåäóñìàòðèâàåò ðåøåíèå ñëåäóþùèõ âîïðîñîâ:
� êàê èçìåíèòñÿ îïòèìàëüíîå ðåøåíèå êîíêðåòíîé çàäà÷è, åñëè èçìåíèòü çíà-
÷åíèÿ åå êîýôôèöèåíòîâ;
� êàê èñïîëüçîâàòü èíôîðìàöèþ, ïîëó÷åííóþ ïðè ðåøåíèè íåêîòîðîé çàäà÷è
òåì èëè èíûì ìåòîäîì, äëÿ ðåøåíèÿ èçìåíåííîé çàäà÷è;
� êàêóþ ìèíèìàëüíóþ äîïîëíèòåëüíóþ èíôîðìàöèþ íåîáõîäèìî íàêîïèòü
ïðè ðåøåíèè èñõîäíîé çàäà÷è â öåëÿõ ýôôåêòèâíîãî ðåøåíèÿ èçìåíåííîé çàäà÷è.
Îáëàñòüþ ïðèìåíåíèÿ ïîñòîïòèìàëüíîãî àíàëèçà ÿâëÿåòñÿ àíàëèç äåÿòåëüíîñ-
òè íåêîòîðîãî ðåàëüíîãî ïðîöåññà, îïèñûâàåìîãî ìîäåëüþ äèñêðåòíîé îïòèìèçà-
136 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 5
� Â.À. Ìèõàéëþê, 2010
öèè, êîòîðûé ëåæèò â îñíîâå ðàçëè÷íîãî ðîäà íîâîââåäåíèé. Êðîìå òîãî, ïðè íå-
áîëüøèõ èçìåíåíèÿõ â èñõîäíûõ äàííûõ ìîäåëè äèñêðåòíîãî ïðîãðàììèðîâàíèÿ,
êàê ïðàâèëî, íåóñòîé÷èâû è íåïðåäñêàçóåìû.
ÎÏÐÅÄÅËÅÍÈÅ ÔÓÍÊÖÈÉ Compl ( { }) Compl ( )I I, ( ) ,� �
Ââåäåì ôîðìàëèçàöèþ ïîíÿòèÿ ýôôåêòèâíîãî ïðîâåäåíèÿ ïîñòîïòèìàëüíîãî àíà-
ëèçà äëÿ çàäà÷ äèñêðåòíîé îïòèìèçàöèè.
Ïóñòü � — íåêîòîðàÿ NP-òðóäíàÿ îïòèìèçàöèîííàÿ ïðîáëåìà (âîçìîæíî, è
NP-ïîëíàÿ), I — ýêçåìïëÿð ïðîáëåìû (çàäà÷è) � . Êàæäîìó ýêçåìïëÿðó I çàäà÷è �
ïîñòàâëåíî â ñîîòâåòñòâèå ìíîæåñòâî { }�( )I ýêçåìïëÿðîâ çàäà÷è � . Ïîñòîïòèìàëü-
íûé àíàëèç äëÿ ïàðû ( , ( ) )I I{ }� äàåò îòâåò íà âîïðîñ : êàê, çíàÿ îïòèìàëüíîå ðåøå-
íèå ýêçåìïëÿðà I ( ( ) ){opt }I , íàéòè îïòèìàëüíîå ðåøåíèå (ðåøåíèÿ) �I çàäà÷ ñ { }�( )I
( ( ) ){opt }�I . Ââåäåì ïîíÿòèå ýôôåêòèâíîãî ïîñòîïòèìàëüíîãî ñâåäåíèÿ ýêçåìïëÿ-
ðîâ çàäà÷è �( )� efp . Áóäåì ñ÷èòàòü, ÷òî ôóíêöèÿ f n( ) ïîëèíîìèàëüíîãî ðîñòà
( ( ) ( ))f n n� poly , åñëè äëÿ íåêîòîðîé êîíñòàíòû c ïðè äîñòàòî÷íî áîëüøèõ n âû-
ïîëíÿåòñÿ f n nc( ) � ; f n O g n f n g n( ) ( ( ))( ( ) ( ( )))� � , åñëè äëÿ íåêîòîðîé êîíñòàí-
òû c ïðè äîñòàòî÷íî áîëüøèõ n f n cg n f n cg n( ) ( )( ( ) ( ))�
.
Îïðåäåëåíèå 1. Áóäåì ñ÷èòàòü, ÷òî ýêçåìïëÿð � �I � ýôôåêòèâíî ïîñòîïòè-
ìàëüíî ñâîäèòñÿ ê ýêçåìïëÿðó I �� , åñëè ñóùåñòâóåò òàêàÿ ïîëèíîìèàëüíî âû÷èñ-
ëèìàÿ íà äåòåðìèíèðîâàííîé ìàøèíå Òüþðèíãà (ÄÌÒ) ôóíêöèÿ f ( )� , ÷òî
opt opt( ) ( ( ))� �I f I , îáîçíà÷åíèå ��I Iefp ( f — ñëîæíîñòü, ÷èñëî òàêòîâ ÄÌÒ).
Îïðåäåëåíèå 2. Äëÿ ôèêñèðîâàííîãî ýêçåìïëÿðà I �� îáîçíà÷èì
C I I I I( ) :� � ��{ }efp .
Îïðåäåëåíèå 3. Ïðîâåäåíèå ïîñòîïòèìàëüíîãî àíàëèçà äëÿ ïàðû ( , ( ) )I I{ }�
áóäåò ýôôåêòèâíûì, åñëè { }�( ) ( )I C I
.
Ïóñòü t I I( , )� — ñëîæíîñòü (÷èñëî øàãîâ, òàêòîâ ÄÌÒ) ïîëó÷åíèÿ îïòèìàëüíî-
ãî ðåøåíèÿ �I , èñõîäÿ èç îïòèìàëüíîãî ðåøåíèÿ I.
Îïðåäåëåíèå 4. Compl { } { }
{ }
( , ( ) ) max ( , )
( )
I I t I I
I I
�
�
� �
��
.
Âåëè÷èíó Compl { }( , ( ) )I I� ìîæíî ñ÷èòàòü ÷èñëîâîé õàðàêòåðèñòèêîé ñëîæíîñ-
òè ïîñòîïòèìàëüíîãî àíàëèçà äëÿ ïàðû ( , ( ) )I I{ }� . Ñîãëàñíî îïðåäåëåíèþ 3 ïðè
ïðîâåäåíèè ýôôåêòèâíîãî ïîñòîïòèìàëüíîãî àíàëèçà âåëè÷èíà Compl { }( , ( ) )I I� —
íå áîëåå ÷åì ïîëèíîì îò ðàçìåðíîñòè çàäà÷è.
Îïðåäåëåíèå 5. Äëÿ NP-òðóäíîé (âîçìîæíî, ïîëíîé) îïòèìèçàöèîííîé ïðîá-
ëåìû � ïîëîæèì
Compl {Compl { } }
{ }
( ) max ( , ( ) )
, ( )
� �
I I
I I
�
� .
Âåëè÷èíó Compl ( )� ìîæíî ñ÷èòàòü ÷èñëîâîé õàðàêòåðèñòèêîé ñëîæíîñòè
ïðîâåäåíèÿ ïîñòîïòèìàëüíîãî àíàëèçà ïðîáëåìû � .
Ïðåäñòàâëÿåò èíòåðåñ âûäåëåíèå äëÿ ýêçåìïëÿðà I �� òàêèõ { }�( )I , ÷òî
Compl { }( , ( ) )I I� — íå áîëåå ÷åì ïîëèíîì îò ðàçìåðíîñòè çàäà÷è, à òàêæå îöåíêà
ñâåðõó è ñíèçó âåëè÷èíû Compl ( )� äëÿ êîíêðåòíûõ ïðîáëåì � .
Çàìå÷àíèå 1. Ïîñòîïòèìàëüíûé àíàëèç òîé èëè èíîé çàäà÷è äèñêðåòíîãî ïðî-
ãðàììèðîâàíèÿ ïðîâîäèòñÿ íà îñíîâå íåêîòîðîãî îïðåäåëåííîãî ïîäõîäà (ìåòîäà),
ïðèìåíÿåìîãî äëÿ ðåøåíèÿ ýòîé çàäà÷è. Èçâåñòíû ïðîöåäóðû ïîñòîïòèìàëüíîãî
àíàëèçà çàäà÷ öåëî÷èñëåííîãî ïðîãðàììèðîâàíèÿ, îñíîâàííûå íà ìåòîäå îòñå÷å-
íèé Ãîìîðè, íà ìåòîäå âåòâåé è ãðàíèö [3, 4]. Òàêèì îáðàçîì, ìîæíî ñ÷èòàòü, ÷òî
ôóíêöèè Compl { }( , ( ) )I I� , Compl ( )� çàâèñÿò è îò ìåòîäà (àëãîðèòìà) ðåøåíèÿ èñ-
õîäíîé çàäà÷è I.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 5 137
ÂÅÐÕÍßß È ÍÈÆÍßß ÎÖÅÍÊÀ ÄËß Compl ( )�
Ïóñòü � — íåêîòîðàÿ NP-ïîëíàÿ îïòèìèçàöèîííàÿ ïðîáëåìà.
Òåîðåìà 1. Compl poly( ) ( )( )� �O n2 .
Äîêàçàòåëüñòâî. Îáîçíà÷èì DTIME( ( ))T n (ñîîòâåòñòâåííî NTIME( ( ))T n )
êëàññ ñëîæíîñòè ïðîáëåì, äëÿ ðåøåíèÿ êîòîðûõ íà äåòåðìèíèðîâàííîé (íåäåòåð-
ìèíèðîâàííîé) ìàøèíå Òüþðèíãà òðåáóåòñÿ âðåìÿ O T n( ( )). Èçâåñòíî [6], ÷òî
P n
n
� �
poly
DTIME poly
( )
( ( )) , NP n
n
� �
poly
NTIME poly
( )
( ( )) , NP
EXPTIME,(1)
EXPTIME DTIME
poly
poly� �
( )
( )( )
n
n2 . (2)
Ïóñòü { }� — ìíîæåñòâî âñåõ ýêçåìïëÿðîâ çàäà÷è � . Ðàññìîòðèì ýêçåìïëÿð
I1 �{ }� òàêîé, ÷òî îïòèìàëüíîå ðåøåíèå I1 íå äàåò íèêàêîé èíôîðìàöèè äëÿ ðåøå-
íèÿ ïðîèçâîëüíîé � �I I{ }� \ 1 (äëÿ êàæäîé êîíêðåòíîé çàäà÷è � òàêîé ýêçåìïëÿð I1
âñåãäà íàéäåòñÿ). Äëÿ òàêîé çàäà÷è I1 ïîëîæèì { } { }�( ) \I I1 1� � è ðàññìîòðèì ïàðó
( , ( ) )I I1 1{ }� . Ñîãëàñíî îïðåäåëåíèÿì 4 è 5 è â ñèëó âûáîðà I1 è { }�( )I1 áóäåì èìåòü
Compl {Compl { } }
{ }
( ) max ( , ( ) )
, ( )
� � �
I I
I I
�
�
� �max max ( , ( ) ) max
( ) ( )I I I I
I I{ {Compl { } }} { max {
{ } { }� �
� max ( , )
( )�
� �
I I
t I I
{ }
{ }}}
�
� � � �
�� ��
max ( , ) max ( )
( )I I I I
t I I I
1 1
1{ max { } {time }
{ } { }� �
,
ãäå time ( )�I — âðåìåííàÿ ñëîæíîñòü ÄÌÒ äëÿ ðåøåíèÿ �I . Ñîãëàñíî (1), (2)
max ( ) ( )( )
��
� �
I
nI O
{ }
poly{time }
�
2 , ÷òî è äîêàçûâàåò òåîðåìó 1.
Óñòàíîâèì íèæíþþ îöåíêó Compl ( )� â êëàññå ìåòîäîâ âåòâåé è ãðàíèö äëÿ
çàäà÷è � îäíîìåðíîé çàäà÷è î ðàíöå.
Ïðîöåññ ðåøåíèÿ çàäà÷è ìåòîäîì âåòâåé è ãðàíèö ìîæíî ïðåäñòàâèòü â âèäå
äåðåâà âåòâëåíèÿ, âåðøèíàì êîòîðîãî ñîîòâåòñòâóþò ñîçäàâàåìûå ïîäçàäà÷è.
Ñëîæíîñòü ðåøåíèÿ çàäà÷è ìåòîäîì âåòâåé è ãðàíèö ïðèíÿòî îïðåäåëÿòü êàê ÷èñëî
âåðøèí Va â äåðåâå âåòâëåíèÿ [7].  îáîèõ ñëó÷àÿõ ýòà âåëè÷èíà èìååò îäèí è òîò
æå ïîðÿäîê, òàê êàê ÷èñëî êîíöåâûõ âåðøèí ñâÿçàíî ñ îáùèì ÷èñëîì âåðøèí â
äåðåâå âåòâëåíèÿ ñîîòíîøåíèåì V Va t� �2 1.
Ðàññìîòðèì èçâåñòíóþ çàäà÷ó Ôèíêåëüøòåéíà [8]:
max ( ){ }f x xi
i
n
�
�
� 2
1
, (3)
2 2
2
1
1
x
n
j
j
n
�
� � �
��
�
��
� , (4)
x i ni � �{ }0 1 1, , , ,� . (5)
Âñå ìíîæåñòâî îïòèìàëüíûõ ðåøåíèé ýòîé çàäà÷è ñîñòîèò èç âñåõ âåêòîðîâ,
ñîäåðæàùèõ
n
2
�
��
�
��
åäèíè÷íûõ è n
n
–
2
�
��
�
��
�
�
�
�
�
� íóëåâûõ êîìïîíåíò.
Òåîðåìà 2 [8].V Ca n
n
� �
�
�
��
�
��
�
2 1
1
2
1
, ãäåVa — ÷èñëî âåðøèí â äåðåâå âåòâëåíèé.
Åñëè ñëîæíîñòü ðåøåíèÿ çàäà÷è ìåòîäîì âåòâåé è ãðàíèö — ÷èñëî êîíöåâûõ
âåðøèí â äåðåâå âåòâëåíèÿ, òî ìîæíî ïîêàçàòü, ÷òî ïðè ëþáîì ñïîñîáå âûáîðà
î÷åðåäíîé ïîäçàäà÷è è ïåðåìåííîé äëÿ âåòâëåíèÿ ñëîæíîñòü ðåøåíèÿ (3)–(5) ðàâíà
V Ct n
n
�
�
�
��
�
��
�
1
2
1
.
138 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 5
 [9] ïîêàçàíî, ÷òî åñëè äëÿ âåòâëåíèÿ âûáèðàåòñÿ ïåðåìåííàÿ ñ íàèáîëüøèì
âåñîì, òî ñëîæíîñòü ðåøåíèÿ çàäà÷è î ðàíöå ñ n ïåðåìåííûìè íå ïðåâîñõîäèò Vt ,
ò.å. çàäà÷à (3)–(5) èìååò ìàêñèìàëüíóþ ñëîæíîñòü ðåøåíèÿ.
Òåîðåìà 3. Ïðè èñïîëüçîâàíèè ìåòîäà âåòâåé è ãðàíèö äëÿ ðåøåíèÿ �
Compl ( )� �
�
�
�
�
�
�
�
�
�
2
1
n
n
.
Äîêàçàòåëüñòâî. Ñîãëàñíî îïðåäåëåíèÿì 4 è 5 íóæíî ïîêàçàòü, ÷òî ñóùåñòâó-
þò òàêèå ýêçåìïëÿðû I I I1 1, ( )� �{ }� , ÷òî t I I c
n
n
( , )1
2
1
�
�
, c �const.  êà÷åñòâå I1
âîçüìåì çàäà÷ó î ðàíöå:
max 2
1
xi
i
n
�
�
�
�
�
!
"
, ( )�3
2 2
21
x
n
j
j
n
�
� � �
��
�
��
,
( )�4
x i ni � �{ }01 1, , ,... , , ( )�5
à â êà÷åñòâå �I — çàäà÷ó (3)–(5) (çàäà÷è I1 è �I îòëè÷àþòñÿ ïðàâûìè ÷àñòÿìè (4)
è ( )�4 . Îïòèìàëüíîå ðåøåíèå çàäà÷è I1 (ñ
n
2
�
��
�
��
åäèíèöàìè) — äîïóñòèìîå ðåøå-
íèå �I . Ñîãëàñíî òåîðåìå 2 ñëîæíîñòü ðåøåíèÿ çàäà÷è �I (çàäà÷è Ôèíêåëüøòåéíà)
ðàâíà V Ct n
n
�
�
�
��
�
��
�
1
2
1
— ÷èñëó êîíöåâûõ âåðøèí â äåðåâå âåòâëåíèÿ. Òàêèì îáðà-
çîì, íåîáõîäèìî ïåðåáðàòü âñå êîíöåâûå âåðøèíû Vt äåðåâà âåòâëåíèÿ äëÿ äî-
êàçàòåëüñòâà îïòèìàëüíîñòè ïîëó÷åííîãî ðåøåíèÿ (ïðè ýòîì îöåíêè âîîáùå íå
ñïîñîáñòâóþò óìåíüøåíèþ ïåðåáîðà), ïîýòîìó
t I I V C C
n
t n
n
n
n n
( , ) ~ ~
(
1 1
2
1
1
1
2
3
22
�
�
�
�
��
�
��
�
�
��
��
�
��
�
� �
�
�1
2
1)
c
n
n
,
ãäå c �
2
3
2
�
.
Çàìå÷àíèå 2.  [10] ïîêàçàíî, ÷òî ñóùåñòâóþò çàäà÷è, ñëîæíîñòü ðåøåíèÿ êî-
òîðûõ ìåòîäîì âåòâåé è ãðàíèö ïðåâîñõîäèò àñèìïòîòè÷åñêè â
3
2
�� ðàç ñëîæíîñòü
ðåøåíèÿ çàäà÷è Ôèíêåëüøòåéíà (3)–(5) ñ òåì æå ÷èñëîì ïåðåìåííûõ. Ýòî äàåò
îñíîâàíèå ïðåäïîëîæèòü, ÷òî îöåíêà èç òåîðåìû 3 âðÿä ëè óëó÷øàåìà (ïî êðàéíåé
ìåðå, â êëàññå ìåòîäîâ âåòâåé è ãðàíèö äëÿ îäíîìåðíîé çàäà÷è î ðàíöå).
ÂÛÄÅËÅÍÈÅ ÊËÀÑÑΠÇÀÄÀ× Î ÏÎÊÐÛÒÈÈ, ÄËß ÊÎÒÎÐÛÕ
Compl ( { ( )}) (poly ( ))I I O n, � �
NP-ïîëíóþ çàäà÷ó î ïîêðûòèè ðàññìîòðèì â ïîñòàíîâêå
min ( ) | ( )f x c x x Q Ai i
i
n
� �
�
�
�
!
"�
�
1
,
Q A x B a x i mn
i j j
j
n
( ) , ,... ,,� �
�
�
�
#
�#
!
#
"#�
� 1 1
1
, (6)
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 5 139
B n n�{ }0 1, , A ai j�{ }, , i m�1, ,� ; j n�1,... , ; A — ( , )m n -áóëåâà ìàòðèöà ( )m n� ;
ci $ 0, i n�1, ,� .
Îïðåäåëåíèå 6 [11, 12]. Ìàòðèöà A aij�{ } ( , , ; ,... , )i m j n� �1 1� íàçûâàåòñÿ
âïîëíå óíèìîäóëÿðíîé, åñëè ëþáîé åå ìèíîð ðàâåí 0, �1 èëè �1.
 ÷àñòíîñòè, ëþáîé ýëåìåíò òàêîé ìàòðèöû ðàâåí 0, �1 èëè �1.
Ðàññìîòðèì õàðàêòåðèçàöèþ Õîôôìàíà–Êðàñêàëà (Hoffman–Kraskal) âïîëíå
óíèìîäóëÿðíûõ ìàòðèö, ñâÿçûâàþùóþ òåîðèþ âïîëíå óíèìîäóëÿðíûõ ìàòðèö ñ
ëèíåéíûì öåëî÷èñëåííûì ïðîãðàììèðîâàíèåì.
Òåîðåìà 4 [11, 12] (Õîôôìàí, Êðàñêàë). Öåëî÷èñëåííàÿ ìàòðèöà A âïîëíå
óíèìîäóëÿðíà òîãäà è òîëüêî òîãäà, êîãäà äëÿ ëþáîãî öåëî÷èñëåííîãî âåêòîðà b
ïîëèýäð { }x x Ax b| ,
�0 öåëî÷èñëåííûé.
Ñëåäñòâèå 1 [11, 12]. Öåëî÷èñëåííàÿ ìàòðèöà A âïîëíå óíèìîäóëÿðíà òîãäà è
òîëüêî òîãäà, êîãäà äëÿ ëþáûõ öåëî÷èñëåííûõ âåêòîðîâ a b c d, , , âñå âåðøèíû ïî-
ëèýäðà { }x c x d a Ax b| ;� � � � öåëî÷èñëåííû.
Ñëåäñòâèå 2 [11, 12]. Öåëî÷èñëåííàÿ ìàòðèöà A âïîëíå óíèìîäóëÿðíà òîãäà è
òîëüêî òîãäà, êîãäà âñå âåðøèíû ïîëèýäðîâ
{ } { }x x c Ax b x x c b Ax| , , | ,� � � � , { } { }x c x Ax b x c x b Ax| , , | ,� � � �
öåëî÷èñëåííû äëÿ ëþáîãî öåëî÷èñëåííîãî âåêòîðà b è íåêîòîðîãî öåëî÷èñëåí-
íîãî âåêòîðà c.
Ñëåäñòâèå 3. Ïîëèýäð çàäà÷è î ïîêðûòèè (6) { }x x Ax| ,
�0 1 ÿâëÿåòñÿ öåëî-
÷èñëåííûì, åñëè (0,1)-ìàòðèöà A âïîëíå óíèìîäóëÿðíà.
Ñëåäñòâèå 3 ïîëó÷àåì èç ñëåäñòâèé 1 è 2.
Èñïîëüçóåì ïîëèíîìèàëüíûå àëãîðèòìû â ëèíåéíîì ïðîãðàììèðîâàíèè
[11, 12] (ìåòîä ýëëèïñîèäîâ Õà÷èÿíà, ìåòîä Êàðìàðêàðà). Ñîãëàñíî ýòèì ðåçóëüòà-
òàì, åñëè ìàòðèöà A âïîëíå óíèìîäóëÿðíà, òî çàäà÷ó î ïîêðûòèè (6) ìîæíî ðåøèòü
ñ ïîëèíîìèàëüíîé ñëîæíîñòüþ (ñëåäñòâèå 3).
Ïðèìåðîì âïîëíå óíèìîäóëÿðíûõ ìàòðèö ÿâëÿþòñÿ ìàòðèöû ñåòåé (ìàòðèöû
ïóòåé, ìàòðèöû õîðä). Ïóñòü D V A� ( , ) — îðèåíòèðîâàííûé ãðàô è T V A� ( , )0 —
ïðîèçâîëüíîå îðèåíòèðîâàííîå äåðåâî ñ òåì æå ìíîæåñòâîì âåðøèíV. Ðàññìîòðèì
(| | | | )A A0 % -ìàòðèöó M, îïðåäåëÿåìóþ ñëåäóþùèì îáðàçîì. Äëÿ âñåõ � �a A0 è
a v w A� �( , ) ïîëîæèì:
� M a a� � �, 1, åñëè åäèíñòâåííûé îðèåíòèðîâàííûé ( )v w� -ïóòü â T ïðîõîäèò
÷åðåç �a â ïðÿìîì íàïðàâëåíèè;
� M a a� � �, 1, åñëè åäèíñòâåííûé îðèåíòèðîâàííûé ( )v w� -ïóòü â T ïðîõîäèò
÷åðåç �a â îáðàòíîì íàïðàâëåíèè;
� M a a� �, 0 , åñëè åäèíñòâåííûé îðèåíòèðîâàííûé ( )v w� -ïóòü â T íå ïðîõîäèò
÷åðåç �a .
Ìàòðèöû, ïîëó÷àþùèåñÿ òàêèì îáðàçîì, íàçûâàþòñÿ ñåòåâûìè. Ïðîèçâîëü-
íóþ ( , )0 1 -ìàòðèöó ñåòè ìîæíî ïîëó÷èòü ñ îðèåíòèðîâàííîãî äåðåâà T, âûáðàâ â
íåì íåêîòîðûå îðèåíòèðîâàííûå ïóòè, à â êà÷åñòâå ñòîëáöîâ âçÿòü ìàòðèöû âåêòî-
ðîâ èíöèäåíöèé ýòèõ ïóòåé (÷òî ðàññìàòðèâàåòñÿ êàê âåêòîðû â R
A| |0 , ãäå A0 —
ìíîæåñòâî äóã â T).  ÷àñòíîñòè, ìàòðèöà èíöèäåíöèé äâóäîëüíîãî
íåîðèåíòèðîâàííîãî ãðàôà — ñåòåâàÿ ( , )0 1 -ìàòðèöà.
Îäíàêî ñóùåñòâóþò âïîëíå óíèìîäóëÿðíûå (0,1)-ìàòðèöû, êîòîðûå íå ÿâëÿ-
þòñÿ ìàòðèöàìè ñåòåé, íàïðèìåð ìàòðèöà B10 [11]:
B10
1 1 1 1 1
1 1 1 0 0
1 0 1 1 0
1 0 0 1 1
1 1 0 0 1
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
.
140 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 5
 äàëüíåéøåì áóäåì ðàññìàòðèâàòü ïðåîáðàçîâàíèÿ è îïåðàöèè íàä ìàòðèöà-
ìè, ñîõðàíÿþùèå ïîëíóþ óíèìîäóëÿðíîñòü.
Êëàññ ìàòðèö ñåòåé (è âïîëíå óíèìîäóëÿðíûõ ìàòðèö) çàìêíóò îòíîñèòåëüíî
âåäóùèõ ïðåîáðàçîâàíèé (ñèìïëåêñ-ïðåîáðàçîâàíèé ñ âåäóùèì ýëåìåíòîì �), ò.å.
îïåðàöèé âèäà
� � �
� �
c
b D
c
b D bc
�
�
�
�
�
� &
�
�
�
�
�
�
�
� ,
ãäå �� '{ }1 , b — âåêòîð-ñòîëáåö, c — âåêòîð-ñòðîêà, D — íåêîòîðàÿ ìàòðèöà.
Ïðèìåð. Äëÿ âåäóùåãî ýëåìåíòà (1,1) ïîëó÷èì
B B�
�
�
�
�
�
�
�
�
�
�
& � �
�
�
�
�
�
�
�
�
�
�
1 0 1 1
1 1 0 1
0 1 1 1
1 0 1 1
1 1 1 0
0 1 1 1
.
Èòàê, ðàññìîòðèì ñëåäóþùèå ïðåîáðàçîâàíèÿ è îïåðàöèè, ñîõðàíÿþùèå
ïîëíóþ óíèìîäóëÿðíîñòü ìàòðèö [11]:
a) ïåðåñòàíîâêà ñòðîê è ñòîëáöîâ;
á) òðàíñïîíèðîâàíèå;
â) âåäóùåå ïðåîáðàçîâàíèå (îïåðàöèÿ çàìåùåíèÿ)
� � �
� �
c
b D
c
b D bc
�
�
�
�
�
� &
�
�
�
�
�
�
�
� ; (7)
ã) ïðèïèñûâàíèå íóëåâîé ñòðîêè èëè íóëåâîãî ñòîëáöà, ñòðîêè ëèáî
ñòîëáöà ñ îäíîé åäèíèöåé;
ä) ïîâòîðåíèå ñòðîêè èëè ñòîëáöà;
(1 — ñóììà) A B
A
B
( �
�
�
�
�
�
�1
0
0
;
(2 — ñóììà) [ ]Aa
b
B
A ab
B
(
�
�
�
�
�
� �
�
�
�
�
�
�2
0
;
(3 — ñóììà)
A a a
c
b
d d B
A ab
dc B0 1
1 0
3
�
�
�
�
�
� (
�
�
�
�
�
� �
�
�
�
�
�
� (8)
(A B, — ìàòðèöû; à), ã) — âåêòîð-ñòîëáöû; á), â) — âåêòîð-ñòðîêè ñîîòâåòñòâó-
þùèõ ðàçìåðîâ).
Òåîðåìà 5 [11, 12] (òåîðåìà Ñåéìóðà [Seymour] î ðàçëîæåíèè âïîëíå óíèìî-
äóëÿðíûõ ìàòðèö). Ìàòðèöà A âïîëíå óíèìîäóëÿðíà òîãäà è òîëüêî òîãäà, êîãäà A
ìîæåò áûòü ïîëó÷åíà èç ìàòðèö ñåòåé è ìàòðèöû B10 ñ ïîìîùüþ îïåðàöèé (7) è (8).
Ïðè ýòîì îïåðàöèè (8) ïðèìåíÿþòñÿ â òîì è òîëüêî òîì ñëó÷àå, åñëè äëÿ êàæäîé
ìàòðèöû A è B ñóììà ÷èñëà ñòðîê è ÷èñëà ñòîëáöîâ íå ìåíüøå ÷åòûðåõ.
Ïóñòü I n — ýêçåìïëÿð çàäà÷è î ïîêðûòèè (6) , óäîâëåòâîðÿþùèé óñëîâèÿì:
� âåêòîð c c cn� ( , , )1 � ïðîèçâîëüíûé;
� ìàòðèöà A aij�{ } — ëèáî ñåòåâàÿ ìàòðèöà, ëèáî ìàòðèöà B10 .
Ìíîæåñòâî ýêçåìïëÿðîâ { }�n nI( ) ñòðîèòñÿ òàêèì îáðàçîì:
� �I In n{ }� ( ) , åñëè âûïîëíÿþòñÿ óñëîâèÿ:
� âåêòîð � � � �c c cn( ,... , )1 çàäà÷è �I ïðîèçâîëüíûé;
�ìàòðèöà � � �A aij{ }ïîëó÷àåòñÿ èç ìàòðèöû A ñ ïîìîùüþ êîíå÷íîãî ÷èñëà ïðå-
îáðàçîâàíèé è îïåðàöèé (7) è (8).
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 5 141
Òåîðåìà 6. Compl { } poly( , ( ) ) ( ( ))I I O nn n n� � .
Äîêàçàòåëüñòâî. Ïóñòü x x xn
* * *( ,... , )� 1 — îïòèìàëüíîå ðåøåíèå ýêçåìïëÿðà
I n çàäà÷è (6) (êîòîðîå ñ ïîìîùüþ ìåòîäà ýëëèïñîèäîâ Õà÷èÿíà èëè ìåòîäîì Êàð-
ìàðêàðà ìîæíî íàéòè ñ ïîëèíîìèàëüíîé ñëîæíîñòüþ). Ðàññìîòðèì ïðîèçâîëüíûé
ýêçåìïëÿð � �I In n{ }� ( ) . Ñîãëàñíî òåîðåìå 5 ìàòðèöà �A ýêçåìïëÿðà �I âïîëíå
óíèìîäóëÿðíà. Ïóñòü x* — äîïóñòèìîå ðåøåíèå �I . Òîãäà, èñõîäÿ èç x* , ñ ïîëè-
íîìèàëüíîé ñëîæíîñòüþ (ìåòîäîì Õà÷èÿíà èëè Êàðìàðêàðà, ñëåäñòâèå 3), ìîæ-
íî íàéòè îïòèìàëüíîå ðåøåíèå �I . Åñëè x* íå ÿâëÿåòñÿ äîïóñòèìûì ðåøåíèåì �I ,
òî èñõîäÿ èç íà÷àëüíîãî ïîêðûòèÿ x0 1 1� ( , , )� çàäà÷è (6) ñ ïîëèíîìèàëüíîé ñëîæ-
íîñòüþ ìîæíî íàéòè îïòèìàëüíîå ðåøåíèå �I .
Òåîðåìà äîêàçàíà.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. Ê î ç å ð à ö ê à ÿ Ë . Í . , Ë å á å ä å â à Ò . Ò . , Ñ å ð ã è å í ê î È .  . Âîïðîñû óñòîé÷èâîñòè,
ïàðàìåòðè÷åñêèé è ïîñòîïòèìàëüíûé àíàëèç çàäà÷ äèñêðåòíîé îïòèìèçàöèè // Êèáåðíåòèêà. —
1983. — ¹ 4. — Ñ. 71– 80.
2. Ñ å ð ã è å í ê î È .  . , Ø è ë î  . Ï . Çàäà÷è äèñêðåòíîé îïòèìèçàöèè. Ïðîáëåìû, ìåòîäû
ðåøåíèÿ, èññëåäîâàíèÿ. — Êèåâ: Íàóê. äóìêà, 2003. — 261 ñ.
3. G e o f f r i o n A . M . , N a u s s R . Parametric and postoptimality analysis in integer linear programming
// Management Sci. — 1977. — 23, N 5. — P. 453–466.
4. R o o d m a n G . M . Post optimality analysis in zero one programming by implicit enumeration // Naval
Res. Logist. Quart. — 1972. — 19, N 3. — P. 435–447.
5. G r e e n b e r g H . J . An annotated bibliography for post-solution analysis in mixed integer programming
and combinatorial optimization / D.L. Woodruff (ed.) // Advances in Comput. and Stochast. optimization,
Logic Program., and Heuristic search. — Berlin: Kluwer Academ. Publ., 1998. — P. 97–148.
6. E i t a n M . G u r a r i . An Introduction to the Theory of Computation. — Ohio State University: Comput.
Sci. Press, 1989.
7. à ð è ø ó õ è í  . Ï . Ýôôåêòèâíîñòü ìåòîäà âåòâåé è ãðàíèö â çàäà÷àõ ñ áóëåâûìè ïåðåìåííûìè //
Èññëåäîâàíèÿ ïî äèñêðåòíîé îïòèìèçàöèè. — Ì.: Íàóêà, 1976. — Ñ. 203–230.
8. Ô è í ê å ë ü ø ò å é í Þ . Þ . Ïðèáëèæåííûå ìåòîäû è ïðèêëàäíûå çàäà÷è äèñêðåòíîãî
ïðîãðàììèðîâàíèÿ. — Ì.: Íàóêà, 1976. — 264 ñ.
9. Ê î ë ï à ê î â Ð . Ì . , Ï î ñ û ï ê è í Ì . À . , Ñ è ã à ë È . Õ . Î ñëîæíîñòè ðåøåíèÿ çàäà÷è î áóëåâîì
ðàíöå // Òð. VII Ìåæäóíàð. êîíô. «Äèñêðåòíûå ìîäåëè â òåîðèè óïðàâëÿþùèõ ñèñòåì». — Ì.:
ÌÀÊÑÏðåññ, 2006. — Ñ. 166–171.
10. Ê î ë ï à ê î â Ð . Ì . , Ï î ñ û ï ê è í Ì . À . Àñèìïòîòè÷åñêàÿ îöåíêà ñëîæíîñòè ìåòîäà âåòâåé
è ãðàíèö ñ âåòâëåíèåì ïî äðîáíîé ïåðåìåííîé äëÿ çàäà÷è î ðàíöå // Äèñêðåòíûé àíàëèç
è èññëåäîâàíèå îïåðàöèé. — 2008 — 15, ¹ 1. — Ñ. 58–81.
11. Ñ õ ð å é â å ð À . Òåîðèÿ ëèíåéíîãî è öåëî÷èñëåííîãî ïðîãðàììèðîâàíèÿ. Ò. 1. — Ì.: Ìèð, 1991. —
360 ñ.
12. Ñ õ ð å é â å ð À . Òåîðèÿ ëèíåéíîãî è öåëî÷èñëåííîãî ïðîãðàììèðîâàíèÿ. Ò. 2. — Ì.: Ìèð, 1991. —
342 ñ.
Ïîñòóïèëà 10.12.2009
142 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 5
|