第四章线性规划选读.ppt

销地 产地 B1 B2 B3 B4 产量 A1 A2 A3 3 1 7 4 9 销量 3 6 5 6 表5.3.6 销地 产地 B1 B2 B3 B4 A1 A2 A3 11 9 4 3 2 10 10 8 5 表5.3.7 第三步 ，按照上述方法直到单位运价表上的所有元素被划去为止。最后在产销平衡表上得到一个调运方案，即初始基可行解，见表5.3.8。 销地 产地 B1 B2 B3 B4 产量 A1 A2 A3 3 6 4 1 3 3 7 4 9 销量 3 6 5 6 表5.3.8 ⑵伏格尔法的步骤是： 第一步：在表5.3.2中分别计算出各行、各列的最小运费和次最小运费的差额，并填入该表的最右列和最下行，见表5.3.9。 销地 产地 B1 B2 B3 B4 行差额 A1 A2 A3 3 1 7 11 9 4 3 2 10 10 8 5 0 1 1 列差额 2 5 1 3 表5.3.9 第二步：从行或列差额中选出最大者，选择它所在行或列中的最小元素。在表5.3.9中，可确定A3的产品应首先供应B2，得表5.3. 10。将单位运价表中的列的数字划去，得表5.3.11。 表5.3.10 销地 产地 B1 B2 B3 B4 产量 A1 A2 A3 6 7 4 9 销量 3 6 5 6 销地 产地 B1 B2 B3 B4 A1 A2 A3 3 1 7 3 2 10 10 8 5 表5.3.11 第三步：对表5.3.11中余下的元素再分别计算出各行、各列的最小运费和次最小运费的差额，重复第一、第二步，直到给出初始基可行解为止。初始基可行解列于表5.3.12。 表5.3.12 销地 产地 B1 B2 B3 B4 产量 A1 A2 A3 3 6 5 2 1 3 7 4 9 销量 3 6 5 6 伏格尔法给出的初始基可行解更接近最优解。本例中用伏格尔法给出的初始基可行解就是最优解。 ⑶用闭回路法判别检验 闭回路法计算检验数的经济解释为：在已给出初始基可行解的表中，可从任一空格出发，如（A1, B1），若让A1的产品调运1吨给B1，为了保持产销平衡，就要依次进行调整：就构成了以（ A1, B1）空格为起点，其它为数字格的闭回路，如表5.3.13中的虚线所示。闭回路各顶点所在格的右上角数字是单位运价。 表5.3.13 调整的方案使运费增加 将“1”填（A1, B1）格中，这就是检验数。按上述办法，可找出所有空格的检验数，见表5.3.14。当检验数还有负数时，需要对原方案进行改造。 表5.3.14 ⑷用位势法检验 第一步：按最小元素法给出表5.3.8的初始基可行解，作表5.3.15。在对应表5.3.8的数字格处填入单位运价。 销地 产地 B1 B2 B3 B4 A1 A2 A3 1 4 3 2 10 5 表5.3.15 第二步：在上表增加一行一列，在列中填入 ，在行中填入 ，得表5.3.16。 表5.3.16 销地 产地 B1 B2 B3 B4 A1 A2 A3 1 4 3 2 10 5 0 -1 -5 2 9 3 10 首先令u1=0,然后按 可确定所有和的数值。 第三步：按 计算所有空格的检验数，特设计计算表5.3.17。 表5.3.17 ⑸ 改进的方法——闭回路调整法 在表5.3.17中，(A2, B4)为调入格，以此格为出发点，作一闭回路。 表5.3.18 格的调入量 是选择闭回路上具有（-1）的数字格中的最小者即 ，然后，按闭回路上的正、负号，加、减此值得到调整方案，如 表5.3.21所示。再用闭回路法或位势法求各空格的检验数，得表5.3.22。在表5.3.22中，因为所有检验数都非负，故得最优解，这时，得到最小运费为85（元）。 销地 产地 B1 B2 B3 B4 产量 A1 A2 A3 3 6 5 2 1 3 7 4 9 销量 3 6 5 6 销地 产地 B1 B2 B3 B4 A1 A2 A3 0 9 2 2 1 12 表5.3.21 表5.3.22 三、产销不平衡的运输问题的求解方法 前面求解运输问题的表上作业法，是以产销平衡为前提的 ，即 实际情况需要把产销不平衡的问题化成产销平衡的问题。 ★当产大于销 运输问题的数学模型为求 使 且满足： 考虑多余的物资在哪一个产地就地储存的问题。设 是产地Ai的储存量，于是有： 当 时