7第七章运输问题

《7第七章运输问题》由会员分享，可在线阅读，更多相关《7第七章运输问题（78页珍藏版）》请在装配图网上搜索。

1、管理运筹学第七章第七章 运输问题运输问题运输模型运输问题的计算机求解运输问题的应用运输问题的表上作业法本章内容本章内容1234 1运 输 模 型例 1.某公司从两个产地 A1、A2 将物品运往三个销地 B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地的每件物品的运费如表所示，问：应如何调运可使总运输费用最小？销地 运费单价/元产地B1B2B3产量/件A1646200A2655300销量/件150150200 1运运 输输 模模 型型 解：产销平衡问题：总产量=总销量设 xij 为从产地 Ai 运往销地 Bj 的运输量，得到运输量表 销地 运输量产地B1B2B3产量/件A1x11x

2、12x13200A2x21x22x23300销量/件150150200500 1运运 输输 模模 型型 min f=6x11+4x12+6x13+6x21+5x22+5x23 s.t.x11+x12+x13=200 （产地A1）x21+x22+x23=300 （产地A2）x11+x21=150 （销地B1）x12+x22=150 （销地B2）x13+x23=200 （销地B3）xij 0 (i=1、2；j=1、2、3）1运运 输输 模模 型型 一般运输问题的线性规划模型：产销平衡 A1、A2、Am 表示某物资的 m 个产地；B1、B2、Bn 表示某物资的 n 个销地；si 表示产地Ai 的产量

3、；dj 表示销地 Bj 的销量；cij 表示把物资从产地 Ai 运往销地 Bj 的单位运价。1运运 输输 模模 型型 设 xij 为从产地 Ai 运往销地 Bj 的运输量，则一般运输问题模型：1111mins.t.1,2,1,2,1,2,;1,2,mnijijijnijijmijjiijfc xxsimxdjnxim jn,01111mins.t.1,2,1,2,1,2,;1,2,mnijijijnijijmijjiijfc xxsimxdjnxim jn,01111mins.t.1,2,1,2,1,2,;1,2,mnijijijnijijmijjiijfc xxsimxdjnxim jn,0

4、1111mins.t.1,2,1,2,1,2,;1,2,mnijijijnijijmijjiijfc xxsimxdjnxim jn,0(产地Ai)(销地Bj)1运运 输输 模模 型型变化：（1）求目标函数最大：利润最大或营业额最大。（2）运输线路上有能力限制时，模型中加入约束条件（等式或不等式约束)。（3）产销不平衡时，加入假想的产地（销大于产）或假想销地（产大于销）。运输模型运输问题的计算机求解运输问题的应用运输问题的表上作业法本章内容本章内容2341 2运输问题的计算机求解运输问题的计算机求解例 2.某公司从两个产地 A1、A2 将物品运往三个销地 B1、B2、B3，各产地的产量、各销地

5、的销量和各产地运往各销地每件物品的运费如表所示，问：应如何调运可使总运输费用最小？销地 运费单价/元产地B1B2B3产量/件A1646300A2655300销量/件150150200 600500 2运输问题的计算机求解运输问题的计算机求解解：销地 运费单价/元产地B1B2B3产量/件A1646300A2655300销量/件150150200 60000100B4600500产销平衡产销平衡运输费用？运输费用？增加一个虚设的销地B4，即增加一个仓库进行货物存储增加一个虚设的销地B4 2运输问题的计算机求解运输问题的计算机求解 数据输入“管理运筹学”软件 2运输问题的计算机求解运输问题的计算机求

6、解由软件得，最优解为：X11=50,X12=150,X13=0,X14=100,X21=100,X22=0,X23=200,X24=0.min f=2500.2运输问题的计算机求解运输问题的计算机求解例 3.某公司从两个产地 A1、A2 将物品运往三个销地 B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如表所示，问：应如何调运可使总运输费用最小？销地 运费单价/元产地B1B2B3产量/件A1646200A2655300销量/件250200200 500650 2运输问题的计算机求解运输问题的计算机求解解：销地 运费单价/元产地B1B2B3产量/件A1646200A

7、2655300销量/件250200200 650增加一个虚设的产地A3 500 6500150A300产销平衡产销平衡运输费用？运输费用？增加一个虚设的产地A3，即缺货 2运输问题的计算机求解运输问题的计算机求解 数据输入“管理运筹学”软件 2运输问题的计算机求解运输问题的计算机求解由软件得，最优解为：X11=0,X12=200,X13=0,X21=100,X22=0,X23=200,X31=150,X32=0,X33=0.min f=2400.运输模型运输问题的计算机求解运输问题的应用运输问题的表上作业法本章内容本章内容3412 3运输问题的应用运输问题的应用例 4.石家庄北方研究院有三个区

8、，即一区，二区，三区，每年分别需要用煤 3 000 t、1 000 t、2 000 t，由河北临城、山西盂县两处煤矿负责供应，价格、质量相同。供应能力分别为 1 500 t、4 000 t，运价如表所示。销地 运费单价产地一区二区三区山西盂县1.801.701.55河北临城1.601.501.75一、产销不平衡的运输问题 单位/(百元/t)3运输问题的应用运输问题的应用 由于需大于供，经院研究决定一区供应量可减少 0-300 t，二区必须满足需求量，三区供应量不少于 1 500 t，试求总费用为最低的调运方案。3运输问题的应用运输问题的应用解：根据题意，作出产销平衡与运价表。销地 运费单价/百

9、元产地一区1一区2二区三区1三区2供应量/t山西盂县1.801.801.701.551.554000河北临城1.601.601.501.751.751500需求量/t270030010001500500 6000需求必需求必须满足须满足需求必需求必须满足须满足需求必需求必须满足须满足55006000500产销平衡产销平衡0MMM0假想生产点运输费用？运输费用？这里 M 代表一个很大的正数，其作用是强迫相应的 x31、x33、x34 取值为 0。非必须非必须满足满足非必须非必须满足满足 3运输问题的应用运输问题的应用由软件计算可得，最优解为：X11=2200,X14=1500,X15=300,X

10、21=500,X23=1000,X32=300,X35=200总运费为9050百元 3运输问题的应用运输问题的应用例 5.设有 A、B、C 三个化肥厂供应四个地区的农用化肥。假设等量的化肥在这些地区使用效果相同，有关数据如表。试求总费用为最低的化肥调拨方案。销地 运费单价/（元/吨)产地IIIIIIIV产量/万吨A1613221750B1413191560C192023-50最低需求/万吨3070010最高需求/万吨507030不限 3运输问题的应用运输问题的应用解：根据题意，作出产销平衡与运价表。销地 运费单价/（元/吨)产地IIIIIIIIVIV产量/万吨A16161322171750B1

11、4141319151560C19192023MM50D50销量/万吨3020703010 210210必须满必须满足足必须满必须满足足必须满必须满足足虚设产地虚设产地运费为运费为050MMM000虚设产地虚设产地运费为运费为0虚设产地虚设产地运费为运费为0运输费用？运输费用？3运输问题的应用运输问题的应用应用软件计算，最优解如表。单位/万吨最小总费用为2460万元。销地 运输量产地IIIIIIIIVIV产量A5050B20103060C3020050D302050销量302070301050 210210 3运输问题的应用运输问题的应用例 6.某运输问题如下表所示，并假设各个产地的货物储存都发

12、生费用，其中1、2、3产地的单位存储费用分别为3、2、1元。假定产地2的物资必须至少运出28个单位，产地3至少运出17个单位，试求费用最少的运输方案。单位：元 销地 运费单价/元产地123产量145320253430335220销量203010 7060 3运输问题的应用运输问题的应用产大于销问题，构造产销平衡与运价表。销地 运费单价产地123产量1453202534282534233521733523销量20301070必须满足必须满足必须满足必须满足10MM32160704（库存）运输费用？存储费用存储费用存储费用存储费用存储费用存储费用产销平衡产销平衡 3运输问题的应用运输问题的应用由软

13、件计算可得，最优解为：X11=13,X14=7,X22=28,X32=2,X41=7,X43=10,X54=3.总运费为207元。3运输问题的应用运输问题的应用例7.造船厂根据合同从当年起连续三年末各提供五条规格型号相同的大型客货轮。该厂这三年内生产大型客货轮的能力及每艘客户轮的成本如下：年度正常生产能力/台 加班生产能力/台 正常生产单位成本/万元133600242700323650二、生产与储存问题 3运输问题的应用运输问题的应用 已知加班生产时，每艘客货轮成本比正常高出10%，造出的客货轮如当年不交货，每艘每积压一年所造成的积压损失为60万元。在签合同时，该厂已积压了两艘未交货的客货轮，

14、而该厂希望在第三年末完成合同后还能存储一艘。问该厂应如何安排每年客货轮的生产量，使在满足上述各项要求的情况下，总的生产费用为最少？3运输问题的应用运输问题的应用解：化为运输问题。考虑：每年生产与交货分别视为产地和销地（1）1-3年合计生产能力（包括第1年初积压量）为 19 艘，销量为 16艘。设一假想销地销量为 3艘；（2）第1年初积压量 2艘，只有积压损失费，列为第 0 行；（4）1-3表示 1-3年正常生产情况，1-3表示 1-3年加班生产情况。（3）第3年的需求除 5艘销量外，还要1艘库存，其需求为 5+1=6 艘；3运输问题的应用运输问题的应用产销平衡与运价表：销售年 单价/万元生产年

15、123正常产量/艘加班产量/艘060120180216006607203166072078032M70076042M77083023MM65023MM7153销量/台556 19虚拟的销地，即为仓库虚拟的销地，即为仓库假想 销地产销平衡产销平衡运输费用？运输费用？316190000000 3运输问题的应用运输问题的应用用管理运筹学软件解得：1-3年最低生产费用为 9665 万元，每年的生产销售安排如下。单位/艘 销售年 运输量生产年123假想 销量0111312124223233 3运输问题的应用运输问题的应用例8.某厂按合同规定须于当年每个季度末分别提供 10、15、25、20 台同一规格的

16、柴油机。已知该厂各季度的生产能力及生产每台柴油机的成本如表所示。如果生产出来的柴油机当季不交货，每台每积压一个季度需储存、维护等费用 0.15 万元。试求在完成合同的情况下，该厂全年生产总费用最小的决策方案。3运输问题的应用运输问题的应用 季度生产能力/台单位成本/万元I2510.8II3511.1III3011.0IV1011.3解：设 xij 为第 i 季度生产的第 j 季度交货的柴油机数目 3运输问题的应用运输问题的应用设 cij 为第 i 季度生产的第 j 季度交货的柴油机的实际成本，应是第i季度生产单位成本加上存储、维护费用。单位/万元 j iIIIIIIIVI10.810.9511

17、.1011.25II11.1011.2511.40III11.0011.15IV11.30不可能的情况，费用？不可能的情况，费用？MMMMMM 3运输问题的应用运输问题的应用构造假想的需求D，产销平衡与运价表：销地 运费单价/万元产地IIIIIIIV产量/台I10.810.9511.1011.2525IIM11.1011.2511.4035IIIMM11.0011.1530IVMMM11.3010销量/台10152520100虚拟的销地，即为仓库虚拟的销地，即为仓库30100D产销平衡产销平衡运输费用？运输费用？700000 3运输问题的应用运输问题的应用运用软件计算，最优解：单位/台 最优值

18、为773万元。销地 运输量产地IIIIIIIVD产量I1015025II053035III25530IV1010销量1015252030 3运输问题的应用运输问题的应用三、转运问题 发点：发货量收货量 中转站：发货量=收货量 收点：发货量收货量 3运输问题的应用运输问题的应用 在原运输问题上增加若干中转站：允许物品从一个发点运往另一个发点或中转站或收点；允许物品从一个中转站运往另外一个中转站或发点或收点；允许物品从一个收点运往另外一个收点或中转站或发点。3运输问题的应用运输问题的应用例9.腾飞电子仪器公司在大连和广州有两个分厂生产同一种仪器，大连分厂每月生产 400 台，广州分厂每月生产600

19、 台。该公司在上海和天津有两个销售公司负责对南京、济南、南昌、青岛四个城市的仪器供应。另外因大连距青岛较近，公司同意大连分厂向青岛直接供货，运输费用如图，单位百元。问应该如何调运仪器，可使总运输费用最低？3运输问题的应用运输问题的应用 腾飞公司运输网络图 1广州2大连3上海4天津5南京6济南7南昌8青岛2331426364465600400200150350300供应量需求量 3运输问题的应用运输问题的应用 解：设 xij 为从 i 到 j 的运输量，线性规划模型：目标函数：min f=所有可能的运输费用（运输单价与运输量乘积之和）约束条件：对产地（发点）i：输出量 输入量=产量对转运站（中转

20、点）：输入量 输出量=0对销地（收点）j：输入量 输出量=销量 3运输问题的应用运输问题的应用 目标函数 min f=2x13+3x14+3x23+x24+4x28+2x35+6x36+3x37+6x38+4x45+4x46+6x47+5x48约束条件 s.t x13+x14 600 （广州分厂供应量限制）x23+x24+x28 400（大连分厂供应量限制）x13 x23+x35+x36+x37+x38=0（上海销售公司，转运站）x14 x24+x45+x46+x47+x48=0（天津销售公司，转运站）x35+x45=200（南京的销量）xij 0,i,j=1,2,3,4,5,6,7,8 x3

21、6+x46=150（济南的销量）x37+x47=350（南昌的销量）x38+x48+x28=300（青岛的销量）3运输问题的应用运输问题的应用用管理运筹学软件解得：x13=550,x14=50,x23=0,x24=100,x35=200,x36=0,x37=350,x38=0,x45=0,x46=150,x47=0,x48=0,x28=300最小运输费用为：4 600 百元 3运输问题的应用运输问题的应用 例10.某公司有 A1、A2、A3 三个分厂生产某种物资，分别供应 B1、B2、B3、B4 四个地区的销售公司销售。假设质量相同，有关数据如下表，试求总费用为最少的调运方案。销地 运费单价/

22、百元产地B1B2B3B4产量/tA13113107A219284A3741059销量/t3656 2020 3运输问题的应用运输问题的应用假设：每个分厂的物资可以运到其他分厂、转运站、销地；每个销地的物资可以运到其他销地、转运站、分厂；每个中转站的物资可以运到其他转运站、产地、销地。3运输问题的应用运输问题的应用运价表：A1A2A3T1T2T3T4B1B2B3B410856746213A1A2A3T1T2T3T4B1B2B3B43-1-2374105231132284615-11145274-231218243232121-2631724111421194858-121321042224231

23、321433113101-35-21928 3运输问题的应用运输问题的应用解：转化为一般运输问题（1）把所有产地、销地、转运站同时看作产地和销地。（2）运输表中不可能方案的运费取作 M，自身对自身的运费为 0。（3）Ai：产量为 20+原产量，销量为 20；Ti：产量、销量均为 20；Bi：产量为 20，销量为 20+原销量，其中 20 为各点可能变化的最大流量。（4）对于最优方案，其中 xii为自身对自身的运量，实际上不进行运作。3运输问题的应用运输问题的应用解：扩大的运输问题产销平衡与运价表：A1 A2 A3 T1T2 T3 T4B1B2B3B4产量/tA1A2A3T1T2T3T4B1B2

24、B3B4销量/t3M01M237410520231013228462015M10114527204M2310218242032321201M262031724110142231194858M1021263210422242032510856746213026272429202020202020202024001321433113102010M35M2192820 3运输问题的应用运输问题的应用应用软件计算，最优解：A1 A2 A3 T1T2 T3 T4B1B2B3B4产量A1A2A3T1T2T3T4B1B2B3B4销量20203172020202020202063142362026520256

25、20262724292020202020202020240202071320 3运输问题的应用运输问题的应用最佳运输方案：最优值（最小运费）：68百元A17A24T1B13B26B35B4676A39636 产地（产量）35 销地（销量）3运输问题的应用运输问题的应用产地直接运输至销地的最小费用：85百元运输模型运输问题的计算机求解运输问题的应用运输问题的表上作业法本章内容本章内容4123 4运输问题的表上作业法运输问题的表上作业法 表上作业法是一种求解运输问题的特殊方法，其实质是单纯形法。运输问题都存在最优解。4运输问题的表上作业法运输问题的表上作业法 基本可行解基本可行解（m+n-1个基变

26、量个基变量）非基变量检验数非基变量检验数检验数大检验数大于等于于等于0 唯一最优解唯一最优解闭回路法调整方案闭回路法调整方案是是否否计算过程（假设产销平衡）非基变量检非基变量检验数等于验数等于0多个最优解多个最优解否否 4运输问题的表上作业法运输问题的表上作业法 例11.喜庆食品公司有三个生产面包的分厂 A1、A2、A3，有四个销售公司 B1，B2，B3，B4，其各分厂每日的产量、各销售公司每日的销量以及各分厂到各销售公司的单位运价如表，在表中产量与销量的单位为吨，运价的单位为百元/吨。问该公司应如何调运产品在满足各销点的需求量的前提下总运费最少？4运输问题的表上作业法运输问题的表上作业法 销

27、地 运价 百元/t产地B1B2B3B4产量/tA13113107A219284A3741059销量/t3656 2020 4运输问题的表上作业法运输问题的表上作业法一、确定初始基本可行解一、确定初始基本可行解 为了把初始基本可行解与运价区分开，我们把为了把初始基本可行解与运价区分开，我们把运价运价放在每一放在每一栏的栏的右上角右上角，每一栏的，每一栏的中间中间写上写上初始基本可行解初始基本可行解（调运量）。（调运量）。销地 产地B1B2B3B4产量A1 3 11 3 10 7 A2 1 9 2 8 4A3 7 4 10 5 9销量 3 656 4运输问题的表上作业法运输问题的表上作业法1.西北

28、角法西北角法 先先从表的左上角（即西北角）的变量从表的左上角（即西北角）的变量x11开始分配运输量，开始分配运输量，并并使使x11取尽可能大的值，即取尽可能大的值，即x11=min(7,3)=3,则则x21与与x31必为零。必为零。同时把同时把B1的销量与的销量与A1的产量都减去的产量都减去3填入销量和产量处，划去填入销量和产量处，划去原来的销量和产量。同理可得余下的初始基本可行解。原来的销量和产量。同理可得余下的初始基本可行解。对西北角的变量分配运输量对西北角的变量分配运输量 使运输量最大使运输量最大 至少使一产地或销地的剩余量为至少使一产地或销地的剩余量为0 4运输问题的表上作业法运输问题

29、的表上作业法 销地 产地B1B2B3B4产量A1 3 11 3 10 7 A2 1 9 2 8 4A3 7 4 10 5 9销量 3 656342236x11=min(7,3)=3 x12=min(4,6)=404020602030 x22=min(4,2)=2x23=min(2,5)=2x33=min(3,9)=3x34=min(6,6)=60 4运输问题的表上作业法运输问题的表上作业法 2最小元素法最小元素法 西北角法是对西北角的变量分配运输量，而最小元素法是就近西北角法是对西北角的变量分配运输量，而最小元素法是就近供应，即供应，即对单位运价最小的变量分配运输量对单位运价最小的变量分配运输

30、量。在表上找到单位运价。在表上找到单位运价最小的最小的x21，并使，并使x21取尽可能大的值，即取尽可能大的值，即x21=min(4,3)=3,把把A2的产的产量改为量改为1，B1的销量改为的销量改为0，并把，并把B1列划去。在剩下的列划去。在剩下的33矩阵中矩阵中再找最小运价，同理可得其他的基本可行解。再找最小运价，同理可得其他的基本可行解。一般来说用最小元素法求得的初始基本可行解比西北角法求得一般来说用最小元素法求得的初始基本可行解比西北角法求得的总运价要少。这样从用最小元素法求得的初始基本可行解出发求的总运价要少。这样从用最小元素法求得的初始基本可行解出发求最优解的迭代次数可能少一些。最

31、优解的迭代次数可能少一些。对单位运价最小的变量分配运输量对单位运价最小的变量分配运输量使运输量最大使运输量最大至少使一产地或销地的剩余量为至少使一产地或销地的剩余量为0 4运输问题的表上作业法运输问题的表上作业法 销地 产地B1B2B3B4产量A1 3 11 3 10 7 A2 1 9 2 8 4A3 7 4 10 5 9销量 3 656346133x11=min(4,3)=3x23=min(1,5)=103010303040 x32=min(9,6)=6x34=min(3,6)=3x13=min(7,4)=4x14=min(3,3)=30 4运输问题的表上作业法运输问题的表上作业法在求初始基

32、本可行解时要注意的两个问题：在求初始基本可行解时要注意的两个问题：l1.1.当取定当取定x xijij的值之后，会出现的值之后，会出现A Ai i的产量与的产量与B Bj j的销量都改的销量都改为零的情况，这时只能划去为零的情况，这时只能划去A Ai i行或行或B Bj j列，但不能同时划列，但不能同时划去去A Ai i行与行与B Bj j列。列。l2.2.用最小元素法时，可能会出现只剩下一行或一列的用最小元素法时，可能会出现只剩下一行或一列的所有格均未填数或未被划掉的情况，此时在这一行或所有格均未填数或未被划掉的情况，此时在这一行或者一列中除去已填上的数外均填上零，不能按空格划者一列中除去已

33、填上的数外均填上零，不能按空格划掉。这样可以保证填过数或零的格为掉。这样可以保证填过数或零的格为m+n-1m+n-1个，即保证个，即保证基变量的个数为基变量的个数为m+n-1m+n-1个。个。l即初始基本可行解一定满足：每一行（列）至少有一即初始基本可行解一定满足：每一行（列）至少有一个格子被填上数字；每一行（列）一定被划掉。个格子被填上数字；每一行（列）一定被划掉。4运输问题的表上作业法运输问题的表上作业法二、最优解的判别1闭回路法 从非基变量的空格出发，沿水平或垂直方向前进，只有碰到基变量的格才能垂直拐弯（或穿过），直至回到发点，形成的封闭折线叫做闭回路。一个空格存在唯一的闭回路 4运输问

34、题的表上作业法运输问题的表上作业法 闭回路法：对闭回路各顶点进行编号，非基变量（编号为1）调运量调整为加 1，并对闭回路上顶点的调运量加1（奇数顶点）或减少 1（偶数顶点），以保持产销平衡的要求。非基变量检验数：调整运输方案引起费用的变化。为了区别调整量，把检验数圈起来。检验数都大于等于零，则已求得最优解。4运输问题的表上作业法运输问题的表上作业法寻找非基变量x11的检验数：销地 产地B1B2B3B4产量A1 3 4 3 7 A2 3 1 1 2 4 A39 销量3656非基变量非基变量x11x11调运量增加调运量增加1t，运费增加运费增加3百元百元保持保持A1产量平衡，产量平衡，x13减减少

35、少1t，运费减少，运费减少3百元百元保持保持B3销量平衡，销量平衡，x23增增加加1t，运费增加，运费增加2百元百元保持保持A2与与B1平衡，平衡，x21减减少少1t，运费减少，运费减少1百元百元调整后运费增加调整后运费增加3-3+2-1=1百元百元 4运输问题的表上作业法运输问题的表上作业法2位势法运输表上的每一行赋予数值 ui，每一列赋予数值vj。数值由基变量 xij 的检验数 ij=cijuivj =0 决定。非基变量 xij的检验数为ij=cij uivj。4运输问题的表上作业法运输问题的表上作业法 销地 产地B1B2B3B4uiA1 3 11 4 3 3 10 A2 3 1 9 1

36、2 8A3 7 6 4 10 3 5vj12-10-1-529310令令u1=0v3=c13 u1=3-0=3令令13=0令令14=0v4=c14 u1=10-0=10令令23=0u2=c23 v3 =2-3=-1令令34=0u3=c34 v4 =5-10=-5令令21=0v1=c21 u2 =1-(-1)=2令令32=0v2=c32 u3 =4-(-5)=911=c11 u1 v1 =3 0 2=112=c12 u1 v2=11 09=222=c22 u2 v2=9(1)-9=124=c24 u2 v4=8(1)-10=-131=c31 u3 v1=7(5)-2=1033=c33 u3 v3

37、=103(5)=12 4运输问题的表上作业法运输问题的表上作业法三、改进运输方案的办法闭回路调整法调整判别准则：存在检验数小于零调整方法：选取所有负检验数最小的非基变量作为入基变量在以x24为出发点的闭回路中，找出所有偶数的顶点的调运量：x14=3，x23=1，x24=min(3,1)=1。把所有闭回路上为偶数顶点的运输量都减少这个值，奇数顶点的运输量都增加这个值(见下表)。4运输问题的表上作业法运输问题的表上作业法 销地 产地B1B2B3B4uiA1 3 11 4 3 3 10 A2 3 1 9 1 2 8A3 7 6 4 10 3 5vj12-10-1-529310非基变量检验数非基变量检

38、验数最小为最小为-1，对应，对应非基变量为非基变量为x24基，为入基变量，基，为入基变量，作闭回路作闭回路 4运输问题的表上作业法运输问题的表上作业法 销地 产地B1B2B3B4产量A1 4 3 7 A2 3 1 4 A3639 销量3656x24=min(3,1)=1(+1)(-1)(-1)(+1)4运输问题的表上作业法运输问题的表上作业法调整后的运输方案：销地 产地B1B2B3B4产量A1 52 7 A2 3 14 A3639 销量3656 4运输问题的表上作业法运输问题的表上作业法 销地 产地B1B2B3B4uiA1 3 11 5 3 2 10 A2 3 1 9 2 1 8A3 7 6

39、4 10 3 5vj120-2-539310令u1=0v3=c13 u1=3-0=3令13=0令14=0v4=c14 u1=10-0=10令24=0u2=c24 v4 =8-10=-2令34=0u3=c34 v4 =5-10=-5令21=0v1=c21 u2 =1-(-2)=3令32=0v2=c32 u3 =4(5)=911=c11 u1 v1 =3 0 3=012=c12 u1 v2=11 09=222=c22 u2 v2=9(2)9=223=c23 u2 v3=2(2)3=131=c31 u3 v1=7(5)3=933=c33 u3 v3=103(5)=120所有非基变量检验数都大于等于零

40、，基变量的检验数等于零，此解释最优解。最小总费用为85百元。4运输问题的表上作业法运输问题的表上作业法四、如何找多个最优方案 多个最优解的判别：最优方案中存在非基变量的检验数为零。如在本题中给出的最优运输方案中x11的检验数为0，可知此运输问题有多个最优解。只要把x11作为入基变量，调整运输方案，就可得到另一个最优方案。4运输问题的表上作业法运输问题的表上作业法 销地 产地B1B2B3B4产量A1 5 2 7 A2 3 1 4 A3639 销量3656x11=min(2,3)=2（+2）（-2）（-2）（+2）4运输问题的表上作业法运输问题的表上作业法最优方案 最小费用为85百元。销地 产地B1B2B3B4A125A2 1 3A363谢谢 谢！谢！