Алгоритм распределения ресурсов с ограничениями

Question

Я знаю, что существуют некоторые алгоритмы для моей проблемы, но у меня возникают проблемы с ее именованием и связанным решением.Вот моя проблема:

• У меня есть набор W кошелька с деньгами
• У меня есть набор P проекта, на который я могу потратить свои деньги
• Каждыйкошелек w имеет сумму денег M, и я могу потратить эти деньги только на несколько проектов и только на определенную сумму
• Каждый проект p нуждается в сумме денег d

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

Кроме того, я бы предпочел, чтобы весь мой проект финансировался, например, на 95%, чем на 100%% и другие при 0%.

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

Пример:

У меня есть 100 € на мой первый кошелек, и я могу потратить 70% на проект 1, 20% на проект 3 и 10% на проект3

И у меня есть второй кошелек на 200 €, где я могу потратить 30% на проект 1, 50% напроект 2 и 20% и проект 3.

О моих проектах:

1. Проект 1 нуждается как минимум в 120 €
2. Проект 2 нуждаетсяминимум 100 €
3. Проекту 3 нужно минимум 110 €

Спасибо за помощь!

Answer 1

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

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