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

Версия 17:59, 27 ноября 2023

Проверено: StasFomin 17:59, 27 ноября 2023 (UTC)

Есть некий регион, с 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, можно поставить два учреждения.

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

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

25×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
1	0	21	23	18	19	12	12	25	72	25	4	25	25	25	18	67	67	67	67	67	25	19	12	12	25
2	0	0	25	5	13	4	4	12	5	12	19	12	12	12	12	75	75	75	75	75	12	13	4	4	12
3	0	0	0	13	15	19	19	4	9	4	13	4	25	4	25	55	55	55	55	55	4	15	19	19	4
4	0	0	0	0	59	13	13	19	39	19	15	19	12	19	12	25	25	25	25	25	19	12	13	13	19
5	0	0	0	0	0	15	15	13	45	13	12	13	12	13	4	12	12	12	12	12	13	12	15	15	13
6	0	0	0	0	0	0	19	15	23	15	4	15	4	15	19	4	4	4	4	4	15	4	12	12	15
7	0	0	0	0	0	0	0	12	22	12	19	12	19	12	13	19	19	19	19	19	12	19	12	19	12
8	0	0	0	0	0	0	0	0	10	4	13	4	13	4	15	4	15	15	4	13	4	13	4	13	4
9	0	0	0	0	0	0	0	0	0	19	15	19	15	19	12	19	12	12	19	15	19	4	19	15	19
10	0	0	0	0	0	0	0	0	0	0	12	13	12	13	4	13	4	4	13	12	13	19	13	12	13
11	0	0	0	0	0	0	0	0	0	0	0	15	4	15	19	15	19	19	15	4	15	13	15	4	15
12	0	0	0	0	0	0	0	0	0	0	0	0	19	29	13	12	13	13	12	19	12	15	12	19	25
13	0	0	0	0	0	0	0	0	0	0	0	0	0	43	15	4	15	15	4	13	4	12	15	13	12
14	0	0	0	0	0	0	0	0	0	0	0	0	0	0	12	19	24	12	19	15	19	4	12	15	4
15	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	13	36	4	13	4	13	19	11	78	19
16	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	15	19	15	19	15	13	77	49	13
17	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	13	32	13	4	15	12	29	15
18	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	23	15	19	4	4	43	12
19	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	25	13	19	19	9	4
20	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	15	13	13	11	19
21	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	15	15	12	13
22	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	12	23	15
23	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	34	20
24	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	11
25	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0

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

Задача зарезервирована: 3xMike 17:54, 4 ноября 2023 (UTC)

Версия 17:59, 27 ноября 2023 (просмотреть исходный код) StasFomin (обсуждение \| вклад) ← Предыдущая правка		Версия 17:59, 27 ноября 2023 (просмотреть исходный код) StasFomin (обсуждение \| вклад) Следующая правка →
Строка 88:		Строка 88:
	\|}		\|}

−	[[File:Размещение административных учреждений_2023-11-27_20-59-05_image0.png\|right\|~~400px~~]]	+	[[File:Размещение административных учреждений_2023-11-27_20-59-05_image0.png\|right\|200px]]

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

Версия 17:59, 27 ноября 2023

Навигация

Просмотры

Персональные инструменты

Навигация

Поиск

Инструменты

	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
1	0	21	23	18	19	12	12	25	72	25	4	25	25	25	18	67	67	67	67	67	25	19	12	12	25
2	0	0	25	5	13	4	4	12	5	12	19	12	12	12	12	75	75	75	75	75	12	13	4	4	12
3	0	0	0	13	15	19	19	4	9	4	13	4	25	4	25	55	55	55	55	55	4	15	19	19	4
4	0	0	0	0	59	13	13	19	39	19	15	19	12	19	12	25	25	25	25	25	19	12	13	13	19
5	0	0	0	0	0	15	15	13	45	13	12	13	12	13	4	12	12	12	12	12	13	12	15	15	13
6	0	0	0	0	0	0	19	15	23	15	4	15	4	15	19	4	4	4	4	4	15	4	12	12	15
7	0	0	0	0	0	0	0	12	22	12	19	12	19	12	13	19	19	19	19	19	12	19	12	19	12
8	0	0	0	0	0	0	0	0	10	4	13	4	13	4	15	4	15	15	4	13	4	13	4	13	4
9	0	0	0	0	0	0	0	0	0	19	15	19	15	19	12	19	12	12	19	15	19	4	19	15	19
10	0	0	0	0	0	0	0	0	0	0	12	13	12	13	4	13	4	4	13	12	13	19	13	12	13
11	0	0	0	0	0	0	0	0	0	0	0	15	4	15	19	15	19	19	15	4	15	13	15	4	15
12	0	0	0	0	0	0	0	0	0	0	0	0	19	29	13	12	13	13	12	19	12	15	12	19	25
13	0	0	0	0	0	0	0	0	0	0	0	0	0	43	15	4	15	15	4	13	4	12	15	13	12
14	0	0	0	0	0	0	0	0	0	0	0	0	0	0	12	19	24	12	19	15	19	4	12	15	4
15	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	13	36	4	13	4	13	19	11	78	19
16	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	15	19	15	19	15	13	77	49	13
17	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	13	32	13	4	15	12	29	15
18	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	23	15	19	4	4	43	12
19	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	25	13	19	19	9	4
20	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	15	13	13	11	19
21	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	15	15	12	13
22	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	12	23	15
23	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	34	20
24	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	11
25	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0

	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
1	0	21	23	18	19	12	12	25	72	25	4	25	25	25	18	67	67	67	67	67	25	19	12	12	25
2	0	0	25	5	13	4	4	12	5	12	19	12	12	12	12	75	75	75	75	75	12	13	4	4	12
3	0	0	0	13	15	19	19	4	9	4	13	4	25	4	25	55	55	55	55	55	4	15	19	19	4
4	0	0	0	0	59	13	13	19	39	19	15	19	12	19	12	25	25	25	25	25	19	12	13	13	19
5	0	0	0	0	0	15	15	13	45	13	12	13	12	13	4	12	12	12	12	12	13	12	15	15	13
6	0	0	0	0	0	0	19	15	23	15	4	15	4	15	19	4	4	4	4	4	15	4	12	12	15
7	0	0	0	0	0	0	0	12	22	12	19	12	19	12	13	19	19	19	19	19	12	19	12	19	12
8	0	0	0	0	0	0	0	0	10	4	13	4	13	4	15	4	15	15	4	13	4	13	4	13	4
9	0	0	0	0	0	0	0	0	0	19	15	19	15	19	12	19	12	12	19	15	19	4	19	15	19
10	0	0	0	0	0	0	0	0	0	0	12	13	12	13	4	13	4	4	13	12	13	19	13	12	13
11	0	0	0	0	0	0	0	0	0	0	0	15	4	15	19	15	19	19	15	4	15	13	15	4	15
12	0	0	0	0	0	0	0	0	0	0	0	0	19	29	13	12	13	13	12	19	12	15	12	19	25
13	0	0	0	0	0	0	0	0	0	0	0	0	0	43	15	4	15	15	4	13	4	12	15	13	12
14	0	0	0	0	0	0	0	0	0	0	0	0	0	0	12	19	24	12	19	15	19	4	12	15	4
15	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	13	36	4	13	4	13	19	11	78	19
16	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	15	19	15	19	15	13	77	49	13
17	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	13	32	13	4	15	12	29	15
18	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	23	15	19	4	4	43	12
19	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	25	13	19	19	9	4
20	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	15	13	13	11	19
21	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	15	15	12	13
22	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	12	23	15
23	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	34	20
24	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	11
25	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0

	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
1	0	21	23	18	19	12	12	25	72	25	4	25	25	25	18	67	67	67	67	67	25	19	12	12	25
2	0	0	25	5	13	4	4	12	5	12	19	12	12	12	12	75	75	75	75	75	12	13	4	4	12
3	0	0	0	13	15	19	19	4	9	4	13	4	25	4	25	55	55	55	55	55	4	15	19	19	4
4	0	0	0	0	59	13	13	19	39	19	15	19	12	19	12	25	25	25	25	25	19	12	13	13	19
5	0	0	0	0	0	15	15	13	45	13	12	13	12	13	4	12	12	12	12	12	13	12	15	15	13
6	0	0	0	0	0	0	19	15	23	15	4	15	4	15	19	4	4	4	4	4	15	4	12	12	15
7	0	0	0	0	0	0	0	12	22	12	19	12	19	12	13	19	19	19	19	19	12	19	12	19	12
8	0	0	0	0	0	0	0	0	10	4	13	4	13	4	15	4	15	15	4	13	4	13	4	13	4
9	0	0	0	0	0	0	0	0	0	19	15	19	15	19	12	19	12	12	19	15	19	4	19	15	19
10	0	0	0	0	0	0	0	0	0	0	12	13	12	13	4	13	4	4	13	12	13	19	13	12	13
11	0	0	0	0	0	0	0	0	0	0	0	15	4	15	19	15	19	19	15	4	15	13	15	4	15
12	0	0	0	0	0	0	0	0	0	0	0	0	19	29	13	12	13	13	12	19	12	15	12	19	25
13	0	0	0	0	0	0	0	0	0	0	0	0	0	43	15	4	15	15	4	13	4	12	15	13	12
14	0	0	0	0	0	0	0	0	0	0	0	0	0	0	12	19	24	12	19	15	19	4	12	15	4
15	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	13	36	4	13	4	13	19	11	78	19
16	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	15	19	15	19	15	13	77	49	13
17	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	13	32	13	4	15	12	29	15
18	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	23	15	19	4	4	43	12
19	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	25	13	19	19	9	4
20	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	15	13	13	11	19
21	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	15	15	12	13
22	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	12	23	15
23	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	34	20
24	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	11
25	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0