NLP - Оптимизация прокладки кабеля

Автор neft, 23 января 2012, 12:24

0 Пользователи и 1 гость просматривают эту тему.

neft

Задача навеяна прокладкой оптоволоконных кабелей для наблюдения за выборами 4 марта.
Задача
35 городов надо связать со СТОЛИЦЕЙ кабелями. Координаты x, y городов известны.
Вопрос
Что выгоднее, связать города со столицей напрямую, или сначала связать города с неким "Датацентром" (наивыгоднейшие координаты расположения которого нужно определить), и только он связан со СТОЛИЦЕЙ?
Рассмотреть 2 варианта:
1. Цена 1 м кабеля, связывающего "Датацентр" с городами равна цене 1 м кабеля, связывающего "Датацентр" со СТОЛИЦЕЙ.
2. Цена 1 м кабеля, связывающего "Датацентр" с городами в 10 раз меньше цены 1 м кабеля, связывающего "Датацентр" со СТОЛИЦЕЙ.

Файл с исходными данными приложен.

PS. Есть и варианты усложнения задачи:
1. Сколько нужно "Датацентров" для оптимизации затрат, если выгоднее с использованием нескольких "Датацентров", а не напрямую?
2. Города можно связывать как через "Датацентры", так и напрямую со СТОЛИЦЕЙ: нужно определить количество "Датацентров", их координаты, и какие города связаны с "Датацентрами", а какие напрямую со столицей?

[вложение удалено Администратором]

bormant

#1
Без ДЦ: ЦФ: 540,51
1) (22,80; 8,01)   ЦФ: 413,86
2) (20,42; 6,85)   ЦФ: 498,47

Для 2 ДЦ (без удорожания) (18,52; 26,07); (32,79; 28,09) ЦФ: 248,95
Без ДЦ: 1, 3, 6, 9, 13, 20, 21, 22, 27, 29
ДЦ1: 2, 5, 7, 8, 10, 12, 15, 23, 24, 26, 28, 30, 31, 32, 34
ДЦ2: 4, 11, 14, 16, 17, 18, 19, 25, 33, 35

Для 3 ДЦ (без удорожания)

ЦФ 216,63

x y
ДЦ1 32,79 28,09
ДЦ2 18,52 26,07
ДЦ3 26,59 10,21

Без ДЦ: 1, 6, 9, 21, 27, 29
ДЦ1: 4, 11, 14, 16, 17, 18, 19, 25, 33, 35
ДЦ2: 2, 5, 7, 8, 10, 12, 15, 23, 24, 26, 28, 30, 31, 32, 34
ДЦ3: 3, 13, 20, 22


ps. Являются ли эти решения глобальными минимумами -- не знаю, если удастся улучшить, то не являются ;-)
pps. Про нахождение ДЦ в городе условия не стояло :-)
Автору на яд. Поддержать форум.