运筹学复习题

《运筹学》复习题

一、单项选择题

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

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

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

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

A. 等式约束 B. “≤”型约束 C. “≥”约束 D. 无法确定 4.若树 T 有 n 个点，那么它的边数一定是（ ）。

A. 2n B. n C. n+1 D. n-1 5．满足线性规划问题全部约束条件的解称为（ ）。

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

A. 解 B. 目标值 C. 解结构 D. 解的分量个数 7． 树T 的任意两个顶点间恰有一（ ）。

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

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

10．任何图中，次为奇数的顶点的个数必为（ ）。

A. 奇数 B. 偶数 C. 奇偶性无法判断 D. 奇数偶数均可

二、 判断题

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

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

找到而且仅能找到惟一的闭回路。

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

*

*

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

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

（ ）8、若线性规划问题有最优解，则一定有基本最优解。 （ ）9、Dijkstra算法是求最大流的一种算法。

（ ）10、若线性规划问题存在两个不同的最优解，则必然有无穷多个最优解

三、运输问题

有A、B、C三个化肥厂供应四个地区Ⅰ、Ⅱ、Ⅲ、Ⅳ的农用化肥，三个工厂每年各自的产量为A--50万吨，B--60万吨，C--50万吨。四个地区的需求量分别是Ⅰ地区最高50万吨，最低30万吨，Ⅱ地区为70万吨，Ⅲ地区为30万吨以下，Ⅳ地区不低于10万吨。问：如何调运，可使总的调运费用最小？单位调运费用如下表所示。

四、用表上作业法求解以下运输问题：

销地 产地 A1 A2 B1 9 4 5 1 B1 3 B2 B3 8 7 5 产量 3 3 9 4 A3 销量 7 6 2 2 3 5 5 五、指派问题

有A、B、C、D4项工作需要4个人完成，每人完成工作的效率不同，有关资料见表，

试确定总效率最好的指派方案

甲 乙 丙 丁

A 2 15 13 4 B 10 4 14 15 C 9 14 16 13 D 7 8 11 9 六、某公司正在安装一个电子邮件系统。下面的网络图展示了办公室之间可以实现的可能

的电子链接情况。办公室之间的距离以100公里为单位(如下图所示)。设计一个办公室联络系统，使所有办公室都能使用电子邮件服务，要求你的设计能使连接8个办公室的线路最短。

2 V1 3 0.5 V2 V3 3 1.5 1 2 1.6 1 V4 V5 3 V7 V61 2 2.5 V8 4 单位：100公里 4 七、求最短路

八、已知线性规划的对偶问题的最优解为Y*=(0,-2)，求原问题的最优解

4

九、求最大流

十、线性规划应用

某医院每天至少需要下列数量的护士： 班次 1 2 3 4 5 6 时间（日夜服务） 6 －－10 点 10 －－ 14 点 14 －－ 18 点 18 －－ 22 点 22 －－ 2 点 2 －－ 6 点 最少护士人数 60 70 60 50 20 30 每班护士在轮班开始时向病房报到，连续工作八小时。医院当然要满足上述各班次的护士数量要求，但又希望尽量少雇佣护士，试作出此问题的线性规划模型。 十一、看懂WINQSB线性规划模型输出的结果