第五章运输问题(运筹学讲义)

Chapter5运输问题与指派问题TransportationandAssignmentProblem§1运输模型TheTransportationmodel§2运输问题表上作业法§3运输问题网络模型TransportationNetwork§4应用实例物流中的一个普遍问题是如何以尽可能小的成本把货物从一系列起始地（sources）（如工厂、仓库）运输到一系列终点地（destinations）（如仓库、顾客）运输问题TheTransportationProblem想想看！如何分析这类问题§1运输问题模型实例TheP&TCompany分配网络P189例1P&T公司是一家主要生产豌豆罐头的公司。它收购豌豆并在食品罐头厂把它们加工成为罐头，然后再把这些罐头食品分销到各地卖出去。豌豆罐头在三个食品罐头厂（靠近华盛顿的贝林翰；俄勒冈州的尤基尼；明尼苏达州的艾尔贝·李）加工，然后用卡车把它们运送到美国西部的四个分销仓库(加利福尼亚州的萨克拉门托；犹他州盐湖城；南达科他州赖皮特城；新墨西哥州澳尔巴古)P&TCompanyDistributionProblemCANNERY1BellinghamCANNERY2EugeneWAREHOUSE1SacramentoWAREHOUSE2SaltLakeCityWAREHOUSE3RapidCityWAREHOUSE4AlbuquerqueCANNERY3AlbertLea贝林翰罐头工厂尤基尼工厂艾尔贝.李工厂萨克拉门托仓库奥尔巴古盐湖城P&T公司问题中的仓库和加工厂位置图赖皮特澳尔巴古相关数据ShippingData罐头厂Output产量仓库分配量Allocation贝林翰75车萨克拉门托80车尤基尼125车盐湖城65车艾尔贝.李100车赖皮特70车总数300车澳尔巴古85车总数300车运输成本每卡车仓库Warehouse产量From\To萨克拉门托盐湖城赖皮特澳尔巴古罐头厂贝林翰$464$513$654$86775尤基尼352416690791125艾尔贝.李995682388685100需求量80657085总产量=总的需求量=300车，产销平衡x11x12x13x14x21x31x22x32x23x33x24x34线性规划模型设Letxij=从罐头厂i运往仓库j卡车数thenumberoftruckloadstoshipfromcanneryitowarehousej(i=1,2,3分别表示贝林翰罐头厂，尤基尼罐头厂，艾尔贝.李罐头厂；j=1,2,3,4分别表示萨克拉门托仓库，盐湖城仓库，赖皮特仓库和澳尔巴古仓库)则线性规划模型为MinimizeCost=464x11+513x12+654x13+867x14+352x21+416x22+690x23+791x24+995x31+682x32+388x33+685x34subjectto罐头厂1:x11+x12+x13+x14=75罐头厂2:x21+x22+x23+x24=125罐头厂3:x31+x32+x33+x34=100仓库1:x11+x21+x31=80仓库2:x12+x22+x32=65仓库3:x13+x23+x33=70仓库4:x14+x24+x34=85xij≥0(i=1,2,3;j=1,2,3,4)一般运输问题的提法：假设A1、A2、…、Am表示某物资的m个产地；B1、B2、…、Bn表示某物资的n个销地；ai表示产地Ai的产量；bj表示销地Bj的需求量；cij表示把物资从产地Ai运往销地Bj的单位运价。如果a1+a2+…+am=b1+b2+…+bn，则称该运输问题为产销平衡问题；否则，称产销不平衡。销地产地B1B2…Bn产量A1A2┇Amc11c12…c1nc21c22…c2n┇┇┇┇cm1cm2…cmna1a2┇am需求量b1b2…bn解：设xij为从产地Ai运往销地Bj的运输量对于产销平衡问题，可得到下列运输问题的模型：ijminjijxcf11minmiaxtsinjij,,2,1..1njbxjmiij,,2,11njmixij,,2,1,,2,10B1B2……BnaiA1c11[x11]c12[x12]……c1n[x1n]a1A2c21[x21]c12[x22]……c1n[x2n]a2………………………………Amcm1[xm1]cm2[xm2]……cmn[xmn]ambjb1b2……bn∑ai=∑bj这就是运输问题的数学模型。它包含m×n个变量，(m+n)个约束方程。其系数矩阵的结构比较松散，且特殊。行行nmvvvuuuxxxxxxxxxnmmnmmnn1111111111111111112121212222111211该系数矩阵中对应于变量xij的系数向量Pij，其分量中除第i个和第m+j个为1以外，其余的都为零。即Pij=(0,…,1,0,…,0,1,0,…,0)T=ei+em+j运输问题的特征CharacteristicsofTransportationProblems运输问题的假定数学模型为：1、需求假设：每一个出发地都有一个固定的供应量，所有的供应量都必须配送到目的地。与之相类似，每一个目的地都有一个固定的需求量，整个需求量都必须由出发地满足2、可行解假定：当且仅当供应量的总和等于需求量的总和时，运输问题才有可行解，且有最优解3、成本假设：从任何一个出发地到任何一个目的地的货物配送成本和所配送的数量成线性比例关系，因此这个成本就等于配送的单位成本乘以所配送的数量4、整数解性质：当供应量和需求量都是整数，必存在决策变量均为整数的最优解运输问题解中非零变量的个数不超过m+n-1个，因为m+n个约束中只有m+n-1个是独立的。基变量在迭代过程中保持为m+n-1个。用单纯形来求解运输问题，需要加m+n个人工变量，产生一个变量数为mn+m+n的线性规划，求解比较复杂，需要寻求更简便的解法。§2运输问题求解——表上作业法基本步骤初始方案的确定（1）－寻找初始方案的方法最小元素法（2）－寻找初始方案的方法最大差值法最优解判定－位势法非最优方案的改进－闭回路调整法多最优解的判断及处理方法一、初始基本可行解的确定初始基本可行解的取值要满足下面条件：①所得的变量均为非负，且变量总数恰好为m+n–1个；得到了一个初始基本可行解。否则，在剩下的运输平衡表中选下一个变量，②所有的约束条件均得到满足；1.最小元素法最小元素法是就近供应，即对单位运价最小的变量分配运输量。假定运价表中cij最小,则分配运量xij,使xij取尽可能大的值xij=Min{ai,bj}。即如果ai＞bj，则取xij＝bj，删除运价表中第j列，修改剩余产量为ai－bj。否则若bj＞ai，则取xij＝ai,删除运价表中第i行，修改剩余需求量bj－ai上述计算过程可用流程图描述如下取未划去的单元格xij,令xij=min{ai,bj}ai’=ai-xijbj’=bj-xijai’=0?划去第i行划去第j列是否bj’=0否所有行列是否均被划去是找到初始基本可行解求运输问题的初始基本可行解过程(42)例2(19)设有三座铁矿山Ai（i＝1，2，3），生产矿石，另有四个炼铁厂Bj（j＝1，2，3，4）需要矿石，各矿日产量为ai，各厂日需量为bj，以及对应的运价（单位物资的运输费用）为cij，cij由下面产销运价表给出，问：应怎样调运矿石才能使运费最小？P58B1B2B3B469127A1601361A2425134A34850302545aibj08解b1＝50＞a2＝42最小元素法（续）B1B2B3B469127A1601361A205134A3488302545aibj(30)018(42)a3＝48＞b2＝30最小元素法（续）0B1B2B3B469127A1601361A205134A318802545aibj(30)(42)(18)7b3＝25＞a3＝18最小元素法（续）B1B2B3B469127A1601361A205134A3080745aibj(30)(42)(18)(7)(8)(45)由此可以得到初始可行解为：x21=42;x32=30;x33=18;x11=8;x14=45;x13=7初始方案的运输费用为：f1=6×8+12×7+7×45+1×42+1×30+3×18=5732差值法Vogel’s法计算运价表各行各列中最小两个运价之差值最小元素法可能导致其他供销点以更高的运费分配运量。次小运费和最小运费的差额越大，说明在该处如果不能以最小运费运送，按次小运费运送的费用将很大，因此次小运费和最小运费的差额为该供应地和需求地的罚数。若罚数的值不大，当不能以最小运费安排运输量时造成的运费损失不大；反之，如果罚数的值很大，不按最小运费安排运输量时造成的运费损失很大。差值法基于这种考虑，先计算所有行和列次小运费和最小运费的差值（称为行差值和列差值），找出最大的差值，然后根据其所在的行或列的最小运费来确定运量的分配。差值法例P58B1B2B3B469127A1601361A2425134A34850302545aibj8(42)b1＝50＞a2＝48增加行差值和列差值行差值列差值10242330差值法例P58B1B2B3B469127A1601361A205134A3488302545aibj23(42)a3＝48＞b3＝25增加行差值和列差值行差值列差值1218930(25)差值法例P58B1B2B3B469127A1601361A205134A323830045aibj7(42)b2＝30＞a3＝23增加行差值和列差值行差值列差值131830(23)(25)(8)(7)(45)差值法例P58B1B2B3B469127A1601361A2425134A34850302545aibj(42)(23)(25)(8)(7)(45)由此可以得到初始可行解为：x11=8;x12=7；x14=45;x21=42;x32=23;x33=25;初始方案的运输费用为：f1=6×8+9×7+7×45+1×42+1×23+3×25=566当我们取定xij的值之后，会出现Ai的产量与Bj的需求量都改为零的情况，这时应同时划去Ai行与Bj列。既在划去xij对应一行（列），填上一个数时，也应划去xij对应列（行），在任意被划去除xij以外任一格内填上0，这时出现退化解。B1B2B3B469127A1781361A205134A3308302545aibj(30)00(42)a3＝30＝b2＝30(0)最优解的判别位势法也称对偶变量法..ijijstuvc(1),,jvjn0jiijijvuc(1),iuimjivu,111212=()(),,,,,,,jjjjBjjjTijijijijBijijijijmnijijijczcCBpcYpczcCBpcYpcuuuvvvpcuvijminjijxcf11minmiaxtsinjij,,2,1..1njbxjmiij,,2,1101212,,,;,,,ijximjn设分别表示前m个约束等式相应的对偶变量，分别表示后n个约束等式相应的对偶变量，既有对偶变量向量1212(),,,,,,,TmnYuuuvvv11maxmniijjijzaubv1212,,,;,,,imjn符号不确定对偶线性规划问题变量的检验数，jx最优解的判别位势法也称对偶变量法所谓位势法，我们对运输表上的每一行赋予一个数值，分别表示前m个约束等式相应的对偶变量，对每一列赋予一个数值分别表示后n个约束等式相应的对偶变量，则变量xij的检验数它们的数值是由基变量xij的检验数所决定的，由于基变量为m+n-1个，而需要确定的值为m+n个，因此，首先令基变量最多那行的，从而可以根据基格确定所有的值。非