数学建模-员工问题

Post author:xfxia
Post published:2023年9月14日
Post category:其他

某公司指派n个员工到n个城市工作(每个城市单独一人),希望使所花费的总电话费用尽可能少.n个员工两两之间每个月通话的时间表示在下面的矩阵的上三角形部分(假设通话的时间矩阵是对称的,没有必要写出下三角形部分),n个城市两两之间通话费率表示在下面的矩阵的下三角形部分(同样道理,假设通话的费率矩阵是对称的,没有必要写出上三角形部分)．试求解该二次指派问题.(如果你的软件解不了这么大规模的问题.那就只考虑最前面的若干员工和城市.)

[0 , 5 , 3 , 7 , 9 , 3 , 9 , 2 , 9 , 0 ]

[7 , 0 , 7 , 8 , 3 , 2 , 3 , 3 , 5 , 7 ]

[4 , 8 , 0 , 9 , 3 , 5 , 3 , 3 , 9 , 3 ]

[6 , 2 , 10, 0 , 8 , 4 , 1 , 8 , 0 , 4 ]

[8 , 6 , 4 , 6 , 0 , 8 , 8 , 7 , 5 , 9 ]

[8 , 5 , 4 , 6 , 6 , 0 , 4 , 8 , 0 , 3 ]

[8 , 6 , 7 , 9 , 4 , 3 , 0 , 7 , 9 , 5 ]

[6 , 8 , 2 , 3 , 8 , 8 , 6 , 0 , 5 , 5 ]

[6 , 3 , 6 , 2 , 8 , 3 , 7 , 8 , 0 , 5 ]

[5 , 6 , 7 , 6 , 6 , 2 , 8 , 8 , 9 , 0 ]

解答：

设0-1变量xij,若为1则代表将第i个员工派向第j个城市，若为0则代表未指派time i m 表示第i个和第m个员工之间的通话和时间，pricejn表示j和n城之间的通话费率，那么即可建立模型如下。

代码：

import numpy as np
import gurobipy as grb
from gurobipy import *

rec = np.array([[0 , 5 , 3 , 7 ,  9 , 3 , 9 , 2 , 9 , 0 ]
               ,[7 , 0 , 7 , 8 ,  3 , 2 , 3 , 3 , 5 , 7 ]
               ,[4 , 8 , 0 , 9 ,  3 , 5 , 3 , 3 , 9 , 3 ]
               ,[6 , 2 , 10, 0 ,  8 , 4 , 1 , 8 , 0 , 4 ]
               ,[8 , 6 , 4 , 6 ,  0 , 8 , 8 , 7 , 5 , 9 ]
               ,[8 , 5 , 4 , 6 ,  6 , 0 , 4 , 8 , 0 , 3 ]
               ,[8 , 6 , 7 , 9 ,  4 , 3 , 0 , 7 , 9 , 5 ]
               ,[6 , 8 , 2 , 3 ,  8 , 8 , 6 , 0 , 5 , 5 ]
               ,[6 , 3 , 6 , 2 ,  8 , 3 , 7 , 8 , 0 , 5 ]
               ,[5 , 6 , 7 , 6 ,  6 , 2 , 8 , 8 , 9 , 0 ]])
triu = np.triu(rec)#取出矩阵的上三角部分
tril = np.tril(rec)#取出矩阵的下三角部分
time = triu+triu.T
price = tril+tril.T
print("各员工通话时间为:\n",time,"\n","各城市通话单价为:\n",price)

model = grb.Model("Company")
x = model.addVars(10,10,vtype=grb.GRB.BINARY,name = "是否指派")
objective = grb.quicksum(x[i,j] * x[m,n] * time[i,m] * price[j,n] for i in range(10) for j in range(10) for m in range(10) for n in range(10))
#设置目标函数
model.setObjective(objective/2,grb.GRB.MINIMIZE)
#添加约束
model.addConstrs((x.sum(i,'*')==1 for i in range(10)),"行")
model.addConstrs((x.sum('*',i)==1 for i in range(10)),"列")
# 求解
model.optimize()
print('目标函数值是：', model.objVal)
if model.status == GRB.OPTIMAL:
    model.printAttr('X')
    model.printAttr('Slack')
    print("指派矩阵为:\n",np.array(model.X).reshape(10,10))

我们使用python来解决这个问题