Data,ModelandDecisions數(shù)據(jù)、模型與決策Session4TransportationandAssignmentProblems運(yùn)輸與指派問題SessionTopicsTheTransportationProblem運(yùn)輸問題

TransportationProblemExample運(yùn)輸問題舉例

CharacteristicsofTransportationProblems

運(yùn)輸問題的特征

AnAward-WinningApplication

運(yùn)輸問題的一個獲獎應(yīng)用

VariantsofTransportationProblems

各種運(yùn)輸問題變體SessionTopicsTheAssignmentProblem指派問題

TheModelforAssignmentProblem

指派問題模型

VariantsofAssignmentProblem

指派問題的變形

ApplicationsofAssignmentProblem

指派問題的應(yīng)用物流中的一個普遍問題是如何以盡可能小的成本把貨物從一系列起始地（sources）（如工廠、倉庫）運(yùn)輸?shù)揭幌盗薪K點(diǎn)地（destinations）（如倉庫、顧客）TheTransportationProblem運(yùn)輸問題你怎么去分析這類問題呢？想想看！TheTransportationProblem運(yùn)輸問題2321341s2=10s3=15d1=13d2=21d3=9d4=7s1=25供應(yīng)量供應(yīng)地運(yùn)價(jià)需求量需求地6753842759106TransportationNetwork運(yùn)輸問題的網(wǎng)絡(luò)表示供應(yīng)地約束需求地約束LPModelofTransportationProblem運(yùn)輸問題線性規(guī)劃模型P&T公司是一家由家族經(jīng)營的小公司。它收購生菜并在食品罐頭廠中把它們加工成為罐頭，然后再把這些罐頭食品分銷到各地賣出去。豌豆罐頭在三個食品罐頭廠（靠近華盛頓的貝林翰；俄勒岡州的尤基尼；明尼蘇達(dá)州的艾爾貝·李）加工，然后用卡車把它們運(yùn)送到美國西部的四個分銷倉庫(加利福尼亞州的薩克拉門托；猶他州鹽湖城；南達(dá)科他州賴皮特城；新墨西哥州澳爾巴古)。TransportationProblemExample運(yùn)輸問題舉例實(shí)際舉例TransportationProblemExample運(yùn)輸問題舉例實(shí)際舉例P&T公司問題中的倉庫和加工廠位置圖

TransportationProblemExample運(yùn)輸問題舉例實(shí)際舉例作為一個運(yùn)輸問題的P&T公司電子表格描述

每一個出發(fā)地都有一定的供應(yīng)量（supply）配送到目的地，每一個目的地都有需要從一定的需求量（demand），接收從出發(fā)地發(fā)出的產(chǎn)品需求假設(shè)（TheRequirementsAssumption）可行解特性（TheFeasibleSolutionsProperty）成本假設(shè)（TheCostAssumption）整數(shù)解性質(zhì)（IntegerSolutionsProperty）CharacteristicsofTransportationProblems運(yùn)輸問題的特征需求假設(shè)（TheRequirementsAssumption）：每一個出發(fā)地都有一個固定的供應(yīng)量，所有的供應(yīng)量都必須配送到目的地。與之相類似，每一個目的地都有一個固定的需求量，整個需求量都必須由出發(fā)地滿足TheRequirementsAssumption需求假設(shè)可行解特性（TheFeasibleSolutionsProperty）：當(dāng)且僅當(dāng)供應(yīng)量的總和等于需求量的總和時(shí)，運(yùn)輸問題才有可行解TheFeasibleSolutionsProperty可行解特性成本假設(shè)（TheCostAssumption）：從任何一個出發(fā)地到任何一個目的地的貨物配送成本和所配送的數(shù)量成線性比例關(guān)系，因此這個成本就等于配送的單位成本乘以所配送的數(shù)量

TheCostAssumption成本假設(shè)整數(shù)解性質(zhì)（IntegerSolutionsProperty）：只要它的供應(yīng)量和需求量都是整數(shù)，任何有可行解的運(yùn)輸問題必然有所有決策變量都是整數(shù)的最優(yōu)解。因此，沒有必要加上所有變量都是整數(shù)的約束條件IntegerSolutionsProperty整數(shù)解性質(zhì)P&G重新設(shè)計(jì)制造和配送體系：90’S

成百上千個供應(yīng)商

50多個產(chǎn)品類別超過60個的工廠

15個配送中心超過1000個的顧客群體AnAward-WinningApplication運(yùn)輸問題的一個獲獎應(yīng)用為每個單獨(dú)的產(chǎn)品種類設(shè)計(jì)并求解運(yùn)輸問題對于針對還在運(yùn)行的工廠的每一個選擇，為每一個產(chǎn)品種類解決相應(yīng)的運(yùn)輸問題體現(xiàn)了從這些工廠運(yùn)送產(chǎn)品到配送中心或顧客區(qū)所需要的配送成本是多少。在找出最好的新生產(chǎn)和配送系統(tǒng)的過程之中解決了許多這樣的運(yùn)輸問題北美工廠數(shù)減少了20%，并且公司每年節(jié)省了2

億美元的稅前費(fèi)用AnAward-WinningApplication運(yùn)輸問題的一個獲獎應(yīng)用供應(yīng)總量超出了需求總量供應(yīng)總量小于需求總量一個目的地同時(shí)存在著最小需求和最大需求在配送中不能使用特定的出發(fā)地——目的地組合目標(biāo)是與配送量有關(guān)的總利潤最大不是成本最小VariantsofTransportationProblems各種運(yùn)輸問題變體TexagoCorp.SiteLocation特塞格選址問題實(shí)際舉例特塞格公司從油田運(yùn)輸原油到煉油廠運(yùn)輸問題的基本電子表格模型描述

TexagoCorp.SiteLocation特塞格選址問題實(shí)際舉例特塞格煉油廠每一個備選廠址所帶來的年變動成本地點(diǎn)運(yùn)輸原油的總成本（百萬美元）運(yùn)輸石油制品的總成本（十億美元）新煉油廠的運(yùn)營成本(百萬美元)總變動成本(十億美元)洛杉機(jī)8201.266202.7加爾維斯敦8601.245702.67圣路易斯10401.085302.65現(xiàn)實(shí)生活之中，我們也經(jīng)常遇到指派人員做某項(xiàng)工作的情況。指派問題的許多應(yīng)用都用來幫助管理人員解決如何為一項(xiàng)將要開展進(jìn)行的工作指派人員的問題。其他的一些應(yīng)用如為一項(xiàng)任務(wù)指派機(jī)器、設(shè)備或者是工廠TheAssignmentProblem指派問題還有哪些這樣的問題呢？想想看！指派問題的形式表述:給定了一系列所要完成的任務(wù)（tasks）以及一系列完成任務(wù)的被指派者（assignees），所需要解決的問題就是要確定出哪一個人被指派進(jìn)行哪一項(xiàng)任務(wù)TheModelforAssignmentProblem指派問題模型指派問題的假設(shè):被指派者的數(shù)量和任務(wù)的數(shù)量是相同的每一個被指派者只完成一項(xiàng)任務(wù)每一項(xiàng)任務(wù)只能由一個被指派者來完成每個被指派者和每項(xiàng)任務(wù)的組合有一個相關(guān)成本目標(biāo)是要確定怎樣進(jìn)行指派才能使得總成本最小TheModelforAssignmentProblem指派問題模型VariantsofAssignmentProblem指派問題的變形指派問題的變形:有一些被指派者并不能進(jìn)行某一些的任務(wù)任務(wù)比被指派者多被指派者比要完成的任務(wù)多每個被指派者可以同時(shí)被指派給多于一個的任務(wù)每一項(xiàng)任務(wù)都可以由多個被指派者共同完成ApplicationsofAssignmentProblem指派問題的應(yīng)用

在各個地點(diǎn)分派設(shè)備

指派工廠生產(chǎn)產(chǎn)品設(shè)計(jì)學(xué)生入學(xué)區(qū)域

AssigningMachinestoLocations各個地點(diǎn)分派設(shè)備為什么不需要0-1條件？AssigningPlantstoProducts指派工廠生產(chǎn)產(chǎn)品求佳產(chǎn)品公司問題指派問題變形的電子表格模型

DesigningSchoolAttendanceZones設(shè)計(jì)學(xué)生入學(xué)區(qū)域米德爾城學(xué)區(qū)問題指派問題變形的電子表格模型

SessionSummary本講小結(jié)小結(jié)運(yùn)輸問題考慮（確實(shí)的或是比喻的）從出發(fā)地運(yùn)送貨物到目的地。每一個出發(fā)地都有一個固定的供應(yīng)量，每一個目的地都有一個固定的需求量指派問就要處理應(yīng)當(dāng)將哪一項(xiàng)任務(wù)指派給哪一個被指派者，才能使完成這些任務(wù)的總達(dá)到最小把可能會