上一篇博客 【运筹学】线性规划 人工变量法 ( 单纯形法总结 | 人工变量法引入 | 人工变量法原理分析 | 人工变量法案例 ) 中 , 介绍了人工变量法 , 主要用于解决线性规划标准形式中 , 初始系数矩阵中没有单位阵的情况 , 并给出一个案例 , 本篇博客中继续使用人工变量法解解上述线性规划问题 ;
添加
个人工变量后 , 得到 人工变量单纯形法 线性规划模型 :
其中的
是一个很大的数值 , 没有具体的值 , 可以理解为正无穷
, 具体使用单纯形法进行计算时 , 将其理解为大于给出的任意一个确定的数值 ;
生成初始基可行表 :
c j c_j cj | c j c_j cj | | 3 3 3 | 2 2 2 | − 1 -1 −1 | 0 0 0 | 0 0 0 | − M -M −M | − M -M −M | |
---|---|---|---|---|---|---|---|---|---|---|
C B C_B CB 基变量系数 (目标函数) | X B X_B XB 基变量 | 常数 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 | x 6 x_6 x6 | x 7 x_7 x7 | θ i \theta_i θi |
− M -M −M ( 目标函数 x 6 x_6 x6 系数 c 6 c_6 c6 ) | x 6 x_6 x6 | 4 4 4 | − 4 -4 −4 | 3 3 3 | 1 1 1 | − 1 -1 −1 | 0 0 0 | 1 1 1 | 0 0 0 | ? ? ? ( θ 6 \theta_6 θ6) |
0 0 0 ( 目标函数 x 5 x_5 x5 系数 c 5 c_5 c5) | x 5 x_5 x5 | 10 10 10 | 1 1 1 | − 1 -1 −1 | 2 2 2 | 0 0 0 | 1 1 1 | 0 0 0 | 0 0 0 | ? ? ? ( θ 5 \theta_5 θ5 ) |
− M -M −M ( 目标函数 x 7 x_7 x7 系数 c 7 c_7 c7) | x 7 x_7 x7 | 1 1 1 | 2 2 2 | − 2 -2 −2 | 1 1 1 | 0 0 0 | 0 0 0 | 0 0 0 | 1 1 1 | ? ? ? ( θ 7 \theta_7 θ7 ) |
σ j \sigma_j σj ( 检验数 ) | | | ? ? ? ( σ 1 \sigma_1 σ1 ) | ? ? ? ( σ 2 \sigma_2 σ2 ) | ? ? ? ( σ 3 \sigma_3 σ3 ) | ? ? ? ( σ 3 \sigma_3 σ3 ) | 0 0 0 | 0 0 0 | 0 0 0 | |
基变量系数 (目标函数)
基变量常数
( 目标函数
系数
)
(
)
( 目标函数
系数
)
(
)
( 目标函数
系数
)
(
)
( 检验数 )
(
)
(
)
(
)
(
)
注意基变量顺序 : 初始基可行解的单位阵的顺序 , 是
, 对应的基变量顺序是
系数是
系数是
系数是
1 . 计算非基变量
的检验数
:
其中
是正无穷
,
是负数 ;
2 . 计算非基变量
的检验数
:
其中
是正无穷
,
是正数 ;
3 . 计算非基变量
的检验数
:
其中
是正无穷
,
是正数 ;
4 . 计算非基变量
的检验数
:
其中
是正无穷
,
是负数 ;
根据上述四个检验数
的值 , 其中
检验数大于
, 该基可行解不是最优解 ;
只有当检验数都小于等于
时 , 该基可行解才是最优解 ;
根据上述四个检验数
的值 , 选择检验数最大的非基变量作为入基变量 ,
最大 , 这里选择
;
出基变量选择 : 常数列
, 分别除以除以入基变量
大于
的系数列
, 计算过程如下
, 得出结果是
, 如果系数小于等于
, 该值就是无效值 , 默认为无穷大 , 不进行比较 , 选择
对应的基变量作为出基变量 , 查看该最小值对应的变量是
, 选择该
变量作为出基变量 ;
c j c_j cj | c j c_j cj | | 3 3 3 | 2 2 2 | − 1 -1 −1 | 0 0 0 | 0 0 0 | − M -M −M | − M -M −M | |
---|---|---|---|---|---|---|---|---|---|---|
C B C_B CB 基变量系数 (目标函数) | X B X_B XB 基变量 | 常数 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 | x 6 x_6 x6 | x 7 x_7 x7 | θ i \theta_i θi |
− M -M −M ( 目标函数 x 6 x_6 x6 系数 c 6 c_6 c6 ) | x 6 x_6 x6 | 4 4 4 | − 4 -4 −4 | 3 3 3 | 1 1 1 | − 1 -1 −1 | 0 0 0 | 1 1 1 | 0 0 0 | 4 4 4 ( θ 6 \theta_6 θ6) |
0 0 0 ( 目标函数 x 5 x_5 x5 系数 c 5 c_5 c5) | x 5 x_5 x5 | 10 10 10 | 1 1 1 | − 1 -1 −1 | 2 2 2 | 0 0 0 | 1 1 1 | 0 0 0 | 0 0 0 | 5 5 5 ( θ 5 \theta_5 θ5 ) |
− M -M −M ( 目标函数 x 7 x_7 x7 系数 c 7 c_7 c7) | x 7 x_7 x7 | 1 1 1 | 2 2 2 | − 2 -2 −2 | 1 1 1 | 0 0 0 | 0 0 0 | 0 0 0 | 1 1 1 | 1 1 1 ( θ 7 \theta_7 θ7 ) |
σ j \sigma_j σj ( 检验数 ) | | | 3 − 2 M 3-2M 3−2M ( σ 1 \sigma_1 σ1 ) | 2 + M 2+M 2+M ( σ 2 \sigma_2 σ2 ) | − 1 + 2 M -1 + 2M −1+2M ( σ 3 \sigma_3 σ3 ) | − M -M −M ( σ 3 \sigma_3 σ3 ) | 0 0 0 | 0 0 0 | 0 0 0 | |
基变量系数 (目标函数)
基变量常数
( 目标函数
系数
)
(
)
( 目标函数
系数
)
(
)
( 目标函数
系数
)
(
)
( 检验数 )
(
)
(
)
(
)
(
)