《运筹学》课程教学资源（试卷习题）第3章 线性规划的对偶理论

推论2若规划（P）有可行解，则（P）有最优解的充分必要条件是规划（D）有可行解。推论3若规划（D）有可行解，则（D）有最优解的充分必要条件是规划（P）有可行解

推论2 若规划（P）有可行解，则（P）有 最优解的充分必要条件是规划（D）有可行 解。 推论3 若规划（D）有可行解，则（D）有 最优解的充分必要条件是规划（P）有可行 解

例3.4试用对偶理论判断下面线性规划是否有最优解Z = Xi +x2max一Xi +X2 +X3 ≤2-2x +X2-X ≤1Xi,X2,X3 ≥ 0解:此规划存在可行解 X=(0,0,0)，其对偶规划为

例3.4 试用对偶理论判断下面线性规划是否 有最优解       − + −  − + +  = + , , 0 2 1 2 max 1 2 3 1 2 3 1 2 3 1 2 x x x x x x x x x Z x x 解:此规划存在可行解 ，其对 偶规划为 ( ) T X = 0,0,0

min f = 2yi + 2— Vi —22 ≥ 1i+ Y2 ≥2Ji— J2≥0V1J2 ≥ 0显然，对偶规划没有可行解，因此，原规划没有最优解

        −  +  − −  = + , 0 0 2 2 1 min 2 1 2 1 2 1 2 1 2 1 2 y y y y y y y y f y y 显然，对偶规划没有可行解，因此，原规划 没有最优解

例3.5用对偶理论判断下面线性规划是否存在最优解Z = 3x1 + 2x2nmax-xi +2x2 ≤ 4<143x1 + 2x25Λ3X1X20Xi_x2 ≥解：此规划存在可行解，其对偶规划为

例3.5 用对偶理论判断下面线性规划是否存 在最优解         −  +  − +  = + , 0 3 3 2 14 2 4 max 3 2 1 2 1 2 1 2 1 2 1 2 x x x x x x x x Z x x 解:此规划存在可行解，其对偶规划为

min f = 4yi +14y2 +3y3Ji +3y2 +3 ≥32Ji +2y2 -Y3 ≥ 2Y1,Y2,Y3 ≥ 0对偶规划也存在可行解=(O,1,0)因此原规划存在最优解

      + −  − + +  = + + , , 0 2 2 2 3 3 min 4 14 3 1 2 3 1 2 3 1 2 3 1 2 3 y y y y y y y y y f y y y 对偶规划也存在可行解 ( ) T Y = 0,1,0 因此原规划存在最优解