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

《《运筹学》期末考试试题及参考答案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《运筹学》试题参考答案一、填空题（每空2分，共10分）1、在线性规划问题中，称满足所有约束条件方程和非负限制的解为可行解。2、在线性规划问题中，图解法适合用于处理变量为两个的线性规划问题。3、求解不平衡的运输问题的基本思想是设立虚供地或虚需求点，化为供求平衡的标准形式。4、在图论中，称无圈的连通图为树。5、运输问题中求初始基本可行解的方法通常有最小费用法、西北角法两种方法。二、（每小题5分，共10分）用图解法求解下列线性规划问题：⑴⑵⑶⑷⑸、⑹1）maxz=6x1+4x2解：此题在“《运筹学》复习参考资料.doc”中已有，不再重复。⑵⑶⑷⑸⑹、⑺2）⑴minz=－3x1+2x2解：第11页共

2、11页可行解域为abcda，最优解为b点。由方程组解出x1=11，x2=0∴X*==（11，0）T∴minz=－3×11+2×0=－33三、（15分）某厂生产甲、乙两种产品，这两种产品均需要A、B、C三种资源，每种产品的资源消耗量及单位产品销售后所能获得的利润值以及这三种资源的储备如下表所示：　ABC　甲94370乙4610120　360200300　1）建立使得该厂能获得最大利润的生产计划的线性规划模型；（5分）第11页共11页2）用单纯形法求该问题的最优解。（10分）解：1）建立线性规划数学模型：设甲、乙产品的生产数量应为x1、x2，则x1、x2≥0，设z是产品售后的总利润，则maxz=

3、70x1+120x2s.t.2）用单纯形法求最优解：加入松弛变量x3，x4，x5，得到等效的标准模型：maxz=70x1+120x2+0x3+0x4+0x5s.t.列表计算如下：第11页共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/

4、111005/11-3/11120x2300/11010-3/222/11701200170/1130/11000-170/11－30/11∴X*=（，，，0，0）T∴maxz=70×+120×=四、（10分）用大M法或对偶单纯形法求解如下线性规划模型：minz=5x1＋2x2＋4x3第11页共11页解：用大M法，先化为等效的标准模型：maxz/=－5x1－2x2－4x3s.t.增加人工变量x6、x7，得到：maxz/=－5x1－2x2－4x3－Mx6－Mx7s.t大M法单纯形表求解过程如下：第11页共11页CBXBb－5－2－400－M－MθLx1x2x3x4x5x6x7－Mx64（3）1

5、2－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－－5－2－11/3

6、11/3－1－1/300－1/3－1－1/3－M+1－M+1/3∴x*=（，2，0，0，0）T最优目标函数值minz=－maxz/=－（－）=五、（15分）给定下列运输问题：（表中数据为产地Ai到销地Bj的单位运费）第11页共11页B1B2B3B4siA1A2A312348765910119108015dj82212181）用最小费用法求初始运输方案，并写出相应的总运费；（5分）2）用1）得到的基本可行解，继续迭代求该问题的最优解。（10分）解：用“表上作业法”求解。1）先用最小费用法（最小元素法）求此问题的初始基本可行解：地产用费地销B1B2B3B4SiA11　23　410　8　2　×　×

7、A28　7　65　20　×　×　2　18A3910　11930　×　20　10　×dj8221218606082B1B2A1∴初始方案：218B3B4A22010B2B3A3Z=1×8+2×2+6×2+5×18+10×20+11×10=424第11页共11页2）①用闭回路法，求检验数：地产用费地销B1B2B3B4SiA11　2304－210　8　2　×　×A28－47－265　20　×　×　2　18A3901