线性规划问题的单纯形法求解(第3讲)ppt课件.ppt
《线性规划问题的单纯形法求解(第3讲)ppt课件.ppt》由会员分享,可在线阅读,更多相关《线性规划问题的单纯形法求解(第3讲)ppt课件.ppt(54页珍藏版)》请在三一办公上搜索。
1、线性规划问题的单纯形法求解,运筹学第三讲2011.03.01,内容提要,线性规划问题解的概念线性规划问题的几何意义线性规划问题的单纯形求解,1.线性规划问题解的概念,标准型可行解:满足约束条件的解称为可行解。最优解:使目标函数达到最大值的可行解称为最优解。,基:若B是矩阵A中mm阶非奇异子矩阵(|B|0),则B是线性规划问题的一个基。不妨设:, j=1,2,,m 基向量。 ,j=1,2,,m 基变量。 , j=m+1,n 非基变量。,线性规划问题解的概念,线性规划问题解的概念,为了进一步讨论线性规划问题的解,下面研究约束方程的求解问题。假设该方程组系数矩阵A的秩为m,因mn,故它有无穷多个解。
2、假设前m个变量的系数列向量是线性独立的。,约束方程组可写成:,线性规划问题解的概念,上式的一个基是,设XB是对应于这个基的基变量XB=(x1,x2,xm)T现若令的非基变量xm+1=xm+2=xn=0,并用高斯消去法,可以求出一个解X=(x1,x2,xm,0,0)T这个解的非零分量的数目不大于方程的个数m,称为基解。于是,由一个基可以求出一个基解。,基可行解:满足非负条件的基解,称为基可行解。于是基可行解的非零分量的数目也不大于m,并且都是非负的。可行基:对应于基可行解的基,称为可行基。,例,基、基变量、非基变量、基向量、非基向量、基解、基可行解、可行基,例,行列式,基变量,非基变量,基向量,
3、非基向量,对应于基B1的基解X1,非基可行解,例,行列式,基变量,非基变量,基变量,非基变量,对应于基B2的基解X2,基可行解,线性规划解的关系图,非可行解,可行解,基可行解,基解,线性规划问题解的概念,最优解?,2.线性规划问题的几何意义,基本概念凸集:,线性规划问题的几何意义,顶点:若K是凸集,XK;若X不能用不同的两点 的线性组合表示为:则X为K的一个顶点。,凸集,线性规划问题的几何意义,顶点,定理1: 若线性规划问题存在可行域, 则其可行域: 是凸集.,基本定理,证明:,线性规划问题的几何意义,只要验证X在D中即可,引理:线性规划问题的可行解X为基可行解的充要条件是X的正分量对应的系数
4、列向量是线性独立的。,定理3:若可行域有界,线性规划问题的目标函数一定可以在其可行域的顶点上达到最优。,定理2:线性规划问题的基可行解X对应于可行域D的顶点。 证明:反证法。分两步。,几点结论:,线性规划问题的可行域是凸集。若线性规划问题有最优解,一定存在一个基可行解是最优解。基可行解与可行域的顶点一一对应,可行域有有限多个顶点。最优解必在顶点上得到。,单纯形法,单纯形法求解步骤: 1、找一个基可行解作为X0初始解 最容易得到的可行基是标准型线性规划的系数矩阵的单位矩阵。2、求检验数,检验X0是否为最优解 ()求检验数将约束方程组的基变量的系数矩阵化为单位矩阵;通过代入或加减乘除消元法将目标函
5、数中的基变量消去,则非基变量的系数即为检验数 ()最优解的判别当检验数全部小于或等于0时, 该基可行解为最优解,求解可结束.当存在正的检验数时,该基可行解就不是最优解,就要换到一个新的(与X0相邻的)基可行解(X1),3、换基(迭代)(1)确定进基变量:凡是检验数大于0的非基变量都可进基;但一般选择最大的检验数对应的变量进基。(2)按最小比原则确定出基变量,就可得一新的(更接近于最优解的)基可行解(X1),对(X1)重复的过程就可在有限步得到最优解,或判断出无最优解。,求解下列的线性规划max z=2x1+3x2+0 x3+0 x4+0 x5 x1+2x2+x3 =8 4x1 +x4 =16
6、1.12 4x2 +x5=12 x1,x2,x3,x4,x50,解 :1、求一个初始基可行解,可以看到x3,x4,x5的系数列向量组成一个单位矩阵,是约束方程组的一个可行基。,这些向量构成一个可行解基,对应的基可行解为x0=(0,0,8,16,12),基,对应于基B0的变量x3,x4,x5为基变量。为求检验数,将约束方程组的基变量的系数矩阵化为单位矩阵可以得到 x3 + x1+2x2 =8x4 +4x1 =16 x5 +4x2 =12或x3=8 - x1-2x2x4=16-4x1 x5=12-4x2将上式代入目标函数z=2x1+3x2+0 x3+0 x4+0 x5得到z=0+2x1+3x2。于
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 线性规划 问题 单纯 求解 ppt 课件
链接地址:https://www.31ppt.com/p-1358667.html