Ћекции.ќрг


ѕоиск:




 атегории:

јстрономи€
Ѕиологи€
√еографи€
ƒругие €зыки
»нтернет
»нформатика
»стори€
 ультура
Ћитература
Ћогика
ћатематика
ћедицина
ћеханика
ќхрана труда
ѕедагогика
ѕолитика
ѕраво
ѕсихологи€
–елиги€
–иторика
—оциологи€
—порт
—троительство
“ехнологи€
“ранспорт
‘изика
‘илософи€
‘инансы
’ими€
Ёкологи€
Ёкономика
Ёлектроника

 

 

 

 


«агальна характеристика задач оптим≥зац≥њ




—кладн≥сть оптим≥зац≥њ мереж поштового звТ€зку визначаЇтьс€ надто великою к≥льк≥стю можливих вар≥ант≥в зТЇднанн€ обТЇкт≥в мереж≥ м≥ж собою.

«агальна к≥льк≥сть можливих вар≥ант≥в зТЇднанн€ n обТЇкт≥в м≥ж собою визначаЇтьс€ сумою можливих вар≥ант≥в зТЇднанн€ зазначених обТЇкт≥в по 2, по 3,..., по n, тобто

,

де - к≥льк≥сть розм≥щень з n обТЇкт≥в по k,

при цьому кожна пара обТЇкт≥в може бути зТЇднана способами.

” табл. 1.1 надан≥ значенн€ у залежност≥ в≥д значень n = 2, 3,..., 10.

“аблиц€ 1.1. «алежн≥сть значень в≥д значень n

n                  
                 

 

ѕри реальн≥й к≥лькост≥ вузл≥в мереж≥ поштового звТ€зку n ≈ 120, значенн€ с€гають астроном≥чних величин, за €ких розрахунок, а тим б≥льш анал≥з ≥ оптим≥зац≥€ структур мереж поштового звТ€зку у загальному вид≥ ви€вл€ютьс€ недос€жними а н≥ дл€ сучасних, а н≥ дл€ майбутн≥х ≈ќћ.

 ажуть, що над под≥бними задачами т€ж≥Ї прокл€тт€ розм≥рност≥.

ƒ≥йсно, враховуючи, що , де Ц к≥льк≥сть сполучень з n обТЇкт≥в по k, тобто >> , а , значенн€ >>2 n.

¬т≥м, будемо вважати ≈ 2 n.

ѕро фантастичну величину числа 2120 можна судити з таких м≥ркувань.

ѕрипустимо, що дл€ розвТ€занн€ задач≥ оптим≥зац≥њ структури мереж≥ поштового звТ€зку використовуЇтьс€ суперкомпТютер, швидкод≥€ €кого 3Ј1010 операц≥й за секунду (це теоретична межа швидкод≥њ компТютера у вид≥ сфери д≥аметром 1 см, €ка визначаЇтьс€ лише часом розповсюдженн€ електромагн≥тноњ хвил≥ в≥д одного краю сфери до протилежного).

Ѕудемо вважати, що розрахунок одного вар≥анту побудови структури мереж≥ поштового звТ€зку потребуЇ виконанн€ лише одн≥Їњ операц≥њ компТютера.

ѕодамо число у вид≥ ≈ 2120 ≈ 1036. “од≥ дл€ розрахунку вс≥х можливих вар≥ант≥в повинно бути витрачено 1036/(3Ј1010) = 0,33Ј1026 секунд або 1018 (м≥ль€рд м≥ль€рд≥в) рок≥в!

ѕроте, ≥Їрарх≥чн≥ принципи побудови мереж≥ поштового звТ€зку, за €кими оптим≥зац≥€ мереж≥ поштового звТ€зку в ц≥лому може бути зам≥нена оптим≥зац≥Їю окремих мереж на кожному з р≥вн≥в ≥Їрарх≥њ; можлив≥сть переходу в≥д повного перебору вар≥ант≥в розвТ€занн€ задач оптим≥зац≥њ мереж поштового звТ€зку до њх спр€мованого перебору; обмеженн€ на к≥льк≥сть ≥ м≥сц€ розташуванн€ обТЇкт≥в поштового звТ€зку, обумовлен≥ вимогами до њх м≥сцеположенн€ серед ≥нших обТЇкт≥в поштового звТ€зку, на€вност≥ розвиненоњ техн≥чноњ ≥нфраструктури, на€вност≥ в≥дпов≥дних шл€х≥в сполученн€; обмеженн€ на к≥льк≥сть обТЇкт≥в поштового звТ€зку, що можуть обслуговуватис€ одним поштовим маршрутом, обумовлен≥ допустимим часом проходженн€ поштових маршрут≥в ≥ вантажоп≥дйомн≥стю транспортних засоб≥в, що використовуютьс€ дл€ перевезень пошти; можлив≥сть застосуванн€ анал≥тичних залежностей м≥ж де€кими параметрами мереж поштового звТ€зку, зокрема, рекурентних; розташуванн€ екстремум≥в ц≥льових функц≥й б≥льшою частиною в област≥ малих значень зм≥нних; р€д ≥нших ефективних метод≥в дозвол€ють радикально скоротити розм≥рност≥ задач оптим≥зац≥њ мереж поштового звТ€зку ≥ розвТ€зати њх за допомогою ≈ќћ з середньою швидкод≥Їю.

ѕри побудов≥ структури мереж≥ поштового звТ€зку за адм≥н≥стративно-територ≥альним принципом в центрах в≥дпов≥дних адм≥н≥стративних утворень ”крањни створюютьс€ обТЇкти поштового звТ€зку ун≥версального призначенн€, ≥Їрарх≥чна п≥дпор€дкован≥сть €ких в≥дпов≥даЇ ≥Їрарх≥чн≥й п≥дпор€дкованост≥ зазначених адм≥н≥стративних утворень: ”крањна (√оловний вузол або «ональний вузо) Ц ќбласть (ќбласний вузол) Ц –айон (–айонний вузол) Ц —≥льрада (¬≥дд≥ленн€ звТ€зку).

ѕри побудов≥ структури мереж≥ поштового звТ€зку за функц≥онально-територ≥альним принципом обТЇкти поштового звТ€зку створюютьс€ за функц≥ональним призначенн€м там, де це економ≥чно доц≥льно.

ѕри переход≥ в≥д структури мереж≥ поштового звТ€зку, побудованоњ за адм≥н≥стративно-територ≥альним принципом, до структури мереж≥ поштового звТ€зку, побудованоњ за функц≥онально-територ≥альним принципом, на територ≥њ ”крањни передбачено створенн€ поштових рег≥он≥в з –ег≥ональними (м≥жобласними) вузлами поштового звТ€зку, а на територ≥€х поштових рег≥он≥в Ц поштових округ≥в з ќкружними (м≥жрайонними) вузлами поштового звТ€зку.

Ќа рис. 1.2 наведено сп≥вв≥дношенн€ р≥вн≥в ≥Їрарх≥њ мереж поштового звТ€зку (а Ц мереж≥, побудованоњ за адм≥н≥стративно-територ≥альним принципом, б Ц мереж≥, побудованоњ за функц≥онально-територ≥альним принципом).

 

–исунок 1.2. —п≥вв≥дношенн€ р≥вн≥в ≥Їрарх≥њ мереж поштового звТ€зку

 

Ќа рис. 1.3 наведено узагальнен≥ структури мереж поштового звТ€зку (а Ц мереж≥, побудованоњ за адм≥н≥стративно-територ≥альним принципом, б Ц мереж≥, побудованоњ за функц≥онально-територ≥альним принципом).

 

       
   
«ональн≥ вузли     ќбласн≥ вузли     –айонн≥ вузли   ¬≥дд≥ленн€ звТ€зку  
 
 

 


 

 

 
 


 

 

а

 
 

 

 


б

–исунок 1.3. ”загальнен≥ структури мереж поштового звТ€зку

 

¬ мереж≥ поштового звТ€зку, побудован≥й за адм≥н≥стративно-територ≥альним принципом, обТЇкти р≥вн€ ≥Їрарх≥њ 1 (зональн≥ вузли) зТЇднуютьс€ м≥ж собою маг≥стральними поштовими маршрутами; кожний обТЇкт р≥вн€ ≥Їрарх≥њ 1 (зональний вузол) зТЇднуЇтьс€ з ус≥ма п≥дпор€дкованими йому обТЇктами р≥вн€ ≥Їрарх≥њ 2 (обласн≥ вузли) зональними поштовими маршрутами; кожний обТЇкт р≥вн€ ≥Їрарх≥њ 2 (обласний вузол) зТЇднуЇтьс€ з ус≥ма п≥дпор€дкованими йому обТЇктами р≥вн€ ≥Їрарх≥њ 3 (районн≥ (м≥ськ≥) вузли) обласними поштовими маршрутами; кожний обТЇкт р≥вн€ ≥Їрарх≥њ 3 (районний (м≥ський) вузол) зТЇднуЇтьс€ з ус≥ма п≥дпор€дкованими йому обТЇктами р≥вн€ ≥Їрарх≥њ 4 (в≥дд≥ленн€ звТ€зку) районними (м≥ськими) поштовими маршрутами.

¬ мереж≥ поштового звТ€зку, побудован≥й за функц≥онально-територ≥альним принципом, обТЇкти р≥вн€ ≥Їрарх≥њ 1 (рег≥ональн≥ вузли) зТЇднуютьс€ м≥ж собою маг≥стральними поштовими маршрутами; кожний обТЇкт р≥вн€ ≥Їрарх≥њ 1 (рег≥ональний вузол) зТЇднуЇтьс€ з ус≥ма п≥дпор€дкованими йому обТЇктами р≥вн€ ≥Їрарх≥њ 2 (окружн≥ вузли) рег≥ональними поштовими маршрутами; кожний обТЇкт р≥вн€ ≥Їрарх≥њ 2 (окружний вузол) зТЇднуЇтьс€ з ус≥ма п≥дпор€дкованими йому обТЇктами р≥вн€ ≥Їрарх≥њ 3 (в≥дд≥ленн€ звТ€зку) окружними поштовими маршрутами.

“аким чином, €к структура мереж≥ поштового звТ€зку, побудованоњ за адм≥н≥стративно-територ≥альним принципом, так ≥ структура мереж≥ поштового звТ€зку, побудованоњ за функц≥онально-територ≥альним принципом, розбиваЇтьс€ на структури р≥зних р≥вн≥в ≥Їрарх≥њ, причому структури маг≥стральних мереж мають чисельн≥ можлив≥ вар≥анти своЇњ побудови ≥ тому потребують оптим≥зац≥њ, а структури мереж на вс≥х ≥нших р≥вн€х ≥Їрарх≥њ визначен≥ однозначно ≥ тому не потребують оптим≥зац≥њ.

як випливаЇ з рис. 1.3, пересиланн€ пошти в мереж≥ поштового звТ€зку, побудован≥й за адм≥н≥стративно-територ≥альним принципом, у найб≥льш неспри€тливому випадку зд≥йснюЇтьс€ за схемою ¬≥дд≥ленн€ звТ€зку Ц –айонний вузол Ц ќбласний вузол Ц «ональний вузол Ц «ональний вузол Ц ќбласний вузол Ц –айонний вузол Ц ¬≥дд≥ленн€ звТ€зку (8 обТЇкт≥в, 7 маршрут≥в), а в мереж≥ поштового звТ€зку, побудован≥й за функц≥онально-територ≥альним принципом, Ц за схемою ¬≥дд≥ленн€ звТ€зку Ц ќкружний вузол Ц –ег≥ональний вузол Ц –ег≥ональний вузол Ц ќкружний вузол Ц ¬≥дд≥ленн€ звТ€зку (6 обТЇкт≥в, 5 маршрут≥в).

“аким чином, при переход≥ в≥д побудови мереж≥ поштового звТ€зку за адм≥н≥стративно-територ≥альним принципом до побудови мереж≥ поштового звТ€зку за функц≥онально-територ≥альним принципом, максимальна к≥льк≥сть обТЇкт≥в поштового звТ€зку, зад≥€них у пересиланн≥ пошт≥вок, скорочуЇтьс€ з 8 до 6 (в 1,33 рази), а максимальна к≥льк≥сть поштових маршрут≥в, зад≥€них у цьому пересиланн≥, Ц з 7 до 5 (в 1,4 рази). «авд€ки цьому суттЇво зменшуютьс€ витрати на обробленн€ пошти, скорочуЇтьс€ к≥льк≥сть поштових маршрут≥в, скорочуЇтьс€ час пересиланн€ пошти, спрощуЇтьс€ синхрон≥зац≥€ обробленн€ ≥ перевезенн€ пошти.

«азначимо, що на€вн≥сть зональних вузл≥в в мереж≥ поштового звТ€зку, побудован≥й за адм≥н≥стративно-територ≥альним принципом, ≥ рег≥ональних вузл≥в в мереж≥ поштового звТ€зку, побудован≥й функц≥онально-територ≥альним принципом, не Ї обовТ€зковою, зокрема, зазначен≥ вузли можуть бути взагал≥ в≥дсутн≥, або зам≥сть них може використовуватис€ Їдиний головний вузол поштового звТ€зку.

« методичних м≥ркувань задач≥ оптим≥зац≥њ мереж поштового звТ€зку под≥лен≥ на дв≥ групи.

ƒо першоњ групи в≥днесен≥ типов≥ задач≥, що мають певне самост≥йне значенн€, ≥ дл€ розвТ€занн€ €ких використовуютьс€ методи теор≥њ граф≥в. –озвТ€занн€ задач ц≥Їњ групи наведене у другому розд≥л≥ монограф≥њ.

ƒо другоњ групи в≥днесен≥ спец≥ф≥чн≥ задач≥, що виникають у контекст≥ узагальнених задач оптим≥зац≥њ обробленн€ ≥ перевезенн€ пошти, ≥ дл€ розвТ€занн€ €ких, кр≥м метод≥в теор≥њ граф≥в, використовуютьс€ також ≥нш≥ методи.

 






ѕоделитьс€ с друзь€ми:


ƒата добавлени€: 2015-11-05; ћы поможем в написании ваших работ!; просмотров: 451 | Ќарушение авторских прав


ѕоиск на сайте:

Ћучшие изречени€:

Ќеосмысленна€ жизнь не стоит того, чтобы жить. © —ократ
==> читать все изречени€...

2092 - | 1832 -


© 2015-2024 lektsii.org -  онтакты - ѕоследнее добавление

√ен: 0.017 с.