2016年南开大学商学院902运筹学(商学院)之《运筹学教程》考研内部复习题及答案
● 摘要
一、填空题
1． 若x 为某极大化线性规划问题的一个基可行解，用非基变量表达其目标函数的形式为
则X 为该LP 最优解的条件是:_____。 【答案】
。
【解析】求极大化问题，则当所有非基变量的检验数均为非正时，即得最优解。线性规划最优时要求非基变 量检验数小于等于0，所以【答案】无可行解
【解析】第一阶段目标函数值不是0，则说明最优解的基变量中含有非零的人工变量，表明原先性规划问题五可行解。
2． 两阶段法中，若第一阶段目标函数最优值不为0，则原问题____。
二、选择题
3． 单纯形法求解最大化线性规划问题，如果存在“左端≥右端常数”的约束条件，对此约束条件应引入（ ）。 A. 可控变量 B. 环境变量 C. 人工变量 D. 松弛变量 【答案】D
【解析】约束方程为“≥”不等式，则可在“≥”不等式左端减去一个非负剩余变量（也可称松弛变量）。
4． 若是否采用j 项目的0--1变量为x ，那么j 个项目中至多只能选择一个项目的约束方程为（ ）。
D. 无法表示 【答案】C
【解析】A 表示的是至少选择一个项目，不符合; B 表示的是只能选择一个项目。
三、计算题
5． 绘制表所示的网络图，并用图上作业法计算时间参数，确定关键路线。
表
【答案】
图 表
关键工序为：A ，F ，I ，N ，O ，Q 关键路线是
6． 用破圈法和避圈法求下图的一个支撑树。
【答案】（l ）用破圈法求解，求解过程如下。
，去掉其中一条边，如e 2=[v1，v 3]; ①取圈（v 1，v 2，v 3）
，去掉其中一条边，如e 7=[v1，v 5]; ②取圈（v 1，v 2，v 5）
，去掉其中一条边，如e 3=[v2，v 3]; ③取圈（v 2，v 3，v 4）
，去掉其中一条边，如e 5=[v2，v 5]; ④取圈（v 2，v 4，v 5）
，去掉其中一条边，如e 10=[v5，v 6]; ⑤取圈（v 4，v 5，v 6）
，去掉其中一条边，如e 15=[v8，v 10]. 这时，剩余的图中不含圈，即得到了⑥取圈（v 8，v 9，v 10）一个支撑树，如图所示。
图
（2）用避圈法求解，求解过程如下:
①在图10-1中，任取一条边e 1，找一条与e 1不构成圈的边e 4; ②找一条与{el ，e 4}不构成圈的边e 6; ③找一条与{el ，e 4，e 6}不构成圈的边e 8; ④找一条与{el ，e 4，e 6，e 8}不构成圈的边e 9; ⑤找一条与毛{el ，e 4，e 6，e 8，e 9}不构成圈的边e 11; ⑥找一条与{el ，e 4，e 6，e 8，e 9，e 11}不构成圈的边e 12; ⑦找一条与{el ，e 4，e 6，e 8，e 9，e 11，e 12}不构成圈的边e 13;
⑧找一条与{el ，e 4，e 6，e 8，e 9，e 12，e 13}不构成圈的边e 14。这时，剩余的图中不含圈，即得到了一个支 撑树，如图所示。
图
相关内容
相关标签