一般化割当問題

一般化割当問題とは

機械 $i$ が仕事 $j$ を行ったときの負荷 $W_{ij}$ を考える. また, 機械 $i$ には処理能力制限 $R_i$ があるとする。仕事 $j$ を機械 $i$ に割り振った際の利潤を $R_{ij}$ とする。このとき、利潤を最大化するにはどのように割り当てればよいか。

回答例

def GAP(Resource, Profit, Weight):
    m,n = Profit.shape
    lp = pulp.LpProblem(sense=pulp.LpMaximize)
    z =  np.array([pulp.LpVariable("z_{}_{}".format(j,i), cat='Binary') for j in range(m) for i in range(n)]).reshape((3,2))
    for j in range(n):
        lp += pulp.lpDot(Weight[:,j],z[:,j]) <= Resource[j], "resource_{}".format(j)
    for i in range(m):
        lp += pulp.lpSum(z[i]) == 1
    lp += pulp.lpDot(z.flatten(), Profit.flatten())  
    lp.solve()
    print(pulp.LpStatus[lp.status])
    print(np.vectorize(lambda x: x.value())(z))
    for name, c in lp.constraints.items():
        print("name: {}, slack: {}, Dual: {}".format(name, c.slack, c.pi))