《第1章线性规划(1-2)》由会员分享，可在线阅读，更多相关《第1章线性规划(1-2)（52页珍藏版）》请在金锄头文库上搜索。
1、第一章 线性规划 线性规划广泛应用于经济领域，包括生产计划、广告媒体选择、投资决策、资本预算、人事安排、产品配比问题等等，线性规划是进行管理决策的最有效的方法之一。【问题导入问题导入】 生产优化生产优化产品组合问题产品组合问题n n问题背景问题背景n n和风家具有限公司生产高质量特色系列的茶和风家具有限公司生产高质量特色系列的茶几和餐桌，由于质量过硬，造型优美时尚，几和餐桌，由于质量过硬，造型优美时尚，部分产品不仅畅销国内，还远销海外，为公部分产品不仅畅销国内，还远销海外，为公司创造了不菲收益。最近，公司的制造总裁司创造了不菲收益。最近，公司的制造总裁李文碰到了一件棘手的问题：总公司旗下有李文
2、碰到了一件棘手的问题：总公司旗下有三个分厂，由于某些产品销售量的下降，高三个分厂，由于某些产品销售量的下降，高层管理部门决定调整公司的产品线。层管理部门决定调整公司的产品线。【问题导入问题导入】 生产优化生产优化产品组合问产品组合问题题n n如果征得管理部门的同意，不盈利的产品要如果征得管理部门的同意，不盈利的产品要停止生产并撤出生产能力来生产研发部刚开停止生产并撤出生产能力来生产研发部刚开发的两个新产品：绿色时尚系列茶几发的两个新产品：绿色时尚系列茶几A A 和餐和餐桌桌B B。现在管理部门要考虑下列两个问题：现在管理部门要考虑下列两个问题：1.1.公司是否应该生产这两个新产品？公司是否应该
3、生产这两个新产品？2.2.如果生产，两个新产品的产品生产组合如何如果生产，两个新产品的产品生产组合如何？每周分别生产多少数量？每周分别生产多少数量？【问题导入问题导入】 生产优化生产优化产品组合问题产品组合问题n n为解决上述问题，我们首先要收集研究所需的信息：每家工厂的生产能力；生产每一产品各需要每家工厂多少生产能力；每一产品的单位利润。表1-1总结了收集到的数据。 两种新产品的有关数据两种新产品的有关数据 工 厂单位产品的生产时间每周可得时间茶几餐桌1231小时03小时02小时2小时4小时12小时18小时单位利润（元）300500【问题导入问题导入】 生产优化生产优化产品组合问产品组合问题
4、题由上述分析可建立本问题的线性规划模型下：o.b. max 300X+500Y (利润最大化)s.t. X4 (工厂1的工时约束) 2Y 12 (工厂2的工时约束) 3X+2Y 18 (工厂3的工时约束) X， Y 0 (非负约束)第一节第一节 线性规划问题及其数学模型线性规划问题及其数学模型 线性规划线性规划线性规划线性规划是运用数学模型，对人力、设备、材料、资金等进行系统和定量的分析，使生产力得到最为合理的组织，以获得最佳的经济效益。1.1线性规划的模型结构 规划问题的数学模型由三个要素组成：规划问题的数学模型由三个要素组成：（1 1）变量，或称决策变量，是问题中要确定的未知量，）变量，或
5、称决策变量，是问题中要确定的未知量，它用以表明规划中的用数量表示的方案、措施，可由它用以表明规划中的用数量表示的方案、措施，可由决策者决定；决策者决定；（2 2）目标函数，它是指对问题所追求的目标的数学描）目标函数，它是指对问题所追求的目标的数学描述，按优化目标分别在这个函数前加上述，按优化目标分别在这个函数前加上maxmax或或minmin；（3 3）约束条件，指决策变量取值时受到的各种资源条约束条件，指决策变量取值时受到的各种资源条件的限制，通常表达为含决策变量的线性等式或不等件的限制，通常表达为含决策变量的线性等式或不等式。式。1.1线性规划的模型结构 实际问题中线性的含义：实际问题中线
6、性的含义： 一是严格的比例性，一是严格的比例性， 生产某产品对资源的消耗量和生产某产品对资源的消耗量和可获取的利润，同其生产数量严格成比例；可获取的利润，同其生产数量严格成比例； 二是可叠加性，如生产多种产品时，可获取的总利二是可叠加性，如生产多种产品时，可获取的总利润是各项产品的利润之和，对某项资源的消耗量应等润是各项产品的利润之和，对某项资源的消耗量应等于各产品对该项资源的消耗量的和。在实际处理不符于各产品对该项资源的消耗量的和。在实际处理不符合条件的问题时，为方便可将其看作近似满足线性条合条件的问题时，为方便可将其看作近似满足线性条件。件。线性规划的数学模型的一般形式为：目标函数 max
7、(min) z=c1 x1+c2x2+cn xn满足约束条件: a11x1+a12x2+a1nxn (,) b1 a21x1+a22x2+a2nxn (,) b2 . . am1x1+am2x2+amnxn (,) bm x1, x2, ,xn 01.1线性规划的模型结构线性规划模型的矩阵形式：线性规划模型的矩阵形式：目标函数目标函数 max(min) Z = CX约束条件 AX (,) b其中，C=(c1, c2, , cn) , X=(x1 ,x2, xn)T b=(b1 ,b2, bm)T a11, a12, a1nA= a21, a22, a2n am1, am2, amn1.2线性规
8、划问题求解的几种可能结局线性规划问题求解的几种可能结局 u线性规划模型解的概念1.解：给每个决策变量任意赋一个值就得到该模型的解，因此模型有无数个解。例如X=20，Y=40，是该模型的解，而X=30， Y=90也是该模型的解，等等还有很多。u线性规划模型解的概念2.可行解：是指满足所有约束条件的解，也就是决策变量的值满足一组等式或不等式的值，需要求解。3.可行域：是指所有可行解的集合。4.最优解：可行域中使目标函数达到最优的解。最优解满足约束条件同时又使得目标函数值达到优。1.2线性规划问题求解的几种可能结局线性规划问题求解的几种可能结局 u线性规划问题的解可能出现下列情况：1 .有惟一解这里
9、，线性规划问题有惟一解是指该规划问题有且仅有一个既在可行域内，又使目标值达到最优的解，即只有一个最优解。1.2线性规划问题求解的几种可能结局线性规划问题求解的几种可能结局 u线性规划问题的解可能出现下列情况：2 .有无穷多解这里，线性规划问题有无穷多解是指该规划问题无穷多个既在可行域内，又使目标值达到最优的解，即有无穷多个最优解。1.2线性规划问题求解的几种可能结局线性规划问题求解的几种可能结局 u线性规划问题的解可能出现下列情况：3 . 无解这里，线性规划问题无解是指该规划问题的约束条件不能同时满足，没有可行域，不存在可行解，也就不存在最优解。1.2线性规划问题求解的几种可能结局线性规划问题
10、求解的几种可能结局 u线性规划问题的解可能出现下列情况：4. 可行域无界这里，线性规划问题的可行域无界是指最大化问题的目标函数值可以无限增大，或最小化问题的目标函数值可以无限减小。1.2线性规划问题求解的几种可能结局线性规划问题求解的几种可能结局 1.3应用应用Excel求解线性规划问题求解线性规划问题n n图解法n n单纯形法n nExcel的“规划求解”1.3应用应用Excel求解线性规划问题求解线性规划问题首先，根据问题建立电子表格模型具体步骤如下：首先，根据问题建立电子表格模型具体步骤如下：1.1.收集问题的数据。收集问题的数据。2.2.在电子表格的数据单元格中输入数据。在电子表格的数
11、据单元格中输入数据。3.3.确定对活动水平需要作出的决策并且指定可变单元显示这些确定对活动水平需要作出的决策并且指定可变单元显示这些决策。决策。4.4.确定对这些决策的约束条件并引入需具体化这些约束条件的确定对这些决策的约束条件并引入需具体化这些约束条件的输出单元格。输出单元格。5.5.选择要输入目标单元格的完全绩效测度。选择要输入目标单元格的完全绩效测度。6.6.使用使用SUMPRODUCTSUMPRODUCT函数为每个输出单元格（包括目标单元格）函数为每个输出单元格（包括目标单元格）输入合适的值。输入合适的值。1.3应用应用Excel求解线性规划问题求解线性规划问题电子表格模型：1.3应用
12、应用Excel求解线性规划问题求解线性规划问题然后，建立了起电子表格模型，就可以利用然后，建立了起电子表格模型，就可以利用ExcelExcel中的工具中的工具SolverSolver（规划求解）求解。规划求解）求解。 1.3应用应用Excel求解线性规划问题求解线性规划问题规划求解的选项对话框：1.3应用应用Excel求解线性规划问题求解线性规划问题最后，保存求解结果第二节第二节 线性规划的灵敏度分析线性规划的灵敏度分析线性规划模型的一般形式为：目标函数 max(min) z = c1 x1+c2x2+cn xn满足约束条件: a11x1+a12x2+a1nxn (,) b1 a21x1+a2
13、2x2+a2nxn (,) b2 . . am1x1+am2x2+amnxn (,) bm x1,x2,xn 0通常，假定系数aij，bi，cj都是常数，而实际上这些系数往往是估计值和预测值。如果市场条件一变， cj值就会变化；工艺条件发生变化会改变aij的值。同样，由于bi是根据资源投入后的经济效果决定的一种决策选择。灵敏度分析就是对系统或事物因周围条件变化显示出来的敏感性程度的分析。第二节第二节 线性规划的灵敏度分析线性规划的灵敏度分析生产优化问题，它的线性规划模型为：o.b. max 300X+500Y (利润最大化)s.t. X4 (工厂1的工时约束) 2Y 12 (工厂2的工时约束)
14、 3X+2Y 18 (工厂3的工时约束) X， Y 0 (非负约束)提出这样两个问题：当这些系数有一个或几个发生变化时，已求得的线性规划问题的最优解、目标值会有什么变化；或者这些系数在什么范围内变化时，线性规划线性规划问题的最优解、目标值不变。2.1一个目标函数系数变动一个目标函数系数变动 本节讨论在假定只有一个系数cj改变，其他系数均保持不变的情况下，目标函数系数变动对最优解的影响。2.1一个目标函数系数变动一个目标函数系数变动第一种方法第一种方法n n可以借助电子表格互动地展开灵敏度分析。当模型参可以借助电子表格互动地展开灵敏度分析。当模型参数发生改变时，只要改变电子表格模型中相应的参数，
15、数发生改变时，只要改变电子表格模型中相应的参数，再重新运行再重新运行Excel“Excel“规划求解规划求解” ”功能，就可以看出改变功能，就可以看出改变参数对最优解的影响。参数对最优解的影响。n n固然能达到灵敏度分析的目的，但需要一个一个地尝固然能达到灵敏度分析的目的，但需要一个一个地尝试，效率低下试，效率低下 。2.1一个目标函数系数变动一个目标函数系数变动第二种方法第二种方法可以利用可以利用ExcelExcel中的中的“ “规划求解规划求解” ”功能可以直接到功能可以直接到“ “敏敏感性分析感性分析” ”，利用该报告可以很方便地进行灵敏度分，利用该报告可以很方便地进行灵敏度分析。析。在
16、在ExcelExcel中中“ “敏感性分析敏感性分析” ”报告的获得报告的获得敏感性报告的内容：由两部分组成，位于报告上部的敏感性报告的内容：由两部分组成，位于报告上部的“ “可变单元格可变单元格” ”部分反映了目标函数中的系数变化对部分反映了目标函数中的系数变化对最优解产生的影响；位于报告下部的最优解产生的影响；位于报告下部的“ “约束约束” ”部分反部分反映了约束条件右端值变化目标值产生的影响。映了约束条件右端值变化目标值产生的影响。敏感性报告敏感性报告上部的表格反映目标函数中系数的变化对最优解的影响。表格中的前三列是该问题中决策变量的信息: “单元格”是指决策变量所在单元格地址，“名字”
17、是这些决策变量的名称，“终值”是决策变量的终值，即最优解。敏感性报告的第一部分内容第四列是“递减成本”，它的绝对值表示目标函数中决策变量的系数必须改进多少，才能得到该决策变量的正数解。“改进”，在最大化问题中是指增加，在最小化问题中是指减少。第五列“目标式系数”是指目标函数中的系数。第六列与第七列分别是“允许的增量”和“允许的减量”它们表示目标函数中的系数在允许的增量和减量范围内变化时，最优解不变。2.2 目标函数系数同时变动的影响目标函数系数同时变动的影响n n在目标函数中只有一个系数变动的情况下，在目标函数中只有一个系数变动的情况下，通过灵敏度分析报告中的数据找到该变动系通过灵敏度分析报告
18、中的数据找到该变动系数的允许变化范围。数的允许变化范围。n n在分析多个系数同时变动的情况时，也使用在分析多个系数同时变动的情况时，也使用同样的这些数据，即每个系数的允许增加值同样的这些数据，即每个系数的允许增加值和减少值和减少值 。n n目标函数系数同时变动的使用百分之百法则目标函数系数同时变动的使用百分之百法则进行判断进行判断2.2 目标函数系数同时变动的影响目标函数系数同时变动的影响n n目标函数系数同时变动的百分之百法则的具体含义为：目标函数系数同时变动的百分之百法则的具体含义为：如果目标函数的系数同时变动，计算出每一系数变动如果目标函数的系数同时变动，计算出每一系数变动量占该系数允许
19、变化范围允许变动量（允许的增量或量占该系数允许变化范围允许变动量（允许的增量或允许的减量）的百分比，而后，将各个系数的变动百允许的减量）的百分比，而后，将各个系数的变动百分比相加，如果所得的和不超过分比相加，如果所得的和不超过100%100%，最优解不会，最优解不会改变；如果超过改变；如果超过100%100%，则不能确定最优解是否改变，则不能确定最优解是否改变，只能通过重新进行规划求解来判断了。只能通过重新进行规划求解来判断了。2.2 目标函数系数同时变动的影响目标函数系数同时变动的影响茶几的单位利润茶几的单位利润P1P1从原来的从原来的300300美元增加到美元增加到450450美元，而餐桌
20、的美元，而餐桌的单位利润单位利润P2P2从原来的从原来的500500美元下降到美元下降到400400美元，运用百分百法则，美元，运用百分百法则，计算如下：计算如下：P1P1：300300美元美元450450美元美元占允许增加量的百分比占允许增加量的百分比=100*=100*（450-300450-300）/450*100%=33.34%/450*100%=33.34%P2P2：500500美元美元400400美元美元占允许增加量的百分比占允许增加量的百分比=100*=100*（500-400500-400）/300*100%=33.34%/300*100%=33.34%总和总和=66.68%=
21、66.68% 因为变动百分比之和不超过因为变动百分比之和不超过100%100%，所以可以确定最初的（茶，所以可以确定最初的（茶几，餐桌）几，餐桌）= =（2 2，6 6）的最优解没有改变。）的最优解没有改变。2.2 目标函数系数同时变动的影响目标函数系数同时变动的影响P1P1：300300美元美元600600美元美元占允许增加量的百分比占允许增加量的百分比=100*=100*（600-600-300300）/450*100%=66.67%/450*100%=66.67%P2P2：500500美元美元400400美元美元占允许增加量的百分比占允许增加量的百分比=100*=100*（500-500
22、-400400）/300*100%=66.67%/300*100%=66.67% 总和总和=133.33%=133.33%通过规划求解得到，最优解已经变成了（通过规划求解得到，最优解已经变成了（4 4，3 3），）， 2.2 目标函数系数同时变动的影响目标函数系数同时变动的影响P1P1：300300美元美元525525美元美元占允许增加量的百分比占允许增加量的百分比=100*=100*（525-525-300300）/450*100%=50%/450*100%=50%P2P2：500500美元美元350350美元美元占允许增加量的百分比占允许增加量的百分比=100*=100*（500-500-
23、350350）/300*100%=50%/300*100%=50% 总和总和=100% =100% 变动百分比之和刚好等于变动百分比之和刚好等于100%100%，但因没有超过，但因没有超过100%100%，所以（茶几，餐桌），所以（茶几，餐桌）= =（2 2，6 6）还是最优）还是最优解。解。2.3单个约束条件变化的影响单个约束条件变化的影响在例在例1.11.1中，每个工厂的可用工时是约束条件的中，每个工厂的可用工时是约束条件的右端值。右端值。工厂工厂1 1的可用工时是的可用工时是4 4，但在规划求解得出的最优，但在规划求解得出的最优方案中，方案中， 1 1只用了只用了2 2小时，因此如果小范
24、围地改小时，因此如果小范围地改变车间变车间1 1的工时，不会改变最优目标值和最优解。的工时，不会改变最优目标值和最优解。但对于工厂但对于工厂2 2和工厂和工厂3 3来说，情况有所不同了，需来说，情况有所不同了，需要通过灵敏度分析，来分析一下改变这两个工厂要通过灵敏度分析，来分析一下改变这两个工厂的可用工时对目标值及最优解的影响。的可用工时对目标值及最优解的影响。2.3单个约束条件变化的影响单个约束条件变化的影响如果管理者让工厂如果管理者让工厂2 2的可用工时从的可用工时从1212小时增加小时增加到到1313小时，修改电子表格模型中相应的参数小时，修改电子表格模型中相应的参数后，重新进行规划求解
25、，此时总利润变为后，重新进行规划求解，此时总利润变为37503750元，增加了元，增加了150150元。由于总利润增加了，元。由于总利润增加了，而目标函数系数不变，所以最优解一定会发而目标函数系数不变，所以最优解一定会发生改变。生改变。 2.3单个约束条件变化的影响单个约束条件变化的影响在电子表格模型中把工厂在电子表格模型中把工厂2 2的可得时间继续上调，总的可得时间继续上调，总利润会继续增长，直到工厂利润会继续增长，直到工厂2 2可得时间增加到可得时间增加到1818小时，小时，此时再增加时间不会带来利润的增长，这是因为工厂此时再增加时间不会带来利润的增长，这是因为工厂3 3的的1818小时可
26、得时间只能每周生产小时可得时间只能每周生产9 9个餐桌，所以工个餐桌，所以工厂厂2 2相应的最多只会使用相应的最多只会使用1818小时的工时。因此，当其小时的工时。因此，当其他工厂的可得时间不发生改变时，他工厂的可得时间不发生改变时，1818小时是工厂小时是工厂2 2可可得时间的最大值。得时间的最大值。 2.3单个约束条件变化的影响单个约束条件变化的影响约束右端值往往体现了管理层的决策，在建模决约束右端值往往体现了管理层的决策，在建模决策后，管理者想要知道改变这些决策是否会提高策后，管理者想要知道改变这些决策是否会提高最终受益，影子价格分析就可为管理者提供这方最终受益，影子价格分析就可为管理者
27、提供这方面的信息。面的信息。在给定线性规划模型的最优解和相应的目标函数在给定线性规划模型的最优解和相应的目标函数值的条件下，影子价格是指约束右端值增加（或值的条件下，影子价格是指约束右端值增加（或减少）一个单位，目标值增加（或减少）的数量。减少）一个单位，目标值增加（或减少）的数量。敏感性报告提供了每个约束的影子价格。敏感性报告提供了每个约束的影子价格。2.3单个约束条件变化的影响单个约束条件变化的影响敏感性报告下部的表格反映约束条件右边变化对目标值的影响。表格中的前三列是关于约束条件左边的信息: “单元格”是指约束条件左边所在单元格地址;“名字”是约束条件左边的名称;“终值”是约束条件左边的
28、终值，即最优解。第四列是“阴影价格”，即影子价格，影子价格是指约束条件右边增加（或减少）一个单位，目标值增加（或减少）的数量。第五列为“约束限制值”是指约束条件右边的值，是已知条件。第六列与第七列分别是“允许的增量”和“允许的减量”它们表示约束条件右边在允许的增量和减量范围内变化时，影子价格不变。2.4约束右端值同时变动的情形约束右端值同时变动的情形 uu车间车间2 2：1213 1213 总利润变化量总利润变化量= = 影子价格影子价格= = 150150元元uu车间车间3 3：1817 1817 总利润变化量总利润变化量=影子价格影子价格=100=100元元uu总利润是否增加总利润是否增加
29、1 50100=501 50100=50（元）？（元）？uu不能确定两个约束右端值同时变动时，原先的影不能确定两个约束右端值同时变动时，原先的影子价格是否依然有效，怎么处理呢？子价格是否依然有效，怎么处理呢？ 2.4约束右端值同时变动的情形约束右端值同时变动的情形uu多个约束右端值同时变动的情形进行分析的方法多个约束右端值同时变动的情形进行分析的方法百分之百法则百分之百法则uu百分之百法则的具体含义为：如果约束右端值同百分之百法则的具体含义为：如果约束右端值同时变动，计算每一变动占允许变动量（允许的增时变动，计算每一变动占允许变动量（允许的增量或允许的减量）的百分比，如果所有的百分比量或允许的
30、减量）的百分比，如果所有的百分比之和不超过之和不超过100%100%，那么，影子价格依然有效，那么，影子价格依然有效，否则只能通过重新进行规划求解来判断了。否则只能通过重新进行规划求解来判断了。2.4约束右端值同时变动的情形约束右端值同时变动的情形uu利用该百分之百法则再分析上述问题，计算如下：利用该百分之百法则再分析上述问题，计算如下：uu工厂工厂2 2：12131213，占允许增加量的百分比，占允许增加量的百分比= =（13-13-1212）/6*100%=16.67%/6*100%=16.67%uu工厂工厂3 3：18171817，占允许减少量的百分比，占允许减少量的百分比= =（18-
31、18-1717）/6*100%=16.67%/6*100%=16.67%uu 总和总和=33.33%=33.33%小于小于100%100%uu用影子价格来预测这些变动的影响是有效的。用影子价格来预测这些变动的影响是有效的。2.4约束右端值同时变动的情形约束右端值同时变动的情形 工厂工厂2 2：12151215，占允许增加量的百分比，占允许增加量的百分比= =（15-1215-12）/6*100%=50%/6*100%=50%工厂工厂3 3：18151815，占允许减少量的百分比，占允许减少量的百分比= =（18-1518-15）/6*100%=50%/6*100%=50% 总和总和=100%=
32、100%所以影子价格仍然有效。但这一变动幅度是最所以影子价格仍然有效。但这一变动幅度是最大的，一旦大于这一幅度，就不能保证影子价格仍然有效大的，一旦大于这一幅度，就不能保证影子价格仍然有效了。了。总利润的变化量为（总利润的变化量为（15-1215-12）* *150-150-（18-1518-15）* *100=150100=1502.5 约束条件系数变化约束条件系数变化uu约束条件中的技术（工艺）系数约束条件中的技术（工艺）系数a aij ij，往往涉及车往往涉及车间生产能力、产品消耗资源数等比较确定的数据，间生产能力、产品消耗资源数等比较确定的数据，因此，一般情况下，它比前面提到的目标函数
33、系因此，一般情况下，它比前面提到的目标函数系数和约束右端值更具有确定性。数和约束右端值更具有确定性。uu但约束条件的系数也有可能发生变化。下面就来但约束条件的系数也有可能发生变化。下面就来讨论只有一个讨论只有一个a aij ij变化而其他数据不变的情况会对变化而其他数据不变的情况会对最优解产生什么样的影响。最优解产生什么样的影响。uu解决这类问题，需要修改模型中的相应的参数并解决这类问题，需要修改模型中的相应的参数并重新进行规划求解。重新进行规划求解。2.5 约束条件系数变化约束条件系数变化n n例例1.11.1的，如果工厂的，如果工厂2 2更新生产工艺，生产一更新生产工艺，生产一个餐桌由原来的个餐桌由原来的2 2小时下降到小时下降到1.51.5小时，此时小时，此时最优解及总利润会发生怎样的变化？最优解及总利润会发生怎样的变化？
