02第二章 线性规划的基本性质

1、第二章线性规划的基本性质在生产、经济、技术领域，许多工程技术和管理问题实际上是线性的，或者是可以用线 性函数近似表达的，所以线性规划的研究是很有意义的。而且对线性规划的理论的研究要比 非线性规划领域成熟的多。掌握线性规划的基本理论和求解方法是本课程最重要的目标之 一。2.1线性规划解的几何特征借助于平面图形可以直观地了解线性规划解的几何特征，具体介绍一个实例。设有两个决策变量和的线性规划：min - 2 x1 - x2s.t.-3 x1 -4 x2 K12(2.1)-x1 + 2 x2 N -2 x1,x2, N 0首先在x1Ox2平面上画出(2.1)的可行域：K = (x , x )T 1-

2、3 x - 4 x -12, - x + 2 x -2, x , x 012121212为此，只要画出K的边界：-3 x1 -4 x2 N-12-x1 + 2 x2 N -2x1 = 0, x2 = 0该可行域如图2.1所示，它是一个由四条直线组成的凸多边形。任何一个含两个变量 的线性规划的可行域都是以直线为边的凸多边形。观察目标函数：f(x) = - 2 x1 - x2对于任一给定的实数a，方程-2 x1 - x2 =a表示一条直线，称为f的等值线。变动a 可以得到一族相互平行的直线。把f的等值线向函数值a减小的方向移动，它与凸多边形K 的最后一个交点即为的最优解。最优解是凸多边形的一个顶点

3、。设目标函数f(x) = C1玉+c2 %它是玉和x2的函数，它的斜率是-宾，它在任意一点 c2的梯度：/)T以=海1J =W C 2)、12 7它与目标函数的等值线垂直，由高等数学的有关知识可知，当点(气,X2)T沿着梯度方向 移动时，f的值将随之增大，沿着梯度负方向移动时，f的值将随之减小。对于式(2.1)，不妨在原点做梯度Vf = (C1c2)t = (-2, -1)T，从原点至点(-2, -1)T作 一个向量即为该梯度。过原点作梯度向量的垂直线(用虚线表示)，它为过原点且a=0的等 值线：-2 % - x2=0因为我们的问题是求目标函数的最小值minf，因此让等值线逆梯度方向移动，于是

4、目 标函数值逐步减小，在等值线刚好要离开可行域的时候，这时等值线在可行域的的一个顶点，一. (16 3、T,顶点X*= 16,- 就是线性规划的最优解，f (X*) = -7是线性规划的最优值。15 5 J结论：若两个变量的线性规划有最优解，则必能在可行域凸多边形的顶点中得到。推广之，对于有n个变量的线性规划，其可行域是一个以超平面为边界的凸多边体。如果线性规划有最优解，则该最优解一定能在凸多边体的顶点中得到。图2.1以上的结论对于求解线性规划有重大的价值，因为原本我们要在可行域的无穷多个点中去寻找最优解，现在根据结论我们只要在可行域的有限个顶点中寻找最优解即可。2.2线性规划解的标准形为了研

5、究方便，定义下列形式为线性规划的标准形：min z = Y c x j j j=1s.t. a x = b , i = 1,2,., m（2.2）j=1Xj 0,j = 1,2,., n对于目标函数，一律定义为求最小值，决策变量一律定义为非负变量，约束条件除变 量的非负条件之外，一律为等式约束。各种形式的线性规划模型都可以化为标准形。1、若问题的目标函数是求最大值max z = lcx，那么可以令：f = -z，把原问题=1化为在相同的约束条件下求最小值：min f，显然，新问题和原问题是同解的。2、如果约束条件中有不等式约束：Ha x 0 ij j i i i j=1称变量x：为松弛变量3、

6、如果约束条件中有不等式约束：ILa x b，则可以引进一个新变量x，并用下ij j iij=1 面两个约束条件来代替原有的不等式约束：乙 a x - x = b , x 0 ij j i i i称变量x为剩余变量4、如果约束条件中出现x. h （h丰0），则可以引进一个新变量y. = x .- h替代原 问题中的变量x,，于是，问题中原有的约束就化为七0。5、如果变量x的符号不受约束，则可以引进两个新变量y和y”，并以x = y- y”代j j j j j j入原问题的目标函数和约束条件消去x，同时在约束条件中增加y 0, y” 0。j j j例2.1把线性规划max z = x + xs.t

7、.2x + 3x 42 x 一 x = 3x 0化为标准形。解该题有四个地方与标准形不符，a.目标函数是求最大值；b.决策变量x的符号没有2约束；C.第一、第二约束条件为不等式。1、令：f = -z = -(x1 + x2)，求max z 改为求 min f2、令：x = x - x , where x 0, x 0 TOC o 1-5 h z 234343、对不等式约束条件分别引入为松弛变量x5和剩余变量x6，从而将原问题化为标准形:min f = -x - x + xs .t.2 x + 3 x 一 3 x + x = 61345x + 7 x 一 7 x 一 x = 413462x -x

8、 +x =3x . 0, j = 1,3, 4, 5, 62.3线性规划解的基本定理观察(2.1)式，其相应的标准形为:min 一 2x - xs .t. 3 x 4 x x = 12x + 2 x x = 2x. 0, j = 1,2, 3,4它的可行域有四个顶点，在标准形的形式下所对应的解为:(0, 0,12, 2) t ,(0, 3, 0, 8) t ,(堂,3,0,0) t ,(2, 0, 6, 0) t5 5四个顶点的共同之处是所对应的变量值中均有两个的坐标为0。仔细分析后可知，作为 平面上凸多边形的顶点必然是两条边界直线的交点。若边界直线为坐标轴，则相应的一个坐 标为0，若边界直线

9、非坐标轴，则化标准形时所引进的松弛变量或剩余变量就应为0，因此 在仅有两个决策变量的线性规划标准形的形式下，顶点所对应的变量的值为0的个数不少于 两个是一般规律。这里的变量可以是决策变量、松弛变量或剩余变量。我们利用代数的这个特征引入基本可行解这个概念来替代几何意义上顶点这个名词，并用以表述线性规划的基本定理。线性规划的标准形(2.2)用矩阵表示为：min z = CTxs .t. Ax = Bx 0(2.3)其中，C = (c , c ,., c )T, x = (x , x ,., x )T, 12n12nA = (a ), B = (b , b ,., b )tij m x n1 2m不妨设矩阵A的秩r(A) = m，即线性方程组Ax = B没有多余的方程。于是线性规划(2.2)的可行解就等价于求线性方程组Ax = B的非负解。线性方程组Ax = B有n个变量，且r(A) = m，因此当Ax = B的一个解中非零分量都是线性无关时，则非零分量的个数不会超过r(A) = m，即零分量的个数不少于n-m。线性方程组Ax = B中对应非零分量呈线性无关的解就是式(2.3)的基本解；其中非负 基本解称为基本可行