工程硕士运筹学及重点方案

1工程硕士运筹学

内蒙古工业大学管理学院

1工程硕士运筹学

内蒙古工业大学管理学院

课程内容绪论线性规划基础线性规划的图解法、用Excel解LP问题整数规划运输问题目标规划图论动态规划网络计划技术2课程内容绪论23第0章绪论

IntroductionstoOperationsResearch

3第0章绪论

IntroductionstoOperat运筹学的实用价值公司应用问题收益/效果惠普公司预测消费者的购买行为，从而优化库存2009至2011年，创造了1.17亿美元的收益中国工商银行银行网点的城市布局问题2006至2011年，苏州因此增加了10.4亿美元的存款IHG洲际酒店集团解决酒店房间的定价问题2011年增加1.45亿美元的收益，并预计推广后未来每年将带来4亿美元的收益HubGroup哈勃货运集团提高场地管理和集装箱分配2008年收益增加了3%，获得了1,100万美元的净汇报Petrobras优化直升飞机在海上石油平台之间的飞行路线每年节省超过2千万美元4

ZARA（全球1500家门店）、P&G（15亿）运筹学的实用价值公司应用问题收益/效果惠普公司预测消费者的购5运筹学学科特点1-

科学性它是在科学方法论的指导下通过一系列规范化步骤。5运筹学学科特点1-科学性6运筹学学科特点2-实践性运筹学以实际问题为分析对象；分析结果必须用于指导实际系统的运行。适应性和鲁棒性Robustness，原是统计学中的一个专门术语，20世纪70年代初开始在控制理论的研究中流行起来，用以表征控制系统对特性或参数扰动的不敏感性。即当应用问题的背景受到一定程度的干扰时，最优解能够继续正常运行的程度。6运筹学学科特点2-实践性7运筹学学科特点3-系统性用系统的观点来分析研究对象，通过协调各组成部分之间的关系和利害冲突，使整个系统达到最优状态。实际问题的多目标“天性”，各目标没有统一的度量标准。7运筹学学科特点3-系统性8运筹学学科特点4-优化方案强调是最优的解决方案，而不是任意的一个可行方案，或者只是对现状的“改进”方案；当研究问题从数学分析上存在多个或无穷最优解时，不刻意去搜索出所有最优解，而是只需找出其中一个最优解；当研究问题过于复杂时，运筹学更倾向于搜索出一个“效率解”。8运筹学学科特点4-优化方案9运筹学学科特点5-

综合性运筹学研究是一种综合性的研究，它涉及问题的方方面面，应用多学科的知识，因此，要由一个各方面的专家组成的小组来完成。9运筹学学科特点5-综合性运筹学求解问题的一般思路1.明确问题，收集数据边界、目标量化、变量、参数、约束2.建立模型，数学模型：模型检验3.选取方法，进行求解：遗传算法等4.验证方案，实施方案5.方案程序化，模块化6.方案实施，效果分析10运筹学求解问题的一般思路1.明确问题，收集数据10运筹学求解问题的一般思路11运筹学求解问题的一般思路1112第1章线性规划基础(IntroductiontoLinearProgramming)12第1章线性规划基础目标1.常见线性规划问题的数学建模思路2.建模的适用范围3.“解”的概念4.图解法5.EXCEL求解一般线性规划问题（练习）13目标1.常见线性规划问题的数学建模思路1314线性规划的定义在满足一组线性约束条件（等式或不等式）的前提下，使得某一个线性目标函数取得极值（最大值或最小值）。这类问题的模型及其优化求解技术，被统称为线性规划(LinearProgramming,LP)。Inmathematics,LPproblemsareoptimizationproblemsinwhichtheobjectivefunction

andtheconstraints

arealllinear.14线性规划的定义在满足一组线性约束条件（等式或不等式）的前线性规划数学模型线性规划问题的一般模型15线性规划数学模型线性规划问题的一般模型15线性规划数学模型模型特点1-所有表达式均为线性表达式2-目标为求目标函数Z的最大值(max)或最小值(min)3-约束条件为”≥/≤/=”，没有”>/<”！4-通常要求决策变量取值非负16线性规划数学模型模型特点1617应用问题示例(1)-生产计划

F公司每周根据原材料M1和M2的采购数量来安排其产品A、B和C的生产计划。问：这3种产品各应生产多少，能使F公司获得最大的利润？单位消耗产品A产品B产品C可用资源原材料M1845320原材料M2221100单位产品利润54217应用问题示例(1)-生产计划F公司每周根据原材料M1和应用问题示例(2)-生产计划A公司用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)-生产计划A公司用M1,M2,M3和M4四应用问题示例(2)原材料M3和M4采购量超过市场供应总量的一半。采购预算费用为25万元人民币。问：根据产品的市场价格以及原材料价格，公司应如何采购以获得最多的利润？19原材料M1M2M3M4市场供给300200400300市场价格300600400500应用问题示例(2)原材料M3和M4采购量超过市场供应总量的一应用问题示例(2)建模思路1--20应用问题示例(2)建模思路1--20应用问题示例(2)正确的建模方法--21应用问题示例(2)正确的建模方法--21应用问题示例(2)22应用问题示例(2)22应用问题示例(3)-财务计划某集团公司未来6年年初的现金需求（万元）如下所示。为此，公司决定在今年年底一次性划拨一笔资金，未来6年不再划拨。23年份123456现金350405355260215230应用问题示例(3)-财务计划某集团公司未来6年年初的现金需求应用问题示例(3)公司可以通过多种投资形式减少资金的需求：1-银行一年期的定期存款，年利率为3%；2-国债（只能在第1年年初购买；国债的实际购买价格要高于其票面价格，且只能在到期日按票面价格收回本金）问：集团公司最少需要划拨多少资金，并如何投资，才能满足未来6年的现金需求？24债券类型票面价格实际购买价格年利率到期年限110,00012,0007.84210,00014,30010.75应用问题示例(3)公司可以通过多种投资形式减少资金的需求：2应用问题示例(3)由于6年内不再追加投资，因此6年内的投资（银行定期存款方式）必然不能超过当年现金需求的余额。并且，由于投资总能够获得更多的回报（103%），所以投资等于当年现金需求的余额！25应用问题示例(3)由于6年内不再追加投资，因此6年内的投资（应用问题示例(3)采用表格形式更加直观展示出投资与回报。年末的收益可以作为下一年年初的投资。回报第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)采用表格形式更加直观展示出投资与回报。回报应用问题示例(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)27回报第1年第2年第3年第4年第5年第6应用问题示例(3)完整问题模型如下：28应用问题示例(3)完整问题模型如下：28应用问题示例(4)-生产计划N公司生产两种产品P1和P2，这2种产品都是由组件C1,C2和C3各1件装配而成。需求为1600件P1和1000件P2。共有100个正常工时和最多60个加班工时，每个加班工时将额外增加12元的运营成本。问：如何安排生产和外购，才是最经济？29组件生产工时生产成本外购成本C11.51.01.2C2产品P14.08.08.5产品P23.06.07.0C3产品P12.01.52.0产品P23.01.82.1应用问题示例(4)-生产计划N公司生产两种产品P1和P2，这应用问题示例(4)根据问题描述，可以定义自行生产和外购的组件数量为决策变量。并且，外购组件的数量与生产能力也有关，因此需要定义实际加班工时为决策变量，即：30应用问题示例(4)根据问题描述，可以定义自行生产和外购的组件应用问题示例(4)31应用问题示例(4)31应用问题示例(5)-运输与分销运输与分销问题问：如何安排物流路线，实现总运输成本最小。32应用问题示例(5)-运输与分销运输与分销问题32应用问题示例(5)定义决策变量为各条路线上的运输量，各变量对应的路线如下所示。33应用问题示例(5)定义决策变量为各条路线上的运输量，各变量对应用问题示例(5)对于此类以图形方式给出的物流问题，存在以下函数关系，即图中每个节点，都必须满足“输入=输出”。34应用问题示例(5)对于此类以图形方式给出的物流问题，存在以下应用问题示例(5)源头节点“工厂1～3”，关系为“产量+运入量=运出量”。35应用问题示例(5)源头节点“工厂1～3”，关系为“产量+应用问题示例(5)中间节点“分销中心”，关系为“运入量=运出量”。36应用问题示例(5)中间节点“分销中心”，关系为“运入量=运出应用问题示例(5)终止节点“仓库1～2”，关系为“运入量=运出量+需求量”。37应用问题示例(5)终止节点“仓库1～2”，关系为“运入量应用问题示例(6)-套裁下料问题某建筑公司需要钢管规格和数量分别为：3m的600根、4m的300根、5m的200根。如果只能选择购入长度为11m的钢管自行切割，M公司至少应采购多少根11m的钢管？38应用问题示例(6)-套裁下料问题某建筑公司需要钢管规格和数量应用问题示例(6)某建筑公司需要钢管规格和数量分别为：3m的600根、4m的300根、5m的200根。如果只能选择购入长度为11m的钢管自行切割，M公司至少应采购多少根11m的钢管？39应用问题示例(6)某建筑公司需要钢管规格和数量分别为：3m的应用问题示例(6)40应用问题示例(6)40应用问题示例(6)思考题：如果目标函数改为“如果购入这些长度为11m的钢管自行切割，RE公司应如何切割废料最少？”41应用问题示例(6)思考题：如果目标函数改为“如果购入这些长度42线性规划模型的假设条件比例性假定：要求目标函数值、约束条件左端取值与决策变量的取值呈严格的比例关系。42线性规划模型的假设条件比例性假定：要求目标函数值、约束条线性规划模型的假设条件43线性规划模型的假设条件4344线性规划问题的标准图解法对于只包含2个变量的线性规划问题，可以通过标准图解法来求解。其解题步骤为：44线性规划问题的标准图解法对于只包含2个变量的线性规划问题45标准图解法示例1用标准图解法求下面的线性规划问题（例1-8）45标准图解法示例1用标准图解法求下面的线性规划问题（例1-标准图解法示例146标准图解法示例146标准图解法示例2应用标准图解法求解线性规划问题（例1-9）47标准图解法示例2应用标准图解法求解线性规划问题（例1-9）4标准图解法示例248标准图解法示例24849线性规划问题的重要推论1-如果线性规划问题的可行域非空且有界，那么线性规划问题一定有最优解；2-如果线性规划问题的可行域无界，那么该问题可能有无界解；3-如果线性规划问题的最优解在可行域的两个顶点上同时得到，那么这两个顶点连线上的所有点都是最优解（有无穷多最优解）；4-如果线性规划问题的可行域为空，意味着该线性规划问题无可行解。49线性规划问题的重要推论1-如果线性规划问题的可行域非空50简化的图解法对于可行域为封闭凸多边形的两变量线性规划问题，可以采用简化的图解法求解：只需要穷举出可行域的所有顶点，计算每一个顶点的目标函数值，就可以找出最优解。50简化的图解法对于可行域为封闭凸多边形的两变量线性规划问题简化的图解法示例1线性规划问题（例1-8）51顶点坐标目标函数值X1X2A000B4012C4327D2636E0630简化的图解法示例1线性规划问题（例1-8）51顶点坐标目标X52Excel求解线性规划问题“规划求解”工具主界面52Excel求解线性规划问题“规划求解”工具主界面Excel求解LP问题示例1线性规划问题（例1-8）53Excel求解LP问题示例1线性规划问题（例1-8）53练习题-图解以下线性规划问题54练习题-图解以下线性规划问题545555某手工作坊生产的竹制座椅中需要用到3种规格楠竹片，每张椅子需要长度为60cm、40cm

和30cm的楠竹片2、6和2片。可以在市场上采购这些规格的现货，也可以将作坊仓库中长度

为110cm的楠竹片切割成所需的规格，但每切割1次会发生1cm的长度损耗。

问：如果要制作100张竹制座椅，该作坊的仓库中至少要有多少条长度为110cm的楠竹片，

才不用去市场上采购？试建立本问题的线性规划模型。

56某手工作坊生产的竹制座椅中需要用到3种规格楠竹片，每张椅子需5757585859第2章整数规划(IntegerLinearProgramming)59第2章整数规划基本概念线性规划模型中增加了决策变量的整数约束，这类数学规划问题被称为整数规划(IntegerLinearProgramming,ILP)问题。整数规划模型虽然只是在线性规划模型中增加了决策变量的整数约束，但是其求解过程却变得非常复杂。（简单的四舍五入？？？）车辆调度、人员安排、产品产量60基本概念线性规划模型中增加了决策变量的整数约束，这类数学规划基本概念根据全部还是部分决策变量必须满足整数约束，整数规划问题可分为两类：纯整数规划（PureIntegerProgramming,PIP）混合整数规划（MixedIntegerProgramming,MIP）根据整数变量取值的范围，整数规划问题还可分为：一般整数规划-整数变量的取值可以是任意非负整数0-1整数规划（BinaryIntegerProgramming,BIP）-要求决策变量只能取值0或者161基本概念根据全部还是部分决策变量必须满足整数约束，整数规划问基本概念62一般整数规划问题的数学模型基本概念62一般整数规划问题的数学模型基本概念630-1整数规划问题的数学模型基本概念630-1整数规划问题的数学模型应用问题建模设施布点问题某市在其5个规划片区规划消防站设点，要求任意一个片区发生火警时，本片区或来自其它片区的消防车可以在15分钟内赶到。虽然在各片区各设一个消防站可以解决此问题，但为提高资源利用率，市政府提出消防站数量应尽可能少。64应用问题建模设施布点问题64应用问题建模背包问题（0-1）某家庭计划自驾野外露营，出发前需考虑携带的物品，各物品的压缩体积及重要程度如表所示。由于其自驾车最大容纳的物品体积为650升，不可能所有物品都能装入车中。问：应选择哪些物品出行？65应用问题建模背包问题（0-1）65应用问题建模指派问题有5项任务需要5个员工独立完成，由于能力差异，不同员工完成同一任务的执行成本不同。下表给出了员工i完成任务j的执行成本cij。问：如何指派任务可以最经济地完成各项任务。66应用问题建模指派问题66应用问题建模将n项任务分配给n个人，约定每人只能完成一项工作，每项工作也只能由一个人来完成，但由于每个人能力各不相同，完成各项工作的收益和成本不同。根据不同的问题背景，可要求得到总利润最大或总成本最小的指派方案。这类问题在运筹学中被称为一种专门的问题：指派问题(AssignmentProblem)。67应用问题建模将n项任务分配给n个人，约定每人只能完成一项工作应用问题建模68定义0-1变量xij(i,j=1,…,n)表示第i个人是否被指派完成第j项任务（0代表不指派，1代表指派），则指派问题的数学模型为：应用问题建模68定义0-1变量xij(i,j=1,…,n)表应用问题建模含有互斥项目的计划1.如果携带食物，就必须同时携带野外厨具和洗漱用品；2.通信设备和应急医疗用品至少要携带1件；3.帐篷和防晒防雨最多只能选择1项；4.野外厨具、摄影器材和通信设备最多选2项。69应用问题建模含有互斥项目的计划69应用问题建模含有互斥约束条件的计划某公司用两种原料E1和E2生产A、B两种产品，生产过程均需经过甲、乙两道工序。甲、乙两道工序又各可以采取2种生产工艺。甲工序可以混合使用甲1和甲2两种工艺，而乙工序只能在乙1和乙2中选择其中一种工艺。问：该公司应如何安排生产可使利润最大？70应用问题建模含有互斥约束条件的计划70在建模中对互斥的约束处理时，可以引入Mi来实现使某个约束条件有效或者冗余，其中Mi为任意大的正数。71在建模中对互斥的约束处理时，可以引入Mi来实现使某个约束条件固定成本问题某工厂用两条生产线𝐿1和𝐿2生产两种产品A和B。这两条生产线每个月的额定工时分别为600和800小时，生产线𝐿1的生产率为产品A60件/小时或产品B45件/小时，生产线𝐿2的生产率为产品A35件/小时或产品B40件/小时；产品A和B的单位售价分别为12元/件和16元/件，生产产品A和B的固定成本分别为60000元和80000元。

问：应如何安排生产可实现利润最大化？试建立本问题的混合整数规划模72固定成本问题某工厂用两条生产线𝐿1和𝐿2生产两种产品A和1）决策变量的定义：因为含有固定成本的问题，所以某产品的产量X和是否生产该产品的决策Y必须分别定义，而且它们必须是联动的，即如果某产品的产量X大于0，那么Y必须为1；而产品的产量X为0时，Y必须为0.否则，就有可能出现未生产产品X却减去了固定成本的问题，或者生产了却未减去固定成本的问题。这类问题必须引入任意大的正数M。731）决策变量的定义：因为含有固定成本的问题，所以某产品的产量2）正数M的引入X≤M∙Y其中M为任意大的正数，即，只要Y=0，则X必须为0，Y=1时，X可以取任意正整数。742）正数M的引入74所以，上题的决策变量定义如下：75所以，上题的决策变量定义如下：757676分枝定界法分枝定界技术是一种求解优化问题的通用思想，其逻辑思路是：把原始问题分解成若干个足够小的可以直接求解的子问题，此为分枝过程(Branching)；对于每个子集及其对应的子问题，考察其最优解是否足够好―是否可能包含原始问题的最优解，此为定界过程(Bounding)；结束某些子问题的分枝过程，并根据定界过程的结果，放弃那些不可能包含原始问题最优解的子集及子问题，此为剪枝过程(Fathoming)。77分枝定界法分枝定界技术是一种求解优化问题的通用思想，其逻辑思割平面法78割平面法78习题1某大型社区临街的中式快餐店每天的营业时间为8:00到24:00，根据社区居民对早餐、中餐、晚餐和夜宵的需求不同，一天中不同时段对服务员的需求如图所示。

79习题1某大型社区临街的中式快餐店每天的营业时间为8:00到2该店的员工分为两类。第一类是正式员工，分别在3个8小时时段上班：8:00-16:00、12:00-

20:00，以及16:00-

24:00，其工作时薪为14元/小时，且规定各时段正式员工数量不能少于3人；第二类是钟点工，可在8:00到24:00的任意时间工作，其工作时薪为12元/小时。

问：应如何雇用正式员工和钟点工，可在人力资源成本最小的基础上满足需求？试建立本问题的整数规划模型。

80该店的员工分为两类。第一类是正81818282习题2某公司计划在东、西、南三个地区建立销售网点，总共有7个备选地点𝐴𝑖(𝑖=1,···,7)可供选择。现要求所设立的销售网点必须满足以下条件：

∙在东部地区，𝐴1,𝐴2,𝐴3三个备选地点中至多选择两个地点设立销售网点；

∙在西部地区，𝐴4,𝐴5两个备选地点中至少选择一个地点设立销售网点；

∙在南部地区，𝐴6,𝐴7两个备选地点只能选一个设立销售网点；

∙出于市场环境的考虑，如果方案中选择了𝐴2地点，必须选择在𝐴5同时设立销售网点。若在备选地点𝐴𝑖设立销售网点需要投资𝑏𝑖万元，每年可获得利润𝑐𝑖万元。问：如果总投资预算为B万元，在哪些备选地点设立网点可获得最多的利润？试建立本问题的数学模型。

83习题2某公司计划在东、西、南三个地区建立销售网点，总共有7个8484习题3某短途航空公司有10条联飞路线，可经停9个城市，下表给出了这10条飞行路线经停的城市和飞行总小时数（单位：小时）。

试从这10条路线中选择3条路线，既能够满足飞行总时间最少的要求，又能够经停9个城市

至少1次。给出本问题的0-1整数规划模型。

85习题3某短途航空公司有10条联飞路线，可经停9个城市，下表给8686则其目标函数为：Min（Z）=？87878888习题4某小提琴手作坊根据顾客提出的定制需求生产小提琴，价格和固定成本因定制需求而异。由于作坊的熟练技师有限(12人)，该手工作坊只能挑选部分订单，甚至只能部分完成订单所要求的数量。目前，作坊收到来自3家交响乐队的小提琴订单，下表给出了与此订单相关的制作成本和价格（单位：元）。问：各订单各应接受多少台，可获得最多的利润？试建立本问题的整数规划模型。

89习题4某小提琴手作坊根据顾客提出的定制需求生产小90909191习题5某工厂生产A和B两种型号的产品，其生产过程须经过甲、乙、丙三个流水线车间加工，其中，乙车间有两条加工效率不同的流水线乙1和乙2。已知乙车间的两条流水线只能任选一条使用，问：如何安排生产可获得最大的利润。建立本问题的整数规划模型。92习题5某工厂生产A和B两种型号的产品，其生产过程须经过甲、乙939394第5章运输问题(TransportationProblems)94第5章运输问题基本概念将某种物资从若干个产地运输到另外若干个销地，要求总运费最小的问题，这一类问题及其衍生问题统称为运输问题(TransportationProblem)。95基本概念将某种物资从若干个产地运输到另外若干个销地，要求总运引例FreshFruit公司旗下有3个苹果种植基地，预计年产量分别为75、125和100吨，近期该公司与4个不同地区的客户签订了今年的苹果供应合同，其销量分别80、65、70和85吨。由于交通条件差异，从3个基地到4个客户所在地的单位运费不同，其运价表如表所示。96引例FreshFruit公司旗下有3个苹果种植基地，预计年产运输问题的数学模型97运输问题通常为：从m个产地向n个销地运输某种物资，产地i到销地j的单位运费是cij（呈比例关系），产地i的产量是ai，销地j的销量是bj，要求找到使得总运费最小的运输方案。当问题满足总产量与总销量相等，这类问题称为标准运输问题，或者产销平衡运输问题。运输问题的数学模型97运输问题通常为：从m个产地向n个销地运运输问题的数学模型标准运输问题的数学模型为：98运输问题的数学模型标准运输问题的数学模型为：98标准运输问题的表上作业法作为一种特殊的线性规划问题，标准运输问题模型并不包含天然的基变量和初始基本可行解，求解时需要在每个等式中引入人工变量，计算较为烦琐。对于标准运输问题，在某种特殊形式的表格上来应用单纯形法，可使求解过程大大简化，这种方法叫作运输问题的表上作业法。需特别强调的是，用表上作业法求解运输问题，产销平衡是一个基本前提。99标准运输问题的表上作业法作为一种特殊的线性规划问题，标准运输标准运输问题的表上作业法解题步骤：1-初始化给出初始基本可行方案；2-迭代第1步基本可行方案的最优判定，判断当前基本可行方案是否最优。如果不是，进入第2步；第2步基本可行方案的改进，然后返回第1步；100标准运输问题的表上作业法解题步骤：100标准运输问题的表上作业法运输问题作业表/产销平衡表101标准运输问题的表上作业法运输问题作业表/产销平衡表101标准运输问题的表上作业法102西北角法从作业表的西北角往东南角逐步填写运输量。标准运输问题的表上作业法102西北角法西北角法示例1103西北角法示例1103西北角法示例1104西北角法示例1104标准运输问题的表上作业法105最小元素法按照单位运费由低到高的次序来选择每次迭代中指派运输量的单元格。标准运输问题的表上作业法105最小元素法最小元素法示例1106最小元素法示例1106最小元素法示例1107最小元素法示例1107产销不平衡的运输问题示例108产销不平衡的运输问题示例108转运问题(1)确定标准运输问题中的产地和销地：转运点既是产地，又是销地。也就是说，标准运输问题中的产地为原始转运问题中的产地和所有的转运点，销地为原始问题中的销地和所有的转运点。(2)确定各产地的产量和销地的销量：将原始转运问题中产地的产量和销地的销量直接移植入标准运输问题；转运点的产量和销量相同，数值都为经过该转运点的最大可能转运量。109转运问题(1)确定标准运输问题中的产地和销地：转运点既是产转运问题(3)确定各产地与销地之间的单位运输费用：将原始问题中已知的两地之间的单位运输费用移植入标准运输问题；各转运点到其自身的单位运输费用为0；对于原始转运问题中不存在的运输路线，单位运费为无穷大，用任意大的正数𝑀表示。110转运问题(3)确定各产地与销地之间的单位运输费用：将原始问转运问题示例1111转运问题示例1111其它问题一些应用问题虽然与物资运输、分销没有任何联系，但是由于其问题背景与运输问题有相似的形式，亦可将其抽象并建模为广义的产销平衡运输问题，从而采用运输问题的表上作业法进行求解。112其它问题一些应用问题虽然与物资运输、分销没有任何联系，但是由习题1求解如下运输问题：113习题1求解如下运输问题：113习题2求解如下运输问题：114习题2求解如下运输问题：114习题3某水产品销售公司每天从3个水产品养殖厂采购新鲜产品运往4个批发市场。3个养殖厂每天提供的水产品数量为2500、3000、4500公斤，4个批发市场每日的需求量分别为2000、2500、3000、2500公斤。根据表5所示3个养殖厂的采购成本价和4个批发市场的价格（单位：元/千克），公司应如何安排运输可使得总利润最大？

115习题3某水产品销售公司每天从3个水产品养殖厂采购新鲜产品运往习题4有3个牧业基地向4个城市提供鲜奶，4个城市每日的鲜奶需求量为16、30、24和30千升，3个基地的每日鲜奶供应量分别为30、40和50千升。已知运送每千升鲜奶的费用如表所示（单位：千元）。试确定最经济的鲜奶运输方案，且求出最小总运费。116习题4有3个牧业基地向4个城市提供鲜奶习题5假定习题3中城市A每天最低需求和总需求量分别为14和24千升，城市C每天最低需求和总需求量分别为25和40千升，其它城市需求量无变化，在最低需求必须满足的前提下，求解该问题，且求出最小总运费。

117习题5假定习题3中城市A每天最低需求和总需求量分别为14和2习题6某干果公司从3个水果生产基地进货，在4个加工厂将水果加工成干果。假定3个水果基地的产量、4个加工厂的需求量，以及单位水果的运价如表所示。在最低需求必须满足的前提下，求总成本最低的运输方案。

118习题6某干果公司从3个水果生产基地进货，在4个加工厂将水果加习题7已知2个供应方A1、A2以及3个需求方B1、B2、B3的运输问题的运价表如表所示。由于违约成本比较低，供应方A1、A2在运输成本较高的情景下可选择违约；同样，由于缺货损失比较低，需求方B1、B2、B3也可以在运输成本较低的情景下选择违约。问：根据表所示的缺货成本、违约成本，以及运输成本，如何安排运输可使得总运营成本最低？

119习题7已知2个供应方A1、A2以及3个需求方B1、B2、B3第6章目标规划(GoalProgramming)120第6章目标规划(GoalProgramming)120目标规划的提出用线性规划来解决实际问题时，除了要满足比例性、可加性、可分性和确定性四个假设之外，通常还假设实际问题的求解目标是单一的，而且其约束条件是可以严格满足的。

线性规划的弊端：现实决策问题通常都有多重的、可能相互冲突的目标其约束条件也不一定必须全部严格满足

目标规划(GoalProgramming)的提出，正是为了消除或至少部分填补这种方法与实际应用之间的空白。121目标规划的提出用线性规划来解决实际问题时，除了要满足比例性、6.1.1引例-目标规划的数学模型在例1-1中，F公司每周需要根据下表确定产品A、B、C的产量，以获取最大的利润其线性规划数学模型为：本问题的求解目标是唯一的———利润最大化。1226.1.1引例-目标规划的数学模型在例1-1中，F公司每周6.1.1引例但现实问题往往会有多个目标，比如把上面这个例子变成：例6-1在满足例1-1资源约束的前提下，按优先次序满足以下的目标：利润最好不少于200元；产品B为产品A的补充件，其产量最好低于产品A的一半；产品C为战略性产品，其产量最好不低于5件；原材料M2最好全部使用完且不超量；原材料M1比较稀缺，最好至少有10千克的剩余。问：F公司应如何安排生产计划，能够尽可能达成以上的经营目标？1236.1.1引例但现实问题往往会有多个目标，比如把上面这个例6.1.1引例问题的线性规划模型变为以下不等式组符合上述不等式组的解，就是本问题的解。经过计算，该不等式组无解。而在实际背景下，该问题显然是有解的。124

资源约束五个目标6.1.1引例问题的线性规划模型变为以下不等式组124 6.1.1引例实际上，本问题前3个优先级的目标是可以完全达成的，第(4)、(5)个目标虽然无法完全达成，但是是允许妥协的———只需要在前几个目标达成的基础上，尽可能满足即可。问题出在建模的方式上以上模型将5个原本有优先次序的、允许妥协的目标变成了必须同时严格满足的目标。因此，一个在现实中有解的多目标决策问题，以线性规划的思路建模可能就无解了。目标规划的提出，正是针对这类线性规划无法解决的实际问题。1256.1.1引例实际上，本问题前3个优先级的目标是可以完全6.1.2目标规划的基本概念目标规划问题是这样一类问题：在满足刚性约束的前提下，求解一组决策变量的取值，使得不同优先级别目标的实现值与目标值之间的偏差尽可能小的线性规划问题。概念实现值与目标值、偏差变量刚性约束与柔性约束达成函数优先级与权重1266.1.2目标规划的基本概念目标规划问题是这样一类问题：16.1.2目标规划的基本概念1、目标值、实现值与偏差变量在目标规划中，描述各个目标的数学表达式称为目标表达式。对某个目标表达式期望的取值水平（不论是不超过、不少于还是等于），称为该目标的目标值。当决策变量xj

的取值确定以后，某个目标表达式的实际取值称为该目标的实现值，又称为决策值。例如，例6-1中第(1)个目标的目标表达式为5x1+4x2+2x3，对此目标的期望值为200，则其目标值为200；第(2)个目标的目标表达式可写为x1

−2x2，此时目标值为0。第(3)个目标的表达式x3，目标值为5。1276.1.2目标规划的基本概念1、目标值、实现值与偏差变量16.1.2目标规划的基本概念实现值与目标值之间可能会存在差异，这种差异的大小在决策（确定决策变量取值）前是无法预知的，是随决策变量变化而变化的，因此称实现值与目标值之间的差异为偏差变量。因建模的需要以及适应线性规划中对变量的非负要求，偏差变量又分为正偏差量，代表实现值超过目标值的偏差，记为d+负偏差量，代表实现值未达到目标值的偏差，记为d-满足非负：满足互斥：1286.1.2目标规划的基本概念实现值与目标值之间可能会存在差6.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目标规划的基本概念例如，例6-1中，如果某个满足6.1.2目标规划的基本概念2、刚性约束、柔性约束与达成函数在目标规划中，必须严格满足的约束条件称为刚性约束或硬目标。刚性约束中不含偏差变量。目标规划中，不满足刚性约束的解为非可行解。与刚性约束相对，目标规划中允许某些目标的决策值与目标值存在偏差，这类目标称为软目标，其所对应的约束条件称为柔性约束。此即柔性约束的表达式。1306.1.2目标规划的基本概念2、刚性约束、柔性约束与达成6.1.2目标规划的基本概念例如，对例6-1中的第(1)个目标，其柔性约束为：同理，对于第(2)、(3)个目标，其柔性约束分别为：1316.1.2目标规划的基本概念例如，对例6-1中的第(1)个6.1.2目标规划的基本概念对每个目标，决策者会表达出对决策值与目标值之间关系的期望———超过、不超过或恰好等于。但仅从柔性约束本身，无法判断决策者究竟是期望达到哪一种。在此引入一个称为达成函数的表达式来表示决策者的期望。由目标规划问题的定义可知，对于任一目标，决策者的期望是使决策值与目标值的偏差尽可能小，因此达成函数是仅含偏差变量，且目标是使偏差变量取最小值的目标函数1326.1.2目标规划的基本概念对每个目标，决策者会表达出对决6.1.2目标规划的基本概念对于单一的目标，达成函数依决策者的期望分三种情况：超过目标值，则达成函数为

。可理解为希望有正偏差，不希望有负偏差。不超过目标值，则达成函数为

。可理解为希望有负偏差，不希望有正偏差。恰好等于目标值，则有

，亦即正、负偏差量都要尽可能地小。结合柔性约束与达成函数，就可以写出每个目标的目标表达式。1336.1.2目标规划的基本概念对于单一的目标，达成函数依决策6.1.2目标规划的基本概念例如，第(1)个目标的达成函数为利润最好不少于200：第(2)个目标的表达式为产品B产量最好低于产品A一半：第(4)个目标的表达式为原材料M2最好全部使用完且不超量：1346.1.2目标规划的基本概念例如，第(1)个目标的达成函数6.1.2目标规划的基本概念3、优先级与权重以上的分析只针对单一目标，当问题中有多个主次不同的目标，且各个目标之间可能存在矛盾时，就需要以某种方式将各个目标的达成函数合并成一个单一的达成函数。目标规划通过引入优先级来为不同目标的达成函数加权。具体为，在合并达成函数时，将目标按重要程度进行优先级排序，第1优先级目标的达成函数乘以优先因子P1，第2优先级目标的达成函数乘以P2，依次类推，第L优先级目标的达成函数乘以优先因子PL，且规定由此保证优先实现P1

级的目标，在此基础上再考虑P2

级目标的实现，然后依次类推。1356.1.2目标规划的基本概念3、优先级与权重1356.1.2目标规划的基本概念某些实际问题中同一优先级下可能有多个目标，这些目标的重要程度还可以有差异，只不过这种差异不是数量级上的，目标规划用权重来区分这种差异。在建模时，可以根据决策者的需求，对该优先级Pl

下某个目标k的达成函数以权系数wlk

加权后再相加。注意：优先级的划分，以及同一优先级下多个目标的权重的设定，没有普适性的规则，而应根据决策者的需求和偏好来确定。------------主观性在不同的问题背景或决策者偏好下，同一个目标的优先级或其在某个优先级中的权系数都可能有不同的设定。1366.1.2目标规划的基本概念某些实际问题中同一优先级下可能6.1.2目标规划的基本概念根据上述概念，可以写出例6-1的目标规划模型。整个问题的达成函数可以写为上式所示的“和”的形式，也可以写为“集合”的形式：1376.1.2目标规划的基本概念根据上述概念，可以写出例6-16.1.3目标规划模型及建模步骤目标规划问题的数学模型的一般形式为：自上而下分别是达成函数、刚性约束、柔性约束和所有变量的非负约束138

6.1.3目标规划模型及建模步骤目标规划问题的数学模型的一6.1.3目标规划模型及建模步骤建模步骤：第1步设定问题的决策变量；第2步列出问题的刚性约束；第3步根据决策者的需求和偏好，设定各个目标的优先级，当有多个目标同属于一个优先级下时，还需根据约定设定各个目标的权重；然后，写出各个目标的柔性约束和各优先级的达成函数；第4步用优先因子和权系数为各个目标的达成函数加权，写出整个问题的达成函数。第5步写出决策变量与偏差变量的非负约束。1396.1.3目标规划模型及建模步骤建模步骤：139例6-2在例6-1中，假定不要求严格满足资源约束，且各优先级的目标依次如下：利润最好不少于180元；产品A的产量最好不多于25件、产品B的产量最好不少于15件、产品C的产量最好不少于5件，且根据单位产品的利润确定权系数；原材料M2最好全部使用完，不足时可购入，原材料M1比较稀缺，最好至少有10千克的剩余。问：F公司应如何安排生产计划，能够尽可能达成以上的经营目标？140例6-2在例6-1中，假定不要求严格满足资源约束，且各优解：用x1，x2

和x3

表示产品A，B和C的产量。141解：用x1，x2和x3表示产品A，B和C的产量。14例6-3电子产品生产企业HF公司通过采购半成品生产A、B、C三种型号的手机。这三种手机在同一流水线上生产，每件的生产工时消耗分别为5分钟，7分钟，12分钟，利润分别为每台140元，210元，384元。生产线正常运转时间为250小时/月，加班满负荷运转时最多有400小时/月。HF公司的决策者提出的月经营目标按优先级排序为：尽可能充分利用生产线的正常工时，工时不够用时可以加班；希望A、B、C的产量至少达到700，750，500台，根据单位工时的利润比例设定权系数；加班工时最好不超过40小时/月；

希望A、B、C的产量尽可能超过月销售量预测的最低水平800，900，550台，根据单位工时的利润比例设定权系数。问：各产品应生产多少才能达成上述经营目标？建立本问题的其目标规划模型。142例6-3电子产品生产企业HF公司通过采购半成品生产A、B解：设A、B、C的产量分别为x1,x2,x3。143解：设A、B、C的产量分别为x1,x2,x3。143例6-4SD公司下属三个工厂生产某种产品来满足四个地区的需求，各工厂的产量、各地的需求量以及从各工厂到四地的单位产品运输费用如下表所示。如果仅要求运输费用最小，在将该问题转化为产销平衡问题后，用运输问题表上作业法求解得最低总运费为2750元。但是考虑到各地的不同情况和运输中可能存在的问题，该公司在确定最后运输方案时还需考虑其它几个目标，按重要程度依次为：P1：地区3为重点销售地区，其需求应优先全部满足；P2：用于供应地区2的产品中，工厂1的产品不少于80件；P3：为平衡各地需求，每个地区用户需求的满足率应不低于90%；P4：由于交通条件的限制，应尽量避免从工厂2运输至地区2；P5：尽可能减少总运费。144例6-4SD公司下属三个工厂生产某种产品来满足四个地区的1451456.2两变量目标规划问题的图解法

1466.2两变量目标规划问题的图解法

1466.2两变量目标规划问题的图解法目标规划模型中对目标进行了优先级的区分，这决定了其求解过程是一个分级进行的过程：对于有L个优先级的目标规划问题，先在可行域内寻找满足P1级目标的解然后在保证P1级目标不被打破的前提下，再寻找满足P2级目标的解依次类推如果用解空间的概念，求解过程又可以表述为：在可行域R0

内找到满足P1

级目标的解空间R1，再以R1

为可行域寻找满足P2

级目标的解空间R2，依次类推，直至在RL-1

内寻找PL

级目标的解空间RL，其中目标规划的最终求解结果通常只能称为满意解即只能保证优先级较高的目标得以实现或部分实现，不保证优先级低的目标能实现。1476.2两变量目标规划问题的图解法目标规划模型中对目标进行了优6.2两变量目标规划问题的图解法步骤第1步在坐标平面第一象限表示出由刚性约束所确定的可行域，以此可行域为初始解空间R0；第2步选定P1优先级的目标，进入第3步；第3步在Rl-1

中找到满足Pl级目标的解空间进入第4步Rl；第4步当所有优先级的目标都处理完时，求解结束，问题的满意解就是目前得到的解空间；或者，如果Rl

为一个点，求解结束，问题的满意解就是该点的坐标。如果上述条件皆不满足，则转到下一个优先级，返回第3步。1486.2两变量目标规划问题的图解法步骤148图解法示例例6-5用图解法求解

149图解法示例例6-5用图解法求解149150150151151152152153153154154155155156156157157158158图解法示例例6-6

用图解法求解159图解法示例例6-6用图解法求解1591601601611611621621631631641641651651661666.2两变量目标规划问题的图解法应用图解法求解只有两个决策变量、且一个优先级Pl下有多个目标的目标规划模型时，确定Pl优先级的解空间Rl的过程就会变得比较复杂，见例6-7(略)。1676.2两变量目标规划问题的图解法应用图解法求解只有两个决策变6.4用Excel求解目标规划问题掌握了序贯解法的原理，理解将目标规划问题转化为一系列线性规划问题的方式，再进一步用Excel规划求解工具完成。略。1686.4用Excel求解目标规划问题掌握了序贯解法的原理，理169第9章网络计划技术(NetworkPlanningTechnique)169第9章网络计划技术基本概念网络计划技术（项目进度管理）它利用网络图的形式直观表现出工程项目中各项任务之间的相互关系，从而找出决定项目总工期的关键路线和关键工序。进而，在一定工期、成本、资源等约束条件下通过各种技术手段获得最佳的计划安排，以达到缩短工期、提高工效、降低成本的目的。170基本概念网络计划技术（项目进度管理）170引例17116分钟引例17116分钟引例17220分钟引例17220分钟发展历程网络计划技术根据起源可以分为关键路径法（CPM-CriticalPathMethod-WalkerandKelly）和计划评审技术（PERT-ProgramEvaluationandReviewTechnic-U.S.Navy）两个源头。关键路径法强调/要求所研究项目中每项任务的执行时间必须是明确的，而计划评审技术中每项任务的执行时间可以是一个估计值/不确定值。因此，关键路径法主要应用于一些有前期经验的工程项目，而计划评审技术更多应用于研究与开发项目的计划管理。1962,钱学森-华罗庚-“统筹法”173发展历程网络计划技术根据起源可以分为关键路径法（CPM-Cr基本流程1-阐明问题，将项目分解为若干个可以独立的工作单元，并明确各个工作单元的相关属性（资源使用、时间消耗、成本计算等），以及工作单元之间的逻辑先后关系。2-根据分解后的工作单元，以及工作单元之间的逻辑先后关系，绘制网络图。174基本流程1-阐明问题，将项目分解为若干个可以独立的工作单元，基本流程3-应用关键路径法计算得到整个项目的最短完成时间，项目中每项工序的最迟开始时间、最早可能开始时间等时间参数，整个项目的关键路径以及关键路径上的各项关键工序。4-根据具体应用，对关键路径上的关键工序进行资源的合理安排和优化。175基本流程3-应用关键路径法计算得到整个项目的最短完成时间，项双代号网络图的绘制方法工作单元用有向箭线来表示，箭线的方向表示工序进行的方向：箭线的箭尾表示该工序的开始，箭线的箭头表示该工序的结束。工序的名称或者代号标注在箭线的上方，工序所花费的时间标注在箭线的下方。176双代号网络图的绘制方法工作单元用有向箭线来表示，箭线的方向表双代号网络图的绘制方法多条箭线指向该节点代表着多条箭线所指的工序都完成之后，该节点之后的工序才可以开始E的紧后工序F，同理，C、D、E是F工序的紧前工序。多条箭线从该节点引出代表着该节点所代表的之前的工序结束后，可以同时开始多项工序。177双代号网络图的绘制方法多条箭线指向该节点代表着多条箭线所指的双代号网络图的绘制方法1-

网络图中箭线尽量从左指向右，从上至下，从小到大，节点的编号按顺序编排，不允许重复。2-

两个节点之间，如果有，只能有一条箭线。3-

网络图中只能有一个起始节点和一个终止节点。4-

不能有缺口和回路。除了起始点和终止点，任何节点都必须有至少一条箭线指向和引出该节点。178双代号网络图的绘制方法1-网络图中箭线尽量从左指向右，从上双代号网络图的绘制方法如果节点之间需要包含两个或两个以上的箭线，即表示多个工序可以同时开始，并同时作为后续工序的紧前工序，那么需要使用虚工序（虚线的箭线）来帮助表示。179双代号网络图的绘制方法如果节点之间需要包含两个或两个以上的箭双代号网络图的绘制方法180双代号网络图的绘制方法180双代号网络图的绘制方法181双代号网络图的绘制方法181双代号网络图的绘制方法182双代号网络图的绘制方法182双代号网络图示例1例9-1183双代号网络图示例1例9-1183双代号网络图示例1184双代号网络图示例1184双代号网络图示例2185双代号网络图示例2185单代号网络图的绘制方法节点表示工序，有向箭线描述工序之间的逻辑关系—紧前/紧后工序：箭尾连接的节点工序为箭头连接的节点工序的紧前工序。单代号网络不需要使用类似双代号网络中的虚工序。186单代号网络图的绘制方法节点表示工序，有向箭线描述工序之间的逻单代号网络图的绘制方法187单代号网络图的绘制方法187单代号网络图的绘制方法188单代号网络图的绘制方法188单代号网络图的绘制方法189单代号网络图的绘制方法189单代号网络图示例1例9-3190单代号网络图示例1例9-3190单代号网络图示例1例9-3191单代号网络图示例1例9-3191单代号网络图示例2192单代号网络图示例2192习题1193习题1193194194195195习题2196习题2196

197197习题3198习题3198199199习题4200习题4200201201关键路径法从开始节点出发，沿着不同的路径到达终止节点所花费的时间也不尽相同。其中，花费时间最长的路经称为关键路径，而关键路径上的所有工序都被称为关键工序。202关键路径法从开始节点出发，沿着不同的路径到达终止节点所花费的关键路径法基本特点1-关键路径上的所有工序总花费时间决定了整个项目的总工期，即项目的总工期等于关键路径上的所有工序持续时间的总和。2-关键路径上的任一个关键工序发生了时间上的延迟，那么必然导致整个项目的工期时间上的延迟。203关键路径法基本特点203关键路径法基本特点3-关键路径上关键工序如果缩短了工期，那么整个项目的工期都会被缩短。相反，如果只是缩短非关键路径上的工序—非关键工序的花费时间，整个项目的工期不会发生变化。4-

如果一个项目包含多条关键路径，那么它们的工期一定都相同。并且，如果只是缩短其中一条关键路径的工期，整个项目的工期并不能被缩短。204关键路径法基本特点204关键路径法基本特点5-

关键路径是相对的。如果关键路径的工期被缩短，那么它有可能变为非关键路径，而非关键路径则有可能变成关键路径。205关键路径法基本特点205关键路径法重要参数最早开始时间。一个工序的最早开始时间TES为该工序的所有紧前工序d最早结束时间中最晚的一个，即其所有紧前工序的最早结束时间的最大值。（前一个工序结束，后一个工序才能开始）最早结束时间。一个工序的最早结束时间TEF等于该工序的最早开始时间加上该工序的花费时间值。206关键路径法重要参数206关键路径法重要参数最迟结束时间。一个工序的最迟结束时间TLF是指该工序在不影响整个项目的时间进度前提下能够最迟结束的时间。它等于该工序所有紧后工序最迟开始时间最早的一个，即所有紧后工序的最迟开始时间的最小值。（取决于别的工序）最迟开始时间。一个工序的最迟开始时间TLS等于该工序的最迟结束时间减去该工序的花费时间值。207关键路径法重要参数207关键路径法重要参数工序总时差。一个工序的总时差TTF是指该工序在不影响整个项目的时间进度前提下，工序最早开始时间可以推迟的时间，即该工序的最迟开始时间和最早开始时间的差值。LS-ES工序自由时差。一个工序的自由时差TFF是指该工序在不影响其它工序（其紧后工序）的最早开始时间前提下，工序最早开始时间可以推迟的时间。208关键路径法重要参数208技巧:工作最早时间的计算:

顺着箭线，取大值

工作最迟时间的计算：

逆着箭线，取小值

总时差：

最迟减最早

自由时差：后早始减本早完209技巧:工作最早时间的计算:

209

1．工作最早时间的计算（包括工作最早开始时间和工作最早完成时间）：“顺着箭线计算，依次取大”（最早开始时间--取紧前工作最早完成时间的最大值），起始结点工作最早开始时间为0。用最早开始时间加持续时间就是该工作的最早完成时间。2．网络计划工期的计算：终点节点的最早完成时间最大值就是该网络计划的计算工期，一般以这个计划工期为要求工期。3．工作最迟时间的计算（包括工作最迟完成时间和最迟开始时间）：“逆着箭线计算，依次取小”（最迟完成时间--取紧后工作最迟开始时间的最小值）。与终点节点相连的最后一个工作的最早完成时间（计算工期）就是最后一个工作的最迟完成时间。用最迟完成时间减去工作的持续时间就是该工作的最迟开始时间。4．总时差：“最迟减最早”（最迟开始时间减最早开始时间或者最迟完成时间减最早完成时间）。注意这里都是“最迟减最早”。每个工作都有总时差，最小的总时差是零，我们经常说总时差为零的工作是“没有总时差”。5．自由时差：“后早始减本早完”(紧后工作的最早开始时间减本工作的最早完成时间)。自由时差总是小于、最多等于总时差，不会大于总时差。210

1．工作最早时间的计算（包括工作最早开始时间和工作最早完成关键路径法对于一个项目而言，一个工序的工序总时差代表着该工序在项目中可以机动的时间。如果一个工序的工序总时差为0，则代表该工序不存在机动时间，那么该工序就是项目的一个关键工序。可以根据计算得到所有关键工序，确定项目的一条或多条关键路径。211关键路径法对于一个项目而言，一个工序的工序总时差代表着该工序双代号网络的关键路径法通过计算节点相关的时间参数得到工序的时间参数。节点的最早发生时间。一个节点的最早发生时间TEEO是由所有指向该节点的箭线（工序）中最晚的最早发生时间确定。（Tes）节点的最迟发生时间。一个节点的最迟发生时间TLEO是由该节点所发出所有箭线（工序）中最早的最迟发生时间确定。(Tlf)212双代号网络的关键路径法通过计算节点相关的时间参数得到工序的时双代号网络的关键路径法213工序A（1,2）M（j）=（紧前工序的集合），N(j)=（紧后工序的集合）双代号网络的关键路径法213工序A（1,2）双代号网络的关键路径法214双代号网络的关键路径法214双代号网络的关键路径法对于工序(i,j)来说，工序的最早开始时间就是节点i的最早发生时间

，最迟结束时间就是节点j的最迟发生时间

。215双代号网络的关键路径法对于工序(i,j)来说，工序的最早开始双代号网络的关键路径法216双代号网络的关键路径法216双代号网络关键路径法示例1例9-5217双代号网络关键路径法示例1例9-5217双代号网络关键路径法示例11-按照网络图中各个节点的逻辑先后顺序，计算所有节点的最早发生时间TEEO。218双代号网络关键路径法示例11-按照网络图中各个节点的逻辑先后双代号网络关键路径法示例1219双代号网络关键路径法示例1219双代号网络关键路径法示例12-计算完所有节点的最早发生时间，从终止节点10开始，反向计算各个节点的最迟发生时间TLEO。220双代号网络关键路径法示例12-计算完所有节点的最早发生时间，双代号网络关键路径法示例1最迟开始时间LS最早开始时间ES221双代号网络关键路径法示例1最迟开始时间LS221双代号网络关键路径法示例1222双代号网络关键路径法示例1222单代号网络的关键路径法与双代号网络图的关键路径法计算方法类似，单代号网络的关键路径法也需要计算每个工序的6项时间参数，并根据工序的总时差为0来找出关键工序。223单代号网络的关键路径法与双代号网络图的关键路径法计算方法类似单代号网络关键路径法示例1例9-7224单代号网络关键路径法示例1例9-7224单代号网络关键路径法示例11-计算所有节点的最早开始时间和最早结束时间。225单代号网络关键路径法示例11-计算所有节点的最早开始时间和最单代号网络关键路径法示例1226单代号网络关键路径法示例1226单代号网络关键路径法示例1227单代号网络关键路径法示例1227单代号网络关键路径法示例1228单代号网络关键路径法示例1228计划评审技术计划评审技术（PERT）与关键路径法（CPM）方法最大的差异在于计划评审技术主要是针对项目中工序持续时间无法精确估计或者给出，而是只能得到由多个数据共同描述的估计值，计算这种情况下项目的总工期，以及项目在规定时间内完成的可能性。229计划评审技术计划评审技术（PERT）与关键路径法（CPM）方计划评审技术计算步骤可以描述为：1-各个工序持续时间的估值计算，即多个时间数据的合成；2-应用CPM方法计算得到项目的关键工序和关键路径；3-计算关键工序以及关键路径持续时间的波动范围；4-计算规定时间内项目能够完工的可能性概率。230计划评审技术计算步骤可以描述为：230计划评审技术在工程实践中，工序持续时间的估计通常采用三点时间，即工序的最长持续时间b、最短持续时间a和最可能发生的持续时间m。而为了由此三个时间得到工序的单一持续时间估计值，通常的方法是取这三个值的加权平均值：231计划评审技术在工程实践中，工序持续时间的估计通常采用三点时间Excel求解关键路径关键路径为网络计划图中总时间最长的一条从起点到终点的路线。因此，可以将关键路径的计算看作是网络中最“长”路径选择问题。232Excel求解关键路径关键路径为网络计划图中总时间最长的一条M.S.Project软件介绍233M.S.Project软件介绍233人有了知识，就会具备各种分析能力，明辨是非的能力。所以我们要勤恳读书，广泛阅读，古人说“书中自有黄金屋。”通过阅读科技书籍，我们能丰富知识，培养逻辑思维能力；通过阅读文学作品，我们能提高文学鉴赏水平，培养文学情趣；通过阅读报刊，我们能增长见识，扩大自己的知识面。有许多书籍还能培养我们的道德情操，给我们巨大的精神力量，鼓舞我们前进。人有了知识，就会具备各种分析能力，工程硕士运筹学及重点方案236工程硕士运筹学

内蒙古工业大学管理学院

1工程硕士运筹学

内蒙古工业大学管理学院

课程内容绪论线性规划基础线性规划的图解法、用Excel解LP问题整数规划运输问题目标规划图论动态规划网络计划技术237课程内容绪论2238第0章绪论

IntroductionstoOperationsResearch

3第0章绪论

IntroductionstoOperat运筹学的实用价值公司应用问题收益/效果惠普公司预测消费者的购买行为，从而优化库存2009至2011年，创造了1.17亿美元的收益中国工商银行银行网点的城市布局问题2006至2011年，苏州因此增加了10.4亿美元的存款IHG洲际酒店集团解决酒店房间的定价问题2011年增加1.45亿美元的收益，并预计推广后未来每年将带来4亿美元的收益HubGroup哈勃货运集团提高场地管理和集装箱分配2008年收益增加了3%，获得了1,100万美元的净汇报Petrobras优化直升飞机在海上石油平台之间的飞行路线每年节省超过2千万美元239

ZARA（全球1500家门店）、P&G（15亿）运筹学的实用价值公司应用问题收益/效果惠普公司预测消费者的购240运筹学学科特点1-

科学性它是在科学方法论的指导下通过一系列规范化步骤。5运筹学学科特点1-科学性241运筹学学科特点2-实践性运筹学以实际问题为分析对象；分析结果必须用于指导实际系统的运行。适应性和鲁棒性Robustness，原是统计学中的一个专门术语，20世纪70年代初开始在控制理论的研究中流行起来，用以表征控制系统对特性或参数扰动的不敏感性。即当应用问题的背景受到一定程度的干扰时，最优解能够继续正常运行的程度。6运筹学学科特点2-实践性242运筹学学科特点3-系统性用系统的观点来