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

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

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

----

Задача «Optprob/Оптимизация медицинских служб»

Оптимизация медицинских служб 2023-12-24 01-44-52 image0.png

Задача зарезервирована: AlferovIS 14:10, 1 декабря 2024 (UTC)

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

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

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

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

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

Сценарий 1

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

Сценарий 2

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

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

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



Задача «Optprob/Оптимизация использования разных станков»

Оптимизация использования разных станков 2023-12-23 16-58-28 image0.png

У компании есть два типа станков A и B.

  • За каждый час работы на станке A производится 20 деталей, а на станке B — 30 деталей в час.
  • В силу возможностей предприятия и всяких рыночных ограничений в день может быть произведено не более 600 и не менее 250 деталей в день.
  • Кроме того, из-за характеристик двух станков стоимость единицы продукции, произведенной на станке A, составляет €4, а на станке B — €3.

Определите оптимальное количество часов работы в день для двух станков со следующими целями и приоритетами:

  • Приоритет 1. Общая сумма ежедневных расходов не превышает 2000 евро.
  • Приоритет 2. Ежедневное рабочее время на станках A и B одинаково.
  • Приоритет 3. Максимально увеличить количество изделий в день.

Задача зарезервирована: MariaZharova 20:02, 15 декабря 2024 (UTC)



Задача «Optprob/Раздаем задачи сотрудникам, с учетом прошлых оценок»

Раздаем задачи сотрудникам, с учетом прошлых оценок 2023-12-23 16-15-19 image0.png

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

  • 5 задач (T1, T2, T3, T4 и T5)
  • между 4 сотрудниками (E1, E2, E3 и E4)
  • с учетом оценок, сделанных на основе предыдущего опыта, представленного в следующей таблице (0 — плохо, 10 — отлично, "--" никак нельзя давать), надо максимизировать «суммарную оценку»:
Раздаем задачи сотрудникам, с учетом прошлых оценок 2023-12-23 15-50-38 image0.png

Необходимо учитывать следующие ограничения:

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

Задача зарезервирована: Isypovi 19:19, 2 декабря 2024 (UTC)



Задача «MAX-CUT: вероятностное округление/Задачи/eupce-6-20»

Задача зарезервирована: Glbmkrv 00:26, 15 декабря 2024 (UTC)

Eupce-6-20 2023-05-19 12-27-59 image0.png



Задача «MAX-CUT: вероятностное округление/Задачи/eupce-6-17»

Проверено: StasFomin 09:07, 27 ноября 2024 (UTC)

Eupce-6-17 2023-05-18 19-57-47 image0.png

Задача зарезервирована: LunevLA 19:21, 25 ноября 2024 (UTC)



Задача «MAX-SAT: дерандомизация/Задачи/eupce-6-15»

Задача зарезервирована: EjenY 15:43, 10 ноября 2024 (UTC)

Eupce-6-15 2023-05-18 19-51-41 image0.png



Задача «MAX-CUT: вероятностное округление/Задачи/eupce-6-14»

Задача зарезервирована: Solovev 15:41, 10 ноября 2024 (UTC)

Eupce-6-14 2023-05-18 19-44-29 image0.png



Задача «MAX-CUT: вероятностное округление/Задачи/eupce-6-11»

Eupce-6-11 2023-05-18 19-41-29 image0.png

Задача зарезервирована: AlferovIS 20:54, 1 декабря 2024 (UTC)



Задача «MAX-CUT: вероятностное округление/Задачи/eupce-6-10»

Eupce-6-10 2023-05-18 19-38-29 image0.png Eupce-6-10 2023-05-18 19-38-53 image0.png

Задача зарезервирована: Trifonov.dv 19:15, 15 декабря 2024 (UTC)



Задача «MAX-CUT: вероятностное округление/Задачи/eupce-6-8»

Eupce-6-8 2023-05-18 19-34-01 image0.png

Задача зарезервирована: Конин Георгий 20:59, 3 декабря 2024 (UTC)



Задача «MAX-CUT: вероятностное округление/Задачи/eupce-6-7»

Задача зарезервирована: Glbmkrv 02:35, 15 декабря 2024 (UTC)

Eupce-6-7 2023-05-18 19-27-32 image0.png



Задача «MAX-SAT: вероятностное округление/Задачи/eupce-6-3-a»

Проверено: StasFomin 22:42, 17 декабря 2024 (UTC)

  • Дан n-вершинный неориентированный граф G=(V, E).

Рассмотрим следующий метод генерации независимого множества.

Для заданной перестановки вершин σ, определим подмножество S(σ) вершин следующим образом: для каждой вершины i, i ∈ S(σ) тогда и только тогда, когда ни один сосед j вершины i не предшествует i в перестановке σ.

Покажите, что каждый S(σ) будет независимым множеством в G.

Задача зарезервирована: Конин Георгий 10:48, 13 декабря 2024 (UTC)



Задача «MAX-SAT: дерандомизация/Задачи/eupce-6-2-a»

Задача зарезервирована: Solovev 15:12, 10 ноября 2024 (UTC)

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



Задача «Вероятность/Задачи/eupce-2-13»

  • Каждая коробка хлопьев содержит один из 2n различных купонов (купон в каждой коробке выбирается независимо и равномерно случайным образом из 2n).
  • Купоны организованы в n пар, так что купоны 1 и 2 составляют пару, купоны 3 и 4 составляют пару и так далее.
  • Получив по одному купону из каждой пары, вы можете получить приз.

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

Задача зарезервирована: AlferovIS 16:11, 1 декабря 2024 (UTC)



Задача «Вероятность/Задачи/eupce-2-9»

Задача зарезервирована: Галлямов Ислам М05-304б 13:43, 9 декабря 2024 (UTC)

Дважды бросают честный k-гранный кубик с числами от 1 от k до k на гранях кубика, получая значения X1 и X2.

  • E[max(X1, X2)] = ?
  • E[min(X1, X2)] = ?

Покажите, что E[max(X1 , X2)] + E[min(X1 , X2)] = E[X1] + E[X2].



Задача «Вероятность/Задачи/eupce-2-8-a»

Алиса и Боб решили заводить детей до тех пор, пока у них не родится девочка или пока у них не будет k ≥ 1 детей.

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

  • Каково ожидаемое число детей женского пола?
  • Каково ожидаемое число детей мужского пола?

Задача зарезервирована: LunevLA 15:45, 23 ноября 2024 (UTC)



Задача «Вероятность/Задачи/eupce-2-7-c»

Задача зарезервирована: Solovev 15:16, 10 ноября 2024 (UTC)

X и Y — независимые случайные величины с геометрическим распределением, с параметрами P и Q соответственно.

P(min(X, Y) = k) = ?



Задача «Вероятность/Задачи/eupce-2-7-a»

X и Y — независимые случайные величины с геометрическим распределением, с параметрами P и Q соответственно.

P(X = Y) = ?

Задача зарезервирована: Галлямов Ислам М05-304б 15:36, 13 декабря 2024 (UTC)



Задача «Вероятность/Задачи/eupce-2-6-d»

Предположим, что независимо бросают два стандартных шестисторонних кости, X1 — то, что выпадает на первой, X2 — на второй, а X — сумма обоих значений.

  • 2 ≤ k ≤ 12
  • E[X1 - X2 | X = k] = ?

Задача зарезервирована: RomanFilonov 20:42, 8 декабря 2024 (UTC)



Задача «Вероятность/Задачи/eupce-2-6-c»

Предположим, что независимо бросают два стандартных шестисторонних кости, X1 — то, что выпадает на первой, X2 — на второй, а X — сумма обоих значений.

E[X1 | X = 9] = ?

Задача зарезервирована: AlferovIS 16:19, 1 декабря 2024 (UTC)



Задача «Вероятность/Задачи/eupce-2-6-b»

Предположим, что независимо бросают два стандартных шестисторонних кости, X1 — то, что выпадает на первой, X2 — на второй, а X — сумма обоих значений.

E[X | X1 = X2] = ?

Задача зарезервирована: LunevLA 15:06, 25 ноября 2024 (UTC)



Задача «Вероятность/Задачи/eupce-2-5»

Если X — случайная величина с биномиальным распределением B(n, 1/2) для n ≥ 1, покажите, что вероятность того,

что X — четное будет 1/2.

Задача зарезервирована: AlferovIS 16:09, 1 декабря 2024 (UTC)



Задача «Вероятность/Задачи/eupce-2-4»

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

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



Задача «Вероятность/Задачи/eupce-1-26-a»

Задача зарезервирована: Ydanyok 09:03, 13 декабря 2024 (UTC)

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

  • Изначально, бросая честную монетку, разметим каждый из девяти квадратов либо X, либо O.
  • Если только один из игроков имеет «три в ряд» → он победил.
  • Если оба или никто → ничья.

Определите вероятность, что «X» выиграет.



Задача «Вероятность/Задачи/eupce-1-16-d»

Задача зарезервирована: Glbmkrv 00:20, 15 декабря 2024 (UTC)

Рассмотрим игру, основанную на бросках трех стандартных шестисторонних костей. Цель → получить одинаковое число на всех трех костях, кто первый этого добьется, тот выиграл.

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

Предположим, что игрок использует следующую оптимальную стратегию:

  • если все три кости одинаковые → останавливаемся и выигрываем;
  • если два кубика совпадают, игрок перебрасывает тот, который «выбивается из коллектива».
  • если все не совпадают — перебрасываем их всех.

Рассматривая все возможные возможные выпадения костей, найдите вероятность того, что игрок выиграет.



Задача «Вероятность/Задачи/eupce-1-15»

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

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

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



Задача «Вероятность/Задачи/eupce-1-14»

Задача зарезервирована: Ydanyok 15:32, 13 декабря 2024 (UTC)

Я играю в турнире ракетбола против игрока, против которого раньше не играл, но видел его в игре.

Априори рассматриваю три равновероятные возможности:

  • мы одинаково талантливы, каждый из нас в равной степени может выиграть каждую игру;
  • Я немного лучше, и поэтому я выигрываю каждую игру независимо с вероятностью 0.6;
  • Он немного лучше, и поэтому он выигрывает каждую игру независимо с вероятностью 0.6.

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

В апостеорной модели, с какой вероятностью я должен верить, что мой оппонент немного лучше, чем я?



Задача «Вероятность/Задачи/eupce-1-13»

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

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

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

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

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

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



Задача «Вероятность/Задачи/eupce-1-11-c»

Пытаемся передать один бит (0 или 1) через «n» промежуточных узлов, каждый из которых независимо

может инвертировать бит с вероятностью «p».

Докажите, что вероятность получения корректного бита:

   \frac{1+(1-2p)^n}{2}

Задача зарезервирована: RomanFilonov 19:10, 8 декабря 2024 (UTC)



Задача «Вероятность/Задачи/eupce-1-9»

  • Честную монету бросили «n» раз.
  • Для k>0, найдите верхнюю границу вероятности, что будет последовательность из \log_2 n + k последовательных орлов.

Задача зарезервирована: RomanFilonov 15:46, 8 декабря 2024 (UTC)



Задача «Open Exercises»

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



Задача «Optprob/Назначение инженеров на проекты»

Назначение инженеров на проекты 2023-12-23 03-17-06 image0.png

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

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

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

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

Задача зарезервирована: Evvnes 07:21, 14 ноября 2024 (UTC)



Задача «Optprob/Планируем генерацию электричества»

Планируем генерацию электричества 2023-12-23 04-16-43 image0.png

Долгосрочный план выработки электроэнергии учитывает график работы существующих энергоблоков и график установки новых электростанций для удовлетворения спроса на электроэнергию в течение ряда будущих (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)



Задача «Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Задачи/accept-after-t-steps-in-npc»

Задача зарезервирована: Ydanyok 09:10, 13 декабря 2024 (UTC)

Язык L состоит из пар (M, t), где
M
одноленточная машина Тьюринга над бинарным алфавитом.
t
число t единичной системе (t единиц).
  • Существует вход x, M(x) останавливается и возвращает 1, после t шагов.

Покажите, что это NP-полная задача.



Задача «Введение в теорию вычислимости/Задачи/NP-sums»

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

Задача зарезервирована: LunevLA 16:01, 23 ноября 2024 (UTC)



Задача «Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Задачи/MAX-CUT-NPC»

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

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



Задача «Жадный алгоритм покрытия для почти всех исходных данных/Задачи/Жадное вершинное покрытие для почти всех исходных данных»

Задача зарезервирована: Ydanyok 09:03, 13 декабря 2024 (UTC)

Рассмотрим жадный алгоритм для вершинного покрытия («брать вершину максимальной степени, ребра удалять»), на случайных графах, у которых
  • n-вершин
  • ребра между любой парой вершин возникают с вероятностью p.

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

(упрощенный вариант — для фиксированного p=½).


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

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

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