《单纯形法》PPT课件.ppt
《《单纯形法》PPT课件.ppt》由会员分享,可在线阅读,更多相关《《单纯形法》PPT课件.ppt(118页珍藏版)》请在三一办公上搜索。
1、第五章 单纯形法,在求解LP问题时,有人给出了图解法,但对多维变量时,却无能为力,于是美国数学家GBDantgig(丹捷格)发明了一种“单纯形法”的代数算法,尤其是方便于计算机运算。这是运筹学史上最辉煌的阶段。,本章主要内容,线性规划问题解的基本概念单纯形解法解的最优性检验表解形式的单纯形法单纯形解法的一些问题及其处理方法,第1节 单纯形解法的基本原理与思路,线性规划问题解的基本概念单纯形解法解的最优性检验,一、线性规划问题解的基本概念,可行解最优解基及基本解可行基及基本可行解代数解与几何解的关系单纯形法的要点,最优解,一、线性规划问题解的基本概念,可行解:满足所有约束条件(包括非负条件)的解
2、称为可行解.即可行域内所有点.,x1+x2300,2x1+x2400,x1 0,x20,s.t.,x2250,x1,200,0,200,300,可行域内的所有点称为:可行解.,maxz=50 x1+100 x2,一、线性规划问题解的基本概念,可行解:满足所有约束条件(包括非负条件)的解称为可行解.即可行域内所有点.最优解:达到最优的可行解.最优解.基本可行解:可行域内的顶点(边界).,基本可行解,初始基本可行解:由于求最优解是一个循环迭代的过程,那么,我们将第一次找到的可行域的顶点。,一、线性规划问题解的基本概念,基及基本解:,目标函数:maxz=50 x1+100 x2,x1+x2300,2
3、x1+x2400,x1 0,x20,s.t.,x2250,maxz=50 x1+100 x2,x1+x2+s1=300,2x1+x2+s2=400,x1 0,x20,si0,s.t.,x2+s3=250,一、线性规划问题解的基本概念,基及基本解:,maxz=50 x1+100 x2+0s1+0s2+0s3,1x1+1 x2+1s1+0s2+0s3=300,2x1+1 x2+0s1+1s2+0s3=400,x1 0,x20,s10,s20,s30,s.t.,0 x1+1x2+0s1+0s2+1s3=250,基及基本解:,s.t.,1x1+1 x2+1s1+0s2+0s3=300,2x1+1 x2
4、+0s1+1s2+0s3=400,x1 0,x20,si0,0 x1+1x2+0s1+0s2+1s3=250,基及基本解:,1x1+1 x2+1s1+0s2+0s3=300,2x1+1 x2+0s1+1s2+0s3=400,x1 0,x20,si0,0 x1+1x2+0s1+0s2+1s3=250,这是一个3X5的矩阵:,其中:,基及基本解:,这是一个3X5的矩阵:,从A中任取一个mxm的子矩阵B,只要B的秩为m,则称B为线性规划问题中的一个基.,基及基本解:,基中每一列(一个向量)称为该基的一个基向量(对B而言)。,是基,的三个基向量。,A中基之外的其它列称为B的非基向量。,是基,的三个基向
5、量.,又如:B,而A中其它两列,则称为B的非基向量.,原模型为:,s.t.,P3与变量s1对应,P4与变量s2对应,P5与变量s3对应,故称s1,s2,s3为基B的基变量,相应地,x1,x2成为B的非基变量.,s1 s2 s3,基及基本解:,s.t.,基及基本解:,s.t.,基及基本解:,s.t.,此方程有无穷多个解,为找最优解,可先令非基变量:x1=x2=0,S1=300,s2=400,s3=250,外加 x1=0,x2=0,基及基本解:,x1=0,x2=0,S1=300,s2=400,s3=250,本解是从基B中求出的,故被称为线性规划的基本解.(要求令非基变量为0,然后从基中解出而得),
6、再看另一个基本解:,s.t.,此方程有无穷多个解,为找最优解,可先令非基变量:s2=s3=0,x1=100,x2=250,s1=-50,外加 s2=0,s3=0,求得满足约束条件的解:基本解,S1=300,s2=400,s3=250,x1=0,x2=0,求得约束条件的解:基本解,S1=300,s2=400,s3=250,x1=0,x2=0,S1=-50 为负,超出可行域的范围;无效,所有决策量非负,在可行域内,称为基本可行解.相应地,B被称为可行基.,线性规划求解流程:,基及基本解:,在求解最优解时,往往会首先找到一个可行基,求出基本可行解,然后通过基本可行解,逐步迭代求出最优解.一般经验认为
7、,可找A中的单位矩阵.,作为(初始)可行基.,二、最优性检验,求出的基本可行解是否最优。还要进行检验!怎么检验?,1。最优性检验的依据-检验数j,是否最优,一般与目标函数的值有关,大家先来看目标函数的值:,在目标函数中,有基变量,也有非基变量;由于基变量可以用非基变量代换掉,这样,目标式中只留下了非基变量。,二、最优性检验,目标式中只留下了非基变量。或者说,基变量的目标系数化为0。,在目标式中,Z0为常量(不变),Xj0,只要看系数j的情况,,2。最优解判别定理定理:在求最大目标函数时,对于某个基本可行解,如果所有检验数j0,则这个可行解就是最优解。其中,最大值就是Z0。在求最小目标函数时,对
8、于某个基本可行解,如果所有检验数j0,则这个可行解就是最优解。其中,最小值就是Z0。,三、基变换,如果初始可行解不是最优解,那么,我们将要重新选择可行基,求出基本可行解,再检验。具体过程为:(1)先确定入基变量。根据检验系数j的大小确定把非基变量调入基中;一般认为,从j0中挑选最大的非基变量替换到基变量中,这一过程称为入基变量过程。(2)同时,要从可行基中挑选出一个向量,作为出基变量。换出的原则是求出的决策变量非负;或者挑选,比值最小的行的原基变量为出基变量。要求,例子,例子的标准型,标准型,标准型化原则:1.目标为min型的,价值系数一律反号令Z=-Z2.第I个约束行为型的,左边增加松驰量x
9、n+i非负,同时令Cn+i=0.3.第I个约束行为型的,左边增加剩余变量xn+i非负,同时令Cn+i=0.4.第I个约束行的bn+i为负的,则左右两边同时反号,保证bn+i.=0,线性方程组的增广矩阵表示,它的初始可行基,初始基本可行解,初始基变量 是松弛变量。初始可行解(只要满足非负条件)初始基本可行解目标函数与最优性检验,第一次迭代,确定入基变量,应当是,它的系数是4。确定出基变量,方法如下,得,确定新基和求解新的基本可行解,新基新的基变量:新的基本可行解,新的基本可行解和目标函数,基本可行解目标函数,第二次迭代,确定入基变量:确定出基变量:,确定新基和求解新的基本可行解,新基新的基变量:
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 单纯形法 单纯 PPT 课件

链接地址:https://www.31ppt.com/p-5475536.html