第 1 页 共 11 页工商管理工商管理 03 级（本）级（本）已考已考运筹学运筹学试题试题参考答案参考答案一、填空题（每空 2 分，共 10 分） 1、在线性规划问题中，称满足所有约束条件方程和非负限制的解为 可行解可行解 。 2、在线性规划问题中，图解法适合用于处理 变量变量 为两个的线性规划问题。 3、求解不平衡的运输问题的基本思想是 设立虚供地或虚需求点，化为供求平衡的标准形式设立虚供地或虚需求点，化为供求平衡的标准形式 。 4、在图论中，称 无圈的无圈的 连通图为树。 5、运输问题中求初始基本可行解的方法通常有 最小费用法最小费用法 、 西北角法西北角法 两种方法。 二、 （每小题 5 分，共 10 分）用图解法求解下列线性规划问题：1）max z = 6x1+4x2 0781022122121xxxxxxx，解：此题在“运筹学运筹学复习参考资料复习参考资料.doc”中已有，不再重复。2）min z =3x1+2x20,137210422422121212121xxxxxxxxxx、第 2 页 共 11 页解：可行解域为 abcda，最优解为 b 点。由方程组 解出 x1=11，x2=0 02242221 xxxX*=（11，0）T 21 xxmin z =311+20=33三、 （15 分）某厂生产甲、乙两种产品，这两种产品均需要 A、B、C 三种资源，每种产品的资源消耗量及单位产品销售后所能获得的利润值以及这三种资源的储备如下表所示：ABC甲94370乙4610120360200300 1）建立使得该厂能获得最大利润的生产计划的线性规划模型；（5 分）2）用单纯形法求该问题的最优解。 （10 分）第 3 页 共 11 页解：1）建立线性规划数学模型：设甲、乙产品的生产数量应为 x1、x2，则x1、x20，设 z 是产品售后的总利润，则max z =70x1+120x2s.t. 0300103200643604921212121xxxxxxxx，2）用单纯形法求最优解：加入松弛变量 x3，x4，x5，得到等效的标准模型：max z =70x1+120x2+0 x3+0 x4+0 x5s.t. 5,.,2 , 1, 03001032006436049521421321jxxxxxxxxxxj列表计算如下：第 4 页 共 11 页70120000 CBXBbx1x2x3x4x5L0x336094100900x420046010100/30x53003（10）0013000000701200000x324039/5010- 2/5400/130x420（11/511/5）001 - 3/5100/11120120x2303/10 1 100 1/1010036120001234000120x31860/1100139/1119/117070x1100/111 100 5/11- 3/11120120x2300/11010- 3/22 2/11701200170/1130/11 1143000 000-170/1130/11X*=（，0，0）T11100 11300 111860max z =70+120=11100 11300 1143000四、 （10 分）用大用大 M 法法或对偶单纯形法求解如下线性规划模型：min z =5x12x24x30,10536423321321321xxxxxxxxx解：用大用大 M 法法，先化为等效的标准标准模型：第 5 页 共 11 页max z/ =5x12x24x3s.t.5,.,2 , 1, 01053642353214321jyxxxxxxxxj增加人工变量 x6、x7，得到：max z/ =5x12x24x3Mx6Mx7s.t7,.,2 , 1, 0105364237532164321jxxxxxxxxxxxj大 M 法单纯形表求解过程如下：第 6 页 共 11 页52400MM CBXBb x1x2x3x4x5x6x7LMx64（3 3）1210104/3Mx71063501015/39M4M7MMMMM9M54M27M4MM005x14/31 11/32/31/301/30Mx72011（2 2）12115-M5/3-M10/3-2M+5/3M2M5/3-M0M1/3M2/32M5/3M3M+5/305x15/311/25/601/601/610/30x410（1/21/2）1/21 11/211/2255/225/605/605/601/21/605/6MM+5/6x12/3101/311/311/352x2201 1121215211/311/311/3 322001/311/3M+1M+1/3x*=（，2，0，0，0）T32最优目标函数值 min z =max z/ =（）=322 322五、 （15 分）给定下列运输问题：（表中数据为产地Ai到销地Bj的单位运费）第 7 页 共 11 页B1 B2 B3 B4siA1A2A31 2 3 48 7 6 59 10 11 9108015dj8 22 12 181）用最小费用法求初始运输方案，并写出相应的总运费；（5 分）2）用 1）得到的基本可行解，继续迭代求该问题的最优解。 （10 分）解：用“表上作业法”求解。1）先用最小费用法（最小元素法）（最小元素法）求此问题的初始基本可行解： B1B2B3B4Si1 23 4A18 8 2 2 108 7 65 A2 2 2 181820910 119A3 2020 1010 30dj82212186060初始方案：Z=18 8+22 2+62 2+51818+102020+111010=424218B3B4A22010B2B3A3销地费 用 产地82B1B2A1第 8 页 共 11 页2）用闭回路法闭回路法，求检验数：B1B2B3B4Si1 230 042 2A18 8 2 2 1084 472 265 A2 2 2 1818209010 1191 1A3 2020 1010 30dj82212186060=10，其余034j选作为入基变量迭代调整。34x用表上闭回路法表上闭回路法进行迭代调整：B1B2B3B4Si1 231 143 3A18 8 2 2 1083 371 165 A2 1212 8 8209010 111 19A3 2020 101030dj82212186060调整后，从上表可看出，所有检验数0，已得最优解。j最优方案为：销地费 用 产地销地费 用 产地第 9 页 共 11 页最小运费 Z=18 8+22 2+61212+58 8+102020+91010=414六、 （8 分）有甲、乙、丙、丁四个人，要分别指派他们完成 A、B、C、D 四项不同的工作，每人做各项工作所消耗的时间如下表所示：ABCD甲21097乙154148丙13141611丁415139问：应该如何指派，才能使总的消耗时间为最少？解：用 “匈牙利法”求解。效率矩阵表示为： 91315411161413814415791025911005324100115780541200)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”中已有。中已有。解：此为动态规划之“最短路问题” ，可用逆向追踪“图上标号法”解决如下：43735191257962424 468515454AB1B2B3C1C2C3D1D2D3E1E2F第 11 页 共 11 页最佳策略为：AB2C1D1E2F此时的最短距离为 5+4+1+2+2=14八、此题在“运筹学参考综合习题 （我站搜集信息自编）.doc”中已有，不再重复。九、此题在“运筹学参考综合习题 （我站搜集信息自编）.doc”中已有，不再重复。十、此题在“运筹学参考综合习题 （我站搜集信息自编）.doc”中已有，不再重复。（2005 年年 3 月已考试题参考答案至此全部完毕，祝考试成功！）月已考试题参考答案至此全部完毕，祝考试成功！）17343201257962424 468515454AB1B2B3C1C2C3D1D2D3E1E2F59147711859121414