Optprob/Размещение административных учреждений — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
(Новая страница: «<!-- p --> {{checked|}} Есть некий регион, с n=25 городами-поселками, который можно представить неор…»)
(нет различий)

Версия 21:51, 17 ноября 2022

Есть некий регион, с n=25 городами-поселками, который можно представить неориентированным графом дорожной связности, и стоит задача размещения там административных учреждений (МФЦ, госуслуги, и т.п.).

Городок 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
Население 16547 10269 9845 1987 1254 69845 3458 10059 35001 26987 13658 15874 6987 2657 4589 3547 875 945 11536 16895 12458 25478 50145 8450 6547
Стоимость учреждения 10000 10000 10000 5000 5000 10000 6400 9000 15000 47000 6500 19800 9000 9000 10000 10000 9000 9000 10000 10000 10000 10000 10000 6400 10000
T
лимит административных расходов на эти учреждения → 150000
M
сколько максимально населения можно приписать и обслуживать этим учреждением → 70000
R
если в городе больше R=25000, можно поставить два учреждения.

Учреждением можно обслуживать города в которых нет своих учреждений, приписал все население поселка к учреждению из другого города, но тогда этим людям придется ездить.

Как обычно, верхнетреугольная матрица расстояний (пусть в километрах)

Надо, в рамках выданного бюджета, расставить учреждения по поселкам-городкам так, чтобы сумма человеко-километров по тем, кому не достанется своих учреждений (считаем, что внутри поселков добираются до своих чиновников мгновенно), была минимальной.