Зарезервированные практические задачи
Всего страниц найдено: 12.
----
Докажите, что для каждого целого числа n существует раскраска ребер полного графа
Задача зарезервирована: StasFomin 11:32, 19 мая 2023 (UTC)
- Константа k≥2, множество переменных U,
- Коллекция C скобок-дизъюнкций литералов, где литерал это какая-то переменная или ее отрицание, размер скобки не больше k.
- Найти истинное присваивание для U.
- Минимизировать число выполненных скобок.
Задача в лаб17 (рид-онли просмотр)
- Задача в базе NP-полных задач Вигго Кана
- Код задачи в книге «ГД» → «LO2»
Задача зарезервирована: Abel1502 09:57, 25 мая 2023 (UTC)
- Константа k≥2, множество переменных U,
- Коллекция C скобок-дизъюнкций литералов, где литерал это какая-то переменная или ее отрицание, размер скобки не больше k.
- Найти истинное присваивание для U.
- Максимизировать число выполненных скобок.
Задача в лаб17 (рид-онли просмотр)
-
— есть тестовые данные и визуализация.
-
— есть Pyomo-формулировка для ЦЛП.
-
— есть сведение на Python NP-полной задачи к данной.
- Задача в базе NP-полных задач Вигго Кана
- Код задачи в книге «ГД» → «LO2»
- Код задачи в книге «ГД» → «LO5»
Задача зарезервирована: Abel1502 08:50, 11 мая 2023 (UTC)
- Набор задач T, m процессоров, время выполнения
l(t,i)∈ Z^+, \ \ ∀t∈ T, \ i∈ [1..m] . - Найти m-процессорное расписание для T, т.е. функцию
f: T→ [1..m] . - Минимизировать время выполнения расписания, т.е.
\max\limits_{i∈ [1..m]}\displaystyle\sum\limits_{t∈ T: \atop f(t)=i} l(t,i) → min
Задача в лаб17 (рид-онли просмотр)
- Задача в базе NP-полных задач Вигго Кана
- Код задачи в книге «ГД» → «SS8» (обобщение)
Задача зарезервирована: JulesIMF 15:31, 28 мая 2023 (UTC)
- Три множества X, Y, W и функция стоимости c: X×Y×W → N
- Найти назначение A, т.е. подмножество A ⊆ X×Y×W, такой что каждый элемент из
X ∪ Y ∪ W принадлежит только одной тройке из A. - Минимизировать стоимость назначения, т.е.
\sum_{(x,y,w) ∈ A}c(x,y,w) → \min
Задача в лаб17 (рид-онли просмотр)
- Задача в базе NP-полных задач Вигго Кана
- Код задачи в книге «ГД» → «SP2» (взвешенная версия)
Задача зарезервирована: Krym4s 15:55, 9 мая 2023 (UTC)
- Коллекция C подмножеств конечного множества S.
- Найти покрытие множества S, на т.е. подмножество C'⊆ C, такое, что для каждый элемент из S принадлежит по крайней мере одному подмножеству из C'.
- Минимизировать суммарных объем покрывающих подмножеств, т.е.
\sum\limits_{c\in C'} |c| → \min
Задача в лаб17 (рид-онли просмотр)
-
— есть тестовые данные и визуализация.
-
— есть Pyomo-формулировка для ЦЛП. 📹 видео 📹
-
— есть сведение на Python NP-полной задачи к данной. 📹 видео 📹
-
Можно доработать — сделать Вероятностное тестирование NPC-сведения!
Задача зарезервирована: Анна Савчук 12:55, 25 апреля 2023 (UTC)
- Коллекция C подмножеств конечного множества S.
- Найти разбиение S, на непересекающиеся множества S1 и S2.
- Максимизировать число подмножеств C, которые «разделены» между S1 и S2, т.е. не лежат полностью в S1 или S2.
Задача в лаб17 (рид-онли просмотр)
-
— есть тестовые данные и визуализация.
-
— есть Pyomo-формулировка для ЦЛП. 📹 видео 📹
-
— есть сведение на Python NP-полной задачи к данной. 📹 видео 📹
-
Можно доработать — сделать Вероятностное тестирование NPC-сведения!
- Задача в базе NP-полных задач Вигго Кана
- Код задачи в книге «ГД» → «SP4»
- Задача в википедии
Задача зарезервирована: Ilya 16:25, 2 мая 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 (рид-онли просмотр)
Задача зарезервирована: StasFomin 21:17, 26 апреля 2023 (UTC)
- Граф G=(V,E).
- Найти разбиение V на непересекающиеся множества V1 и V2.
- Максимизировать размер разреза, т.е. число ребер, в которых один конец в множестве V1, а другой конец в V2.
Задача в лаб17 (рид-онли просмотр)
-
— есть тестовые данные и визуализация.
-
— есть Pyomo-формулировка для ЦЛП. 📹 видео 📹
- Задача в базе NP-полных задач Вигго Кана
- Код задачи в книге «ГД» → «ND16»
Задача зарезервирована: Artklyachin 14:06, 18 мая 2023 (UTC)
Долгосрочный план выработки электроэнергии учитывает график работы существующих энергоблоков и график установки новых электростанций для удовлетворения спроса на электроэнергию в течение ряда будущих (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)
[ Хронологический вид ]Комментарии
Войдите, чтобы комментировать.