工程硕士运筹学及重点方案课件.ppt

《工程硕士运筹学及重点方案课件.ppt》由会员分享，可在线阅读，更多相关《工程硕士运筹学及重点方案课件.ppt（235页珍藏版）》请在三一办公上搜索。

1、1,工程硕士运筹学,内蒙古工业大学管理学院,课程内容,绪论线性规划基础线性规划的图解法、用Excel解LP问题整数规划运输问题目标规划图论动态规划网络计划技术,2,3,第0章,绪论Introductions to Operations Research,运筹学的实用价值,4,ZARA（全球1500家门店）、P&G（15亿）,5,运筹学学科特点,1-科学性它是在科学方法论的指导下通过一系列规范化步骤。,6,运筹学学科特点,2-实践性运筹学以实际问题为分析对象；分析结果必须用于指导实际系统的运行。适应性和鲁棒性Robustness，原是统计学中的一个专门术语，20世纪70年代初开始在控制理论的研究

2、中流行起来，用以表征控制系统对特性或参数扰动的不敏感性。即当应用问题的背景受到一定程度的干扰时，最优解能够继续正常运行的程度。,7,运筹学学科特点,3-系统性用系统的观点来分析研究对象，通过协调各组成部分之间的关系和利害冲突，使整个系统达到最优状态。实际问题的多目标“天性”，各目标没有统一的度量标准。,8,运筹学学科特点,4-优化方案强调是最优的解决方案，而不是任意的一个可行方案，或者只是对现状的“改进”方案；当研究问题从数学分析上存在多个或无穷最优解时，不刻意去搜索出所有最优解，而是只需找出其中一个最优解；当研究问题过于复杂时，运筹学更倾向于搜索出一个“效率解”。,9,运筹学学科特点,5-综

3、合性运筹学研究是一种综合性的研究，它涉及问题的方方面面，应用多学科的知识，因此，要由一个各方面的专家组成的小组来完成。,运筹学求解问题的一般思路,1.明确问题，收集数据边界、目标量化、变量、参数、约束2.建立模型，数学模型：模型检验3.选取方法，进行求解：遗传算法等4.验证方案，实施方案5.方案程序化，模块化6.方案实施，效果分析,10,运筹学求解问题的一般思路,11,12,第1章,线性规划基础(Introduction to Linear Programming),目标,1.常见线性规划问题的数学建模思路2.建模的适用范围3.“解”的概念4.图解法5.EXCEL求解一般线性规划问题（练习）,

4、13,14,线性规划的定义,在满足一组线性约束条件（等式或不等式）的前提下，使得某一个线性目标函数取得极值（最大值或最小值）。这类问题的模型及其优化求解技术，被统称为线性规划(Linear Programming,LP)。In mathematics,LP problems are optimization problems in which the objective function and the constraints are all linear.,线性规划数学模型,线性规划问题的一般模型,15,线性规划数学模型,模型特点1-所有表达式均为线性表达式2-目标为求目标函数Z的最大值(m

5、ax)或最小值(min)3-约束条件为”/=”，没有”/”！4-通常要求决策变量取值非负,16,17,应用问题示例(1)-生产计划,F公司每周根据原材料M1和M2的采购数量来安排其产品A、B和C的生产计划。问：这3种产品各应生产多少，能使F公司获得最大的利润？,应用问题示例(2)-生产计划,A公司用M1,M2,M3和M4四种原材料，生产产品P1,P2和P3。这三种产品由这四种原材料混合而成（产品重量为四种原材料重量之和）。,18,应用问题示例(2),原材料M3和M4采购量超过市场供应总量的一半。采购预算费用为25万元人民币。问：根据产品的市场价格以及原材料价格，公司应如何采购以获得最多的利润？

6、,19,应用问题示例(2),建模思路1-,20,应用问题示例(2),正确的建模方法-,21,应用问题示例(2),22,应用问题示例(3)-财务计划,某集团公司未来6年年初的现金需求（万元）如下所示。为此，公司决定在今年年底一次性划拨一笔资金，未来6年不再划拨。,23,应用问题示例(3),公司可以通过多种投资形式减少资金的需求：1-银行一年期的定期存款，年利率为3%；2-国债（只能在第1年年初购买；国债的实际购买价格要高于其票面价格，且只能在到期日按票面价格收回本金）问：集团公司最少需要划拨多少资金，并如何投资，才能满足未来6年的现金需求？,24,应用问题示例(3),由于6年内不再追加投资，因此

7、6年内的投资（银行定期存款方式）必然不能超过当年现金需求的余额。并且，由于投资总能够获得更多的回报（103%），所以投资等于当年现金需求的余额！,25,应用问题示例(3),采用表格形式更加直观展示出投资与回报。年末的收益可以作为下一年年初的投资。,26,应用问题示例(3),27,应用问题示例(3),完整问题模型如下：,28,应用问题示例(4)-生产计划,N公司生产两种产品P1和P2，这2种产品都是由组件C1,C2和C3各1件装配而成。需求为1600件P1和1000件P2。共有100个正常工时和最多60个加班工时，每个加班工时将额外增加12元的运营成本。问：如何安排生产和外购，才是最经济？,29

8、,应用问题示例(4),根据问题描述，可以定义自行生产和外购的组件数量为决策变量。并且，外购组件的数量与生产能力也有关，因此需要定义实际加班工时为决策变量，即：,30,应用问题示例(4),31,应用问题示例(5)-运输与分销,运输与分销问题问：如何安排物流路线，实现总运输成本最小。,32,应用问题示例(5),定义决策变量为各条路线上的运输量，各变量对应的路线如下所示。,33,应用问题示例(5),对于此类以图形方式给出的物流问题，存在以下函数关系，即图中每个节点，都必须满足“输入=输出”。,34,应用问题示例(5),源头节点“工厂1 3”，关系为“产量+运入量=运出量”。,35,应用问题示例(5)

9、,中间节点“分销中心”，关系为“运入量=运出量”。,36,应用问题示例(5),终止节点“仓库1 2”，关系为“运入量=运出量+需求量”。,37,应用问题示例(6)-套裁下料问题,某建筑公司需要钢管规格和数量分别为：3m的600根、4m的300根、5m的200根。如果只能选择购入长度为11m的钢管自行切割，M公司至少应采购多少根11m的钢管？,38,应用问题示例(6),某建筑公司需要钢管规格和数量分别为：3m的600根、4m的300根、5m的200根。如果只能选择购入长度为11m的钢管自行切割，M公司至少应采购多少根11m的钢管？,39,应用问题示例(6),40,应用问题示例(6),思考题：如果

10、目标函数改为“如果购入这些长度为11m的钢管自行切割，RE公司应如何切割废料最少？”,41,42,线性规划模型的假设条件,比例性假定：要求目标函数值、约束条件左端取值与决策变量的取值呈严格的比例关系。,线性规划模型的假设条件,43,44,线性规划问题的标准图解法,对于只包含2个变量的线性规划问题，可以通过标准图解法来求解。其解题步骤为：,45,标准图解法示例1,用标准图解法求下面的线性规划问题（例1-8）,标准图解法示例1,46,标准图解法示例2,应用标准图解法求解线性规划问题（例1-9）,47,标准图解法示例2,48,49,线性规划问题的重要推论,1-如果线性规划问题的可行域非空且有界，那么

11、线性规划问题一定有最优解；2-如果线性规划问题的可行域无界，那么该问题可能有无界解；3-如果线性规划问题的最优解在可行域的两个顶点上同时得到，那么这两个顶点连线上的所有点都是最优解（有无穷多最优解）；4-如果线性规划问题的可行域为空，意味着该线性规划问题无可行解。,50,简化的图解法,对于可行域为封闭凸多边形的两变量线性规划问题，可以采用简化的图解法求解：只需要穷举出可行域的所有顶点，计算每一个顶点的目标函数值，就可以找出最优解。,简化的图解法示例1,线性规划问题（例1-8）,51,52,Excel求解线性规划问题,“规划求解”工具主界面,Excel求解LP问题示例1,线性规划问题（例1-8）

12、,53,练习题-图解以下线性规划问题,54,55,某手工作坊生产的竹制座椅中需要用到3种规格楠竹片，每张椅子需要长度为60cm、40cm和 30cm 的楠竹片 2、6和2 片。可以在市场上采购这些规格的现货，也可以将作坊仓库中长度为110cm的楠竹片切割成所需的规格，但每切割1次会发生1cm的长度损耗。问：如果要制作100张竹制座椅，该作坊的仓库中至少要有多少条长度为110cm的楠竹片，才不用去市场上采购？试建立本问题的线性规划模型。,56,57,58,59,第2章,整数规划(Integer Linear Programming),基本概念,线性规划模型中增加了决策变量的整数约束，这类数学规划

13、问题被称为整数规划(Integer Linear Programming,ILP)问题。整数规划模型虽然只是在线性规划模型中增加了决策变量的整数约束，但是其求解过程却变得非常复杂。（简单的四舍五入？）车辆调度、人员安排、产品产量,60,基本概念,根据全部还是部分决策变量必须满足整数约束，整数规划问题可分为两类：纯整数规划（Pure Integer Programming,PIP）混合整数规划（Mixed Integer Programming,MIP）根据整数变量取值的范围，整数规划问题还可分为：一般整数规划-整数变量的取值可以是任意非负整数0-1整数规划（Binary Integer Pro

14、gramming,BIP）-要求决策变量只能取值0或者1,61,基本概念,62,一般整数规划问题的数学模型,基本概念,63,0-1整数规划问题的数学模型,应用问题建模,设施布点问题某市在其5个规划片区规划消防站设点，要求任意一个片区发生火警时，本片区或来自其它片区的消防车可以在15分钟内赶到。虽然在各片区各设一个消防站可以解决此问题，但为提高资源利用率，市政府提出消防站数量应尽可能少。,64,应用问题建模,背包问题（0-1）某家庭计划自驾野外露营，出发前需考虑携带的物品，各物品的压缩体积及重要程度如表所示。由于其自驾车最大容纳的物品体积为650升，不可能所有物品都能装入车中。问：应选择哪些物品

15、出行？,65,应用问题建模,指派问题有5项任务需要5个员工独立完成，由于能力差异，不同员工完成同一任务的执行成本不同。下表给出了员工i完成任务j的执行成本cij。问：如何指派任务可以最经济地完成各项任务。,66,应用问题建模,将n项任务分配给n个人，约定每人只能完成一项工作，每项工作也只能由一个人来完成，但由于每个人能力各不相同，完成各项工作的收益和成本不同。根据不同的问题背景，可要求得到总利润最大或总成本最小的指派方案。这类问题在运筹学中被称为一种专门的问题：指派问题(Assignment Problem)。,67,应用问题建模,68,定义0-1变量xij(i,j=1,n)表示第i个人是否被

16、指派完成第j项任务（0代表不指派，1代表指派），则指派问题的数学模型为：,应用问题建模,含有互斥项目的计划1.如果携带食物，就必须同时携带野外厨具和洗漱用品；2.通信设备和应急医疗用品至少要携带1件；3.帐篷和防晒防雨最多只能选择1项；4.野外厨具、摄影器材和通信设备最多选2项。,69,应用问题建模,含有互斥约束条件的计划某公司用两种原料E1和E2生产A、B两种产品，生产过程均需经过甲、乙两道工序。甲、乙两道工序又各可以采取2种生产工艺。甲工序可以混合使用甲1和甲2两种工艺，而乙工序只能在乙1和乙2中选择其中一种工艺。问：该公司应如何安排生产可使利润最大？,70,在建模中对互斥的约束处理时，可

17、以引入Mi来实现使某个约束条件有效或者冗余，其中Mi为任意大的正数。,71,固定成本问题,某工厂用两条生产线1和2生产两种产品A和B。这两条生产线每个月的额定工时分别为600和800小时，生产线1的生产率为产品A 60件/小时或产品B 45件/小时，生产线2的生产率为产品A 35件/小时或产品B 40件/小时；产品A和B的单位售价分别为12元/件和16元/件，生产产品A和B的固定成本分别为60000元和80000元。问：应如何安排生产可实现利润最大化？试建立本问题的混合整数规划模,72,1）决策变量的定义：因为含有固定成本的问题，所以某产品的产量X和是否生产该产品的决策Y必须分别定义，而且它们

18、必须是联动的，即如果某产品的产量X大于0，那么Y必须为1；而产品的产量X为0时，Y必须为0.否则，就有可能出现未生产产品X却减去了固定成本的问题，或者生产了却未减去固定成本的问题。这类问题必须引入任意大的正数M。,73,2）正数M的引入XMY其中M为任意大的正数，即，只要Y=0，则X必须为0，Y=1时，X可以取任意正整数。,74,所以，上题的决策变量定义如下：,75,76,分枝定界法,分枝定界技术是一种求解优化问题的通用思想，其逻辑思路是：把原始问题分解成若干个足够小的可以直接求解的子问题，此为分枝过程(Branching)；对于每个子集及其对应的子问题，考察其最优解是否足够好是否可能包含原始

19、问题的最优解，此为定界过程(Bounding)；结束某些子问题的分枝过程，并根据定界过程的结果，放弃那些不可能包含原始问题最优解的子集及子问题，此为剪枝过程(Fathoming)。,77,割平面法,78,习题1,某大型社区临街的中式快餐店每天的营业时间为8:00到24:00，根据社区居民对早餐、中餐、晚餐和夜宵的需求不同，一天中不同时段对服务员的需求如图所示。,79,该 店 的 员 工 分 为 两 类。第 一 类 是 正 式 员 工，分 别 在3个8小 时 时 段 上 班：8:00-16:00、12:00-20:00，以及 16:00-24:00，其工作时薪为14元/小时，且规定各时段正式员工

20、数量不能少于3人；第二类是钟点工，可在8:00到24:00的任意时间工作，其工作时薪为12元/小时。问：应如何雇用正式员工和钟点工，可在人力资源成本最小的基础上满足需求？试建立本问题的整数规划模型。,80,81,82,习题2,某公司计划在东、西、南三个地区建立销售网点，总共有7个备选地点(=1,7)可供选择。现要求所设立的销售网点必须满足以下条件：在东部地区，1,2,3三个备选地点中至多选择两个地点设立销售网点；在西部地区，4,5两个备选地点中至少选择一个地点设立销售网点；在南部地区，6,7两个备选地点只能选一个设立销售网点；出于市场环境的考虑，如果方案中选择了2地点，必须选择在5同时设立销售

21、网点。若在备选地点设立销售网点需要投资万元，每年可获得利润万元。问：如果总投资预算为B万元，在哪些备选地点设立网点可获得最多的利润？试建立本问题的数学模型。,83,84,习题3,某短途航空公司有10条联飞路线，可经停9个城市，下表给出了这10条飞行路线经停的城市和飞行总小时数（单位：小时）。试从这10条路线中选择3条路线，既能够满足飞行总时间最少的要求，又能够经停9个城市至少1次。给出本问题的0-1整数规划模型。,85,86,则其目标函数为：Min（Z）=？,87,88,习题4,某小提琴手作坊根据顾客提出的定制需求生产小提琴，价格和固定成本因定制需求而异。由于作坊的熟练技师有限(12人)，该手

22、工作坊只能挑选部分订单，甚至只能部分完成订单所要求的数量。目前，作坊收到来自3家交响乐队的小提琴订单，下表给出了与此订单相关的制作成本和价格（单位：元）。问：各订单各应接受多少台，可获得最多的利润？试建立本问题的整数规划模型。,89,90,91,习题5,某工厂生产A和B两种型号的产品，其生产过程须经过甲、乙、丙三个流水线车间加工，其中，乙车间有两条加工效率不同的流水线乙1和乙2。已知乙车间的两条流水线只能任选一条使用，问：如何安排生产可获得最大的利润。建立本问题的整数规划模型。,92,93,94,第5章,运输问题(Transportation Problems),基本概念,将某种物资从若干个产

23、地运输到另外若干个销地，要求总运费最小的问题，这一类问题及其衍生问题统称为运输问题(Transportation Problem)。,95,引例,FreshFruit公司旗下有3个苹果种植基地，预计年产量分别为75、125和100吨，近期该公司与4个不同地区的客户签订了今年的苹果供应合同，其销量分别80、65、70和85吨。由于交通条件差异，从3个基地到4个客户所在地的单位运费不同，其运价表如表所示。,96,运输问题的数学模型,97,运输问题通常为：从m个产地向n个销地运输某种物资，产地i到销地j的单位运费是cij（呈比例关系），产地i的产量是ai，销地j的销量是bj，要求找到使得总运费最小的

24、运输方案。当问题满足总产量与总销量相等，这类问题称为标准运输问题，或者产销平衡运输问题。,运输问题的数学模型,标准运输问题的数学模型为：,98,标准运输问题的表上作业法,作为一种特殊的线性规划问题，标准运输问题模型并不包含天然的基变量和初始基本可行解，求解时需要在每个等式中引入人工变量，计算较为烦琐。对于标准运输问题，在某种特殊形式的表格上来应用单纯形法，可使求解过程大大简化，这种方法叫作运输问题的表上作业法。需特别强调的是，用表上作业法求解运输问题，产销平衡是一个基本前提。,99,标准运输问题的表上作业法,解题步骤：1-初始化 给出初始基本可行方案；2-迭代第1步基本可行方案的最优判定，判断

25、当前基本可行方案是否最优。如果不是，进入第2步；第2步基本可行方案的改进，然后返回第1步；,100,标准运输问题的表上作业法,运输问题作业表/产销平衡表,101,标准运输问题的表上作业法,102,西北角法从作业表的西北角往东南角逐步填写运输量。,西北角法示例1,103,西北角法示例1,104,标准运输问题的表上作业法,105,最小元素法按照单位运费由低到高的次序来选择每次迭代中指派运输量的单元格。,最小元素法示例1,106,最小元素法示例1,107,产销不平衡的运输问题示例,108,转运问题,(1)确定标准运输问题中的产地和销地：转运点既是产地，又是销地。也就是说，标准运输问题中的产地为原始转

26、运问题中的产地和所有的转运点，销地为原始问题中的销地和所有的转运点。(2)确定各产地的产量和销地的销量：将原始转运问题中产地的产量和销地的销量直接移植入标准运输问题；转运点的产量和销量相同，数值都为经过该转运点的最大可能转运量。,109,转运问题,(3)确定各产地与销地之间的单位运输费用：将原始问题中已知的两地之间的单位运输费用移植入标准运输问题；各转运点到其自身的单位运输费用为0；对于原始转运问题中不存在的运输路线，单位运费为无穷大，用任意大的正数表示。,110,转运问题示例1,111,其它问题,一些应用问题虽然与物资运输、分销没有任何联系，但是由于其问题背景与运输问题有相似的形式，亦可将其

27、抽象并建模为广义的产销平衡运输问题，从而采用运输问题的表上作业法进行求解。,112,习题1,求解如下运输问题：,113,习题2,求解如下运输问题：,114,习题3,某水产品销售公司每天从3个水产品养殖厂采购新鲜产品运往4个批发市场。3个养殖厂每天提供的水产品数量为2500、3000、4500公斤，4个批发市场每日的需求量分别为2000、2500、3000、2500 公斤。根据表5所示3个养殖厂的采购成本价和4个批发市场的价格（单位：元/千克），公司应如何安排运输可使得总利润最大？,115,习题4,有3个 牧 业 基 地 向4个 城 市 提 供 鲜 奶，4个 城 市 每 日 的 鲜 奶 需 求

28、量为16、30、24和30千升，3个基地的每日鲜奶供应量分别为30、40和50千升。已知运送每千升鲜奶的费用如表所示（单位：千元）。试确定最经济的鲜奶运输方案，且求出最小总运费。,116,习题5,假定习题3中城市A每天最低需求和总需求量分别为14和24千升，城市C每天最低需求和总需求量分别为25和40千升，其它城市需求量无变化，在最低需求必须满足的前提下，求解该问题，且求出最小总运费。,117,习题6,某干果公司从3个水果生产基地进货，在4个加工厂将水果加工成干果。假定3个水果基地的产量、4个加工厂的需求量，以及单位水果的运价如表所示。在最低需求必须满足的前提下，求总成本最低的运输方案。,11

29、8,习题7,已知2个供应方A1、A2以及3个需求方B1、B2、B3的运输问题的运价表如表所示。由于违约成本比较低，供应方A1、A2在运输成本较高的情景下可选择违约；同样，由于缺货损失比较低，需求方B1、B2、B3也可以在运输成本较低的情景下选择违约。问：根据表所示的缺货成本、违约成本，以及运输成本，如何安排运输可使得总运营成本最低？,119,第6章 目标规划,(Goal Programming),120,目标规划的提出,用线性规划来解决实际问题时，除了要满足比例性、可加性、可分性和确定性四个假设之外，通常还假设实际问题的求解目标是单一的，而且其约束条件是可以严格满足的。线性规划的弊端：现实决策

30、问题通常都有多重的、可能相互冲突的目标其约束条件也不一定必须全部严格满足目标规划(Goal Programming)的提出，正是为了消除或至少部分填补这种方法与实际应用之间的空白。,121,6.1.1 引例-目标规划的数学模型,在例1-1中，F公司每周需要根据下表确定产品A、B、C的产量，以获取最大的利润其线性规划数学模型为：本问题的求解目标是唯一的利润最大化。,122,6.1.1 引例,但现实问题往往会有多个目标，比如把上面这个例子变成：例6-1 在满足例1-1资源约束的前提下，按优先次序满足以下的目标：利润最好不少于200元；产品B为产品A的补充件，其产量最好低于产品A的一半；产品C为战略

31、性产品，其产量最好不低于5件；原材料M2最好全部使用完且不超量；原材料M1比较稀缺，最好至少有10千克的剩余。问：F公司应如何安排生产计划，能够尽可能达成以上的经营目标？,123,6.1.1 引例,问题的线性规划模型变为以下不等式组符合上述不等式组的解，就是本问题的解。经过计算，该不等式组无解。而在实际背景下，该问题显然是有解的。,124,资源约束,五个目标,6.1.1 引例,实际上，本问题前3 个优先级的目标是可以完全达成的，第(4)、(5)个目标虽然无法完全达成，但是是允许妥协的只需要在前几个目标达成的基础上，尽可能满足即可。问题出在建模的方式上以上模型将5 个原本有优先次序的、允许妥协的

32、目标变成了必须同时严格满足的目标。因此，一个在现实中有解的多目标决策问题，以线性规划的思路建模可能就无解了。目标规划的提出，正是针对这类线性规划无法解决的实际问题。,125,6.1.2 目标规划的基本概念,目标规划问题是这样一类问题：在满足刚性约束的前提下，求解一组决策变量的取值，使得不同优先级别目标的实现值与目标值之间的偏差尽可能小的线性规划问题。概念实现值与目标值、偏差变量刚性约束与柔性约束达成函数优先级与权重,126,6.1.2 目标规划的基本概念,1、目标值、实现值与偏差变量在目标规划中，描述各个目标的数学表达式称为目标表达式。对某个目标表达式期望的取值水平（不论是不超过、不少于还是等

33、于），称为该目标的目标值。当决策变量xj 的取值确定以后，某个目标表达式的实际取值称为该目标的实现值，又称为决策值。例如，例6-1中第(1)个目标的目标表达式为5x1+4x2+2x3，对此目标的期望值为200，则其目标值为200；第(2)个目标的目标表达式可写为x1 2x2，此时目标值为0。第(3)个目标的表达式x3，目标值为5。,127,6.1.2 目标规划的基本概念,实现值与目标值之间可能会存在差异，这种差异的大小在决策（确定决策变量取值）前是无法预知的，是随决策变量变化而变化的，因此称实现值与目标值之间的差异为偏差变量。因建模的需要以及适应线性规划中对变量的非负要求，偏差变量又分为正偏差

34、量，代表实现值超过目标值的偏差，记为d+负偏差量，代表实现值未达到目标值的偏差，记为d-满足非负：满足互斥：,128,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，有,129,6.1.2 目标规划的基本概念,2、刚性约束、柔性约束与达成函数在目标规划中，必须严格满足的约束条件称为刚性约束或硬目

35、标。刚性约束中不含偏差变量。目标规划中，不满足刚性约束的解为非可行解。与刚性约束相对，目标规划中允许某些目标的决策值与目标值存在偏差，这类目标称为软目标，其所对应的约束条件称为柔性约束。此即柔性约束的表达式。,130,6.1.2 目标规划的基本概念,例如，对例6-1中的第(1)个目标，其柔性约束为：同理，对于第(2)、(3)个目标，其柔性约束分别为：,131,6.1.2 目标规划的基本概念,对每个目标，决策者会表达出对决策值与目标值之间关系的期望超过、不超过或恰好等于。但仅从柔性约束本身，无法判断决策者究竟是期望达到哪一种。在此引入一个称为达成函数的表达式来表示决策者的期望。由目标规划问题的定

36、义可知，对于任一目标，决策者的期望是使决策值与目标值的偏差尽可能小，因此达成函数是仅含偏差变量，且目标是使偏差变量取最小值的目标函数,132,6.1.2 目标规划的基本概念,对于单一的目标，达成函数依决策者的期望分三种情况：超过目标值，则达成函数为。可理解为希望有正偏差，不希望有负偏差。不超过目标值，则达成函数为。可理解为希望有负偏差，不希望有正偏差。恰好等于目标值，则有，亦即正、负偏差量都要尽可能地小。结合柔性约束与达成函数，就可以写出每个目标的目标表达式。,133,6.1.2 目标规划的基本概念,例如，第(1)个目标的达成函数为利润最好不少于200：第(2)个目标的表达式为产品B产量最好低

37、于产品A一半：第(4)个目标的表达式为原材料M2最好全部使用完且不超量：,134,6.1.2 目标规划的基本概念,3、优先级与权重以上的分析只针对单一目标，当问题中有多个主次不同的目标，且各个目标之间可能存在矛盾时，就需要以某种方式将各个目标的达成函数合并成一个单一的达成函数。目标规划通过引入优先级来为不同目标的达成函数加权。具体为，在合并达成函数时，将目标按重要程度进行优先级排序，第1 优先级目标的达成函数乘以优先因子P1，第2 优先级目标的达成函数乘以P2，依次类推，第L 优先级目标的达成函数乘以优先因子PL，且规定由此保证优先实现P1 级的目标，在此基础上再考虑P2 级目标的实现，然后依

38、次类推。,135,6.1.2 目标规划的基本概念,某些实际问题中同一优先级下可能有多个目标，这些目标的重要程度还可以有差异，只不过这种差异不是数量级上的，目标规划用权重来区分这种差异。在建模时，可以根据决策者的需求，对该优先级Pl 下某个目标k的达成函数以权系数wlk 加权后再相加。注意：优先级的划分，以及同一优先级下多个目标的权重的设定，没有普适性的规则，而应根据决策者的需求和偏好来确定。-主观性在不同的问题背景或决策者偏好下，同一个目标的优先级或其在某个优先级中的权系数都可能有不同的设定。,136,6.1.2 目标规划的基本概念,根据上述概念，可以写出例6-1的目标规划模型。整个问题的达成

39、函数可以写为上式所示的“和”的形式，也可以写为“集合”的形式：,137,6.1.3 目标规划模型及建模步骤,目标规划问题的数学模型的一般形式为：自上而下分别是达成函数、刚性约束、柔性约束和所有变量的非负约束,138,6.1.3 目标规划模型及建模步骤,建模步骤：第1步 设定问题的决策变量；第2步 列出问题的刚性约束；第3步 根据决策者的需求和偏好，设定各个目标的优先级，当有多个目标同属于一个优先级下时，还需根据约定设定各个目标的权重；然后，写出各个目标的柔性约束和各优先级的达成函数；第4步 用优先因子和权系数为各个目标的达成函数加权，写出整个问题的达成函数。第5步 写出决策变量与偏差变量的非负

40、约束。,139,例6-2 在例6-1中，假定不要求严格满足资源约束，且各优先级的目标依次如下：利润最好不少于180元；产品A的产量最好不多于25件、产品B的产量最好不少于15件、产品C的产量最好不少于5件，且根据单位产品的利润确定权系数；原材料M2最好全部使用完，不足时可购入，原材料M1比较稀缺，最好至少有10千克的剩余。问：F公司应如何安排生产计划，能够尽可能达成以上的经营目标？,140,解：用x1，x2 和x3 表示产品A，B 和C 的产量。,141,例6-3 电子产品生产企业HF公司通过采购半成品生产A、B、C三种型号的手机。这三种手机在同一流水线上生产，每件的生产工时消耗分别为5分钟，

41、7分钟，12分钟，利润分别为每台140元，210元，384元。生产线正常运转时间为250小时/月，加班满负荷运转时最多有400小时/月。HF公司的决策者提出的月经营目标按优先级排序为：尽可能充分利用生产线的正常工时，工时不够用时可以加班；希望A、B、C的产量至少达到700，750，500台，根据单位工时的利润比例设定权系数；加班工时最好不超过40小时/月；希望A、B、C的产量尽可能超过月销售量预测的最低水平800，900，550台，根据单位工时的利润比例设定权系数。问：各产品应生产多少才能达成上述经营目标？建立本问题的其目标规划模型。,142,解：设A、B、C 的产量分别为x1,x2,x3。,

42、143,例6-4 SD 公司下属三个工厂生产某种产品来满足四个地区的需求，各工厂的产量、各地的需求量以及从各工厂到四地的单位产品运输费用如下表所示。如果仅要求运输费用最小，在将该问题转化为产销平衡问题后，用运输问题表上作业法求解得最低总运费为2750 元。但是考虑到各地的不同情况和运输中可能存在的问题，该公司在确定最后运输方案时还需考虑其它几个目标，按重要程度依次为：P1：地区3 为重点销售地区，其需求应优先全部满足；P2：用于供应地区2 的产品中，工厂1 的产品不少于80 件；P3：为平衡各地需求，每个地区用户需求的满足率应不低于90%；P4：由于交通条件的限制，应尽量避免从工厂2 运输至地

43、区2；P5：尽可能减少总运费。,144,145,6.2 两变量目标规划问题的图解法,146,6.2两变量目标规划问题的图解法,目标规划模型中对目标进行了优先级的区分，这决定了其求解过程是一个分级进行的过程：对于有L 个优先级的目标规划问题，先在可行域内寻找满足P1级目标的解然后在保证P1级目标不被打破的前提下，再寻找满足P2级目标的解依次类推如果用解空间的概念，求解过程又可以表述为：在可行域R0 内找到满足P1 级目标的解空间R1，再以R1 为可行域寻找满足P2 级目标的解空间R2，依次类推，直至在RL-1 内寻找PL 级目标的解空间RL，其中目标规划的最终求解结果通常只能称为满意解即只能保证

44、优先级较高的目标得以实现或部分实现，不保证优先级低的目标能实现。,147,6.2两变量目标规划问题的图解法,步骤第1 步 在坐标平面第一象限表示出由刚性约束所确定的可行域，以此可行域为初始解空间R0；第2 步 选定P1优先级的目标，进入第3步；第3 步 在Rl-1 中找到满足Pl级目标的解空间进入第4步Rl；第4 步 当所有优先级的目标都处理完时，求解结束，问题的满意解就是目前得到的解空间；或者，如果Rl 为一个点，求解结束，问题的满意解就是该点的坐标。如果上述条件皆不满足，则转到下一个优先级，返回第3 步。,148,图解法示例,例6-5 用图解法求解,149,150,151,152,153,

45、154,155,156,157,158,图解法示例,例6-6 用图解法求解,159,160,161,162,163,164,165,166,6.2两变量目标规划问题的图解法,应用图解法求解只有两个决策变量、且一个优先级 Pl下有多个目标的目标规划模型时，确定 Pl优先级的解空间 Rl的过程就会变得比较复杂，见例6-7(略)。,167,6.4 用Excel求解目标规划问题,掌握了序贯解法的原理，理解将目标规划问题转化为一系列线性规划问题的方式，再进一步用Excel规划求解工具完成。略。,168,169,第9章,网络计划技术(Network Planning Technique),基本概念,网络计

46、划技术（项目进度管理）它利用网络图的形式直观表现出工程项目中各项任务之间的相互关系，从而找出决定项目总工期的关键路线和关键工序。进而，在一定工期、成本、资源等约束条件下通过各种技术手段获得最佳的计划安排，以达到缩短工期、提高工效、降低成本的目的。,170,引例,171,16分钟,引例,172,20分钟,发展历程,网络计划技术根据起源可以分为关键路径法（CPM-Critical Path Method-Walker and Kelly）和计划评审技术（PERT-Program Evaluation and Review Technic-U.S.Navy）两个源头。关键路径法强调/要求所研究项目中

47、每项任务的执行时间必须是明确的，而计划评审技术中每项任务的执行时间可以是一个估计值/不确定值。因此，关键路径法主要应用于一些有前期经验的工程项目，而计划评审技术更多应用于研究与开发项目的计划管理。1962,钱学森-华罗庚-“统筹法”,173,基本流程,1-阐明问题，将项目分解为若干个可以独立的工作单元，并明确各个工作单元的相关属性（资源使用、时间消耗、成本计算等），以及工作单元之间的逻辑先后关系。2-根据分解后的工作单元，以及工作单元之间的逻辑先后关系，绘制网络图。,174,基本流程,3-应用关键路径法计算得到整个项目的最短完成时间，项目中每项工序的最迟开始时间、最早可能开始时间等时间参数，整

48、个项目的关键路径以及关键路径上的各项关键工序。4-根据具体应用，对关键路径上的关键工序进行资源的合理安排和优化。,175,双代号网络图的绘制方法,工作单元用有向箭线来表示，箭线的方向表示工序进行的方向：箭线的箭尾表示该工序的开始，箭线的箭头表示该工序的结束。工序的名称或者代号标注在箭线的上方，工序所花费的时间标注在箭线的下方。,176,双代号网络图的绘制方法,多条箭线指向该节点代表着多条箭线所指的工序都完成之后，该节点之后的工序才可以开始E的紧后工序F，同理，C、D、E是F工序的紧前工序。多条箭线从该节点引出代表着该节点所代表的之前的工序结束后，可以同时开始多项工序。,177,双代号网络图的绘

49、制方法,1-网络图中箭线尽量从左指向右，从上至下，从小到大，节点的编号按顺序编排，不允许重复。2-两个节点之间，如果有，只能有一条箭线。3-网络图中只能有一个起始节点和一个终止节点。4-不能有缺口和回路。除了起始点和终止点，任何节点都必须有至少一条箭线指向和引出该节点。,178,双代号网络图的绘制方法,如果节点之间需要包含两个或两个以上的箭线，即表示多个工序可以同时开始，并同时作为后续工序的紧前工序，那么需要使用虚工序（虚线的箭线）来帮助表示。,179,双代号网络图的绘制方法,180,双代号网络图的绘制方法,181,双代号网络图的绘制方法,182,双代号网络图示例1,例9-1,183,双代号网

50、络图示例1,184,双代号网络图示例2,185,单代号网络图的绘制方法,节点表示工序，有向箭线描述工序之间的逻辑关系紧前/紧后工序：箭尾连接的节点工序为箭头连接的节点工序的紧前工序。单代号网络不需要使用类似双代号网络中的虚工序。,186,单代号网络图的绘制方法,187,单代号网络图的绘制方法,188,单代号网络图的绘制方法,189,单代号网络图示例1,例9-3,190,单代号网络图示例1,例9-3,191,单代号网络图示例2,192,习题1,193,194,195,习题2,196,197,习题3,198,199,习题4,200,201,关键路径法,从开始节点出发，沿着不同的路径到达终止节点所花