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

êàæäîå xi — ýòî öåëîå ÷èñëî îò 1 äî n è ïðè i ≠ j xi ≠ xj. Íà
ìíîæåñòâå âñåõ ïåðåñòàíîâîê ðàññìîòðèì ôóíêöèþ
                           n −1
                    f ( x) = ∑ cx x        + cx       cx   .
                           i =1   i i +1          n    1

     Ñòàâèòñÿ çàäà÷à: ìèíèìèçèðîâàòü ôóíêöèþ f(x) íà ìíîæå-
ñòâå ïåðåñòàíîâîê.
     Èíîãäà çàäà÷è ñ ðàçëè÷íûìè ñëîâåñíûìè ôîðìóëèðîâêàìè
ïðèâîäÿò ê îäíîé è òîé æå ìàòåìàòè÷åñêîé ìîäåëè. Ðàññìîòðèì
çàäà÷ó î ïåðåíàëàäêå ñòàíêà. Ïóñòü íà îäíîì ñòàíêå íàäî îáðàáî-
òàòü n äåòàëåé. Íàñ èíòåðåñóåò âðåìÿ âûïîëíåíèÿ çàäàíèÿ, êîòî-
ðîå ñêëàäûâàåòñÿ èç ñóììàðíîãî âðåìåíè, çàòðà÷åííîãî íà îáðà-
áîòêó âñåõ äåòàëåé è âðåìåíè, çàòðà÷åííîãî íà ïåðåíàëàäêè ñòàíêà.
Åñëè ñðàçó ïîñëå i-é äåòàëè îáðàáàòûâàåòñÿ j-ÿ äåòàëü, òî íåîá-
õîäèìî çàòðàòèòü âðåìÿ tij íà ïåðåíàëàäêó ñòàíêà.
     Íàäî âûáðàòü òàêîé ïîðÿäîê îáðàáîòêè äåòàëåé, ÷òîáû ñóì-
ìàðíîå âðåìÿ ïåðåíàëàäîê áûëî ìèíèìàëüíûì.
     Ñ ìàòåìàòè÷åñêîé òî÷êè çðåíèÿ çàäà÷à î ïåðåíàëàäêå ýêâè-
âàëåíòíà çàäà÷å êîììèâîÿæåðà. Äîñòàòî÷íî äåòàëè íàçâàòü ãîðî-
äàìè, à âðåìÿ ïåðåíàëàäêè âðåìåíåì èëè ñòîèìîñòüþ ïåðååçäà. Â
äàëüíåéøåì áóäåì ãîâîðèòü î çàäà÷å êîììèâîÿæåðà.
     Âåðíåìñÿ ê íàøåìó ïðèìåðó. Âûáåðåì íåêîòîðûé ñïîñîá
îáúåçäà ãîðîäîâ. Íàïðèìåð, ìîæíî ïðîåõàòü ïî ãîðîäàì â ïîðÿä-
êå âîçðàñòàíèÿ èõ íîìåðîâ. Òàêîìó îáúåçäó ñîîòâåòñòâóåò ïåðå-
ñòàíîâêà õ = (1, 2, 3, 4, 5).
                   4   9    4  3   5
                 1 → 2 → 3 → 4 → 5 → 1
      Çäåñü ñòðåëêè îçíà÷àþò ïóòü èç ãîðîäà â ãîðîä. Íàä ñòðåë-
êîé íàïèñàíà ñòîèìîñòü ïåðååçäà. Ñóììàðíàÿ ñòîèìîñòü ýòîãî âà-
ðèàíòà îáúåçäà
    f(x) = ñ12 + ñ23 + ñ34 + ñ45 + ñ51 = 4 + 9 + 4 + 3 + 5 = 25.
      Ìû ðàññìîòðåëè ïðîèçâîëüíûé îáúåçä. Ìàëîâåðîÿòíî, ÷òî
îí áóäåò íàèëó÷øèì. Ïîïðîáóåì äåéñòâîâàòü èíà÷å, ðàññ÷èòûâàÿ
íà áîëåå óäà÷íîå ðåøåíèå. Ñòîèìîñòè ïåðååçäà èç 1-ãî ãîðîäà óêà-
çàíû â ïåðâîé ñòðîêå ìàòðèöû ñòîèìîñòåé. Â 1-é ñòðîêå ìèíè-
ìàëüíûé ýëåìåíò ðàâåí 2, ýòî ýëåìåíò ñ13. Òîãäà èç ãîðîäà 1 ïî-
åäåì â ãîðîä 3. Â 3-é ñòðîêå ìèíèìàëüíûé ýëåìåíò ðàâåí 0, ýòî ñ32.
Òîãäà èç ãîðîäà 3 ïîåäåì â ãîðîä 2. Âî 2-é ñòðîêå ìèíèìàëüíûé
ýëåìåíò ðàâåí 1, ýòî ñ25. Òîãäà èç ãîðîäà 2 ïîåäåì â ãîðîä 5. Â

                                  81