《运筹学参考综合习题》.doc

运筹学参考综合习题（我站搜集信息自编，非南邮综合练习题，仅供参考）资料加工、整理人杨峰（函授总站高级讲师）可能出现的考试方式（题型）第一部分 填空题（考试中可能有5个小题，每小题2分，共10分）考查知识点：几个基本、重要的概念第二部分 分步设问题（即是我们平常说的“大题”，共90分）参考范围：1、考两变量线性规划问题的图解法（目标函数为max z和min z的各1题）2、考线性规划问题的单纯形解法（可能2个题目：给出问题，要求建立线性规划模型，再用单纯形迭代表求解；考查对偶问题，要求写出原问题的线性规划模型之后写出其对偶问题的线性规划模型，然后用大M法求解其对偶问题，从而也得到原问题的最优解）3、必考任务分配（即工作指派）问题，用匈牙利法求解。4、考最短路问题（如果是“动态规划”的类型，则用图上标号法；如果是网络分析的类型，用TP标号法，注意不要混淆）5、考寻求网络最大流（用寻求网络最大流的标号法）6、考存储论中的“报童问题”（用概率论算法模型解决）未知是否必考的范围：1、运输规划问题（用表上作业法，包括先求初始方案的最小元素法和将初始方案调整至最优的表上闭回路法）；2、求某图的最小生成树（用破圈法，非常简单）考试提示：可带计算器，另外建议带上铅笔、直尺、橡皮，方便绘图或分析。第一部分 填空题复习参考一、线性规划部分：基本概念：定义：满足所有约束条件的解为可行解；可行解的全体称为可行（解）域。定义：达到目标的可行解为最优解。由图解法得到的三个结论：线性规划模型的可行解域是凸集；如果线性规划模型有唯一的最优解的话，则最优解一定是凸集（可行解域）的角顶；任何一个凸集，其角顶个数是有限的。有关运输规划问题的概念：设有m个产地Ai（i=1，2，m），n个销地Bj（j=1，2，n）, Ai产量（供应量）Si，Bj销量（需求量）di，若产、销平衡，则： 二、网络分析中的一些常用名词：定义：无方向的边称为边；有方向的边称为弧。定义：赋“权”图称为网络。定义：有向图中，若链中每一条弧的走向一致，如此的链称为路。闭链称为圈。闭回路又称为回路。定义：在图G中任两点间均可找到一条链，则称此图为连通图。无重复边与自环的图称为连通图。定义：树是无圈的连通图。树的基本性质：树的任两点之间有且只有一条链；若图的任两点之间有且只有一条链，则此图必为树；有n个顶点的树有n1条边；任何一个具有p个顶点，p1条边的连通图必为树。有关网络最大流的几个概念：网络的每条弧上的最大通过能力称为该弧的容量。若fij=cij，称弧（ci，cj）为饱和弧；若fijcij，称弧（ci，cj）为非饱和弧。第一部分到此结束第二部分 分步设问题复习参考除了已公布的运筹学复习参考资料.doc中的题目外，补充几个参考题目：给出问题，要求建立线性规划模型的补充题：补例1：某厂生产两种不同类型的通信电缆，出售后单位产品的收益分别为6万元和4万元，生产单位甲产品要消耗2单位的A资源（铜）和1单位的B资源（铅）；生产单位乙产品要消耗1单位的A资源和1单位的B资源。现该厂拥有10单位的A资源、8单位的B资源。经调查，市场对乙产品的最大需求量为7单位，对甲产品的需求没有限制。问：该厂应如何组织生产才能使产品的售后的收益为最大？（只要求建立线性规划模型，不必进行求解）解：设甲、乙产品的生产数量应为x1、x2 x1、x20设z是产品售后的总收益，则max z= 6x1 +4x2 s.t.补例2：某工厂生产中需要某种混合料，它应包含甲、乙、丙三种成份。这些成份可由市场购买的A、B、C三种原料混合后得到。已知各种原料的单价、成份含量以及各种成份每月的最低需求量如下表：份成量含料原 A B C各种成分的每月最低需求量甲乙丙1 1 11/2 1/2 1/42 1 120610各种原料的单价（万元/吨）6 3 2问：该厂每月应购买各种原料多少吨，才能使在满足需求的基础上使用于购买原材料所耗费的资金为最少？（该题只要求建立线性规划模型，不必进行求解）解：现设x1、x2、x2为A、B、C原料的购买数量， x1、x2、x30设z为总的耗费资金，则min z= 6x1+3x2+2x3s.t.运输规划问题补充题：类型一：供求平衡的运输规划问题（又称“供需平衡”、“产销平衡”）补例：课本P52例110（此题务必熟悉）解：用“表上作业法”求解。先用最低费用法（最小元素法）求此问题的初始基础可行解：地产用费地销1234产量Si19129650302027377604020365911504010产量Sj40406020 160160初始方案：401013340202323020341运费Z=930+620+340+720+640+910=980元对的初始可行解进行检验（表上闭回路法）：地产用费地销1234产量Si19312796503020273377360402036509115504010产量Sj40406020 160160从上表可看出，所有检验数0，已得最优解。（上述初始方案就是最优方案，不需要调整）最优方案的运费就是Z=930+620+340+720+640+910=980元类型二：供求不平衡的运输规划问题若，则是供大于求（供过于求）问题，可设一虚销地Bn+1，令ci,n+1=0，dn+1=，转化为产销平衡问题。若，则是供小于求（供不应求）问题，可设一虚产地Am+1，令cm+1,j=0，sm+1=，转化为产销平衡问题。（=1，2，m；=1，2，n）补例：求下列运输问题的最优解：地产费运地销B1 B2 B3siA1A2A35 1 76 4 63 2 5108015dj75 20 50105145解：，此为供小于求（供不应求）问题，可设一虚产地A4，令c4,j=0，s4=，（i=1,2,3,4；j=1,2,3）转化为产销平衡问题。仍用“表上作业法”求解。先用最低费用法（最小元素法）求此问题的初始基础可行解：地产用费地销B1B2B3产量SiA1531751010A26416807010A3325215510A4000104040产量Sj752050 145145初始方案：510B1B2A37010B1B3A2B210A1Z=110+670+610+35+210=525对的初始可行解进行迭代（表上闭回路法），求最优解：地产用费地销B1B2B3产量SiA1521741010A264680601010A3321521515A4000204040产量Sj752050 145145用表上闭回路法调整后，从上表可看出，所有检验数0，已得最优解。B2106010B1B3A2最优方案：B115A3B210A1最小运费Z=110+660+410+610+315=515任务分配（工作指派）问题补充题：类型一：求极小值的匈牙利法：（重点掌握这种基本问题）补例：某游泳队教练需选派一组运动员去参加4200混合接力赛，候选运动员有甲、乙、丙、丁、戊五位，他们游仰泳、蛙泳、蝶泳、自由泳的成绩，根据统计资料算得平均值（以秒计）如下表：员队种绩成泳 A B C D甲乙丙丁戊37.7 43.4 33.3 29.232.9 33.1 28.5 26.433.8 42.2 38.9 29.637 34.7 30.4 28.535.4 41.8 33.6 31.1问：教练应选派哪四位运动员，各游什么泳姿，才能使总的成绩最好？解：用“匈牙利法”求解。因人数多于任务数，作如下处理：效率矩阵表示为：列约简标号（cij）= 至此已得最优解：使总成绩最好（耗时最少）的分配任务方案为：甲自由泳，乙蝶泳，丙仰泳，丁蛙泳此时总成绩W=29.2+28.5+33.8+34.7=126.2秒类型二：求极大值的匈牙利法：min z=max（z）（cij）（Mcij）=（bij），（cij）中最大的元素为Mmax z=补例：有四个人分别操作四台机器，每人操作不同机器的产值如下表：员队种绩成泳 A B C D甲乙丙丁10 9 8 73 4 5 62 1 1 24 3 5 6求对四个工人分配不同的机器使得总产值为最大的方案。解：用求极大值的“匈牙利法”求解。效率矩阵表示为：行约简MCijM=10 标号列约简 使总产值为最大的分配任务方案为：甲A，乙C，丙B，丁D此时总产值W=10+5+1+6=22动态规划问题（只要求“最短路问题”）补充题：补例：某旅游者要从A地出发到终点F，他事先得到的路线图如下：19B124553168E19435FC2AB2165E274145247D1C1D3C3D2B3各点之间的距离如上图所示数值，旅游者沿着箭头方向行走总能走到F地，试找出AF间的最短路线及距离。解：此为动态规划之“最短路问题”，可用逆向追踪“图上标号法”解决如下：144519B131245541490168E15943FC2AB2117265E2741425247D1C1D3C3D2B31287最佳策略为：AB2C1E1D2F此时的最短距离为5+4+1+2+2=14v5v2网络分析问题补充题：8补例1：221732v7v4v174431v6v3求v1到v7的最短路径和最短距离。解：此为网络分析之“最短路问题”，可用顺向追踪“TP标号法”解决如下：94v2v5852217732v7v4v1744310v6v314v1到v7的最短路径是：v1v3v4v7，最短距离为1+4+2=7。补例2：教材P124图48v3v1补例3：求下图所示网络的最大流：（4，0）（5，0）（3，0）（3，0）（1，0）（1，0）vtvs（2，0）（5，0）（2，0）v4v2图中为（Cij，fij）解：此为网络分析之“寻求网络最大流问题”，可用“寻求网络最大流的标号法（福特富克尔逊算法）”解决如下：标号过程：1、给vs标上（0，）；2、检查vs，在弧（vs，v1）上，fs1=0，Cs1=3，fs1Cs1，给v1标号(s，l(v1)，其中，（s，3）v1v3（4，0）（5，0）（3，0）（s，）（3，0）（1，0）（1，0）vtvs（2，0）（5，0）（2，0）v4v2（s，5）同理，给v2标号(s，l(v2)，其中，3、检查v1，在弧（v1，v3）上，f13=0，C13=4，f13C13，给v3标号(1，l(v3)，其中，（1，3）（s，3）v1v3（4，0）（5，0）（3，0）（s，）（3，0）（1，0）（1，0）vtvs（2，0）（5，0）（2，0）v4v2（2，2）（s，5）检查v2，同理，给v4标号(2，l(v4)，其中，4、检查v4，在弧（v4，vt）上，f4t=0，C4t=2，f13C13，给vt标号(4，l(vt)，其中，vt得到标号，标号过程结束。（1，3）（s，3）v1v3（4，0）（5，0）（3，0）（4，2）（s，）（3，0）（1，0）（1，0）vtvs（2，0）（5，0）（2，0）v4v2（2，2）（s，5）调整过程：从vt开始逆向追踪，找到增广链。（1，3）（s，3）v1v3（4，0）（5，0）（3，0）（2，2）（s，）（3，0）（1，0）（1，0）vtvs（2，0）（5，0）（2，0）v4v2（2，2）（s，5）（vs，v2，v4，vt），=2，在上进行流量=2的调整，得可行流f 如图所示：（1，3）（s，3）v1v3（4，0）（5，0）（3，0）（1，0）（4，2）（s，）（3，0）（1，0）vtvs（2，2）（5，2）（2，2）v4v2（2，2）（s，5）去掉各点标号，从vs开始，重新标号。（1，3）（s，3）v1v3（4，0）（5，0）（3，0）（3，3）（s，）（3，0）（1，0）（1，0）vtvs（2，2）（5，2）（2，2）v4v2（t，2）（s，3）vt又得到标号，标号过程结束。再次从vt开始逆向追踪，找到增广链。（1，3）（s，3）v1v3（4，0）（5，0）（3，0）（3，3）（s，）（3，0）（1，0）（1，0）vtvs（2，2）（5，2）（2，2）v4v2（t，2）（s，3）（vs，v1，v3，vt），=3，在上进行流量=3的调整，得可行流f 如图所示：（1，3）（s，3）v1v3（4，3）（5，3）（3，3）（3，3）（s，）（3，0）（1，0）（1，0）vtvs（2，2）（5，2）（2，2）v4v2（t，2）（s，3）去掉各点标号，从vs开始，重新标号。（1，1）（2，1）v1v3（4，3）（5，3）（3，3）（3，1）（s，）（3，0）（1，0）（1，0）vtvs（2，2）（5，2）（2，2）v4v2（s，3）vt又得到标号，标号过程结束。再次从vt开始逆向追踪，找到增广链。（1，1）（2，1）v1v3（4，3）（5，3）（3，3）（3，1）（s，）（3，0）（1，0）（1，0）vtvs（2，2）（5，2）（2，2）v4v2（s，3）（vs，v2，v1，v3，vt），=1，在上进行流量=1的调整，得可行流f 如图所示：（1，1）（2，1）v1v3（4，4）（5，4）（3，3）（3，1）（s，）（3，0）（1，0）（1，1）vtvs（2，2）（5，3）（2，2）v4v2（s，3）去掉各点标号，从vs开始，重新标号。v1v3（4，4）（5，4）（3，3）（s，）（3，0）（1，0）（1，1）vtvs（2，2）（5，3）（2，2）v4v2（s，2）标号至点v2：标号过程无法进行，所以f 即为最大流。v1v3（4，4）（5，4）（3，3）（s，）（3，0）（1，0）（1，1）vtvs（2，2）（5，3）（2，2）v4v2（s，2）=vs，v2，=v1，v3，v4，vt截集（，）=（vs，v1），（v2，v1），（v2，v4）V（ f ）=C（，）=3+1+2=6v3v1补例4：求下图所示网络的最大流：（9，5）（5，5）（8，6）（6，2）（2，2）（5，1）vtvs（10，5）（7，4）（9，7）v4v2图中为（Cij，fij）解：此为网络分析之“寻求网络最大流问题”，可用“寻求网络最大流的标号法（福特富克尔逊算法）”解决如下：标号过程：1、给vs标上（0，）；2、检查vs，在弧（vs，v1）上，fs1=6，Cs1=8，fs1Cs1，给v1标号(s，l(v1)，其中，v3v1（s，2）（9，5）（5，5）（8，6）（0，）（6，2）（2，2）（5，1）vtvs（10，5）（7，4）（s，3）（9，7）v4v2同理，给v2标号(s，l(v2)，其中，3、检查v1，在弧（v1，v3）上，f13=5，C13=9，f13C13，给v3标号(1，l(v3)，其中，v3v1（1，2）（s，2）（9，5）（5，5）（8，6）（0，）（6，2）（2，2）（5，1）vtvs（10，5）（7，4）（2，2）（s，3）（9，7）v4v2检查v2，同理，给v4标号(2，l(v4)，其中，4、检查v3，在弧（v3，vt）上，f3t=C3t=5，不满足标号条件，v3v1（1，2）（s，2）（9，5）（5，5）（8，6）（0，）（6，2）（2，2）（5，1）vtvs（10，5）（7，4）（2，2）（s，3）（9，7）v4v2检查v4，在弧（v4，vt）上，f4t=5，C4t=10，f13C13，给vt标号(4，l(vt)，其中，vt得到标号，标号过程结束。调整过程：从vt开始逆向追踪，找到增广链。（s，2）v1v3（1，2）（9，5）（5，5）（8，6）（0，）（6，2）（2，2）（5，1）vtvs（10，5）（7，4）（9，7）v4v2（2，2）（s，3）（vs，v2，v4，vt），=2，在上进行流量=2的调整，得可行流f 如图所示：（1，2）（s，2）v3v1（9，5）（5，5）（8，6）（0，）（6，2）（2，2）（5，1）vtvs（10，7）（7，6）v4v2（9，9）（2，2）（s，3）去掉各点标号，从vs开始，重新标号。（1，2）（s，2）v3v1（9，5）（5，5）（8，6）（4，2）（0，）（6，2）（2，2）（5，1）vtvs（10，7）（7，6）v4v2（