玩三国, 学【离散优化建模】基础篇 01

离散优化建模 基础篇

图片和内容摘自离散优化建模基础篇, MOOC由香港中文大学开发, 推荐各位到 Coursera 边看视频边学习, 链接见阅读原文.

东汉末年，朝政腐败、 民不聊生 暴乱四起。

刘备、 关羽和张飞立志平定暴乱 在桃园向天宣誓结拜为兄弟. 一位仙人赐三位名为神算法板的宝物来解决遇到的各种问题, 由此开始了三国之旅.

第 1 步

刘关张打算从冯、 刘、 赵、 简四家村庄招兵, 四个村庄壮丁的战斗能力、 雇佣金和数量各有不同 刘备只有10000两用于招兵 他希望能善用这笔钱筹备战斗力尽可能强大的军队.

关羽认为兵贵在精，提议尽量雇佣战斗力强的简家村士兵. 张飞则认为兵贵在多 提议尽量雇佣雇佣金最低的冯家村士兵, 我们能找到更好的招募方法么?

这样需要列出相应的目标方程和约束条件来(下面就是李浩文教授来):

用数学语言来建立模型描述就是下面的式子:

用 Wolfram 语言来求解, 可以看到跟上面的数学式子非常类似, 这样也易于检查所列出式子是否正确:

可以看到最后结果, 也就是最大的战斗力之和为 4752 . 尽管从 4 个村子中招募的人数跟用 MiniZinc 软件不同, 但最优解完全一样的.

第 2 步

借助神算法板招兵后，三兄弟开始训练军队 由于训练艰苦，有士兵难以承受，就借机逃跑 三兄弟发觉有士兵走失后，就计划重新整理 统计士兵人数。将士兵排成五列，发觉有两名剩余 将士兵排成七列，则有两名剩余 再将士兵排成 12 列，则有一名剩余

能否据此算出士兵的数量呢? 不难啦, 拿出 Wolfram语言出来:

第 3 步

刘关张三人向富商张世平借用马匹, 张世平向三兄弟出题，并承诺若能解答，就应许相助.

张世平要求刘备使用不多于四种颜色为汉室地图上色，而相邻的州 不可用相同的颜色。

我们看看雍州这个例子吧 雍州(Yong)跟凉州(Liang)在旁边 所以呢，它们不可以有相同的颜色 所以呢，我们的约束就要求它们的值不相等的 雍州跟益州(Yi)也是 相邻，所以呢，我们也要求它们的值是不相等的 也有雍州跟荆州(Jing), 雍州跟这个泗州(Si)，我们也相同，有类似的约束 然后其他的约束呢.

我们将 4 种颜色用 1 到 4 整数来进行替代, 方便计算. 根据题意列出约束条件来, 分为两个部分的约束条件, 因为解不止一个(共3888个解), 所以我们只解出来一个就好了, 这里用到了 FindInstance 指令.

可以将地图着色进行观察, 这里只是用着色的圆盘来演示了:

上面就是利用Wolfram语言来帮助刘关张解决问题例子, 往后还有更多的难关啦, 感兴趣赶紧参加此次课程吧, 还来得及哦.

好了, 现在让我们在下一篇的课堂再见. 这里感谢各位每一位看到这里的老师和朋友!

Thanks!