如何划分带约束的饼

Question

如何划分带约束的饼？

嗨，我有圆圆的派，想分给它，但是我想不出怎么做。

我有四个朋友: A，B，C，D我想根据我的喜好来划分派，所以根据意见。

1. 切片大小：

A= 1/22派B= 10/22派C= 1/22派D= 10/22派

当有一些约束时，如何划分馅饼？就像B会告诉我，他想要整个馅饼的10%，而D必须至少有85%的馅饼。A，C不在乎。

在这种情况下，我可以说，好的，所以D需要至少85%的22*0.85= 18.7，所以他会得到这个。现在我只有剩下的22-18.7= 3.3 = 15%可以除以，我不想给比10%更大的比例给B，我仍然想应用我提议的比率，但只适用于饼的其余部分，因为D必须至少有85%。

我认为在解决了限制后，现在应该采用这些比率。

A has no constraint so he can get from 0-100%
B wants 0-10%
C has no constraints 0-100%
D wants at least 85-100%

当B想要0-10%时，我可以在约束条件下将比例应用到切片上，然后我可以说比率对0-10%之间的大小有影响，对于D，该比率将影响大小(85%-100%)。

|   friends: |    A   |    B     |     C     |   D    |
|constraints:|        |  <=0.1   |  >=0.85   |        |
|ranges:     | 0 to 1 | 0 to 0.1 | 0.85 to 1 | 0 to 1 |
|ratios:     |  1/22  |  10/22   |   1/22    | 10/22  |

希望问题是可以理解的。最后，我希望在ABCD中分配整个饼，不违反约束，并以某种方式应用比率。

Answer 1

让我把这个问题形式化为二次规划。让x是所需的结果。我们希望将x/ratio (Element Wise)的L2范数降到最小，条件是x·1 = 1，且受下≤x≤上(Element Wise)的约束。

这一目标背后的思想是，通过考察最优性条件，我们可以证明存在一些标量z，使得x = ratio z， by )。

下面是一些测试非常糟糕的Python 3代码，可以近似地解决这个二次型程序。

from fractions import Fraction


ratio = [1, 10, 2, 10]
lower = [0, 0, 0, 85]
upper = [100, 10, 100, 100]
# Want to minimize the L2 norm of x / ratio subject to lower <= x <= upper and
# sum(x) == 100

# Validation
assert 0 < len(ratio) == len(lower) == len(upper)
assert all(0 < r for r in ratio)
assert all(0 <= l <= u <= 100 for (l, u) in zip(lower, upper))
assert sum(lower) <= 100 <= sum(upper)

# Binary search
n = len(ratio)
critical = sorted(
    {Fraction(bound[i], ratio[i]) for bound in [lower, upper] for i in range(n)}
)
a = 0
b = len(critical)
while b - a > 1:
    m = (a + b) // 2
    z = critical[m]
    if sum(sorted([lower[i], ratio[i] * z, upper[i]])[1] for i in range(n)) <= 100:
        a = m
    else:
        b = m

x = [0] * n
z = critical[a]
divisor = 0
for i in range(n):
    value = ratio[i] * z
    if value < lower[i]:
        x[i] = lower[i]
    elif upper[i] <= value:
        x[i] = upper[i]
    else:
        divisor += ratio[i]
dividend = 100 - sum(x)
for i in range(n):
    if lower[i] <= ratio[i] * z < upper[i]:
        x[i] = Fraction(ratio[i], divisor) * dividend
print(x)

输出：

[Fraction(5, 3), 10, Fraction(10, 3), 85]