运筹学笔记3线性规划问题的几何特征

也即是从几何上给线性规划问题的概念给一个具体的说明。

运筹学笔记3线性规划问题的几何特征

 

 

连接x1,x2的线段,如果包括x1,x2端点则称为闭线段,不包括则称为开线段。  数学上表述为,任取线段内部的某一点x,如果能写出/描述出这点x的轨迹或其坐标变化的规律,

就可以。为了做到这一点,我们设想有x1,x2,分别有以x1,x2为终点的向量也有在二者之间任取的一点x为终点的向量,让后把以x为终点的向量,用以x1,x2为终点的向量表示。

如下图,大体做法为,过点x做向量ox2的平行线,在下图的三角形中,两条蓝色和一条红色向量,其中x轴的蓝色向量是ox1向量的一部分,然后用x1,x2表示ox向量,当x1,x2前面的系数lamda在0和1之间变动时,x也就在线段x1x2上来回变动,那么所有x的轨迹也就是闭线段;如果lamda不取0和1那么,就称为开线段。

运筹学笔记3线性规划问题的几何特征

 

 

前面讲过一个例子,如下图示,在交点处(2,2)和(3,3/2)处都是最优解,且连接两个点线段之间的任意取值都是最优解;所以闭线段就是以某两个点为端点连接而成的闭合的线段而已。 

运筹学笔记3线性规划问题的几何特征

 

 

 凸集,如下图中第一个图形,它是一个凸多边形,往外补/顶的多边形,所围成的一个区域/集合,我们称之为凸集。

数学上可这样描述:

在某集合的内部任选两个点,连接这两个点的闭线段仍然示含于这个集合的,我们就称这个集合为凸集。

所以,有这样的若干条直线,围成的凸多边形区域一定示凸集。

运筹学笔记3线性规划问题的几何特征            运筹学笔记3线性规划问题的几何特征

 

 

大家注意:圆面是不是凸集?肯定是的。因为在其内部任选两点。。。。

但是,圆并不是凸集,因为,在圆边上任选两个点,很显然并不完全在圆上。同理球面也不是。但是,球体是凸集。

顶点:就是不在任意两个点连线的内部(不含端点)的点;如下图的五个顶点(已标出);

运筹学笔记3线性规划问题的几何特征

 

上图看得到,凸多边形(正好构成一个凸集)的顶点,恰好就是凸多边形构成的凸集的顶点。  那么,圆面是一个凸集,那么圆面有没有顶点呢?有的,圆面的边界就是它的顶点。

 

上一篇:计算机中的数及编码


下一篇:SSA