招兵买马后,刘备下一步考虑生产五种兵器 斧、 剑、 戟、 长矛和狼牙棒 供士兵作战使用,每种兵器对士兵有着不同的战斗力提升 军中已有生产兵器所需的铁料 木材以及木匠、 铁匠,生产 各种兵器所需的原料数量和工时各有不同 刘备希望有效利用军中有限的原料和工匠生产兵器 得到尽可能大的战斗力提升 面对难题,刘备取出神算法板求助 >> 要打仗,兵马的实力当然非常重要 但是更重要当然就是兵器 原来我们三位英雄呢,他们也给这个兵器的生产问题 觉得很烦恼。 我们看看这五种不同的兵器 它们都有不同的威力,而且呢 它们也需要不同的资源,包括材料 还有不同的工匠的时间,才可以把它们打造出来 所以呢下面这个表我们就可以看见 每一种不同的兵器它们对不同的资源 的需求是怎么样的,这个就是我们的数据了 我们的资源是有限的 我们的约束就是要求呢,我们要打造的兵器 它们可以用的资源不可以超过我们现在有的资源 当然了我们最重要就是希望打造出来的兵器它们的 战斗力就是最大化的。 我们 面对这个问题呢其实是一个典型的生产规划问题 如果你们注意到的话 我们这个生产规划问题呢跟我们之前看过的一些问题都很相似 每一个问题都有一个所谓叫产品 我们要把这个产品生产出来呢,都要用掉一些资源 我们的约束跟目标就是分别是 对我们资源的一些限制,而且呢我们希望把我们的利润最大化 我们之前看过一个组建军队的 问题,我们的资源就是我们的金钱的预算 我们的产品呢就是我们的士兵 也看看我们的桃园宴会这个问题 我们的资源呢就是桌子的空间 所谓消耗呢就是用了它们的这个空间,我们的产品呢就是我们的菜品了 所以呢我们其实都可以为 这一批的问题建立一个我们所谓叫一般化的模型出来 利用同一个模型就可以解决这里我们看过所有不同的问题了 我们来看看这个生产规划问题的 模型,我们首先看看它的数据 我们有一个枚举类型的数据来表示不同的产品 另外呢需要一个数组来代表 每一种产品它可以达到的利润 我们也需要另外一个枚举类型的数据来表示不同的资源 另外一个数组来代表每一种资源 它有的量是多少。 下面我们就看见一个新的概念,这是一个 二维的数组,在这个二维的数组里面呢 就是给我们每一种产品 到底它要对每一种的资源 它要用的量是多少?我们刚才看过数据 我们现在再看看我们的变量跟我们的约束 我们有一个整型变量的数组,就是每一种产品 我们到底要生产的量是多少 然后我们的约束就是说,每一种产品我们要求要生产的量 不可以小于零,这个是非常正常的 下面这个约束呢比较复杂一点,就是要求呢我们的每一个资源 所有产品要用这个资源的量 不可以大于这个资源现有的 量。 我们所以要求每一个资源 然后把所有需要用到这个 资源的产品,它消耗的量的总和 算起来,然后要求它小于等于 这个资源的它的量。 最后就是 我们的目标函数,我们就需要把所有的 产品,它可以带来的利润 的总和算起来,然后要把这个 值要最大化,然后就是我们的输出语句 在这里呢,我们也看见一个新的概念 就是原来一个数组呢可以是二维的 而且呢我们现在看见是一个二维数组的查找 我们再来看看这个数组 刚才已经提过一个数组呢可以是多维的 我们怎么声明一个多维的数组呢?非常简单,就是 声明它们的下标的时候,把每一个下标的集合 就用一个逗号把它们分开就可以了 然后当然也要定这个数组它的类型是什么 刚才提到一个数组的下标集合,它是可以一个整型范围 或者是一个枚举类型,也可以是一个 固定值的集合表达式,集合呢我们在未来可以 再介绍。 数组的元素可以是任何的类型 但是不可以是另外一个数组,所以我们看见 我们刚才这个例子就是我们定义了一个 二维的数组,它有两个下标分别就是 产品这个枚举类型的数据跟这个资源 这个枚举类型的数据,然后它的类型就是一个整型的数据 这个就是这个数组的名字 对于数组呢,MiniZinc 里面也有一个内建的函数 叫 length,length 就是返回一个一维数组的长度的 好了,我们有了这个 数组的参数,我们当然要需要给它赋值 或者说初始化,对于一维的数组呢非常简单 因为一个一维数组的常量呢就是用一个 列表来表示的,所以对于利润 跟容量这两个一维的数组呢,我们就可以 直接利用一个列表来把两个不同的参数 初始化了。 但是我们怎么把一个二维的数组来初始化呢,我们就需要一个 特别的语法。 首先要把一个二维的 数组的常量表示出来,我们开始的时候需要 一个中括号跟一个竖线 然后呢其实对于一个二维的数组来讲 第一维的每一个元素也是一个列表,所以呢一个列表里面不同的 元素呢我们就用逗号把它们分开,我们写完了 一维,每一个,整个元素的列表之后 我们也需要一个竖线来把 一维里面不同的元素分开,然后最后 我们也需要一个竖线跟一个中括号来 把我这个常量结尾 好了,我们刚才看见怎么把一个 二维的数组参数初始化 但是如果我们的数组到达维度是比 二更大怎么办呢?首先呢在 MiniZinc 里面它的数组的维度最高只可以为 6 在 MiniZinc 里面也提供了一个族的函数,我们叫 array nd,那这个 n 呢可以是 2, 3, 4, 5, 6 也可以的 这个 array nd 这个函数呢,就是帮助我们把一个 一维的数组然后把它变成一个二维、 三维、 四维 五维还是六维的数组出来的。 我们就看看我们利用这个 array 2d 这个函数怎么可以把一个一维的 数组把它 变成一个二维的数组,然后来初始化我们刚才的这个 consumption 这个参数 我们首先要定义我们的这个二维的数组 它的下标。 第一个下标这是 1..5,然后这是 1..4 然后就是一个一维的数组。 然后 array 2d 呢就会返回一个 1..5、 1..4 的二维的数组,然后就可以把它 赋值给我们的 consumption 这个参数了 MiniZinc 里面也有提供数组推导式 这个是用来帮助我们生成这个 数组出来的。 它们的意义也跟这个 Haskell 跟 ML 这两个编程语言里面的很类似 这个就是 MiniZinc 里面的数组推导式的形式了 我们来看看这个例子来解释它的意义吧。 我们有一个 两个生成器 i j in 1..4,我们可以把它写成 i in 1..4 然后逗号,j in 1..4,我们现在看见就是一个比较简单的写法 然后这个两个生成器呢就会生成 不同的 i 跟 j 在这个 1..4 这个范围里面的组合 但是我们也有一个 where,这个 where 后面有一个条件 它说虽然你可以生成不同的 i 跟 j 的组合,但是我们要求 i 一定要小于 j,我们才接受这个组合的 然后,利用这个生成器跟 where 生产出来的组合呢,我们就放到我们之前的 表达式,就利用这个表达式呢,来生成 1+2,1+3,1+4 到了最后 3+4,最后就生成我们这个 3, 4, 5 5, 6, 7 这个一维的数组了 我们刚才看过一个例子,就是怎么可以利用 array 2d 把一个一维的数组把它变成一个二维的数组,从而来 初始化一个二维数组的参数,其实呢,我们利用一个 数组的推导式呢,也可以把一个 高维的数组把它压平 变成一个列表也就是说一个一维的数组。 下面就是一个 例子,把这个 consumption 这个二维的数组,把它变成一个一维的数组。 我们就是说 这个生成器就是 i in 1..5 j in 1..4 然后这两个生成器呢,就会产生 i 跟 j 不同的组合 然后我们这个表达式就是 consumption [i, j],然后出来呢就是一个 一维的数组,里面就已经有原来这个二维数组里面的所有的元素在里面了 [空白_录音] MiniZinc 里面也提供了不同的对于列表可以 进行这个操作的内建函数 包括 sum、 product、 min 跟 max 这一些函数呢,它们的输入 就是一个数字的列表,sum 就会把这个 输入的数字的列表里面所有的元素把它加起来,product 把它们乘起来 min 跟 max 就是把它们的最小跟最大的值 找出来。 forall 呢,它的输入是个 约束的列表。 我们看看下面的例子 我们说,forall i, j in 1..10,然后我们也要求 i 要小于 j,这里呢我们就可以 生成 i 跟 j 在 1..10 里面的不同的 组合,但是我们要求 i 是要小于 j 的 然后把对应的 i 跟 j,不同的 i, j 对应的 a[i]! 等 a[j] 呢,我们的要求这个约束呢为真 其实,这个刚才看见这个例子呢,跟下边这个是等价的 其实就是一个 forall,我们给它一个约束的列表 然后我们就要求这个约束列表里面每一个元素都要为真 就是这个意思。 我们回到我们的 兵器生产问题,我们看看我们的数据文件 我们可以看到,我们在这个文件里面就把我们不同的参数 都给它们赋值。 特别的是 我们这里有一个二维的数组的常量。 基本上呢 每一行就代表一个产品 然后每一个列就对应一个不同的资源 所以这个是一个矩阵 我们利用我们的模型跟我们的数据,要求这个 MiniZinc 来求解 这个就是我们得到的答案了。 所以我们的英雄已经 准备好怎么去把他们的军队好好地装备了 我们用相同一个模型,但是如果给它不同的数据的话 我们也可以利用这个模型呢,来解决其他生产规划的问题的 包括我们之前提过的组建军队的 问题,我们的产品呢就是不同的穿装,我们的利润就是 这个不同穿装的壮丁他们的战斗力是多少。 我们的资源就是 钱了。 然后我们有的钱就是总共有一万块钱,然后 要招募一个壮丁再不同的穿装,这个就是我们要消耗、 要用的钱了 在这个桃园宴会呢,我们的产品就是不同的菜 然后我们的利润就是我们的满足的程度 我们的资源就是这每一盘菜它的大小 我们的量就是我们的桌子的 容量,而且呢每一盘菜它需要用 多少的地方,这个就是我们的资源的消耗了 我们也发觉,我们用我们 MiniZinc 里面默认的一个求解器 Gecode 要解决这个兵器生产的问题的时候,花费了很长很长的时间 才可以把这个最优的解找到出来。 但是呢,如果我们 改了用一个我们刚才提过的 G 12 MIP 利用这个 混合整数 线性规划这个技术生成的求解器呢,我们几乎是 立刻就可以把这个问题解决了。 这发生了什么事情呢? 原来我们这个生产规划的问题是个混合 整数规划问题,所以呢用 MIP 来求解是最理想的 所以我们知道,我们建了模之后,也要知道选择用什么的求解器 更适合来解决我们手上的问题 我们来一个小结 真正的模型呢,应该可以应用到不同大小的数据 上面呢,在这个 MiniZinc 里面,我们利用这个枚举类型 为我们的对象命名,利用数组来 捕捉我们对象的不同的信息 我们也可以利用推导式,用来创建适用于不同 规模的数据的约束以及表达式 [空白_录音]