管理运筹学试题(A答案)

第1页共8页五邑大学试卷答案及评分标准试卷分类（A卷或B卷）A学期：2009至2010学年度第2学期课程：管理运筹学专业：信管、电子商务、市场营销班级学号：姓名：一、求解下述线性规划问题（共30分，每小题10分）1．12max58zxx1212122312318,0xxxxxx解：(1)画直角坐标系……………………………………1分(2)画约束条件，决定可行域………………………5分(3)画目标函数线……………………………………7分(4)移动目标函数线，得到最优解…………………10分**(0,4),32Xz得分第2页共8页2.123max45zxxx123121231233218245,,0xxxxxxxxxxx解：引入松弛变量和人工变量，化标准形为1236min45wxxxMx1234125123632182455,1,2,,6ixxxxxxxxxxxxijc45100MbBCBX1x2x3x4x5x6x04x3211001805x2[1]00104M6x1110015j4M5M1M0005wM04x1011201052x2100104M6x1010111j6M01M05M020wM因为全体检验数非负，但基变量中存在人工变量，故原问题无可行解。评分标准：化标准形3分给出初始单纯形表3分迭代3分判断无可行解1分第3页共8页3.1234min3wxxxx123124123422436,,,0xxxxxxxxxx解：jc3111bBCBX1x2x3x4x13x2[2]10414x31016j220010w12x11120214x[4]01214j00106w由上表得到最优解*(0,2,0,4)X，*6w因存在非基变量的检验数为0，故本题具有无穷多解。评分标准：初始单纯形表4分；得到最优解5分；判断存在无穷多最优解1分。第4页共8页二、已知如下产销量及运价表，求解此运输问题（20分）产销量及运价表解：（1）由伏格尔法求初始调运方案产销平衡表单位运价表（2）用位势法求检验数检验数表（3）因为全体检验数非负，所以初始调运方案即为最优解。评分标准：求初始调运方案9分求检验数9分判断最优解2分得分第5页共8页三、用隐枚举法求解下述0-1规划问题（15分）12345max82475zxxxxx123451234512345332345324,,,,01xxxxxxxxxxxxxxx--+或解：第一步，将上述线性规划问题转换成规范形式（1）目标函数求极小化，约束条件为“”形式12345min82475wxxxxx123451234512345332345324,,,,01xxxxxxxxxxxxxxx++-或……………………………..2分（2）令111xx，221xx12345min8247510wxxxxx1234512345332325324()01,1,2,,5jjxxxxxxxxxxxxj++-或或……………………………..4分（3）按目标函数变量系数的大小从小到大排列变量，约束条件也作相应的调整23541min2457810wxxxxx2354123541332323254()01,1,2,,5jjxxxxxxxxxxxxj+-+或或……………………………..6分第二步，检验全零解，不是可行解。……………………………..8分第三步，依次分枝，直到得到最优解。本问题的最优解为*(1,0,1,0,0)X，*4z……………………………..15分得分第6页共8页四、求解下述标准指派问题（10分）四人完成四项工作，他们完成各项任务的时间（小时）如下表所示，如何安排四人的工作，才能使完成这四项工作总的时间消耗最少。解：指派方案为：人员1→工作4；人员2→工作1；人员3→工作3；人员4→工作2消耗的最小时间为：43评分标准：第一个矩阵3分；第二个矩阵5分；给出最优解2分。得分第7页共8页五、用动态规划求解下述非线性问题（15分）123maxzxxx1231239,,0xxxxxx解：阶段变量1,2,3k；决策变量kx；状态变量kS，表示从kx到3x所占有的份额；状态转移率：1kkkSSx；允许决策集合：0kkxS；边界条件：19S，44()1fS，40S；递推关系式：110()maxkkkkkkkxSfSxfS；………………………….5分当3k时，33333440()maxxSfSxfS3S*33xS………………………….8分当2k时，22222330()maxxSfSxfS222222201max()4xSxSxS*222Sx………………………….10分当1k时，11111220()maxxSfSxfS112311110()1max27427xSSxxS*113Sx………………………….12分综上：19S，*13x26S，*23x33S，*33x*27z………………………….15分得分第8页共8页六、用Dijkstra标号算法求图中开始结点VS到其他各结点的最短路（10分）解：评分标准：漏标或错标1个扣2分。得分