(运筹学课件运输问题-).ppt

《(运筹学课件运输问题-).ppt》由会员分享，可在线阅读，更多相关《(运筹学课件运输问题-).ppt（134页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第七章第七章 运输问题运输问题 赵 玮 7.1 7.1 运输模型运输模型 7.2 7.2 运输问题的计算机求解运输问题的计算机求解 7.3 7.3 运输问题的应用运输问题的应用 一、产销不平衡的运输问题一、产销不平衡的运输问题 二、生产与储存问题二、生产与储存问题 三、三、转运问题转运问题 7.4 7.4 运输问题的表上作业法运输问题的表上作业法 一、确定初始基本可行解一、确定初始基本可行解 二、最优解的判别二、最优解的判别 三、改进运输方案的办法三、改进运输方案的办法闭回路调整闭回路调整法法 四、如何找多个最优方案四、如何找多个最优方案 一般的运输问题就是要解决把某种产一般的运输问题就是要解

2、决把某种产品从若干个产地调运到若干个销地，在每品从若干个产地调运到若干个销地，在每个产地的供应量与每个销地的需求量已知，个产地的供应量与每个销地的需求量已知，并知道各地之间的运输单价的前提下，如并知道各地之间的运输单价的前提下，如何确定一个使得总的运输费用最小的方案。何确定一个使得总的运输费用最小的方案。 例例1. 1. 某公司从两个产地某公司从两个产地A A1 1,A,A2 2将物品运往将物品运往三个销地三个销地B B1 1，B B2 2，B B3 3, ,各产地的产量、各销地的各产地的产量、各销地的销量和各产地运往各销地的每件物品的运费如销量和各产地运往各销地的每件物品的运费如下表所示：下

3、表所示：问应如何调运，使得总运输费最小？问应如何调运，使得总运输费最小？ 解：我们知道解：我们知道A A1 1、A A2 2两个产地的总产量为：两个产地的总产量为：200 + 300 = 500200 + 300 = 500（件）；（件）；B B1 1，B B2 2，B B3 3三个销地三个销地的总销量为：的总销量为：150+150+200=500150+150+200=500（件）（件）, ,总产量总产量等于总销量这是一个产销平衡的运输问题。把等于总销量这是一个产销平衡的运输问题。把 A A1 1，A A2 2 的产量全部分配给的产量全部分配给B B1 1，B B2 2，B B3 3，正好正

4、好满足这三个销地的需要。满足这三个销地的需要。 设设x xijij表示从产地表示从产地A Ai i调运到调运到B Bj j的运输量（的运输量（i = i = 1 1，2 2；j = 1j = 1，2 2，3 3），），例如，例如，x x1212表示从表示从A A1 1调运调运到到B B2 2的物品数量，现将安排的运输量列表如下的物品数量，现将安排的运输量列表如下： 从上表可写出此问题的数学模型。从上表可写出此问题的数学模型。 满足产地产量的约束条件为：满足产地产量的约束条件为： x x11 11 + x+ x12 12 + x+ x1313 = 200 = 200， x x21 21 + x+

5、 x2222 + x + x2323 = 300. = 300. 满足销地销量的约束条件为：满足销地销量的约束条件为： x x1111 + x + x2121 = 200 = 200， x x1212 + x + x2222 = 300 = 300， x x1313 + x + x2323 = 200. = 200.所以此运输问题的线性规划的模型如下：所以此运输问题的线性规划的模型如下： 目标函数：目标函数： minf=6xminf=6x1111+4x+4x1212+6x+6x1313+6x+6x2121+5x+5x2222+5x+5x2323约束条件：约束条件： x x11 11 + x+

6、x12 12 + x+ x1313 = 200 = 200， x x2121 + x + x22 22 + x+ x2323 = 300 = 300， x x1111 + x + x2121 = 150 = 150， x x1212 + x + x2222 = 150 = 150， x x1313 + x + x2323 = 200. = 200. x xijij0. (i = 10. (i = 1，2 2；j = 1j = 1，2 2，3)3) 为了给出一般运输问题的线性规划的模为了给出一般运输问题的线性规划的模型，我们将使用以下的一些符号：型，我们将使用以下的一些符号： A A1 1，A

7、A2 2，A Am m表示某种物资的表示某种物资的m m个产地；个产地； B B1 1，B B2 2，B Bn n表示某种物资的表示某种物资的n n个销地；个销地； s si i表示产地表示产地A Ai i的产量；的产量； d dj j表示销地表示销地B Bj j的销量；的销量； c cijij表示把物资从产地表示把物资从产地A Ai i运到销地运到销地B Bj j的单的单位运价。位运价。 同样设同样设x xijij表示从产地表示从产地A Ai i运到销地运到销地B Bj j的的运输量，则产销平衡的运输问题的线性规运输量，则产销平衡的运输问题的线性规划模型如下所示：划模型如下所示： 目标函数：

8、目标函数：i ij jn n1 1j ji ij jm m1 1i ix xc cm mi in nf f 约束条件：约束条件：n，2 21 1，j jd dx xj jm m1 1i ii ij jX Xijij0 0，对所有的对所有的i i和和j.j.m， 2 21 1，i is sx xi in n1 1j ji ij j 有时上述的运输问题的一般模型会发有时上述的运输问题的一般模型会发生一些如下变化：生一些如下变化： 1. 1.求目标函数的最大值而不是最小值求目标函数的最大值而不是最小值有些运输问题中，它的目标是要找出利润有些运输问题中，它的目标是要找出利润最大或营业额最大的调运方案，

9、这时要求最大或营业额最大的调运方案，这时要求目标函数的最大值了。目标函数的最大值了。 2. 2.当某些运输线路的运输能力有一定限当某些运输线路的运输能力有一定限制时，这时要在线性规划的模型的约束条件制时，这时要在线性规划的模型的约束条件上要加上运输能力限制的约束条件。例如从上要加上运输能力限制的约束条件。例如从 A A3 3 运到运到 B B4 4的物品的数量受到运输能力的限的物品的数量受到运输能力的限制，最多运送制，最多运送10001000单位，这时只要在原来的单位，这时只要在原来的模型上加上约束条件模型上加上约束条件x x34341000 1000 即可。即可。 3 3.当生产总量不等于销

10、售总量，即当生产总量不等于销售总量，即产销不平衡时，这时将通过增加一个假产销不平衡时，这时将通过增加一个假想仓库或假想生产地来化成产销平衡的想仓库或假想生产地来化成产销平衡的问题，具体做法将在下面阐述。问题，具体做法将在下面阐述。 在上一节中我们讨论的是产销平衡的在上一节中我们讨论的是产销平衡的运输问题，对于产销不平衡的运输问题，运输问题，对于产销不平衡的运输问题，我们可以先化为产销平衡的运输问题然后我们可以先化为产销平衡的运输问题然后再求解。再求解。 例例2 2某公司从两个产地某公司从两个产地 A A1 1，A A2 2 将物将物品运往三个销地品运往三个销地 B B1 1，B B2 2，B

11、B3 3，各产地产量各产地产量和各销地销量以及各产地运往各销地的每和各销地销量以及各产地运往各销地的每件物品的运输费列表如下：件物品的运输费列表如下： 应如何组织运输，使总运输费用为最小？应如何组织运输，使总运输费用为最小？ 例例2 2的产销平衡表的产销平衡表 例例3 3某公司从两个产地某公司从两个产地A A1 1，A A2 2将物品运往三将物品运往三个销地个销地B B1 1，B B2 2，B B3 3，各销地的销量以及从产地到各销地的销量以及从产地到销地的每件物品的运输单价列表如下：销地的每件物品的运输单价列表如下： 主要内容：主要内容： 一、一、产销不平衡的运输问题产销不平衡的运输问题 二

12、、二、生产与储存问题生产与储存问题 三、三、转运问题转运问题 例例4 4石家庄北方研究院有三个区，即石家庄北方研究院有三个区，即一区、二区、三区，每年分别需要生活用一区、二区、三区，每年分别需要生活用煤和取暖用煤煤和取暖用煤30003000、10001000、20002000吨，由河吨，由河北临城，山西盂县两处煤矿负责供应，这北临城，山西盂县两处煤矿负责供应，这两处煤矿的价格相同，煤的质量也基本相两处煤矿的价格相同，煤的质量也基本相同，两处煤矿能供应北方研究院的单位运同，两处煤矿能供应北方研究院的单位运价（百元价（百元/ /吨）见下表：吨）见下表： 由于需大于供，经院研究平衡决定由于需大于供，

13、经院研究平衡决定一区供应量可减少区供应量可减少0 0200200吨，二区需要量应吨，二区需要量应全部满足，三区供应量不少于全部满足，三区供应量不少于17001700吨。试吨。试求总运费为最低的调运方案。求总运费为最低的调运方案。 运价运价 百元百元/ /吨吨 解：根据题意，作出产销平衡与运价表如下：解：根据题意，作出产销平衡与运价表如下： 例例5 5设有三个化肥厂供应四个地区设有三个化肥厂供应四个地区 的农用化肥。假定等量的化肥在这些地的农用化肥。假定等量的化肥在这些地区使用效果相同。各化肥厂年产量、各区使用效果相同。各化肥厂年产量、各地区年需求量及从各化肥厂到各地区运地区年需求量及从各化肥厂

14、到各地区运送单位化肥的运价如下表，试求出总的送单位化肥的运价如下表，试求出总的运费最节省的化肥调拨方案。运费最节省的化肥调拨方案。 输入输入“管理运筹学软件管理运筹学软件”即可得到最优调即可得到最优调运方案如下（注：表中的运方案如下（注：表中的M M我们只要输入一个足我们只要输入一个足够大的正数如够大的正数如10 00010 000即可）即可）最小总运费为最小总运费为2 4602 460万元。万元。 例例6. 6. 某厂按合同规定须于当年每个某厂按合同规定须于当年每个季度末分别提供季度末分别提供1010，1515，2525，2020台同一规台同一规格的柴油机。已知该厂各季度的生产能力格的柴油机

15、。已知该厂各季度的生产能力及生产每台柴油机的成本如下表所示，又及生产每台柴油机的成本如下表所示，又如果生产出来的柴油机当季不交货，每台如果生产出来的柴油机当季不交货，每台每积压一个季度需储存、维护等费用每积压一个季度需储存、维护等费用0.150.15万元。要求在完成合同的情况下，做出使万元。要求在完成合同的情况下，做出使该厂全年生产（包括储存、维护）费用最该厂全年生产（包括储存、维护）费用最小的决策。小的决策。 解：由于每个季度生产出来的柴油机解：由于每个季度生产出来的柴油机不一定当月交货，故设不一定当月交货，故设x xijij为第为第i i季度生产季度生产的第的第j j季度交货的柴油机的数目

16、。季度交货的柴油机的数目。由合同规定，各季度交货数必须满足：由合同规定，各季度交货数必须满足：x x1111 = 10, = 10,x x1212 + x + x2222 = 15, = 15,x x1313 + x + x2323 + x + x3333 = 15, = 15,x x1414 + x + x2424 + x + x3434 + x + x4444 = 20 = 20又各季生产的柴油机数目都不能超过各又各季生产的柴油机数目都不能超过各季度的生产能力，故又有季度的生产能力，故又有x x1111 + x + x1212 + x + x1313 + x + x141425,25,x

17、x2222 + x + x2323 + x + x2424 15,15,x x3333 + x + x3434 30,30,x x4444 10.10. 设设c cijij是第是第i i季度生产的第季度生产的第j j季度交货的每季度交货的每台柴油机的实际成本，台柴油机的实际成本，c cijij应该是该季度单位应该是该季度单位成本加上储存、维护等费用成本加上储存、维护等费用c cijij值看下表。值看下表。 这样此问题的目标函数可写成：这样此问题的目标函数可写成： minf=10.8 xminf=10.8 x1111+10.95x+10.95x1212+11.10 x+11.10 x1313+

18、+ 11.25x 11.25x1414+11.10 x+11.10 x2222+11.25x+11.25x2323+ + 11.40 x 11.40 x2424+11.00 x+11.00 x3333+11.15x+11.15x3434+ + 11.30 x 11.30 x4444 我们把目标函数和以上的约束条件以及我们把目标函数和以上的约束条件以及x xijij非负限制放在一起就建立此问题的线性规划的非负限制放在一起就建立此问题的线性规划的模型。把它输入管理运筹学软件，我们就可以模型。把它输入管理运筹学软件，我们就可以得到结果。得到结果。 如果我们写出此问题的产销平衡与运如果我们写出此问题的

19、产销平衡与运价表并输入运输问题的软件。我们也可以价表并输入运输问题的软件。我们也可以立即得到结果。这时由于产大于销，我们立即得到结果。这时由于产大于销，我们可以加上一个假想的需求可以加上一个假想的需求D D（实际上，不实际上，不加这个假想需求加这个假想需求D,D,此软件也能自动平衡产此软件也能自动平衡产销，求解），并注意到当销，求解），并注意到当i ij j时，时，x xijij=0=0，所以应令对应的所以应令对应的c cij ij = M= M。产销平衡与运产销平衡与运价表如下：价表如下： 在输入数据时，关于在输入数据时，关于M M我们可以选择相我们可以选择相对表中的价格足够大的正数如对表中

20、的价格足够大的正数如1 0001 000既可，既可，从计算机输出我们得到最优解如下所示从计算机输出我们得到最优解如下所示, ,其其最优解为最优解为773773万元。万元。 例例7 7光明仪器厂生产电脑绣花机是以销定产光明仪器厂生产电脑绣花机是以销定产的。已知的。已知1 1至至6 6月份各月的生产能力、合同销量和单月份各月的生产能力、合同销量和单台电脑绣花机平均生产费用见下表。又已知上年末台电脑绣花机平均生产费用见下表。又已知上年末库存库存103103台绣花机台绣花机, ,又如果当月生产出来的机器当月又如果当月生产出来的机器当月不交货，则需要运到分厂库房，每台增加运输成本不交货，则需要运到分厂库

21、房，每台增加运输成本0.10.1万元，每台机器每月的平均仓储费、维护费为万元，每台机器每月的平均仓储费、维护费为0.20.2万元，在万元，在 7 78 8月份销售淡季，全厂停产月份销售淡季，全厂停产1 1个月，个月，因此在因此在6 6月份完成销售合同后还要留出库存月份完成销售合同后还要留出库存 80 80台。台。加班生产机器每台增加成本加班生产机器每台增加成本1 1万元。问应如何安排万元。问应如何安排1 16 6月份的生产使总的生产月份的生产使总的生产( (包括运输、仓储、维包括运输、仓储、维护）费用最少？护）费用最少？月份月份正常生产正常生产能力能力（台）（台）加班生产加班生产能力能力（台）

22、（台）销量销量（台）（台）单台费用单台费用（万元）（万元）16010104152501075143902011513.54100401601351004010313680407013.5 解：这是一个生产储存问题，可以解：这是一个生产储存问题，可以化为运输问题来做。根据已知条件可列出化为运输问题来做。根据已知条件可列出产销平衡与运价表，制定此表主要考虑如产销平衡与运价表，制定此表主要考虑如下条件：下条件： 1 11 1至至6 6月份合计生产能力（包括上月份合计生产能力（包括上年末储存量）为年末储存量）为743743台，销量为台，销量为707707台，产台，产大于销大于销3636台，所以在销地栏

23、中设一个假想台，所以在销地栏中设一个假想销地（仓库），其销量实为不安排生产的销地（仓库），其销量实为不安排生产的剩余生产能力。剩余生产能力。 2 2上年末库存上年末库存103103台，只有仓储费台，只有仓储费和运输费我们把它列在序号和运输费我们把它列在序号0 0行里。行里。 3 36 6月份的需求除了月份的需求除了7070台销量外还台销量外还要要8080台库存，其需求应为台库存，其需求应为80+70=15080+70=150台。台。 4 4产销平衡与运价表中产销平衡与运价表中, ,生产时间生产时间中的序号中的序号1 16 6表示表示1 16 6月份正常生产情月份正常生产情况，序号况，序号116

24、6表示表示1 16 6月份加班生月份加班生产情况。产情况。 用用“管理运筹学软件管理运筹学软件”解得结果是解得结果是1 1至至6 6月份最低总生产（包括运输、仓月份最低总生产（包括运输、仓储、维护）费用为储、维护）费用为8307.58307.5万元，每月万元，每月的生产销售安排见下表。的生产销售安排见下表。 销售月销售月 单价单价生产月生产月1 1月月2 2月月3 3月月4 4月月5 5月月6 6月月假假想想产产地地产量产量正正常常加加班班00.30.50.70.91.11.3010311515.315.515.715.916.1060 11616.316.516.716.917.10102M

25、1414.314.514.714.90502M1515.315.515.715.9010 产销平衡与运价表产销平衡与运价表 3MM13.513.814.014.0090 3MM14.514.815.015.20204MMM1313.313.50100 4MMM1414.314.50405MMMM1313.30100 5MMMM1414.30406MMMMM13.5080 6MMMMM14.5040销量销量1047511516010315036 743 743 销售月销售月运输量运输量生产月生产月1 1月月2 2月月3 3月月4 4月月5 5月月6 6月月假想假想销售销售063155201411

26、9110250 210 最优生产销售安排最优生产销售安排 390 320 4100 440 56337 540 680 6337 所谓的转运问题是运输问题的一个所谓的转运问题是运输问题的一个扩充，在原来的运输问题中的产地（也扩充，在原来的运输问题中的产地（也称发点）、销地（也称收点）之外还增称发点）、销地（也称收点）之外还增加了中转点。加了中转点。 在运输问题中我们只允许物品从发在运输问题中我们只允许物品从发点运往收点，而在转运问题中我们还允点运往收点，而在转运问题中我们还允许把物品从一个发点运往另一个发点或许把物品从一个发点运往另一个发点或中转点或收点，也允许把物品从一个中中转点或收点，也允

27、许把物品从一个中转点运往另一个中转点或发点或收点，转点运往另一个中转点或发点或收点，也允许把物品从一个收点运往另一个收也允许把物品从一个收点运往另一个收点或中转点或发点。点或中转点或发点。在每一个发点的供应量限定，每一在每一个发点的供应量限定，每一个收点的需求一定，每两个点之间的运个收点的需求一定，每两个点之间的运输单价已知的条件下如何进行调运使得输单价已知的条件下如何进行调运使得总的运输费用最小。总的运输费用最小。 例例8 8腾飞电子仪器公司在大连和广州腾飞电子仪器公司在大连和广州有两个分厂有两个分厂, ,大连分厂每月生产大连分厂每月生产400400台某种台某种仪器，广州分厂每月生产仪器，广

28、州分厂每月生产600600台某种仪器。台某种仪器。该公司在上海与天津有两个销售公司负责该公司在上海与天津有两个销售公司负责对南京、济南、南昌与青岛四个城市的仪对南京、济南、南昌与青岛四个城市的仪器供应，又因为大连与青岛相距较近，公器供应，又因为大连与青岛相距较近，公司也同意大连分厂直接向青岛供货，这些司也同意大连分厂直接向青岛供货，这些城市间的每台仪器的运输费用我们标在两城市间的每台仪器的运输费用我们标在两个城市间的弧上，单位为百元，问应该如个城市间的弧上，单位为百元，问应该如何调运仪器，使得总的运输费最低。何调运仪器，使得总的运输费最低。 解：如图解：如图7-17-1所示，我们用所示，我们用

29、 1 1代表代表在广州；在广州；2 2代表大连；代表大连；3 3代表上海；代表上海；4 4代代表天津；表天津；5 5代表南京；代表南京；6 6代表济南；代表济南；7 7代代表南昌；表南昌；8 8代表青岛。代表青岛。 设设x xijij表示从表示从i i到到j j的调运量，如的调运量，如x x3636表示从上海运到济南的仪器台数。表示从上海运到济南的仪器台数。 x13 + x14600,x23 + x24600,-x13 - x23 + x35 + x36 + x37 + x38 = 0,-x14 - x24 + x45 + x46 + x47 + x48 = 0,x35 + x45 = 200

30、,x36 + x46 = 150,X37 + x47= 350,x28 + x38 + x48 = 300,xij0,对所有的对所有的i、j.约束条件：约束条件：目标函数：目标函数： minf= minf= 2x13+3x14 +3x23+ x24 +2x35+6x36+3x37 + 6x38+4x45 +4x46+6x47+5x48+4x28 用用“管理运筹学管理运筹学”软件求解得到结软件求解得到结果如下：果如下： x x1313=550,x=550,x1414=0, x=0, x2323=0, x=0, x2424=150,=150, x x3535=200,x=200,x3636=0,

31、x=0, x3737=350,x=350,x3838=0,=0, x x4545=0,x=0,x4646=150, x=150, x4747=0, x=0, x4848=0,=0, x x2828=300.=300. 最小的运输费用为最小的运输费用为45004500百元。百元。对于转运问题的一般线性规划的模型如下：对于转运问题的一般线性规划的模型如下：目标函数：目标函数：ijijmin c x .对所有的弧ijijixxs所有流出量所有流入量 ，ijijxx0所有流出量所有流入量 ，ijijjjxxd所有流出量所有流入量 ，约束条件：约束条件：对于中转点有对于中转点有对于收点对于收点j j有有

32、 对发点对发点i i有有ijcisjd其中：其中： 为从为从i i点运到点运到j j点的单位运价，点的单位运价， 为发点为发点i i的供应量，的供应量， 为收点为收点j j的需求量。的需求量。 我们也可以用产销平衡与运价表使我们也可以用产销平衡与运价表使用管理运筹学软件的运输问题来解决转用管理运筹学软件的运输问题来解决转运问题。运问题。 例例9 9某公司有三个分厂生产某种某公司有三个分厂生产某种物资，分别运往四个地区的销售公司去物资，分别运往四个地区的销售公司去销售。有关分厂的产量，各销售公司的销售。有关分厂的产量，各销售公司的销量及运价见表所列，要求总的运费最销量及运价见表所列，要求总的运费

33、最少的调运方案少的调运方案。 销地销地运输单价运输单价产地产地B1B2B3B4产量产量A13113107A219284A3741059销量销量3656 2020 这是一个普通的产销平衡问题，但这是一个普通的产销平衡问题，但是如果假定：是如果假定： 1. 1. 每个分厂的物资不一定直接发每个分厂的物资不一定直接发运到销地，可以从其中几个产地击中一运到销地，可以从其中几个产地击中一起运。起运。 2. 2. 运往各销地的物资可以先运给运往各销地的物资可以先运给其中几个销地，再转运给其他销地。其中几个销地，再转运给其他销地。 3. 3. 除产销之外除产销之外, , 还有几个中转站，还有几个中转站，在产

34、地之间、销地之间或产地与销地之在产地之间、销地之间或产地与销地之间转运。间转运。 已知各产地、销地、中转站及相互之已知各产地、销地、中转站及相互之间每吨物资的运价见表，问在考虑产销之间每吨物资的运价见表，问在考虑产销之间直接运输和非直接运输的各种可能方案间直接运输和非直接运输的各种可能方案的情况下，如何将三个分厂生产的物资运的情况下，如何将三个分厂生产的物资运往销售公司，才使总的运费最少。往销售公司，才使总的运费最少。产地产地中转站中转站销地销地A1 A2 A3T1 T2 T3 T4B1 B2 B3 B4产产地地A1A2A3 1 3 1 3 2 1 4 3 3 5 2 1 2 3 3 11 3

35、 10 1 9 2 8 7 4 10 5中中转转站站T1T2T3T4 2 3 1 1 5 4 2 3 2 3 1 3 2 1 1 1 3 1 2 2 1 2 3 11 3 10 4 5 2 7 1 8 2 4 1 2 6销销地地B1B2B3B4 3 1 711 9 4 3 2 1010 8 5 2 4 1 1 8 5 8 4 2 2 2 6 7 4 6 1 4 2 1 2 1 4 2 3 2 1 3 从上表可以看出，从从上表可以看出，从A A1 1到到B B2 2直接运直接运费单价为费单价为1111元，单从元，单从A A1 1经经A A3 3到到B B2 2，运价运价仅为仅为3 34=74=7

36、元。从元。从A A1 1经经T T2 2到到B B2 2只需只需1 15=65=6元；从元；从A A1 1到到B B2 2的最佳途径为的最佳途径为A A1 1AA2 2BB1 1BB2 2，运价只是运价只是1 11 11=31=3元，元，可见转运问题比一般运输问题复杂。可见转运问题比一般运输问题复杂。 现在我们把此转运问题化成一般运现在我们把此转运问题化成一般运输问题，要做如下处理：输问题，要做如下处理： 1. 1. 由于问题中的所有产地、中转站、由于问题中的所有产地、中转站、销地都可以看成产地，也可以看成销地，销地都可以看成产地，也可以看成销地，因此整个问题可以看成一个有因此整个问题可以看成

37、一个有1111个产地个产地 有有1111个销地的扩大的运输问题。个销地的扩大的运输问题。 2. 2. 对扩大了的运输问题建立运价表，对扩大了的运输问题建立运价表，将表中不可能的运输方案用任意大的整将表中不可能的运输方案用任意大的整 数数M M代替。代替。 3. 3. 所有中转站的产量等于销量也即所有中转站的产量等于销量也即流入量等于流出量。由于运费最少时不流入量等于流出量。由于运费最少时不可能出现一批物资来回倒运的现象，所可能出现一批物资来回倒运的现象，所以每个中转站的转运量不会超过以每个中转站的转运量不会超过2020吨，吨，可以规定可以规定T T1 1 ，T T2 2 ，T T3 3 ，T

38、T4 4 的产量和的产量和销量均为销量均为2020吨。由于实际的转运量吨。由于实际的转运量nmijiijjj 1i 1xsxd .， 这里这里s si i表示表示i i点的流出量，点的流出量，d dj j表示表示j j点点的流出量，对中转点来说，按上面规定的流出量，对中转点来说，按上面规定s si i=d=dj j=20=20。 这样可以在每个约束条件中增加一这样可以在每个约束条件中增加一个松弛变量个松弛变量x xiiii，x xiiii相当于虚构的中转站，相当于虚构的中转站，其意义就是自己运给自己。其意义就是自己运给自己。(20-(20-x xiiii) )就是就是每个中转站的实际转运量，每

39、个中转站的实际转运量，x xiiii的对应运的对应运价价c ciiii=0.=0. 4 4扩大了的运输问题中原来的产扩大了的运输问题中原来的产地与销地由于也具有转运作用，所以同地与销地由于也具有转运作用，所以同样在原来的产量与销量的数字上加上样在原来的产量与销量的数字上加上2020吨，即三个分厂的产量改为吨，即三个分厂的产量改为2727、2424、2929吨，销量均为吨，销量均为2020吨，四个销地的每天销吨，四个销地的每天销量改为量改为2323，2626，2525，2626吨，产量均为吨，产量均为2020吨，同时引进吨，同时引进x xiiii为松弛变量。下面写出为松弛变量。下面写出扩大了的运

40、输问题产销平衡与运价表。扩大了的运输问题产销平衡与运价表。 销地销地产地产地A1A2A3T1T2T3T4B1B2B3B4产量产量A101310M3M023115M4M2323317119432101085272429A2A3T1214335M21M2301321011310221202411858M4222674620202020T2T3T4B13113101928741052846452718241M26014210214203213020202020B2B3B4销量销量2020202020202023262526 240240 销地销地调运量调运量产地产地A1A2A3T1T2T3T4B1B

41、2B3B4产量产量A120727A2136524A3203629T117320T22020 用管理运筹学软件进行计算，得到如下用管理运筹学软件进行计算，得到如下结果，其最小运输费为结果，其最小运输费为6868元，最优解如下：元，最优解如下：T32020T42020B11420B22020B32020B42020销量销量2020202020202023262526 240240 从上表可知从上表可知A A1 1把把7 7吨产量先运到吨产量先运到A A2 2，然然后与后与A A2 2的的4 4吨产量一共有吨产量一共有1111吨，其中吨，其中6 6吨运吨运给给B B1 1，5 5吨运给吨运给B B3

42、 3；A A3 3 把把3 3吨通过中转吨通过中转T T1 1 运运给了给了B B1 1，6 6吨直接运给了吨直接运给了B B2 2，这样这样B B1 1一共收一共收到了到了9 9吨，其多余的吨，其多余的6 6吨转运给吨转运给B B4 4，这是最这是最佳运输方案，总运费只有佳运输方案，总运费只有6868元。元。 表上作业法是一种求解运输问题的特表上作业法是一种求解运输问题的特殊的方法，其实质是单纯形法，它针对运殊的方法，其实质是单纯形法，它针对运输问题变量多（如对有输问题变量多（如对有2020个产地个产地3030个销地个销地的运输问题就有的运输问题就有20203030600600个变量）个变量

43、）, ,结结构独特的情况，大大简化了计算过程的求构独特的情况，大大简化了计算过程的求解方法，它的计算过程如下：解方法，它的计算过程如下： 这里假设所有的运输问题都是产销平这里假设所有的运输问题都是产销平衡的，至于产销不平衡的运输问题可以先衡的，至于产销不平衡的运输问题可以先化为产销平衡的问题，再求解。化为产销平衡的问题，再求解。将产销不平衡调整将产销不平衡调整为产销平衡为产销平衡给出运输问题的有关给出运输问题的有关产、销、运价信息产、销、运价信息是 否 产 销 平是 否 产 销 平衡衡确定初始调运方案确定初始调运方案是否最优方是否最优方案案调整运输方案调整运输方案输出，结束输出，结束确定初始基

44、确定初始基本可行解本可行解计算各非基计算各非基变量检验数变量检验数确定入基变量确定入基变量与出基变量与出基变量N NN NY YY Y 表上作业法求解流程图表上作业法求解流程图 对于有对于有m m个产地个产地n n个销地的产销平衡的个销地的产销平衡的问题，从其线性规划的模型上可知在它的问题，从其线性规划的模型上可知在它的约束条件中有约束条件中有m m个关于产量的约束方程和个关于产量的约束方程和n n个关于销量的约束方程共有个关于销量的约束方程共有 m+nm+n个约束方个约束方程，但由于产销平衡程，但由于产销平衡, ,前前m m个约束方程之和个约束方程之和等于后等于后n n个约束方程之和个约束方

45、程之和, ,所以其模型最多所以其模型最多只有只有m+n-1m+n-1个独立的约束方程。个独立的约束方程。 实际上其正好是实际上其正好是 m+n-1m+n-1个独立的约个独立的约束方程，也就是说其系数矩阵的秩为束方程，也就是说其系数矩阵的秩为m+n-1m+n-1，即运输问题有即运输问题有 m+n-1m+n-1个基变量，个基变量，找出初始基本可行解，就是在（找出初始基本可行解，就是在（m mn n）产销平衡表上给出产销平衡表上给出 m+n-1m+n-1个数字格，其个数字格，其相应的调运量就是基变量，格子中所填相应的调运量就是基变量，格子中所填写的值即为基变量的值。写的值即为基变量的值。 2. 求各

46、非基变量的检验数，即在表上求各非基变量的检验数，即在表上计算除了上述的计算除了上述的m+n-1m+n-1个数字格以外的空格个数字格以外的空格的检验数判别是否达到最优解的检验数判别是否达到最优解,如已是最优如已是最优解，则停止计算解，则停止计算,否则转到下一步。在运输否则转到下一步。在运输问题中都存在最优解。问题中都存在最优解。 3. 确定入基变量与出基变量，找出新确定入基变量与出基变量，找出新的基本可行解。在表上用闭回路法调整。的基本可行解。在表上用闭回路法调整。 4. 重复重复2、3直至得到最优解。直至得到最优解。 以上运算都可以在表上完成，下面通以上运算都可以在表上完成，下面通过例子来说明

47、表上作业法计算步骤。过例子来说明表上作业法计算步骤。 例例1010喜庆食品公司有三个生产面包喜庆食品公司有三个生产面包的分厂的分厂A A1 1，A A2 2，A A3 3，有四个销售公司有四个销售公司B B1 1，B B2 2，B B3 3，B B4 4，其各分厂每日的产量、各销其各分厂每日的产量、各销售公司每日的销量以及各分厂到各销售公售公司每日的销量以及各分厂到各销售公司的单位运价如表所示，在表中产量与销司的单位运价如表所示，在表中产量与销量的单位为吨，运价的单位为百元量的单位为吨，运价的单位为百元/ /吨。吨。问该公司应如何调运产品在满足各销点需问该公司应如何调运产品在满足各销点需求量的

48、前提下，总运费最少？求量的前提下，总运费最少？ 销地销地 运价运价产地产地 B1 B2 B3 B4产量产量A1A2A33 11 3 101 9 2 87 4 10 5749销量销量 3 6 5 6 20 20 我们用表上作业法来解此题，这是我们用表上作业法来解此题，这是一个产销平衡的运输问题，上面的产销一个产销平衡的运输问题，上面的产销情况和运价表已经是产销平衡和运价表情况和运价表已经是产销平衡和运价表了，不需要再设假想产地和销地了。了，不需要再设假想产地和销地了。 一、确定初始基本可行解一、确定初始基本可行解 二、最优解的判别二、最优解的判别 三、改进运输方案的办法三、改进运输方案的办法闭回

49、闭回路调整法路调整法 四、如何找多个最优方案四、如何找多个最优方案 我们在产销平衡与运价表上找出初我们在产销平衡与运价表上找出初始基本可行解，为了把初始基本可行解始基本可行解，为了把初始基本可行解与运价区分开，我们把运价放在每一栏与运价区分开，我们把运价放在每一栏的右上角，每一栏的中间写上初始基本的右上角，每一栏的中间写上初始基本可行解（调运量）见表。可行解（调运量）见表。 si，i1m输入输入 dj，j1n ij1xijmin（si，dj）sisixijdjdjxijdj0将将Bj列划去列划去si0将将Ai行划去行划去jj1ii1imEND输出输出xij，i1m，j1nNYNNYY西西北北角

50、角法法求求解解流流程程图图 先从表的左上角（即西北角）的变先从表的左上角（即西北角）的变量量x x1111开始分配运输量，并使开始分配运输量，并使x x1111取尽可能取尽可能大的值，这里发点大的值，这里发点A A1 1的产量为的产量为7 7，B B1 1的销的销量为量为3 3，x x1111只能取只能取3 3，即，即 x x1111=min(7,3)=3.=min(7,3)=3. 销地销地产地产地B1B2B3B4产量产量A1 3 11 3 107 4 0A2 1 9 2 84 2 0A3 7 4 10 59 6 0销量销量2062052060326432 由于由于x x1111为为3 3，所