运筹学参考综合习题.doc

第  PAGE 29 页 共  NUMPAGES 29 页 《运筹学参考综合习题》 （我站搜集信息自编，非南邮综合练习题，仅供参考） 资料加工、整理人——杨峰（函授总站高级讲师） 可能出现的考试方式（题型）  HYPERLINK \l 第一部分 第一部分 填空题（考试中可能有5个小题，每小题2分，共10分） ——考查知识点：几个基本、重要的概念  HYPERLINK \l 第二部分 第二部分 分步设问题（即是我们平常说的“大题”，共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个顶点的树有n－1条边； ④任何一个具有p个顶点，p－1条边的连通图必为树。 有关网络最大流的几个概念： 网络的每条弧上的最大通过能力称为该弧的容量。 若fij=cij，称弧（ci，cj）为饱和弧；若fijcij，称弧（ci，cj）为非饱和弧。  HYPERLINK \l 要求掌握的各部分知识点 第一部分到此结束 第二部分 分步设问题复习参考 除了已公布的《运筹学》复习参考资料.doc中的题目外，补充几个参考题目： ※给出问题，要求建立线性规划模型的补充题： 补例1：某厂生产两种不同类型的通信电缆，出售后单位产品的收益分别为6万元和4万元，生产单位甲产品要消耗2单位的A资源（铜）和1单位的B资源（铅）；生产单位乙产品要消耗1单位的A资源和1单位的B资源。现该厂拥有10单位的A资源、8单位的B资源。经调查，市场对乙产品的最大需求量为7单位，对甲产品的需求没有限制。问：该厂应如何组织生产才能使产品的售后的收益为最大？（只要求建立线性规划模型，不必进行求解） 解：设甲、乙产品的生产数量应为x1、x2 ∵ x1、x2≥0 设z是产品售后的总收益，则max z= 6x1 +4x2 s.t. 补例2：某工厂生产中需要某种混合料，它应包含甲、乙、丙三种成份。这些成份可由市场购买的A、B、C三种原料混合后得到。已知各种原料的单价、成份含量以及各种成份每月的最低需求量如下表： 份 成 量 含 料 原  A B C各种成分的每月 最低需求量甲 乙 丙1 1 1 1/2 1/2 1/4 2 1 120 6 10各种原料的单价（万元/吨）6 3 2——问：该厂每月应购买各种原料多少吨，才能使在满足需求的基础上使用于购买原材料所耗费的资金为最少？（该题只要求建立线性规划