诸葛亮用神算法板求得的计划
用时过长,此时孙权的都督周瑜禀报
他已预见两城需互运物资,早已秘密下令修建另一条运河 如今即可使用。
考虑新增的运河,诸葛亮借助神算法板 重新求解方案。
原来周瑜已经建好了另外一条运河 虽然还是那么窄,但是呢,事情就好办很多了
现在呢我们对每一条船呢 除了要决定它出发的时间,还要决定它要采用哪一条的运河
我们新的运河呢是比较短的,它的长度是 24
千米 这个呢就是我们新的版本,这个双运河问题的
图,其实跟之前没有太大的改变,只是多了一条运河
这个就是双运河 这个问题的文字的描述,跟以前也是很相似
我们利用这个紫色的文字来描述我们新的加进去的
东西,我们现在有两条的运河 要做的决定呢,也新加了每一条船应该采用的哪一条的运河
而且呢因为有新的运河呢,它的长度 24
千米呢也要表示的 其余的条件都跟之前一模一样
好了,其实呢我们可以把之前的单运河
的模型呢做一些小的改动,就可以解决这个双运河这个问题了
首先因为我们已经有多于
一条的运河了,所以呢我们在数据方面要定义一个叫 nC
就是运河的数量,然后呢也定义一个数组,就是每一条运河呢,它的长度是多少
其他的参数跟之前呢,也是没有改变
到了我们的决策变量跟一些辅助的参数
你们还也记得,我们为了要 知道下一条船是什么呢。
所以呢,我们要加,为 我们的运河加上一条,我们叫虚设的船
每一条运河也需要一条虚设的船 所以呢我们现在船的数目不但是
nS+1,是 nS 要加 nC 我在我们的故事里面,nC
就是 2 而且呢我们还需要给这个 kind 这个数组
跟这个速度 speed 这个数组呢,要做一点改动 这个
kind 的数组呢,就是代表每一条船,也包括了我们的虚设的船 它的方向是什么。
因为我们现在有多于 一条虚设的船,所以呢,我们要利用一个推导式把 nC
这个数量的 dummy 加进我们原来这个方向这个数组里面
同样地,对于这个速度来讲 因为我们现在也需要给我们虚设船它一个
0 的速度 而且因为我们现在有 nC
那么多艘的虚设船 所以呢我们也需要一个推导式,把不同的
0 来定义我们每一条的虚设船它们的速度
变量方面,我们多了一组的变量,就是每一条船
包括我们虚设的船呢,它采用了哪一条的运河
好了我们看看问题里面的约束 如果你们还记得呢,我们虚设的船呢,应该就是放到最后的
所以现在呢,因为我们现在有多于一艘的虚设的船,所以我们需要一个循环
来定义每一条虚设的船呢,它的开始时间跟它的结束时间呢都要定义为 最大的可能的时间。
然后我们有一个新的要求 就是呢,每一条虚设的船呢,都应该分配到每一条的
运河的,我们在这里呢利用了一个小小的技巧
就是每一条虚设的船,它是分配到 s 减 nS 这一条的运河的。
那 nS 就是 我们船的数目,但是 s 它是一个循环的下标
它的范围呢,是从 nS+1 到 nS+nC 的
所以呢我们利用这个子表达式呢,我们就可以成功地 把这个每一条虚设的船呢,分配到不同的运河里面
我们也需要呢去定义 我们每一条船它开始的时间跟结束的时间的关系
我们就是说,它每一条船它的开始的时间加上它
航行的时间,就应该等于它结束的时间 但是呢每一条船它航行的时间,
应该是基于它采用了哪一条的运河的,所以呢我们也需要这个运河
这个变量来帮助我们检查,它这个
航行的这个距离的,基于另外这个约束也没有改变
好了,一条船跟它下一条船,它的关系
完全没有改变,但是呢我们要加入一个新的条件
就是呢我们要求呢,每一条船跟它下一条船呢,它们采用的运河是同一条
另外的约束跟我们的目标函数也没有改变
好了我们已经有一个解决
双运河问题的这个模型,我们就可以求解
求解的结果呢是很好的,因为我们发觉呢最后一条船它 只需要
293 个小时呢就可以 到达对面的港口了。
孙权呢,非常开心 因为我们之前呢,利用一条运河的时候,我们需要 22
天的时间 但是我们利用两条的运河的时候,我们可以把它
降低到稍微地超过 12 天,所以这个是非常好的结果
好了,如果我们发觉我们的问题里面的任务
是要依赖一个顺序来决定准备的时间或者是代价的话
我们呢,就应该明确地去表示下一个任务是什么,然后呢
也添加这个约束来保证准备的时间,跟这个代价已经呢 已经在我们的考虑当中。
我们提过的例子 包括运河中航行的时候方向的改变
一个机器作业调度当中呢一个模式的
改变,之前提到就是要把这个线的颜色要改变 还有就是在不同温度的这个
熔炉的这个工厂里面这个作业之间,如果一个熔炉需要是 冷却的时间。
我们来一个小结 我们面对的是一个复杂的调度应用问题
特别的地方就是,任务跟下一个任务之间是有相关性的 所以呢我们就需要对每一个任务都建模
明白了下一个任务是什么的时候,我们就可以 利用约束来表达要
延迟的时间或者是代价也考虑在里面了
[空白_录音]