week14 规划问题–Santa的接待安排

Santa的接待安排

圣诞节前100天，Santa开放了workshop，欢迎以家庭单位的参观，如何更合理的安排这些家庭参观？

每个家庭有10个选择choice0-9，数字代表了距离圣诞节的天数，比如 1代表12月24日，每个家庭必须并且只安排一次参观

家庭数量 5000，即family_id 为[0, 4999]，每天访问的人数需要在125-300人

解题思路

为了更合理的计算Santa的安排能力，我们使用preference cost和accounting penalty两个指标

1）preference cost，代表Santa的个性化安排能力 

2）accounting penalty，代表Santa安排的财务成本

每天接待的人员数N(d)如果大于125，就会拥挤，产生过多的清洁成本，计算公式为

 其中 N(d)代表当天，N(d+1)代表前一天（因为N代表距离圣诞节的天数）

最终的 Score = preference cost + accounting penalty

最终提交每个家庭的安排 submission.csv

代码实现步骤

Step1, 数据加载

Step2，数据预处理

1）计算Perference Cost矩阵 pcost_mat

2）计算Accounting Cost矩阵 acost_mat

3）计算每个家庭的人数 FAMILY_SIZE

4）每个家庭的倾向选择（choice_） DESIRED

Step3，使用LP和MIP求解 规划方案

1）先使用LP 对绝大部分家庭进行规划

2）再使用MIP 对剩余家庭进行规划

3）汇总两边的结果 => 最终规划方案

Step4, 结果评估

按照evaluation标准，计算

Score = preference cost + accounting penalty

Step5，方案优化

通过更换family_id的选择，查找更好的score

每次更换后，都对方案进行评估，选择更小的score方案

%%time 在jupyter中可以给出cell代码运行一次的时间

np.sort(a)，对a按从小到大的顺序排序

np.argsort(a)，返回数组从小到大的索引

@njit(fastmath=True)

numba是python的即时编译器，当调用python函数时，代码会替换为机器码执行

numba可以加速计算负载比较大的python函数

@njit 表示全部使用加速

fastmath=True，启用函数的快速数学行为

思考

运筹学求解思路简单，但要找到满意的结果却很难

现在的求解思路类似暴力穷举，而求解的空间又是非常巨大的 => 不能在约束的时间内得到较好结果

针对凸优化问题（比如线性规划）可直接得到最优解

如果是非凸优化，无法判定是全局最优解还是局部最优解，在业界一般使用启发式算法，比如遗传算法

分支定界法，启发式算法核心原理是暴力穷举的改进，尽可能减少搜索空间，更快得到可行解