第2章-线性规划的对偶理论与灵敏度分析ppt课件

.,第2章线性规划的对偶理论与灵敏度分析,2.1线性规划的对偶问题,2.2对偶问题的基本性质,2.3影子价格,2.4对偶单纯形法,2.5灵敏度分析,.,2.1.1对偶问题的提出,例1第一章例1中美佳公司利用公司资源生产两种家电产品时，其线性规划问题为：,s.t.,(P),.,2.1.1对偶问题的提出,这时，如果有另一家公司想购买美佳公司的资源全部资源，那么它至少应出多少的价格，才会使美佳公司愿意出让？,解：设其购买三种资源的价格分别为y1,y2,y3,总花费为w，则：,s.t.,y1,y2,y30,(D),.,2.1.1对偶问题的提出,s.t.,y1,y2,y30,s.t.,(P),(D),.,2.1.1对偶问题的提出,s.t.,.,2.1.1对偶问题的提出,s.t.,.,2.1.2对偶问题的对称形式,(P),(D),对称式对偶模型：,（1）其变量均具有非负约束,（2）约束条件当目标函数求极大时均取“”,（3）约束条件当目标函数求极大时均取“”,.,2.1.2对偶问题的对称形式,例2：写出下面问题的对偶规划,.,2.1.2对偶问题的“非对称”形式,目标函数maxz,n个,无约束,变量,m个,=,约束条件,约束条件右端项,目标函数变量的系数,目标函数minw,n个,=,约束条件,变量,m个,无约束,约束条件右端项,目标函数变量的系数,.,2.1.2对偶问题的对称形式,例3：写出下面问题的对偶规划,无约束,.,2.1.2对偶问题的对称形式,解：,无约束,.,2.1.2对偶问题的一般形式,练习：写出下面线性规划的对偶规划模型,s.t.,无约束,s.t.,无约束,.,2.2对偶问题的基本性质,1.对称性对偶问题的对偶问题是原问题,（P）与（D）互为对偶，没有要求原问题一定要是max型，对偶问题一定要是min型,2.弱对偶性,设X,Y分别为(P),(D)的任一可行解，则CXYb,证：因为X,Y分别为(P),(D)的可行解，那么有：,AXbYAXYb,YACYAXCX,CXYb,.,2.2对偶问题的基本性质,2.弱对偶性,由上述弱对偶性可推出：,若(P)为无界解，则(D)无可行解,若(D)为无界解，则(P)无可行解,CX,Yb,？课本中关于弱对偶性的推论如何理解,.,2.2对偶问题的基本性质,推论1原问题任一可行解的目标函数值是其对偶问题目标函数值的下界，反之，对偶问题任一可行解的目标函数值是其原问题目标函数值的上界。,推论2若原问题有可行解且目标函数值无界，则其对偶问题无可行解；反之，对偶问题有无界解，原问题无可行解。（但逆向不成立）,推论3若原问题有可行解，对偶问题无可行解，则原问题目标函数值无界；反之，对偶问题有可行解，而原问题无可行解，则对偶问题的目标函数值无界。,.,2.2对偶问题的基本性质,3.最优性,设，分别为(P)与(D)的可行解，且，则，,证：对任一可行解X,由弱对偶性，故，同理,.,2.2对偶问题的基本性质,4.强对偶性（对偶定理）,若(P)有最优解，则(D)也有最优解，且二者最优值相等,证：对(P)增加松弛变量Xs,化为：,s.t.,.,2.2对偶问题的基本性质,4.强对偶性（对偶定理）,证：（续）,设其最优基为B,终表为：,C-CBB-1A0,0CBB-1I0,取,.,2.2对偶问题的基本性质,4.强对偶性（对偶定理）,证：（续）,则满足：,是(D)的可行解，且，由最有性定理，可得：,.,2.2对偶问题的基本性质,4.强对偶性（对偶定理）,(1)由性质4可知，对偶问题最优解的表达式Y*=?,(2)求Y*是否要重新求解(D),CBB-1,不需要，可以从原问题(P)的单纯形终表获得,.,2.2对偶问题的基本性质,例如，在前面美佳公司的生产计划中，其单纯形终表为：,.,2.2对偶问题的基本性质,由上表可直接得到问题(P)的最优解和最优值：,X*=(7/2,3/2,15/2,0,0)TZ*=8.5,根据强对偶性可得：,Y*=(0,1/4,1/2)Y*=8.5,.,2.2对偶问题的基本性质,5.互补松弛性（松紧定理）,设，分别为(P)和(D)的可行解，则：,是最优解,其中，为最优解中松弛变量部分。,.,2.2对偶问题的基本性质,证：,将(P)、(D)的约束条件化为等式：,因为，是最优解，所以，即：,而,故只有：,.,2.2对偶问题的基本性质,原始问题变量,原始问题的松弛变量,对偶问题变量,对偶问题的松弛变量,在如上的一对变量中，其中一个大于0，另一个一定等于0,.,2.2对偶问题的基本性质,在线性规划问题中,（1）如果对应于某一约束条件的对偶变量值为非0，则该约束条件取严格等式,（2）如果约束条件取严格不等式，则其对应的对偶变量一定为0,.,2.2对偶问题的基本性质,例4已知如下线性规划问题,s.t.,已知其对偶问题最优解,试利用对偶理论，找出原问题的最优解。,.,2.2对偶问题的基本性质,解：先写出其对偶问题,s.t.,(1),(2),(3),(4),(6),将，的值代入左边5个约束条件中，得约束（2），（3），（4）为严格等式，由互补松弛性定理得：,又,，所以对应于原问题的约束条件取等式,.,2.2对偶问题的基本性质,所以：,.,2.3对偶问题的经济解释,2.3.3对偶松弛变量的经济解释产品的差额成本,2.3.1对偶问题最优解的经济解释资源的影子价格,2.3.2对偶约束的经济解释产品的机会成本,2.3.4互补松弛关系的经济解释,.,2.3.1影子价格,根据前述对偶定理可知，对偶问题最优解的表达式Y*=CBB-1,CBB-1对偶问题的最优解买主的最低出价,CBB-1原问题资源的影子价格当该资源增加1单位时引起的总收入的增量卖主的内控价格,设D的最优解为Z*（注：与P最优值相同）,则：,.,2.3.1影子价格,例5请根据美佳公司生产计划安排的单纯形终表指出：,资源设备A、B和调试工序的影子价格，并解释其经济意义,.,2.3.1影子价格,例5美佳公司生产计划安排的单纯形终表如下：,.,2.3.1影子价格,解：,即再增加设备A台时，利润不会增加,即再增加1个设备B台时，利润增加1/4元,即再增加1个调试台时，利润增加1/2元,.,2.3.1影子价格,x30,y1=0,x4=0,y20,x5=0,y30,.,2.3.1影子价格,因为，影子价格只是表示某种资源在企业内部的虚拟价格，而不等于资源的市场价格,为什么叫影子价格？,.,2.3.1影子价格,影子价格在管理决策中的应用,这种资源对目标增益的影响越大,这种资源对该企业越稀缺、贵重,管理措施：,通过挖掘革新、降低消耗或及时补充该种资源,重视对该资源的管理；,.,2.3.1影子价格,某种资源的影子价格为0，表明：,这种资源对该企业而言，是相对富余的,管理措施：,通过对企业内部的改造、挖掘和增加对影子价格大于零的资源的投入，使原有剩余资源得到充分利用,以市场价出售,.,2.3.1影子价格,影子价格市场价格，则买进该资源,影子价格市场价格，则卖出该资源,决策判断依据：,.,2.3.2对偶约束的经济解释,s.t.,机会成本，表示减少一件产品所节省的资源可以增加的利润,.,2.3.3对偶松弛变量的经济解释,差额成本=机会成本利润,.,2.3.4互补松弛关系的经济解释,在利润最大化的生产计划中,(1)影子价格大于0的资源没有剩余；有剩余的资源影子价格为0,(2)安排生产机会成本等于利润的产品；机会成本大于利润的产品不安排生产,.,2.4对偶单纯形法,二、对偶单纯形法基本步骤max型,(1)作初始表，要求全部j0(0),.,(3)确定换入变量,若Xil行的alj全0，停，原问题无可行解。,若Xil行的alj有alj0,则求,Xk为换入变量,2.4对偶单纯形法,(4)以alk为主元，换基迭代,.,2.4对偶单纯形法,例6用对偶单纯形法求下述线性规划问题,s.t.,y1,y2,y30,.,2.4对偶单纯形法,解：先将问题改写为：,s.t.,yi0(i=1,5),.,2.4对偶单纯形法,在上述两个约束条件两端乘“-1”,s.t.,yi0(i=1,5),.,2.4对偶单纯形法,列出单纯形表，用对偶单纯形法进行计算：,*,.,2.4对偶单纯形法,列出单纯形表，用对偶单纯形法进行计算：,*,.,2.4对偶单纯形法,Y*=(0,1/4,1/2,0,0),w=8.5(元),.,2.4对偶单纯形法,从上述对偶单纯形法的求解中，可以看出其优点：,(1)初始解可以是非可行解，当检验数均为非正数时，就可以进行基变换，此时无需加入人工变量，因此可以简化计算,(2)当变量多余约束条件时，用对偶单纯形法计算可以减少计算工作量,(3)在灵敏度析及整数规划的割平面法中，有时需要用对偶单纯形法以简化问题的处理,.,2.4对偶单纯形法,但对偶单纯形法也有其局限性：,对于多数线性规划问题，在初始单纯形表中其对偶问题应是基可行解这一点很难实现，所以对偶单纯形法一般不单独使用,.,2.4对偶单纯形法,练习1：用对偶单纯形法求解,s.t.,xj0(j=1,3),.,2.4对偶单纯形法,练习2：用对偶单纯形法求解,s.t.,xj0(j=1,4),.,2.5灵敏度分析,灵敏度,指系统或事物因周围条件变化显示出来的敏感程度,.,2.5灵敏度分析,灵敏度分析步骤,1.将参数的改变通过计算反映到最终单纯形表上来,2.检查员问题是否仍为可行解,3.检查对偶问题是否仍为可行解,.,2.5.1分析cj的变化,例7,在第1章例1的美佳公司例子中：（1）若家电1的利润将至1.5元/件，美佳公司最优生产计划有何变化（2）若家电1的利润不变，则家电2的利润在什么范围内变化时，该公司的最优生产计划将不发生改变？,.,2.5.1分析cj的变化,1.52,1.52,1/8,-9/4,.,因为，检验数全非正，该解为最优解，即：,2.5.1分析cj的变化,.,2.5.1分析cj的变化,1,1,-1/4,-1/2,为保持最优解不变，应有：,.,2.5.2分析bi的变化,例8,在第1章例1的美佳公司例子中：（1）若设备A和调试工序的每天能力不变，而设备B每天的能力增加到32h，分析公司最优计划的变化；（2）若设备A和设备B每天可用能力不变，则调试工序能力在什么范围内变化时，问题的最优基不变？,.,2.5.2分析bi的变化,1,1,-1/4,-1/2,.,2.5.2分析bi的变化,解：,（1）由已知得，则：,.,2.5.2分析bi的变化,解：,.,2.5.2分析bi的变化,1,1,-1/4,-1/2,15/2,7/2,3/2,35/2,11/2,-1/2,.,2.5.2分析bi的变化,1,1,15,5,2,因为，检验数全非正，该解为最优解，即：此时，美佳公司只生产5件家电1,.,2.5.2分析bi的变化,解：,（2）设调试工序每天可用能力为h,.,2.5.2分析bi的变化,解：,当时，问题的最优基不变，可解得,由此，调试工序的能力在4h6h之间,.,2.5.3增加一个变量xj的分析,增加一个变量在实际问题中反映为增加一个新的品种，其分析步骤如下：,1.计算,2.计算,3.若，原最优解不变，只需将计算得到的,直接写入最终单纯形表中；若，则按单纯形法继续迭代计算找出最优解。,.,2.5.3增加一个变量xj的分析,例9,在第1章例1的美佳公司例子中，设该公司又计划推出新型号的家电3，生产一件所需设备A、B及调试工序的时间分别为3h,4h,2h,该产品的预期盈利为3元/件，试分析该种产品是否值得投产；如投产，对该公司的最优生产计划有何影响？,.,2.5.3增加一个变量xj的分析,解：,设该公司生产家电3的数量为x6,由已知可得：,c6=3,P6=(3,4,2)T,由原最终单纯形表可得，Y*=(0,1/4,1/2),.,2.5.3增加一个变量xj的分析,解：,将其反映到最终单纯形表中：,*,.,2.5.3增加一个变量xj的分析,解：,将其反映到最终单纯形表中：,此时，美佳公司的最优生产计划为每天生产7/2件家电1,3/4件家电2。,.,2.5.4分析参数aij的变化,若变量xj在最终单纯形表中为非基变量，其约束条件中系数aij的变化分析可参照增加一个变量xj的分析,若变量xj在最终单纯形表中为基变量，则aij的变化将使相应的B和B-1发生变化，从而有可能出现原问题和对偶问题均为非可行解的情况，此时，需引入人工变量先将原问题的解转化为可行解，再用单纯形法求解。,.,2.5.4分析参数aij的变化,例10,在第1章例1的美佳公司例子中，若家电2每件需设备A,B和调试工序工时变为8h,4h,1h,该产品的利润变为3元/件，试重新确定该公司最优生产计划。,解：,先将生产工时变化后的新家电2看作是一种新产品，生产量为，计算、，并反映到最终单纯形表中：,.,2.5.4分析参数aij的变化,*,因已变换为，故用单纯形法将替换出原基变量中的，并在下一表中不再保留,.,2.5.4分析参数aij的变化,该表中原问题与对偶问题均为非可行解，故先设法使原问题变为可行解，该表中第1行的约束可写为：,