【运筹学】运输规划 ( 运输规划基变量个数 | 运输问题一般形式 | 产销平衡 | 产销不平衡 )

韩曙亮

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

4870

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

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

文章目录

一、运输规划基变量个数

运输规划问题 :

\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 m+ n - 1 = 4

, 基矩阵的秩也是

;

继续求解上述运输规划问题的最优解 ;

该运输规划问题有

个变量 , 找到一个初始基可行解 , ① 满足上述等式方程 , ② 该解还是基解 ;

涉及到基解 , 变量就可以分为两部分 , 基变量与非基变量 , 解基解的时候 , 令非基变量为

;

从

个变量中 , 找出初始基变量 , 确定初始基可行解 , 基变量的个数是

\rm m+ n - 1 = 3 + 2 - 1= 4

;

初始基可行解对应的基变量

个 , 非基变量

个 ;

运输问题的系数矩阵是稀疏矩阵 , 矩阵中的元素都是

或

;

二、运输规划问题一般形式

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

\rm m

个产地 :

\rm A_1, A_2,A_3 , \cdots , A_m

;

\rm n

个销地 :

\rm B_1, B_2,B_3 , \cdots , B_n

;

\rm a_i

表示产地

\rm A_i

的产量 ,

\rm i = 1, 2,3, \cdots , m

;

\rm b_j

表示产地

\rm B_j

的销量 ,

\rm j = 1, 2,3, \cdots , n

;

\rm c_{ij}

表示将

\rm A_i

产地的产品运往

\rm B_j

销地的运输成本 ;

假设

\rm x_{ij}

是从产地

\rm A_i

运往销地

\rm B_j

的运输量 ;

可以得到如下线性规划模型 :

\begin{array}{lcl} \rm minW = \sum_{i = 1}^{m} \sum_{j = 1}^{n} c_{ij} x_{ij} \\\\ \rm s.t\begin{cases} \rm \sum_{j = 1}^{n} x_{ij} = a_i \ \ \ \ ( \ i = 1, 2,3, \cdots , m \ ) \\\\ \rm \sum_{i = 1}^{m} x_{ij} = b_j \ \ \ \ ( \ j = 1, 2,3, \cdots , n \ ) \\\\ \rm x_{ij} \geq 0 \ \ \ \ ( \ i = 1, 2,3, \cdots , m \ \ ; \ \ j = 1, 2,3, \cdots , n \ ) \end{cases}\end{array}