运筹学(第3章 运输问题)

运筹学基础及应用(OperationsResearch)主讲：杨启明运输问题的典例和数学模型1求解方法——表上作业法2产销不平衡运输问题3第3章运输问题3.1运输问题的典例和数学模型例1.某食品公司经销的主要产品之一是糖果.它下面设有三个加工厂,每天的糖果产量分别为:A1-7t,A2-4t,A3-9t.该公司把这些糖果分别运往四个地区的门市销售,各地区每天的销售量分别为：B1-3t,B2-6t，B3-5t,B3-6t.已知从每个加工厂到各销售门市部每吨的运价如表所示，问该食品公司应如何调运,在满足各门市部销售需要的情况下，使得总的运费支出为最少。加工厂A17T加工厂A24T加工厂A39T门市B13t门市B26t门市B35t门市B46t1113109287410153表3-1单位：元/tB1B2B3B4生产能力A13113107A219284A3741059需求3656食品调运问题：确定合理的调运方案，使得总运费支出最少。B1B2B3B4生产能力A13113107A219284A3741059需求3656运输问题的数学模型设xij为从产地Ai运往销地Bj的物资数量(i=1,…m;j=1,…n），建立规划模型AiBj

运输问题的一般提法

现有一批货物,从m个供应地运往n个销售地,Ai(i=1,‥‥,m)处有货物ai吨，Bj(j=1,‥‥,n)处需货物bj吨,已知从Ai到Bj的运价为cij

元/吨.

问如何安排，既可以满足各销地需要，又使总费用最小？A1A2Am︰︰B1B2Bn︰︰a1a2am︰︰b1b2bm︰︰供应量需求地供应地需求量调运量xij运输问题的框图表示产销表运输问题的数学模型单位运价表运输问题的数学模型运输表（运价，运量）作业表销量产量销地产地产销平衡条件下设xij为从产地Ai运往销地Bj的物资数量(i=1,…m;j=1,…n）从Ai运出的物资总量应等于Ai的产量ai，xij应满足：

运到Bj的物资总量应该等于Bj的销量bj，xij还应满足：运输问题的数学模型总运费为：运输问题的数学模型运输问题的数学模型在产销平衡条件下，线性规划模型可写为：1.约束条件都是等式约束2.总产量＝总销量产销平衡的运输问题的特点与性质3.系数矩阵是一个结构特殊的稀疏矩阵将约束方程组展开约束方程组共包含m×n个变量，(m+n)个约束条件产销平衡的运输问题的特点与性质产销平衡的运输问题的特点与性质系数矩阵A：m行n行

矩阵的元素均为1或0；每一列只有两个元素为1，其余元素均为0；将矩阵分块,特点是:前m行构成m个m×n阶矩阵,而且第k个矩阵只有第k行元素全为1,其余元素全为0（k=1,…,m）;后n行构成m个n阶单位阵。A的秩一般为m+n-1

m行n行为什么？第i行第m+j行

作业表（产销平衡表）：将运输问题的有关信息表和决策变量——调运量结合在一起构成“作业表”（产销平衡表）。表上作业法是单纯形法求解运输问题的一种简化方法，实质是单纯形法。但是具体计算和术语有所不同。销量产量销地产地3.2表上作业法运输问题中寻找可行解1023206563销量9563474829217101143

3产量销地产地填有数字的格:对应运输问题解中的基变量取值，这里为3+4-1=6个空格：对应解中非基变量表上作业法的基本思想是:先设法给出一个初始方案(如典例所示),然后根据确定的判别准则对初始方案进行检查、调整、改进，直至求出最优方案。表上作业法和单纯形法的求解思想完全一致，但是具体作法更加简捷。3.2表上作业法

确定初始方案(初始基可行解)

改进调整（换基迭代）否

判定是否最优？是结束最优方案——求解思路图表上作业法1.最小元素法2.沃格尔（Vogel）法(一)初始方案的给定给定初始方案的方法很多(如前例)，一般来说，希望方法简便易行，并能给出较好的方案。减少迭代次数。这里介绍1.最小元素法基本思想：就近供应，即优先考虑单位运价最小（或运距最短）的供销业务，最大限度地满足其供销量。销地产地产量311310719284741059销量3656203－3－31－1－1－4－4-6－66433－3－3-3-3销地产地产量311310719284741059销量365620316433Z=4*3+3*10+3*1+1*2+6*4+3*5=86最小元素法的说明退化现象：

部分产量和＝部分销量和在迭代过程中，可能出现一行和一列同时被划去。销地产地产量31145777384121069销量36562034－4－4－1－1-6－6616－3－3－6-60为使迭代过程中基变量的个数恰好为(m+n-1)个，应在同时划去的一行或一列中的某个格中填入数字0，表示这个格中的变量是取值为0的基变量。以便当做有数字的格看待。销地产地产量31145777384121069销量365620346160基本思想：优选考虑最大差额（最小运价优势）方案行（列）差额（罚数）=次小运价系数-最小运价系数2.沃格尔（Vogel）法(差额法)行差额列差额1023206563销量95474891710113产量

销地产地0112513()6220071312121162()33()521108()1023206563销量95474891710113产量

销地产地633521一般当产销地数量不多时，(Vogel)法给出的初始方案有时就是最优方案。沃格尔法Z=5*3+2*10+3*1+1*8+6*4+3*5=85最小元素法Z=4*3+3*10+3*1+1*2+6*4+3*5=86>8529练习.求下表给出的运输问题的初始基本可行解．

B1B2B3B4产量A14104420A2773815A31210615销量510251050(一)初始方案的给定30

销地产地B1B2B3B4aiA14104420A2773815A31210615销量5102510505100151010(一)初始方案的给定31BjAiB1B2B3B4aiA14104420A2773815A31210615bj5102510505100151010(一)初始方案的给定

最小元素法或Vogel法给出的是一个运输问题的基可行解，需要通过最优性检验判别该解得目标函数值是否最优，当为否时，应进行调整得到优化.(二)最优性检验与方案的调整基本思想：计算非基变量（未填上数值的格，即空格）的检验数（也称为空格的检验数），若全部大于等于零，则该方案就是最优调运方案，否则就应进行调整。1.闭回路法2.对偶变量法（位势法）沿水平或垂直方向前，向左或右转90度（当然也可以不改变方向）继续前进，这样继续下去，直至回到出发的那个空格，由此形成的封闭折线叫做闭回路。闭回路

x25x23

B1B2B3B4B5A1

A2

A3

x35A4

x43

x11x12x31

x42表中闭回路的变量集合是{x11,x12,x42,x43,x23,x25,x35,x31}共有8个顶点，这8个顶点间用水平或垂直线段连接起来，组成一条封闭的回路。

运输问题中的闭回路有关闭回路的一些重要结果

定理3-设是一个闭回路，则该闭回路中的变量所对应的系数列向量具有下面的关系：推论

若一组变量包含闭回路，则这组变量所对应的系数列向量线性相关。

推论

m+n-1个变量构成基变量的充要条件是该变量组不含闭回路。将如下表中6个顶点间用水平或垂直线段连接起来，组成一条封闭的回路。1023206563销量95346748191371034113产量

销地产地(A2,B1),(A3,B2)无法连入闭回路中闭回路孤立格是指在所在行或列中唯一出现的变量。孤立格一定不会成为闭回路的顶点最小元素法得初始方案

以确定了初始调运方案的作业表为基础，以一个非基变量作为起始顶点，寻求闭回路。

该闭回路的特点是：除了起始顶点是非基变量（对应着空格）外，其他顶点均为基变量（对应着填有数字的格）。对于每一个非基变量而言，以其为起点的闭回路存在且唯一。运输问题中的闭回路目的：计算解中各非基变量(空格)的检验数基本思路：对于代表非基变量的空格（其调运量为零），把它的调运量调整为1（每次调整一个非基变量）；由于产销平衡的要求我们必须对这个空格的闭回路的顶点的调运量加上或减少1(可行条件)；计算出由这些变化给整个运输方案的总运输费带来的变化，这里称之为检验数。闭回路法求检验数4.如果所有代表非基变量的空格的检验数也即非基变量的检验数都大于等于零，则已求得最优解，否则进行方案调整（后续）23206563销量9544

11

3710

产量

销地产地64333同理可以找出所有空格（即非基变量）的检验数。+1－1＋1－1总运费变化＝即此新可行解较原来解运费增加1元闭回路法求检验数闭回路法求检验数23206563销量954411

3710

产量

销地产地6433-1+1-1+1-1+1总运费变化＝7

约定作为起始顶点的非基变量为第一个奇数次顶点，相邻顶点为偶次顶点，其它顶点依次排列，那么，该非基变量xij的检验数：=（闭回路上奇数次顶点运价之和）－（闭回路上偶数次顶点运价之和）

-11A21210A321A1B4B3B2B1销地产地检验数表闭回路法求检验数当至少有一个非基变量的检验数是负值时，说明作业表上当前的调运方案不是最优的，应进行调整。请画出下表空格(1,1)和(1,4)的闭回路10050120708090闭回路法求调整方案选一个非基变量变为基变量进基选一个基变量变为非基变量离基反映在运输表上就是要选一个空格填上大于0的数选择入基的原则是：从绝对值最大的负检验数格(k,l)出发闭回路法求调整方案-11A21210A321A1B4B3B2B1销地产地检验数表在作业表上以（A2,B4）为起点作一条除该空格外其余顶点均为有数字格组成的闭回路闭回路法求调整方案206563销量94

1

374

产量销地产地

6

33

调运方案（最小元素法得到）+1-1=min{3,1}=1离基？在作业表上以（A2,B4）为起点作一条除该空格外其余顶点均为有数字格组成的闭回路在这条闭回路上，在保持产销平衡的条件下对偶数顶点格子的运量做最大可能的调整+1-1闭回路法求调整方案（A2,B4）为起点作一条出该空格外其余顶点均为有数字各组成的闭回路206563销量94

375

产量

销地产地

6

32

调运方案（最小元素法得到）1=min{3,1}=1继续用闭回路检验，直到检验数σ≥01.在作业表上从绝对值最大的负检验数格(k,l)出发,即xkl为起始变量作出闭回路。2.以空格(k,l)为第一个奇数顶点，沿闭回路的顺（或逆）时针方向依次对顶点编号。3.在闭回路上的所有偶数顶点中，找出运输量最小的格子，以该格对应的变量为离基变量。4.调整量5.将该闭回路上所有奇数顶点处的运输量都增加

所有偶数顶点处的运输量都减去ij

=min{该闭回路中偶数次顶点运输量xij}闭回路法求调整方案

在闭回路方法当中，要判断一个方案是否最优，需要通过每一个空格来寻找回路，以及根据闭回路求出每个空格的检验数，当一个运输问题的产地和销地很多时，用此方法工作量十分繁重.位势法位势法是根据对偶理论推导出来的一种求解检验数方法。运输方案的调整同前面的闭回路法.49位势法求检验数原问题对偶问题50记原问题基变量XB的下标集合为I，有如下式子成立：解上面第一个方程，将ui、vj代入第二个方程求出检验数,称ui(i=1,…,m),vj(j=1,…,n)分别成为第i行和第j列的位势回忆：这里Pij有如何特殊形式?位势法求检验数对偶变量uiu1u2u3对偶变量vjv1v2v3v4不妨令v1=1，则u2=0;v3=2;u1=1;v4=9;u3=-4;v2=8.(1)(0)(-4)(1)(8)(2)(9)1023206563销量95346748191371034113产量

销地产地注意：由于这些位势的数值是相互关联的，所以填写时可以先任意决定其中的一个，然后推导出其他位势的数值。A2A3A1B4B3B2B1销地产地检验数表121-11012uiu1u2u3vjv1v2v3v4(1)(0)(-4)(1)(8)(2)(9)1023206563销量95346748191371034113产量

销地产地位势法计算非基变量xij检验数的公式σij=cij-（ui+vj）=（闭回路上奇数次顶点运距或运价之和）-（闭回路上偶数次顶点运距或运价之和）闭回路法计算非基变量xij检验数的公式：复习比较检验数计算的两种方法思考：试解释位势变量的含义（提示：写出运输问题的对偶问题）表

上

作

业

法得到最优方案算出的总运价分析实际问题列出产销平衡表及单位运价表求检验数（闭回路法或位势法）

是确定初始调运方案（最小元素法或Vogel法）

找出绝对值最大的负的检验数用闭回路调整，得出新的调运方案否循环所有检验数≥0求

解步骤1产销2销产3.扩大的运输问题（中转站）3.3产销不平衡运输问题及其应用Minz=cij·xijni=1j=1mMinz=cij·xij+0xi,n+1ni=1j=1mi=1m相当于：增加一个假想销地1.产销问题ai>bj产地销地A1A2┊AmB1 B2 ┈

BnC11 C12 ┈ C1nC21 C22 ┈ C2n┆ ┊ ┈ ┊Cm1 Cm2 ┈ CmnBn+1０

０┆０销量产量b1 b2 ┈

bna1a2┊amaibj相当于：增加一个假想销地产销问题单位运价表Minz=cij·xijni=1j=1mMinz=cij·xij+0xm+1,jni=1j=1mj=1n销产问题相当于：增加一个假想产地ai<bj产地销地A1A2┊AmB1 B2 ┈

BnC11 C12 ┈ C1nC21 C22 ┈ C2n┆ ┊ ┈ ┊Cm1 Cm2 ┈ CmnAm+10 0 ┈ 0销量产量b1 b2 ┈

bna1a2┊ambjai销产问题单位运价表相当于：增加一个假想产地例一：某工厂按合同规定必须于当年的每个季度末分别提供10、15、25、20台同一规格的柴油机。已知该厂的生产能力及生产每台柴油机的成本如表示。又如果生产出来的柴油机当季不交货，每台每积压一个季度需要存储维护费用0.15万元。要求在完成合同的情况下，做出使全年生产费用最小的决策。季度生产能力(台)单位成本(万元/台)ⅠⅡⅢⅣ2535301010.811.111.011.3运输问题案例1数学模型：设xij第i季度生产，用于第j季度交货的数量。目标函数：

minz=cijxiji=1j=1

44x11+x12+x13+x1425

x22+x23+x2435

x33+x3430

x4410x11=10x12+x22

=15x13+x23+x33

=25x14+x24+x34+x44=20xij0,(i=1,····,4;j=1,····,4)供应：ⅠⅡⅢⅣⅠⅡⅢⅣ需求：季度生产能力(台)单位成本(万元/台)ⅠⅡⅢⅣ2535301010.811.111.011.3某工厂按合同规定必须于当年的每个季度末分别提供10、15、25、20台同一规格的柴油机。合同要求交货不得超过生产力产>销数学模型：季度生产能力(台)单位成本(万元/台)ⅠⅡⅢⅣ2535301010.811.111.011.3每台每积压一个季度需要存储维护费用0.15万元。单位运价表：ⅠⅡⅢⅣ销量ⅠⅡ Ⅲ ⅣD产量10.8 10.95 11.1011.25025

M11.1011.25

11.40035

M

M 11.00

11.15030单位：万元供应需求10 15 25

2030M MM

11.30010当i>j时，必须xij=0，令cij=M(很大的正数)，加以惩罚产>销

例二有A、B、C三个化肥厂供应四个地区Ⅰ、Ⅱ、Ⅲ、Ⅳ的农用化肥，三个工厂每年各自的产量为A--50万吨，B--60万吨，C--50万吨。四个地区的需求量分别是Ⅰ地区最高50万吨，最低30万吨，Ⅱ地区为70万吨，Ⅲ地区为30万吨以下，Ⅳ地区不低于10万吨。问：如何调运，可使总的调运费用最小？单位调运费用如下表所示。产地销地A1A2A3B1B2B3B4产量销量1613221714131915192023―单位运价表50605030-50700-3010-单位：万元/万吨设xij--第i工厂调至第j需求地区的化肥数量运输问题案例2销产上限50运输问题案例2ABCDⅠ Ⅰ Ⅱ Ⅲ Ⅳ Ⅳ

16 16 13 22 17 1714 14 13 19 15 1519 19 20 23 M MM 0 M 0 M 0供应需求产量销量50605050

30

20

70

30

10

50修正运价表产地销地A1A2A3B1B2B3B4产量销量1613221714131915192023―单位运价表50605030-50700-3010-单位：万元/万吨设xij--第i工厂调至第j需求地区的化肥数量销产扩大的运输问题例：在前面的糖果例题中，若既可以从Ai运到Bj，也可以经过中间站T1、T2、T3、T4或者Ai、Bj转运，称扩大的运输问题。几点说明：1.所有的产地、销地、中间站均视作产地、销地；2.所有中转站的转运量等于总的产量之和；3.不能出现循环倒运现象，允许自身往自身最多调运一次，运价为Cij=0；4.实际产地产量为转运量与该产地实际产量之和，实际销地销量为转运量与实际销量之和。A1A2A3T1T2T3T4B1B2B3B4A1A2A3T1T2T3T4B1B2B3B401310-3-0214335-21-2331131019287410523115-4-232331711943210108501321011310221202846452718241-262411858-422267460142102142032130产销产量销量27242920202020202020202020202020202023262526产销平衡表

某餐馆承办宴会，每晚连续举行，共举行五次。宴会上需用特殊的餐巾，根据参加的人数，预计