《第三章 对偶单纯形法》由会员分享，可在线阅读，更多相关《第三章 对偶单纯形法（50页珍藏版）》请在金锄头文库上搜索。
1、对偶理论与灵敏度分析,第二章 对偶理论与灵敏度分析,第一节 对偶问题的提出 第二节 线性规划的对偶理论 第三节 对偶问题的经济解释 第四节 对偶单纯形法,【例2-1】某家电厂利用现有资源生产两种产品，有关数据如下表：,第一节 对偶问题的提出,如何安排生产， 使获利最多？,厂 家,设 产量产量,设：设备A 元时设备B 元时调试工序 元时,承租,付出的代价最小，且对方能接受。,出让代价应不低于 用同等数量的资源 自己生产的利润。,厂家能接受的条件：,出让代价应不低于 用同等数量的资源 自己生产的利润。,收购方的意愿：,厂 家,对 偶 问 题,原 问 题,承 租,厂 家,一对对偶问题,第二节 线性规
2、划的对偶理论,一原问题与对偶问题的关系,二对偶问题的基本性质,一原问题与对偶问题的关系,1对称式的对偶,“”不等式约束条件的原问题与“”不等式约束条件的对偶问题，称为对称式的一对对偶问题。,原问题：,对偶问题：,n个变量，m个约束条件,m个变量，n个约束条件,2约束条件全部为“=”的对偶,原问题：,其中 Y1=(y1, y2, ym)， Y2=(ym+1, ym+2, y2m),对偶问题,3约束条件为“”的对偶,原问题：,对偶问题,4变量0的对偶,原问题：,令X= X1,对偶问题,5变量无约束的对偶,原问题：,对偶问题,6原问题与对偶问题的关系表,【例2-2】试求下述线性规划问题的对偶问题,（
3、P）与(D)的关系对应表：,目标函数max,目标函数min,目标函数系数,约束方程常数列,约束方程常数列,目标函数系数,变量个数n,约束方程个数n,约束方程个数m,变量个数m,约束方程,变量0,0,=,无符号约束,变量0,约束方程,0,无符号约束,=,系数矩阵A,解 ：,（P）与(D)的关系对应表：,目标函数max,目标函数min,目标函数系数,约束方程常数列,约束方程常数列,目标函数系数,变量个数n,约束方程个数n,约束方程个数m,变量个数m,约束方程,变量0,0,=,无符号约束,变量0,约束方程,0,无符号约束,=,系数矩阵A,【例2-3】 试求下述线性规划原问题的对偶问题,解：原问题的对
4、偶问题,【课堂练习】,（P）与(D)的关系对应表：,目标函数max,目标函数min,目标函数系数,约束方程常数列,约束方程常数列,目标函数系数,变量个数n,约束方程个数n,约束方程个数m,变量个数m,约束方程,变量0,0,=,无符号约束,变量0,约束方程,0,无符号约束,=,系数矩阵A,构建对偶问题的规则,要求：1、将所有约束转换成等式；2、将所有决策变量转换成大于等于。,回顾：原问题与对偶问题的关系表,二对偶问题的基本性质,1对称性：对偶问题的对偶问题是原问题。,2弱对偶性：若X(0)是原问题的可行解， Y(0)是对偶问题的可行解，则存在CX(0) Y(0) b。,3无界性：若原问题无界解，
5、 则其对偶问题无可行解 。,4最优性：若X(0)是原问题的可行解， Y(0)是对偶问题的可行解，且C X(0) = Y(0) b ，则X(0)，Y(0)是最优解。,5对偶定理：若原问题有最优解， 那么对偶问题也有最优解；且目标函数值相等。,6互补松弛性：若X(0)是原问题的可行解， Y(0)是对偶问题的可行解，则YsX(0)=0和Y(0)Xs=0 当且仅当X(0)，Y(0)是最优解。 其中Xs和Ys分别为原问题和对偶问题的松弛变量的可行解.,【例2-4】已知线性规划问题,min w=2x1+3x2+5x3+2x4+3x5 x1+x2+2x3+x4+3x54 2x1-x2+3x3+x4+x53x
6、j0，j=1，2，5 已知其对偶问题的最优解为y1*=4/5，y2*=3/5；z=5。试用对偶理论找出原问题的最优解 。,【例2-4】已知线性规划问题解：先写出它的对偶问题,max z=4y1+3y2 y1+2y22 y1-y23 2y1+3y25 y1+y22 3y1+y23 y1，y20,【例2-4】已知线性规划问题将y1* =4/5,y2* =3/5的值代入约束条件，,得=1/53，=17/55，=7/52它们为严格不等式；由互补松弛性得x2*=x3*=x4*=0。 因y1，y20；原问题的两个约束条件应取等式，故有x1*+3x5*=4，2x1*+x5*=3 求解后得到x1*=1,x5*
7、=1；故原问题的最优解为X*=(1，0，0，0，1)T；w*=5,1、原始问题是利润最大化的生产计划问题,单位产品的利润（元/件）,产品产量（件）,总利润（元）,资源限量（吨）,单位产品消耗的资源（吨/件）,剩余的资源（吨）,消耗的资源（吨）,第三节 对偶问题的经济解释,2、对偶问题,资源限量（吨）,资源价格（元/吨）,总利润（元）,对偶问题是资源定价问题，对偶问题的最优解y1、y2、.、ym称为m种资源的影子价格（Shadow Price）,原始和对偶问题都取得最优解时，最大利润 max z=min w,3、资源影子价格的性质,从对偶定理可知，当达到最优解时，原问题和对偶问题的目标函数值相等
8、，即z=CX(0)=Y(0)b=CBB-1b .,也即z=CX(0)=Y(0)b=CBB-1b =y1(0)b1+ y2(0) b2 + +ym(0) bm 其中 X(0),Y(0)分别是原问题和对偶问题的最优解。,现在考虑在最优解处，常数项bi的微小变动对目标函数值的影响(不改变原来的最优基).求z对bi的偏导数，可得：, ,这说明，若原问题的某一约束条件的右端常数项bi增加一个单位，则由此引起的最优目标函值的增加量，就等于该约束条件相对应的对偶变量的最优值。,最优变量yi(0) 的值，就相当于对单位第I种资源在实现最大利润时的一种估价。这种估价是针对具体企业具体产品而存在的一种特殊价格，称
9、它为“影子价格”。,【例1-3】 求下列问题的最优解。,影价格及其经济解释,第四节 对偶单纯形法,6(LP)的检验数的相反数对应于(DP)的一个基解，其中第j个决策变量xj的检验数的相反数对应于(DP)中第j个松弛变量ysj的解，第i个松弛变量xsi的检验数的相反数对应于第i个对偶变量yi的解。,二对偶问题的基本性质,【例2-4】线性规划,（1）用单纯形方法求最优解； （2）求每步迭代对应对偶问题的基本解。,1,2,3,解：,原问题与对偶问题解之间的对应关系指出：在单纯形表中进行迭代时，在b列中得到的是原问题的基可行解，而在检验数行得到的是对偶问题的基解。 通过逐步迭代，当在检验数行得到对偶问
10、题的解也是基可行解时，已得到最优解。即原问题与对偶问题都是最优解。 根据对偶问题的对称性，可以这样考虑：若保持对偶问题的解是基可行解，即cjCBB-1Pj0，而原问题在非可行解的基础上，通过逐步迭代达到基可行解，这样也得到了最优解。其优点是原问题的初始解不一定是基可行解，可从非基可行解开始迭代。,设原问题为 max z=CX AX=b X0 又设B是一个基。不失一般性，令B=(P1，P2，Pm)，它对应的变量为 XB=(x1，x2，,xm)。当非基变量都为零时，可以得到XB=B-1b。若在B-1b中至少有一个负分量，设(B-1b)i0，并且在单纯形表的检验数行中的检验数都为非正，即对偶问题保持
11、可行解。 每次迭代是将基变量中的负分量xl取出，去替换非基变量中的xk，经基变换，所有检验数仍保持非正。从原问题来看，经过每次迭代，原问题由非可行解往可行解靠近。当原问题得到可行解时，便得到了最优解。,2对偶单纯形法的计算步骤,列出初始单纯形表,最优性检验,根据线性规划问题，确定一个对偶可行的基解，列出初始单纯形表。,检查b列的数，若都为非负，则已得到最优解。停止计算。若b列的数中，还有分量为负数，则进行下一步计算。,确定换出变量,按min (B-1b)i | (B-1b)i0，则无可行解，停止计算。,如果 有alj 0 ( j=1,2, n) ,则计算,确定xk为换入 变量，且保持得到的对偶
12、问题的解是基可行解。,迭代运算,以alk为主元素，对单纯形表进行迭代运算，得到新单纯表。,重复,【例2-5】用对偶单纯形法求解,解：,其中x4,x5为松弛变量,原最优 X*=(11/5,2/5,0,0,0)T，对偶最优 Y*=(8/5,1/5),从以上求解过程可以看到对偶单纯形法有以下优点： (1) 初始解可以是非可行解，当检验数都为负数时就可以进行基的变换，这时不需要加入人工变量，因此可以简化计算。 (2) 当变量多于约束条件，对这样的线性规划问题用对偶单纯形法计算可以减少计算工作量，因此对变量较少，而约束条件很多的线性规划问题，可先将它变换成对偶问题，然后用对偶单纯形法求解。 (3) 在灵
13、敏度分析及求解整数规划的割平面法中，有时需要用对偶单纯形法，这样可使问题的处理简化。对偶单纯形法的局限性主要是，对大多数线性规划问题，很难找到一个对偶问题初始可行基，因而这种方法在求解线性规划问题时很少单独应用。,对偶单纯形法的计算步骤（min）,列出初始单纯形表,最优性检验,根据线性规划问题，确定一个对偶可行的基解，列出初始单纯形表。,检查b列的数，若都为非负，则已得到最优解。停止计算。若b列的数中，还有分量为负数，则进行下一步计算。,确定换出变量,按min (B-1b)i | (B-1b)i0，则无可行解，停止计算。,如果 有alj 0 ( j=1,2, n) ,则计算,确定xk为换入 变量，且保持得到的对偶问题的解是基可行解。,迭代运算,以alk为主元素，对单纯形表进行迭代运算，得到新单纯表。,重复,【例2-6】用对偶单纯行法求解,初始单纯形表,第一次迭代,第二次迭代,第三次迭代,由互补松弛定理，容易识别原问题的最优解。,作业p75 2.8 (1),结 束,
