《运筹学》试卷09-答案

一、单项选择题(15分）

1.B 2.B 3.C 4.D 5.A 二、判断正误（对者打“√”，错者打“×”。15分） 1.√ 2. × 3. × 4. × 5.√ 三、(25分）解:

1. (3分）设产品Ⅰ、Ⅱ、Ⅲ在计划期内产量分别为x1、x2 、x3，由题意，该问题的LP模型为：

maxz20x115x218x3

2x13x24x3100 s.t.4x12x23x380x0,j1,2,3j2.(15分）在约束中分别添加松弛变量x4、x5将LP化为标准形式，列单纯形表求解:

cj CB XB 20 15 18 0 0 x1 x2 x3 x4 x5 b 100 80 0 60 20 -400 30 5 -550  50 20 x4 2 3 4 1 0 0 x5 [4] 2 3 0 1 0 j 20 15 18 0 0 ∴ x1换入、 x5 换出:

50 x4 0 x1 j 50 x2 x1 40 j

0 [2] 5/2 1 -1/2 1 1/2 3/4 0 1/4 0 5 3 0 -5 0 1 5/4 1/2 -1/4 1 0 1/8 -1/4 1/8 0 0 -13/4 -5/2 -15/4 *

T

*

30 40 ∴ x2换入、 x4 换出:

∵j0，∴得最优解:X=(5,30,0,0,0)，最优值z=550

3.∵x3是非基变量，故当3’0，即c3 -3=13/4，亦即c3’ 85/4时，原最优解仍是最优解。 4.对偶问题为：min w = 100y1 + 80y2 2y1+4y3 20 3y1 +2y2  15 4y1 +3y2  18

y1, y2  0

对偶问题最优解：Y*=( 5/2,15/4)T，最优值w*=550 评分标准:

1.正确设定决策变量:1分；正确列出LP模型:2分。

2.化标准形式、答案各1分，第1张单纯形表3分, 第2,3张单纯形表各5分； 3.3分。

4.正确列出对偶问题模型:3分；最优解1分。 个别数据错误酌情扣分。

四、(10分)解: 设计划期内A、B、C三种产品的产量分别为x1,x2,x3，由题意，该问题的GP模型为:

min{P1(d1d1d2d3),P2d4,P3d5,P4d6}x1d1d190x2d2d270xdd50333 s.t.150x1180x2200x3d4d4300002x2.5x3xdd48012355d5d6d640x0,j1,2,3,d,d0,i1,,6jii评分标准: 正确设定决策变量:2分；正确列出目标规划模型:8分。个别条件列错酌情扣分。

9 4 6 4 65 0 2 0 25 6 3 5 32 3 0 2 014 9 11 90 10 5 7 5C' 五、(15分）解: 化简系数矩阵:C4 12 11 4 3 79 8 1 0 42 8 5 8 40 6 3 6 2圈出C’中的独立0元素: 5  2  2 2 3  2   10 5 7 5 9 8 1  4  6 3 6 2   

5  2  2 2 3  2   10 5 7 5 -2 → 9 8 1  4  6 3 6 2 -2 +2 7 0 2 0 2 4 3 0 2 0 0 8 3 5 3 =C’’ 11 8 1 0 4 0 4 1 4 0

C’中只有4个独立0元素，需要继续变换:用最少直线数覆盖所有0元素，未被直线覆盖的元素中的最小元素是2，则未被直线覆盖的行中每个元素-2, 被直线覆盖的列中每个元素+2，得到C’’。 圈出C’’中的独立0元素: 7  2  2 4 3  2   8 3 5 3 11 8 1  4  4 1 4 

已得到5个独立0元素。∴最优指派方案为: I做B工作；II做C工作；III做A工作；IV做D工作；V做E工作。总耗时为4+3+4+3+4=18（天）。

评分标准: 变换系数矩阵得到C’：3分；进一步变换系数矩阵得到C’’：7分；圈出5个独立0元素、给出最优指派方案：5分。个别数据错误酌情扣分。 六、(10分)解:建立该问题的动态规划模型如下: (1)采用逆序解法(顺序解法亦可);

(2)阶段：按产品划分阶段,每种产品为一个阶段，k＝1,2,…,n

(3)状态变量状态变量s＝(X,Y)，其中：X：分配用于生产第k至第n种产品的第一种资源数;

kkkk

Y：分配用于生产第k至第n种产品的第二种资源数。 k

(4)状态集合: S1=(a,b)，Sn+1=(0，0), (0，0)Sk(a,b)，k=2,3,…,n

(5)决策变量u=(x，y)，其中x :用于第k种产品生产的第一种资源数, y: 用于第k种产品生产

kkkkk

的第二种资源数。

(6)允许决策集合: D(X,Y)={(x，y)|0 xX，0 yY}, k=1,2,…,n

k

(7)状态转移方程：Xk+1= Xk- xk , Yk+1= Yk-yk，k＝1,2,…,n

kkkkkkkk

(8)阶段指标: gk (xk,yk) ，k＝1,2,…,n

(9)最优指标函数f(Xk,Yk)表示表示当分配于第k种产品至第n种产品两种资源数量为Xk和Yk 时的最大收益。 (10)DP基本方程为：

fk(Xk,Yk)maxgk(xk,yk)fk1(Xkxk,Ykyk)k=n,n-1,…,2,1 0xkXk0ykYKf(s)0n1n1评分标准: (1)～(10) 项每项1分.

七、(15分）解:

(1)标号过程：先给vs标以(0，+∞)。检查vs的相邻未标号点，发现v1、 v2符合标号条件，故给v以标号(vs,min｛+∞,cs1-fs1｝)=(vs,2)；给v2以标号( vs,min｛+∞,cs2-fs2})= (vs,2)。继续标号过

1

程，给v以标号(v2,min｛2,c23-f23｝)=(v2,2)；给vt以标号(v,min｛2, c3t –f3t})= (v,2)。至此vt已

333

得到标号，说明存在一条可增广链：v→v→v→v，如图1。转调整过程。

s23t

v1 (8,6) (0, +∞) (vs,2)

(3,3) (3,3) v3 (v,2)

2

(8,5) (v,2)

vs (10,8) (6,0) (5,2) v3 (9,9) 3vt

(2)调整过程：沿可增广链调整流量，调整量δ=vt=2，即令可增广链上所有前向弧的流量增加2。调整后得到的可行流如图2：

(3) 重新标号：去掉所有标号，对新的可行流重新标号。

给vs标（0,+∞）, 给v1以标号( vs,min｛+∞,cs1-fs1})= (vs,2)。至此标号进行不下去，而vt未得到标号，说明图中的流已是最大流。最大流量w(f * ) =f4t+f3 t=16。

最小割集S,S={(vs,v2),(v1,v3) ,(v1,v4)},如图2中的虚线所示。最小割集的容量为：c(S,Ŝ)=cs1+ c13+c14=10+3+3=16, 与最大流的流量相等。

(vs,2) (6,6) v2 图1 (vs,2) 图1

v1 (3,3 ) (3,3) v3 (8,7) (6,0) (8, 6 ) (0,+∞） vs (10,10) v2 vt

(5,4) (6,6) 图 2 图1 (9,9) v4 评分标准: (1)、(2)、（3）、图1、图2各3分。若算法步骤和图不完整,可适当扣分。 八、(15分）解: 闭回路法求得表中基可行解的非基变量的检验数，填入表1中空格的左下角。 ∵11<0，∴表中基可行解不是最优解。

表1 销地 产地 B1 -2 4 B2 5 B3 3 5 3 B4 2 7 产量 60 75 90 A1 A2 A3 需求量 10 2 50 8 2 40 0 3 8 35 8 7 4 0 70 45 70 20 70 40 用闭回路法对表中的解进行调整，闭回路为：（x11）—x12—x22—x21—（x11），调整量为min{x12，x21}=10，调整后得到一个新的基可行解,如表2。

表2 销地 产地 B1 B2 5 B3 3 5 B4 2 7 产量 60 75 90 A1 A2 A3 需求量 4 10 2 3 2 6 7 50 6 2 30 2 3 8 2 45 4 70 45 70 20 70 40 再用闭回路法求得表2中基可行解的非基变量的检验数，填入表2中空格的左下角。∵ij>0，∴表2中的解即为问题的最优解。

最小总运费z=410+250+330+245+270+420=540。

评分标准: 两个表中的基可行解的检验和解的调整各5分。个别数据错误酌情扣分。