數(shù)據(jù)模型與決策-課件chapter06-指派問題

Chapter6.TransportationandAssignmentProblems第六章.運輸問題和指派問題ThemarketingmanagerofSellmoreCompanywillbeholdingthecompany’sannualsalesconferencesoon.(塞爾默公司的營銷經(jīng)理將要主持召開一年一度的由營銷區(qū)域經(jīng)理以及銷售人員參加的銷售協(xié)商會議)指派問題SellmoreCompanyAssignmentProblemSellmoreCompanyAssignmentProblemHeishiringfourtemporaryemployees:(他雇用了四個臨時員工)Ann(安)Ian(伊恩)Joan(瓊)Sean(肖恩)Eachwillhandleoneofthefollowingfourtasks:(每一個人負責(zé)完成下面的一項任務(wù))Wordprocessingofwrittenpresentations(書面陳述的文字處理)Computergraphicsforbothoralandwrittenpresentations(制作口頭和書面陳述的計算機圖形)SellmoreCompanyAssignmentProblemSellmoreCompanyAssignmentProblemPreparationofconferencepackets,includingcopyingandorganizingmaterials(會議材料的準(zhǔn)備，包括書面材料的抄寫和組織)Handlingofadvanceandon-siteregistrationfortheconference(處理與會者的提前和當(dāng)場注冊報名)DatafortheSellmoreProblemSellmoreCompanyAssignmentProblemWhichpersonshouldbeassignedtowhichtask?哪個人應(yīng)該負責(zé)哪項工作？SpreadsheetFormulation增加0-1變量表示任務(wù)的分配TheModelforAssignmentProblemsGivenasetoftaskstobeperformedandasetofassigneeswhoareavailabletoperformthesetasks,theproblemistodeterminewhichassigneeshouldbeassignedtoeachtask.

(給定了一系列所要完成的任務(wù)以及一系列完成任務(wù)的被指派者，所需要解決的問題就是要確定出哪一個人被指派進行哪一項任務(wù))TheModelforAssignmentProblemsTofitthemodelforanassignmentproblem,thefollowingassumptionsneedtobesatisfied:(為了符合指派問題的模型，需要滿足下面的一些假設(shè))Thenumberofassigneesandthenumberoftasksarethesame.(被指派者的數(shù)量和任務(wù)的數(shù)量是相同的)Eachassigneeistobeassignedtoexactlyonetask.(每一個被指派者只完成一項任務(wù))TheModelforAssignmentProblemsEachtaskistobeperformedbyexactlyoneassignee.(每一項任務(wù)只能由一個被指派者來完成)Thereisacostassociatedwitheachcombinationofanassigneeperformingatask.(每一個被指派者和每一項任務(wù)的組合都會有一個相關(guān)的成本)Theobjectiveistodeterminehowalltheassignmentsshouldbemadetominimizethetotalcost.(問題的目標(biāo)是要確定怎樣進行指派才能使得總成本達到最小)TheNetworkRepresentation指派問題的網(wǎng)絡(luò)表示法所有指派者都按照次序排列在左邊需要完成的任務(wù)都排列在右邊箭頭代表每一個可能的指派需要選擇箭頭，從每一個被指派者指向每一項任務(wù)每一個箭頭旁邊的數(shù)字代表如果這個指派被選中的話，其成本的大小指派問題是一種特殊的運輸問題被指派者：出發(fā)地任務(wù)：目的地每一個出發(fā)地的供應(yīng)量都為1每一個目的地的需求量都為1指派問題的變形某些被指派者不能進行某些任務(wù)任務(wù)比被指派者多被指派者比任務(wù)多每一個被指派者可以被指派給多于一個的任務(wù)每一項任務(wù)可以由多個被指派者共同完成JobShop(AssigningMachinestoLocations)TheJobShopCompanyhaspurchasedthreenewmachinesofdifferenttypes.(嬌普肖普公司購買了三種不同類型的新設(shè)備)Therearefiveavailablelocationswherethemachinecouldbeinstalled.(車間里有五個不同的地點可供安裝)JobShop(AssigningMachinestoLocations)Someoftheselocationsaremoredesirableforparticularmachinesbecauseoftheirproximitytoworkcentersthatwillhaveaheavyworkflowtothesemachines.(其中某些地點比其他地點更為適合某些機器，因為他們十分接近工作中心，流入和流出這些設(shè)備的工作很多)Materials-HandlingCostDataJobShop(AssigningMachinestoLocations)Howshouldthemachinesbeassignedtolocations?設(shè)備應(yīng)該安裝到什么位置更加合理？SpreadsheetFormulation求佳產(chǎn)品公司問題再研究產(chǎn)品生產(chǎn)分解將產(chǎn)生隱性成本：額外的設(shè)置、配送和管理費用等新問題：已知如表6.6所示的數(shù)據(jù)，使把每一個工廠指派給至少一個新產(chǎn)品(每一種新產(chǎn)品只能在一個工廠生產(chǎn))的總成本最小BetterProducts(NoProductSplitting)米德爾城學(xué)區(qū)問題再研究區(qū)域5被分割的問題學(xué)生在學(xué)校間的分布不均衡的問題新問題：已知如表6.12所示的數(shù)據(jù)，當(dāng)每一