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

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

                              1




                                           4


                              5


                                           3


                                  2

                        Дерево вариантов



                                      86