Теориялық бөлім. Ti, i=1, n терминалдарының берілген санын, кейбір жіберілетін көптеген Kj (j=1, m) концентраторларын қамтитын екідеңгейлі желі

 

T_i, i=1,... n терминалдарының берілген санын, кейбір жіберілетін көптеген K_j (j=1, … m) концентраторларын қамтитын екідеңгейлі желі синтезінің алгоритмін қарастырайық. Олардың орналасатын жері белгілі, ал саны шешілген тапсырманың нәтижесіне қарап таңдалуы тиіс. Орталық өңдеуші құрылғыны (ЭВМ) К₀ деп белгілейік. Әрбір r_j концентраторына қосуға болатын терминалдар саны және f_j концентраторларын пайда ететін құн берілген. Егер концентраторға бір терминал қосылса, онда ол ашық, ал кері жағдайда жабық деп аталады.

Әрбір терминал тек бір ғана ЭВМ-ге немесе кез келген концентраторға қосылуы мүмкін. Тапсырма барлық сипатталған технологиялық шектеулерді есепке ала отырып, минималды құнды желінің тұрғызылуынан тұрады.

Сонымен, берілгендер мыналар:

- көптеген Т_i терминалдары және K_j (i=1,..n; j=1,2,…m), ЭВМ – К₀ концентраторлар;

- С=ççС_ijçç, i=1,..n; j=0,1,…m құнды матрицаларымен берілген байланыс жолдарының құны;

- f₁,f₂,…f_m концентраторларын құрудың құны;

- r_j терминалдарын қосу мүмкіндігінің саны.

Анықтау керек:

- ашық концентраторлар санын;

- оларға қосылған терминалдардың сұлбасын;

- желінің құнын.

Осы тапсырманы шешу үшін көптеген әдістер жасалған, солардың ішінде біреуін қарастырайық.

Қоспа әдісінің алгоритмі

Бұл алгоритм қосымша концентраторлардың ашылу есебімен мақсатты функцияның кезекті азаюының итерациялық процессі және оларға терминалдарды рационалды бекітумен түсіндіріледі.

0-қадам. Біріншіден, барлық концентраторлар жабық, ал терминалдар ЭВМ - К₀ -мен байланысқан деп есептейік. Мұндай желіні тұрғызудың шығыны терминалдарды ЭВМ-мен байланыстырудың қосындысына тең, яғни К₀ сәйкес келетін қатардың элементтер қосындысына, яғни:

 

F⁰= С_i0.

Бұл ең қымбат шешім екені белгілі.

 

1 - итерация.

Бұл итерацияның әрекетін бір концентратордың (алдымен К₁, содан кейін К₂, …) ашылу шешімімен бағалайды, сонымен қатар оған неғұрлым үлкен эффект беретін терминалдар байланысу керек. Олар байланыс жолының құнын азайту есебімен пайда болады. Итерацияның қадамдар саны концентраторлар санына тең.

 

1-қадам. К₁ ашамыз. S_i –дің К₀ орнына К₁ -мен байланысуынан болған өзгеру эффектін мына формуламен анықтаймыз:

 

С_i0- C_i1. (4.1)

 

К₁ –ге тек қана S_i сәйкес келеді, олар үшін есептелген (4.1) айырымы дұрыс келеді. Алайда мұндай байланысатын S_i шектелген r₁. К₁ концентраторын құруға кеткен f₁ шығынын ескере отырып, эффектті есептейміз:

 

F₁¹=F⁰- (C_i0-C_i1)- … (C_j0-C_j1) +f₁.

 

(тек (C_i0-C_i1)>0 қосылған, олардың саны r₁ төмен).

Аналогтық қадам m болады (концентраторлар саны бойынша).

 

(m+1) қадам. Неғұрлым аз шығындар анықталады:

 

{F₁¹, F₂¹, … F_m¹}= F_j¹

 

Сонымен қатар, К_j концентраторын ашамыз, оған {S_g, S_l, … S_к} қосамыз.

 

2 - итерация.

K_j концентраторын ашық деп санай келе, кезектеп тағы бір концентратордан ашамыз.

 

1-қадам. K_j ашық кезінде К₁ ашамыз, бағалаймыз:

K_j –ге байланыспаған i үшін (C_i0-C_i1); (4.2)

 

g, l, … k үшін (C_gj-C_g1), яғни K_j –ге байланысқан S₁ үшін.

r₁ үшін неғұрлым үлкен (4.2) айырымдар таңдалады және шығындар есептеледі:

 

F_1,j²=F_j^’- (C_gx-C_g1)+f₁.

m-1 қадам болады (жабық концентраторлар саны бойынша).

 

m- қадам. Функцияның аз мағынасы анықталады:

 

min {F_j1², F_j2², … F_jm²}, j m.

 

3 - итерация.

Екі ашық концентратор кезінде үшіншісін ашу мүмкіндігі сарапталады.

Соңғы интерация барлық концентраторлардың бір уақытта ашылуымен түсіндіріледі. Сипатталған алгоритмді мысалмен көрсетейік.