2023-03-28 16:21:48
浏览数 (3)
文章目录
( 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 的 , 那么该解就不是最优解 , 就需要继续向下迭代 ;
