Доброго времени суток!
У меня такая задача:
Дана карта (текстовый файл), в котором содержится множество '0' и '1'. '1' - это дом, '0' - пустое пространство. Группа вплотную расположенных '1' - единый дом. В другом файле содержатся количество жителей каждого дома. Нужно подключить все дома к GSM-сети.
В состав GSM-сети входят:
- базовая станция (200 тыс. соединений(кол-во конечных подключаемых абонентов домов), цена: 100000 ед. служит для соединения сотовых станций, только проводное соед.);
- сотовая станция (5 тыс. соед., 100000 ед., служит для соединения ст.связи, только провод.);
- ст.связи (1 тыс. соед., 10000 ед., служит для подсоединения конечных домов по проводной связи и секторов по беспроводной связи(при подключении секторов количество абонентов ст. связи уменьшается до 500));
- сектор (100 соед., 1000 ед., служит для подсоединения конечных абонентов домов по беспроводной связи. Радиус действия ограничен);
- проводное соединение (цена 1 клетки: 100 ед.)
- беспроводное соединение (цена 1 клетки: 10 ед.)
Нужно разместить все станции связи и подключить абонентов к сети с минимальными затратами. Разместить станции и проводные/беспроводные соединения нужно на карте(т.е. в виде двумерного массива '0' и '1' в файле).
Насколько я понимаю, это задача оптимизации, т.е сначала нужно расположить оптимальным образом баз. станции, затем анализировать размещение сотовых станций, ст. связи, секторов, и выбирать самый наименьший по стоимости и приемлемый по размещению (чтобы хватило свободного пространства на карте).
Фактически, нужно минимизировать функцию y=100000*(кол-во баз.ст.)+100000*(кол-во сот.ст.) + 10000*(кол-во ст. связи) + 100*(кол-во единиц проводов) + 10*(кол-во ед. беспроводного соед.)
Какую мат. модель или какие-либо конкретные методы и алгоритмы можно использовать при размещении станций на карте(по клеткам) и анализе оптимальности варианта размещения станций?