单纯形法 (2)精选PPT.ppt

关于单纯形法(2)第1页，讲稿共85张，创作于星期日1.线性规划的标准型 用单纯形法求解线性规划的前提是先将模型化为标准型：标准型的特征：Max型、等式约束、非负约束一、单纯形法的预备知识第2页，讲稿共85张，创作于星期日非标准形式如何化为标准1)Min型化为Max型 加负号 因为，求一个函数的极小点，等价于求该函数的负函数的极大点。注意：Min型化为Max型求解后，最优解不变，但最优值差负号。第3页，讲稿共85张，创作于星期日第4页，讲稿共85张，创作于星期日2)不等式约束化为等式约束分析：以例1中煤的约束为例之所以“不等”是因为左右两边有一个差额，称为“松弛量”，若在左边加上这个松弛量，则化为等式。而这个松弛量也是变量，记为X3，则有X3称为松弛变量。问题：它的实际意义是什么？煤资源的“剩余”。第5页，讲稿共85张，创作于星期日练习：请将例1的约束化为标准型解：增加松弛变量则约束化为易见，增加的松弛变量的系数恰构成一个单位阵I。第6页，讲稿共85张，创作于星期日一般地，记松弛变量的向量为 Xs，则问题：松弛变量在目标中的系数为何？0。3)当模型中有某变量 xk 没有非负要求，称为自由变量,则可令 化为标准型。第7页，讲稿共85张，创作于星期日2.基本概念（1）可行解与最优解直观上，可行解是可行域中的点，是一个可行的方案；最优解是可行域的角点，是一个最优的方案。第8页，讲稿共85张，创作于星期日（2）基矩阵与基变量基矩阵(简称基)：系数阵A中的m阶可逆子阵，记 为B；其余部分称为非基矩阵，记为N。基向量：基B中的列；其余称非基向量。基变量：与基向量Pj对应的决策变量xj，记其组成的 向量为XB；与非基向量对应的变量称非基变 量，记其组成的向量为XN。第9页，讲稿共85张，创作于星期日 6个。一般地，mn 阶矩阵A中基的个数最多有多少个？问题：本例的A中一共有几个基？第10页，讲稿共85张，创作于星期日（3）基本解与基本可行解可见：一个基本解是由一个基决定的。注意：基本解仅是资源约束的解，并未要求其非负，因此其未必可行。称非负的基本解为基本可行解（简称基可行解）。第11页，讲稿共85张，创作于星期日例4：在上例中求相应于基B1和B2的基本解，它们是否基本可行解？第12页，讲稿共85张，创作于星期日上二组概念间的联系：系数阵A中可找出若干个基B每个基B都对应于一个基本解非负的基本解就是基本可行解几种解之间的关系：可行解基本解非可行解基本可行解问题：基本可行解是可行域中的哪些点？第13页，讲稿共85张，创作于星期日3.基本定理（1）线性规划的可行域是一个凸多面体。（2）线性规划的最优解（若存在的话）必能在可行 域的角点获得。（3）线性规划可行域的角点与基本可行解一一对应。第14页，讲稿共85张，创作于星期日二、单纯形法的步骤 单纯形法是一种迭代的算法，它的思想是在可行域的角点基本可行解中寻优。由于角点是有限个（为什么？），因此，算法经有限步可终止。确定一个初始基可行解检验这个基可行解是否最优寻找一个更好的基可行解否是停止第15页，讲稿共85张，创作于星期日1.确定初始基可行解 由于基可行解是由一个可行基决定的，因此，确定初始基可行解X0相当于确定一个初始可行基B0。方法：若A中含I，则B0=I；若A中不含I，则可用人工变量法构 造一个I。问题：若B0=I，则X0=？第16页，讲稿共85张，创作于星期日2.最优性检验问题：用什么检验？目标。问题：非最优的特征为何？第17页，讲稿共85张，创作于星期日3.寻找更好的基可行解 由于基可行解与基对应，即寻找一个新的基可行解，相当于从上一个基B0变换为下一个新的基B1，因此，本步骤也称为基变换。（基变换）进基出基第18页，讲稿共85张，创作于星期日 以例1为例，可按上述单纯形法的步骤求出其最优解，其大致的过程如下。（1）先将模型化为标准型(2)确定初始基可行解、检验第19页，讲稿共85张，创作于星期日第20页，讲稿共85张，创作于星期日第21页，讲稿共85张，创作于星期日第22页，讲稿共85张，创作于星期日（3）换基、计算下一个基可行解、再检验，直至最优问题：当模型规模较大时，计算量很大。事实上，单纯形法的实现是在单纯形表上完成的。第23页，讲稿共85张，创作于星期日练习：对于下面的线性规划（1）用图解法求解；（2）将模型化为标准型；（3）用单纯形法步骤求出其最优解，并指出求 解过程中每一个基可行解相当于可行域的 哪一个角点。第24页，讲稿共85张，创作于星期日第25页，讲稿共85张，创作于星期日第26页，讲稿共85张，创作于星期日第27页，讲稿共85张，创作于星期日第28页，讲稿共85张，创作于星期日第29页，讲稿共85张，创作于星期日第30页，讲稿共85张，创作于星期日第31页，讲稿共85张，创作于星期日第32页，讲稿共85张，创作于星期日三、单纯形表 单纯形表是基于单纯形法的步骤设计的计算格式，是单纯形法的具体实现。回顾单纯形法步骤第33页，讲稿共85张，创作于星期日单纯形表的主要结构：问题：第一张表的B-1=？单位阵I。检验数的公式是什么？第34页，讲稿共85张，创作于星期日第35页，讲稿共85张，创作于星期日第36页，讲稿共85张，创作于星期日第37页，讲稿共85张，创作于星期日第38页，讲稿共85张，创作于星期日第39页，讲稿共85张，创作于星期日第40页，讲稿共85张，创作于星期日例5：用单纯形法求解例1问题：标准模型的A中是否含I？松弛变量系数恰好构成I。第41页，讲稿共85张，创作于星期日 中表示进基列与出基行的交叉元，下一张表将实行以它为主元的初等行变换（称高斯消去）。方法是：先将主元消成1，再用此1将其所在列的其余元消成0。第42页，讲稿共85张，创作于星期日第43页，讲稿共85张，创作于星期日第44页，讲稿共85张，创作于星期日第45页，讲稿共85张，创作于星期日第46页，讲稿共85张，创作于星期日第47页，讲稿共85张，创作于星期日第48页，讲稿共85张，创作于星期日第49页，讲稿共85张，创作于星期日第50页，讲稿共85张，创作于星期日第51页，讲稿共85张，创作于星期日第52页，讲稿共85张，创作于星期日第53页，讲稿共85张，创作于星期日第54页，讲稿共85张，创作于星期日第55页，讲稿共85张，创作于星期日第56页，讲稿共85张，创作于星期日第57页，讲稿共85张，创作于星期日第58页，讲稿共85张，创作于星期日第59页，讲稿共85张，创作于星期日第60页，讲稿共85张，创作于星期日第61页，讲稿共85张，创作于星期日第62页，讲稿共85张，创作于星期日第63页，讲稿共85张，创作于星期日第64页，讲稿共85张，创作于星期日第65页，讲稿共85张，创作于星期日第66页，讲稿共85张，创作于星期日 （请解释其实际意义）第67页，讲稿共85张，创作于星期日第68页，讲稿共85张，创作于星期日第69页，讲稿共85张，创作于星期日第70页，讲稿共85张，创作于星期日第71页，讲稿共85张，创作于星期日练习：用单纯形法求解下面的线性规划第72页，讲稿共85张，创作于星期日 注：1.表上每一列的含义：2.每张表上B-1的位置在哪？对应于初表中I 的位置。第73页，讲稿共85张，创作于星期日 第74页，讲稿共85张，创作于星期日 例6：填表：第75页，讲稿共85张，创作于星期日练习：用单纯形法求解下面的线性规划第76页，讲稿共85张，创作于星期日 问题：本题的单纯形终表检验数有何特点？非基变量x2 的检验数等于零。第77页，讲稿共85张，创作于星期日注：（1）解的几种情况在单纯形表上的体现（Max型）：-唯一最优解：终表非基变量检验数均小于零；-多重最优解：终表非基变量检验数中有等于零的；-无界解：任意表有正检验数相应的系数列均非正。（2）Min型单纯形表与Max型的区别仅在于：检验数反号，即 -令负检验数中最小的对应的变量进基；-当检验数均大于等于零时为最优。第78页，讲稿共85张，创作于星期日 几个定理n定理1 若若线线性性规规划划问问题题存存在在可可行行域域，则则其其可可行行域域n是凸集是凸集 第79页，讲稿共85张，创作于星期日引理 1 线性规划问题的可行解线性规划问题的可行解X=(x1,x2,，xn)T为基可为基可行解的充要条件是行解的充要条件是X的正分量所对应的系数列向量是线性独的正分量所对应的系数列向量是线性独立的。立的。定理定理2 2 线性规划问题的基可行解线性规划问题的基可行解X X对应于可行对应于可行 D D的顶点。的顶点。第80页，讲稿共85张，创作于星期日引理2 若若K是有界凸集，则任何一点是有界凸集，则任何一点XK可表可表示为示为K的顶点的凸组合。的顶点的凸组合。n本引理证明从略，用以下例子说明这引理。n例5 设X是三角形中任意一点，X(1),X(2)和X(3)是三角形的三个顶点，试用三个顶点的坐标表示X(见图1-8)第81页，讲稿共85张，创作于星期日解 任选一顶点X(2)，做一条连线XX(2)；并延长交于X(1)、X(3)连接线上一点X。因X是X(1)、X(3)连线上一点，故可用X(1)、X(3)线性组合表示为nX=X(1)+(1-)X(3)01n又因X是X与X(2)连线上的一个点，故nX=X+(1-)X(2)01n将X的表达式代入上式得到nX=X(1)+(1-)X(3)+(1-)X(2)n=X(1)+(1-)X(3)+(1-)X(2)第82页，讲稿共85张，创作于星期日令 1=,2=(1-),3=(1-)n这就得到nX=1X(1)+2X(2)+3X(3)nii=1,0i1第83页，讲稿共85张，创作于星期日 定理 3 若可行域有界，线性规划问题的目标函若可行域有界，线性规划问题的目标函数一定可以在其可行域的顶点上达到最优。数一定可以在其可行域的顶点上达到最优。第84页，讲稿共85张，创作于星期日感感谢谢大大家家观观看看第85页，讲稿共85张，创作于星期日