О комбинаторной оптимизации в условиях неопределенности
Saved in:
| Published in: | Кибернетика и системный анализ |
|---|---|
| Date: | 2008 |
| Main Authors: | , |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2008
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/44251 |
| 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: | О комбинаторной оптимизации в условиях неопределенности / О.А. Емец, А.А. Роскладка // Кибернетика и системный анализ. — 2008. — № 5. — С. 35-44 . — Бібліогр.: 47 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859988049784471552 |
|---|---|
| author | Емец, О.А. Роскладка, А.А. |
| author_facet | Емец, О.А. Роскладка, А.А. |
| citation_txt | О комбинаторной оптимизации в условиях неопределенности / О.А. Емец, А.А. Роскладка // Кибернетика и системный анализ. — 2008. — № 5. — С. 35-44 . — Бібліогр.: 47 назв. — рос. |
| collection | DSpace DC |
| container_title | Кибернетика и системный анализ |
| first_indexed | 2025-12-07T16:30:15Z |
| format | Article |
| fulltext |
ÓÄÊ 519.85
Î.À. ÅÌÅÖ, À.À. ÐÎÑÊËÀÄÊÀ
Î ÊÎÌÁÈÍÀÒÎÐÍÎÉ ÎÏÒÈÌÈÇÀÖÈÈ Â ÓÑËÎÂÈßÕ
ÍÅÎÏÐÅÄÅËÅÍÍÎÑÒÈ
Êëþ÷åâûå ñëîâà: êîìáèíàòîðíàÿ îïòèìèçàöèÿ, íåîïðåäåëåííîñòü, ñëó÷àéíàÿ
âåëè÷èíà, ñòîõàñòè÷åñêîå ìíîæåñòâî.
ÏÎÑÒÀÍÎÂÊÀ ÏÐÎÁËÅÌÛ Â ÎÁÙÅÌ ÂÈÄÅ È ÅÅ ÑÂßÇÜ
Ñ ÂÀÆÍÛÌÈ ÍÀÓ×ÍÛÌÈ ÇÀÄÀÍÈßÌÈ
Òåîðèÿ è ìåòîäû êîìáèíàòîðíîé îïòèìèçàöèè, ÿâëÿÿñü ðàçäåëîì äèñêðåòíîé
îïòèìèçàöèè [1–9], â íàñòîÿùåå âðåìÿ àêòèâíî ðàçâèâàþòñÿ íà îñíîâå ïîãðó-
æåíèÿ êîìáèíàòîðíûõ ìíîæåñòâ â åâêëèäîâî ïðîñòðàíñòâî â ðàìêàõ åâêëèäî-
âîé êîìáèíàòîðíîé îïòèìèçàöèè [10–29].
Ðàçâèòèå åâêëèäîâîé êîìáèíàòîðíîé îïòèìèçàöèè ñ ó÷åòîì íåîïðåäåëåííî çà-
äàííîé èíôîðìàöèè îáóñëîâèëî ïîÿâëåíèå íîâûõ ìîäåëåé, êîòîðûå èñïîëüçóþò èñ-
õîäíûå äàííûå â óñëîâèÿõ íåîïðåäåëåííîñòè [10, 19, 20, 22, 25, 27–30].
Ðàññìîòðèì íåîáõîäèìûå îñíîâíûå ïîíÿòèÿ è îïðåäåëåíèÿ åâêëèäîâîé êîìáè-
íàòîðíîé îïòèìèçàöèè, îïèðàÿñü â îñíîâíîì íà [10]. Îáîçíà÷èì Jm ìíîæåñòâî
ïåðâûõ m íàòóðàëüíûõ ÷èñåë, ò.å. J mm � { }1, . . . , . Ïîä ìóëüòèìíîæåñòâîì
G g g g� { }1 2, , . . . , � áóäåì ïîíèìàòü ñîâîêóïíîñòü ýëåìåíòîâ, ñðåäè êîòîðûõ ìîãóò
áûòü è îäèíàêîâûå (íåðàçëè÷èìûå). Ëþáîå ìóëüòèìíîæåñòâî G, êîòîðîå èìååò n
ðàçíûõ ýëåìåíòîâ, ìîæíî çàäàòü åãî îñíîâàíèåì S G e e en( ) ( , , . . . , )� 1 2 — êîðòå-
æåì âñåõ ðàçíûõ ýëåìåíòîâ èç G è êðàòíîñòüþ — ÷èñëîì ïîâòîðåíèé êàæäîãî ýëå-
ìåíòà îñíîâàíèÿ ýòîãî ìóëüòèìíîæåñòâà. Êîðòåæ êðàòíîñòåé ìóëüòèìíîæåñòâà íà-
çûâàþò åãî ïåðâè÷íîé ñïåöèôèêàöèåé è îáîçíà÷àþò [ ]G � ( , , . . . , )� � �1 2 n . Íå íà-
ðóøàÿ îáùíîñòè ñóæäåíèé, áóäåì ñ÷èòàòü, ÷òî ýëåìåíòû ìóëüòèìíîæåñòâà G
óïîðÿäî÷åíû ïî âîçðàñòàíèþ, ò.å. èìååò ìåñòî íåðàâåíñòâî g g g1 2� � �. . . � .
Ðàññìîòðèì óïîðÿäî÷åííóþ k-âûáîðêó èç ìóëüòèìíîæåñòâà G
e g g gi i ik
� ( , , . . . , )
1 2
, (1)
ãäå g Gij
� , i ij t� � �i i Jj t, � , � �j t Jk, .
Ìíîæåñòâî E, ýëåìåíòàìè êîòîðîãî ÿâëÿþòñÿ k-âûáîðêè e e ek� ( , . . . , )1 ,
~ (~ , . . . , ~ )e e ek� 1 âèäà (1) èç ìóëüòèìíîæåñòâà G, íàçîâåì åâêëèäîâûì êîìáèíàòîð-
íûì ìíîæåñòâîì, åñëè èç óñëîâèÿ � �j Jk , e ej j� ~ ñëåäóåò e e� ~.
Äðóãèìè ñëîâàìè, ñâîéñòâî ìíîæåñòâà E çàêëþ÷àåòñÿ â ñëåäóþùåì: äâà ýëå-
ìåíòà e è ~e , ïðèíàäëåæàùèå ýòîìó ìíîæåñòâó, ðàçëè÷íû, åñëè îíè íåçàâèñèìî îò
äðóãèõ îòëè÷èé èìåþò ðàçíûé ïîðÿäîê ñëåäîâàíèÿ ñèìâîëîâ, êîòîðûå èõ îáðàçóþò.
Íàèáîëåå ðàñïðîñòðàíåííûìè ñðåäè åâêëèäîâûõ êîìáèíàòîðíûõ ìíîæåñòâ
ÿâëÿþòñÿ:
— îáùåå ìíîæåñòâî ïåðåñòàíîâîê E Gkn ( ) — ìíîæåñòâî âñåõ k-âûáîðîê
âèäà (1), ãäå k n� �� , èç ìóëüòèìíîæåñòâà G, êîòîðîå ñîñòîèò èç k äåéñòâèòåëü-
íûõ ÷èñåë, ñðåäè êîòîðûõ n ðàçëè÷íûõ;
— îáùåå ìíîæåñòâî ðàçìåùåíèé E Gn
k
� ( ) — ñîâîêóïíîñòü âñåõ óïîðÿäî÷åííûõ
k-âûáîðîê âèäà (1) èç ìóëüòèìíîæåñòâà G, êîòîðîå ñîñòîèò èç � äåéñòâèòåëüíûõ ÷è-
ñåë, ñðåäè êîòîðûõ n ðàçëè÷íûõ ïðè óñëîâèè � i k� � �i Jk ;
— îáùåå ìíîæåñòâî ñî÷åòàíèé S Gn
k
� ( ) — ñîâîêóïíîñòü âñåõ k-âûáîðîê
âèäà (1) èç ìóëüòèìíîæåñòâà G, ñîñòîÿùåãî èç � äåéñòâèòåëüíûõ ÷èñåë, ñðåäè
êîòîðûõ n ðàçëè÷íûõ ïðè óñëîâèè � i k� � �i Jk .
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 5 35
© Î.À. Åìåö, À.À. Ðîñêëàäêà, 2008
Åñëè íàëè÷èå è êîëè÷åñòâî îäèíàêîâûõ ÷èñåë ñðåäè ýëåìåíòîâ ìóëüòèìíî-
æåñòâà íå ÿâëÿåòñÿ ñóùåñòâåííûì, òî ñîîòâåòñòâóþùèå åâêëèäîâûå êîìáèíàòîð-
íûå ìíîæåñòâà áóäåì îáîçíà÷àòü E Gn ( ), E Gn
k ( ) è S Gn
k ( ).
Ïîä îáùåé çàäà÷åé åâêëèäîâîé êîìáèíàòîðíîé îïòèìèçàöèè ïîíèìàþò çà-
äà÷ó íàõîæäåíèÿ
F x F x
x E
( ) min ( )* �
�
, (2)
x F x
x E
* min ( )�
�
arg (3)
ïðè îãðàíè÷åíèÿõ
� i
mx i J( ) � � �0 , (4)
ãäå m — íåêîòîðûå öåëûå íåîòðèöàòåëüíûå êîíñòàíòû; E — åâêëèäîâî êîì-
áèíàòîðíîå ìíîæåñòâî â ïðîñòðàíñòâå R k ; F x( ), � i x( ), � r i x ( ) — íåêîòîðûå
ôóíêöèè.
Ðàññìîòðèì àíàëèç ïîñëåäíèõ èññëåäîâàíèé è ïóáëèêàöèé, â êîòîðûõ ïîëî-
æåíî íà÷àëî ðåøåíèþ äàííîé ïðîáëåìû, è âûäåëèì ðàíåå íåðåøåííûå ÷àñòè
îáùåé ïðîáëåìû.
Èññëåäîâàòåëè òåîðèè è ìåòîäîâ åâêëèäîâîé êîìáèíàòîðíîé îïòèìèçàöèè
ïðîäâèíóëèñü â ðåøåíèè äåòåðìèíèðîâàííûõ çàäà÷ îïòèìèçàöèè (2), (3) íà ìíî-
ãèõ åâêëèäîâûõ êîìáèíàòîðíûõ ìíîæåñòâàõ ñ ëèíåéíûìè, äðîáíî-ëèíåéíûìè,
âûïóêëûìè è âîãíóòûìè öåëåâûìè ôóíêöèÿìè, à òàêæå ñîîòâåòñòâóþùèõ ëè-
íåéíûõ çàäà÷ ñ äîïîëíèòåëüíûìè îãðàíè÷åíèÿìè âèäà (4), (5) [10–19, 21–24, 26].
Îäíàêî ìîäåëü (2)–(4) íå ó÷èòûâàåò òîãî, ÷òî ìíîãèì ôàêòîðàì, õàðàêòåðè-
çóþùèì ðåàëüíûå ïðîöåññû, ñâîéñòâåííà íåîïðåäåëåííîñòü. Èñõîäíàÿ èíôîðìà-
öèÿ äëÿ ïëàíèðîâàíèÿ, ïðîåêòèðîâàíèÿ è óïðàâëåíèÿ â ýêîíîìèêå, òåõíèêå, âî-
åííîì äåëå, êàê ïðàâèëî, íåäîñòàòî÷íî äîñòîâåðíàÿ. Ïëàíèðîâàíèå ïðîèçâîäñòâà
òàêæå îáû÷íî ïðîèñõîäèò â óñëîâèÿõ íåïîëíîé èíôîðìàöèè îá îáñòàíîâêå, â êî-
òîðîé áóäåò âûïîëíÿòüñÿ ïëàí è ðåàëèçîâûâàòüñÿ âûðàáîòàííàÿ ïðîäóêöèÿ.
Èãíîðèðîâàíèå íåîïðåäåëåííîñòè ïàðàìåòðîâ çàäà÷è, êàê ïðàâèëî, ïðèâîäèò ê
èñêàæåíèþ ðåçóëüòàòîâ è ïîòåðå àäåêâàòíîñòè ðàññìàòðèâàåìîé ìîäåëè [3].
Ïîñëåäóþùåå ðàçâèòèå åâêëèäîâîé êîìáèíàòîðíîé îïòèìèçàöèè ïðèâåëî ê
âîçìîæíîñòè ðàññìîòðåíèÿ îïòèìèçàöèîííûõ çàäà÷ íà åâêëèäîâûõ êîìáèíàòîð-
íûõ ìíîæåñòâàõ â óñëîâèÿõ íåîïðåäåëåííîñòè [19, 20, 22, 23, 25, 27–29]. Ïîíÿ-
òèå íåîïðåäåëåííîñòè î÷åâèäíî ÿâëÿåòñÿ ÷ðåçâû÷àéíî øèðîêèì: — îò ÷åòêîãî
óêàçàíèÿ ãðàíèö è õàðàêòåðà èçìåíåíèÿ ñëó÷àéíûõ ôàêòîðîâ äî ñëó÷àåâ ñ âûñî-
êîé ñòåïåíüþ íåîïðåäåëåííîñòè, â êîòîðîé ìîæíî ãîâîðèòü ëèøü î ãèïîòåçàõ,
êîòîðûå õàðàêòåðèçóþò ïîâåäåíèå ñëó÷àéíûõ ïàðàìåòðîâ çàäà÷è.  ïîñòàíîâêàõ
çàäà÷ îïòèìèçàöèè ìîæíî âûäåëèòü òàêèå îñíîâíûå âèäû íåîïðåäåëåííîñòè
äàííûõ:
— ñòîõàñòè÷åñêàÿ íåîïðåäåëåííîñòü — èçâåñòíû çàêîíû ðàñïðåäåëåíèÿ
âåðîÿòíîñòåé;
— èíòåðâàëüíàÿ íåîïðåäåëåííîñòü — çíà÷åíèÿ äàííûõ ëåæàò â èçâåñòíûõ
èíòåðâàëàõ;
— íå÷åòêàÿ íåîïðåäåëåííîñòü — äàííûå â âèäå íå÷åòêèõ ìíîæåñòâ;
— ïàðàìåòðè÷åñêàÿ íåîïðåäåëåííîñòü — çíà÷åíèÿ çàâèñÿò îò íåêîòîðîãî
ïàðàìåòðà;— ìíîãîêðèòåðèàëüíàÿ íåîïðåäåëåííîñòü âûðàæàåòñÿ íåîáõîäèìîñ-
òüþ ìíîãîêðèòåðèàëüíîé îïòèìèçàöèè.
Îïòèìèçàöèÿ â óñëîâèÿõ íåîïðåäåëåííîñòè íà êîìáèíàòîðíûõ ìíîæåñòâàõ
â ïåðâóþ î÷åðåäü èñïîëüçóåò ïîäõîäû è ìåòîäîëîãèþ äèñêðåòíîãî
ïðîãðàììèðîâàíèÿ.
Èññëåäîâàíèå çàäà÷ ïåðâîé ãðóïïû îïèðàåòñÿ íà àïïàðàò òåîðèè âåðîÿòíîñ-
òåé [31] è ñòîõàñòè÷åñêîãî ïðîãðàììèðîâàíèÿ [32, 33].  îñíîâå âòîðîãî ïîäõîäà
ëåæàò ïîíÿòèÿ èíòåðâàëüíîé ãåîìåòðèè è èíòåðâàëüíîãî àíàëèçà [30, 34–37]. Íå-
îïðåäåëåííîñòü òðåòüåãî âèäà îñíîâàíà íà èñïîëüçîâàíèè òåîðèè íå÷åòêèõ ìíî-
æåñòâ [34, 38, 39]. ×åòâåðòûé ïîäõîä ê ó÷åòó íåîïðåäåëåííîñòè èññëåäóåòñÿ ñðå-
36 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 5
äñòâàìè ócòîé÷èâîñòè è ïàðàìåòðè÷åñêîãî àíàëèçà [4]. Ïÿòûé òèï
íåîïðåäåëåííîñòè èññëåäóåòñÿ ìåòîäàìè âåêòîðíîé îïòèìèçàöèè [5, 40–45].
Îñíîâíàÿ öåëü ñòàòüè çàêëþ÷àåòñÿ â ïîèñêå îáùåãî ïîäõîäà ê ïîñòàíîâêå è
èññëåäîâàíèþ çàäà÷ åâêëèäîâîé êîìáèíàòîðíîé îïòèìèçàöèè.
ÈÇËÎÆÅÍÈÅ ÎÑÍÎÂÍÎÃÎ ÌÀÒÅÐÈÀËÀ
1. Ïîñòàíîâêà îáùåé çàäà÷è åâêëèäîâîé êîìáèíàòîðíîé îïòèìèçàöèè
â óñëîâèÿõ íåîïðåäåëåííîñòè.Îáùóþ çàäà÷ó åâêëèäîâîé êîìáèíàòîðíîé
îïòèìèçàöèè â óñëîâèÿõ íåîïðåäåëåííîñòè ìîæíî ïðåäñòàâèòü â âèäå
S F x F xt{ } extr1 ( ~ , ), . . . , ( ~ , )
�
� �� � , (5)
� �i mx i J( ~ , )
� � � �0 , (6)
� �~ ~
x E , (7)
� �
, (8)
ãäå
� �
�~ ( , | )x x x x� � — íå÷åòêî îïðåäåëåííûé ýëåìåíò èíòåðâàëüíîãî ïðîñòðà-
íñòâà I R n( ), çàäàííûé ñ ïîãðåøíîñòüþ èçìåðåíèÿ � x è ñî çíà÷åíèåì ôóíêöèè
ïðèíàäëåæíîñòè, ðàâíûì �x; m — öåëàÿ íåîòðèöàòåëüíàÿ êîíñòàíòà; � — ñëó-
÷àéíûé ïàðàìåòð, êîòîðûé õàðàêòåðèçóåò îïðåäåëåííîå ñîñòîÿíèå ñðåäû;
—
ìíîæåñòâî ýòèõ ñîñòîÿíèé; F xt ( ~ , )
� � — ìíîãîêðèòåðèàëüíûé (t-êðèòåðèàëüíûé)
èíòåðâàëüíîçíà÷íûé öåëåâîé ôóíêöèîíàë, êîòîðûé çàâèñèò òàêæå îò �; S — íå-
êîòîðàÿ âåêòîðíàÿ ñòîõàñòè÷åñêàÿ ôóíêöèÿ, êàæäàÿ êîìïîíåíòà êîòîðîé èìååò
ñòàòèñòè÷åñêîå ñîäåðæàíèå (ìàòåìàòè÷åñêîå îæèäàíèå, äèñïåðñèÿ, âåðîÿòíîñòü
íåïðåâûøåíèÿ çàäàííîãî ïîðîãà è ò.ï.); � i , i Jm� , — íåêîòîðûå ñòîõàñòè÷åñêèå
ôóíêöèè;
~
E — íå÷åòêî çàäàííîå åâêëèäîâî êîìáèíàòîðíîå ìíîæåñòâî ñ ðàíäî-
ìèçèðîâàííûìè ñâîéñòâàìè èç ýëåìåíòîâ èíòåðâàëüíîãî ïðîñòðàíñòâà:
~
( )E I R n� . Êàæäûé ýëåìåíò ìîäåëè (5)–(8) ìîæíî ðàññìàòðèâàòü êàê çàâèñèìûé
îò ðÿäà ïàðàìåòðîâ.
2. Ïîñòðîåíèå ìîäåëè çàäà÷è åâêëèäîâîé êîìáèíàòîðíîé îïòèìèçàöèè
â óñëîâèÿõ ñòîõàñòè÷åñêîé íåîïðåäåëåííîñòè. Ðàññìîòðèì ïðèìåð ïîñòðîåíèÿ
ìàòåìàòè÷åñêîé ìîäåëè â âèäå (5)–(8) â óñëîâèÿõ ñòîõàñòè÷åñêîé
íåîïðåäåëåííîñòè.
Ïóñòü ñóùåñòâóåò íåêîòîðàÿ ïîëóáåñêîíå÷íàÿ (äîñòàòî÷íî äëèííàÿ) ïîëîñà,
êîòîðàÿ ðàçäåëåíà íà ïîëîñêè îäèíàêîâîé øèðèíû h (ðèñ. 1). Çàäàíî p ïðÿìîóãîëü-
íèêîâ äëèíîé a a p1, . . . , è øèðèíîé h. Çàäà÷à ñîñòîèò â ðàçìåùåíèè ïðÿìîóãîëüíè-
êîâ áåç íàëîæåíèé â ïîëîñå îò åå íà÷àëà òàêèì îáðàçîì, ÷òîáû äëèíà çàíÿòîé ÷àñòè
ïîëîñû áûëà ìèíèìàëüíî âîçìîæíîé.
Çàäà÷à è òî÷íûå ìåòîäû åå ðåøåíèÿ â äåòåðìèíèðîâàííîé ïîñòàíîâêå ðàñ-
ñìîòðåíû â [11], à ïðèáëèæåííûå ìåòîäû — â [10, 19, 25]. Îäíàêî íà ïðàêòèêå
äëèíû ïðÿìîóãîëüíèêîâ a a a p1 2, , . . . , èìåþò ïîãðåøíîñòè èçìåðåíèé, äëÿ êîòî-
ðûõ, â ñâîþ î÷åðåäü, çàäàí çàêîí ðàñïðåäåëåíèÿ çíà÷åíèé. Ïîýòîìó ðàññìîòðå-
íèå çàäà÷è ñ ó÷åòîì ñòîõàñòè÷åñêîé íåîïðåäåëåííîñòè â çàäàíèè íà÷àëüíûõ
äàííûõ ÿâëÿåòñÿ àêòóàëüíîé ïðîáëåìîé.
Ñòîõàñòè÷åñêàÿ íåîïðåäåëåííîñòü ÿâëÿåòñÿ ðàñïðîñòðàíåííûì òèïîì íå-
îïðåäåëåííîñòè è ïðèñóùà ìíîãèì ðåàëüíûì ïðîöåññàì. Òàê, ðàáîòà àâòîìàòè-
÷åñêèõ óñòðîéñòâ ñîïðîâîæäàåòñÿ íåïðåäâèäåííûìè ñëó÷àéíûìè ïðåïÿòñòâèÿ-
ìè, ñòàòèñòè÷åñêèå çàêîíîìåðíîñòè êîòîðûõ íå âñåãäà ìîãóò áûòü îïðåäåëåíû è
ó÷òåíû ïðè âû÷èñëåíèè óïðàâëÿþùèõ âîçäåéñòâèé.
Åñëè ìóëüòèìíîæåñòâî G g g g( ) ( ), ( ), . . . , ( )� � � ��� { }1 2 ñîäåðæèò ýëåìåíòû,
ÿâëÿþùèåñÿ ñëó÷àéíûìè ÷èñëàìè è çàâèñÿùèå îò íåêîòîðîãî ñîñòîÿíèÿ ñðåäû �, òî
G ( )� áóäåì íàçûâàòü ñòîõàñòè÷åñêèì ìóëüòèìíîæåñòâîì, à ñîîòâåòñòâóþùèå åâêëè-
äîâû êîìáèíàòîðíûå ìíîæåñòâà — ñòîõàñòè÷åñêèìè åâêëèäîâûìè êîìáèíàòîðíûìè
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 5 37
ìíîæåñòâàìè (íàïðèìåð, îáùåå
ìíîæåñòâî ïåðåñòàíîâîê
E Gkn ( ( ))� íàçîâåì ñòîõàñòè÷åñêèì
îáùèì ìíîæåñòâîì ïåðåñòàíîâîê).
Èñïîëüçîâàíèå ìåòîäîâ ðå-
øåíèÿ ïîñòàâëåííîé çàäà÷è óïà-
êîâêè â óñëîâèÿõ ñòîõàñòè÷åñêîé
íåîïðåäåëåííîñòè ïðåäïîëàãàåò
çíàíèå ðåçóëüòàòîâ îïåðàöèé íà-
õîæäåíèÿ ñóììû, ìèíèìóìà è
ìàêñèìóìà ñòîõàñòè÷åñêèõ âåëè-
÷èí. Åñëè èçâåñòíû âåðîÿòíîñòè
òîãî, ÷òî ñëó÷àéíûå âåëè÷èíû gi
— ýëåìåíòû ñòîõàñòè÷åñêîãî
ìóëüòèìíîæåñòâà — ïðèìóò çíà÷åíèÿ, ìåíüøèå, ÷åì òåêóùèé àðãóìåíò x R� 1
(ò.å. èçâåñòíî P g x F xi gi
( ) ( )� � ), òî áóäåì ñ÷èòàòü, ÷òî èçâåñòíî ðàñïðåäåëåíèå
(ôóíêöèÿ ðàñïðåäåëåíèÿ F xgi
( )) ñëó÷àéíûõ çíà÷åíèé gi .
Íà ïðàêòèêå íàèáîëåå ÷àñòî âñòðå÷àåòñÿ íîðìàëüíûé çàêîí ðàñïðåäåëåíèÿ. Äî-
êàçàíî (íàïðèìåð, [31]), ÷òî ñóììà äîñòàòî÷íî áîëüøîãî ÷èñëà íåçàâèñèìûõ (èëè
ñëàáî çàâèñèìûõ) ñëó÷àéíûõ âåëè÷èí, ïîä÷èíåííûõ êàêèì-ëèáî çàêîíàì ðàñïðåäå-
ëåíèÿ, ïðèáëèæåííî ïîä÷èíÿåòñÿ íîðìàëüíîìó çàêîíó. Òàêîé çàêîí ðàñïðåäåëåíèÿ
ñëó÷àéíûõ âåëè÷èí õàðàêòåðèçóåòñÿ äâóìÿ ïàðàìåòðàìè: ìàòåìàòè÷åñêèì îæèäàíè-
åì m è ñðåäíåêâàäðàòè÷åñêèì îòêëîíåíèåì �.
Òàêèì îáðàçîì, â ñëó÷àå íîðìàëüíîãî ðàñïðåäåëåíèÿ ñëó÷àéíûõ âåëè÷èí
gi ( )� ýëåìåíòû ñòîõàñòè÷åñêîãî ìóëüòèìíîæåñòâà áóäåì ïðåäñòàâëÿòü â âèäå
óïîðÿäî÷åííîé ïàðû g mi i i( ) ( , )� �� , i J� � , ãäå mi i, � — ïàðàìåòðû íîðìàëü-
íîãî ðàñïðåäåëåíèÿ ñëó÷àéíîé âåëè÷èíû — çíà÷åíèÿ ýëåìåíòà
ìóëüòèìíîæåñòâà gi .
Áóäåì ñ÷èòàòü, ÷òî â ñëó÷àå ñòîõàñòè÷åñêîé íåîïðåäåëåííîñòè äëèíû ïðÿìîó-
ãîëüíèêîâ a mi i i� ( , )� , i J p� , ÿâëÿþòñÿ íåçàâèñèìûìè íîðìàëüíî ðàñïðåäåëåí-
íûìè ñëó÷àéíûìè âåëè÷èíàìè. Èçâåñòíî [31], ÷òî ñóììà k íîðìàëüíî ðàñïðåäå-
ëåííûõ âåëè÷èí ( , )mi i� ÿâëÿåòñÿ íîðìàëüíî ðàñïðåäåëåííîé ñëó÷àéíîé âåëè÷è-
íîé ñ ïàðàìåòðàìè ( , )M � , ãäå M m m mk� 1 2 . . . ,� � � � �
1
2
2
2 2. . .
k
.
Ââåäåì îïðåäåëåíèå ìàêñèìóìà è ìèíèìóìà äâóõ íîðìàëüíî ðàñïðåäåëåí-
íûõ ñëó÷àéíûõ ÷èñåë: a m1 1 1� ( , )� è a m2 2 2� ( , )� .
Îïðåäåëåíèå 1. Åñëè âûïîëíÿåòñÿ îäíî èç âçàèìîèñêëþ÷àþùèõ óñëîâèé:
m m1 2� èëè � �1 2� ïðè m m1 2� , òî ÷èñëî a1 áóäåì ñ÷èòàòü ìàêñèìóìîì, à a2
— ìèíèìóìîì.
Ïðè ñðàâíåíèè ñëó÷àéíûõ âåëè÷èí íåîáõîäèìî òàêæå îïðåäåëåíèå ðàâå-
íñòâà äâóõ íîðìàëüíî ðàñïðåäåëåííûõ ñëó÷àéíûõ ÷èñåë.
Îïðåäåëåíèå 2. Äâà íîðìàëüíî ðàñïðåäåëåííûõ ñëó÷àéíûõ ÷èñëà
a m1 1 1� ( , )� è a m2 2 2� ( , )� áóäåì ñ÷èòàòü ðàâíûìè, åñëè m m1 2� è � �1 2� .
Åñëè íå âûïîëíåíî õîòÿ áû îäíî èç äâóõ íàçâàííûõ óñëîâèé, òî ÷èñëà a1 è
a2 ìîæíî óïîðÿäî÷èòü, èñïîëüçóÿ îïðåäåëåíèå 1.
Âîçâðàòèìñÿ ê ïîñòðîåíèþ ìàòåìàòè÷åñêîé ìîäåëè çàäà÷è.  êàæäîé ïîëîñêå â
îïòèìàëüíîì ðåøåíèè î÷åâèäíî ìîæåò ñòîÿòü îò îäíîãî äî p m p m� � � � ( )1 1
ïðÿìîóãîëüíèêîâ, ãäå m — êîëè÷åñòâî ðàçäåëåííûõ ïîëîñîê, ò.å. öåëàÿ ÷àñòü îò äå-
ëåíèÿ øèðèíû ïîëîñû íà h. Îáîçíà÷èì n m p m� � ( )1 è ââåäåì â ðàññìîòðåíèå
n p� ïðÿìîóãîëüíèêîâ ñ øèðèíîé h è äëèíîé a0 , ãäå ñëó÷àéíîå ÷èñëî a0 — íîð-
ìàëüíî ðàñïðåäåëåííàÿ âåëè÷èíà ñ íóëåâûì ìàòåìàòè÷åñêèì îæèäàíèåì è áåñêî-
íå÷íî ìàëûì ñðåäíåêâàäðàòè÷åñêèì îòêëîíåíèåì. Ïðè ýòîì ïðåäåë ïðè m � 0 ïëîò-
íîñòè ïðè íîðìàëüíîì ðàñïðåäåëåíèè ñ òàêèìè ïàðàìåòðàìè â òî÷êå x � 0
îïðåäåëÿåòñÿ ôîðìóëîé
38 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 5
Ðèñ. 1. Ðàçìåùåíèå ïðÿìîóãîëüíèêîâ â çàäà÷å
óïàêîâêè
lim ( ) lim
( )
� �
�
�
� �
�
�
�
�
�
�
�
�
�
�
�
�
� �
0 0
21
2
2
2
f x e
x m
,
à ïðè ïðîèçâîëüíîì ôèêñèðîâàííîì çíà÷åíèè â òî÷êå x x� �0 0 êàê
lim ( ) lim
( )
� �
�
� � �
�
�
�
�
�
�
�
�
�
�
�
�
�
0 0
21
2
0
2
2
f x e
x m
.
Ýòî çíà÷èò, ÷òî ïðàêòè÷åñêè âñå âîçìîæíûå çíà÷åíèÿ ñëó÷àéíîé âåëè÷èíû a0
ñîñðåäîòî÷åíû â áåñêîíå÷íî ìàëîé îêðåñòíîñòè íóëÿ. Ââåäåííóþ òàêèì îáðà-
çîì âåëè÷èíó a0 íàçîâåì ñòîõàñòè÷åñêèì àíàëîãîì îáû÷íîãî íóëÿ. Òîãäà
ìîæíî ñ÷èòàòü, ÷òî â êàæäîé ïîëîñêå íàõîäèòñÿ ðîâíî p m� 1 ïðÿìîóãîëü-
íèêîâ. Îáîçíà÷èì xij äëèíó ïðÿìîóãîëüíèêà (ñëó÷àéíîå ÷èñëî), êîòîðûé íà-
õîäèòñÿ â i-é ïîëîñêå íà j-ì ìåñòå îò íà÷àëà ïîëîñêè, i Jm� , j J p m� � 1.
Òàêóþ âåëè÷èíó áóäåì íàçûâàòü ñòîõàñòè÷åñêîé äëèíîé ñîîòâåòñòâóþùåãî
ïðÿìîóãîëüíèêà. Ðàññìîòðèì âåêòîð âèäà
x x x x x xp m p m i� � � ( , , , , , , , ,, ,11 1 1 21 2 1 1� � � �
� � �, , , , , ), ,x x xi p m m m p m� � 1 1 1 .
Îáðàçóåì ìóëüòèìíîæåñòâî G a a a ap� { }1 0 0, . . . , , , . . . , , â êîòîðîì ýëåìåíò
a0 âñòðå÷àåòñÿ n p� ðàç. Òîãäà âåêòîð x ìîæíî ðàññìàòðèâàòü êàê ýëåìåíò ñòî-
õàñòè÷åñêîãî ìíîæåñòâà ïåðåñòàíîâîê E Gn ( ( ))� èç ýëåìåíòîâ ìóëüòèìíîæåñòâà
G ( )� . Ïðè ýòîì êàæäîé ïåðåñòàíîâêå x áóäåò ñîîòâåòñòâîâàòü îïðåäåëåííîå ðàç-
ìåùåíèå ïðÿìîóãîëüíèêîâ â ïîëîñå è ñîîòâåòñòâåííî êàæäîìó ðàçìåùåíèþ
ïðÿìîóãîëüíèêîâ îòâå÷àåò ïåðåñòàíîâêà x.
Èñïîëüçóÿ ââåäåííûå îïåðàöèè ñóììû, íàõîæäåíèÿ ìàêñèìóìà è ìèíèìóìà
ñëó÷àéíûõ âåëè÷èí, ìîæíî ïðåäñòàâèòü ìàòåìàòè÷åñêóþ ìîäåëü ñôîðìóëèðî-
âàííîé çàäà÷è óïàêîâêè ïðÿìîóãîëüíèêîâ â óñëîâèÿõ ñòîõàñòè÷åñêîé
íåîïðåäåëåííîñòè â òàêîì âèäå:
íàéòè
F x x
x E G i m j
p m
ij
n
* *
( ( ))
( ) min max�
� � � �
�
�
� 1 1
1
; (9)
x x
x E G i m j
p m
ij
n
*
( ( ))
min max�
� � � �
�
�arg
� 1 1
1
, (10)
ãäå arg F x( ) îáîçíà÷àåò òî÷êó x, êîòîðàÿ äîñòàâëÿåò ñîîòâåòñòâóþùåå çíà÷å-
íèå F ôóíêöèè F x( ).
Ïîñòàâëåííóþ çàäà÷ó ìîæíî ðåøèòü ñ ïîìîùüþ ìåòîäà âåòâåé è ãðàíèö
[46].  åãî îñíîâå ëåæèò ñèñòåìà âåòâëåíèé è îòñå÷åíèé, èäåÿ êîòîðîé äëÿ çàäà-
÷è (9), (10) ñîñòîèò â ñëåäóþùåì.
Èñïîëüçóÿ ââåäåííîå âûøå îïðåäåëåíèå ìàêñèìóìà â óñëîâèÿõ ñòîõàñòè÷åñ-
êîé íåîïðåäåëåííîñòè, óïîðÿäî÷èì ñòîõàñòè÷åñêèå äëèíû ïðÿìîóãîëüíèêîâ ïî
óáûâàíèþ a a a p1 2� � �. . . . Óïîðÿäî÷èâàíèå ñëó÷àéíûõ ÷èñåë áóäåì ïðîâî-
äèòü ñîãëàñíî ïðàâèëó: a ai j� , åñëè max ;{ }a a ai j i� .
Ðàçìåùàåì ïðÿìîóãîëüíèê äëèíû a1 â ïåðâóþ ïîëîñó. Íà÷èíàÿ ñî âòîðîãî
ïðÿìîóãîëüíèêà, ïîñëåäîâàòåëüíî ðàçìåùàåì êàæäûé èç ïðÿìîóãîëüíèêîâ äëè-
íû ai â êàæäóþ èç ïîëîñ. Òàêèì îáðàçîì, ôîðìèðóþòñÿ âåòâè àëãîðèòìà. Ïîä
äëèíîé çàíÿòîé ÷àñòè ïîëîñû áóäåì ïîíèìàòü ñëó÷àéíîå ÷èñëî, ÿâëÿþùååñÿ
ñóììîé ñòîõàñòè÷åñêèõ äëèí ïðÿìîóãîëüíèêîâ [31], ðàçìåùåííûõ â äàííîé ïî-
ëîñå. Îöåíêîé
( )Qi
j óçëà Qi
j äåðåâà ðåøåíèé ( j — íîìåð óðîâíÿ âåòâëåíèÿ, i —
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 5 39
ïîðÿäêîâûé íîìåð óçëà íà òåêóùåì óðîâíå) äàííîãî àëãîðèòìà ÿâëÿåòñÿ äëèíà
çàíÿòîé ÷àñòè ïîëîñû. Íà êàæäîì ýòàïå ðàçâåòâëÿåòñÿ óçåë ñ ïîðÿäêîâûì íîìå-
ðîì s, èìåþùèé íàèìåíüøóþ îöåíêó íà òåêóùåì óðîâíå, ò.å. äëÿ ýòîãî óçëà
( ) min ( )Q Qs
j
i
i
j� .
Ïðîöåññ âåòâëåíèÿ çàêàí÷èâàåòñÿ ïîñëå ðàçìåùåíèÿ ïîñëåäíåãî ïðÿìîó-
ãîëüíèêà äëèíîé a p â êàæäóþ èç ïîëîñ è ïîñëå îöåíêè ñîîòâåòñòâóþùèõ
äîïóñòèìûõ ðåøåíèé.
Ôðàãìåíò äåðåâà âåòâëåíèé èçîáðàæåí íà ðèñ. 2.
3. Îöåíêà ñëîæíîñòè àëãîðèòìà äëÿ çàäà÷è åâêëèäîâîé êîìáèíàòîðíîé
îïòèìèçàöèè â óñëîâèÿõ ñòîõàñòè÷åñêîé íåîïðåäåëåííîñòè.Ïîäñ÷èòàåì êî-
ëè÷åñòâî àðèôìåòè÷åñêèõ îïåðàöèé è îïåðàöèé ñðàâíåíèÿ, êîòîðûå íóæíî âû-
ïîëíèòü äëÿ íàõîæäåíèÿ ìàêñèìóìà äâóõ ñëó÷àéíûõ âåëè÷èí, ïîä÷èíåííûõ
íîðìàëüíîìó çàêîíó ðàñïðåäåëåíèÿ. Ïóñòü a m1 1 1� ( , )� , a m2 2 2� ( , )� .
Âíà÷àëå íåîáõîäèìî âûïîëíèòü îäíó îïåðàöèþ ñðàâíåíèÿ ìàòåìàòè÷åñêèõ
îæèäàíèé m1 è m2 , à â ñëó÷àå m m1 2� âûïîëíèòü ñðàâíåíèå ñðåäíåêâàäðàòè÷åñêèõ
îòêëîíåíèé �1 è � 2 . Äëÿ íàõîæäåíèÿ ìàêñèìóìà èç s ñëó÷àéíûõ íîðìàëüíî ðàñïðå-
äåëåííûõ âåëè÷èí äîñòàòî÷íî âûïîëíèòü íå áîëåå 2 1( )s � àðèôìåòè÷åñêèõ îïåðà-
öèé. Î÷åâèäíî, ÷òî äëÿ íàõîæäåíèÿ ìèíèìóìà êîëè÷åñòâî îïåðàöèé áóäåò òåì æå.
Äëÿ íàõîæäåíèÿ ïàðàìåòðîâ íîðìàëüíîãî ðàñïðåäåëåíèÿ äëÿ âåëè÷èíû, ÿâ-
ëÿþùåéñÿ ñóììîé s íîðìàëüíî ðàñïðåäåëåííûõ ñëó÷àéíûõ ÷èñåë, íåîáõîäèìî
âíà÷àëå âûïîëíèòü ( )s �1 îïåðàöèé ñëîæåíèÿ ìàòåìàòè÷åñêèõ îæèäàíèé äëÿ íà-
õîæäåíèÿ ñóììû
i
s
im
�
�
1
. Äëÿ îïðåäåëåíèÿ âåëè÷èíû
i
s
�
�
1
1
2� íåîáõîäèìî âû-
ïîëíèòü s âîçâåäåíèé â êâàäðàò (óìíîæåíèé íà ñåáÿ) ñðåäíåêâàäðàòè÷åñêèõ îò-
êëîíåíèé � i , ïîñëåäóþùèå ( )s �1 îïåðàöèé èõ ñëîæåíèÿ è îïåðàöèþ íàõîæäåíèÿ
êâàäðàòíîãî êîðíÿ èç ðåçóëüòàòà. Òàêèì îáðàçîì, äëÿ íàõîæäåíèÿ èñêîìîé ñóì-
ìû èç s íîðìàëüíî ðàñïðåäåëåííûõ ñëó÷àéíûõ ñëàãàåìûõ íåîáõîäèìî
âûïîëíèòü s s s s� � � �1 1 1 3 1 àðèôìåòè÷åñêèõ îïåðàöèé.
Ïðîâåäåì àíàëèç àëãîðèòìà ìåòîäà ïîëíîãî ïåðåáîðà äëÿ ðåøåíèÿ çàäà÷è
(9), (10). Åñòåñòâåííî, ÷òî îöåíêà ñëîæíîñòè ìåòîäà ïîëíîãî ïåðåáîðà äîïóñòè-
ìûõ ðåøåíèé äëÿ ñòîõàñòè÷åñêîé íåîïðåäåëåííîñòè íå ÿâëÿåòñÿ ïîëèíî-
ìèàëüíîé, ïîñêîëüêó ïåðåñòàíîâêè äàþò êàê ìèíèìóì ôàêòîðèàëüíóþ ñëîæ-
íîñòü àëãîðèòìà � ( !)n (â îáîçíà÷åíèÿõ [47]). Öåëåñîîáðàçíîñòü ïðîâåäåíèÿ òà-
êîãî àíàëèçà ñîñòîèò â íàõîæäåíèè âåðõíåé îöåíêè ñëîæíîñòè ðåøåíèÿ çàäà÷è
óïàêîâêè äëÿ ñòîõàñòè÷åñêîé íåîïðåäåëåííîñòè.
Åñëè äëèíû ïðÿìîóãîëüíèêîâ íîðìàëüíî ðàñïðåäåëåíû ñ ïàðàìåòðàìè
( , )mi i� � �i J p , òî ñ ó÷åòîì âûøåóñòàíîâëåííûõ 3 1s � îïåðàöèé äëÿ âû÷èñëå-
íèÿ ñóììû s ñëàãàåìûõ îáùåå êîëè÷åñòâî îïåðàöèé ñëîæåíèÿ, âûïîëíåííûõ äëÿ
âû÷èñëåíèÿ äëèí çàíÿòûõ ÷àñòåé ïîëîñ, ñîñòàâëÿåò 3 1n � � � � �3 1 1m p m( )
îïåðàöèé. Ïðè îïðåäåëåíèè ìàêñèìàëüíîãî çíà÷åíèÿ öåëåâîé ôóíêöèè äëÿ êàæ-
äîé ïåðåñòàíîâêè íåîáõîäèìî âûïîëíèòü 2 1( )m � îïåðàöèé ñðàâíåíèÿ. Íàêîíåö,
äëÿ íàõîæäåíèÿ îïòèìàëüíîãî ðåøåíèÿ íóæíî ñðàâíèòü n m p m! ( ( )) !� � 1 çíà-
÷åíèé, ïîëó÷åííûõ äëÿ êàæäîãî äîïóñòèìîãî âàðèàíòà ðàçìåùåíèÿ ïðÿìîóãîëü-
íèêîâ ïî ïîëîñàì. Êîëè÷åñòâî îïåðàöèé äëÿ òàêèõ ñðàâíåíèé ðàâíî
2 1 1� � �[( ( )) ! ]m p m . Ñëåäîâàòåëüíî, äëÿ âû÷èñëåíèÿ îáùåãî êîëè÷åñòâà îïåðà-
öèé (àðèôìåòè÷åñêèõ îïåðàöèé ñëîæåíèÿ è ñðàâíåíèÿ), êîòîðûå íåîáõîäèìî
îñóùåñòâèòü äëÿ íàõîæäåíèÿ îïòèìàëüíîé óïàêîâêè â äàííîé çàäà÷å, íóæíî êî-
ëè÷åñòâî îïåðàöèé äëÿ ïîèñêà îäíîãî äîïóñòèìîãî ðåøåíèÿ (3 1 1m p m( )� �
îïåðàöèé ñëîæåíèÿ è 2 1( )m � îïåðàöèé ñðàâíåíèÿ) óìíîæèòü íà êîëè÷åñòâî îïå-
ðàöèé ñðàâíåíèÿ äîïóñòèìûõ ðåøåíèÿ ïðè ïîèñêå îïòèìàëüíîãî ðåøåíèÿ. Òà-
êèì îáðàçîì, îáùåå êîëè÷åñòâî îïåðàöèé íå ïðåâûøàåò
2 1 1 3 1 1 2 1� � � � � � �[( ( )) ! ] [ ( ) ( )]m p m m p m m , ÷òî ñîñòàâëÿåò âåëè÷èíó
�(( ) ! ( ) !)m p2 1 ñîãëàñíî òåðìèíîëîãèè [47].
40 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 5
4. Ó÷åò ðàçëè÷íûõ òèïîâ íåîïðåäåëåííîñòè â çàäà÷àõ åâêëèäîâîé êîì-
áèíàòîðíîé îïòèìèçàöèè. Áîëüøîé èíòåðåñ ïðåäñòàâëÿþò èññëåäîâàíèÿ çàäà÷
åâêëèäîâîé êîìáèíàòîðíîé îïòèìèçàöèè, â êîòîðûõ èñõîäíûå äàííûå çàäà÷è
âêëþ÷àþò íåñêîëüêî òèïîâ íåîïðåäåëåííîñòè.  êà÷åñòâå ïðèìåðà ðàññìîòðèì
ôîðìèðîâàíèå îáùåãî ïîäõîäà ê ó÷åòó ñòîõàñòè÷åñêîé è íå÷åòêîé
íåîïðåäåëåííîñòè.
Îïðåäåëåíèå 3 [38]. Íå÷åòêèì ÷èñëîì G íàçîâåì íå÷åòêîå ìíîæåñòâî âèäà
~
( | ), . . . , ( | )G g g� { }1 1� �� � , ãäå { }g g g1 2, , . . . , � , g Ri � 1 � �i Jm , — íîñèòåëü íå-
÷åòêîãî ìíîæåñòâà, { }� � ��1 2, , . . . , , � i R� 1 � �i J� , — ìíîæåñòâî çíà÷åíèé
ôóíêöèè ïðèíàäëåæíîñòè, 0 1� �� i � �i J� .
 ñëó÷àå, êîãäà ýëåìåíòû ìóëüòèìíîæåñòâà ÿâëÿþòñÿ íå÷åòêî çàäàííûìè
÷èñëàìè, áóäåì ñ÷èòàòü åãî ìóëüòèìíîæåñòâîì íå÷åòêèõ ÷èñåë
~
( | ), . . . , ( | )G g g� { }1 1� �� � .
Ââåäåì â ðàññìîòðåíèå ìóëüòèìíîæåñòâî
~
( ) [ ( ), ],G g� � �� { 1 1
[ ( ), ], . . . , [ ( ), ]g g2 2� � � �� � }. Äëÿ íîðìàëüíîãî ðàñïðåäåëåíèÿ ñòîõàñòè÷åñêèõ
ýëåìåíòîâ gi ( )� èìååì
~
( ) [( , ), ], [( , ), ], . . . , [( , ), ]G m m m� � � � � � �� � �� { }1 1 1 2 2 2 .
Äåéñòâèòåëüíî, ïðè íå÷åòêîé íåîïðåäåëåííîñòè íîñèòåëü íå÷åòêîãî ìíî-
æåñòâà ÿâëÿåòñÿ îáû÷íûì ìíîæåñòâîì äåòåðìèíèðîâàííûõ ýëåìåíòîâ. Êàê è â
ñëó÷àå çàäàíèÿ ñòîõàñòè÷åñêîãî àíàëîãà îáû÷íîãî íóëÿ áóäåì ñ÷èòàòü, ÷òî äëÿ
äåòåðìèíèðîâàííîãî àíàëîãà gi ñòîõàñòè÷åñêîãî ýëåìåíòà ( , )mi i� åãî ìàòåìàòè-
÷åñêîå îæèäàíèå m gi i� , à ñðåäíåêâàäðàòè÷åñêîå îòêëîíåíèå ÿâëÿåòñÿ áåñêîíå÷-
íî ìàëîé âåëè÷èíîé. Ïðè ýòîì ïðåäåë ïëîòíîñòè íîðìàëüíîãî ðàñïðåäåëåíèÿ ñ
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 5 41
Ðèñ. 2. Äåðåâî âåòâëåíèé â ìåòîäå âåòâåé è ãðàíèö äëÿ çàäà÷è óïàêîâêè ïðÿìîóãîëüíèêîâ íà
ñòîõàñòè÷åñêèõ ïåðåñòàíîâêàõ (aiû — ñèìâîëè÷åñêîå èçîáðàæåíèå ñòîõàñòè÷åñêîé äëèíû
ïðÿìîóãîëüíèêîâ)
òàêèìè ïàðàìåòðàìè ïðè x m� èìååò âèä
lim ( ) lim
( )
� �
�
� � �
�
�
�
�
�
�
�
�
�
�
�
�
�
� �
0 0
21
2
2
2
f x e
x m
,
à ïðè ïðîèçâîëüíîì ôèêñèðîâàííîì çíà÷åíèè x x m� �0 îïðåäåëèòñÿ
ôîðìóëîé
lim ( ) lim
( )
� �
�
� � �
�
�
�
�
�
�
�
�
�
�
�
�
�
�
0 0
21
2
0
2
2
f x e
x m
.
Òàêèì îáðàçîì, ýëåìåíò ìóëüòèìíîæåñòâà gi ìîæíî ñ÷èòàòü äåòåðìèíèðî-
âàííûì àíàëîãîì ñòîõàñòè÷åñêîãî ýëåìåíòà ( , )gi i� ñ áåñêîíå÷íî ìàëûì ñðåä-
íåêâàäðàòè÷åñêèì îòêëîíåíèåì.
Äëÿ ñòîõàñòè÷åñêîé íåîïðåäåëåííîñòè ñòåïåíü ïðèíàäëåæíîñòè ýëåìåíòà
ìóëüòèìíîæåñòâó íå÷åòêèõ ÷èñåë � i �1 � �i Jn îïðåäåëèòñÿ âûðàæåíèåì
[( , ) | ] [( , ) | ] ( , )m m mi i i i i i i� � � �� �1 ,
ò.å. èìååì ýëåìåíò ìóëüòèìíîæåñòâà ñòîõàñòè÷åñêèõ ýëåìåíòîâ.  ýòîì ñëó÷àå
ìíîæåñòâî ïåðåñòàíîâîê, êîòîðîå îáúåäèíÿåò â ñåáå ñâîéñòâà íå÷åòêîãî è ñòî-
õàñòè÷åñêîãî ìíîæåñòâ ïåðåñòàíîâîê, íàçîâåì îáùèì åâêëèäîâûì êîìáèíà-
òîðíûì ìíîæåñòâîì ïåðåñòàíîâîê íå÷åòêèõ ñòîõàñòè÷åñêèõ ÷èñåë è
îáîçíà÷èì åãî E Gk (
~
( ))� .
ÂÛÂÎÄÛ ÈÇ ÄÀÍÍÎÃÎ ÈÑÑËÅÄÎÂÀÍÈß
È ÏÅÐÑÏÅÊÒÈÂÛ ÄÀËÜÍÅÉØÈÕ ÈÑÑËÅÄÎÂÀÍÈÉ
 íàñòîÿùåé ñòàòüå âïåðâûå ïîñòàâëåíà îáùàÿ çàäà÷à åâêëèäîâîé êîìáèíàòîðíîé
îïòèìèçàöèè â óñëîâèÿõ íåîïðåäåëåííîñòè. Ââåäåíû ïîíÿòèÿ ñòîõàñòè÷åñêîãî
ìóëüòèìíîæåñòâà è ìóëüòèìíîæåñòâà íå÷åòêèõ ÷èñåë, ñòîõàñòè÷åñêîãî åâêëèäîâîãî
êîìáèíàòîðíîãî ìíîæåñòâà, à òàêæå îáùåãî åâêëèäîâîãî êîìáèíàòîðíîãî ìíîæåñ-
òâà íå÷åòêèõ ñòîõàñòè÷åñêèõ ÷èñåë, îáúåäèíÿþùåãî â ñåáå ñâîéñòâà îáîèõ âèäîâ
íåîïðåäåëåííîñòè. Ðàññìîòðåíà ïîñòàíîâêà è îáîñíîâàí àëãîðèòì ðåøåíèÿ çàäà÷è
óïàêîâêè ïðÿìîóãîëüíèêîâ â óñëîâèÿõ ñòîõàñòè÷åñêîé íåîïðåäåëåííîñòè. Ïðîâåäåí
àíàëèç ñëîæíîñòè è äàíà âåðõíÿÿ îöåíêà ñëîæíîñòè àëãîðèòìà ðåøåíèÿ çàäà÷è
óïàêîâêè â óñëîâèÿõ ñòîõàñòè÷åñêîé íåîïðåäåëåííîñòè.
Çàäà÷è åâêëèäîâîé êîìáèíàòîðíîé îïòèìèçàöèè â óñëîâèÿõ ñòîõàñòè÷åñêîé
íåîïðåäåëåííîñòè ìåíåå èçó÷åíû, ÷åì, íàïðèìåð, çàäà÷è ñ ïàðàìåòðè÷åñêîé èëè
èíòåðâàëüíîé íåîïðåäåëåííîñòüþ. Íàëè÷èå ñðåäè èñõîäíûõ äàííûõ ðåàëüíûõ çà-
äà÷ íåäåòåðìèíèðîâàííûõ âåëè÷èí, êîòîðûå ìîãóò áûòü îõàðàêòåðèçîâàíû
ñëó÷àéíûìè ÷èñëàìè ñ èçâåñòíûì çàêîíîì ðàñïðåäåëåíèÿ, ïîäòâåðæäàåò àêòóàëüíîñòü
äàëüíåéøåãî èññëåäîâàíèÿ êîìáèíàòîðíûõ çàäà÷ â óñëîâèÿõ íåîïðåäåëåííîñòè.
Ìåòîäàìè ñòîõàñòè÷åñêîé åâêëèäîâîé êîìáèíàòîðíîé îïòèìèçàöèè ìîæíî
ýôôåêòèâíî ðåøàòü ýêîíîìè÷åñêèå çàäà÷è, â êîòîðûõ èñõîäíûå äàííûå, íåîáõî-
äèìûå äëÿ èõ ðåøåíèÿ (ñòîèìîñòü ïðîèçâîäñòâà åäèíèöû ïðîäóêöèè, êîëè÷åñòâî
çàïàñîâ ñûðüÿ, ýíåðãèè, âåëè÷èíà êàïèòàëîâëîæåíèé), èçìåíÿþòñÿ âî âðåìåíè ïî
èçâåñòíîìó çàêîíó ðàñïðåäåëåíèÿ ñëó÷àéíûõ âåëè÷èí.
Èññëåäîâàííûå â íàñòîÿùåé ñòàòüå ìåòîäû è èõ îöåíêè ìîãóò áûòü èñïîëüçîâà-
íû äëÿ ïîñòðîåíèÿ è àíàëèçà àëãîðèòìîâ ðåøåíèÿ çàäà÷ â óñëîâèÿõ íåîïðåäåëåííîñòè
íà äðóãèõ åâêëèäîâûõ êîìáèíàòîðíûõ ìíîæåñòâàõ. Ïåðñïåêòèâíûì ïðåäñòàâëÿåòñÿ
èññëåäîâàíèå ñâîéñòâ åâêëèäîâûõ êîìáèíàòîðíûõ çàäà÷ îïòèìèçàöèè â óñëîâèÿõ íå-
îïðåäåëåííîñòè ðàçëè÷íûõ òèïîâ, à òàêæå ñâîéñòâ òàêèõ çàäà÷, îñíîâàííûõ íà îäíî-
âðåìåííîì ó÷åòå íåñêîëüêèõ òèïîâ íåîïðåäåëåííîñòè.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. Ñ å ð ã è å í ê î È .  . , Ø è ë î  . Ï . Çàäà÷è äèñêðåòíîé îïòèìèçàöèè: ïðîáëåìû, ìåòîäû
èññëåäîâàíèÿ, ðåøåíèÿ. — Ê.: Íàóê. äóìêà, 2003. — 263 ñ.
42 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 5
2. Ñ å ð ã è å í ê î È .  . Ìàòåìàòè÷åñêèå ìîäåëè è ìåòîäû ðåøåíèÿ çàäà÷ äèñêðåòíîé îïòèìè-
çàöèè. — Ê.: Íàóê. äóìêà, 1988. — 471 ñ.
3. Ñ å ð ã è å í ê î È .  . , Ï à ð à ñ þ ê È . Í . , Ê à ñ ï ø è ö ê à ÿ Ì . Ô . Îá îäíîé íå÷åòêîé
çàäà÷å ìíîãîïàðàìåòðè÷åñêîãî âûáîðà îïòèìàëüíûõ ðåøåíèé // Êèáåðíåòèêà è ñèñòåìíûé
àíàëèç. — 2003. — ¹ 2. — Ñ. 3–15.
4. Ñ å ð ã è å í ê î È . Â . , Ë å á å ä å â à Ò . Ò . , Ñ å ì å í î â à Í . Â . Î ñóùåñòâîâàíèè ðåøå-
íèé â çàäà÷àõ âåêòîðíîé îïòèìèçàöèè // Òàì æå. — 2000. — ¹ 6. — Ñ. 39–46.
5. Ñ å ð ã è å í ê î È . Â . , Ê î ç å ð à ö ê à ÿ Ë . Í . , Ë å á å ä å â à Ò . Ò . Èññëåäîâàíèå óñòîé-
÷èâîñòè è ïàðàìåòðè÷åñêèé àíàëèç äèñêðåòíûõ îïòèìèçàöèîííûõ çàäà÷. — Ê.: Íàóê. äóìêà,
1995. — 170 ñ.
6. Å ì å ë è ÷ å â Â . À . , Ê î â à ë å â Ì . Ì . , Ê ð à â ö î â Ì . Ê . Ìíîãîãðàííèêè, ãðàôû,
îïòèìèçàöèÿ. — Ì.: Íàóêà, 1981. — 342 ñ.
7. Å ì å ë è ÷ å â Â . À . , Ê î ì ë è ê Â . È . Ìåòîä ïîñòðîåíèÿ ïîñëåäîâàòåëüíîñòè ïëàíîâ äëÿ
ðåøåíèÿ çàäà÷ äèñêðåòíîé îïòèìèçàöèè. — Ì.: Íàóêà, 1981. — 208 ñ.
8. Ï à í è ø å â À . Â . , Ï ë å ÷ è ñ ò û é Ä . Ä . Ìîäåëè è ìåòîäû îïòèìèçàöèè â ïðîáëåìå êî-
ìèâîÿæåðà. — Æèòîìèð: ÆÃÒÓ, 2006. — 300 ñ.
9. Ï à í i ø å â À .  . , Ä à í è ë ü ÷ å í ê î Î . Ì . , Ñ ê à ÷ ê î â  . Î . Âñòóï äî òåîði ñêëàä-
íîñòi äèñêðåòíèõ çàäà÷. — Æèòîìèð: ÆÄÒÓ, 2004. — 326 ñ.
10. C ò î ÿ í Þ . à . , ª ì å ö ü Î . Î . Òåîðiÿ i ìåòîäè åâêëiäîâî êîìáiíàòîðíî îïòèìiçàöiÂ.
— Ê.: Iíñòèòóò ñèñòåìíèõ äîñëiäæåíü îñâiòè, 1993. — 188 ñ.
11. Ñ ò î ÿ í Þ . Ã . , ª ì å ö ü Î . Î . , ª ì å ö ü ª . Ì . Îïòèìiçàöiÿ íà ïîëiðîçìiùåííÿõ: òåîðiÿ
òà ìåòîäè. — Ïîëòàâà: ÐÂÖ ÏÓÑÊÓ, 2005. — 103 ñ.
12. ª ì å ö ü Î . Î . , Ð î ñ ê ë à ä ê à Î .  . Çàäà÷i îïòèìiçàöi íà ïîëiêîìáiíàòîðíèõ ìíîæè-
íàõ: âëàñòèâîñòi òà ðîçâ’ÿçóâàííÿ. — Ïîëòàâà: ÐÂÖ ÏÓÑÊÓ, 2006. — 103 ñ.
13. Å ì å ö Î . À . , Ê î ë å ÷ ê è í à Ë . Í . Çàäà÷è êîìáèíàòîðíîé îïòèìèçàöèè ñ äðîáíî-ëè-
íåéíûìè öåëåâûìè ôóíêöèÿìè. — Ê.: Íàóê. äóìêà, 2005. — 117 ñ.
14. Ñ ò î ÿ í Þ . Ã . , ß ê î â ë å â Ñ . Â . , ª ì å ö ü Î . Î . , Â à ë ó é ñ ü ê à Î . Î . Ïðî Ÿñíó-
âàííÿ îïóêëîãî ïðîäîâæåííÿ ôóíêöié, ÿêi çàäàíi íà ãiïåðñôåði // Äîï. ÍÀÍ ÓêðàÂíè. — 1998.
— ¹ 2. — Ñ. 128–133.
15. Ñ ò î ÿ í Þ . Ã . , ª ì å ö ü Î . Î . , ª ì å ö ü ª . Ì . Ìíîæèíè ïîëiðîçìiùåíü â êîìáiíà-
òîðíié îïòèìiçàöi // Äîï. ÍÀÍ ÓêðàÂíè. — 1999. — ¹ 8. — Ñ. 37–41.
16. ß ê î â ë å â Ñ . Â . , Â à ë ó é ñ ê à ÿ Î . À . Î ìèíèìèçàöèè ëèíåéíîé ôóíêöèè íà âåðøèíàõ
ïåðåñòàíîâî÷íîãî ìíîãîãðàííèêà ñ ó÷åòîì ëèíåéíûõ îãðàíè÷åíèé // Òàì æå. — 1999. — ¹ 4.
— Ñ. 103–108.
17. ª ì å ö ü Î . Î . , ª ì å ö ü ª . Ì . Âiäñiêàííÿ â ëiíiéíèõ ÷àñòêîâî êîìáiíàòîðíèõ çàäà÷àõ
åâêëiäîâî êîìáiíàòîðíî îïòèìiçàöi // Òàì æå. — 2000. — ¹ 9. — Ñ. 105–109.
18. ª ì å ö ü Î . Î . , Á à ð á î ë i í à Ò . Ì . , × å ð í å í ê î Î . Î . Ðîçâ’ÿçóâàííÿ óìîâíèõ çàäà÷ ç
äðîáîâî-ëiíiéíîþ ôóíêöiºþ öiëi íà ìíîæèíi ðîçìiùåíü // Òàì æå. — 2006. — ¹ 11. — Ñ. 15–18.
19. ª ì å ö ü Î . Î . Òåîðiÿ i ìåòîäè êîìáiíàòîðíî îïòèìiçàöi íà åâêëiäîâèõ ìíîæèíàõ â ãåî-
ìåòðè÷íîìó ïðîåêòóâàííi: Àâòîðåô. äèñ. ... ä-ðà ôiç.-ìàò. íàóê: 01.05.01 / Ií-ò êiáåðíåòèêè
ÍÀÍ ÓêðàÂíè. — Ê., 1997. — 42 ñ.
20. Ð î ñ ê ë à ä ê à À . À . Ïàðàìåòðè÷íi çàäà÷i òà ñòiéêiñòü ïðè ìîäåëþâàííi åâêëiäîâèìè êî-
ìáiíàòîðíèìè çàäà÷àìè îïòèìiçàöi: Àâòîðåô. äèñ. ... êàíä. ôiç.-ìàò. íàóê: 01.05.01 / Äíiïðî-
ïåòðîâ. íàö. óí-ò. — Äíiïðîïåòðîâñüê, 2000. — 18 ñ.
21. Å ì å ö Î . À . , Á à ð á î ë è í à Ò . Ì . , × å ð í å í ê î Î . À . Ðåøåíèå çàäà÷ îïòèìèçàöèè
ñ äðîáíî-ëèíåéíûìè öåëåâûìè ôóíêöèÿìè è äîïîëíèòåëüíûìè îãðàíè÷åíèÿìè íà ðàçìåùå-
íèÿõ // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 2006. — ¹ 5. — Ñ. 79–85.
22. ª ì å ö ü Î . Î . , Ð î ñ ê ë à ä ê à À . À . , ª ì å ö ü Î ë - ð à Î . Çàäà÷à åâêëiäîâî êî-
ìáiíàòîðíî¿ îïòèìiçàöi¿ â óìîâàõ íåâèçíà÷åíîñòi // Çá. íàóê. ïðàöü Õìåëüíèöüêîãî íàö. óí-òó.
Ñåð.: Ôiç.-ìàò. íàóêè. — 2005. — Âèï. 1. — Ñ. 40–45.
23. ª ì å ö ü Î . Î . , Ê î ë º ÷ ê i í à Ë . Ì . , Í å ä î á à ÷ i é Ñ . I . Äîñëiäæåííÿ îáëàñòåé âèç-
íà÷åííÿ çàäà÷ åâêëiäîâî êîìáiíàòîðíî îïòèìiçàöi íà ïåðåñòàâíèõ ìíîæèíàõ. ×. 1. —
Ïîëòàâà: ×ÏÊÏ «Ëåãàò», 1999. — 64 ñ.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 5 43
24. ª ì å ö ü Î . Î . , Ê î ë º ÷ ê i í à Ë . Ì . , Í å ä î á à ÷ i é Ñ . I . Äîñëiäæåííÿ îáëàñòåé
âèçíà÷åííÿ çàäà÷ åâêëiäîâî êîìáiíàòîðíî îïòèìiçàöi íà ïåðåñòàâíèõ ìíîæèíàõ. ×. 2. —
Ïîëòàâà: ×ÏÊÏ «Ëåãàò», 1999. — 32 ñ.
25. Å ì å ö Î . À . Êîìáèíàòîðíàÿ ìîäåëü è ïðèáëèæåííûé ìåòîä ñ àïðèîðíîé îöåíêîé ðåøåíèÿ
îïòèìèçàöèîííîé çàäà÷è ðàçìåùåíèÿ ðàçíîöâåòíûõ ïðÿìîóãîëüíèêîâ // Ýêîíîìèêà è ìàò. ìå-
òîäû. — 1993. — 29, âûï. 2. — Ñ. 294–304.
26. Å ì å ö Î . À . Åâêëèäîâû êîìáèíàòîðíûå ìíîæåñòâà è îïòèìèçàöèÿ íà íèõ. Íîâîå â ìàòåìà-
òè÷åñêîì ïðîãðàììèðîâàíèè: Ó÷åá. ïîñîáèå. — Ê.: ÓÌÊ ÂÎ. — 1992. — 92 ñ.
27. R o s k l a d k a A . Stochastic settings of the problems of Euclidean combinatorial optimization //
Theory of stochastic processes. — 2003. — 9(25), N 3–4. — P. 170–175.
28. ª ì å ö ü Î ë - ð à Î . Îäíà çàäà÷à êîìáiíàòîðíî îïòèìiçàöi íà ïåðåñòàâëåííÿõ íå÷iòêèõ
ìíîæèí // Âîëèíñ. ìàò. âiñíèê: Ñåð. Ïðèêëàäíà ìàòåìàòèêà. — 2004. — Âèï. 2(11). — Ñ. 101–106.
29. à ð å á å í í i ê I .  . Ìàòåìàòè÷íi ìîäåëi òà ìåòîäè êîìáiíàòîðíî îïòèìiçàöi â ãåîìåò-
ðè÷íîìó ïðîåêòóâàííi. Àâòîðåô. äèñ. ... ä-ðà òåõí. íàóê: 01.05.02 / Iíñòèòóò ïðîáëåì ìàøèíî-
áóäóâàííÿ iì. À.Ì. Ïiäãîðíîãî. — Õàðêiâ, 2006. — 34 ñ.
30. Ñ ò î ÿ í Þ . Ã . Ðàñøèðåííîå ïðîñòðàíñòâî IS(R) öåíòðèðîâàííûõ èíòåðâàëîâ. — Õàðüêîâ,
1994. — 27 ñ. (Ïðåïð. / ÍÀÍÓ. IÏMaø; 378).
31. Â å í ò ö å ë ü Å . Ñ . Òåîðèÿ âåðîÿòíîñòåé. — Ì.: Íàóêà, 1969. — 576 ñ.
32. Å ð ì î ë ü å â Þ . Ì . Ìåòîäû ñòîõàñòè÷åñêîãî ïðîãðàììèðîâàíèÿ. — Ì.: Íàóêà, 1976. —
240 ñ.
33. Þ ä è í Ä . Á . Çàäà÷è è ìåòîäû ñòîõàñòè÷åñêîãî ïðîãðàììèðîâàíèÿ. — Ì.: Ñîâ. ðàäèî, 1979.
— 392 ñ.
34. Ì à ê ñ è ø ê î Í . Ê . , Ï å ð å ï å ë è ö à Â . À . Àíàëèç è ïðîãíîçèðîâàíèå ýâîëþöèè ýêîíî-
ìè÷åñêèõ ñèñòåì: — Çàïîðîæüå: Ïîëèãðàô, 2006. — 236 ñ.
35. À ë å ô å ë ü ä à . , Õ å ð ö á å ð ã å ð Þ . Ââåäåíèå â èíòåðâàëüíûå âû÷èñëåíèÿ. — Ì.: Ìèð,
1987. — 360 ñ.
36. Ê à ë ì û ê î â Ñ . À . , Ø î ê è í Þ . È . , Þ ë ä à ø å â Ç . Õ . Ìåòîäû èíòåðâàëüíîãî àíà-
ëèçà. — Íîâîñèáèðñê: Íàóêà, 1986. — 222 ñ.
37. Ï î ë ÿ ê Á . Ò . , Í à ç è í Ñ . À . Îöåíèâàíèå ïàðàìåòðîâ â ëèíåéíûõ ìíîãîìåðíûõ ñèñòå-
ìàõ ñ èíòåðâàëüíîé íåîïðåäåëåííîñòüþ // Ïðîáëåìû óïðàâëåíèÿ è èíôîðìàòèêè. — 2006. —
¹ 1. — Ñ. 103–115.
38. Ê î ô ì à í À . Ââåäåíèå â òåîðèþ íå÷åòêèõ ìíîæåñòâ. — Ì.: Ðàäèî è ñâÿçü, 1982. — 432 ñ.
39. À ë ò ó í è í À . Å . , Ñ å ì ó õ è í Ì .  . Ìîäåëè è àëãîðèòìû ïðèíÿòèÿ ðåøåíèé â íå÷åò-
êèõ óñëîâèÿõ. — Òþìåíü: Èçä-âî ÒþìÃÓ, 2000. — 352 ñ.
40. Ì à ø ó í è í Þ . Ê . Òåîðåòè÷åñêèå îñíîâû è ìåòîäû âåêòîðíîé îïòèìèçàöèè â óïðàâëåíèè
ýêîíîìè÷åñêèìè ñèñòåìàìè. — Ì.: Ëîãîñ, 2001. — 247 ñ.
41. Â à ñ è ë ü å â Ñ . Í . , Ê î ò ë î â Þ . Â . Ìåòîäû è àëãîðèòìû ìíîãîêðèòåðèàëüíîé îïòèìè-
çàöèè íà îñíîâå íåñòðîãèõ ðàíæèðîâîê àëüòåðíàòèâ ïî ÷àñòíûì êðèòåðèÿì è îïûò êîìïüþòåðíîé
ðåàëèçàöèè // Ïðîáëåìû óïðàâëåíèÿ è èíôîðìàòèêè. — 2006. — ¹ 1. — Ñ. 28–38.
42. Ñ à ô ð î í î â Â . Â . , Â å ä å ð í è ê î â Þ . Â . , Ø à õ î â à Î . À . Âåêòîðíàÿ îïòèìèçà-
öèÿ ñëîæíûõ òåõíè÷åñêèõ ñèñòåì ïðè íåîïðåäåëåííîñòè èñõîäíûõ äàííûõ // Èíôîðìàöèîí-
íûå òåõíîëîãèè. — 2001. — ¹ 2. — Ñ. 27–32.
43. Ñ å ì å í î â Â . Â . Ëèíåéíûé âàðèàöèîííûé ïðèíöèï äëÿ âûïóêëîé âåêòîðíîé ìàêñèìèçà-
öèè // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 2007. — ¹ 2. — Ñ. 105–114.
44. Å ì å ë è ÷ å â  . À . , à ó ð å â ñ ê è é Å . Å . Oá óñòîé÷èâîñòè âåêòîðíîé êîìáèíàòîðíîé
çàäà÷è ðàçáèåíèÿ // Òàì æå. — 2007. — ¹ 3. — Ñ. 177–181.
45. Ë å á å ä å â à Ò . Ò . , Ñ å ð ã è å í ê î Ò . È . Óñòîé÷èâîñòü ïî âåêòîðíîìó êðèòåðèþ è îãðà-
íè÷åíèÿì âåêòîðíîé öåëî÷èñëåííîé çàäà÷è êâàäðàòè÷íîãî ïðîãðàììèðîâàíèÿ // Òàì æå. —
2006. — ¹ 5. — Ñ. 46–73.
46. Ê î ð á ó ò À . À , Ô è í ê å ë ü ø ò å é í Þ . Þ . Äèñêðåòíîå ïðîãðàììèðîâàíèå. — Ì.: Íà-
óêà, 1969. — 368 ñ.
47. Ê î ð ì å í Ò . , Ë å é ç å ð ñ î í × . , Ð è â å ñ ò Ð . Àëãîðèòìû: ïîñòðîåíèå è àíàëèç. —
Ì.: ÌÖÍÌÎ, 2001. — 960 ñ.
Ïîñòóïèëà 02.07.2007
44 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 5
|
| id | nasplib_isofts_kiev_ua-123456789-44251 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0023-1274 |
| language | Russian |
| last_indexed | 2025-12-07T16:30:15Z |
| publishDate | 2008 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Емец, О.А. Роскладка, А.А. 2013-05-27T13:58:25Z 2013-05-27T13:58:25Z 2008 О комбинаторной оптимизации в условиях неопределенности / О.А. Емец, А.А. Роскладка // Кибернетика и системный анализ. — 2008. — № 5. — С. 35-44 . — Бібліогр.: 47 назв. — рос. 0023-1274 https://nasplib.isofts.kiev.ua/handle/123456789/44251 519.85 ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Системный анализ О комбинаторной оптимизации в условиях неопределенности Article published earlier |
| spellingShingle | О комбинаторной оптимизации в условиях неопределенности Емец, О.А. Роскладка, А.А. Системный анализ |
| title | О комбинаторной оптимизации в условиях неопределенности |
| title_full | О комбинаторной оптимизации в условиях неопределенности |
| title_fullStr | О комбинаторной оптимизации в условиях неопределенности |
| title_full_unstemmed | О комбинаторной оптимизации в условиях неопределенности |
| title_short | О комбинаторной оптимизации в условиях неопределенности |
| title_sort | о комбинаторной оптимизации в условиях неопределенности |
| topic | Системный анализ |
| topic_facet | Системный анализ |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/44251 |
| work_keys_str_mv | AT emecoa okombinatornoioptimizaciivusloviâhneopredelennosti AT roskladkaaa okombinatornoioptimizaciivusloviâhneopredelennosti |