运筹学三运输问题(新)a.ppt

作业：P99~100 3.1 表3-35 3.2 3.3第三章 运输问题 第一节 运输问题的数学模型  解：设为xij表示从产地为Ai给销地为Bj的运输量。则有 运输问题的系数矩阵 下面先讨论产销平衡的运输问题的解法，对产销不平衡的运输问题，只需化为产销平衡问题，即可求解。 定理1. 运输问题的数学模型必有最优解。定理2. 若运输问题中产量和销量皆为整数，则必有整数最优解。 例1. 已知运输问题见表 初始调运方案见下，总运费为z =86 特殊情况：若运价表为: 2. 西北角法 在单位运价表中的左上角（西北角）处确定供销关系，划去满足的行或列，以此类推，直至给出一个完整的调运方案。对例1，已知单位运价表为 3.vogel法 从运价表上分别找出每行与每列的最小的两个元素之差，再从差值最大的行或列中找出最小运价确定供需关系和供需数量，划去运价表中对应的行或列，然后重复上述步骤。 2-2 最优性检验 1. 进行最优性检验的闭回路法 闭回路：在调运方案中，从一个空格处出发，以有数字格为顶点（或拐点），沿水平或垂直连线又回到空格处所形成的封闭回路。 这里定义：闭回路上空格顶点的编号为0，其余按1，2，3...类推。闭回路的可能形状： σ11=c11 -c13+c23-c21=3-3+2-1=1σ31=7-1+2-3+10-5=10...... 2-3 调整方案，然后转2-2令调整量θ=闭回路上奇数顶点的最小运量。调整方法：闭回路上偶数顶点运量 + θ  闭回路上奇数顶点运量 - θ 因所有检验数σij ≥0，故得最优方案。Minz=85 作业 P99 3.1 表3-36（位势法）P101 3.4 3.52. 进行最优性检验的位势法 运输问题的对偶问题数学模型为 已知运输问题的基变量有m+n-1个，因此，上式是一个具有m+n个变量，m+n-1个等式的方程组，由于变量数多于方程数，故有无穷多解。 对以上问题，可先选定任意一个变量的取值，然后就可计算出其它变量的值。(变量ui也称为行位势，vj称为列位势。)有了ui和vj，就可计算非基变量的检验数 σij = cij – (ui+vj )。 对例1，可先令v1 =1，根据cij 就可求出其它的ui，vj ，从而可计算出检验数。 例 ：求解下列运输问题 解: 初始方案 一次调整后方案 2-4 表上作业法总结1. 总结2. 求最大值问题 例：求解下列运输问题 第三节 产销不平衡的运输问题及应用 2.当供不应求时，运输问题的数学模型可写成下式，加松弛变量化为标准形式 作业 P103 3.7 3.8(a)例2. 已知见表：试决定总运费最少的调运方案。 最优方案见下表，最小运费为 min z = 35 例3. 已知见表，试决定使总运费最省的化肥调运方案。 最优调运方案见下表，最小运费为min z = 2460 例4. 转运问题 表上作业法与单纯形法1.确定初始基本可行解2.最优性检验3.确定换入变量 4.确定换出变量 销 地 产 地 B1 B2 B3 B4 B5 产 量 A1 A2 A3 25 15 10 60 0 20 70 ? 50 60 90 销 量 ? 25 35 60 10 70 ? 200 检验表 销 地 产 地 B1 B2 B3 B4 B5 ui A1 A2 A3 10 15 (15) 20 (35) (0) (15) 15 30 (15) (0) 35 (15) (15) 25 ? 0 10 20 vj ? 10 15 5 20 5 ? 因所有检验数都大于等于零