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

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

T

лимит административных расходов на эти учреждения → 150000

M

сколько максимально населения можно приписать и обслуживать этим учреждением → 70000

R

если в городе больше R=25000, можно поставить два учреждения.

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

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

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