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

编程问答

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

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

文章目录

一、第二次迭代
二、方程组同解变换
三、生成新的单纯形表
四、计算检验数、最优解判定
五、最优解个数说明
- 1、唯一最优解
- 2、无穷最优解
- 3、无界解
- 4、总结
六、出基变量选择说明

一、第二次迭代

当前的方程组为 ${53x1+0x2+x3−13x4=3013x1+x2+0x3+13x4=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}$ , 选择 $x_1, x_2$ 作为基变量 , 基矩阵为 $(530131)\begin{pmatrix} \quad \dfrac{5}{3} \quad 0 \quad \\\\ \quad \dfrac{1}{3} \quad 1 \quad \end{pmatrix}$ , 进行同解变换 , 将基矩阵转为单位阵 ;

二、方程组同解变换

方程 $1$ 同解变换 :

将 $53x1+0x2+x3−13x4=30\dfrac{5}{3} x_1 + 0x_2 + x_3 - \dfrac{1}{3} x_4 = 30$ 方程中的 $x_1$ 的系数变为 $1$ , $x_2$ 的系数为 $0$ 保持不变 ;

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

$53x1+0x2+x3−13x4=30(53x1+0x2+x3−13x4)×35=30×35x1+0x2+35x3−15x4=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}$

当前方程组变成 ${x1+0x2+35x3−15x4=1813x1+x2+0x3+13x4=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}$

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

① 方程 $1$ 乘以 $−13-\dfrac{1}{3}$ :

$(x1+0x2+35x3−15x4)×−13=18×−13−13x1+0x2+−15x3+115x4=−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}$

② 与方程 $2$ 相加 :

$(−13x1+0x2+−15x3+115x4)+(13x1+x2+0x3+13x4)=−6+100x1+x2−15x3+25x4=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}$

当前方程组变成 ${x1+0x2+35x3−15x4=180x1+x2−15x3+615x4=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}$

三、生成新的单纯形表

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

c_j

c_j

3

4

0

0

$C_B$ 基变量系数 (目标函数)	基变量	常数 $b$	$x_1$	$x_2$	$x_3$	$x_4$	$θi\theta_i$
$0$ ( 目标函数 $x_3$ 系数 $c_3$ )	$x_3$	$40$	$2$	$1$	$1$	$0$	$40$ ( $θ3\theta_3$ )
$0$ ( 目标函数 $x_4$ 系数 $c_4$ )	$x_4$	$30$	$1$	$3$	$0$	$1$	$10$ ( $θ4\theta_4$ )
$σj\sigma_j$			$3$ ( $σ1\sigma_1$ )	$4$ ( $σ2\sigma_2$ )	$0$	$0$
第一次迭代	–	–	–	–	–	–	–
$0$ ( 目标函数 $x_3$ 系数 $c_3$ )	$x_3$	$30$	$53\dfrac{5}{3}$	$0$	$1$	$−13-\dfrac{1}{3}$	$18$ ( $θ3\theta_3$ )
$4$ ( 目标函数 $x_2$ 系数 $c_2$ )	$x_2$	$10$	$13\dfrac{1}{3}$	$1$	$0$	$13\dfrac{1}{3}$	$30$ ( $θ2\theta_2$ )
$σj\sigma_j$ ( 检验数 )			$53\dfrac{5}{3}$ ( $σ1\sigma_1$ )	$0$	$0$	$−43-\dfrac{4}{3}$ ( $σ4\sigma_4$ )
第二次迭代	–	–	–	–	–	–	–
$3$ ( 目标函数 $x_1$ 系数 $c_1$ )	$x_1$	$18$	$1$	$0$	$35\dfrac{3}{5}$	$−15-\dfrac{1}{5}$	$?$ ( $θ3\theta_3$ )
$4$ ( 目标函数 $x_2$ 系数 $c_2$ )	$x_2$	$4$	$0$	$1$	$−15-\dfrac{1}{5}$	$25\dfrac{2}{5}$	$?$ ( $θ2\theta_2$ )
$σj\sigma_j$ ( 检验数 )			$0$	$0$	$?$ ( $σ3\sigma_3$ )	$?$ ( $σ4\sigma_4$ )

四、计算检验数、最优解判定

计算检验数 $σ\sigma$ :

$σ3=0−3×35−4×(−15)=−95+45=−1\sigma_3 = 0 - 3 \times \dfrac{3}{5} - 4 \times (-\dfrac{1}{5}) = -\dfrac{9}{5} + \dfrac{4}{5} = -1$

$σ4=0−3×(−15)−4×25=35−85=−1\sigma_4 = 0 - 3 \times (-\dfrac{1}{5}) - 4 \times \dfrac{2}{5} = \dfrac{3}{5} - \dfrac{8}{5} = -1$

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

五、最优解个数说明

1、唯一最优解

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

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

2、无穷最优解

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

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

假如计算检验数时 , 有一个非基变量的检验数小于 $0$ , 另外一个检验数等于 $0$ ;
假设目标函数是 $maxZ = b^0 + 0x_7 - 10x_8$ 形式的 , 一个系数为 $0$ , 一个系数为 $- 10$ ;
此时 $x_7$ 不论取何值 , 都是最优解 , 该线性规划就有无数个最优解 ;

3、无界解

无界解 :

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

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

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

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

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

4、总结

根据检验数判定 :

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

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

六、出基变量选择说明

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

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

《新程序员》：云原生和全面数字化实践50位技术专家共同创作，文字、视频、音频交互阅读

总结

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

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