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

                         Ìåòîä ïîòåíöèàëîâ
      Ïóñòü íàéäåí íåêîòîðûé ïëàí X. Ïîïðîáóåì äîêàçàòü åãî
îïòèìàëüíîñòü. Äëÿ ýòîãî ïðåîáðàçóåì ìàòðèöó ñòîèìîñòåé òàê,
÷òîáû âñå ïåðåâîçêè îñóùåñòâëÿëèñü ïî ýëåìåíòàì íóëåâîé ñòî-
èìîñòè. Òîãäà ýòîò ïëàí ïî íîâîé ìàòðèöå áóäåò èìåòü íóëåâóþ
ñòîèìîñòü. Åñëè â ïðåîáðàçîâàííîé ìàòðèöå ñòîèìîñòåé íå îêà-
æåòñÿ îòðèöàòåëüíûõ ýëåìåíòîâ, òî ñîãëàñíî ëåììå îá îïòèìàëü-
íîñòè ýòîò ïëàí îïòèìàëåí.
      Ðàññìîòðèì ñëåäóþùåå ïðåîáðàçîâàíèå ìàòðèöû ñòîèìîñ-
òåé. Âû÷òåì èç êàæäîé ñòðîêè i íåêîòîðîå αi, à èç êàæäîãî ñòîë-
áöà j íåêîòîðîå βj. αi è βj âûáåðåì òàê, ÷òîáû äëÿ ëþáîé íåíóëå-
âîé ïåðåâîçêè õij âûïîëíÿëîñü ðàâåíñòâî
                              α i + β j = cij .
     ×èñëà α1, α2,..., αm, β1, β2,..., βn îáû÷íî íàçûâàþò ïîòåíöèàëà-
ìè ñòðîê è ñòîëáöîâ, à ñàì ìåòîä — ìåòîäîì ïîòåíöèàëîâ. Âûïè-
ñûâàÿ ñîîòâåòñòâóþùåå óðàâíåíèå äëÿ êàæäîé íåíóëåâîé ïåðå-
âîçêè, ïîëó÷àåì ñèñòåìó ëèíåéíûõ óðàâíåíèé.  ýòîé ñèñòåìå
÷èñëî ïåðåìåííûõ ðàâíî (m + n), à ÷èñëî óðàâíåíèé ðàâíî ÷èñëó
íåíóëåâûõ ïåðåâîçîê íàøåãî ïëàíà.
     Ïðîàíàëèçèðóåì ïîëó÷åííóþ ñèñòåìó. Ìîæåò ëè ýòà ñèñòå-
ìà èìåòü åäèíñòâåííîå ðåøåíèå? Íåò! Åñëè ïîòåíöèàëû âñåõ ñòðîê,
òî åñòü âñå αi, óâåëè÷èòü, íàïðèìåð, íà 5, à ïîòåíöèàëû âñåõ
ñòîëáöîâ, òî åñòü âñå βj, óìåíüøèòü íà 5, òî íîâûå ïîòåíöèàëû
òîæå óäîâëåòâîðÿþò âñåì óðàâíåíèÿì ñèñòåìû. Åñëè ýòà ñèñòåìà
èìååò õîòÿ áû îäíî ðåøåíèå, òî îíà èìååò áåñêîíå÷íîå ìíîæå-
ñòâî ðåøåíèé.
     Íàéäåì êàêîå-ëèáî ÷àñòíîå ðåøåíèå ñèñòåìû. Íàïðèìåð,
ïîëîæèì 10 α1 = 0. Íà êàæäîì ñëåäóþùåì øàãå âûáèðàåì óðàâíå-
íèå, â êîòîðîì îäíà ïåðåìåííàÿ óæå îïðåäåëåíà, à äðóãàÿ åùå
íåò, è îïðåäåëÿåì íîâóþ ïåðåìåííóþ. Ðåøèâ ñèñòåìó, âû÷òåì
îò êàæäîé ñòðîêè è êàæäîãî ñòîëáöà ìàòðèöû ñîîòâåòñòâóþùèé
ïîòåíöèàë. Ìàòðèöà ñòîèìîñòåé èçìåíèòñÿ. Â íåé ïîÿâÿòñÿ íóëå-
âûå ñòîèìîñòè òàì, ãäå èìåþòñÿ íåíóëåâûå ïåðåâîçêè. Ñòîèìîñòü
ýòîãî ïëàíà ïî ýòîé èçìåíåííîé ìàòðèöå ðàâíà 0.  ñëó÷àå îòñóò-
ñòâèÿ â ìàòðèöå ñòîèìîñòåé îòðèöàòåëüíûõ ýëåìåíòîâ íàéäåí-
íûé ïëàí îïòèìàëåí.
__________________

        10
             Ìîæíî ïðîèçâîëüíîå çíà÷åíèå.

                                    62