运筹学 试卷及答案 卷2

课程名称:课程名称:运筹学题号一二三四五六七八九十总分评卷得分评卷签名复核得分复核签名一、单项选择（每题2分，共20分）1、对一个极大化的线性规划问题用单纯形法求解，若对所有的检验数，但对某个非基变量，有，则该线性规划问题（）A．有唯一最优解B．有无穷多最优解C．为无界解D．无可行解2、下列描述错误的是（）A．对偶问题的对偶问题等同于原问题B．有些线性规划问题通过对偶问题的求解可以简化原问题的求解C．若原问题和对偶问题均存在最优解时，则它们相应的目标函数值相等D．当对偶问题有解时，原问题也有解3、线性规划原问题第j个约束是严格不等式，则对偶问题中第j个变量是。A．xj≥0B．xj≤0C．xj=0D．不一定4、对于m个产地、n个销地的产销平衡的运输问题，叙述错误的是。A．该问题的系数矩阵有m×n列

B．该问题的系数矩阵有m+n行C．该问题的系数矩阵的秩必为m+n-1

D．该问题的最优解必唯一5、一个无向连通图可以一笔画的充分必要条件是（）A．图中没有奇点B．图中恰好有两个奇点;C．图中没有偶点;D．图中的奇点数为0或者26、下列叙述正确的是。A．线性规划问题，若有最优解，则必是一个基变量组的可行基解学院：专业：学号：姓名：装订线B．线性规划问题一定有可行基解C．线性规划问题的最优解只能在顶点上达到D．单纯形法求解线性规划问题时每换基迭代一次必使目标函数值下降一次7、若一个指派问题的系数矩阵的某行各元素都加上常数得到一个新的矩阵，这一新矩阵对应着一个新的指派问题，则（）。A．新问题与原问题有相同的最优解B．新问题最优目标值大于原问题最优目标函数值C．新问题最优解等于原问题最优解加上D．新问题最优解小于原问题最优解8、用单纯形法求解线性规划问题时引入的松弛变量在目标函数中的系数为。A．0 B．很大的正数C．很大的负数 D．19、下列叙述正确的是。A．目标规划中的正偏差变量取正值，负偏差变量取负值B．在目标规划模型中，应同时包含绝对约束与目标约束C．目标规划可以求解多阶段决策问题D．要求不超过目标值，则目标规划的目标函数表示为min{f（d+）}10、以下叙述中，不正确的是。A．树的点数为边数加1 B．树的任意两点间只有一条路C．图的点数大于边数 D．任何不连通图都不是树二、判断题（每题2分，共20分）1、如果线性规划问题的原问题存在可行解，则其对偶问题也一定存在可行解。（）2、若线性规划问题的最优解存在，则最优解或最优解之一（如果有无穷多的话）一定是可行域的凸集的某个顶点。（）3、序列6，6，5，5，3，3可以是某个图的点的次的序列。（）4、若在无圈图中，任意增加一条边就可以得到唯一的一个圈，则该图为树。5、图解法同单纯形法虽然求解的形式不同，但从几何上理解，两者是一致的。（）6、有m个产地，n个销地的产销平衡的运输问题中，用表上作业法求解得到时，表中空格数是m×n－(m＋n－1)。（）7、对一个有n个变量、m个约束条件的标准型的线性规划问题，其可行域的顶点恰好为Cnm个。（）8、在目标规划中，绝对约束相应的目标函数其优先等级一定是P1级。（）9、若某种资源的影子价格等于C，在其他条件不变的情况下，当该种资源增加5个单位时，相应的目标函数值将增大5C。（）10、产销平衡的运输问题可能存在可行解也可能无解。（）三、解答题（共60分）1、（24分）已知线性规划问题（1）用单纯形法求解线性规划问题，并指出属哪一类解。（16分）（2）用图解法解上述线性规划问题。（8分）2、（10分）写出下列问题的对偶问题。3、（10分）试求下图的最小生成树,并计算该树的长度。2525615461545353446376374、（16分）某公司要把4个有关能源工程项目承包给4个互不相关的外商投标者，规定每个承包商只能且必须承包一个项目，试在总费用最小的条件下确定各个项目的承包者，总费用为多少？各承包商对工程的报价如下表所示：项目投标者ABCD甲21097乙154148丙13141611丁415139《运筹学》参考答案及评分细则一、单项选择题（2分/题，共20分）1、B2、D3、C4、D5、D6、A7、A8、A9、D10、C二、判断题（2分/题，共20分）1、╳2、√3、√4、√5、√6、√7、╳8、╳9、╳10、╳三、解答题1．（1）解：将原问题化为标准形式如下：(2分)Cj→24000θCBXBbx1x2x3x4x50x34-1[2]1004/20x4101201010/20x521-1001-δj24000（4分）4x22-1/211/200-0x46[2]0-11030x541/201/2018δj40-200（5分）4x37/2011/41/402x1310-1/21/200x55/2003/4-1/41δj000-20（3分）因为δ3=0，所以此问题有无穷多最优解。（1分）其中一个最优解为X*=(3，7/2，0，0，5/2)T，maxZ＝20（1分）（2）图解法-4-4-252210AB-x1+2x2=4-x1+x2=2x1+2x2=10如图示，目标函数等值线与可行域的交点是线段AB，A（3，7/2），B（2，4），此问题有无穷多最优解，maxz=10（图6分，结果2分）2．解：设对偶变量分别为y1，y2，y3，则对偶问题为：3．解：利用破圈法得原图的最小树如下图所示：3344312（8分）最小树长为：3+4+3+4+2+1＝17（2分）4．解：用“匈牙利法”求解。行减（2分）试指派（4分）列减行减（2分）试指派（4分）列减（1分）√√√√