线性规划理论在实际问题中的应用

1、线性规划理论在实际问题中的应用内容摘要 :企业是一个复杂的系统 ,要研究它必须将其抽象出来形成模型。如果将系统内部因素的相互关系和它们活动的规律用数学的形式描述出来，就称之为数学模型.线性规划是运用数学模型 ,对人力、设备、材料、资金等进行系统和定量的分析，使生产 力得到最为合理的组织，以获得最佳的经济效益。应用线性规划问题解决实际问题， 最重要的一个步骤就是首先要建立实际问题的线性规划问题的数学模型 .一、线性规划问题及其数学模型二、线性规划模型的具体分析及应用 Excel 求解线性规划问题三、线性规划的局限性一、线性规划问题及其数学模型（一）线性规划的模型决定于它的定义，线性规划的定义是：

2、求一组变量的值， 在满足一组约束条件下，求得目标函数的最优解。根据这个定义,就可以确定线性规划模型的基本结构。（ 1）变量变量又叫未知数， 它是实际系统的未知因素 ,也是决策系统中的可控因素， 一般称为决策变量，常引用英文字母加下标来表示 ,如 Xl,X2，X3，Xmn 等。（2）目标函数将实际系统的目标，用数学形式表现出来，就称为目标函数，线性 规划的目标函数是求系统目标的数值，即极大值，如产值极大值、利润极大值或者极 小值，如成本极小值、费用极小值、损耗极小值等等。（3）约束条件约束条件是指实现系统目标的限制因素。它涉及到企业内部条件和外 部环境的各个方面 ,如原材料供应、设备能力、计划指

3、标、产品质量要求和市场销售状 态等等，这些因素都对模型的变量起约束作用，故称其为约束条件。约束条件的数学 表示形式为三种，即 二二、W线性规划的变量应为正值，因为变量在实际问题中所代 表的均为实物，所以不能为负。（二）在经济管理中，线性规划使用较多的是下述几个方面的问题：（1）投资问题确定有限投资额的最优分配 ,使得收益最大或者见效快。（2）计划安排问题 确定生产的品种和数量 ,使得产值或利润最大，如资源配制问 题。（3）任务分配问题 分配不同的工作给各个对象（劳动力或机床 ），使产量最多、 效率最高，如生产安排问题。（4）下料问题 如何下料，使得边角料损失最小。（5）运输问题在物资调运过程中

4、，确定最经济的调运方案。（6）库存问题如何确定最佳库存量 ,做到即保证生产又节约资金等等。（三）应用线性规划建立数学模型的三步骤：（1）明确问题，确定问题，列出约束条件。（2）收集资料，建立模型。（3）模型求解（最优解） ，进行优化后分析。 其中，最困难的是建立模型，而建立模型的关键是明确问题、确定目标，在建立 模型过程中花时间、花精力最大的是收集资料。(四) 线性规划的数学模型的一般形式为 :目标函数 max (min) z=c1 Xi +c2 X2+cn Xn 满足约束条件：all Xi +a12 X2,+ +a1nXn< (=,>) bl a21 Xi +a22 X2,+ +

5、a2nXn <(= ,>) b2ami Xi +am2 X2+amn Xn < (=,> ) bmXi, X2,Xn > 0线性规划模型的矩阵形式：目标函数 max( min) Z = CX约束条件AX < (=,)b其中，C=(c1, c2,cn) , X=( Xi, X2,Xn) Tb=(b1, b2,bm)TGil, a12,a1n 'A= a21, a22,a2n乜mi, am2,amn 丿二、线性规划模型的具体分析及应用Excel求解线性规划问题我们来看生产计划问题：生产计划是控制生产装置运行的命令，要利用有限的资源获得最大的经济效益，就必

6、须制定最佳生产计划。随着公司生产装置的不断增多，生产计划的制定变得越来越 复杂.采用现代管理技术，建立数学模型，利用电子计算机求解 ，很容易得出最优生产计 划。下面举一案例说明(本案例出自运筹学，林齐宁,北京邮电大学出版社，2003 年，P7)某工厂计划用现有的铜、铅两种资源生产 A、B两种型号的电缆。A、B两种型号 的电缆单位售价分别为6万元和4万元。市场对A型电缆的需要量无限制，而对B电缆 的最大需求量为7单位。生产单位产品A、B两种型号电缆对铜、铅的消耗量及可利 用的铜、铅数量如下表所示：表1 ：基本信息表A型电缆B型电缆资源提供限量1消耗：铜(吨)2110消耗：铅(吨)118产品需要限

7、量7售价(万元)64工厂应该如何让安排生产，才能使工厂总收入最大?解答过程如下：(1) 决策变量设x1 , x2分别代表A、B两种型号电缆的生产量,f(x)为工厂总收入(2) 目标函数本问题的目标是工厂收益最大值Maxf (x)=6 X i+4X2(3) 约束条件:A型电缆B型电缆资源提供限量消耗:铜（吨）2110消耗：铅（吨）118产品需要限量7售价（万元）64则上述问题可以用如下数学模型（线性规划模型）来表示:Obj:Maxf（x）=6 X1+4X22 X1+X2W 10铜资源约束s.t. X1+X2 < 8铅资源约束X2< 7产量数量约束Xi, X2>0产量质量约束用E

8、xcel辅助计算求解。首先,根据问题建立电子表格模型具体步骤如下：1。收集问题的数据。2。在电子表格的数据单元格中输入数据。3。确定对活动水平需要作出的决策并且指定可变单元显示这些决策。4。确定对这些决策的约束条件并引入需具体化这些约束条件的输出单元格。5。选择要输入目标单元格的完全绩效测度。6。使用SUMPRODUC数为每个输出单元格（包括目标单元格）输入合适的值然后,建立了起电子表格模型：A1.5 .CDEF1A型电统连源提供陶量取大用里2消孤洞（吨）2110>0 W消耗；铅（吨）11>o n4产品需餐限重756土产量007售价（万元<54总收入Q再进行规划求解:设星日标

9、单元箱:HIT 窗等于：堆大值O最小值©) o值討o 可变单元格:抑拥：虻$E阳推测峋束QD：丨脈加® ) 更改© 求解王亍I关用J匮项1jBter$C$6 >= 0ICJ6 <= JC54$&$2；$D$3 >= $F$2：$F$3险部重说® 帮助规划求解的选项对话框:最后,保存求解结果：規划求解结皋报告麴我解找到一解可满足所有的约束及量忧®保存觊划求解箱果.卄更复为原值0)i确定 助肖 假荐方葉盘)帮助最终结果如下图所示r - aBCDEF1A型电缆F型电缆资源提供限量曰m曰取大用里22110>r 103消耗

10、:铅（吨）118>4严品需要限量75>&二疔量2 67售价（万元）64总收入368可以利用Excel中的“规划求解”功能可以直接到“敏感性分析”，利用该报告可以很方便地进行灵敏度分析：J变单兀格单元格名字终递减 ft建目标式 系数允许的 増量允许的$B$6注产量A型电缆20622$C$6护量>60421阴影约東允许的九许的单元格名字值价格限制值増量减量W$2梢耗*铜吨）贺源提供辰量10-201&$D$M梢耗:铅（吨）资源提洪限量8-2030.5敏感性报告的内容由两部分组成：（1）位于报告上部的“可变单元格"部分反映了目标函数中的系数变化对最优解产 生

11、的影响第一列“单元格”是指决策变量所在单元格地址。 第二列“名字”是这些决策变量的名称 第三列“终值”是决策变量的终值，即最优解。第四列是“递减成本”，它的绝对值表示目标函数中决策变量的系数必须改进多 少，才能得到该决策变量的正数解第五列“目标式系数”是指目标函数中的系数。第六列与第七列分别是“允许的增量"和“允许的减量”它们表示目标函数中的 系数在允许的增量和减量范围内变化时，最优解不变。（2）位于报告下部的“约束”部分反映了约束条件右端值变化目标值产生的影响。 目标函数系数同时变动的情况：当各个系数变动的百分比之和小于 100%时，最优解不发生变化；当各个系数变动的百分比之和等于

12、 100时，最优解不发生变化； 当各个系数变 动的百分比之和大于 100时，不能确定最优解的变化，可能改变，也可能不变 . 约束 右端值同时变动：当各个右端值变动的百分比之和小于 100时 , 影子价格有效 ; 当各个右端值变动的百分比之和等于 100%时，影子价格有效； 当各个右端值变动的百分比之和大于 100时 , 不能保证影子价格依然有效。三、线性规划的局限性公司生产的复杂性使得手编计划的工作极其复杂 , 手编计划的工作量大， 而且更为 重要的是很难甚至无法实现优化，会给公司造成很大的机会损失。采用线性规划模型 制定公司计划和进行决策分析是可行的、必要的 . 在这个效率优先的时代 ,众多

13、领域中， 但凡涉及最优解的问题，首先考虑的方法即是线性规划。要建立一个切合实际的线型规划模型，需要工程技术人员、财务管理人员等的通 力配合，否则会失去很多有用的信息。线性规划作为运筹学的一个分支发展至今，从 建立模型到求的最优解的整个过程 ,都有一套发展较为完备的体系和理论 .涉及到生产 计划以及类似的问题时，线性规划显然是首选的方法。然而，线性规划并不是没有其因为方法本身或者问题本身超出方法谈到的要求所产 生的某些局限性。非常明显的一点是 ,线性规划模型实质上还是一个静态的模型 .事实上， 随着约束条件的变化，目标函数中的一些指标常常并非一成不变。举例来说,在考虑生产计划，即如何选择产业结构使生产成本最低的时候，成本系数实质上是一个会根据产业 结构和模式之变化而难以绝对保持静态的变量， 这就势必导致模型的理想化。 另一方面， 生产过程也不是一个绝对静态的过程，即产业结构本身，或者说约束条件中