Открытые бизнес-задачи

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

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

----

Беру задачу «Optprob/Игра UnblockMe» себе!

Опишем игру «Разблокируй меня» (Kira Games 2021) — это игра-головоломка, представляющая собой поле, состоящее из нескольких столбцов и рядов.

• Блоки располагаются по горизонтально или вертикально;
• Горизонтальный блок может двигаться только вправо и влево;
• Вертикальный блок может двигаться только вверх и вниз.
• Вы должны переместить их таким образом, чтобы освободить путь для красного блока.
• Количество рядов NF=6
• Количество столбцов равно NС=6.

• В этих рядах и столбцах размещается ряд блоков, которые мы будем называть препятствиями, и которые могут быть горизонтальными или вертикальными.
• Горизонтальные блоки размещаются в ряд и могут быть перемещены только в пределах этого ряда (перемещение вправо и влево).
• Вертикальные препятствия могут перемещаться только в пределах столбца, к которому они относятся (перемещение вверх и вниз).

С другой стороны, у нас есть красный блок; это горизонтальный блок, расположенный в определенном ряду (ряд 3 на оригинальной игровой панели) и поэтому перемещается только по горизонтали.

В конце этого ряда на доске есть выход.

Наша задача — убрать красный блок с доски.

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

Мы создадим модель, математически представляющую игру с двумя сценариями:

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

Не готово, нужно дорабатывать

---

---

Беру задачу «Optprob/Размещение городских велостанций» себе!

В городе, поделенном на 10 секторов, будут установлены велосипедные станции.

Каждый сектор, имеет определенное количество потенциальных клиентов:

Sectors	1	2	3	4	5	6	7	8	9	10
C	400	300	200	500	350	450	150	250	380	290

В городе есть 40 возможных мест города для установки станций.

Каждое место

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

Место	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
Максимум велокреплений	30	20	40	45	50	25	15	18	25	25	40	40	45	50	25	15	18	25	25	40	40	45	50	25	15	18	25	25	40	40	45	50	25	15	18	25	25	40	40	30
Сектор	1	2	3	4	5	1	2	3	4	5	6	7	8	9	10	1	2	3	4	5	1	7	8	1	10	9	8	7	7	5	6	4	3	2	1	2	3	4	5	6

Нам известны расстояния между локациями.

верхнетреугольная матрица 40×40

Расстояние	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
1	0	500	600	1000	2000	300	800	100	200	200	400	500	600	100	200	200	400	500	600	100	200	200	400	500	600	100	200	2000	400	500	600	100	200	200	400	500	600	3000	4000	5000
2	0	0	500	600	1000	2000	300	800	200	200	400	500	600	100	200	200	400	500	600	100	200	200	400	500	600	100	200	2000	400	500	600	100	200	200	400	500	600	3000	4000	800
3	0	0	0	500	600	1000	500	600	200	200	400	500	600	100	200	200	400	500	600	100	200	200	400	500	600	100	200	2000	400	500	600	100	200	200	400	500	600	3000	4000	800
4	0	0	0	0	500	600	1000	500	600	1000	2000	300	800	200	200	400	500	600	100	200	200	400	500	600	100	200	200	400	500	600	100	200	2000	400	500	600	100	200	200	400
5	0	0	0	0	0	500	600	1000	500	600	1000	2000	300	800	100	200	200	400	500	600	1000	2000	300	800	100	200	200	400	500	600	1000	2000	300	800	900	100	200	200	400	500
6	0	0	0	0	0	0	500	600	1000	400	500	600	1000	2000	300	800	100	200	200	400	500	600	1000	2000	300	800	800	300	800	100	200	200	400	500	600	1000	2000	300	800	250
7	0	0	0	0	0	0	0	100	200	200	400	500	600	1000	2000	300	800	100	200	200	400	500	600	1000	2000	300	800	300	800	100	200	200	400	500	600	1000	2000	300	800	350
8	0	0	0	0	0	0	0	0	100	200	200	400	500	2000	300	800	300	800	100	200	200	400	500	1000	2000	300	800	300	800	100	200	200	400	500	600	1000	2000	300	800	450
9	0	0	0	0	0	0	0	0	0	100	200	200	400	500	2000	300	800	300	800	1000	2000	300	800	300	800	1000	2000	300	800	300	800	600	100	200	200	100	200	200	400	500
10	0	0	0	0	0	0	0	0	0	0	200	200	400	500	600	1000	2000	300	2000	300	800	300	800	400	1000	2000	300	800	300	800	100	200	200	400	500	100	200	200	400	500
11	0	0	0	0	0	0	0	0	0	0	0	200	200	400	500	600	1000	2000	300	2000	300	800	300	800	1000	2000	300	800	300	100	200	200	400	500	600	1000	2000	300	800	400
12	0	0	0	0	0	0	0	0	0	0	0	0	2000	300	800	200	200	400	500	600	800	300	800	1000	2000	300	800	300	800	100	200	200	400	500	100	200	200	400	500	500
13	0	0	0	0	0	0	0	0	0	0	0	0	0	2000	300	800	200	200	400	500	600	800	300	800	1000	2000	300	800	300	800	100	200	200	400	200	200	400	300	2000	300
14	0	0	0	0	0	0	0	0	0	0	0	0	0	0	2000	300	800	200	200	400	500	600	200	400	500	600	1000	2000	300	400	500	600	1000	2000	200	200	400	300	2000	300
15	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	200	200	400	500	600	1000	2000	300	2000	300	200	200	400	500	600	1000	100	200	200	200	200	400	300	2000	300
16	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	200	200	400	500	600	1000	2000	300	2000	300	1000	2000	300	2000	200	400	500	600	1000	2000	300	800	600	700
17	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	200	200	400	500	600	1000	2000	300	2000	300	1000	2000	300	2000	200	200	400	500	100	200	200	400	500
18	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	200	200	400	500	600	1000	2000	300	2000	300	1000	2000	300	2000	200	400	500	100	200	200	400	500
19	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	200	200	400	500	600	1000	2000	300	2000	300	1000	2000	300	2000	400	500	100	200	200	400	500
20	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	200	200	400	500	600	1000	2000	300	2000	300	100	200	200	400	500	100	200	200	400	500
21	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	200	200	400	500	600	1000	2000	300	2000	300	100	200	200	400	2000	300	1000	2000	300
22	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	200	200	400	500	600	1000	2000	300	2000	300	100	200	200	2000	300	1000	2000	300
23	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	200	200	400	500	600	1000	2000	300	2000	300	1000	2000	300	2000	300	1000	500
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	200	200	400	500	600	1000	2000	300	2000	300	1000	2000	300	2000	300	600
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	200	200	400	500	600	1000	2000	300	2000	300	1000	2000	300	2000	300
26	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	0	200	200	400	500	600	1000	2000	300	2000	300	1000	2000	300	2000
27	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	0	0	200	200	400	500	600	1000	2000	300	1000	2000	300	2000	300
28	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	0	0	0	200	200	400	500	600	1000	2000	300	2000	300	500	600
29	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	0	0	0	0	200	200	400	500	600	1000	2000	300	2000	300	200
30	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	0	0	0	0	0	200	200	400	500	600	1000	2000	300	2000	300
31	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	0	0	0	0	0	0	600	1000	2000	300	2000	300	300	2000	300
32	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	0	0	0	0	0	0	0	600	1000	2000	300	2000	300	500	600
33	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	0	0	0	0	0	0	0	0	600	1000	2000	300	2000	300	400
34	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	0	0	0	0	0	0	0	0	0	600	1000	2000	300	2000	300
35	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	0	0	0	0	0	0	0	0	0	0	600	1000	2000	300	2000
36	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	0	0	0	0	0	0	0	0	0	0	0	250	300	650	650
37	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	0	0	0	0	0	0	0	0	0	0	0	0	200	400	500
38	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	0	0	0	0	0	0	0	0	0	0	0	0	0	600	900
39	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	0	0	0	0	0	0	0	0	0	0	0	0	0	0	800
40	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	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0

Установка станции включает в себя стоимость управляющего компьютера, CO=1200, и стоимость каждого умного крепления (якорной стоянки), каждая из которых оценивается в CB=450.

С другой стороны, необходимо будет также приобрести велосипеды.

Стоимость каждого велосипеда составляет CK=350.

Если будет закуплено более 500 велосипедов, поставщик велосипедов

предлагает скидку в размере Dt=30 за каждый велосипед.

Требования к установке следующие.

• Во всех секторах должно быть несколько станций.
• Расстояние между двумя местами со станцией должно быть не менее 300 м.
• Любое место со станцией должно иметь по крайней мере одно другое место со станцией, расположенной на расстоянии не более 500 м, чтобы избежать длительных поездок при отсутствии велосипедов или свободных стоянок при поездке на станцию.
• В старом секторе города (сектор 1) может быть установлено не более четырех станций.
• Количество приобретенных велосипедов должно составлять не менее 70% от общего количества установленных креплений.
• Если станция устанавливается в каком-либо месте, то количество креплений-якорей должно быть от 8 до его максимальной вместимости.
• У городского отдела планирования есть бюджет в размере P=9000000 на проект установки.

Задача состоит в том, чтобы сбалансировать соотношение между потенциальными клиентами (чтобы было пропорционально…) и установленными в секторе креплениями.

---

---

Беру задачу «Optprob/Назначение инженеров на проекты» себе!

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

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

Каждый проект требует персонала (для проекта 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.

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

---

---

Беру задачу «Optprob/Охрана аптек» себе!

В данном городе имеется 52 аптеки, распределенные по 5 районам (j = 1. . .5).

Аптеки бывают двух типов:

• Обычные (0): Открытие и закрытие в обычные часы, не работают в выходные.
• Аптеки 12 ч (1): Открыты каждый день в году до 22:00.

Аптека	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
Тип	1	1	1	1	1	1	1	1	0	1	1	1	1	1	1	0	1	1	1	1	1	1	1	1	1	1	1	0	1	1	1	0	1	1	1	1	1	1	1	0	1	1	1	1	1	0	1	1	1	1	1	1
Район	1	1	1	1	1	1	1	1	1	1	1	1	1	2	2	2	2	2	2	2	2	2	2	2	3	3	3	3	3	3	3	3	3	3	3	4	4	4	4	4	4	4	5	5	5	5	5	5	5	5	5	5

Есть годовой календарь праздничных дней:

365 дней → holidays

Days
Id	Month	Holidays
1	1	1
2	1	0
3	1	1
4	1	0
5	1	1
6	1	1
7	1	0
8	1	0
9	1	0
10	1	1
11	1	0
12	1	0
13	1	0
14	1	0
15	1	0
16	1	0
17	1	1
18	1	0
19	1	0
20	1	0
21	1	0
22	1	0
23	1	0
24	1	1
25	1	0
26	1	0
27	1	0
28	1	1
29	1	0
30	1	0
31	1	1
32	2	0
33	2	0
34	2	0
35	2	0
36	2	0
37	2	0
38	2	1
39	2	0
40	2	0
41	2	1
42	2	0
43	2	0
44	2	0
45	2	1
46	2	0
47	2	0
48	2	0
49	2	0
50	2	0
51	2	1
52	2	1
53	2	0
54	2	0
55	2	0
56	2	0
57	2	0
58	2	0
59	2	1
60	3	0
61	3	0
62	3	0
63	3	0
64	3	0
65	3	0
66	3	1
67	3	0
68	3	0
69	3	0
70	3	1
71	3	1
72	3	1
73	3	1
74	3	0
75	3	0
76	3	0
77	3	0
78	3	0
79	3	0
80	3	1
81	3	0
82	3	0
83	3	0
84	3	1
85	3	1
86	3	0
87	3	1
88	3	0
89	3	0
90	3	0
91	4	0
92	4	0
93	4	0
94	4	1
95	4	0
96	4	0
97	4	0
98	4	0
99	4	0
100	4	0
101	4	1
102	4	0
103	4	0
104	4	0
105	4	1
106	4	0
107	4	0
108	4	1
109	4	0
110	4	0
111	4	0
112	4	0
113	4	0
114	4	0
115	4	1
116	4	0
117	4	0
118	4	0
119	4	0
120	4	0
121	5	0
122	5	1
123	5	0
124	5	0
125	5	0
126	5	0
127	5	1
128	5	0
129	5	1
130	5	0
131	5	0
132	5	0
133	5	0
134	5	0
135	5	0
136	5	1
137	5	0
138	5	0
139	5	0
140	5	0
141	5	0
142	5	0
143	5	1
144	5	0
145	5	0
146	5	0
147	5	0
148	5	0
149	5	0
150	5	1
151	5	0
152	6	0
153	6	0
154	6	0
155	6	0
156	6	0
157	6	1
158	6	0
159	6	0
160	6	1
161	6	0
162	6	0
163	6	0
164	6	1
165	6	0
166	6	0
167	6	0
168	6	0
169	6	0
170	6	0
171	6	1
172	6	0
173	6	0
174	6	0
175	6	0
176	6	0
177	6	0
178	6	1
179	6	0
180	6	0
181	6	0
182	7	0
183	7	0
184	7	0
185	7	1
186	7	0
187	7	0
188	7	0
189	7	0
190	7	0
191	7	0
192	7	1
193	7	0
194	7	0
195	7	0
196	7	0
197	7	0
198	7	0
199	7	1
200	7	0
201	7	0
202	7	0
203	7	0
204	7	0
205	7	0
206	7	1
207	7	0
208	7	0
209	7	0
210	7	1
211	7	0
212	7	0
213	8	1
214	8	0
215	8	0
216	8	0
217	8	0
218	8	0
219	8	0
220	8	1
221	8	0
222	8	0
223	8	0
224	8	0
225	8	0
226	8	0
227	8	1
228	8	0
229	8	0
230	8	0
231	8	0
232	8	1
233	8	0
234	8	1
235	8	0
236	8	0
237	8	0
238	8	0
239	8	0
240	8	0
241	8	1
242	8	0
243	8	0
244	9	0
245	9	0
246	9	1
247	9	0
248	9	1
249	9	0
250	9	0
251	9	0
252	9	0
253	9	0
254	9	0
255	9	1
256	9	0
257	9	0
258	9	0
259	9	0
260	9	0
261	9	0
262	9	1
263	9	0
264	9	0
265	9	0
266	9	0
267	9	0
268	9	0
269	9	1
270	9	0
271	9	0
272	9	0
273	9	0
274	10	0
275	10	0
276	10	1
277	10	0
278	10	0
279	10	0
280	10	0
281	10	0
282	10	0
283	10	1
284	10	1
285	10	0
286	10	0
287	10	0
288	10	0
289	10	0
290	10	1
291	10	0
292	10	0
293	10	0
294	10	0
295	10	0
296	10	0
297	10	1
298	10	0
299	10	0
300	10	0
301	10	0
302	10	1
303	10	0
304	10	1
305	11	0
306	11	0
307	11	0
308	11	0
309	11	0
310	11	0
311	11	1
312	11	0
313	11	0
314	11	0
315	11	0
316	11	0
317	11	0
318	11	1
319	11	0
320	11	0
321	11	0
322	11	1
323	11	0
324	11	0
325	11	1
326	11	0
327	11	0
328	11	0
329	11	0
330	11	0
331	11	0
332	11	1
333	11	0
334	11	0
335	12	0
336	12	1
337	12	0
338	12	1
339	12	1
340	12	0
341	12	0
342	12	0
343	12	0
344	12	0
345	12	0
346	12	1
347	12	0
348	12	0
349	12	0
350	12	0
351	12	0
352	12	0
353	12	1
354	12	0
355	12	0
356	12	0
357	12	0
358	12	1
359	12	1
360	12	1
361	12	0
362	12	0
363	12	0
364	12	0
365	12	1

Когда аптеки не работают, их надо охранять, наркоманы не дремлют.

Вооруженных охранников аптеки нанять не могут, их выделяет муниципалитет.

Существует два типа охранников:

• Дневной: 9:00-21:00, для выходных-праздничных дней — работают только днем, в выходные.
• Ночной: 21:00-9:00, работают каждый день.

Но к каждой аптеке охранника не приставить, их не хватает на всех, и хотелось бы как-то более-менее справедливо их распределить.

Район	1	2	3	4	5
Дневных охранников	2	2	1	1	2
Ночных охранников	2	1	1	1	1

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

• Обычная аптека не может охраняться более 24 часов подряд.
• Любая аптека не может охраняться два выходных подряд.
• Разница в ежемесячном количестве караулов в каждой обычной аптеке не может быть быть больше трех.
• Разница в общем числе караулов всех охранников в для каждой аптеки не превышает двух единиц.

Округи ревниво следят за «Y_j» — количеством ночных охранников аптек, деленное на количество аптек в его округе «j».

Надо минимизировать разницу между «Y_j», соблюдая вышеуказанные регуляции.

Не готово, проблемы с решением

---

---

Беру задачу «Optprob/Задача Штейнера о минимальном дереве» себе!

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

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

• 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

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

---

---

Беру задачу «Optprob/Назначение предметов на аудитории» себе!

В университете «Синергия» собираемся ежедневноЧтобы упростить размер модели, мы рассматриваем один день преподавания предмета преподавать 150 предметов.

У каждого предмета есть количество учеников.

150 предметов

Subjects
Id	students
1	20
2	10
3	15
4	15
5	25
6	50
7	60
8	60
9	80
10	90
11	20
12	10
13	15
14	15
15	25
16	50
17	60
18	60
19	80
20	90
21	20
22	10
23	15
24	15
25	25
26	50
27	60
28	60
29	80
30	90
31	20
32	10
33	15
34	15
35	25
36	50
37	60
38	60
39	80
40	90
41	20
42	10
43	15
44	15
45	25
46	50
47	60
48	60
49	80
50	90
51	20
52	10
53	15
54	15
55	25
56	50
57	60
58	60
59	80
60	90
61	20
62	10
63	15
64	15
65	25
66	50
67	60
68	60
69	80
70	90
71	20
72	10
73	15
74	15
75	25
76	50
77	60
78	60
79	80
80	90
81	20
82	10
83	15
84	15
85	25
86	50
87	60
88	60
89	80
90	90
91	20
92	10
93	15
94	15
95	25
96	50
97	60
98	60
99	80
100	90
101	20
102	10
103	15
104	15
105	25
106	50
107	60
108	60
109	80
110	90
111	20
112	10
113	15
114	15
115	25
116	50
117	60
118	60
119	80
120	90
121	90
122	20
123	10
124	15
125	15
126	25
127	50
128	60
129	60
130	80
131	90
132	20
133	10
134	15
135	15
136	25
137	50
138	60
139	60
140	80
141	100
142	100
143	80
144	90
145	40
146	100
147	100
148	100
149	100
150	90

Расписание предметов уже составлено (как было удобно лекторам), и чтобы не возится с временами начала-окончания, получим сразу важные для нас данные — какой предмет пересекается по времени с каким (не может быть одновременно).

пересечения преподаваемых предметов

Overlaps
A1	A2
1	2
1	5
1	6
1	7
10	27
10	28
11	28
12	29
12	30
13	31
13	32
13	33
14	34
14	35
14	36
2	5
2	7
3	10
3	11
3	12
3	13
3	14
4	15
4	16
4	17
5	16
5	17
5	18
6	18
6	20
7	21
8	22
8	23
9	24
9	25
9	26

Аудитории мы арендуем в огромном бизнес-центре (неисчерпаемом, «Бесконечный Замок»©), где есть аудитории двух размеров

• Большие, на 100 человек, стоимость $25 в день
• Малые, на 50 человек, стоимость $10 в день.

Стоимость аренды в день — т.е. можно в каждую аудиторию внести все «непересекающиеся» занятия (день тоже «растяжимый»).

В большие точно должны влезть группы студентов по любому предмету, в маленькие — не факт.

Сколько и каких комнат арендовать, и как назначить предметы на эти аудитории, чтобы было подешевле и все студенты поместились?

---

---

Беру задачу «Optprob/Выбор внеклассных мероприятий» себе!

Школа хочет спланировать распределение внеклассных занятий среди учащихся. Предлагаются следующие виды деятельности (8 активностей, 12 групп):

• Гимнастика (две группы)
• Музыка (одна группа)
• Баскетбол (две группы)
• Ремесла (одна группа)
• Рисование (одна группа)
• Английский язык (две группы)
• Французский язык (одна группа)
• Футбол (две группы)

Отображение групп на активности

 A_k = 1 1 2 3 3 4 5 6 6 7 8 8 

Максимум учеников в каждой группе:

 M = 10 10 10 10 10 10 10 10 10 10 12 12

100 учеников уже запросили различные активности, не зная о расписании:

Тут длинная бинарная матрица 100×8

S = 
    1 1 0 0 0 0 0 0 
    1 1 0 0 0 0 1 0 
    1 1 0 0 0 1 1 0 
    0 0 0 0 0 0 1 0 
    0 1 1 0 1 1 0 0 
    1 1 0 1 1 0 0 0 
    1 1 0 1 0 1 0 0 
    1 1 0 0 1 1 0 0 
    0 1 0 0 1 0 0 0 
    1 1 0 0 0 0 1 0 
    1 1 0 0 0 0 0 0 
    1 1 0 0 1 1 1 0 
    1 1 0 0 1 0 0 1 
    1 1 0 0 0 0 0 0 
    0 0 0 0 1 1 0 1 
    1 1 1 0 1 0 0 0 
    1 1 0 1 0 0 0 0 
    1 1 0 0 0 0 1 0 
    1 0 1 0 0 0 1 0 
    1 1 1 0 0 0 0 0 
    1 1 0 0 0 1 0 0 
    1 1 0 0 1 0 0 0 
    1 1 0 0 1 1 0 0 
    0 1 0 0 1 0 0 0 
    0 1 0 0 1 0 1 0 
    1 1 0 0 1 0 0 0 
    0 1 1 0 0 0 0 0 
    1 1 0 0 1 0 1 0 
    0 0 1 0 1 0 0 0 
    1 0 1 0 0 0 0 1 
    1 1 0 1 1 0 0 0 
    1 1 0 1 1 0 0 0 
    1 1 0 0 1 0 0 0 
    0 0 0 0 0 0 0 0 
    0 1 0 0 1 0 0 0 
    1 1 0 0 1 1 0 0 
    1 0 0 0 1 0 0 0 
    1 1 0 0 0 1 0 1 
    0 0 1 0 0 0 1 0 
    1 1 0 0 1 0 0 0 
    1 1 0 0 1 0 0 0 
    1 1 0 0 1 0 0 0 
    1 1 0 0 1 0 0 0 
    1 1 1 0 1 0 0 0 
    1 0 1 0 0 0 0 0 
    0 0 1 0 0 0 1 0 
    1 1 0 0 1 0 0 0 
    1 1 0 0 0 0 0 0 
    1 1 0 1 1 0 0 0 
    0 1 0 0 1 0 0 1 
    0 1 0 0 1 0 0 0 
    1 1 0 1 1 0 0 0 
    1 1 0 0 0 1 0 1 
    0 1 0 0 0 0 1 0 
    1 1 0 0 1 0 1 0 
    1 0 1 0 0 1 1 0
    1 1 0 0 1 0 0 0
    1 1 0 0 1 0 0 0 
    1 1 1 0 0 1 0 0 
    0 0 1 0 0 1 1 0 
    1 0 0 0 1 0 0 0 
    1 1 0 1 1 0 0 0 
    1 1 0 0 1 1 0 0 
    1 1 0 0 1 0 1 0 
    1 1 0 0 1 0 0 0 
    0 0 0 0 1 0 0 0 
    1 1 0 0 1 0 0 0 
    1 1 0 0 0 0 0 0 
    0 1 1 0 0 0 1 0 
    1 0 1 0 1 0 0 0 
    1 1 1 0 0 1 0 0 
    1 1 0 0 1 0 0 0 
    1 1 0 0 1 0 0 1 
    0 1 0 0 1 0 1 0 
    0 1 0 0 1 0 0 0 
    0 1 0 0 1 0 1 0 
    1 1 0 0 1 0 0 0 
    1 1 0 0 1 0 0 0 
    1 1 0 0 1 0 0 0 
    0 0 0 1 0 0 0 0 
    1 1 0 0 1 0 0 0 
    1 1 0 0 1 0 0 0 
    1 1 0 0 0 1 0 0 
    1 1 1 0 0 0 0 0 
    1 1 1 0 1 0 0 0 
    0 1 1 0 0 0 0 0 
    1 1 0 0 1 0 0 0 
    1 1 0 0 0 0 0 1 
    0 1 0 1 1 0 1 0 
    0 0 0 0 0 1 0 0 
    1 0 0 0 1 0 1 0 
    1 1 0 0 1 0 0 0 
    1 1 0 0 0 0 0 0 
    1 1 0 0 1 0 1 0 
    1 1 1 0 1 0 1 0 
    1 1 1 0 1 0 0 0 
    1 1 0 0 1 0 0 0
    1 1 0 0 0 1 0 0 
    1 1 1 0 1 0 1 0 
    0 0 0 0 1 0 0 1 

Занятия проводятся в течение 1 часа

• в понедельник, вторник, среду и четверг.
• в слоты «с 4 до 5 часов», «с 5 до 6» или «с 6 до 7 часов» пополудни — 3 слота в день, всего 12 слотов (h).

Для моделирование конкретное время неважно, т.е. есть 4 дня, и 12 часовых слотов, которые так отражаются на дни:

 D_h = 1 1 1 2 2 2 3 3 3 4 4 4

Расписание занятий уже фиксировано, матрицей 12×12.

P_kh=1 0 0 0 0 0 1 0 0 0 0 0
     0 1 0 0 0 0 0 1 0 0 0 0
     0 0 1 0 0 0 0 0 1 0 0 0
     0 0 0 1 0 0 0 0 0 1 0 0
     0 0 0 0 1 0 0 0 0 0 1 0
     0 0 0 0 0 1 0 0 0 0 0 1
     1 0 0 0 1 0 0 0 0 1 0 0
     0 1 0 0 0 1 0 0 0 0 1 0
     0 0 1 0 0 0 1 0 0 0 0 1
     0 0 1 0 0 0 1 0 0 0 0 0
     0 0 1 0 0 0 1 0 0 1 0 0
     0 0 0 0 1 0 0 0 0 0 1 0

Есть мероприятия с двумя группами. У каждой группы свое расписание и свое максимальное количество студентов.

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

назначены общему числу студентов, принимая во внимание, что:

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

---

---

Беру задачу «Optprob/Назначение задач операторам» себе!

Система имеет N=25 задач и M=10 операторов.

Каждая задача имеет следующие характеристики:

• Приоритет задачи: Значение от 0 до 10.

	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
Приоритет	4	8	9	9	10	2	3	4	7	7	7	5	5	3	2	2	1	1	1	2	1	1	2	3	4

• Время обработки задачи каждым оператором.

	1	2	3	4	5	6	7	8	9	10
1	10	0	23	18	19	12	0	0	32	25
2	0	14	0	0	0	4	0	0	5	0
3	0	7	0	0	15	19	0	0	9	0
4	0	0	13	0	0	13	0	0	0	0
5	23	0	0	34	12	15	0	0	45	13
6	0	0	15	13	45	0	35	0	0	0
7	12	15	0	0	45	0	15	0	22	12
8	0	0	0	35	13	13	19	0	10	0
9	0	0	12	0	25	0	25	0	0	0
10	0	24	0	34	12	0	72	0	0	0
11	0	35	0	0	19	0	19	0	0	21
12	23	24	0	34	0	19	0	19	0	0
13	14	35	0	13	0	0	19	13	0	0
14	18	19	0	12	0	72	0	21	0	23
15	14	35	0	0	19	0	0	25	0	0
16	0	24	0	34	0	12	0	72	0	0
17	0	0	13	0	0	0	0	25	0	25
18	0	24	0	0	0	0	0	72	0	21
19	20	14	35	13	13	19	39	0	25	0
20	0	0	0	0	0	13	0	0	20	21
21	0	22	0	0	35	0	0	0	13	0
22	12	13	0	35	0	0	19	0	19	15
23	11	0	35	0	0	0	39	0	12	13
24	10	0	0	35	13	0	19	0	11	12
25	19	0	0	0	0	0	25	0	25	19

---

Каждый оператор имеет следующие характеристики:

• Совместимость с задачами: Есть задачи, которые они могут выполнять (1), и другие, которые

они не могут (0).

	1	2	3	4	5	6	7	8	9	10
1	1	0	1	1	1	1	0	0	1	1
2	0	1	0	0	0	1	0	0	1	0
3	0	1	0	0	1	1	0	0	1	0
4	0	0	1	0	0	1	0	0	1	0
5	1	0	0	1	1	1	0	0	0	0
6	0	0	1	1	1	0	1	0	1	1
7	1	1	0	0	1	0	1	0	0	0
8	1	0	0	1	1	1	1	0	1	1
9	0	0	1	0	1	0	1	0	1	0
10	0	1	0	1	1	0	1	0	0	0
11	0	1	0	0	1	0	1	0	0	0
12	1	1	0	1	0	1	0	1	0	1
13	1	1	0	1	0	0	1	1	0	0
14	1	1	0	1	0	1	0	1	0	0
15	1	1	0	0	1	0	0	1	0	1
16	0	1	0	1	0	1	0	1	0	0
17	0	0	1	0	0	1	0	1	0	0
18	0	1	0	0	0	0	0	1	0	1
19	1	1	1	1	1	1	1	0	1	0
20	0	0	0	0	0	1	0	0	1	1
21	0	1	0	0	1	0	0	0	1	0
22	1	1	0	1	0	0	1	0	1	1
23	1	0	1	0	0	0	1	0	1	1
24	1	0	0	1	1	0	1	0	1	1
25	1	0	0	0	0	0	1	0	1	1

Каждый оператор имеет:

• Максимальное время работы.
• фиксированную стоимость.

	1	2	3	4	5	6	7	8	9	10
Costs	35	34	38	41	42	50	39	31	25	29
Maximum Times	100	80	70	70	50	40	80	90	50	50

Ограничения:

• Для каждой выполненненной задачи, количество невыполненных задач с более высоким приоритетом, чем она не может превышать 2 (чем выше цифра приоритета — тем больше приоритет).
• У компании есть лимит расходов G=900, который не должен быть превышен.

Цель — максимизировать количество выполненных задач.

• Участник:ScherbakIA/Назначение задач операторам — перепроверить.

---

---

Беру задачу «Optprob/Выбор ребер и узлов в графе» себе!

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

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

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 

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

---

---

Беру задачу «Optprob/Производство и распределение» себе!

Компания имеет два завода, на которых производятся единицы ее продукции.

Каждый завод i имеет

• ежедневную производственную мощность K(i) единиц продукции
• небольшой склад, емкостью FA(i)

Factories
Id	FA	K
1	20,000	5,000
2	25,000	3,500

Предположим, что для производства требуется L=5 рабочих дней в неделю.

---

Еще у компании есть два склада-хаба, откуда произведенная продукция рассылается потребителям. У каждого склада j есть

• Вместимость Aj
• Способность ежедневной отгрузки Ej

Hubs
Id	Aj	Ej
1	10,000	5,000
2	50,000	4,000

---

Есть

n потребителей с их еженедельными запросами этих продуктов

Потребитель
Id	Запросы
1	1,500
2	2,500
3	5,000
4	4,000
5	3,000
6	4,000
7	8,000
8	6,500
9	4,500
10	900
11	500
12	1,600
13	1,700
14	1,900
15	5,200
16	6,700
17	6,900
18	1,500
19	1,600
20	700

---

Между потребителями, фабриками и хабами есть расстояния:

Потребитель-Фабрика

Distance_F_C
Factory	Customer	Distance
1	1	1,500
1	2	4,000
1	3	50
1	4	100
1	5	6,000
1	6	50
1	7	200
1	8	3,000
1	9	100
1	10	80
2	1	934
2	2	1,420
2	3	3,440
2	4	8,000
2	5	150
2	6	120
2	7	1,200
2	8	140
2	9	1,700
2	10	70

Фабрика-Хаб

Distance_F_H
Hub	Distance	Factory
1	150	1
2	400	1
1	3500	2
2	100	2

Хаб-Потребитель

Distance_H_C
Hub	Customer	Distance
1	2	400
1	3	1,500
1	4	1,500
1	5	410
1	6	30
1	7	60
1	8	250
1	9	150
1	10	90
2	1	500
2	2	160
2	3	150
2	4	390
2	5	200
2	6	4,000
2	7	50
2	8	60
2	9	40
2	10	834

хаб-хаб

Distance_H_H
Hub2	Distance	Hub1
2	500	1
1	500	2

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

Надо смоделировать производство и перемещение продуктов между заводом-хабами-потребителями, чтобы минимизировать

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

---

---

Беру задачу «Optprob/Плантации» себе!

Плантатор планирует оптимальные посадки сельхоз культур на своих участках.

Он владеет N=20 участками с площадями (м²)

 800 700 800 1000 5000 10000 4000 25000 40000 10000 5000 10000 4000 25000 40000 5000 10000 4000 25000 40000

Участки могут граничить, и это выражается матрицей

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

Он может посадить 4 культуры (пшеницу, кукурузу, овес и оливки). Есть

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

Культура (i)	Необходимо посадить D_i м²	Выручка на м²	Фиксированные затраты на участок
пшеница	50000	100	40
кукуруза	20000	200	10
овес	30000	150	15
оливки	20000	200	20

И, в зависимости от участка, есть переменные затраты на квадратный метр каждой культуры

10 12 14 13 14 15 17 13 12 10 10 12 11 9 8 7 9 5 6 7 
7 7 7 7 8 8 9 9 10 5 5 5 5 9 8 7 9 5 6 7 
12 11 9 8 7   9 5 6 7 8  12 14 13 14 15   17 13 12 10 10 
6 12 14 13 14  15 17 13 12 10  10 12 11 9 8  7 9 5 6 7  ~

И ограничения хитрой агрикультурной магии:

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

Но

• Пшеницу нельзя совмещать на участке с другими культурами.
• Нельзя растить на одном и даже соседних участках
  • кукурузу и пшеницу
  • курурузу и овес

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

---

---

Беру задачу «Optprob/Онлайн-распродажа» себе!

Овощной магазин продает 45 различных товаров онлайн, включая фрукты, овощи и всякое такое.

25 из них продаются килограммами, KS — запасы этих продуктов на складе:

	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
KS	200	300	500	400	300	500	350	550	350	330	400	400	450	500	500	300	200	200	120	120	200	300	400	500	500

а KV — объем каждого килограмма продукта:

	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
KV	10	25	32	45	40	20	20	20	30	32	33	45	54	10	20	30	10	30	40	10	20	20	30	30	30

Остальные 20 товаров продаются единицами, их запасы на складе US:

	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20
US	300	250	250	500	450	400	150	240	260	450	340	340	500	500	400	400	300	300	200	300

А объем каждого штучного товара — UV:

	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20
UV	10	20	10	15	15	20	30	30	35	45	14	13	12	10	20	20	15	20	20	10

Каждый заказ упаковывается в коробки, разных типов, и надо решить, в какой из них отправлять

• есть четыре модели коробок, каждая с определенным объемом.
• имеется достаточный запас коробок любой модели.

	1	2	3	4
V	200	300	400	500

Мы получили 100 заказов, в каждом из которых заказано определенное количество килограмм каждой позиции весового товара:

матрица 100×25

KP	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	0	1	0	1	0	2	2	0	2	1	2	0	0	2	0	0	0	4	4	3	3	2	1	1
2	0	0	2	1	2	0	0	0	0	3	0	4	4	0	0	0	0	0	0	0	0	0	0	0	0
3	0	2	1	2	0	0	2	0	3	0	4	4	0	0	0	0	0	0	0	0	0	0	0	0	0
4	0	0	2	1	2	0	0	2	0	3	0	4	4	0	0	0	0	0	0	0	0	0	0	0	0
5	0	0	0	0	0	0	0	0	0	0	0	0	2	1	2	0	0	2	0	3	0	4	4	0	0
6	0	0	0	0	0	0	0	0	0	0	0	0	0	0	2	1	2	0	0	2	0	3	0	4	4
7	0	0	0	0	0	1	2	0	0	2	1	0	2	0	0	2	0	0	2	0	0	1	0	1	0
8	0	0	0	1	2	0	0	2	1	0	2	0	0	2	0	0	2	0	0	1	0	1	0	1	0
9	0	0	0	0	0	1	2	1	0	2	0	0	2	0	0	2	0	0	1	0	1	0	1	0	0
10	0	0	0	0	0	0	1	2	1	0	2	0	0	2	0	0	2	0	0	1	0	1	0	1	0
11	0	0	0	0	0	0	1	0	2	0	0	2	0	0	2	0	0	1	0	1	0	1	0	0	0
12	0	1	1	0	2	0	0	2	0	0	2	0	0	1	0	1	0	1	0	0	0	1	0	2	0
13	2	1	0	2	0	0	2	0	0	2	0	0	1	0	1	0	1	0	0	0	1	0	2	0	2
14	0	0	0	0	0	0	2	1	2	2	1	1	2	1	1	2	2	1	1	1	1	1	1	1	1
15	1	0	2	0	0	2	0	0	2	0	0	1	0	1	0	1	0	0	0	1	0	2	0	2	0
16	0	0	0	1	0	2	0	0	2	0	0	2	0	0	1	0	1	0	1	0	0	0	1	0	2
17	0	0	0	1	0	2	0	0	2	0	0	2	0	0	1	0	1	0	1	0	0	0	1	0	2
18	1	0	2	0	0	2	0	0	2	0	0	1	0	1	0	1	0	0	0	1	0	2	0	2	0
19	0	0	0	1	0	2	0	0	2	0	0	2	0	0	1	0	1	0	1	0	0	0	1	0	2
20	0	0	0	1	0	2	0	0	2	0	0	2	0	0	1	0	1	0	1	0	0	0	1	0	2
21	0	0	0	1	0	2	0	0	2	0	0	2	0	0	1	0	1	0	1	0	0	0	1	0	2
22	0	0	0	5	1	0	2	0	0	2	0	0	2	0	0	1	0	1	0	1	0	0	0	1	0
23	0	0	0	1	0	2	0	0	2	0	0	2	0	0	1	0	1	0	1	0	0	0	1	0	2
24	0	0	0	1	0	2	0	0	2	0	0	2	0	0	1	0	1	0	1	0	0	0	1	0	2
25	0	0	0	1	0	2	0	0	2	0	0	2	0	0	1	0	1	0	1	0	0	0	1	0	2
26	1	1	0	2	0	0	2	0	0	2	0	0	1	0	1	0	1	0	0	0	1	0	2	0	2
27	1	0	2	0	0	2	0	0	2	0	0	1	0	1	0	1	0	0	0	1	0	2	0	2	0
28	1	0	2	0	0	2	0	0	2	0	0	1	0	1	0	1	0	0	0	1	0	2	0	2	0
29	1	0	2	0	0	2	0	0	2	0	0	1	0	1	0	1	0	0	0	1	0	2	0	2	0
30	1	0	2	0	0	2	0	0	2	0	0	1	0	1	0	1	0	0	0	1	0	2	0	2	0
31	1	1	0	2	0	0	2	0	0	2	0	0	1	0	1	0	1	0	0	0	1	0	2	0	2
32	0	0	0	1	0	2	0	0	2	0	0	2	0	0	1	0	1	0	1	0	0	0	1	0	2
33	0	0	0	1	0	2	0	0	2	0	0	2	0	0	1	0	1	0	1	0	0	0	1	0	2
34	0	0	0	1	0	2	0	0	2	0	0	2	0	0	1	0	1	0	1	0	0	0	1	0	2
35	0	0	0	1	0	2	0	0	2	0	0	2	0	0	1	0	1	0	1	0	0	0	1	0	2
36	0	0	0	1	0	2	0	0	2	0	0	2	0	0	1	0	1	0	1	0	0	0	1	0	2
37	1	0	2	0	0	2	0	0	2	0	0	1	0	1	0	1	0	0	0	1	0	2	0	2	0
38	1	0	2	0	0	2	0	0	2	0	0	1	0	1	0	1	0	0	0	1	0	2	0	2	0
39	1	0	2	0	0	2	0	0	2	0	0	1	0	1	0	1	0	0	0	1	0	2	0	2	0
40	0	0	0	1	0	2	0	0	2	0	0	2	0	0	1	0	1	0	1	0	0	0	1	0	2
41	0	0	0	1	0	2	0	0	2	0	0	2	0	0	1	0	1	0	1	0	0	0	1	0	2
42	0	0	0	1	0	2	0	0	2	0	0	2	0	0	1	0	1	0	1	0	0	0	1	0	2
43	1	0	2	0	0	2	0	0	2	0	0	1	0	1	0	1	0	0	0	1	0	2	0	2	0
44	1	1	0	2	0	0	2	0	0	2	0	0	1	0	1	0	1	0	0	0	1	0	2	0	2
45	1	1	0	2	0	0	2	0	0	2	0	0	1	0	1	0	1	0	0	0	1	0	2	0	2
46	1	1	0	2	0	0	2	0	0	2	0	0	1	0	1	0	1	0	0	0	1	0	2	0	2
47	1	1	0	2	0	0	2	0	0	2	0	0	1	0	1	0	1	0	0	0	1	0	2	0	2
48	1	1	0	2	0	0	2	0	0	2	0	0	1	0	1	0	1	0	0	0	1	0	2	0	2
49	1	0	2	0	0	2	0	0	2	0	0	1	0	1	0	1	0	0	0	1	0	2	0	2	0
50	1	0	2	0	0	2	0	0	2	0	0	1	0	1	0	1	0	0	0	1	0	2	0	2	0
51	0	0	1	0	2	0	0	2	0	0	2	0	0	1	0	1	0	1	0	0	0	1	0	2	0
52	0	0	0	1	0	2	0	0	2	0	0	2	0	0	1	0	1	0	1	0	0	0	1	0	2
53	0	0	0	1	0	2	0	0	2	0	0	2	0	0	1	0	1	0	1	0	0	0	1	0	2
54	0	0	0	1	0	2	0	0	2	0	0	2	0	0	1	0	1	0	1	0	0	0	1	0	2
55	0	0	0	1	0	2	0	0	2	0	0	2	0	0	1	0	1	0	1	0	0	0	1	0	2
56	0	0	0	1	0	2	0	0	2	0	0	2	0	0	1	0	1	0	1	0	0	0	1	0	2
57	0	0	0	1	0	2	0	0	2	0	0	2	0	0	1	0	1	0	1	0	0	0	1	0	2
58	0	0	0	1	0	2	0	0	2	0	0	2	0	0	1	0	1	0	1	0	0	0	1	0	2
59	0	0	0	1	0	2	0	0	2	0	0	2	0	0	1	0	1	0	1	0	0	0	1	0	2
60	0	0	0	1	0	2	0	0	2	0	0	2	0	0	1	0	1	0	1	0	0	0	1	0	2
61	3	3	1	0	2	0	0	2	0	0	2	0	0	1	0	1	0	1	0	0	0	1	0	2	0
62	1	0	2	0	0	2	0	0	2	0	0	1	0	1	0	1	0	0	0	1	0	2	0	2	0
63	1	0	2	0	0	2	0	0	2	0	0	1	0	1	0	1	0	0	0	1	0	2	0	2	0
64	3	3	1	0	2	0	0	2	0	0	2	0	0	1	0	1	0	1	0	0	0	1	0	2	0
65	3	3	1	0	2	0	0	2	0	0	2	0	0	1	0	1	0	1	0	0	0	1	0	2	0
66	1	0	2	0	0	2	0	0	2	0	0	1	0	1	0	1	0	0	0	1	0	2	0	2	0
67	0	0	0	1	0	2	0	0	2	0	0	2	0	0	1	0	1	0	1	0	0	0	1	0	2
68	0	0	0	1	0	2	0	0	2	0	0	2	0	0	1	0	1	0	1	0	0	0	1	0	2
69	0	0	0	1	0	2	0	0	2	0	0	2	0	0	1	0	1	0	1	0	0	0	1	0	2
70	0	0	1	0	2	0	0	2	0	0	2	0	0	1	0	1	0	1	0	0	0	1	0	2	0
71	0	0	0	1	0	2	0	0	2	0	0	2	0	0	1	0	1	0	1	0	0	0	1	0	2
72	0	0	1	0	2	0	0	2	0	0	2	0	0	1	0	1	0	1	0	0	0	1	0	2	0
73	1	0	2	0	0	2	0	0	2	0	0	1	0	1	0	1	0	0	0	1	0	2	0	2	0
74	0	0	0	0	1	0	2	0	0	2	0	0	2	0	0	1	0	1	0	1	0	0	0	0	0
75	0	0	0	0	1	0	2	0	0	2	0	0	2	0	0	1	0	1	0	1	0	0	0	0	0
76	0	0	0	0	1	0	2	0	0	2	0	0	2	0	0	1	0	1	0	1	0	0	0	0	0
77	1	0	2	0	0	2	0	0	2	0	0	1	0	1	0	1	0	0	0	0	0	0	0	0	0
78	0	1	0	2	0	0	2	0	0	2	0	0	1	0	1	0	1	0	0	0	0	0	0	0	0
79	0	1	0	2	0	0	2	0	0	0	0	0	1	0	1	0	1	0	0	0	0	0	0	0	0
80	0	0	1	0	2	0	0	2	0	0	2	0	0	1	0	1	0	1	0	0	0	0	0	0	0
81	0	0	0	1	0	2	0	0	2	0	0	2	0	0	1	0	1	0	1	0	0	0	0	0	0
82	0	0	0	0	1	0	2	0	0	2	0	0	2	0	0	1	0	1	0	1	0	0	0	0	0
83	0	0	0	0	0	1	0	2	0	0	2	0	0	2	0	0	1	0	1	0	1	0	0	0	0
84	0	0	0	0	1	0	2	0	0	2	0	0	2	0	0	1	0	1	0	1	0	0	0	0	0
85	0	0	0	1	0	2	0	0	2	0	0	2	0	0	1	0	1	0	1	0	0	0	0	0	0
86	0	0	1	0	2	0	0	2	0	0	2	0	0	1	0	1	0	1	0	0	0	0	0	0	0
87	0	1	0	2	0	0	2	0	0	0	0	0	1	0	1	0	1	0	0	0	0	0	0	0	0
88	1	0	2	0	0	2	0	0	2	0	0	1	0	1	0	1	0	0	0	0	0	0	0	0	0
89	0	1	0	2	0	0	2	0	0	2	0	0	1	0	1	0	1	0	0	0	0	0	0	0	0
90	0	0	1	0	2	0	0	2	0	0	2	0	0	1	0	1	0	1	0	0	0	0	0	0	0
91	0	0	0	0	1	0	2	0	0	2	0	0	2	0	0	1	0	1	0	1	0	0	0	0	0
92	0	0	0	0	0	1	0	2	0	0	2	0	0	2	0	0	1	0	1	0	1	0	0	0	0
93	0	0	0	0	0	0	1	0	2	0	0	2	0	0	2	0	0	1	0	1	0	1	0	0	0
94	0	0	0	0	0	0	0	0	2	0	0	2	0	0	2	0	0	1	0	1	0	1	0	0	0
95	0	0	0	0	0	1	0	2	0	0	2	0	0	2	0	0	1	0	1	0	1	0	0	0	0
96	0	0	0	0	1	0	2	0	0	2	0	0	2	0	0	1	0	1	0	1	0	0	0	0	0
97	0	1	0	2	0	0	2	0	0	2	0	0	1	0	1	0	1	0	1	0	0	0	0	0	0
98	0	1	0	2	0	0	2	0	0	2	0	0	1	0	1	0	1	0	0	0	0	0	0	0	0
99	0	1	0	2	0	0	2	0	0	2	0	0	1	0	1	0	1	0	0	0	0	0	0	0	0
100	0	0	1	0	2	0	0	2	0	0	2	0	0	1	0	1	0	1	0	0	0	0	0	0	0

И также, матрица заказов штучных товаров:

матрица 100×20

UP	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20
1	1	0	2	0	0	2	0	0	2	0	0	1	0	1	0	1	0	0	0	0
2	0	1	0	2	0	0	2	0	0	2	0	0	1	0	1	0	1	0	0	0
3	0	0	1	0	2	0	0	2	0	0	2	0	0	1	0	1	0	1	0	0
4	0	0	0	1	0	2	0	0	2	0	0	2	0	0	1	0	1	0	1	0
5	1	0	0	1	1	2	2	1	1	2	1	1	2	1	1	1	0	1	0	1
6	2	1	0	2	0	0	2	2	2	1	2	2	1	2	2	0	1	0	1	0
7	0	2	1	0	2	1	0	0	0	2	0	0	2	0	0	1	0	1	0	0
8	1	0	2	1	0	0	1	1	1	0	1	1	0	1	1	1	1	2	2	1
9	0	1	1	0	0	2	0	0	0	1	0	0	1	0	0	1	1	0	0	1
10	2	0	2	2	2	0	2	2	2	0	2	2	0	2	2	2	1	1	1	1
11	0	2	0	0	2	0	0	0	0	2	0	0	2	0	0	0	2	0	0	2
12	0	0	1	0	2	2	0	0	0	0	0	0	0	0	0	1	0	2	2	0
13	2	0	0	2	1	2	2	2	2	0	2	2	0	2	2	0	1	0	0	1
14	2	2	2	2	2	2	2	2	2	2	2	2	2	2	2	2	0	0	0	0
15	2	2	0	2	0	2	2	2	2	2	2	2	2	2	2	0	2	2	2	2
16	1	2	0	2	1	1	2	2	2	2	2	0	2	2	1	0	0	2	2	0
17	2	1	2	1	0	2	1	2	2	2	0	2	1	0	2	2	0	2	2	0
18	0	2	2	2	2	0	1	1	2	2	0	0	0	1	0	2	2	2	2	2
19	1	0	2	0	0	1	2	2	1	2	2	0	2	0	1	2	2	1	2	2
20	0	1	1	1	0	0	0	0	2	1	2	2	0	2	0	1	2	2	2	2
21	2	0	2	0	2	2	1	1	0	2	2	2	0	0	2	0	1	0	2	2
22	0	2	0	2	2	0	0	0	1	0	1	2	2	0	0	2	0	1	0	0
23	0	0	1	0	2	0	2	2	0	1	2	1	2	2	0	0	2	0	1	1
24	2	0	0	0	2	2	0	0	2	0	0	2	2	2	2	0	0	2	0	0
25	2	2	2	2	2	2	0	0	0	2	1	0	1	2	2	2	0	0	2	2
26	2	2	0	2	2	2	2	2	0	0	0	1	2	1	2	2	2	0	0	0
27	1	2	0	2	1	1	2	2	2	0	2	0	0	1	1	2	2	2	0	0
28	2	1	2	2	2	2	2	2	2	2	0	2	1	2	1	1	2	2	2	2
29	0	1	2	1	0	0	1	2	2	2	0	0	0	0	1	2	1	2	2	2
30	1	2	2	2	1	1	2	2	1	2	2	0	2	1	2	0	2	1	2	2
31	0	0	1	0	0	0	0	1	2	1	2	2	0	0	0	1	0	1	1	1
32	2	1	2	1	2	2	1	2	0	2	2	2	0	2	1	0	1	2	1	2
33	0	0	0	0	0	0	0	0	1	0	2	2	2	0	0	2	0	0	1	0
34	0	2	1	2	0	0	2	1	0	1	1	1	2	0	2	0	2	1	2	1
35	2	0	0	0	2	2	0	0	2	0	2	2	2	2	0	0	0	0	0	0
36	2	0	2	0	2	2	0	2	0	2	0	0	1	2	0	2	0	2	1	2
37	2	2	0	2	2	2	2	0	0	0	1	1	2	2	2	2	2	0	0	0
38	1	2	0	2	1	2	2	0	2	0	0	0	0	1	2	2	2	0	2	0
39	2	2	2	2	2	1	2	2	2	2	2	2	1	2	2	1	2	2	0	2
40	0	1	2	2	0	2	1	2	2	2	0	0	0	0	1	1	1	2	0	2
41	1	2	2	1	1	0	2	2	1	2	0	0	2	1	2	1	2	2	2	2
42	0	0	0	2	0	1	0	1	2	2	2	2	0	0	0	1	0	1	2	1
43	2	1	2	2	2	0	1	2	0	2	2	2	0	2	1	2	1	2	2	2
44	0	0	2	2	0	2	0	0	1	2	2	2	2	0	0	0	0	0	2	0
45	0	2	2	1	0	0	2	1	0	3	3	2	2	0	2	1	2	1	0	1
46	2	0	3	1	2	0	0	0	2	3	3	2	2	2	0	0	0	0	0	0
47	2	0	1	1	2	2	0	2	0	3	2	3	3	2	0	2	0	2	2	2
48	2	2	1	2	2	2	2	0	0	3	2	3	3	2	2	0	2	0	2	0
49	1	2	1	0	2	2	2	0	2	3	2	3	3	1	2	0	2	0	2	0
50	2	2	1	1	1	3	2	2	2	2	3	3	2	2	2	2	2	2	2	2
51	0	1	2	0	2	1	2	2	2	2	2	2	2	1	2	2	1	2	1	2
52	1	1	0	2	1	2	1	2	2	1	2	1	1	2	1	2	2	2	2	2
53	0	2	1	0	2	1	2	2	2	2	1	2	2	0	2	2	1	1	0	1
54	2	0	0	0	0	2	0	1	2	0	2	0	0	1	0	1	2	2	1	2
55	0	1	2	2	1	0	1	2	1	1	0	1	1	0	1	2	0	1	0	1
56	0	0	0	2	0	1	0	0	2	0	1	0	0	2	0	0	1	2	2	2
57	2	2	0	2	2	0	2	1	0	2	0	2	2	0	2	1	0	0	0	0
58	2	0	2	2	0	2	0	0	1	0	2	0	0	0	0	0	2	1	0	1
59	2	0	2	1	0	0	0	2	0	0	0	0	0	2	0	2	0	0	2	0
60	2	2	2	2	2	0	2	0	2	2	0	2	2	2	2	0	0	2	2	2
61	1	2	1	0	2	2	2	0	0	2	2	2	2	2	2	0	2	0	2	0
62	2	2	2	1	2	2	2	2	0	2	2	2	2	3	2	2	2	0	3	0
63	0	1	1	0	3	2	3	2	2	3	2	3	3	0	3	2	2	2	1	2
64	1	2	2	2	2	3	0	2	2	0	3	0	0	2	0	2	3	2	0	2
65	0	1	0	0	2	0	2	3	2	2	2	2	2	2	2	3	0	2	2	2
66	2	2	1	0	0	2	2	0	3	2	0	2	2	2	2	0	2	3	2	3
67	0	0	0	2	2	2	2	2	0	2	2	2	2	3	2	2	2	0	2	0
68	0	1	2	2	2	2	3	2	2	3	2	3	3	2	3	2	2	2	3	2
69	2	0	0	2	2	3	2	2	2	2	2	2	2	1	2	2	3	2	2	2
70	2	2	0	3	3	2	1	3	2	1	3	1	1	2	1	3	2	2	1	2
71	2	0	2	0	2	1	2	2	3	2	2	2	2	0	2	2	1	3	2	3
72	3	0	2	2	1	2	0	1	2	0	1	0	0	1	0	1	2	2	0	2
73	2	2	2	2	2	0	1	2	1	1	2	1	1	0	1	2	0	1	1	1
74	1	2	3	2	0	1	0	0	2	0	0	0	0	2	0	0	1	2	0	2
75	2	2	1	3	1	0	2	1	0	2	1	2	2	0	2	1	0	0	2	0
76	0	3	0	2	0	2	0	0	1	0	0	0	0	0	0	0	2	1	0	1
77	1	2	2	1	2	0	0	2	0	0	2	0	0	2	0	2	0	0	0	0
78	0	1	2	2	0	0	2	0	2	2	0	2	2	2	2	0	0	2	2	2
79	2	0	2	0	0	2	2	0	0	2	0	2	2	2	2	0	2	0	2	0
80	0	2	3	1	2	2	2	2	0	2	2	2	2	3	2	2	2	0	2	0
81	0	2	2	0	2	2	3	2	2	3	2	3	3	1	3	2	2	2	3	2
82	2	2	1	2	2	3	1	2	2	1	2	1	1	1	1	2	3	2	1	2
83	2	3	2	0	3	1	1	3	2	1	3	1	1	3	1	3	1	2	1	2
84	2	2	0	0	1	1	1	1	3	1	1	1	1	1	1	1	1	3	1	3
85	3	1	1	2	1	2	2	1	1	2	1	2	2	1	3	1	0	1	0	1
86	2	2	0	2	2	0	2	2	1	2	2	2	3	2	1	1	1	1	2	1
87	1	0	2	2	2	1	2	0	2	2	0	3	1	0	1	1	0	1	0	1
88	2	1	0	3	3	0	3	1	3	3	1	1	1	1	2	1	2	1	0	0
89	0	0	0	1	1	2	1	0	1	1	0	1	2	0	0	0	0	0	2	2
90	1	2	2	1	1	0	1	2	1	1	2	0	0	2	0	2	0	2	2	2
91	0	0	2	2	0	0	0	0	0	0	0	0	0	0	2	0	2	0	2	2
92	2	0	2	2	0	2	2	0	0	2	0	2	2	0	2	0	2	0	3	3
93	0	2	3	2	2	2	0	2	2	0	2	2	2	2	2	2	2	2	1	1
94	0	2	1	3	2	2	0	2	2	0	2	2	2	2	3	2	3	2	1	1
95	2	2	1	1	2	3	2	2	2	2	2	3	3	2	1	2	1	2	1	0
96	2	3	3	1	3	1	2	3	3	2	3	1	1	3	1	3	1	3	0	0
97	2	1	2	3	1	1	2	1	1	2	1	1	1	1	0	1	0	1	0	0
98	3	1	1	2	1	2	3	1	1	3	1	2	2	1	0	1	0	0	0	0
99	1	0	1	0	2	0	1	2	0	1	2	0	0	1	0	0	0	1	0	0
100	1	1	0	2	0	0	1	0	0	1	0	0	1	0	1	0	1	0	0	0

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

Целевая функция — минимизация суммы объема отправленных коробок плюс штраф в десятикратном размере за объем оставшихся на складе товаров.

---

---

Беру задачу «Optprob/Независимое множество ребер» себе!

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

---

---

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

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

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