《数据、模型与决策_(第二版)》第三章线性规划

第二篇规划和优化模型第三章线性规划数据、模型与决策(第二版)第三章线性规划第三章线性规划数据、模型与决策(第二版)学习目的线性规划是运筹学的一个重要分支。通过对本章的学习要求：•能够掌握线性规划问题中的主要概念•能够掌握线性规划问题中的线性规划的标准形式•能够掌握线性规划问题的求解方法——图解法及单纯形法•理解线性规划问题解的概念和基本定理•了解线性规划问题的敏感性分析以及善于建立线性规划模型来解决一些实际问题。第三章线性规划数据、模型与决策(第二版)第三章线性规划•3.1线性规划问题概述•3.2线性规划问题的图解法•3.3单纯形法•3.4对偶问题•3.5敏感性分析第三章线性规划数据、模型与决策(第二版)3.1线性规划问题概述•3.1.1线性规划问题中的主要概念•3.1.2线性规划问题的数学模型第三章线性规划数据、模型与决策(第二版)3.1.1线性规划问题中的主要概念•目标（objective）:所要达到的最优结果（最大或最小）。•约束条件（constraints）：对所能产生结果的限制。•线性规划：一种解决带有约束条件的最优化问题的方法。•解决线性规划问题的步骤定义问题和收集数据。建立模型，用恰当的数学式子表示问题求出问题的最优解进行敏感性分析，检查条件发生变化是会发生的情况。第三章线性规划数据、模型与决策(第二版)确定潘得罗索工业公司的产品组合•潘得罗索工业公司是一家墨西哥公司，截至在1998年的销售，公司生产了全国胶合板产量的四分之一，与其他胶合板生产厂商一样，潘得罗索工业公司的许多产品根据厚度和所用木材的质量而有所不同。因为产品在一个竞争的环境中进行销售，产品的价格由市场决定，所以产品的价格每月都有很大的变化。结果导致每项产品对公司整体利润的贡献也有很大的变动。•从1980年开始，潘得罗索工业公司管理部门每个月使用线性规划指导下个月的产品组合决策。线性规划的数学模型考虑了这一决策的所有相关限制条件，包括生产产品所需的有限的可得数量。然后对模型求解，找出可行并且最大可能利润（largestpossibleprofit）的产品组合。•采用线性规划后，潘得罗索工业公司的成绩是显著的。改进的产品组合使公司的总利润增加了20%，线性规划得其他贡献包括更好的原材料利用，更好的资本投资，和更好的人员利用。第三章线性规划数据、模型与决策(第二版)航空业的成本控制•那时，联行在其11个航班订票处，有超过4，000名的机场销售代表和支持人员。在十个最大的机场大约有一千名顾客服务代表，有些时兼职的，每班2到8个小时不等，大部分是全职的，每班8现实或10小时，有许多个不同的上班时间。每个订票处都有一天24小时营业（通过电话订票。然而，每个地点提供所需水平服务的雇员数量在一天24小时种的变化很大，或许美国半个小时就会有很大的变化。•为了更有效率的满足服务要求，在每个地点为所有工作人员设计动作排成，是一个组合的梦魇。一旦一名雇员上了班，就会工作一个班次，只有就餐和每个两个小时的短暂的休息时间，给定24小时的一天中每半个小时各的服务所需的最小雇员数，在七天一周中，24小时一天中每个班次需要多少雇员并且合适上班呢？•幸运的是，线性规划能解决这些组合梦魇问题。据有形估计，建立在线性规划基础上的计算机规划系统每年为联合航空公司在直接薪酬和津贴成本上节省了600万美元，得到的其他好处包括改善客户服务以及降低雇员的工作负担。第三章线性规划数据、模型与决策(第二版)线性规划问题的数学模型•一家玻璃产品生产公司生产带有花样图案的彩色玻璃花瓶。每一个花瓶经过艺术玻璃吹风机从液态加工而成，然后进入储藏室冷却至室温，花瓶有大和小两种尺寸，但是生产过程几乎相当，而且使用同一种材料。不论尺寸，每一个花瓶都需要20分钟的艺术加工，每周艺术加工工作时间为40小时；大小花瓶每个个需彩色玻璃2OZ和1OZ。每周可用的玻璃为160OZ。另外，一个小花瓶占用2单位储存空间，大花瓶占用3个单位储存空间，一共有260个单位储存空间。大小花瓶的利润贡献率分别为12元/个和10元/个。问应该怎样安排生产，才能使利润值最大。第三章线性规划数据、模型与决策(第二版)线性规划问题的数学模型工序花瓶种类占用材料（OZ）艺术加工（小时）储存空间（一单位）利润值（元）大花瓶21/3312小花瓶11/3210每周可用能力16040260——B表示大花瓶每周生产的数量，S表示小花瓶每周生产的数量。第三章线性规划数据、模型与决策(第二版)约束条件•2B+S≤160•1/3B+1/3S≤40•3B+2S≤260•B≥0,S≥0目标函数：•maxz=12B+10S第三章线性规划数据、模型与决策(第二版)数学模型表述如下•目标函数maxz=12B+10S•材料约束2B+S≤160•时间约束1/3B+1/3S≤40•储存约束3B+2S≤260•非负约束B≥0,S≥0第三章线性规划数据、模型与决策(第二版)数学建模四个步骤：•决策变量•确定目标函数•确定约束条件•确定非负约束第三章线性规划数据、模型与决策(第二版)•实例分析：•A集团有1,000,000元的资金可供投资，该集团有五个可供选择的投资项目，其中各种资料如下：投资项目风险%红利%增长%信用度110510112681783187141041262245410710第三章线性规划数据、模型与决策(第二版)•A集团的目标为：投资风险最小，每年红利至少是80,000元，最低平均增长率14%，最低平均信用度为6，请用线性规划方法描述该问题。第三章线性规划数据、模型与决策(第二版)•决策变量为个项目的投资数额，设为xi(i=1,2,3,4,5)•目标函数：minz=(0.1x1+0.06x2+0.18x3+0.12x4+0.04x5)第三章线性规划数据、模型与决策(第二版)约束条件：•各项目投资总和为1,000,000元x1+x2+x3+x4+x5=1,000,000•所得红利最少为80,000元0.05x1+0.08x2+0.07x3+0.06x4+0.1x5≥80,000•增加额不低于140,000元1x1+0.17x2+0.14x3+0.22x4+0.7x5≥140,000•平均信用度不低于6(11x1+8x2+10x3+4x4+10x5)/5≥6•非负约束xi≥0(i=1,2,3,4,5)第三章线性规划数据、模型与决策(第二版)•实例分析：•某石油公司利用三种有生产两种混合原料。每种油的成本和每天的可用量如下表所示：油成本（元/升）可用量（升）A810,000B1015,000C1220,000燃料1A：最多占25%B：最少占30%C：最多占40%燃料2A：最少占20%B：最多占50%C：最少占30%第三章线性规划数据、模型与决策(第二版)•燃料1售价为30元/升，燃料2售价为35元/升，该公司有一向长期合同，每天供应两种原料，各10，000升。请建立该问题的数学规划模型。解题过程：•决策变量为加入到两种燃料种的各种油的量：•A1为原料1中加入A种油的升数。•A2为原料2中加入A种油的升数。•B1为燃料1中加入B种油的升数。•B2为燃料2中加入B种油的升数。•C1为燃料1中加入C种油的升数。•C2为燃料2中加入C种油的升数。第三章线性规划数据、模型与决策(第二版)•燃料1和燃料2的产量为：•燃料1：A1+B1+C1•燃料2：A2+B2+C2•各种油的使用量：•A种油=A1+A2•B种油=B1+B2•C种油=C1+C2•目标是取得最大化的利润，两种燃料的销售收入为：•30×(A1+B1+C1)+35×(A2+B2+C2)第三章线性规划数据、模型与决策(第二版)•而三种油的成本为：•8×(A1+A2)+10×(B1+B2)+12×(C1+C2)•利润是销售收入和成本之差，作为目标函数可以表示如下：•maxz=22×A1+27A2+20B1+25B2+18C1+23C2•三种可用的原料油的约束为：•A1+A2≤10,000•B1+B2≤15,000•C1+C2≤20,000第三章线性规划数据、模型与决策(第二版)•各种原料油所占比例的六个约束：•A1≤0.25×(A1+B1+C1)•B1≥0.3×(A1+B1+C1)•C1≤0.4×(A1+B1+C1)•A2≥0.2×(A2+B2+C2)•B2≤0.5×(A2+B2+C2)•C2≥0.3×(A2+B2+C2)•长期供货合同约束：•A1+B1+C1≥10,000•A2+B2+C2≥10,000•非负约束：•Ai，Bi，Ci≥0(i=1,2)第三章线性规划数据、模型与决策(第二版)第三章线性规划•3.1线性规划问题概述•3.2线性规划问题的图解法•3.3单纯形法•3.4对偶问题•3.5敏感性分析第三章线性规划数据、模型与决策(第二版)3.2线性规划问题的图解法•3.2.1图解法的过程介绍•3.2.2规划问题求解的几种可能结果•3.2.3图解法延伸第三章线性规划数据、模型与决策(第二版)3.2.1图解法的过程介绍•花瓶问题•目标函数maxz=12B+10S•材料约束2B+S≤160（1）•时间约束1/3B+1/3S≤40（2）•储存约束3B+2S≤260（3）•非负约束B≥0,S≥0第三章线性规划数据、模型与决策(第二版)直线把图分为两部分，直线上方的点都不符合约束条件，而直线上和直线下方的点都满足约束条件。第三章线性规划数据、模型与决策(第二版)最优解为：•B=20,S=100将B和S值代入目标函数中得：•Z=12×20+10×100=1240所以最大利润值是1240。第三章线性规划数据、模型与决策(第二版)图解法的步骤：•其中一个变量作为横坐标轴，另一个变量作为纵坐标轴，画出平面直角坐标系，并适当选取单位坐标长度，由于变量是非负的，因此，画出坐标系的第一象限即可。•出各约束条件在坐标轴上对应的直线，找出可行域（常用阴影区域标识）。•图标目标函数，z是一个待求的目标函数值。目标函数常用一组平行虚线表示，离坐标原点越远的虚线表示的目标函数值越大。•确定最优解。因为最优解是可行域中使目标函数值达到最优的点，当目标函数直线由原点开始向右上方移动时，z值开始增大，一直移到目标函数直线与可行域相切时为止，切点就是最优解的点。第三章线性规划数据、模型与决策(第二版)3.2.2规划问题求解的几种可能结果•无穷多最优解•无界解•无解或者无可行解第三章线性规划数据、模型与决策(第二版)3.2.3图解法延伸•图解法的解体方法和几何判断对于求解一般的线性规划问题有很大启发：•1、性规划问题的解的情况有以下几种：唯一最优解；无穷多最优解；无界解；无可行解。•2、线性规划问题有解，那么可行域是凸集。•3、规划问题优解存在，那么唯一最优解一定是可行域凸集的某个顶点；无穷最优解一定是可行域的某个边或某个面。•4、规划问题的一般解体思路：先找出凸集的任一顶点，计算该点处目标函数值，与周围相邻顶点处的目标函数值相比较，如果该点值最大，那么该点就是最优解或者最优解之一；如果不是，那么就对目标函数值比该点大的另一点重复此过程，直到找出最优解。第三章线性规划数据、模型与决策(第二版)•实例分析：•某工厂生产A,B两种产品，分别经过三道工序，已知建立的模型如下所示，可行域为凸多边形OACDB,试以图解法求解最优生产方案。•目标函数maxz=20A+30B•工序一约束2A+B≤40•工序二约束A+2B≤40•工序三约束A+B≤25•非负约束A≥0,B≥0第三章线性规划数据、模型与决策(第二版)第三章线性规划数据、模型与决策(第二版)•A+2B=40工序二约束•A+B=25工序三约束•联立以上方程，可以求得最优解•A=10,B=15•代入目标函数，求得最大目标函数值为20*10+30*15=650。第三章线性规划数据、模型与决策(第二版)第三章线性规划•3.1线性规划问题概述•3.2线性规划问题的图解法•3.3单纯形法•3.4对偶问题•3.5敏感性分析第三章线性规划数据、模型与决策(第二版)3.3单纯形法•3.3.1线性规划问题的标准形式•3.3.2