有限制的资金分配

Question

我试图解决一个问题，即在各种约束条件下确定政府补助金的分配。最好将问题描述为：

政府已决定发放总额为180万美元的财政援助。他们邀请了同样的申请。他们决定了如何分配基金的一些限制条件。制约因素包括：

1. 根据申请人的财务状况可以分配的金额的最大限额

   富=300000

   中产阶级=500000

   差=1000000

2. 可按申请人性别分配的最高金额限制

   男性=800000

   女性=1000000

他们收到了不同组合的申请。政府无法分配申请收到的更多资金

+--------------------+------------------+-----------------------------+------------------------+
| Applicant Category | Applicant Gender | Total Applications Received | Amount to be allocated |
+--------------------+------------------+-----------------------------+------------------------+
| Rich               | Male             | 200,000                     |                        |
| Middle class       | Female           | 400,000                     |                        |
| Middle class       | Male             | 350,000                     |                        |
| Poor               | Female           | 650,000                     |                        |
| Poor               | Male             | 750,000                     |                        |
+--------------------+------------------+-----------------------------+------------------------+

在上面的例子中，有钱男性的申请总数是200000。因此，政府不能为这一类拨款超过20万英镑。如果这有助于增加所有这些行的总支出金额，政府可以分配比这少的资金

中产阶级男性要求总共40万英镑，中产阶级女性要求35万英镑。然而，中产阶级可支付的总金额为50万美元。这意味着它无法完全分配给这些桶，必须满足于更少的需求

中产阶级女性要求40万，贫困女性要求65万。然而，可以在所有女性中分配的总金额是1000000，这意味着这两个桶也不能完全分配

上表中的“分配金额”列是算法必须确定的内容。类似于-可以分配给表中每个条目的最大金额是多少，允许我们总共支付最大金额，这不违反任何限制，“分配金额”金额不应超过“收到的申请总数”

例如，如果我们将700000分配给贫困男性，那么它需要从男性和贫困类别中扣除。分配700000给贫困男性后，男性剩余金额为100000（800,00-700000），贫困男性剩余金额为300000（1000000-700000）。现在，对其他条目的后续分配必须考虑修改后的约束条件，并确保不违反限制

其目的是确定政府可分配给各类别和性别组合的金额，以最大限度地提高支付总额

我对线性规划有点陌生，但是通过阅读在线帮助，我可以确定我可以对每个类别单独施加的约束

x (rich) <= 300,000
y (middle class) <= 500,000
z (poor) <= 1,000,000
p (male) <= 800,000
q (female) <= 1,000,000

不过，我无法就政府收到的申请制订限制。例如，富人男性收到的200000份申请并不转化为（x+p）<；=二十万

Answer 1

我们可以用线性方程的形式表述上述问题，如下所示：

Let Rm = Rich Male
    Rm = Rich Female 
    Mm = Middleclass Male
    Mf = Middleclass Female
    Pm = Poor Male
    Pf = Poor Female

目标：Maximize: Rm + Rf + Mm + Mf + Pm + Pf

受以下约束：

1) Rm + Rf <= 300,000
2) Mm + Mf <= 500,000
3) Pm + Pf <= 1,000,000

4) Rm + Mm + Pm <= 800,000
5) Rf + Mf + Pf <= 1,000,000

6) Rm <= 200,000
7) Mm <= 350,000
8) Pm <= 750,000
9) Rf <= 0
10) Mf <= 400,000
11) Pf <= 650,000

约束6-11可以根据输入数据进行更改
解决这个问题，我们得到：

Rm = 200,000
Mm = 250,000
Pm = 350,000
Rf = 0
Mf = 250,000
Pf = 650,000

因此，根据给定的数据，总共可以在申请人之间支付1,70,000

Answer 2

代码：

from pulp import *
import pandas as pd

# Problem Data

df = pd.DataFrame({'economic': ['rich', 'middle', 'middle', 'poor', 'poor'],
                   'gender': ['male', 'female', 'male', 'female', 'male'],
                   'received': [200000, 400000, 350000, 650000, 750000]})

max_by_economic = {'rich': 300000, 'middle':500000, 'poor':1000000}
max_by_gender = {'male': 800000, 'female':500000, 'poor':1000000}
max_total = 1800000

# Implementation
prob = LpProblem("allocation", LpMaximize)

alloc_vars = LpVariable.dicts('alloc_vars', df.index)

# Objective
prob += lpSum([alloc_vars[i] for i in df.index])

# Bounds
for i in df.index:
    prob += alloc_vars[i] <= df.received[i]


# Constraints
for status in max_by_economic:
    prob += lpSum([alloc_vars[i] for i in df.index if df['economic'][i] == status]) <= max_by_economic[status]

for gender in max_by_gender:
    prob += lpSum([alloc_vars[i] for i in df.index if df['gender'][i] == gender]) <= max_by_gender


prob += lpSum([alloc_vars[i] for i in df.index]) <= max_total


prob.solve()

# Load results into dataframe                  
df['allocation'] = [alloc_vars[i].varValue for i in df.index]
print(df)

返回：

  economic  gender  received  allocation
0     rich    male    200000    200000.0
1   middle  female    400000    150000.0
2   middle    male    350000    350000.0
3     poor  female    650000    250000.0
4     poor    male    750000    750000.0