pulpでスケジューリング

Question

前提・実現したいこと

ある企業で各社員について出社したときと休んでいる時の業務が与えられているとして、会社の業務が最大化するような問題を実装してみたいと思っています。
制約として
・各社員が5日以上は出社する
・一日に4人以上は出社する

発生している問題・エラーメッセージ

エラーメッセージは出ないですが、値が出力されません。

該当のソースコード

import pulp
import sys
import numpy as np

#オフィスワークの業務効率
o=[2,5,2,3,6,7,8,65,4,7,2]
#テレワークの業務効率
r=[1,4,2,3,2,7,8,6,4,7,10]
#交通費
c=[603,400,603,909,703,200,307,400,077,1102,602,360,520,2208]

#従業員数
employee_num = 10
weekday_num = 7

data = []
for i in range(employee_num):
    data += [[o[i],r[i],c[i]]]

print(data)
cc = []
owc = []
odc = []

def main():  
    problem = pulp.LpProblem("miximize", pulp.LpMaximize)

    variable = [[None for _ in range(weekday_num)] for _ in range(employee_num)]
    for i in range(employee_num):
        for d in range(weekday_num):
            variable[i][d] = pulp.LpVariable(f"x({i},{d})",0 ,1,pulp.LpInteger)
            
    efi = None
    for i in range(employee_num):
        for d in range(weekday_num):
            efi += variable[i][d] * data[i][0] + (1 - variable[i][d]) * data[i][1]

    problem += efi # 目的関数
    cc = [0,0,0,0,0]
    owc = [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
    odc = [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
    # 制約1本目
    
    for d in range(weekday_num):
        for i in range(employee_num):
            cc[d] += variable[i][d] * data[i][2]            
        problem += cc[d] <= 5000
    
    # 制約2本目
    
    for i in range(employee_num):
        for d in range(weekday_num):
            if variable[i][d] == 1:
                owc[i] += 1            
        problem += owc[i] >= 2
    
    # 制約3本目 

    for d in range(weekday_num):
        for i in range(employee_num):
            if variable[i][d] == 1:
                owc[d] += 1            
        problem += odc[d] >= 2
    
    print(problem)
    status = problem.solve()
    print(status)
    print("Obj.value", problem.objective.value())


if __name__=="__main__":
    main()

試したこと

出社なら1、リモートなら0の関数がうまく言っていないのかなと感じましたが、修正の見当がつきませんでした。

補足情報（FW/ツールのバージョンなど）

Python3.7
Jupyter Notebook 6.0.3

Answer 1

不具合の原因は単純に３つ目の制約において

odc[d] += 1

とするべき箇所を

owc[d] += 1

とした事かと思います。

あとはもう一箇所気になるところは、交通費は（多分）10円単位でデータを保持しているにも関わらず、

cc[d] <= 5000

と計算しているところ。ここは

cc[d] <= 500

となるのではないでしょうか。
あと合計を求める箇所を lpSum() を使うように修正すると以下のようになります。

import pulp
import sys
import numpy as np

#オフィスワークの業務効率
o=[1, 5,2,6,7,32,7,45,7,9,0,8,7,6,4,3,2,]
#テレワークの業務効率
r=[1, 3, 3, 5, 9, 7, 3, 9, 10, 4, 8, 7, 9, 2, 10, 9, 5, 4, 1, 9]
#交通費
c=[63,4,63,99,73,20,37,40,77,112,62,36,52,22,9,6,51,76,219,118]

#従業員数
employee_num = 10
weekday_num = 5

data = []
for i in range(employee_num):
    data += [[o[i],r[i],c[i]]]

print(data)
cc = []
owc = []
odc = []

def main():  
    problem = pulp.LpProblem("miximize_business_efficiency", pulp.LpMaximize)

    variable = [[None for _ in range(weekday_num)] for _ in range(employee_num)]
    for i in range(employee_num):
        for d in range(weekday_num):
            variable[i][d] = pulp.LpVariable(f"x({i},{d})", cat="Binary")

    efi = None
    for i in range(employee_num):
        for d in range(weekday_num):
            efi += variable[i][d] * data[i][0] + (1 - variable[i][d]) * data[i][1]

    problem += efi # 目的関数
    cc = [0,0,0,0,0]
    owc = [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
    odc = [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
    
    # 制約：１日の交通費は5000円以下とする
    for d in range(weekday_num):
        cc[d] = pulp.lpSum(variable[i][d] * data[i][2] for i in range(employee_num))
        problem += cc[d] <= 500

    # 制約：１人２日以上出社
    for i in range(employee_num):
        owc[i] = pulp.lpSum(variable[i][d] for d in range(weekday_num))
        problem += owc[i] >= 2

    # 制約：１日２人以上出社
    for d in range(weekday_num):
        odc[d] = pulp.lpSum(variable[i][d] for i in range(employee_num))
        problem += odc[d] >= 2

    print(problem)
    status = problem.solve()
    print(status)
    print("Obj.value", problem.objective.value())

    result = [[variable[i][d].varValue  for d in range(weekday_num)] for i in range(employee_num)]
    print(result)

if __name__=="__main__":
    main()

Comments

[退会済みユーザー]

まさに実装してみたいことができました。
本当にありがとうございました！
これからも色々と試してみます！