优化方法线性规划.ppt

线性规划 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 A2 B1B2B3 工地 运价（元/万块 ） 砖厂 50 60 70 60 110 160 1947年 美国数学家 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+c2x2 s.t. a11x1+a12x2b1 a21x1+a22x2b2 x1,x20 在平面上取一直角坐标系，它的两个坐标分别是x1,x2,把 满足第一个方程的x1,x2看作平面的一个点，那么这个点应 在什么地方呢？平面被直线a11x1+a12x2=b1 划分为两个半 平面，这个点一定在两个半平面的某一个上面。所有满足 约束条件的点就构成一个区域K。 现在，我们就是要在K 中找一点（x10,x20），使目标函数达到最大。 a21x1+a22x2=b2 a11x1+a12x2=b1 c1x1+c2x2=h A 显然，把h作为参数的方程c1x1+c2x2=h 表示一平行直线束 ，在K中任意取一点(x10,x20)，h=c1x1+c2x2=c1x10+c2x20 就表 示这个直线束中通过（x10,x20）的一条直线。所以，我们 要在K中找一点（x10,x20）使c1x10+c2x20为最大，就变成在 直线束中找一条直线，这条直线既通过K中某一点，又使 原点到这条直线的距离沿正法线方向达到最大。 x2 x1 O 那么，怎样找这条直线呢？让直线c1x1+c2x2=h 沿着它的正 法线（梯度）方向移动，移动到刚刚开始要离开K的时候 ，这时的直线仍与K相交，也就是还通过K的点. 总结：求最大，沿正法线方向移动。 求最小，沿负法线方向移动。 例1. max S=-x1+x2 s.t. 2x1+x22 x1-2x22 x1+x25 x1,x20 法线方向： ,A(1,4)是S达到最大值的点。 x1+x2=5 -2x1+x2=2 x1-2x2=2 A 例2min S=-2x1+x2 s.t. x1+x21 x1-3x2-3 x1,x20 负法线方向 ： O x1 x2 最小值为负无穷 x1-3x2=-3 x1+x2 =1 例3Max S=3x1+x2 s.t. x1+x25 -x1+x20 6x1+2x221 x1,x20 法线方向 ，此问题有无穷多个解. O x1 x2 例4Max S=3x1+x2 s.t. x1-x2-1 x1+x2-1 x1,x20 此问题无可行解。 O x1 x2 -1 1 -1 6x1+2x2=21 x1+x2=5 -x1+x2=0 x2 x1 O 可在某一顶点 上取得。 总结：两个变量的线性规划问题的解有4种情况 。 1有唯一的最优解 2有最优解，但不唯一 （有无穷多个） 3有可行解，但无最优解 4无可行解 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 加一变量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 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 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 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，根据规 则计算 确定离基变量xl，得主元alk，转5 5.进行基变换，得新的单纯形表，返回2 例1 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 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 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/5 5.单纯形法的进一步讨论 5.1人工变量法 若线性规划问题的约束条件 a11x1+a1nxn=b1 am1x1+amnxn=bm 不存在单位矩阵。我们可以强行为约束条件加入一单位矩 阵 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 xj0,j=1,2, ,m+n M为充分大的正数。 定理：应用单纯形法求解(*) (1)如果获得最优解 ,则当 ,i=1,2,m都成立时， 为(LP)之最优 解；否则(LP)的可行解不存在； (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 =3x1+2x1+x3-x4-M(x5+x6) s.t. 3x1+2x2+x3 +x5 =15 5x1+x2+2x3 +x6=20 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 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,原问题的解 为(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 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,