1、5.1,第二講 線性規(guī)劃建模,1 運(yùn)輸問題和指派問題 2 目標(biāo)規(guī)劃 3 整數(shù)規(guī)劃 4 網(wǎng)絡(luò)最優(yōu)化問題,5.2,P j = 1, 2, 3, 4)Min成本 = $464x11 + $513x12 + $654x13 + $867x14 + $352x21 + $416x22+ $690 x23 + $791x24 + $995x31 + $682x32 + $388x33 + $685x34st罐頭加工廠1:x11 + x12 + x13 + x14 = 75罐頭加工廠2:x21 + x22 + x23 + x24 = 125罐頭加工廠3:x31 + x32 + x33 + x34 = 100

2、倉庫1:x11 + x21 + x31 = 80倉庫2:x12 + x22 + x32 = 65倉庫3:x13 + x23 + x33 = 70倉庫4:x14 + x24 + x34 = 85且 xij 0 (i = 1, 2, 3; j = 1, 2, 3, 4),5.11,整數(shù)解性質(zhì),只要它的供應(yīng)量和需求量都是整數(shù)，任何有可行解的運(yùn)輸問題必然有所有決策變量都是整數(shù)的最優(yōu)解。因此，沒有必要加上所有變量都是整數(shù)的約束條件。,5.12,耐芙迪公司 (選擇顧客),耐芙迪公司在3個(gè)工廠中專門生產(chǎn)一種產(chǎn)品. 4個(gè)顧客可能會(huì)大量訂貨。可以滿足他們最小購買需求，但是不能滿足所有的購買需求 主要是由于運(yùn)輸成

3、本上的差異，銷售一個(gè)產(chǎn)品得到的凈利潤也不同，很大程度上取決于哪個(gè)工廠供應(yīng)哪個(gè)顧客。 問題:耐芙迪應(yīng)該向每個(gè)顧客銷售多少單位的產(chǎn)品，應(yīng)該從每個(gè)工廠運(yùn)輸多少單位到每個(gè)顧客？,5.13,耐芙迪公司的數(shù)據(jù),問題:耐芙迪應(yīng)該向每個(gè)顧客銷售多少單位的產(chǎn)品，應(yīng)該從每個(gè)工廠運(yùn)輸多少單位到每個(gè)顧客？,5.14,電子表格建模,5.15,米德爾城學(xué)區(qū),米德爾學(xué)區(qū)開辦了三所中學(xué)，需要為每一所學(xué)校重新劃定這個(gè)城市內(nèi)德服務(wù)區(qū)域。 這個(gè)城市被分成了擁有大致相同數(shù)量人口德9個(gè)區(qū)域。 每個(gè)學(xué)校都有一個(gè)指派的最小和最大的學(xué)生的數(shù)量。 學(xué)區(qū)的管理者認(rèn)為劃分入學(xué)區(qū)域界限的適當(dāng)目標(biāo)是要使學(xué)生到學(xué)校的平均路程最短。. 問題: 每一個(gè)區(qū)域

4、應(yīng)該分配多少學(xué)生到每個(gè)學(xué)校？,5.16,米德爾城學(xué)區(qū)的數(shù)據(jù),5.17,電子表格建模,5.18,塞爾默公司的指派問題,塞爾默公司的營銷經(jīng)理將要主持召開一年一度的由營銷區(qū)域經(jīng)理以及銷售人員參加的銷售協(xié)商會(huì)議。 他雇傭了四個(gè)臨時(shí)工： 安 伊恩 瓊 肖恩 每一個(gè)人負(fù)責(zé)完成下面的一項(xiàng)任務(wù)： 書面陳述的文字處理. 制作口頭和書面陳述的電腦圖。 會(huì)議材料的準(zhǔn)備，包括書面材料的抄寫和組織。 處理與會(huì)者提前和當(dāng)場注冊(cè)報(bào)名。 問題:那個(gè)人應(yīng)該指派去完成哪項(xiàng)工作？,5.19,塞爾默問題的數(shù)據(jù),5.20,電子表格建模,5.21,指派問題的模型,給定了一系列所要完成的任務(wù)以及一系列完成任務(wù)的被指派者，所要解決的問題就是

5、要確定出哪一個(gè)人被指派進(jìn)行哪一項(xiàng)任務(wù)。 為了符合指派問題的模型，需要滿足下面的一些假設(shè)： 被指派者的數(shù)量和任務(wù)的數(shù)量是相同的。 每一個(gè)被指派者只完成一項(xiàng)任務(wù)。 每一項(xiàng)任務(wù)只能由一個(gè)被指派者完成。 每一個(gè)被指派者和每一項(xiàng)任務(wù)的組合都會(huì)有一個(gè)相關(guān)的成本。 問題的目標(biāo)是確定怎樣進(jìn)行指派才能使得總成本最小。,5.22,網(wǎng)絡(luò)表示法,5.23,(米德爾城學(xué)區(qū) ),5.24,2 目標(biāo)規(guī)劃,案例研究：德懷特公司德目標(biāo)規(guī)劃問題 加權(quán)目標(biāo)規(guī)劃 優(yōu)先目標(biāo)規(guī)劃,5.25,德懷特公司,德懷特公司是美國最大的電動(dòng)工具制造商之一。 公司正在準(zhǔn)備將目前的產(chǎn)品替換為新一代的產(chǎn)品，即三種新型的電動(dòng)工具。 管理層需要決定確定公司的

6、三種產(chǎn)品的組合來最好地實(shí)現(xiàn)如下的三個(gè)目標(biāo)： 至少達(dá)到1.25億美元的總利潤（凈現(xiàn)值）。 維持目前4000名員工的水平。 將投入資金限制在5500萬美元之下。,5.26,罰數(shù)權(quán)重,5.27,各種產(chǎn)品對(duì)目標(biāo)的貢獻(xiàn)數(shù)據(jù),5.28,加權(quán)目標(biāo)規(guī)劃,各種管理科學(xué)模型（線性規(guī)劃，整數(shù)規(guī)劃，非線性規(guī)劃）的普遍特征是只有一個(gè)目標(biāo)函數(shù)。 并不是所有的情況都可以做到將所有的管理目標(biāo)都集中到一個(gè)目標(biāo)函數(shù)中，管理目標(biāo)可能包括： 保持穩(wěn)定的利潤。 增加市場份額。 多樣化產(chǎn)品線。 保持穩(wěn)定的價(jià)格。 提高工人的士氣。 保持對(duì)企業(yè)的控制力。 增加公司的聲譽(yù)。 加權(quán)目標(biāo)規(guī)劃提供了一種同時(shí)滿足多個(gè)目標(biāo)的方法。,5.29,帶權(quán)目標(biāo)規(guī)

7、劃,對(duì)于加權(quán)目標(biāo)規(guī)劃，目標(biāo)是： 最小化 W =偏離目標(biāo)的帶權(quán)和。 這些權(quán)重是偏離目標(biāo)的罰數(shù)權(quán)重。 引入新的可變單元，超過的數(shù)量和低于的數(shù)量，將會(huì)測量目前的解超過或低于目標(biāo)函數(shù)多少 超過或低于目標(biāo)的可變單元格的數(shù)量是為了在如下約束下保持正確的值：達(dá)到的水平 超過的數(shù)量 +低于的數(shù)量 =目標(biāo),5.30,德懷特公司問題德加權(quán)目標(biāo)規(guī)劃建模,令Pi = 每天生產(chǎn)產(chǎn)品 i 的數(shù)量 (i = 1, 2, 3),在目標(biāo) i 之下 = 在目標(biāo) i 之下的數(shù)量 (i = 1, 2, 3),超過目標(biāo) i = 超過目標(biāo) i 的數(shù)量 (i = 1, 2, 3),Min W = 5(低于目標(biāo)1) + 2（超過目標(biāo) 2)

8、+ 4 (低于目標(biāo) 2) + 3 (超過目標(biāo) 3)st達(dá)到的水平 偏離目標(biāo)目標(biāo) 1: 12P1 + 9P2 + 15P3 (超過目標(biāo) 1) + (低于目標(biāo) 1) =125目標(biāo) 2:5P1 + 3P2 + 4P3 (超過目標(biāo) 2) + (低于目標(biāo) 2) = 40目標(biāo) 3:5P1 + 7P2 + 8P3 (超過目標(biāo) 3) + (低于目標(biāo) 3) =55且Pi 0, 低于目標(biāo) i 0, 超過目標(biāo) i 0 (i = 1, 2, 3),5.31,帶權(quán)目標(biāo)規(guī)劃的電子表格,5.32,加權(quán) vs. 優(yōu)先目標(biāo)規(guī)劃,加權(quán)目標(biāo)規(guī)劃適用于對(duì)于所有的目標(biāo)都很重要，只是重要性有一些不同，不同的重要性可以通過給每個(gè)目標(biāo)指定不

9、同的權(quán)重來描述。 優(yōu)先目標(biāo)規(guī)劃在目標(biāo)的重要性有顯著的不同時(shí)使用。 這些目標(biāo)按照他們的重要性排列。 開始集中在最重要的目標(biāo)上。 然后對(duì)第二重要的目標(biāo)做同樣的處理。 (在不妨礙第一個(gè)目標(biāo)的前提下是可能的。). 如下的目標(biāo)做同樣的處理。 (在不妨礙前面的目標(biāo)的前提下是可能的。）,5.33,優(yōu)先目標(biāo)規(guī)劃,引入一個(gè)新的可變單元格，超過的數(shù)量和低于的數(shù)量，將會(huì)用于度量目前的解超過或低于每個(gè)目標(biāo)多少。 超過可變單元格的數(shù)量和低于目標(biāo)單元格的數(shù)量是在如下的約束下維持正確的值。要達(dá)到的水平 超過的數(shù)量 + 低于的數(shù)量 = 目標(biāo) 從實(shí)現(xiàn)第一個(gè)目標(biāo)的目標(biāo)開始 (或盡可能地接近): 最小化 (超過目標(biāo)1的數(shù)量/低于目

10、標(biāo)1的數(shù)量) 繼續(xù)如下的目標(biāo)，但是保證不使前面的目標(biāo)變壞： 最小化 (超過/低于目標(biāo)2的數(shù)量)受約束于超過/低于目標(biāo)1的數(shù)量 = (在前面的步驟中達(dá)到的數(shù)量) 對(duì)所有其他的目標(biāo)重復(fù)上述步驟。,5.34,德懷特的優(yōu)先目標(biāo)規(guī)劃,目標(biāo)的優(yōu)先次序是： 總利潤（凈現(xiàn)值）不得少于1.25億美元. 避免使員工水平低于4000人。 將資金投資限制在5500萬美元以內(nèi)。 避免員工水平超過4000人。 從第一個(gè)目標(biāo)開始 (或者盡可能地接近): Min (低于目標(biāo)1) 然后，比如如果目標(biāo)1達(dá)到了 (比如，低于目標(biāo)1 = 0)，然后 Min (低于目標(biāo)2)受約束于(低于目標(biāo)1) = 0,5.35,德懷特公司問題的優(yōu)先

11、目標(biāo)規(guī)劃建模(步驟1),令Pi = 每天生產(chǎn)產(chǎn)品 i 的數(shù)量 (i = 1, 2, 3),低于目標(biāo) i = 低于目標(biāo) i 的數(shù)量 (i = 1, 2, 3),超過目標(biāo) i = 超過目標(biāo) i 的數(shù)量 (i = 1, 2, 3),Min (低于目標(biāo) 1)st達(dá)到的水平 偏差目標(biāo)目標(biāo) 1: 12P1 + 9P2 + 15P3 (超過目標(biāo)1) + (低于目標(biāo) 1) =125目標(biāo) 2:5P1 + 3P2 + 4P3 (超過目標(biāo)2) + (低于目標(biāo) 2) = 40目標(biāo) 3:5P1 + 7P2 + 8P3 (超過目標(biāo)3) + (低于目標(biāo) 3) =55且Pi 0,低于目標(biāo) i 0, 超過目標(biāo) i 0 (i =

12、 1, 2, 3),5.36,德懷特公司問題的優(yōu)先目標(biāo)規(guī)劃建模(步驟2),令Pi = 每天生產(chǎn)產(chǎn)品 i 的數(shù)量 (i = 1, 2, 3),低于目標(biāo) i = 低于目標(biāo) i 的數(shù)量 (i = 1, 2, 3),超過目標(biāo) i = 超過目標(biāo) i 的數(shù)量 (i = 1, 2, 3),Min (低于目標(biāo) 2)st達(dá)到目標(biāo)的水平 偏差目標(biāo)目標(biāo) 1: 12P1 + 9P2 + 15P3 (超過目標(biāo) 1) + (低于目標(biāo) 1) =125目標(biāo)2:5P1 + 3P2 + 4P3 (超過目標(biāo) 2) + (低于目標(biāo) 2) = 40目標(biāo)3:5P1 + 7P2 + 8P3 (超過目標(biāo) 3) + (低于目標(biāo) 3) =55(

13、低于目標(biāo) 1) = (第一步達(dá)到的水平)且Pi 0, 低于目標(biāo) i 0, 超過目標(biāo) i 0 (i = 1, 2, 3),5.37,懷特公司問題的優(yōu)先目標(biāo)規(guī)劃建模(步驟3),令Pi = 每天生產(chǎn)產(chǎn)品 i 的數(shù)量 (i = 1, 2, 3),低于目標(biāo) i = 低于目標(biāo) i 的數(shù)量 (i = 1, 2, 3),超過目標(biāo) i = 超過目標(biāo) i 的數(shù)量 (i = 1, 2, 3),Min ( 超過 3)st達(dá)到的水平 偏差目標(biāo)目標(biāo) 1: 12P1 + 9P2 + 15P3 (超過目標(biāo) 1) + (低于目標(biāo) 1) =125目標(biāo) 2:5P1 + 3P2 + 4P3 (超過目標(biāo) 2) + (低于目標(biāo) 2) =

14、 40目標(biāo) 3:5P1 + 7P2 + 8P3 (超過目標(biāo) 3) + (低于目標(biāo) 3) =55(低于目標(biāo) 1) = (第一步達(dá)到的水平)(低于目標(biāo) 2) = (第二步達(dá)到的水平)且Pi 0,低于目標(biāo) i 0,超過目標(biāo) i 0 (i = 1, 2, 3),5.38,懷特公司問題的優(yōu)先目標(biāo)規(guī)劃建模(步驟4),令Pi = 每天生產(chǎn)產(chǎn)品 i 的數(shù)量 (i = 1, 2, 3),低于目標(biāo) i = 低于目標(biāo) i 的數(shù)量 (i = 1, 2, 3),超過目標(biāo) i = 超過目標(biāo) i 的數(shù)量 (i = 1, 2, 3),Min (超過目標(biāo) 2)st達(dá)到的水平 偏差目標(biāo)目標(biāo) 1: 12P1 + 9P2 + 15P

15、3 (超過目標(biāo) 1) + (低于目標(biāo) 1) =125目標(biāo)2:5P1 + 3P2 + 4P3 (超過目標(biāo) 2) + (低于目標(biāo) 2) = 40目標(biāo) 3:5P1 + 7P2 + 8P3 (超過目標(biāo) 3) + (低于目標(biāo) 3) =55(低于目標(biāo) 1) = (第1步達(dá)到的水平)(低于目標(biāo) 2) = (第2步達(dá)到的水平)(超過目標(biāo) 3) = (第3步達(dá)到的水平)andPi 0, 低于目標(biāo) i 0, 超過目標(biāo) i 0 (i = 1, 2, 3),5.39,Preemptive Goal Programming Spreadsheet步驟 1: Min (低于目標(biāo) 1),5.40,優(yōu)先目標(biāo)規(guī)劃的電子表格步驟

16、 3: Min (超過目標(biāo) 3),5.41,優(yōu)先目標(biāo)規(guī)劃的電子表格步驟 4: Min (超過目標(biāo) 2),5.42,3 整 數(shù) 規(guī) 劃,5.43,整數(shù)規(guī)劃問題的類型,純整數(shù)規(guī)劃問題: 指的是所有的決策變量均為整數(shù)的線性規(guī)劃問題 混合整數(shù)規(guī)劃問題: 只有部分決策變量要求為整數(shù)(整數(shù)變量),而可分性假設(shè)對(duì)其余變量是適用的(連續(xù)變量). 0-1變量是指只能取0或1的變量. 0-1整數(shù)規(guī)劃 (BIP)指那些要求整數(shù)的決策變量只能在0或1兩個(gè)值中取值的問題. 這類問題可以依據(jù)是否所有的決策變量均為0-1變量而劃分為純0-1整數(shù)規(guī)劃問題和混合整數(shù)規(guī)劃問題.,5.44,0-1變量的應(yīng)用,由于0-1變量只提供兩

17、種選擇,當(dāng)涉及到是非決策的時(shí)候,非常適合. 例子: 我們是否應(yīng)該開展某一特定的項(xiàng)目? 我們是否應(yīng)該做某一固定投資? 我們是否應(yīng)該將設(shè)備設(shè)置在某一特定地點(diǎn)上?,5.45,加利福尼亞制造公司的例子,加利福尼亞制造公司T是在整個(gè)加利福尼亞地區(qū)擁有多個(gè)工廠和倉庫的多元化公司.但是在洛山磯和舊金山還沒有運(yùn)作設(shè)施 一個(gè)基本的問題是是否在洛山磯或舊金山建一個(gè)新的工廠. 管理層也在考慮至多建立一個(gè)新的倉庫,但是倉庫地點(diǎn)限制在新建工廠的城市. 問題:加利福尼亞制造公司是否應(yīng)該在洛山磯或就金山擴(kuò)展他們的公司或倉庫?,5.46,加利福尼亞制造公司的數(shù)據(jù),5.47,0-1決策變量,5.48,代數(shù)建模,令x1 = 1

18、如果在洛山磯建廠.; 否則為0 x2 = 1 如果在舊金上建廠.; 否則為0 x3 = 1 如果在洛山磯建倉庫;否則為0 x4 = 1 如果在舊金山建倉庫;否則為 0Max 凈現(xiàn)值 = 8x1 + 5x2 + 6x3 + 4x4 (萬美元)st花費(fèi)的資金: 6x1 + 3x2 + 5x3 + 2x4 10 (萬美元)最多一個(gè)倉庫: x3 + x4 1有廠才有倉庫: x3 x1 x4 x2且x1, x2, x3, x4 都是0-1變量.,5.49,電子表格建模,5.50,使用Solver Table進(jìn)行敏感性分析,5.51,管理層的結(jié)論,管理層最開始嘗試性的決策是獲得1000萬美元的資金. 使用

19、這些資金,最好的計(jì)劃就是在洛山磯和舊金山都建工廠,但是不要倉庫. 整個(gè)計(jì)劃的優(yōu)勢在于它只用了900萬美元,為其他的項(xiàng)目節(jié)約了100萬美元的資金. 如果可用的資金減少到900萬美元以下,那么將會(huì)遭受重大的損失(總的凈現(xiàn)值將減少400萬美元). 如果可獲得的資金增加100萬美元(到1100萬美元)將會(huì)顯著地增加總地凈現(xiàn)值(400萬美元),管理者決定這樣做. 用這些可獲得的資金,最好的計(jì)劃是在兩個(gè)城市都建廠,在舊金山建一個(gè)倉庫.,5.52,一些應(yīng)用,投資分析 我們是否應(yīng)該開展某一固定投資? 選址 某一地點(diǎn)是否應(yīng)該被選擇作為一個(gè)新的設(shè)施的地點(diǎn)? 設(shè)計(jì)一個(gè)生產(chǎn)和配送網(wǎng)絡(luò) 某一工廠是否應(yīng)該開?某一地點(diǎn)是否

20、應(yīng)該選擇來修一個(gè)新的工廠?某一配送中心是否應(yīng)該開?某一地點(diǎn)是否應(yīng)該選擇來修一個(gè)新的配送中心?是否應(yīng)該指點(diǎn)某一配送來服務(wù)某一市場區(qū)域?,5.53,帶有啟動(dòng)成本的偉恩德公司的例子 (變化1),假定偉恩德公司的例子做了兩個(gè)變化： 對(duì)于每個(gè)產(chǎn)品，在開始生產(chǎn)之前都需要為安裝生產(chǎn)設(shè)備支出一次性的準(zhǔn)備成本。 一個(gè)生產(chǎn)批次在一個(gè)星期后結(jié)束，因此，原模型的D,W值分別表示門和窗的生產(chǎn)數(shù)量，而不是每周的生產(chǎn)率。因此，必須將門，窗的數(shù)量限制在整數(shù)范圍內(nèi)。,5.54,代數(shù)建模,令D = 生產(chǎn)的門的數(shù)量,W = 生產(chǎn)的窗的數(shù)量,y1 = 生產(chǎn)門為1 ；否則為 0y2 = 生產(chǎn)窗為1 ；否則為 0Max P = 300D

21、 + 500W 700y1 1,300y2st原始的約束:工廠 1:D 4工廠 2:2W 12工廠 3:3D + 2W 18只有開始生產(chǎn):門:D 99y1窗:W 99y2且D 0, W 0, y1 和 y2 都是0-1變量,5.55,包含互斥產(chǎn)品的偉恩德例子(變化2),假定現(xiàn)在原始的偉恩德公司例子只有一個(gè)變化： 兩種潛在的新產(chǎn)品 (門和窗）具有相同的用戶，是相互競爭的。因此，管理層決定不同時(shí)生產(chǎn)兩種產(chǎn)品. 最多只選擇一種產(chǎn)品生產(chǎn)，所以，要么D = 0 ，要么 W = 0,或同時(shí)為0,5.56,代數(shù)建模,令D = 生產(chǎn)門的數(shù)量,W = 生產(chǎn)窗的數(shù)量,y1 = 如果生產(chǎn)門則為1，否則為0y2 =

22、如果生產(chǎn)窗則為1，否則為0Max P = 300D + 500Wst原始的約束:工廠 1:D 4工廠 2:2W 12工廠 3:3D + 2W 18如果生產(chǎn)任何一種則輔助變量必須為1 ：門 ：D 99y1窗：W 99y2相互排斥：:y1 + y2 1且D 0, W 0, y1 和 y2 都是0-1變量.,5.57,加入二選一約束的偉恩德公司的例子(變化3),現(xiàn)在假設(shè)僅對(duì)最初的偉恩德例子做如下的改動(dòng)： 工廠最近建了一個(gè)與工廠3類似的新工廠（工廠4），因此，新廠也可以生產(chǎn)兩種新產(chǎn)品(門和窗)。 但是，管理層只想只選擇一個(gè)工廠生產(chǎn)這些產(chǎn)品，選擇的工廠應(yīng)該提供最具盈利性的產(chǎn)品組合。,5.58,加入二選一

23、約束的偉恩德例子的數(shù)據(jù)(變化3),5.59,代數(shù)建模,令D = 生產(chǎn)門的數(shù)量W =生產(chǎn)窗的數(shù)量,y = 如果選擇工廠4則為1；如果顯則工廠3則為 0Max P = 300D + 500Wst工廠 1:D 4工廠 2:2W 12工廠 3:3D + 2W 18 + 99y工廠 4:2D + 4W 28 + 99(1 y)且D 0, W 0, y1 和 y2 都是0-1變量.,5.60,超級(jí)蘇滋公司的營銷計(jì)劃,超級(jí)蘇滋公司正在為其下一年的新產(chǎn)品制定營銷計(jì)劃。 對(duì)于這三種產(chǎn)品，需要作出在國家電視網(wǎng)絡(luò)購買5個(gè)時(shí)段的廣告的決策。 每個(gè)時(shí)段只針對(duì)一種產(chǎn)品。 問題:這5個(gè)時(shí)段如何分配給這三種產(chǎn)品？,5.61,

24、超級(jí)蘇滋公司問題的數(shù)據(jù),5.62,代數(shù)建模,令yij = 1 如果產(chǎn)品i 有j 個(gè)廣告片斷; 否則為0 (i = 1, 2, 3; j = 1, 2, 3)Max 利潤= y11 + 3y12 + 3y13 + 2y22 + 3y23 y31 + 2y32 + 4y33 (千美元)st相互排斥:產(chǎn)品 1:y11 + y12 + y13 1產(chǎn)品 2:y21 + y22 + y23 1 產(chǎn)品 3:y31 + y32 + y33 1 總的可以獲得的片斷:y11 + 2y12 + 3y13 + y21 + 2y22 + 3y23 + y31 + 2y32 + 3y33 5且yij 是0-1變量 (i

25、= 1, 2, 3; j = 1, 2, 3).,5.63,5.64,4 網(wǎng)絡(luò)最優(yōu)化問題,5.65,無限配送公司的問題,無限配送公司有兩個(gè)工廠生產(chǎn)產(chǎn)品，這些產(chǎn)品需要運(yùn)到兩個(gè)倉庫里： 工廠1生產(chǎn) 80單位. 工廠2生產(chǎn) 70 單位. 倉庫1需要 60 單位. 倉庫2需要 90 單位. 工廠1和倉庫1之間以及工廠2和倉庫2之間各有一條鐵路運(yùn)輸軌道 卡車司機(jī)最多可以從工廠運(yùn)輸50個(gè)單位到配送中心，然后可以從配送中心運(yùn)輸50個(gè)單位到倉庫。 問題: 每條線路運(yùn)送多少單位的產(chǎn)品？,5.66,配送網(wǎng)絡(luò),5.67,配送網(wǎng)絡(luò)的數(shù)據(jù),5.68,網(wǎng)絡(luò)模型,5.69,最優(yōu)解,5.70,最小費(fèi)用流問題的術(shù)語,所有最小費(fèi)

26、用流問題都是用帶有通過其中的流的網(wǎng)絡(luò)表示的. 網(wǎng)絡(luò)中的圓圈表示節(jié)點(diǎn). 如果節(jié)點(diǎn)產(chǎn)生的凈流量（流出或流近）是一個(gè)確定的正數(shù)的話，這個(gè)節(jié)點(diǎn)就是供應(yīng)點(diǎn)。 如果節(jié)點(diǎn)產(chǎn)生的凈流量是一個(gè)確定的負(fù)數(shù)的話，這個(gè)節(jié)點(diǎn)就是需求點(diǎn)。 如果節(jié)點(diǎn)產(chǎn)生的凈流量恒為0，那么這個(gè)節(jié)點(diǎn)就稱為轉(zhuǎn)運(yùn)點(diǎn)，我們把流出節(jié)點(diǎn)的量等于流入節(jié)點(diǎn)的量稱為流量守恒。 網(wǎng)絡(luò)中的箭頭稱為弧. 允許通過某一條弧的最大流量稱為該弧的容量.,5.71,最小費(fèi)用流問題的假設(shè),至少有一個(gè)節(jié)點(diǎn)稱為供應(yīng)點(diǎn) 至少有一個(gè)節(jié)點(diǎn)稱為需求點(diǎn). 所有剩下的節(jié)點(diǎn)稱為轉(zhuǎn)運(yùn)點(diǎn). 通過弧的流只允許沿著箭頭的方向流動(dòng)，通過弧的最大流量取決于該弧的容量（如果流是雙向的話，則需要用一對(duì)箭頭

27、指向相反的弧來表示） 網(wǎng)絡(luò)中有足夠的弧提供足夠的容量，使得所有在供應(yīng)點(diǎn)產(chǎn)生的流都能夠到達(dá)需求點(diǎn)。 在流的單位成本已知的前提下，通過每一條弧的流的成本和流量成正比 最小費(fèi)用流問題的目標(biāo)是在滿足給定需求的條件下，使得通過網(wǎng)絡(luò)供應(yīng)的總成本最?。〒Q一種說法是通過這樣做使得總利潤最大化）。,5.72,最小費(fèi)用流問題的性質(zhì),具有可行解的特征：在以上的假設(shè)下，當(dāng)且僅當(dāng)供應(yīng)點(diǎn)所提供的流量總和等于需求點(diǎn)所需要的流量總和時(shí)，最小費(fèi)用流問題具有可行解。 具有整數(shù)解的性質(zhì)：只要其所有的供應(yīng)、需求和弧的容量都是整數(shù)值，那么任何最小費(fèi)用流問題的可行解就一定是所有流量都是整數(shù)的最優(yōu)解。,5.73,電子表格建模,5.74,S

28、UMIF函數(shù),SUMIF公式可以用來簡化節(jié)點(diǎn)流約束. =SUMIF(Range A, x, Range B) 對(duì)于在(Range A)中等于x的數(shù)量，SUMIF 對(duì)相應(yīng)的在(Range B).中的實(shí)體相加。 從節(jié)點(diǎn)x的凈流量 (流出流入) =SUMIF(“From labels”, x, “Flow”) SUMIF(“To labels”, x, “Flow”),5.75,BMZ 最大流問題,BMZ公司是歐洲一家生產(chǎn)豪華汽車的制造商，出口到美國顯得尤其重要. BMZ 的汽車在加利福尼亞越來越受歡迎，所以保證洛杉磯中心良好的供應(yīng)就顯得尤其重要了. BMZ需要盡快制定一個(gè)方案，使得下個(gè)月從總廠運(yùn)送

29、到洛杉磯配送中心的供應(yīng)件盡可能多。 可以運(yùn)送多少配件的限制條件就是該公司配送網(wǎng)絡(luò)的容量。 問題:通過每個(gè)運(yùn)送 線路應(yīng)該運(yùn)送多少單位才能使從斯圖加特到洛杉磯的流量最大？,5.76,BMZ 配送網(wǎng)絡(luò),5.77,BMZ的網(wǎng)絡(luò)模型,5.78,BMZ的電子表格建模,5.79,最大流問題的假設(shè),網(wǎng)絡(luò)中所有流起源于一個(gè)節(jié)點(diǎn)，這個(gè)節(jié)點(diǎn)叫做源，所有的流終止于另一個(gè)節(jié)點(diǎn)，這個(gè)節(jié)點(diǎn)叫做收點(diǎn)（在BMZ問題中的源和收點(diǎn)分別代表工廠額配送中心）。 其余所有的節(jié)點(diǎn)叫做轉(zhuǎn)運(yùn)點(diǎn) 通過每一個(gè)弧的流只允許沿著箭頭所示的方向移動(dòng)。由源出發(fā)的所有的弧背向源，而所有終結(jié)于收點(diǎn)的弧都指向收點(diǎn)。 最大流問題的目標(biāo)就是使得從源點(diǎn)到收點(diǎn)的總流量

30、最大，這個(gè)流量的大小可以用兩種等價(jià)的方式來衡量，分別叫做從源點(diǎn)出發(fā)的流量和進(jìn)入收點(diǎn)的流量。,5.80,具有多個(gè)供應(yīng)點(diǎn)和需求點(diǎn)的BMZ,BMZ在柏林有第二家、小一點(diǎn)的工廠。. 當(dāng)洛杉磯配送中心出現(xiàn)庫存短缺時(shí)，西雅圖的配送中心有能力供應(yīng)配件給洛杉磯配送中心的顧客。 問題：經(jīng)過每一個(gè)運(yùn)輸線路應(yīng)該運(yùn)動(dòng)多少單位從而使從斯圖加特和柏林到洛杉磯和西雅圖的總流量達(dá)到最大？,5.81,擴(kuò)展的BMZ問題的網(wǎng)絡(luò)模型,5.82,電子表格建模,5.83,最大流問題的一些應(yīng)用,通過配送網(wǎng)絡(luò)的流量最大，如 BMZ問題. 通過從供應(yīng)商到處理設(shè)施的公司供應(yīng)網(wǎng)絡(luò)的流量最大. 通過管道運(yùn)輸系統(tǒng)的油的流量最大. 最大化通過輸水系統(tǒng)的

31、水的流量. 通過交通網(wǎng)絡(luò)的車輛的流量最大.,5.84,里特城的消防隊(duì)問題,Littletown is a small town in a rural area. Its fire department serves a relatively large geographical area that includes many farming communities. Since there are numerous roads throughout the area, many possible routes may be available for traveling to any given farming community. Question: Which route from the fire station to a certain farming community minimizes the total number of miles?,5.85,里特城的道路系統(tǒng),5.86,網(wǎng)絡(luò)表述,5.87,電子表格建模,5.88,最短路問題的假設(shè),在網(wǎng)絡(luò)中選擇一條路，這條路始