§5.2初始基本可行解
本节来介绍求的一个初始基本可行解的两种方法：西北角法和最小元素法.
如§5.1所言，运输问题的求解过程并不象一般线性规划问题一样借助于单纯形表，而是借助于运输表来实现；但其算法在理论基础、基本思想、算法步骤（包括初始基本可行解的选取、最优性的验证、转轴）等各方面都和单纯形法是一致的.
供需平衡型运输问题的运输表：
运输表实际上是运输问题的单纯形表.
一.西北角法基本思想：优先安排运输表中的西北角处的格子（即编号小的格子）对应的发点与收点之间的运输业务.
使用条件：已知.
步骤：
1.令西北角格子对应的变量的值为.将填入格子中，并圈起.
2.令，.
当时，删去第行，并在格子内画；
当时，删去第列，并在格子内画；
当时，删去第行（或第列），并在格子（或）内画.
3.重复1，2，直至所有行、列均被删去，则得的一个基本格子集为被圈起，相应的基本可行解为.
注：（1）在利用西北角法得到的最终的运输表中，被圈起的元素为基变量的值，画的元素为非基变量的值；而且，被圈起的元素的个数必恰为.这是因为：被圈起的元素的个数=基变量的个数=基中的列向量的个数==.
（2）西北角法仅用到的供应量和需求量，并不涉及单位运费.
Th1利用西北角法必可求得的一个基本可行解.
证明：由算法步骤知，是一个孤立格子集，且.
故由§5.2命题知，必是一个基本格子集.
于是，从中去掉一个多余的行，即得的一个基，相应的基本可行解为.▍
例1设中，，，试利用西北角法求的一个基本可行解.
解：
的一个基本格子集为.
故从中去掉一个多余的行，即得的一个基，相应的基本可行解为，其它.▍
注：当最后仅剩下一个格子时，不能画，只能填数圈起，以使得被圈起的元素的个数（基变量的个数）为.
二 最小元素法基本思想：优先安排运输表中的单位运费最小的格子对应的发点与收点之间的运输业务（当最小单位运费不唯一时，可任选其一）.
使用条件：已知.
步骤：
1.令,.
将填入格子中，并圈起.
2.令，.
当时，删去第行，并在格子内画；
当时，删去第列，并在格子内画；
当时，删去第行（或第列），并在格子（或）内画.
3.重复1，2，直至所有行、列均被删去，则得的一个基本格子集为被圈起，相应的基本可行解为.
注：（1）在利用最小元素法得到的最终的运输表中，被圈起的元素为基变量的值，画的元素为非基变量的值，且被圈起的元素的个数必恰为.
（2）最小元素法和西北角法的唯一区别在于：（算法的步骤1）是否以单位运费为安排运输业务的依据.
Th2利用最小元素法必可求得的一个基本可行解.▍
例2设中，，，，试利用最小元素法求的一个基本可行解.
解：
的一个基本格子集为.
故从中去掉一个多余的行，即得的一个基，相应的基本可行解为，其它.▍
西北角法和最小元素法的优劣比较
最小元素法优先安排单位运费最小的发点与收点之间的运输业务，
一般地，利用最小元素法求得的基本可行解常优于（目标函数值较小）利用西北角法求得的基本可行解.故以后常用最小元素法求的一个初始基本可行解.
本节来介绍求的一个初始基本可行解的两种方法：西北角法和最小元素法.
如§5.1所言，运输问题的求解过程并不象一般线性规划问题一样借助于单纯形表，而是借助于运输表来实现；但其算法在理论基础、基本思想、算法步骤（包括初始基本可行解的选取、最优性的验证、转轴）等各方面都和单纯形法是一致的.
供需平衡型运输问题的运输表：
运输表实际上是运输问题的单纯形表.
一.西北角法基本思想：优先安排运输表中的西北角处的格子（即编号小的格子）对应的发点与收点之间的运输业务.
使用条件：已知.
步骤：
1.令西北角格子对应的变量的值为.将填入格子中，并圈起.
2.令，.
当时，删去第行，并在格子内画；
当时，删去第列，并在格子内画；
当时，删去第行（或第列），并在格子（或）内画.
3.重复1，2，直至所有行、列均被删去，则得的一个基本格子集为被圈起，相应的基本可行解为.
注：（1）在利用西北角法得到的最终的运输表中，被圈起的元素为基变量的值，画的元素为非基变量的值；而且，被圈起的元素的个数必恰为.这是因为：被圈起的元素的个数=基变量的个数=基中的列向量的个数==.
（2）西北角法仅用到的供应量和需求量，并不涉及单位运费.
Th1利用西北角法必可求得的一个基本可行解.
证明：由算法步骤知，是一个孤立格子集，且.
故由§5.2命题知，必是一个基本格子集.
于是，从中去掉一个多余的行，即得的一个基，相应的基本可行解为.▍
例1设中，，，试利用西北角法求的一个基本可行解.
解：
的一个基本格子集为.
故从中去掉一个多余的行，即得的一个基，相应的基本可行解为，其它.▍
注：当最后仅剩下一个格子时，不能画，只能填数圈起，以使得被圈起的元素的个数（基变量的个数）为.
二 最小元素法基本思想：优先安排运输表中的单位运费最小的格子对应的发点与收点之间的运输业务（当最小单位运费不唯一时，可任选其一）.
使用条件：已知.
步骤：
1.令,.
将填入格子中，并圈起.
2.令，.
当时，删去第行，并在格子内画；
当时，删去第列，并在格子内画；
当时，删去第行（或第列），并在格子（或）内画.
3.重复1，2，直至所有行、列均被删去，则得的一个基本格子集为被圈起，相应的基本可行解为.
注：（1）在利用最小元素法得到的最终的运输表中，被圈起的元素为基变量的值，画的元素为非基变量的值，且被圈起的元素的个数必恰为.
（2）最小元素法和西北角法的唯一区别在于：（算法的步骤1）是否以单位运费为安排运输业务的依据.
Th2利用最小元素法必可求得的一个基本可行解.▍
例2设中，，，，试利用最小元素法求的一个基本可行解.
解：
的一个基本格子集为.
故从中去掉一个多余的行，即得的一个基，相应的基本可行解为，其它.▍
西北角法和最小元素法的优劣比较
最小元素法优先安排单位运费最小的发点与收点之间的运输业务，
一般地，利用最小元素法求得的基本可行解常优于（目标函数值较小）利用西北角法求得的基本可行解.故以后常用最小元素法求的一个初始基本可行解.
