2010生第七章运输问题

1第七章运输问题§1运输模型§2运输问题的计算机求解（EXCEL）§3运输问题的应用§4*运输问题的表上作业法2例1、某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？解：产销平衡问题：总产量=总销量设xij

为从产地Ai运往销地Bj的运输量，得到下列运输量表：

Minf=6x11+4x12+6x13+6x21+5x22+5x23s.t.x11+x12+x13=200

x21+x22+x23=300

x11+x21=150

x12+x22=150

x13+x23=200xij≥0(i=1、2；j=1、2、3）

§1运输模型3目标函数：MinF=

6x11+4x12+6x13

6x21+5x22+5x23x11+x12+x13=200x21+x22+x23=300x11+x21=150x12+x22=150x13+x23=200xij≥0产地约束，全部运出销地约束，全部运入非负条件，S.T.注意：约束条件——全部使用“=”

不能“≥“，因为产地没有那么多，不能”≤“，因为销地的供货不满足，4课

后

练

习

第

1

题5一般化：m个产地，

m个约束n个销地，

n个约束注意：1.不一定总是Min，有时Max，例如利润问题2.某些路线可能有能力限制，加条件，xij≤限制3.产销不平衡时，加入假想的产地或销地，详见下节6§2运输问题的计算机求解例2、某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？解：增加一个虚设的销地运输费用为07§2运输问题的计算机求解例3、某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？解：增加一个虚设的产地运输费用为08§3运输问题的应用一、产销不平衡的运输问题例4、石家庄北方研究院有一、二、三三个区。每年分别需要用煤3000、1000、2000吨，由河北临城、山西盂县两处煤矿负责供应，价格、质量相同。供应能力分别为1500、4000吨，运价为：由于需大于供，经院研究决定一区供应量可减少0--300吨，二区必须满足需求量，三区供应量不少于1500吨，试求总费用为最低的调运方案。解：根据题意，作出产销平衡与运价表：这里M代表一个很大的正数，其作用是强迫相应的x31、x33、x34取值为0。9§3运输问题的应用一、产销不平衡的运输问题例5、设有A、B、C三个化肥厂供应1、2、3、4四个地区的农用化肥。假设效果相同，有关数据如下表：

试求总费用为最低的化肥调拨方案。解：根据题意，作出产销平衡与运价表：

最低要求必须满足，因此把相应的虚设产地运费取为M，而最高要求与最低要求的差允许按需要安排，因此把相应的虚设产地运费取为0。对应4”的销量

50是考虑问题本身适当取的数据，根据产销平衡要求确定D的产量为50。

10§3运输问题的应用二、生产与储存问题例6、某厂按合同规定须于当年每个季度末分别提供10、15、25、20台同一规格的柴油机。已知该厂各季度的生产能力及生产每台柴油机的成本如右表。如果生产出来的柴油机当季不交货，每台每积压一个季度需储存、维护等费用0.15万元。试求在完成合同的情况下，使该厂全年生产总费用为最小的决策方案。11§3运输问题的应用解：设xij为第i季度生产的第j季度交货的柴油机数目，那么应满足：交货：x11=10生产：x11+x12+x13+x14≤25

x12+x22=15x22+x23+x24≤35x13+x23+x33=25x33+x34≤30x14+x24+x34+x44=20x44≤10

把第i季度生产的柴油机数目看作第i个生产厂的产量；把第j季度交货的柴油机数目看作第j个销售点的销量；成本加储存、维护等费用看作运费。可构造下列产销平衡问题：目标函数：Minf=10.8x11+10.95x12+11.1x13+11.25x14+11.1x22+11.25x23+11.4x24+11.0x33+11.15x34+11.3x4412§3运输问题的应用二、生产与储存问题例7、光明仪器厂生产电脑绣花机是以产定销的。已知1至6月份各月的生产能力、合同销量和单台电脑绣花机平均生产费用见下表：已知上年末库存103台绣花机，如果当月生产出来的机器当月不交货，则需要运到分厂库房，每台增加运输成本0.1万元,每台机器每月的平均仓储费、维护费为0.2万元。在7--8月份销售淡季，全厂停产1个月，因此在6月份完成销售合同后还要留出库存80台。加班生产机器每台增加成本1万元。问应如何安排1--6月份的生产，可使总的生产费用（包括运输、仓储、维护）最少？13§3运输问题的应用解：这个生产存储问题可化为运输问题来做。考虑：各月生产与交货分别视为产地和销地

1）1--6月份合计生产能力（包括上年末储存量）为743台，销量为707台。设一假想销地销量为36；

2）上年末库存103台，只有仓储费和运输费，把它列为第0行；

3）6月份的需求除70台销量外，还要80台库存，其需求应为70+80=150台；

4）1--6表示1--6月份正常生产情况，1’--6’表示1--6月份加班生产情况。产销平衡与运价表：14§3运输问题的应用

用EXCEL软件解得的结果是：1-6月最低生产费用为8307.5万元，每月的销售安排如下表所示15§3运输问题的应用三、转运问题：在原运输问题上增加若干转运站。运输方式有：产地转运站、转运站销地、产地产地、产地销地、销地转运站、销地产地等。例8、腾飞电子仪器公司在大连和广州有两个分厂生产同一种仪器，大连分厂每月生产400台，广州分厂每月生产600台。该公司在上海和天津有两个销售公司负责对南京、济南、南昌、青岛四个城市的仪器供应。另外因为大连距离青岛较近，公司同意大连分厂向青岛直接供货，运输费用如图，单位是百元。问应该如何调运仪器，可使总运输费用最低？图中1-广州、2-大连、3-上海、4-天津、5-南京、6-济南、7-南昌、8-青岛16§3运输问题的应用解：设xij

为从i到j的运输量，可得到有下列特点的线性规划模型：目标函数：Minf=所有可能的运输费用（运输单价与运输量乘积之和）约束条件：对产地（发点）i：输出量-输入量=产量对转运站（中转点）：输入量-输出量=0

对销地（收点）j：输入量-输出量=销量例8．（续）目标函数：Minf=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（南京的销量）

x36+x46=150（济南的销量）

x37+x47=350（南昌的销量）

x38+x48+x28=300（青岛的销量）

xij≥0,i,j=1,2,3,4,5,6,7,817运费3上海4天津5南京6济南7南昌8青岛发出1广州23MMMM6002大连31MMM44003上海MM2636x35+……x384天津MM4465x45+……x48接收x13+x23x14+x242001503503001000+转运解3上海4天津5南京6济南7南昌8青岛发出1广州5505000006002大连01000003004003上海00200035005504天津00015000150接收5501502001503503001000+700MinF=460018§3运输问题的应用用EXCEL软件求得结果：

x13=550x14=50；

x23=0x24=100x28=300；

x35=200x36=0x37=350x38=0；

x45=0x46=150x47=0x48=0。最小运输费用为：4600百元例9、某公司有A1、A2、A3三个分厂生产某种物资，分别供应B1、B2、B3、B4四个地区的销售公司销售。假设质量相同，有关数据如下表：

试求总费用为最少的调运方案。假设：

1.每个分厂的物资不一定直接发运到销地，可以从其中几个产地集中一起运；

2.运往各销地的物资可以先运给其中几个销地，再转运给其他销地；

3.除产销地之外，还有几个中转站，在产地之间、销地之间或在产地与销地之间转运。19§3运输问题的应用运价如下表：解：把此转运问题转化为一般运输问题：

1、把所有产地、销地、转运站都同时看作产地和销地；

2、运输表中不可能方案的运费取作M，自身对自身的运费为0；

3、Ai：产量为20+原产量，销量为20；Ti

：产量、销量均为20；Bi：产量为20，销量为20+原销量，其中20为各点可能变化的最大流量；

4、对于最优方案，其中xii

为自身对自身的运量，实际上不进行运作。20§3运输问题的应用

扩大的运输问题产销平衡与运价表：21§4.运输问题的表上作业法本章第1节中，2产地，3销地的问题中有6个变量，那么m产地，n销地的问题中就要有m*n个变量，对应的单纯形表中就要有m*n列

——如果用普通的单纯形法，计算烦琐！为简化计算，用“表上作业法”，实质也是单纯形法基本思路：注意：仅对“产销平衡问题！！”确定初始基本可行解是否最优？迭代否结束是22例10，3产地，4销地，产销平衡问题，1.确定初始可行解——迭代的起点单价(百元)销售点产量(吨)B1B2B3B4产地A13113107A219284A3741059销量(吨)365620解（0）销售点产量(吨)B1B2B3B4产地A1347A2224A3369销量(吨)365620不含数字的格：空格含有数字的格：数格每个数格：一个基变量基变量的个数：约束条件矩阵的秩，m+n-1m+n-1？？：Σ前m个约束=Σ后n个约束x11+x12+x13+x14=7x11+x21+x31=3x21+x22+x23+x24=4x12+x22+x32=6x31+x32+x33+x34=9x13+x23+x33=5x14+x24+x34=623确定初始可行解的3种方法——西北角法、最小元素法“伏格尔法”（增加）西北角法，（左上角）尽可能排满左上角的运量，例，解（0）销售点产量(吨)B1B2B3B4产地A17A24A39销量(吨)3656203？73B1已经运量满足，所以……A1已经运出3吨给B1，还剩余4吨须要运往其它销地下一个西北角(左上角)，继续……,确定初始基本可行解6?4?\44236西北角法，简单，确定的初始解的基变量分布在对角线上，可能与最优解存在很大差异，这就增加了后面的迭代次数！24解（0）销售点产量(吨)B1B2B3B4产地A17A24A39销量(吨)365620单价(百元)销售点产量(吨)B1B2B3B4产地A13113107A219284A3741059销量(吨)365620(2)

最小元素法：优先安排运费最小的路线(数格，基变量)3\1\143163最小元素法，稍复杂，确定的初始解比较接近最优解，但不是最接近最优解的方法25(3)

伏格尔法：优先安排运费最具“优势”的路线(横比、纵比)第1步，计算，行、列差额=|最小–

次小|,

差额越大，对应的“优势”越大，谁的优势？第2步，取差额最大，再取对应的最小运费的路线，优先安排第3步，划去运完的产(销)地.，未运完的要减去相应的运量第4步，重复1、2、3，直到确定初始解运费B1B2B3B4311310192874105解产(吨)B1B2B3B474936562025130

1

16\\352

31

3

伏格尔法，最复杂，确定的初始解“最”接近最优解，

注意：不论使用哪个方法，如果同时划去一行、一列要在行、列的任意位置补一个“0”，当作数格(基变量)看待262.最优性判定

——计算检验数，空格（非基变量）的检验数

——两种方法“闭回路法”、“位势法”(1)闭回路法：从一个空格出发，遇到数格转90度，也可穿过最终回到出发的空格。例，

x11

x13x23x21x11

该空格(非基变量)的检验数：

σ11=

c11

–c13+c23–c21=Σc奇–Σc偶

=3–3+2–1=1433163311310192874105解运费分析，如果x11由01，这就增加了A1、B1的运量为满足A1的运量，x13就要减少1个运量，又影响了B3为满足B3的运量，x23就要增加1个运量，又影响了A2为满足A2的运量，x21就要减少1个运量，B1也满足了这样，才算完成x11的调整，(所以要找“闭回路”)此时，总运费的变动=c11

–c13+c23

–c21=1即，增加x11处的运量(变成基变量)不能优化当前方法结论，最优方法的检验数全部非负（大于等于0）B1B2B3B4出A1437A2314A3639进365627(2)位势法，比较简便ui为每1行确定1个位势值，

vj为每1列确定1个位势值，检验数σij=cij–(ui+vj)，例：x13是基变量，∴σ13=0=c13–(u1+v3)令u1=0，则v3=c13=3继续，v4=c14=10再继续，……所有的位势值再计算非基变量的检验数：σij=cij–(ui+vj)σ11=c11–(u1+v1)=3–(0+2)=1费B1B2B3B4uiA1311310A21928A374105vj433163解30293100-1-5基本思路：利用公式(ui+vj)=cij-σ基变量=cij计