运筹学基础及应用第2章-线性规划的对偶问题(胡运权版).ppt

2.原问题与对偶问题 性质1 对称性定理：对偶问题的对偶是原问题 min Z’= - CX s.t. - AX≤- b X ≥0 对偶的定义 对偶的定义 max W’ = -Yb s.t. YA≥ C Y ≤ 0 3.对偶问题的基本性质 性质2 弱对偶原理(弱对偶性)：设 和 分别是问题(P)和(D)的可行解，则必有 推论1: 原问题任一可行解的目标函数值是其对偶问题目标函数值的下界；反之，对偶问题任意可行解的目标函数值是其原问题目标函数值的上界。 推论2: 在一对对偶问题（P）和（D）中，若其中一个问题可行但目标函数无界，则另一个问题无可行解；反之不成立。这也是对偶问题的无界性。（无界性） 3.对偶问题的基本性质 无界 （原） 无可 行解 （对） 关于无界性有如下结论： 问题无界 无可行解 无可行解 问题无界 对偶问题 原问题 例2.5 3.对偶问题的基本性质 推论3：在一对对偶问题（P）和（D）中，若一个可行（如P），而另一个不可行（如D），则该可行的问题目标函数值无界。 试估计它们目标函数的界，并验证弱对偶性原理。 （P） 例2.6 3.对偶问题的基本性质 解： （D） 由观察可知： =（1.1.1.1）， =（1.1），分别是（P）和（D）的可行解。Z=10 ，W=40，故有 ，弱对偶定理成立。由推论⑴可知，W 的最小值不能小于10，Z 的最大值不能超过40。 ＜ 3.对偶问题的基本性质 性质3 最优性定理：如果 是原问题的可行解， 是其对偶问题的可行解，并且: 则 是原问题的最优解， 是其对偶问题的最优解。 例如:在一对对偶问题（P）和（D）中，可找到 X*=（0.0.4.4）， Y*=（1.2，0.2）,且Z=W28 ， 则X*，Y*分别是 P和D 的最优解。 3.对偶问题的基本性质 性质4 强对偶性：若原问题及其对偶问题均具有可行解，则两者均具有最优解，且它们最优解的目标函数值相等。 还可推出另一结论：若（LP）与（DP）都有可行解，则两者都有最优解，若一个问题无最优解，则另一问题也无最优解。 性质5 互补松弛性：设X0和Y0分别是P问题 和 D问题 的可行解，则它们分别是最优解的充要条件是： 其中：Xs、Ys为松弛变量 3.对偶问题的基本性质 性质5的应用： 该性质给出了已知一个问题最优解求另一个问题最优解的方法，即已知Y＊求X＊或已知X＊求Y＊ 互补松弛条件 由于松弛变量都非负，要使求和式等于零，则必定每一分量为零，因而有下列关系： 若Y＊≠0，则Xs必为0；若X＊≠0，则Ys必为0 利用上述关系，建立对偶问题（或原问题）的约束线性方程组，方程组的解即为最优解。 3.对偶问题的基本性质 例2.7 已知线性规划 的最优解是X＊=(6,2,0)T,求其对偶问题的最优解Y＊。 解：写出原问题的对偶问题，即 标准化 3.对偶问题的基本性质 设对偶问题最优解为Y＊＝(y1，y2),由互补松弛性定理可知，X＊和 Y＊满足： 即： 因为X1=6≠0，X2=2≠0，所以对偶问题的第一、二个约束的松弛变量等于零，即y3＝0，y4＝0，带入方程中： 解此线性方程组得y1=1,y2=1,从而对偶问题的最优解为： Y＊=(1,1)，最优值w=26。 3.对偶问题的基本性质 例2.8 已知线性规划 的对偶问题的最优解为Y＊=(0,-2)，求原问题的最优解。 解: 对偶问题是 标准化 3.对偶问题的基本性质 设对偶问题最优解为X＊＝(x1，x2 ，x3)T ,由互补松弛性定理可知，X＊和 Y＊满足： 将Y＊ =(0,-2)带入由方程可知，y3＝y5＝0，y4＝1。 ∵y2=-2≠0 ∴x5＝0 又∵y4=1≠0 ∴x2＝0 将x2，x5分别带入原问题约束方程中，得： 解方程组得：x1=-5,x3=-1, 所以原问题的最优解为 X＊=(-5,0,-1)，最优值z=-12 3.对偶问题的基本性质 原问题与对偶问题解的对应关系小结 对应关系 原问题 最优解 无界解 无可行解 对偶问题 最优解 (Y,Y) (N,N) —— —— 无界解 —— —— (Y,Y) 无可行解 —— (Y,Y) 无法判断 3.对偶问题的基本性质 1. 影子价格的数学分析： 定义：在一对 P 和 D 中，若 P 的某个约束条件的右端项常数bi （第i种资源的拥有量）增加一个单位时，所引起目标函数最优值z* 的改变量称为第 i 种资源的影子价格，其值等于D问题中对偶变量yi*。 由对偶问题得基本性质可得： 4.对偶问题的经济解释－影子价格 2. 影子价格的经济意义 1）影子价格是一种边际价格 在其它条件不