《对偶问题的基本性质.ppt》由会员分享，可在线阅读，更多相关《对偶问题的基本性质.ppt（24页珍藏版）》请在金锄头文库上搜索。
1、3 3 对偶问题的基本性质对偶问题的基本性质 Max z = CXMax z = CXMin w = Y bMin w = Y bs t .AX s t .AX b b s t . YA s t . YA C C X X 0 0 Y Y 0 0(1) (1) 弱对偶性：弱对偶性： 若若 X X0 0原问题可行解，原问题可行解，Y Y0 0对偶问题可行对偶问题可行解解, ,则则 CXCX0 0 Y Y0 0 b b证明证明 Y Y0 0 0 0， AXAX0 0 b b， Y Y0 0 AX AX0 0 Y Y0 0 b b，而而 Y Y0 0 A A C C ， CXCX0 0 Y Y0 0A
2、XAX0 0 ， CXCX0 0 Y Y0 0 AX AX0 0 Y Y0 0 b b （2）最优性：）最优性： 若若 X X0 0原问题可行解，原问题可行解，Y Y0 0对偶问题可行解，且对偶问题可行解，且 CXCX0 0 = = Y Y0 0 b b 则则 X X0 0原问题最优解，原问题最优解， Y Y0 0对偶问题最优解对偶问题最优解证明：设 X* 原问题最优解， Y* 对偶问题最优解 则 CX0 CX* Y* b Y0 b 但 CX0 = Y0 b， CX0 = CX* = Y* b = Y0 b X0原问题最优解， Y0对偶问题最优解证毕。 （3）无界性）无界性若原问题若原问题(对
3、偶问题）最优解无界，则对偶问题对偶问题）最优解无界，则对偶问题（原问题）无可行解（原问题）无可行解 证：有性质1，C X0 Y0 b，当 CX0 时，则不可能存在Y0，使得 C X0 Y0 b 。 注：逆定理不成立，即 如果原问题（对偶问题）无可行解，那么 对偶问题（或原问题）“解无界”不成立。（4 4）强对偶性（对偶定理）强对偶性（对偶定理） 若原问题有最优解，则对偶问题一定有最优解，若原问题有最优解，则对偶问题一定有最优解，且有且有 z z max max = w = w minmin证： 由 = C- CB B-1 A 0 令 CBB-1 = Y* ，得 Y* A C若 -Y * = -
4、CBB-1 0，则 Y* 0 因此， Y*是对偶问题的可行解，又 CX* = CB (B-1 b) = CB B-1b = Y* b Y*是对偶问题的最优解。原问题（或对偶问题）原问题（或对偶问题） 对偶问题（或原问题）对偶问题（或原问题）原问题和对偶问题解之间关系：原问题和对偶问题解之间关系：有最优解有最优解 有最优解有最优解无界无界 无可行解无可行解无可行解无可行解无可行解或无界无可行解或无界例例 证明如下证明如下LP问题无界问题无界（5）互补松弛性）互补松弛性例：已知如下问题的对偶问题最优解为例：已知如下问题的对偶问题最优解为求原问题的最优解求原问题的最优解解：对偶问题为解：对偶问题为（
5、6）原问题的检验数行对应对偶问题的一）原问题的检验数行对应对偶问题的一个基本解个基本解5 对偶单纯形法对偶单纯形法例： min z=2x1+3x2 max z=-2x1-3x2+0x3 +0x4 s.t x1+x23 标准化 s.t x1+x2-x3=3 x1+2x2 4 x1+2x2-x4=4 x10, x20 xj 0, (j=1,2,3,4) max z=-2x1-3x2+0x3 +0x4 s.t - x1-x2+x3=-3 - x1-2x2+x4=-4 xj 0, (j=1,2,3,4) Cj x1x2x3x4XBbCB-1 -1 1 0 -1 -2 0 1-2 -3 0 0-3 -4
6、x3 x400cj - zj -2-300-1/2 0 1 -1/2 1/2 1 0 -1/2x3 x2-1 2cj - zj -1/2 0 0 -3/2 0 -31 0 -2 1 0 1 1 -1x1 x221cj - zj 0 0 -1 -1-2 -3列单纯表计算：列单纯表计算：对偶单纯形法步骤：对偶单纯形法步骤：1.列初始单纯形表，使得所有检验数j 0 ；2.出基变量：取min bi0 = bl x(l)3.入基变量：min |alk0= xk4.主元素： alk5.迭代：同单纯形法，新单纯表中pk化为单位向量cj-zjalj说明：10 使用对偶单纯形法时，初始表中检验数必须全部为j 0，即使得其对偶问题为可行解，20 为便于说明，这里采取从原问题角度叙述迭代步骤。
