【运筹学】线性规划 单纯形法 ( 案例解析 | 标准形转化 | 查找初始基可行解 | 最优解判定 | 查找入基变量与出基变量 | 迭代一 : 列出单纯形表) 后续博客 , 在上一篇博客中进行了 初始基可行解的检验数计算 , 最优解判定 , 入基变量与出基变量计算 , 并开始第一次迭代 ; 本篇博客中进行后续步骤解析 ;
当前的线性规划标准形式等式方程组 :
当前的单纯性表 :
c j c_j cj | c j c_j cj | | 1 1 1 | 2 2 2 | 1 1 1 | 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 | x 5 x_5 x5 | θ i \theta_i θi |
0 0 0 ( 目标函数 x 4 x_4 x4 系数 c 4 c_4 c4 ) | x 4 x_4 x4 | 15 15 15 | 2 2 2 | − 3 -3 −3 | 2 2 2 | 1 1 1 | 0 0 0 | − - − ( θ 4 \theta_4 θ4) |
0 0 0 ( 目标函数 x 5 x_5 x5 系数 c 5 c_5 c5) | x 5 x_5 x5 | 20 20 20 | 1 3 \dfrac{1}{3} 31 | 1 1 1 | 5 5 5 | 0 0 0 | 1 1 1 | 20 20 20 ( θ 5 \theta_5 θ5 ) |
σ j \sigma_j σj ( 检验数 ) | | | 1 1 1 ( σ 1 \sigma_1 σ1 ) | 2 2 2 ( σ 2 \sigma_2 σ2 ) | 1 1 1 ( σ 3 \sigma_3 σ3 ) | 0 0 0 | 0 0 0 | |
第一次迭代 | – | – | – | – | – | – | – | – |
0 0 0 ( 目标函数 x 4 x_4 x4 系数 c 4 c_4 c4 ) | x 4 x_4 x4 | ? ? ? | ? ? ? | ? ? ? | ? ? ? | ? ? ? | ? ? ? | ? ? ? ( θ 4 \theta_4 θ4 ) |
2 2 2 ( 目标函数 x 2 x_2 x2 系数 c 2 c_2 c2) | x 2 x_2 x2 | ? ? ? | ? ? ? | ? ? ? | ? ? ? | ? ? ? | ? ? ? | ? ? ? ( θ 2 \theta_2 θ2) |
σ j \sigma_j σj ( 检验数 ) | | | ? ? ? ( σ 1 \sigma_1 σ1 ) | 0 0 0 | ? ? ? ( σ 3 \sigma_3 σ3 ) | 0 0 0 | ? ? ? ( σ 2 \sigma_2 σ2 ) | |
基变量系数 (目标函数)基变量常数
( 目标函数
系数
)
(
)
( 目标函数
系数
)
(
)
( 检验数 )
(
)
(
)
(
)
第一次迭代––––––––
( 目标函数
系数
)
(
)
( 目标函数
系数
)
(
)
( 检验数 )
(
)
(
)
(
)
下面进行矩阵变换 :
中心元 : 在下面单纯形表中 ,
列 ( 红色选框 ) , 与
行 ( 绿色选框 ) , 上述 行列相交的部分 是 中心元 ,
以上述 中心元 为轴做变换 , 变换目的是把 中心元位置变换成
, 把中心元所在列的另一个位置变换成
;
该行中
的系数 , 就是
, 不用改变 , 因此这里将第二行的系数原封不动填入第一次迭代的单纯形表中 ;
接下来要将上图 蓝色选框 部分的位置 , 变为
, 变换过程如下 :
方程 等式左右两边乘以
;
相加 ;
新的单纯形表为 :
c j c_j cj | c j c_j cj | | 1 1 1 | 2 2 2 | 1 1 1 | 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 | x 5 x_5 x5 | θ i \theta_i θi |
0 0 0 ( 目标函数 x 4 x_4 x4 系数 c 4 c_4 c4 ) | x 4 x_4 x4 | 15 15 15 | 2 2 2 | − 3 -3 −3 | 2 2 2 | 1 1 1 | 0 0 0 | − - − ( θ 4 \theta_4 θ4) |
0 0 0 ( 目标函数 x 5 x_5 x5 系数 c 5 c_5 c5) | x 5 x_5 x5 | 20 20 20 | 1 3 \dfrac{1}{3} 31 | 1 1 1 | 5 5 5 | 0 0 0 | 1 1 1 | 20 20 20 ( θ 5 \theta_5 θ5 ) |
σ j \sigma_j σj ( 检验数 ) | | | 1 1 1 ( σ 1 \sigma_1 σ1 ) | 2 2 2 ( σ 2 \sigma_2 σ2 ) | 1 1 1 ( σ 3 \sigma_3 σ3 ) | 0 0 0 | 0 0 0 | |
第一次迭代 | – | – | – | – | – | – | – | – |
0 0 0 ( 目标函数 x 4 x_4 x4 系数 c 4 c_4 c4 ) | x 4 x_4 x4 | 75 75 75 | 3 3 3 | 0 0 0 | 17 17 17 | 1 1 1 | 3 3 3 | ? ? ? ( θ 4 \theta_4 θ4 ) |
2 2 2 ( 目标函数 x 2 x_2 x2 系数 c 2 c_2 c2) | x 2 x_2 x2 | 20 20 20 | 1 3 \dfrac{1}{3} 31 | 1 1 1 | 5 5 5 | 0 0 0 | 1 1 1 | ? ? ? ( θ 2 \theta_2 θ2) |
σ j \sigma_j σj ( 检验数 ) | | | ? ? ? ( σ 1 \sigma_1 σ1 ) | 0 0 0 | ? ? ? ( σ 3 \sigma_3 σ3 ) | 0 0 0 | ? ? ? ( σ 5 \sigma_5 σ5 ) | |
基变量系数 (目标函数)基变量常数
( 目标函数
系数
)
(
)
( 目标函数
系数
)
(
)
( 检验数 )
(
)
(
)
(
)
第一次迭代––––––––
( 目标函数
系数
)
(
)
( 目标函数
系数
)
(
)
( 检验数 )
(
)
(
)
(
)
1 . 计算非基变量
的检验数
:
2 . 计算非基变量
的检验数
:
3 . 计算非基变量
的检验数
:
新的单纯形表为 :
c j c_j cj | c j c_j cj | | 1 1 1 | 2 2 2 | 1 1 1 | 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 | x 5 x_5 x5 | θ i \theta_i θi |
0 0 0 ( 目标函数 x 4 x_4 x4 系数 c 4 c_4 c4 ) | x 4 x_4 x4 | 15 15 15 | 2 2 2 | − 3 -3 −3 | 2 2 2 | 1 1 1 | 0 0 0 | − - − ( θ 4 \theta_4 θ4) |
0 0 0 ( 目标函数 x 5 x_5 x5 系数 c 5 c_5 c5) | x 5 x_5 x5 | 20 20 20 | 1 3 \dfrac{1}{3} 31 | 1 1 1 | 5 5 5 | 0 0 0 | 1 1 1 | 20 20 20 ( θ 5 \theta_5 θ5 ) |
σ j \sigma_j σj ( 检验数 ) | | | 1 1 1 ( σ 1 \sigma_1 σ1 ) | 2 2 2 ( σ 2 \sigma_2 σ2 ) | 1 1 1 ( σ 3 \sigma_3 σ3 ) | 0 0 0 | 0 0 0 | |
第一次迭代 | – | – | – | – | – | – | – | – |
0 0 0 ( 目标函数 x 4 x_4 x4 系数 c 4 c_4 c4 ) | x 4 x_4 x4 | 75 75 75 | 3 3 3 | 0 0 0 | 17 17 17 | 1 1 1 | 3 3 3 | ? ? ? ( θ 4 \theta_4 θ4 ) |
2 2 2 ( 目标函数 x 2 x_2 x2 系数 c 2 c_2 c2) | x 2 x_2 x2 | 20 20 20 | 1 3 \dfrac{1}{3} 31 | 1 1 1 | 5 5 5 | 0 0 0 | 1 1 1 | ? ? ? ( θ 2 \theta_2 θ2) |
σ j \sigma_j σj ( 检验数 ) | | | 1 3 \dfrac{1}{3} 31 ( σ 1 \sigma_1 σ1 ) | 0 0 0 | − 9 -9 −9 ( σ 3 \sigma_3 σ3 ) | 0 0 0 | − 2 -2 −2 ( σ 5 \sigma_5 σ5 ) | |
基变量系数 (目标函数)基变量常数
( 目标函数
系数
)
(
)
( 目标函数
系数
)
(
)
( 检验数 )
(
)
(
)
(
)
第一次迭代––––––––
( 目标函数
系数
)
(
)
( 目标函数
系数
)
(
)
( 检验数 )
(
)
(
)
(
)
上述三个检验数 ,
, 其中
大于
, 只有当检验数都小于等于
时 , 该基可行解才是最优解 ; 该解不是最优解 ;
无穷多最优解 : 当有检验数等于
时 , 其它都小于
, 该线性规划有无穷多个最优解 ;
无界解 : 找不到出基变量 , 则该线性规划是无界解 ;
根据上述三个检验数
的值 , 选择检验数最大的非基变量作为入基变量 , 这里选择
;
出基变量选择 : 常数列
, 分别除以除以入基变量
大于
的系数列
, 计算过程如下
, 得出结果是
, 如果系数小于等于
, 该值就是无效值 , 默认为无穷大 , 不进行比较 , 选择
对应的基变量作为出基变量 , 查看该最小值对应的变量是
, 选择该
变量作为出基变量 ;
新的单纯形表为 :
c j c_j cj | c j c_j cj | | 1 1 1 | 2 2 2 | 1 1 1 | 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 | x 5 x_5 x5 | θ i \theta_i θi |
0 0 0 ( 目标函数 x 4 x_4 x4 系数 c 4 c_4 c4 ) | x 4 x_4 x4 | 15 15 15 | 2 2 2 | − 3 -3 −3 | 2 2 2 | 1 1 1 | 0 0 0 | − - − ( θ 4 \theta_4 θ4) |
0 0 0 ( 目标函数 x 5 x_5 x5 系数 c 5 c_5 c5) | x 5 x_5 x5 | 20 20 20 | 1 3 \dfrac{1}{3} 31 | 1 1 1 | 5 5 5 | 0 0 0 | 1 1 1 | 20 20 20 ( θ 5 \theta_5 θ5 ) |
σ j \sigma_j σj ( 检验数 ) | | | 1 1 1 ( σ 1 \sigma_1 σ1 ) | 2 2 2 ( σ 2 \sigma_2 σ2 ) | 1 1 1 ( σ 3 \sigma_3 σ3 ) | 0 0 0 | 0 0 0 | |
第一次迭代 | – | – | – | – | – | – | – | – |
0 0 0 ( 目标函数 x 4 x_4 x4 系数 c 4 c_4 c4 ) | x 4 x_4 x4 | 75 75 75 | 3 3 3 | 0 0 0 | 17 17 17 | 1 1 1 | 3 3 3 | 25 25 25 ( θ 4 \theta_4 θ4 ) |
2 2 2 ( 目标函数 x 2 x_2 x2 系数 c 2 c_2 c2) | x 2 x_2 x2 | 20 20 20 | 1 3 \dfrac{1}{3} 31 | 1 1 1 | 5 5 5 | 0 0 0 | 1 1 1 | 60 60 60 ( θ 2 \theta_2 θ2) |
σ j \sigma_j σj ( 检验数 ) | | | 1 3 \dfrac{1}{3} 31 ( σ 1 \sigma_1 σ1 ) | 0 0 0 | − 9 -9 −9 ( σ 3 \sigma_3 σ3 ) | 0 0 0 | − 2 -2 −2 ( σ 5 \sigma_5 σ5 ) | |
基变量系数 (目标函数)基变量常数
( 目标函数
系数
)
(
)
( 目标函数
系数
)
(
)
( 检验数 )
(
)
(
)
(
)
第一次迭代––––––––
( 目标函数
系数
)
(
)
( 目标函数
系数
)
(
)
( 检验数 )
(
)
(
)
(
)
下一篇博客 开始第二次迭代