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

7   9   3   4   0           7    9        3    4   0        5   8    3    4    0* 
                                                                                  
8   5   1   2   4 − 1       7    4        0    1   3        5   3    0*   1    3
6   3   2   5   3 − 2   ⇒   4    1        0    3   1   ⇒    2   0*   0    3    1 .
                                                            *                     
3   7   1   8   6 − 1       2    6        0    7   5       0    5    0    7    5
                                                                                  
5   4   2   0   3           5    4        2    0   3        3   3    2    0*   3
                               −2       −1
     Ìû ñìîãëè îòìåòèòü ïÿòü íóëåé, ñòîÿùèõ â ðàçíûõ ñòîëá-
öàõ è ðàçíûõ ñòðîêàõ. Ñëåäîâàòåëüíî, çàäà÷à ðåøåíà.  ïåðâîé
ñòðîêå îòìå÷åí íóëü â 5 ñòîëáöå. Ïîýòîìó ïåðâîãî ÷åëîâåêà íà-
çíà÷èì íà 5 äîëæíîñòü. Âî âòîðîé ñòðîêå îòìå÷åí íóëü â òðåòüåì
ñòîëáöå. Ïîýòîìó âòîðîãî ÷åëîâåêà íàçíà÷èì íà òðåòüþ äîëæ-
íîñòü, 3-ãî íà âòîðóþ, 4-ãî íà ïåðâóþ è, íàêîíåö, 5-ãî íà 4-þ.
Çíà÷åíèå öåëåâîé ôóíêöèè áóäåò ìèíèìàëüíûì. Âû÷èñëèì åãî
ïî ïåðâîíà÷àëüíîé ìàòðèöå
     L = a 15 + a 23 + a 32 + a 41 + a 54 = 0 + 1 + 3 + 3 + 0 = 7 .
      Íå âñåãäà ðåøåíèå ïîëó÷àåòñÿ òàê ñðàçó. Ðàññìîòðèì äàëü-
íåéøèå øàãè àëãîðèòìà.
      Øàã 4. «Ðàññòàíîâêà ìåòîê». Ñòðîêè è ñòîëáöû, â êîòîðûõ
íåò îòìå÷åííûõ çâåçäî÷êîé íóëåé, áóäåì íàçûâàòü «íåäîâîëü-
íûìè».
      Îòìåòèì «íåäîâîëüíóþ» ñòðîêó.
      4.1. Åñëè îòìå÷åíà ñòðîêà, òî îòìåòèì âñå òå ñòîëáöû, ó
êîòîðûõ â äàííîé ñòðîêå åñòü íóëè.
      4.2. Åñëè îòìå÷åí êàêîé-ëèáî ñòîëáåö, òî îòìåòèì òó ñòðî-
êó, ó êîòîðîé â ýòîì ñòîëáöå åñòü 0*.
      Øàãè 4.1 è 4.2 ïîâòîðÿþòñÿ äî òåõ ïîð, ïîêà â ýòîé ïðîöå-
äóðå ïîÿâëÿþòñÿ íîâûå ñòðîêè è ñòîëáöû.
      Çäåñü ìîãóò âîçíèêàòü äâå ðàçëè÷íûå ñèòóàöèè. Íàçîâåì èõ
ñèòóàöèåé «ïðîðûâà» è ñèòóàöèåé «óçêîå ìåñòî».
      Ñèòóàöèÿ «ïðîðûâà». Òàêàÿ ñèòóàöèÿ âîçíèêàåò â òîì ñëó-
÷àå, åñëè, íà÷àâ ñî ñòðîêè, ìû â êàêîé-òî ìîìåíò îòìåòèëè
«íåäîâîëüíûé» ñòîëáåö. Ýòî çíà÷èò, ÷òî ìû íå î÷åíü óäà÷íî âû-
áèðàëè íóëè. Èç èìåþùèõñÿ íóëåé ìîæíî áûëî âûáðàòü è îòìå-
òèòü áîëüøå íóëåé, ÷åì ìû âûáðàëè. Ïîêàæåì, êàê ïåðåðàñïðå-
äåëèòü ÷àñòü çâåçäî÷åê è íàçíà÷èòü åùå îäíó. Ïîìå÷åííîìó «íå-
äîâîëüíîìó» ñòîëáöó äîëæíà äàòü çâåçäî÷êó òà ñòðîêà, êîòîðàÿ
åãî ïîìåòèëà. Åñëè ïðè ýòîì â ñòðîêå îêàæåòñÿ áîëåå îäíîé çâåç-
äî÷êè, òî íàäî óáðàòü çâåçäî÷êó â ñòîëáöå, ïîìåòèâøåì ýòó

                                                 47