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

UptoLike

ВУЗ: 

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

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

Рубрика: 

39
l
À
*
= 0, l
2
*
= 4, l
3
= 9, l
4
*
= 2, l
5
= 8, l
6
= ∞, l
7
= 9, l
8
= ∞, l
Â
= l
9
= ∞.
Àíàëîãè÷íî, ñðåäè ìåòîê l
3
, l
5
, l
7
(l
3
= 9, l
5
= 8, l
7
= 9)
âûáèðàåì l
5
. Èç 5-é âåðøèíû åñòü ðåáðà â âåðøèíû 6 è 8. Çàìå-
íÿåì l
6
= 9, l
8
= 11. l
5
*
= 8.
l
À
*
= 0, l
2
*
= 4, l
3
= 9, l
4
*
= 2, l
5
*
= 8, l
6
= 9, l
7
= 9, l
8
= 11,
l
Â
= l
9
= ∞.
Äàëåå âûáîð ïðîèçâîäèòñÿ èç âåðøèí 3, 6, 7 è 8. Ìîæåò
áûòü âûáðàíà ëþáàÿ èç âåðøèí 3, 6, 7(l
3
= 9, l
6
= 9, l
7
= 9, l
8
=
11). Íàïðèìåð, 3-ÿ.  ýòîì ñëó÷àå âñå ìåòêè ñîõðàíÿþò ñâîè çíà-
÷åíèÿ. l
3
*
= 9.
l
À
*
= 0, l
2
*
= 4, l
3
*
= 9, l
4
*
= 2, l
5
*
= 8, l
6
= 9, l
7
= 9, l
8
= 11,
l
Â
= l
9
= ∞.
Èç âåðøèí 6, 7 è 8 âûáåðåì âåðøèíó 6. Òîãäà l
Â
= 17. l
6
*
= 9.
l
À
*
= 0, l
2
*
= 4, l
3
= 9, l
4
*
= 2, l
5
*
= 8, l
6
*
= 9, l
7
= 9, l
8
= 11,
l
Â
= l
9
= 17.
Íàêîíåö, èç âåðøèí 7, 8 è 9(Â) âûáèðàåì âåðøèíó ñ ìè-
íèìàëüíîé ìåòêîé. Ýòî âåðøèíà 7. Âñå ìåòêè ñîõðàíÿþò ñâîè
çíà÷åíèÿ. l
7
*
= 9.
Îñòàëèñü âåðøèíû 8-ÿ è Â (9-ÿ). Èõ ìåòêè äåëàþòñÿ ïîñòî-
ÿííûìè, ñîõðàíÿÿ ñâîè çíà÷åíèÿ. l
8
*
= 11, l
Â
*
= 17. Òàêèì îáðà-
çîì, l
Â
*
= 17.
Çàäà÷à ðåøåíà. Íàéäåíû äëèíû êðàò÷àéøèõ ïóòåé. Äëÿ îòûñ-
êàíèÿ ñàìèõ ïóòåé íàäî, íà÷èíàÿ ñ âåðøèíû Â, äëÿ êàæäîé
âåðøèíû j îòìåòèòü òàêîå ðåáðî (i, j), äëÿ êîòîðîãî l
i
+ a
ij
= l
j
.
Çäåñü ðåáðà îðèåíòèðîâàíû îò i ê j (!).  íàøåì ïðèìåðå ïîëó÷èì
ñëåäóþùèå îòìå÷åííûå (ñì. ÷åðòåæ) ðåáðà. Ïðè ýòîì â êàæäóþ
âåðøèíó, êðîìå íà÷àëüíîé, âõîäèò ïî êðàéíåé ìåðå îäíî ðåáðî.
8 9
4 6
7
5
1 2 3
А
В
2
4
6
7 3
1
8
5
Êðàò÷àéøèé ïóòü èäåò ÷åðåç âåðøèíû À → 4 → 5 → 6 → Â.
 ïðîöåññå ïîèñêà êðàò÷àéøåãî ïóòè èç À â  îïðåäåëÿþòñÿ
è êðàò÷àéøèå ïóòè èç À â ëþáóþ äðóãóþ âåðøèíó ãðàôà. Òðóäî-
      lÀ* = 0, l2*= 4, l3 = 9, l4* = 2, l5 = 8, l6 = ∞, l7 = 9, l8 = ∞, lÂ
= l9 = ∞.
      Àíàëîãè÷íî, ñðåäè ìåòîê l3, l5, l7 (l3 = 9, l5= 8, l7= 9)
âûáèðàåì l5. Èç 5-é âåðøèíû åñòü ðåáðà â âåðøèíû 6 è 8. Çàìå-
íÿåì l6 = 9, l8 = 11. l5* = 8.
      lÀ* = 0, l2*= 4, l3 = 9, l4* = 2, l5* = 8, l6 = 9, l7 = 9, l8 = 11,
l = l9 = ∞.
      Äàëåå âûáîð ïðîèçâîäèòñÿ èç âåðøèí 3, 6, 7 è 8. Ìîæåò
áûòü âûáðàíà ëþáàÿ èç âåðøèí 3, 6, 7(l3 = 9, l6 = 9, l7 = 9, l8 =
11). Íàïðèìåð, 3-ÿ.  ýòîì ñëó÷àå âñå ìåòêè ñîõðàíÿþò ñâîè çíà-
÷åíèÿ. l3*= 9.
      lÀ* = 0, l2*= 4, l3*= 9, l4* = 2, l5* = 8, l6 = 9, l7 = 9, l8 = 11,
l = l9 = ∞.
      Èç âåðøèí 6, 7 è 8 âûáåðåì âåðøèíó 6. Òîãäà l = 17. l6*= 9.
      lÀ* = 0, l2*= 4, l3 = 9, l4* = 2, l5* = 8, l6*= 9, l7 = 9, l8 = 11,
l = l9 = 17.
      Íàêîíåö, èç âåðøèí 7, 8 è 9(Â) âûáèðàåì âåðøèíó ñ ìè-
íèìàëüíîé ìåòêîé. Ýòî âåðøèíà 7. Âñå ìåòêè ñîõðàíÿþò ñâîè
çíà÷åíèÿ. l7*= 9.
      Îñòàëèñü âåðøèíû 8-ÿ è Â (9-ÿ). Èõ ìåòêè äåëàþòñÿ ïîñòî-
ÿííûìè, ñîõðàíÿÿ ñâîè çíà÷åíèÿ. l8* = 11, lÂ* = 17. Òàêèì îáðà-
çîì, lÂ*= 17.
      Çàäà÷à ðåøåíà. Íàéäåíû äëèíû êðàò÷àéøèõ ïóòåé. Äëÿ îòûñ-
êàíèÿ ñàìèõ ïóòåé íàäî, íà÷èíàÿ ñ âåðøèíû Â, äëÿ êàæäîé
âåðøèíû j îòìåòèòü òàêîå ðåáðî (i, j), äëÿ êîòîðîãî li + aij = lj.
Çäåñü ðåáðà îðèåíòèðîâàíû îò i ê j (!).  íàøåì ïðèìåðå ïîëó÷èì
ñëåäóþùèå îòìå÷åííûå (ñì. ÷åðòåæ) ðåáðà. Ïðè ýòîì â êàæäóþ
âåðøèíó, êðîìå íà÷àëüíîé, âõîäèò ïî êðàéíåé ìåðå îäíî ðåáðî.
                                                         В
                            7           8            9

                                7       3        8

                            4       6   5    1       6


                             2

                            1       4   2    5       3
                        А

     Êðàò÷àéøèé ïóòü èäåò ÷åðåç âåðøèíû À → 4 → 5 → 6 → Â.
      ïðîöåññå ïîèñêà êðàò÷àéøåãî ïóòè èç À â  îïðåäåëÿþòñÿ
è êðàò÷àéøèå ïóòè èç À â ëþáóþ äðóãóþ âåðøèíó ãðàôà. Òðóäî-


                                        39

Страницы