文章目录
一、运输规划问题模型及变化
二、运输规划问题求解 ( 表上作业法 )
一、运输规划问题模型及变化
运输规划问题一般形式 ( 产销平衡 ) :
m \rm mm 个产地 : A 1 , A 2 , A 3 , ⋯ , A m \rm A_1, A_2,A_3 , \cdots , A_mA
1
,A
2
,A
3
,⋯,A
m
;
n \rm nn 个销地 : B 1 , B 2 , B 3 , ⋯ , B n \rm B_1, B_2,B_3 , \cdots , B_nB
1
,B
2
,B
3
,⋯,B
n
;
a i \rm a_ia
i
表示产地 A i \rm A_iA
i
的产量 , i = 1 , 2 , 3 , ⋯ , m \rm i = 1, 2,3, \cdots , mi=1,2,3,⋯,m ;
b j \rm b_jb
j
表示产地 B j \rm B_jB
j
的销量 , j = 1 , 2 , 3 , ⋯ , n \rm j = 1, 2,3, \cdots , nj=1,2,3,⋯,n ;
c i j \rm c_{ij}c
ij
表示将 A i \rm A_iA
i
产地的产品运往 B j \rm B_jB
j
销地的运输成本 ;
假设 x i j \rm x_{ij}x
ij
是从产地 A i \rm A_iA
i
运往销地 B j \rm B_jB
j
的运输量 ;
可以得到如下线性规划模型 :
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 )
minW=∑mi=1∑nj=1cijxijs.t⎧⎩⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪∑nj=1xij=ai ( i=1,2,3,⋯,m )∑mi=1xij=bj ( j=1,2,3,⋯,n )xij≥0 ( i=1,2,3,⋯,m ; j=1,2,3,⋯,n )
minW=∑i=1m∑j=1ncijxijs.t{∑j=1nxij=ai ( i=1,2,3,⋯,m )∑i=1mxij=bj ( j=1,2,3,⋯,n )xij≥0 ( i=1,2,3,⋯,m ; j=1,2,3,⋯,n )
minW=∑
i=1
m
∑
j=1
n
c
ij
x
ij
s.t
⎩
⎪
⎪
⎪
⎪
⎪
⎪
⎨
⎪
⎪
⎪
⎪
⎪
⎪
⎧
∑
j=1
n
x
ij
=a
i
( i=1,2,3,⋯,m )
∑
i=1
m
x
ij
=b
j
( j=1,2,3,⋯,n )
x
ij
≥0 ( i=1,2,3,⋯,m ; j=1,2,3,⋯,n )
此外运输规划还有一些变化模型 :
① 目标函数求最大值 , 如利润最大 ;
② 运输能力限制 , 需要在模型中加入等式或不等式约束条件 ;
③ 产销不平衡 , 参考 【运筹学】运输规划 ( 运输规划基变量个数 | 运输问题一般形式 | 产销平衡 | 产销不平衡 ) 三、运输规划中的产销( 不 )平衡问题 ;
二、运输规划问题求解 ( 表上作业法 )
运输问题线性规划 本质也是线性规划 , 是特殊的线性规划 , 其 最优解 可以使用 单纯形法 求得 ;
运输问题是线性规划中比较简单的模型 , 其系数矩阵中的元素都是 0 , 1 0,10,1 , 是稀疏矩阵 , 可以使用简化版的单纯形法求最优解 , 该方法称为 " 表上作业法 " ;
m \rm mm 个产地 , n \rm nn 个销地 , 变量个数是 m × n \rm m \times nm×n 个 ;
m \rm mm 个产地 , n \rm nn 个销地 , 约束方程个数是 m + n \rm m + nm+n 个 , 这些约束方程中 , 有一个是多余的 , 最本质的方程最多有 m + n − 1 \rm m + n - 1m+n−1 个 ;
第一步 , 开始找 初始基可行解 , 基变量个数是 m + n − 1 \rm m + n - 1m+n−1 个 , 基矩阵的秩是 m + n − 1 \rm m + n - 1m+n−1 ;
求解基可行解时 , 非基变量取值 0 00 , 基变量允许非 0 00 变量 , 找 m + n − 1 \rm m + n - 1m+n−1 个基变量 ,
第二步 , 找到一个规则 , 判断是否是最优解 ;
第三步 , 如果不是最优解 , 进行 迭代 , 如何进行迭代 ;
