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

编程问答

【运筹学】线性规划人工变量法 ( 人工变量法案例 | 第一次迭代 | 中心元变换 | 检验数计算 | 选择入基变量 | 选择出基变量 )

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

文章目录

一、第一次迭代 : 中心元变换
二、第一次迭代 : 单纯形表
三、第一次迭代 : 计算检验数
四、第一次迭代 : 最优解判定
五、第一次迭代 : 选择入基变量
六、第一次迭代 : 选择出基变量
七、第一次迭代 : 更新单纯形表

上一篇博客【运筹学】线性规划人工变量法 ( 人工变量法案例 | 初始单纯形表 | 检验数计算 | 入基变量 | 出基变量 ) 中 , 使用了人工变量法解没有单位阵的线性规划问题 , 通过添加人工变量 , 构造了单位阵 , 生成初始单纯形表 , 计算该单纯形表检验数 , 进行最优解判定 , 该初始基可行解不是最优解 , 先选择入基变量 , 然后根据入基变量选择出基变量 ; 本篇博客中开始进行第一次迭代计算 ;

一、第一次迭代 : 中心元变换

当前初始单纯形表 :

c_j

c_j

3

2

- 1

0

0

- M

- M

$C_B$ 基变量系数 (目标函数)	$X_B$ 基变量	常数 $b$	$x_1$	$x_2$	$x_3$	$x_4$	$x_5$	$x_6$	$x_7$	$θi\theta_i$
$- M$ ( 目标函数 $x_6$ 系数 $c_6$ )	$x_6$	$4$	$- 4$	$3$	$1$	$- 1$	$0$	$1$	$0$	$4$ ( $θ6\theta_6$ )
$0$ ( 目标函数 $x_5$ 系数 $c_5$ )	$x_5$	$10$	$1$	$- 1$	$2$	$0$	$1$	$0$	$0$	$5$ ( $θ5\theta_5$ )
$- M$ ( 目标函数 $x_7$ 系数 $c_7$ )	$x_7$	$1$	$2$	$- 2$	$1$	$0$	$0$	$0$	$1$	$1$ ( $θ7\theta_7$ )
$σj\sigma_j$ ( 检验数 )			$3 - 2 M$ ( $σ1\sigma_1$ )	$2 + M$ ( $σ2\sigma_2$ )	$- 1 + 2 M$ ( $σ3\sigma_3$ )	$- M$ ( $σ4\sigma_4$ )	$0$	$0$	$0$

中心元 : 入基变量为 $x_3$ , 出基变量为 $x_7$ , 在单纯形表中 , 入基变量与出基变量相交的位置 , 称为中心元 ;

中心元变换 : 以中心元为轴 , 作系数矩阵变换 ;

中心元位置变换成 $1$ ;
中心元对应入基变量所在列其它位置变换为 $0$ ;

当前约束方程组为 :

$s.t{−4x1+3x2+x3−x4+0x5+x6+0x7=4x1−x2+2x3+0x4+x5+0x6+0x7=102x1−2x2+x3+0x4+0x5+0x6+x7=1xj≥0(j=1,2,3,4,5,6,7)s.t\begin{cases} -4 x_1 + 3x_2 + x_3 - x_4 + 0x_5 + x_6 + 0x_7 = 4 \\\\ x_1 - x_2 + 2x_3 + 0x_4 + x_5 + 0x_6 + 0x_7 = 10 \\\\ 2x_1 - 2x_2 + x_3 + 0x_4 + 0x_5 + 0x_6 + x_7 = 1 \\\\ x_j \geq 0 \quad (j = 1 , 2 , 3, 4, 5 , 6 , 7 ) \end{cases}$

方程 $3$ 变换 : 在 $2x_1 - 2x_2 + x_3 + 0x_4 + 0x_5 + 0x_6 + x_7 = 1$ 中 , $x_3$ 的系数是中心元 , 其系数需要变换成 $1$ , 其本身就是 $1$ , 方程 $3$ 等式不用进行变换 ;

方程 $2$ 变换 : 将 $x_1 - x_2 + 2x_3 + 0x_4 + x_5 + 0x_6 + 0x_7 = 10$ 等式中 $x_3$ 的系数变为 $0$ , 将方程 $3$ 左右两端乘以 $- 2$ , 与方程 $2$ 相加 ;

$(2x1−2x2+x3+0x4+0x5+0x6+x7)×−2+(x1−x2+2x3+0x4+x5+0x6+0x7)=−2+10−3x1+3x2+0x3+0x4+x5+0x6−2x7=8\begin{array}{lcl} ( 2x_1 - 2x_2 + x_3 + 0x_4 + 0x_5 + 0x_6 + x_7 ) \times -2 + (x_1 - x_2 + 2x_3 + 0x_4 + x_5 + 0x_6 + 0x_7) = -2 + 10 \\\\ -3x_1 + 3x_2 + 0x_3 + 0x_4 + x_5 + 0x_6 - 2 x_7 = 8 \end{array}$

方程 $1$ 变换 : 将 $4 x_1 + 3x_2 + x_3 - x_4 + 0x_5 + x_6 + 0x_7 = 4$ 等式中 $x_3$ 的系数变为 $0$ , 将方程 $3$ 左右两端乘以 $- 1$ , 与方程 $1$ 相加 ;

$(2x1−2x2+x3+0x4+0x5+0x6+x7)×−1+(−4x1+3x2+x3−x4+0x5+x6+0x7)=−1+4−6x1+5x2+0x3−x4+0x5+x6−x7=3\begin{array}{lcl} ( 2x_1 - 2x_2 + x_3 + 0x_4 + 0x_5 + 0x_6 + x_7 ) \times -1 + (-4 x_1 + 3x_2 + x_3 - x_4 + 0x_5 + x_6 + 0x_7) = -1 + 4 \\\\ -6x_1 + 5x_2 + 0x_3 -x_4 + 0x_5 + x_6 - x_7 =3 \end{array}$

最终方程组为 :

$s.t{−6x1+5x2+0x3−x4+0x5+x6−x7=3−3x1+3x2+0x3+0x4+x5+0x6−2x7=82x1−2x2+x3+0x4+0x5+0x6+x7=1s.t\begin{cases} -6x_1 + 5x_2 + 0x_3 -x_4 + 0x_5 + x_6 - x_7 =3 \\\\ -3x_1 + 3x_2 + 0x_3 + 0x_4 + x_5 + 0x_6 - 2 x_7 = 8 \\\\ 2x_1 - 2x_2 + x_3 + 0x_4 + 0x_5 + 0x_6 + x_7 = 1 \end{cases}$

二、第一次迭代 : 单纯形表

$x_7$ 是后添加的人工变量 , 其取值肯定是 $0$ , 这里的单纯性表中 , 可以将 $x_7$ 彻底删除 , 不再使用 ;

c_j

c_j

3

2

- 1

0

0

- M

- M

$C_B$ 基变量系数 (目标函数)	$X_B$ 基变量	常数 $b$	$x_1$	$x_2$	$x_3$	$x_4$	$x_5$	$x_6$	$x_7$	$θi\theta_i$
$- M$ ( 目标函数 $x_6$ 系数 $c_6$ )	$x_6$	$4$	$- 4$	$3$	$1$	$- 1$	$0$	$1$	$0$	$4$ ( $θ6\theta_6$ )
$0$ ( 目标函数 $x_5$ 系数 $c_5$ )	$x_5$	$10$	$1$	$- 1$	$2$	$0$	$1$	$0$	$0$	$5$ ( $θ5\theta_5$ )
$- M$ ( 目标函数 $x_7$ 系数 $c_7$ )	$x_7$	$1$	$2$	$- 2$	$1$	$0$	$0$	$0$	$1$	$1$ ( $θ7\theta_7$ )
$σj\sigma_j$ ( 检验数 )			$3 - 2 M$ ( $σ1\sigma_1$ )	$2 + M$ ( $σ2\sigma_2$ )	$- 1 + 2 M$ ( $σ4\sigma_4$ )	$- M$ ( $σ3\sigma_3$ )	$0$	$0$	$0$
第二次迭代	–	–	–	–	–	–	–	–	–	–
$- M$ ( 目标函数 $x_6$ 系数 $c_6$ )	$x_6$	$3$	$- 6$	$5$	$0$	$- 1$	$0$	$1$	移除	$?$ ( $θ6\theta_6$ )
$0$ ( 目标函数 $x_5$ 系数 $c_5$ )	$x_5$	$8$	$- 3$	$3$	$0$	$0$	$1$	$0$	移除	$?$ ( $θ5\theta_5$ )
$- 1$ ( 目标函数 $x_3$ 系数 $c_3$ )	$x_3$	$1$	$2$	$- 2$	$1$	$0$	$0$	$0$	移除	$?$ ( $θ3\theta_3$ )
$σj\sigma_j$ ( 检验数 )			$?$ ( $σ1\sigma_1$ )	$?$ ( $σ2\sigma_2$ )	$0$	$?$ ( $σ4\sigma_4$ )	$0$	$0$	移除

三、第一次迭代 : 计算检验数

1 . 计算非基变量 $x_1$ 的检验数 $σ1\sigma_1$ :

$σ1=3−(−M0−1)×(−6−32)=3−(−M×−6+0×−3+−1×2)=5−6M\sigma_1 = 3 - \begin{pmatrix} \quad -M \quad 0 \quad -1 \quad \\ \end{pmatrix} \times \begin{pmatrix} \quad -6 \quad \\\\ \quad -3 \quad \\\\ \quad 2 \quad \end{pmatrix} = 3- ( -M \times -6 + 0 \times -3 + -1 \times 2) =5 - 6M$

其中 $M$ 是正无穷 $+∞+\infin$ , $5 - 6 M$ 是负数 ;

2 . 计算非基变量 $x_2$ 的检验数 $σ2\sigma_2$ :

$σ2=2−(−M0−1)×(53−2)=2−(−M×5+0×3+−1×−2)=5M\sigma_2 = 2 - \begin{pmatrix} \quad -M \quad 0 \quad -1 \quad \\ \end{pmatrix} \times \begin{pmatrix} \quad 5 \quad \\\\ \quad 3 \quad \\\\ \quad -2 \quad \end{pmatrix} = 2- ( -M \times 5 + 0 \times 3 + -1 \times -2) =5M$

其中 $M$ 是正无穷 $+∞+\infin$ , $5 M$ 是正数 ;

3 . 计算非基变量 $x_4$ 的检验数 $σ4\sigma_4$ :

$σ4=0−(−M0−1)×(−100)=0−(−M×−1+0×0+−1×0)=−M\sigma_4 = 0 - \begin{pmatrix} \quad -M \quad 0 \quad -1 \quad \\ \end{pmatrix} \times \begin{pmatrix} \quad -1 \quad \\\\ \quad 0 \quad \\\\ \quad 0 \quad \end{pmatrix} = 0- ( -M \times -1 + 0 \times 0 + -1 \times 0 ) = -M$

其中 $M$ 是正无穷 $+∞+\infin$ , $- M$ 是负数 ;

四、第一次迭代 : 最优解判定

根据上述三个检验数 ${σ1=5−6M(负数)σ2=5M(正数)σ4=−M(负数)\begin{cases} \sigma_1 = 5 - 6M \quad ( 负数 )\\\\ \sigma_2= 5M \quad ( 正数 )\\\\ \sigma_4 = -M \quad ( 负数 ) \end{cases}$ 的值 , 其中 $σ2\sigma_2$ 检验数大于 $0$ , 该基可行解不是最优解 ;

只有当检验数都小于等于 $0$ 时 , 该基可行解才是最优解 ;

五、第一次迭代 : 选择入基变量

根据上述三个检验数 ${σ1=5−6M(负数)σ2=5M(正数)σ4=−M(负数)\begin{cases} \sigma_1 = 5 - 6M \quad ( 负数 )\\\\ \sigma_2= 5M \quad ( 正数 )\\\\ \sigma_4 = -M \quad ( 负数 ) \end{cases}$ 的值 , 选择检验数最大的非基变量作为入基变量 , $σ2=5M\sigma_2= 5M$ 最大 , 这里选择 $x_2$ 作为入基变量 ;

六、第一次迭代 : 选择出基变量

出基变量选择 : 常数列 $=\begin{pmatrix} \quad 3 \quad \\ \quad 8 \quad \\ \quad 1 \quad \\ \end{pmatrix}$ , 分别除以除以入基变量 $x_2$ 大于 $0$ 的系数列 $(53−2)\begin{pmatrix} \quad 5 \quad \\\\ \quad 3 \quad \\\\ \quad -2 \quad \end{pmatrix}$ , 计算过程如下 $(3583系数不符合要求)\begin{pmatrix} \quad \cfrac{3}{5} \quad \\\\ \quad \cfrac{8}{3} \quad \\\\ \quad 系数不符合要求 \quad \end{pmatrix}$ , 得出结果是 $(3583−)\begin{pmatrix} \quad \cfrac{3}{5} \quad \\\\ \quad \cfrac{8}{3} \quad \\\\ \quad - \quad \end{pmatrix}$ , 如果系数小于等于 $0$ , 该值就是无效值 , 默认为无穷大 , 不进行比较 , 选择 $35\cfrac{3}{5}$ 对应的基变量作为出基变量 , 查看该最小值对应的变量是 $x_6$ , 选择该 $x_6$ 变量作为出基变量 ;

七、第一次迭代 : 更新单纯形表