运筹学运输与指派问题VIP专享VIP免费

运筹学OperationsResearchChapter5运输与指派问题TransportationandAssignmentProblem5.1运输问题的数学模型及其特征5.2运输单纯形法5.3运输模型的应用5.4指派问题5.1运输问题的数学模型及其特征MathematicalModelofTransportationProblems人们在从事生产活动中，不可避免地要进行物资调运工作。如某时期内将生产基地的煤、钢铁、粮食等各类物资，分别运到需要这些物资的地区，根据各地的生产量和需要量及各地之间的运输费用，如何制定一个运输方案，使总的运输费用最小。这样的问题称为运输问题。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运输模型ModelofTransportationProblems设xij(i=1,2,3；j=1,2,3,4)为i个产粮地运往第j个需求地的运量，这样得到下列运输问题的数学模型：34333231242322211413121192428353623minxxxxxxxxxxxxZ5810343332312423222114131211xxxxxxxxxxxx3875342414332313322212312111xxxxxxxxxxxx运量应大于或等于零（非负要求），即4,3,2,13,2,1,0jixij；5.1运输模型ModelofTransportationProblems100010001000010001000100001000100010000100010001111100000000000011110000000000001111:343332312423222114131211xxxxxxxxxxxx其系数矩阵为有些问题表面上与运输问题没有多大关系，也可以建立与运输问题形式相同的数学模型看一个例子：【例5-2】有三台机床加工三种零件，计划第i台的生产任务为ai(i=1,2,3)个零件，第j种零件的需要量为bj(j=1,2,3)，第i台机床加工第j种零件需要的时间为cij，如表5－2所示。问如何安排生产任务使总的加工时间最少？零件机床B1B2B3生产任务A152350A264160A373440需要量703050150表5－25.1运输模型ModelofTransportationProblems【解】设xij(i=1,2,3；j=1,2,3,)为第i台机床加工第j种零件的数量，则此问题的数学模型为3,2,13,2,1,050307040605043746325min332313322212312111333231232221131211333231232221131211jixxxxxxxxxxxxxxxxxxxxxxxxxxxxZij；5.1运输模型ModelofTransportationProblems5.1.2模型特征运输问题的一般数学模型设有m个产地（记作A1，A2，A3,…,Am），生产某种物资，其产量分别为a1,a2，…，am；有n个销地（记作B1，B2，…，Bn），其需要量分别为b1,b2，…，bn；且产销平衡，即。从第i个产地到j个销地的单位运价为cij，在满足各地需要的前提下，求总运输费用最小的调运方案。njjmiiba115.1运输模型ModelofTransportationProblems销地产地产量销量nBBB..............................21mAAA21mnmmnnccccccccc.................................................................................212222111211maaa21nbbb..............................21njijijmixcz11minnjmixnjbxmiaxijjmiijnjiij,,1;,,1,0,,1,,111设xij(i=1,2,…，m；j=1,2,…,n)为第i个产地到第j个销地的运量，则数学模型为：5.1运输模型ModelofTransportationProblemsm行n行5.1运输模型ModelofTransportationProblems111212122212111111111111111111nnmmmnxxxxxxxxxA＝的单位向量个分量为个和第分别为第和对应的列向量可表为变量中运输问题约束系数矩阵1)(0110:,jmieeeePxjmijmiijij运输问题具有如...