资源描述：
《运输与指派模型问题课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、运筹学OperationsResearchChapter7运输与指派问题Transportation andAssignmentProblem7.1运输模型MathematicalModelofTransportationProblems7.2运输单纯形法TransportationSimplexMethod7.3运输模型的应用AplicationofTransportationModel7.4指派问题Assignmentproblem8/24/202117.1运输模型MathematicalModelofTransportationProblems8/24/20212人们在从事
2、生产活动中，不可避免地要进行物资调运工作。如某时期内将生产基地的煤、钢铁、粮食等各类物资，分别运到需要这些物资的地区，根据各地的生产量和需要量及各地之间的运输费用，如何制定一个运输方案，使总的运输费用最小。这样的问题称为运输问题。7.1运输模型ModelofTransportationProblems7.1.1数学模型产地销地A110A28A35B43B38B27B15354231682329图7.18/24/20213【例7.1】现有A1，A2，A3三个产粮区，可供应粮食分别为10，8，5（万吨），现将粮食运往B1，B2，B3，B4四个地区，其需要量分别为5，7，8，3（万吨）
3、。产粮地到需求地的运价（元/吨）如表7－1所示.问如何安排一个运输计划，使总的运输费用最少。地区产粮区B1B2B3B4产量A1326310A253828A341295需要量578323运价表（元/T）表7－18/24/20214设xij(i=1,2,3；j=1,2,3,4)为i个产粮地运往第j个需求地的运量，则运输费用为：地区产粮区B1B2B3B4产量A1326310A253828A341295需要量5783238/24/20215地区产粮区B1B2B3B4产量A1326310A253828A341295需要量578323从产粮区运出去的量8/24/20216运给需求地的量地区产
4、粮区B1B2B3B4产量A1326310A253828A341295需要量5783238/24/20217运量应大于或等于零（非负要求），即这样得到下列运输问题的数学模型：8/24/20218有些问题表面上与运输问题没有多大关系，也可以建立与运输问题形式相同的数学模型【例7.2】有三台机床加工三种零件，计划第i台的生产任务为ai(i=1,2,3)个零件(三种零件)，第j种零件的需要量为bj(j=1,2,3)，第i台机床加工第j种零件需要的时间为cij，如下表所示。问如何安排生产任务使总的加工时间最少？零件机床B1B2B3生产任务A152350A264160A373440需要量70
5、30501508/24/20219【解】设xij(i=1,2,3；j=1,2,3,)为第i台机床加工第j种零件的数量，零件机床B1B2B3生产任务A152350A264160A373440需要量703050150则总的加工时间为8/24/202110则此问题的数学模型为8/24/202111运输问题的一般数学模型设有m个产地（记作A1，A2，A3,…,Am），生产某种物资，其产量分别为a1,a2，…，am；有n个销地（记作B1，B2，…，Bn），其需要量分别为b1,b2，…，bn；且产销平衡，即。从第i个产地到j个销地的单位运价为cij，在满足各地需要的前提下，求总运输费用最小的
6、调运方案。设xij(i=1,2,…，m；j=1,2,…,n)为第i个产地到第j个销地的运量，则数学模型为：8/24/202112则数学模型为：8/24/202113设数学模型为7.1.2最大值问题8/24/202114第一种方法：将极大化问题转化为极小化问题。设极大化问题的运价表为C=（Cij）m×n，用一个较大的数M（M≥max{Cij}）去减每一个Cij得到矩阵C′=（C′ij）m×n，其中C/ij=M－Cij≥0,将C/作为极小化问题的运价表，用表上用业法求出最优解，目标函数值为8/24/202115当总产量与总销量不相等时,称为不平衡运输问题.这类运输问题在实际中常常碰到
7、,它的求解方法是将不平衡问题化为平衡问题再按平衡问题求解。1.当产大于销时,即7.1.3不平衡运输问题BjAiB1B2B3产量A1659120A212107100A3698130销量100100808/24/2021161.当产大于销时数学模型为即8/24/202117由于总产量大于总销量，必有部分产地的产量不能全部运送完，必须就地库存，即每个产地设一个仓库，库存量为xi，n+1（i=1，2，…，m），总的库存量为8/24/202118bn+1作为一个虚设的销地Bn+1的销量。各
