第五章运输问题与指派问题(MBA讲义)

Chapter5运输问题与指派问题TransportationandAssignmentProblem§1运输模型TheTransportationmodel§2运输问题网络模型TransportationNetwork§3应用实例§4指派问题AssignmentProblem物流中的一个普遍问题是如何以尽可能小的成本把货物从一系列起始地（sources）（如工厂、仓库）运输到一系列终点地（destinations）（如仓库、顾客）运输问题TheTransportationProblem想想看！如何分析这类问题§1运输问题模型实例TheP&TCompany分配网络P189P&T公司是一家由家族经营的小公司。它收购生菜并在食品罐头厂中把它们加工成为罐头，然后再把这些罐头食品分销到各地卖出去。豌豆罐头在三个食品罐头厂（靠近华盛顿的贝林翰；俄勒冈州的尤基尼；明尼苏达州的艾尔贝·李）加工，然后用卡车把它们运送到美国西部的四个分销仓库(加利福尼亚州的萨克拉门托；犹他州盐湖城；南达科他州赖皮特城；新墨西哥州澳尔巴古)P&TCompanyDistributionProblemCANNERY1BellinghamCANNERY2EugeneWAREHOUSE1SacramentoWAREHOUSE2SaltLakeCityWAREHOUSE3RapidCityWAREHOUSE4AlbuquerqueCANNERY3AlbertLea贝林翰罐头工厂尤基尼工厂艾尔贝.李工厂萨克拉门托仓库奥尔巴古盐湖城P&T公司问题中的仓库和加工厂位置图赖皮特澳尔巴古相关数据ShippingDataCanneryOutput产量Warehouse分配量AllocationBellingham75truckloadsSacramento80truckloadsEugene125truckloadsSaltLakeCity65truckloadsAlbertLea100truckloadsRapidCity70truckloadsTotal300truckloadsAlbuquerque85truckloadsTotal300truckloads运输成本perTruckloadWarehouse仓库From\To萨克拉门托盐湖城赖皮特澳尔巴古罐头厂贝林翰$464$513$654$867尤基尼352416690791艾尔贝.李995682388685总产量=总的需求量=300车，产销平衡线性规划模型设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+685x34subjecttoCannery1:x11+x12+x13+x14=75Cannery2:x21+x22+x23+x24=125Cannery3:x31+x32+x33+x34=100Warehouse1:x11+x21+x31=80Warehouse2:x12+x22+x32=65Warehouse3:x13+x23+x33=70Warehouse4:x14+x24+x34=85xij≥0(i=1,2,3;j=1,2,3,4)TransportationProblemExample运输问题举例实际举例作为一个运输问题的P&T公司电子表格描述运输问题一般模型generalTheTransportationproblemmodelTerminology术语foraTransportationProblemP&TCompanyProblemTruckloadsofcannedpeasCanneriesWarehousesOutputfromacanneryAllocationtoawarehouseShippingcostpertruckloadfromacannerytoawarehouseGeneralModelUnitsofacommodity商品单位Sources运出地Destinations目的地Supplyfromasource运出量Demandatadestination需求量Costperunitdistributedfromasourcetoadestination单位成本一般模型表示：设A1、A2、…、Am表示m个产地；B1、B2、…、Bn表示n个销地；ai表示产地Ai的产量；bj表示销地Bj的销量；cij表示把物资从产地Ai运往销地Bj的单位运价,设xij为从产地Ai运往销地Bj的运输量，得到下列一般运输量问题的模型：mnMinf=cijxiji=1j=1s.t.xij=aii=1,2,…,mxij=bjj=1,2,…,nxij≥0(i=1,2,…,m;j=1,2,…,n)运输问题的特征CharacteristicsofTransportationProblems运输问题的假定数学模型为：1、需求假设：每一个出发地都有一个固定的供应量，所有的供应量都必须配送到目的地。与之相类似，每一个目的地都有一个固定的需求量，整个需求量都必须由出发地满足2、可行解假定：当且仅当供应量的总和等于需求量的总和时，运输问题才有可行解，且有最优解3、成本假设：从任何一个出发地到任何一个目的地的货物配送成本和所配送的数量成线性比例关系，因此这个成本就等于配送的单位成本乘以所配送的数量4、整数解性质：当供应量和需求量都是整数，必存在决策变量均为整数的最优解例1、某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？解：产销平衡问题：总产量=总销量设xij为从产地Ai运往销地Bj的运输量，得到下列运输量表：运输模型销地产地B1B2B3产量A1x11x12x13200A2x21x22x23300销量150150200销地产地B1B2B3产量aiA1646200A2655300销量bj150150200数学模型为Minf=6x11+4x12+6x13+6x21+5x22+5x23s.t.x11+x12+x13=200x21+x22+x23=300x11+x21=150x12+x22=150x13+x23=200xij≥0(i=1、2；j=1、2、3）§3TransportationNetwork运输问题的网络表示销地产地B1B2B3B3供应量aiA1675325A2842710A259101615需求量bj132197TransportationNetwork运输问题的网络表示每一个节点建立一个约束方程，目标函数为每一条箭线上的决策变量xij乘以单位运价cij之和2321341a2=10a3=15b1=13b2=21b3=9b4=7a1=25供应量sources运价需求量Destinations需求地6753842759106x11x12x13x14A1A2A3B1B2B3B4suppliesdemands0xxxxxxxxxxxx13xxx12xxx13xxx22xxx19xxxx27xxxx14xxxxs.t.x6x10x9x5x7x2x4x8x3x5x7x6zmin343332312423222114131211342414332313322212312111343332312423222114131211343332312423222114131211供应地约束需求地约束LPModelofTransportationProblem运输问题线性规划模型供应总量超出了需求总量ai＞bj供应总量小于需求总量ai＜bj增加一个虚拟的生产地，其产量等于bj－ai，此产地到需求地的单位运价为零。一个目的地同时存在着最小需求和最大需求在配送中不能使用特定的出发地——目的地组合目标是与配送量有关的总利润最大不是成本最小各种运输问题变体VariantsofTransportationProblems求佳公司分配工厂生产产品P199求佳公司用3个有多余生产能力的工厂生产4种新产品，3个工厂的多余生产能力和4种产品的需求量以及每种产品在不同工厂的单位产品生产成本如下单位成本Product:1234生产能力工厂1$41$27$28$247524029—237533730272145需求量20303040Question:哪个工厂应生产何种产品及数量电子表格模型345678910111213141516BCDEFGHIUnitCostProduct1Product2Product3Product4Plant1$41$27$28$24Plant2$40$29-$23Plant3$37$30$27$21ProducedDailyProductionProduct1Product2Product3Product4AtPlantCapacityPlant103030060=75Plant20001515=75Plant320002545=45ProductsProduced20303040====TotalCostRequiredProduction20303040$3,260数学模型MinimizeCost=41x11+27x12+28x13+24x14+40x21+29x22+23x24+37x31+30x32+27x33+21x34S.T.工厂1：x11+x12x13+x14≤75工厂2:x21+x22+x23+x24≤75工厂3:x31+x32+x33+x34≤45产品1需求:x11+x21+x31=20产品2需求:x12+x22+x32=30产品3需求:x13+x23+x33=30产品4需求:x14+x24+x34=30xij≥0(i=1,2,3;j=1,2,3,4)耐芙迪公司选择顾客NiftyCompanyP201单位利润顾客:1234产量工厂1$55$42$46$53800023718324850003295951357000最小采购量7000300020000要求采购量7000900060008000顾客1为最好顾客，需求必须满足，顾客2、3也是重要顾客，最低需满足其订单的1/3，顾客4的订单可以不考虑，问，在满足上述要求的前提下，需向每一位顾客供应多少产品数量，可使总利润最大?电子表格模型P200345678910111213141516171819BCDEFGHIUnitProfitCustomer1Customer2Customer3Customer4Plant1$55$42$46$53Plant2$37$18$32$48Plant3$29$59$51$35TotalProductionShipmentCustomer1Customer2Customer3Customer4ProductionQuantityPlant17,00001,00008,000=8,000Plant20005,0005,000=5,000Plant306,0001,00007,000=7,000MinPurchase7,0003,0002,0000====TotalProfitTotalShipped7,0006,0002,0005,000$1,076,000====MaxPurchase7,0009,0006,0008,0007000≤x11+x21+x31≤70003000≤x12+x22+x32≤90003000≤x13+x23+x33≤6000x14+x24+x3