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

      1-é ñòðîêå ìû îòìåòèëè 3-é ñòîëáåö. Çíà÷èò, êîììèâîÿ-
æåð èç ãîðîäà 1 ïîåäåò â ãîðîä 3. Â 3-é ñòðîêå ìû îòìåòèëè 2-é
ñòîëáåö. Çíà÷èò, êîììèâîÿæåð èç ãîðîäà 3 ïîåäåò â ãîðîä 2. Âî 2-é
ñòðîêå ìû îòìåòèëè 5-é ñòîëáåö. Çíà÷èò, êîììèâîÿæåð èç ãîðîäà
2 ïîåäåò â ãîðîä 5.  5-é ñòðîêå ìû îòìåòèëè 4-é ñòîëáåö. Çíà÷èò,
êîììèâîÿæåð èç ãîðîäà 5 ïîåäåò â ãîðîä 4. Â ñòðîêå 4 ìû îòìåòè-
ëè 1-é ñòîëáåö. Çíà÷èò, êîììèâîÿæåð èç ãîðîäà 4 ïîåäåò â ãîðîä
1. Äàííûå ïåðååçäû îáðàçóþò öèêë. Åãî äëèíà ïî ïîñëåäíåé ìàò-
ðèöå ðàâíà 0. Âñå ýëåìåíòû ìàòðèöû íåîòðèöàòåëüíû. Ïëàí çàâå-
äîìî îïòèìàëåí äëÿ ïðåîáðàçîâàííîé ìàòðèöû, çíà÷èò îí îïòè-
ìàëåí è äëÿ ïåðâîíà÷àëüíîé ìàòðèöû.
     Ðàññìîòðèì äðóãîé ïðèìåð. Ïóñòü ïîñëå ðåøåíèÿ çàäà÷è î
íàçíà÷åíèÿõ ìû ïîëó÷èëè ñëåäóþùóþ ìàòðèöó
                        ×    2    2    0*   2
                                               
                        2    ×    7    1    0*
                        3    0*   ×    0    2 .
                                               
                        0*   3    5    ×    0
                        0                   × 
                             5    0*   0
     Ðåøåíèå çàäà÷è î íàçíà÷åíèÿõ íå ìîæåò ðàññìàòðèâàòüñÿ
êàê ðåøåíèå çàäà÷è êîììèâîÿæåðà.  ñàìîì äåëå, â ñòðîêå 1 ìû
îòìåòèëè ñòîëáåö 4. Çíà÷èò, êîììèâîÿæåð èç ãîðîäà 1 ïîåäåò â
ãîðîä 4.  4-é ñòðîêå ìû îòìåòèëè ñòîëáåö 1. Çíà÷èò, êîììèâîÿ-
æåð èç ãîðîäà 4 ïîåäåò â ãîðîä 1. Ìû ïîëó÷èëè öèêë, íå îáúåõàâ
âñå ãîðîäà. Ïðîäîëæèì ïóòåøåñòâèå èç êàêîãî-íèáóäü äðóãîãî
ãîðîäà.  ñòðîêå 2 ìû îòìåòèëè ñòîëáåö 5. Çíà÷èò, êîììèâîÿæåð
èç ãîðîäà 2 ïîåäåò â ãîðîä 5. Â ñòðîêå 5 ìû îòìåòèëè 3-é ñòîëáåö.
Çíà÷èò, êîììèâîÿæåð èç ãîðîäà 5 ïîåäåò â ãîðîä 3.  ñòðîêå 3 ìû
îòìåòèëè ñòîëáåö 2. Çíà÷èò, êîììèâîÿæåð èç ãîðîäà 3 ïîåäåò â
ãîðîä 2. Ýòî ðåøåíèå çàäà÷è î íàçíà÷åíèÿõ ñîîòâåòñòâóåò íå îä-
íîìó, à äâóì öèêëàì. «1 → 4 → 1» è «2 → 5 → 3 → 2».
     Ïîïðîáóåì «ñêëåèòü» ýòè öèêëû. Íàïðèìåð, ýòî ìîæíî ñäå-
ëàòü ñ ïîìîùüþ ýâðèñòè÷åñêîãî àëãîðèòìà «èäè â áëèæàéøèé» .
Ïîëó÷èì öèêë «1 → 4 → 5 → 3 → 2 → 1». Åãî äëèíà ïî ïîñëå-
äíåé ìàòðèöå ðàâíà 2.
     Äëÿ ïîèñêà îïòèìàëüíîãî ðåøåíèÿ ïðèìåíèì ìåòîä âåò-
âåé è ãðàíèö. Â íåì ìû áóäåì ðèñîâàòü äåðåâî âàðèàíòîâ. Íî ìû
íå áóäåì ðèñîâàòü âñå âåòâè. Çàâåäîìî ïëîõèå âåòâè ìû áóäåì
îòáðàñûâàòü. Ýòî ìåòîä ðàçóìíîãî ïåðåáîðà.

                                   85