运筹学部分课后习题解答

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