[理学]3运输问题.ppt

第三章 运输问题 — 数学模型及其解法 第一节 运输问题的数学模型 二、运输问题的一般数学模型 有m个产地生产某种物资，有n个地区需要该类物资 3、左上角法（西北角法） 从 x11开始分配，从西北向东南方向逐个分配 第四节 应用举例 2. 由位势法求检验数 ③ ④ ① ⑥ ③ ③ ui vj 令u1=0 0 按ui+vj=cij相继确定其他数字格的ui和vj 3 10 -1 -5 2 9 计算空格的检验数。如λ11=3-(0+2)=1 1 2 1 -1 10 12 因为λ11=-10,因而该问题至此尚未达到最优解. 3. 从最小负检验数所对应的空格进行调整 调整方法： ③ ④ ① ⑥ ③ ③ 1 2 1 -1 10 12 1）找出闭回路 2）使最小负检验数所对应的空格达到最大的调整量1 ② ⑤ ① ③ ⑤ ① ⑥ ③ ② ui vj 0 3 10 -2 -5 3 9 0 2 2 9 12 令u1=0 按ui+vj=cij相继确定其他数字格的ui和vj 计算空格的检验数。如λ11=3-(3+0)=0 1 因为所有的λij≥0,至此该问题已经达到最优解. 4. 再按调整后的解由位势法计算空格的检验数 六、位势法的理论依据（互补松弛定理） 第三节 产销不平衡的运输问题 一、 原理 证明： 结论： 二、产销不平衡问题的处理 例10 产销不平衡问题 （书P91例2） 在产销平衡表中增加一个假想的化肥厂D，年产量为50万吨；将需求分两种情况的地区，实际按两个地区看待。 这样可将该问题化为产销平衡问题： 根据表上作业法计算，可得该问题的最优方案，如下表： 例11 （书P93例3） 设ai表示第i季度的生产能力，bj表示第j季度的合同供应量，建立数学模型表示为： * * 一、数学模型 例1 设xij表示产地 i 运往销地 j 的物资量，wij表示对应的单位运费，则我们有运输问题的数学模型如下： 令a1, a2, …, am表示各产地产量， b1, b2, …, bn表示各销地的销量， 一般满足产销平衡：?ai=?bj 三、变量xij的系数列向量的特征 例2 在例1中，运输问题的系数矩阵为： 2. 一般情况下,运输问题的决策变量xij的系数列向量为: 四、闭回路 概念 ③ ④ ① ⑥ ③ ③ 例3 1) 数字格 2) 空格 3) 闭回路 ③ ④ ① ⑥ ③ ③ ③ ④ ① ⑥ ③ ③ ③ ④ ① ⑥ ③ ③ ③ ④ ① ⑥ ③ ③ ③ ④ ① ⑥ ③ ③ ③ ④ ① ⑥ ③ ③ ③ ④ ① ⑥ ③ ③ ③ ④ ① ⑥ ③ ③ ③ ④ ① ⑥ ③ ③ ③ ④ ① ⑥ ③ ③ ③ ④ ① ⑥ ③ ③ ③ ④ ① ⑥ ③ ③ ③ ④ ① ⑥ ③ ③ ③ ④ ① ⑥ ③ ③ 2. 闭回路与变量所对应的系数列向量组线性相关性的关系 结论1. 运输问题一组变量构成闭回路的充要条件是这组变量所对应的系数列向量线性相关 结论2. 运输问题的一个可行解是基可行解的充要条件是： 1）数字格的个数为m+n-1个； 2） m+n-1个数字格不构成闭回路。 第二节 表上作业法 一、表上作业法的步骤 初始基可行解 的确定 结束 Y 调整 N 二、初始基可行解的确定 1. 最小元素法 ③ ④ ① ⑥ ③ ③ 例4 2. 伏格尔法（Vogel） 1 1 0 2 1 0 3 1 5 2 ⑥ 3 1 - 2 ③ - 1 0 2 1 - 2 ③ - 1 0 - 1 - 2 ① ② ⑤ 例5 在以上两种方法中，有几点需要注意： 这两种方法得出的解均为初始可行解。 一般由伏格尔法得出的解比最小元素法得出的解更接近最优解。 在以上方法过程中，不可同时划去行和列。 例6 xij 的分配公式 例6 左上角法解题演示 三、求检验数并进行最优解的判定 1. 闭回路法: 例7 ③ ① ③ ③ ④ ⑥ 1 2 1 -1 10 12 注: 1)数字格检验数均为0 显然该问题至此尚未达到最优解。 ③ ④ ① ⑥ ③ ③ ③ ④ ① ⑥ ③ ③ ③ ④ ① ⑥ ③ ③ ③ ④ ① ⑥ ③ ③ ③ ④ ① ⑥ ③ ③ ③ ④ ① ⑥ ③ ③ ③ ④ ① ⑥ ③ ③ ③ ④ ① ⑥ ③ ③