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

第1章线性规划及其扩展,第1节线性规划问题及其数学模型第2节线性规划问题的几何意义第3节单纯形法第4节单纯形法的计算步骤第5节单纯形法的进一步讨论第6节应用举例,1.3线性规划问题的标准形式,(其中bi0(i=1,2,.,m),称下列形式为线性规划问题的标准形式:,目标函数求极大,约束条件为等式,决策变量及右边常数项为非负,线性规划问题的几种表示形式,用向量表示为：,则标准形式的矩阵表示：,若令,A称为系数矩阵,b称为资源向量,C称为价值向量,X称为决策变量向量,用矩阵表示为：,非标准形式化为标准形式的方法,1.当目标函数为求极小值,即minz=c1x1+c2x2+.+cnxn,因为求minz等价于max(-z),故可令,则目标函数化为:,2.当右端项bim)其秩为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,定理:DxRn|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且对应的列向量Pj0时，该线性规划问题有无界解；,(4)对线性规划问题无可行解的判别将在后面讨论。,(2)当存在某个j0且对应的列向量Pj中有正分量时，说明目标函数值还可以增大，需要进行基变换；,第4节单纯形法的计算步骤,一.单纯形法的计算步骤,第一步：求初始基可行解，列出初始单纯形表,首先写出关于价值系数的表：（非单纯形表）,一.单纯形法的计算步骤（2）,将基变量下方的价值系数通过变换化为零，得初始单纯形表,一.单纯形法的计算步骤（3）,第二步：最优性检验,(1)当所有的j0时，现行基可行解为最优解；当所有的j0且对应的列向量Pj0时，该线性规划问题有无界解；,(3)当存在某个j0且对应的列向量Pj中有正分量时，说明目标函数值还可以增大，需要进行基变换。,一.单纯形法的计算步骤(4),第三步：换基迭代,(1)确定进基变量,选择检验数最大的非基变量为进基变量,k=maxj|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,1010-1/2,16,40010,3,0,1,0,0,1/4,-9,2,0,0,0,-3/4,T(B2),T(B2),x1,x4,x2,-z,2,1010-1/2,8,00-412,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,1001/40,4,00-21/21,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,10100,3,01010,2,1,0,0,-2,1,-6,1,0,0,-2,0,T(B2),二单纯形法例2(2),T(B2),x3,x2,x1,-z,2,0012-1,3,01010,2,1,0,0,-2,1,-8,0,0,0,0,-1,T(B3),二单纯形法例2(3),二单纯形法例2(4),在单纯形终表中，x4,x5为非基变量，非基变量检验数均小于等于零，且4=0,5=-10时，始终选取下标值为最小的变量为进基变量；,(2)当计算值出现两个以上相同的最小比值时，始终选取下标值为最小的变量为出基变量。,按最小比值来确定出基变量时，有时会出现两个以上相同的最小比值，从而使下一个单纯形表中出现一个或多个基变量等于零的退化解。将使得多个基可行解对应同一顶点，可能出现迭代计算的循环。,注：目标函数求最小的情况,(1)化成标准型，目标函数求极大；,(2)有些书中规定目标函数的极小化作为线性规划的标准形式，这时只需以所有检验数j0作为判别表中解是否是最优的标志。,(1)当所有的j0时，现行基可行解为最优解；当所有的j0时，该线性规划问题有唯一最优解；当所有的j0，且对某个非基变量xk，有k=0,该线性规划问题有无穷多最优解。(2)当存在某个j0且对应的列向量Pj0时，该线性规划问题有无界解；,确定进基变量,选择检验数最小的非基变量为进基变量,k=minj|j0,j=1,2,.,n,则xk为进基变量,确定出基变量,根据下列原则确定出基变量,则l所对应的基变量xl为出基变量,元素alk为轴心项(或称为主元素),以alk为轴心项进行换基迭代