工程硕士运筹学课件及重点讲义

1工程硕士运筹学内蒙古工业大学管理学院内蒙古工业大学管理学院 课程内容n绪论绪论n线性规划基础线性规划基础n线性规划的图解法、用线性规划的图解法、用Excel解解LP问题问题n整数规划整数规划n运输问题运输问题n目标规划目标规划n图论图论n动态规划动态规划n网络计划技术网络计划技术23第0章绪论IntroductionstoOperationsResearch运筹学的实用价值公司公司应用问题应用问题收益收益/效果效果惠普公司预测消费者的购买行为，从而优化库存2009至2011年，创造了1.17亿美元的收益中国工商银行银行网点的城市布局问题2006至2011年，苏州因此增加了10.4亿美元的存款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，原是统计学中的一个专门术语，20世纪70年代初开始在控制理论控制理论的研究中流行起来，用以表征控制系统对特性或参数扰动的不敏感性。即当应用问题的背景受到一定程度的干扰时，最即当应用问题的背景受到一定程度的干扰时，最优解能够继续正常运行的程度。优解能够继续正常运行的程度。7运筹学学科特点n3-系统性n用系统的观点来分析研究对象，通过协调各组成部分之间的关系和利害冲突，使整个系统达到最优状态。n实际问题的多目标“天性”，各目标没有统一的度量标准。8运筹学学科特点n4-优化方案n强调是最优的解决方案，而不是任意的一个可行方案，或者只是对现状的“改进”方案；n当研究问题从数学分析上存在多个或无穷最优解时，不刻意去搜索出所有最优解，而是只需找出其中一个最优解；n当研究问题过于复杂时，运筹学更倾向于搜索出一个“效率解”。9运筹学学科特点n5-综合性n运筹学研究是一种综合性的研究，它涉及问题的方方面面，应用多学科的知识，因此，要由一个各方面的专家组成的小组来完成。运筹学求解问题的一般思路n1.明确问题，收集数据边界、目标量化、变量、参数、约束n2.建立模型，数学模型：模型检验n3.选取方法，进行求解：遗传算法等n4.验证方案，实施方案n5.方案程序化，模块化n6.方案实施，效果分析10运筹学求解问题的一般思路1112第1章线性规划基础(IntroductiontoLinearProgramming)目标n1.常见线性规划问题的数学建模思路n2.建模的适用范围n3.“解”的概念n4.图解法n5.EXCEL求解一般线性规划问题（练习）1314线性规划的定义n在满足一组线性约束条件（等式或不等式）的前提下，使得某一个线性目标函数取得极值（最大值或最小值）。这类问题的模型及其优化求解技术，被统称为线性规划(LinearProgramming,LP)。nInmathematics,LPproblemsareoptimizationproblemsinwhichtheobjectivefunctionandtheconstraintsarealllinear.线性规划数学模型n线性规划问题的一般模型15线性规划数学模型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。这三种产品由这四种原材料混合而成（产品重量为四种原材料重量之和）。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)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债券类型票面价格实际购买价格年利率到期年限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.078债券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个加班工时，每个加班工时将额外增加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应用问题示例(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某建筑公司需要钢管规格和数量分别为：3m的600根、4m的300根、5m的200根。n如果只能选择购入长度为11m的钢管自行切割，M公司至少应采购多少根11m的钢管？39应用问题示例(6)40应用问题示例(6)n思考题：如果目标函数改为“如果购入这些长度为11m的钢管自行切割，RE公司应如何切割废料最少？”4142线性规划模型的假设条件n比例性假定：要求目标函数值、约束条件左端取值与决策变量的取值呈严格的比例关系。线性规划模型的假设条件4344线性规划问题的标准图解法线性规划问题的标准图解法n对于只包含2个变量的线性规划问题，可以通过标准图解法来求解。其解题步骤为：45标准图解法示例1n用标准图解法求下面的线性规划问题（例1-8）标准图解法示例146标准图解法示例2n应用标准图解法求解线性规划问题（例1-9）47标准图解法示例24849线性规划问题的重要推论n1-如果线性规划问题的可行域非空且有界，那么线性规划问题一定有最优解；n2-如果线性规划问题的可行域无界，那么该问题可能有无界解；n3-如果线性规划问题的最优解在可行域的两个顶点上同时得到，那么这两个顶点连线上的所有点都是最优解（有无穷多最优解）；n4-如果线性规划问题的可行域为空，意味着该线性规划问题无可行解。50简化的图解法n对于可行域为封闭凸多边形的两变量线性规划问题，可以采用简化的图解法求解：只需要穷举出可行域的所有顶点，计算每一个顶点的目标函数值，就可以找出最优解。简化的图解法示例1n线性规划问题（例1-8）51顶点顶点坐标坐标目标目标函数值函数值X1X2A000B4012C4327D2636E063052Excel求解线性规划问题n“规划求解”工具主界面Excel求解LP问题示例1n线性规划问题（例1-8）53练习题-图解以下线性规划问题5455n某手工作坊生产的竹制座椅中需要用到3种规格楠竹片，每张椅子需要长度为60cm、40cm和30cm的楠竹片2、6和2片。可以在市场上采购这些规格的现货，也可以将作坊仓库中长度为110cm的楠竹片切割成所需的规格，但每切割1次会发生1cm的长度损耗。问：如果要制作100张竹制座椅，该作坊的仓库中至少要有多少条长度为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设施布点问题n某市在其5个规划片区规划消防站设点，要求任意一个片区发生火警时，本片区或来自其它片区的消防车可以在15分钟内赶到。虽然在各片区各设一个消防站可以解决此问题，但为提高资源利用率，市政府提出消防站数量应尽可能少。64应用问题建模n背包问题（0-1）n某家庭计划自驾野外露营，出发前需考虑携带的物品，各物品的压缩体积及重要程度如表所示。由于其自驾车最大容纳的物品体积为650升，不可能所有物品都能装入车中。n问：应选择哪些物品出行？65应用问题建模n指派问题n有5项任务需要5个员工独立完成，由于能力差异，不同员工完成同一任务的执行成本不同。下表给出了员工i完成任务j的执行成本cij。n问：如何指派任务可以最经济地完成各项任务。66应用问题建模n将n项任务分配给n个人，约定每人只能完成一项工作，每项工作也只能由一个人来完成，但由于每个人能力各不相同，完成各项工作的收益和成本不同。根据不同的问题背景，可要求得到总利润最大或总成本最小的指派方案。这类问题在运筹学中被称为一种专门的问题：指派问题(AssignmentProblem)。67应用问题建模68n定义0-1变量xij(i,j=1,n)表示第i个人是否被指派完成第j项任务（0代表不指派，1代表指派），则指派问题的数学模型为：应用问题建模n含有互斥项目的计划n1.如果携带食物，就必须同时携带野外厨具和洗漱用品；n2.通信设备和应急医疗用品至少要携带1件；n3.帐篷和防晒防雨最多只能选择1项；n4.野外厨具、摄影器材和通信设备最多选2项。69应用问题建模n含有互斥约束条件的计划n某公司用两种原料E1和E2生产A、B两种产品，生产过程均需经过甲、乙两道工序。甲、乙两道工序又各可以采取2种生产工艺。n甲工序可以混合使用甲1和甲2两种工艺，而乙工序只能在乙1和乙2中选择其中一种工艺。n问：该公司应如何安排生产可使利润最大？70n在建模中对互斥的约束处理时，可以引入Mi来实现使某个约束条件有效或者冗余，其中Mi为任意大的正数。71固定成本问题n某工厂用两条生产线1和2生产两种产品A和B。这两条生产线每个月的额定工时分别为600和800小时，生产线1的生产率为产品A60件/小时或产品B45件/小时，生产线2的生产率为产品A35件/小时或产品B40件/小时；产品A和B的单位售价分别为12元/件和16元/件，生产产品A和B的固定成本分别为60000元和80000元。问：应如何安排生产可实现利润最大化？试建立本问题的混合整数规划模72n1）决策变量的定义：因为含有固定成本的问题，所以某产品的产量X和是否生产该产品的决策Y必须分别定义，而且它们必须是联动的，即如果某产品的产量X大于0，那么Y必须为1；而产品的产量X为0时，Y必须为0.否则，就有可能出现未生产产品X却减去了固定成本的问题，或者生产了却未减去固定成本的问题。这类问题必须引入任意大的正数M。73n2）正数M的引入XMY其中M为任意大的正数，即，只要Y=0，则X必须为0，Y=1时，X可以取任意正整数。74n所以，上题的决策变量定义如下：7576分枝定界法n分枝定界技术是一种求解优化问题的通用思想，其逻辑思路是：n把原始问题分解成若干个足够小的可以直接求解的子问题，此为分枝过程(Branching)；n对于每个子集及其对应的子问题，考察其最优解是否足够好是否可能包含原始问题的最优解，此为定界过程(Bounding)；n结束某些子问题的分枝过程，并根据定界过程的结果，放弃那些不可能包含原始问题最优解的子集及子问题，此为剪枝过程(Fathoming)。77割平面法78习题1n某大型社区临街的中式快餐店每天的营业时间为8:00到24:00，根据社区居民对早餐、中餐、晚餐和夜宵的需求不同，一天中不同时段对服务员的需求如图所示。79该店的员工分为两类。第一类是正式员工，分别在3个8小时时段上班：8:00-16:00、12:00-20:00，以及16:00-24:00，其工作时薪为14元/小时，且规定各时段正式员工数量不能少于3人；第二类是钟点工，可在8:00到24:00的任意时间工作，其工作时薪为12元/小时。问：应如何雇用正式员工和钟点工，可在人力资源成本最小的基础上满足需求？试建立本问题的整数规划模型。808182习题2n某公司计划在东、西、南三个地区建立销售网点，总共有7个备选地点 (=1,7)可供选择。现要求所设立的销售网点必须满足以下条件：在东部地区，1,2,3三个备选地点中至多选择两个地点设立销售网点；在西部地区，4,5两个备选地点中至少选择一个地点设立销售网点；在南部地区，6,7两个备选地点只能选一个设立销售网点；出于市场环境的考虑，如果方案中选择了2地点，必须选择在5同时设立销售网点。n若在备选地点设立销售网点需要投资万元，每年可获得利润万元。问：如果总投资预算为B万元，在哪些备选地点设立网点可获得最多的利润？试建立本问题的数学模型。8384习题3n某短途航空公司有10条联飞路线，可经停9个城市，下表给出了这10条飞行路线经停的城市和飞行总小时数（单位：小时）。试从这10条路线中选择3条路线，既能够满足飞行总时间最少的要求，又能够经停9个城市至少1次。给出本问题的0-1整数规划模型。8586n则其目标函数为：nMin（Z）=？8788习题4n某小提琴手作坊根据顾客提出的定制需求生产小提琴，价格和固定成本因定制需求而异。由于作坊的熟练技师有限(12人)，该手工作坊只能挑选部分订单，甚至只能部分完成订单所要求的数量。目前，作坊收到来自3家交响乐队的小提琴订单，下表给出了与此订单相关的制作成本和价格（单位：元）。n问：各订单各应接受多少台，可获得最多的利润？试建立本问题的整数规划模型。899091习题5n某工厂生产A和B两种型号的产品，其生产过程须经过甲、乙、丙三个流水线车间加工，其中，乙车间有两条加工效率不同的流水线乙1和乙2。n已知乙车间的两条流水线只能任选一条使用，问：如何安排生产可获得最大的利润。建立本问题的整数规划模型。929394第5章运输问题(TransportationProblems)基本概念n将某种物资从若干个产地运输到另外若干个销地，要求总运费最小的问题，这一类问题及其衍生问题统称为运输问题(TransportationProblem)。95引例nFreshFruit公司旗下有3个苹果种植基地，预计年产量分别为75、125和100吨，近期该公司与4个不同地区的客户签订了今年的苹果供应合同，其销量分别80、65、70和85吨。由于交通条件差异，从3个基地到4个客户所在地的单位运费不同，其运价表如表所示。96运输问题的数学模型97n运输问题通常为：从m个产地向n个销地运输某种物资，产地i到销地j的单位运费是cij（呈比例关系），产地i的产量是ai，销地j的销量是bj，要求找到使得总运费最小的运输方案。n当问题满足总产量与总销量相等，这类问题称为标准运输问题，或者产销平衡运输问题。运输问题的数学模型n标准运输问题的数学模型为：98标准运输问题的表上作业法n作为一种特殊的线性规划问题，标准运输问题模型并不包含天然的基变量和初始基本可行解，求解时需要在每个等式中引入人工变量，计算较为烦琐。n对于标准运输问题，在某种特殊形式的表格上来应用单纯形法，可使求解过程大大简化，这种方法叫作运输问题的表上作业法。n需特别强调的是，用表上作业法求解运输问题，产销平衡是一个基本前提。99标准运输问题的表上作业法n解题步骤：n1-初始化给出初始基本可行方案；n2-迭代n第1步基本可行方案的最优判定，判断当前基本可行方案是否最优。如果不是，进入第2步；n第2步基本可行方案的改进，然后返回第1步；100标准运输问题的表上作业法n运输问题作业表/产销平衡表101标准运输问题的表上作业法102n西北角法n从作业表的西北角往东南角逐步填写运输量。西北角法示例1103西北角法示例1104标准运输问题的表上作业法105n最小元素法n按照单位运费由低到高的次序来选择每次迭代中指派运输量的单元格。最小元素法示例1106最小元素法示例1107产销不平衡的运输问题示例108转运问题n(1)确定标准运输问题中的产地和销地：转运点既是产地，又是销地。也就是说，标准运输问题中的产地为原始转运问题中的产地和所有的转运点，销地为原始问题中的销地和所有的转运点。n(2)确定各产地的产量和销地的销量：将原始转运问题中产地的产量和销地的销量直接移植入标准运输问题；转运点的产量和销量相同，数值都为经过该转运点的最大可能转运量。109转运问题n(3)确定各产地与销地之间的单位运输费用：将原始问题中已知的两地之间的单位运输费用移植入标准运输问题；各转运点到其自身的单位运输费用为0；对于原始转运问题中不存在的运输路线，单位运费为无穷大，用任意大的正数 表示。110转运问题示例1111其它问题n一些应用问题虽然与物资运输、分销没有任何联系，但是由于其问题背景与运输问题有相似的形式，亦可将其抽象并建模为广义的产销平衡运输问题，从而采用运输问题的表上作业法进行求解。112习题1n求解如下运输问题：113习题2n求解如下运输问题：114习题3n某水产品销售公司每天从3个水产品养殖厂采购新鲜产品运往4个批发市场。3个养殖厂每天提供的水产品数量为2500、3000、4500公斤，4个批发市场每日的需求量分别为2000、2500、3000、2500公斤。根据表5所示3个养殖厂的采购成本价和4个批发市场的价格（单位：元/千克），公司应如何安排运输可使得总利润最大？115习题4n有3个牧业基地向4个城市提供鲜奶，4个城市每日的鲜奶需求量为16、30、24和30千升，3个基地的每日鲜奶供应量分别为30、40和50千升。已知运送每千升鲜奶的费用如表所示（单位：千元）。试确定最经济的鲜奶运输方案，且求出最小总运费。116习题5n假定习题3中城市A每天最低需求和总需求量分别为14和24千升，城市C每天最低需求和总需求量分别为25和40千升，其它城市需求量无变化，在最低需求必须满足的前提下，求解该问题，且求出最小总运费。117习题6n某干果公司从3个水果生产基地进货，在4个加工厂将水果加工成干果。假定3个水果基地的产量、4个加工厂的需求量，以及单位水果的运价如表所示。在最低需求必须满足的前提下，求总成本最低的运输方案。118习题7n已知2个供应方A1、A2以及3个需求方B1、B2、B3的运输问题的运价表如表所示。由于违约成本比较低，供应方A1、A2在运输成本较高的情景下可选择违约；同样，由于缺货损失比较低，需求方B1、B2、B3也可以在运输成本较低的情景下选择违约。问：根据表所示的缺货成本、违约成本，以及运输成本，如何安排运输可使得总运营成本最低？119第6章目标规划(GoalProgramming)120目标规划的提出n用线性规划来解决实际问题时，除了要满足比例性、可加性、可分性和确定性四个假设之外，通常还假设实际问题的求解目标是单一的，而且其约束条件是可以严格满足的。n线性规划的弊端：n现实决策问题通常都有多重的、可能相互冲突的目标n其约束条件也不一定必须全部严格满足n目标规划(GoalProgramming)的提出，正是为了消除或至少部分填补这种方法与实际应用之间的空白。1216.1.1引例-目标规划的数学模型在例1-1中，F公司每周需要根据下表确定产品A、B、C的产量，以获取最大的利润其线性规划数学模型为：本问题的求解目标是唯一的利润最大化。1226.1.1引例n但现实问题往往会有多个目标，比如把上面这个例子变成：例6-1在满足例1-1资源约束的前提下，按优先次序满足以下的目标：1.利润最好不少于200元；2.产品B为产品A的补充件，其产量最好低于产品A的一半；3.产品C为战略性产品，其产量最好不低于5件；4.原材料M2最好全部使用完且不超量；5.原材料M1比较稀缺，最好至少有10千克的剩余。问：F公司应如何安排生产计划，能够尽可能达成以上的经营目标？1236.1.1引例n问题的线性规划模型变为以下不等式组符合上述不等式组的解，就是本问题的解。经过计算，该不等式组无解。而在实际背景下，该问题显然是有解的。124 资源约束五个目标6.1.1引例n实际上，本问题前3个优先级的目标是可以完全达成的，第(4)、(5)个目标虽然无法完全达成，但是是允许妥协的只需要在前几个目标达成的基础上，尽可能满足即可。n问题出在建模的方式上n以上模型将5个原本有优先次序的、允许妥协的目标变成了必须同时严格满足的目标。因此，一个在现实中有解的多目标决策问题，以线性规划的思路建模可能就无解了。n目标规划的提出，正是针对这类线性规划无法解决的实际问题。1256.1.2目标规划的基本概念n目标规划问题是这样一类问题：n在满足刚性约束的前提下，求解一组决策变量的取值，使得不同优先级别目标的实现值与目标值之间的偏差尽可能小的线性规划问题。n概念n实现值与目标值、偏差变量n刚性约束与柔性约束n达成函数n优先级与权重1266.1.2目标规划的基本概念n1、目标值、实现值与偏差变量、目标值、实现值与偏差变量n在目标规划中，描述各个目标的数学表达式称为目标表达式。n对某个目标表达式期望的取值水平（不论是不超过、不少于还是等于），称为该目标的目标值。n当决策变量xj 的取值确定以后，某个目标表达式的实际取值称为该目标的实现值，又称为决策值。n例如，n例6-1中第(1)个目标的目标表达式为5x1+4x2+2x3，对此目标的期望值为200，则其目标值为200；n第(2)个目标的目标表达式可写为x1 2x2，此时目标值为0。n第(3)个目标的表达式x3，目标值为5。1276.1.2目标规划的基本概念n实现值与目标值之间可能会存在差异，这种差异的大小在决策（确定决策变量取值）前是无法预知的，是随决策变量变化而变化的，因此称实现值与目标值之间的差异为偏差变量。n因建模的需要以及适应线性规划中对变量的非负要求，偏差变量又分为n正偏差量，代表实现值超过目标值的偏差，记为d+n负偏差量，代表实现值未达到目标值的偏差，记为d-n满足非负：n满足互斥：1286.1.2目标规划的基本概念例如，例6-1中，如果某个满足了约束条件式(6-1)的决策为x1=25;x2=13;x3=5;则第(1)个目标，其实现值为5x1+4x2+2x3=187，未达到目标值200，如果用 表示该目标的正负偏差量，有对于第(2)个目标，其实现值为x1 2x2=1，目标值为0，有同理，对于第(3)个目标，因为实现值等于目标值5，有1296.1.2目标规划的基本概念2、刚性约束、柔性约束与达成函数n在目标规划中，必须严格满足的约束条件称为刚性约束或硬目标。n刚性约束中不含偏差变量。目标规划中，不满足刚性约束的解为非可行解。n与刚性约束相对，目标规划中允许某些目标的决策值与目标值存在偏差，这类目标称为软目标，其所对应的约束条件称为柔性约束。此即柔性约束的表达式。1306.1.2目标规划的基本概念n例如，对例6-1中的第(1)个目标，其柔性约束为：同理，对于第(2)、(3)个目标，其柔性约束分别为：1316.1.2目标规划的基本概念n对每个目标，决策者会表达出对决策值与目标值之间关系的期望超过、不超过或恰好等于。n但仅从柔性约束本身，无法判断决策者究竟是期望达到哪一种。在此引入一个称为达成函数的表达式来表示决策者的期望。n由目标规划问题的定义可知，对于任一目标，决策者的期望是使决策值与目标值的偏差尽可能小，因此达成函数是仅仅含偏差变量，且目标是使偏差变量取最含偏差变量，且目标是使偏差变量取最小值小值的目标函数1326.1.2目标规划的基本概念n对于单一的目标，达成函数依决策者的期望分三种情况：n超过目标值，则达成函数为。可理解为希望有正偏差，不希望有负偏差。n不超过目标值，则达成函数为。可理解为希望有负偏差，不希望有正偏差。n恰好等于目标值，则有，亦即正、负偏差量都要尽可能地小。n结合柔性约束与达成函数，就可以写出每个目标的目标表达式。1336.1.2目标规划的基本概念n例如，第(1)个目标的达成函数为利润最好不少于200：第(2)个目标的表达式为产品B产量最好低于产品A一半：第(4)个目标的表达式为原材料M2最好全部使用完且不超量：1346.1.2目标规划的基本概念3、优先级与权重n以上的分析只针对单一目标，当问题中有多个主次不同的目标，且各个目标之间可能存在矛盾时，就需要以某种方式将各个目标的达成函数合并成一个单一的达成函数。n目标规划通过引入优先级来为不同目标的达成函数加权。n具体为，在合并达成函数时，将目标按重要程度进行优先级排序，第1优先级目标的达成函数乘以优先因子P1，第2优先级目标的达成函数乘以P2，依次类推，第L优先级目标的达成函数乘以优先因子PL，且规定n由此保证优先实现P1级的目标，在此基础上再考虑P2级目标的实现，然后依次类推。1356.1.2目标规划的基本概念n某些实际问题中同一优先级下可能有多个目标，这些目标的重要程度还可以有差异，只不过这种差异不是数量级上的，目标规划用权重来区分这种差异。n在建模时，可以根据决策者的需求，对该优先级Pl 下某个目标k的达成函数以权系数wlk 加权后再相加。n注意：注意：n优先级的划分，以及同一优先级下多个目标的权重的设定，没有普适性的规则，而应根据决策者的需求和偏好来确定。-主观性主观性n在不同的问题背景或决策者偏好下，同一个目标的优先级或其在某个优先级中的权系数都可能有不同的设定。1366.1.2目标规划的基本概念n根据上述概念，可以写出例6-1的目标规划模型。整个问题的达成函数可以写为上式所示的“和”的形式，也可以写为“集合”的形式：1376.1.3目标规划模型及建模步骤n目标规划问题的数学模型的一般形式为：n自上而下分别是达成函数、刚性约束、柔性约束和所有变量的非负约束138 6.1.3目标规划模型及建模步骤n建模步骤：n第第1步步 设定问题的决策变量；n第第2步步 列出问题的刚性约束；n第第3步步 根据决策者的需求和偏好，设定各个目标的优先级，当有多个目标同属于一个优先级下时，还需根据约定设定各个目标的权重；然后，写出各个目标的柔性约束和各优先级的达成函数；n第第4步步 用优先因子和权系数为各个目标的达成函数加权，写出整个问题的达成函数。n第第5步步 写出决策变量与偏差变量的非负约束。139例例6-2 在例6-1中，假定不要求严格满足资源约束，且各优先级的目标依次如下：1.利润最好不少于180元；2.产品A的产量最好不多于25件、产品B的产量最好不少于15件、产品C的产量最好不少于5件，且根据单位产品的利润确定权系数；3.原材料M2最好全部使用完，不足时可购入，原材料M1比较稀缺，最好至少有10千克的剩余。问：F公司应如何安排生产计划，能够尽可能达成以上的经营目标？140解：用x1，x2和x3 表示产品A，B和C的产量。141n例例6-3 电子产品生产企业HF公司通过采购半成品生产A、B、C三种型号的手机。这三种手机在同一流水线上生产，每件的生产工时消耗分别为5分钟，7分钟，12分钟，利润分别为每台140元，210元，384元。生产线正常运转时间为250小时/月，加班满负荷运转时最多有400小时/月。HF公司的决策者提出的月经营目标按优先级排序为：1.尽可能充分利用生产线的正常工时，工时不够用时可以加班；2.希望A、B、C的产量至少达到700，750，500台，根据单位工时的利润比例设定权系数；3.加班工时最好不超过40小时/月；4.希望A、B、C的产量尽可能超过月销售量预测的最低水平800，900，550台，根据单位工时的利润比例设定权系数。问：各产品应生产多少才能达成上述经营目标？建立本问题的其目标规划模型。142解：设A、B、C的产量分别为x1,x2,x3。143n例例6-4 SD公司下属三个工厂生产某种产品来满足四个地区的需求，各工厂的产量、各地的需求量以及从各工厂到四地的单位产品运输费用如下表所示。如果仅要求运输费用最小，在将该问题转化为产销平衡问题后，用运输问题表上作业法求解得最低总运费为2750元。但是考虑到各地的不同情况和运输中可能存在的问题，该公司在确定最后运输方案时还需考虑其它几个目标，按重要程度依次为：nP1：地区3 为重点销售地区，其需求应优先全部满足；nP2：用于供应地区2 的产品中，工厂1 的产品不少于80 件；nP3：为平衡各地需求，每个地区用户需求的满足率应不低于90%；nP4：由于交通条件的限制，应尽量避免从工厂2 运输至地区2；nP5：尽可能减少总运费。1441456.2 两变量目标规划问题的图解法两变量目标规划问题的图解法1466.2两变量目标规划问题的图解法n目标规划模型中对目标进行了优先级的区分，这决定了其求解过程是一个分级进行的过程：n对于有L 个优先级的目标规划问题，先在可行域内寻找满足P1级目标的解n然后在保证P1级目标不被打破的前提下，再寻找满足P2级目标的解n依次类推n如果用解空间的概念，求解过程又可以表述为：n在可行域R0内找到满足P1 级目标的解空间R1，再以R1为可行域寻找满足P2级目标的解空间R2，依次类推，直至在RL-1内寻找PL级目标的解空间RL，其中n目标规划的最终求解结果通常只能称为满意解n即只能保证优先级较高的目标得以实现或部分实现，不保证优先级低的目标能实现。1476.2两变量目标规划问题的图解法n步骤n第第1 步步在坐标平面第一象限表示出由刚性约束所确定的可行域，以此可行域为初始解空间R0；n第第2 步步 选定P1优先级的目标，进入第3步；n第第3 步步 在Rl-1 中找到满足Pl级目标的解空间进入第4步Rl；n第第4 步步 当所有优先级的目标都处理完时，求解结束，问题的满意解就是目前得到的解空间；或者，如果Rl 为一个点，求解结束，问题的满意解就是该点的坐标。如果上述条件皆不满足，则转到下一个优先级，返回第3步。148图解法示例n例例6-5 用图解法求解149150151152153154155156157158图解法示例n例例6-6用图解法求解1591601611621631641651666.2两变量目标规划问题的图解法n应用图解法求解只有两个决策变量、且一个优先级Pl下有多个目标的目标规划模型时，确定Pl优先级的解空间Rl的过程就会变得比较复杂，见例6-7(略)。1676.4用Excel求解目标规划问题n掌握了序贯解法的原理，理解将目标规划问题转化为一系列线性规划问题的方式，再进一步用Excel规划求解工具完成。n略。168169第9章网络计划技术(NetworkPlanningTechnique)基本概念n网络计划技术（项目进度管理）n它利用网络图的形式直观表现出工程项目中各项任务之间的相互关系，从而找出决定项目总工期的关键路线和关键工序。n进而，在一定工期、成本、资源等约束条件下通过各种技术手段获得最佳的计划安排，以达到缩短工期、提高工效、降低成本的目的。170引例17116分钟引例17220分钟发展历程n网络计划技术根据起源可以分为关键路径法（CPM-CriticalPathMethod-WalkerandKelly）和计划评审技术（PERT-ProgramEvaluationandReviewTechnic-U.S.Navy）两个源头。n关键路径法强调/要求所研究项目中每项任务的执行时间必须是明确的，而计划评审技术中每项任务的执行时间可以是一个估计值/不确定值。n因此，关键路径法主要应用于一些有前期经验前期经验的工程项目，而计划评审技术更多应用于研究与开发研究与开发项目的计划管理。n1962,钱学森-华罗庚-“统筹法”173基本流程n1-阐明问题，将项目分解为若干个可以独立的工作单元，并明确各个工作单元的相关属性（资源使用、时间消耗、成本计算等），以及工作单元之间的逻辑先后关系。n2-根据分解后的工作单元，以及工作单元之间的逻辑先后关系，绘制网络图。174基本流程n3-应用关键路径法应用关键路径法计算得到整个项目的最短完最短完成时间成时间，项目中每项工序的最迟开始时间最迟开始时间、最最早可能开始时间早可能开始时间等时间参数时间参数，整个项目的关键关键路径路径以及关键路径上的各项关键工序关键工序。n4-根据具体应用，对关键路径上的关键工序进行资源的合理安排和优化合理安排和优化。175双代号网络图的绘制方法n工作单元用有向箭线来表示，箭线的方向表示工序进行的方向：箭线的箭尾表示该工序的开始，箭线的箭头表示该工序的结束。n工序的名称或者代号标注在箭线的上方，工序所花费的时间标注在箭线的下方。176双代号网络图的绘制方法n多条箭线指向该节点代表着多条箭线所指的工序都完成之后，该节点之后的工序才可以开始E的紧紧后工序后工序F，同理，C、D、E是F工序的紧前工序紧前工序。n多条箭线从该节点引出代表着该节点所代表的之前的工序结束后，可以同时开始多项工序。177双代号网络图的绘制方法n1-网络图中箭线尽量从左指向右，从上至下，从小到大，节点的编号按顺序编排，不允许重复。n2-两个节点之间，如果有如果有，只能有一条箭线。n3-网络图中只能有一个起始节点和一个终止节点。n4-不能有缺口和回路。除了起始点和终止点，任何节点都必须有至少一条箭线指向和引出该节点。178双代号网络图的绘制方法n如果节点之间需要包含两个或两个以上的箭线，即表示多个工序可以同时开始，并同时作为后续工序的紧前工序，那么需要使用虚工序虚工序（虚线的箭线）来帮助表示。179双代号网络图的绘制方法180双代号网络图的绘制方法181双代号网络图的绘制方法182双代号网络图示例1n例9-1183双代号网络图示例1184双代号网络图示例2185单代号网络图的绘制方法n节点表示工序，有向箭线描述工序之间的逻辑关系紧前/紧后工序：箭尾连接的节点工序为箭头连接的节点工序的紧前工序。n单代号网络不需要使用类似双代号网络中的虚工序。186单代号网络图的绘制方法187单代号网络图的绘制方法188单代号网络图的绘制方法189单代号网络图示例1n例9-3190单代号网络图示例1n例9-3191单代号网络图示例2192习题1193194195习题2196197习题3198199习题4200201关键路径法n从开始节点出发，沿着不同的路径到达终止节点所花费的时间也不尽相同。其中，花费时间最长的路经称为关键路径，而关键路径上的所有工序都被称为关键工序。202关键路径法n基本特点n1-关键路径上的所有工序总花费时间决定了整个项目的总工期，即项目的总工期等于关键路径上的所有工序持续时间的总和。n2-关键路径上的任一个关键工序发生了时间上的延迟，那么必然导致整个项目的工期时间上的延迟。203关键路径法n基本特点n3-关键路径上关键工序如果缩短了工期，那么整个项目的工期都会被缩短。相反，如果只是缩短非关键路径上的工序非关键工序的花费时间，整个项目的工期不会发生变化。n4-如果一个项目包含多条关键路径，那么它们的工期一定都相同。并且，如果只是缩短其中一条关键路径的工期，整个项目的工期并不能被缩短。204关键路径法n基本特点n5-关键路径是相对的。如果关键路径的工期被缩短，那么它有可能变为非关键路径，而非关键路径则有可能变成关键路径。205关键路径法n重要参数n最早开始时间。一个工序工序的最早开始时间TES为该工序的所有紧前工序d最早结束时间中最晚的一个，即其所有紧前工序的最早结束时间的最大值。（前一个工序结束，后一个工序才能开始）n最早结束时间。一个工序工序的最早结束时间TEF等于该工序的最早开始时间加上该工序的花费时间值。206关键路径法n重要参数n最迟结束时间。一个工序的最迟结束时间TLF是指该工序在不影响整个项目的时间进度前提下能够最迟结束的时间。它等于该工序所有紧后工序最迟开始时间最早的一个，即所有紧后工序的最迟开始时紧后工序的最迟开始时间的最小值间的最小值。（取决于别的工序取决于别的工序）n最迟开始时间。一个工序的最迟开始时间TLS等于该工序的最迟结束时间减去该工序的花费时间值。207关键路径法n重要参数n工序总时差。一个工序的总时差TTF是指该工序在不影响整个项目的时间进度前提下，工序最早开始时间可以推迟的时间，即该工序的最迟开始时间和最早开始时间的差值。LS-ESn工序自由时差。一个工序的自由时差TFF是指该工序在不影响其它工序（其紧后工序）的最早开始时间前提下，工序最早开始时间可以推迟的时间。208技巧:n工作最早时间的计算:顺着箭线，取大值工作最迟时间的计算：逆着箭线，取小值总时差：最迟减最早自由时差：后早始减本早完209n1工作最早时间的计算（包括工作最早开始时间和工作最早完成时间）：“顺着箭线计算，依次取大”（最早开始时间-取紧前工作最早完成时间的最大值），起始结点工作最早开始时间为0。用最早开始时间加持续时间就是该工作的最早完成时间。n2网络计划工期的计算：终点节点的最早完成时间最大值就是该网络计划的计算工期，一般以这个计划工期为要求工期。n3工作最迟时间的计算（包括工作最迟完成时间和最迟开始时间）：“逆着箭线计算，依次取小”（最迟完成时间-取紧后工作最迟开始时间的最小值）。与终点节点相连的最后一个工作的最早完成时间（计算工期）就是最后一个工作的最迟完成时间。用最迟完成时间减去工作的持续时间就是该工作的最迟开始时间。n4总时差：“最迟减最早”（最迟开始时间减最早开始时间或者最迟完成时间减最早完成时间）。注意这里都是“最迟减最早”。每个工作都有总时差，最小的总时差是零，我们经常说总时差为零的工作是“没有总时差”。n5自由时差：“后早始减本早完”(紧后工作的最早开始时间减本工作的最早完成时间)。自由时差总是小于、最多等于总时差，不会大于总时差。210关键路径法n对于一个项目而言，一个工序的工序总时差代对于一个项目而言，一个工序的工序总时差代表着该工序在项目中可以机动的时间。表着该工序在项目中可以机动的时间。n如果一个工序的工序总时差为0，则代表该工序不存在机动时间，那么该工序就是项目的一个关键工序。n可以根据计算得到所有关键工序，确定项目的一条或多条关键路径。211双代号网络的关键路径法n通过计算节点相关的时间参数得到工序的时间参数。n节点的最早发生时间。一个节点节点的最早发生时间TEEO是由所有指向指向该节点的箭线（工序）中最晚的最早发生时间确定。（Tes）n节点的最迟发生时间。一个节点节点的最迟发生时间TLEO是由该节点所发出发出所有箭线（工序）中最早的最迟发生时间确定。(Tlf)212双代号网络的关键路径法213工序A（1,2）M（j）=（紧前工序的集合），N(j)=（紧后工序的集合）双代号网络的关键路径法214双代号网络的关键路径法n对于工序(i,j)来说，工序的最早开始时间就是节点i的最早发生时间，最迟结束时间就是节点j的最迟发生时间。215双代号网络的关键路径法216双代号网络关键路径法示例1n例9-5217双代号网络关键路径法示例1n1-按照网络图中各个节点的逻辑先后顺序，计算所有节点的最早发生时间最早发生时间TEEO。218双代号网络关键路径法示例1219双代号网络关键路径法示例1n2-计算完所有节点的最早发生时间，从终止节点10开始，反向计算各个节点的最迟发生时间最迟发生时间TLEO。220双代号网络关键路径法示例1n最迟开始时间LSn最早开始时间ES221双代号网络关键路径法示例1222单代号网络的关键路径法n与双代号网络图的关键路径法计算方法类似，单代号网络的关键路径法也需要计算每个工序的6项时间参数，并根据工序的总时差为0来找出关键工序。223单代号网络关键路径法示例1n例9-7224单代号网络关键路径法示例1n1-计算所有节点的最早开始时间和最早结束时间。225单代号网络关键路径法示例1226单代号网络关键路径法示例1227单代号网络关键路径法示例1228计划评审技术n计划评审技术（PERT）与关键路径法（CPM）方法最大的差异在于计划评审技术主要是针对项目中工序持续时间无法精确估计或者给出，而是只能得到由多个数据共同描述的估计值，计算这种情况下项目的总工期，以及项目在规定时间内完成的可能性。229计划评审技术n计算步骤可以描述为：n1-各个工序持续时间的估值计算，即多个时间数据的合成；n2-应用CPM方法计算得到项目的关键工序和关键路径；n3-计算关键工序以及关键路径持续时间的波动范围；n4-计算规定时间内项目能够完工的可能性概率。230计划评审技术n在工程实践中，工序持续时间的估计通常采用三点时间，即工序的最长持续时间b、最短持续时间a和最可能发生的持续时间m。n而为了由此三个时间得到工序的单一持续时间估计值，通常的方法是取这三个值的加权平均值：231Excel求解关键路径n关键路径为网络计划图中总时间最长的一条从起点到终点的路线。因此，可以将关键路径的计算看作是网络中最“长”路径选择问题。232M.S.Project软件介绍233