第三章 运输问题1.ppt

第三章运输问题 一 运输问题及其数学模型二 表上作业法三 运输问题的进一步讨论四 应用举例 一 运输问题及其数学模型 供应地 运价 需求地 引例 运输问题网络图 供应地约束 需求地约束 一 运输问题及其数学模型 运输问题的描述 设某种物品有m个产地A1 A2 Am 各产地的产量分别是a1 a2 am 有n个销地B1 B2 Bn 各销地的销量分别为b1 b2 bn 假定从产地Ai i 1 2 m 向销地出Bj j l 2 n 运输单位物品的运价是cij 问怎样调运这些物品才能使总运费最小 一 运输问题及其数学模型 运价表 一 运输问题及其数学模型 产销平衡运输问题的数学模型表示 一 运输问题及其数学模型 该模型是一个线性规划模型 可以用单纯形法求解 但是变量数目非常多 如3个产地 4个销地 变量数目会有19个之多 因此应该寻求更简便的解法 为了说明适于求解运输问题的更好的解法 先分析运输问题数学模型的特点 一 运输问题及其数学模型 运输问题数学模型的特点 1 运输问题有有限最优解 是一个可行解 同时 目标函数有下界 且不会趋于负无穷 所以 必存在有限最优解 一 运输问题及其数学模型 2 运输问题约束条件的系数矩阵 n行 m行 系数列向量 一 运输问题及其数学模型 由此可知 运输问题具有下述特点 1 约束条件系数矩阵的元素等于0或1 2 约束条件系数矩阵的每一列有两个非零元素 这对应于每一个变量在前m个约束方程中出现一次 在后n个约束方程中也出现一次 对产销平衡运输问题 除上述两个特点外 还有以下特点 3 所有结构约束条件都是等式约束 4 各产地产量之和等于各销地销量之和 秩 A m n 1运输问题的基可行解中应包含m n 1个基变量 一 运输问题及其数学模型 3 运输问题的解 1 解x必须满足模型中的所有约束条件 2 基变量对应的约束方程组的系数列向量线性无关 3 解中非零变量xij的个数不能大于 m n 1 个 原因是运输问题中虽有 m n 个结构约束条件 但由于总产量等于总销量 故只有 m n 1 个结构约束条件是线性独立的 4 为使迭代顺利进行 基变量的个数在迭代过程中保持为 m n 1 个 运输问题解的每一个分量 都唯一对应其运输表中的一个格填有数字的格或空格 一 运输问题及其数学模型 下表给出了例1的一个解 一 运输问题及其数学模型 二 表上作业法 表上作业法是一种迭代法 迭代步骤为 1 先按某种规则找出一个初始解 初始调运方案 2 再对现行解作最优性判别 3 若这个解不是最优解 就在运输表上对它进行调整改进 得出 个新解 4 再判别 再改进 5 直至得到运输问题的最优解为止 迭代过程中得出的所有解都要求是运输问题的基可行解 例1 二 表上作业法 8 2 10 14 8 6 所以 初始基可行解为 目标函数值Z 246 二 表上作业法 1 初始基可行解 最小元素法 在满足约束条件下尽可能的给最左上角的变量最大值 8 8 6 4 8 14 所以 初始基可行解为 目标函数值Z 372 1 初始基可行解 西北角法 二 表上作业法 沃格尔法计算步骤 1 分别算出各行 各列的罚数 2 从行 列中选出差额最大者 选择它所在行 列中的最小元素 进行运量调整 3 对剩余行 列再分别计算各行 列的差额 返回1 2 二 表上作业法 1 初始基可行解 沃格尔法 14 所以 初始基可行解为 目标函数值Z 244 8 8 12 2 4 二 表上作业法 8 2 10 14 8 6 1 2 1 10 12 1 二 表上作业法 2 解的最优性检验 闭回路法 某空格的检验数是以该空格为第一个顶点 某回路的奇数顶点运价和减去其偶数顶点运价和 原问题 设其对偶变量为 2 解的最优性检验 对偶变量法 二 表上作业法 对偶问题 考虑原问题变量xj的检验数为 二 表上作业法 假设已得到一个基可行解 其基变量为 则有 s m n 1 则运输问题变量xij的检验数为 二 表上作业法 方程组有m n 1个方程 因为运输表中每行和每列均有基变量 因此上面方程组含有全部m n个对偶变量 故解不唯一 其解称为位势 若上述方程的某组解满足对偶问题的所有条件 即 此时 原问题与对偶问题均可行 故达到最优 其解分别为 二 表上作业法 例 8 2 10 14 8 6 二 表上作业法 改进的方法是在运输表中找出这个空格对应的闭回路 在满足所有约束条件的前提下 使xij尽量增大并相应调整此闭回路上其它顶点的运输量 以得到另一个更好的基可行解 3 解的改进 闭回路调整法 二 表上作业法 解改进的具体步骤 1 以xij为换入变量 找出它在运输表中的闭回路 2 以空格 Ai Bj 为第一个奇数顶点 沿闭回路的顺 或逆 时针方向前进 对闭回路上的顶点依次编号 3 在闭回路上的所有偶数顶点中 找出运输量最小的顶点 格子 以该格中的变量为换出变量 4 以换出变量的运输量为调整量 将该闭回路上所有奇数顶点处的运输量都增加这一数值 所有偶数顶点处的运输量都减去这一数值 从而得出一新的运输方案 该运输方案的总运费比原运输方案减少 改变量等于换出变量的检验数 然后 再对得到的新解进行最优性检验 加不是最优解 就重复以上步骤继续进行调整 一直到得出最优解为止 二 表上作业法 例 二 表上作业法 例 8 2 12 14 8 4 0 2 2 9 12 1 由于所有非基变量的检验数全非负 故这个解为最优解 又由于非基变量有零检验数 所以有无穷多最优解 二 表上作业法 练习题 二 表上作业法 练习题 练习题 二 表上作业法 练习题 练习题 二 表上作业法 答案 二 表上作业法 1 若运输问题的某一基可行解有几个非基变量的检验数均为负 在继续进行迭代时 取它们中的任一变量为换入变量均可使目标函数值得到改善 但通常取小于零的检验数中最小者对应的变量为换入变量 2 当迭代到运输问题的最优解时 如果有某非基变量的检验数等于零 则说明该运输问题有多重 无穷多 最优解 4 需要说明的几个问题 二 表上作业法 3 二 退化某一基变量的值为0初始解在确定初始解的供需关系时 若在确定 i j 的数字时 要划去第i行 第j列 为使在产销平衡表上有m n 1个数字格 须在第i行或j列中 非i j 选一数字格为0 退化解闭回路中有 标记中有两个或以上相等的最小数 调整后出现退化解 必须在一数字格中填入0 以表明其为基变量 二 表上作业法 三 运输问题的进一步讨论 上一节讲述的运输问题的算法 是以总产量等于总销量 产销平衡 为前提的 实际上 在很多运输问题中 总产量不等于总销量 表上作业法 以产销平衡为前提 1 产销不平衡的运输问题 三 运输问题的进一步讨论 2 3 2 1 3 4 1 s2 27 s3 19 d1 22 d2 13 d3 12 d4 13 s1 14 供应量 供应地 运价 需求量 需求地 6 7 5 3 8 4 2 7 5 9 10 6 例 假设供应量大于需求量 5 5 d5 5 假想销地 000 s3 24 三 运输问题的进一步讨论 产大于销 产销不平衡 产销平衡 模型 三 运输问题的进一步讨论 设为Ai的贮存量 将多余物原地贮存 令 三 运输问题的进一步讨论 理解 产 销假想有一销地j n 1销量为运价 模型 三 运输问题的进一步讨论 三 运输问题的进一步讨论 例 某市有三个造纸厂A1 A2 A3 其纸的产量分别为8 5和9个单位 有4个集中用户B1 B2 B3 B4 其需用量分别为4 3 5和6个单位 由各造纸厂到各用户的单位运价如表3 15所示 请确定总运费最少的调运方案 三 运输问题的进一步讨论 解 由于总产量22大于总销量18 故本问题是个产销不平衡运输问题 增加一假想销地B5 用表上作业法求解 三 运输问题的进一步讨论 三 运输问题的进一步讨论 2 有转运的运输问题 在以上讨论中 假定物品由产地直接运送到销售目的地 不经中间转运 但是 常常会遇到这种情形 需先将物品由产地运列某个中间转运站 可能是另外的产地 销地或中间转运仓库 然后再转运到销售目的地 有时 经转运比直接运到目的地更为经济 因此 在决定运输方案时有必要把转运也考虑进去 三 运输问题的进一步讨论 2 有转运的运输问题 转运量t1t2t3t4t5t6t7 供应量 需求量 xij 转运量t1t2t3t4t5t6t7 假设单位运转费用为ti 则线性规划模型为 三 运输问题的进一步讨论 第二项为常数 对求解结果无影响 可去掉 模型变为下列形式 这是一个产销平衡运输问题的数学模型 可以列出其运价表 用表上作业法求解 其运价表形式如下 注意其中对角线上的运价值 建立一般意义上的数学模型 设 ai 第i个产地的产量 净供应量 bj 第j个销地的销量 净需要量 xij 由第i个发送地运到第j个接收地的物品数量 cij 由第i个发送地到第j个接收地的单位运价 ti 第i个地点转运物品的数量 ci 第i个地点转运单位物品的费用 将产地和销地统一编号 并把产地排在前面 销地排在后面 则有 令 建立数学模型 注 所有i j cij ci a1 a5b1 b5Qc1 c5c11 c55 例 如图所示是一个运输系统 它包括二个产地 1和2 二个销地 4和5 及一个中间转运站 3 各产地的产量和各销地的销量用相应节点处箭线旁的数字表示 节点联线上的数字表示其间的运输单价 节点旁的数字为该地的转运单价 试确定最优运输方案 运用最小元素法 求初始运输方案 如下表 最优运输方案如下表 一 回答问题1 在运输问题数学模型中 为什么模型的 m n 个约束中最多只有 m n 1 个是独立的 2 试述用最小元素法确定运输问题的初始基可行解的基本思路 3 如何用闭回路法求检验数 4 沃格尔法的基本思想是什么 什么是罚数 5 在解的改进过程中 如何确定调整量 6 如何把一个产销不平衡的运输问题 含产大于销和销大于产 转化为产销平衡的运输问题 练习题 二 判断下列说法是否正确 1 运输问题是一种特殊的线性规划模型 因而求解结果也可能出现下列四种情况之一 有唯一最优解 有无穷多最优解 无界解 无可行解 2 在运输问题中 只要给出一组合 m n 1 个非零的 xij 且满足 xij ai xij bj 就可以作为一个初始基可行解 3 表上作业法实质上就是求解运输问题的单纯形法 4 按最小元素法 或伏格尔法 给出的初始基可行解 从每一空格出发可以找出而且仅能找出唯一的闭回路 练习题 5 如果运输问题单位运价表的某一行 或某一列 元素分别加上一个常数k 最优调运方案将不会发生变化 6 如果运输问题单位运价表的某一行 或某一列 元素分别乘上一个常数k 最优调运方案将不会发生变化 7 当所有产地产量和销地的销量均为整数值时 运输问题的最优解也为整数值 1 2 6不对 练习题 三 用位势法 对偶变量法 求其检验数 练习题 四 运用举例 例1 某飞机制造厂生产一种民用喷气式飞机 生产的最后阶段是制造喷气发动机 以及把发动机安装到已完成的飞机骨架上 一种很快的操作 为了不误合同规定的交货期 第一 二 三 四月必须安装发动机的台数分别为 10 15 25 20 但受生产能力等条件的限制 这些月份的最高生产台数分别为 25 35 30 10 每月单台发动机的存储费用为1 5万元 已知一 二 三 四月份的单台生产费用各为 108 111 110 113万元 试安排这四个月的生产计划 使生产费用和存储费用之和最小 1 建立此问题的一般LP模型 2 把此问题作为运输问题来处理 试建立相应的运输表格 3 求此 运输问题 的最优解 解 1 设xi表示第i个月生产发动机的台数 yi表示第个月的存储台数 则一般LP模型为 四 运用举例 由于不能缺货 并考虑到是不平衡问题 虚设收点5 建立如下运输表格 四 运用举例 最小费用为 w 7730 万元 四 运用举例 例2某航运公司承担六个港口城市A B C D E F的四条固定航线的物资运输任务 已知各条航线的起点 终点城市及每天航班数见表 每条航线使用相同型号的船只 各城市间的航程天数如表 四 运用举例 每条船只每次装卸货物的时间各需一天 该航运公司至少应配备多少条船 才能满足所有航线的运货需求 四 运用举例 每天载货航程所需的船只数 四 运用举例 分析 1 所需船只可分为两部分 载货航程所需的船只数 各港口间调度所需的船只数 2 每天载货航程所需的船只数 3 每天各港口调度所需船只数 四 运用举例 为使配备船只数最少 就应将C D F的船只调运到A B E 由表上作业法 最优调运为 四 运用举例 所以 每天用于调度的最少船只数为 5 2 13 1 17 1 7 1 47最少总需求为91 47 138 条 四 运用举例 例3 某玩具公司分别生产三种新型玩具 每月可供量分别为l000件 2000件 2000件 它们分别被送到甲 乙 丙三个百货商店销售 已知每月百货商店各类玩具预期销售量均为1500件 由于经营方面原因 各商店销售不同玩具的盈利额不同 见表 又知丙百货商店要求