运筹学_运输问题.ppt

《运筹学_运输问题.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第五章运输问题运输问题模型表上作业法运输问题扩展例1.某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往个销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？引例B1B2B3产量A1646200A2655300销量150150200销地产地解：产销平衡问题：总产量=总销量设xij为从产地Ai运往销地Bj的运输量，得到下列运输量表：Minz=6x11+4x12+6x13+6x21+5x22+5x23s.t.x11+x12+x13=200x21+x22+x23=300x11+x21=150x12+

2、x22=150x13+x23=200xij≥0(i=1，2；j=1，2，3)构建数学模型：线性规划模型B1B2B3产量A1x11x12x13200A2x21x22x23300销量150150200500销地产地运输问题的一般形式假设某种物品有m个产地，用Ai来表示(i=1,…,m)，各地的产量分别为ai(i=1,…,m)，有n个销地，用Bj来表示(j=1,…,n)，各地的销量分别为bj(j=1,…,n)，从产地Ai到销地Bj运输一个单位物资的运价为Cij，问该如何调运物品使总运费最小？运输问题的一般模型ai——产地i的产量，bj——销地j的销量。(4)s.t

3、.产销平衡运输问题的模型(5)s.t.产销平衡运输问题数学模型的特点：产量总和等于销量总和。约束条件系数矩阵的元素等于0或1。约束条件系数矩阵的每一列有两个1其余都等于0，即每一个变量xij在前m个约束方程中出现1次，在后n个约束方程中出现1次。所有的约束都是等式约束。11‥‥‥111‥‥‥111‥‥‥1‥‥‥11‥‥‥1111111111111‥‥‥‥‥‥1111x11x12‥‥x1nx21x22‥‥x2nx31x32‥‥x3n‥‥‥xm1xm2‥‥xmnm行n行(m+n)×mn系数矩阵AA的m+n-1阶方阵是非奇异的将A的第m行去掉，然后选取下列变量对应

4、的列向量，构成一个m+n-1阶子方阵可以证明：(1)运输问题一定有有限的最优解；为什么？？？(2)运输问题任意m+n-1个约束都是线性独立的，即基可行解应有m+n-1个基变量(a)运输问题目标函数有下界，目标函数值不会趋于负无穷大；(b)令可以验证上述解为运输问题的一个可行解，因此运输问题存在上界。因而，运输问题一定存在有限个最优解。运输问题可行解的表示：m个产地、n个销地的运输问题，除了满足可行的条件外，任何一个基要满足以下条件：基变量的个数为m+n-1即m+n-1个格的运输量不为0(实格)，(m-1)(n-1)个格的运输量为0(空格)。基变量不能形成闭回

5、路运输表：运输问题表上作业法就是基于运输表来展开。销地产地基可行解在运输表中的表示B1B2B3B4A1A2A3B1B2B3B4A1A2A3B1B2B3B4A1A2A3B1B2B3B4123B1B2B3B4A1A2A3B1B2B3B4A1A2A3B1B2B3B4A1A2A3B1B2B3B4123B1B2B3B4A1A2A3B1B2B3B4A1A2A3运输表中同行同列组成回路的变量表上作业法运输问题的求解方法：(1)单纯形法：把运输问题作为标准的线性规划问题来处理，用一般单纯形法来求解。缺点：变量较多，计算时间较长。(2)表上作业法：根据运输问题约束系数

6、矩阵和目标函数构成的特殊性来求解问题。表上作业法运输问题的求解方法：表上作业法基于运输表来求解运输问题销地产地表上作业法表上作业法(其实质是单纯形法)该法分以下几步进行：第一步：找初始基可行解求出初始基可行解。即在m×n产销平衡运输表上给出m+n-1个数字格(基变量)，其它为空格(非基变量)且使基变量对应的系数列向量线性无关；第二步：解的最优性检验求出各非基变量的检验数，判断是否最优，如果是则停止计算，如果不是转下一步；第三步：解的改进确定换入换出变量，找出新的基可行解(即调整运输方案)；重复第二步和第三步直到找到最优解为止。第一步：初始基可

7、行解的确定方法1：最小元素法方法2：西北角法方法3：沃格尔法方法1：最小元素法1.相应的在运输表上对应位置标记出运输量。相应的在运输表上划去不需要再考虑的产地。相应的在运输表上划去不需要再考虑的销地。2.在余下的供销关系(尚未划去的表格)中，继续按照上面的方法安排调运，直至安排完所有的供销任务，得到一个完整的调运方案为止。按照费用矩阵元素cij增加顺序逐个选择引入基本解的变量xij，非退化情况下，每选择1个，就必然排除1个产地或销地，最后一步可一次排除1个产地和1个销地，这样便可得到一个初始基础可行解(m+n-1个基变量)。填有数字的表格对应的为基变量。对于

8、非基变量对应的表格(空格)，不填入数字。例1：某部门