模型求解: 在上面的模型中,我们可以看到这里的决策变量为an,Pn,约束条件是线性的, 而目标函数却是非线性的,故无法用单纯型算法实现 我们利用动态规划算法编程实现,算法流程图见附录I。 计算结果如下 共需要15辆卡车,最小的总运量为92236.8(吨公里) 分布路线图如下: 1(2 4+2(81) 2(85) 3 1(14 1(15) 装场Ⅱ 倒装场 图中+表示铲位 o表示卸点 第6页共20页
第 6 页 共 20 页 模型求解： 在上面的模型中，我们可以看到这里的决策变量为 ij a , ij p ，约束条件是线性的， 而目标函数却是非线性的，故无法用单纯型算法实现。 我们利用动态规划算法编程实现，算法流程图见附录 I。 计算结果如下： 一共需要 15 辆卡车，最小的总运量为 92236.8（吨公里） 分布路线图如下： 路线上标示的括号前的数字表示在该路线上承载运输工作的车辆数，括号中 的数字表示该路线上所发卡车所需承载的总趟数。 铲点冲突率： 1 2 3 4 5 6 7 8 9 10 19.1% 9.8% 20.1% 0 26.9% 0 0 0 20.8% 13.9% 铲点平均冲突率：15.8% 卸点冲突率： 1 2 3 4 5 0.5% 14.6% 11.2% 28.5% 2.6% 一班次的含铁量 矿石漏 30.46% 倒装场 1 30.47% 倒装场 2 29.62%
卸点平均冲突率:11.5% 问题二 当利用现有车辆运输时,例如本实例,有20辆车进行运输,通过我们上面 的程序是搜索不到可行解的,故避免冲突的可行解也自然不存在。因此本模型对 于解决问题二是不可能的。同时我们用蒙特卡罗仿真寻找15~19内的可行解,进 行2×10°次仿真,仅能搜索到一个可行解(当为17辆卡车时),所以我们可以基 本认为该模型对于任意给定的卡车数是无解的。于是这就促使我们去寻找更优秀 而更有效的模型。 模型优缺点: 该模型的优点 1、计划简单易操作,一旦路线分配完,卡车就可以在确定的铲点和卸点之间不 停的来回工作,直到完成任务为止。 2、冲突率容易计算,并易于避免冲突的发生 3、方案受随机性影响较小,稳定性较强。 该模型的缺点 1、安排的卡车数较多,所走总路线较长,矿厂的经济效益不高。 2、所安排的计划执行效率不高,铲点挖空后卡车就不工作,处于闲置状态。 车次模型: 不同于车辆模型,车次模型是一个以计算车次为基础来考虑的模型,车次允 许卡车走多条路线。例如一辆卡车可以在一段时间内走A路线,另一段时间走B 路线,而这一点在车辆模型中是不会出现的 为了描述该模型,引入车次的概念,一个车次代表一辆卡车在一条路线上工 作一次。铲点到卸点的车次安排表示应当在该路线上所安排的车次总数。 定义x为所安排的车次数量,于是类似上面的车辆模型,可以得到一个线性规 划 问题 我们得到类似于车辆模型的线性规划如下: 第7页共20页
第 7 页 共 20 页 卸点平均冲突率：11.5% 问题二： 当利用现有车辆运输时，例如本实例，有 20 辆车进行运输，通过我们上面 的程序是搜索不到可行解的，故避免冲突的可行解也自然不存在。因此本模型对 于解决问题二是不可能的。同时我们用蒙特卡罗仿真寻找 15~19 内的可行解，进 行 9 2´10 次仿真，仅能搜索到一个可行解（当为 17 辆卡车时），所以我们可以基 本认为该模型对于任意给定的卡车数是无解的。于是这就促使我们去寻找更优秀 而更有效的模型。 模型优缺点： 该模型的优点： 1、计划简单易操作，一旦路线分配完，卡车就可以在确定的铲点和卸点之间不 停的来回工作，直到完成任务为止。 2、冲突率容易计算，并易于避免冲突的发生。 3、方案受随机性影响较小，稳定性较强。 该模型的缺点： 1、安排的卡车数较多，所走总路线较长，矿厂的经济效益不高。 2、所安排的计划执行效率不高，铲点挖空后卡车就不工作，处于闲置状态。 车次模型： 不同于车辆模型，车次模型是一个以计算车次为基础来考虑的模型，车次允 许卡车走多条路线。例如一辆卡车可以在一段时间内走 A 路线，另一段时间走 B 路线，而这一点在车辆模型中是不会出现的。 为了描述该模型，引入车次的概念，一个车次代表一辆卡车在一条路线上工 作一次。铲点到卸点的车次安排表示应当在该路线上所安排的车次总数。 定义 ij x 为所安排的车次数量，于是类似上面的车辆模型，可以得到一个线性规 划。 问题一： 我们得到类似于车辆模型的线性规划如下：