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

1、1 初步分析线性规划解的几种可能性 2 线性规划解的求解方法之一：图解法 3 对偶性质及平衡定理 4 基础解及基础可行解 已知线性规划的标准形式为AX=b, XO, CTX=min满足前2条的解为可行解，同时又满足第3条的为最优解。从解的性质看，线性规划有下述几种可能：1不存在可行解或无解，例如规划x1= x1 0 无可行解3 x1=min 2存在可行解，但找不到最优解，例如规划x1x2=0 x1，x202 x1=min 显然，令x1=x2=,为任意非负值都是可行解， 当+，则目标函数2 x1，故找不出使目标函数 取极小值的具体解X。 100121及xxXx2101 x1图 1-13存在最优解

2、，但不是唯一的。例如规划x1+x2=1x1，x2ox1+ x2=min 显然 两点连线上的所有点 都是最优解，（见图1-1）4一般情况有无穷多可行解，但有唯一最优解。 A0423214x131x2B2x1+x2=4L1L3L2图 1-2例1-3 求解下述线性规划2x1+x2x3=4(1)xj0 j=1,2,3(2)3x1+5x2=min(3)将(1)式中的x3移至右边，常数4移至左边，得： 2x1+x24=x30 移项得：2x1+x24于是变为两维线性规划问题，其约束可行域可用直角坐标系表示,如图1-2。 图1-2中，阴影部分为可行域，若要求出最优点，必须作出目标函数的等值线，然后令等值线向最

3、小值方向（即最优方向）移动，直到离开可行域的瞬间为止，此时的交点即为最优点。图中直线L1，L2，L3即为目标值分别为12，9及6的等值线，L3与可行域的顶点B（x12，x20），L3再向左下方移动，必离开可行域，于是该点即为线性规划之最优解，即：X （x1，x2，x3）=(2,0,0)，目标值为3x1+5x26。图解法简单易行，但只适于两维问题（本题虽是三维，但很容易变为两维）。对于高维问题，只能采用其它的办法求解。很幸运，该法已经找到，这就是以后将要介绍的单纯形法。 1弱对偶性（不等式性质）设原线性规划为AX=b，X0，CTX=min其对偶规划为YTACT, YT b=max若X、Y分别是原

4、问题和对偶问题的可行解，则必存在关系式CTXYTb 证明：因为X、Y分别是原问题及对偶问题的可行解，因此YTAX=YT(AX)=YTb及 YTAX =(YTA)XCTX故 CTXYTbo这是一个很有用的性质，因为有时并不需要精确求出线性规划问题最优解，只需了解最优目标值的范围，那么采用求解对偶可行解就显得十分方便。 2强对偶性（对偶最优性） 若 分别是原问题与对偶问题可行解，且 ，则 必分别是原问题及对偶问题的最优解。证明：设X是原向题任一可行解，则从弱对偶性知， ，可见 是原问题最优解。同理，设Y是对偶问题任一可行解，则 ，故 是对偶问题最优解。 YX，bYXCTTYX，XCbYXCTTTX

5、bYXCbYTTTY1平衡定理设原问题为 (4) xj0 (j=1,2,，n) (5)(6)其对偶形式为 (7)(8) njjijbxa1.m),21,(i njjjxc1minmijijicay1n),1,2,(j max1miiiby则平衡定理阐述如下：若xj(j=1,2，n)和yi（i=1,2,，m）分别是原问题和对偶问题之可行解，必存在下述关系：（即弱对偶性） 上式中两边相等的充分必要条件是： 或 xj=0 或 xj0,但 njjjmiiixcby11 mijijicay1 证明：根据(5)式和(7)式可得：(9) njmiijiiayx11j 0 cnjjjmjiimiiinjjjn

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

7、约束条件为等式，则此时的解必为最优解。例1-4 应用平衡定理解下述规划 min13250 (11) 1696(10) 024x 6x5432143214321xxxxXxxxxxx其对偶形式为 首先令原问题中任两个变量为0（因有2个约束条件，这样可求出唯一解），试探求出一组原问题可行解。例如，令x1=x4=0，则得： max16 (15) 1392y-(14) 26y4(13) 56(12) 15 2212 12121yyyyyyy32x 166046x-323232xxxx故此时X=(0,2,3,0)T是原问题可行解。 为检验是否为最优解，令非零xj对应的对偶约束为等式，求平衡解Y。即令将y

8、1,y2值代入式(12)及式(15)，看是否满足。-5+1=-412+9=1113全满足，可见Y是符合平衡定理的对偶解，因此，X=(0,2,3,0)T及Y=(-1,1)T分别是原问题及对偶问题的最优解。此时目标函数值CTX=YTb=16。 11y 26456y-212122yyyy显然，一次成功是一咱巧合。最坏情况，本例需次才能找到。当维数增大，这种枚举法的计算量会呈现指数般急剧增长而变为不现实。以后将重点阐述有实用价值的单纯形法。 6234!24! 2! 4C24一、基础解定义 令X 满足，AX=b，若X 0，则X 必有非零分量x，x ，于是必存的方程式： (1)其中a，a，为与x，x ，对

9、应的A阵列矢量，如果列矢量a，a，之间线性独立，则称X为基础解。 baxaxAX 线性独立的定义（或判断准则）为：若方程中的矢量系数， ，必须全为零才能使方程满足，则称矢量a，a，之间线性独立。即，任何一个矢量都不能由其它矢量的线性组合所构成的一组矢量必线性独立。例如： 中， ， ，则知a1，a2，a3之间线性相关（即线性不独立），因为任何一个矢量都可由其它两个矢量所组成。但是这三个矢量中，两两之间线性无关（独立）。 0aa3- 2 1-1- 1- 1A111a212a313a 若存在多个不同的非零基础解，则它们之间组合系数之和为1的线性组合也必是方程解，即方程必存在无穷多个解。二、基础可行解

10、定义 o满足等式约束AX=b及自变量限制X0的解称为可行解，既是可行解又是基础解解的解称为基础可行解。即基础解与可行解之交集称为基础可行解。o基础可行解是可行域的顶点，它是可行解的一部分。基础可行解在线性规划的求解中具有特殊重要性，下面将阐述并证明关于它的重要定理。 三、定理对于下述标准线性规划 1、如果存在可行解，则必存在基础可行解。2、如果存在最优解，则必存在基础最优解。定理1证明：设，规划已有一个可行解X，且具有正分量x，x ，（如果无正分量，则X本身即为落在原点的基础可行解），如果正分量x，x ，对应的A阵列矢量a，a，线性独立，则X即为基础可行解，如果不独立，则在下述方程：min, 0,XCXbAXT 中 (3)至少有一项i0，不失一般性，令0且0（否则等式两边乘以-1）。设 (4)其中，x，x ，0则用(4)式 (3)式得(5)0aabaxaxAXbaxaxaa 如果，足够小，则仍可使（