1、线性规划求解（优选）线性规划求解（4）基：设A为线性规划模型约束条件系数矩阵（m n，mn），而B为其mm子矩阵，若|B|0，则称B为该线性规划模型的一个基。（5）基变量：基中每个向量所对应的变量称为基变量。（6）非基变量：模型中基变量之外的变量称为非基变量。（7）基解（基解）：令模型中所有非基变量X非基=0后，由模型约束方程组 n aijxj=bi(i=1,2,m)得到的一组解。j=1（8）基本可行解（基可行解）：在基解中，同时又是可行解的解称为基可行解。（9）可行基：对应于基可行解的基称为可行基。Max z=2x1+3x2 st.x1+x23 x1+2x24 x1,x20 Max z=2x
2、1+3x2+0 x3+0 x4 st.x1+x2+x3=3 x1+2x2+x4=4 x1,x2,x3,x40A=x1 x2 x3 x41 1 1 01 2 0 1可行解：X=(0，0)T，X=(0，1)T，X=(1/2，1/3)T 等。设B=1 0 0 1，令，则|B|=10,令 x1=x2=0，则 x3=3,x4=4，X=(0,0,3,4)T例：x3 x4基变量令 B=1 1 1 0 x1 x3，则令 x2=x4=0，则 x3=-1,x1=4，X=(4,0,-1,0)T|B|=-10,非基本可行解基本可行解标准化复习思考题：1.可行解和可行域有怎样的关系？2.一个标准化LP模型，最多可有多少
3、个基？3.基解是如何定义的？怎样才能得到基解？4.可行解、基解、基可行解三者之间有什么关系？在LP模型中是否一定存在？5.什么是可行基？1.2 线性规划问题的图解方法*利用作图方法求解。例：max z=2x1+3x2 s.t 2x1+2x212 -x1+2x2 8 -4x116 -4x2 12 -x10,x20 x1x222468460Z=6Z=0(4,2)ZmaxAAB唯一解无穷多解无界解无可行解步骤：（1）作平面直角坐标系，标上刻度；（2）做出约束方程所在直线，确定可行域；（3）做出一条目标函数等值线，判定优化方向；（4）沿优化方向移动，确定与可行域相切的点，确定最优 解，并计算最优值。讨
4、论一：模型求解时，可得到如下几种解的状况：（1）唯一最优解：只有一点为最优解点，简称唯一解；（2）无穷多最优解：有许多点为最优解点，简称无穷多解；（3）无界最优解：最优解取值无界，简称无界解；（4）无可行解：无可行域，模型约束条件矛盾。讨论二：LP模型求解思路：（1）若LP模型可行域存在，则为一凸形集合；（2）若LP模型最优解存在，则其应在其可行域顶点上找到；（3）顶点与基本解、基本可行解的关系：复习思考题：1.LP模型的可行域是否一定存在?2.图解中如何去判断模型有唯一解、无穷多解、无界解和无可行解？3.LP模型的可行域的顶点与什么解具有对应关系？4.你认为把所有的顶点都找出来，再通过比较目
5、标函数值大小的方式找出最优解，是否是最好的算法？为什么？具有无穷多解；或者 Pj=B-1PjP1 P2 Pm Pm+1 Pj Pn b引进人工变量，及M非常大正系数，模型转变为XC=(4,2,0,0,4)T对应最终单纯形表的模型x1+x2+x3=3 x1+2x2+x4=4 x1,x2,x3,x401 0 -2 2 -1 0 1 1 -1 1或者，任给X1C，X2 C，X=X1+(1-)X2 C (01)，则C为凸集。令 x2=x4=0，则 x3=-1,x1=4，X=(4,0,-1,0)Tmax z=CBXB+CNXN+0XSxj0 （j=1,2,n)xj0，xsi0 （j=1,2,n;i=1,
6、2,m)由(1)+(2)得 (x1+1)P1+(x2+2)P2+(xm+m)Pm=b对应最终单纯形表的模型第 1 章 线性规划1.3 单纯形法的基本原理（Simplex Method）1.3.1 两个概念：（1 1）凸集：对于集合）凸集：对于集合C C中任意两点连线上的点，若也在中任意两点连线上的点，若也在C C内，则称内，则称 C C为凸集。为凸集。或者或者，任给X1C，X2 C，X=X1+(1-)X2 C (01)，则C为凸集。凸集非凸集（2 2）顶点：凸集中不成为任意两点连线上的点，称为凸集顶点。）顶点：凸集中不成为任意两点连线上的点，称为凸集顶点。或者或者，设C为凸集，对于XC，不存在
7、任何X1C，X2 C，且X1X2，使得X=X1+(1-)X2C，(01)，则X为凸集顶点。XXXXX定理定理1 1：若线性LP模型存在可行解，则可行域为凸集。证明：证明：设 max z=CX st.AX=b X0并设其可行域为C，若X1、X2为其可行解，且X1X2，则 X1C，X2 C，即AX1=b，AX2=b，X10，X20，又 X为X1、X2连线上一点，即 X=X1+(1-)X2C，(01)，AX=AX1+(1-)AX2=b+(1-)b=b,(01)，且 X 0，X C，C为凸集。1.3.2 1.3.2 三个基本定理三个基本定理引理：引理：线性规划问题的可行解X=(x1,x2,xn)T 为
8、基本可行解的充要条件是X的正分量所对应的系数列向量线性独立。证：证：（1）必要性：）必要性：X基本可行解基本可行解X的正分量所对应的系数列向量线性独立的正分量所对应的系数列向量线性独立 可设X=(x1,x2,xk,0,0,0)T，若X为基本可行解，显然，由基本可行解定义可知x1,x2,xk所对应的系数列向量P1,P2,Pk应该线性独立。（2）充分性：）充分性：X的正分量所对应的系数列向量线性独立的正分量所对应的系数列向量线性独立 X为基本可行解为基本可行解若A的秩为m，则X的正分量的个数km；当k=m时，则x1,x2,xk的系数列向量P1,P2,Pk恰好构成基，X为基本可行解。当km时，则必定
9、可再找出m-k个列向量与P1,P2,Pk一起构成基，X为基本可行解。证：用反证法 X非基本可行解非基本可行解X非凸集顶点非凸集顶点（1）必要性）必要性：X非基本可行解非基本可行解 X非凸集顶点非凸集顶点 不失一般性，设X=(x1,x2,xm,0,0,0)T，为非基本可行解，X为可行解，pjxj=b，j=1n即 pjxj=b(1)j=1m又 X是非基本可行解，P1,P2,Pm线性相关，即有1P1+2P2+mPm=0，其中1，2，m不全为0，两端同乘0，得1P1+2P2+mPm=0，（2）定理定理2 2：线性规划模型的基本可行解对应其可行域的顶点。由(1)+(2)得 (x1+1)P1+(x2+2)
10、P2+(xm+m)Pm=b由(1)-(2)得 (x1-1)P1+(x2-2)P2+(xm-m)Pm=b令X1=(x1+1，x2+2，xm+m，0，0)T X2=(x1-1，x2-2，xm-m，0，0)T取充分小,使得 xj j0，则 X1、X2均为可行解，但 X=0.5X1+(1-0.5)X2，X是X1、X2连线上的点，X非凸集顶点。xj0 （j=1,2,n)第 1 章 线性规划B-1 new=I，XB=(x3,，x4)T=(3，4)T,N=(1，2)=(2，3)，n第 1 章 线性规划s.stBXB+NXN+IXS=bXB,XN,XS0第 1 章 线性规划t x1+x2-x3+x4=3 x1
11、+2x2 +x5=4 xj0,(j=1,2,3,4,5)（1）凸集：对于集合C中任意两点连线上的点，若也在C内，则称 C为凸集。3单纯形法的基本原理（Simplex Method）第 1 章 线性规划S=-CB B-1（2）计算检验数：j=z=cj-zj=cj-ciaijLP模型的可行域的顶点与什么解具有对应关系？pjzj=b(2)设模型 n则 X1C，X2 C，即AX1=b，AX2=b，X10，X20，x1 x3（2）充分性：）充分性：X非凸集顶点非凸集顶点 X非基本可行解非基本可行解设X=(x1,x2,xr,0,0,0)T为非凸集顶点，则必存在Y、Z两点，使得X=Y+(1-)Z，(01)，
12、且Y、Z为可行解或者 xj=yj+(1-)zj (00,1-0，当xj=0，必有yj=zj=0 pjyj=j=1n pjyj=b(1)j=1r pjzj=j=1n pjzj=b(2)j=1r (yj-zj)pj=0j=1r,(1)-(2),得即(y1-z1)P1+(y2-z2)P2+(yr-zr)Pr=0 Y、Z为不同两点，yj-zj不全为0，P1,P2,Pr线性相关，X非基本可行解。34O(3,3)C(4,2)662X1+2X2+X3=124X2+X5=124X1+X4=16XA=(0,3,6,16,0)TXO=(0,0,12,16,12)TXB=(3,3,0,4,0)TXC=(4,2,0,
13、0,4)TXD=(4,0,4,0,12)TADBX1X2z1=CX1=CX0-C=zmax-C，z2=CX2=CX0+C=zmax+C z0=zmax z1，z0=zmax z2，z1=z2=z0，即 X1、X2也为最优解，若X1、X2仍不是顶点，可如此递推，直至找出一个顶点为最优解。从而，必然会找到一个基本可行解为最优解。定理定理3 3：若线性规划模型有最优解，则一定存在一个基本可行解为最优解。证：证：设 X0=(x10,x20,xn0)T 是线性规划模型的一个最优解，z0=zmax=CX0若X0非基本可行解，即非顶点，只要取充分小，则必能找出X1=X0-0，X2=X0+0，即X1、X2为可
14、行解，单纯形法的计算步骤：初始基本可行解新的基本可行解最优否？STOPYN1初始基本可行解的确定：初始基本可行解的确定：设模型 n max z=cjxj j=1 n s.t.aijxjbi （i=1,2,m)j=1 xj0 （j=1,2,n)n m max z=cjxj+0 xsi j=1 I=1 n s.t.aijxj+xsi=bi （i=1,2,m)j=1 xj0，xsi0 （j=1,2,n;i=1,2,m)化标准形初始基本可行解 X=(0,0,0,b1,b2,bm)T，n个02从一个基本可行解向另一个基本可行解转换从一个基本可行解向另一个基本可行解转换 不失一般性，设基本可行解X0=(x
15、10,x20,xm0,0,0)T，前m个分量为正值，秩为m，其系数矩阵为P1 P2 Pm Pm+1 Pj Pn b 1 0 0a 1,m+1 a1j a 1n b1 0 1 0 a 2,m+1 a2j a 2nb2 0 0 1a m,m+1 amj a mn bm pjxj0=j=1n pixi0=b(1)i=1m 又P1 P2 Pm为一个基，任意一个非基向量Pj可以以该组向量线性组合表示，即Pj=a1j P1 +a2j P2+amj Pm，即 Pj=aij pi，移项，两端同乘0，有 (Pj-aij pi)=0 (2)i=1mi=1m(1)+(2)：(xi 0-aij)Pi+Pj=b，取充分
16、小，使所有xi 0-aij 0，从而i=1mX1=(x1 0-a1j,x2 0-a2j,xm 0-amj,0,0)T也是可行解。当取 =min aij 0 =，则X1的前m个分量至少有一个xL1为0。xi 0aijaljxL 0i P1,P2,PL-1,PL+1,Pm,Pj 线性无关。第 1 章 线性规划t x1+x2 3 标准化 s.j=1或者j=Cj-CBB-1 Pj解得 X=(0,0,3,4)TXC=(4,2,0,0,4)T1/2 0 -1 1 -1/2 1/2 1 0 0 1/2（2）用EXCEL工具求解第 1 章 线性规划（2）无穷多最优解：有许多点为最优解点，简称无穷多解；0 0
17、-1 -11 1 1 0（2）做出约束方程所在直线，确定可行域；令X1=(x1+1，x2+2，xm+m，0，0)T pjyj=b(1)max z=CBXB+CNXN+0XSMax z=2x1+3x2+0 x3+0 x41 1 1 0初始表 XB XN XS0 1/aLk 0 P1,P2,Pr线性相关，X1 也为基本可行解。3.最优解的判别最优解的判别依题义z0=cjxj0 =ci xi0 i=1mj=1nz0=cjxj1 =ci(xi 0-aij)+cj i=1mj=1n =ci(xi 0-aij)+(cj-ciaij)=z0+ji=1mi=1m因因 0，所以有如下结论：，所以有如下结论：(1
18、)对所有j，当 j0，有z1 z0，即z0为最优值，X0为最优解；(2)对所有j，当j0，但存在某个非基变量k=0，则对此Pk作 为新基向量得出的解X1，应有z1=z0，故z1 也为最优值，从而 X1为最优解，且为基本可行解，X0、X1 连线上所有的点均为最优解，因此该线性规划模型 具有无穷多解；(3)若存在某个j 0，但对应aij0，则因当 时，有z1，该线性规划模型具有无界解。1.4单纯形法的计算及示例1.4.1 单纯形法几何解释-顶点寻优 例：max z=2x1+3x2 max z=2x1+3x2+0 x3+0 x4 s.t x1+x23 标准化 s.t x1+x2+x3=3 x1+2x
19、2 4 x1+2x2+x4=4 x10,x20 xj0,(j=1,2,3,4)（1）初始基本可行解的选择：-坐标原点处令 x1=x2=0,由 x1+x2+x3=3 x1+2x2+x4=4 （2）是否为最优解的判定:-计算检验数若 x11,则 x31,x41,1=2-（01+01）=2 j=z=cj-zj=cj-ciaij，称 j为检验数。x3=3-(x1+x2)x4=4-(x1+2x2)解得 X=(0,0,3,4)T若 x21,则 x31,x42,2=3-(01+02)=3 *当所有检验数均有j 0时，则为最优解。*（3）找新的顶点（基本可行解）：直观看，x21,则 z 3，应找A点，即增加x
20、2。x2 可增加多少？需要保证 x3=3-(x1+x2)0 x4=4-(x1+2x2)0，x2 =min（3/1，4/2），从而 x3=1-(x1/2-x4/2）x2=2-(x1/2+x4/2)令 x1=x4=0，则新的基本可行解为 X=(0，2，1，0)T重复上述过程，直至所有检验数 j 0。继续迭代：找新的顶点（基本可行解）：若x11,则 z 1/2，应找B点，即增加x1。x1 可增加多少？需要保证 x3=1-(x1/2-x4/2)0 x2=2-(x1/2+x4/2)0，x1 =min（2，4），从而 x1=2-(2x3-x4)x2=1-(-x3+x4),则新的基本可行解为 X=(2，1，
21、0，0)T若 x11,则 x31/2,x21/2,1=2-（01/2+31/2）=1/2若 x41,则 x3-1/2,x21/2,4=0-（0(-1/2)+31/2）=-3/23=-1,4=-1,zmax=7O C A BX1X2(0,2)(3,0)(2,1)34Cj x1x2x3x4XBbCB1 1 1 0 1 2 0 12 3 0 034x3 x400cj-zj 23003/1=34/2=21/2 0 1 -1/2 1/2 1 0 1/2x3 x212cj-zj 1/2 0 0 -3/203241 0 2 -1 0 1 -1 1x1 x221cj-zj 0 0 -1 -1231.4.2 单
22、纯形法计算i单纯形法计算过程总结（1）化标准形，列初始单纯形表；（2）计算检验数：j=z=cj-zj=cj-ciaij（3）最优性判断：当所有检验数均有j 0时，则为最优解。否则迭代求新的基本可行解。（4）迭代：入基变量：取maxj 0=kxk出基变量：取min i=bi/aik aik0=l x(l)主元素：alk新单纯表：pk=单位向量注：当所有检验数j 0时，若存在非基变量检验数为0时，则有无穷多解，否则只有唯一最优解。i=1m 例：min z=2x1+3x2 max z=-2x1-3x2+0 x3 s.t x1+x2 3 标准化 s.t x1+x2-x3=3 x1+2x2=4 x1+2
23、x2=4 x10,x20 xj0,(j=1,2,3,4)max z=-2x1-3x2+0 x3-M x4-M x5 s.t x1+x2-x3+x4=3 x1+2x2 +x5=4 xj0,(j=1,2,3,4,5)引进人工变量，及M非常大正系数，模型转变为这种处理方法称为大M法，以下则可完全按单纯形法求解。1大大M法法1.5 单纯形法进一步讨论Cj x1x2x3x4XBbCB1 1 -1 1 0 1 2 0 0 1-2 -3 0 -M -M34x4 x5-M -Mcj-zj-2+2M-3+3M-M03/1=34/2=21/2 0 -1 1 -1/2 1/2 1 0 0 1/2x4 x212cj-
24、zj-1/2+M/2 0 -M 0 3/2-M/2-M-3241 0 -2 2 -1 0 1 1 -1 1x1 x221cj-zj 0 0 -1 1-M 1-M-2-3ix50说明：说明：当所有当所有 j j 0 0 ，但存在人工变量但存在人工变量x人人=0=0，则可以判定则可以判定该模型有无可行解。该模型有无可行解。采用大M法求解线性规划模型时，如果模型中各个系数与M的值非常接近时，若手工计算时，不会出现任何问题。如果利用计算机程序求解，则大M表现为一个较大的数字，由于综合计算的影响，导致检验数出现符号误差，引起判断错误，从而使大M方法失效。在这种情况下，可采用下面的两阶段法进行计算。2两阶
25、段法两阶段法：例：min z=2x1+3x2 max z=-2x1-3x2+0 x3 s.t x1+x2 3 标准化 s.t x1+x2-x3=3 x1+2x2=4 x1+2x2=4 x10,x20 xj0,(j=1,2,3,4)obj:max z=-x4-x5 s.t x1+x2-x3+x4=3 x1+2x2 +x5=4 xj0,(j=1,2,3,4,5)(1)第一阶段，构造判断是否存在可行解的模型：用单纯形法求解，若用单纯形法求解，若z zmaxmax=0=0，表明该模型有可行解，则可进，表明该模型有可行解，则可进入第二阶段，求原模型最优解。入第二阶段，求原模型最优解。Cj x1x2x3x
26、4XBbCB1 1 -1 1 0 1 2 0 0 1 0 0 0 -1 -134x4 x5-1 -1cj-zj 2 3-103/1=34/2=21/2 0 -1 1 -1/2 1/2 1 0 0 1/2x4 x212cj-zj 1/2 0 -1 0 1-1 0241 0 -2 2 -1 0 1 1 -1 1x1 x221cj-zj 0 0 0 -1 -10 0ix50(2)第二阶段，将原目标函数引入最终单纯形表，继续迭代：max z=-2x1-3x2+0 x3Cj x1x2x3XBbCB1 1 0 0 0 -1-2 -3 0 21x1 x2-2 -3cj-zj 0 0-11.4.3 程序求解（
27、1）用LINDO软件求解（2）用EXCEL工具求解使用EXCEL中数据处理工具规划求解。1.6 改进单纯形法单纯形法迭代过程可用矩阵变换描述如下：设 max z=CX stAXbX0分解 max z=CBXB+CNXN+0XS stBXB+NXN+IXS=bXB,XN,XS0约束方程两端同乘B-1，则可得如下表达式：式中，B最终表中基对应的矩阵，N初始表与最终表中均为非基对应的矩阵，I 单位矩阵A=B N max z=CBXB+CNXN+0XS st B-1 BXB+B-1 NXN+B-1 XS=B-1 b XB,XN,XS0对应最终单纯形表的模型用单纯形表表示如下：XS=bB N IXB=b
28、 I N B-1初始表 XB XN XS cj-zj 0,0 N S最终表 XB XN XS cj-zj B N 0,0 表中，b=B-1b N=B-1N 或者 Pj=B-1PjN=CN-CB B-1 N或者j=Cj-CBB-1 PjS=-CB B-1 化标准形：B-1 new =I，XB=b，求检验数：N=CN-CB B-1 new N，S=-CB B-1 new 最优性判别：所有 0，X人0，无可行解；所有 0，X人=0，存在 N=0，无穷多解；所有 0，X人=0，不存在N=0，唯一解；否则(存在 0)，转，取max xk，为换入变量，计算Pk=B-1 new Pk，若 Pk 0 无界解,
29、否则，计算i=bi/aik|aik 0，取min xL为换出变量，令改进单纯形法计算步骤：改进单纯形法计算步骤：D=1 -a1k/aLk 00 1/aLk 00 -amk/aLk 1 xL计算 B-1 new=D B-1old，b=B-1 newb转。注：D矩阵为单位矩阵中出基变量所在单位向量以上述列向量代换。实例演算如下：例：max z=2x1+3x2 max z=2x1+3x2+0 x3+0 x4 s.t x1+x23 标准化 s.t x1+x2+x3=3 x1+2x2 4 x1+2x2+x4=4 x10,x20 xj0,(j=1,2,3,4)x1x2x3 x4 b111 0 3 120
30、1 4 初始解：B-1 new=I，XB=(x3,，x4)T=(3，4)T,N=(1，2)=(2，3)，计算 P2=B-1 new P2=(1，2)T，换入变量：max x2，换出变量：i=bi/ai2|ai2 0=(3，2)，min x4，用单纯形法求解，若zmax=0，表明该模型有可行解，则可进入第二阶段，求原模型最优解。pjzj=1/2 0 -1 0 1第 1 章 线性规划重复上述过程，直至所有检验数 j 0。z0=zmax=CX01 两个概念：如果利用计算机程序求解，则大M表现为一个较大的数字，由于综合计算的影响，导致检验数出现符号误差，引起判断错误，从而使大M方法失效。在这种情况下，
31、可采用下面的两阶段法进行计算。4x2 12 -x1x2x3 x4 b0 0 0 -1 -1t x1+x2 3 标准化 s.x1+x2+x3=3 x1+2x2+x4=4 x1,x2,x3,x40对应最终单纯形表的模型（7）基解（基解）：令模型中所有非基变量X非基=0后，由模型约束方程组 n则 X1C，X2 C，即AX1=b，AX2=b，X10，X20，P1,P2,Pr线性相关，（8）基本可行解（基可行解）：在基解中，同时又是可行解的解称为基可行解。XC=(4,2,0,0,4)T 第二次计算：1 -1/20 1/2D=，B-1 new=D B-1old=1 -1/20 1/21 00 11 -1/
32、20 1/2=XB=(x3,，x2)T=B-1 new b=(1，2)T,N=(1，4)=CN-CB B-1 N=(2，0)-(0，3)1 -1/20 1/21 01 1=(1/2，-3/2),换入变量：max x1，计算 P1=B-1 new P1=(1/2，1/2)T，换出变量：i=bi/ai1|ai1 0=(2，4)，min x3，t 2x1+2x212 -该线性规划模型具有无界解。初始表 XB XN XS第 1 章 线性规划若 x41,则 x3-1/2,x21/2,4=0-（0(-1/2)+31/2）=-3/2计算 P2=B-1 new P2=(1，2)T，P1 P2 Pm Pm+1
33、Pj Pn b用单纯形法求解，若zmax=0，表明该模型有可行解，则可进入第二阶段，求原模型最优解。可行解：X=(0，0)T，X=(0，1)T，X=(1/2，1/3)T 等。=(1/2，-3/2),由(1)+(2)得 (x1+1)P1+(x2+2)P2+(xm+m)Pm=b X1 也为基本可行解。第 1 章 线性规划n mt x1+x2 3 标准化 s.（2）用EXCEL工具求解重复上述过程，直至所有检验数 j 0。引进人工变量，及M非常大正系数，模型转变为第 1 章 线性规划证明：设 max z=CX定理2：线性规划模型的基本可行解对应其可行域的顶点。XC=(4,2,0,0,4)Tmax z
34、=CBXB+CNXN+0XS第 1 章 线性规划0 1/21 1 1 0令X1=(x1+1，x2+2，xm+m，0，0)T（8）基本可行解（基可行解）：在基解中，同时又是可行解的解称为基可行解。（4）基：设A为线性规划模型约束条件系数矩阵（m n，mn），而B为其mm子矩阵，若|B|0，则称B为该线性规划模型的一个基。则 X1C，X2 C，即AX1=b，AX2=b，X10，X20，0 1/aLk 04单纯形法的计算及示例第 1 章 线性规划（1）用LINDO软件求解最终表 XB XN XS（1）必要性：X非基本可行解 X非凸集顶点单纯形法迭代过程可用矩阵变换描述如下：设计算 B-1 new=D B-1old，pjzj=Y、Z为不同两点，yj-zj不全为0，2 0-1 1D=，B-1 new=D B-1old=2 0-1 12 -1-1 11 -1/20 1/2=XB=(x1，x2)T=B-1 new b=(2，1)T,N=(3，4)=CN-CB B-1 N=(0，0)-(2，3)2 -1-1 11 00 1=(-1，-1),第三次计算：所有 0，故为最优解，XB=(x1，x2)T=(2，1)T,z max=7
