《运筹学》试题及答案

《运筹学》试题及参考答案

一、填空题（每空2分，共10分）

1、在线性规划问题中，称满足所有约束条件方程和非负限制的解为可行解。

2、在线性规划问题中，图解法适合用于处理变量为两个的线性规划问题。

3、求解不平衡的运输问题的基本思想是设立虚供地或虚需求点，化为供求平衡

的标准形式。

4、在图论中，称无圈的连通图为树。

5、运输问题中求初始基本可行解的方法通常有最小费用法、西北角法两

种方法。

二、（每小题5分，共10分）用图解法求解下列线性规划问题：

1）maxz=6XI+4X2⑴

2X,+X2<10⑵

X）+x2<8⑶

<x2<7（4）

内，A:2>0⑸、（6）

解：此题在“循筹学》复习参考趋科.doc”中已有，不再重复。

2)minz=-3XI+2X2⑴

2AT,4-4X2<22⑵

-X,+4X2<10(3)

<2xt-x2<7(4)

X)-3X2<1⑸

xpx2>0(6)、(7)

解:

可行解域为abcda,最优解为b点。

2%[+4x,-22

由方程组｛12八解出Xl=ll,X2=0

AX*=〜=(11,0)T

Jminz=-3x11+2X0=—33

三、（15分）某厂生产甲、乙两种产品，这两种产品均需要A、B、C三种资源,

每种产品的资源消耗量及单位产品销售后所能获得的利润值以及这三种资源的储

备如下表所示:

ABC

甲94370

乙4610120

360200300

1）建立使得该厂能获得最大利润的生产计划的线性规划模型；（5分）

2）用单纯形法求该问题的最优解。（10分）

解：1）建立线性规划数学模型：

设甲、乙产品的生产数量应为XI、X2,则XI、X2>0,设Z是产品售后的总利

润,则

maxz=7（）xi+120x2

9X1+4X2<360

4巧+6%4200

3a+10工2«300

孙x2>0

2)用单纯形法求最优解：

加入松弛变量X3,X4,X5,得到等效的标准模型:

maxz=70XI+120X2+0X3+OX4+OX5

9Xj+4X24-x5=360

4xj+6X2+x4=200

3x(+l()x2+x5=300

与N0,j=l,2,・・・5

列表计算如下:

70120000

CBXBb0L

XiX2X3X4X5

0X33609410090

0X420046010100/3

0X53003(10)00130

00000

70120t000

0X324039/5010-2/5400/13

0X420(11/5)001-3/5100/11

120X2303/101001/10100

361200012

34t000-12

0X31860/11001-39/1119/11

70Xi100/111005/113/11

120X2300/110i0-3/222/11

43000701200170/1130/11

11000-170/11-30/11

300I860

AX*=(—，，0,0)T

111111

•100-300_43000

..maxz=70vX一+120Xv——

111111

四、（10分）用大M法或对偶单纯形法求解如下线性规划模型:

minz=5XI+2X2+4X3

3x1+x2+2x3>4

JV>10

6x}+3X2+53

xpx2,x3>0

解：用大M法，先化为等效的标准模型:

maxzz=_5xi-2x2-4x3

3内4-x2+2X3-x4=4

•6x,4-3X24-5X3-x5=10

匕20,7=1,2,...,5

增加人工变量X6、X7,得到：

maxzz=_5xi—2x2-4x3—Mx6-Mx7

3x)+%+2X3-X4+x6=4

<6X]+3X2+5X3-X5+x7=10

XjNO,/=1,2,...,7

大M法单纯形表求解过程如下:

-5-2-400-M-M

CBXBb0L

XiX2X3X4X5X6X7

-MX64(3)12-10104/3

-MX7106350-101

5/3

-4MMM-M

-9M-7M-M

-M-M0

9M-5f4M-27M-40

—5Xi4/311/32/3-1/301/30

-MX72011(2)-1-211

-5-M-5/3-M-10/3-2M+5/3M2M-5/3-M

0M-l/3M-2/32M-5/3f-M-3M1-5/30

—

—5Xi5/311/25/601/601/610/3

0X410(1/2)1/21-1/2-11/22

一5—5/2-25/605/60—5/6

01/2t1/60—5/6—M—M+5/6

—5Xi2/3101/3-11/31-1/3

-2X220112-1-21

—5-2-11/311/3-1-1/3

_22

­

00-1/3-1-1/3—M+l-M+l/3

2

•*T

•.X=(—,2,0,0,0)

最优目标函数值minz=—maxz』一（一争艳

五，（15分）给定下列运输问题：（表中数据为产地A,到销地Bj的单位运费）

BiB2B3B4Si

Ai12341()

A2876580

A391011915

dj8221218

1）用最小费用法求初始运输方案，并写出相应的总运费；（5分）

2）用1）得到的基本可行解，继续迭代求该问题的最优解。（10分）

解：用“表上作业法”求解。

1）先用最小费用法（最小元素法）求此问题的初始基本可行解：

Z=1X8+2X2+6X2+5X18+10X20+11X10=424

2)①用闭回路法，求检验数:

费\销

BiB2B3B4Si

i2304-2

A\10

82XX

8-47-265

A220

XX218

90101191

As30

X2010X

\60

dj8221218

60\

Vcr34=l>(),其余％WO

，选如作为入基变量迭代调整。

②用表上闭回路法进行迭代调整:

敬

BiB2B3BSi

与'4

i23-14-3

Ai10

82XX

8-37-165

A20

2XX128

901011-19

A30

3X20X10

\60

dj8221218

60\

调整后，从上表可看出，所有检验数%W0,已得最优解。

最优方案为:

最小运费Z=1X8+2X2+6X12+5X8+10X20+9X10=414

六、（8分）有甲、乙、丙、丁四个人，要分别指派他们完成A、B、C、D四项不同的工作，每

人做各项工作所消耗的时间如卜表所示:

ABCD

甲21097

乙154148

丙13141611

T415139

问：应该如何指派，才能使总的消耗时间为最少？

解：用“匈牙利法”求解。

效率矩阵表示为:

‘21097)

’0875、列约简

行约简

1541481101()4

131416111iX2350标号）

、415139,、01195,

V

V

f(0)825]r(c)825)

11

11(0)5411Js

1>

>r---------QA*

23(0)0*1Jw)V

1。，5J)•V

12411245J

6(0)3

(0)54

30,(0)

1023,

0010、

0100

至此已得最优解:

0001

10°0,

・,・使总消耗时间为最少的分配任务方案为:

甲fC,乙fB,丙一D,JfA

此时总消耗时间W=9+4+l1+4=28

七、（6分）计算下图所示的网络从A点到F点的最短路线及其长度。

此题在“《运筹学参考综合习题》（我站搜集信息自编）.doc”中已有。

「、9

：Bi*Di

4

<A5

A)>：B2)>1C2>

7,

：B3\>!：C3\

解：此为动态规划之“最短路问题”，可用逆向追踪“图上标号法”解决如下:

HHH

最佳策略为：AfB2->C]fD】fE?fF

此时的最短距离为5+4+1+2+2=14

《运筹学》试题及答案

19、简述线性规划模型主要参数（P11）

（1）、价值系数：目标函数中决策变量前的系数为价值系数

（2）、技术系数：约束条件中决策变量前的系数

（3）、约束条件右边常数项

15、简述线性规划解几种可能的结果（情形）（ppt第二章39或89页）

（1）.有唯一最优解（单纯形法中在求最大目标函数的问题时，对于某个基本可行解，所

有6jWO）

（2）.无可行解，即可行域为空域，不存在满足约束条件的解，也就不存在最优解了。

（3）.无界解，即可行域的范围延伸到无穷远，目标函数值可以无穷大或无穷小，一般来

说，这说明模型有错，忽略了一些必要的约束条件

（4）.无穷多个最优解，则线段上的所有点都代表了最优解

（5）退化问题，基变量有时存在两个以上相同的最小比道，这样在下一次迭代中就有一个

或几个基变量等于零，用图解法无退化解

1、简述单纯形法的基本思路570）

从可行域中某一个顶点开始，判断此顶点是否是最优解，如不是，则再找另一个使得其F1标

函数值更优的顶点，称之为迭代，再判断此点是否是最优解。直到找到一个顶点为其最优解，

就是使得其目标函数值最优的解，或者能判断出线性规划问题无最优解为止。

17、简述线性规划中添加人工变量的前提（p85）

在系数矩阵中直接找不到初始可行解，进而通过添加人工变量的方法来构造初始可行基，

得出初始基本可行解

10、简述线性规划对偶问题的基本性质（P122）

（1）对称性（2）弱对偶性（3）强对偶性（4）最优性（5）互补松弛型

原函数与对偶问题的关系

1）求目标函数最大值的线性规划问题中有n个变量m个约束条件，它的约束条件都是小于

等于不等式。而其对偶则是求目标函数为最小值的线性规划问题,有m个变量n个约束条件，

其约束条件都为大于等于不等式。

2）原问题的LI标函数中的价值系数为对偶问题中的约束条件的右边常数项，并且原问题的目

标函数中的第i个价值系数就等于对偶问题中的第i个约束条件的右边常数项。

3）原问题的约束条件的右边常数项为对偶问题的目标函数中价值系数。并且原问题的第i个约

束条件的右边常数项就等于零对偶问题的目标函数中的第i个变量的系数。

4）对偶问题的约束条件的系数矩阵A是原问题约束矩阵的转置。

5、运输问题是特殊的线性规划问题，但为什么不用单纯形法求解

因为这类线性规划问题在结构上存在着特殊性，表上作业法根据运输问题的特点来设计的

特殊的单纯形法，可以更加形象直观简单的解决运输问题。

9、简述表上作业法的基本步骤

（1）用最小元素法找出初始基可行解，也就是初始调运方案。对于有m个产地n个销地的

产销平衡问题，则有m个关于产量的约束方程和n个关于销量的约束方程。由于产销平衡，其

模型最多只有Wn1个独立的约束方程，即运输问题有Wn1个基变量。在mXn的产销平衡表

上给出m+n-1个数字格，其相对应的调运量的值即为基变量的值。

（2）求各非基变量的检验数。

（3）用闭回路法来判别问题是否达到最优解。如已是最优解则停止计算，否则继续下一步。

(4)用闭回路法进行基变换，确定入基变量和出基变量，找出新的基本可行解。在表上用

闭回路法调整。

11、简述指派问题的标准形式及数学模型(ppt

设决策变量1指派却个人去做第J件工作

或书上P179)为=•

0不指派第i个人去做第j件工作

设〃个人被分配去做〃件工作，规定每个

CUXiJ

人只做一件工作，每件工作只有一个其数学模型为:人去做。已

知第i个人去做第j件工作的效率(时间或

费用)为…〃;户1.2…〃)并假设

Cij20。问应如何分配才能使总效率(时间或

费用)最高？

xi}-。或1。,7-1.2.­••./f)

12、简述分枝定界法的基本步骤

分枝定界法是先求解整数规划的线性规划问题。如果其最优解不符合整数条件，则求出整

数规划的上下界，用增加约束条件的办法，把相应的线性规划的可行域分成子区域(称为分枝),

再求解这些子区域上的线性规划问题，不断缩小整数规划的上下界的距离，最后得整数规划的

最优解。

基本思路：

1、先求出线性规划的解

2、确定整数规划的最优目标函数值z*初始上界和下界&

3、将一个线性规划问题分为两枝，并求解

4、修改最优目标函数上、下界

5、比较与剪枝：各分枝的目标函数值中，若有小于乙者，则剪掉此枝，表明此子何题已

经探清，不必再分枝了；否则继续分枝。

6、如此反复进行，直到得到Z=Z为止，即得最优解ro

6、简述II标规划的II标函数主要类型及其数学表达式。

目标规划的目标函数只能取极小形式，即minz=f(d+,d-),共有如下三种形式：(1),要求

恰好等于目标值，即希望决策值超过和不足目标值的部分都尽可能小，因此由函数

min片f(diid)；(2),要求不超过目标值，允许达不到目标佳，即希望决策值不超过目标值，

也希望d+越小越好，因此有minif(d+);(3)要求不低于目标值，允许超过目标值，即希望决

策值不低于目标值，也希望d-越小越好，因此有minz=f(d-).

2、简述运筹学中背包问题的一般提法(p225)

对于N种具有不同重量和不同价值的物品，在携带物品总重量限制的情况下，决定这N种

物品中每一种物品多少数量装入背包内，使得装入背包物品的总价值最大。

4、建立动态规划模型时，应定义状态变量，请说明状态变量的特点

第一,可知性，即各阶段的状态变量的取值能直接或间接的确定；第二,能够确切的描述过程

的演变且满足无后效性.

7、简述动态规划数学模型要点(ppt第I•章18论述题增加阶段和阶段变量)

(1)分析题意，识别问题的多阶段特性，按时间或空间的先后顺序适当划分为满足递推关

系的若干阶段，对分时序的静态问题要认为赋予“时段”概念；

(2)正确选择状态变量，状态变量应具备两个特征：第一，可知性，即各阶段的状态变量

的取值能直接或间接的确定；第二，能够确切的描述过程的演变且满足无后效性；

(3)根据状态变量和决策变量的含义，正确写出状态转移方程：

(4)根据题意明确过程指标函数和最优指标函数以及第k阶段指标函数的含义，并正确列

出基本方程。

这其实也是♦个动态规划问题，下面用逆序解法求解它.

阶段变量k：第k次装载笫k种物品(k=l,2,...,n)

状态变量限：第k次装我时背包还可以装我的曳量；

决策变量叫=%：第k次装载第k种物品的件数：•这个问题可以用整数规划模型来描述。设不

决策允许秦合：口岛)={xj()■xss/w,乂卜为整数}:

kkk为第琳物品装入背包的件件(i=l,2,…,

状态转移方程：S1T="-WkXk：n),背包中物品的总价值为z,则

阶段指标：Vk=与人;

,Maxz=cx+cx+...+CN

最优过程指标函数0%)：第k到n阶段容许装入物品的最大使1122

用价值；•W|Xi+W2X2+...+WnX$a

递推方程：欣max{叽/[(5k.J}s.t.

=max{ckxk^1(Vwkxk)):.x1,X»…,X庐0且为整数(i=l,2,n)<

x已入(与)

终端条件：X,(sn.1)=Oo

3、简述著名的哥尼斯堡七桥难题及答案

河上有7座桥，将河中的两个岛和河岸连结，如图1所示。一个散步者能否一次走遍7座

桥，而且每座桥只许通过一次，最后仍回到起始地点。这就是七桥问题，一个著名的图论问题。

欧拉证明了这样的走法不存在。欧拉是这样解决问题的：既然陆地是桥梁的连接地点，不

妨把图中被河隔开的陆地看成A、B、C、D4个点，7座桥表示成7条连接这4个点的线，如图2

所示。

于是“七桥问题”就等价于图3中所画图形的一笔画问题了。每个点如果有进去的边就必

须有出来的边，从而每个点连接的边数必须有偶数个才能完成一笔画。图3的每个点都连接着

奇数条边，因此不可能一笔画出，这就说明不存在一次走遍7座桥，而每座桥只许通过一次的

走法。

8、简述树定义及性质

树:连通且不含圈的无向图称为树。

性质：（1）觥t圈，m=n~l.（2）极连通，m=n~l.（3）树无圈，但每加一条新边，则可得到

惟一一个圈.（4）极连通，但任舍一条边，图就不连通.（5）树任意两点之间有惟一一条链相

迁.

16、简述求最小生成树的方法

（1）避圈法：将图中的边按权由小到大排序；按排序由小到大选定n—l条边为止，选择

时每选一条边应避免和已选的边构成圈，且所选边是未选边中的最小权边。

（2）破圈法：在给定的赋权的连通图上任选一个圈；在所找的圈中去掉一个权数最大的

边（如果有两条或两条以上的边都是权数最大的边，则任意去掉其中一条）；如果所余下的图已

不包含圈，则计算结束，所余下的图即为最小生成树，否则返回第1步。

18、简述决策按环境分类（分为哪几种）（P389）

确定型决策：在决策环境完全确定的条件下进行

不确定型决策：在决策环境不确定的条件下进行，决策者对个自然状态发生的概率一无所

知

风险型决策问题：在决策环境不确定的条件下进行，决策者对各自然状态发生的概率可以

预先估计或计算出来［非程序化决策：］

13、简述不确定型决策的决策方法（决策准则）（p389）

（1）最大最小准则（悲观准则），决策者从最不利的角度去考虑问题；

（2）最大最大准则（乐观准则），决策者从最有利的角度去考虑问题；

（3）等可能性准则，决策者把各自然状态发生的机会看成是等可能的；

（4）乐观系数准则（折衷准则），决策者取乐观准则和悲观准则的折衷；

（5）后悔值准则（沙万奇准则），决策者从后悔的角度去考虑问题

14、简述层次分析法的基本步骤（ppt­概率修正中要用到两个公式:

第16章31）•L全概率公式：

1.明确问题，提出总目标2.绘

?（4）・£尸区也）尸（与）A-1,2(,…).

制层次结构图3.标度及两两比较

矩阵4.求各因素权重的过程5.两两•2、贝叶斯公式：

KN)

比较矩阵一致性检验6.利用权数/-1.2,Lm.4=1.2.

或特征向量求出各方案的优劣次序.

尸郎）.曾

EVPI=EVwPI-EVwoPI

1、结合我国企业发展中面临的一实

际问题，简要论述运筹学在我国企'业管理优化中的重要应用及作用。

答：运筹学在企业管理优化领域的主要应用有：

①生产计•划。如一家重型制造厂用线性规划及整数规划安排生产计划，节约了10%的生产费

用。

②市场营销。在广告预算和广告媒介的选择、竞争性定价、新产品开发、销售计划、市场

竞争策略的制定等方面，运筹学也大展身手。美国杜邦公司在五十年代起就非常重视将运筹学

用于研究如何做好广告工作、产品定价，通用公司也运用运筹学方法进行市场模拟研究。

③库存管理。运筹学中的存贮论可以应用于物资库存量的管理，以确定仓库的合理容量，

以及确定适当的库存方式和库存量。

④运输问题。运用运筹学，可以确定最小成本的运输路线、物资的调拨、运输工具的调度,

以及新建厂址的选择等等。

⑤人事管理。对人员的需求和招聘情况的预测；人力资源的开发，如对人才的教育和培训I,

人才评价体系、薪酬体系的确定等，都可以运用运筹学方法。

⑥财务会计。运筹学解决企业如何最有效的利用资金资源的问题。其涉及到投资决策分析、

成本核算分析、证券管理等。在投资决策分析中，企业如何利用剩余资金，如何投资往往有多

种方案。而运筹学的作用就是要要对这些不同的投资方案进行决策，以确定最优的方案，使得

企业的收益最大。通常是利用线性规划模型、决策论来进行判断。

满足乘客需求前提下，以最低成本进行订票及安排600万

联合航空公司1-2/1986

机场工作班次

控制成品库存（制定最优再订购点和订购■,确保

标准品牌公司12/1981380万

安全库存）

进行上千个国内航线的飞机优化配置来最大化利

Delta航空公司1-2/19941亿

润

重新设计北美生产和分销系统以降低成本并加快

宝洁公司1-2/19972亿

了市场进入速度

2、根据您所学的《运筹学》及其它学科知识，谈谈您对“运筹帷幄，决胜千里”的理解；

语出＜史记高祖本纪》，意思是说，张良坐在军帐中运用计谋，就能决定千里之外战斗的胜

利，这说明张良心计多，善用脑，善用兵，后来人们就用“运筹帷幄”表示善于策划用兵,

学习中，我们应当努力学习运筹学的理论知识，并将理论知识付诸实践，在学习其他学科

时，运用运筹学的知识，比如在写毕业论文时，运用运筹学的知识，丰富论文内容，为论文增

加支撑理论。

生活中，我们面对任何问题都要仔细思考，运用运筹学的知识，更好地解决问题，而现在

网络及通讯工具的不断发展，让我们远在千里之外也可以解决问题，如：越来越多的跨国公司，

不仅仅是局限于面对面的交谈，很多网络会议或电话会议，让解决问题更加方便迅速。

在企业管理中，生产计划、市场营销、库存管理、人事资源、运输问题等。

3、请论述如何把你所学的运筹学的知以应用到今后的管理实践中去；

答：（1）对运筹学的知识体系了若指掌。（2）处理管理实践的问题时，有意识的使用运筹

学的知识体系和方法来解决。（3）需要有很强的归纳总结能力，把在实践中遇到的问题，转化

为运筹学书上的问题来解决，如：背