2016年东华大学旭日工商管理学院802运筹学考研内部复习题及答案
● 摘要
一、选择题
1． 关于对偶问题，下列叙述错误的有（ ）
A. 根据对偶问题的性质, 当原问题为无解时, 其对偶问题无可行解; 反之当对偶问题无可行解, 其原问题具有无界解。
B. 若线性规划的原问题有多重最优解，则其对偶问题也一定具有多重最优解。
C. 己知y 飞为线性规划的对偶问题的最优解，若y*j>0，说明在最优生产计划中第j 种资源己完全耗尽
D. 若某种资源的影子价格等于k ，在其他条件不变的情况下，当种资源增加5个单位时，相应的目标函 数只讲增大sk 【答案】A
【解析】当原问题（对偶问题）无可行解时，对偶问题（原问题）或具有无界解或无可行解。 2． 设线性规划A. 基本可行解 B. 基本可行最优解 C. 最优解 D. 基本解 【答案】A
【解析】可行解包括基可行解与非基可行解。
3． 单纯形法求解最大化线性规划问题，如果存在“左端≥右端常数”的约束条件，对此约束条件应引入（ ）。 A. 可控变量 B. 环境变量 C. 人工变量 D. 松弛变量 【答案】D
【解析】约束方程为“≥”不等式，则可在“≥”不等式左端减去一个非负剩余变量（也可称松弛变量）。
4． 动态规划是解决（ ）的一种数学方法。 A. 单阶段决策过程最优化 B. 多目标决策过程最优化
第 2 页，共 26 页
有可行解，则此线性规划一定有（ ）。
C. 多阶段决策过程最优化 D. 位目标决策过程最优化 【答案】C
【解析】动态规则是运筹学的一个分支，它是解决多阶段决策过程最优化的一种数学方法
二、填空题
5． 图G=（V ，E ）有生成树的充分必要条件是___。 【答案】G 是连通图
【解析】图G 是连通图，如果G 不含圈，那么G 本身是一个树，从而G 使它自身的一个支撑树。现设G 含圈，任取一个圈，从圈中任意地去掉一条边，得到G 的一个支撑子图Gl 。如果Gl 不含圈，那么Gl 是G 的 一个支撑树，如果Gl 仍含圈，那么从Gl 中再任取一个圈，如此重复，最终可以得到G 的一个支撑子图Gk ， 它不含圈，于是Gk 就是G 的一个支撑树。 6． 若对偶问题为无界解，则原问题:_____。 【答案】无可行解
【解析】任一对偶问题的可行解都是原问题的上界，而原问题的任意可行解都是对偶问题的下界。若对偶问题为无界解，则原问题的目标函数有可行解。
7． 若P （k ）是f （x ）在x （K ）处的下降方向，则满足_。 【答案】
【解析】若存在实数
【答案】z-l
【解析】由树的性质可知，树的边数=数的节点数一1
均有
，使对于任意的
，就称方向
）为
均有下式成立:
点的一个下降方向。
无界，即无限小，则z 无解，即没
8． 网络中如果树的节点个数为z ，则边的个数为___。
三、证明题
9． 设线性规划问题解。
【答案】其对偶问题为
有最优解，B 为最优基，证明单纯形乘子CB 是对偶问题的最优
1
设是原问题的最优解，则其对应的基矩阵B 必存在
第 3 页，共 26 页
，即可得，
这时Y 是对偶问题的可行解，它使
由于原问题的最优解，使目标函数取值，由此得，即是对偶
问题的最优解，因此单纯形乘子10．证明:设
，则
是不等式组（I ）和（II ）的解，且
，是对偶问题的最优解。
为G 的解的充要条件是:存在数。（本章定理4）
，使得
和
分别
【答案】（l ）先证充分性。由于x*是不等式组（I ）的解，
且
又由于
是不等式组
的解，且
②
由式①和式②，可知
故由教材第390页的定理3可知，（X ，Y ）为G 的解。 （2）再证必要性，由于（X ，Y ）为G 的解，所以有
*
*
*
*
则
，
**
，因此X 和Y 分别是不等式组（I ）和 （）
的解，且v=VG 。 11．设线性规划问题1是
（
）是其对偶问题的最优解。
又设线性规划问题2是
第 4 页，共 26 页
相关内容
相关标签