第六章(运输问题1)

第六章运输问题 数学模型及其解法 在处理产 供 销的经济活动中 会经常遇到物资调拨的运输问题 如粮棉油 煤炭 钢铁 水泥 化肥 木材等物资要由若干个产地调运到若干个销售地 问题是 怎样制定合理的调用方案才能使总运输费用最少 本章将专门讨论这类特殊形式的线性规划问题 导言 例某食品公司经销的主要商品之一是糖果 它下面设有三个加工厂 产量分别为A1 5t A2 2t A3 3t 该公司把这些糖果分别运往四个地区的门市部销售 各地区每天的销售量为 B1 2t B2 3t B3 1t B4 4t 已知从各个加工厂到各销售部门每吨的运价见下表 问 该食品公司应如何调运 在满足各部门销售的情况下 使总的运费支出为最少 引例 6 1运输问题的数学模型 无论全国或一个地区 在各种生产或生活物资调运中都可以提出入上述问题类似的例子 现在把问题概括一下 在线性规划中我们研究这样一类运输问题 6 1运输问题的数学模型 设有某种物资要从m个产地 或称发点 Ai i 1 2 m 运往n个销地 或称收点 Bj j 1 2 n Ai的产量为ai Bj的销量为bj 把Ai运到Bj的单位运价设为cij 问怎样编制调运方案才能使总运费最少 假设从Ai运到Bj的物资数量为xij 总运费为S 总产量 总销量 那么这个运输问题的数学模型是 6 1运输问题的数学模型 6 1运输问题的数学模型 运输问题的数学模型 产销平衡表 产销平衡的运输问题 6 1运输问题的数学模型 运输问题的数学模型是 运输问题有m n个决策变量 m n个约束条件 由于产销平衡条件 只有m n 1个相互独立 因此 运输问题的基变量只有m n 1个 C c11 c12 c1n c21 c22 c2n cm1 cm2 cmn B a1 a2 am b1 b2 bn TX x11 x12 x1n x21 x22 x2n xm1 xm2 xmn T 6 1运输问题的数学模型 其矩阵形式为 产销平衡的运输问题 6 2运输问题的求解方法 约束条件非常有规律 技术系数非0即1基变量的个数远小于决策变量的个数采用表上作业法运算中涉及两个表 运费表和产销平衡表 分配表 表上作业法是求解产销平衡运输问题的一种简便而有效的方法 其求解工作在运输表上进行 其实质是单纯形法 但具体计算和术语有所不同 可归纳为 1 找出初始基本可行解 初始运输方案 2 求各非基变量的检验数 即在表上计算空格的检验数 判别是否达到最优解 如已是最优解 则停止计算 否则转到下一步 3 确定换入变量和换出变量 找出新的基本可行解 在表上用闭回路法调整 4 重复 2 3 直到得到最优解为止 表上作业法 运输单纯形法 一 寻找初始可行解的方法 1 西北角法从x11开始分配 从西北向东南方向逐个分配xij的分配公式 例3 2 1 例6 1西北角法 2 最小元素法 最低费用法 这方法是根据运价低的优先供应的原则安排运输量 它首先找出运价最小的 并以最大限度满足其供销量为原则确定供销业务 然后 在余下的未确定的供销业务中找运价最小的 同样以最大限度满足其供销量为原则确定供销业务 同样的方法反复进行直到确定了所有的供销业务 得到一个完整的调运方案即初始基本可行解为止 采用最小费用优先分配的原则 看一步 f x 121 比西北角法低84 注意事项 为保证基变量为m n 1个 确定基变量时应遵循原则 1 在确定某一变量为基变量并安排运输任务时 如果其所在行和列其他元素都为0时 不能同时把行和列都划掉 2 在确定为最小元素的某一空格上 如果变量xij min ai bj 0 此时不能保留空格 应安排任务为0 但也是基变量 3 运费差额法 伏格尔 Vogel 法 最小元素法的缺点是 为了节省一处的费用 有时造成在其它处要多花几倍的运费 伏格尔法考虑到某产地的产品假如不能按最小运费就近供应 就考虑次小运费 这就有一个差额 差额越大 说明不能按最小运费调运时 运费增加越多 因而对差额最大处 就应当采用最小运费调运 采用最大差额费用 即利用每行或列中最小费用与次最小之间的差额中选最大 优先分配的原则 f x 98 比最低费用法又低了23 例题 课堂练习 分别用三种方法进行初始调运方案的编制 二 最优解的判断1 位势法 最优解的判别方法是计算空格 非基变量 的检验数 因运输问题的目标函数是要求实现最小化 故当所有的检验数 ij Cij Zij 都大于或等于零时 为最优解 不采用单纯型法 如何获得xij的检验数找到原问题的基础可行解 保持互补松弛条件 求出对应对偶问题的解 若该对偶问题的解非可行 则原问题的解不是最优解 否则 达到最优解 位势法的原理 为满足互补松弛条件 原问题中Xij被选为基变量 即Xij 0 则要求对偶问题中Ui Vj Cij 即该行的松弛变量为0共有m n 1个基变量Xij 因此可得m n 1个等式Ui Vj Cijm n 1个等式只能解出m n 1个Ui和Vj 而一共有m n个Ui和Vj 但可令任一个Ui或Vj 0 从而解出其它m n 1个的值 这就是位势法令Zij Ui Vj 其相当原问题Xij 非基变量 的机会费用若对所有非基变量有Cij Zij 0 即Ui Vj Cij 表明当前Ui和Vj是对偶问题的可行解 由互补松弛定理可知当前m n 1个基变量Xij是最优解 否则从Cij Zij 0中找最小者 对应Xij就是入变量 例题 用位势法判断是否达到最优 如没有达到最优确定入变量 X24为入变量 2 闭回路法求检验数 闭回路画法 以非基变量为出发点 在水平或垂直方向划线 碰到基变量允许变向 直到找到一个闭回路 从换入变量开始编号1 2 从入变量xij出发 遇到某个基变量则选一个方向拐角 若不能再遇到其它基变量 则返回上一拐角 换一个方向走 采用深探法闭合回路不一定是矩形 求各个非基变量检验数方法 按照闭回路上编号 所有奇点运费取正 所有偶点运费取负值 检验数等于闭回路上所有点的运费代数和 说明 以任何一个非基变量为起终点 与运输表各中m n 1个基变量只能画出唯一一个闭回路 例题 用闭回路法求解各非基变量的检验数 并判断有没有达到最优 闭回路的经济含义 例如在x11对应的空格处把调运方案调整一下 由产地A1调1单位物资给B1 为保持平衡 必须x13处减少1单位的物资 x23增加1单位物资 x21处减少1单位物资 由此保持调运物资平衡 对应需要增加物资的调运的为总运费增加 减少调运的为总运费减少 当检验数为正值时说明该处增加调运任务会使总运费增加 故不能作为入变量 当检验数为负 说明该处增加调运任务会使总运费减少 故原调运方案不是最优 课堂练习 分别用位势法和闭回路法判断是否达到最优 如没有达到最优确定入变量 X13为入变量 三 非最优方案的调整 闭回路法 当出现负检验数时 表明不是最优解 需要改进 1 入变量的确定 若有两个和两个以上的负检验数时 一般选其中最小的负检验数 以它对应的变量为换入变量 如同时多个最小 则选运费最小者优先进基 即以它对应的非基变量为换入变量 2 出变量的确定 在进基变量组成的闭回路上 按照 minxij 所有偶点 确定出基变量 且 为调整值 如果有多个 同时最小 则选运价大者优先出基 如此时有多个运价同时最大 则任意一个出基即可 3 方案的调整 所有偶点 与换入变量相邻的变量 都减去 所有奇点 与偶点相邻的变量 都加上 例题 用闭回路法调整最优方案 迭代中需注意的问题 1 不能正确画闭合回路2 初始解退化 未能补足基变量的个数 因此在位势法中多次令某个ui或vj为0 3 在位势法中只能令一个ui或vj为0 若不能求出全部ui和vj 说明基变量未选够数或未选对 运输问题是特殊的线性规划问题 但是求解结果只可能出现下列三种情况之一 有唯一最优解 有无穷多最优解 无可行解 因为我们讲的问题 数据都是正的 而目标求最小 如果把运输问题没有作为实际问题 而是线形规划问题的一种则解的类型有 有唯一最优解 有无穷多最优解 无可行解和无界解 表上作业法小结 表上作业法解题过程框图 作业 用表上作业法求出最优调运方案 6 3产销不平衡的运输问题及其求解方法 实际问题中产销往往是不平衡的 就需要把产销不平衡的问题化成产销平衡的问题 转化为产销平衡的方法就是增加虚拟产地和虚拟销地 仓库 然后按照产销平衡的方法求解即可 在用最小元素法确定初始调运方案时 先考虑有实际运输任务的产销地 最后再给虚拟的产销地安排任务 1 产量大于销量的情形 产销不平衡运输问题的转化 其运输问题的数学模型是 由于总量大于总销量 所以多余物资应储存在产地 设某产地Ai的多余存储量为xi n 1 于是运输问题的约束条件方程组为 则 产销不平衡运输问题的转化 可将不平衡的运输问题3化为如下的平衡运输问题 产销不平衡运输问题的转化 令 2 产量大于销量的运输问题这时可增加一个设想的发点Am 1 发出量为 并令该发点到收点B 的运价C 同样可将不平衡的运输问题转化为平衡的运输问题 产销不平衡运输问题的转化 6 4表上作业法应用举例 1 需求量或产量有区间范围限制例 已知A1 A2 A3三个矿区可分别供应煤炭200 300 400 万吨 年 下述地区需调入煤炭 B1为100 200万吨 年 B2为200 300万吨 年 B3为不低于200万吨 年 最高不限 B4为180 300万吨 年 已知单位运价表 元 吨 如表所示 如要求把所有煤炭分配出去 满足上述需求 又使总运费为最少的调运方案 试列出用运输问题模型求解时的产销平衡表及单位运价表 不必求解 解 因为销地至少需要680单位 产地总量900 故B3最多需要420 故销地最多有1220 大于实际产量 应虚设一个产地 课堂练习 已知从A1 A2 A3三个产地运至销地B1 B2 B3 三个销地需求量分别为7 5 5单位 A1处至少发出6单位 最多发出10个单位 A2必须发出5单位 A3处至少发出3单位 已知单位运价表如表所示 如要求满足所有销地需求并使总运费为最少的调运方案 试列