运筹学1线性规划课件

1、2-3 灵敏度分析例2-12 某工厂 用甲、乙两种原料生产A、B、C、D四种产品，每种产品的利润、现有的原料数及每种产品消耗原料定量如表。第1页，共72页。第2页，共72页。问题1：怎样组织生产，才能使总利润 最大？ 设生产A、B、C、D产品各X1， X2， X3， X4万件，数学模型为： max S=9x1+8x2 +50 x3+19x4 3x1+2x2 +10 x3 + 4x4 18 2x3+ (1/2)x4 3 x1，x2 ， x3 ， x4 0第3页，共72页。化成标准型 max S = 9x1+8x2 +50 x3+19x4 3x1+2x2 +10 x3 + 4x4 + x5 = 1

2、8 2x3+ (1/2)x4 + x6 = 3 x1,x2, x3 , x4 ,x5 ,x6 0第4页，共72页。初始基 B1=（P5，P6）第5页，共72页。第二行除以2第6页，共72页。第一行加上第二行的（-10）第7页，共72页。第8页，共72页。B3=（P1，P3）第一行除以3第9页，共72页。B3=（P1，P3）第10页，共72页。B4=（P2，P3）第一行乘以（3/2） 第11页，共72页。第一行乘以（4/3） 第12页，共72页。B5=（P4，P3）第二行减去第一行1/4倍第13页，共72页。最优基 B5=（P4，P3）最优解=（0，0，1，2） S = 88第14页，共72页。

3、B5=（P4，P3）在初始表中第15页，共72页。最优决策方案：生产C 1万件，D 2万件，最大利润为88万元。问题2：若A、C产品的利润产生波动，波动范围多大，最优基不变？ 4 10最优表B5=（P4，P3）= 1/2 2第16页，共72页。对应原松驶变量的位置即为B-1初始表最优表第17页，共72页。B-1= 2/3 -10/3 -1/6 4/3第18页，共72页。B-1A= 2 4/3 0 1 2/3 -10/3 -1/2 -1/3 1 0 -1/6 4/3第19页，共72页。CB=（C4，C3）=（19，50）C=（9，8，50，19，0，0）当目标函数的C1= 9 有波动，设波动为C

4、1= 9 + a, CB = CB,C=（9+ a ，8，50，19，0，0）得到检验数的变化为 ： =(-4+a,-2/3,0,0, -13/3, -10/3)第20页，共72页。 =(-4+a,-2/3,0,0,-13/3,-10/3)第21页，共72页。仅当 -4 + a0时，即a4时，即每万件A产品的利润超过13万元时，B 已经不是最优基，继续进行最优化。第22页，共72页。当a4时，-4+a0第23页，共72页。第一行除以2第24页，共72页。第二行加上第一行（1/2）。重新计算检验数，为了保证B为最优，必须满足 6-2a 0 , 4-a 0, -9-a 0, 5a -30 0 得到

5、4 a 6第25页，共72页。当4 a 6时，即每万件A产品的利润在13-15万元之间，得到新的最优基=（P1，P3）最优决策方案=（1，0，3/2，0），最优利润=84+ a，最大利润在88-90之间。第26页，共72页。当目标函数的C3= 50 有波动，设波动为C3= 50 + a, CB = CB, 原最优表如下第27页，共72页。当目标函数的C3= 50有波动，设波动为C3= 50+a, CB = CB, 重新计算检验数如下第28页，共72页。为保证最优，满足 a-8 0, a-2 0, a-26 0, -10-4a 0。得到 -5/2 a 2，即产品C的利润在47.5-52万元之间，

6、原最优决策方案不变，最优利润在85.5-90万元之间。第29页，共72页。同理可以讨论：a 2时，只要X2进基变量。 第30页，共72页。问题3：若想增加甲种原料，增加多少时，原最优基不变？ 当增加甲种原料供应量时， b1发生了变化，设b1=18+a， b=( 18+a,3) 2/3 -10/3 18+a 2+(2/3)aB-1 b= -1/6 4/3 3 = 1-(1/6)a第31页，共72页。解： 2+(2/3) a 0 , 1-(1/6)a 0得到：-3 a 6 即 15 b1 24原最优基不变，但最优解与目标函数最优值都是 a 的函数：X*=（0，0，1- a/6，2+（2/3） a）

7、S*=88+（13/3） a（万元）第32页，共72页。当 a 6 , a6 情形：原问题最优基。第33页，共72页。 2+(2/3)a用 B-1 b= 1-(1/6) a 代替常数项因为 a6， 则1-(1/6) a6新的最优基, B,=(P4,P2) 最优解=(0， -3+(1/2) a，0，6)最大利润=90+4 a (万元)第37页，共72页。问题4：若考虑要生产产品E，且生产1万件E产品要消耗甲原料3公斤，消耗乙原料1公斤。那么，E产品的每万件利润是多少时有利于投产？第38页，共72页。增加变量；设生产E产品X7万件，每万件利润是C7万元，则模型为：max S = 9x1 + 8x2

8、 + 50 x3 + 19x4 + C7 x7 3x1+2x2 +10 x3 + 4x4 + x5 +3x7 = 18 2x3+ (1/2)x4 + x6 +x7 = 3 x1,x2, x3 , x4 ,x5 ,x6 , x7 0第39页，共72页。A=（P1，P2，P3，P4，P5，P6，P7）P7=（3，1）t原最优解=（0，0，1，2，0，0）则 X =（0，0，1，2，0，0，0）一定是原问题的可行解，但不一定是原问题的最优解。第40页，共72页。若要生产E，在原最优表中增加非基变量X7，其中P7,=B-1 P7= 2/3 -10/3 3 = -4/3 -1/10 4/3 1 5/6相

9、应的检验数= -49/3 + C7 0 时，才有利生产。令C7 =17，相应的检验数= 2/3第41页，共72页。插入原最优表，继续求解。第42页，共72页。第二行乘以6/5第43页，共72页。第一行加上第二行乘以4/3第44页，共72页。得到新的最优解= (0,0,0,18/5,0,0,6/5) 最优值=88(4/5)。最优方案生产D产品18/5(万件),E产品6/5 (万件) ,利润达到88.8(万元)。第45页，共72页。问题5：假设该工厂又增加了用电不超过8千瓦的限制，而生产A、B、C、D四种产品各1万件分别消耗电4、3、5、2千瓦。此约束是否改变了原最优决策方案？第46页，共72页。

10、只需在模型中增加新的约束条件：4x1+3x2 +5x3 + 2x4 8标准化后有4x1+3x2 +5x3 + 2x4 + x7 =8加入模型中：第47页，共72页。第48页，共72页。X4,X3,X7是基变量,使增加一行元素(5)(2)为零第49页，共72页。第三行加上第一行的（-2）倍第50页，共72页。第三行加上第二行的（-5）倍第51页，共72页。第三行对偶不可行第52页，共72页。第三行乘以（-2）第53页，共72页。第一行加上第三行乘以（-2/3）。第54页，共72页。第二行加上第三行乘以（1/6）计算检验数得最优表第55页，共72页。增加用电约束后，最优生产方案：生产4/3万件C产

11、品，2/3万件D产品，总利润为79.5万元第56页，共72页。2-4 对偶解的经济解释 如果把线性规划的约束看成广义资源约束，右边项则代表某种资源的可用量。对偶解的经济含义是资源的单位改变量引起目标函数值的改变量。通常称为影子价格。影子价格表明对偶解是对系统内部资源的客观估计，又表明它是一种虚拟的价格而不是真实价格。第57页，共72页。影子价格的特征：影子价格是对系统资源的最优估计，只有系统达到最优状态时才可能赋与资源这种价值。因此，也称为最优价格。第58页，共72页。影子价格的特征：影子价格是对系统资源的最优估计，只有系统达到最优状态时才可能赋与资源这种价值。因此，也称为最优价格。影子价格的

12、取值与系统的价值取向有关，并受系统状态变化的影响。系统内部资源数量和价格的变化，它是一种动态的价格体系。第59页，共72页。影子价格的特征：对偶解影子价格的大小客观反映了资源在系统内的稀缺程度。如果某资源在系统内供大于求，尽管它有市场价格，但它的影子价格等于零。增加这种资源的供应不会引起系统目标的任何变化。如果某资源是稀缺资源，其影子价格必然大于零。影子价格越高，这种资源在系统中越稀缺。第60页，共72页。影子价格的特征：影子价格是一种边际价值，它与经济学中边际成本的概念相同。因而在经济管理中有十分重要的价值。企业管理者可以根据资源在企业内部影子价格的 大小决定企业的经营策略。第61页，共72

13、页。例2-13：某企业生产A，B二种产品。A产品需要消耗2个单位原料和1个小时人工；B产品需要消耗3个单位原料和2个小时人工；A产品销售价格23元，B产品销售价格40元。该企业每天可利用生产原料25单位和15个人工。每单位原料的采购成本为5元，每小时人工工资为10元。问该企业如何组织生产才能使销售利润最大？第62页，共72页。解：（模型一）目标函数系数直接使用计算好的销售利润，成本数据不直接反映在模型中。 max g=3x1+5x2 s.t. 2x1+3x2 25 x1+2x2 15 x1,x2 0最优解X=（5，5）最优值Z=40对偶解Y=（1，1）第63页，共72页。解：（模型二）目标函数

14、系数使用未经过处理的数据，成本数据直接反映在模型中。 max g=23x1+40 x2-5 x3-10 x4 s.t. 2x1+3x2 -x3 =0 x1+2x2 -x4 =0 x3 25 x4 15 x1,x2 , x3 , x4 0第64页，共72页。（模型二）最优解 X=（5，5，0，0）最优值 Z=40对偶解 Y=（6，11，1，1）第65页，共72页。一般来讲，如果模型显性地处理所有资源的成本计算（模型二）则对偶解与影子价格相等，我们按以下原则考虑企业的经营策略：如果某资源的影子价格高于市场价格，表明该资源在系统内有获利能力，应买入该资源。第66页，共72页。一般来讲，如果模型显性地

15、处理所有资源的成本计算（模型二）则对偶解与影子价格相等，我们按以下原则考虑企业的经营策略：如果某资源的影子价格高于市场价格，表明该资源在系统内有获利能力，应买入该资源。如果某资源的影子价格低于市场价格，表明该资源在系统内无获利能力，应卖出该资源。第67页，共72页。一般来讲，如果模型显性地处理所有资源的成本计算（模型二）则对偶解与影子价格相等，我们按以下原则考虑企业的经营策略：如果某资源的影子价格高于市场价格，表明该资源在系统内有获利能力，应买入该资源。如果某资源的影子价格低于市场价格，表明该资源在系统内无获利能力，应卖出该资源。如果某资源的影子价格等于市场价格，表明该资源在系统内处于平衡状态，既不用买入，也不必卖出该资源。第68页，共72页。一般来讲，如果模型隐性地处理所有资源的成本计算（模型一）则影子价格应等于对偶解与资源的成本之和，我们按以下原则考虑企业的经营策略：如果某资源的对偶解大于零，表明该资源在系统内有获利能力，应买入该资源。第69页，共72页。一般来讲，如果模型隐性地处理所有资源的成本计算（模型一）则影子价格应等于对偶解与资源的成本之和，我们按以下原则考虑企业的经营策略：如果某资源的对偶解大于零，表明该资源在系统内有获利能力，应买入该资源