《线性规划(运筹学.ppt》由会员分享，可在线阅读，更多相关《线性规划(运筹学.ppt（45页珍藏版）》请在三一办公上搜索。
1、*,第 二讲 线性规划基本概念、解法和应用,李勇建 教授,*,主要内容,举例 线性规划模型线性规划在管理中的应用建模 线性规划解法,*,拼装玩具生产,自己动手,你怎么去分析呢？,*,为了最小化成本或最大化利润的目的需要对一些稀缺资源进行配置,自己动手,最大化：($20)*桌子数量+（$15）*椅子数量满足以下条件：大块：2*桌子数量+椅子数量6小块：2*桌子数量+2*椅子数量8桌子数量0；椅子数量0,Max 20table+15chairs.t.2table+chair6 2table+2chair8 table0；chair0,你的答案是什么？,*,1 生产计划问题,某工厂计划生产两种产品，
2、生产单位产品所需要的设备台时、原料、利润及资源的限制如下：,*,模 型,假设生产产品I、II的数量分别为（称为决策变量）那么利润最大化的目标为：,但是设备和原料有限制设备：原料A：原料B：,*,模型的组成部分,决策变量目标函数约束,*,例2-1（教材P12）,*,线性规划模型的构成,分析并表述方案决策变量方案的环境限制约束条件方案的优劣评价指标目标计算最优的方案最优解,*,线性规划的基本特点运筹学中应用最广泛的方法之一运筹学的最基本的方法之一。网络分析、整数规划、多目标规划等都是以线性规划为基础的解决稀缺资源最优分配的有效方法，使付出的费用最小或获得的收益最大研究对象有一定的人力、财力、资源条
3、件下，如何合理安排使用，效益最高某项任务确定后，如何安排人、财、物，使之花费最省,*,典型问题,产品生产计划：合理利用人力、物力、财力等，使获利最大合理利用线材问题：如何下料，使得使用材料最少配料问题：在原料供应量的限制下如何获取最大利润投资问题：从投资项目中选取方案，使投资回报最大劳动力安排：用最少的劳动力来满足工作的需要运输问题：如何制定调运方案，使总运费最小。,*,线性规划模型的假设,线性性：目标函数和约束条件都是决策变量的线性关系可加性：强调目标函数和约束条件都是各个决策变量对其贡献之和连续性：表示决策变量的取值是连续的确定性：所有的系数都是确定的常数,*,为什么要使用线性规划,线性规
4、划很容易而有效率地被求解如果存在最优解，则肯定能够找到功能强大的敏感性分析（sensitivity analysis）许多实际问题本质上是线性的,*,线性规划的一般数学描述,线性规划要确定决策变量 x1,x2,xn 使得,已知参数 c1,cn;a11,amn;b1,bm.,目标函数,条件约束,非负性约束,*,以上模型的简写形式为,矩阵表示,*,线性规划问题建模步骤,需要做哪些决策？决策变量是什么 问题的目标是什么？写出目标函数 资源和需求之间的情况如何？确定约束条件具体过程见例2-2，书P14,线性规划在管理中的应用,一、人力资源分配的问题二、生产计划的问题三、套裁下料问题四、配料问题五、投资
5、问题,*,一、人力资源分配的问题 例1某昼夜服务的公交线路每天各时间段内所需司机和乘务人员数如下：设司机和乘务人员分别在各时间段一开始时上班，并连续工作八小时，问该公交线路怎样安排司机和乘务人员，既能满足工作需要，又配备最少司机和乘务人员?,线性规划在管理中的应用(1),*,线性规划在管理中的应用(1),xi 表示第i 班次时开始上班的司机和乘务人员数，i=1，2，6Minimize(Min)x1+x2+x3+x4+x5+x6 x1+x6 60 x1+x2 70 x2+x3 60 x3+x4 50 x4+x5 20 x5+x6 30 x1,x2,x3,x4,x5,x6 0,决策变量：目标函数：
6、约束条件(s.t)班次1班次2班次3班次4班次5班次6非负性,*,线性规划在管理中的应用(2),一、人力资源分配的问题（2）例2福安商场是个中型的百货商场，它对售货员的需求经过统计分析如下表：为了保证售货人员充分休息，售货人员每周工作 5天，休息两天，并要求休息的两天是连续的。问应该如何安排售货人员的作息，既满足工作需要，又使配备的售货人员的人数最少？,*,线性规划在管理中的应用(2),xi(i=1-7)表示星期一至日开始休息的人数Min x1+x2+x3+x4+x5+x6+x7 x1+x2+x3+x4+x5 28x2+x3+x4+x5+x6 15x3+x4+x5+x6+x7 24x4+x5+
7、x6+x7+x1 25x5+x6+x7+x1+x2 19x6+x7+x1+x2+x3 31x7+x1+x2+x3+x4 28x1,x2,x3,x4,x5,x6,x7 0,决策变量：目标函数：约束条件(s.t)星期日星期一星期二星期三星期四星期五星期六非负性,*,二、生产计划的问题 例3(书P24例2-3)某家具生产企业需要制定下一季度的生产计划。该企业主要生产四种类型的产品：沙发，双人沙发，躺式椅子和矮茶几。下一季度的生产预算为180000美元。可用的机器时间为800小时，可用的人力为1200小时。另外，企业管理人员还提出了如下的要求：沙发的成本占总成本的比例不低于40%；躺式椅子的成本占总成
8、本的比例不低于25%；双人沙发的产量不低于30单位。要求计算下一季度的最优生产计划。,线性规划在管理中的应用(3),*,决策变量：xi(i=1,2,3,4)分别表示家具企业生产沙发、双人沙发、躺式椅子、矮茶几的产量目标函数：max 约束：成本预算约束：预测销量约束：机器时间约束：人力时间约束：,线性规划在管理中的应用(3),*,管理层的三个约束：要求一：沙发的成本占总成本的比例不低于40%整列可得：要求二：躺式椅子的成本占总成本的比例不低于25%要求三：双人沙发的产量不低于30单位，则完整的线性规划模型：,线性规划在管理中的应用(3),*,二、生产计划的问题 例4明兴公司生产甲、乙、丙三种产品
9、，都需要经过铸造、机加工和装配三个车间。甲、乙两种产品的铸件可以外包协作，亦可以自行生产，但产品丙必须本厂铸造才能保证质量。数据如下表。问：公司为了获得最大利润，甲、乙、丙三种产品各生产多少件？甲、乙两种产品的铸造中，由本公司铸造和由外包协作各应多少件？,线性规划在管理中的应用(4),*,设 x1,x2,x3 分别为三道工序都由本公司加工的甲、乙、丙三种产品的 件数，x4,x5 分别为由外协铸造再由本公司机加工和装配的甲、乙两种产品的件数。求 xi 对应的利润：利润=售价-各成本之和 可得到 xi（i=1,2,3,4,5）的利润分别为 15、10、7、13、9 元。Max 15x1+10 x2
10、+7x3+13x4+9x5 s.t.5x1+10 x2+7x3 8000 6x1+4x2+8x3+6x4+4x5 12000 3x1+2x2+2x3+3x4+2x5 10000 x1,x2,x3,x4,x5 0,决策变量：,目标函数：,约束条件：,线性规划在管理中的应用(4),*,二、生产计划的问题 例5永久机械厂生产、三种产品，均要经过A、B两道工序加工。设有两种规格的设备A1、A2能完成 A 工序；有三种规格的设备B1、B2、B3能完成 B 工序。可在A、B的任何规格的设备上加工；可在任意规格的A设备上加工，但对B工序，只能在B1设备上加工；只能在A2与B2设备上加工；数据如下表。问：为使
11、该厂获得最大利润，应如何制定产品加工方案？,线性规划在管理中的应用(5),*,设 xijk 表示第 i 种产品，在第 j 种工序上的第 k 种设备上加工的数量。产品1数量：x111+x112产品2数量：x211+x212产品3数量：x312 利润=（销售单价-原料单价）*产品件数之和-（每台时的设备费用*设备实际使用的总台时数）之和。因此，目标函数：Max(1.25-0.25)(x111+x112)+(2.00-0.35)(x211+x212)+(2.80-0.50)x312-300/6000(5x111+10 x211)-321/10000(7x112+9x212+12x312)-50/40
12、00(6x121+8x221)-783/7000(4x122+11x322)-200/4000*7x123即 Max 0.75x111+0.7753x112+1.15x211+1.3611x212+1.9148x312-0.375x121-0.5x221-0.4475x122-1.2304x322-0.35x123,决策变量：,目标函数：,线性规划在管理中的应用(5),*,5x111+10 x211 6000 7x112+9x212+12x312 10000 6x121+8x221 4000 4x122+11x322 7000 7x123 4000 x111+x112-x121-x122-x1
13、23=0 x211+x212-x221=0 x312-x322=0 xijk 0,i=1,2,3;j=1,2;k=1,2,3,约束条件：,设备 A1 设备 A2 设备 B1 设备 B2 设备 B3 产品在A、B工序加工的数量相等产品在A、B工序加工的数量相等产品在A、B工序加工的数量相等非负性约束,线性规划在管理中的应用(5),*,三、套裁下料问题 例6某工厂要做100套钢架，每套用长为2.9 m,2.1 m,1.5 m的圆钢各一根。已知原料每根长7.4 m，问：应如何下料，可使所用原料最省？解：写出所有可能的下料方案（从剪裁的一种思路考虑）整理为剩余料头从小到大的方案顺序,线性规划在管理中的
14、应用(6),*,考虑下列 5 种下料方案,设x1,x2,x3,x4,x5分别为上面前 5 种方案下料的原材料根数。这样我们建立如下的数学模型。目标函数：Min x1+x2+x3+x4+x5 约束条件：s.t.x1+2x2+x4 100 2x3+2x4+x5 100 3x1+x2+2x3+3x5 100 x1,x2,x3,x4,x5 0,决策变量：,线性规划在管理中的应用(6),*,四、配料问题 例7某工厂要用三种原料1、2、3混合调配出三种不同规格的产品甲、乙、丙，数据如下表。问：该厂应如何安排生产，使利润收入为最大？,线性规划在管理中的应用(7),*,设 xij 表示第 i 种（甲、乙、丙）
15、产品中原料 j 的含量。甲的重量：x11+x12+x13；乙的重量：x21+x22+x23；丙的重量：x31+x32+x33；原料1的需求量：x11+x21+x31；原料2的需求量：x12+x22+x32；原料3的需求量：x13+x23+x33；目标函数：利润最大 利润=收入-原料支出 Max z=50(x11+x12+x13)+35(x21+x22+x23)+25(x31+x32+x33)-65(x11+x21+x31)-25(x12+x22+x32)-35(x13+x23+x33)即 Max z=-15x11+25x12+15x13-30 x21+10 x22-40 x31-10 x33,
16、决策变量:,线性规划在管理中的应用(7),*,约束条件：规格要求 4 个：甲：原材料1不少于50%：x11-x12-x13 0 甲：原材料2不超过25%：-0.25x11+0.75x12-0.25x130 乙：原材料1不少于25%：0.75x21-0.25x22-0.25x23 0乙：原材料2不超过50%：-0.5 x21+0.5 x22-0.5 x23 0供应量限制 3 个：供应量限制：x11+x21+x31 100供应量限制：x12+x22+x32 100供应量限制：x13+x23+x33 60非负性约束：xij 0,i=1,2,3;j=1,2,3,线性规划在管理中的应用(7),*,五、投
17、资问题 例8某部门现有资金200万元，今后五年内考虑给以下的项目投资。已知：项目A：从第一年到第五年每年年初都可投资，当年末能收回本利110%；项目B：从第一年到第四年每年年初都可投资，次年末能收回本利125%，但规定每年最大投资额不能超过30万元；项目C：需在第三年年初投资，第五年末能收回本利140%，但规定最大投资额不能超过80万元；项目D：需在第二年年初投资，第五年末能收回本利155%，但规定最大投资额不能超过100万元；据测定每万元每次投资的风险指数如下表：问：a）应如何确定这些项目的每年投资额，使得第五年年末拥有资金的本利金额为最大？b）应如何确定这些项目的每年投资额，使得第五年年末
18、拥有资金的本利在330万元的基础上使得其投资总的风险系数为最小？,线性规划在管理中的应用(8),*,1）确定决策变量：连续投资问题 设 xij(i=1-5，j=1、2、3、4)表示第 i 年初投资于A(j=1)、B(j=2)、C(j=3)、D(j=4)项目的金额。这样我们建立如下的决策变量：年份：1 2 3 4 5 A：5年内都可投资 x11 x21 x31 x41 x51 B：前4年都可投资 x12 x22 x32 x42 C：第3年初投资 x33 D：第2年初投资 x24 年初资金,200,1.1x11,1.1x21+1.25x12,1.1x31+1.25x22,1.1x41+1.25x3
19、2,项目A：当年末能收回本利110%,项目B：次年末能收回本利125%,项目C：第五年末能收回本利140%,项目D：第五年末能收回本利155%,问题a：,线性规划在管理中的应用(8),*,2）约束条件：第一年：x11+x12=200；第二年：x21+x22+x24=1.1x11；第三年：x31+x32+x33=1.1x21+1.25x12；第四年：x41+x42=1.1x31+1.25x22；第五年：x51=1.1x41+1.25x32；B、C、D的投资限制：xi2 30(i=1、2、3、4)，x33 80，x24 100,1）确定决策变量：连续投资问题 设 xij(i=1-5，j=1、2、3
20、、4)表示第 i 年初投资于A(j=1)、B(j=2)、C(j=3)、D(j=4)项目的金额。这样我们建立如下的决策变量：年份：1 2 3 4 5 A：5年内都可投资 x11 x21 x31 x41 x51 B：前4年都可投资 x12 x22 x32 x42 C：第3年初投资 x33 D：第2年初投资 x24 年初资金,200,1.1x11,1.1x21+1.25x12,1.1x31+1.25x22,1.1x41+1.25x32,线性规划在管理中的应用(8),*,3）目标函数（第5年末的资金）Max z=1.1x51+1.25x42+1.4x33+1.55x24 问题a的线性规划模型：Max
21、z=1.1x51+1.25x42+1.4x33+1.55x24 s.t.x11+x12=200 x21+x22+x24-1.1x11=0;x31+x32+x33-1.1x21-1.25x12=0；x41+x42-1.1x31-1.25x22=0；x51-1.1x41-1.25x32=0；xi2 30(I=1、2、3、4)，x33 80，x24 100 xij 0(i=1、2、3、4、5；j=1、2、3、4）,线性规划在管理中的应用(8),*,问题b：应如何确定这些项目的每年投资额，使得第五年年末拥有资金的本利在330万元的基础上使得其投资总的风险系数为最小？b)Min f=(x11+x21+x
22、31+x41+x51)+3(x12+x22+x32+x42)+4x33+5.5x24 s.t.x11+x12 200 x21+x22+x24-1.1x11 0;x31+x32+x33-1.1x21-1.25x12 0；x41+x42-1.1x31-1.25x22 0；x51-1.1x41-1.25x32 0；xi2 30(I=1、2、3、4)，x33 80，x24 100 1.1x51+1.25x42+1.4x33+1.55x24 330 xij 0(i=1、2、3、4、5；j=1、2、3、4）,线性规划在管理中的应用(8),线性规划在ERP中的的适用层次,计划链的层次,产值计划 或 利润计划
23、 绝对数量 或 增长幅度 期限:年度 单位:万元,大类产品销售收入或台套 产品品种和数量如何确定 期限:年度 单位:万台,具体产品在具体 时段的出产计划 合同订单和预测 转换为生产任务,将产品出产计划转换成物料需求表,大类产品年度生产计划 确定产品的品种和数量 期限:年度 单位:万台,*,线性规划解法,*,线性规划模型：,设x1、x2分别为生产产品1和2的数量，则Max z=3x1+5x2s.t.x1 4 2x212 3x1+2x218 xj0,j=1,2,*,图解法,图1.1 生产计划问题,想一想此最优解唯一吗?何时无有限最优解(有无界解)?,何时有无穷多最优解?无可行解?,x1,x2,线性规划解的特性,由线性不等式组成的可行域是凸多边形(凸多边形是凸集)凸集定义：集合内部任意两点连线上的点都属于这个集合,可行域有有限个顶点。目标函数最优值一定在可行域的边界达到，而不可能在其区域的内部。,*,线性规划的软件求解,（1）用Lindo或Lingo软件求解（2）用Excel求解：家具生产的例子（3）其他软件：Mathematics,Matlab,LINDO:Max 3x1+5x2Stx142x2123x1+2x218end,LINGO:Max=3*x1+5*x2;x1=4;2*x2=12;3*x1+2*x2=18;,
