运筹学07-运输问题

第七章运输问题7.1运输问题的数学模型7.2表上作业法7.3产销不平衡问题5.1运输问题的数学模型(1)运输问题的引入例1有一个地区有两个产棉区A1,A2向三个纺织厂B1B2,B3供应棉花,产棉区每年的供应量分别为70kt和50kt;纺织厂每年的需求量分别为50kt,40kt和30kt.已知各产棉区到各纺织厂的单位运价如左表,问如何安排运输方案,使总运费最小.设由Ai运往Bj的棉花的运量为xij(kt),如右表:销地产地B1B2B3A1A2586438销地产地B1B2B3产量A1A2x11x12x13x21x22x237050销量5040301205.1运输问题的数学模型(1)运输问题的引入由于各个产棉区Ai运往各个纺织厂Bj的总量应该等于它的产量，所以x11+x12+x13=70x21+x22+x23=50另外,由于各个纺织厂收到各个产棉区运输的总量应该等于它的需求量x11+x21=50x12+x22=40x13+x23=30目标是总运费最小，即minz=5x11+8x12+6x13+4x21+3x22+8x23销地产地B1B2B3产量A1A2x11x12x13x21x22x237050销量5040301205.1运输问题的数学模型(1)运输问题的引入此运输问题的数学模型为:minz=5x11+8x12+6x13+4x21+3x22+8x23x11+x12+x13=70x21+x22+x23=50x11+x21=50x12+x22=40x13+x23=30xij≥0(i=1,2;j=1,2,3)5.1运输问题的数学模型(2)运输问题的一般数学模型运输问题的一般描述:m个产地Ai,I=1,2..,m,产量分别为ai个单位,n个产地Bj,j=1,2..,n,产量分别为bj个单位;Ai与Bj之间的单位运价爲Cij,问如何安排运输方案,使总运费最少?销地产地B1B2…Bn产量A1A2…Amc11c12…c1nc21c22…c2n……………………………cm1cm2…cmna1a2…am销量b1b2…bn∑ai=∑bj5.1运输问题的数学模型(2)运输问题的一般数学模型此问题的数学模型:minz=∑∑cijxijs.t∑xij=ai(i=1,2..m)∑xij=bj(j=1,2..n)xij≥0(i=1,2..m,j=1,2..n)i＝1j＝1mn5.2表上作业法模型的矩阵表述表上作业法的计算步骤确定初始基可行解最优解的判别闭回路调整法对于平衡运输问题化成矩阵形式:minz=CX;AX=b;X≥0其中C=(c11,c12,...,C1n,...,cm1,cm2,…,cmn)，b=(a1,a2,…,am,b1,b2,…,bn)T,X=(x11,x12,…,x1n,…,xm1,xm2,…,xmn)T。11…111…1…A=11…111…1111………111R(A)=m+n-15.2.1模型的矩阵表示该系数矩阵中对应于变量xij的系数向量Pij，其分量中除第i个和第m+j个为1外，其余的都为零。即Pij＝(0,0,…,0,1,0,…,0,1,0,…,0)T＝ei+em+j对产销平衡的运输问题，由于有以下关系式存在：∑bj=∑(∑xij)=∑(∑xij)=∑ai所以模型最多只有m+n-1个独立约束方程。即系数矩阵的秩≤m+n-1。5.2.1模型的矩阵表示表上作业法的实质是单纯形法。其计算步骤为：（1）找出初始基可行解。即在（m×n）产销平衡表上给出（m+n—1）个数字格。（2）求各非基变量的检验数。在表上即是空格的检验数。判别是否达到最优解。如果已经是最优解，则停止计算，否则转到下一步。（3）确定换入变量和换出变量，找出新的基可行解。在表上用闭回路法调整。（4）重复（2），（3）直到得到最优解(肯定存在)为止。以上运算都可以在表上进行。5.2.2表上作业法的矩阵表示步骤详解（例2）例2设某物资从A1,A2,A3处运往B1,B2,B3,B4处,各处供应量,需求量及单位运价见下表。问如何安排运输方案,才能使总运费最少?销地产地B1B2B3B4供应量A137645A224322A343853需求量323210最小元素法伏格尔（Vogel）法5.2.3确定初始基可行解最小元素法根据单位运价最低处优先供应的原则依次安排运输量最小元素法销地产地B1B2B3B4供应量A137645A224322A343853需求量323210单位运价最小元素法销地产地B1B2B3B4供应量A137645A2224322A343853需求量323210最小元素法销地产地B1B2B3B4供应量A1317645A2224322A343853需求量323210最小元素法销地产地B1B2B3B4供应量A1317645A2224322A3432853需求量323210最小元素法销地产地B1B2B3B4供应量A13176425A2224322A3432853需求量323210最小元素法销地产地B1B2B3B4供应量A131762425A2224322A3432853需求量323210最小元素法销地产地B1B2B3B4供应量A131762425A2224322A34328153需求量323210最小元素法销地产地B1B2B3B4供应量A11225A222A3213需求量323210运量初始基可行解伏格尔（Vogel）法（推荐）比较最小运费与次小运费的差额，在差额最大处，采用最小运费调运。最小元素法的缺点是为了节省一处的费用，有时候造成在其它地方要多化几倍的运费。伏格尔（Vogel）法销地产地B1B2B3B4供应量A137645A224322A343853需求量323210运价行差额运价列差额伏格尔（Vogel）法销地产地B1B2B3B4行差额供应量A1376415A2243202A3438513运价列差额1132需求量323210伏格尔（Vogel）法销地产地B1B2B3B4行差额供应量A1376415A22432202A3438513运价列差额1132需求量323210伏格尔（Vogel）法销地产地B1B2B3B4行差额供应量A1376415A2243222A34328513运价列差额1421需求量323210伏格尔（Vogel）法销地产地B1B2B3B4行差额供应量A13761415A2243222A34328513运价列差额121需求量323210伏格尔（Vogel）法销地产地B1B2B3B4行差额供应量A133761415A2243222A34328513运价列差额11需求量323210伏格尔（Vogel）法销地产地B1B2B3B4行差额供应量A133761445A2243222A343285153运价列差额1需求量323210伏格尔（Vogel）法销地产地B1B2B3B4行差额供应量A133761445A2243222A34328513运价列差额4需求量323210伏格尔（Vogel）法销地产地B1B2B3B4行差额供应量A1337614145A2243222A34328513运价列差额4需求量323210伏格尔（Vogel）法销地产地B1B2B3B4供应量A13115A222A3213需求量323210初始基可行解闭回路法位势法判别的方法是计算空格（非基变量）的检验数C-CBB-1A。因运输问题的目标函数是要求实现最小化，故当所有的C-CBB-1A≥0时，得最优解。5.2.4最优解的判别§3.2.4.1闭回路法闭回路法:Xij对应的检验数σij=(闭回路上的偶数顶点运价之和－闭回路上的奇数顶点运价之和)闭回路:以某空格为起点，用水平或垂直线向前划，每(?)碰到一数字格转90度后，继续前进，直到回到起始空格为止，得到一个闭回路。从每一个空格出发一定存在和可以找到一个惟一的闭回路。（非基变量对应的系数列向量由基唯一地线性表示）闭回路法销地产地B1B2B3B4供应量A11+12-125A22-1+12A3213需求量323210闭回路法销地产地B1B2B3B4供应量A11+1372-16245A22-124+1-2322A34231853需求量323210闭回路法销地产地B1B2B3B4供应量A11+1372-16245A22-124+1-2322A34231853需求量323210σ23=3-6+3-2=-2闭回路法销地产地B1B2B3B4供应量A1103672062045A220244-23-122A3-14203108-153需求量323210位势法（推荐）设u1,u2,…,um;v1,v2,…,vn是对应运输问题的m+n个约束条件的对偶变量。B是含有一个人工变量xa的(m+n)×(m+n)初始基矩阵。人工变量在目标函数中的系数ca＝0，从线性规划的对偶理论可知：CBB-1＝(u1,u2,…,um;v1,v2,…,vn)而每个决策变量xij的系数向量Pij=ei+em+j，所以CBB-1Pij=ui＋vj。于是检验数σij＝cij－CBB-1Pij=cij－（ui＋vj）当xij为基变量时，有cij－（ui＋vj）=0,即ui＋vj＝cij非基变量的检验数为：σij＝cij－（ui＋vj）其中cij为对应的运价，称ui为对应的行位势，vj为对应的列位势。位势法（步骤）位势法：第一步：给出初始解，在对应的数字格处填入单位运价。第二步：在表中增加一行一列，在列中填入u1,u2,…,um，在行中填入v1,v2,…,vn。先取定一个数u1=0，根据ui＋vj＝cij求得各个ui和vj值。第三步：再根据σij＝cij－（ui＋vj）求得非基变量（空格）的检验数。位势法(第一步)销地产地B1B2B3B4uiA11372624A222432A3423185vj位势法(第二步)销地产地B1B2B3B4uiA113726240A222432A3423185vj位势法(第二步)【演排】销地产地B1B2B3B4uiA113726240A222432A3423185vj位势法(第二步)销地产地B1B2B3B4uiA113726240A222432-1A34231852vj3164位势法(第三步)【演排】销地产地B1B2B3B4uiA113726240A222432-1A34231852vj3164位势法(第三步)销地产地B1B2B3B4uiA1103672062040A220244-23-12-1A3-14203108-152vj3164观察与思考闭回路法与位势法所得的检验数是一样的，但位势法更简便一些。闭回路调整法调整量θ=min(闭回路上的奇数顶点运量)（其原理与单纯形法中按最小比值规则来确定换出变量相同。）一般选择其中最小的负检验数，以它对应的空格为调入格。（即以它对应的非基变量为换入变量。）闭回路调整法销地产地B1B2B3B4uiA1103672062040A220244-23-12-1A3-14203108-152vj3164调入格（换入变量）闭回路调整法（调整过程）销地产地B1B2B3B4uiA11+203672-2062040A22-20244+2-23-12-1A3-14203108-152vj3164调出格（换出变量）闭回路调整法销地产地B1B2B3B4uiA13370624A224232A3423185vj闭回路调整法（退化解）说明：（1）在用闭回路法调整时，若在闭回路上出现两个或两个以上的奇数顶点的相等的最小值，这时只能选择其中一个作为调入格。而经调整后，得到退化解。这时有一个数字格必须填入一个零，表明它是基变量。（2）得到新的调整方案（新的解）后，再用闭回路法或位势法求各空格的检验数。（3）若仍有检验数为负，则继续调整。若所有检验数都非负，则表中的解为最优解。闭回路调整法[演排]销地产地B1B2B3B4uiA133706240A224232A3423185vj闭回路调整法销地产地B1B2B3B4uiA133706240A224232-3A342