Тапсырманы есептеу мысалы

S_1, S₂, S₃ терминалдарын ЭЕМ S₀ байланыстыратын минималды бағалы желіні құру қажет. Жолдар бағалары C_ij 3 кестеде берілген, барлық жолдардың өткізу қабілеттіктер r_ij=5 тең.

4 –кесте. Желі тораптарының жалғану бағалары

а₀=-8; а₁=2; а₂=3; а₃=3.

	S0	S1	S2	S3
S1		-
S2			-
S3				-

0 қадам. Белгіленулер көпшілігін есептейміз:

t_ij= C_ij- C_io (2.2)

t₁₂= C₁₂- C₁₀=2-1=1

t₁₃= C₁₃- C₁₀=4-1=3

t₂₁= C₂₁- C₂₀=3-4=-1;

t₂₃= C₂₃- C₂₀=1-4=-3;

t₃₁= C₃₁- C₃₀=1-3=-2;

t₃₂= C₃₂- C₃₀=5-3=2

1 итерация.

1 қадам. (1) көпшілігінде минималды белгіленуді таңдайық

{ t_ij}= t₂₃=-3

Бұл S₂ және S₃ (S₂=>S₃) шыңдарды байланыстыру мүмкіндігін тексеру қажеттілігін білдіреді.

2 қадам. S₂ шыңдағы интенсивтілігін есептейік

а₂=3>0; а₂=3<r=5.

а₂+ а₃=3+3>r - яғни S₂=>S₃ байланыс мүмкінсіз, t₂₃= болады, 2 итерацияны есептейік.

Итерация 2.

1 қадам.

{t_ij}= t₃₁=-2, яғни S₃ және S₁ байланысына сәйкес_.

2 қадам. а₃=3>0 а₃<r=5, а₁=3+2=5=r, яғни бұл байланыс мүмкін болады.

3 қадам. Есептейік:

– шығындар F=C₃₁=1;

– терминалдардың S₃ және S₁ жаңа интенсивтіліктері a₃¹=0 а₁¹=2+3=5

– өткізу қабілеті r¹₃₁=5-3=2.

–

6 – сурет. S₃ және S₁ түйіндерінің жалғануы

3 итерация.

1 қадам. {t_ij} = t₂₁.

2 қадам. Тексерейік:

a₂=3>0; а₂<r=5; а₂+а₁^’= 3+5>r=5, сондықтан бұл байланыс мүмкінсіз.

4 итерация.

1 қадам. {t_ij}= t₁₂>0, яғни барлық t_ij – оң.

4 қадам. Оң интенсивтіліктермен шыңдарды S_0. байланыстырайық

A₁=5<r₁₀ a¹¹₁=0 а¹₀=-8+5=-3 F¹¹=F+C₁₀=1+1=2.

А₂=3<r₂₀ a¹₂=0 а¹¹₀=-3+3=0 F¹¹¹=F¹¹+C₂₀=2+4=6.

A¹₃=0

Есеп шығарылды, оптималды сұлба 7 суретте көрсетілген, шығындар 6 бірлікке тең.

7 – сурет. Телекоммуникациялар желісінің оптималды сұлбасы

Дата добавления: 2015-07-11