運輸問題與指派問題講義

Chapter5運輸問題與指派問題TransportationandAssignment

Problem

§1運輸模型The

Transportationmodel

§2運輸問題網(wǎng)絡模型TransportationNetwork§3

應用實例§4指派問題Assignment

Problem

物流中的一個普遍問題是如何以盡可能小的成本把貨物從一系列起始地（sources）（如工廠、倉庫）運輸?shù)揭幌盗薪K點地（destinations）（如倉庫、顧客）運輸問題TheTransportationProblem想想看！如何分析這類問題§1運輸問題模型實例TheP&TCompany

分配網(wǎng)絡P189P&T公司是一家由家族經(jīng)營的小公司。它收購生菜并在食品罐頭廠中把它們加工成為罐頭，然后再把這些罐頭食品分銷到各地賣出去。豌豆罐頭在三個食品罐頭廠（靠近華盛頓的貝林翰；俄勒岡州的尤基尼；明尼蘇達州的艾爾貝·李）加工，然后用卡車把它們運送到美國西部的四個分銷倉庫(加利福尼亞州的薩克拉門托；猶他州鹽湖城；南達科他州賴皮特城；新墨西哥州澳爾巴古)P&TCompanyDistributionProblem貝林翰罐頭工廠尤基尼工廠艾爾貝.李工廠薩克拉門托倉庫奧爾巴古鹽湖城P&T公司問題中的倉庫和加工廠位置圖賴皮特澳爾巴古相關數(shù)據(jù)ShippingDataCanneryOutput產(chǎn)量Warehouse分配量AllocationBellingham75truckloadsSacramento80truckloadsEugene125truckloadsSaltLakeCity65truckloadsAlbertLea100truckloadsRapidCity70truckloadsTotal300truckloadsAlbuquerque85truckloadsTotal300truckloads運輸成本perTruckload

Warehouse倉庫From\To薩克拉門托鹽湖城賴皮特澳爾巴古罐頭廠貝林翰$464$513$654$867尤基尼352416690791艾爾貝.李995682388685總產(chǎn)量=總的需求量=300車，產(chǎn)銷平衡線性規(guī)劃模型設Letxij=從罐頭廠i

運往倉庫j卡車數(shù)thenumberoftruckloadstoshipfromcanneryitowarehousej(i=1,2,3分別表示貝林翰罐頭廠，尤基尼罐頭廠，艾爾貝.李罐頭廠；j=1,2,3,4分別表示薩克拉門托倉庫，鹽湖城倉庫，賴皮特倉庫和澳爾巴古倉庫)

則線性規(guī)劃模型為

MinimizeCost=464x11+513x12+654x13+867x14+352x21+416x22

+690x23+791x24+995x31+682x32+388x33+685x34

subjectto

Cannery1: x11+x12+x13+x14=75

Cannery2: x21+x22+x23+x24=125

Cannery3: x31+x32+x33+x34=100

Warehouse1: x11+x21+x31=80

Warehouse2: x12+x22+x32=65

Warehouse3: x13+x23+x33=70

Warehouse4: x14+x24+x34=85

xij≥0(i=1,2,3;j=1,2,3,4)TransportationProblemExample運輸問題舉例實際舉例作為一個運輸問題的P&T公司電子表格描述

運輸問題一般模型generalThe

TransportationproblemmodelTerminology術語foraTransportationProblemP&TCompanyProblemTruckloadsofcannedpeasCanneriesWarehousesOutputfromacanneryAllocationtoawarehouseShippingcostpertruckloadfromacannerytoawarehouseGeneralModelUnitsofacommodity商品單位Sources運出地Destinations目的地Supplyfromasource運出量Demandatadestination需求量Costperunitdistributedfromasourcetoadestination單位成本

一般模型表示：設A1、A2、…、Am表示m個產(chǎn)地；B1、B2、…、Bn表示n個銷地；ai表示產(chǎn)地Ai的產(chǎn)量；bj

表示銷地Bj

的銷量；cij表示把物資從產(chǎn)地Ai運往銷地Bj的單位運價,設

xij

為從產(chǎn)地Ai運往銷地Bj的運輸量，得到下列一般運輸量問題的模型：

mn

Minf=cijxij

i=1j=1

s.t.xij=

ai

i=1,2,…,m

xij=bj

j=1,2,…,n

xij≥0(i=1,2,…,m;j=1,2,…,n)

運輸問題的特征CharacteristicsofTransportationProblems運輸問題的假定數(shù)學模型為：1、需求假設：每一個出發(fā)地都有一個固定的供應量，所有的供應量都必須配送到目的地。與之相類似，每一個目的地都有一個固定的需求量，整個需求量都必須由出發(fā)地滿足2、可行解假定：當且僅當供應量的總和等于需求量的總和時，運輸問題才有可行解，且有最優(yōu)解3、成本假設：從任何一個出發(fā)地到任何一個目的地的貨物配送成本和所配送的數(shù)量成線性比例關系，因此這個成本就等于配送的單位成本乘以所配送的數(shù)量4、整數(shù)解性質：當供應量和需求量都是整數(shù)，必存在決策變量均為整數(shù)的最優(yōu)解例1、某公司從兩個產(chǎn)地A1、A2將物品運往三個銷地B1、B2、B3，各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運往各銷地每件物品的運費如下表所示，問：應如何調運可使總運輸費用最??？解：

產(chǎn)銷平衡問題：總產(chǎn)量=總銷量設xij為從產(chǎn)地Ai運往銷地Bj的運輸量，得到下列運輸量表：

運輸模型銷地產(chǎn)地B1B2B3產(chǎn)量A1x11x12x13200A2x21x22x23300銷量150150200銷地產(chǎn)地B1B2B3產(chǎn)量aiA1646200A2655300銷量bj150150200

數(shù)學模型為

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）§3

TransportationNetwork運輸問題的網(wǎng)絡表示銷地產(chǎn)地B1B2B3B3供應量aiA1675325A2842710A259101615需求量bj132197TransportationNetwork運輸問題的網(wǎng)絡表示每一個節(jié)點建立一個約束方程，目標函數(shù)為每一條箭線上的決策變量xij

乘以單位運價cij之和2321341a2=10a3=15b1=13b2=21b3=9b4=7a1=25供應量sources運價需求量Destinations需求地6753842759106x11x12x13x14A1A2A3B1B2B3B4suppliesdemands供應地約束需求地約束LPModelofTransportationProblem運輸問題線性規(guī)劃模型供應總量超出了需求總量ai＞bj

供應總量小于需求總量ai

＜bj

增加一個虛擬的生產(chǎn)地，其產(chǎn)量等于bj－

ai

，此產(chǎn)地到需求地的單位運價為零。一個目的地同時存在著最小需求和最大需求在配送中不能使用特定的出發(fā)地——目的地組合目標是與配送量有關的總利潤最大不是成本最小各種運輸問題變體VariantsofTransportationProblems求佳公司分配工廠生產(chǎn)產(chǎn)品P199求佳公司用3個有多余生產(chǎn)能力的工廠生產(chǎn)4種新產(chǎn)品，3個工廠的多余生產(chǎn)能力和4種產(chǎn)品的需求量以及每種產(chǎn)品在不同工廠的單位產(chǎn)品生產(chǎn)成本如下單位成本Product:1234生產(chǎn)能力工廠1$41$27$28$247524029—237533730272145需求量20303040Question:哪個工廠應生產(chǎn)何種產(chǎn)品及數(shù)量電

子

表

格

模

型數(shù)學模型MinimizeCost=41x11+27x12+28x13+24x14+40x21+29x22

+23x24+37x31+30x32+27x33+21x34

S.T.工廠1： x11+x12

x13+x14

≤75

工廠2: x21+x22+

x23+x24

≤75

工廠3: x31+x32+

x33+x34

≤45

產(chǎn)品1需求: x11+x21+x31=20

產(chǎn)品2需求: x12+x22+x32=30

產(chǎn)品3需求: x13+x23+x33=30

產(chǎn)品4需求: x14+x24+x34=30

xij≥0(i=1,2,3;j=1,2,3,4)耐芙迪公司選擇顧客NiftyCompanyP201單位利潤顧客:1234產(chǎn)量工廠1$55$42$46$53800023718324850003295951357000最小采購量7000300020000要求采購量7000900060008000顧客1為最好顧客，需求必須滿足，顧客2、3也是重要顧客，最低需滿足其訂單的1/3，顧客4的訂單可以不考慮，問，在滿足上述要求的前提下，需向每一位顧客供應多少產(chǎn)品數(shù)量，可使總利潤最大?電子表格模型P2007000≤x11+x21+x31≤7000

3000≤x12+x22+x32≤9000

3000≤x13+x23+x33≤6000

x14+x24+x34≤8000SUM（C11：F11）一個獲獎的應用寶潔公司重新設計制造和配送體系

DistributionSystematProctorandGambleP197MetroWater米德羅水資源(DistributingNaturalResources)MetroWaterDistrictisanagencythatadministerswaterdistributioninalargegeographicregion.Theregionisarid干旱,sowatermustbebroughtinfromoutsidetheregion.Sourcesofimportedwater:克倫坡河Colombo,塞克隆Sacron,and卡路里Calorierivers.水源來自三條河Maincustomers:CitiesofBerdoo,LosDevils,SanGo,andHollyglass.供應四個城市CostperAcreFootBerdooLosDevilsSanGoHollyglassAvailableColomboRiver$160$130$220$1705SacronRiver1401301901506CalorieRiver190200230—5Needed2541.5(million立方英尺)Question:從每條河流中引進多少水，在滿足需求的前提下，使總成本最少布都洛斯戴維斯圣哥豪利格拉斯P203SpreadsheetFormulation布都洛斯戴維斯圣哥豪利格拉斯克倫坡塞克隆卡路里北方飛機公司NorthernAirplane(ProductionScheduling)北方飛機公司生產(chǎn)商業(yè)飛機，其中最重要的步驟是生產(chǎn)飛機發(fā)動機NorthernAirplaneCompanyproducescommercialairplanes.Thelaststageinproductionistoproducethejetenginesandinstallthem.公司必須滿足第2列發(fā)動機安裝量incolumn2.Productionandstoragecostsvaryfrommonthtomonth.MaximumProductionUnitCostofProduction($million)UnitCost

ofStorage

($thousand)MonthScheduled

InstallationsRegular

TimeOvertimeRegular

TimeOvertime11020101.081.101521530151.111.121532525101.101.11154205101.131.15Question:制定一個生產(chǎn)計劃，每月生產(chǎn)發(fā)動機的數(shù)量，使制造和存儲成本最小Howmanyenginesshouldbeproducedineachofthefourmonthssothatthetotaloftheproductionandstoragecostswillbeminimized?P205SpreadsheetFormulation最優(yōu)生產(chǎn)計劃OptimalProductionatNorthernAirplaneMonth1(RT)2(RT)3(RT)3(OT)4(RT)Production201025105Installation101525020Stored10551001月份生產(chǎn)20個發(fā)動機,其中當月裝配10個,5個在2月份裝配,另5個在4月份裝配,2月份正常生產(chǎn)10個，用于當月裝配，3月份正常生產(chǎn)25個，當月裝配，3月加班生產(chǎn)10個用于4月分裝配，4月正常生產(chǎn)5個用于當月裝配。米德爾城學生區(qū)域劃分MiddletownSchoolDistrictMiddletown米德爾城SchoolDistrictis開辦openingathirdhighschoolandthusneedstoredraw需要重新規(guī)劃theboundariesfortheareaofthecitythatwillbeassignedtotherespectiveschools.Thecityhasbeendividedinto9tracts區(qū)域withapproximatelyequalpopulations.Eachschoolhasaminimumandmaximumnumberofstudentsthatshouldbeassigned.Theschooldistrictmanagementhasdecidedthattheappropriateobjectiveistominimizetheaveragedistancethatstudentsmusttraveltoschool.Question:Howmanystudentsfromeachtractshouldbeassignedtoeachschool?P207DatafortheMiddletownSchoolDistrictDistance(Miles)toSchoolTract123NumberofHighSchoolStudents500400450400500450450400500Minimumenrollment1,2001,1001,000Maximumenrollment1,8001,7001,500SpreadsheetFormulation§3運輸問題的應用編制生產(chǎn)計劃二、生產(chǎn)與儲存問題例6、某廠按合同規(guī)定須于當年每個季度末分別提供10、15、25、20臺同一規(guī)格的柴油機。已知該廠各季度的生產(chǎn)能力及生產(chǎn)每臺柴油機的成本如右表。如果生產(chǎn)出來的柴油機當季不交貨，每臺每積壓一個季度需儲存、維護等費用0.15萬元。試求在完成合同的情況下，使該廠全年生產(chǎn)總費用為最小的決策方案。解：設xij為第i季度生產(chǎn)的第j季度交貨的柴油機數(shù)目，那么應滿足：交貨：x11=10生產(chǎn)：x11+x12+x13+x14≤25

x12+x22=15x22+x23+x24≤35x13+x23+x33=25x33+x34≤30x14+x24+x34+x44=20x44≤10把第i季度生產(chǎn)的柴油機數(shù)目看作第i個生產(chǎn)廠的產(chǎn)量；把第j季度交貨的柴油機數(shù)目看作第j個銷售點的銷量；成本加儲存、維護等費用看作運費?？蓸嬙煜铝挟a(chǎn)銷平衡問題：目標函數(shù)：Minf=10.8x11+10.95x12+11.1x13+11.25x14+11.1x22+11.25x23+11.4x24+11.0x33+11.15x34+11.3x44二、生產(chǎn)與儲存問題例7、光明儀器廠生產(chǎn)電腦繡花機是以產(chǎn)定銷的。已知1至6月份各月的生產(chǎn)能力、合同銷量和單臺電腦繡花機平均生產(chǎn)費用見下表：

已知上年末庫存103臺繡花機，如果當月生產(chǎn)出來的機器當月不交貨，則需要運到分廠庫房，每臺增加運輸成本0.1萬元,每臺機器每月的平均倉儲費、維護費為0.2萬元。在7--8月份銷售淡季，全廠停產(chǎn)1個月，因此在6月份完成銷售合同后還要留出庫存80臺。加班生產(chǎn)機器每臺增加成本1萬元。問應如何安排1--6月份的生產(chǎn)，可使總的生產(chǎn)費用（包括運輸、倉儲、維護）最少？解：這個生產(chǎn)存儲問題可化為運輸問題來做?？紤]：各月生產(chǎn)與交貨分別視為產(chǎn)地和銷地1）1--6月份合計生產(chǎn)能力（包括上年末儲存量）為743臺，銷量為707臺。設一假想銷地銷量為36；2）上年末庫存103臺，只有倉儲費和運輸費，把它列為第0行；3）6月份的需求除70臺銷量外，還要80臺庫存，其需求應為70+80=150臺；4）1--6表示1--6月份正常生產(chǎn)情況，1’--6’表示1--6月份加班生產(chǎn)情況。產(chǎn)銷平衡與運價表：

用軟件解得的結果是：1-6月最低生產(chǎn)費用為8307.5萬元，每月的銷售安排如下表所示§3運輸問題的應用三、轉運問題：在原運輸問題上增加若干轉運站。運輸方式有：產(chǎn)地轉運站、轉運站銷地、產(chǎn)地產(chǎn)地、產(chǎn)地銷地、銷地轉運站、銷地產(chǎn)地等。例8、騰飛電子儀器公司在大連和廣州有兩個分廠生產(chǎn)同一種儀器，大連分廠每月生產(chǎn)400臺，廣州分廠每月生產(chǎn)600臺。該公司在上海和天津有兩個銷售公司負責對南京、濟南、南昌、青島四個城市的儀器供應。另外因為大連距離青島較近，公司同意大連分廠向青島直接供貨，運輸費用如圖，單位是百元。問應該如何調運儀器，可使總運輸費用最低？圖中產(chǎn)地：1-廣州、2-大連、轉運站3-上海、4-天津、銷地：5-南京、6-濟南、7-南昌、8-青島解：設xij為從i到j的運輸量，可得到有下列特點的線性規(guī)劃模型：目標函數(shù)：Minf=所有可能的運輸費用（運輸單價與運輸量乘積之和）約束條件：對產(chǎn)地（發(fā)點）i：輸出量-輸入量=產(chǎn)量對轉運站（中轉點）：輸入量-輸出量=0對銷地（收點）j：輸入量-輸出量=銷量例8．（續(xù)）目標函數(shù)：Minf=2x13+3x14+3x23+x24+4x28+2x35+6x36+3x37+6x38+4x45+4x46+6x47+5x48

約束條件：s.t.x13+x14≤600(廣州分廠供應量限制）

x23+x24+x28≤400(大連分廠供應量限制）-x