文章目录
X_N = O 目标函数最大 分析
在上一篇博客 【运筹学】线性规划数学模型 ( 单纯形法原理 | 单纯形法流程 | 查找初始基可行解 ) 中 , 讲解到了使用单纯形法求解线性规划问题 , 需要解决以下三个主要问题 :
该博客中已经讲解了如何查找初始基可行解 , 查找初始基可行解时 , 优先选择单位阵作为基矩阵 , 单位阵
I 对应的基解 , 必定是基可行解 ;
( 如果没有单位阵
I , 那么后续在讨论 )
本博客开始讲解 , 如何 判定最优解 ( 最优解是如何确定出来的 ) , 和 如何迭代到下一个基可行解 ;
一、基矩阵 + 非基矩阵 约束条件
目标函数 , 用于判定
1 个基可行解是否是最优解 ;
在 【运筹学】线性规划数学模型 ( 求解基矩阵示例 | 矩阵的可逆性 | 线性规划表示为 基矩阵 基向量 非基矩阵 非基向量 形式 ) 博客中 , 根据推导 , 线性规划的约束条件 , 可以表示为 :
BX_B + NX_N = b二、基矩阵 + 非基矩阵 线性规划
将上述约束条件代入线性规划标准形式中
\begin{array}{lcl}max Z = \sum_{j=1}^{n}c_j x_j\\ \\ \begin{cases} \sum_{j=1}^{n} a_{ij}x_j = b_i & (i = 1 , 2 \cdots m) \\ \\x_j \geq 0 & (i = 1 , 2 \cdots n) \end{cases}\end{array} 得到如下形式 :
\begin{array}{lcl}max Z = C_B^TX_B + C_N^TX_N \\ \\ \begin{cases} BX_B + NX_N = b \\ \\x_j \geq 0 & (i = 1 , 2 \cdots n) \end{cases}\end{array}假设得到基解
\begin{cases} X_B = B^{-1}b \\ \\X_N = O \end{cases} , 其中
O 表示零矩阵 , 矩阵张红每个元素的值都是
0 ;
判断该基解
\begin{pmatrix} X_B \\ X_N \\ \end{pmatrix} 是否是最优解 , 需要从目标函数
max Z = C_B^TX_B + C_N^TX_N 开始分析 ;
三、线性规划 可行解
从现在开始不再讨论基解了 , 回到之前 , 讨论可行解 ,
X_N 可以取值任意合法值 , 而不是取
O 矩阵值 , 查看取值其它值的时候 , 目标函数是否有最大值 , 这里 重新进行解的推导 :
在 【运筹学】线性规划数学模型 ( 线性规划求解 | 根据非基变量的解得到基变量解 | 基解 | 基可行解 | 可行基 ) 二、根据非基变量的解得到可行解 博客章节 , 在
BX_B + NX_N = b 两端都乘以
B^{-1} , 然后移项得到了 :
X_B = B^{-1}b - B^{-1}NX_N将上述可行解 , 列举出来 :
\begin{cases} X_B = B^{-1}b - B^{-1}NX_N \\ \\X_N \end{cases}四、目标函数 推导
此时进行判定线性规划可行解
\begin{cases} X_B = B^{-1}b - B^{-1}NX_N \\ \\X_N \end{cases} 中 ,
X_N 取值
O 矩阵 , 是否是最好的情况 , 即目标函数达到最大值 , 目标函数如下 :
max Z = C_B^TX_B + C_N^TX_N将
X_B = B^{-1}b - B^{-1}NX_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 \end{array}C_B^T B^{-1}b 计算结果是一个数值常量 , 可以写成
b_0 , 与
X (
n 个决策变量 ) 无关 ;
\begin{array}{lcl} &=& b_0 + ( C_N^T - C_B^T B^{-1}N )X_N \\\\ \end{array}之前的基解的策略是 , 将
X_N 取值为
O 零矩阵 , 现在讨论 , 要使上述目标函数
maxZ 最大 , 分析
X_N = O 是否是最好的选择 , 即分析
X_N = O 是否是使
maxZ 目标函数最大的值 ;
假设
X_N 矩阵中的变量值为
\begin{pmatrix} x_{m+1} \\ x_{m+2} \\ \vdots\\ x_n \end{pmatrix} ,
( C_N^T - C_B^T B^{-1}N ) 的计算结果是
\begin{pmatrix} \sigma_{m+1} , \sigma_{m+2} , \cdots , \sigma_n \end{pmatrix} ,
( C_N^T - C_B^T B^{-1}N )X_N 结果是
\sigma_{m+1} x_{m+1} + \sigma_{m+2} x_{m+2} + \cdots + \sigma_{n} x_{n}\begin{array}{lcl} &=& 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 目标函数最大 分析
当上述
X_N 矩阵中的变量值
\begin{pmatrix} x_{m+1} \\ x_{m+2} \\ \vdots\\ x_n \end{pmatrix} 都为
0 时 , 假如上述公式取值最大值 , 即
b_0 + \sigma_{m+1} x_{m+1} + \sigma_{m+2} x_{m+2} + \cdots + \sigma_{n} x_{n}取值最大值 ;
在线性规划约束条件中 , 所有的变量都是大于等于
0 的 , 每个
x_j 约束变量取值都可以大于等于
0 , 目前是查看当所有的
x_j 变量都取值
0 时 , 目标函数达到最大值的情况 ;
当
X_N 取值等于
O 零矩阵时 , 目标函数值等于
b_0 , 当
X_N 中有元素取值大于
0 时 , 就会在
b_0 基础上加上一个值 , 如果这个值是 小于等于
0 的 , 那么对应的
x_j 取值越大 , 目标函数值越小 ;
因此这里得到 , 在
X_N=\begin{pmatrix} x_{m+1} \\ x_{m+2} \\ \vdots\\ x_n \end{pmatrix} 非基变量前的系数是小于等于
0 时 , 才能满足当
X_N 中的元素取值等于
0 时 , 目标函数是最大值 ;
因此
b_0 + \sigma_{m+1} x_{m+1} + \sigma_{m+2} x_{m+2} + \cdots + \sigma_{n} x_{n}中的
\sigma_{m+1} , \sigma_{m+2} , \cdots , \sigma_{n} 系数值小于等于
0 , 其中每个系数对应的变量
x_{j} 必定是大于等于
0 的值 , 那么系数
\sigma_{m+1} 小于等于
0 时 , 每个变量取值
x_j = 0 , 目标函数达到最小值 ;
六、总结
将线性规划约束条件表示为
BX_B + NX_N = b进行变换后得到
X_B = B^{-1}b - B^{-1}NX_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 , 当
X_N 取值为
0 时 , 目标函数得到最大值 ;
