第三章线性规划的对偶定理

第三章线性规划的对偶原理3.1线性规划的对偶问题3.2对偶问题的基本性质和基本定理3.3对偶单纯形法3.4灵敏度分析第一节线性规划的对偶问题一、对偶问题的提出二、原问题与对偶问题的数学模型三、原问题与对偶问题的对应关系实例：某家电厂家利用现有资源生产两种产品，有关数据如下表：设备A

设备B调试工序利润（元）0612521115时24时5时产品Ⅰ产品ⅡD一、对偶问题的提出如何安排生产，使获利最多？厂家设

Ⅰ产量–––––Ⅱ产量–––––设：设备A——元／时设备B––––元／时调试工序––––元／时收购付出的代价最小，且对方能接受。出让代价应不低于用同等数量的资源自己生产的利润。设备A

设备B调试工序利润（元）0612521115时24时5时ⅠⅡD厂家能接受的条件：收购方的意愿：单位产品Ⅰ出租收入不低于2元单位产品Ⅱ出租收入不低于1元出让代价应不低于用同等数量的资源自己生产的利润。厂家对偶问题原问题收购厂家一对对偶问题3个约束2个变量2个约束3个变量原问题对偶问题一般规律特点：

1．

2．限定向量b价值向量C

（资源向量）

3．一个约束一个变量。

4．的LP约束“”的

LP是“”的约束。

5．变量都是非负限制。其它形式的对偶?二、原问题与对偶问题的数学模型1．对称形式的对偶当原问题对偶问题只含有不等式约束时，称为对称形式的对偶。原问题对偶问题情形一：原问题对偶问题情形二：证明对偶2、非对称形式的对偶若原问题的约束条件是等式，则原问题对偶问题推导:原问题

根据对称形式的对偶模型,可直接写出上述问题的对偶问题:令，得对偶问题为：证毕。三、原问题与对偶问题的对应关系

minmax

，变变约不变

例:对偶问题为结束线性规划的对偶问题第二节对偶问题的基本性质对称性弱对偶性最优性对偶性（强对偶性）互补松弛性一、对称定理：定理：对偶问题的对偶是原问题。证：设原问题（1）将做问题(2)如下变换其对偶问题为对偶问题（2）转化得原问题二、弱对偶性定理：

若和分别是原问题（1）及对偶问题（2）的可行解，则有证明：从弱对偶性可得到以下重要结论：（1）极大化问题（对偶问题）的任一可行解所对应的目标函数值是对偶问题最优目标函数值的下界。（2）极小化问题（原问题）的任一可行解所对应的目标函数值是原问题最优目标函数值的上界。（3）若原问题可行，但其目标函数值无界，则对偶问题无可行解。（4）若对偶问题可行，但其目标函数值无界，则原问题无可行解。（5）若原问题有可行解而其对偶问题无可行解，则原问题目标函数值无界。（6）对偶问题有可行解而其原问题无可行解，则对偶问题的目标函数值无界。原问题对偶问题原问题与对偶问题解的对应关系三、最优性定理：若和分别是（1）和（2）的可行解，且有则分别是(1)和(2)的最优解。

则为（1）的最优解，反过来可知：也是（2）的最优解。证明：因为（1）的任一可行解均满足四、对偶定理（强对偶性）：若原问题及其对偶问题均具有可行解，则两者均具有最优解，且它们最优解的目标函数值相等。证明：设X(0)为原问题的最优基本可行解，相应的基为B,则非基变量的检验数为即有，即，令有，即Y(0)是对偶问题的可行解，有因X(0)为原问题的最优解，有原问题与对偶问题的解一般有三种情况：一个有有限最优解另一个有有限最优解。一个有无界解另一个无可行解。两个均无可行解。五、对称形式的互补松弛定理：若X(0)和Y(0)分别为原问题和对偶问题的可行解，则X(0)和Y(0)都是最优解的充要条件是，对所以i,j,下列关系成立：1.如果2.如果，必有，必有3.如果4.如果，必有，必有其中Pj是A的第j列，Ai是A的第i行.证明：(必要性)

因为X(0)、Y(0)分别为原问题和对偶问题的最优解。又C≥Y(0)A,X(0)≥0,故有

CX(0)≥Y(0)AX(0)

同理由AX(0)≥b,Y(0)≥0，有

Y(0)AX(0)≥Y(0)b

由对偶定理有

CX(0)=Y(0)AX(0)=Y(0)b即(C-Y(0)A)X(0)=0

Y(0)(AX(0)–b)=0所以1、2成立3，4成立（充分性）设X(0)、Y(0)分别为原问题和对偶问题的可行解.所以由1、2由3，4(C-Y(0)A)X(0)=0Y(0)(AX(0)–b)=0CX(0)=Y(0)AX(0)

Y(0)

AX(0)=Y(0)bCX(0)=Y(0)b即X(0)、Y(0)分别为原、对的最优解互补松弛定理应用：从已知的最优对偶解，求原问题最优解，反之亦然六、非对称形式的对偶的互补松弛定理：若X(0)和Y(0)分别为原问题和对偶问题的可行解，则X(0)和Y(0)都是最优解的充要条件是，对所有的j,下列关系成立：1.如果，必有2.如果，必有思考题如下线性规划问题已知其对偶问题的最优解为试用对偶理论找出原问题的最优解.提示：写出对偶问题，根据互补松弛定理求解.最优解为：结束对偶问题的基本性质第三节对偶单纯形法

对偶单纯形法的基本思路对偶单纯形法的计算步骤关于初始对偶可行的基本解对偶单纯形法的基本思路单纯形法的基本思路：原问题基可行解最优解判断对偶问题的可行解对偶问题最优解判断对偶单纯形法基本思路对偶单纯形法的计算步骤线性规划问题

不妨设为对偶问题的初始可行基，则。

若，即表中原问题和对偶问题均为最优解，否则换基。换基方法：确定换出基变量

对应变量为换出基的变量确定换入基变量为主元素，为换入基变量初始可行基例、用对偶单纯形法求解线性规划问题：对偶问题的初始可行基例、用对偶单纯形法求解线性规划问题：使对偶问题基变量可行,换出

换出换出例、用对偶单纯形法求解线性规划问题：最优解例、用对偶单纯形法求解线性规划问题：练习用对偶单纯形法求解线性规划问题：结束对偶单纯形法第四节灵敏度分析一、分析的变化二、分析的变化三、分析的变化四、增加一个变量的分析五、增加一个约束条件的分析问题：当这些系数中的一个或多个发生变化时，原最优解会怎样变化？当这些系数在什么范围内变化时，原最优解仍保持不变？若最优解发生变化，如何用最简单的方法找到现行的最优解？灵敏度分析的步骤归纳如下：（1）将参数的改变计算反映到最终单纯形表上；（2）检查原问题是否仍为可行解；（3）检查对偶问题是否仍为可行解；（4）按下表所列情况得出结论和决定继续计算的步骤。一、改变价值向量C1.若cr是非基变量的系数：

r’=cr+

cr-∑ciair=

r+

cr若

r’≥0,即cr≥-

r

，则最优解不变若

r’<0，将最优单纯形表中的检验数

r

用

r’取代，以xr为换入变量，cr

换成cr’，继续单纯形法的表格计算。

考虑检验数设cr变化cr为cr’=cr+

cr2.若cr是基变量的系数：

设最终表内xr是第k行约束是的基变量，即xr=xBk.原检验数为

j，新检验数为

j’，则若则所有

j’≥0，最优解不变，否则迭代例考虑该规划问题，当c1=-1.5时，讨论解的变化解：在最终表中，x1是第2行约束的基变量，r=1，k=2，即所以时，解不变.原问题最优解对偶问题最优解原问题的最终单纯形表：最终单纯形表0×5/4-1.5×1/4-1×（-1/4）=1/8二、改变限定向量b设分量br

变化为br+

br

，根据第1章的讨论，最优解的基变量xB=B-1b，那么只要保持B-1(b+

b)≥0，则最优基不变，即基变量保持，只有值的变化；否则，需要利用对偶单纯形法继续计算。例：若在上例中求b2=32时的最优解及最优值代入单纯形表中可行性改变，用对偶单纯形法换基求解。主元新的最优解换基迭代得：三、增加一个变量的分析

增加一个变量，其价值系数为，系数列向量为。分析步骤：1、计算2、计算3、若，原最优解不变；若，则按单纯形表继续迭代计算找出最优解。例：在上例中增加变量x6,其相应系数为解：代入最终原单纯形表中主元若对应的变量为非基变量，参见三的分析。四、改变约束矩阵A若对应的变量为基变量，B将改变。需引入人工变量求出可行解，再用单纯形法求解。设原问题为标准型四、改变约束矩阵A增加一个约束其中设原最优基为B，各基向量为A的前m例，最优解为引入松弛得则的检验数为又基变量检验数即问题为对偶可行.若则用对偶单纯形法求解.若则对偶可行的基本解为最优解例：在上例中增加约束条件，是讨论最优解原最优解为（3.5，7.5，1.5）不满足新约束，将其放入