1、 线性规划与单纯形法线性规划与单纯形法 线性规划（LP：Linear Programming）规划论中的静态规划 解决有限资源的最佳分配问题 求解方法：图解法 单纯形解法 线性规划简介 19391939年苏联的康托洛维奇（年苏联的康托洛维奇（H.B.Kahtopob H.B.Kahtopob）和美国的希奇）和美国的希奇柯克（柯克（F.L.HitchcockF.L.Hitchcock）等人就在生产组织管理和制定交通）等人就在生产组织管理和制定交通运输方案方面首先研究和应用一线性规划方法。运输方案方面首先研究和应用一线性规划方法。19471947年旦茨格等人提出了求解线性规划问题的单纯形法，年旦茨
2、格等人提出了求解线性规划问题的单纯形法，为线性规划的理论与计算奠定了基础。为线性规划的理论与计算奠定了基础。随着电子计算机的出现和日益完善，规划论得到迅速的发随着电子计算机的出现和日益完善，规划论得到迅速的发展，可用电子计算机来处理成千上万个约束条件和变量的展，可用电子计算机来处理成千上万个约束条件和变量的大规模线性规划问题，从解决技术问题的最优化，到工业、大规模线性规划问题，从解决技术问题的最优化，到工业、农业、商业、交通运输业以及决策分析部门都可以发挥作农业、商业、交通运输业以及决策分析部门都可以发挥作用。用。线性规划问题的三个要素线性规划问题的三个要素 决策变量 决策问题待定的量值称为决
3、策变量。决策变量的取值要求非负。约束条件 任何问题都是限定在一定的条件下求解，把各种限制条件表示为一组等式或不等式，称之为约束条件。约束条件是决策方案可行的保障。LP的约束条件，都是决策变量的线性函数。目标函数 衡量决策方案优劣的准则，如时间最省、利润最大、成本最低。目标函数是决策变量的线性函数。有的目标要实现极大，有的则要求极小。1线性规划问题及其数学模型 设设 备备原原 料料A A原原 料料B B 1 4 0 2 0 4 8台时 16kg 12kg例 某工厂在计划期内要安排生产、两种产品，已知生产单位产品所需的设备台时和原料A、B的消耗量如下表。该工厂每生产一件产品可获利2元，每生产一件产
4、品可获利3元，问应如何安排生产计划能使该厂获利最多？这个问题可以用下面的数学模型来描述，设计划期内产品、的产量分别为x1，x2，可获利润用z表示，则有：Max Z=2x1+3x2x1+2x284x1 16 4x212x1,x201.1问题的提出问题的提出又例又例 靠近某河流有两个化工厂，流经靠近某河流有两个化工厂，流经第一化工厂的河流流量为每天第一化工厂的河流流量为每天500万万m3，两工厂之间有一条流量为每天两工厂之间有一条流量为每天200万万m3的的支流（见图）。支流（见图）。第一化工厂每天排放污水第一化工厂每天排放污水2万万m3，第二，第二化工厂每天排放污水化工厂每天排放污水 1.4万万
5、m3。污水从。污水从工厂工厂1流到工厂流到工厂2前会有前会有20%自然净化。自然净化。根据环保要求，河水中污水的含量应不根据环保要求，河水中污水的含量应不大于大于0.2%。而工厂。而工厂1和工厂和工厂2处理污水的处理污水的成本分别为成本分别为1000元元/万万m3和和800元元/万万m3。问两工厂各应处理多少污水才能使处理问两工厂各应处理多少污水才能使处理污水的总费用最低？污水的总费用最低？设工厂设工厂1和工厂和工厂2每天分别处理污水每天分别处理污水x1和和x2万万m3，则有，则有：Min z=1000 x1+800 x2(2-x1)/500 0.0020.8(2-x1)+1.4-x2/700
6、 0.002 x12,x21.4 x1,x20以上两例都有一些共同的特征：以上两例都有一些共同的特征：用一组变量表示某个方案，一用一组变量表示某个方案，一般这些变量取值是非负的。般这些变量取值是非负的。存在一定的约束条件，可以用存在一定的约束条件，可以用线性等式或线性不等式来表示。线性等式或线性不等式来表示。都有一个要达到的目标，可以都有一个要达到的目标，可以用决策变量的线性函数来表示。用决策变量的线性函数来表示。满足以上条件的数学模型称为满足以上条件的数学模型称为线性规划模型。线性规划模型线性规划模型。线性规划模型的一般形式如下：的一般形式如下：0,),(),(),(max(min)2122
7、1122222121112121112211nmnmnmmnnnnnnxxxbxaxaxabxaxaxabxaxaxaxcxcxcz其中：其中：cj为价值系数；为价值系数；aij为技术系数；为技术系数；bi为限额系数；为限额系数；xj为非负变量为非负变量 图解法即是用图示的方法来求解线性规划问图解法即是用图示的方法来求解线性规划问题。题。一个二维的线性规划问题，可以在平面图上一个二维的线性规划问题，可以在平面图上求解，三维的线性规划则要在立体图上求解，求解，三维的线性规划则要在立体图上求解，这就比较麻烦，而维数再高以后就不能图示这就比较麻烦，而维数再高以后就不能图示了。了。1.2线性规划的图解
8、法线性规划的图解法可行域的确定可行域的确定 例例:数学模型为数学模型为 maxZ=3x1+5 x2 x1 8 2x2 12 3x1+4 x2 36 x1 0,x2 0S.t.x1=82x2=123x1+4 x2=36x1x24812369 五边形五边形OABCD内内(含边界含边界)的任意一点的任意一点(x1，x2)都是满足所有都是满足所有约束条件的一个解，称之可行解约束条件的一个解，称之可行解。满足所有约束条件的解的集合，称之为可行域。即所有约束满足所有约束条件的解的集合，称之为可行域。即所有约束条件共同围城的区域。条件共同围城的区域。最优解的确定最优解的确定Z=30Z=42Z=15 目标函数
9、 Z=3x1+5 x2 代表以Z为参数的一族平行线。x1=82x2=123x1+4 x2=36x1x24812369 等值线：位于同一直线上的点的目标函数值相同。等值线：位于同一直线上的点的目标函数值相同。最优解：可行解中使目标函数最优最优解：可行解中使目标函数最优(极大或极小极大或极小)的解的解 由线性不等式组成的可行域是凸集由线性不等式组成的可行域是凸集(凸集的定凸集的定义是：集合内部任意两点连线上的点都属于这义是：集合内部任意两点连线上的点都属于这个集合个集合)。可行域有有限个顶点。设规划问题有可行域有有限个顶点。设规划问题有n个变量，个变量，m个约束，则顶点的个数不多于个约束，则顶点的
10、个数不多于Cnm个。个。目标函数最优值一定在可行域的边界达到，而目标函数最优值一定在可行域的边界达到，而不可能在其内部。不可能在其内部。几点说明几点说明解的可能性解的可能性x1=82x2=123x1+4 x2=36x1x24812369上例的数学模型变为上例的数学模型变为 maxZ=3x1+4 x2 x1 8 2x2 12 3x1+4 x2 36 x1 0,x2 0S.t.Z=24Z=36Z=12 唯一最优解：只有一个最优点。多重最优解：无穷多个最优解。若在两个顶点同时得到最优解，则它们连线上的每一点都是最优解。无界解：线性规划问题的可行域无界，使目标函数无限增大而无界。（缺乏必要的约束条件）
11、例如例如 maxZ=3x1+2 x2 -2x1+x2 2 x1-3 x2 3 x1 0,x2 0-2x1+x2=2x1-3 x2=3x2123-1x1123-1Z=6Z=12S.t.无可行解：若约束条件相互矛盾，则可行域为空集例如例如 maxZ=3x1+2 x2 -2x1+x2 2 x1-3 x2 3 x1 0,x2 0-2x1+x2=2x1-3 x2=3x2123-1x1123-1S.t.唯一最优解无穷多最优解x1x2x1x2无界解无可行解当线性规划的可行域非空它是有界或无界凸多边形，若存在最优解，则最优解一定在可行域的的某个顶点或顶点的连线取得，也即有唯一最优解或无穷多最优解图解法虽然简单
12、直观，但是只能解决两个变量练习:用图解法求解以下LP模型无符号限制21212121,2322265maxxxxxxxxxzAnswerx1x2-2x1+3x2=2x1-2x2=20Ax1=-10,x2=-6,z=-861.3 线性规划的标准型 线性规划问题的数学模型有各种不同的形式，如 目标函数有极大化和极小化；约束条件有“”、“”和“”三种情况；决策变量一般有非负性要求，有的则没有。为了求解方便，特规定一种线性规划的标准形式，非标准型可以转化为标准型。标准形式为：目标函数极大化 约束条件为等式 右端常数项bi0 决策变量非负。一一、标准型、标准型1.代数式二、标准型的表达方式二、标准型的表达
13、方式 有代数式、矩阵式：有代数式、矩阵式：maxZ=c1x1+c2x2+cnxn a11x1+a12x2+a1nxn b1 a21x1+a22x2+a2nxn b2 am1x1+am2x2+amnxnbm x1,x2,xn 0maxZ=cjxj aijxjbi (i=1,2,m)xj0 (j=1,2,n)nj1nj1简记2.矩阵式矩阵式 0.maxXbAXtsXCZ),(21ncccC价值向量mnmmnnaaaaaaaaaA212222111211技术矩阵mbbbb21资源向量nxxxX21决策向量 目标函数为 min z=c1x1+c2x2+cnxn 令z=-z,变为 max z=-c1x1
14、-c2x2-cnxn 两端同乘以-1 当约束方程为“”时，左端加入一个非负的松弛变量，就把不等式变成了等式；当约束条件为“”时，不等式左端减去一个非负的剩余变量(也可称松弛变量)即可。令xk=xk-x k，其中xk，x k 0，用xk、x k 取代模型中xk三、非标准型向标准型转化三、非标准型向标准型转化 标准型 例例1 maxZ=3x1+5 x2 x1 8 2x2 12 3x1+4 x2 36 x1 0,x2 0S.t.x1 +x3 =8 2x2 +x4 =12 3x1+4 x2 +x5=36 x1,x2,x3,x4,x5 0 maxZ=3x1+5 x2+0 x3+0 x4+0 x5 min
15、Z=x1+2 x2+3 x3 x1+2 x2+x35 2x1+3 x2+x36 -x1 -x2 -x3-2 x1 0,x30 例例2 minZ=x1+2 x2-3 x3 x1+2 x2-x3 5 2x1+3 x2-x3 6 -x1 -x2 +x3 -2 x1 0,x3 0 标准化标准化1S.t.标准化标准化2 minZ=x1+2(x2-x 2)+3 x3 x1+2(x2-x 2)+x35 2x1+3(x2-x 2)+x36 -x1 -(x2-x 2)-x3-2 x1,x2,x 2,x3 0 标准化标准化3 minZ=x1+2(x2-x 2)+3 x3 x1+2(x2-x 2)+x35 2x1+
16、3(x2-x 2)+x36 x1+(x2-x 2)+x3 2 x1,x2,x 2,x3 0 标准化标准化4 minZ=x1+2(x2-x 2)+3 x3 x1+2(x2-x 2)+x3+x4=5 2x1+3(x2-x 2)+x36 x1+(x2-x 2)+x3 2 x1,x2,x 2,x3,x4 0 标准化标准化5 minZ=x1+2(x2-x 2)+3 x3 x1+2(x2-x 2)+x3+x4 =5 2x1+3(x2-x 2)+x3 -x5=6 x1+(x2-x 2)+x3 2 x1,x2,x 2,x3,x4,x5 0 标准化标准化6 minZ=x1+2(x2-x 2)+3 x3 x1+2
17、(x2-x 2)+x3+x4 =5 2x1+3(x2-x 2)+x3 -x5 =6 x1+(x2-x 2)-x3 +x6=2 x1,x2,x 2,x3,x4,x5,x6 0 标准化标准化7 maxZ=-x1-2(x2-x 2)-3x3+0 x4+0 x5+0 x6 x1+2(x2-x 2)+x3+x4 =5 2x1+3(x2-x 2)+x3 -x5 =6 x1+(x2-x 2)-x3 +x6 =2 x1,x2,x 2,x3,x4,x5,x6 0 可行解：满足约束条件AX=b,X0的解。最优解：使目标函数达到最大的可行解，称为最优解。基 设A是约束方程组的mn维系数矩阵，其秩为m，B是矩阵A中的
18、mm阶非奇异子矩阵，则称B是线性规划问题的一个基。mn，且m个方程线性无关，即矩阵A的秩为m；根据线性代数定理可知，nm，则方程组有多个解，这也正是线性规划寻求最优解的余地所在。一、线性规划解的概念一、线性规划解的概念 1.4 线性规划问题的解的概念线性规划问题的解的概念 线性方程组的增广矩阵 例例 maxZ=3x1+5 x2+0 x3+0 x4+0 x5 x1 +x3 =8 2x2 +x4 =12 3x1+4 x2 +x5=36 x1,x2,x3,x4,x5 036101201800043020101Ax1x2x3x4x5 基矩阵：系数矩阵A中任意m列所组成的m阶非奇异子矩阵，称为该线性规划
19、问题的一个基矩阵。或称为一个基，用B表示。称基矩阵的列为基向量，用Pj表示(j=1,2,m)。100100043020101A的基矩阵的基矩阵B最多最多C53=10，如下：，如下：100010001x3x4x5103010001x1x4x5104012000 x2x4x5130000011x3x1x5140020001x3x2x5300010101x3x4x1400210001x3x4x2043020101x1x2x5x1x2x4043120001x1x2x5143020001 基变量：与基向量Pj相对应的m个变量xj称为基变量，其余的m-n个变量为非基变量。基解：令所有非基变量等于零，对m个
20、基变量所求的解 对应一个特定的基矩阵能求得一组唯一解，这个对应于基的解称为基解。结合图解来看，基解是各约束方程及坐标轴之间交点的坐标。100010001Bx3x4x5基变量是基变量是x3,x4,x5非基变量是非基变量是x1,x2令非基变量令非基变量x1=x2=0，得到一个基解，得到一个基解 x3=8，x4=12，x5=36 基可行解：满足非负性约束的基解称为基可行解。可行基：对应于基可行解的基，称为可行基。最优基：最优解对应的基矩阵，称为最优基。非可行解可行解基解基可行解.若线性规划问题存在可行域，则其可行域一定是凸集凸集。.线性规划问题的基可行解对应可行域的顶点顶点。.若可行域有界，线性规划
21、的目标函数一定可以在可行域的顶点顶点上达到最优。二、线性规划的基本定理二、线性规划的基本定理 线性规划问题可以有无数个可行解，最优解只可能在线性规划问题可以有无数个可行解，最优解只可能在顶点上顶点上达到，而有限个顶点对应的是基可行解，故只达到，而有限个顶点对应的是基可行解，故只要在有限个基可行解中寻求最优解即可。要在有限个基可行解中寻求最优解即可。从一个顶点出发找到一个可行基，得到一组基可行解，从一个顶点出发找到一个可行基，得到一组基可行解，拿目标函数做尺度衡量一下看是否最优。拿目标函数做尺度衡量一下看是否最优。如若不是，则向邻近的顶点转移，换一个基再行求解、如若不是，则向邻近的顶点转移，换一
22、个基再行求解、检验，如此迭代循环目标值逐步改善，直至求得最优检验，如此迭代循环目标值逐步改善，直至求得最优解。解。三、线性规划的解题思路三、线性规划的解题思路 例maxz=2x1+3x2St:X1+2x2+x3 =8 4x1 +x4 =16 4x2 +x5=12 Xi=0 1 2 1 0 0 A=4 0 0 1 0 0 4 0 0 1令非基变量X4=X5=0，则可解出X1=4,X2=3,X3=-2所以得出基解 X1=（4，2，-2，0，0），但由于X30,所以X2是可行解，相应的B2为可行基若用以上方法可枚举出此线性规划问题的基可行解分别为X3(4,0,4,0,12)，X4(0,3,2,16,
23、0)，X5（2，3，0，8，0）和X6（4，2，0，0，4），将这些解代入目标函数，可知X6可使得Z最大，所以X6为最优解2 单纯形法单纯形法 单纯形法的思路：先找到一个初始可行基，求出这个基可行解，然后判断该基可行解是否为最优解，若是最优解，则求解结束，若不是，则进行基变换，得到一个新的可行基，再进行判断该基可行解是否为最优解。每次基变换后的目标函数不断增大，一直到找到最优解为止。单纯形法基本思路是否最优解求最优目标函数值是基变换,迭代否确定初始可行解2.1单纯形法的原理例：maxz=2X1+3X2+0X3+0X4+0X5 st X1+2X2+X3=8 4X1+X4=16 4X2+X5=12
24、 Xj 0系数子矩阵 1 2 1 0 0A=（P1 P2 P3 P4 P5）=4 0 01 0 0 4 0 0 1初始可行基 1 0 0 B1=0 1 0 0 0 1（1）所以：X3=8-X1-2X2 X4=16-4X1 X5=12-4X2将此代入目标函数将此代入目标函数Z=2X1+3X2，令非基变量等于，令非基变量等于0，则得到一个基可行解则得到一个基可行解X0=（0 0 8 16 12），目标函数），目标函数值等于值等于0。但是从目标函数可知，因。但是从目标函数可知，因X1，X2的价值系的价值系数均大于数均大于0，当，当X1或或X2由非基变量变成基变量时，目由非基变量变成基变量时，目标函数
25、就会增加，所以此解并非最优解。标函数就会增加，所以此解并非最优解。将x2换入，x2换入后，需从X3,X4,X5中换出一个变量，并保证所有变量非负X3=8-2X2 X4=16X5=12-4X2当X2增大时，要满足X3，X4，X5 0，所以x2的最大只能取3，且此时x5为换出变量（2）基变换 新基变量为（X3，X4，X2），得X3=2-X1+0.5X5X4=16-4X1X2=3-0.25X5代入目标函数得Z=9+2X1-0.75X5因为x1的系数为正，依然不是最优解，换入x1，再经过迭代最后的最优解（4 2 0 0 4）2.2单纯形法求解单纯形法求解（1）初始基可行解的确定）初始基可行解的确定a
26、直接观察法直接观察法b 构造法构造法 形式，加松弛变量形式，加松弛变量 形式形式,减松弛变量后加人工变量（具体求解要用大减松弛变量后加人工变量（具体求解要用大法或二阶段法）法或二阶段法）目的目的:使初始可行基为单位阵使初始可行基为单位阵,令非基变量等于零令非基变量等于零,因为因为b0,b0,即可以得到初始基可行解即可以得到初始基可行解.（2）最优性检验与解的判）最优性检验与解的判别别四种情况四种情况:唯一最优解唯一最优解 无穷多最优解无穷多最优解 无界解无界解 无可行解无可行解 一般情况下一般情况下,经过迭代后经过迭代后jnmjmiijijimiijnmjijiixaccbczmixabx)(
27、),2,1(1111z0j 对于对于 a.最优解的判别定理最优解的判别定理:若若 为对应于基为对应于基B的一个基可行解的一个基可行解,且对于一切且对于一切j=m+1,n有有j j0,0,则则 为最优解为最优解.称称j j为检验数为检验数.21)0()0,0,(mbbbX)0(Xnmjjjxzz10 证明证明:因对一切非基变量的角下标因对一切非基变量的角下标j，均有均有00，显然，对于任一可行解，显然，对于任一可行解均有均有zzzz0 0,但基本可行解但基本可行解 能使能使等式成立，故为最优解等式成立，故为最优解)0(X)0(Xjb.无穷多最优解的判别定理无穷多最优解的判别定理:若若 为一个基可
28、行解为一个基可行解,且对于一切且对于一切j=m+1,n有有j j0,0,又存在某个非基变量的检验数又存在某个非基变量的检验数m+km+k=0,=0,则线性规划问题有无穷多最优解则线性规划问题有无穷多最优解21)0()0,0,(mbbbXc.无界解（无有限最优解）判别定理无界解（无有限最优解）判别定理若若为一基可行解，有一个为一基可行解，有一个m+km+k，并且对，并且对i=1,2,mi=1,2,m有有a ai,m+ki,m+k0,0,那么该线性规划问题具有无界解（无最那么该线性规划问题具有无界解（无最优解）优解）21)0()0,0,(mbbbXd.无可行解无可行解 约束条件相互矛盾，可行域为空
29、集约束条件相互矛盾，可行域为空集 最终计算表中人工变量仍然为基变量最终计算表中人工变量仍然为基变量（3）基变换）基变换 当初始基可行解不是最优解及不能判别无界时当初始基可行解不是最优解及不能判别无界时,需要找需要找一个新的基可行解一个新的基可行解,具体是从原可行解基中换一个列向具体是从原可行解基中换一个列向量量,得到一个新的可行基得到一个新的可行基,称为基变换称为基变换.基变换的关键是如何选择换入变量和换出变量这两个基变换的关键是如何选择换入变量和换出变量这两个问题问题.(原则和原则和原则原则)a.a.换入变量：当换入变量：当j0时取时取j中最大的所对应的非基变量中最大的所对应的非基变量x x
30、k k。b.b.换出变量：换出变量：=b=bi i/a/aikik(a(aikik0)0)中最小的所对应的中最小的所对应的x xl l为为换出变量。换出变量。经过基变换得到的解是基可行解经过基变换得到的解是基可行解,目标函数值增加目标函数值增加（4）迭代运算）迭代运算 将将xk和和xl进行对换，即把进行对换，即把Pk变为单位列向量取代变为单位列向量取代Pl,可可通过系数矩阵的增广矩阵的初等变换来实现通过系数矩阵的增广矩阵的初等变换来实现 将增广矩阵的第将增广矩阵的第l行除以行除以alk 将将k列除列除alk变换为变换为1以外，其他都变成以外，其他都变成0。alk称之为主元素，称之为主元素，k列
31、成为主元列，列成为主元列，l行称为主远行。行称为主远行。2.3 单纯形表 单纯形表，是对上节讨论的方法步骤进行具体化、规范化、表格化的结果。CjCBCB1CB2CBn检验数jXBxB1xB2xBnbb1b2bm-ZC1x1a11a21am11C2x2a12a22am22Cjxja1ja2jamjjCnxna1na2namnn比值12m将线性规划问题化成标准型。找出或构造一个m阶单位矩阵作为初始可行基，建立初始单纯形表。计算各非基变量xj的检验数j=Cj-CBPj，若所有j0，则问题已得到最优解，停止计算，否则转入下步。在大于0的检验数中，若某个k所对应的系数列向量Pk0，则此问题是无界解，停止
32、计算，否则转入下步。根据maxjj0=k原则，确定xk为换入变量(进基变量)，再按规则计算：=minbi/aik|aik0=bl/aik 确定xBl为换出变量。建立新的单纯形表，此时基变量中xk取代了xBl的位置。以aik为主元素进行迭代，把xk所对应的列向量变为单位列向量，即aik变为1，同列中其它元素为0，转第 步。单纯形法的计算步骤单纯形法的计算步骤 maxZ=3x1+5 x2+0 x3+0 x4+0 x5=0 x1 +x3 =8 2x2 +x4 =12 3x1+4 x2 +x5=36 单纯形法计算举例单纯形法计算举例CjCB检验数jXBb比值x1x2x3x4x5350008101001
33、2020103634001x3x4x5000035000-12/2=636/4=9miijBjjaCCi1检验数j81010060101/2012300-21x3x2x5050-30300-5/208-4CjCB检验数jXBb比值x1x2x3x4x53500081010012020103634001x3x4x5000035000-12/2=636/4=9CjCB检验数jXBb比值x1x2x3x4x53500081010060101/2012300-21x3x2x5050-30300-5/208-4检验数j40012/3-1/360101/204100-2/31/3x3x2x1053-42000
34、-1/2-1最优解最优解:X*=(4,6,4,0,0)T，Z*=42 最优基 CjCB053检验数jXBx3x2x1b464-423x100105x201000 x310000 x42/31/2-2/3-1/20 x5-1/301/3-1比值340020101*Bx3x2x1313200210313211*B 最优基的逆最优基的逆 最优基和最优基的逆最优基和最优基的逆又例又例Max z=2x1+3x2 x1+2x2+x3 =8 4x1 +x4 =16 4x2 +x5=12 x1,x2,x3,x4,x50 此问题的最优解为此问题的最优解为:x1*=4,x2*=2,x5*=4,x3*=x4*=x1
35、*=0,z*=2 4+3 2=14例Max z=2x1+3x2 x1+2x2 8 4x1 16 4x2 12 x1,x2 0 例如例如maxZ=3x1+2 x2 -2x1+x2 2 x1-3 x2 3 x1,x2 0S.t.标准化标准化 maxZ=3x1+2 x2-2x1+x2+x3 =2 x1-3 x2 +x4=3 x1,x2,x3,x4 0CjCB检验数jXBb比值x1x2x3x432002-211031-301x3x40003200-3检验数j80-512x3x103-31-301-90110-3 此时，检验数2=11 0，还没有得到最优解。确定x2进基，但x2所在列的系数向量元素非正，
36、无界 值不存在，有进基变量但无离基变量。用单纯形法解题时，需要有一个单位矩阵作为初始基。当约束条件都是“”时，加入松弛变量就形成了初始基。但实际存在“”或“”型的约束，没有现成的单位矩阵。采用人造基的办法：采用人造基的办法：在没有单位列向量的等式约束中加入人工变量，构成原线性在没有单位列向量的等式约束中加入人工变量，构成原线性规划问题的伴随问题，从而得到一个初始基。规划问题的伴随问题，从而得到一个初始基。人工变量是在等式中人为加进的，只有它等于人工变量是在等式中人为加进的，只有它等于0时，约束条件时，约束条件才是它本来的意义。才是它本来的意义。处理方法有两种：处理方法有两种：大大M 法法 两阶
37、段法两阶段法3.单纯形法的进一步讨论 没有单位矩阵，不符合构造初始基的条件，需加入人工变量。人工变量最终必须等于0才能保持原问题性质不变。为保证人工变量为0，在目标函数中令其系数为-M。M为无限大的正数，这是一个惩罚项，倘若人工变量不为零，则目标函数就永远达不到最优，所以必须将人工变量逐步从基变量中替换出去。如若到最终表中人工变量仍没有置换出去，那么这个问题就没有可行解，当然亦无最优解。大大M法法 例如例如 maxZ=3x1-x2-2 x3 3x1+2 x2-3 x3=6 x1 -2 x2+x3=4 x1,x2,x3 0S.t.按大按大M法构造人造基，引入人工变量法构造人造基，引入人工变量x4
38、,x5 的辅助问题如下：的辅助问题如下：maxZ=3x1-x2 -2 x3-M x4-M x5 3x1+2 x2-3 x3 +x4 =6 x1 -2 x2+x3 +x5=4 x1,x2,x3,x4,x5 0CjCB检验数jXBb比值x1x2x3x4x53-1-2-M-M632-31041-210100-2-2M-13+4M-10Mx4x5-M-M24miijBjjaCCi1CjCB检验数jXBb比值x1x2x3x4x53-1-2-M-M632-31041-21013+4M-1-2-2M00 x4x5-M-M24检验数j212/3-11/3020-8/32-1/310-1-4M/31+2M-3-
39、8M/30 x1x53-M-1检验数j31-2/301/61/210-4/31-1/61/20-5/30-M-5/6-M-1/2x1x33-2用计算机处理数据时，只能用很大的数代替用计算机处理数据时，只能用很大的数代替M,可能可能造成计算机上的错误，故多采用两阶段法。造成计算机上的错误，故多采用两阶段法。第一阶段：第一阶段：在原线性规划问题中加入人工变量，构造如下模型：在原线性规划问题中加入人工变量，构造如下模型：0 00min11111111111mnmmnnmnmnnnnmnnxxbxxaxabxxaxaxxxxW两阶段法两阶段法 对上述模型求解（单纯形法），若对上述模型求解（单纯形法），
40、若W=0,W=0,说明问题存在基本可行解，可以进行说明问题存在基本可行解，可以进行第二个阶段；否则，原问题无可行解，停第二个阶段；否则，原问题无可行解，停止运算。止运算。第二阶段：在第一阶段的最终表中，第二阶段：在第一阶段的最终表中，去掉人工变量，将目标函数的系数换成原去掉人工变量，将目标函数的系数换成原问题的目标函数系数，作为第二阶段计算问题的目标函数系数，作为第二阶段计算的初始表（用单纯形法计算）。的初始表（用单纯形法计算）。单纯形法补遗 进基变量相持：单纯形法运算过程中，同时出现多个相同的j最大。在符合要求的j(目标为max：j0，min：j0)中，选取下标下标最最小小的非基变量为换入变
41、量；离基变量相持：单纯形法运算过程中，同时出现多个相同的最小值。继续迭代，便有基变量为0，称这种情况为。选取其中下标最大的基变量做为换出变量。多重最优解：最优单纯形表中，存在非基变量的检验数j=0。让这个非基变量进基，继续迭代，得另一个最优解。无界解：大于0的检验数中，若某个k所对应的系数列向量Pk0，则解无界。无可行解：最终表中存在人工变量人工变量是基变量。4.线性规划的运用线性规划的运用解解 先看有多少种裁料方案，再进行组合和选择。方案：先看有多少种裁料方案，再进行组合和选择。方案：套裁下料套裁下料 现要做一百套钢管现要做一百套钢管,每套要长为每套要长为2.9m、2.1m和和1.5m的钢管
42、各的钢管各一根。已知原料长一根。已知原料长7.4m，问应如何下料，使用的原料最省。，问应如何下料，使用的原料最省。设用方案设用方案,分分别裁原料钢管别裁原料钢管x1,x2,.x5根根,则：则：Min z=0 x1+0.1 x2+0.2 x3+0.3x4+0.8x5x1+2x2 +x4 =100 2x3+2x4+x5=100 3x1+x2+2x3 +x5=100 x1,x2,x3,x4,x5 0 例例 某工厂要用三种原材料某工厂要用三种原材料C,P,HC,P,H混合调配出三种不同规格的产混合调配出三种不同规格的产品品A,B,DA,B,D。已知产品的规格要求、单价和原料的供应量、单价如。已知产品的
43、规格要求、单价和原料的供应量、单价如下表。该厂应如何安排生产，能使利润最大？下表。该厂应如何安排生产，能使利润最大？产产品品名名规规格格要要求求单单价价A原原料料 C 不不少少于于 50%原原料料 P 不不超超过过 25%50 元/KGB原原料料 C 不不少少于于 25%原原料料 P 不不超超过过 50%35 元/KGD不不限限25 元/KG配料问题配料问题根据产品要求有：根据产品要求有：AC0.5A,AP0.25A BC0.25B,BP0.5B AC+AP+AH=A BC+BP+BH=B根据原料供应量有：根据原料供应量有：AC+BC+DC100 AP+BP+DP100 AH+BH+DH60设
44、设AC,AP,DH分别为分别为x1,x2,x9，有，有Max z=50(x1+x2+x3)+35(x4+x5+x6)+25(x7+x8+x9)-65(x1+x4+x7)-25(x2+x5+x8)-35(x3+x6+x9)x10.5(x1+x2+x3)x2 0.25(x1+x2+x3)x4 0.25(x4+x5+x6)x5 0.5(x4+x5+x6)x1+x4+x7100 x2+x5+x8100 x3+x6+x960 xj0,j=1,2,3,4,5,6,7,8,9解：记产品解：记产品A A、B B、D D中中C C、P P、H H的含量分别为：的含量分别为：AC、AP、AH、BC、BP、BH、D
45、C、DP、DH。例例 某单位有资金某单位有资金10万元，在今后万元，在今后5年内可考虑下列投资项目，年内可考虑下列投资项目，已知：已知：项目项目A：从第：从第1到第到第4年每年初可投资，并于次年末回收本利年每年初可投资，并于次年末回收本利115%；项目项目B：第：第3年初需要投资，到第年初需要投资，到第5年末回收本利年末回收本利125%，但最，但最大投资额不超过大投资额不超过4万元；万元；项目项目C：第：第2年初需要投资，到第年初需要投资，到第5年末能回收本利年末能回收本利140%，但，但最大投资额不超过最大投资额不超过3万元；万元；项目项目D：5年内每年初可购买公債，当年末回收本利年内每年初
46、可购买公債，当年末回收本利106%。问它应该如何安排每年的投资，使到问它应该如何安排每年的投资，使到5年末拥有的资金最多？年末拥有的资金最多？投资计划投资计划 x2A+x2C+x2D=1.06x1D解：每年的投资额应不超过手中的资金。由于项目解：每年的投资额应不超过手中的资金。由于项目D每每年都可投资，且当年末就可收回。所以该单位每年必年都可投资，且当年末就可收回。所以该单位每年必然把资金全部投出去，即投资额等于手中的资金数。然把资金全部投出去，即投资额等于手中的资金数。设第设第i年投资各项目的资金为年投资各项目的资金为xiA、xib、xiC、xiD，数学，数学模型为：模型为：Max z=1.
47、15x4A+1.4x2C+1.25x3B+1.06x5D x1A+x1D=10 x3A+x3B+x3D=1.15x1A+1.06x2Dx4A+x4D=1.15x2A+1.06x3D x5D=1.15x3A+1.06x4DxiA,xib,xiC,xiD0例某昼夜服务的公交线路每天各时间段内所需司机和乘务人员数如下：设司机和乘务人员分别在各时间段一开始时上班，并连续工作八小时，问该公交线路怎样安排司机和乘务人员，既能满足工作需要，又配备最少司机和乘务人员?人力资源分配的问题人力资源分配的问题解：设 xi 表示第i班次时开始上班的司机和乘务人员数,这样我们建立如下的数学模型。目标函数：Min x1+
48、x2+x3+x4+x5+x6 约束条件：s.t.x1+x6 60 x1+x2 70 x2+x3 60 x3+x4 50 x4+x5 20 x5+x6 30 x1,x2,x3,x4,x5,x6 0 例：明兴公司生产甲、乙、丙三种产品，都需要经过铸造、例：明兴公司生产甲、乙、丙三种产品，都需要经过铸造、机加工和装配三个车间。甲、乙两种产品的铸件可以外包协作，机加工和装配三个车间。甲、乙两种产品的铸件可以外包协作，亦可以自行生产，但产品丙必须本厂铸造才能保证质量。数据亦可以自行生产，但产品丙必须本厂铸造才能保证质量。数据如下表。问：公司为了获得最大利润，甲、乙、丙三种产品各如下表。问：公司为了获得最
49、大利润，甲、乙、丙三种产品各生产多少件？甲、乙两种产品的铸造中，由本公司铸造和由外生产多少件？甲、乙两种产品的铸造中，由本公司铸造和由外包协作各应多少件？包协作各应多少件？生产计划生产计划解：设 x1,x2,x3 分别为三道工序都由本公司加工的甲、乙、丙三种产品的件数，x4,x5 分别为由外协铸造再由本公司机加工和装配的甲、乙两种产品的件数。求 xi 的利润：利润=售价-各成本之和可得到 xi（i=1,2,3,4,5）的利润分别为15、10、7、13、9元。这样我们建立如下的数学模型。目标函数：Max 15x1+10 x2+7x3+13x4+9x5 约束条件：s.t.5x1+10 x2+7x3
50、 8000 6x1+4x2+8x3+6x4+4x5 12000 3x1+2x2+2x3+3x4+2x5 10000 x1,x2,x3,x4,x5 0练习：某厂生产练习：某厂生产、三种产品，均要经过三种产品，均要经过A A、B B 两道工序两道工序加工。假设有两种规格的设备加工。假设有两种规格的设备A A1 1、A A2 2能完成能完成 A A 工序；有三种工序；有三种规格的设备规格的设备B B1 1、B B2 2、B B3 3能完成能完成 B B 工序。工序。可在可在A A、B B的任何规的任何规格的设备上加工；格的设备上加工；可在任意规格的可在任意规格的A A设备上加工，但对设备上加工，但对
