线性规划的对偶理论与灵敏度分析课件

1、第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

2、., (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 对偶问题的“非对称”形式,目标函数 max z,n个,无约束,变量,m个,=,约束条件,约束条件右端项,目标函数变量的系数,目标函数 min w,n个,=,约束条件,变量,m个,无约束,约束条件右端项,目标函数变量的系数,2.1.2 对偶问题的

3、对称形式,例3：写出下面问题的对偶规划,无约束,2.1.2 对偶问题的对称形式,解：,无约束,2.1.2 对偶问题的一般形式,练习： 写出下面线性规划的对偶规划模型,s.t.,无约束,s.t.,无约束,2.2 对偶问题的基本性质,1. 对称性 对偶问题的对偶问题是原问题,（P）与（D）互为对偶，没有要求原问题一定要是max型，对偶问题一定要是min型,2. 弱对偶性,设X, Y分别为(P), (D)的任一可行解，则CX Yb,证：因为X, Y分别为(P), (D)的可行解，那么有：,AX b YAXYb,YA C YAX CX,CX Yb,2.2 对偶问题的基本性质,2. 弱对偶性,由上述弱对

4、偶性可推出：,若(P)为无界解，则(D)无可行解,若(D)为无界解，则(P)无可行解,CX,Yb,？课本中关于弱对偶性的推论如何理解,2.2 对偶问题的基本性质,推论1 原问题任一可行解的目标函数值是其对偶问题目标函数值的下界，反之，对偶问题任一可行解的目标函数值是其原问题目标函数值的上界。,推论2 若原问题有可行解且目标函数值无界，则其对偶问题无可行解；反之，对偶问题有无界解，原问题无可行解。（但逆向不成立）,推论3 若原问题有可行解，对偶问题无可行解，则原问题目标函数值无界；反之，对偶问题有可行解，而原问题无可行解，则对偶问题的目标函数值无界。,2.2 对偶问题的基本性质,3. 最优性,设

5、 ， 分别为(P)与(D)的可行解，且 ，则 ，,证：对任一可行解X, 由弱对偶性 ，故 ，同理,2.2 对偶问题的基本性质,4. 强对偶性（对偶定理）,若(P)有最优解，则(D)也有最优解，且二者最优值相等,证：对(P)增加松弛变量Xs, 化为：,s.t.,2.2 对偶问题的基本性质,4. 强对偶性（对偶定理）,证：（续）,设其最优基为B, 终表为：,C - CBB-1A 0,0 CBB-1I 0,取,2.2 对偶问题的基本性质,4. 强对偶性（对偶定理）,证：（续）,则 满足：,是(D)的可行解，且 ，由最有性定理，可得：,2.2 对偶问题的基本性质,4. 强对偶性（对偶定理）,(1)由性

6、质4可知，对偶问题最优解的表达式Y* = ?,(2)求Y*是否要重新求解(D), CBB-1, 不需要，可以从原问题(P)的单纯形终表获得,2.2 对偶问题的基本性质,例如，在前面美佳公司的生产计划中，其单纯形终表为：,2.2 对偶问题的基本性质,由上表可直接得到问题(P)的最优解和最优值：,X* = (7/2, 3/2, 15/2, 0, 0)T Z* = 8.5,根据强对偶性可得：,Y* = (0, 1/4, 1/2) Y* = 8.5,2.2 对偶问题的基本性质,5. 互补松弛性（松紧定理）,设 ， 分别为(P)和(D)的可行解，则：, 是最优解,其中， ， 为最优解中松弛变量部分。,2

7、.2 对偶问题的基本性质,证：,将(P)、(D)的约束条件化为等式：,因为 ， 是最优解，所以 ，即：,而,故只有：,2.2 对偶问题的基本性质,原始问题变量,原始问题的松弛变量,对偶问题变量,对偶问题的松弛变量,在如上的一对变量中，其中一个大于0，另一个一定等于0,2.2 对偶问题的基本性质,在线性规划问题中,（1）如果对应于某一约束条件的对偶变量值为非0，则该约束条件取严格等式,（2）如果约束条件取严格不等式，则其对应的对偶变量一定为0,2.2 对偶问题的基本性质,例4 已知如下线性规划问题,s.t.,已知其对偶问题最优解 , ,试利用对偶理论，找出原问题的最优解。,2.2 对偶问题的基本

8、性质,解：先写出其对偶问题,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 对偶问题的最优解 买主的最

9、低出价,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 影子价格,因为，影

10、子价格只是表示某种资源在企业内部的虚拟价格，而不等于资源的市场价格,为什么叫影子价格？,2.3.1 影子价格,影子价格在管理决策中的应用,这种资源对目标增益的影响越大,这种资源对该企业越稀缺、贵重,管理措施：,通过挖掘革新、降低消耗或及时补充该种资源,重视对该资源的管理；,2.3.1 影子价格,某种资源的影子价格为0，表明：,这种资源对该企业而言，是相对富余的,管理措施：,通过对企业内部的改造、挖掘和增加对影子价格大于零的资源的投入，使原有剩余资源得到充分利用,以市场价出售,2.3.1 影子价格,影子价格 市场价格，则买进该资源,影子价格 市场价格，则卖出该资源,决策判断依据：,2.3.2 对

11、偶约束的经济解释,s.t., 机会成本，表示减少一件产品所节省的资源可以增加的利润,2.3.3 对偶松弛变量的经济解释,差额成本 = 机会成本 利润,2.3.4 互补松弛关系的经济解释,在利润最大化的生产计划中,(1) 影子价格大于0的资源没有剩余； 有剩余的资源影子价格为0,(2)安排生产机会成本等于利润的产品；机会成本大于利润的产品不安排生产,2.4 对偶单纯形法,二、对偶单纯形法基本步骤 max型,(1) 作初始表，要求全部j 0 (0),(3)确定换入变量, 若Xi l行的alj 全0 ，停，原问题无可行解。, 若Xi l行的alj 有alj 0 ,则求,Xk为换入变量,2.4 对偶单

12、纯形法,(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 对偶单纯形法,从上述对偶单纯形法的求解中，可

13、以看出其优点：,(1) 初始解可以是非可行解，当检验数均为非正数时，就可以进行基变换，此时无需加入人工变量，因此可以简化计算,(2) 当变量多余约束条件时，用对偶单纯形法计算可以减少计算工作量,(3) 在灵敏度析及整数规划的割平面法中，有时需要用对偶单纯形法以简化问题的处理,2.4 对偶单纯形法,但对偶单纯形法也有其局限性：,对于多数线性规划问题，在初始单纯形表中其对偶问题应是基可行解这一点很难实现，所以对偶单纯形法一般不单独使用,2.4 对偶单纯形法,练习1：用对偶单纯形法求解,s.t.,xj0(j = 1, , 3),2.4 对偶单纯形法,练习2：用对偶单纯形法求解,s.t.,xj0(j

14、= 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.5 2,1.5 2,1/8,-9/4,因为，检验数全非正，该解为最优解，即：,2.5.1 分

15、析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/

16、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

17、的美佳公司例子中，设该公司又计划推出新型号的家电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的分析,解：,将其反映到最终单纯形表中：,此时，美佳公司的最优生产计划为每天生

18、产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行的约束可写为：,2.5.4 分析参数aij的变化,此时，美佳公司的最优生产计划为