【运筹学】线性规划 单纯形法 案例二 ( 案例解析 | 标准形转化 | 查找初始基可行解 | 最优解判定 | 查找入基变量与出基变量 | 第一次迭代 )
【运筹学】线性规划 单纯形法 案例二 ( 案例解析 | 标准形转化 | 查找初始基可行解 | 最优解判定 | 查找入基变量与出基变量 | 第一次迭代 )
文章目录
一、线性规划示例
线性规划示例 : 使用单纯形法求解下面的线性规划 ;
二、转化成标准形式
首先将现行规划转化成标准形式 :
参考 【运筹学】线性规划数学模型标准形式 ( 标准形式 | 目标函数转化 | 决策变量转化 | 约束方程转化 | 固定转化顺序 | 标准形式转化实例 ) 线性规划 普通形式 -> 标准形式 转化顺序说明 博客 , 先处理变量约束 , 再将不等式转为等式 , 最后更新目标函数 ;
1 . 处理约束变量 : 所有的约束变量都大于等于
, 这里无需处理 ;
2 . 将不等式转为等式 : 两个不等式都是小于等于不等式 , 在左侧加入松弛变量即可 ;
① 添加松弛变量 : 上述两个不等式
, 在左侧分别添加
松弛变量 ;
② 最终结果 : 转化后的结果是
3 . 处理目标函数取最大值 : 目标函数就是取最大值 , 无需处理 ;
4 . 最终的标准形结果是 :
三、初始基可行解
找初始基可行解 :
① 查找单位阵 : 该线性规划标准形的系数矩阵中 ,
的系数矩阵是
, 该矩阵是单位阵 ;
② 可行基 : 选择该矩阵作为可行基 ;
③ 初始基可行解 : 其对应的解是基可行解
;
四、列出单纯形表
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 | − 1 -1 −1 | 2 2 2 | 1 1 1 | 0 0 0 | − - − |
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 |
σ 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 |
基变量系数 (目标函数)基变量常数
( 目标函数
系数
)
( 目标函数
系数
)
( 检验数 )
(
)
(
)
(
)
五、计算检验数
计算非基变量的检验数 :
单个检验数计算公式 :
, 其中
是对应目标函数非基变量系数 ,
是目标函数中基变量系数 ,
是系数矩阵中对应的
非基变量列向量 ;
①
检验数计算 :
②
检验数计算 :
③
检验数计算 :
六、选择入基变量与出基变量
入基变量选择 : 选择检验数
较大的非基变量作为入基变量 , 即
;
出基变量是根据
值来选择的 , 选择
值较小的值对应的基变量作为出基变量 ;
出基变量选择 : 常数列
, 分别除以除以入基变量
大于
的系数列
, 计算过程如下
, 得出结果是
, 如果系数小于等于
, 该值就是无效值 , 默认为无穷大 , 不进行比较 , 选择
对应的基变量作为出基变量 , 查看该最小值对应的变量是
, 选择该
变量作为出基变量 ;
七、第一次迭代 : 列出单纯形表
上述已经得到
作为入基变量 , 由非基变量转为基变量 ,
作为出基变量 , 由基变量转为非基变量 ; 使用
, 替换基变量中的
的位置 ;
基变量为
, 注意顺序不要写反 ;
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 | − 1 -1 −1 | 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 | 15 15 15 | ? ? ? | 1 1 1 | ? ? ? | 1 1 1 | ? ? ? | ? ? ? ( θ 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 | ? ? ? | 0 0 0 | ? ? ? | 0 0 0 | ? ? ? | ? ? ? ( θ 2 \theta_2 θ2) |
σ j \sigma_j σj ( 检验数 ) | 1 1 1 ( σ 1 \sigma_1 σ1 ) | 0 0 0 | 1 1 1 ( σ 3 \sigma_3 σ3 ) | 0 0 0 | ? ? ? ( σ 2 \sigma_2 σ2 ) |
基变量系数 (目标函数)基变量常数
( 目标函数
系数
)
(
)
( 目标函数
系数
)
(
)
( 检验数 )
(
)
(
)
(
)
第一次迭代––––––––
( 目标函数
系数
)
(
)
( 目标函数
系数
)
(
)
( 检验数 )
(
)
(
)
(
)
腾讯云开发者
