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

UptoLike

ВУЗ: 

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

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

Рубрика: 

57
Àíàëîãè÷íî îñòàëüíûå ïåðåâîçêè â ÷åòâåðòîì ñòîëáöå ðàâíû íóëþ,
à â ñòðîêå íåîáõîäèìî ðàñïðåäåëèòü åùå ïÿòü åäèíèö òîâàðà. Èç
îñòàâøèõñÿ çíà÷åíèé ìàòðèöû ñòîèìîñòåé â ïåðâîé ñòðîêå ñàìîå
ìàëåíüêîå c
12
= 5, íå ðàñïðåäåëåíî åùå 5 åäèíèö. Ïîëîæèì õ
12
=
5. Òåïåðü îãðàíè÷åíèÿ, ïðåäñòàâëÿåìûå ïåðâîé ñòðîêîé, âûïîë-
íåíû, âñå íåíàçâàííûå ïåðåìåííûå â ïåðâîé ñòðîêå ïîëàãàþòñÿ
ðàâíûìè íóëþ. Ïåðåõîäèì ê ñëåäóþùåé ñòðîêå. Ïîâòîðÿÿ àíàëî-
ãè÷íûå äåéñòâèÿ è ó÷èòûâàÿ, ÷òî çíà÷åíèÿ íåêîòîðûõ ïåðåìåí-
íûõ óæå îïðåäåëåíû (ðàâíû íóëþ), ïîëîæèì õ
22
= 20. Òåïåðü
âûïîëíåíû îãðàíè÷åíèÿ, ïðåäñòàâëÿåìûå âòîðîé ñòðîêîé, ïîëà-
ãàåì îñòàëüíûå ïåðåìåííûå â ñòðîêå ðàâíûìè íóëþ, ïåðåõîäèì
ê òðåòüåé ñòðîêå. Çäåñü õ
33
= 15 è õ
32
= 15.
Ïîëó÷åí íåêîòîðûé ïëàí ïåðåâîçîê Õ
(1)
, çàïèøåì åãî â òàá-
ëèöå è ïîäñ÷èòàåì åãî ñòîèìîñòü
8
.
В
1
В
2
В
3
В
4
10
3
5
5
9
35
4
7
20
1
6
8
0
15
9
15
2
3
10
40 15 35
А
1
А
2
А
3
50
20
30
Ñòîèìîñòü ïëàíà Õ
(1)
:
L
(1)
= 3⋅10 + 5⋅5 + 4⋅35 + 20 + 9⋅15 +
2⋅15 = 380 (åä.).
Ïðè ïðèìåíåíèè ýòîãî àëãîðèòìà ìû ïîëó÷èì ïëàí ïåðåâî-
çîê, ñîäåðæàùèé íå áîëåå ÷åì m + n - 1 íåíóëåâóþ ïåðåâîçêó
9
.
Ïëàí, ñîäåðæàùèé ðîâíî m + n - 1 íåíóëåâûõ ïåðåâîçîê, íàçû-
âàåòñÿ íåâûðîæäåííûì.
Ðàññìîòðåííûé àëãîðèòì ïîçâîëÿåò íàõîäèòü äîñòàòî÷íî
õîðîøèé ïëàí, êîòîðûé, ê ñîæàëåíèþ, íå âñåãäà îïòèìàëåí,
çàòî åãî ïîèñê íå òðåáóåò áîëüøèõ âðåìåííûõ çàòðàò. ×àñòî òàêîé
ïëàí ÿâëÿåòñÿ íåïëîõèì ïåðâûì ïðèáëèæåíèåì. Àëãîðèòìû òà-
êîãî ðîäà, äàþùèå äîñòàòî÷íî ðàçóìíûå âàðèàíòû, íî íå âñåãäà
ïðèâîäÿùèå ê òî÷íîìó ðåøåíèþ, íàçûâàþòñÿ ýâðèñòè÷åñêèìè.
Äàííûé ýâðèñòè÷åñêèé àëãîðèòì îòíîñèòñÿ ê òàê íàçûâàåìûì
__________________
8
 êëåòêàõ ìàòðèöû, ãäå íå óêàçàíà âåëè÷èíà ïåðåâîçêè, ïåðå-
âîçêà ðàâíà íóëþ.
9
×èñëî íåíóëåâûõ ïåðåâîçîê ñâÿçàíî ñ ÷èñëîì áàçèñíûõ ïåðå-
ìåííûõ ñèñòåìû óðàâíåíèé (ñì. ñèìïëåêñ-ìåòîä).
Àíàëîãè÷íî îñòàëüíûå ïåðåâîçêè â ÷åòâåðòîì ñòîëáöå ðàâíû íóëþ,
à â ñòðîêå íåîáõîäèìî ðàñïðåäåëèòü åùå ïÿòü åäèíèö òîâàðà. Èç
îñòàâøèõñÿ çíà÷åíèé ìàòðèöû ñòîèìîñòåé â ïåðâîé ñòðîêå ñàìîå
ìàëåíüêîå c12 = 5, íå ðàñïðåäåëåíî åùå 5 åäèíèö. Ïîëîæèì õ12 =
5. Òåïåðü îãðàíè÷åíèÿ, ïðåäñòàâëÿåìûå ïåðâîé ñòðîêîé, âûïîë-
íåíû, âñå íåíàçâàííûå ïåðåìåííûå â ïåðâîé ñòðîêå ïîëàãàþòñÿ
ðàâíûìè íóëþ. Ïåðåõîäèì ê ñëåäóþùåé ñòðîêå. Ïîâòîðÿÿ àíàëî-
ãè÷íûå äåéñòâèÿ è ó÷èòûâàÿ, ÷òî çíà÷åíèÿ íåêîòîðûõ ïåðåìåí-
íûõ óæå îïðåäåëåíû (ðàâíû íóëþ), ïîëîæèì õ22 = 20. Òåïåðü
âûïîëíåíû îãðàíè÷åíèÿ, ïðåäñòàâëÿåìûå âòîðîé ñòðîêîé, ïîëà-
ãàåì îñòàëüíûå ïåðåìåííûå â ñòðîêå ðàâíûìè íóëþ, ïåðåõîäèì
ê òðåòüåé ñòðîêå. Çäåñü õ33 = 15 è õ32 = 15.
      Ïîëó÷åí íåêîòîðûé ïëàí ïåðåâîçîê Õ(1), çàïèøåì åãî â òàá-
ëèöå è ïîäñ÷èòàåì åãî ñòîèìîñòü 8 .
                               В1       В2    В3           В4
                              10        5                           35
                     А1                           9                      50
                          3         5                           4
                                        20
                     А2                                                  20
                          7         1             6             8
                                        15            15                 30
                     А3   0         9         2                 3
                          10        40            15            35
      Ñòîèìîñòü ïëàíà Õ(1): L(1) = 3⋅10 + 5⋅5 + 4⋅35 + 20 + 9⋅15 +
2⋅15 = 380 (åä.).
      Ïðè ïðèìåíåíèè ýòîãî àëãîðèòìà ìû ïîëó÷èì ïëàí ïåðåâî-
çîê, ñîäåðæàùèé íå áîëåå ÷åì m + n - 1 íåíóëåâóþ ïåðåâîçêó 9 .
Ïëàí, ñîäåðæàùèé ðîâíî m + n - 1 íåíóëåâûõ ïåðåâîçîê, íàçû-
âàåòñÿ íåâûðîæäåííûì.
      Ðàññìîòðåííûé àëãîðèòì ïîçâîëÿåò íàõîäèòü äîñòàòî÷íî
õîðîøèé ïëàí, êîòîðûé, ê ñîæàëåíèþ, íå âñåãäà îïòèìàëåí,
çàòî åãî ïîèñê íå òðåáóåò áîëüøèõ âðåìåííûõ çàòðàò. ×àñòî òàêîé
ïëàí ÿâëÿåòñÿ íåïëîõèì ïåðâûì ïðèáëèæåíèåì. Àëãîðèòìû òà-
êîãî ðîäà, äàþùèå äîñòàòî÷íî ðàçóìíûå âàðèàíòû, íî íå âñåãäà
ïðèâîäÿùèå ê òî÷íîìó ðåøåíèþ, íàçûâàþòñÿ ýâðèñòè÷åñêèìè.
Äàííûé ýâðèñòè÷åñêèé àëãîðèòì îòíîñèòñÿ ê òàê íàçûâàåìûì
__________________


        êëåòêàõ ìàòðèöû, ãäå íå óêàçàíà âåëè÷èíà ïåðåâîçêè, ïåðå-
       8

âîçêà ðàâíà íóëþ.
     ×èñëî íåíóëåâûõ ïåðåâîçîê ñâÿçàíî ñ ÷èñëîì áàçèñíûõ ïåðå-
       9

ìåííûõ ñèñòåìû óðàâíåíèé (ñì. ñèìïëåêñ-ìåòîä).

                                             57

Страницы