Optprob/Распределение МРТ по больницам — различия между версиями

Версия 22:38, 19 февраля 2023

Проверено: StasFomin 22:38, 19 февраля 2023 (UTC) Российский олигарх решил пожертвовать E=20 единиц нового технологического оборудования для МРТ (магнитно-резонансной томографии) больницам Московской области, и решено, что каждый житель МО, должен иметь доступ к этим МРТ для диагностики.

В Московской области имеется 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
Район	1	1	1	2	2	3	3	3	3	4	4	4	4	5	5	5	5	6	6	6	7	7	8	8	8
Граждан	506500	350005	275000	247156	159874	236548	157489	325000	259001	142000	156800	247158	125698	52014	69054	189456	147569	458756	256478	156421	152310	147150	65045	89015	194520

Известно расположение больниц и расстояние между ними.

верхнетреугольная матрица 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		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

Наем технического персонала для использования оборудования является обязанностью администрации МО.

В каждой больнице, где имеется оборудование необходим технический специалист. Стоимость услуг техника составляет Ct=45000.
Если в больнице
- один МРТ, то стоимость обслуживания C1=50000
- больше одного МРТ, то стоимость обслуживания C2=80000
У администрации бюджет на это все PP=2000000
Надо, чтобы в каждом районе был хоть один МРТ.
Чем больше граждан приписаны к больнице, тем приоритетней больница для установки МРТ — больница, имеющая больше граждан, чем какая-то другая, не может иметь меньше МРТ.
Общее число граждан, приписанных к больнице, деленное на количество МРТ в больнице не должно быть больше М=400000.
С другой стороны, если больница не имеет собственного МРТ, необходимо распределить граждан этой больницы к другим, имеющим МРТ. Это грустно, и конечно, порождает недовольство, возможно гражданам теперь дольше добираться до новой больницы (в худшем случае, как раз на расстояние между старой и новой больницами).
- Но если граждане одной больницы переприписаны к другой, расстояние между этими больницами не должно превышать K=50 км (иначе совсем жестоко).

Задача состоит в том, чтобы минимизировать сумму «человеко-километров» по всем перемещенным в другие больницы гражданам.

Участник:Philipakhiarov/Распределение МРТ по больницам

@@ Строка 1: / Строка 1: @@
 <!-- p39 -->
-{{checked|}}
+{{checked|[[Участник:StasFomin|StasFomin]] 22:38, 19 февраля 2023 (UTC)}}
-{{reserve-task|[[Участник:Philipakhiarov|Philipakhiarov]] 16:33, 3 декабря 2022 (UTC)}}
 Российский олигарх решил пожертвовать E=20 единиц нового технологического оборудования для МРТ (магнитно-резонансной томографии) больницам Московской области, и решено, что каждый житель МО, должен иметь доступ к этим МРТ для диагностики.
@@ Строка 818: / Строка 816: @@
 Задача состоит в том, чтобы минимизировать сумму «человеко-километров» по всем перемещенным в другие больницы гражданам.
+* [[Участник:Philipakhiarov/Распределение МРТ по больницам]]
 {{enddiv}}
 [[Категория:OptimizationProblems]]

Optprob/Распределение МРТ по больницам — различия между версиями

Версия 22:38, 19 февраля 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		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		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		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