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

UptoLike

ВУЗ: 

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

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

Рубрика: 

66
Àëãîðèòì ðåøåíèÿ òðàíñïîðòíîé çàäà÷è
ìåòîäîì ïîòåíöèàëîâ
Øàã 1. Ïîäîáðàòü íåêîòîðûé ïåðâîíà÷àëüíûé ïëàí
ïåðåâîçîê.
Øàã 2. Èñïîëüçóÿ íåïðàâèëüíûå ïðÿìîóãîëüíèêè (åñëè îíè
åñòü), óëó÷øèòü èìåþùèéñÿ ïëàí (ìåòîä ëîêàëüíîãî ïîèñêà).
Øàã 3. Ñ ïîìîùüþ ïîòåíöèàëîâ ïðåîáðàçîâàòü ìàòðèöó ñòî-
èìîñòåé ñîãëàñíî ïîñëåäíåìó (ñàìîìó ëó÷øåìó èç íàéäåííûõ) ïëàíó.
 ñëó÷àå îòñóòñòâèÿ îòðèöàòåëüíûõ ýëåìåíòîâ â íîâîé ìàòðèöå ñòî-
èìîñòåé, íàéäåííûé ïëàí îïòèìàëåí. Åñëè ïîÿâèëñÿ îòðèöàòåëü-
íûé ýëåìåíò, òî èçìåíÿåì ïëàí òàê, ÷òîáû íà ýòîì ìåñòå áûëà
íåíóëåâàÿ ïåðåâîçêà. Ïîëó÷àåì íîâûé ïëàí. Ïîâòîðÿåì øàã 3.
Òîíêîñòè àëãîðèòìà
Âñåãäà ëè ñèñòåìà óðàâíåíèé äëÿ îïðåäåëåíèÿ ïîòåíöèàëîâ
èìååò ðåøåíèå? Ñèñòåìà ñîäåðæèò (n+m) ïåðåìåííûõ. Ïðè ðå-
øåíèè ñèñòåìû (6) âîçìîæíû òðè ñëó÷àÿ. Ðàññìîòðèì èõ áîëåå
äåòàëüíî.
Ñëó÷àé 1. Ïîëîæèâ
α
1
= 0, íàéäåì ÷àñòíîå ðåøåíèå ñèñòå-
ìû, îäíîçíà÷íî îïðåäåëÿÿ âñå îñòàëüíûå ïåðåìåííûå.  ýòîì ñëó÷àå
â ñèñòåìå (n + m - 1) óðàâíåíèå.
Ñëó÷àé 2. Ïîëîæèâ
α
1
= 0, ìû íå ñìîãëè îäíîçíà÷íî îïðåäå-
ëèòü âñå ïîòåíöèàëû. Îñòàâøèåñÿ óðàâíåíèÿ ñîäåðæàò òîëüêî íå-
èçâåñòíûå âåëè÷èíû. Òîãäà ñíîâà âûáåðåì íåêîòîðóþ ïåðåìåííóþ
è çàäàäèì åé íåêîòîðîå çíà÷åíèå (îáû÷íî ðàâíîå íóëþ). Ïðîäîë-
æèì âû÷èñëåíèÿ. Ýòîò øàã ìîæåò áûòü ïðèäåòñÿ ïîâòîðèòü íå-
ñêîëüêî ðàç. Òàêàÿ ñèòóàöèÿ âîçíèêàåò â òîì ñëó÷àå, åñëè ÷èñëî
óðàâíåíèé ìåíüøå (n+m-1). Ïëàí, â êîòîðîì ÷èñëî ïîëîæè-
òåëüíûõ ïåðåâîçîê ìåíüøå (n+m-1), íàçûâàþò âûðîæäåííûì.
Ñëó÷àé 3. Ñèñòåìà ìîæåò íå èìåòü ðåøåíèé.  ýòîì ñëó÷àå â
ìàòðèöå ïåðåâîçîê åñòü öèêë (ñì. îïèñàíèå öèêëà), âåðøèíû
êîòîðîãî ñîîòâåòñòâóþò íåíóëåâûì ïåðåâîçêàì. Äëÿ ïðîâåðêè òîãî,
÷òî ñèñòåìà èìååò ðåøåíèå, ïðèìåíèì ñëåäóþùóþ ïðîöåäóðó.
Íàçîâåì åå ïðîöåäóðîé ðàçâàëà. Âû÷åðêíåì â ìàòðèöå âñå ñòðîêè
è ñòîëáöû ñ îäíîé ïåðåâîçêîé. Áóäåì ïîâòîðÿòü ýòî, ïîêà âîç-
ìîæíî. Åñëè ìû âû÷åðêíóëè âñå ñòðîêè è âñå ñòîëáöû ìàòðèöû,
òî öèêëà íåò, è ñèñòåìà èìååò ðåøåíèå.
Íà ïðèìåðå ýòî âûãëÿäèò ñëåäóþùèì îáðàçîì. Ðàññìîòðèì
ìàòðèöó ïåðåâîçîê
         Àëãîðèòì ðåøåíèÿ òðàíñïîðòíîé çàäà÷è
                 ìåòîäîì ïîòåíöèàëîâ
     Øàã 1. Ïîäîáðàòü íåêîòîðûé ïåðâîíà÷àëüíûé ïëàí
ïåðåâîçîê.
     Øàã 2. Èñïîëüçóÿ íåïðàâèëüíûå ïðÿìîóãîëüíèêè (åñëè îíè
åñòü), óëó÷øèòü èìåþùèéñÿ ïëàí (ìåòîä ëîêàëüíîãî ïîèñêà).
     Øàã 3. Ñ ïîìîùüþ ïîòåíöèàëîâ ïðåîáðàçîâàòü ìàòðèöó ñòî-
èìîñòåé ñîãëàñíî ïîñëåäíåìó (ñàìîìó ëó÷øåìó èç íàéäåííûõ) ïëàíó.
 ñëó÷àå îòñóòñòâèÿ îòðèöàòåëüíûõ ýëåìåíòîâ â íîâîé ìàòðèöå ñòî-
èìîñòåé, íàéäåííûé ïëàí îïòèìàëåí. Åñëè ïîÿâèëñÿ îòðèöàòåëü-
íûé ýëåìåíò, òî èçìåíÿåì ïëàí òàê, ÷òîáû íà ýòîì ìåñòå áûëà
íåíóëåâàÿ ïåðåâîçêà. Ïîëó÷àåì íîâûé ïëàí. Ïîâòîðÿåì øàã 3.
                     Òîíêîñòè àëãîðèòìà
     Âñåãäà ëè ñèñòåìà óðàâíåíèé äëÿ îïðåäåëåíèÿ ïîòåíöèàëîâ
èìååò ðåøåíèå? Ñèñòåìà ñîäåðæèò (n + m) ïåðåìåííûõ. Ïðè ðå-
øåíèè ñèñòåìû (6) âîçìîæíû òðè ñëó÷àÿ. Ðàññìîòðèì èõ áîëåå
äåòàëüíî.
     Ñëó÷àé 1. Ïîëîæèâ α1 = 0, íàéäåì ÷àñòíîå ðåøåíèå ñèñòå-
ìû, îäíîçíà÷íî îïðåäåëÿÿ âñå îñòàëüíûå ïåðåìåííûå.  ýòîì ñëó÷àå
â ñèñòåìå (n + m - 1) óðàâíåíèå.
     Ñëó÷àé 2. Ïîëîæèâ α1 = 0, ìû íå ñìîãëè îäíîçíà÷íî îïðåäå-
ëèòü âñå ïîòåíöèàëû. Îñòàâøèåñÿ óðàâíåíèÿ ñîäåðæàò òîëüêî íå-
èçâåñòíûå âåëè÷èíû. Òîãäà ñíîâà âûáåðåì íåêîòîðóþ ïåðåìåííóþ
è çàäàäèì åé íåêîòîðîå çíà÷åíèå (îáû÷íî ðàâíîå íóëþ). Ïðîäîë-
æèì âû÷èñëåíèÿ. Ýòîò øàã ìîæåò áûòü ïðèäåòñÿ ïîâòîðèòü íå-
ñêîëüêî ðàç. Òàêàÿ ñèòóàöèÿ âîçíèêàåò â òîì ñëó÷àå, åñëè ÷èñëî
óðàâíåíèé ìåíüøå (n + m - 1). Ïëàí, â êîòîðîì ÷èñëî ïîëîæè-
òåëüíûõ ïåðåâîçîê ìåíüøå (n + m - 1), íàçûâàþò âûðîæäåííûì.
     Ñëó÷àé 3. Ñèñòåìà ìîæåò íå èìåòü ðåøåíèé.  ýòîì ñëó÷àå â
ìàòðèöå ïåðåâîçîê åñòü öèêë (ñì. îïèñàíèå öèêëà), âåðøèíû
êîòîðîãî ñîîòâåòñòâóþò íåíóëåâûì ïåðåâîçêàì. Äëÿ ïðîâåðêè òîãî,
÷òî ñèñòåìà èìååò ðåøåíèå, ïðèìåíèì ñëåäóþùóþ ïðîöåäóðó.
Íàçîâåì åå ïðîöåäóðîé ðàçâàëà. Âû÷åðêíåì â ìàòðèöå âñå ñòðîêè
è ñòîëáöû ñ îäíîé ïåðåâîçêîé. Áóäåì ïîâòîðÿòü ýòî, ïîêà âîç-
ìîæíî. Åñëè ìû âû÷åðêíóëè âñå ñòðîêè è âñå ñòîëáöû ìàòðèöû,
òî öèêëà íåò, è ñèñòåìà èìååò ðåøåíèå.
     Íà ïðèìåðå ýòî âûãëÿäèò ñëåäóþùèì îáðàçîì. Ðàññìîòðèì
ìàòðèöó ïåðåâîçîê

                              66

Страницы