第六章--整數(shù)規(guī)劃應(yīng)用運籌學(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 指派問題,求整數(shù)解的線性規(guī)劃問題，不是用四舍五入法或去尾法對線性規(guī)劃的非整數(shù)解加以處理都能解決的，而要用整數(shù)規(guī)劃的方法加以解決。在整數(shù)規(guī)劃中，如果所有的變量都為整數(shù)，則稱為純整數(shù)規(guī)劃問題；如果有一部分變量為整數(shù)，另一部分變量可以不取整數(shù)，則稱之為混合整數(shù)規(guī)劃問題。在整數(shù)規(guī)劃中，如果變量的取值只限于0和1，這樣的變量我們稱之為0-1變量。在純整數(shù)規(guī)劃和混合整數(shù)規(guī)劃問題中，如果所有的變量都為0-1變量，則稱之為0-1規(guī)

3、劃。,例1 TBA 航空公司飛機采購問題Airlines Problem,線性規(guī)劃模型設(shè)Let S = 購買的小飛機數(shù) Number of small airplanes to purchaseL = 購買的大飛機數(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,線性規(guī)劃的可分性假設(shè) (divisibility Assumptio

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

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

7、;1　整數(shù)規(guī)劃的圖解法,例1. 某公司擬用集裝箱托運甲、乙兩種貨物，這兩種貨物每件的體積、重量、可獲利潤以及托運所受限制如表所示。 P162甲種貨物至多托運4件，問兩種貨物各托運多少件，可使獲得利潤最大。解：設(shè)x1 、 x2分別為甲、乙兩種貨物托運的件數(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、個約束，就是一個線性規(guī)劃問題。利用圖解法，,得到線性規(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)的線性規(guī)劃的最大目標(biāo)函數(shù)值；任何求最小目標(biāo)函數(shù)值的純整數(shù)規(guī)劃或混合整數(shù)規(guī)劃的最小目標(biāo)函數(shù)值大于或等于相應(yīng)的線性規(guī)劃的最小目標(biāo)函數(shù)值。,,§2

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

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

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

13、最優(yōu)解為整數(shù)，從該最優(yōu)解的目標(biāo)函數(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)修改 ，找出所有未 分枝問題目標(biāo)函數(shù)值最大者，為新的上界當(dāng)改變完上、下界 ， 后，若 ＝ ，則所有分枝均已查明，得到 A0的最優(yōu)解， 若 ＞ ，則說明仍有分枝未查明，返回到第四步,例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對應(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 ,因為1<x2<2,為了使x2整數(shù)化,剔除1<x2<2對應(yīng)的可行域。為此,增加約束條件x2≤1及x2≥2,于是可行域R0可分解成兩個小可行域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,無解 ×,考察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ī)劃B0Z0=6.79x1=3.93 x2=1.43,,,x2≤1,x2≥2,線性規(guī)劃B1Z1 =5.5x1=3.5 x2=1,,,線性規(guī)劃B2Z2 =6.5x1=2.5 x2=2,,,,線性規(guī)劃B4無可行解,x1≥3,x1≤2,,線性規(guī)劃B3Z3 = 6.4x1=2 , x2=2.2,,,,x2≥3,x2≤2,,線性規(guī)劃B5Z5=6x1=2 , x2=2,線性規(guī)劃B6Z5=6

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

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

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

28、測情況見表所示 (單位：萬元)。但投資總額不能超過720萬元，問應(yīng)選擇哪幾個銷售點，可使年利潤為最大?,解：設(shè)：0--1變量 xi = 1 (Ai 點被選用）或 0 (Ai 點沒被選用） 這樣我們可建立如下的數(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個投資地點，如何表示？2) 或選擇A

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

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

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

33、 x1, x2, x3, x4 ＝0或1.求解得： x1 ＝x2 ＝1, x3 ＝ x4 ＝0。 NPV = 13 (百萬）。即在洛杉磯和舊金山各建一個工廠，不建倉庫,,靈敏度分析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萬元資金最優(yōu)方案是在洛杉磯和舊金山各建一個工廠。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百萬資金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萬美元以下，凈現(xiàn)值減400萬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.增加一百萬，可增加4百萬的凈現(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萬資金時，最好的方案是在舊金山增加一倉庫。,投資分析 Investment Analysis,A company is pla

38、nning their capital budget over the next several years.10個項目可供投資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.計算未來五年每個項目所需的投資現(xiàn)金，具體數(shù)字見下張PPT假定需要滿足一下要求, suppose there are the following contingency constraints:at least one of project 1, 2 or 3 must be done,1,2,3至少做一個project 4 a

40、nd project 5 cannot both be done, 4,5不能同時做project 7 can only be done if project 6 is done.項目7只有在項目6投資的情況下才能投資 ( project 7 can not be done unless project 6 is done)Question: 應(yī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 如果投資項目i; 0 不投資項目 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、問題 例5．高壓容器公司制造小、中、大三種尺寸的金屬容器，所用資源為金屬板、勞動力和機器設(shè)備，制造一個容器所需的各種資源的數(shù)量如表所示。不考慮固定費用，每種容器售出一只所得的利潤分別為 4萬元、5萬元、6萬元，可使用的金屬板有500噸，勞動力有300人/月，機器有100臺/月，此外不管每種容器制造的數(shù)量是多少，都要支付一筆固定的費用：小號是l00萬元，中號為 150 萬元，大號為200萬元?，F(xiàn)在要制定一個生產(chǎn)

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

46、 ，i =1，2，3，M充分大，(通常M可取xi 的最大取值或一個上界值)。當(dāng) yi = 0 時，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,固定成本問題Fixed Costs Example #3,Woodridge Pewter錫鉛合金Company生產(chǎn)三種產(chǎn)品 is a manufacturer of three pewt

48、er products: platters淺盤, 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對于每種產(chǎn)品生產(chǎn)所需的的加工機器和模具，根據(jù)下列費率來租賃: for the platters,淺盤費用$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ù)量,線性規(guī)劃模型,設(shè) Let x1 = 生產(chǎ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 的加工機器和模具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)加工機器和模具租賃時，才能生產(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月號土耳其煉油公司運用BIP 將數(shù)千百萬的投資用于擴(kuò)建煉油設(shè)施和能源儲備上 選址 Interfaces 1997年1－2月號，AT&T公司運用BIP模型幫

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

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

56、20,000個0－1決策變量，40,000個一般整數(shù)變量。）來求解飛機的分配問題。每年可為公司節(jié)省近$100百萬 Interfaces1989年7－8月號以及1991年1－2月號美洲航空公司 運用BIP模型解決其每月的人員規(guī)劃問題，每年節(jié)省了$20多百萬,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)用類

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.,含有相互排斥約束條件選擇,兩個約束條件選一個問題 假設(shè)我們要從以下兩個約束條

63、件中任選一個 x1+x2≤300 1.5x1+ 0.8x2≤320引進(jìn)一個0—1變量y和充分大的正數(shù)M，,將上述問題變?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個約束條件中選k個約束問題（ k ≤m ）設(shè)有m個約束，需從m個約束中恰好有k個約束成立 a11 x1 + a12 x2 + … + a1n xn ≤ b1 …… …… am1 x1 + am2 x2 + … + amn

65、 xn ≤ bm需從m個約束中恰好選擇k個約束成立,則問題可表示成 或 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個成立 ： y1 + y2 + … + ym≥m－k,,滿足若干約束,Consider a linear programming model with the following constraints, and suppose t

67、hat meeting 3 out of 4 of these is good enough滿足3個以上約束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)計劃,研發(fā)部門研發(fā)了一些新產(chǎn)品為了避免過度多元化 管理部門做出如下要求:約束1 From the three possible new products, at most two should be chosen to be produced.三種新產(chǎn)品中,至多選擇兩種生產(chǎn)每種產(chǎn)品可以在兩個工廠生產(chǎn). 為了便于管理