运筹学期末试题2答案

北京林业大学20 07 --20 08 学年第 二 学期考试试卷

试卷名称： 运筹学 （A） 课程所在学院： 理学院 考试班级 学号 姓名 成绩 试卷说明：

1. 本次考试为闭卷考试。本试卷共计 4 页，共 三 大部分，请勿漏答； 2. 考试时间为 120 分钟，请掌握好答题时间；

3. 答题之前，请将试卷和答题纸上的考试班级、学号、姓名填写清楚； 4. 本试卷所有试题答案写在 试卷 纸上；（特殊要求请详细说明） 5. 答题完毕，请将试卷交回，不得带出考场；

6. 考试中心提示：请你遵守考场纪律，参与公平竞争！一、填空题（每小题3分，共30分）

maxz2x13x2

1.线性规划问题

4x12x215的标准形式：4x12x2x315。 s.t.x1x25s.t.x1x2x45x,x0x,x,x,x0121234maxz2x13x2

4x12x215用两阶段方法求解辅助问题为：4x12x2x315。 s.t.x1x25s.t.x1x2x4x55x,x0x,x,x,x0121234

mingx5

minz,2x13x2

2.线性规划问题

3.线性规划问题中原问题的约束的个数和对偶问题的 变量 的个数相同。

4.求解混合整数规划问题的常用方法： 分支定界方法 。

mincTx

5.x1为s.t.Axb的可行解，y1为其对偶问题的可行解，则cTx1bTy1（大小关系）。

x0

0

6．给出图



11

1

0110

01

1101

0

1。 11

1101010

7.一个图共有5个点，它们的次分别为3、3、4、2、5，这是否可能？ 不可能 。

8. 某超市有一个收款台，顾客到来交款服从最简单流，平均每10分钟6人，收款台服务时间服从负指数分布，平均每10分钟完成9人。该问题属于哪一类型的排队问题： M/M/1/∞ 。 9.根据对状态的了解程度对决策分析问题进行分类，可分为：确定型、风险型、不确定型决策问题 。

1q6

10.矩阵对策p510的平衡局势值为5，则p,q的取值范围为：p5,q5。 623

maxz3x13x2x3

11.（15分）线性规划问题

（2）写出原4x12x2x317（1）用单纯形方法求最优解最优值；



s.t.x1x2x34

x,x,x0

123

问题的对偶问题；（3）利用（1）的结果以及对偶理论写出互补松紧条件并以此求对偶问题的最优解

最优值。 解：（1）

原问题的最优解：x=(4,0,0),最优值：z=12。

min17w14w2

4w1w23（2）原问题的对偶问题：

2w1w23 s.t.

w1w21w1,w20

4w1w23w23

（3）互补松紧条件： 

w0w011

对偶问题最优解:(0,3),最优值：12。

12.（10分）从A 地到E 地要铺设一条煤气管道,其中需经过三级中间站，两点之间的连线上的数字表示距离（单位为千米），如图所示。问应该选择什么路线，使总距离最短？最短距离为多少？（用动态规划方法求解） 解：

最优路线为AB2C1D1E，最短距离为19千米。

13.（12分）某城市建设了一个从湖中抽水到城市的蓄水池的管道系统如图，线上标注的数字是单位时间通过两节点的流量。试求单位时间由湖到蓄水池的最大流量(单位：吨)。 解：

最大流量为7吨。

14.（15分）某工厂面对激烈的市场竞争，拟制定利用先进技术对产品改型的计划。现有三个改型方案可供选择：d1、d2、d3。根据市场需求调查，该厂产品面临高需求、一般需求与低需求三种自然

0.5，0.3，0.2。下表给出了预期收益的情况：

（1） 用期望值方法进行决策； （2） 用决策树模型进行决策；

（3） 如果求助于咨询公司求完全信息的价值。 解：（1）E(d1)=40×0.5+20×0.3+10×0.2=28 E(d2)=70×0.5+30×0.3+0×0.2=44

E(d3)=110×0.5+10×0.3+(-50)×0.2=48,应该选d3。 （2）

（3）完全信息的价值：110×0.5+30×0.3+10×0.2-48=18。

15.（10分）甲、乙二人游戏，每人出一个或两个手指，同时又把猜测对方所出的手指数叫出来。如果只有一个人猜正确，则他赢得的数目（由对方付给）为二人所出的手指数之和，否则重新开始。试写出该对策中局中人集合、各局中人的策略集、各局中人的支付函数矩阵。 解：局中人集合：I={甲、乙}={1、2}

策略集： S甲={甲出一个手指猜乙出一个手指，甲出一个手指猜乙出两个手指， 甲出两个手指猜乙出一个手指，甲出两个手指猜乙出两个手指}

S乙={乙出一个手指猜甲出一个手指，乙出一个手指猜甲出两个手指， 乙出两个手指猜甲出一个手指，乙出两个手指猜甲出两个手指}

2300

2003，HH H12130040340

三、建模题（8分）

16. 某公司承担了每天至少搬运280t水泥的任务，已知该公司有6辆A型卡车和4辆B型卡车，已知A型卡车每天每辆的运载量为30t，成本费为0.9千元，B型卡车每天每辆的运载量为40t，成本费为1千元。假设你是公司的调度员，请你按要求设计出公司每天的排车方案使得花费最低。（只建立模型不需求解）

解：设每天安排A型卡车x1辆，B型卡车x2辆。

minz0.9x1x2

30x140x2280

x16

s.t.

x24x1,x20,x1,x2I

北京林业大学20 07 --20 08 学年第 二 学期考试试卷

试卷名称： 运筹学 （A） 课程所在学院： 理学院 考试班级 学号 姓名 成绩 试卷说明：

1. 本次考试为闭卷考试。本试卷共计 4 页，共 三 大部分，请勿漏答； 2. 考试时间为 120 分钟，请掌握好答题时间；

3. 答题之前，请将试卷和答题纸上的考试班级、学号、姓名填写清楚； 4. 本试卷所有试题答案写在 试卷 纸上；（特殊要求请详细说明） 5. 答题完毕，请将试卷交回，不得带出考场；

6. 考试中心提示：请你遵守考场纪律，参与公平竞争！一、填空题（每小题3分，共30分）

maxz2x13x2

1.线性规划问题

4x12x215的标准形式：4x12x2x315。 s.t.x1x25s.t.x1x2x45x,x0x,x,x,x0121234maxz2x13x2

4x12x215用两阶段方法求解辅助问题为：4x12x2x315。 s.t.x1x25s.t.x1x2x4x55x,x0x,x,x,x0121234

mingx5

minz,2x13x2

2.线性规划问题

3.线性规划问题中原问题的约束的个数和对偶问题的 变量 的个数相同。

4.求解混合整数规划问题的常用方法： 分支定界方法 。

mincTx

5.x1为s.t.Axb的可行解，y1为其对偶问题的可行解，则cTx1bTy1（大小关系）。

x0

0

6．给出图



11

1

0110

01

1101

0

1。 11

1101010

7.一个图共有5个点，它们的次分别为3、3、4、2、5，这是否可能？ 不可能 。

8. 某超市有一个收款台，顾客到来交款服从最简单流，平均每10分钟6人，收款台服务时间服从负指数分布，平均每10分钟完成9人。该问题属于哪一类型的排队问题： M/M/1/∞ 。 9.根据对状态的了解程度对决策分析问题进行分类，可分为：确定型、风险型、不确定型决策问题 。

1q6

10.矩阵对策p510的平衡局势值为5，则p,q的取值范围为：p5,q5。 623

maxz3x13x2x3

11.（15分）线性规划问题

（2）写出原4x12x2x317（1）用单纯形方法求最优解最优值；



s.t.x1x2x34

x,x,x0

123

问题的对偶问题；（3）利用（1）的结果以及对偶理论写出互补松紧条件并以此求对偶问题的最优解

最优值。 解：（1）

原问题的最优解：x=(4,0,0),最优值：z=12。

min17w14w2

4w1w23（2）原问题的对偶问题：

2w1w23 s.t.

w1w21w1,w20

4w1w23w23

（3）互补松紧条件： 

w0w011

对偶问题最优解:(0,3),最优值：12。

12.（10分）从A 地到E 地要铺设一条煤气管道,其中需经过三级中间站，两点之间的连线上的数字表示距离（单位为千米），如图所示。问应该选择什么路线，使总距离最短？最短距离为多少？（用动态规划方法求解） 解：

最优路线为AB2C1D1E，最短距离为19千米。

13.（12分）某城市建设了一个从湖中抽水到城市的蓄水池的管道系统如图，线上标注的数字是单位时间通过两节点的流量。试求单位时间由湖到蓄水池的最大流量(单位：吨)。 解：

最大流量为7吨。

14.（15分）某工厂面对激烈的市场竞争，拟制定利用先进技术对产品改型的计划。现有三个改型方案可供选择：d1、d2、d3。根据市场需求调查，该厂产品面临高需求、一般需求与低需求三种自然

0.5，0.3，0.2。下表给出了预期收益的情况：

（1） 用期望值方法进行决策； （2） 用决策树模型进行决策；

（3） 如果求助于咨询公司求完全信息的价值。 解：（1）E(d1)=40×0.5+20×0.3+10×0.2=28 E(d2)=70×0.5+30×0.3+0×0.2=44

E(d3)=110×0.5+10×0.3+(-50)×0.2=48,应该选d3。 （2）

（3）完全信息的价值：110×0.5+30×0.3+10×0.2-48=18。

15.（10分）甲、乙二人游戏，每人出一个或两个手指，同时又把猜测对方所出的手指数叫出来。如果只有一个人猜正确，则他赢得的数目（由对方付给）为二人所出的手指数之和，否则重新开始。试写出该对策中局中人集合、各局中人的策略集、各局中人的支付函数矩阵。 解：局中人集合：I={甲、乙}={1、2}

策略集： S甲={甲出一个手指猜乙出一个手指，甲出一个手指猜乙出两个手指， 甲出两个手指猜乙出一个手指，甲出两个手指猜乙出两个手指}

S乙={乙出一个手指猜甲出一个手指，乙出一个手指猜甲出两个手指， 乙出两个手指猜甲出一个手指，乙出两个手指猜甲出两个手指}

2300

2003，HH H12130040340

三、建模题（8分）

16. 某公司承担了每天至少搬运280t水泥的任务，已知该公司有6辆A型卡车和4辆B型卡车，已知A型卡车每天每辆的运载量为30t，成本费为0.9千元，B型卡车每天每辆的运载量为40t，成本费为1千元。假设你是公司的调度员，请你按要求设计出公司每天的排车方案使得花费最低。（只建立模型不需求解）

解：设每天安排A型卡车x1辆，B型卡车x2辆。

minz0.9x1x2

30x140x2280

x16

s.t.

x24x1,x20,x1,x2I