运筹学3 运输问题.ppt

《运筹学3 运输问题.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、Chapter3运输问题Transportation Problem运输问题是一种特殊的线性规划问题,用一种特殊的方法(表上作业法)求解更为简单运筹学OperationsResearch1.运输模型MathematicalModelofTransportationProblems2.基变量与闭回路BasisVariableandClosedpath3.表上作业法TransportationSimplexMethod4.运输问题的变体VariantsofTransportationProblems9

2、/10/2021运输问题人们在从事生产活动中，不可避免地要进行物资调运工作。如某时期内将生产基地的煤、钢铁、粮食等各类物资，分别运到需要这些物资的地区，根据各地的生产量和需要量及各地之间的运输费用，如何制定一个运输方案，使总的运输费用最小。这样的问题称为运输问题。9/10/2021运输问题的特征CharacteristicsofTransportationProblems每一个出发地都有一定的供应量（supply）配送到目的地，每一个目的地都有需要从一定的需求量（demand），接收从出发地发出的

3、产品。需求假设（TheRequirementsAssumption）可行解特性（TheFeasibleSolutionsProperty）成本假设（TheCostAssumption）整数解性质（IntegerSolutionsProperty）9/10/2021需求假设（TheRequirementsAssumption）：每一个出发地都有一个固定的供应量，所有的供应量都必须配送到目的地。与之相类似，每一个目的地都有一个固定的需求量，整个需求量都必须由出发地满足，即总供应量＝总需求量可行解特性（

4、TheFeasibleSolutionsProperty）：当且仅当供应量的总和等于需求量的总和时，运输问题才有可行解9/10/2021成本假设（TheCostAssumption）：从任何一个出发地到任何一个目的地的货物配送成本和所配送的数量成线性比例关系，因此这个成本就等于配送的单位成本乘以所配送的数量整数解性质（IntegerSolutionsProperty）：只要它的供应量和需求量都是整数，任何有可行解的运输问题必然有所有决策变量都是整数的最优解。因此，没有必要加上所有变量都是整数的约束

5、条件9/10/2021【例1】现有A1，A2，A3三个产粮区，可供应粮食分别为10，8，5（万吨），现将粮食运往B1，B2，B3，B4四个地区，其需要量分别为5，7，8，3（万吨）。产粮地到需求地的运价（10万元/万吨）如表3－1所示，问如何安排一个运输计划，使总的运输费用最少。钢铁厂矿山B1B2B3B4产量A1326310A253828A341295需要量578323运价表（元/吨）表3－19/10/2021设xij(i=1,2,3；j=1,2,3,4)为i个产粮地运往第j个需求地的运量，这样得

6、到下列运输问题的数学模型：运量应大于或等于零（非负要求），即Minz=3x11+2x12+6x13+3x14+5x21+3x22+8x23+2x24+4x31+x32+2x33+9x34xij0,i=1,2,3;j=1,2,3,49/10/2021有些问题表面上与运输问题没有多大关系，但经过转换，也可以建立与运输问题形式相同的数学模型看一个例子：【例2】有三台机床加工三种零件，计划第i台的生产任务为ai(i=1,2,3)个零件，第j种零件的需要量为bj(j=1,2,3)，第i台机床加工第j种零件

7、需要的时间为cij，如表3－2所示。问如何安排生产任务使总的加工时间最少？零件机床B1B2B3生产任务A152350A264160A373440需要量703050150表3－29/10/2021【解】设xij(i=1,2,3；j=1,2,3,)为第i台机床加工第j种零件的数量，则此问题的数学模型为9/10/2021运输问题的数学模型设有m个产地（记作A1，A2，A3,…,Am），生产某种物资，其产量分别为a1,a2，…，am；有n个销地（记作B1，B2，…，Bn），其需要量分别为b1,b2，…，b

8、n；且产销平衡，即。从第i个产地到j个销地的单位运价为cij，在满足各地需要的前提下，求总运输费用最小的调运方案。设xij(i=1,2,…，m；j=1,2,…,n)为第i个产地到第j个销地的运量，则数学模型为：9/10/2021基变量与闭回路Exit9/10/2021设平衡运输问题的数学模型为：9/10/2021【定理1】设有m个产地n个销地且产销平衡的运输问题，则基变量数为m+n-1。【证】因为产销平衡，即，将前m个约束方程两边相加得再将后n个约束相加得显然前m个约束方程之和等于