【运筹学】运输规划 ( 运输规划基变量个数 | 运输问题一般形式 | 产销平衡 | 产销不平衡 )

一、运输规划基变量个数

运输规划问题 :

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​​

根据上一篇博客 【运筹学】运输规划 ( 运输规划基变量个数分析 ) 可知 , 该线性规划的约束方程个数是 m + n − 1 = 4 \rm m+ n - 1 = 4 m+n−1=4 , 基矩阵的秩也是 4 4 4 ;

继续求解上述运输规划问题的最优解 ;

该运输规划问题有 6 6 6 个变量 , 找到一个初始基可行解 , ① 满足上述等式方程 , ② 该解还是基解 ;

涉及到基解 , 变量就可以分为两部分 , 基变量 与 非基变量 , 解基解的时候 , 令非基变量为 0 0 0 ;

从 6 6 6 个变量中 , 找出初始基变量 , 确定初始基可行解 , 基变量的个数是 m + n − 1 = 3 + 2 − 1 = 4 \rm m+ n - 1 = 3 + 2 - 1= 4 m+n−1=3+2−1=4 ;

初始基可行解对应的 基变量 4 4 4 个 , 非基变量 2 2 2 个 ;

运输问题的系数矩阵是 稀疏矩阵 , 矩阵中的元素都是 0 0 0 或 1 1 1 ;

二、运输规划问题一般形式

运输规划问题一般形式 ( 产销平衡 ) :

m \rm m m 个产地 : A 1 , A 2 , A 3 , ⋯   , A m \rm A_1, A_2,A_3 , \cdots , A_m A1​,A2​,A3​,⋯,Am​ ;

n \rm n n 个销地 : B 1 , B 2 , B 3 , ⋯   , B n \rm B_1, B_2,B_3 , \cdots , B_n B1​,B2​,B3​,⋯,Bn​ ;

a i \rm a_i ai​ 表示产地 A i \rm A_i Ai​ 的产量 , i = 1 , 2 , 3 , ⋯   , m \rm i = 1, 2,3, \cdots , m i=1,2,3,⋯,m ;

b j \rm b_j bj​ 表示产地 B j \rm B_j Bj​ 的销量 , j = 1 , 2 , 3 , ⋯   , n \rm j = 1, 2,3, \cdots , n j=1,2,3,⋯,n ;

c i j \rm c_{ij} cij​ 表示将 A i \rm A_i Ai​ 产地的产品运往 B j \rm B_j Bj​ 销地的运输成本 ;

假设 x i j \rm x_{ij} xij​ 是从产地 A i \rm A_i Ai​ 运往销地 B j \rm B_j Bj​ 的运输量 ;

可以得到如下线性规划模型 :

m i n W = ∑ i = 1 m ∑ j = 1 n c i j x i j s . t { ∑ j = 1 n x i j = a i      (   i = 1 , 2 , 3 , ⋯   , m   ) ∑ i = 1 m x i j = b j      (   j = 1 , 2 , 3 , ⋯   , n   ) x i j ≥ 0      (   i = 1 , 2 , 3 , ⋯   , m    ;    j = 1 , 2 , 3 , ⋯   , n   ) \begin{array}{lcl} \rm minW = \sum_{i = 1}^{m} \sum_{j = 1}^{n} c_{ij} x_{ij} \\\\ \rm s.t\begin{cases} \rm \sum_{j = 1}^{n} x_{ij} = a_i \ \ \ \ ( \ i = 1, 2,3, \cdots , m \ ) \\\\ \rm \sum_{i = 1}^{m} x_{ij} = b_j \ \ \ \ ( \ j = 1, 2,3, \cdots , n \ ) \\\\ \rm x_{ij} \geq 0 \ \ \ \ ( \ i = 1, 2,3, \cdots , m \ \ ; \ \ j = 1, 2,3, \cdots , n \ ) \end{cases}\end{array} minW=∑i=1m​∑j=1n​cij​xij​s.t⎩⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎧​∑j=1n​xij​=ai​    ( i=1,2,3,⋯,m )∑i=1m​xij​=bj​    ( j=1,2,3,⋯,n )xij​≥0    ( i=1,2,3,⋯,m  ;  j=1,2,3,⋯,n )​​

三、运输规划中的产销( 不 )平衡问题

运输规划中 , 如果产量 = 销量 , 则 产销平衡 ;

如果 产量 ≥ \geq ≥ 销量 , 或 产量 ≤ \leq ≤ 销量 , 则 产销不平衡 ;

产量 = = = 销量 , 销量可以全部满足 , 产量可以满足 ,

产量的约束方程是 等式 ;

销量的约束方程是 等式 ;

产量 ≥ \geq ≥ 销量 , 销量可以全部满足 , 产量有些地方就有剩余的 ,

产量的约束方程就是 大于等于不等式 ;

销量的约束方程仍然是 等式 ;

产量 ≤ \leq ≤ 销量 , 产量可以全部满足 , 销量有些地方就有剩余的 ,

产量的约束方程仍然是 等式 ;

销量的约束方程仍然就是 小于等于不等式 ;