运筹学3.运输问题.ppt

第三章 运输问题 第一节 运输问题的数学模型 第二节 表上作业法 第三节 产销不平衡的运输问题 第四节 应用举例 第一节 运输问题的数学模型 二、运输问题的一般数学模型 产量约束：由某一产地运往各个销售地的物品数 量之和等于该产地的产量。 产大于销 产小于销（销大于产） 定理1 运输问题的数学模型必有最优解。 首先，运输问题一定有可行解；其次，任何单位运价cij≥0，从而对于任一可行解，必有目标函数值大于或等于零，即目标函数有下界。 所以，求解运输问题时，不需要进行无最优解的判别。 三、变量xij的系数列向量的特征 四、闭回路 第二节 表上作业法 表上作业法步骤：初始方案、最优性检验、改进方案 一、初始方案的确定 1.最小元素法 2.伏格尔法 二、最优性检验 1.闭回路法 2.位势法 三、改进方案 在闭回路内改进 二、初始基可行解的确定 三、求检验数并进行最优解的判定 位势法的理论依据（互补松弛定理） 位势法的理论依据 运输问题 位势法的步骤 对于每一个基变量（数字格）都按照公式 ui+vj=cij 列出一个位势方程，形成位势方程组（m+n-1个）； 任意决定其中一个位势的数值，然后求出其他位势的数值； 按照公式 计算非基变量（空格处）的检验数（m×n-(m+n-1)个）。 四、调整 五、典型运输问题解题步骤示例 表上作业法的步骤： （1）编制调运表（产销平衡表、单位运价表） （2）在调运表上求出初始基可行解 （3）用位势法或闭回路法计算非基变量的检验数，若所有非基变量的检验数均大于等于0，则已得到问题的最优解 （4）选取小于0的检验数中的最小者所对应的非基变量作为进基变量，用闭回路法进行基可行解的转换，得到新的基可行解，转入步骤（3）。 可能出现的几种情况 （1）无穷多最优解 某一个非基变量（空格处）的检验数为0； 可能出现的几种情况 （2）退化 同时划去一行和一列； 在用闭回路法调整时，同时有两个或两个以上的偶数顶点具有最小值 第三节 产销不平衡的运输问题 二、产销不平衡问题的处理 二、产销不平衡问题的处理 第四节 应用举例 7 4 10 20 6 5 6 3 bj 5 8 10 9 4 7 ai 1 3 9 11 2 3 A3 A2 A1 B4 B3 B2 B1 销地 产地 ③ ④ ① ⑥ ③ ③ 7 4 10 20 6 5 6 3 bj 5 8 10 9 4 7 ai 1 3 9 11 2 3 A3 A2 A1 B4 B3 B2 B1 销地 产地 ③ ④ ① ⑥ ③ ③ 7 4 10 20 6 5 6 3 bj 5 8 10 9 4 7 ai 1 3 9 11 2 3 A3 A2 A1 B4 B3 B2 B1 销地 产地 ③ ④ ① ⑥ ③ ③ 2.位势法 例6 由最小元素法得出初始解,如下表 3）行势、列势可不唯一，但检验数是一致的。 7 4 10 20 6 5 6 3 bj 5 8 10 9 4 7 ai 1 3 9 11 2 3 A3 A2 A1 B4 B3 B2 B1 销地 产地 ③ ④ ① ⑥ ③ ③ 0 ), ( ) 2 = σ + - = σ ij j i ij ij v u c 数字格 检验数的计算：空格 设B为一可行基，则相应的基可行解的各变量的检验数为 运输问题的对偶问题 由对偶理论有 Y=CBB-1 基变量的检验数等于0 （I：基变量下标集） 位势法的计算过程 令u1=0 按ui+vj=cij相继确定其他数字格的ui和vj 计算空格的检验数。如σ 11=3-(0+2)=1 因为σ24=-10,因而该问题至此尚未达到最优解. 7 4 10 5 8 10 1 3 9 11 2 3 A3 A2 A1 B4 B3 B2 B1 销地 产地 ③ ④ ① ⑥ ③ ③ ui vj 0 3 10 -1 -5 2 9 1 2 1 -1 10 12 从最小负检验数所对应的空格进行调整 例7 对由最小元素法得出的初始解进行调整 调整方法： 1）找出负检验数所在空格处的闭回路 2）在闭回路上找到偶数点所对应的基变量的最小值 再按调整后的解由位势法计算空格的检验数 7 4 10 5 8 10 1 3 9 11 2 3 A3 A2 A1 B4 B3 B2 B1 销地 产地 ③ ④ ① ⑥ ③ ③ 1 2 1 -1 10 12 ⑤ ① ② x23 x14 x24 x13 3）以此最小值θ为调整量，在奇数格加上该调整量，在偶数格上减去该调整量 换入变量：x24 换出变量：x23 1.由最小元素法求得初始基可