运筹学用对偶分析原问题最优解名校讲义

1、第三讲 用对偶分析原问题最优解,1 初步分析线性规划解的几种可能性 2 线性规划解的求解方法之一：图解法 3 对偶性质及平衡定理 4 基础解及基础可行解,1 初步分析线性规划解的几种可能性 （1）,已知线性规划的标准形式为 AX=b, XO, CTX=min 满足前2条的解为可行解，同时又满足第3条的为最优解。 从解的性质看，线性规划有下述几种可能： 1不存在可行解或无解，例如规划 x1= x1 0 无可行解 3 x1=min,1 初步分析线性规划解的几种可能性 （2）,2存在可行解，但找不到最优解，例如规划 x1x2=0 x1，x20 2 x1=min 显然，令x1=x2=,为任意非负值都是

2、可行解， 当+，则目标函数2 x1，故找不出使目标函数 取极小值的具体解X。,1 初步分析线性规划解的几种可能性 （3）,3存在最优解，但不是唯一的。例如规划 x1+x2=1 x1，x2o x1+ x2=min 显然 两点连线上的所有点 都是最优解，（见图1-1） 4一般情况有无穷多可行解，但有唯一最优解。,2 线性规划解的求解方法之一：图解法 （1）,例1-3 求解下述线性规划 2x1+x2x3=4(1) xj0 j=1,2,3(2) 3x1+5x2=min(3) 将(1)式中的x3移至右边，常数4移至左边， 得： 2x1+x24=x30 移项得：2x1+x24 于是变为两维线性规划问题，其

3、约束可行 域可用直角坐标系表示,如图1-2。,2 线性规划解的求解方法之一：图解法 （2）,图1-2中，阴影部分为可行域，若要求出最优点，必须作出目标 函数的等值线，然后令等值线向最小值方向（即最优方向）移 动，直到离开可行域的瞬间为止，此时的交点即为最优点。 图中直线L1，L2，L3即为目标值分别为12，9及6的等值线，L3与 可行域的顶点B（x12，x20），L3再向左下方移动，必离开 可行域，于是该点即为线性规划之最优解，即：X （x1，x2， x3）=(2,0,0)，目标值为3x1+5x26。 图解法简单易行，但只适于两维问题（本题虽是三维，但很容 易变为两维）。对于高维问题，只能采用

4、其它的办法求解。很 幸运，该法已经找到，这就是以后将要介绍的单纯形法。,3 对偶性质及平衡定理 （1）,1弱对偶性（不等式性质） 设原线性规划为AX=b，X0，CTX=min 其对偶规划为YTACT, YT b=max 若X、Y分别是原问题和对偶问题的可行解，则必存在关系式CTXYTb 证明：因为X、Y分别是原问题及对偶问题的可行解，因此 YTAX=YT(AX)=YTb 及 YTAX =(YTA)XCTX 故 CTXYTb 这是一个很有用的性质，因为有时并不需要精确求出线性规划问题最优解，只需了解最优目标值的范围，那么采用求解对偶可行解就显得十分方便。,3 对偶性质及平衡定理 （2）,2强对偶

5、性（对偶最优性） 若 分别是原问题与对偶问题可行解，且 ， 则 必分别是原问题及对偶问题的最优解。 证明：设X是原向题任一可行解，则从弱对偶性知， ，可见 是原问题最优解。 同理，设Y是对偶问题任一可行解，则 ，故 是对偶问题最优解。,3 对偶性质及平衡定理 （3）,1平衡定理 设原问题为 (4) xj0 (j=1,2,，n) (5) (6) 其对偶形式为 (7) (8),3 对偶性质及平衡定理 （4）,则平衡定理阐述如下：若xj(j=1,2，n)和yi（i=1,2,，m）分 别是原问题和对偶问题之可行解，必存在下述关系： （即弱对偶性） 上式中两边相等的充分必要条件是： 或 xj=0 或 x

6、j0,但,3 对偶性质及平衡定理 （5）,证明：根据(5)式和(7)式可得： (9),3 对偶性质及平衡定理 （6）,证明：若使 ，即表明(9)式左边为0（不等式 变为等式），而该式是由n 项和组成，每一项 是两因子乘积，每个因子都0。 故每一项都0。若使n项为0，势必使每一项为0，即： 则其中至少有一个因子为0。 于是得出，或xj=0；或xj0，必使 。,3 对偶性质及平衡定理 （7）,从强对偶性知，符合平衡定理第条时的可行解X，Y必是最 优解，于是，平衡定理为寻找线性规划最优解提供了一种方 法。亦即，在若干个问题的可行解X中，若是有一组解所对应 的对偶可行解，使得Xj0所对应的对偶约束条件

7、为等式，则 此时的解必为最优解。 例1-4 应用平衡定理解下述规划,3 对偶性质及平衡定理 （8）,其对偶形式为 首先令原问题中任两个变量为0（因有2个约束条件，这样可 求出唯一解），试探求出一组原问题可行解。 例如，令x1=x4=0，则得：,3 对偶性质及平衡定理 （9）,故此时X=(0,2,3,0)T是原问题可行解。 为检验是否为最优解，令非零xj对应的对偶约束为等式，求 平衡解Y。即令 将y1,y2值代入式(12)及式(15)，看是否满足。 -5+1=-41 2+9=1113 全满足，可见Y是符合平衡定理的对偶解，因此， X=(0,2,3,0)T及Y=(-1,1)T分别是原问题及对偶问题

8、的最 优解。此时目标函数值CTX=YTb=16。,3 对偶性质及平衡定理 （10）,显然，一次成功是一咱巧合。最坏情况，本例需 次才能找到。 当维数增大，这种枚举法的计算量会呈现指数般急剧增长而 变为不现实。 以后将重点阐述有实用价值的单纯形法。,4 基础解及基础可行解 （1）,一、基础解定义 令X 满足，AX=b，若X 0，则X 必有非零分量x，x ， 于是必存的方程式： (1) 其中a，a，为与x，x ，对应的A阵列矢量，如果列矢 量a，a，之间线性独立，则称X为基础解。,4 基础解及基础可行解 （2）,线性独立的定义（或判断准则）为：若方程 中的矢量系数， ，必须全为零才能使方程满足，则

9、称 矢量a，a，之间线性独立。 即，任何一个矢量都不能由其它矢量的线性组合所构成的一 组矢量必线性独立。 例如： 中， ， ， 则知a1，a2，a3之间线性相关（即线性不独立），因为任何一 个矢量都可由其它两个矢量所组成。但是这三个矢量中，两 两之间线性无关（独立）。,4 基础解及基础可行解 （3）,若存在多个不同的非零基础解，则它们之间组合系数之和为1 的线性组合也必是方程解，即方程必存在无穷多个解。 二、基础可行解定义 满足等式约束AX=b及自变量限制X0的解称为可行解，既是可行解又是基础解解的解称为基础可行解。即基础解与可行解之交集称为基础可行解。 基础可行解是可行域的顶点，它是可行解的

10、一部分。基础可行解在线性规划的求解中具有特殊重要性，下面将阐述并证明关于它的重要定理。,4 基础解及基础可行解 （4）,三、定理 对于下述标准线性规划 1、如果存在可行解，则必存在基础可行解。 2、如果存在最优解，则必存在基础最优解。 定理1证明：设，规划已有一个可行解X，且具有正分量x， x ，（如果无正分量，则X本身即为落在原点的基础可行 解），如果正分量x，x ，对应的A阵列矢量a，a，线 性独立，则X即为基础可行解，如果不独立，则在下述方程：,4 基础解及基础可行解 （5）,中 (3) 至少有一项i0，不失一般性，令0且0（否则等式两 边乘以-1）。设 (4) 其中，x，x ，0 则用(4)式 (3)式得 (5),4 基础解及基础可行解 （6）,