对称的原始问题和对偶问题 原问题为 max z=6X1+9x2 原问题是极大化问题 st.x1+2X2≤2 原问题的约束全为≤ 2X13X2≤3 原问题有2个变量,3个约束 x1+2x2≤-1 原问题的变量全部为非负 x1x2≥0 对偶问题为 对偶问题是极小化问题 min w=2y1+ 3y2-y3 对偶问题的约束全为≥ st.y1+2y2+y326 对偶问题有3个变量,2个约束 2y1-3y2+2y3≥9 对偶问题的变量全部为非负 yi y2r y320 原问题变量的个数(2)等于对偶问题约束条件的个数(2) 原问题约束条件的个数(3)等于对偶问题变量的个数(3)
对称的原始问题和对偶问题 对偶问题为 min w=2y1+3y2-y3 s.t. y1+2y2+y3≥6 2y1-3y2+2y3≥9 y1, y2, y3≥0 原问题为 max z=6x1+9x2 s.t. x1+2x2≤2 2x1- 3x2≤3 x1+2x2≤-1 x1, x2≥0 原问题是极大化问题 原问题的约束全为≤ 原问题有2个变量，3个约束 原问题的变量全部为非负 对偶问题是极小化问题 对偶问题的约束全为≥ 对偶问题有3个变量，2个约束 对偶问题的变量全部为非负 原问题变量的个数(2)等于对偶问题约束条件的个数(2) 原问题约束条件的个数(3)等于对偶问题变量的个数(3)
根据定义写出对偶问题的练习 max z=2x,+x, sx st.x13X2+2x35X4≤6 4x1+x2-5X3+2X4≤9 x1+2X2+x4≤12 yyy 123 x1rX2nx34≥0 原问题有4个变量,3个约束,对偶问题应该有3个变量,4 个约束。根据定义,对偶问题为: min w=6y1+9y2+12y3 st.y1+42-y322 3y1+y2+2y321 y15y22-3 xxxx 5y1+2y2+y320 234 y1y2y320
根据定义写出对偶问题的练习 max z=2x1+x2-3x3 s.t. x1-3x2+2x3- 5x4 ≤ 6 4x1+x2- 5x3+2x4 ≤ 9 -x1+2x2 +x4 ≤ 12 x1, x2, x3, x4 ≥0 原问题有4个变量，3个约束，对偶问题应该有3个变量，4 个约束。根据定义，对偶问题为： y1 y2 y3 min w=6y1+9y2+12y3 s.t. y1+4y2- y3 ≥2 -3y1+ y2+2y3 ≥ 1 2y1-5y2 ≥ -3 -5y1+2y2+ y3 ≥ 0 y1, y2, y3 ≥0 x1 x2 x3 x4
对偶问题的对偶 maxw=-8y4-16y2-12y mnw=8y1+16y2+12y3写成原问st.y4yzs2 题的形式 y1+4y2≥2 y14y3≤-3 y1+4y323 yyzy3≥0 y1,y2,y3≥0 根据定义写出对偶问题 max z=2X1+ 3X2 st.x1+X2≤8 min z=-2X1-3X2 4x1≤16 st.-x1-X≥-8 变形 4x≤12 -4x12-16 x1X20 -4x2≥-12 X1X2≥0 结论:对偶问题的对偶就是原始问题。两个问题中的任 个都可以作为原始问题。另一个就是它的对偶问题
对偶问题的对偶 minw=8y1+16y2+12y3 y1+4y2 ≥2 y1+ 4y3≥3 y1，y2，y3 ≥0 max w’=-8y1 -16y2 -12y3 s.t. -y1 -4y2 ≤ -2 -y1 - 4y3 ≤ -3 y1, y2,y3 ≥0 min z’=-2x1-3x2 s.t. –x1-x2 ≥ -8 -4x1 ≥ -16 -4x2 ≥ -12 x1, x2, ≥0 max z=2x1+3x2 s.t. x1+x2 ≤ 8 4x1 ≤ 16 4x2 ≤12 x1, x2≥0 结论：对偶问题的对偶就是原始问题。两个问题中的任一 个都可以作为原始问题。另一个就是它的对偶问题。 写成原问 题的形式 根据定义写出对偶问题 变形
其他形式的对偶一极大化问题有“2"约束 max z=2X+3x2-X3 max z=2X1+ 3x2-X3 2xy-Xx≤-6 st.x1+2x2+x326 st 2x1-3X2+2X2s9 2X1-3X2+2X39 X1 X, x220 x1x2,x3≥0 min w=6y1+9y2 min w=-6y1+9y2 s.t. y1+2y222 Y1=-y'1y150 s.t. -y1+2y222 2y1-3y223 2y1-3y23 y1+2y2-1 y1+2y22-1 y1≤0,y2≥0 yry2≥0 如果极大化原始问题中一个约束是“≥"约束,则对偶问 题中相应的变量≤0
其他形式的对偶—极大化问题有“≥ ”约束 max z=2x1+3x2-x3 s.t. x1+2x2+x3 ≥ 6 2x1-3x2+2x3≤9 x1, x2, x3≥0 max z=2x1+3x2-x3 s.t. -x1-2x2-x3≤-6 2x1-3x2+2x3≤9 x1, x2, x3≥0 min w=-6y1 ’+9y2 s.t. -y’ 1+2y2 ≥ 2 -2y’ 1 -3y2 ≥ 3 -y’ 1+2y2 ≥ -1 y’ 1, y2≥0 min w=6y1+9y2 s.t. y1+2y2 ≥ 2 2y1- 3y2 ≥ 3 y1+2y2 ≥ -1 y1≤0, y2≥0 y1=-y’ 1, y1≤0 如果极大化原始问题中一个约束是“≥”约束，则对偶问 题中相应的变量≤0
其他形式的对偶一原始问题有“=“约束 min z=2X,1+3x2X3min z=2X1+3X2-X3 min z=2X1+3X2-X3 st.x1+2x2+x3=6 st.x1+2X2+x2≥6 st.x1+2x2+x226 x1+2x2+x3≤6 2X1-3X2+2X3≥9 x12x2x32-6 2x13X2+2x2≥9 2x1-3x2+2X3≥9 x1X,x2≥0 x1X2x320 Xx,x20 y1=y1y1∠:Free max y=6 1+9y2 maxw=6(v1 -)+9y2 maxw=6y1'-6y1+9y2 st.y1+2y2≤2 st.(y1y1)+2y2≤2 st.y1-y1+2y2≤2 2y1-3y2≤3 2(y1y1)-3y2≤3 2y1-2y13y2≤3 W1+2y2≤-1 (y1y"1)+2y2≤-1 y1y1+2y2≤-1 yi: Free y220 y'ly1y220 y'ly1y220 如果原始问题中一个约束是等号约束,则对偶问题中相应的变 量没有符号限制
min z=2x1+3x2-x3 s.t. x1+2x2+x3=6 2x1-3x2+2x3≥9 x1, x2, x3≥0 min z=2x1+3x2-x3 s.t. x1+2x2+x3≥6 x1+2x2+x3≤6 2x1-3x2+2x3≥9 x1, x2, x3≥0 min z=2x1+3x2-x3 s.t. x1+2x2+x3≥6 -x1- 2x2- x3≥-6 2x1-3x2+2x3≥9 x1, x2, x3≥0 maxw=6y1 ’-6y1 ’’+9y2 s.t. y’ 1-y’’ 1+2y2≤2 2y’ 1-2y’’ 1-3y2≤3 y’ 1-y’’ 1+2y2≤-1 y’ 1, y’’ 1, y2≥0 max w=6(y1 ’-y1 ’’)+9y2 s.t. (y’ 1-y’’ 1)+2y2≤2 2(y’ 1-y’’ 1)-3y2≤3 (y’ 1-y’’ 1)+2y2≤-1 y’ 1, y’’ 1, y2≥0 max y=6y1+9y2 s.t. y1+2y2≤2 2y1- 3y2≤3 w1+2y2≤-1 y1:Free y2≥0 y1=y’ 1-y’’ 1 , y1:Free 如果原始问题中一个约束是等号约束，则对偶问题中相应的变 量没有符号限制 其他形式的对偶—原始问题有“=”约束