资源描述：
《运筹学运输与指派问题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、运筹学OperationsResearchChapter5运输与指派问题Transportation andAssignmentProblem5.1运输问题的数学模型及其特征5.2运输单纯形法5.3运输模型的应用5.4指派问题5.1运输问题的数学模型及其特征MathematicalModelofTransportationProblems人们在从事生产活动中，不可避免地要进行物资调运工作。如某时期内将生产基地的煤、钢铁、粮食等各类物资，分别运到需要这些物资的地区，根据各地的生产量和需要量及各地之间的运输费用，如何制定一个运输方案，使总的运输费用最小。这样的问题称为运输问题
2、。5.1运输模型ModelofTransportationProblems5.1.1数学模型产地销地A110A28A35B43B38B27B15354231682329图5.1【例5-1】现有A1，A2，A3三个产粮区，可供应粮食分别为10，8，5（万吨），现将粮食运往B1，B2，B3，B4四个地区，其需要量分别为5，7，8，3（万吨）。产粮地到需求地的运价（元/吨）如表5-1所示，问如何安排一个运输计划，使总的运输费用最少。需求地产粮地B1B2B3B4供给量A1326310A253828A341295需求量578323运价表（元/吨）表5-15.1运输模型Modelof
3、TransportationProblems设xij(i=1,2,3；j=1,2,3,4)为i个产粮地运往第j个需求地的运量，这样得到下列运输问题的数学模型：运量应大于或等于零（非负要求），即5.1运输模型ModelofTransportationProblems有些问题表面上与运输问题没有多大关系，也可以建立与运输问题形式相同的数学模型看一个例子：【例5-2】有三台机床加工三种零件，计划第i台的生产任务为ai(i=1,2,3)个零件，第j种零件的需要量为bj(j=1,2,3)，第i台机床加工第j种零件需要的时间为cij，如表5－2所示。问如何安排生产任务使总的加工时间最
4、少？零件机床B1B2B3生产任务A152350A264160A373440需要量703050150表5－25.1运输模型ModelofTransportationProblems【解】设xij(i=1,2,3；j=1,2,3,)为第i台机床加工第j种零件的数量，则此问题的数学模型为5.1运输模型ModelofTransportationProblems5.1.2模型特征运输问题的一般数学模型设有m个产地（记作A1，A2，A3,…,Am），生产某种物资，其产量分别为a1,a2，…，am；有n个销地（记作B1，B2，…，Bn），其需要量分别为b1,b2，…，bn；且产销平衡，
5、即。从第i个产地到j个销地的单位运价为cij，在满足各地需要的前提下，求总运输费用最小的调运方案。5.1运输模型ModelofTransportationProblems销地产地产量销量设xij(i=1,2,…，m；j=1,2,…,n)为第i个产地到第j个销地的运量，则数学模型为：5.1运输模型ModelofTransportationProblemsm行n行5.1运输模型ModelofTransportationProblems运输问题具有如下特点:1.运输问题存在可行解，也一定存在最优解2.当供应量和需求量都是整数时，则一定存在整数最优解3.有m+n个约束，mn个变量
6、4.约束条件系数矩阵的元素等于0或15.约束条件系数矩阵的每一列有两个非零元素,这对应于每一个变量在前m个约束方程中出现一次,在后n个约束方程中也出现一次6.所有约束方程都是等式方程7.各产地产量之和等于各销地销量之和8.有m+n－1个基变量,因为产销平衡,所以模型最多只有m+n-1个独立约束方程,即系数矩阵的秩最多为m+n-1.5.2运输单纯形法TransportationSimplexMethod设平衡运输问题的数学模型为：5.2运输单纯形法TransportationSimplexMethod运输单纯形法也称为表上作业法，是直接在运价表上求最优解的一种方法，它的步骤
7、是：第一步：求初始基本可行解（初始调运方案）。常用的方法有最小元素法、元素差额法（Vogel近似法）、左上角法。第二步：求检验数并判断是否得到最优解。常用求检验的方法有闭回路法和位势法，当非基变量的检验数λij全都非负时得到最优解，若存在检验数λlk<0，说明还没有达到最优，转第三步。第三步：调整运量，即换基。选一个变量出基，对原运量进行调整得到新的基可行解，转入第二步。5.2运输单纯形法TransportationSimplexMethod5.2.1初始基可行解1.最小元素法最小元素法的思想是就近优先运送，即最小运价Cij对
