【运筹学】线性规划数学模型 ( 单纯形法 | 第二次迭代 | 方程组同解变换 | 生成新单纯形表 | 计算检验数 | 最优解判定 | 线性规划解个数分析 )

上一篇博客 【运筹学】线性规划数学模型 ( 单纯形法 | 第一次迭代 | 方程组同解变换 | 计算新单纯形表 | 计算检验数 | 入基变量选择 | 出基变量选择 | 第三次迭代 | 得到最优解 ) 中进行了线性规划的第一次迭代 , 本篇博客中进行第二次迭代 ;

一、第二次迭代

当前的方程组为 { 5 3 x 1 + 0 x 2 + x 3 − 1 3 x 4 = 30 1 3 x 1 + x 2 + 0 x 3 + 1 3 x 4 = 10 \begin{cases} \dfrac{5}{3} x_1 + 0x_2 + x_3 - \dfrac{1}{3} x_4 = 30 \\\\ \dfrac{1}{3}x_1 + x_2 + 0x_3 + \dfrac{1}{3}x_4 = 10 \end{cases} ⎩⎪⎪⎪⎨⎪⎪⎪⎧​35​x1​+0x2​+x3​−31​x4​=3031​x1​+x2​+0x3​+31​x4​=10​ , 选择 x 1 , x 2 x_1, x_2 x1​,x2​ 作为基变量 , 基矩阵为 ( 5 3 0 1 3 1 ) \begin{pmatrix} \quad \dfrac{5}{3} \quad 0 \quad \\\\ \quad \dfrac{1}{3} \quad 1 \quad \end{pmatrix} ⎝⎜⎜⎛​35​031​1​⎠⎟⎟⎞​ , 进行同解变换 , 将基矩阵转为单位阵 ;

二、方程组同解变换

方程 1 1 1 同解变换 :

将 5 3 x 1 + 0 x 2 + x 3 − 1 3 x 4 = 30 \dfrac{5}{3} x_1 + 0x_2 + x_3 - \dfrac{1}{3} x_4 = 30 35​x1​+0x2​+x3​−31​x4​=30 方程中的 x 1 x_1 x1​ 的系数变为 1 1 1 , x 2 x_2 x2​ 的系数为 0 0 0 保持不变 ;

方程的左右变量乘以 3 5 \dfrac{3}{5} 53​ :

5 3 x 1 + 0 x 2 + x 3 − 1 3 x 4 = 30 ( 5 3 x 1 + 0 x 2 + x 3 − 1 3 x 4 ) × 3 5 = 30 × 3 5 x 1 + 0 x 2 + 3 5 x 3 − 1 5 x 4 = 18 \begin{array}{lcl} \dfrac{5}{3} x_1 + 0x_2 + x_3 - \dfrac{1}{3} x_4 &=& 30 \\\\ ( \dfrac{5}{3} x_1 + 0x_2 + x_3 - \dfrac{1}{3} x_4 ) \times \dfrac{3}{5} &=& 30 \times \dfrac{3}{5} \\\\ x_1 + 0x_2 + \dfrac{3}{5} x_3 - \dfrac{1}{5}x_4 &=& 18 \end{array} 35​x1​+0x2​+x3​−31​x4​(35​x1​+0x2​+x3​−31​x4​)×53​x1​+0x2​+53​x3​−51​x4​​===​3030×53​18​

当前方程组变成 { x 1 + 0 x 2 + 3 5 x 3 − 1 5 x 4 = 18 1 3 x 1 + x 2 + 0 x 3 + 1 3 x 4 = 10 \begin{cases} x_1 + 0x_2 + \dfrac{3}{5} x_3 - \dfrac{1}{5}x_4 = 18 \\\\ \dfrac{1}{3}x_1 + x_2 + 0x_3 + \dfrac{1}{3}x_4 = 10 \end{cases} ⎩⎪⎪⎪⎨⎪⎪⎪⎧​x1​+0x2​+53​x3​−51​x4​=1831​x1​+x2​+0x3​+31​x4​=10​

方程 2 2 2 同解变换 : 将方程 1 1 1 乘以 − 1 3 -\dfrac{1}{3} −31​ , 与方程 2 2 2 相加 ;

① 方程 1 1 1 乘以 − 1 3 -\dfrac{1}{3} −31​ :

( x 1 + 0 x 2 + 3 5 x 3 − 1 5 x 4 ) × − 1 3 = 18 × − 1 3 − 1 3 x 1 + 0 x 2 + − 1 5 x 3 + 1 15 x 4 = − 6 \begin{array}{lcl} ( x_1 + 0x_2 + \dfrac{3}{5} x_3 - \dfrac{1}{5}x_4 ) \times -\dfrac{1}{3} &=& 18 \times -\dfrac{1}{3} \\\\ -\dfrac{1}{3} x_1 + 0x_2 + -\dfrac{1}{5}x_3 + \dfrac{1}{15} x_4 &=& -6 \end{array} (x1​+0x2​+53​x3​−51​x4​)×−31​−31​x1​+0x2​+−51​x3​+151​x4​​==​18×−31​−6​

② 与方程 2 2 2 相加 :

( − 1 3 x 1 + 0 x 2 + − 1 5 x 3 + 1 15 x 4 ) + ( 1 3 x 1 + x 2 + 0 x 3 + 1 3 x 4 ) = − 6 + 10 0 x 1 + x 2 − 1 5 x 3 + 2 5 x 4 = 4 \begin{array}{lcl} (-\dfrac{1}{3} x_1 + 0x_2 + -\dfrac{1}{5}x_3 + \dfrac{1}{15} x_4) + (\dfrac{1}{3}x_1 + x_2 + 0x_3 + \dfrac{1}{3}x_4)&=& -6 + 10 \\\\ 0x_1 + x_2 -\dfrac{1}{5}x_3 + \dfrac{2}{5} x_4 &=& 4 \end{array} (−31​x1​+0x2​+−51​x3​+151​x4​)+(31​x1​+x2​+0x3​+31​x4​)0x1​+x2​−51​x3​+52​x4​​==​−6+104​

当前方程组变成 { x 1 + 0 x 2 + 3 5 x 3 − 1 5 x 4 = 18 0 x 1 + x 2 − 1 5 x 3 + 6 15 x 4 = 4 \begin{cases} x_1 + 0x_2 + \dfrac{3}{5} x_3 - \dfrac{1}{5}x_4 = 18 \\\\ 0x_1 + x_2 -\dfrac{1}{5}x_3 + \dfrac{6}{15} x_4 = 4 \end{cases} ⎩⎪⎪⎪⎨⎪⎪⎪⎧​x1​+0x2​+53​x3​−51​x4​=180x1​+x2​−51​x3​+156​x4​=4​

三、生成新的单纯形表

更新一下单纯形表 : 将第三次迭代的矩阵填入下面的单纯形表中 ;

c j c_j cj​ c j c_j cj​ 3 3 3 4 4 4 0 0 0 0 0 0 C B C_B CB​ 基变量系数 (目标函数)基变量常数 b b b x 1 x_1 x1​ x 2 x_2 x2​ x 3 x_3 x3​ x 4 x_4 x4​ θ i \theta_i θi​ 0 0 0 ( 目标函数 x 3 x_3 x3​ 系数 c 3 c_3 c3​ ) x 3 x_3 x3​ 40 40 40 2 2 2 1 1 1 1 1 1 0 0 0 40 40 40 ( θ 3 \theta_3 θ3​ ) 0 0 0 ( 目标函数 x 4 x_4 x4​ 系数 c 4 c_4 c4​) x 4 x_4 x4​ 30 30 30 1 1 1 3 3 3 0 0 0 1 1 1 10 10 10 ( θ 4 \theta_4 θ4​ ) σ j \sigma_j σj​ 3 3 3 ( σ 1 \sigma_1 σ1​ ) 4 4 4 ( σ 2 \sigma_2 σ2​ ) 0 0 0 0 0 0第一次迭代––––––– 0 0 0 ( 目标函数 x 3 x_3 x3​ 系数 c 3 c_3 c3​ ) x 3 x_3 x3​ 30 30 30 5 3 \dfrac{5}{3} 35​ 0 0 0 1 1 1 − 1 3 -\dfrac{1}{3} −31​ 18 18 18 ( θ 3 \theta_3 θ3​ ) 4 4 4 ( 目标函数 x 2 x_2 x2​ 系数 c 2 c_2 c2​) x 2 x_2 x2​ 10 10 10 1 3 \dfrac{1}{3} 31​ 1 1 1 0 0 0 1 3 \dfrac{1}{3} 31​ 30 30 30 ( θ 2 \theta_2 θ2​ ) σ j \sigma_j σj​ ( 检验数 ) 5 3 \dfrac{5}{3} 35​ ( σ 1 \sigma_1 σ1​ ) 0 0 0 0 0 0 − 4 3 -\dfrac{4}{3} −34​ ( σ 4 \sigma_4 σ4​ )第二次迭代––––––– 3 3 3 ( 目标函数 x 1 x_1 x1​ 系数 c 1 c_1 c1​ ) x 1 x_1 x1​ 18 18 18 1 1 1 0 0 0 3 5 \dfrac{3}{5} 53​ − 1 5 -\dfrac{1}{5} −51​ ? ? ? ( θ 3 \theta_3 θ3​ ) 4 4 4 ( 目标函数 x 2 x_2 x2​ 系数 c 2 c_2 c2​) x 2 x_2 x2​ 4 4 4 0 0 0 1 1 1 − 1 5 -\dfrac{1}{5} −51​ 2 5 \dfrac{2}{5} 52​ ? ? ? ( θ 2 \theta_2 θ2​ ) σ j \sigma_j σj​ ( 检验数 ) 0 0 0 0 0 0 ? ? ? ( σ 3 \sigma_3 σ3​ ) ? ? ? ( σ 4 \sigma_4 σ4​ ) 四、计算检验数、最优解判定

计算检验数 σ \sigma σ :

σ 3 = 0 − 3 × 3 5 − 4 × ( − 1 5 ) = − 9 5 + 4 5 = − 1 \sigma_3 = 0 - 3 \times \dfrac{3}{5} - 4 \times (-\dfrac{1}{5}) = -\dfrac{9}{5} + \dfrac{4}{5} = -1 σ3​=0−3×53​−4×(−51​)=−59​+54​=−1

σ 4 = 0 − 3 × ( − 1 5 ) − 4 × 2 5 = 3 5 − 8 5 = − 1 \sigma_4 = 0 - 3 \times (-\dfrac{1}{5}) - 4 \times \dfrac{2}{5} = \dfrac{3}{5} - \dfrac{8}{5} = -1 σ4​=0−3×(−51​)−4×52​=53​−58​=−1

两个非基变量的检验数都是小于等于 0 0 0 的 , 因此该基可行解 ( 18 4 0 0 ) \begin{pmatrix} \quad 18 \quad \\ \quad 4 \quad \\ \quad 0 \quad \\ \quad 0 \quad \end{pmatrix} ⎝⎜⎜⎛​18400​⎠⎟⎟⎞​是最优解 ;

五、最优解个数说明 1、唯一最优解

唯一最优解 : 上述示例中有最优解 , 两个检验数全都小于 0 0 0 , 说明该线性规划有唯一最优解 ;

如果有一个检验数等于 0 0 0 , 该线性规划有无穷多最优解 ; 如果非基变量系数都是负数 , 该线性规划有无界解

2、无穷最优解

无数最优解 : 如果线性规划中有两个最优解 , 那么这两个最优解之间的连线都是最优解 , 那么该线性规划有无数个最优解 ;

无数最优解示例 : 非基变量检验数为 0 0 0 , 就会产生无穷最优解 ;

• 假如计算检验数时 , 有一个非基变量的检验数小于 0 0 0 , 另外一个 检验数等于 0 0 0 ;

• 假设目标函数是 m a x Z = b 0 + 0 x 7 − 10 x 8 maxZ = b^0 + 0x_7 - 10x_8 maxZ=b0+0x7​−10x8​ 形式的 , 一个系数为 0 0 0 , 一个系数为 − 10 -10 −10 ;

• 此时 x 7 x_7 x7​ 不论取何值 , 都是最优解 , 该线性规划就有无数个最优解 ;

3、无界解

无界解 :

假设线性规划是如下方程组 { 2 x 1 − x 2 + x 3 = 40 x 1 − 3 x 2 + x 4 = 30 \begin{cases} 2x_1 - x_2 + x_3 = 40 \\\\ x_1 - 3x_2 + x_4 = 30 \end{cases} ⎩⎪⎨⎪⎧​2x1​−x2​+x3​=40x1​−3x2​+x4​=30​ , 该线性规划一定没有最优解 ;

构造一个解 ( 0 k 40 + k 30 + 3 k ) \begin{pmatrix} \quad 0 \quad \\ \quad k \quad \\ \quad 40 + k \quad \\ \quad 30 + 3k \quad \end{pmatrix} ⎝⎜⎜⎛​0k40+k30+3k​⎠⎟⎟⎞​ , 其中 k k k 是任意一个大于 0 0 0 的正数 , ∀ k > 0 \forall k >0 ∀k>0 ;

当 k k k 大于等于 0 0 0 时 , 该解是线性规划的解 , 将上述解代入目标函数中 , 目标函数可以取值到正无穷 , 该解是无界解 ;

无界解的情况总结 ( 找不到出基变量 ) :

• 找不到出基变量 : 找到初始基可行解 , 其检验数大于 0 , 但是找不到出基变量 ;
• 出基变量选择 : 出基变量是需要常数项除以对应非基变量系数中大于 0 0 0 的数 , 取较小的那个系数对应的基变量 ;
• 这里两个系数都小于 0 0 0 , 找不到出基变量 , 此时无法继续进行迭代 , 这种情况下目标函数取不到最大值 , 目标函数可以取值无限大 ;

4、总结

根据检验数判定 :

• 唯一最优解 : 检验数全部小于 0 0 0 ;
• 无穷最优解 : 检验数有一个等于 0 0 0 ;
• 无界解: 能根据检验数找到入基变量 , 假如某个非基变量的系数全部小于 0 0 0 , 无法找到出击变量 , 此时是无界解 ;

线性规划无解的情况 : 线性规划中 , 假设是有初始基可行解的 , 如果没有解 , 初始基可行解也不存在 ;

六、出基变量选择说明

每次迭代时 , 先找到入基变量 ( 换入变量 ) , 然后根据换入变量计算 θ \theta θ 值 , 找到出基变量 ( 换出变量 ) ;

出基变量查找方法 : 使用 常数项 , 与 入基变量中大于 0 0 0 的系数 做除法 , 如果有小于 0 0 0 的系数 , 那么不进行计算 , 该值没有任何参考价值 ;