运筹学部分课后习题解答
P47 1.1 用图解法求解线性规划问题
min z=2x 1+3x 2
⎧4x 1+6x 2≥6
a） ⎪
s .. t ⎨4x 1+2x 2≥4⎪x , x ≥0⎩12
解：由图1可知，该问题的可行域为凸集MABCN ，且可知线段BA 上的点都为
3
最优解，即该问题有无穷多最优解，这时的最优值为z min =2⨯+3⨯0=
3
2
P47 1.3 用图解法和单纯形法求解线性规划问题
max z=10x1+5x 2
a）
⎧3x 1+4x 2≤9
⎪
s .. t ⎨5x 1+2x 2≤8⎪x , x ≥0⎩12
解：由图1可知，该问题的可行域为凸集OABCO ，且可知B 点为最优值点，
⎧x =1T
⎧3x 1+4x 2=9⎪13⎛⎫*
⇒⎨即⎨3，即最优解为x = 1, ⎪
⎝2⎭⎩5x 1+2x 2=8⎪x 2=
⎩2
这时的最优值为z max =10⨯1+5⨯
335
= 22
单纯形法： 原问题化成标准型为
max z=10x1+5x 2
⎧3x 1+4x 2+x 3=9
⎪
s .. t ⎨5x 1+2x 2+x 4=8⎪x , x , x , x ≥0⎩1234
335⎛3⎫
所以有x *= 1, ⎪, z max =10⨯1+5⨯=
222⎝⎭
T
P78 2.4 已知线性规划问题：
max
z =2x 1+4x 2+x 3+x 4
+x 4≤8⎧x 1+3x 2
⎪2x +x ≤612⎪⎪
x 2+x 3+x 4≤6⎨
⎪x +x +x ≤9⎪123⎪⎩x 1, x 2, x 3, x 4≥0
求: (1) 写出其对偶问题；（2）已知原问题最优解为X *=(2, 2, 4, 0) ，试根据对偶理论，直接求出对偶问题的最优解。 解：（1）该线性规划问题的对偶问题为：
min
w =8y 1+6y 2+6y 3+9y 4
+y 4≥2⎧y 1+2y 2
⎪3y +y +y +y ≥41234⎪⎪
y 3+y 4≥1⎨
⎪y +y 3≥1⎪1⎪⎩y 1, y 2, y 3, y 4≥0
（2）由原问题最优解为X *=(2, 2, 4, 0) ，根据互补松弛性得：
+y 4=2⎧y 1+2y 2
⎪
⎨3y 1+y 2+y 3+y 4=4 ⎪y 3+y 4=1⎩
把X *=(2, 2, 4, 0) 代入原线性规划问题的约束中得第四个约束取严格不等号，即2+2+4=8
=2⎧y 1+2y 2
⎪
从而有⎨3y 1+y 2+y 3=4
⎪y 3=1⎩
43
得y 1=, y 2=, y 3=1, y 4=0
55
43
所以对偶问题的最优解为y *=(, ,1,0) T ，最优值为w min =16
55
P79 2.7 考虑如下线性规划问题：
min z =60x 1+40x 2+80x 3⎧3x 1+2x 2+x 3≥2⎪4x +x +3x ≥4⎪123⎨
⎪2x 1+2x 2+2x 3≥3⎪⎩x 1, x 2, x 3≥0
（1）写出其对偶问题；（2）用对偶单纯形法求解原问题； 解：（1）该线性规划问题的对偶问题为：
max w =2y 1+4y 2+3y 3⎧3y 1+4y 2+2y 3≤60⎪2y +y +2y ≤40⎪123⎨
⎪y 1+3y 2+2y 3≤80⎪y 1, y 2, y 3≥0⎩
（2）在原问题加入三个松弛变量x 4, x 5, x 6把该线性规划问题化为标准型：
max z =-60x 1-40x 2-80x 3=-2⎧-3x 1-2x 2-x 3+x 4⎪-4x -x -3x +x =-4
⎪1235⎨
+x 6=-3⎪-2x 1-2x 2-2x 3
⎪x j ≥0, j =1, ,6⎩
x *=(, ,0) T , z max =60⨯+40⨯+80⨯0=
63633
P81 2.12 某厂生产A 、B 、C 三种产品，其所需劳动力、材料等有关数据见下表。要求：（a ）确定获利最大的产品生产计划；（b ）产品A 的利润在什么范围内变动时，上述最优计划不变；（c ）如果设计一种新产品D ，单件劳动力消耗为8单位，材料消耗为2单位，每件可获利3元，问该种产品是否值得生产？ （d ） 如果劳动力数量不增，材料不足时可从市场购买，每单位0.4 元。问该厂要不要购进原材料扩大生产，以购多少为宜。 解：由已知可得，设x j 表示第j 种产品，从而模型为：
max z =3x 1+x 2+4x 3⎧6x 1+3x 2+5x 3≤45
⎪
s .. t ⎨3x 1+4x 2+5x 3≤30⎪x 1, x 2, x 3≥0⎩
a) 用单纯形法求解上述模型为：
得到最优解为x *=(5,0,3)T ；最优值为z max =3⨯5+4⨯3=27
b）设产品A 的利润为3+λ，则上述模型中目标函数x 1的系数用3+λ替代并求解得：
要最优计划不变，要求有如下的不等式方程组成立
λ⎧-2+≤0⎪3⎪
39⎪1λ
--≤0解得： -≤λ≤⎨
55⎪53
⎪3λ⎪-5+3≤0⎩
9⎤⎡3⎡24⎤
从而产品A 的利润变化范围为：⎢3-,3+⎥, 即⎢2, 4⎥
5⎦⎣5⎣55⎦
C ）设产品D 用x 6表示，从已知可得
σ6=c 6-c B B -1P 6=1/5
⎡1
⎢3' -1
P 6=B P 6=⎢
⎢-1⎢⎣5
1⎤
-⎥⎡2⎤
8⎡⎤3
⎥⎢⎥=⎢4⎥ 2⎥⎣2⎦⎢-⎥
⎣5⎦
5⎥⎦
把x 6加入上述模型中求解得：
=27.5>27 2
从而得最优解x *=(0,0,5,0,0,5/2) T ；最优值为z max =4⨯5+3⨯所以产品D 值得生产。 d ）
P101 3.1已知运输问题的产销量与单位运价如下表所示，用表上作业法求各题的最优解及最小运费。 表3-35
解：由已知和最小元素法可得初始方案为
检验：
检验：
检验：
从上表可以看出所有的检验数都大于零，即为最优方案 最小运费为：z min =2⨯5+2⨯5+7⨯10+9⨯15+11⨯10+18⨯0=335
表3
4
解：因为∑a i =58>∑b j =55，即产大于销，所以需添加一个假想的销地，销
i =1
j =1
量为3，构成产销平衡问题，其对应各销地的单位运费都为0。
由上表和最小元素法可得初始方案为 检验：
从上表可以看出所有的检验数都大于零，即为最优方案
最小运费为：z min =6⨯9+5⨯1+3⨯10+1⨯7+4⨯13+3⨯15+0⨯3=193
表3-37
3
5
解：因为∑a i =80
i =1
j =1
量为20，构成产销平衡问题，其对应各销地的单位运费都为0。
由上表和最小元素法可得初始方案为 检验：
从上表可以看出所有的检验数都大于零，即为最优方案
最小运费为：z min =3⨯20+5⨯20+4⨯10+6⨯5+3⨯25+8⨯0+0⨯20+0⨯0=305
P127 4.8 用割平面法求解整数规划问题。
max z =7x 1+9x 2
⎧-x 1+3x 2≤6a ） ⎪
7x +x ≤35⎨12
⎪x , x ≥0, 且为整数⎩12
解：该问题的松弛问题为：
max z =7x 1+9x 2⎧-x 1+3x 2≤6⎪
⎨7x 1+x 2≤35⎪x , x ≥0⎩12
割平面1为：(3+1/2) =x 2+(0+7/22) x 3+(0+1/22) x 4
171711-x 3-x 4=x 2-3≤0⇒x 3+x 4-x 5=
2222222222⇒
割平面2为：(4+4/7) =x 1+(0+1/7) x 4+(-1+6/7) x 5
⇒
416164-x 4-x 5=x 1-x 5-4≤0
⇒x 4+x 5-x 6= x *=(4,3)，最优值为z max =7⨯4+9⨯3=55
T
P144 5.3 用图解分析法求目标规划模型
min Z = P 1 d 1-+ P 2 d 2++ P 3（2d 3- +1d 4-）
c ）
s.t.
解:由下图可知，满足目标函数的满意解为图中的A 点。
x 1 + x2 + d 1- - d 1+= 40
x 1 + x2 + d 2- - d 2+= 40+10=50 x 1 + d 3- - d 3+= 24 x 2 + d 4- - d 4+= 30
x 1 、x 2 、d 1+、d 1-、d 2+、d 2- 、d 3+、d 3- 、d 4+、d 4- ≥ 0
P170 6.4 求下图中的最小树
解：避圈法为：
得到最小树为：
P171 6.7 用标号法求下图中点v 1到各点的最短路。
解：如下图所示：
P 173 6.14 用Ford-Fulkerson 的标号算法求下图中所示各容量网络中从
v s
到
v t
的
最大流，并标出其最小割集。图中各弧旁数字为容量c ij ，括弧中为流量f ij .
B)
解：对上有向图进行2F 标号得到
由于所有点都被标号了，即可以找到增广链，所以流量还可以调整，调整量为1，得
由图可知，标号中断，所以已经是最大流了，最大流量等于最小割的容量，最小割为与直线KK 相交的弧的集合，即为
{(v s , v 3),(v s , v 4),(v s , v 5),(v 1, v t ),(v 2, v t ),(v 2, v 3) }
*
=1+2+5+3+2+1=14 所以从v s 到v t 的最大流为：f st
C)
解：对上有向图进行2F 标号得到
由于所有点都被标号了，即可以找到增广链，所以流量还可以调整，调整量为1，得
由图可知，标号中断，所以已经是最大流了，最大流量等于最小割的容量，最小割为与直线
v s , v 3), v (2v , 5}) ，所以从v s 到v t 的最大流为：KK 相交的弧的集合，即为{(v s , v 1), (
*
f st =5+3+5=13
P193 7.1 根据下表给定的条件，绘制PERT 网络图。
绘制的PERT 网络图为：
解：绘制的PERT 网络图为：
运筹学部分课后习题解答
P47 1.1 用图解法求解线性规划问题
min z=2x 1+3x 2
⎧4x 1+6x 2≥6
a） ⎪
s .. t ⎨4x 1+2x 2≥4⎪x , x ≥0⎩12
解：由图1可知，该问题的可行域为凸集MABCN ，且可知线段BA 上的点都为
3
最优解，即该问题有无穷多最优解，这时的最优值为z min =2⨯+3⨯0=
3
2
P47 1.3 用图解法和单纯形法求解线性规划问题
max z=10x1+5x 2
a）
⎧3x 1+4x 2≤9
⎪
s .. t ⎨5x 1+2x 2≤8⎪x , x ≥0⎩12
解：由图1可知，该问题的可行域为凸集OABCO ，且可知B 点为最优值点，
⎧x =1T
⎧3x 1+4x 2=9⎪13⎛⎫*
⇒⎨即⎨3，即最优解为x = 1, ⎪
⎝2⎭⎩5x 1+2x 2=8⎪x 2=
⎩2
这时的最优值为z max =10⨯1+5⨯
335
= 22
单纯形法： 原问题化成标准型为
max z=10x1+5x 2
⎧3x 1+4x 2+x 3=9
⎪
s .. t ⎨5x 1+2x 2+x 4=8⎪x , x , x , x ≥0⎩1234
335⎛3⎫
所以有x *= 1, ⎪, z max =10⨯1+5⨯=
222⎝⎭
T
P78 2.4 已知线性规划问题：
max
z =2x 1+4x 2+x 3+x 4
+x 4≤8⎧x 1+3x 2
⎪2x +x ≤612⎪⎪
x 2+x 3+x 4≤6⎨
⎪x +x +x ≤9⎪123⎪⎩x 1, x 2, x 3, x 4≥0
求: (1) 写出其对偶问题；（2）已知原问题最优解为X *=(2, 2, 4, 0) ，试根据对偶理论，直接求出对偶问题的最优解。 解：（1）该线性规划问题的对偶问题为：
min
w =8y 1+6y 2+6y 3+9y 4
+y 4≥2⎧y 1+2y 2
⎪3y +y +y +y ≥41234⎪⎪
y 3+y 4≥1⎨
⎪y +y 3≥1⎪1⎪⎩y 1, y 2, y 3, y 4≥0
（2）由原问题最优解为X *=(2, 2, 4, 0) ，根据互补松弛性得：
+y 4=2⎧y 1+2y 2
⎪
⎨3y 1+y 2+y 3+y 4=4 ⎪y 3+y 4=1⎩
把X *=(2, 2, 4, 0) 代入原线性规划问题的约束中得第四个约束取严格不等号，即2+2+4=8
=2⎧y 1+2y 2
⎪
从而有⎨3y 1+y 2+y 3=4
⎪y 3=1⎩
43
得y 1=, y 2=, y 3=1, y 4=0
55
43
所以对偶问题的最优解为y *=(, ,1,0) T ，最优值为w min =16
55
P79 2.7 考虑如下线性规划问题：
min z =60x 1+40x 2+80x 3⎧3x 1+2x 2+x 3≥2⎪4x +x +3x ≥4⎪123⎨
⎪2x 1+2x 2+2x 3≥3⎪⎩x 1, x 2, x 3≥0
（1）写出其对偶问题；（2）用对偶单纯形法求解原问题； 解：（1）该线性规划问题的对偶问题为：
max w =2y 1+4y 2+3y 3⎧3y 1+4y 2+2y 3≤60⎪2y +y +2y ≤40⎪123⎨
⎪y 1+3y 2+2y 3≤80⎪y 1, y 2, y 3≥0⎩
（2）在原问题加入三个松弛变量x 4, x 5, x 6把该线性规划问题化为标准型：
max z =-60x 1-40x 2-80x 3=-2⎧-3x 1-2x 2-x 3+x 4⎪-4x -x -3x +x =-4
⎪1235⎨
+x 6=-3⎪-2x 1-2x 2-2x 3
⎪x j ≥0, j =1, ,6⎩
x *=(, ,0) T , z max =60⨯+40⨯+80⨯0=
63633
P81 2.12 某厂生产A 、B 、C 三种产品，其所需劳动力、材料等有关数据见下表。要求：（a ）确定获利最大的产品生产计划；（b ）产品A 的利润在什么范围内变动时，上述最优计划不变；（c ）如果设计一种新产品D ，单件劳动力消耗为8单位，材料消耗为2单位，每件可获利3元，问该种产品是否值得生产？ （d ） 如果劳动力数量不增，材料不足时可从市场购买，每单位0.4 元。问该厂要不要购进原材料扩大生产，以购多少为宜。 解：由已知可得，设x j 表示第j 种产品，从而模型为：
max z =3x 1+x 2+4x 3⎧6x 1+3x 2+5x 3≤45
⎪
s .. t ⎨3x 1+4x 2+5x 3≤30⎪x 1, x 2, x 3≥0⎩
a) 用单纯形法求解上述模型为：
得到最优解为x *=(5,0,3)T ；最优值为z max =3⨯5+4⨯3=27
b）设产品A 的利润为3+λ，则上述模型中目标函数x 1的系数用3+λ替代并求解得：
要最优计划不变，要求有如下的不等式方程组成立
λ⎧-2+≤0⎪3⎪
39⎪1λ
--≤0解得： -≤λ≤⎨
55⎪53
⎪3λ⎪-5+3≤0⎩
9⎤⎡3⎡24⎤
从而产品A 的利润变化范围为：⎢3-,3+⎥, 即⎢2, 4⎥
5⎦⎣5⎣55⎦
C ）设产品D 用x 6表示，从已知可得
σ6=c 6-c B B -1P 6=1/5
⎡1
⎢3' -1
P 6=B P 6=⎢
⎢-1⎢⎣5
1⎤
-⎥⎡2⎤
8⎡⎤3
⎥⎢⎥=⎢4⎥ 2⎥⎣2⎦⎢-⎥
⎣5⎦
5⎥⎦
把x 6加入上述模型中求解得：
=27.5>27 2
从而得最优解x *=(0,0,5,0,0,5/2) T ；最优值为z max =4⨯5+3⨯所以产品D 值得生产。 d ）
P101 3.1已知运输问题的产销量与单位运价如下表所示，用表上作业法求各题的最优解及最小运费。 表3-35
解：由已知和最小元素法可得初始方案为
检验：
检验：
检验：
从上表可以看出所有的检验数都大于零，即为最优方案 最小运费为：z min =2⨯5+2⨯5+7⨯10+9⨯15+11⨯10+18⨯0=335
表3
4
解：因为∑a i =58>∑b j =55，即产大于销，所以需添加一个假想的销地，销
i =1
j =1
量为3，构成产销平衡问题，其对应各销地的单位运费都为0。
由上表和最小元素法可得初始方案为 检验：
从上表可以看出所有的检验数都大于零，即为最优方案
最小运费为：z min =6⨯9+5⨯1+3⨯10+1⨯7+4⨯13+3⨯15+0⨯3=193
表3-37
3
5
解：因为∑a i =80
i =1
j =1
量为20，构成产销平衡问题，其对应各销地的单位运费都为0。
由上表和最小元素法可得初始方案为 检验：
从上表可以看出所有的检验数都大于零，即为最优方案
最小运费为：z min =3⨯20+5⨯20+4⨯10+6⨯5+3⨯25+8⨯0+0⨯20+0⨯0=305
P127 4.8 用割平面法求解整数规划问题。
max z =7x 1+9x 2
⎧-x 1+3x 2≤6a ） ⎪
7x +x ≤35⎨12
⎪x , x ≥0, 且为整数⎩12
解：该问题的松弛问题为：
max z =7x 1+9x 2⎧-x 1+3x 2≤6⎪
⎨7x 1+x 2≤35⎪x , x ≥0⎩12
割平面1为：(3+1/2) =x 2+(0+7/22) x 3+(0+1/22) x 4
171711-x 3-x 4=x 2-3≤0⇒x 3+x 4-x 5=
2222222222⇒
割平面2为：(4+4/7) =x 1+(0+1/7) x 4+(-1+6/7) x 5
⇒
416164-x 4-x 5=x 1-x 5-4≤0
⇒x 4+x 5-x 6= x *=(4,3)，最优值为z max =7⨯4+9⨯3=55
T
P144 5.3 用图解分析法求目标规划模型
min Z = P 1 d 1-+ P 2 d 2++ P 3（2d 3- +1d 4-）
c ）
s.t.
解:由下图可知，满足目标函数的满意解为图中的A 点。
x 1 + x2 + d 1- - d 1+= 40
x 1 + x2 + d 2- - d 2+= 40+10=50 x 1 + d 3- - d 3+= 24 x 2 + d 4- - d 4+= 30
x 1 、x 2 、d 1+、d 1-、d 2+、d 2- 、d 3+、d 3- 、d 4+、d 4- ≥ 0
P170 6.4 求下图中的最小树
解：避圈法为：
得到最小树为：
P171 6.7 用标号法求下图中点v 1到各点的最短路。
解：如下图所示：
P 173 6.14 用Ford-Fulkerson 的标号算法求下图中所示各容量网络中从
v s
到
v t
的
最大流，并标出其最小割集。图中各弧旁数字为容量c ij ，括弧中为流量f ij .
B)
解：对上有向图进行2F 标号得到
由于所有点都被标号了，即可以找到增广链，所以流量还可以调整，调整量为1，得
由图可知，标号中断，所以已经是最大流了，最大流量等于最小割的容量，最小割为与直线KK 相交的弧的集合，即为
{(v s , v 3),(v s , v 4),(v s , v 5),(v 1, v t ),(v 2, v t ),(v 2, v 3) }
*
=1+2+5+3+2+1=14 所以从v s 到v t 的最大流为：f st
C)
解：对上有向图进行2F 标号得到
由于所有点都被标号了，即可以找到增广链，所以流量还可以调整，调整量为1，得
由图可知，标号中断，所以已经是最大流了，最大流量等于最小割的容量，最小割为与直线
v s , v 3), v (2v , 5}) ，所以从v s 到v t 的最大流为：KK 相交的弧的集合，即为{(v s , v 1), (
*
f st =5+3+5=13
P193 7.1 根据下表给定的条件，绘制PERT 网络图。
绘制的PERT 网络图为：
解：绘制的PERT 网络图为：