1、线性规划解概念和单纯形法（优选）线性规划解概念和单纯形法2解的解析MaxMaxz z=2=2 x x1 1 +3+3 x x2 2+0+0 x x3 3+0 +0 x x4 4+0 +0 x x5 5 s.t.2 s.t.2x x1 1+2+2x x2 2 +x x3 3 =12(A)=12(A)4 4x x1 1 +x x4 4 =16(B)=16(B)5 5x x2 2 +x x5 5=15(C)=15(C)x x1 1,x,x2 2 ，x x3 3，x x4 4 ，x x5 5 0(D,E)0(D,E)3解的解析w可行解可行解 满足上述约束条件(A)、(B)、（C)的解x x=(x1,x
2、2，x3，x4，x5)T称为线性规划问题的可行解，全部可行解的集合成为可行域。w最优解最优解 是目标函数z=15达到最大值的可行解x x=(3,3，0，4，0)T成为最优解。4解的解析w基基 设A为约束方程组3*5阶系数矩阵 P1 P2 P3 P4 P5 2 2 1 0 02 2 1 0 0 A=4 0 0 1 0 0 5 0 0 1设B=(P3 P4 P5)5 A中其秩为3,B是A矩阵中的一个3阶的满秩矩阵,称B是线性规划问题的一个基，B中的每一个列向量(如P3 P4 P5)称为基向量，与基向量对应的变量称为基变量，线性规划中除基变量以外的其他变量称为非基变量。6解的解析w基解 在约束方程组
3、中，令所有非基变量为0,又因为有B行列式不为0，由各约束方程可解出各基变量的唯一解。将这个解加上非基变量取0的值称为线性规划问题的基解，显然，在基解中变量取非零值的个数不大于方程数，基解的总数不超过20个。7解的解析w基可行解 满足变量非负约束条件的基解称为基可行解。w可行基 对应与基可行解的基成为可行基。8a21 x1+a22 x2+a2n xn+xn+2=b2图解法求解线性规划（2）线性规划问题的基本解、基本可行解和可行基xN 02x1+x2+5x3+x6=20a11x1+a12x2+a1nxn+xn+1=b1而其他变量称为非基变量。考虑线性规划标准形式的约束条件解 列出单纯形表并进行单纯
4、形变换我们可以证明以下结论线性规划的基本可行解就是可行域的极点。基 b3x2+x5=75 Danzig）在1947年为研究美国空军资源的优化配置时提出的一种方法。设B是线性规划的一个基，则A可以表示为设B=(P3 P4 P5)1)x1应取多大的值？(回顾)例2.1 问题工厂应如何安排生产可获得最大的总利润？用图解法求解。解设变量xi为第i种（甲、乙）产品的生产件数（i1，2）。根据前面分析，可以建立如下的线性规划模型 Max z=1500 x1+2500 x2 s.t.3x1+2x2 65 (A)2x1+x2 40 (B)3x2 75 (C)x1,x2 0 (D,E)9 图解法求解线性规划10
5、2030405010203040O10 (线性规划的基、基本解与基本可行解)在一般情况下，由于图解法无法解决三个变量以上的线性规划问题，对于n个变量的线性规划问题，我们必须用解方程的办法来求得可行域的极点。再来进一步考察前例。例2.8 把例2.1的线性规划模型标准化，引入松驰变量 x3，x4，x5 0，得到11Max Max z z=1500 =1500 x x1 1 +2500+2500 x x2 2s.t.3s.t.3x x1 1+2+2x x2 2+x x3 3=65=65 2 2x x1 1+x x2 2+x x4 4=40=40 3 3x x2 2+x x5 5=75=75 x x1
6、 1 ,x x2 2 ,x x3 3,x x4 4 ,x x5 5 0 0 可见：等式约束条件的系数矩阵为 100300101200123A12从其中取出不同的三列出来，有 C53=10 种取法 0301120232B 1000120036B 100300101200123A 1030010128B 0001020134B 1300120233B 0300121231B 0031010127B 1000020135B 10001000110B 1030110029B13其中B1对应的基变量为x1,x2,x3，非基变量为x4,x5 令非基变量 x4=0,x5=0，则得对应方程组3x1+2x2+x
7、3=65 2x1+x2=40 3x2=75得对应基本解 该10个方阵中除 B4 外，其余均为满秩矩阵，故均为线性规划的基。x(1)=(7.5,25,-7.5,0,0)T类似，可得所有基本解为14 X(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,0,-45)T X(5）=(20,0,5,0,75)T X(10)=(0,0,65,40,75)T X(7）=(0,25,15,15,0)T不是可行解
8、是可行解,对应顶点A是可行解,对应顶点B是可行解,对应顶点C不是可行解不是可行解不是可行解是可行解,对应顶点D是可行解,对应顶点E15A=(p1，p2，pn)，xN为nm列向量，它的各分量称为非基变量，与非基矩阵N的列向量对应。图解法求解线性规划x1+2x2+3x3=153x2=75（1）如何找到一个初始的基本可行解。1 0 0 1/4 -1/2通过运算，所有的基变量都可以用非基变量来表示：称为基向量，与基向量对应的变量称为基变量，线性规划中除基变量以外的其他变量称为非基变量。基 b考虑标准形式的线性规划问题：0 15/2显然，xj=0 j=1,n;X(7）=(0,25,15,15,0)TA=
9、(p1，p2，pn)，线性规划解的概念基 b基 bm m 图解法求解线性规划102030405010203040O16w 上图各约束直线的交点是上图各约束直线的交点是由以下方法得到在标准化的等式由以下方法得到在标准化的等式约束中，令其中的非基变量为零，约束中，令其中的非基变量为零，求出其他基变量的唯一解，得求出其他基变量的唯一解，得LPLP问题的基解问题的基解(x1,x2,x3,(x1,x2,x3,x4,x5)T,x4,x5)T,若其分量全为非负，若其分量全为非负，则该解称为基可行解则该解称为基可行解,对应于线性对应于线性规划可行域的一个极点（顶点）；规划可行域的一个极点（顶点）；若基解中至少
10、有一个分量为负值若基解中至少有一个分量为负值则该交点不是可行域的极点。则该交点不是可行域的极点。2.2.线性规划解的概念线性规划解的概念 17 下面讨论线性规划标准形式的基、基本解、基本可行解的概念。考虑线性规划标准形式的约束条件 Ax=b，x0 其中A为mn的矩阵，nm，秩(A)=m，b Rm。在约束等式中，令n维空间的解向量 x=(x1，x2，xn)T 2.2.线性规划解的概念线性规划解的概念 （1）线性规划的基基：对于线性规划的约束条件 Ax=b，x0 18 设B B是A A矩阵中的一个非奇异（满秩）的mm 子矩阵，则称B B为线性规划的一个基基。用前文的记号，A A=(p p1 1，p
11、 p2 2，p pn n)，其中 p pj j=(a1j，a2j，amj)T Rm，任取A A中的m个线性无关列向量 p pj j Rm 构成矩阵 B B=(p pj1 j1，p pj2 j2，p pjmjm)。那么B B为线性规划的一个基基。我们称对应于基B B的变量xj1，xj2，xjm为基变量基变量；而其他变量称为非基变量非基变量。2.2.线性规划解的概念线性规划解的概念 19 可以用矩阵来描述这些概念。设B是线性规划的一个基，则A可以表示为 A=B,N x也可相应地分成 xB x=xN 其中xB为m维列向量，它的各分量称为基变量，与基B的列向量对应；xN为nm列向量，它的各分量称为非基
12、变量，与非基矩阵N的列向量对应。2.2.线性规划解的概念线性规划解的概念 20 （2）线性规划问题的基本解、基本可行解和可行基 对于线性规划问题，设矩阵B=(pj1，pj2，pjm)为一个基，令所有非基变量为零，可以得到m个关于基变量xj1，xj2，xjm的线性方程，解这个线性方程组得到基变量的值。我们称这个解为一个基本解；若得到的基变量的值均非负，则称为基本可行解，同时称这个基B为可行基。2.2.线性规划解的概念线性规划解的概念 21 矩阵描述为，对于线性规划的解 xB B1b x=xN 0 称为线性规划与基B对应的基本解。若其中B1b0，则称以上的基本解为一基本可行解，相应的基B称为可行基
13、。2.2.线性规划解的概念线性规划解的概念 22 我们可以证明以下结论线性规划的基本可行解就是可行域的极点。这个结论被称为线性规划的基本定理，它的重要性在于把可行域的极点这一几何概念与基本可行解这一代数概念联系起来，因而可以通过求基本可行解的线性代数的方法来得到可行域的一切极点，从而有可能进一步获得最优极点。2.2.线性规划解的概念线性规划解的概念 23 利用求解线性规划问题基本可行解（极点）的方法来求解较大规模的问题是不可行的。单纯形法的基本思路是有选择地取基本可行解，即是从可行域的一个极点出发，沿着可行域的边界移到另一个相邻的极点（要求新极点的目标函数值不比原目标函数值差）。3.3.单单
14、纯纯 形形 法法243.3.单单 纯纯 形形 法法N NY Y单纯形法的基本过程25需要解决的三个问题：（1）如何找到一个初始的基本可行解。（2）如何判别当前的基本可行解是否已达到了最优解。（3）若当前解不是最优解，如何去寻找一个改善了的基本可行解。单纯型原理是由美国数学家丹齐格（G.B.Danzig）在1947年为研究美国空军资源的优化配置时提出的一种方法。26下面举例说明单纯型法的思想 0,524261552121212xxxxxxxmax z=2x1+x2 (4.1)max z=2x1+x2例：max z=2x1+x2270,524261550002max5432152142132543
15、21xxxxxxxxxxxxxxxxxxz将上式标准化为543,xxx为基变量，将基变量用非基变量表示为为基变量，将基变量用非基变量表示为 取2152142352624515xxxxxxxx2x令非基变量x1=0,令非基变量等于令非基变量等于0，得到一个基本可行解，得到一个基本可行解TX)5,24,15,0,0()0(28考虑线性规划标准形式的约束条件还是非基变量，仍取零值。Ax=b，x02x1+x2+5x3+x6=202、表中第三列（b列）的数总应保持非负（0）；Maxz=2 x1+3 x2+0 x3+0 x4+0 x5A中其秩为3,B是A矩阵中的一个3阶的满秩矩阵,称B是线性规划问题的一个
16、基，B中的每一个列向量(如P3 P4 P5)合理利用线材问题如何下料使用材最少。xn cn bn am1 am2 .1 0 0 1/4 -1/2 .考虑线性规划标准形式的约束条件.Max z=5x1+2x2+3x3x4Mx5Mx6通过运算，所有的基变量都可以用非基变量来表示：第一阶段 (LP-1）x1+2x2+3x3+x5=152 2 1 0 0w 我们想让x1从非基变量转为基变量，今后我们称之为进基。因基变量只有三个，因此必须从原有的基x3，x4，x5，中选一个离开基转为非基变量。下解决两个问题w1)x1应取多大的值？w2)x1进基，x3，x4，x5 那一个出基？现在，2x还是非基变量，仍取
17、零值。现在，还是非基变量，仍取零值。还是非基变量，仍取零值。15143562415xxxxxx1要增加，要增加，x3，x4，x5 0。1x5,624min=4=29把以上的运算制成一张表格，称单纯型表。0 2 1 0 0 0 基 b 0 15 0 24 0 50 5 1 0 06 2 0 1 01 1 0 0 1 5 2 1 0 0 01x2x3x4x5xBCjc3x5x6244xX1进基，x4出基。jjzc 30 0 2 1 0 0 0 基 b 0 15 2 4 0 10 5 1 0 01 2/6 0 1/6 00 4/6 0 -1/6 1 3123/2 0 1/3 0 -1/3 01x2x
18、3x4x5xBCjc3x5x1xjjzc 下一步应选哪个变量进基，又选哪个变量出基呢？下一步的单纯形表又怎样列呢？31 0 2 1 0 0 0 基 b 0 15/2 2 7/2 1 3/2 0 0 1 5/4 -15/21 0 0 1/4 -1/20 1 0 -1/4 3/2 0 0 0 -1/4 -1/2 1x2x3x4x5xBCjc3x1xjjzc 表得该LP问题的最优解为：5x2X=(7/2,3/2,15/2,0,0)T,maxz=17/232考虑标准形式的线性规划问题：Max z=c1x1+c2x2+cnxn s.t.a11 x1+a12 x2+a1n xn=b1 a21 x1+a22
19、 x2+a2n xn=b2 .am1 x1+am2 x2+amn xn=bm x1,x2,xn 0 x1 c1 b1 a11 a12 .a1n x2 c2 b2 a21 a22 .a2nX=.C=.B=.A=.xn cn bn am1 am2 .amn 3.3.单单 纯纯 形形 法法Max z=CXs.t.AX=b X033这里，矩阵这里，矩阵A A表示为：表示为：A A=(=(p p1 1，p p2 2，p pn n)，若找到一个可行基，无防设若找到一个可行基，无防设B B=(=(p p1 1，p p2 2，p pm m)，则，则m m个基变量个基变量为为 x1,x2,xm，n-mn-m个非
20、基变量为个非基变量为 xm+1，xm+2，xn 。通过运算，所有的基变量。通过运算，所有的基变量都可以用非基变量来表示：都可以用非基变量来表示：3.3.单单 纯纯 形形 法法34 x1=b1-（a1m+1xm+1+a1m+2xm+2+a1nxn）x2=b2-（a2m+1xm+1+a2m+2xm+2+a2nxn）(2-11).xm=bm-（amm+1xm+1+amm+2xm+2+amnxn）把它们代入目标函数，得把它们代入目标函数，得 z z=zz+m+1m+1x xm+1m+1+m+2m+2x xm+2m+2+n nx xn n (2-12)(2-12)其中其中 j j=c cj j-（c c
21、1 1aa1j 1j+c c2 2aa2j 2j+c cm m a amjmj）我们把由非基变量表示的目标函数形式称为基我们把由非基变量表示的目标函数形式称为基B B相应的目标函数形式。相应的目标函数形式。3.3.单单 纯纯 形形 法法353 3、单单 纯纯 形形 法法w表格单纯形法表格单纯形法w考虑考虑 bi 0 i=1,mw Max z=c1 x1+c2 x2+cn xn w s.t.a11 x1+a12 x2+a1n xn b1w a21 x1+a22 x2+a2n xn b2w w am1 x1+am2 x2+amn xn bmw x1，x2，xn 0363 3、单单 纯纯 形形 法法
22、w加入松弛变量加入松弛变量w Max z=c1 x1+c2 x2+cn xn w s.t.a11 x1+a12 x2+a1n xn+xn+1=b1w a21 x1+a22 x2+a2n xn+xn+2=b2w w am1 x1+am2 x2+amn xn+xn+m=bmw x1，x2，xn，xn+1，xn+m 037显然，显然，xj=0 j=1,n;xn+i=bi i=1,m 是基本可行是基本可行解解 对应的基是单位矩阵。对应的基是单位矩阵。以下是初始单纯形表以下是初始单纯形表 m m其中其中f=cn+i bi j=cj cn+i aij 为检验数为检验数 cn+i=0 i=1,m i=1 i
23、=1 an+i,i=1 ,an+i,j=0(ji)i,j=1,m为约束方程系为约束方程系数数3 3、单单 纯纯 形形 法法b价值系数方程组右侧常数比比率率计计算算值值383 3、单单 纯纯 形形 法法w表格单纯形法的计算步骤w（1）找出初始可行基，确定初始基可行解，建立初始单纯形表；w（2）检验各非基变量的检验数，若所有j 0，则已达最优解，停止计算；否则，转入下一步；w（3）若有某个j 0，其对应系数列向量0，则此问题是无界解，停止计算；否则，转入下一步；w（4）决定换入和换出基变量；w（5）用矩阵的初等行变换法将 xk 所对应的列向量变换为（0，0，1，0）T，换入新的基变量，得到新的单纯
24、形表，返回步骤（2）。39X(1)=(7.任取A中的m个线性无关列向量 pj Rm 构成矩阵 B=(pj1，pj2，pjm)。当所有非基变量的检验数均0,则相应的最优解是唯一的。（1）找出初始可行基，确定初始基可行解，建立初始单纯形表；x1要增加，x3，x4，x5 0。若基解中至少有一个分量为负值则该交点不是可行域的极点。3x2=75xn+i=bi i=1,mx=.x1+2x2+3x3=15x1 c1 b1 a11 a12 .x1，x2，xn，xn+1，xn+m 0 x1+2x2+3x3+x5=15第一阶段 (LP-1）例例2.102.10：用单纯形法的基本思路：用单纯形法的基本思路解例解例2
25、.82.8的线性规划问题的线性规划问题 Max Max z z=1500 =1500 x x1 1 +2500+2500 x x2 2 s.t.3 s.t.3 x x1 1 +2+2 x x2 2 +x x3 3 =65=65 2 2 x x1 1 +x x2 2 +x x4 4=40=40 3 3 x x2 2 +x x5 5 =75=75 x x1 1,x,x2 2,x,x3 3,x,x4 4,x,x5 5 0 03.3.单单 纯纯 形形 法法40 解解 列出单纯形表并进行单纯形变换列出单纯形表并进行单纯形变换 最优解最优解 x1=5 x2=25 x4 =5（松弛标量，表示（松弛标量，表示
26、B设备有设备有5个机时的剩余个机时的剩余）最优值最优值 z*=70000 3 3、单单 纯纯 形形 法法41w注意单纯形法中，注意单纯形法中，w 1、每一步运算只能用矩阵初等行变、每一步运算只能用矩阵初等行变换；换；w 2、表中第三列（、表中第三列（b列）的数总应保列）的数总应保持非负（持非负（0）；）；w 3、当所有检验数均非正（、当所有检验数均非正（0）时，）时，得到最优单纯形表。当所有非基变量得到最优单纯形表。当所有非基变量的检验数均的检验数均0,则相应的最优解是唯一则相应的最优解是唯一的。的。3 3、单纯形法单纯形法 424.单纯形法的进一步讨论单纯形法的进一步讨论 a21 x1+a2
27、2 x2+a2n xn+a21 x1+a22 x2+a2n xn+xn+2 =b2xn+2 =b2 .am1 x1+am2 x2+amn xn+am1 x1+am2 x2+amn xn+xn+m =bmxn+m =bm x1 x1，x2 x2，xn xn ，xn+1 xn+1，xn+m 0 xn+m 0 对于规模较大的问题，用试算的方法取得初始基可行解很困难，必须有一个初始可行基的系统化方法。43显然，xj=0 j=1,n;xn+i=bi i=1,m 是基本可行解。对应的基是单位矩阵。结论由于 Max z=c1x1+c2x2+cnxn Mxn+1 Mxn+m则若得到的最优解满足 xn+i=0
28、i=1,m 则是原问题的最优解；否则，原问题无可行解。4.单纯形法的进一步讨论单纯形法的进一步讨论44例2.11（LP）Max z=5x1+2x2+3x3 x4 s.t.x1+2x2+3x3=15 2x1+x2+5x3=20 x1+2x2+4x3 +x4 =26 x1,x2,x3,x4 04.单纯形法的进一步讨论单纯形法的进一步讨论45w Max z=5x1+2x2+3x3x4Mx5Mx6 w s.t.x1+2x2+3x3+x5=15 w 2x1+x2+5x3+x6=20 w x1+2x2+4x3+x4=26 w x1,x2,x3,x4,x5,x6 04.单纯形法的进一步讨论单纯形法的进一步讨
29、论46大大M M法法 （LP-M）得到最优解：(25/3，10/3，0，11)T 最优目标值：112/34.单纯形法的进一步讨论单纯形法的进一步讨论47w 4.2 两阶段法w 引入人工变量 xn+i 0，i=1,m；w 构造:w Max z=xn+1 xn+2 xn+m w s.t.w a11x1+a12x2+a1nxn+xn+1=b1w a21x1+a22x2+a2nxn+xn+2=b2 w .w .w .w am1x1+am2x2+amnxn+xn+m=bmw x1,x2.xn,xn+1,xn+m 04.单纯形法的进一步讨论单纯形法的进一步讨论48 结论：若得到的最优解满足 xn+i=0
30、i=1,m 则是原问题的基本可行解;否则，原问题无可行解。得到原问题的基本可行解后，第二阶段求解原问题。49w 第一阶段问题（第一阶段问题（LP 1LP 1）w Max z=x5 x6 Max z=x5 x6 w s.t.x1+2x2+3x3+x5 =s.t.x1+2x2+3x3+x5 =15 15 w 2x1+x2+5x3+x6=2x1+x2+5x3+x6=20 20 w x1+2x2+4x3 +x4 =x1+2x2+4x3 +x4 =26 26 x1,x2,x3,x4,x5,x6 x1,x2,x3,x4,x5,x6 0 0例例2.112.11：（：（LPLP）Max Max z z=5=5
31、x x1 1 +2+2x x2 2 +3+3x x3 3 -x x4 4 s.t.s.t.x x1 1+2 2x x2 2+3 3x x3 3=15 =15 2 2x x1 1 +x x2 2 +5+5x x3 3=20 =20 x x1 1 +2+2x x2 2 +4+4x x3 3 +x x4 4 =26 =26 x x1 1 ,x x2 2 ,x x3 3 ,x x4 4 0 0505152 合理利用线材问题如何下料合理利用线材问题如何下料使用材最少。使用材最少。配料问题在原料供应量的限配料问题在原料供应量的限制下如何获取最大利润。制下如何获取最大利润。投资问题从投资项目中选取投资问题从
32、投资项目中选取方案，使投资回报最大。方案，使投资回报最大。5.5.线性规划应用线性规划应用 一、线性规划一、线性规划-53 例例2.14:2.14:明兴公司生产甲、乙、丙三种产品，都需要经过铸造、机加工和装配 三个车间。甲、乙两种产品的铸件可以外包协作，亦可以自行生产，但产品丙必须本厂铸造才能保证质量。数据如下表。问：公司为了获得最大利润，甲、乙、丙三种产品各生产多少件？甲、乙两种产品的铸造中，由本公司铸造和由外包协作各应多少件？生产计划的问题生产计划的问题54解：解：设 x1,x2,x3 分别为三道工序都由本公司加工的甲、乙、丙三种产品的件数，x4,x5 分别为由外协铸造再由本公司机加工和装配的甲、乙两种产品的件数。生产计划的问题生产计划的问题55
