线性规划的基本定理

3.线性规划的基本定理1标准形式及图解法1.1标准形式矩阵表示3.线性规划的基本性质其中A是mn矩阵，c是n维行向量，b是m维列向量。评注：为计算需要，一般假设b0.否则，可在方程两端乘以(-1)即可化为非负。3.线性规划的基本性质任意非标准形式均可划为标准形式，如引入松弛变量xn+1，

xn+2,…xn+m.则有3.线性规划的基本性质若某变量xj无非负限制，则引入xj

=

xj

'

-

xj

''，

xj

',

xj

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

lj,令xj

'=xj

-lj,,

有xj

'

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

50

x,y

0.例如，考虑食谱问题3.线性规划的基本性质30104020501020304050yx03x+2.5y2x+4y403x+2y50(15,2.5)可行区域的极点：(0,25)(15,2.5)最优解(20,0)2基本性质2.1线性规划的可行域3.线性规划的基本性质定理

3.1

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

2.2最优极点观察上例，最优解在极点(15,2.5)达到，我们现在来证明这一事实:线性规划若存在最优解,则最优解一定可在某极点上达到.考察线性规划的标准形式(3.2)3.线性规划的基本性质根据表示定理，任意可行点x可表示为把x的表达式代入(3.2),得等价的线性规划:3.线性规划的基本性质于是,问题简化成3.线性规划的基本性质在(3.6)中令3.线性规划的基本性质显然,当时目标函数取极小值.3.线性规划的基本性质(p)x因此极点是问题(3.2)的最优解.即(3.5)和(3.8)是(3.4)的最优解,此时2,若(3.2)存在有限最优解,则目标数的最优值可在某极点达到.3.线性规划的基本性质定理3.2设线性规划(3.2)的可行域非空,则1,(3.2)存在最优解的充要条件是所有(j)cd非负,其中是可行域的极方向d(j)3最优基本可行解3.线性规划的基本性质前面讨论知道们最优解可在极点达到，而极点是一几何概念，下面从代数的角度来考虑。不失一般性,设rank(A)=m,A=[B,N],B是m阶可逆的.3.线性规划的基本性质于是,Ax=b可写为于是特别的令Nx=0,则称为方程组Ax=b的一个基本解.3.线性规划的基本性质定义3.1B称为基矩阵,的各分量称为基变量.xB基变量的全体称为一组基.的各分量称为基变量.xN为约束条件Ax=b,x0的一个基本可行解.B称为可行基矩阵3.线性规划的基本性质称为一组可行基.Bb>0,称基本可行解是非退化的,若-1若Bb0,-1且至少有一个分量为0,称基本可行解是退化的.3.线性规划的基本性质3.线性规划的基本性质3.线性规划的基本性质容易知道,基矩阵的个数是有限的,因此基本解从而基本可行解的个数也是有限的,不超过3.线性规划的基本性质定理3.3令K={x|Ax=b,x0},A是m×n矩阵,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的列线性无关.3.线性规划的基本性质3.线性规划的基本性质3.线性规划的基本性质2)设x是Ax=b,x0的基本可行解,记即3.线性规划的基本性质总结,线性规划存在最优解,目标函数的最优值一定能在某极点上达到.可行域K={x|Ax=b,x0}的极点就是其基本可行解.

从而,求线性规划的最优解,只需要求出最优基本可行解即可.3.线性规划的基本性质3.4基本可行解的存在问题3.线性规划的基本性质定