一、运输规划基变量个数

上一篇博客 【运筹学】运输规划 ( 运输规划问题的数学模型 | 运输问题引入 ) 提出了运输规划问题 , 其约束方程系数矩阵的系数都是 $0,1$ , 该矩阵称为 稀疏矩阵 , 现在开始使用简化版的单纯形法解出最优解 ;

运输问题的线性规划如下 :

m i n W = 6 x 1 + 4 x 2 + 6 x 3 + 6 x 4 + 5 x 5 + 5 x 6 s . t { x 1 + x 2 + x 3 = 200 x 4 + x 5 + x 6 = 300 x 1 + x 4 = 150 x 2 + x 5 = 150 x 3 + x 6 = 200 x 1 , x 2 , x 3 , x 4 , x 5 , x 6 ≥ 0

上述运输问题的系数矩阵为 : $5$ 个约束方程对应的是 $5\times 6$ 矩阵 ;

( 1 1 1 0 0 0 0 0 0 1 1 1 1 0 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 1 )

运输问题是产销平衡的 , 约束方程中前两个相加之和是 $500$ , 后三个相加之和也是 $500$ , 说明这 $5$ 个方程中 , 肯定有一个是多余的 ;

给上述约束方程编号 : ① ~ ⑤ ;

m i n W = 6 x 1 + 4 x 2 + 6 x 3 + 6 x 4 + 5 x 5 + 5 x 6 s . t { x 1 + x 2 + x 3 = 200      ① x 4 + x 5 + x 6 = 300      ② x 1 + x 4 = 150      ③ x 2 + x 5 = 150      ④ x 3 + x 6 = 200      ⑤ x 1 , x 2 , x 3 , x 4 , x 5 , x 6 ≥ 0

① + ② - ③ - ④ = ⑤

① + ② - ③ - ⑤ = ④

① + ② - ④ - ⑤ = ③

① + ② 减去 ③ ④ ⑤ 中的任意两个 , 肯定等于第三个 ;

③ + ④ + ⑤ - ① = ②

③ + ④ + ⑤ - ② = ①

③ + ④ + ⑤ 减去 ① ② 中的任意一个 , 肯定等于另一个 ;

上述 $5$ 个方程 , 有一个是多余的 , 最多有 $4$ 个实际的方程 ;

这样可以得出以下定理 ;

二、运输规划问题数学模型基变量数定理

运输规划问题数学模型基变量数定理 :

假设有 $\mathrm{m}$ 个产地 , $\mathrm{n}$ 个销地 , 并且 产销平衡 , 其基变量数为 $\mathrm{m}+\mathrm{n}-1$ ;

$\mathrm{m}$ 个产地 , $\mathrm{n}$ 个销地 , 变量个数是 $\mathrm{m}\times \mathrm{n}$ 个 ;

$\mathrm{m}$ 个产地 , $\mathrm{n}$ 个销地 , 约束方程个数是 $\mathrm{m}+\mathrm{n}$ 个 , 这些约束方程中 , 有一个是多余的 , 最本质的方程最多有 $\mathrm{m}+\mathrm{n}-1$ 个 ;

任意删掉一个约束方程 , 就不再有多余的方程了 ;

确定约束方程个数后 , 就确定了基矩阵的秩 , 根据单纯形法的基本流程 , 第一步找初始基可行解 , 可行基就知道找什么样的可行基了 ;

单纯形法解线性规划最优解过程 :

① 基可行解 : 先找到一个 初始基可行解 ;

② 检验数 : 计算检验数 , 判定当前基可行解是否是 最优解 ;

③ 迭代 : 根据检验数确定 入基变量 , 根据入基变量系数计算 出基变量 , 然后进行 同解变换 , 生成新的单纯形表 , 继续计算检验数 ;

文章来源: hanshuliang.blog.csdn.net，作者：韩曙亮，版权归原作者所有，如需转载，请联系作者。

原文链接：hanshuliang.blog.csdn.net/article/details/112199919