线性规划的基本定理课件

3.线性规划的基本定理1标准形式及图解法1.1标准形式1可编辑课件PPT矩阵表示3.线性规划的基本性质其中A是m

n矩阵，c是n维行向量，b是m维列向量。评注：为计算需要，一般假设b

0.否则，可在方程两端乘以(-1)即可化为非负。2可编辑课件PPT3.线性规划的基本性质任意非标准形式均可划为标准形式，如引入松弛变量xn+1，xn+2,…xn+m.3可编辑课件PPT则有3.线性规划的基本性质4可编辑课件PPT若某变量xj无非负限制，则引入xj=

xj'

-

xj''，xj',

xj''0若有上下界限制，比如xj

lj,令xj'=xj-lj,,

有xj'

03.线性规划的基本性质5可编辑课件PPT1.2.图解法当自变量个数少于3时，我们可以用较简便的方法求解。3.线性规划的基本性质Min3x+2.5ys.t.2x+4y

403x+2y

50

x,y

0.例如，考虑食谱问题6可编辑课件PPT3.线性规划的基本性质30104020501020304050yx03x+2.5y2x+4y

403x+2y

50(15,2.5)可行区域的极点：(0,25)(15,2.5)最优解(20,0)7可编辑课件PPT2基本性质2.1线性规划的可行域3.线性规划的基本性质定理

3.1

线性规划的可行域是凸集.

2.2最优极点观察上例，最优解在极点(15,2.5)达到，我们现在来证明这一事实:线性规划若存在最优解,则最优解一定可在某极点上达到.8可编辑课件PPT考察线性规划的标准形式(3.2)3.线性规划的基本性质根据表示定理，任意可行点x可表示为9可编辑课件PPT把x的表达式代入(3.2),得等价的线性规划:3.线性规划的基本性质10可编辑课件PPT于是,问题简化成3.线性规划的基本性质11可编辑课件PPT在(3.6)中令3.线性规划的基本性质显然,当时目标函数取极小值.12可编辑课件PPT3.线性规划的基本性质(p)x因此极点是问题(3.2)的最优解.即(3.5)和(3.8)是(3.4)的最优解,此时13可编辑课件PPT2,若(3.2)存在有限最优解,则目标数的最优值可在某极点达到.3.线性规划的基本性质定理3.2设线性规划(3.2)的可行域非空,则1,(3.2)存在最优解的充要条件是所有(j)cd非负,其中是可行域的极方向d(j)14可编辑课件PPT3最优基本可行解3.线性规划的基本性质前面讨论知道们最优解可在极点达到，而极点是一几何概念，下面从代数的角度来考虑。不失一般性,设rank(A)=m,A=[B,N],B是m阶可逆的.15可编辑课件PPT3.线性规划的基本性质于是,Ax=b可写为于是特别的令Nx=0,则16可编辑课件PPT称为方程组Ax=b的一个基本解.3.线性规划的基本性质定义3.1B称为基矩阵,的各分量称为基变量.xB基变量的全体称为一组基.的各分量称为基变量.xN为约束条件Ax=b,x0的一个基本可行解.B称为可行基矩阵17可编辑课件PPT3.线性规划的基本性质称为一组可行基.Bb>0,称基本可行解是非退化的,若-1若Bb

0,-1且至少有一个分量为0,称基本可行解是退化的.18可编辑课件PPT3.线性规划的基本性质19可编辑课件PPT3.线性规划的基本性质20可编辑课件PPT3.线性规划的基本性质21可编辑课件PPT容易知道,基矩阵的个数是有限的,因此基本解从而基本可行解的个数也是有限的,不超过3.线性规划的基本性质22可编辑课件PPT定理3.3令K={x|Ax=b,x

0},A是m×n矩阵,r(A)=m则K的极点集与Ax=b,x

0的基本可行解集合等价.3.线性规划的基本性质证明:(提纲)1)设x是K的极点,则x是Ax=b,x

0的基本可行解.2)设x是Ax=b,x

0的基本可行解,则x是K的极点.23可编辑课件PPT3.线性规划的基本性质1),先证极点x的正分量所对应的A的列线性无关.24可编辑课件PPT3.线性规划的基本性质25可编辑课件PPT3.线性规划的基本性质26可编辑课件PPT3.线性规划的基本性质2)设x是Ax=b,x

0的基本可行解,记27可编辑课件PPT即3.线性规划的基本性质28可编辑课件PPT总结,线性规划存在最优解,目标函数的最优值一定能在某极点上达到.可行域K={x|Ax=b,x

0}的极点就是其基本可行解.从而,求线性规划的最优解,只需要求出最优基本可行解即可.3.线性规划的基本性质29可编辑课件PPT3.4基本可行解的存在问题3.线性规划的基本性质定理3.4若Ax=b,x

0有可行解,则一定存在基本可行解,其中A是秩为m的m

n矩阵.30可编辑课