第四版运筹学部分课后习题解答

运筹学部分课后习题解答

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3x14x29



s..t5x12x28x,x012

a）

解：由图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1234

3353

所以有x*1,,zmax1015

222

T

P78 2.4 已知线性规划问题：

max

z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

55

43

所以对偶问题的最优解为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）该线性规划问题的对偶问题为：

max

w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

x*(,,0)T,zmax6040800

63633

P81 2.12 某厂生产A、B、C三种产品，其所需劳动力、材料等有关数据见下表。要求：（a）确定获利最大的产品生产计划；（b）产品A的利润在什么范围内变动时，上述最优计划不变；（c）如果设计一种新产品D，单件劳动力消耗为8单位，材料消耗为2单位，每件可获利3元，问该种产品是否值得生产？ （d） 如果劳动力数量不增，材料不足时可从市场购买，每单位0.4 元。问该厂要不要购进原材料扩大生产，以购多少为宜。 解：由已知可得，设xj表示第j种产品，从而模型为：

maxz3x1x24x36x13x25x345



s..t3x14x25x330x1,x2,x30

a) 用单纯形法求解上述模型为：

得到最优解为x*(5,0,3)T；最优值为zmax354327

b）设产品A的利润为3，则上述模型中目标函数x1的系数用3替代并求解得：

要最优计划不变，要求有如下的不等式方程组成立

203

391

0解得： 5355

3530

9324

从而产品A的利润变化范围为：3,3,即2,4

5555

C）设产品D用x6表示，从已知可得

6c6cBB1P61/5

11

2833

P6'B1P64

122

555

把x6加入上述模型中求解得：

27.527 2

从而得最优解x*(0,0,5,0,0,5/2)T；最优值为zmax453所以产品D值得生产。

P101 3.1已知运输问题的产销量与单位运价如下表所示，用表上作业法求各题的最优解及最小运费。 表3-35

解：因为aibj，即产销平衡.所以由已知和最小元素法可得初始方案为

i1

j1

34

检验：

检验：

由于还有检验数小于零，所以需调整，调整二：

检验：

从上表可以看出所有的检验数都大于零，即为最优方案 最小运费为：zmin25257109151110180335

表3

4

解：因为ai58bj55，即产大于销，所以需添加一个假想的销地，销

i1

j1

量为3，构成产销平衡问题，其对应各销地的单位运费都为0。

由上表和最小元素法可得初始方案为

检验：

从上表可以看出所有的检验数都大于零，即为最优方案

最小运费为：zmin69513101741331503193

表3-37

3

5

解：因为ai80bj100，即销大于产，所以需添加一个假想的产地，产

i1

j1

量为20，构成产销平衡问题，其对应各销地的单位运费都为0。

由上表和最小元素法可得初始方案为

检验：

从上表可以看出所有的检验数都大于零，即为最优方案

最小运费为：zmin320520410653258002000305

P127 4.8 用割平面法求解整数规划问题。

maxz7x19x2

a） 





x,x0,且为整数12

x13x267x1x235

解：该问题的松弛问题为：

maxz7x19x2x13x26

7x1x235x,x012

则单纯形法求解该松弛问题得最后一单纯形表为：

割平面1为：(31/2)x2(07/22)x3(01/22)x4

171711x3x4x230x3x4x5

2222222222

割平面2为：(44/7)x1(01/7)x4(16/7)x5



164416

x4x5x1x540x4x5x6

777777

x*4,3，最优值为zmax749355

T

P144 5.3 用图解分析法求目标规划模型

+- -min P1 d1+ P2 d+ P（2d+1d） 2334-+

c） x1 + x2 + d1 - d1= 40

x1 + x2 + d2- - d2+= 40+10=50 x1 + d3- - d3+= 24 s.t.

x2 + d4- - d4+= 30

x1 、x2 、d1+、d1-、d2+、d2- 、d3+、d3- 、d4+、d4- ≥ 0

--

解:由下图可知，满足mind1的满意解为区域X2CDX1；

满足mind2+的满意解为闭区域BCDEB； 满足min2d3-的满意解为图中的A 点,

满足mind4-的满意解为图中的A 点，所以该问题的满意解为图中的点A（24，

26） 。

用图解分析法求目标规划模型



minzP1d1P2d3P3d2

x12x2d1d14

x12x2d2d24

x2xdd81233

x1,x20;di、di0i1,2,3

的满意解。

解：由下图可知，满足mind1的满意解为区域CDOA； 满足mind3的满意解为闭区域MCDOM；



满足mind2的满意解为图中的阴影部分，即为图中的凸多边形OABCDO 。

P170 6.4 求下图中的最小树

解：避圈法为：

得到最小树为：

P171 6.7 用标号法求下图中点v1到各点的最短路。

解：如下图所示：

P 173 6.14 用Ford-Fulkerson的标号算法求下图中所示各容量网络中从

vs到vt的

最大流，并标出其最小割集。图中各弧旁数字为容量cij，括弧中为流量fij.

B)

解：对上有向图进行2F标号得到

由于所有点都被标号了，即可以找到增广链，所以流量还可以调整，调整量为1，得

由图可知，标号中断，所以已经是最大流了，最大流量等于最小割的容量，最小割为与直线KK相交的弧的集合，即为

(vs,v3),(vs,v4),(vs,v5),(v1,vt),(v2,vt),(v2,v3)

*

所以从vs到vt的最大流为：fst12532114

C)

解：对上有向图进行2F标号得到

由于所有点都被标号了，即可以找到增广链，所以流量还可以调整，调整量为1，得

由图可知，标号中断，所以已经是最大流了，最大流量等于最小割的容量，最小割为与直线KK相交的弧的集合，即为(vs,v1),(vs,v3),v(2v,5)，所以从vs到vt的最大流为：

*fst53513

P193 7.1 根据下表给定的条件，绘制PERT网络图。

绘制的PERT网络图为：

解：绘制的PERT网络图为：

解：绘制的PERT网络图为：

P194 表7-11

解：绘制的PERT网络图为：

P215 8.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3x14x29



s..t5x12x28x,x012

a）

解：由图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1234

3353

所以有x*1,,zmax1015

222

T

P78 2.4 已知线性规划问题：

max

z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

55

43

所以对偶问题的最优解为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）该线性规划问题的对偶问题为：

max

w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

x*(,,0)T,zmax6040800

63633

P81 2.12 某厂生产A、B、C三种产品，其所需劳动力、材料等有关数据见下表。要求：（a）确定获利最大的产品生产计划；（b）产品A的利润在什么范围内变动时，上述最优计划不变；（c）如果设计一种新产品D，单件劳动力消耗为8单位，材料消耗为2单位，每件可获利3元，问该种产品是否值得生产？ （d） 如果劳动力数量不增，材料不足时可从市场购买，每单位0.4 元。问该厂要不要购进原材料扩大生产，以购多少为宜。 解：由已知可得，设xj表示第j种产品，从而模型为：

maxz3x1x24x36x13x25x345



s..t3x14x25x330x1,x2,x30

a) 用单纯形法求解上述模型为：

得到最优解为x*(5,0,3)T；最优值为zmax354327

b）设产品A的利润为3，则上述模型中目标函数x1的系数用3替代并求解得：

要最优计划不变，要求有如下的不等式方程组成立

203

391

0解得： 5355

3530

9324

从而产品A的利润变化范围为：3,3,即2,4

5555

C）设产品D用x6表示，从已知可得

6c6cBB1P61/5

11

2833

P6'B1P64

122

555

把x6加入上述模型中求解得：

27.527 2

从而得最优解x*(0,0,5,0,0,5/2)T；最优值为zmax453所以产品D值得生产。

P101 3.1已知运输问题的产销量与单位运价如下表所示，用表上作业法求各题的最优解及最小运费。 表3-35

解：因为aibj，即产销平衡.所以由已知和最小元素法可得初始方案为

i1

j1

34

检验：

检验：

由于还有检验数小于零，所以需调整，调整二：

检验：

从上表可以看出所有的检验数都大于零，即为最优方案 最小运费为：zmin25257109151110180335

表3

4

解：因为ai58bj55，即产大于销，所以需添加一个假想的销地，销

i1

j1

量为3，构成产销平衡问题，其对应各销地的单位运费都为0。

由上表和最小元素法可得初始方案为

检验：

从上表可以看出所有的检验数都大于零，即为最优方案

最小运费为：zmin69513101741331503193

表3-37

3

5

解：因为ai80bj100，即销大于产，所以需添加一个假想的产地，产

i1

j1

量为20，构成产销平衡问题，其对应各销地的单位运费都为0。

由上表和最小元素法可得初始方案为

检验：

从上表可以看出所有的检验数都大于零，即为最优方案

最小运费为：zmin320520410653258002000305

P127 4.8 用割平面法求解整数规划问题。

maxz7x19x2

a） 





x,x0,且为整数12

x13x267x1x235

解：该问题的松弛问题为：

maxz7x19x2x13x26

7x1x235x,x012

则单纯形法求解该松弛问题得最后一单纯形表为：

割平面1为：(31/2)x2(07/22)x3(01/22)x4

171711x3x4x230x3x4x5

2222222222

割平面2为：(44/7)x1(01/7)x4(16/7)x5



164416

x4x5x1x540x4x5x6

777777

x*4,3，最优值为zmax749355

T

P144 5.3 用图解分析法求目标规划模型

+- -min P1 d1+ P2 d+ P（2d+1d） 2334-+

c） x1 + x2 + d1 - d1= 40

x1 + x2 + d2- - d2+= 40+10=50 x1 + d3- - d3+= 24 s.t.

x2 + d4- - d4+= 30

x1 、x2 、d1+、d1-、d2+、d2- 、d3+、d3- 、d4+、d4- ≥ 0

--

解:由下图可知，满足mind1的满意解为区域X2CDX1；

满足mind2+的满意解为闭区域BCDEB； 满足min2d3-的满意解为图中的A 点,

满足mind4-的满意解为图中的A 点，所以该问题的满意解为图中的点A（24，

26） 。

用图解分析法求目标规划模型



minzP1d1P2d3P3d2

x12x2d1d14

x12x2d2d24

x2xdd81233

x1,x20;di、di0i1,2,3

的满意解。

解：由下图可知，满足mind1的满意解为区域CDOA； 满足mind3的满意解为闭区域MCDOM；



满足mind2的满意解为图中的阴影部分，即为图中的凸多边形OABCDO 。

P170 6.4 求下图中的最小树

解：避圈法为：

得到最小树为：

P171 6.7 用标号法求下图中点v1到各点的最短路。

解：如下图所示：

P 173 6.14 用Ford-Fulkerson的标号算法求下图中所示各容量网络中从

vs到vt的

最大流，并标出其最小割集。图中各弧旁数字为容量cij，括弧中为流量fij.

B)

解：对上有向图进行2F标号得到

由于所有点都被标号了，即可以找到增广链，所以流量还可以调整，调整量为1，得

由图可知，标号中断，所以已经是最大流了，最大流量等于最小割的容量，最小割为与直线KK相交的弧的集合，即为

(vs,v3),(vs,v4),(vs,v5),(v1,vt),(v2,vt),(v2,v3)

*

所以从vs到vt的最大流为：fst12532114

C)

解：对上有向图进行2F标号得到

由于所有点都被标号了，即可以找到增广链，所以流量还可以调整，调整量为1，得

由图可知，标号中断，所以已经是最大流了，最大流量等于最小割的容量，最小割为与直线KK相交的弧的集合，即为(vs,v1),(vs,v3),v(2v,5)，所以从vs到vt的最大流为：

*fst53513

P193 7.1 根据下表给定的条件，绘制PERT网络图。

绘制的PERT网络图为：

解：绘制的PERT网络图为：

解：绘制的PERT网络图为：

P194 表7-11

解：绘制的PERT网络图为：

P215 8.1