运筹学课后习题解答 - 1

运筹学部分课后习题解答

P47 1.1 用图解法求解线性规划问题

min z=2x1?3x2?4x1?6x2?6 a） ?

s..t?4x1?2x2?4?x,x?0?12解：由图1可知，该问题的可行域为凸集MABCN，且可知线段BA上的点都为

3最优解，即该问题有无穷多最优解，这时的最优值为zmin=2??3?0?3

2

P47 1.3 用图解法和单纯形法求解线性规划问题

max z=10x1?5x2 a）

?3x1?4x2?9 ?s..t?5x1?2x2?8?x,x?0?12解：由图1可知，该问题的可行域为凸集OABCO，且可知B点为最优值点，

?x?1T?3x1?4x2?9?13??*??即?3，即最优解为x??1,?

?2??5x1?2x2?8?x2??2这时的最优值为zmax=10?1?5?335? 22

单纯形法： 原问题化成标准型为

max z=10x1?5x2?3x1?4x2?x3?9 ?s..t?5x1?2x2?x4?8?x,x,x,x?0?1234cj? 10 XB x3 x4 5 x2 0 x3 0 x4 CB b 9 8 x1 0 0 3 [5] 10 4 2 5 [14/5] 2/5 1 1 0 0 1 0 0 1 0 0 5/14 -1/7 0 1 0 -3/5 1/5 -2 -3/14 2/7 Cj?Zj 0 10 x3 x1 21/5 8/5 0 1 0 Cj?Zj 5 10 x2 x1 3/2 1 0 1 0 Cj?Zj -5/14 -25/14 335?3?所以有x*??1,?,zmax?10?1?5??

22?2?

TP78 2.4 已知线性规划问题：

maxz?2x1?4x2?x3?x4?x4?8?x1?3x2?2x?x?612??x2?x3?x4?6??x?x?x?9?123??x1,x2,x3,x4?0

求: (1) 写出其对偶问题；（2）已知原问题最优解为X*?(2,2,4,0)，试根据对偶理论，直接求出对偶问题的最优解。 解：（1）该线性规划问题的对偶问题为：

minw?8y1?6y2?6y3?9y4?y4?2?y1?2y2?3y?y?y?y?41234??y3?y4?1??y?y3?1?1??y1,y2,y3,y4?0

（2）由原问题最优解为X*?(2,2,4,0)，根据互补松弛性得：

?y4?2?y1?2y2??3y1?y2?y3?y4?4 ?y3?y4?1?把X*?(2,2,4,0)代入原线性规划问题的约束中得第四个约束取严格不等号，即2?2?4?8?9?y4?0

?2?y1?2y2? 从而有?3y1?y2?y3?4

?y3?1?43 得y1?,y2?,y3?1,y4?0

5543所以对偶问题的最优解为y*?(,,1,0)T，最优值为wmin?16

55

P79 2.7 考虑如下线性规划问题：

minz?60x1?40x2?80x3?3x1?2x2?x3?2?4x?x?3x?4?123??2x1?2x2?2x3?3??x1,x2,x3?0

（1）写出其对偶问题；（2）用对偶单纯形法求解原问题； 解：（1）该线性规划问题的对偶问题为：

maxw?2y1?4y2?3y3?3y1?4y2?2y3?60?2y?y?2y?40?123??y1?3y2?2y3?80?y1,y2,y3?0?

（2）在原问题加入三个松弛变量x4,x5,x6把该线性规划问题化为标准型：

maxz??60x1?40x2?80x3??2??3x1?2x2?x3?x4??4x?x?3x?x??4 ?1235??x6??3??2x1?2x2?2x3?xj?0,j?1,,6?cj? -60 XB x4 x5 x6 -40 x2 -80 x3 0 x4 0 x5 0 x6 CB b -2 -4 -3 x1 0 0 0 -3 [-4] -2 -60 -2 -1 -2 -40 -5/4 1/4 -1 -3 -2 -80 5/4 3/4 1 0 0 0 1 0 0 1 0 0 -1/12 -1/4 0 0 1 0 0 0 Cj?Zj 0 80 x4 x1 1 1 0 1