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

1、运筹学运筹学Operations ResearchChapter 7 运输问题运输问题Transportation Problem7.1运输模型运输模型 Mathematical Model of Transportation Problems7.2 运输问题的计算机求解运输问题的计算机求解 Transportation Simplex Method7.1 7.1 运输模型运输模型 Mathematical Model of Transportation Problems广西大学数学与信息科学学院2021年7月6日星期二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、广西大学数学与信息科学学院2021年7月6日星期二4人们在从事生产活动中，不可避免地要进行物资人们在从事生产活动中，不可避免地要进行物资调运工作。如某时期内将生产基地的煤、钢铁、粮食调运工作。如某时期内将生产基地的煤、钢铁、粮食等各类物资，分别运到需要这些物资的地区，根据各等各类物资，分别运到需要这些物资的地区，根据各地的地的生产量生产量和和需要量需要量及各地之间的及各地之间的运输费用运输费用，如何制，如何制定一个运输方案，使总的运输费用最小。这样的问题定一个运输方案，使总的运输费用最小。这样的问题称为称为运输问题运输问题。广西大学数学与信息科学学院2021年7月6日星期二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广西大学数学与信息科学学院2021年7月6日星期二6设设 xij (i=1,2,3；j=1,2,3,4)为为i个产粮地个产粮地运往运往第第j个需求地个需求地的运量，的运量，11121314212223243132333432635382429Zxxxxxxxxxxxx 地区地区产粮区产粮区B1B2B3B4产量产量A1326310A253828A34

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

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

7、rtation Problems广西大学数学与信息科学学院2021年7月6日星期二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广西大学数学与信息科学学院2021年7月6日星期二10运输问题的一般数学模型运输问题的一般数学模型设有设有m个产地（记作个产地（记作A1，A2，A3,Am），生产某种物资，其产），生产某种物资，其产量分别为量分别为a1,a2，

8、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广西大学数学与信息科学学院2021年7月6日星期二1111minmnijijiizc x njmixnjbxmiaxijjmiijnjiij, 1;, 1,0, 1, 111设平衡运输问题的数学模型为：设平衡运输问题的数学模型为：模型特征模型特征1.运输问题存在可行解，也一定存在最优解运输问题存在可行解，也一定存在最优解 2.当供应量和需求量都是整数时，则一定存在整数最优解当供应量和需求量都是整数时，则一定存在整数最优解3.有有m+n个约束，个约束，

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

11、平衡运输问题不平衡运输问题的数学模型的数学模型7.1 运输模型运输模型 Model of Transportation Problems广西大学数学与信息科学学院2021年7月6日星期二132). 2). 当销大于产时当销大于产时, ,即即11mnijijab 数学模型为数学模型为 11minmnijijijZC x njmixnjbxmiaxijmijijnjiij, 2 , 1;, 2 , 1, 0, 2 , 1, 2 , 1117.1 运输模型运输模型 Model of Transportation Problems广西大学数学与信息科学学院2021年7月6日星期二14 有些问题表面上与

12、运输问题没有多大关系，也可以建立与有些问题表面上与运输问题没有多大关系，也可以建立与运输问题形式相同的数学模型运输问题形式相同的数学模型【例例7.2】有三台机床加工三种零件，计划第有三台机床加工三种零件，计划第i台的生产任务为台的生产任务为a i (i=1,2,3)个零件，第个零件，第 j 种零件的需要量为种零件的需要量为 bj (j=1,2,3)，第，第 I 台台机床加工第机床加工第 j 种零件需要的时间为种零件需要的时间为 cij ，如表，如表72所示。所示。问如何问如何安排生产任务使总的加工时间最少？安排生产任务使总的加工时间最少？ 零件零件机床机床B1B2B3生产任务生产任务A1523

13、50A264160A373440需要量需要量703050150表表727.1 运输模型运输模型 Model of Transportation Problems广西大学数学与信息科学学院2021年7月6日星期二15 【解解】 设设 xi j (i=1,2,3；j=1,2,3,)为第为第 i 台机床加工第台机床加工第 j 种零件种零件的数量，的数量，11121222321313233364537342Zxxxxxxxxx 零件零件机床机床B1B2B3生产生产任务任务A152350A264160A373440需要需要量量703050150111213212223313233506040 xxxxx

14、xxxx 则总的加工时间为则总的加工时间为112131122232132333703050 xxxxxxxxx7.1 运输模型运输模型 Model of Transportation Problems广西大学数学与信息科学学院2021年7月6日星期二16111213212223313233111213212223313233112131122232132333min523647345060407030500,1,2,31,2,3,ijZxxxxxxxxxxxxxxxxxxxxxxxxxxxxij ；则此问题的数学模型为则此问题的数学模型为零件零件机床机床B1B2B3生产生产任务任务A15235

15、0A264160A373440需要需要量量7030501507.1 运输模型运输模型 Model of Transportation Problems广西大学数学与信息科学学院2021年7月6日星期二17例例7.3. 生产时序的安排生产时序的安排1) 问题的提出问题的提出 北方飞机公司为全球各航空公司制造商用飞机。其生北方飞机公司为全球各航空公司制造商用飞机。其生产过程之最后阶段为生产喷射引擎，然后装置于（一极速产过程之最后阶段为生产喷射引擎，然后装置于（一极速工作）制妥的机体，该公司有若干近期必须交付使用的飞工作）制妥的机体，该公司有若干近期必须交付使用的飞机的合同，现须安排今后四个月飞机喷

16、射引擎的生产计划，机的合同，现须安排今后四个月飞机喷射引擎的生产计划，并须于每月末分别提供并须于每月末分别提供10、15、25、20台引擎。台引擎。7.1 运输模型运输模型 Model of Transportation Problems广西大学数学与信息科学学院2021年7月6日星期二18 已知该公司各月的生产能力和生产每台引擎的成本如下已知该公司各月的生产能力和生产每台引擎的成本如下表所示（单位：百万元），又如果生产出来的引擎当月不能表所示（单位：百万元），又如果生产出来的引擎当月不能交货的，每台引擎每积压一个月需存储和维护费用交货的，每台引擎每积压一个月需存储和维护费用0.015百百万元

17、，试在完成合约的情况下，制定引擎数量的生产安排方万元，试在完成合约的情况下，制定引擎数量的生产安排方案，以使该公司今后四个月的生产费用最小。案，以使该公司今后四个月的生产费用最小。生产成本表生产成本表月月 份份合约数合约数生产能力生产能力单位成本单位成本存储和维护费存储和维护费1 1101025251 108080 00150152 2151535351 111110 00150153 3252530301 110100 00150154 4202010101 11313 7.1 运输模型运输模型 Model of Transportation Problems广西大学数学与信息科学学院202

18、1年7月6日星期二19ijxijx假设假设表示第表示第 i i月生产并用于第月生产并用于第 j月交货月交货应满足：应满足：的引擎数，因公司必须完成合同，则的引擎数，因公司必须完成合同，则2025 15 10 44342414332313221211xxxxxxxxxx月月 份份合约数合约数1 110102 215153 325254 42020【解解】7.1 运输模型运输模型 Model of Transportation Problems广西大学数学与信息科学学院2021年7月6日星期二20又每月生产的用于当月和以后各月交货的引擎数不可能又每月生产的用于当月和以后各月交货的引擎数不可能超过该

19、公司的实际生产能力，故超过该公司的实际生产能力，故 还应满足：还应满足：ijx10 30 35 25 44343324232214131211xxxxxxxxxx月月 份份生产能力生产能力1 125252 235353 330304 410107.1 运输模型运输模型 Model of Transportation Problems广西大学数学与信息科学学院2021年7月6日星期二21下面再构造下面再构造“单位运价表单位运价表”，它应等价于这里的，它应等价于这里的“成本费用表成本费用表”。 iijc因第因第 i i 月生产并用于第月生产并用于第 j 月月 交货的引擎数的实际成本交货的引擎数的实际成本应该是其生产单位成本再加上存储、维护费用，从而我们应该是其生产单位成本再加上存储、维护费用，从而我们可得其可得其“成本费用表成本费用表”如下：如下： 成本费用表成本费用表 1 12 23 34 41 11.081.081.0951.0951.1101.1101.1251.1252 2 1.1101.1101.1251.1251.1401.1403 3 1.1001.1001.1151.1154 4 1.1301.130生产生产交货交货7.