初章，什么是规划问题-一一网

这是我参与更文挑战的第1天
从今天开始会推出关于OptaPlanner学习的一系列文章，一方面想跟大家共同学习OptaPlanner规划问题的求解，另一方面也想多多认识志同道合的朋友。也希望这一系列文章，能对一些中小型公司在面对规划问题求解的时提供一些帮助，而减少对专业算法团队的投入，从而可以降低一些“智能化”的工作成本。

内容概要

开张首篇，主要是对几个大的概念进行学习，会有些枯燥，希望大家能耐得住心看完，这对后续学习OptaPlanner很关键。

介绍

有句老话“吃不穷，喝不穷，算计不到就受穷”，可见凡事都要有计划的进行。计划是对一项确定的目标，在有限定资源下对未来的活动做出安排。代表这一类的问题，可以叫“规划问题（Planning Problems）”。这类问题规划目的都是一样的，在有限的资源（时间、金钱、人员）的情况下，做更多更好的事情。通俗的来说就是，既想马儿跑又想马儿不吃草，既想花钱少又想多办事儿，是不是很像咱们程序员的遭遇。
举例看下这类问题的代表场景：

人员排班：护士排班、客服排班等；
日程安排：安排会议、约会、维修工作等；
课程安排：安排课程、考试；
车辆路线：规划车辆路线，如何安排路线可多运货物，减少路程；
装箱计算：在集装箱、卡车、船舶和存储仓库中装入物品，如何安排可装入最多货物；
工作车间调度：规划汽车装配线，机器排队计划，劳动力任务计划；
切割库存：在切割纸张、钢铁、地毯时，尽量减少浪费。
金融优化：投资组合优化，风险分散；

规划问题是什么

从“介绍”一章，大家已经大致了解了，规划问题的定义，以及在我们的生活当中那些场景是规划问题。在这一篇章，我们来学习一下规划问题的几个特征。
每一个规划问题有一个最优化的目标，基于有限的资源和特定的约束条件。最优结果可以是任何数量的东西，例如：

利润最大化：最优目标会带来尽可能高的利润。
路程最小化：最优目标对可减少站点的建设数量。
员工或客户的满意度最大化：最优目标优先考虑员工或客户的需求。

而要实现这些目标，要依赖于可用的资源，例如。

我只有5名员工。
只有一个月的时间。
预算是20W以内。
固定资源，例如，机器、车辆、计算机等。

这些资源可以理解成，我们现有的固定资源，利用有限资源得出最优化的结果，其过程就是最优化求解过程，但是在寻优过程当中，还有一些制约的因素在里面。例如：一个人的工作时间范围、对机器的熟练度，路线中各站点的路线距离等；

NP问题

一个规划问题是NP-complete的或NP-hard问题，上面所有的用例都可能是NP-complete/NP-hard，通俗点说就是。

在合理的时间内找到一个满足问题各项条件的方案是很容易的。
没有银弹（具有极端有效性的解决方法，杀招）可以在合理的时间内找到一个问题的最优解(*)。

有些问题存在最优解例如：N皇后，有些问题无法证明它最后的结果就是最优解，所以大多数面对NP问题我们只需要一个接近最优解的结果就可以了。
通常简单的算法是无法解决这里问题的，例如：
穷举算法，还举N皇后，4个皇后有256（4^4）个组合，8皇后有16777216个组合，如果是100个皇后呢？
一个快速的算法，例如：在背包中，每次先把最大的物品放进去，但最后的结果一定不是最优的结果。

软硬约束

一般情况下，每个规划问题至少有两个层级的约束：
硬约束：在任何情况下硬约束不允许打破，例如：一个老师不能同时去两个教室上课。
软约束：尽可能的情况下不去打破，例如：英语老师不喜欢在周五下午上课。
从这里看，无论软硬约束都是一个消极的约束，不被打破类似于红牌、黄牌。但实际场景中是存在积极约束或者是奖励的约束，例如：数学老师喜欢在周一早上上课。

评分机制

用分值来表示每个解决方案是最公平的方式，假设我们把各个约束条件增加分值，最后的解决方案都会有一个分值。
每一个规划问题，都存在大量的解决方案，可以分为以下几类：

可能的解决方案：每个解决方案都可以作为一个规划问题的解决方案，无论是否打破软/硬约束，其结果都是一个解决方案，只不过这类解决方案是没有价值，而且在大多数的结果都是没有价值的。
可行的解决方案：这类结果是打破软/硬约束的，但是有时候可能没有可行的解决方案。例如：每周需要一个不同的人进行值班，但是我只有4个人。
最优解决方案：一个最优解是最高分数的解，每个规划问题可能存在一个或者几个最优解（N皇后）。
最佳方案：最佳方案的限定条件是在于时间，在规定时间内找到一个可行的最高分数的解，就是一个最优解。例如：我需要在1分钟内对一个月进行排班。