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

     ×òî ïðîèçîéäåò, åñëè ìû îò êàêîé-íèáóäü ñòðîêè ìàòðèöû
Ñ îòíèìåì ÷èñëî à? Òàê êàê â ýòîé ñòðîêå äîëæåí áûòü âûáðàí
îäèí è òîëüêî îäèí ýëåìåíò, òî ñòîèìîñòü ëþáîãî âàðèàíòà íà-
çíà÷åíèé óìåíüøèòñÿ íà à. Íî åñëè ñòîèìîñòü ëþáîãî âàðèàíòà
èçìåíèëàñü íà îäíó è òó æå âåëè÷èíó, òî îòíîøåíèå ïðåäïî÷òå-
íèÿ ìåæäó âàðèàíòàìè íå èçìåíèëîñü. Åñëè äâà âàðèàíòà ñòîèëè
ïî ñòàðîé ìàòðèöå îäèíàêîâî, òî îíè áóäóò ñòîèòü îäèíàêîâî è
ïî íîâîé ìàòðèöå. Åñëè îäèí èç ñðàâíèâàåìûõ âàðèàíòîâ ïî ñòà-
ðîé ìàòðèöå ñòîèë ìåíüøå (áîëüøå) äðóãîãî, òî è ïî íîâîé
ìàòðèöå îí ñòîèò íà òó æå âåëè÷èíó ìåíüøå (áîëüøå). Ýòè ðàñ-
ñóæäåíèÿ ÿâëÿþòñÿ îáîñíîâàíèåì äëÿ ñëåäóþùèõ ïðåîáðàçîâà-
íèé ìàòðèöû ñòîèìîñòåé Ñ.
     Ýêâèâàëåíòíûå ïðåîáðàçîâàíèÿ. Ìû èìååì ïðàâî îò ëþáîé
ñòðîêè (ñòîëáöà) ìàòðèöû Ñ îòíÿòü (ïðèáàâèòü) ëþáîå ÷èñëî.
Ðåøåíèå, îïòèìàëüíîå äëÿ îäíîé ìàòðèöû, îñòàåòñÿ îïòèìàëü-
íûì äëÿ âñåõ ìàòðèö, ïîëó÷àåìûõ ïðè ëþáîé ïîñëåäîâàòåëüíîñòè
ýêâèâàëåíòíûõ ïðåîáðàçîâàíèé ìàòðèöû Ñ.
     Ïðè ðåøåíèè âåíãåðñêèì àëãîðèòìîì çàäà÷è î íàçíà÷åíèÿõ
íà ìèíèìóì ìû, èìåÿ â âèäó ëåììó îá îïòèìàëüíîñòè, áóäåì
ðàáîòàòü ñ ìàòðèöàìè áåç îòðèöàòåëüíûõ ýëåìåíòîâ è âûáèðàòü â
ýòèõ ìàòðèöàõ òîëüêî íóëåâûå ýëåìåíòû. Åñëè ìû ñìîæåì âûá-
ðàòü ïî îäíîìó íóëåâîìó ýëåìåíòû â êàæäîé ñòðîêå è êàæäîì
ñòîëáöå ìàòðèöû (ìîæåò áûòü óæå ïðåîáðàçîâàííîé ñ ïîìîùüþ
ýêâèâàëåíòíûõ ïðåîáðàçîâàíèé), òî ìû íàøëè îïòèìàëüíîå ðå-
øåíèå êàê äëÿ ïîñëåäíåé, òàê è äëÿ ïåðâîíà÷àëüíîé ìàòðèöû.
Åñëè ìû íå ñìîæåì âûáðàòü ðåøåíèå, ñîñòîÿùåå òîëüêî èç íó-
ëåâûõ ýëåìåíòîâ, òî ìàòðèöó íàäî ïðåîáðàçîâàòü.
  Àëãîðèòì ðåøåíèÿ çàäà÷è î íàçíà÷åíèÿõ íà ìèíèìóì
     Øàã 1. Ïðåîáðàçóåì ìàòðèöó. Îò êàæäîé ñòðîêè îòíèìåì
ìèíèìàëüíûé ýëåìåíò ýòîé ñòðîêè. Â ðåçóëüòàòå âñå ýëåìåíòû
ìàòðèöû áóäóò íåîòðèöàòåëüíû, è â êàæäîé ñòðîêå ïîÿâèòñÿ
õîòÿ áû îäèí íóëü.
     Øàã 2. Àíàëîãè÷íî âû÷èòàåì ìèíèìàëüíûé ýëåìåíò èç êàæ-
äîãî ñòîëáöà ïîëó÷èâøåéñÿ ìàòðèöû.  ðåçóëüòàòå â êàæäîì ñòîë-
áöå è â êàæäîé ñòðîêå ïîÿâèëñÿ õîòÿ áû îäèí 0.
     Øàã 3. Îñóùåñòâëÿåì íàçíà÷åíèÿ, âûáèðàÿ è îòìå÷àÿ çâåç-
äî÷êîé íóëè, ñòîÿùèå â ðàçíûõ ñòðîêàõ è ðàçíûõ ñòîëáöàõ. Íóëè



                              45