运筹学2 对偶问题课件.pptVIP

得Δc3≥－2，同理，用此方法可求出c2和c1的变化区间。 ，要使 、 同时小于等于零，解不等式组 2.4.2 资源限量bi变化分析 为了使最优基B不变，求bi的变化范围。 设br的增量为Δbr，b的增量为 原线性规划的最优解为X，基变量为XB=B－1b，要使最优基B不变，即要求， 显然有 Y°XS=－YS X° 又因为Y°、Xs、Ys、X°≥0，所以有 Y°XS=0和YS X°=0 成立。 反之， 当Y°XS=0和YS X°=0时，有 Y°A X°＝Y°b Y°A X°=C X° 显然有Y°b=C X°,由性质3知Y°与X°是（LP）与（DP）的最优解。证毕。 性质5告诉我们已知一个问题的最优解时求另一个问题的最优解的方法，即已知Y°求X°或已知X°求Y°。 Y°XS=0和YS X°=0 两式称为互补松弛条件。将互补松弛条件写成下式 由于变量都非负，要使求和式等于零，则必定每一分量为零，因而有下列关系： （1）当yi°0时， ，反之当 时yi°=0； 注意：对于非对称形式，性质5的结论仍然有效。 【例2.6】 已知线性规划 的最优解是 ，求对偶问题的最优解。 的最优解是 ， 求对偶问题的最优解。 【解】对偶问题是 因为X1≠0，X2≠0，所以对偶问题的第一、二个约束的松弛变量等于零，即 解此线性方程组得y1=1,y2=1,从而对偶问题的最优解为Y=（1，1），最优值w=26。 【例2.7】 已知线性规划 的对偶问题的最优解为Y=（0, -2），求原问题的最优解。 【解】对偶问题是 由y2≠0得 =0，由 得x2=0，原问题的约束条件变为: 解此方程组得原问题最优解： X=(-5, 0, -1)T，minZ = -12。 【例2.8】 证明下列线性规划无最优解： 【证】容易看出X=（4，0，0） 是一可行解，故问题可行。对偶问题 将三个约束的两端分别相加得 ， 而第二个约束有y2≥1，矛盾，故对偶问题无可行解， 因而原问题为无界解，即无最优解。 【性质6】 （LP）的检验数的相反数对应于（DP）的一组基本解. 其中第j个决策变量xj的检验数的相反数对应于（DP）中第j个松弛变量 的解，第i个松弛变量 的检验数的相反数对应于第i个对偶变量yi的解。反之，（DP）的检验数（注意：不乘负号）对应于（LP）的一组基本解。 证明略。 【例2.9】 线性规划 （1）用单纯形法求最优解； （2）写出每步迭代对应对偶问题的基本解； （3）从最优表中写出对偶问题的最优解； （4）用公式Y=CBB-1求对偶问题的最优解。 【解】（1）加入松弛变量x4、x5后，单纯形迭代如表2－2所示。 表2－2 XB x1 x2 x3 x4 x5 b (1) x4 x5 2* 1 -1 0 2 4 1 0 0 1 2→ 4 λj 6↑ -2 1 0 0 ? (2) x1 x5 1 0 -1/2 1/2* 1 3 1/2 -1/2 0 1 1 3→ λj 0 1↑ -5 -3 0 ? (3) x1 x2 1 0 0 1 4 6 0 -1 1 2 4 6 λj 0 0 -11 -2 -2 ? 最优解X=（4，6，0），最优值Z=6×4－2×6=12； （2）设对偶变量为y1、y2,松弛变量为y3、y4、y5,Y=（y1、y2、 y3、y4、y5），由性质6得到对偶问题的基本解 （y1、y2、 y3、y4、y5） =（－λ4，－λ5，－λ1，－λ2，－λ3），即 表2－2（1）中λ=（6，－2，1，0，0）， 则Y（1）=（0，0，-6，2，－1） 表2－2（2）中λ=（0，1，－5，－3，0）， 则Y（2）=（3，0，0，－1，5） 表2－2（3）中λ=（0，0，－11，－2，－2）， 则Y（3）=（2，2，0，0，11） （1）因为表2－2（3）为最优解，故 Y（3）=（2，2，0，0，11）为对偶问题最优解； （1）表2－2（3）中的最优