运筹学复习专题-201110.ppt

运筹学复习专题,华中科技大学管理学院 管理科学与信息管理系 授课教师：傅 小 华 Telephone:1398601962 E-mail:fuxhua@,考试的学科范围 应考范围包括： 线性规划 动态规划 整数规划 网络规划,评价目标运筹学考试的目标在于考查学生运筹学的基本概念、基本理论和方法的掌握以及对实际问题的分析、建立必要的数学模型和求解问题的能力考生应能： 正确理解运筹学中的基本概念和基本理论 正确分析实际问题并建立相应的数学模型 掌握求解运筹学中常见问题的方法 能正确的解释所求问题的计算结果考纲所规定出题形式与考试范围数学规划建模专题线性规划专题动态规划专题整数规划专题图与网络规划专题存储论专题,考纲所规定出题形式与考试范围,答题时间：180分钟 试卷分数：满分为150分 试卷结构及考查比例： 问题建模40% 基本理论和方法40% 分析题20%考纲所规定出题形式与考试范围,线性规划 线性规划问题及其数学模型线性规划问题图解法、解的基本性质、单纯形法的基本原理、线性规划对偶理论及对偶单纯形法、灵敏度分析、运输问题 动态规划 多阶段决策问题、动态规划基本方程、动态规划的递推方法、解析法和数值法。

考纲所规定出题形式与考试范围,整数规划 整数规划问题的数学模型；分枝定界法与割平面法的基本原理；0-1规划问题与隐枚举法；分配问题 图与网络规划 图与网络的基本概念，树与最小树问题，最短路问题，网络最大流问题，最小费用最大流问题 存贮论 确定型存贮模型，随机型存贮模型,考纲所规定出题形式与考试范围,参考教材 杨超. 运筹学, 北京, 科学出版社, 2004. 钱颂迪. 运筹学, 北京, 清华大学出版社, 1993. 邓成梁. 运筹学的原理与方法, 武汉, 华中理工大学出版社, 1996,数学规划建模专题,特点 题量大、单题分值高 综合性强 出题范围大 多态性 不易辨别对错对建模者的综合素质要求高 基本功扎实 逻辑思辨与推理能力强 细致周到 思维稳定性,相关考研真题 2007 5 8(20) 9 2006 1(20) 4(20) 8 2005 1(20) 4(15) 2004 3 4(10) 10(20) 2002 1(10) 4(10),数学规划建模专题,特点 题量大、单题分值高 综合性强 出题范围大 多态性 不易辨别对错对建模者的综合素质要求高 基本功扎实 逻辑思辨与推理能力强 细致周到 思维稳定性,数学规划的建模原则 容易理解建立的模型不但要求建模者理解，还应当让有关人员理解。

这样便于考察实际问题与模型的关系，使得到的结论能够更好地应用于解决实际问题 容易查找模型中的错误这个原则的目的显然与(1)相关常出现的错误有：书写错误、公式错误 容易求解对线性规划来说，容易求解问题主要是控制问题的规模，包括决策变量的个数和约束条件的个数这条原则的实现往往会与(1)发生矛盾，在实现时需要对两条原则进行统筹考虑建立数学规划模型的四个步骤明确问题，确定决策变量；决策变量是构成解决方案的要素或单元，决策变量的组合构成一个可行解决方案明确约束条件并用决策变量的等式或不等式表示；尽可能分类描述，防止差错和遗漏用决策变量的函数表示目标，并确定是求极大（Max）、极小（Min）还是特定值；根据决策变量的物理性质研究变量是否有非负性或上下界例 某昼夜服务的公交线路每天各时间段内所需司机和乘务人员数如下：,设司机和乘务人员分别在各时间段一开始时上班，并连续工作8h，问该公交线路怎样安排司机和乘务人员，既能满足工作需要，又配备最少司机和乘务人员?,一、工作安排问题,线性规划问题建模,解：设 xi 表示第i班次时开始上班的司机和乘务人员数,这样我们建立如下的数学模型 目标函数：Min z =x1 + x2 + x3 + x4 + x5 + x6 约束条件：s.t. x1 + x6 ≥ 60x1 + x2 ≥ 70x2 + x3 ≥ 60x3 + x4 ≥ 50x4 + x5 ≥ 20x5 + x6 ≥ 30x1,x2,x3,x4,x5,x6 ≥ 0,，整数,例某工厂要做100套钢架，每套用长为2.9 m, 2.1m, 1.5m的圆钢各一根。

已知原料每根长7.4 m，问：应如何下料，可使所用原料最省？,解:考虑下列各种下料方案（按一种逻辑顺序给出）,把各种下料方案按剩余料头从小到大顺序列出,二、下料问题,假设 x1,x2,x3,x4,x5 分别为上面前 5 种方案下料的原材料根数我们建立如下的数学模型 目标函数： Min z=x1 + x2 + x3 + x4 + x5 约束条件： s.t. x1 + 2x2 + x4 = 100 2x3 + 2x4 + x5 = 1003x1 + x2 + 2x3+ 3x5 = 100x1,x2,x3,x4,x5 ≥ 0,模型1,假设 x1,x2,x3,x4,x5,x6,x7,x8 分别为上面前 8种方案下料的原材料根数我们建立如下的数学模型 目标函数： Min z = 0.1x1+0.3x2+0.9x3+1.1x5+0.2x6+0.8x7+1.4x8 约束条件： s.t. 2x1+x2+x3+x4 = 100 2x2+x3 +3x5+2x6+ x7 = 100x1 +x3+3x4 +2x6+3x7+4x8 = 100x1,x2,x3,x4,x5,x6,x7,x8 = 0，整数,模型2,假设 x1,x2,x3,x4,x5,x6,x7,x8 分别为上面前 8种方案下料的原材料根数。

我们建立如下的数学模型 目标函数： Min z = x1+x2+x3+x4+x5+x6+x7+x8 约束条件： s.t. 2x1+x2+x3+x4 = 100 2x2+x3 +3x5+2x6+ x7 = 100x1 +x3+3x4 +2x6+3x7+4x8 = 100x1,x2,x3,x4,x5,x6,x7,x8 = 0，整数,模型3,例:明兴公司生产甲、乙、丙三种产品，都需要经过铸造、机加工和装配 三个车间甲、乙两种产品的铸件可以外包协作，亦可以自行生产，但产品丙必须本厂铸造才能保证质量数据如下表问：公司为了获得最大利润，甲、乙、丙三种产品各生产多少件？甲、乙两种产品的铸造中，由本公司铸造和由外包协作各应多少件？,三、生产决策问题,解：设 x1 ， x2 ， x3分别为三道工序都由本公司加工的甲、乙、丙三种产品的件数，x4 ， x5分别为由外协铸造再由本公司机加工和装配的甲、乙两种产品的件数。

求 xi 的利润:利润 = 售价 - 各成本之和可得到 xi（i=1,2,3,4,5）的利润分别为15、10、7、13、9元这样我们建立如下数学模型：目标函数: Max z=15x1+10x2+7x3+13x4+9x5 约束条件： s.t. 5x1+10x2+7x3 ≤ 80006x1+4x2+8x3+6x4+4x5 ≤120003x1+2x2+2x3+3x4+2x5 ≤ 10000x1,x2,x3,x4,x5 ≥ 0,某厂生产Ⅰ、Ⅱ、Ⅲ三种产品，产品Ⅰ依次经过设备A、B加工，产品Ⅱ依次经过设备A、C加工，产品Ⅲ依次经过设备B、C加工，已知有关数据如下表所示，问如何安排生产计划才能获利最大？试建立该问题的线性规划模型例:某工厂要用三种原料1、2、3混合调配出三种不同规格的产品甲、乙、丙，数据如下表问：该厂应如何安排生产，使利润收入为最大？,四、混合问题,解：设 xij 表示第 i 种（甲、乙、丙）产品中原料 j 的含量这样我们建立数学模型时，要考虑：,对于甲： x11，x12，x13；对于乙： x21，x22，x23；对于丙： x31，x32，x33；对于原料1： x11，x21，x31；对于原料2： x12，x22，x32； 对于原料3： x13，x23，x33；,目标函数：利润最大，利润 = 收入 - 原料支出 约束条件：规格要求 4 个；供应量限制 3 个。

Max z = -15x11+25x12+15x13-30x21+10x22-40x31-10x33 s.t. 0.5 x11-0.5 x12 -0.5 x13 ≥ 0 （原材料1不少于50%）-0.25x11+0.75x12 -0.25x13 ≤ 0 （原材料2不超过25%）0.75x21-0.25x22 -0.25x23 ≥ 0 （原材料1不少于25%）-0.5 x21+0.5 x22 -0.5 x23 ≤ 0 （原材料2不超过50%）x11+x21+x31≤ 100 (供应量限制）x12+x22+x32≤ 100 (供应量限制）x13+x23+x33≤ 60 (供应量限制）xij≥0 ,i = 1,2,3; j = 1,2,3,设某种动物每天至少需要700克蛋白质、30克矿物质、100毫克维生素现有5种饲料可供选用，各种饲料营养成分的含量与单价如下表所示：试建立既满足动物生长的营养需要、又使费用最省的选用饲料方案的线性规划模型例：某部门现有资金200万元，今后五年内考虑给以下的项目投资已知：项目A ：从第一年到第五年每年年初都可投资，当年末能收回本利110%；项目B：从第一年到第四年每年年初都可投资，次年末能收回本利125%，但规定每年最大投资额不能超过30万元；项目C：需在第三年年初投资，第五年末能收回本利140%，但规定最大投资额不能超过80万元；项目D：需在第二年年初投资，第五年末能收回本利155%，但规定最大投资额不能超过100万元。

据测定每万元每次投资的风险指数如下表：,五、连续投资问题,求：,解：1）确定决策变量：连续投资问题设 xij ( i = 1-5，j = 1、2、3、4)表示第 i 年初投资于A(j=1)、B(j=2)、C(j=3)、D(j=4)项目的金额这样我们建立如下决策变量：A x11 x21 x31 x41 x51 B x12 x22 x32 x42C x33 D x24,a）应如何确定这些项目的每年投资额，使得第五年年末拥有资金的本利金额为最大？ b）应如何确定这些项目的每年投资额，使得第五年年末拥有资金的本利在330万元的基础上使得其投资总的风险系数为最小？,2）约束条件：第一年：A当年末可收回投资，故第一年年初应把全部资金投出去，于是： x11+ x12 = 200第二年：B次年末才可收回投资故第二年年初的资金为1.1x11，于是： x21 + x22+ x24 = 1.1x11第三年：年初的资金为1.1x21+1.25x12，于是 ： x31 + x32+ x33 = 1.1x21+ 1.25x12第四年：年初的资金为1.1x31+1.25x22，于是： x41 + x42 = 1.1x31+ 1.25x22第五年：年初的资金为1.1x41+1.25x32，于是： x51 = 1.1x41+ 1.25x32B、C、D的投资限制： xi2 ≤ 30 ( i=1，2，3，4 )，x33 ≤ 80，x24 ≤ 100,a) Max z=1.1x51+1.25x42+1.4x33+1.55x24s.t. x11+ x12 = 200x21 + x22+ x24 = 1.1x11x31 + x32+ x33 = 1.1x21+ 1.25x12x41 + x42 = 1.1x31+ 1.25x22x51 = 1.1x41+ 1.25x32xi2 ≤ 30 ( i =1、2、3、4 )， x33 ≤ 80，x24 ≤ 100 xij≥0(i=1,2,3,4,5；j=1,2,3,4）,。