运筹学课件——第2讲线性规划模型.ppt

第1章 线性规划,本章要求： 1.掌握并熟练应用线性规划的模型处理实际问题 2.掌握线性规划的图解法 3.掌握软件求解线性规划 4.了解线性规划对偶问题的基本性质 5.理解有关灵敏度分析内容,关于“线性规划”,英文名：Linear Programming,缩写为LP 自1947年丹齐格提出求解一般线性规划的有效方法单纯形法后，得到迅速发展，成为运筹学应用最广泛的分支。 特点： 1.应用广泛 2.模型简单易建 3.求解方法成熟,线性规划是运筹学的重要组成部分，也是最基础的部分。自1947年丹齐格（G.B.Dantzig）提出了求解线性规划的一般方法单纯形法以来，线性规划在理论上趋向成熟，日臻完善，尤其是计算机处理问题的规模及运算速度提高后，线性规划的应用领域更加广泛。无论工业、农业、商业、交通运输、军事、经济计划和管理决策等领域都有应用。大到一个国家、一个地区，小到一个企业、一个车间、一个班组都有运用线性规划后提高经济效益的例子。,简介,问题的提出,在生产管理和经营活动中，组织常常必须对如何向不同的活动分配资源的问题做出决策，以便最好地达成组织的目标。,这样的问题通常有两类，一类是如何合理地使用有限的劳动力、设备、资金等资源，以最大化效益；另一类是为了达到一定的目标，应如何组织生产，或合理安排工艺流程，或调整产品的成分以使资源消耗最少。,向不同的活动分配的资源可以是资金、不同的人员以及机器、设备。而需要这些资源的活动也可以是各类生产活动，例如产品生产、营销、在不同媒体做广告、金融活动、进行资金投资或其他一些活动。,由于所有活动都要求一定资源作支撑，而资源却是有限的，这必然导致活动间的冲突与矛盾。这就需要管理者利用一些科学的方法进行协调，以使资源达到最大的效用。,显然，上述活动所引起的问题是一类有约束的最优化问题（Constrained Optimization）。,线性规划正是解决有约束的最优化问题的一种常用的方法，其涉及的主要概念包括：,目标（Objective）:所要达到的最优结果（最 大或最小）；,约束条件（Constraints）:对所能产生结果的 限制。,例1,1.1 基本问题,1.1 .1 基本模型的建立,例2,例3：生产计划问题,某厂计划安排生产A，B两种产品，已知生产单位产品的利润与所需的劳动力，设备台时及原材料的消耗如图所示。问应该如何安排生产获利最大？,设:安排生产A产品x1个单位，B产品x2个单位.,例4：饮料配制计划,大众酒吧自行配制生产甲，乙两种饮料，管理层决定下月总产量至少达到350升。甲饮料每升的制造成本为2元，制造时间需2小时，乙饮料每升的制造成本为3元，制造时间需1小时，下月总生产时间为600小时。此外，下月有一位客户已预定甲饮料125升。试为管理层制定满足客户要求且制作成本最小的生产计划。 线性规划模型？,LP模型：,设:配制生产甲饮料x1升,乙饮料x2升.,某集团有1000000元资金供投资，该集团有5个可供选择的投资项目，其中各种资料如下表：,该集团的目标为：投资风险最小，每年红利至少80000元，最低平均增长率14%，最低平均信用度6，请用线性规划方法描述该问题。,例5 投资问题,分析建模：决策变量为各项目的投资数额，设为 xi（i =1,2,3,4,5）。,目标函数：,投资额约束：,红利约束：,增长额约束：,平均信用度约束：,非负约束：,LP模型：,例6：运输问题,A1，A2两个煤矿给B1，B2，B3三个城市供煤，各煤矿产量和各城市需求量以及各地之间的单位运价如下表所示： 问应该如何调运，才能既满足城市需求，又使总运费最小？线性规划模型？,运价（元/吨）,设xij表示产地Ai运往销地Bj煤的数量(i=1,2;j=1,2,3).,运输表,产品组合问题的推广,线性规划的矩阵形式,对于一般线性规划模型，目标函数可以求最大，也可以求最小；约束条件可以是“”，也可以是“”或“=”型。因此，一般线性规划模型可表示为,线性规划模型的一般形式,线性规划模型的标准形式,线性规划化的标准化,(1) 目标函数,(2) 约束条件,当要求目标函数极小化时，将目标函数价值系数乘以“ -1”，按最大化求解。,不等式,+ 松弛变量,不等式,- 剩余变量,=,=,max z = 3x1+5x2,写出例1.1的标准形式,标准形式,max z = 3x1+5x2,s.t.,s.t.,(3) 变量,解,例 将下列线性规划化成标准型,得到,例、将下列线性规划模型化为标准型,例、将下列线性规划模型化为标准型,令x2=-x4,x3=x5-x6,s.t.,可行解： 满足约束条件(b)、(c)的解X=（x1，xn)T，称为线性规划问题的可行解。全部可行解的集合称为可行域。 最优解：使目标函数(a)达到最大值的可行解称为最优解。,（a）,（b）,（c）,1.1.2 线性规划问题的基本概念,基：设Amn (nm)为约束方程组(b)的系数矩阵，其秩为m。Bmm 是矩阵A 中的一个mm 阶的满秩子矩阵(|B|不等于0), ，称B 是线性规划问题的一个基。不失一般性，设,B 中的每一个列向量Pj（j=1,2,m）称为基向量，与基向量Pj 对应的变量xj 称为基变量。除基变量以外的其它变量称为非基变量。 基B的m个列向量是线性无关的。,标准形式,max z = 3x1+5x2,是一个基，对应的变量x3,x4,x5是基变量，x1,x2是非,基变量。,基解：假设系数矩阵A 的秩为m，不妨设A 中前m 个列向量线性独立，方程可以写为,令所有非基变量xm+1=xn=0， 由|B|0，根据克莱姆规则，可得m个基变量的唯一解 xb=(x1,x2,xm) 加上所有取值为0 的非基变量，得： x=(x1,x2,xm,0,0),称x 为线性规划问题的基解。,令x1=x2=0，解得x3=4,x4=12,x5=18,则x=(0,0,4,12,18)T是一个基解。,max z = 3x1+5x2,基可行解： 满足变量非负约束条件(c)的基解称为基可行解。,可行基：对应于基可行解的基称为可行基。,可行解,基 解,基可行解,令x1=x2=0，解得x3=4,x4=12,x5=18,则x=(0,0,4,12,18)T是一个基解。 由于该基解中所有变量取值为非负，故是基可行解，对应的基,是可行基。,可行基往往不只一个。,如（P1,P4,P5）也是可行基。,最多可能有多少个?,例：求下述线性规划的基可行解,基可行解,解,1.2 几何思路,1.2.1 图解法的介绍,1. 确定可行解集合R，即可行域的图形. 注：满足所有约束条件的解称为线性规划问题的可行解。 2. 作出目标函数等值线. 3. 确定最优解，记为x*. 注：图解法仅适应与求解两个决策变量的LP问题,max z = 3x1+5x2,当目标函数的等值线沿着梯度方向移动到刚离开可行域时，即可得到目标函数有最大值的解。,max z = 3x1+2x2,max z = 3x1+5x2,图解法求解结果 有可能出现以下各种情形： （1 ）有最优解并且唯一； （2）有最优解但不唯一，有无穷多个； （3 ）因为可行域无界而不存在最优解； （4）可行域为空集，没有可行解。,用图解法求例3：生产计划问题,用图解法求例4:饮料配制计划,设:配制生产甲饮料x1升,乙饮料x2升.,1.2.2解的几何意义,1、基本概念,(1) 线段,(2) 凸集,凸集没有凹入部分，其内部没有空洞。,(3) 凸组合,设,=1,(4)顶点,即,作业,复习：LP的图解方法与标准型。 预习： 单纯形法与对偶理论。 作业：习题 1.1；习题 1.2,引例：LP的应用,例1：大通曼哈顿银行员工工作安排 例2：航空公司机组人员排程,利用LP安排的结果,例2：航空业的成本控制,航空业在1983年和1984年发生了史无前例的行业竞争，尽管如此，联合航空公司还是开通了48个新机场的服务，并且取得了很大的增长。1984年，它是唯一的一家在美国全部50个州开通服务的公司，1984年的收入比1983年增长了6个百分点，达到62亿美元，而同时成本的增长少于2%，因此营运利润提高，达到了5.64亿美元。,在航空业，成本控制是关键。作为公司管理扩展的一部分，美国航空公司的高层管理部门实施了一个成本控制项目，目标是根据消费者的需求进行工作排程，以减少成本并且改进航空订票处和机场工作人员的利用率。,美国航空公司机组人员线性规划排程介绍,建立线性规划模型,（1）确定决策变量：通常为非负，决策变量的一组 取值称为线性规划的一组解，表示一个方案。 （2）确定目标函数z：它是决策变量的线性函数，我们要使它取最大值或最小值。 （3）确定约束条件：可用决策变量的一组线性等式或不等式表示。,实例：潘得罗索公司的产品组合,潘得罗索工业公司是一家墨西哥公司，截止1998年，公司产销量占该国的四分之一。,与其他胶合板生产厂商一样，潘得罗索工业公司的许多产品因厚度和所用木材的质量而有所不同。由于产品在一个竞争的环境中进行销售，产品的价格由市场决定，所以产品的价格每月都有很大的变化。结果导致每项产品对公司整体利润的贡献也有很大的变化。这样，在某个月一个产品可能比另一个产品赚取更大的利润，而在下一个月的情况则可能正好相反。,所以，每个月管理层面临的关键问题是选择产品组合（Product Mix），以尽可能多地获取利润。,这一选择是很复杂的，因为它需要考虑当前生产产品必须的各种资源的可得数量。六项最重要的资源为：四种类型的原木（根据原木的质量区分）；生产胶合板的两项关键作业的生产能力（磨压作业和抛光作业）。,从1980年开始，潘得罗索工业公司管理部门每个月使用线性规划决定下个月的产品组合决策。线性规划的数学模型考虑了这一决策的所有相关限制条件，包括生产产品所需的有限的可得资源，然后求解模型，找出可行并且最大的可能利润产品组合。,线性规划还给潘得罗索工业公司的管理层提供了其它一些有价值的生产信息，包括当前生产中某一特定资源的采购决策及其对利润的影响。例如，假设公司为生产某一特别赚钱的产品所需的某类原木只有少量供应，线性规划将表明如果赶紧购买该类原木会对产品组合以及利润产生多大的影响。,采用线性规划后，潘得罗索工业公司的成绩是显著的。产品组合调整使公司总利润增加了20%，线性规划的其他贡献包括更好的原材料利用、更好的资本投资和更好的人员利用。,LP应用效果,建立线性规划问题的数学模型,例1：一家玻璃制品公司生产带有花样图案的彩色玻璃花瓶。每一个花瓶经过艺术玻璃吹风机从液态加工而成，然后进入储藏室冷却至室温。花瓶有大、小两种尺寸，但生产过程几乎相当，而且使用同一种材料。不论尺寸，每一个花瓶都需要20分钟的艺术加工，每周艺术加工工作时间为40小时；大、小花瓶每个需彩色玻璃2 OZ和1 OZ，每周可用的玻璃为160 OZ；另外，一个小花瓶占用2单位储存空间，大花瓶占用3个单位储存空间，一共有260个储存空间。大、小花瓶的利润贡献率分别为12元/个和10元/个。问应该怎样安排生产，利润值最大。,分析建模：用B表示每周生产大花瓶的数量，S表示每周生产小花瓶的数量，则决策变量为B、S。,目标函数：,材料约束：,时间约束：,储存约束：,非负约束：,LP模型：,由上可知，LP数学建模过程主要有三个步骤：,确定决策变量；,确定目标函数；,确定约束条件（包括非负约束）。,例2：某寻呼台每天需要话务员人数、值班时间以及工资情况如下表所示。每班话务员在轮班开始时报到，并连续工作9小时。问如何安排，使得既满足需求又使总支付工资最低，试建立数学模型。,分析建模：决策变量为从第 i 班开始工作的人数，设为 xi（i =1,2,3,4,5,6,7,8）。,目标函数：,第班人数约束：,第班人数约束：,第班人数约束：,第班人数约束：,第班人数约束：,第班人数约束：,第班人数约束：,第班人数约束：,非负约束：,LP模型：,例4：某石油公司利用三种油料生产两种混合原料。每种油的成本和每天的可用量如表所示：,两种混合原料中各种油料所占比例如下表所示：,原料售价为30元/L，原料售价为35元/L，该公司有一项长期合同，每天供应两种原料各10000L。试建立该问题的数学规划模型。,分析建模：决策变量为加入到原料中的各种油料的量：,A 1为加入原料中的油料 A 的升数；,A 2为加入原料中的油料 A 的升数；,B 1为加入原料中的油料 B 的升数；,B 2为加入原料中的油料