线性规划的基本定理课件

1、3.线性规划的基本定理,1标准形式及图解法 1.1标准形式,1,学习交流PPT,矩阵表示,3.线性规划的基本性质,其中A是mn矩阵，c是n维行向量， b是m维列向量。,评注：为计算需要，一般假设b0.否则，可在方程两端乘以(-1)即可化为非负。,2,学习交流PPT,3.线性规划的基本性质,任意非标准形式均可划为标准形式，如,引入松弛变量xn+1， xn+2 , xn+m.,3,学习交流PPT,则有,3.线性规划的基本性质,4,学习交流PPT,若某变量xj无非负限制，则引入xj = xj - xj ， xj , xj 0 若有上下界限制，比如xj lj, 令xj = xj - lj, , 有 x

2、j 0,3.线性规划的基本性质,5,学习交流PPT,1.2. 图解法 当自变量个数少于3时，我们可以用较简便的 方法求解。,3.线性规划的基本性质,Min 3x +2.5y s.t. 2x + 4y 40 3x + 2y 50 x, y 0.,例如，考虑食谱问题,6,学习交流PPT,3.线性规划的基本性质,可行区域的极点： (0, 25) (15, 2.5) 最优解 (20, 0),7,学习交流PPT,2 基本性质 2.1 线性规划的可行域,3.线性规划的基本性质,定理 3.1 线性规划的可行域是凸集.,2.2 最优极点,观察上例，最优解在极点(15,2.5)达到，我们 现在来证明这一事实:线

3、性规划若存在最优解, 则最优解一定可在某极点上达到.,8,学习交流PPT,考察线性规划的标准形式(3. 2),3.线性规划的基本性质,根据表示定理，任意可行点x可表示为,9,学习交流PPT,把x的表达式代入(3. 2),得等价的线性规划:,3.线性规划的基本性质,10,学习交流PPT,于是,问题简化成,3.线性规划的基本性质,11,学习交流PPT,在(3.6)中令,3.线性规划的基本性质,显然,当,时目标函数取极小值.,12,学习交流PPT,3.线性规划的基本性质,即(3.5)和(3.8)是(3.4)的最优解,此时,13,学习交流PPT,2,若(3. 2)存在有限最优解,则目标数的最优值 可在

4、某极点达到.,3.线性规划的基本性质,定理3.2 设线性规划(3.2)的可行域非空,则,14,学习交流PPT,3最优基本可行解,3.线性规划的基本性质,前面讨论知道们最优解可在极点达到，而极点 是一几何概念，下面从代数的角度来考虑。,不失一般性,设rank(A)=m,A=B,N,B是m阶可逆的.,15,学习交流PPT,3.线性规划的基本性质,于是,Ax=b可写为,于是,16,学习交流PPT,称为方程组Ax=b的一个基本解.,3.线性规划的基本性质,定义3.1,为约束条件Ax=b,x0的一个基本可行解. B称为 可行基矩阵,17,学习交流PPT,3.线性规划的基本性质,称为一组可行基.,且至少有

5、一个分量为0,称基本可行解是退化的.,18,学习交流PPT,3.线性规划的基本性质,19,学习交流PPT,3.线性规划的基本性质,20,学习交流PPT,3.线性规划的基本性质,21,学习交流PPT,容易知道,基矩阵的个数是有限的,因此基本解从而基本可行解的个数也是有限的, 不超过,3.线性规划的基本性质,22,学习交流PPT,定理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的极点

6、.,23,学习交流PPT,3.线性规划的基本性质,1),先证极点x的正分量所对应的A的列线性无关.,24,学习交流PPT,3.线性规划的基本性质,25,学习交流PPT,3.线性规划的基本性质,26,学习交流PPT,3.线性规划的基本性质,2)设x是Ax=b,x0的基本可行解,记,27,学习交流PPT,即,3.线性规划的基本性质,28,学习交流PPT,总结,线性规划存在最优解,目标函数的最优值 一定能在某极点上达到.可行域K=x| Ax=b,x0的极点就是其基本可行解. 从而,求线性规划的最优解,只需要求出最优基本 可行解即可.,3.线性规划的基本性质,29,学习交流PPT,3. 4 基本可行解的存在问题,3.线性规划的基本性质,定理3. 4 若Ax=b,x0有可行解,则一定存在基本