Математические методы в экономике. Копылов Г.Н - 80 стр.

               §6. ÇÀÄÀ×À ÊÎÌÌÈÂÎßÆÅÐÀ

     Êîììèâîÿæåð (áðîäÿ÷èé òîðãîâåö) äîëæåí îáúåõàòü n ãî-
ðîäîâ, ïîáûâàâ â êàæäîì ïî îäíîìó ðàçó, è âåðíóòüñÿ îáðàòíî.
Ìû õîòèì èç ìíîæåñòâà âîçìîæíûõ ñïîñîáîâ îáúåçäà ãîðîäîâ
âûáðàòü íàèëó÷øèé.
     ×òî ìîæåò ÿâëÿòüñÿ êðèòåðèåì îïòèìàëüíîñòè?
      êà÷åñòâå êðèòåðèÿ îïòèìàëüíîñòè ìîãóò áûòü âûáðàíû
ðàçíûå âåëè÷èíû. Íàïðèìåð, âðåìÿ îáúåçäà ãîðîäîâ, ñóììàðíàÿ
ñòîèìîñòü èëè äëèíà ïðîéäåííîãî ïóòè. Ìû â êà÷åñòâå êðèòåðèÿ
îïòèìàëüíîñòè âûáåðåì ñóììàðíóþ äëèíó ïðîéäåííîãî ïóòè.
     Ðàññìîòðèì ïðèìåð. Ïðåäïîëîæèì, íåîáõîäèìî îáúåõàòü 5
ãîðîäîâ. Íóæíî îïðåäåëèòü ñàìûé êîðîòêèé ñïîñîá îáúåçäà ýòèõ
ãîðîäîâ.
     Áóäåì ñ÷èòàòü, ÷òî âîçìîæåí ïåðååçä èç ëþáîãî ãîðîäà â
ëþáîé äðóãîé è èçâåñòíà äëèíà êàæäîãî ïåðååçäà. Ýòà èíôîðìà-
öèÿ çàäàåòñÿ â âèäå ìàòðèöû.
                           ×   4 2 8 3
                                        
                           6   × 9 7 1
                           5   0 × 4 1
                                        
                           6   7 9 × 3
                           5   8 3 7 × 
                           
     Íàçîâåì ýòó ìàòðèöó ìàòðèöåé ñòîèìîñòåé è áóäåì îáîçíà-
÷àòü áóêâîé Ñ. Îáû÷íî ñ÷èòàþò, ÷òî íîìåð ñòðîêè ìàòðèöû óêà-
çûâàåò, îòêóäà ìû åäåì, à íîìåð ñòîëáöà — êóäà. Òàê, ñòîèìîñòü
ïåðååçäà èç ãîðîäà 1 â ãîðîä 2 îïðåäåëÿåòñÿ ýëåìåíòîì ñ12, îí
ðàñïîëîæåí â 1-é ñòðîêå è 2-ì ñòîëáöå. Ýòà ñòîèìîñòü ðàâíà 4 (ñ12
= 4). Íà äèàãîíàëè ÷èñåë íåò, òàê êàê äèàãîíàëüíûé ýëåìåíò
ñîîòâåòñòâóåò ïåðååçäó èç ãîðîäà â òîò æå ãîðîä. Èíîãäà êðåñòè-
êè ìîæíî ñ÷èòàòü íóëÿìè, èíîãäà áåñêîíå÷íîñòüþ. Ìàòðèöà ìî-
æåò íå áûòü ñèììåòðè÷íîé, òàê êàê ñòîèìîñòü ïðîåçäà èç À â Â
íå âñåãäà ðàâíà ñòîèìîñòè ïðîåçäà èç  â À. Íå îãðàíè÷èâàÿ
îáùíîñòè, ìîæíî ñ÷èòàòü, ÷òî îáúåçä íà÷èíàåòñÿ èç 1-ãî ãîðîäà.
     Äàäèì ôîðìàëüíóþ ïîñòàíîâêó çàäà÷è.
     Çàäàíî ÷èñëî n è ìàòðèöà Ñ(n×n). Íàçîâåì ïåðåñòàíîâêîé
÷èñåë {1, 2,... , n} n-ìåðíûé âåêòîð õ = (x1, x2, x3,...…, xn) òàêîé, ÷òî

                                   80