1、第第1页页第第2页页第第3页页一般线性规划问题的求解方法：一般线性规划问题的求解方法：单纯形法单纯形法。实际工作当中，往往有些线性规划问题，它们的实际工作当中，往往有些线性规划问题，它们的约束方程组的系数矩阵具有特殊的结构，这就有约束方程组的系数矩阵具有特殊的结构，这就有可能找到比单纯形法更为简便的求解方法。可能找到比单纯形法更为简便的求解方法。运输问题运输问题就属于这样一类特殊的就属于这样一类特殊的线性规划问题线性规划问题。第第4页页经济建设中，经常碰到大宗物资调运问题：利用现有经济建设中，经常碰到大宗物资调运问题：利用现有的交通运输网络，将煤炭、钢铁、木材、粮食等物资的交通运输网络，将煤炭
2、、钢铁、木材、粮食等物资，从生产地运往消费地，使得总运费最小。，从生产地运往消费地，使得总运费最小。第第5页页用数学语言对上述问题进行描述：用数学语言对上述问题进行描述：1.有有 m个生产地个生产地 Ai：i=1,2,m；供应量分别为：；供应量分别为：ai，i=1,2,m；2.有有n个消费地个消费地 Bj：j=1,2,n；需求量分别为：；需求量分别为：bj，j=1,2,n；3.单位物资从单位物资从 Ai 到到 Bj 的运价为的运价为 cij。第第6页页 销地销地产地产地B1B2Bn产量产量A1c11c12c1na1Amcm1cm2cmnam销量销量b1b2bn单位运价单位运价产地产量产地产量销
3、地销量销地销量x11x12x1nxm1xm2xmn第第7页页如果运输问题中，总产量等于总销量，即有如果运输问题中，总产量等于总销量，即有 njjmiiba11则称为则称为产销平衡运输问题产销平衡运输问题。第第8页页若用若用 xij 表示从表示从 Ai 到到 Bj 的运量，要得出总运费最小的运量，要得出总运费最小的调运方案，可建立如下数学模型：的调运方案，可建立如下数学模型：0,.,1,.,1,min1111ijjmiijinjijminjijijxnjbxmiaxxcz这就是运输问题的数学模型。这就是运输问题的数学模型。第第9页页如果运输问题中，总产量不等于总销量，即有如果运输问题中，总产量不
4、等于总销量，即有 njjmiiba11称为称为产销不平衡运输问题产销不平衡运输问题。第第10页页1、有、有 mn 个变量。个变量。2、（、（m+n）个约束条件，且都为等式。）个约束条件，且都为等式。3、其系数矩阵为：、其系数矩阵为：第第11页页 111.1111111.111.111.11.212222111211mnmmnnxxxxxxxxxm行行n行行第第12页页 该 系 数 矩 阵 中 对 应 于 变 量该 系 数 矩 阵 中 对 应 于 变 量 xi j的 系 数 向 量的 系 数 向 量 Pi j=（01010）T，其分量中除，其分量中除第第 i 个个和和第第 m+j 个个为为 1
5、以外，其余的都为以外，其余的都为 0。（1）约束条件系数矩阵的元素等于）约束条件系数矩阵的元素等于 0 或或 1；（2）约束条件系数矩阵的每一列有两个非）约束条件系数矩阵的每一列有两个非 0 元素，对元素，对应于每一个变量的应于每一个变量的前前 m 个约束条件中出现一次，后个约束条件中出现一次，后 n 个约束条件中也出现一次个约束条件中也出现一次。第第13页页4、对于产销平衡的运输问题：、对于产销平衡的运输问题：特点特点 1：模型中最多只有：模型中最多只有m+n-1个约束条件方程独立。个约束条件方程独立。证明：证明：前前m个约束条件方程之和为：个约束条件方程之和为：后后n个约束条件方程之和为：
6、个约束条件方程之和为：而，而，故模型中最多只有，故模型中最多只有 m+n-1 个约束条个约束条件方程独立，即件方程独立，即系数矩阵的秩系数矩阵的秩 m+n-1。miiminjijax111 njjnjmiijbx111 njjmiiba11第第14页页 111.1111111.111.111.11.212222111211mnmmnnxxxxxxxxxm行行n行行+-第第15页页 0.0000.000.00.1111111.111.111.11.212222111211mnmmnnxxxxxxxxxm行行n行行第第16页页证明：设证明：设 Qbanjjmii 11njmiQbaxjiij,.,
7、1;,.,1,特点特点 2：必有有限最优解。：必有有限最优解。令变量令变量 iinjjinjjinjijaQQabQaQbax 111第第17页页又因为又因为jjmiijmijimiijbQQbaQbQbax 111njmiQbaxjiij,.,1;,.,1,Qbaxjiij 满足所有约束条件。满足所有约束条件。0 Qbaxjiij为可行解。为可行解。第第18页页由此可知：产销平衡的运输问题，存在可行解。由此可知：产销平衡的运输问题，存在可行解。又因为，产销平衡的运输问题的目标函数有下界又因为，产销平衡的运输问题的目标函数有下界，目标函数不会趋于，目标函数不会趋于-，由此可知，运输问题必，由此
8、可知，运输问题必有有限最优解。有有限最优解。第第19页页例例 判断题判断题运输问题是一种特殊的线性规划模型，因而求解结运输问题是一种特殊的线性规划模型，因而求解结果也可能出现下列四种情况之一：唯一最优解，无果也可能出现下列四种情况之一：唯一最优解，无穷多最优解，无界解，无可行解。穷多最优解，无界解，无可行解。（）第第20页页 表上作业法是单纯型法在求解运输问题时的一种简表上作业法是单纯型法在求解运输问题时的一种简化方法，其实质是单纯型法。化方法，其实质是单纯型法。表上作业法的步骤：表上作业法的步骤：1.找出初始基可行解：在（找出初始基可行解：在（mn）产销平衡表中给）产销平衡表中给出（出（m+
9、n-1）个数字格；）个数字格；第第21页页2.求非基变量的检验数：在表上计算空格的检验数，求非基变量的检验数：在表上计算空格的检验数，判别是否达到最优解；判别是否达到最优解；3.确定换入变量和换出变量，找出新的基可行解：确定换入变量和换出变量，找出新的基可行解：在表上用闭回路法调整；在表上用闭回路法调整；4.重复重复2、3直到最优解为止。直到最优解为止。第第22页页1.西北角法西北角法思路：优先考虑位于运输表中西北角上空格的供思路：优先考虑位于运输表中西北角上空格的供销业务。销业务。步骤：步骤：（1）在（）在（A1，B1）格中填入）格中填入x11=min(a1,b1)；第第23页页（3）若）若
10、x11=b1，则销地，则销地B1的需求已全部满足（划去该的需求已全部满足（划去该元素所在的列），且元素所在的列），且A1的可供量由的可供量由a1减少为减少为a1-b1。（4）运输表中尚未划去的部分中，左上角格子为）运输表中尚未划去的部分中，左上角格子为（A1，B2）或（）或（A2，B1）；）；（2）若）若 x11=a1，则产地，则产地 A1 的可供物品已用完（划去的可供物品已用完（划去该元素所在的行），且该元素所在的行），且 B1 的需求量由的需求量由 b1 减少为减少为 b1-a1；第第24页页（5）重复（）重复（2）和（）和（3）的过程；）的过程；（6）表中每填入一个数字，就划去一行或一列
11、，表）表中每填入一个数字，就划去一行或一列，表中共有中共有 m 行行 n 列，总共可划（列，总共可划（m+n）条直线；）条直线；（7）当表中只剩一个元素时，在表上填写这个数字，）当表中只剩一个元素时，在表上填写这个数字，并同时划去一行和一列。并同时划去一行和一列。第第25页页例：例：销地销地产地产地B1B2B3B4产量产量A13113107A219284A3741059销量销量3656第第26页页 销地销地产地产地B1B2B3B4产量产量A1311310A21928A374105销量销量3解：判断：问题为一产销平衡问题。解：判断：问题为一产销平衡问题。37496564422223366第第27
12、页页2.最小元素法最小元素法 思路：优先考虑具有最小运价的供销业务。思路：优先考虑具有最小运价的供销业务。步骤：步骤：1）对所有）对所有 i 和和 j，找出，找出 ，并将，并将 的物资量由的物资量由 供应给供应给 ；)min(00ijjicc),min(0000jijibax 0iA0jB第第28页页2）若）若 ，则产地，则产地 的可供物品已用完（划的可供物品已用完（划 去该元素所在的行），且去该元素所在的行），且 的需求量由的需求量由 减少减少为为 ；3）若）若 ，则销地，则销地 的需求已全部满足（划的需求已全部满足（划去该元素所在的列），且去该元素所在的列），且 的可供量由的可供量由 减少
13、减少为为 ；000ijiax 0iA0jB00ijab 0jb000jjibx 0jB0iA0ia00jiba 第第29页页 4）重复）重复2）和）和3）的过程；）的过程；5）表中每填入一个数字，就划去一行或一列，表）表中每填入一个数字，就划去一行或一列，表 中共有中共有 m 行行 n 列，总共可划（列，总共可划（m+n）条直线；）条直线；6）当表中只剩一个元素时，在表上填写这个数字，）当表中只剩一个元素时，在表上填写这个数字，并同时划去一行和一列。并同时划去一行和一列。最小元素法的缺点：按某一最小运价优先安排物品调最小元素法的缺点：按某一最小运价优先安排物品调运时，可能导致其他供销点对之间运
14、费很高，从而使运时，可能导致其他供销点对之间运费很高，从而使得总运费很高。得总运费很高。第第30页页例：例：销地销地产地产地B1B2B3B4产量产量A13113107A219284A3741059销量销量3656第第31页页 销地销地产地产地B1B2B3B4产量产量A1311310A21928A374105销量销量3解：判断：问题为一产销平衡问题。解：判断：问题为一产销平衡问题。37496561143633334第第32页页3.伏格尔法（伏格尔法（Vogel）罚数：针对每一个供应地或销售地，罚数：针对每一个供应地或销售地，最小运价最小运价和和次小次小运价运价之差称为该供应地或销售地的罚数；之差
15、称为该供应地或销售地的罚数；若罚数大，则不按最小运价安排运输时造成的运费损若罚数大，则不按最小运价安排运输时造成的运费损失也大，故应尽量按最小运价安排运输；若罚数小，失也大，故应尽量按最小运价安排运输；若罚数小，则不按最小运价安排运输时造成的运费损失也小。则不按最小运价安排运输时造成的运费损失也小。第第33页页思路：优先考虑罚数大的产地或销地，并按最小思路：优先考虑罚数大的产地或销地，并按最小运费安排调运。运费安排调运。步骤：步骤：1）计算每一行和每一列的次小运价和最小运价的）计算每一行和每一列的次小运价和最小运价的差值，并称为行罚数和列罚数；差值，并称为行罚数和列罚数；2）将算出的行罚数填入
16、表中右侧的行罚数栏；）将算出的行罚数填入表中右侧的行罚数栏；第第34页页3）将算出的列罚数填入表中下边的列罚数栏；）将算出的列罚数填入表中下边的列罚数栏；4）从行罚数和列罚数中选出）从行罚数和列罚数中选出最大者最大者，并选择它所在，并选择它所在行或列中的行或列中的最小元素最小元素；5）按最小元素法进行。）按最小元素法进行。伏格尔法给出的初始解比最小元素法更接近最优解。伏格尔法给出的初始解比最小元素法更接近最优解。第第35页页例：例：销地销地产地产地B1B2B3B4产量产量A13113107A219284A3741059销量销量3656第第36页页解：问题为一产销平衡问题。解：问题为一产销平衡问
17、题。计算各产地和销地的差值（罚数）：计算各产地和销地的差值（罚数）：销地销地产地产地B1B2B3B4产量产量行差值行差值A1311A292A3710销量销量列差值列差值0 1 1 2 5 1 3 7 4 9 3 6 5 6 4 6 3 0 1 2 2 1 3 5 3 0 1 2 1 2 1 3 1 7 1 3 5 2 0 3 6 2 0 2 10 8 1 2 0 0 2 第第37页页4.值得注意的问题值得注意的问题 确定初始基可行解时，若在确定初始基可行解时，若在(i,j)填入数字时（不是最填入数字时（不是最后一个数字格），出现后一个数字格），出现 Ai 处的余量处的余量=Bj 处的余量，处的
18、余量，则在填入该数字后，同时划去一行和一列，并在所则在填入该数字后，同时划去一行和一列，并在所划去的一行或一列中选取某个空格填入数字划去的一行或一列中选取某个空格填入数字 0。此时表示问题出现了退化现象。此时表示问题出现了退化现象。第第38页页例：例：销地销地产地产地B1B2B3B4产量产量A1311457A277384A3121069销量销量3656第第39页页解：最小元素法。解：最小元素法。销地销地产地产地B1B2B3B4产量产量A13A27784A3106销量销量36139 6266345 1417 656110第第40页页形式的变量的集合称为一个闭回路。形式的变量的集合称为一个闭回路。
19、介绍两种求空格（空格对应着非基变量）检验数的介绍两种求空格（空格对应着非基变量）检验数的方法：方法：1.闭回路法（闭回路法（cycle method）（1）关于闭回路的基本理论）关于闭回路的基本理论 132222111,.,jijijijijijisssxxxxxx定义：凡能排成定义：凡能排成第第41页页 132222111,.,jijijijijijisssxxxxxx 132222111,.,jijijijijijisssPPPPPP性质性质 1 构成闭回路的变量组如下构成闭回路的变量组如下 其对应的列向量为其对应的列向量为 是线性相关的。是线性相关的。第第42页页 010)(10行行）（
20、第第行行第第jmiPij=证明：运输问题中，变量证明：运输问题中，变量 xij 的系数列向量为的系数列向量为第第43页页如果变量组如果变量组 组成一组成一闭回路，则这组闭回路中变量的系数列向量满足如闭回路，则这组闭回路中变量的系数列向量满足如下关系：下关系：从而由线性相关的定义可知：从而由线性相关的定义可知：是线性相关的。是线性相关的。132222111,.,jijijijijijisssxxxxxx0.132222111 jijijijijijisssPPPPPP 132222111,.,jijijijijijisssPPPPPP第第44页页性质性质 2 运输问题中，运输问题中，s 个变量组
21、个变量组对应的列向量线性无关的充要条件是：对应的列向量线性无关的充要条件是：中不含闭回路。中不含闭回路。证明：略。证明：略。ssjijijijijixxxxx,.,44332211 ssjijijijijixxxxx,.,44332211第第45页页推论推论 1 若若 线性相关，线性相关，则则 中必含闭回路。中必含闭回路。推论推论 2 运输问题的基可行解中基变量组不含有闭回运输问题的基可行解中基变量组不含有闭回路。路。ssjijijijijiPPPPP,.,44332211 判断运输问题的解是否为基解的方法：判断判断运输问题的解是否为基解的方法：判断 m+n-1个基变量是不是含有闭回路。个基变
22、量是不是含有闭回路。ssjijijijijixxxxx,.,44332211第第46页页例例 判断题判断题在运输问题中，只要任意给出一组含在运输问题中，只要任意给出一组含(m+n-1)个非零个非零的的 xij，且满足，且满足 ，就可，就可以作为一个初始基可行解。以作为一个初始基可行解。injijax 1jmiijbx 1（）必须不含闭回路！必须不含闭回路！第第47页页 销地销地产地产地B1B2B3B4产量产量A1311532107A21392184A376410359A4356273销量销量3956例例 判断下列可行解是否能作为表上作业法求解时的初始解。判断下列可行解是否能作为表上作业法求解时
23、的初始解。第第48页页中含有闭回路。中含有闭回路。变量组变量组 41343224221413,xxxxxxx 41343224221413,PPPPPPP线性相关。线性相关。说明说明第第49页页 41343224221413,xxxxxxx不是一组基解。不是一组基解。说明说明不能作为表上作业法求解时的初始解。不能作为表上作业法求解时的初始解。第第50页页 销地销地产地产地B1B2B3B4产量产量A1311532107A23192184A376410359销量销量3656例例 判断下列可行解是否能作为表上作业法求解时的初始解。判断下列可行解是否能作为表上作业法求解时的初始解。第第51页页中不含有
24、闭回路。中不含有闭回路。变量组变量组线性无关。线性无关。说明说明 343224211413,xxxxxx 343224211413,PPPPPP第第52页页是一组基解。是一组基解。说说 明明 343224211413,xxxxxx可以作为表上作业法求解时的初始解。可以作为表上作业法求解时的初始解。第第53页页性质性质 3 运输问题中，设变量运输问题中，设变量 （s=m+n-1）是基变量，是基变量，y 是一个非基变量，则在变量组是一个非基变量，则在变量组 中，存在中，存在唯唯一一的闭回路。的闭回路。ssjijijijijixxxxx,.,44332211 ssjijijijijixxxxxy,.
25、,44332211第第54页页证明证明：反证法。由性质：反证法。由性质 2 可知：可知：ssjijijijijixxxxxy,.,44332211如果存在如果存在 2 条不同的闭回路，则这条不同的闭回路，则这 2 条闭回路中都必须含有条闭回路中都必须含有 y。中存在闭回路。中存在闭回路。第第55页页由此可得由此可得 Py 可以用两种不同的方式表示可以用两种不同的方式表示的线性组合。的线性组合。ssjijiPP,.,11 ssjijiPP,.,11这与这与 为线性无关发生矛盾（线性表示的含为线性无关发生矛盾（线性表示的含义）。证明完毕。义）。证明完毕。第第56页页（2）结论）结论 数字格：对应基
26、变量；数字格：对应基变量；空空 格：对应非基变量。格：对应非基变量。利用西北角法、最小元素法、伏格尔法得出的利用西北角法、最小元素法、伏格尔法得出的运输问题的初始基可行解中不含有闭回路，即运输问题的初始基可行解中不含有闭回路，即数字格组不成闭回路。（由数字格组不成闭回路。（由性质性质 2 可知）可知）第第57页页根据西北角法、最小元素法、伏格尔法求初根据西北角法、最小元素法、伏格尔法求初始调运方案的过程可知，其数字格组不成闭始调运方案的过程可知，其数字格组不成闭回路。回路。又数字格数量满足又数字格数量满足 m+n 1 的数量要求，故的数量要求，故由上述三种方法得出的初始调运方案，为基由上述三种
27、方法得出的初始调运方案，为基可行解。可行解。第第58页页从任一空格出发，寻找闭回路，要求该闭回路从任一空格出发，寻找闭回路，要求该闭回路上除了出发位置为空格外，其他位置均为数字上除了出发位置为空格外，其他位置均为数字格，则这样的闭回路是存在的且是唯一的。格，则这样的闭回路是存在的且是唯一的。（由（由性质性质 3 可知）可知）方法：从某一空格出发，用水平或垂直线向前方法：从某一空格出发，用水平或垂直线向前划，当碰到一数字格时转划，当碰到一数字格时转 90 度，继续向前，度，继续向前，直到回到起始空格为止。直到回到起始空格为止。第第59页页 销地销地产地产地B1B2B3B4产量产量A1311433
28、107A23191284A376410359销量销量3656第第60页页 销地销地产地产地B1B2B3B4产量产量A1311433107A23191284A376410359销量销量3656第第61页页 销地销地产地产地B1B2B3B4产量产量A1311433107A23191284A376410359销量销量3656第第62页页 销地销地产地产地B1B2B3B4产量产量A1311433107A23191284A376410359销量销量3656第第63页页 销地销地产地产地B1B2B3B4产量产量A1311433107A23191284A376410359销量销量3656第第64页页 销地销
29、地产地产地B1B2B3B4产量产量A1311433107A23191284A376410359销量销量3656第第65页页（3）检验数的计算方法）检验数的计算方法 利用闭回路计算空格检验数：闭回路中利用闭回路计算空格检验数：闭回路中奇数次顶点奇数次顶点的运价总和的运价总和与与偶数次顶点的运价总和偶数次顶点的运价总和之差，称为对之差，称为对应于空格的检验数。应于空格的检验数。第第66页页 销地销地产地产地B1B2B3B4产量产量A1311433107A23191284A376410359销量销量3656第第67页页 销地销地产地产地B1B2B3B4产量产量A1311433107A23191284
30、A376410359销量销量3656第第68页页 销地销地产地产地B1B2B3B4产量产量A1311433107A23191284A376410359销量销量3656第第69页页（4）闭回路法的缺点）闭回路法的缺点 用闭回路法判定一个运输方案是否为最优方案，需用闭回路法判定一个运输方案是否为最优方案，需要找出所有空格的闭回路，并计算出其检验数。当要找出所有空格的闭回路，并计算出其检验数。当空格数目很大时，计算检验数的工作十分繁重。空格数目很大时，计算检验数的工作十分繁重。第第70页页2.位势法或对偶变量法（位势法或对偶变量法（dual variable method）u1,u2,um：表示前：
31、表示前 m 个约数条件等式对应的个约数条件等式对应的对偶变量；对偶变量；v1,v2,vn：表示后：表示后 n 个约数条件等式对应的对个约数条件等式对应的对偶变量。偶变量。第第71页页即有对偶变量为：即有对偶变量为：Y=(u1,u2,um,v1,v2,vn)则运输问题的对偶问题为：则运输问题的对偶问题为：的的符符号号不不限限vunjmicvuvbuazijjinjjjmiii,.,1;,.,1,max11第第72页页 0,.,1,.,1,min1111ijjmiijinjijminjijijxnjbxmiaxxcz 的的符符号号不不限限vunjmicvuvbuazijjinjjjmiii,.,1
32、;,.,1,max11原问题原问题对偶问题对偶问题第第73页页设设 为原问题决策变量为原问题决策变量 xij 的检验数的检验数ijijijBijijYPcPBCc 1 ij 因为因为 Y=(u1,u2,um,v1,v2,vn)010)(10行行）（第第行行第第jmiPij第第74页页(u1,u2,um,v1,v2,vn)0 10)(10行行）（第第行行第第jmi ijYP第第75页页故故由西北角法、最小元素法或伏格尔法已经得出运输问由西北角法、最小元素法或伏格尔法已经得出运输问题的一个基可行解，即题的一个基可行解，即 ，s=m+n-1，而基变量的检验数，而基变量的检验数 ，从而可得：，从而可得
33、：)(jiijijvuc ssjijijijijixxxxx,.,443322110 ij 第第76页页该方程组有该方程组有 m+n-1 个方程，个方程，m+n 个变量，变个变量，变量数比方程数多一个，故解不唯一。方程组的解量数比方程数多一个，故解不唯一。方程组的解称为称为位势位势。sssjijsijijicvucvu.1111第第77页页例：例：销地销地产地产地B1B2B3B4产量产量A13113107A219284A3741059销量销量3656第第78页页 销地销地产地产地B1B2B3B4产量产量A13113107A219284A3741059销量销量3656解：（解：（1）利用最小元素
34、法可得出初始可行解为：）利用最小元素法可得出初始可行解为：433163第第79页页 销地销地产地产地B1B2B3B4产量产量uiA13113107A219284A3741059销量销量3656vj433163（2）计算位势值和检验数）计算位势值和检验数 0310-12-59(1)(2)(1)(-1)(10)(12)第第80页页步骤：步骤：1.若表中空格处的检验数均非负，则当前解已经达若表中空格处的检验数均非负，则当前解已经达到最优；到最优；2.若表中存在检验数为负的空格，则从该空格出发，若表中存在检验数为负的空格，则从该空格出发，寻找闭回路，并使得该闭回路上除了出发顶点为空寻找闭回路，并使得该
35、闭回路上除了出发顶点为空格外，其它顶点均为数字格；格外，其它顶点均为数字格；第第81页页3.确定换出变量：在闭回路上的确定换出变量：在闭回路上的偶数顶点偶数顶点中寻找中寻找运运输量最小输量最小的顶点，并以该顶点所对应的变量为的顶点，并以该顶点所对应的变量为换出换出变量变量；第第82页页4.迭代：在该闭回路上所有迭代：在该闭回路上所有奇数顶点奇数顶点处的运输量处的运输量增增加加这一数值，所有这一数值，所有偶数顶点偶数顶点处的运输量处的运输量减去减去这一数这一数值，从而得出一新的运输方案。值，从而得出一新的运输方案。第第83页页例：例：销地销地产地产地B1B2B3B4产量产量A13113107A2
36、19284A3741059销量销量3656第第84页页解：（解：（1）利用最小元素法求出初始基可行解；）利用最小元素法求出初始基可行解；（2）利用位势法计算空格处的检验数）利用位势法计算空格处的检验数；（3）解的改进）解的改进。销地销地产地产地B1B2B3B4产量产量uiA1(1)3(2)114331070A231(1)91284-1A3(10)764(12)10359-5销量销量3656vj29310(-1)+1+1-1-1第第85页页 销地销地产地产地B1B2B3B4产量产量uiA1311532107A23192184A376410359销量销量3656vj0310-2-539(0)(2)
37、(2)(1)(9)(12)第第86页页1.无穷多最优解的情况：当迭代到运输问题的最优无穷多最优解的情况：当迭代到运输问题的最优解时，如果某非基变量的检验数等于解时，如果某非基变量的检验数等于 0，则说明该，则说明该运输问题有无穷多最优解；运输问题有无穷多最优解；第第87页页2.退化问题的情况：退化问题的情况：（1）第一种情况：确定初始基可行解时，若在）第一种情况：确定初始基可行解时，若在(i,j)填入数字时（不是最后一个数字格），出现填入数字时（不是最后一个数字格），出现 Ai 处的处的余量余量=Bj 处的余量，则在填入该数字后，要同时划处的余量，则在填入该数字后，要同时划去一行和一列，为了使
38、运输表中有去一行和一列，为了使运输表中有(m+n-1)个数字格，个数字格，这时需要添一个这时需要添一个 0，它的位置可在对应同时划去的，它的位置可在对应同时划去的那行或那列的任一空格处。那行或那列的任一空格处。第第88页页（2）第二种情况：在求出所有空格的检验数后，对）第二种情况：在求出所有空格的检验数后，对解进行改进时，从检验数为负的空格出发，寻找闭解进行改进时，从检验数为负的空格出发，寻找闭回路，若闭回路的偶数顶点上运输量最小的顶点有回路，若闭回路的偶数顶点上运输量最小的顶点有两个，则任选个变量为换出变量，令一个变量仍保两个，则任选个变量为换出变量，令一个变量仍保留为基变量，只是该基变量为留为基变量，只是该基变量为 0。
