线性规划解的概念及单纯形法ppt课件.ppt

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

1、第二章线性规划建模及单纯形法主要内容线性规划问题及其数学模型线性规划解的概念线性规划的单纯形法单纯形法的进一步讨论线性规划应用——建模1可行解、可行解集（可行域）最优解、最优值基、基变量、非基变量基本解、基本可行解可行基、最优基熟悉下列一些解的概念2.线性规划解的概念2解的解析Maxz=2x1+3x2+0x3+0x4+0x5s.t.2x1+2x2+x3=12(A)4x1+x4=16(B)5x2+x5=15(C)x1,x2，x3，x4，x5≥0(D,E)3解的解析可行解满足上述约束条件(A)、(B)、（C)的解x=(x1,x2，x3，x4，x5)T称为线性规划问题的可

2、行解，全部可行解的集合成为可行域。最优解是目标函数z=15达到最大值的可行解x=(3,3，0，4，0)T成为最优解。4解的解析基设A为约束方程组3*5阶系数矩阵P1P2P3P4P522100A=4001005001设B=(P3P4P5)5A中其秩为3,B是A矩阵中的一个3阶的满秩矩阵,称B是线性规划问题的一个基，B中的每一个列向量(如P3P4P5)称为基向量，与基向量对应的变量称为基变量，线性规划中除基变量以外的其他变量称为非基变量。6解的解析基解在约束方程组中，令所有非基变量为0,又因为有B行列式不为0，由各约束方程可解出各基变量的唯一解。将这个解加上非基变量取0

3、的值称为线性规划问题的基解，显然，在基解中变量取非零值的个数不大于方程数，基解的总数不超过20个。7解的解析基可行解满足变量非负约束条件的基解称为基可行解。可行基对应与基可行解的基成为可行基。8(回顾)例2.1问题：工厂应如何安排生产可获得最大的总利润？用图解法求解。解：设变量xi为第i种（甲、乙）产品的生产件数（i＝1，2）。根据前面分析，可以建立如下的线性规划模型：Maxz=1500x1+2500x2s.t.3x1+2x2≤65(A)2x1+x2≤40(B)3x2≤75(C)x1,x2≥0(D,E)9图解法求解线性规划102030405010203040OZ=0

4、Z=25000A（5,25）B（15,10）C（20,0）D（0,25）E(0,0)10(线性规划的基、基本解与基本可行解)在一般情况下，由于图解法无法解决三个变量以上的线性规划问题，对于n个变量的线性规划问题，我们必须用解方程的办法来求得可行域的极点。再来进一步考察前例。例2.8把例2.1的线性规划模型标准化，引入松驰变量x3，x4，x5≥0，得到11Maxz=1500x1+2500x2s.t.3x1+2x2+x3=652x1+x2+x4=403x2+x5=75x1,x2,x3,x4,x5≥0可见：等式约束条件的系数矩阵为12从其中取出不同的三列出来，有C53=1

5、0种取法13其中B1对应的基变量为x1,x2,x3，非基变量为x4,x5令非基变量x4=0,x5=0，则得对应方程组3x1+2x2+x3=652x1+x2=403x2=75得对应基本解该10个方阵中除B4外，其余均为满秩矩阵，故均为线性规划的基。x(1)=(7.5,25,-7.5,0,0)T类似，可得所有基本解为14X(3）=(15,10,0,0,45)TX(2)=(5,25,0,5,0)TX(9)=(0,32.5,0,7.5,-22.5)TX(6）=(65/3,0,0,-10/3,75)TX(1)=(7.5,25,-7.5,0,0)TX(8)=(0,40,-15,

6、0,-45)TX(5）=(20,0,5,0,75)TX(10)=(0,0,65,40,75)TX(7）=(0,25,15,15,0)T不是可行解是可行解,对应顶点A是可行解,对应顶点B是可行解,对应顶点C不是可行解不是可行解不是可行解是可行解,对应顶点D是可行解,对应顶点E15图解法求解线性规划102030405010203040OZ=0Z=25000A（5,25）B（15,10）C（20,0）D（0,25）E(0,0)16上图各约束直线的交点是由以下方法得到：在标准化的等式约束中，令其中的非基变量为零，求出其他基变量的唯一解，得LP问题的基解(x1,x2,x3,x

7、4,x5)T,若其分量全为非负，则该解称为基可行解,对应于线性规划可行域的一个极点（顶点）；若基解中至少有一个分量为负值则该交点不是可行域的极点。2.线性规划解的概念17下面讨论线性规划标准形式的基、基本解、基本可行解的概念。考虑线性规划标准形式的约束条件：Ax=b，x≥0其中A为m×n的矩阵，n>m，秩(A)=m，bRm。在约束等式中，令n维空间的解向量：x=(x1，x2，…，xn)T2.线性规划解的概念（1）线性规划的基：对于线性规划的约束条件Ax=b，x≥018设B是A矩阵中的一个非奇异（满秩）的m×m子矩阵，则称B为线性规划的一个基。用前文的记号，A=