49运输问题

2020/1/241一、运输问题的数学模型例：某运输问题的资料如下：单位销地运价产地B1B2B3B4产量A1291029A213425A384257销量38462020/1/242)4.3.2.1,3.2.1(06483759524824371092min342414332313322212312111343332312423222114131211343332312423222114131211jixxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxZxijij约束条件：目标函数：为运量设某种物品有m个产地A1,A2,…,Am，各产地的产量分别是a1,a2,…,am；有n个销地B1,B2,…,Bn，各销地的销量分别为b1,b2,…,bn。假设从产地Ai(i=1,2,…,m)向销地Bj(j=1,2,…,n)运输单位物品的运价是cij，怎样调运这些物品才能使总运费最小？B1B2…Bnc11c12…c1nA1x11x12…x1na1c21c22…c2nA2x21x22…x2na2…………………………cm1cm2…cmnAmxm1xm2…xmnamb1b2…bn运输问题的数学模型111111min..1,2,...,1,2,...,01,2,...,;1,2,...,mnijijijnijijmijjimnijijijZcxstxaimxbjnabximjn　　　，　　　，　　　　　，min..0ZcxstAxdx　　2020/1/245运输问题数学模型的特点1.运输问题有有限个最优解2.运输问题约束条件的特点：运输问题的数学模型包含m×n个变量，(m+n)个约束方程，其系数矩阵的结构比较松散且特殊。行行nmvvvuuuxxxxxxxxxnmmnmmnn11111111111111111121212122221112112020/1/246运输问题的解运输问题也是一个线性规划问题，其求解时仍然可以先找一个基可行解，进行解的最优性检验，若不是最优，就进行迭代，继续检验和调整直到最优，因此要求每步得到的解都是基可行解，需满足(1)满足所有约束条件；(2)基变量对应的系数列向量线性无关；(3)解中非零变量的个数不能大于m+n-1个，原因是运输问题中虽有m+n个约束条件，但由于总产量等于总销量，故只有m+n-1个约束条件是线性独立的；(4)保持基变量的个数在迭代过程中为m+n-1个。2020/1/247二、表上作业法表上作业法是单纯形法在求解运输问题时的一种简化方法，其实质是单纯形法,但具体计算和术语有所不同，其步骤可归纳为：(1)找出初始基可行解：即在(m×n)产销平衡表上用最小元素法或西北角法给出m+n-1个数字，称为数字格，它们就是初始基变量的取值。(2)求各非基变量的检验数，即在表上计算空格的检验数，判别是否达到最优解。如已是最优解，则停止计算，否则转到下一步。(3)确定换入变量和换出变量，找出新的基可行解。在表上用闭回路法调整。(4)重复(2)，(3)直到得到最优解为止。确定初始方案(初始基本可行解)改进调整（换基迭代）否判定是否最优？是结束最优方案运输问题求解思路图（一）初始基本可行解的确定例2：甲、乙两个煤矿供应A、B、C三个城市用煤，各煤矿产量及各城市需煤量、各煤矿到各城市的运输单价见表所示，求使总运输费用最少的调运方案。例题有关信息表450200150100日销量（需求量）250756580乙2001007090甲日产量（供应量）CBA运距城市煤矿例题数学模型;3,2,1;2,1,0200150100250200..7565801007090min231322122111232221131211232221131211jixxxxxxxxxxxxxtsxxxxxxZij需求约束日产量约束总运输量（1）最小元素法：从运价最小的格开始，在格内标上允许取得的最大数。然后按运价从小到大顺序填数。若某行（列）的产量（销量）已满足，则把该行（列）的其他格划去。如此进行下去，直至得到一个基本可行解。调销地运量产地B1B2B3产量A190X1170X12100X13200A280X2165X2275X23250销量100150200450用最小元素法确定初始调运方案150100100100100100100得到初始调运方案为：x11=100，x13=100，x22=150，x23=10038750100*100150*65100*100100*90总运价为：2020/1/2415练习单位销地运价产地产量311310719284741059销量3656产销平衡321AAA例：某食品公司下属的A1、A2、A3，3个厂生产方便食品，要运输到B1、B2、B3、B4，4个销售点，数据如下：用表上作业法求最初运输方案。4321BBBB2020/1/2416B1B2B3B4产量A17,3,0A24,1,0A39销量3,06,05,1,06,3,0311310192741058341633总的运输费用＝（3×1）＋（6×4）＋（4×3）＋（1×2）＋（3×10）＋（3×5）＝86元（2）西北角法不是优先考虑具有最小单位运价的供销业务，而是优先满足运输表中西北角（左上角）上空格的供销要求调销地运量产地B1B2B3产量A190X1170X12100X13200A280X2165X2275X23250销量100150200450用西北角法确定初始调运方案1001001005050200200得到初始调运方案为：x11=100，x12=100，x22=50，x23=20039250100*20065*50100*70100*90总运价为：（二）最优性检验根据最小元素法或西北角法求得运输问题的初始基可行解之后，按照表上作业法的第二步，下面需对这个解进行最优性判别，看它是否为本运输问题的最优解.思路：要判定运输问题的初始基可行解是否为最优解，可仿照一般单纯形法，检验这个解的各非基变量（对应于运输表中的空格）的检验数。检验数：运输问题中非基变量（对应于空格）的检验数定义为给某空格增加单位运量导致总费用的增加量。如果有某空格（Ａi、Bj）的检验数为负，说明将Xij变为基变量将使运输费用减少，故当前这个解不是最优解。若所有空格的检验数全为非负，则不管怎样变换，均不能使运输费用降低，即目标函数值已无法改进，这个解就是最优解。闭回路：在给出的调运方案的运输表上，从一个空格（非基变量）出发，沿水平或垂直方向前进，只有碰到代表基变量的数字格才能向左或向右转90°继续前进，直至最终回到初始空格而形成的一条回路。从每一空格出发，一定可以找到一条且只存在唯一一条闭回路。１、闭回路法以xij空格为第一个奇数顶点，沿闭回路的顺（或逆）时针方向前进，对闭回路上的每个折点依次编号；非基变量xij的检验数：现在，在用最小元素法确定例2初始调运方案的基础上，计算非基变量X12的检验数：ij=（闭回路上奇数次顶点运距或运价之和）-（闭回路上偶数次顶点运距或运价之和）调销地运量产地B1B2B3产量A190X1170X12100X13200A280X2165X2275X23250销量100150200450100100100150初始调运方案中以X12(X21)为起点的闭回路非基变量X12的检验数：非基变量X21的检验数：=（c12+c23）-（c13+c22）=70+75-（100+65）=-20，12=（c21+c13）-（c11+c23）=80+100-（90+75）=15。21经济含义：在保持产销平衡的条件下，该非基变量增加一个单位运量而成为基变量时目标函数值的变化量。2、对偶变量法（位势法）检验数公式：分别表示前m个约束等式对应的对偶变量；分别表示后n个约束等式对应的对偶变量。jiijijvuc(1,2,)iuimL，(1,2,)jvjnL，初始调运方案对偶变量对应表调销地运量产地B1B2B3产量A190X1170X12100X13200A280X2165X2275X23250销量100150200450对偶变量vjv1v2v3100100100150对偶变量uiu1u2以初始调运方案为例，设置对偶变量和，然后构造下面的方程组：iujv7565100902332222213311111cvucvucvucvu在式中，令u1=0，则可解得v1=90，v3=100，u2=-25，v2=90，于是σ12=c12-（u1+v2）=70-（0+90）=-20σ21=c21-（u2+v1）=80-（-25+90）=15与前面用闭回路法求得的结果相同。方程组的特点：方程个数是m+n-1=2+3-1=4个，对偶变量共有m+n=2+3=5。初始方案的每一个基变量xij对应一个方程——-—所在行和列对应的对偶变量之和等于该基变量对应的运距（或运价）：ui+vj=cij；方程组恰有一个自由变量，可以证明方程组中任意一个变量均可取作自由变量。这个时候方程的解可以称为位势。在式中，令u1=0，则可解得v1=90，v3=100，u2=-25，v2=90，于是σ12=c12-（u1+v2）=70-（0+90）=-20σ21=c21-（u2+v1）=80-（-25+90）=15与前面用闭回路法求得的结果相同。位势法计算非基变量xij检验数的公式σij=cij-（ui+vj）ij=（闭回路上奇数次顶点运距或运价之和）-（闭回路上偶数次顶点运距或运价之和）闭回路法计算非基变量xij检验数的公式：复习比较检验数计算的两种方法2020/1/2433练习销地加工厂B1B2B3B4产量A1311341037A21392184A374610539销量36562020/1/2434空格闭回路检验数(11)(12)(22)(24)(31)(33)(11)-(13)-(23)-(21)-(11)(12)-(14)-(34)-(32)-(12)(22)-(23)-(13)-(14)-(34)-(32)-(22)(24)-(23)-(13)-(14)-(24)(31)-(34)-(14)-(13)-(23)-(21)-(31)(33)-(34)-(14)-(13)-(33)121-11012（三）解的改进——闭回路调整法如检验出初始解不是最优解，即某非基变量检验数为负，说明将这个非基变量变为基变量时运费会下降。根据表上作业法的第三步，需对初始方案进行改进。解改进的步骤1．（如存在多个非基变量的检验数为负时，以最小负检验数所在空格对应的变量）为换入变量，找出它在运输表中的闭回路；2．以这个空格为第一个奇数顶点，沿闭回路的顺（或逆）时针方向前进，对闭回路上的每个折点依次编号；3．在闭回路的所有偶数折点中，找出运输量最小的一个折点，以该格中的变量为换出变量；4．将闭回路上所有奇数折点的运输量都增加这一换出变量值，所有偶数折点处的运输量都减去这一数值，最终得出一个新的运输方案。对得出的新方案再进行最优性检验，如不是最优解，就重复以上步骤继续进行调整，一直到得出最优解为止。调销地运量产地B1B2B3产量A190X1170X12100X13200A280X2165X2275X23250销量100150200450100100100150++--因σ12=-20，画出以x12为起始变量的闭回路020050100计算调整量：ε=Min（100，150）=100。按照下面的方法调整调运量：闭回路上，奇数次顶点的调运量加上ε，偶数次顶点的调运量减去ε；闭回路之外的变量调运量不变。得到新的调运方案：调销地运量产地B