第七章+运输问题（1表上作业）.ppt

第七章运输问题 TransportationProblem 第七章运输问题 运输问题在工商管理中有着广泛的应用 是一类重要的和特殊的线性规划问题 由于这类线性规划问题在结构上有特殊性 所以有专门的解法 表上作业法等 用以简便求解这类问题 管理运筹学软件中也为求解这类问题编制了专门的程序供我们使用 第七章运输问题 7 1运输问题的模型 7 1运输问题的模型 例1 某公司从两个产地A1 A2将物品运往三个销地B1 B2 B3 各产地的产量 各销地的销量和各产地运往各销地每件物品的运费如下表所示 问应如何调运可使总运输费用最小 7 1运输问题的模型 解 这是一个产销平衡问题 总产量 总销量 500 设xij为从产地Ai运往销地Bj的运输量 如 x12表示从产地A1运往销地B2的运输数量 于是我们得到新的综合表格 7 1运输问题的模型 解 这是一个产销平衡问题 总产量 总销量 500 设xij为从产地Ai运往销地Bj的运输量 如 x12表示从产地A1运往销地B2的运输数量 于是我们得到新的综合表格 minf 6x11 4x12 6x13 6x21 5x22 5x23s t x11 x12 x13 200 x21 x22 x23 300 x11 x21 150 x12 x22 150 x13 x23 200 xij 0 i 1 2 j 1 2 3 解得 minf 2500 x11 50 x12 150 x13 0 x21 100 x22 0 x23 200 7 1运输问题的模型 1 一般运输问题的线性规划模型假设A1 A2 Am表示某物资的m个产地 B1 B2 Bn表示某物资的n个销地 si表示产地Ai的产量 dj表示销地Bj的销量 cij表示把物资从产地Ai运往销地Bj的单位运价 如果s1 s2 sm d1 d2 dn 称该运输问题是产销平衡的 否则 称它是产销不平衡的 7 1运输问题的模型 7 1运输问题的模型 设xij为从产地Ai运往销地Bj的运输量 则对于产销平衡问题 可得到下列运输问题的模型 mnminf cijxiji 1j 1ns t xij sii 1 2 mj 1m xij djj 1 2 ni 1xij 0 i 1 2 m j 1 2 n minf 6x11 4x12 6x13 6x21 5x22 5x23s t x11 x12 x13 200 x21 x22 x23 300 x11 x21 150 x12 x22 150 x13 x23 200 xij 0 i 1 2 j 1 2 3 7 1运输问题的模型 设xij为从产地Ai运往销地Bj的运输量 则对于产销平衡问题 可得到下列运输问题的模型 mnminf cijxiji 1j 1ns t xij sii 1 2 mj 1m xij djj 1 2 ni 1xij 0 i 1 2 m j 1 2 n 7 1运输问题的模型 2 一般模型的系数矩阵特征1 共有m n行 分别表示各产地和销地 m n列 分别表示各变量 2 每列只有两个1 其余为0 分别表示只有一个产地和一个销地被使用 minf 6x11 4x12 6x13 6x21 5x22 5x23s t x11 x12 x13 200 x21 x22 x23 300 x11 x21 150 x12 x22 150 x13 x23 200 xij 0 i 1 2 j 1 2 3 7 1运输问题的模型 2 一般模型的系数矩阵特征1 共有m n行 分别表示各产地和销地 m n列 分别表示各变量 2 每列只有两个1 其余为0 分别表示只有一个产地和一个销地被使用 7 1运输问题的模型 3 一般模型有时会发生一些如下变化 1 有时求目标函数最大值 如求利润最大或营业额最大等 2 当某些运输线路上的能力有限制时 模型中可直接加入 等式或不等式 约束 3 产销不平衡时 可加入虚设的产地 销大于产时 或销地 产大于销时 第七章运输问题 7 1运输问题的模型7 2运输问题的表上作业法 7 2运输问题的表上作业法 表上作业法是一种求解运输问题的特殊方法 其实质是单纯形法 运输问题都存在最优解 7 2运输问题的表上作业法 计算过程 假设产销平衡 1 找出初始基本可行解 对于有m个产地n个销地的产销平衡问题 则有m个关于产量的约束方程和n个关于销量的约束方程 minf 6x11 4x12 6x13 6x21 5x22 5x23s t x11 x12 x13 200 x21 x22 x23 300 x11 x21 150 x12 x22 150 x13 x23 200 xij 0 i 1 2 j 1 2 3 7 2运输问题的表上作业法 计算过程 假设产销平衡 1 找出初始基本可行解 对于有m个产地n个销地的产销平衡问题 则有m个关于产量的约束方程和n个关于销量的约束方程 由于产销平衡 其模型最多只有m n 1个独立的约束方程 即运输问题有m n 1个基变量 minf 6x11 4x12 6x13 6x21 5x22 5x23s t x11 x12 x13 200 x21 x22 x23 300 x11 x21 150 x12 x22 150 x13 x23 200 xij 0 i 1 2 j 1 2 3 7 2运输问题的表上作业法 计算过程 假设产销平衡 1 找出初始基可行解 对于有m个产地n个销地的产销平衡问题 则有m个关于产量的约束方程和n个关于销量的约束方程 由于产销平衡 其模型最多只有m n 1个独立的约束方程 即运输问题有m n 1个基变量 7 2运输问题的表上作业法 计算过程 假设产销平衡 1 找出初始基可行解 2 求各非基变量的检验数 即检验除了上述m n 1个基变量以外的空格的检验数判别是否达到最优解 如果已是最优 停止计算 否则转到下一步 7 2运输问题的表上作业法 计算过程 假设产销平衡 1 找出初始基可行解 2 求各非基变量的检验数 3 确定入基变量和出基变量 找出新的基可行解 4 重复2 3直到得到最优解 7 2运输问题的表上作业法 1 找出初始基可行解 7 2运输问题的表上作业法 例 喜庆食品公司有三个生产面包的分厂A1 A2 A3 有四个销售公司B1 B2 B3 B4 其各分厂每日的产量 各销售公司每日的销量以及各分厂到各销售公司的单位运价如表所示 在表中产量与销量的单位为吨 运价的单位为百元 吨 问该公司应如何调运产品在满足各销点的需求量的前提下总运费最少 7 2运输问题的表上作业法 1 找出初始基可行解 最小元素法我们很容易的直观想到 为了减少运费 应优先考虑单位运输价格最小 或运输距离最短 的供销业务 最大限度的满足其供销量 7 2运输问题的表上作业法 例 喜庆食品公司有三个生产面包的分厂A1 A2 A3 有四个销售公司B1 B2 B3 B4 其各分厂每日的产量 各销售公司每日的销量以及各分厂到各销售公司的单位运价如表所示 在表中产量与销量的单位为吨 运价的单位为百元 吨 问该公司应如何调运产品在满足各销点的需求量的前提下总运费最少 最小元素法 最小元素法 最小元素法 最小元素法 最小元素法 最小元素法 最小元素法 最小元素法 7 2运输问题的表上作业法 1 找出初始基可行解 注意两个问题 1 当我们取定xij的值之后 会出现Ai的产量与Bj的销量都改为零的情况 这时只能划去Ai行或Bj列 但不能同时划去Ai行与Bj列 2 用最小元素法时 可能会出现只剩下一行或一列的所有格均未填数或未被划掉的情况 此时在这一行或者一列中除去已填上的数外均填上零 不能按空格划掉 这样可以保证填过数或零的格为m n 1个 即保证基变量的个数为m n 1个 最小元素法 最小元素法 最小元素法 最小元素法 最小元素法 7 2运输问题的表上作业法 1 找出初始基可行解 注意两个问题 1 当我们取定xij的值之后 会出现Ai的产量与Bj的销量都改为零的情况 这时只能划去Ai行或Bj列 但不能同时划去Ai行与Bj列 2 用最小元素法时 可能会出现只剩下一行或一列的所有格均未填数或未被划掉的情况 此时在这一行或者一列中除去已填上的数外均填上零 不能按空格划掉 这样可以保证填过数或零的格为m n 1个 即保证基变量的个数为m n 1个 7 2运输问题的表上作业法 计算过程 假设产销平衡 1 找出初始基可行解 2 求各非基变量的检验数 7 2运输问题的表上作业法 2 求各非基变量的检验数 所谓闭回路是在已给出的调运方案的运输表上从一个代表非基变量的空格出发 沿水平或垂直方向前进 只有遇到代表基变量的填入数字的格才能向左或右转90度 当然也可以不改变方向 继续前进 这样继续下去 直至回到出发的那个空格 由此形成的封闭折线叫做闭回路 一个空格存在唯一的闭回路 闭回路 闭回路 7 2运输问题的表上作业法 2 求各非基变量的检验数 闭回路所谓闭回路是在已给出的调运方案的运输表上从一个代表非基变量的空格出发 沿水平或垂直方向前进 只有遇到代表基变量的填入数字的格才能向左或右转90度 当然也可以不改变方向 继续前进 这样继续下去 直至回到出发的那个空格 由此形成的封闭折线叫做闭回路 一个空格存在唯一的闭回路 闭回路 闭回路 闭回路 7 2运输问题的表上作业法 2 求各非基变量的检验数 对于代表非基变量的空格 其调运量为零 把它的调运量调整为1 由于产销平衡的要求 我们必须对这个空格的闭回路的顶点的调运量加上或减少1 最后我们计算出由这些变化给整个运输方案的总运输费带来的变化 闭回路 闭回路 闭回路 闭回路 闭回路 检验数即为3 3 2 1 1 闭回路 闭回路 闭回路 闭回路 闭回路 检验数即为11 10 5 4 2 闭回路 检验数即为7 5 10 3 2 1 10 闭回路 7 3运输问题的表上作业法 2 求各非基变量的检验数 对于代表非基变量的空格 其调运量为零 把它的调运量调整为1 由于产销平衡的要求 我们必须对这个空格的闭回路的顶点的调运量加上或减少1 最后我们计算出由这些变化给整个运输方案的总运输费带来的变化 如果所有代表非基变量的空格的检验数都大于等于零 则已求得最优解 否则继续迭代找出最优解 7 2运输问题的表上作业法 计算过程 假设产销平衡 1 找出初始基可行解 2 求各非基变量的检验数 3 确定入基变量和出基变量 找出新的基可行解 闭回路调整法 闭回路调整法 1 选取所有负检验数最小的非基变量作为入基变量 以求尽快实现最优 闭回路调整法 闭回路调整法 选取所有负检验数最小的非基变量xij作为入基变量 以求尽快实现最优 在以xij为出发点的闭回路中 找出所有偶数的顶点的调运量 以其中的最小的变量为换出变量将该闭回路上所有的奇数顶点的调运量增加这一数值 所有的偶数顶点的调运量减少这一数值 闭回路调整法 闭回路调整法 闭回路调整法 选取所有负检验数最小的非基变量xij作为入基变量 以求尽快实现最优 在以xij为出发点的闭回路中 找出所有偶数的顶点的调运量 以其中的最小的变量为换出变量将该闭回路上所有的奇数顶点的调运量增加这一数值 所有的偶数顶点的调运量减少这一数值 闭回路调整法 闭回路调整法 闭回路调整法 7 2运输问题的表上作业法 计算过程 假设产销平衡 1 找出初始基可行解