О сложности одной задачи оптимизации упаковок

Рассмотрена задача оптимизации упаковок элементов квадратной матрицы, заданных целыми положительными числами, в блоки фиксированного размера. Предложена постановка задачи и исследована трудоемкость полного перебора ее решений. Доказано, что задача является NP-полной, путем полиномиального сведения к...

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2016
Hauptverfasser:	Трофимчук, А.Н., Васянин, В.А., Кузьменко, В.Н.
Format:	Artikel
Sprache:	Russian
Veröffentlicht:	Інститут кібернетики ім. В.М. Глушкова НАН України 2016
Schriftenreihe:	Кибернетика и системный анализ
Schlagworte:	Системный анализ
Online Zugang:	http://dspace.nbuv.gov.ua/handle/123456789/131394
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:	О сложности одной задачи оптимизации упаковок / А.Н. Трофимчук, В.А. Васянин, В.Н. Кузьменко // Кибернетика и системный анализ. — 2016. — Т. 52, № 1. — С. 83-92. — Бібліогр.: 8 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-131394
record_format	dspace
spelling	irk-123456789-1313942018-03-22T03:03:02Z О сложности одной задачи оптимизации упаковок Трофимчук, А.Н. Васянин, В.А. Кузьменко, В.Н. Системный анализ Рассмотрена задача оптимизации упаковок элементов квадратной матрицы, заданных целыми положительными числами, в блоки фиксированного размера. Предложена постановка задачи и исследована трудоемкость полного перебора ее решений. Доказано, что задача является NP-полной, путем полиномиального сведения к ней NP-полной целочисленной задачи о многопродуктовом потоке минимальной стоимости. Розглянуто задачу оптимізації упакувань елементів квадратної матриці, заданих цілими позитивними числами, у блоки фіксованого розміру. Запропоновано постановку задачі та досліджено трудомісткість повного перебору її розв’язків. Доведено, що задача є NP-повною. Це зроблено шляхом поліноміального зведення до неї NP-повної цілочисельної задачі про багатопродуктовий потік мінімальної вартості. The authors consider the optimization of packing elements of a square matrix, which are given by positive integers, into blocks of fixed size. The problem is formulated and its combinatorial intractability is discussed. The problem is proved to be NP-complete. This is done by polynomial reduction of an NP-complete minimum-cost integer multicommodity flow problem to this problem. 2016 Article О сложности одной задачи оптимизации упаковок / А.Н. Трофимчук, В.А. Васянин, В.Н. Кузьменко // Кибернетика и системный анализ. — 2016. — Т. 52, № 1. — С. 83-92. — Бібліогр.: 8 назв. — рос. 0023-1274 http://dspace.nbuv.gov.ua/handle/123456789/131394 519.854.2:004.023 ru Кибернетика и системный анализ Інститут кібернетики ім. В.М. Глушкова НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
topic	Системный анализ Системный анализ
spellingShingle	Системный анализ Системный анализ Трофимчук, А.Н. Васянин, В.А. Кузьменко, В.Н. О сложности одной задачи оптимизации упаковок Кибернетика и системный анализ
description	Рассмотрена задача оптимизации упаковок элементов квадратной матрицы, заданных целыми положительными числами, в блоки фиксированного размера. Предложена постановка задачи и исследована трудоемкость полного перебора ее решений. Доказано, что задача является NP-полной, путем полиномиального сведения к ней NP-полной целочисленной задачи о многопродуктовом потоке минимальной стоимости.
format	Article
author	Трофимчук, А.Н. Васянин, В.А. Кузьменко, В.Н.
author_facet	Трофимчук, А.Н. Васянин, В.А. Кузьменко, В.Н.
author_sort	Трофимчук, А.Н.
title	О сложности одной задачи оптимизации упаковок
title_short	О сложности одной задачи оптимизации упаковок
title_full	О сложности одной задачи оптимизации упаковок
title_fullStr	О сложности одной задачи оптимизации упаковок
title_full_unstemmed	О сложности одной задачи оптимизации упаковок
title_sort	о сложности одной задачи оптимизации упаковок
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
publishDate	2016
topic_facet	Системный анализ
url	http://dspace.nbuv.gov.ua/handle/123456789/131394
citation_txt	О сложности одной задачи оптимизации упаковок / А.Н. Трофимчук, В.А. Васянин, В.Н. Кузьменко // Кибернетика и системный анализ. — 2016. — Т. 52, № 1. — С. 83-92. — Бібліогр.: 8 назв. — рос.
series	Кибернетика и системный анализ
work_keys_str_mv	AT trofimčukan osložnostiodnojzadačioptimizaciiupakovok AT vasâninva osložnostiodnojzadačioptimizaciiupakovok AT kuzʹmenkovn osložnostiodnojzadačioptimizaciiupakovok
first_indexed	2025-07-09T15:21:52Z
last_indexed	2025-07-09T15:21:52Z
_version_	1837183287277125632
fulltext	ÓÄÊ 519.854.2:004.023 À.Í. ÒÐÎÔÈÌ×ÓÊ, Â.À. ÂÀÑßÍÈÍ, Â.Í. ÊÓÇÜÌÅÍÊÎ Î ÑËÎÆÍÎÑÒÈ ÎÄÍÎÉ ÇÀÄÀ×È ÎÏÒÈÌÈÇÀÖÈÈ ÓÏÀÊÎÂÎÊ Àííîòàöèÿ. Ðàññìîòðåíà çàäà÷à îïòèìèçàöèè óïàêîâîê ýëåìåíòîâ êâàäðàòíîé ìàòðèöû, çàäàííûõ öåëûìè ïîëîæèòåëüíûìè ÷èñëàìè, â áëîêè ôèêñèðîâàííîãî ðàçìåðà. Ïðåäëî- æåíà ïîñòàíîâêà çàäà÷è è èññëåäîâàíà òðóäîåìêîñòü ïîëíîãî ïåðåáîðà åå ðåøåíèé. Äîêà- çàíî, ÷òî çàäà÷à ÿâëÿåòñÿ NP-ïîëíîé, ïóòåì ïîëèíîìèàëüíîãî ñâåäåíèÿ ê íåé NP-ïîëíîé öåëî÷èñëåííîé çàäà÷è î ìíîãîïðîäóêòîâîì ïîòîêå ìèíèìàëüíîé ñòîèìîñòè. Êëþ÷åâûå ñëîâà: îïòèìèçàöèÿ óïàêîâîê, öåëî÷èñëåííûé ìíîãîïðîäóêòîâûé ïîòîê, òðó- äîåìêîñòü ïîëíîãî ïåðåáîðà, ïîëèíîìèàëüíàÿ ñâîäèìîñòü, NP-ïîëíûå çàäà÷è. ÂÂÅÄÅÍÈÅ Ðàññìîòðåííàÿ äàëåå çàäà÷à îïòèìèçàöèè óïàêîâîê, â êîòîðîé ýëåìåíòû ñòðîê è ñòîëáöîâ êâàäðàòíîé ìàòðèöû, çàäàííûå öåëûìè ïîëîæèòåëüíûìè ÷èñëàìè, îïðåäåëåííûì îáðàçîì óïàêîâûâàþòñÿ â áëîêè ôèêñèðîâàííîãî ðàçìåðà, âîç- íèêàåò ïðè ôîðìàëèçàöèè è îïòèìèçàöèè ïðîöåññîâ ñîðòèðîâêè è óïàêîâêè ìåëêîïàðòèîííûõ êîððåñïîíäåíöèé (ãðóçîâ èëè ñîîáùåíèé) â òðàíñïîðòíûå áëîêè (ôèçè÷åñêèå èëè âèðòóàëüíûå êîíòåéíåðû) â òðàíñïîðòíûõ ñåòÿõ èëè â ñåòÿõ ïåðåäà÷è äàííûõ [1, 2]. Ñóòü ïðèêëàäíîé çàäà÷è çàêëþ÷àåòñÿ â íàõîæ- äåíèè ðàöèîíàëüíîé ñõåìû îáúåäèíåíèÿ èñõîäÿùèõ èç óçëîâ ñåòè ìåëêîïàð- òèîííûõ ïîòîêîâ îäíîðîäíûõ ãðóçîâ (ñîîáùåíèé) ñ ðàçëè÷íûìè àäðåñàìè íà- çíà÷åíèÿ è óïàêîâêè èõ â òðàíñïîðòíûå áëîêè (êîíòåéíåðû) çàäàííîãî ðàçìå- ðà â öåëÿõ ìèíèìèçàöèè êîëè÷åñòâà ïîñëåäíèõ äëÿ òðàíñïîðòèðîâêè ìåëêîïàðòèîííûõ êîððåñïîíäåíöèé âî âñåé ñåòè ïðè îïðåäåëåííûõ óñëîâèÿõ åå ôóíêöèîíèðîâàíèÿ. Â äàííîé ðàáîòå ðàññìàòðèâàåòñÿ ïîñòàíîâêà «÷èñòîé» çàäà÷è óïàêîâîê áåç ôóíêöèé çàòðàò, êîòîðûå ìîæíî ââåñòè äëÿ îöåíêè ñòîèìîñòè ïðîöåññîâ îáðà- áîòêè è òðàíñïîðòèðîâêè ìåëêîïàðòèîííûõ êîððåñïîíäåíöèé â ðåàëüíûõ ïðèëî- æåíèÿõ. Ïðè ýòîì äàííàÿ ïðèêëàäíàÿ çàäà÷à ñâîäèòñÿ ê çàäà÷å íàä ýëåìåíòàìè êâàäðàòíîé ìàòðèöû. Èññëåäóåòñÿ ïåðåáîðíàÿ ñëîæíîñòü çàäà÷è è äîêàçàíî, ÷òî îíà ÿâëÿåòñÿ NP-ïîëíîé. Ïðèâîäÿòñÿ äàííûå ýêñïåðèìåíòàëüíûõ èññëåäîâàíèé, ïîêàçûâàþùèå çàâèñèìîñòü ðåçóëüòàòîâ ðåøåíèÿ çàäà÷è îò ãðàíèö èçìåíåíèÿ çíà÷åíèé âõîäíûõ äàííûõ è ñõåì ïåðåáîðà âàðèàíòîâ ðåøåíèÿ. ÏÎÑÒÀÍÎÂÊÀ ÇÀÄÀ×È Çàäàíà ìàòðèöà A aij n n� �\| \| \| \| ñ öåëûìè ïîëîæèòåëüíûìè ýëåìåíòàìè âíå äèà- ãîíàëè è c íóëåâîé äèàãîíàëüþ. Íàä ýëåìåíòàìè ìàòðèöû ìîæíî âûïîëíÿòü íåêîòîðóþ îïåðàöèþ îáúåäèíåíèÿ, ñîáëþäàÿ îïðåäåëåííûå îãðàíè÷åíèÿ. Äëÿ âûïîëíåíèÿ îòäåëüíîé îïåðàöèè âûáèðàåòñÿ ýëåìåíò aij � 0 è íåïóñòîå ìíîæåñòâî íåïåðåñåêàþùèõñÿ èíäåêñîâ { }k k km1 2, , ,� , îòëè÷íûõ îò i è j (� m n mk � � �� 1 2 , n � 3). Â ðåçóëüòàòå ýëåìåíòû a a aik k k k jm1 1 2 , , ,� óâåëè÷èâàþòñÿ íà âåëè÷èíó aij è ýëåìåíò aij îáíóëÿåòñÿ. Êàæäûé ïðåîáðàçîâàííûé a aik k k1 1 2 , ,� �, ak jm èëè íåïðåîáðàçîâàííûé ýëåìåíò aij (êîãäà { , , , }k k km1 2 � ��) ðàç- ìåùàåòñÿ («óïàêîâûâàåòñÿ») â öåëîå êîëè÷åñòâî áëîêîâ ðàçìåðà � Z . Ïðè èçìåíåíèè ìàòðèöû èçìåíÿåòñÿ ñóììàðíîå êîëè÷åñòâî áëîêîâ, íåîáõîäèìûõ äëÿ ðàçìåùåíèÿ âñåõ ýëåìåíòîâ. Òðåáóåòñÿ íàéòè òàêóþ ïîñëåäîâàòåëüíîñòü îïåðàöèé îáúåäèíåíèÿ, ÷òîáû â ðåçóëüòàòå ïîëó÷èòü ìàòðèöó ñ ìèíèìàëüíûì ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 1 83 © À.Í. Òðîôèì÷óê, Â.À. Âàñÿíèí, Â.Í. Êóçüìåíêî, 2016 ÷èñëîì áëîêîâ. Ñîäåðæàòåëüíî èñõîäíàÿ ìàòðèöà A çàäàåò ïîòðåáíîñòè â òðàíñïîðòèðîâêå, à îïåðàöèÿ îáúåäèíåíèÿ îçíà÷àåò, ÷òî åñëè åñòü ïðÿìîé ïîòîê aij , òî åãî ìîæíî íàïðàâèòü ÷åðåç òðàíçèòíûå óçëû k k km1 2, , ,� , ñîîò- âåòñòâåííî èçìåíèâ ýëåìåíòû a a aik k k k jm1 1 2 , , ,� , aij . Ïðèâåäåì ôîðìàëüíóþ ïîñòàíîâêó çàäà÷è, ðàçäåëèâ èñõîäíîå ñîñòîÿíèå ìàòðèöû è èçìåíåííîå. Èìååòñÿ ìàòðèöà öåëî÷èñëåííûõ ïåðåìåííûõ X xij n n� �\| \| \| \| , íà÷àëüíûå çíà÷åíèÿ êîòîðîé ñîâïàäàþò ñî çíà÷åíèÿìè ìàòðèöû A. Òðåáóåòñÿ íàéòè ìèíèìóì ôóíêöèè � � � �� x x a a a ij j n i n ij ij rs ij / , ,* � 11 åñëè íåïîñðåäñòâåííî íå îáúåäèíÿëñÿ ñ äðóãèìè ýëåìåíòàìè,rs � � � � � 0 (1) i j n, , ,�1 ãäå � �x — íàèìåíüøåå öåëîå, áîëüøåå èëè ðàâíîå x, { }ars * — ìíîæåñòâî ýëå- ìåíòîâ (ìîæåò áûòü ïóñòûì), îáúåäèíåííûõ ñ aij . Óñëîâèÿ áàëàíñà èìåþò âèä x a x aij ij j n j n ji ji j n j n � � � �� 11 11 , i n�1, . (2) Îãðàíè÷åíèÿ íà âåëè÷èíó çíà÷åíèé xij îïðåäåëÿòñÿ òàê: x a ij ij � � � � � � � � �, i j n, ,�1 . (3) Îöåíèì òðóäîåìêîñòü ðåøåíèÿ ñôîðìóëèðîâàííîé çàäà÷è. Ïðè ïîñòðîåíèè àëãîðèòìà íóæíî ðåøèòü, êàê âûáèðàòü ýëåìåíòû xij è èíäåêñû { }k k km1 2, , ,� äëÿ âûïîëíåíèÿ îïåðàöèè îáúåäèíåíèÿ. Ïðè ðåøåíèè çàäà÷è (1)–(3) â ìàòðèöå X èìååòñÿ n n( )�1 âàðèàíòîâ âûáîðà ïåðâîãî ýëåìåíòà xij . ßñíî, ÷òî ïîñëå âûáî- ðà ýòîãî ýëåìåíòà è êàêîãî-ëèáî ìíîæåñòâà èíäåêñîâ { }k k km1 2, , ,� ñóùåñòâóåò îãðîìíîå ÷èñëî ïîñëåäóþùèõ âàðèàíòîâ âûáîðà xij è èíäåêñîâ. Ó÷èòûâàÿ, ÷òî îáúåäèíåíèå ýëåìåíòîâ xij ìîæåò âûïîëíÿòüñÿ ìíîãîêðàòíî, ÷èñëî âàðèàíòîâ ïîëíîãî ïåðåáîðà ðåøåíèÿ çàäà÷è (1)–(3), êîòîðîå áóäåò ðàñòè ýêñïîíåíöèàëüíî, íåïðîñòî âûðàçèòü â âèäå ôîðìóëû îò ðàçìåðíîñòè ìàòðèöû X . Åñëè ñôîðìóëè- ðîâàòü (1)–(3) êàê çàäà÷ó ïåðå÷èñëåíèÿ, ò.å. îòâåòèòü íà âîïðîñ, ñêîëüêî ó íåå èìååòñÿ ðåøåíèé, òî, ñêîðåå âñåãî, îíà ïðèíàäëåæèò ê êëàññó KP-ïîëíûõ çàäà÷ [3, ñòð. 210]. Ïðè ðåøåíèè èíäèâèäóàëüíîé çàäà÷è ñóùåñòâåííóþ ðîëü èãðàþò ãðàíèöû èçìåíåíèÿ çíà÷åíèé ýëåìåíòîâ aij ïî ñðàâíåíèþ ñî çíà÷åíèåì �. Òàê, åñëè aij � � � �i j n, ,1 , òî î÷åâèäíî, ÷òî âåðõíÿÿ ãðàíèöà ìèíèìóìà ðàâíà � � �� aijj n i n / � 11 è îïðåäåëèòü ýòî ìîæíî çà âðåìÿ O n( )2 , ïîñêîëüêó îïåðàöèè îáúåäèíåíèÿ ýëåìåíòîâ ìîãóò òîëüêî óâåëè÷èòü çíà÷åíèå ôóíêöèè öåëè. Åñëè âûïîëíÿåòñÿ aijj n � � 1 � � �i n1, è aiji n � � 1 � � �j n1, , òî â ýòîì êðàéíåì ñëó÷àå ñóùåñòâóåò ïðîñòîé àëãîðèòì, íå ó÷èòûâàþùèé îãðàíè÷åíèÿ (3), ñî ñëîæíîñòüþ O n( )3 äëÿ íàõîæäåíèÿ íèæíåé ãðàíèöû ìèíèìóìà ôóíêöèè � � � � �� x nijj n i n / � 11 2 2 ñ ìèíèìàëüíûì çíà÷åíèåì òðàíçèòíûõ îáúåäèíåííûõ ýëåìåíòîâ y yii n � � 1 , y x ai ij ijj n j n � � �� 11 (ñì. ïðèâåäåííûé äàëåå àëãîðèòì unconditional packing). 84 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 1 â ïðîòèâíîì ñëó÷àå, Ëåììà 1. Ìàêñèìàëüíîå ÷èñëî ýëåìåíòîâ, ïðåîáðàçóåìûõ ñ ïîìîùüþ îïå- ðàöèè îáúåäèíåíèÿ, íå ìîæåò ïðåâûøàòü çíà÷åíèÿ n n2 3 2� . Äîêàçàòåëüñòâî. ×èñëî ýëåìåíòîâ â ìàòðèöå ðàâíî n n2 � . Ïîñêîëüêó ëþ- áóþ ìàòðèöó ñ íåíóëåâûìè ýëåìåíòàìè (êðîìå äèàãîíàëüíûõ) ñ ïîìîùüþ îïå- ðàöèè îáúåäèíåíèÿ ìîæíî ïðèâåñòè ê âèäó, â êîòîðîì îíà áóäåò ñîäåðæàòü ðîâ- íî 2 2n� ýëåìåíòà, ÷èñëî ïðåîáðàçóåìûõ ýëåìåíòîâ îïðåäåëÿåòñÿ êàê n n n n n2 22 2 3 2� � � � � ( ) . NP-ÏÎËÍÎÒÀ ÇÀÄÀ×È Îòìåòèì, ÷òî çàäà÷à (1)–(3), ñôîðìóëèðîâàííàÿ êàê çàäà÷à ðàñïîçíàâàíèÿ: ñó- ùåñòâóåò ëè ïîñëåäîâàòåëüíîñòü îáúåäèíåíèé òàêàÿ, ÷òî çíà÷åíèå ôóíêöèè (1) íå ïðåâûøàåò B Z , ïðèíàäëåæèò ê êëàññó NP, òàê êàê äëÿ íåå âñåãäà íàé- äåòñÿ ñåðòèôèêàò ñ äëèíîé, îãðàíè÷åííîé ïîëèíîìîì n n2 3 2� (ëåììà 1). Ïîêàæåì, ÷òî NP-ïîëíóþ öåëî÷èñëåííóþ çàäà÷ó î ìíîãîïðîäóêòîâîì ïîòîêå ìèíèìàëüíîé ñòîèìîñòè (minimum-cost integer multicommodity flow problem, MC IMCF) ìîæíî ïîëèíîìèàëüíî ñâåñòè ê çàäà÷å (1)–(3). Â ðàáîòå [4] NP-ïîëíîòà çàäà÷è MC IMCF äàæå äëÿ äâóõïðîäóêòîâîãî öåëî÷èñëåííîãî ïî- òîêà äîêàçàíà ïóòåì ñâåäåíèÿ ê íåé çàäà÷è 3-âûïîëíèìîñòè (3-SAT). Ïîä ñâî- äèìîñòüþ çäåñü è äàëåå ïîäðàçóìåâàåòñÿ ñâîäèìîñòü ïî Êàðïó äëÿ ñîîòâåòñòâóþ- ùèõ çàäà÷ ðàñïîçíàâàíèÿ [3]. Ïðèâåäåì ïîñòàíîâêó çàäà÷è MC IMCF â ôîðìå «óçëû–äóãè» (node–arc or conventional). Ïóñòü G N E( , ) — ñåòü ñ ìíîæåñòâîì óçëîâ N , n N� \| \|, è ìíîæåñ- òâîì îðèåíòèðîâàííûõ äóã ij E , e E� \| \| . Çàäàíî ìíîæåñòâî ïðîäóêòîâ (commodity) P, p P� \| \| , êàæäûé èç êîòîðûõ õàðàêòåðèçóåòñÿ òðîéêîé (sm , tm , am ), m p�1 2, , ,� , am Z , ãäå sm , tm è am — ñîîòâåòñòâåííî óçëû îòïðàâëåíèÿ (origin) è íàçíà÷åíèÿ (destination), à òàêæå êîëè÷åñòâî (demand) ïðîäóêòà m P , êîòîðîå íóæíî äîñòàâèòü èç óçëà sm â óçåë tm . Ïðè òðàíñïîðòèðîâêå ïðîäóêòà çàïðåùåíî åãî ðàçâåòâëåíèå (ðàñùåïëåíèå, äðîáëåíèå íà ÷àñòè). Ïîñêîëüêó âñå ïðîäóêòû îäíîðîäíû, ïðåäïîëàãàåòñÿ, ÷òî åäèíèöà ëþáîãî ïðîäóêòà ïðè òðàíñ- ïîðòèðîâêå ïî äóãå èñïîëüçóåò åäèíèöó åå ïðîïóñêíîé ñïîñîáíîñòè. Äëÿ êàæäîé äóãè ñåòè ij E çàäàíû ïðîïóñêíàÿ ñïîñîáíîñòü wij Z è ñòîèìîñòü cij m � 0, cij m Z , òðàíñïîðòèðîâêè åäèíèöû ïðîäóêòà m. Ââåäåì áóëåâû ïåðåìåííûå xij m , ij E , m P . Òàê êàê ðàçâåòâëåíèå ïîòîêîâ çàïðåùåíî, òî xij m �1, åñëè ïðîäóêò m òðàíñïîðòèðóåòñÿ ïî äóãå ij E , è xij m � 0 â ïðîòèâíîì ñëó÷àå. Òðåáóåòñÿ íàéòè min c a xij m ij Em P m ij m (4) ïðè îãðàíè÷åíèÿõ x x i s i s tij m j ij E ji m j ji E m m m : : , , � � � � � � 1 0 1 ïðè ïðè ïðè i tm� � � � � � � � m P i N, ; (5) a x wm m P ij m ij � � ij E; (6) xij m { }0 1, � ij E, � m P. (7) ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 1 85 Îòìåòèì, ÷òî äëÿ çàäà÷è MC IMCF èçâåñòíî ìíîãî ðàçíîâèäíîñòåé ïîñòàíî- âîê, íàïðèìåð ñ ìàòðè÷íîé çàïèñüþ îãðàíè÷åíèé áàëàíñà (5) ñ èñïîëüçîâàíèåì ìàòðèöû èíöèäåíöèé óçëû–äóãè ñåòè [5]. Ôîðìóëèðîâêè â âèäå «äóãè–ïóòè» (arc–path or column generation) ïðèâåäåíû â [6, 7]. Âñå ïîñòàíîâêè çàäà÷ MC IMCF ïðè ðàçëè÷íûõ äîïîëíèòåëüíûõ îãðàíè÷åíèÿõ ìîæíî ëåãêî òðàíñôîðìè- ðîâàòü îäíó â äðóãóþ. Â [6, 7] ïðèâåäåí òàêæå îáøèðíûé áèáëèîãðàôè÷åñêèé îáçîð ðàçâèòèÿ ìåòîäîâ è àëãîðèòìîâ ðåøåíèÿ ìíîãîïðîäóêòîâûõ çàäà÷. Òåîðåìà 1. Çàäà÷à óïàêîâîê (1)–(3) ÿâëÿåòñÿ NP-ïîëíîé. Äîêàçàòåëüñòâî. Äëÿ ñâåäåíèÿ çàäà÷è (4)–(7) ê çàäà÷å (1)–(3) ðàññìîòðèì èíäèâèäóàëüíóþ çàäà÷ó (4)–(7) íà ïîëíîé ñåòè, êîãäà èíäåêñû m âñåõ ïðîäóêòîâ çàìåíåíû íîìåðàìè óçëîâ sm è tm , ñîâïàäàþùèìè ñ èíäåêñàìè äóã (ò.å. äëÿ êàæ- äîãî ïðîäóêòà st P èìååòñÿ äóãà ij E è s i� , t j� ). Èíäèâèäóàëüíàÿ çàäà÷à. Ïóñòü G N E( , ) — ïîëíàÿ ñåòü áåç ïåòåëü ñ ìíî- æåñòâîì óçëîâ N , n N� \| \| , è ìíîæåñòâîì îðèåíòèðîâàííûõ äóã ij E , e E n n� � �\| \| 2 , ò.å. � ij E � ji E. Êàæäàÿ äóãà ij èìååò ïðîïóñêíóþ ñïîñîáíîñòü wij Z . Çàäàíà ìàòðèöà òðåáîâàíèé (demand) A ast n n� �\| \| \| \| è ÷èñëî �, ast , � Z , ast � 0 ïðè s t� . Êàæäûé ïðîäóêò st P , \| \|P n n� �2 , â êîëè÷åñòâå ast äîëæåí áûòü äîñòàâëåí èç óçëà îòïðàâëåíèÿ s â óçåë íàçíà÷åíèÿ t. Ïóñòü ñòîè- ìîñòü òðàíñïîðòèðîâêè åäèíèöû ïðîäóêòà cij st �1 � ij E è � st P. Ïåðåìåííûå xij st �1, åñëè ïðîäóêò st P òðàíñïîðòèðóåòñÿ ïî äóãå ij E , è xij st � 0 â ïðîòèâíîì ñëó÷àå. Ïóñòü w a ij ij � � � � � � � � � � ij E. Îáîçíà÷èì x a xij st st P ij st� � ij E. Òîãäà èí- äèâèäóàëüíàÿ çàäà÷à çàïèñûâàåòñÿ òàê min xij ij E � � � � � � � (8) ïðè îãðàíè÷åíèÿõ a x a x a i s i sst ij st j ij E st ji st j ji E st : : , � � � � � ïðè ïðè0 t st P i N a i tst , , ; , � � � � � � � � � ïðè (9) x a ij ij � � � � � � � � � � ij E; (10) xij st { }0 1, � ij E, � st P. (11) Ñëîæèâ äëÿ êàæäîãî i ðàâåíñòâà (9) ïî âñåì ïðîäóêòàì st P , ïîëó÷èì óðàâ- íåíèÿ áàëàíñà äëÿ óçëîâ i â âèäå a x a x ast ij st st Pj ij E st ji st st Pj ji E it t it � � � : : : P si s si P a : èëè x a x aij j ij E it t it P ji j ji E si s si P: : : : � � � � i N , ÷òî èäåíòè÷íî óñëîâèÿì (2). 86 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 1 Òàêèì îáðàçîì, çàäà÷à (1)–(3) èìååò ðåøåíèå òîãäà è òîëüêî òîãäà, êîãäà èìååò ðåøåíèå ïîñòðîåííàÿ çàäà÷à (8)–(11). Ïðèâåäåííîå ñâåäåíèå ìîæíî âû- ïîëíèòü çà ïîëèíîìèàëüíîå âðåìÿ O n( )2 , ïðåîáðàçîâàâ ëþáóþ ñåòü ñ çàäàííûìè òðåáîâàíèÿìè A ast n n� �\| \| \| \| â ïîëíóþ ñ äóãàìè, äëÿ êîòîðûõ cij st �1è w a ij ij � � � � � � � � � äëÿ âñåõ èíäåêñîâ st è ij. Ïóñòü èìååòñÿ ëþáîå (íå îáÿçàòåëüíî îïòèìàëüíîå) ðå- øåíèå xij st , st P , ij E , çàäà÷è (8 )–(11). Íàáîð çíà÷åíèé xij st îäíîçíà÷íî îïðåäå- ëÿåò x a xij st st P ij st� � ij E — çíà÷åíèÿ ïåðåìåííûõ â (1)–(3). Ïîýòîìó î÷åâèäíî, ÷òî ðåøåíèÿ çàäà÷ (8)–(11) è (1)–(3) ñîâïàäàþò. Îáðàòíî. Ïóñòü ïîëó÷åíî êà- êîå-ëèáî ðåøåíèå xij , i j n, ,�1 , çàäà÷è (1)–(3). Ïî ñîõðàíåííûì öåïî÷êàì îáúåäè- íåíèÿ ýëåìåíòîâ âñåãäà ìîæíî îïðåäåëèòü çíà÷åíèÿ xij st , îòëè÷íûå îò íóëÿ. Òà- êèì îáðàçîì, ïî ðåøåíèþ îäíîé çàäà÷è ìîæíî ïîëó÷èòü àíàëîãè÷íîå ðåøåíèå äðóãîé çàäà÷è è íàîáîðîò. Î÷åâèäíî, ÷òî çàäà÷à (1)–(3) ïðè ôîðìóëèðîâêå åå â âèäå çàäà÷è MC IMCF íà ïîëíîé ñåòè ïîëèíîìèàëüíî ñâîäèòñÿ ê çàäà÷å (8)–(11). Â ñèëó NP-ïîëíîòû (8)–(11) çàäà÷à (1)–(3) òàêæå ÿâëÿåòñÿ NP-ïîëíîé. Òåîðåìà äîêàçàíà. Ñðàâíèâàÿ ðàçëè÷íûå ïîñòàíîâêè çàäà÷è äëÿ ïîëíîé ñåòè ñ ÷èñëîì ïðîäóê- òîâ p n n� �2 è ñ ÷èñëîì äóã e n n� �2 ïî êîëè÷åñòâó îãðàíè÷åíèé è ïåðåìåííûõ (òàáë. 1), ìîæíî óòâåðæäàòü, ÷òî äëÿ ðàçðàáîòêè ýâðèñòè÷åñêèõ êîìáèíàòîðíûõ àëãîðèòìîâ ðåøåíèÿ çàäà÷è ëó÷øåé ÿâëÿåòñÿ èñõîäíàÿ ôîðìóëèðîâêà, òàê êàê îíà ñîäåðæèò çíà÷èòåëüíî ìåíüøå îãðàíè÷åíèé è ïåðåìåííûõ. Ïîñòàíîâêà (1)–(3) äàåò âîçìîæíîñòü êîíñòðóèðîâàòü ýôôåêòèâíûå (ïîëèíîìèàëüíûå) àëãî- ðèòìû ëîêàëüíîé îïòèìèçàöèè (àëãîðèòìû ìåòîäà âåêòîðà ñïàäà, ðàíäîìèçèðî- âàííûå, ìåòààëãîðèòìû, ãèáðèäíûå è ïð.) áåç ââåäåíèÿ áóëåâûõ ïåðåìåííûõ (ò.å. íå èñïîëüçîâàòü â êà÷åñòâå áàçû òîëüêî èçâåñòíûå ìåòîäû ðåøåíèÿ öåëî÷èñ- ëåííîé çàäà÷è î ìíîãîïðîäóêòîâîì ïîòîêå ìèíèìàëüíîé ñòîèìîñòè [6, 7]). ×ÈÑËÅÍÍÛÉ ÝÊÑÏÅÐÈÌÅÍÒ Ïîêàæåì íà ïðèìåðå ïðîñòûõ òåñòîâûõ àëãîðèòìîâ óïàêîâîê (unconditional packing è conditional packing), êàê âëèÿþò èçìåíåíèå ãðàíèö âõîäíûõ äàííûõ è ðàçëè÷íûå ïåðåáîðíûå ñõåìû ðåøåíèÿ çàäà÷è íà êîíå÷íûå ðåçóëüòàòû. Ýòè àëãîðèòìû íå ïðåäíàçíà÷åíû äëÿ îïòèìàëüíîãî ðåøåíèÿ çàäà÷è (1)–(3) è òåì áîëåå äëÿ ðåøåíèÿ ïðàêòè÷åñêèõ çàäà÷ óïàêîâîê ñ çàäàííûìè ôóíêöèÿìè çà- òðàò íà îáðàáîòêó è òðàíñïîðòèðîâêó ìåëêîïàðòèîííûõ êîððåñïîíäåíöèé, â îñíîâå êîòîðûõ ëåæèò ðåøåíèå çàäà÷è (1)–(3). Ðåçóëüòàòû ðàáîòû ýòèõ àëãî- ðèòìîâ òîëüêî óêàçûâàþò, íà ÷òî íóæíî îáðàòèòü âíèìàíèå ïðè äàëüíåéøåé ðàçðàáîòêå ðàáî÷èõ àëãîðèòìîâ äëÿ ðåøåíèÿ çàäà÷ óïàêîâîê â ðåàëüíûõ êîì- ìóíèêàöèîííûõ ñåòÿõ. Ââåäåì íåêîòîðóþ ôèêñèðîâàííóþ îïåðàöèþ îáúåäèíåíèÿ ýëåìåíòîâ ïðè ðåøåíèè çàäà÷è (1)–(3), êîòîðàÿ ôîðìàëüíî çàïèñûâàåòñÿ òàê: íàä ëþáîé òðîé- ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 1 87 Ïîñòàíîâêà çàäà÷è Êîëè÷åñòâî îãðàíè÷åíèé ïåðåìåííûõ Èñõîäíàÿ (1)–(3) n n n �( )2 ( )n n2 � Â âèäå MC IMCF óçëû–äóãè (8)–(11) ( )( )n n n �1 2 ( )n n2 2� Ò à á ë è ö à 1 êîé ýëåìåíòîâ x x xik kj ij, , � 0, k i j n, , ,�1 , k i j� � , ìàòðèöû X ìîãóò âûïîëíÿòüñÿ äåéñòâèÿ x x xik ik ij� , x x xkj kj ij� , c k y y x xij k k ij ij� � �, , 0, (12) ãäå «�» — çíàê îïåðàöèè ïðèñâàèâàíèÿ; k — èíäåêñ ñòîëáöà è ñòðîêè, ÷åðåç êîòîðûé âûïîëíÿåòñÿ îáúåäèíåíèå xij , ïðè÷åì xij äîëæåí îáúåäèíÿòüñÿ ñ xik è xkj òîëüêî öåëèêîì; cij — ýëåìåíòû ñïðàâî÷íîé ìàòðèöû îáúåäèíåíèé ýëå- ìåíòîâ C cij n n� �\| \| \| \| ; Y yk� \| \| \| \| , k n�1, , — âåêòîð ñóìì òðàíçèòíûõ îáúåäè- íåííûõ ýëåìåíòîâ, y x ak kj kj j n j n � � �� 11 . Â íà÷àëüíîì ñîñòîÿíèè äëÿ âñåõ i ýëå- ìåíòû c i j nij � � �1, , à Y � 0. Èç ìàòðèöû C íà ëþáîì øàãå ìîæíî îïðåäå- ëèòü ñ ïîìîùüþ àëãîðèòìîâ, ïðèâåäåííûõ â [8], ïîñëåäîâàòåëüíîñòü � ij i k� {( , ),1 ( , ), , ( , )k k k jm1 2 � } ñ ïðîìåæóòî÷íûìè èíäåêñàìè ñòîëáöîâ è ñòðîê { }k k km1 2, , ,� , ÷åðåç êîòîðûå âûïîëíÿëîñü îáúåäèíåíèå ýëåìåíòà aij , à òàêæå íàéòè ìíîæåñòâî äðóãèõ ýëåìåíòîâ { }ars * , êîòîðûå óæå áûëè îáúå- äèíåíû ñ aij íà ïðåäûäóùèõ èòåðàöèÿõ, åñëè c iij � . Ëåììà 2. Åñëè � � � � � � � � � � � � � � � � � � � � � � � � � � � x x x x x ik kj ij ik ij � � � � x xkj ij � � � � � � � � � � � � � , (13) òî åå çíà÷åíèå íå ìîæåò ïðåâûøàòü åäèíèöû. Äîêàçàòåëüñòâî. Â (13) âîçìîæíû òðè ñëó÷àÿ: � ! 0, � � 0 è � �1. Ïîñëåä- íèé ñëåäóåò èç òîãî, ÷òî ïðè óñëîâèÿõ x x xik ij ik � � � � � � � � � � � � � � � è x x xkj ij kj � � � � � � � � � � � � � � � ðàç- íîñòü â (13) íå ìîæåò ïðåâûøàòü 1, òàê êàê ïðè xij � � è xij � � � � � � � � 1 îíà âñåãäà áó- äåò îòðèöàòåëüíîé. Òàêèì îáðàçîì, çà îäíó îïåðàöèþ îáúåäèíåíèÿ (12) ïðè � �1 ìîæíî óìåíü- øèòü çíà÷åíèå ôóíêöèè (1) íà åäèíèöó. Ðàññìîòðèì àëãîðèòìû unconditional packing è conditional packing è ðå- çóëüòàòû èõ ðàáîòû ïðè èçìåíåíèè ãðàíèö çíà÷åíèé min ( ) max� � �x aij ij ïðè ôèêñèðîâàííîì �. Â àëãîðèòìàõ èñïîëüçóþòñÿ î÷åâèäíîå ñâîéñòâî � � � � � � � � � x xi i ii / ( ) /� � è òî, ÷òî ëþáóþ ìàòðèöó X ñ ïîìîùüþ ïðåîáðàçîâàíèé (12) ìîæíî äëÿ ëþáûõ ñòðîêè i è ñòîëáöà j, i j� , ïðèâåñòè ê âèäó (â ïðèìåðå i j� �1): 0 0 0 0 0 0 0 0 0 0 2 2 x x x x ii ini jj njj � � . Àëãîðèòì unconditional packing èìååò ñëîæíîñòü O n( )3 , íå ïðîâåðÿåò âûïîëíå- íèÿ îãðàíè÷åíèé (3) è çíà÷åíèÿ � â (13). Àëãîðèòì conditional packing ïðîâåðÿåò çíà÷åíèå � è ïðè � � 0 äîïóñêàåò îñëàáëåíèå îãðàíè÷åíèé (3). Ñëîæíîñòü âòîðîãî àëãîðèòìà áîëüøå è ñîñòàâëÿåò O fs n( )" 3 , ãäå fs — ÷èñëî âõîäîâ â öèêë ïî k. 88 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 1 Àëãîðèòì unconditional packing 1. OPT X A_ � ; OPT CS C_ � ; opt cont sum aijj n i n _ _ /� � � �� 11 ; OPT Y_ � 0; opt y sum_ _ � 0. 2. Äëÿ { }k k n\| ,�1 âûïîëíèòü ïï. 3–11. 3. X A� ; CS C� ; Y � 0. 4. Äëÿ { , }i i n i k\| ,� �1 âûïîëíèòü ïï. 5–8. 5. Äëÿ { , }j j n j i j k\| ,� � # �1 âûïîëíèòü ïï. 6–7. 6. x x xik ik ij� ; x x xkj kj ij� ; cs kij � ; y y xk k ij� ; xij � 0. 7. Ïåðåéòè ê ï. 5. * Êîíåö öèêëà ïî j 8. Ïåðåéòè ê ï. 4. * Êîíåö öèêëà ïî i 9. cont sum xrss n r n _ /� � � �� 11 , y sum yrr n _ � � 1 . 10. Åñëè cont sum opt cont sum cont sum opt cont sum y sum_ _ _ _ _ _ _! $ � # ! ! opt y sum_ _ , òî OPT X X_ � ; OPT CS CS_ � ; OPT Y Y_ � ; opt cont sum_ _ � � cont sum_ ; opt y sum y sum_ _ _� . 11. Ïåðåéòè ê ï. 2. * Êîíåö öèêëà ïî k 12. Êîíåö àëãîðèòìà. Àëãîðèòì conditional packing 1. OPT X A_ � ; OPT CS C_ � ; opt cont sum aijj n i n _ _ /� � � �� 11 ; OPT Y_ � 0; fs � 0; fs cont sum opt cont sum_ _ _ _� ; FS Y_ � 0; fs y sum_ _ � 0. 2. Äëÿ { }k k n\| ,�1 âûïîëíèòü ïï. 3–12. 3. X A� ; CS C� ; Y FS Y� _ ; opt y sum fs y sum_ _ _ _� . 4. Äëÿ { , }i i n i k\| ,� �1 âûïîëíèòü ïï. 5–9. 5. Äëÿ { , 0 0 0}j j n j i j k x x xik kj ij\| ,� � # � # � # � # �1 âûïîëíèòü ïï. 6–8. 6. � � � � � � � � � � � � � � � � � � � � � � � � � � � x x x x x ik kj ij ik ij � � � � x xkj ij � � � � � � � � � � � � � . 7. Åñëè � � 0, òî x x xik ik ij� ; x x xkj kj ij� ; cs kij � ; y y xk k ij� ; xij � 0. * Âîçìîæíî è � � 0 8. Ïåðåéòè ê ï. 5. * Êîíåö öèêëà ïî j 9. Ïåðåéòè ê ï. 4. * Êîíåö öèêëà ïî i 10. � �cont sum x y sum yrss n r n rr n _ / , _� � �� 11 1 . 11. Åñëè cont sum opt cont sum cont sum opt cont sum y sum_ _ _ _ _ _ _! $ � # ! ! opt y sum_ _ , òî OPT X X_ � ; OPT CS CS_ � ; OPT Y Y_ � ; opt cont sum_ _ � � cont sum_ ; opt y sum y sum_ _ _� . 12. Ïåðåéòè ê ï. 2. * Êîíåö öèêëà ïî k 13. Åñëè opt cont sum fs cont sum_ _ _ _! , òî fs fs� 1; fs cont sum_ _ � � opt cont sum_ _ ; A OPT X� _ ; C OPT CS� _ ; FS Y OPT Y_ _� ; fs y sum_ _ � � opt y sum_ _ ; ïåðåéòè ê ï. 2. 14. Êîíåö àëãîðèòìà. Â çàïèñè àëãîðèòìîâ ïðîïèñíûìè áóêâàìè îáîçíà÷åíû ìàòðèöû è âåêòîðû (íàïðèìåð, OPT X_ , OPT Y_ ), à ñòðî÷íûìè (íàïðèìåð, opt cont sum_ _ , opt y sum_ _ ) — ïðîñòûå ïåðåìåííûå, çíàêîì * îòìå÷åíû êîììåíòàðèè. Â àë- ãîðèòìå unconditional packing � èç (13) íå âû÷èñëÿåòñÿ, â ýòîì ñëó÷àå îãðàíè÷å- íèÿ (3) íå ó÷èòûâàþòñÿ. Â àëãîðèòìå conditional packing â ï. 7 äîïóñêàåòñÿ � � 0 è � � 0, ÷òî ñîîòâåòñòâóåò ñòðîãîìó ñîáëþäåíèþ îãðàíè÷åíèé (3) è èõ îñëàáëåíèþ. ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 1 89 Ïðè ïðîâåäåíèè ýêñïåðèìåíòà ìàòðèöà A ãåíåðèðîâàëàñü äàò÷èêîì ïñåâ- äîñëó÷àéíûõ ÷èñåë äëÿ âîñüìè èíòåðâàëîâ. Ðåçóëüòàòû ýêñïåðèìåíòà äëÿ n �100 è � � 40 ïðèâåäåíû â òàáë. 2, â êîòîðîé ïðèíÿòû ñëåäóþùèå îáîçíà÷åíèÿ: opt cont sum_ _ — çíà÷åíèå ôóíêöèè öåëè (1); opt y sum_ _ — ìèíèìàëüíîå çíà÷å- íèå y ykk n � � 1 ; Kav — ñðåäíèé êîýôôèöèåíò çàãðóçêè áëîêà; N av — ñðåäíåå ÷èñëî íåíóëåâûõ ýëåìåíòîâ â ñòðîêå ìàòðèöû X ; f s — ÷èñëî âõîäîâ â öèêë ïî k â àëãîðèòìå conditional packing; tav — âðåìÿ ðåøåíèÿ çàäà÷è. Äëÿ êàæäîãî èí- òåðâàëà äàííîé òàáëèöû ðåçóëüòàòû ñîîòâåòñòâóþò ðàáîòå àëãîðèòìîâ: äî îïòè- ìèçàöèè — ïåðâàÿ ñòðîêà; unconditional packing — âòîðàÿ ñòðîêà; conditional packing ïðè � � 0 è � � 0 — òðåòüÿ è ÷åòâåðòàÿ ñòðîêè. Çíà÷åíèÿ K n x x av ii n ij j n ij � � � � � � � � � � � � � � � 1 1 1 1� � �/ , � �i ij j n � � 1 , è N n av i i n � � 1 1 � , i n�1, , âû÷èñëÿëèñü ïî ðåçóëüòèðóþùåé ìàòðèöå OPT X_ , ãäå �ij �1 , åñëè xij � 0, è �ij � 0 â ïðîòèâíîì ñëó÷àå. Â òàáë. 3 ïðèâåäåíû ðåçóëüòàòû ðàáîòû àëãîðèòìà conditional packing ïðè � � 0, � � 0 è ïåðåñòàíîâêå èíäåêñîâ îñíîâíîãî òðîéíîãî öèêëà (ïï. 2, 4, 5 àëãî- 90 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 1 Èíòåðâàëû çíà÷åíèé aij , i j n, ,� 1 Ðåçóëüòàòû ðàáîòû àëãîðèòìîâ unconditional packing è conditional packing opt cont sum_ _ opt y sum_ _ Kav N av f s tav , ñ [1, 5] 9900 1569 1570 2391 0 29057 29126 22477 0,075 0,936 0,937 0,519 99 1 1 23 – 1 3 30 – 0,17 0,97 6,46 [1, 10] 9900 2793 2790 3552 0 53253 53278 32890 0,138 0,963 0,942 0,597 99 1 2 35 – 1 3 34 – 0,16 0,97 8,75 [1, 20] 9900 5238 5219 4510 0 101619 100735 47325 0,262 0,982 0,866 0,819 99 1 2 45 – 1 7 59 – 0,17 1,54 17,02 [1, 40] 9900 9900 8039 6734 0 0 92435 28156 0,512 0,512 0,833 0,854 99 99 35 67 – 1 31 75 – 0,16 7,13 29,36 [1, 60] 13232 13232 12069 9931 0 0 149615 43588 0,550 0,550 0,887 0,868 99 99 37 65 – 1 45 98 – 0,17 10,94 37,47 [1, 80] 14869 14869 14057 12334 0 0 119340 32342 0,632 0,632 0,889 0,872 99 99 51 73 – 1 36 93 – 0,16 10,81 39,91 [1, 100] 17827 17827 17049 15344 0 0 122630 37448 0,657 0,657 0,893 0,873 99 99 54 74 – 1 40 93 – 0,16 12,93 40,34 [1, 120] 19791 19791 19160 17726 0 0 102874 30478 0,701 0,701 0,900 0,881 99 99 61 78 – 1 39 92 – 0,16 14,04 42,46 Ò à á ë è ö à 2 ðèòìà) ïðè n � 200 , �� , aij [ , ]1 120 , i j n, ,�1 . Â ïåðâîé ñòðîêå äàíû ðåçóëü- òàòû ðàáîòû àãîðèòìà conditional packing äî îïòèìèçàöèè, âî âòîðîé è òðåòüåé ñòðîêàõ — ñîîòâåòñòâåííî ïðè � � 0 è � � 0. Èç òàáë. 2 âèäíî, ÷òî àëãîðèòì unconditional packing ìîæåò ïðè ìàëûõ ãðà- íèöàõ èçìåíåíèÿ aij äàòü ëó÷øèå ðåøåíèÿ, ÷åì àëãîðèòì conditional packing. Ïðè áîëüøèõ çíà÷åíèÿõ � ñ ïîìîùüþ ýòîãî àëãîðèòìà ìîæíî ïîëó÷èòü è îïòè- ìàëüíîå ðåøåíèå opt cont sum n_ _ � � �2 2 198 ñ ìèíèìàëüíûì çíà÷åíèåì opt y sum_ _ . Ïðè óâåëè÷åíèè ãðàíèö èçìåíåíèÿ aij ëó÷øèå ðåçóëüòàòû ïîêàçûâà- åò àëãîðèòì conditional packing ïðè � � 0 è � � 0. Èç òàáë. 3 ìîæíî âèäåòü, ÷òî ðàçëè÷íûå ïåðåáîðíûå ñõåìû îáúåäèíåíèÿ ýëåìåíòîâ â àëãîðèòìå conditional packing äàþò ðàçíûå ñèëüíî îòëè÷àþùèåñÿ ðå- çóëüòàòû. Àíàëèç ðåçóëüòàòîâ, ïðèâåäåííûõ â òàáë. 2 è 3, ïîçâîëÿåò ñäåëàòü ñëåäóþ- ùèå âûâîäû: — ïðè ìàëûõ çíà÷åíèÿõ aij , i j n, ,�1 (èíòåðâàëû [1, 5], [1, 10]) ëó÷øèå çíà÷å- íèÿ ôóíêöèè öåëè ìîæíî ïîëó÷èòü ñ ïîìîùüþ àëãîðèòìà unconditional packing, êîãäà � íå âû÷èñëÿåòñÿ è îãðàíè÷åíèÿ (3) íå ó÷èòûâàþòñÿ, à íà÷èíàÿ ñ èíòåðâà- ëà [1, 40] ýòîò àëãîðèòì íåïðèìåíèì, òàê êàê íå ïðèâîäèò ê óëó÷øåíèþ çíà÷åíèÿ öåëåâîé ôóíêöèè; — äëÿ èíòåðâàëîâ [1, 5], [1, 10] íåïëîõèå ðåçóëüòàòû ïîêàçûâàåò àëãîðèòì conditional packing ïðè � � 0, â ýòîì ñëó÷àå ñóììà çíà÷åíèé òðàíçèòíûõ îáúåäè- íåííûõ ýëåìåíòîâ (opt y sum_ _ ) âñåãäà íàìíîãî áîëüøå, ÷åì â ñëó÷àå � � 0, ÷òî íåîáõîäèìî ó÷èòûâàòü ïðè ðàçðàáîòêå ðàáî÷èõ àëãîðèòìîâ äëÿ ðåàëüíûõ çàäà÷ óïàêîâêè ñî ñëîæíîé öåëåâîé ôóíêöèåé; — áåçóñëîâíàÿ è óñëîâíàÿ ïðè � � 0 ñòðàòåãèè ìîãóò ðàñøèðÿòü ãðàíèöû ïîèñêà ëîêàëüíîãî ìèíèìóìà ïðè ñëó÷àéíîì èõ èñïîëüçîâàíèè â àëãîðèòìå conditional packing è ïðèâåñòè ê ëó÷øåìó ðåçóëüòàòó ïî ñðàâíåíèþ ñ íåïðåðûâ- íûì ïðèìåíåíèåì ñòðàòåãèè � � 0; — ñðåäíèé êîýôôèöèåíò çàãðóçêè áëîêà Kav íå ìîæåò ÿâëÿòüñÿ êðèòåðèåì ïîèñêà ëó÷øåãî ðåøåíèÿ; ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 1 91 Ïîñëåäîâàòåëüíîñòü èíäåêñîâ òðîéíîãî öèêëà Ðåçóëüòàòû ðàáîòû àëãîðèòìà conditional packing opt cont sum_ _ opt y sum_ _ Kav N av f s tav , ñ k i j, , 46481 40729 32220 0 1438516 434132 0,514 0,856 0,877 199 60 127 – 65 196 – 106,63 573,91 k j i, , 46481 40729 32220 0 1438516 434132 0,514 0,856 0,877 199 60 127 – 65 196 – 105,89 571,85 i k j, , 46481 41463 32779 0 1537721 501658 0,514 0,934 0,890 199 64 130 – 192 200 – 339,69 591,79 j k i, , 46481 41431 32798 0 1532645 497041 0,514 0,921 0,880 199 64 130 – 191 199 – 338,27 584,35 i j k, , 46481 42599 34729 0 1595685 670593 0,514 0,941 0,886 199 80 140 – 169 200 – 332,05 644,47 j i k, , 46481 42645 34692 0 1601494 661718 0,514 0,919 0,881 199 80 140 – 175 200 – 362,27 700,57 Ò à á ë è ö à 3 — äàííûå ýêñïåðèìåíòà ïîäòâåðæäàþò ñèëüíóþ çàâèñèìîñòü ðåçóëüòàòîâ ðåøåíèÿ çàäà÷è îò âûáîðà ýëåìåíòîâ xij è èíäåêñîâ k äëÿ âûïîëíåíèÿ îïåðàöèé îáúåäèíåíèÿ (12) è îò ãðàíèö èçìåíåíèÿ âõîäíûõ äàííûõ — çíà÷åíèé n, aij , �, à òàêæå íåîáõîäèìîñòü ïîèñêà è ðàçðàáîòêè ýôôåêòèâíûõ ýâðèñòè÷åñêèõ àëãîðèòìîâ. Âñå çàäà÷è ðåøàëèñü íà ÏÊ ñ ïðîöåññîðîì Intel Core 2 Duo c òàêòîâîé ÷àñòî- òîé 2,66 ÃÃö è îïåðàòèâíîé ïàìÿòüþ 2 Ãá. ÇÀÊËÞ×ÅÍÈÅ Â ðàáîòå äîêàçàíà NP-ïîëíîòà îäíîé çàäà÷è îïòèìèçàöèè óïàêîâîê, êîòîðàÿ èñïîëüçóåòñÿ ïðè ñîðòèðîâêå è óïàêîâêå ìåëêîïàðòèîííûõ ãðóçîâ â êîíòåéíå- ðû â òðàíñïîðòíûõ ñåòÿõ èëè îáúåäèíåíèè ñîîáùåíèé â âèðòóàëüíûå êîíòåé- íåðû â ñåòÿõ ïåðåäà÷è äàííûõ. Ïðèâåäåíû äàííûå ÷èñëåííîãî ýêñïåðèìåíòà ñ ïðîñòûìè òåñòîâûìè àëãîðèòìàìè óïàêîâîê, êîòîðûå ïîêàçûâàþò ñèëüíóþ çàâèñèìîñòü ðåçóëüòàòîâ ðåøåíèÿ çàäà÷è îò ãðàíèö èçìåíåíèÿ çíà÷åíèé âõîä- íûõ äàííûõ è âûáîðà ñõåì ïåðåáîðà âàðèàíòîâ ðåøåíèÿ, à òàêæå óêàçûâàþò, íà ÷òî íóæíî îáðàòèòü âíèìàíèå ïðè ðàçðàáîòêå àëãîðèòìîâ äëÿ ðåøåíèÿ çà- äà÷ îáðàáîòêè è òðàíñïîðòèðîâêè ìåëêîïàðòèîííûõ êîððåñïîíäåíöèé â ðåàëü- íûõ êîììóíèêàöèîííûõ ñåòÿõ. ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ 1. Ò ð î ô è ì ÷ ó ê À . Í . , Â à ñ ÿ í è í Â . À . Ìåòîäèêà ðåøåíèÿ çàäà÷è îïòèìèçàöèè óïàêîâîê äëÿ óïðàâëåíèÿ ïåðñïåêòèâíûì ðàçâèòèåì óçëîâ êîììóíèêàöèîííîé ñåòè // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 2014. — ¹ 4. — Ñ. 88–99. 2. Ò ð î ô è ì ÷ ó ê À . Í . , Â à ñ ÿ í è í Â . À . Ìîäåëèðîâàíèå óïàêîâêè, ðàñïðåäåëåíèÿ è ìàðøðóòèçà- öèè ìåëêîïàðòèîííûõ ïîòîêîâ â ìíîãîïðîäóêòîâîé ñåòè // Ïðîáëåìû óïðàâëåíèÿ è èíôîðìàòèêè. — 2015. — ¹ 4. — Ñ. 132–146. 3. Ã ý ð è Ì . , Ä æ î í ñ î í Ä . Âû÷èñëèòåëüíûå ìàøèíû è òðóäíîðåøàåìûå çàäà÷è. — Ì.: Ìèð, 1982. — 416 ñ. 4. E v e n S . , I t a i A . , S h a m i r A . On the complexity of timetable and multicommodity flow problems // SIAM J: Comput. — 1976. — 5. — P. 691–703. 5. A h u j a R . K . , M a g n a n t i T . L . , O r l i n J . B . Network flows: theory, algorithms, and applications. — Upper Saddle River (New Jersey): Prentice-Hall, Inc., 1993. — 846 p. 6. B a r n h a r t C . , H a n e C . A . , V a n g e P . H . Using branch-and-price-and-cut to solve origin destination integer multicommodity flow problems // Operations Research. — 2000. — 48, N 2. — P. 318–326. 7. B a r n h a r t C . , K r i s h n a n N . , V a n g e P . H . Multicommodity flow problems: In Encyclopedia of Optimization: Second Edition, C.A. Floudas and P.M. Pardalos (Eds.). — New York: Springer, 2009. — P. 2354–2362. 8. Â à ñ ÿ í è í Â . À . Ñïðàâî÷íàÿ ìàòðèöà ñëèÿíèÿ ïîòîêîâ â çàäà÷àõ îïòèìèçàöèè óïàêîâîê íà ìíîãîïðî- äóêòîâûõ ñåòÿõ // Ñèñòåìí³ äîñë³äæåííÿ òà ³íôîðìàö³éí³ òåõíîëîã³¿. — 2014. — ¹ 3. — Ñ 42–49. Ïîñòóïèëà 27.04.2015 92 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 1

О сложности одной задачи оптимизации упаковок

Institution

Ähnliche Einträge