玩三国, 学【离散优化建模】基础篇 02
离散优化建模 基础篇
图片和内容摘自离散优化建模基础篇, MOOC由香港中文大学开发, 推荐各位到 Coursera 边看视频边学习, 链接见阅读原文.
1.1.5 桃园宴会
书接上文:
为了振奋士气,刘备 关羽和张飞在桃园设宴款待自己和士兵.
刘关张三兄弟最爱的菜肴是蛇羹, 宫保田鸡和麻婆豆腐. 他们对各样菜肴有不同的满意享受程度(29,19,8), 而盛放菜肴的碟子大小也各有不同(8,5,3). 他们希望在他们桌子上尽量多地放置这三道菜, 使碟子占位不超出桌子(最大18),又使享受程度最高.
而对普通士兵而言, 他们有更多的菜式和更宽的桌子, 但他们也面临类似的问题.
面对难题, 刘备又取出了神算法宝, 也让我们用 Wolfram 语言来看看如何帮助小刘吧, 还是请出 Maximize 命令就可以了.
其实呢. 桃园宴会问题是众所周知的背包问题的一个版本. Wolfram 语言中的 KnapsackSolve 提供了简单且便于使用的方法求解如背包问题 (knapsack problem) 的组合最优化. 下面就是求在约束条件 8 s+5g+3m<=18 下, 使得总的满意度 29 s+19g+8m 最大化的数量的解法:
是不是很简单呢, 如果用关联来编写会更容易理解, 设置每道菜的喜爱程度和尺寸大小.
类似也可以求出来对士兵桌子如何放置菜肴的问题啦:
1.1.6 兵器大生产
招兵买马后,刘备下一步考虑生产五种兵器 斧(Axe)、 剑(Sword)、 戟(Pike)、 长矛(Spear)和狼牙棒( ) 供士兵作战使用。
每种兵器对士兵有着不同的战斗力提升.
军中已有生产兵器所需的铁料 木材,以及木匠、 铁匠, 如下所列.
生产各种 兵器所需的原料数量和工时各有不同
刘备希望有效利用军中有限的原料和工匠,生产出的兵器尽可能大的提升战斗力. 面对难题,刘备取出神算法板求助 .
我们 面对这个问题呢,其实是一个典型的生产规划问题, 这跟之前遇到过的一些问题都属于同一类型 - 如组建军队和桃园宴会.
那当然我们还是可以用 Maximize 命令来搞定了.
不过值得值得一提的是, Wolfram语言中的 LinearProgramming 是用来解线性生产规划问题的主要函数,它能够最灵活地指定应该使用哪一个函数,并且对于解决大规模问题是最有效的.
LinearProgramming 语法没有 Maximize 那么直观, 不过对于大型的线性规划问题, 还是推荐大家来使用的.
上面就是利用Wolfram语言来帮助刘关张解决问题例子.
好了, 现在让我们在下一篇的课堂再见. 这里感谢各位每一位看到这里的老师和朋友!
Thanks!