运筹学大学课件42对偶问题的基本性质文档

返回继续第二节对偶问题的基本性质单纯形法计算的矩阵描述引例对称性弱对偶性最优性对偶性（强对偶性）互补松弛性

单纯形法的矩阵描述不妨设基为基变量非基变量设线性规划问题则

单纯形法的矩阵描述其中令得当前的基解为：当前基解约束方程组当前目标值目标函数令得当前的目标函数值为：

单纯形法的矩阵描述当前检验数

单纯形法的矩阵描述检验数其中当前对应的系数列单纯形法计算的矩阵描述线性规划问题化为标准型，引入松弛变量初始单纯形表非基变量基变量初始基变量单纯形法计算的矩阵描述基变量非基变量当基变量为时，新的单纯形表单纯形法计算的矩阵描述当前检验数当前基解单纯形法计算的矩阵描述

从上两表可看出，当迭代后基变量为XB时，其在初始单纯形表中的系数矩阵为B，则有：

(1)对应初始单纯形表中的单位矩阵I，迭代后的单纯形表中为B-1(2)初始单纯形表中基变量Xs

＝b，迭代后的表中

(3)初始单纯形表中约束系数矩阵为[A,I]=[B,N,I]，迭代后的表中约束系数矩阵为[B-1A,B-1I]=[B-1B,B-1N,B-1I]=[I,B-1N,B-1]。。

单纯形法计算的矩阵描述

(4)若初始矩阵中变量xj的系数向量为Pj迭代后为

则有

(5)当B为最优基时,在新的单纯形表应有单纯形法计算的矩阵描述

可看出这时检验数行，若取其相反数恰好是其对偶问题的一个可行解。将这个解代入对偶问题的目标函数值，有当原问题为最优解时，这时对偶问题为可行解，且两者具有相同的目标函数值对偶问题原问题收购厂家引例（）原问题的变量原问题松弛变量对偶问题剩余变量对偶问题的变量化为极小问题原问题化为极小问题，最终单纯形表：原问题的变量原问题松弛变量对偶问题剩余变量对偶问题的变量对偶问题用两阶段法求解的最终的单纯形表（）原问题的变量原问题松弛变量对偶问题剩余变量对偶问题的变量化为极小问题原问题最优解对偶问题最优解原问题化为极小问题，最终单纯形表：两个问题作一比较:1.两者的最优值相同2.变量的解在两个单纯形表中互相包含原问题最优解（决策变量）对偶问题最优解（决策变量）

对偶问题的松弛变量原问题的松弛变量从引例中可见：原问题与对偶问题在某种意义上来说，实质上是一样的，因为第二个问题仅仅在第一个问题的另一种表达而已。理论证明：原问题与对偶问题解的关系对偶问题的基本性质一、对称定理：定理：对偶问题的对偶是原问题。设原问题（1）对偶问题（2）二、弱对偶性定理：

——若和分别是原问题（1）及对偶问题（2）的可行解，则有证明：对偶问题的基本性质从弱对偶性可得到以下重要结论：（1）极大化问题（原问题）的任一可行解所对应的目标函数值是对偶问题最优目标函数值的下界。（2）极小化问题（对偶问题）的任一可行解所对应的目标函数值是原问题最优目标函数值的上界。（3）若原问题有可行解，但其目标函数值无界，则对偶问题无可行解。（4）若对偶问题可行，但其目标函数值无界，则原问题无可行解。（5）若原问题有可行解而其对偶问题无可行解，则原问题目标函数值无界。（6）对偶问题有可行解而其原问题无可行解，则对偶问题的目标函数值无界。例题判断下例说法是否正确，为什么？A如果线性规划的原问题存在可行解，则其对偶问题也一定存在可行解B如果线性规划的对偶问题无可行解，则原问题也一定无可行解。C在互为对偶的一对原问题和对偶问题中，不管原问题是求极大或者极小，原问题可行解的目标函数值都一定不超过其对偶问题可行解的目标函数值。A不对。因为原问题为无界解时（它当然有可行解），其对偶问题无可行解。B此句为A的逆否命题，所以也不对。C不对。因为哪个问题是原问题，哪个问题是对偶问题是相对而言的。原问题对偶问题三、最优性定理：

——若和分别是（1）和（2）的可行解，且有则分别是（1）和（2）的最优解。

则为（1）的最优解，反过来可知：也是（2）的最优解。证明：因为（1）的任一可行解均满足对偶问题的基本性质证明：原问题与对偶问题的解一般有三种情况：一个有有限最优解另一个有有限最优解。一个有无界解另一个无可行解。两个均无可行解。四、对偶定理（强对偶性）：

——若原问题及其对偶问题有一个有最优解，则另一个也有最优解，且它们最优解的目标函数值相等。对偶问题的基本性质从强对偶性可得到以下重要结论：(1)若原问题有最优解X，对应最优基B，则是对偶问题的最优解，且两者的最优值相等。(2)原问题最优表中，松弛变量的检验数的反号数，是对偶问题的最优解。五、互补松弛性：

——若分别是原问题（1）与对偶问题（2）的可行解，分别为（1）、（2）的松弛变量，则：即：为最优解原问题第i条约束

A的第i行

说明：在线性规划问题的最优解中，如果对应某一约束条件的对偶变量值为非零，则该约束条件去严格等式；反之如果约束条件取严格不等式，则其对应的对偶变量一定为零。另一方面：对偶问题的第j条约束性质5告诉我们已知一个问题的最优解时求另一个问题的最优解的方法，即已知求或已知求。

两式称为互补松弛条件。将互补松弛条件写成下式

由于变量都非负，要使求和式等于零，则必定每一分量为零，因而有下列关系：(1)当

时，,反之当,时；利用上述关系，建立对偶问题(或原问题)的约束线性方程组，方程组的解即为最优解。【例】已知线性规划的最优解是,求对偶问题的最优解。【解】对偶问题是因为x1≠0，x2≠0，所以对偶问题的第一、二个约束的松弛变量等于零，即解此线性方程组得y1=1,y2=1,从而对偶问题的最优解为Y=(1，1)T，最优值w=26。【例】已知线性规划的对偶问题的最优解为Y=(0，-2)T，求原问题的最优解。【解】对偶问题是解方程组得：x1=－5,x3=－1,所以原问题的最优解为X=(－5，0，－1)T，最优值Z=－12。因为y2≠0，所以原问题第二个松弛变量=0，由y1=0、y2=-2知，松弛变量故x2=0，则原问题的约束条件为线性方程组：互补松弛定理应用：（1）从已知的最优对偶解，求原问题最优解，反之亦然。（2）证实原问题可行解是否为最优解。（3）从不同假设来进行试算，从而研究原问题、对偶问题最优解的一般性质。（4）非线性的方面的应用。以上性质同样适用于非对称形式。一个问题max另一个问题min有最优解有最优解性质4无无最优解无最优解性质4最优无界解(有可行解)无可行解性质2解无可行解无界解(有可行解)性质2应用已知最优解通过解方程求最优解性质5已知检验数检验数乘以－1求得基本解性质6根据对偶性质,可将原问题与对偶问题解的对应关系列表如下：【性质6】LP(max)的检验数的相反数对应于DP(min)的一组基本解。其中第j个决策变量xj的检验数的相反数对应于(DP)中第j个松弛变量