《运筹学》试卷
一、单项选择题(1⨯5分）
1. 线性规划(以下简称LP) 模型中自由变量可以用两个非负变量之（ ）代换。 A．和 B．差 C．积 D．商
2.LP 原问题的第i 个约束条件是“=”型，则对偶问题的变量y i 是（ ）。 A．剩余变量 B．自由变量 C．松弛变量 D．非负变量
3. 基可行解中的非零变量的个数小于约束条件数时，该LP 问题可求得( ）。 A．基本解 B．多重解 C．退化解 D．无解 4. 运筹学中著名的“TSP 问题”是指 ( ) 。
A.背包问题 B.中国邮递员问题 C.哥尼斯堡七桥问题 D.货郎担问题 5. 用大M 法求解极大化的LP 问题时，人工变量在目标函数中的系数是（ ）。 A. -M B. M C. 1 D. -1
二、判断正误（对者打“√”，错者打“×”。1⨯5分）
1.线性规划问题的最优解不一定只在可行域的顶点上取得。 （ ） 2. 对偶单纯形法是求解线性规划对偶问题的一种算法。 （ ）
3. 容量网络中从发点到收点的最大流流量等于分离发点和收点的任一割集的容量。（ ） 4. 若整数规划问题存在可行解，则其可行解集合是凸集。 （ ） 5. 目标规划模型中可以没有绝对约束，但不能没有目标约束。 （ ）
三、(25分) 某企业生产3种产品，这些产品均需使用A 、B 两种原料，每种产品的原料单耗(kg/件) 、单位利润以及这两种原料在计划期内的可供应量(kg)如下表。该企业应如何安排3种产品生产，可使企业所获利润最大？
要求：
1.建立该问题的线性规划模型；（3分） 2. 用单纯形法求该问题的最优解及最优值；（15分）
3.产品Ⅲ的单位利润在什么范围内变动时，最优解不变？（3分） 4. 直接写出该LP 的对偶问题及其最优解。（4分）
四、(10分) 某家电厂商生产A 、B 、C 三种规格的某种家电产品，装配工作在同一生产线上完成，三种产品装配时的工时消耗分别为2小时、2.5小时和3小时，生产线每月正常工作时间为480小时；三种产品销售后，每台获利分别为150、180和200元；每月销售量预计分别为90、70和50台。该厂经营目标如下：
P 1：根据三种产品的需求变动趋势，产品A 按预计销量生产、产品B 的产量不超过预计销量、产品C 的产量不低于预计销量为宜； P 2：利润指标为每月不低于3万元； P 3：充分利用生产线的正常工作时间；
P 4：产品旺销时可以适当加班，但每月加班时间不宜超过40小时。 试根据上述资料建立该家电厂商产品生产计划的目标规划模型。（不求解）
五、（15分）指派5位员工去完成5项不同的工作，每人做各项工作所需时间（单位：天）如下表所示。试用匈牙利法求最优指派方案及最少总时间。
六、（10分）有总量为a 和b 的两种资源，可用于n 种产品的生产。如果第一种资源以数量x i 、第二种资源以数量y i 分配于第i 种产品的生产，其收益为g(x i , yi ) , (i=1,2,…,n)。如何分配这两种资源于n 种产品的生产活动可使总收益最大？试建立该问题的动态规划模型(不求解) 。
（提示 建立动态规划模型包括：确定解法(顺序或逆序) ；划分阶段；定义状态变量、状态集合、决策变量、允许决策集合、状态转移方程、阶段指标、最优指标函数；写出动态规划基本方程） 七、（15分）用Ford-Fulkerson 算法求图1中容量网络的最大流和最小割集。图中弧旁的数字表示(c ij ，f ij ) 。 （提示 求解过程应写出，并在图上做相应的标记。一个可行流用一张图表示）
图1
八、 (15分)
已知产销平衡运输问题表1所示。试检验表1中的基可行解是否是最优解。如不是，用闭回路法对表中的解进行调整，求出最优解及最小总运费。 （提示 应简要写出求解过程，并将有关数据填入表中。一个基可行解用一张表表示）
v v t
《运筹学》试卷
一、单项选择题(1⨯5分）
1.B 2.B 3.C 4.D 5.A 二、判断正误（对者打“√”，错者打“×”。1⨯5分） 1.√ 2. × 3. × 4. × 5.√ 三、(25分）解:
1. (3分）设产品Ⅰ、Ⅱ、Ⅲ在计划期内产量分别为x 1、x 2 、x 3，由题意，该问题的LP 模型为：
max z =20x 1+15x 2+18x 3
⎧2x 1+3x 2+4x 3≤100
⎪
s . t . ⎨4x 1+2x 2+3x 3≤80⎪x ≥0, j =1, 2, 3⎩j
2.(15
:
*
*
T
∴ 换入换出:
∵∀σj ≤0，∴得最优解:X =(5,30,0,0,0)，最优值z =550
3. ∵x 3是非基变量，故当σ3’≤0，即∆c 3 ≤-σ3=13/4，亦即c 3’ ≤85/4时，原最优解仍是最优解。 4. 对偶问题为：min w = 100y1 + 80y2 2y 1+4y3 ≥20 3y 1 +2y2 ≥ 15 4y 1 +3y2 ≥ 18 y 1, 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 三种产品的产量分别为x 1, x 2, x 3，由题意，该问题的GP 模型
为:
--+
min{P 1(d 1++d 1-+d 2+d 3+), P 2d 4, P 3d 5-, P 4d 6}
⎧x 1+d 1--d 1+=90⎪-+
x 2+d 2-d 2=70⎪⎪-+
x +d -d =50333⎪ ⎪-+
s . t . ⎨150x 1+180x 2+200x 3+d 4-d 4=30000⎪-+2x +2. 5x +3x +d -d 2355=480⎪1
-+⎪d 5++d 6-d 6=40
⎪-+x ≥0, j =1, 2, 3, d , d ≥0, i =1, , 6⎪j i i ⎩
评分标准: 正确设定决策变量: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元素:
→ ’’
C ’中只有4个独立0元素，需要继续变换:用最少直线数覆盖所有0元素，未被直线覆盖的元素中的最小元素是2，则未被直线覆盖的行中每个元素-2, 被直线覆盖的列中每个元素+2，得到C’’。 圈出C ’’
已得到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 种产品的第一种资源数;
k k k k
Y ：分配用于生产第k 至第n 种产品的第二种资源数。 k
(4)状态集合: S1=(a,b)，S n+1=(0，0), (0，0) ≤S k ≤(a,b)，k=2,3,…,n
(5)决策变量u =(x ，y ) ，其中x :用于第k 种产品生产的第一种资源数, y: 用于第k 种产品生
k k k k k
产的第二种资源数。
(6)允许决策集合: D(X,Y )={(x ，y )|0≤ x ≤X ，0 ≤y ≤Y }, k=1,2,…,n
k k k k k k k k k
(7)状态转移方程：X = X- x , Y= Y-y ，k ＝1,2,…,n
k+1k k k+1k k
(8)阶段指标: gk (x k ,y k ) ，k ＝1,2,…,n
(9)最优指标函数f(Xk ,Y k ) 表示表示当分配于第k 种产品至第n 种产品两种资源数量为X 和Y 时
k k
的最大收益。 (10)DP基本方程为：
⎧f k (X k , Y k ) =max {g k (x k , y k ) +f k +1(X k -x k , Y k -y k ) }k=n,n-1,…,2,1 ⎪0≤x k ≤X k
0≤y k ≤Y K ⎨
⎪f (s ) =0⎩n +1n +1
评分标准: (1)～(10) 项每项1分.
七、(15分）解:
(1)标号过程：先给v s 标以(0，+∞) 。检查v s 的相邻未标号点，发现v 1、 v 2符合标号条件，故给v 以标号(vs ,min ｛+∞,cs1-f s1｝)=(vs ,2) ；给v 2以标号( v s ,min ｛+∞,cs2-f s2})= (vs ,2) 。继续标号
1
过程，给v 以标号(v2,min ｛2,c 23-f 23｝)=(v2,2) ；给v t 以标号(v,min ｛2, c 3t –f 3t })= (v,2) 。至此
333
v t 已得到标号，说明存在一条可增广链：v →v →v →v ，如图1。转调整过程。
s 23t
(0, (vs ,2)
(2)调整过程：沿可增广链调整流量，调整量δ=δv t =2，即令可增广链上所有前向弧的流量增加2。调整后得到的可行流如图2：
(3) 重新标号：去掉所有标号，对新的可行流重新标号。
给v s 标（0,+∞）, 给v 1以标号( vs ,min ｛+∞,cs1-f s1})= (vs ,2) 。至此标号进行不下去，而v t 未得到标号，说明图中的流已是最大流。最大流量w (f * ) =f4t +f3 t=16。
最小割集S , S ={(v s ,v 2),(v1,v 3) ,(v1,v 4)}, 如图2中的虚线所示。最小割集的容量为：c(S,Ŝ)=cs1+
(,2)
v t
()
v
v t
c 13+c14=10+3+3=16, 与最大流的流量相等。 评分标准: (1)、(2)、（3）、图1、图2各3分。若算法步骤和图不完整, 可适当扣分。
八、(15分）解: 闭回路法求得表中基可行解的非基变量的检验数，填入表1中空格的左下角。 ∵σ11
用闭回路法对表中的解进行调整，闭回路为：（x 11）—x 12—x 22—x 21—（x 11），调整量为min{x 12，x 21}=10，调整后得到一个新的基可行解, 如表2。
再用闭回路法求得表2中基可行解的非基变量的检验数，填入表2中空格的左下角。∵∀σij >0，∴表2中的解即为问题的最优解。
最小总运费z=4⨯10+2⨯50+3⨯30+2⨯45+2⨯70+4⨯20=540。
评分标准: 两个表中的基可行解的检验和解的调整各5分。个别数据错误酌情扣分。