运筹学三线性规划的对偶原理.ppt

第三章 线性规划的对偶原理 单纯形法的矩阵描述 A为m×n阶矩阵 RankA=m,取B为可行基,N为非基， 求解步骤： 现在不再生产，将设备材料出租出让，确定租费及转让费？ 设y1为设备单位台时的租金，y2,y3为材料A、B转让附加费(kg-1) 目标函数，约束条件？ 一般的，原问题：max z = CX AX ≤ b X ≥ 0 二、 对偶问题的化法 1、典型情况（对称形式） [例2]max z = x1 + 2x2 + x3 2x1 + x2 ≤ 6 2x2 + x3 ≤ 8 x1,x2,x3 ≥ 0 2、含等式的情况 [例3]max z = x1 + 2x2 + 4x3 2x1 + x2 + 3x3 = 3 x1 + 2x2 + 5x3 ≤ 4 x1,x2,x3 ≥ 0 3、含“≥”的max问题 [例4]max z = x1 + 2x2 + 4x3 2x1 + x2 + 3x3 ≥ 3 x1 + 2x2 + 5x3 ≤ 4 x1,x2,x3 ≥ 0 例5 min z = 2x1 + 3x2 - 5x3 + x4 x1 + x2 - 3x3 + x4 ≥ 5 2x1 + 2x3 - x4 ≤ 4 x2 + x3 + x4 = 6 x1 ≤ 0,x2,x3 ≥ 0,x4自由变量 §2 对偶问题的基本性质和基本定理 对偶问题中，解的情况有： 1.都有有限最优解 2.都无可行解 3.一个有无界解，另一个无可行解 7、检验数与解的关系 原问题附加变量最优检验数的值为对偶问题的最优解。 求对偶问题的最优解: 1.单纯形乘子Y的定理 2.松弛性 3.检验数与解的关系 [例6]已知：min w = 20y1 + 20y2 的最优解为y1*=1.2,y2*=0.2 -ys1 y1 + 2y2 ≥ 1 ① 试用松弛性求对偶 -ys2 2y1 + y2 ≥ 2 ② 问题的最优解。 -ys3 2y1 + 3y2 ≥ 3 ③ -ys4 3y1 + 2y2 ≥ 4 ④ y1,y2 ≥ 0 ∵y1*=1.2,y2*＝0.2 0 ∴xs1* = xs2* = 0 由① y1* + 2y2* = 1.6 1 ∴ys1* 0 ∴x1* = 0 由② 2y1* + y2* = 2.6 2 ∴ys2* 0 ∴x2* = 0 由③ 2y1* + 3y2* = 3 =右边 ∴ys3* = 0 ∴x3*待定 由④ 3y1* + 2y2* = 4 =右边 ∴ys4* = 0 ∴x4*待定 8、对偶问题的经济含义——影子价格 最优情况：z* = w* = b1y1* + ··· + biyi* + ··· + bmym* §3 对偶单纯形法 单纯形法：由 XB = B-1b ≥ 0，使σj ≥ 0，j = 1,···,m 对偶单纯形法：由σj ≥ 0(j= 1,···,n)，使XB = B-1b ≥ 0 相同点：都用于求解原问题 对偶单纯形法：从一个原始不可行而对偶可行的基出发，进行基变换，每次基变换时都保持基的对偶可行性，一旦获得一个原始可行基，则该基必定是最优基。 [例8]用对偶单纯形法求解 min w = 2x1 + 3x2 + 4x3 x1 + 2x2 + x3 ≥ 1 2x1 - x2 + 3x3 ≥ 4 x1,x2,x3 ≥ 0 min w = 2x1 + 3x2 + 4x3 + 0x4 + 0x5 - x1 - 2x2 - x3 + x4 ＝ - 1 - 2x1 + x2 - 3x3 + x5 ＝ - 4 x1,x2,x3,x4,x5 ≥ 0