安徽大学：《运筹学》课程习题详解（PPT讲稿）第二章 线性规划的对偶理论

运筹学教程 第二章习题解答 2.1写出下列线性规划问题的对偶问题。 min Z 2x+2x2 +4x3 x1+3x2+4x3≥2 (1) 2x1+x2+3x3≤3 st x1+4x2+3x3=5 x1,x2,≥0，x3无约束 max W =2y +3y2+5y3 4+2y2+y3≤2 对偶问题： J3y+y2+4y≤2 st 4y+3y2+3y3=4 y≥0，y2≤0，y3无限制 page 2 23 April 2025 School of Management

运筹学教程 School of Management page 2 23 April 2025 第二章习题解答 2.1 写出下列线性规划问题的对偶问题。         + + = + +  + +  = + + 1 2 3无约束 1 2 3 1 2 3 1 2 3 1 2 3 , , 0, 4 3 5 2 3 3 3 4 2 min 2 2 4 (1) x x x x x x x x x x x x st Z x x x          + + = + +  + +  = + + 无限制 对偶问题 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 0, 0, 4 3 3 4 3 4 2 2 2 max 2 3 5 : y y y y y y y y y y y y st W y y y

运筹学教程 第二章习题解答 max Z=5x+6x2 +3x3 x1+2x2+2x3=5 (2) -x1+5x2-3x3≥3 st 4x1+7x2+3x3≤8 x无约束，x2,之0，x3≤0 max W=5y +3y2+8y3 y-y2+4y3=5 对偶问题： 2y+52+7y3≥6 st 2y1-3y2+3y3≤3 y无约束，y2≤0,3≥0 page 3 23 April 2025 School of Management

运筹学教程 School of Management page 3 23 April 2025 第二章习题解答          + +  − + −  + + = = + + , , 0, 0 4 7 3 8 5 3 3 2 2 5 max 5 6 3 (2) 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 x x x x x x x x x x x x st Z x x x 无约束          − +  + +  − + = = + + , 0, 0 2 3 3 3 2 5 7 6 4 5 max 5 3 8 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 y y y y y y y y y y y y st W y y y 无约束 对偶问题：

运筹学教程 第二章习题解答 m mim=∑∑cgx, i=1j=1 x=a,(i=1.,m) (3) st (j=1,.,n) i=1 ≥0 (i=1,.,m,j=1,.,n） maxW=∑a,y+∑b,y,+m i三1 对偶问题： j=1 y+yj+m≤C(i=1,.,mj=1,.,m) st. y,无限制，i=1,.,n+m page 4 23 April 2025 School of Management

运筹学教程 School of Management page 4 23 April 2025 . 0 ( 1, , , 1, , ) ( 1, , ) ( 1, , ) min (3) 1 1 1 1           = = = = = = =    = = = = x i m j n x b j n x a i m st Z c x i j n i i j j n j i j i m i n j i j i j     第二章习题解答    = + +  = = = + + = =   + y i n m y y c i m j n st W a y b y i i j m i j m i n j i i j j m 1, , ( 1, , , 1, , ) . max 1 1    无限制， 对偶问题：

运筹学教程 第二章习题解答 Z=∑cx j=1 ,ax,≤b,(i=1,.,m<m) (4) j= st ∑ax,=6(=m+1m+2,.,m) x,≥0 (=1,.,n,<n),x,无约束(=h1+1,.,n) page 5 23 April 2025 School of Management

运筹学教程 School of Management page 5 23 April 2025           =  = + = = + +  =  =    = = = x j n n x 无约束（j n n） a x b i m m m a x b i m m st Z c x j j n j i j j i n j i j j i m j j j 0 ( 1, , , ), 1, , ( 1, 2, , ) ( 1, , ) max (4) 1 1 1 1 1 1 1 1     第二章习题解答

运筹学教程 第二章习题解答 min w=by +b2y2+.+omym 2ay≥c,(=1,2,n) i=1 对偶问题： st3 ∑ayy=C,(j=n+1,n+2,.,m） i y,≥0(i=1.,m) y,无约束(=m,+1,.,m) page 6 23 April 2025 School of Management

运筹学教程 School of Management page 6 23 April 2025          = +  = = = + +  = = + + +   = = 无约束（ ） 对偶问题： y j m m y i m a y c j n n n a y c j n st W b y b y b y i i m i i j i j m i i j i j m m 1, , 0 ( 1, , ) ( 1, 2, , ) ( 1,2, , ) min 1 1 1 1 1 1 1 1 1 2 2      第二章习题解答

运筹学教程 第二章习题解答 2.2判断下列说法是否正确，为什么？ (1)如果线性规划的原问题存在可行解，」 则其对偶 问题也一定存在可行解； 答：不对！如原问题是无界解，对偶问题无可行 解。 (②)如果线性规划的对偶问题无可行解，则原问题 也一定无可行解； 答：不对！道理同上。 page 7 23 April 2025 School of Management

运筹学教程 School of Management page 7 23 April 2025 2.2 判断下列说法是否正确，为什么? (1)如果线性规划的原问题存在可行解，则其对偶 问题也一定存在可行解； 答：不对！如原问题是无界解，对偶问题无可行 解。 (2)如果线性规划的对偶问题无可行解，则原问题 也一定无可行解； 答：不对！道理同上。 第二章习题解答

运筹学教程 第二章习题解答 (3)在互为对偶的一对原问题与对偶问题中，不管 原问题是求极大或极小，原问题可行解的目标函数值 一定不超过其对偶问题可行解的目标函数值； 答：不对！如果原问题是求极小，结论相反。 (4)任何线性规划问题具有惟一的对偶问题。 答：结论正确！ page 8 23 April 2025 School of Management

运筹学教程 School of Management page 8 23 April 2025 (3)在互为对偶的一对原问题与对偶问题中，不管 原问题是求极大或极小，原问题可行解的目标函数值 一定不超过其对偶问题可行解的目标函数值； 答：不对！如果原问题是求极小，结论相反。 (4)任何线性规划问题具有惟一的对偶问题。 答：结论正确！ 第二章习题解答

运筹学教程 第二章习题解答 2.3已知某求极大化线性规划问题用单纯形 法求解时的初始单纯形表及最终单纯形表如下表 所示，求表中各括弧内未知数的值。 解： 1=1,k=0,h=-1/2,a=2, c=3,b=10,e=5/4,f=-1/2, d=1/4,g=-3/4,i=-1/4,j=-1/4 page 9 23 April 2025 School of Management

运筹学教程 School of Management page 9 23 April 2025 第二章习题解答 2.3 已知某求极大化线性规划问题用单纯形 法求解时的初始单纯形表及最终单纯形表如下表 所示，求表中各括弧内未知数的值。 解： l=1, k=0 , h=-1/2, a=2, c=3, b=10, e=5/4, f=-1/2, d=1/4, g=-3/4, i=-1/4, j=-1/4

运筹学教程 C 32 20 0 0 b X1X2 X3X4XX。 0 X (b) 1 1 1 0 0 X2 15 (a) 1 2 0 X3 20 2 (c) 1 0 C-Z 32 2 0 0 0 ! 0 X45/4 0 0 (d)(-1/4-1/4 3 X1 25/4 1 0 (e) 0 3/4 () 2 X, 5/2 0 (f) 0 (h) 1/2 C-Z 0 (k) (g) 0-5/4 page 10 23 April 2025 School of Management

运筹学教程 School of Management page 10 23 April 2025 Cj → 3 2 2 0 0 0 CB 基 b X1 X2 X3 X4 X5 X6 0 X1 (b) 1 1 1 1 0 0 0 X2 15 (a) 1 2 0 1 0 0 X3 20 2 (c) 1 0 0 1 Cj－Zj 3 2 2 0 0 0 ┆ ┆ ┆ ┆ ┆ ┆ ┆ ┆ ┆ 0 X4 5/4 0 0 (d) (l) -1/4 -1/4 3 X1 25/4 1 0 (e) 0 3/4 (i) 2 X2 5/2 0 1 (f) 0 (h) 1/2 Cj－Zj 0 (k) (g) 0 -5/4 (j)

运筹学教程 第二章习题解答 2.4给出线性规划问题 minZ=2x1+3x2+5x3+6x4 X1+2x2+3x3+x4≥2 t.-2x1+x2-X3+3x4≤-3 x,≥0，(j=1,.,4) (1)写出其对偶问题；(2)用图解法求解对偶问题； (3)利用(2)的结果及根据对偶问题性质写出原问题最优 解。 page 11 23 April 2025 School of Management

运筹学教程 School of Management page 11 23 April 2025 2.4 给出线性规划问题       = − + − +  − + + +  = + + + 0,( 1, ,4) 2 3 3 2 3 2 . min 2 3 5 6 1 2 3 4 1 2 3 4 1 2 3 4 x j  x x x x x x x x st Z x x x x j (1)写出其对偶问题；(2)用图解法求解对偶问题； (3)利用(2)的结果及根据对偶问题性质写出原问题最优 解。 第二章习题解答