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

     Åñëè â íîâîé ìàòðèöå ñòîèìîñòåé åñòü õîòÿ áû îäèí îò-
ðèöàòåëüíûé ýëåìåíò, òî óñëîâèÿ ëåììû íå âûïîëíåíû, è ìû
íå ìîæåì áûòü óâåðåíû â îïòèìàëüíîñòè íàøåãî ïëàíà. Ñòî-
èìîñòü ýòîãî ïëàíà ðàâíà íóëþ, íî ìîæåò ñóùåñòâîâàòü ïëàí
îòðèöàòåëüíîé ñòîèìîñòè (âî ìíîãèõ ñëó÷àÿõ îòðèöàòåëüíûå
ýëåìåíòû ñâèäåòåëüñòâóþò î íåçàìå÷åííûõ íåïðàâèëüíûõ ïðÿ-
ìîóãîëüíèêàõ).
     Âûáåðåì â òðàíñïîðòíîé òàáëèöå êëåòêó, êîòîðîé ñîîòâåò-
ñòâóåò îòðèöàòåëüíîå çíà÷åíèå â ìàòðèöå ñòîèìîñòåé. Íàì âû-
ãîäíî èçìåíèòü ïëàí, óâåëè÷èâ ïåðåâîçêó â ýòîé êëåòêå. Èçìå-
íèâ (óâåëè÷èâ èëè óìåíüøèâ) ïåðåâîçêó â êàêîé-òî êëåòêå, ìû
äîëæíû êîìïåíñèðîâàòü ýòî èçìåíåíèå (óìåíüøèâ èëè óâåëè-
÷èâ ñîîòâåòñòâåííî êàêóþ-òî ïåðåâîçêó â ýòîé ñòðîêå è êàêóþ-
òî ïåðåâîçêó â ýòîì ñòîëáöå). Êëåòêè, â êîòîðûõ èçìåíèëèñü
ïåðåâîçêè, îáðàçóþò öèêë. Öèêë — ýòî çàìêíóòàÿ ëîìàíàÿ ëè-
íèÿ, ñîñòîÿùàÿ èç ãîðèçîíòàëüíûõ è âåðòèêàëüíûõ îòðåçêîâ. Âåð-
øèíû ëîìàíîé íàõîäÿòñÿ â òåõ êëåòêàõ òàáëèöû, â êîòîðûõ íà-
õîäÿòñÿ íåíóëåâûå ïåðåâîçêè. Îòðåçêè ëîìàíîé ìîãóò ñîåäèíÿòü
òîëüêî ýëåìåíòû, èìåþùèå íåíóëåâûå ïåðåâîçêè è ñòîÿùèå â
îäíîì ñòîëáöå èëè â îäíîé ñòðîêå. Òàêîé öèêë îáÿçàòåëüíî ñó-
ùåñòâóåò, åñëè ïëàí áûë íåâûðîæäåííûé, òî åñòü ñîäåðæàë (n+m-
1) íåíóëåâóþ ïåðåâîçêó. Íàéäÿ òàêîé öèêë, ïîìå÷àåì åãî êëåòêè
çíàêàìè «+» è «-», íà÷èíàÿ ñî çíàêà «+» â íà÷àëüíîé êëåòêå ñ
îòðèöàòåëüíîé ñòîèìîñòüþ. Çàòåì çíàêè äîëæíû ÷åðåäîâàòüñÿ. Ìû
óâåëè÷èì ïåðåâîçêó âî âñåõ êëåòêàõ, ïîìå÷åííûõ çíàêîì «+», è
óìåíüøèì ïåðåâîçêó âî âñåõ êëåòêàõ, ïîìå÷åííûõ çíàêîì «-».
Èçìåíåíèå ïåðåâîçêè íàäî ñäåëàòü íà âåëè÷èíó ìèíèìàëüíîé èç
ïåðåâîçîê, îòìå÷åííûõ çíàêîì «-». Íîâûé ïëàí áóäåò èìåòü ìåíü-
øóþ ñòîèìîñòü.
     Ðàññìîòðèì ïðèìåð. Ïóñòü ïîñëå ïðåîáðàçîâàíèé ïîëó÷èëè
ñëåäóþùóþ òàáëèöó. ñ21 < 0. Ïîïðîáóåì óâåëè÷èòü ïåðåâîçêó õ21.
                  1        0        2        7            2
                       6                                      6
                 -2        5        0        0            6
             х 21              10        4                    14
                  0        3        4        2            0
             8                                   5            13
                 3         0        0        4            0
                      8        7                 9            24
             8        14       17        4           14


                                    64