Элементы теории графов. Домнин Л.Н. - 127 стр.

UptoLike

ВУЗ: 

ПГУ | Пенза

Составители: 

Рубрика: 

n
c
i,j
v
j
v
i
,
n
n=6, (n−1)!=5!=120
   5.4.1. Ïðèìåíåíèå è ìåòîäû ðåøåíèÿ çàäà÷è
   Íà ïðàêòèêå ñ ýòîé îïòèìèçàöèîííîé çàäà÷åé è ðàçëè÷-
íûìè åå ìîäèôèêàöèÿìè ïîñòîÿííî ñòàëêèâàþòñÿ ôèðìû è
àãåíòñòâà, çàíèìàþùèåñÿ äîñòàâêîé ãðóçîâ. Åùå îäíà îáëàñòü
ïðèìåíåíèÿ  ýòî ïëàíèðîâàíèå ïðîèçâîäñòâà n ðàçëè÷íûõ
ïðîäóêòîâ íà åäèíñòâåííîì êîìïëåêòå òåõíîëîãè÷åñêîãî îáî-
ðóäîâàíèÿ (ñì. ðàçä. 5.3.1). Åñëè ci,j  ýòî âðåìÿ íà ïåðåíà-
ëàäêó îáîðóäîâàíèÿ ïðè ïåðåõîäå ê ïðîèçâîäñòâó ïðîäóêòà vj
ïîñëå ïðîäóêòà vi , òî íàèëó÷øèé ïî âðåìåíè ïîðÿäîê ïðîèç-
âîäñòâà âñåõ n ïðîäóêòîâ îïðåäåëÿåòñÿ êðàò÷àéøèì ãàìèëü-
òîíîâûì öèêëîì â ñîîòâåòñòâóþùåì ïîëíîì ãðàôå.
   Íàãëÿäíûé ïðèìåð ïðèìåíåíèÿ çàäà÷è êîììèâîÿæåðà ïðè-
âåäåí â [12]. Ïðè ïðîèçâîäñòâå ïå÷àòíûõ ïëàò íåîáõîäèìî ñäå-
ëàòü áîëüøîå êîëè÷åñòâî îòâåðñòèé â ðàçëè÷íûõ òî÷êàõ ïëà-
òû. Àâòîìàòè÷åñêèé ñâåðëèëüíûé ñòàíîê, âûïîëíÿþùèé ýòó
îïåðàöèþ, äîëæåí íàðÿäó ñ ñîáñòâåííî ñâåðëåíèåì âûïîëíÿòü
ïîçèöèîíèðîâàíèå ñâåðëà (ïëàòû). Âðåìåííûå   çàòðàòû íà ýòî
äåéñòâèå íåïîñðåäñòâåííî çàâèñÿò îò ïîðÿäêà îáõîäà âûøå-
óêàçàííûõ òî÷åê. Ìèíèìèçèðîâàòü îáùåå âðåìÿ âûïîëíåíèÿ
ïîäîáíîé îáðàáîòêè ïëàòû ìîæíî çà ñ÷åò âûáîðà îïòèìàëü-
íîé ïîñëåäîâàòåëüíîñòè îáõîäà òî÷åê ñâåðëåíèÿ, ò. å. ïåðåä
íàìè çàäà÷à êîììèâîÿæåðà.
   Íåñìîòðÿ íà ïðîñòîòó ôîðìóëèðîâêè, çàäà÷à îêàçûâàåòñÿ
âåñüìà ñëîæíîé. Ýòî îäíà èç îïòèìèçàöèîííûõ êîìáèíàòîð-
íûõ çàäà÷, äëÿ êîòîðûõ ýôôåêòèâíûå àëãîðèòìû íåèçâåñòíû.
Ñóùåñòâóþò ðàçëè÷íûå ïîäõîäû ê åå ðåøåíèþ.
   Ïðîñòåéøèé ïîäõîä, îñíîâàííûé íà ïåðåáîðå âñåõ âàðèàí-
òîâ, ãîäèòñÿ ëèøü äëÿ ãðàôîâ ìàëîé ðàçìåðíîñòè. Òàê, ïðè
÷èñëå âåðøèí n=6, íåîáõîäèìî ñôîðìèðîâàòü (n−1)!=5!=120
ïåðåñòàíîâîê, êàæäàÿ èç êîòîðûõ îïðåäåëÿåò íåêîòîðûé ãà-
ìèëüòîíîâ öèêë, ïîäñ÷èòàòü, èñïîëüçóÿ ìàòðèöó âåñîâ, äëèíó
âñåõ ýòèõ öèêëîâ è âûáðàòü èç íèõ îïòèìàëüíûé(å).
   Áîëåå ïðîäóêòèâåí ïîäõîä, îñíîâàííûé íà ÷àñòè÷íîì ïå-
ðåáîðå, êîãäà íà îñíîâå íåêîòîðûõ êðèòåðèåâ îòáðàñûâàþòñÿ
çàâåäîìî áåñïåðñïåêòèâíûå âàðèàíòû. Èìåííî òàêîé ïîäõîä
ðåàëèçóåòñÿ ñ ïîìîùüþ ìåòîäà âåòâåé è ãðàíèö.


                            127

Страницы