1、线性规划o数学教研室o石鸿雁引言o线性规划是数学规划的一个重要分支，历史比较悠久，理论比较成熟，方法较为完善。线性规划的思想最早可以追溯到1939年，当时的苏联数学家、经济学家（康特罗维奇）在生产组织与计划中的数学方法一书中提出了类似线性规划的模型，以解决下料问题和运输问题，并给出了“解决乘数法”的求解方法。然而，他们的长期工作未被人们知道。o由于战争的需要，美国的经济学家T.C.Koopmans（库普曼斯）重新独立的研究运输问题，并很快看到了线性规划在经济学中应用的意义。在这之后，线性规划也被广泛地应用于军事、经济等方面。由于他们在这方面的突出贡献，康特罗维奇和库普曼斯联合得到1975年诺贝
2、尔经济学奖。引言o对线性规划贡献最大的是美国数学家G.B.Dantig(丹捷格)，他在1947年提出了求解线性规划的单纯形法（Simple Method），并同时给出了许多很有价值的理论，为线性规划奠定了理论基础。在1953年，丹捷格又提出了改进单纯形法，1954年Lemke(兰母凯)提出了对偶单纯形法（dual simplex method）。o在1976年，R.G.Bland 提出避免出现循环的方法后，使线性规划的理论更加完善。但在1972年，V.Klee和G.Minmty构造了一个例子，发现单纯形法的迭代次数是指数次运算，不是好方法并不是多项式算法（多项式算法被认为是好算法），这对单纯形
3、法提出了挑战。引言o1979年，前苏联青年数学家（哈奇扬）提出了一种新算法椭圆算法，是一个多项式算法，这一结果在全世界引起了极大轰动，被认为是线性规划理论上的历史突破。然而在实际计算中，椭球算法的计算量与单纯形算法差不多，因此，椭球算法并不实用。o1984年，在美国的贝尔实验室工作的印度数学家N.Karmarkar(卡玛卡尔)又提出了一个多项式算法Karmarkar 算法，Karmarkar算法本质上属于内点法，这种算法不仅在理论上优于单纯形算法，而且也显示出对求解大规模线性规划问题的巨大潜力。o此外，1980年前后，形成求解线性规划的有效集法（active set method），在理论上有
4、效集法与单纯形法是等价的，但解决问题的侧重点不同，因此各有优缺点，起着相互补充的作用。引言o由于很多非常重要的实际问题都是线性的，即使不是至少能够用线性函数很好地近似，所以线性规划的研究是很有价值的。o另一方面，线性规划方面的工作与非线性规划领域相比更为成熟。目前，线性规划方法的发展已被用来求解非线性模型，所以掌握线性规划的理论和解法是本课程的重要目标之一。线性规划（LP）A1A2B1B2B3工地工地运价（元运价（元/万块）万块）砖厂砖厂50 60 7060 110 1601947年 美国数学家 Dantzig 单纯形法 理论基础1979年 苏联数学家 哈奇安 椭球法 理论上的突破1984年
5、美国数学家 Karmarkar Karmarkar算法 大规模 1.问题与模型1.1.数学模型 例1.设有A1，A2两个工厂，产量分别为23万块和27万块砖，供应三个工地B1，B2，B3，其需求量分别为17万块、18万块和15万块，而自产地到各工地的运价见表，问应如何调运，才能使总运费最小？圆桌 0.18 0.08 6衣柜 0.09 0.28 10产品 利润 木 料第一种 第二种解 设xij Ai运往Bj的运量（万块）minS=50 x11+60 x12+70 x13+60 x21+110 x22+160 x23S.t.x11+x12+x13=23x21+x22+x23=27x11+x21=1
6、7x12+x22=18x13+x23=15xij0,i=1,2、j=1,2,3 例2.某木器厂生产圆桌和衣柜两种产品，现有两种木料，第一种有72m3,第二种有56m3，生产圆桌和衣柜所需木料如下表。每生产一个桌子可获利润6元，生产衣柜可获利润10元。木料厂在现有木料的条件下，圆桌和衣柜各生产多少，才能使利润最大？解设生产圆桌x1个，衣柜x2个max S=6x1+10 x2s.t.0.18x1+0.09x2720.08x1+0.28x256x1,x20 线性规划问题：约束条件及目标函数均为未知量的线线性规划问题：约束条件及目标函数均为未知量的线性函数，求目标函数的最大或最小值问题。性函数，求目标
7、函数的最大或最小值问题。.2图解法（只限于两个变量）max S=c1x1+c2x2 s.t.a11x1+a12x2b1 a21x1+a22x2b2 x1,x20在平面上取一直角坐标系，它的两个坐标分别是x1,x2,把满足第一个方程的x1,x2看作平面的一个点，那么这个点应在什么地方呢？平面被直线a11x1+a12x2=b1 划分为两个平面，这个点一定在两个半平面的某一个上面。所有满足约束条件的点就构成一个区域K。现在，我们就是要在K中找一点（x10,x20），使目标函数达到最大。a21x1+a22x2=b2a11x1+a12x2=b1c1x1+c2x2=hA我们知道，把h作为参数的方程c1x1
8、+c2x2=h 表示一平行直线束，在K中任意取一点(x10,x20)，h=c1x1+c2x2=c1x10+c2x20 就表示这个直线束中通过（x10,x20）的一条直线。所以，我们要在K中找一点（x10,x20）使c1x10+c2x20为最大，就变成在直线束中找一条直线，这条直线既通过K中某一点，又使原点到这条直线的距离沿正法线方向达到最大。x2x1O那么，怎样找这条直线呢？让直线c1x1+c2x2=h 沿着它的正法线（梯度）方向移动，移动到刚刚开始要离开K的时候，这时的直线仍与K相交，也就是还通过K的点.总结：求最大，沿正法线方向移动。总结：求最大，沿正法线方向移动。求最小，沿负法线方向移动
9、。求最小，沿负法线方向移动。例1.max S=-x1+x2 s.t.2x1+x22 x1-2x22 x1+x25 x1,x20法线方向：,A(1,4)是S达到最大值的点。)21,21(x1+x2=5-2x1+x2=2x1-2x2=2A)51,52(例2min S=-2x1+x2 s.t.x1+x21 x1-3x2-3 x1,x20负法线方向：Ox1x2最小值为负无穷x1-3x2=-3x1+x2=1)101,103(例3Max S=3x1+x2 s.t.x1+x25 -x1+x20 6x1+2x221 x1,x20法线方向 ，此问题有无穷多个解.Ox1x2例4Max S=3x1+x2 s.t.x
10、1-x2-1 x1+x2-1 x1,x20此问题无可行解。Ox1x2-11-16x1+2x2=21x1+x2=5-x1+x2=0 x2x1O可在某一顶点上取得。总结：两个变量的线性规划问题的解有4种情况。1有唯一的最优解 2有最优解，但不唯一 （有无穷多个）3有可行解，但无最优解 4无可行解3 3标准形式min=c1x1+c2x2+cnxn s.t.a11x1+a12x2+a1nxn=b1 a21x1+a22x2+a2nxn=b2 am1x1+am2x2+amnxn=bm xj0;j=1,2,n bi0;i=1,2,m化一般问题为标准形式：(一)若ak1x1+ak2x2+aknxnbk 加一变
11、量xn+k0（松驰变量），改写为 ak1x1+ak2x2+aknxn+xn+k=bk若ak1x1+ak2x2+aknxnbk减一变量xn+k0(剩余变量），改写为 ak1x1+ak2x2+aknxn-xn+k=bk(二)若目标函数为max=c1x1+c2x2+cnxnmin=-=-(c1x1+c2x2+cnxn)（三）若xj0，令xj=xj-xj”,xj0,xj”0利用矩阵和向量的符号，线性规划问题可以写为a11 a12 a1n am1 am2 amnB=X=b1b2bmx1x2xnp1jp2jpmjPj=min=CX s.t.AX=b X0 min=CX s.t.xjPj=b X0 C=(c
12、1,c2,cn)A=mn.秩(A)=m4 线性规划问题的解可行解：满足约束条件的解最优解：使目标函数达到最大的可行解 基:若B是A中m*m阶非奇异子矩阵，(|B|0)，则称B是一个基，相应于B的变量称为基变量。B被称为一个基，是由于是由m个线性无关列组成，这m个线性无关的列向量可以作为Em空间的一个基。基本解：令非基变量取零，则得唯一解，称为基本解。基本可行解：所有变量非负的基本解。可行基：对应于基可行解的基。例.Min Z=2x1+x2 s.t.x1+x2+x3 =5 -x1+x2 +x4 =0 6x1+2x2 +x5=21 xj0,j=1,2,5 1 1 1 0 0A=-1 1 0 1 0
13、 6 2 0 0 1由于 ，因此P3,P4,P5是一个基，对应的x3,x4,x5为基变量。1p3=0 0 0p4=1 0 0P5=0 1令x1=x2=0,则得x3=5,x4=0,x5=21,x0=(0,0,5,0,21)T是1 0 00 1 00 0 1对应于基B=的一个基本解。因xi0,x0为基本可行解。另外，向量P1=，P2=,P3=线性无关，因此P1,P2,P3为一个基，对应的x1,x2,x3为基变量。令x4=x5=0,得 x1=21/8,x2=21/8,x3=-2/8则x=(21/8,21/8,-2/8,0,0)T也是基本解，但其不是可行解。1 1 1-1 1 06 2 0 又向量P2
14、，P3，P5线性无关，其为一基，x2，x3，x5为对应的基变量，令x1=x4=0，则x2=0，x3=5，x5=21，所以X2=（0，0，5，0，21）T也是一基本可行解，但是退化的。2.线性规划问题的几何意义2.1基本概念 凸集：凸集：设k为n维欧氏空间的一点集，任取X,YK,若连接X,Y的线段仍属于K,则称K为凸集。即任取,01 X+(1-)YK称K为凸集。顶点（极点）：顶点（极点）：设K是凸集，XK,若X不能用不同的两点 X(1)K,X2)K的线性组合表示为 X=X(1)+(1-)X(2)(00,并且对i=1,2,m,有ai,m+k0,那么该线性规划问题没有有限最优解。证取xm+k为进基变
15、量，令xm+k增加，并取其余非基变量为零，则得kmkmmmmkmkmkmkmxabxxabxxabx/,/,2/22/,1/11令xm+k=0，显然，这时目标函数值为 z=z0+m+k+（+）故没有有限最优解。4 基变换1.换入变量的确定 一般取j0中的最大者 max(j0)=k对应的xk为换入变量。2.换出变量的确定5 迭代（旋转运算）4.单纯形法的计算步骤 基变量 b x1 x2 xm xm+1 xn x1 b1 1 0 0 a1m+1 a1n x2 b2 0 1 0 a2m+1 a2n xm bm 0 0 1 amm+1 amn c1 c2 cm cm+1 cn基变量 b x1 x2 x
16、m xm+1 xn x1 b1 1 0 0 a1m+1 a1n x2 b2 0 1 0 a2m+1 a2n xm bm 0 0 1 amm+1 amn 0 0 0 m+1 n初始单纯形表初始单纯形表4.1单纯形表4.2计算步骤步骤：1.找出初始基本可行解，建立初始单纯形表；2.检验各非基变量的检验数j，若所有j0，则已得最优解，停止。否则，转3 3.在所有j0中若有一k对应的Pk 0，则此问题无界，停止计算；否则，转4 4.根据max(j0)=k确定进基变量xk，根据规则计算lklikikiabaab)0|min(确定离基变量xl，得主元alk，转5 5.进行基变换，得新的单纯形表，返回2例1
17、 min=2x1+5x2 s.t.x14 x23 x1+2x28 x1,x20 解 标准化：min=2x1+5x2 s.t.x1 +x3 =4 x2 +x4 =3 x1+2x2 +x5=8 xj0,j=1,2,5 XB b x1 x2 x3 x4 x5 x3 4 1 0 1 0 0 -x4 3 0 1 0 1 0 3 x5 8 1 2 0 0 1 4 0 2 5 0 0 0 x3 4 1 0 1 0 0 4 x2 3 0 1 0 1 0 -x5 2 1 0 0 -2 1 2 2 0 0 5 0 x3 2 0 0 1 2 -1 x2 3 0 1 0 1 0 x1 2 1 0 0-2 1 0 0
18、0 1 -2 最优解为(2,3,2,0,0)T，max=19例2min z=3x1+x2+3x3 s.t.2x1+x2+x32 x1+2x2+3x35 2x1+2x2+x36 xi0,i=1,2,3解 标准化后，写出单纯形表 XB b x1 x2 x3 x4 x5 x6 x4 2 2 1 1 1 0 0 1 x5 5 1 2 3 0 1 0 5/2 x6 6 2 2 1 0 0 1 3 0 3 1 3 0 0 0 x2 2 2 1 1 1 0 0 2 x5 1 -3 0 1 -2 1 0 1/2 x6 2 -2 0 -1-2 0 1 -2 1 0 2 -1 0 0 XB b x1 x2 x3
19、x4 x5 x6 x2 1 5 1 0 3 -1 0 1/5 x3 1 -3 0 1 -2 1 0 -x6 3 -5 0 0 -4 1 1 -7 0 0 3 -2 0 x1 1/5 1 1/5 0 3/5 -1/5 0 x3 8/5 0 3/5 0 -1/5 2/5 0 x6 4 0 1 1 -1 0 1 -27/5 0 -7/5 0 -6/5-3/5 0最优解为(1/5,0,8/5,0,0,4)T min=27/55.单纯形法的进一步讨论 5.1人工变量法 若线性规划问题的约束条件 a11x1+a1nxn=b1 am1x1+amnxn=bm不存在单位矩阵。我们可以强行为约束条件加入一单位矩阵
20、 a11x1+a1nxn+xn+1 =b1 a21x1+a2nxn +xn+2 =b2 am1x1+amnxn +xn+m=bm xj0,j=1,2,m+n xn+1,xn+m称为人工变量。因为人工变量必须为零，所以若经过基变量的逐步转换，最优解中不存在人工变量则原问题有解；若最优解中还存在人工变量，则原问题无解。1.大M法 我们引入一个很大的正系数(+M)，把规划问题变为下列形式 (*)max=c1x1+c2x2+cnxn-M（xn+1+xn+2+xn+m）s.t.a11x1+a1nxn+xn+1 =b1 a21x1+a2nxn +xn+2 =b1 am1x1+amnxn +xn+m=b1
21、xj0,j=1,2,m+n M为充分大的正数。定理：应用单纯形法求解(*)(1)如果获得最优解 ,则当 ,i=1,2,m都成立时，为(LP)之最优解；否则(LP)的可行解不存在；0 inxTmnnnxxxxxX),(121),(21nxxx (2)如果(*)目标值无下界，且在迭代过程中最后得到的基本可行解 ，则当 ,i=1,2,m都成立时,(LP)也无下界；否则(LP)的可行解不存在。例.max=3x1+2x1+x3-x4 s.t.3x1+2x2+x3 =15 5x1+x2+2x3 =20 x1+2x2+x3+x4 =10 x1,x2,x3,x40解引入人工变量把原问题变成下列形式 max=3
22、x1+2x1+x3-x4-M(x5+x6)s.t.3x1+2x2+x3 +x5 =15 5x1+x2+2x3 +x6=20 TmnnnxxxxxX),(1210 inx x1+2x2+x3+x4 =10 xi0,i=1,2,6 3 2 1 -1 -M -M XB b x1 x2 x3 x4 x5 x6 x5 15 3 2 1 0 1 0 x6 20 5 1 2 0 0 1 x4 10 1 2 1 1 0 0 8M+2 3M+2 3M+2 0 0 0 x5 3 0 7/5 -1/5 0 1 -3/5 x1 4 1 1/5 2/5 0 0 1/5 x4 6 0 9/5 3/5 1 0 -1/5 0
23、 7/5M -M/5 0 0 -8/5M +16/5 +2/5 -4/5 XB b x1 x2 x3 x4 x5 x6 x2 15/7 0 1 -1/7 0 7/5 -3/7 x1 25/7 1 0 3/7 0 -1/7 2/7 x4 15/7 0 0 6/7 1 -9/7 5/7 0 0 6/7 0 -M-2/7 -M+5/7 x2 5/2 0 1 0 1/6 1/2 -1/4 x1 5/2 1 0 0 -1/2 1/2 -1/14 x3 5/2 0 0 1 7/6 -3/2 6/5 0 0 0 -1 -M+1 -M最优解为(5/2,5/2,5/2,0,0,0)T,max=15,原问题的解为
24、(5/2,5/2,5/2,0)T,max=15.2.两阶段法 第一阶段：首先判断原问题是否存在基本可行解，在有基本可行解的情况下，求出一基本可行解。(*)min=xn+1+xn+m s.t.a11x1+a1nxn+xn+1 =b1 am1x1+amnxn +xn+m=bm xj0,j=1,2,m 结论：若原问题有解，则min=0 若(*)问题min=0,原问题有解，相反，若 min0,则原问题无解。由此问题可得一基本可行解，第二阶段：若第一阶段已判断出原问题有解，这时原问题已得一基本可行解。则可删去xn+1,xn+m,而把原问题的目标函数 代入求max。例.max=3x1+2x1+x3-x4
25、s.t 3x1+2x2+x3 =15 5x1+x2+2x3 =20 x1+2x2+x3+x4 =10 x1,x2,x3,x40解第一阶段 max=-x5-x6 s.t.3x1+2x2+x3 +x5 =15 5x1+x2+2x3 +x6=20 x1+2x2+x3+x4 =10 x1,x2,x3,x40单纯形表为：0 0 0 0 -1 -1 XB b x1 x2 x3 x4 x5 x6 x5 15 3 2 1 0 1 0 x6 20 5 1 2 0 0 1 x4 10 1 2 1 1 0 0 8 3 3 0 0 0 XB b x1 x2 x3 x4 x5 x6 x5 3 0 7/5 -1/5 0
26、1 -3/5 x1 4 1 1/5 2/5 0 0 1/5 x4 6 0 9/5 3/5 1 0 -1/5 0 7/5 -1/5 0 0 -8/5 x2 15/7 0 1 -1/7 0 7/5 -3/7 x1 25/7 1 0 3/7 0 -1/7 2/7 x4 15/7 0 0 6/7 1 -9/7 5/7 0 0 0 0 0 -1 -1第二阶段：3 2 1 -1 XB b x1 x2 x3 x4 x2 15/7 0 1 -1/7 0 x1 25/7 1 0 3/7 0 x4 15/7 0 0 6/7 1 0 0 6/7 0 XB b x1 x2 x3 x4 x2 5/2 0 1 0 1/6 x1 5/2 1 0 0 -1/2 x3 5/2 0 0 1 7/6 0 0 0 -1最优解为x1=x2=x3=5/2,x4=0.5.2退化 若用规则确定换出变量时，有时存在两个以上的最小比值，这样在下一次迭代中就有一个或几个基变量等于零，这就出现退化解。当出现退化解时，会出现循环。1974年勃兰特(Bland)提出了一种简便规则：(1)选取j0中下标最小的非基变量xk为换入变量k=min(j|j0)(2)当按规则计算存在两个和两个以上最小比值时，选取下标最小的基变量换出变量。
