Открытые бизнес-задачи

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

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

----


Игра UnblockMe 2022-11-22 02-31-00 image0.png

Опишем игру «Разблокируй меня» (Kira Games 2021) — это игра-головоломка, представляющая собой поле, состоящее из нескольких столбцов и рядов.

  • Блоки располагаются по горизонтально или вертикально;
  • Горизонтальный блок может двигаться только вправо и влево;
  • Вертикальный блок может двигаться только вверх и вниз.
  • Вы должны переместить их таким образом, чтобы освободить путь для красного блока.
  • Количество рядов NF=6
  • Количество столбцов равно NС=6.
  • В этих рядах и столбцах размещается ряд блоков, которые мы будем называть препятствиями, и которые могут быть горизонтальными или вертикальными.
  • Горизонтальные блоки размещаются в ряд и могут быть перемещены только в пределах этого ряда (перемещение вправо и влево).
  • Вертикальные препятствия могут перемещаться только в пределах столбца, к которому они относятся (перемещение вверх и вниз).

С другой стороны, у нас есть красный блок; это горизонтальный блок, расположенный в определенном ряду (ряд 3 на оригинальной игровой панели) и поэтому перемещается только по горизонтали.

В конце этого ряда на доске есть выход.

Наша задача — убрать красный блок с доски.

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

Мы создадим модель, математически представляющую игру с двумя сценариями:

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

Не готово, нужно дорабатывать




У нас есть группа из 60 экскурсантов, которые наняли услуги компании автобусных туров на следующие 3 дня.

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

Вот, какие экскурсии выбрал каждый экскурсант:


  • Автобусы компании имеют вместимость (количество мест). У компании 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 дня, чтобы использовать наименьшее количество автобусов

(минимизируем «автобусо-дни»).

    • При этом нужно найти назначение экскурсий и экскурсантов на рейсы автобусов




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

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

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

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




В данном городе имеется 52 аптеки, распределенные по 5 районам (j = 1. . .5).

Аптеки бывают двух типов:

  • Обычные (0): Открытие и закрытие в обычные часы, не работают в выходные.
  • Аптеки 12 ч (1): Открыты каждый день в году до 22:00.
Аптека 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 41 42 43 44 45 46 47 48 49 50 51 52
Тип 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 1
Район 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5

Есть годовой календарь праздничных дней:

Когда аптеки не работают, их надо охранять, наркоманы не дремлют.

Вооруженных охранников аптеки нанять не могут, их выделяет муниципалитет.

Существует два типа охранников:

  • Дневной: 9:00-21:00, для выходных-праздничных дней — работают только днем, в выходные.
  • Ночной: 21:00-9:00, работают каждый день.

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

Район 1 2 3 4 5
Дневных охранников 2 2 1 1 2
Ночных охранников 2 1 1 1 1


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

  • Обычная аптека не может охраняться более 24 часов подряд.
  • Любая аптека не может охраняться два выходных подряд.
  • Разница в ежемесячном количестве караулов в каждой обычной аптеке не может быть быть больше трех.
  • Разница в общем числе караулов всех охранников в для каждой аптеки не превышает двух единиц.

Округи ревниво следят за «Y_j» — количеством ночных охранников аптек, деленное на количество аптек в его округе «j».

Надо минимизировать разницу между «Y_j», соблюдая вышеуказанные регуляции.

Не готово, проблемы с решением



Иголка в стоге сена 2022-11-18 11-39-49 image0.png

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

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

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


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

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

Иголка в стоге сена 2022-11-18 11-45-09 image0.png

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




Задача Штейнера о минимальном дереве.

Т.е. у нас есть неориентированный граф, где

  • N=74 узлов, узлы графа двух типов:
Терминальные
Они должны быть частью сети.
Штейнера
Не обязательно, чтобы они были частью сети.
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 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74
Терминальный? 0 0 0 0 0 0 0 0 0 1 1 1 0 1 0 0 0 1 0 0 0 1 0 0 0 0 1 0 1 1 0 0 1 0 0 1 1 1 0 0 0 0 0 0 1 1 1 1 0 0 1 0 0 0 1 0 1 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0
  • M=153 неориентированных ребер в весом-стоимостью, которых мы представим 306 двойными дугами, ребро (i, j, w) → в ребро i→j (w) и ребро j→i (w)

Надо найти подграф минимальной стоимости, соединающий все терминальные узлы.




Есть некий регион, с 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, можно поставить два учреждения.

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

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

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





В университете «Синергия» собираемся ежедневноЧтобы упростить размер модели, мы рассматриваем один день преподавания предмета преподавать 150 предметов.

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

Расписание предметов уже составлено (как было удобно лекторам), и чтобы не возится с временами начала-окончания, получим сразу важные для нас данные — какой предмет пересекается по времени с каким (не может быть одновременно).

Аудитории мы арендуем в огромном бизнес-центре (неисчерпаемом, «Бесконечный Замок»©), где есть аудитории двух размеров

  • Большие, на 100 человек, стоимость $25 в день
  • Малые, на 50 человек, стоимость $10 в день.

Стоимость аренды в день — т.е. можно в каждую аудиторию внести все «непересекающиеся» занятия (день тоже «растяжимый»).

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

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




Школа хочет спланировать распределение внеклассных занятий среди учащихся. Предлагаются следующие виды деятельности (8 активностей, 12 групп):

  • Гимнастика (две группы)
  • Музыка (одна группа)
  • Баскетбол (две группы)
  • Ремесла (одна группа)
  • Рисование (одна группа)
  • Английский язык (две группы)
  • Французский язык (одна группа)
  • Футбол (две группы)

Отображение групп на активности

 A_k = 1 1 2 3 3 4 5 6 6 7 8 8 

Максимум учеников в каждой группе:

 M = 10 10 10 10 10 10 10 10 10 10 12 12

100 учеников уже запросили различные активности, не зная о расписании:

Занятия проводятся в течение 1 часа

  • в понедельник, вторник, среду и четверг.
  • в слоты «с 4 до 5 часов», «с 5 до 6» или «с 6 до 7 часов» пополудни — 3 слота в день, всего 12 слотов (h).

Для моделирование конкретное время неважно, т.е. есть 4 дня, и 12 часовых слотов, которые так отражаются на дни:

 D_h = 1 1 1 2 2 2 3 3 3 4 4 4

Расписание занятий уже фиксировано, матрицей 12×12.

P_kh=1 0 0 0 0 0 1 0 0 0 0 0
     0 1 0 0 0 0 0 1 0 0 0 0
     0 0 1 0 0 0 0 0 1 0 0 0
     0 0 0 1 0 0 0 0 0 1 0 0
     0 0 0 0 1 0 0 0 0 0 1 0
     0 0 0 0 0 1 0 0 0 0 0 1
     1 0 0 0 1 0 0 0 0 1 0 0
     0 1 0 0 0 1 0 0 0 0 1 0
     0 0 1 0 0 0 1 0 0 0 0 1
     0 0 1 0 0 0 1 0 0 0 0 0
     0 0 1 0 0 0 1 0 0 1 0 0
     0 0 0 0 1 0 0 0 0 0 1 0

Есть мероприятия с двумя группами. У каждой группы свое расписание и свое максимальное количество студентов.

Мы собираемся распределить группы мероприятий ученикам с целью максимизации суммы мероприятий, которые

назначены общему числу студентов, принимая во внимание, что:

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




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

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

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

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

Управление загрязняющими продуктами 2022-11-17 16-03-02 image0.png

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

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

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




Есть неориентированный граф, список ребер…

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




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

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

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

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

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

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




Компания имеет два завода, на которых производятся единицы ее продукции.

Каждый завод i имеет

  • ежедневную производственную мощность K(i) единиц продукции
  • небольшой склад, емкостью FA(i)
Factories
IdFAK
120,0005,000
225,0003,500

Предположим, что для производства требуется L=5 рабочих дней в неделю.


Еще у компании есть два склада-хаба, откуда произведенная продукция рассылается потребителям. У каждого склада j есть

  • Вместимость Aj
  • Способность ежедневной отгрузки Ej
Hubs
IdAjEj
110,0005,000
250,0004,000



Есть


Между потребителями, фабриками и хабами есть расстояния:

Фабрика-Хаб
Distance_F_H
HubDistanceFactory
11501
24001
135002
21002


хаб-хаб
Distance_H_H
Hub2DistanceHub1
25001
15002

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

Производство и распределение 2022-11-17 15-17-39 image0.png

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

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




Плантатор планирует оптимальные посадки сельхоз культур на своих участках.

Он владеет N=20 участками с площадями (м²)

 800 700 800 1000 5000 10000 4000 25000 40000 10000 5000 10000 4000 25000 40000 5000 10000 4000 25000 40000

Участки могут граничить, и это выражается матрицей

1 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 1
0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 0 1 0 0 1 0 0 1 0 0 1 0 0 0 0 0 0
0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0
0 0 0 0 0 1 0 0 0 1 0 1 0 1 0 0 1 0 0 1
0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 1 0
0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 0 0 0
0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 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 0 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 0 0 0 0 0 0 0 0 1 0 0
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 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 

Он может посадить 4 культуры (пшеницу, кукурузу, овес и оливки). Есть

  • минимальный план посадок,
  • есть доход/выручка на каждый квадратный метр для каждой культуры,
  • есть фиксированные затраты на засев культурой любого участка
Культура (i) Необходимо посадить D_i м² Выручка на м² Фиксированные затраты на участок
пшеница 50000 100 40
кукуруза 20000 200 10
овес 30000 150 15
оливки 20000 200 20

И, в зависимости от участка, есть переменные затраты на квадратный метр каждой культуры

10 12 14 13 14 15 17 13 12 10 10 12 11 9 8 7 9 5 6 7 
7 7 7 7 8 8 9 9 10 5 5 5 5 9 8 7 9 5 6 7 
12 11 9 8 7   9 5 6 7 8  12 14 13 14 15   17 13 12 10 10 
6 12 14 13 14  15 17 13 12 10  10 12 11 9 8  7 9 5 6 7  ~

И ограничения хитрой агрикультурной магии:

  • Каждый участок можно
    • не засевать
    • либо засевать максимум двумя культурами.

Но

  • Пшеницу нельзя совмещать на участке с другими культурами.
  • Нельзя растить на одном и даже соседних участках
    • кукурузу и пшеницу
    • курурузу и овес

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




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

25 из них продаются килограммами, KS — запасы этих продуктов на складе:


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
KS 200 300 500 400 300 500 350 550 350 330 400 400 450 500 500 300 200 200 120 120 200 300 400 500 500

а KV — объем каждого килограмма продукта:



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
KV 10 25 32 45 40 20 20 20 30 32 33 45 54 10 20 30 10 30 40 10 20 20 30 30 30


Остальные 20 товаров продаются единицами, их запасы на складе US:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
US 300 250 250 500 450 400 150 240 260 450 340 340 500 500 400 400 300 300 200 300


А объем каждого штучного товара — UV:


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
UV 10 20 10 15 15 20 30 30 35 45 14 13 12 10 20 20 15 20 20 10


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

  • есть четыре модели коробок, каждая с определенным объемом.
  • имеется достаточный запас коробок любой модели.

1 2 3 4
V 200 300 400 500

Мы получили 100 заказов, в каждом из которых заказано определенное количество килограмм каждой позиции весового товара:

И также, матрица заказов штучных товаров:

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

Целевая функция — минимизация суммы объема отправленных коробок плюс штраф в десятикратном размере за объем оставшихся на складе товаров.




Дан неориентированный граф G (N, E), надо получить множество с наибольшим числом несвязанных ребер (два ребра соединяются, когда они разделяют узел).


Независимое множество ребер 2022-10-21 16-18-00 image0.png




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

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

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

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

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

Портфель ценных бумаг 2022-10-21 13-05-06 image0.png

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

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

таких как:

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

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


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

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

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