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

ñòðîêó. Ýòî ïåðåðàñïðåäåëåíèå çâåçäî÷åê ìîæåò çàòðîíóòü è äðó-
ãèå ïîìå÷åííûå ñòðîêè è ñòîëáöû. Åñëè â ïîìå÷åííîì ñòîëáöå
íåò çâåçäî÷êè, òî åå äîëæíà äàòü òà ñòðîêà, êîòîðàÿ åãî ïîìåòè-
ëà. Åñëè â ñòðîêå îêàæåòñÿ áîëåå îäíîé çâåçäî÷êè, òî íàäî óáðàòü
çâåçäî÷êó ó ñòîëáöà, ïîìåòèâøåãî ýòó ñòðîêó. Ïðè ýòîì ñòðîêè è
ñòîëáöû, ïîëó÷èâøèå çâåçäî÷êó îäèí ðàç, âñåãäà îñòàíóòñÿ ñî
çâåçäî÷êîé. Îíà ìîæåò ïåðåéòè íà äðóãîå ìåñòî â ñòðîêå èëè
ñòîëáöå, íî íå äîëæíà ïðîïàñòü.
      Åñëè, â ðåçóëüòàòå ïåðåðàñïðåäåëåíèÿ, ÷èñëî îòìå÷åííûõ
çâåçäî÷êàìè íóëåé ñòàíåò ðàâíî n, òî çàäà÷à ðåøåíà. Åñëè æå
ìåíüøå n, òî íåîáõîäèìî ïîâòîðèòü ñíà÷àëà øàã 4.
      Ñèòóàöèÿ «óçêîå ìåñòî». Îíà âîçíèêàåò â òîì ñëó÷àå, åñëè
ïðîöåäóðà ðàññòàíîâêè ìåòîê çàâåðøèëàñü, íî ïðè ýòîì íå áûë
îòìå÷åí íè îäèí «íåäîâîëüíûé» ñòîëáåö.  ýòîì ñëó÷àå ÷èñëî
ïîìå÷åííûõ ñòðîê áîëüøå ÷èñëà ïîìå÷åííûõ ñòîëáöîâ. Ïîýòîìó
ïî äàííîé ìàòðèöå îñóùåñòâèòü âñå íàçíà÷åíèÿ ïî íóëåâûì ýëå-
ìåíòàì íåâîçìîæíî. Èçìåíèì ìàòðèöó ñòîèìîñòåé. Íàéäåì ìè-
íèìàëüíûé ýëåìåíò ñðåäè ÷èñåë, ñòîÿùèõ â îòìå÷åííûõ ñòðîêàõ
âíå îòìå÷åííûõ ñòîëáöîâ. Ýòîò ýëåìåíò âû÷òåì îò âñåõ îòìå÷åí-
íûõ ñòðîê è ïðèáàâèì êî âñåì îòìå÷åííûì ñòîëáöàì.  ðåçóëüòà-
òå â ìàòðèöå ïîÿâÿòñÿ íîâûå íóëè. Âåðíåìñÿ ê øàãó 3 6 .
      Ïðèìåð. Ïðåäïîëîæèì, ðåøàÿ çàäà÷ó î íàçíà÷åíèÿõ, ïîëó-
÷èëè ñëåäóþùóþ ìàòðèöó.
                     2     0*   3    5 7
                                          
                     0     3    4    6 2
                      0*   3    1    1 1 .
                                          
                     5     1    4    0 0* 
                                          
                     0     1    0*   5 0
     Çäåñü íàì óäàëîñü ðàññòàâèòü âñåãî 4 çâåçäî÷êè. Ñíà÷àëà ìû
îòìåòèì ñòðîêó 2, êîòîðîé íå õâàòèëî 0*. Èç-çà íåå ìû îòìåòèì
ñòîëáåö 1. Çàòåì îòìåòèì òðåòüþ ñòðî÷êó. Áîëüøå îòìåòèòü íè÷å-
ãî íåëüçÿ. Îòìå÷åí ñòîëáåö 1, íî åãî íåëüçÿ íàçâàòü íåäîâîëü-
íûì. Ïîýòîìó èìååò ìåñòî ñèòóàöèÿ «óçêîå ìåñòî».
__________________


       Ìîæíî ïåðåéòè ê øàãó 4 è ïðåîáðàçîâàòü ðåøåíèå. Äîëæíà
        6

âîçíèêíóòü ñèòóàöèÿ ïðîðûâà. Ïåðåéäÿ ê øàãó 3, ìû ïðîñòî îòáðîñè-
ëè ñòàðîå ðåøåíèå è íà÷àëè ïîèñê íîâîãî.

                                 48