数学建模公选课第二讲.ppt
《数学建模公选课第二讲.ppt》由会员分享,可在线阅读,更多相关《数学建模公选课第二讲.ppt(59页珍藏版)》请在三一办公上搜索。
1、数学建模公选课,基础教研室,第二讲:线性规划模型,引例:某商业规划处在商场内要装修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.
2、该商场的目标是在不超过所有资源限量的条件下,如何确定数量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
3、和x 1,x 2 0约束的点,必然在由这三个半平面围成的区域内。所有约束条件为半平面围成的区域见右下图阴影部分。阴影区域中的每一个点(包括边界点)都这个线性规划问题的解。,再分析目标函数,在这坐标平面上,它表示以 z为参数、为斜率的一族平行直线:,x 2=x1+z 位于同一直线上的点,具有相同的目标函数值,因而称它为“等值线”。当z值由小变大时,直线x 2=x1+z 沿其法线方向(法线方向是指与直线垂直的方向)向上方移动。当移动到Q 2点时,使z值在可行域(阴影部分)边界上实现最大化,这就得到了最优解Q2,Q2点的坐标为(4,2)。于是算得Max=14。这说明该商场的最优装修计划方案是:装修铺
4、位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。最优解:满足所有约束
5、条件和目标函数的向量。4。最优值:最优解的目标函数值。,建模分析,第一步:决策变量。决策变量选取得当,不仅能顺利地建立模型而且能方便地求解,否则很可能事倍功半。第二步:约束条件。并用决策变量的线性方程或线性不等式来表示。当限制条件多,背景比较复杂时,可以采用图示或表格形式列出所有的已知数据和信息,以避免“遗漏”或“重复”所造成的错误。,第三步:目标函数。确定对函数是取极大还是取极小的要求。决策变量的非负要求可以根据问题的实际意义加以确定。讨论:这三步的顺序可以颠倒吗?为什么?,几类典型的LP问题,有大量的实际问题可以归结为线性规划问题来研究,这些问题背景不同,表现各异,但数学模型却有着完全相同
6、的形式。尽可能多地掌握一些典型的模型不仅有助于深刻理解线性规划本身的理论和方法,而且有利于灵活地处理千差万别的实际问题,提高解决实际问题的能力。,例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:生产计划问题:某厂生产两种产品,需要三种资源,已知各产品的利润、各资源的限量和各产品
7、的资源消耗系数如下表,问题:如何安排生产计划,使得获利最多?,步骤: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,且已知用三种不同车床加工单位数量不同工件所需的台时数和加工
8、费用如下表。问怎样分配车床的加工任务,才能既满足加工工件的要求,又使加工费用最低?,设在甲车床上加工工件1、2、3的数量分别为x1、x2、x3,在乙车床上加工工件1、2、3的数量分别为x4、x5、x6。可建立以下线性规划模型:,应用总结,市场营销(广告预算和媒介选择,竞争性定价,新产品开发,制定销售计划)生产计划制定(合理下料,配料,“生产计划、库存、劳力综合”)库存管理(合理物资库存量,停车场大小,设备容量)运输问题财政、会计(预算,贷款,成本分析,投资,证券管理)人事(人员分配,人才评价,工资和奖金的确定)设备管理(维修计划,设备更新)城市管理(供水,污水管理,服务系统设计、运用),要解决
9、的问题的目标可以用数值指标反映对于要实现的目标有多种方案可选择有影响决策的若干约束条件,用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.,引例
10、解:编程序如下: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
11、 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
12、;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
13、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
14、.3800e+004,企业生产计划,生产与销售计划,空间层次,工厂级:根据外部需求和内部设备、人力、原料等条件,以最大利润为目标制订产品生产计划;,车间级:根据生产计划、工艺流程、资源约束及费用参数等,以最小成本为目标制订生产批量计划。,时间层次,若短时间内外部需求和内部资源等不随时间变化,可制订单阶段生产计划,否则应制订多阶段生产计划。,例:一奶制品加工厂用牛奶生产A1、A2两种奶制品。一桶牛奶可以在甲类设备上用12小时加工成3公斤A1,或者在乙类设备上用8小时加工成4公斤A2。根据市场需求,生产的A1、A2可以全部售出。每公斤A1获利24元,每公斤A2获利16元。现在每天有50桶牛奶的供应
15、。每天正式工人总的工作时间为480小时,并且甲类设备每天至多能加工100公斤A1,乙类设备的加工能力不受限制。试为该厂制定一个生产计划,使该厂每天获利最大?并进一步讨论以下几个附加问题:1)若用35元可以买到一桶牛奶,应否作这项投资?若投资,每天最多购买多少桶牛奶?2)若可以聘请临时工以增加劳动时间,付给临时工的工资最多是每小时几元?,3)由于市场需求变化,每公斤A1的获利增加到30元,应否改变生产计划?为增加工厂的获利,开发了奶制品的深加工技术:用2小时和3元加工费。可以将1公斤A1加工成0。8公斤高级奶制品B1,也可以将1公斤A2加工成0。75公斤高级奶制品B2,每公斤B1获利44元,每公
16、斤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
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数学 建模 选课 第二
链接地址:https://www.31ppt.com/p-5985127.html