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

      Äëÿ óìåíüøåíèÿ ïåðåáîðà ðåêîìåíäóåòñÿ ïðåîáðàçîâàòü ìàò-
ðèöó ñòîèìîñòåé. Ýòî ìîæíî ñäåëàòü, ïðèìåíÿÿ òå æå ïðîöåäó-
ðû, êîòîðûå èñïîëüçîâàëèñü ïðè ðåøåíèè çàäà÷è î íàçíà÷åíèÿõ
âåíãåðñêèì àëãîðèòìîì.
      Çàäà÷à êîììèâîÿæåðà òåñíî ñâÿçàíà ñ çàäà÷åé î íàçíà÷åíè-
ÿõ. Äàííûå îïðåäåëÿþòñÿ ìàòðèöåé, êàæäûé ýëåìåíò êîòîðîé
çàäàåò ñòîèìîñòü ñîîòâåòñòâóþùåãî ïåðååçäà èç îäíîãî ïóíêòà â
äðóãîé. Êîììèâîÿæåð äîëæåí ïðèåõàòü â êàæäûé ãîðîä ðîâíî
îäèí ðàç è ðîâíî îäèí ðàç äîëæåí âûåõàòü èç êàæäîãî ãîðîäà.
Åñëè ìû îòìåòèì â ìàòðèöå ñäåëàííûå ïîåçäêè, òî â êàæäîé
ñòðîêå è êàæäîì ñòîëáöå áóäåò âûáðàí ðîâíî îäèí ýëåìåíò. Ïî-
ýòîìó ëþáîå äîïóñòèìîå ðåøåíèå çàäà÷è î êîììèâîÿæåðå äàåò
íàì äîïóñòèìîå ðåøåíèå çàäà÷è î íàçíà÷åíèÿõ. Îáðàòíîå íåâåðíî,
òàê êàê åñëè ïåðâîãî ÷åëîâåêà íàçíà÷èòü íà 2 äîëæíîñòü, à âòî-
ðîãî íà ïåðâóþ, òî êîììèâîÿæåð äîëæåí áûë áû èç ãîðîäà 1
åõàòü â 2, à èç 2 â 1, ÷òî íåâîçìîæíî.
      Êàê è ïðè ðåøåíèè çàäà÷è î íàçíà÷åíèÿõ, ìû èìååì ïðàâî
ïðèáàâëÿòü ê ñòðîêàì è ñòîëáöàì ìàòðèöû ñòîèìîñòåé ïðîèç-
âîëüíûå ÷èñëà. Ïðè òàêèõ ïðåîáðàçîâàíèÿõ ìíîæåñòâî âîçìîæ-
íûõ âàðèàíòîâ íå ìåíÿåòñÿ, à öåëåâàÿ ôóíêöèÿ ìåíÿåòñÿ íà êîí-
ñòàíòó. Ïëàí, îïòèìàëüíûé äëÿ íîâîé ìàòðèöû, îïòèìàëåí äëÿ
ñòàðîé è íàîáîðîò.
      Îò êàæäîé ñòðîêè âû÷èòàåì åå ìèíèìàëüíûé ýëåìåíò, ñ÷è-
òàÿ, ÷òî íà äèàãîíàëè ñòîÿò áåñêîíå÷íîñòè. Çàòåì âû÷òåì ìèíè-
ìàëüíûé ýëåìåíò èç òåõ ñòîëáöîâ, ãäå íåò 0.
×   4 2 8 3     -2   ×    2   0   6    1          ×   2 0 2 1        ×    2 0* 2 2
                                                                                    
6   × 9 7 1     -1   5    ×   8   6    0          3   × 8 2 0  -1    2    ×   71 0*
5   0 × 4 1     -0   5    0   ×   4    1          3   0 × 0 1        3    0* × 0 2 
                -3                                                                  
6   7 9 × 3          3    4   6   ×    0          1   4 6 × 0        0*   3 5 × 0
5                                                                    -1
     8 3 7 ×         2                 × 
                  -3                                  0
                           5   3   4                    5 3 0 ×       0
                                                                                5 0 0* × 
                        -2           -4                            +1
     Ïîñëå ïåðâîãî ïðåîáðàçîâàíèÿ, âòîðàÿ è ÷åòâåðòàÿ ñòðîêà
ïðåòåíäîâàëè íà 5-é ñòîëáåö. ×òîáû â ýòèõ ñòðîêàõ ïîÿâèëèñü
åùå íóëè, ìû îòíÿëè 1 îò 2-é è 4-é ñòðîêè è ïðèáàâèëè 1 ê 5-
ìó ñòîëáöó. Âûáèðàÿ åäèíñòâåííûå íóëè â ñòðîêàõ è ñòîëáöàõ,
óäàëîñü ïîìåòèòü 5 íóëåé, ñòîÿùèõ â ðàçíûõ ñòðîêàõ è ñòîëáöàõ.
Ìû ðåøèëè çàäà÷ó î íàçíà÷åíèÿõ, íî ñîîòâåòñòâóåò ëè ýòî ðåøå-
íèå çàäà÷è î íàçíà÷åíèÿõ ðåøåíèþ çàäà÷è êîììèâîÿæåðà?


                                                 84