运筹学课后习题解答_1.(DOC)

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*T

P78 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

53所以对偶问题的最优解为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 0 x6 -1 0 0 [-3/2] -1/2 -25 0 0 1 0 -35 5/3 2/3 1/3 -80/3 0 0 1 0 0 0 -1/2 -15 1/3 -1/3 1/3 -20/3 1 0 -5/6 1/6 -2/3 -50/3 CjZj 0 80 40 x4 x1 x2 11/6 0 5/6 2/3 1 0 0 CjZj 5252230 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 元。问该厂要不要购进原材料扩大生产，以购多少为宜。 消 耗 定 额 产品 A B C 可用量（单位） 资源 劳动力 材 料 产品利润（元/件） 6 3 5 3 4 5 3 1 4 45 30 解：由已知可得，设xj表示第j种产品，从而模型为：

maxz3x1x24x36x13x25x345 s..t3x14x25x330x1,x2,x30a) 用单纯形法求解上述模型为：

cj 3 1 4 0 0 CB XB x4 x5 b 45 30 x1 x2 x3 x4 x5 0 0 6 3 3 3 4 1 5 [5] 4 0 1 0 0 1 0 1 0 0 1 0 0 1/3 0 1 0 -1 1/5 -4/5 -1/3 CjZj 0 4 x4 x3 15 6 [3] -1 3/5 4/5 3/5 -11/5 CjZj 3 4 x1 x3 5 3 1 0 0 -1/3 1 -2 -1/5 2/5 -1/5 -3/5 CjZj 得到最优解为x*(5,0,3)T；最优值为zmax354327

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

cj 3 1 x2 4 0 0 x5 CB XB x1 x3 b x1 5 3 1 0 x3 x4 3 4 CjZj -1/3 1 -2 0 1 0 1/3 -1/5 -1/5 -1/5-/3 -1/3 2/5 -3/5 -3/5+/3  0 CjZj -2+/3 0 要最优计划不变，要求有如下的不等式方程组成立

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用x6表示，从已知可得

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

13'1P6BP61512834 2255把x6加入上述模型中求解得：

cj 3 XB x1 x3 1 x2 4 x3 0 x4 0 x5 3 x6 CB b 5 3 x1 3 4 1 0 0 -1/3 1 -2 -1/6 0 1 0 0 1/3 -1/5 -1/5 1/6 -1/3 2/5 -3/5 -1/6 [2] -4/5 1/5 1 0 CjZj 3 4 x6 x3 5/2 5 1/2 2/5 13/15 1 -1/15 4/15 CjZj -1/10 -59/30 0 -7/30 -17/30 0 527.527 2从而得最优解x*(0,0,5,0,0,5/2)T；最优值为zmax453所以产品D值得生产。 d）

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

销地 产地 A1 A2 A3 销量 B1 10 12 2 5 B2 2 7 14 15 B3 20 9 16 15 B4 11 20 18 10 产量 15 25 5 解：由已知和最小元素法可得初始方案为

销地 B1 产地 A1 A2 A3 销量 检验：

5 5 B2 15 0 15 B3 15 0 15 B4 10 10 产量 15 25 5

由于有两个检验数小于零，所以需调整，调整一： 销地B1 B2 B3 B4 产地 A1 A2 A3 销量 检验：

5 5 15 0 15 15 15 10 0 10 产量 15 25 5

由于还有检验数小于零，所以需调整，调整二： 销地 B1 B2 B3 B4 产地 A1 A2 A3 销量 检验： 5 5 5 10 15 15 15 10 0 10 产量 15 25 5

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

表3-36 销地 产地 A1 A2 A3 销量 34B1 8 6 5 10 B2 4 9 3 10 B3 1 4 4 20 B4 2 7 3 15 产量 7 25 26 解：因为ai58bj55，即产大于销，所以需添加一个假想的销地，销

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

销地 B1 产地 A1 A2 A3 销量 8 6 5 B2 4 9 3 B3 1 4 4 B4 2 7 3 B5 0 0 0 3 产量 7 25 26 10 10 20 15 由上表和最小元素法可得初始方案为 销地 B1 产地 A1 A2 A3 销量 9 1 10 B2 10 10 B3 7 13 20 B4 15 15 B5 3 3 产量 7 25 26 检验：

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

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

表3-37

销地 B1 产地 A1 A2 A3 销量 3B2 6 M 3 25 5B3 3 8 9 20 B4 7 4 6 10 B5 5 7 8 20 产量 20 30 30 8 5 6 25 解：因为ai80bj100，即销大于产，所以需添加一个假想的产地，产

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

销地 B1 产地 A1 A2 A3 A4 销量 8 5 6 0 25 B2 6 M 3 0 25 B3 3 8 9 0 20 B4 7 4 6 0 10 B5 5 7 8 0 20 产量 20 30 30 20 由上表和最小元素法可得初始方案为 销地 B1 产地 A1 A2 A3 A4 销量 5 20 25 B2 25 25 B3 20 0 20 B4 10 10 B5 15 5 20 产量 20 30 30 20 检验：

由于有两个检验数小于零，所以需调整，调整一： 销地 B1 产地 A1 A2 20 A3 A4 5 销量 25 检验： B2 25 25 B3 20 0 20 B4 10 10 B5 5 15 20 产量 20 30 30 20

由于还有检验数小于零，所以需调整，调整二： 销地 B1 产地 A1 A2 20 A3 5 A4 销量 25 检验： B2 25 25 B3 20 0 20 B4 10 10 B5 0 20 20 产量 20 30 30 20

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

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

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

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

7xx3512x,x0,且为整数12解：该问题的松弛问题为：

maxz7x19x2x13x267x1x235x,x012

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

7 9 0 0 cj CB XB b x1 x2 x3 x4 9 7 x2 x1 7/2 0 9/2 1 0 1 0 0 7/22 1/22 -1/22 3/22 -28/11 -15/11 CjZj 割平面1为：(31/2)x2(07/22)x3(01/22)x4

171711x3x4x230x3x4x5 2222222222从而有 7 9 0 0 0 cj CB XB b x1 x2 x3 x4 x5 9 7 0 x2 x1 x5 7/2 0 9/2 1 -1/2 0 0 3 0 1 0 0 0 1 0 0 0 7/22 1/22 0 0 -1/22 3/22 -7/22 -1/22 1 -28/11 -15/11 0 0 0 1 0 0 1/7 1/7 -1 1 -1/7 -22/7 -8 CjZj 9 7 0 x2 x1 x3 32/7 1 11/7 0 0 CjZj 割平面2为：(44/7)x1(01/7)x4(16/7)x5

cj 4161x4x5x1x540x4x5x6 7777777 9 0 0 0 3 b 3 x1 x2 x3 x4 x5 x6 CB XB x2 x1 x3 x6 9 7 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1/7 1/7 1 0 32/7 1 11/7 0 -4/7 0 0 3 4 1 4 0 1 0 0 0 -1/7 0 -22/7 0 -1/7 -6/7 1 -1 0 0 0 1 0 -8 1 -1 -4 6 -2 0 0 1 1 -7 -7 CjZj 9 7 0 0 x2 x1 x3 x4 CjZj 由上表可知该问题已经达到整数解了，所以该整数解就是原问题的最优解，即x*4,3，最优值为zmax749355

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

min Z = P1 d1-+ P2 d2++ P3（2d3- +1d4-）

c）

s.t.

解:由下图可知，满足目标函数的满意解为图中的A 点。

x1 + x2 + d1- - d1+= 40

x1 + x2 + d2- - d2+= 40+10=50 x1 + d3- - d3+= 24 x2 + d4- - d4+= 30

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

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)

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

C)

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

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

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

*fst53513

P193 7.1 根据下表给定的条件，绘制PERT网络图。 表7-8 作业代号 紧前作业 a1 a2 a3 b1 b2 b3 c1 c2 c3 无 a1 a2 无 b1 b2 a1，b1 a2，b2，c1 a3，b3，c2 解：绘制的PERT网络图为：

表7-9 作业代号 紧前作业 A B C D E F G H I J K L M 无 无 无 A,B B B F,C B E,H E,H C,D,F,J K L,I,G 解：绘制的PERT网络图为：

表7-10 作业代号 紧前作业 A B C D E F G H I J K L M 无 无 B C A,D D A,D E G,H I G J,K L

解：绘制的PERT网络图为：