运筹学课件ch1单纯形法.pptVIP

计算检验比θ,确定出基向量*01020304Minθ(θ≥0)P5出基B1=(P3,P4,P2)确定新基1事实上，单纯形法的实现是在单纯形表上完成的。32问题：当模型规模较大时，计算量很大。换基、计算下一个基可行解、再检验，直至最优练习：对于下面的线性规划*用图解法求解；将模型化为标准型；用单纯形法步骤求出其最优解，并指出求解过程中每一个基可行解相当于可行域的哪一个角点。010302三、单纯形表*单纯形表是基于单纯形法的步骤设计的计算格式，是单纯形法的具体实现。回顾单纯形法步骤*单纯形表CjC1C2CjθCBXBB-1bX1X2XjP1P2pjσ(σ≤0?)Ab分别将系数C,矩阵A和资源限制b填入,得到单纯形表的初表,计算检验数,进行最优性检验,若非优,就做初等行变换,形成新基的单纯形表σ=C-CBB-1A单纯形表的主要结构：问题：第一张表的B-1=？——单位阵I。检验数的公式是什么？例5：用单纯形法求解例1*问题：标准模型的A中是否含I？——松弛变量系数恰好构成I。[][]中表示进基列与出基行的交叉元，下一张表将实行以它为主元的初等行变换（称高斯消去）。方法是：先将主元消成1，再用此1将其所在列的其余元消成0。此行元素乘以(-5)加入上行*[][]（请解释其实际意义）此行元素除以主元10300.31000.1此行元素除以主元2.5练习：用单纯形法求解下面的线性规划*[]注：1.表上每一列的含义：每张表上B-1的位置在哪？——对应于初表中I的位置。12第二节单纯形法*BDFACE单纯形法是求解线性规划的主要算法，1947提出。但单纯形法以其简单实用的特色始终保持着绝对年由美国斯坦福大学教授丹捷格（）尽管在其后的几十年中，又有一些算法问世，的“市场”占有率。1.线性规划的标准型一、单纯形法的预备知识*用单纯形法求解线性规划的前提是先将模01型化为标准型表示为02标准型的特征：Max型、等式约束、非负约束03非标准形式如何化为标准*1)Min型化为Max型加负号因为，求一个函数的极小点，等价于求该函数的负函数的极大点。注意：Min型化为Max型求解后，最优解不变，但最优值差负号。⑵.约束方程的转换：由不等式转换为等式。称为松弛变量01称为剩余变量022)不等式约束化为等式约束*例1某工厂可生产甲、乙两种产品，需消耗煤、电、油三种资源。现将有关数据列表如下：试拟订使总收入最大的生产方案。资源单耗产品资源甲乙资源限量煤电油9445310360200300单位产品价格7122)不等式约束化为等式约束*分析：以例1中煤的约束为例X3称为松弛变量。问题：它的实际意义是什么？之所以“不等”是因为左右两边有一个差额，称为“松弛量”，若在左边加上这个松弛量，则化为等式。而这个松弛量也是变量，记为X3，则有——煤资源的“剩余”。2341练习：请将例1的约束化为标准型*解：增加松弛变量01.则约束化为02.易见，增加的松弛变量的系数恰构成一个单位阵I。03.一般地，记松弛变量的向量为Xs，则问题：松弛变量在目标中的系数为何？——0。当模型中有某变量xk没有非负要求，称为自由变量,则可令化为标准型。（1）可行解与最优解2.基本概念*直观上，可行解是可行域中的点，是一个可行的方案；01最优解是可行域的角点，是一个最优的方案。02（2）基矩阵与基变量*基矩阵(简称基)：由系数阵A中的线性无关的列组成的m阶子矩阵，记为B；其余列构成非基矩阵，记为N。基向量：基B中的列；其余的列称非基向量。基变量：与基向量Pj对应的决策变量xj，记其组成的向量为XB；与非基向量对应的变量称非基变量，记其组成的向量为XN。基矩阵的特点:1.基B是可逆矩阵,即2.基B是一个方阵r（B）=m或者A=(B