运筹学第7章运输数学模型.

《运筹学第7章运输数学模型.》由会员分享，可在线阅读，更多相关《运筹学第7章运输数学模型.（23页珍藏版）》请在文档大全上搜索。

1、运筹学运筹学Operations ResearchChapter 7 运输问题运输问题Transportation Problem7.1运输模型运输模型 Mathematical Model of Transportation Problems7.2 运输问题的计算机求解运输问题的计算机求解 Transportation Simplex Method7.1 7.1 运输模型运输模型 Mathematical Model of Transportation Problems广西大学数学与信息科学学院2022年5月31日星期二3现有现有A1，A2，A3三个产粮区，可供应三个产粮区，可供应 粮食分别

2、为粮食分别为10，8，5（万（万吨），现将粮食运往吨），现将粮食运往B1，B2，B3，B4四个地区，其需要量分别四个地区，其需要量分别为为5，7，8，3（万吨）。产粮地到需求地的运价（千元（万吨）。产粮地到需求地的运价（千元/吨）如吨）如表表1所示所示. 问如何安排一个运输计划，使总的运输费用最少。问如何安排一个运输计划，使总的运输费用最少。地区地区产粮区产粮区B1B2B3B4产量产量A1326310A253828A341295需要量需要量578323 运价表（运价表（千千元元/吨吨）表表17.1 运输模型运输模型 Model of Transportation Problems运输问题运输问

3、题广西大学数学与信息科学学院2022年5月31日星期二4人们在从事生产活动中，不可避免地要进行物资人们在从事生产活动中，不可避免地要进行物资调运工作。如某时期内将生产基地的煤、钢铁、粮食调运工作。如某时期内将生产基地的煤、钢铁、粮食等各类物资，分别运到需要这些物资的地区，根据各等各类物资，分别运到需要这些物资的地区，根据各地的地的生产量生产量和和需要量需要量及各地之间的及各地之间的运输费用运输费用，如何制，如何制定一个运输方案，使总的运输费用最小。这样的问题定一个运输方案，使总的运输费用最小。这样的问题称为称为运输问题运输问题。广西大学数学与信息科学学院2022年5月31日星期二5产地产地销地

4、销地 A1 10 A2 8 A3 5 B4 3 B3 8 B2 7 B1 5354231682329产地产地销地销地 A1 10 A2 8 A3 5 B4 3 B3 8 B2 7 B1 535423168232953552315+4+18+40+6+588广西大学数学与信息科学学院2022年5月31日星期二6设设 xij (i=1,2,3；j=1,2,3,4)为为i个产粮地个产粮地运往运往第第j个需求地个需求地的运量，的运量，11121314212223243132333432635382429Zxxxxxxxxxxxx 地区地区产粮区产粮区B1B2B3B4产量产量A1326310A25382

5、8A341295需要量需要量578323运输费用运输费用7.1 运输模型运输模型 Model of Transportation Problems广西大学数学与信息科学学院2022年5月31日星期二7地区地区产粮区产粮区B1B2B3B4产量产量A1326310A253828A341295需要量需要量5783235810343332312423222114131211xxxxxxxxxxxx3875342414332313322212312111xxxxxxxxxxxx产地运出量产地运出量 = = 生产量生产量运给销地的量运给销地的量 = =需要量需要量产销平行产销平行7.1 运输模型运输模型

6、Model of Transportation Problems广西大学数学与信息科学学院2022年5月31日星期二8这样得到该运输问题的数学模型：这样得到该运输问题的数学模型：34333231242322211413121192428353623minxxxxxxxxxxxxZ5810343332312423222114131211xxxxxxxxxxxx3875342414332313322212312111xxxxxxxxxxxx运量应大于或等于零（非负要求），即运量应大于或等于零（非负要求），即 4,3,2, 13,2, 1,0jixij；7.1 运输模型运输模型 Model of T

7、ransportation Problems广西大学数学与信息科学学院2022年5月31日星期二9产地产地销地销地 A1 10 A2 8 A3 5 B4 3 B3 8 B2 7 B1 5323622产地产地销地销地 A1 10 A2 8 A3 5 B4 3 B3 8 B2 7 B1 532168253552315+4+18+40+6+58852353515+4+18+15+6+1068广西大学数学与信息科学学院2022年5月31日星期二10运输问题的一般数学模型运输问题的一般数学模型设有设有m个产地（记作个产地（记作A1，A2，A3,Am），生产某种物资，其产），生产某种物资，其产量分别为量分

8、别为a1,a2，am；有；有n个销地（记作个销地（记作B1，B2，Bn），），其需要量分别为其需要量分别为b1,b2，bn；且；且产销平衡产销平衡，即，即 。从第从第i个产地到个产地到j 个销地的单位运价为个销地的单位运价为cij ，在满足各地需要的前提，在满足各地需要的前提下，求总运输费用最小的调运方案。下，求总运输费用最小的调运方案。 设设 xij (i=1,2,，m；j=1,2,n)为第为第i个产地到第个产地到第j个销地的运量，则数学模型为：个销地的运量，则数学模型为： njjmiiba11njijijmixcz11min11,nijijxaim 1. 1. 平衡运输问题的数学模型平衡运

9、输问题的数学模型11,0,1,;1,mijjiijxbjnxim jn 7.1 运输模型运输模型 Model of Transportation Problems广西大学数学与信息科学学院2022年5月31日星期二1111minmnijijiizc x njmixnjbxmiaxijjmiijnjiij, 1;, 1,0, 1, 111设平衡运输问题的数学模型为：设平衡运输问题的数学模型为：模型特征模型特征1.运输问题存在可行解，也一定存在最优解运输问题存在可行解，也一定存在最优解 2.当供应量和需求量都是整数时，则一定存在整数最优解当供应量和需求量都是整数时，则一定存在整数最优解3.有有m+

10、n个约束，个约束，mn个变量个变量4.有有m+n1个基变量个基变量7.1 运输模型运输模型 Model of Transportation Problems广西大学数学与信息科学学院2022年5月31日星期二12 当总产量与总销量不相等时当总产量与总销量不相等时, ,称为不平衡运输问题称为不平衡运输问题. 这类运输问题在实际中常常碰到。这类运输问题在实际中常常碰到。1). 1). 当产大于销时当产大于销时, ,即即 11mnijijab 数学模型为数学模型为 minjijijxCZ11minnjmixnjbxmiaxijmijijnjiij, 2 , 1;, 2 , 10, 2 , 1, 2

11、, 111，2. 不平衡运输问题不平衡运输问题的数学模型的数学模型7.1 运输模型运输模型 Model of Transportation Problems广西大学数学与信息科学学院2022年5月31日星期二132). 2). 当销大于产时当销大于产时, ,即即11mnijijab 数学模型为数学模型为 11minmnijijijZC x njmixnjbxmiaxijmijijnjiij, 2 , 1;, 2 , 1, 0, 2 , 1, 2 , 1117.1 运输模型运输模型 Model of Transportation Problems广西大学数学与信息科学学院2022年5月31日星期