【运筹学】运输规划 ( 运输规划问题的数学模型 | 运输问题引入 )

韩曙亮

发布于 2023-03-28 20:45:14

7100

文章被收录于专栏：韩曙亮的移动开发专栏韩曙亮的移动开发专栏

文章目录

一、运输规划涉及内容

运输规划涉及内容 :

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

② 表上作业法 ;

③ 运输问题应用 ;

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

将两个产地

\rm A_1

,

\rm A_2

的物品运往三个销售地

\rm B_1

,

\rm B_2

,

\rm B_3

,

各地的产量 , 销量 ,

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

	B 1 \rm B_1 B1	B 2 \rm B_2 B2	B 3 \rm B_3 B3	产量
A 1 \rm A_1 A1	6 6 6	4 4 4	6 6 6	200 200 200
A 2 \rm A_2 A2	6 6 6	5 5 5	5 5 5	300 300 300
销量	150 150 150	150 150 150	200 200 200

\rm B_1

\rm B_2

\rm B_3

产量

\rm A_1

6

4

6

200

\rm A_2

6

5

300

销量

150

200

\rm A_1 , A_2

的产量之和是

500

,

\rm B_1 , B_2 , B_3

的总的销量之和是

500

,

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

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

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

500

;

假设变量 :

	B 1 \rm B_1 B1	B 2 \rm B_2 B2	B 3 \rm B_3 B3	产量
A 1 \rm A_1 A1	x 1 \rm x_1 x1	x 2 \rm x_2 x2	x 3 \rm x_3 x3	200 200 200
A 2 \rm A_2 A2	x 4 \rm x_4 x4	x 5 \rm x_5 x5	x 6 \rm x_6 x6	300 300 300
销量	150 150 150	150 150 150	200 200 200

\rm B_1

\rm B_2

\rm B_3

产量

\rm A_1

\rm x_1

\rm x_2

\rm x_3

200

\rm A_2

\rm x_4

\rm x_5

\rm x_6

300

销量

150

200

\rm A_1

产地运往

\rm B_1

产地的产品数量是

\rm x_1

,

\rm A_1

产地运往

\rm B_2

产地的产品数量是

\rm x_2

,

\rm A_1

产地运往

\rm B_3

产地的产品数量是

\rm x_3

,

\rm A_2

产地运往

\rm B_1

产地的产品数量是

\rm x_4

,

\rm A_2

产地运往

\rm B_2

产地的产品数量是

\rm x_5

,

\rm A_2

产地运往

\rm B_3

产地的产品数量是

\rm x_6

;

存在以下等式约束 :

\rm A_1

的产量

\rm x_1 + x_2 + x_3 = 200

;

\rm A_2

的产量

\rm x_4 + x_5 + x_6 = 300

;

\rm B_1

的销量

\rm x_1 + x_4 = 150

;

\rm B_2

的销量

\rm x_2 + x_5= 150

;

\rm B_3

的销量

\rm x_3 + x_6= 200

;

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

\rm x_1, x_2, x_3 , x_4 , x_5 , x_6 \geq 0

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

\rm minW = 6x_1 + 4x_2 + 6x_3 + 6x_4 + 5x_5 + 5x_6

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

最终的线性规划如下 :

\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}

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

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

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

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

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

首先确定基是多少 , 将上述线性规划 , 转为标准形 , 约束方程的系数矩阵

\rm A_{m \times n}

是

\rm m \times n

矩阵 ,

\rm n \geq m

,

\rm n

是变量个数 ,

\rm m

是约束方程个数 ,

假设

\rm A_{m \times n}

矩阵是行满秩的 , 即秩为

\rm m

, 约束方程个数为

\rm m

, 上述运输问题的约束方程个数是

5

个 ;

上述运输问题的系数矩阵为 :

5

个约束方程对应的是

\rm 5 \times 6

矩阵 ;

\begin{pmatrix} \quad 1 \quad 1 \quad 1 \quad 0 \quad 0 \quad 0 \quad \\\\ \quad 0 \quad 0 \quad 0 \quad 1 \quad 1 \quad 1 \quad \\\\ \quad 1 \quad 0 \quad 0 \quad 1 \quad 0 \quad 0 \quad \\\\ \quad 0 \quad 1 \quad 0 \quad 0 \quad 1 \quad 0 \quad \\\\ \quad 0 \quad 0 \quad 1 \quad 0 \quad 0 \quad 1 \quad \end{pmatrix}

运输问题约束方程的系数矩阵都是由

0

或

1

组成的 , 这种矩阵称为稀疏矩阵 , 稀疏矩阵的计算要远远比正常的矩阵更简单 ;

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

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

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2021-01-04，如有侵权请联系 cloudcommunity@tencent.com 删除

变量