最优化方法-线性规划课件.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《最优化方法-线性规划课件.ppt》由用户(晟晟文业)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 优化 方法 线性规划 课件
- 资源描述:
-
1、线性规划o数学教研室o石鸿雁引言o线性规划是数学规划的一个重要分支,历史比较悠久,理论比较成熟,方法较为完善。线性规划的思想最早可以追溯到1939年,当时的苏联数学家、经济学家(康特罗维奇)在生产组织与计划中的数学方法一书中提出了类似线性规划的模型,以解决下料问题和运输问题,并给出了“解决乘数法”的求解方法。然而,他们的长期工作未被人们知道。o由于战争的需要,美国的经济学家T.C.Koopmans(库普曼斯)重新独立的研究运输问题,并很快看到了线性规划在经济学中应用的意义。在这之后,线性规划也被广泛地应用于军事、经济等方面。由于他们在这方面的突出贡献,康特罗维奇和库普曼斯联合得到1975年诺贝
2、尔经济学奖。引言o对线性规划贡献最大的是美国数学家G.B.Dantig(丹捷格),他在1947年提出了求解线性规划的单纯形法(Simple Method),并同时给出了许多很有价值的理论,为线性规划奠定了理论基础。在1953年,丹捷格又提出了改进单纯形法,1954年Lemke(兰母凯)提出了对偶单纯形法(dual simplex method)。o在1976年,R.G.Bland 提出避免出现循环的方法后,使线性规划的理论更加完善。但在1972年,V.Klee和G.Minmty构造了一个例子,发现单纯形法的迭代次数是指数次运算,不是好方法并不是多项式算法(多项式算法被认为是好算法),这对单纯形
3、法提出了挑战。引言o1979年,前苏联青年数学家(哈奇扬)提出了一种新算法椭圆算法,是一个多项式算法,这一结果在全世界引起了极大轰动,被认为是线性规划理论上的历史突破。然而在实际计算中,椭球算法的计算量与单纯形算法差不多,因此,椭球算法并不实用。o1984年,在美国的贝尔实验室工作的印度数学家N.Karmarkar(卡玛卡尔)又提出了一个多项式算法Karmarkar 算法,Karmarkar算法本质上属于内点法,这种算法不仅在理论上优于单纯形算法,而且也显示出对求解大规模线性规划问题的巨大潜力。o此外,1980年前后,形成求解线性规划的有效集法(active set method),在理论上有
4、效集法与单纯形法是等价的,但解决问题的侧重点不同,因此各有优缺点,起着相互补充的作用。引言o由于很多非常重要的实际问题都是线性的,即使不是至少能够用线性函数很好地近似,所以线性规划的研究是很有价值的。o另一方面,线性规划方面的工作与非线性规划领域相比更为成熟。目前,线性规划方法的发展已被用来求解非线性模型,所以掌握线性规划的理论和解法是本课程的重要目标之一。线性规划(LP)A1A2B1B2B3工地工地运价(元运价(元/万块)万块)砖厂砖厂50 60 7060 110 1601947年 美国数学家 Dantzig 单纯形法 理论基础1979年 苏联数学家 哈奇安 椭球法 理论上的突破1984年
5、美国数学家 Karmarkar Karmarkar算法 大规模 1.问题与模型1.1.数学模型 例1.设有A1,A2两个工厂,产量分别为23万块和27万块砖,供应三个工地B1,B2,B3,其需求量分别为17万块、18万块和15万块,而自产地到各工地的运价见表,问应如何调运,才能使总运费最小?圆桌 0.18 0.08 6衣柜 0.09 0.28 10产品 利润 木 料第一种 第二种解 设xij Ai运往Bj的运量(万块)minS=50 x11+60 x12+70 x13+60 x21+110 x22+160 x23S.t.x11+x12+x13=23x21+x22+x23=27x11+x21=1
6、7x12+x22=18x13+x23=15xij0,i=1,2、j=1,2,3 例2.某木器厂生产圆桌和衣柜两种产品,现有两种木料,第一种有72m3,第二种有56m3,生产圆桌和衣柜所需木料如下表。每生产一个桌子可获利润6元,生产衣柜可获利润10元。木料厂在现有木料的条件下,圆桌和衣柜各生产多少,才能使利润最大?解设生产圆桌x1个,衣柜x2个max S=6x1+10 x2s.t.0.18x1+0.09x2720.08x1+0.28x256x1,x20 线性规划问题:约束条件及目标函数均为未知量的线线性规划问题:约束条件及目标函数均为未知量的线性函数,求目标函数的最大或最小值问题。性函数,求目标
7、函数的最大或最小值问题。.2图解法(只限于两个变量)max S=c1x1+c2x2 s.t.a11x1+a12x2b1 a21x1+a22x2b2 x1,x20在平面上取一直角坐标系,它的两个坐标分别是x1,x2,把满足第一个方程的x1,x2看作平面的一个点,那么这个点应在什么地方呢?平面被直线a11x1+a12x2=b1 划分为两个平面,这个点一定在两个半平面的某一个上面。所有满足约束条件的点就构成一个区域K。现在,我们就是要在K中找一点(x10,x20),使目标函数达到最大。a21x1+a22x2=b2a11x1+a12x2=b1c1x1+c2x2=hA我们知道,把h作为参数的方程c1x1
8、+c2x2=h 表示一平行直线束,在K中任意取一点(x10,x20),h=c1x1+c2x2=c1x10+c2x20 就表示这个直线束中通过(x10,x20)的一条直线。所以,我们要在K中找一点(x10,x20)使c1x10+c2x20为最大,就变成在直线束中找一条直线,这条直线既通过K中某一点,又使原点到这条直线的距离沿正法线方向达到最大。x2x1O那么,怎样找这条直线呢?让直线c1x1+c2x2=h 沿着它的正法线(梯度)方向移动,移动到刚刚开始要离开K的时候,这时的直线仍与K相交,也就是还通过K的点.总结:求最大,沿正法线方向移动。总结:求最大,沿正法线方向移动。求最小,沿负法线方向移动
9、。求最小,沿负法线方向移动。例1.max S=-x1+x2 s.t.2x1+x22 x1-2x22 x1+x25 x1,x20法线方向:,A(1,4)是S达到最大值的点。)21,21(x1+x2=5-2x1+x2=2x1-2x2=2A)51,52(例2min S=-2x1+x2 s.t.x1+x21 x1-3x2-3 x1,x20负法线方向:Ox1x2最小值为负无穷x1-3x2=-3x1+x2=1)101,103(例3Max S=3x1+x2 s.t.x1+x25 -x1+x20 6x1+2x221 x1,x20法线方向 ,此问题有无穷多个解.Ox1x2例4Max S=3x1+x2 s.t.x
10、1-x2-1 x1+x2-1 x1,x20此问题无可行解。Ox1x2-11-16x1+2x2=21x1+x2=5-x1+x2=0 x2x1O可在某一顶点上取得。总结:两个变量的线性规划问题的解有4种情况。1有唯一的最优解 2有最优解,但不唯一 (有无穷多个)3有可行解,但无最优解 4无可行解3 3标准形式min=c1x1+c2x2+cnxn s.t.a11x1+a12x2+a1nxn=b1 a21x1+a22x2+a2nxn=b2 am1x1+am2x2+amnxn=bm xj0;j=1,2,n bi0;i=1,2,m化一般问题为标准形式:(一)若ak1x1+ak2x2+aknxnbk 加一变
11、量xn+k0(松驰变量),改写为 ak1x1+ak2x2+aknxn+xn+k=bk若ak1x1+ak2x2+aknxnbk减一变量xn+k0(剩余变量),改写为 ak1x1+ak2x2+aknxn-xn+k=bk(二)若目标函数为max=c1x1+c2x2+cnxnmin=-=-(c1x1+c2x2+cnxn)(三)若xj0,令xj=xj-xj”,xj0,xj”0利用矩阵和向量的符号,线性规划问题可以写为a11 a12 a1n am1 am2 amnB=X=b1b2bmx1x2xnp1jp2jpmjPj=min=CX s.t.AX=b X0 min=CX s.t.xjPj=b X0 C=(c
12、1,c2,cn)A=mn.秩(A)=m4 线性规划问题的解可行解:满足约束条件的解最优解:使目标函数达到最大的可行解 基:若B是A中m*m阶非奇异子矩阵,(|B|0),则称B是一个基,相应于B的变量称为基变量。B被称为一个基,是由于是由m个线性无关列组成,这m个线性无关的列向量可以作为Em空间的一个基。基本解:令非基变量取零,则得唯一解,称为基本解。基本可行解:所有变量非负的基本解。可行基:对应于基可行解的基。例.Min Z=2x1+x2 s.t.x1+x2+x3 =5 -x1+x2 +x4 =0 6x1+2x2 +x5=21 xj0,j=1,2,5 1 1 1 0 0A=-1 1 0 1 0
13、 6 2 0 0 1由于 ,因此P3,P4,P5是一个基,对应的x3,x4,x5为基变量。1p3=0 0 0p4=1 0 0P5=0 1令x1=x2=0,则得x3=5,x4=0,x5=21,x0=(0,0,5,0,21)T是1 0 00 1 00 0 1对应于基B=的一个基本解。因xi0,x0为基本可行解。另外,向量P1=,P2=,P3=线性无关,因此P1,P2,P3为一个基,对应的x1,x2,x3为基变量。令x4=x5=0,得 x1=21/8,x2=21/8,x3=-2/8则x=(21/8,21/8,-2/8,0,0)T也是基本解,但其不是可行解。1 1 1-1 1 06 2 0 又向量P2
展开阅读全文