数战告捷后,刘备计划组建
一支巡逻队,每天分班次巡逻,以防敌军突袭
每天巡逻中,深夜班需要三名士兵当值,而白天不 需要安排巡逻。
黄昏后的傍晚班最好有两名士兵巡逻 但如果人手不足,最少仍需要一名士兵
为保存士兵精力,士兵不可连续当值两个 以上的深夜班。
当值了傍晚班的士兵不可以当值紧接下来的深夜班
刘备希望找到一个满足所有条件的轮值表 并使当值傍晚班的士兵数量尽可能多
刘备再次取出神算法板
>> 虽然打赢了几场仗,但是
刘备他们还是害怕这个董卓会来偷袭的
所以他们需要派兵在晚上去巡逻 在夜晚的时候
非常危险,天很黑,所以他们需要三名士兵 在大白天
每个人都在,所以就不需要士兵了。
在傍晚 他们需要两个士兵,但是如果人手不够的话
一名也勉强可以。
其实这个 巡逻轮换的问题是非常头疼的
我们就需要给每一名的士兵安排
在这八天里面,每一天他需要是当这个
夜班,还是傍晚班,还是休息 我们记住,这个白天是不需要这个巡逻的
而且我们的所谓是,夜班就是在午夜之后
我们要解决这个问题的时候,需要小心一点
因为我们看看这个情况 我们看见,这个士兵需要
三天连续都要上这个夜班
这个是不可能的,因为当夜班是过了半夜
所以如果连续多于 两天当夜班,这个士兵就没有
足够的休息的时间。
还有另外一个例子 那这个例子有什么问题呢?我们看看这里
这个士兵需要当了一个傍晚的班,然后
就马上就要当一个夜班 这个也是不可能的。
你看清楚,基本上他 上了这个傍晚班就直接就开始另外一个夜班
他基本上就是没有休息的时间,这个也是不行 我们刚才讲过
因为人手的问题,所以上这个傍晚
班的士兵的数量可以是一还是二 但是我们觉得呢还是当傍晚班的
士兵的数量是越多越好的,所以这个就变成了我们的要优化的目标了
这个就是一个可能
给一个士兵他要当班的 这个时间表。
你看见他第一天当夜班 第二天当这个傍晚班,第三天他是放假
然后四五天当夜班,第六天当傍晚班 第七天放假,然后第八天他是当夜班
其实我们这个轮换的问题 也就是一个确定函数问题。
我们要确定就是 每一个士兵每一天他要上什么的班
我们也可以把它看成一个划分的问题
就是每天的每一个班 有什么的士兵要当这个班呢?
或者下面有另外一个看法 我们就是要确定另外一个函数
这个函数就是拿一个班,然后要确定
什么的士兵是在这个班里面的。
所以 这个大 F(c) 这个函数就是要从班
映射到一个士兵的子集 这个大
F(c) 这个函数其实就是我们刚才提到这个小
f(d) 这个函数的 伪逆函数。
我们现在来看看 这个问题的模型,首先就是数据
我们需要定义士兵呢、 不同的班呢
而且我们要做这个轮换问题要多少天呢
然后也需要定义我们不同的班 需要多少个士兵,夜班需要
o 那么多士兵,然后傍晚班需要
在它的下限就是 l,它的上限就是 u
那我们这个排班问题的变量是什么呢?因为这个问题是一个
确定函数的问题,我们要看看这个函数的 定义域跟它的值域是什么。
这个函数的定义域就是 士兵的集合跟日子的集合它的乘积
而它的值域的对象就是不同的班
所以我们对于每一天每一个士兵
我要决定他的班次是什么 所以我们的变量的定义就是一个二维的数组
这个数组里面每一个元素就
是每一个士兵每一天他要上什么的班
这个当然就可以看成为一个划分问题了
是根据班次的类型来划分士兵
对每一个班次的士兵集合进行推理 我们来看看这个排班问题的约束
第一个约束就是说,每一个士兵都不能连续多于两个晚上 当这个夜班。
我们可以利用 这一条的约束来表达这个条件
我们说每一个士兵他连续三天
我们把他当夜班的次数 总和,要求这个总和是不大于
2 但是你们跟我也可能是一样,觉得这个不太清楚
我们有一个比较直接的方法来表示这个条件
就是说如果一个士兵有一天当了夜班
下一天也当了夜班,那
他再下一天就不可以再当夜班了,这个比较直接
同样的,每一个士兵不能
当了傍晚班然后在下一天再当这个夜班的话
我们也可以这样子说,一个士兵如果有一天当了这个
傍晚班,他的下一天就不可以当夜班了
其实利用这个逻辑联结词
是可以帮助我们去表达很多比较复杂的 约束,当然在
MiniZinc 里面 也支持不同我们常用的逻辑联结词
还有另外的约束 每个晚上当夜班的士兵需要有
o 个 我们就很简单了,把所有
当夜班的士兵每一天加起来,要求它是等于
o 当傍晚班的士兵
比较复杂一点,因为它不是要一个固定的数目,是有一个
下限还有一个上限 所以我们需要就是算一算
每一天多少个士兵是当傍晚班 然后要求它是大于
或者等于这个下限,然后相同地
也要求同一个总和要小于或者等于它的上限
我们的目标函数就是要求
上傍晚班的士兵
他加起来的总和是最大化 这个就是我们的
排班问题的模型,包括我们之前提过的数据
变量的定义,还有我们不同的约束的表达方式
我们建了一个模型出来
当然要跑这个模型,希望求到一个解 但是我们利用
MiniZinc,过了五分钟 还是没有任何的结果,其实我们最后是等了超过十分钟
MiniZinc 才把这个答案给了我们。
如果我们把这个 问题的规模变小
把天数改为 6,这个 MiniZinc
就需要 7 秒钟就把这个 解找出来了。
是不是什么地方出了问题呢? 其实这个例子正好就把组合
优化这个问题的困难的地方带出来 我们的问题看起来很简单,规模也不大
但是偏偏就是很困难来解决
在下一回我们就看一看,怎么可以 把我们的模型改善,然后从而
提高这个解决这个问题的效率
[空白_录音]