运筹学复习题

选错、多选或不选得0 分）

1．原问题与对偶问题都有可行解，则（ D ）。

A．原问题有最优解，对偶问题没有最优解 B. 原问题与对偶问题可能都没有最优解

C. 一个问题有最优解，另一个问题有无界解 D. 原问题与对偶问题都有最优解 2、当线性规划问题的可行解集合非空时一定（ D ）。

A. 包含原点X=（0，0，„） B. 有界 C. 无界 D. 是凸集 3、 若原问题中xi 为自由变量，那么对偶问题中的第i个约束一定为（ A ）。

A. 等式约束 B. “≤”型约束 C. “≥”约束 D. 无法确定

4．在目标规划中，要求不低于第一目标值，恰好完成第二目标值，则其目标函数为（ A ）。

A. min Z = P1d1 + P2（d2 + d2） B. min Z = P1d1 + P2（d2 + d2） C. min Z = P1（d1 + d1） + P2（d2 + d2） D. min Z = P1（d2 + d2） + P2d2 5．若树 T 有 n 个点，那么它的边数一定是（ D ）。

A. 2n B. n C. n+1 D. n-1 6．完全决定确定型动态规划问题第k+1阶段的状态Sk+1 的是（ D ）。 A. 阶段数k B. 决策Uk C. 状态Sk D. 状态Sk 与决策Uk 7．任何图中，次为奇数的顶点的个数必为（ B ）。

A. 奇数 B. 偶数 C. 奇偶性无法判断 D. 奇数偶数均可 8．图=(V,E)有生成树的充要条件是（ C ）。

A. G是欧拉图 B. G是完全图 C. G是连通图 D. G是有限图G 9．求m个产地，n个销地的运输问题的表上作业法中，用最小元素法确定初始可行解时基变量（即填有数字格）的个数为（ A ） A. m+n-1 B. m+n C. m+n+1 D. mn

10．求解指派问题的匈牙利方法要求系数矩阵中每个元素都是（ A ）。

A. 非负的 B. 大于零 C. 无约束 D. 非零常数 11．满足线性规划问题全部约束条件的解称为（ C ）。

A. 最优解 B. 基本解 C. 可行解 D. 多重解 12、 原问题与对偶问题解相同的是最优（ B ）。

-+

-+

-+

---+

+

-+

A. 解 B. 目标值 C. 解结构 D. 解的分量个数 13．完全决定确定型动态规划问题第k+1阶段的状态Sk+1 的是（ D ）。 A. 阶段数k B. 决策Uk C. 状态Sk D. 状态Sk 与决策Uk 14． 树T 的任意两个顶点间恰有一（ B ）。

A. 边 B. 链 C. 圈 D. 回路 15． 若G是一个简单图，则G中任意两点间（ C ）。

A. 至少有一条边 B. 至少有一条链 C. 最多有一条边 D. 恰有一条链 16．若运输问题已求得最优解，此时所求出的检验数一定是全部（ A ） A. 大于或等于零 B. 大于零 C. 小于零 D. 小于或等于零 17．动态规划的最优性原理是（ A ）

A. 贝尔曼原理 B. 标号原理 C. 霍夫曼原理 D. 旦次捷原理

判断题（对每题结论正确与错误进行判断，如正确，则将“”填入题前的括

号，否则填“×”，）

（  ）1、 若线性规划问题存在两个不同的最优解，则必然有无穷多个最优解。 （  ）2、 图解法同单纯形法虽然求解形式不同，但从几何上理解，两者是一致的。 （ ×）3、 连通图G的生成树是取G的部分点和部分边所组成的树。

（ ×）4、 如线性规划问题存在最优解，则最优解一定对应可行域边界上的一个点。 （  ）5、 按最小元素法（或Vogel法）给出的初始基可行解，从每一空格出发可以找到而且仅能找到惟一的闭回路。

（  ）6、 已知yi为线性规划的对偶问题的最优解，若yi=0，说明在最优生产计划

*

*

中第i种资源一定有剩余。

（ ×）7、 对偶问题的对偶问题未必是原问题。

（ ×）8、 当目标规划模型中存在x1 + x2 + d= 4的约束条件，则该约束为系统约束。

-

（ ×）9、目标规划中的正偏差变量大于等于零，负偏差变量小于等于零。

（ ×）10、整数规划解的目标函数值一般优于其相应的线性规划问题的解的目标函值。 （  ）11、树图是边数最多的无圈的连通图。

（  ）12、求网络最大流的问题可以归结为求解一个线性规划模型。

（ ×）13、图论中的图不论反映了研究对象之间的关系，而且是真实图形的写照，因

而对图中点与点的相对位置，点与点连线的长短曲直等都要严格注意。

（  ）14、动态规划的基本方程是将一个多阶段的决策问题转化为一系列具有递推关系的单阶段的决策问题。

（  ）15、在动态规划模型中，问题的阶段数等于问题的子问题的数目。 （  ）16、若线性规划问题有最优解，则一定有基本最优解。 （ ×）17、Dijkstra算法是求最大流的一种算法。

（  ）18、若线性规划问题存在两个不同的最优解，则必然有无穷多个最优解。 （  ）19、采用单纯形法求解线性规划问题时，人工变量一但出基就不会再进基。 （ ×）20、 整数规划的最优解是先求相应线性规划松弛问题的最优解，然后取整得到。

（ ×）21、 原问题最优解的目标函数值是对偶问题最优解的目标函数值的上界。 （ ×）22、 资源的影子价格反映了资源的市场价值。 （  ）8、 目标规划中的目标约束一定是等式约束。

（ ×）23、 目标规划中的正偏差变量大于等于零，负偏差变量小于等于零。 （ ×）24、指派问题的数学模型属于混合整数规划模型。 （  ）25、给定连通图G=（V，E），则G一定有生成树。

（ ×）26、动态规划问题第k阶段的状态Sk由第k-1阶段的状态Sk-1唯一确定。 （  ）27、如果  是一条增广链，则在其后向弧上满足流量f > 0。 （ ×）28、动态规划是求解多阶段决策问题的一种思路，同时也是一种算法。 （ ×）29、动态规划中最优指标函数fk（Sk）是k阶段状态为Sk 时到下一阶段的最优指标函数值。

（ ×）30．运输问题不一定存在最优解 （  ）31．一对正负偏差变量至少一个等于零 （ ×）32．人工变量出基后还可能再进基

（  ）33．将指派问题效率表中的每一元素同时减去一个数后最优解不变 （  ）34．求极大值的目标值是各分枝的上界

（  ）35．若原问题具有m个约束，则它的对偶问题具有m个变量 （  ）36．原问题求最大值，第i个约束是“≥”约束，则第i个对偶变量yi ≤0 （  ）37．要求不低于目标值的目标函数是minZd

（ ×）38．原问题无最优解，则对偶问题无可行解

（ ×）39．正偏差变量大于等于零，负偏差变量小于等于零

（  ）40．要求不超过目标值的目标函数是minZd （  ）41．可行流的流量等于发点流出的合流 （  ）42．割集中弧的容量之和称为割量。

三、给出线性规划问题

maxz2x14x2x3x4x13x2x482xx612x2x3x46xxx9231x1,x2,x3,x40（1）写出其对偶问题；

（2）已知原问题最优解为X*=(2,2,4,0)，根据对偶理论直接求出对偶问题的最优解。

四、应用题

40． 某厂组装三种产品，有关数据如下表所示。 产品 A B C 单件组装工时 1.1 1.3 1.5 日销量（件） 70 60 80 产值（元/件） 日装配能力 40 60 80 300

要求确定两种产品的日生产计划，并满足： （1）工厂希望装配线尽量不超负荷生产； （2）每日剩余产品尽可能少； （3）日产值尽可能达到6000元。 试建立该问题的目标规划数学模型。

五、有一运输问题平衡作业表如下：（10分，每小题5分）

销地 B1 B1 B2 B3 产地

9 3 8 7 A1 4 9 4 5 A2

5 7 6 2

A3

销量 1 2 3 5

1） 为此运输问题确定初始调运方案；

2） 计算检验数填于表中，并判断初始调运方案是否为最优方案。

六．（1）求下列系数矩阵的最小化指派问题

产量 3 3 5 10114287111014125691214131511107（2）需要分派5人去做5项工作，每人做各项工作的能力评分见表。应如何分排，才能使总的得分最大？

01.21.31.30  1.0001.20 01.0500.21.4  1.00.90.601.1

七．用Ford-Fulkerson算法求下图所示有向网络中从S到T的最大流.

1

a c

3 3 4

2 2 s t

3 3 4 b d

1.30.8001.02、用标号法求下图所示网络中vs---vt的最大流量，图中弧旁数字为容量。

八． 已知A、B两人对策时对A的赢得矩阵如下，求双方各自的最优策略及对策值。 （1） 2 1 4 （2） ―3 －2 6

2 0 3 2 0 2 －1 －2 0 5 －2 －4

九 某决策问题，其决策信息如下表

效益（万元） 方 案 状 态 14 v2 vs 5 v3 7 10 v1 10 v4 10 5 4 6 v5 4 13 vt 9 5 v6 N1 50 30 10 N2 20 25 10 N3 -20 -10 10 S1 S2 S3 （1）用悲观主义决策标准求最佳方案； （2）用乐观主义决策准则求最佳方案； （3）用等可能性决策准则求最佳方案；

（4）令乐观系数α＝0.4，用折衷主义决策准则求最佳方案； （5）用后悔值准则求最佳方案。

十. 某公司内联结8个车间的道路网如图所示，已知每条道路的距离，求沿部分道路架设联结8个车间的电话网，使电话线总距离最短？