【运筹学】运输规划 ( 运输规划问题的数学模型

运输规划涉及内容 :

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

② 表上作业法 ;

③ 运输问题应用 ;

将 两个产地 A 1 \rm A_1 A1​ , A 2 \rm A_2 A2​ 的物品运往 三个销售地 B 1 \rm B_1 B1​ , B 2 \rm B_2 B2​ , B 3 \rm B_3 B3​ ,

各地的 产量 , 销量 ,

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

A 1 , A 2 \rm A_1 , A_2 A1​,A2​ 的产量之和是 500 500 500 ,

B 1 , B 2 , B 3 \rm B_1 , B_2 , B_3 B1​,B2​,B3​ 的总的销量之和是 500 500 500 ,

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

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

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

假设变量 :

A 1 \rm A_1 A1​ 产地运往 B 1 \rm B_1 B1​ 产地的产品数量是 x 1 \rm x_1 x1​ ,

A 1 \rm A_1 A1​ 产地运往 B 2 \rm B_2 B2​ 产地的产品数量是 x 2 \rm x_2 x2​ ,

A 1 \rm A_1 A1​ 产地运往 B 3 \rm B_3 B3​ 产地的产品数量是 x 3 \rm x_3 x3​ ,

A 2 \rm A_2 A2​ 产地运往 B 1 \rm B_1 B1​ 产地的产品数量是 x 4 \rm x_4 x4​ ,

A 2 \rm A_2 A2​ 产地运往 B 2 \rm B_2 B2​ 产地的产品数量是 x 5 \rm x_5 x5​ ,

A 2 \rm A_2 A2​ 产地运往 B 3 \rm B_3 B3​ 产地的产品数量是 x 6 \rm x_6 x6​ ;

存在以下等式约束 :

A 1 \rm A_1 A1​ 的产量 x 1 + x 2 + x 3 = 200 \rm x_1 + x_2 + x_3 = 200 x1​+x2​+x3​=200 ;

A 2 \rm A_2 A2​ 的产量 x 4 + x 5 + x 6 = 300 \rm x_4 + x_5 + x_6 = 300 x4​+x5​+x6​=300 ;

B 1 \rm B_1 B1​ 的销量 x 1 + x 4 = 150 \rm x_1 + x_4 = 150 x1​+x4​=150 ;

B 2 \rm B_2 B2​ 的销量 x 2 + x 5 = 150 \rm x_2 + x_5= 150 x2​+x5​=150 ;

B 3 \rm B_3 B3​ 的销量 x 3 + x 6 = 200 \rm x_3 + x_6= 200 x3​+x6​=200 ;

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

x 1 , x 2 , x 3 , x 4 , x 5 , x 6 ≥ 0 \rm x_1, x_2, x_3 , x_4 , x_5 , x_6 \geq 0 x1​,x2​,x3​,x4​,x5​,x6​≥0

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

m i n W = 6 x 1 + 4 x 2 + 6 x 3 + 6 x 4 + 5 x 5 + 5 x 6 \rm minW = 6x_1 + 4x_2 + 6x_3 + 6x_4 + 5x_5 + 5x_6 minW=6x1​+4x2​+6x3​+6x4​+5x5​+5x6​

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

最终的线性规划如下 :

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 \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} minW=6x1​+4x2​+6x3​+6x4​+5x5​+5x6​s.t⎩⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎧​x1​+x2​+x3​=200x4​+x5​+x6​=300x1​+x4​=150x2​+x5​=150x3​+x6​=200x1​,x2​,x3​,x4​,x5​,x6​≥0​​

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

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

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

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

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

首先确定基是多少 , 将上述线性规划 , 转为标准形 , 约束方程的系数矩阵 A m × n \rm A_{m \times n} Am×n​ 是 m × n \rm m \times n m×n 矩阵 , n ≥ m \rm n \geq m n≥m , n \rm n n 是变量个数 , m \rm m m 是约束方程个数 ,

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

上述运输问题的系数矩阵为 : 5 5 5 个约束方程对应的是 5 × 6 \rm 5 \times 6 5×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 ) \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} ⎝⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎛​111000000111100100010010001001​⎠⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎞​

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

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

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