第三章运输问题.ppt

第3章运输问题,第1节运输问题的数学模型第2节表上作业法第3节产销不平衡的运输问题及其求解方法第4节应用举例,引例,某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？,运费表,引例,解：产销平衡问题：总产量=总销量设xij为从产地Ai运往销地Bj的运输量，得到数学模型：,系数矩阵,第1节运输问题的数学模型,系数矩阵A的特点：1、约束条件左边所有系数都是0或1，而且每一列中恰好只有两个元素是1，其他元素都是0。列向量为：,共有mn个Pij。,第1节运输问题的数学模型,2、前m个每行有n个1（其余都是0），从第m+1行到第n行，每行有m个1（其余都是0）。,第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，这些数据可汇总于产销平衡表和单位运价表中，见表3-1，表3-2。有时可把这两表合二为一。,第1节运输问题的数学模型,表3-1,第1节运输问题的数学模型,表3-2,第1节运输问题的数学模型,若用xij表示从Ai到Bj的运量，那么在产销平衡的条件下，要求得总运费最小的调运方案，数学模型,第1节运输问题的数学模型,产销平衡的对偶问题,第1节运输问题的数学模型,这就是运输问题的数学模型。它包含mn个变量，(m+n)个约束方程。其系数矩阵的结构比较松散，且特殊。,第1节运输问题的数学模型,第1节运输问题的数学模型,系数矩阵A的特点：1、约束条件左边所有系数都是0或1，而且每一列中恰好只有两个元素是1，其他元素都是0。列向量为：,共有mn个Pij。,第1节运输问题的数学模型,2、前m个每行有n个1（其余都是0），从第m+1行到第n行，每行有m个1（其余都是0）。,第1节运输问题的数学模型,系数矩阵中对应于变量xij的系数向量Pij，其分量中除第i个和第m+j个为1以外，其余的都为零。即Pij=(0,1,0,0,1,0,0)T=ei+em+j对产销平衡的运输问题，由于有以下关系式存在：,第1节运输问题的数学模型,所以，该模型最多只有m+n-1个独立约束方程，由于有以上特征，求解运输问题时，可用比较简便的计算方法，习惯上称为表上作业法。,第2节表上作业法,表上作业法是单纯形法在求解运输问题时的一种简化方法，其实质是单纯形法。但具体计算和术语有所不同。可归纳为：(1)找出初始基可行解。即在(mn)产销平衡表上（用西北角法、最小元素法，Vogel法）给出m+n-1个数字，称为数字格。它们就是初始基变量的取值。,第2节表上作业法,(2)求各非基变量的检验数，即在表上计算空格的检验数，判别是否达到最优解。如已是最优解，则停止计算，否则转到下一步。(3)确定换入变量和换出变量，找出新的基可行解。在表上用闭回路法调整。(4)重复(2)，(3)直到得到最优解为止。,第2节表上作业法,第2节表上作业法,例1某公司经销甲产品。它下设三个加工厂。每日的产量分别是：A1为7吨，A2为4吨，A3为9吨。该公司把这些产品分别运往四个销售点。各销售点每日销量为：B1为3吨，B2为6吨，B3为5吨，B4为6吨。已知从各工厂到各销售点的单位产品的运价为表3-3所示。问该公司应如何调运产品，在满足各销点的需要量的前提下，使总运费为最少。,第2节表上作业法,解先作出这问题的产销平衡表和单位运价表，见表3-3，表3-4,表3-3单位运价表,第2节表上作业法,表3-4产销平衡表,第2节表上作业法,用线性规划法处理此问题。设由产地i到销地j的运量为xij，模型为：minz=3x11+11x12+3x13+10 x14+x21+9x22+2x23+8x24+7x31+4x32+10 x33+5x34x11+x12+x13+x14=7x21+x22+x23+x24=4x31+x32+x33+x34=9x11+x21+x31=3x12+x22+x32=6x13+x23+x33=5x14+x24+x34=6xij0(i=1,2,3;j=1,2,3,4)运输问题一般用表上作业法求解，需建立表格模型：,第2节表上作业法,2.1确定初始基可行解,这与一般线性规划问题不同。产销平衡的运输问题总是存在可行解。因有,必存在xij0，i=1，m，j=1，n这就是可行解。又因0xijmin(aj，bj)故运输问题必存在最优解。,2.1确定初始基可行解,确定初始基可行解的方法很多，有西北角法，最小元素法和伏格尔(Vogel)法。一般希望的方法是既简便，又尽可能接近最优解。下面介绍两种方法：,1.最小元素法,1.最小元素法这方法的基本思想是就近供应，即从单位运价表中最小的运价开始确定供销关系，然后次小。一直到给出初始基可行解为止。,1.最小元素法,最小元素法的基本步骤：1.找出最小运价，确定供求关系，最大量的供应；2.划掉已满足要求的行或(和)列，如果需要同时划去行和列，必须要在该行或列的任意位置填个“0”；3.在剩余的运价表中重复1、2两步，直到得到初始基可行解。,第2节表上作业法,3,1,1,4,4,3,6,3,3,3,3,1.最小元素法,以例1进行讨论。第一步：从表3-3中找出最小运价为1，这表示先将A2的产品供应给B1。因a2b1，A2除满足B1的全部需要外，还可多余1吨产品。在表3-4的(A2，B1)的交叉格处填上3。得表3-5。并将表3-3的B1列运价划去。得表3-6。,1.最小元素法,表3-5.表3-6,1.最小元素法,第二步：在表3-6未划去的元素中再找出最小运价2，确定A2多余的1吨供应B3，并给出表3-7，表3-8。,1.最小元素法,第三步：在表3-8未划去的元素中再找出最小运价3；这样一步步地进行下去，直到单位运价表上的所有元素划去为止，最后在产销平衡表上得到一个调运方案，见表3-9。这方案的总运费为86元。,总的运输费用（31）（64）（43）（12）（310）（35）86元,1.最小元素法,1.最小元素法,用最小元素法给出的初始解是运输问题的基可行解，其理由为：(1)用最小元素法给出的初始解，是从单位运价表中逐次地挑选最小元素，并比较产量和销量。当产大于销，划去该元素所在列。当产小于销，划去该元素所在行。然后在未划去的元素中再找最小元素，再确定供应关系。,1.最小元素法,这样在产销平衡表上每填入一个数字，在运价表上就划去一行或一列。表中共有m行n列，总共可划(n+m)条直线。但当表中只剩一个元素时，这时当在产销平衡表上填这个数字时，而在运价表上同时划去一行和一列。此时把单价表上所有元素都划去了，相应地在产销平衡表上填了(m+n-1)个数字。即给出了(m+n-1)个基变量的值。,