§5.1运输问题
运输问题（TP，Transportation Problem）：从个发点往个收点运输货物，有关数据如下图所示：
其中（供需平衡）.
或见如下的供需-运费表：
问：应如何组织运输，才能既满足供需关系，又使得运费最省？
解：令= 从发点运往收点的货物的数量，，则可建立如下线性规划模型
，
其中，.▍
运输问题有供需平衡型（）运输问题和供需不平衡型（）运输问题.其中，供需不平衡又可分为供大于需（）和需大于供（）两种.本章将主要介绍供需平衡型运输问题.
令，
（cost matrix，费用矩阵），，
，
其中,
则的矩阵和向量形式为
.
注：此处，的形式纯粹是为讨论问题的便利而作的硬性规定，并不符合线性代数中的矩阵和向量的有关运算的定义.
显然，是一种线性规划问题，当然可用求解线性规划问题的一般方法（如单纯形法、对偶单纯形法等）来解；但是，如下所述，作为一种特殊的线性规划问题，其求解亦有特殊的方法.
令：中变量对应的列向量；：的第个行向量；
Th1的特性：
（1）；
（2）中恰有一个多余的约束方程；
（3）总可行；
（4）是全幺模阵；
（5）的任一基本解均为整数解；
（6）总有最优解.
证明：（1），的行向量组线性相关.于是，.
易证，的阶子矩阵，有.
故.
（2）由（1）知，的行向量组线性相关，且其中恰有一个行向量可由其余行向量线性表出.故对应地，中恰有一个多余的约束方程.
（3）由（1）知，约束方程组总有解；而且，易证.
（4）令，则由§6.2 Th2知，是全幺模阵.
（5）由（4）知，是全单模阵；又是整数向量，故由§6.2 Th1知,的任一基本解必为整数解.
（6）令，则，即有下界；又由（3）知，可行，必有最优解.▍
的基：的任一阶非奇异子矩阵.
类似地，可定义基变量；非基变量等.
命题（1）的任一个基均为幺模阵；
（2）（的基的构造）从中删去任一行，再从剩下的矩阵中选取个线性无关的列向量，则所得矩阵即为的一个基.
证明：（1）由（4）知，是全单模阵.（2）由（1）及基的定义得证.▍
的单纯形表：
W.L.O.G.设的一个基为，
令，，，
，，
则.
代入目标函数得
联立得
作典式
作单纯形表
由单纯形表易见，关于基的基本解为，相应的目标函数值为.
注：(1)关于基的检验数为（与标准形的检验数反号！）.
(2)在实际计算时，鉴于运输问题的特殊性质，其求解过程并不借助于单纯形表，而是借助于运输表来实现.
格子（mesh）
对的每一个变量，作一个格子与之对应，得格子表（集）
显然，有如下一一对应关系：格子表中的格子的变量的列向量.
,令.
规定：格子集线性无（相）关中的各列向量线性无（相）关.
定义 的线性无关的格子集称为基本格子集，记作：.
易见，当是基本格子集时，中的个列向量作成的矩阵去掉一个多余的行即为的一个基，基变量为，非基变量为.令，即得关于基的基本解.
定义 设，若，有，则称为行孤立格子；若，有，则称为列孤立格子.二者合称孤立格子（isolated mesh）.
孤立格子集的递归定义：
设，，若满足条件：（1）单个格子构成的格子集是孤立格子集；（2）当是一个孤立格子时，仍是一个孤立格子集，则称是一个孤立格子集.
例如，给定格子集，令，则是一个孤立格子集.
这是因为：（孤立格子集的递归定义）依次为孤立格子.
命题 的孤立格子集必是基本格子集.▍
运输问题（TP，Transportation Problem）：从个发点往个收点运输货物，有关数据如下图所示：
其中（供需平衡）.
或见如下的供需-运费表：
问：应如何组织运输，才能既满足供需关系，又使得运费最省？
解：令= 从发点运往收点的货物的数量，，则可建立如下线性规划模型
，
其中，.▍
运输问题有供需平衡型（）运输问题和供需不平衡型（）运输问题.其中，供需不平衡又可分为供大于需（）和需大于供（）两种.本章将主要介绍供需平衡型运输问题.
令，
（cost matrix，费用矩阵），，
，
其中,
则的矩阵和向量形式为
.
注：此处，的形式纯粹是为讨论问题的便利而作的硬性规定，并不符合线性代数中的矩阵和向量的有关运算的定义.
显然，是一种线性规划问题，当然可用求解线性规划问题的一般方法（如单纯形法、对偶单纯形法等）来解；但是，如下所述，作为一种特殊的线性规划问题，其求解亦有特殊的方法.
令：中变量对应的列向量；：的第个行向量；
Th1的特性：
（1）；
（2）中恰有一个多余的约束方程；
（3）总可行；
（4）是全幺模阵；
（5）的任一基本解均为整数解；
（6）总有最优解.
证明：（1），的行向量组线性相关.于是，.
易证，的阶子矩阵，有.
故.
（2）由（1）知，的行向量组线性相关，且其中恰有一个行向量可由其余行向量线性表出.故对应地，中恰有一个多余的约束方程.
（3）由（1）知，约束方程组总有解；而且，易证.
（4）令，则由§6.2 Th2知，是全幺模阵.
（5）由（4）知，是全单模阵；又是整数向量，故由§6.2 Th1知,的任一基本解必为整数解.
（6）令，则，即有下界；又由（3）知，可行，必有最优解.▍
的基：的任一阶非奇异子矩阵.
类似地，可定义基变量；非基变量等.
命题（1）的任一个基均为幺模阵；
（2）（的基的构造）从中删去任一行，再从剩下的矩阵中选取个线性无关的列向量，则所得矩阵即为的一个基.
证明：（1）由（4）知，是全单模阵.（2）由（1）及基的定义得证.▍
的单纯形表：
W.L.O.G.设的一个基为，
令，，，
，，
则.
代入目标函数得
联立得
作典式
作单纯形表
由单纯形表易见，关于基的基本解为，相应的目标函数值为.
注：(1)关于基的检验数为（与标准形的检验数反号！）.
(2)在实际计算时，鉴于运输问题的特殊性质，其求解过程并不借助于单纯形表，而是借助于运输表来实现.
格子（mesh）
对的每一个变量，作一个格子与之对应，得格子表（集）
显然，有如下一一对应关系：格子表中的格子的变量的列向量.
,令.
规定：格子集线性无（相）关中的各列向量线性无（相）关.
定义 的线性无关的格子集称为基本格子集，记作：.
易见，当是基本格子集时，中的个列向量作成的矩阵去掉一个多余的行即为的一个基，基变量为，非基变量为.令，即得关于基的基本解.
定义 设，若，有，则称为行孤立格子；若，有，则称为列孤立格子.二者合称孤立格子（isolated mesh）.
孤立格子集的递归定义：
设，，若满足条件：（1）单个格子构成的格子集是孤立格子集；（2）当是一个孤立格子时，仍是一个孤立格子集，则称是一个孤立格子集.
例如，给定格子集，令，则是一个孤立格子集.
这是因为：（孤立格子集的递归定义）依次为孤立格子.
命题 的孤立格子集必是基本格子集.▍
