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

Материал из DISCOPAL
Перейти к: навигация, поиск

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

----


Задача зарезервирована: Philipakhiarov 16:33, 3 декабря 2022 (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

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

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

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

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



Задача зарезервирована: PankratovViktor 17:37, 29 ноября 2022 (UTC)

В городе, поделенном на 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

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

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

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

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

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

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

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

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


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



Задача зарезервирована: Участник:Robohant

Есть металлургическая фабрика, на которой производятся металлические пруты, на складе их ( j = 1 … n), n=50. Каждый прут j имеет длину LA_j (в сантиметрах, запятая там для красоты).


Получен заказ на набора запрошенных прутков десяти типов (i = 1...m, m=10). Каждый тип i имеет длину ld_i и количество брусков D_i.

DemandedBars
IdLengthNumber
11,2004
260020
350013
41,5002
52,0005
67005
79005
84005
91,00016
101,10014

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

Т.е. пусть целевая функция

   \sum_j d_j + C \times \alpha_j

  • где d_j — остаток прута j меньше 200см
  • \alpha_j — индикатор, что прут j вообще использовали.




Задача зарезервирована: PankratovViktor 17:38, 29 ноября 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.

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




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

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

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

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

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


Задача зарезервирована: Vshokorov 12:30, 4 декабря 2022 (UTC)




Задача зарезервирована: Philipakhiarov 10:23, 4 декабря 2022 (UTC)

Представим некую систему штучного производства.

Есть шесть станков и неопределенное количество операторов.

Каждый станок i имеет производительность R_i единиц продукции в час.

R_i = 500 300 190 160 100 90
  • К станкам можно приставлять оператора, но это стоит денег.
C_i = 150 100 130 120 100 100
  • Станок 4 глючит, если он используется, к нему обязательно приставлять оператора.
  • К остальным станкам оператора не обязательно приставлять, но если приставить — производство ускорится на 20%. Ну или просто можно считать что там будет «увеличенная производительность» заданная
RR_i = 600 360 228 160 120 108
  • Ни в коем случае нельзя назначать более одного оператора.
  • Если станок работает больше 8 часов, надо заплатить штраф F=1500
  • Надо произвести Q=10000 деталей

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




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

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

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

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

Группа     1  2  3  4  5
Минимум    2  2  5  3  5
Максимум   7  8  7  6  10
  • В каждой группе нужно работать над двумя предметами.
  • Каждый предмет, должен изучаться по крайней мере в одной группе
  • Если индекс компетентности кого-то в предмете меньше 0.5, он не может входить в рабочую группу, которая этим занимается.
  • Предметы, которые изучает группа, должны быть совместимы («нет конфликта интересов», «техника безопасности» … )


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

Задача зарезервирована: Тараймович Игорь 18:25, 4 декабря 2022 (UTC)



Задача зарезервирована: SochnevaMA М05-104в 11:00, 1 декабря 2022 (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%.
  • Отдельно стоящие дома могут располагаться только в один ряд.
  • Застройщик не обязан строить весь ряд — можно строить дома в упор друг-другу, или с промежутками, или вовсе не до конца.

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



Задача зарезервирована: Kiranov dmitry 20:00, 5 декабря 2022 (UTC)

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

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

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

  • Для этого, создается 15 учебных групп.
  • В каждой группе может быть не более 10 учеников.
  • Во всех группах есть ученики с блестящей оценкой (если их не менее 15).
  • Если в группе нет отличников, в ней должно быть по крайней мере, столько же отличников, сколько и в группе с «блестящими».
  • У группы есть уровень \forall j: y_j = \sum_{i=1}^{4} v_i x_{ij}, где x_{ij} — число студентов «уровня i» назначенных в группу «j».

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




Система имеет 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 14:15, 17 ноября 2022 (UTC)



Задача зарезервирована: Участник:Robohant

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

На складе есть 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х метров.


Есть 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=совместимы), представлена ниже.

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



Задача зарезервирована: Kiranov dmitry 19:39, 4 декабря 2022 (UTC)

Компания рассматривает пять проектов.

Каждый утвержденный проект будет выполняться в 3-летний период.

Ожидаемые доходы и ежегодные расходы по каждому проекту, а также доступные годовые средства в тысячах евро:

Выбор проекта 2022-10-21 16-48-44 image0.png

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

Кроме того:

  • Проект 3 не может быть выбран, если он выбран проект 5.
  • Проекты 1 и 2 завершаются совместно только в том случае, если не завершены оба — проект 4, и проект 5.
  • Компания должна сократить свои свободные средства на 5000 долларов в течение одного из 3 лет и должна решить, в каком году это сделать.




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

Покупка станков 2022-10-21 16-42-28 image0.png

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

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

Надо:

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

Задача зарезервирована: Cherniavskii 09:14, 12 ноября 2022 (UTC)




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

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

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

Планируем генерацию электричества 2022-10-21 16-20-36 image0.png

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

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

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

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

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

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

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

CE_{it}, 1 \leq i \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)




Задача зарезервирована: Larin.dv 11:36, 6 декабря 2022 (UTC)

Город разделен на 18 районов.

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

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

PSEC могут быть установлены двумя способами: по отдельности или парами (два смежных

PSEC устанавливаются с двойным дозатором).

Стоимость отдельного PSEC составляет CI, в то время как общая стоимость двух PSEC на пару составляет CD.

Бюджет, доступный для проекта, составляет P.

Парковки для электромобилей 2022-10-21 13-28-41 image0.png



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

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

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