excel-module-3-整數(shù)規(guī)劃0-1規(guī)劃的應(yīng)用

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

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

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

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

5、多只建1個(gè)倉庫3. 相依決策變量--建廠才建倉庫,目標(biāo)函數(shù)：凈現(xiàn)值最大,目標(biāo)函數(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求解過程,目標(biāo)函數(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 連鎖店選址,某連鎖店計(jì)劃在城區(qū)的東南西北部建店。有10個(gè)位置可供參考。每個(gè)位置的預(yù)計(jì)投資額和利潤如表。并有如下條件：　 A1,A2,A3三個(gè)點(diǎn)至多選擇2個(gè)； A4,A5兩個(gè)點(diǎn)中至少選擇1個(gè)； A6,A7兩個(gè)

7、點(diǎn)中至少選擇1個(gè)； A8,A9,A10三個(gè)點(diǎn)中至少選擇2個(gè)。 投資總額不能超過720萬。,目標(biāo)函數(shù)： 約束：,問題建模,目標(biāo)函數(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è)希望在一個(gè)區(qū)域建立分銷中心，就在該區(qū)域及其接壤的周邊區(qū)域建立連鎖店?，F(xiàn)在該B地區(qū)有20個(gè)相鄰的區(qū)域（以數(shù)字標(biāo)示），它們之間的相鄰關(guān)系如表所示。建立分銷中心是需要復(fù)雜的審批手續(xù)的，至少應(yīng)該建立多少個(gè)分銷中心、在哪些區(qū)域建立，能夠使分銷中心和連鎖店覆蓋整個(gè)B地區(qū)，而且分銷中心的數(shù)量最小。,例5 分銷中心選址—圖示,,例5 相鄰關(guān)系數(shù)據(jù)表,例6

9、資金預(yù)算,A冰箱公司正在考慮今后4年的投資方案。面對(duì)每年有限的資金，管理者需要選擇最好的方案，每種方案的凈現(xiàn)金流、資金需求和4年內(nèi)的可用資金如表所示。求能使凈現(xiàn)值最大的投資方案。,例6 資金預(yù)算 – 數(shù)據(jù),目標(biāo)函數(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)化模型和求解過程,目標(biāo)函數(shù)：I13：=SUMPRODUCT(C10:F10,C13:F13)約束：G6

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

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

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