线性规划图解法几何意义.ppt

第1章 线性规划及其扩展,第1节 线性规划问题及其数学模型 第2节 线性规划问题的几何意义 第3节 单纯形法 第4节 单纯形法的计算步骤 第5节 单纯形法的进一步讨论 第6节 应用举例,1.3线性规划问题的标准形式,(其中bi0(i=1,2,.,m),称下列形式为线性规划问题的标准形式:,目标函数求极大,约束条件为等式,决策变量及右边常数项为非负,线性规划问题的几种表示形式,用向量表示为：,则标准形式的矩阵表示：,若令,A称为系数矩阵,b称为资源向量,C称为价值向量,X称为决策变量向量,用矩阵表示为：,非标准形式化为标准形式的方法,1.当目标函数为求极小值,即 min z=c1x1+c2x2+.+cnxn,因为求min z 等价于max (-z),故可令,则目标函数化为:,2.当右端项 bi0时,只需将等式或不等式两端同乘(-1),则右端项必大于0,3.当约束条件为 ai1x1+ai2x2+.+ainxnbi,引入一个变量xn+i0,可使成为等式即 ai1x1+ai2x2+.+ainxnxn+ibi,变量xn+i称为松弛变量,4. 当约束条件为ai1x1+ai2x2+.+ainxnbi时,则引入一个变量xn+i0,可使不等式成为等式,即 ai1x1+ai2x2+.+ainxnxn+ibi,变量xn+i称为剩余变量,5.当变量xi为无约束的变量时,则我们引入两个变量,令:,将其代入线性规划模型中,6.当变量xi0时,则令,再代入线性规划模型中,例3 将例1的数学模型化为标准形,该线性规划问题加入三个松驰变量x3,x4,x50后：,例4 将下述线性规划问题化为标准形,解：分以下步骤进行处理,(1)令z= -z，把求min z 改为求max z; (2) 在第一个约束不等式号的左端加入松弛变量x4； (3) 在第二个约束不等式号的左端减去剩余变量x5； (4)用x6-x7替换x3，其中x6，x70,即可得到该问题的标准形.,得原问题的标准形为：,1.4 线性规划问题的解的概念,1.可行解 2.基 3.基可行解 4.可行基,一. 线性规划问题解的概念,线性规划问题,1.可行解:,满足线性规划问题的约束条件的解X=(x1，x2，.，xn ) T称为线性规划问题的可行解。,2.可行域:,全部可行解构成的集合称为可行域。,3.最优解:,使目标函数达到最优的可行解称为最优解。,4.基:,设系数矩阵Amn(nm)其秩为m,B是矩阵A中的一个mm阶的满秩子矩阵,称B是线性规划问题的一个基。,一. 线性规划问题解的概念（2）,=(P1,P2,.,Pm),B中的每一列向量Pj(j=1,2,.m)称为基向量,基向量：,与基向量Pj的对应的变量xj 称为基变量,基变量：,非基变量：,线性规划中的其余变量称为非基向量,5.基解,设X是（LP）的约束方程AX=b的一个解，B是一个基，若X中对应基B的非基变量取值全为零，则称X为(LP)关于基B的基解，记作X(B),不妨设基为,基解的个数不会超过 个,一. 线性规划问题解的概念（3）,可证明:一个基可以而且唯一地确定一个基解.,6.基可行解：,若基解X(B)满足非负条件X(B)0，则称基解X(B)为基可行解,7.基最优解：,若基可行解X(B)是(LP)的最优解,则称X(B)为(LP)的基最优解.,最优基：,基最优解对应的可行基B称为最优基.,可行基：,基可行解对应的基B称为可行基.,注:基解没有X0的限制,故基解不一定是可行解.,X(B)=,一. 线性规划问题解的概念（4）,8.退化解：,若基本可行解X的所有基变量的值均大于0，则称X是非退化的，否则称X为退化的。,若(LP)的所有基本可行解都是非退化的, 则称线性规划问题是非退化的.,二. 例题,考虑线性规划问题：,约束方程的系数矩阵A,很显然A中的后3列是线性无关的，它们构成一个基,基B1对应的变量x3,x4,x5是基变量, x1,x2是非基变量,二. 例题（2）,若令：,得,该解是对应B1的基解，它是基可行解，B1是可行基；,如取,是（LP）的一个基，,若令：,基B2对应的变量x1,x2,x3是基变量， ,x4,x5是非基变量,得,该解是对应B2的基解，它不是基可行解，B2不是可行基；,三. 线性规划问题解的关系图,AX=b的解,基解,若非基变量为0,基可行解,基最优解,B是A的m阶子矩阵,基B,若|B|0,可行基B,当B-1b0,最优基B,若基变量取非负,若对应目标函数 值最优,非可行解,三. 线性规划问题解的关系图（2）,可行解,基可行解,基解,基,可行基,最优基,第2节 线性规划问题的几何意义,2.1 基本概念 2.2 几个定理,一.凸集与顶点,凸集:,如果集合K中任意两个点X(1),X(2),其连线上的所有点也都是集合K中的点,则称集合K为凸集.,或K=X|X=X(1)+(1-)X(2), X(1)K,X(2)K,01,定理: D xRn| Ax=b,x0是凸集,顶点:凸集K中满足下列条件的点X称为顶点:如 果K中不存在任何两个不同的点X1,X2,使X 成为这两个点连线上的一个点.,定理: 有限个凸集的交集还是凸集,凸组合:设,是n维欧氏空间中的k个点,则称X是 的凸组合,凸集的概念：,凸集,凸集,不是凸集,顶点,不是凸集,二.几个基本定理,定理1,若线性规划问题存在可行解,则问题的可行域是凸集.,定理2,若线性规划问题有非零可行解，则其必有基可行解。,定理4,若线性规划问题有最优解，一定存在一个基可行解是最优解。,定理3,线性规划问题的基可行解X对应线性规划问题可行域(凸集)的顶点.,引理1,线性规划的可行解X(x1,x2,xn)T为基可行解的充要条件是X的正分量所对应的系数列向量是线性无关的。,第3节 单 纯 形 法,一. 单纯形法迭代的基本思想,开始于某一个可行基及其对应的基可行解，从一个基可行解迭代到另一个基可行解，并且使目标函数值不断增大，经过有限步必能求得线性规划问题的最优解或者判定线性规划问题无有界的最优解（无界解）。,二. 单纯形法引例,考虑线性规划问题：,约束方程的系数矩阵A,很显然A中的后3列是线性无关的，它们构成一个基,基B对应的变量x3,x4,x5是基变量，则,二. 单纯形法引例（2）,即：,将它们代入目标函数中得,令非基变量x1=x2=0,得目标值 z0 一个基可行解 X(0)(0,0,8,16,12),为了使目标函数能更大，让x2变成基变量，原基变量 的x3，x4，x5要有一个变为非基变量,当x1=0,由最上式得,从上式可看出，当x2=3仍可保证所有变量非负， 并使目标函数增大,二. 单纯形法引例（3）,为了得到以x3,x4,x2为基变量的一个基可行解，则对左边方程中的x2与x5互换,得,再令非基变量x1=x5=0,得目标值 z9 一个基可行解 X(0)(0,3,2,16,0),为了使目标函数能更大，让x1变成基变量，原基变量 的x3，x4，x2要有一个变为非基变量,目标函数变为,二. 单纯形法引例（4）,这样如此下去，可得,X(2)(2,3,0,8,0),为了使目标函数能更大，让x1变成基变量，原基变量 的x3，x4，x2要有一个变为非基变量,此时目标函数变为,X(3)(4,2,0,0,4),由于目标函数中的变量系数都小于等于0， 所以 X(3)（4,2,0,0,4)为最优解， 最优值z14,下面从几何角度分析一下最优解的寻求过程：,几何意义：顶点转移，目标增大,三. 单纯形法原理,1.确定初始基可行解：,对标准型的LP问题,在约束条件(1.1)的变量的系数矩阵中总会存在一个单位矩阵。,(2)当线性规划的约束条件都为号时，其松弛变量对应的系数列向量构成的矩阵即为单位阵；,(3)当线性规划的约束条件为或的情况，引入人工变量后也可实现。,(1)系数矩阵中可以直接观察得到一个单位子矩阵；,三. 单纯形法原理（2）,2. 从一个基可行解转换为相邻的基可行解：,定义：两个基可行解称为相邻的，如果他们之间变换且仅变换一个基变量。,设初始基可行解为：,可知：,其对应的系数矩阵的增广矩阵为：,三. 单纯形法原理（3）,易得：,(1.3)+(1.4) (0), 得,令：,显然：,为使X(1)成为可行解，令：,可证明:将(1.6)式代回到X(1)中,X(1) 为基可行解，此时完成了从一个基可行解到另一个与其相邻的基可行解的转换。,三. 单纯形法原理（4）,证明：将与变量 x1,xl-1,xl+1,xm,xj对应的列向量，经重新排列后加上b列有如下形式：,因为 P1,P2, ,Pl-1， Pj,Pl+1,Pm 线性无关，故X(1)为基可行解。,三. 单纯形法原理（5）,3.最优性检验与解的判别：,将2中的基可行解X(0)与X(1)分别代入目标函数，得,称为检验数,三. 单纯形法原理（6）,(1)当所有的j0时 ，现行基可行解为最优解； 当所有的j0时 ，该线性规划问题有唯一最优解； 当所有的j0，且对某个非基变量xk，有k=0,该线性规划问题有无穷多最优解。,(2)当存在某个j0且对应的列向量Pj 0时，该线性规划问题有无界解；,(4)对线性规划问题无可行解的判别将在后面讨论。,(2)当存在某个j0且对应的列向量Pj 中有正分量时，说明目标函数值还可以增大，需要进行基变换；,第 4 节 单 纯 形 法的计算步骤,一. 单纯形法的计算步骤,第一步：求初始基可行解，列出初始单纯形表,首先写出关于价值系数的表：（非单纯形表）,一. 单纯形法的计算步骤（2）,将基变量下方的价值系数通过变换化为零，得初始单纯形表,一. 单纯形法的计算步骤（3）,第二步：最优性检验,(1)当所有的j0时 ，现行基可行解为最优解； 当所有的j0时 ，该线性规划问题有唯一最优解； 当所有的j0，且对某个非基变量xk，有k=0,该线性规划问题有无穷多最优解。,(2)当存在某个j0且对应的列向量Pj 0时，该线性规划问题有无界解；,(3)当存在某个j0且对应的列向量Pj 中有正分量时，说明目标函数值还可以增大，需要进行基变换。,一. 单纯形法的计算步骤(4),第三步：换基迭代,(1)确定进基变量,选择检验数最大的非基变量为进基变量,k=max j| j0,j=1,2,.,n,则xk为进基变量,(2)确定出基变量,根据下列原则确定出基变量,则l所对应的基变量xl为出基变量,元素alk为轴心项(或称为主元素),(3)以alk为轴心项进行换基迭代,即利用矩阵的初等行变换,把元素alk所在的列化为单位向量.得到新的单纯形表,一. 单纯形法的计算步骤（5）,第四步：重复第二、三步，一直到计算结束为止。,二单纯形法 例1(1),例 用单纯形法解下列线性规划,解:,将原问题化为标准形为：,得单纯形初表为:,二单纯形法 例1(2),T(B1),x3,x4,x2,-z,2,1 0 1 0 -1/2,16,4 0 0 1 0,3,0,1,0,0,1/4,-9,2,0,0,0,-3/4,T(B2),T(B2),x1,x4,x2,-z,2,1 0 1 0 -1/2,8,0 0 -4 1 2,3,0,1,0,0,1/4,-13,0,0,-2,0,1/4,T(B3),二单纯形法 例1(3),T(B3),x1,x5,x2,-z,4,1 0 0 1/4 0,4,0 0 -2 1/2 1,2,0,1,1/2,-1/8,0,-14,0,0,-3/2,-1/8,0,T(B4),二单纯形法 例1(4),二单纯形法 例1(4),在单纯形终表中，x3,x4为非基变量，所有非基变量检验数均小于零，故该线性规划问题有唯一最优解X*=(4,2,0,0,4)T ，最优值为 Z*=14。,二单纯形法 例2(1),例2: 用单纯形法解下列线性规划,解:,将原问题化为标准形为：,得单纯形初表为:,T(B1),x3,x2,x5,-z,4,1 0 1 0 0,3,0 1 0 1 0,2,1,0,0,-2,1,-6,1,0,0,-2,0,T(B2),二单纯形法 例2(2),T(B2),x3,x2,x1,-z,2,0 0 1 2 -1,3,0 1 0 1 0,2,1,0,0,-2,1,-8,0,0,0,0,-1,T(B3),二单纯形法 例2(3),二单纯形法 例2(4),在单纯形终表中，x4,x5为非基变量，非基变量检验数均小于等于零，且4=0,5=-10;故该线性规划问题有无穷多最优解。,注：在上述单纯形终表中，以x4为进基变量，按照极小化原则确定出基变量x3，进行基变换，可得该线性规划问题的另一个最优解。,T(B3),x4,x2,x1,-z,1,0 0 1/2 1 -1/2,2,0 1 -1/2 0 1/2,4,1,0,1,0,0,-8,0,0,0,0,-1,T(B4),最优解X* =(2,3,2,0,0)T,最优值 Z*=8,六单纯形法举例2(5),最优值 Z*=8,最优解X*= (4,2,0,1,0)T,开始,判断所有检验数是否小于等于0,得到最优解,构造单纯形表,NO,输入,结束,Yes,是否存在某个大于0的检验数所对应的列的元素全小于等于0？,原问题为无界解,换基迭代,选择出基变量,Yes,选择进基变量,NO,单纯形法的框图表示为如下:,注：退化情形的处理,为避免出现计算的循环，1947年勃兰特（Bland）提出了一个简单有效的规则：,(1)当存在多个j0时，始终选取下标值为最小的变量为进基变量；,(2)当计算值出现两个以上相同的最小比值时，始终选取下标值为最小的变量为出基变量。,按最小比值来确定出基变量时，有时会出现两个以上相同的最小比值，从而使下一个单纯形表中出现一个或多个基变量等于零的退化解。将使得多个基可行解对应同一顶点，可能出现迭代计算的循环。,注：目标函数求最小的情况,(1) 化成标准型，目标函