最优化方法图解法和LP基本定理学习教案.pptx

了解游戏教学的基本理念和方法 #生活乐趣# #游戏乐趣# #游戏教学#

《最优化方法图解法和LP基本定理学习教案.pptx》由会员分享，可在线阅读，更多相关《最优化方法图解法和LP基本定理学习教案.pptx（25页珍藏版）》请在知学网上搜索。

1、Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,11/7/2009,#,#,单击此处编辑母版标题样式,会计学,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,会计学,1,最优化方法(fngf)图解法和LP基本定理,第一页，共25页。,确定可行(kxng)域：,画约束直线，确定满足约束条件的半平面，所有半平面的交集，即为线性规划的可行(kxng)域。,确定目标函数的等值线及优化方向(fngxing)：画一

2、条目标函数等值线，并确定目标函数优化的方向(fngxing)。,平行移动(ydng)目标函数等值线，通过观察得到线性规划的最优解。,图解法的步骤,2,第一节 图解法,第1页/共25页,第二页，共25页。,例1.用图解法求解线性规划(xin xn u hu)问题,二、例题(lt)解析,3,第2页/共25页,第三页，共25页。,x,1,x,2,o,-3X,1,-4X,2,=-12(,),Lo,：,0=2X,1,+X,2,D,此点是唯一(wi y)最优解，,且最优目标函数值,min Z=-7,可行(kxng)域,4,解：,第3页/共25页,第四页，共25页。,例,2.,第4页/共25页,第五页，共2

3、5页。,x,1,x,2,o,X,1,-1.9X,2,=3.8,(),X,1,+1.9X,2,=3.8(,),X,1,-1.9X,2,=-3.8(,),X,1,+1.9X,2,=10.2,(),（,7.6,，,2,）,D,L,0,：,0=3X,1,+5.7X,2,max Z,（,3.8,，,4,）,30.6,=3,X,1,+5.7X,2,蓝色线段上的所有(suyu)点都是最,优解。这种情形为有无穷多最,优解，但是最优目标函数值,max Z=30.6是相同的。,可行(kxng)域,6,例,2.,第5页/共25页,第六页，共25页。,x,1,x,2,O,10,20,30,40,10,20,30,40

4、50,50,可行(kxng)域是空集,无可行(kxng)解(即无最优解),max Z=3,x,1,+4,x,2,7,例,3.,2X,1,+X,2,=40(,),X,1,+1.5,X,2,=30(,),X,1,+X,2,=50(,),第6页/共25页,第七页，共25页。,线性规划(xin xn u hu)的图解法启示：,线性规划(xin xn u hu)问题的解有多种情形；,若线性规划的可行(kxng)域非空，则一定是凸集（区域内任意两点连线都在其中）；,线性规划问题若有最优解,则最优解在可行域的某顶点上达到,.,第7页/共25页,第八页，共25页。,优缺点,简单、直观(zhgun)、便于初学

5、者理解和记忆；,仅适用于低维情况，通常(tngchng)适用于含两个或三个变量的情况。,9,对于高维情况,怎么(zn me)求解呢?-单纯形法,第8页/共25页,第九页，共25页。,第二节 线性规划(xin xn u hu)的标准形,10,线性规划(xin xn u hu)的形式是多种多样的:,目标函数求极大(极小);,约束可能(knng)有等式约束,也可能(knng)有不等式约束;,决策变量有的受非负约束,有的是无限制.,为了方便研究,考虑将各种形式的,LP,化为一种统一,的形式,这种形式即被称为,LP,的标准形式,.,第9页/共25页,第十页，共25页。,11,一、LP标准(biozhn)

6、形,三大特点,目标函数：,min,约束条件：=,变量符号：0,第10页/共25页,第十一页，共25页。,二、化LP为标准型的方法(fngf),12,第11页/共25页,第十二页，共25页。,13,例,1,2.举例(j l),分析:共有(n yu)4处不符合标准形的要求.,解,:,第12页/共25页,第十三页，共25页。,14,则相应(xingyng)的标准形为,第13页/共25页,第十四页，共25页。,15,例,2,分析(fnx):共有5处不符合标准形的要求.,解,:,第14页/共25页,第十五页，共25页。,16,则相应(xingyng)的标准形为,第15页/共25页,第十六页，共25页。,

7、第三节 LP基本(jbn)定理,将LP化为标准(biozhn)形后,如何求最优解呢?,有一个(y)定理给出了这个问题的答案,这就是LP基本定理.,第16页/共25页,第十七页，共25页。,18,LP标准形的矩阵(j zhn)形式,其中(qzhng),第17页/共25页,第十八页，共25页。,19,考虑(kol)具有标准形的LP:,一、线性规划(xin xn u hu)的基本概念,约束系数矩阵(j zhn)A是mn 矩阵(j zhn),mn，并且 r(A)m.,当,m,n,时，基矩阵唯一,;,当,m,n,时，基矩阵就可能有多个，但数目不超过 个。,1.,基,矩阵,:,若,A,中的,m,m,子矩阵

8、B,满足,r,(,B,),m,即,则称,B,是,LP,问题的一个基矩阵（简称为,基,）。,于是,A,中至少有一个,m,m,子矩阵,B,，使得：,r,(,B,),m,。,第18页/共25页,第十九页，共25页。,约束方程的系数矩阵为,：,例,1,设,易看出,r,（,A,）,=2,，,2,阶子矩阵有,=,10,个，而基矩阵只有,9,个，,20,第19页/共25页,第二十页，共25页。,2.基向量:基矩阵(j zhn)对应的列向量称为基向量，其余列向量称为非基向量.,3.基变量:基向量对应的变量称为(chn wi)基变量，非基向量对应的变量称为(chn wi)非基变量(自由变量)。,例如(lr)：

9、对于基B2而言，x1,x4是基变量，x2,x3,x5是非基变量。,x,1,x,4,思考,：基变量的选取唯一吗？取法有多少种？,第20页/共25页,第二十一页，共25页。,【注】基变量、非基变量是针对某一确定基而言的，不同(b tn)的基对应的基变量和非基变量也不同(b tn)。,4.基本(jbn)解:对于某一确定的基B，令所有的自由变量等于零,求出 Ax=b的解，称这组解为LP问题的关于基 的基本(jbn)解。,5.基可行解:非负的基本(jbn)解称为基可行解（基本(jbn)可行解）.,【,注,】,基可行解,也被定义为,“可行的基本解”。,22,注,:,基变量的选取方式,有限,所以基本解的个数

10、也为有限个,.,可见：,求基可行解要先求基本解,然后看是否非负即可。,另外，基本可行解也一定为有限个。,第21页/共25页,第二十二页，共25页。,二、基本(jbn)解的求法,例,1,求,的一个基本解和一个基本可行解,.,第22页/共25页,第二十三页，共25页。,解:约束方程的增广(zn un)矩阵,x,2,x,4,注意(zh y)到A是24矩阵,r(A)2.,由于第2列和第4列线性无关,构成一个2阶单位子块，因此(ync)可构成一个基矩阵.,取,为基变量,为自由变量,表示基变量得如下同解方程组,:,用自由变量,第23页/共25页,第二十四页，共25页。,又因该解非负，所以又是一个(y)基本可行解。,思考:若基变量选为其他变量时,如何(rh)求基本解呢?,启发:若系数矩阵(j zhn)中含有m阶单位子块很容易求基本解.,于是，得一个基本解：,第24页/共25页,第二十五页，共25页。,

网址：最优化方法图解法和LP基本定理学习教案.pptx https://www.yuejiaxmz.com/news/view/1371904

相关内容

最优化：建模、算法与理论/最优化计算方法
详解机器学习的凸优化、图神经网络、强化学习、贝叶斯方法等四大主题
最优化方法学习笔记01——基本概念
生活与哲学原理和方法论总结PPT学习教案
最优化学学习方法总结
学习方法的优化之策.pptx
学生学习方法优化的窍门秘诀.pptx
3.4 系统优化的基本方法
健身锻炼方法与评定
机器/深度学习模型最优化问题详解及优化算法汇总

随便看看