注：此案例由MindOpt团队和赵直团队合作完成
前言
在过年假期间，单身的小美面临着来自家长的压力，她需要在假期中安排一系列的相亲来满足父母的期望。这不仅仅是一个情感的问题，更是一个需要精心策划的排班问题。
背景故事
排班是一个经典的组合优化问题，而相亲排班可谓是它的一种别出心裁的应用。小美的挑战在于，如何在有限的8天空闲时间内，安排至少12场有效的相亲，并且满足诸如“父母严选”和通勤时间等一系列复杂的条件。
具体条件如下：
- 仅有10天年假（中间2天陪伴家人过年，实则空闲8天）
- 每天不超过2场相亲，且每天仅有3个时段可以相亲
- 假期内会面至少12位以上相亲对象
- 其中至少5位为“爸妈严选”，亲戚、同学和和朋介绍的至少各有一个，这些相亲对象定义为“关系户”
- 确保每天至少安排一位“关系户”，且关系户放在状态较好的下午和晚间
- “爸妈严选“不能全部安排在假期的前半部分，也不能连续见面2位以上，防止爸妈继续塞人
- 年龄、学历、收入、身高等综合分数最高的两名需要安排二面
- 地点离小美越远的安排相亲时考虑降低优先级
解决问题
为了解决这个问题，小美运用了她最近学到的运筹学知识，并借助MindOpt团队的帮助，开发了一个数学模型，旨在最大化她的相亲满意度。变量和参数被定义以覆盖所有的相亲场景，目标函数被设计以考虑相亲对象的综合评分和通勤距离。通过这个模型，小美可以预测每次相亲的满意度并加以优化。
数学模型的构建
目标函数:
其中：
-
是相亲对象的总数。 -
是表征交通因素影响的权重参数，且 
。 -
是第 
个相亲对象的综合评分。 -
是与第 
个相亲对象之间的距离。 -
是一个二进制变量，表示第 
天是否安排了第 个相亲对象。
约束条件：
-
，表示至少安排12个相亲对象。 -
，表示每天最多安排两场相亲。 -
，表示至少有5个由父母推荐的对象。 -
，保证父母推荐的不都在前半部分。 -
，每天见的“爸妈严选”不能超过一个。 -
，每天至少安排一位“关系户”。 -
，“关系户”不安排在午饭时间。 -
，至少各种介绍渠道各有一个。 -
，每个时段只能安排一个相亲对象。 -
，每位相亲对象只安排一个时段。 -
，每位相亲对象最多安排一次相亲。 -
，对于两位评分最高的对象，安排两次相亲。 -
，安排相亲的同时，该时间段必须有相亲活动。 -
，安排相亲的同时，该相亲对象在那天必须有安排。 -
，相亲对象和小美在那个时段都应该是空闲的。
编写执行代码
随后，借助MindOpt Studio 及其MAPL建模语言，小美编写并执行了优化代码，成功地生成了符合所有要求的相亲排程表。最终，一个既满足家人期望又兼顾小美个人偏好的相亲日程就在她眼前展开。
clear model; option modelname BlindDate_2; ############################# # 相亲匹配问题 MAPL建模 # ############################# ####################################### # 该块内的参数均为固定值 ####################################### #param numSource = 5; #相亲对象的介绍来源数，一共5种 set I = 1..8; #假期日集合 set FrontHalf = 1..4; #前半假期集合 set LatterHalf = 5..8; #后半假期集合 param Noon = 1; #午饭时段的编号 param alpha = 0.1; #距离影响系数，目标函数中采用 ####################################### # 该块内的参数(param)均需要读取数据先行初始化 ####################################### print "读取数据----------"; #读取数据：相亲对象基本信息 #相亲对象序号：渠道1，渠道2，渠道3，渠道4，渠道5，综合分，距离，姓名 param : K : Src1, Src2, Src3, Src4, Src5, Score, Dist, Name = read_csv("相亲对象人员名单.csv", skip=1); #print K; print Src1; print Src2; print Src3; print Src; printSrc5; print Score; print Dist; print Name; set Parent = {k in K with Src1[k]=1: k}; #父母介绍 set Relative = {k in K with Src2[k]=1: k}; #亲戚介绍 set Classmate = {k in K with Src3[k]=1: k}; #同学介绍 set Friend = {k in K with Src4[k]=1: k}; #朋友介绍 set Other = {k in K with Src5[k]=1: k}; #其他渠道 #读取数据：该日期的该时段是否空闲？ param : Key : Free = read_csv("空闲时段登记表.csv", use_col="0,1,2,3", skip=1, pattern="n+"); set J = proj(Key, <2>); #时段集合 #计算哪两个是综合分最高的 set Top2 = argmax(2){k in K}Score[k]; # print K; # print I; # print J; # print Score; # print Parent; # print Relative; # print Other; ####################################### print "开始建模----------"; ## 设置变量------- var x[I*J] binary; #表示第 $i$ 天的第 $j$ 个时段是否安排相亲，如果是则为 1，否则为 0。 var y[I*K] binary; #表示第 $i$ 天是否安排了第 $k$ 个相亲对象，如果是则为 1，否则为 0。 var z[I*J*K] binary; #表示第 $i$ 天的第 $j$ 个时段是否安排了第 $k$ 个相亲对象，如果是则为 1，否则为 0。 ## 设置目标------- # 综合评分减去距离影响为单次约会评分， # 总目标是，总计所有安排的约会评分加和最高 maximize Satisfaction: sum{(i,k) in I*K} (Score[k]-alpha*Dist[k])*y[i,k]; ## 设置约束------- #希望在春节期间见到至少12个对象 subto c1: sum{(i,k) in I*K} y[i,k]>=12; #表示不能在同一天安排两个以上的相亲对象 subto c2: for i in I: sum{j in J} x[i,j]<=2; #希望其中至少5个是父母友推荐的。 subto c3: sum{(i,k) in I*Parent} y[i,k]>=5; #表示父母推荐的不能全部安排在假期的前半部分 subto c4: sum{(i,k) in LatterHalf*Parent} y[i,k]>=1; #父母推荐的一天不能连续见两个 #转化为两条约束 subto c5: for i in I: sum{k in Parent}(z[i,1,k]+z[i,2,k])<=1 and sum{k in Parent}(z[i,2,k]+z[i,3,k])<=1; #确保每天至少安排一位“关系户” subto c6: for i in I: sum{k in (K - Other)} y[i,k]>=1; #所有“关系户”需要放在状态较好的下午和晚间 subto c7: for i in I: sum{k in (K - Other)} z[i,Noon,k]=0; #希望亲戚、同学和朋友介绍的至少各有一个 subto c8: sum{(i,k) in I*Relative} y[i, k]>=1 and sum{(i,k) in I*Classmate} y[i, k]>=1 and sum{(i,k) in I*Friend} y[i, k]>=1; #表示如果第 $i$ 天的第 $j$ 个时段安排了相亲，那么只能安排一个相亲对象 subto c9: for (i,j) in I*J: sum{k in K} z[i,j,k]<=x[i,j]; #表示如果第 $i$ 天安排了第 $k$ 个相亲对象，那么只能安排在一个时段 subto c10: for (i,k) in I*K: sum{j in J} z[i,j,k] = y[i,k]; #表示第 $k$ 个相亲对象只能安排一次相亲。 subto c11_1: for k in K - Top2: sum{i in I} y[i,k]<=1; #表示综合评分最好的两个对象需要安排两次相亲 subto c11_2: for k in Top2: sum{i in I} y[i,k]=2; #1)如果第 $i$ 天的第 $j$ 个时段安排了第 $k$ 个相亲对象，那么第 $i$ 天的第 $j$ 个时段有安排相亲。 #2)如果第 $i$ 天的第 $j$ 个时段安排了第 $k$ 个相亲对象，那么第 $i$ 天有安排第 $k$ 个相亲对象。 #3)第 $i$ 天的第 $j$ 个时段安排了第 $k$ 个相亲对象，小美和相亲对象是否都空闲可以安排相亲。 subto c12: for(i,j,k) in I*J*K: z[i,j,k]<=x[i,j] and z[i,j,k]<=y[i,k] and z[i,j,k]<=Free[k,j,i]; print "开始求解----------"; # 选择MindOpt求解器运行 option solver mindopt; solve; print "求解结束，打印结果----------"; #结果存入表格文件中 print "天序号,时段序号,相亲对象序号,相亲对象名称,综合评分,距离" : "解_相亲日程安排.csv"; for (i,j,k) in I*J*K: if z[i,j,k] =1 then print "{},{},{},{},{},{}" % i,j,k,Name[k],Score[k],Dist[k]>> "解_相亲日程安排.csv"; close "解_相亲日程安排.csv"; print "结果已存入：解_相亲日程安排.csv文件"; # 打印部分结果 print "|天序号|时段序号|相亲对象序号|相亲对象名称|综合评分|距离|"; print "|--|--|--|--|--|--|"; for (i,j,k) in I*J*K: if z[i,j,k] =1 then print "| {}| {}| {}| {}| {}| {}|" % i,j,k,Name[k],Score[k],Dist[k];
运行结果如下：
读取数据---------- 开始建模---------- 开始求解---------- Running mindoptampl wantsol=1 MindOpt Version 1.0.1 (Build date: 20231114) Copyright (c) 2020-2023 Alibaba Cloud. Start license validation (current time : 05-FEB-2024 17:37:55). License validation terminated. Time : 0.008s Model summary. - Num. variables : 984 - Num. constraints : 1780 - Num. nonzeros : 5844 - Num. integer vars. : 984 - Bound range : [1.0e+00,1.2e+01] - Objective range : [1.5e+00,9.9e+01] Branch-and-cut method started. Original model: nrow = 1780 ncol = 984 nnz = 5844 Tolerance: primal = 1e-06 int = 1e-06 mipgap = 0.0001 mipgapAbs = 1e-06 Limit: time = 1.79769313486232e+308 node = -1 stalling = -1 solution = -1 presolver terminated; took 2 ms presolver terminated; took 90 ms Parallelism: root=4, tree=4 accept new sol: obj -838.5 bnd vio 0 int vio 0 mipgap 10.584496124031 time 0 Model summary. - Num. variables : 389 - Num. constraints : 164 - Num. nonzeros : 1184 - Bound range : [1.0e+00,8.0e+00] - Objective range : [1.5e+00,9.9e+01] - Matrix range : [1.0e+00,1.0e+00] Presolver started. Presolver terminated. Time : 0.001s Simplex method started. Model fingerprint: =Y2dgFmZmdnbiR2djRmZ Iteration Objective Dual Inf. Primal Inf. Time 0 -1.12056e+04 0.0000e+00 4.3700e+02 0.00s 193 -1.28600e+03 0.0000e+00 0.0000e+00 0.00s Postsolver started. Simplex method terminated. Time : 0.005s accept new sol: obj -1286 bnd vio 0 int vio 0 mipgap 0 time 0 Root relaxation: -1286 iteration = 193 time = 0.005 Branch-and-cut method terminated. Time : 0.230s OPTIMAL; objective 1286.00 Completed. 求解结束，打印结果---------- 结果已存入：解_相亲日程安排.csv文件 |天序号|时段序号|相亲对象序号|相亲对象名称|综合评分|距离| |--|--|--|--|--|--| | 1| 2| 11| 王十一| 85| 4| | 1| 3| 23| 张廿三| 79| 15| | 2| 2| 5| 陈五| 81| 14| | 2| 3| 14| 刘十四| 66| 25| | 3| 1| 25| 陈廿五| 67| 19| | 3| 2| 18| 黄十八| 84| 19| | 4| 2| 13| 张十三| 37| 15| | 4| 3| 19| 周十九| 66| 24| | 5| 2| 3| 张三| 82| 10| | 5| 3| 15| 陈十五| 93| 11| | 6| 2| 17| 赵十七| 99| 25| | 6| 3| 24| 刘廿四| 100| 10| | 7| 2| 8| 黄八| 100| 6| | 7| 3| 12| 李十二| 70| 17| | 8| 2| 8| 黄八| 100| 6| | 8| 3| 24| 刘廿四| 100| 10|
