管理运筹学讲义第3章运输问题.pptx

《管理运筹学讲义第3章运输问题.pptx》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第3章运输问题Subtitle学习要点1．掌握运输问题的数学模型、系数矩阵特殊形式2．掌握用西北角法、最小元素法求初始基可行解3．掌握位势法求解、牢固掌握三合一表格求解运输问题过程1石家庄经济学院管理科学与工程学院§3.1运输问题及其数学模型§3.2表上作业法§3.3产销不平衡的运输问题§3.4应用举例本章主要内容第3章运输问题2石家庄经济学院管理科学与工程学院§3.1运输问题及其数学模型问题的提出一般的运输问题就是要解决把某种产品从若干个产地调运到若干个销地，在每个产地的供应量与每个销地的需求量已知，并知道各地之间的运输单价的

2、前提下，如何确定一个使得总的运输费用最小的方案。回本章目录3石家庄经济学院管理科学与工程学院例3.1某公司从三个产地A1、A2、A3将物品运往四个销地B1、B2、B3、B4，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示问应如何调运，可使得总运输费最小?4石家庄经济学院管理科学与工程学院解：这是一个产销平衡的运输问题，设xij为从产地Ai运往销地Bj的运输量（i=1，2，3；j=1，2，3，4）该运输问题的线性规划模型如下：Minf=3x11+11x12+3x13+10x14+x21+9x22+2x23+8

3、x24+7x31+4x32+10x33+5x345石家庄经济学院管理科学与工程学院s.t.x11+x12+x13+x14=7x21+x22+x23+x24=4x31+x32+x33+x34=9x11+x21+x31=3x12+x22+x32=6x13+x23+x33=5x14+x24+x34=6xij≥0(i=1、2、3；j=1、2、36石家庄经济学院管理科学与工程学院其系数矩阵为：共有m+n行，分别表示产地和销地；有mn列分别表示各变量；每列只有两个1，其余为0。7石家庄经济学院管理科学与工程学院运输问题的一般提法是：设某种物

4、资有m个产地和n个销地。产地Ai的产量为；销地Bj的销量为。从第i个产地向第j个销地运输每单位物资的运价为Cij，这就是由多个产地供应多个销地的单品种物资运输问题。问如何调运这些物资才能使总运费达到最小。8石家庄经济学院管理科学与工程学院表3-1产销平衡表9石家庄经济学院管理科学与工程学院表3-2单位运价表10石家庄经济学院管理科学与工程学院表中的表示由产地Ai向销地Bj运输物资的数量（即运量）。在产销平衡表3-1中，去掉最后一行和最后一列余下的部分，称为一个调运方案，或简称为一个方案。或者将上述两个表格合在一起，称为运输表（表

5、3-3）。11石家庄经济学院管理科学与工程学院销地产地B1B2…Bn产量A1x11x12…x1na1A2x21x22…x2na2Amxm1xm2…xmnam销量b1b2…bn表3-3运输表12石家庄经济学院管理科学与工程学院下面分两种情况来讨论：（1）。即运输问题的总产量等于其总销量，这样的运输问题称为产销平衡的运输问题。（2）。即运输问题的总产量不等于总销量，这样的运输问题称为产销不平衡的运输问题。我们重点讨论产销平衡的运输问题及其求解方法。然后在此基础上讨论产销不平衡的运输问题应该如何转化为产销平衡的运输问题。13石家庄经济

6、学院管理科学与工程学院若用xij表示从Ai到Bj的运量，那么在产销平衡的条件下，要求得总运费最小的调运方案，数学模型为：14石家庄经济学院管理科学与工程学院其中，ai和bj满足：(3-2)称为产销平衡条件。15石家庄经济学院管理科学与工程学院将（3-1）的结构约束加以整理，可知其系数矩阵的结构比较松散，且特殊16石家庄经济学院管理科学与工程学院该系数矩阵中对应于变量xij的系数向量Pij，其分量中除第i个和第m+j个为1以外，其余的都为零。即17石家庄经济学院管理科学与工程学院根据运输问题的数学模型求出的运输问题的解，代表着一个

7、运输方案，其中每一个变量xij的值表示由Ai调运数量为xij的物品给Bj。前已指出运输问题是一种线性规划问题，可设想用迭代法进行求解，即先找出它的某一个基可行解，再进行解的最优性检验，若它不是最优解，就进行迭代调整，以得到一个新的更好的解，继续检验和调整改进，直至得到最优解为止。18石家庄经济学院管理科学与工程学院为了能按上述思路求解运输问题，要求每步得到的解X=(xij)都必须是基可行解，这意味着:（1）解X必须满足模型中的所有约束条件；（2）解中基变量xij的个数不能大于(m+n-1)个；原因是运输问题中虽有(m+n)个约束

8、条件，但由于总产量等于总销量，故只有(m+n-1)个约束条件是线性独立的。19石家庄经济学院管理科学与工程学院§3.2表上作业法表上作业法是求解产销平衡运输问题的一种简便而有效的方法，其求解工作在运输表上进行。其实质是单纯形法。但具体计算和术语有所有同。可归纳为