【运筹学】不平衡运输问题 ( 不平衡问题转化为平衡问题 )

一、运输规划产销不平衡问题

运输规划产销不平衡问题 :

运输规划问题中 , 总产量 与 总销量 可能不对等 , 这类问题称为 不平衡运输问题 ;

这类问题的求解方法是 将 不平衡问题 转化为 平衡问题 , 按照 产销平衡问题 求解 ;

① 产量大于销量时 : 存在 ∑ i = 1 m a i > ∑ j = 1 n b i \rm \sum_{i = 1}^{m} a_i > \sum_{j = 1}^{n} b_i ∑i=1m​ai​>∑j=1n​bi​

运输规划模型如下 : 销地满了 , 产地不够 ;

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} \leq 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 )​​

② 产量小于销量时 : 存在 ∑ i = 1 m a i < ∑ j = 1 n b i \rm \sum_{i = 1}^{m} a_i < \sum_{j = 1}^{n} b_i ∑i=1m​ai​ 销量 : 部分产地的产量剩余 , 这里就增加一个虚拟的销地 B n + 1 \rm B_{n+1} Bn+1​ , 各个产地 A i \rm A_i Ai​ 向该虚拟销地运价为 0 0 0 , 即 C i , n + 1 = 0 ,    ( i = 1 , 2 , ⋯   , m ) \rm C_{i, n + 1} = 0 , \ \ ( i = 1, 2, \cdots , m ) Ci,n+1​=0,  (i=1,2,⋯,m) ;

线性规划模型如下 :

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 , n + 1   ) 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 , n + 1 \ ) \\\\ \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,n+1 )xij​≥0    ( i=1,2,3,⋯,m  ;  j=1,2,3,⋯,n )​​

2 . 产量 < 销量 : 部分销地供应不足 , 这里就增加一个虚拟的产地 A m + 1 \rm A_{m+1} Am+1​ , 该虚拟产地 A i \rm A_i Ai​ 向各销地运价为 0 0 0 , 即 C m + 1 , j = 0 ,    ( j = 1 , 2 , ⋯   , n ) \rm C_{m + 1, j} = 0 , \ \ ( j = 1, 2, \cdots , n ) Cm+1,j​=0,  (j=1,2,⋯,n) ;

线性规划模型如下 :

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 , m + 1   ) ∑ 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 , m + 1 \ ) \\\\ \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,m+1 )∑i=1m​xij​=bj​    ( j=1,2,3,⋯,n )xij​≥0    ( i=1,2,3,⋯,m  ;  j=1,2,3,⋯,n )​​