数学建模公选课第二讲.ppt

数学建模公选课,基础教研室,第二讲:线性规划模型,引例：某商业规划处在商场内要装修I、II两种经营不同商品的铺位各若干个，已知装修一个铺位所需的人数及A、B两种装修材料的消耗，如下表所示。,该商场每个铺位I可获利 2万 元，每个铺位II可获利 3 万元，问应如何安排装修计划使商场获利最大？,这问题可以用以下的数学模型来描述：设x1,x2分别表示在计划期内装修I、II的数量。因为可调动的人数为8人，这是一个限制装修数量的条件，所以在确定I、II的数量时，要考虑不超过可调动人数，即可用不等式表示为：x 1+2x 2 8.同理，因装修材料A、B的限量，可以得到以下不等式：4x116，4x 2 12.该商场的目标是在不超过所有资源限量的条件下，如何确定数量x1、x2以得到最大的利润。若用 z 表示利润，这时z=2 x 1+3 x 2。,综上所述，该计划问题可用数学模型表示为：目标函数：Max z=2x 1+3x 2 满足约束条件：,图解法 图解法简单直观，有助于了解线性规划问题求解的基本原理。现进行图解。在以x1、x2为坐标轴的直角坐标系中，非负条件x1,x2 0 是指第一象限（及x轴正半轴、y轴正半轴）。每一个约束条件都表示一个半平面。若约束条件 x 1+2x 2 8 是代表以直线x 1+2x 2=8为边界的左下方的半平面，同时满足x 1+2x 2 8，4 x 1 16，4 x 2 12和x 1，x 2 0约束的点，必然在由这三个半平面围成的区域内。所有约束条件为半平面围成的区域见右下图阴影部分。阴影区域中的每一个点（包括边界点）都这个线性规划问题的解。,再分析目标函数,在这坐标平面上，它表示以 z为参数、为斜率的一族平行直线：,x 2=x1+z 位于同一直线上的点，具有相同的目标函数值，因而称它为“等值线”。当z值由小变大时，直线x 2=x1+z 沿其法线方向（法线方向是指与直线垂直的方向）向上方移动。当移动到Q 2点时，使z值在可行域（阴影部分）边界上实现最大化，这就得到了最优解Q2，Q2点的坐标为（4，2）。于是算得Max=14。这说明该商场的最优装修计划方案是：装修铺位I 4间，装修铺位II 2间，可得到最大利润为14万元。,线性规划模型形式,线性规划模型的矩阵式目标函数：max，min约束条件：,=,变量符号：0线性规划的标准形式目标函数：min约束条件：=变量符号：0,线性规划的简写式,线性规划的向量式,其中：C=(c1,c2,cn)-价值向量X=(x1,x2,xn)T-决策向量Pj=(a1j.a2j,amj)T-系数向量B=(b1,b2,bn)T-资源向量,线性规划问题的一般形式,Max(min)Z=C1X1+C2X2+CnXn,基本概念1。可行解(可行点):满足所有约束条件的向量。2。可行域（可行集）：所有可行解构成的集合。3。最优解：满足所有约束条件和目标函数的向量。4。最优值：最优解的目标函数值。,建模分析,第一步：决策变量。决策变量选取得当，不仅能顺利地建立模型而且能方便地求解，否则很可能事倍功半。第二步：约束条件。并用决策变量的线性方程或线性不等式来表示。当限制条件多，背景比较复杂时，可以采用图示或表格形式列出所有的已知数据和信息，以避免“遗漏”或“重复”所造成的错误。,第三步：目标函数。确定对函数是取极大还是取极小的要求。决策变量的非负要求可以根据问题的实际意义加以确定。讨论：这三步的顺序可以颠倒吗?为什么？,几类典型的LP问题,有大量的实际问题可以归结为线性规划问题来研究，这些问题背景不同，表现各异，但数学模型却有着完全相同的形式。尽可能多地掌握一些典型的模型不仅有助于深刻理解线性规划本身的理论和方法，而且有利于灵活地处理千差万别的实际问题，提高解决实际问题的能力。,例1：人力资源分配问题,公交线路需要24小时值班，每次值班8小时。不同时段需要的人数不等。,问题：如何安排，所需人数最少？,设xi为第i班次开始上班的人数目标函数：min Z=x1+x2+x3+x4+x5+x6约束条件：x1+x2 70 x2+x3 60 x3+x4 50 x4+x5 20 x5+x6 30 x1+x6 60非负性约束：xj 0,j=1,2,6,例2：生产计划问题：某厂生产两种产品，需要三种资源，已知各产品的利润、各资源的限量和各产品的资源消耗系数如下表,问题：如何安排生产计划，使得获利最多？,步骤：1.确定决策变量：设生产A产品x1kg,B产品x2kg2.确定目标函数：maxZ=70 x1+120 x23.确定约束条件：人力约束 9x1+4x2360 设备约束 4x1+5x2 200 原材料约束 3x1+10 x2 300 非负性约束 x10,x20,设生产A产品x1kg,B产品x2kg,则得线性规划模型:,例题3：任务分配问题,某车间有甲、乙两台机床，可用于加工三种工件。假定这两台车床的可用台时数分别为800和900，三种工件的数量分别为400、600和500，且已知用三种不同车床加工单位数量不同工件所需的台时数和加工费用如下表。问怎样分配车床的加工任务，才能既满足加工工件的要求，又使加工费用最低？,设在甲车床上加工工件1、2、3的数量分别为x1、x2、x3，在乙车床上加工工件1、2、3的数量分别为x4、x5、x6。可建立以下线性规划模型：,应用总结,市场营销(广告预算和媒介选择，竞争性定价，新产品开发，制定销售计划)生产计划制定(合理下料，配料,“生产计划、库存、劳力综合”)库存管理(合理物资库存量，停车场大小，设备容量)运输问题财政、会计(预算，贷款，成本分析，投资，证券管理)人事(人员分配，人才评价，工资和奖金的确定)设备管理(维修计划，设备更新)城市管理(供水，污水管理，服务系统设计、运用),要解决的问题的目标可以用数值指标反映对于要实现的目标有多种方案可选择有影响决策的若干约束条件,用MATLAB优化工具箱解线性规划,命令：x=linprog（c，A，b）,2、模型：min z=cX,命令：x=linprog（c，A，b，Aeq,beq）,注意：若没有不等式：存在，则令A=，b=.,命令：1 x=linprog（c，A，b，Aeq,beq,VLB，VUB）2 x=linprog（c，A，b，Aeq,beq,VLB，VUB,X0）,注意：1 若没有等式约束:,则令Aeq=,beq=.2其中X0表示初始点,4、命令：x,fval=linprog()返回最优解及处的目标函数值fval.,引例解：编程序如下：f=-2-3;A=1 2;4 0;0 4;b=8;16;12;Aeq=;beq=;x f=linprog(f,A,b,Aeq,beq)得结果：Optimization terminated successfully.x=4.0000 2.0000f=-14.0000,目标函数：min Z=x1+x2+x3+x4+x5+x6约束条件：x1+x2 70 x2+x3 60 x3+x4 50 x4+x5 20 x5+x6 30 x1+x6 60非负性约束：xj 0,j=1,2,6,例1,c=1;1;1;1;1;1;A=-1-1 0 0 0 0;0-1-1 0 0 0;0 0-1-1 0 0;0 0 0-1-1 0;0 0 0 0-1-1;-1 0 0 0 0-1;b=-70;-60;-50;-20;-30;-60;Aeq=;beq=;vlb=0;0;0;0;0;0;vub=;x,fval=linprog(c,A,b,Aeq,beq,vlb,vub),解:编写M文件xxgh2.m如下：,Optimization terminated successfully.x=41.9176 28.0824 35.0494 14.9506 9.8606 20.1394fval=150.0000,结果如下:,解 编写M文件xxgh1.m如下：c=-70;-120;A=9 4;4 5;3 10;b=360;200;300;Aeq=;beq=;Vlb=0;0;Vub=;x,fval=linprog(c,A,b,Aeq,beq,Vlb,Vub),数学建模总/%E6%95%B0%E5%AD%A6%E5%BB%BA%E6%A8%A1%E9%80%89%E4%BF%AE%E8%AF%BE/MATLAB6p1/bin/win32/matlab.exeMatlab(xxgh1),例2：,Optimization terminated successfully.x=20.0000 24.0000fval=-4.2800e+003,结果如下:,例3,解:编写M文件xxgh2.m如下：,f=13 9 10 11 12 8;A=0.4 1.1 1 0 0 0 0 0 0 0.5 1.2 1.3;b=800;900;Aeq=1 0 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 1;beq=400 600 500;vlb=zeros(6,1);vub=;x,fval=linprog(f,A,b,Aeq,beq,vlb,vub)x,fval=linprog(c,A,b,Aeq,beq,vlb,vub),Optimization terminated successfully.x=0.0000 600.0000 0.0000 400.0000 0.0000 500.0000fval=1.3800e+004,企业生产计划,生产与销售计划,空间层次,工厂级：根据外部需求和内部设备、人力、原料等条件，以最大利润为目标制订产品生产计划；,车间级：根据生产计划、工艺流程、资源约束及费用参数等，以最小成本为目标制订生产批量计划。,时间层次,若短时间内外部需求和内部资源等不随时间变化，可制订单阶段生产计划，否则应制订多阶段生产计划。,例：一奶制品加工厂用牛奶生产A1、A2两种奶制品。一桶牛奶可以在甲类设备上用12小时加工成3公斤A1，或者在乙类设备上用8小时加工成4公斤A2。根据市场需求，生产的A1、A2可以全部售出。每公斤A1获利24元，每公斤A2获利16元。现在每天有50桶牛奶的供应。每天正式工人总的工作时间为480小时，并且甲类设备每天至多能加工100公斤A1，乙类设备的加工能力不受限制。试为该厂制定一个生产计划，使该厂每天获利最大？并进一步讨论以下几个附加问题：1）若用35元可以买到一桶牛奶，应否作这项投资？若投资，每天最多购买多少桶牛奶？2）若可以聘请临时工以增加劳动时间，付给临时工的工资最多是每小时几元？,3）由于市场需求变化，每公斤A1的获利增加到30元，应否改变生产计划？为增加工厂的获利，开发了奶制品的深加工技术：用2小时和3元加工费。可以将1公斤A1加工成0。8公斤高级奶制品B1，也可以将1公斤A2加工成0。75公斤高级奶制品B2，每公斤B1获利44元，每公斤B2获利32元。试为该厂制定一个生产销售计划，使每天的净利润最大。并讨论以下问题：4）若投资30元可以增加供应1桶牛奶，投资3元可以增加1小时劳动时间，应否作这些投资？若每天投资150元，可赚回多少？5）每公斤高级奶制品B1、B2的获利经常有10%的波动，对制定的计划有无影响？若每公斤B1的获利下降10%，计划应该变化吗？,分析：,50桶牛奶,时间480小时,至多加工100公斤A1,制订生产计划，使每天获利最大,35元可买到1桶牛奶，买吗？若买，每天最多买多少?,可聘用临时工人，付出的工资最多是每小时几元?,A1的获利增加到 30元/公斤，应否改变生产计划？,每天：,x1桶牛奶生产A1,x2桶牛奶生产A2,获利 243x1,获利 164 x2,原料供应,劳动时间,加工能力,决策变量,目标函数,每天获利,约束条件,非负约束,线性规划模型(LP),时间480小时,至多加工100公斤A1,模型分析与假设,比例性,可加性,连续性,xi对目标函数的“贡献”与xi取值成正比,xi对约束条件的“贡献”与xi取值成正比,xi对目标函数的“贡献”与xj取值无关,xi对约束条件的“贡献”与xj取值无关,xi取值连续,A1,A2每公斤的获利是与各自产量无关的常数,每桶牛奶加工出A1,A2的数量和时间是与各自产量无关的常数,A1,A2每公斤的获利是与相互产量无关的常数,每桶牛奶加工出A1,A2的数量和时间是与相互产量无关的常数,加工A1,A2的牛奶桶数是实数,线性规划模型,模型求解,图解法,约束条件,目标函数,z=c(常数)等值线,在B(20,30)点得到最优解,目标函数和约束条件是线性函数,可行域为直线段围成的凸多边形,目标函数的等值线为直线,最优解一定在凸多边形的某个顶点取得。,MODEL:FVAL MAX=72*X1+64*X2;MILK X1+X2=50;TIME 12*X1+8*X2=480;SHOP 3*X1=100;END,Rows=4 Vars=2 No.integer vars=0(all are linear)Nonzeros=10 Constraint nonz=5(2 are+-1)Density=0.833 Smallest and largest elements in abs value=1.00000 480.000 No.:0,Obj=MAX,GUBs=1 Single cols=0Optimal solution found at step:1 Objective value:3360.000 Variable Value Reduced Cost X1 20.00000 0.0000000 X2 30.00000 0.0000000 Row Slack or Surplus Dual Price 1 3360.000 1.000000 2 0.0000000 48.00000 3 0.0000000 2.000000 4 40.00000 0.0000000,选lingo-Ranges即得:Ranges in which the basis is unchanged:Objective Coefficient Ranges Current Allowable Allowable Variable Coefficient Increase Decrease X1 72.00000 24.00000 8.000000 X2 64.00000 8.000000 16.00000 Righthand Side Ranges Row Current Allowable Allowable RHS Increase Decrease 2 50.00000 10.00000 6.666667 3 480.0000 53.33333 80.00000 4 100.0000 INFINITY 40.00000,模型求解,软件实现,LINDO 6.1,max 72x1+64x2st2）x1+x2503）12x1+8x24804）3x1100end,OBJECTIVE FUNCTION VALUE 1)3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2)0.000000 48.000000 3)0.000000 2.000000 4)40.000000 0.000000 NO.ITERATIONS=2,DO RANGE(SENSITIVITY)ANALYSIS?,No,20桶牛奶生产A1,30桶生产A2，利润3360元。,结果解释,OBJECTIVE FUNCTION VALUE 1)3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2)0.000000 48.000000 3)0.000000 2.000000 4)40.000000 0.000000 NO.ITERATIONS=2,原料无剩余,时间无剩余,加工能力剩余40,max 72x1+64x2st2）x1+x2503）12x1+8x24804）3x1100end,三种资源,“资源”剩余为零的约束为紧约束（有效约束）,结果解释,OBJECTIVE FUNCTION VALUE 1)3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2)0.000000 48.000000 3)0.000000 2.000000 4)40.000000 0.000000 NO.ITERATIONS=2,最优解下“资源”增加1单位时“效益”的增量,原料增加1单位,利润增长48,时间增加1单位,利润增长2,加工能力增长不影响利润,影子价格,35元可买到1桶牛奶，要买吗？,35 48,应该买！,聘用临时工人付出的工资最多每小时几元？,2元！,RANGES IN WHICH THE BASIS IS UNCHANGED:OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X1 72.000000 24.000000 8.000000 X2 64.000000 8.000000 16.000000 RIGHTHAND SIDE RANGES ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 50.000000 10.000000 6.666667 3 480.000000 53.333332 80.000000 4 100.000000 INFINITY 40.000000,最优解不变时目标函数系数允许变化范围,DO RANGE(SENSITIVITY)ANALYSIS?,Yes,x1系数范围(64,96),x2系数范围(48,72),A1获利增加到 30元/千克，应否改变生产计划,x1系数由24 3=72增加为303=90，在允许范围内,不变！,(约束条件不变),结果解释,RANGES IN WHICH THE BASIS IS UNCHANGED:OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X1 72.000000 24.000000 8.000000 X2 64.000000 8.000000 16.000000 RIGHTHAND SIDE RANGES ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 50.000000 10.000000 6.666667 3 480.000000 53.333332 80.000000 4 100.000000 INFINITY 40.000000,影子价格有意义时约束右端的允许变化范围,原料最多增加10,时间最多增加53,35元可买到1桶牛奶，每天最多买多少？,最多买10桶!,(目标函数不变),奶制品的生产销售计划,深加工,制订生产计划，使每天净利润最大,30元可增加1桶牛奶，3元可增加1小时时间，应否投资？现投资150元，可赚回多少？,50桶牛奶,480小时,至多100公斤A1,B1，B2的获利经常有10%的波动，对计划有无影响？,出售x1 千克 A1,x2 千克 A2，,X3千克 B1,x4千克 B2,原料供应,劳动时间,加工能力,决策变量,目标函数,利润,约束条件,非负约束,x5千克 A1加工B1，x6千克 A2加工B2,附加约束,模型求解,软件实现,LINDO 6.1,OBJECTIVE FUNCTION VALUE 1)3460.800 VARIABLE VALUE REDUCED COST X1 0.000000 1.680000 X2 168.000000 0.000000 X3 19.200001 0.000000 X4 0.000000 0.000000 X5 24.000000 0.000000 X6 0.000000 1.520000ROW SLACK OR SURPLUS DUAL PRICES 2)0.000000 3.160000 3)0.000000 3.260000 4)76.000000 0.000000 5)0.000000 44.000000 6)0.000000 32.000000 NO.ITERATIONS=2,OBJECTIVE FUNCTION VALUE 1)3460.800 VARIABLE VALUE REDUCED COST X1 0.000000 1.680000 X2 168.000000 0.000000 X3 19.200001 0.000000 X4 0.000000 0.000000 X5 24.000000 0.000000 X6 0.000000 1.520000ROW SLACK OR SURPLUS DUAL PRICES 2)0.000000 3.160000 3)0.000000 3.260000 4)76.000000 0.000000 5)0.000000 44.000000 6)0.000000 32.000000 NO.ITERATIONS=2,结果解释,每天销售168 千克A2和19.2 千克B1，利润3460.8（元）,8桶牛奶加工成A1，42桶牛奶加工成A2，将得到的24千克A1全部加工成B1,除加工能力外均为紧约束,结果解释,OBJECTIVE FUNCTION VALUE 1)3460.800 VARIABLE VALUE REDUCED COST X1 0.000000 1.680000 X2 168.000000 0.000000 X3 19.200001 0.000000 X4 0.000000 0.000000 X5 24.000000 0.000000 X6 0.000000 1.520000ROW SLACK OR SURPLUS DUAL PRICES 2)0.000000 3.160000 3)0.000000 3.260000 4)76.000000 0.000000 5)0.000000 44.000000 6)0.000000 32.000000,增加1桶牛奶使利润增长3.1612=37.92,增加1小时时间使利润增长3.26,30元可增加1桶牛奶，3元可增加1小时时间，应否投资？现投资150元，可赚回多少？,投资150元增加5桶牛奶，可赚回189.6元。（大于增加时间的利润增长）,结果解释,B1,B2的获利有10%的波动，对计划有无影响,RANGES IN WHICH THE BASIS IS UNCHANGED:OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X1 24.000000 1.680000 INFINITY X2 16.000000 8.150000 2.100000 X3 44.000000 19.750002 3.166667 X4 32.000000 2.026667 INFINITY X5-3.000000 15.800000 2.533334 X6-3.000000 1.520000 INFINITY,B1获利下降10%，超出X3 系数允许范围,B2获利上升10%，超出X4 系数允许范围,波动对计划有影响,生产计划应重新制订：如将x3的系数改为39.6计算，会发现结果有很大变化。,谢 谢！,