聊回 原问题(或对偶问题)对偶问题(或原问题) 目标函数maxz 目标函数mnw n个约束 n个变量 约束≤maxz)变量≥0 约束≥ 变量≤0 上页 约束= 自由变量 m个变 m个约束 下页 变量20mm 约束≥ 变量≤0 约束≤ 回 自由变量 约束= 目标函数的价值向量约束条件的限定向量 约束条件的限定向量目标函数的价值向量
返回 上页 下页 对 偶 问 题 三、原问题与对偶问题的对应关系 约束条件的限定向量 目标函数的价值向量 自由变量 变量 变量 个变量 约束 约束 约束 个约束 目标函数 0 0 max = m n z 原问题（或对偶问题） 对偶问题（或原问题） 目标函数的价值向量 约束条件的限定向量 约束 约束 约束 个约束 自由变量 变量 变量 个变量 目标函数 0 0 min = m n w max z min z
例 maXz=5x1+3x2+2x3+4x4 5x1+x2+x3+8x4<8 上页 st2x+4x2+3x3+2x4=10 下页 ,x2≥ 0x3,x4无约欢 回
返回 上页 下页 对 偶 问 题 ◼ 例: + + + = + + + = + + + x ,x x ,x 无约束 x x x x x x x x s.t z x x x x 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 0 2 4 3 2 10 5 8 8 max 5 3 2 4
对偶问题为 min w=8y1+10y2 5y1+2y2≥0 y1+4y2≥3 上页 st1y1+3y2=2 下页 y1+2 8 2 2=4 回 y1≥0,y2无约東
返回 上页 下页 对 偶 问 题 对偶问题为 + = + = + + 1 0, 2 无约束 8 2 4 3 2 4 3 5 2 0 1 2 1 2 1 2 1 2 y y y y y y y y y y s.t. min 8 1 10 2 w = y + y
3.12对偶问题的基本性质 引例 对称性 弱对偶性 最优性 返回 对偶性(强对偶性) 互补松弛性
返回 继续 3.1.2 对偶问题的基本性质 ◼引例 ◼对称性 ◼弱对偶性 ◼最优性 ◼对偶性（强对偶性） ◼互补松弛性
max z=2x1+x2 原S.t. 5x2≤15 问6x1+2x2≤24 题 x1+x2≤5 X1x2>0 上页 minw=15y1+24y2+5y对 下页 st y2+y≥2偶 6 回 5y+2y2+y2≥ 题 收 购 y,y2,y3≥0 烈
返回 上页 下页对偶问题 , 0 5 6 2 24 5 15 max 21 2 1 2 1 2 2 1 2 + + = + x x x x x x s.t. x z x x y , , 0 5 2 1 . 6 2 1 2 3 1 2 3 2 3 + + + y y y y y s t y y min 15 1 24 2 5 3 w = y + y + y 对偶问题 原问题收购 厂家 ◼引例