217 指派，0代表不指派）；目標函式是所有指派的總成本；左端約束值是能夠被分配給代理的任務量和分配給任務的代理數；右端約束值為每個代理能夠解決的任務數（1）和每個任務所需要的代理數（1）。 福爾公司指派問題的工作表模型和Excel 求解過程如圖7-16所示。 福爾公司專案負責人（起點節點） 特瑞卡爾邁克孟德客戶（終點節點） 2 10 6 15 18 14 3 9 5 3 模型最小時間 1 26 客戶（終點節點） 2 專案負責人（起點節點） 特瑙卡爾邁克孟德總計 3 總計圖7-16 3 福爾公司指派問題的 Excel 的解決方案 7A. 2.1 模型資料和描述性標誌列在單元格 Al:D7內。注意，我們沒有輸人供給和需求量，因為轉運問題中它們一般情況下為1。在工作表底部出現的線性規劃模型的4個關鍵元素都被塗上陰影了。 決策變數 B16:D18 單元格是為決策變數保留的。最優值顯示為xi2 =1，*ns=1，*s1 =1，所有其他決策變量都等於0，也就是說沒有被指派。 目標函式在單元格C12 中輸人公式=SUM PRODUCT （B5: D7,B16: D18），用來計算每個指派完成工作需要的總時間。最短時間的解決方案所需的總工作時間為26天。 左端億單元格 E16:E18 為每個專案負責人所接任務左端值約東條件，單元格B19:D19的左端值約束條件要求每個任務都必須要指派一個專案負責人。 單元格 E16=SUM （B16:D16）（複製到 E17:E18） 單元格 B19=SUM （B16:B18）（複製到C19:D19） 右端僵單元格G16:G18 為右端值任務量約束條件，所有的右端任務量約束單元格值都為1。 7A. 2.2 Excel 解決方案圖7-16所示的是透過工具欄中的 Solver 求解得出的最優解決方案。在 Solver Parameters 對話方塊中輸入正確的值，並選擇標準“單純線性規劃（Stadard Simplex LP）”，指定選項“假設非負”（Assume Non-Negative），然後確認單擊“解決”（Solver）。圖7-17是 Solver Parameters對話方塊中輸入的資訊。 7A.3 轉運問題我們用來描述轉運問題的工作表模型能用在這一章提到的所有的網路流量問題上（運輸、轉運和指派）。 我們把工作表分成兩個部分：弧部分和節點部分。可透過列出瑞恩電子公司轉運問題（見7.3節）的工作表模型和解決方案來描述Excel 的求解過程。參考圖7-18，我們已經描述了所需的步驟，要素都被塗上影了。
218 資料、模型與決策：管理科學篇 7A. 3.1 模型弧部分在單元格 A3:D16 中。對於每一條弧，它的起點節點和終點節點都在單元格 A5:B16 中列出。弧的成本列在單元格CS： C16，單元格 D5:D16 是給決策變數保留的 （弧上的運輸量）。 節點部分的資料放置在工作表單元格 FS：K14 中。各個節點在單元格 F7:F14中。在相應單元格內依次輸人如下公式來表達每個節點的流入量和流出量。 流入量： $16:0$18 Standad SimglLP $B$19：$D$19 = $B$21：$0$21 $E$16:YE$18<： $G$16：$G$18 圖7-17 Solver Parameters 對話方塊中輸入的福斯特公司問題的資訊單元格C9=D5+D6 單元格C10=D6+D8 單元格G11 = D9+D13 單元格G12=D10+D14 單元格G13= D11+D15 單元格 C14 = D12+ D16 瑞恩電子公司轉運問題弧起點節點終點節點丹佛堪薩斯城路易斯維爾亞特蘭人 |堪薩斯城亞特竺天路易斯維爾堪薩斯城底特律璂薩斯城邁阿密堪薩斯城達拉斯堪薩斯城新奧爾良路易斯維爾底特律路易斯維外遊阿密路易斯維外： 達拉斯路易斯維爾新奧爾良成本 2 3 運輸量運輸量 2 6 4 節點八佛亞特蘭大堪薩斯城路易斯維丕底特律邁阿密達拉斯新奧爾良進出 600 400 550 450 淨運輸量供給八籍八經 550 450 200 150 350 300 5 總成本圖7-18 瑞恩電子公司問題的 Excel 解決方案流出量： 單元格 H7=SUM （D5:D6） 單元格 H8=SUM （D7:D8） 單元格 H9=SUM（D9:D12） 單元格 H10=SUM（D13:D16） 單元格 17:114中表示的運輸量為每個節點的流出量減去該節點的流人量。對於供給節點，流出量超出流人量，從而產生一個正的淨運輸量值。而對於需求節點，流出量小於流人量，因此產生一個負的淨運輸量值。 “淨”運輸量值在單元格 K7:K14 中。需要注意的是，需求節點的淨運輸量值為負。 和前面的工作表單格式一樣，這裡被 Solver要求的關鍵元素同樣被塗上陰影。 決策變數單元格 D5:D16 中的資料為決策變數，用來表示每條弧上的最優運輸量值。 目標函式在單元格 118中輸人公式 SUMPRODUCT （CS: C16,DS: D16），用來計算和解決與方案相關的全部成本總額。從圖中我們可以看出，最小成本總額為5200美元。 左端儃約東條件的左端值表示每個節點的淨運輸量。單元格 17:114專門用來儲存這些約束條件。
第了章運輸、指派與轉運問題 219 單元格17=H7-G7 （複製到I8:114中） 右端億約束條件的右端值表示每個節點的供給量。單元格 K7:K14 專門用來儲存這些值。（注意：4個需求節點的供給量是負值。） 7A. 3.2 Excel解決方案開啟下拉選單 Tools，點選 Solver， 在開啟的 Solver Parameters 對話方塊中鍵入合適的值，選擇 Standard Simplex LP，從而實現 Assume Non-Negative 的功能。最後點選 Solve。Solver Parameters 對話方塊中需要鍵入的其他信息參見圖7-19。 $0$5：$0$16 $1$7：$7$8 <= $K$7：$K$8 5$9：$7$14 = $K$9：$K$14 Stadiard Simpler LP 圖7-19 瑞恩電子公司解決方案中使用到的 Solver Parameters 對話方塊第8章整數線性規劃本章，我們將討論這樣一類問題，這類問題可以被構建成線性規劃的模型，並且其中至少有一個變數是整數。這類問題稱做整數線性規劃問題。如果在這類問題中，既有整數變數，又有非整數變量，則我們將其稱為混合整數線性規劃。在應用整數線性規劃時，經常要求變數等於0或1，這些變量稱為0-1變數或二進位制變數。如果所有變數均為0-1變數，我們稱此類問題為0-1 整數線性規劃。 整數變數（特別是0-1變數）可以使建模變得十分容易、靈活，從而使得線性規劃的應用得到了廣泛的普及。例如，專欄8-1 介紹了紐西蘭航空公司如何使用0-1 整數規劃來有效安排分配該公司的員工。專欄8-2中介紹了金屬谷容器公司（VMC）如何透過混合整數規劃來安排谷司公司啤酒鋁質易拉罐的生產以及貝爾卡公司開發的混合整數規劃模型是如何透過使用批次訂貨進而獲得折扣的方法替客戶節省開支的。在本章讀者還將看到整數規劃的其他一些應用的範例。 本章的主要內容就是對整數線性規劃的應用做詳細介紹。首先，我們將討論整數線性規劃的不同分類。隨後，我們將介紹整數線性規劃的公式解法、圖解法以及計算機解法。在第8.3 節中，我們將討論5個使用0-1變數的整數線性規劃的應用例項：資金預算問題、固定成本問題、分佈系統設計問題、銀行選址問題和市場份額最最佳化問題。在第8.4 節中，我們將再舉一個例子來說明使用0-1變數給規劃帶來的巨大靈活性和便利性。本章的附錄將舉例說明如何使用Excel 電子表格來求解整數規劃問題。 但是，雖然整數變數（尤其是0-1變數）給建模帶來了一定的靈活性，它的代價是：通常這種含有整數變數的問題也比較難以求解。舉例來說：一個含有上千個連續變數的線性規劃問題，可以使用任何一種商業線性規劃解法進行求解。但是一個僅含有少於100個全整數變數的線性規劃問題卻極難解決。經驗豐富的管理科學家能夠分辨出哪些整數線性規劃是容易求解的，哪些可能是無解的或者無法求解的。商用計算機軟體包，例如 MPSX-MIP®、OSL®、CPLEX®和 LINDO 都有強大的整數規劃功能。管理科學家較件和電子表格軟體，如 Excel，可以用來求解小型整數線性規劃問題。
第8章整數線性規劃 221 專欄8-1 實踐中的管理科學紐西蘭航空公司的職員任務規劃我們在第1章就已經提到，管理科學在航空業得到了廣泛的應用（參見專欄1-1）。紐西蘭航空公司是紐西蘭最大的國內、國際航空公司。在過去的15年中，紐西蘭航空公司開發了一套整數規劃模型來規劃職員的任務。 飛機每次出航前12周，紐西蘭航空公司就開始為該次航行制定任務規劃。隨後，按照該規劃執行飛行任務。職員規劃的問題包括：為飛行員以及乘務員制定任務計劃時刻表，分兩個階段進行：第一階段，制定航行職責（ToD）計劃，這個計劃用以明確飛行員和乘務員在航行中需要執行的一系列任務。ToD計劃分為職責週期（主要進行航行、訓練等）和滯留（臨時支配）週期，共2個週期，輪換執行，該週期可能只有一天，也可能為期幾天。ToD 計劃中並沒有考慮單個職員需要執行的航行任務。第二階段，安排每個職員的航行任務，該階段的計劃稱為“花名冊”問題。 紐西蘭航空公司使用整數規劃模型來求解 ToD 問題和“花名冊”問題。在ToD 問題的整數規劃模型中，每個變數要麼為1，要麼為0。其中，每個1和0相應地代表每個職員（包括飛行員和乘務員） 執行某項任務的可能性。每個0-1約東對應於一次具體的航班，並且確保該次航班屬於一個Tol計劃。」代表執行第j次TOD 的成本，目標是使總成本最小化。紐西蘭航空公司要為每一類員工（其中一類為飛行員，另一類為乘務員）單獨求解一個ToD問題。 在花名冊問題中，透過求解TOD 問題來為每個員工構建工作線（LoW），並且使用0-1變數進行整數規劃。其中0-1代表每個員工可能的LOW。每個員工對應一個單獨的約束，從而可以確保每個員工僅能被安排一個LoW。ToD的其他相關約束必須在花名冊問題的可行性方案中包括。 紐西蘭航空公司開發的員工規劃最佳化方案使其獲“利”匪淺。在過去15年，紐西蘭航空公司開發這些系統共花費近200萬紐西蘭元。但是這些規劃系統以及最佳化系統每年卻能為紐西蘭航空公司節省1560萬紐西蘭元。1999年，使用這些系統節省的費用佔紐西蘭航空公司淨營業利潤的11%。除了直接的經濟收益外，該系統還有許多無形的益處，如能在更短的時間內更有效地求解問題，而且越來越少地依賴於少數熱練的規劃者；當既定計劃發生徽小變化時，求解起來也表現得十分靈活，並且還能更有效地履行法律和合同要求。 資料來源：基於：E. Rod Buchers el. al.， “Optimized Crew Scheduling et Air New Zealand， " Interfaces， （January/February 2001）：30-56. 註釋與評論 1. 因為整數線性規劃比一般的線性規劃難以求解，所以當簡單地將一般線性規劃的解進行近似就可以解決問題時，不應採取此規劃。在許多線性規劃問題中，如前面幾章中所提到的，近似的方法對目標函式幾乎不產生經濟學上的影響，所以是完全可行的。然而，在諸如決定生產多少臺噴氣發動機的一些問題中，近似的影響將是比較大的，因而需要應用整數規劃方法來解決。 2. 有些線性規劃問題有一種特殊的結構，可以保證變數是整數型的。第7章中提到的指派問題、 遠輸問題和轉運問題就是這種結構。如果運輸和轉運的供給與需求問題為整數型，那麼最優線性規劃解法將會得出整數型載運量。在指派問題中，最優線性規劃解法必將包括0-1變數。所以，在這些有特殊結構的問題中，應用一般線性規劃方法就可以得到最優的整數結果。如果沒有必要，儘量不要用整數線性規劃。 8.1 整數線性規劃的分類本章所研究的線性規劃問題和前幾章研究的問題的惟一區別是：線上性規劃問題中，至少有一個變數是整數型的。如果所有變數均為整數，就稱其為全整數線性規劃。下面透過構建一個含有2個整
222 資料、模型與決策：管理科學篇數變數的全整型線性規劃模型來說明： max 2x，+3x2 S.t. 3x，+3%≤12 2/3x，+1x≤4 Ix，+2x，≤6 X」，X≥0，且為整數請注意，如果去掉此模型中的“整數”一詞，我們將得到我們所熟悉的雙變數線性規劃。去掉整數要求後得到的線性規劃稱做整數線性規劃的LP 鬆弛。 如果只有一些變數是整數而非全部都是，則稱做混合整數線性規劃。下面是一個有兩個變數的混合整數線性規劃。 max 3%， +4x S.t. -1x， +2x≤8 1x，+2x≤12 2x，+1x≤16 *，2≥0，且x，為整數去掉“x為整數”這個條件後，我們得到此混合整數線性規劃的LP鬆弛。 在某些應用軟體中，整數變數只取0或1。這類規劃被稱做0-1 整數線性規劃。讀者可以在本章的後面部分中發現，使用0-1變數可以使線性規劃很靈活、很容易求解。專欄8-2 描述瞭如何用一個含有0-1變數的混合整數線性規劃確定啤酒易拉罐的生產進度。生產線的換線用0-1變數來表示， 而產量則用連續變數來表示。 專欄82 實踐中的管理科學金屬谷容器公司啤酒易拉罐的生產金屬谷容器公司（VMC）為谷司釀酒廠的7個啤酒品牌生產易拉罐分別是：Coors Extra Gold， Coors Light, Coors Original, Keystone Ale, Keystone Ice, Keystone Light，和 Keystone Premium。 VMC 在6 條生產線上生產這些易拉罐，並分別儲存在3個不同的存貨點，然後將易拉罐從這些存貨點分別運輸到古司公司在科羅拉多州格爾登、田納西州孟菲斯和弗吉尼亞州謝南多厄的釀酒廠。 VMC在制定生產進度時遇到兩個重要問題。第一，每次更換生產線製造另一種易拉罐（改變標籤）時，新標籤準確套色這一過程非常耗時，結果會發生停工併產生廢料。第二，合理的進度安排能減少要從長期轉溝短期的庫存量。於是，VMC 工廠在制定最優生產進度時，有兩個成本是至關重要的：標籤轉換成本和儲存方式轉換成本。為了做出能使這兩個成本最小的生產計劃，VMC 為其生產進程開發了一個混合整數線性規劃模型。 此模型的目標函式要求每星期的標籤轉換成本與儲存方式的轉換成本之和最小化。生產過程中的一次標籤轉換用二進位制（0-1）變數來表示；在一個班次中一條生產線上生產同種型號標籤的產量用連續變數來表示，該變數同時也表示生產的每種易拉罐的庫存量；本週中已被轉為短期儲存的庫存量用其他連續變數來表示。 VMC的生產進度問題使用一臺個人電腦每週排一次。資料和儲存產出報表用Excel 工作表來輸入。其混合整數線性規劃問題用GAMS數學規劃系統進行求解。古司容器運作部的物流經理蘇姍稱這一系統的應用使每年的開支減少了169230 美元。 資料來源：基於：Elena Katok and Dennis Otl， "Using MixedInteger Progranming to Reduce Lsbel Changes in the Coors Aluminum Can Plant" •Interfaces（March/April 2000）：1-12
第8童整數線性規劃 223 8.2 全整數線性規劃的圖解法與計算機解法伊斯特伯恩房地產公司有200萬美元可用於購買新的租賃財產。經過篩選，公司已將投資專案的方案減少為連體別墅和公寓樓。每套連體別墅售價282 000 美元，現有5套空置。每幢公寓樓售價 400 000美元，而且開發商可以根據伊斯特伯恩的需要數量建房。 伊斯特伯恩的財產經理每月可以有140小時用來處理這些新置的財產，其中，每套連體別墅預計每月要花4小時，每幢公寓樓預計每月40小時。扣除抵押償還和經營成本後，年現金流量預計為：每套連體別墅10000美元；每幢公寓樓15 000美元。伊斯特伯恩的股東想知道在保證年現金流量最大的要求下，購買連體別墅和公寓樓的數量。 我們先定義決策變數如下： T——連體別墅的數量； A——公寓樓的數量。 現金流量（單位：1000美元）的目標函式為： max 10T+15A 必須滿足的3個約束條件是： 282T+400A ≤2 000 4T +40A ≤140 T ^ 5 變數『和A必須是非負的。而且， 連體別墅和（或）公寓樓均不可以拆開購買。因此，亇和A一定是整數型的。伊斯特伯恩房地產問題的模型即如下全整數線性規劃： max I0T+15A 8.t. 可用資金（單位：1000美元） 管理者的時間（小時） 可得連體別墅 5 管理者時間約束 282T+400A≤2 000 4T +40A ≤140 T ≤5 T, A≥0，且為整數最優LP鬆弛解 T=2.479,4=3.252 3 2 8.2.1 LP 鬆弛的圖解法可行城現在我們去掉T和A為整數的條 1 目標函式=73.574 可得貧金的來件，重新來求解伊斯特伯恩公司的 LP 鬆弛問題。運用第2章中的圖解步驟， 0 4 連體別墅可得能力約束 5 6 7 圖8-1即為最優的線性規劃解法，即 T=2.479 套連體別墅，A =3.252 幢公 2 3 連體別墅的數量圖8-1 用圖解法求解伊斯特伯態公司的問題寓樓。目標函式的最優值為73.574。 也就是說每年的現金流量是73 574美元。但是，不幸的是，伊斯特伯恩無法購買零星數量的連體別墅和公寓樓。所以需要進行進一步分析。 8.2.2 近似整數解的獲得大多數情況下，可以透過使用本節的方法來求得可接受的整數解。例如，某關於生產進度問題求
224 資料、模型與決策：管理科學篇得的線性規劃結果可能要求生產15132.4箱穀類食品。其近似結果為15132箱，而該近似解對目標函數的值及其結果的可行性只產生極小的影響。因此，近似是一個較好的方法。實際上，只要近似對目標函式的約束條件只產生極小的影響，大多數管理者都可以接受。此時，一個最優近似解就夠了。 然而，近似並不是一個萬能的方法。當決策變數取很小的數值就對目標函式的值和結果的可行性產生較大影響時，就需要一個最優的整數解。讓我們回到伊斯特伯恩公司的問題中來，重新檢驗一下近似解。伊斯特伯恩房地產問題LP 鬆弛後的最優結果是T=2.479套連體別墅，A =3.252 幢公寓樓。 由於每套連體別墅售價282000 美元，每幢公寓樓售價400 000 美元，如果近似得到一個整數解，將會對這個問題產生重大經濟影響。 假設我們把LP 鬆弛的解近似到整數：T=2，A=3。於如果問題只含有小於或等於形式的約是目標函式值為：10×2+15×3=65。而65 000美元的年束條件，並且變數的係數都是正數，用近現金流量比 LP 鬆弛的結果73754美元少很多。那麼有沒有似的方法一般都會找到可行解。 其他可能的近似解呢？對其他近似方法的研究表明：整數結果T=3，A=3不可行，因為這樣資金就超過了伊斯特伯恩公司現有的2000000美元；同理、『= 2，A=4也不可行。在這樣的情況下，近似得到此問題的最可行的整數結果：2套連體別墅，3幢公寓樓和65 000美元的年現金流量。但是，我們並不知道這一結果是否為該問題的最優整數結果。 近似到整數解是一個反覆試驗的方法。每一個近似解都必須經過可行性檢查和對目標函式值影響的檢查。即使當近似解是可行時，我們也無法保證我們找到了最優的整數解。稍後我們就會發現近似解（T=2，A=3）不是以上問題的最優解。 8.2.3 全整數問題的圖解法圖8-2說明了用圖解法求解伊斯特伯恩房地產整數線性規劃問題中所需要做的變化。首先，可行域圖幾乎和 LP鬆弛問題的一樣。然後，因為最優解一定是整數型的，我們用點標出可行的整數解。最後，不是將目標函式線向可行域的極值點移動，而是儘量將它著使目標函式最優的方向移動 （可行整數點之一）。參看圖8-2，我們看到當T=4 套連體別墅，A=3幢公寓樓時，得到最優整數值。目標函式值為10×4+15 ×2 =70，並得年現金流盧是70 000美元。 這一結果要比近似得到的最優解亇=2，A =3，年現金流量65 000 美元好得多。所以我們可以看到近似法並不是伊斯特伯恩公司房地產問題的最好的求解方法。 管理者時間約束可得資金約束 3 蕞優整數解 7=4,A=2 2 羽行城目標函式=70 一連體別墅 0 可得能力約來 3 4 5 6 連體別墅的數靈圖 8-2 用圖解法解決伊斯特伯恩公司的房地產問題注：點代表可行整數解 8.2.4 應用LP 鬆弛法建立約束邊界從伊斯特伯恩房地產問題的研究中，我們可以得出一個結論：一定要處理好最優整數解的值和LP 鬆弛後的最優解的值之間的關係。 在含有最大化問題的整數線性規劃中，L.P 鬆弛後的最優解的值就是最優整數解的值的上限。在含第8章整數線性規劃 225 有最小化問題的整數線性規劃中，LP 鬆弛後的最優解的值就是最優整數解的值的下限。 這一結論適用於伊斯特伯恩房地產問題。最優整數解的值為70000美元，LP 鬆弛後的最優解的值次73 574美元。於是，我們知道目標函式值的上限為73 574美元。 透過LP 鬆弛的上下限特性，我們可以得出結論：如果L.P 鬆弛的解恰好是整數，那麼，它也是該整數線性規劃的最優解。這一上下限的特性也可以用來確定近似解是否“足夠好”。如果一個近似的 LP 鬆弛解是可行的，並能使得到的目標函式值同LP 鬆弛的目標函式值幾乎一樣好，我們就認為該近似解是最優近似整數解。因此，我們也可以不用整數線性規劃來求解問題。 8.2.5 計算機解法正如前面所講，有很多商用軟體能夠求解整數線性規劃問題。一般來說，這些軟體可以求解那些含有上百個整數變數的問題，還有一些可以求解含有幾千個整數變數的特殊結構的問題。 管理科學家軟體可用來解決本章中的絕大多數整數線性規劃問題。若用管理科學家軟體來解決伊斯特伯恩房地產問題，輸人資料的工作表與一般的線性規劃一樣（見附錄2A）。然後，在完成了計算機求解的框架後，使用者必須指出哪些變量是整數型的。如圖8-3，將T和A定義為整數型，得出了最優整數解。當「=4 套連體別墅、 目標函式值= 變數 ------------- T A 約束 1 2 3 70.000 值 A =2幢公寓樓時，所得到的解的最大年現金流量 4.000 2.000 鬆弛/剩餘 -------- 72.000 44.000 1.000 為70000 美元。該鬆弛變數的值表明：還有 72 000美元的資金閒置，管理者仍有44 小時的空圖8-3 用管理科學豪軟體解決伊斯特伯恩公司房地產問題閒時間，有1幢連體別墅未賣出。 註釋與評論在附錄8A 中，我們將演示如何使用 Excel 求解整數線性規劃問題，如伊斯特伯恩房地產問題。 8.3 含有0-1變數的整數線性規劃的應用整數線性規劃在構建模型上的靈活性很大程度上是由於使用了0-1變數。在很多應用中，如果採取相應行動，則變數值取1，否則取0。0-1變數因此而提供著選擇的功能。本節所講的資金預算、 固定成本核算、分佈系統設計、銀行選址、產品設計和市場份額的應用問題都用到了0-1 變數。 8.3.1 資金預算愛斯柯德冰箱公司正在考慮隨後4年內的投資方案，這些方案有著不同的資金要求。面對每年有限的資金，管理者需要選擇最好的方案。每種方案的估計淨現值°、資金需求和4年內的可用資金見表8-1。 4個0-1 決策變數如下： 如果工廠擴建方案透過，P=1；如果杏決，P取0。 ◎ 估計淨現值是用淨現金流量貼現到第1年初得到的。
226 資料、模型與決策：管理科學篇表8-1 愛斯柯德冰箱公司的估計淨現值、資金需求和4年內的可用資金 （單位：美元） 淨現值第1年資金需求第2年資金需求第3年資金需求第4年資金需求工廠擴建 90 000 15 000 20 000 20 000 15 000 倉庫擴建 40 000 10 000 I5 000 20 000 $ 000 專案機髁更新 10 000 10 000 4000 新產品研發 37 000 15 000 10 000 10 000 10 000 可用資金總額 40 000 50 000 40 000 35 000 如果倉庫擴建方案透過，W=1；如果否決，W取0。 如果機器更新方案透過，M=1；如果否決，M取0。 如果新產品研發方案透過，R=1；如果否決，R取0。 在資金預算問題中，公司的目標函式是使資金預算的淨現值最大化。此問題有4 個約束條件，其一為4年中每年的可用資金。 該0-1整數線性規劃模型（單位：1000美元）如下： max 90P +40W+10M +37R s.t. 15P +10W+10M +15R≤40 20P +15W +10R≤50 20P+20W +10R≤40 15P +5W+4M +10R≤35 第1年的可用資金第2年的可用資金第3年的可用資金第4年的可用資金 P,W,M,R=0,1 圖8-4 為管理科學家軟體的整數規劃解。最優解是： P=1,W=1,M=1,R=0，此時淨現值為140 000 美元。因此，該公司將投資於工廠擴建、倉庫擴建和機器更新。如果投有額外的資金可用，研發新產品方案只能暫緩了。鬆弛變數的值（見圖8-4）表明該公司在第1 年有5000美元的剩餘，第2年有15 000美元的剩餘， 第4年有11000美元剩餘。對照研發新產品方案的資金需求，可知在第2年和第4年又有足夠的資金可用於此方案。但是，該公司必須在第1年和第3年各提供10000 美元的額外資金投資於新產品研發方案。 月標函式值= 變數 140.000 值 P W M R 約束 1.000 1.000 1.000 0.000 鬆弛/剩餘 1 2 3 4 -- 5.000 15.000 0.000 11.000 困8-4 愛斯柯鐮冰箱公司問題的管理科學取解決方案 8.3.2 固定成本核算在許多應用中，產品的成本由兩部分構成：其一為配置成本，即固定成本；其二為可變成本，直接與產量相關。0-1變數的應用，使得在生產應用軟體包中考慮配置成本成為可能。 我們可以將 RMC問題視為固定成本問題的例子。3種原料用來生產3種產品：一種燃料新增劑、 一種溶劑、一種地板清潔劑。使用以下決策變數： F—生產的燃料新增劑的噸數； S—一生產的溶劑的噸效； C——生產的地板清潔劑的噸數。 生產每噸燃料新增劑的利潤是40 美元，生產每噸溶劑的利潤是30美元，生產每噸地板清潔劑的第8章整數線性規劃 227 利潤是50美元。生產每噸燃料新增劑需要0.4噸原料1和0.6噸原料3；生產每噸溶劑需要0.5 噸原料1、0.2噸原料2和0.3噸原料3；生產每噸地板清潔劑需要0.6噸原料1、0.1噸原料2和0.3噸原料3。RMC共有20噸原料1、S噸原料2和21噸原料3。我們需要決定下一計劃期內的最優生產量。 RMC 問題的一個線性規劃模型如下： max 40F +30S+50C s.t. 0.4F +0.SS +0.6C≤20 原料1 0.25+0.1C≤5 原料2 0.6F +0. 3S+0.3C≤21原料3 F,S,C≥0 運用管理科學家軟體的規劃模型，我們得到一個最優解：27.5噸燃料新增劑、0噸溶劑和1.5 噸地板清潔劑，總價值為1850 美元，見圖8-5。 日標函式值= 變數 F S c 1850.00 值減少的成本 27.500 0.000 15.000 0.000 12.500 0.000 國8-5 用管理科學寂軟體對 RMC公司的問題進行求解 RMC 問題的這一線性規劃問題並不包含這些產品的配置成本。假設已知配置成本和3種產品的最高生產量如下： 產品分類配量成本（美元） 燃料新增劑 200 溶劑 50 地板清潔劑 400 最大生產量（噸） 50 25 40 我們現在可以利用0-1變數帶來的建模靈活性，把固定的配置成本加人到生產模型中。0-1變量定義如下： 如果生產燃料新增劑，則SF=1，否則，SF=0； 如果生產溶劑，則SS=1，否則，SS=0； 如果生產地板清潔劑，則SC=1，否則，SC =0。 利用這些變數，總的配置成本為： 200SF +50SS +400SC 現在我們可以重新寫出包括配置成本的目標函式。於是，淨利潤目標函式變為： max 40F +30S +50C -200SF -50SS -400SC 接下來，我們需要寫出生產能力的約束條件，使得：當配置變數等於0時，不允許生產相應的產品；當配置變數等於1時，可以大量生產該產品。對於燃料新增劑，我們加人如下條件： F≤SOSF 注意，在此條件下：SF =0時，不生產燃料新增劑；SF =1時，燃料新增劑可最多生產50噸。我們可以把配置變數看做一個開關。當它關著，就不允許生產；當它開著才允許生產。 利用0-1變數，為溶劑和地板清潔劑增加類似的生產能力約束條件，如下： S≤25SS C≤40SC 把所有的變數移到約束條件的左邊，得到RMC 向題的固定成本模型：
228 資料、模型與決策：管理科學篇 max S.t. 40F +30S +5OC -200SF -50SS -400SC 0.4F +0.5$+0.60 0.2S+0.1C 0.6F +0.3S+0.3C F - 50SF ≤20 ≤21 ≤0 S -25SS 原料1 原料2 原料3 F的最大值 S的最大值 C的最大值 C -40SC F,S,C≥0;SF, SS, SC=0,1 我們用管理科學家軟體求解含有配置成本的 RMC 問題。如圖8-6所示，最優解為25噸燃料新增劑和 20噸溶劑。扣除配置成本後的目標函式值為1350美元。燃料新增劑和溶劑的配置成本為200美元+50美元=250美元。最優解的結果為SC=0，表示應取消昂貴的400美元的地板清潔劑配置成本，因此不應生產地板清潔劑。 構建一個固定成本模型的關鍵是各個固定成本 0-1變數的引入，以及相應的生產變數上下限的設目標肉數值= 變數 F S c SF SS SC 1350.000 值 25.000 20.000 0.000 1.000 1.000 0.000 用為，當配置變數y=0時不允許生產，而在y=1時允許生產。最大生產量M的值需要足夠大，以滿足所有正常生產的水平。但是，研究顯示，選擇過大的變數 M 值會降低求解問題的速度。 8.3.3 分佈系統設計馬丁貝克公司在聖路易斯經營一家年產量為 30 000件產品的工廠。產品被運輸到位於波士頓、亞特蘭大和休斯敦的地區分銷中心。由於預期將有需求的增長，馬丁貝克公司計劃在底特律、託菜多、丹佛和堪薩斯城中的一個或多個城市建立新工廠以增加生產力。在上述4個城市中建立工廠的年固定成本和年生產能力如表1。 該公司的長期計劃小組對3個地區分銷中心的年需求量做了如表2所示的預測。 每件產品從各工廠到各分銷中心的運費見表8-2。 圖8-7描述了馬丁貝克公司可能的分銷系統網路圖， 其中包含了每一個可能的工廠地點、生產能力和需求基，均以1000單位。這一網路演示圖針對的是聖路易斯一個工廠和4個擬議工廠的選址的運輸問題。但是，將建立哪一個或哪些工廠，還未最後決定。 現在說明在該分佈系統設計問題中，如何應用 0-1麥量建立模型來選揮最優的廠址、確定從各工廠到各分銷中心的運輸量。我們可以用以下的0-1變量來表示建立工廠的決策。 目標工廠底特律托萊多丹佛堪薩斯城表1 年固定成本（美元）年生產能力（件） 175 000 10 000 300 000 20000 375 000 30 000 500 000 40 000 表2 分銷中心波士頓亞特蘭大休斯敦年需求量（件） 30 000 20000 20 000 表8-2 馬丁貝克分佈系統的單位運輸成本分銷中心工廠地點底特律托萊多丹佛堪薩斯城聖路易斯波士頓 5 4 9 亞特蘭大 2 3 7 4 8 4 休斯敦 3 4 5 2 3
第8章整數線性規劃 229 如果在底特律建廠，3=1，否則，Y：=0； 如果在托萊多建廠，½2=1，否則，½2=0； 如果在丹佛建廠，Y=1，否則，3=0； 如果在堪薩斯城建廠，=1，否則，Y=0。 對各工廠到每個各中心的運輸量變數的定義和運輸問題中的相同。 x—工廠i到分銷中心j的運輸量其中，i=1，2，3,4, 5且j=1，2，3。 利用表8-2 中的運輸資料，年運輸成本（單位：1000美元）為： 5x11 +2x12 + 3x13 +4xz1 + 3%22 +4x23 +9x31 +7X32 + 5x33 + 10xa1 +4442 +2%43 +8xsi +4xsz +3xs3 經營新工廠的年固定成本（單位：1000美元）為： 10 底持鋒 5 2 分銷中心波生⑨ 30 20 託萊多 30 20 10 175y+300y+375y+500y。 注意，根據0-1變數的定義，只有當建立某個工廠（如y：=1）時，才計算經營該新工廠的固定成本；而如果沒有建立該工廠（即y：= 0），則相應的年固定成本為0。 馬丁貝克公司的目標函式為：年運輸成本與經營新建立的工廠的年固定成本之和最小化。 現在我們考慮一下4 個擬議工廠的生產能力約束條件。以底特律為例，可以得出如下約束條件： 40 20 30 蛋路易期生產能力分銷路線需求圖8-7 馬丁貝克分佈系統網路圖 Xi + +as≤l0y 如果底特律的工廠建立了，即鄉；=1，那麼從底特律運到3個分銷中心的總量必須小於或等於底特律的生產能力，即10000件。如果底特律的工廠沒有建立，即3：=0，則意味著底特律的生產能力為0。這樣，相應得出自底特律的運輸量均等於0。把所有的變數都置於約束條件的左邊，得到如下所示的底特律生產能力約束條件： Xi1 +Xi2 +xis-10y，≤0 底特律的生產能力以類似的方式，可以求出托萊多工廠的生產能力約束條件如下： Xa1 +X22 +42s -20y， ≤0 託菜多的生產能力丹佛和堪薩斯城的也是完全類似的。考慮到聖路易斯已經存在工廠，我們把其定義為0-1變數。 其生產能力約束條件可寫為： *si +Xs2 +2ss ≤30 聖路易斯工廠的生產能力還需要為3個分銷中心的需求量各自設定一個約束條件。波士頓分銷中心的需求量（單位：1000 件）的約束條件可寫為： Xi1 +X21 +231 +441 + 1s1 =30 波士頓的需求亞特蘭大和休斯敦分銷中心的是相同的。 於是，我們得到了馬丁貝克公司的分佈系統設計問題的完整模型： min Sxi +2xi2 +3%1 +4821 + 3822 +483 + 9xs1 + 7x32 + 5x3s + 10xa， +4xa2 +2x8+8xs1 +48sz +3xss + 175y，+300y +375ys+500ya 3.t.
230 資料、模型與決策：管理科學篇 - 10%1 Xz1+ Xn+X23 Xisa t ia + Xs XA1十XA2+X43 X'si + Xsz + Xss - 20%z - 30ys <0 底特律的生產能力 ≤0 託菜多的牛產能力 ≤0 丹佛的生產能力 -40yA ≤0 堪薩斯城的生產能力 ≤ 30 聖路易斯的生產能力 = 30 波士頓的需求 Xiz+Xn tXsa t Xaz t Xsz =20 亞特蘭大的需求 Xig + Xzs tXss t Xas +Xss =20 休斯敦的需求對所有的i，j，有xy≥0；Y1，32，3，%=0，1。 利用管理科學家軟體的整數線性規劃模型，我們得出如圖8-8所示的結果。最優解說明要在堪薩斯城建立一個工廠（y=1）；從堪薩斯城到亞特蘭大運輸20 000件產品（x42 =20）；從堪薩斯城到休斯敦運輸20 000件產品（x43 =20）；從聖路易斯到波士頓運輸30 000件產品（xs1 =30）。注意，包括堪薩斯城工廠的固定成本500000美元在內，該解所得到的總成本為860000美元。 上述基本模型可以進行擴充套件，從而可以適用於含有工廠與倉庫、工廠與零售店面之同的直接運輸和多種產品的分佈系統。利用0-1變數的特性質，該模型還可以進行擴充套件，從而可以為廠址配置問題增加多個約束條件。例如，假設在其他問題中， 選址1為達拉斯，而選址2位沃斯堡，因為這兩個城市相距太近，公司也許不希望同時在這兩地建廠。 為避免此情況發生，模型中可加入下面的約束條件： 91+3≤1 在上述限制條件下，%，與Y2中最多隻有一個可能等於1。而如果把約束條件寫成等式，就使得必須在達拉斯與沃斯堡中選擇一個。 最優解目標函式值 = 變數 X11 ×12 X13 X21 ×22 X23 X31 X32 X33 X41 X42 X43 ×51 X52 ×53 Y1 Y2 Y3 Y4 約束 1 860.000 值 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 20.000 20.000 30.000 0.000 0.000 0.000 0.000 0.000 1.000 鬆弛/剩餘 0.000 0.000 8.3.4 銀行選址 0.000 俄亥俄州信託公司的長期計劃部正考慮在俄亥俄州東北部20個郡的地區開展業務（見圖8-9）。 4567 0.000 0.000 0.000 俄亥俄州信託公司目前在這20個郡沒有一個主營 0.000 業處。根據該州相關法律，如果一個銀行在任一郡 8 0.000 建立一個主營業處，即可在該郡及所有毗鄰郡建立圖8-8 馬丁貝克公司分佈系統問題分行。但是，為了建立一個主營業處，俄亥俄州信的管理科學來解決方案託公司必須獲得本州銀行管理者的批准，或者購買一家當地現存的銀行。 表8-3列出了這一地區的20 個郡及其鄰郡。例如，阿什特比拉與菜克、吉奧特、特蘭博爾毗鄰； 菜克郡與阿什特比拉、凱加、吉奧特毗鄰；等等。 計劃的第一步，俄亥俄州信託公司需要確定將來在這20個郡全部都營業總共需要建立的主營業處的最小數目。可用一個整數規劃模型來求解俄亥俄州信託公司的選址問題。我們定義變數如下： 如在；郡建立主營業處，則x，=1；否則，x；=0。
第8章鏊數線性規劃 231 安大略 16 14 賓夕法尼亞 10 12 13 俄亥俄 20 19 西弗吉尼亞郡 1. 阿什特比拉 2. 菜克 3.凱雀加 4.洛雷恩 5.休倫 6.裡奇蘭 7.阿什蘭 8.韋恩 9.梅迪納 10.薩米特 11.斯塔克 12.吉奧格 13.波帝奇 14.哥倫比亞納 15.馬霍寧 16.特蘭伯爾 17諾克斯 18.雀姆斯 19.塔斯長盧斯 20.卡羅爾圖8-9 俄亥俄州東北部的20 個郡考慮的郡 1. 阿什特比拉 2. 萊克 3.凱襤加 4.洛雷恩 S.休倫 6.裡奇蘭 7.阿什蘭 8.韋恩 9，梅迪納 10. 薩米特表8-3 俄亥俄州信託公司的擴充套件區臨近的都（困8-9中的數字代號） 考慮的郡 2,12,16 11. 斯塔克 1,3,12 12. 吉奧特 2,4,9.10,12,13 13. 波帝奇 3,5,7,9 14.哥倫比亞納 4,6,1 15. 馬霍寧 5,7,17 16. 特蘭伯爾 4, 5, 6,8,9,17,18 17.諾克斯 7,9,10,11,18 18. 霍姆斯 3,4,7,8,10 19. 塔斯卡盧斯 3，8，？，11,12,13 20. 卡羅爾臨近的郡（8-9中的數字代號） 8,10,13,14,15,18,19,20 1,2,3,10,13,16 3，10,11,12,15,16 11,15,20 11,13,14,16 1,12,13,15 6,7,18 7,8. 11,17.19 11,18,20 11,14,19 為了得到所需主營業處的最小數目，我們將目標函式寫為： min x；+X2+：•+420 如果某郡擁有一個主營業處或其毗鄰郡擁有主營業處，那麼該銀行就可以在該郡建立分行。於是，每個郡都要滿足一個條件。例如，阿什特比拉郡所需要滿足的條件是： X，+*+X2+216≥1 阿什特比拉注意，滿足這一條件就可以保證阿什特比拉郡及其（一個或多個）鄰郡至少設有一個主營業處。於是這一條件使俄亥俄州信託公司能夠在阿什特比拉郡設立分行。 該銀行選址問題的完整表述如下：
232 資料、模型與決策：管理科學篇 min x+xt S.t. X+ +xn +X16 +X20 ≥1 阿什特比拉郡 >1 菜克郡鍛優解日標函式值= 3.000 變數值 ---- ASHT 0.000 Ki + Xia + Xis +X20>1 卡羅爾郡 X： =0,1 i=1,2.，20 利用管理科學家軟體來求解這個含有20個變數、20 個約束條件的函式。圖8-10是計算機輸出結果的一部分， 其中變數名稱對應各郡開頭4個字母。透過這一結果， 我們得知最優解為：需要在阿什蘭、斯塔克、吉奧特設立主營業處。有了這3個主營業處後，俄亥俄州信託公司就可以在這全部20個郡設立分行（見圖8-11）。其他所有決策變數的最優值都為0，即不需要在這些郡設立主營業處。很明顯，該整數規劃模型可進行擴充套件，用於在更大一塊地區或整個州開展業務。 LAKE 0.000 CUYA 0.000 LORA 0.000 HURO 0.000 RICH 0.000 ASHL 1.000 WAYN 0.000 MEDI 0.000 SUMM 0.000 STAR 1.000 GEAU 1.000 PORT 0.000 COLU 0.000 MAHO 0.000 TRUM 8.3.5 產品設計和市場份額的最最佳化 0.000 KNOX 0.000 HOLM 0.000 聯合分析是一種市場研究方法，透過該種方法可以 TUsC 0.000 瞭解預期的購買者如何評價產品的屬性。本節將說明如 CARR 0.000 何把聯合分析的結果應用到產品設計和市場份額最最佳化問題的整數規劃模型中去。我們透過一家主要的冷凍食圍8-10 用管理科學寂軟體解決俄亥俄州信託公司的問題品製造商——塞倫食品公司—所面臨的問題來介紹其方法。 塞倫食品公司計劃進入冷凍比薩餅市場。而目前已有兩個品牌：安東澳和國王，它們佔領了主要的市場份額。塞倫準備開發一種香腸比薩餅，並想以之奪取大量市場份額。塞倫已確定顧客在購買冷凍香腸比薩餅時最關心的4個屬性為：麵包皮、乳酪、調味醬和香腸的風味。麵包皮屬性有2種（薄和厚）；乳酪屬性有2種（義大利乳酪和混合乳酪）；調味醬屬性也有2種（細滑的以及帶塊的）；香腸風味有3種（清淡口味的，大眾口味的，辣味的）。 塞倫準備了各種屬性組合的比薩餅，請接受調查的消費者就這些比薩餅給出他們的偏好程度，以進行聯合分析。然後使用迴歸分析法來確定各種屬性品質的區域性價值。也就是說，區域性價值是消費者對某個屬性品質給出的效用。如何利用迴歸方法來計算區域性價值不在本書討論的範圍之內，但我們會說明如何使用區域性價值來計算消費者對某種比薩餅給出的整體效用值。 表8-4顯示了8位目前在購買安東尼奧和國王的比薩餅，但有可能轉向塞倫的潛在顧客給出的每一種風性的區域性價值。對於顧客1，薄麵包皮的區域性價值為11，而厚麵包皮為2，這就意味著他偏好薄麵包皮。在乳酪屬性上，義大利乳酪的區域性價值為6，而混合型乳酪為7，就是說顧客1對混合型奶酪有輕微的偏好。透過其他的區域性價值分析，我們可知顧客1對於細滑調味醬比對小塊的調味醬有強烈的偏好（17比3），而對大眾口味的香腸有輕微的偏好。顧客2對薄麵包皮、混合乳酪、帶塊調味醬和清淡口味的香腸有偏好。其他顧客的區域性價值屬性也是如此解釋。 區域性價值還可以用來確定每位顧客對某一種比薩餅的整體評價。例如，顧客！目前最喜愛的比薩餅是安東尼奧牌的厚麵包皮、義大利乳酪、帶塊調味醬、大眾口味香腸的比薩餅。我們可以利用表8-4中的區域性價值來確定某一種比薩餅對顧客1的效用。對顧客1，厚麵包皮的區域性價值為6，帶塊兒調味醬的第8章整數線性規劃 233 安大略 3 賓夕法尼亞 10 15 俄亥俄 418 20 19 西弗吉尼亞郡 1. 阿什特比拉 2. 萊克 3.凱雀加 4.洛雷恩 5.休倫 6.裡奇蘭 7.附什蘭 8. 韋恩 9.梅迪納 10.薩米特 11.斯塔克 12.吉奧格 13.波帝奇 14.哥倫比亞納 15.馬霍寧 16.特蘭伯爾 17.諾克斯 18.霍姆斯 19.塔斯卡盧斯 20.卡羅爾 *應該在這些郡設立主營業處。 圖 8-11 俄亥俄州信託公司主營業處的位置區域性價值為17，大眾口味香腸的區域性價值為27。因此安東尼奧牌比薩餅對顧客1的效用為2+6+17 +27 =52。我們可以用類似的方法計算國王牌比薩餅對顧客1的效用。國王牌比薩餅是薄麵包皮、混合乳酪、細滑調味醬、清淡口味的香腸。由於對顧客1，薄麵包皮的區域性價值為11，混合乳酪的區域性價值為7，細滑調味醬的區域性價值為3，清淡口味香腸的區域性價值為26，所以國王牌比薩餅對顧客1的效用為11 +7+3+26=47。一般地，每位顧客對某種比薩餅的評價就是對各區域性價值偏好的簡單相加。 表8-4 塞倫食品公司問題的區域性價值麵包皮乳酪調味蕾廠大利乳酪混合乳酪帶塊的 1 2 3 4 5 6 7 8 薄 11 11 7 13 2 12 5 2 7 5 20 8 17 19 9 6 7 15 17 14 細滑的 3 16 16 17 26 7 20 6 11 12 4 17 14 11 9 16 14 30 2 16 23 20 30 25 16 喬腸口味濟淡口味大眾口味 26 27 14 1 29 16 25 29 15. s 22 12 30 23 16 30 辣味 8 10 6l 10 12 20 19 3 為了使其品牌獲得成功，塞倫食品公司意識到必須誘使市場上的消費者從他們中意的比薩餅品牌轉變到塞倫的產品上來。也就是說，塞倫必須設計出一種比薩餅（透過選擇麵包皮、乳酪、調昧醬和
234 資料、模型與決策：管理科學篇香腸口味），這種比薩餅能為足夠多的人提供比其目前中意的皮薩餅更高的效用，這樣才能保證足夠的銷售量，從而來支援該種產品的生產。假設目前所研究的抽樣調查的8位顧客可以代表整個冷凍香腸比薩餅市場，那麼，我們就可以列出並解決一個整數規劃模型來幫助塞倫得出設計方案。在市場營銷領域，這個問題被稱做份額選擇問題。 定義決策變數如下： 如果賽倫在屬性j上選擇品質i，則=1，否則為0； 如果顧客h選擇塞倫品牌，則y=1，否則為0。 目標是選擇每種屬性的品質，以使偏好塞倫牌比薩餅的顧客人數達到最大。由於偏好塞倫比薩餅的顧客人數就是變數y：的總和，所以目標函式就是： max Y： +½+：+% 每一位抽樣顧客都有一個約束條件。為了說明列出的約束條件，我們以顧客1為例。對於顧客1， 某種比薩餅的效用可以表示為區域性價值的和： 顧客1的效用=114，+2b1+6l;a+7bs+3bs+17½+26l +27b +8b 為了使顧客1選擇塞倫比薩餅，塞倫比薩餅的效用必須高於該顧客目前中意的比薩餅。由於顧客 1目前中意的比薩餅品牌是安東尼奧，效用為52，所以若要顧客1選擇塞倫，塞倫必須在以下條件下選擇各屬性的品質： 11k6.1+2ba +6ba + 7baz + 3b+ 17bs + 26lya +27ba + 8b3 >52 由於決策變數y：的定義是：當顧客選擇塞倫品牌時，設y：=1；而當顧客不選擇塞倫品牌時，設y：= 0。所以我們這樣來描述顧客1的選擇條件： 11b，+2b1 +6b2 + 7baz + 3bs + 17bas + 26bs +27b + 8b4≥1 + 52% 這樣，只有當塞倫比薩餅的效用（約束條件的左邊）至少比顧客1目前中意的比薩餅的效用大1時， Y，才可能等於1。由於目標函式是要求變數3，的和的最大，所以最優解就是要找到一種產品設計，能使盡量多的y.等於1。 把決策變數都放到約束條件的左邊，條件1可以重寫為： 11k+2ba +6lia +7baa + 3bs + 17bs + 26b+27b +8b - 52%，≥1 每一位抽樣顧客的條件都是如此。效用函式中變數1的係數來自表8-4，變數y。的係數是透過計算顧客目前中意的比薩餅品牌的總體效用得到的。下面的條件分別對應抽樣調查中的8位顧客。 11 + 2a + ia t Tl + 3hs + 172a + 264 + 27124 + 8- 52y> 1 114 + 7bai + 15kp2 + 17bz + 16his + 26bz + I44 + 1z + 10bsa- S8y2 > 1 Til+ Si t &l + l4z + l6is + Tlzs + 2 + 16z + 19- ys ≥ l L3h + 20621 + 20kp2 + 17lzz + 174s + 14lzg + 25l + 29/2 + 10/z- 83.≥1 2011 + 8a + iz + 11bx2 + 303 + 20kz + l5is + Slz + 12b- 8ys ≥ 1 12b1 + 17l1 + ll+ lzz + 243 + 30kz + 22h4 + 1262 + 20g4- 70%y > 1 9h1 + 19621 + 124i2 + 16zz + 16k1s + 251zs + 3k + 236 + 19- 9 ≥1 Sh + 9hr + 4lnz2 + 14zz + 23hs + 16kzs + l6ks + 30bz + 3b- S9 >1 另外還需要4個條件，每一種屬性需要一個。需要這些條件來保證每一種屬性都選擇一種並且只選擇一種品質。對於屬性1（麵包皮），我們加上條件： b +hs=1 由於和12都是0-1變數，所以這一條件就使得這兩個變數中一個等於1，另一個等於0。下面的3 個條件保證另外3種屬性也必須選擇並且只能選擇一種品質。 b12 +bz =1 4is +½s =1 bia +ba tbu=1
第8章整數線性規劃 235 這個含有117個變數、12個條件的整數線性規劃的最優解（利用LINDO 求得）為：1.=l2 = b8 = 1i4 =1且y，=½：=Y。=多，=1。最優解的值為4，就是說如果塞倫製作這種比薩餅，將會得到這8位顧客中的4位的青睞。由於L.1=b2 =l28 =L=1，所以塞倫可以佔得最大市場份額的比薩餅設計是：薄面包皮、混合乳酪、清淡口味的香腸比薩餅。而根據y：=2=%=3，=1，顧客1、2、6、7將偏好塞倫比薩餅。根據這些資訊，塞倫公司可以營銷此種比薩餅。 註釋與評論 1.大多數實務應用軟體都只含有0-1變數。實際上，一些混合整數的計算機規則只能處理二進位制的整數變數。但是，只需要稍用數學技巧，就能使這些規劃適用於含有一般整數變數的問題。這種技巧叫做二進制擴充，並且需要為每個整數變數設立一個上限。這些將會在更深入的整數線性規劃的書中講到。 2. 專欄8-3講述瞭如何在模型中運用0-1變數來充分利用業務量折扣。貝爾克的客戶由於運用了混合整數模型而節省了幾百萬美元。 3. 一般用途的混合整數線性規劃和一些電子表格軟體可以用於線性規劃問題、全整數問題和既含有連續變數又含有整數變數的問題。一般用途的規則在解決含有特殊結構的問題（如運輸、指派以及轉運）上通常不是速度最快的。但是，除非問題非常龐大，求解速度通常不是關鍵問題。因此，相對於使用許多針對於特殊問題的計算機規劃而言，多數從業者更傾向於使用一個能適用於大量不同問題的一般用途的計算機軟體。 專欄83 實踐中的管理科學貝爾克公司的價格報價分析貝爾克公司建於1984年，為地區性貝爾運營電話公司提供多種服務。為了減少購買產品和服務的成本，貝爾克客戶公司更多地向廠商提出業務量折扣的要求，而不是傳統的數量折扣。在傳統的數量折扣中，每種產品的價格根據購買件數來打折。業務量折扣和簡單的產品數量折扣的不同在於：廠商根據所有產品的利潤總額來決定對每種產品降價多少以及降價百分比為多少。總的來說，利用業務量折扣，公司可以實現整體購買成本的降低，而供應商也可以透過獲得該公司的大量業務而增加總收入。但是，業務量折扣也極大增加了採購過程的複雜性，因為最後的折扣取決於所有購買的產品的數量和價格。 為了幫助其客戶公司應用業務量折扣，貝爾克開發了採購決策支援系統（PDSS），這是一個基於計算機的、利用混合整數規劃模型來最小化購買成本的決策支援規劃系統。該模型利用0-1整數變數來表示可應用於該問題的折扣種類，幷包含多個有關於諸如生產能力和供應商可獲取利潤極限等因素的約束條件。從1990年開始，已經有一個貝爾克公司的客戶公司宣告有兩項節省款項：一筆是450萬美元，另一筆是1500萬美元。這些款項幾乎達到了採購成本的10%。而還有一家客戶公司降低了接近80%的價格報價分析成本。客戶們大都承認 PDSS 的確是在與供應商談判中鑑別機遇的一個有利工具。 資料來源：基於：P.Katz,A. Sadrian,and P. Tendick， "Telephone Companies Analyze Pirce Quotatione with Bellcore'a PDsS Software"， Interfaces （January/February 1994）：50 -63. 8.4 0-1 整數變數在建模過程中的靈活性分析第8.3節中，我們已經初步介紹了0-1整數變數的4種應用。本節將結合應用繼續討論0-1 整數變數在構建模型中的靈活性。首先，0-1整數變數可以使得構建的模型中變數可以有多重選擇特性，並且0-1代表的變數具有互斥特性。這些特性都使得我們可以構建從n個方案中挑選h個方案的 ◎我們在本章的開始部分說過，一些相當小的線性規劃問題是很難解決的。本部分中的一些混合線性規劃問題太難了，無法用管理科學家軟體解決。我們使用LINDO解決了塞倫食品公司的問題。用Excel 求解這個問題的過程，參見本書附帶的CD。
236 資料、模型與決策：管理科學篇模型，也可以把A方案作為B方案的約束條件，從而構建模型。本節的最後，我們將嘗試討論整數線性規劃中的靈敏度分析及其在整數線性規劃中所起的作用。 8.4.1 多重選擇和互斥約束請回顧一下前一節中講到的愛斯柯德冰箱公司的資金預算問題。其決策變數的定義如下： P=1，表示執行公司擴建方案；否則取O； W=1，表示執行倉庫擴充套件方案；否則取O； M =1，表示執行新機器方案；否則取0； R=1，表示執行新產品研製方案；否則取0。 假設愛斯柯德公司不是執行擴建1個倉庫的方案，而是需要考慮擴建3個倉庫的方案，其中有1 個倉庫必須被擴建以迎合增長的產品需求，但是新增需求還沒有達到必須擴建一個以上的倉庫。下面定義的變數和多置選擇約束，實際上可以考慮用0-1 整數線性規劃模型，從而反映愛斯柯德公司目前所面臨的局面。設： 如果擴建現有倉庫的方案透過，W，=1，否則，W， =0； 如果擴建第2個倉庫的方案透過，W=1，否則，W，=0； 如果擴建第3個倉庫的方案透過，W，=1，否則，W，=0。 由於要求這些方案中只能執行其中一個方案，則反映這一要求的多重選擇約束如下： W，+W，+W，=1 如果W、、W，和W，為0-1變數，則意味著只能從這些方案中選擇其一。 如果不要求必須擴建1個倉庫，則多重選擇約束條件可以寫成： W，+W+W≤1 該多重選擇約束條件允許不擴建任何倉庫的（W，+W+W，=0）情況出現，但不允許出現擴建1個以上的倉庫的情況。這種多重選擇約束條件稱為互斥約束。 8.4.2 n 選k約束將多重選擇約束概念延伸就可以很容易得出n個方案中挑選k個方案的模型，也即n選k約束。 設W」、W2、W、W、和W，代表S個潛在的倉庫擴建方案，並且在這5個方案中至少必須執行2個。 那麼這個約束條件可以寫成： W，+W，+W，+W。+W，=2 如果5個方案中執行的方案不能超過2個，則約束條件又可寫成： W，+W，+W+W。+W，≤2 當然，這裡使用的變數都是0-1變數。 8.4.3 條件約束和並行約束很多時候，必須執行一個方案才能觸發另一個方案執行。例如，愛斯柯德公司的工廠擴建方案是倉庫擴建方案的必備條件，顯然，只有工廠擴建了，倉庫才能擴建。工廠不擴建，則管理層將無從考慮倉庫的擴建。現在，我們用P代表工廠擴建方案，而用代表倉庫擴建方案，則需要引人條件的束來反映該要求： W≤P W和P必須為0-1變數。而且，P為0，則W就只能取0；而P取1，則取也有可能取1。這樣，工廠和倉庫才能都被擴建。然而，必須指出，執行工廠擴建方案，並不要求一定執行倉庫擴建方案。這和現實中的情況是一致的。
第8章整數線性規劃 237 而如果我們要求不管工廠擴建方案執行與否，都必須執行倉庫擴建的方案，反之亦然，我們就說 P和W是並行約束。對於這種情形，可以用一個簡單的等式來表達： W=P 同樣，P和W 也僅限於0-1變數。 專欄8-4 實踐中的管理科學 Ketron 的客戶訂單分配模型 Ketron 的管理科學研究部門為數學規劃模型的設計及其具體實施提供諮詢服務。其中一個重要的應用案例是：Ketron 為一家大型體育用品公司的客戶訂單分配應用構建了一個混合整數規劃模型。該體育用品公司經營近300種體育產品，而且生產產品的原材料來源於約30個不同的地方（包括工廠和庫房）。建立該模型的目的是要考慮如何分配客戶訂單和生產原材料的來源地之間的對應關係，從而使得所訂購的產品的總製造成本達到最小化。這個問題可以透過圖8-12來表示。請注意：圖中關係表示每個客戶只能得到有限幾個供應方的供應。例如，客戶1從A和B處得到供應；而客戶2只能從 A 處得到供應，參見圖8-12，以此類推。 該體育用品公司把客戶的訂單分為兩類：一類被稱做“保證”訂單，另一類被稱做“二級”訂單。第一類訂單是單源訂單，只由一個供應方來供應，並且要保證能夠將訂貨一次性交付給客戶。這種單源供應的要求，使得在建模中需要使用0-1變數。近80%的客戶訂單屬於第一類訂單。第二類訂單可以加以分割，由多個供應商供應，這些訂單是客戶為了再補充庫存而發出的，因此可以在不同的時間、從不同的供應商接受零星運輸量。第一類訂單的問題可以使用0-1變數來表示，而第二類訂單則使用連續變數來表示。 該體育用品公司問題的約束條件主要有：原材料存貨量、生產製造能力以及各個產品的存貨量。 一個代表性的典型應用（問題）可以包含800 多個約東條件，2000多個表達不同含義的0-1變數 （針對第一類訂單而言），500多個連續參變數（針對第二類訂單應用而言）。隨著客戶訂單的到達， 可以分階段對客戶訂單進行分配。通常在一個週期內，大約有20~40個客戶要求訂貨。又因為大多數客戶要求訂購若干種不同產品，因此通常將600~800個訂單分派到不同的供應方。 資料來源：基於 Keron Management Science 的 J. A. Tomlin 提供的資訊。 供給的來源客戶： 圖 8-12 客戶訂單分配問題的網路圖注：帶縮頭的線段代表每個顧客可能的密源供給。
238 資料、模型與決策：管理科學篇 8.4.4 關於靈敏度分析的討論線上性規劃問題中，特別是整數線性規劃問題，靈敏度分析起到至關重要的作用。在一些應用中經常可以看到，當約束條件中某個引數發生很小的變化，就可能使得最優解的值產生很大的波動。下面我們考慮一個針對簡單資本預算問題而構建的線性規劃模型它包括4個方案和一段時期內的預算約束條件。 max S. t. 40x，+60x2+70x+160x 16x，+35x+45x，+85x， ≤100 我們可以簡單地使用列舉法求出最優解：即x=1， 對偶價格只適用於線性規劃問題，而 *2=1，X=1，x=0，且目標函式的值為170美元。但是，不可以在整數規劃中分析靈敏度。如果想如果預算變數增加1美元（比如從100美元增加到101美要解決整數規劃的靈敏度問題，則需要用元），則最優解的值就會變成：x，=1，*=0，x=0，x4= 到高速計算機。 1，目標函式也會相應變成200美元。也即，預算中增加1 美元就會導致收人增加30美元。管理層當然很樂意遇到這種情況，也樂意去增加1美元的預算。從這個資金預算問題中，我們可以看到：由於最優解的值對預算資金這個條件引數有著極大的靈敏反應， 人們通常建議在選擇最後實施的最優解之前，先對各個條件引數稍加改變，多求解幾次最優解的值。 本章小結本章介紹了線性規劃的一個很重要的擴充套件，即整數線性規劃。本章所研究的整數線性規劃和前幾章研究的線性規劃問題的惟一區別在於，其中的一個或者幾個變數侷限於取整數值。極端情況下，如果所有變數全部取整數，我們就得到全整數線性規劃。而如果變數不全部取整數，則得到混合整數線性規劃。當然，多數整數規劃軟體中都含有0-1或二進位制規劃的求解方案。 研究整數線性規劃的兩個最重要的原因是：第一，當變數、引數不允許出現小數值時，使用整數線性規劃求解問題就顯得非常重要。而且，大多數情況下，僅僅靠對一般線性規劃解的四舍五人並不能得到最優解的值。當取近似值能夠產生較大的經濟影響時，我們就需要尋找更有效的求解方法。第二，使用0-1 變數構建線性整數規劃模型的靈活性是十分明顯的。本章我們透過對資金預算、固定成本問題、分佈系統的設計、銀行選址以及產品設計\市場份額等問題的求解應用，演示了線性規劃中使用0-1 變數建模的靈活性以及在使用 0-1變數建模過程中需要考慮的一些問題。 現代社會，應用整數線性規劃的情況越來越多，很大一部分原因是因為出現了一些優秀的整數線性規劃軟件包。隨著對大型整數線性規劃問題的不斷深入研究，再加上計算機速度的不斷提升，我們有理由相信，未來使用整數規劃解決問題的數量會與日俱增。 專業術語 integer linear program 整數線性規劃至少有一個變數為整數型的線性規劃。 all-integer linear program 全整數線性規期所有變數均為整數型的線性規劃。 IP Relaxation LP 鬆弛整數線性規劃中去掉變數的整數型要求後得到的線性規劃。 mixed-integer linear program 混合整數線性規劃僅有部分變數為整數型的線性規劃。 0-1 integer linear program 0-1整數線性規劃全整數或者混合整數線性規劃中的整數取0-1 值時，這樣的線性規劃就叫0-1整數線性規劃，又叫二進位制整數規劃。 capital budgeting problem 資金預算阿題在一個0-1整數規劃中尋求最優投資回報率方案的問題。 fixed cost problem 固定成本問題屬於0-1混合整數規劃的一種，在該規劃問題中，0或1代表一個行為的發生與否。比如生產某種產品，用1表示生產，用0表示不生產。 distribution system design problem 分佈系統設計問題屬於混合整數線性規劃，在這個規劃中，一般用二進第8章整數線性規劃 239 制整數變數表示選擇倉庫或工廠的地點，而用連續變數表示分佈網路上各條弧上的運輸量。 location problem 選址問題以選擇能滿足既定目標的最優地點為目的的0-1 整數規劃問題。此問題的變化即是覆蓋問題（參見第8.3節中的銀行選址問題）。 product design and market share optimization problem 產品設計和市場份額最最佳化問題這個問題常被稱做份額選擇問題，設計一種產品（方案）以滿足最多客戶的需求。 multi-choice constraint 多重選擇納束要求兩個或多個0-1 變數的和等於1的約束條件。因此，一個可行解就是選擇一個變數為1。 mutually exclusive constraint 互斥約束要求兩個或多個0-1變數的和小於或等於1的約束條件。這樣，如果一個變數等於1，則其他變數就必須等於0。但是，也可以選擇所有的變數為0。 k out of n alternatives constraint n選K約束多重選擇約束條件的擴充，要求n個0-1變數的和等於K。 conditional constraint 條件約束只有當某些變數為1時才允許另一些變數等於1的0-1變數約束條件。 corequisite constraint 並行約東即要求2個0-1變數相等的約束條件。因此，這2個變數同時在方案中或者同時不在方案中。 問 2. 就下面的全整數線性規劃作答： max St， +8xg s.t. 6x， +5x，≤30 9x，+4x≤36 1%+28≤10，4≥0且為警數 a.畫出本題的約束條件，並用點號表示可行的整數解。 b.求出LP鬆弛的最優解。進一步近似，以求其可行的整數解。 c•直接求解最優整數解。比較（c）和（b），看它們所求得的結果是否一致。 4. 就下面的全整數線性規劃作答： max 10x， +3x 8.t 6x，+7x≤40 3%，+1x≤11 *，X≥0且為整數 a.列出本題的LP鬆弛的式子，並求解。使用圖解法求解，並作近似，以求出它的一個可行解。指出最優解的上限值。 b.使用圖解法求出本整數線性規劃的解。比較圖解法求出的解和（a）中求出的結果。 c•假設目標函式變為max 3x，+6x。重新求解（a）和（b）。 6. 就下面的混合整數線性規劃作答： max 1%，+1x 8.t. 74，+9x，≤63 9%， +58≤45 3x：+1x≤12， ≥0且為整數日.畫出本題的約束條件，並在圖上標出所有可行的混合整數結果。 b.求LP鬆弛的最優解。取x的近似值，從而得到一個可行的混合整數解。求解本規劃問題最優解的上下限。 c. 求解問題的最優結果。• 8.斯賓塞公司需要從下列一系列投資方案中進行選擇。下面列出了所有可能的方案，以及對應的未來回報的淨現值、需求資金以及3年中的可用資金：
240 資料、模型與決策：管理科學篇淨魂值可能選擇 （美元） 小規模倉庫擴建 4 000 大規模倉庫擴建 6 000 測試新產品市場 10500 廣告活動 4 000 1年 3 000 2 500 6 000 2 000 糯求資金（葵元） 2年 1 000 3 500 4 000 1 500 可能選擇 3年 • 4 000 3 500 基礎研究買人新裝置可用資金淨現值 （美元） 8 000 3000 5 000 1年 $ 000 1 000 10 500 需求資金（美元） 2年 1000 500 7000 3年 4000 900 8 750 1 800 a.構建該問題的整數線性規劃模型，以求得最大的淨現值。 b.假設只能有-個倉庫擴建方案可行，重新構建整數線性規劃模型。 c•假議，如果將新產品投放市場，則需要進行廣告表3 活動。此時，請重新構建一個整數線性規劃模型。 10. 格雷大市打算遷移其某些警察分局，來透過改變警察分局的佈局實現加強管制高犯罪率地區的效果。 表3是所考慮的地點以及這些地點所能管制到的區域。 日.構建一個整數線性規劃模型，以最少數目的地點可能的分佈地址 A B c D E F c 覆藎區堿 1,5,7 1,2,5,7 1,3,5 2,4,5 3,4,6 4,5,6 1, 5,6,7 覆蓋所有區域，即最優選址問題。 b.求解上面的線性規劃模型。 12. 葉慈公司為各郡高速公路部門供鹽。葉慈共有3輛卡車，其中兩輛載重15 噸，另外一輛載重30噸。公司的決策人員安排明天向波克、達拉斯和賈斯波3郡供鹽。根據卡車的載重量，則兩個郡將各收到15噸鹽， 而另一個郡收到30噸鹽。決策者需要決定需要分別向3個郡各送多少噸鹽。令： x，—運往波克郡的噸數； X，——運往達拉斯的噸數； *，—運往賈斯伯的噸數； 8.利用這些變數的定義，列出運到各郡的鹽的數量約束條件。 b.30噸的卡車到達3郡的派遭成本不等，分別是：波克100美元，達拉斯85 美元，賈斯波50美元。構建一個混合整數線性規劃模型，並求解需向各郡運輸多少噸鹽。 14.一家汽車製造商擁有5家陳舊的工廠，分佈如下： 表4 密歇根、俄亥餓、加利福尼亞3州各有一家，紐約有2家。現在管理層打算更新這些工廠以生產一種工廠所在的州更新成本發動機組變速髑 （100萬費元）（1000個）（1000個） 新型轎車的發動機組合變速器。更新每家工廠的成巒歇根 25 500 300 本和更新後的生產能力如表4。 紐約 800 400 假設需要達到900000個發動機組和 900 000 紐納 35 400 800 個變速器的總生產能力。問：管理層需要更新哪些俄亥俄 40 900 600 工廠以達到預定的總生產能力，並且同時使更新的加利福尼亞 20 200 300 總成本最小。 日.列出所有可供管理層選揮的組合，並指出每種組合中發動機組個數和變速器個數，並且判斷每種組合是否能達到預定的生產需要。求出按每種組合更新後的成本。 b.觀察（日）中的結果，對該公司管理層提一些建設性建議。 c.構建一個0-1整數規劃模型，求解本問題的最優解。 d.求解（c）中構建的模型。 16.北海岸銀行打算為其全職出納和兼職出納制定一個有效的工作時間表。時間表須能讓銀行有效運作，考慮到提供足夠多的客戶服務、員工休息等諸多因素。該銀行週五營業時間為上午9:00到下午7：00。下面列出週五各個時間段內為提供足夠的客戶服務所需要的出納員的數量。
第8章整數線性規劃 241 工作時間上午9:00~上午10:00 出納員數量 6 工作時間下午2:00~下午3:00 上午10:00~上午11:00 下午3:00~下午4:00 出納員數量 6 4 上午11:00~正午下午4:00~下午5:00 正午~下午1:00 下午1:00~下午2:00 10 9 下午5:00~下午6:00 6 下午6:00~下午7:00 6 每個全職員工需要從整點開始工作，連續工作4個小時後，是一個1小時的午餐時間，然後繼續工作 3個小時。兼職員工需要從整點開始工作，連續工作4 個小時。全職員工和兼職員工的工資和額外福利不一樣，因此銀行使用全職員工和兼職員工的成本也不一樣，分別為每小時15美元（每天105美元）和每小時8美元（每天32美元）。 日.構建一個整數線性規劃模型，以使用最少人力成本並且以滿足顧客服務為目標，構建一個可行的時間表。（提示：令x，表示第；點鐘全職員工開始工作的人數；3，表示第j點鐘兼職員工開始工作的人數。） b. 求解（a）中模型的LP 鬆弛。 c.求解出納員的最優時間表，並解釋結果。 d. 考察（c）中求出的結果後，銀行的經理意識到需要額外提出如下一些要求：每個時間段內至少要有一個全職員工，而且在所有員工中至少包括5個全職員工。重新構建模型以滿足這些要求，並求出最優解。 18.參考第8.3 節塞倫食品公司的份額選擇例子，回答下面問題。據說國王牌有意退出冷凍比薩餅業務。此時，塞倫食品的主要對手就變成了安東尼奧比薩餅。 a.計算安東尼奧牌比薩餅對錶8-4 中每位顧客的總效用。 b.假設安東尼奧牌比薩餅是塞倫的惟一競爭對手，列出能最大化市場份額的選擇問題並求解。最佳的產品設計是什麼？將會取得多大市場份額？ 20.參考第14題。管理層認為對紐約工廠的更新成本低估了。假設每個工廠的更新成本均為4 000萬美元，解答如下問題： 日.結合如上成本的變化，重新構建整數線性規劃模型。 b.根據上面的變化，就此更新計劃給管理層提一些建設性建議。 c•根據新的成本資料，重新求解。假設管理層認為在同一州關閉兩家工廠是不可能的，則如何把這一政策約束加人到你的0-1 整數規劃模型中去？ d. 基於成本的改變和（c）中的政策約束，你會給管理層提供什麼建議？ 22. 三角洲集團是一家衛生保健行業的管理諮詢公司。它目前打算組建一個小組以研究可能的新市場，並透過構建線性規劃模型來選擇組員。主管要求組員只能為3、5或7人。組員並不知道如何在模型中體現這個要求。 構建的模型要求組員從3個既定部門抽選，並使用如下變數定義： *—從部門1抽選的人數； *—從部門2抽選的人數； *，—從部門3抽選的人數。 試寫出約束條件來保證這個組由3、5或7個人組成。必要時採用下面的整數變數： 如果3個人分成一組，則y，=1，否則$ =0； 如果5個人分成一組，則y=1，否則½2=0； 如果7個人分成一組，則 =1，否則32=0。 24. 影劇院的管理者使用一個名為 SilverScreener 的數學規劃系統（屬於0-1 整數規劃模型）來求解多銀屏劇院（一個劇院有多個放電影的銀屏）一週內電影播放節目的計劃安排問題（Interfaces,2001 年5/6雙月刊）。現在，假設谷電影集團的管理層想要調查研究一下，在不同多銀屏劇院採用類似的放映計劃有何潛在差別。谷電影集團的管理層選擇了一個有2個銀屏的小型劇院作為研究的樣本劇院。研究打算構建一個整數規劃模型來幫助制定隨後4周的電影放映計劃時間表。共有6部電影可以選擇放映。下表列出了第一周和最後一週可以放映的電影以及每部電影最多可以播放的週數等資訊。
242 資料、模型與決策：管理科學篇電影編號第一週可以放映的電影最後一週可以放映的電影每部電影最多可以放映的週數 6 1 1 2 3 3 2 3 1 4 6 5 2 2 2 2 3 3 樣本劇院的全部電影播放計劃時刻表由6部電影的單個的計劃播放時刻表組成。每部電影的計劃播放時刻表需要包括以下具體內容：該部電影應該從哪周開始放映，該部電影在哪幾周連續播放。例如，電影 2 可以採取如下放映計劃時間表：在第一週開始放映，並且連續放映2周。劇院的政策是：一旦一部電影開始放映，則它必須連續放映幾周，不能有所中斷或重新開始。可以使用下面的決策變數來表示每部電影可能的計劃時間表： 3•｛：提脂電要：以部）間開始造裝數終如個例如：*392=1表示電影5在第3周開始放映，並且連續放映2周。為每部電影每個可能的計劃放映表分配一個獨立變數。 日.現有3個放映計劃和電影1相關。列出代表這3個放映計劃的變數表示式。 b.寫出一個約束條件來表達：電影1只能選擇一種放映計劃。 c.寫出一個約束條件來表達：電影5只能選擇一種放映計劃。 d.是什麼因素限制了第一週所能播放的電影數？寫出一個約束條件來限制第一週可以放映的電影總數。 e. 寫出一個約束條件來限制第一週可以放映的電影總數。 案例問題1課本出版 ASW 出版公司是一家小型大學課本出版公司，它目前需要對來年將出版的教材科目做出決策。以下為考慮出版的書籍和對應書籍3年中的預期銷售量。 各學科教材書籟型別商務微積分有限數學普通統計學數學統計學商務統計學新書悠訂本新書新書修訂本預期銷售鑼 （1000美元） 20 30 15 10 25 各學科教材書籍型別金融學財務會計管理會討英語文學德語新書新書餎訂本新書新書預期銷售簸 （1000美元） 18 25 50 20 30 被列為修訂本的書是已經與ASW簽了合同的，並將考慮以新版本發行的書。列為新書的書只是已由該公司審閱過，但是合同還未籤。 該公司現有3個人可接受這些任務。他們的可用時間不同：約翰有60天可用，蘇珊與莫尼卡都有40天。 每個人完成每項任務需要的天數在下表中列出。例如，如果要出版商務微積分，就需要30天約輸的時間和 40 天蘇珊的時間。“X”表示此任務不需要此人。注意，除了金融學，其他每項任務都需要至少兩人參與。 各學科數材約翰蘇珊莫尼卡各學科教材約輪蘇珊莫尼卡商務徽積分 30 40 X 金融學 X 有限數學 16 24 X 財務會計 X 警邇統計學 24 X 30 管理會計數學統計學 X 20 X 24 英語文學 40 商務統計學 10 X 16 德語 x 24 28 34 S0 26 30 30 36 ASW 在一年中不會出版兩本以上統計學的書和一本以上會計學的書。而且，已決定必定在兩本數學書 （商務微積分和有限數學）中出版一本，但不會都出版。
第8章虀數線性規劃 243 管理報告為ASW的管理編輯寫一份報告，說明你關於下一年最優出版方案的決定和建議。在你的分析中，可以假設所有書每本的固定成本和銷售收人是相同的。管理人員最關心的是銷售總數量的最大化。 管理編輯還要求你的建議考慮到以下可能的變化： 1.如果必要，蘇珊可以從另一任務中抽調出12天的時間。 2. 如果必要，莫尼卡也可再提供10天的時間。 3.如果一些修訂本可以推遲一年出版，應推遲嗎？很明顯，這樣公司會有丟失市場的危險。 在你的報告中請附上你分析的詳細細節。 案例問題3 含有更換成本的生產計劃巴克艾製造廠生產一種卡車製造中所用到的發動機頭。該生產線十分複雜，長達900英尺，能夠生產兩種型號的發動機頭：P頭和H頭。P頭用於重型卡車，而H頭用於小卡車。由於生產線在一個時間點上只能生產一種型號，所以生產線要麼設定成生產P頭，要麼設定成生產H頭，而不能同時生產兩種。每週末更換一次： 從生產P頭設定轉換到生產H頭設定的成本是500美元，反之亦然。當生產P頭時，每週最多可生產100件， 而H頭，每週最多可生產80件。 巴克艾剛剛完成了生產P頭的設定。管理者需要為隨後的8周制定生產和設定更換計劃。目前，巴克艾庫存中有125件P 頭和143件H頭。庫存成本按庫存價值的19.5%計算。P頭的生產成本是225美元，H頭的生產成本是310美元。制定生產計劃的目的是使生產成本、庫存成本與更換成本之和達到最小。 巴克艾已經收到一家發動機裝配廠9周內的需求計劃，如下： 產品需求靈周次產品需求假周次 1 2 P頭 55 55 44 5 45 H頭 38 38 30 0 48 6 7 8 9 P頭 45 36 35 35 H頭 48 58 57 58 安全庫存量要求每週末時庫存至少要達到下週需求量的80%。 營理報告為巴克艾製造廠的管理層制定一個隨後8周的設定更換與生產的計劃時間表。計劃時間表中需要說明總成本中有多少是生產成本，有多少是庫存成本，有多少是更換成本？ 附錄 8A 整數線性規劃的 Excel 解法利用工作表來求解整數線性規劃時的公式和方法與求解線性規劃問題的類似。事實上，工作表中的公式是完全相同的。只是需要在設定 Solver Parameters 和 Integer Options 對話方塊時增加一些資訊。首先需要在 Solver Parameters 對話方塊中加入條件來定義整數變數。另外，需要調整 Integer Options 對話方塊裡的Tolerance 值，從而得出結果。 下面我們將演示如何用Excel 來求解伊斯特伯恩房地產問題。含有最優解的工作表見圖8-14。我們將逐個講述工作表中的關鍵元素，演示如何求解，並對結果做出解釋。 8A.1公式圖8-14中，工作表中AI:G7單元格中存放的是資料和描述性標題。工作表中有陰影的單元格是 Excel Solver （決策變數、目標函式、約束條件的左端和約束條件的右端）所需要的資訊。 決策變數單元格 B17:C17是用來存放決策變數的。最優解為購買4 套連體別墅和2幢公寓樓。 目標函式公式=SUMPRODUCT （B7:C7,B17:C17）被放在B13單元格中，表示與最優解相對應的年現金流量。所得出的最優年現金流量是70000美元。 左端 3個約束條件的左端放在單元格 F15:F17中。 單元格 FIS = SUMPRODUCT （B4: C4， $B $17：$C$17）（複製到單元格 F16）
244 資料、模型與決策：管理科學篇 10% B 伊斯特伯恩房地產問題連體別墅價格（單位：$1000） 管理者的時間年現金流靈模型最大現金流量公寓 282 4 10 400 40 15 可用資金量（$1000） 管理者的可用時間可得連體別墅 2000 140 5 15 16 17 數連體別墅公寓購買計劃約束資金時間連體別墅左端 2928 右端 2000 140 入舊圖8-14 使用 Excel 求解伊斯特伯恩房地產問題單元格 F17=B17 右端3個約束條件的右端放在單元格 HI5:H17中。 單元格 HI5=G4（複製到單元格 H16:H17） 8A.2 線性規劃的 Excel解法開啟軟體，從Tool 選單中選擇 Solver 子選單，並在開啟的 Solver Parameters 對話方塊中輸入適當數值（參見圖8-15）。第一個約束條件是$B＄17：＄C$17=整數，也即 Solver單元格B17和C17中的決策變數必須是整數。 這個整數約束條件可以透過執行 Add-Constraint 程式來產生。對於單元格＄B$17：$C$17，選擇 Cell Reference 和“in”（整數）這兩個條件，而不是使用<=、=或＞=來表示約束條件。當選擇了“in”之後，約束條件的右端會自動出現整數字樣。圖8-15顯示了 Solver Parameters 對話方塊所需填寫的其他資訊。 接下來點選 Options 按鈕，選擇 Assume Non-Negative 復小貼士：在 Solver Parameter 對話方塊中選擇選框。針對伊斯特伯恩房地產問題，圖8-16列出了需要在 “bin”才能定義0-1 變數。 Solver Options 對話方塊中改置的全部資訊。在 Solver Options 對話方塊中點選 OK，隨後在 Solver Parameters 對話方塊中點選 Solve按鈕，計算機就會自動計算出最優整數結果。 圖8-14 中的工作表顯示最優解為購買4套連體別墅和2幢公寓樓，年現金流量為70000美元。 $8$17：$C$17 $B$17：$C$17 = intager $F$15：$F＄17 《= $H$15:1炸17 Standard Simpolax tp 圖8-15 伊斯特伯恩房地產問題的 Solver Parameters 對話方塊