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

UptoLike

ВУЗ: 

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

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

Рубрика: 

68
Âåíãåðñêèé àëãîðèòì ðåøåíèÿ òðàíñïîðòíîé çàäà÷è
Âûøå íàìè áûë ðàññìîòðåí îäèí èç ìåòîäîâ ðåøåíèÿ òðàíñ-
ïîðòíîé çàäà÷è — ìåòîä ïîòåíöèàëîâ. Ïðèìåíÿÿ ýòîò ìåòîä, ìû
ñíà÷àëà íàõîäèì êàêîé-ëèáî ïëàí ïåðåâîçîê, à çàòåì ïðåîáðàçó-
åì ìàòðèöó ñòîèìîñòåé òàê, ÷òîáû âñå ïåðåâîçêè îñóùåñòâëÿ-
ëèñü ïî ýëåìåíòàì íóëåâîé ñòîèìîñòè. Åñëè ïðè ýòîì âñå ýëå-
ìåíòû íîâîé ìàòðèöû íåîòðèöàòåëüíû, òî íàéäåííûé ïëàí îï-
òèìàëåí. Ïðè ðåøåíèè çàäà÷è âåíãåðñêèì àëãîðèòìîì áóäåì èñ-
êàòü ïëàí, èñïîëüçóÿ ïåðåâîçêè òîëüêî íóëåâîé ñòîèìîñòè. Åñëè
ìû íå ìîæåì íàçíà÷èòü âñå ïåðåâîçêè ïî ýëåìåíòàì íóëåâîé
ñòîèìîñòè, òî áóäåì ïðîèçâîäèòü ïðåîáðàçîâàíèÿ ìàòðèöû ñòî-
èìîñòåé Ñ: îòíèìàòü èëè ïðèáàâëÿòü ê ñòðîêàì è ñòîëáöàì ñîîò-
âåòñòâóþùèå ÷èñëà. Ïðè ýòîì â ïðåîáðàçîâàííîé ìàòðèöå íå äîë-
æíî áûòü îòðèöàòåëüíûõ ýëåìåíòîâ. Ðàíåå áûëî ïîêàçàíî, ÷òî
ïëàí, îïòèìàëüíûé äëÿ èñõîäíîé ìàòðèöû ñòîèìîñòåé, îïòèìà-
ëåí è äëÿ ïðåîáðàçîâàííîé ìàòðèöû è íàîáîðîò. Åñëè ìû ïåðå-
âåçëè âñå, ÷òî òðåáóåòñÿ, òî, ñîãëàñíî ëåììå îá îïòèìàëüíîñòè
(â ìàòðèöå áåç îòðèöàòåëüíûõ ñòîèìîñòåé ïëàí íóëåâîé ñòîèìî-
ñòè çàâåäîìî îïòèìàëåí), çàäà÷à ðåøåíà.
Îïèñàíèå àëãîðèòìà áóäåì ñîïðîâîæäàòü ïðèìåðîì åãî ðåà-
ëèçàöèè. Ðàññìîòðèì ïðèìåð 1. Ýòîò ïðèìåð áûë ðåøåí íàìè ðà-
íåå ìåòîäîì ïîòåíöèàëîâ. Ïóñòü çàäàíà òðàíñïîðòíàÿ òàáëèöà.
3
5
9
4
7
1
6
8
0
9
2
3
50
20
30
10 40 15 35
Âñå ïåðåâîçêè íóæíî îñóùåñòâëÿòü òîëüêî ïî ýëåìåíòàì
íóëåâîé ñòîèìîñòè. Îäíàêî â ïåðâîé ñòðîêå ìàòðèöû ñòîèìîñòåé
íåò íè îäíîãî íóëÿ. Âû÷òåì èç âñåõ ýëåìåíòîâ ïåðâîé ñòðîêè
ìàòðèöû ñòîèìîñòåé åå ìèíèìàëüíûé ýëåìåíò, òî åñòü 3. Òàê êàê
â ïåðâîé ñòðîêå ìàòðèöû íàäî ðàñïðåäåëèòü 50 åäèíèö òîâàðà, à
ñòîèìîñòü ïåðåâîçêè êàæäîé åäèíèöû òîâàðà ñòàíåò ïî íîâîé
ìàòðèöå íà 3 åäèíèöû äåøåâëå, òî ñòîèìîñòü ëþáîãî ïëàíà ïî
íîâîé ìàòðèöå äåøåâëå íà 150 (3×50) åäèíèö, ÷åì ïî ñòàðîé.
Ââåäåì îáîçíà÷åíèÿ.
      Âåíãåðñêèé àëãîðèòì ðåøåíèÿ òðàíñïîðòíîé çàäà÷è
     Âûøå íàìè áûë ðàññìîòðåí îäèí èç ìåòîäîâ ðåøåíèÿ òðàíñ-
ïîðòíîé çàäà÷è — ìåòîä ïîòåíöèàëîâ. Ïðèìåíÿÿ ýòîò ìåòîä, ìû
ñíà÷àëà íàõîäèì êàêîé-ëèáî ïëàí ïåðåâîçîê, à çàòåì ïðåîáðàçó-
åì ìàòðèöó ñòîèìîñòåé òàê, ÷òîáû âñå ïåðåâîçêè îñóùåñòâëÿ-
ëèñü ïî ýëåìåíòàì íóëåâîé ñòîèìîñòè. Åñëè ïðè ýòîì âñå ýëå-
ìåíòû íîâîé ìàòðèöû íåîòðèöàòåëüíû, òî íàéäåííûé ïëàí îï-
òèìàëåí. Ïðè ðåøåíèè çàäà÷è âåíãåðñêèì àëãîðèòìîì áóäåì èñ-
êàòü ïëàí, èñïîëüçóÿ ïåðåâîçêè òîëüêî íóëåâîé ñòîèìîñòè. Åñëè
ìû íå ìîæåì íàçíà÷èòü âñå ïåðåâîçêè ïî ýëåìåíòàì íóëåâîé
ñòîèìîñòè, òî áóäåì ïðîèçâîäèòü ïðåîáðàçîâàíèÿ ìàòðèöû ñòî-
èìîñòåé Ñ: îòíèìàòü èëè ïðèáàâëÿòü ê ñòðîêàì è ñòîëáöàì ñîîò-
âåòñòâóþùèå ÷èñëà. Ïðè ýòîì â ïðåîáðàçîâàííîé ìàòðèöå íå äîë-
æíî áûòü îòðèöàòåëüíûõ ýëåìåíòîâ. Ðàíåå áûëî ïîêàçàíî, ÷òî
ïëàí, îïòèìàëüíûé äëÿ èñõîäíîé ìàòðèöû ñòîèìîñòåé, îïòèìà-
ëåí è äëÿ ïðåîáðàçîâàííîé ìàòðèöû è íàîáîðîò. Åñëè ìû ïåðå-
âåçëè âñå, ÷òî òðåáóåòñÿ, òî, ñîãëàñíî ëåììå îá îïòèìàëüíîñòè
(â ìàòðèöå áåç îòðèöàòåëüíûõ ñòîèìîñòåé ïëàí íóëåâîé ñòîèìî-
ñòè çàâåäîìî îïòèìàëåí), çàäà÷à ðåøåíà.
     Îïèñàíèå àëãîðèòìà áóäåì ñîïðîâîæäàòü ïðèìåðîì åãî ðåà-
ëèçàöèè. Ðàññìîòðèì ïðèìåð 1. Ýòîò ïðèìåð áûë ðåøåí íàìè ðà-
íåå ìåòîäîì ïîòåíöèàëîâ. Ïóñòü çàäàíà òðàíñïîðòíàÿ òàáëèöà.
                                           50
                  3     5     9     4
                  7     1     6     8      20

                  0     9     2     3      30
                  10     40   15    35
     Âñå ïåðåâîçêè íóæíî îñóùåñòâëÿòü òîëüêî ïî ýëåìåíòàì
íóëåâîé ñòîèìîñòè. Îäíàêî â ïåðâîé ñòðîêå ìàòðèöû ñòîèìîñòåé
íåò íè îäíîãî íóëÿ. Âû÷òåì èç âñåõ ýëåìåíòîâ ïåðâîé ñòðîêè
ìàòðèöû ñòîèìîñòåé åå ìèíèìàëüíûé ýëåìåíò, òî åñòü 3. Òàê êàê
â ïåðâîé ñòðîêå ìàòðèöû íàäî ðàñïðåäåëèòü 50 åäèíèö òîâàðà, à
ñòîèìîñòü ïåðåâîçêè êàæäîé åäèíèöû òîâàðà ñòàíåò ïî íîâîé
ìàòðèöå íà 3 åäèíèöû äåøåâëå, òî ñòîèìîñòü ëþáîãî ïëàíà ïî
íîâîé ìàòðèöå äåøåâëå íà 150 (3×50) åäèíèö, ÷åì ïî ñòàðîé.
     Ââåäåì îáîçíà÷åíèÿ.



                             68

Страницы