线性规划及单纯形法课件.ppt

《线性规划及单纯形法课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三节单纯形法原理一、线性规划规划问题的解的概念（一）线性规划问题标准型（1）可行解：满足上述约束条件(1.7),(1.8)的解X=(x1,…,xn)T，称为线性规划问题的可行解。全部可行解的集合称为可行域。（2）最优解：使目标函数(1.6)达到最大值的可行解称为最优解。（3）基：设A为约束方程组(1.7)的m×n阶系数矩阵，（设n>m），其秩为m，B是矩阵A中的一个m×m阶的满秩子矩阵，称B是线性规划问题的一个基。不失一般性，设B中的每一个列向量Pj(j=1,…,m)称为基向量，与基向理Pj对应的变量xj称为基变量。线性规划中除基变量以外的变量称为非基

2、变量。（4）基解：在约束方程组(1.7)中，令所有非基变量为xm+1=xm+2=…=xn=0零，以因为有

3、B

4、≠0，根据克莱姆法则，由m个约束方程可解出m个基变量的唯一解XB=(x1,…,xm)T。将这个解加上非基解中变量取0的值有X=（x1,x2,…,xm,0,0,…,0）T，称X为线性规划问题的基解。显然在基解中变量取非零值的个数不大于方程数m，故基解的总数不超过Cnm个。（5）基可行解：满足变量非负约束条件(1.8)的基解称为基可行解。（6）可行基：对应基可行解的基称为可行基。可行解基解基可行解（二）可行解、基解与基可行解的关系线性规划的基矩阵、基

5、变量、非基变量==目标函数约束条件行列式≠0基矩阵右边常数（三）线性规划的基本概念的直观描述（四）求出下列线性规划问题的所有基解、基可行解该线性规划问题的标准型为：基变量x1、x2、x3，非基变量x4、x5、x6基解为（x1，x2，x3，x4，x5，x6）=（5，3，1，0，0，0）是基可行解，表示可行域的一个极点。目标函数值为：z=20基变量x1、x2、x4，非基变量x3、x5、x6基解为（x1，x2，x3，x4，x5，x6）=（27/5，12/5，0，2/5，0，0）是基可行解，表示可行域的一个极点。目标函数值为：z=18基变量x1、x2、x5，非基

6、变量x3、x4、x6基解为（x1，x2，x3，x4，x5，x6）=（6，3，0，0，-3，0）是基解，但不是可行解，不是一个极点。基变量x1、x2、x6，非基变量x3、x4、x5基解为（x1，x2，x3，x4，x5，x6）=（3，4，0，0，0，4）是基可行解，表示可行域的一个极点。目标函数值为：z=18基变量x2、x3、x4，非基变量x1、x5、x6基解为（x1，x2，x3，x4，x5，x6）=（0，21/2，27/2，-30，0，0）是基解，但不是可行解。基变量x1、x2、x3，非基变量x4、x5、x6基解为（x1，x2，x3，x4，x5，x6）=（

7、0，3，6，0，15，0）是基可行解，表示可行域的一个极点。目标函数值为：z=15基变量x1、x2、x3，非基变量x4、x5、x6基解为（x1，x2，x3，x4，x5，x6）=（0，11/2，-3/2，0，0，10）是基解但不是可行解。例：设有一标准的线性规划问题的约束条件如下：2x1+x2+x4=7x2+x3=3x1,x2,x3,x40已知下列各点均满足以上的两个方程：(1)(0,7,-4,0)T,(2)(2,3,0,0)T,(3)(1,0,3,5)T(4)(2.5,2,1,0)T,(5)(0,3,0,4)T二、凸集及其顶点1凸集设C是n维空间中的一

8、个点集。若对任意n维向量X1C，X2C，且X1X2，以及任意实数（01），有X=X1+(1-)X2C则称C为n维空间中的一个凸集。点X称为点X1和X2的凸组合。以上定义有明显的几何意义，它表示凸集C中的任意两个不相同的点连线上的点（包括这两个端点），都位于凸集C之中。2顶点凸集C中满足下述条件的点X称为顶点：如果C中不存在任何两个不同的点X1，X2，使X成为这两个点连线上的一个点。或者这样叙述：对任何X1C，X2C，不存在X=X1+(1-)X2C（01），则称X是凸集C的顶点。三、几个定理的证明定理1若线性规划问题存在

9、可行解，则问题的可行域是凸集。证：设C为满足约束条件的集合，X1=（x11,x12,…,x1n)T,X2=(x21,x22,…,x2n)T为C内任意两点，即X1C，x2C，将X1，X2代约束条件有：X1，X2连线上任意一点可以表示为：将（1.9）代入（1.10）得：即：引理线性规划问题的可行解X=（x1,x2,…xn)为基可行解的充要条件是X的正分量所对应的系数列向量线性独立的。证：（1）必要性（结论条件）由基可行解的定义显然成立。（2）充分性。（条件结论）若向量P1,P2,…,Pk线性独立，则必有k≤m.当k=m时，它们恰好构成一个基，从而X=

10、(x1,x2,…,xm,0,0,..,0)为相应的基可行解。当K