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

                        0 20 0 30 
                                  
                        0 20 0 0  .
                        10 0 15 5 
                                  
     ×èñëî íåíóëåâûõ ïåðåâîçîê ðàâíî 6. Ýòî ðàâíî ÷èñëó ñòðîê
ïëþñ ÷èñëî ñòîëáöîâ ìèíóñ 1. Âû÷åðêíåì ñòðîêó 2, ñòîëáåö 1,
ñòîëáåö 3. Ïîñëå âû÷åðêèâàíèÿ ïîÿâèëèñü íîâûå ñòðîêè è ñòîëá-
öû ñ îäíîé íåíóëåâîé ïåðåâîçêîé. Ñîõðàíÿÿ ïðåæíþþ íóìåðà-
öèþ, âû÷åðêíåì ñòîëáåö 2 è ñòðîêó 3.  ìàòðèöå îñòàëñÿ îäèí
íåíóëåâîé ýëåìåíò à14, âû÷åðêíåì è åãî. Ìàòðèöà ðàçâàëèëàñü.
Ñèñòåìà óðàâíåíèé (6) ðàçðåøèìà.
     Åñëè íåíóëåâûõ ïåðåâîçîê â ïëàíå áîëüøå, ÷åì (n+m-1), òî
ìàòðèöà íàâåðíÿêà íå ðàçâàëèòñÿ, òî åñòü ìû íå ñìîæåì óäàëèòü
âñå ñòðî÷êè è ñòîëáöû.  îñòàâøåéñÿ ÷àñòè ìàòðèöû îáÿçàòåëüíî
ñóùåñòâóåò öèêë. Âûäåëèì åãî. Îòìåòèì âåðøèíû öèêëà çíàêàìè
«+» è «-», ÷åðåäóÿ èõ. ×èñëî òåõ è äðóãèõ â öèêëå âñåãäà îäèíà-
êîâî. Ïîäñ÷èòàåì ñóììó ñòîèìîñòåé âî âñåõ âåðøèíàõ, îòìå÷åí-
íûõ îäèíàêîâûìè çíàêàìè. Ñðàâíèì èõ è âûáåðåì áîëüøóþ ñóììó.
Óìåíüøèì âñå ïåðåâîçêè â âåðøèíàõ ñ òåì çíàêîì, êîòîðîìó
ñîîòâåòñòâóåò áîëüøàÿ ñóììà. Óìåíüøåíèå ïðîèçâåäåì íà ìèíè-
ìàëüíóþ ïåðåâîçêó ñðåäè ýòèõ âåðøèí.  âåðøèíàõ, îòìå÷åííûõ
äðóãèì çíàêîì, ïåðåâîçêè óâåëè÷èì íà òó æå âåëè÷èíó. Íàïðè-
ìåð, åñëè ñóììàðíàÿ ñòîèìîñòü áîëüøå ó ïëþñîâ, òî ìû ïîëó-
÷èì ïëàí ìåíüøåé ñòîèìîñòè, åñëè óìåíüøèì ïåðåâîçêè ó âñåõ
ïëþñîâ è óâåëè÷èì ïåðåâîçêè ó âñåõ ìèíóñîâ. Åñëè ñóììû ñòî-
èìîñòåé îäèíàêîâû, òî âûáåðåì ñóììó ñ ïðîèçâîëüíûì çíàêîì
è ïðîäåëàåì òàêèå æå äåéñòâèÿ. Âî âñåõ ñëó÷àÿõ èçìåíåíèå ïåðå-
âîçîê äåëàåòñÿ íà âåëè÷èíó, ìèíèìàëüíóþ èç óìåíüøàåìûõ ïå-
ðåâîçîê. Ýòà ïðîöåäóðà àíàëîãè÷íà èñïðàâëåíèþ íåïðàâèëüíûõ
ïðÿìîóãîëüíèêîâ.
     Ïðè ïîÿâëåíèè â ìàòðèöå ñòîèìîñòåé îòðèöàòåëüíûõ ýëå-
ìåíòîâ, äîáàâëÿåì ê êëåòêàì ñ íåíóëåâûìè ïåðåâîçêàìè êëåòêó
ñ îòðèöàòåëüíîé ñòîèìîñòüþ è èùåì öèêë. Äëÿ ïîèñêà öèêëà
ìîæíî ñíîâà ïðèìåíèòü ïðîöåäóðó ðàçâàëà. Åñëè ãðàô ðàçâàëèò-
ñÿ ïîëíîñòüþ, òî öèêëà íåò.  ýòîì ñëó÷àå íàäî äîáàâèòü ýòó
êëåòêó ê ñèñòåìå óðàâíåíèé äëÿ ïîèñêà ïîòåíöèàëîâ è çàíîâî
ðåøèòü ñèñòåìó. Åñëè öèêë íàéäåí, òî ïåðåðàñïðåäåëèì ïåðåâîçêè.




                              67