第六讲 杂胨输问题 .pptVIP

运输问题及其数学模型 运输问题及其数学模型（2） 运输问题及其数学模型（3） 运输问题及其数学模型（4） 运输问题及其数学模型（5） 3.2 表上作业法 确定初始基可行解 确定初始基可行解（2） 最小元素法 最小元素法例题 最小元素法例题（2） 最小元素法例题（3） 最小元素法例题（4） 2.伏格尔法（Vogel）。 最小元素法给定初始调整方案是以局部观点考虑运价最低者优先的原则。这可能造成整体的不合理。因为可能存在这样的情形：某单位运价在整个单位运价表中可能并不是最低的，但是它在所在行（或所在列）中是最低运价，而且它与同行（或同列）中的次最低运价相差非常显著。因此就该行（或该列）而言，如果我们不慎采用了次最低运价，而不是最低运价，那么总运费就会惩罚性地增加。我们通常把每行或每列的次最低运价与最低运价之差额称为罚金成本（Penalty cost）。 为了避免在总运费总增加过多的罚金成本。伏格尔法确定初始基本可行解的基本思路是：罚金成本最高的行或列中运价最低者优先考虑。其基本步骤为： ① 计算出每行(列)的罚金成本，并填入附加的最右列(最下行)从所有的罚金成本中找出最高值。选择它所在行(列)的最低运价。比较最小运价对应的加工厂的日产量和销售地的日销量的大小，确定第一笔供销关系。 1.在确定初始调运方案过程中，可能出现最低单位运价对应的产地的产量和销地的销量恰好相等的情形。此时在运输表中填入一个数字后，必须同时划去产地所在行和销地所在列，这和每填入一个数字只划一条直线的基本原则相违背（最后一个数字除外）。这时我们称运输问题出现了退化。 　　因为运输问题的基本解中基变量的个数必须是m＋n－1个，此时需要添加一个“0”调运量，出现了数字为0的数字格只是说明在初始基可行解中有一个基变量为零。即该初始基可行解是退化解。通常的做法是：当同时划去某产地行和某销地列时，在划去的行、列中选择运费较小的空格填上“0”。 2.在伏格尔法中，若出现两个或者以上相同差额时，可任意选取其中一个先进行调运。 3.用最小元素法和伏格尔法给出的初始调运方案均为运输问题的一个基可行解。 4.一般情况下，伏格尔法给出的初始基可行解比用最小元素法给出的初始基可行解更接近最优解。 回顾利用单纯形法求解线性规划的步骤： 　 在求出基可行解以后，就必须检验该基可行解是否为最优解，为此给出一个检验标准。在求极大化的线性规划时，若初始基可行解所有非基变量检验数 　　　　　（j为非基变量下标） 　　则初始基可行解为最优解，停止计算。否则将进行基变换，对初始基可行解进行改进。 　　运输问题初始基可行解的最优性检验也必须设定一个标准。由于运输问题目标函数是求极小化问题，因此检验标准是计算所有非基变量(空格)的检验数 (i,j为非基变量下标)． 如果所有非基变量检验数 　　 则初始基可行解为最优解。 　　下面介绍两种计算检验数的方法。 利用闭回路的概念计算非基变量的检验数，以判别基可行解是否为最优解。 定义：若运输表中的一组变量经过适当排列以后，可写成如下形式： 其中 互不相同， 　　 互不相同。 　那么这些变量集合就构成了一个闭回路。其中的每一个变量称为这个闭回路的顶点。 　　由闭回路定义可知，若用水平和垂直的线段将这个变量集合中处于同行同列的相邻顶点相连接。就能构成一个封闭的回路。而且该闭回路的每一条边（水平或垂直）上只包含两个顶点。且都处于每条边的两个端点上。如下表所示： 表中变量集合　　　　　　　,变量集合 　　 　　　 变量集合　　　　　　　　　 等均构成闭回路． 　性质 定理1 运输问题模型中,系数矩阵A的一组系数列向量 线性无关的充分必要条件是这组向量所对应的变量 不包含闭回路。 本定理证明从略。 　　变量组 　　　　　 不包含闭回路的含义是该变量组中任何一个变量子集合均不构成闭回路。　 　由定理１可得如下推论： 　推论1.若一组变量包含闭回路，那么这组变量所对应的系数列向量线性相关。 　推论2.m＋n－1个变量构成基可行解的基变量的充分必要条件是它们不包含闭回路。 定理2 若变量组　　　　　 (s=m+n-1)是运输问题基可行解的基变量，　是一个非基变量，则变量组 中存在包含　　的唯一闭回路。 　由定理2可知，从任何一个非基变量对应的空格出发，用水平或垂直线向前划，遇到某个基变量对应的数字格，试转90o后继续前进，最后总能找到一条闭回路，回到起始空格。 　闭回路法: 　　设　　是一个非基变量，根据定理2，在运输表中可以