大学精品课件：第三章(运输问题).ppt

1、2023-3-1浙江科技学院经济管理学院管工系1第三章 运输问题3.1 3.1 运输问题及其数学模型运输问题及其数学模型3.2 3.2 表上作业法表上作业法3.3 3.3 运输问题的进一步讨论运输问题的进一步讨论2023-3-1浙江科技学院经济管理学院管工系2本章学习要求本章学习要求n掌握表上作业法及其在产销平衡运输问题求掌握表上作业法及其在产销平衡运输问题求解中的应用解中的应用n掌握产销不平衡运输问题的求解方法掌握产销不平衡运输问题的求解方法2023-3-1浙江科技学院经济管理学院管工系33.1 运输问题及其数学模型 运输问题的一般提法：假设有运输问题的一般提法：假设有m个生产地点，可以供个

2、生产地点，可以供应某种物资（以后称为产地），用应某种物资（以后称为产地），用Ai来表示，来表示，i=1,m,有有n个销地，用个销地，用Bj来表示，来表示，j=1,n，产地，产地的产量和销地的销量分别为的产量和销地的销量分别为ai,bj，从产地，从产地Ai到销地到销地Bj运输一个单位物资的运价为运输一个单位物资的运价为Cij，这些数据可汇总于，这些数据可汇总于下表，在假设产销平衡的条件下，即下表，在假设产销平衡的条件下，即ai=bj，问该，问该如何调运物品使总运费最小？如何调运物品使总运费最小？B1B2Bn产量A1C11C12C1na1A2C21C22C2na2AmCm1Cm2Cmnam销量b1

3、b2bn2023-3-1浙江科技学院经济管理学院管工系4建模：设建模：设xij表示从表示从Ai到到Bj的运量，则所求的的运量，则所求的数学模型为：数学模型为：min=cijxij s.t.xij=ai i=1,mxij=bj j=1,nj=1ni=1mi=1mj=1nxij0 i=1,m,j=1,n2023-3-1浙江科技学院经济管理学院管工系5例如：三个产地四个销地，用网络表示例如：三个产地四个销地，用网络表示2312341b1=22b2=13b3=12b4=13a2=27a3=19a1=14产地产地运价运价销地销地6753482759106产量产量销量销量总产量总产量60吨吨总销量总销量6

4、0吨吨产销平衡的运输问题产销平衡的运输问题2023-3-1浙江科技学院经济管理学院管工系60131213221927146109572483576min343332312423222114131211342414332313322212312111343332312423222114131211343332312423222114131211=+=+=+=+=+=+=+=xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxs.t.xxxxxxxxxxxxz其运输问题线性规划模型其运输问题线性规划模型产量约束产量约束销量约束销量约束3.2表上作业法表上作业法一、表上作业法的基

5、本概念与重要结论一、表上作业法的基本概念与重要结论A=x11 x12 x1n x21 x22 x2n xm1 xm2 xmn1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 12023-3-1浙江科技学院经济管理学院管工系8定义定义1：设：设E是运输问题的一组变量，如果对是运输问题的一组变量，如果对E中变量适当排列中变量适当排列使其能够成为具有下列形式的序列：使其能够成为具有下列形式的序列：xi1j1,xi1j2,xi2j2,xi2j3,xisjs,xisj1其中其中i1,is;j1,js各不相同，则称各不相同，则称E为运输问题的一个闭回路。为运输问题的一个闭回路。E中的变量称

6、为此闭回路的顶点。中的变量称为此闭回路的顶点。例例.当当m=4,n=5时，时，x25,x22 x32,x34 x14,x15 为一闭回路。为一闭回路。A1A2A3 A4 AiBjB1 B2 B3 B4 B5 定理：（定理：（1）运输问题中的）运输问题中的m+n个约束方程中只个约束方程中只有有m+n-1个是相互独立的，而且其中任意个是相互独立的，而且其中任意m+n-1个方个方程都是相互独立的；程都是相互独立的；(2)运输问题中个运输问题中个m+n-1变量能构成一组基本变量变量能构成一组基本变量的充要条件是：不存在一条全以此的充要条件是：不存在一条全以此组内变量为顶点的组内变量为顶点的闭回路；闭回

7、路；(3)设设是运输问题的一组基本变量，变量是运输问题的一组基本变量，变量xij不不在在内，则必存在一条唯一的全以内，则必存在一条唯一的全以Uxij中变量为顶中变量为顶点的闭回路；点的闭回路；(4)若若ai,bj均是整数，则任一基本解中各变量的取值均是整数，则任一基本解中各变量的取值均为整数。均为整数。2023-3-1浙江科技学院经济管理学院管工系10二、表上作业法二、表上作业法1.找出初始基可行解，即在（找出初始基可行解，即在（mn）产销平衡表）产销平衡表上给出上给出m+n-1个有数字的格，这些有数字的格个有数字的格，这些有数字的格不能构成闭回路，且行和等于产量，列和等于不能构成闭回路，且行

8、和等于产量，列和等于销售量。销售量。2.求各非基变量的检验数，即在表中求空格的检求各非基变量的检验数，即在表中求空格的检验数，判断是否达到最优解。如果达到，则停验数，判断是否达到最优解。如果达到，则停止计算，否则转入下一步。止计算，否则转入下一步。3.确定换入变量和换出变量，找出新的基可行解，确定换入变量和换出变量，找出新的基可行解，在表上用闭回路法调整。在表上用闭回路法调整。4.重复重复2、3，直到求得最优解为止。，直到求得最优解为止。2023-3-1浙江科技学院经济管理学院管工系111、确定初始基可行解n运输问题基的表示运输问题基的表示n最小元素法最小元素法n沃格尔法沃格尔法2023-3-

9、1浙江科技学院经济管理学院管工系12运输问题基的表示运输问题基的表示 m个产地、个产地、n个销地的运输问题，任何一个基要满个销地的运输问题，任何一个基要满足以下三个条件：足以下三个条件：n 基变量的个数为基变量的个数为m+n-1；n 基变量不能形成闭回路；基变量不能形成闭回路；n 行和等于各产地的产量，列和等于各销地的销量行和等于各产地的产量，列和等于各销地的销量2023-3-1浙江科技学院经济管理学院管工系13123412312341231234123123412312341231234123基在运输表中的表示基在运输表中的表示2023-3-1浙江科技学院经济管理学院管工系141234123

10、12341231234123123412312341231234123运输表中同行同列组成回路的变量运输表中同行同列组成回路的变量2023-3-1浙江科技学院经济管理学院管工系15（1）最小元素法）最小元素法采用就近供应采用就近供应(运费最小运费最小)原则，安排运输。原则，安排运输。例例.某公司经销甲产品，它下设三个加工厂，每日的产量分某公司经销甲产品，它下设三个加工厂，每日的产量分别为别为a1=7吨，吨，a2=4吨，吨，a3=9吨，该公司把这些产品分别运往四吨，该公司把这些产品分别运往四个销售点，各销售点的每日销售量为：个销售点，各销售点的每日销售量为：b1=3吨，吨，b2=6吨，吨，b3=

11、5吨，吨，b4=6吨，吨，已知从各工厂到各销售点的单位产品的运已知从各工厂到各销售点的单位产品的运价如表所示，问该公司应如何调运产品在满足各销售点的需要价如表所示，问该公司应如何调运产品在满足各销售点的需要量前提下，使总的运费为最少？量前提下，使总的运费为最少？解：先画出这个问题的产销平衡表：解：先画出这个问题的产销平衡表：B1B2B3B4产量A13113107A219284A3741059销量36562023-3-1浙江科技学院经济管理学院管工系16B1B2B3B4产量产量A13113107A219284A3741059销量销量3656B1B2B3B4A1A2A3采用最小元素法，得采用最小元

12、素法，得运输方案：运输方案：Z=8631144363332023-3-1浙江科技学院经济管理学院管工系17例：同时划一行和一列的情况例：同时划一行和一列的情况B1B2B3B4产量产量A1531049A216964A32010577销量销量35842023-3-1浙江科技学院经济管理学院管工系18B1B2B3B4产量产量A1531049A216964A32010577销量销量3584B1B2B3B4A1A2A3311445407(2)沃格尔沃格尔(Vogel)法法 沃格尔法的思想沃格尔法的思想:一产地的产品假如不能按最小运费就近一产地的产品假如不能按最小运费就近供应，就考虑次小运费，这就有一个差

13、额。差额越大的地方，供应，就考虑次小运费，这就有一个差额。差额越大的地方，说明不能说明不能按最小运费调运时，运费增加越多。因而对差额最按最小运费调运时，运费增加越多。因而对差额最大处，就应当优先采用最小运费。大处，就应当优先采用最小运费。步骤：步骤：(一一)计算各行和各列的最小运费和次最小运费的差额，即计算各行和各列的最小运费和次最小运费的差额，即行罚数和列罚数。行罚数和列罚数。(二二)从行和列罚数中选出最大者，选择它所在行或列中从行和列罚数中选出最大者，选择它所在行或列中的最小元素进行运输，划出满足需求的行或列。的最小元素进行运输，划出满足需求的行或列。(三三)对未划去的元素分别计算各行、各

14、列的最小运费和对未划去的元素分别计算各行、各列的最小运费和次最小运费的差额。次最小运费的差额。重复（二）（三）重复（二）（三）,直至得出初始解。直至得出初始解。2023-3-1浙江科技学院经济管理学院管工系20B1B2B3B4A1A2A3B1B2B3B4行罚数行罚数产量产量A13113107A219284A3741059列罚数列罚数销量销量36560112513632322317652321采用沃格尔法，得运采用沃格尔法，得运输方案：输方案：Z=852、最优解的判别最优解的判别（1）闭回路法）闭回路法 思想方法：让非基变量增大，判断目标值是否减思想方法：让非基变量增大，判断目标值是否减小，也就

15、是看，非基变量的检验数是否大于零。小，也就是看，非基变量的检验数是否大于零。检验数检验数 ij=奇数点奇数点cij-偶数点偶数点cij具体做法，在给出调运方案的计算表上，从每一具体做法，在给出调运方案的计算表上，从每一空格出发，找一条闭回路。空格出发，找一条闭回路。闭回路法计算闭回路法计算 ij的经济意义：在闭回路上，空格的经济意义：在闭回路上，空格处每增加一单位运输量，引起目标函数的变化量。处每增加一单位运输量，引起目标函数的变化量。2023-3-1浙江科技学院经济管理学院管工系22B1B2B3B4产量产量A13113107A219284A3741059销量销量3656B1B2B3B4A14

16、3A231A363非基变量非基变量闭回路闭回路检验数检验数x11x11 x13 x23 x213-3+2-1=1x12x12 x14 x34 x3211-10+5-4=2x22x22 x23 x13 x14 x34 x329-2+3-10+5-4=1x24x24 x14 x13 x238-10+3-2=-1x31x31 x34 x14 x13 x23 x217-5+10-3+2-1=10 x33x33 x34 x14 x1310-5+10-3=12采用最小元素法，得运输方案：采用最小元素法，得运输方案：2023-3-1浙江科技学院经济管理学院管工系23（2）位势法（对偶变量法）位势法（对偶变量

17、法）CBB-1=(U1,U2,Um,V1,V2,Vn)又因变量又因变量xij的系数列向量为的系数列向量为pij=(0,0,1,0,0,1,0,)T 设设 U1,U2,Um,V1,V2,Vn 是对应是对应m+n个约束条个约束条件的对偶变量，其中件的对偶变量，其中Ui对应第对应第i个产地的产量约束，个产地的产量约束，Vj对应第对应第j个销地的销量约束，称个销地的销量约束，称Ui为行位势，为行位势，Vj为为列位势，由对偶理论知：列位势，由对偶理论知：第第m+j个分量个分量第第i个分量个分量所以所以CBB-1 pij=Ui+Vj于是于是ij=cij-（Ui+Vj）2023-3-1浙江科技学院经济管理学

18、院管工系24 因为基变量的检验数为因为基变量的检验数为0，故所有数字格有：，故所有数字格有：ui+vj=cij，而基变量的个数为，而基变量的个数为m+n-1个，所以这个，所以这样的方程就有样的方程就有m+n-1个，而这时任意给定其中一个，而这时任意给定其中一个变量的值（通常令个变量的值（通常令U1=0），则可以求得），则可以求得U1,U2,Um,V1,V2,Vn 的一组值，代入的一组值，代入 ij=cij-（Ui+Vj），即可得所有非基变量（即空格）的），即可得所有非基变量（即空格）的检验数。检验数。2023-3-1浙江科技学院经济管理学院管工系25B1B2B3B4行位势行位势A1 3 11

19、3 10A2 1 9 2 8A3 7 4 10 5列位势列位势B1B2B3B4A143A231A3634313630310-12-59121-11012可以看出可以看出 24 0，所以此方案不是最所以此方案不是最优解。与闭回路法优解。与闭回路法的结果是一致的的结果是一致的2023-3-1浙江科技学院经济管理学院管工系263、解的改进、解的改进闭回路调整法闭回路调整法1）确定进基格）确定进基格原则：原则：min ij ij0优先进基优先进基2）找出闭回路）找出闭回路3）出基格的确定）出基格的确定在闭回路上调整运量在闭回路上调整运量调整量调整量=min偶数点偶数点xij调整：奇数点调整：奇数点+偶

20、数点偶数点-2023-3-1浙江科技学院经济管理学院管工系27 进基格：x24 闭回路：x24 x14 x13 x23调整量调整量=min1,3=1调整：调整：x24=0+1=1，x14=3-1=2 x13=4+1=5，x23=1-1=0，则则x23出基出基B1B2B3B4行位势行位势A1 3 11 3 10A2 1 9 2 8A3 7 4 10 5列位势列位势4313630310-12-59121-110122023-3-1浙江科技学院经济管理学院管工系28B1B2B3B4行位势行位势A1 3 11 3 10A2 1 9 2 8A3 7 4 10 5列位势列位势B1B2B3B4A152A23

21、1A3635213630310-23-59022912可以看出可以看出 ij 0，所，所以此方案是最优解。以此方案是最优解。又因为又因为 11=0所以是所以是无穷多解的情况。无穷多解的情况。12023-3-1浙江科技学院经济管理学院管工系29单纯形法与表上作业法比较单纯形法与表上作业法比较单纯形法（单纯形法（Min）表上作业法表上作业法确定初确定初始基变始基变量量XB+松驰变量松驰变量+（人工变量）（人工变量）XB系数矩阵为系数矩阵为I，m个个其余其余XN最小元素法、沃格尔法最小元素法、沃格尔法XB数字格，数字格，m+n-1个个XN 空格空格检验数检验数基变量基变量 j=0非基变量非基变量 j

22、=cj-cBB-1pj基变量基变量 ij=0非基变量非基变量 ij=cij-Ui-Vj调整调整进基：进基：min j j 0出基：出基：minbi/aik，aik0进基：进基：min ij ijbj方法：虚购一销地方法：虚购一销地Bn+1，其销量，其销量bn+1=ai-bjAi运往运往Bn+1物资的数量物资的数量xin+1，就是产地就地贮存的，就是产地就地贮存的物资量，因此，产地到虚销地的单位运价均为物资量，因此，产地到虚销地的单位运价均为0，即即cin+1=0，这样，就转化成了一个产销平衡问题。，这样，就转化成了一个产销平衡问题。2023-3-1浙江科技学院经济管理学院管工系31例：某建筑公

23、司有例：某建筑公司有A1、A2、A3三个水泥库，其水泥三个水泥库，其水泥贮存量分别为贮存量分别为30吨、吨、50吨、吨、60吨，四个工地吨，四个工地B1、B2、B3、B4需要水泥的数量依次为需要水泥的数量依次为15吨、吨、10吨、吨、40吨、吨、45吨，已知从各库到各工地运送每吨水泥吨，已知从各库到各工地运送每吨水泥的费用如下表，求使运费最少的调运方案？的费用如下表，求使运费最少的调运方案？B1B2B3B4产量产量A13050804030 A27040806050A310030502060销量销量15104045解：计算解：计算ai=140，bj=110，aibj所以要虚构一销地所以要虚构一销

24、地B5，其销量，其销量b5=30，而，而ci5=0，这样，就转，这样，就转化成了一个产销平衡问题。化成了一个产销平衡问题。2023-3-1浙江科技学院经济管理学院管工系322）产小于销，即）产小于销，即aibj方法：虚购一产地方法：虚购一产地Am+1，其产量，其产量am+1=bj-aiA Am+1m+1运往运往B Bj j物资的数量物资的数量x xm+1jm+1j，就是各销地缺货的物资量，就是各销地缺货的物资量，因此，虚产地到各销地的单位运价均为因此，虚产地到各销地的单位运价均为0 0，即，即c cm+1jm+1j=0=0，这样，就转化成了一个产销平衡问题。这样，就转化成了一个产销平衡问题。例

25、如：B1B2B3B4产量产量A13113109 A219284A3741057销量销量1361562023-3-1浙江科技学院经济管理学院管工系33二、一些变形和推广二、一些变形和推广1、最大化问题、最大化问题作法：作法：1）找出单位物资效益表（）找出单位物资效益表（cij）中的最大元素）中的最大元素M，即，即M=maxcij2)令令bij=M-cij，并视为运价。，并视为运价。3）由）由bij构成单位运价表，按通常的表上作业法求解，求得构成单位运价表，按通常的表上作业法求解，求得最优解后还要把所得结果转换为原问题的答案。最优解后还要把所得结果转换为原问题的答案。2、销量不确定（有最高需求和最

26、低需求）、销量不确定（有最高需求和最低需求）设销地设销地Bk的最低需求为的最低需求为bk，最高需求为，最高需求为bk，这时可把看作，这时可把看作Bk和和Bk两个销地，两个销地，Bk需求量需求量bk，Bk的需求量的需求量bk-bk2023-3-1浙江科技学院经济管理学院管工系34例：设某种材料有例：设某种材料有A1、A2、A3三个生产厂家，其产品供应三个生产厂家，其产品供应B1、B2、B3、B4四个城市，假定等量的材料在这些城市的使四个城市，假定等量的材料在这些城市的使用效果相同，已知各建材厂的年产量、各城市的年需求量用效果相同，已知各建材厂的年产量、各城市的年需求量以及各厂到各城市运送单位建材

27、的运价如表所示，求使运以及各厂到各城市运送单位建材的运价如表所示，求使运费最少的调运方案？费最少的调运方案？B1B2B3B4产量产量A11613221750 A21413191560A3192023M50最低需求最低需求3070010最高需求最高需求507030不限不限解释解释c34=M（M是一个无穷大的正数），这意味着不允许从是一个无穷大的正数），这意味着不允许从A3运货至运货至B4，或者因为交通不方便等原因，使从，或者因为交通不方便等原因，使从A3到到B4不不可能送货。可能送货。2023-3-1浙江科技学院经济管理学院管工系35B1B2B3B4产量产量A11613221750 A21413

28、191560A3192023M50最低需求最低需求3070010最高需求最高需求507030不限不限B1B1B2B3B4B4销量销量302070301050A1A2A3A4产量产量50605050161419M1614190131320M22192301715MM1715M02023-3-1浙江科技学院经济管理学院管工系363、指定销售问题、指定销售问题如规定销地如规定销地1的需求量必须由产地的需求量必须由产地4供应，如供应，如何处理？何处理？1）直接令）直接令x41=b12)令令c41=-M，或者，或者c11=c21=c31=M样销地样销地1的的需求量肯定是由产地需求量肯定是由产地4供应了。

29、供应了。2023-3-1浙江科技学院经济管理学院管工系374、缺货损失问题、缺货损失问题如下表，设销地如下表，设销地1 1不允许缺货；销地不允许缺货；销地2 2缺货，单位损失费缺货，单位损失费3 3元；销地元；销地3 3缺货，单位损失费缺货，单位损失费2 2元，问如何处理？元，问如何处理？B1B2B3产量产量A151710 A264680A332515销量销量655525B1B2B3产量产量A151710 A264680A332515销量销量655525A440M322023-3-1浙江科技学院经济管理学院管工系38三、生产与存储问题三、生产与存储问题例：某厂按合同须于当年每个季度末分别提供例

30、：某厂按合同须于当年每个季度末分别提供10、15、25、20台同一规格的起重机，已知该厂各季度的生产能力及生产每台同一规格的起重机，已知该厂各季度的生产能力及生产每台起重机的成本如表所示，若生产出来的起重机当季不交货，台起重机的成本如表所示，若生产出来的起重机当季不交货，每台每积压一个季度工厂需支付保管及维护费每台每积压一个季度工厂需支付保管及维护费0.15万元，试万元，试问在按合同完成任务的情况下，工厂应如何安排生产计划才问在按合同完成任务的情况下，工厂应如何安排生产计划才能使全年消耗的生产与存贮费用的总和最少？能使全年消耗的生产与存贮费用的总和最少？季度季度工厂生产能力（台工厂生产能力（台

31、/季）季）工厂生产成本（台工厂生产成本（台/季）季）交货量（台）交货量（台）12510.81023511.101533011.002541011.30202023-3-1浙江科技学院经济管理学院管工系39发货点：生产起重机的四个季度发货点：生产起重机的四个季度发货量：生产能力发货量：生产能力收货点：按合同交付起重机的四个季度收货点：按合同交付起重机的四个季度收货量：按合同提供起重机的数量收货量：按合同提供起重机的数量cij=第第i季度每台起重机的生产成本季度每台起重机的生产成本+（j-i）个季度每台起重机）个季度每台起重机的存贮费（的存贮费（ji）12345发量（台）发量（台）12523533

32、0410收量（台）收量（台）101525203010.8010.9511.1011.25M11.1011.2511.40MM11.0011.15MMM11.3000002023-3-1浙江科技学院经济管理学院管工系40四、有转运的运输问题四、有转运的运输问题1、运输表的构成、运输表的构成1）产地：原产地、中间转运站、转运物资的销地）产地：原产地、中间转运站、转运物资的销地2）销地：原销地、中间转运站、转运物资的产地）销地：原销地、中间转运站、转运物资的产地3）设各转运站转运物资的数量均为）设各转运站转运物资的数量均为 ai这样专职转运站的产量和销量均为这样专职转运站的产量和销量均为 ai而原产

33、地而原产地Ai的产量均为（的产量均为（ai+ai）原销地原销地Bj的销量均为（的销量均为（bj+ai）4)将各条线路实际的运输单位列成单位运价表，其将各条线路实际的运输单位列成单位运价表，其中不可能的运输其单位运价用中不可能的运输其单位运价用M表示。表示。2023-3-1浙江科技学院经济管理学院管工系412、举例：、举例：A、B两个化肥厂每年各生产磷肥两个化肥厂每年各生产磷肥900,600万吨，这些化万吨，这些化肥要通过公路运到三个港口，然后再装船运往其他各地，肥要通过公路运到三个港口，然后再装船运往其他各地，已知三个港口已知三个港口C、D、E每年能承担的船运量分别为每年能承担的船运量分别为700、400、300万吨，两个工厂及三个港口之间均有公路相通，万吨，两个工厂及三个港口之间均有公路相通，且已知单位运价如表所示，为按需要把磷肥运到各港口，且已知单位运价如表所示，为按需要把磷肥运到各港口，怎样安排运输才能使运费最少？怎样安排运输才能使运费最少？ABCDEA029107B2071010C97034D1010302E7104202023-3-1浙江科技学院经济管理学院管工系42ABCDEA029107B2071010C97034D1010302E710420P发量发量收量收量240021001500150015001500150022001900180010000000