线性规划的基本定理-最优化方法.ppt

线性规划的基本定理
本节主要内容
>上节内容回顾
凸集
>极点与极方向
>线性规划解的基本定理
知识点回顾
、标准形式的线性规划
maxZ=CX
=b
s t
Ⅹ≥0
设集合D={X|AX=b,X≥0
则,D是该线性规划的可行域,可行域中的点
可行解。
约定A是行满秩的m行n列矩阵。
2、基、基向量、基变量、基本解、基本可行解、
可行基、最优解、最优基
基:矩阵A中一个m阶非奇异子矩阵
基向量:基的列向量
基变量:基向量对应的变量
基本解:非基变量全为零的解
基本可行解:非基变量为零,基变量都大于等于
零的解
可行基:基可行解对应的基
最优解:基本解中使目标函数最大的解
最优基:最优解对应的基
本
非
可行解(行
基本解可
解
解
、凸集
引例
我们先考察二维平面上直
线段上任意一点的表示形
式。(如右图)
取Xy为平面上两点,用以原点为起点的
向量来表示X和y,并设Z是线段y上任
意一,得向量zy它与向量Ⅹ-y平行且方
向相同,可以得到下面关系式
A≤1
可以得到
(x-y)有
z=x+(1-)y
这说明当0≤A≤1时,Ax+(1
入)y表示以x,y为端点的直线段上的所
有点,
段
般地,,则
有如下定义
如果x=(x1
y(y1…yn)是R中任意两点,定
义z=Ax+(1-N)y(0≤A≤1),z=(z1…zn)T的点
所构成的集合为以x,y为端点的线段,对应A=0,
A=1的点x,y叫做这线段的端点,而对应
0<<1的点叫做这线段的内点。
◇设R是Rn中的一个点集,(即R≤Rn),对于任意
两点x∈R,y∈R以及满足0≤λ≤1的实数λ,恒有
R=入x+(1-λ)y
今则称R为凸集。
规定:单点集{x}为凸集,空集∞为凸集。
根据以上定义可以看到,凸集的几何意义是
连接凸集中任意两点的直线段仍在此集合内
例如实心的圆,实心的矩形,实心的球体
实心的长方体等等均是凸集,圆周不是凸集。
直观地看,凸集是没有凹入的部分,其内部没有
孔洞。