很久没更新过APS系列文章了，这段时间项目工作确实非常紧，所以只能抽点时间学习一下运筹学的入门知识，算是为以后的APS项目积累点基础。看了一些运筹学的书（都是科普级别的）发现原来我目前面对的很多排产、排班、资源分配和路线规划问题，都是运筹学上的典型案例。与此同时，除了继续使用Optaplanner来做我们的规划类项目外，还花点时间去研究了一下Google OR-Tools开源规划引擎，这是Google旗下的一个开源求解器，接下来我会专门写一些关于Google OR-Tools应用的文章，并与Optaplanner作些关联对比。

本篇先向大家展示一下两个规划工具，在求解线性规划问题上的应用方法，分别是Microsoft Office的Excel里的”规划求解”组件和Google Dos中的Spreadsheet上提供的Linear Optimization插件。这两个工具都可以作为规划问题的求解器。因为它们是以插件或软件功能形式提供的，在灵活性和扩展性方面限制还是比较大，但是因为不涉及软件开发的技能，普通用户都能很好地应用它们来解决一些现实业务中遇到的规则问题。

因为Google的Linear Optimization是Google文件服务中的Spreadsheet（Google提供的类似于Excel的电子表格程序），因为目前国内的网络情况（你懂的），访问它需要自己想办法，我们公司总部不在中国境内，所以我们的办公网络经过注册，是可以合法访问外界的；关于网方面不在本篇中讨论，大家自己科学解决就可以了。

       下面先给出本次我们需要求解的线性规划问题，其实在Optaplanner相关的文章中，详细介绍过关于NPC问题，普通线性规划问题很多并不是NPC问题，因为对于线性规划模型，还是有例如单纯形法等算法推算它的最优解的，而不是所有规划问题的时间复杂度都是O(a^n)或O(n!)的，大家要理解清楚两者的关系。

       我们要求解的问题跟很多运筹学教材或科普书籍上的例子一样，也是最简单的在确定的条件约束下，求最大利润下的产品生产方案问题。例如一家工厂生产两种产品，产品A与产品B，均需使用到三种资源，资源1、资源2和资源3。其中生产一件产品A，需要5个单位的资源1，4个单位的资源2，3个单位的资源3。生产一件产品B需要3个单位的资源1，8个单位的资源2，5个单位的资源3。一个产品A的利润是20，一个产品B的利润是25。库存中三种资源的存量为：280单位的资源1，580单位的资源2，360单位的资源3.见下表：

求：两种产品分别生产多少件，才能令到总利润最大？此时的利润是多少？

       以上问题是典型的线性规划问题，运筹学的同学可以通过单纯形法进行求解，但是这种方法对于没有运筹学背景的普通工程师来说，困难还是不小。即使我们学会这种办法，但遇到更复杂问题的时候，对我们来说其挑战还是相当大。因此，目前市上，或开源世界里，提供了很多解决此类规划问题的开源软件。但对于非IT人员来说，没有软件开发背景，很难利用这些开源软件工具写程序求解。因此，一些知名的办公软提供了相关的特性，让非IT专业人员直接使用其规划功能，输入数据即可快速求得答案。对各行业的生产、管理活动提供了极大的帮助。下面我们就以Excel和Google Spreadsheet两种工具中的规划求解功能，尝试求解上述问题。 

       要解决上述问题，就需要对问题进行线性规划建模，建立数学模型，以数学工具对问题的约束和目标进行归纳、抽象，用数学语言表达问题的本质意义。对于上面的问题我们的建模如下：假设产品A生产x件，产品B生产y件，才能让利润最大化。那么我们通过对问题的约条件和规划目标的分析，可以得出以下数学模型。

该模型表示：生产产品A和产品B所需的三种资源的总量，均不能超过每种资源的库存量；并且产品件数量必须是大于等于0的整数。规划的目标函数是找出两种产品的利润之和的最大值，并计算出获得该利润时，两种产品的产量分别是多少。

对于线性规划问题，其实可以通过单纯形法、对模型进行求解，从而得出z最大时的x与y的值。但此方法需要一定的数学知识，此范围的知识不在本文的讨论范围内，以后若有机会，我再简单介绍一下通过单纯形法对此模型求解步骤。但本人也不是运筹专业出身，估计也只是班门弄斧；因此，大家可以上网寻找更专业的运筹学资源，了解规划模型的解法。本文通过Excel下的规划求解功能，以及Google下的Spreadsheet中的Linear Optimization插件，对该规划模型进行求解，从而取得该生产安排问题的解。

       Excel提供了一个非常强大的组件用于解决此类规划问题，目前我还只尝试过线性规划问题，根据其资料显示，非线性规划也是可以解的。以后若有机会尝试一下其它规划问题再分享给大家。下面逐一展示这组件具体用法给大家。

因为规则求解功能默认不会出现在Excel的常用工具栏中，因此，需要从加载项目中把它加载出来才能使用。在Excel菜单栏中，选择【文件】->【选项】，在弹出的【Excel选项】窗口中，选择【加载项】页签，在列表中的【非活动应用程序加载项】（意思是说Excel目前有这些功能可以用，但还没有加载进去，所以不会显示在工具栏中）的其下方找到【规则求解加载项】，如下图.

在列表下方的【管理(A)】下拉框中选择【Excel加载项】，点击【“转到...】按钮，会弹加载项窗口，如下图。在【可用加载宏(A)】列表中，选中【规划求解加载项】，点击确定，窗口关闭。

在Excel的【数据】工具栏的最右则，你会看到【规划求解】的图标，即是刚才我们操作完成后加载进来的组件，如下图。

事实上它是Microsoft提供的一个求解器，该组件对应的文件在C:\Program Files (x86)\Microsoft Office\root\Office16\Library\SOLVER此文件夹下。该文件夹下有两个文件，分别是SOLVER.XLAM和SOLVER32.DLL, SOLVER.XLAM是一个Excel的宏文件，用于实现Excel对求解器核心SOLVER32.DLL的调用，因此SOLVER32.DLL应该就是这个求解器的核心程序动态连接库。

完成规划求解组件加载后，下面就可以将数学模型的各个常量、变量和约束关系填入Excel单元格中；先将两种产品和三种资源对应的使用数量建立一张二维表，如下表。

通过Excel及规划求解组件解答此问题步骤如下：

1.填入常量：上表中，产品A对资源1、资源2和资源3的要求量分别是5，4，3(即B2,B3,B4的值)，其单件利润为20(B5)。 同样方法将产品B对应的数量填入C２- C5单元格中。另外，对于三种资源的库存量，将其值填 入D2 - D4中。自此，模型中涉及的常量已经全部填写时表格。

2.根据数学模型，定义运算关系：本模型中，我们的目标是求得当z最大时变量x,y的值(x,y在运筹学的规划模型中被称为 决策变量；在Optaplanner中，它们被称作规划变量)。在Excel中每一个决策变量需要确定在一个单元格，以备参与接下来的规划计算，如上表的B6,C6单元格。在未启动规划的时候，这两个单元格直接填上0作为初始值即可。这两个代表决策变量的单元格在完成规划，找到答案后，运算结果值将会被填到对应的单元格中。

确定好这两个变量后，下一步需要考虑规划目标，也就是总利润最大化的目标，也需要为此目标值确定一个单元格，此单元格的值会在规划完成时，确定了B6和C6两件单元格的值之后计算出来。根据目标函数z = 20x X 25y的定义，此单元格的公式应为 ：B5 * B6 + C5 * C6，即两种产品的利润之和。我们把存储利润之和的值定在D7单元格，为了直观美观，我们把D7与E7合并。

确定了目标函数值的单元格和计算公式后，下一步需要处理约束条件，也就是产品的资源使用量与库存的约束关系。对于资源1，我们将E2确定为其资源用量，它计算公式应该是:B2 * B6 + C2 * C6,即两种产品对该资源的使用量之和。按相同的规则，设置E3 = B3 * B6+ C3* C6, E4 = B4 * B6 + C4 * C6.

通过上述两个步骤设定后，各个单元格的常量值、决策变量和运算关系已设定好。接下来就可以启动【规划求解】插件进行逻辑设定。在【数据】菜单项目中，最右则的【分析】组里，有一个【规划求解】图标，点击它，即可打开【规划求解】窗口(如下图)

以下讲解这些参数意义及其设置。

1.【设置目标(T)】项:该项目我们需要选定一个单元格，表示该单元格是本次规划活动需要计算的目标。通过问题描述和规划模型，我们得知该问题目标是求利润的最大值及取得该利润时两种产品的产量。也即模型中的目标函数z的最大值，及此时的x,y的值。在上表中D7就是存放这个目标函数的单元格，因此这里选中D7即可。在参数设置时，都是使用单元格的绝对地址，因此单元格地址前面都有$符号。

　　2.目标值中【到】项：该项用于设置对于目标函数的取值要求，可以看到它有【最大值】，【最小值】和【目标值】三个选项。其中【最大值】和【最小值】，表示目标函数往最大或最小两个极值方向求解，即最优解中，D7单元格的值是在满足约束条件情况下取得的最大值。而【目标值】则表示取得最优解时，目标函数值最等于或最接近于此值。本问题中的目标是求利润最大，所以我们选择【最大值】。

　　3.【通过更改可变单元格(B)】：该项表示在规划过程中求解器，通过改变哪些单元格的值，来获得结果，直到【目标值】所指的单远格（本例中的D7)中的值达到极值。对应到模型中，也就是x与y两个决策变量，本例中对应的单元格是B6和C6，分别表示产品A和产品B的产量。因此，选择B6和C6即可。

　　4.【遵守约束】：该项内容表示本次规划需要符合的约束条件，也就是模型中的s.t.部分(s.t. 是subject to的缩写)和各个不等式和各变量的范围条件。点击右则的【添加(A)】按钮，弹出【添加约束】窗口(如下图)，可以看到约束的表达方式非常简单，就是添加左右两则值的逻辑关系。

参照模型中的s.t.部分，和excel中的单元格位置关系，添加它们的关系即可。例如对于资源1，s.t.中的约束条件5x * 3y