1、選 址 問 題,中央財經(jīng)大學 信息學院吳 靖,正確地使用方法，并對結(jié)果做出恰當?shù)亟忉尅?§1 選址（運輸）,一家石油公司，有油田并進口原油，有若干個煉油廠和配送中心，由于市場拓展的需要，公司決定新建煉油廠，管理層需要為新煉油廠選址做出決策。決策的三個主要因素是：1.從油田運送原油到所有煉油廠（含新建煉油廠）的運輸成本；2.從所有煉油廠（含新建煉油廠）到每一個配送中心的運輸成本；3.新煉油廠的運作成本。例如，勞動力成

2、本、賦稅、能源成本、保險成本等。,例1 Site-Select Problem,§2 選址--整數(shù)規(guī)劃應用,前面討論的線性規(guī)劃問題中，有些最優(yōu)決策變量可能是小數(shù)，但對于某些具體問題，常有要求解答必須是整數(shù)（稱為整數(shù)解）。例如，機器的臺數(shù)、完成工作的人數(shù)等。 為了得到問題的整數(shù)解，對得到的小數(shù)解四舍五入化整是不可以的，化整以后不一定是問題的解，或不一定是問題的最優(yōu)解。因此，需要專門研究。 整數(shù)規(guī)劃是規(guī)劃問題的一個分支，是近

3、20年發(fā)展起來的。,整數(shù)規(guī)劃,例2 投資。全整數(shù)規(guī)劃問題。 A公司有2000萬用來購買租賃財產(chǎn)。經(jīng)過篩選，已把投資目標定位在聯(lián)體別墅和公寓樓。每套聯(lián)體別墅售價282萬，現(xiàn)有5套空閑。每棟公寓樓售價400萬，開發(fā)商可根據(jù)A公司的需要建造。 A公司項目經(jīng)理每月用于這些新置財產(chǎn)上的時間是140小時。每套聯(lián)體別墅預計每月用時4小時，每棟公寓樓預計每月用時40小時。 扣除抵押償還和經(jīng)營成本后，現(xiàn)金流預計每套聯(lián)體別墅10

4、萬，每棟公寓樓15萬。股東需要確定使現(xiàn)金流最大的購買方案。,例2 投資--全整數(shù)規(guī)劃問題,例3 選址（0-1規(guī)劃應用）,A公司在L3地區(qū)有多個工廠和倉庫，由于業(yè)務拓展的需要，管理層決定在L1和L2地區(qū)建廠。需要決策的問題是在L1還是在L2建廠，或在2個地區(qū)都建廠；并同時考慮至多建1個新倉庫，如果建新倉庫，該倉庫應該與新建廠在同一個地點?？捎觅Y金：10百萬。,模型—問題的解析描述,約 束1. 可用資金102. 互斥決策變量--至

5、多只建1個倉庫3. 相依決策變量--建廠才建倉庫,目標函數(shù)：凈現(xiàn)值最大,目標函數(shù)：Max z=8x1+5x2+6x3+4x4 約束： 1.可用資金10 6*x1+3*x2+5*x3+2*x4=x3，x2>=x4 4.決策變量 xi = 0,1 (i = 1,2,3,4),例3 模型和Excel求解過程,目標函數(shù)：Max z=8x1+5x2+6x3+4x4

6、 約束： 1.可用資金10 6*x1+3*x2+5*x3+2*x4=x3，x2>=x4 4.決策變量 xi = 0,1 (i = 1,2,3,4),例4 連鎖店選址,某連鎖店計劃在城區(qū)的東南西北部建店。有10個位置可供參考。每個位置的預計投資額和利潤如表。并有如下條件：　 A1,A2,A3三個點至多選擇2個； A4,A5兩個點中至少選擇1個； A6,A7兩個

7、點中至少選擇1個； A8,A9,A10三個點中至少選擇2個。 投資總額不能超過720萬。,目標函數(shù)： 約束：,問題建模,目標函數(shù)：H15：=SUMPRODUCT(C5:L5,C9:L9)約束：C15：=SUMPRODUCT(C4:L4,C9:L9)C17：=SUM(C9:E9)C18：=SUM(F9:G9)C19：=SUM(H9:I9)C20：=SUM(J9:L9),Excel求解過程,例5

8、 分銷中心選址,A企業(yè)需要在B地區(qū)建立分銷中心和連鎖店。由于建立分銷中心的成本較高，A企業(yè)希望在一個區(qū)域建立分銷中心，就在該區(qū)域及其接壤的周邊區(qū)域建立連鎖店?，F(xiàn)在該B地區(qū)有20個相鄰的區(qū)域（以數(shù)字標示），它們之間的相鄰關系如表所示。建立分銷中心是需要復雜的審批手續(xù)的，至少應該建立多少個分銷中心、在哪些區(qū)域建立，能夠使分銷中心和連鎖店覆蓋整個B地區(qū)，而且分銷中心的數(shù)量最小。,例5 分銷中心選址—圖示,,例5 相鄰關系數(shù)據(jù)表,例6

9、資金預算,A冰箱公司正在考慮今后4年的投資方案。面對每年有限的資金，管理者需要選擇最好的方案，每種方案的凈現(xiàn)金流、資金需求和4年內(nèi)的可用資金如表所示。求能使凈現(xiàn)值最大的投資方案。,例6 資金預算 – 數(shù)據(jù),目標函數(shù)：Max z=90x1+40x2+10x3+37x4 約束： 15x1 + 10x2 + 10x3 + 15x4 <= 40

10、 20x1 + 15x2 + 0x3 + 10x4 <= 50 ...... ...... xi = 0,1 (i=1,2,3,4,),優(yōu)化模型和求解過程,目標函數(shù)：I13：=SUMPRODUCT(C10:F10,C13:F13)約束：G6

11、：=SUMPRODUCT(C6:F6,$C$13:$F$13)G7：G8：G9：,§3 指 派,指派問題討論的是n項工作分配給n個人去完成，每個人的工作效率不同，如何分配任務，能夠使總的工作效率最高。類似的有：n臺機器加工n項任務，n條航線n艘船只航行等。 指派（分配）問題是0-1規(guī)劃的特例，也是運輸問題的特例，在指派問題模型中，每一個產(chǎn)地的提供量和每一個目的地的需求量均為1，即n=m, ai=bi=1 。,指

12、派問題一般模型,例7—比賽場地,某主辦方舉辦4場比賽,并為每場比賽派出官員,下表給出每一位官員到每個賽場的距離,舉辦方希望以總距離最小的方案派出官員,求派出方案。,例8—客戶項目,A公司分別從3個客戶（c1,c2,c3）那里得到了市場調(diào)研的項目，目前有3個項目經(jīng)理（m1,m2,m3）可以承擔這些項目，完成每個項目所需的時間與這3位項目經(jīng)理的經(jīng)驗和能力有關，管理層估算了每位經(jīng)理完成各項目的可能時間，如何分配項目給各經(jīng)理，可以使項目盡快完成

13、（所用時間最短）？,例9—Assignment Problem,Sellmore Co. Assignment Problem 一家公司為一次會議聘用了4位臨時工人,需要為4位工人分配四項工作,每個人由于能力的不同,完成每項工作所用的時間不同,經(jīng)過評估,每個人每小時工資也不相同,公司需要確定如何分配工作,總費用最小.,例10 Machine-Location Problem,Job Shop Co. Machine-Locat