提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  其他

当前栏目

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

规划 问题 引入 运筹学 运输 数学模型
2023-06-13 09:17:48 时间

文章目录

一、运输规划涉及内容

运输规划涉及内容 :

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

② 表上作业法 ;

③ 运输问题应用 ;

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

将 两个产地

\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
5
300

销量

150
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
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

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

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

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

相关文章