当前位置：首页 > 编程资源 > 编程问答 >内容正文

编程问答

【运筹学】线性规划数学模型 ( 单纯形法 | 最优解判定原则 | 单纯形表 | 系数计算方法 | 根据系数是否小于等于 0 判定最优解 )

发布时间：2025/6/17 编程问答 55 豆豆

生活随笔收集整理的这篇文章主要介绍了【运筹学】线性规划数学模型 ( 单纯形法 | 最优解判定原则 | 单纯形表 | 系数计算方法 | 根据系数是否小于等于 0 判定最优解 ) 小编觉得挺不错的,现在分享给大家,帮大家做个参考.

文章目录

一、 $C_N^T - C_B^T B^{-1}N )$ 系数分析
二、 $C_B$ $X_B$ 分析
三、 $C_N$ $X_N$ 分析
四、 $B^{-1}N$ 分析
五、单纯形表
六、最优解判定

在上一篇博客【运筹学】线性规划数学模型 ( 单纯形法 | 最优解判定原则 | 可行解表示 | 目标函数推导 | 目标函数最大值分析 ) 博客中讲解了最优解判定的推导过程 , 基本原理就是

将可行解 ${XB=B−1b−B−1NXNXN\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 )$ 系数分析

目标函数推导 :

$maxZ=CBT(B−1b−B−1NXN)+CNTXN=CBTB−1b−CBTB−1NXN+CNTXN=b0+(CNT−CBTB−1N)XN=b0+σm+1xm+1+σm+2xm+2+⋯+σnxn\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$ 时 , 如果使目标函数取值最大 ,

$σm+1xm+1+σm+2xm+2+⋯+σnxn\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_B$ $X_B$ 分析

$C_B$ 与 $X_B$ 矩阵分析 :

$C_B^T$ 矩阵与 $X_B$ 的对应关系 , $XB=(x1x2⋮xm)X_B =\begin{pmatrix} x_{1} \\ x_{2} \\ \vdots\\ x_m \end{pmatrix}$ , $CB=(c1c2⋮cm)C_B =\begin{pmatrix} c_{1} \\ c_{2} \\ \vdots\\ c_m \end{pmatrix}$ , $CBT=(c1c2⋯cm)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$ , 在目标函数中 , 有以下对应关系 :

其中的 $CBTXB=(c1c2⋯cm)×(x1x2⋮xm)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_N$ $X_N$ 分析

$C_N$ 与 $X_N$ 矩阵分析 :

$C_N^T$ 矩阵与 $X_N$ 的对应关系 , $XN=(xm+1xm+2⋮xn)X_N =\begin{pmatrix} x_{m+1} \\ x_{m+2} \\ \vdots\\ x_n \end{pmatrix}$ , $CN=(cm+1cm+2⋮cn)C_N =\begin{pmatrix} c_{m+1} \\ c_{m+2} \\ \vdots\\ c_n \end{pmatrix}$ , $CNT=(cm+1cm+2⋯cn)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$ 矩阵计算 , $CNTXN=(cm+1cm+2⋯cn)×(xm+1xm+2⋮xn)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$ , 其系数矩阵是 $(BN)\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$ , 系数矩阵是 $(IB−1N)\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$ 如下图所示 :

六、最优解判定

目标函数推导 :

最终目标是计算 $σm+1,σm+2,⋯,σn\sigma_{m+1} , \sigma_{m+2} , \cdots , \sigma_{n}$ 系数是否小于等于 $0$ ;

上面已经推导出目标函数的系数是 $C_N^T - C_B^T B^{-1}N )$ 矩阵 :

$CNT=(cm+1cm+2⋯cn)C_N^T=\begin{pmatrix} c_{m+1} \quad c_{m+2} \quad \cdots \quad c_n \end{pmatrix}$
$CBT=(c1c2⋯cm)C_B^T = \begin{pmatrix} c_{1} \quad c_{2} \quad \cdots \quad c_m \end{pmatrix}$
$B−1N=[a1,m+1⋯a1n⋮⋮⋮am,m+1⋯amn]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}$

$σj\sigma_j$ 个系数的公式如下 :

$σj=cj−∑ciaij\sigma_j = c_j - \sum c_i a_{ij}$

其中 $c_j$ 对应的是非基变量在目标函数系数 , $c_i$ 是基变量在目标函数中的系数 , $a_{ij}$ 是 $B^{-1}N$ 中的矩阵向量 , 代表一列 ;

如 :

$σm+1=cm+1−∑i=1nciai,m+1=cm+1−c1a1,m+1−c2a2,m+1−⋯−cnan,m+1\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}$

如果所有的 $σj\sigma_j$ 系数值, 都小于等于 $0$ , 说明该基可行解就是最优解 ;

最优解判定示例 :

① 不是最优解的情况 : 如果最终计算的系数是 $max Z = 88 + 3x_6 - 4x_7$ , 此时 $x_6$ 的系数 $σ6\sigma_6$ 大于 $0$ , 该函数不是最优解 ;

② 是最优解的情况 : 如果最终计算的系数是 $max Z = 88 - 3x_6 - 4x_7$ , 所有的系数都是小于等于 $0$ 的值 , 该基矩阵对应的解就是最优解 ;

只要有一个系数不是小于等于 $0$ 的 , 那么该解就不是最优解 , 就需要继续向下迭代 ;

总结

以上是生活随笔为你收集整理的【运筹学】线性规划数学模型 ( 单纯形法 | 最优解判定原则 | 单纯形表 | 系数计算方法 | 根据系数是否小于等于 0 判定最优解 )的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。

上一篇：【运筹学】线性规划数学模型 ( 单纯形法
下一篇：【运筹学】线性规划数学模型 ( 单纯形法