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

第1页共9页1工商管理07级（本）已考《运筹学》试题参考．．答案资料加工、整理人——杨峰（函授总站高级讲师）※考试提示：可带计算器，另外建议带上铅笔、直尺、橡皮，方便绘图或分析。一、填空题（每空1分，共10分）1、运筹学是评价比较决策方案优劣的一种数量化决策方法。2、规划问题是指如何最合理的利用有限的资源，使产出的消耗最小。3、在线性问题的标准形式中，aij称为技术系数。4、在单纯形解法中，检查zj－cj，若所有的zj－cj≥0，则此解是最优解；若存在zj－cj≤0，则此解不是最优解。5、工作指派问题的数学模型可以看作运输规划问题的特例。6、在网络图中，弧的最大允许流通量称为容量，用cij表示。二、（25分）某公司生产甲、乙两种产品，生产所需原材料、工时和零件等有关数据如下：甲乙可用量原材料（吨/件）工时（工时/件）零件（套/件）2252.513000吨4000工时500套产品利润（元/件）43要求：⑴建立使利润最大的生产计划的数学模型；⑵将数学模型化为标准形式；⑶用表解形式的单纯形法求解；⑷求最大利润。解：⑴设甲、乙两种产品的生产数量为x1、x2，∵x1、x2≥0设z为产品售后总利润，则maxz=4x1+3x2s.t.0,50040005.253000222112121xxxxxxx⑵加入松弛变量x3，x4，x5，得到等效的标准形式：maxz=4x1+3x2+0x3+0x4+0x5第2页共9页2s.t.5,...,2,1,050040005.2530002251421321jxxxxxxxxxj⑶用表解形式的单纯形法求解，列表计算如下：CBXBb43000θLx1x2x3x4x50x33000221003000/2=15000x4400052.50104000/5=8000x5500（1）0001500/1=500000004↑30000x320000210-22000/2=10000x415000（2.5）01-51500/2.5=6004x150010001——4000403↑00-40x3800001-0.8（2）800/2=4003x26000100.4-2——4x150010001500/1=5004301.2-2000-1.22↑0x5400000.5-0.413x21400011-0.404x110010-0.50.4046004310.4000-1-0.40据上表，X*=（100，1400，0，0，400）T第3页共9页3⑷最大利润maxz=4×100+3×1400=4600（元）三、求解指派问题，并求出最小费用。（15分）Minz=4141ijijijxc（cij）4×4=1925211721161824232422172212820解：用“匈牙利法”求解。效率矩阵表示为：1925211721161824232422172212820284050286750144012)0(8403)0(28475)0(124)0(12*至此已得最优解：1000010000010010∴最小费用W=8+17+16+19=60四、下列是将产品从三个产地运往四个销地的运输费用表。（20分）销地产地A1A2A3A4产量19129650273776036591150需求量40406020要求：⑴用最小费用法建立运输计划的初始方案；⑵用位势法做最优解检验；⑶求最优解和最优方案的运费。运价产行约简标号列约简第4页共9页4解：⑴先用最小费用法（最小元素法）求此问题的初始基本可行解：A1A2A3A4Si19129650××30202737760×4020×3659115040×10×dj40406020160160∴最小费用法初始方案：初始方案总运费Z=9×30+6×20+3×40+7×20+6×40+9×10=980⑵按题目要求用位势法，作最优解检验：销地费用产地3020A3A414020A2A324010A1A33第5页共9页5A1A2A3A4ui190120960××3020277377－2－9×4020×36509110－740×10×vj9121618所有检验数如下：11＝1111vuc＝9－0－9＝0，12＝2112vuc＝12－0－12＝0，21＝1221vuc＝7－（－9）－9＝7，24＝4224vuc＝7－（－9）－18＝－2，32＝2332vuc＝5－（－7）－12＝0，34＝4334vuc＝11－（－7）－18＝0。⑶再用闭回路法求最优解和最优方案的运费，先检验：A1A2A3A4Si19－312－79650××302027－3377－360×4020×3650911－55040×10×dj40406020160160∵所有检验数ij≤0，∴该方案已是最优方案，不需要再调整。销地费用产地销地费用产地第6页共9页6最优方案的运费Z=9×30+6×20+3×40+7×20+6×40+9×10=980五、一个旅行者从A点出发，经过B、C、D等处，到达E。各地间距离如图中所示。问该旅行者应选择哪一条路线，使从A到E的总路程最短？（15分）⑴用标号法求解（可直接在图上标号）；⑵找最优路线，并在图上标出路线图；⑶计算最短路程。解：⑴此为动态规划之“最短路问题”，可用逆向追踪“图上标号法”解决如下：（如在考试中，可直接在上图中标出，不必另画，以节省时间！）62314551743334523AB1B3C1B2C3D1C2D2E33020A3A414020A2A324010A1A33第7页共9页7⑵最优路线如上图加粗线标出，即A→B3→C2→D2→E⑶此时从A到E的最短路程=3＋1＋3＋4=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解：可用“寻求网络最大流的标号法（福特—富克尔逊算法）”解决如下：62314551743334523AB1B3C1B2C3D1C2D2E34111143078647第8页共9页8（0，∞）（s，4）（s，3）（－4，1）（2，4）（4，2）（3，1）（0，∞）（s，1）（s，3）（－4，1）（2，1）（5，1）（3，1）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得到增广链µ（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开始，重新标号。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，v2，v4，v3，v5，vt），=1，在µ上进行流量=1的调整，得可行流f'如下图所示：第9页共9页9（0，∞）（s，3）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）VtVs（0，1）(1，3)（0，1）(1，2)（2，5）（2，3）V5V1（4，4）V3见上图，标号至点v1：标号过程无法进行，已得f'最大流。1V={vs，v1}，1V={v2，v3，v4，vt}截集（1V，1V）={（vs，v2），（v1，v3）}V（f'）=C（1V，1V）=6+4=10（2008年3月已考试题参考答案至此全部完毕，祝考试成功！）