线性规划的基本定理

1、3.线性规划的基本定理 1标准形式及图解法 1.1标准形式11 min s.t. , i=1,2,.m x0, j=1,2,.n (3.1)njjjnijjijjc xa xb称如下形式的线性规划为标准形式矩阵表示3.线性规划的基本性质 min s.t. , i=1,2,.m x0, (3.2)cxAxb其中A是mn矩阵，c是n维行向量， b是m维列向量。评注：为计算需要，一般假设b0.否则，可在方程两端乘以(-1)即可化为非负。3.线性规划的基本性质1122nn1111221nn12112222nn2m11m22mnnm min c xc x.c x s.t. a xa x.a xb a x

2、a x.a xb . axax.axb j x0, j1,2,.n任意非标准形式均可划为标准形式，如引入松弛变量xn+1， xn+2 , xn+m.则有3.线性规划的基本性质1122nn1111221nnn 112112222nnn 22m11m22mnnn mm min c xc x.c x s.t. a xa x.a xxb a xa x.a xxb . axax.axxb j x0, j1,2,.nm若某变量xj无非负限制，则引入xj = xj - xj ， xj , xj 0若有上下界限制，比如xj lj, 令xj = xj - lj, , 有 xj 03.线性规划的基本性质 1.2.

3、 图解法 当自变量个数少于3时，我们可以用较简便的方法求解。3.线性规划的基本性质Min 3x +2.5y s.t. 2x + 4y 40 3x + 2y 50 x, y 0.例如，考虑食谱问题3.线性规划的基本性质30104020501020304050yx03x +2.5y2x+4y 403x+2y 50(15, 2.5)可行区域的极点：可行区域的极点：(0, 25)(15, 2.5) 最优解最优解(20, 0) 2 基本性质 2.1 线性规划的可行域3.线性规划的基本性质定理定理 3.1 线性规划的可行域是凸集线性规划的可行域是凸集. 2.2 最优极点观察上例，最优解在极点(15,2.5

4、)达到，我们现在来证明这一事实:线性规划若存在最优解线性规划若存在最优解,则最优解一定可在某极点上达到则最优解一定可在某极点上达到.考察线性规划的标准形式(3. 2)3.线性规划的基本性质(1)(2)( )(1)(2)( ),.,.,ktxxxddd设可行域的极点为极方向为。根据表示定理，任意可行点x可表示为 (3.3) 1 0, 1,2,., 0, 1,2,., .iiiiixxdikit kt(i)(i)i=1i=1ki=1把x的表达式代入(3. 2),得等价的线性规划:3.线性规划的基本性质min()() (3.4) 1 0, 1,2,., 0, 1,2,., .iiiiicxcdiki

5、t kt(i)(i)i=1i=1ki=1于是,问题简化成3.线性规划的基本性质jj1,j,cd0,cd() (j)(j)若有某 使得则有 从而问题的目标函数值可以无限小()。此时我们称该问题是无界的或不存在有限最优解。j2,0,0j12,t5jcd( j )若对任意的 有则为极小化目标函数，必有 ， ，. . . ,. ( 3. )在(3.6)中令3.线性规划的基本性质 min() (3.6) 1 0, 1,2,.,iiicxik k( i )i =1ki =1p(i)1 i kcxmin cx (3.7) ( )显然,当pj1,0, jp (3.8) 时目标函数取极小值.3.线性规划的基本性

6、质iipiipcx(cx)(cd) (cx)(cx) =cx kt(i)(i)i=1i=1kk(i)( )i=1i=1( )(p)x因此极点是问题(3.2)的最优解.即(3.5)和(3.8)是(3.4)的最优解,此时2,若若(3. 2)存在有限最优解存在有限最优解,则目标数的最优值则目标数的最优值可在某极点达到可在某极点达到.3.线性规划的基本性质定理定理3.2 设线性规划设线性规划(3.2)(3.2)的可行域非空的可行域非空, ,则则1,(3. 2)1,(3. 2)存在最优解的充要条件是所有存在最优解的充要条件是所有(j)cd非负非负,其中其中 是可行域的极方向是可行域的极方向d(j) 3最

7、优基本可行解3.线性规划的基本性质前面讨论知道们最优解可在极点达到，而极点是一几何概念，下面从代数的角度来考虑。 min cx s.t. Axb, i=1,2,.m x0, (3.2)不失一般性,设rank(A)=m,A=B,N,B是m阶可逆的.BNxxx设 BNxBxN的分量与 中列对应;的分量与 中列对应3.线性规划的基本性质于是,Ax=b可写为BNBNx(B,N)bx BxNxb (3.9)即-1-1BNxB bB Nx于是特别的令Nx =0,则-1BNxB bx (3.10)x0称为方程组Ax=b的一个基本解基本解.3.线性规划的基本性质定义定义3.1-1BNxB bxx0B称为基矩阵

8、基矩阵, 的各分量称为基变量基变量. xB基变量的全体12mBBBx ,x,.,x称为一组基一组基.的各分量称为基变量基变量. xN-1BNxB bxx01B b0,又若则称为约束条件Ax=b,x0的一个基本可行解基本可行解. B称为可行基矩阵可行基矩阵3.线性规划的基本性质12mBBBx ,x,.,x称为一组可行基一组可行基.B b0,称基本可行解是非退化非退化的,若-1 若B b0,-1 且至少有一个分量为0,称基本可行解是退化退化的.1212例1, 求出约束为x +x =1 的所有基本可行解x ,x0:A(1,1),AAx, x,. 解注意到 任意一基矩阵是 的可逆子矩阵.于是,容易知道

9、, 仅有两个一元矩阵(1)从而得所有10的基本解为 =它们都是基本可行解013.线性规划的基本性质31/2.,x1231212例2, 求出约束为x +x +x =1 x -x的所有基本可行解x ,x01231111:A,b1101/2111111B,B,B.111010解均可逆3.线性规划的基本性质111111/21/2B1/21/21/21/213/4xBb01/21/21/21/41221101B110111/2xBb0111/21/23.线性规划的基本性质1331101B110111/2xBb111/23/212,x ,x3可见是非退化的基本可行解,而x 不是非负的,从而不是基本可行解.

10、 容易知道,基矩阵的个数是有限的,因此基本解从而基本可行解的个数也是有限的, 不超过3.线性规划的基本性质nn!mm!(nm)!(1,0)(0,1)123x +x +x =1基本可行解极点定理定理3. 3 令K=x| Ax=b,x0,A是mn矩阵,r(A)=m则K的极点集与Ax=b,x0的基本可行解集合等价.3.线性规划的基本性质证明证明: (提纲)1)设x是K的极点,则x是Ax=b,x0的基本可行解.2)设x是Ax=b,x0的基本可行解,则x是K的极点.3.线性规划的基本性质1),先证极点x的正分量所对应的A的列线性无关.T12sj12ss 1s 2nx(x ,x ,.,x ,0,0,.,0

11、) ,x0, j1,2,.s,A(p ,p ,.,p ,p,p,.,p )设其中记 12s12s12sjsjjj 1x ,x ,.,xp ,p ,.,p .p ,p ,.,p, j1,2,.,sp0设所对应的列为假设线性相关 则存在一组不全为零的数使得 jjjj(1)(2)jjx, j1,2,.,sx, j1,2,.,sx, x 0, js1,2,.,n0, js1,2,.,n 记3.线性规划的基本性质j(1)(2)jjx0, j1,2,.,s0,x0,x0, j1,2,.,s由于故可取充分小的使得(1)nn(1)jjjjjj 1j 1ssjjjjj 1j 1 Axx p(x)p x ppb则

12、(2)Axb同理 (1)(2)(1)(2)0,xx(xx).x.从而当充分小 有是可行点,1但我们又有x=此与 为极点相矛盾23.线性规划的基本性质12s12ss 1m,p ,p ,.,p,smr(A),A,B(p ,p ,.,p ,p,.,p ).B于是线性无关从而可将其扩充为 的一组基 记做我们得到可逆阵T12s1122sss 1m1BBBBNx(x ,x ,.,x ,0,0,.,0)K,Axb,x0,x px p.x p0p.0pb Bxb,xB b0 xxxx0又是 的极点 所以满足于是 即且 从而是基本可行解3.线性规划的基本性质2)设x是Ax=b,x0的基本可行解,记(1)(2)(

13、1)(2)x,x(0,1), xx+(1)x 假设存在两点及某使得BBNxxx0 x0(1)(2)(1)(2)BB(1)(2)NNxx x,x.xx记(1)(2)(1)(2)-1BBNNxxB b(1).0 xx 则 即3.线性规划的基本性质(1)(2)(1)(2)-1BBNNB bx(1)x,0 x(1)x. (1)(2)NN(1)(2)NN0,(1)0,x0,x0.x0,x0. 又 则由上两式知(1)(2)(1)(2)(1)11(1)1BN(2)11(2)1BN(1)(2)x,x Axb,AxbxB bB NxB b xB bB NxB bx xx又由于都是可行点,所以于是可得于是 = 总

14、结,线性规划存在最优解,目标函数的最优值 一定能在某极点上达到.可行域K=x| Ax=b,x0的极点就是其基本可行解. 从而,求线性规划的最优解,只需要求出最优基本可行解即可.3.线性规划的基本性质 3. 4 基本可行解的存在问题3.线性规划的基本性质定理定理3. 4 若Ax=b,x0有可行解,则一定存在基本可行解,其中A是秩为m的mn矩阵.12nT12sjA(p ,p ,.,p ) x(x ,x ,.,x ,0,0,.,0), x0, j1,2,.s.证明:记 设 是一可行解其中12sxsp ,p ,.,p,x若 的 个正分量对应的列线性无关 则可以将其扩充为一组基 从而得 即一基本可行解.否则,我们通过如下步骤构造出一基本可行解3.线性规划的基本性质12ssjjjj 1p ,p ,.,p, j1,2,.,s p0假设