运筹学（三）_北京新东方前途出国的博客-新东方前途出国

线性问题（也叫线性规划）：F(X)和G(X)都是线性的函数，就是都能写成ax+by+cz+d这种形式，而且里面的未知数都是实数。下图是个例子。这是最最简单的形式，用现在的计算机来解，大部分线性问题都是一眨眼的功夫。当然也有规模很大的，我在FB工作的时候，有个同事就解过一个有几十万个变量和几百万个限制条件的问题，服务器解起来也要一段时间。后来我把它重新建模，同样一个问题，变量只剩几千个，限制条件只剩几万个，电脑一下就解出来了。

有整数限制的线性问题（也叫整数规划）：也就是说F(X)和G(X)都是线性的函数，但是有的未知数是整数，甚至只能是0或者1，用来描述像安排几个人去做某个工作（不能安排半个人），或者安排某个人去做或者不做，不能只做1/3。把上面那个例子的其中一个未知数规定只能取整数，就变成整数规划了。这类问题大部分比线性问题难，有一些可以巧妙地转化成线性问题；如果不能，搞不好问题规模比较大的，你长命到百岁都还没算完。

非线性问题（也叫非线性规划）：也就是说F(X)和G(X)中有不是线性的函数。这里头水也比较深，基本上可以理解成爬山，山的形状各种各样，你要爬到最高的地方去。

有的问题很简单，只有一座山，而且只要你每步往上走，一定能爬到顶。
有的问题难一点，山的那边还有山，你不爬完所有山永远不知道那座山最高。。。
还有的问题更恶心，你每走一步都漆黑一片，看不清周围，看不到方向，只能靠试和靠猜，一脚踏进坑里也很正常。

还有一类也算是线性或者非线性问题的，我单独拿出来，因为比较特殊：

最优控制问题：G(X)都是随时间变化的函数或者方程，只要知道输入什么，就知道输出什么，知道整个系统是怎么随时间变化的。我们的目标是优化这个系统的某些随时间变化的指标。例如说我们的室温是随时间变化的，我们的空调机可以控制每时每刻制冷的强度，来保证整个白天的室温都在一定范围内，而且最省电。

除了上面提到的这些确定性的，给出X就清楚能算出F(X)和G(X)的问题，也有一些带不确定性的问题。例如，对于菜市场店铺而言，给定明天买菜的人的需求量满足一个概率分布，在能卖完所有菜的概率不小于80%的限制条件下，最大化盈利。这种问题，F(X)和G(X)就会有部分是用概率来表达，或者跟概率相关的东西，例如期望值和方差，来表达。

一般涉及到不确定性的都是比较复杂的问题。当然，也有很多好玩的问题，例如卖报童问题，排队论，生灭过程等。例如说排队论，就是可以用来优化银行的排队系统，看怎么样才能尽快服务好排队的客户。

（转载自公众号【运筹之学，作者【滴水】】）