1、數(shù)據(jù)，模型和決策數(shù)據(jù)，模型和決策，第4講運輸，分配問題和網(wǎng)絡(luò)優(yōu)化，主要內(nèi)容，運輸公司的分配問題，運輸問題的特點，運輸問題變量的獲獎應(yīng)用，特塞奇公司的地址選擇問題，分配問題，模型分配問題變量分配問題的應(yīng)用，主要內(nèi)容，主要內(nèi)容：飛利浦石油公司的運輸工具替換計劃的應(yīng)用網(wǎng)絡(luò)優(yōu)化問題類型：最小成本流問題：最短路徑問題：最小生成樹問題：分配問題：運輸公司是一個小型家族企業(yè)。它購買生菜，在家里的食品罐頭廠裝罐，然后將這些罐頭食品分發(fā)到各地。該公司的主要產(chǎn)品之一是豌豆罐頭，它由三個罐頭食品工廠生產(chǎn)(華盛頓附近的貝靈漢；俄勒岡州尤金；明尼蘇達州的利雅博)，然后用卡車將它們運輸?shù)矫绹鞑康乃膫€配送倉庫(加利福尼亞

2、州的薩克拉曼多；猶他州鹽湖城；南達科他州里佩爾市；新墨西哥州奧爾巴古)。實際問題，分銷問題，實際問題，分銷問題，當前的運輸策略：1因為貝靈漢的罐頭廠離倉庫最遠，它的產(chǎn)品被運輸?shù)阶罱膫}庫。那是薩克拉門托的倉庫。如果有剩余，把它們送到鹽湖城的倉庫。因為奧爾巴古的倉庫離食品罐頭廠最遠，所以有必要將產(chǎn)品從最近的罐頭廠(易北河李罐頭廠)運輸?shù)綂W爾巴古。如果有剩余，將被運送到里佩爾市的倉庫。利用雪尼的罐頭廠來滿足其他倉庫的剩余需求。我們現(xiàn)在要做的是檢查當前的運輸計劃，看看我們是否能制定一個新的運輸計劃，并將總運輸成本降低到絕對最低。運輸是物流中常見的問題。如何以盡可能低的成本將貨物從一系列來源(如工廠和

3、倉庫)運輸?shù)揭幌盗心康牡?如倉庫和客戶)，運輸問題，運輸問題，運輸問題，運輸公司的運輸問題，運輸問題，運輸公司的運輸問題，運輸問題，運輸問題，運輸問題，運輸公司的運輸問題，運輸公司的運輸問題，運輸公司的運輸問題，Excel建模，運輸問題，每個出發(fā)地點都有一定的供應(yīng)要交付到目的地，每個目的地都需要一定的需求。需求假設(shè)、可行解屬性、成本假設(shè)、整數(shù)解屬性是從出發(fā)地點接收的，運輸問題的特征、運輸問題的特征和需求假設(shè)：每個出發(fā)地點都有固定的供應(yīng)，所有的供應(yīng)都必須交付到目的地。同樣，每個目的地都有一個固定的需求，整個需求必須由出發(fā)地來滿足。需求假說，運輸問題的特征，可行解性質(zhì)：只有當供給的總和等于需求的總

4、和時，運輸問題才有可行解，可行解和運輸問題的特征。成本假設(shè)：貨物從任何出發(fā)地點到任何目的地的配送成本與交付數(shù)量成線性比例，因此該成本等于配送單位成本乘以交付數(shù)量。成本假設(shè)、運輸問題的特征和整數(shù)解性質(zhì)：只要供給和需求是整數(shù)，任何有可行解的運輸問題都必須有一個最優(yōu)解，所有決策變量都是整數(shù)。因此，沒有必要添加所有變量都是整數(shù)的約束，整數(shù)解的性質(zhì)，運輸問題的特征，寶潔公司重新設(shè)計制造和分銷系統(tǒng)：90S，數(shù)十萬供應(yīng)商，50多個產(chǎn)品類別，60多個工廠，15個分銷中心，1000多個客戶群，運輸問題的獲獎應(yīng)用，獲獎應(yīng)用， 為每個單獨的產(chǎn)品類別設(shè)計和解決運輸問題對于每個仍在運營的工廠選擇，為每個產(chǎn)品類別解決相應(yīng)

5、的運輸問題反映了將產(chǎn)品從這些工廠運輸?shù)脚渌椭行幕蚩蛻魠^(qū)域所需的配送成本。 在尋找最佳新生產(chǎn)和分配系統(tǒng)的過程中，許多運輸問題已經(jīng)得到解決。北美的工廠數(shù)量減少了20%，公司每年節(jié)省了2億美元的稅前開支。運輸問題的獲獎申請，獲獎申請，總供給超過總需求，而總供給小于總需求。一個目的地既有最低需求也有最高需求。在分發(fā)中，不能使用特定的目的地組合。目標是最大化與分銷量相關(guān)的總利潤，而不是最小化成本。各種運輸問題都是變形的，運輸問題也是變形的。該公司決定利用三家工廠的閑置產(chǎn)能來生產(chǎn)四種新產(chǎn)品。每一個單位產(chǎn)品都需要同樣的工作量，所以一個工廠的有效生產(chǎn)能力是以每天生產(chǎn)的任何一種產(chǎn)品的數(shù)量來衡量的。秋嘉公司指定的

6、工廠生產(chǎn)產(chǎn)品，運輸問題變形。內(nèi)福迪公司選擇客戶，內(nèi)福迪公司專門在三個工廠生產(chǎn)一種產(chǎn)品。這種產(chǎn)品質(zhì)量很好，所以現(xiàn)在公司收到了很多訂單，產(chǎn)品供應(yīng)短缺。該公司還試圖擴大生產(chǎn)，甚至計劃建立一個新工廠，但這個新工廠要到明年才能投入運營。在接下來的四個月里，中國不同地區(qū)有四個潛在客戶(批發(fā)商)可能會下大訂單。客戶1是公司最好的客戶，所以它的所有訂單都應(yīng)該得到滿足；顧客2和3也是公司非常重要的顧客，所以營銷經(jīng)理認為他們的訂單至少有1/3應(yīng)該得到滿足；至于顧客4，她認為不需要特別考慮，所以她不想給這個顧客供貨。這樣，就有足夠的貨物來滿足最低數(shù)量。運輸問題變形了，內(nèi)福迪公司選擇客戶，運輸問題變形了，德洛水管站分

7、配自然資源。米德羅水管站是一個負責大面積水資源分配的組織。由于這個地區(qū)非常干燥，這個機構(gòu)需要從其他地方取水。這些迷人的水域來自三條河流：科倫坡、塞科龍和卡里弗。引入水后，該組織將其轉(zhuǎn)售給該地區(qū)的用戶。其主要客戶是布杜、羅爾斯戴維斯、圣地亞哥和霍利格拉斯的供水部門。運輸問題變形，德洛水管站分配自然資源，德洛水管站分配自然資源，電子表格，運輸問題變形，北方飛機制造公司的生產(chǎn)計劃安排，為世界各地的航空公司生產(chǎn)各種商用飛機。制造過程的最后一步是生產(chǎn)噴氣發(fā)動機，并將它們安裝到完成的飛機框架中(一個非?？焖俚牟僮?。根據(jù)該公司的一些訂單和合同，該公司將很快交付和使用相當數(shù)量的飛機。因此，有必要為未來四個月

8、這些飛機的噴氣發(fā)動機的生產(chǎn)制定一個計劃。交通問題變形，北方飛機制造公司生產(chǎn)計劃，交通問題變形，電子表格，派中學學區(qū)劃分學生入學區(qū)，中學學區(qū)已經(jīng)開設(shè)了第三所中學，有必要為每所學校重新定義本市的服務(wù)區(qū)。在初步規(guī)劃中，城市被劃分為9個區(qū)域，人口大致相同(在進一步的詳細規(guī)劃中，城市被劃分為100多個較小的區(qū)域)。表5-12給出了每個學校和每個區(qū)域之間的大致距離。最右邊的一欄顯示了明年每個地區(qū)的高中生數(shù)量(這些數(shù)字預(yù)計會最后兩行顯示了每個學?？梢园才诺淖钚『妥畲髮W生人數(shù)。交通問題變形，派中學校區(qū)劃分學生入口區(qū)域，交通問題變形，遠豐公司滿足能源需求，遠豐公司需要為新建筑建立能源系統(tǒng)。建筑的能源需求主要來自

9、以下三個方面：1)電力，2)熱水，3)建筑供暖。這三種用途(以相同單位計量)的每日能源需求分別為20單位、10單位和30單位。滿足這些需求的三種可能的能源是電力、天然氣和安裝在屋頂上的太陽能加熱裝置。屋頂?shù)拇笮Q定了太陽能加熱裝置每天可以提供30單位的能量。但是對電力和天然氣沒有這樣的限制。交通問題變形，遠豐公司滿足能源需求，交通問題變形，特塞格公司選址問題，特塞格公司，特塞格公司選址問題，特塞格公司，特塞格公司選址問題，特塞格公司和特塞格煉油廠的每一個備選地點所帶來的年度可變成本，特塞格公司選址問題，特塞格公司，一個特殊的線性規(guī)劃問題，我們也經(jīng)常遇到指派人員的問題。其他應(yīng)用，如給任務(wù)分配機器

10、、設(shè)備或工廠。給定一系列要完成的任務(wù)和一系列要完成任務(wù)的被分配者，要解決的問題是確定哪個人被分配到哪個任務(wù)。指派問題模型，指派問題假設(shè)：受指派者的數(shù)量和任務(wù)的數(shù)量是相同的。每個受理人只能完成一項任務(wù)。每個受理人只能完成每個受理人和每個任務(wù)的組合。有一個相關(guān)的成本目標來確定如何使總成本最小化。分配問題模型。塞爾默公司的營銷經(jīng)理將主持由營銷區(qū)域經(jīng)理和銷售人員參加的年度銷售談判會議。為了更好地安排這次會議，他雇傭了四名臨時工(安、伊恩、瓊和肖恩)，每個人負責完成以下任務(wù)之一：1。書面陳述的文字處理。制作口頭和書面陳述的計算機圖表。準備會議材料，包括復(fù)印和組織書面材料。4.提前和現(xiàn)場辦理參會人員登記。

11、塞爾默公司，塞爾默公司，塞爾默公司，分配問題的轉(zhuǎn)換，分配問題的轉(zhuǎn)換：有些受讓人不能執(zhí)行某些任務(wù)。受分配人比受分配人多，需要完成的任務(wù)也多。每個受理人可以同時被分配到多個任務(wù)。每個任務(wù)都可以由多個分配者完成。在每個地方分配設(shè)備來設(shè)計工廠生產(chǎn)產(chǎn)品的學生入口區(qū)域，分配問題應(yīng)用程序，在每個地方分配設(shè)備，分配問題應(yīng)用程序，要求更好的產(chǎn)品公司分配工廠來生產(chǎn)產(chǎn)品，分配問題應(yīng)用程序，米德爾頓學區(qū)設(shè)計學生入口區(qū)域并分配問題應(yīng)用程序。飛利浦石油應(yīng)用最短路徑問題模型優(yōu)化各種公路運輸車輛、卡車和貨車的運輸路線，以降低成本和提高競爭力。飛利浦石油公司的運輸工具更換計劃，沃德爾(1983)7-8月接口文章，“設(shè)備更換決策

12、和政策模型”，飛利浦石油公司，有1，500輛卡車和3，800輛卡車使用最短路徑模型建立更換策略(20年時間跨度)。每次，模型都是針對每種運輸類型求解的?？紤]的成本包括維護和運營成本、租賃成本、購買成本、政府授權(quán)費、道路稅和其他稅(投資稅、折舊)，然后制定更換策略，該策略現(xiàn)在擴展到其他設(shè)備(非運輸車輛)。飛利浦石油公司的運輸工具更換計劃，飛利浦石油公司的網(wǎng)絡(luò)優(yōu)化模型的應(yīng)用，以及網(wǎng)絡(luò)在運輸、電子和通訊網(wǎng)絡(luò)中覆蓋我們?nèi)粘Ｉ畹母鱾€方面。網(wǎng)絡(luò)計劃也被廣泛用于解決不同領(lǐng)域的各種問題，如生產(chǎn)、配送、項目規(guī)劃、選址、資源管理和財務(wù)規(guī)劃等。網(wǎng)絡(luò)計劃為描述系統(tǒng)各組成部分之間的關(guān)系提供了非常有效、直觀和概念性的幫

13、助，并廣泛應(yīng)用于科學、社會和經(jīng)濟活動的各個領(lǐng)域。網(wǎng)絡(luò)描述，網(wǎng)絡(luò)優(yōu)化問題類型，最小成本流問題，最大流問題，最短路徑問題，最小生成樹問題，基本術(shù)語，節(jié)點，供應(yīng)點，需求點，轉(zhuǎn)移點流，流守恒，弧，容量，最小成本流問題，最小成本流問題的組成：節(jié)點(供應(yīng)點，需求點，轉(zhuǎn)移點)弧(弧)目標。37860.0000000005至少一個節(jié)點是需求點。所有剩余的節(jié)點都是轉(zhuǎn)移點。4通過電弧的流量只能沿箭頭方向流動，通過電弧的最大流量取決于電弧的容量。(如果流動是雙向的，則需要用一對指向相反弧線的箭頭來表示。)，最小成本流，最小成本流假設(shè)問題，5。網(wǎng)絡(luò)中有足夠的弧來提供足夠的容量，這樣在供應(yīng)點產(chǎn)生的所有流量都可以到達需求

14、點。在單位流量成本已知的前提下，通過每個弧的流量成本與流量成正比。最小成本流問題的目標是在滿足給定需求的條件下，使通過網(wǎng)絡(luò)供應(yīng)的總成本最小。換句話說，就是通過這樣做使總利潤最大化。)，最小成本流，解的特征，具有可行解的特征：在上述假設(shè)下，當且僅當供應(yīng)點提供的總流量等于需求點所需的總流量時，最小成本流問題具有整數(shù)解的可行解的特征：只要其所有供應(yīng)、需求和弧容量都是整數(shù)值，那么任何最小成本流問題的可行解都必須具有所有流量都是整數(shù)的最優(yōu)解。電子表格模型、最小成本流和網(wǎng)絡(luò)單純形法求解無限分銷公司的最小成本流問題，在實際應(yīng)用中解決相對較大的問題時需要不同的方法。網(wǎng)絡(luò)單純形法可用于解決用單純形法無法解決的大

15、問題。Excel Solver軟件沒有網(wǎng)絡(luò)單純形法，但其他用于線性規(guī)劃的商業(yè)軟件包通常都有這種方法，最小成本流。在一些實際應(yīng)用中，國際紙業(yè)公司(Interfaces 3/4，1988)的分銷網(wǎng)絡(luò)是世界上最大的紙漿、紙張和紙制品制造商，也是木材和膠合板的主要生產(chǎn)商。擁有2000萬英畝的森林面積或其權(quán)益。分布在不同地方的林區(qū)是其分銷網(wǎng)絡(luò)的供應(yīng)點，供應(yīng)流必須經(jīng)過一系列的長轉(zhuǎn)移點：林區(qū)的倉庫客戶、木材場、鋸木廠、造紙廠、紙制品加工廠、最低成本流、一些實際應(yīng)用、馬歇爾公司分銷網(wǎng)絡(luò)中的折扣連鎖零售店(1987年7月8日)，現(xiàn)在和以前，如何使用微型計算機處理最低成本流問題。在應(yīng)用中，公司試圖優(yōu)化從供應(yīng)商到加工中心，然后從加工中心到零售店的業(yè)務(wù)流程。其中一些網(wǎng)絡(luò)有超過20，000條弧線。最小成本流量、最大流量問題和最大流量問題也與網(wǎng)絡(luò)中的流量有關(guān)，但目標不是使流量成本最小化，而是找到一種使網(wǎng)絡(luò)中的流量最大化的流量方案。1.網(wǎng)絡(luò)中的所有流都源自一個稱為源的節(jié)點，所有流都終止于另一個稱為匯的節(jié)點。(在BMZ問題中，來源和接收點分別代表工廠和配送中心。)所有其他節(jié)點都稱為轉(zhuǎn)移點。(在BMZ問題中，節(jié)點ro、BO、LI、NY和no都是過境點。3)通過每個電弧的氣流只能沿電