线性规划问题的单纯形法求解(第3讲)ppt课件.ppt

《线性规划问题的单纯形法求解(第3讲)ppt课件.ppt》由会员分享，可在线阅读，更多相关《线性规划问题的单纯形法求解(第3讲)ppt课件.ppt（54页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、线性规划问题的单纯形线性规划问题的单纯形法求解法求解运筹学运筹学第三讲第三讲2011.03.01内容提要内容提要线性规划问题解的概念线性规划问题的几何意义线性规划问题的单纯形求解线性规划问题的单纯形求解1.1.1.1.线性规划问题解的概念线性规划问题解的概念线性规划问题解的概念线性规划问题解的概念标准型可行解：满足约束条件的解称为可行解。最优解：使目标函数达到最大值的可行解称为最优解。基：若B是矩阵A中mm阶非奇异子矩阵（|B|0），则B是线性规划问题的一个基。不妨设：,j=1，2，,m 基向量。，j=1，2，,m 基变量。,j=m+1,n 非基变量。为了进一步讨论线性规划问题的解，下面研究约

2、束方程的求解问题。假设该方程组系数矩阵A的秩为m,因m0,并且对i=1,2,m有ai,m+k0,那么该线性规划问题具有无界解（或称无最优解）基变换基变换 1、换入变量的确定：由前面的分析看到，当某些j0时，xj增加则目标函数还可以增大，这时要将某个非基变量xj换到基变量中去（称为换入变量）。若有两个以上的j0，那么选哪个非基变量作为换入变量呢？为了使目标函数值增加最快，从直观上一般选j0中 的 大 者（可 以 任 意 选 或 按 最 小 下 标 选）即max(j0)=k 则对应的xk为换入变量。实际上换一次基将使目标函数值改进k。换出变量确定Z 大大（在可行的范围内）迭代运算 写成增广矩阵的形

3、式,进行迭代.例：非基变量基变量001通过初等行变换化主列为主元 每次迭代的信息都在增每次迭代的信息都在增广矩阵及目标函数中。广矩阵及目标函数中。检验数 在上一节单纯形法迭代原理中可知，每一次迭代计在上一节单纯形法迭代原理中可知，每一次迭代计算只要表示出当前的约束方程组及目标函数即可。算只要表示出当前的约束方程组及目标函数即可。单纯形表E单位阵N非基阵基变量XB非基变量XN0 单纯形表 2 1 0 0 0 检验数单纯形表结构 单纯形表 24/65/1C已知用单纯形表求解LP问题例.用单纯形表求解LP问题解：化标准型 2 1 0 0 0 0 15 0 5 1 0 0 0 24 6 2 0 1 0

4、 0 5 1 1 0 0 1 2 1 0 0 0 24/65/1主元化为1主列单位向量 换出 换入表1：列初始单纯形表 （单位矩阵对应的变量为基变量）正检验数中最大者对应的列为主列最小的值对应的行最小的值对应的行为主行为主行 2 1 0 0 0 0 15 0 5 1 0 0 2 4 1 2/6 0 1/6 0 0 1 0 4/6 0 -1/6 1 0 1/3 0 -1/3 0 15/524/26/4 0*5 2*2/6 +0*4/61-2/3=表2：换基 （初等行变换，主列化为单位向量，主元为1）检验数0确定主列 最小确定主列主元 2 1 0 0 0 0 15/2 0 0 1 5/4 -15/2 2 7/2 1 0 0 1/4 -1/2 1 3/2 0 1 0 -1/4 3/2 0 0 0 -1/4 -1/2 检验数=0最优解为X=(7/2,3/2,15/2,0,0)目标函数值Z=8.5 2*7/2 1*3/2+0*15/28.5表3：换基 （初等行变换，主列化为单位向量，主元为1）