平衡运输问题及其表上作业法 | 您所在的位置:网站首页 › 运筹学的运输问题表上作业法是什么 › 平衡运输问题及其表上作业法 |
一、平衡运输问题及其表上作业法 平衡问题及数学建模平衡运输问题: 就是生产数量与销售数量相等的运输问题。对总产量等于总需求量的运输问题,可直接采用表上作业法求最优运输方案 数学模型: 2、表上作业法 表上作业法步骤: 1:求解初始可行解(最小元素法、西北角法) 2:位势法求非基变量的检验数(当所有检验数>=0时,为最优解) 3:若检验数不满足时,找出负检验数中最小的格子,用闭回路法调整得到更优的基变量 4:重复2和3 直到得到最优解 运输问题如下例题1:有3个产地,4 个销地的运输规划问题 , 表格中的内容是某产地运往某销地的运费 产地 销地 B1 B2 B3 B4 产量 A1 3 11 3 10 7 A2 1 9 2 8 4 A3 7 4 10 5 9 销量 3 6 5 6 目标函数:minz=3X11+11X12+3X13+10X14+1X21+9X22+2X23+8X24+7X31+4X32+10X33+5X34 最小元素法:从单位运价表中逐次挑选最小的元素,然后划去满足销量或者产量的行或者列,确定初始可行解 第1个基变量 第2个基变量 第3个基变量 第4个基变量 第5个基变量 第6个基变量 直到所有的行列全部划掉 , 所有的产销全部安排完毕 ,此时找到的解就是运输问题的初始可行解 ###################### 最优解判别 : 得到一组 基可行解 之后 , 使用 检验数 判定该解是否是最优解 ; 检验数判定原则 : 运输规划的 目标函数求最小值 时 , 所有的 非基变量检验数 λij λij 都非负 , 该基可行解就是最优解 , 该运输方案是最优方案 ; 求检验数的方法 : ① 位势法 计算出的非基变量 检验数使用蓝色括号字体 红色字体为基变量对应的运量 上述检验数中σ24 为负数 , 需要进行换基 , 该非基变量就是入基变量 ; 该检验数的闭合回路中在 − 符号的基变量中挑选一个最小的 , 作为出基变量 ; 重新计算检验数验证>=0 , 即为最优解 二、指派问题及数学模型 有n项任务需要均分给n个人完成,工人i完成任务j的成本为cij,确定人和任务之间 一一对应的一个分配方案,使得总成本最小。 Cij的取值为0或者1(表示安排第i人完成第j项任务,且每个人完成一项任务、每项任务由一人完成) 匈牙利解法步骤 人员 任务 A B C D 甲 7 16 9 11 乙 6 11 10 5 丙 18 12 10 11 丁 12 13 14 8 1:变化效率矩阵,使每行每列至少有一个0 行变化:找每行最小的元素,从该行各元素减去 列变化:找出每列最小元素,从该列各元素减去
2:找出独立0元素,行有独立划掉列,列有独立划掉行
3:独立0的个数若小于n,则转2、3、4,否则结束 4:在未划线的元素中找出最小的,未划线的各个元素减去这个最小元素,而交叉划线的元素加上这个最小的元素
5独立0的个数若小于n,则转4,否则结束
|
CopyRight 2018-2019 实验室设备网 版权所有 |