一、运输规划问题模型及变化

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

$\mathrm{m}$ 个产地 : ${\mathrm{A}}_1,{\mathrm{A}}_2,{\mathrm{A}}_3,\cdots ,{\mathrm{A}}_{\mathrm{m}}$ ;

$\mathrm{n}$ 个销地 : ${\mathrm{B}}_1,{\mathrm{B}}_2,{\mathrm{B}}_3,\cdots ,{\mathrm{B}}_{\mathrm{n}}$ ;

${\mathrm{a}}_{\mathrm{i}}$ 表示产地 ${\mathrm{A}}_{\mathrm{i}}$ 的产量 , $\mathrm{i}=1,2,3,\cdots ,\mathrm{m}$ ;

${\mathrm{b}}_{\mathrm{j}}$ 表示产地 ${\mathrm{B}}_{\mathrm{j}}$ 的销量 , $\mathrm{j}=1,2,3,\cdots ,\mathrm{n}$ ;

${\mathrm{c}}_{\mathrm{i}\mathrm{j}}$ 表示将 ${\mathrm{A}}_{\mathrm{i}}$ 产地的产品运往 ${\mathrm{B}}_{\mathrm{j}}$ 销地的运输成本 ;

假设 ${\mathrm{x}}_{\mathrm{i}\mathrm{j}}$ 是从产地 ${\mathrm{A}}_{\mathrm{i}}$ 运往销地 ${\mathrm{B}}_{\mathrm{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   )

此外运输规划还有一些变化模型 :

① 目标函数求最大值 , 如利润最大 ;

② 运输能力限制 , 需要在模型中加入等式或不等式约束条件 ;

③ 产销不平衡 , 参考 【运筹学】运输规划 ( 运输规划基变量个数 | 运输问题一般形式 | 产销平衡 | 产销不平衡 ) 三、运输规划中的产销( 不 )平衡问题 ;

二、运输规划问题求解 ( 表上作业法 )

运输问题线性规划 本质也是线性规划 , 是特殊的线性规划 , 其 最优解 可以使用 单纯形法 求得 ;

运输问题是线性规划中比较简单的模型 , 其系数矩阵中的元素都是 $0,1$ , 是稀疏矩阵 , 可以使用简化版的单纯形法求最优解 , 该方法称为 " 表上作业法 " ;

$\mathrm{m}$ 个产地 , $\mathrm{n}$ 个销地 , 变量个数是 $\mathrm{m}\times \mathrm{n}$ 个 ;

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

第一步 , 开始找 初始基可行解 , 基变量个数是 $\mathrm{m}+\mathrm{n}-1$ 个 , 基矩阵的秩是 $\mathrm{m}+\mathrm{n}-1$ ;

求解基可行解时 , 非基变量取值 $0$ , 基变量允许非 $0$ 变量 , 找 $\mathrm{m}+\mathrm{n}-1$ 个基变量 ,

第二步 , 找到一个规则 , 判断是否是最优解 ;

第三步 , 如果不是最优解 , 进行 迭代 , 如何进行迭代 ;

文章来源: hanshuliang.blog.csdn.net，作者：韩曙亮，版权归原作者所有，如需转载，请联系作者。

原文链接：hanshuliang.blog.csdn.net/article/details/112221582