《《运筹学》期末考试试题及参考答案.docx》由会员分享，可在线阅读，更多相关《《运筹学》期末考试试题及参考答案.docx（12页珍藏版）》请在三一文库上搜索。
1、 .运筹学试题参考答案一、填空题（每空 2 分，共 10 分）1、在线性规划问题中，称满足所有约束条件方程和非负限制的解为 可行解 。2、在线性规划问题中，图解法适合用于处理 变量 为两个的线性规划问题。3、求解不平衡的运输问题的基本思想是 设立虚供地或虚需求点，化为供求平衡的标准形式 。4、在图论中，称 无圈的 连通图为树。5、运输问题中求初始基本可行解的方法通常有 最小费用法 、 西北角法 两种方法。二、（每小题 5 分，共 10 分）用图解法求解下列线性规划问题：1）max z = 6x +4x122x + x 1012x + x 812x 72x，x 01、2解：此题在“运筹学复习参考
2、资料.doc”中已有，不再重复。2）min z =3x +2x122x + 4x 2212- x + 4x 10122x - x 712x -3x 112 , 0x x、12解：Word 资料 .可行解域为 abcda，最优解为 b 点。 +2x 4x 22=由方程组12解出 x =11，x =0x = 0122 x X = 1 =（11，0） *Tx 2min z =311+20=33三、（15 分）某厂生产甲、乙两种产品，这两种产品均需要 A、B、C 三种资源，每种产品的资源消耗量及单位产品销售后所能获得的利润值以及这三种资源的储备如下表所示：A9B4C3甲乙704610120360200
3、300Word 资料 .1）建立使得该厂能获得最大利润的生产计划的线性规划模型；（5 分）2）用单纯形法求该问题的最优解。（10 分）解：1）建立线性规划数学模型：设甲、乙产品的生产数量应为 x 、x ，则 x 、x 0，设 z 是产品售后的总利润，1212则max z =70x +120x12s.t. + 9x 4x 36012+ 6x 2004x123x +10x 30012x ，x 0122）用单纯形法求最优解：加入松弛变量 x ，x ，x ，得到等效的标准模型：345max z =70x +120x +0 x +0 x +0 x12345s.t. + += 360= 2009x 4x
4、x1234x + 6x+ x1243x +10x+ x = 300125x 0, j = 1,2,.,5j列表计算如下：Word 资料 .bBBLxxxxx12345x1000010000100003xx45xxx1202x1860/11100/11300/113xx1207001200-170/11 30/111003001860X =（ ， ， ，0，0）*T111110011300 43000max z =70 +120 =111111四、（10 分）用大 M 法或对偶单纯形法求解如下线性规划模型：min z =5x 2x 4x123Word 资料 .3x + x + 2x 41236x
5、 + 3x + 5x 10123x , x , x 0123解：用大 M 法，先化为等效的标准模型：max z =5x 2x 4x/123s.t.3 + + 2 -= 4- x =10x xx x12346x + 3x + 5x1235y 0, j =1,2,.,5j增加人工变量 x 、x ，得到：67max z =5x 2x 4x Mx Mx/12367s.t3 + + 2 -+x= 4x xx x123466x + 3x + 5x- x+ x =1012357x 0, j =1,2,.,7j大 M 法单纯形表求解过程如下：Word 资料 .50bBBLxxxxxxx1234567xxMM4
6、/35/3667MMMMM4M21/317M42/3151/31-M5/3 -M10/3 -2M+5/32M5/3-M0M1/31/2M 3M+5/35010110/3205000M1M5210511/31/312230011/3 +1 M+1/3M2x =（ ，2，0，0，0）*T3Word 资料 .22最优目标函数值 min z =max z/ =（ ）=2233AB五、（15 分）给定下列运输问题：（表中数据为产地 到销地 的单位运费）ijsi11d8221218j1）用最小费用法求初始运输方案，并写出相应的总运费；（5 分）2）用 1）得到的基本可行解，继续迭代求该问题的最优解。（10
7、 分）解：用“表上作业法”求解。1）先用最小费用法（最小元素法）求此问题的初始基本可行解：费销用BBBBSi地1234产地189AAA1020308181011201060dj1882212Word 资料 .初始方案：BBBBBB822010123423AAA123218Z=18+22+62+518+1020+1110=4242）用闭回路法，求检验数：费销BBBBSi用地1234产地189AAA10203021811011201060188221260 =10，其余 0ss34j选 作为入基变量迭代调整。x34用表上闭回路法进行迭代调整：Word 资料 .费销BBBBSi用地1234产地189
8、AAA10203010112060188221260调整后，从上表可看出，所有检验数 0，已得最优解。j最优方案为：BBBBB821282010123424AAA123B最小运费 Z=18+22+612+58+1020+910=414六、（8 分）有甲、乙、丙、丁四个人，要分别指派他们完成 A、B、C、D 四项不同的工作，每人做各项工作所消耗的时间如下表所示：Word 资料 .甲乙丙丁151341416131415119问：应该如何指派，才能使总的消耗时间为最少？解：用 “匈牙利法”求解。效率矩阵表示为：2 10 915 4 1413 14 164 15 1370112871055列约简标号行
9、约简8110430590119(0)1128(0)3254(0)1122555(0)340*5(0)40*5(0)40*120*12 0*6(0)3 134(0)3540*2(0)3(0)1000010100100000至此已得最优解：10Word 资料 .使总消耗时间为最少的分配任务方案为：甲C，乙B，丙D，丁A此时总消耗时间 W=9+4+11+4=28七、（6 分）计算下图所示的网络从 A 点到 F 点的最短路线及其长度。此题在“运筹学参考综合习题（我站搜集信息自编）.doc”中已有。9BD4111523EE48165ABDF2229421474572BCD333解：此为动态规划之“最短路问题”，可用逆向追踪“图上标号法”解决如下：Word 资料 .549BCD4111123E819065ABCDF22297E4214742572BCD3331287最佳策略为：AB C D E F2112此时的最短距离为 5+4+1+2+2=14Word 资料