《《运筹学教学资料》运筹学第1章第3-4节.ppt》由会员分享，可在线阅读，更多相关《《运筹学教学资料》运筹学第1章第3-4节.ppt（42页珍藏版）》请在三一办公上搜索。
1、第一章 线性规划,1 线性规划问题及其模型,2 线性规划问题几何意义,3 单纯形法,4 单纯形法计算步骤,5 单纯形法进一步讨论,6 应用举例,本节学习要点：1、重点掌握单纯形的变换过程及基本思路；2、了解单纯形解的判别。,先找出一个基可行解，判断其是否为最优解；如为否，则转换到相邻的基可行解，并使目标函数值不断增大；一直找到最优解为止。,定义：两个基可行解称为相邻的，如果它们之间变换且仅变换一个基变量。,单纯形法迭代的基本思路是：,3 单纯形法,单纯形法的步骤,确定初始基本可行解,检验其是否最优？,寻找更好的基本可行解,是,否,STOP,方法前提：模型化为标准型,3 单纯形法,3.1 引例：
2、,例：,3 单纯形法,为基变量,没有安排生产1、2两种产品，资源没有利用，所以利润为零。即这个基可行解不是极点。分析：如果将非基变量转变成基变量，目标函数就可能增大。如果目标函数中还有正系数的非基变量存在，则说明目标函数还有增大的可能。,3 单纯形法,将正系数最大的那个非基变量换入（即该变量0）,以获得该产品的最大产量和对应的最大利润。,即x2=6时可以使约束条件不被破坏。而此时x5=0，,不再适合做基变量，所以将其用x2换出，因此得到：,3 单纯形法,同理：,3 单纯形法,此时的目标函数为：,函数中的x1，仍然没有利用，其系数仍然为正数，说明目标还有增长的余地，该基可行解仍不是最优解，下一步
3、将x1换入基变量中。,即x1=2时可以使约束条件不被破坏。而此时x3=0，,不再适合做基变量，所以将其用x1换出，因此得到：,3 单纯形法,3 单纯形法,此时的目标函数为：,函数中所有非基变量的系数都是负数，说明如果想要得到利润的增加，就需要对“不存在的、没有利用的”资源付出代价，这是不现实的，所以求解停止。也就是说，生产x1 2吨，生产x2 6吨，可以得到最的利润36万元。这个结果与前面图解法的结果相同。,该例子是一个二维的规划问题，但是在加入松弛变量x3 x4 x5之后就变成了高维的规划问题。这时可以想象，满足所有约束条件的可行域是高维空间的凸多面体，基可行解就是凸多面体上的顶点。下面将前
4、面所使用的方法进行总结归纳，推导求解一般线性规划问题的基本方法单纯形算法。,3 单纯形法,给定一个初始基可行解,对线性规划问题,则基可行解可写成,对应的 A=(B,N)，,3.2 解的判别定理,3 单纯形法,max,称为基 所对应的典式。,3 单纯形法,max,3 单纯形法,线性规划典式(proper form)的分量表示：,重要！重要！,max,3 单纯形法,1）基可行解,注：给出基 后,由其典式可得出结论,2）其对应目标函数值z0=CBB-1b,利用这组数来判断X0是否是最优解。,3 单纯形法,定理1 最优解判定准则,如果对一切 则 X 0是线性规划问题的最优解。,如果对一切 则 X 0是
5、线性规划问题的唯一最优解。,如果对一切 并且存在某个,则线性规划问题有无穷多最优解。,如果存在一个 并且对一切,则线性规划问题无最优解(也称无界解，即最优值为无穷)。,设 X 0 是基可行解，则：,3 单纯形法,定理2（基可行解改进定理）,证明 略。,设X0是基可行解，典式如前所示，如果,存在一个；,中至少有一个正分量；,所有的;则一定存在另一个基可行解X1,使,3 单纯形法,第一章 线性规划,1 线性规划问题及其模型,2 线性规划问题几何意义,3 单纯形法,4 单纯形法计算步骤,5 单纯形法进一步讨论,6 应用举例,1947年，提出求解线性规划的单纯形法。,单纯形算法的直接思想：,从一个基可
6、行解开始，通过基变换，到另一个基可行解，逐步达到最优解的过程。基变换是通过迭代法实现的。,4.1 单纯形算法计算步骤,Step1 求初始基可行解。找出一个初始基可行解X0，写出X0相应的典式.,3）进行基变换.得到新的基可行解 X1及其典式，转step 2.,Step2 最优性检验。如果所有非基变量 xj 的检验数都不大于0，则X0是最优解，计 算结束；若存在某个检验数k0，其所有的ik0，则线性规划问题无最优解，计算结束；否则转至step 3.,Step3 进行基变换。,1）确定换入变量.规则,找最大的其对应的 xk 就是换入变量.,2）确定换出变量.规则,计算确定 xl 是换出变量.,4.
7、1 单纯形算法计算步骤,找初始基可行解X0及可行基B,单纯形法计算框图,j 0?,写出最优解与最优值,停,是否有ik0,无界解,N,确定换出变量x l,以kl为主元作基变换,停,N,Y,Y,4.1 单纯形算法计算步骤,基变换示例,如果存在某个,使,并且至少有一个,设基（S 为基变量下标集合）的典式为：,基变换公式,令,这表示xk为换入变量（成为基变量）,xl为非基变量。得一个新基，其中：,设新基 的典式为：,4.1 单纯形算法计算步骤,新、旧两基典式的基变换公式为：,1）将主元素所在 l 行除以主元素，既有,2）将刚计算得到的第 l 行乘上()加到典式的第 i 行,3）,4.1 单纯形算法计算
8、步骤,例1.利用单纯形算法求解下面的线性规划问题。,4.1 单纯形算法计算步骤,解：本问题有一个明显的可行基x3、x4、x5，它的典式为：,非基变量x1、x2的检验数为3、5，基可行解X0=(0,0,4,12,18)T不是最优解，取检验数最大者，x2作为换入变量,再确定换出变量，由于：,故x4为换出变量，得到一个新可行基x3,x2,x5，,其典式为,由于x1的检验数为30，故基可行解X1=(0,6,4,0,6)T不是最优解，让x1为换入变量。,令,所以 x5 为换出变量，又得一个新基x3,x2,x1,非基变量x4、x5的检验数是-3/2、-1，故X2=(2,6,2,0,0)T是最优解，并且是唯
9、一最优解。,，其典式为：,基可行解与图解法顶点的对应关系,图示：,X0=(0,0,4,12,18)T,X1=(0,6,4,0,6)T,X2=(2,6,2,0,0)T,4.1 单纯形算法计算步骤,4.2 单纯形表,单纯形表(simple tableau)是为单纯形算法而设计的一种计算表，其功能类似于方程组的增广矩阵，易于进行基变换运算。,设可行基 的典式为：,将式(1.4)与(1.5)组成一个m+1个方程、n+1个变量的方程组为,4.2 单纯形表,此方程组的增广矩阵为：,其中基变量 的系数构成单位矩阵，z是 一个不参与基变换的变量。,可设计单纯形表,表4-1单纯形表,例1,建立单纯形表,注2：min问题如果给定的线性规划问题是要求目标函数达到最小，可以直接用单纯形计算，而不必先化成标准形中要求目标函数的极大值。此时，要求检验数 时，基可行解才是最优解；迭代时，选负检验数最小者作为换入变量。,注1：上面的计算过程也可以用基变换公式来实现。,单纯形算法特别适合计算机实现。,思考题：编程实现单纯形算法。,4.2 单纯形表,解：建立单纯形表如下：,例2 求解线性规划问题：,4.2 单纯形表,4.2 单纯形表,最优解是，最优值为 z=-11.,4.2 单纯形表,每一列的含义？每个表中的B和B-1的查找？,思考题,
