運(yùn)輸問題與指派問題講義

Chapter5運(yùn)輸問題與指派問題TransportationandAssignment

Problem

§1運(yùn)輸模型The

Transportationmodel

§2運(yùn)輸問題網(wǎng)絡(luò)模型TransportationNetwork§3

應(yīng)用實(shí)例§4指派問題Assignment

Problem

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

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

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

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

則線性規(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運(yùn)輸問題舉例實(shí)際舉例作為一個(gè)運(yùn)輸問題的P&T公司電子表格描述

運(yùn)輸問題一般模型generalThe

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

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

表示銷地Bj

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

xij

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

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)

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

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

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

數(shù)學(xué)模型為

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運(yùn)輸問題的網(wǎng)絡(luò)表示銷地產(chǎn)地B1B2B3B3供應(yīng)量aiA1675325A2842710A259101615需求量bj132197TransportationNetwork運(yùn)輸問題的網(wǎng)絡(luò)表示每一個(gè)節(jié)點(diǎn)建立一個(gè)約束方程，目標(biāo)函數(shù)為每一條箭線上的決策變量xij

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

供應(yīng)總量小于需求總量ai

＜bj

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

ai

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

子

表

格

模

型數(shù)學(xué)模型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單位利潤(rùn)顧客:1234產(chǎn)量工廠1$55$42$46$53800023718324850003295951357000最小采購(gòu)量7000300020000要求采購(gòu)量7000900060008000顧客1為最好顧客，需求必須滿足，顧客2、3也是重要顧客，最低需滿足其訂單的1/3，顧客4的訂單可以不考慮，問，在滿足上述要求的前提下，需向每一位顧客供應(yīng)多少產(chǎn)品數(shù)量，可使總利潤(rùn)最大?電子表格模型P2007000≤x11+x21+x31≤7000

3000≤x12+x22+x32≤9000

3000≤x13+x23+x33≤6000

x14+x24+x34≤8000SUM（C11：F11）一個(gè)獲獎(jiǎng)的應(yīng)用寶潔公司重新設(shè)計(jì)制造和配送體系

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

ofStorage

($thousand)MonthScheduled

InstallationsRegular

TimeOvertimeRegular

TimeOvertime11020101.081.101521530151.111.121532525101.101.11154205101.131.15Question:制定一個(gè)生產(chǎn)計(jì)劃，每月生產(chǎn)發(fā)動(dòng)機(jī)的數(shù)量，使制造和存儲(chǔ)成本最小Howmanyenginesshouldbeproducedineachofthefourmonthssothatthetotaloftheproductionandstoragecostswillbeminimized?P205SpreadsheetFormulation最優(yōu)生產(chǎn)計(jì)劃OptimalProductionatNorthernAirplaneMonth1(RT)2(RT)3(RT)3(OT)4(RT)Production201025105Installation101525020Stored10551001月份生產(chǎn)20個(gè)發(fā)動(dòng)機(jī),其中當(dāng)月裝配10個(gè),5個(gè)在2月份裝配,另5個(gè)在4月份裝配,2月份正常生產(chǎn)10個(gè)，用于當(dāng)月裝配，3月份正常生產(chǎn)25個(gè)，當(dāng)月裝配，3月加班生產(chǎn)10個(gè)用于4月分裝配，4月正常生產(chǎn)5個(gè)用于當(dāng)月裝配。米德爾城學(xué)生區(qū)域劃分MiddletownSchoolDistrictMiddletown米德爾城SchoolDistrictis開辦openingathirdhighschoolandthusneedstoredraw需要重新規(guī)劃theboundariesfortheareaofthecitythatwillbeassignedtotherespectiveschools.Thecityhasbeendividedinto9tracts區(qū)域withapproximatelyequalpopulations.Eachschoolhasaminimumandmaximumnumberofstudentsthatshouldbeassigned.Theschooldistrictmanagementhasdecidedthattheappropriateobjectiveistominimizetheaveragedistancethatstudentsmusttraveltoschool.Question:Howmanystudentsfromeachtractshouldbeassignedtoeachschool?P207DatafortheMiddletownSchoolDistrictDistance(Miles)toSchoolTract123NumberofHighSchoolStudents500400450400500450450400500Minimumenrollment1,2001,1001,000Maximumenrollment1,8001,7001,500SpreadsheetFormulation§3運(yùn)輸問題的應(yīng)用編制生產(chǎn)計(jì)劃二、生產(chǎn)與儲(chǔ)存問題例6、某廠按合同規(guī)定須于當(dāng)年每個(gè)季度末分別提供10、15、25、20臺(tái)同一規(guī)格的柴油機(jī)。已知該廠各季度的生產(chǎn)能力及生產(chǎn)每臺(tái)柴油機(jī)的成本如右表。如果生產(chǎn)出來的柴油機(jī)當(dāng)季不交貨，每臺(tái)每積壓一個(gè)季度需儲(chǔ)存、維護(hù)等費(fèi)用0.15萬元。試求在完成合同的情況下，使該廠全年生產(chǎn)總費(fèi)用為最小的決策方案。解：設(shè)xij為第i季度生產(chǎn)的第j季度交貨的柴油機(jī)數(shù)目，那么應(yīng)滿足：交貨：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)的柴油機(jī)數(shù)目看作第i個(gè)生產(chǎn)廠的產(chǎn)量；把第j季度交貨的柴油機(jī)數(shù)目看作第j個(gè)銷售點(diǎn)的銷量；成本加儲(chǔ)存、維護(hù)等費(fèi)用看作運(yùn)費(fèi)?？蓸?gòu)造下列產(chǎn)銷平衡問題：目標(biāo)函數(shù)：Minf=10.8x11+10.95x12+11.1x13+11.25x14+11.1x22+11.25x23+11.4x24+11.0x33+11.15x34+11.3x44二、生產(chǎn)與儲(chǔ)存問題例7、光明儀器廠生產(chǎn)電腦繡花機(jī)是以產(chǎn)定銷的。已知1至6月份各月的生產(chǎn)能力、合同銷量和單臺(tái)電腦繡花機(jī)平均生產(chǎn)費(fèi)用見下表：

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

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

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

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