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

UptoLike

ВУЗ: 

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

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

Рубрика: 

69
Ïóñòü L(Õ) — ñòîèìîñòü ïëàíà ïåðåâîçîê Õ (Õ = {x
ij
}), ïîä-
ñ÷èòàííàÿ ïî ïåðâîíà÷àëüíîé ìàòðèöå ñòîèìîñòåé Ñ;
Ñ
k
— ìàòðèöà ñòîèìîñòåé, ïîëó÷åííàÿ ïîñëå k-ãî ïðåîáðà-
çîâàíèÿ;
L
k
(Õ)
— ñòîèìîñòü ïëàíà ïåðåâîçîê X, ïîäñ÷èòàííàÿ ïî ìàò-
ðèöå ñòîèìîñòåé Ñ
k
.
Òîãäà, ïðè ðàññìîòðåííîì ïðåîáðàçîâàíèè ìàòðèöû, äëÿ
ëþáîãî X:
L
1
(Õ) = L(Õ)
-150.
Àëãîðèòì
Øàã 1. Ïðåîáðàçóåì ìàòðèöó ñòîèìîñòåé Ñ, îòíèìàÿ îò êàæ-
äîé ñòðîêè ìèíèìàëüíûé ýëåìåíò ýòîé ñòðîêè
11
.
Øàã 2. Îòíèìåì îò êàæäîãî ñòîëáöà, íå èìåþùåãî íóëåâûõ
ýëåìåíòîâ, åãî ìèíèìàëüíûé ýëåìåíò
12
.
Ïîñëå âûïîëíåíèÿ ïåðâîãî øàãà àëãîðèòìà ìàòðèöà ñòî-
èìîñòåé ïðèìåò âèä:
3 5 9 4 -3
7 1 6 8 -1
0 9 2 3
0 2 6 1
6 0 5 7
0 9 2 3
L
1
(X) = L(X)
— 3⋅50 = L(X)
— 150.
L
2
(X) = L
1
(X)
— 1⋅20 = L(X) — 170.
Ïîñëå âòîðîãî øàãà àëãîðèòìà:
0 2 6 1
6 0 5 7
0 9 2 3
(
-2
)
(
-1
)
0 2 4 0
6 0 3 6
0 9 0 2
L
3
(Õ)= L
2
(Õ)
— 2⋅15 = L
2
(Õ) — 30 = L(Õ) — 200.
L
4
(Õ)= L
3
(Õ)
— 35 = L(Õ) — 235.
__________________
11
Ïîñëå ýòîãî â êàæäîé ñòðîêå îêàæåòñÿ õîòÿ áû îäèí 0.
12
Ïîñëå ýòîãî â êàæäîé ñòðîêå è êàæäîì ñòîëáöå èìååòñÿ õîòÿ
áû îäèí 0. Íà âñåõ ýòàïàõ àëãîðèòìà â ìàòðèöå ñòîèìîñòåé íå äîëæíî
áûòü îòðèöàòåëüíûõ ýëåìåíòîâ.
     Ïóñòü L(Õ) — ñòîèìîñòü ïëàíà ïåðåâîçîê Õ (Õ = {xij}), ïîä-
ñ÷èòàííàÿ ïî ïåðâîíà÷àëüíîé ìàòðèöå ñòîèìîñòåé Ñ;
     Ñk — ìàòðèöà ñòîèìîñòåé, ïîëó÷åííàÿ ïîñëå k-ãî ïðåîáðà-
çîâàíèÿ;
     Lk(Õ) — ñòîèìîñòü ïëàíà ïåðåâîçîê X, ïîäñ÷èòàííàÿ ïî ìàò-
ðèöå ñòîèìîñòåé Ñk.
     Òîãäà, ïðè ðàññìîòðåííîì ïðåîáðàçîâàíèè ìàòðèöû, äëÿ
ëþáîãî X:
                       L (Õ) = L(Õ) -150.
                                  1

                                      Àëãîðèòì
     Øàã 1. Ïðåîáðàçóåì ìàòðèöó ñòîèìîñòåé Ñ, îòíèìàÿ îò êàæ-
äîé ñòðîêè ìèíèìàëüíûé ýëåìåíò ýòîé ñòðîêè 11 .
     Øàã 2. Îòíèìåì îò êàæäîãî ñòîëáöà, íå èìåþùåãî íóëåâûõ
ýëåìåíòîâ, åãî ìèíèìàëüíûé ýëåìåíò 12 .
     Ïîñëå âûïîëíåíèÿ ïåðâîãî øàãà àëãîðèòìà ìàòðèöà ñòî-
èìîñòåé ïðèìåò âèä:
                     3   5    9       4   -3            0       2       6       1
                     7   1    6       8   -1            6       0       5       7
                     0   9    2       3                 0       9       2       3

                 L1(X) = L(X) — 3⋅50 = L(X) — 150.
                L2(X) = L1(X) — 1⋅20 = L(X) — 170.
       Ïîñëå âòîðîãî øàãà àëãîðèòìà:
                     0   2    6       1             0       2       4       0
                     6   0    5       7             6       0       3       6
                     0   9    2       3             0       9       0       2
                             (-2) (-1)
            L3(Õ)= L2(Õ) — 2⋅15 = L2(Õ) — 30 = L(Õ) — 200.
                   L4(Õ)= L3(Õ) — 35 = L(Õ) — 235.

__________________

       11
            Ïîñëå ýòîãî â êàæäîé ñòðîêå îêàæåòñÿ õîòÿ áû îäèí 0.
       Ïîñëå ýòîãî â êàæäîé ñòðîêå è êàæäîì ñòîëáöå èìååòñÿ õîòÿ
       12

áû îäèí 0. Íà âñåõ ýòàïàõ àëãîðèòìà â ìàòðèöå ñòîèìîñòåé íå äîëæíî
áûòü îòðèöàòåëüíûõ ýëåìåíòîâ.

                                               69

Страницы