线性规划的基本定理.pptVIP

3.线性规划的基本定理1标准形式及图解法1标准形式矩阵表示评注：为计算需要，一般假设b?0.否则，可在方程两端乘以(-1)即可化为非负。其中A是m?n矩阵，c是n维行向量，b是m维列向量。3.线性规划的基本性质3.线性规划的基本性质任意非标准形式均可划为标准形式，如引入松弛变量xn+1，xn+2,…xn+m.3.线性规划的基本性质则有若某变量xj无非负限制，则引入xj=xj-xj，若有上下界限制，比如xj?lj,令xj=xj-lj,,xj,xj?0有xj?03.线性规划的基本性质010203x,y?0.3x+2y?50s.t.2x+4y?40Min3x+2.5y当自变量个数少于3时，我们可以用较简便的方法求解。例如，考虑食谱问题1.2.图解法3.线性规划的基本性质3.线性规划的基本性质30104020501020304050yx03x+2.5y2x+4y?403x+2y?50(15,2.5)可行区域的极点：(0,25)(15,2.5)最优解(20,0)线性规划的可行域定理3.1线性规划的可行域是凸集.01最优极点观察上例，最优解在极点(15,2.5)达到，我们现在来证明这一事实:线性规划若存在最优解,则最优解一定可在某极点上达到.02基本性质3.线性规划的基本性质3.线性规划的基本性质根据表示定理，任意可行点x可表示为考察线性规划的标准形式(3.2)3.线性规划的基本性质把x的表达式代入(3.2),得等价的线性规划:3.线性规划的基本性质于是,问题简化成在(3.6)中令01显然,当02时目标函数取极小值.033.线性规划的基本性质3.线性规划的基本性质(p)x因此极点是问题(3.2)的最优解.即(3.5)和(3.8)是(3.4)的最优解,此时3.线性规划的基本性质2,若(3.2)存在有限最优解,则目标数的最优值可在某极点达到.定理3.2设线性规划(3.2)的可行域非空,则1,(3.2)存在最优解的充要条件是所有(j)cd非负,其中是可行域的极方向d(j)前面讨论知道们最优解可在极点达到，而极点是一几何概念，下面从代数的角度来考虑。不失一般性,设rank(A)=m,A=[B,N],B是m阶可逆的.0102033最优基本可行解3.线性规划的基本性质3.线性规划的基本性质于是,Ax=b可写为于是特别的令Nx=0,则3.线性规划的基本性质称为方程组Ax=b的一个基本解.定义3.1B称为基矩阵,的各分量称为基变量.xB基变量的全体称为一组基.的各分量称为基变量.xN为约束条件Ax=b,x?0的一个基本可行解.B称为可行基矩阵3.线性规划的基本性质称为一组可行基.Bb0,称基本可行解是非退化的,若-1若Bb?0,-1且至少有一个分量为0,称基本可行解是退化的.3.线性规划的基本性质3.线性规划的基本性质3.线性规划的基本性质3.线性规划的基本性质容易知道,基矩阵的个数是有限的,因此基本解从而基本可行解的个数也是有限的,不超过3.线性规划的基本性质证明:(提纲)设x是K的极点,则x是Ax=b,x?0的基本可行解.设x是Ax=b,x?0的基本可行解,则x是K的极点.定理3.3令K={x|Ax=b,x?0},A是m×n矩阵,r(A)=m则K的极点集与Ax=b,x?0的基本可行解集合等价.3.线性规划的基本性质,先证极点x的正分量所对应的A的列线性无关.