线性规划数学模型.ppt
《线性规划数学模型.ppt》由会员分享,可在线阅读,更多相关《线性规划数学模型.ppt(48页珍藏版)》请在咨信网上搜索。
1、1第二章 线 性 规 划(L Linearinear P Programmingrogramming)线性性规划划问题是目是目标函数和函数和约束条件均束条件均为线性的最性的最优化化问题。自从自从1947年丹捷格年丹捷格(Dantzig)提出求解提出求解线性性规划的划的单纯形方法以形方法以来,来,线性性规划在理划在理论上上趋向成熟。特向成熟。特别是在是在计算机能算机能处理成千理成千上万个上万个约束条件和决策束条件和决策变量的量的线性性规划划问题之后,之后,线性性规划的划的适用适用领域更域更为广泛,已成广泛,已成为现代管理中代管理中经常采用的基本方法之常采用的基本方法之一。一。线性性规划是最划是最
2、优化化问题中的重要中的重要领域之一,很多运筹学中域之一,很多运筹学中的的实际问题都可以用都可以用线性性规划来表述。很多其他种划来表述。很多其他种类的最的最优化化问题算法也都可以分拆成算法也都可以分拆成线性性规划子划子问题,然后求解。,然后求解。通通过学学习本章,本章,应当了解当了解线性性规划的有关概念,掌握划的有关概念,掌握线性性规划划模型的建立及模型的建立及优化方法,会用化方法,会用计算机算机对大型大型线性性规划模型划模型问题进行求解和分析。本章的行求解和分析。本章的难点点为单纯形形计算方法。算方法。2第一节 线性规划问题的提出线性性规划是运筹学的一个重要分支,主要用于研究解划是运筹学的一个
3、重要分支,主要用于研究解决有限决有限资源的最佳分配源的最佳分配问题,即如何,即如何对有限有限资源做出源做出最佳方式的最佳方式的调配和最有利的使用,以便最充分地配和最有利的使用,以便最充分地发挥资源的效能,以源的效能,以获取最佳取最佳经济效益。效益。它的适用它的适用领域非常广泛,从工域非常广泛,从工业、农业、商、商业、交通、交通运运输业、军事的事的计划和管理及决策到整个国民划和管理及决策到整个国民经济计划的最划的最优方案的提出,都有它的用武之地,是方案的提出,都有它的用武之地,是现代管代管理科学的重要基理科学的重要基础和手段之一。和手段之一。3第一节 线性规划问题的提出线性性规划研究的划研究的问
4、题主要有以下两主要有以下两类。(1)给出一定量的人力、物力、财力等资源,如何统筹规划这些有限资源完成最大任务。(如资金、设备、原标材料、人工、时间等)(2)给定一项任务,如何运筹规划,合理安排,以最少资源来完成它。(如产品量最多、利润最大.)线性性规划要研究的两划要研究的两类问题中都有一个限制条件:第中都有一个限制条件:第一一类问题是是给出一定量的人力、物力和出一定量的人力、物力和财力等力等资源;源;第二第二类问题是是给定一定一项任任务。4第二节 线性规划问题的数学模型当用当用线性性规划的方法划的方法对实际问题进行行优化化时,必必须把把这个个实际问题用恰当的数学形式表达出用恰当的数学形式表达出
5、来,来,这个表达的个表达的过程,就是建立数学模型的程,就是建立数学模型的过程。数学模型的建立需要程。数学模型的建立需要经验和技巧以及有关和技巧以及有关的的专业知知识,只有通,只有通过大量的大量的实践,在建立模践,在建立模型型时才能得心才能得心应手。初学手。初学时可从可从题目中所目中所给出出的限制条件和目的限制条件和目标入手,由限制条件建立起入手,由限制条件建立起线性方程性方程组,由目,由目标得到目得到目标函数。函数。下面,下面,结合若干个合若干个实际问题讨论数学模型的建数学模型的建立。立。5一、投资问题的数学模型解(参见教材P15)6二、配料问题的数学模型解(参见教材P16)二、配料问题的数学
6、模型 某化工厂要用三种原料某化工厂要用三种原料 A,B B,C C 混合配制三种不同规格混合配制三种不同规格的产品的产品 X,Y,Z。有关数据如下有关数据如下:产品产品规规 格格单价单价(元元/kg)X原料原料D不少于不少于50%原料原料P不超过不超过25%50Y原料原料D不少于不少于25%原料原料P不超过不超过50%35Z不不 限限25原料原料最大供量最大供量(kg/天天)单价单价(元元/kg)A1006565B1002525C603535应如合配制应如合配制,才能使利润达到最大才能使利润达到最大?表表2-3表表2-4二、配料问题的数学模型一、决策变量决策变量 设以设以 xij 表示每天生产
7、的表示每天生产的第第i 种产品中所含第种产品中所含第j 种原料种原料的数量的数量(kg,右表右表)。ji A B CXYZx11 x12 x13x21 x22 x23x31 x32 x33二、约束条件二、约束条件 规格约束规格约束(据据表表2-3)x11+x12+x13x11 0.50 x11+x12+x13x12 0.25x11+x12+x13x21 0.25x11+x12+x13x22 0.50二、配料问题的数学模型改写成改写成 -x11 +x12 +x13 0-x11+3 x12 -x13 0-3 x21 +x22 +x23 0 x21 +x22 -x23 0 资源约束资源约束(据据表表
8、2-4)x11+x21 +x31 100 x12+x22+x32 100 x13+x23 +x33 60二、配料问题的数学模型三、目标函数三、目标函数 总产值总产值(据据表表2-3)产品产品X的产值的产值:50(x11+x12 +x13)产品产品Y的产值的产值:35(x21+x22+x23)产品产品Z的产值的产值:25(x31+x32 +x33)以上三项之和即以上三项之和即总产值总产值。总成本总成本(据据表表2-4)原料原料A的成本的成本:6565(x11+x21 +x31)原料原料B的成本的成本:2525(x12+x22+x32)原料原料C的成本的成本:3535(x13+x23 +x33)以
9、上三项之和即以上三项之和即总成本总成本。二、配料问题的数学模型 目标函数目标函数为:为:总利润总利润总利润总利润=总产值总产值-总成本总成本max z z=-15x11+25x12+15x13-30 x21+10 x22-40 x31-10 x33 该问题的数学模型为该问题的数学模型为:s.t.-x11 +x12+x13 0 -x11+3x12 -x13 0 -3x21+x22 +x23 0 x21+x22 -x23 0 x11 +x21 +x31 100 x12 +x22 +x32 100 x13 +x23 +x33 60 xij 0,i=1,2,3;j=1,2,3配料问题配料问题练习:练习
10、:某化工厂根据一项合同要为用户生产一种某化工厂根据一项合同要为用户生产一种用甲、乙两种原料混合配制而成的特殊产品。甲、用甲、乙两种原料混合配制而成的特殊产品。甲、乙两种原料都含有乙两种原料都含有A,B,C三种化学成分三种化学成分,其含量其含量(%)是是:甲为甲为1212,2 2,3 3;乙为乙为3 3,3 3,1515。按合同规按合同规定定,产品中三种化学成分的含量产品中三种化学成分的含量(%)不得低于不得低于4 4,2 2,5 5。甲、乙原料成本为每千克甲、乙原料成本为每千克3 3,2 2元。元。厂方希望厂方希望总成本达到最小总成本达到最小,则应如何配制该产品则应如何配制该产品?配料问题配料
11、问题 成分含量成分含量(%)(%)原原 料料 化学成分化学成分 甲甲 乙乙 产品成分产品成分 最低含量最低含量(%)(%)A B C 12 3 2 3 3 15 4 2 5 成本(元成本(元/千克)千克)3 2 x x1 1x x2 2min z z=3x1+2x2 12 x1 +3x2 4 2 x1 +3x2 2s.t.3 x1+15x2 5 x1 +x2=1 x1,x2 0配料平衡条件配料平衡条件z z14三、人力资源问题的数学模型解(参见教材P17)三、人力资源问题的数学模型练习:练习:某昼夜服务的公交线路每天各时间段内某昼夜服务的公交线路每天各时间段内所需司机和乘务人员人数如下表所示:
12、所需司机和乘务人员人数如下表所示:班次班次时间时间所需人员所需人员16:0010:0060210:0014:0070314:0018:0060418:0022:0050522:002:002062:006:0030设司机和乘务人员分别在各时间段开始时上班,并连续工作设司机和乘务人员分别在各时间段开始时上班,并连续工作8小时,问该公交线路应怎样安排司机和乘务人员,即能满小时,问该公交线路应怎样安排司机和乘务人员,即能满足工作需要,又使配备司机和乘务人员的人数减少足工作需要,又使配备司机和乘务人员的人数减少?三、人力资源问题的数学模型解:解:设xi表示第表示第i班次班次时开始上班的司机和乘开始上班
13、的司机和乘务人人员人数。人数。此问题最优解:此问题最优解:x150,x220,x350,x40,x520,x610,一共需要司机和乘务员,一共需要司机和乘务员150人。人。17四、合理下料问题的数学模型合理下料合理下料问题是机械工是机械工业常遇到的常遇到的问题。毛坯。毛坯车间经常要在常要在长度一定的条形材料或面度一定的条形材料或面积一定的板材上切割一定的板材上切割若干个具有一定形状、尺寸的毛坯。在一般情况下,若干个具有一定形状、尺寸的毛坯。在一般情况下,材料不可能被完全利用,会有材料不可能被完全利用,会有边角余料,造成浪角余料,造成浪费。因此,如何最大限度地减少因此,如何最大限度地减少边角余料
14、,提高材料利用角余料,提高材料利用率,使得切割率,使得切割规定数量的毛坯所用材料最少就是合理定数量的毛坯所用材料最少就是合理下料下料问题所要研究的。所要研究的。例2-5 某车间有一批长度为180cm的钢管(数量充分多),为了制造零件的需要,要将其截成三种不同长度的管料:70cm、52cm、35cm。规定这三种管料的需要量分别不少于100根、150根和100根。问:应如何下料能使消耗的钢管数量最少?解(参见教材P18)四、合理下料问题的数学模型 练习:制造某种机床制造某种机床,需要需要 A,B,C三种轴件三种轴件,其规格其规格与数量如表所示与数量如表所示,各类轴件都用各类轴件都用5.5米长的同一
15、种圆钢米长的同一种圆钢下料下料。若计划生产若计划生产100台机床台机床,最少需要用多少根圆钢最少需要用多少根圆钢?四、合理下料问题的数学模型轴类轴类 规格:长度(米)规格:长度(米)每台机床所需轴件数每台机床所需轴件数 A 3.1 1 B 2.1 2 C 1.21.2 4 余料余料 j j 1.21.2找出全部找出全部省料截法省料截法一根圆钢所截各类轴件数一根圆钢所截各类轴件数 截法截法轴类轴类 轴轴 件件 需要量需要量 A(3.1)100 B(2.1)200 C(1.2)400 余料余料(米米)234511100.310200210.1 0 0 1 0 2 4 1 0.7四、合理下料问题的数
16、学模型min z=x1+x2+x3+x4+x5s.t.x1+x2 100 x1 +2x3 +x4 200 2x2 +x3+2x4+4x5 400 x1,x2,x3,x4,x5 0则该问题的数学模型为则该问题的数学模型为:设第设第 j 种截法下料种截法下料 xj 根。根。四、合理下料问题的数学模型例:现有一批某种型号的圆钢长例:现有一批某种型号的圆钢长8米,需要截取米,需要截取2.5米米长的毛坯长的毛坯100根,长根,长1.3米的毛坯米的毛坯200根。问如何才能根。问如何才能既满足需要,又能使总的用料最少?既满足需要,又能使总的用料最少?解:为了找到一个省料的套裁方案,必须先设计出较好的几解:为
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 线性规划 数学模型
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【a199****6536】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【a199****6536】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。