3,4,6,8复习题

第三章

一、判断题

1．运输问题是一种特殊的线性规划模型，因而求解的结果也可能出现下列四种情况之一：有唯一最优解，有无穷多最优解，无界解，无可行解．

2．在运输问题中，只要任意地给出一组含m?n?1个非零的?xij?，且满足

?xj?1nij?ai，?xij?bj，就可以作为一个初始基本可行解．

i?1m3．按最小元素法（或伏格尔法）给出的初始基可行解，从每一空格出发可以找出而且仅能找出唯一的闭回路．

4.如果运输问题单位运价表的某一行（或某一列）元素分别加上一个常数k，最优调运方案将不会发生变化．

5.如果运输问题单位运价表的某一行（或某一列）元素分别乘上一个常数k，最优调运方案将不会发生变化．

6.当所有产地的产量和所有销地的销量均为整数时，运输问题的最优解也为整数值．

7.如果运输问题单位运价表的全部元素乘上一个常数k（k?0），最优调运方案将不会发生变化．

8.用位势法求运输问题某一调运方案的检验数时，其结果可能同闭回路法求得的结果有异．

9.m?n?1个变量构成基变量组的充要条件是它们不包含闭回路． 10. 运输问题的可行解中基变量的个数一定遵循m?n?1的规则．

二、选择题

1.在求解运输问题的过程中运用到下列哪些方法（ ） A．西北角法 B.位势法 C. 闭回路法 D. 以上都是

2．在运输方案中出现退化现象，是指数字格的数目 ( ) A．等于m?n B．等于m?n?1

C．小于m?n?1 D．大于m?n?1

3．在产销平衡运输问题中，设产地为m个，销地为n个，那么基可行解中非零变量的个数（ ）

A. 不能大于m?n?1； B. 不能小于m?n?1； C. 等于m?n?1 ； D. 不确定

4 . m?n?1个变量构成一组基变量的充要条件是（ ） A．m?n?1个变量恰好构成一个闭回路 B．m?n?1个变量不包含任何闭回路

C．m?n?1个变量中部分变量构成一个闭回路 D．m?n?1个变量对应的系数列向量线性相关

5.有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个非基变量

三、填空题

1．有5个产地5个销地的平衡运输问题，则它的基变量有（ ）个 2．设运输问题求最大值，则当所有检验数（ ）时得到最优解。 3．运输问题的检验数?ij与对偶变量ui,vj之间存在关系（ ） 4．运输问题的检验数?ij的经济含义是（ ）

5．运输问题中m?n?1个变量构成基变量的充要条件是（ ）

四、计算题

1．某一运输问题的产销平衡表和单位运价表如下图所示：

A1 A2 销量 用表上作业法求最优解.

2．已知运输问题的产销地的供需量与单位运价表如下表所示，试用表上作业法求此运输问题的最优解．

产地 销地 B1 8 7 3 B2 6 10 4 B3 4 9 4 产量 6 5 B1 7 2 6 5 B2 5 7 6 4 B3 4 2 5 8 B4 1 5 6 5 产量 4 11 7 A1 A2 A3 销量 第四章

一、判断题

1.整数规划的最优解是先求相应的线性规划的最优解然后取整得到． 2. 整数规划模型不考虑变量的整数约束得到的相应的线性规划模型，如该模型有无穷多最优解，则整数规划模型也一定有无穷多最优解． 3．用割平面法求解纯整数规划问题时，要求包括松弛变量在内的全部变量必须取整数值．

4. 一个整数规划问题如果存在两个以上的最优解，则该问题一定有无穷多最优解． 5．用分枝定界法求解一个极大化的整数规划问题，当得到多于一个可行解时，通常可任取其中一个作为下界值，再进行比较剪枝．

6．整数规划解的目标函数值一般优于其相应的线性松弛规划问题的解的目标函数值． 7．用割平面法求解整数规划时，构造的割平面有可能切去一些不属于最优解的整数解．

8．指派问题的效率矩阵的每个元素都乘上同一常数k(k>0)，将不影响最优指派方案．

9．指派问题数学模型的形式同运输问题十分相似，故也可以用表上作业法求解．

10．分支定界法在需要分支时必须满足：一是分支后的各子问题必须容易求解，二是各子问题解的集合必须覆盖原问题的解． 二、选择题

1．下列说法错误的是（ ）

A．整数规划解的目标函数值一般优于其相应的线性规划问题解的目标函数值；

B．用割平面法求解纯整数规划时，要求包括松弛变量在内的全部变量必须取整数值；

C．指派问题数学模型的形式同运输问题十分相似，故也可以用表上作业法求解；

D．求解0-1规划的隐枚举法是分枝定界法的特例。 三、填空题

5151．割平面法中，来源于行x1?x3?x4?的割平面方程是（ ）

6632122．割平面法中，来源于行x2?x3?x4?的割平面方程是（ ）

3333．求解某纯整数规划问题的线性松弛模型得最优解为x1?5.8,x2?0，应该如何构造分支条件__________________.

第六章动态规划

一、判断题

1．在动态规划模型中，问题的阶段数等于问题中的子问题的数目；

2．动态规划中，定义状态时应保证在各个阶段中所做决策的相互独立性； 3．动态规划的最优性原理保证了从某一状态开始的未来决策独立于先前已作出的决策；

4．对一个动态规划问题，应用顺推或者逆推解法可能会得出不同的最优解； 5．在动态规划基本方程中，凡子问题具有叠加性质的，其边界条件取值均为零，子问题为乘积型的，边界条件取值均为1；

6．一个线性规划问题若转化为动态规划方法求解时，应严格按变量的下标顺序来划分阶段，如将决定x1的值作为第一阶段，决定x2的值作为第二阶段等。

7．动态规划是用于求解多阶段优化决策的模型和方法，这里多阶段既可以是时间顺序的自然分段，也可以是根据问题性质人为的将决策过程划分成先后顺序的阶段。 二、选择题

1．以下关于动态规划的陈述中不正确的是（ ）．

A．使用动态规划必须满足无后效性的原则 B．动态规划可求解多阶段优化问题

C．动态规划的指标函数要满足可分离性、单调性、递推性 D．动态规划只能倒推求解

2．关于动态规划问题的下列命题中（ ）是错误的。 A、动态规划阶段的顺序与求解过程无关；

B、状态是由决策确定的；

C、用逆序法求解动态规划问题的重要基础之一是最优性原理； D、列表法是求解某些离散变量动态规划问题的有效方法。

三、计算题

1．某工厂有100台机器，准备生产A,B两种产品，若生产产品A,每台机器

2每年可收入10万元，年完好率为，若生产产品B，每台机器年收入为7万元，

39年完好率，三年后这批机器将全部淘汰，试问每年如何生产，使三年内的收

10入最多？运用动态规划方法具体计算求解．

第六章 图和网络分析

一、判断题

1.图论中的图不仅反映了研究对象之间的关系，而且是真实图形的写照，因而对图论中的点与点的相对位置、点与点连线的长短曲直等都要严格注意； 2.在任一图G中，当点集V确定后，树图是G中边数最少的连通图；

3.如果图中某点vi由若干个相邻点，与其距离最远的相邻点vj，则边[i,j]必不包含在最小支撑树内；

4.如图中从vi到各点均有唯一的最短路，则连接vi至其它各点的最短路在去掉重复部分后，恰好构成该图的最小支撑树；

5.求图的最小支撑树以及求图中一点至另一点的最短路问题，都可以归结为求解整数规划问题；

6.求网络最大流问题可归结为求解一个线性规划问题； 7.任一图中奇点的个数可能为奇数个，也可能为偶数个； 8.任何含n个节点n?1条边的连通图一定是树图；

9.一个具有多个发点和多个收点的求网络最大流的问题一定可以转化为求具有单个发点和单个收点的求网络最大流问题；

10.作为增广链上的弧，如属于正向弧一定有fij?cij。

二、选择题

1．已知某个含10个结点的树图，其中9个结点的次为1，1，3，1，1，1，3，1，3，则另一个结点的次为 ( A ) A．3 B．2

C．1 D．以上三种情况均有可能 2．?是关于可行流f的一条增广链，则在?上有( )

A．对任意(i,j)???,有fij?Cij B．对任意(i,j)???,有fij?Cij C．对任意(i,j)???,有fij?Cij D．对任意(i,j)???,有fij?0 三、填空题

1．求最小生成树问题，常用的方法有：避圈法和 。 2．含有n个顶点的完全图，其边数有 条.

3．完全偶图中V1有m个顶点，V2有n个顶点，其边数共有 条. 四、计算题

1．求如图所示网络的最大流和最小割集，每弧旁的数字是（cij,fij）．（14分） v1 (4,1) v3 (8,4) (4,4) (2,2)

(2,2) (5,2)

v2 (3,3) v4 2．用Dijkstra算法求下图中v1到其余各顶点的最短路.（13分）

v2 3 v4

1 2 3 1

v1 4 v6 3 2

5

v3 v5

vs (1,1) (6,3) vt

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库3,4,6,8复习题在线全文阅读。