运输问题表上作业法（汇总）.ppt

必威体育精装版文档 必威体育精装版文档 必威体育精装版文档 必威体育精装版文档 必威体育精装版文档 §7.4 表上作业法 一、表上作业法迭代步骤 1．按某种规则找出一个初始基可行解； 2．对现行解作最优性判断，即求各非基变量的检验数，判别是否达到最优解，如已是最优解，则停止计算，如不是最优解，则进行下一步骤； 3．在表上对初始方案进行改进，找出新的基可行解，再按第二步进行判别，直至找出最优解。 必威体育精装版文档 * 确定初始方案 ( 初 始 基本可行解) 改进调整 （换基迭代） 否 判定是否 最 优？ 是 结 束 最优方案 图 1运输问题求解思路图 必威体育精装版文档 * 二、初始基本可行解的确定 例2：甲、乙两个煤矿供应A、B、C三个城市用煤，各煤矿产量及各城市需煤量、各煤矿到各城市的运输单价见表所示，求使总运输费用最少的调运方案。 必威体育精装版文档 * 例题有关信息表 450 200 150 100 日销量 （需求量） 250 75 65 80 乙 200 100 70 90 甲 日产量 （供应量） C B A 运距 城市 煤矿 必威体育精装版文档 * 例题 数学模型 必威体育精装版文档 * （1）最小元素法：从运价最小的格开始，在格内的标上允许取得的最大数。然后按运价从小到大顺序填数。若某行（列）的产量（销量）已满足，则把该行（列）的其他格划去。如此进行下去，直至得到一个基本可行解。 必威体育精装版文档 * 调 销地 运 量 产地 B1 B2 B3 产 量 A1 90 X11 70 X12 100 X13 200 A2 80 X21 65 X22 75 X23 250 销 量 100 150 200 450 用最小元素法确定初始调运方案 150 100 100 100 100 100 100 必威体育精装版文档 * 得到初始调运方案为： x11=100，x13=100，x22=150，x23=100 必威体育精装版文档 * （2）西北角法 不是优先考虑具有最小单位运价的供销业务，而是优先满足运输表中西北角（左上角）上空格的供销要求 必威体育精装版文档 * 调 销地 运 量 产地 B1 B2 B3 产 量 A1 90 X11 70 X12 100 X13 200 A2 80 X21 65 X22 75 X23 250 销 量 100 150 200 450 用西北角法确定初始调运方案 100 100 100 50 50 200 200 必威体育精装版文档 * 得到初始调运方案为： x11=100，x12=100，x22=50，x23=200 必威体育精装版文档 * 三、最优性检验 根据最小元素法或西北角法求得运输问题的初始基可行解之后，按照表上作业法的第二步，下面需对这个解进行最优性判别，看它是否为本运输问题的最优解. 必威体育精装版文档 * １、闭回路法 思路：要判定运输问题的初始基可行解是否为最优解，可仿照一般单纯形法，检验这个解的各非基变量（对应于运输表中的空格）的检验数。 检验数：运输问题中非基变量（对应于空格）的检验数定义为给某空格增加单位运量导致总费用的增加量。 如果有某空格（Ａi、Bj）的检验数为负，说明将Xij变为基变量将使运输费用减少，故当前这个解不是最优解。若所有空格的检验数全为非负，则不管怎样变换，均不能使运输费用降低，即目标函数值已无法改进，这个解就是最优解。 必威体育精装版文档 * 闭回路：在给出的调运方案的运输表上，从一个空格（非基变量）出发，沿水平或垂直方向前进，只有碰到代表基变量的数字格才能向左或向右转90°继续前进，直至最终回到初始空格而形成的一条回路。 从每一空格出发，一定可以找到一条且只存在唯一一条闭回路 。 必威体育精装版文档