第六章--整數(shù)規(guī)劃應(yīng)用運(yùn)籌學(xué)

1、Chapter 6 Integer Programming 整數(shù)規(guī)劃,§1 Graphical Method for Integer Programming 整數(shù)規(guī)劃的圖解法§2　Branch and Bound for Pure IPs 整數(shù)規(guī)劃的分枝定界法 §3 Binary integer programming 0-1整數(shù)規(guī)劃 §4 Assignment P

2、roblems 指派問(wèn)題,求整數(shù)解的線(xiàn)性規(guī)劃問(wèn)題，不是用四舍五入法或去尾法對(duì)線(xiàn)性規(guī)劃的非整數(shù)解加以處理都能解決的，而要用整數(shù)規(guī)劃的方法加以解決。在整數(shù)規(guī)劃中，如果所有的變量都為整數(shù)，則稱(chēng)為純整數(shù)規(guī)劃問(wèn)題；如果有一部分變量為整數(shù)，另一部分變量可以不取整數(shù)，則稱(chēng)之為混合整數(shù)規(guī)劃問(wèn)題。在整數(shù)規(guī)劃中，如果變量的取值只限于0和1，這樣的變量我們稱(chēng)之為0-1變量。在純整數(shù)規(guī)劃和混合整數(shù)規(guī)劃問(wèn)題中，如果所有的變量都為0-1變量，則稱(chēng)之為0-1規(guī)

3、劃。,例1 TBA 航空公司飛機(jī)采購(gòu)問(wèn)題Airlines Problem,線(xiàn)性規(guī)劃模型設(shè)Let S = 購(gòu)買(mǎi)的小飛機(jī)數(shù) Number of small airplanes to purchaseL = 購(gòu)買(mǎi)的大飛機(jī)數(shù)Number of large airplanes to purchaseMaximize Profit z = S + 5L ($millions)subject to 5S + 50L ≤ 100

4、 ($millions) Capital Available S ≤ 2 Max Small Planes: S ≥ 0, L ≥ 0. 且為整數(shù),可分規(guī)劃 Separable Programming,線(xiàn)性規(guī)劃的可分性假設(shè) (divisibility Assumptio

5、n of LP)線(xiàn)性規(guī)劃的決策變量可以在滿(mǎn)足一定約束條件下取所有實(shí)數(shù)，包括小數(shù)。因此決策變量不一定是整數(shù)，決策變量代表各種可能的方案(活動(dòng)水平).違背可分性假設(shè)當(dāng)要求決策變量必須取整數(shù)時(shí)，就不再符合可分性假設(shè)，,圖解法 Graphical Method for Integer Programming,當(dāng)一個(gè)整數(shù)規(guī)劃問(wèn)題只有兩個(gè)決策變量時(shí)，可用圖解法求解首先去掉整數(shù)約束，得到松弛規(guī)劃。確定松弛規(guī)劃的可行域。根據(jù)目標(biāo)函數(shù)確定等值線(xiàn)，

6、將等值線(xiàn)沿著梯度的方向移動(dòng)。.當(dāng)?shù)戎稻€(xiàn)平移到可行域內(nèi)的最后一個(gè)整數(shù)點(diǎn)，使目標(biāo)函數(shù)取得最優(yōu)值時(shí)，這個(gè)整數(shù)解即為最優(yōu)解。用圖解法求例1最優(yōu)解,圖解,,,,,,(0, 2)整數(shù)規(guī)劃最優(yōu)解,利潤(rùn)等于10,Max z = S + 5L S.T. 5S + 50L ≤ 100 S ≤ 2,,最優(yōu)解,利潤(rùn)＝11＝S＋5L,取整解,利潤(rùn)＝7,購(gòu)買(mǎi)的小飛機(jī)數(shù),大飛機(jī)數(shù),§

7、;1　整數(shù)規(guī)劃的圖解法,例1. 某公司擬用集裝箱托運(yùn)甲、乙兩種貨物，這兩種貨物每件的體積、重量、可獲利潤(rùn)以及托運(yùn)所受限制如表所示。 P162甲種貨物至多托運(yùn)4件，問(wèn)兩種貨物各托運(yùn)多少件，可使獲得利潤(rùn)最大。解：設(shè)x1 、 x2分別為甲、乙兩種貨物托運(yùn)的件數(shù)，建立模型 目標(biāo)函數(shù)： Max z = 2x1 +3 x2 約束條件： s.t.

8、195 x1 + 273 x2 ≤1365 4 x1 + 40 x2 ≤140 x1 ≤4 x1，x2 ≥ 0 為整數(shù)。如果去掉最后一

9、個(gè)約束，就是一個(gè)線(xiàn)性規(guī)劃問(wèn)題。利用圖解法，,得到線(xiàn)性規(guī)劃的最優(yōu)解為x1=2.44, x2=3.26,目標(biāo)函數(shù)值為14.66。由圖表可看出，整數(shù)規(guī)劃的最優(yōu)解為x1=4, x2=2,目標(biāo)函數(shù)值為14。性質(zhì)1：任何求最大目標(biāo)函數(shù)值的純整數(shù)規(guī)劃或混合整數(shù)規(guī)劃的最大目標(biāo)函數(shù)值小于或等于相應(yīng)的線(xiàn)性規(guī)劃的最大目標(biāo)函數(shù)值；任何求最小目標(biāo)函數(shù)值的純整數(shù)規(guī)劃或混合整數(shù)規(guī)劃的最小目標(biāo)函數(shù)值大于或等于相應(yīng)的線(xiàn)性規(guī)劃的最小目標(biāo)函數(shù)值。,,§2

10、 Branch and Bound Technique for Pure IPs整數(shù)規(guī)劃的分枝定界法,,,分枝定界法是求解整數(shù)規(guī)劃的一種常用的有效的方法，它既能解決純整數(shù)規(guī)劃的問(wèn)題，又能解決混合整數(shù)規(guī)劃的問(wèn)題。大多數(shù)求解整數(shù)規(guī)劃的商用軟件就是基于分枝定界法而編制成的。 分枝定界法是先求解整數(shù)規(guī)劃的線(xiàn)性規(guī)劃問(wèn)題。如果其最優(yōu)解不符合整數(shù)條件，則求出整數(shù)規(guī)劃的上下界，用增加約束條件的辦法，把相應(yīng)的線(xiàn)性規(guī)劃的可行域分成子區(qū)域（稱(chēng)為分枝

11、），再求解這些子區(qū)域上的線(xiàn)性規(guī)劃問(wèn)題，不斷縮小整數(shù)規(guī)劃的上下界的距離，最后得整數(shù)規(guī)劃的最優(yōu)解。,分枝定界法步驟,第一步: 將原規(guī)劃稱(chēng)為問(wèn)題A0.去掉整數(shù)約束得到相應(yīng)的松弛規(guī)劃B0第二步：求解B0 ，有以下幾種情況：(1) B0無(wú)解→ A0無(wú)解，停止計(jì)算 (2) B0 最優(yōu)解為整數(shù)，則B0 最優(yōu)解為A0最優(yōu)解，停止計(jì)算 (3) B0 最優(yōu)解不是整數(shù)解，則轉(zhuǎn)入下一步第三步：確定初始上界

12、 和下界 ，記B0 最優(yōu)值為 用觀察法找到A 0.的一個(gè)整數(shù)解，此解的目標(biāo)函數(shù)值記為第四步：分枝（將問(wèn)題B0分枝），在的最優(yōu)解中，任選一個(gè)不符合整數(shù)條件變量 xj＝bj 構(gòu)造兩個(gè)約束條件， xj≤[bj ]； xj ≥ [bj ]＋1；加到 B0中得到兩個(gè)子規(guī)劃B1和B2（兩支）。第五步：比較與剪枝，對(duì)B1和B2求解，可得到以下情況： (1) 分枝無(wú)解→該分枝是樹(shù)葉，剪枝。 (2) 分枝

13、最優(yōu)解為整數(shù)，從該最優(yōu)解的目標(biāo)函數(shù)值與原來(lái)的 值中選最大的值作為新的 ，該分枝為樹(shù)葉，剪掉,(3) 該分枝最優(yōu)解不是整數(shù)解，但其目標(biāo)函數(shù)值≤ 當(dāng)前下界 ,該分枝剪掉 (4) 該分枝最優(yōu)解不是整數(shù)解，而其目標(biāo)函數(shù)值 ≥當(dāng)前下界 ，則該枝需要繼續(xù)分枝，在各分枝中選目標(biāo)函數(shù)最大的那枝進(jìn)行分枝。第六步：修改上、下界 (1)每求出一次符合整數(shù)的解，都要考慮修改下界 ，選整數(shù)解的目標(biāo)

14、函數(shù)值最大者為新的下界 (2)修改 ，找出所有未 分枝問(wèn)題目標(biāo)函數(shù)值最大者，為新的上界當(dāng)改變完上、下界 ， 后，若 ＝ ，則所有分枝均已查明，得到 A0的最優(yōu)解， 若 ＞ ，則說(shuō)明仍有分枝未查明，返回到第四步,例2 考慮下面整數(shù)規(guī)劃 consider the following Integer Programming P73 max z =x1

15、+2x2 s.t. 2x1+5x2≤15A0 2x1－2x2≤5 x1 , x2≥0 且為整數(shù),分枝定界法,,The optimal solutionfor the LP relaxation B0 is X，不考慮x1, x2為整數(shù)的限制條件，得規(guī)劃B0對(duì)應(yīng)的最優(yōu)解與最優(yōu)值如下，而 X=(0，0)為A0的可行解,,,R0,▽z,2x1＋5x2=15

16、,3,2.5,分枝與定界（1）,2x1－5x2=5,B0 max z =x1+2x2 s.t. 2x1+5x2 ≤ 15 2x1－2x2 ≤5 x1 , x2≥0,考察X的某一分量，不妨選x2 ,因?yàn)?<x2<2,為了使x2整數(shù)化,剔除1<x2<2對(duì)應(yīng)的可行域。為此,增加約束條件x2≤1及x2≥2,于是可行域R0可分解成兩個(gè)小可行域R1和R2

17、.原規(guī)劃B0分解成子(subproblem)規(guī)劃B1與規(guī)劃B2，求解得:,B1 B2max z= x1+2x2 max z = x1+2x2s.t. 2x1+5x2≤15 s.t. 2x1+5x2≤15 2x1-2x2≤5

18、 2x1-2x2≤5 x2 ≤1 x2≥2 x1, x2≥0 x1, x2≥0,分枝與定界（2）,B0,,,x2≤1,x2≥2,x2≤1,所有松弛規(guī)劃的上界為Z ≤6.5，

19、修改上界為,,,R2,R1,分枝與定界（3）,因規(guī)劃B2的z 值優(yōu)于規(guī)劃B1 的z 值，故先分解規(guī)劃B2。仿上，R2分解成R3與R4=Ф。規(guī)劃B2分解成規(guī)劃B3與規(guī)劃B4,分枝與定界（4）,B3 B4max z = x1+2x2 max z= x1+2x2s.t. 2x1+5x2≤1

20、5 s.t. 2x1+5x2≤15 2x1-2x2≤5 2x1-2x2≤5 x2≥2 x2≥2 x1 ≤2

21、x1 ≥3 x1, x2≥0 x1, x2≥0,B0,,,x2≤1,x2≥2,B1,B2,,,x1≤2,x1≥3,無(wú)解 ×,考察B1 、B3，因規(guī)劃B3 的z值優(yōu)于規(guī)劃B1 的z值，故先分解規(guī)劃B3。仿上，R3分解成R5與R6。規(guī)劃B3 分解成規(guī)劃B5 與規(guī)劃B6 ：,分枝與定界（5）,B5

22、 B5max z= x1+2x2 max z=x1+2x2s.t. 2x1+5x2≤15 s.t. 2x1+5x2≤15 2x1-2x2≤5 2x1-2x2≤5 x2 ≥2

23、 x2 ≥2 x1 ≤2 x1 ≥3 x2 ≤2 x2 ≥3 x1, x2≥0且為整數(shù) x1, x2≥0

24、且為整數(shù),分枝定界求解過(guò)程,線(xiàn)性規(guī)劃B0Z0=6.79x1=3.93 x2=1.43,,,x2≤1,x2≥2,線(xiàn)性規(guī)劃B1Z1 =5.5x1=3.5 x2=1,,,線(xiàn)性規(guī)劃B2Z2 =6.5x1=2.5 x2=2,,,,線(xiàn)性規(guī)劃B4無(wú)可行解,x1≥3,x1≤2,,線(xiàn)性規(guī)劃B3Z3 = 6.4x1=2 , x2=2.2,,,,x2≥3,x2≤2,,線(xiàn)性規(guī)劃B5Z5=6x1=2 , x2=2,線(xiàn)性規(guī)劃B6Z5=6

25、x1=0 , x2=3,§3 0—1規(guī)劃Binary integer programming,當(dāng)我面臨是與非兩種選擇時(shí)，我們可以用決策變量取0或1值來(lái)表示這樣的決策，這樣，地j個(gè)是非決策問(wèn)題可以表示成 大量例子Examples:我們決定是否參與某個(gè)特定項(xiàng)目? Should we undertake a particular fixed project?我們決定是否進(jìn)行某項(xiàng)投資? Should we make

26、a particular fixed investment?我們決定是否將某個(gè)設(shè)施布置在某個(gè)特定的場(chǎng)所Should we locate a facility in a particular site?,一、Example 1 Site Selection 例4、京成畜產(chǎn)品公司計(jì)劃在市區(qū)的東、西、南、北四區(qū)建立銷(xiāo)售門(mén)市部，擬議中有10個(gè)位置 Aj (j＝1，2，3，…，10)可供選擇，考慮到各地區(qū)居民的消費(fèi)水平及居民居

27、住密集度，規(guī)定： 在東區(qū)由A1 ， A2 ，A3 三個(gè)點(diǎn)至多選擇兩個(gè)； 在西區(qū)由A4 ， A5 兩個(gè)點(diǎn)中至少選一個(gè)； 在南區(qū)由A6 ， A7 兩個(gè)點(diǎn)中至少選一個(gè)； 在北區(qū)由A8 ， A9 ， A10 三個(gè)點(diǎn)中至少選兩個(gè)。 Aj 各點(diǎn)的設(shè)備投資及每年可獲利潤(rùn)由于地點(diǎn)不同都是不一樣的，預(yù)

28、測(cè)情況見(jiàn)表所示 (單位：萬(wàn)元)。但投資總額不能超過(guò)720萬(wàn)元，問(wèn)應(yīng)選擇哪幾個(gè)銷(xiāo)售點(diǎn)，可使年利潤(rùn)為最大?,解：設(shè)：0--1變量 xi = 1 (Ai 點(diǎn)被選用）或 0 (Ai 點(diǎn)沒(méi)被選用） 這樣我們可建立如下的數(shù)學(xué)模型：Max z =36x1+40x2+50x3+22x4+20x5+30x6+25x7+48x8+58x9+61x10s.t. 100x1+120x2+150x3+80x4+70x5+90x6+80x7+140x8

29、+160x9+180x10 ≤ 720 x1 + x2 + x3 ≤ 2 x4 + x5 ≥ 1 x6 + x7 ≥ 1 x8 + x9 + x10 ≥ 2 xj ≥ 0 xj is binary ,for i = 1,2,3,……,10其他約束的表示：1) 如果選擇4個(gè)投資地點(diǎn)，如何表示？2) 或選擇A

30、3和A6 ，或選擇A9 3)如果選擇了A1或A5 , 就不選擇A8 反之如果選擇了A8 ,就不選擇A1和A5 4）A2和A7同時(shí)入選或同時(shí)不入選,x3 + x9 ＝ 1； x6 + x9 ＝ 1,x1 + x8 ≤ 1 ；x5 + x8 ≤ 1,x2 ＝ x7,加利福尼壓制造公司選址,加利福尼亞制造公司在加利福尼亞地區(qū)擁有多個(gè)工廠和倉(cāng)庫(kù)，但在洛杉磯和舊金山?jīng)]有設(shè)施，決策是在洛杉磯還是

31、在舊金山建立工廠（或兩個(gè)城市均建工廠）；管理層考慮至多建立一個(gè)新的倉(cāng)庫(kù)，而且倉(cāng)庫(kù)建在新建工廠的城市。建工廠和倉(cāng)庫(kù)收益的凈現(xiàn)值和所需資金見(jiàn)下表：,公司總的投資金額不超過(guò)1000萬(wàn)元，公司該如何進(jìn)行選址決策？,解 設(shè) x1 = 1 如果在洛杉磯建廠; 否則x1 = = 0 。x2 = 1如果在舊金山建廠; 否則x2 = 0 。 x3 = 1如果在洛杉磯建倉(cāng)庫(kù);否則x3= 0 ； x4 = 1如果在舊金山建倉(cāng)庫(kù)；否則x4 = 0 。數(shù)學(xué)模

32、型為Max NPV = 8x1 + 5x2 + 6x3 + 4x4 ($millions)約束投資資金: 6x1 + 3x2 + 5x3 + 2x4 ≤ 10 (百萬(wàn)）至多建一個(gè)倉(cāng)庫(kù):x3 + x4 ≤ 1倉(cāng)庫(kù)只建在新工廠所在地:x3 ≤ x1x4 ≤ x2

33、 x1, x2, x3, x4 ＝0或1.求解得： x1 ＝x2 ＝1, x3 ＝ x4 ＝0。 NPV = 13 (百萬(wàn)）。即在洛杉磯和舊金山各建一個(gè)工廠，不建倉(cāng)庫(kù),,靈敏度分析Sensitivity Analysis with Solver Table,管理結(jié)論Management’s Conclusion,Management’s initial tentative decision had been to make $

34、10 million of capital available.最初決策只有1000萬(wàn)元資金最優(yōu)方案是在洛杉磯和舊金山各建一個(gè)工廠。With this much capital, the best plan would be to build a factory in both Los Angeles and San Francisco, but no warehouses.An advantage of this plan is

35、that it only uses $9 million of this capital, which frees up $1 million for other projects.剩余1百萬(wàn)資金A heavy penalty (a reduction of $4 million in total net present value) would be paid if the capital made available were t

36、o be reduced below $9 million. 資金數(shù)量減到900萬(wàn)美元以下，凈現(xiàn)值減400萬(wàn)Increasing the capital made available by $1 million (to $11 million) would enable a substantial ($4 million) increase in the total net present value. Management deci

37、des to do this.增加一百萬(wàn)，可增加4百萬(wàn)的凈現(xiàn)值With this much capital available, the best plan is to build a factory in both cities and a warehouse in San Francisco.當(dāng)能增加100萬(wàn)資金時(shí)，最好的方案是在舊金山增加一倉(cāng)庫(kù)。,投資分析 Investment Analysis,A company is pla

38、nning their capital budget over the next several years.10個(gè)項(xiàng)目可供投資There are 10 potential projects they are considering pursuing.They have calculated the expected net present value of each project, along with the cash out

39、flow that would be required over the next five years.計(jì)算未來(lái)五年每個(gè)項(xiàng)目所需的投資現(xiàn)金，具體數(shù)字見(jiàn)下張PPT假定需要滿(mǎn)足一下要求, suppose there are the following contingency constraints:at least one of project 1, 2 or 3 must be done,1,2,3至少做一個(gè)project 4 a

40、nd project 5 cannot both be done, 4,5不能同時(shí)做project 7 can only be done if project 6 is done.項(xiàng)目7只有在項(xiàng)目6投資的情況下才能投資 ( project 7 can not be done unless project 6 is done)Question: 應(yīng)投資哪些項(xiàng)目Which projects should they pursue?,

41、相關(guān)數(shù)據(jù)Data for Capital Budgeting Problem,Max NPV = 20x1 +25x2 +22x3 +30x4 +42x5 +25x6 +18x7 +35x8 +28x9 +33x10 ($millions)s.t. : x1 +4x2 +4x4 +4x5 +3x6 +2x7 + 8x8 +2x9 +6x10 ≤ 25 3x1

42、+6x2 +2x3 +6x4 +6x5 +6x6 +4x7 +11x8 + 5x9 +12x10 ≤ 50 6x1 + 8x2 +7x3 +8x4 +10x5+8x6 +7x7 +15x8 +13x9+14x10≤ 75 10x1+12x2+12x3+12x4+15x5+11x6+ 8x7 +17x8 +14x9+15x10 ≤ 100 11x1+13x2 +1

43、2x3+18x4+20x5+16x6+13x7 +18x8+15x9+17x10 ≤125.,Let xi = 1 如果投資項(xiàng)目i; 0 不投資項(xiàng)目 i(i = 1, …,10).,Spreadsheet Solution,x1 +x2 +x3≥ 1 x4 +x5 ≤ 1 x7 ≤ x6 xi(i = 1, …,10). 等于0或1 are binary variables,二、固定成本

44、問(wèn)題 例5．高壓容器公司制造小、中、大三種尺寸的金屬容器，所用資源為金屬板、勞動(dòng)力和機(jī)器設(shè)備，制造一個(gè)容器所需的各種資源的數(shù)量如表所示。不考慮固定費(fèi)用，每種容器售出一只所得的利潤(rùn)分別為 4萬(wàn)元、5萬(wàn)元、6萬(wàn)元，可使用的金屬板有500噸，勞動(dòng)力有300人/月，機(jī)器有100臺(tái)/月，此外不管每種容器制造的數(shù)量是多少，都要支付一筆固定的費(fèi)用：小號(hào)是l00萬(wàn)元，中號(hào)為 150 萬(wàn)元，大號(hào)為200萬(wàn)元。現(xiàn)在要制定一個(gè)生產(chǎn)

45、計(jì)劃，使獲得的利潤(rùn)為最大。,解：這是一個(gè)混合整數(shù)規(guī)劃的問(wèn)題。 設(shè)x1，x2， x3 分別為小號(hào)容器、中號(hào)容器和大號(hào)容器的生產(chǎn)數(shù)量。各種容器的固定費(fèi)用只有在生產(chǎn)該種容器時(shí)才投入，為了說(shuō)明固定費(fèi)用的這種性質(zhì)，設(shè) yi = 1(當(dāng)生產(chǎn)第 i種容器, 即 xi ＞ 0 時(shí)) 或0（當(dāng)不生產(chǎn)第 i種容器即 xi = 0 時(shí)）。當(dāng)投入了固定成本時(shí)，才能生產(chǎn)相應(yīng)的產(chǎn)品，故引入約束為 xi ≤ M yi

46、 ，i =1，2，3，M充分大，(通常M可取xi 的最大取值或一個(gè)上界值)。當(dāng) yi = 0 時(shí)，xi = 0 這樣我們可建立如下的數(shù)學(xué)模型： Max z = 4x1 + 5x2 + 6x3－100y1 － 150y2 － 200y3 s.t. 2x1 + 4x2 + 8x3 ≤ 500 2x1 + 3x2 + 4x3 ≤ 300

47、x1 + 2x2 + 3x3 ≤ 100 xi ≤ M yi ，i =1，2，3，M 充分大正數(shù)，在這里可取M＝200 xj ≥ 0 yj 為0--1變量，i = 1,2,3,固定成本問(wèn)題Fixed Costs Example #3,Woodridge Pewter錫鉛合金Company生產(chǎn)三種產(chǎn)品 is a manufacturer of three pewt

48、er products: platters淺盤(pán), bowls碗, and pitchers有柄水罐.The manufacture of each product requires Woodridge to have the appropriate machinery and molds available. The machinery and molds for each product can be rented at the f

49、ollowing rates對(duì)于每種產(chǎn)品生產(chǎn)所需的的加工機(jī)器和模具，根據(jù)下列費(fèi)率來(lái)租賃: for the platters,淺盤(pán)費(fèi)用$400/week; for the bowls,碗$250/week; for the pitcher,有柄水罐$300/week.每種產(chǎn)品生產(chǎn)數(shù)據(jù)如下Each product requires the amounts of labor and pewter given in the table bel

50、ow. The sales price and variable cost are also given in the table.,Question: 應(yīng)生產(chǎn)哪些產(chǎn)品，生產(chǎn)數(shù)量,線(xiàn)性規(guī)劃模型,設(shè) Let x1 = 生產(chǎn)淺盤(pán)的數(shù)量Number of platters produced, x2 =生產(chǎn)碗的數(shù)量Number of bowls produced,x3 =生產(chǎn)有柄水罐的數(shù)量Number of pitchers prod

51、uced, 有 xi ≤ 99 (i = 1, 2, 3). yi = 1 如果租賃生產(chǎn)產(chǎn)品i 的加工機(jī)器和模具if lease machine and mold for product i; 否則yi = 0 otherwise (i = 1, 2, 3).整數(shù)規(guī)劃模型為Max Profit = (100–60)x1 + (85–50)x2 + (75–40)x3 –400y1 –250y2 –300

52、y3subject toLabor:3x1 + x2 + 4x3 ≤ 130 hoursPewter:5x1 + 4x2 + 3x3 ≤ 240 pounds當(dāng)加工機(jī)器和模具租賃時(shí)，才能生產(chǎn)Allow production only if machines and molds are purchased: x1 ≤ 99y1x2 ≤

53、 99y2x3 ≤ 99y3and xi ≥ 0, and yi 為0-1變量are binary (i = 1, 2, 3).,Spreadsheet Solution,一些應(yīng)用例子,固定投資方案的資金預(yù)算 Interfaces 1990年7－8月號(hào)土耳其煉油公司運(yùn)用BIP 將數(shù)千百萬(wàn)的投資用于擴(kuò)建煉油設(shè)施和能源儲(chǔ)備上 選址 Interfaces 1997年1－2月號(hào)，AT&T公司運(yùn)用BIP模型幫

54、助其客戶(hù)選擇電話(huà)營(yíng)銷(xiāo)中心，1988年AT&T公司為其46個(gè)客戶(hù)快速而準(zhǔn)確的作出了選址決策設(shè)計(jì)生產(chǎn)與配送網(wǎng)絡(luò) Interfaces 1995年1－2月號(hào)數(shù)字設(shè)備公司對(duì)公司整個(gè)全球供應(yīng)鏈進(jìn)行重整，年制造成本節(jié)省$500百萬(wàn)，物流成本節(jié)省$300百萬(wàn)，所需資金總額減少了$400百萬(wàn),規(guī)劃相關(guān)活動(dòng) Interfaces1995年1－2月號(hào)，中國(guó)國(guó)家計(jì)劃委員會(huì)為了最小化折現(xiàn)成本，和世界銀行合力開(kāi)發(fā)了一個(gè)BIP模型，用于指導(dǎo)決策1

55、5年內(nèi)在能源領(lǐng)域投入至少$2,400億的規(guī)劃，在15年內(nèi)，會(huì)為中國(guó)節(jié)省近$64億 規(guī)劃資產(chǎn)剝離 Interfaces1987年1－2月號(hào)荷馬特發(fā)展公司面臨的一個(gè)主要問(wèn)題是如何出售其購(gòu)物中心和辦公樓。有100多處資產(chǎn)需要在10年內(nèi)售出。通過(guò)運(yùn)用BIP指導(dǎo)決策，整個(gè)資產(chǎn)剝離計(jì)劃的收入增加了$40百萬(wàn) 航空方面的應(yīng)用 Interfaces1994年1－2月號(hào)Delta 航空公司運(yùn)用一個(gè)大型的整數(shù)規(guī)劃模型（包括40,000個(gè)函數(shù)約束，

56、20,000個(gè)0－1決策變量，40,000個(gè)一般整數(shù)變量。）來(lái)求解飛機(jī)的分配問(wèn)題。每年可為公司節(jié)省近$100百萬(wàn) Interfaces1989年7－8月號(hào)以及1991年1－2月號(hào)美洲航空公司 運(yùn)用BIP模型解決其每月的人員規(guī)劃問(wèn)題，每年節(jié)省了$20多百萬(wàn),All references available for download at www.mhhe.com/hillier2e/articles,Some Other Applic

57、ations,Dispatching Shipments貨物配送Should a certain route be selected for a truck? Should a certain size truck be used? Should a certain time period for departure be used?Examples: Quality Stores (1987), Air Products and

58、Chemicals, Inc. (1983), Reynolds Metals Co. (1991), Sears, Roebuck and Company (1999)Scheduling Interrelated ActivitiesShould a certain activity begin in a certain time period?Examples: Texas Stadium (1983), China (19

59、95)Scheduling Asset Divestitures安排資產(chǎn)出售Should a certain asset be sold in a certain time period?Example: Homart Development (1987)Airline Applications:航空業(yè)中的應(yīng)用Should a certain type of airplane be assigned to a certain

60、flight leg? Should a certain sequence of flight legs be assigned to a crew?Examples: American Airlines (1989, 1991), Air New Zealand (2001)All references available for download at www.mhhe.com/hillier2e/articles,0-1應(yīng)用類(lèi)

61、型 Applications of Binary Variables,Making “yes-or-no” type decisionsBuild a factory?Manufacture a product? Do a project?Assign a person to a task?Fixed costs (charge) problemIf a product is produced, must incur a f

62、ixed setup cost.If a warehouse is operated, must incur a fixed cost.Either-or constraintsProduction must either be 0 or ≥ 100.Subset of constraintsmeet k out of N constraints.,含有相互排斥約束條件選擇,兩個(gè)約束條件選一個(gè)問(wèn)題 假設(shè)我們要從以下兩個(gè)約束條

63、件中任選一個(gè) x1+x2≤300 1.5x1+ 0.8x2≤320引進(jìn)一個(gè)0—1變量y和充分大的正數(shù)M，,將上述問(wèn)題變?yōu)椋?x1 + x2 ≤300 +M(1－ y) 1.5x1+ 0.8x2 ≤320 +M y如果將y記作y2， 1－ y記作y1 ，則有 x1 + x2 ≤300 +M y1

64、 1.5x1+ 0.8x2 ≤320 +M y2 y1 + y2＝1 y1 ， y2為0—1變量,m個(gè)約束條件中選k個(gè)約束問(wèn)題（ k ≤m ）設(shè)有m個(gè)約束，需從m個(gè)約束中恰好有k個(gè)約束成立 a11 x1 + a12 x2 + … + a1n xn ≤ b1 …… …… am1 x1 + am2 x2 + … + amn

65、 xn ≤ bm需從m個(gè)約束中恰好選擇k個(gè)約束成立,則問(wèn)題可表示成 或 a11x1 + a12x2 + … + a1nxn≤ b1+My1 a11x1 + a12 x2 + … + a1nxn≤b1 + M(1- y1) …… …… am1x1+am2 x2 +… + amnxn≤bm+ Mym am1x1+a

66、m2 x2 +… + amnxn≤bm+ M(1-ym) y1 + y2 + … + ym＝m－k y1 + y2 + … + ym＝k 如果至多有k個(gè)成立 ： y1 + y2 + … + ym≥m－k,,滿(mǎn)足若干約束,Consider a linear programming model with the following constraints, and suppose t

67、hat meeting 3 out of 4 of these is good enough滿(mǎn)足3個(gè)以上約束12x1 + 24x2 + 18x3 ≥ 2,40015x1 + 32x2 + 12x3 ≥ 1,80020x1 + 15x2 + 20x3 ≤ 2,00018x1 + 21x2 + 15x3 ≤ 1,600,Meeting a Subset of Constraints,Let yi = 1 if constraint

68、i is enforced; 0 otherwise.Constraints:y1 + y2 + y3 + y4 ≥ 312x1 + 24x2 + 18x3 ≥ 2,400y1(or 2400－ M (1 – y1))15x1 + 32x2 + 12x3 ≥ 1,800y2 (or 1800－M (1 – y1))20x1 + 15x2 + 20x3 ≤ 2,000 + M (1 – y3)18x1 + 21x2 + 15x

69、3 ≤ 1,600 + M (1 – y4)where M is a large number.,求佳產(chǎn)品公司的生產(chǎn)計(jì)劃,研發(fā)部門(mén)研發(fā)了一些新產(chǎn)品為了避免過(guò)度多元化 管理部門(mén)做出如下要求:約束1 From the three possible new products, at most two should be chosen to be produced.三種新產(chǎn)品中,至多選擇兩種生產(chǎn)每種產(chǎn)品可以在兩個(gè)工廠生產(chǎn). 為了便于管理