第04章 运输问题 运筹学

《第04章 运输问题 运筹学》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

2、最小？4解：产销平衡问题：总产量=总销量设xij为从产地Ai运往销地Bj的运输量，得到下列运输量表：4.1运输问题模型及有关概念5Minf=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）4.1运输问题模型及有关概念6111000000111100100010010001001系数矩阵4.1运输问题模型及有关概念7模型系数矩阵特征1.

3、共有m+n行，分别表示各产地和销地；mn列，分别表示各决策变量；2.每列只有两个1，其余为0，分别表示只有一个产地和一个销地被使用。4.1运输问题模型及有关概念84.1.2一般运输问题的线性规划模型及求解思路一般运输问题的提法：假设A1,A2,…,Am表示某物资的m个产地；B1,B2,…,Bn表示某物资的n个销地；si表示产地Ai的产量；dj表示销地Bj的销量；cij表示把物资从产地Ai运往销地Bj的单位运价（表4-3）。如果s1+s2+…+sm=d1+d2+…+dn则称该运输问题为产销平衡问题；否则，称产销不平

4、衡。首先讨论产销平衡问题。4.1运输问题模型及有关概念9表4-3运输问题数据表4.1运输问题模型及有关概念销地产地B1B2…Bn产量A1A2┇Amc11c12…c1nc21c22…c2n┇┇┇┇cm1cm2…cmns1s2┇sm销量d1d2…dn设xij为从产地Ai运往销地Bj的运输量，根据这个运输问题的要求，可以建立运输变量表（表4-4）。10表4-4运输问题变量表4.1运输问题模型及有关概念销地产地B1B2…Bn产量A1A2┇Amx11x12…x1nx21x22…x2n┇┇┇xm1xm2…xmns1s2┇sm销

5、量d1d2…dn11mnMinf=cijxij（4-1）ns.t.xij≤sii=1,2,…,m（4-2）j=1mxij≤(=,≥)djj=1,2,…,n（4-3）i=1xij≥0(i=1,2,…,m;j=1,2,…,n)（4-4）4.1运输问题模型及有关概念于是得到一般运输问题的模型：在模型（4-1）—（4-4）中，式（4-2）为m个产地的产量约束；式（4-3）为n个销地的销量约束。12mnMinf=cijxiji=1j=1ns.t.xij=sii=1,2,…,m(4-5)j=1mxij=djj=

6、1,2,…,n(4-6)i=1xij≥0(i=1,2,…,m;j=1,2,…,n)4.1运输问题模型及有关概念对于产销平衡问题，可得到下列运输问题的模型：13在产销平衡问题中，式（4-2）、（4-3）分别变为（4-5）、（4-6），约束条件成为等式。在实际问题建模时，还会出现如下一些变化：（1）有时目标函数求最大，如求利润最大或营业额最大等；（2）当某些运输线路上的能力有限制时，模型中可直接加入（等式或不等式）约束；4.1运输问题模型及有关概念14(3)产销不平衡的情况。当销量大于产量时可加入一个虚设的产地去生产不

7、足的物资，这相当于在式（4-2）每一式中加上1个松弛变量，共m个；当产量大于销量时可加入一个虚设的销地去消化多余的物资，这相当于在式（4-3）每一式中加上1个松弛变量，共n个。4.1运输问题模型及有关概念15运输问题是一种特殊的线性规划问题，在求解时依然可以采用单纯形法的思路，如图4-1所示。由于运输规划系数矩阵的特殊性，如果直接使用线性规划单纯形法求解计算，则无法利用这些有利条件。人们在分析运输规划系数矩阵特征的基础上建立了针对运输问题的表上作业法。下面主要讨论基本可行解、检验数以及基的转换等问题。续下页4.1运

8、输问题模型及有关概念164.1运输问题模型及有关概念基本可行解是否最优解结束换基是否图4-1运输问题的求解思路返回174.1.3运输问题求解的有关概念考虑产销平衡问题，由于我们关心的量均在表4-3与表4-4中，因此考虑把表4-3与表4-4合成一个表,如下表4-5表4-5运输问题求解作业数据表(下页）4.1运输问题模型及有关概念184.1运输问题模型及有关概念