对偶总结 max z=CX max zCX max zCX st.AX≤b s t. AXb st.AX≥b >0 X>0 X>0 min w=yb min w=yb min w=yb s.t.YA≥CT st.YA≥CT st.YA≥CT Y≥0 Y Free Y≤0 原问题约束条件的性质,影响对偶问题变量的性质。 原问题变量的性质,影响对偶问题约束条件的性质
对偶总结 原问题约束条件的性质，影响对偶问题变量的性质。 原问题变量的性质，影响对偶问题约束条件的性质。 min W=Yb s.t. YA CT Y ≤0 min w=Yb s.t. YA CT Y :Free ≤ min w=Yb s.t. Y A CT Y 0
写对偶问题的练习(1) min z= 2x +4x-x maxw=6y1+12y2+8y3+15y4 st.3x1-x2+2x3≥6 st.3y1y2+2y3+y42 x1+2x2-3x3=12 y1+2y2+y3+3y4>4 2x1+x2+2x3≤8 2y13y2+2yy4=-1 X1+3x2-X3≥15 y1≥0,y2 Free,y3≤0 0 ≥0X2<0x3:Free 口原始问题变量的个数(3)等于对偶问题约束条件的个数(3); 口原始问题约束条件的个数(4)等于对偶问题变量的个数(4)。 口原始问题变量的性质影响对偶问题约束条件的性质。 口原始问题约束条件的性质影响对偶问题变量的性质
min z= 2x1+4x2-x3 s.t. 3x1- x2+2x3 6 -x1+2x2-3x3 12 2x1+x2+2x3 8 x1+3x2-x3 15 max w=6y1+12y2+8y3+15y4 s.t. 3y1- y2+2y3+ y4 2 -y1+2y2+ y3+3y4 4 2y1- 3y2+2y3- y4 -1 y1 0,y2 ,y3 0,y4 0 ≤ ≥ = ≥ Free ≤ ≥ ≥ = ≤ ≥ x1≥0 x2≤0 x3: Free p原始问题变量的个数(3)等于对偶问题约束条件的个数(3)； p原始问题约束条件的个数(4)等于对偶问题变量的个数(4)。 p原始问题变量的性质影响对偶问题约束条件的性质。 p原始问题约束条件的性质影响对偶问题变量的性质。 写对偶问题的练习（1）
写对偶问题的练习(2) 原始问题 对偶问题 mnw=12y1+8y2+15y3 max z=2X1-X,+3X3-2X4 st.x1+3X2-2X3+X4≤12 st.y1-2y2+3y3≥2 -2x1+X 2 3Xa28 3y1+y2-4y3=-1 2 +5ya≤3 3x1-4X2+5X3-X4=15 x1≥0,x2: Free, x3≤0,x420 y1-3y2-y32-2 y120y2≤0,y3:Free
写对偶问题的练习（2） 原始问题 max z=2x1-x2+3x3-2x4 s.t. x1 +3x2 - 2x3 + x4≤12 -2x1 + x2 -3x4≥8 3x1 - 4x2 +5x3 - x4 = 15 x1≥0, x2:Free, x3≤0, x4≥0 minw=12y1+8y2+15y3 s.t. y1 – 2y2 + 3y3≥2 3y1 + y2 – 4y3=-1 -2y1 +5y3≤3 y1 – 3y2 - y3≥-2 y1≥0,y2≤0, y3:Free 对偶问题
对偶问题的性质总结 1、对称性:对偶的对偶就是原始问题 max zCX 对偶的定义 min w=yb st.AX≤b s.t.ATY≥CT X>0 Y>0 min z=-CX Maxw’=-Yb st.-AX≥-b s.t.-ATY≤CT X>0 对偶的定义 Y≥0
对偶问题的性质总结 1、对称性：对偶的对偶就是原始问题 对偶的定义 ≤ min W=Yb s.t. ATY CT Y≥0 对偶的定义 Maxw’= -Yb s.t. -ATY≤-CT Y ≥0
2、弱对偶性 若x是极大化问题的可行解,y是对偶问题 的可行解,则有 CXsYb。解释 推论:(1)无界性--若原问题无界,则对 偶问题无可行解 ·(2)极大化问题任一可行解的目标函数值 是其对偶问题目标函数值的下界,反之, 对偶问题任一可行解的目标函数值是原问 题目标函数值的上界。 (3)若原问题和对偶问题一个有可行解, 另一个无可行解,则可行的问题无界
2、弱对偶性 • 若x是极大化问题的可行解，y是对偶问题 的可行解，则有CX≤Yb。解释 • 推论：（1）无界性---若原问题无界，则对 偶问题无可行解 • （2）极大化问题任一可行解的目标函数值 是其对偶问题目标函数值的下界，反之， 对偶问题任一可行解的目标函数值是原问 题目标函数值的上界。 • （3）若原问题和对偶问题一个有可行解， 另一个无可行解，则可行的问题无界