第七章_运输问题(1表上作业)

第七章运输问题TransportationProblem第七章运输问题运输问题在工商管理中有着广泛的应用，是一类重要的和特殊的线性规划问题。由于这类线性规划问题在结构上有特殊性，所以有专门的解法——表上作业法等，用以简便求解这类问题。管理运筹学软件中也为求解这类问题编制了专门的程序供我们使用。第七章运输问题7.1运输问题的模型§7.1运输问题的模型例1.某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问应如何调运可使总运输费用最小？运费单价销地产地B1B2B3产量(件)A1646200A2655300销量(件)150150200§7.1运输问题的模型解：这是一个产销平衡问题：总产量=总销量=500。设xij为从产地Ai运往销地Bj的运输量，如：x12表示从产地A1运往销地B2的运输数量。于是我们得到新的综合表格：运费单价销地产地B1B2B3产量(件)A1646200A2655300销量(件)150150200§7.1运输问题的模型解：这是一个产销平衡问题：总产量=总销量=500。设xij为从产地Ai运往销地Bj的运输量，如：x12表示从产地A1运往销地B2的运输数量。于是我们得到新的综合表格：运费单价销地产地办运输量B1B2B3产量(件)A16x114x126x13200A26x215x225x23300销量(件)150150200500500运费单价销地产地办运输量B1B2B3产量(件)A16x114x126x13200A26x215x225x23300销量(件)150150200500500minf=6x11+4x12+6x13+6x21+5x22+5x23s.t.x11+x12+x13=200x21+x22+x23=300x11+x21=150x12+x22=150x13+x23=200xij≥0(i=1，2；j=1，2，3）。解得：minf=2500，x11=50，x12=150，x13=0，x21=100，x22=0，x23=200。§7.1运输问题的模型1.一般运输问题的线性规划模型假设A1，A2，…，Am表示某物资的m个产地；B1，B2，…，Bn表示某物资的n个销地；si表示产地Ai的产量；dj表示销地Bj的销量；cij表示把物资从产地Ai运往销地Bj的单位运价。如果s1+s2+…+sm=d1+d2+…+dn，称该运输问题是产销平衡的；否则，称它是产销不平衡的。§7.1运输问题的模型销地产地B1B2…Bn产量A1c11x11c12x12…c1nx1ns1A2c21x21c22x22…c2nx2ns2┇┇┇┇┇┇Amcm1xm1cm2xm2…cmnxmnsm销量d1d2…dn§7.1运输问题的模型设xij为从产地Ai运往销地Bj的运输量，则对于产销平衡问题，可得到下列运输问题的模型：mnminf=cijxiji=1j=1ns.t.xij=sii=1,2,…,mj=1mxij=djj=1,2,…,ni=1xij≥0(i=1,2,…,m;j=1,2,…,n)。运费单价销地产地办运输量B1B2B3产量(件)A16x114x126x13200A26x215x225x23300销量(件)150150200500500minf=6x11+4x12+6x13+6x21+5x22+5x23s.t.x11+x12+x13=200x21+x22+x23=300x11+x21=150x12+x22=150x13+x23=200xij≥0(i=1，2；j=1，2，3）。§7.1运输问题的模型设xij为从产地Ai运往销地Bj的运输量，则对于产销平衡问题，可得到下列运输问题的模型：mnminf=cijxiji=1j=1ns.t.xij=sii=1,2,…,mj=1mxij=djj=1,2,…,ni=1xij≥0(i=1,2,…,m;j=1,2,…,n)。§7.1运输问题的模型2.一般模型的系数矩阵特征1.共有m+n行，分别表示各产地和销地；m×n列，分别表示各变量；2.每列只有两个1，其余为0，分别表示只有一个产地和一个销地被使用。运费单价销地产地办运输量B1B2B3产量(件)A16x114x126x13200A26x215x225x23300销量(件)150150200500500minf=6x11+4x12+6x13+6x21+5x22+5x23s.t.x11+x12+x13=200x21+x22+x23=300x11+x21=150x12+x22=150x13+x23=200xij≥0(i=1，2；j=1，2，3）。§7.1运输问题的模型2.一般模型的系数矩阵特征1.共有m+n行，分别表示各产地和销地；m×n列，分别表示各变量；2.每列只有两个1，其余为0，分别表示只有一个产地和一个销地被使用。§7.1运输问题的模型3.一般模型有时会发生一些如下变化：1）有时求目标函数最大值。如求利润最大或营业额最大等；2）当某些运输线路上的能力有限制时，模型中可直接加入（等式或不等式）约束；3）产销不平衡时，可加入虚设的产地（销大于产时）或销地（产大于销时）。第七章运输问题7.1运输问题的模型7.2运输问题的表上作业法§7.2运输问题的表上作业法表上作业法是一种求解运输问题的特殊方法，其实质是单纯形法。运输问题都存在最优解。§7.2运输问题的表上作业法计算过程（假设产销平衡）：1.找出初始基本可行解。•对于有m个产地n个销地的产销平衡问题，则有m个关于产量的约束方程和n个关于销量的约束方程。运费单价销地产地办运输量B1B2B3产量(件)A16x114x126x13200A26x215x225x23300销量(件)150150200500500minf=6x11+4x12+6x13+6x21+5x22+5x23s.t.x11+x12+x13=200x21+x22+x23=300x11+x21=150x12+x22=150x13+x23=200xij≥0(i=1，2；j=1，2，3）。§7.2运输问题的表上作业法计算过程（假设产销平衡）：1.找出初始基本可行解。•对于有m个产地n个销地的产销平衡问题，则有m个关于产量的约束方程和n个关于销量的约束方程。•由于产销平衡，其模型最多只有m+n-1个独立的约束方程，即运输问题有m+n-1个基变量。运费单价销地产地办运输量B1B2B3产量(件)A16x114x126x13200A26x215x225x23300销量(件)150150200500500minf=6x11+4x12+6x13+6x21+5x22+5x23s.t.x11+x12+x13=200x21+x22+x23=300x11+x21=150x12+x22=150x13+x23=200xij≥0(i=1，2；j=1，2，3）。§7.2运输问题的表上作业法计算过程（假设产销平衡）：1.找出初始基可行解。•对于有m个产地n个销地的产销平衡问题，则有m个关于产量的约束方程和n个关于销量的约束方程。•由于产销平衡，其模型最多只有m+n-1个独立的约束方程，即运输问题有m+n-1个基变量。§7.2运输问题的表上作业法计算过程（假设产销平衡）：1.找出初始基可行解。2.求各非基变量的检验数。即检验除了上述m+n-1个基变量以外的空格的检验数判别是否达到最优解，如果已是最优，停止计算，否则转到下一步。§7.2运输问题的表上作业法计算过程（假设产销平衡）：1.找出初始基可行解。2.求各非基变量的检验数。3.确定入基变量和出基变量，找出新的基可行解。4.重复2、3直到得到最优解。§7.2运输问题的表上作业法1.找出初始基可行解。§7.2运输问题的表上作业法例.喜庆食品公司有三个生产面包的分厂A1，A2，A3，有四个销售公司B1，B2，B3，B4，其各分厂每日的产量、各销售公司每日的销量以及各分厂到各销售公司的单位运价如表所示，在表中产量与销量的单位为吨，运价的单位为百元/吨。问该公司应如何调运产品在满足各销点的需求量的前提下总运费最少？销地产地B1B2B3B4产量A13113107A219284A3741059销量36562020§7.2运输问题的表上作业法1.找出初始基可行解。最小元素法我们很容易的直观想到,为了减少运费,应优先考虑单位运输价格最小(或运输距离最短)的供销业务,最大限度的满足其供销量。§7.2运输问题的表上作业法例.喜庆食品公司有三个生产面包的分厂A1，A2，A3，有四个销售公司B1，B2，B3，B4，其各分厂每日的产量、各销售公司每日的销量以及各分厂到各销售公司的单位运价如表所示，在表中产量与销量的单位为吨，运价的单位为百元/吨。问该公司应如何调运产品在满足各销点的需求量的前提下总运费最少？销地产地B1B2B3B4产量A13113107A219284A3741059销量36562020销地产地B1B2B3B4产量A131131073043A2192841031A37410593063销量30605406302020最小元素法销地产地B1B2B3B4产量A131131073043A2192841031A37410593063销量30605406302020最小元素法销地产地B1B2B3B4产量A131131073043A2192841031A37410593063销量30605406302020最小元素法销地产地B1B2B3B4产量A131131073043A2192841031A37410593063销量30605406302020最小元素法销地产地B1B2B3B4产量A131131073043A2192841031A37410593063销量30605406302020最小元素法销地产地B1B2B3B4产量A131131073043A2192841031A37410593063销量30605406302020最小元素法销地产地B1B2B3B4产量A131131073043A2192841031A37410593063销量30605406302020最小元素法销地产地B1B2B3B4产量A131131073043A2192841031A37410593063销量30605406302020最小元素法§7.2运输问题的表上作业法1.找出初始基可行解。注意两个问题：•1.当我们取定xij的值之后，会出现Ai的产量与Bj的销量都改为零的情况，这时只能划去Ai行或Bj列，但不能同时划去Ai行与Bj列。•2.用最小元素法时，可能会出现只剩下一行或一列的所有格均未填数或未被划掉的情况，此时在这一行或者一列中除去已填上的数外均填上零，不能按空格划掉。这样可以保证填过数或零的格为m+n-1个，即保证基变量的个数为m+n-1个。销地产地B1B2B3B4产量A131131073043A2192841031A37410593063销量30605406302020最小元素法销地产地B1B2B3B4产量A131131083043A2192831031A37410593063销量30605406302020最小元素法销地产地B1B2B3B4产量A131131083043A2192830031A37410593063销量30605406302020最小元素法销地产地B1B2B3B4产量A131131083043A2192830030A37410593063销量30605406302020最小元素法销地产地B1B2B3B4产量A131131083053A2192830030A37410593063销量30605506302020最小元素法§7.2运输问题的表上作业法1.找出初始基可行解。注意两个问题：•1.当我们取定xij的值之后，会出现Ai的产量与Bj的销量都改为零的情况，这时只能划去Ai行或Bj列，但不能同时划去Ai行与Bj列。•2.用最小元素法时，可能会出现只剩下一行或一列的所有格均未填数或未被划掉的情况，此时在这一行或者一