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

UptoLike

ВУЗ: 

ВолГУ | Волгоград

Составители: 

Рубрика: 

73
Àëãîðèòì ðàññòàíîâêè ìåòîê ïðèâîäèò ê îäíîé èç äâóõ ñè-
òóàöèé. Îäíó èç íèõ íàçîâåì ñèòóàöèåé ïðîðûâà. Îíà âîçíèêàåò â
òîì ñëó÷àå, åñëè ìû ïîìåòèëè «íåäîâîëüíûé» ñòîëáåö. Ýòî îçíà-
÷àåò, ÷òî ìû ïëîõî ðàñïðåäåëèëè ïåðåâîçêè ïî èìåþùèìñÿ íóëÿì.
Ïëàí ïåðåâîçîê áóäåò èçìåíåí è îáùåå êîëè÷åñòâî ïåðåâåçåííîãî
òîâàðà áóäåò óâåëè÷åíî. Äðóãóþ ñèòóàöèþ íàçîâåì «óçêîå ìåñòî».
 ýòîì ñëó÷àå ïî èìåþùèìñÿ íóëÿì íåâîçìîæíî ðåàëèçîâàòü âñå
ïåðåâîçêè.  ýòîì ñëó÷àå ìàòðèöà ñòîèìîñòåé áóäåò ïðåîáðàçî-
âàíà. Â ìàòðèöå ïîÿâÿòñÿ íîâûå íóëè, à ñòîèìîñòü ëþáîãî ïëàíà
ïî íîâîé ìàòðèöå áóäåò ìåíüøå, ÷åì ïî ñòàðîé. Ðàññìîòðèì êàæ-
äóþ èç ýòèõ ñèòóàöèé áîëåå ïîäðîáíî.
D
1
) Ñèòóàöèÿ «ïðîðûâà». Ïåðåðàñïðåäåëèì ïåðåâîçêè. Íà
ïåðåñå÷åíèè «íåäîâîëüíîãî» ñòîëáöà è ñòðîêè, èç-çà êîòîðîé îí
áûë îòìå÷åí, ïåðåâîçêó óâåëè÷èì. ×òîáû ñîõðàíèòü âåëè÷èíó
ïåðåâîçêè â ýòîé ñòðîêå, óìåíüøèì ïåðåâîçêó â ñòðîêå è ñòîëá-
öå, èç-çà êîòîðîãî îíà áûëà îòìå÷åíà. ×òîáû ñîõðàíèòü âåëè÷èíó
ïåðåâîçêè â ýòîì ñòîëáöå, óâåëè÷èì ïåðåâîçêó â ñòîëáöå è ïî-
ìåòèâøåé åãî ñòðîêå. È ò. ä., ïîêà íå äîéäåì äî «íåäîâîëüíîé»
ñòðîêè. Ìû ïåðåâåçëè áîëüøåå êîëè÷åñòâî òîâàðà. Åñëè ïåðåâåçëè
âñå, ÷òî íàäî, òî ïîëó÷èëè îïòèìàëüíûé ïëàí. Åñëè îïÿòü ïåðå-
âåçëè íå âñå, òî ïîâòîðÿåì øàã 5.
D
2
) Ñèòóàöèÿ «óçêîå ìåñòî». Íàõîäèì ìèíèìàëüíûé ýëå-
ìåíò â îòìå÷åííûõ ñòðîêàõ ìàòðèöû ñòîèìîñòåé, èñêëþ÷àÿ ýëå-
ìåíòû îòìå÷åííûõ ñòîëáöîâ. Îòíèìàåì åãî îò êàæäîé îòìå÷åí-
íîé ñòðîêè è ïðèáàâëÿåì ê êàæäîìó îòìå÷åííîìó ñòîëáöó. Ïîñëå
ýòîãî âûïîëíÿåì øàã 3.
Ðàññìîòðèì ïðèìåð 2. Äàííûå çàäà÷è ïðåäñòàâëåíû â òðàíñ-
ïîðòíîé òàáëèöå ìàòðèöåé ñòîèìîñòåé, óêàçàíû òàêæå ñïðîñ è
ïðåäëîæåíèå.  òàáëèöå ÷åòûðå ïóíêòà ïðåäëîæåíèÿ, è ïÿòü ïóí-
êòîâ ïîòðåáëåíèÿ. Ðåøèì çàäà÷ó, ïðèìåíÿÿ âåíãåðñêèé àëãîðèòì.
11 12 11 12 10
9 10 7 8 9
14 12 13 12 14
9 10 8 10 11
20
15
17
18
12 15 14 20 9 
      Àëãîðèòì ðàññòàíîâêè ìåòîê ïðèâîäèò ê îäíîé èç äâóõ ñè-
òóàöèé. Îäíó èç íèõ íàçîâåì ñèòóàöèåé ïðîðûâà. Îíà âîçíèêàåò â
òîì ñëó÷àå, åñëè ìû ïîìåòèëè «íåäîâîëüíûé» ñòîëáåö. Ýòî îçíà-
÷àåò, ÷òî ìû ïëîõî ðàñïðåäåëèëè ïåðåâîçêè ïî èìåþùèìñÿ íóëÿì.
Ïëàí ïåðåâîçîê áóäåò èçìåíåí è îáùåå êîëè÷åñòâî ïåðåâåçåííîãî
òîâàðà áóäåò óâåëè÷åíî. Äðóãóþ ñèòóàöèþ íàçîâåì «óçêîå ìåñòî».
 ýòîì ñëó÷àå ïî èìåþùèìñÿ íóëÿì íåâîçìîæíî ðåàëèçîâàòü âñå
ïåðåâîçêè.  ýòîì ñëó÷àå ìàòðèöà ñòîèìîñòåé áóäåò ïðåîáðàçî-
âàíà. Â ìàòðèöå ïîÿâÿòñÿ íîâûå íóëè, à ñòîèìîñòü ëþáîãî ïëàíà
ïî íîâîé ìàòðèöå áóäåò ìåíüøå, ÷åì ïî ñòàðîé. Ðàññìîòðèì êàæ-
äóþ èç ýòèõ ñèòóàöèé áîëåå ïîäðîáíî.
      D1 ) Ñèòóàöèÿ «ïðîðûâà». Ïåðåðàñïðåäåëèì ïåðåâîçêè. Íà
ïåðåñå÷åíèè «íåäîâîëüíîãî» ñòîëáöà è ñòðîêè, èç-çà êîòîðîé îí
áûë îòìå÷åí, ïåðåâîçêó óâåëè÷èì. ×òîáû ñîõðàíèòü âåëè÷èíó
ïåðåâîçêè â ýòîé ñòðîêå, óìåíüøèì ïåðåâîçêó â ñòðîêå è ñòîëá-
öå, èç-çà êîòîðîãî îíà áûëà îòìå÷åíà. ×òîáû ñîõðàíèòü âåëè÷èíó
ïåðåâîçêè â ýòîì ñòîëáöå, óâåëè÷èì ïåðåâîçêó â ñòîëáöå è ïî-
ìåòèâøåé åãî ñòðîêå. È ò. ä., ïîêà íå äîéäåì äî «íåäîâîëüíîé»
ñòðîêè. Ìû ïåðåâåçëè áîëüøåå êîëè÷åñòâî òîâàðà. Åñëè ïåðåâåçëè
âñå, ÷òî íàäî, òî ïîëó÷èëè îïòèìàëüíûé ïëàí. Åñëè îïÿòü ïåðå-
âåçëè íå âñå, òî ïîâòîðÿåì øàã 5.
      D2 ) Ñèòóàöèÿ «óçêîå ìåñòî». Íàõîäèì ìèíèìàëüíûé ýëå-
ìåíò â îòìå÷åííûõ ñòðîêàõ ìàòðèöû ñòîèìîñòåé, èñêëþ÷àÿ ýëå-
ìåíòû îòìå÷åííûõ ñòîëáöîâ. Îòíèìàåì åãî îò êàæäîé îòìå÷åí-
íîé ñòðîêè è ïðèáàâëÿåì ê êàæäîìó îòìå÷åííîìó ñòîëáöó. Ïîñëå
ýòîãî âûïîëíÿåì øàã 3.
      Ðàññìîòðèì ïðèìåð 2. Äàííûå çàäà÷è ïðåäñòàâëåíû â òðàíñ-
ïîðòíîé òàáëèöå ìàòðèöåé ñòîèìîñòåé, óêàçàíû òàêæå ñïðîñ è
ïðåäëîæåíèå.  òàáëèöå ÷åòûðå ïóíêòà ïðåäëîæåíèÿ, è ïÿòü ïóí-
êòîâ ïîòðåáëåíèÿ. Ðåøèì çàäà÷ó, ïðèìåíÿÿ âåíãåðñêèé àëãîðèòì.
                  11   12    11   12   10     20
                9    10    7         8        9    15
                14   12    13        12       14   17
                9    10    8         10       11   18
               12    15   14     20       9




                                73

Страницы