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

                               0 20 0 30 
                      (3)                
                     Х      =  0 20 0 0  .
                                         
                               10 0 15 5 
     Â ïëàíå Õ(3) âñå ïðÿìîóãîëüíèêè ïðàâèëüíûå. Èòàê, åñëè â
ïëàíå èìåþòñÿ íåïðàâèëüíûå ïðÿìîóãîëüíèêè, òî îí íå îïòè-
ìàëåí. Ìîæíî ëè óòâåðæäàòü îáðàòíîå? Îêàçûâàåòñÿ, íåò. Âîç-
ìîæíà ñèòóàöèÿ, êîãäà âñå ïðÿìîóãîëüíèêè ïðàâèëüíûå, à ïëàí
íå ÿâëÿåòñÿ îïòèìàëüíûì.  ýòîì ñëó÷àå èçìåíåíèÿ äîëæíû çàò-
ðîíóòü áîëåå ÷åòûðåõ ýëåìåíòîâ ìàòðèöû ïåðåâîçîê.

                     Òî÷íûå àëãîðèòìû
     Ìû íàó÷èëèñü ðåøàòü òðàíñïîðòíóþ çàäà÷ó ýâðèñòè÷åñêè-
ìè àëãîðèòìàìè. Ñíà÷àëà ñ ïîìîùüþ æàäíîãî àëãîðèòìà ìû ïî-
ëó÷èëè ïåðâîíà÷àëüíûé ïëàí, à ïîòîì ñ ïîìîùüþ ëîêàëüíîãî
àëãîðèòìà (èñïðàâëåíèå íåïðàâèëüíûõ ïðÿìîóãîëüíèêîâ) ïîïû-
òàëèñü åãî óëó÷øèòü. Íî îòñóòñòâèå íåïðàâèëüíûõ ïðÿìîóãîëü-
íèêîâ íå ãàðàíòèðóåò îïòèìàëüíîñòü íàéäåííîãî ðåøåíèÿ.
     Íèæå ìû ðàññìîòðèì äâà òî÷íûõ àëãîðèòìà — ìåòîä ïîòåí-
öèàëîâ è âåíãåðñêèé àëãîðèòì. Îáà ìåòîäà ÿâëÿþòñÿ íåêîòîðîé
ìîäèôèêàöèåé ñèìïëåêñ-ìåòîäà äëÿ ðåøåíèÿ òðàíñïîðòíîé çà-
äà÷è. Íî èçëàãàþòñÿ ýòè ìåòîäû òàê, ÷òî çíàíèå ñèìïëåêñ-ìåòî-
äà íå ÿâëÿåòñÿ íåîáõîäèìûì äëÿ ïîíèìàíèÿ. Îáà ìåòîäà îïèðà-
þòñÿ íà ëåììó îá îïòèìàëüíîñòè è ýêâèâàëåíòíûå ïðåîáðàçîâà-
íèÿ ìàòðèöû ñòîèìîñòåé.
     Ëåììà îá îïòèìàëüíîñòè. Åñëè ñòîèìîñòü ïëàíà ïåðåâîçîê Õ,
ïîäñ÷èòàííàÿ ïî ìàòðèöå ñòîèìîñòåé Ñ, ðàâíà íóëþ, à â ìàòðèöå
Ñ íåò îòðèöàòåëüíûõ ýëåìåíòîâ, òî ýòîò ïëàí îïòèìàëåí.
     Ñóììàðíàÿ ñòîèìîñòü èçäåðæåê L îïðåäåëÿåòñÿ êàê ñóììà
ïðîèçâåäåíèé ñòîèìîñòè ñij íà ñîîòâåòñòâóþùóþ ïåðåâîçêó õij. Òàê
êàê âñå ïåðåâîçêè íåîòðèöàòåëüíû ïî óñëîâèÿì çàäà÷è, à ýëå-
ìåíòû ìàòðèöû ñòîèìîñòåé íåîòðèöàòåëüíû ïî óñëîâèþ ëåììû,
òî L =  ∑ c i j x i j íà ëþáîì ïëàíå. Ñëåäîâàòåëüíî, íóëåâîé
        i, j
(ïî ñòîèìîñòè) ïëàí îïòèìàëåí.
     Íà ïåðâûé âçãëÿä êàæåòñÿ, ÷òî ëåììà îá îïòèìàëüíîñòè
áåñïîëåçíà, òàê êàê â ðåàëüíîñòè íå áûâàåò ïëàíîâ ïåðåâîçîê ñ
íóëåâîé ñòîèìîñòüþ. ×òîáû åå ïðèìåíèòü, íàäî óìåòü ïðåîáðà-
çîâûâàòü ìàòðèöó ñòîèìîñòåé.

                                 60