《工程硕士运筹学及重点方案课件》由会员分享，可在线阅读，更多相关《工程硕士运筹学及重点方案课件（235页珍藏版）》请在金锄头文库上搜索。
1、1工程硕士运筹学内蒙古工业大学管理学院内蒙古工业大学管理学院 课程内容n绪论绪论n线性规划基础线性规划基础n线性规划的图解法、用线性规划的图解法、用Excel解解LP问题问题n整数规划整数规划n运输问题运输问题n目标规划目标规划n图论图论n动态规划动态规划n网络计划技术网络计划技术23第0章绪论IntroductionstoOperationsResearch运筹学的实用价值公司公司应应用用问题问题收益收益/效果效果惠普公司预测消费者的购买行为，从而优化库存2009至2011年，创造了1.17亿美元的收益中国工商银行银行网点的城市布局问题2006至2011年，苏州因此增加了10.4亿美元的存款
2、IHG 洲际酒店集团解决酒店房间的定价问题2011年增加1.45亿美元的收益，并预计推广后未来每年将带来4亿美元的收益Hub Group哈勃货运集团提高场地管理和集装箱分配 2008年收益增加了3%，获得了1,100万美元的净汇报Petrobras优化直升飞机在海上石油平台之间的飞行路线每年节省超过2千万美元4nZARA（全球1500家门店）、P&G（15亿）5运筹学学科特点n1-科学性n它是在科学方法论的指导下通过一系列规范化步骤。6运筹学学科特点n2-实践性n运筹学以实际问题为分析对象；n分析结果必须用于指导实际系统的运行。n适应性和鲁棒性鲁棒性Robustness，原是统计学中的一个专门
3、术语，20世纪70年代初开始在控制理论控制理论的研究中流行起来，用以表征控制系统对特性或参数扰动的不敏感性。即当应用问题的背景受到一定程度的干扰时，最即当应用问题的背景受到一定程度的干扰时，最优解能够继续正常运行的程度。优解能够继续正常运行的程度。7运筹学学科特点n3-系统性n用系统的观点来分析研究对象，通过协调各组成部分之间的关系和利害冲突，使整个系统达到最优状态。n实际问题的多目标“天性”，各目标没有统一的度量标准。8运筹学学科特点n4-优化方案n强调是最优的解决方案，而不是任意的一个可行方案，或者只是对现状的“改进”方案；n当研究问题从数学分析上存在多个或无穷最优解时，不刻意去搜索出所有
4、最优解，而是只需找出其中一个最优解；n当研究问题过于复杂时，运筹学更倾向于搜索出一个“效率解”。9运筹学学科特点n5-综合性n运筹学研究是一种综合性的研究，它涉及问题的方方面面，应用多学科的知识，因此，要由一个各方面的专家组成的小组来完成。运筹学求解问题的一般思路n1.明确问题，收集数据边界、目标量化、变量、参数、约束n2.建立模型，数学模型：模型检验n3.选取方法，进行求解：遗传算法等n4.验证方案，实施方案n5.方案程序化，模块化n6.方案实施，效果分析10运筹学求解问题的一般思路1112第1章线性规划基础(IntroductiontoLinearProgramming)目标n1.常见线性
5、规划问题的数学建模思路n2.建模的适用范围n3.“解”的概念n4.图解法n5.EXCEL求解一般线性规划问题（练习）1314线性规划的定义n在满足一组线性约束条件（等式或不等式）的前提下，使得某一个线性目标函数取得极值（最大值或最小值）。这类问题的模型及其优化求解技术，被统称为线性规划(LinearProgramming,LP)。nInmathematics,LPproblemsareoptimizationproblemsinwhichtheobjectivefunctionandtheconstraintsarealllinear.线性规划数学模型n线性规划问题的一般模型15线性规划数学模
6、型n模型特点n1-所有表达式均为线性表达式n2-目标为求目标函数Z的最大值(max)或最小值(min)n3-约束条件为”/=”，没有”/”！n4-通常要求决策变量取值非负1617应用问题示例(1)-生产计划nF公司每周根据原材料M1和M2的采购数量来安排其产品A、B和C的生产计划。n问：这3种产品各应生产多少，能使F公司获得最大的利润？单位消耗单位消耗产品产品A产品产品B产品产品C可用可用资源资源原材料M1845320原材料M2221100单位产品利润542应用问题示例(2)-生产计划nA公司用M1,M2,M3和M4四种原材料，生产产品P1,P2和P3。这三种产品由这四种原材料混合而成（产品重
7、量为四种原材料重量之和）。18产品原材料配方加工成本市场售价P1M1：不超过产品重量的35%301200M2：不少于产品重量的45%M3：不超过产品重量的50%M4：产品重量的20%P2M1：不超过产品重量的60%40850M2：不少于产品重量的20%M4：产品重量的10%P3M1：不超过产品重量的75%50900应用问题示例(2)n原材料M3和M4采购量超过市场供应总量的一半。n采购预算费用为25万元人民币。n问：根据产品的市场价格以及原材料价格，公司应如何采购以获得最多的利润？19原材料原材料M1M2M3M4市场供给300200400300市场价格300600400500应用问题示例(2)
8、n建模思路1-20应用问题示例(2)n正确的建模方法-21应用问题示例(2)22应用问题示例(3)-财务计划n某集团公司未来6年年初的现金需求（万元）如下所示。为此，公司决定在今年年底一次性划拨一笔资金，未来6年不再划拨。23年份年份123456现金现金350 405 355 260 215 230应用问题示例(3)n公司可以通过多种投资形式减少资金的需求：n1-银行一年期的定期存款，年利率为3%；n2-国债（只能在第1年年初购买；国债的实际购买价格要高于其票面价格，且只能在到期日按票面价格收回本金）n问：集团公司最少需要划拨多少资金，并如何投资，才能满足未来6年的现金需求？24债券类型票面价
9、格实际购买价格年利率到期年限110,00012,0007.84210,00014,30010.75应用问题示例(3)n由于6年内不再追加投资，因此6年内的投资（银行定期存款方式）必然不能超过当年现金需求的余额。并且，由于投资总能够获得更多的回报（103%），所以投资等于当年现金需求的余额！25应用问题示例(3)n采用表格形式更加直观展示出投资与回报。n年末的收益可以作为下一年年初的投资。回报回报第第1年年年末年末第第2年年年末年末第第3年年年末年末第第4年年年末年末第第5年年年末年末第第6年年年末年末存款1.031.031.031.031.031.03债券10.0780.0780.0781.0
10、78债券20.1070.1070.1070.1071.10726应用问题示例(3)27回报回报第第1年年年末年末第第2年年年末年末第第3年年年末年末第第4年年年末年末第第5年年年末年末第第6年年年末年末存款1.031.031.031.031.031.03债券10.0780.0780.0781.078债券20.1070.1070.1070.1071.107应用问题示例(3)n完整问题模型如下：28应用问题示例(4)-生产计划nN公司生产两种产品P1和P2，这2种产品都是由组件C1,C2和C3各1件装配而成。n需求为1600件P1和1000件P2。n共有100个正常工时和最多60个加班工时，每个加
11、班工时将额外增加12元的运营成本。n问：如何安排生产和外购，才是最经济？29组件生产工时生产成本外购成本C11.51.01.2C2产品P14.08.08.5产品P23.06.07.0C3产品P12.01.52.0产品P23.01.82.1应用问题示例(4)n根据问题描述，可以定义自行生产和外购的组件数量为决策变量。并且，外购组件的数量与生产能力也有关，因此需要定义实际加班工时为决策变量，即：30应用问题示例(4)31应用问题示例(5)-运输与分销n运输与分销问题n问：如何安排物流路线，实现总运输成本最小。32应用问题示例(5)n定义决策变量为各条路线上的运输量，各变量对应的路线如下所示。33应
12、用问题示例(5)n对于此类以图形方式给出的物流问题，存在以下函数关系，即图中每个节点，都必须满足“输入=输出”。34应用问题示例(5)n源头节点“工厂13”，关系为“产量+运入量=运出量”。35应用问题示例(5)n中间节点“分销中心”，关系为“运入量=运出量”。36应用问题示例(5)n终止节点“仓库12”，关系为“运入量=运出量+需求量”。37应用问题示例(6)-套裁下料问题n某建筑公司需要钢管规格和数量分别为：3m的600根、4m的300根、5m的200根。n如果只能选择购入长度为11m的钢管自行切割，M公司至少应采购多少根11m的钢管？38应用问题示例(6)n某建筑公司需要钢管规格和数量分
13、别为：3m的600根、4m的300根、5m的200根。n如果只能选择购入长度为11m的钢管自行切割，M公司至少应采购多少根11m的钢管？39应用问题示例(6)40应用问题示例(6)n思考题：如果目标函数改为“如果购入这些长度为11m的钢管自行切割，RE公司应如何切割废料最少？”4142线性规划模型的假设条件n比例性假定：要求目标函数值、约束条件左端取值与决策变量的取值呈严格的比例关系。线性规划模型的假设条件4344线性规划问题的标准图解法线性规划问题的标准图解法n对于只包含2个变量的线性规划问题，可以通过标准图解法来求解。其解题步骤为：45标准图解法示例1n用标准图解法求下面的线性规划问题（例
14、1-8）标准图解法示例146标准图解法示例2n应用标准图解法求解线性规划问题（例1-9）47标准图解法示例24849线性规划问题的重要推论n1-如果线性规划问题的可行域非空且有界，那么线性规划问题一定有最优解；n2-如果线性规划问题的可行域无界，那么该问题可能有无界解；n3-如果线性规划问题的最优解在可行域的两个顶点上同时得到，那么这两个顶点连线上的所有点都是最优解（有无穷多最优解）；n4-如果线性规划问题的可行域为空，意味着该线性规划问题无可行解。50简化的图解法n对于可行域为封闭凸多边形的两变量线性规划问题，可以采用简化的图解法求解：只需要穷举出可行域的所有顶点，计算每一个顶点的目标函数值
15、，就可以找出最优解。简化的图解法示例1n线性规划问题（例1-8）51顶顶点点坐坐标标目目标标函数函数值值X1X2A000B4012C4327D2636E063052Excel求解线性规划问题n“规划求解”工具主界面Excel求解LP问题示例1n线性规划问题（例1-8）53练习题-图解以下线性规划问题5455n某手工作坊生产的竹制座椅中需要用到3种规格楠竹片，每张椅子需要长度为60cm、40cm和30cm的楠竹片2、6和2片。可以在市场上采购这些规格的现货，也可以将作坊仓库中长度为110cm的楠竹片切割成所需的规格，但每切割1次会发生1cm的长度损耗。问：如果要制作100张竹制座椅，该作坊的仓库
16、中至少要有多少条长度为110cm的楠竹片，才不用去市场上采购？试建立本问题的线性规划模型。56575859第2章整数规划(IntegerLinearProgramming)基本概念n线性规划模型中增加了决策变量的整数约束，这类数学规划问题被称为整数规划(IntegerLinearProgramming,ILP)问题。n整数规划模型虽然只是在线性规划模型中增加了决策变量的整数约束，但是其求解过程却变得非常复杂。（简单的四舍五入？）n车辆调度、人员安排、产品产量60基本概念n根据全部还是部分全部还是部分决策变量必须满足整数约束，整数规划问题可分为两类：n纯整数规划（PureIntegerProgramming,PIP）n混合整数规划（MixedIntegerProgramming,MIP）n根据整数变量取值的范围，整数规划问题还可分为：n一般整数规划-整数变量的取值可以是任意非负整数n0-1整数规划（BinaryIntegerProgramming,BIP）-要求决策变量只能取值0或者161基本概念62n一般整数规划问题的数学模型基本概念63n0-1整数规划问题的数学模型应用问题建模n设施
