文章目录
( C_N^T - C_B^T B^{-1}N ) 系数 分析
C_BX_B 分析
C_NX_N 分析
B^{-1}N 分析
在上一篇博客 【运筹学】线性规划数学模型 ( 单纯形法 | 最优解判定原则 | 可行解表示 | 目标函数推导 | 目标函数最大值分析 ) 博客中讲解了最优解判定的推导过程 , 基本原理就是
\begin{cases} X_B = B^{-1}b - B^{-1}NX_N \\ \\X_N \end{cases}max Z = C_B^TX_B + C_N^TX_N 中 ,
maxZ = b_0 + ( C_N^T - C_B^T B^{-1}N )X_N 目标函数 ,
( C_N^T - C_B^T B^{-1}N ) 系数小于等于
0 时 , 该目标函数才是最大值 , 该解是最优解 ;
单纯形法解线性规划的三大问题 : 查找初始基可行解 , 判定是否是最优解 , 如何迭代基可行解 , 当前讨论的问题是判定最优解 ;
一、
( C_N^T - C_B^T B^{-1}N ) 系数 分析
目标函数推导 :
\begin{array}{lcl} max Z &=& C_B^T ( B^{-1}b - B^{-1}NX_N ) + C_N^TX_N \\\\ &=& C_B^T B^{-1}b - C_B^T B^{-1}NX_N + C_N^TX_N\\\\ &=& b_0 + ( C_N^T - C_B^T B^{-1}N )X_N \\\\ &=& b_0 + \sigma_{m+1} x_{m+1} + \sigma_{m+2} x_{m+2} + \cdots + \sigma_{n} x_{n} \\\\ \end{array}上述分析到在
X_N = O 时 , 如果使目标函数取值最大 ,
\sigma_{m+1} x_{m+1} + \sigma_{m+2} x_{m+2} + \cdots + \sigma_{n} x_{n}系数都小于等于
0 时 , 满足上述要求 ;
上面的系数是通过
( C_N^T - C_B^T B^{-1}N ) 计算出来的 ;
C_N^T 是目标函数中 , 非基变量的系数 ;
C_B^T 是目标函数中 , 基变量的系数 ;
B^{-1}N :
B^{-1}N 是将基矩阵进行变换 , 将基矩阵变换为单位阵
I , 非基矩阵就是
B^{-1}N ;
二、
C_BX_B 分析
C_B 与
X_B 矩阵分析 :
C_B^T 矩阵与
X_B 的对应关系 ,
X_B =\begin{pmatrix} x_{1} \\ x_{2} \\ \vdots\\ x_m \end{pmatrix} ,
C_B =\begin{pmatrix} c_{1} \\ c_{2} \\ \vdots\\ c_m \end{pmatrix} ,
C_B^T =\begin{pmatrix} c_{1} \quad c_{2} \quad \cdots \quad c_m \end{pmatrix} ;
目标函数为
max Z = C_B^T X_B+ C_N^TX_N , 在目标函数中 , 有以下对应关系 :
其中的
C_B^T X_B = \begin{pmatrix} c_{1} \quad c_{2} \quad \cdots \quad c_m \end{pmatrix} \times \begin{pmatrix} x_{1} \\ x_{2} \\ \vdots\\ x_m \end{pmatrix} ,
c_1 与
x_1 对应 ,
c_m 与
x_m 对应 ;
三、
C_NX_N 分析
C_N 与
X_N 矩阵分析 :
C_N^T 矩阵与
X_N 的对应关系 ,
X_N =\begin{pmatrix} x_{m+1} \\ x_{m+2} \\ \vdots\\ x_n \end{pmatrix} ,
C_N =\begin{pmatrix} c_{m+1} \\ c_{m+2} \\ \vdots\\ c_n \end{pmatrix} ,
C_N^T =\begin{pmatrix} c_{m+1} \quad c_{m+2} \quad \cdots \quad c_n \end{pmatrix} ;
目标函数为
max Z = C_B^T X_B+ C_N^TX_N , 在目标函数中 , 有以下对应关系 :
同理 ,
C_N 与
X_N 矩阵计算 ,
C_N^T X_N = \begin{pmatrix} c_{m+1} \quad c_{m+2} \quad \cdots \quad c_n \end{pmatrix} \times \begin{pmatrix} x_{m+1} \\ x_{m+2} \\ \vdots\\ x_n \end{pmatrix} ,
c_{m+1} 与
x_{m+1} 对应 ,
c_n 与
x_n 对应 ;
四、
B^{-1}N 分析
B^{-1}N 分析 :
线性规划约束条件是
BX_B + NX_N = b , 其系数矩阵是
\begin{pmatrix} \, B \quad N \, \end{pmatrix} 样式的 , 在
BX_B + NX_N = b 两端都乘以
B^{-1} , 然后移项得到
X_B + B^{-1}NX_N= B^{-1}b, 此时当基变量是单位阵
I 时 , 非基变量就是
B^{-1}N , 系数矩阵是
\begin{pmatrix} \, I \quad B^{-1}N \, \end{pmatrix}五、单纯形表
通过计算
( C_N^T - C_B^T B^{-1}N ) , 是否是负数 , 可以判定当前的解是否是最优解 ;
将上述
C_N^T ,
C_B^T ,
B^{-1} ,
N 等写在一个表中 , 该表就是如下单纯形表 ;
在上述单纯形表中 , 假设前
m 个向量是基变量 , 将基变量对应的矩阵 , 变换为单位阵 , 单位阵
I 与
B^{-1}N 如下图所示 :
六、最优解判定
目标函数推导 :
\begin{array}{lcl} max Z &=& C_B^T ( B^{-1}b - B^{-1}NX_N ) + C_N^TX_N \\\\ &=& C_B^T B^{-1}b - C_B^T B^{-1}NX_N + C_N^TX_N\\\\ &=& b_0 + ( C_N^T - C_B^T B^{-1}N )X_N \\\\ &=& b_0 + \sigma_{m+1} x_{m+1} + \sigma_{m+2} x_{m+2} + \cdots + \sigma_{n} x_{n} \\\\ \end{array}最终目标是计算
\sigma_{m+1} , \sigma_{m+2} , \cdots , \sigma_{n} 系数是否小于等于
0 ;
上面已经推导出目标函数的系数是
( C_N^T - C_B^T B^{-1}N ) 矩阵 :
C_N^T=\begin{pmatrix} c_{m+1} \quad c_{m+2} \quad \cdots \quad c_n \end{pmatrix}C_B^T = \begin{pmatrix} c_{1} \quad c_{2} \quad \cdots \quad c_m \end{pmatrix}B^{-1}N =\begin{bmatrix} &a_{1,m+1} & \cdots & a_{1n} & \\\\ &\vdots & \vdots & \vdots & \\\\ &a_{m,m+1} & \cdots & a_{mn} & \end{bmatrix}( C_N^T - C_B^T B^{-1}N ) = \begin{pmatrix} c_{m+1} \quad c_{m+2} \quad \cdots \quad c_n \end{pmatrix} - \begin{pmatrix} c_{1} \quad c_{2} \quad \cdots \quad c_m \end{pmatrix} \times \begin{bmatrix} &a_{1,m+1} & \cdots & a_{1n} & \\\\ &\vdots & \vdots & \vdots & \\\\ &a_{m,m+1} & \cdots & a_{mn} & \end{bmatrix}= \begin{pmatrix} \sigma_{m+1} \quad \sigma_{m+2} \quad \cdots \quad \sigma_n \end{pmatrix}\sigma_j 个系数的公式如下 :
\sigma_j = c_j - \sum c_i a_{ij}其中
c_j 对应的是非基变量在目标函数系数 ,
c_i 是基变量在目标函数中的系数 ,
a_{ij} 是
B^{-1}N 中的矩阵向量 , 代表一列 ;
如 :
\begin{array}{lcl} \sigma_{m+1} &=& c_{m+1} - \sum_{i = 1}^{n} c_i a_{i, m+1} \\\\ &=& c_{m+1} - c_1a_{1,m+1} - c_2a_{2,m+1} - \cdots - c_na_{n,m+1} \end{array}如果所有的
\sigma_j 系数值, 都小于等于
0 , 说明该基可行解就是最优解 ;
最优解判定示例 :
① 不是最优解的情况 : 如果最终计算的系数是
max Z = 88 + 3x_6 - 4x_7 , 此时
x_6 的系数
\sigma_6 大于
0 , 该函数不是最优解 ;
② 是最优解的情况 : 如果最终计算的系数是
max Z = 88 - 3x_6 - 4x_7 , 所有的系数都是小于等于
0 的值 , 该基矩阵对应的解就是最优解 ;
只要有一个系数不是小于等于
0 的 , 那么该解就不是最优解 , 就需要继续向下迭代 ;
