具有约束的资源分配算法

问题描述 投票:0回答:1

我知道我的问题存在一些算法,但我在命名它和解决方案时遇到了问题。这是我的问题:

  • 我有一套带钱的W钱包
  • 我有一套项目,我可以花我的钱
  • 每个钱包都有M金额,我只能将这笔钱花在几个项目上,而且只需要一定的金额
  • 每个项目p都需要一笔钱

目标:最大限度地分配我的钱包资金,这样我就可以资助我的大部分项目。

此外,我宁愿让我的所有项目资助比例为95%,而不是让一些项目资助100%,其他项目资助0%。

所以我想最小化的功能是所有的总和(d-(分配给这个项目的所有资金))²假设我没有足够的资金来资助我的所有项目

示例:

我的第一个钱包里有100欧元,我可以在项目1上花费70%,在项目3上花费20%,在项目3上花费10%

我有200欧元我的第二个钱包,我可以在项目1上花费30%,在项目2上花50%,在项目3上花费20%。

关于我的项目:

  1. 项目1至少需要120欧元
  2. 项目2至少需要100欧元
  3. 项目3至少需要110欧元

谢谢你的帮助 !

algorithm resources allocation schedule
1个回答
1
投票

您可以将此表示为最大流量问题。将源顶点连接到与钱包对应的顶点,其中每个弧的容量是钱包中的金额。将与项目对应的顶点连接到汇点顶点,其中每个弧的容量是该项目所需的金额。将钱包连接到具有弧形的项目,弧形的容量反映了该钱包可以在该项目上花费的金额。

处理分段二次目标有点棘手。幸运的是,它是凸的,所以我打赌你可以使用二次程序求解器来达到良好的效果。

© www.soinside.com 2019 - 2024. All rights reserved.