【运筹学】运输规划 ( 运输规划基变量个数分析 )

文章目录

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

一、运输规划基变量个数

上一篇博客【运筹学】运输规划 ( 运输规划问题的数学模型 | 运输问题引入 ) 提出了运输规划问题 , 其约束方程系数矩阵的系数都是

0,1

, 该矩阵称为稀疏矩阵 , 现在开始使用简化版的单纯形法解出最优解 ;

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

begin{array}{lcl} rm minW = 6x_1 4x_2 6x_3 6x_4 5x_5 5x_6 \\ rm s.tbegin{cases} rm x_1 x_2 x_3 = 200 \\ rm x_4 x_5 x_6 = 300 \\ rm x_1 x_4 = 150 \\ rm x_2 x_5= 150 \\ rm x_3 x_6= 200 \\ rm x_1, x_2, x_3 , x_4 , x_5 , x_6 geq 0 end{cases}end{array}

上述运输问题的系数矩阵为 :

个约束方程对应的是

rm 5 times 6

矩阵 ;

begin{pmatrix} quad 1 quad 1 quad 1 quad 0 quad 0 quad 0 quad \\ quad 0 quad 0 quad 0 quad 1 quad 1 quad 1 quad \\ quad 1 quad 0 quad 0 quad 1 quad 0 quad 0 quad \\ quad 0 quad 1 quad 0 quad 0 quad 1 quad 0 quad \\ quad 0 quad 0 quad 1 quad 0 quad 0 quad 1 quad end{pmatrix}

运输问题是产销平衡的 , 约束方程中前两个相加之和是

500

, 后三个相加之和也是

500

, 说明这

个方程中 , 肯定有一个是多余的 ;

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

begin{array}{lcl} rm minW = 6x_1 4x_2 6x_3 6x_4 5x_5 5x_6 \\ rm s.tbegin{cases} rm x_1 x_2 x_3 = 200 ① \\ rm x_4 x_5 x_6 = 300 ② \\ rm x_1 x_4 = 150 ③ \\ rm x_2 x_5= 150 ④ \\ rm x_3 x_6= 200 ⑤ \\ rm x_1, x_2, x_3 , x_4 , x_5 , x_6 geq 0 end{cases}end{array}

① ② - ③ - ④ = ⑤

① ② - ③ - ⑤ = ④

① ② - ④ - ⑤ = ③

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

③ ④ ⑤ - ① = ②

③ ④ ⑤ - ② = ①

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

上述

个方程 , 有一个是多余的 , 最多有

个实际的方程 ;

这样可以得出以下定理 ;

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

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

假设有

rm m

个产地 ,

rm n

个销地 , 并且产销平衡 , 其基变量数为

rm m n - 1

;

rm m

个产地 ,

rm n

个销地 , 变量个数是

rm m times n

个 ;

rm m

个产地 ,

rm n

个销地 , 约束方程个数是

rm m n

个 , 这些约束方程中 , 有一个是多余的 , 最本质的方程最多有

rm m n - 1

个 ;

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

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

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

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

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

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

变量博客

0 人点赞