第三章--运筹学运输问题

运筹学OperationsResearchChapter5运输问题TransportationProblem5.1运输问题的数学模型及其特征5.2运输单纯形法5.3运输模型的应用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.1运输模型ModelofTransportationProblems有些问题表面上与运输问题没有多大关系，也可以建立与运输问题形式相同的数学模型看一个例子：【例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运输问题具有如下特点:1.运输问题存在可行解，也一定存在最优解2.当供应量和需求量都是整数时，则一定存在整数最优解3.有m+n个约束，mn个变量4.约束条件系数矩阵的元素等于0或15.约束条件系数矩阵的每一列有两个非零元素,这对应于每一个变量在前m个约束方程中出现一次,在后n个约束方程中也出现一次6.所有约束方程都是等式方程7.各产地产量之和等于各销地销量之和8.有m+n－1个基变量,因为产销平衡,所以模型最多只有m+n-1个独立约束方程,即系数矩阵的秩最多为m+n-1.5.2运输单纯形法TransportationSimplexMethodnjijijmixcz11minnjmixnjbxmiaxijjmiijnjiij,,1;,,1,0,,1,,111设平衡运输问题的数学模型为：5.2运输单纯形法TransportationSimplexMethod运输单纯形法也称为表上作业法，是直接在运价表上求最优解的一种方法，它的步骤是：第一步：求初始基本可行解（初始调运方案）。常用的方法有最小元素法、元素差额法（Vogel近似法）、左上角法。第二步：求检验数并判断是否得到最优解。常用求检验的方法有闭回路法和位势法，当非基变量的检验数λij全都非负时得到最优解，若存在检验数λlk0，说明还没有达到最优，转第三步。第三步：调整运量，即换基。选一个变量出基，对原运量进行调整得到新的基可行解，转入第二步。5.2运输单纯形法TransportationSimplexMethod5.2.1初始基可行解1.最小元素法最小元素法的思想是就近优先运送，即最小运价Cij对应的变量xij优先赋值然后再在剩下的运价中取最小运价对应的变量赋值并满足约束，依次下去，直到最后得到一个初始基可行解。jiijbax,min5.2运输单纯形法TransportationSimplexMethod【例5-3】求表5－6所示的运输问题的初始基可行解。表5－6销地产地B1B2B3B4产量A1A2A39723610859412705020销量106040301405.2运输单纯形法TransportationSimplexMethodBjAiB1B2B3B4产量A1938470A2765150A32109220销量10604030140表5－7～5－9【解】30××10×××10605.2运输单纯形法TransportationSimplexMethod×2010到一组基可行解可用矩阵表示，矩阵X中空白处对应的变量是非基变量，运量等于零，这组解就是初始调运方案．总运费Z=3×60+8×10+5×20+1×30+2×10+9×10=500101030201060X5.1运输模型ModelofTransportationProblems【例5-4】求表5-10给出的运输问题的初始基本可行解．B1B2B3B4aiA14104420A2773815A31210615bj510251050表5-105.2运输单纯形法TransportationSimplexMethod表5-11BjAiB1B2B3B4aiA14104420A2773815A31210615bj510251050【解】5××10××××015×10105.2运输单纯形法TransportationSimplexMethod初始基本可行解可用下列矩阵表示5.2运输单纯形法TransportationSimplexMethod1051510100X2．元素差额法（Vogel近似法）最小元素法只考虑了局部运输费用最小。有时为了节省某一处的运费，而在其它处可能运费很大。元素差额法对最小元素法进行了改进，考虑到产地到销地的最小运价和次小运价之间的差额，如果差额很大，就选最小运价先调运，否则会增加总运费。例如下面两种运输方案10515108520211515C10155108520211515C前一种按最小元素法求得，总运费是Z1=10×8+5×2+15×1=105后一种方案考虑到C11与C21之间的差额是8－2=6，先调运x21，再是x22，其次是x12这时总运费Z2=10×5+15×2+5×1=85Z1。5.2运输单纯形法TransportationSimplexMethod基于以上思路，元素差额法求初始基本可行解的步骤是：第一步：求出每行次小运价与最小运价之差，记为ui，i=1,2,…,m；同时求出每列次小运价与最小运价之差，记为vj，j=1，2，…，n；第二步：找出所有行、列差额的最大值，即L=max{ui，vi}，差额L对应行或列的最小运价处优先调运；第三步：这时必有一列或一行调运完毕，在剩下的运价中再求最大差额，进行第二次调运，依次进行下去，直到最后全部调运完毕，就得到一个初始调运方案。用元素差额法求得的基本可行解更接近最优解，所以也称为近似方案。5.2运输单纯形法TransportationSimplexMethod表5-6【例5-5】用元素差额法求表5—6运输问题的初始基本可行解。【解】求行差额ui,i=1,2,3及列差额vj,j=1,2,3,4.计算公式为ui=i行次小运价—i行最小运价vj=j列次小运价—j例最小运价5.2运输单纯形法TransportationSimplexMethod销地产地B1B2B3B4产量A1A2A39723610859412705020销量10604030140表5—12BjAiB1B2B3B4aiuiA19384701A27651504A321092207bj10604030140vj5331【0】10××5.2运输单纯形法TransportationSimplexMethod表5-1310××5.2运输单纯形法TransportationSimplexMethodBjAiB1B2B3B4aiuiA19384701×A27651504×A32109220710bj10604030140vj－331【】5.2运输单纯形法TransportationSimplexMethodBjAiB1B2B3B4aiuiA19384701×A27651504×A32109220－10××10bj10604030140vj