Решенные бизнес задачи

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

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

----

Задача «Optprob/Транспортировка нефти»

Проверено: StasFomin 06:12, 13 ноября 2024 (UTC)

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

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

Определите время, необходимое для транспортировки 60000 литров с нефтеперерабатывающего завода в центр хранения, если каждый

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

Если мощность дуги (2,5) увеличить с 1 до 4, на сколько сократится полученное время?

📺 видео 📺

• Код решения в проекте «adv2022-course-pyomo-business-optimization» в «optprob/Транспортировка_нефти.ipynb»

---

---

Задача «Optprob/Планирование производства рождественских игрушек»

Проверено: StasFomin 12:07, 26 декабря 2023 (UTC)

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

• Создание мощностей для производства этих моделей обойдется в €25000, €35000 и €300000
• Прибыль на единицу продукции составит €10, €15 и €13 соответственно.
• У компании есть три завода для производства этих моделей, но, чтобы избежать затрат, только один из них будет производить игрушки, выбор зависит от максимизации прибыли.

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

Завод      Игрушка1      Игрушка2    Игрушка3

Завод1 5 4 6 Завод2 4 2 2 Завод3 3 3 3

• Мощность завода в человеко-часах на заводах составляют 500, 600 и 630 часов в день соответственно
• Руководство решило разработать хотя бы одну из трех игрушек.
• На само производство останется 30 дней.

Надо максимизировать общую прибыль.

• Код решения в проекте «adv2022-course-pyomo-business-optimization» в «optprob/Планирование_производства_рождественских_игрушек.ipynb»

📺 видео 📺

---

---

Задача «Optprob/Распределение МРТ по больницам»

Проверено: 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 км (иначе совсем жестоко).

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

📺 видео 📺

• Код решения в проекте «adv2022-course-pyomo-business-optimization» в «optprob/Распределение_МРТ_по_больницам.ipynb»

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

---

---

Задача «Optprob/Управление скидками»

Проверено: StasFomin 01:14, 28 ноября 2022 (UTC)

Мы должны купить N=1000 единиц товара. У нас есть три поставщика (A, B и C).

• Первый из них предлагает нам пропорциональную скидку: Три цены (pA1 $/единица, pA2 $/единица, pA3 $/единица), которые будут применяться ко всем единицам в зависимости от количества единиц, которые мы запрашиваем (pA1 > pA2 > pA3), у нас pA1=10, pA2=9, pA3=8. Рассмотрим, соответственно, три интервала: (0, A1], (A1, A2] и (A2, N], (A1=200, A2=5000).

• Второй предлагает нам инкрементную скидку: Три цены (pB1 $/единица, pB2 $/единица, pB3 $/единица, у нас pB1=9.5, pB2=9, PB3=8.5), которые применяются к единицам каждого интервала (pB1 > pB2 > pB3). Интервалы (0, B1], (B1, B2] и (B2, N], соответственно (B1=300, B2=700).

• Третий из них предлагает нам фиксированную цену pC $/единицу (pC=9) и фиксированные скидки: скидка в размере D1$ за заказ свыше C1 единиц и вторую скидку, которая добавляется к первой в размере D2$ при заказе свыше C2 единиц (C1=500, C2=800, D1=300, D2=300).

У кого сколько покупать, чтобы минимизировать стоимость покупки?

📺 видео 📺

• Код решения в проекте «adv2022-course-pyomo-business-optimization» в «optprob/Управление_скидками.ipynb»

StasFomin 01:14, 28 ноября 2022 (UTC): Надо сделать модификацию задачи (генератор?), тут получились скучные цифры.

---

---

Задача «Optprob/Иголка в стоге сена»

Проверено: StasFomin 16:23, 23 декабря 2022 (UTC)

Создатель «теории ограничений» и пропагандист математической оптимизации в бизнес-задачах Элияху Моше Голдратт, часто прибегал к написанию «производственных бизнес-романов» для иллюстрации своих идей.

Очень рекомендую, для культуры, прочитать хотя бы первый и самый известный роман — «Цель»

В одном из них, в «Синдроме Стога Сена» на 40 страницах текста без малейшей романтики и лирики рассматривается в цифрах оптимизация некоторого модельного производства, и где «на пальцах» читателя убеждают, что для достижения максимальной прибыли нужно жертвовать локальными оптимумами, и принимать решения, часто интуитивно непонятные. Эту книгу десятилетия любят бизнес-тренеры, и консультанты, перерабатывают ее в тренинги…, см. например, тренинг Сергея Мартыненко или вот (→→→), свежий пост из бизнесового телеграмм-чата

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

В докладе Стас Фомина была приведена модель на MathML и решение на GLPK (увы, вроде остались только слайды и видео), надо повторить это на Pyomo. Может где-то ее уже на Pyomo и решили (не проверял).

Всю книгу там перечитывать не обязательно, но если прочитаете — это будет совсем незря!

• Участник:Larin.dv/Иголка в стоге сена
• Код решения в проекте «adv2022-course-pyomo-business-optimization» в «optprob/Иголка_в_стоге_сена.ipynb»

📺 видео 📺

---

---

Задача «Optprob/Планирование задач с приоритетом и временами перенастройки»

Проверено: StasFomin 12:41, 23 декабря 2022 (UTC)

Пусть имеется набор из n=10 производственных задач.

Каждая задача имеет время выполнения.

1	2	3	4	5	6	7	8	9	10
12	14	25	10	13	18	7	9	11	18

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

Кроме того:

• Между задачами существуют условные прецеденты: Задача i должна быть обработана после j, если задача t была обработана до i. Это собрано в бинарном атрибуте A_ijt.

I	j	t
1	2	3
4	6	3
3	10	8
8	7	1
10	5	8

• Между задачами нужна перенастройка станка. Если задача i находится на позиции k, а задача j — на позиции k + 1, добавляется дополнительное машинное время, s_ij.

матрица 10×10

	1	2	3	4	5	6	7	8	9	10
1	0	1	2	3	4	5	6	7	8	9
2	1	0	2	2	2	2	1	1	0	9
3	1	1	0	2	3	4	5	6	7	8
4	2	2	3	0	1	2	2	13	12	11
5	4	1	10	20	0	2	1	1	2	2
6	4	15	6	3	0	0	1	10	1	20
7	1	2	2	2	0	0	0	1	1	0
8	1	3	3	3	0	0	0	0	1	2
9	9	1	1	1	4	3	3	4	0	3
10	8	2	4	4	4	4	4	4	7	0

Цель задачи — минимизировать общее время производства.

• Код решения в проекте «adv2022-course-pyomo-business-optimization» в «optprob/Планирование_задач_с_приоритетом_и_временами_перенастройки.ipynb»

📺 видео 📺

• Участник:PankratovViktor/Планирование задач с приоритетом и временами перенастройки

---

---

Задача «Optprob/Группировка людей»

Проверено: StasFomin 22:40, 19 февраля 2023 (UTC)

Пусть имеется группа из n=50 человек, с которыми будет создано m=10 рабочих групп.

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

1	2	3	4	5	6	7	8	9	10
5	4	4	3	6	4	5	7	6	6

Некоторые люди знают друг друга.

70 связей

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

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

• Код решения в проекте «adv2022-course-pyomo-business-optimization» в «optprob/Группировка_людей.ipynb»

📺 видео 📺

• Blog:Advanced_Algorithms/Разбор_оптимизационной_задачи_«Группировка_людей»

---

---

Задача «Optprob/Размещение административных учреждений»

Проверено: 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

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

📺 видео 📺

• Код решения в проекте «adv2022-course-pyomo-business-optimization» в «optprob/Размещение_административных_учреждений.ipynb»

---

---

Задача «Optprob/Домостроительство»

Проверено: StasFomin 02:29, 28 ноября 2023 (UTC)

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

Площадь блока составляет 25000 м2 (500м в длину на 50м в ширину).

Он собирается построить дома в два ряда (длина каждого ряда 500 м, ширина 20 м) — ну такой классический американский минигородок с одной улицей (симпсоны, саус-парк).

В середине есть участок шириной 10 м для улицы-проезда.

Застройщик должен решить сколько домов построить в каждом ряду в рамках трех моделей:

Элитка

• Отдельные элитные такие дома на участках площадью 400м2 (20м в длину 20м в ширину).

Таунхаус

Совмещенные блоки из двух домов на участках площадью 700м2 (35м в длину 20м в ширину).

Эконом-пенал

Небольшие, но раздельные эконом-домики на участках площадью 200м2 (10м в длину 20м в ширину) для каждого дома.

Стоимость строительства каждого дома равна C_i (i = 1, 2, 3).

 190000 150000 100000

Цена продажи для каждого типа дома составляет B_i.

 250000 200000 120000

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

  4 4 6

• если количество таунхаус-блоков больше, чем количество элитных домов, это влечет за собой дополнительные расходы в размере CA=15000 на каждый дополнительный двухдомный блок.
• «Эконом-пенал» дома могут располагаться только в одном ряду (из двух, требования архитектора).
• Установленный потолок инвестиций составляет TI=3000000 долларов.
• Инвестиционные деньги имеют стоимость CI=3%.
• Застройщик не обязан строить весь ряд — можно строить дома в упор друг-другу, или с промежутками, или вовсе не до конца.

Предложите модель, которая максимизирует выгоду.

• Код решения в проекте «adv2022-course-pyomo-business-optimization» в «optprob/Домостроительство.ipynb»
• 📺 видео 📺

---

---

Задача «Optprob/Назначение студентов в группы»

Проверено: StasFomin 00:29, 23 декабря 2023 (UTC)

После получения оценок первой оценки ВУЗ рассматривает вопрос об улучшении успеваемости своих учеников по математике.

• Оценка каждого ученика по этому предмету известна, от 0 до 10.
• Закон о персданных конечно запрещает узнать (нам, оптимизаторам) у кого какая оценка, даже под «анонимным номером», но известно, что после разбития на категории, у нас такое грубое распределение студентов:
  • v=1, «неудовлетворительно [0-5]» → 24
  • v=2, «хорошо» [5,7], → 58
  • v=3, «отлично» [7,9], → 11
  • v=4, «блестяще» [9,10] → 7

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

• Для этого, создается 15 учебных групп.
• В каждой группе может быть не более 10 учеников.
• В каждой группе по возможности нужно поместить ученика с «блестящей» оценкой.
• Если в группе нет «блестящих», в ней должно быть по крайней мере, не меньше отличников, чем и в любой группе с «блестящими».
• У группы есть «уровень» $\backslash forall\; j:\; y\_j\; =\; \backslash sum\_\{i=1\}^\{4\}\; v\_i\; x\_\{ij\}$, где x_{ij} — число студентов «уровня i» назначенных в группу «j» — мы, оптимизаторы, работаем только с «уровнями» и «группами», не с отдельными студентами.

Цель состоит в том, чтобы сбалансировать уровень оценок групп, чтобы разница минимального и максимального «уровня» у групп было минимальным.

📺 видео 📺

• Код решения в проекте «adv2022-course-pyomo-business-optimization» в «optprob/Назначение_студентов_в_группы.ipynb»
• Blog:Advanced_Algorithms/Разбор_задачи_«Назначение_студентов_в_группы»

---

---

Задача «Optprob/Управление загрязняющими продуктами»

Проверено: StasFomin 10:47, 23 декабря 2023 (UTC)

Компания рассматривает возможность производства трех своих продуктов P1, P2 и P3 в одном из мест U1, U2 и U3.

При производстве каждого продукта образуется объем загрязнения в объеме 0,5, 2 и 1 см3, соответственно, на единицу произведенной продукции, независимо от местоположения.

В таблице показаны для каждого из мест:

• удельный доход ($) от каждого продукта,
• суточная производственная мощность (единиц).
• дневная производственная мощность (единиц),
• максимальные объемы загрязнения (см3),
• штраф за превышение объема загрязнения ($/см3).

Компания, осознавая экологические проблемы, предлагает цели с порядком приоритетов:

• Приоритет 1. Максимизировать ежедневный доход.
• Приоритет 2. Не превышать максимальный уровень загрязнения местности.
• Приоритет 3. Компания не хочет тратить более $9000 в день из-за превышения уровня загрязнения.

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

• Код решения в проекте «adv2022-course-pyomo-business-optimization» в «optprob/Управление_загрязняющими_продуктами.ipynb»

📺 видео 📺

• Blog:Advanced_Algorithms/Разбор_задачи_«Управление_загрязняющими_продуктами»

---

---

Задача «Optprob/Производство подразделяемых задач»

Проверено: StasFomin 00:21, 23 декабря 2022 (UTC)

Дано множество из n=15 производственных задач, каждая из которых имеет…

заданное время выполнения

Tasks
Id	Time
1	12
2	4
3	11
4	3
5	23
6	12
7	5
8	3
9	23
10	34
11	23
12	23
13	21
14	56
15	45

Имеется набор 5 машин для обработки заданий.

• Все задачи должны быть обработаны.
• Задание считается обработанной, если сумма времени обработки на каждой машине равна времени выполнения задания.
• Задание может быть частично обработано не более чем на трех машинах, но всегда одна машина должна обрабатывать не менее одной трети времени выполнения задания.
• Каждое задание, которое обрабатывается на любой машине, приводит к тому, что машина затрачивает время на установку TT=100 плюс время, которое машина обрабатывает задание.

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

Для простоты: Нет необходимости учитывать перекрытие: то есть, нет необходимости

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

📺 видео 📺

• Код решения в проекте «adv2022-course-pyomo-business-optimization» в «optprob/Производство_подразделяемых_задач.ipynb»
• Участник:PankratovViktor/Производство подразделяемых задач

---

---

Задача «Optprob/Хранение артефактов на складе»

Проверено: StasFomin 08:10, 22 декабря 2022 (UTC)

Представим склад на котором надо хранить какие-то артефакты.

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

m

15

Максимальный вес для места:

1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
15	25	25	30	30	40	40	30	30	25	25	15	15	10	10

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

матрица 15×15

	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
1	0	10	2	1	1.5	2.5	3.5	4	5	5.5	6	6.5	7	7.7	7
2	0	0	1.5	2	1.5	3	4	5	2	3	2	3	4	5	5
3	0	0	0	1.5	4	1.5	1.5	4	2	2	2	2	5	3	2
4	0	0	0	0	2	4	4	1.5	4	2	2	1	1	1	1
5	0	0	0	0	0	3	4	2	1	2	2	2	2	3	2.5
6	0	0	0	0	0	0	3.5	2.5	1	2	1	4.6	1	2.7	4
7	0	0	0	0	0	0	0	1	2	1	2.6	1	2.7	1.5	1.5
8	0	0	0	0	0	0	0	0	1	1	3	4	6	3.5	2.5
9	0	0	0	0	0	0	0	0	0	1	2	1	2.6	1	2.7
10	0	0	0	0	0	0	0	0	0	0	1	2	1	1.5	2.5
11	0	0	0	0	0	0	0	0	0	0	0	1	3.4	3.5	2.7
12	0	0	0	0	0	0	0	0	0	0	0	0	4	2.5	1
13	0	0	0	0	0	0	0	0	0	0	0	0	0	2.5	2
14	0	0	0	0	0	0	0	0	0	0	0	0	0	0	3
15	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0

---

Есть 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
12	14	15	16	4	7	5	9	12	15	14	13	12	17	3	5	7	6	3	4	5	5	3	2	2

Некоторые артефакты совместимы — и их можно размещать в одном месте хранения, если суммарный вес не превышен. Некоторые нельзя — таблица совместимости (1=совместимы), представлена ниже.

матрица совместимости 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	1	1	0	1	0	1	1	1	1	0	0	1	0	0	0	1	0	0	1	0	0	0	0	1	1
2	0	1	1	0	1	0	0	1	1	0	0	0	0	0	0	0	0	1	1	0	0	0	1	0	0
3	0	0	1	0	0	1	1	0	1	1	1	0	1	0	0	1	0	0	0	0	0	0	0	1	0
4	0	0	0	1	0	0	0	1	0	1	1	0	0	0	0	0	0	0	0	0	0	1	1	0	0
5	0	0	0	0	1	1	0	0	1	0	1	0	0	0	1	0	1	0	1	0	0	0	0	0	1
6	0	0	0	0	0	1	0	1	0	0	1	0	1	0	0	0	0	0	0	0	1	0	1	0	0
7	0	0	0	0	0	0	1	0	0	0	0	0	0	1	1	1	0	0	0	0	0	0	0	0	0
8	0	0	0	0	0	0	0	1	0	1	0	1	1	0	0	0	0	0	0	0	0	0	0	1	1
9	0	0	0	0	0	0	0	0	1	1	1	1	0	1	0	0	1	0	1	0	1	0	0	0	0
10	0	0	0	0	0	0	0	0	0	1	0	0	1	1	0	1	0	0	0	0	0	0	0	0	0
11	0	0	0	0	0	0	0	0	0	0	1	1	0	0	0	0	0	0	0	0	1	0	0	0	1
12	0	0	0	0	0	0	0	0	0	0	0	1	0	0	1	0	1	0	1	1	0	0	0	1	0
13	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
14	0	0	0	0	0	0	0	0	0	0	0	0	0	1	0	0	0	0	0	0	0	0	1	0	1
15	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	0	1	0	0	1	0	0	0	0	0
16	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	0	0	0	0	1	0	0	0	0
17	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	0	0	0	0	0	1	1	0
18	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
19	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
20	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	0	0	1	0	0
21	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	0	0	1	0
22	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	0	0	0
23	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	0	0
24	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	0
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	1

Не факт, что вообще удастся разместить все артефакты (ну тогда лишние уедут на другие «Хранилища»), но цель — разместить максимум артефактов (в штуках), т.е. каждому артефакту назначить место, или отказать в хранении.

📺 видео 📺

• Код решения в проекте «adv2022-course-pyomo-business-optimization» в «optprob/Хранение_артефактов_на_складе.ipynb»

• Участник:Robohant/Хранение артефактов на складе

---

---

Задача «Optprob/Аренда склада»

Проверено: StasFomin 23:51, 27 ноября 2022 (UTC)

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

В промышленной зоне, где он собирается открыть бизнес, есть шесть складов («i= 1…6»), доступных для аренды.

Бизнесмен начинает бизнес с 50 тонн цемента и пяти автомобилей для транспортировки.

Склады, которые он арендует, должны вмещать как цемент, так и

транспортные средства.

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

Номер склада	1	2	3	4	5	6
Стоимость аренды	35	33	26	23	30	29
Вместимость машин	2	2	2	1	3	3
Вместимость цемента	20	18	13	19	22	22

Цель состоит в том, чтобы минимизировать общую стоимость аренды на этот год.

📺 видео 📺

• Код решения в проекте «adv2022-course-pyomo-business-optimization» в «optprob/Аренда_склада.ipynb»

---

---

Задача «Optprob/Распределение рабочих по производственным центрам»

Проверено: StasFomin 01:43, 28 ноября 2022 (UTC)

• Есть L городов
• Есть n рабочих.
  • Каждый работник живет в определенном городе.
• Есть m рабочих центров, каждый из которых
  • расположен в определенном городе.
  • имеет минимальную и максимальную потребность в работниках.

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

L	25
m	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
n	4	8	16	13	10	12	11	10	7	7	7	5	5	3	2	2	1	1	1	2	1	1	2	3	4

Расстояние между 25 городами (расстояния симметричные, представлены верхней треугольной матрицей).

матрица 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	35	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	35	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	15	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	26	27	28	29	30	31	32	33	34	35	36	37	38	39	40
Минимальная потребность	2	3	2	3	4	2	3	4	2	3	4	2	3	4	2	2	2	2	2	3	4	2	2	2	2	3	4	2	2	2	2	3	4	2	2	2	2	4	5	5
Максимальная потребность	5	5	5	5	7	4	4	6	4	5	7	4	4	5	5	4	4	4	4	5	6	4	4	4	4	4	6	4	4	4	4	5	7	5	4	4	4	6	7	7
Город для рабочего центра	1	1	2	2	2	3	4	5	6	7	8	8	9	9	10	11	12	13	14	15	16	17	17	17	18	18	19	19	20	20	20	21	22	22	23	23	24	24	25	25

📺 видео 📺

• Код решения в проекте «adv2022-course-pyomo-business-optimization» в «optprob/Распределение_рабочих_по_производственным_центрам.ipynb»

---

---

Задача «Optprob/Покупка станков»

Проверено: StasFomin 22:45, 19 февраля 2023 (UTC)

Задан набор из n=40 производственных задач, каждая из которых имеет заданное время обработки.

Стоимость станков, которые выполняют задачи, составляет C=400 за каждый.

• каждое задание обрабатывается на одном станке (не параллелится)
• и станок не может обрабатывать более пяти задач (M) за раз, в день, без отдыха.

Надо:

• чтобы все задачи обрабатывались менее чем за TT=8 ч (машины начинают работать одновременно, и нет задач продолжительностью более 8 ч).
• минимальную стоимость покупки станков.

• Код решения в проекте «adv2022-course-pyomo-business-optimization» в «optprob/Покупка_станков.ipynb»
• Blog:Advanced_Algorithms/Хорошие_практики_компактных_Pyomo-формулировок_на_примере_решения_«Задачи_о_станках»
• Участник:Cherniavskii/BusinessProblems/Покупка_станков

---

---

Задача «Optprob/Поделить поровну»

Проверено: StasFomin 12:29, 5 декабря 2022 (UTC)

Задан набор из n элементов, каждый из которых целое положительное число.

S = {7 8 2 5 7 1 5 5 9 9 4 3 2 2 1 3 6 3 11 12}

Как поделить их на две максимально равные части?

• Код решения в проекте «adv2022-course-pyomo-business-optimization» в «optprob/Поделить_поровну.ipynb»

📺 видео 📺

• Blog:Advanced_Algorithms/Задача_о_двух_кучах_камней_и_примеры_использования_различных_ЦЛП-солверов

---

---

Задача «Optprob/Капитальные инвестиции»

Проверено: StasFomin 08:18, 1 декабря 2022 (UTC)

У нас есть 2200 долларов, которые можно инвестировать в течение следующих 5 лет.

В начале каждого года мы можем инвестировать часть денег в депозиты сроком на 1 или 2 года.

По годичным депозитам выплачивается 5% годовых, в то время как по 2-летним депозитам выплачивается 11% в конце 2-х лет.

Кроме того, в начале второго года можно вложить деньги в 3-летние облигации компании А, общая доходность которых составляет 17%.

Куда и сколько инвестировать? Добейтесь того, в конце пятилетнего периода капитал был как можно больше.

• Код решения в проекте «adv2022-course-pyomo-business-optimization» в «optprob/Капитальные инвестиции.ipynb»

📺 видео 📺

• Blog:Advanced_Algorithms/2022-11-27_Разбор_задачи_«Капитальные_инвестиции»_и_решения_студента

---

---

Задача «Optprob/Портфель ценных бумаг»

Проверено: StasFomin 15:29, 30 ноября 2023 (UTC)

Инвестор владеет долями в различных ценных бумагах.

Более конкретно, он владеет b акций некоторых ценных бумаг A_i, \n 1 \leq i \leq n \in

Текущие цены этих ценных бумаг равны v_i.

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

то есть ценная бумага A_i принесет d_i и будет иметь новую цену w_i.

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

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

таких как:

• Общий капитал портфеля не должен изменяться при корректировке; то есть общий капитал, который покупается, такой же, как и проданный.
• Портфель должен избегать чрезмерной зависимости от какой-либо одной ценности. Это условие может быть установлено путем требования, чтобы капитал, связанный с какой-либо конкретной ценной бумагой, после корректировки покупки и продажи составлял по меньшей мере определенный процент r% от текущего общего капитала портфеля.
• Общий капитал в будущем должен составлять не менее текущего капитала плюс определенный процент s% от инвестированного в настоящее время капитала.

Для нашей задачи положим r=3%; s=5%;

• Код решения в проекте «adv2022-course-pyomo-business-optimization» в «optprob/Портфель_ценных_бумаг.ipynb»

📺 видео 📺

---

---

Задача «Optprob/Продажа фруктов»

Проверено: StasFomin 00:06, 28 ноября 2022 (UTC)

Торговцу фруктами нужно

• 16 коробок апельсинов,
• 5 коробок бананов
• 20 коробок яблок.

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

Оптовик А отправляет в каждом контейнере по

• 8 коробок апельсинов,
• 1 коробку бананов и
• 2 коробки яблок.

Оптовый продавец B отправляет

• 2 коробки апельсинов,
• одну коробку бананов,
• 7 коробок яблок в каждом контейнере.

Зная, что оптовик А находится в 150 км, а оптовик В - в 300 км, подсчитайте, сколько контейнеров нам придется купить у каждого оптовика, чтобы сэкономить время и свести к минимуму расстояние (каждый контейнер означает поездку).

📺 видео 📺

• Код решения в проекте «adv2022-course-pyomo-business-optimization» в «optprob/Поставка_фруктов.ipynb»

---

---

Задача «Optprob/производство продукта»

Проверено: StasFomin 23:46, 1 декабря 2022 (UTC)

Компания располагает

• 1000 тоннами минерала В1,
• 2000 тоннами минерала В2
• 500 тоннами B3.

Из этих материалов могут быть получены продукты A1, A2 и A3.

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

Далее подробно указывается необходимое количество каждого минерала для получения 1 тонны каждого

продукта и польза, получаемая от каждого из них.

Компания также должна учитывать:

• что он не должен производить более 10 тонн А2, поскольку на рынке не так много спроса.
• что есть компания, которая покупает минерал В2 по цене 20 долларов за тонну.

Максимизируйте прибыль компании.

• Код решения в проекте «adv2022-course-pyomo-business-optimization» в «optprob/Производство_продукта.ipynb»

📺 видео 📺

---

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

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

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