运筹学参考综合习题汇总.doc

1、运筹学参考综合习题（我站搜集信息自编，非南邮综合练习题， 仅供参考）可能出现的考试方式（题型）第一部分 填空题（考试中可能有5个小题，每小题2分，共10分）考查知识点：几个基本、重要的概念第二部分 分步设问题（即是我们平常说的“大题”，共90分）参考范围：1、考两变量线性规划问题的图解法（目标函数为max z和min z的各 1题）2、考线性规划问题的单纯形解法（可能2个题目： 给出问题，要求建立线性规划模型，再用单纯 形迭代表求解； 考查对 偶问题，要求写出原问题的线性规划模型之后写出其对偶问题的线性规划模型，然后用大M 法求解其对偶问题，从而也得到原问题的最优解）3、必考任务分配（即工作指

2、派）问题，用匈牙利法求解。4、考最短路问题（如果是“动态规划”的类型，则用图上标号法；如果是网络分析的类型，用 TP标 号法，注意不要混淆）5、考寻求网络最大流（用寻求网络最大流的标号法）6、考存储论中的“报童问题”（用概率论算法模型解决）未知是否必考的范围：1、运输规划问题（用表上作业法，包括先求初始方案的最小元素法和将初始方案调整至最优的表上闭回路法）；2、求某图的最小生成树（用破圈法，非常简单）考试提示：可带计算器，另外建议带上铅笔、直尺、橡皮，方便绘图或分析。第一部分 填空题复习参考一、线性规划部分：基本概念：定义：满足所有约束条件的解为可行解；可行解的全体称为可行（解）域。定义：达到

3、目标的可行解为最优解。由图解法得到的三个结论：线性规划模型的可行解域是凸集；如果线性规 划模型有唯一的最 优解的话，则最优解一定是凸集（可行解域）的角顶；任何一个凸集，其角顶个数是有限的。有关运输规划问题的概念：设有m个产地Ai（i=1，2， m），n个销地Bj（j=1，2 ，n）, Ai产量（供应量）Si， Bj销量（需求量） di，若产、销平衡，则：二、网络分析中的一些常用名词：定义：无方向的边称为边；有方向的边称为弧。定义：赋“权 ”图称为网 络。定义：有向图中，若链中每一条弧的走向一致，如此的链称为路。闭链称为圈。闭回路又称为回路。定义：在图G中任两点间均可找到一条链，则称此图为连通图

4、。无重复边与自环的图称为连通图。定义：树是无圈的连通图。树的任两点之间有且只有一条链；若图 的任两点之间有且只有一条链，则此图必为树；有n 个顶点的树有n1条边；任何一个具有p个顶点，p1条边的连通图必为树。有关网络最大流的几个概念：网络的每条弧上的最大通过能力称为该弧的容量。若fij=cij，称弧（ci，cj ）为饱 和弧；若fij ij ，称弧（ c i ， c j ）为非饱和弧。 第一部分到此结束第二部分 分步设问题复习参考除了已公布的运筹学复习参考资料.doc中的题目外，补充几个参考题目：给出问题，要求建立线性规划模型的补充题：补例1：某厂生产两种不同类型的通信电缆，出售后单位产品的收

5、益分别为6万元和4万元，生产单位甲产品要消耗2单位的A 资源（铜）和 1单位的B资源（铅）；生产单位乙产品要消耗1单位的A资源和1单位的B 资源。现该厂 拥有10单位的A 资源、8单位的B资源。经调查，市场对乙产品的最大需求量为7单位， 对甲产品的需求没有限制。问：该厂应如何组织生产才能使产品的售后的收益为最大？（只要求建立线性规划模型，不必进行求解）解：设甲、乙产品的生产数量应为x1、x2 x1、x20s.t.补例2：某工厂生产中需要某种混合料，它应包含甲、乙、丙三种成份。这些成份可由市场购买的A、B、C三种原料混合后得到。已知各种原料的单价、成份含量以及各种成份每月的最低需求量如下表：份成

6、量含料原A B C各种成分的每月最低需求量甲乙丙1 1 11/2 1/2 1/42 1 120610各种原料的单价（万元/吨） 6 3 2 问：该厂每月应购买各种原料多少吨，才能使在满足需求的基础上使用于购买原材料所耗费的资金为最少？（该题只要求建立线性规划模型，不必进行求解）解：现设x1、x2、x2为A 、B、C原料的购买数量， x1、x2、x30s.t.运输规划问题补充题：类型一：供求平衡的运输规划问题（又称“供需平衡”、“产销平衡”）补例：课本P52 例110（此 题务必熟悉）解：用“表上作业法”求解。先用最低费用法（最小元素法）求此问题的初始基础可行解：地产用费地销1 2 3 4 产量

7、Si1 9 12 9 6 50 30 202 7 3 7 7 60 40 20 3 6 5 9 11 5040 10 销量dj40 40 60 20 160160初始方案：321运费Z=930 +620+340+720+640+910=980元对的初始可行解进行检验（表上闭回路法）：地产用费地销1 2 3 4 产量Si1 9 3 12 7 9 6 50 30 202 7 3 3 7 7 3 60 40 20 3 6 5 0 9 115 5040 10 销量dj40 40 60 20 160160从上表可看出，所有检验数 0，已得最优解。（上述初始方案就是最优方案，不需要调整）最优方案的运费就是

8、Z=9 30+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,

9、2,3,4；j=1,2,3）转化为产销平衡问题。仍用“表上作业法”求解。先用最低费用法（最小元素法）求此问题的初始基础可行解：地产用B1 B2 B3产量Si费地销A1 5 3 1 7 5 10 10 A2 6 4 1 6 8070 10A3 3 2 5 2 155 10 A4 0 0 0 1 0 40 40销量dj75 20 50145145初始方案：A3A2A1Z=110+670+610+35+210=525对的初始可行解进行迭代（表上闭回路法），求最优解：地产用费地销B1 B2 B3产量SiA1 5 2 1 7 4 10 10 A2 6 4 6 8060 10 10A3 3 2 1 5 2 15