运筹学第4章表上作业法.

第2章线性规划与单纯形法第3章对偶理论与灵敏度分析第4章运输问题第5章线性目标规划第4章运输问题第1节运输问题的数学模型第2节表上作业法第3节产销不平衡的运输问题及其求解方法第4节应用举例2第1节运输问题的数学模型销地产地12┉n12┆mC11c12┈c1nC21c22┈c2n┇cm1cm2┈cmn已知有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。有时可把这两表合二为一。销地产地12┉n产量12┆mA1A2┆Am销量B1B2┈BNn第1节运输问题的数学模型0)23(,,2,1)13(,,2,1..min1111ijnjijijmijijminjijijxmiaxnjbxtsxcz4若用xij表示从Ai到Bj的运量，那么在产销平衡的条件下，要求得总运费最小的调运方案的数学模型为第1节运输问题的数学模型行行nmvvvuuuxxxxxxxxxnmmnmmnn11111111111111111121212122221112115这就是运输问题的数学模型。它包含m×n个变量，(m+n)个约束方程，其系数矩阵的结构比较松散，且特殊。第1节运输问题的数学模型njminjmiimiijnjijjaxxb1111116该系数矩阵中对应于变量xij的系数向量Pij，其分量中除第i个和第m+j个为1以外，其余的都为零。即Pij=(0,…,1,0,…,0,1,0,…,0)T=ei+em+j对产销平衡的运输问题，由于有以下关系式存在：第2节表上作业法•表上作业法是单纯形法在求解运输问题时的一种简化方法，其实质是单纯形法。但具体计算和术语有所不同。可归纳为：•(1)找出初始基可行解。即在(m×n)产销平衡表上用西北角法或最小元素法，Vogel法给出m+n-1个数字，称为数字格。它们就是初始基变量的取值。。•(2)求各非基变量的检验数，即在表上计算空格的检验数，判别是否达到最优解。如已是最优解，则停止计算，否则转到下一步。•(3)确定换入变量和换出变量，找出新的基可行解。在表上用闭回路法调整。•(4)重复(2)，(3)直到得到最优解为止。7第2节表上作业法•例1某公司经销甲产品。它下设三个加工厂。每日的产量分别是：A1为7吨，A2为4吨，A3为9吨。该公司把这些产品分别运往四个销售点。各销售点每日销量为：B1为3吨，B2为6吨，B3为5吨，B4为6吨。已知从各工厂到各销售点的单位产品的运价为表3-3所示。问该公司应如何调运产品，在满足各销点的需要量的前提下，使总运费为最少。8第2节表上作业法•解：先作出这问题的产销平衡表和单位运价表，见表3-3，表3-4销地加工厂B1B2B3B4A1A2A3317119432101085销地加工厂B1B2B3B4产量A1A2A3749销量36569表3-4产销平衡表表3-3单位运价表2.1确定初始基可行解minjjidba1110与一般线性规划问题不同，产销平衡的运输问题总是存在可行解。因有必存在xij≥0，i=1，…，m，j=1，…，n，这就是可行解。又因0≤xij≤min(aj，bj)，故运输问题必存在最优解。2.1确定初始基可行解11确定初始基可行解的方法很多，有西北角法，最小元素法和伏格尔(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确定初始基可行解销地加工厂B1B2B3B4产量A1A2A33749销量3656销地加工厂B1B2B3B4A1A2A331711943210108512表3-5和表3-62.1确定初始基可行解销地加工厂B1B2B3B4产量A1A2A331749销量3656销地加工厂B1B2B3B4A1A2A331711943210108513第二步：在表3-6未划去的元素中再找出最小运价2，确定A2多余的1吨供应B3，并给出表3-7，表3-8。2.1确定初始基可行解销地加工厂B1B2B3B4产量A1A2A3364133749销量365614第三步：在表3-8未划去的元素中再找出最小运价3；这样一步步地进行下去，直到单位运价表上的所有元素划去为止，最后在产销平衡表上得到一个调运方案，见表3-9。这方案的总运费为86元。2.1确定初始基可行解15用最小元素法给出的初始解是运输问题的基可行解，其理由为：(1)用最小元素法给出的初始解，是从单位运价表中逐次地挑选最小元素，并比较产量和销量。当产大于销，划去该元素所在列。当产小于销，划去该元素所在行。然后在未划去的元素中再找最小元素，再确定供应关系。这样在产销平衡表上每填入一个数字，在运价表上就划去一行或一列。表中共有m行n列，总共可划(n+m)条直线。但当表中只剩一个元素时，这时当在产销平衡表上填这个数字时，而在运价表上同时划去一行和一列。此时把单价表上所有元素都划去了，相应地在产销平衡表上填了(m+n-1)个数字。即给出了(m+n-1)个基变量的值。2.1确定初始基可行解1111jmijieeP11jix11jiP16用最小元素法给出的初始解是运输问题的基可行解，其理由为：(2)这(m+n-1)个基变量对应的系数列向量是线性独立的。证若表中确定的第一个基变量为它对应的系数列向量为:因当给定的值后，将划去第i1行或第j1列，即其后的系数列向量中再不出现ei1或em+j1，因而不可能用解中的其他向量的线性组合表示。类似地给出第二个，…，第(m+n-1)个。这(m+n-1)个向量都不可能用解中的其他向量的线性组合表示。故这(m+n-1)个向量是线性独立的。2.1确定初始基可行解17用最小元素法给出初始解时，有可能在产销平衡表上填入一个数字后，在单位运价表上同时划去一行和一列。这时就出现退化。关于退化时的处理将在2.4节中讲述。销地产地B1B2B3B4产量A116A210A322销量8141214484285101112346911①8②2③10④14⑤8⑥⑥6课堂练习总费用z==10×4+6×11+8×2+2×3+14×5+8×6=24634i=1j=1cijijx2.1确定初始基可行解192.伏格尔法最小元素法的缺点是：为了节省一处的费用，有时造成在其他处要多花几倍的运费。伏格尔法考虑到，一产地的产品假如不能按最小运费就近供应，就考虑次小运费，这就有一个差额。差额越大，说明不能按最小运费调运时，运费增加越多。因而对差额最大处，就应当采用最小运费调运。2.1确定初始基可行解销地加工厂B1B2B3B4行差额A1A2A3317119432101085011列差额251320伏格尔法的步骤是：第一步：在表3-3中分别计算出各行和各列的最小运费和次最小运费的差额，并填入该表的最右列和最下行，见表3-10。2.1确定初始基可行解销地加工厂B1B2B3B4产量A1A2A36749销量365621第二步：从行或列差额中选出最大者，选择它所在行或列中的最小元素。在表3-10中B2列是最大差额所在列。B2列中最小元素为4，可确定A3的产品先供应B2的需要。得表3-112.1确定初始基可行解销地加工厂B1B2B3B4行差额A1A2A3317119432101085012列差额21322同时将运价表中的B2列数字划去。如表3-12所示。2.1确定初始基可行解销地加工厂B1B2B3B4产量A1A2A3365213749销量365623第三步：对表3-12中未划去的元素再分别计算出各行、各列的最小运费和次最小运费的差额，并填入该表的最右列和最下行。重复第一、二步。直到给出初始解为止。用此法给出例1的初始解列于表3-13。2.1确定初始基可行解24由以上可见：伏格尔法同最小元素法除在确定供求关系的原则上不同外，其余步骤相同。伏格尔法给出的初始解比用最小元素法给出的初始解更接近最优解。本例用伏格尔法给出的初始解就是最优解。沃格尔法•罚数=次小费用-最小费用•找出最大的罚数行或列所对应的最小费用优先安排。•重复计算步骤1和2销地产地B1B2B3B4产量行罚数12345A116A210A322销量814121448列罚数123454101211346911285201513221011321148810217062201242总费用z==24434i=1j=1cijijx结束语•随我国物流业的兴起，现已有专门的学科和专业，从事研究和教学。并有相应的学会和网站。是一个广阔的领域。27