《北邮运筹学ch3-1_运输问题》由会员分享，可在线阅读，更多相关《北邮运筹学ch3-1_运输问题（11页珍藏版）》请在金锄头文库上搜索。
1、Chapter 3 运输问题运输问题 Transportation Problem 运输问题是一种特殊的线性规划问题运输问题是一种特殊的线性规划问题,用一种特殊的 方法 用一种特殊的 方法(表上作业法表上作业法)求解更为简单求解更为简单 运筹学运筹学 Operations Research 1.运输模型运输模型 Mathematical Model of Transportation Problems 2.基变量与闭回路基变量与闭回路Basis Variable and Closed path 3.表上作业法表上作业法 Transportation Simplex Method 4.运输问题的
2、变体运输问题的变体Variants of Transportation Problems 北京邮电大学 运筹学 3.1 运输问题的数学模型运输问题的数学模型 Mathematical Model of T P Ch3 Transportation Problem 2013-5-17Page 2 of 11 运输问题运输问题 人们在从事生产活动中，不可避免地要进行物资调运工作。如某时 期内将生产基地的煤、钢铁、粮食等各类物资，分别运到需要这些 物资的地区，根据各地的 人们在从事生产活动中，不可避免地要进行物资调运工作。如某时 期内将生产基地的煤、钢铁、粮食等各类物资，分别运到需要这些 物资的地区
3、，根据各地的生产量生产量和和需要量需要量及各地之间的及各地之间的运输费用运输费用， 如何制定一个运输方案，使总的运输费用最小。这样的问题称为 ， 如何制定一个运输方案，使总的运输费用最小。这样的问题称为运 输问题 运 输问题。 北京邮电大学 运筹学 3.1 运输问题的数学模型运输问题的数学模型 Mathematical Model of T P Ch3 Transportation Problem 2013-5-17Page 3 of 11 运输问题的特征运输问题的特征 Characteristics of Transportation Problems 每一个每一个出发地出发地都有一定的都有
4、一定的供应量供应量（supply）配送到 目的地，每一个 ）配送到 目的地，每一个目的地目的地都有需要从一定的都有需要从一定的需求量需求量（ demand），接收从出发地发出的产品。 需求假设 接收从出发地发出的产品。 需求假设（The Requirements Assumption） 可行解特性可行解特性（The Feasible Solutions Property） 成本假设（成本假设（The Cost Assumption） 整数解性质（ ） 整数解性质（Integer Solutions Property） 北京邮电大学 运筹学 3.1 运输问题的数学模型运输问题的数学模型 Math
5、ematical Model of T P Ch3 Transportation Problem 2013-5-17Page 4 of 11 需求假设需求假设（The Requirements Assumption）： 每一个出发地都有一个固定的供应量，所有的供应 量都必须配送到目的地。与之相类似，每一个目的 地都有一个固定的需求量，整个需求量都必须由出 发地满足，即 总供应量 总需求量总供应量 总需求量 可行解特性（可行解特性（The Feasible Solutions Property）：）： 当且仅当供应量的总和等于需求量的总和时，运输问 题才有可行解 北京邮电大学 运筹学 3.1 运
6、输问题的数学模型运输问题的数学模型 Mathematical Model of T P Ch3 Transportation Problem 2013-5-17Page 5 of 11 成本假设（成本假设（The Cost Assumption）：）： 从任何一个出发地到任何一个目的地的货物配送成 本和所配送的数量成线性比例关系，因此这个成本 就等于配送的单位成本乘以所配送的数量 整数解性质（整数解性质（Integer Solutions Property）： 只要它的供应量和需求量都是整数，任何有可行 解的运输问题必然有所有决策变量都是整数的最 优解。因此，没有必要加上所有变量都是整数的 约
7、束条件 北京邮电大学 运筹学 3.1 运输问题的数学模型运输问题的数学模型 Mathematical Model of T P Ch3 Transportation Problem 2013-5-17Page 6 of 11 【例例1】现有A1，A2，A3三个产粮区，可供应 粮食分别为10， 8，5（万吨），现将粮食运往B1，B2，B3，B4四个地区，其需要 量分别为5，7，8，3（万吨）。产粮地到需求地的运价（10万 元/万吨）如表31所示，问如何安排一个运输计划，使总的运 输费用最少。 233875需要量 59214A3 82835A2 103623A1 产量B4B3B2B1 钢铁厂 矿山
8、 运价表（元/吨） 表31 北京邮电大学 运筹学 3.1 运输问题的数学模型运输问题的数学模型 Mathematical Model of T P Ch3 Transportation Problem 2013-5-17Page 7 of 11 设设xij( i =1,2,3；j =1,2,3,4)为为i个产粮地运往第个产粮地运往第j个需求地的运量，这 样得到下列运输问题的数学模型： 个需求地的运量，这 样得到下列运输问题的数学模型： 5 8 10 34333231 24232221 14131211 xxxx xxxx xxxx 3 8 7 5 342414 332313 322212 31
9、2111 xxx xxx xxx xxx 运量应大于或等于零（非负要求），即运量应大于或等于零（非负要求），即 Min z = 3x11+ 2x12+ 6x13+ 3x14+ 5x21+ 3x22+ 8x23+ 2x24 + 4x31+ x32+ 2x33+ 9x34 xij 0, i =1, 2, 3; j =1, 2, 3, 4 北京邮电大学 运筹学 3.1 运输问题的数学模型运输问题的数学模型 Mathematical Model of T P Ch3 Transportation Problem 2013-5-17Page 8 of 11 有些问题表面上与运输问题没有多大关系，但经过转
10、换，也 可以建立与运输问题形式相同的数学模型 看一个例子： 【例例2】 有三台机床加工三种零件，计划第i台的生产任务为a i (i=1,2,3)个零件，第j种零件的需要量为bj(j=1,2,3)，第i台机床加 工第j种零件需要的时间为cij，如表32所示。问如何安排生产 任务使总的加工时间最少？ 150503070需要量 40437A3 60146A2 50325A1 生产任务B3B2B1 零件 机床 表32 北京邮电大学 运筹学 3.1 运输问题的数学模型运输问题的数学模型 Mathematical Model of T P Ch3 Transportation Problem 2013-5
11、-17Page 9 of 11 【解】 设xi j(i=1,2,3；j=1,2,3,)为第i台机床加工第j种零件的数 量，则此问题的数学模型为 3 , 2 , 13 , 2 , 1, 0 50 30 70 40 60 50 43746325min 332313 322212 312111 333231 232221 131211 333231232221131211 jix xxx xxx xxx xxx xxx xxx xxxxxxxxxZ ij ； 北京邮电大学 运筹学 3.1 运输问题的数学模型运输问题的数学模型 Mathematical Model of T P Ch3 Transpo
12、rtation Problem 2013-5-17Page 10 of 11 运输问题的数学模型运输问题的数学模型 设有m个产地（记作A1，A2，A3,Am），生产某种物 资，其产量分别为a1,a2，am；有n个销地（记作B1， B2，Bn），其需要量分别为b1,b2，bn；且产销平 衡，即。从第i个产地到j 个销地的单位运价为 cij，在满足各地需要的前提下，求总运输费用最小的调运 方案。 设xij(i=1,2,，m；j=1,2,n)为第i个产地到第j个 销地的运量，则数学模型为： n j j m i i ba 11 北京邮电大学 运筹学 3.1 运输问题的数学模型运输问题的数学模型 Mathematical Model of T P Ch3 Transportation Problem 2013-5-17Page 11 of 11 n j ijij m i xcz 11 min njmix njbx miax ij j m i ij n j iij , 1;, 1,0 , 1 , 1 1 1 基变量与闭回路 Exit
