运筹学概念 _原创精品文档.pdfVIP

运筹学基本概念

➢线性规划问题的基与解

LP：max(min)z=CX（1-1）

s.tAX=b（1-2）

X=0（1-3）

设A施m*n矩阵，且A的秩为m，则有

可行解：满足上述约束条件（1-2）、（1-3）的向量X称为可行解。

最优解：满足式（1-1）的可行解称为最优解

基：A中任何一组m个线性无关的列向量构成的子矩阵B，称为该问题的一个基，

即B为A的m*m非奇异子矩阵。

基向量：基B中的一列即为B的一个基向量。基B中公寓m个基向量

非基向量：矩阵A中基B之外的一列即为B的一个非基向量。A中共有n-m个非

基向量。

基变量：与基B的基向量相应的变量恒伟B的基变量，基变量共有m个。

非基变量：与基B非基向量相应的变量称为B的非基变量，非基变量共有n-m个。

基本解：对于基B，令所有非基变量为零，求得满足式（1-2）的解，称为B对应

的基本解。

基本可行解：满足式（1-3）的基本解称为基本可行解，其对应的基称为可行基。

基本最优解：满足式（1-1）的基本可行解称为基本最优解，其对应的基称为最优

基。

退化的基本解：若基本解中有基变量为零这，则称之为退化的基本解。类似地，

有退化的基本可行解和退化的基本最优解。

➢几何意义上的几个基本概念

凸集：设S是n维空间的一个点集，若任意两点X（1）、X(2)∈S的所连线

段上的一切点αX（1）+（1-α）X(2)，（0=α=1），则称S为凸集。

凸组合：设X（1）、X(2)……X（K）,为n维空间中的k个点。则X=μ1X（1）

+μ2X(2)+μkX（K）（0=μi=1，i=1,2……k,且μ1+……μk=1）称为X

（1）、X(2)……X（K）的凸组合。

极点：S是凸集，X∈S，若X不能用S中相异的两点X（1）、X(2)线性表示

为：

X=αX（1）+（1-α）X(2)，α∈（0,1），则称X为S的极点或定点。即极点

不能成为任何线段的内点。

➢线性规划问题的基本定理

定理1-1线性规划问题的可行域S是凸集

定理1-2X是可行域S上极点的充要条件是它为基本可行解。

定理1-3线性规划问题的任一可行解均可表示为基本可行解的凸组合。

定理1-4如果线性规划问题有有限最优解，则其最优值一定可以再可行域的极

点上达到。

➢最优性检验及解的判别准则

最优解的判别准则若X（0）=（b1,b2,……bm，0，……，0）‘为对应于基

B的一个基本可行解，且对一切j=m+1,……，n有Δj=0，则X（0）为最优

解。

多重最优解判别准则若X（0）=（b1,b2,……bm，0，……，0）‘为一基本

可行解，对于一切j=m+1,……，n有Δj=0，且有存在某个非基变量的检验

数Δm+k=0，则线性规划问题有多重最优解。

无最优解判别准则若X（0）=（b1,b2,……bm，0，……，0）‘为一基本可

行解，至少有一个Δm+k0，并且对i=1,2……，m均有ai,m+k=0，那么线

性规划问题无最优解（或称具有无界解）

➢对偶关系

原问题（或对偶问题）对偶问题（或原问题）

目标函数maxz目标函数minw

n个变量