1、1工程硕士运筹学内蒙古工业大学管理学院内蒙古工业大学管理学院 课程内容n绪论绪论n线性规划基础线性规划基础n线性规划的图解法、用线性规划的图解法、用Excel解解LP问题问题n整数规划整数规划n运输问题运输问题n目标规划目标规划n图论图论n动态规划动态规划n网络计划技术网络计划技术23第0章绪论Introductions to Operations Research运筹学的实用价值公司公司应用问题应用问题收益收益/效果效果惠普公司预测消费者的购买行为，从而优化库存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章线性规划基础(Introduction to Linear Programming)目标n
5、1.常见线性规划问题的数学建模思路n2.建模的适用范围n3.“解”的概念n4.图解法n5.EXCEL求解一般线性规划问题（练习）1314线性规划的定义n在满足一组线性约束条件（等式或不等式）的前提下，使得某一个线性目标函数取得极值（最大值或最小值）。这类问题的模型及其优化求解技术，被统称为线性规划(Linear Programming,LP)。nIn mathematics,LP problems are optimization problems in which the objective function and the constraints are all linear.线性规划数学
6、模型n线性规划问题的一般模型151 12211 1122121 12212221 12212,),)max/min(.(,0,)nnnnnnmmnmmnnZc xc xc xa xa xa xsta xa xa xa xaxaxbx xbbx 线性规划数学模型n模型特点n1-所有表达式均为线性表达式n2-目标为求目标函数Z的最大值(max)或最小值(min)n3-约束条件为”/=”，没有”/”！n4-通常要求决策变量取值非负161 12211 1122121 122221 1222112max/mi.n(,)(,)(,)(,),0nnnnnnmmmnmnnZc xc xc xa xa xa x
7、sta xa xbbba xa xaxaxx xx 17应用问题示例(1)-生产计划n F公司每周根据原材料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：不少于产品
8、重量的45%M3：不超过产品重量的50%M4：产品重量的20%应用问题示例(2)n原材料M3和M4采购量超过市场供应总量的一半。n采购预算费用为25万元人民币。n问：根据产品的市场价格以及原材料价格，公司应如何采购以获得最多的利润？19原材料原材料M1M2M3M4市场供给300200400300市场价格300600400500应用问题示例(2)n建模思路1-20311,2,3,4;1,2,34,1,2,3,4jijjiijijzyijxy zxi定义：变量 表示 种产品的生产数量，为原材料在产品中的配方比率，为原材料的购买数量。各产品中原材料使用量与配方比例和产量之间的关系为：与线性规划定“约
9、束条件必须为线性义中相矛盾！”思路不可行。应用问题示例(2)n正确的建模方法-214141311,2,3,4;1,24,33ijijjiijijiijijjjiixijPMPMPxxxM定义：产品 中原材料的使用量为x。产品 的总产量为（种原材料之和），原材料在产品 中的配方比率为，原材料总使用量为（种产品中该原材料使用之和）。应用问题示例(2)221111213141211121314113132333431121314113233343()0.35()0.45()0.750.650.350.350.3500.250.750.750.750 xxxxxxxxxxxxxxxxxxxxxxx不同
10、原料在不同产品中配方比率的约束，即：整理得到，应用问题示例(3)-财务计划n某集团公司未来6年年初的现金需求（万元）如下所示。为此，公司决定在今年年底一次性划拨一笔资金，未来6年不再划拨。23年份年份123456现金现金350 405 355 260 215 230应用问题示例(3)n公司可以通过多种投资形式减少资金的需求：n1-银行一年期的定期存款，年利率为3%；n2-国债（只能在第1年年初购买；国债的实际购买价格要高于其票面价格，且只能在到期日按票面价格收回本金）n问：集团公司最少需要划拨多少资金，并如何投资，才能满足未来6年的现金需求？24债券类型票面价格实际购买价格年利率到期年限110
11、,00012,0007.84210,00014,30010.75应用问题示例(3)n由于6年内不再追加投资，因此6年内的投资（银行定期存款方式）必然不能超过当年现金需求的余额。并且，由于投资总能够获得更多的回报（103%），所以投资等于当年现金需求的余额！25121611 2,定义：设划拨资金总额为万元，第 年年初所购买的、型债券的票面总金额分别为 万元，每年年初存入的银行一年期定期存款金额分别为。aabbxxxx应用问题示例(3)n采用表格形式更加直观展示出投资与回报。n年末的收益可以作为下一年年初的投资。回报回报第第1年年年末年末第第2年年年末年末第第3年年年末年末第第4年年年末年末第第5
12、年年年末年末第第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.1071212121312241235124621350 1.21.432405=0.0780.1071.033355=0.0
13、780.1071.034260=0.0780.1071.035215=1.0780.1071.036230=1.1071.0aabbaabbaabbaabbaabbaxxxyxxxxxxxxxxxxxxxxxx第 年：第 年：第 年：第 年：第 年：第 年：53bx应用问题示例(3)n完整问题模型如下：281211212122312341245256min.1.21.433500.0780.1071.03=4050.0780.1071.03=3550.0780.1071.03=2601.0780.1071.03=2151.1071.03=230,aabaabbaabbaabbaabbabbab
14、ijZystyxxxxxxxxxxxxxxxxxxxxxxy xx0,1,2;1,6ij 应用问题示例(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应用问题示例(4)n根据问题描述，可以定义自行生产和外购的组件数量为决策变量。并且，外购组件的数
15、量与生产能力也有关，因此需要定义实际加班工时为决策变量，即：301212231321212231320112221323,CPCPCPCPC,定义:变量 为组件的实际生产数量；变量用于产品 的组件 的实际生产数量；变量用于产品 的组件 的实际生产数量；变量用于产品 的组件 的实际生产数量；变量用于产品 的组件 的实际生产数量；类似地，定义变量分别为外购各组件的数量；定义变量 为实际使用的加班工时。xxxxxy yyyyx应用问题示例(4)3101212231320112121222231313232011212122223131100+1.54323100min1.288.5671.521.8
16、2.1122600.16001000生产所有组件所消耗的工时不能超出总工时（正常工时 加班工时 x ），即：整理得到本问题的模型如下：xxxxxxZxyxyxyxyxyxxystxyxyxy323201212231320112121222231313232016001000601.54323100,0 xyxxxxxxxx y xyxyxyxyx应用问题示例(5)-运输与分销n运输与分销问题n问：如何安排物流路线，实现总运输成本最小。32应用问题示例(5)n定义决策变量为各条路线上的运输量，各变量对应的路线如下所示。33应用问题示例(5)n对于此类以图形方式给出的物流问题，存在以下函数关系，即
17、图中每个节点，都必须满足“输入=输出”。34应用问题示例(5)n源头节点“工厂1 3”，关系为“产量+运入量=运出量”。351231231231=50=0 11 1 1250+0=50 xxxxxxxxx以工厂 为例：产量运入量运出量分别为（工厂 到仓库），（工厂 到分销中心），（工厂 到工厂）整理得到：，即应用问题示例(5)n中间节点“分销中心”，关系为“运入量=运出量”。36246824682468 1 2 3 2=0 xxxxxxxxxxxx运入量分别为（工厂 到分销中心），（工厂 到分销中心），（工厂 到分销中心）运出量为（分销中心到仓库）整理得到：，即应用问题示例(5)n终止节点“仓
18、库1 2”，关系为“运入量=运出量+需求量”。371109110911091=80 11 21 12=8080 xxxxxxxxx以仓库 为例：需求量运入量分别为（工厂 到仓库），（仓库 到仓库）运出量为（仓库 到仓库）整理得到：，即应用问题示例(6)-套裁下料问题n某建筑公司需要钢管规格和数量分别为：3m的600根、4m的300根、5m的200根。n如果只能选择购入长度为11m的钢管自行切割，M公司至少应采购多少根11m的钢管？38应用问题示例(6)n某建筑公司需要钢管规格和数量分别为：3m的600根、4m的300根、5m的200根。n如果只能选择购入长度为11m的钢管自行切割，M公司至少应
19、采购多少根11m的钢管？39应用问题示例(6)401231231,65m1 2 35m22200iixxxxxxx表示用第i种方法切割的钢管的数量。则，长度为的钢管可以通过第、种切法得到。根据切法的不同，得到管总数为这个数量必须满足需求量，于是有约束条件：定义应用问题示例(6)n思考题：如果目标函数改为“如果购入这些长度为11m的钢管自行切割，RE公司应如何切割废料最少？”41123456min11200 5-600 3300 4 Zxxxxxx42线性规划模型的假设条件n比例性假定：要求目标函数值、约束条件左端取值与决策变量的取值呈严格的比例关系。线性规划模型的假设条件4344线性规划问题的
20、标准图解法线性规划问题的标准图解法n对于只包含2个变量的线性规划问题，可以通过标准图解法来求解。其解题步骤为：45标准图解法示例1n用标准图解法求下面的线性规划问题（例1-8）12121212max35.463218,0Zxxstxxxxx x 标准图解法示例146标准图解法示例2n应用标准图解法求解线性规划问题（例1-9）4712121212max1.20,0Zxxxxs txxx x标准图解法示例24849线性规划问题的重要推论n1-如果线性规划问题的可行域非空且有界，那么线性规划问题一定有最优解；n2-如果线性规划问题的可行域无界，那么该问题可能有无界解；n3-如果线性规划问题的最优解在
21、可行域的两个顶点上同时得到，那么这两个顶点连线上的所有点都是最优解（有无穷多最优解）；n4-如果线性规划问题的可行域为空，意味着该线性规划问题无可行解。50简化的图解法n对于可行域为封闭凸多边形的两变量线性规划问题，可以采用简化的图解法求解：只需要穷举出可行域的所有顶点，计算每一个顶点的目标函数值，就可以找出最优解。简化的图解法示例1n线性规划问题（例1-8）51顶点顶点坐标坐标目标目标函数值函数值X1X2A000B4012C4327D2636E063052Excel求解线性规划问题n“规划求解”工具主界面Excel求解LP问题示例1n线性规划问题（例1-8）53练习题-图解以下线性规划问题5
22、455n某手工作坊生产的竹制座椅中需要用到3种规格楠竹片，每张椅子需要长度为60cm、40cm和 30cm 的楠竹片 2、6和2 片。可以在市场上采购这些规格的现货，也可以将作坊仓库中长度为110cm的楠竹片切割成所需的规格，但每切割1次会发生1cm的长度损耗。问：如果要制作100张竹制座椅，该作坊的仓库中至少要有多少条长度为110cm的楠竹片，才不用去市场上采购？试建立本问题的线性规划模型。56575859第2章整数规划(Integer Linear Programming)基本概念n线性规划模型中增加了决策变量的整数约束，这类数学规划问题被称为整数规划(Integer Linear Pro
23、gramming,ILP)问题。n整数规划模型虽然只是在线性规划模型中增加了决策变量的整数约束，但是其求解过程却变得非常复杂。（简单的四舍五入？）n车辆调度、人员安排、产品产量60基本概念n根据全部还是部分全部还是部分决策变量必须满足整数约束，整数规划问题可分为两类：n纯整数规划（Pure Integer Programming,PIP）n混合整数规划（Mixed Integer Programming,MIP）n根据整数变量取值的范围，整数规划问题还可分为：n一般整数规划-整数变量的取值可以是任意非负整数n0-1整数规划（Binary Integer Programming,BIP）-要求决
24、策变量只能取值0或者161基本概念62n一般整数规划问题的数学模型()()max.0,ZstIICXAXbXXXX且为整数()基本概念63n0-1整数规划问题的数学模型()()max.0,01ZstBBCXAXbXXXX且或()()()()max.10,且为整数()IIIZstCXAXbXXXXX应用问题建模n设施布点问题n某市在其5个规划片区规划消防站设点，要求任意一个片区发生火警时，本片区或来自其它片区的消防车可以在15分钟内赶到。虽然在各片区各设一个消防站可以解决此问题，但为提高资源利用率，市政府提出消防站数量应尽可能少。64应用问题建模n背包问题（0-1）n某家庭计划自驾野外露营，出发
25、前需考虑携带的物品，各物品的压缩体积及重要程度如表所示。由于其自驾车最大容纳的物品体积为650升，不可能所有物品都能装入车中。n问：应选择哪些物品出行？65应用问题建模n指派问题n有5项任务需要5个员工独立完成，由于能力差异，不同员工完成同一任务的执行成本不同。下表给出了员工i完成任务j的执行成本cij。n问：如何指派任务可以最经济地完成各项任务。66应用问题建模n将n项任务分配给n个人，约定每人只能完成一项工作，每项工作也只能由一个人来完成，但由于每个人能力各不相同，完成各项工作的收益和成本不同。根据不同的问题背景，可要求得到总利润最大或总成本最小的指派方案。这类问题在运筹学中被称为一种专门
26、的问题：指派问题(Assignment Problem)。67应用问题建模68n定义0-1变量xij(i,j=1,n)表示第i个人是否被指派完成第j项任务（0代表不指派，1代表指派），则指派问题的数学模型为：1111max/min().1,(1,)1,(1,)01,(,1,)或nnijijjinijinijjijZc xstxjnxinxi jn应用问题建模n含有互斥项目的计划n1.如果携带食物，就必须同时携带野外厨具和洗漱用品；n2.通信设备和应急医疗用品至少要携带1件；n3.帐篷和防晒防雨最多只能选择1项；n4.野外厨具、摄影器材和通信设备最多选2项。69应用问题建模n含有互斥约束条件的计
27、划n某公司用两种原料E1和E2生产A、B两种产品，生产过程均需经过甲、乙两道工序。甲、乙两道工序又各可以采取2种生产工艺。n甲工序可以混合使用甲1和甲2两种工艺，而乙工序只能在乙1和乙2中选择其中一种工艺。n问：该公司应如何安排生产可使利润最大？70n在建模中对互斥的约束处理时，可以引入Mi来实现使某个约束条件有效或者冗余，其中Mi为任意大的正数。71Mi iM固定成本问题n某工厂用两条生产线1和2生产两种产品A和B。这两条生产线每个月的额定工时分别为600和800小时，生产线1的生产率为产品A 60件/小时或产品B 45件/小时，生产线2的生产率为产品A 35件/小时或产品B 40件/小时；
28、产品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可以取任意
29、正整数。74n所以，上题的决策变量定义如下：7576分枝定界法n分枝定界技术是一种求解优化问题的通用思想，其逻辑思路是：n把原始问题分解成若干个足够小的可以直接求解的子问题，此为分枝过程(Branching)；n对于每个子集及其对应的子问题，考察其最优解是否足够好是否可能包含原始问题的最优解，此为定界过程(Bounding)；n结束某些子问题的分枝过程，并根据定界过程的结果，放弃那些不可能包含原始问题最优解的子集及子问题，此为剪枝过程(Fathoming)。77割平面法78习题1n某大型社区临街的中式快餐店每天的营业时间为8:00到24:00，根据社区居民对早餐、中餐、晚餐和夜宵的需求不同，一
30、天中不同时段对服务员的需求如图所示。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)可供选择。现要求所设立的销售网点必须满
31、足以下条件：在东部地区，1,2,3三个备选地点中至多选择两个地点设立销售网点；在西部地区，4,5两个备选地点中至少选择一个地点设立销售网点；在南部地区，6,7两个备选地点只能选一个设立销售网点；出于市场环境的考虑，如果方案中选择了2地点，必须选择在5同时设立销售网点。n若在备选地点设立销售网点需要投资万元，每年可获得利润万元。问：如果总投资预算为B万元，在哪些备选地点设立网点可获得最多的利润？试建立本问题的数学模型。8384习题3n某短途航空公司有10条联飞路线，可经停9个城市，下表给出了这10条飞行路线经停的城市和飞行总小时数（单位：小时）。试从这10条路线中选择3条路线，既能够满足飞行总时
32、间最少的要求，又能够经停9个城市至少1次。给出本问题的0-1整数规划模型。8586n则其目标函数为：nMin（Z）=？8788习题4n 某小提琴手作坊根据顾客提出的定制需求生产小提琴，价格和固定成本因定制需求而异。由于作坊的熟练技师有限(12人)，该手工作坊只能挑选部分订单，甚至只能部分完成订单所要求的数量。目前，作坊收到来自3家交响乐队的小提琴订单，下表给出了与此订单相关的制作成本和价格（单位：元）。n问：各订单各应接受多少台，可获得最多的利润？试建立本问题的整数规划模型。899091习题5n某工厂生产A和B两种型号的产品，其生产过程须经过甲、乙、丙三个流水线车间加工，其中，乙车间有两条加工
33、效率不同的流水线乙1和乙2。n已知乙车间的两条流水线只能任选一条使用，问：如何安排生产可获得最大的利润。建立本问题的整数规划模型。929394第5章运输问题(Transportation Problems)基本概念n将某种物资从若干个产地运输到另外若干个销地，要求总运费最小的问题，这一类问题及其衍生问题统称为运输问题(Transportation Problem)。95引例nFreshFruit公司旗下有3个苹果种植基地，预计年产量分别为75、125和100吨，近期该公司与4个不同地区的客户签订了今年的苹果供应合同，其销量分别80、65、70和85吨。由于交通条件差异，从3个基地到4个客户所在
34、地的单位运费不同，其运价表如表所示。96运输问题的数学模型97n运输问题通常为：从m个产地向n个销地运输某种物资，产地i到销地j的单位运费是cij（呈比例关系），产地i的产量是ai，销地j的销量是bj，要求找到使得总运费最小的运输方案。n当问题满足总产量与总销量相等，这类问题称为标准运输问题，或者产销平衡运输问题。运输问题的数学模型n标准运输问题的数学模型为：98标准运输问题的表上作业法n作为一种特殊的线性规划问题，标准运输问题模型并不包含天然的基变量和初始基本可行解，求解时需要在每个等式中引入人工变量，计算较为烦琐。n对于标准运输问题，在某种特殊形式的表格上来应用单纯形法，可使求解过程大大简
35、化，这种方法叫作运输问题的表上作业法。n需特别强调的是，用表上作业法求解运输问题，产销平衡是一个基本前提。99标准运输问题的表上作业法n解题步骤：n1-初始化 给出初始基本可行方案；n2-迭代n第1步基本可行方案的最优判定，判断当前基本可行方案是否最优。如果不是，进入第2步；n第2步基本可行方案的改进，然后返回第1步；100标准运输问题的表上作业法n运输问题作业表/产销平衡表101标准运输问题的表上作业法102n西北角法n从作业表的西北角往东南角逐步填写运输量。西北角法示例1103西北角法示例1104标准运输问题的表上作业法105n最小元素法n按照单位运费由低到高的次序来选择每次迭代中指派运输
36、量的单元格。最小元素法示例1106最小元素法示例1107产销不平衡的运输问题示例108转运问题n(1)确定标准运输问题中的产地和销地：转运点既是产地，又是销地。也就是说，标准运输问题中的产地为原始转运问题中的产地和所有的转运点，销地为原始问题中的销地和所有的转运点。n(2)确定各产地的产量和销地的销量：将原始转运问题中产地的产量和销地的销量直接移植入标准运输问题；转运点的产量和销量相同，数值都为经过该转运点的最大可能转运量。109转运问题n(3)确定各产地与销地之间的单位运输费用：将原始问题中已知的两地之间的单位运输费用移植入标准运输问题；各转运点到其自身的单位运输费用为0；对于原始转运问题中
37、不存在的运输路线，单位运费为无穷大，用任意大的正数表示。110转运问题示例1111其它问题n一些应用问题虽然与物资运输、分销没有任何联系，但是由于其问题背景与运输问题有相似的形式，亦可将其抽象并建模为广义的产销平衡运输问题，从而采用运输问题的表上作业法进行求解。112习题1n求解如下运输问题：113习题2n求解如下运输问题：114习题3n某水产品销售公司每天从3个水产品养殖厂采购新鲜产品运往4个批发市场。3个养殖厂每天提供的水产品数量为2500、3000、4500公斤，4个批发市场每日的需求量分别为2000、2500、3000、2500 公斤。根据表5所示3个养殖厂的采购成本价和4个批发市场的
38、价格（单位：元/千克），公司应如何安排运输可使得总利润最大？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个水果生产基地进
39、货，在4个加工厂将水果加工成干果。假定3个水果基地的产量、4个加工厂的需求量，以及单位水果的运价如表所示。在最低需求必须满足的前提下，求总成本最低的运输方案。118习题7n已知2个供应方A1、A2以及3个需求方B1、B2、B3的运输问题的运价表如表所示。由于违约成本比较低，供应方A1、A2在运输成本较高的情景下可选择违约；同样，由于缺货损失比较低，需求方B1、B2、B3也可以在运输成本较低的情景下选择违约。问：根据表所示的缺货成本、违约成本，以及运输成本，如何安排运输可使得总运营成本最低？119第6章 目标规划(Goal Programming)120目标规划的提出n用线性规划来解决实际问题时
40、，除了要满足比例性、可加性、可分性和确定性四个假设之外，通常还假设实际问题的求解目标是单一的，而且其约束条件是可以严格满足的。n线性规划的弊端：n现实决策问题通常都有多重的、可能相互冲突的目标n其约束条件也不一定必须全部严格满足 n目标规划(Goal Programming)的提出，正是为了消除或至少部分填补这种方法与实际应用之间的空白。1216.1.1 引例-目标规划的数学模型在例1-1中，F公司每周需要根据下表确定产品A、B、C的产量，以获取最大的利润其线性规划数学模型为：本问题的求解目标是唯一的利润最大化。122123123123123max542845320.22100,0Zxxxxx
41、xstxxxx xx6.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
42、12312312384532022100,0 xxxxxxx xx123542200 xxx1220 xx35x 12322100 xxx123845310 xxx 资源约束五个目标6.1.1 引例n实际上，本问题前3 个优先级的目标是可以完全达成的，第(4)、(5)个目标虽然无法完全达成，但是是允许妥协的只需要在前几个目标达成的基础上，尽可能满足即可。n问题出在建模的方式上n以上模型将5 个原本有优先次序的、允许妥协的目标变成了必须同时严格满足的目标。因此，一个在现实中有解的多目标决策问题，以线性规划的思路建模可能就无解了。n目标规划的提出，正是针对这类线性规划无法解决的实际问题。1256.
43、1.2 目标规划的基本概念n目标规划问题是这样一类问题：n在满足刚性约束的前提下，求解一组决策变量的取值，使得不同优先级别目标的实现值与目标值之间的偏差尽可能小的线性规划问题。n概念n实现值与目标值、偏差变量n刚性约束与柔性约束n达成函数n优先级与权重1266.1.2 目标规划的基本概念n1、目标值、实现值与偏差变量、目标值、实现值与偏差变量n在目标规划中，描述各个目标的数学表达式称为目标表达式。n对某个目标表达式期望的取值水平（不论是不超过、不少于还是等于），称为该目标的目标值。n当决策变量xj 的取值确定以后，某个目标表达式的实际取值称为该目标的实现值，又称为决策值。n例如，n例6-1中第
44、(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满足互斥：128,0dd0
45、dd6.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，有12911dd和11013dd和2201dd和3300dd和6.1.2 目标规划的基本概念2、刚性约束、柔性约束与达成函数n在目标规划中，必须严格满足的约束条件称为刚性约束或硬目标。n刚性约束中不含偏差变量。目标规划中，不满足刚性约束的解为非可
46、行解。n与刚性约束相对，目标规划中允许某些目标的决策值与目标值存在偏差，这类目标称为软目标，其所对应的约束条件称为柔性约束。此即柔性约束的表达式。130iidd目标表达式目标值6.1.2 目标规划的基本概念n例如，对例6-1中的第(1)个目标，其柔性约束为：同理，对于第(2)、(3)个目标，其柔性约束分别为：13112311542200 xxxdd1222333205xxddxdd6.1.2 目标规划的基本概念n对每个目标，决策者会表达出对决策值与目标值之间关系的期望超过、不超过或恰好等于。n但仅从柔性约束本身，无法判断决策者究竟是期望达到哪一种。在此引入一个称为达成函数的表达式来表示决策者的
47、期望。n由目标规划问题的定义可知，对于任一目标，决策者的期望是使决策值与目标值的偏差尽可能小，因此达成函数是仅仅含偏差变量，且目标是使偏差变量取最含偏差变量，且目标是使偏差变量取最小值小值的目标函数132min(,)iif dd6.1.2 目标规划的基本概念n对于单一的目标，达成函数依决策者的期望分三种情况：n超过目标值，则达成函数为 。可理解为希望有正偏差，不希望有负偏差。n不超过目标值，则达成函数为 。可理解为希望有负偏差，不希望有正偏差。n恰好等于目标值，则有 ，亦即正、负偏差量都要尽可能地小。n结合柔性约束与达成函数，就可以写出每个目标的目标表达式。133minidminidmin()
48、iidd6.1.2 目标规划的基本概念n例如，第(1)个目标的达成函数为利润最好不少于200：第(2)个目标的表达式为产品B产量最好低于产品A一半：第(4)个目标的表达式为原材料M2最好全部使用完且不超量：1341mind12311542200 xxxdd21222min20dxxdd4412344min22100ddxxxdd6.1.2 目标规划的基本概念3、优先级与权重n以上的分析只针对单一目标，当问题中有多个主次不同的目标，且各个目标之间可能存在矛盾时，就需要以某种方式将各个目标的达成函数合并成一个单一的达成函数。n目标规划通过引入优先级来为不同目标的达成函数加权。n具体为，在合并达成函
49、数时，将目标按重要程度进行优先级排序，第1 优先级目标的达成函数乘以优先因子P1，第2 优先级目标的达成函数乘以P2，依次类推，第L 优先级目标的达成函数乘以优先因子PL，且规定n由此保证优先实现P1 级的目标，在此基础上再考虑P2 级目标的实现，然后依次类推。135121llLPPPPP6.1.2 目标规划的基本概念n某些实际问题中同一优先级下可能有多个目标，这些目标的重要程度还可以有差异，只不过这种差异不是数量级上的，目标规划用权重来区分这种差异。n在建模时，可以根据决策者的需求，对该优先级Pl 下某个目标k的达成函数以权系数wlk 加权后再相加。n注意：注意：n优先级的划分，以及同一优先
50、级下多个目标的权重的设定，没有普适性的规则，而应根据决策者的需求和偏好来确定。-主观性主观性n在不同的问题背景或决策者偏好下，同一个目标的优先级或其在某个优先级中的权系数都可能有不同的设定。1366.1.2 目标规划的基本概念n根据上述概念，可以写出例6-1的目标规划模型。整个问题的达成函数可以写为上式所示的“和”的形式，也可以写为“集合”的形式：137122334445512312312311122233312344123551123()845320.221005422002052210084m5310,0,1,in,5iidddddxxxstxxxxxxddxxZddxddxxxPdPPd
