第二章--线性规划的对偶理论与灵敏度分析--运筹学.ppt

1、清华大学出版社,运筹学教程（第二版）,运筹学基础,胡运权 主编,教材,例一,美佳公司计划制造、两种家电产品。已知各制造一件时分别占用的设备A、B的台时、调试时间及A、B设备和调试工序每天可用于这两种家电的能力、各售出一件时的获利情况如下表所示。问该公司应制造、两种家电备多少件使获取的利润为最大。,一、标准化,二、写出初始单纯形表（必定存在有单位矩阵）,2 1 0 0 0,三、最优解检验（唯一解、无限多解、无界解和无解）,X*=(7/2,3/2,15/2,0,0),Z*= 17/2,把解X=(7/2,3/2)代入原问题(因为x3、 x4、 x5为附加变量),四、分析,53215/2,A有空闲 B

2、设备已经饱和 调试工序也已经满负荷,6y2 + y3,分 析,设： y1 设备A值的价值 y2 设备B值的价值 y3 调试工序值的价值,2,5y1 + 2y2 + y3,1,z= 15 y1 + 24y2 + 5y3,总价值,min,例一,6y2 + y3,2,5y1 + 2y2 + y3,1,z= 15 y1 + 24y2 + 5y3,min,z= -15 y1 - 24y2 - 5y3,max,6y2 + y3 y4,=,2,5y1 + 2y2 + y3 y5,1,=,y1, y2, y3, y4, y5,0,问题求解,6y2 + y3,2,5y1 + 2y2 + y3,1,z= 15 y

3、1 + 24y2 + 5y3,min,z= -15 y1 - 24y2 - 5y3,max,6y2 + y3 y4,=,2,5y1 + 2y2 + y3 y5,1,=,y1, y2, y3, y4, y5,0,Y=(0, , , 0, 0),z=-17/2,z = 17/2,问题求解,Y=(0, , , 0, 0 ),问题分析,问题 的解,问题：,？,原问题：,问题 的解,X*=(7/2,3/2,15/2,0,0),Z*= 17/2,Z*= 17/2,5*3/2 = 15/2,15,结 论,两个问题的最优解的值一致 最大值问题可行解的目标值必定不大于最小值问题可行解的目标值 一个问题的剩余变量

4、（松弛变量） 不为0（即有资源剩余），则对应问题的解为0 一个决策变量不为0，则对应的问题的约束条件的剩余变量(松弛变量) 为0(即资源彻底用完),估价影子价格 （即增加单位资源所得到的贡献）,Z= =CX=Yb Z/ b=(Yb) =Y,Y=(0, , , 0, 0 ),X*=(7/2,3/2, 15/2,0,0),解的关系,一、线性规划的对偶问题,1、对偶问题定义,对称形式,X 0,st.,AX b,max z =,CX,其中： C=（c1，c2, ,cn) b=（b1，b2, ,bm)T X=（x1，x2, ,xn)T Y=（y1，y2, ,ym)T,A=,a11 a12 a1n a11

5、 a12 a1n am1 am2 anm,Y 0,st.,ATY C,min w =,YTb,一、线性规划的对偶问题,非对称形式？,x1 0, x2 0, x3无约束,st.,a11x1+a12x2+a13x3 b1 a21x1+a22x2+a23x3 = b2 a31x1+a32x2+a33x3 b3,max z = c1x1 + c2x2 +c3x3,x1 , x2, x3，x3 0,st.,a11x1 - a12x2 + a13x3- a13x3 b1 a21x1 - a22x2 + a23x3- a23x3 b2 -a21x1 + a22x2 _ a23x3+ a23x3 -b2 -a

6、31x1 + a32x2 - a33x3+ a33x3 -b3,max z = c1x1 - c2x2 + c3x3 - c3x3,y1 , y2, y2 ，y30,st.,a11y1 + a21y2 a21y2 - a31y3 c1 -a12y1 - a22y2+ a22y2 - a32y3-c2 a13y1 + a23y2 a23y2- a33y3 c3 -a13y1 - a23y2+ a23y2+ a33y3-c3,min w = b1y1 + b2y2- b2y2 - b3y3,min w = b1y1 + b2y2 + b3y3,a11y1 + a21y2 + a31y3 c1 a1

7、2y1 + a22y2 + a32y3 c2 a13y1 + a23y2 + a33y3 = c3,st.,y10, y2无约束，y3 0,对偶规则 变量、约束与系数,原问题有m个约束条件，对偶问题有m个变量 原问题有n个变量，对偶问题有n个约束条件 原问题的价值系数对应对偶问题的右端项 原问题的右端项对应对偶问题的价值系数 原问题的技术系数矩阵转置后为对偶问题系数矩阵,对偶规则 变量与约束对应关系,对偶问题性质证明的几个重要内容,X 0,st.,AX b,max z = CX,X, Xs 0,st.,AX + IXs = b,max z = CX + 0Xs,对偶问题性质证明的几个重要内容,

8、X 0,st.,AX b,max z = CX,对称形式,Y 0,st.,ATY CT,min w = YTb,原问题为最优解0，即：,CB-CBB-1B 0 CN-CBB-1N 0 -CBB-1 0,C - CBB-1A0,令YT= CBB-1,则有：,CBB-1 0,ATY CT,w = YTb = CBB-1b = z 即此时原问题与对偶问题的解的值是相等的。,则可以得到：,对偶问题的基本性质（对称形）,对称性：对偶问题的对偶问题是原问题 弱对偶性：极大化原问题的任一可行解的目标函数值，不大于其对偶问题任意可行解的目标函数值 对偶定理：若一个问题有最优解，则另一问题也有最优解，且目标函数

9、值相等。若原问题最优基为B，则其对偶问题最优解Y*=CBB-1 无界性：原问题无界，对偶问题无可行解,需要说明的是：这些性质同样适用于非对称形问题,B与B-1,影子价格,从上节对偶问题的基本性质可以看出，当线性规划原问题求得最优解xj*(j=1,n)时，其对偶问题也得到最优解yi*(i=1,.,m)，且代入各自的目标函数后有：,式中bi是线性规划原问题约束条件的右端项，它代表第i种资源的拥有量；对偶变量yi*的意义代表在资源最优利用条件下对单位第i种资源的估价。这种估价不是资源的市场价格，而是根据资源在生产中作出的贡献而做的估价，为区别起见，称为影子价格(shadow price)。 1、资源

10、的市场价格是其价值的客观体现，相对比较稳定，而它的影子价格则有赖于资源的利用情况。因企业生产任务、产品结构等情况发生变化，资源的影子价格也随之改变。 2、影子价格是一种边际价格，若对式中目标函数z求bi的偏导数可得 。这说明yi*的值相当于在资源得到最优利用的生产条件下，bi每增加一个单位时目标函数z的增量。,影子价格,3、资源的影子价格实际上又是一种机会成本。在完全市场经济条件下，当第2种资源的市场价格低于影子价格时，可以买进这种资源；相反，当市场价格高于影子价格时，就会卖出这种资源。随着资源的买进卖出，它的影子价格也将随之发生变化，一直到影子价格与市场价格保持同等水平时，才处于平衡状态。

11、4、在上一节对偶问题的互补松弛性质中有 时，yi=0；当yi0时，有 ，这表明生产过程中如果某种资源bi未得到充分利用时，该种资源的影子价格为零；又当资源的影子价格不为零时，表明该种资源在生产中已耗费完毕。 5、当产品产值大于隐含成本时，表明生产该产品有利，可在计划中安排，否则用这些资源来生产别的产品更为有利，就不在生产计划中安排。这就是单纯形表中各个检验数的经济意义。 6、一般说对线性规划问题的求解是确定资源的最优分配方案，而对于对偶问题的求解则是确定对资源的恰当估价，这种估价直接涉及资源的最有效利用。如在一个大公司内部，可借助资源的影子价格确定一些内部结算价格，以便控制有限资源的使用和考核

12、下属企业经营的好坏。又如在社会上可对一些最紧缺的资源，借助影子价格规定使用这种资源一单位时必须上缴的利润额，以控制一些经济效益低的企业自觉地节约使用紧缺资源，使有限资源发挥更大的经济效益。,对偶单纯形法,对于单纯形法叠代过程本质：1）确保z变大； 2）B-1b 0,由对偶理论知道，当原问题为最优解时，-0且为对偶问题的最优解，因此人们提出对 偶单纯形法。叠代过程本质：1） 0； 2）逐步使B-1b 0,与,6y2 + y3,2,5y1 + 2y2 + y3,1,z= 15 y1 + 24y2 + 5y3,min,z= -15 y1 - 24y2 - 5y3,max,6y2 + y3 y4,=,

13、2,5y1 + 2y2 + y3 y5,1,=,y1, y2, y3, y4, y5,=,0,问题求解,6y2 + y3,2,5y1 + 2y2 + y3,1,z= 15 y1 + 24y2 + 5y3,min,z= -15 y1 - 24y2 - 5y3,max,6y2 + y3 y4,=,2,5y1 + 2y2 + y3 y5,1,=,y1, y2, y3, y4, y5,=,0,问题求解,y4 y5,0 0,-15 -24 -5 0 0,-15 0 -1 -4 0,y2 y5,-24 0,-24 -5,y2 y3,-15/2 0 0 -7/2 3/2,二、灵敏度分析,灵敏度分析是指系统或

14、事物对周围环境变化显示出来的敏感程度,在LP问题中，aij、cj、bi都有可能发生变化，分析这些变化对最优解或目标值的影响程度就是灵敏度分析。,二、灵敏度分析,例如：cj通常表示一些估计或预测的数据，随市场 而变化； aij通常随工艺技术条件的改变而改变； bi则反映了企业资源状况。,公式, Z0= CBB-1b XB= B-1b, A = C - CBB-1 A N = CN - CBB-1 N j = Cj- CBB-1 Pj,二、灵敏度分析,b*= B-1 b,最优解的增量b*与初始b的增量b 成B-1 倍变化,Pj* =B-1 Pj,最优解时的系数增量Pj* 与初始的系数增量Pj也成B

15、-1 倍变化,最优性条件可表达为：,二、灵敏度分析,通常需要分析的项目：,(1)、参数a，b，C在什么范围内变动，对当前方案无影响？,(2)、参数b，b，c中的一个(几个)变动，对当前方案影响程度？,(3)、如果最优方案改变，如何用简便方法求新方案？,二、灵敏度分析,灵敏度分析的步骤可归纳如下：,1、将参数的改变通过计算反映到最终单纯形表上来。 具体计算方法是，按下列公式计算出由参数aij，bi，cj的变化而引起的最终单纯形表上有关数字的变化。 2、检查原问题是否仍为可行解。 3、检查对偶问题是否仍为可行解。 4、按下表所列情况得出结论或决定继续计算的步骤。,二、灵敏度分析,1、分析cj的变化

16、,线性规划目标函数中变量系数cj的变化仅仅影响到检验数(cj-zj)的变化。所以将cj的变化直接反映到最终单纯形表中，只可能出现上页表中前两种情况。 下面举例说明： 例：在第一章例I的美佳公司例子中，(1)若家电I的利润降至1.5元/件，而家电II的利润增至2元/件时，美佳公司最优生产计划有何变化；(2)若家电I的利润不变，则家电II的利润在什么范围内变化时，该公司的最优生产计划将不发生变化？,二、灵敏度分析,解 (1)将家电I、II的利润变化直接反映到最终单纯形表中得到表如下：,因变量x4的检验数大于零，故需继续用单纯形法迭代计算，得表如下：,即美佳公司随家电I、II的利润变化应调整为生产2

17、件I，生产3件II。,二、灵敏度分析,(2)设家电II的利润为(1+m)元，反映到最终单纯形表中，得表如下：,为使上表中的解仍为最优解，应有：,解得：,即家电II的利润c2的变化范围应满足：,二、灵敏度分析,2、分析bj的变化,右端项bi的变化在实际问题中反映为可用资源数量的变化。bi变化反映到最终单纯形表上将引起b列数字的变化，在表2-9中可能出现第一或第三的两种情况。出现第一种情况时，问题的最优基不变，变化后的b列值为最优解。出现第三种情况时，用对偶单纯形法迭代继续找出最优解。 下面举例说明： 例：在上述美佳公司例子中，(1)若设备A和调试工序的每天能力不变，而设备B每天的能力增加到32h

18、，分析公司最优计划的变化；(2)若设备A和设备B每天可用能力不变，则调试工序能力在什么范围内变化时，问题的最优基不变。,二、灵敏度分析,解 (1)因有 ，则：,将其反映到最终单纯形表中得表如下。由于该表中原问题为非可行解，故用对偶单纯形法继续计算，其结果如下量表所示：,二、灵敏度分析,对偶单纯形法处理后结果：,由此美佳公司的最优计划改变为只生产5件家电I。,二、灵敏度分析,(2)设调式工序每天可用能力为(5+m)h，因有,将其反映到最终单纯形表中，其b列数字为：,当b=0时问题的最优基不变，解得-1=m=1。由此调试工序的能力应在4h-6h之间。,二、灵敏度分析,3、增加一个变量xj的分析,增

19、加一个变量在实际问题中反映为增加一种新的产品。其分析步骤为： 1、计算 2、计算 3、若 ，原最优解不变，只需将计算得到的 和 直接写入最终单纯形表中；若 ，则按单纯形法继续迭代计算找出最优。 例：在美佳公司例子中，设该公司又计划推出新型号的家电III，生产一件所需设备A、B及调试工序的时间分别为3h、4h、2h，该产品的预期盈利为3元/件，试分析该种产品是否值得投产；若投产，该公司的最优生产计划有何变化。,二、灵敏度分析,解 设该公司生产x6件家电III，有c6=3，P6=(3,4,2)T,将其反映到最终单纯形表中得表如下:,二、灵敏度分析,因 ，故用单纯形法继续迭代计算结果为：,由上表可知

20、，美佳公司新的最优生产计划应该为每天生产7/2件家电I，51/4件家电III。,二、灵敏度分析,4、分析参数aij的变化,aij的变化使线性规划的约束系数矩阵A发生变化。若变量xj在最终单纯形表中为基变量，则aij的变化分析步骤可参照本节之三；若变量xj在最终单纯形表中为基变量，则aij的 变化将使相应的B和B-1发生变化，因此有可能出现原问题和对偶问题均为非可行解的情况。出现这种情况时，需引进人工变量先将原问题的解转化为可行解，再用单纯形法求解，下面举例说明。 例：在美佳公司的例子中，若家电II每件需设备A、B和调试工时变为8h、4h、1h，该产品的利润变为3元/件，试重新确定该公司最优生产计划。,二、灵敏度分析,解 先将生产工时变化后的新家电II看作是一种新产品，生产量x2，仿上一节的步骤直接计算 和 并反映到最终单纯形表中。其中：,将其反映到最终单纯形表中得表如下。,二、灵敏度分析,因x2已变换为x2，故用单纯形算法将x2替换出基变量中的x2，并在下一个表中不再保留x2，得表如下：,二、灵敏度分析,上表中，原问题与对偶问题均