SupposetherearethreeoriginsA1,A2,A3,andfourdestinationsB1,B2,B3,B4,totransportacertaincmmodity，weknowtheamountofavailablesupplyanddemandandthetransportingcost,howshallwetransporttominimizethetotalcost?Chapter3TransportationProblem1.OptimizationmodelfortransportationproblemThetransportationproblemwhichdemandequalssupplyanditsoptimizationmodelThetransportationproblemwhichdemandequalssupplyoptimizationmodelAetnaSchoolofManagement,S.J.T.U.AllRightsReserved,RenJianBiao,2019Session4TransportationandAssignmentProblems運(yùn)輸與指派問(wèn)題

renjbonline.sh

renjb.home.物流中的一個(gè)普遍問(wèn)題是如何以盡可能小的成本把貨物從一系列起始地（sources）（如工廠、倉(cāng)庫(kù)）運(yùn)輸?shù)揭幌盗薪K點(diǎn)地（destinations）（如倉(cāng)庫(kù)、顧客）TheTransportationProblem運(yùn)輸問(wèn)題你怎么去分析這類問(wèn)題呢？想想看！產(chǎn)地銷地產(chǎn)量bi需求量ai決策變量供應(yīng)量Xij單位運(yùn)價(jià)Cij第三章：運(yùn)輸問(wèn)題（1）---產(chǎn)銷平衡運(yùn)輸問(wèn)題AetnaSchoolofManagement,S.J.T.U.AllRightsReserved,RenJianBiao,2019Session4TransportationandAssignmentProblems運(yùn)輸與指派問(wèn)題

renjbonline.sh

renjb.home.P&T公司是一家由家族經(jīng)營(yíng)的小公司。它收購(gòu)生菜并在食品罐頭廠中把它們加工成為罐頭，然后再把這些罐頭食品分銷到各地賣出去。豌豆罐頭在三個(gè)食品罐頭廠（靠近華盛頓的貝林翰；俄勒岡州的尤基尼；明尼蘇達(dá)州的艾爾貝·李）加工，然后用卡車把它們運(yùn)送到美國(guó)西部的四個(gè)分銷倉(cāng)庫(kù)(加利福尼亞州的薩克拉門托；猶他州鹽湖城；南達(dá)科他州賴皮特城；新墨西哥州澳爾巴古)。TransportationProblemExample運(yùn)輸問(wèn)題舉例實(shí)際舉例這段時(shí)間公司成本正迅速增長(zhǎng)而利潤(rùn)沒(méi)有得到同樣增長(zhǎng)。道格拉斯對(duì)配送經(jīng)理說(shuō)：豌豆罐頭的運(yùn)輸成本，幾年前是100，000美元，而上季度已漲到178，000美元。配送經(jīng)理：司機(jī)要價(jià)太高，我們正打算重新雇傭司機(jī)，成本會(huì)下降到165，000美元。道格拉斯：可否從另外角度看問(wèn)題。你是不是從我們?nèi)齻€(gè)罐頭廠把豌豆罐頭運(yùn)到我們的四個(gè)倉(cāng)庫(kù)中？可以請(qǐng)管理科學(xué)小組生成運(yùn)輸計(jì)劃。

書P189公司目前的做法：1。罐頭廠貝林翰離倉(cāng)庫(kù)最遠(yuǎn)，所以把它的產(chǎn)品送到離它最近的一個(gè)倉(cāng)庫(kù)，也就是薩克拉門托倉(cāng)庫(kù)，若有剩余送到鹽湖城倉(cāng)庫(kù)。2。因?yàn)榘臓柊凸艂}(cāng)庫(kù)離罐頭廠最遠(yuǎn)，所以將離它最近的罐頭廠（艾爾貝·李罐頭廠）的產(chǎn)品運(yùn)到澳爾巴古倉(cāng)庫(kù)，如果還有剩余的化，若有剩余，運(yùn)到賴皮特城倉(cāng)庫(kù)。3。用尤基尼罐頭廠滿足其它倉(cāng)庫(kù)的剩余需求。

書P191罐頭廠1：貝林翰罐頭廠2：尤基尼罐頭廠3：艾爾貝.李倉(cāng)庫(kù)3：賴皮特城倉(cāng)庫(kù)2：鹽湖城倉(cāng)庫(kù)1：薩克拉門托倉(cāng)庫(kù)4：澳爾巴古書P189表一：P&T公司的運(yùn)輸數(shù)據(jù)表

罐頭廠產(chǎn)量倉(cāng)庫(kù)分配量貝林翰75薩克拉門托80尤基尼125鹽湖城65艾爾貝·李100賴皮特城70

澳爾巴古85合計(jì)300合計(jì)300書P191表二：P&T公司的運(yùn)輸計(jì)劃

至從倉(cāng)庫(kù)薩克拉門托鹽湖城賴皮特城澳爾巴古罐頭廠貝林翰750

尤基尼56555

艾爾貝·李

1585表三：P&T公司的單位卡車運(yùn)輸成本

至從

倉(cāng)庫(kù)

薩克拉門托鹽湖城賴皮特城澳爾巴古罐頭廠

貝林翰464513654867尤基尼352416690791艾爾貝·李995682388685因而：公司目前做法的運(yùn)輸成本：總的運(yùn)輸成本==75*464+5*352+65*416+55*69015*388+85*685=165，595（美元）

管理科學(xué)小組要做的是要做的是檢查當(dāng)前運(yùn)輸計(jì)劃是否最優(yōu)，研究用運(yùn)輸問(wèn)題解的方案是否會(huì)更節(jié)約成本。建立該問(wèn)題的運(yùn)輸問(wèn)題模型：

最小化成本=464x11+513x12+654x13+867x14+352x21+416x22+690x23+791x24+995x31+682x32+388x33+685x34

約束條件x11+x12+x13+x14=75x21+x22+x23+x24=125x31+x32+x33+x34=100x11+x21+x31=80x12+x22+x32=65x13+x23+x33=70x14+x24+x34=85表四：P&T公司的運(yùn)輸問(wèn)題的最優(yōu)解

至從

倉(cāng)庫(kù)

薩克拉門托鹽湖城賴皮特城澳爾巴古罐頭廠

貝林翰020055尤基尼804500艾爾貝·李007030計(jì)算機(jī)計(jì)劃總運(yùn)輸成本手工計(jì)劃總的運(yùn)輸成本==75*464+5*352+65*416+55*69015*388+85*685=165，595（美元）計(jì)算機(jī)計(jì)劃總運(yùn)輸成本=20*513+55*867+80*352+45*416+70*388+30*685=152，535美元比當(dāng)前計(jì)劃相比減少了13060美元。

薩克拉門鹽湖城賴皮特城澳爾巴古罐頭廠

貝林翰75464，0，7551320，6540，86755，尤基尼12535280，541645，656900，557910，艾爾貝·李1009950，6820，38870，1568530，851。人工規(guī)則的確很好的照顧了貝林翰和澳爾巴古的利益，但它卻使尤基尼和艾爾貝·李的利益大大受損。而后兩個(gè)廠的產(chǎn)量都多于前者。2。雖然人工規(guī)則所在行和列都選了最小值，但沒(méi)有選全局最小值，造成了局部最優(yōu)，全局受損。倉(cāng)庫(kù)薩克拉門托鹽湖城賴皮特城澳爾巴古罐頭廠貝林翰46451365486775尤基尼352416690791125艾爾貝·李99568238868510080657085倉(cāng)庫(kù)薩克拉門托鹽湖城賴皮特城澳爾巴古罐頭廠貝林翰46451365486775尤基尼35280416690791125艾爾貝·李99568238868510080657085倉(cāng)庫(kù)薩克拉門托鹽湖城賴皮特城澳爾巴古罐頭廠貝林翰46451365486775尤基尼3528041669079112545艾爾貝·李9956823887068510080657085倉(cāng)庫(kù)薩克拉門托鹽湖城賴皮特城澳爾巴古罐頭廠貝林翰46451365486775尤基尼352804164569079112545艾爾貝·李995682388706851003080657085倉(cāng)庫(kù)薩克拉門托鹽湖城賴皮特城澳爾巴古罐頭廠貝林翰4645132065486775尤基尼352804164569079112545艾爾貝·李99568238870685100308065207085倉(cāng)庫(kù)薩克拉門托鹽湖城賴皮特城澳爾巴古罐頭廠貝林翰46451320654867557555尤基尼352804164569079112545艾爾貝·李9956823887068530100308065207085一老板有3工廠生產(chǎn)甲產(chǎn)品銷往4個(gè)地區(qū)，求運(yùn)費(fèi)最少？銷地B1銷地B2銷地B3銷地B4產(chǎn)量產(chǎn)地A13元/噸113107噸產(chǎn)地A218284產(chǎn)地A3741059銷量3噸656練習(xí)題思路：首先考慮運(yùn)費(fèi)最少的對(duì)應(yīng)的產(chǎn)地和銷地書P167例1：求佳公司決定使用三個(gè)有生產(chǎn)余力的工廠進(jìn)行四種新產(chǎn)品的生產(chǎn)制造。每單位產(chǎn)品需要等量的工作，所以工廠的有效生產(chǎn)能力以每天生產(chǎn)的任意種產(chǎn)品的數(shù)量來(lái)衡量。表的最后一行給出了要求的產(chǎn)品生產(chǎn)率（每天的產(chǎn)品數(shù)量），以滿足計(jì)劃的銷售量。每種產(chǎn)品在不同工廠中的單位成本有差異。重慶百貨大樓股份有限公司物流優(yōu)化配送系統(tǒng)重慶百貨大樓股份有限公司物流優(yōu)化配送系統(tǒng)指派問(wèn)題(assignmentproblem)重慶移動(dòng)公司基站維護(hù)外包問(wèn)題的分析及對(duì)策基站外包問(wèn)題解析實(shí)際維護(hù)工作中，結(jié)合重慶市行政劃分和重慶移動(dòng)公司網(wǎng)絡(luò)結(jié)構(gòu)特點(diǎn)，分成了北碚片區(qū)(A1)、永川片區(qū)(A2)、萬(wàn)州片區(qū)(A3)、黔江片區(qū)(A4)、城區(qū)片區(qū)(A5)、涪陵片區(qū)(A6)六個(gè)片區(qū)進(jìn)行代維工作開展。重慶移動(dòng)公司基站代維現(xiàn)狀及問(wèn)題城區(qū)北碚永川涪陵萬(wàn)州黔江城區(qū)涪陵北碚永川萬(wàn)州黔江公司1公司2公司3公司4Optimizationmodelforassigmentproblem0－1整數(shù)規(guī)劃應(yīng)用－－指派問(wèn)題(P128)英日德俄

甲乙丙丁

2151341041415914161378119第五章：0-1整數(shù)規(guī)劃英日德俄

甲乙丙丁

2151341041415914161378119注意到：1從人來(lái)看，如果B不作日語(yǔ)，損失特別大62從事來(lái)看，如果英語(yǔ)不分配給甲，損失特別大50－1整數(shù)規(guī)劃應(yīng)用－－指派問(wèn)題(P128)原理：從人的角度思考……..考慮人最適合的工作從工作的角度思考…….考慮工作最適合的人英日德俄

甲乙丙丁

2151341041415914161378119各行都減去這一行的最小值，得到的0表示這個(gè)0所在的行對(duì)應(yīng)的人最適合的工作是這個(gè)0所在的列對(duì)應(yīng)的事這一列有三個(gè)0，表示這一列的事有三個(gè)人適合作行最小值英日德俄

甲乙丙丁

01311260101105740142第五章：0-1整數(shù)規(guī)劃指派問(wèn)題第一步:{各行元素}—{該行行最小}{各列元素}—{該列列最小}本題有n個(gè)獨(dú)立的0元素則已得最優(yōu)解

各列都減去這一列的最小值，得到的0表示這個(gè)