О сложности вычисления параметров устойчивости в задачах булева программирования
Показано, что для NP-полных задач трудоемким является даже вычисление шара устойчивости радиуса 1 оптимального решения (т.е. при P ≠ NP для этого не существует полиномиального алгоритма). При использовании жадных алгоритмов для задачи о покрытии множествами (задачи о ранце) при радиусе устойчивости...
Saved in:
| Published in: | Кибернетика и системный анализ |
|---|---|
| Date: | 2015 |
| Main Authors: | , |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2015
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/124906 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | О сложности вычисления параметров устойчивости в задачах булева программирования / В.А. Михайлюк, Н.В. Лищук // Кибернетика и системный анализ. — 2015. — Т. 51, № 5. — С. 56-62. — Бібліогр.: 14 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-124906 |
|---|---|
| record_format |
dspace |
| spelling |
Михайлюк, В.А. Лищук, Н.В. 2017-10-11T16:56:13Z 2017-10-11T16:56:13Z 2015 О сложности вычисления параметров устойчивости в задачах булева программирования / В.А. Михайлюк, Н.В. Лищук // Кибернетика и системный анализ. — 2015. — Т. 51, № 5. — С. 56-62. — Бібліогр.: 14 назв. — рос. 0023-1274 https://nasplib.isofts.kiev.ua/handle/123456789/124906 519.854 Показано, что для NP-полных задач трудоемким является даже вычисление шара устойчивости радиуса 1 оптимального решения (т.е. при P ≠ NP для этого не существует полиномиального алгоритма). При использовании жадных алгоритмов для задачи о покрытии множествами (задачи о ранце) при радиусе устойчивости r = O(1) существуют полиномиальные алгоритмы вычисления шара устойчивости радиуса r lnm-приближенного решения (1-приближенного решения). Показано, що для NP-повних задач трудомістким є навіть обчислення кулі стійкості радіуса 1 оптимального розв’язку (тобто при P ≠ NP для цього розв’язку не існує поліноміального алгоритму). При використанні жадібних алгоритмів для задачі про покриття множинами (задачі про рюкзак) при радіусі стійкості r = O(1) існують поліноміальні алгоритми обчислення кулі стійкості радіуса r ln m-наближеного розв’язку (1-наближеного розв’язку). The authors show that even calculating the stability ball of radius 1 of the optimal solution is cumbersome for NP-hard problems (i.e., a polynomial algorithm does not exist unless P ≠ NP ). When greedy algorithms are used for set covering problem (knapsack problem) for stability radius r =O(1 ), polynomial algorithms of calculating the stability ball of radius r of ln m-approximate solution (1-àpproximate solution) exist. ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Кибернетика О сложности вычисления параметров устойчивости в задачах булева программирования Про складність обчислення параметрів стійкості в задачах булевого програмування The complexity of calculating sensitivity parameters in Boolean programming problems 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 |
2015 |
| language |
Russian |
| container_title |
Кибернетика и системный анализ |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| format |
Article |
| title_alt |
Про складність обчислення параметрів стійкості в задачах булевого програмування The complexity of calculating sensitivity parameters in Boolean programming problems |
| description |
Показано, что для NP-полных задач трудоемким является даже вычисление шара устойчивости радиуса 1 оптимального решения (т.е. при P ≠ NP для этого не существует полиномиального алгоритма). При использовании жадных алгоритмов для задачи о покрытии множествами (задачи о ранце) при радиусе устойчивости r = O(1) существуют полиномиальные алгоритмы вычисления шара устойчивости радиуса r lnm-приближенного решения (1-приближенного решения).
Показано, що для NP-повних задач трудомістким є навіть обчислення кулі стійкості радіуса 1 оптимального розв’язку (тобто при P ≠ NP для цього розв’язку не існує поліноміального алгоритму). При використанні жадібних алгоритмів для задачі про покриття множинами (задачі про рюкзак) при радіусі стійкості r = O(1) існують поліноміальні алгоритми обчислення кулі стійкості радіуса r ln m-наближеного розв’язку (1-наближеного розв’язку).
The authors show that even calculating the stability ball of radius 1 of the optimal solution is cumbersome for NP-hard problems (i.e., a polynomial algorithm does not exist unless P ≠ NP ). When greedy algorithms are used for set covering problem (knapsack problem) for stability radius r =O(1 ), polynomial algorithms of calculating the stability ball of radius r of ln m-approximate solution (1-àpproximate solution) exist.
|
| issn |
0023-1274 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/124906 |
| citation_txt |
О сложности вычисления параметров устойчивости в задачах булева программирования / В.А. Михайлюк, Н.В. Лищук // Кибернетика и системный анализ. — 2015. — Т. 51, № 5. — С. 56-62. — Бібліогр.: 14 назв. — рос. |
| work_keys_str_mv |
AT mihailûkva osložnostivyčisleniâparametrovustoičivostivzadačahbulevaprogrammirovaniâ AT liŝuknv osložnostivyčisleniâparametrovustoičivostivzadačahbulevaprogrammirovaniâ AT mihailûkva proskladnístʹobčislennâparametrívstíikostívzadačahbulevogoprogramuvannâ AT liŝuknv proskladnístʹobčislennâparametrívstíikostívzadačahbulevogoprogramuvannâ AT mihailûkva thecomplexityofcalculatingsensitivityparametersinbooleanprogrammingproblems AT liŝuknv thecomplexityofcalculatingsensitivityparametersinbooleanprogrammingproblems |
| first_indexed |
2025-11-25T22:43:40Z |
| last_indexed |
2025-11-25T22:43:40Z |
| _version_ |
1850570123290607616 |
| fulltext |
ÓÄÊ 519.854
Â.À. ÌÈÕÀÉËÞÊ, Í.Â. ËÈÙÓÊ
Î ÑËÎÆÍÎÑÒÈ ÂÛ×ÈÑËÅÍÈß ÏÀÐÀÌÅÒÐΠÓÑÒÎÉ×ÈÂÎÑÒÈ
 ÇÀÄÀ×ÀÕ ÁÓËÅÂÀ ÏÐÎÃÐÀÌÌÈÐÎÂÀÍÈß
Àííîòàöèÿ. Ïîêàçàíî, ÷òî äëÿ NP-ïîëíûõ çàäà÷ òðóäîåìêèì ÿâëÿåòñÿ äàæå âû÷èñëåíèå
øàðà óñòîé÷èâîñòè ðàäèóñà 1 îïòèìàëüíîãî ðåøåíèÿ (ò.å. ïðè P NP� äëÿ ýòîãî íå ñó-
ùåñòâóåò ïîëèíîìèàëüíîãî àëãîðèòìà). Ïðè èñïîëüçîâàíèè æàäíûõ àëãîðèòìîâ äëÿ çàäà-
÷è î ïîêðûòèè ìíîæåñòâàìè (çàäà÷è î ðàíöå) ïðè ðàäèóñå óñòîé÷èâîñòè r O� ( )1 ñóùåñò-
âóþò ïîëèíîìèàëüíûå àëãîðèòìû âû÷èñëåíèÿ øàðà óñòîé÷èâîñòè ðàäèóñà r ln m-ïðèáëè-
æåííîãî ðåøåíèÿ (1-ïðèáëèæåííîãî ðåøåíèÿ).
Êëþ÷åâûå ñëîâà: ñëîæíîñòü àíàëèçà óñòîé÷èâîñòè, ðàäèóñ óñòîé÷èâîñòè çàäà÷è, øàð
óñòîé÷èâîñòè ðàäèóñà r �-ïðèáëèæåííîãî ðåøåíèÿ çàäà÷è.
ÂÂÅÄÅÍÈÅ
Àíàëèç óñòîé÷èâîñòè çàäà÷ äèñêðåòíîãî ïðîãðàììèðîâàíèÿ ñâîäèòñÿ ê îïðåäå-
ëåíèþ òàêèõ èçìåíåíèé ïàðàìåòðîâ (êîýôôèöèåíòîâ) èñõîäíîé çàäà÷è, ïðè
êîòîðûõ îïòèìàëüíîå ðåøåíèå îñòàåòñÿ áåç èçìåíåíèé [1]. Êàê ïðàâèëî,
óñòîé÷èâîñòü îïòèìàëüíîãî èëè ïðèáëèæåííîãî ê íåìó ðåøåíèÿ õàðàêòåðèçó-
åòñÿ íåêîòîðûìè ïàðàìåòðàìè: îáëàñòü, øàð, ðàäèóñ óñòîé÷èâîñòè è ò.ä. [2–4].
 ðàáîòå [2] ðàññìîòðåíû îáùèå ïîíÿòèÿ òåîðèè óñòîé÷èâîñòè è ââåäåíî âàæ-
íîå ïîíÿòèå ðàäèóñà óñòîé÷èâîñòè çàäà÷è.  [3] èçó÷àþòñÿ âîïðîñû âû÷èñëå-
íèÿ ðàäèóñà óñòîé÷èâîñòè �-ïðèáëèæåííîãî ðåøåíèÿ äëÿ íåêîòîðîãî êëàññà
äèñêðåòíûõ ýêñòðåìàëüíûõ çàäà÷. Îïðåäåëåíû íåîáõîäèìûå è äîñòàòî÷íûå
óñëîâèÿ, ïðè âûïîëíåíèè êîòîðûõ ðàäèóñ óñòîé÷èâîñòè ðàâåí íóëþ èëè áåñ-
êîíå÷íîñòè. Ïðåäëîæåí àëãîðèòì âû÷èñëåíèÿ ðàäèóñà óñòîé÷èâîñòè è âûäå-
ëåí êëàññ çàäà÷, äëÿ êîòîðûõ ýòîò àëãîðèòì ÿâëÿåòñÿ ïîëèíîìèàëüíûì. Ïðè
ýòîì âñå èçó÷àåìûå âåëè÷èíû êàñàþòñÿ èçìåíåíèé êîýôôèöèåíòîâ öåëåâîé
ôóíêöèè çàäà÷è.  [4] ïðåäñòàâëåíû è èçó÷åíû àëãîðèòìû âû÷èñëåíèÿ ðàäèó-
ñà óñòîé÷èâîñòè �-îïòèìàëüíîãî ðåøåíèÿ äëÿ îïòèìèçàöèîííîé çàäà÷è ñ ðàç-
íûìè öåëåâûìè ôóíêöèÿìè. Ïðè ýòîì èçìåíÿþòñÿ çíà÷åíèÿ êîýôôèöèåíòîâ
öåëåâîé ôóíêöèè çàäà÷è.  [5, 6] ïîëó÷åíû ðåçóëüòàòû îòíîñèòåëüíî óñòîé÷è-
âîñòè ëîêàëüíûõ ðåøåíèé çàäà÷ öåëî÷èñëåííîãî ïðîãðàììèðîâàíèÿ. Âàæíîå
çíà÷åíèå óäåëÿåòñÿ îöåíêàì ñëîæíîñòè àíàëèçà óñòîé÷èâîñòè äèñêðåòíûõ çàäà÷
îïòèìèçàöèè. Äëÿ NP-òðóäíûõ çàäà÷ ýòî ñâîäèòñÿ ê àíàëèçó ñóùåñòâîâàíèÿ ïî-
ëèíîìèàëüíûõ àëãîðèòìîâ íàõîæäåíèÿ îïòèìàëüíèõ ðåøåíèé èçìåíåííûõ çà-
äà÷, èñõîäÿ èç îïòèìàëüíûõ ðåøåíèé èñõîäíîé çàäà÷è.  [7] ïðèâîäÿòñÿ ðå-
çóëüòàòû îòíîñèòåëüíî ñëîæíîñòè àíàëèçà óñòîé÷èâîñòè 0/1 çàäà÷ ñ ëèíåéíîé
öåëåâîé ôóíêöèåé ïðè èçìåíåíèè çíà÷åíèé öåëåâîãî âåêòîðà. Ïîêàçàíî, ÷òî
îñòàåòñÿ íåèçìåííî NP-òðóäíûì (íå ñóùåñòâóåò ïîëèíîìèàëüíîãî àëãîðèòìà
ïðè P NP� ) îïðåäåëåíèå îïòèìàëüíîãî ðåøåíèÿ äëÿ NP-òðóäíûõ çàäà÷ ïðè
ïðîèçâîëüíîì èçìåíåíèè âåêòîðà çíà÷åíèé öåëåâîé ôóíêöèè. Ïîäîáíûõ ðåçóëü-
òàòîâ ïî èçìåíåíèþ êîýôôèöèåíòîâ âåêòîðà îãðàíè÷åíèé èëè íå ñóùåñòâóåò,
èëè îíè ìàëî÷èñëåííû.  ýòîì íàïðàâëåíèè ñëåäóåò îòìåòèòü ðàáîòû [8–11].
 äàííîé ñòàòüå èçó÷àþòñÿ âîïðîñû èññëåäîâàíèÿ øàðîâ óñòîé÷èâîñòè çà-
äàííîãî ðàäèóñà äëÿ îïòèìàëüíûõ è �-ïðèáëèæåííûõ ðåøåíèé (â ÷àñòíîñòè, ñó-
ùåñòâîâàíèÿ ïîëèíîìèàëüíûõ àëãîðèòìîâ ïîñòðîåíèÿ øàðîâ óñòîé÷èâîñòè çà-
äàííîãî ðàäèóñà äëÿ íåêîòîðûõ êëàññîâ NP-ïîëíûõ çàäà÷) ïðè èçìåíåíèè
ìàòðèöû îãðàíè÷åíèé è ïðàâûõ ÷àñòåé çàäà÷è.
56 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 5
© Â.À. Ìèõàéëþê, Í.Â. Ëèùóê, 2015
ÎÑÍÎÂÍÛÅ ÏÎÍßÒÈß È ÎÏÐÅÄÅËÅÍÈß
Ðàññìîòðèì çàäà÷ó áóëåâà ïðîãðàììèðîâàíèÿ
min{ ( ) ( , ..., )}f x f x xn� 1 ,
x G B n n� � � { , }0 1 . (1)
Ïðåäïîëîæèì, ÷òî äîïóñòèìàÿ îáëàñòü G çàäà÷è (1) îïðåäåëÿåòñÿ ïàðà-
ìåòðîì E (íàïðèìåð, ìàòðèöà îãðàíè÷åíèé ñ ïðàâûìè ÷àñòÿìè). Ïóñòü
E E i II i� �{ , } — íåêîòîðîå ìíîæåñòâî ïàðàìåòðîâ (I ìîæåò áûòü êàê êîíå÷-
íûì, òàê è áåñêîíå÷íûì ìíîæåñòâîì) è �( , )E Ei j , i j I, � , — ìåòðèêà, îïðå-
äåëåííàÿ íà EI (ñ÷èòàåì, ÷òî êàæäîìó ïàðàìåòðó E i Ii , � , ñîîòâåòñòâóåò
îáëàñòü Gi çàäà÷è (1)). Ïóñòü i I* � è E
i*
— íåêîòîðûé ôèêñèðîâàííûé ïàðàìåòð.
Îïðåäåëåíèå 1. Øàðîì ïàðàìåòðîâ ðàäèóñà r ñ öåíòðîì â E
i*
íàçûâàåòñÿ
ìíîæåñòâî { : }E j Ij � òàêèõ ïàðàìåòðîâ, ÷òî �( , )*E E r
i j � (îáîçíà÷åíèå O Er i
( )* ).
Ïóñòü x o — îïòèìàëüíîå ðåøåíèå çàäà÷è (1) è � � 0 — öåëîå.
Îïðåäåëåíèå 2. Áóäåì íàçûâàòü x G� �-ïðèáëèæåííûì ðåøåíèåì çàäà-
÷è (1), åñëè âûïîëíÿåòñÿ ñîîòíîøåíèå
f x f x o( ) ( ) ( )� �1 � . (2)
Çàìå÷àíèå 1. Ïðè � � 0 �-ïðèáëèæåííîå ðåøåíèå x ïðåîáðàçóåòñÿ â îïòè-
ìàëüíîå (òî÷íîå) ðåøåíèå.
Çàìå÷àíèå 2. Åñëè (1) — çàäà÷à ìàêñèìèçàöèè, òî (2) ïðèîáðåòàåò âèä
f x
f x
o( )
( )
1�
�
�
. ( )2
Îïðåäåëåíèå 3. Ìíîæåñòâî âñåõ ïàðàìåòðîâ E I II �( ), äëÿ êîòîðûõ ñî-
õðàíÿåòñÿ ñâîéñòâî âåêòîðà x áûòü �-ïðèáëèæåííûì ðåøåíèåì çàäà÷è, íàçî-
âåì îáëàñòüþ óñòîé÷èâîñòè �-ïðèáëèæåííîãî ðåøåíèÿ x è îáîçíà÷èì S x( , )� .
Ïóñòü x — �-ïðèáëèæåííîå ðåøåíèå çàäà÷è (1) ñ ïàðàìåòðîì E
i*
(îáëàñòü G
i*
).
Îïðåäåëåíèå 4. Åñëè
O E S xr i
( ) ( , )*
� , (3)
òî O Er i
( )* áóäåì íàçûâàòü øàðîì óñòîé÷èâîñòè ðàäèóñà r �-ïðèáëèæåííîãî
ðåøåíèÿ çàäà÷è (1).
Îïðåäåëåíèå 5. Íàèáîëüøåå çíà÷åíèå r, äëÿ êîòîðîãî âûïîëíÿåòñÿ (3), íàçî-
âåì ðàäèóñîì óñòîé÷èâîñòè �-ïðèáëèæåííîãî ðåøåíèÿ x è îáîçíà÷èì � � ( , )*x E
i
.
Âîçíèêàåò âîïðîñ èññëåäîâàíèÿ øàðà óñòîé÷èâîñòè ðàäèóñà r �-ïðèáëèæåí-
íîãî ðåøåíèÿ çàäà÷è (1) ïðè êîíêðåòíûõ çíà÷åíèÿõ � è r .
ÑËÎÆÍÎÑÒÜ ÂÛ×ÈÑËÅÍÈß ØÀÐÀ ÓÑÒÎÉ×ÈÂÎÑÒÈ ÐÀÄÈÓÑÀ 1 ÎÏÒÈÌÀËÜÍÎÃÎ
ÐÅØÅÍÈß ÇÀÄÀ×È Î ÏÎÊÐÛÒÈÈ ÌÍÎÆÅÑÒÂÀÌÈ È ÇÀÄÀ×È Î ÐÀÍÖÅ
Ðàññìîòðèì çàäà÷ó î ïîêðûòèè ìíîæåñòâàìè
min c xi
i
n
i
�
�
�
�
�
�
�1
,
a xij
j
n
j
�
� �
1
1 , i m�1, ..., , (4)
x i ni � �{ , }, , ...,0 1 1 .
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 5 57
Ïðè ýòîì m n� -ìàòðèöà A aij� { } — áóëåâà, âåêòîð c c cn� ( , ..., )1 — öåëî÷èñëåí-
íûé.  äàííîì ñëó÷àå ïàðàìåòð E ïðåäñòàâëÿåò ìàòðèöó A .  çàäà÷å (4) ïîäâåðãàòü
èçìåíåíèÿì áóäåì òîëüêî ìàòðèöó A . Äëÿ ïðîèçâîëüíûõ áóëåâûõ m n� -ìàòðèö
A aij� { }, B bij� { } ââåäåì ìåòðèêó �( , ) | |
,
A B a bij ij
i j
� �� . Çàäà÷ó (4) ñ ìàòðèöåé A
áóäåì îáîçíà÷àòü SetCov A( ) è ñ÷èòàòü åå çàäà÷åé (4) ñ ýêçåìïëÿðîì I A� .
Îïðåäåëåíèå 6. Çàäà÷ó SetCov A( ) ñ ïðîèçâîëüíîé ìàòðèöåé A òàêîé, ÷òî
�( , )A A �1 , íàçîâåì áëèçêîé ê çàäà÷å SetCov A( ) .
Ïóñòü Re ( ( ))opt SetCov A — çàäà÷à íàõîæäåíèÿ îïòèìàëüíîãî ðåøåíèÿ çàäà-
÷è SetCov A( ) , áëèçêîé ê SetCov A( ), èñõîäÿ èç îïòèìàëüíîãî ðåøåíèÿ x * çàäà÷è
SetCov A( ) .
Äàëåå áóäåì èñïîëüçîâàòü ñëåäóþùèå ðåçóëüòàòû.
Ëåììà 1 [12]. Ïóñòü Q — NP-òðóäíàÿ çàäà÷à è mod �Q — íåêîòîðàÿ ëîêàëüíàÿ
ìîäèôèêàöèÿ äëÿ Q . Çàäà÷à mod �Q ÿâëÿåòñÿ NP-òðóäíîé, åñëè ñóùåñòâóåò ïîëè-
íîìèàëüíûé àëãîðèòì A, êîòîðûé äëÿ ëþáîãî ýêçåìïëÿðà I çàäà÷è Q âû÷èñëÿåò:
1) ýêçåìïëÿð I äëÿ Q ;
2) îïòèìàëüíîå ðåøåíèå x äëÿ I ;
3) ïîñëåäîâàòåëüíîñòü ëîêàëüíûõ ìîäèôèêàöèé òèïà mod �Q (íå áîëåå ÷åì
ïîëèíîìèàëüíóþ), êîòîðàÿ ïðåîáðàçóåò I â I .
Ëåììà 2 [10]. Ñóùåñòâóåò ïîëèíîìèàëüíûé àëãîðèòì, êîòîðûé èìååò íå áî-
ëåå
c
c
nmax
min
� øàãîâ äëÿ îïðåäåëåíèÿ äîïóñòèìîãî ðåøåíèÿ çàäà÷è SetCov A( )
( max{ }maxc c
i
i� ; c c
i
imin min{ }� ).
Ïóñòü M m� { , ..., }1 , N n� { , ..., }1 , K i ik1 1� { , ..., } — íåêîòîðàÿ âûáîðêà ñ N
îáúåìîì k k n k m( ; )1 � � � . Òî÷êà � � �� �( , ..., )1 n
nB òàêàÿ, ÷òî � j �1 ïðè
j K� 1 , � j � 0 ïðè j N K� \ 1 , à � � �i i
n
i nB� �( , ..., )
1
òàêàÿ, ÷òî � �i
i
j
i� �1 0,
ïðè j i� . Îïèøåì êëàññ { }A� áóëåâûõ m n� -ìàòðèö A aij� { } ; A A�{ }� òîãäà è
òîëüêî òîãäà, êîãäà ìàòðèöà A íå èìååò îäèíàêîâûõ è íóëåâûõ ñòðîê è, êðîìå
òîãî, âûïîëíÿþòñÿ ñëåäóþùèå óñëîâèÿ:
1) ìàòðèöà A èìååò ïîäìàòðèöó A1 �
�
�
i
ik
1
...
�
�
�
�
�
�
�
�
�
�
�
�
;
2) ìàòðèöà A èìååò ïîäìàòðèöó A aij
2 � { } ( \ , )i M K j N� �1 òàêóþ, ÷òî äëÿ
ïðîèçâîëüíîãî i M K aij
j K
� �
�
�\ ,1 1
1
îñòàëüíûå ýëåìåíòû A 2 — ïðîèçâîëüíû.
Ïóñòü âåêòîð x x x Bn
n* * *( , ..., )� �1 òàêîé, ÷òî x xi ik1
1* *� � �� ; îñòàëüíûå
êîîðäèíàòû âåêòîðà x * ðàâíû íóëþ, A A* { }� � .
Ëåììà 3 [10]. Âåêòîð x * ïðåäñòàâëÿåò îïòèìàëüíîå ðåøåíèå çàäà÷è
SetCov A( )* .
Òåîðåìà 1. Çàäà÷à Re ( ( ))opt SetCov A ÿâëÿåòñÿ NP-òðóäíîé.
Äîêàçàòåëüñòâî. Áóäåì èñïîëüçîâàòü ëåììó 1. Èçâåñòíî, ÷òî çàäà÷à î ïî-
êðûòèè ÿâëÿåòñÿ NP-ïîëíîé.  êà÷åñòâå ýêçåìïëÿðà I áåðåì ýêçåìïëÿð çàäà÷è
SetCov A( )* èç ëåììû 3. Èñïîëüçóÿ äëÿ ýòîãî ýêçåìïëÿðà ïîëèíîìèàëüíûé àëãî-
ðèòì èç ëåììû 2, ïîëó÷àåì îïòèìàëüíîå ðåøåíèå (âûïîëíåíû ïï. 1, 2 ëåììû 1).
58 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 5
Ïðåäïîëîæèì, ÷òî T A( ) äëÿ ëþáîé ìàòðèöû A ÿâëÿåòñÿ ïðåîáðàçîâàíèåì A
ñ çàìåíîé ðîâíî îäíîé êîìïîíåíòû 0 íà 1 ëèáî 1 íà 0 (â äàííîì ñëó÷àå ýòèì ïðå-
îáðàçîâàíèåì ÿâëÿåòñÿ ìîäèôèêàöèÿ mod �Q). Áóäåì çàïèñûâàòü A T A � ( ) , åñëè
ïîñëå ïðèìåíåíèÿ ê A ïðåîáðàçîâàíèÿ T ïîëó÷àåì ìàòðèöó A (î÷åâèäíî, ÷òî
�( , )A A �1).
Ïðîèçâîëüíóþ ìàòðèöó A ìîæíî ïîëó÷èòü èç ìàòðèöû A *, èñïîëüçóÿ íå áî-
ëåå m n� ïðåîáðàçîâàíèé T : A A A A
T T T k* � �� � �� � �� �1
� , ãäå A T A1 � ( )* ,
�( , )*A A1 1� ; A T A A Ai i i i� �� �1 1 1( ), ( , )� , i k� �1 1, ..., ; k m n� � è ï. 3 ëåì-
ìû 1 âûïîëíåí. Ïðèìåíèâ ëåììó 1, ïîëó÷èì äîêàçàòåëüñòâî òåîðåìû.
Òåîðåìà 2. Åñëè P NP� , òî äëÿ çàäà÷è î ïîêðûòèè ìíîæåñòâàìè (4) (â íàè-
õóäøåì ñëó÷àå) íå ñóùåñòâóåò ïîëèíîìèàëüíîãî àëãîðèòìà âû÷èñëåíèÿ øàðà
óñòîé÷èâîñòè ðàäèóñà 1 îïòèìàëüíîãî ðåøåíèÿ.
Äîêàçàòåëüñòâî. Èñïîëüçóåì òåîðåìó 1. Ïîñêîëüêó çàäà÷à Re ( ( ))opt SetCov A �
NP-òðóäíàÿ, òî ñîãëàñíî îïðåäåëåíèþ 6 (â íàèõóäøåì ñëó÷àå) ñóùåñòâóåò ýêçåìïëÿð
ìàòðèöû A òàêîé, ÷òî ïðè P NP� äëÿ çàäà÷è SetCov A( ) , ãäå �( , )A A �1, íå ñó-
ùåñòâóåò ïîëèíîìèàëüíîãî àëãîðèòìà íàõîæäåíèÿ îïòèìàëüíîãî ðåøåíèÿ, èñõîäÿ èç
îïòèìàëüíîãî ðåøåíèÿ çàäà÷è SetCov A( ) . Ñîãëàñíî îïðåäåëåíèÿì 1, 2 (ïðè � � 0), 3 è
4 ýòî îçíà÷àåò, ÷òî äëÿ çàäà÷è (4) (â íàèõóäøåì ñëó÷àå) íå ñóùåñòâóåò ïîëèíîìèàëü-
íîãî àëãîðèòìà âû÷èñëåíèÿ øàðà óñòîé÷èâîñòè ðàäèóñà 1 îïòèìàëüíîãî ðåøåíèÿ.
Ðàññìîòðèì îäíîìåðíóþ çàäà÷ó î ðàíöå ñ áóëåâûìè ïåðåìåííûìè:
max c xi
i I
i
�
�
�
�
�
�
�
,
a x bi
i I
i
�
� � , x i Ii � �{ , },0 1 . (5)
Áóäåì ñ÷èòàòü, ÷òî âñå ÷èñëà a ci i, è b ÿâëÿþòñÿ íàòóðàëüíûìè, I — íåêîòî-
ðîå ìíîæåñòâî èíäåêñîâ. Çàäà÷ó (5) ñî ñòàíäàðòíûì ìíîæåñòâîì èíäåêñîâ
I n� { , ..., }1 áóäåì îáîçíà÷àòü KP a b c( , , ) , ãäå âåêòîðû a a c ci i I i i I� �� �( ) , ( ) .
Ïóñòü Z x x xn
n� �{ ( , ..., )}1 : x xi i� 0, — öåëûå, i n� { , ..., }1 , äëÿ x �
� ��
�( , ..., , )x x x Zn n
n
1 1
1 , y y y y Zn n
n� ��
�( , ..., , )1 1
1 ââåäåì ìåòðèêó �( , )x y �
� �
�
�
� | |x yi i
i
n
1
1
. Äëÿ a a a b Zn
n� � �( , ... , )1
1 âåêòîð a òàêîé, ÷òî �( , )a a �1 (çà-
äà÷ó KP a b c( , , ) áóäåì îáîçíà÷àòü òàê: KP a c( , )). Ðàññìîòðèì ïðîèçâîëüíóþ
çàäà÷ó KP a c( , ) .
Îïðåäåëåíèå 7. Çàäà÷ó KP a c( , ) ñ ïðîèçâîëüíûì âåêòîðîì a òàêèì, ÷òî
�( , )a a �1, áóäåì íàçûâàòü îáîáùåííî-áëèçêîé ê KP a c( , ) .
Èòàê, îáîáùåííî-áëèçêèå çàäà÷è ìîãóò îòëè÷àòüñÿ îäíà îò äðóãîé íà åäè-
íèöó íå òîëüêî ïî ïðàâûì ÷àñòÿì (êàê «áëèçêèå» â [8]), íî è ïî êîìïîíåíòàì
âåêòîðà a a an� ( , ..., )1 .
Îáîçíà÷èì Re ( ( , ))opt KP a c çàäà÷ó íàõîæäåíèÿ îïòèìàëüíîãî ðåøåíèÿ çà-
äà÷è KP a c( , ) , îáîáùåííî áëèçêîé ê KP a c( , ) , èñõîäÿ èç îïòèìàëüíîãî ðåøå-
íèÿ x * çàäà÷è KP a c( , ) .
Òåîðåìà 3 [11]. Çàäà÷à Re ( ( , ))opt KP a c ÿâëÿåòñÿ NP-òðóäíîé.
Òåîðåìà 4. Åñëè P NP� , òî äëÿ çàäà÷è î ðàíöå (5) (â íàèõóäøåì ñëó÷àå) íå
ñóùåñòâóåò ïîëèíîìèàëüíîãî àëãîðèòìà âû÷èñëåíèÿ øàðà óñòîé÷èâîñòè ðàäèó-
ñà 1 îïòèìàëüíîãî ðåøåíèÿ.
Äîêàçàòåëüñòâî ïîëíîñòüþ àíàëîãè÷íî äîêàçàòåëüñòâó òåîðåìû 2 (òîëüêî
ñ èñïîëüçîâàíèåì òåîðåìû 3).
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 5 59
ÑËÎÆÍÎÑÒÜ ÂÛ×ÈÑËÅÍÈß ØÀÐΠÓÑÒÎÉ×ÈÂÎÑÒÈ �-ÏÐÈÁËÈÆÅÍÍÛÕ ÐÅØÅÍÈÉ
ÇÀÄÀ×È Î ÏÎÊÐÛÒÈÈ ÌÍÎÆÅÑÒÂÀÌÈ È ÇÀÄÀ×È Î ÐÀÍÖÅ
Èçâåñòíî, ÷òî æàäíûé àëãîðèòì [13, 14] íàõîäèò ln m-ïðèáëèæåííîå ðåøåíèå
(� � ln m â îïðåäåëåíèè 2) çàäà÷è î ïîêðûòèè (4). Ñóòü ýòîãî ïîëèíîìèàëüíîãî
àëãîðèòìà (è ïîäîáíûõ åìó) ñîñòîèò â èñïîëüçîâàíèè ïðîñòåéøåé æàäíîé ýâ-
ðèñòèêè: íà êàæäîì øàãå âûáèðàòü ìàêñèìàëüíî íåïîêðûòîå ïîäìíîæåñòâî,
ò.å. ïîäìíîæåñòâî, ñîäåðæàùåå ìàêñèìàëüíîå ÷èñëî ýëåìåíòîâ, íå ïîêðûòûõ
íà ïðåäûäóùèõ øàãàõ. Áóäåì èñïîëüçîâàòü ýòîò àëãîðèòì ïðè âû÷èñëåíèè
øàðà óñòîé÷èâîñòè íåêîòîðîãî ðàäèóñà äëÿ ln m-ïðèáëèæåííîãî ðåøåíèÿ çàäà-
÷è î ïîêðûòèè (4).
Ñîãëàñíî îïðåäåëåíèþ 1 øàðîì ïàðàìåòðîâ ðàäèóñà r ñ öåíòðîì â E A
i*
*� (íå-
êîòîðàÿ ôèêñèðîâàííàÿ áóëåâà m n� -ìàòðèöà) åñòü ìíîæåñòâî m n� -ìàòðèö
{ : }A j Ij � òàêèõ, ÷òî �( , )*A A rj � (O Ar ( )* — øàð ðàäèóñà ñ öåíòðîì A * ; � —
ìåòðèêà, ââåäåííàÿ äëÿ çàäà÷ î ïîêðûòèè). Íåîáõîäèìî îïðåäåëèòü ÷èñëî ýëå-
ìåíòîâ âî ìíîæåñòâå O Ar ( )* , ïðè ýòîì �( , , ) | ( )|*m n r O Ar� . Ïóñòü
C
n
k n k
n
k �
� �
!
! ( )!
— ÷èñëî k-ýëåìåíòíûõ ïîäìíîæåñòâ ìíîæåñòâà èç n ýëåìåíòîâ
(÷èñëî ñî÷åòàíèé èç n ïî k , k n� — íàòóðàëüíûå). Áóäåì ñ÷èòàòü, ÷òî ôóíêöèÿ
f n( ) èìååò ïîëèíîìèàëüíûé ðîñò ( ( ) ( ))f n poly n� , åñëè äëÿ íåêîòîðîé êîíñòàí-
òû c c O( ( ))� 1 ïðè äîñòàòî÷íî áîëüøèõ n âûïîëíÿåòñÿ óñëîâèå f n nc( ) � .
Ëåììà 4. Èìååì �( , , )m n r Cm n
k
k
r
� � �
�
�1
1
.
Äîêàçàòåëüñòâî. ×èñëî m n� -ìàòðèö, íàõîäÿùèõñÿ íà çàäàííîì ðàññòîÿíèè
1 � �k r îò ôèêñèðîâàííîé m n� -ìàòðèöû A * , ðàâíî Cm n
k
� . Îñòàëîñü ïðîñóììèðî-
âàòü ýòè âåëè÷èíû ïî k îò åäèíèöû äî r ñ ó÷åòîì ìàòðèöû A * .
Çàìåòèì, ÷òî åñëè k k O� �const( ( ))1 , òî C poly m nm n
k
� � �( ) è, ñëåäîâàòåëüíî,
�( , , ) ( )m n r poly m n� � ïðè r O� ( )1 (â ñèëó ëåììû 4).
Ñëåäñòâèå. Ïðè r O� ( )1 èìååì �( , , ) ( )m n r poly m n� � .
Òåîðåìà 5. Ïðè r O� ( )1 äëÿ çàäà÷è î ïîêðûòèè ìíîæåñòâàìè (4) ñóùåñòâóåò
ïîëèíîìèàëüíûé àëãîðèòì âû÷èñëåíèÿ øàðà óñòîé÷èâîñòè ðàäèóñà r ln m-ïðè-
áëèæåííîãî ðåøåíèÿ.
Äîêàçàòåëüñòâî. Äëÿ ðåøåíèÿ çàäà÷è SetCov A( ) ñ ïðîèçâîëüíîé (ôèêñèðî-
âàííîé) ìàòðèöåé A èñïîëüçóåì (ïîëèíîìèàëüíûé) æàäíûé àëãîðèòì. Ïîëó÷èì
íåêîòîðîå ln m-ïðèáëèæåííîå ðåøåíèå. Äàëåå äëÿ íàõîæäåíèÿ ðåøåíèé çàäà÷ èç
øàðà óñòîé÷èâîñòè ðàäèóñà r çàäà÷è A (êîòîðûõ â ñèëó ëåììû 4 íå áîëåå
�( , , )m n r ) òàêæå èñïîëüçóåì ïîëèíîìèàëüíûé æàäíûé àëãîðèòì. Ïîñêîëüêó
�( , , ) ( )m n r poly m n� � ïðè r O� ( )1 (ñëåäñòâèå èç ëåììû 4), òî çàòðà÷åííîå îáùåå
âðåìÿ äëÿ ðåøåíèÿ âñåõ çàäà÷ íå áîëåå ÷åì ïîëèíîì îò m n� , òåì ñàìûì òåîðåìà
äîêàçàíà.
Èçâåñòíî, ÷òî ïîëèíîìèàëüíûé æàäíûé àëãîðèòì íàõîäèò 1-ïðèáëèæåííîå
ðåøåíèå (� �1 èç ( )2 ) çàäà÷è î ðàíöå (5) [14]. Áóäåì èñïîëüçîâàòü ýòîò àëãîðèòì
â âû÷èñëåíèè øàðà óñòîé÷èâîñòè íåêîòîðîãî ðàäèóñà äëÿ 1-ïðèáëèæåííîãî
ðåøåíèÿ çàäà÷è î ðàíöå (5).
Ñîãëàñíî îïðåäåëåíèþ 1 øàðîì ïàðàìåòðîâ ðàäèóñà r ñ öåíòðîì â E a
i*
*� (íå-
êîòîðûé ôèêñèðîâàííûé ( )n �1 -âåêòîð èç íàòóðàëüíûõ ÷èñåë) åñòü ìíîæåñòâî
( )n �1 -âåêòîðîâ { : }a j Ij � òàêèõ, ÷òî �( , )*a a rj � ; � — ìåòðèêà, ââåäåííàÿ äëÿ
60 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 5
ðåøåíèÿ çàäà÷ î ðàíöå. Íåîáõîäèìî îïðåäåëèòü ÷èñëî ýëåìåíòîâ âî ìíîæåñòâå
O ar ( )* ; �( , ) | ( )|*n r O ar� . Äëÿ ïðîñòîòû ïîäñ÷åòà �( , )n r ââåäåì îãðàíè÷åííóþ
âåðñèþ çàäà÷è î ðàíöå (5): áóäåì ñ÷èòàòü âåêòîð a a an� ( , ..., )1 áóëåâûì (ò.å. ñî-
ñòîÿùèì èç íóëåé è åäèíèö), b poly n b r� �( ), . Îáîçíà÷èì � ( , )n k , 1 � �k r, ÷èñëî
ýëåìåíòîâ O ar ( )* â øàðå, êîòîðûå íàõîäÿòñÿ íà ðàññòîÿíèè ðîâíî k îò öåíòðà a * .
Î÷åâèäíî, ÷òî � �( , ) ( , )n r n k
k
r
� �
�
�1
1
.
Ëåììà 5. Äëÿ îãðàíè÷åííîé âåðñèè çàäà÷è î ðàíöå (5)
� ( , ) ( )n k C Cn
k
n
j
j
k
� � � �
�
�
�2 1
1
1
.
Äîêàçàòåëüñòâî. Ðàçîáüåì âåêòîð a a a bn
* * * *( , , )� 1 � óñëîâíî íà äâå êîì-
ïîíåíòû: ( , )* *a an1 � è b* . Ïîäñ÷åò êîëè÷åñòâà ýëåìåíòîâ íà ðàññòîÿíèè k îò a *
ïðîâåäåì ïî ýòèì êîìïîíåíòàì. Ñíà÷àëà ðàññìàòðèâàåì ïåðâóþ êîìïîíåíòó. Íà
ðàññòîÿíèè k ïî ïåðâîé êîìïîíåíòå íàõîäèòñÿ Cn
k ýëåìåíòîâ; âòîðàÿ êîìïîíåíòà
íå èçìåíÿåòñÿ. Ïîâòîðíî ðàññìàòðèâàåì ïåðâóþ êîìïîíåíòó; íà ðàññòîÿíèè k �1 ïî
ïåðâîé êîìïîíåíòå íàõîäèòñÿ Cn
k�1 ýëåìåíòîâ; âòîðàÿ êîìïîíåíòà èçìåíÿåòñÿ:
ê b*äîáàâëÿåòñÿ èëè èç íåå âû÷èòàåòñÿ åäèíèöà; â èòîãî èìååì åùå 2 1� �Cn
k ýëåìåí-
òîâ íà ðàññòîÿíèè k . Ñíîâà ðàññìàòðèâàåì ïåðâóþ êîìïîíåíòó; íà ðàññòîÿíèè k �2
ïî ïåðâîé êîìïîíåíòå íàõîäèòñÿ Cn
k�2 ýëåìåíòîâ; âòîðàÿ êîìïîíåíòà òàêæå èçìå-
íÿåòñÿ: ê b* äîáàâëÿåòñÿ èëè èç íåå âû÷èòàåòñÿ 2; â ðåçóëüòàòå èìååì åùå 2 2� �Cn
k
ýëåìåíòîâ íà ðàññòîÿíèè k è ò.ä. Ïðîäîëæàåì ðàññìàòðèâàòü ïåðâóþ êîìïîíåíòó;
íà ðàññòîÿíèè 1 ïî ïåðâîé êîìïîíåíòå íàõîäèòñÿ Cn
1 ýëåìåíòîâ; âòîðàÿ êîìïîíåíòà
òàêæå èçìåíÿåòñÿ: ê b* äîáàâëÿåòñÿ èëè âû÷èòàåòñÿ k �1; â èòîãå èìååì åùå 2 1�Cn
ýëåìåíòîâ íà ðàññòîÿíèè k . Íàêîíåö, ïðè èçìåíåíèè òîëüêî âòîðîé êîìïîíåíòû
(äîáàâëÿåòñÿ èëè âû÷èòàåòñÿ k) ïîëó÷èì åùå äâà ýëåìåíòà íà ðàññòîÿíèè k.
Òàêèì îáðàçîì, ïîëó÷èëè C C C Cn
k
n
k
n
k
n� � � � � � � �� �2 2 2 21 2 1... ýëåìåíòîâ íà
ðàññòîÿíèè k, ÷òî è òðåáîâàëîñü äîêàçàòü.
Çàìåòèì, ÷òî åñëè k k O� �const ( ( ))1 , òî C poly nn
k � ( ) è, ñëåäîâàòåëüíî,
� ( , ) ( )n k poly n� ïðè k O� ( )1 (â ñèëó ëåììû 5). À ïîñêîëüêó � �( , ) ( , )n r n k
k
r
� �
�
�1
1
,
òî �( , ) ( )n r poly n� ïðè r O� ( )1 .
Ñëåäñòâèå. Ïðè r O� ( )1 èìååì �( , ) ( )n r poly n� .
Òåîðåìà 6. Ïðè r O� ( )1 äëÿ îãðàíè÷åííîé âåðñèè çàäà÷è î ðàíöå (5) ñóùå-
ñòâóåò ïîëèíîìèàëüíûé àëãîðèòì âû÷èñëåíèÿ øàðà óñòîé÷èâîñòè ðàäèóñà r
1-ïðèáëèæåííîãî ðåøåíèÿ.
Äîêàçàòåëüñòâî. Äëÿ ðåøåíèÿ çàäà÷è KP a c( , ) ñ ïðîèçâîëüíûìè (ôèêñèðî-
âàííûìè) âåêòîðàìè a è c èñïîëüçóåì (ïîëèíîìèàëüíûé) æàäíûé àëãîðèòì. Ïî-
ëó÷èì íåêîòîðîå 1-ïðèáëèæåííîå ðåøåíèå. Òåïåðü äëÿ ïîëó÷åíèÿ ðåøåíèé çà-
äà÷, èñõîäÿ èç øàðà óñòîé÷èâîñòè ðàäèóñà r çàäà÷è ñ âåêòîðîì a (êîòîðûõ íå áî-
ëåå �( , )n r ) òàêæå èñïîëüçóåì ïîëèíîìèàëüíûé æàäíûé àëãîðèòì. Ïîñêîëüêó
�( , ) ( )n r poly n� ïðè r O� ( )1 (ñëåäñòâèå èç ëåììû 5), òî çàòðà÷åííîå îáùåå âðåìÿ
íà ðåøåíèå âñåõ çàäà÷ íå áîëåå ÷åì ïîëèíîì îò n , òåì ñàìûì òåîðåìà äîêàçàíà.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 5 61
Ñëåäñòâèå. Ñóùåñòâîâàíèå ïîëèíîìèàëüíîãî àëãîðèòìà âû÷èñëåíèÿ øàðà
óñòîé÷èâîñòè ðàäèóñà r 1-ïðèáëèæåííîãî ðåøåíèÿ çàäà÷è î ðàíöå (5) âîçìîæíî
ëèøü ïðè r O� ( )1 .
ÇÀÊËÞ×ÅÍÈÅ
Ðåçóëüòàòû, èçëîæåííûå â íàñòîÿùåé ñòàòüå, ïîêàçûâàþò, ÷òî äëÿ NP-ïîëíûõ çà-
äà÷ òðóäîåìêèì ÿâëÿåòñÿ äàæå âû÷èñëåíèå øàðà óñòîé÷èâîñòè ðàäèóñà 1 îïòè-
ìàëüíîãî ðåøåíèÿ (ò.å. ïðè P NP� äëÿ ýòîãî âû÷èñëåíèÿ íå ñóùåñòâóåò ïîëèíî-
ìèàëüíîãî àëãîðèòìà). Ýòîò ðåçóëüòàò (îòíîñèòåëüíî ââåäåííûõ ïîíÿòèé) ñîãëà-
ñóåòñÿ ñ ðåçóëüòàòàìè èç ðàáîò [2– 4, 7]. Äëÿ �-ïðèáëèæåííûõ ðåøåíèé ðåçóëüòàò
íåñêîëüêî èíîé. Ïîêàçàíî, ÷òî ïðè èñïîëüçîâàíèè æàäíûõ àëãîðèòìîâ äëÿ çàäà-
÷è î ïîêðûòèè ìíîæåñòâàìè (çàäà÷è î ðàíöå) ïðè ðàäèóñå óñòîé÷èâîñòè r, ðàâ-
íîì O( )1 , ñóùåñòâóþò ïîëèíîìèàëüíûå àëãîðèòìû âû÷èñëåíèÿ øàðà óñòîé÷èâîñòè
ðàäèóñà r ln m-ïðèáëèæåííîãî ðåøåíèÿ (1-ïðèáëèæåííîãî ðåøåíèÿ).
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. F e r n a n d e z - B a c a D . , V e n k a t a c h a l a m B . Sensitivity analysis in combinatorial optimization /
Handbook of Approximation Algorithms and Metaheuristics (Ed. T. Gonzalez). — Boca Raton:
Chapman&Hall/CRC Computer and Information Science Series, 2007. — P. 30.-1–30.-29.
2. Ë å î í ò ü å â  . Ê . , Ì à ì ó ò î â Ê . Õ . Óñòîé÷èâîñòü ðåøåíèé â çàäà÷àõ ëèíåéíîãî áóëåâà
ïðîãðàììèðîâàíèÿ // Æóðíàë âû÷èñëèòåëüíîé ìàòåìàòèêè è ìàòåìàòè÷åñêîé ôèçèêè. —
1988. — 28, ¹ 10. — Ñ. 1475–1481.
3. Ñ î ò ñ ê î â Þ . Í . Èññëåäîâàíèå óñòîé÷èâîñòè ïðèáëèæåíîãî ðåøåíèÿ áóëåâîé çàäà÷è ìèíèìè-
çàöèè ëèíåéíîé ôîðìû // Æóðíàë âû÷èñëèòåëüíîé ìàòåìàòèêè è ìàòåìàòè÷åñêîé ôèçèêè. —
1993. — 33, ¹ 5. — Ñ. 785–795.
4. C h a k r a v a r t i N . , W a g e l m a n s A . P . M . Calculation of stability radii for combinatorial
optimization problems // Operations Research Letters. — 1998. — 23. — P. 1–7.
5. Ñ å ð ã è å í ê î È .  . Ìàòåìàòè÷åñêèå ìîäåëè è ìåòîäû ðåøåíèÿ çàäà÷ äèñêðåòíîé îïòèìèçà-
öèè. — Êèåâ: Íàóê. äóìêà, 1985. — 210 ñ.
6. Ñ å ð ã è å í ê î È .  . , Ô è ë î í å í ê î Í .  . Ðåøåíèå íåêîòîðûõ çàäà÷ óñòîé÷èâîñòè â öåëî÷èñ-
ëåííîì ëèíåéíîì ïðîãðàììèðîâàíèè // Äîêëàäû ÀÍ ÓÑÑÐ. Ñåð. À. — 1982. — ¹ 6. —
Ñ. 79–82.
7. V a n H o e s e l S . , W a g e l m a n s A . On the complexity of postoptimality analysis of 0/1
programs // Discrete Applied Mathematics. — 1999. — 91. — P. 251–263.
8. B l a i r C . Sensitivity analysis for knapsack problems: A negative result // Discrete Applied
Mathematics. — 1998. — 81. — P. 133–139.
9. W o e g i n g e r G . J . Sensitivity analysis for knapsack problems: Another negative result // Discrete
Applied Mathematics. — 1999. — 92. — P. 247–251.
10. Ì è õ à é ë þ ê Â . À . Îáùèé ïîäõîä ê îöåíêå ñëîæíîñòè ïîñòîïòèìàëüíîãî àíàëèçà äèñêðåò-
íûõ çàäà÷ îïòèìèçàöèè // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 2010. — 46, ¹ 2. —
Ñ. 134–141.
11. Ì è õ à é ë þ ê  . A . , Ë è ù ó ê Í .  . Àíàëèç óñòîé÷èâîñòè çàäà÷è î ðàíöå: îäèí îòðèöàòåëü-
íûé ðåçóëüòàò // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 2013. — 49, ¹ 2. — Ñ. 48–51.
12. Ì è õ à é ë þ ê  . A . Ðåîïòèìèçàöèÿ çàäà÷è î ìàêñèìàëüíîì k-ïîêðûòèè: ïîðîã îòíîøåíèÿ àï-
ïðîêñèìàöèè // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 2012. — 48, ¹ 2. — Ñ. 97–104.
13. C h v a t a l V . A . A greedy heuristic for the set covering problem // Mathematics of Operation
Research. — 1979. — 4, N 3. — P. 233–235.
14. Ê ó ç þ ð è í Í . Í . , Ô î ì è í Ñ . À . Ýôôåêòèâíûå àëãîðèòìû è ñëîæíîñòü âû÷èñëåíèé. —
Ì.: ÌÔÒÈ, 2008. — 344 ñ.
Ïîñòóïèëà 20.10.2014
62 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 5
|