运筹学课件第一节运输问题及其数学模型.ppt

第三章运输问题 模型及其特点求解思路及相关理论求解方法 表上作业法运输问题的推广1 产销不平衡的运输问题2 转运问题 第一节运输问题及其数学模型一 运输问题的数学模型1 运输问题的一般提法 某种物资有若干产地和销地 现在需要把这种物资从各个产地运到各个销地 产量总数等于销量总数 已知各产地的产量和各销地的销量以及各产地到各销地的单位运价 或运距 问应如何组织调运 才能使总运费 或总运输量 最省 单位根据具体问题选择确定 表有关信息 2 运输问题的数学模型 设xij为从产地Ai运往销地Bj的物资数量 i 1 m j 1 n 由于从Ai运出的物资总量应等于Ai的产量ai 因此xij应满足 同理 运到Bj的物资总量应该等于Bj的销量bj 所以xij还应满足 总运费为 运输问题的数学模型 二 运输问题数学模型的特点1 约束方程组的系数矩阵具有特殊的结构系数矩阵A 形式如下 2 运输问题的基变量总数是m n 1写出增广矩阵 每一列只有两个元素为1 其余元素均为0 列向量Pij 0 0 1 0 0 1 0 0 T 其中两个元素1分别处于第i行和第m j行 将该矩阵分块 特点是 前m行构成m个m n阶矩阵 而且第k个矩阵只有第k行元素全为1 其余元素全为0 k 1 m 后n行构成m个n阶单位阵 证明系数矩阵A及其增广矩阵的秩都是m n 1 前m行相加之和减去后n行相加之和结果是零向量 说明m n个行向量线性相关 因此的秩小于m n 因此的秩恰好等于m n 1 又D本身就含于A中 故A的秩也等于m n 1 由的第二至m n行和前n列及对应的列交叉处元素构成m n 1阶方阵D非奇异 可以证明 m n个约束方程中的任意m n 1个都是线性无关的 第二节表上作业法求解运输问题表上作业法的基本思想是 先设法给出一个初始方案 然后根据确定的判别准则对初始方案进行检查 调整 改进 直至求出最优方案 如图所示 表上作业法和单纯形法的求解思想完全一致 但是具体作法更加简捷 运输问题求解思路图 一 初始方案的确定1 作业表 产销平衡表 初始方案就是初始基本可行解 将运输问题的有关信息表和决策变量 调运量结合在一起构成 作业表 产销平衡表 下表是两个产地 三个销地的运输问题作业表 表运输问题作业表 产销平衡表 其中xij是决策变量 表示待确定的从第i个产地到第j个销地的调运量 cij为从第i个产地到第j个销地的单位运价或运距 2 确定初始方案的步骤 1 选择一个xij 令xij min ai bj 将具体数值填入xij在表中的位置 2 调整产销剩余数量 从ai和bj中分别减去xij的值 若ai xij 0 则划去产地Ai所在的行 即该产地产量已全部运出无剩余 而销地Bj尚有需求缺口bj ai 若bj xij 0 则划去销地Bj所在的列 说明该销地需求已得到满足 而产地Ai尚有存余量ai bj 3 当作业表中所有的行或列均被划去 说明所有的产量均已运到各个销地 需求全部满足 xij的取值构成初始方案 否则 在作业表剩余的格子中选择下一个决策变量 返回步骤 2 按照上述步骤产生的一组变量必定不构成闭回路 其取值非负 且总数是m n 1个 因此构成运输问题的基本可行解 对xij的选择采用不同的规则就形成各种不同的方法 比如每次总是在作业表剩余的格子中选择运价 或运距 最小者对应的xij 则构成最小元素法 若每次都选择左上角格子对应的xij就形成西北角法 也称左上角法 和沃格尔法 vogel 3 举例 例某部门有3个生产同类产品的工厂 生产的产品由4个地点销售 各个供应地 目的地的生产量 销售量以及各个供应地到目的地的运费见表 求使总运输量最少的调运方案 1 最小元素法 产地 销地 4 12 10 2 8 5 11 3 4 11 9 6 8 2 10 14 8 6 Z 10X4 6X11 8X2 2X3 14X5 8X6 246 最小元素法的基本思想是 就近供应 运价表上找最小 平衡表上定产销 满足销量划去 列 修改 行产 要记牢 满足产量划去 行 修改 列销 要记牢 余表再来找最小 2 西北角法 4 3 9 4 11 12 11 6 8 5 10 2 8 8 6 4 8 14 Z 8X4 8X12 6X10 4X3 8X11 14X6 372 西北角法则不考虑运距 或运价 每次都选剩余表格的左上角 即西北角 元素作为基变量 其它过程与最小元素法相同 3 沃格尔法 每个供应地到销售地 或每个销售地到供应地 的单位运价中找出最小运价和次小单位运价 运价之差为供应地到销售地的罚数 如果罚数的数值不大 当不能按照最小单位运输时造成的损失不大 如果罚数的数值大 当不能按照最小单位运输时造成的损失大 应该尽量按照最小单位运输 计算步骤1 计算每一行和每一列的罚数 称为行罚数和列罚数 2 将计算的行罚数和列罚数添加到表格中 3 根据行罚数和列罚数 行等于列 找最大的罚数 确定罚数所在的行或列 按照最小单位法进行表上作业 4 9 4 11 6 11 5 8 12 2 3 10 14 8 8 12 2 4 Z 12x4 4x11 8x2 2x9 14x5 8x6 244一般用作近似解 小结 1 讲解运输问题及其数学模型 2 三种表上作业法求解运输问题的计算步骤