《运筹学》期末考试试题及参考答案-

第1页共11页《运筹学》试题参考答案一、填空题�每空2分�共10分�1、在线性规划问题中�称满足所有约束条件方程和非负限制的解为可行解。2、在线性规划问题中�图解法适合用于处理变量为两个的线性规划问题。3、求解不平衡的运输问题的基本思想是设立虚供地或虚需求点�化为供求平衡的标准形式。4、在图论中�称无圈的连通图为树。5、运输问题中求初始基本可行解的方法通常有最小费用法、西北角法两种方法。二、�每小题5分�共10分�用图解法求解下列线性规划问题�1�maxz=6x1+4x2�������������0781022122121xxxxxxx�解�此题在“《运筹学》复习参考资料.doc”中已有�不再重复。2�minz=�3x1+2x2�������������������0,137210422422121212121xxxxxxxxxx解�⑴⑵⑶⑷⑸⑹、⑺⑴⑵⑶⑷⑸、⑹第2页共11页可行解域为abcda�最优解为b点。由方程组������02242221xxx解出x1=11�x2=0∴X*=��������21xx=�11�0�T∴minz=�3×11+2×0=�33三、�15分�某厂生产甲、乙两种产品�这两种产品均需要A、B、C三种资源�每种产品的资源消耗量及单位产品销售后所能获得的利润值以及这三种资源的储备如下表所示�ABC甲94370乙46101203602003001�建立使得该厂能获得最大利润的生产计划的线性规划模型��5分�第3页共11页2�用单纯形法求该问题的最优解。�10分�解�1�建立线性规划数学模型�设甲、乙产品的生产数量应为x1、x2�则x1、x2≥0�设z是产品售后的总利润�则maxz=70x1+120x2s.t.��������������0300103200643604921212121xxxxxxxx�2�用单纯形法求最优解�加入松弛变量x3�x4�x5�得到等效的标准模型�maxz=70x1+120x2+0x3+0x4+0x5s.t.������������������5,...,2,1,03001032006436049521421321jxxxxxxxxxxj列表计算如下�第4页共11页CBXBb70120000θLx1x2x3x4x50x336094100900x420046010100/30x53003�10�001300000070120↑0000x324039/5010-2/5400/130x420�11/5�001-3/5100/11120x2303/101001/1010036120001234↑000�120x31860/11001�39/1119/1170x1100/111005/11-3/11120x2300/11010-3/222/111143000701200170/1130/11000-170/11�30/11∴X*=�11100�11300�111860�0�0�T∴maxz=70×11100+120×11300=1143000四、�10分�用大M法或对偶单纯形法求解如下线性规划模型�minz=5x1�2x2�4x3������������0,,10536423321321321xxxxxxxxx第5页共11页解�用大M法�先化为等效的标准模型�maxz/=�5x1�2x2�4x3s.t.���������������5,...,2,1,01053642353214321jyxxxxxxxxj增加人工变量x6、x7�得到�maxz/=�5x1�2x2�4x3�Mx6�Mx7s.t�����������������7,...,2,1,0105364237532164321jxxxxxxxxxxxj大M法单纯形表求解过程如下�第6页共11页CBXBb�5�2�400�M�MθLx1x2x3x4x5x6x7�Mx64�3�12�10104/3�Mx7106350�1015/3�9M�4M�7MMM�M�M9M�5↑4M�27M�4�M�M00�5x14/311/32/3�1/301/30——�Mx72011�2��1�211�5-M�5/3-M�10/3-2M+5/3M2M�5/3-M0M�1/3M�2/32M�5/3↑�M�3M+5/30�5x15/311/25/60�1/601/610/30x410�1/2�1/21�1/2�11/22�5�5/2�25/605/60�5/601/2↑1/60�5/6�M�M+5/6�5�2x12/3101/3�11/31�1/3x220112�1�21�322�5�2�11/311/3�1�1/300�1/3�1�1/3�M+1�M+1/3∴x*=�32�2�0�0�0�T最优目标函数值minz=�maxz/=���322�=322五、�15分�给定下列运输问题��表中数据为产地Ai到销地Bj的单位运费�第7页共11页B1B2B3B4siA1A2A312348765910119108015dj82212181�用最小费用法求初始运输方案�并写出相应的总运费��5分�2�用1�得到的基本可行解�继续迭代求该问题的最优解。�10分�解�用“表上作业法”求解。1�先用最小费用法�最小元素法�求此问题的初始基本可行解�B1B2B3B4SiA112341082××A2876520××218A391011930×2010×dj82212186060∴初始方案�Z=1×8+2×2+6×2+5×18+10×20+11×10=424218B3B4A22010B2B3A3销地费用产地82B1B2A1第8页共11页2�①用闭回路法�求检验数�B1B2B3B4SiA112304�21082××A28�47�26520××218A39010119130×2010×dj82212186060∵34�=1�0�其余j�≤0∴选34x作为入基变量迭代调整。②用表上闭回路法进行迭代调整�B1B2B3B4SiA1123�14�31082××A28�37�16520××128A3901011�1930×20×10dj82212186060调整后�从上表可看出�所有检验数j�≤0�已得最优解。∴最优方案为�销地费用产地销地费用产地第9页共11页最小运费Z=1×8+2×2+6×12+5×8+10×20+9×10=414六、�8分�有甲、乙、丙、丁四个人�要分别指派他们完成A、B、C、D四项不同的工作�每人做各项工作所消耗的时间如下表所示�ABCD甲21097乙154148丙13141611丁415139问�应该如何指派�才能使总的消耗时间为最少�解�用“匈牙利法”求解。效率矩阵表示为���������������9131541116141381441579102��������������5911005324100115780��������������541200)0(3245)0(11528)0(**��������������541200)0(3245)0(11528)0(**行约简128B3B4A22010B2B4A382B1B2A1标号列约简√√√第10页共11页��������������3210)0()0(03445)0(133)0(60**至此已得最优解���������������0001100000100100∴使总消耗时间为最少的分配任务方案为�甲→C�乙→B�丙→D�丁→A此时总消耗时间W=9+4+11+4=28七、�6分�计算下图所示的网络从A点到F点的最短路线及其长度。此题在“《运筹学参考综合习题》�我站搜集信息自编�.doc”中已有。解�此为动态规划之“最短路问题”�可用逆向追踪“图上标号法”解决如下�43735191257962424468515454AB1B2B3C1C2C3D1D2D3E1E2F第11页共11页最佳策略为�A→B2→C1→D1→E2→F此时的最短距离为5+4+1+2+2=1417343201257962424468515454AB1B2B3C1C2C3D1D2D3E1E2F59147711859121414