运筹学课件ch3运输问题.ppt

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

1、运输问题的表示网络图、线性规划模型、运输表初始基础可行解西北角法、最小元素法非基变量的检验数闭回路法、位势法确定进基变量，调整运量，确定离基变量第三章运输问题TransportationProblem2021/9/26运筹学课件一.运输问题的一般提法人们在从事生产活动中，不可避免地要进行物资调运工作。如某时期内将生产基地的煤、钢铁、粮食等各类物资，分别运到需要这些物资的地区，根据各地的生产量和需要量及各地之间的运输费用，如何制定一个运输方案，使总的运输费用最小。这样的问题称为运输问题。2021/

2、9/26运筹学课件典型范例各工厂应分別运送多少数量至各配送中心，才能使总的运输成本最低？供给及需求单位：1卡车的量单位运输成本：千元工厂配送中心供给W1W2W3W4P1675314P2842727P35910619需求2213121360运价表2021/9/26运筹学课件2321341运输问题网络图s2=27s3=19d1=22d2=13d3=12d4=13s1=14供应量供应地运价需求量需求地67538427591062021/9/26运筹学课件运输问题线性规划模型供应地约束需求地约束设xij

3、(i=1,2,3；j=1,2,3,4)为i个工厂运往第j个配送中心的运量，这样得到下列运输问题的数学模型：2021/9/26运筹学课件运输问题的表格表示2021/9/26运筹学课件运输问题的一般提法是：1.产销平衡问题已知：m个产地（记作A1，A2，A3,…,Am），其产量分别为a1,a2，…，am；n个销地（记作B1，B2，…，Bn），其需要量分别为b1,b2，…，bn；且产销平衡，即。从第i个产地到j个销地的单位运价为cij，问：在满足各地需要的前提下，求总运输费用最小的调运方案。即Ai——

4、Bj的运量xij使2021/9/26运筹学课件2.产销不平衡问题此时分为两种情形来考虑：供不应求：即产量小于销量时有供过于求：即产量大于销量时有2021/9/26运筹学课件二.运输问题的模型产销平衡问题模型2021/9/26运筹学课件将约束方程式展开可得约束方程式中共mn个变量，m+n个约束。2021/9/26运筹学课件上述模型是一个线性规划问题。但是其结构很特殊，特点如下：1.变量多（mn个），但结构简单。技术系数矩阵2021/9/26运筹学课件系数矩阵的特点:(1)约束条件的系数矩阵的元素

5、只有两个:0,1.(2)元素xij对应于每一个变量在前m个约束方程中(第i个方程中)出现一次,在后n个约束方程中(第m+j个方程中)也出现一次.(3)产销平衡问题为等式约束.(4)产销平衡问题中各产地产量之和与各销售地点的销量之和相等.2021/9/26运筹学课件2.m+n个约束中有一个是多余的（因为其间含有一个平衡关系式）所以R(A)=m+n-1，即解的mn个变量中基变量为m+n-1个。3.m+n－1个变量组构成基变量的充要条件是它不包含任何闭回路。一条回路中的顶点数一定是偶数。2021

6、/9/26运筹学课件【证】因为产销平衡，即，将前m个约束方程两边相加得再将后n个约束相加得显然前m个约束方程之和等于后n个约束方程之和，m+n个约束方程是相关的，系数矩阵【定理1】设有m个产地n个销地且产销平衡的运输问题，则基变量数为m+n-1。2021/9/26运筹学课件中任意m+n阶子式等于零，取第一行到m+n－1行与对应的列（共m+n-1列）组成的m+n－1阶子式m行n行2021/9/26运筹学课件故r(A)=m+n－1所以运输问题有m+n－1个基变量。为了在mn个变量中找出m+n－1个变

7、量作为一组基变量，就是要在A中找出m+n-1个线性无关的列向量，通常引用闭回路的概念寻找这些基变量。2021/9/26运筹学课件三.运输问题的解法运输问题仍然是线性规划问题，可以用线性规划法中的单纯形法来解决。但是：1.运输问题所涉及的变量多，造成单纯形表太大；2.若把技术系数矩阵A中的0迭代成非0，会使问题更加复杂。以上两个原因使得我们不得不利用运输问题的特点设计出它的特殊解法——表上作业法。2021/9/26运筹学课件运输单纯形法也称为表上作业法，是直接在运价表上求最优解的一种方法，它的步骤

8、是：第一步：求初始基行可行解（初始调运方案）。常用的方法有最小元素法、元素差额法（Vogel近似法）、左上角法。第二步：求检验数并判断是否得到最优解。常用求检验的方法有闭回路法和位势法，当非基变量的检验数σij全都非负时得到最优解，若存在检验数λlk<0，说明还没有达到最优，转第三步。第三步：调整运量，即换基。选一个变量出基，对原运量进行调整得到新的基可行解，转入第二步。表上作业法2021/9/26运筹学课件左上角法(亦称西北角法)是优先从运价表的左上角的变量赋值，当行或列分配完毕后，再在表中余