文章目录

在上一篇博客 【运筹学】线性规划数学模型 ( 单纯形法 | 最优解判定原则 | 单纯形表 | 系数计算方法 | 根据系数是否小于等于 0 判定最优解 ) 博客中讲解了最优解判定原则 , 基本原理就是

目标函数推导后的结果 maxZ=b0+(CNT−CBTB−1N)XNmaxZ = b_0 + ( C_N^T - C_B^T B^{-1}N )X_NmaxZ=b0​+(CNT​−CBT​B−1N)XN​ ;

如果满足条件 : "当 XN=OX_N = OXN​=O 时 , 目标函数取值最大" , 那么该 BBB 矩阵对应的基可行解就是最优解 ( 根据定理得出 ) ;

在 (CNT−CBTB−1N)( C_N^T - C_B^T B^{-1}N )(CNT​−CBT​B−1N) 计算结果中 , 每个分量的值都小于等于 000 时 , 该解就是最优解;

将 CNC_NCN​ , CBC_BCB​ , B−1NB^{-1}NB−1N 写入单纯形表中 , 方便计算 ;

(CNT−CBTB−1N)=(cm+1cm+2⋯cn)−(c1c2⋯cm)×[a1,m+1⋯a1n⋮⋮⋮am,m+1⋯amn]( 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}(CNT​−CBT​B−1N)=(cm+1​cm+2​⋯cn​​)−(c1​c2​⋯cm​​)×⎣⎢⎢⎢⎢⎢⎡​​a1,m+1​⋮am,m+1​​⋯⋮⋯​a1n​⋮amn​​​⎦⎥⎥⎥⎥⎥⎤​

根据上述公式 , 每个系数的计算公式为 : σj=cj−∑ciaij\sigma_j = c_j - \sum c_i a_{ij}σj​=cj​−∑ci​aij​ , 其中 cjc_jcj​ 对应的是非基变量在目标函数系数 , cic_ici​ 是基变量在目标函数中的系数 , aija_{ij}aij​ 是 B−1NB^{-1}NB−1N 中的矩阵向量 , 代表一列 ;

单纯形法解线性规划的三大问题 :查找初始基可行解 , 判定是否是最优解 , 如何迭代基可行解 ;

在前几篇博客中讲解了 如何查找初始基可行解 , 与 判定是否是最优解 , 本篇博客中讲解 如何进行迭代 ;

一、单纯形法计算示例

使用单纯形法求解线性规划最优解 :

maxZ=3x1+4x2{2x1+x2≤40x1+3x2≤30xj≥0(j=1,2)\begin{array}{lcl} max Z = 3x_1 + 4x_2 \\ \\ \begin{cases} 2 x_1 + x_2 \leq 40 \\\\ x_1 + 3x_2 \leq 30 \\ \\x_j \geq 0 & (j = 1 , 2 ) \end{cases}\end{array}maxZ=3x1​+4x2​⎩⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎧​2x1​+x2​≤40x1​+3x2​≤30xj​≥0​(j=1,2)​​

二、转化标准形式

首先将该线性规划转为标准形式 :

参考 【运筹学】线性规划数学模型标准形式 ( 标准形式 | 目标函数转化 | 决策变量转化 | 约束方程转化 | 固定转化顺序 | 标准形式转化实例 ) 线性规划 普通形式 -> 标准形式 转化顺序说明 博客 , 先处理变量约束 , 再将不等式转为等式 , 最后更新目标函数 ;

① 变量约束 :首先查看变量约束 , 两个变量都是 ≥0\geq 0≥0 的 , 符合线性规划标准形式要求 ;

② 不等式转换 :两个等式都是 小于等于不等式 , 需要 在不等式左侧加入松弛变量 , 将其转为等式 ;

2x1+x2≤402 x_1 + x_2 \leq 402x1​+x2​≤40 , 左侧加入松弛变量 x3x_3x3​ , 变为 2x1+x2+x3=402 x_1 + x_2 + x_3 = 402x1​+x2​+x3​=40x1+3x2≤30x_1 + 3x_2 \leq 30x1​+3x2​≤30 , 左侧加入松弛变量 x4x_4x4​ , 变为 x1+3x2+x4=30x_1 + 3x_2 + x_4 = 30x1​+3x2​+x4​=30

③ 更新目标函数 :将 x3x_3x3​ 和 x4x_4x4​ 加入到目标函数中 , 得到新的目标函数 maxZ=3x1+4x2+0x3+0x4max Z = 3x_1 + 4x_2 + 0x_3 + 0x_4maxZ=3x1​+4x2​+0x3​+0x4​ ;

此时线性规划标准形式为 :

maxZ=3x1+4x2+0x3+0x4{2x1+x2+x3+0x4=40x1+3x2+0x3+x4=30xj≥0(j=1,2,3,4)\begin{array}{lcl} max Z = 3x_1 + 4x_2 + 0x_3 + 0x_4 \\ \\ \begin{cases} 2 x_1 + x_2 + x_3 + 0x_4 = 40 \\\\ x_1 + 3x_2 + 0x_3 + x_4 = 30 \\\\ x_j \geq 0 & (j = 1 , 2 , 3 , 4 ) \end{cases}\end{array}maxZ=3x1​+4x2​+0x3​+0x4​⎩⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎧​2x1​+x2​+x3​+0x4​=40x1​+3x2​+0x3​+x4​=30xj​≥0​(j=1,2,3,4)​​

三、查找初始基可行解

找基矩阵 :

上述线性规划标准形式的系数矩阵为 [21101301]\begin{bmatrix} &2 & 1 & 1 & 0 & \\\\ & 1 & 3 & 0 & 1 & \end{bmatrix}⎣⎡​​21​13​10​01​​⎦⎤​ , 其中子矩阵中有 [1001]\begin{bmatrix} & 1 & 0 & \\\\ & 0 & 1 & \end{bmatrix}⎣⎡​​10​01​​⎦⎤​ 单位阵 III ;

使用该单位阵 III 作为基矩阵 , 单位阵肯定是可逆的 , 其对应的基解 , 解出后的值就是右侧的常数值 , 肯定大于等于 000 , 是基可行解 ;

四、列出单纯形表

列出单纯形表 :

基变量是 x3x_3x3​ 和 x4x_4x4​ , 基变量在约束条件中的系数矩阵 [1001]\begin{bmatrix} &1 & 0 & \\\\ &0 & 1 & \end{bmatrix}⎣⎡​​10​01​​⎦⎤​ 就是基矩阵 , 这是个单位阵 ;

基变量是 x3x_3x3​ 和 x4x_4x4​ 在目标函数中的系数是 (00)\begin{pmatrix} \quad 0 \quad 0 \quad \end{pmatrix}(00​) ;

此时的基解是 (004030)\begin{pmatrix} \quad 0 \quad \\ \quad 0 \quad \\ \quad 40 \quad \\ \quad 30 \quad \\ \end{pmatrix}⎝⎜⎜⎛​004030​⎠⎟⎟⎞​ , 该解是初始解 , 下面判定该解是否是最优解 ;

五、最优解判定

使用 检验数矩阵 (CNT−CBTB−1N)( C_N^T - C_B^T B^{-1}N )(CNT​−CBT​B−1N) 判断上述解 , 是否是最优解 , 该矩阵计算结果中所有的数 , 都是检验数 σ\sigmaσ , 如果 所有的数都小于等于 000 , 说明该解就是最优解 ;

这里只求非基变量的检验数 , 即 x1x_1x1​ , x2x_2x2​ 的检验数 ;

列出目标函数非基变量系数 (CNT−CBTB−1N)( C_N^T - C_B^T B^{-1}N )(CNT​−CBT​B−1N) 矩阵 :

非基变量在目标函数中的系数矩阵 :CNT=(34)C_N^T=\begin{pmatrix} \quad 3 \quad 4 \quad \end{pmatrix}CNT​=(34​)

基变量在目标函数中的叙述矩阵 :CBT=(00)C_B^T = \begin{pmatrix} \quad 0 \quad 0 \quad \end{pmatrix}CBT​=(00​)

B−1NB^{-1}NB−1N 是系数矩阵中经过矩阵变换后 , 基变量系数是单位阵 III , 非基变量系数是 B−1NB^{-1}NB−1N :B−1N=[2113]B^{-1}N =\begin{bmatrix} &2 & 1 & \\\\ &1 & 3 & \end{bmatrix}B−1N=⎣⎡​​21​13​​⎦⎤​

(CNT−CBTB−1N)=CNT=(34)−(00)×[2113]( C_N^T - C_B^T B^{-1}N ) = C_N^T=\begin{pmatrix} \quad 3 \quad 4 \quad \end{pmatrix} - \begin{pmatrix} \quad 0 \quad 0 \quad \end{pmatrix} \times \begin{bmatrix} &2 & 1 & \\\\ &1 & 3 & \end{bmatrix}(CNT​−CBT​B−1N)=CNT​=(34​)−(00​)×⎣⎡​​21​13​​⎦⎤​

=(σ1σ2)= \begin{pmatrix} \quad \sigma_{1} \quad \sigma_{2} \quad \end{pmatrix}=(σ1​σ2​​)

其中 σ1\sigma_{1}σ1​ 是目标函数中 x1x_1x1​ 的系数 , σ2\sigma_{2}σ2​ 是目标函数中的 x2x_2x2​ 的系数 ;

如果上述两个系数都小于等于 000 , 那么当 非基变量 XN=(x1x2)X_N =\begin{pmatrix} x_{1} \\ x_{2} \end{pmatrix}XN​=(x1​x2​​) 取值为 000 时 , 目标函数取值最大 ;

系数的计算公式为 : σj=cj−∑ciaij\sigma_j = c_j - \sum c_i a_{ij}σj​=cj​−∑ci​aij​ , 其中 cjc_jcj​ 对应的是非基变量在目标函数系数 , cic_ici​ 是基变量在目标函数中的系数 , aija_{ij}aij​ 是 B−1NB^{-1}NB−1N 中的矩阵向量 , 代表一列 ;

σ1=c1−(c3a11+c4a12)\sigma_{1} = c_1 - ( c_3 a_{11} + c_4 a_{12} )σ1​=c1​−(c3​a11​+c4​a12​)

σ1=3−(0×2)−(0×1)=3\sigma_{1} =3 - (0 \times 2) - (0 \times 1) = 3σ1​=3−(0×2)−(0×1)=3 , 是从下面的单纯形表中的如下位置提取的数值 ;

σ2=c2−(c3a21+c4a22)\sigma_{2} = c_2 - ( c_3 a_{21} + c_4 a_{22} )σ2​=c2​−(c3​a21​+c4​a22​)

σ2=4−(0×1)−(0×3)=4\sigma_{2} =4 - (0 \times 1) - (0 \times 3) = 4σ2​=4−(0×1)−(0×3)=4 , 是从下面的单纯形表中的如下位置提取的数值 ;

如果这两个系数 , 如果都小于等于 000 , 该 基可行解(004030)\begin{pmatrix} \quad 0 \quad \\ \quad 0 \quad \\ \quad 40 \quad \\ \quad 30 \quad \\ \end{pmatrix}⎝⎜⎜⎛​004030​⎠⎟⎟⎞​ 才是最优解 , 这两个系数都大于 000 , 因此不是最优解 ;