工商管理07级(本)已考运筹学试题参考答案.doc

工商管理07级（本）已考运筹学试题参考答案资料加工、整理人杨峰（函授总站高级讲师）考试提示：可带计算器，另外建议带上铅笔、直尺、橡皮，方便绘图或分析。一、填空题（每空1分，共10分）1、运筹学是评价比较决策方案优劣的一种 数量化 决策方法。2、规划问题是指如何最合理的利用 有限的资源 ，使 产出的 消耗最小。3、在线性问题的标准形式中，aij称为 技术系数 。4、在单纯形解法中，检查zjcj，若所有的zjcj0，则此解 是最优解 ；若存在zjcj0，则此解 不是最优解 。5、工作指派问题的数学模型可以看作 运输规划 问题的特例。6、在网络图中，弧的最大允许流通量称为 容量 ，用 cij 表示。二、（25分）某公司生产甲、乙两种产品，生产所需原材料、工时和零件等有关数据如下：甲 乙可用量原材料（吨/件）工时（工时/件）零件（套/件）2 25 2.513000吨4000工时500套产品利润（元/件） 4 3要求：建立使利润最大的生产计划的数学模型； 将数学模型化为标准形式；用表解形式的单纯形法求解； 求最大利润。解：设甲、乙两种产品的生产数量为x1、x2， x1、x20设z为产品售后总利润，则max z = 4x1+3x2s.t.加入松弛变量x3，x4，x5，得到等效的标准形式：max z= 4x1+3x2+0 x3+0 x4+0 x5s.t.用表解形式的单纯形法求解，列表计算如下：CBXBb43000Lx1x2x3x4x50x33000221003000/2 =15000x4400052.50104000/5 =8000x5500（1）0001500/1 =50000000 430000x320000210-22000/2 =10000x415000（2.5）01-51500/2.5 =6004x150010001400040 300-40x3800001-0.8（2）800/2 =4003x26000100.4-24x150010001500/1 =5004301.2-2000-1.2 20x5400000.5-0.413x21400011-0.404x110010-0.50.4046004310.4000-1-0.40据上表，X*=（100，1400，0，0，400）T 最大利润max z =4100+31400=4600（元）三、求解指派问题，并求出最小费用。（15分）Min z =（cij）44=解：用 “匈牙利法”求解。效率矩阵表示为：行约简标号列约简 至此已得最优解：最小费用W=8+17+16+19=60四、下列是将产品从三个产地运往四个销地的运输费用表。（20分）运销价 地产产 地A1A2A3A4产量19129650273776036591150需求量40406020要求：用最小费用法建立运输计划的初始方案；用位势法做最优解检验；求最优解和最优方案的运费。解：先用最小费用法（最小元素法）求此问题的初始基本可行解：地产用费地销A 1A 2A 3A 4Si19129650302027377604020365911504010dj40406020 1601603020A3A41最小费用法初始方案：4010A1A334020A2A32初始方案总运费Z=930+620+340+720+640+910=980按题目要求用位势法，作最优解检验：地产用费地销A 1A 2A 3A 4ui19012096030202773772940203650911074010vj9121618 所有检验数如下：9090 ， 120120 ，7（9）97 ， 7（9）182 ，5（7）120 ，11（7）180。再用闭回路法求最优解和最优方案的运费，先检验：地产用费地销A 1A 2A 3A 4Si19312796503020273377360402036509115504010dj40406020 160160所有检验数0， 该方案已是最优方案，不需要再调整。3020A3A414010A1A334020A2A32最优方案的运费Z=930+620+340+720+640+910=980五、一个旅行者从A点出发，经过B、C、D等处，到达E。各地间距离如图中所示。问该旅行者应选择哪一条路线，使从A到E的总路程最短？（15分）用标号法求解（可直接在图上标号）；找最优路线，并在图上标出路线图；计算最短路程。71B15D1443362EC25B2A34231D2C1335C3B3解：此为动态规划之“最短路问题”，可用逆向追踪“图上标号法”解决如下：（如在考试中，可直接在上图中标出，不必另画，以节省时间！）411731B15D1443377011462EC25B2A34231D2C13435C3B386最优路线如上图加粗线标出，即AB3C2D2E此时从A到E的最短路程=3134=11六、用标号法求下图所示网络流的最大流。（15分）要求：画出每次迭代图；在迭代图中画出增广链；求网络中的最大流。V2（2，6）V4 （2，6） （4，7）VtVs（0，1）(2，3) （0，1）(0，2)（2，5）（1，3） V5V1（4，4）V3解：可用“寻求网络最大流的标号法（福特富克尔逊算法）”解决如下：（2，4）（s，4）V2（2，6）V4（4，2） （2，6） （4，7）（0，）VtVs（0，1）(2，3) （0，1）(0，2)（3，1）（2，5）（1，3） V5（4，1）（s，3）V1（4，4）V3得到增广链（vs，v2，v4，vt），=3，在上进行流量=3的调整，得可行流f 如下图所示：V2（5，6）V4 （5，6） （7，7）VtVs（0，1）(2，3) （0，1）(0，2)（2，5）（1，3） V5V1（4，4）V3去掉各点标号，从vs开始，重新标号。（2，1）（s，1）V2（5，6）V4（5，1） （5，6） （7，7）（0，）VtVs（0，1）(2，3) （0，1）(0，2)（3，1）（2，5）（1，3） V5（4，1）（s，3）V1（4，4）V3得到增广链（vs，v2，v4，v3，v5，vt），=1，在上进行流量=1的调整，得可行流f 如下图所示：V2（6，6）V4 （6，6） （7，7）VtVs（0，1）(1，3) （0，1）(1，2)（2，5）（2，3） V5V1（4，4）V3去掉各点标号，从vs开始，重新标号。V2（6，6）V4 （6，6） （7，7）（0，）VtVs（0，1）(1，3) （0，1）(1，2)（2，5）（2，3） V5（