【运筹学】线性规划 单纯形法 阶段总结 ( 初始基可行解 | 判定最优解 | 迭代 | 得到最优解 | 全流程详细解析 ) ★
文章目录
一、线性规划示例二、转化标准形式三、查找初始基可行解四、初始基可行解的最优解判定五、第一次迭代 : 入基与出基变量选择六、第一次迭代 : 方程组同解变换七、第一次迭代 : 生成新的单纯形表八、第一次迭代 : 解出基可行解九、第一次迭代 : 计算检验数
σ
j
\sigma_j
σj 判定最优解 并选择入基变量十、第一次迭代 : 根据入基变量计算并选择出基变量十一、第二次迭代 : 方程组同解变换十二、第二次迭代 : 生成新的单纯形表十三、第二次迭代 : 计算检验数、最优解判定
单纯形法 参考博客 :
1 . 查找初始基可行解 :
【运筹学】线性规划数学模型 ( 单纯形法原理 | 单纯形法流程 | 查找初始基可行解 )
2 . 最优解判定 :
【运筹学】线性规划数学模型 ( 单纯形法 | 最优解判定原则 | 可行解表示 | 目标函数推导 | 目标函数最大值分析 )【运筹学】线性规划数学模型 ( 单纯形法 | 最优解判定原则 | 单纯形表 | 系数计算方法 | 根据系数是否小于等于 0 判定最优解 )【运筹学】线性规划数学模型 ( 单纯形法 | 最优解判定原则 | 线性规划求解示例 )
3 . 迭代原则 :
【运筹学】线性规划数学模型 ( 单纯形法 | 迭代原则 | 入基 | 出基 | 线性规划求解示例 )【运筹学】线性规划数学模型 ( 单纯形法 | 第一次迭代 | 方程组同解变换 | 计算新单纯形表 | 计算检验数 | 入基变量选择 | 出基变量选择 )【运筹学】线性规划数学模型 ( 单纯形法 | 第二次迭代 | 方程组同解变换 | 生成新单纯形表 | 计算检验数 | 最优解判定 | 线性规划解个数分析 )
4 . 单纯形法阶段总结 :
【运筹学】线性规划 单纯形法 阶段总结 ( 初始基可行解 | 判定最优解 | 迭代 | 得到最优解 | 全流程详细解析 ) ★ 推荐
一、线性规划示例
使用单纯形法求解线性规划最优解 :
m
a
x
Z
=
3
x
1
+
4
x
2
{
2
x
1
+
x
2
≤
40
x
1
+
3
x
2
≤
30
x
j
≥
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 的 , 符合线性规划标准形式要求 ;
② 不等式转换 : 两个等式都是 小于等于不等式 , 需要 在不等式左侧加入松弛变量 , 将其转为等式 ;
2
x
1
+
x
2
≤
40
2 x_1 + x_2 \leq 40
2x1+x2≤40 , 左侧加入松弛变量
x
3
x_3
x3 , 变为
2
x
1
+
x
2
+
x
3
=
40
2 x_1 + x_2 + x_3 = 40
2x1+x2+x3=40
x
1
+
3
x
2
≤
30
x_1 + 3x_2 \leq 30
x1+3x2≤30 , 左侧加入松弛变量
x
4
x_4
x4 , 变为
x
1
+
3
x
2
+
x
4
=
30
x_1 + 3x_2 + x_4 = 30
x1+3x2+x4=30
③ 更新目标函数 : 将
x
3
x_3
x3 和
x
4
x_4
x4 加入到目标函数中 , 得到新的目标函数
m
a
x
Z
=
3
x
1
+
4
x
2
+
0
x
3
+
0
x
4
max Z = 3x_1 + 4x_2 + 0x_3 + 0x_4
maxZ=3x1+4x2+0x3+0x4 ;
此时线性规划标准形式为 :
m
a
x
Z
=
3
x
1
+
4
x
2
+
0
x
3
+
0
x
4
{
2
x
1
+
x
2
+
x
3
+
0
x
4
=
40
x
1
+
3
x
2
+
0
x
3
+
x
4
=
30
x
j
≥
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)
三、查找初始基可行解
找基矩阵 :
上述线性规划标准形式的系数矩阵为
[
2
1
1
0
1
3
0
1
]
\begin{bmatrix} &2 & 1 & 1 & 0 & \\\\ & 1 & 3 & 0 & 1 & \end{bmatrix}
⎣⎡21131001⎦⎤ , 其中子矩阵中有
[
1
0
0
1
]
\begin{bmatrix} & 1 & 0 & \\\\ & 0 & 1 & \end{bmatrix}
⎣⎡1001⎦⎤ 单位阵
I
I
I ;
使用该单位阵
I
I
I 作为基矩阵 , 单位阵肯定是可逆的 , 其对应的基解 , 解出后的值就是右侧的常数值 , 肯定大于等于
0
0
0 , 是基可行解 ;
列出单纯形表 :
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
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
σ
j
\sigma_j
σj
3
3
3
4
4
4
0
0
0
0
0
0
基变量是
x
3
x_3
x3 和
x
4
x_4
x4 , 基变量在约束条件中的系数矩阵
[
1
0
0
1
]
\begin{bmatrix} &1 & 0 & \\\\ &0 & 1 & \end{bmatrix}
⎣⎡1001⎦⎤ 就是基矩阵 , 这是个单位阵 ;
基变量是
x
3
x_3
x3 和
x
4
x_4
x4 在目标函数中的系数是
(
0
0
)
\begin{pmatrix} \quad 0 \quad 0 \quad \end{pmatrix}
(00) ;
此时的基解是
(
0
0
40
30
)
\begin{pmatrix} \quad 0 \quad \\ \quad 0 \quad \\ \quad 40 \quad \\ \quad 30 \quad \\ \end{pmatrix}
⎝⎜⎜⎛004030⎠⎟⎟⎞ , 该解是初始解 , 下面判定该解是否是最优解 ;
四、初始基可行解的最优解判定
使用 检验数矩阵
(
C
N
T
−
C
B
T
B
−
1
N
)
( C_N^T - C_B^T B^{-1}N )
(CNT−CBTB−1N) 判断上述解 , 是否是最优解 , 该矩阵计算结果中所有的数 , 都是检验数
σ
\sigma
σ , 如果 所有的数都小于等于
0
0
0 , 说明该解就是最优解 ;
这里只求非基变量的检验数 , 即
x
1
x_1
x1 ,
x
2
x_2
x2 的检验数 ;
列出目标函数非基变量系数
(
C
N
T
−
C
B
T
B
−
1
N
)
( C_N^T - C_B^T B^{-1}N )
(CNT−CBTB−1N) 矩阵 :
非基变量在目标函数中的系数矩阵 :
C
N
T
=
(
3
4
)
C_N^T=\begin{pmatrix} \quad 3 \quad 4 \quad \end{pmatrix}
CNT=(34)
基变量在目标函数中的叙述矩阵 :
C
B
T
=
(
0
0
)
C_B^T = \begin{pmatrix} \quad 0 \quad 0 \quad \end{pmatrix}
CBT=(00)
B
−
1
N
B^{-1}N
B−1N 是系数矩阵中经过矩阵变换后 , 基变量系数是单位阵
I
I
I , 非基变量系数是
B
−
1
N
B^{-1}N
B−1N :
B
−
1
N
=
[
2
1
1
3
]
B^{-1}N =\begin{bmatrix} &2 & 1 & \\\\ &1 & 3 & \end{bmatrix}
B−1N=⎣⎡2113⎦⎤
(
C
N
T
−
C
B
T
B
−
1
N
)
=
C
N
T
=
(
3
4
)
−
(
0
0
)
×
[
2
1
1
3
]
( 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−CBTB−1N)=CNT=(34)−(00)×⎣⎡2113⎦⎤
=
(
σ
1
σ
2
)
= \begin{pmatrix} \quad \sigma_{1} \quad \sigma_{2} \quad \end{pmatrix}
=(σ1σ2)
其中
σ
1
\sigma_{1}
σ1 是目标函数中
x
1
x_1
x1 的系数 ,
σ
2
\sigma_{2}
σ2 是目标函数中的
x
2
x_2
x2 的系数 ;
如果上述两个系数都小于等于
0
0
0 , 那么当 非基变量
X
N
=
(
x
1
x
2
)
X_N =\begin{pmatrix} x_{1} \\ x_{2} \end{pmatrix}
XN=(x1x2) 取值为
0
0
0 时 , 目标函数取值最大 ;
系数的计算公式为 :
σ
j
=
c
j
−
∑
c
i
a
i
j
\sigma_j = c_j - \sum c_i a_{ij}
σj=cj−∑ciaij , 其中
c
j
c_j
cj 对应的是非基变量在目标函数系数 ,
c
i
c_i
ci 是基变量在目标函数中的系数 ,
a
i
j
a_{ij}
aij 是
B
−
1
N
B^{-1}N
B−1N 中的矩阵向量 , 代表一列 ;
σ
1
=
c
1
−
(
c
3
a
11
+
c
4
a
12
)
\sigma_{1} = c_1 - ( c_3 a_{11} + c_4 a_{12} )
σ1=c1−(c3a11+c4a12)
σ
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
=
c
2
−
(
c
3
a
21
+
c
4
a
22
)
\sigma_{2} = c_2 - ( c_3 a_{21} + c_4 a_{22} )
σ2=c2−(c3a21+c4a22)
σ
2
=
4
−
(
0
×
1
)
−
(
0
×
3
)
=
4
\sigma_{2} =4 - (0 \times 1) - (0 \times 3) = 4
σ2=4−(0×1)−(0×3)=4 , 是从下面的单纯形表中的如下位置提取的数值 ;
如果这两个系数 , 如果都小于等于
0
0
0 , 该 基可行解
(
0
0
40
30
)
\begin{pmatrix} \quad 0 \quad \\ \quad 0 \quad \\ \quad 40 \quad \\ \quad 30 \quad \\ \end{pmatrix}
⎝⎜⎜⎛004030⎠⎟⎟⎞ 才是最优解 , 这两个系数都大于
0
0
0 , 因此不是最优解 ;
五、第一次迭代 : 入基与出基变量选择
入基变量选择 : 具体哪个变量入基 , 是由检验数决定的 , 检验数
σ
j
\sigma_j
σj 较大的入基 ;
x
2
x_2
x2 的检验数
σ
2
\sigma_2
σ2 是
4
4
4 , 大于
σ
1
=
3
\sigma_1 = 3
σ1=3 , 因此这里选择
x
2
x_2
x2 作为入基变量 ;
出基变量选择 : 系数矩阵中 , 常数列
b
=
(
40
30
)
b =\begin{pmatrix} \quad 40 \quad \\ \quad 30 \quad \end{pmatrix}
b=(4030) , 分别除以除以入基变量大于
0
0
0 的系数列
(
1
3
)
\begin{pmatrix} \quad 1 \quad \\ \quad 3 \quad \end{pmatrix}
(13) , 得出结果是
(
40
10
)
\begin{pmatrix} \quad 40 \quad \\ \quad 10 \quad \end{pmatrix}
(4010) , 然后选择一个最小值
10
10
10 , 查看该最小值对应的变量是
x
4
x_4
x4 , 选择该变量作为出基变量 ;
这里将出基变量与入基变量选择好了 ,
x
2
x_2
x2 的检验数较大 , 选择
x
2
x_2
x2 作为入基变量 ,
x
4
x_4
x4 的
θ
4
\theta_4
θ4 较小 , 选择
x
4
x_4
x4 作为出基变量 ;
入基出基操作完成后 , 基变量变成了
x
3
,
x
2
x_3, x_2
x3,x2 ;
六、第一次迭代 : 方程组同解变换
方程组做同解变换 :
线性规划原始方程组为
{
2
x
1
+
x
2
+
x
3
+
0
x
4
=
40
x
1
+
3
x
2
+
0
x
3
+
x
4
=
30
\begin{cases} 2 x_1 + x_2 + x_3 + 0x_4 = 40 \\\\ x_1 + 3x_2 + 0x_3 + x_4 = 30 \end{cases}
⎩⎪⎨⎪⎧2x1+x2+x3+0x4=40x1+3x2+0x3+x4=30 , 需要将
x
2
x_2
x2 的系数变为
(
0
1
)
\begin{pmatrix} \quad 0 \quad \\ \quad 1 \quad \end{pmatrix}
(01) ,
x
3
x_3
x3 的系数保持
(
1
0
)
\begin{pmatrix} \quad 1 \quad \\ \quad 0 \quad \end{pmatrix}
(10) 不变 ;
方程
2
2
2 同解变换 : 在
x
1
+
3
x
2
+
0
x
3
+
x
4
=
30
x_1 + 3x_2 + 0x_3 + x_4 = 30
x1+3x2+0x3+x4=30 中 , 需要将
x
2
x_2
x2 的系数变成
1
1
1 , 在方程两端乘以
1
3
\dfrac{1}{3}
31 , 此时方程变成
1
3
x
1
+
x
2
+
0
x
3
+
1
3
x
4
=
10
\dfrac{1}{3}x_1 + x_2 + 0x_3 + \dfrac{1}{3}x_4 = 10
31x1+x2+0x3+31x4=10 ;
方程
1
1
1 同解变换 : 将上述方程
2
2
2 作同解变换后 , 方程组变成
{
2
x
1
+
x
2
+
x
3
+
0
x
4
=
40
1
3
x
1
+
x
2
+
0
x
3
+
1
3
x
4
=
10
\begin{cases} 2 x_1 + x_2 + x_3 + 0x_4 = 40 \\\\ \dfrac{1}{3}x_1 + x_2 + 0x_3 + \dfrac{1}{3}x_4 = 10 \end{cases}
⎩⎪⎪⎨⎪⎪⎧2x1+x2+x3+0x4=4031x1+x2+0x3+31x4=10 , 目前的需求是将方程
1
1
1 的
x
2
x_2
x2 系数变为
0
0
0 , 使用方程
1
1
1 减去 方程
2
2
2 即可得到要求的矩阵 :
(
2
−
1
3
)
x
1
+
0
x
2
+
x
3
+
(
0
−
1
3
)
x
4
=
40
−
10
5
3
x
1
+
0
x
2
+
x
3
−
1
3
x
4
=
30
\begin{array}{lcl} (2 - \dfrac{1}{3}) x_1 + 0 x_2 + x_3 + (0 - \dfrac{1}{3}) x_4 &=& 40 - 10 \\\\ \dfrac{5}{3} x_1 + 0x_2 + x_3 - \dfrac{1}{3} x_4 &=& 30 \end{array}
(2−31)x1+0x2+x3+(0−31)x435x1+0x2+x3−31x4==40−1030
最终方程
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
35x1+0x2+x3−31x4=30 ;
同解变换完成后的方程组为
{
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}
⎩⎪⎪⎪⎨⎪⎪⎪⎧35x1+0x2+x3−31x4=3031x1+x2+0x3+31x4=10
七、第一次迭代 : 生成新的单纯形表
单纯形表变成如下形式 : 下面的单纯形表中 , 上面部分是初始基可行解对应的单纯形表 , 下面的部分是本次迭代后生成的新的单纯形表 ;
将同解变换后的方程组中的 系数矩阵 , 和 常数 , 填入新的单纯形表中 ;
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
?
?
? (
θ
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
?
?
? (
θ
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 )
八、第一次迭代 : 解出基可行解
新的 基变量是
x
3
,
x
2
x_3 , x_2
x3,x2 , 对应的基矩阵是
(
1
0
0
1
)
\begin{pmatrix} \quad 1 \quad 0 \quad \\ \quad 0 \quad 1 \quad \end{pmatrix}
(1001) , 非基变量是
x
1
,
x
4
x_1, x_4
x1,x4 , 对应的非基矩阵是
(
5
3
−
1
3
1
3
1
3
)
\begin{pmatrix} \quad \dfrac{5}{3} \quad -\dfrac{1}{3} \quad \\ \quad \dfrac{1}{3} \quad \dfrac{1}{3} \quad \end{pmatrix}
⎝⎜⎛35−313131⎠⎟⎞ , 将非基变量设置为
0
0
0 , 方程组为
{
5
3
×
0
+
0
x
2
+
x
3
−
1
3
×
0
=
30
1
3
×
0
+
x
2
+
0
x
3
+
1
3
×
0
=
10
\begin{cases} \dfrac{5}{3} \times 0 + 0x_2 + x_3 - \dfrac{1}{3} \times 0 = 30 \\\\ \dfrac{1}{3} \times 0 + x_2 + 0x_3 + \dfrac{1}{3} \times 0 = 10 \end{cases}
⎩⎪⎪⎪⎨⎪⎪⎪⎧35×0+0x2+x3−31×0=3031×0+x2+0x3+31×0=10 , 解出基变量为
{
x
3
=
30
x
2
=
10
\begin{cases} x_3 = 30 \\\\ x_2 = 10 \end{cases}
⎩⎪⎨⎪⎧x3=30x2=10 , 基可行解 为
(
0
10
30
0
)
\begin{pmatrix} \quad 0 \quad \\ \quad 10 \quad \\ \quad 30 \quad \\ \quad 0 \quad \end{pmatrix}
⎝⎜⎜⎛010300⎠⎟⎟⎞
九、第一次迭代 : 计算检验数
σ
j
\sigma_j
σj 判定最优解 并选择入基变量
根据 【运筹学】线性规划数学模型 ( 单纯形法 | 最优解判定原则 | 单纯形表 | 系数计算方法 | 根据系数是否小于等于 0 判定最优解 ) 博客中分析 , 检验数计算公式为 :
矩阵形式 :
C
N
T
−
C
B
T
B
−
1
N
C_N^T - C_B^T B^{-1}N
CNT−CBTB−1N单个检验数计算公式 :
σ
j
=
c
j
−
∑
c
i
a
i
j
\sigma_j = c_j - \sum c_i a_{ij}
σj=cj−∑ciaij
基变量的检验数是
0
0
0 , 主要是求非基变量的检验数
σ
1
,
σ
4
\sigma_1 , \sigma_4
σ1,σ4 ;
σ
1
=
c
1
−
(
c
3
a
11
+
c
2
a
12
)
\sigma_{1} = c_1 - ( c_3 a_{11} + c_2 a_{12} )
σ1=c1−(c3a11+c2a12)
σ
1
=
3
−
(
0
×
5
3
)
−
(
4
×
1
3
)
=
5
3
\sigma_{1} =3 - (0 \times \dfrac{5}{3}) - (4 \times \dfrac{1}{3}) = \dfrac{5}{3}
σ1=3−(0×35)−(4×31)=35 , 是从下面的单纯形表中的如下位置提取的数值 ;
σ
4
=
c
4
−
(
c
3
a
41
+
c
2
a
42
)
\sigma_{4} = c_4 - ( c_3 a_{41} + c_2 a_{42} )
σ4=c4−(c3a41+c2a42)
σ
4
=
0
−
(
0
×
−
1
3
)
−
(
4
×
1
3
)
=
−
4
3
\sigma_{4} =0 - (0 \times -\dfrac{1}{3}) - (4 \times \dfrac{1}{3}) = -\dfrac{4}{3}
σ4=0−(0×−31)−(4×31)=−34 , 是从下面的单纯形表中的如下位置提取的数值 ;
检验数
{
σ
1
=
3
−
(
0
×
5
3
)
−
(
4
×
1
3
)
=
5
3
σ
4
=
0
−
(
0
×
−
1
3
)
−
(
4
×
1
3
)
=
−
4
3
\begin{cases} \sigma_{1} =3 - (0 \times \dfrac{5}{3}) - (4 \times \dfrac{1}{3}) = \dfrac{5}{3} \\\\ \sigma_{4} =0 - (0 \times -\dfrac{1}{3}) - (4 \times \dfrac{1}{3}) = -\dfrac{4}{3} \end{cases}
⎩⎪⎪⎪⎨⎪⎪⎪⎧σ1=3−(0×35)−(4×31)=35σ4=0−(0×−31)−(4×31)=−34 ,
σ
1
\sigma_1
σ1 是大于
0
0
0 的 , 两个检验数必须都小于等于
0
0
0 , 该基可行解才算作是最优解 , 因此 该基可行解不是最优解 ;
根据检验数选择入基变量 : 继续迭代 , 选择检验数较大的非基变量 , 作为入基变量 , 这里入基变量是
x
1
x_1
x1 ;
十、第一次迭代 : 根据入基变量计算并选择出基变量
参考博客 【运筹学】线性规划数学模型 ( 单纯形法 | 迭代原则 | 入基 | 出基 | 线性规划求解示例 ) 五、出基与入基变量选择
入基变量 根据检验数
σ
\sigma
σ 选择的是
x
1
x_1
x1 ;
出基变量是根据
θ
\theta
θ 值来选择的 , 选择
θ
\theta
θ 值较小的值对应的基变量作为出基变量 ;
θ
\theta
θ 值计算 : 常数列
b
=
(
30
10
)
b =\begin{pmatrix} \quad 30 \quad \\ \quad 10 \quad \end{pmatrix}
b=(3010) , 分别除以除以入基变量
x
1
x_1
x1 大于
0
0
0 的系数列
(
5
3
1
3
)
\begin{pmatrix} \quad \dfrac{5}{3} \quad \\\\ \quad \dfrac{1}{3} \quad \end{pmatrix}
⎝⎜⎜⎛3531⎠⎟⎟⎞ , 计算过程如下
(
30
5
3
10
1
3
)
\begin{pmatrix} \quad \cfrac{30}{\dfrac{5}{3}} \quad \\\\ \quad \cfrac{10}{\dfrac{1}{3}} \quad \end{pmatrix}
⎝⎜⎜⎜⎜⎜⎜⎜⎛35303110⎠⎟⎟⎟⎟⎟⎟⎟⎞ , 得出结果是
(
18
30
)
\begin{pmatrix} \quad 18 \quad \\\\ \quad 30 \quad \end{pmatrix}
⎝⎛1830⎠⎞ , 然后选择一个最小值
18
18
18 , 查看该最小值对应的变量是
x
3
x_3
x3 , 选择该变量作为出基变量 ;
x
1
x_1
x1 作入基变量 ,
x
3
x_3
x3 作出基变量 ; 使用
x
1
x_1
x1 替代基变量中
x
3
x_3
x3 的位置 ;
迭代后的基变量为
x
1
,
x
2
x_1 ,x_2
x1,x2 ;
更新一下单纯形表 :
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 )
十一、第二次迭代 : 方程组同解变换
当前的方程组为
{
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}
⎩⎪⎪⎪⎨⎪⎪⎪⎧35x1+0x2+x3−31x4=3031x1+x2+0x3+31x4=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}
⎝⎜⎜⎛350311⎠⎟⎟⎞ , 进行同解变换 , 将基矩阵转为单位阵 ;
方程
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
35x1+0x2+x3−31x4=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}
35x1+0x2+x3−31x4(35x1+0x2+x3−31x4)×53x1+0x2+53x3−51x4===3030×5318
当前方程组变成
{
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+53x3−51x4=1831x1+x2+0x3+31x4=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+53x3−51x4)×−31−31x1+0x2+−51x3+151x4==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}
(−31x1+0x2+−51x3+151x4)+(31x1+x2+0x3+31x4)0x1+x2−51x3+52x4==−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+53x3−51x4=180x1+x2−51x3+156x4=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⎠⎟⎟⎞是最优解 ;
Copyright © 2022 日本世界杯_林高远世界杯 - edenyn.com All Rights Reserved.