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

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 – сурет. Телекоммуникациялар желісінің оптималды сұлбасы