[法律资料]第04章运输问题

《[法律资料]第04章运输问题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1第4章运输问题2运输问题与有关概念运输问题的求解—表上作业法运输问题应用—建模本章内容重点34.1运输问题模型及有关概念4.1.1问题的提出一般的运输问题就是要解决把某种产品从若干个产地调运到若干个销地，在每个产地的供应量与每个销地的需求量已知，并知道各地之间的运输单价的前提下，如何确定一个使得总的运输费用最小的方案。4例4.1:某公司从三个产地A1、A2，A3将物品运往四个销地B1、B2、B3、B4，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？5解：产销平衡问题：总产量=总销量设xij为从产

2、地Ai运往销地Bj的运输量，得到下列运输量表：6产量(3个)销量（4个）7系数矩阵8模型系数矩阵特征1.共有m+n(3+4)行，分别表示各产地和销地；mn(3*4)列，分别表示各决策变量；2.每列只有两个1，其余为0，分别表示只有一个产地和一个销地被使用。9一般运输问题的提法：假设A1,A2,…,Am表示某物资的m个产地；B1,B2,…,Bn表示某物资的n个销地；si表示产地Ai的产量；dj表示销地Bj的销量；cij表示把物资从产地Ai运往销地Bj的单位运价（表4-3）。如果s1+s2+…+sm=d1+d2+…+dn则称该运输问题为产销平衡问题；否则，

3、称产销不平衡。4.1.2一般运输问题的线性规划模型及求解思路10表4-2运输问题数据表销地产地B1B2…Bn产量A1A2┇Amc11c12…c1nc21c22…c2n┇┇┇┇cm1cm2…cmns1s2┇sm销量d1d2…dn设xij为从产地Ai运往销地Bj的运输量，根据这个运输问题的要求，可以建立运输变量表（表4-3）。产销平衡11表4-3运输问题变量表销地产地B1B2…Bn产量A1A2┇Amx11x12…x1nx21x22…x2n┇┇┇xm1xm2…xmns1s2┇sm销量d1d2…dn产销平衡mnMinf=cijxiji=1j=1ns.t.x

4、ij=sii=1,2,…,m(4-5)j=1mxij=djj=1,2,…,n(4-6)i=1xij≥0(i=1,2,…,m;j=1,2,…,n)对于产销平衡问题，可得到下列运输问题的模型：13在实际问题建模时，还会出现如下一些变化：（1）有时目标函数求最大，如求利润最大或营业额最大等；（2）当某些运输线路上的能力有限制时，模型中可直接加入（等式或不等式）约束；(3)产销不平衡的情况。当销量大于产量时可加入一个虚设的产地去生产不足的物资，这相当于在式（4-2）每一式中加上1个松弛变量，共m个；当产量大于销量时可加入一个虚设的销地去消化多余的物资，这相当于

5、在式（4-3）每一式中加上1个松弛变量，共n个。15运输问题是一种特殊的线性规划问题，在求解时依然可以采用单纯形法的思路，如图4-1所示。由于运输规划系数矩阵的特殊性，如果直接使用线性规划单纯形法求解计算，则无法利用这些有利条件。人们在分析运输规划系数矩阵特征的基础上建立了针对运输问题的表上作业法。下面主要讨论基本可行解、检验数以及基的转换等问题。续下页16基本可行解是否最优解结束换基是否图4-1运输问题的求解思路返回转28页17考虑产销平衡问题，由于我们关心的量均在表4-2与表4-3中，因此考虑把表4-2与表4-3合成一个表,如下表4-4(下页）4.1

6、.3运输问题求解的有关概念(产销平衡)18销地产地B1B2…Bn产量A1c11x11c12x12…c1nx1na1A2c21x21c22x22…c2nx2na2┇┇┇┇┇Amcm1xm1cm2xm2…cmnxmnam销量b1b2…bn销地产地B1B2…Bn产量A1c11x11c12x12…c1nx1na1A2c21x21c22x22…c2nx2na2┇┇┇┇┇Amcm1xm1cm2xm2…cmnxmnam销量b1b2…bn销地产地B1B2…Bn产量A1c11x11c12x12…c1nx1ns1A2c21x21c22x22…c2nx2ns2┇┇┇┇┇Amc

7、m1xm1cm2xm2…cmnxmnsm销量d1d2…dn表4-4运输问题求解作业数据表平衡转31中任意m+n阶子式等于零，取第一行到m+n－1行与对应的列（共m+n-1列）组成的m+n－1阶子式。m个n个m*n故r(A)=m+n－1所以运输问题有m+n－1个基变量。21运输问题的基变量共有m+n-1个，A的秩为m+n-1。怎样找这m+n-1个基变量呢？m+n-1个基变量不含闭回路。运输问题的基变量22定义4.1在表4-4的决策变量格中，凡是能够排列成下列形式的xab,xac,xdc,xde,…,xst,xsb(4-7)或xab,xcb,xcd,xed,

8、…,xst,xat(4-8)其中，a,d,…,s各不相同；b,c,…,t各不相同