资源描述：
《吉林大学本科运筹学运输问题ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第3章运输问题第1节运输问题的数学模型第2节表上作业法第3节产销不平衡的运输问题及其求解方法第4节应用举例第1节运输问题的数学模型已知有m个生产地点Ai,i=1,2,…，m。可供应某种物资，其供应量(产量)分别为ai，i=1，2，…，m，有n个销地Bj，j=1,2,…,n，其需要量分别为bj，j=1,2,…,n，从Ai到Bj运输单位物资的运价(单价)为cij，这些数据可汇总于产销平衡表和单位运价表中，有时可把这两表合二为一。销地产地12┉n产量12┆mA1A2┆Am销量B1B2┈BNn第1节运输问题的数学模型若用xij表示从Ai到Bj
2、的运量，那么在产销平衡的条件下，要求得总运费最小的调运方案的数学模型为第1节运输问题的数学模型这就是运输问题的数学模型。它包含m×n个变量，(m+n)个约束方程，其系数矩阵的结构比较松散，且特殊。第1节运输问题的数学模型该系数矩阵中对应于变量xij的系数向量Pij，其分量中除第i个和第m+j个为1以外，其余的都为零。即Pij=(0,…,1,0,…,0,1,0,…,0)T=ei+em+j对产销平衡的运输问题，由于有以下关系式存在：第2节表上作业法表上作业法是单纯形法在求解运输问题时的一种简化方法，其实质是单纯形法。但具体计算和术语有所不
3、同。可归纳为：(1)找出初始基可行解。即在(m×n)产销平衡表上用西北角法或最小元素法、Vogel法给出m+n-1个数字，称为数字格。它们就是初始基变量的取值。(2)求各非基变量的检验数，即在表上计算空格的检验数，判别是否达到最优解。如已是最优解，则停止计算，否则转到下一步。(3)确定换入变量和换出变量，找出新的基可行解。在表上用闭回路法调整。(4)重复(2)，(3)直到得到最优解为止。第2节表上作业法例1某公司经销甲产品。它下设三个加工厂。每日的产量分别是：A1为7吨，A2为4吨，A3为9吨。该公司把这些产品分别运往四个销售点。各销
4、售点每日销量为：B1为3吨，B2为6吨，B3为5吨，B4为6吨。已知从各工厂到各销售点的单位产品的运价为表3-3所示。问该公司应如何调运产品，在满足各销点的需要量的前提下，使总运费为最少。第2节表上作业法解：先作出这问题的产销平衡表和单位运价表，见表3-3，表3-4表3-4产销平衡表表3-3单位运价表2.1确定初始基可行解与一般线性规划问题不同，产销平衡的运输问题总是存在可行解。因有存在xij=aibj/Q，i=1，…，m，j=1，…，n，这就是可行解。又因目标函数有下界，故运输问题必存在最优解。2.1确定初始基可行解确定初始基可行解
5、的方法很多，有西北角法，最小元素法和伏格尔(Vogel)法。一般希望的方法是既简便，又尽可能接近最优解。下面介绍两种方法：1.最小元素法基本思想是就近供应，即从单位运价表中最小的运价开始确定供销关系，然后次小。一直到给出初始基可行解为止。以例1进行讨论。第一步：从表3-3中找出最小运价为1，这表示先将A2的产品供应给B1。因a2＞b1，A2除满足B1的全部需要外，还可多余1吨产品。在表3-4的(A2，B1)的交叉格处填上3。得表3-5。并将表3-3的B1列运价划去。得表3-6。2.1确定初始基可行解表3-5和表3-62.1确定初始基可
6、行解第二步：在表3-6未划去的元素中再找出最小运价2，确定A2多余的1吨供应B3，并给出表3-7，表3-8。2.1确定初始基可行解第三步：在表3-8未划去的元素中再找出最小运价3；这样一步步地进行下去，直到单位运价表上的所有元素划去为止，最后在产销平衡表上得到一个调运方案，见表3-9。这方案的总运费为86元。2.1确定初始基可行解2.伏格尔法最小元素法的缺点是：为了节省一处的费用，有时造成在其他处要多花几倍的运费。伏格尔法考虑到，一产地的产品假如不能按最小运费就近供应，就考虑次小运费，这就有一个差额。差额越大，说明不能按最小运费调运时
7、，运费增加越多。因而对差额最大处，就应当采用最小运费调运。2.1确定初始基可行解伏格尔法的步骤是：第一步：在表3-3中分别计算出各行和各列的最小运费和次最小运费的差额，并填入该表的最右列和最下行，见表3-10。2.1确定初始基可行解第二步：从行或列差额中选出最大者，选择它所在行或列中的最小元素。在表3-10中B2列是最大差额所在列。B2列中最小元素为4，可确定A3的产品先供应B2的需要。得表3-112.1确定初始基可行解同时将运价表中的B2列数字划去。如表3-12所示。2.1确定初始基可行解第三步：对表3-12中未划去的元素再分别计算
8、出各行、各列的最小运费和次最小运费的差额，并填入该表的最右列和最下行。重复第一、二步。直到给出初始解为止。用此法给出例1的初始解列于表3-13。2.1确定初始基可行解由以上可见：伏格尔法同最小元素法除在确定供求关系的原则
