运输问题-课件

第三章运输问题第三章运输问题产销不平衡的运输问题内容运输问题表上作业法123运输问题的应用4产销不平衡的运输问题内容运输问题表上作业法123运《运筹学》第三章运输问题Slide3一、运输模型（产销平衡）例1．某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地的每件物品的运费如下表所示：问：应如何调运，使得总运输费最小？设Xij表示从产地Ai调运到Bj的运输量(i＝1，2；j＝1，2，3)，现将安排的运输量列表如下：《运筹学》《运筹学》第三章运输问题Slide4产销平衡表满足产地产量的约束条件为：

X11+X12+X13=200X21+X22+X23=300满足销地销量的约束条件为：

X11+X21＝150X12+X22＝150X13+X23＝200《运筹学》《运筹学》第三章运输问题Slide5使运输费最小的目标函数为：

minz＝6X11+4X12+6X13+6X21+5X22+5X23Xij>=0一般运输问题的线性规划的模型：有m个产地生产某种物资，有n个地区需要该类物资。Al，A2，…，Am表示某种物资的m个产地；Bl，B2，…，Bn表示某种物资的n个销地；令a1,a2,…,am表示各产地产量，b1,b2,…,bn表示各销地的销量，ai=bj称为产销平衡。Cij表示把物资从产地Ai运到销地Bj的单位运价。同样设Xij表示从产地Ai运到销地Bj的运输量。《运筹学》《运筹学》第三章运输问题Slide6则产销平衡的运输问题的线性规划模型如下所示：运输问题有mn个决策变量，m+n个约束条件。由于产销平衡条件，只有m+n–1个相互独立，因此，运输问题的基变量只有m+n–1个。《运筹学》《运筹学》第三章运输问题Slide7共有2个产地和3个销地，产销平衡。基变量的个数为2+3-1=4Objectivevalue:2500《运筹学》《运筹学》第三章运输问题Slide8二、表上作业法表上作业法是单纯形法在求解运输问题时的一种简化方法，其实质是单纯形法。(1)给出初始调运方案——初始基可行解：即在(m×n)产销平衡表上给出m+n-1个数字格。用最小元素法或伏格尔法。(2)检验方案是否最优，若是最优解，则停止计算；否则转下一步。求各非基变量的检验数，即在表上计算空格的检验数。在表上用闭环回路法或乘数法。(3)调整调运方案，得新的方案。——确定入基和出基变量，找出新的基可行解。在表上用闭环回路法。(4)重复(2),(3)直到求出最优方案。【定理】：产销平衡的运输问题一定有可行解，且一定有最优解。《运筹学》《运筹学》第三章运输问题Slide9证：记∑ai=∑bj=QXij=aibj/Q就是一个可行解，因为Xij≥0，且满足∑Xij=ai,∑Xij=bj又因为Cij≥0,Xij≥0,所以目标函数有下界零。因而运输问题一定有最优解。1、确定初始基可行解最常用的方法是最小元素法。——既简便，又尽可能接近最优解。最小元素法的基本思想是就近供应，即从单位运价表中最小的运价开始确定供销关系，同时兼顾各产销地的需求，然后次小，一直到给出初始基可行解为止。《运筹学》《运筹学》第三章运输问题Slide10P83例2.1：某公司经销甲产品，它下设三个加工厂，每日的产量分别为A1－7吨，A2－4吨，A3－9吨。该公司把这些产品分别运往四个销售点。各销售点每日销量为B1－3吨，B2－6吨，B3－5吨，B4－6吨。已知从各工厂到各销售点的单位产品的运价如下表所示。

产销平衡表《运筹学》1）找出最小运价为1，先将A2的产品供应给B1，因a2>b1，A2除满足B1的全部需要外，还可多余1吨产品。在(A2,B1)的交叉格处填上3。并将B1列运价划去。2）在未划去的元素中再找出最小运价2，确定A2多余的1吨供应B3。在(A2,B3)的交叉格处填上1。并将A2行运价划去3）在未划去的元素中再找出最小的运价3，这样一步步进行下去，直到运价表上的所有元素划去为止。最后在(A1,B4)的交叉格处填上3，将A1行和B4列运价同时划去，得到一个初始调运方案。这方案的总运费为86元。3146331）找出最小运价为1，先将A2的产品供应给B1，因a2>b1《运筹学》第三章运输问题Slide12最小元素法中的退化情况第一次划去第1列B1，第二次最小运价为2，对应的销地B2销量和产地A3的产量未分配量皆为6，故同时划去B2列和A3行。非零的数字格小于(m+n-1)个。出现退化时，要在同时被划去的行列中选一个空格填0，此格作为有数字格。345602《运筹学》伏格尔法(Vogel)——差额法：最小元素法的缺点是：为了节省一处的费用，有时会造成在其他处要多花几倍的运费。伏格尔法考虑到：一产地的产品假如不能按最小运费就近供应，就应考虑次小运费。这就有一个差额，差额越大，说明不能按最小运费调运时，运费增加越多。因而对差额最大处，就应当采用最小运费调运。315632伏格尔法(Vogel)——差额法：315632运输问题-课件《运筹学》第三章运输问题Slide151）分别计算出各行和各列的最小运费和次最小运费的差额，填入表格的最右列和最下行。2）从行或列差额中选出最大者，选择它所在行或列中的最小元素。B2列中的最小元素是4，可确定A3的产品先满足B2的需要，同时将B2列运价划去。3）对未划去的元素再分别计算出各行、各列的最小运费和次最小运费的差额，重新填入表格的最右列和最下行。重复1）2），直到找到初始调运方案。总运费为85元。伏格尔法给出的初始解比用最小元素法给出的更接近最优解。本例用伏格尔法给出的初始解就是最优解。《运筹学》《运筹学》第三章运输问题Slide162、调运方案的检验判别的方法是计算空格（非基变量）的检验数，若所有的检验数都大于等于0，为最优解。1）闭环回路法：在给出的初始调运方案表上，从每一空格出发找一条闭环回路，它是以某空格为起点，用水平或垂直线向前划，每碰到一数字格转90°后（回路的转角点必须是一个基变量），继续前进，直到回到起始空格为止。从每一空格出发一定存在且只有唯一的闭环回路。从空格开始加减闭环各个顶点的运输单价，可得每个空格对应的检验数。《运筹学》314633314633《运筹学》第三章运输问题Slide18闭环回路计算检验数的经济解释为：从任一空格出发，如(A1,B1)，若让A1的产品调运1吨给B1，为了保持产销平衡，就要依次作调整：在(A2,B1)处减少1吨，在(A2,B3)处增加1吨，在(A1,B3)处减少1吨，即构成了以空格(A1,B1)为起点的闭环回路。调整后的方案使运费变成(+1)×3＋(－1)×1＋(+1)×2＋(－1)×3＝1（元）这就是(A1,B1)的检验数。当检验数还存在负数时，说明原方案还不是最优解。用闭环回路求检验数,当产销点很多时,这种计算很繁琐。2）乘数法（位势法）：乘数法的原理是对偶理论。《运筹学》运输问题对偶问题σij与原问题有什么关系？

由对偶性质，σij是原问题变量xij的检验数。

当xij是基变量时，σij=0，此时有由此求出Ui和Vj，再代回（*）式求非基变量的σij（空格检验数）P93-94运输问题对偶问题σij与原问题有什么关系？P93-94基变量：X13U1+V3=C13=3X14U1+V4=C14=10X21U2+V1=C21=1X23U2+V3=C23=2X32U3+V2=C32=4X34U3+V4=C34=5设U1＝0，则V3=3,U2=-1,V1=2,V4=10,U3=-5,V2=9非基变量：C11－U1－V1=3－0－2＝1C12－U1－V2＝11－0－9＝2C22－U2－V2=9＋1－9＝1C24－U2－V4＝8＋1－10＝－1C31－U3－V1=7+5－2＝10C33－U3－V3=10＋5－3＝12基变量：3、调整改进的闭环回路方法——迭代若有两个或两个以上的负检验数时，一般选其中最小的负检验数。以(24)格为调入格，以此格为出发点，作一闭环回路。在闭回路上进行运量调整，使选定空格处的运量尽可能地增加（即取相邻两数字格中较小的）。运量调整后，必然使某个数字格变成零。把一个变成零的数字格抹去，得新的调运方案。经检验，所有检验数都非负，故达到最优，最优方案总运费最小是85元。3、调整改进的闭环回路方法——迭代若有两个或两个以上的负检验《运筹学》第三章运输问题Slide22课堂作业：1、用表上作业法求出最优解。（最小元素法）2、用伏格尔法直接给出近似最优解。《运筹学》《运筹学》第三章运输问题Slide231、这是一个产销平衡的问题。1）初始调运方案（最小元素法）401520251025初始调运方案的总运费为420元。2）最优解的判别（闭环回路法）《运筹学》401520251025401520251025（乘数法）：基变量：X11U1+V1=C11=3X12U1+V2=C12=2X21U2+V1=C21=7X23U2+V3=C23=2X24U2+V4=C24=3X31U3+V1=C31=2设U1＝0，则V1=3,V2=2,U2=4,V3=-2,V4=-1,U3=-1非基变量：C13－U1－V3=7－0+2＝9C14－U1－V4＝6－0+1＝7C22－U2－V2=5－4－2＝-１C32－U3－V2＝5＋1－2＝4C33－U3－V3=4+1+2＝7C34－U3－V4=5+1+1＝7（乘数法）：《运筹学》第三章运输问题Slide263)调整调运方案，得新的方案。以(22)格为调入格，以此格为出发点，作一闭环回路。经检验，所有检验数都大于0，该调运方案是最优的方案。总运费为395元。401520251025151520253525《运筹学》2、用伏格尔法直接给出近似最优解。52020252010002、用伏格尔法直接给出近似最优解。5202025201000运输问题-课件《运筹学》第三章运输问题Slide29用伏格尔法直接找到了近似最优方案，总运价为305元。《运筹学》《运筹学》第三章运输问题Slide30第二种算法：用伏格尔法直接找到了近似最优方案，总运价为345元。用伏格尔法求解，是否一定要转化为产销平衡表？《运筹学》三、产销不平衡的运输问题

产销平衡表

P96例2.3：假设产地A1的产品必须全部调运出去,产地A2、A3的商品调运不出的单位存储费为2百元和1百元产大于销三、产销不平衡的运输问题产销平衡表P96例2.3：假设产运输费用：2×2+5×4+3×3+4×1+1×2=39(百元)

存储费用：2×2+2×1=6(百元)总成本：39+6=45(百元)P98例2.4销大于产运输费用：2×2+5×4+3×3+4×1+1×2=39(百销地B1、B2的需求必须全部满足，销地B3、B4每短缺1吨，发生损失费1百元、0。总成本是52百元，其中2百元是销地B3发生缺货的损失费。销地B1、B2的需求必须全部满足，销地B3、B4每短缺1吨，《运筹学》第三章运输问题Slide34例3．石家庄北方研究院有三个区，即一区、二区、三区，每年分别需要生活用煤和取暖用煤3000、1000、2000吨，由河北临城，山西孟县两处煤矿负责供应，这两处煤矿的价格相同，煤的质量也基本相同。两处煤矿能供应北方研究院的煤的数量，山西盂县为4000吨，河北临城为l500吨，由煤矿至北方研究院的单位运价(百元／吨)见下表。由于需求大于供给，经院研究平衡决定一区供应量可减少0～200吨，二区需要量应全部满足，三区供应量不少于1700吨。试求总运费最低的调运方案。《运筹学》《运筹学》第三章运输问题Slide35河北临城，山西孟县两处煤矿可以供应煤5500吨。一区、二区、三区至少需要煤5500吨。至多需要煤6000吨。一区和三区必须供应的煤分别为2800吨和1700吨。可以不供应的煤分别为200吨和300吨。产销平衡表《运筹学》《运筹学》第三章运输问题Slide36例4．设有三个化肥厂供应四个地区的农用化肥。假定等量的化肥在这些地区使用效果相同。各化肥厂年产量，各地区年需要量及从各化肥厂到各地区运送单位化肥的运价如下表所示，试求出总的运费最节省的化肥调运方案。《运筹学》《运筹学》第三章运输问题Slide37三个化肥厂共可供应化肥160吨。问：根据现有三个化肥厂的产量，地区IV

最高需求是否可以不限？最高需求是多少？160－30－70－0＝60吨四个地区对化肥的最高需求为50＋70＋30＋60＝210吨《运筹学》《运筹学》第三章运输问题Slide38四、运输问题的应用（一）生产与储存的问题

P109习题2-16某厂按合同规定须于当年每个季度末分别提供10,15,25,20台同一规格的柴油机。已知该厂各季度的生产能力及市场每台柴油机的成本如下表所示。又如果生产出来的柴油机当季不交货的，每台每积压一个季度需储存、维护费用0.2万元。要求在完成合同的情况下，做出使该厂全年生产（包括储存、维护）费用最小的决策。《运筹学》《运筹学》第三章运输问题Slide39设Xij为第i季度生产的用于第j季度交货的柴油机数实际的成本为该季度生产成本加上储存和维护费用。四个季度的生产能力为100台。而四个季度末共须提供柴油机70台。《运筹学》《运筹学》第三章运输问题Slide40例6．光明仪器厂生产电脑绣花机是以销定产的。已知1至6月份各月的生产能力、合同销量和单台电脑绣花机平均生产费用见下表。又已知上年末库存103台绣花机。加班生产机器每台增加成本1万元。《运筹学》《运筹学》第三章运输问题Slide41又如果当月生产出来的机器当月不交货，则需要运到分厂库房，每台增加运输成本0.1万元，每台机器每月的平均仓储费、维护费为0.2万元。在7、8月份销售淡季，全厂停产1个月，因此在6月份完成销售合同后还要留出库存80台。问应如何安排1~6月份的生产使总的生产(包括运输、仓储、维护)费用最少?设Xij为第i个月生产的用于第j个月交货的机器数实际的成本为该月生产成本加上运输、储存和维护费用将正常生产和加班生产分成两种不同的生产月来进行安排。六个月的生产能力为743台。而六个月末共须提供机器707台。上年末库存的103台绣花机，作为第0个月的生产供给。《运筹学》运输问题-课件《运筹学》第三章运输问题Slide43（二）调度问题例7：某航运公司承担六个港口初始A、B、C、D、E、F的四条固定航线的物资运输任务。已知各条航线的起点、终点城市及每天航班数见下表7－1。假定各条航线使用相同型号的船只，又各城市间的航程天数见表7－2。又知每条船只每次装卸货的时间各需1天，则该航运公司至少应配备多少条船，才能满足所有航线的运货需求？

表7－1《运筹学》表7－2(1)载货航程需要的周转船只数：表7－2(1)载货航程需要的周转船只数：《运筹学》第三章运输问题Slide45

例如：航线1，在港口E装货1天，E－D航程17天，在D卸货1天，总计19天。每天3航班。故该航线需周转船57条以上共需周转船只数91条。(2)各港口间调度所需船只数。有些港口每天到达船数多于需要船数。例如，港口D，每天到达3条，需求1条。《运筹学》《运筹学》第三章运输问题Slide46

为使各港口间调度周转所需的空船数最少，其产销平衡表如下。单位运价应为相应各港口之间的船只航程天数。可求出空船的最优调度方案如下：《运筹学》《运筹学》第三章运输问题Slide47

由上表可计算得知最少周转的空船数为40条。所以，在不考虑维修、储备等情况下，该公司至少应配备131条船。（三）转运问题例8．腾飞电子仪器公司在大连和广州有两个分厂，大连分厂每月生产400台某种仪器，广州分厂每月生产600台某种仪器。该公司在上海与天津有两个销售公司负责对南京、济南、南昌与青岛四个城市的仪器供应，又因为大连与青岛相距较近，公司同意大连分厂也可以向青岛直接供货。这些城市间的每台仪器的运输费用我们标在两个城市间的弧上，单位为百元。问应该如何调运仪器，使得总的运输费最低。《运筹学》《运筹学》第三章运输问题Slide48思路:将转运问题化为无转运问题。中转地3、4既可作为产地，也可作为销地。《运筹学》

例9：某公司经销甲产品，它下设三个加工厂，每日的产量分别为A1－7吨，A2－4吨，A3－9吨。该公司把这些产品分别运往四个销售点。各销售点每日销量为B1－3吨，B2－6吨，B3－5吨，B4－6吨。已知从各工厂到各销售点的单位产品的运价如下表所示。课本P100例2.5

例9：某公司经销甲产品，它下设三个加工厂，每日的产量分别为《运筹学》第三章运输问题Slide50如果假定1）每个工厂生产的产品不一定直接发运到销售点，可以其中几个产地集中一起运；2）运往各销售点的产品可以先运给其中几个销售点，再转运给其它销售点；3）除产地、销售点之外，中间还可以有几个转运站，在产地之间、销售点之间或产地与销售点之间转运。已知各产地、销售点、中间转运站及相互之间每吨产品的运价如下表所示，问在考虑到产销地之间直接运输和非直接运输的各种可能方案的情况下，如何将三个厂每天生产的产品运往各个销售点，使总的运费最少。《运筹学》运输问题-课件《运筹学》第三章运输问题Slide52从A1到B2的单位运价为11元，如从A1经A3运往B2，运价为3＋4＝7元，从A1经T2运往B2，运价为1＋5＝6元。运费最少的路经是从A1经A2、B1运往B2，运价为1+1+1＝3元1)所有的产地、中转地和销地都可以看作产地，也可以看作销地。因此整个问题被当作有11个产地和11个销地的扩大运输问题。2)中转站的产量等于销量。每个中转站的转运量不大于20吨。可以规定四个中转站的产量和销量均为20吨。实际的转运量小于20吨，可以加入一个松弛量Xii，对应的运价为0。(20－Xii)为实际的转运量。3)原来的产地和销地也有转运站的作用，故三个厂产量为27、24、29吨，销量均为20吨，四个销售点的销量为23、26、25、26吨，产量均为20吨。同时引进Xii作为松弛变量。《运筹学》运输问题-课件《运筹学》第三章运输问题Slide54例10：某厂在A、B、C三处设仓库供应①～⑧点的各零售商，详见下图。图中各边数字为沿该线路运送一单位物资所需的费用（元）。已知A、B、C三仓库内现库存物资数分别为200、170、160单位。①～⑧点各零售商所需物资数列于下表。且对零售商供应短缺一单位时的罚款也列于表中。应如何确立各仓库对各零售点的分配量，使总的运输费和罚款之和最小。《运筹学》①②③④⑤⑥⑦⑧ABC①②③④⑤⑥⑦⑧ABC《运筹学》第三章运输问题Slide56总供给量530，总需求量550。

《运筹学》第三章运输问题第三章运输问题产销不平衡的运输问题内容运输问题表上作业法123运输问题的应用4产销不平衡的运输问题内容运输问题表上作业法123运《运筹学》第三章运输问题Slide59一、运输模型（产销平衡）例1．某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地的每件物品的运费如下表所示：问：应如何调运，使得总运输费最小？设Xij表示从产地Ai调运到Bj的运输量(i＝1，2；j＝1，2，3)，现将安排的运输量列表如下：《运筹学》《运筹学》第三章运输问题Slide60产销平衡表满足产地产量的约束条件为：

X11+X12+X13=200X21+X22+X23=300满足销地销量的约束条件为：

X11+X21＝150X12+X22＝150X13+X23＝200《运筹学》《运筹学》第三章运输问题Slide61使运输费最小的目标函数为：

minz＝6X11+4X12+6X13+6X21+5X22+5X23Xij>=0一般运输问题的线性规划的模型：有m个产地生产某种物资，有n个地区需要该类物资。Al，A2，…，Am表示某种物资的m个产地；Bl，B2，…，Bn表示某种物资的n个销地；令a1,a2,…,am表示各产地产量，b1,b2,…,bn表示各销地的销量，ai=bj称为产销平衡。Cij表示把物资从产地Ai运到销地Bj的单位运价。同样设Xij表示从产地Ai运到销地Bj的运输量。《运筹学》《运筹学》第三章运输问题Slide62则产销平衡的运输问题的线性规划模型如下所示：运输问题有mn个决策变量，m+n个约束条件。由于产销平衡条件，只有m+n–1个相互独立，因此，运输问题的基变量只有m+n–1个。《运筹学》《运筹学》第三章运输问题Slide63共有2个产地和3个销地，产销平衡。基变量的个数为2+3-1=4Objectivevalue:2500《运筹学》《运筹学》第三章运输问题Slide64二、表上作业法表上作业法是单纯形法在求解运输问题时的一种简化方法，其实质是单纯形法。(1)给出初始调运方案——初始基可行解：即在(m×n)产销平衡表上给出m+n-1个数字格。用最小元素法或伏格尔法。(2)检验方案是否最优，若是最优解，则停止计算；否则转下一步。求各非基变量的检验数，即在表上计算空格的检验数。在表上用闭环回路法或乘数法。(3)调整调运方案，得新的方案。——确定入基和出基变量，找出新的基可行解。在表上用闭环回路法。(4)重复(2),(3)直到求出最优方案。【定理】：产销平衡的运输问题一定有可行解，且一定有最优解。《运筹学》《运筹学》第三章运输问题Slide65证：记∑ai=∑bj=QXij=aibj/Q就是一个可行解，因为Xij≥0，且满足∑Xij=ai,∑Xij=bj又因为Cij≥0,Xij≥0,所以目标函数有下界零。因而运输问题一定有最优解。1、确定初始基可行解最常用的方法是最小元素法。——既简便，又尽可能接近最优解。最小元素法的基本思想是就近供应，即从单位运价表中最小的运价开始确定供销关系，同时兼顾各产销地的需求，然后次小，一直到给出初始基可行解为止。《运筹学》《运筹学》第三章运输问题Slide66P83例2.1：某公司经销甲产品，它下设三个加工厂，每日的产量分别为A1－7吨，A2－4吨，A3－9吨。该公司把这些产品分别运往四个销售点。各销售点每日销量为B1－3吨，B2－6吨，B3－5吨，B4－6吨。已知从各工厂到各销售点的单位产品的运价如下表所示。

产销平衡表《运筹学》1）找出最小运价为1，先将A2的产品供应给B1，因a2>b1，A2除满足B1的全部需要外，还可多余1吨产品。在(A2,B1)的交叉格处填上3。并将B1列运价划去。2）在未划去的元素中再找出最小运价2，确定A2多余的1吨供应B3。在(A2,B3)的交叉格处填上1。并将A2行运价划去3）在未划去的元素中再找出最小的运价3，这样一步步进行下去，直到运价表上的所有元素划去为止。最后在(A1,B4)的交叉格处填上3，将A1行和B4列运价同时划去，得到一个初始调运方案。这方案的总运费为86元。3146331）找出最小运价为1，先将A2的产品供应给B1，因a2>b1《运筹学》第三章运输问题Slide68最小元素法中的退化情况第一次划去第1列B1，第二次最小运价为2，对应的销地B2销量和产地A3的产量未分配量皆为6，故同时划去B2列和A3行。非零的数字格小于(m+n-1)个。出现退化时，要在同时被划去的行列中选一个空格填0，此格作为有数字格。345602《运筹学》伏格尔法(Vogel)——差额法：最小元素法的缺点是：为了节省一处的费用，有时会造成在其他处要多花几倍的运费。伏格尔法考虑到：一产地的产品假如不能按最小运费就近供应，就应考虑次小运费。这就有一个差额，差额越大，说明不能按最小运费调运时，运费增加越多。因而对差额最大处，就应当采用最小运费调运。315632伏格尔法(Vogel)——差额法：315632运输问题-课件《运筹学》第三章运输问题Slide711）分别计算出各行和各列的最小运费和次最小运费的差额，填入表格的最右列和最下行。2）从行或列差额中选出最大者，选择它所在行或列中的最小元素。B2列中的最小元素是4，可确定A3的产品先满足B2的需要，同时将B2列运价划去。3）对未划去的元素再分别计算出各行、各列的最小运费和次最小运费的差额，重新填入表格的最右列和最下行。重复1）2），直到找到初始调运方案。总运费为85元。伏格尔法给出的初始解比用最小元素法给出的更接近最优解。本例用伏格尔法给出的初始解就是最优解。《运筹学》《运筹学》第三章运输问题Slide722、调运方案的检验判别的方法是计算空格（非基变量）的检验数，若所有的检验数都大于等于0，为最优解。1）闭环回路法：在给出的初始调运方案表上，从每一空格出发找一条闭环回路，它是以某空格为起点，用水平或垂直线向前划，每碰到一数字格转90°后（回路的转角点必须是一个基变量），继续前进，直到回到起始空格为止。从每一空格出发一定存在且只有唯一的闭环回路。从空格开始加减闭环各个顶点的运输单价，可得每个空格对应的检验数。《运筹学》314633314633《运筹学》第三章运输问题Slide74闭环回路计算检验数的经济解释为：从任一空格出发，如(A1,B1)，若让A1的产品调运1吨给B1，为了保持产销平衡，就要依次作调整：在(A2,B1)处减少1吨，在(A2,B3)处增加1吨，在(A1,B3)处减少1吨，即构成了以空格(A1,B1)为起点的闭环回路。调整后的方案使运费变成(+1)×3＋(－1)×1＋(+1)×2＋(－1)×3＝1（元）这就是(A1,B1)的检验数。当检验数还存在负数时，说明原方案还不是最优解。用闭环回路求检验数,当产销点很多时,这种计算很繁琐。2）乘数法（位势法）：乘数法的原理是对偶理论。《运筹学》运输问题对偶问题σij与原问题有什么关系？

由对偶性质，σij是原问题变量xij的检验数。

当xij是基变量时，σij=0，此时有由此求出Ui和Vj，再代回（*）式求非基变量的σij（空格检验数）P93-94运输问题对偶问题σij与原问题有什么关系？P93-94基变量：X13U1+V3=C13=3X14U1+V4=C14=10X21U2+V1=C21=1X23U2+V3=C23=2X32U3+V2=C32=4X34U3+V4=C34=5设U1＝0，则V3=3,U2=-1,V1=2,V4=10,U3=-5,V2=9非基变量：C11－U1－V1=3－0－2＝1C12－U1－V2＝11－0－9＝2C22－U2－V2=9＋1－9＝1C24－U2－V4＝8＋1－10＝－1C31－U3－V1=7+5－2＝10C33－U3－V3=10＋5－3＝12基变量：3、调整改进的闭环回路方法——迭代若有两个或两个以上的负检验数时，一般选其中最小的负检验数。以(24)格为调入格，以此格为出发点，作一闭环回路。在闭回路上进行运量调整，使选定空格处的运量尽可能地增加（即取相邻两数字格中较小的）。运量调整后，必然使某个数字格变成零。把一个变成零的数字格抹去，得新的调运方案。经检验，所有检验数都非负，故达到最优，最优方案总运费最小是85元。3、调整改进的闭环回路方法——迭代若有两个或两个以上的负检验《运筹学》第三章运输问题Slide78课堂作业：1、用表上作业法求出最优解。（最小元素法）2、用伏格尔法直接给出近似最优解。《运筹学》《运筹学》第三章运输问题Slide791、这是一个产销平衡的问题。1）初始调运方案（最小元素法）401520251025初始调运方案的总运费为420元。2）最优解的判别（闭环回路法）《运筹学》401520251025401520251025（乘数法）：基变量：X11U1+V1=C11=3X12U1+V2=C12=2X21U2+V1=C21=7X23U2+V3=C23=2X24U2+V4=C24=3X31U3+V1=C31=2设U1＝0，则V1=3,V2=2,U2=4,V3=-2,V4=-1,U3=-1非基变量：C13－U1－V3=7－0+2＝9C14－U1－V4＝6－0+1＝7C22－U2－V2=5－4－2＝-１C32－U3－V2＝5＋1－2＝4C33－U3－V3=4+1+2＝7C34－U3－V4=5+1+1＝7（乘数法）：《运筹学》第三章运输问题Slide823)调整调运方案，得新的方案。以(22)格为调入格，以此格为出发点，作一闭环回路。经检验，所有检验数都大于0，该调运方案是最优的方案。总运费为395元。401520251025151520253525《运筹学》2、用伏格尔法直接给出近似最优解。52020252010002、用伏格尔法直接给出近似最优解。5202025201000运输问题-课件《运筹学》第三章运输问题Slide85用伏格尔法直接找到了近似最优方案，总运价为305元。《运筹学》《运筹学》第三章运输问题Slide86第二种算法：用伏格尔法直接找到了近似最优方案，总运价为345元。用伏格尔法求解，是否一定要转化为产销平衡表？《运筹学》三、产销不平衡的运输问题

产销平衡表

P96例2.3：假设产地A1的产品必须全部调运出去,产地A2、A3的商品调运不出的单位存储费为2百元和1百元产大于销三、产销不平衡的运输问题产销平衡表P96例2.3：假设产运输费用：2×2+5×4+3×3+4×1+1×2=39(百元)

存储费用：2×2+2×1=6(百元)总成本：39+6=45(百元)P98例2.4销大于产运输费用：2×2+5×4+3×3+4×1+1×2=39(百销地B1、B2的需求必须全部满足，销地B3、B4每短缺1吨，发生损失费1百元、0。总成本是52百元，其中2百元是销地B3发生缺货的损失费。销地B1、B2的需求必须全部满足，销地B3、B4每短缺1吨，《运筹学》第三章运输问题Slide90例3．石家庄北方研究院有三个区，即一区、二区、三区，每年分别需要生活用煤和取暖用煤3000、1000、2000吨，由河北临城，山西孟县两处煤矿负责供应，这两处煤矿的价格相同，煤的质量也基本相同。两处煤矿能供应北方研究院的煤的数量，山西盂县为4000吨，河北临城为l500吨，由煤矿至北方研究院的单位运价(百元／吨)见下表。由于需求大于供给，经院研究平衡决定一区供应量可减少0～200吨，二区需要量应全部满足，三区供应量不少于1700吨。试求总运费最低的调运方案。《运筹学》《运筹学》第三章运输问题Slide91河北临城，山西孟县两处煤矿可以供应煤5500吨。一区、二区、三区至少需要煤5500吨。至多需要煤6000吨。一区和三区必须供应的煤分别为2800吨和1700吨。可以不供应的煤分别为200吨和300吨。产销平衡表《运筹学》《运筹学》第三章运输问题Slide92例4．设有三个化肥厂供应四个地区的农用化肥。假定等量的化肥在这些地区使用效果相同。各化肥厂年产量，各地区年需要量及从各化肥厂到各地区运送单位化肥的运价如下表所示，试求出总的运费最节省的化肥调运方案。《运筹学》《运筹学》第三章运输问题Slide93三个化肥厂共可供应化肥160吨。问：根据现有三个化肥厂的产量，地区IV

最高需求是否可以不限？最高需求是多少？160－30－70－0＝60吨四个地区对化肥的最高需求为50＋70＋30＋60＝210吨《运筹学》《运筹学》第三章运输问题Slide94四、运输问题的应用（一）生产与储存的问题

P109习题2-16某厂按合同规定须于当年每个季度末分别提供10,15,25,20台同一规格的柴油机。已知该厂各季度的生产能力及市场每台柴油机的成本如下表所示。又如果生产出来的柴油机当季不交货的，每台每积压一个季度需储存、维护费用0.2万元。要求在完成合同的情况下，做出使该厂全年生产（包括储存、维护）费用最小的决策。《运筹学》《运筹学》第三章运输问题Slide95设Xij为第i季度生产的用于第j季度交货的柴油机数实际的成本为该季度生产成本加上储存和维护费用。四个季度的生产能力为100台。而四个季度末共须提供柴油机70台。《运筹学》《运筹学》第三章运输问题Slide96例6．光明仪器厂生产电脑绣花机是以销定产的。已知1至6月份各月的生产能力、合同销量和单台电脑绣花机平均生产费用见下表。又已知上年末库存103台绣花机。加班生产机器每台增加成本1万元。《运筹学》《运筹学》第三章运输问题Slide97又如果当月生产出来的机器当月不交货，则需要运到分厂库房，每台增加运输成本0.1万元，每台机器每月的平均仓储费、维护费为0.2万元。在7、8月份销售淡季，全厂停产1个月，因此在6月份完成销售合同后还要留出库存80台。问应如何安排1~6月份的生产使总的生产(包括运输、仓储、维护)费用最少?设Xij为第i个月生产的用于第j个月交货的机器数实际的成本为该月生产成本加上运输、储存和维护费用将正常生产和加班生产分成两种不同的生产月来进行安排。六个月的生产能力为743台。而六个月末共须提供机器707台。上年末库存的103台绣花机，作为第0个月的生产供给。《运筹学》运输问题-课件《运筹学》第三章运输问题Slide99（二）调度问题例7：某航运公司承担六个港口初始A、B、C、D、E、F的四条固定航线的物资运输任务。已知各条航线的起点、终点城市及每天航班数见下表7－1。假定各条航线使用相同型号的船只，又各城市间的航程天数见表7－2。又知每条船只每次装卸货的时间各需1天，则该航运公司至少应配备多少条船，才能满足所有航线的运货需求？

表7－1《运筹学》表7－2(1)载货航程需要的周转船只数：表7－2(1)载货航程需要的周转船只数：《运筹学》