9运输问题的特殊解法详解.ppt

运输问题——表上作业法 运输问题——表上作业法 运输问题——表上作业法 运输问题——表上作业法 运输问题——表上作业法 运输问题——表上作业法 运输问题——表上作业法 运输问题——表上作业法 第七章 运输问题的特殊解法 典型背景——单一物资运输调度问题 设某种物品有: m个产地： 产量： n个销地： 销量： 从产地 到销地 的单位运价是 。 求总运费最小的调度方案。 决策变量 表示由 到 的物品数量。 销地 产地 销量 产量 产销平衡问题——总产量=总销量 即 产销不平衡问题——总产量=总销量 产销平衡问题的数学模型 设 （1）运输问题有可行解，并且有最优解 （2）运输问题中系数矩阵A的秩等于m+n-1 凡能排成如下形式 （其中i1，i2，···，is互不相同，j1，j2，···，js互不相同）的一组变量称为一个闭回路，称上述各变量为闭回路的顶点。 B1 B2 B3 B4 A1 X11 X12 X13 X14 A2 X21 X22 X23 X24 A3 X31 X32 X33 X34 第二节 运输问题的 表上作业法 由上节介绍运输问题的数学模型及其约束方程组的系数矩阵结构的特殊性，本节将由此给出运输问题的比单纯形法更为简便的求解方法—表上作业法。 例1：设物资有A1，A2，A3三个产地，B1，B2，B3，B4四个销地，已知运价表与平衡表见下表，求总运费最少的调运方案？ 运输问题——表上作业法 B1 B2 B3 B4 发量 A1 X11 X12 X13 X14 3 A2 X21 X22 X23 X24 5 A3 X31 X32 X33 X34 7 收量 6 3 2 4 15 2 5 1 7 5 9 2 6 3 4 8 9 最小元素法思路： 从单价中最小运价确定供应量，逐步次小，直至得到m+n-1个数字格。 运输问题——表上作业法 B1 B2 B3 B4 发量 A1 3 A2 5 A3 7 收量 6 3 2 4 15 2 5 1 7 5 9 2 6 3 4 8 9 0 1 5 1 0 4 0 3 2 0 1 1 2 2 0 2 0 0 书p169第4题（1） 运输问题——表上作业法 位势法 思路：计算空格（非基变量）的检验数 运输问题——表上作业法 设给定了一组基础可行解，对应基变量为 其中r=m+n-1。现在引进m+n个未知量，对于特定的调运方案的每一行给出一个因子 ui（称为行位势），每一列给出一个因子vj（称为列位势）。 如何求检验数？ 使对于目前解的每一个基变量xij 有cij= ui + vj，这里的ui 和 vj可正、可负也可以为零。那么任一非基变量 xij的检验数就是 运输问题——表上作业法 第一步：把方案表中基变量格填入其相应的运价并令u1=0 ；让每一个基变量xij都有cij= ui + vj ，可求得所有的位势，如表所示。 B1 B2 B3 B4 A1 1 2 A2 5 A3 1 2 4 2 5 1 7 5 9 2 6 3 4 8 9 解得 运输问题——表上作业法 第二步：利用 计算各非基变量xij 的检验数。 在负检验数中找出最小的检验数，该检验数所对应的变量即为入基变量。 定义：非基变量增大的数值称为调整变量，记为δ，调整数为闭回路中第奇数次拐角点中最小的调运量，即 δ=闭回路中奇数次拐角点的最小调运量 调整数δ确定后，把闭回路中第奇数次拐角点的数各减去调整数δ，第偶数次拐角点的数各加上调整数δ，得到新的调运方案。在进行判别、调整。 运输问题——表上作业法 ，故选择x23为入基变量。 B1 B2 B3 B4 发量 A1 5 5 3 A2 5 -1 4 5 A3 5 7 收量 6 3 2 4 15 2 5 1 7 5 9 2 6 3 4 8 9 5 1 4 2 1 2 然后闭回路第奇数次拐角点各数减去调整数2，第偶数次拐角点加上调整数2，便得到新的调运方案 B1 B2 B3 B4 发量 A1 5 5 3 A2 5 4 5 A3 5 7 收量 6 3 2 4 15 2 5 1 7 5 9 2 6 3 4 8 9 3 3 4 2 3 0 新的调运方案s=2 ×3+3 ×1+2 ×2+