运筹学 试卷及答案 卷1

课程名称:课程名称:运筹学题号一二三四五六七八九十总分评卷得分评卷签名复核得分复核签名一、单项选择（每题2分，共20分）1、对一个极大化的线性规划问题用单纯形法求解，若存在某检验数，且它所在列的系数向量，则该线性规划问题（）。A．有唯一最优解B．有无穷多最优解C．为无界解D．无可行解2、若原问题中xj为自由变量，那么对偶问题中的第j个约束一定为。A．等式约束B．“≤”型约束C．“≥”约束D．无法确定3、有m个产地，n个销地的产销平衡的运输问题中，用表上作业法求解得到时，表中空格数是。A．m×nB．m+n－1C．m+nD．m×n－(m+n－1)4、要用最少费用建设一条公路网，将五个城市连接起来，使它们可以相互到达，已知建设费用与公路长度成正比，那么该问题可以看成是。A．最小树问题求解 B．树的生成问题求解C．最短路问题求解 D．最大流问题求解5、在用对偶单纯形法解最大化线性规划问题时，每次迭代要求单纯形表中（）。A．b列元素不小于零B．检验数都大于零C．检验数都不小于零D．检验数都不大于零6、任何图中，顶点次数的总和等于边数的（）倍。A．2B．3C．1D．4学院：专业：学号：姓名：装订线7、整数规划问题（）。A．可以用舍入取整法求得最优解B．最优目标函数值一定优于松弛问题最优目标函数值C．可以化为0-1型整数规划问题D．一定有有限个可行解8、如果要使目标规划实际实现值不低于目标值，但允许超过目标值，则目标函数应该采用以下哪个基本表达式：（）。A．min{f（d-）}B．min{f（d+）}C．min{f（d++d-）}D．min{f(d--d+)}9、用沃格尔法求解运输问题时，如果罚数的值很大时，应尽量按（）运价安排运输。A．最小单位B．最大单位C．最大差D．最小差10、关于凸集，不正确的描述是（）。A.凸集里面的任意两个点的连线上的点仍然在该凸集内B.线性规划问题的可行域一定是一个凸集C.若线性规划问题的可行域是凸集，则该凸集上的任一个顶点都可能是最优解D.若线性规划问题存在最优解，则最优解一定是可行域的凸集上的某一个顶点二、判断题（每题2分，共20分）1、线性规划问题的任意一可行解都可以用全部基可行解的线形组合表示。（）2、整数规划问题的可行解集合是它的松弛问题可行解集合的一个子集，任意两个可行解的凸组合不一定满足整数约束条件，因而不一定仍为可行解。（）3、目标约束是一种软约束，目标约束中决策值和目标值之间的差异用偏差变量表示,它并不是目标规划所特有的概念。（）4、设T是图G的最小树，任取G中的一条不属于T中的边e添加到T中，则可以得到一个圈，并且e是这个圈中的权最大的边。（）5、用位势法求检验数时，位势不同则求出的检验数不一定不同。（）6、当原问题为无界解时，其对偶问题无可行解，反之，当对偶问题无可行解时，其原问题具有无界解。（）7、指派问题数学模型的形式同运输问题十分相似，也可用表上作业法求解。（）8、无向连通图G是欧拉图，当且仅当G中只有一个奇点。（）9、序列5，4，3，2，1可以是某个简单图的点的次的序列。（）10、用单纯形法计算中，如不按最小比值原则选取换出变量，则在下一个解中至少有一个基变量的值为负。（）三、解答题（注意：1、2、3题为必做题，4、5题为选做题，工商管理1-4班选做第5题，工商管理5、6班选做第4题）1、（20分）已知下列线性规划问题（1）用单纯形法求解线性规划问题。（14分）（2）写出上述问题的对偶问题。（6分）2、（16分）给定下列运输问题：（表中数据为产地Ai到销地Bj的单位运费），求最优运输方案。产销B1B2B3B4产量A1123410A2876520A391011930销量82212183、（10分）试求下图的最小生成树,并计算该树的长度。4、（14分）已知赢得矩阵A如下，请用图解法求解矩阵对策。5、（14分）某公司打算在3个不同地区设置4个销售点，根据市场预测部门估计，每月可得利润如下表所示，试问应如何在各地区设置销售站，可使每月总利润最大？地区销售点01234A016253032B012172022C010141617《运筹学》参考答案及评分细则一、单项选择题（2分/题，共20分）1、C2、A3、D4、A5、D6、A7、D8、A9、A10、B二、判断题（2分/题，共20分）1、√2、√3、╳4、√5、╳6、╳7、√8、╳9、╳10、√三、解答题1．（1）解：将原问题化为标准形式如下：(2分)Cj→20200θCBXBbx1x2x3x4x50x4102471010/20x511[4]830111/4δj20200（3分）0x49/200[11/2]1-1/29/112x111/4123/401/411/3δj0-41/20-1/2（4分）2x39/110012/11-1/112x147/22120-3/227/22δj0-40-1/11-5/11（3分）此时，原问题得到最优解为X*=(47/22，0，9/11，0，0)T，maxZ＝65/11（2分）（2）.原问题的对偶问题为：2．解：方法一：（1）用最小元素法求得初始解，并计算检验数如下：B1B2B3B4产量uiA182（0）（2）100A2（4）（2）218203A3（0）2010（-1）308销量8221218vj1232（初始方案5分，位势2分，检验数2分）（2）因为σ34<0，所以此方案不是最优方案，调整的新方案并计算新检验数：B1B2B3B4产量uiA182（1）（3）100A2（3）（1）128204A3（0）20（1）10308销量8221218vj1221（新方案3分，位势1分，检验数1分）因为所有σij≥0，所以此解为最优解，又因为有非基变量检验数δ31＝0，所以，该问题有多个最优解。其中一个最优解为：A1-B1：8，A1-B2：2，A2-B3：12，A2-B4：8，A3-B2：20，A3-B4：10；最小运费z=8×1+2×2+12×6+8×5+20×10+10×9＝414。（2分）方法二：用沃格尔法（方法略），初始解即为最优解。（评分标准：沃格尔法求得初始方案10分，检验数4分，结果2分）V1V2V5V3V6312121V7V43．解：利用破圈法依次去掉边V2V5，VV1V2V5V3V6312121V7V4（8分）最小树长为：3+1+1+2+2+1＝10（2分）753232753232-2xΙΙΙΙΙΙAß4ß1ß2ß3（4分）图中A点纵坐标即为对策值，令其为V，联立过A的三条由ß1，ß2，ß3，确定的直线方程：解得：=1/2，＝5/2所以，局中人Ι的最优混合策略为X*＝（1/2，1/2）T（6分）因为局中人ΙΙ的最优混合策略只能由ß1，ß2，ß3组成，设Y*＝（y1*，y2*，y3*，y4*）T因为E（x*，1）＝1/2*2+1/2*5）＝7/2>5/2＝V所以y1*＝0又因为x1*＝1/2>0，x2*＝1/2>0，根据定理可得：又因为y1*＝0所以解得：y1*＝y4*＝0，y2*＝y3*＝1/2。局中人ΙΙ的最优策略为y*＝（0，1/2，1/2，0）T。（4分）5．解：此问题可分为三个阶段，分别在地区A、B、C设销售点，k=1,2,3；决策变量uk：表示在地区k可设置的销售点数；状态变量sk：表示k阶段出可在第k到第c个地区设置销售点的个数；状态转移方程：sk+1=sk-uk（表示：2分）因为此问题为离散确定性多阶段决策，所以可用图表示，见下图。（图形：6分）此问题求总利润最大，相当于求状态s1到状态s4的最长路，采用逆序法标号。（标号：4分）则最长路径为：4—2