运筹学第三版试题和答案

运筹学第三版试题和答案

一、单项选择题（共15题，每题2分，共30分）

1.运筹学的主要研究对象是（）A.纯数学理论问题B.实际管理与决策问题C.自然科学现象D.社会经济统计数据

2.线性规划模型中，决策变量的核心特征是（）A.非负性B.离散性C.连续性D.整数性

3.约束条件“3x1-2x2≤1/think”属于线性规划中的（）A.等式约束B.不等式约束C.非负约束D.目标约束

4.线性规划问题的基变量个数等于（）A.约束条件的个数B.决策变量的个数C.基矩阵的阶数D.非基变量的个数

5.若线性规划问题存在可行解，则其可行域一定是（）A.无界区域B.凸集C.凹集D.有限点集

6.图论中，连接两个不同顶点且无重复顶点的边称为（）A.环B.平行边C.路径D.简单边

7.最大流量问题中，若某条边的流量等于其容量，则该边被称为（）A.饱和边B.零流边C.反向边D.正向边

8.动态规划的基本方程是基于（）建立的A.初始状态和目标函数B.状态转移和决策变量C.约束条件和初始决策D.子问题的最优解

9.整数规划中，若所有决策变量均为整数，则称为（）第1页共8页A.0-1整数规划B.纯整数规划C.混合整数规划D.非线性整数规划

10.运输问题中，“产销平衡”是指（）A.总供应量等于总需求量B.总供应量大于总需求量C.总供应量小于总需求量D.各产地产量等于各销地销量

11.对偶问题的最优解与原问题的最优解之间的关系是（）A.原问题最优解大于对偶问题最优解B.原问题最优解小于对偶问题最优解C.两者相等D.不确定，需具体问题分析

12.若线性规划问题存在无界解，则其对偶问题（）A.无可行解B.有可行解C.有最优解D.无最优解

13.最小生成树问题中，Kruskal算法的核心步骤是（）A.每次选择权值最小的边，避免形成环B.每次选择权值最大的边，避免形成环C.从起点开始扩展，每次选最近顶点D.从终点开始扩展，每次选最近顶点

14.排队系统M/M/1中，系统稳定的关键条件是（）A.到达率λ服务率μB.到达率λ服务率μC.到达率λ=服务率μD.与到达率、服务率无关

15.目标规划中，偏差变量d+和d-的关系是（）A.d+≥0,d-≥0B.d+≥0,d-≤0C.d+≤0,d-≥0D.d+≤0,d-≤0

二、填空题（共10题，每题3分，共30分）

1.线性规划标准型的目标函数为______（填“max”或“min”），约束条件均为______等式，决策变量均为______

2.单纯形法中，基变量的取值称为______，非基变量的初始取值通常为______第2页共8页

3.图论中，不与任何顶点相连的边称为______，连接同一对顶点的多条边称为______

4.最大流量问题中，若某条边的流量为0，则该边称为______；若流量等于容量，则称为______

5.动态规划的三要素是状态、决策和______，其核心思想是将多阶段问题分解为______的子问题

6.运输问题初始基可行解的求法有西北角法、最小元素法和______

7.对偶问题中，原问题的松弛变量对应对偶问题的______变量，原问题的剩余变量对应对偶问题的______变量

8.整数规划分支定界法的基本步骤包括分支、和

9.最小生成树的常见算法有Kruskal算法、Prim算法和______

10.线性规划的可行解是满足所有______的决策变量取值，最优解是目标函数达到______的可行解

三、判断题（共10题，每题2分，共20分）

1.线性规划的可行域一定是凸集（）

2.单纯形法中，若所有非基变量的检验数均小于等于0，则当前基可行解为最优解（）

3.图论中，路径是指由若干条边组成的、顶点不重复的序列（）

4.运输问题的基变量个数等于产地数加销地数减1（）

5.动态规划的最优性原理是指“无论初始状态和决策如何，当前决策仅与当前状态有关，与历史状态无关”（）

6.整数规划问题一定存在最优解（）

7.对偶问题的最优解的目标函数值等于原问题的最优解的目标函数值（）

8.最小生成树的总权值一定小于任意其他生成树的总权值（）第3页共8页

9.排队系统M/M/c中，系统稳定的条件是λ/cμ1（λ为到达率，μ为服务率，c为服务台数）（）

10.目标规划中，d+表示未达到目标值的部分，d-表示超过目标值的部分（）

四、简答题（共5题，每题5分，共25分）

1.简述线性规划的基本假设及其实际意义

2.解释对偶问题的定义，并说明其经济意义

3.动态规划中状态转移方程的定义和作用是什么？

4.简述表上作业法求解运输问题的基本步骤

5.整数规划与线性规划的主要区别是什么？

五、计算题（共4题，每题10分，共40分）

1.用图解法求解线性规划问题max z=2x1+3x2，s.t.x1+x2≤5，2x1+x2≤8，x1,x2≥

02.某运输问题的产销平衡表（单位件）和单位运价表（单位元/件）如下，用最小元素法求初始基可行解并计算总运费o产地产量A1=50，A2=60，A3=40；销地销量B1=30，B2=70，B3=50（总产销平衡）o运价表B1B2B3-----------第4页共8页----A1234A2152A

33413.用单纯形法求解min z=3x1+2x2，s.t.2x1+x2≥10，x1+2x2≥8，x1,x2≥

04.某企业生产A、B两种产品，需经甲、乙、丙设备加工A每件需甲2h、乙3h、丙1h；B每件需甲3h、乙1h、丙2h甲设备12h/日，乙15h/日，丙10h/日A每件利润10元，B每件利润8元求最大利润的生产计划

六、案例分析题（共1题，20分）某农场计划种植A、B两种作物，面积为x

1、x2（亩）A每亩需化肥20kg、农药10瓶；B每亩需化肥15kg、农药20瓶现有化肥1000kg、农药800瓶，A至少种10亩，B不少于5亩A每亩利润50元，B每亩60元建立线性规划模型，求最优种植面积及最大利润，并分析化肥、农药的影子价格第5页共8页答案汇总

一、单项选择题答案

1.B

2.A

3.B

4.C

5.C

6.C

7.A

8.A

9.B

10.A

11.C

12.A

13.A

14.A

15.A

二、填空题答案

1.max；等式；非负

2.基值；

03.孤立边；平行边

4.零流边；饱和边

5.状态转移方程；一系列顺序

6.伏格尔法

7.变量；松弛

8.定界；剪枝第6页共8页

9.破圈法

10.约束条件；最优值

三、判断题答案

1.√

2.√

3.√

4.√

5.√

6.×

7.√

8.√

9.√

10.×

四、简答题答案

1.基本假设比例性（资源消耗与决策变量线性关系）、可加性（目标与约束为变量线性组合）、确定性（参数已知）、非负性（变量非负）；意义简化问题，使实际问题可建模为线性关系

2.对偶问题是与原线性规划对应的另一个线性规划，经济意义原问题目标为最大利润时，对偶问题目标为最小成本，反映资源的机会成本（影子价格）

3.状态转移方程描述从状态i到状态j的决策过程；作用将多阶段问题分解为子问题，通过递推关系求解最优解

4.步骤

①列产销表和运价表；

②求初始基可行解（西北角法/最小元素法/伏格尔法）；

③计算检验数，调整得最优解

5.区别整数规划要求决策变量为整数，线性规划无此要求；整数规划求解更复杂，需分支定界法等特殊算法

五、计算题答案

1.最优解x1=3，x2=2，max z=12（提示可行域顶点为0,0,0,5,3,2,4,0，代入目标函数得3,2时z最大）

2.初始基可行解x11=30，x12=20，x22=40，x23=20，x23=30；总运费=30×2+20×3+40×5+20×2+30×1=390元

3.最优解x1=4/3，x2=14/3，min z=46/3第7页共8页（提示转化为标准型后用单纯形法，最终基变量为x1,x2，检验数均为负）

4.最优计划A=2件，B=3件，最大利润=44元（提示列出约束条件，用单纯形法求解，最优解为2,3，z=2×10+3×8=44）

六、案例分析题答案线性规划模型max z=50x1+60x2s.t.20x1+15x2≤1000，10x1+20x2≤800，x1≥10，x2≥5，x1,x2≥0最优解x1=20，x2=20，总利润=2200元；化肥影子价格=2元/kg，农药影子价格=0元/瓶（提示约束条件联立解得20,20，检验数均非正，故为最优解；影子价格通过单纯形法计算）第8页共8页。