《《运筹学》期末考试试题及参考答案.doc》由会员分享，可在线阅读，更多相关《《运筹学》期末考试试题及参考答案.doc（11页珍藏版）》请在金锄头文库上搜索。
1、运筹学试题参考答案一、填空题（每空2分，共10分）1、在线性规划问题中，称满足所有约束条件方程和非负限制的解为 可行解 。2、在线性规划问题中，图解法适合用于处理 变量 为两个的线性规划问题。3、求解不平衡的运输问题的基本思想是 设立虚供地或虚需求点，化为供求平衡的标准形式 。4、在图论中，称 无圈的 连通图为树。5、运输问题中求初始基本可行解的方法通常有 最小费用法 、 西北角法 两种方法。二、（每小题5分，共10分）用图解法求解下列线性规划问题： 、1）max z = 6x1+4x2解：此题在“运筹学复习参考资料.doc”中已有，不再重复。 、2） min z =3x1+2x2解：可行解域
2、为abcda，最优解为b点。由方程组 解出x1=11，x2=0X*=（11，0）Tmin z =311+20=33三、（15分）某厂生产甲、乙两种产品，这两种产品均需要A、B、C三种资源，每种产品的资源消耗量及单位产品销售后所能获得的利润值以及这三种资源的储备如下表所示：ABC甲94370乙46101203602003001）建立使得该厂能获得最大利润的生产计划的线性规划模型；（5分）2）用单纯形法求该问题的最优解。（10分）解：1）建立线性规划数学模型：设甲、乙产品的生产数量应为x1、x2，则x1、x20，设z是产品售后的总利润，则max z =70x1+120x2s.t.2）用单纯形法求最
3、优解：加入松弛变量x3，x4，x5，得到等效的标准模型：max z =70x1+120x2+0 x3+0 x4+0 x5s.t.列表计算如下：CBXBb70120000Lx1x2x3x4x50x336094100900x420046010100/30x53003（10）0013000000701200000x324039/5010- 2/5400/130x420（11/5）001 - 3/5100/11120x2303/10 100 1/1010036120001234000120x31860/1100139/1119/1170x1100/11100 5/11- 3/11120x2300/11
4、010- 3/22 2/11701200170/1130/11000-170/1130/11X*=（，0，0）Tmax z =70+120=四、（10分）用大M法或对偶单纯形法求解如下线性规划模型：min z =5x12x24x3解：用大M法，先化为等效的标准模型：max z/ =5x12x24x3s.t.增加人工变量x6、x7，得到：max z/ =5x12x24x3Mx6Mx7s.t大M法单纯形表求解过程如下：CBXBb52400MMLx1x2x3x4x5x6x7Mx64（3）1210104/3Mx71063501015/39M4M7MMMMM9M54M27M4MM005x14/311/3
5、2/31/301/30Mx72011（2）12115-M5/3-M10/3-2M+5/3M2M5/3-M0M1/3M2/32M5/3M3M+5/305x15/311/25/601/601/610/30x410（1/2）1/211/211/2255/225/605/605/601/21/605/6MM+5/652x12/3101/311/311/3x2201121215211/311/311/3001/311/3M+1M+1/3x*=（，2，0，0，0）T最优目标函数值min z =max z/ =（）=五、（15分）给定下列运输问题：（表中数据为产地Ai到销地Bj的单位运费）B1 B2 B3
6、B4siA1A2A31 2 3 48 7 6 59 10 11 9108015dj8 22 12 181）用最小费用法求初始运输方案，并写出相应的总运费；（5分）2）用1）得到的基本可行解，继续迭代求该问题的最优解。（10分）解：用“表上作业法”求解。1）先用最小费用法（最小元素法）求此问题的初始基本可行解： 地产用费地销B1B2B3B4SiA112341082A2876520218A3910119302010dj8221218 606082B1B2A1初始方案：218B3B4A22010B2B3A3Z=18+22+62+518+1020+1110=4242）用闭回路法，求检验数：地产用费地销
7、B1B2B3B4SiA11230421082A284726520218A390101191302010dj8221218 6060=10，其余0选作为入基变量迭代调整。用表上闭回路法进行迭代调整：地产用费地销B1B2B3B4SiA11231431082A283716520128A390101119302010dj8221218 6060调整后，从上表可看出，所有检验数0，已得最优解。最优方案为：82B1B2A1128B3B4A22010B2B4A3最小运费Z=18+22+612+58+1020+910=414六、（8分）有甲、乙、丙、丁四个人，要分别指派他们完成A、B、C、D四项不同的工作，每
8、人做各项工作所消耗的时间如下表所示：ABCD甲21097乙154148丙13141611丁415139问：应该如何指派，才能使总的消耗时间为最少？解：用 “匈牙利法”求解。效率矩阵表示为：行约简标号列约简 至此已得最优解：使总消耗时间为最少的分配任务方案为：甲C，乙B，丙D，丁A此时总消耗时间W=9+4+11+4=28七、（6分）计算下图所示的网络从A点到F点的最短路线及其长度。此题在“运筹学参考综合习题（我站搜集信息自编）.doc”中已有。19B1245534168E19435FC2AB2265E274145247D1C1D3C3D2B3解：此为动态规划之“最短路问题”，可用逆向追踪“图上标号法”解决如下：144519B131245541490168E15943FC2AB2117265E2741425247D1C1D3C3D2B31287最佳策略为：AB2C1D1E2F此时的最短距离为5+4+1+2+2=14第 11 页 共 11 页
