运筹学线性规划

1、第一章 线性规划(Linear Programming, LP),2005年7月 龙子泉,概 述,线性规划问题的提出最早是1939年由前苏联数学家康托洛维奇在研究铁路运输的组织问题、工业生产的管理问题时提出来的。 1947年，美国学者丹西格（G.B.Dantzig）提出了线性规划问题的单纯形方法。 线性规划理论最为成熟、应用最为广泛,2005年7月 龙子泉,第一节 线性规划问题及其数学模型,一、问题提出 例1（生产计划问题）某企业利用A、B、C三种资源，在计划期内生产甲、乙两种产品，已知生产单位产品资源的消耗、单位产品利润等数据如下表，问如何安排生产计划使企业利润最大？,决策变量：x1、x2分

2、别代表甲、乙两种产品的生产数量。 目标函数：max z=50 x1+100 x2 约束条件： x1 + x2300 2x1 + x2400 x2250 即有： max z=50 x1+100 x2 x1 + x2300 2x1 + x2400 x2250 x1、x20 称之为上述问题的数学模型。,例2 靠近某河流有两个化工厂，流经第一化工厂的河流流量为每天500万m3，在两个工厂之间有一条流量为200万m3的支流。两化工厂每天排放某种有害物质的工业污水分别为2万m3和1.4万m3。从第一化工厂排出的工业污水流到第二化工厂以前，有20%可以自然净化。环保要求河流中工业污水含量不能大于0.2%。两

3、化工厂处理工业污水的成本分别为1000元/万m3和800元/万m3。现在要问在满足环保要求的条件下，每厂各应处理多少工业污水，使这两个工厂处理工业污水的费用最小.,决策变量：x1、x2分别代表工厂1和工厂2处理污水的数量(万m3)。 则目标函数：min z=1000 x1+800 x2 约束条件： 第一段河流（工厂1工厂2之间）： (2x1)/500 0.2% 第二段河流： 0.8(2x1) +(1.4x2)/7000.2% 此外有： x12； x21.4 化简有： min z=1000 x1+800 x2 x1 1 0.8x1 + x2 1.6 x1 2 x21.4 x1、x20 称之为上述

4、问题的数学模型。,从上述两个例子，我们可以总结出线性规划的数学模型的一般形式。 max(min) z=c1x1+c2x2+cnxn 目标函数 a11x1+a12x2+a1nxn= (,) b1 a21x1+a22x2+a2nxn= (,) b2 约束条件 am1x1+am2x2+amnxn= (,) bm x1，x2，xn0 模型特点：目标函数(Objective function)与约束条件(Constraint)均为线性的；目标函数实现极大化或极小化。,2005年7月 龙子泉,第二节 线性规划图解法 (Graphical Solution),一、基本概念 可行解(Feasible Solu

5、tion)任一满足约束条件的一组决策变量的数值； 可行域(Feasible Region)所有可行解组成的集合，也称为可行解集； 目标函数等值线(Objective function line)为于同一直线上的点，具有相同的目标函数值； 二、图解法步骤(Procedure) （1）画出线性规划问题的可行域； （2）画出两条目标函数等值线； （3）平行移动目标函数等值线，使目标函数在可行域范围内达到最优。,三、图解法举例,例1 max Z=50 x1+100 x2 x1 + x2300 2x1 + x2400 x2250 x1、x20,该问题有唯一最优解 x1=50；x2=250,例2 max

6、Z=50 x1+50 x2 x1 + x2300 2x1 + x2400 x2250 x1、x20,B点和C点所代表的坐标同时为最优解，即该问题有无穷多最优解,max Z=50 x1+100 x2,例3 max z =x1+x2 x1x2 1 x1 + 2x20 x1、x20 问题有无界解 (unbounded) 例4 min z =x1+x2 x1x2 1 x1 + 2x20 x1、x20 有唯一最优解,例4 max z =x1+x2 x1 + 2x21 x1 + x22 x1、x20 问题无可行解 (no feasible solution),2005年7月 龙子泉,直 观 结 论,可行域

7、可以是个凸多边形，可能无界，也可能为空； 若线性规划问题的最优解存在，它一定可以在可行域的某一个顶点上得到； 若在两个顶点上同时得到最优解，则该两点连线上的所有点都是最优解，即LP有无穷多最优解； 若可行域非空有界，则一定有最优解。,2005年7月 龙子泉,四、线性规划问题的标准形式(Standard form),规定如下形式的线性规划数学模型为LP标准形式。 max z=c1x1+c2x2+cnxn 目标函数 a11x1+a12x2+a1nxn= b1 a21x1+a22x2+a2nxn= b2 约束条件 am1x1+am2x2+amnxn= bm x1，x2，xn0 特点：Zmax；约束条

8、件为等号；变量非负；右端常数项大等于零。 问题：n m why？,2005年7月 龙子泉,上述标准形式的线性规划模型还可写成如下一些形式:,(1) (2),(3),(5),(4),2005年7月 龙子泉,五、化非标准形为标准形,（1）若min f=cX 此时可令：z =f，则max z=min f =cX，这样处理所得最优解不变； 举例： min z =x1x2 2x1 + x22 x1 + x21 x1、x20 max f =x1+ x2,(2)约束条件为“”时， aijxjbi aijxj + xn+i = bi xn+i 松弛变量(slack variable)； (3)约束条件为“”时

9、， aijxj bi aijxj xn+i = bi xn+i 过剩变量(surplus variable)； 这样处理所得最优解不变； max z =x1+10 x2 x1 + 2x2100 x1、x20,max z =x1+10 x2 x1 + 2x2 + x3=100 x1、x20,（4）若xk为无限制， 则令xk=xk1xk2，其中xk1、xk20 （5）若bi 0 举例: 化下列线性规划为标准形 max z=2x1+2x24x3 x1 + 3x23x3 30 x1 + 2x24x380 x1、x20，x3无限制,max z=2x1+2x24x3+4x3” x1 + 3x23x3+3x

10、3” x4 = 30 x1 + 2x24x3+ 4x3” + x5 = 80 x1、x2 、x3、x3” 、x4、x5 0,2005年7月 龙子泉,第三节 线性规划问题解的性质 (Properties of Solution of LP),一、线性规划问题的基本概念(concepts) 对于标准形式的线性规划： max z=cX （a） AX=b X0 （b） 可行解(feasible solution)满足约束条件（b）的点X=（x1，x2，xn）T称为该LP的一个可行解； 最优解(optimal solution)使目标函数值达到最大的可行解,3基、基变量、非基变量 (base, basi

11、c variable, nonbasic variable),设约束方程的系数矩阵A中，有m个线性无关的列向量， 且设 B=（P1，P2，Pm）线性无关，则称B为该LP的一个基； 相应的 P1，P2，Pm为基向量； 与之对应的变量 x1，x2，xm基变量，记为：XB= （x1，x2，xm）T ； 其余的向量为非基向量，记为：N=（Pm+1，Pm+2，Pn）； 其余的变量为非基变量 ，记为：XN=（xm+1，xm+2，xn）T；,4基本解 (basic solution),将AX=b改写 （B，N）（XB，XN）T=b 有： BXB=bNXN 令 XN=0 得到 BXB=b 线性方程组。 由于B

12、中各列向量线性无关，因此解此方程组有唯一解 即： XB= （x10，x20，xm0）T 于是得到AX=b的一个确定的解： X0=（XB，XN）T =（x10，x20，xm0，0，0，0）T 称X0为该线性规划对应与基B的一个基本解。,同样，在A中任选m个线性无关的列向量都可以组成一个基，对应基一个基本解。对于一个LP最多有多少呢？从n个中选m个进行组合，即： Cnm=n！/（nm）！m！ 因此，基本解是有限的。 举例：找出下列LP所有的基及其对应的基本解 max z=6x1+4x2 2x1 + 3x2100 4x1 + 2x2120 x1、x20 解：化为标准型 max z=6x1+4x2+0

13、 x3+0 x4 2x1 + 3x2 + x3 =100 4x1 + 2x2 +x4 =120 x1、x2，x3，x4 0,2005年7月 龙子泉,二、线性规划的基本定理(Theorems),定义 凸集设K是n维欧氏空间的一个点集，若任意两点X(1)K，X(2)K的连线上所有的点X=X（1）+（1）X（2）K，（01），则称K为凸集。 定理1 若线性规划存在可行域，则其可行域R=X|AX=b，X0是凸集。 定理2 线性规划问题的可行解X=（x1，x2，xn）T为基可行解的充要条件是：X的非零分量所对应的系数列向量是线性无关的。 定理3 如果线性规划有可行解，则一定有基可行解。 定理4 线性规划

14、问题的基可行解对应于可行域的顶点。 定理5 若线性规划问题的可行域非空有界，则线性规划问题的最优解一定可以在其可行域的某个顶点上得到；,2005年7月 龙子泉,第四节 单纯形法 (simplex method) (教材第五章P162-168),基本思想：在有限的基可行解中寻找最优解。即，从初始基可行解出发，转换到另一个基可行解，使目标值增大，直到达到最优解，或判断出无最优解为止。 一、引例 用单纯形方法求解下列线性规划 max z=6x1+4x2 2x1 + 3x2100 4x1 + 2x2120 x1、x20 解：化为标准型 max z=6x1+4x2+0 x3+0 x4 2x1 + 3x2

15、 + x3 =100 4x1 + 2x2 +x4 =120 x1、x2，x3，x4 0,（1）找初始可行基：B1=（P3，P4）现成的初始可行基； 此时， XB=（x3，x4）T，XN=（x1，x2）T 用XN表示Z和XB有： max z=6x1+4x2 x3 =1002x13x2 +x4 =1204x12x2 令 XN=(0,0)T 有 XB=(100,120)T 则有： X（1）=（0，0，100，120）T为对应于基B1的基可行解。 问： X（1）是否最优呢？否 因为： x1和x2在目标函数中的系数为正，当x1，z；x2，z。 且： 称非基变量在目标函数中的系数为检验数。,（2）寻找可行

16、基B2，使其对应的基可行解X（2）能使目标函数值增加。 选： x10 则有： X（2）=（x1，0，x3，x4）T 要使为X（2）基可行解，x3，x4中必有一个为零，而另一个大等于零。 只要取 x1=min100/2，120/4=30 就有 x3=40，x4=0 这样 X（2）=（30，0，40，0）T 因为 P1，P3线性无关，因此，B2=（P1，P3）为一个基 而 X（2）为对应于B2的基可行解 此时 XB=（x1，x3）T，XN=（x2，x4）T 用XN表示Z和XB有： max z=180+2x2（3/2）x4 x1 = 30（1/2）x2（1/4）x4 x3 = 40 2 x2 +（1

17、/2）x4 问： X（2）是否最优呢？否 因为： x2在目标函数中的系数为正，当x2，z。,（3）寻找可行基B3，使其对应的基可行解X（3）能使目标函数值增加。 选： x20 则有： X（3）=（x1，x2，x3，0）T 要使为X（3）基可行解，x1，x3中必有一个为零，而另一个大等于零。 只要取 x2=min30/（1/2），40/2=20 就有 x1=20，x3=0 这样 X（3）=（20，20，0，0）T 因为 P1，P2线性无关，因此，B3=（P1，P2）为一个基 而 X（3）为对应于B3的基可行解 此时 XB=（x1，x2）T，XN=（x3，x4）T 用XN表示Z和XB有： max

18、z=2001/2）x3（5/4）x4 x1 =20 +（1/4）x3 （3/8）x4 x2 =20 （1/2）x3 +（1/4）x4 问： X（3）是否最优呢？是， 求解过程：从引例可以总结出求解过程：（1）找出初始基及其基可行解；（2）判断是否为最优解，是停止，否则转下一步；（3）转换可行基，并求出相应的基可行解，使目标函数值有所改进，转（2）。,2005年7月 龙子泉,二、单纯形方法 1检验数( evaluation index),检验数用非基变量表示目标函数后，非基变量在目标函数中的系数 设有标准形式的线性规划问题：max z=cX；AX=b，X0； 现假定 A中存在一可行基B 又设 B

19、=（P1，P2，Pm）；且B为单位阵 这样 AX=b可以描述成如下形式，也就是用非基变量表示基变量 x1 + a1,m+1xm+1 + + a1nxn=b1 x2 + a2,m+1xm+1 + + a2nxn=b2 xm + am,m+1xm+1 + + amnxn=bm 即 从上述约束方程中可以得到对应于基B的基可行解 X=（b1，b2，bm，0，0）T,用非基变量表示目标函数有： 令 有 式中 j为基可行解X的检验数。 更一般性：,2005年7月 龙子泉,2最优性检验(optimality testing),判别定理1：设X为线性规划的一个基可行解，且对于一切jJ（J为非基变量的下标集）有

20、j0，则X为线性规划的最优解； 判别定理2：设X为线性规划的一个基可行解，且对于一切jJ（J为非基变量的下标集）有j0，同时有某个非基变量的检验数k=0（kJ），则该线性规划有无穷多最优解； 判别定理3：设X为线性规划的一个基可行解，若有k0（kJ），且Pk0，则该线性规划问题具有无界解（无最优解）。,3 单纯形表(simplex tableau),对于线性规划：max z=z0 + m+1xm+1 + + nxn x1 + a1,m+1xm+1 + + a1nxn=b1 x2 + a2,m+1xm+1 + + a2nxn=b2 xm + am,m+1xm+1 + + amnxn=bm x1，

21、x2，xn0 列如下单纯形表：,单纯形表的说明与功能： （1）一个基对应一个单纯形表，且单纯形表中必须有一个初始单位基。 （2）从单纯表中，可立即得到一个基可行解，如上表中： X=（b1，b2，bm，0，0）T为基可行解。 （3）很容易计算检验数，并可判别上述基可行解是否为最优解或线性规划问题无最优解。 4. 单纯形法计算步骤 （1）找出初始可行基，建立初始单纯形表； （2）计算检验数，若对于一切jJ有j0，则已得到线性规划的最优解，可停止计算，否则转下一步； （3）若有k0（kJ），且Pk0，则该线性规划问题具有无界解（无最优解），停止计算，否则转下一步； （4）根据maxj|j0=k，确定

22、xk为换入变量； 按规则确定换出变量，即 =bi/aik|aik0=bs/ask，对应的xs为换出变量，转下一步； （5）以ask为主元素进行迭代，得新的单纯形表，转（2）,2005年7月 龙子泉,三、单纯形法解题举例,例1：用单纯形法求解 max z=6x1+4x2 2x1 + 3x2100 4x1 + 2x2120 x1、x20 解：化为标准型 max z=6x1+4x2+0 x3+0 x4 2x1 + 3x2 + x3 =100 4x1 + 2x2 +x4 =120 x1、x2，x3，x4 0 找初始可行基：B1=（P3，P4）现成的初始可行基；,从表中有：X（1）=（0，0，100，1

23、20）T为对应于基B1的基可行解，显然不是最优解； 根据maxj|j0=1，确定x1为换入变量； 按规则确定换出变量，即：=bi/aik|aik0=120/4，对应的x4为换出变量；,列初始单纯形表,以4为主元素进行迭代，得新的单纯形表： 从表中有：X（2）=（30，0，40，0）T为对应于基B2的基可行解，显然不是最优解； 根据maxj|j0=2，确定x2为换入变量； 按规则确定换出变量，即：=bi/aik|aik0=40/2，对应的x3为换出变量；,表中j0，j=1，4， 因此得最优解：X*=（20，20，0，0）T，Z*=200,以2为主元素进行迭代，得新的单纯形表：,将上述计算列在一个

24、表中为：,Cj6400b CB XB x1x2x3x4 0 x3 2310100100/2 0 x4 4201120120/4(min) z 64000 0 x3021-1/24040/2(min) 6 x111/201/43030/(1/2) Z 010-3/8180 4 x2011/2-1/420 6 x110-1/43/820 Z00 -1/2-5/4200,例2：用单纯形法求解 max z=50 x1+100 x2 x1 + x2300 2x1 + x2400 x2250 x1、x20,例3：用单纯形法求解 max z=2x1+x2 x1 + x25 2x15x210 x1、x20 2

25、=6 0，且P20，故该线性规划有无界解。,例4：用单纯形法求解 max z=6x1+2x2+10 x3+8x4 5x1 + 6x24x34x420 3x13x2 +2x3 + 8x425 4x12x2 + x3 + 3x410 x1、x2、x3、x40 7=340, p70,故该LP有无解解,2005年7月 龙子泉,四、极小化问题(Minimization Problem),若标准形式的线性规划问题的目标函数是极小化形式，则问题的判别准则就会有所改变。这样三个判别定理如下： 判别定理1：设X为线性规划的一个基可行解，且对于一切jJ（J为非基变量的下标集）有j 0，则X为线性规划的最优解； 判

26、别定理2：设X为线性规划的一个基可行解，且对于一切jJ（J为非基变量的下标集）有j 0，同时有某个非基变量的检验数k=0（kJ），则该线性规划有无穷多最优解； 判别定理3：设X为线性规划的一个基可行解，若有k 0（kJ），且Pk0，则该线性规划问题具有无界解（无最优解）。,2005年7月 龙子泉,上述单纯形法的基础是线性规划问题有初始基可行解。有些线性规划问题化为标准形式以后，就存在初始可行基，如约束条件全部为“”的线性规划问题。对于标准形式的线性规划问题，若约束方程系数矩阵中不存在现成的初始可行基，则不能简单的用上述单纯形法，而通常采用所谓的人工变量法。人工变量法一般有大M法和两阶段法。,五

27、、人工变量法(Artificial Variable Method),（一）大M法(Big M method) 对于标准形式的线性规划问题（问题A） max z=c1x1+c2x2+cnxn a11x1+a12x2+a1nxn= b1 a21x1+a22x2+a2nxn= b2 am1x1+am2x2+amnxn= bm x1，x2，xn0 若其约束方程的系数矩阵中不存在现成的初始可行基，则引入所谓的人工变量xn+1，xn+m构造如下形式的线性规划问题（问题B） max z=c1x1+c2x2+cnxnMxn+1Mxn+m a11x1+a12x2+a1nxn+xn+1 = b1 a21x1+a

28、22x2+a2nxn +xn+2 = b2 am1x1+am2x2+amnxn +xn+m = bm x1，x2，xn，xn+1，xn+m0,问题B中M为任意大的正数。显然问题B存在现成的单位基，且初始基可行解中，以人工变量为基变量。 关于问题B的几点结论： （1）问题B要实现极大化，必须将人工变量从基变量中换出，否则目标函数不可能实现极大化； （2）若在求解问题B的过程中，已将人工变量从基变量中换出，则已得到问题A的一个基可行解，可继续求解，以获得问题A的最优解或判别问题A无最优解； （3）若求解问题B已得到最优解，但最优解的基变量中含有不为零人工变量，则问题A无可行解； （4）若求解问题B

29、已得到最优解，且最优解的基变量中不含有人工变量，则问题B的最优解就是问题A的最优解。,例：用单纯形法（大M法）求解 max z=3x12x2x3 x1 2x2 + x3 11 4x1 + x2 +2x3 3 2x1 x3 = 1 x1、x2、x30 解：化为标准形式，并引入人工变量，构造如下模型： max z=3x12x2x3Mx6Mx7 x12x2 + x3 + x4 = 11 4x1 + x2 +2x3 x5 + x6 = 3 2x1 x3 +x7 = 1 x1、x2、x30 列表计算：,（二）两阶段法 对于标准形式的线性规划问题（问题A） max z=c1x1+c2x2+cnxn a11

30、x1+a12x2+a1nxn= b1 a21x1+a22x2+a2nxn= b2 am1x1+am2x2+amnxn= bm x1，x2，xn0 若其约束方程的系数矩阵中不存在现成的初始可行基，则引入所谓的人工变量xn+1，xn+m构造如下辅助线性规划问题（问题C） min w =xn+1 + + xn+m a11x1+a12x2+a1nxn+xn+1 = b1 a21x1+a22x2+a2nxn +xn+2 = b2 am1x1+am2x2+amnxn +xn+m = bm x1，x2，xn，xn+1，xn+m0,关于问题C的几点结论： （1）由于问题C为极小化问题，且目标函数有下界，因此问题C肯定有最优解； （2）求解问题C已得到其最优解，若问题C最优解所对应目标函数值w0，则原问题A无可行解，若问题C所对应目标函数值w =0，则已得到原问题A的一个基可行解； 因此问题的求解有如下两