《运输问题的数学模型》由会员分享，可在线阅读，更多相关《运输问题的数学模型（11页珍藏版）》请在金锄头文库上搜索。
1、Chapter 3 运输问题Transportation Problem 运输问题是一种特殊的线性规划问题,用一种特殊的 方法(表上作业法)求解更为简单运筹学 Operations Research1.运输模型 Mathematical Model of Transportation Problems 2.基变量与闭回路Basis Variable and Closed path 3.表上作业法 Transportation Simplex Method 4.运输问题的变体Variants of Transportation Problems Date3.1 运输问题的数学模型Mathemat
2、ical Model of T P Ch3 Transportation Problem Page 2 of 11运输问题人们在从事生产活动中，不可避免地要进行物资调运工作。如某时 期内将生产基地的煤、钢铁、粮食等各类物资，分别运到需要这些 物资的地区，根据各地的生产量和需要量及各地之间的运输费用， 如何制定一个运输方案，使总的运输费用最小。这样的问题称为运 输问题。 Date3.1 运输问题的数学模型Mathematical Model of T P Ch3 Transportation Problem Page 3 of 11运输问题的特征 Characteristics of Trans
3、portation Problems每一个出发地都有一定的供应量（supply）配送到 目的地，每一个目的地都有需要从一定的需求量（ demand），接收从出发地发出的产品。 需求假设（The Requirements Assumption） 可行解特性（The Feasible Solutions Property） 成本假设（The Cost Assumption） 整数解性质（Integer Solutions Property）Date3.1 运输问题的数学模型Mathematical Model of T P Ch3 Transportation Problem Page 4 of
4、11需求假设（The Requirements Assumption）： 每一个出发地都有一个固定的供应量，所有的供应 量都必须配送到目的地。与之相类似，每一个目的 地都有一个固定的需求量，整个需求量都必须由出 发地满足，即 总供应量 总需求量 可行解特性（The Feasible Solutions Property）： 当且仅当供应量的总和等于需求量的总和时，运输问 题才有可行解 Date3.1 运输问题的数学模型Mathematical Model of T P Ch3 Transportation Problem Page 5 of 11成本假设（The Cost Assumption
5、）： 从任何一个出发地到任何一个目的地的货物配送成 本和所配送的数量成线性比例关系，因此这个成本 就等于配送的单位成本乘以所配送的数量 整数解性质（Integer Solutions Property）： 只要它的供应量和需求量都是整数，任何有可行 解的运输问题必然有所有决策变量都是整数的最 优解。因此，没有必要加上所有变量都是整数的 约束条件 Date3.1 运输问题的数学模型Mathematical Model of T P Ch3 Transportation Problem Page 6 of 11【例1】现有A1，A2，A3三个产粮区，可供应 粮食分别为10，8 ，5（万吨），现将粮
6、食运往B1，B2，B3，B4四个地区，其需要 量分别为5，7，8，3（万吨）。产粮地到需求地的运价（10万 元/万吨）如表31所示，问如何安排一个运输计划，使总的运 输费用最少。钢铁厂 矿山B1B2B3B4产量A1326310A253828A341295需要量578323运价表（元/吨）表31Date3.1 运输问题的数学模型Mathematical Model of T P Ch3 Transportation Problem Page 7 of 11设xij ( i =1,2,3；j =1,2,3,4)为i个产粮地运往第j个需求地的运量，这 样得到下列运输问题的数学模型：运量应大于或等于零
7、（非负要求），即 Min z = 3x11+ 2x12+ 6x13+ 3x14+ 5x21+ 3x22+ 8x23+ 2x24+ 4x31+ x32+ 2x33+ 9x34xij 0, i =1, 2, 3; j =1, 2, 3, 4Date3.1 运输问题的数学模型Mathematical Model of T P Ch3 Transportation Problem Page 8 of 11有些问题表面上与运输问题没有多大关系，但经过转换，也 可以建立与运输问题形式相同的数学模型看一个例子：【例2】 有三台机床加工三种零件，计划第i台的生产任务为a i (i=1,2,3)个零件，第j种零
8、件的需要量为bj (j=1,2,3)，第i台机床加 工第j种零件需要的时间为cij ，如表32所示。问如何安排生产 任务使总的加工时间最少？ 零件 机床B1B2B3生产任务A152350A264160A373440需要量703050150表32Date3.1 运输问题的数学模型Mathematical Model of T P Ch3 Transportation Problem Page 9 of 11【解】 设 xi j (i=1,2,3；j=1,2,3,)为第i台机床加工第j种零件的数量 ，则此问题的数学模型为Date3.1 运输问题的数学模型Mathematical Model of
9、T P Ch3 Transportation Problem Page 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个销地的运量，则数学模型为： Date3.1 运输问题的数学模型Mathematical Model of T P Ch3 Transportation Problem Page 11 of 11基变量与闭回路ExitDate
