第四章-运输问题.ppt

1、运筹学 Operations Research,北京理工大学珠海学院 吴浩然,运输问题模型,第四章 运输问题,1,表上作业法,2,运输问题的应用,3,1.运输问题模型-问题提出,某企业从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示：,请问，应如何调运可使总运输费用最小？,产地,销地,元素等于0或1； 每列只有两个元素为1，其余为0； 对于每个变量，前m个约束方程只出现一次，后n个约束方程也只出现一次；,运输问题约束条件系数矩阵的特点,是否最优解？,寻找新的基本可行解,2.表上作业法步骤,西北角法：从 x11开始分配，

2、从西北向东南方向逐个分配； 最小元素法：采用最小费用优先分配的原则；,步骤1：初始基本可行解的确定,检验数的公式为：,其中 分别称为行位势、列位势。,结论： （1）基变量所对应的检验数：,步骤2：最优解的检验-位势法,（2）若非基变量所对应的检验数 当前解即为最优解；,闭回路： 从进基变量的空格出发，沿水平或垂直方向前进，每碰到数字格转90o（有些情况也可以不改变方向）继续前进，直到回到出发的空格为止，由此形成的封闭的折线称为闭回路。,步骤3：寻找新的基本可行解-闭回路法,某企业从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如

3、下表所示：,请问，应如何调运可使总运输费用最小？,产地,销地,某公司有从三个产地A1，A2，A3，将物品运送到四个销地B1，B2，B3，B4，各产地的产量、各销地的销量、各产地到各销地的单位运价如下表所示： 请问，应如何调运产品，使得总运费最少？,课堂练习,从每一个非基变量的空格出发，构造闭回路。若非基变量所对应的检验数 ，则当前解即为最优解。 其中： 闭回路奇数顶点运费之和 -闭回路偶数顶点运费之和,闭回路法检验解的最优性,某公司有从三个产地A1，A2，A3，将物品运送到四个销地B1，B2，B3，B4，各产地的产量、各销地的销量、各产地到各销地的单位运价如下表所示： 请用最小元素法确定初始基

4、本可行解，并用闭回路法检验初始基本可行解是否为最优解。,课堂练习,总产量总销量,2.表上作业法（产销不平衡的运输问题）,某公司有从三个产地A1，A2，A3，将物品运送到三个销地B1，B2，B3，各产地的产量、各销地的销量、各产地到各销地的单位运价如下表所示：,请问，应如何调运产品，使得总运费最少？,某公司有从三个产地A1，A2，A3，将物品运送到四个销地B1，B2，B3，B4，各产地的产量、各销地的销量、各产地到各销地的单位运价如下表所示： 请问，应如何调运产品，使得总运费最少？,课堂练习,总销量总产量,某公司有从三个产地A1，A2，A3，将物品运送到五个销地B1，B2，B3，B4， B5，各产地的产量、各销地的销量、各产地到各销地的单位运价如下表所示： 请问，应如何调运产品，使得总运费最少？,1.判别下表中的调运方案能否作为表上作业法的初始解。,2.请用最小元素法确定下述运输问题的初始基本可行解。,3.某公司有从两个产地A1，A2，将物品运送到三个销地B1，B2，B3，各产地的产量、各销地的销量、各产地到各销地的单位运价如下表所示： 其中， B3的销量必须得到满足。请问，应如何调运产品，使得总运费最少？,4.某公司有从三个产地A1，A2， A3 ，将物品运送到三个销地B1，B2，B3，各产地的产量