线性规划应用.doc

精品文档线性规划应用信息管理与信息系统（财会） 孙燕 201101002030摘要：线性规划是运筹学中应用最广泛的方法之一，也是运筹学中的最基本的方法之一，网络规划、整数规划、目标规划和多目标规划都是以线性规划为基础的。线性规划是解决稀缺资源最优分配的有效方法，使付出的费用最少或获得的利益最大。它的研究对象是有一定的人力、财力、资源条件下，如何合理安排使用，效益最高；某项任务确定后，如何安排人、财、物，使之最省。它要解决的问题的目标可以用数值指标反映，对于要实现的目标有多种方案可以选择，有影响决策的若干约束条件。通过该课题的设计，可以加深对运筹学、最优化方法、线性规划、非线性规划等的认识，提高对这些知识的综合运用，提高利用灵敏度分析解决各种实际问题的能力。本文章主要介绍了线性规划模型在实际生活中的应用，其中包括解线性方程组的各种方法，如图解法、单纯形法以及对偶单纯形法等等，以及简单介绍了有关灵敏度分析的方法。由于许多问题仅仅利用线性规划的方法还不足以解决，因此用到了对偶理论，也因此引出了对偶单纯形法。对偶规划是线性规划问题从另一个角度进行研究，是线性规划理论的进一步深化，也是线性规划理论整体的一个不可分割的组成部分。灵敏度分析是对线性规划结果的再发掘，是对线性规划理论的充要应用。由于知识储备和资料查阅的有限性，线性规划的重要作用及应用不能一一分析，还存在许多不足之处有待进一步改进和提高。关键词：线性规划 单纯型表法 对偶单纯型法 灵敏度分析 图解法 数学模型 线性规划主要在两类问题中得到应用：一是在人力、物力、财力等资源一定的条件下，如何使用它们完成最多的任务；二是做一项任务，如何合理安排和规划，能以最少的人力、物力、资金等资源来完成该项任务（即少投入，多产出）。在这里，重要的是建立线性规划的数学模型，一个实际问题的数学模型，是依据客观规律对该问题中我们所关心的那些量进行科学的分析后所得出反映这些量之间本质联系的数学关系式。线性规划问题的数学模型的一般形式为：minmax=1X1+2X2+nXn() sta11X1+a12X2+a1nXn*b1a21X1+a22X2+a2nXnb2am1X1+am2X2+amnXnbm() Xj * 0 j=1,2n. 其中 ajj,bjj,cjji=1,2m;j=1,2n均为已知常数， *表示“”“”或“=”，X1，X2,，Xn称为决策变量，为目标函数。()和（）称为约束条件，（）中的每一个式子均称为线性约束，（）中若要求变量0的条件称为非负条件。这说明，线性规划模型由三部分构成：（1）一组决策变量X1，X2,，Xn通常要求它们非负，但在某些实际问题中也会出现变量为负数的情况（2）表示所给问题最优化指标的目标函数（3）一组约束条件正因为目标函数和约束条件都是关于决策变量的线性表示式，所以，这种数学模型称为线性规划模型，相应的问题叫做线性规划问题。若（）中的不等式都为等式且（）中的变量为非负，则叫做线性规划模型的标准型。解任一线性规划问题通用的方法是单纯形法，但对于某些特殊的线性规划问题也有特殊的解法，这样更加简便。一、单纯形法、对偶理论与灵敏度分析的应用问题提出 在生产管理和经营活动中经常提出一类问题，即如何合理利用有限的人力物力财力等资源，以便得到最好的经济效果。 某工厂在计划期内要安排生产甲、乙两种产品，已知生产单位产品所需的A、B两种原材料的消耗量，见下表，试回答下面问题： 甲 乙 资源限量(kg)原材料的成本（/kg）原材料A 2 4 160 1原材料B 3 2 180 2 单价/元 13 16（1）应如何安排生产计划使该工厂获得的利润最大？ （2）原料A、B的影子价格各是多少？那一种更珍贵？ （3）如果乙产品价格达到20元/每件，方案会发生什么变化？（4）现有新产品丙可投入开发，一直对两种原材料的消耗量分别为3和4，问该产品的价格至少应为多少才值得生产？问题分析1. 问题一：应如何安排生产计划使该工厂获得的利润最大？ 该问题为合理利用有限的人力、物力、财力等资源，以便得到最好的经济效果的问题，应该运用线性规划原理，建立数学模型，再运用单纯型法或图解法求解。 2. 问题二：原料A、B的影子价格各是多少？那一种更珍贵？ 影子价格的经济意义是指在其他条件不变的情况下，单位资源变化所引起的目标函数的最优值的变化，代表A、B这两种资源的经济估价，影子价格可运用对偶单纯型法可求得。 3. 问题三：如果乙产品价格达到20元/每件，方案会发生什么变化？ 乙产品价格变化，表示乙产品的价值系数变化，运用灵敏度分析，判断最终经济效益是否会发生变化。 4. 问题四：现有新产品丙可投入开发，一直对两种原材料的消耗量分别为3和4，问该产品的价格至少应为多少才值得生产？ 分析在原计划中是否安排一种新产品，运用灵敏度分析，通过单纯型表法，求得新产品 的价格，使总的经济效益会增加。 符号说明X1工厂在计划期内安排生产甲产品的数量。X2工厂在计划期内安排生产乙产品的数量。工厂总的经济收益。模型建立建立线性规划模型目标函数：max =13X1+16X2-2X1+4X2-23X1+2X2即：max =5X1+8X2条件约束：st2X1+4X21603X1+2X2180X1,X20模型求解1问题一：应如何安排生产计划使该工厂获得的利润最大？运用单纯型表法求解，（1）写出原模型的标准型：max =5X1+8X2+0X3+0X4 st2X1+4X2+0X3=1603X1+2X2+0X4=180X1,X2,X3,X40（2）得到原始单纯形表：Cj5800CBXBbX1X2X3X40X316024100X41803201表1（3）对原始单纯形表进行迭代计算得：Cj5800iCBXBbX1X2X3X40X31602410400X4180320190 05800表2Cj5800iCBXBbX1X2X3X48X2400.510.250800X410020-0.5150 32010-20表3Cj5800iCBXBbX1X2X3X48X215010.375-0.255X15010-0.250.5 37000-1.75-0.5表4（4）计算结果是：工厂在计划日期内安排生产甲产品的量为50，生产乙产品的量为15。所获得的最大利润为370元。2 问题二：原料A、B的影子价格各是多少？那一种更珍贵？由表1的最终结果表4得：原料A的影子价格是2.25、B的影子价格是0.5，所以原料A更珍贵。3 问题三：如果乙产品价格达到20元/每件，方案会发生什么变化？乙产品价格达到20元/每件；即目标函数中乙产品的价值系数改变。目标函数变为：max =13X1+20X2+2X1+4X2-23X1+2X2 即：max =5X1+12X2所以最终单纯形表变为：Cj51200iCBXBbX1X2X3X4X215010.375-0.25-X15010-0.250.5100 37000-3.250.5表5Cj51200iCBXBbX1X2X3X412X2400.510.2500X410020-0.51 370-10-30表6由表6可得如果乙产品价格达到20元/每件，工厂的生产方案为生产甲产品的量为0，生产乙产品的量为40。4 问题四：现有新产品丙可投入开发，一直对两种原材料的消耗量分别为3和4，问该产品的价格至少应为多少才值得生产？假设新产品丙的价格为3，则目标函数变为：max =13X1+20X2+3X3-2X1+4X2+3X3-23X1+2X2+4X3即：max =5X1+8X2+3-11X3条件约束：st2X1+4X2+3X31603X1+2X2+4X3180X1，X2，X30所以产品的技术向量为3=(3,4)，然后计算最终表中对应X3的检系数为3=3-B-13=3-11-1.75,0.5(3,4)=3-18.25当30 时，说明新产品丙值得生产。即318.25，所以新产品丙的价格至少应为18.25。分析结果1 问题一：应如何安排生产计划使该工厂获得的利润最大？工厂在计划日期内安排生产甲产品的量为50，生产乙产品的量为15。所获得的最大利润为370元。2 问题二：原料A、B的影子价格各是多少？那一种更珍贵？原料A的影子价格是2.25，B的影子价格是0.5，所以原料A更珍贵。3 问题三：如果乙产品价格达到20元/每件，方案会发生什么变化？工厂的生产方案为生产甲产品的量为0，生产乙产品的量为40。4 问题四：现有新产品丙可投入开发，一直对两种原材料的消耗量分别为3和4，问该产品的价格至少应为多少才值得生产？新产品丙的价格至少应为18.25。二、图解法的应用问题提出某养鸡场有1万只鸡，用动物饲料和谷物饲料混合喂养。每天每只鸡平均吃混合饲料0.5kg，其中动物饲料不能少于谷物饲料的15。动物饲料每千克0.9元，谷物饲料每千克0.28元，饲料公司每周仅保证供应谷物饲料50000kg，问饲料怎样混合，才是成本最低。符号说明X为每周需用谷物饲料数量Y为动物饲料数量元每周总的饲料费用模型建立由已知条件得到的线性规划模型为：min=0.28X+0.9YstX+Y35000Y15XX50000X0，Y,0模型求解这是二维线性规划问题，可用图解法求解，先作出满足约束条件的平面区域,即可行域S，如下图所示： YO X AY=15X 50000X+Y=35000图1再作直线0.28X+0.9Y=0,平行移动此直线，得到过可行域且离原点最近的直线是经过直线X+Y=35000和直线Y=15X的交点875003,175003的直线，从而得到饲料混合的最佳喂养方案,即当谷物饲料X=875003,动物饲料Y=175003时,饲料的混合既能达到饲养的要求又能使费用最低。也就是说,谷物饲料和动物饲料按5:1的比例混合是最佳方案。 三、总结体会通过上例分析，我清楚地了解线性规划及其建模的进一步分析对合理安排和规划资源，来完成任务的重要意义。对线性规划这一方法有了更深的了解，能够熟练掌握这一类问题的解决思路及方法。同时，在例题分析中也得出了一些认识：1运用用数学模型解决现实中的问题，简单合理，清晰明了。2在灵敏度分析中，有时需要用对偶单纯型法，这样的可使问题的处理简单化。对偶单纯型法的局限主要是，对大多数线性规划问题，很难找到一个初始可行基，因而这个方法在求解线性规划问题时很少单独应用。3用建立线性规划的模型解决现实问题必须满足：（1） 要求解得目标函数能用数值指标来反映，且为线性函数；（2） 存在多种方案及有关数据；（3） 要求达到目标是在一定约束条件下实现的，这些约束条件可以用线性式或不等式表示；（4）要完成一项确定的任务