Комбинаторная оптимизационная модель упаковки прямоугольников со стохастическими параметрами
На основе введенного отношения порядка на множестве дискретных случайных величин формализованы понятия взаимного расположения в полосе прямоугольников со стохастическими параметрами: попадание в полосу, касание, пересечение, непересечение. Построена комбинаторная математическая модель задачи оптимал...
Gespeichert in:
| Veröffentlicht in: | Кибернетика и системный анализ |
|---|---|
| Datum: | 2015 |
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | Russisch |
| Veröffentlicht: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2015
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/124841 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Комбинаторная оптимизационная модель упаковки прямоугольников со стохастическими параметрами / О.А. Емец, Т.Н. Барболина // Кибернетика и системный анализ. — 2015. — Т. 51, № 4. — С. 99-111. — Бібліогр.: 15 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859626428282175488 |
|---|---|
| author | Емец, О.А. Барболина, Т.Н. |
| author_facet | Емец, О.А. Барболина, Т.Н. |
| citation_txt | Комбинаторная оптимизационная модель упаковки прямоугольников со стохастическими параметрами / О.А. Емец, Т.Н. Барболина // Кибернетика и системный анализ. — 2015. — Т. 51, № 4. — С. 99-111. — Бібліогр.: 15 назв. — рос. |
| collection | DSpace DC |
| container_title | Кибернетика и системный анализ |
| description | На основе введенного отношения порядка на множестве дискретных случайных величин формализованы понятия взаимного расположения в полосе прямоугольников со стохастическими параметрами: попадание в полосу, касание, пересечение, непересечение. Построена комбинаторная математическая модель задачи оптимальной упаковки прямоугольников для случая, когда входные данные являются дискретными случайными величинами.
На основі введеного відношення порядку на множині дискретних випадкових величин формалізовано поняття взаємного розташування у смузі прямокутників зі стохастичними параметрами: потрапляння у смугу, дотик, перетин, неперетин. Побудовано комбінаторну математичну модель задачі оптимального пакування прямокутників для випадку, коли вхідні дані є дискретними випадковими величинами.
Based on the relation of order on the set of discrete random variables, which is introduced in the paper, we formalize the arrangement of rectangles with stochastic parameters in a breadth: hit in a breadth, tangency, intersection, non-intersection. We also construct a combinatorial mathematical model of optimal rectangle packing when data are discrete random variables
|
| first_indexed | 2025-11-29T11:59:02Z |
| format | Article |
| fulltext |
ÓÄÊ 519.85
Î.À. ÅÌÅÖ, Ò.Í. ÁÀÐÁÎËÈÍÀ
ÊÎÌÁÈÍÀÒÎÐÍÀß ÎÏÒÈÌÈÇÀÖÈÎÍÍÀß ÌÎÄÅËÜ ÓÏÀÊÎÂÊÈ
ÏÐßÌÎÓÃÎËÜÍÈÊΠÑÎ ÑÒÎÕÀÑÒÈ×ÅÑÊÈÌÈ ÏÀÐÀÌÅÒÐÀÌÈ
Àííîòàöèÿ. Íà îñíîâå ââåäåííîãî îòíîøåíèÿ ïîðÿäêà íà ìíîæåñòâå äèñêðåòíûõ ñëó÷àé-
íûõ âåëè÷èí ôîðìàëèçîâàíû ïîíÿòèÿ âçàèìíîãî ðàñïîëîæåíèÿ â ïîëîñå ïðÿìîóãîëüíèêîâ
ñî ñòîõàñòè÷åñêèìè ïàðàìåòðàìè: ïîïàäàíèå â ïîëîñó, êàñàíèå, ïåðåñå÷åíèå, íåïåðåñå÷å-
íèå. Ïîñòðîåíà êîìáèíàòîðíàÿ ìàòåìàòè÷åñêàÿ ìîäåëü çàäà÷è îïòèìàëüíîé óïàêîâêè ïðÿ-
ìîóãîëüíèêîâ äëÿ ñëó÷àÿ, êîãäà âõîäíûå äàííûå ÿâëÿþòñÿ äèñêðåòíûìè ñëó÷àéíûìè âå-
ëè÷èíàìè.
Êëþ÷åâûå ñëîâà: äèñêðåòíàÿ ñëó÷àéíàÿ âåëè÷èíà, êîìáèíàòîðíàÿ îïòèìèçàöèÿ, ëèíåé-
íûé ïîðÿäîê, ìîäåëè óïàêîâêè, ñòîõàñòè÷åñêàÿ îïòèìèçàöèÿ, óïàêîâêà ïðÿìîóãîëüíèêîâ.
ÂÂÅÄÅÍÈÅ
Ðàçâèòèå êîìáèíàòîðíîé îïòèìèçàöèè ñ ó÷åòîì íåîïðåäåëåííî çàäàííîé èí-
ôîðìàöèè îáóñëîâèëî ïîÿâëåíèå ìîäåëåé, èñïîëüçóþùèõ èñõîäíûå äàííûå
â óñëîâèÿõ íåîïðåäåëåííîñòè [1–5]. Èññëåäîâàíèå ìåòîäîâ ðåøåíèÿ îïòèìèçà-
öèîííûõ çàäà÷ íà ìíîæåñòâàõ êîìáèíàòîðíîé ïðèðîäû ñ ó÷åòîì ðàçëè÷íûõ
âèäîâ íåîïðåäåëåííîñòè îñóùåñòâëÿåòñÿ â òîì ÷èñëå â ðàìêàõ åâêëèäîâîé
êîìáèíàòîðíîé îïòèìèçàöèè [6–10].
Ðàññìîòðèì íåîáõîäèìûå ïîíÿòèÿ è îïðåäåëåíèÿ åâêëèäîâîé êîìáèíàòîð-
íîé îïòèìèçàöèè íà îñíîâå ðàáîòû [11]. Ïîä ìóëüòèìíîæåñòâîì ïîíèìàåì ñîâî-
êóïíîñòü ýëåìåíòîâ, ñðåäè êîòîðûõ ìîãóò áûòü îäèíàêîâûå. Óïîðÿäî÷åííîé
k-âûáîðêîé èç ìóëüòèìíîæåñòâà G g g� { }1, ,� � íàçûâàåòñÿ íàáîð
( , , )g gi ik1
� , (1)
ãäå g Gij
� , i i i i Jj t j t� � �, � , � �j t Jk, (çäåñü è äàëåå Jn îáîçíà÷åíî ìíîæåñ-
òâî n ïåðâûõ íàòóðàëüíûõ ÷èñåë). Ìíîæåñòâî, ðàçëè÷íûìè ýëåìåíòàìè êîòî-
ðîãî ÿâëÿþòñÿ ðàçëè÷íûå k-âûáîðêè âèäà (1), íàçûâàåòñÿ åâêëèäîâûì êîìáè-
íàòîðíûì. Òàêèì îáðàçîì, ýëåìåíòû åâêëèäîâîãî êîìáèíàòîðíîãî ìíîæåñòâà
îòëè÷àþòñÿ, åñëè îíè íåçàâèñèìî îò äðóãèõ îòëè÷èé èìåþò ðàçëè÷íûé ïîðÿ-
äîê ñëåäîâàíèÿ îáðàçóþùèõ èõ ñèìâîëîâ. Ïðèìåðû åâêëèäîâûõ êîìáèíàòîð-
íûõ ìíîæåñòâ:
� îáùåå ìíîæåñòâî ðàçìåùåíèé — ìíîæåñòâî âñåõ k-âûáîðîê âèäà (1) èç
ìóëüòèìíîæåñòâà G ;
� îáùåå ìíîæåñòâî ïåðåñòàíîâîê — ìíîæåñòâî âñåõ k-âûáîðîê âèäà (1)
èç ìóëüòèìíîæåñòâà G ïðè óñëîâèè k � � .
Ïðèìåíåíèå àïïàðàòà åâêëèäîâîé êîìáèíàòîðíîé îïòèìèçàöèè ïîçâîëÿåò
àäåêâàòíî ôîðìàëèçîâàòü öåëûé ðÿä ïðàêòè÷åñêè çíà÷èìûõ çàäà÷. Îäíîé èç íèõ
ÿâëÿåòñÿ çàäà÷à óïàêîâêè ïðÿìîóãîëüíèêîâ, êîòîðàÿ â ïðîñòåéøåì ñëó÷àå ôîðìó-
ëèðóåòñÿ ñëåäóþùèì îáðàçîì. Ïóñòü åñòü íåêîòîðàÿ ïîëóáåñêîíå÷íàÿ ïîëîñà, ðàç-
äåëåííàÿ íà ïîëîñêè îäèíàêîâîé øèðèíîé h0 . Çàäàíû òàêæå p ïðÿìîóãîëüíèêîâ
øèðèíîé h0 ñ äëèíàìè a a p1, ,� . Çàäà÷à ñîñòîèò â ðàñïîëîæåíèè ïðÿìîóãîëüíè-
êîâ áåç íàëîæåíèé â ïîëîñå òàêèì îáðàçîì, ÷òîáû äëèíà çàíÿòîé ÷àñòè ïîëîñû
áûëà ìèíèìàëüíî âîçìîæíîé (ïîä äëèíîé çàíÿòîé ÷àñòè ïîëîñû ïîíèìàþò ìàê-
ñèìàëüíóþ èç äëèí çàíÿòûõ ÷àñòåé îòäåëüíûõ ïîëîñîê).  îïòèìàëüíîì ðåøå-
íèè ïðÿìîóãîëüíèêè äîëæíû ðàçìåùàòüñÿ â ïîëîñêàõ òàê, ÷òîáû êàæäûé ñëåäó-
þùèé êàñàëñÿ ïðåäûäóùåãî.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 4 99
© Î.À. Åìåö, Ò.Í. Áàðáîëèíà, 2015
Èçâåñòíû ìåòîäû ðåøåíèÿ ýòîé çàäà÷è â ñëó÷àÿõ, êîãäà âõîäíûå äàííûå ÿâ-
ëÿþòñÿ äåéñòâèòåëüíûìè ÷èñëàìè [11, 12], íå÷åòêèìè ÷èñëàìè [6, 7], öåíòðèðî-
âàííûìè èíòåðâàëàìè [8, 9], ñëó÷àéíûìè âåëè÷èíàìè ñ íîðìàëüíûì çàêîíîì
ðàñïðåäåëåíèÿ [10], îäíàêî àêòóàëüíûì îñòàåòñÿ åå ðàññìîòðåíèå ñ ó÷åòîì ñòî-
õàñòè÷åñêîé íåîïðåäåëåííîñòè, êîãäà ñëó÷àéíûå âåëè÷èíû èìåþò äðóãîé çàêîí
ðàñïðåäåëåíèÿ.
Îòìåòèì, ÷òî â ñëó÷àå íàëè÷èÿ òîé èëè èíîé íåîïðåäåëåííîñòè âõîäíûõ
äàííûõ âîçíèêàåò âîïðîñ î ôîðìàëèçàöèè ïîíÿòèé âçàèìíîãî ðàñïîëîæåíèÿ
ïðÿìîóãîëüíèêîâ â ïîëîñå, êàê ýòî ñäåëàíî, íàïðèìåð, â [6] äëÿ ïðÿìîóãîëüíè-
êîâ ñ íå÷åòêèìè ïàðàìåòðàìè. Äëÿ ñëó÷àéíûõ âåëè÷èí àíàëîãè÷íûå ðåçóëüòàòû
íå ïðèâîäèëèñü.
Òàêèì îáðàçîì, äëÿ ìàòåìàòè÷åñêîé ïîñòàíîâêè çàäà÷è óïàêîâêè ïðÿìîóãîëü-
íèêîâ ñî ñòîõàñòè÷åñêîé íåîïðåäåëåííîñòüþ ñíà÷àëà íåîáõîäèìî îïðåäåëèòü,
÷òî ïîíèìàòü ïîä ðàçëè÷íûìè ñïîñîáàìè ðàçìåùåíèÿ ïðÿìîóãîëüíèêîâ:
� ïîïàäàíèå ïðÿìîóãîëüíèêà â ïîëîñó;
� âçàèìíîå ïåðåñå÷åíèå ïðÿìîóãîëüíèêîâ, ðàçìåùåííûõ â ïîëîñå;
� âçàèìíîå íåïåðåñå÷åíèå ïðÿìîóãîëüíèêîâ, ðàçìåùåííûõ â ïîëîñå;
� êàñàíèå ïðÿìîóãîëüíèêîâ, ðàçìåùåííûõ â ïîëîñå.
Äëÿ ôîðìàëèçàöèè óêàçàííûõ ïîíÿòèé ìîæíî èñïîëüçîâàòü óïîðÿäî÷åíèå
ñëó÷àéíûõ âåëè÷èí (íåêîòîðûå âîçìîæíûå ñïîñîáû ââåäåíèÿ ïîðÿäêà íà ìíî-
æåñòâå äèñêðåòíûõ ñëó÷àéíûõ âåëè÷èí ðàññìîòðåíû â [13, 14]).
ÎÏÐÅÄÅËÅÍÈÅ ÏÎÐßÄÊÀ ÍÀ ÌÍÎÆÅÑÒÂÅ ÑËÓ×ÀÉÍÛÕ ÂÅËÈ×ÈÍ
È ÅÃÎ ÑÂÎÉÑÒÂÀ
 äàííîé ðàáîòå èñïîëüçóåì óïîðÿäî÷åíèå äèñêðåòíûõ ñëó÷àéíûõ âåëè÷èí
â ñîîòâåòñòâèè ñ ïðèâåäåííûì íèæå îïðåäåëåíèåì (äàëåå ïîëàãàåì, ÷òî ñðåäè
âîçìîæíûõ çíà÷åíèé êàæäîé ðàññìàòðèâàåìîé ñëó÷àéíîé âåëè÷èíû åñòü íàè-
ìåíüøåå, ïðè÷åì îíî èìååò íîìåð 1). Ïóñòü äèñêðåòíàÿ ñëó÷àéíàÿ âåëè÷èíà
X ïðèíèìàåò ñ ïîëîæèòåëüíûìè âåðîÿòíîñòÿìè px
1
, px
2
,� çíà÷åíèÿ x1, x2 , � ,
à äèñêðåòíàÿ ñëó÷àéíàÿ âåëè÷èíà Y — ñ ïîëîæèòåëüíûìè âåðîÿòíîñòÿìè p y
1
,
p y
2
,� çíà÷åíèÿ y1, y2 ,� Îáîçíà÷èì M X( ) ìàòåìàòè÷åñêîå îæèäàíèå ñëó÷àé-
íîé âåëè÷èíû X , à D X( ) — äèñïåðñèþ.
Îïðåäåëåíèå 1. Íàçîâåì äâå äèñêðåòíûå ñëó÷àéíûå âåëè÷èíû X è Y óïîðÿ-
äî÷åííûìè â âîçðàñòàþùåì (X ïðåäøåñòâóåò Y ) ïîðÿäêå � (îáîçíà÷èì ýòîò ôàêò
X Y� ), åñëè âûïîëíåíî îäíî èç ñëåäóþùèõ óñëîâèé:
1) M X M Y( ) ( )� ;
2) M X M Y( ) ( )� , D X D Y( ) ( ) ;
3) M X M Y( ) ( )� , D X D Y( ) ( )� è íàéäåòñÿ òàêîé èíäåêñ t, ÷òî x yi i� ,
p pi
x
i
y� äëÿ âñåõ i t� , ïðè ýòîì:
3.1) ëèáî x yt t� ,
3.2) ëèáî x yt t� è p pt
x
t
y .
Óòâåðæäåíèå 1. Îòíîøåíèå � íà ìíîæåñòâå äèñêðåòíûõ ñëó÷àéíûõ âåëè-
÷èí ÿâëÿåòñÿ ñòðîãèì ïîðÿäêîì.
Äîêàçàòåëüñòâî. Äëÿ òîãî ÷òîáû îòíîøåíèå áûëî ñòðîãèì ïîðÿäêîì, íåîá-
õîäèìî è äîñòàòî÷íî, ÷òîáû îíî áûëî àíòèðåôëåêñèâíûì, ñèëüíî àíòèñèììåò-
ðè÷íûì è òðàíçèòèâíûì.
Àíòèðåôëåêñèâíîñòü îçíà÷àåò, ÷òî íè ïðè êàêîì X íå èìååò ìåñòà X X� .
Äåéñòâèòåëüíî, M X M X( ) ( )� , D X D X( ) ( )� è x yi i� , p pi
x
i
y� äëÿ âñåõ
i �1 2, , ,� ò.å. íè îäíî èç óñëîâèé îïðåäåëåíèÿ 1 íå âûïîëíÿåòñÿ.
100 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 4
Äîêàæåì ñèëüíóþ àíòèñèììåòðè÷íîñòü, à èìåííî òîò ôàêò, ÷òî íè äëÿ êà-
êèõ X è Y ñîîòíîøåíèÿ X Y� è Y X� íå ìîãóò âûïîëíÿòüñÿ îäíîâðåìåííî.
Ïðåäïîëîæèì îáðàòíîå: X Y� è Y X� . Òîãäà âñëåäñòâèå X Y� èìååì
M X M Y( ) ( )
, à èç Y X� — M Y M X( ) ( )
, îòêóäà M X M Y( ) ( )� .
Àíàëîãè÷íî ïîëó÷àåì D X D Y( ) ( )� . Òàêèì îáðàçîì, óñëîâèÿ 1 è 2 îïðåäåëåíèÿ 1
íå âûïîëíÿþòñÿ, ïîýòîìó äëÿ èíäåêñà t i x y p pi i i
x
i
y� � � �min |{ } äîëæíî âû-
ïîëíÿòüñÿ óñëîâèå 3.1 èëè 3.2. Íî îäíîâðåìåííîå âûïîëíåíèå óñëîâèé x yt t� è
y xt t� íåâîçìîæíî. Ñëåäîâàòåëüíî, äîëæíî èìåòü ìåñòî óñëîâèå 3.2, ò.å. p pt
x
t
y
è p pt
y
t
x , ÷òî òàêæå íåâîçìîæíî. Çíà÷èò, ïðåäïîëîæåíèå íåïðàâèëüíî è îòíî-
øåíèå � ñèëüíî àíòèñèììåòðè÷íî.
Äëÿ äîêàçàòåëüñòâà òðàíçèòèâíîñòè ïîëîæèì X Y� è Y Z� è ðàññìîòðèì
ñëåäóþùèå ñëó÷àè.
1. Ïóñòü M X M Y( ) ( )� èëè M Y M Z( ) ( )� . Òîãäà èìååò ìåñòî îäíî èç òðåõ
ñîîòíîøåíèé:
1) M X M Y M Z( ) ( ) ( )� � ;
2) M X M Y M Z( ) ( ) ( )� � ;
3) M X M Y M Z( ) ( ) ( )� � .
Ñëåäîâàòåëüíî, M X M Z( ) ( )� , ò.å. X Z� .
2. Ïóñòü M X M Y M Z( ) ( ) ( )� � , íî D X D Y( ) ( )� èëè D Y D Z( ) ( )� .
Àíàëîãè÷íî ñëó÷àþ 1 ïîëó÷àåì D X D Z( ) ( ) , ò.å. X Z� .
3. Ïóñòü M X M Y M Z( ) ( ) ( )� � è D X D Y D Z( ) ( ) ( )� � . Òîãäà äëÿ X è Y , Y
è Z èìåþò ìåñòî óñëîâèÿ 3 îïðåäåëåíèÿ 1. Ïóñòü t i x y p pi i i
x
i
y� � � �min |{ },
� � � � �min |{ }j y z p pj j j
y
j
z . Òîãäà min | min ,{ } { }l x z p p tl l l
x
l
z� � � � � . Ðàñ-
ñìîòðèì âîçìîæíûå ñîîòíîøåíèÿ ìåæäó t è �:
3.1) t � �, òîãäà y zt t� è p pt
y
t
z� ; ñëåäîâàòåëüíî, ëèáî x y zt t t� � , ëèáî
x y zt t t� � è p p pt
x
t
y
t
z � ; çíà÷èò, X Z� ;
3.2) t �, òîãäà x y� �� è p px y
� �� ; ñëåäîâàòåëüíî, x y z� � �� � èëè
x y z� � �� � , ïðè÷åì p p px y z
� � �� ; çíà÷èò, X Z� ;
3.3) t � �, òîãäà âîçìîæíû òàêèå âàðèàíòû: x y zt t t� � ; x y zt t t� � ;
x y zt t t� � ; x y zt t t� � , îòêóäà ñëåäóåò p p pt
x
t
y
t
z .
 ëþáîì ñëó÷àå X Z� .
Òàêèì îáðàçîì, îòíîøåíèå � òðàíçèòèâíî. Óòâåðæäåíèå äîêàçàíî.
Îïðåäåëåíèå 2. Íàçîâåì äâå äèñêðåòíûå ñëó÷àéíûå âåëè÷èíû X è Y óïîðÿ-
äî÷åííûìè â íåóáûâàþùåì ïîðÿäêå � (îáîçíà÷èì ýòîò ôàêò X Y� ), åñëè X Y�
èëè X Y� .
Ïîêàæåì, ÷òî ââåäåííîå îòíîøåíèå ÿâëÿåòñÿ ëèíåéíûì ïîðÿäêîì. Äëÿ ýòîãî
ñíà÷àëà äîêàæåì âñïîìîãàòåëüíîå óòâåðæäåíèå.
Óòâåðæäåíèå 2. Åñëè X è Y — ðàçëè÷íûå äèñêðåòíûå ñëó÷àéíûå âåëè÷èíû,
èìåþùèå ñîîòâåòñòâåííî k è m çíà÷åíèé, òî íàéäåòñÿ òàêîé èíäåêñ
t k m
min ,{ }, ÷òî x yt t� èëè p pt
x
t
y� .
Äîêàçàòåëüñòâî. Ïóñòü äëÿ îïðåäåëåííîñòè k m
. Ïðåäïîëîæèì, ÷òî äëÿ
âñåõ t k
èìåþò ìåñòî ðàâåíñòâà x yt t� è p pt
x
t
y� . Òàê êàê ñëó÷àéíûå âåëè÷è-
íû X è Y ðàçëè÷íû, â ýòîì ñëó÷àå äîëæíî áûòü m k . Ñëåäîâàòåëüíî,
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 4 101
p p p p pt
y
t
m
t
y
t
k
t
y
t k
m
t
y
t
k
t
x
t
k
� � � � � �
� � � �
1 1 1 1 1
1,
÷òî íåâîçìîæíî. Òàêèì îáðàçîì, ïðåäïîëîæåíèå íåâåðíî. Óòâåðæäåíèå äîêàçàíî.
Óòâåðæäåíèå 3. Îòíîøåíèå � íà ìíîæåñòâå äèñêðåòíûõ ñëó÷àéíûõ âåëè-
÷èí ÿâëÿåòñÿ ëèíåéíûì ïîðÿäêîì.
Äîêàçàòåëüñòâî. Òàê êàê îòíîøåíèå � — îáúåäèíåíèå ñòðîãîãî ïîðÿäêà �
è äèàãîíàëè, îíî ÿâëÿåòñÿ ïîðÿäêîì [15].
Ïîêàæåì, ÷òî ýòîò ïîðÿäîê ëèíåéíûé, ò.å. äëÿ ëþáûõ äâóõ äèñêðåòíûõ ñëó-
÷àéíûõ âåëè÷èí X è Y âûïîëíÿåòñÿ îäíî èç óñëîâèé: X Y� èëè Y X� .
Ïðåäïîëîæèì, ÷òî íåðàâåíñòâî X Y� íå èìååò ìåñòà. Ñëåäîâàòåëüíî, X è Y —
ðàçëè÷íûå ñëó÷àéíûå âåëè÷èíû, ïðè÷åì M X M Y( ) ( )� . Åñëè M X M Y( ) ( ) , òî
ñîãëàñíî ï. 1 îïðåäåëåíèÿ 1 Y X� , à çíà÷èò, Y X� .
Åñëè M X M Y( ) ( )� , íî D X D Y( ) ( ) , òî òàêæå Y X� .
Ðàññìîòðèì ñëó÷àé, êîãäà M X M Y( ) ( )� è D X D Y( ) ( )� . Ïîñêîëüêó X è Y
ðàçëè÷íû, â ñîîòâåòñòâèè ñ óòâåðæäåíèåì 2 ñóùåñòâóåò òàêîé èíäåêñ t, ÷òî
x yt t� èëè p pt
x
t
y� . Ïî ïðåäïîëîæåíèþ íåðàâåíñòâî X Y� íå âûïîëíÿåòñÿ.
Ñëåäîâàòåëüíî, x yt t� . Ïðè x yt t èìååì Y X� ñîãëàñíî ï. 3.1 îïðåäåëåíèÿ 1.
Åñëè x yt t� , òî p pt
x
t
y , à çíà÷èò, Y X� (ï. 3.2 îïðåäåëåíèÿ 1). Òàêèì îáðàçîì,
åñëè äëÿ ñëó÷àéíûõ âåëè÷èí X è Y íå èìååò ìåñòà ñîîòíîøåíèå X Y� , òî Y X� .
Óòâåðæäåíèå äîêàçàíî.
Ñóùåñòâåííûì â çàäà÷àõ îïòèìèçàöèè ÿâëÿåòñÿ îïðåäåëåíèå ìèíèìóìà è ìàê-
ñèìóìà íà çàäàííîì ìíîæåñòâå äèñêðåòíûõ ñëó÷àéíûõ âåëè÷èí. Èñïîëüçóÿ ââåäåí-
íûé â îïðåäåëåíèè 2 ëèíåéíûé ïîðÿäîê, óïîðÿäî÷èì ýëåìåíòû çàäàííîãî êîíå÷íî-
ãî ìíîæåñòâà íåçàâèñèìûõ äèñêðåòíûõ ñëó÷àéíûõ âåëè÷èí: X X X s1 2
� � �... .
Ìàêñèìóìîì ÿâëÿåòñÿ âåëè÷èíà X s, à ìèíèìóìîì — âåëè÷èíà X 1.
Îòìåòèì, ÷òî ëèíåéíûé ïîðÿäîê èìååò âàæíîå äëÿ ìîäåëèðîâàíèÿ ðÿäà
ïðàêòè÷åñêèõ çàäà÷ ñâîéñòâî: óïîðÿäî÷åíèå äâóõ ñëó÷àéíûõ âåëè÷èí ñîõðàíÿåò-
ñÿ ïðè ïðèáàâëåíèè ê ëåâîé è ïðàâîé ÷àñòè ñîîòíîøåíèÿ îäíîé è òîé æå
ñëó÷àéíîé âåëè÷èíû.
Ðàññìîòðèì ñóììó Z X Y� � , ãäå X è Y — íåçàâèñèìûå ñëó÷àéíûå âåëè÷è-
íû. Ìíîæåñòâî çíà÷åíèé äèñêðåòíîé ñëó÷àéíîé âåëè÷èíû Z åñòü ìíîæåñòâî ðàç-
ëè÷íûõ çíà÷åíèé ñóìì âèäà x yi j� , à ñîîòâåòñòâóþùèå âåðîÿòíîñòè ðàâíû
p p p
k
z
i
x
j
y
i j x y zi j k
�
� �
, :
.
Óòâåðæäåíèå 4. Åñëè äëÿ äèñêðåòíûõ ñëó÷àéíûõ âåëè÷èí X è Y âûïîëíÿ-
åòñÿ óñëîâèå X Y� è âåëè÷èíû X è Z, Y è Z íåçàâèñèìû, òî òàêæå èìååò ìåñòî
X Z Y Z� �� .
Äîêàçàòåëüñòâî. Îáîçíà÷èì X Z X� � , Y Z Y� � .
Åñëè M X M Y( ) ( )� , òî íà îñíîâàíèè òîãî ôàêòà, ÷òî ìàòåìàòè÷åñêîå îæèäà-
íèå ñóììû ñëó÷àéíûõ âåëè÷èí ðàâíî ñóììå èõ ìàòåìàòè÷åñêèõ îæèäàíèé [16],
èìååì
M X M X Z M X M Z M Y M Z M Y Z M Y( ) ( ) ( ) ( ) ( ) ( ) ( ) ( )� � � � � � � � � .
Òàêèì îáðàçîì, X Z Y Z� �� ñîãëàñíî óñëîâèþ 1 îïðåäåëåíèÿ 1.
Åñëè M X M Y( ) ( )� è D X D Y( ) ( ) , òî àíàëîãè÷íî ïðåäûäóùåìó ñëó÷àþ
D X D X D Z D Y D Z D Y( ) ( ) ( ) ( ) ( ) ( )� � � �
102 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 4
(äèñïåðñèÿ ñóììû íåçàâèñèìûõ ñëó÷àéíûõ âåëè÷èí ðàâíà ñóììå èõ äèñïåð-
ñèé [16]). Ñëåäîâàòåëüíî, X Z Y Z� �� ñîãëàñíî óñëîâèþ 2 îïðåäåëåíèÿ 1.
Ïóñòü M X M Y( ) ( )� , D X D Y( ) ( )� . Òîãäà ñóùåñòâóåò òàêîé èíäåêñ t, äëÿ
êîòîðîãî âûïîëíÿåòñÿ óñëîâèå 3 îïðåäåëåíèÿ 1. Ñëåäîâàòåëüíî, äëÿ ëþáûõ j
è âñåõ i t� âûïîëíÿþòñÿ ðàâåíñòâà
x z y zi j i j� � � , p p p pi
x
j
z
i
y
j
z� . (2)
Ýòî îçíà÷àåò, ÷òî x yk k� äëÿ âñåõ k s� , ãäå x x zs t� � 1, y y zs t� � 1.  òî æå
âðåìÿ äëÿ âñåõ i t è ïðîèçâîëüíîãî j èìååì
x z x z x z xi j t j t s� � � � �1 , y z y z y z yi j t j t s� � � � �1 .
Òàêèì îáðàçîì, äëÿ âñåõ k s� â ñóììàõ
p p p
k
x
i
x
j
z
i j x z xi j k
�
� �
, :
, p p p
k
y
i
y
j
z
i j y z yi j k
�
� �
, :
âñå i t� , à çíà÷èò, p p
k
x
k
y� .
Ïóñòü äëÿ âñåõ k s� âûïîëíÿþòñÿ óñëîâèÿ x yk k� è p p
k
x
k
y� . Åñëè ïðè ýòîì
x x z y y zs t s t� � � � �1 1, òî ïîëó÷àåì X Y� .  ïðîòèâíîì ñëó÷àå èç x yt t
(ñî-
ãëàñíî óñëîâèþ 3 îïðåäåëåíèÿ 1) èìååì x ys s� , ïðè ýòîì p pt
x
t
y .
Ðàññìîòðèì âåðîÿòíîñòè ps
x è ps
y . Âñëåäñòâèå (2) äëÿ èíäåêñîâ â ñóììàõ
x z xi j s� � , y z yi j s� � âûïîëíÿåòñÿ óñëîâèå i t
, ïðè÷åì åñëè i t� , òî j �1.
Ñëåäîâàòåëüíî,
p p p p ps
x
i
x
j
z
i j x z x
i t
t
x z
i j k
� � �
� �
�
, :
1
� � �
� �
�
� �
�
i j y z y
i t
i
y
j
z
t
x z
i j y z y
i t
i
y
i j k i j k
p p p p p
, : , :
1
p p p pj
z
t
y z
s
y� �
1
,
ò.å. X Y� . Óòâåðæäåíèå äîêàçàíî.
Ñëåäñòâèå 1. Åñëè äëÿ äèñêðåòíûõ ñëó÷àéíûõ âåëè÷èí X è Y âûïîëíÿåòñÿ
óñëîâèå X Y� è âåëè÷èíû X è Z , Y è Z íåçàâèñèìû, òî òàêæå èìååò ìåñòî
X Z Y Z� �� .
Äîêàçàòåëüñòâî. Ñîãëàñíî îïðåäåëåíèþ 2 X Y� , åñëè X Y� èëè X Y� .
 ïåðâîì ñëó÷àå âûïîëíåíèå óñëîâèÿ X Z Y Z� �� ñëåäóåò èç óòâåðæäåíèÿ 4, âî âòî-
ðîì âûïîëíÿåòñÿ ðàâåíñòâî X Z Y Z� � � , îòêóäà X Z Y Z� �� . Ñëåäñòâèå äîêàçàíî.
Ñëåäñòâèå 2. Åñëè äëÿ äèñêðåòíûõ ñëó÷àéíûõ âåëè÷èí X è Y âûïîëíÿåòñÿ
óñëîâèå X Y� , à âåëè÷èíû X è Z , Y è Z íåçàâèñèìû, ïðè÷åì âñå âîçìîæíûå çíà-
÷åíèÿ âåëè÷èíû Z íåîòðèöàòåëüíû, òî òàêæå èìååò ìåñòî ñîîòíîøåíèå X Y Z� � .
Äîêàçàòåëüñòâî. Ïîñêîëüêó âñå çíà÷åíèÿ âåëè÷èíû Z íåîòðèöàòåëüíû,
M Z( ) � 0, ïðè÷åì M Z( ) � 0 òîëüêî â ñëó÷àå, êîãäà z1 0� , p z
1
1� . Çíà÷èò, ïðè
M Z( ) � 0 èìååì òàêæå X X Z� � . Åñëè M Z( ) 0, òî M X M X M Z( ) ( ) ( )� � �
� �M X Z( ), ñëåäîâàòåëüíî, ñîãëàñíî îïðåäåëåíèþ 1 X X Z� � . Òàêèì îáðàçîì,
ïðè âûïîëíåíèè óñëîâèé ñëåäñòâèÿ èìååì X X Z� � . Èç ñëåäñòâèÿ 1 òàêæå âû-
òåêàåò X Z Y Z� �� . Èç äâóõ ïîñëåäíèõ íåðàâåíñòâ è òðàíçèòèâíîñòè îòíîøå-
íèÿ � ïîëó÷àåì X Y Z� � . Ñëåäñòâèå äîêàçàíî.
Ïîñëåäíåå ñâîéñòâî ñóììû è ïîðÿäêà âàæíî äëÿ ïðèìåíåíèÿ ïåðåáîðíûõ
ìåòîäîâ (òèïà âåòâåé è ãðàíèö), ïîñêîëüêó ïîçâîëÿåò îñóùåñòâëÿòü îòñå÷åíèå
«áåñïåðñïåêòèâíûõ» ïîäìíîæåñòâ.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 4 103
ÔÎÐÌÀËÈÇÀÖÈß ÐÀÑÏÎËÎÆÅÍÈß ÏÐßÌÎÓÃÎËÜÍÈÊÎÂ
ÑÎ ÑÒÎÕÀÑÒÈ×ÅÑÊÈÌÈ ÏÀÐÀÌÅÒÐÀÌÈ
Ïóñòü øèðèíà ïîëîñû �0 ðàâíà h0 . Ñâÿæåì ñ íèæíèì ëåâûì óãëîì ïîëîñû
íà÷àëî ñèñòåìû êîîðäèíàò, íàïðàâèâ îñè Ox1, Ox2 ïî ñòîðîíàì ïîëîñû. Ðàñ-
ñìîòðèì ðàñïîëîæåíèå ïðÿìîóãîëüíèêà � â ïîëîñå, ïðè ýòîì áóäåì ñ÷èòàòü,
÷òî ñòîðîíû ïðÿìîóãîëüíèêà ïàðàëëåëüíû îñÿì êîîðäèíàò. Òîãäà ðàñïîëîæå-
íèå ïðÿìîóãîëüíèêà � îòíîñèòåëüíî ïîëîñû ìîæíî îïðåäåëèòü òàêèìè ïàðà-
ìåòðàìè: � �, — ñîîòâåòñòâåííî àáñöèññà è îðäèíàòà ëåâîãî íèæíåãî óãëà ïðÿ-
ìîóãîëüíèêà â ñèñòåìå êîîðäèíàò Ox x1 2 ; h — øèðèíà (âûñîòà) ïðÿìîóãîëüíè-
êà; d — äëèíà ïðÿìîóãîëüíèêà.
Ïðÿìîóãîëüíèê ñ óêàçàííûìè ïàðàìåòðàìè îáîçíà÷èì �( , , , )� � h d . Ïîëàãà-
åì, ÷òî øèðèíà ïîëîñû h0 è ïàðàìåòðû � �, , ,h d — íåçàâèñèìûå äèñêðåòíûå ñëó-
÷àéíûå âåëè÷èíû (â ÷àñòíîñòè, äåéñòâèòåëüíûå ÷èñëà), ïðè÷åì ñðåäè âîçìîæ-
íûõ çíà÷åíèé êàæäîé âåëè÷èíû åñòü íàèìåíüøåå.
Îïðåäåëåíèå 3. Ïðÿìîóãîëüíèê �( , , , )� � h d íàçîâåì ðàçìåùàþùèìñÿ â ïî-
ëóáåñêîíå÷íîé ïîëîñå �0 øèðèíîé h0 , åñëè
0
0
0
�
�
�
�
�
�
,
,
.�
�
�
�
�
� h h
(3)
Óñëîâèÿ (3) íàçîâåì óñëîâèÿìè ðàçìåùåíèÿ ïðÿìîóãîëüíèêà � â ïîëîñå �0 .
Çàìå÷àíèå 1. Åñëè ïîðÿäîê íà ìíîæåñòâå äèñêðåòíûõ ñëó÷àéíûõ âåëè÷èí
çàäàí â ñîîòâåòñòâèè ñ îïðåäåëåíèåì 2, òî óñëîâèå 0� � îçíà÷àåò, ÷òî � — íåîò-
ðèöàòåëüíîå äåéñòâèòåëüíîå ÷èñëî èëè äèñêðåòíàÿ ñëó÷àéíàÿ âåëè÷èíà ñ íåîòðè-
öàòåëüíûì ìàòåìàòè÷åñêèì îæèäàíèåì.
Ðàññìîòðèì âçàèìíîå ðàñïîëîæåíèå â ïîëîñå äâóõ ïðÿìîóãîëüíèêîâ —
�( , , , )� � h d è � � � � �� ( , , , )� � h d (êàê è âûøå, âñå ïàðàìåòðû ÿâëÿþòñÿ íåçàâèñèìû-
ìè äèñêðåòíûìè ñëó÷àéíûìè âåëè÷èíàìè, ó êîòîðûõ ñóùåñòâóåò íàèìåíüøåå
âîçìîæíîå çíà÷åíèå). Èçó÷èì ñíà÷àëà ñëó÷àé, êîãäà h h h� � � 0 , ïðè ýòîì
� �� � � 0.
Îïðåäåëåíèå 4. Ïðÿìîóãîëüíèê � � � � �� ( , , , )� � h d áóäåì íàçûâàòü òàêèì, êî-
òîðûé â ïîëóáåñêîíå÷íîé ïîëîñå �0 :
1) êàñàåòñÿ ïðÿìîóãîëüíèêà �( , , , )� � h d ñïðàâà, åñëè � �� � �d ;
2) ðàñïîëîæåí ñïðàâà îò ïðÿìîóãîëüíèêà �( , , , )� � h d (ò.å. � è �� íå ïåðåñå-
êàþòñÿ), åñëè � �� �d � ;
3) ïåðåñåêàåòñÿ ñ ïðÿìîóãîëüíèêîì �( , , , )� � h d ñïðàâà, åñëè � � �� �� � d .
Ïðèìåð 1. Ðàññìîòðèì ðàçìåùåíèå ïðÿìîóãîëüíèêîâ �1 1 1 1 1( , , , )� � h d ,
�2 2 2 2 2( , , , )� � h d , �3 3 3 3 3( , , , )� � h d â ïîëóáåñêîíå÷íîé ïîëîñå �0 øèðèíîé
h0 2� , åñëè ïîðÿäîê çàäàí îïðåäåëåíèåì 2, � � �1 2 3 0� � � , h h h h1 2 3 0 2� � � � ,
�1, �2 , �3 , d1, d2 , d3 — ñëó÷àéíûå âåëè÷èíû, çàäàííûå ðÿäàìè ðàñïðåäåëåíèÿ
â ñîîòâåòñòâèè ñ òàáë. 1.
Ñëó÷àéíàÿ âåëè÷èíà �1 1� d ìîæåò ïðèíèìàòü òàêèå çíà÷åíèÿ: 2 3 5� � ñ âå-
ðîÿòíîñòüþ1 0 2 0 2� �, , ; 2 5 7� � ñ âåðîÿòíîñòüþ1 0 4 0 4� �, , ; 2 6 8� � ñ âåðîÿòíîñòüþ
1 0 4 0 4� �, , , ò.å. ðÿä ðàñïðåäåëåíèÿ ñëó÷àéíîé âåëè÷èíû �1 1� d èìååò ñëåäóþ-
ùèé âèä:
Òàêèì îáðàçîì, � �1 1 2� �d , îòêóäà ñîãëàñíî ï. 1 îïðåäåëåíèÿ 4 ñëåäóåò, ÷òî
ïðÿìîóãîëüíèê �2 êàñàåòñÿ ñïðàâà ïðÿìîóãîëüíèêà �1.
104 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 4
� çíà÷åíèÿ 5 7 8
� âåðîÿòíîñòè 0,2 0,4 0,4.
Îïðåäåëèì âçàèìíîå ðàñïîëîæåíèå ïðÿìîóãîëüíèêîâ �3 è �2 :
M d M M d( ) ( ) ( ) , ,� �2 2 2 2 7 3 5 10 5� � � � � � , M ( ) ,�3 10 5� ,
D d D D d( ) ( ) ( ) , , ,� �2 2 2 2 1 2 2 25 3 45� � � � � � , D( ) ,�3 3 45� ,
ïðè ýòîì íàèìåíüøåå çíà÷åíèå âåëè÷èíû �2 2� d ðàâíî 8, òîãäà êàê íàèìåíü-
øåå çíà÷åíèå âåëè÷èíû �3 ðàâíî 7 8� , ïîýòîìó � �3 2 2� � d . Ïîñêîëüêó òàêæå
� �2 3� (êàê ñëåäñòâèå M M( ) ( ) ,� �2 37 10 5� � � ), ñîãëàñíî ï. 3 îïðåäåëåíèÿ 4
ïðÿìîóãîëüíèêè �3 è �2 ïåðåñåêàþòñÿ.
Äëÿ ïðÿìîóãîëüíèêîâ �3 è �1 èìååì M d M( ) ( ) ,� �1 1 37 10 5� � � � , ïîýòî-
ìó ñîãëàñíî ï. 2 îïðåäåëåíèÿ 4 ïðÿìîóãîëüíèêè �3 è �1 íå ïåðåñåêàþòñÿ.
Ñôîðìóëèðóåì îïðåäåëåíèÿ ðàçëè÷íûõ âàðèàíòîâ âçàèìíîãî ðàñïîëîæåíèÿ
ïðÿìîóãîëüíèêîâ �( , , , )� � h d è � � � � �� ( , , , )� � h d â îáùåì ñëó÷àå (íå íàðóøàÿ îáù-
íîñòè, ìîæíî ñ÷èòàòü, ÷òî � �� �).
Îïðåäåëåíèå 5. Ïðÿìîóãîëüíèêè �( , , , )� � h d è � � � � �� ( , , , )� � h d íàçîâåì ïå-
ðåñåêàþùèìèñÿ, åñëè âûïîëíÿåòñÿ îäíà èç äâóõ ñèñòåì ñîîòíîøåíèé:
� � �
� � �
� �
� �
� �
� �
�
�
�
d
h
,
,
� � �
� � �
� �
� �
� �
� � � �
�
�
�
d
h
,
.
Îïðåäåëåíèå 6. Ïðÿìîóãîëüíèêè �( , , , )� � h d è � � � � �� ( , , , )� � h d íàçîâåì íå-
ïåðåñåêàþùèìèñÿ, åñëè âûïîëíÿåòñÿ ñîâîêóïíîñòü ñîîòíîøåíèé
� �
� �
� �
� �
� �
� � �
�
�
�
�
�
d
h
h
�
�
�
,
,
.
Ïðèìåð 2. Ðàññìîòðèì ðàçìåùåíèå ïðÿìîóãîëüíèêîâ �1 1 1 1 1( , , , )� � h d ,
�2 2 2 2 2( , , , )� � h d , �3 3 3 3 3( , , , )� � h d â ïîëóáåñêîíå÷íîé ïîëîñå �0 øèðèíîé
h0 6� , åñëè:
M ( )�1 2� , M ( )�1 1� , M h( )1 2� , M d( )1 4� ;
M ( )�2 5� , M ( ) ,� 2 2 5� , M h( )2 1� , M d( )2 4� ;
M ( ) ,�3 8 5� , M ( )� 3 2� , M h( )3 2� , M d( )3 3� .
Ïðÿìîóãîëüíèêè � � �1 2 3, , ðàçìåùàþòñÿ â ïîëîñå �0 , òàê êàê äëÿ íèõ âû-
ïîëíÿþòñÿ óñëîâèÿ (3) ðàçìåùåíèÿ ïðÿìîóãîëüíèêà â ïîëîñå.  ÷àñòíîñòè, äëÿ
�1 èìååì
0 2
0 1
3 6
1
1
1 1 0
�
�
� �
�
�
�
�
�
�
M
M
M h M h
( ) ,
( ) ,
( ) ( ) ,
�
�
�
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 4 105
Ò à á ë è ö à 1
Ïàðàìåòðû
Ðÿäû ðàñïðåäåëåíèÿ ïàðàìåòðîâ ïðÿìîóãîëüíèêîâ
�1 � 2 � 3
Çíà÷åíèÿ � i 2 5 7 8 7 10 12 14
Âåðîÿòíîñòè
çíà÷åíèé � i
1 0,2 0,4 0,4 0,1 0,65 0,1 0,15
Çíà÷åíèÿ di 3 5 6 3 8 3
Âåðîÿòíîñòè
çíà÷åíèé di
0,2 0,4 0,4 0,9 0,1 1
äëÿ �2 è �3 ñîîòâåòñòâåííî
0 5
0 2 5
3 5 6
2
2
2 2 0
�
�
� �
�
�
�
�
�
�
M
M
M h M h
( ) ,
( ) , ,
( ) , ( ) ,
�
�
�
0 8 5
0 2
4 6
3
3
3 3 0
�
�
� �
�
�
�
�
�
�
M
M
M h M h
( ) , ,
( ) ,
( ) ( ) .
�
�
�
Òàêèì îáðàçîì,
0
0
0
�
�
�
�
�
�
i
i
i ih h
,
,
,�
�
�
�
�
�
i �1 2 3, , .
Ðàññìîòðèì âçàèìíîå ðàçìåùåíèå ïðÿìîóãîëüíèêîâ �1 è �2 . Ïîñêîëüêó
M M M d( ) ( ) ( )� � �1 2 1 1
� � (2 5 6� � ) è M M M h( ) ( ) ( )� � �1 2 1 1
� �
( , )1 2 5 3� � , âûïîëíÿåòñÿ ñèñòåìà ñîîòíîøåíèé
� � �
� � �
1 2 1 1
1 2 1 1
� �
� �
�
�
�
�
�
d
h
,
,
ò.å. â ñîîòâåòñòâèè ñ îïðåäåëåíèåì 5 ïðÿìîóãîëüíèêè �1 è �2 ïåðåñåêàþòñÿ.
Ïðÿìîóãîëüíèêè �2 è �3 òàêæå ïåðåñåêàþòñÿ, ïîñêîëüêó âûïîëíÿåòñÿ ñèñ-
òåìà íåðàâåíñòâ
M M M d
M M M h
( ) ( ) ( ),
( ) ( ) ( ),
� � �
� � �
2 3 2 2
3 2 3 3
� �
� �
�
�
�
� � �
� � �
2 3 2 2
3 2 3 3
� �
� �
�
�
�
�
�
d
h
,
.
Ïðÿìîóãîëüíèêè �1 è �3 íå ïåðåñåêàþòñÿ (ðèñ. 1), òàê êàê âûïîëíÿåòñÿ
ïåðâîå èç ñîîòíîøåíèé ñîâîêóïíîñòè èç îïðåäåëåíèÿ 6: � �1 1 3� d �
( ( )M d�1 1 6� � , M ( ) ,�3 8 5� ).
Çàìå÷àíèå 2.  ïðèìåðå 2 äëÿ ïðîñòîòû ãåîìåòðè÷åñêîé èíòåðïðåòàöèè ïî-
äîáðàíû òàêèå ñëó÷àéíûå âåëè÷èíû, ÷òî äëÿ èõ óïîðÿäî÷åíèÿ äîñòàòî÷íî ñðàâ-
íåíèÿ ìàòåìàòè÷åñêèõ îæèäàíèé, ÷òî â îáùåì ñëó÷àå ìîæåò íå èìåòü ìåñòà.
Îïðåäåëåíèå 7. Ïðÿìîóãîëüíèêè �( , , , )� � h d è � � � � �� ( , , , )� � h d íàçîâåì êà-
ñàþùèìèñÿ, åñëè âûïîëíÿåòñÿ ïî êðàéíåé ìåðå îäíà èç ñèñòåì ñîîòíîøåíèé
� �
� � �
� � �
� �
�
�
�
d
h
,
,� �
� �
� � �
� � �
� � � �
�
�
�
d
h
,
,� �
� � �
� �
� �� �
� � �
�
�
�
d
h
,
,
� � �
� �
� �� �
� � � �
�
�
�
d
h
,
.
106 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 4
x2
1 x1
0
�1
�2 �3
M(�1)
M(�1)
M(�1+d1)
M(�1+ h1)
M(�2)
M(�2) M(�3)
M(�3+ h3)
10
5
Ðèñ. 1
Ïðèìåð 3. Ïóñòü ïðÿìîóãîëüíèêè �1 1 1 1 1( , , , )� � h d , �2 2 2 2 2( , , , )� � h d ,
�3 3 3 3 3( , , , )� � h d è �4 4 4 4 4( , , , )� � h d â ïîëóáåñêîíå÷íîé ïîëîñå øèðèíîé
h0 6� îïðåäåëÿþòñÿ ðÿäàìè ðàñïðåäåëåíèÿ ïàðàìåòðîâ â ñîîòâåòñòâèè ñ òàáë. 2.
Ïîêàæåì, ÷òî ïðÿìîóãîëüíèêè �1 è �2 , �1 è �3 , �2 è �4 , �3 è �4 êàñà-
þòñÿ îäèí äðóãîãî. Ðàññìîòðèì ñíà÷àëà ïðÿìîóãîëüíèêè �1 è �2 . Òàê êàê
M ( )�1 1� , M ( )�2 4� , M d( ) ,1 3 2� , äëÿ ìàòåìàòè÷åñêèõ îæèäàíèé âåëè÷èí �1,
�2 , �1 1� d âûïîëíÿåòñÿ äâîéíîå íåðàâåíñòâî M M M d( ) ( ) ( )� � �1 2 1 1
� � . Ñëå-
äîâàòåëüíî, èìååò ìåñòî ñîîòíîøåíèå � � �1 2 1 1� � � d . Â òî æå âðåìÿ
� �2 2 1� �h , ïîñêîëüêó ðÿä ðàñïðåäåëåíèÿ � 2 2� h èìååò ñëåäóþùèé âèä:
Òàêèì îáðàçîì, âûïîëíÿåòñÿ ÷åòâåðòàÿ ñèñòåìà èç îïðåäåëåíèÿ 7.
Ðàññìîòðèì ïðÿìîóãîëüíèêè �1 è �3 . Òàê êàê M ( ) ,�3 1 9� , àíàëîãè÷íî
ïðåäûäóùåìó ñëó÷àþ èìååò ìåñòî ñîîòíîøåíèå � � �1 3 1 1� � � d . Ïðè ýòîì, êàê
ëåãêî âèäåòü, � �1 1 3� �h , ñëåäîâàòåëüíî, âûïîëíÿåòñÿ òðåòüÿ ñèñòåìà èç îïðåäå-
ëåíèÿ 7.
Äëÿ ïðÿìîóãîëüíèêîâ �2 è �4 èìåþò ìåñòî ñîîòíîøåíèÿ � �2 2 4� �d è
� � �2 4 2 2� � � h (ïîñëåäíåå ñëåäóåò èç òîãî, ÷òî M ( )� 2 1� , M ( )� 4 2� ,
M h( ) ,2 1 5� , èíà÷å M M M h( ) ( ) ( )� � �2 4 2 2
� � ), ò.å. èìååò ìåñòî ïåðâàÿ ñèñ-
òåìà èç îïðåäåëåíèÿ 7.
Ðàññìîòðèì ðàçìåùåíèå ïðÿìîóãîëüíèêîâ �3 è �4 . Çàïèøåì âîçìîæíûå
çíà÷åíèÿ è ñîîòâåòñòâóþùèå âåðîÿòíîñòè äëÿ âåëè÷èíû �3 3� d :
Òàêèì îáðàçîì, � �3 3 4� �d . Ñëó÷àéíàÿ âåëè÷èíà � 4 ïðåäøåñòâóåò ñëó÷àéíîé
âåëè÷èíå � 3 , òàê êàê M M( ) ( )� �4 32 5� � � . Îïðåäåëèì ñîîòíîøåíèå âåëè÷èí � 3
è � 4 4� h . Ïîñêîëüêó M M h( ) ( )� �3 4 4 5� � � , íî D D h( ) , ( ) ,� �3 4 44 25 26 5� � � � ,
ïîëó÷àåì � �4 4 3� h � . Ñëåäîâàòåëüíî, èìååò ìåñòî âòîðàÿ ñèñòåìà èç îïðåäåëå-
íèÿ 7 (ðèñ. 2).
Çàìå÷àíèå 3. Êàê è â ïðèìåðå 2, ñëó÷àéíûå âåëè÷èíû ïîäîáðàíû òàêèì
îáðàçîì, ÷òî äëÿ èõ óïîðÿäî÷åíèÿ äîñòàòî÷íî ñðàâíåíèÿ ìàòåìàòè÷åñêèõ îæè-
äàíèé.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 4 107
Ò à á ë è ö à 2
Ïàðàìåòðû
Ðÿäû ðàñïðåäåëåíèÿ ïàðàìåòðîâ ïðÿìîóãîëüíèêîâ
�1 �2 �3 �4
Çíà÷åíèÿ � i 0,5 3 1 4 7 1 4 3 6 9
Âåðîÿòíîñòè
çíà÷åíèé � i
0,8 0,2 0,21 0,58 0,21 0,7 0,3 0,21 0,58 0,21
Çíà÷åíèÿ � i 1 2 6 7 0,5 1,5 3,5 4,5 8,5 9,5 1 3,5
Âåðîÿòíîñòè
çíà÷åíèé � i
0,4 0,4 0,1 0,1 0,5 0,5 0,4 0,4 0,1 0,1 0,6 0,4
Çíà÷åíèÿ hi 2,5 0,5 5,5 0,5 3 0,5 13
Âåðîÿòíîñòè
çíà÷åíèé hi
1 0,8 0,2 0,8 0,2 0,8 0,2
Çíà÷åíèÿ di 2 4 2 2 5 2 4
Âåðîÿòíîñòè
çíà÷åíèé di
0,4 0,6 1 0,3 0,7 0,8 0,2
� çíà÷åíèÿ 0,5�0,5 1,5�0,5 0,5�5,5 1,5�5,5
� âåðîÿòíîñòè 0 5 0 8, ,� 0 5 0 8, ,� 0 5 0 2, ,� 0 5 0 2, , .�
� çíà÷åíèÿ 1 2� 1 5 4 2� � � 4 5�
� âåðîÿòíîñòè 0 7 0 3, ,� 0 7 0 7 0 3 0 3, , , ,� � � 0 3 0 7, ,� .
ÌÀÒÅÌÀÒÈ×ÅÑÊÀß ÌÎÄÅËÜ ÇÀÄÀ×È ÓÏÀÊÎÂÊÈ ÏÐßÌÎÓÃÎËÜÍÈÊÎÂ
ÑÎ ÑÒÎÕÀÑÒÈ×ÅÑÊÈÌÈ ÏÀÐÀÌÅÒÐÀÌÈ
Èñïîëüçóÿ ââåäåííûå ïîíÿòèÿ, ïîñòðîèì ìàòåìàòè÷åñêóþ ìîäåëü çàäà÷è óïà-
êîâêè ïðÿìîóãîëüíèêîâ â ñëó÷àå, êîãäà ðàçìåðû ïîëîñîê è ïðÿìîóãîëüíèêîâ
h0 , a a p1, ... , ÿâëÿþòñÿ äèñêðåòíûìè ñëó÷àéíûìè âåëè÷èíàìè.
Ïóñòü êîëè÷åñòâî ïîëîñîê, íà êîòîðûå ïîäåëåíà çàäàííàÿ ïîëóáåñêîíå÷íàÿ
ïîëîñà, ðàâíî m. Òîãäà â îïòèìàëüíîì ðåøåíèè â êàæäîé ïîëîñêå ðàñïîëîæåíî
îò 1 äî p m� �( )1 ïðÿìîóãîëüíèêîâ. Îáîçíà÷èì n p m� � �1 è ââåäåì â ðàññìîò-
ðåíèå mn p� ïðÿìîóãîëüíèêîâ øèðèíîé h0 è äëèíîé a0 0� . Åñëè â íåêîòîðîé
ïîëîñêå íàõîäèòñÿ ìåíüøå, ÷åì n ïðÿìîóãîëüíèêîâ, òî ðàçìåñòèì â íåé ñòîëüêî
ïðÿìîóãîëüíèêîâ äëèíîé a0 , ÷òîáû èõ îáùåå êîëè÷åñòâî â ïîëîñêå ðàâíÿëîñü n.
Òàêèì îáðàçîì, ìîæíî ñ÷èòàòü, ÷òî â êàæäîé ïîëîñêå íàõîäèòñÿ ðîâíî n ïðÿìî-
óãîëüíèêîâ.
Ïóñòü íà÷àëî ñèñòåìû êîîðäèíàò ñîâïàäàåò ñ ëåâûì íèæíèì óãëîì ïîëîñû,
� ij ij ij ij ijh x( , , , )� � — ïðÿìîóãîëüíèê, ðàçìåùåííûé â i-é ïîëîñêå ( i Jm� ) íà j-ì
( )j Jn� îò íà÷àëà ïîëîñû ìåñòå (íàïîìíèì, ÷òî Js îáîçíà÷åíî ìíîæåñòâî s ïåð-
âûõ íàòóðàëüíûõ ÷èñåë). Òàê êàê âñå ïîëîñêè è ïðÿìîóãîëüíèêè îäèíàêîâîé øè-
ðèíû h0 , èìååì h hij � 0 , � ij i h� �( )1 0 � �i Jm , j Jn� (ïðè ýòîì ïðÿìîóãîëüíèêè,
ðàçìåùåííûå â ðàçíûõ ïîëîñêàõ, ëèáî íå ïåðåñåêàþòñÿ, ëèáî êàñàþòñÿ îäèí äðó-
ãîãî). Çäåñü ïîä ïðîèçâåäåíèåì ih0 ïîíèìàåì ñëó÷àéíóþ âåëè÷èíó, âîçìîæíûå
çíà÷åíèÿ êîòîðîé ðàâíû ïðîèçâåäåíèþ âîçìîæíûõ çíà÷åíèé âåëè÷èíû h0 íà
÷èñëî i, à âåðîÿòíîñòè — ñîîòâåòñòâóþùèì âåðîÿòíîñòÿì âåëè÷èíû h0 .
Êàê îòìå÷àëîñü, â îïòèìàëüíîì ðåøåíèè ïðÿìîóãîëüíèêè äîëæíû ðàçìå-
ùàòüñÿ òàê, ÷òîáû êàæäûé ñëåäóþùèé êàñàëñÿ ïðåäûäóùåãî. Èç óñëîâèÿ êàñà-
íèÿ ñîñåäíèõ ïðÿìîóãîëüíèêîâ ïîëó÷àåì � �i j ij ijx, � � �1 � �i Jm , � � �j Jn 1.
Êðîìå òîãî, � i0 0� � �i Jm . Òàêèì îáðàçîì, äëèíà çàíÿòîé ÷àñòè i-é ïîëîñêè ðàâ-
íà xij
j
n
�
1
, à äëèíà çàíÿòîé ÷àñòè ïîëîñû â öåëîì îïðåäåëÿåòñÿ êàê max
1 1
�
i m
ij
j
n
x .
Äëÿ ôîðìàëèçàöèè îãðàíè÷åíèé íà âîçìîæíûå äëèíû ïðÿìîóãîëüíèêîâ ðàñ-
ñìîòðèì ìóëüòèìíîæåñòâî G a a a a
mn p
p�
�
{ }0 0 1, ..., , , ,
� �� ��
� è âåêòîð
x x x x x xn m mn� ( , , , , , , )11 1 21 1� � . (4)
Òîãäà êàæäîìó ðàñïîëîæåíèþ ïðÿìîóãîëüíèêîâ â ïîëîñå âçàèìíî îäíîçíà÷íî
ñîîòâåòñòâóåò âåêòîð x, êîòîðûé ìîæíî ðàññìàòðèâàòü êàê ýëåìåíò ìíîæåñòâà
ïåðåñòàíîâîê E Gk ( ) ( )k mn� èç ýëåìåíòîâ ìóëüòèìíîæåñòâà G, ò.å. x E Gk� ( ).
108 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 4
x2
3 x10
�1
�2
�3
M(�1)
M(�2)
M(�4+ d4)
M(�1)
M(�2) M(�4)
M(�3)
10
6
�4
Ðèñ. 2
Ìàòåìàòè÷åñêóþ ìîäåëü ñôîðìóëèðîâàííîé çàäà÷è óïàêîâêè ïðÿìîóãîëü-
íèêîâ, ðàçìåðû êîòîðûõ ÿâëÿþòñÿ äèñêðåòíûìè ñëó÷àéíûìè âåëè÷èíàìè, ìîæ-
íî çàïèñàòü ñëåäóþùèì îáðàçîì: íàéòè ïàðó � �F x x( ),* * òàêóþ, ÷òî
F x x
x E G i m
ij
j
n
k
( ) min max*
( )
�
�
�
1 1
, x x
x E G i m
ij
j
n
k
*
( )
min max�
�
�
arg
1 1
.
Äëÿ èëëþñòðàöèè ìîäåëè ðàññìîòðèì ïðèìåð.
Ïðèìåð 4. Ïóñòü çàäàíû m � 2 ïîëîñêè è p � 4 ïðÿìîóãîëüíèêà, ñðåäè êîòî-
ðûõ îäèí äëèíîé a1, äâà — äëèíîé a2 è îäèí — äëèíîé a3 . Ðàñïðåäåëåíèÿ íåçà-
âèñèìûõ äèñêðåòíûõ ñëó÷àéíûõ âåëè÷èí çàäàíû â ñîîòâåòñòâèè ñ òàáë. 3. (×èñ-
ëîâûå õàðàêòåðèñòèêè âåëè÷èí a1, a2 , a3 ðàâíû M a( )1 3� , M a M a( ) ( )2 3 4� � ,
D a( )1 2� , D a( ) ,2 1 2� , D a( ) . )3 4�
Ðàññìîòðèì ðåøåíèå äàííîé çàäà÷è ìåòîäîì ïîëíîãî ïåðåáîðà.  îïòèìàëü-
íîì ðåøåíèè â êàæäîé èç äâóõ ïîëîñîê ìîæåò ðàñïîëàãàòüñÿ îäèí, äâà èëè òðè
ïðÿìîóãîëüíèêà, ò.å. n p m� � � �1 3. ×òîáû â êàæäîé ïîëîñå ðàçìåùàëîñü ðîâíî
òðè ïðÿìîóãîëüíèêà, íåîáõîäèìî ââåñòè â ðàññìîòðåíèå mn p� � 2 ïðÿìîóãîëüíè-
êà äëèíîé a0 0� . Òàêèì îáðàçîì, ìóëüòèìíîæåñòâî G a a a a a a� { }0 0 1 2 2 3, , , , , .
Ìíîæåñòâî ïåðåñòàíîâîê E Gk ( ) èç ìóëüòèìíîæåñòâà G èìååò âèä
E G E G a a a a a a a a a a a a a a a a a ak ( ) ( ) , ,� �6 1 2 2 3 0 0 2 1 2 3 0 0 0 2 0 1 3{ 2 , ... }.
Ðàñïîëîæèì â ïåðâîé ïîëîñêå ïðÿìîóãîëüíèêè ñ äëèíàìè a1, a2 , a2 , âî âòî-
ðîé — a3 , a0 , a0 . Â çàâèñèìîñòè îò âçàèìíîãî ðàñïîëîæåíèÿ ïðÿìîóãîëüíèêîâ
â êàæäîé ïîëîñêå ïîëó÷èì ñîîòâåòñòâóþùèå âåêòîðû âèäà (4) — ýëåìåíòû
ìíîæåñòâà E Gk ( ):
( , , , , , )a a a a a a1 2 2 3 0 0 , ( , , , , , )a a a a a a2 1 2 3 0 0 , ( , , , , , )a a a a a a2 2 1 3 0 0 ,
( , , , , , )a a a a a a1 2 2 0 3 0 , ( , , , , , )a a a a a a2 1 2 0 3 0 , ( , , , , , )a a a a a a2 2 1 0 3 0 ,
( , , , , , )a a a a a a1 2 2 0 0 3 , ( , , , , , )a a a a a a2 1 2 0 0 3 , ( , , , , , )a a a a a a2 2 1 0 0 3 .
Äëÿ êàæäîãî âåêòîðà ñóììû âèäà xij
j�
1
3
ïðè i �1è i � 2 ñîîòâåòñòâåííî ðàâíû
a a a1 2 2� � è a3 . Òàêèì îáðàçîì, äëÿ ïåðå÷èñëåííûõ âåêòîðîâ F F x1 � �( )
� � �max ,{ }a a a a1 2 2 3 . Ïîñêîëüêó M a a a M a M a M a( ) ( ) ( ) ( )1 2 2 1 2 2� � � � � �
� � � �3 4 4 11, M a M a a a( ) ( )3 1 2 24� � � � , èìååì a a a a3 1 2 2� � � , ò .å .
F F x a a a1 1 2 2� � � �( ) .
 ñëó÷àå, êîãäà â ïåðâîé ïîëîñêå ðàñïîëàãàþòñÿ ïðÿìîóãîëüíèêè äëèíîé a1,
a2 , a3 , à âî âòîðîé — a2 , a0 , a0 , ïîëó÷àåì F F x a a a a2 1 2 3 2� � � �( ) max ,{ }.
Òàê êàê M a a a M a( ) ( )1 2 3 211 4� � � � , èìååì a a a a2 1 2 3� � � è
F x a a a( ) � � �1 2 3 .
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 4 109
Ò à á ë è ö à 3
Âåëè÷èíû
Ðÿäû ðàñïðåäåëåíèÿ äëèíû ïðÿìîóãîëüíèêîâ
i � 1 i � 2 i � 3
Çíà÷åíèÿ ai 2 5 3 4 6 3 8
Âåðîÿòíîñòè
çíà÷åíèé ai
2
3
1
3
2
5
2
5
1
5
4
5
1
5
Ðàñïîëîæèâ â ïåðâîé ïîëîñêå ïðÿìîóãîëüíèêè äëèíîé a2 , a2 , a3 , âî âòî-
ðîé — a1, a0 , a0 , ïîëó÷èì F F x a a a a a a a3 2 2 3 1 2 2 3� � � � � � �( ) max ,{ }
(a a a a1 2 2 3� � � , ïîñêîëüêó M a a a M a( ) ( )2 2 3 112 3� � � � ).
Èòàê, ðàññìîòðåíû âñå ñëó÷àè, êîãäà â ïåðâîé ïîëîñêå ðàçìåùåíû òðè èç
ïåðâîíà÷àëüíî çàäàííûõ ïðÿìîóãîëüíèêîâ, à âî âòîðîé — îäèí. Ïóñòü â êàæäîé
ïîëîñêå íàõîäèòñÿ ïî äâà èç ïåðâîíà÷àëüíî çàäàííûõ ïðÿìîóãîëüíèêîâ:
� â ïåðâîé ïîëîñêå ðàñïîëàãàþòñÿ ïðÿìîóãîëüíèêè äëèíîé a1 è a2 , à âî âòî-
ðîé — a2 è a3 : F F x a a a a a a4 1 2 2 3 2 3� � � � � �( ) max ,{ } ( ( )M a a1 2 7� � ,
M a a( )2 3 8� � );
� â ïåðâîé ïîëîñêå ðàñïîëàãàþòñÿ ïðÿìîóãîëüíèêè äëèíîé a1 è a3 , âî âòî-
ðîé — a2 è a2 : F F x a a a a a a5 1 3 2 2 2 2� � � � � �( ) max ,{ } ( ( )M a a1 3 7� � ,
M a a( )2 2 8� � ).
Îñòàâøèåñÿ ïåðåñòàíîâêè èç ìíîæåñòâà E Gk ( ) ñîîòâåòñòâóþò òåì ðàñïîëî-
æåíèÿì ïðÿìîóãîëüíèêîâ, êîòîðûå ïîëó÷àþòñÿ èç óæå ðàññìîòðåííûõ, åñëè ïî-
ìåíÿòü ìåñòàìè ïåðâóþ è âòîðóþ ïîëîñêè. Î÷åâèäíî, ÷òî çíà÷åíèÿ öåëåâîé
ôóíêöèè ïðè ýòîì íå èçìåíÿòñÿ. Îïòèìàëüíîå çíà÷åíèå öåëåâîé ôóíêöèè
F x F F F F F( ) min , , , ,* � { }1 2 3 4 5 . Äëÿ ìàòåìàòè÷åñêèõ îæèäàíèé óêàçàííûõ
ñëó÷àéíûõ âåëè÷èí âûïîëíÿþòñÿ ñîîòíîøåíèÿ
M F M F M F M F M F( ) ( ) ( ) ( ) ( )3 1 2 4 5 � � .
Òàêèì îáðàçîì, âåëè÷èíû F1, F2 , F3 íå ÿâëÿþòñÿ îïòèìóìîì çàäà÷è. Ðàññìîò-
ðèì âåëè÷èíû F4 è F5 , äëÿ êîòîðûõ
D F D a D a( ) ( ) ( ) , ,4 2 3 1 2 4 5 2� � � � � ;
D F D a D a( ) ( ) ( ) , , ,5 2 2 1 2 12 2 4� � � � � .
Ïîñêîëüêó D F D F( ) ( )4 5 , â ñîîòâåòñòâèè ñ óñëîâèåì 2 îïðåäåëåíèÿ 1 èìååì
F F4 5� . Ñëåäîâàòåëüíî, F x a a( )* � �2 3 , à îäíà èç òî÷åê, äîñòàâëÿþùèõ
îïòèìàëüíîå çíà÷åíèå öåëåâîé ôóíêöèè, èìååò âèä x a a a a a a* ( , , , , , )� 2 3 0 1 2 0 .
Ïðèâåäåì îäíó èç ñîäåðæàòåëüíûõ èíòåðïðåòàöèé çàäà÷è. Ïóñòü èìååòñÿ m
îäíîòèïíûõ óñòðîéñòâ, íà êîòîðûõ íóæíî îáðàáîòàòü p çàÿâîê. Âðåìÿ îáñëóæèâà-
íèÿ êàæäîé çàÿâêè — äèñêðåòíàÿ ñëó÷àéíàÿ âåëè÷èíà ñ èçâåñòíûì ðÿäîì ðàñïðå-
äåëåíèÿ. Íåîáõîäèìî ðàçìåñòèòü çàÿâêè ïî óñòðîéñòâàì òàêèì îáðàçîì, ÷òîáû
âðåìÿ îáñëóæèâàíèÿ âñåõ çàÿâîê áûëî íàèìåíüøèì (ïðè ñðàâíåíèè ñëó÷àéíûõ âå-
ëè÷èí èñïîëüçóåòñÿ ïîäõîä, ïðåäëîæåííûé â îïðåäåëåíèè 2: äëÿ îïòèìàëüíîãî
ðåøåíèÿ ìàòåìàòè÷åñêîå îæèäàíèå ÿâëÿåòñÿ íàèìåíüøèì, ïðè ðàâíûõ ìàòåìàòè-
÷åñêèõ îæèäàíèÿõ âûáèðàåòñÿ âåëè÷èíà ñ áîëüøåé äèñïåðñèåé è ò.ä.).
Äàííóþ çàäà÷ó ìîæíî ðàññìàòðèâàòü êàê çàäà÷ó óïàêîâêè ïðÿìîóãîëüíè-
êîâ, åñëè ñ÷èòàòü, ÷òî ïîëîñêè äëÿ óïàêîâêè ñîîòâåòñòâóþò îáñëóæèâàþùèì
óñòðîéñòâàì, äëèíà ïðÿìîóãîëüíèêà ñîîòâåòñòâóåò âðåìåíè îáñëóæèâàíèÿ çàÿâ-
êè.  ýòîì ñëó÷àå âðåìÿ îáñëóæèâàíèÿ çàÿâîê îïðåäåëåííûì óñòðîéñòâîì âûðà-
æàåòñÿ êàê äëèíà çàíÿòîé ÷àñòè ïîëîñêè, à âðåìÿ îáñëóæèâàíèÿ âñåõ çàÿâîê —
ìàêñèìàëüíàÿ èç ýòèõ âåëè÷èí.
ÇÀÊËÞ×ÅÍÈÅ
Ïðåäëîæåíà êîìáèíàòîðíàÿ ìàòåìàòè÷åñêàÿ ìîäåëü çàäà÷è îïòèìàëüíîé óïà-
êîâêè ïðÿìîóãîëüíèêîâ â ñëó÷àå, êîãäà ïàðàìåòðû ÿâëÿþòñÿ äèñêðåòíûìè
ñëó÷àéíûìè âåëè÷èíàìè. Ôîðìàëèçàöèÿ ïîíÿòèé âçàèìíîãî ðàñïîëîæåíèÿ
ïðÿìîóãîëüíèêîâ îñóùåñòâëåíà íà îñíîâå ââåäåíèÿ ëèíåéíîãî ïîðÿäêà íà
ìíîæåñòâå äèñêðåòíûõ ñëó÷àéíûõ âåëè÷èí. Êàê íàïðàâëåíèå äàëüíåéøèõ èñ-
ñëåäîâàíèé ìîæíî îòìåòèòü ðàçðàáîòêó ìåòîäîâ ðåøåíèÿ ñôîðìóëèðîâàííîé
çàäà÷è, â ÷àñòíîñòè ðàçâèòèå ìåòîäà âåòâåé è ãðàíèö.
110 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 4
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. Ñ å ð ã è å í ê î È .  . , Ï à ð à ñ þ ê È . Í . , Ê à ñ ï ø è ö ê à ÿ Ì . Ô . Îá îäíîé íå÷åòêîé çàäà-
÷å ìíîãîïàðàìåòðè÷åñêîãî âûáîðà îïòèìàëüíûõ ðåøåíèé // Êèáåðíåòèêà è ñèñòåìíûé àíà-
ëèç. — 2003. — ¹ 2. — Ñ. 3–15.
2. Ñ å ð ã è å í ê î È .  . , Ì è õ à ë å â è ÷ Ì .  . Ïðèìåíåíèå ìåòîäîâ ñòîõàñòè÷åñêîé îïòèìèçà-
öèè äëÿ èññëåäîâàíèÿ òðàíñôîðìàöèîííûõ ïðîöåññîâ â ýêîíîìèêå // Ñèñòåìí³ äîñë³äæåííÿ òà
³íôîðìàö³éí³ òåõíîëî㳿. — 2004. — ¹ 4. — Ñ. 7–29.
3. Ã ð å á å í í è ê È . Â . Èíòåðâàëüíûå ìîäåëè êîìáèíàòîðíîé îïòèìèçàöèè êâàçèëèíåéíûõ
ôóíêöèé â ïðîñòðàíñòâå I Rs
n // Äîï. ÍÀÍÓ. — 2004. — ¹ 9. — Ñ. 60–64.
4. Ñ å ð à ÿ Î .  . Íå÷åòêàÿ çàäà÷à êîììèâîÿæåðà // Ìàòåìàòè÷åñêîå ìîäåëèðîâàíèå. — 2007. —
¹ 2(17). — Ñ. 13–15.
5. Ñ å ð ã è å í ê î È .  . , Å ì å ö Î . À . , Å ì å ö À . Î . Çàäà÷è îïòèìèçàöèè ñ èíòåðâàëüíîé íå-
îïðåäåëåííîñòüþ: ìåòîä âåòâåé è ãðàíèö // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 2013. — ¹ 5.
— Ñ. 38–50.
6. ª ì å ö ü Î . Î . , ª ì å ö ü Î ë - ð à Î . Ðîçâ’ÿçóâàííÿ çàäà÷ êîìá³íàòîðíî¿ îïòèì³çàö³¿ íà íå-
÷³òêèõ ìíîæèíàõ. — Ïîëòàâà: ÏÓÅÒ, 2011. — 239 ñ. — http://dspace.puet.edu.ua/handle/
123456789/352.
7. ª ì å ö ü Î . Î . , ª ì å ö ü Î ë - ð à Î . Ïîáóäîâà ìàòåìàòè÷íî¿ ìîäåë³ îäí³º¿ êîìá³íàòîðíî¿ çà-
äà÷³ óïàêóâàííÿ ïðÿìîêóòíèê³â ç íå÷³òêèìè ðîçì³ðàìè // Íàóê. â³ñò³ ÍÒÓÓ «Êϲ». — 2008. —
¹ 6. — Ñ. 25–33.
8. Å ì å ö Î . À . , Å â ñ å å â à Ë . à . , Ð î ì à í î â à Í . à . Èíòåðâàëüíàÿ ìàòåìàòè÷åñêàÿ ìîäåëü
êîìáèíàòîðíîé çàäà÷è öâåòíîé óïàêîâêè ïðÿìîóãîëüíèêîâ // Êèáåðíåòèêà è ñèñòåìíûé àíà-
ëèç. — 2001. — ¹ 3. — Ñ. 131–138.
9. Å ì å ö Î . À . , Å â ñ å å â à Ë . à . , Ð î ì à í î â à Í . à . Çàäà÷à öâåòíîé óïàêîâêè ïðÿìîóãîëü-
íèêîâ ñ ó÷åòîì ïîãðåøíîñòåé èñõîäíûõ äàííûõ è åå ðåøåíèå // Ýêîíîìèêà è ìàò. ìåòîäû. —
2000. — 36, ¹ 3. — Ñ. 149–152.
10. Å ì å ö Î . À . , Ð î ñ ê ë à ä ê à À . À . Î êîìáèíàòîðíîé îïòèìèçàöèè â óñëîâèÿõ íåîïðåäåëåí-
íîñòè // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 2008. — ¹ 5. — Ñ. 35–44.
11. C ò î ÿ í Þ . à . , ª ì å ö ü Î . Î . Òåîð³ÿ ³ ìåòîäè åâêë³äîâî¿ êîìá³íàòîðíî¿ îïòèì³çàö³¿. — Ê.:
²í-ò ñèñòåìíèõ äîñë³äæåíü îñâ³òè, 1993. — 188 ñ. — http://dspace.puet.edu.ua/handle/
123456789/487.
12. Ñ ò î ÿ í Þ . à . , ª ì å ö ü Î . Î . , ª ì å ö ü ª . Ì . Îïòèì³çàö³ÿ íà ïîë³ðîçì³ùåííÿõ: òåîð³ÿ òà
ìåòîäè. — Ïîëòàâà: ÐÂÖ ÏÓÑÊÓ, 2005. — 103 ñ. — http://dspace.puet.edu.ua/handle/
123456789/376.
13. Á à ð á î ë ³ í à Ò . Ì . , ª ì å ö ü Î . Î . Ìîìåíòè, ïîðÿäîê, îïòèì³çàö³ÿ äëÿ âèïàäêîâèõ âåëè-
÷èí // ²íôîðìàòèêà òà ñèñòåìí³ íàóêè (²ÑÍ-2014): Ìàòåð³àëè V Âñåóêð. íàóê.-ïðàêò. êîíô.
(ì. Ïîëòàâà, 13–15 áåðåçíÿ 2014 ðîêó) / Çà ðåä. Î.Î. ªìöÿ. — Ïîëòàâà : ÏÓÅÒ, 2014. —
Ñ. 40–43. — http://dspace.puet.edu.ua/handle/123456789/1942.
14. Å ì å ö Î . À . , Á à ð á î ë è í à Ò . Í . Îá óïîðÿäî÷èâàíèè äèñêðåòíûõ ñëó÷àéíûõ âåëè÷èí //
Ìàòåìàòè÷åñêîå ìîäåëèðîâàíèå, îïòèìèçàöèÿ è èíôîðìàöèîííûå òåõíîëîãèè: Materiale Conf.
Intern. 25–28 mar. 2014, Chisin
�
au / Red. resp.: Dumitru Solomon. — Chisin
�
au: Evrica, 2014. — 2.
— P. 171–175.
15. Î á ù à ÿ àëãåáðà / Î.Â. Ìåëüíèêîâ, Â.Í. Ðåìåñëåííèêîâ, Â.À. Ðîìàíüêîâ è äð.; Ïîä îáù. ðåä.
Ë.À. Ñêîðíÿêîâà. — Ì.: Íàóêà. Ãë. ðåä. ôèç.-ìàò. ëèò., 1990. — Ò. 1. — 592 ñ.
16. Â å í ò ö å ë ü Å . Ñ. Òåîðèÿ âåðîÿòíîñòåé. — Ì.: Ãë. ðåä. ôèç.-ìàò. ëèò., 1969. — 576 ñ.
Ïîñòóïèëà 07.07.2014
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 4 111
|
| id | nasplib_isofts_kiev_ua-123456789-124841 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0023-1274 |
| language | Russian |
| last_indexed | 2025-11-29T11:59:02Z |
| publishDate | 2015 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Емец, О.А. Барболина, Т.Н. 2017-10-06T19:11:34Z 2017-10-06T19:11:34Z 2015 Комбинаторная оптимизационная модель упаковки прямоугольников со стохастическими параметрами / О.А. Емец, Т.Н. Барболина // Кибернетика и системный анализ. — 2015. — Т. 51, № 4. — С. 99-111. — Бібліогр.: 15 назв. — рос. 0023-1274 https://nasplib.isofts.kiev.ua/handle/123456789/124841 519.85 На основе введенного отношения порядка на множестве дискретных случайных величин формализованы понятия взаимного расположения в полосе прямоугольников со стохастическими параметрами: попадание в полосу, касание, пересечение, непересечение. Построена комбинаторная математическая модель задачи оптимальной упаковки прямоугольников для случая, когда входные данные являются дискретными случайными величинами. На основі введеного відношення порядку на множині дискретних випадкових величин формалізовано поняття взаємного розташування у смузі прямокутників зі стохастичними параметрами: потрапляння у смугу, дотик, перетин, неперетин. Побудовано комбінаторну математичну модель задачі оптимального пакування прямокутників для випадку, коли вхідні дані є дискретними випадковими величинами. Based on the relation of order on the set of discrete random variables, which is introduced in the paper, we formalize the arrangement of rectangles with stochastic parameters in a breadth: hit in a breadth, tangency, intersection, non-intersection. We also construct a combinatorial mathematical model of optimal rectangle packing when data are discrete random variables ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Системный анализ Комбинаторная оптимизационная модель упаковки прямоугольников со стохастическими параметрами Комбінаторна оптимізаційна модель пакування прямокутників зі стохастичними параметрами Combinanatorial optimization model of packing rectangles with stochastic parameters Article published earlier |
| spellingShingle | Комбинаторная оптимизационная модель упаковки прямоугольников со стохастическими параметрами Емец, О.А. Барболина, Т.Н. Системный анализ |
| title | Комбинаторная оптимизационная модель упаковки прямоугольников со стохастическими параметрами |
| title_alt | Комбінаторна оптимізаційна модель пакування прямокутників зі стохастичними параметрами Combinanatorial optimization model of packing rectangles with stochastic parameters |
| title_full | Комбинаторная оптимизационная модель упаковки прямоугольников со стохастическими параметрами |
| title_fullStr | Комбинаторная оптимизационная модель упаковки прямоугольников со стохастическими параметрами |
| title_full_unstemmed | Комбинаторная оптимизационная модель упаковки прямоугольников со стохастическими параметрами |
| title_short | Комбинаторная оптимизационная модель упаковки прямоугольников со стохастическими параметрами |
| title_sort | комбинаторная оптимизационная модель упаковки прямоугольников со стохастическими параметрами |
| topic | Системный анализ |
| topic_facet | Системный анализ |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/124841 |
| work_keys_str_mv | AT emecoa kombinatornaâoptimizacionnaâmodelʹupakovkiprâmougolʹnikovsostohastičeskimiparametrami AT barbolinatn kombinatornaâoptimizacionnaâmodelʹupakovkiprâmougolʹnikovsostohastičeskimiparametrami AT emecoa kombínatornaoptimízacíinamodelʹpakuvannâprâmokutnikívzístohastičnimiparametrami AT barbolinatn kombínatornaoptimízacíinamodelʹpakuvannâprâmokutnikívzístohastičnimiparametrami AT emecoa combinanatorialoptimizationmodelofpackingrectangleswithstochasticparameters AT barbolinatn combinanatorialoptimizationmodelofpackingrectangleswithstochasticparameters |