数学建模教学中顺序调度问题的研究

陈允峰

[摘           要]  在参考资料《数学建模算法与应用》一书消防车调度的基础上通过进一步完善，提出解决顺序指派问题的一个通用数学模型，并通过抢险车顺序调度这一具体问题，编制lingo程序，程序运算结果验证本方法的有效性。

[关    键   词]  数学建模;顺序调度;lingo

[中图分类号]  G712                   [文献标志码]  A                    [文章编号]  2096-0603（2018）26-0139-01

某防汛中心下有5辆抢险车，分属于3个不同的抢险站。某市洪灾，有三处抢险点分别需要2辆、1辆、2辆抢险车，洪灾损失程度与抢险车到达的及时程度有关。记第j辆车到达第i个地点的时间为tij，这三处抢险点的损失分别为5t11+3t12，3t21，6t31+4t32，假设抢险车从3个抢险站到3个抢险点的时间如表1所示，假设3个抢险站恰好分别有2，1，2辆车，该防汛中心该如何调度抢险车辆。

问题分析：

参考文献[1]，该问题可以看作是指派问题的一个变种，我们可以通过构造相应的损失矩阵，再添加合适的决策变量，把这个问题转化为0-1规划模型。我们把每一个抢险点需要的一辆车看成是1个需求，这样从抢险点1到抢险点3共有5个需求点，这样我们可以得到从3个抢险站到5个需求点的损失表（见表2），记从第i个抢险站到第j个需求点派车，损失为Sij（i=1，2，3，j=1，2，3，4，5）。

同样的方法我们可以整理出从3个抢险站到5个需求点的时间表（见表3），并记从第i个抢险站到第j个需求点的时间为Tij（i=1，2，3，j=1，2，3，4，5）。

设第i个搶险站向第j个需求点派车为Xij（i=1，2，3，j=1，2，3， 4，5），Xij=1，表示第i个抢险站向第j个需求点派车，Xij=0，表示不派车。

模型建立及求解：

则此顺序调配问题可以表示为如下线性规划模型：

min=■■SijXij

s.t.■X1j=2■X2j=1■X3j=2■Xi2Ti2<■Xi1Ti1■Xi5Ti5<■Xi4Ti4■Xij=1，（j=1，2，3，4，5）Xi，j为0-1变量

编制lingo程序，并运算得全局最优解：X1，3=1，X1，5=1，X2，2=1，X3，1=1，X3，4=1，其余决策变量为零。即得抢险车的调度方案为：从抢险站1往抢险点2发一辆车，从抢险站1往抢险点3发第二辆车，从抢险站2往抢险点1发第二辆车，从抢险站3往抢险点1发第一辆车，从抢险站3往抢险点3发第一辆车，经验证，此解为合理的。

参考文献：

[1]谢金星，薛毅.优化建模与LINDO/LINGO软件[M].北京：清华大学出版社，2006.

[2]司守奎，孙玺菁.LIINGO软件及应用[M].北京：国防工业出版社，2017.