《运筹学》试题及答案大全

1、在线性规划问题中，称满足所有约束条件方程和非负限制的解为可行解。2、在线性规划问题中，图解法适合用于处理变量为两个的线性规划问题。3、求解不平衡的运输问题的基本思想是设立虚供地或虚需求点，化为供求平衡的标准形式。

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

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

二、（每小题5分，共10分）用图解法求解下列线性规划问题：1）maxz=6x1+4x22x1x210

xx812

x27x1，x20

解：此题在“《运筹学》复习参考资料.doc”中已有，不再重复。2）minz=－3x1+2x2⑴⑵⑶⑷⑸⑹、⑺

2x14x222x4x10

12

2x1x27x3x1

21x1,x20

解：

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

2x14x222

由方程组

x20

x1

T∴X*=x=（11，0）

2∴minz=－3×11+2×0=－33

解出x1=11，x2=0

三、（15分）某厂生产甲、乙两种产品，这两种产品均需要A、B、C三种资源，每种产品的资源消耗量及单位产品销售后所能获得的利润值以及这三种资源的储备如下表所示：

A甲乙94360B46200C310300701201）建立使得该厂能获得最大利润的生产计划的线性规划模型；（5分）2）用单纯形法求该问题的最优解。（10分）解：1）建立线性规划数学模型：

设甲、乙产品的生产数量应为x1、x2，则x1、x2≥0，设z是产品售后的总利润，则

maxz=70x1+120x2s.t.

9x14x2360



4x16x2200

3x110x2300x1，x20

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

加入松弛变量x3，x4，x5，得到等效的标准模型：

maxz=70x1+120x2+0x3+0x4+0x5s.t.

3609x14x2x3

x42004x16x2

x53003x110x2xj0,j1,2,...,5

列表计算如下：

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

minz=5x1＋2x2＋4x33x1x22x34



6x13x25x310x,x,x0123解：用大M法，先化为等效的标准模型：

maxz/=－5x1－2x2－4x3s.t.

3x1x22x3x44

x5106x13x25x3y0,j1,2,...,5j增加人工变量x6、x7，得到：

maxz/=－5x1－2x2－4x3－Mx6－Mx7s.t

3x1x22x3x4x64

x5x7106x13x25x3x0,j1,2,...,7j大M法单纯形表求解过程如下：

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

B1A1A2A31898

B2271022

B3361112

B445918

si108015

dj1）用最小费用法求初始运输方案，并写出相应的总运费；（5分）2）用1）得到的基本可行解，继续迭代求该问题的最优解。（10分）解：用“表上作业法”求解。

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

费用产地销地B1188×9×81072B2326×112022B34B4SiA1A2A3dj∴初始方案：

8

10×5202930101218×18×6060B1

A2

2

B3

A3

20

B2

A1

2

B2

18

B4

10

B3

Z=1×8+2×2+6×2+5×18+10×20+11×10=4242）①用闭回路法，求检验数：

费用产地销地B11882B2327B30×6211201012954B4－2SiA1A2A3dj10×－4×－2×201890×810130×60221860∵34=1＞0，其余j≤0∴选x34作为入基变量迭代调整。②用表上闭回路法进行迭代调整：

费用产地销地B11882B2327B3－1×654B4－3SiA1A2A3dj10×－3×－1×201211893090×8102022－1×1210601860调整后，从上表可看出，所有检验数j≤0，已得最优解。

∴最优方案为：

8

B1

A2

12

B3

A3

20

B2

A1

2

B2

8

B4

10

B4

最小运费Z=1×8+2×2+6×12+5×8+10×20+9×10=414

六、（8分）有甲、乙、丙、丁四个人，要分别指派他们完成A、B、C、D四项不同的工作，每人做各项工作所消耗的时间如下表所示：

A

甲乙丙丁

解：用“匈牙利法”求解。效率矩阵表示为：

215134

1041415

9141613

78119

行约简B1041415

C9141613

D78119

215134

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





01120

80311

71059

5405

列约简标号√

(0)

1120*

8(0)312

25(0)4

540*5(0)

1120*

8(0)312

25(0)4

5√40*

√5



0*134(0)

6(0)310

0001

0100

(0)50*2

1000

34(0)3

0010





至此已得最优解：



∴使总消耗时间为最少的分配任务方案为：

甲→C，乙→B，丙→D，丁→A此时总消耗时间W=9+4+11+4=28

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

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

B153

5

4B235

4

1B37

4C3C2846

D29

C115

D12E169E242D37

5

1

F2

4A

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

14B15314A

5

9B2435

4

1B312

79

5C1158C2114C38

46

4D126D277

5

2D37

9E22

41E11

0F2

4最佳策略为：A→B2→C1→D1→E2→F此时的最短距离为5+4+1+2+2=14

《运筹学》试题及答案19、简述线性规划模型主要参数（p11）（1）、价值系数：目标函数中决策变量前的系数为价值系数（2）、技术系数：约束条件中决策变量前的系数（3）、约束条件右边常数项

15、简述线性规划解几种可能的结果（情形）（ppt第二章39或89页）（1）.有唯一最优解(单纯形法中在求最大目标函数的问题时，对于某个基本可行解，所有δj≤0)

（2）.无可行解，即可行域为空域，不存在满足约束条件的解，也就不存在最优解了。（3）.无界解，即可行域的范围延伸到无穷远，目标函数值可以无穷大或无穷小，一般来说，这说明模型有错，忽略了一些必要的约束条件

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

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

或几个基变量等于零，用图解法无退化解1、简述单纯形法的基本思路（p70）

从可行域中某一个顶点开始，判断此顶点是否是最优解，如不是,则再找另一个使得其目标函数值更优的顶点，称之为迭代，再判断此点是否是最优解。直到找到一个顶点为其最优解，就是使得其目标函数值最优的解，或者能判断出线性规划问题无最优解为止。17、简述线性规划中添加人工变量的前提（p85）在系数矩阵中直接找不到初始可行解，进而通过添加人工变量的方法来构造初始可行基，得出初始基本可行解

10、简述线性规划对偶问题的基本性质（p122）（1）对称性（2）弱对偶性（3）强对偶性（4）最优性（5）互补松弛型

原函数与对偶问题的关系1）

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

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

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

3）原问题的约束条件的右边常数项为对偶问题的目标函数中价值系数。并且原问题的第i个约束条件的右边常数项就等于零对偶问题的目标函数中的第i个变量的系数。4）对偶问题的约束条件的系数矩阵A是原问题约束矩阵的转置。5、运输问题是特殊的线性规划问题，但为什么不用单纯形法求解因为这类线性规划问题在结构上存在着特殊性,表上作业法根据运输问题的特点来设计的特殊的单纯形法，可以更加形象直观简单的解决运输问题。9、简述表上作业法的基本步骤

（1）用最小元素法找出初始基可行解,也就是初始调运方案。对于有m个产地n个销地的产销平衡问题，则有m个关于产量的约束方程和n个关于销量的约束方程。由于产销平衡，其模型最多只有m+n-1个独立的约束方程，即运输问题有m+n-1个基变量。在m×n的产销平衡表上给出m+n-1个数字格，其相对应的调运量的值即为基变量的值。

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

（3）用闭回路法来判别问题是否达到最优解。如已是最优解则停止计算，否则继续下一步。（4）用闭回路法进行基变换，确定入基变量和出基变量，找出新的基本可行解。在表上用闭回路法调整。

11、简述指派问题的标准形式及数学模型（ppt或书上p179）

设n个人被分配去做n件工作，规定每个人只做一件工作，每件工作只有一个人去做。已知第i个人去做第j件工作的效率（时间或费用）为Cij(i=1.2…n;j=1.2…n)并假设Cij≥0。问应如何分配才能使总效率（时间或费用）最高？12、简述分枝定界法的基本步骤分枝定界法是先求解整数规划的线性规划问题。如果其最优解不符合整数条件，则求出整数规划的上下界，用增加约束条件的办法，把相应的线性规划的可行域分成子区域（称为分枝），再求解这些子区域上的线性规划问题，不断缩小整数规划的上下界的距离，最后得整数规划的最优解。

基本思路：

1、先求出线性规划的解

2、确定整数规划的最优目标函数值z*初始上界和下界z3、将一个线性规划问题分为两枝，并求解4、修改最优目标函数上、下界

5、比较与剪枝：各分枝的目标函数值中，若有小于Z者，则剪掉此枝，表明此子问题已经探清，不必再分枝了;否则继续分枝。

6、如此反复进行，直到得到Z＝Z为止，即得最优解X。6、简述目标规划的目标函数主要类型及其数学表达式。目标规划的目标函数只能取极小形式，即minz=f(d+,d-)，共有如下三种形式：（1）,要求恰好等于目标值，即希望决策值超过和不足目标值的部分都尽可能小，因此由函数minz=f(d++d-)；（2），要求不超过目标值，允许达不到目标值，即希望决策值不超过目标值，也希望d+越小越好，因此有minz=f（d+）;(3)要求不低于目标值，允许超过目标值，即希望决策值不低于目标值，也希望d-越小越好，因此有minz=f(d-).2、简述运筹学中背包问题的一般提法（p225）对于N种具有不同重量和不同价值的物品，在携带物品总重量限制的情况下，决定这N种物品中每一种物品多少数量装入背包内，使得装入背包物品的总价值最大。4、建立动态规划模型时，应定义状态变量，请说明状态变量的特点第一,可知性,即各阶段的状态变量的取值能直接或间接的确定；第二,能够确切的描述过程的演变且满足无后效性.

7、简述动态规划数学模型要点（ppt第十章18论述题增加阶段和阶段变量）（1）分析题意，识别问题的多阶段特性，按时间或空间的先后顺序适当划分为满足递推关

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

（2）正确选择状态变量，状态变量应具备两个特征：第一，可知性，即各阶段的状态变量的取值能直接或间接的确定；第二，能够确切的描述过程的演变且满足无后效性；

（3）根据状态变量和决策变量的含义，正确写出状态转移方程；

（4）根据题意明确过程指标函数和最优指标函数以及第k阶段指标函数的含义，并正确列出基本方程。

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

河上有7座桥，将河中的两个岛和河岸连结，如图1所示。一个散步者能否一次走遍7座桥，而且每座桥只许通过一次，最后仍回到起始地点。这就是七桥问题，一个著名的图论问题。

欧拉证明了这样的走法不存在。欧拉是这样解决问题的：既然陆地是桥梁的连接地点，不妨把图中被河隔开的陆地看成A、B、C、D4个点，7座桥表示成7条连接这4个点的线，如图2所示。

于是“七桥问题”就等价于图3中所画图形的一笔画问题了。每个点如果有进去的边就必须有出来的边，从而每个点连接的边数必须有偶数个才能完成一笔画。图3的每个点都连接着奇数条边，因此不可能一笔画出，这就说明不存在一次走遍7座桥，而每座桥只许通过一次的走法。

8、简述树定义及性质

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

性质：（1）树无圈，m=n-1.(2)树连通，m=n-1.(3)树无圈，但每加一条新边，则可得到惟一一个圈.(4)树连通，但任舍一条边，图就不连通.(5)树中任意两点之间有惟一一条链相连.

16、简述求最小生成树的方法（1）避圈法：将图中的边按权由小到大排序；按排序由小到大选定n－1条边为止，选择时每选一条边应避免和已选的边构成圈，且所选边是未选边中的最小权边。

（2）破圈法：在给定的赋权的连通图上任选一个圈；在所找的圈中去掉一个权数最大的边（如果有两条或两条以上的边都是权数最大的边，则任意去掉其中一条）；如果所余下的图已不包含圈，则计算结束，所余下的图即为最小生成树，否则返回第1步。18、简述决策按环境分类（分为哪几种）（p389）

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

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

风险型决策问题：在决策环境不确定的条件下进行，决策者对各自然状态发生的概率可以预先估计或计算出来［非程序化决策：］

13、简述不确定型决策的决策方法（决策准则）（p389）（1）最大最小准则（悲观准则），决策者从最不利的角度去考虑问题；（2）最大最大准则（乐观准则），决策者从最有利的角度去考虑问题；（3）等可能性准则，决策者把各自然状态发生的机会看成是等可能的;（4）乐观系数准则(折衷准则)，决策者取乐观准则和悲观准则的折衷；（5）后悔值准则（沙万奇准则），决策者从后悔的角度去考虑问题14、简述层次分析法的基本步骤（ppt第16章31）

1.明确问题，提出总目标2.绘制层次结构图3.标度及两两比较矩阵4.求各因素权重的过程5.两两比较矩阵一致性检验6.利用权数或特征向量求出各方案的优劣次序.EVPI=EVWPI-EVW0PI

1、结合我国企业发展中面临的一实际问题，简要论述运筹学在我国企业管理优化中的重要应用及作用。答：运筹学在企业管理优化领域的主要应用有：

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

②市场营销。在广告预算和广告媒介的选择、竞争性定价、新产品开发、销售计划、市场竞争策略的制定等方面，运筹学也大展身手。美国杜邦公司在五十年代起就非常重视将运筹学用于研究如何做好广告工作、产品定价，通用公司也运用运筹学方法进行市场模拟研究。

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

④运输问题。运用运筹学，可以确定最小成本的运输路线、物资的调拨、运输工具的调度，以及新建厂址的选择等等。

⑤人事管理。对人员的需求和招聘情况的预测；人力资源的开发，如对人才的教育和培训，人才评价体系、薪酬体系的确定等，都可以运用运筹学方法。

⑥财务会计。运筹学解决企业如何最有效的利用资金资源的问题。其涉及到投资决策分析、成本核算分析、证券管理等。在投资决策分析中，企业如何利用剩余资金，如何投资往往有多种方案。而运筹学的作用就是要要对这些不同的投资方案进行决策，以确定最优的方案，使得

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

联合航空公司满足乘客需求前提下,以最低成本进行订票及安排机场工作班次控制成品库存（制定最优再订购点和订购量，确保安全库存）进行上千个国内航线的飞机优化配置来最大化利润重新设计北美生产和分销系统以降低成本并加快了市场进入速度1-2/1986600万标准品牌公司12/1981380万Delta航空公司1-2/19941亿宝洁公司1-2/19972亿2、根据您所学的《运筹学》及其它学科知识，谈谈您对“运筹帷幄，决胜千里”的理解；语出<史记高祖本纪>，意思是说，张良坐在军帐中运用计谋，就能决定千里之外战斗的胜利，这说明张良心计多，善用脑，善用兵，后来人们就用“运筹帷幄”表示善于策划用兵。

学习中，我们应当努力学习运筹学的理论知识，并将理论知识付诸实践，在学习其他学科时，运用运筹学的知识，比如在写毕业论文时，运用运筹学的知识，丰富论文内容，为论文增加支撑理论。

生活中，我们面对任何问题都要仔细思考，运用运筹学的知识，更好地解决问题，而现在网络及通讯工具的不断发展，让我们远在千里之外也可以解决问题，如：越来越多的跨国公司，不仅仅是局限于面对面的交谈，很多网络会议或电话会议，让解决问题更加方便迅速。

在企业管理中，生产计划、市场营销、库存管理、人事资源、运输问题等。3、请论述如何把你所学的运筹学的知识应用到今后的管理实践中去；答：（1）对运筹学的知识体系了若指掌。（2）处理管理实践的问题时，有意识的使用运筹学的知识体系和方法来解决。（3）需要有很强的归纳总结能力，把在实践中遇到的问题，转化为运筹学书上的问题来解决，如：背包问题、七桥问题。以上三者缺一不可，遇到问题，首先想到解决该问题需要哪些资源，从哪里可以获得这些资源；其次考虑再获得资源后，如何使这些资源得到最合理的利用，使其产生最大效益。另外，强化管理，不断进行管理刨新已成为企业在竞争中制胜的根本保证。作为企业的管理者，把握并运用好运筹学的理念定会取得“运筹帷幄之中，决胜千里之外”之功效。

4、请简要列举（至少3）我国古代朴素的运筹学思想，并论述其间的运筹学原理。（4个）答：（1）孙子兵法与运筹学思想。《孙子兵法》在表达军事思想的同时，也蕴藏着丰富的运筹学思想------军事运筹学。孙武在《孙子兵法》中灵活运用整体性原则研究军事问题，采用定量分析方法谋划战争，运用优化原则进行科学决策。

（2）田忌赛马。战国时期的“田忌赛马”是运筹思想的一次完美应用。整个赛马过程中，

孙膑巧妙地运用了一种科学合理的方法——博弈论。博弈论是运筹学的一个分支，是指二人在平等的对局中各自利用对方的策略变换自己的对抗策略，达到取胜的目的。通过博弈论的思想，孙膑指出用本方的下马对齐王的上马，用本方的上马对齐王的中马，用本方的中马对齐王的下马。最终以一负两胜取胜。孙膑成功地将本方劣势转为优势，赢得了比赛。

（3）围魏救赵。魏国攻打赵国，赵国求救于齐。孙膑指出应趁魏国国内兵力空虚之际，发兵直取魏都大梁，迫使伪军弃赵回救。最终这一战略取得了胜利。其中的战略思想，妙在善于调动第二年。调动敌人的要诀，在于“攻其所必救”。这充分体现了如何策划兵力，选择最佳时间、地点，趋利避害，集中优势兵力以弱克强的运筹思想。

（4）沈括运军粮：沈括曾经从行军中各类人员可以背负粮食的基本数据出发，分析计算了后勤人员与作战兵士在不同行军天数中的不同比例关系，同时也分析计算了用各种牲畜运粮与人力运粮之间的利弊，最后做出了从敌国就地征粮，保障前方供应的重要决策，从而减少了后勤人员的比例，增强了前方作战的兵力。这种军事后勤问题的分析计算是具有现代意义的运筹思想的范例。

（5）晋国公重建皇城的施工方案，体现了运筹学的朴素斯思想。要使重建工程的各个工序，在时间、空间上彼此协调，环环相扣，就需要运用行列式的相关知识，进行精确计算。

1.影子价格:当约束条件中的常数项增加一个单位时，最优目标函数值增加的数量。（影增）2.对偶价格:当约束条件中的常数项增加一个单位时，最优目标函数值改进的数量。3.灵敏度分析:对系统或事物因周围条件变化显示出来的敏感程度分析。4.0-1规划:所有决策变量只能取0或1两个整数的整数线性规划。

5.分支定界法:分枝定界法是先求解整数规划的线性规划问题。如果其最优解不符合整数条件，则求出整数规划的上下界，用增加约束条件的办法，把相应的线性规划的可行域分成子区域（称为分枝），再求解这些子区域上的线性规划问题，不断缩小整数规划的上下界的距离，最后得整数规划的最优解。

6.生成子图:给定一个无向图G=（V,E），保留G的所有点，而删掉部分G的边或者说保留一部分G的边，所获得图G，称之为G的生成子图。

7.松弛问题:不考虑整数约束条件，由余下的目标函数和约束条件构成的规划问题。8.欧拉回路:图G的一个回路，若它恰通过G中每条边一次,则称该回路为欧拉回路。9.样本信息:研究中实际观测或调查的一部分个体的信息。

10.最小生成树:在一个赋权的连通的无向图G找出一个生成树，并使得这个生成树的所有边的权数之和最小。

11.目标约束:在引入了目标值和正、负偏差变量后，可以将原目标函数加上负偏差变量，减去正偏差变量，并且等于目标值，这样形成一个新的函数方程，把它作为一个新的约束条件，加入到原问题中去，称这种新的约束条件为目标约束。

12.偏差变量:指目标规划中实现值与目标值之间的差异。其中实现值超过目标值的部分记为d+,实现值未达到目标值的部分记为d-。d+，d-这样的变量称为偏差变量。13.状态变量：描述各阶段状态的变量称为状态变量。14.基本可行解：满足非负条件的基本解叫基本可行解。15.后验概率：利用样本情报对先验概率修正后得到的概率。

16.定性分析：借助决策者的知识,经验,分析和判断能力等进行决策的方法。

17.定量分析：量化决策问题并建立数学模型进行决策的方法。（基于事物的数据和数量关系,建模、计算找出解决方案）

18.状态与状态变量：状态是指每个阶段开始所处的自然状况或客观条件，而描述过程状态的变量就是状态变量。能够完全描述动态系统时域行为的所含变量个数最少的变量组称为系统的状态变量。

《运筹学》试题及答案（A卷）

一、单项选择题（从下列各题四个备选答案中选出一个正确答案，答案选错或未选者，该题不得分。每小题1分，共10分）1．线性规划具有唯一最优解是指A．最优表中存在常数项为零B．最优表中非基变量检验数全部非零C．最优表中存在非基变量的检验数为零D．可行解集合有界2．设线性规划的约束条件为则基本可行解为A．(0,0,4,3)C．(2,0,1,0)B．(3,4,0,0)D．(3,0,4,0)3．A．无可行解B．有唯一最优解mednD．有无界解则C．有多重最优解4．互为对偶的两个线性规划,对任意可行解X和Y，存在关系A．Z>WC．Z≥WB．Z=WD．Z≤W5．有6个产地4个销地的平衡运输问题模型具有特征A．有10个变量24个约束B．有24个变量10个约束C．有24个变量9个约束D．有9个基变量10个非基变量6.下例错误的说法是A．标准型的目标函数是求最大值B．标准型的目标函数是求最小值C．标准型的常数项非正D．标准型的变量一定要非负7.m+n－1个变量构成一组基变量的充要条件是A．m+n－1个变量恰好构成一个闭回路B．m+n－1个变量不包含任何闭回路C．m+n－1个变量中部分变量构成一个闭回路D．m+n－1个变量对应的系数列向量线性相关8．互为对偶的两个线性规划问题的解存在关系A．原问题无可行解，对偶问题也无可行解B．对偶问题有可行解，原问题可能无可行解C．若最优解存在，则最优解相同D．一个问题无可行解，则另一个问题具有无界解9.有m个产地n个销地的平衡运输问题模型具有特征A．有mn个变量m+n个约束…m+n-1个基变量B．有m+n个变量mn个约束C．有mn个变量m+n－1约束D．有m+n－1个基变量，mn－m－n－1个非基变量10．要求不超过第一目标值、恰好完成第二目标值，目标函数是minZpdp(dd)11222A．minZpdp(dd)11222B．minZpdp(dd)11222C．D．minZp1d1p2(d2d2)

二、判断题（你认为下列命题是否正确，对正确的打“√”；错误的打“×”。每小题1分，共15分）11.若线性规划无最优解则其可行域无界X基本解为空12.凡基本解一定是可行解X同19××××13.线性规划的最优解一定是基本最优解X可能为负14.可行解集非空时,则在极点上至少有一点达到最优值X可能无穷15.互为对偶问题，或者同时都有最优解，或者同时都无最优解√16.运输问题效率表中某一行元素分别乘以一个常数,则最优解不变X17.要求不超过目标值的目标函数是18.求最小值问题的目标函数值是各分枝函数值的下界19.基本解对应的基是可行基X当非负时为基本可行解，对应的基叫可行基20.对偶问题有可行解，则原问题也有可行解X21.原问题具有无界解，则对偶问题不可行22.m+n－1个变量构成基变量组的充要条件是它们不包含闭回路23.目标约束含有偏差变量24.整数规划的最优解是先求相应的线性规划的最优解然后取整得到X25.匈牙利法是对指派问题求最小值的一种求解方法三、填空题（每小题1分，共10分）26．有5个产地5个销地的平衡运输问题，则它的基变量有（9）个27．已知最优基，CB=（3，6)，则对偶问题的最优解是（））28．已知线性规划求极小值，用对偶单纯形法求解时，初始表中应满足条件（对偶问题可行29．非基变量的系数cj变化后，最优表中(30．设运输问题求最大值，则当所有检验数（)发生变化）时得到最优解。31．线性规划第1、2个约束中松驰变量（S1,S2）=（）的最优解是(0，6),它的32．在资源优化的线性规划问题中，某资源有剩余，则该资源影子价格等于（）33．将目标函数1x156x36x4

转化为求极小值是（）34．来源行53的高莫雷方程是（）35．运输问题的检验数λij的经济含义是（四、求解下列各题（共50分）36．已知线性规划（15分））maxZ3x14x25x3x12x2x310

2x1x23x35x0，j1,2,3j

（1）求原问题和对偶问题的最优解；（2）求最优解不变时cj的变化范围37.求下列指派问题（min）的最优解（10分）568512152018

C

910979656

38.求解下列目标规划(15分)minzp1(d3d4)P2d1P3d2x1x2d1d1

xxdd1222

x1d3d3x2d4d4x1,x2,di,di

406030200

(i1,,4)

39．求解下列运输问题（min）（10分）85440

90C141813

9210110

8010060五、应用题（15分）40．某公司要将一批货从三个产地运到四个销地，有关数据如下表所示。销地B1B2B3B4

供

应

产地量

A1A2A3需求量

726320

364240

752480

9115380

560400750

现要求制定调运计划，且依次满足：（1）B3的供应量不低于需要量；（2）其余销地的供应量不低于85%；（3）A3给B3的供应量不低于200；（4）A2尽可能少给B1；（5）销地B2、B3的供应量尽可能保持平衡。（6）使总运费最小。试建立该问题的目标规划数学模型。运筹学（B卷）一、单项选择题（从下列各题四个备选答案中选出一个正确答案，答案选错或未选者，该题不得分。每小题1分，共10分）1．线性规划最优解不唯一是指()A．可行解集合无界C．可行解集合是空集B．存在某个检验数λk>0且D．最优表中存在非基变量的检验数非零2．则()A．无可行解B．有唯一最优解C．有无界解)D．有多重解3．原问题有5个变量3个约束，其对偶问题(A．有3个变量5个约束B．有5个变量3个约束C．有5个变量5个约束D．有3个变量3个约束)4．有3个产地4个销地的平衡运输问题模型具有特征(A．有7个变量C．有6约束B．有12个约束D．有6个基变量)C．非可行解)5．线性规划可行域的顶点一定是(A．基本可行解B．非基本解D．最优解6．X是线性规划的基本可行解则有(A．X中的基变量非零，非基变量为零C．X中的基变量非负，非基变量为零7．互为对偶的两个问题存在关系()B．X不一定满足约束条件D．X是最优解A．原问题无可行解，对偶问题也无可行解B．对偶问题有可行解，原问题也有可行解C．原问题有最优解解，对偶问题可能没有最优解D．原问题无界解，对偶问题无可行解8．线性规划的约束条件为则基本解为()B．(3,0,－1,0)D．(2,0,1,2))A．(0,2,3,2)C．(0,0,6,5)9．要求不低于目标值，其目标函数是(A．B．C．D．10．μ是关于可行流f的一条增广链，则在μ上有()A．对任意B．对任意C．对任意D．.对任意(i,j),有fij0

二、判断题（你认为下列命题是否正确，对正确的打“√”；错误的打“×”。每小题1分，共15分）11．线性规划的最优解是基本解×12．可行解是基本解×13．运输问题不一定存在最优解×14．一对正负偏差变量至少一个等于零×15．人工变量出基后还可能再进基×16．将指派问题效率表中的每一元素同时减去一个数后最优解不变17．求极大值的目标值是各分枝的上界18．若原问题具有m个约束，则它的对偶问题具有m个变量19．原问题求最大值，第i个约束是“≥”约束，则第i个对偶变量yi≤020．要求不低于目标值的目标函数是minZd21．原问题无最优解，则对偶问题无可行解×22．正偏差变量大于等于零，负偏差变量小于等于零×23．要求不超过目标值的目标函数是minZd24．可行流的流量等于发点流出的合流25．割集中弧的容量之和称为割量。三、填空题（每小题1分，共10分）

26．将目标函数minZ10x15x28x3转化为求极大值是（）27．在约束为110A201，它的全部基是（）的线性规划中,设）28．运输问题中m+n－1个变量构成基变量的充要条件是（29．对偶变量的最优解就是（）价格23的高莫雷方程是（21xx2333x430．来源行）31．约束条件的常数项br变化后，最优表中（）发生变化）32．运输问题的检验数λij与对偶变量ui、vj之间存在关系（33．线性规划maxZx1x2,2x1x26,4x1x28,x1,x20的最优解是(0，6),它的））对偶问题的最优解是（34．已知线性规划求极大值，用对偶单纯形法求解时，初始表中应满足条件（35．Dijkstra算法中的点标号b(j)的含义是（四、解答下列各题（共50分）36.用对偶单纯形法求解下列线性规划（15分））37．求解下列目标规划（15分）38．求解下列指派问题（min）（10分）39．求下图v1到v8的最短路及最短路长（10分）五、应用题（15分）40．某厂组装三种产品，有关数据如下表所示。产品ABC

单件组装工

时1.1

1.31.5

日销量（件）产值（元/件）日装配能力

706080

406080

300

要求确定两种产品的日生产计划，并满足：（1）工厂希望装配线尽量不超负荷生产；（2）每日剩余产品尽可能少；（3）日产值尽可能达到6000元。试建立该问题的目标规划数学模型。运筹学（A卷）试题参考答案一、单选题（每小题1分，共10分）1.B2.C3.A4.D5.B6.C7.B8.B9.A10.A二、判断题（每小题1分，共15分）11.×21.√12.×22.√13.×23.√14.×24.×15.√25.√16.×17.√18.√19.×20.×三、填空题（每小题1分，共10分）26.（9）31.(0,2)27.(3,0)32.(0)28.(对偶问题可行)29.(λj)30.(小于等于0)33.(minZx15x2)

34.(s1

552

x3x4或s15x35x44)663

35.xij增加一个单位总运费增加λij四、计算题（共50分）36.解：（1）化标准型2分maxZ3x14x25x3x12x2x3x410



2x1x23x3x55x0，j1,2,,5j

（2）单纯形法5分CBXB4x25x3C(j)-Z(j)x111-6x2100x3010x40.60.2-3.4x50.20.4-2.8b7448

（3）最优解X=(0，7，4)；Z＝48（2分）（4）对偶问题的最优解Y＝（3.4，2.8）(2分)5

c1(,9),c2,c31

3（5）Δc1≤6，Δc2≥-17/2，Δc3≥-6，则(4分)37.解：，（5分）（5分）38．（15分）作图如下：满意解X＝（30，20）39．（10分）最优值Z=1690，最优表如下：B1

销地

产地

B2B3

产量

A1

8

×

57014

18109

2

80

100

×

4×

13

100

1060

4040

A22090

A3×

11024

销量

0

五、应用题（15分）40．设xij为Ai到Bj的运量，数学模型为minzPdP(ddd)PdPdP(dd)Pd112234354657768x13x23x33d1d1480B3保证供应x11x21x31d2d2274B1需求的85％xxxdd204B需求的85％223233212x14x24x34d％4d4323B3需求的85x33d5d5200A3对B3s.t.x21d60A2对B12x112x212x31x12x22x32d7d70B2与B3的平衡34cijxijd80运费最小i1j1xij0 (i1,2,3; j1,2,3,4);d,d0(i1,2,...,8);ii运筹学（B卷）试题参考答案一、单选题（每小题1分，共10分）1.D2.A3.A4.D5.A6.C7.D8.B9.B10.C二、判断题（每小题1分，共15分）11.×21.×12.×22.×13.×23.√14.×24.√15.×25.√16.×17.√18.√19.√20.√三、空题（每小题1分，共10分）26．maxZ10x15x28x3

27.28.不包含任何闭回路29．影子112

s1x3x4或s1x3x42

33330．31.最优解32．ijcijuivj

33．（1，0）34．检验数小于等于零35．发点vi到点vj的最短路长四、解答题（共50分）36．.（15分）模型(3分)Cj30405bCBXBx1

x4

－13－21－2040x2

x5

－0－150[－1]－5/21x3

－8－100x40x5

λj[－2]130x401/2－－30x1

λj10003/2－1/211/2517/24x20－11/215/23（10分）3x1

λj1201100－1－211最优解X＝（2，3）；Z＝1837．（15分）（2分）（画图10分）满意解X是AB线段上任意点。（5分）38．（10分）15617701507

400455

147051



431004

402464005005(0)7

4(0)444545

4605146(0)



300043(0)0

0144(0)146

(8分),最优值Z＝11（2分）39．（10分）(7分)v1到v8的最短路有两条：P18={v1,v3,v6,v8}及P18={v1,v3,v7,v6,v8},最短路长为21。(3分)五、应用题（15分）40．设x1,x2，x3为产品A、B、C的产量，则有（2分）(13分)《运筹学》试题及答案

一、单选题

1.μ是关于可行流f的一条增广链，则在μ上有A.对一切C.对一切2.不满足匈牙利法的条件是A.问题求最小值C.人数与工作数相等B.对一切D.对一切(D)B.效率矩阵的元素非负D.问题求最大值（D）3.从甲市到乙市之间有—公路网络，为了尽快从甲市驱车赶到乙市，应借用（）CA.树的逐步生成法B.求最小技校树法C.求最短路线法D.求最大流量法4.串联系统可靠性问题动态规划模型的特点是（A.状态变量的选取C.有虚拟产地或者销地A.最优基BB.决策变量的选取D.目标函数取乘积形式(B)D.基变量XB

C.第i列的系数）D5.当基变量xi的系数ci波动时，最优表中引起变化的有B.所有非基变量的检验数6.当非基变量xj的系数cj波动时，最优表中引起变化的有A.单纯形乘子B.目标值C.非基变量的检验数(D)C.无界D.是凸集(B)B.有界7.当线性规划的可行解集合非空时一定A.包含点X=(0,0,···,0)A.使原问题保持可行(C)D.常数项8.对偶单纯形法的最小比值规划则是为了保证B.使对偶问题保持可行C.逐步消除原问题不可行性A.正确B.错误D.逐步消除对偶问题不可行性）AD.无法判断C.不一定9.对偶单纯形法迭代中的主元素一定是负元素（10.对偶单纯形法求解极大化线性规划时，如果不按照最小化比值的方法选取什么变量则在下一个解中至少有一个变量为正（）BA.换出变量B.换入变量C.非基变量）BD.不增大(D.无法判断D.无法判断）是基本最优解。AD.无法判断）AD.无法判断）AC.不一定C.不一定C.不一定C.不一定）A）CD.标号法（C）D.基变量11.对LP问题的标准型：maxZCX,AXb,X0，利用单纯形表求解时，每做一次换基迭代，都能保证它相应的目标函数值Z必为（A.增大A.正确A.一定A.一定A.正确B.不减少C.减少12.单纯形法迭代中的主元素一定是正元素B.错误B.一定不B.一定不B.错误13.单纯形法所求线性规划的最优解（14.单纯形法所求线性规划的最优解（）是可行域的顶点。A15.动态规划最优化原理的含义是：最优策略中的任意一个K-子策略也是最优的（16.动态规划的核心是什么原理的应用（A.最优化原理B.逆向求解原理A.图解法A.6B.7B.单纯形法C.8D.9（B）B.工序A完工后工序B才能开工D.工序A是工序B的后续工序(C)D.TL(j)＋tij(C)D.minTL(j)tiji

C.最大流最小割原理D.网络分析原理C.逆序求解17.动态规划求解的一般方法是什么？（18.工序（i,j）的最乐观时间、最可能时间、最保守时间分别是5、8和11，则工序（i,j）的期望时间是19.工序A是工序B的紧后工序，则错误的结论是A．工序B完工后工序A才能开工C.工序B是工序A的紧前工序A.TE(i)t(i,j)

B.TL(j)tij20.工序（i，j）的最迟必须结束时间TLF（i，j）等于C.TL（j）21.工序（i，j）的最早开工时间TES（i，j）等于A.TE（j）A．B.TL（i）C.maxTE(k)tkik22.工序（i，j）的总时差R(i，j)等于TL(j)TE(i)tij

(D)D.TL(j)TE(i)－tijT(i,j)TEF(i,j)B.TEF(i,j)TES(i,j)C.LS

23.活动（i，j）的时间为tij，总时差为R(i,j)，点i及点j的最早开始时刻为TE(i)和TE(j),最迟结束时间为TL(i)和TL(j),下列正确的关系式是（A）A.B.C(A)D.24.互为对偶的两个线性规划问题的解存在关系A.一个问题具有无界解，另一问题无可行解B原问题无可行解，对偶问题也无可行解C.若最优解存在，则最优解相同D.一个问题无可行解，则另一个问题具有无界解(B)B.一个有最优解，另一个也有最优解25.互为对偶的两个线性规划问题的解存在关系A.原问题有可行解，对偶问题也有可行解C.一个无最优解，另一个可能有最优解D.一个问题无可行解，则另一个问题具有无界解26.静态问题的动态处理最常用的方法是？BA.非线性问题的线性化技巧C.引入虚拟产地或者销地27.基本可行解是满足非负条件的基本解。A.正确B.错误C.不一定B.人为的引入时段D.网络建模（）AD.无法判断28.极大化线性规划，单纯形法计算中，如果不按照最小化比值的方法选取换出变量，则在下一个解中至少有一个变量为负，改变量为什么变量？（）DA.换出变量A.正确B.换入变量B.错误C.非基变量C.不一定（C）D.基变量）AD.无法判断29.可行解是满足约束条件和非负条件的决策变量的一组取值。（30.连通图G有n个点，其部分树是T，则有A.T有n个点n条边C.T有n个点n－1条边B.T的长度等于G的每条边的长度之和D.T有n－1个点n条边(B)B.m+n－1个变量不包含任何闭回路(A)31.m+n－1个变量构成一组基变量的充要条件是A.m+n－1个变量恰好构成一个闭回路32.A.无可行解33.A.无可行解B.有唯一最优解B.有唯一最优解C.有无界解C.m+n－1个变量中部分变量构成一个闭回路D.m+n－1个变量对应的系数列向量线性相关D.有多重最优解(B)C.有多重最优解(A)D.有无界解34.某个常数bi波动时，最优表中引起变化的有A.B－1bB.B.CBB－1

C.B－1

C.CBB1b－

D.B－1N(C)B）A.D.系数矩阵35.某个常数bi波动时，最优表中引起变化的有A.检验数36.任意一个容量的网络中，从起点到终点的最大流的流量等于分离起点和终点的任一割集的容量。（A.正确B.错误C.不一定D.无法判断37.若线性规划问题的最优解同时在可行解域的两个顶点处达到，则此线性规划问题的最优解为（两个B.无穷多个C.零个D.过这的点直线上的一切点38.若LP最优解不唯一，则在最优单纯形表上（A.非基变量的检验数必有为零者C.非基变量的检验数必全部为零A.一定有最优解C.可能无可行解B.一定有可行解D.全部约束是小于等于的形式(D)C.最优目标函数值相等D.以上结论都不对）AB.非基变量的检验数不必有为零者D.以上均不正确(B)）B39.若线性规划不加入人工变量就可以进行单纯形法计算40.如果决策变量数相等的两个线性规划的最优解相同，则两个线性规划A.约束条件相同B.模型相同41.设线性规划的约束条件为(D)则非退化基本可行解是A.(2，0，0，0)

B.(0，2，0，0)

C.(1，1，0，0)D.(0，0，2，4)

42.设线性规划的约束条件为(C)则非可行解是A.(2，0，0，0)B.(0，1，1，2)C.(1，0，1，0)D.(1，1，0，0)

43.设P是图G从vs到vt的最短路，则有（A）A.P的长度等于P的每条边的长度之和B.P的最短路长等于vs到vt的最大流量C.P的长度等于G的每条边的长度之和D.P有n个点n-1条边44.事件j的最早时间TE（j）是指（A）A.以事件j为开工事件的工序最早可能开工时间B.以事件j为完工事件的工序最早可能结束时间C.以事件j为开工事件的工序最迟必须开工时间D.以事件j为完工事件的工序最迟必须结束时间45.使函数减少得最快的方向是(B)A.(－1,1,2)B.(1,－1,－2)C.(1,1,2)D.(－1,－1,－2)46.通过什么方法或者技巧可以把工程线路问题转化为动态规划问题？（B）A.非线性问题的线性化技巧B.静态问题的动态处理C.引入虚拟产地或者销地D.引入人工变量47.通过什么方法或者技巧可以把产销不平衡运输问题转化为产销平衡运输问题(C)A.非线性问题的线性化技巧B.静态问题的动态处理C.引入虚拟产地或者销地D.引入人工变量48.为什么单纯形法迭代的每一个解都是可行解？因为遵循了下列规则(A)A.按最小比值规则选择出基变量B.先进基后出基规则C.标准型要求变量非负规则D.按检验数最大的变量进基规则49.网络图关键线路的长度(C)工程完工期。A.大于B.小于C.等于D.不一定等于50.为了在各住宅之间安装一个供水管道．若要求用材料最省，则应使用(B)。A.求最短路法B.求最小技校树法C.求最大流量法D.树的逐步生成法51.最小枝权树算法是从已接接点出发，把()的接点连接上CA.最远B.较远C.最近D.较近52.求解线性规划模型时，引入人工变量是为了（）BA.使该模型存在可行解B.确定一个初始的基可行解C.使该模型标准化D.以上均不正确53.求最短路的计算方法有（B）A.加边法B.Floyd算法C.破圈法D.Ford-Fulkerson算法54.求最大流的计算方法有（D）A.Dijkstra算法B.Floyd算法C.加边法D.Ford-Fulkerson算法55.X是线性规划的基本可行解则有(A)A.X中的基变量非负，非基变量为零B.X中的基变量非零，非基变量为零解D.X不一定满足约束条件56.X是线性规划的可行解，则错误的结论是(D)A.X可能是基本解B.X可能是基本可行解C.X满足所有约束条件D.X是基本可行解C.X不是基本57.下列说法正确的是A.割集是子图（C）B.割量等于割集中弧的流量之和D.割量小于等于最大流量D.发点流出的合流等于流入收点的合流（A）B.流量非负C.容量非负（C）B.可行流是最大流当且仅当存在发点到收点的增广链C.割量大于等于最大流量58.下列错误的结论是A.容量不超过流量59.下列正确的结论是A.最大流等于最大流量C.可行流是最大流当且仅当不存在发点到收点的增广链D.调整量等于增广链上点标号的最大值60.下列正确的结论是61.下列说法错误的是（B）（D）A.最大流量等于最大割量D.最大流量不小于任意割量B.最大流量等于最小割量C.任意流量不小于最小割量A.旅行售货员问题可以建立一个0－1规划数学模型B.旅行售货员问题归结为求总距离最小的Hamilton回路C.旅行售货员问题是售货员遍历图的每个点D.旅行售货员问题是售货员遍历图的每条边62.下列错误的关系式是A.63.下列正确的说法是B.(D)（B）C.DA.在PERT中，项目完工时间的标准差等于各关键工序时间的标准差求和B.单位时间工序的应急成本等于工序总应急成本减去工序总正常成本C.项目的总成本等于各关键工序的成本之和D.项目的总成本等于各工序的成本之和64.下列变量组是一个闭回路65.下列结论正确的有(A)(C)A.{x11,x12,x23,x34,x41,x13}B.{x21,x13,x34,x41,x12}C.{x12,x32,x33,x23,x21,x11}D.{x12,x22,x32,x33,x23,x21}A运输问题的运价表第r行的每个cij同时加上一个非零常数k，其最优调运方案不变B运输问题的运价表第p列的每个cij同时乘以一个非零常数k，其最优调运方案不变C.运输问题的运价表的所有cij同时乘以一个非零常数k,其最优调运方案变化D．不平衡运输问题不一定存在最优解66.下列说法正确的是(D)A.若变量组B包含有闭回路，则B中的变量对应的列向量线性无关B.运输问题的对偶问题不一定存在最优解C.平衡运输问题的对偶问题的变量非负D．第i行的位势ui是第i个对偶变量67.下列错误的结论是(A)A.将指派（分配）问题的效率矩阵每行分别乘以一个非零数后最优解不变B.将指派问题的效率矩阵每行分别加上一个数后最优解不变C.将指派问题的效率矩阵每个元素同时乘以一个非零数后最优解不变D.指派问题的数学模型是整数规划模型68.下列说法正确的是（）：AA.在PERT网络图中只能存在一个始点和一个终点B.网络图中的任何一个结点都具有某项作业的开始和他项作业结束的双重标志属性C.同一结点为开始事件的各项作业的最早开始时间相同D.结点的最早开始时间和最迟完成时间两两相同的所组成的路线是关键路线69.下例错误的说法是(C)A.标准型的目标函数是求最大值70.下例错误的结论是(D)B.标准型的目标函数是求最小值C.标准型的常数项非正D.标准型的变量一定要非负A.检验数是用来检验可行解是否是最优解的数B.检验数是目标函数用非基变量表达的系数C.不同检验数的定义其检验标准也不同D.检验数就是目标函数的系数71.线性规划标准型的系数矩阵Am×n，要求72.线性规划具有无界解是指A.可行解集合无界C.存在某个检验数(B)A.秩(A)=m并且mx

1

(2,4)，x2(4,8)是某LP的两个最优解，则（）也是LP的最优解。DB.x(1,2)

C.x(2,3)

D.无法判断...,λ),松弛变量的检验数为...,λ92.已知对称形式原问题（MAX)的最优表中的检验数为（λ1，λ2，（λn+1，λn+2，nn+m)，则对偶问题的最优解为(C)A.－（λ1，λ2，...,λn)B.（λ1，λ2，...,λn)A有12个变量A.有9个变量B有42个约束B.有9个基变量C－（λn+1，λn+2，...,λn+m)D.（λn+1，λn+2，...,λn+m)(B)93.有6个产地7个销地的平衡运输问题模型的对偶模型具有特征C.有13个约束(D)C.有20个约束C.无可行解94.有5个产地4个销地的平衡运输问题D．有13个基变量D．有8个基变量）CD.以上都不对95.用大M法求解LP模型时，若在最终单纯形表上基变量中仍含有非零的人工变量，则原模型（A.有可行解，但无最优解B.有最优解96.用图解法求解一个关于最小成本的线性规划问题时，若其等成本线与可行解区域的某一条边重合，则该线性规划问题()。AA.有无穷多个最优解A.正确B.有有限个最优解C.有唯一的最优解D.无最优解）AC.不一定D.无法判断97.用单纯形法求解线性规划时，不论极大化或者是极小化问题，均用最小比值原则确定出基变量。（B.错误98.用增加虚设产地或者虚设销地的方法可将产销不平衡的运输问题化为产销平衡的运输问题（A）A.正确B.错误C.不一定D.无法判断99.用DP方法处理资源分配问题时，通常总是选阶段初资源的拥有量作为决策变量（A.正确A.正确A.标准化B.错误B.错误C.不一定C.不一定D.无法判断）BD.无法判断）B100.用DP方法处理资源分配问题时，每个阶段资源的投放量作为状态变量（101.用单纯形法求解线性规划时，引入人工变量的目的是什么？（B.确定初始基本可行解C.确定基本可行解D.简化计算B.无回路有向网络B.不增不减的C.混合网络C.增加的D.容量网络)。C）。）B102.用动态规划求解工程线路问题时，什么样的网络问题可以转化为定步数问题求解（）BA.任意网络A.降低的103.在网络计划技术中，进行时间与成本优化时，一般地说，随着施工周期的缩短，直接费用是(D.难以估计的104.在求最短路线问题中，已知起点到A，B，C三相邻结点的距离分别为15km，20km,25km，则（DA.最短路线—定通过A点C.最短路线一定通过C点A.存在一个圈B.最短路线一定通过B点D.不能判断最短路线通过哪一点)A105.在一棵树中，如果在某两点间加上条边，则图一定(B.存在两个圈C.存在三个圈D.不含圈106.在总运输利润最大的运输方案中，若某方案的空格的改进指数分别为IWB=50元，IWC=-80元，IYA=0元，IXC=20元，则最好挑选()为调整格。AA.WB格A.可以形成至少B.WC格B.不能形成C.YA格C.可以形成D.XC格)一条闭合回路。BD.有可能形成107.在一个运输方案中，从任一数字格开始，(108.在箭线式网络固中，()的说法是错误的。DA.结点不占用时间也不消耗资源B.结点表示前接活动的完成和后续活动的开始C.箭线代表活动D.结点的最早出现时间和最迟出现时间是同一个时间109.在计算最大流量时，我们选中的每一条路线(A.一定是一条最短的路线)。CB.一定不是一条最短的路线)路线通过。AC.是使某一条支线流量饱和的路线D.是任一条支路流量都不饱和的路线110.在一棵树中，从一个结点到另一个结点可以(A.有1条B.有2条C.有3条D.没有111.在求极小值的线性规划问题中，引入人工变量之后，还必须在目标函数中分别为它们配上系数，这些系数值应为()。AA.很大的正数B.较小的正数C.1D.0（D）112.在计划网络图中，节点i的最迟时间TL(i)是指A.以节点i为开工节点的活动最早可能开工时间B.以节点i为完工节点的活动最早可能结束时间C.以节点i为开工节点的活动最迟必须开工时间D.以节点i为完工节点的活动最迟必须结束时间二、多选题

1.大M法和两阶段法是用来（为（）BCA.简化计算）的，当用两阶段法求解LP时，第一阶段建立辅助LP标准型的目标函数C.人工变量之和）。BCB.要保持基变量的取值非负；D.要保持检验数的取值非正。）ACDC.给出目标函数值D.给出最优策略D.存在增广链D.约束条件D.传递性C.连续性定理）部分构成的ABDC.基本方程）BDB.给出动态过程D.Z'cZ

G.人工变量之和的相反数B.处理人工变量E.进行灵敏度分析F.松弛变量、剩余变量和人工变量之和2.单纯形法计算中哪些说法正确（A.非基变量的检验数不为零；C.计算中应进行矩阵的初等行变换；3.动态规划的模型包含有（A.给出最优状态序列A.非负条件A.非负条件A.非负性5.动态规划的标准型是由（B.目标要求4.动态规划的求解的要求是什么（B.四个条件6.动态规划建模时，状态变量的选择必须能够描述状态演变的特征，且满足。BCB.马尔可夫性C.可知性7.动态规划的基本方程包括（A.约束条件B.递推公式）BDC.选择条D.边界条件）。AD8.动态规划方法不同于线性规划的主要特点是（A.动态规划可以解决多阶段决策过程的问题；B.动态规划问题要考虑决策变量；C.它的目标函数与约束不容易表示；D.它可以通过时间或空间划分一些问题为多阶段决策过程问题。9.Dijkstra算法的基本步骤：采用T标号和P标号两种标号，其中（久标号。ABA.T标号B.P标号C.两者均是D.两者均不是）AD10.分析单纯形法原理时，最重要的表达式是什么？（A.用非基变量表示基变量的表达式C.约束条件的表达式A．工序B完工后工序A才能开工C.工序B是工序A的紧前工序B.目标函数的表达式D.用非基变量表示目标函数的表达式（ACD）B.工序A完工后工序B才能开工），目标函数值（））标号为临时标号，（）标号为永11.工序A是工序B的紧后工序，则结论正确的是D.工序A是工序B的后续工序12.极小化（minZ）线性规划标准化为极大化问题后，原规划与标准型的最优解（BAA.相差一个负号A.目标要求B.相同C.没有确定关系C.非负条件D.非线性关系E.以上都不对D.顶点集合E.约束条件13.LP的数学模型由（B.基本方程）三个部分构成。ACE14.目标函数取极小化的（minZ）的线性规划可以转化为目标函数取值最大化即（解；两者的最优解（），最优值（）BEDA.max(Z)E.相同A.对称性C.递推性16.下列说法不正确的是B.max(Z)F.无确定的关系C.max(Z)G.maxZ

D.相关的一个负号H.以上均不正确）BCD）的线性规划问题求15.适合动态规划求解的问题，其目标必须有具有关于阶段效应的（B.可分离形式D.对于K子阶段目标函数的严格单调性（ABC）A.整数规划问题最优值优于其相应的线性规划问题的最优值B.用割平面法求解整数规划问题，构造的割平面有可能切去一些不属于最优解的整数解C.用分枝定界法求解一个极大化的整数规划时，当得到多于一个可行解时，通常可任取其中一个作为下界，再进行比较剪枝D.分枝定界法在处理整数规划问题时，借用线性规划单纯形法的基本思想，在求相应的线性模型解的同时，逐步加入对各变量的整数要求限制，从而把原整数规划问题通过分枝迭代求出最优解。17．下列线性规划与目标规划之间正确的关系是（ACD）A.线性规划的目标函数由决策变量构成，目标规划的目标函数由偏差变量构成B.线性规划模型不包含目标约束，目标规划模型不包含系统约束C.线性规划求最优解，目标规划求满意解D.线性规划模型只有系统约束，目标规划模型可以有系统约束和目标约束18．下面对运输问题的描述不正确的有（BCD）A.是线性规划问题A.容量不超过流量B.不是线性规划问题(BCD)C.可能存在无可行解D.可能无最优解19．下列正确的结论是B.流量非负C.容量非负D.发点流出的合流等于流入收点的合流20.下列错误的结论是（ABD）A.最大流等于最大流量B.可行流是最大流当且仅当存在发点到收点的增广链C.可行流是最大流当且仅当不存在发点到收点的增广链D.调整量等于增广链上点标号的最大值21.下列错误的结论是A.最大流量等于最大割量C.任意流量不小于最小割量22.下列说法正确的是（ACD）B.最大流量等于最小割量D.最大流量不小于任意割量（ABC）A.旅行售货员问题可以建立一个0－1规划数学模型B.旅行售货员问题归结为求总距离最小的Hamilton回路C.旅行售货员问题是售货员遍历图的每个点D.旅行售货员问题是售货员遍历图的每条边23.下列的方法中不是求最大流的计算方法有A.Dijkstra算法C.加边法A.25.下例正确的说法是C.标准型的常数项非正26.下例说法正确是B.Floyd算法D.Ford-Fulkerson算法（ACD）C.（ABD）B.标准型的目标函数是求最小值D.标准型的变量一定要非负（ABC）D.B.（ABC）24．下列正确的关系式是A.标准型的目标函数是求最大值A.检验数是用来检验可行解是否是最优解的数B.检验数是目标函数用非基变量表达的系数C.不同检验数的定义其检验标准也不同27、下面命题正确的是（AB）。A、线性规划标准型要求右端项非负；B、任何线性规划都可化为标准形式；C、线性规划的目标函数可以为不等式；D、可行线性规划的最优解存在。28、单纯形法计算中哪些说法正确（BC）。A、非基变量的检验数不为零；B、要保持基变量的取值非负；C、计算中应进行矩阵的初等行变换；D、要保持检验数的取值非正。29.下面命题正确的是（）。ABA.线性规划标准型要求右端项非负；B.任何线性规划都可化为标准形式；C.线性规划的目标函数可以为不等式；D.可行线性规划的最优解存在。30、下面命题正确的是（BD）。A、线性规划的最优解是基本可行解；B、基本可行解一定是基本解；C、线性规划一定有可行解；D、线性规划的最优值至多有一个。31.线性规划模型有特点（AC）A、所有函数都是线性函数；B、目标求最大；C、有等式或不等式约束；A.无可行解D、变量非负。C.有唯一最优解D.最优解无界32.线性规划的可行域为无界区域时，求解的结果有哪几种可能？（BCD）B.有无穷多个最优解33、线性规划问题的灵敏度分析研究（BC）。数就是目标函数的系数A、对偶单纯形法的计算结果；B、目标函数中决策变量系数的变化与最优解的关系；C、资源数量变化与最优解的关系；D、最优单纯形表中的检验数与影子价格的联系。34.线性规划问题的灵敏度分析研究（A.对偶单纯形法的计算结果；C.资源数量变化与最优解的关系；）BCB.目标函数中决策变量系数的变化与最优解的关系；D.最优单纯形表中的检验数与影子价格的联系。35.X是线性规划的可行解，则正确的是A.X可能是基本解C.X满足所有约束条件A.生产能力C.决策变量的允许取值范围（ABC）B.X可能是基本可行解D.X是基本可行解）BCB.状态变量的允许取值范围D.库存容量36.用动态规划解决生产库存的时候，应该特别注意哪些问题？（37、一个线性规划问题（P）与它的对偶问题（D）有关系（BCD）。A、（P）有可行解则（D）有最优解；B、（P）、（D）均有可行解则都有最优解；C、（P）可行（D）无解，则（P）无有限最优解；D、（P）（D）互为对偶。38、运输问题的基本可行解有特点（AD）。A、有m＋n－1个基变量；B、有m+n个位势；C、产销平衡；D、不含闭回路。39.线性规划问题的标准型最本质的特点是（A.目标要求是极小化C.变量可以取任意值A.针对产销平衡的表）BDE.以上均不对B.变量和右端常数要求非负D.约束形式一定是等式形式40.在运输问题的表上作业法选择初始基本可行解时，必须注意（AD）。B.位势的个数与基变量个数相同D.填写的运输量要等于行、列限制中较小的数值C.填写的运输量要等于行、列限制中较大的数值三、判断题

1.泊松流也称为泊松分布（）√2.D氏标号法求解网络最短路的问题时，通过层层筛选来保证从起点出发，每前进一步都是最短的。（v）3.D氏标号法求解网络最短路的问题时，通过T标号自身比较和T标号横向比较来保证从起点出发，每前进一步都是最短的。（）√4.单纯形法迭代中的主元素一定是正元素，对偶单纯形法迭代中的主元素一定是负元素。（5.动态规划最优化原理的含义是：最优策略中的任意一个K-子策略也是最优的。（6.对偶单纯形法的最小比值规划则是为了保证使原问题保持可行7.当非基变量xj的系数cj波动时，最优表中的常数项也会发生变化9.简单图G（V,E）是树图，则G无圈且连通。10.简单图G（V,E）是树图，有n个点和恰好(n-1)条边。11.简单图G（V,E）是树图，图中任意两点存在唯一的链。13..简单图G（V,E）是树图，图中任意两点存在唯一的链。）√）√（X）（X）（√）8.当线性规划的原问题存在可行解时，则其对偶问题也一定存在可行解。(X）（X）（√）（√）12.简单图G（V,E）是树图，G无圈，但只要加一条边即得唯一的圈。（√）14．割集是子图（F）15．割量小于等于最大流量（F）16．将指派问题的效率矩阵每行分别加上一个数后最优解不变（v）17．将指派问题的效率矩阵每个元素同时乘以一个非零数后最优解不变（v）18凡具备优化、限制、选择条件且能将有关条件用关于决策变量的线性表达式表示出来的问题可以考虑用线性规划模型来处理。（√）19.可通过标号法求最小树20.LP问题的每一个基解对应可行域的一个顶点。×21.LP问题的基本类型是“max”问题。22.LP问题的每一个基可行解对应可行域的一个顶点。23.理论分布是排队论研究的主要问题之一（（（×）x×）））））√（√（×24.M/M/c损失制排队系统可以看成是M/M/c/N混合制的排队系统的特例（25.某服务机构有N个服务台，可同时对顾客提供服务。设顾客到达服从泊松分布，单位时间平均到达λ（人），各服务台服务时间服从同一负指数分布，则可以使用M/M/1（λ／N）的模型（参数）（√）。26.目标函数可以是求min,也可以是求max。×162.某服务机构有N个服务台，可同时对顾客提供服务。设顾客到达服从泊松分布，单位时间平均到达λ（人），各服务台服务时间服从同一负指数分布，则可以使用M/M/1（λ／N）的模型（参数）（√）。27.排队系统的状态转移速度矩阵中，每一列的元素之和等于0。28.排队系统中状态是指系统中的顾客数（）√）×29.排队系统的组成部分有输入过程、排队规则和服务时间（31.排队系统的静态优化是指参数优化（32.排队系统的动态优化是指最优控制（）×）√）×√）。（x）（×）30.排队系统中，若系统输入为泊松流，则相继到达的顾客间隔时间服从负指数分布（）√33.排队系统中，若相继到达顾客的间隔时间服从负指数分布，则系统输入一定是泊松流。（√）34.确定无回路有向网络的节点序时，依据的是寻找增广链（36.求解最大流标记化方法中，标号过程的目的是寻找增广链（37.若可行域是空集则表明存在矛盾的约束条件。(√)38.若线性规划不加入人工变量就可以进行单纯形法计算一定有最优解35.求解网络最大流的标号法中，增广链中的弧一定满足正向非饱和的条件（√）39．若变量组B包含有闭回路，则B中的变量对应的列向量线性无关（x）（）√）×40.容量网络中满足容量限制条件和中间点平衡条件的弧上的流，称为可行流。41.任一容量网络中，从起点到终点的最大流的流量等于分离起点和终点的任一割集的容量。（42.图解法同单纯形表法虽然求解的形式不同，但是从几何上解释，两者是一致的。√43.通过网络建模可以设备更新问题转换为最短路问题？（44.网络最大流的求解结果中，最大流量是唯一的。（46.网络最大流的求解结果中，最小割是唯一的。（48.线性规划求最优解，目标规划求满意解49.线性规划具有无界解是指可行解集合无界（x）（v）（v）（v）50．线性规划求最大值或最小值，目标规划只求最小值52.线性规划无可行解是指进基列系数非正（x）√×）（v）√））45.网络最大流的求解结果中，最小割容量不一定是唯一的。（×）47.线性规划问题的任一可行解都可以用全部基可行解的线性组合表示。(×)51.线性规划的退化基可行解是指基可行解中存在为零的基变量53.线性规划模型不包含目标约束，目标规划模型不包含系统约束54.一旦一个人工变量在迭代中变为非基变量后，改变量及相应的列的数字可以从单纯形表中删除，而不影响计算结果。√55．有6个产地7个销地的平衡运输问题模型的对偶模型有12个变量（x）56．有5个产地4个销地的平衡运输问题有8个变量57．运输问题的对偶问题不一定存在最优解58．运输问题的数学模型属于0-1规划模型（x）（x）（v）59.研究排队模型及数量指标的思路是首先明确系统的意义，然后写出状态概率方程（√）60.原问题与对偶问题都有可行解，则原问题与对偶问题都有最优解（v）61.用增加虚设产地或虚设销地的方法可将产销不平衡的运输问题化为产销平衡的运输问题处理；（√）62.用DP方法处理资源分配问题时，通常总是选阶段初资源的拥有量作为决策变量，每个阶段资源的投放量作为状态变量。（×）63.用增加虚设产地或虚设销地的方法可将产销不平衡的运输问题化为产销平衡的运输问题处理；（64.用大M法处理人工变量的时候，若最终表上基变量中仍然含有人工变量，则原问题无可行解。（65.最短树一定是无圈图（√）66.在容量网络中，满足容量限制条件和弧上的流称为可行流。（×）67.最小树是网络中总权数最小的支撑树，因此它既是支撑子图，又是无圈的连通图。（√）68.整数规划中的指派问题最优解有这样的性质，若从系数矩阵（cij）的一列（行）各元素中分别减去该列（行）的最小元素，得到新矩阵(bij)，那么以(bij)为系数矩阵求得最优解和用原系数矩阵求得最优解相同。（√）（x）69.整数规划问题最优值优于其相应的线性规划问题的最优值√）×）70.在目标线性规划问题中正偏差变量取正值，负偏差变量取负值。（x）