运筹学基础及应用(第五版)_(第三章运输问题)

1、2021-12-51运筹学运筹学OPERATIONS RESEARCH2021-12-52第三章第三章 运输问题运输问题n运输问题的数学模型运输问题的数学模型n表上作业法表上作业法n产销不平衡的运输问题及应用产销不平衡的运输问题及应用2021-12-531 1 运输问题的典例及数学模型运输问题的典例及数学模型一、一、 引例引例某公司从三个产地某公司从三个产地 ， ， 将产品运往四个销地将产品运往四个销地 ， ， ，各产地的产量，各销地的销量，及各产地往各销，各产地的产量，各销地的销量，及各产地往各销地的运费单价如表所示。应如何调运可使运费最小？地的运费单价如表所示。应如何调运可使运费最小？ 1

2、A2A1B2B3B3A4B 销地 运费单价产地B1B2B3B4产量（吨）A13113107A219284A3741059 销量（吨）36562021-12-54解：解：从表中可知：总产量从表中可知：总产量 = = 总销量。这是一个产销平衡的总销量。这是一个产销平衡的 运输问题。假设运输问题。假设 表示从产地表示从产地 运往销地运往销地 的产的产 品数量，品数量， 建立如下表格：建立如下表格：ijxij. 4 , 3 , 2 , 1; 3 , 2 , 1ji于是可建立如下的数学模型于是可建立如下的数学模型： 销地 运费单价产地B1B2B3B4产量（吨）A13113107A219284A37410

3、59 销量（吨）365611x12x13x21x22x23x31x32x33x14x24x34x2021-12-55目标函数目标函数：34333231242322211413121151047829103113xxxxxxxxxxxxMinZ约束条件：约束条件：947343332312423222114131211xxxxxxxxxxxx产量约束产量约束销量约束销量约束20204 , 3 , 2 , 1; 3 , 2 , 1, 06563342414332313322212312111jixxxxxxxxxxxxxij2021-12-56设有设有m个产地，分别为个产地，分别为 ; n 个销地，

4、分别是个销地，分别是 ；从产地从产地 运往销地运往销地 的单位运价是的单位运价是 ，运量，运量 是产地是产地 的产量；的产量； 是销地是销地 的销量。的销量。 mAAA,.,21nBBB,.,21iAjBijcijxisiAjdjB二、二、一般运输问题数学模型一般运输问题数学模型则该运输问题的模型如下：则该运输问题的模型如下：2021-12-57njmixmisxnjdxtsxcfMinijinjijjmiijminjijij,.,1,.1,0,.1,.,1.1111 说明说明：当：当 时，称其为产销平衡的运输问题，时，称其为产销平衡的运输问题，否则产销不平衡。否则产销不平衡。njjmiids

5、112021-12-58说明说明：从上述模型可以看出：从上述模型可以看出：（1）这是一个线性规划的模型；）这是一个线性规划的模型；（2）变量有）变量有mn个；个；（3）约束条件有）约束条件有 m+n 个；个；（4）系数矩阵非常稀疏；系数矩阵的秩一般为（系数矩阵非常稀疏；系数矩阵的秩一般为（m+n-1),m+n-1), 而非而非m+n 。若直接用单纯形法求解，显然单纯形表比较庞大，于是在若直接用单纯形法求解，显然单纯形表比较庞大，于是在单纯形法的基础上创建了表上作业法求解运输问题这一特单纯形法的基础上创建了表上作业法求解运输问题这一特殊的线性规划问题殊的线性规划问题 2021-12-59 从第一

6、节的运输问题的数学模型可知，运输问题实际上从第一节的运输问题的数学模型可知，运输问题实际上也属于线性规划，但由也属于线性规划，但由于于运输问题的特殊性（变量个数较多，运输问题的特殊性（变量个数较多，系数矩阵的特点），如果用单纯形表格方法迭代，计算量很系数矩阵的特点），如果用单纯形表格方法迭代，计算量很大。今天介绍的大。今天介绍的 “表上作业法表上作业法”，是针对运输问题的特殊求解，是针对运输问题的特殊求解方法，实质还是单纯形法，但减少了计算量。方法，实质还是单纯形法，但减少了计算量。 表上作业法表上作业法适用于求解产销平衡的运输问题。（产销不平适用于求解产销平衡的运输问题。（产销不平衡的问题可

7、转化为平衡问题）衡的问题可转化为平衡问题）2 2 运输问题的表上作业法运输问题的表上作业法2021-12-510表上作业法表上作业法 一般步骤一般步骤：1、找出初始基本可行解；、找出初始基本可行解；2、检查各非基变量的检验数，是否达到最优性条件，若达到，则得最优、检查各非基变量的检验数，是否达到最优性条件，若达到，则得最优解；否则解；否则 转第三步；转第三步；3、确定出基变量、进基变量，用闭回路方法进行调整，得到新的基可、确定出基变量、进基变量，用闭回路方法进行调整，得到新的基可 行解；行解；4、重复第二、第三步，直至得到最优解。、重复第二、第三步，直至得到最优解。 销地 运费单价产地B1B2

8、B3B4产量（吨）A13113107A219284A3741059 销量（吨）36562021-12-511一、确定初始基本可行解：一、确定初始基本可行解： 对于有对于有m m个产地个产地n n个销地的产销平衡问题，有个销地的产销平衡问题，有m m个关于产量个关于产量的约束方程和的约束方程和n n个关于销量的约束方程。表面上，共有个关于销量的约束方程。表面上，共有m+nm+n个个约束方程。约束方程。 但由于产销平衡，其模型最多只有但由于产销平衡，其模型最多只有m+n-1m+n-1个独立的约束方个独立的约束方程，所以运输问题实际上有程，所以运输问题实际上有m+n-1m+n-1个基变量个基变量。在

9、。在m mn n的产销的产销平衡表上给出平衡表上给出m+n-1m+n-1个数字格，其相对应的调运量的值即为个数字格，其相对应的调运量的值即为基变量的值。基变量的值。 那么在该例中，应有那么在该例中，应有 3+4-1=63+4-1=6个基变量。个基变量。2021-12-5121.最小元素法最小元素法 最小元素法的思想是就近供应，即对单位运价最小最小元素法的思想是就近供应，即对单位运价最小的变量分配运输量。的变量分配运输量。 在表上找到单位运价最小的在表上找到单位运价最小的x x2121，并使，并使x x2121取尽可能大取尽可能大的值，即的值，即x x2121=3,=3,把把A A1 1的产量改

10、为的产量改为1 1，B B1 1的销量改为的销量改为0 0，并，并把把B B1 1列划去。在剩下的列划去。在剩下的3 33 3矩阵中再找最小运价，同矩阵中再找最小运价，同理可得其他的基本可行解。理可得其他的基本可行解。 销地产地 B1 B2 B3 B4 产量 A1 4 37 3 0 A2 3 1 4 1 0 A3 6 39 3 0 销量 3 0 6 0 5 4 0 6 3 0 20203113108510294712021-12-513表中填表中填有数字的格有数字的格对应于对应于基变量基变量( (取值即为格中数字），而取值即为格中数字），而空格空格对应对应的是的是非基变量非基变量（取值为零）（

11、取值为零）. .n在求初始基本可行解时要在求初始基本可行解时要注意注意的一个问题：的一个问题： 当我们取定当我们取定x xijij的值之后，会出现的值之后，会出现A Ai i的产量与的产量与B Bj j的销量都改为零的情的销量都改为零的情况，这时只能划去况，这时只能划去A Ai i行或行或B Bj j列，但不能同时划去列，但不能同时划去A Ai i行与行与B Bj j列。列。（或者在同时划去（或者在同时划去A Ai i行与行与B Bj j列时，在该行或该列的任意空格处填加一列时，在该行或该列的任意空格处填加一个个0 0。）。） 这样可以保证填过数或零的格为这样可以保证填过数或零的格为m+n-1

12、m+n-1个，即保证基变量的个数为个，即保证基变量的个数为m+n-1m+n-1个。个。2021-12-5142.Vogel法法 Vogel法的思想是法的思想是:一地的产品如果不能按照最小运一地的产品如果不能按照最小运费就近供应，就考虑次小运费，这就有差额，差额越大，费就近供应，就考虑次小运费，这就有差额，差额越大，说明不能按最小运费调运时，运费增加得越多。因而差说明不能按最小运费调运时，运费增加得越多。因而差额越大处，就应当采用最小运费调运。额越大处，就应当采用最小运费调运。 销地产地 B1 B2 B3 B4 A1 5 20 0 0 7 A2 3 11 1 1 6 A36 31 2222 5

13、1111 3322 20203113102947110852021-12-515二二、最优解的判别、最优解的判别 判别解的最优性需要：判别解的最优性需要：计算检验数。计算检验数。方法有两种方法有两种 闭回路：闭回路：是在已给出的调运方案的运输表上从一个代表是在已给出的调运方案的运输表上从一个代表非基变量的空格出发，沿水平或垂直方向前进，遇到代表非基变量的空格出发，沿水平或垂直方向前进，遇到代表基变量的填入数字的格可转基变量的填入数字的格可转9090度（当然也可以不改变方向）度（当然也可以不改变方向）继续前进，这样继续下去，直至回到出发的那个空格，由继续前进，这样继续下去，直至回到出发的那个空格

14、，由此形成的封闭折线叫做此形成的封闭折线叫做闭回路闭回路。一个空格存在唯一的闭回一个空格存在唯一的闭回路。路。1 1.闭回路法闭回路法因为任意非基向量均可表示为基向量的唯一线性组因为任意非基向量均可表示为基向量的唯一线性组合，因此对于任意空格都合，因此对于任意空格都能够找到、并且只能找到能够找到、并且只能找到唯一的唯一的一条闭回路。一条闭回路。2021-12-516 销地产地 B1 B2 B3 B4 产量 A1（+）1 4 （-） 3 7 A2（-） 3 1 （+） 4 A363 9 销量 3 6 5 6 108531131029471从非基变量从非基变量 出发，找到一个闭回路如上表所示。回路

15、有四出发，找到一个闭回路如上表所示。回路有四个顶点，除个顶点，除 外，其余都为基变量。外，其余都为基变量。调整调运量：调整调运量： ，运费增加了，运费增加了3 3元；元； ，运费减少，运费减少3 3元元 ，运费增加，运费增加2 2元；元； ，运费减少，运费减少1 1元元调整后，调整后，总运费增加总运费增加：3-3+2-1=13-3+2-1=1元。元。说明如果让说明如果让 为基变量，运费就会增加，其增加值为基变量，运费就会增加，其增加值1 1作为作为 的的检验数检验数，111x123x113x11x121x11x11x11x2021-12-517闭回路法计算检验数：闭回路法计算检验数：就是对于代

16、表非基变量的空格就是对于代表非基变量的空格（其调运量为零），把它的调运量调整为（其调运量为零），把它的调运量调整为1 1，由于产销平衡的，由于产销平衡的要求要求, ,必须对这个空格的闭回路中的各顶点的调运量加上或减必须对这个空格的闭回路中的各顶点的调运量加上或减少少1 1。最后计算出由这些变化给整个运输方案的总运输费带来。最后计算出由这些变化给整个运输方案的总运输费带来的变化。以这个变化的数值，作为各空格（非基变量）的检的变化。以这个变化的数值，作为各空格（非基变量）的检验数。验数。判别最优解准则：判别最优解准则：如果所有代表非基变量的空格的检验如果所有代表非基变量的空格的检验数都大于等于零，

17、则已求得最优解；否则继续改进找出最优数都大于等于零，则已求得最优解；否则继续改进找出最优解。解。2021-12-5182.2.位势法位势法 （1 1）对运输表上的每一行赋予一个数值）对运输表上的每一行赋予一个数值 ，对每一列赋予一个数值对每一列赋予一个数值 ，称为行（列，称为行（列) )位势。位势。（2 2）行（列）行（列) )位势的数值是由基变量的检验数所决位势的数值是由基变量的检验数所决定的，即定的，即基变量基变量要满足：要满足： 非基变量非基变量 的检验数就可以用公式的检验数就可以用公式 求出。求出。0jiijijvucjiijijvuciujvijx2021-12-519 我们先给我们

18、先给u u1 1赋个任意数值，不妨设赋个任意数值，不妨设u u1 1=0=0，则从基变，则从基变量量x x1111的检验数求得的检验数求得 v v3 3=c=c1313-u-u1 1=3-0=3 =3-0=3 。同理可以求得同理可以求得 v v4 4=10=10，u u2 2= -1= -1，等等见上表。，等等见上表。检验数的求法，即用公式检验数的求法，即用公式 ，如如 。 销地产地 B1 B2 B3 B4 ui A1 1 2 4 3 0 A2 3 1 1 -1 -1 A3 10 6 12 3 -5 vj 2 9 3 10 311310851029471jiijijvuc1203111111v

19、uc2021-12-520位势法计算检验数：位势法计算检验数： 检验数：检验数： ijnmijijijijBijijPvvuucYPcPBCc),.,(1,.,11又因为基变量的检验数为又因为基变量的检验数为0 0，于是由（，于是由（m+n-1)m+n-1)个基变个基变 量的检验数量的检验数可解出可解出 ，进而计算其他非基，进而计算其他非基变量的检验数。变量的检验数。0jiijvuc),.,(1,.,1nmvvuu其中其中 TijP)0.0, 1.,0, 1,.0(第第i i个分量个分量第第m+jm+j个分个分量量2021-12-521三、改进运输方案的办法三、改进运输方案的办法闭回路调整法闭

20、回路调整法当表中的某个检验数小于零时，方案不为最优，需要调整。当表中的某个检验数小于零时，方案不为最优，需要调整。方法是：选取所有负检验数中最小的非基变量作为入基变量，方法是：选取所有负检验数中最小的非基变量作为入基变量，以求尽快实现最优。以求尽快实现最优。（1 1）确定调整量确定调整量：例：取：例：取 ，表明增加一个单位的，表明增加一个单位的 运输量，可使得总运费减少运输量，可使得总运费减少1 1。在以。在以 为出发点的闭为出发点的闭回路中，找出所有偶数顶点的调运量：回路中，找出所有偶数顶点的调运量： ，则调整量则调整量 （2 2）调整方法调整方法：把所有闭回路上为偶数顶点的运输量都减：把所

21、有闭回路上为偶数顶点的运输量都减少这个值，奇数顶点的运输量都增加这个值少这个值，奇数顶点的运输量都增加这个值( (见下表见下表) )。12424x314x123x1)3 , 1min(24x24x2021-12-522 销地产地 B1 B2 B3 B4 ui A1 4(+1) 3(-1) 0 A2 3 1 (-1) +1 -1 A3 6 3 -5 vj 2 9 3 10 311310851029471调整运量后的新方案：调整运量后的新方案： 销地产地 B1 B2 B3 B4 产量 A1 5 2 7 A2 3 1 4 A3 6 3 9 销量 3 6 5 6 2021-12-523 销地产地 B1

22、 B2 B3 B4 ui A1 0 2 5 2 0 A2 3 2 1 1 -2 A3 9 6 12 3 -5 vj 3 9 3 10 311310851029471对上表用位势法进行检验如下表，可知已达最优解。对上表用位势法进行检验如下表，可知已达最优解。表上作业法表上作业法的一般步骤：的一般步骤：1 1、用最小元素法或、用最小元素法或VogelVogel法确定初始基可行解；法确定初始基可行解；2 2、判断是否为最优：用闭回路法或位势法计算空格检验数，、判断是否为最优：用闭回路法或位势法计算空格检验数，若所有检验数均非负，则已得到最优解；否则进入第三步；若所有检验数均非负，则已得到最优解；否则

23、进入第三步；3 3、 从所有负检验数中选择最小者对应空格作为进基变量，从所有负检验数中选择最小者对应空格作为进基变量，从此点出发作闭回路，确定调整量从此点出发作闭回路，确定调整量 ，奇点处增加，奇点处增加 ，偶点处减少偶点处减少 。2021-12-524例：例：用表上作业法，求解下面的用表上作业法，求解下面的 运输问题运输问题 ： 销地 产地甲乙丙丁产量137645224322343853销量3322解解: :用最小元素法确定初始基可行解，如下表所示：用最小元素法确定初始基可行解，如下表所示： 2021-12-525 销地 产地甲乙丙丁产量1 33 70 62 405 （0）2 2 4 3 2

24、 2 2 (-2）3 4 33 8 53 （-4）销量3 （3）3 （7）2 （6）2 （4） 销地 产地甲乙丙丁产量1 3 0 2 05 （0）21 -1 -1 2 2 (-2）35 36 5 3 （-4）销量3 （3）3 （7）2 （6）2 （4）+-2021-12-526 销地 产地甲乙丙丁产量1 33 70 6 425 （0）2 2 4 32 2 0 2 (-2）3 4 33 8 53 （-4）销量3 （3）3 （7）2 （5）2 （4） 销地 产地甲乙丙丁产量1 3 01 25 （0）21 -12 0 2 (-2）35 3753 （-4）销量3 （3）3 （7）2 （5）2 （4）+

25、-2021-12-527 销地 产地甲乙丙丁产量1 33 7 6 425 （0）2 2 40 32 2 0 2 (-2）3 4 33 8 53 （-3）销量3 （3）3 （6）2 （5）2 （4）1 31 1 25 （0）21 0 2 0 2 (-2）34 36 4 3 （-3）销量3 （3）3 （6）2 （5）2 （4）此时所有非基变量的检验数均非负，故已达最优解。此时所有非基变量的检验数均非负，故已达最优解。2021-12-528一、产销不平衡的运输问题一、产销不平衡的运输问题例例1 1：某公司从两个产地某公司从两个产地 ， ，将产品运往三个销地，将产品运往三个销地 ， ， ， 各产地的产

26、量，各销地的销量，及各产地往各销地的运费单价如表所示。各产地的产量，各销地的销量，及各产地往各销地的运费单价如表所示。 应如何调运可使运费最小？应如何调运可使运费最小？ 1A2A1B2B3B 销地 运费单价产地B1B2B3产量（件）A1646200A2655300 销量（件）250200200 5006503 产销不平衡的运输问题及应用产销不平衡的运输问题及应用1A3B2A1A3B1B2A1A3B2B1B2A1A3B例例1 1：某公司从两个产地某公司从两个产地 ， ，将产品运往三个销地，将产品运往三个销地 ， ， ， 各产地的产量，各销地的销量，及各产地往各销地的运费单价如表所示。各产地的产量

27、，各销地的销量，及各产地往各销地的运费单价如表所示。 应如何调运可使运费最小？应如何调运可使运费最小？ 2A1A例例1 1：某公司从两个产地某公司从两个产地 ， ，将产品运往三个销地，将产品运往三个销地 ， ， ， 各产地的产量，各销地的销量，及各产地往各销地的运费单价如表所示。各产地的产量，各销地的销量，及各产地往各销地的运费单价如表所示。 应如何调运可使运费最小？应如何调运可使运费最小？ 2A1A例例1 1：某公司从两个产地某公司从两个产地 ， ，将产品运往三个销地，将产品运往三个销地 ， ， ， 各产地的产量，各销地的销量，及各产地往各销地的运费单价如表所示。各产地的产量，各销地的销量，

28、及各产地往各销地的运费单价如表所示。 应如何调运可使运费最小？应如何调运可使运费最小？ 2A1A例例1 1：某公司从两个产地某公司从两个产地 ， ，将产品运往三个销地，将产品运往三个销地 ， ， ， 各产地的产量，各销地的销量，及各产地往各销地的运费单价如表所示。各产地的产量，各销地的销量，及各产地往各销地的运费单价如表所示。 应如何调运可使运费最小？应如何调运可使运费最小？ 2A1A例例1 1：某公司从两个产地某公司从两个产地 ， ，将产品运往三个销地，将产品运往三个销地 ， ， ， 各产地的产量，各销地的销量，及各产地往各销地的运费单价如表所示。各产地的产量，各销地的销量，及各产地往各销地

29、的运费单价如表所示。 应如何调运可使运费最小？应如何调运可使运费最小？ 2A1A例例1 1：某公司从两个产地某公司从两个产地 ， ，将产品运往三个销地，将产品运往三个销地 ， ， ， 各产地的产量，各销地的销量，及各产地往各销地的运费单价如表所示。各产地的产量，各销地的销量，及各产地往各销地的运费单价如表所示。 应如何调运可使运费最小？应如何调运可使运费最小？ 2A1A2021-12-529易知这个问题中：总产量总销量，即易知这个问题中：总产量总销量，即3121200200250650500300200jjiids这时可考虑增加一个假想产地，其产量是（总销量总产量这时可考虑增加一个假想产地，其

30、产量是（总销量总产量150)150)他到各销地的单位运费是于是得到如下的表格：他到各销地的单位运费是于是得到如下的表格：3A 销地 运费单价产地B1B2B3产量（件）A1646200A2655300A 销量（件）2502002006502021-12-530例例2 2：某单位有三个区，一区、二区、三区；每年需要生活某单位有三个区，一区、二区、三区；每年需要生活用煤和取暖用煤各用煤和取暖用煤各30003000吨，吨，10001000吨，吨，20002000吨；由河北临城、吨；由河北临城、山西盂县两处煤矿负责供应，两地价格和煤质相同，两煤山西盂县两处煤矿负责供应，两地价格和煤质相同，两煤矿的供应能

31、力分别是矿的供应能力分别是15001500吨，和吨，和40004000吨。由煤矿至该单位吨。由煤矿至该单位三个区的单位运价如表所示。三个区的单位运价如表所示。 销地 运费单价产地一区二区三区供应量（吨）盂县1.81.71.554000临城1.61.51.751500 需要量（吨）300010002000由于供应能力限制，经研究决定，一区供应量可减少由于供应能力限制，经研究决定，一区供应量可减少03000300吨，吨，二区全部满足，三区不能少于二区全部满足，三区不能少于15001500吨，试求使得运费最小的运吨，试求使得运费最小的运输方案？输方案？2021-12-531根据题意，添加虚拟产地后，

32、可作出产销平衡的运价表：根据题意，添加虚拟产地后，可作出产销平衡的运价表： 销地 运费单价产地一区B1一区1B1二区B2三区B3三区1B3供应量（吨）盂县1.81.81.71.551.554000临城1.61.61.51.751.751500虚拟产地M0MM0500 需要量（吨）27003001000150050060002021-12-532 销地 运费单价产地供应量（万吨）A1613221750B1413191560C192023_50最低需求万吨3070010最高需求万吨507030不限例：例：设有三个化肥厂供应四个地区的化肥，假设等量的化设有三个化肥厂供应四个地区的化肥，假设等量的化肥

33、在这个地区的使用效果相同。各厂的产量、各地区的需肥在这个地区的使用效果相同。各厂的产量、各地区的需要量、单位运价如表所示。求出运费最省的调拨方案。要量、单位运价如表所示。求出运费最省的调拨方案。2021-12-533解：无论考虑需求的上限还是下限，这都是一个产销不平衡的问题。解：无论考虑需求的上限还是下限，这都是一个产销不平衡的问题。 当考虑下限时，产当考虑下限时，产销；当考虑需求上限时，产销；当考虑需求上限时，产销。销。 于是可以考虑在满足最低需求的情况下，兼顾最高需求。即将每于是可以考虑在满足最低需求的情况下，兼顾最高需求。即将每 个地区的需求分为个地区的需求分为最低需求最低需求和和（最高

34、（最高- -最低）需求最低）需求，最低部分必须，最低部分必须 满足，高出的部分可满足也可不满足。虽然销地满足，高出的部分可满足也可不满足。虽然销地的需求无上限，的需求无上限， 但根据生产能力，最多可以给她分配但根据生产能力，最多可以给她分配6060万吨。万吨。 另外若将最高需求考虑进来，则需添加虚拟产地另外若将最高需求考虑进来，则需添加虚拟产地D D，其产量应为，其产量应为 5050万吨。万吨。 于是可给出如下的产销平衡及运价表。于是可给出如下的产销平衡及运价表。2021-12-534 销地 运费单价产地供应量（吨）A1616132222171750B1414131919151560C1919

35、202323MM50假想DM0MM0M050最高需求万吨30207003010502102021-12-535二、生产与存储问题二、生产与存储问题例例4 4：某厂按照合同规定须于当年每季度末分别提供某厂按照合同规定须于当年每季度末分别提供1010，1515，2525，2020台同一规格的柴油机。已知该厂各季度的生台同一规格的柴油机。已知该厂各季度的生产能力及生产每台柴油机的成本如表所示。又如果生产产能力及生产每台柴油机的成本如表所示。又如果生产出来的柴油机当季不交货，每台每积压一个季度，存储出来的柴油机当季不交货，每台每积压一个季度，存储维护费用维护费用0.150.15万元。要求在完成合同的情况