一、运输规划涉及内容

运输规划涉及内容 :

① 运输规划问题的数学模型 ;

② 表上作业法 ;

③ 运输问题应用 ;

二、运输规划问题的数学模型

将 两个产地 ${\mathrm{A}}_1$ , ${\mathrm{A}}_2$ 的物品运往 三个销售地 ${\mathrm{B}}_1$ , ${\mathrm{B}}_2$ , ${\mathrm{B}}_3$ ,

各地的 产量 , 销量 ,

各个产地 运往 各个销售地 的每件物品的运费如下图所示 :

${\mathrm{A}}_1,{\mathrm{A}}_2$ 的产量之和是 $500$ ,

${\mathrm{B}}_1,{\mathrm{B}}_2,{\mathrm{B}}_3$ 的总的销量之和是 $500$ ,

上述产量之和等于销量之和 , 是产销平衡的 ;

不同的产地运往不同的销地 , 运费不同 , 如何合理安排运输 , 能使总运费最少 ;

这里存在一个产销平衡问题 : 总产量 = 总销量 = $500$ ;

假设变量 :

${\mathrm{A}}_1$ 产地运往 ${\mathrm{B}}_1$ 产地的产品数量是 ${\mathrm{x}}_1$ ,

${\mathrm{A}}_1$ 产地运往 ${\mathrm{B}}_2$ 产地的产品数量是 ${\mathrm{x}}_2$ ,

${\mathrm{A}}_1$ 产地运往 ${\mathrm{B}}_3$ 产地的产品数量是 ${\mathrm{x}}_3$ ,

${\mathrm{A}}_2$ 产地运往 ${\mathrm{B}}_1$ 产地的产品数量是 ${\mathrm{x}}_4$ ,

${\mathrm{A}}_2$ 产地运往 ${\mathrm{B}}_2$ 产地的产品数量是 ${\mathrm{x}}_5$ ,

${\mathrm{A}}_2$ 产地运往 ${\mathrm{B}}_3$ 产地的产品数量是 ${\mathrm{x}}_6$ ;

存在以下等式约束 :

${\mathrm{A}}_1$ 的产量 ${\mathrm{x}}_1+{\mathrm{x}}_2+{\mathrm{x}}_3=200$ ;

${\mathrm{A}}_2$ 的产量 ${\mathrm{x}}_4+{\mathrm{x}}_5+{\mathrm{x}}_6=300$ ;

${\mathrm{B}}_1$ 的销量 ${\mathrm{x}}_1+{\mathrm{x}}_4=150$ ;

${\mathrm{B}}_2$ 的销量 ${\mathrm{x}}_2+{\mathrm{x}}_5=150$ ;

${\mathrm{B}}_3$ 的销量 ${\mathrm{x}}_3+{\mathrm{x}}_6=200$ ;

变量约束 : 每个变量肯定大于等于 0 ;

${\mathrm{x}}_1,{\mathrm{x}}_2,{\mathrm{x}}_3,{\mathrm{x}}_4,{\mathrm{x}}_5,{\mathrm{x}}_6\ge 0$

目标函数 : 目的是为了使运费最小 ;

$\mathrm{m}\mathrm{i}\mathrm{n}\mathrm{W}=6{\mathrm{x}}_1+4{\mathrm{x}}_2+6{\mathrm{x}}_3+6{\mathrm{x}}_4+5{\mathrm{x}}_5+5{\mathrm{x}}_6$

上述的目标函数与约束方程都是线性的 , 因此该规划是线性规划 ;

最终的线性规划如下 :

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

使用单纯形法对上述规划求解即可得到最优解 ;

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

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

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

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

首先确定基是多少 , 将上述线性规划 , 转为标准形 , 约束方程的系数矩阵 ${\mathrm{A}}_{\mathrm{m}\times \mathrm{n}}$ 是 $\mathrm{m}\times \mathrm{n}$ 矩阵 , $\mathrm{n}\ge \mathrm{m}$ , $\mathrm{n}$ 是变量个数 , $\mathrm{m}$ 是约束方程个数 ,

假设 ${\mathrm{A}}_{\mathrm{m}\times \mathrm{n}}$ 矩阵是行满秩的 , 即秩为 $\mathrm{m}$ , 约束方程个数为 $\mathrm{m}$ , 上述运输问题的约束方程个数是 $5$ 个 ;

上述运输问题的系数矩阵为 : $5$ 个约束方程对应的是 $5\times 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 )

运输问题约束方程的 系数矩阵都是由 $0$ 或 $1$ 组成 的 , 这种矩阵称为 稀疏矩阵 , 稀疏矩阵的计算要远远比正常的矩阵更简单 ;

针对运输问题 , 存在一个简化版的单纯形法 ;

简化版的单纯形法与单纯形法的框架基本类似 , 也需要按照 ① 初始基可行解 , ② 最优解判定 , ③ 迭代 , 步骤进行计算 ;

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

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