解先将该问题化为规范形式例 写出下述规划的对偶问题max(-W)=-12yi -16y2 -15y3min W =12y +16y2 +15y3≤-2-2y -4y2s.t≥22y +4y2s.t-2y1-5y, ≤-32y1+5y, ≥3Ji,y2 >0Ji,y2 >0互为对偶于是对偶问题即为：也即为：min(-Z) =-2x -3x2max Z =2x +3x2[2x +2x2 ≤12[-2xi -2x, ≥-12≤164x1- 4x≥-165x2 ≤15-5x2 ≥-15[X,x ≥0Xi,X2 ≥0-对称性于是对偶问题的对偶是原问题2025/4/5
2025/4/5 12 例 写出下述规划的对偶问题 min 12 1 16 2 15 3 W = y + y + y s.t 2y1 + 4y2 2 , 0 2 5 3 1 2 1 3 + y y y y 于是对偶问题即为： 1 2 3 max( −W) = −12y −16y −15y . -2 -4 -2 st y1 y2 , 0 2 5 3 1 2 1 3 − − − y y y y , 0 -5 -15 - 4 -16 - 2 - 2 -12 1 2 2 1 1 2 x x x x x x 2 1 3 2 min(−Z) = − x − x 解 先将该问题化为规范形式 也即为： + , 0 5 15 4 16 2 2 12 1 2 2 1 1 2 x x x x x x max Z = 2x1 +3x2 于是对偶问题的对偶是原问题。-对称性
如何写出非规范的原问题相应的对偶问题目标函数MIN1.MAX≤约束条件≥2.3．约束条件=+?≤0或 无约束4.变量?例：P55例2，写出下面规划的对偶规划min z = 7x +4x2 -3x3[-4x + 2x2 -6x ≤24-3x -6x2 -4x, ≥155x2 +3x3 = 30xi≤0,x无约束，x,≥02025/4/513
2025/4/5 13 如何写出非规范的原问题相应的对偶问题： 1. 目标函数MIN MAX 2. 约束条件 3. 约束条件 = ? 4. 变量 ? 0 或 无约束 0 或 无约束 例：P55 例2，写出下面规划的对偶规划 + = − − − − + − = + − 0, 0 5 3 30 3 6 4 15 4 2 6 24 min 7 4 3 1 2 3 2 3 1 2 3 1 2 3 1 2 3 x x x x x x x x x x x z x x x 无约束
解：将原问题模型变形令x=-xmin z =-7x' +4x2 -3x3-4x' -2x2 +6x ≥-24y13x -6x2 - 4xg ≥15y25x, +3x, =30y3x≥0,x,无约束，x≥0max w =-24yi +15y2 +30y3则对偶问题是[- 4yi +3y2≤-7xi-2y1-6y2 +5y3 = 4X2X36y1-4y2 +3x, ≤-3[J1,2≥0,x无约束2025/4/5
2025/4/5 14 解：将原问题模型变形 + = − − − − + − = − + − 0, 0 5 3 30 3 6 4 15 4 2 6 24 min 7 4 3 1 2 3 2 3 1 2 3 1 2 3 1 2 3 x x x x x x x x x x x z x x x 无约束， 3 2 1 y y y 1 1 令x = −x 则对偶问题是 − + − − − + = − + − = − + + 1 2 3 无约束 1 2 3 1 2 3 1 2 1 2 3 , 0, 6 4 3 3 2 6 5 4 4 3 7 max 24 15 30 y y x y y x y y y y y w y y y 3 2 1 x x x
小结：对偶问题与原问题的关系：目标函数：MIN目标函数：MAX对m个变量变量：约束条件：m个约束原≤≥0偶问(2)问(≤ 0)题题=无约束变量：n个变量约束条件：n个约束≥≥0(≤)(<≤0)=无约束价值系数约束条件右端项价值系数约束条件右端项2025/4/515
2025/4/5 15 小结：对偶问题与原问题的关系： 原 问 题 对 偶 问 题 目标函数：MAX 约束条件：m个约束 变量 ： n个变量 目标函数：MIN = ( ) 无约束 ( 0) 0 约束条件：n个约束 变量 ： m个变量 无约束 ( 0) 0 = ( ) 约束条件右端项 价值系数 价值系数 约束条件右端项
83 对偶问题的基本性质就上节所讨论的一般的线性规划问题及其对偶问题，有如下的性质：1、弱对偶性Ji, i=l...,m, j=l...n 分如果xj，别是原问题和对偶问题的可行解，则恒有Zex,≤Zby,i=1=≤a,y,及Za,xj ≤b, 代入。考虑利用 C,i-12、无界性如果原问题（对偶问题）有无界解，则其对偶问题（原问题）无可行解。2025/4/516
2025/4/5 16 §3 对偶问题的基本性质 就上节所讨论的一般的线性规划问题及其对偶问题，有如下的性质： 1、弱对偶性 如果 分 别是原问题和对偶问题的可行解，则恒有 考虑利用 及 代入。 = = m i i i n j j j c x b y 1 1 x j , y i m j n i , =1,., , =1,. 2、无界性 如果原问题（对偶问题）有无界解，则其对偶问题 （原问题）无可行解。 = m i j ij i c a y 1 i n j j aij x b =1