线性规划的数学模型和基本性质-PPT课件.pptx
《线性规划的数学模型和基本性质-PPT课件.pptx》由会员分享,可在线阅读,更多相关《线性规划的数学模型和基本性质-PPT课件.pptx(84页珍藏版)》请在咨信网上搜索。
1、线性性规划划及及单纯形法形法1线性规划介绍2线性规划数学模型3线性规划标准形式4线性规划的图解法5线性规划基本概念6单纯形法7应用举例11线性性规划介划介绍历史悠久,理论成熟,应用广泛运筹学的最基本的方法之一,网络规划、整数规划、目标规划和多目标规划都是以线性规划为基础的。解决稀缺资源最优分配的有效方法,使付出的费用最小或获得的收益最大。2线性性规划理划理论的的发展展:1939年前年前苏联康托洛康托洛维奇(奇(KOHTOPOBUZ)生生产组织与与计划中的划中的 数学方法数学方法提出提出 “解乘数法解乘数法”。1线性性规划介划介绍列奥尼德列奥尼德康托康托罗维奇,前奇,前苏联人,由于在人,由于在1
2、939年年创立立了享誉全球的了享誉全球的线形形规划要点,划要点,对资源最源最优分配理分配理论做做出了出了贡献,而献,而获得得诺贝尔经济学学奖。3美国科学院院士美国科学院院士DANTZIG(丹(丹齐克),克),1948年在年在研究美国空研究美国空军资源的源的优化配置化配置时提出提出线性性规划及其通用划及其通用解法解法“单纯形法形法”。被称。被称为线性性规划之父。划之父。1线性性规划介划介绍 线性规划之父的Dantzig(丹齐克)。据说,一次上课,Dantzig迟到 了,仰头看去,黑板上留了几个几个题目,他就抄了一下,回家后埋头苦做。几个星期之后,疲惫的去找老师说,这件事情真的对不起,作业好像太难
3、了,我所以现在才交,言下很是 惭愧。几天之后,他的老师就把他召了过去,兴奋的告诉他说他太兴奋了。Dantzig很不解,后来才知道原来黑板上的题目根本就不是什么家庭作业,而是老师说的本领域的未解决的问题,他给出的那个解法也就是单纯形法。这个方法是上个世纪前十位的算法。41线性性规划介划介绍 1960 1960年,年,“最佳最佳资源利用的源利用的经济计算算”康托洛康托洛维奇和奇和库伯曼斯伯曼斯(Koopmans)(Koopmans)。两人。两人因因对资源最源最优分配理分配理论的的贡献而献而获19751975年年诺贝尔经济学学奖 佳林佳林库普曼斯,美国人,他将数理普曼斯,美国人,他将数理统计学成功运
4、用学成功运用于于经济计量学,量学,对资源最源最优分配理分配理论做出了做出了贡献。献。51961年,查恩斯与库伯提出了目标规划,艾吉利提出了用优先因子来处理多目标问题。20世纪70年代,斯姆李与杰斯开莱尼应用计算机处理目标规划问题。计算机 50约束 100变量 30000约束 3000000变量1线性性规划介划介绍6从1964年诺贝尔奖设经济学奖后,到1992年28年间的32名获奖者中有13人(40%)从事过与线性规划有关的研究工作,其中著名的有Simon,Samullson,Leontief,Arrow,Miller等。1线性性规划介划介绍保罗-萨缪尔逊(PAUL A SAMUELSON),他
5、发展了数理和动态经济理论,将经济科学提高到新的水平。他的研究涉及经济学的全部领域。于1970年获得诺贝尔经济学奖。华西里列昂惕夫(WASSILY LEONTIEF),美国人,他发展了投入产出方法,该方法在许多重要的经济问题中得到运用。曾获1973年诺贝尔经济科学奖。肯尼斯-J-阿罗(KENNETH J.ARROW),美国人,因与约翰-希克斯(JOHN R.HICKS)共同深入研究了经济均衡理论和福利理论获得1972年诺贝尔经济学奖。牟顿-米勒(MERTON M.MILLER),1923-2000,美国人,由于他在金融经济学方面做出了开创性工作,于1990年获得诺贝尔经济奖。71线性性规划介划介
6、绍线性规划研究的主要问题:有一定的人力、财力、资源条件下,如何合理安排使用,效益最高?某项任务确定后,如何安排人、财、物,使之最省?8 例例1 美佳公司美佳公司计划制造划制造I,II两种家两种家电产品。已知各品。已知各制造一件制造一件时分分别占用的占用的设备A、B的台的台时、调试时间及及A、B设备和和调试工序每天可用于工序每天可用于这两种家两种家电的能力、各售出的能力、各售出一件一件时的的获利情况如表利情况如表Il所示。所示。问该公司公司应制造制造A、B两两种家种家电各多少件,使各多少件,使获取的利取的利润为最大?最大?项目目I IIIII每天可用能力每天可用能力设备A A(h h)设备B B
7、(h h)调试工序工序(h h)0 06 61 15 52 21 1151524245 5利利润(元)(元)2 21 12线性性规划数学模型划数学模型9例例2 捷运公司捷运公司拟在下一年度的在下一年度的1-4月的月的4个月内需租用个月内需租用仓库堆堆放物放物资。已知各月份所需。已知各月份所需仓库面面积数列数列见下表。下表。仓库租借租借费用随用随合同期定,期限越合同期定,期限越长折扣越大,具体数字折扣越大,具体数字见下表。租借下表。租借仓库的合的合同每月初都可同每月初都可办理,每份台同具体理,每份台同具体现定租用面定租用面积数和期限。因此数和期限。因此该厂可根据需要,在任何一个月初厂可根据需要,
8、在任何一个月初办理租借台同。每次理租借台同。每次办理理时可可签一份,也可一份,也可签若干份租用面若干份租用面积和租借期限不同的合同,和租借期限不同的合同,试确定确定该公司公司签订租借合同的最租借合同的最优决策,目的是使所付租借决策,目的是使所付租借费用最小。用最小。月份月份1 12 23 34 4所需所需仓库面面积1515101020201212合同租借期限合同租借期限1 1个月个月2 2个月个月3 3个月个月4 4个月个月合同期内的租合同期内的租费280028004500450060006000730073002线性性规划数学模型划数学模型10目目标函数函数约束条件束条件解:用解:用变量量x
9、1x1和和x2x2分分别表示美佳公司制造家表示美佳公司制造家电I I和和IIII的数量。的数量。项目目I IIIII每天可用能力每天可用能力设备A A(h h)设备B B(h h)调试工序工序(h h)0 06 61 15 52 21 1151524245 5利利润(元)(元)2 21 1例例1 1用数学用数学语言描述言描述2线性性规划数学模型划数学模型11解:设变量xij表示捷运公司在第i(i1,4)个月初签订的租借期为jj1,4)个月的仓库面积的合同(单位为100m2)。约束条件目标函数例例2 2月份月份1 12 23 34 4所需所需仓库面面积1515101020201212合同租借期限
10、合同租借期限1 1个月个月2 2个月个月3 3个月个月4 4个月个月合同期内的租合同期内的租费280028004500450060006000730073002线性性规划数学模型划数学模型12 A B 备用用资源源 煤煤 1 2 30 劳动日日 3 2 60 仓库 0 2 24 利利润 40 50求:最大利润的生产计划。练习1 生生产计划划问题2线性性规划数学模型划数学模型13max Z=40 x1+50 x2解:设产品A,B产量分别为变量x1,x2x1+2x2 30 3x1+2x2 602x2 24x1,x2 0s.t.2线性性规划数学模型划数学模型14求:最低成本的原料混合方案?求:最低成
11、本的原料混合方案?原料原料 A B 每每单位成本位成本 1 4 1 0 2 2 6 1 2 5 3 1 7 1 6 4 2 5 3 8 每每单位添位添 加加剂中中维生生 12 14 8 素最低含量素最低含量练习2 混合配料混合配料问题2线性性规划数学模型划数学模型15解:解:设每每单位添加位添加剂中原料中原料i的用量的用量为xi(i=1,2,3,4)minZ=2x1+5x2+6x3+8x4 4x1+6x2+x3+2x4 12 x1+x2+7x3+5x4 14 2x2+x3+3x4 8 xi 0(i=1,4)s.t.2线性性规划数学模型划数学模型16决策变量:向量(x1 xn)T 决策人要考虑和
12、控制的因素。非负约束条件:线性等式或不等式目标函数:Z=(x1 xn)线性式,求Z极大或极小线性规划模型特点2线性性规划数学模型划数学模型17如果规划问题的数学模型中,决策变量的取值可以是连续的,目标函数是决策变量的线性函数,约束条件是含决策变量的线性等式或不等式,则该类规划问题的数学模型称为线性性规划的数学模型划的数学模型。实际问题中线性的含义:一是严格的比例性二是可叠加性关于关于线性的界定性的界定2线性性规划数学模型划数学模型1819max(min)Z=c1x1+c2x2+cnxnn个个变量量价价值系系数数第第i 种种资源的源的拥有有量量技技术系数或系数或工工艺系数系数a11x1+a12x
13、2+a1nxn(=,)b1a21x1+a22x2+a2nxn(=,)b2 am1x1+am2x2+amnxn(=,)bmxj 0(j=1,n)s.t.线性性规划的一般式划的一般式2线性性规划数学模型划数学模型线性性规划的划的简写式写式2线性性规划数学模型划数学模型20线性性规划的向量表示式划的向量表示式2线性性规划数学模型划数学模型21线性性规划的矩划的矩阵表示式表示式2线性性规划数学模型划数学模型22比例性:决策变量变化引起目标的改变量与决策变量改变量成正比;可加性:每个决策变量对目标和约束的影响独立于其它变量;连续性:每个决策变量取连续值;确定性:线性规划中的参数aij,bi,ci为确定值
14、。隐含的假含的假设2线性性规划数学模型划数学模型23仓库工厂 1 2 3 库存 1 2 1 3 50 2 2 2 4 30 3 3 4 2 10 需求 40 15 35练习3 运运输问题工厂需要的原棉存放在三个仓库中,现将原棉运往工厂以满足工厂生产的需求。已知原棉运到各个工厂的单位运费如表所示。问使总运费最小的运输方案?2线性性规划数学模型划数学模型24解:解:设xij为i 仓库运到运到 j工厂的原棉数量工厂的原棉数量(i=1,2,3 j=1,2,3)minZ=2x11+x12+3x13+2x21+2x22+4x23+3x31 +4x32+2x33x11+x12+x13 50 x21+x22+
15、x23 30 x31+x32+x33 10 x11+x21+x31=40 x12+x22+x32=15x13+x23+x33=35 xij 0st.2线性性规划数学模型划数学模型25练习4 4 连续投投资1010万元万元A A:从第:从第1 1年到第年到第4 4年每年初投年每年初投资,次年末回收本利,次年末回收本利1.151.15;B B:第第3 3年初投年初投资资,到第,到第5 5年末回收年末回收本利本利1.251.25,最大投,最大投资4 4万元;万元;C C:第第2 2年初投年初投资资,到第,到第5 5年末回收年末回收本利本利1.401.40,最大投,最大投资3 3万元;万元;D D:每
16、年初投每年初投资资,每年末回收,每年末回收本利本利1.111.11。求:使求:使5 5年末年末总资本最大的投本最大的投资方案。方案。分析:分析:1 2 3 4 5A x1A x2A x3A x4A B x3BC x2CD x1D x2D x3D x4D x5D 2线性性规划数学模型划数学模型26解解:xik(i=1,2,5;k=A,B,C,D)为第第i年初投年初投资到第到第k个个项目的目的资金数。金数。MaxZ=1.15x4A+1.40 x2C+1.25x3B+1.11x5Dx1A+x1D=10 x2A+x2C+x2D=1.11 x1Dx2C 3x3A+x3B+x3D=1.15 x1A+1.1
17、1 x2Dx3B 4x4A+x4D=1.15 x2A+1.11 x3Dx5D=1.15 x3A+1.11 x4D xik 0s.t.2线性性规划数学模型划数学模型27线性性规划划问题应用用市场营销(广告预算和媒介选择,竞争性定价,新产品开发,制定销售计划)生产计划制定(合理下料,配料,“生产计划、库存、劳力综合”)库存管理(合理物资库存量,停车场大小,设备容量)运输问题财政、会计(预算,贷款,成本分析,投资,证券管理)人事(人员分配,人才评价,工资和奖金的确定)设备管理(维修计划,设备更新)城市管理(供水,污水管理,服务系统设计、运用)2线性性规划数学模型划数学模型28线性性规划的适用情况划的
18、适用情况要解决的问题的目标可以用数值指标反映对于要实现的目标有多种方案可选择有影响决策的若干约束条件2线性性规划数学模型划数学模型29线性规划模型的结构目标函数:max,min约束条件:,=,变量符号:0,0线性规划的标准形式目标函数:max约束条件:=变量符号:03线性性规划划标准形式准形式30标准型的一般型准型的一般型min z=c1x1+c2x2+cnxn其中 bi 0(i=1,2,m)a11x1+a12x2+a1nxn=b1a21x1+a22x2+a2nxn=b2 am1x1+am2x2+amnxn=bmxj 0(j=1,2,n)s.t.3线性性规划划标准形式准形式31 P1 P2 P
19、n a11 a12 a1n其中 A=a21 a22 a2n am1 am2 amn x1 x=x2 xn b1 b=b2 bmC=(C1 C2 Cn)标准型的矩准型的矩阵型型min Z=Ax=b x 0 b0 b 0 0 3线性性规划划标准形式准形式32 x1Ax=(P1 P2 Pn)x2 =b xn P1 x1+P2 x2+Pn xn=b标准型的向量型准型的向量型3线性性规划划标准形式准形式33线性性规划划问题化化标准型:准型:(1)、约束条件(2)、变量(3)、目标函数(4)、右端常数3线性性规划划标准形式准形式34(1)、约束条件束条件x3为松弛变量x4为剩余变量 松弛变量或剩余变量在实
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 线性规划 数学模型 基本 性质 PPT 课件
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【胜****】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【胜****】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。