algorithm - 使用标准集优化资源分配

Question

一位垂死的父亲对剥离他的属性(property)很感兴趣。他有这样的投资组合:

AAPL : 5,000
MSFT : 10,000
AMZN : 6,000 and etc 

我们知道不同类型股票的数量是有限的，持有的股票总数也是有限的

他有许多遗产受益人，我们不知道这个数字，但我们知道它是有限的。我们知道每个受益人都有不同的要求，要求的数量是有限的。

例如:

Case 1:
    Charity X can only take 3,000 shares of AAPL and 6,000 share of MSFT
    Leftover  : 2,000 shares of AAPL, 4,000 shares of MSFT, 6,000 shares of AMZN

Case 2:
    Charity X can only take 3,000 shares of AAPL and 6,000 share of MSFT
    Charity Y can ony take 1,000 shares of AAPL
    Leftover  : 1,000 shares of AAPL, 4,000 shares of MSFT, 6,000 shares of AMZN

是否有一种算法能够:

• 返回 1 个受益人、或 2 个受益人或 3 个受益人等的最佳股份分配

• 在临终父亲的原始投资组合中剩下的最少 - 如果知道股票要求的类型以及每个受益人对该类型股票的数量限制？

Answer 1

这可以通过某种形式的 linear programming 来解决.

它完全符合线性规划问题的定义:您有一组非负变量:每个人持有的每只股票的数量，包括获得的“剩余”部分。您对它们有一组限制:一个分数可以持有一种类型的最大份额数。你有一个目标函数要最大化!剩余份额的数量应该最小化，即它的负数应该最大化。

我不是财务人员，但我猜你不能持有零星股份。在这种情况下，问题变得更加困难，因为您的所有数字都必须是整数。这就是所谓的“整数线性规划”(ILP)。在许多实际解决方案中，这可以是 NP-hard .但是，如果您的数字不太奇怪，您的实例很可能会得到有效解决。 ILP 求解器也得到了很好的研究，因为很多问题都可以映射到它们。还要检查 this answer在 SO 上。