运筹学课件2.ppt

1、2.1 LP问题的图解法: 图解法不是解线性规划的主要方法,只是用于说明线性规划解的性质和特点。只能解两个变量问题。 （用图解法求解,线性规划不需要化成标准型） 图解法的步骤： 1、约束区域的确定 2、目标函数等值线 3、平移目标函数等值线求最优值,2 LP问题的几何意义,例1： max z=2x1+ 3x2 x1+ 2x28 4x1 16 x1，x20,有唯一解,画图步骤： 1、约束区域的确定 2、目标函数等值线 3、平移目标函数等值线求最优值,线性规划解的几种可能情况 1、唯一最优解 2、无穷多最优解 3、无可行解 4、无有限最优解(无界解),有无穷多解,两个顶点处达到最优解,例2：,约束

2、条件围不成区域 (又称矛盾方程),无可行解,例3：,Max z=4x1+3x2 -3x1+2x2 6 s.t -x1+3x2 18 x1, x2 0,无有限最优解(无界解),例4：,线性规划的几何特性：,线性规划问题若有最优解,一定在其可行域的顶点达到 (唯一最优解必在一个顶点达到 或无穷多最优解至少在两个顶点达到) ;无最优解(可行域为空集或目标函数无有限极值),图解法得出线性规划问题解的几种情况,问题 : 围成无界区域就不能有唯一解吗?,列向量 x=(x1，x2，xn）T为n维列向量。xRn 线性相关 一组向量v1,vn,如果有一组不全为零的系数 1, ,n,使得: 1 v1+nvn=0

3、则称v1,vn 是线性相关的. 线性无关 一组向量v1,vn,如果对于任何数1,n, 若要满足: 1 v1+nvn=0 ,则必有系数 1=n=0,(全为零)则称v1,vn线性无关. 矩阵A的秩 设A为一个mn阶矩阵(mn),若矩阵中最大线性 无关列向量个数为k,则称矩阵A的秩为k,记 为秩(A)=k.,补充线性代数内容:,设线性规划的标准形式： max z=cjxj (1) s.t aijxj=bi i=1,2,m (2) xj0 j=1,2,n (3) 可行域：由约束条件(2)、(3)所围成的区域； 可行解：满足(2)、(3)条件的解X=(x1，x2，xn)T为可行解； 基：设A是约束条件方

4、程组的mn维系数矩阵,其秩为m，B是A中mm阶非奇异子矩阵，则称B为线性规划问题的一个基。 设,2.2 线性规划问题解的概念,基向量、非基向量、基变量、非基变量： 称pj(j=1,2,m） 为基向量，其余称为非基变量向量；与基向量pj(j=1,2,m）对应的xj称为基变量，其全体写成XB=（x1，x2，xm）T；否则称为非基变量，其全体 经常写称XN。,基解：对给定基B,设XB是对应于这个基的基变量 XB=(x1 , x2 , , xm)T； 令非基变量xm+1=xm+2=xn=0，由（2） 式得出的解X=（x1，x2，xm，0，0）T 称为基解。,基可行解：所有决策变量满足非负条件(xj 0

5、)的基解, 称作基可行解。 可行基：基可行解所对应的基称为可行基。,注：基解的数目最多为Cnm个。基可行解的数目一般小于基解的数目; 基解中非零分量的个数小于m个时，基解称为退化解。以后在不声明的情况下，均假设不出现退化情况。,可行解,基解,基可 行解,非可行解,解的关系：,凸集: （直观）图形中连接任意两点的直线全部都在图形区域内,称此图形是凸的.严格数学定义: 设K为一n维欧氏空间的点集,若任意两点x(1),x(2)K,有x=x(1) +(1-)x(2)K，其中0，1，则称K为凸集。,2.3 线性规划问题的几何意义,x1, x2,凸组合 设x(1),x(2),x(k)是n维空间中的k个点,

6、若存在1,2,k (0i1 i=1,2,k 且i=1)使 x=1x(1)+2x(2)+kx(k)成立,则称 x为x(1),x(2),x(k) 的凸组合。 特别，平面上的两点x(1),x(2),连线上任一点x的坐标为 x=x(1)+(1-)x(2) 01. 顶点 设K为凸集,xK并且x不能用K内不同的两点x(1),x(2) (xx(1),xx(2)的凸组合表示,则称x为顶点. 定理1: 线性规划问题若存在可行域,则其必是凸集，亦即 D=XAX=b , xj0 =X , xj0 是 凸集.,凸集性质:,设x(1)x(2)为D内任取两点，则Ax(1)=b,Ax(2)=b,x(1) 0, x(2) 0

7、,令x为线段x(1) ,x(2)上任一点,既有 x=x(1)+(1-)x(2) (01) 则 Ax=Ax(1) + (1-) x(2) (01) =Ax(1)+Ax(2)-Ax(2) =b+bb=b 又因为 x(1) 0, x(2) 0, 01 所以 x 0 即 xD 证毕,证明：线性规划 max z =CX s.t AX=b X0,引理1. 线性规划问题的可行解为基本可行解的充分必要条件是X的正分量所对应的系数列向量是线性独立的. 证明:充分性：已知为线性规划的基本可行解，要证X的正分量所对应的系数列向量线性独立。 因为X为基本解，由定义，其非零分量所对应的系数列向量线性独立；又因为X还是可

8、行解，从而其非零分量全为正。 必要性：已知可行解X的正分量所对应的系数列向量线性独立，欲证X是线性规划的基本可行解。 若向量P1, P2, Pk线性独立,则必有km；当k=m时，它们恰构成一个基，从而X=（x1，x2,xk，00）为相应的基可行解。Km时，则一定可以从其余的系数列向量中取出m-k个与P1, P2, Pk构成最大的线性独立向量组，其对应的解恰为X，所以根据定义它是基可行解，(退化)。,定理2：X是线性规划问题的基可行解的充要条件是它对应于可行域D的顶点。（线性规划问题的基可行解X对应于可行域D的顶点。） 证明：不失一般性，假设基可行解X的前m个分量为正。故 必要性（顶点基可行解，

9、逆否命题）： 由引理1，若X不是基可行解，则其正分量所对应的系数列向量P1,P2,Pm线性相关,即存在一组不全为零的数i,i=1,2,m,（1）,令X(1)=(x1-1),(x2-2), ,(xm-m),0, ,0 X(2)=(x1+1),(x2+2), ,(xm+m),0, ,0 由X(1), X(2) 可以得到 X= ,即X是X(1),X(2)连线的中心. 另一方面,当充分小时,可保证xii0 i=1,2, ,m,即X(1), X(2)是可行解,所以X不是可行域D的顶点.,使得 1P1+ 2P2+ +mPm=0 （2） 用一个0的数乘（2）式在分别与（1）相加和相减，这样得到 (x1-1)

10、P1+(x2-2)P2+(xm-m)Pm=b (x1+1)P1+(x2+2)P2+(xm+m)Pm=b,引理2 若K是有界凸集,则任何 一点XK可表示为K的顶点的凸组合. 证明略。,充分性（基可行解顶点，逆否命题）： X不是可行域的顶点,故可在可行域内找到两个不同的点x(1),x(2)，使得 x=x(1)+(1-)x(2), 01 反设X是基可行解,故可设向量组P1Pm线性独立. 由于x(1),x(2)是可行域的两点.应满足Pjxj(1)=b与Pjxj(2)=b 将这两式相减,即得 Pj(xj(1)-xj(2)=0 因X(1)x(2),所以上式系数(xj(1)-xj(2)不全为零,故向量P1,P2,Pm组线性相关与假设矛盾.即X不是基可行解.,定理3 若可行域有界,线性规划问题的目标函数一定可以在其可行域的顶点上达到最优.,证：设X(1),X(2), ,X(k)是可行域的顶点,若X(0)不是顶点且目标函数在X(0)处达到最优 z*=CX(0)(不妨设标准型是z*=maxz),则X(0)可以用顶点表示为 X(0)=iX(i) i0,i=1 记X(1),X(2), ,X(k