Open Exercises
Всего страниц найдено: 71.
Задача «Задачи/eupce-1-11-a»©
Пытаемся передать один бит (0 или 1) через «n» промежуточных узлов, каждый из которых независимо
может инвертировать бит с вероятностью «p».
Докажите, что вероятность получения корректного бита:
K_4
Задача «Задачи/eupce-6-2-a»©
Докажите, что для каждого целого числа n существует раскраска ребер полного графа в два цвета, такое что полное число одноцветных подграфов
Задача зарезервирована: StasFomin 11:32, 19 мая 2023 (UTC)
Задача «Задачи/eupce-6-20»©
Задача «Задачи/eupce-6-19»©
Задача «Задачи/eupce-6-17»©
Задача «Задачи/eupce-6-15»©
Задача «Задачи/eupce-6-14»©
Задача «Задачи/eupce-6-13»©
Задача «Задачи/eupce-6-11»©
Задача «Задачи/eupce-6-10»©
Задача «Задачи/eupce-6-9»©
Задача «Задачи/eupce-6-8»©
Задача «Задачи/eupce-6-4»©
- Дан n-вершинный неориентированный граф G=(V, E)
Рассмотрим следующий метод генерации независимого множества.
Для заданной перестановки вершин σ, определим подмножество S(σ) вершин следующим образом: для каждой вершины i, i ∈ S(σ) тогда и только тогда, когда никакой ни один сосед j вершины i не предшествует i в перестановке σ.
Предложите вероятностный алгоритм для поиска σ
для которого можно показать, что ожидаемый размер
где означает степень вершины i.
Докажите, что в G существует независимое множество размера как минимум
Задача «Задачи/eupce-6-3-a»©
- Дан n-вершинный неориентированный граф G=(V, E)
Рассмотрим следующий метод генерации независимого множества.
Для заданной перестановки вершин σ, определим подмножество S(σ) вершин следующим образом: для каждой вершины i, i ∈ S(σ) тогда и только тогда, когда никакой ни один сосед j вершины i не предшествует i в перестановке σ.
Покажите, что каждый S(σ) будет независимым множеством в G.
Задача «Задачи/eupce-6-1-b»©
Предложите алгоритм дерандомизации методом условных вероятностей для алгоритма из MAX-SAT: вероятностное округление/Задачи/eupce-6-1-a.
Задача «Задачи/eupce-6-1-a»©
Рассмотрим K-ESAT, SAT, когда в каждой скобке ровно k литералов.
Предложите Лас-Вегас алгоритм выполняющий минимум
скобок, и проанализируйте матожидание его времени выполнения.
Задача «Задачи/eupce-2-13-b»©
Решите обобщенную версию задачи [[../eupce-2-13]]:
- kn различных купонов, организованных в n непересекающихся наборов из k купонов.
- нужен один купон из каждого набора.
Задача «Задачи/eupce-2-13»©
- Каждая коробка хлопьев содержит один из 2n различных купонов (купон в каждой коробке выбирается независимо и равномерно случайным образом из 2n).
- Купоны организованы в n пар, так что купоны 1 и 2 составляют пару, купоны 3 и 4 составляют пару и так далее.
- Получив по одному купону из каждой пары, вы можете получить приз.
Какое ожидаемое количество коробок, надо для этого купить?
Задача «Задачи/eupce-2-9»©
Дважды бросают честный 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 и что многоплодных родов не бывает.
- Каково ожидаемое число детей женского пола?
- Каково ожидаемое число детей мужского пола?
Задача «Задачи/eupce-2-7-d»©
X и Y — независимые случайные величины с геометрическим распределением, с параметрами P и Q соответственно.
E[X | X ≤ Y] = ?
Задача «Задачи/eupce-2-7-c»©
X и Y — независимые случайные величины с геометрическим распределением, с параметрами P и Q соответственно.
P(min(X, Y) = k) = ?
Задача «Задачи/eupce-2-7-b»©
X и Y — независимые случайные величины с геометрическим распределением, с параметрами P и Q соответственно.
E[max(X, Y)] = ?
Задача «Задачи/eupce-2-7-a»©
X и Y — независимые случайные величины с геометрическим распределением, с параметрами P и Q соответственно.
P(X = Y) = ?
Задача «Задачи/eupce-2-6-d»©
Предположим, что независимо бросают два стандартных шестисторонних кости, X1 — то, что выпадает на первой, X2 — на второй, а X — сумма обоих значений.
- 2 ≤ k ≤ 12
- E[X1 - X2 | X = k] = ?
Задача «Задачи/eupce-2-6-c»©
Предположим, что независимо бросают два стандартных шестисторонних кости, X1 — то, что выпадает на первой, X2 — на второй, а X — сумма обоих значений.
E[X1 | X = 9] = ?
Задача «Задачи/eupce-2-6-b»©
Предположим, что независимо бросают два стандартных шестисторонних кости, X1 — то, что выпадает на первой, X2 — на второй, а X — сумма обоих значений.
E[X | X1 = X2] = ?
Задача «Задачи/eupce-2-6-a»©
Предположим, что независимо бросают два стандартных шестисторонних кости, X1 — то, что выпадает на первой, X2 — на второй, а X — сумма обоих значений.
E[X | X1 — четное] = ?
Задача «Задачи/eupce-2-5»©
Если X — случайная величина с биномиальным распределением B(n, 1/2) для n ≥ 1, покажите, что вероятность того,
что X — четное будет 1/2.
Задача «Задачи/eupce-2-4»©
Докажите, что для любого целого .
Задача «Задачи/eupce-1-26-b»©
Обычные крестики-нолики скучные, при оптимальной стратегии в них выигрывают крестики.
Рассмотрим вероятную модификацию этой игры.
- Как обычно, крестики и нолики ходят по очереди и нолик идет первым. Как обычно, выигрывает тот, кто первый добъется «три в ряд», или ничья, если никто.
- Но на каждом ходе позиция и у крестиков и у ноликов выбирается независимо и равномерно среди свободных квадратов.
Найдите вероятность, выигрыша для «крестиков» и для «ноликов».
Задача «Задачи/eupce-1-26-a»©
Обычные крестики-нолики скучные, при оптимальной стратегии в них выигрывают крестики.
Рассмотрим вероятную модификацию этой игры.
- Изначально, бросая честную монетку, разметим каждый из девяти квадратов либо X, либо O.
- Если только один из игроков имеет «три в ряд» → он победил.
- Если оба или никто → ничья.
Определите вероятность, что «X» выиграет.
Задача «Задачи/eupce-1-18»©
- Есть функция
- и известно что .
Единственный способ вычисления F — использовать таблицу поиска, в которой хранится значения F. К сожалению, злой противник изменил значение 1/5 записей в этой таблице.
Опишите простой рандомизированный алгоритм, который, учитывая входной Z, выводит значение, которое равняется f(z) с вероятностью не менее 1/2.
Ваш алгоритм должен работать для каждого значения Z, независимо от того, какие записи изменил противник.
Дополнительно, предположим, вам разрешено повторить этот ваш начальный алгоритм три раза.
Как этим воспрользоваться, чтобы максимально увеличить вероятность правильного ответа, и какова эта вероятность?
Задача «Задачи/eupce-1-16-d»©
Рассмотрим игру, основанную на бросках трех стандартных шестисторонних костей.
Цель → получить одинаковое число на всех трех костях, кто первый этого добьется, тот выиграл.
- Игрок начинает с броска всех трех кубиков.
- После первого броска игрок может выбрать одну, две или три кости и бросить их снова.
- После второго броска игрок один из трех кубиков и перебросить его.
Предположим, что игрок использует следующую оптимальную стратегию:
- если все три кости одинаковые → останавливаемся и выигрываем;
- если два кубика совпадают, игрок перебрасывает тот, который «выбивается из коллектива».
- если все не совпадают — перебрасываем их всех.
Рассматривая все возможные возможные выпадения костей, найдите вероятность того, что игрок выиграет.
Задача «Задачи/eupce-1-16-c»©
Рассмотрим игру, основанную на бросках трех стандартных шестисторонних костей.
Цель → получить одинаковое число на всех трех костях, кто первый этого добьется, тот выиграл.
- Игрок начинает с броска всех трех кубиков.
- После первого броска игрок может выбрать одну, две или три кости и бросить их снова.
- После второго броска игрок один из трех кубиков и перебросить его.
Предположим, что игрок использует следующую оптимальную стратегию:
- если все три кости одинаковые → останавливаемся и выигрываем;
- если два кубика совпадают, игрок перебрасывает тот, который «выбивается из коллектива».
- если все не совпадают — перебрасываем их всех.
Найдите вероятность того, что игрок выиграет, если на первом шаге он уже выбросил две одинаковые кости.
Задача «Задачи/eupce-1-16-b»©
Рассмотрим игру, основанную на бросках трех стандартных шестисторонних костей.
Цель → получить одинаковое число на всех трех костях, кто первый этого добьется, тот выиграл.
- Игрок начинает с броска всех трех кубиков.
- После первого броска игрок может выбрать одну, две или три кости и бросить их снова.
- После второго броска игрок один из трех кубиков и перебросить его.
Предположим, что игрок использует следующую оптимальную стратегию:
- если все три кости одинаковые → останавливаемся и выигрываем;
- если два кубика совпадают, игрок перебрасывает тот, который «выбивается из коллектива».
- если все не совпадают — перебрасываем их всех.
Найдите вероятность того, что ровно два из трех кубиков показывают одинаковое число в первом броске.
Задача «Задачи/eupce-1-16-a»©
Рассмотрим игру, основанную на бросках трех стандартных шестисторонних костей.
Цель → получить одинаковое число на всех трех костях, кто первый этого добьется, тот выиграл.
- Игрок начинает с броска всех трех кубиков.
- После первого броска игрок может выбрать одну, две или три кости и бросить их снова.
- После второго броска игрок один из трех кубиков и перебросить его.
Предположим, что игрок использует следующую оптимальную стратегию:
- если все три кости одинаковые → останавливаемся и выигрываем;
- если два кубика совпадают, игрок перебрасывает тот, который «выбивается из коллектива».
- если все не совпадают — перебрасываем их всех.
Найдите вероятность того, что все три кубика показывают одинаковое число в первом броске.
Задача «Задачи/eupce-1-15»©
Предположим, что бросают десять стандартных шестисторонних костей.
Какова вероятность того, что их сумма будет деленной на 6, предполагая, что броски независимы?
Задача «Задачи/eupce-1-14»©
Я играю в турнире ракетбола против игрока, против которого раньше не играл, но видел его в игре.
Априори рассматриваю три равновероятные возможности:
- мы одинаково талантливы, каждый из нас в равной степени может выиграть каждую игру;
- Я немного лучше, и поэтому я выигрываю каждую игру независимо с вероятностью 0.6;
- Он немного лучше, и поэтому он выигрывает каждую игру независимо с вероятностью 0.6.
В рокетбол играют, пока один игрок не выиграет три сета. В нашей игре, я выиграл только второй сет, а противник выиграл первый, третий и четвертый.
В апостеорной модели, с какой вероятностью я должен верить, что мой оппонент немного лучше, чем я?
Задача «Задачи/eupce-1-13»©
Медицинская компания рекламирует свой новый тест на определенное заболевание.
Частота ошибок первого рода (false negative) мала: если у вас есть расстройство, вероятность того, что тест вернет положительный результат, составляет 0.999.
Частота ошибок второго рода (false positive) тоже невелика: если у вас нет расстройства, вероятность того, что тест вернет положительный результат, составляет всего 0.005.
Предположим, что эту болезнь имеет 2% населения.
Если мы проверяем человека, выбранного равномерно из популяции, и получается положительный результат, какова вероятность того, что эта болезнь у него действительно есть?
Задача «Задачи/eupce-1-12»©
Есть три коробки.
В одной миллион рублей, в двух других — 100р.
Игра играется следующим образом:
- Участник выбирает коробку.
- Ведущий открывает одну из других коробок, чтобы убедить, что там всего — 100р.
- Участник может выбрать первоначально выбранную коробку или переключится на другую (разумеется, логично выбрать не ту, где показали 100 р).
Итак, если участник сменит выбранную на первом шаге коробку, увеличит ли это его шансы?
Задача «Задачи/eupce-1-11-b»©
- Пытаемся передать один бит (0 или 1) через промежуточные узлы, каждый из которых независимо может инвертировать бит с вероятностью «p».
- Скажем, узел имеет смещение «q», если это , «смещение» будет вещественным числом на отрезке [−1, 1].
Докажите, что прохождение бита через узлы со смещениями «q1» и «q2» эквивалентно прохождению бита через один узел со смещением «q1×q2».
Задача «Задачи/eupce-1-11-c»©
Пытаемся передать один бит (0 или 1) через «n» промежуточных узлов, каждый из которых независимо
может инвертировать бит с вероятностью «p».
Докажите, что вероятность получения корректного бита:
Задача «Задачи/eupce-1-10»©
Есть нормальная честная монета и фальшивая, с двумя «решками». Допустим, что мы
- выбираем одну из двух монет случайным образом,
- подбрасываем ее
- выпала решка.
Какова вероятность, что мы выбрали фальшивую монету?
Задача «Задачи/eupce-1-9»©
- Честную монету бросили «n» раз.
- Для k>0, найдите верхнюю границу вероятности, что будет последовательность из последовательных орлов.
Задача «Задачи/P^BPP»©
Какой класс будет
Задача «Задачи/\Sigma^p k=NP^(\Sigma^p (k-1))»©
Докажите
Задача «Задачи/compliment-in-ph»©
Задача «Задачи/Свойство Sigma i=PH»©
.
Задача «Задачи/3csat-npc»©
Задача «Задачи/DHAM3»©
Пусть
- — задача поиска гамильтонового цикла в графе , где V — делиться на 3.
- — задача подтверждения наличия гамильтонового цикла в таком графе.
Докажите, что и — NP-трудны.
Задача «Задачи/MAX-CUT-NPC»©
Докажите, что задача MAX-CUT, в форме задачи разрешения («правда, ли, что для графа G есть разрез больше K?») NP-полна.
Задача «Задачи/NTIME-NlogN-reduction-3SAT»©
Покажите, что для любого языка , можно построить полиномиальную Карп-сводимость, от слов длины n, к 3SAT-формулам длины .
Задача «Задачи/QBEQ-NPC-NPC»©
Покажите NP-полноту языка совместимых систем квадратичных уравнений в булевых переменных. Т.е. разрешимых систем вида
и где сложение по модулю 2.
Задача «Задачи/USUBSETSUM-IN-P»©
Вспомним задачу булев-рюкзак выполнимость, и потребуем, чтобы все веса и размер рюкзака задавались в унарной системе ().
Покажите, что тогда язык таких выполнимых рюкзаков, лежит в классе P.
Задача «Задачи/accept-after-t-steps-in-npc»©
Язык L состоит из пар (M, t), где
- M
- одноленточная машина Тьюринга над бинарным алфавитом.
- t
- число t единичной системе (t единиц).
- Существует вход x, M(x) останавливается и возвращает 1, после t шагов.
Покажите, что это NP-полная задача.
Задача «Задачи/conp-as-yes»©
Покажите, что язык L лежит в co-NP тогда и только тогда, если существует недетерминированная машина M, и полином p, такой, что M останавливается за время p(n) для всех входов x длины n, и L состоит точно только из таких строк x, у которых все пути вычисления M(x) приводят к ответу «1».
Задача «Задачи/scheduling-ident-machines-in-npc»©
Рассмотрим задачу разрешения для оптимизационной задачи Планирование Задач на Одинаковых Машинах («если ли планировка с максимальным временем меньше k»).
Покажите, что эта задача, даже в случае p=2, NP-полна.
Задача «Задачи/unary-in-p-then-exptime-nexp»©
Докажите, что если каждый унарный язык из NP также лежит в P, то EXPTIME=NEXP.
Задача «Задачи/unary-in-p-then-time2kn-in-time2cn»©
Докажите, что если каждый унарный язык из NP также лежит в P, то то для любого языка из для какого-либо k, он тажке лежит в для любого c.
Задача «Задачи/Квадрат букв»©
Задача «Задачи/Порядок закачек — NPC»©
Представим распределенный сервис стриминга видеофильмов. Центральный сервер с полной БД фильмов получает от периферийных кеширующих узлов запросы на требуемые фильмы и ориентировочные сроки, когда люди собираются их посмотреть.
Однако пропускная способность от сервера с дисками к внешнему миру ограничена, и требуется составить работающее расписание отгрузки фильмов.
Конкретно, узел контроля планирования получает n-заданий вида:
- «начать_не_раньше, закончить_не_позже, размер_фильма»i, 1<=i<=n
- максимальная пропускная способность не больше МаксКанал
И говорит «OK» (или «Паника-Паника!» в противном случае), если существует такое расписание из n команд отгрузки, соответствующих заданию (1<=i<=n ):
- «время_начала, время_окончания, ширина_канала»i,
- время_началаi >= начать_не_раньшеi
- время окончанияi <= закончить_не_позжеi
- ширина_каналаi <= МаксКанал
- ширина_канала*(время_окончания — время_начала)i >= размер_фильмаi
Докажите NP-полноту задачи.
Hint: Можно через «Рюкзак-выполнимость» или «SUBSET-SUM»
Задача «Задачи/ptas-for-minimal-scheduling»©
Разработайте PTAS-алгоритм для Планирование Задач на Одинаковых Машинах используя этот подход.
Задача «Задачи/NP-sums»©
Проверить принадлежность классу следующей задачи: по заданному конечному множеству натуральных чисел, представленных в своей бинарной записи, определить возможность разделения этого множества на два подмножества с одинаковыми суммами.
Задача «Задачи/dtime-n2-is-closed-carp-reduction»©
- Класс сложности С замкнут относительно какой-то сводимости, если L→L' и , то .
Рассмотрим класс .
Замкнут ли он относительно полиномиальной сводимости по Карпу?
Задача «Задачи/maximum-k-choice-knapsack-dynamic-programming»©
Придумайте алгоритм динамического программирования, находящий оптимальное решение задачи Maximum Integer k-choice Knapsack.
Задача «Задачи/Жадное вершинное покрытие для почти всех исходных данных»©
Рассмотрим жадный алгоритм для вершинного покрытия («брать вершину максимальной степени, ребра удалять»), на случайных графах, у которых
- n-вершин
- ребра между любой парой вершин возникают с вероятностью p.
Какова точность алгоритма для почти всех исходных данных?
(упрощенный вариант — для фиксированного p=½).
Задача «Задачи/P^(\Sigma^p k)=P^(\Pi^p k)»©
Докажите
Задача «[[Зарезервированные практические задачи|]]»©
Всего страниц найдено: 14.
----
Докажите, что для каждого целого числа n существует раскраска ребер полного графа
Задача зарезервирована: StasFomin 11:32, 19 мая 2023 (UTC)
- Конечное множество U, для каждого u ∈ U задан
- вес-размер
s(u)∈ Z^+ - ценность
v(u)∈ Z^+
- вес-размер
- Положительное целое
B∈ Z^+ — размер рюкзака. - Выбрать подмножество U' ⊆ U, не превышающее емкость рюкзака:
\displaystyle\sum\limits_{u∈ U'} s(u)≤B - Максимизировать ценность выбранных элементов,
\displaystyle\sum\limits_{u∈ U'} v(u) → \max .
Задача в лаб17 (рид-онли просмотр)
-
— есть тестовые данные и визуализация. -
— есть Pyomo-формулировка для ЦЛП.
- Задача в базе NP-полных задач Вигго Кана
- Код задачи в книге «ГД» → «MP9»
Задача зарезервирована: Анна_Дмитриенко,_М05-204 14:19, 26 ноября 2023 (UTC)
- Коллекция C подмножеств конечного множества S.
- Найти подколлекцию C'⊆ C, такую, что для каждой пары различных элементов
x_1,x_2∈ S , есть некоторое множествоc∈ C' , которое содержит точно один элемент из этой пары. - Минимизировать мощность этой подколлекции |C'|.
Задача в лаб17 (рид-онли просмотр)
- Задача в базе NP-полных задач Вигго Кана
- Код задачи в книге «ГД» → «SP6»
Задача зарезервирована: 3xMike 14:23, 26 ноября 2023 (UTC)
- Набор C из m городов с заданными расстояниями между ними
d(c_i,c_j)∈ N для каждой пары городов. Расстояния удовлетворяют неравенству треугольника! - Найти тур C, т.е. перестановка
\pi: [1..m]→ [1..m] . - Минимизировать длину этого тура
d\left(\{c_{\pi(m)},c_{\pi(1)}\}\right)+\displaystyle\sum\limits_{i=1}^{m-1} d\left(\{c_{\pi(i)},c_{\pi(i+1)}\}\right)
Задача в лаб17 (рид-онли просмотр)
Задача зарезервирована: annimo 12:54, 25 октября 2023 (UTC)
- Граф G=(V,E).
- Найти клику в G, т.е. подмножество вершин V'⊆V, такое что любая пара вершин в V' соединены ребром из E.
- Максимизировать размер клики, т.е. |V'|.
Задача в лаб17 (рид-онли просмотр)
- Задача в базе NP-полных задач Вигго Кана
- Код задачи в книге «ГД» → «GT19»
Задача зарезервирована: Lachin Sergey 20:07, 4 декабря 2023 (UTC)
Граф G=(V,E).
Найти раскраску G, т.е. разбиение V на непересекающиеся наборы
V1, V2, …, Vk, такие, что каждый Vi независимое множество в G.
Минимизировать размерность раскраски, т.е. число этих независимых наборов Vi.
Задача в лаб17 (рид-онли просмотр)
- Задача в базе NP-полных задач Вигго Кана
- Код задачи в книге «ГД» → «GT4»
Задача зарезервирована: Alekseevk1 08:41, 16 августа 2023 (UTC)
У нас есть группа из 60 экскурсантов, которые наняли услуги компании автобусных туров на следующие 3 дня.
- Есть шесть различных экскурсий, которые могут быть проведены.
- Каждый экскурсант выбрал максимум три экскурсии. Экскурсант может взять только одну экскурсию в день.
Вот, какие экскурсии выбрал каждый экскурсант:
| Экскурсант | Экскурсия |
| 1 | 1 |
| 1 | 3 |
| 1 | 5 |
| 2 | 2 |
| 2 | 4 |
| 3 | 6 |
| 4 | 2 |
| 5 | 1 |
| 5 | 5 |
| 6 | 4 |
| 6 | 6 |
| 6 | 3 |
| 7 | 1 |
| 7 | 4 |
| 7 | 5 |
| 8 | 3 |
| 8 | 5 |
| 9 | 2 |
| 10 | 1 |
| 10 | 3 |
| 11 | 1 |
| 11 | 4 |
| 12 | 3 |
| 12 | 5 |
| 13 | 6 |
| 13 | 4 |
| 14 | 2 |
| 14 | 6 |
| 15 | 2 |
| 15 | 4 |
| 16 | 4 |
| 16 | 5 |
| 17 | 2 |
| 17 | 6 |
| 18 | 2 |
| 18 | 6 |
| 19 | 1 |
| 19 | 4 |
| 20 | 6 |
| 20 | 2 |
| 21 | 1 |
| 21 | 3 |
| 22 | 4 |
| 22 | 6 |
| 23 | 6 |
| 24 | 1 |
| 24 | 3 |
| 24 | 6 |
| 25 | 2 |
| 26 | 2 |
| 26 | 4 |
| 27 | 4 |
| 27 | 5 |
| 28 | 3 |
| 28 | 5 |
| 29 | 6 |
| 29 | 3 |
| 30 | 1 |
| 30 | 4 |
| 30 | 5 |
| 31 | 6 |
| 32 | 2 |
| 33 | 1 |
| 33 | 3 |
| 34 | 2 |
| 34 | 4 |
| 35 | 4 |
| 35 | 6 |
| 36 | 6 |
| 36 | 2 |
| 37 | 1 |
| 37 | 3 |
| 37 | 5 |
| 38 | 4 |
| 38 | 5 |
| 38 | 6 |
| 39 | 2 |
| 40 | 3 |
| 40 | 5 |
| 41 | 2 |
| 41 | 6 |
| 42 | 2 |
| 42 | 6 |
| 43 | 3 |
| 44 | 4 |
| 44 | 5 |
| 45 | 1 |
| 45 | 4 |
| 46 | 2 |
| 46 | 6 |
| 47 | 2 |
| 47 | 4 |
| 48 | 4 |
| 48 | 6 |
| 49 | 6 |
| 50 | 2 |
| 50 | 6 |
| 51 | 2 |
| 52 | 3 |
| 52 | 5 |
| 53 | 1 |
| 53 | 3 |
| 54 | 3 |
| 54 | 5 |
| 55 | 6 |
| 55 | 2 |
| 56 | 1 |
| 56 | 3 |
| 56 | 5 |
| 57 | 1 |
| 57 | 4 |
| 57 | 5 |
| 58 | 2 |
| 58 | 4 |
| 59 | 4 |
| 59 | 6 |
| 59 | 3 |
| 60 | 4 |
| 60 | 5 |
| 60 | 6 |
- Автобусы компании имеют вместимость (количество мест). У компании 5 автобусов.
| Buses | 1 | 2 | 3 | 4 | 5 |
| |
60 | 50 | 60 | 60 | 40 |
Один автобус в день может совершить несколько экскурсий в зависимости от близости между ними.
Эта информация будет собрана в бинарном атрибуте между экскурсиями (1: они могут быть
выполняться одним и тем же автобусом, 0: нет).
| Вблизи | 1 | 2 | 3 | 4 | 5 | 6 |
| 1 | 0 | 1 | 0 | 0 | 0 | 1 |
| 2 | 0 | 0 | 0 | 1 | 1 | 0 |
| 3 | 0 | 0 | 0 | 0 | 1 | 0 |
| 4 | 0 | 0 | 0 | 0 | 1 | 0 |
| 5 | 0 | 0 | 0 | 0 | 0 | 0 |
| 6 | 0 | 0 | 0 | 0 | 0 | 0 |
- Однако автобус не должен охватывать более двух экскурсий за один день.
- Компания хочет спланировать экскурсии на 3 дня, чтобы использовать наименьшее количество автобусов
(минимизируем «автобусо-дни»).
- При этом нужно найти назначение экскурсий и экскурсантов на рейсы автобусов
Задача зарезервирована: Ivanstepanov 9:01, 21 ноября 2023 (UTC)
Задача зарезервирована: Gleb Berezin M05-203v 14:25, 5 декабря 2023 (UTC)
Мы планируем распределять инженеров по проектам компании.
В течение следующего года компания имеет возможность участвовать в десяти инженерных проектах.
Каждый проект требует персонала (для проекта j потребуется Aj инженеров любого типа), приносит доход (G_j) и имеет общие расходы (C_j).
| Projects | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| A | 3 | 3 | 3 | 2 | 2 | 2 | 4 | 4 | 4 | 5 |
| C | 10000 | 20000 | 25000 | 40000 | 10000 | 40000 | 20000 | 25000 | 10000 | 30000 |
| G | 55000 | 60000 | 60000 | 90000 | 30000 | 100000 | 65000 | 50000 | 50000 | 60000 |
Инженеры компании делятся на две категории:
- S: Старший инженер (с опытом)
- JJ: Младший инженер (без достаточного опыта)
Каждый инженер имеет годовую зарплату M.
В настоящее время компания располагает штатом, состоящим из семи старших инженеров и четырех младших инженеров.
| Engineers | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
| S | 1 | 1 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | 1 | 0 |
| JJ | 0 | 0 | 1 | 1 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
| M | 50000 | 45000 | 30000 | 35000 | 28000 | 58000 | 36000 | 55000 | 35000 | 50000 | 33000 |
Каждый инженер, будь то старший или младший, подходит для каждого из проектов, в зависимости от их подготовки. Эта пригодность измеряется в виде непрерывного индекса от 0 (нет) до 1 (оптимально).
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
| 1 | 0 | 1 | 0.5 | 0.5 | 0.5 | 1 | 0.3 | 0.2 | 0.4 | 0.8 |
| 2 | 0.5 | 0.5 | 1 | 0.3 | 0.2 | 0.4 | 1 | 1 | 0 | 0 |
| 3 | 1 | 1 | 0 | 0 | 1 | 0 | 0.4 | 0.5 | 0.6 | 0.5 |
| 4 | 2 | 0.5 | 0.5 | 1 | 0.3 | 0.2 | 0.4 | 2 | 0.3 | 0.5 |
| 5 | 0.5 | 1 | 0.3 | 0.2 | 0.4 | 1 | 1 | 1 | 0.3 | 0 |
| 6 | 0.2 | 0.5 | 0.5 | 3 | 0 | 0 | 1 | 1 | 1 | 0.6 |
| 7 | 1 | 0.6 | 0.7 | 0.5 | 0.5 | 1 | 0.3 | 0.2 | 0.4 | 0.6 |
| 8 | 1 | 3 | 3 | 3 | 0.5 | 1 | 0.3 | 0.2 | 0.4 | 1 |
| 9 | 0 | 1 | 1 | 0.5 | 0.5 | 1 | 0.3 | 0.2 | 0.4 | 0.1 |
| 10 | 0.5 | 1 | 0.3 | 0.2 | 0.5 | 1 | 0.3 | 0.2 | 0.4 | 1 |
| 11 | 0.5 | 1 | 0.3 | 0.2 | 0.5 | 1 | 0.3 | 0.2 | 0.4 | 1 |
Компания имеет возможность нанимать новых инженеров.
Затраты, которые компания оценивает для найма новых сотрудников, следующие
следующим образом:
- Старший инженер: $50 000/год
- Младшие инженеры: $35 000/год
Для новых инженеров компания присваивает пригодность 75% старшим инженерам и 50% младшим, так как персонал будет подбираться в соответствии к проектам.
Существует два типа назначений для инженеров:
- частичная занятость
- полный рабочий день
Компания позволяет назначить инженера на неполный или полный рабочий день на проекты. Если он работает полный рабочий день, он может быть занят только в одном проекте.
Если неполный рабочий день — может быть максимум в двух.
Новые инженеры могут быть назначены только эксклюзивно.
На проекте затраты на зарплату инженера, назначенного на неполный рабочий день, будут составлять половину ее оклада.
Количество инженеров, необходимых проекту, всегда является величиной, предполагающей исключительности.
Если инженеры назначены на неполный рабочий день, то два инженера на неполный рабочий день считаются как
один инженер.
Компания хочет, чтобы
- в каждом проекте, в котором она участвует, был как минимум один старший инженер (новый или уже работающий) на полную ставку.
- общая пригодность инженеров, назначенных на проект, была выше 50% — расчет общей пригодности производится как сумма пригодности инженеров, назначенных на проект, деленная на количество назначенных инженеров, независимо от того, работают ли они неполный или полный рабочий день.
Помимо всего этого, существуют и другие спецификации:
- В проекте не должно быть более трех инженеров, работающих неполный рабочий день.
- Проекты 5 и 6 не могут иметь ни одного общего инженера в этих двух проектах.
- Участие в проекте 2 на неполный рабочий день требует участия в проекте 3.
Цель компании — максимизация прибыли: «Доход от проектов» - «Расходы» (расходы на заработную плату + общие расходы).
Пусть имеется группа из n=20 человек, с которыми мы собираемся создать m=5 рабочих групп. (эксперты-политики создающие новые законы, ученые, инженеры и т.п.).
У нас есть 10 дисциплин-предметов (научные дисциплины, технологии, законы, …), а насколько каждый человек хорош в каждой дисциплине, задается индексом компетентности ([0…1]),
и все это формирует матрицу
1 0.1 0.3 0.5 0.7 0.8 0.4 0.9 1 1 0 1 0 1 0 0 0.4 0.1 0.1 0.8 0 0 1 0 1 0.6 0.4 1 0 0 1 0.1 0.3 0.5 0.7 0.8 0.4 0.9 1 1 1 0 1 0 1 0 1 0 0 0 1 0 0 1 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 0 1 0.9 1 1 1 1 1 1 0 0 0 0.7 1 0 0.7 0 0 0 1 0 1 0 0 1 0 0 0 0 0 1 1 0 0 1 0 1 0 0 1 0 0 1 0 1 0 1 0 0 0 0 0.7 0 1 0 1 0.3 0 1 0 0 0 1 0 1 0 1 0 0 1 1 0 0.7 0 0 1 0 1 0 0 0 0 0 0 0 0 1 0 1 0 1 1 1 0 0 0 0 0 0 0 0 0.6 0.6 1 0 0 1 0 1 0 0 0 0 0 0.7 0 0 1 0 1 0 0 0 0.7 0 0 0 1 0 0 1
Каждая группа имеет ограничение на минимум и максимум людей
Группа 1 2 3 4 5 Минимум 2 2 5 3 5 Максимум 7 8 7 6 10
- В каждой группе нужно работать над двумя предметами.
- Каждый предмет, должен изучаться по крайней мере в одной группе
- Если индекс компетентности кого-то в предмете меньше 0.5, он не может входить в рабочую группу, которая этим занимается.
- Предметы, которые изучает группа, должны быть совместимы («нет конфликта интересов», «техника безопасности» … )
1 1 0 0 0 1 1 0 1 1 1 1 0 1 1 0 1 0 0 1 0 0 1 0 1 0 1 0 1 1 0 1 0 1 1 1 1 0 1 1 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 1 0 1 0 1 1 1 0 1 0 1 1 0 1 1 0 0 1 0 0 0 0 1 0 0 1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 0 1 0 0 1
Цель формирования групп — максимизировать общую компетентность — сумма индивидуальных компетентностей тех, кто в группе, по дисциплинам, изучаемым в группе — и так по всем группам.
Задача зарезервирована: Sanya 17:03, 16 ноября 2023 (UTC)
Задача зарезервирована: Bagurgl 13:30, 7 ноября 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 учеников.
- В каждой группе по возможности нужно поместить ученика с «блестящей» оценкой.
- Если в группе нет «блестящих», в ней должно быть по крайней мере, не меньше отличников, чем и в любой группе с «блестящими».
- У группы есть «уровень» , где
x_{ij} — число студентов «уровня i» назначенных в группу «j» — мы, оптимизаторы, работаем только с «уровнями» и «группами», не с отдельными студентами.
Цель состоит в том, чтобы сбалансировать уровень оценок групп, чтобы разница минимального и максимального «уровня» у групп было минимальным.
Задача зарезервирована: Serj964 17:32, 29 ноября 2023 (UTC)
Компания рассматривает возможность производства трех своих продуктов P1, P2 и P3 в каждом из мест U1, U2 и U3.
При производстве каждого продукта образуется объем загрязнения в объеме 0,5, 2 и 1 см3, соответственно, на единицу произведенной продукции, независимо от местоположения.
В таблице показаны для каждого из мест:
- удельный доход ($) от каждого продукта,
- суточная производственная мощность (единиц).
- дневная производственная мощность (единиц),
- максимальные объемы загрязнения (см3),
- штраф за превышение объема загрязнения ($/см3).
Компания, осознавая экологические проблемы, предлагает цели с порядком приоритетов:
- Приоритет 1. Максимизировать ежедневный доход.
- Приоритет 2. Не превышать максимальный уровень загрязнения местности.
- Приоритет 3. Компания не хочет тратить более $9000 в день из-за превышения уровня загрязнения.
Давайте сформулируем модель, которая позволит нам определить, сколько ежедневных единиц каждого продукта должно быть произведено и в каком месте.
Долгосрочный план выработки электроэнергии учитывает график работы существующих энергоблоков и график установки новых электростанций для удовлетворения спроса на электроэнергию в течение ряда будущих (5) лет при минимально возможных затратах.
- Период планирования; 5 лет
Потребность в электроэнергии описывается кривой продолжительности нагрузки (LDC), как показано на рис (цифры на картинке приблизительны, точные будут дальше текстом), по оси ординат — мегаватты, по оси абсцисс — часы.
Площадь под графиком соответствует потребностям производства электроэнергии в мегаватт-часах.
Чтобы модель была простой, например линейной, график аппроксимируется кусочно-постоянной функцией, показанной в виде гистограммы (ступенчатой функции), с
- «Bars=4».
- TD — отсечки по горизонтали
2920 3650 1280 910
Первый столбец обозначает минимальную нагрузку, столбец «4» — пиковую нагрузку, а два промежуточных — представляют потребность в средней нагрузке.
В любой компании или стране для производства электроэнергии используется несколько различных типов (n=5) технологий, таких как
- паровые турбины
- газовые турбины
- гидроэлектростанции
- дизель-генераторы
- комбинированные генераторы
Эти энергоблоки требуют различных затрат, затрат на установку и переменных затрат, и переменная по времени генерации (что-то ломается, что-то амортизируется, что-то улучшается).
- ; — планируемые мощности существующих генерирующих типов по времени.
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
- ; Переменная (на мегаватт) годовая стоимость старой установки типа «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», она будет существовать в системе до истечения технического срока службы этой установки (Это потому, что продолжительность горизонта планирования, рассматриваемого в этой задаче, короче, чем технический срок службы любого нового энергоблока, доступного на рынке).
- ; Фиксированная годовая стоимость новой установки типа «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 ~
- ; Фиксированная годовая стоимость новой установки типа «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)
[ Хронологический вид ]Комментарии
Войдите, чтобы комментировать.