第五讲 运输问题续

第五讲运输问题（续）目标规划表4-3运输问题数据表1.运输问题模型及有关概念销地产地B1B2…Bn产量A1A2┇Amc11c12…c1nc21c22…c2n┇┇┇┇cm1cm2…cmns1s2┇sm销量d1d2…dn设xij为从产地Ai运往销地Bj的运输量，根据这个运输问题的要求，可以建立运输变量表（表4-4）。表4-4运输问题变量表1.运输问题模型及有关概念销地产地B1B2…Bn产量A1A2┇Amx11x12…x1nx21x22…x2n┇┇┇xm1xm2…xmns1s2┇sm销量d1d2…dnmnMinf=cijxij（4-1）i=1j=1ns.t.xij≤sii=1,2,…,m（4-2）j=1mxij≤(=,≥)djj=1,2,…,n（4-3）i=1xij≥0(i=1,2,…,m;j=1,2,…,n)（4-4）1.运输问题模型及有关概念于是得到下列一般运输问题的模型：在模型（4-1）—（4-4）中，式（4-2）为m个产地的产量约束；式（4-3）为n个销地的销量约束。mnMinf=cijxiji=1j=1ns.t.xij=sii=1,2,…,m(4-5)j=1mxij=djj=1,2,…,n(4-6)i=1xij≥0(i=1,2,…,m;j=1,2,…,n)1.运输问题模型及有关概念对于产销平衡问题，可得到下列运输问题的模型：1.运输问题模型及有关概念基本可行解是否最优解结束换基是否图4-1运输问题的求解思路——表上作业法1.运输问题模型及有关概念销地产地B1B2…Bn产量A1c11x11c12x12…c1nx1na1A2c21x21c22x22…c2nx2na2┇┇┇┇┇Amcm1xm1cm2xm2…cmnxmnam销量b1b2…bnA的秩为m+n-1，基变量共有m+n-1个。运输问题的m+n-1个变量构成基变量的充分必要条件是不含闭回路。特点运输问题基变量的1.运输问题模型及有关概念2.运输问题求解—表上作业法一、初始基本可行解的确定西北角法：最小元素法：求检验数的方法:闭回路法位势法二、基本可行解的最优性检验2.运输问题求解—表上作业法表4-10以非基变量x22为起始顶点的闭回路销地产地B1B2B3B4产量3[]11[]341037139[]218[]47[]4610[]539销量365620(产销平衡)A1A2A39–2+3–10+5–4＝1,总的运费增加1个单位销地产地B1B2B3B4产量A13[1]11[2]341037A2139[1]218[-1]4A37[10]4610[12]539销量365620(产销平衡)表4-11初始基本可行解及检验数2.运输问题求解—表上作业法位势法2.位势法位势：设对应基变量xij的m+n-1个ij，存在ui,vj满足ui+vj=cij，i=1,2…,m;j=1,2…,n.称这些ui,vj为该基本可行解对应的位势。注.由于有m+n个变量（ui,vj），m+n-1个方程（基变量个数），故有一个自由变量，位势不唯一。利用位势求检验数：ij=cij-ui-vji=1,…,m;j=1,…,n2.运输问题求解—表上作业法前例，位势法求检验数：step1从任意基变量对应的cij开始,任取ui或vj，然后利用公式cij=ui+vj依次找出m+n个ui,vj从c14=10开始step2计算非基变量的检验数ij=cij-ui-vj；填入圆圈内2.运输问题求解—表上作业法2.运输问题求解—表上作业法当非基变量的检验数出现负值时，则表明当前的基本可行解不是最优解。在这种情况下，应该对基本可行解进行调整，即找到一个新的基本可行解使目标函数值下降，这一过程通常称为换基(或主元变换)过程。2.运输问题求解—表上作业法三、求新的基本可行解（1）选负检验数中最小者rk，那么xrk为主元，作为进基变量（上页图中x24）;（2）以xrk为起点找一条闭回路，除xrk外其余顶点必须为基变量格（上页图中的回路）;2.运输问题求解—表上作业法在运输问题的表上作业法中，换基的过程是如下进行：（3）为闭回路的每一个顶点标号，xrk为1，沿一个方向（顺时针或逆时针）依次给各顶点标号；（4）求=Min{xijxij对应闭回路上的偶数标号格}=xpq那么确定xpq为出基变量，为调整量；2.运输问题求解—表上作业法（5）对闭回路的各奇标号顶点调整为：xij+，对各偶标号顶点调整为：xij-，特别xpq-=0，xpq变为非基变量。重复(2)、(3)步，直到所有检验数均非负，得到最优解。2.运输问题求解—表上作业法2.表上作业法ij≥0，得到最优解x13=5,x14=2,x21=3,x24=1,x32=6,x34=3,其余xij=0;最优值：f*=3×5+10×2+1×3+8×1+4×6+5×3=85作业：四、产销不平衡问题的处理在实际中遇到的运输问题常常不是产销平衡的，而是下列的一般运输问题模型mnMinf=cijxij（4-1）i=1j=1ns.t.xij≤sii=1,2,…,m（4-2）j=1mxij≤(=,≥)djj=1,2,…,n(4-3）i=1xij≥0(i=1,2,…,m;j=1,2,…,n)（4-4）2.运输问题求解—表上作业法我们已经介绍过，可以通过增加虚设产地或销地（加、减松弛变量）把问题转换成产销平衡问题，下面分别来讨论。1.产量大于销量的情况mn考虑sidj的运输问题，得到的数学模i=1j=1型为2.运输问题求解—表上作业法2.运输问题求解—表上作业法mnMinf=cijxiji=1j=1ns.t.xij≤sii=1,2,…,mj=1mxij=djj=1,2,…,ni=1xij≥0(i=1,2,…,m;j=1,2,…,n)只要在模型中的产量限制约束（前m个不等式约束）中引入m个松弛变量xin+1i=1,2,…,m即可，变为：nxij+xin+1=sii=1,2,…，mj=1然后，需设一个销地Bn+1,它的销量为：mnbn+1=si-dji=1j=12.运输问题求解—表上作业法这里，松弛变量xin+1可以视为从产地Ai运往销地Bn+1的运输量，由于实际并不运送，它们的运费为cin+1=0i=1,2,…,m。于是，这个运输问题就转化成了一个产销平衡的问题。2.运输问题求解—表上作业法例4.2:某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？2.运输问题求解—表上作业法解：增加一个虚设的销地运输费用为02.运输问题求解—表上作业法2.销量大于产量的情况mn考虑sidj的运输问题，得到的数学模型为i=1j=12.运输问题求解—表上作业法mnMinf=cijxiji=1j=1ns.t.xij=sii=1,2,…,mj=1mxij≤djj=1,2,…,ni=1xij≥0(i=1,2,…,m;j=1,2,…,n)只要在模型中的产量限制约束（后n个不等式约束）中引入n个松弛变量xm+1jj=1,2,…,n即可，变为：mxij+xm+1j=djj=1,2,…，mi=1然后，需设一个产地Am+1,它的销量为：nmam+1=dj-sij=1i=12.运输问题求解—表上作业法这里，松弛变量xm+1j可以视为从产地Am+1运往销地Bj的运输量，由于实际并不运送，它们的运费为cm+1j=0j=1,2,…,n。于是，这个运输问题就转化成了一个产销平衡的问题。2.运输问题求解—表上作业法例4.3:某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？2.运输问题求解—表上作业法解：增加一个虚设的产地运输费用为02.运输问题求解—表上作业法例4.4:石家庄北方研究院有一、二、三，三个区。每年分别需要用煤3000、1000、2000t，由河北临城、山西盂县两处煤矿负责供应，价格、质量相同。供应能力分别为1500、4000t，运价如下表。由于需大于供，经院研究决定一区供应量可减少0—300t，二区必须满足需求量，三区供应量不少于1700t，试求总费用为最低的调运方案。3.运输问题的应用解:根据题意，作出产销平衡与运价表：取M代表一个很大的正数，其作用是强迫相应的x31、x33、x34取值为0。3.运输问题的应用生产与储存问题例4.7:光明仪器厂生产电脑绣花机是以销定产的。已知1至6月份各月的生产能力、合同销量和单台电脑绣花机平均生产费用见下表：正常生产能力/台加班生产能力/台销量/台单台费用/万元1月份6010104152月份501075143月份902011513.54月份10040160135月份10040103136月份80407013.53.运输问题的应用已知上年末库存103台绣花机，如果当月生产出来的机器当月不交货，则需要运到分厂库房，每台增加运输成本0.1万元,每台机器每月的平均仓储费、维护费为0.2万元。在7--8月份销售淡季，全厂停产1个月，因此在6月份完成销售合同后还要留出库存80台。加班生产机器每台增加成本1万元。问应如何安排1--6月份的生产，可使总的生产费用（包括运输、仓储、维护）最少？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月份加班生产情况。3.运输问题的应用1月2月3月4月5月6月虚销地正常产量加班产量00.30.50.70.91.11.3010311515.315.515.715.916.10601’1616.316.516.76.917.10102M1414.314.514.714.90502’M1515.315.515.715.90103MM13.513.814.014.20903’MM14.514.815.015.20204MMM13.013.313.501004’MMM14.014.314.50405MMMM13.013.301005’MMMM14.014.30406MMMMM13.50806’MMMMM14.5040销量1047511516010315036产销平衡与运价表：三、转运问题:原运输问题上增加若干转运站。运输方式有：产地转运站、转运站销地、产地产地、产地销地、销地转运站、销地产地等。3.运输问题的应用例4.9:某公司有A1、A2、A3三个分厂生产某种物质，分别供应B1、B2、B3、B4四个地区的销售公司销售。假设质量相同，有关数据如下表：B1B2B3B4产量A13113107A219284A3741059销量3656和=203.运输问题的应用试求总费用为最少的调运方案。假设：1、每个分厂的物资不一定直接发运到销地,可以从其中几个产地集中一起运；2、运往各销地的物资可以先运给其中几个销地，再转运给其他销地；3、除产销地之外，还有几个中转站，在产地之间、销地之间或在产地与销地之间转运。运价如下表：3.运输问题的应用3.运输问题的应用A1A2A3T1T2T3T4B1B2B3B4A1132143311310A21---35---21928A33---1---2374105T12311322846T215---1114527T34---23121824T43232121---26B13172411142B21194858---121B332104222423B410856746213解：把此转运问题转化为一般运输问题：1.把所有产地、销地、转运站都同时看作产地和销地；2.运输表中不可能方案的运费取作M，自身对自身的运费为0；3