3.1-运输问题的模型解析

第3章

运输问题（TP）学习目标了解运输问题数学模型及其特点。

掌握产销平衡运输问题的表上作业法。

学会产销不平衡运输问题的转化。

学习表上作业法在物流管理中的典型应用。23运输问题（TP）运输问题的模型3.1运输问题的表上作业法3.2产销不平衡的运输问题3.3运输问题的应用案例3.4运输问题的Excel处理3.53运输问题（TP）3有时候为了书写简便，运输问题也被写做TP（TransportationProblem）。例：对某种物资，设有m个产地A1,A2,…,Am，称它们为发点，其对应产量为a1,a2,…,am，称它们为产量；另有n个销地B1,B2,…,Bn，称它们为收点，其对应销量为b1,b2,…,bn，称它们为销量。

又知，从产地（发点）Ai运至销地（收点）Bj，该种物资每单位的运价为cij（cij≥0）。

试问：应如何安排调运方案，在满足一定要求的前提下，使总运费最低？43.1运输问题的模型53.1运输问题的模型根据上述参量的意义列出产量、销量和运价，如表3.1所示3.1运输问题的模型表中：ai、bj、cij的单位为吨、千克、件等，即ai,bj,cij的单位类别应该一致（i

=

1,2,…,m；j

=

1,2,…,n）。表的右下角

表示各产地产量的总和，即总产量或总发量；

表示各销地销量的总和，即总销量或总收量。这时有两种可能：

总产量=总销量即产销平衡问题总产量≠总销量即产销不平衡问题63.1运输问题的模型先讨论产销平衡问题，再讨论产销不平衡问题。令xij表示某物资从发点Ai到收点Bj的调拨量（运输量），可以列出产销平衡表，如表3.2所示。73.1运输问题的模型将表3.1与表3.2合在一起，得到一个新表，这一新表被称为运输表（或称为产销矩阵表），如表3.383.1运输问题的模型根据产销矩阵表，求上述问题的解等于求下面数学模型的解。

xij（i

=

1,2,…,m；j

=

1,2,…,n）93.1运输问题的模型从上述这一特殊的线性规划（LP）问题，可以得到下列三条结论。该问题的基变量有m

+

n

−1个。该问题一定有最优解。如果ai和bj全是整数，则该问题一定有整数最优解。1011A1A2A3B1B2B3B47t4t9t3t6t5t6t

问题：如何安排调运方案，在满足各销售地点需要的情况下，使总的运费最少。总产量：7t+4t+9t=20t总销量：3t+6t+5t+6t=20t总产量=总销量：产销平衡问题产地销地已知：各个产地到各个销地1吨糖果的运价

已知:一家糖果公司有三个加工厂（A1，A2，A3），公司要把这三个工厂生产的糖果运往四个销售地区（B1，B2，B3，B4）。已知每个工厂的产量、每个销售地点的销量、各工厂到各销售地点1吨糖果的运价（单位运价）。3运输问题（TP）单位运价表产销平衡表单位：百元/t12CijB1B2B3B4A1311310A21928A374105XijB1B2B3B4产量A1x11x12x13x147A2x21x22x23x244A3x31x32x33x349销量3656A1A2A3B1B2B3B47t4t9t3t6t5t6t产地销地x11x12x34第i个产地第j个销地运输量Xij…3运输问题（TP）两个重要表格单位运价表单位：百元/tCijB1B2B3B4A1311310A21928A374105运输问题的数学模型MinZ=3x11+11x12+3x13+

10x14

+

x21+9x22+2x23+

8x24

+7x31+

4x32+10x33+

5x34总运费最少MinZ=∑cijxij目标函数XijB1B2B3B4产量A1x11x12x13x147A2x21x22x23x244A3x31x32x33x349销量3656产量约束产销平衡表销量约束XijB1B2B3B4产量A1x11x12x13x147A2x21x22x23x244A3x31x32x33x349销量3656产销平衡表XijB1B2B3B4产量A1x11x12x13x147A2x21x22x23x244A3x31x32x33x349销量3656+++=XijB1B2B3B4产量A1x11x12x13x147A2x21x22x23x244A3x31x32x33x349销量3656+++=+++=XijB1B2B3B4产量A1x11x12x13x147A2x21x22x23x244A3x31x32x33x349销量3656+++=+++=+++=XijB1B2B3B4产量A1x11x12x13x147A2x21x22x23x244A3x31x32x33x349销量3656++=XijB1B2B3B4产量A1x11x12x13x147A2x21x22x23x244A3x31x32x33x349销量3656++=++=XijB1B2B3B4产量A1x11x12x13x147A2x21x22x23x244A3x31x32x33x349销量3656++=++=++=XijB1B2B3B4产量A1x11x12x13x147A2x21x22x23x244A3x31x32x33x349销量3656++=++=++=++=Xij≥0Xij≥03运输问题（TP）133.1运输问题的模型有三家工厂，都将产品运往三个不同的商店（见下图）。每个工厂以产品件数表示出每周生产能力见下表1。每家商店平均需求量见下表2。工厂1工厂3工厂2商店1商店3商店2

商店123需求量（件/周）506030工厂123供应量（件/周）507020表1表2143.1运输问题的模型但是，由于运货距离不同，各个工厂运往各商店的货物的运输费用是不同的。费用如下表，我们的问题是确定由哪家工厂运送多少件产品到哪家商店。能否列出线性最优化模型？决策存在什么样的约束条件？模型评价涉及什么样的准则？有那些决策变量？由工厂每件产品运往各商店的费用（元）

12313232105831310153.1运输问题的模型1、模型建立决策变量—有待确定的是从每家工厂i（i=1，2，3）运输多少件产品到每家商店j（j=1，2，3）去。因此，方便的办法是用双下标来表示决策变量即Xij。目标函数—利用运输费用表中的数据，我们希望其值为最小的是：MinZ=由工厂1运出产品的总费用(3X11+2X12+3X13)

+由工厂2运出产品的总费用(10X21+5X22+8X23)

+由工厂3运出产品的总费用(X31+3X32+10X33)即：MinZ=3X11+2X12+3X13+10X21+5X22+8X23+X31+3X32+10X33约束条件—需要把决策变量的约束条件当作方案生成源。对工厂1必须有X11+X12+X13≤50

（对工厂1的供应约束）对工厂2必须有X21+X22+X23≤70

（对工厂2的供应约束）对工厂3必须有X31+X32+X33≤20

（对工厂3的供应约束）163.1运输问题的模型对每家商店来说，也需要一个逻辑关系式来说明每个星期运到的产品总数应等于每周的需求量。对商店1必须有X11+X21+X31=50

对商店2必须有X12+X22+X32=60

对商店3必须有X13+X23+X33=30

于是，用于解此问题的线性最优化模型是：

Xij≥0且为整数i=1，2，3;j=1，2，3173.1运输问题的模型运输问题模型分析一般形式：某种物资有m个产地Ai，产量（供应量）是ai（i=1，2，…，m），有n个销地Bj，销量（需求量）是bj（j=1，2，…，n）。从运到到的单位运价为cij（i=1，2，…，m；j=1，2，…，n），如何安排运输可使总运费最小？产大于销-

ai

≥bjMinZ=

CijXij

xij≤ai

（i=1，2，…，m）

xij=bj

（j=1，2，…，n）

xij≥0（i=1，2，…，m；

j=1，2，…，n）销大于产-

ai

≤bjMinZ=

CijXij

xij=ai

（i=1，2，…，m）

xij≤bj

（j=1，2，…，n）

xij≥0（i=1，2，…，m；

j=1，2，…，n）183.1运输问题的模型产销平衡-

ai=bj注意！这种模型具有特殊的形式：所有决策变量的约束条件，其系数均等于1；而且，每个决策变量仅出现于两个约束条件之中。这些特性表明，解这类线性最优化模型的单纯形法中有一种特殊的方法可用来解这个问题——这是解这类模型的特别有效的一种方法。而且上述特性还表明，可以给这类线性最优化模型以一种象网络模型式的形象化的说明。MinZ=

CijXij

xij=ai

（i=1，2，…，m）

xij=bj

（j=1，2，…，n）

xij≥0（i=1，2，…，m；j=1，2，…，n）jjii193.1运输问题的模型（2）产销不平衡问题——总产量小于总销量的运输问题例2—有三个化肥厂供应四个地区的农用化肥。等量化肥在这些地区使用效果相同。相关数据如下表，试分析总运费最节省的化肥调运方案。A1A2A3最低需求（万吨）最高需求（万吨）

B1B2B3B4