EXCEL 求解线性规划问题

一、问题

Par公司是一家生产高尔夫的小型公司,它决定进入中高等价位的高尔夫袋市场。分销商对新产品十分感兴趣。在对整个高尔夫袋生产步骤进行详细调查之后,管理层明确了高尔夫袋的生产过程:·1）切割与印染原材料;2）缝合；3）·成型（插入支撑架、球棒分离装置等);4）检查与包装。

生产主管详细分析了生产过程的每一步,得出以下结论:生产一个中等价位的标准高尔夫袋需要用7/10小时切制与印染，1/2小时缝合,1小时成型,1/10小时检查与包装。生产一个高级袋则需要1小时切制与印染,5/6小时缝合，2/3小时成刑，1/4小时检查与包装。生产信息如下：

Par公司的生产还受各个部门生产时间的限制。经过对各个生产部门工作量的研究，生产主管估计未来3个月内每个部门可用的最大生间分别是:切割与印染630小时,缝合600小时，成型708小时,检查与包装135小时。

会计部门经过对生产数据、各种生产成本的分析得出了以下结论:生产一个标准袋的利润是10美元,生产一个高级袋的利润是9美元。我们现在可以为Par公司建立一个数学模型，来决定标准袋和高级袋各生产多少,以最大化产品的总利润贡献。

 二、建模

问题模型化(problem formulation）或称建模(modeling)，是将语言文字描述转化为数学描述的过程。可以说,这是一项艺术创造，只有通过不断的练习才能热练掌握。

描述目标:使产品的总利润贡献最大;

描述约束条件：一 共有4 个约束条件，它们制约着两种高尔夫袋的生产；

约束条件1:用于切割与印染的总时间必须小于等于切割与印染都所能承受的最大工作时间。

约束条件2:用于缝合的总时间必须小于等于缝合部所能承受的最大工作时间。

约束条件3:用于成型的总时间必须小于等于成型部所能承受的最大工作时间。

约束条件4:用于检查与包装的总时间必须小于等于检查与包装部所能承受的最大工作时间。

定义决策变量：Par 公司可以控制的输人有两个:①标准袋产量;②高级袋产量。设：

S----标准袋产量;

D----高级袋产量。

用决策变量写出目标：

公司的利润来源于两方面:1）生产S个标准袋所获得的利润；2）生产D个高级袋所获得的利润。则：

总利润贡献= 10S +9D

公司的目标是使总利润贡献最大，总利润贡献又是决策变量S和D的函数，所以Par公司的目标如下:

 

用决策变量写出约束条件：

约束条件1:用于切割与印染的总时间必须小于等于切割与印染都所能承受的最大工作时间。

生产S个标准袋和D个高级袋共需要的切割与印染时间是:

生产主管估计的总切割与印染的可用时间为630小时，所以以上的生产组合需要满足：

 

约束条件2:用于缝合的总时间必须小于等于缝合部所能承受的最大工作时间。

从上面的表中我们知道，每个标准袋的缝合时间是1/2小时，每个高级袋的缝合时间是600小时，即：

 

约束条件3:用于成型的总时间必须小于等于成型部所能承受的最大工作时间。

每个标准袋需要1小时成型时间，每个高级袋需要2/3小时成型时间，成型部最大的工作时间是708小时，所以

 

约束条件4:用于检查与包装的总时间必须小于等于检查与包装部所能承受的最大工作时间。

检查与包装一个标准袋需要 10小时，检查与包装一个高级袋需要1/4小时，而检查与包装部的最大时间是135 小时，所以

 

至此，我们已经列出了与4个部门有关的约束的数学关系。由于Par公司生产高尔夫袋的产量不能为负，加上一条约束：

 

综上，Par公司问题完整的数学模型如下:

s.t.

接下来我们需要找到合适的组合，既满足约束条件，又能使得函数的值最大。即经典的组合优化问题。

Par公司问题的数学模型为线性规划模型(linear programming model)。线性函数(linear function)是指函数中的每个变量都是分离的并且幂次为1。本文模型中约束和目标函数全部是线性的，因此我们称之为线性规划。

三、Excel求解

对于简单的线性规划模型，我们可以使用求解器Cplex、Gruobi、Lingo、Excel等进行求解，后续有精力的话会考虑更新求解器求解方法。本文主要介绍的是Excel求解线性规划问题。

3.1 模型编写

一般Excel里使用工作表建立线性规划模型:

Step1：输入问题的数据；

Step2：确定决策变量的位置；

Step3：输入约束条件，编写约束条件的计算公式；

工作表和计算公式如下图所示，实际计算时所有的计算公式前面要加=号。

没有添加过规划求解工具的童鞋，需要先在excel里添加规划求解工具箱。步骤如下:

3.2  用Excel求解

Step1：添加过规划求解工具之后，可以在excel菜单栏顶端选择规划求解。在弹出来的窗口填入目标函数对应的单元格B23,决策变量对应的单元格B21:C21；

Step2：添加约束，点击添加按钮，在弹出来的添加约束窗格，根据单元格引用添加约束条件，因为两个决策变量>=0，勾选使无约束变量为非负数；

Step3：选择单纯线性规划求解方法，进行求解。

求解结果如下，根据需求若袋数不能为小数，四舍五入取整，标准袋540袋，高级袋252袋。

选中你想要输出的报告，勾选制作报告大纲可以输出三种类型的报告，运算结果报告：

 敏感性报告：

​​​​​​​ 

极限值报告：

根据自身问题和需求可以对三种类型的报告进行分析。  下次我打算学习一下敏感度分析。

数据和结果已上传我的资源>excel求解线性规划，有不足之处多多交流！

参考书籍：《数据、模型与决策:管理科学篇(原书第13版)》 机械工程出版社