О радиусе устойчивости векторной задачи целочисленного линейного программирования в случае регулярности нормы в критериальном пространстве
Розглянуто багатокритеріальний варіант задачі цілочисельного лінійного програмування зі скінченною множиною допустимих рішень, що полягає в пошуку множини Парето. Використовуючи нерівність Мінковського–Малера, а також відомий критерій стійкості задачі, отримано нижню і верхню досяжні оцінки радіуса...
Saved in:
| Published in: | Кибернетика и системный анализ |
|---|---|
| Date: | 2010 |
| Main Authors: | , |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2010
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/45128 |
| 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: | О радиусе устойчивости векторной задачи целочисленного линейного программирования в случае регулярности нормы в критериальном пространстве / В.А. Емеличев, К.Г. Кузьмин // Кибернетика и системный анализ. — 2010. — № 1. — С. 82–89. — Бібліогр.: 19 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859875308268683264 |
|---|---|
| author | Емеличев, В.А. Кузьмин, К.Г. |
| author_facet | Емеличев, В.А. Кузьмин, К.Г. |
| citation_txt | О радиусе устойчивости векторной задачи целочисленного линейного программирования в случае регулярности нормы в критериальном пространстве / В.А. Емеличев, К.Г. Кузьмин // Кибернетика и системный анализ. — 2010. — № 1. — С. 82–89. — Бібліогр.: 19 назв. — рос. |
| collection | DSpace DC |
| container_title | Кибернетика и системный анализ |
| description | Розглянуто багатокритеріальний варіант задачі цілочисельного лінійного програмування зі скінченною множиною допустимих рішень, що полягає в пошуку множини Парето. Використовуючи нерівність Мінковського–Малера, а також відомий критерій стійкості задачі, отримано нижню і верхню досяжні оцінки радіуса стійкості задачі, припускаючи, що норма в просторі розв’язків довільна, а в критеріальному просторі монотонна. Як наслідок, наведено оцінки радіуса стійкості задачі в просторах з метрикою Гельдера.
A multicriteria integer linear programming problem of finding a Pareto set is considered. The set of feasible solutions is supposed to be finite. Using the Minkowski-Mahler inequality and known stability criteria of the problem, lower and upper accessible bounds for the radius of stability are obtained under the assumption that the norm is arbitrary in the space of solutions and monotone in the space of criteria. Bounds for the radius of stability of the problem in spaces with the Helder metric are given as corollaries.
|
| first_indexed | 2025-12-07T15:50:52Z |
| format | Article |
| fulltext |
ÓÄÊ 519.8
Â.À. ÅÌÅËÈ×ÅÂ, Ê.Ã. ÊÓÇÜÌÈÍ
Î ÐÀÄÈÓÑÅ ÓÑÒÎÉ×ÈÂÎÑÒÈ ÂÅÊÒÎÐÍÎÉ ÇÀÄÀ×È
ÖÅËÎ×ÈÑËÅÍÍÎÃÎ ËÈÍÅÉÍÎÃÎ ÏÐÎÃÐÀÌÌÈÐÎÂÀÍÈß
 ÑËÓ×ÀÅ ÐÅÃÓËßÐÍÎÑÒÈ ÍÎÐÌÛ
 ÊÐÈÒÅÐÈÀËÜÍÎÌ ÏÐÎÑÒÐÀÍÑÒÂÅ
Êëþ÷åâûå ñëîâà: âåêòîðíàÿ çàäà÷à öåëî÷èñëåííîãî ëèíåéíîãî ïðîãðàììèðîâà-
íèÿ, ìíîæåñòâî Ïàðåòî, ìíîæåñòâî Ñëåéòåðà, óñòîé÷èâîñòü, ðàäèóñ óñòîé÷è-
âîñòè, âîçìóùàþùàÿ ìàòðèöà, íîðìà âåêòîðà, êðèòåðèàëüíîå ïðîñòðàíñòâî,
ïðîñòðàíñòâî ðåøåíèé.
ÂÂÅÄÅÍÈÅ
Íà÷àëüíûì ðåçóëüòàòîì êà÷åñòâåííîé òåîðèè óñòîé÷èâîñòè âåêòîðíûõ çàäà÷
äèñêðåòíîé îïòèìèçàöèè ÿâëÿåòñÿ òåîðåìà, óñòàíîâëåííàÿ â ðàáîòàõ [1–3]
(ñì. òàêæå [4–8]). Ñîãëàñíî ýòîé òåîðåìå ñîâïàäåíèå ìíîæåñòâ Ïàðåòî è Ñëåé-
òåðà íåîáõîäèìî è äîñòàòî÷íî äëÿ óñòîé÷èâîñòè ïî ôóíêöèîíàëó âåêòîðíîé
çàäà÷è öåëî÷èñëåííîãî ëèíåéíîãî ïðîãðàììèðîâàíèÿ (ÖËÏ) ñ êîíå÷íûì ìíî-
æåñòâîì äîïóñòèìûõ ðåøåíèé, ñîñòîÿùåé â îòûñêàíèè ðåøåíèé, îïòèìàëüíûõ
ïî Ïàðåòî.  [9] áûëè èññëåäîâàíû êîëè÷åñòâåííûå õàðàêòåðèñòèêè óñòîé÷è-
âîñòè òàêîé çàäà÷è.  ÷àñòíîñòè, ïîëó÷åíû íèæíÿÿ è âåðõíÿÿ äîñòèæèìûå
îöåíêè ðàäèóñà óñòîé÷èâîñòè âåêòîðíîé çàäà÷è ÖËÏ â ñëó÷àå, êîãäà â ïðî-
ñòðàíñòâàõ ðåøåíèé è êðèòåðèåâ çàäàíà îäíà è òà æå ÷åáûøåâñêàÿ íîðìà. Ñëå-
äóåò îòìåòèòü, ÷òî ïðåäëîæåííàÿ â [9] âåðõíÿÿ îöåíêà ðàäèóñà óñòîé÷èâîñòè,
ïðåäñòàâëÿþùàÿ ñîáîé íîðìó ìàòðèöû êîýôôèöèåíòîâ âåêòîðíîãî êðèòåðèÿ,
ÿâëÿåòñÿ äîñòàòî÷íî ãðóáîé.  íàñòîÿùåé ñòàòüå áëàãîäàðÿ èñïîëüçîâàíèþ
óïîìÿíóòîãî âûøå íåîáõîäèìîãî è äîñòàòî÷íîãî óñëîâèÿ óñòîé÷èâîñòè çàäà÷è
óñòàíîâëåíà áîëåå òî÷íàÿ âåðõíÿÿ îöåíêà ýòîãî ðàäèóñà. Êðîìå òîãî, îñíîâû-
âàÿñü íà èçâåñòíîì íåðàâåíñòâå Ìèíêîâñêîãî–Ìàëåðà, óäàëîñü îáîáùèòü ïîëó-
÷åííûå ðàíåå îöåíêè íà ñëó÷àé ïðîèçâîëüíîé íîðìû â ïðîñòðàíñòâå ðåøåíèé
è íîðìû â êðèòåðèàëüíîì ïðîñòðàíñòâå, óäîâëåòâîðÿþùåé íåêîòîðûì íåîáðå-
ìåíèòåëüíûì óñëîâèÿì (òàêèìè íîðìàìè ÿâëÿþòñÿ, íàïðèìåð, âñå íîðìû
øëüäåðà lp , 1� � �p ). Îòìåòèì, ÷òî ïîäîáíàÿ òåõíèêà èñïîëüçîâàíèÿ íåðàâåí-
ñòâà Ìèíêîâñêîãî–Ìàëåðà ðàíåå áûëà ïðèìåíåíà â [10] äëÿ ïîëó÷åíèÿ íèæíåé
è âåðõíåé äîñòèæèìûõ îöåíîê ðàäèóñà ñèëüíîé óñòîé÷èâîñòè (T1-óñòîé÷èâîñòè
â òåðìèíîëîãèè [5–8]), à òàêæå â [11] äëÿ íàõîæäåíèÿ ôîðìóëû ðàäèóñà óñòîé-
÷èâîñòè ýôôåêòèâíîãî ðåøåíèÿ âåêòîðíîé çàäà÷è ÖËÏ.
ÎÑÍÎÂÍÛÅ ÎÏÐÅÄÅËÅÍÈß È ÂÑÏÎÌÎÃÀÒÅËÜÍÛÅ ÓÒÂÅÐÆÄÅÍÈß
Ïóñòü Rm — êðèòåðèàëüíîå ïðîñòðàíñòâî, Rn — ïðîñòðàíñòâî ðåøåíèé, C —
ìàòðèöà ðàçìåðà n m� ñî ñòîëáöàìè C c c ci i i in
T n� �( , , , )1 2 � R , i N m� �
�{ }1 2, , ,� m , x x x x Xn
T n� � �( , , , )1 2 � Z , ïðè÷åì 1� � �| |X . Ïóñòü òàêæå íà
êîíå÷íîì ìíîæåñòâå öåëî÷èñëåííûõ âåêòîðîâ (ðåøåíèé) X çàäàí ëèíåéíûé âåê-
òîðíûé êðèòåðèé
C x C x C x C xT
m
T
x X
�
�
(( , ), ( , ), , ( , )) min1 2 � ,
ãäå ( , )
— ñêàëÿðíîå ïðîèçâåäåíèå âåêòîðîâ.
Ïîä âåêòîðíîé (m-êðèòåðèàëüíîé) çàäà÷åé ÖËÏ Z Cm ( ) , C n m� �R , áóäåì ïî-
íèìàòü çàäà÷ó ïîèñêà ìíîæåñòâà Ïàðåòî (ìíîæåñòâà ýôôåêòèâíûõ âåêòîðîâ)
P C x X P x Cm m( ) : ( , )� � ��{ },
82 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 1
© Â.À. Åìåëè÷åâ, Ê.Ã. Êóçüìèí, 2010
ãäå
P x C x X C x C x C x C xm T T T T( , ) : &� � �
� � �{ }.
 ñèëó êîíå÷íîñòè X ìíîæåñòâî P Cm ( ) �� ïðè ëþáîé ìàòðèöå C n m� �R .
Âîçìóùåíèå ýëåìåíòîâ ìàòðèöû C áóäåì îñóùåñòâëÿòü ïóòåì ïðèáàâëåíèÿ ê íåé
ìàòðèö C� èç Rn m� . Òàêèì îáðàçîì, âîçìóùåííàÿ çàäà÷à Z C Cm ( )� � èìååò âèä
( ) minC C xT
x X
� �
�
,
à ìíîæåñòâî Ïàðåòî òàêîé çàäà÷è — âèä P C Cm ( )� � .
 ïðîñòðàíñòâå ðåøåíèé Rn , â êîòîðîì âåêòîðû ñóòü ìàòðèöû ðàçìåðà n � 1,
çàäàäèì ïðîèçâîëüíóþ íîðìó
. Ïóñòü
*
— íîðìà â ñîïðÿæåííîì ïðîñòðàí-
ñòâå ( )*Rn . Òîãäà âûïîëíÿþòñÿ ðàâåíñòâà
v
u v
u
u n*
max
|( , )|
: \ { }� �
�
�
�
��
�
�
�
��
R 0 ,
u
u v
v
v n� �
�
�
�
��
�
�
�
��
max
|( , )|
: \ { }
*
R 0 ,
ãäå 0 — íóëü–âåêòîð ïðîñòðàíñòâà Rn . Ïîýòîìó äëÿ ëþáûõ âåêòîðîâ u v n, �R
ñïðàâåäëèâî íåðàâåíñòâî Ìèíêîâñêîãî–Ìàëåðà [12] (èíîãäà ýòî íåðàâåíñòâî íà-
çûâàþò íåðàâåíñòâîì Øâàðöà [13])
| ( , )|
*
u v u v� . (1)
Îòñþäà âûòåêàåò ôîðìóëà
�
� � � �� 0, v an nR R ( | ( , )| &
*
a v v a� �� � ). (2)
Íîðìó
, çàäàííóþ â êðèòåðèàëüíîì ïðîñòðàíñòâå Rm , áóäåì íàçûâàòü ðåãó-
ëÿðíîé, åñëè îíà ìîíîòîííà ( y y y� �& , � � � � ��y y ymR ) è âñå åäèíè÷íûå
âåêòîðû ïðîñòðàíñòâà Rm íîðìèðîâàíû ( ei �1, i N m� ).
Äëÿ ïðîèçâîëüíîãî ÷èñëà � � 0 îïðåäåëèì ìíîæåñòâî âîçìóùàþùèõ ìàòðèö
� ( ) { : }� �� � � � ��C Cn mR .
Çäåñü è äàëåå íîðìà �C ìàòðèöû C� ñî ñòîëáöàìè C C C m
n� � � �1 2, , ,� R îïðå-
äåëÿåòñÿ êàê íîðìà âåêòîðà, êîìïîíåíòàìè êîòîðîãî ÿâëÿþòñÿ íîðìû ñòîëáöîâ
ìàòðèöû
� � � � �C C C Cm
T( , , ... , )1 2 .
Ââèäó ðåãóëÿðíîñòè íîðìû â Rm âûïîëíÿþòñÿ íåðàâåíñòâà �
�C Ci , i N m� .
Êàê îáû÷íî (íàïðèìåð, [9, 14–17]), ðàäèóñîì óñòîé÷èâîñòè çàäà÷è Z Cm ( )
(â òåðìèíîëîãèè [5–8] T3 -óñòîé÷èâîñòè) áóäåì íàçûâàòü âåëè÷èíó
�m C
C C
( )
sup ( ), ( ) ,
�
���
�
�
� �åñëè
â ïðîòèâíîì0
ãäå
� �( ) : ( )C C� � � � �{� �0 ( ( ) ( ))P C C P Cm m� � � }.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 1 83
ñëó÷àå,
Òàêèì îáðàçîì, ðàäèóñ óñòîé÷èâîñòè çàäà÷è Z Cm ( ) — ýòî ïðåäåëüíûé óðî-
âåíü âîçìóùåíèé ýëåìåíòîâ ìàòðèöû C â ïðîñòðàíñòâå Rn m� , êîòîðûå íå ïðèâî-
äÿò ê ïîÿâëåíèþ íîâûõ ýôôåêòèâíûõ âåêòîðîâ.
Åñòåñòâåííî çàäà÷ó Z Cm ( ) íàçûâàòü óñòîé÷èâîé, åñëè �m C( ) � 0 . Ïîñêîëüêó
ëþáûå äâå íîðìû â êîíå÷íîìåðíîì ëèíåéíîì ïðîñòðàíñòâå ýêâèâàëåíòíû [18], òî
âñå óòâåðæäåíèÿ, êàñàþùèåñÿ ïîíÿòèÿ óñòîé÷èâîñòè, íå çàâèñÿò îò âèäà íîðì â
ïðîñòðàíñòâàõ Rm è Rn .  ÷àñòíîñòè, â òðèâèàëüíîì ñëó÷àå, êîãäà ìíîæåñòâî
P C X P Cm m( ): \ ( )� ïóñòî, âêëþ÷åíèå P C C P Cm m( ) ( )� � � èìååò ìåñòî ïðè ëþ-
áîé âîçìóùàþùåé ìàòðèöå C n m� � �R , ïîýòîìó âíå çàâèñèìîñòè îò âèäà íîðì â
Rm è Rn çàäà÷à Z Cm ( ) óñòîé÷èâà ïðè ëþáîé ìàòðèöå C n m� �R . Çàäà÷ó Z Cm ( ) ,
äëÿ êîòîðîé ìíîæåñòâî P Cm ( ) íåïóñòî, áóäåì íàçûâàòü íåòðèâèàëüíîé.
Ââåäåì ìíîæåñòâî Ñëåéòåðà (ìíîæåñòâo ñëàáî ýôôåêòèâíûõ âåêòîðîâ), îïðå-
äåëÿåìîå ïî ïðàâèëó [19]
Sl { Sl }m mC x X x C( ) : ( , )� � �� ,
ãäå
Sl { }m
m ix C x X i N C x x( , ) : (( , ) )� � � � � � � � 0 .
Î÷åâèäíî, ÷òî ïðè êàæäîé ìàòðèöå C n m� �R âûïîëíÿåòñÿ âêëþ÷åíèå
P C Cm m( ) ( )� Sl è äëÿ ëþáîãî âåêòîðà x X� âåðíî âêëþ÷åíèå Slm mx C P x C( , ) ( , )� .
Äëÿ âåêòîðà x P Cm� ( ) ââåäåì ìíîæåñòâî P C P C x Cx
m m( ) ( ) ( , )� � Sl .
Äàëåå èñïîëüçóåì íåñêîëüêî î÷åâèäíûõ âñïîìîãàòåëüíûõ óòâåðæäåíèé.
Ñâîéñòâî 1. Åñëè P C C Xm m( ) ( )� �Sl , òî Ci � 0 ïðè ëþáîì èíäåêñå
i N m� .
Ñâîéñòâî 2. Åñëè P C Cm m( ) ( )� Sl , òî P Cx ( ) �� ïðè ëþáîì âåêòîðå
x P Cm� ( ) .
Ñâîéñòâî 3. Åñëè P C Cm m( ) ( )� Sl , x P Cm� ( ) , x P Cx� � ( ) , òî ( , )C x xi � � � 0
ïðè ëþáîì èíäåêñå i N m� .
Ñâîéñòâî 4. Åñëè C C n m, 0 � �R , x P Cm� ( ) è
P C x C Cm m( ) ( , )� � ��Sl 0 , (3)
òî
P C C Cm m( ) ( )� � ��Sl 0 .
Äåéñòâèòåëüíî, åñëè Slm x C C( , )� ��0 , òî x C Cm� �Sl ( )0 , ïîýòîìó ñâîéñòâî
î÷åâèäíî. Åñëè Slm x C C( , )� ��0 , òî â ñèëó âíåøíåé óñòîé÷èâîñòè ìíîæåñòâà
Ñëåéòåðà (ñì. íàïðèìåð, [19]) ñóùåñòâóåò òàêîé x x C Cm0 0� �Sl ( , ) , ÷òî
x C Cm0 0� �Sl ( ) , ïðè÷åì ââèäó (3) âåêòîð x P Cm0 � ( ) .
Ëåììà. Ïóñòü P C Cm m( ) ( )� Sl , x P Cm� ( ) , ( , )r s N Nm m� � . Ïóñòü â ïðî-
ñòðàíñòâå Rn çàäàíà ïðîèçâîëüíàÿ íîðìà, à â Rm — ðåãóëÿðíàÿ. Òîãäà, ïîëàãàÿ
� �
� �
� �
� �
�
�
�
�
�
�
max
( , )
( , )
: ( )
C x x
C x x
x P Cr
s
x ,
� �� Cs , (4)
èìååì
� � � � � � ��� � �C P C C Cm m0 0�( ) ( ( ) ( ) )Sl . (5)
84 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 1
Äîêàçàòåëüñòâî. Ñëåäóåò îòìåòèòü, ÷òî ñîãëàñíî ñâîéñòâàì 1–3 ñïðàâåäëèâî
íåðàâåíñòâî � � 0 . Âûáåðåì ïðîèçâîëüíî ÷èñëî �, ïîä÷èíåííîå óñëîâèþ
� � �� � Cs . Ñòîëáöû âîçìóùàþùåé ìàòðèöû C n m0 � �R çàäàäèì ïî ïðàâèëó
C
C i r
i N r
i
s
m
0 �
� �
�
�
�
�
� , ,
, \ { }.
åñëè
åñëè0
Òîãäà, ó÷èòûâàÿ ðåãóëÿðíîñòü íîðìû â Rm , ïîëó÷àåì C Cs
0 �� , ò.å. C 0��( )� .
Ïóñòü x P Cm� ( ). Ïîêàæåì, ÷òî âûïîëíÿåòñÿ ðàâåíñòâî (3). Äëÿ ýòîãî äîñòà-
òî÷íî äîêàçàòü, ÷òî íèêàêîé âåêòîð x P Cm0 � ( ) íå ïðèíàäëåæèò ìíîæåñòâó
Slm x C C( , )� 0 . Ðàññìîòðèì äâà ñëó÷àÿ.
Ñëó÷àé 1. Ïóñòü x P Cx
0 � ( ) . Òîãäà, ïðèíèìàÿ âî âíèìàíèå ñòðîåíèå âîçìóùà-
þùåé ìàòðèöû C 0 è îïðåäåëåíèå ÷èñëà � , ïîëó÷àåì
( , ) ( , ) ( , ) ( , )C C x x C x x C x x C x xr r r s r� � � � � � � � �0 0 0 0 0�
� �
� �
� �
� � �
��
( , ) max
( , )
( , )
( , )
( )
C x x
C x x
C x x
C x xs
x P C
r
s
r
x
0 0 ( , )
( , )
( , )
C x x
C x x
C x x
s
r
s
�
�
�
�0
0
0
0 .
Ïîýòîìó x x C Cm0 0 �Sl ( , ) .
Ñëó÷àé 2. Ïóñòü x P C P Cm
x
0 � ( ) \ ( ) . Åñëè ñóùåñòâóåò òàêîé èíäåêñ
l N rm� \ { }, ÷òî ( , )C x xl � �0 0 , òî â ñèëó ñòðîåíèÿ âîçìóùàþùåé ìàòðèöû C 0
èìåþò ìåñòî ñîîòíîøåíèÿ
( , ) ( , )C C x x C x xl l l� � � � �0 0 0 0 .
Åñëè äëÿ âñÿêîãî èíäåêñà i N rm� \ { } ñïðàâåäëèâî íåðàâåíñòâî ( , )C x xi �
0 0 ,
òî (ââèäó � �x X P x C\ ( , )0 ) èìååì ( , )C x xr � �0 0 . Ïîýòîìó ñ ó÷åòîì ñòðîåíèÿ âîç-
ìóùàþùåé ìàòðèöû C 0 ïîëó÷àåì
( , ) ( , )C C x x C x xr r r� � � � �0 0 0 0 ïðè s r� .
( , ) ( , ) ( , )C C x x C x x C x xr r r r� � � � � � �0 0 0 0 0 ïðè s r� .
Ñëåäîâàòåëüíî, è âî âòîðîì ñëó÷àå x x C Cm0 0 �Sl ( , ) .
Ðåçþìèðóÿ óòâåðæäàåì, ÷òî ðàâåíñòâî (3) âåðíî, ïîýòîìó ñîãëàñíî ñâîéñòâó 4
âåðíà ôîðìóëà (5).
Ëåììà äîêàçàíà.
ÎÖÅÍÊÈ ÐÀÄÈÓÑÀ ÓÑÒÎÉ×ÈÂÎÑÒÈ
Êàê áûëî îòìå÷åíî âûøå, íåîáõîäèìûì è äîñòàòî÷íûì óñëîâèåì íåóñòîé÷èâîñòè íå-
òðèâèàëüíîé çàäà÷è Z Cm ( ) ÿâëÿåòñÿ íåñîâïàäåíèå ìíîæåñòâ Ïàðåòî P Cm ( ) è Ñëåéòå-
ðà Slm C( ) . Ïîýòîìó â ýòîì ñëó÷àå ðàäèóñ óñòîé÷èâîñòè çàäà÷è Z Cm ( ) ðàâåí íóëþ.
Îñòàåòñÿ ðàññìîòðåòü ëèøü ñëó÷àé, êîãäà âûïîëíÿåòñÿ ðàâåíñòâî P C Cm m( ) ( )� Sl .
Òåîðåìà 1. Ïóñòü çàäà÷à ÖËÏ Z Cm ( ) , m
1, íåòðèâèàëüíà, P C Cm m( ) ( )� Sl è
ïóñòü â ïðîñòðàíñòâå ðåøåíèé Rn çàäàíà ïðîèçâîëüíàÿ íîðìà, à â êðèòåðèàëüíîì
ïðîñòðàíñòâå Rm íîðìà ðåãóëÿðíà. Òîãäà, ïîëàãàÿ
� �
� �
� �� �� �
min max min
( , )
( ) ( ) *
x P C x P C i N
i
m
x m
C x x
x x
,
� �
� �
� � � ��
min min max
( , )
( ,( ) ( , ) ( )x P C i k N N x P C
i
km
m m x
C x x
C x x
Ck
� � )
, (6)
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 1 85
èìååì
0 � � �� � �m C( ) .
Äîêàçàòåëüñòâî. Îòìåòèì, ÷òî P Cm ( ) �� , òàê êàê çàäà÷à Z Cm ( ) íåòðèâèàëü-
íà. Ïîñêîëüêó âûïîëíÿåòñÿ ðàâåíñòâî P C Cm m( ) ( )� Sl , òî íà îñíîâàíèè êðèòåðèÿ
óñòîé÷èâîñòè çàäà÷è Z Cm ( ) î÷åâèäíî íåðàâåíñòâî �m C( ) � 0 . Êðîìå òîãî, ó÷èòû-
âàÿ ñâîéñòâà 1–3, ëåãêî óâèäåòü, ÷òî � � 0 .
Ñíà÷àëà äîêàæåì ñïðàâåäëèâîñòü íåðàâåíñòâà � �m C( ) � .  ñîîòâåòñòâèè
ñ îïðåäåëåíèåì âåëè÷èíû � íàéäóòñÿ òàêèå x P Cm� ( ) è ( , )r s N Nm m� � , ÷òî âû-
ïîëíÿåòñÿ ðàâåíñòâî (4). Ïîýòîìó ñîãëàñíî ëåììå âåðíà ôîðìóëà (5), ïðè ýòîì íîð-
ìà C 0 � � óäîâëåòâîðÿåò íåðàâåíñòâàì � � �� � . Ïîñêîëüêó P C Cm ( )� �0
� �Slm C C( )0 , òî âîçìîæíû äâà ñëó÷àÿ.
Ñëó÷àé 1. Ïóñòü P C P C Cm m( ) ( )� � ��0 . Òîãäà î÷åâèäíî, ÷òî
P C C P Cm m( ) ( ) ,/� �0 ïðè÷åì C 0 �� ( )� .
Ñëó÷àé 2. Ïóñòü P C P C Cm m( ) ( )� � ��0 . Òîãäà ñóùåñòâóåò âåêòîð
x P C C C P C Cm m m0 0 0� � � �( ( ) ( )) \ ( )Sl . Ïîýòîìó ñîãëàñíî ëåììå 4.2 èç [5]
(ñì. òàêæå [4]) íàéäåòñÿ òàêàÿ ìàòðèöà � ( )C � �� � , ãäå
�� � �� , ÷òî
x P C C Cm0 0� � �( � ) . Èíà÷å ãîâîðÿ, äëÿ âñÿêîãî ÷èñëà � � � � ñóùåñòâóåò òàêàÿ
ìàòðèöà
~
� ( )C C C� � �0 � � , ÷òî P C C P Cm m(
~
) ( ) ./� �
Ðåçþìèðóÿ ýòè ñëó÷àè, ïîëó÷àåì, ÷òî ïðè ëþáîì ÷èñëå � �� ñïðàâåäëèâî íå-
ðàâåíñòâî � �m C( ) � . Ñëåäîâàòåëüíî, � �m C( ) � .
Äàëåå ïîêàæåì ñïðàâåäëèâîñòü íåðàâåíñòâ 0 � �� �m C( ) .
Íà îñíîâàíèè ñâîéñòâà 2 ìíîæåñòâî P Cx ( ) íåïóñòî ïðè ëþáîì âåêòîðå
x P Cm� ( ) . Ïîýòîìó ñîãëàñíî ñâîéñòâó 3 èìååì � � 0 .
Ïóñòü C� �� ( )� . Òîãäà ñîãëàñíî îïðåäåëåíèþ âåëè÷èíû � è ðåãóëÿðíîñòè
íîðìû â Rm äëÿ ëþáîãî x P Cm� ( ) íàéäåòñÿ òàêîé âåêòîð x P Cx
0� ( ) , ÷òî ñïðà-
âåäëèâû ñîîòíîøåíèÿ
� � � � �
�
�
Ñ Ñ
C x x
x x
i
i�
( , )
*
0
0
, i N m� .
Îòñþäà, èñïîëüçóÿ íåðàâåíñòâî Ìèíêîâñêîãî–Ìàëåðà (1), íàõîäèì
( , ) ( , )
*
C C x x C x x Ñ x xi i i i� � �
� � � � �0 0 0 0 , i N m� .
Òàêèì îáðàçîì, x P C Cm� � �( ) , îòêóäà çàêëþ÷àåì, ÷òî ïðè ëþáîé ìàòðèöå
C � ��( )� èìååò ìåñòî âêëþ÷åíèå P C C P Cm m( ) ( )� � � . Ñëåäîâàòåëüíî, âåðíà
îöåíêà ñíèçó � �m C( )
.
Òåîðåìà äîêàçàíà.
Øèðîêèé êëàññ ñêàëÿðíûõ (îäíîêðèòåðèàëüíûõ) òðàåêòîðíûõ çàäà÷, äëÿ êîòî-
ðûõ íèæíÿÿ îöåíêà � äîñòèæèìà, îïèñàí â [16]. Äîñòèæèìîñòü íèæíåé îöåíêè ðà-
äèóñà óñòîé÷èâîñòè âåêòîðíîé ëèíåéíîé áóëåâîé çàäà÷è â ñëó÷àå ÷åáûøåâñêîé
íîðìû l� â ïðîñòðàíñòâàõ Rm è Rn áûëà äîêàçàíà â [9, 17].
Ñëåäñòâèå 1. Ïóñòü çàäà÷à ÖËÏ Z Cm ( ) , m
1, íåòðèâèàëüíà, íîðìà â ïðî-
ñòðàíñòâå Rn ïðîèçâîëüíà, à â ïðîñòðàíñòâå Rm ðåãóëÿðíà. Òîãäà, ïîëîæèâ
( , ) min
( , )
:
*
x x
C x x
x x
i Ni
m� �
� �
� �
�
�
�
�
��
�
�
�
��
, �
� � �
� �� �
min max ( , )
( ) ( ) ( , )x P C x P C P x Cm m m
x x ,
86 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 1
èìååì
� � �
�
� �m
i N
iC C
m
( ) min . (7)
Êðîìå òîãî, ïðè m
2 ðàäèóñ óñòîé÷èâîñòè �m C( ) � 0 òîãäà è òîëüêî òîãäà, êîã-
äà �� � 0 .
Äîêàçàòåëüñòâî. Ñíà÷àëà äîêàæåì ïîñëåäíåå óòâåðæäåíèå ñëåäñòâèÿ. Ïóñòü
�m C( ) � 0 , m
2 . Òîãäà P C Cm m( ) ( )� Sl è ïîýòîìó î÷åâèäíî ñóùåñòâîâàíèå âåê-
òîðà x P C Cm m0 � �( ) ( )Sl . Îòñþäà äëÿ âñÿêîãî x P C P x Cm m� � �( ) ( , ) íàéäåòñÿ
èíäåêñ s N m� ñ óñëîâèåì ( , )C x xs
0 0� � � . Ñëåäîâàòåëüíî, �� � 0 .
Ïóñòü òåïåðü �� � 0 . Òîãäà íàéäåòñÿ òàêîé âåêòîð x P Cm0 � ( ) , ÷òî äëÿ âñÿêîãî
âåêòîðà x P C P x Cm m� � �( ) ( , )0 ñóùåñòâóåò èíäåêñ s N m� ïðè óñëîâèè
( , )C x xs
0 0� � � . Ýòî îçíà÷àåò, ÷òî íèêàêîé âåêòîð x P C P x Cm m� � �( ) ( , )0 íå ïðè-
íàäëåæèò ìíîæåñòâó Slm x C( , )0 è ïîòîìó (ââèäó Slm mx C P x C( , ) ( , )0 0� ) ìíîæå-
ñòâî P C x Cm m( ) ( , )� Sl 0 ïóñòî. Îòñþäà â ñèëó ñâîéñòâà 4 ìíîæåñòâî
P C Cm m( ) ( )� Sl íåïóñòî. Ïîýòîìó P C Cm m( ) ( )� Sl . Ñëåäîâàòåëüíî, çàäà÷à
Z Cm ( ) íå ÿâëÿåòñÿ óñòîé÷èâîé è �m C( ) � 0 .
Äàëåå äîêàçàòåëüñòâî îöåíîê (7) ïðîâåäåì â ïðåäïîëîæåíèè, ÷òî �m C( ) � 0 .
Òîãäà P C Cm m( ) ( )� Sl è ïîýòîìó â ñèëó òåîðåìû � �m C( ) � . Ïîëàãàÿ k i� â âûðà-
æåíèè (6) è ó÷èòûâàÿ ðåãóëÿðíîñòü íîðìû â Rm , ëåãêî óáåäèòüñÿ â ñïðàâåäëèâî-
ñòè âåðõíèõ îöåíîê ôîðìóëû (7).
Íàêîíåö, äîêàæåì, ÷òî � �m C( )
� . Ïîñêîëüêó �m C( ) � 0 , òî P C Cm m( ) ( )� Sl
è ïîýòîìó ñîãëàñíî òåîðåìå 1 íèæíåé îöåíêîé ðàäèóñà óñòîé÷èâîñòè ÿâëÿåòñÿ ÷èñ-
ëî � � 0 . Ëåãêî âèäåòü, ÷òî â ýòèõ ïðåäïîëîæåíèÿõ � �� � . Äåéñòâèòåëüíî, â ñèëó
ñâîéñòâà 3 ïðè ëþáûõ x P Cm� ( ) , x P Cx� � ( ) ÷èñëî
( , )x x� � 0 , à ïðè x P Cm� ( ) è
� � �x P C P x C P Cm m
x( ( ) ( , )) \ ( ) èìååì
( , )x x� � 0 .
Ñëåäñòâèå 1 äîêàçàíî.
Î÷åâèäíî, ÷òî âåðõíÿÿ îöåíêà ðàäèóñà óñòîé÷èâîñòè ñêàëÿðíîé çàäà÷è ÖËÏ
�1 ( )C C� , C n�R , ñïðàâåäëèâà ïðè ëþáîé íîðìå. Óíèâåðñàëüíûé õàðàêòåð
ýòîé îöåíêè âïåðâûå áûë îïèñàí â ðàáîòå [15] (ñì. òàêæå [14]) äëÿ ñêàëÿðíûõ
òðàåêòîðíûõ çàäà÷.
Ñëåäóþùåå ñëåäñòâèå ñâèäåòåëüñòâóåò î äîñòèæèìîñòè íèæíåé îöåíêè ðàäèó-
ñà óñòîé÷èâîñòè, óñòàíîâëåííîé òåîðåìîé 1.
Ñëåäñòâèå 2. Ïóñòü çàäà÷à ÖËÏ Z Cm ( ) , m
1, èìååò åäèíñòâåííûé ýôôåêòèâ-
íûé âåêòîð x0 è ïóñòü íîðìà â ïðîñòðàíñòâå Rn ïðîèçâîëüíà, à â ïðîñòðàíñòâå
Rm — ðåãóëÿðíà. Òîãäà
�m
x X x i N
iC
C x x
x xm
( ) min min
( , )
|| ||\{ } *
�
�
�� �0
0
0
. (8)
Äîêàçàòåëüñòâî. Äëÿ êðàòêîñòè äàëüíåéøåãî èçëîæåíèÿ ëåâóþ ÷àñòü ôîðìó-
ëû (8) îáîçíà÷èì ÷åðåç � .
Ïóñòü P C xm ( ) �{ }0 . Òîãäà ñîãëàñíî îïðåäåëåíèþ âåëè÷èíû � íàéäóòñÿ òàêèå
� ( )x P Cm� è s N m� , ÷òî ñïðàâåäëèâî ðàâåíñòâî
� || � || ( , � )*x x C x xs� � �0 0 , (9)
ïðè ýòîì � � 0 . Çàäàâ � �� , çàôèêñèðóåì ÷èñëî � , óäîâëåòâîðÿþùåå íåðàâåí-
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 1 87
ñòâàì � � �� � .  ñèëó ôîðìóëû (2), ÿâëÿþùåéñÿ ñëåäñòâèåì íåðàâåíñòâà Ìèí-
êîâñêîãî–Ìàëåðà, íàéäåòñÿ òàêîé âåêòîð-ñòîëáåö a n�R , ÷òî
a � � , ( , � ) || � || *a x x x x� � � �0 0� .
Ïîýòîìó, îïðåäåëèâ ñòîëáöû âîçìóùàþùåé ìàòðèöû C n m0 � �R ïî ïðàâèëó
C
a i s
i N s
i
m
0 �
�
�
�
�
�
, ,
\ { } ,
åñëè
åñë è0,
íà îñíîâàíèè ðåãóëÿðíîñòè íîðìû â Rm èìååì
|| ||C 0 � � , ( , � ) || � || *C x x x xs
0 0 0� � � �� .
Îòñþäà è èç ðàâåíñòâà (9) ïîëó÷àåì
( , � ) ( , � ) || � || ( ) || �*C C x x C x x x x x xs s s� � � � � � � � �0 0 0 0 0� � � || * � 0 ,
ò.å. x P x C Cm0 0 �( �, ) . Åñëè P x C Cm ( �, )� ��0 , òî � ( )x P C Cm� � 0 . Åñëè
P x C Cm ( �, )� ��0 , òî áëàãîäàðÿ âíåøíåé óñòîé÷èâîñòè ìíîæåñòâà P C Cm ( )� 0
(ñì., íàïðèìåð, [19]) íàéäåòñÿ òàêîé âåêòîð ~ ( �, )x P x C Cm� � 0 , ÷òî
~ ( )x P C Cm� � 0 .
Èòàê, äëÿ ëþáîãî ÷èñëà � �� ãàðàíòèðóåòñÿ ñóùåñòâîâàíèå òàêîé âîçìóùàþ-
ùåé ìàòðèöû C 0�� ( )� , ÷òî íàéäåòñÿ âåêòîð x X x� � \ { }0 ñ óñëîâèåì
x P C Cm� � �( )0 , ò. å. P C C P Cm m( ) ( )� !�
0 . Ñëåäîâàòåëüíî, � �m C( ) � äëÿ ëþáîãî
� �� . Ýòî ñâèäåòåëüñòâóåò î ñïðàâåäëèâîñòè îöåíêè � �m C( ) � .
Ïîñêîëüêó çàäà÷à Z Cm ( ) íåòðèâèàëüíà ( | ( )|P Cm �1), òî â ñèëó ñëåäñòâèÿ 1
âåðíî íåðàâåíñòâî � �m C( )
. Èñõîäÿ èç ýòîãî, à òàêæå ñ ó÷åòîì ïîêàçàííîé âûøå
îöåíêè � �m C( ) � ïîëó÷àåì ôîðìóëó (8).
Ñëåäñòâèå 2 äîêàçàíî.
Èòàê, íèæíÿÿ îöåíêà ðàäèóñà óñòîé÷èâîñòè � äîñòèæèìà ïðè | ( )|P Cm �1. Èç
ñëåäñòâèÿ 1 âûòåêàåò ñëåäóþùåå óòâåðæäåíèå.
Ñëåäñòâèå 3. Åñëè çàäà÷à ÖËÏ Z Cm ( ) , m
2, íåòðèâèàëüíà, òî ïðè íàëè÷èè â
ìàòðèöå C n m� �R õîòÿ áû îäíîãî íóëåâîãî ñòîëáöà, ðàäèóñ óñòîé÷èâîñòè �m C( ) � 0 .
Î÷åâèäíî, ÷òî ñëåäñòâèå 3 äîêàçûâàåò äîñòèæèìîñòü âåðõíåé îöåíêè ðàäèóñà
óñòîé÷èâîñòè, âûÿâëåííîé ñëåäñòâèåì 1.
Ïîñêîëüêó âñå íîðìû øëüäåðà lp , 1� � �p , ðåãóëÿðíû, òî ÷àñòíûì ñëó÷àåì
ñëåäñòâèÿ 1 ÿâëÿåòñÿ ñëåäóþùèé ðåçóëüòàò.
Ñëåäñòâèå 4. Ïóñòü â ïðîñòðàíñòâàõ Rn è Rm çàäàíà íîðìà øëüäåðà lp :
|| || | | ,
/
z zp i
i
p
p
�
"
#
$
$
%
&
'
'(
1
1� � �p , || || max| |z z
i
i� � .
Òîãäà äëÿ ðàäèóñà óñòîé÷èâîñòè íåòðèâèàëüíîé çàäà÷è ÖËÏ Z Cm ( ) , C n m� �R ,
m
1, ñïðàâåäëèâû îöåíêè
min max min
( , )
|| ||( ) ( , )x P C x P x C i N
i
qm m
m
C x x
x x� �� �
� �
� �
� �m
i p mC C i N C( ) min{ || || : } || ||� � � .
Çäåñü, êàê îáû÷íî, 1 1 1/ /p q� � ïðè 1� � �p ; q �1 ïðè p � � ; q � � ïðè p �1.
 ñëó÷àå ÷åáûøåâñêîé íîðìû l� â ïðîñòðàíñòâàõ Rn è Rm ýòè îöåíêè áûëè
ïîëó÷åíû â [9] (ñì. òàêæå [17]).
88 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 1
Ïîñêîëüêó P C C1 1( ) ( )� Sl , òî èç òåîðåìû 1 âûòåêàåò òàêæå, ÷òî îäíîêðèòåðè-
àëüíàÿ (ñêàëÿðíàÿ) çàäà÷à Z C1 ( ) óñòîé÷èâà ïðè ëþáîì âåêòîðå C n�R .
ÇÀÊËÞ×ÅÍÈÅ
 íàñòîÿùåé ñòàòüå âïåðâûå ïîëó÷åíû íèæíÿÿ è âåðõíÿÿ äîñòèæèìûå îöåíêè
ðàäèóñà óñòîé÷èâîñòè âåêòîðíîãî âàðèàíòà øèðîêî èçâåñòíîé çàäà÷è ÖËÏ â
ïðåäïîëîæåíèè, ÷òî â ïðîñòðàíñòâå ðåøåíèé çàäàíà ïðîèçâîëüíàÿ íîðìà, à â
êðèòåðèàëüíîì ïðîñòðàíñòâå — ìîíîòîííàÿ íîðìà. Ïðè÷åì äîñòèæèìîñòü íèæ-
íåé îöåíêè, ïîëó÷åííîé íà îñíîâå èñïîëüçîâàíèÿ íåðàâåíñòâà Ìèíêîâñêîãî-Ìà-
ëåðà, ãàðàíòèðóåòñÿ óêàçàíèåì òàêîãî êëàññà çàäà÷, äëÿ êîòîðûõ ýòà îöåíêà ÿâ-
ëÿåòñÿ ôîðìóëîé. Ïðèâîäèòñÿ òàêæå ëåãêî âû÷èñëèìàÿ äîñòèæèìàÿ âåðõíÿÿ
îöåíêà, ðàâíàÿ ìèíèìàëüíîé èç íîðì ñòîëáöîâ ìàòðèöû êîýôôèöèåíòîâ âåêòîð-
íîãî êðèòåðèÿ. Èç ýòèõ ðåçóëüòàòîâ åñòåñòâåííûì îáðàçîì âûòåêàþò èçâåñòíûå
ðàíåå îöåíêè ðàäèóñà óñòîé÷èâîñòè ðàññìàòðèâàåìîé çàäà÷è äëÿ ñëó÷àÿ ÷åáû-
øåâñêîé ìåòðèêè â ïðîñòðàíñòâàõ ðåøåíèé è êðèòåðèåâ.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. Ê î ç å p à ö ê à ÿ Ë . Í . , Ë å á å ä å â à Ò . Ò . , Ñ å ð ã è å í ê î Ò . È .  î ï ðîñû ïàpàìåòpè÷åñêîãî àíàëèçà
è èññëåäîâàíèå óñòîé÷èâîñòè ìíîãîêðèòåðèàëüíûõ çàäà÷ öåëî÷èñëåííîãî ëèíåéíîãî ïðîãðàì-
ìèðîâàíèÿ // Êèáåðíåòèêà. — 1988. — ¹ 3. — Ñ. 41–44.
2. Ê î ç å p à ö ê à ÿ Ë . Í . , Ë å á å ä å â à Ò . Ò . , Ñ å ð ã è å í ê î Ò . È . Íåîáõîäèìûå è äîñòàòî÷íûå óñëîâèÿ
ìíîãîêðèòåðèàëüíûõ çàäà÷ öåëî÷èñëåííîãî ïðîãðàììèðîâàíèÿ // Äîêë. ÀÍ ÓÑÑÐ. Ñåð. À. —
1988. — ¹ 10. — Ñ. 76–78.
3. Ê î ç å p à ö ê à ÿ Ë . Í . , Ë å á å ä å â à Ò . Ò . , Ñ å ð ã è å í ê î Ò . È . Çàäà÷è öåëî÷èñëåííîãî ïpîãpàì-
ìèpîâàíèÿ ñ âåêòîpíûì êpèòåpèåì: ïàpàìåòpè÷åñêèé àíàëèç è èññëåäîâàíèå óñòîé÷èâîñòè // Äîêë.
ÀÍ ÑÑÑÐ. — 1989. — 307, ¹ 3. — Ñ. 527–529.
4. Ñ å ð ã è å í ê î È .  . , Ê î ç å ð à ö ê à ÿ Ë . Í . , Ë å á å ä å â à Ò . Ò . Èññëåäîâàíèå óñòîé÷èâîñòè è
ïàðàìåòðè÷åñêèé àíàëèç äèñêðåòíûõ îïòèìèçàöèîííûõ çàäà÷. — Êèåâ: Íàóê. äóìêà, 1995. — 170 c.
5. Ñ å ð ã è å í ê î È .  . , Ø è ë î  . Ï . Çàäà÷è äèñêðåòíîé îïòèìèçàöèè. Ïðîáëåìû, ìåòîäû ðåøåíèÿ,
èññëåäîâàíèÿ. — Êèåâ: Íàóê. äóìêà, 2003. — 261 ñ.
6. Ë å á å ä å â à Ò . Ò . , Ñ å ð ã è å í ê î Ò . È . Ñðàâíèòåëüíûé àíàëèç ðàçëè÷íûõ òèïîâ óñòîé÷èâîñòè ïî
îãðàíè÷åíèÿì âåêòîðíîé çàäà÷è öåëî÷èñëåííîé îïòèìèçàöèè // Êèáåðíåòèêà è ñèñòåìíûé àíà-
ëèç. — 2004. — ¹ 1. — Ñ. 63–70.
7. Ë å á å ä å â à Ò . Ò . , Ñ å ì å í î â à Í .  . , Ñ å ð ã è å í ê î Ò . È . Óñòîé÷èâîñòü âåêòîðíûõ çàäà÷ öåëî-
÷èñëåííîé îïòèìèçàöèè: âçàèìîñâÿçü ñ óñòîé÷èâîñòüþ ìíîæåñòâ îïòèìàëüíûõ è íåîïòèìàëüíûõ
ðåøåíèé // Òàì æå. — 2005. — ¹ 4. — Ñ. 90–100.
8. Ë å á å ä å â à Ò . Ò . , Ñ å ð ã è å í ê î Ò . È . Ðàçíûå òèïû óñòîé÷èâîñòè âåêòîðíîé çàäà÷è öåëî÷èñëåííîé
îïòèìèçàöèè: îáùèé ïîäõîä // Òàì æå. — 2008. — ¹ 3. — Ñ. 142–148.
9. Å ì å ë è ÷ å â  . À . , Ï î ä ê î ï à å â Ä . Ï . Î êîëè÷åñòâåííîé ìåðå óñòîé÷èâîñòè âåêòîðíîé çàäà÷è
öåëî÷èñëåííîãî ïðîãðàììèðîâàíèÿ // Æóðí. âû÷èñë. ìàòåìàòèêè è ìàò. ôèçèêè. — 1998. — 38,
¹ 11. — Ñ. 1801–1805.
10. Å ì å ë è ÷ å â  . À . , Ê ó ç ü ì è í Ê . à . Îá îäíîì òèïå óñòîé÷èâîñòè ìíîãîêðèòåðèàëüíîé çàäà÷è
öåëî÷èñëåííîãî ëèíåéíîãî ïðîãðàììèðîâàíèÿ â ñëó÷àå ìîíîòîííîé íîðìû // Èçâ. ÐÀÍ. Òåîðèÿ è
ñèñòåìû óïðàâëåíèÿ. — 2007. — ¹ 5. — Ñ. 45–51.
11. Å ì å ë è ÷ å â  . À . , Ê ó ç ü ì è í Ê . à . Îáùèé ïîäõîä ê èññëåäîâàíèþ óñòîé÷èâîñòè ïàðåòî-
îïòèìàëüíîãî ðåøåíèÿ âåêòîðíîé çàäà÷è öåëî÷èñëåííîãî ëèíåéíîãî ïðîãðàììèðîâàíèÿ // Äèñêðåò-
íàÿ ìàòåìàòèêà. — 2007. — 19. — Âûï. 3. — Ñ. 79–83.
12. Á å ê ê å í á à õ Ý . , Á å ë ë ì à í Ð . Íåðàâåíñòâà. — Ì.: Ìèð, 1965. — 276 ñ.
13. Ê à ò î Ò . Òåîðèÿ âîçìóùåíèé ëèíåéíûõ îïåðàòîðîâ. — Ì.: Ìèð, 1972. — 740 ñ.
14. Ë å î í ò ü å â  . Ê . Óñòîé÷èâîñòü â ëèíåéíûõ äèñêðåòíûõ çàäà÷àõ // Ïðîáë. êèáåðíåòèêè. — 1979. —
Âûï. 35. — Ñ. 169–184.
15. Ë å î í ò ü å â  . Ê . , à î ð ä å å â Ý . Í . Êà÷åñòâåííîå èññëåäîâàíèå òðàåêòîðíûõ çàäà÷ // Êèáåð-
íåòèêà. — 1986. — ¹ 5. — Ñ. 82–89.
16. à î ð ä å å â Ý . Í . , Ë å î í ò ü å â  . Ê . Îáùèé ïîäõîä ê èññëåäîâàíèþ óñòîé÷èâîñòè ðåøåíèé
â çàäà÷àõ äèñêðåòíîé îïòèìèçàöèè // Æóðí. âû÷èñë. ìàòåìàòèêè è ìàò. ôèçèêè. — 1996. — 36,
¹ 1. — Ñ. 66–72.
17. E m e l i c h e v V . A . , G i r l i c h E . , N i k u l i n Y u . V . , P o d k o p a e v D . P . Stability and regularization
of vector problems of integer linear programming // Optimization. — 2002. — 51, N 4. — P. 645–676.
18. Ê î ë ì î ã î ð î â À . Í . , Ô î ì è í Ñ . Â . Ýëåìåíòû òåîðèè ôóíêöèé è ôóíêöèîíàëüíîãî àíàëèçà. —
Ì.: Ôèçìàòëèò, 2004. — 572 ñ.
19. Ï î ä è í î â ñ ê è é Â . Â . , Í î ã è í Â . Ä . Ïàðåòî-îïòèìàëüíûå ðåøåíèÿ ìíîãîêðèòåðèàëüíûõ
çàäà÷. — Ì.: Íàóêà, 1982. — 256 c.
Ïîñòóïèëà 29.10.2008
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 1 89
|
| id | nasplib_isofts_kiev_ua-123456789-45128 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0023-1274 |
| language | Russian |
| last_indexed | 2025-12-07T15:50:52Z |
| publishDate | 2010 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Емеличев, В.А. Кузьмин, К.Г. 2013-06-07T19:25:28Z 2013-06-07T19:25:28Z 2010 О радиусе устойчивости векторной задачи целочисленного линейного программирования в случае регулярности нормы в критериальном пространстве / В.А. Емеличев, К.Г. Кузьмин // Кибернетика и системный анализ. — 2010. — № 1. — С. 82–89. — Бібліогр.: 19 назв. — рос. 0023-1274 https://nasplib.isofts.kiev.ua/handle/123456789/45128 519.8 Розглянуто багатокритеріальний варіант задачі цілочисельного лінійного програмування зі скінченною множиною допустимих рішень, що полягає в пошуку множини Парето. Використовуючи нерівність Мінковського–Малера, а також відомий критерій стійкості задачі, отримано нижню і верхню досяжні оцінки радіуса стійкості задачі, припускаючи, що норма в просторі розв’язків довільна, а в критеріальному просторі монотонна. Як наслідок, наведено оцінки радіуса стійкості задачі в просторах з метрикою Гельдера. A multicriteria integer linear programming problem of finding a Pareto set is considered. The set of feasible solutions is supposed to be finite. Using the Minkowski-Mahler inequality and known stability criteria of the problem, lower and upper accessible bounds for the radius of stability are obtained under the assumption that the norm is arbitrary in the space of solutions and monotone in the space of criteria. Bounds for the radius of stability of the problem in spaces with the Helder metric are given as corollaries. ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Системный анализ О радиусе устойчивости векторной задачи целочисленного линейного программирования в случае регулярности нормы в критериальном пространстве Про радіус стійкості векторної задачі цілочисельного лінійного програмування у випадку регулярності норми в критеріальному просторі On the stability radius of a vector integer linear programming problem in the case of the regular norm in the space of criteria Article published earlier |
| spellingShingle | О радиусе устойчивости векторной задачи целочисленного линейного программирования в случае регулярности нормы в критериальном пространстве Емеличев, В.А. Кузьмин, К.Г. Системный анализ |
| title | О радиусе устойчивости векторной задачи целочисленного линейного программирования в случае регулярности нормы в критериальном пространстве |
| title_alt | Про радіус стійкості векторної задачі цілочисельного лінійного програмування у випадку регулярності норми в критеріальному просторі On the stability radius of a vector integer linear programming problem in the case of the regular norm in the space of criteria |
| title_full | О радиусе устойчивости векторной задачи целочисленного линейного программирования в случае регулярности нормы в критериальном пространстве |
| title_fullStr | О радиусе устойчивости векторной задачи целочисленного линейного программирования в случае регулярности нормы в критериальном пространстве |
| title_full_unstemmed | О радиусе устойчивости векторной задачи целочисленного линейного программирования в случае регулярности нормы в критериальном пространстве |
| title_short | О радиусе устойчивости векторной задачи целочисленного линейного программирования в случае регулярности нормы в критериальном пространстве |
| title_sort | о радиусе устойчивости векторной задачи целочисленного линейного программирования в случае регулярности нормы в критериальном пространстве |
| topic | Системный анализ |
| topic_facet | Системный анализ |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/45128 |
| work_keys_str_mv | AT emeličevva oradiuseustoičivostivektornoizadačiceločislennogolineinogoprogrammirovaniâvslučaeregulârnostinormyvkriterialʹnomprostranstve AT kuzʹminkg oradiuseustoičivostivektornoizadačiceločislennogolineinogoprogrammirovaniâvslučaeregulârnostinormyvkriterialʹnomprostranstve AT emeličevva proradíusstíikostívektornoízadačícíločiselʹnogolíníinogoprogramuvannâuvipadkuregulârnostínormivkriteríalʹnomuprostorí AT kuzʹminkg proradíusstíikostívektornoízadačícíločiselʹnogolíníinogoprogramuvannâuvipadkuregulârnostínormivkriteríalʹnomuprostorí AT emeličevva onthestabilityradiusofavectorintegerlinearprogrammingprobleminthecaseoftheregularnorminthespaceofcriteria AT kuzʹminkg onthestabilityradiusofavectorintegerlinearprogrammingprobleminthecaseoftheregularnorminthespaceofcriteria |