import pulp
 
# Data biaya
costs = [
    [45, 50, 55, 60, 65],
    [52, 48, 47, 55, 58],
    [50, 46, 54, 57, 56],
    [47, 53, 51, 49, 59],
    [55, 52, 50, 48, 46]
]
 
# Nama divisi dan proyek
divisions = ['D1', 'D2', 'D3', 'D4', 'D5']
projects = ['P1', 'P2', 'P3', 'P4', 'P5']
 
# Problem
prob = pulp.LpProblem("Assignment_Problem", pulp.LpMinimize)
 
# Variabel
x = pulp.LpVariable.dicts("x", 
                          ((i, j) for i in range(5) for j in range(5)),
                          cat='Binary')
 
# Fungsi objektif
prob += pulp.lpSum(costs[i][j] * x[i, j] for i in range(5) for j in range(5))
 
# Kendala: setiap divisi hanya satu proyek
for i in range(5):
    prob += pulp.lpSum(x[i, j] for j in range(5)) == 1
 
# Kendala: setiap proyek hanya satu divisi
for j in range(5):
    prob += pulp.lpSum(x[i, j] for i in range(5)) == 1
 
# Solve
prob.solve()
 
# Output
print("Status:", pulp.LpStatus[prob.status])
print("Total Biaya Minimum =", pulp.value(prob.objective), "juta\n")
 
print("Penugasan Optimal:")
for i in range(5):
    for j in range(5):
        if pulp.value(x[i, j]) == 1:
            print(f"{divisions[i]} -> {projects[j]} (Biaya: {costs[i][j]})")

aW1wb3J0IHB1bHAKCiMgRGF0YSBiaWF5YQpjb3N0cyA9IFsKICAgIFs0NSwgNTAsIDU1LCA2MCwgNjVdLAogICAgWzUyLCA0OCwgNDcsIDU1LCA1OF0sCiAgICBbNTAsIDQ2LCA1NCwgNTcsIDU2XSwKICAgIFs0NywgNTMsIDUxLCA0OSwgNTldLAogICAgWzU1LCA1MiwgNTAsIDQ4LCA0Nl0KXQoKIyBOYW1hIGRpdmlzaSBkYW4gcHJveWVrCmRpdmlzaW9ucyA9IFsnRDEnLCAnRDInLCAnRDMnLCAnRDQnLCAnRDUnXQpwcm9qZWN0cyA9IFsnUDEnLCAnUDInLCAnUDMnLCAnUDQnLCAnUDUnXQoKIyBQcm9ibGVtCnByb2IgPSBwdWxwLkxwUHJvYmxlbSgiQXNzaWdubWVudF9Qcm9ibGVtIiwgcHVscC5McE1pbmltaXplKQoKIyBWYXJpYWJlbAp4ID0gcHVscC5McFZhcmlhYmxlLmRpY3RzKCJ4IiwgCiAgICAgICAgICAgICAgICAgICAgICAgICAgKChpLCBqKSBmb3IgaSBpbiByYW5nZSg1KSBmb3IgaiBpbiByYW5nZSg1KSksCiAgICAgICAgICAgICAgICAgICAgICAgICAgY2F0PSdCaW5hcnknKQoKIyBGdW5nc2kgb2JqZWt0aWYKcHJvYiArPSBwdWxwLmxwU3VtKGNvc3RzW2ldW2pdICogeFtpLCBqXSBmb3IgaSBpbiByYW5nZSg1KSBmb3IgaiBpbiByYW5nZSg1KSkKCiMgS2VuZGFsYTogc2V0aWFwIGRpdmlzaSBoYW55YSBzYXR1IHByb3llawpmb3IgaSBpbiByYW5nZSg1KToKICAgIHByb2IgKz0gcHVscC5scFN1bSh4W2ksIGpdIGZvciBqIGluIHJhbmdlKDUpKSA9PSAxCgojIEtlbmRhbGE6IHNldGlhcCBwcm95ZWsgaGFueWEgc2F0dSBkaXZpc2kKZm9yIGogaW4gcmFuZ2UoNSk6CiAgICBwcm9iICs9IHB1bHAubHBTdW0oeFtpLCBqXSBmb3IgaSBpbiByYW5nZSg1KSkgPT0gMQoKIyBTb2x2ZQpwcm9iLnNvbHZlKCkKCiMgT3V0cHV0CnByaW50KCJTdGF0dXM6IiwgcHVscC5McFN0YXR1c1twcm9iLnN0YXR1c10pCnByaW50KCJUb3RhbCBCaWF5YSBNaW5pbXVtID0iLCBwdWxwLnZhbHVlKHByb2Iub2JqZWN0aXZlKSwgImp1dGFcbiIpCgpwcmludCgiUGVudWdhc2FuIE9wdGltYWw6IikKZm9yIGkgaW4gcmFuZ2UoNSk6CiAgICBmb3IgaiBpbiByYW5nZSg1KToKICAgICAgICBpZiBwdWxwLnZhbHVlKHhbaSwgal0pID09IDE6CiAgICAgICAgICAgIHByaW50KGYie2RpdmlzaW9uc1tpXX0gLT4ge3Byb2plY3RzW2pdfSAoQmlheWE6IHtjb3N0c1tpXVtqXX0pIik=