???????????????????
福建农林大学考试试卷 （ A ）卷
学年 第 学期
课程名称：?????运????筹????学?????考试时间?????????分钟???????
????????????????专业??????年级??????班??学号????????????????姓名??????????? 题号 一 二 三 四 五 六 七 八 九 总得分 得分 评卷人签字 得分 一、填空题（每空?分，共??分）
?? 复核人签字 ???目标规划模型中，对目标约束ax?d?d?g，求ax最大的目标函数为
min(d??d?)。
???增广链上的调整量?大于?零。
???用????????算法求解最短路问题时，距离矩阵的元素必须满足?非负要求?。 ???线性规划的退化基本解的非零分量?至多??个。 ???树是?无圈?的连通图。 得分 二、单项选择题（选择正确答案的字母填入空格，每小题?分，共??分）
???????????
???线性规划的基本解中，非基变量取???值。
???????????????????
?．零???????????????????????????????????．非零 ?．非负??????????????????????????????????．非正 ??增广链是在???下定义的。
?．零流??????????????????????????????????．可行流 ?．不可行流??????????????????????????????．非零流
???在约束为AX＝b?0,X?0的线性规划中??A?(aij)m?n,rA?m，则基的最小数目为???。
?．Cn???????????????????????????????????．? ?．???????????????????????????????????????．?
???互为对偶的两个线性规划问题，如果其中一个无有限最优解，则另外一个???。 ?．无可行解???????????????????????????????．有可行解 ?．有最优解???????????????????????????????．无有限最优解 ???如果目标规划问题（??）没有满意解，则????。
?．（??）无可行解??????????????????????????．（??）有可行解 ?．（??）有无穷多最优解????????????????????．（??）可能有可行解 得分 四、问答题（每小题?分，共??分）
m???对偶单纯形法的求解要点。
⑴建立初始规范型（检验数非正，有负的限定常数），转⑵。
⑵解的检验：出现无可行解特征，停止；限定常数非负，转单纯型法；其他转⑶。 ⑶进行基变换，转⑵。
??最大流算法中流量调整量的确定。
设f为可行流，在?下进行标号，如果无法给??标上号，f为最大流，无需确定流量调整量，否则??l(vt)。 ??网络计划中时差的计算。
可以据下图计算：
???????????
?? ??????????????????????? ?????????
???最短路问题的基础数据与求解内容。
距离矩阵；最短路线，最短路长。 得分 五、（第一小题?分，第二小题?分，第三小题?分，共??分） 对(P)：要求：
???写出(D)；
???用单纯形法或对偶单纯形法确定(P)或(D)的最优解；
???从(P)或(D)的最终表出发，据对偶理论直接确定(D)或(P)的解。
maxz?2x1?x2?x1?x2?10(P)：?
s..t?x2?15?x,x?0?12解：???(D)：
minw?10y1?15y2?y1?2?s..t?y1?y2?1?y,y?0?12 ? ?○?
???选择⑴用单纯形法或确定(P)的最优解； ?? ????????????????? ? ?? ??????????????????? ???????????
运筹学期末考试试卷(AB)卷
