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

一、运输规划基变量个数

上一篇博客 【运筹学】运输规划 ( 运输规划问题的数学模型 | 运输问题引入 ) 提出了运输规划问题 , 其约束方程系数矩阵的系数都是 0 , 1 0,1 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 \begin{array}{lcl} \rm minW = 6x_1 + 4x_2 + 6x_3 + 6x_4 + 5x_5 + 5x_6 \\\\ \rm s.t\begin{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} minW=6x1​+4x2​+6x3​+6x4​+5x5​+5x6​s.t⎩⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎧​x1​+x2​+x3​=200x4​+x5​+x6​=300x1​+x4​=150x2​+x5​=150x3​+x6​=200x1​,x2​,x3​,x4​,x5​,x6​≥0​​

上述运输问题的系数矩阵为 : 5 5 5 个约束方程对应的是 5 × 6 \rm 5 \times 6 5×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 ) \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} ⎝⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎛​111000000111100100010010001001​⎠⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎞​

运输问题是产销平衡的 , 约束方程中前两个相加之和是 500 500 500 , 后三个相加之和也是 500 500 500 , 说明这 5 5 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 \begin{array}{lcl} \rm minW = 6x_1 + 4x_2 + 6x_3 + 6x_4 + 5x_5 + 5x_6 \\\\ \rm s.t\begin{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} minW=6x1​+4x2​+6x3​+6x4​+5x5​+5x6​s.t⎩⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎧​x1​+x2​+x3​=200    ①x4​+x5​+x6​=300    ②x1​+x4​=150    ③x2​+x5​=150    ④x3​+x6​=200    ⑤x1​,x2​,x3​,x4​,x5​,x6​≥0​​

① + ② - ③ - ④ = ⑤

① + ② - ③ - ⑤ = ④

① + ② - ④ - ⑤ = ③

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

③ + ④ + ⑤ - ① = ②

③ + ④ + ⑤ - ② = ①

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

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

这样可以得出以下定理 ;

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

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

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

m \rm m m 个产地 , n \rm n n 个销地 , 变量个数是 m × n \rm m \times n m×n 个 ;

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

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

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

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

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

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

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