运筹学期末试题

《运筹学》试题样卷（一）

题号 得分 一 二 三 四 五 六 七 八 九 十 总分 一、判断题（共计10分，每小题1分，对的打√，错的打X）

1. 无孤立点的图一定是连通图。

2. 对于线性规划的原问题和其对偶问题，若其中一个有最优解， 另一个也一定有最优解。

3. 如果一个线性规划问题有可行解，那么它必有最优解。 4．对偶问题的对偶问题一定是原问题。

5．用单纯形法求解标准形式（求最小值）的线性规划问题时，与都可以被选作换入变量。

6．若线性规划的原问题有无穷多个最优解时，其对偶问题也有无穷 多个最优解。

7. 度为0的点称为悬挂点。

8. 表上作业法实质上就是求解运输问题的单纯形法。 9. 一个图G 是树的充分必要条件是边数最少的无孤立点的图。 10. 任何线性规划问题都存在且有唯一的对偶问题。 ① ② ③ ④ ⑤ ⑥ ⑦ ⑧ ⑨ j0对应的变量

二、建立下面问题的线性规划模型（8分）

某农场有100公顷土地及15000元资金可用于发展生产。农场劳动力情况为秋冬季3500人日；春夏季4000人日。如劳动力本身用不了时可外出打工，春秋季收入为25元 / 人日，秋冬季收入为20元 / 人日。该农场种植三种作物：大豆、玉米、小麦，并饲养奶牛和鸡。种作物时不需要专门投资，而饲养每头奶牛需投资800元，每只鸡投资3元。养奶牛时每头需拨出1.5公顷土地种饲料，并占用人工秋冬季为100人日，春夏季为50人日，年净收入900元 / 每头奶牛。养鸡时不占用土地，需人工为每只鸡秋冬季0.6人日，春夏季为0.3人日，年净收入2元 / 每只鸡。农场现有鸡舍允许最多养1500只鸡，牛栏允许最多养200头。三种作物每年需要的人工及收入情况如下表所示：

大豆 玉米 麦子 秋冬季需人日数 春夏季需人日数 年净收入（元/公顷）

试决定该农场的经营方案，使年净收入为最大。

.

20 50 3000 35 75 4100 10 40 4600 .

x,x三、已知下表为求解某目标函数为极大化线性规划问题的最终单纯形表，表中45为

松弛变量，问题的约束为  形式（共8分） x1 x3 5/2 5/2 0 1 0 x2 1/2 －1/2 －４ x3 1 0 0 x4 1/2 －1/6 －４ x5 ０ 1/3 －２ x1 cjzj (1)写出原线性规划问题；（4分） (2)写出原问题的对偶问题；（3分）

(3)直接由上表写出对偶问题的最优解。（1分） 四、用单纯形法解下列线性规划问题（16分）

maxZ2x1x2x3

s. t. 3 x1 + x2 + x3  60

x 1- x 2 +2 x 3  10 x 1+ x 2- x 3  20

x 1, x 2 , x 3 0

五、求解下面运输问题。 （18分）

某公司从三个产地A1、A2、A3 将物品运往四个销地B1、B2、B3、B4，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如表所示： 问：应如何调运，可使得总运输费最小?

B1B2销 地 产 地 B3 B4 产 量 25 25 50 100 A1A2 A310 8 9 15 5 2 3 20 6 7 4 30 7 6 8 35 销 量 六、灵敏度分析（共8分）

线性规划max z = 10x1 + 6x2 + 4x3

s.t. x1 + x2 + x3  100 10x1 +4 x2 + 5 x3  600 2x1 +2 x2 + 6 x3  300 x1 , x2 , x3  0

.

.

的最优单纯形表如下： 6 10 0 x2 x1 x6 j 200/3 100/3 100 0 1 0 0 5/6 1/6 4 –8/3 1 0 0 0 5/3 -2/3 -2 -10/3 – 1/6 1/6 0 – 2/3 0 0 1 0 (1)C1在何范围内变化，最优计划不变？(4分) (2)b1在什么范围内变化，最优基不变？(4分)

七、试建立一个动态规划模型。（共8分）

某工厂购进100台机器，准备生产 p1 , p2 两种产品。若生产产品 p1 ，每台机器每年可收入45万元，损坏率为65%；若生产产品 p2 ，每台机器 每年可收入35万元，损坏率为35%；估计三年后将有新 的机器出现，旧的机器将全部淘汰。试问每年应如何安排生产，使在三年内收入最多？

八、求解对策问题。（共10分）

某种子商店希望订购一批种子。据已往经验，种子的销售量可能为500，1000，1500或2000公斤。假定每公斤种子的订购价为6元，销售价为9元，剩余种子的处理价为每公斤3元。 要求：

（1）建立损益矩阵；（3分）

（2）用悲观法决定该商店应订购的种子数。（2分）

（3）建立后悔矩阵，并用后悔值法决定商店应订购的种子数。（5分）

九、求下列网络计划图的各时间参数并找出关键问题和关键路径。（8分） 1 8 6 2 5 5 3 4 3 7 4 9 7

工序 代号 1-2 .

7 2 3 3 8 6 最晚完 工时间 机动 时间 工序 时间 8 最早完 工时间 最早开 工时间 最晚开 工时间 .

1-3 1-4 2-4 2-5 3-4 3-6 4-5 4-6 4-7 5-7 6-7 7 6 3 5 2 3 3 7 4 9 8

十、用标号法求V1 到 V6 的最短路。（6分） V2 4 3 6 V1 6 5 6 V3 4

V4 8 3 4 V5 V6

.

.

《运筹学》试题样卷（二）

题号 得分

一、判断题（对的打√，错的打X. 共计10分，答在下面的表格中） 1、单纯形法计算中，选取最大正检验数得到最快的减少。

2、单纯形法计算中，如不按最小非负比值原则选出换出变量，则在下一个解中至少有一个基变量的值是负的。

3、对于一个动态规划问题，应用顺推法和逆推法可能会得到不同的最优解。

一 二 三 四 五 六 七 八 九 十 总分 k对应的变量xk作为换入变量，可使目标函数值

x4、应用对偶单纯形法计算时，若单纯形表中某一基变量i都大于或等于零，则其对偶问题具有无界解。

0，且xi所在行的所有元素

5、用位势法计算检验数时，每一行（或列）的位势的值是唯一的，所以每一个空格的检验数是唯一的。

6、动态规划的最短路问题也可以用图论中求最短路问题的方法求解。

7、图论中的图是为了研究问题中有哪些对象及对象之间的关系，它与图的几何形状无关。 8、 动态规划只是用来解决和时间有关的问题。 9、在画网络计划图时，允许有多个起点和多个终点。

10、因为运输问题是一种特殊的线性规划模型，因而求其解也可能出现下列四种情况：有唯一最优解；有无穷多个最优解；无界解；无可行解。 ① ② ③ ④ ⑤ ⑥ ⑦ ⑧ ⑨ 10

二、试建立此问题的数学模型。 （ 8分 ）

某工厂Ⅰ、Ⅱ、Ⅲ三种产品在下一年个季度的合同预定数如下表所示，该三种产品第一季度初无库存，要求在在第四季度末每种产品的库存为150件。已知该厂每季度生产工时为15000小时，生产产品Ⅰ、Ⅱ、Ⅲ每件需3，4，3小时。因更换工艺装备，产品Ⅰ在第二季度无法生产。规定当产品不能按期交货时，产品Ⅰ、Ⅱ每件每迟交一个季度赔偿20元，产品Ⅲ赔偿15元，又生产出来的产品不在本季度交货的，每件每季度的库存费为5元。问应如何安排生产，使总的赔偿加库存费用最小。

.

.

产 品 Ⅰ Ⅱ Ⅲ

季 度 1 1500 1500 1500 2 1000 1500 2000 3 2000 1200 1500 4 1200 1500 2500 三、用单纯形法求解线性规划问题 （ 16分 ）

Max Z = 1500 x1 + 2500 x2 s.t. 3x1 + 2 x2

 65

2 x1 + x2  40 3x2  75 x1, x2  0

四、写出下面线性规划的对偶问题 ( 8分 )

minzx1x22x3

2x1x22x372x3xx51233x15x24x33x1,x20,x3无约束；

五 、求解下面运输问题。 （ 18分 ）

某公司从三个产地A1、A2、A3 将物品运往四个销地B1、B2、B3、B4，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如表所示 销 地 产 地 B1 A1 A2 A3 B2 B3 B4 产 量

3 1 7 3 11 9 4 6 3 2 10 5 10 8 5 6 7 4 9 20

销 量 问：应如何调运，可使得总运输费最小?

六、灵敏度分析（ 8分 ）

.

.

线性规划

maxz4x1x25x3

的最终单纯形表如下： 6x13x25x3453x14x25x330x,x,x0123

cj CB 4 5 4 1 5 0 0 XB x1 x3 j b 5 3 x1 １ 0 0 x2 －1/3 1 －8/3 x3 0 1 ０ x4 1/3 －1/5 －１/3 x5 －1/3 2/5 －2/3 x1的系数C1在什么范围变化，上述最优解不变？（4分） （1）

（2）b2在什么范围变化，最优基不变？（4分）

七、建动态规划模型。（8分）

某公司拥有资金 10 万元，若投资于项目 i (i＝1，2，3) 的投资额为 xi 时，其收益分别为 g1(x1)=4x1 , g2(x2)=9x2 , g3(x3)=2x32 ,问应如何分配投资数额才能使总收益最大?

八、解决对策问题。（10分）

根据已往的资料，一家超级商场每天所需面包数（当天市场需求量）可能是下列当中的某一个：100，150，200，250，300，但其概率分布不知道。如果一个面包当天卖不掉，则可在当天结束时每个0.5元处理掉。新鲜面包每个售价1.2元，进价0.9元，假设进货量在需求量中的某一个，要求

（1）建立面包进货问题的损益矩阵；（3分） （2）用乐观法确定进货量。（2分）

（3）建立后悔矩阵，并用后悔值法确定进货量。（5分）

.

.

九、用双标号法求下列图中V1到V9的最短路线及其长度。（ 6分 ） 1VV5 8 V63 V2

4

2

3 4 1 3 2 V7V9

3

V4 3 2

V81

V3

十、下图是商业中心建设项目的网络计划图，请用标号法计算出表中的各个参数，最后指出关键问题，并画出关键线路。 （8分，直接答在下面） 6 14 G 10 7 H 6 8 12 A 1

20 10 F 8 I 9 6 B 2

3 C 4 24 D 5 8 E J 10

工序时间 开工时间 最早 最晚 完工时间 最早 最晚 机动时间 A （20） B （10） C （8） D （24） E （8） .

.

F （14） G （10） H （6） I （12） J （6）

运筹学样卷（一）

答案

一、 ① X

二、建线性规划模型。共计8分（酌情扣分）

解：用x1,x2,x3分别表示大豆、玉米、麦子的种植公顷数；x4,x5分别表示奶牛和鸡的饲养数；x6,x7分别表示秋冬季和春夏季的劳动力（人日）数，则有

② √ ③ X ④ √ ⑤ √ ⑥ √ ⑦ X ⑧ √ ⑨ X 10 √ 判断题。共计10分，每小题1分

maxZ3000x14100x24600x3900x420x520x625x7

三、对偶问题。共计8分

100(土地)x1x2x31.5x4400x43x515000(资金)20x135x210x3100x40.6x5x63500(劳动力)50x1175x240x350x40.3x5x74000(劳动力)x4200(牛栏)x51500(鸡舍)x0(j1,2,,7)j

z6x12x210x3

解：（１）原线性规划问题：maxx22x253x1x2x310x,x02 1 ；……4分

（２）原问题的对偶规划问题为：

minw5y110y2

.

.

3y26

yy212

2y1y210

y1,y20 ； ……3分

Y(4,2)T 。……1分 （３）对偶规划问题的最优解为：

四、单纯形表求解线性规划。共计16分 解：引入松弛变量x4、 x5、 x6，标准化得，

maxZ2x1x2x3

s. t. 3 x1 + x2 + x3+ x4 = 60

x 1- x 2 +2 x 3 + x5 = 10 x 1+ x 2- x 3 + x6 = 0

x 1, x 2 , x 3， x4、 x5、 x6，≥0……………3分

建初始单纯形表，进行迭代运算： ……………………… …9分

CB 0 0 0 1 0 2 0 2 0 2 -1 3 x4 x1 x2 x4 x1 x6 Xb x4 x5 x6 b’ 60 10 20 0 30 10 10 20 10 15 5 25 2 x1 3 [1] 1 2* 0 1 0 0 0 1 0 0 -1 x2 1 -1 1 -1 4 -1 [2] 1* 0 0 1 0 1 x3 1 2 -1 1 -5 2 -3 -3 1 0.5 -1.5 -1.5 0 x4 1 0 0 0 1 0 0 0 1 0 0 0 0 x5 0 1 0 0 -3 1 -1 -2 -1 0.5 -0.5 -1.5 0 x6 0 0 1 0 0 0 1 0 -2 0.5 0.5 -0.5 θ 20 10* 20 7.5 --- 5* 由最优单纯形表可知，原线性规划的最优解为： ( 15 , 5 , 0 )T …2分

最优值为： z*=25。………2分

.

.

五、求解运输问题。共计18分 解：

（1）最小元素法：（也可以用其他方法，酌情给分） 设xij为由Ai运往Bj的运量（i=1,2,3; j=1,2,3,4）, 列表如下：

销 地 B1 B2 B3 B4 产 地 1 2 3 销 量 15 15 20 20 30 30 25 5 5 35 产 量 25 25 50 100 ……………3分

所以，基本的初始可行解为：x14 =25； x22=20 ； x24 =5 ；

X31 =15； x33 =30； x34=5

其余的xij=0。 …………3分

（2）求最优调运方案：

1会求检验数，检验解的最优性：11=2；12=2；13=3；

21=1；23=5；32= - 1…………3分

2会求调整量进行调整：=5 …………2分

销 地 B1 B2 B3 B4 产 量 产 地 1 2 3 销 量 15 15 15 5 20 30 30 25 10 35 25 25 50 100 …3分

3再次检验 …………2分

4能够写出正确结论

解为：x14=25 ； x22 =15 ； x24 =10 x31 =15， x32 =5 x33=30

其余的xij=0。 ……1分

最少运费为： 535 ………1分。

六、灵敏度分析。共计8分 （1）（4分） 8/32/310/3max,cmin 11/61/62/3

4c15,6104c1c110515

（2）（4分）

.

.

200/3100/3100max,bmin,15/32/3240b110

七、建动态规划模型。共计8分

解：(1)设阶段变量k表示年度，因此，阶段总数n=3。

(2)状态变量sk表示第k年度初拥有的完好机床台数， 同时也是第 k–1 年度末时的完好机床数量。

(3)决策变量uk，表示第k年度中分配于生产产品 p1 的机器台数。于是sk– uk便为该年度中分配于生产产品 p1的机器台数． （4） 状态转移方程为

sk10.35uk0.65(skuk)（5）允许决策集合,在第 k 段为 U(s){u0us}kkkkk（6）目标函数。设gk(sk,uk)为第k年度的产量，则

gk(sk,uk) = 45uk + 35(sk–uk) ,

因此，目标函数为 3 Rg(s,u) kikkkk（7）条件最优目标函数递推方程。

f(s)max(u(s))kkkkukUk

令fk(sk)表示由第k年的状态sk出发，采取最优分配方案到第3年度结束这段时间的产品产量，根据最优化

原理有以下递推关系： {[45 uk35(skuk)]fk1[0.35uk0.65(skuk)]}（8）.边界条件为

f31(s31)0

八、解决对策问题。共10分

（1）益损矩阵如下表所示：……3分

销 售 S1 S2 S3 S4 订 购 500 1000 1500 2000 A1 500 A2 1000 A3 1500 A4 2000 1500 0 －1500 －3000 1500 3000 1500 0 1500 3000 4500 3000 1500 3000 4500 6000 （2）悲观法：A1 ，订购500公斤。……2分 （3）后悔矩阵如下表所示：……3分

S1 S2 S3 S4 A1 A2 A3 0 1500 3000 1500 0 1500 3000 1500 0 4500 3000 1500 最大后悔值 4500 3000 3000 A4 4500 3000 1500 0 4500 按后悔值法商店应取决策为A2或A3 ，即订购1000公斤或1500公斤。……2分

.

.

九、求网络计划图的各时间参数。（8分） 8 0 85 2

8 3 11 0 0 6 1 4

0 11 7 2 3

7 3 9

工序 代号 1-2 1-3 1-4 2-4 2-5 3-4 3-6 4-5 4-6 4-7 5-7 6-7 工序 时间 8 7 6 3 5 2 3 3 7 4 9 8 最早开 工时间 0 0 0 8 8 7 7 11 11 11 14 18 最早完 工时间 8 7 6 11 13 9 10 14 18 15 23 26 最晚开 工时间 0 2 5 8 9 9 15 11 11 22 17 18 14 14 5 3 9 7 4 26 0 8 6 187 18 26 0 机动 时间 0 2 6 0 1 2 8 0 0 11 3 0

最晚完 工时间 8 9 11 11 14 11 18 14 18 26 26 26 关键问题是：①→②；2→④；④→⑤；④→6；6→⑦ 关键线路是： 1

评分标准：①能正确给各顶点标号并填表......................4分

②正确写出关键问题.............. 2分

③正确画出关键线路............. ２分

.

2 4 1 6 7 .

十、用标号法求v1 到 v6 的最短路。（6分）

(4,v1)

V2 6

4 7

(0,0) V1 2

8 3 V3 (6,v2) 7

（8,v1）

最短路为：v1,v2,v3,v4,v5,v6 长度为：12

正确标号：4分；正确写出结论：2分

V4 (9,v3) (10,v2) 5 1 V6 (12,v5) (14,v4) 2 V5 (10,v4) (11,v2) (13,v3)

运筹学样卷(二)答案

二、 ① X

二、建线性规划模型。（8分）（酌情给分）

② √ ③ X ④ X ⑤ X ⑥ √ ⑦ √ ⑧ X ⑨ X 10 X 判断题。（共计10分，每小题1分）

xs解：设ij为第i个季度生产的产品j的数量；ij为第i个季度末需库存的产品j的数量；tij为第i个季度不能交货的产品j的数量；yij为第i个季度对产品j的预定数量，则有：

minZ20(ti1ti2)15ti35siji1i1j1433

.

.

xi1xi2xi315000(i1,2,3,4)x02144xijyij150(j1,2,3)i1i1iixkjtijsijykj(i1,2,3,4;j1,2,3)k1k1xij,sij,tij0

三、求解线性规划。（16分）

解：引入松弛变量x3, x4, x5，标准化得，

Max Z = 1500X1 + 2500X2 s.t. 3 x1 + 2x2 + x3 = 65

2x1 + x2 + x4 = 40 3 x2 + x5 =75

x1, x2 ≥0 ………………3分

建初始单纯形表，进行迭代运算：…………………………9分

CB 0 0 0 Xb x3 x4 x5 1 0 0 x3 x4 b’ 65 40 75 0 15 15 25 1500 x1 3 2 0 1500 [3] 2 0 2500 x2 2 1 [3] 1 x3 1 0 0 0 x4 0 1 0 0 0 1 0 0 1/3 0 -2/3 0 1 0 0 x5 0 0 1 0 -2/3 -1/3 1/3 32.5 40 2.5* 5* 7.5 ---- θ 2500* 0 0 0 1 1 0 0 0 2500 x2 2 1500 x1 0 x4 62500 1500* 0 5 5 25 1 0 0 0 0 1 -2500/3 -2/9 1/9 1/3 2500 x2 .

.

3 70000 0 0 -500 0 -500 由最优单纯形表可知原线性规划的最优解为： ( 5, 25 , 0, 5 , 0 )T …2分

最优值为： z*=70000。………2分

四、解：原问题的对偶规划问题为：（共8分）

Max f=7y1+5y2+3y3

五、求解运输问题。（18分） 解：（1）最小元素法：

2y12y23y31y3y5y11232y1y24y32y10,y2无约束，y30

设xij为由Ai运往Bj的运量（i=1,2,3; j=1,2,3,4）, 列表如下： 销 地 B1 B2 B3 B4 产 地 1 2 3 销 量 3 3 6 6 4 1 5 3 3 6 产 量 7 4 9 20 ……………3分

所以，基本的初始可行解为：x13=4 ； x14 =3 ；

x21 =3 x23 =21 x32 =6 x34=3

其余的xij=0。 …………3分

（2）求最优调运方案：

111,122,221,1会求检验数，检验解的最优性：241,3110,3312…………3分

2会求调整量进行调整：1 …………2分

销 地 B1 B2 B3 B4 产 地 1 2 3 销 量 3 3 6 6 5 5 2 1 3 6 产 量 7 4 9 20 …………3分

.

.

3再次检验 …………2分

4能够写出正确结论

解为：x13=5 ； x14 =2 ； x21 =3 x24 =1， x32 =6 x34=3

其余的xij=0。 …………1分

最少运费 f351021381465385………1分

六、灵敏度分析。（8分） （1）（4分） 1/38/32/3maxcmin, 11/31/31/3

1c12,341c1c1426

（2）（4分） 35max, b2min2/51/3

7.5b215

七、建动态规划模型。（8分）

1．分阶段：设阶段变量 k 表示依次对第 k 个项目投资，因此，阶段总数 n = 3。 ( k = 1 , 2 , 3 )

2. 状态变量：用 sk 表示已经对第 1 至第 k-1 个项目投资后的剩余资金；即第 k

段初拥有的可以分配给第 k 到第3个项目的资金额 （单位：万元） 。

3. 决策变量：用 xk 表示对第 k 个项目投资 的资金数量（单位：万元）。 4．状态转移方程为：

sk1skxk

５．决策变量的取值： 0  xk  sk 6. 基本方程为：

最优指标函数 fk(sk) 表示第 k 阶段，初始状态为 sk 时，从第 k 到第 3 个

项目所获最大收益

{gk(xk)fk1(sk1)} fk(sk)0maxxs

八、解决对策问题。（10分）

（1）益损矩阵如下表所示：……3分

.

k3,2,1f4(s4)0kk.

销 售 进 货 A1 100 A2 150 A3 200 A4 250 A5 300 S1 100 30 10 －10 －30 －50 S2 150 30 45 25 5 －15 S3 200 30 45 60 40 20 S4 250 30 45 60 75 55 S5 300 30 45 60 75 90

（2）乐观法（最大最大）：A5 ，订购300个；……2分

（3）后悔值法：后悔矩阵如下表所示：……3分

S1 S2 S3 S4 S5 A1 A2 A3 A4 A5 0 20 40 60 80 15 0 20 40 60 30 15 0 20 40 45 30 15 0 20 60 45 30 25 0 最大后悔值 60 45 40 60 80 A3 ，订购200个。……2分

九、最短路问题。（6分） (0, 0) V1

(VV 1,4 ) V5 (V 2, 7 ) 23 3 2 4 8 V6(V 2，7 ) 3 (V7 ,8) 4 V9 3 1 (V 3,6 ) V72 V4(V2,6) ) 3 1 2 V8(V 7 , 8 ) V3(V 1,3 )

由V1到V9的最短路线为: V1→V3→ V7→V9．

最短路线长为：8

评分标准：正确标号：4分；正确写出结论：2分

十、网络计划问题。共8分

工序(时间) 开工时间

完工时间 机动时间 .

.

最早 A （20） B （10） C （8） D （24） E （8） F （14） G （10） H （6） I （12） J （6） 0 0 20 28 52 20 34 52 58 70 最晚 0 10 20 28 62 28 42 52 58 70 最早 20 10 28 52 60 34 44 58 70 76 最晚 20 20 28 52 70 42 52 58 70 70 0 10 0 0 10 8 8 0 0 0 关键问题是：A ,C ,D ,H , I， Ｊ

关键线路是：①→②．．．→．③→④→⑤．．．→⑦→⑧→⑨→⑩ 评分标准：①能正确给各顶点标号并填表......................4分

②正确写出关键问题.............. 2分

③正确画出关键线路............. ２分

.