Зарезервированные практические задачи

Ссылки сюда (15) →

Всего страниц найдено: 21.

----

К задаче…

Три медицинские службы состоят из 10, 6 и 4 врачей соответственно; каждый врач принимает максимум 10 пациентов.

Стоимость лечения каждого пациента составляет

• 10 евро в день для службы 1,
• 20 евро в день для службы 2,
• 25 евро в день для службы 3.

Общий дневной бюджет для трех служб составляет 2400 евро.

Кроме того, первые две службы должны обслуживать как минимум в два раза больше пациентов, чем служба 3.

Сценарий 1

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

Сценарий 2

Дневной бюджет был увеличен до €3200.

Больница должна принять решение: открыть четвертую медицинскую службу с 5 новыми врачами и стоимостью обслуживания одного пациента 22 €/день или увеличить каждую из существующих служб на два врача.

Определите, какое решение принять, с целью максимизации общего количества принятых пациентов.

Задача зарезервирована: Сергей Артерчук 10:59, 27 декабря 2023 (UTC)

---

---

К задаче…

Задача зарезервирована: Sfirstov 22:39, 22 декабря 2023 (UTC)

Директор школы должен распределить

• преподавание 5 предметов, A1, A2, A3, A4 и A5,
• между 4 учителями, P1, P2, P3 и P4,
• принимая во внимание рейтинги опросов учеников и некоторые ограничения, налагаемые МинОбром.

На основе опросов предыдущих лет мы получили следующие средние оценки (шкала: 0 - плохо, 5 - отлично):

Ограничения гласят

• Учитель P3 не может преподавать предметы A1 и A2.
• Учитель P1 должен вести только один предмет.
• Предметы должны преподаваться все.
• Ни один учитель не может остаться без предметов.

Распределите учителей так, чтобы максимизировать среднюю оценку учителя за предмет.

---

---

К задаче…

Бонусная задача

Докажите, что для каждого целого числа n существует раскраска ребер полного графа K_n в два цвета, такое что полное число одноцветных подграфов K_4 будете не больше чем \binom{n}{4} 2^{-5}

Задача зарезервирована: StasFomin 11:32, 19 мая 2023 (UTC)

---

---

К задаче…

Докажите, что E[X^k] ≥ E[X]^k для любого целого k ≥ 1.

Задача зарезервирована: Ermakov

---

---

К задаче…

Предположим, что бросают десять стандартных шестисторонних костей.

Какова вероятность того, что их сумма будет деленной на 6, предполагая, что броски независимы?

Задача зарезервирована: Ermakov

---

---

К задаче…

Медицинская компания рекламирует свой новый тест на определенное заболевание.

Частота ошибок первого рода (false negative) мала: если у вас есть расстройство, вероятность того, что тест вернет положительный результат, составляет 0.999.

Частота ошибок второго рода (false positive) тоже невелика: если у вас нет расстройства, вероятность того, что тест вернет положительный результат, составляет всего 0.005.

Предположим, что эту болезнь имеет 2% населения.

Если мы проверяем человека, выбранного равномерно из популяции, и получается положительный результат, какова вероятность того, что эта болезнь у него действительно есть?

Задача зарезервирована: Ermakov

---

---

К задаче…

showtotal=yes namespace=Main limit=500 order=lastedit desc,pagename output=template template=IncludeCard2 redirect=no category=Теоретические_задачи notcategory=Solved notcategory=Решенные_задачи notcategory=OptimizationProblems ignore=Permission denied ignore=A ignore=Open_Exercises ignore=Открытые_теоретические_задачи

---

---

К задаче…

• Набор инструкций, формирующих некий блок без переходов,
  • N доступных регистров,
  • стоимость S_i, \ \ 1≤i≤N чтения и записи в регистр i.
• Порядок резервирования регистров для этой последовательности инструкций.
• Минимизировать полную стоимость чтения-записи в регистры.

---

Задача в лаб22 (рид-онли просмотр)

---

• Задача в базе NP-полных задач Вигго Кана

Задача зарезервирована: Dainbow 15:30, 25 марта 2024 (UTC)

---

---

К задаче…

• Набор задач T, m процессоров, время выполнения l(t,i)∈ Z^+, \ \ ∀t∈ T, \ i∈ [1..m].
• Найти m-процессорное расписание для T, т.е. функцию f: T→ [1..m].
• Минимизировать время выполнения расписания, т.е.

\max\limits_{i∈ [1..m]}\displaystyle\sum\limits_{t∈  T: \atop f(t)=i} l(t,i) → min 

---

Задача в лаб22 (рид-онли просмотр)

---

• Задача в базе NP-полных задач Вигго Кана
• Код задачи в книге «ГД» → «SS8» (обобщение)

Задача зарезервирована: Stanislav 16:55, 1 апреля 2024 (UTC)

---

---

К задаче…

• Набор X векторов из [0,1]^{d}.
• Найти разбиение X на m подмножеств S_{1},…,S_{m}
• Максимизировать покрывающих подмножеств среди \{S_{1},…,S_{m}\}, где «покрывающим» подмножество S векторов из [0,1]^{d}, считается, если для всех i ≤ d сумма i-х компонент элементов из S будет не меньше 1.

---

Задача в лаб22 (рид-онли просмотр)

---

• Задача в базе NP-полных задач Вигго Кана

Задача зарезервирована: Mishaglik 17:36, 13 мая 2024 (UTC)

---

---

К задаче…

Задача зарезервирована: Protobarhatus 16:13, 9 мая 2024 (UTC)

• Набор C из m городов с заданными расстояниями между ними d(c_i,c_j)∈ N для каждой пары городов. Расстояния удовлетворяют неравенству треугольника!
• Найти тур C, т.е. перестановка \pi: [1..m]→ [1..m].
• Минимизировать длину этого тура

d\left(\{c_{\pi(m)},c_{\pi(1)}\}\right)+\displaystyle\sum\limits_{i=1}^{m-1} d\left(\{c_{\pi(i)},c_{\pi(i+1)}\}\right)

---

Задача в лаб22 (рид-онли просмотр)

---

• Задача в базе NP-полных задач Вигго Кана

---

---

К задаче…

showtotal=yes namespace=Main limit=500 order=lastedit desc,pagename output=template template=IncludeCard2 redirect=no category=ClassicHardProblems notcategory=Solved notcategory=Теоретические_задачи ignore=Permission denied ignore=A ignore=Open Classic Hard Problems

---

---

К задаче…

Граф G=(V,E).

Найти раскраску G, т.е. разбиение V на непересекающиеся наборы

V₁, V₂, …, V_k, такие, что каждый V_i независимое множество в G.

Минимизировать размерность раскраски, т.е. число этих независимых наборов V_i.

---

Задача в лаб22 (рид-онли просмотр)

---

• Задача в базе NP-полных задач Вигго Кана
• Код задачи в книге «ГД» → «GT4»

Задача зарезервирована: Alekseevk1 08:41, 16 августа 2023 (UTC)

---

---

К задаче…

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

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

Вот, какие экскурсии выбрал каждый экскурсант:

122 строк отношения «Экскурсант хочет Экскурсию»

Экскурсант	Экскурсия
1	1
1	3
1	5
2	2
2	4
3	6
4	2
5	1
5	5
6	4
6	6
6	3
7	1
7	4
7	5
8	3
8	5
9	2
10	1
10	3
11	1
11	4
12	3
12	5
13	6
13	4
14	2
14	6
15	2
15	4
16	4
16	5
17	2
17	6
18	2
18	6
19	1
19	4
20	6
20	2
21	1
21	3
22	4
22	6
23	6
24	1
24	3
24	6
25	2
26	2
26	4
27	4
27	5
28	3
28	5
29	6
29	3
30	1
30	4
30	5
31	6
32	2
33	1
33	3
34	2
34	4
35	4
35	6
36	6
36	2
37	1
37	3
37	5
38	4
38	5
38	6
39	2
40	3
40	5
41	2
41	6
42	2
42	6
43	3
44	4
44	5
45	1
45	4
46	2
46	6
47	2
47	4
48	4
48	6
49	6
50	2
50	6
51	2
52	3
52	5
53	1
53	3
54	3
54	5
55	6
55	2
56	1
56	3
56	5
57	1
57	4
57	5
58	2
58	4
59	4
59	6
59	3
60	4
60	5
60	6

• Автобусы компании имеют вместимость (количество мест). У компании 5 автобусов.

Buses	1	2	3	4	5
	60	50	60	60	40

Один автобус в день может совершить несколько экскурсий в зависимости от близости между ними.

Эта информация будет собрана в бинарном атрибуте между экскурсиями (1: они могут быть

выполняться одним и тем же автобусом, 0: нет).

Вблизи	1	2	3	4	5	6
1	0	1	0	0	0	1
2	0	0	0	1	1	0
3	0	0	0	0	1	0
4	0	0	0	0	1	0
5	0	0	0	0	0	0
6	0	0	0	0	0	0

• Однако автобус не должен охватывать более двух экскурсий за один день.
• Компания хочет спланировать экскурсии на 3 дня, чтобы использовать наименьшее количество автобусов

(минимизируем «автобусо-дни»).

• • При этом нужно найти назначение экскурсий и экскурсантов на рейсы автобусов

Задача зарезервирована: Ivanstepanov 9:01, 21 ноября 2023 (UTC)

---

---

К задаче…

Задача зарезервирована: Gleb Berezin M05-203v 14:25, 5 декабря 2023 (UTC)

Мы планируем распределять инженеров по проектам компании.

В течение следующего года компания имеет возможность участвовать в десяти инженерных проектах.

Каждый проект требует персонала (для проекта j потребуется Aj инженеров любого типа), приносит доход (G_j) и имеет общие расходы (C_j).

Projects	1	2	3	4	5	6	7	8	9	10
A	3	3	3	2	2	2	4	4	4	5
C	10000	20000	25000	40000	10000	40000	20000	25000	10000	30000
G	55000	60000	60000	90000	30000	100000	65000	50000	50000	60000

Инженеры компании делятся на две категории:

• S: Старший инженер (с опытом)
• JJ: Младший инженер (без достаточного опыта)

Каждый инженер имеет годовую зарплату M.

В настоящее время компания располагает штатом, состоящим из семи старших инженеров и четырех младших инженеров.

Engineers	1	2	3	4	5	6	7	8	9	10	11
S	1	1	0	0	0	1	0	1	0	1	0
JJ	0	0	1	1	1	0	1	0	1	0	1
M	50000	45000	30000	35000	28000	58000	36000	55000	35000	50000	33000

Каждый инженер, будь то старший или младший, подходит для каждого из проектов, в зависимости от их подготовки. Эта пригодность измеряется в виде непрерывного индекса от 0 (нет) до 1 (оптимально).

	1	2	3	4	5	6	7	8	9	10
1	0	1	0.5	0.5	0.5	1	0.3	0.2	0.4	0.8
2	0.5	0.5	1	0.3	0.2	0.4	1	1	0	0
3	1	1	0	0	1	0	0.4	0.5	0.6	0.5
4	2	0.5	0.5	1	0.3	0.2	0.4	2	0.3	0.5
5	0.5	1	0.3	0.2	0.4	1	1	1	0.3	0
6	0.2	0.5	0.5	3	0	0	1	1	1	0.6
7	1	0.6	0.7	0.5	0.5	1	0.3	0.2	0.4	0.6
8	1	3	3	3	0.5	1	0.3	0.2	0.4	1
9	0	1	1	0.5	0.5	1	0.3	0.2	0.4	0.1
10	0.5	1	0.3	0.2	0.5	1	0.3	0.2	0.4	1
11	0.5	1	0.3	0.2	0.5	1	0.3	0.2	0.4	1

Компания имеет возможность нанимать новых инженеров.

Затраты, которые компания оценивает для найма новых сотрудников, следующие

следующим образом:

• Старший инженер: $50 000/год
• Младшие инженеры: $35 000/год

Для новых инженеров компания присваивает пригодность 75% старшим инженерам и 50% младшим, так как персонал будет подбираться в соответствии к проектам.

Существует два типа назначений для инженеров:

• частичная занятость
• полный рабочий день

Компания позволяет назначить инженера на неполный или полный рабочий день на проекты. Если он работает полный рабочий день, он может быть занят только в одном проекте.

Если неполный рабочий день — может быть максимум в двух.

Новые инженеры могут быть назначены только эксклюзивно.

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

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

Если инженеры назначены на неполный рабочий день, то два инженера на неполный рабочий день считаются как

один инженер.

Компания хочет, чтобы

• в каждом проекте, в котором она участвует, был как минимум один старший инженер (новый или уже работающий) на полную ставку.
• общая пригодность инженеров, назначенных на проект, была выше 50% — расчет общей пригодности производится как сумма пригодности инженеров, назначенных на проект, деленная на количество назначенных инженеров, независимо от того, работают ли они неполный или полный рабочий день.

Помимо всего этого, существуют и другие спецификации:

• В проекте не должно быть более трех инженеров, работающих неполный рабочий день.
• Проекты 5 и 6 не могут иметь ни одного общего инженера в этих двух проектах.
• Участие в проекте 2 на неполный рабочий день требует участия в проекте 3.

Цель компании — максимизация прибыли: «Доход от проектов» - «Расходы» (расходы на заработную плату + общие расходы).

---

---

К задаче…

Задача зарезервирована: Sfirstov 18:05, 12 декабря 2023 (UTC)

Задача Штейнера о минимальном дереве.

Т.е. у нас есть неориентированный граф, где

• N=74 узлов, узлы графа двух типов:

Терминальные

Они должны быть частью сети.

Штейнера

Не обязательно, чтобы они были частью сети.

	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	26	27	28	29	30	31	32	33	34	35	36	37	38	39	40	41	42	43	44	45	46	47	48	49	50	51	52	53	54	55	56	57	58	59	60	61	62	63	64	65	66	67	68	69	70	71	72	73	74
Терминальный?	0	0	0	0	0	0	0	0	0	1	1	1	0	1	0	0	0	1	0	0	0	1	0	0	0	0	1	0	1	1	0	0	1	0	0	1	1	1	0	0	0	0	0	0	1	1	1	1	0	0	1	0	0	0	1	0	1	0	1	0	0	0	0	1	0	1	0	0	0	0	0	0	0	0

• M=153 неориентированных ребер в весом-стоимостью, которых мы представим 306 двойными дугами, ребро (i, j, w) → в ребро i→j (w) и ребро j→i (w)

сотни дуг с весами

1	18	2
2	20	2
3	1	1
3	23	3
3	74	8
4	13	3
5	3	2
5	4	6
5	16	6
5	20	3
5	47	6
5	50	7
5	59	10
5	68	5
6	32	1
6	59	3
7	23	9
8	1	1
8	33	5
8	44	5
9	16	7
9	37	8
10	12	8
13	26	9
13	30	4
14	52	2
14	54	2
14	62	4
15	24	8
15	41	1
16	15	9
16	19	6
17	44	6
17	1	2
18	24	2
18	63	6
18	69	3
19	6	6
19	38	8
19	72	8
20	7	7
21	42	3
22	11	4
22	28	5
22	43	6
22	51	3
23	39	5
24	57	4
25	36	1
25	66	5
26	16	10
26	53	3
27	48	3
29	31	3
31	48	9
31	72	2
32	28	2
32	25	2
33	13	9
33	17	7
34	11	3
35	34	10
35	42	1
36	7	2
36	68	8
37	68	1
37	73	10
39	9	1
39	28	8
39	45	8
39	54	3
39	65	6
39	71	2
40	12	5
40	27	2
40	52	3
40	20	8
41	30	6
41	52	2
42	14	5
42	30	10
42	62	3
42	72	7
43	10	5
11	42	7
44	7	5
44	59	6
45	40	1
46	5	9
46	25	6
46	15	7
46	39	9
48	24	6
49	38	1
49	47	6
49	53	7
49	56	4
50	67	6
50	71	6
51	38	1
51	42	9
51	63	10
51	70	8
52	47	5
52	66	8
52	70	1
53	9	8
53	25	9
54	36	2
55	9	7
55	17	1
55	49	3
55	61	7
56	2	6
56	59	3
56	65	1
57	63	5
58	70	7
60	15	2
60	17	1
60	25	1
60	29	1
61	8	8
61	58	6
62	7	7
62	48	2
62	58	2
62	64	1
64	55	3
65	11	5
66	39	10
67	55	1
67	72	4
68	6	10
68	19	5
68	21	3
68	22	10
68	56	6
68	64	7
69	21	2
69	35	5
70	4	7
70	23	5
70	10	10
70	34	17
71	1	9
72	2	7
72	43	6
73	8	6
73	26	6
74	10	5
74	37	3
74	71	4
18	1	2
20	2	2
1	3	1
23	3	3
74	3	8
13	4	3
3	5	2
4	5	6
16	5	6
20	5	3
47	5	6
50	5	7
59	5	10
68	5	5
32	6	1
59	6	3
23	7	9
1	8	1
33	8	5
44	8	5
16	9	7
37	9	8
12	10	8
26	13	9
30	13	4
52	14	2
54	14	2
62	14	4
24	15	8
41	15	1
15	16	9
19	16	6
44	17	6
1	17	2
24	18	2
63	18	6
69	18	3
6	19	6
38	19	8
72	19	8
7	20	7
42	21	3
11	22	4
28	22	5
43	22	6
51	22	3
39	23	5
57	24	4
36	25	1
66	25	5
16	26	10
53	26	3
48	27	3
31	29	3
48	31	9
72	31	2
28	32	2
25	32	2
13	33	9
17	33	7
11	34	3
34	35	10
42	35	1
7	36	2
68	36	8
68	37	1
73	37	10
9	39	1
28	39	8
45	39	8
54	39	3
65	39	6
71	39	2
12	40	5
27	40	2
52	40	3
20	40	8
30	41	6
52	41	2
14	42	5
30	42	10
62	42	3
72	42	7
10	43	5
42	11	7
7	44	5
59	44	6
40	45	1
5	46	9
25	46	6
15	46	7
39	46	9
24	48	6
38	49	1
47	49	6
53	49	7
56	49	4
67	50	6
71	50	6
38	51	1
42	51	9
63	51	10
70	51	8
47	52	5
66	52	8
70	52	1
9	53	8
25	53	9
36	54	2
9	55	7
17	55	1
49	55	3
61	55	7
2	56	6
59	56	3
65	56	1
63	57	5
70	58	7
15	60	2
17	60	1
25	60	1
29	60	1
8	61	8
58	61	6
7	62	7
48	62	2
58	62	2
64	62	1
55	64	3
11	65	5
39	66	10
55	67	1
72	67	4
6	68	10
19	68	5
21	68	3
22	68	10
56	68	6
64	68	7
21	69	2
35	69	5
4	70	7
23	70	5
10	70	10
34	70	17
1	71	9
2	72	7
43	72	6
8	73	6
26	73	6
10	74	5
37	74	3
71	74	4

Надо найти подграф минимальной стоимости, соединающий все терминальные узлы.

---

---

К задаче…

Пусть имеется группа из n=20 человек, с которыми мы собираемся создать m=5 рабочих групп. (эксперты-политики создающие новые законы, ученые, инженеры и т.п.).

У нас есть 10 дисциплин-предметов (научные дисциплины, технологии, законы, …), а насколько каждый человек хорош в каждой дисциплине, задается индексом компетентности ([0…1]),

и все это формирует матрицу

«матрицей компетентности»

1 0.1 0.3 0.5 0.7 0.8 0.4 0.9 1 1 0 1 0 1 0 0 0.4 0.1 0.1 0.8 0 0 1 0 1 0.6 0.4 1 0 0 1 0.1 0.3 0.5 0.7 0.8 0.4 0.9 1 1 1 0 1 0 1 0 1 0 0 0 1 0 0 1 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 0 1 0.9 1 1 1 1 1 1 0 0 0 0.7 1 0 0.7 0 0 0 1 0 1 0 0 1 0 0 0 0 0 1 1 0 0 1 0 1 0 0 1 0 0 1 0 1 0 1 0 0 0 0 0.7 0 1 0 1 0.3 0 1 0 0 0 1 0 1 0 1 0 0 1 1 0 0.7 0 0 1 0 1 0 0 0 0 0 0 0 0 1 0 1 0 1 1 1 0 0 0 0 0 0 0 0 0.6 0.6 1 0 0 1 0 1 0 0 0 0 0 0.7 0 0 1 0 1 0 0 0 0.7 0 0 0 1 0 0 1

Каждая группа имеет ограничение на минимум и максимум людей

Группа 1 2 3 4 5 Минимум 2 2 5 3 5 Максимум 7 8 7 6 10

• В каждой группе нужно работать над двумя предметами.
• Каждый предмет, должен изучаться по крайней мере в одной группе
• Каждый человек может входить максимум в три группы, но тогда эти у этих групп не должно быть общего предмета.
• Если индекс компетентности кого-то в предмете меньше 0.5, он не может входить в рабочую группу, которая этим занимается.
• Предметы, которые изучает группа, должны быть совместимы («нет конфликта интересов», «техника безопасности» … )

«матрицей совместимости дисциплин»

1 1 0 0 0 1 1 0 1 1
1 1 0 1 1 0 1 0 0 1
0 0 1 0 1 0 1 0 1 1
0 1 0 1 1 1 1 0 1 1
0 0 0 0 1 0 0 0 0 0
1 0 1 0 0 1 0 1 0 1
1 1 0 1 0 1 1 0 1 1
0 0 1 0 0 0 0 1 0 0
1 0 0 1 0 1 1 0 0 1
1 0 1 0 0 0 1 0 0 1 

Цель формирования групп — максимизировать общую компетентность — сумма индивидуальных компетентностей тех, кто в группе, по дисциплинам, изучаемым в группе — и так по всем группам.

Задача зарезервирована: Sanya 17:03, 16 ноября 2023 (UTC)

---

---

К задаче…

Задача зарезервирована: Sfirstov 10:47, 10 декабря 2023 (UTC)

Есть неориентированный граф, список ребер…

в формате «узел узел стоимость»

1 49                 6   
4 5                  1 
4 48                 1 
7 17                 4 
7 33                 5 
9 10                 4 
9 18                 5 
9 21                 1 
9 22                 8 
9 41                 10 
9 45                 9 
10 6                 4 
10 13                1 
10 30                8 
10 48                1 
11 3                 8 
11 15                8 
11 20                5 
12 35                8 
13 34                2 
14 28                7 
15 47                9 
16 38                2 
17 50                7 
18 16                4 
19 12                9 
20 10                4 
20 23                7 
21 8                 7 
21 11                8 
21 12                1 
21 30                9 
22 4                 5 
22 5                 4 
22 25                2 
22 50                5 
24 27                5 
26 39                6 
27 9                 1 
29 7                 4 
29 37                2 
30 12                5 
30 26                10 
30 32                4 
31 5                 2 
31 30                8 
33 36                5 
34 1                 10 
34 46                6 
36 42                8 
37 31                2 
40 19                8 
40 24                1 
41 29                4 
41 42                6 
42 44                9 
43 9                 2 
45 6                 3 
48 2                 8 
50 14                7 
50 39                1 
50 40                5 
50 43                7 

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

---

---

К задаче…

Долгосрочный план выработки электроэнергии учитывает график работы существующих энергоблоков и график установки новых электростанций для удовлетворения спроса на электроэнергию в течение ряда будущих (5) лет при минимально возможных затратах.

Период планирования; 5 лет

Потребность в электроэнергии описывается кривой продолжительности нагрузки (LDC), как показано на рис (цифры на картинке приблизительны, точные будут дальше текстом), по оси ординат — мегаватты, по оси абсцисс — часы.

Площадь под графиком соответствует потребностям производства электроэнергии в мегаватт-часах.

Чтобы модель была простой, например линейной, график аппроксимируется кусочно-постоянной функцией, показанной в виде гистограммы (ступенчатой функции), с

• «Bars=4».
• TD — отсечки по горизонтали

 2920 3650 1280 910

Первый столбец обозначает минимальную нагрузку, столбец «4» — пиковую нагрузку, а два промежуточных — представляют потребность в средней нагрузке.

В любой компании или стране для производства электроэнергии используется несколько различных типов (n=5) технологий, таких как

• паровые турбины
• газовые турбины
• гидроэлектростанции
• дизель-генераторы
• комбинированные генераторы

Эти энергоблоки требуют различных затрат, затрат на установку и переменных затрат, и переменная по времени генерации (что-то ломается, что-то амортизируется, что-то улучшается).

$CE\_\{it\},\; 1\; \backslash leq\; i\; \backslash leq\; n$; — планируемые мощности существующих генерирующих типов по времени.

    15000 18000  20000  21000  21000
    40000 350000 300000 280000 280000 
    50000 400000 400000 400000 300000
    10000 100000 120000 130000 150000
     1000  11000 12000  14000  16000 

$VC\_\{it\}$; Переменная (на мегаватт) годовая стоимость старой установки типа «i»

    4 4 4 4 4
    5 5 5 5 5
    3 3 3 3 3
    3 3 3 3 3
    1 1 1 1 1 

---

Кроме того, в будущем могут быть добавлены дополнительные мощности.

Например, предположим, что модель решила установить новую установку типа «j=1» мощностью 50 МВт в период «1», она будет существовать в системе до истечения технического срока службы этой установки (Это потому, что продолжительность горизонта планирования, рассматриваемого в этой задаче, короче, чем технический срок службы любого нового энергоблока, доступного на рынке).

$FC\_\{jt\}$; Фиксированная годовая стоимость новой установки типа «j»

    100 110 110 120 120
    200 200 200 200 200 
    300 290 290 285 285
    200 190 190 180 180
    50 50 50 50 50  ~

$FC\_\{jt\}$; Фиксированная годовая стоимость новой установки типа «j»

!AF; 80 80 85 85 85

    85 85 85 85 85
    90 90 90 90 90
    90 90 95 95 95
    85 85 90 90 90~

!PD; 6000 6000 6000 6000 6000

    9000 10000 110000 12000 13000
    25000 27000 27000 27000 27000
    50000 58000 58000 58000 57000~

!W; 20 50 10 10 10~

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

Задача планирования состоит в том, чтобы определить

• график работы существующих установок,
• установок нового поколения, которые будут запущены в будущем,
• и график введения новых установок путем минимизации суммы затрат на установку и эксплуатацию за заданное количество

лет, соблюдая при этом технические и финансовые ограничения.

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

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

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

Пока не додумано, надо доработать

Задача зарезервирована: StasFomin 16:33, 27 ноября 2022 (UTC)

---

---

К задаче…

Задача зарезервирована: Sfirstov 22:48, 22 декабря 2023 (UTC)

Дан неориентированный граф G (N, E), надо получить множество с наибольшим числом несвязанных ребер (два ребра соединяются, когда они разделяют узел).

---

---

---

К задаче…

Докажите, что задача MAX-CUT, в форме задачи разрешения («правда, ли, что для графа G есть разрез больше K?») NP-полна.

Задача зарезервирована: Ermakov

---

[ Хронологический вид ]Комментарии

(нет элементов)

Войдите, чтобы комментировать.