线性规划o数学教研室 o石鸿雁引言o线性规划是数学规划的一个重要分支，历史比较悠久，理论比 较成熟，方法较为完善。线性规划的思想最早可以追溯到1939 年，当时的苏联数学家、经济学家（康特罗维奇）在生产组 织与计划中的数学方法一书中提出了类似线性规划的模型， 以解决下料问题和运输问题，并给出了“解决乘数法”的求解方 法。然而，他们的长期工作未被人们知道。 o由于战争的需要，美国的经济学家T.C.Koopmans（库普曼斯 ）重新独立的研究运输问题，并很快看到了线性规划在经济学 中应用的意义。在这之后，线性规划也被广泛地应用于军事、 经济等方面。由于他们在这方面的突出贡献，康特罗维奇和库 普曼斯联合得到1975年诺贝尔经济学奖。 引言o对线性规划贡献最大的是美国数学家G.B.Dantig(丹捷格)，他 在1947年提出了求解线性规划的单纯形法（Simple Method ），并同时给出了许多很有价值的理论，为线性规划奠定了理 论基础。在1953年，丹捷格又提出了改进单纯形法，1954年 Lemke(兰母凯)提出了对偶单纯形法（dual simplex method）。 o在1976年， R. G. Bland 提出避免出现循环的方法后，使线 性规划的理论更加完善。但在1972年，V. Klee和G .Minmty 构造了一个例子，发现单纯形法的迭代次数是指数次运算，不 是好方法并不是多项式算法（多项式算法被认为是好算法 ），这对单纯形法提出了挑战。引言o1979年，前苏联青年数学家（哈奇扬）提出了一种新算法 椭圆算法，是一个多项式算法，这一结果在全世界引起了极大 轰动，被认为是线性规划理论上的历史突破。然而在实际计算 中，椭球算法的计算量与单纯形算法差不多，因此，椭球算法 并不实用。 o1984年，在美国的贝尔实验室工作的印度数学家 N.Karmarkar (卡玛卡尔)又提出了一个多项式算法 Karmarkar 算法，Karmarkar算法本质上属于内点法，这种 算法不仅在理论上优于单纯形算法，而且也显示出对求解大规 模线性规划问题的巨大潜力。 o此外，1980年前后，形成求解线性规划的有效集法（active set method），在理论上有效集法与单纯形法是等价的，但 解决问题的侧重点不同，因此各有优缺点，起着相互补充的作 用。引言o 由于很多非常重要的实际问题都是线性的， 即使不是至少能够用线性函数很好地近似， 所以线性规划的研究是很有价值的。 o 另一方面，线性规划方面的工作与非线性规 划领域相比更为成熟。目前，线性规划方法 的发展已被用来求解非线性模型，所以掌握 线性规划的理论和解法是本课程的重要目标 之一。线性规划（LP）A1 A2B1B2B3工地 运价（元/万块 ）砖厂50 60 70 60 110 1601947年 美国数学家 Dantzig 单纯形法 理论基础 1979年 苏联数学家 哈奇安 椭球法 理论上的突破 1984年 美国数学家 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=50x11+60x12+70x13+60x21+110x22+160x23 S.t. x11+x12+x13=23 x21+x22+x23=27 x11+x21=17 x12+x22=18 x13+x23=15 xij0, i=1,2、j=1,2,3例2.某木器厂生产圆桌和衣柜两种产品，现有两种木料，第一种 有72m3,第二种有56m3，生产圆桌和衣柜所需木料如下表。每生产一 个桌子可获利润6元，生产衣柜可获利润10元。木料厂在现有木料的 条件下，圆桌和衣柜各生产多少，才能使利润最大？解设生产圆桌x1个，衣柜x2个 max S=6x1+10x2 s.t. 0.18x1+0.09x272 0.08x1+0.28x256 x1,x20线性规划问题：约束条件及目标函数均为未知量的线 性函数，求目标函数的最大或最小值问题。.2图解法（只限于两个变量）max S=c1x1+c2x2s.t. a11x1+a12x2b1a21x1+a22x2b2x1,x20在平面上取一直角坐标系，它的两个坐标分别是x1,x2,把 满足第一个方程的x1,x2看作平面的一个点，那么这个点应 在什么地方呢？平面被直线a11x1+a12x2=b1 划分为两个半 平面，这个点一定在两个半平面的某一个上面。所有满足 约束条件的点就构成一个区域K。 现在，我们就是要在K 中找一点（x10,x20），使目标函数达到最大。a21x1+a22x2=b2a11x1+a12x2=b1c1x1+c2x2=hA显然，把h作为参数的方程c1x1+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的点.总结：求最大，沿正法线方向移动。求最小，沿负法线方向移动。例1. max S=-x1+x2s.t. 2x1+x22x1-2x22x1+x25x1,x20法线方向： ,A(1,4)是S达到最大值的点。x1+x2=5-2x1+x2=2x1-2x2=2A例2min S=-2x1+x2s.t. x1+x21x1-3x2-3x1,x20负法线方向 ：Ox1x2最小值为负无穷x1-3x2=-3x1+x2 =1例3Max S=3x1+x2s.t. x1+x25-x1+x206x1+2x221x1,x20法线方向 ，此问题有无穷多个解.Ox1x2例4Max S=3x1+x2s.t. x1-x2-1x1+x2-1x1,x20此问题无可行解。Ox1x2-11-16x1+2x2=21x1+x2=5-x1+x2=0x2x1O可在某一顶点 上取得。总结：两个变量的线性规划问题的解有4种情况 。1有唯一的最优解2有最优解，但不唯一（有无穷多个）3有可行解，但无最优解4无可行解3标准形式 min =c1x1+c2x2+cnxns.t. a11x1+a12x2+a1nxn=b1 a21x1+a22x2+a2nxn=b2 am1x1+am2x2+amnxn=bmxj0;j=1,2, ,nbi0;i=1,2, ,m化一般问题为标准形式： (一)若ak1x1+ak2x2+aknxnbk 加一变量xn+k0（松驰变量），改写为ak1x1+ak2x2+aknxn+xn+k=bk若ak1x1+ak2x2+aknxnbk减一变量xn+k0(剩余变量），改写为ak1x1+ak2x2+aknxn-xn+k=bk(二) 若目标函数为max=c1x1+c2x2+cnxn min =-=-(c1x1+c2x2+cnxn)（三）若xj0,并且对i=1,2,m,有ai,m+k0, 那么该线性规划问题没有有限最优解。证取xm+k为进基变量，令xm+k增加，并取其余非基变 量为零，则得令xm+k=0，显然，这时目标函数值为z=z0+m+k+ （+ ） 故没有有限最优解。4 基变换1.换入变量的确定一般取j0中的最大者max(j0)=k 对应的xk为换入变量。2.换出变量的确定5 迭代（旋转运算）4.单纯形法的计算步骤 基变量 b x1 x2 xm xm+1 xnx1 b1 1 0 0 a1m+1 a1nx2 b2 0 1 0 a2m+1 a2n xm bm 0 0 1 amm+1 amnc1 c2 cm cm+1 cn基变量 b x1 x2 xm xm+1 xnx1 b1 1 0 0 a1m+1 a1nx2 b2 0 1 0 a2m+1 a2n xm bm 0 0 1 amm+1 amn0 0 0 m+1 n初始单纯形表4.1单纯形表4.2计算步骤 步骤：1.找出初始基本可行解，建立初始单纯形表；2.检验各非基变量的检验数j，若所有j0，则已得 最优解，停止。否则，转33.在所有j0中若有一k对应的Pk 0，则此问题无界 ，停止计算；否则，转44.根据max(j0)= k确定进基变量xk，根据规 则计算确定离基变量xl，得主元alk，转55.进行基变换，得新的单纯形表，返回2例1 min=2x1+5x2s.t. x14x23x1+2x28x1,x20解 标准化：min=2x1+5x2s.t. x1 +x3 =4x2 +x4 =3x1+2x2 +x5=8xj0,j=1,2, ,5XB b x1 x2 x3 x4 x5 x3 4 1 0 1 0 0 -x4 3 0 1 0 1 0 3x5 8 1 2 0 0 1 40 2 5 0 0 0 x3 4 1 0 1 0 0 4x2 3 0 1 0 1 0 -x5 2 1 0 0 -2 1 22 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 0 1 -2 最优解为(2,3,2,0,0)T ，max =19例2min z=3x1+x2+3x3s.t. 2x1+x2+x32x1+2x2+3x352x1+2x2+x36xi0,i=1,2,3 解 标准化后，写出单纯形表XB b x1 x2 x3 x4 x5 x6 x4 2 2 1 1 1 0 0 1x5 5 1 2 3 0 1 0 5/2x6 6 2 2 1 0 0 1 30 3 1 3 0 0 0x2 2 2 1 1 1 0 0 2x5 1 -3 0 1 -2 1 0