言 13 預測模型、模擬模型和整數規劃模型。 透過預測模型可以對各個商店的每天的營業額做出預測。同其他製造廠商按年、月、周來預測所不同的是，Taco Bell 公司需要每15分鐘就對顧客到達量做出預測。然後根據這些結果預測次日一個分店有多少營業額資料，再使用模擬模型確定出工作人數以及如何對其進行安排。為了確定次日的工作表，模擬模型必須考慮到各個 Taco Bell 公司便利店的差異性、公司所採用的按單生產的食品準備方法以及顧客需求的隨機性。模擬模型將工作表制定好以後，再透過整數規劃模型確定出這一天需要多少人，分成幾班，以保證最低的人工成本。此外，整數規劃模型也考慮到了其他的客戶服務工作，這就使得經理可以排定其他的工作，如清潔、維持店面的衛生。 這套系統已經被公司所有的連鎖店採用。截止到1996年，有70%的代理經銷商也接受了該系統。 新系統使公司在1993~1996年的開銷節約高達4034萬美元。員工對系統也非常認可。其他快餐連鎖店表示，這套系統給 Taco Bell 公司提供了核心的競爭優勢。 資料來源：Nancy Bistritz， “Taco Bell Finds Recipe for Success，"OR/MS Today （October 1997）：20-21. 註釋與評論 1.美國勞工統計局將運籌分析員列入當今增長得最快的職業。從業者需學士學位。預計到2005 年，這一工作崗位數量將從1990年的57 000 個增加到100 000個，增長率高達73%。 2. 運籌學和管理科學研究所、決策科學研究所是兩所專業機構，它們定期出版期刊和時事通訊， 其內容包括運籌學以及管理科學方法的最新研究、應用。 本章小結本章討論的內容是管理科學如何幫助管理者更好地進行決策。決策制定過程和管理科學在此過程中扮演的角色是本章的重點。我們研究了在決策制定過程中何題的定位，並且對數學模型在此類分析中是如何應用的也做了大致介紹。 還有一點需要注意的是，數學模型和它所表示的實際情況或管理問題之間是有差異的。數學模型只是現實世界的抽象，因而我們不可能將現實情況的所有因素都表現出來。但是，只要能夠抓住問題的關鍵，提出推薦方案，那麼模型對決策就是有幫助的。 管理科學一個越來越明顯的特點就是努力尋找問題的最優解。在運用定量分析方法時，我們應該就是在試圖尋找最好的或者說是最優解。 專業術語 problem solving 解決問題在明確實際情況和期望情況之間的差異後，為解決這種差異而採取措施的過。 decision making 制定決策定義問題、明確備選方案、確定標準、評估備選方案和選擇一種備選方案的過程。 single-criterion decision problem」 單準則決策問題只依賴一個標準來尋找最優解的問題。 multicnteria decision problem 多準期決策問題有多個準則，透過考慮所有的準則，以找到最優解的問題。 decision 決策選擇出的備選方案。 model模型對真實物件或情況的反映。 iconic model 形象模型物理實體的仿製品，或真實物件的反映。 analog model 模擬模型也是物理模型，但是在外形上同所反映的真實物件或情況並不一樣。 mathematical model 數學模型用數學符號和表示式來表示實際情況。 constraints 約東條件問題中的限制和制約因素。 objective function 目標函式用來描述問題目標的數學方程。 uncontrollable inputs 非可控輸入無法由決策的制定者控制的環境因素。 controllable inputs 可控輸入可以由決策的制定者控制的因素。 decision variable 決策變數即可控因素。
14 資料、模型與決策：管理科學篇 deterministic model 確定模型模型中所有的非可控輸人都已知，且不可變。 stochastic/probabilistic model 隨機/機率模型至少有一個非可控因素是不明確的、可變的。隨機模型又稱為機率模型。 optimal solution 最優解特定的決策變數的值或使模型提供最優輸出的解。 infeasible solution 不可行解不滿足一個或多個約束條件的備選方案。 feasible solution 可行解滿足全部約束條件的備選方案。 fixed cost 固定威本不隨產量變化的那部分成本。無論你生產多少產品，固定成本總是一個定值。 variable cost 可變成本隨產量變化而變化的成本。 marginal cost 邊際成本在產量變化時，總成本的變化率。 marginal revenue 邊際收入在銷售量變化時，總收人的變化率。 breakeven point 盈虧平衡點總收人與總成本相同時的產量。 問題 2.列出決策過程的步驟，並討論。 4.某企業新建了一個廠房，可以生產500多種產品，有50多條不同的生產線和各類機器。合理制定生產時間表至關重要，因為倘若無法按時滿足顧客需求，就會有損於銷售。如果公司中沒有一個人有過這種生產運作方面的經驗，而且每週都要制定生產時間表，為什麼企業應該考慮採用定量分析的方式來完成工作時間表的制定？ 6.假設管理者可以從以下兩種數學模型中選擇一種來描述實際情況：（a）相對簡單的模型，是對實際情況的合理接近；（b）完整但十分複雜的模型，可以非常準確地描述實際情況。為什麼管理者很可能會選擇 （a）？ 8. 回憶一下第1.3節中的生產模型。 max $. t. 10x 5x≤40 $≥0 假設現在公司考慮生產第二種產品，它的單位利潤是5美元，單位制造用時為2小時。用y表示產品2的產量。 日.考慮同時生產兩種產品，請寫出數學模型。 b.確定該模型中的可控和非可控輸入。 c.畫出該模型的輸人輸出流程圖（參見圖1-5）。 d. * 和的最優解是多少？ e. 在（a）中所求的這個模型是確定模型還是隨機模型？請解釋。 10.A地的一家零售商店甲收到了從B地和C地運來的貨物。假設x表示從B地發來的貨物量，夕表示從C地發來的貨物量。 8.寫出該零售商店所收到的單位產品總數的表示式。 b.從B地運出的運費是每單位0.20美元，而從C地運出的運費是每單位0.25美元。寫出到該零售商店的總運費的目標函式。 c.假設該零售商店每月的需求是5000單位的產品，寫出要把5000單位產品運送到該店的約束條件。 d.在一個月中，從B地運出的貨物不超過4000單位，而從C地運出的不超過3000單位。寫出模擬這個情況的約束條件。 e.當然，貨物量是負數時是不能運送的。請結合目標函式以及約束條件，寫出滿足該零售商店需求的成本最低的數學模型。 12. 如果訂單規模大到可以帶來合理的利潤，O’Neill製鞋廠將會生產一種特殊型號的鞋子。對於每一個特殊型號的訂單，在生產裝置上公司都會花費1000美元的固定成本。每雙鞋的可變成本是30美元，售價是40 美元。 a.用x表示生產了多少雙鞋，寫出生產x雙鞋的總成本的數學模型。
第1章引言 15 b.用P表示總利潤，寫出一個訂購x雙鞋的訂單所能帶來的總利潤的數學模型。 c.在O'Neill鞋廠達到盈虧平衡前，鞋的訂單規模應該達到多大？ 14.Eastman 出版公司正在考慮出版一本關於電子資料表在商業上的應用的平裝版教科書。估計原稿準備、教科書設計以及生產裝置的固定成本是80000 美元，每本書可變的生產和原料成本估計是3美元，對書的需求估計是4000冊。該公司想以每本書20美元的價格賣給大學和學院的書店。 8.盈虧平衡點是多少？ b.需求是4000冊時，預期利潤或損失是多少？ c需求是4000冊時，為了達到盈虧平衡，該公司必須索取的最低單價是多少？ d.如果該公司認為單價可以增長到25.95美元，且不會影響4000冊的預期需求，你覺得采取什麼樣的行動最好？預期利潤或損失又是多少？ 16. Financial Analysts 有限公司是為許多客戶管理股票資產組合的投資公司。一名新客戶要求該公司處理80000 美元的投資組合。作為個人投資策略，該客戶希望限制他的資產組合在下面兩個股票的混合中： 股票每股價格每股最大預期年收益 Oil Alaska $50 $6 Southwest Petroleum $30 $4 可能的投資 $50 000 ＄45 000 令x= Oil Alaska的股份數；y= Southwest Petroleum 的股份數。 a.假設客戶希望最大化總的年收益，則目標函式是什麼？ b.寫出在下面3個約束條件下的每一個的數學表示式： （1）總的投資基金是80000美元。 （2）對 Oil Alaska的最大投資是50000美元。 （3）對 Southwest Petroleum 的最大投資是45000美元。 注：增加x≥0和y≥0的約束會提供一個投資問題的線性規劃模型。這個模型的解決過程將在本書第2章討論。 案例問題高爾夫聯合會的日程安排 Chris Lane 是 Royal Oak Country俱樂部的高層專業人員，他必須寫出高爾夫聯合會的比賽日程，這個比賽的賽季在明天下午4點開始。18對選手簽名參加了聯合會，每對選手必須在17周的賽季中完成與其他每一對選手的比賽。Chris Lane 以為寫出這樣一個日程安排是非常容易的事，但幾個小時後，他也沒能做出這份日程安排。因為在明天下午之前Chris Lane 必須做好這份日程安排，所以他請你幫忙。一個可能的複雜情況是，一對選手告訴 Chris，他們也許會取消這個賽季的比賽。他們告訴Chris，他們會在明天下午1點以前通知他是否參賽。 管理報告為 Chris Lane 準備一份報告。你的報告至少應該包括： 1.在為期17周的賽季中，使18對選手都能夠和其他的每對選手比賽的日安排。 2. 如果和 Chris 聯絡的那對選手決定取消比賽，一個可用的意外情況的計劃。 附錄1A 管理科學素軟體計算機技術的發展在將管理科學技巧運用於決策之中扮演了非常重要的角色。本書附帶有管理科學家軟體包。6.0版可以在Windows95 到Windows XP 作業系統中執行。該軟體可用於求解本書中提到的小規模問題。 用管理科學家軟體可以對運用計算機技術到決策中，給我們一個直觀的理解。 該軟體包括12個模組或程式，可以讓我們解決下列問題： 第2~ 6章線性規劃第7章運輸與指派第8章鏊數線性規劃第9章最短路徑及最小支撐樹第10章 PERT/CPM
16 資料、模型與決策：管理科學篇第11章庫存模型第12章等候線模型第14章決策分析第16章預測第17章馬爾可夫過程我們可以用管理科學家軟體來解這些問題。有時我們會插人一些管理科學家軟體求解問題的輸出結果的圖表。由於軟體都比較類似，我們不用去理解這些圖和裡面內容的含義。本文接下來介紹該軟體的主要特點及如何使用軟體。 1A.1 選擇一個模組啟動管理科學家軟體後，你會看到模組選擇的畫面，如圖1-7。你可以使用它的12個模組，只需選中，並按OK按鈕，軟體就可以將相應模組調人記憶體。 1A.2 檔案選單一個模組被載入後，你需要點選檔案選單， Selea LMooas 以著手解決問題。檔案選單提供以下操作： 新建選擇這項操作可以開始一個新問題。 對話方塊和輸人模板會在資料輸人過程中給你引導。 ct. MineacFrogremna Caharpencion 開啟選擇這項操作可取回以前儲存的問題。 Lear Frogrommne 一旦你想解決的問題被選定，它會出現在幕上以供核實。 Minlmot Spanning iee 儲存進人一個新問題後，你可能需要儲存以便日後使用或修改。儲存操作會引導你命名和儲存過程。如果建立一個以問題命名的資料夾， 開啟和儲存操作會自動為你開啟那個問題的文件夾。 更改模組這項操作回到如圖1-7的螢幕控制，這時可以選擇其他的模組。 圖1-7 管理科學察軟體6.0版模組選擇畫面退出這項操作可以退出管理科學家。 1A.3 編輯選單一個新問題解答後，你可能需要對要解決的同題做一個或幾個修改。編輯選單提供了這樣的功能，它可以顯示問題，然後在解答或儲存問題前對它做修改。線上性或整數規劃模型裡，編輯選單還包括透過增加或減少變數和增添或刪除約束條件來改變問題的規模。運輸和指派問題的編輯選單中，也提供類似的改變問題規模的操作。 1A.4 求解選單求解選單提供了以下3項操作： 求解這項操作解答現有問題並把結果顯示在螢幕上。 列印一旦解答在解幕上輸出後，列印操作就可以把這個解答傳送給印表機。 作為文字檔案儲存一旦解答在螢幕上輸出後，儲存操作能把這個解答作為一個文字檔案儲存下來。文字檔案可以透過文字編輯器訪問，這樣解答結果就可以作為解決報告的一部分顯示。 1A.5 資料輸入建議任何時候一個新問題被選擇後，恰當的模型就會提供對話方塊，並描述問題應輸人的資料形式。使用管理科學家軟體，你會發現以下的資料輸入建議很有用： 1. 輸人資料時不要輸人逗號（，）。例如，數值104，000應以六位輸人：104000。 2. 輸人利潤和成本資料時不要輸入貨幣符號（$），例如，＄20.00的成本應輸人20。 3. 如果需要百分數時，不要輸人百分號（%）。例如，25%應以25輸人，而不是25%或.25。 4.有時模型需要用分數表示，如1/4、2/3、5/6等。管理科學家軟體的資料輸入必須使用小數的形式。 分數1/4可以以.25 的形式輸人。但是有些分數如2/3、5/6 被表示為迴圈小數的形式。在這種情況下，按慣第1章引言 17 例我們推薦保留5位小數，如.66667 和.83333。 5.最後我們建議，在通常情況下您可以嘗試轉化非常大的錄入資料，以便在計算機上錄入和操作較小的數字。例如，成本2 500000美元轉化為2.5，應理解為間題中涉及的資料是以百萬元為單位的。 附錄1B 用 Excel 做盈虧平衡分析在第1.4節中我們以 Nowlin塑膠製品公司的生產為例，說明定量模型是怎樣聯絡一個既定產量或預計銷量來幫助經理確定專案的成本、收人和利潤。在本附錄裡，我們將透過演示如何使用微軟的Excel 來完成 Nowlin 塑膠製品公司生產的定量分析，介紹工作表程式的應用。 請看圖1-8中的表單。我們開始在這個表單的上部輸人問題的資料。單元格B3 中數值3000 是安裝費用， 單元格 B5 中數值2是單位可變的人工和原料費用，單元格B7 中數值5是單位售價。通常每當我們用Excel做定量分析時，我們會在表單的上部輸入問題的資料，將底部留作模組展開。單元格 A10的“模組”標籤幫助提供這個提示。 表單中模組部分的單元格B12是計劃的單位產量。因為總成本、總收人和總利潤的值都取決於這個決策變量的數值，我們在圖1-8中使單元格B12 的周圍顯示出粗方框，以著重強調一下。基於單元格B12中的數值， 單元格B14、B16 和B18中的公式分別用來計算總成本、總收入和總利潤（虧損）的值。首先，總成本是固定成本（單元格B3）與總可變成本之和。總可變成本—產品的單位可變成本（單元格 BS）和產量（單元格 B12）—用B5*B12 給出。這樣，我們在單元格 B14 中輸人公式=B3+BS * B12 來計算總成本。其次，總收人是產品的單位售價（單元格B7）和產量（單元格B12）的乘積，在單元格B16 中輸人公式 =B7*B12。最後，總利潤（虧損）是總收人（單元格 B16）和總成本（單元格B14）的差。這樣，在單元格 B18 中我們輸入 T公式=B16-B14。圖1-8所示的表單顯示了用來計算的公式；我們稱它為一個公式表。 塑膠製品公司固定成本單位可變成本單位售價 3000 2 塑膠製品公司固定成本單位可變成本單位售價 ＄3 000 $2 $5 模組產量總成本總收人總利潤（損失） 800；=B3+B5*B12 =B7*B12 =B16-B14 模組產量總成本總收人總利潤（損失） 800 $4 600 $4 000 -$600 圖1-8 Nowlin 塑膠製品公司生產公式表單示例圖1-9 Nowlin 塑膠製品公司生產例子中生產800 單位的解為了檢驗一個特定產量數值的結果，我們在單元格 B12 中輸人數值800。圖1-9所示的表單中顯示了由公式得到的數值：800單位的產量導致4600 美元的總成本、4000美元的總收人和600美元的虧損。檢驗不同產量的結果，我們只需要在單元格B12 中輸人不同的數值。檢驗不同的成本和售價的結果，我們僅需要在表單的資料部分輸人合適的數值，結果會在表單的公式部分顯示出來。 我們在第1.4節中例示了盈虧平衡點，下面來看看Excel的單變數求解是怎樣用於計算 Nowlin 塑膠製品公司生產例項中的盈虧平衡點的。
18 資料、模型與決策：管理科學篇使用 Excel 的單變數求解工具確定盈虧平衡點盈虧平衡點是總收入等於總成本，即利潤為零時的產量。確定盈虧平衡點的一種方法是試錯法。例如，在圖1-9中，我們可以看出試用一個800單位的產量導致600美元的虧損。因此，800單位的產量不可能是盈虧平衡點。繼續試驗其他的產量值，我們可以很容易地透過在單元格B12 中輸人不同的數值，觀察由此產生的在單元格B18中的利潤或虧損。一個更好的方法是使用Excel的單變數求解工具來確定盈虧平衡點。 Excel 的單變數求解工具允許使用者在輸入格內確定一個數值，使相關的結果格中產生一個等於要求的數值 （稱為日標值）。在一些盈虧平衡點分析中，這個目標值被設定為使總利潤為零的一個合適的產量。單變數求解能讓我們找到恰好使Nowlin 塑膠製品公司總利潤為零的產量。以下的步驟說明了怎樣使用單變數求解尋找 Nowlin 塑膠製品公司的盈虧平衡點。 第一步點選工具（Tools）選單。 第二步選擇單變數求解（Goal Seek）操作。 第三步在出現的單變數求解（Goal Seek）對話方塊中： 在目標單元格 （Set cell）中輸入 B18 在目標值格（To value）中輸入0 在可變單元格（By changing cell）中輸入 B12 單擊 OK 圖1-10是完成的單變數求解對話方塊，圖1-11是點選確定後得到的表單。單元格B18 中的總利潤為零，單元格B12中的產量已被設定為盈虧平衡點1000。 B18 B12 團1-10 Nowlin 塑膠製品公司問題的單變最求解對話方塊塑膠製品公司固定成本單位可變成本單位售價 ＄3 000 $2 $5 模組產殿總成本總收入總利潤（損失） 5000 5 000 0 圖1-11 用 Excel 的單變最求解工異來解出 Nowlin 塑膠製品公司的盈虧平衡點，
第2章線性規劃導論線性規劃是一種幫助管理者制定決策和解決問題的方法。在今天激烈的商業競爭中，有很多應用線性規劃的例子。比如，柯達公司應用線性規劃確定在哪裡使用它們在全世界的裝置進行生產；GE Capital 公司應用線性規劃幫助它們確定最優的租賃結構；Marathon 石油公司應用線性規劃混合汽油以及評估新的終端或管線的經濟學問題。在專欄2-1 中，MeadWestvaco 公司的木材採伐模型也是應用線性規劃的一個例子。本章專欄2-2中還介紹了日本大阪某高速公路收費站應用線性規劃控制交通問題的例子。 為了說明線性規劃問題所共有的特性，我們考慮以下幾個典型的應用： 1.製造商希望建立一個生產時間表和庫存計劃，以滿足未來一段時間的市場需求。最理想的情況是，既滿足市場需求，同時又使生產和庫存的成本最低。 2.財務分析師必須選擇若干支股票和債券進行投資組合，使其所做的投資組合的回報最大。 3. 營銷經理希望將固定的廣告預算在廣播、電視、報紙、雜誌等廣告媒體中進行最好的分配，使廣告效果最好。 4.一冢公司的倉庫分佈於全美各地。現在有一些顧客訂單，公司希望確定每個倉庫到每個顧客的發貨量，使總的運輸成本最低。 專欄2-1實踐中的營理科學 MeadWestvaco 公司的木材採伐模型 MeadWestvaco 公司是期刊雜誌、書籍、商業印刷以及企業檔案等用紙的主要生產商。該公司還生產紙漿和木材，併為飲料及其他消費市場設計製造包裝系統，是一家在塗層板及集裝箱運輸界內的世界級領導企業。MeadWestvaco公司的定量分析是由公司的決策分析部門開發和實施。該部門除了為決策者提供定量方法的分析工具外，還提供個別的分析與建議。 MeadWestvaco 應用定量模型幫助公司進行木材基地的長期管理。透過使用大規模線性規劃模型， 公司制定了長期的木材採伐計劃。這些模型考慮了木材的市場條件、紙漿用木材的要求、採伐能力以
20 資料、模型與決策：管理科學篇及一般的森林管理規律。在這些約東條件下，模型給出了基於貼現現金流量的最優的採伐和採購安排，其中考慮了森林的生長、木材實用性和通常的經濟條件等各種假設的變化。 定量方法還用線上性規劃模型的輸入方面。木材價格、供應以及加工廠要求必須隨時間變化進行預測，而且在地塊評價和森林生長計劃方面還採用了先進的抽樣技術，因而整個採伐計劃都是由定量方法完成的。 資料來源：基於 MeadWestvaco 公司的 Edward P. Winkofsky 博士提供的資訊。 這些只是成功應用線性規劃的一小部分，但足可以看出線性規劃原本稱為“線性結構規劃線性規劃應用的廣泛性。經過仔細的觀察，我們可以發現這 （programming in a linear structure）”，但在些例子有共同的特點。在每個例子當中都要求使某個量最大 1948年，Tjalling Koopmans 認為這個名字太化或最小化。在第一個例子中，製造商希望最小化成本；在長了，建議 George Dantzig 將其縮寫為線性第二個例子中，財務分析師希望最大化投資收益；在第三個規劃（linear programming）。Dantzig採納了例子中，營銷經理希望最大化廣告效益；在第四個例子中， Koopmans 的建議，從此將該領域更名為我公司希望最小化運輸成本。在所有線性規劃問題中，某個量們現在所知道的線性規劃。 的最大化或最小化稱為目標。 線性規劃同題還有第二個特點，也就是存在某些限制或約束條件，這些約束條件某種程度上限制了對目標的追求。在上面的例1中，製造商要滿足市場的產品需求，而且還要受制於生產能力。財務分析師的投資組合問題既受投資總額的限制，又受每支股票或債券最大投資額的限制。營銷經理對廣告媒體的選擇決策既受廣告預算的約束，也要受廣告媒體的限定。在運輸問題中，費用最小的排程安排必須受到各個倉庫儲存量的限制。因此，有約束條件是每個線性規劃問題所共有的另一個特點。 2.1 一個簡單的最大化問題 Par 公司是一個生產高爾夫器材的小型公司，它決定進人中等和高等價位的高爾夫袋市場。分銷商對新產品十分感興趣，且同意買進Par公司未來3個月內的全部產品。 在對整個高爾夫袋生產步驟進行了詳細調查以後，管理層明確了高爾夫袋的生產過程： 1.切割並印染原材料； 2. 縫合； 3. 成型（插人支撐架、球棒分離裝置等）； 4．檢查與包裝。 生產主管詳細分析了生產過程的每一步，得出以下結論：生產一個中價位標準高爾夫袋需要用7/10小時切割與印染，1/2小時縫合，1小時部門成型，1/10 小時檢查與包裝。生產一個高階袋則需要1 小時切割與印染，5/6 小時縫合，2/3 小時成型，1/4小時檢查與包裝。生產資訊列於表2-1中。 Par 公司的生產還受各個部門生產時間的限切割與印染縫合成型檢壹與包裝表2-1 生產每個高爾夫袋所膏要的時間生產時間（小時） 標準袋高階袋 7/10 1/2 1 $/6 - 2/3 1/10 1/4 制。經過對各個生產部門工作量的研究，生產主管估計未來3個月內每個部門可用的最大生產時間分別是：切割與印染630 小時，縫合600小時，成型708 小時，檢查與包裝135小時。 會計部門經過對生產資料、各種生產成本的分析得出了以下的結論：生產一個標準袋的利潤°是 10美元，生產一個高階袋的利潤是9美元。我們現在可以為 Par公司建立一個數學模型，來決定標準 O 從會計學的角度看，利潤更能準確地描述每個袋的邊際貢獻。比如，不包括分攤的同接費和其他共享成本。
第2章線性規劃導論 21 袋和高階袋各生產多少，以最大化公司的利潤貢獻。 2.1.1 問題模型化問題模型化或稱建模，是將語言文字描述轉化為數學描有一點必須明確，我們所追求的是利述的過程。可以說，這是一項藝術創造，只有透過不斷的練潤貢獻最大化，而不是利潤最大化。利潤習才能熟練掌握。雖然實際生活中的每個問題都有其獨特之還要減去日常開支等成本。 處，但其中大部分還是有共性的。所以，我們可以學習一些具有普遍適用性的方法來幫助我們建立效學模型，這些方法對初學者尤其有效。下面我們以 Par公司為例講解一下建立數學模型的基本原則。 全面地瞭解問題我們選擇Par 公司介紹線性規劃，是因為它容易理解。對於一個比較複雜的例子，模型需要詳細考慮的因素可能比較多。處理複雜的例子，我們可以先快速地瀏覽一下整個問題， 以瞭解問題所包含的內容，做一些記錄對抓住關鍵問題和重點事實會有很大幫助。 描述目標本題的目標就是使產品的利潤貢獻最大。 描述約束條件對於生產時間來說，一共有4 個約束條件，它們制約著兩種高爾夫袋的生產。 約束條件1：用於切割與印染的總時間必須小於等於切割與印染部所能承受的最大工作時間。 約束條件2：用於縫合的總時間必須小於等於縫合部所能承受的最大工作時間。 約束條件3：用於成型的總時間必須小於等於成型部所能承受的最大工作時間。 約束條件4：用於檢查與包裝的總時間必須小於等於檢查與包裝部所能承受的最大工作時間。 定義決策變數 Par公司可以控制的輸人有兩個：（1）標準袋產量；（2）高階袋產量。設 S——標準袋產量； D—一高階袋產量。 用線性規劃的術語，S和D叫做決策變數。 用決策變數寫出目標 Par 公司的利潤來源於兩方面：（1）生產S個標準袋所獲得的利潤； （2）生產D個高階袋所獲得的利潤。如果公司生產一個標準袋創造10美元利潤，那麼生產S個標準袋可獲得10S美元。同樣，如果生產一個高階袋獲得9美元，那麼生產D個高階袋可獲得10D美元。 因此，我們有總利潤貢獻=10S+9D 因為公司的目標是使總利潤貢獻最大，總利潤貢獻又是決策變數S和D的函式，所以我們稱10S+9D 為目標函式。使用 max 來表示使函式最大化，則Par公司的目標如下： max 10S +9D 用決策變數寫出約束條件約束條件1： （切割與印染所用的時間）≤（公司切割與印染部的最大工作時間） 因為每個標準袋都需要7/10個小時切割與印染，因此製造S個標準袋所需要的切割與印染時間是 ZS。同理，製造一個高階袋需要1 小時切割與印染，製造 D個高階袋所用的切割與印染時間是1D。 於是生產S個標準袋和 D個高階袋共需要的切割與印染時間是： 總切割與印染時間=⅞S+1D 生產主管估計的總切割與印染的可用時間為630小時，所以以上的生產組合需要滿足 ⅞S+1D≤630 （2-1） 約束條件2： （縫合所用時間）≤（公司縫合部的最大工作時間） 從表2-1我們知道，每個標準袋的縫合時間是1/2 小時，每個高階袋的縫合時間是5/6小時，而可用的縫合時間是600小時，所以
22 資料、模型與決策：管理科學篇 ½S+⅚D≤600 （2-2） 約束條件3： （成型所用時間）≤（公司成型部的最大工作時間） 每個標準袋需要1小時成型時間，每個高階袋需要2/3小時成型時間。成型部最大的工作時間是 708 小時，所以 IS + ⅔D≤708 （2-3） 約束條件4： （檢查與包裝所用時間）≤（公司檢查與包裝部的最大工作時間） 檢查與包裝一個標準袋需要1/10小時，檢查與包裝一個高階袋需要1/4小時，而檢查與包裝部的最大時間是135小時。所以 %S+¼D≤135 （2-4） 我們已經列出了與4個部門有關的約束的數學關係。還有其他約束嗎？Par 生產高爾夫袋的產量能是負值嗎？當然不能！所以，為了防止決策變數S和D取負值，必須 S≥0且D≥0 （2-5） 這兩個條件必須加上。這樣的約束可以確保模型的解是非負值，因此它被稱為非負約束。非負約束在線性規劃問題裡經常縮寫成： S,D≥0 2.1.2 Par 問題的數學描述 Par 公司問題的數學描述或數學構造已經完成。我們已經成功地將問題的目標和約束用一組數學關係式—數學模型表述出來。Par 問題完整的數學模型如下： max 10S +9D 3.t. ⅞S+ID≤630 切割與印染 ½S+⅝D≤600 縫合 1S+⅔D≤708 成型 %S+¼D≤135 檢查與包裝 S,D≥0 （2-6） 我們接下來的工作就是找到合適的組合（即S和D的組合），既滿足約束條件，又能使目標函式的值最大。一旦這些值都計算出來了，我們也就找到了問題的最優解。 我們稱 Par 問題的數學模型為線性規劃模型或線性規劃。正如我們上文所言，該問題有目標和約束條件，這是所有線性規劃問題共有的特點。那麼，它還有什麼特點使其成為線性規劃問題呢？我們發現它的目標函式和約束條件（約束不等式的左邊）都是決策變數的線性函式。 線性函式是指函式中的每個變數都是分離的並且冪次為1。目標函式（10S+9D）就是線性函式， 因為它的兩個變數是分離的，並且是一次冪。同理，切割與印染的生產時間函式（%S +1D）也是決策變數的線性函式。所有約束不等式的左側（約束函式）都是線性函式。因此，我們稱這個問題的數學模型為線性規劃。 線性規劃（linear programming）與計算機程式 （computer programming） 沒什麼關係。規劃（programming）這個詞是指選擇一系列的活動。當數學模型中只有線性函式時，線性規劃就進行與之相應的一系列的線性計算。 註釋與評論 1. 線性規劃問題的3個基本假設是：比例性、可加性、可分性。比例性是指與目標函式值和約束條件所對應的資源儘與決策變數值成比例。可加性是指目標函式的值和使用資源總量分別可以透過匯第2章線性規劃導論 23 總所有的決策變數對目標函教的貢獻和各個決策變數使用資源數量而得到。可分性是指決策可變數是連續性的。可分性假設與非負條件意味著決策可變數可以取大於或等於零的一切數值。 2. 管理科學家軟體構造並解決了包含一個目標函式與若干約東條件的各種各樣的數學模型，這類模型稱為數學規劃模型。線性規劃模型是數學規劃模型的一種，它要求所有的目標函教和約東條件都是線性的。 2.2 圖解法線性問題只需包含兩個變數就可以使用圖形求解。我們透過畫圖表示 Par 公司問題的可能的解（S 和D的值）來開始介紹圖解法。如圖 D 2-1所示，我們用橫軸代表S，縱軸代表D。於是圖形上的任意一點都對應一 1 200 個確定的S和D的值，可以透過對此點作垂直線和水平線分別來求得。因為每 1000個點（S,D）都是一個可能的解，所以圖形上的點稱為解點。S=0且D=0 800 村應 S-200.D-800的解點 -f（20.80w） 的解點就是原點。因為§和D都應該是 600非負的，所以圖中只畫出了S≥0且 D≥0的部分。 前面我們已經得出了用來表示切割 4001～一、 與印染時間的約束函式： *應S-400D-300的解點 （40.300 200⅞S+1D≤630 為了找到所有滿足此關係的解點，我們先將不等式改寫為等式。即，求出滿足 0 200 400 ⅞S+1D =630的點。因為對應該方程的圖形是一條直線，所以我們只需確定 600 800 標準袋產量圖2-1 Par 公司兩個變數的解點 T600 120S 兩點就可以畫出整條直線。假設S=0， 解方程求D，可以得到解點（S=0,D D =630）。為了找到另一個滿足方程的 1 200~ 點，我們假設D=0，解出S，我們得到 ⅞5+1×0=630， 即S=900。因此第 1000二個滿足方程的解點就是（S=900,D =0）。有了以上兩點，我們可以畫出滿 800 （0,630） 足等式 ⅞S+1D =630 的直線。此線稱為切割與印染的約束線，如圖2-2。我們用C&D來表示這條直線。 切割與印染的約束條件是 ZS+1D≤630 你能求出所有滿足約束條件的解嗎？直線%S+1D=630上的任意點一定滿足約束條件。但如何找到滿足％S +1D 400200YoS+1D-630 •（200,200） • （600,500） 200 400 600 800 1000 標準袋產量圈2-2 切劑與印染約東線 1200 1400 一。
24 資料、模型與決策：管理科學篇 ＜630的解點呢？觀察一下這兩個解：（S=200，D=200）和（S=600,D=500）。從圖2-2中我們可以看到，第一個解點在約束直線的下面，而第二個解點在約束直線的上面。哪個解滿足約束條件呢？ 將（S =200，D=200）代人方程，得到 %65+1D=%×200+1×200 =340 因為340小時小於部門的最大工作時間630，所以生產組合或解點（S=200，D=200）滿足該約束。 將（S=600，D=500）代入，我們得到 ⅞S+1D=%×600+1 x500 =920 因為920小時大於630 小時，所以解點（S=600，D=500）不滿足此約束條件，因此它就不是可行解。 如果一個解點對某一約束條件是不可行的，那麼它所在直線的這一側的解便都是不可行的。如果一個解對某一約束條件是可行的，那麼它所在的這一側的解對這一約束條件來說便都是可行的。所以我們只需要驗算一個解，便可以確定出約束直線的哪一邊是可行解。如圖2-3，我們用陰影區域表示滿足切割與印染約束條件的解。 D 1200 1000個 800 高階袋產量切割與印染約束條件 （C&D） 600 400 S+ID=630 200 0 200 400 600 800 1000 1200 標準袋產量圖2-3 對應切割與印染約束條件的可行解（陰影部分） 1400S 我們繼續可以得到對於每個單獨的約束條件可行解的範圍。對每個約束條件的可行解如圖2-4所示。 四個圖各自對應相應的約束條件。線上性規劃問題裡，我們需要找到能夠同時滿足所有約束條件的解。為了找到這些可行解，我們把所有4個約束條件畫在一張圖裡面，就可以找出同時滿足所有約束條件的區域。 圖2-3和圖2-4重疊起來，就可以在一張圖裡畫出4條約束線，如圖2-5所示。陰影區域包含了每一個同時滿足所有約束條件的解點。我們稱能夠滿足所有約束條件的解為可行解，可行解所在的陰影區域稱為可行域。任何在可行域邊界上或在可行域內的解點都是可行解點。 確定出可行域後，我們可以運用圖解法求Par 公司問題的最優解。一個線性規劃問題的最優解就是使得目標函式得到最優值的可行解。讓我們從另一張圖上開始我們的圖解法尋優步驟，如圖2-6。
第2章線性規劃導論 25 D 1200 D 1200-，（0,1 062） 1 000 1000 （0,720） 800 縫合約束條件 600 高階袋產量 $：800 600 IS+⅔3D 成型約束條件 400 1/5+⅝D=600 400 200 200 0 200 400 800 1000 1200，（1200,0） 什c 1 400，（708，① 1 200 1400 600 標準袋產曩 200 400 600 800 標準袋產量 1000 D 12001000 800 600 （0， $40） 檢查與包裝約束條件（1&P） 400 1/105+14D= 135 200 （1350,0） 0 200 400 1000 1200 14005 600 800 標準袋產鱟圖2-4 縫合、成型、檢查與包裝約東條件的可行解（陰影部分） 求最優解的一個方法就是計算每個可行解的目標函式值，取最大值的可行解就是最優解。這種方法的困難之處在於可行解有無窮多，你不可能計算無窮多個可行解，所以這種反覆實驗的方法無法找到最優解。 相對於每一個可行解計算利潤貢獻，不如對任意的利潤貢獻值，找出所有的能產生同樣目標值的可行解（S，D）。比如，哪些可行解可以產生1800美元的利潤貢獻呢？也就是在約束區域內找出滿足以下目標方程的S和D。 10S+9D=1800 這種表示就是一個直線方程。所以，所有產生1800美元利潤貢獻的可行解點（S,D）一定在直線上。前面我們已經學習瞭如何畫約束直線，同樣可以畫出利潤或目標函式直線。令S=0，那麼D= 200，解點（S=0，D=200）在這條直線上。類似地，令D=0，解點（S=180，D=0）也在這條直線上。透過這兩個點的直線上所有的解點都同樣有1800美元的利潤貢獻，如圖2-7所示。 因為我們的目的是要找到產生最大利潤貢獻的可行解，那麼我們選擇大一些的利潤貢獻值，然後找出相應的可行解，比如，對利潤貢獻值3600 美元和5400美元，要求相應的可行解，就需要求滿足如下直線方程的S和D。 10S+9D=3 600 且 10S +9D=5 400 用同樣的辦法，我們將3600美元和5400美元的利潤線畫在圖2-8上。儘管不是所有5400 美元
26 資料、模型與決策：管理科學篇 1200 1000 800一 600 400 200 可行域 0 200 圖 2-5 400 600 800 標準袋產量 1000 Par 問題的所有約束表示的可行域 1 200 1400 D 600 400 200 可行域 S 0 200 400 標準袋產鬣 600 800 圖2-6 Par 公司問題的可行域的利潤線的點都是可行解，但至少有一些直線的點在可行域裡面，因此找到產生5400 美元利潤貢獻的可行解是可能的。 我們可以找到有更高利潤貢獻的可行解嗎？從圖2-8上已經畫出來的利潤線我們可以發現一些規律性的東西：（1）利潤線之間彼此平行；（2）利潤越高的直線離原點越遠。這兩個發現也可以用代數第2章線性規劃導論 27 600 高階袋產量 400 （0 200 0 利潤線 103+9D=1800 61$0.0 200 S 圖 2-7 400 標準袋產量 600 Par 公司1 800 美元的等值利潤線 800 600 高階袋產量 200 10S+9D 10S+90=3 600 10S+9D 1800 0 \200 \400 標準袋產量 1600 圖2-8 Par 公司的幾條等值利潤線方式表達。令P表示總的利潤貢獻值，目標函式為 P=10S+9D 解出用S和P表示的D，得到 800 —S 9D=-10S+P D=-%S+⅑P （2-7） 式（2-7）是關於S和D的斜截式直線方程，S的係數-%是斜率，第二項⅛P是D的截距〔即式 （2-7）與橫軸軸相交時的D值。將P=1800,P=3600，P=5 400分別代入方程，就得到圖2-8已
28 資料、模型與決策：管理科學篇經畫出來的直線的斜截式方程： P=1800時， D=-%S+200 P =3 600時， D=-1%S+400 P=5 400時， D=-%S+600 每條利潤線的斜率都一樣（-10/9），因為它們互相平行。另外，隨著利潤貢獻的增加，D的截距也增加，所以，利潤越高的直線離原點越遠。 因為利潤線之間彼此平行而且利潤越高的直線離原點越遠，所以，我們從原點平行外移利潤線就可以得到更大的目標函式值，但是當移到某一個點時再外移利潤線就會完全移出了可行區域。因為可行區域以外的解是不被接受的，所以，可行區域上利潤最高的點就是線性規劃的最優解。 現在你應該可以得出Par 問題的最優解了。用一把尺子或一張紙的邊從原點儘可能地外移，最後達到的可行區域的點是哪個點？這個點就是最優解，如圖2-9所示。 600 最大化利潤線 IOS + 9D=7668 量 400 最優解 200 S 200 400 標準袋產量 600 800 圖 2-9 Par 公司問題的最優解最優解處S和D的值即決策變數的最優解。能否準確地確定S和D的值取決於圖是否畫得準確。 從圖2-9可以看出，最優的生產組合是大約生產標準袋550個（S），高階袋250個（D）。 仔細觀察圖2-5和圖2-9，發現最優解在切割與印染約束線和成型約束線的交點處。即最優解點既在切割與印染約束線上 ⅞S+1D=630 （2-8） 又在成型約束線上 IS+ ⅔D=708 所以，決策變數S和D的最優值必須同時滿足式（2-8）和式（2-9）。由式（2-8）解出S得 ⅞S =630-D （2-9） 即 S=900-1%D （2-10） 將式（2-10）代人式（2-9），得 D=252 將D=252 代入式（2-10），得 S=540
第2章線性規劃導論 29 最優解的精確位置 S=540，D=252。所以Par 公司最優的生產量為540個標準袋和252個高階袋，利潤貢獻為10x540+9×252=7668美元。 對只有兩個決策變數的線性規劃問題，決策變數的精確解可以先由圖解法確定最優解點，然後解相應的兩個方程得到。 2.2.1 畫圖時的注意事項圖解法的一個關鍵就是畫線性規劃的約束直線和目標函式。畫直線方程的過程我們是採用先找出滿足方程的任何兩個點，然後過這兩個點畫一條直線。在Par 公司問題的約束條件裡，兩點很容易得到。含S=0，解該約束方程，然後令D=0，解出S來得到。對於切割與印染約束線： ⅞S+1D=630 這個過程得到兩個點（S=0，D=630）和（S=900，D=0）。透過這兩個點畫一條直線，就得到切割與印染約束線。 如果約束線上的兩個點可以確定，那麼雙變數線性規劃中的所有的約束線和目標函式都可以畫出來。但是，找出約束線上的兩個點並不都像 Par公司問題那樣容易。例如，假定一個公司製造兩種型號的小型手提電腦：助手型（A）和專業型（P）。管理層需要給銷售部門50臺專業型電腦，並預計這種專業型產品銷售量最多會是助手型的1.5倍。由此產生的需求約束條件是： P-50≤½A 或 2P-100≤A 或 2P-A≤100 用解方程的形式，令P=0，我們得到點（P=0，A=-100）是在約束線上。令A=0，我們得到約束線上的第二個點（P=50,A=0）。如果我們只要畫圖形的非負部分（P≥0，A≥0），那麼第一個點 （P=0，A= -100）就沒法描出來，因為A=-100並不在圖形上。遇到這種可以找到兩個點，但是有一個或兩個點都不能畫在非負區，最簡單的方法是將圖形拉大、展開。在這個例子中，點（P=0， A = -100）可以描在包括負A軸的擴充套件的圖形上。一旦滿足約束方程的兩個點都定位好了，也就可以畫出線來了。約束線和約束條件2P-A≤100的可行解顯示在圖2-10中。 我們看看另一個例子。考慮一個包括兩個決策變數（R 和T）的問題。假設 R產生的單位數至少等於『產生的單位數，滿足該要求的約束條件就是： R≥T 或 R-T≥0 為了找到所有滿足上面約束條件的等式形式，我們首先設R =0並解出T。這個解表明原點（T= 0,R=0）在約束線上。令T=0並解出R，得到相同的點。但是我們也可以將T值設為非零值並解出 R。例如，令『=100 並解出R，我們得到線上的點（T=100，R=100）。用這兩個點（T=0,R=0） 和（T=100，R=100），約束線R-T=0 和滿足R-T≥0的可行解就按圖2-11 的方式描出來了。 2.2.2 圖解法求解最大化問題小結正如我們所看到的那樣，圖解法是用於解決雙變數線性規劃問題（如 Par 公司問題）的一種方法。用圖解法求解最大化問題的過程可小結如下： 1. 為每個約束條件畫出可行解圖形。 2. 識別出同時滿足所有約束條件的解的可行域。 3. 畫出目標函式線，表示可產生特定目標函式值的決策變數的值。 4. 著使目標函式值最大化方向平行移動目標函式線，直到移動到可行域的邊界。 5.在目標函式線上具有最大值的任何可行解都是一個最優解。 2.2.3 鬆弛變數除了最優解和與之相關的利潤貢獻，Par 公司管理層很有可能希望知道關係每個生產運作所需要的生產時間的資訊。我們可以透過將最優值（S=540，D=252）代人線性規劃的約束條件裡來獲得該資訊。
30 資料、模型與決策：管理科學篇 300 200 300 200 100 -4=100 （100， 100） R-T=0 （50,0） 100 0 100 200 —P 300 （0,0） （0，-100） MR -100 100 200 300 圖2-10 約束條件2P-A≤100 的可行解圖2-11 約束條件R-T≥0 的可行解約束條件切割與印染縫合成型檢查與包裝當S =540及D=252時所糬的小時數 （7/10） x540+1x252 = 630 （1/2） ×540 + （5/6） ×252 =480 1 x540 + （2/3） ×252 = 708 （1/10） x540+（1/4）x252 =117 可用小時數未用小時數 630 600 708 135 0 120 0 18 因此，這個完全方案告訴管理層生產540個標準袋和252個高階袋將需要耗用所有可用的切割與印染時間（630小時）以及所有可用的成型時間（708小時），但還有600-480=120個縫合小時、 135-117=18個檢查與包裝小時剩餘。120個縫合小時和18個檢查與包裝小時對於這兩個部門來說就是鬆弛的。線上性規劃術語裡，對a≤約束條件的任何未用產能，都稱為與約束條件對應是松弛的。 通常我們會將鬆弛變數引人到線性規劃方程中來，表示鬆弛或閒置的產能。未被使用的能力對利潤並無貢獻；因此在目標函式里，鬆弛變數的係數是零。在增加了4個鬆弛變數S」、S、S，和S。之後，Par 公司問題的數學模型就是： max 10S+ 9D +0S，+05+05，+0S. S.t. ⅞5+ 1D +1S」 ½S+⅝D +1S 1S+ ⅔D +1S， ¼S+¼D =630 =600 =708 +1S.=135 S, D, Si,S,S,S.≥0 如果線性規劃問題的所有約束條件都用等式來表達時，這種寫法被稱為標準型。 對於 Par 公司問題的標準型問題來說，我們發現對最優解（S=540及D.=252），鬆弛變數的值是第2章線性規劃導論 31 約束灸件鬆弛變數的值約束條件鬆弛變數的儦切制與印染 S，=0 成型 Sg =0 縫合 S：=120 檢查與包裝 SA= 18 我們可以利用圖解法來得到這方面的資訊嗎？答案是肯定的。在對圖2-5求解的過程中，我們發現，最優解受切割與印染時間及成型時間的約束。所以這個解需用上述這兩個部門的所有時間。換言之，圖形告訴我們切割與印染部門及成型部門將沒有鬆弛變數。另一方面，因為縫合及檢查與包裝沒有對最優解形成約束，所以我們就知道這兩個部門是有鬆弛或是有閒置時間的。 作為對圖解法的最後說明，我們提醒大家注意一下圖2-5裡顯示的縫合約束線。注意，這項約束並不影響可行區域的大小。也就是說，不管有沒有縫合約束，可行域的大小都是一樣的。這也告訴我們，只要其他3個部門能完成工作量，縫合部門也能完成。這是因為縫合工序並不影響最優解，它被稱為冗餘約束。 註釋與評論 1.線上性規劃問題的標準型表示方式中，鬆弛變數的係數為零，它表示鬆弛變數也就是未使用的資源並不對目標函式產生任何影響。但是在實際的問題中，公司也可以出售未使用的資源，從而使其獲利。倘若這樣，鬆弛變數就變成了表示公司可以出售多少未用資源的決策變數。這些變數前面的非零係數代表每出售1單位的對應資源，公司利潤的變化量。 2.冗餘約來並不影響可行城的大小，即使將它們刪去也不會影響最優解的值。但是，如果將線性規劃模型的資料進行改變並求解，就可能使冗餘約束轉化為有效約束。因此我們建議保留所有的約束條件，即使出現了一個或多個冗餘約束條件。 2.3 極點與最優解假設 Par公司生產的標準袋利潤從10美元降到5美元，而高階袋的利潤和所有的約束條件都不變。這個新問題的數學模型同我們在第2.1 節裡說的模型差不多完全一樣，惟一有區別的就是目標函效變成了： max SS +9D 目標函式的改變會對最優解產生什麼影響呢？如圖2-12所示，我們使用圖解法對目標函式改變後的問題進行求解。注意，這裡只要約束條件不變，可行域就不變。目標函式變化了，利潤線也就跟著變化了。 透過平移利潤線，讓它透過利潤的最大值，我們找到了如圖2-12所示的模型的最優解。圖形在這點所對應的決策變數的值是S=300且D=420。因標準袋利潤的變化導致了最優解的變化。而事實上， 正如大家可能想到的那樣，我們削減了標準袋的產量，增加了高階袋的產量。 到目前為止，在這兩個問題中，對於最優點的位置我們還發現了什麼？仔細觀察圖2-9和圖2-12， 我們注意到所有最優解的點都在可行域的頂點或“拐點”上。線上性規劃術語中，這樣的頂點稱為可行域的極點。Par 公司問題的可行域一共有5個頂點，或者說5個極點（見圖2-13）。我們可以正式表述一下如何找到最優解的點的位置： 線性規劃問題的最優解一定可以在可行區域的一個極點上找到。。 這個特點意味著我們在尋找最優解時，不必對每一個可行解進行計算。而事實上，我們只要計算可行域的極點就可以了。對Par 公司這個例子來說，我們也不需要計算所有的可行解，只需要對5個 • 我們會在本章第2.5節中討論兩種特的線性規劃問題（不存在或無窮大），在這兩種情況下，模型是沒有最優解的，因而此時該表述就不適用了。
32 資料、模型與決策：管理科學篇 600 最優解 （S = 300.D=420） 400 （300 200 9D 敏大化利潤線：5S+9D=5280 0 （540,0） 600 s 圖 2-12 200 400 標準袋產量 800 目標函式為5S+9D 時 Par公司問題的最優解 600 400 200 可行城 ① 0 200 48 600 標準袋產量圖2-13 Par 公司問題可行域的5個極點 —S 800 極點進行計算，找到其中使得利潤值最大的點即可，而這個點就是最優解的點。實際上，圖解法是求解雙變數問題的最簡單的方法。 2.4 Par 公司問題的計算機求解設計計算機程式來求解線性規劃問題已經得到廣泛的應 1952 年1月，求解線性規劃問題首次用。大多數公司和大學都曾使用過這些計算機程式。在簡單在標準東部自動計算機（SEAC）上威功實熟悉了軟體包的功能特點後，使用者就可以幾乎毫無困難地求現。SEAC，作為第一個在美國空軍贊助下第2章線性規劃導論 33 由美國國家標準局製造的數字計算機，具有512 位元組的記憶體和磁碟外部儲存器。 解線性規劃問題。現在對於有成千上萬個變數和約束條件的問題，用計算機求解就成了常規、可行的方法。對於大多數大型的線性規劃問題，計算機只需要幾分鐘便可求解出答案，如果問題比較小，求解時間通常只需要幾秒鐘。 最近，隨著個人計算機軟體爆炸式增長，也出現了許多用於求解線性規劃問題的非常友好的計算機程式。這些由科研單位和小型軟體公司開發的程式使用起來非常方便。這些程式一般都是為小型線性規劃問題（幾百個變數）設計的。其中一些也能夠解決成幹上萬個變數和約束條件的線性規劃問題。線性規劃求解工具的應用十分廣泛，很多擴充套件軟體都帶有這種工具。 管理科學家是本書作者開發的軟體包，它也有線性規劃模組。我們以 Par 公司問題為例說明怎麼使用這套軟體。因為計算機要求輸入的資料必須為小數而不是分數，所以我們將模型中的公式改寫為： maX 10S+ 9D S.t. 0.7S + 1D≤630 切割與印染 0.SS +0.833 33D≤600 縫合 1.OS +0.666 67D≤708 成型 0.1S+ 0.25D≤135 檢查與包裝 S,D≥0 看看上面係數的形式，在縫合不等式中，D的係數0.83333 是最接近5/6的5位小數。同樣，在成型的約束不等式中，我們用0.666 67 來近似地表示2/3。當遇到必須輸人約數時，我們自然會認為計算機所給出的解應該和我們手算的真實解有小量的差距。不過你會發現這兩個解之間是非常接近的，約數不會引起任何嚴重的問題。圖2-14顯示了由管理科學家軟體得到的解。 Objective Function Value = Variable S D Constraint 7667.99417 Value Reduced Costa 539.99842 0.00000 252.00110 0.00000 Slack/Surplus Dual Prices -- 1 0.00000 4.37496 2 120.00071 0.00000 3 0.00000 6.93753 4 17.99988 0.00000 OBJECTIVE COEFFICIENT RANGES Variable Lower Limit 6.30000 6.66670 Current Value 10.00000 9.00000 Upper Limit 13.49993 14.28571 RIGHT HAND SIDE RANGES Constraint 1 2 3 4 Lower Limit 495.60000 479.99929 580.00140 117.00012 Current Value 630.00000 600.00000 708.00000 135.00000 Upper Limit 682.36316 No Upper Limit 900.00000 No Upper Limit 用2~14 Par 公司問題用管理科學取軟體得到的解注：由於本書所附光碟中攜帶的軟體使用的是英文版，故書中的這種圖表也採用英文版。 譯者注
34 資料、模型與決策：管理科學篇計算機輸出結果的解釋下面我們仔細看看圖2-14顯示的計算機輸出結果。首先，注意目標函式值右邊的值7667.99417。 將它四舍五人求近似值，我們就得到最優解相對應的利潤7668美元。在目標函式值的下面我們發現了最優解所對應的決策變數的值。進行同樣的近似變換後，我們就得到：標準袋產量S=540，高階袋產量為D=252。 減少的成本下的資訊表示在目標函式中，決策變數的係數需改進°多少才能使最優解對應的決策變數的值是正值。如果決策變數在最優解的條件下已經是正值了，減少的成本就應該是零。如在 Par 公司問題中，最優解是S=540和D=252。兩個變數已經是正值，所以它們相對應的減少的成本是答。 在第3章我們還會介紹最優解的決策變數不是正值的情況。 緊接著S、D值以及減少的成本資訊之後，計算機還給出了一些約束條件的資訊。回想一下 Par公司問題，它有4個關於時間的小於等於的約束條件，每個條件對應一個部門。這些資訊表示在鬆弛/ 剩餘下面。四捨五入後的資訊小結如下： 約東條件號碼約束條件名稱鬆弛約束條件號碼約束條件名稱切削與印染 0 3 成型 2 縫合 120 4 檢查與包裝鬆弛 0 18 從這些資訊裡我們發現，有效約束（切割與印染及成型約束）在最優解時的鬆弛是零。縫合部門有 120小時的鬆弛，或稱為未使用產能，檢查與包裝部門有18 小時的鬆弛。 圖2-14的下面其餘的資訊是有關目標函式的係數或約束條件右端值變化時對最優解的影響。有關這部分內容我們會在第3章的靈敏度分析專題中加以詳細討論。 註釋與評論線性規劃求解工具有著大多數擴充套件軟體包的標準特徵。Excel、Lotusl-2-3 和 Quattro Pro 都有解決最最佳化問題的能力，其中就有線性規劃。這些求解工具都是由 Frontline 系統製作的，介面簡單友好。 2.5 一個簡單的最小化問題 M&D 化學公司生產兩種產品，它們是生產肥皂和清洗劑的原材料。基於對當前存貨水平和下月的市場需求的分析，M&D 管理層確定A 和B 的總產量至少要達到350加侖。特別地，公司的一個主要客戶訂購的125加侖必須首先得到滿足。A產品的製造時間是每加侖2小時，而B產品則是每加侖 1小時。下個月總加工時間是600小時。M&D的目標是在滿足客戶需求的前提之下儘可能降低成本。 每加侖A產品的製造成本是2美元，而每加侖B產品的製造成本是3美元。 為了制定出使得成本達到最小的生產計劃，我們列出M&D公司的線性規劃方程。同我們前面提到的第一個例子相類似，我們首先定義出該問題的目標函式和決策變數。假設： A—A 產品產量； B—B產品產量。 因為A產品的成本是每加侖2美元，B產品的成本是每加侖3美元，那麼使成本最小化的目標函數就可寫成： min 2A +3B 接下來我們看看 M&D的約束條件。因為公司必須首先滿足主要客戶的125加侖產品，所以A必 ◎對於最大化問題來說，改進意味著變大；而對最小化問題，改進則意味著變小。
第2章線性規劃導論 35 須至少是125加侖。因此，我們可以將約束條件寫成： • 1A≥125 又因為兩種產品的總產量必須至少是350加侖，我們得到： 1A +1B≥350 最後，我們還知道公司最大可用加工時間是600 小時，因此再增加一個約束條件： 2A +1B≤600 增加非負約束條件（A，B≥0）之後，我們就得到 M&D公司問題的線性規劃方程： min 24 +3B s.t. 1A ≥125 A 產品的需求量 1A+1B≥350 總產量 24 +1B≤600 生產時間 A,B≥0 這個線性規劃模型只有兩個決策 B 變數，所以我們可以用圖解法來求解 600 最優產量。求解該題的方法同求解 Par 公司問題時相同。首先畫出約束圖， 500 生產時間 A= 125 找到可行區域。透過先分別畫出各約束直線，檢驗一下約束直線兩邊的點， 則每個約束條件的可行解就確定下來 400 了。再把每個約束條件的可行域都結量合起來，我們就得到了整個問題的可 300 行域，如圖2-15所示。 ［1A+1B=350 為了找到使成本最小化的解，我們現在畫出基於某一特定的總成本值 200 24+1B =600 的目標函式線。比如，我們可以先畫出2A+38=1200這條線，見圖2-16。 100 很明顯，可行域裡的某些點可以提供 1200美元的總成本。為了找到能使總成本較小的A和B的值，我們將直線 0 100 200 300 400 500 600 向左下方移動，但不可以太大，因為 A產品產量只要稍微移動一點，整條線就會全部圖 2-15 M&D 化學公司問題的可行域落在可行域的外面。注意，透過極點A =250 和B=100 的目標函效線是24+3B=800。透過圖2-15和圖2-16我們可以看出，總生產能力約束和總生產時間約束是有效約束。同其他每個線性規劃問題一樣，該問題的最優解也在可行域的極點處。 2.5.1 圖解法求解最小化問題的主要過程小結圖解法求解最小化問題的主要過程總結如下： 1.畫出每個約束條件的可行解。 2. 確定滿足所有約束條件的可行域。 3.畫出目標函式線，使不同的目標函式值對應不同的決策變數值。 4.平移目標函式線，直至繼續移動會使得直線完全處於可行域之外，以確保目標函式值最小。 5.目標函式線上具有最小值的可行解即為問題的最優解。
36 資料、模型與決策：管理科學篇 2.5.2 剩餘變數 M&D 化學公司問題的最優解說明瞭透過使用所有的2A +1B=2x B 600250+1 ×100 =600 小時，我們可以達到A+B =350 的生產量。另外， 500 注意，A產品的產量已經達到其最低要求，A=250 加侖。實際上我們已經超過了 A產品的最小要求 250400 125=125加侖。多生產出來的這部分產品就稱為剩餘。 回憶一下，對於一個 a≤約束條產品產量 300 件的問題，我們可以將鬆弛變數加到不等式的左邊，使其變成一個等 200式。同樣，對於一個a≥約束條件的問題，我們可以在不等式的左邊減 100一 24+38=1200 去一個剩餘變數而使不等式變成等式。同鬆弛變數一樣，在目標函式中多個變數的值也是零，它們對目 0 最優解 （A = 250.8 = 100） 100 24+38=800 200 標函式的值並沒有影響。在包括兩 400 個≥約束條件的剩餘變數S，和S，以及一個≤約束條件問題的鬆弛變數 300 A產品產量圖 2-16 求解 M&D化學公司的團解方法 S，後，M&D 化學公司問題的線性規劃模型就變為： min 24 +3B +0S， +0S+05 S.t. 500 600 1A -15， = 125 IA+1B -18 = 350 2A+1B + 1S，=600 A，B,S.，S,S，≥0 現在所有的約束條件都是等式了。以上形式就稱為M&D化學公司問題的標準形式。問題的最優解是A =250，B=100，鬆弛變數和剩餘變數的值如下： 約東條件剩餘變數和鬆弛變數的傭 A 產品的需求 S，=125 總產量 S：=0 生產時間 Ss=0 觀察圖2-15 和圖2-16，我們發現有效約束條件的鬆弛變數或剩餘變數的值都為零時，總產量和生產時間約束條件達到最優解。而A 產品需求的非有效性約束條件相對應的剩餘變數值為125加侖。 在Par公司問題裡，所有的約束條件都是≤型別的，而M&D公司的問題中，約束條件既有≥型的，也有≤型。特定線性規劃問題所面臨的約束條件的型別和數量取決於問題中存在的特定條件。很可能出現的情況是一個問題中既有≥型的，也有≤型，還有=型的約束條件。對於等式約束來說，可行解必在約束直線上。 下面這個例子是也是個雙決策變數問題，決策變數是G和H，包含3種形式的約束條件： min 2G+2H
第2章線性規劃導論 37 8.t. 1G+3H≤12 3G+1H≥13 1G-1H=3 G,H≥0 其標準型為： min 2G +2H +0S， +0S2 s.t. IG+3H+1S、 3G+1H 1G-1H =12 -15，=13 =3 G,H,S.，S.≥0 在標準型中，≤形式的約束條件對應的是鬆弛變數，≥形式的約束條件對應的是剩餘變數。而=形式的約束條件則不存在這些變數，因為它本身就是等式。 如果用圖解法求解線性規劃問題，則沒有必要寫出問題的標準型。然而我們應該可以計算鬆弛變量和剩餘變數的值，並且理解它們的含義，因為這些值的計算也包括在計算機求解過程中。在第5章我們會向大家介紹解決線性規劃問題的代數方法—單純形法。用這種方法我們可以解決變數數成幹上萬的線性規劃問題。在使用單純形法解決問題的步驟中，必須對多個等式型的約束條件進行求解。 因此，如果我們希望使用單純形法求解，就必須要將約束條件用線性等式表示出來，這時我們就需要用到標準型了。 最後一點是，線性規劃問題的標準型其實是與原始形式等價的。也就是說，一個線性規劃問題的最優解與其標準型的最優解的值應該是一樣的。一個問題的標準型並不改變問題的本質，它只是改變我們對問題中約束條件的表示方法。 2.5.3 M&D 問題的計算機求解用管理科學家軟體求解 M&D問題的結果如圖2-17所示。透過計算機結果我們可以看到，目標函 Objective Function Value = Variable 800.000 Value Reduced Coats A B Constraint 250.000 0.000 100.000 0.000 Slack/SurPlus Dual Prices 1 2 125.000 0.000 0.000 -4.000 3 0.000 1.000 OBJECTIVE COEFFICI EIYT RANGES Variable Lower Limit Current Value A日 No Lower Limit 2.000 Upper Limit 3.000 No Upper Limit RIGHT HAND SIDE RANGES Constraint Lower Limit 1 No Lower Limit 300.000 475.000 Current Value 125.000 350.000 600.000 Upper Limit 250.000 475.000 700.000 圖2-17 用普理科學來求解 M&D問題
38 資料、模型與決策：管理科學篇數的值，即使得成本最小化的值是800美元。決策變數值表明在生產成本最低時，A產品的產量是 250加侖，B產品的產量是100加侖。 鬆弛/剩餘變數欄顯示，對應於A產品的需求的一個≥型的約束條件有125加侖的剩餘。這一欄說明，當函式的解是最優解時，A產品的產量比它的需求多125加侖。總生產需求（第二個約束條件）和處理時間約束（第三個約束條件）的鬆弛/剩餘的值是零，表明這兩個約束在最優解中是有約束力的。我們會在第3章的靈敏度分析中對圖2-17的其他部分進行分析。 2.6 特例這一部分中我們會討論三種在求解線性規劃問題中可能遇到的特殊情況。 2.6.1 多重最優解從對圖解法的討論，我們知道最優解可以從可行域的極點中找到。現在考慮一下特的情況，目標函式線與可行域邊界所在的約束線重合。我們會看到這會導致有多重最優解。在此情況下，函式的最優解將多於一個。 為了解釋多重最優解，我們再回到Par 公司的例子上去。我們假設生產每個標準袋的利潤減為 6.30美元，因而目標函式的值就變成了6.3S+9D。這時再用圖解法求解該問題，如圖2-18所示。注意，最優解雖然還在極點上，但實際上，兩個極點都是最優點：極點④（S=300，D=420）和極點③ （S =540，D=252）。 600） （300,420） 400 200 639+92=2780 （540,252 6.3S+9D=5670 2 一S 0 200 400 標準袋產量 600 800 圈 2-18 目標函式為 6. 3S+9D（多重最優解）的Par 公司問題這兩個極點的目標函式值可以寫成： 6. 3S+9D=6.3 x300+9 x420 =5 670 以及 6.3S +9D=6.3 ×540+9 x252 =：5 670 此外，這兩個最優解的點之間的任何點也都是最優解。例如，點（S =420，D=336）在兩個極點中間，它也使得目標函式的值最大。
第2 章線性規劃導論 39 6. 3S+9D=6.3x420+9×336 =5 670 具有多重最優解的線性規劃問題對經理人或是決策者來說一般是好事。這意味著可以有很多決策變數組合供選擇，決策者可以選擇一個最理想的。不幸的是，決定一個問題是否有多重最優解並不是件容易的事。 2.6.2 無可行解無可行解是指線性規劃問題不存在滿足全部約束條件（包括非負約束）的解。在圖形中，無可行解是指可行域並不存在。也就是說，沒有任何一個點可以同時滿足所有的約束條件以及非負約束。為了進一步解釋，我們再回到 Par 公司的例子上來。 假設管理層確定公司必須至少生產500個標準袋和360個高階袋。在圖形中就必須重新畫出問題的解的區域以反映兩個新增的要求（見圖2-19），左下方的陰影區域表示滿足生產能力的解，右上方的陰影區域表示的是標準袋的最低生產量是500個，高階袋的最低生產量是360個。但是沒有任何一個點能夠滿足這兩個約束條件。因此，如果管理層增加這兩個最小產量約束條件，該問題就沒有可行域了。 600 滿足最低生產要求的點 min S 400 滿足部門約束條件的點 200 0 200 400 標準袋產量 600 800 圖2-19 無可行域的最低生產需求為500個標準袋和360個高階袋的 Par 公司問題我們如何說明這個問題的不可行性呢？首先，在已有資源的基礎上（如切割與印染、縫合、成型以及檢查與包裝的時間），我們無法生產出500個標準袋和360個高階袋。此外，我們也可以準確地告訴管理層要生產500個標準袋和360個高階袋還需要多少資源。表2-2列出了完成任務所需要的最少資源、現有資源和還需要增加的資源。現在我們知道要想完成管理層的任務，至少還要增加80小時的切割與印染時間、32小時的成型時間以及S小時的檢查與包裝時間。 表2-2 生產500個標準袋和360 個高階袋所需資源操作切割與印染縫合成型檢查與包裝最少資源要求（小時） 可用資源 7/10 x500 +1 ×360=710 630 1/2×500+5/6 ×360 =550 600 1 x500+2/3 ×360 =740 708 1/10×500+1/4 x360 = 140 135 還需墻加的資源（小時） 80 無 32 5
40 資料、模型與決策：管理科學篇如果看完表2-2後，管理層還是希望生產500個標準袋和360個高階袋，那就得增加資源了。 可以透過僱用其他人到切割與印染部門工作、抽調廠裡面其他地方的人來成型部門做兼職或讓縫合部的人定期到檢查與包裝部門來工作。這樣的話，所需的資源就可滿足。正如你所看到的那樣，一且我們發現問題缺少可行解，便可以採取很多方法來改正管理層的行為。重要的是我們要知道，運用線性規劃分析可以確定出管理層的計劃是否可行。我們可以發現不可行的情況，並開始改正我們的行為。 如果用管理科學家軟體來解無可行解的問題，你會得到 “No Feasible Solution（無可行解）”的信息。這時你便知道不存在同時滿足所有規定的約束條件以及非負約束條件的解。仔細檢查一下所列的方程，找出問題無可行解的原因。一般來說，在這種情況下，最好的辦法是去掉一個或多個約束條件。如果修改過的方程存在最優解，你就知道了是哪些約束條件使得問題無可行解了。 2.6.3 無界解如果一個最大化線性規劃問題的解可以無限地變大，卻不違反任何約束條件，我們就稱這個解是無界解。對於一個最小化問題，如果它的解可以無限地變小，那麼它的解也是無界的。這種條件被稱為管理烏托邦。例如，如果是利潤最大化問題遇到這種條件，那麼管理者可能獲得無盡的利潤。 但是，如果一個實際的線性規劃模型中出現了無界解的情況，那就說明問題所對應的方程出現了問題。我們知道對於一個現實問題來說，不可能會出現利潤無限大的情況。所以我們得出以下結論： 如果對於一個求利潤最大的問題的方程具有無界解，那麼這個數學模型就一定沒有真實反映實際問題。產生這種情況的原因常常是在對模型列表示式時，遺漏了一些約束條件。 我們透過下面這個例子來說明這種情況。假設下面的線性規劃問題只有兩個變數X和Y。 20 15 10 目標兩數無限大可行域— IS m 20X + I0Y=80 10 20X+10Y=160 20X 2-20 無界問題例項 20
第2童線性規劃導論 41 max 20X +10Y S.t. IX ≥2 IY≤S X,Y≥0 在圖2-20中我們畫出了這個問題的可行域。注意，我們只是畫出了部分的可行域，因為可行域是向X軸正方向無限延伸的。看一下圖2-20中的目標函式線，我們發現這個問題的解可以是無限大的。 也就是說，無論我們將解定為多大，我們總是能夠在可行域裡找到更大值的可行解。因而我們說，該線性規劃的解是無界的。 用管理科學家軟體解無界問題時，我們會得到一條資訊：“Problem is Unbounded（問題無界）”。 因為現實世界問題是不可能出現無界的情況的，所以如果發生這種情況，一定要先檢查一下所列函效模型裡的方程是否正確。一般而言，出現這種情況很可能是列方程時遺漏了約束條件。 註釋與評論 1.無可行解同目標函式本身無關。它的出現是因為約東條件太苛刻，無法得到線性規劃問題的可行城。因而在遇到不可行問題時，去改變目標函式是沒有意義的。就算改了，問題依然無可行解。 2. 產生無界解的原因通常是遺漏了約束條件。但是改變目標函式可能會使一個無界問題變成一個有界問題。例如在圖2-20中，對目標函式最大化20X+10Y來說具有無界解，而對最大化-20X-10Y 來說，該問題就有最優解（X=2，Y=0）了，而我們並未改變約來條件。 2.7 線性規劃的通用符號本章我們已經介紹瞭如何對 Par 公司和 M&D 化學公司問題進行線性規劃建模。對 Par公司問題進行線性規劃建模，我們先定義了兩個變數：S—標準袋產量，D—高階袋產量。在M&D 化學公司問題中，我們也定義了兩個變數：A-A產品產量，B—B產品產量。我們選擇S、D作為Par公司問題的決策變數，並選擇A、B作為 M&D 化學公司問題的決策變數，目的是使我們能夠透過決策變量的名字聯想起它所代表的含義。這種方法對於規模較小的問題來說比較方便，但是問題中如果包含大量的決策變數，採用這種方法就會遇到困難了。 線上性規劃問題中更加通用的符號是帶有下標的x。例如，在Par公司例子中，我們可以將決策變數定義為： *，—標準袋產量； *，—一高階袋產量。 而在M&D公司的問題裡，我們也可以使用相同的變數名，當然它們被定義為不同的內容。 *—A產品產量； *—B產品產量。 在使用這種變數命名方法時，我們可能會忘記變數在數學模型中所代表的含義。如果模型中包含大量的決策變數，使用這種方法命名會相對比較容易。例如，對於一個包含3個變數的線性規劃問題，我們可以將變數命名為4、*和*，而對於一個有4個變數的問題來說，我們可將變數命名為%」、2、 X；和x，依此類推。 下面我們舉個例子說明如何使用通用符號來對線性規劃問題進行求解。設下面這個最大化的數學模型中包含兩個變數。
42 資料、模型與決策：管理科學篇 max 3x， + 282 s.t. 2x+ 2x2≤8 1x， +0.5x≤3，龍≥0 首先，我們將可行解（x，和x，的值）圖示出來，採用的方法一般是將x，作為橫座標，將x，作為縱座標。圖2-21顯示了這個雙變數問題的圖解。注意，該問題的最優解是x，=2，*2=2，對應的目標函式值是10 用通用線性規劃符號，我們可寫出該線性規劃問題的標準型，如下： max 3x， +2%+08，+052 X2 s.t. 2%+ 2%+13 Ix，+0.5x+ =18 1sz =3 9 因而最優解是x，=2，*2=2，鬆弛變數是S，=S=0。 本章小結約東條件2 我們對如下兩個線性規劃問題進行了建模：Par 公司的最大化問題和 M&D 化學公司的最小化問題。對這兩個問題，我們約束條件L 都採用了圖解法和應用管理科學家軟體來求解最優解。在對這些問題進行數學建模戢優解 X1=2,X2=2 最優值 =3x1+ 2x2=10 2 的過程中，我們給出了線性規劃模型的一般定義。 3xi + 2x2=6 線性規劃模型是具有如下特點的數學模型： 1. 求解最大化或是最小化的線性目標函式； 一X 0 1 3 5 2. 存線上性約束集合； 3. 滿足非負約束的決策變數。 鬆弛變數被用來將小於等於形式的約圖2-21 圖解法求解用通用符號表示的雙變最線性規劃問題束條件轉變為等於形式的約束條件。剩餘變數被用來將大於等於形式的約束條件轉變為等於形式的約束條件。鬆弛變數就是未使用的資源，而剩餘變數則是超過某一最低需求的量。當所有的約束條件都寫成了等式形式，就被稱為線性規劃問題的標準型。 如果一個線性規劃問題的解是不可行的或是無界的，那這個問題就沒有最優解。對於無可行解的情況，模型無法找到同時滿足所有約束條件的解；而對於模型的解是無界的情況，若問題為最大化問題，則目標函式可以無限地擴大；若是最小化問題，則目標函式可以無限地縮小。對多重最優解的情況，存在兩個或多個最優極點，且連線上所有的點也是最優解。 本章還介紹瞭如何使用通用的線性規劃符號。在專欄2-2中，我們介紹如何運用線性規劃進行交通控制， 這是線性規劃在實際應用的一個小例子。在本書第3章和第4章裡，我們還會看到更多的線性規劃應用的例子。 專欄22 實踐中的管理科學運用線性規劃進行交通控制漢神高速公路是日本大阪市的第一條城市收費高速公路。儘管1964年它的長度還只有2.3公里，
第2章線性規劃導論 43 但現在該高速公路網路已經覆蓋了200 多公里。漢神高速公路主要為漢神（大坂一神戶）地區提供交通服務，這是全日本第二繁華的地區。漢神高速公路的日均車流量是828 000輛，有時一天的流量就超過100萬輛。1990年漢神高速公路公共公司開始使用交通自動控制系統，以使得高速公路網路的流量達到最大。 交通自動控制系統主要依靠兩種方法：（I）限制高速公路入口處的進車數量；（2）給司機提供最新、最準確的交通訊息。這些資訊包括車流量和交通事故的報道。對汽車數量進行限制主要基於兩個方面：一是高速公路的運轉是否正常平穩，二是有沒有非正常事件發生，比如交通事故或汽車拋錨等。 在第一個階段，穩定狀態情況下，公司使用線性規劃模型求出在不產生交通擁塞且不對周邊公路網路產生負面影響的情況下，駛入高速公路的最大汽車數量。執行線性規劃模型的資料是由高速公路上每500米安裝一個以及在進出口都安裝有的探測器裡得到的。每5分鐘，從探測器收集到的實時數據用於更新模型的係數，這時新的線性規劃模型就便計算出高速公路能夠容納的最大的汽車數量。 這個交通自動控制系統已經執行成功。根據相關調查，透過使用該系統，高速公路上的擁塞由原來的30%降到20%。它已經被證明是個非常節約成本的，並被認為是必不可少的系統。 資料來源：T. Yoshino, T. Sasaki, and T. Hasegawa， "The Traffic-Control System on the Hanshin Expressway，" Interfaces （January/February 1995）：94-108. 專業術語 constraint 約東條件使得決策變數組合成為可行解的等式或不等式規則。 problem formulation 建模將口頭問題用數學語言表達出來（稱為數學模型）的過。 decision variable 決策變數線性規劃模型中的可控性輸人。 nonnegativity constraints 非負約東要求所有變數都為非負數的約束。 mathematical model 數學模型將目標和所有的約束條件都用數學語言描述出來的表達形式。 linear programming model 線性規劃模型具有線性目標函式、線性約束集合以及非負變數的數學模型。 linear program 線性規劃線性規劃模型的另一種說法。 linear functions 線性函式：變數單獨存在，且最高冪次為1的數學表示式。 feasible solution 可行解滿足所有約束條件的解。 feasible region 可行城所有可行解的集合。 Slack variable 鬆弛變數加到小於等於形式的約束條件的左邊，使其成為等式的變數。這個變數的值可看成是未使用資源的數量。 standard form 標準型所有約束都寫成等式的形式的線性規劃問題。標準型的最優解同原問題的最優解是一樣的。 redundant constraint 冗餘約束不影響可行域大小的約束。刪除冗餘約束不會影響問題的可行域。 exTeme pomt被點從圖上來說板點是可行域的頂點或“拐點”所對應的可行解點，對於雙變數問題，極點可由約束線的交點來確定。 surplus variable 剩餘變數在左邊減去這種變數，使得大於等於型的不等式變成等式形式。這種變數被解釋為多於某一最低要求的量。 alternative optimal solutions 多重最優解至少有兩個解使得目標函式的值達到最優的情況。 infeasibility 無可行解沒有滿足全部約束條件的解。 unbounded 無界在最大化問題中，解的值可以無限擴大，在最小化問題，解的值可以無限縮小，而沒有任何約束，這種問題就稱為是無界的。 問題 2. 找出滿足下列條件的可行解點： a.4%+28≤16 b.4x+2%≥16 C. 4x，+2%=16 4.分別作圖畫出下列約束的約束線和可行解： 8. 3%1-4%≥60 b. -6x：+5%，≤60 C. 5x，-24≤0
44 資料、模型與決策：管理科學篇 6.確定目標函式如下所示的三個線性規劃問題的斜率：7x，+10x，6x，+4x，和-4x，+7x。畫出目標函式值為 420時的圖形。 8.確定下面約束集合的可行域： 24- 1x≤0 -1x，+1.5x ≤200， ≥0 10. 對如下所示的線性規劃問題： max 2x， +3x s. t. 1x，+2x≤6 Sx，+3x≤15 *，%≥0 運用圖解法求出模型的最優解，並確定最優解處的目標函式值。 12. 考慮如下所示的線性規劃模型： max 3x，+3x 8.t. 2x1 +4x≤12 6x，+4%≤24 B.用圖解法求出最優解。 b.如果目標函式變為2x，+6x，求最優解。 e. 本題有多少個極點？在每個極點裡，*，*的值是多少？ 14. 考慮如下所示的線性規劃模型： max 1x，+28 s.t. 1x ≤S 1x，≤4 2x+2%=12 a.畫出可行城。 b. 可行域的極點是什麼？ c•用圖解法求最優解。 16.在圖2-13中參見 Par 公司問題的可行域。 8.建立一個目標函式，使得極點⑤是最優解。 b. a 中確定的目標函式對應的最優解是多少？ c.這個解所對應的鬆弛變數的值是多少？ 18. 對於如下所示的線性規劃問題： max 4x+1x 8. t. 10%，+24≤30 3%+24≤12 2%+24≤10 *，½≥0 日，寫出該線性規劃問題的標準型。 b•用圖解法求最優解。 c.3個鬆弛變數的值是多少？
第2章線性規劃導論 45 20. 大使摩托車公司（EM）為丫滿足客戶安全和便捷等方面的需要，準備生產兩種輕型摩托車。EZ 騎士型配制了新引擎，底盤較低，易掌握平衡。而運動女士型稍微大一點，使用了傳統的引擎，它的獨特設計適合女性.使用。大使摩托車公司在愛荷華州的 Des Moines 工廠生產這兩種型號的摩托車引擎。生產每個 EZ騎 t：引擎需要6小時，而生產每個運動女士型引擎需要3小時。Des Moines 工廠在下一個生產期間的總生產時間是2100小時。大使摩托車公司的摩托外殼供應商可以保證EZ 騎士型摩托車的任何數量的需要。而對於較複雜的運動女上型外殼，供應商在下一個生產期間只能提供280件。最後，對於組裝和檢測，EZ騎士型需要2小時，運動女士型需要2.5小時。在下一個生產期間內總共有1000小時的組裝和檢測時間可用。 公司的會計部門預測，每輛EZ.騎士型的利潤貢獻是2400美元，而每輛運動女士型的利潤貢獻是1800美元。 a.列出線性規劃模型，確定每種型號的摩托車應該生產多少才能使公司的總利潤最大。 b.用圖解法找到最優解。 c•哪個約束條件是有效約束？ 22. Kelson 運動器材公司製作兩種棒球手套：普通型和捕手型。公司的切割與印染部門有900小時的可工作時間，成型部門有300 小時的可工作時間，包裝和發貨部門有100小時的可工作時間。每雙手套的生產時間和利潤貢獻要求如下： 型號切劓與縫合普通型捕手型 3/2 生產時間（小時） 鹹型 1/2 1⅓3 包裝和發貨 1/8 1/4 每雙手套的利潤貢獻（美元） s 8 假設公司希望實現總利潤貢獻最大，回答以下問題： a. 本題的線性規劃模型是什麼？ b•用圖解法找到最優解。此時每種手套各應該生產多少雙？ c.在最優解時公司獲得的總利潤貢獻是多少？ d. 每個部門應該安排多少小時的生產時間？ e.每個部門的鬆弛時間是多少？ 24.海港飯店每月的廣告預算是1000美元，現在飯店希望確定在報紙上和廣播上各應該花多少廣告費。管理層已經確定，兩種媒體的廣告費用都至少要佔總預算的25%，而且花在報紙上的錢至少是廣播的兩倍。市場顧阿已經建立起一個用來衡量廣告影響力的指數，1~100，值越高，表示媒體的影響力越大。如果本地報紙的影響力指數是50，而廣播的影響力指數是80。飯店應該如何分配預算才能使總影響力指數的值最大。 a.列出線性規劃模型，確定飯店應該如何分配預算才能使總影響力的數值最大。 b.用圖解法找出模型的最優解。 26. 湯姆公司向位於堪薩斯州和新墨西哥州的西部食品連鎖店提供墨西哥食品。湯姆公司生產兩種 Salsa 食品， 西部食品 Salsa 和墨西哥城 Salsa。需要特別指出的是，這兩種產品在番茄的配料方面有所不同。西部食品 Salsa 中含50%的生番茄，30%的番茄醬，20%的番茄糊；而墨西哥城 Salsa 中含70%的生番茄，10%的番茄醬，20%的番茄糊。每瓶 Salsa 重10盎司。現階段，湯姆公司可以買到280磅生番茄、130磅番茄醬和 100磅番茄糊。它們的單位價格分別是0.96美元、0.64美元和0.56 美元。其他香料和配料的價格大約合每瓶0.10美元。湯姆公司所購空瓶的價格是每瓶0.02美元。貼標籤和裝瓶的成本是每瓶0.03美元。湯姆公司與西部食品店簽訂的合約是，每提供1瓶西部食品 Salsa，給湯姆公司獲得1.64 美元，每提供1瓶墨西哥城 Salsa，獲得1.93美元。 8.建模，使湯姆公司透過模型能夠確定每種產品各生產多少時，總利潤貢獻會最大。 b，求最優解。 28. 戴海（Dichl）投資公司的財務顧問得知有兩家公司很可能在近期有併購計劃。西部電纜公司是製造建築光纜方面的優秀公司，而康木交換公司是一家數字交換系統方面的新公司。西部電纜公司股票的現在每股交易價是40美元，而康木交換公司的每股交易價是25美元。如果併購發生了，財務顧問預測西部電纜公司每股價格將上漲到55 美元，康木交換公司每股價格將上漲到43美元。財務顧問確認投資康木交換的風險比較高。假設投資在這兩種股票上的資金的最大值是50 000 美元，財務顧同希望至少在西都電續公司上投
46 資料、模型與決策：管理科學篇資15000美元，至少在康木交換公司投資10000美元。又因為康木交換公司的風險比較高，所以財務顧問建議對康木交換公司的最大投資不能超過25 000 美元。 a.建立線性規劃模型，決定對西部電纜公司和康木交換公司各應該投資多少才能使總投資回報率最大。 b.畫出可行域。 c.確定每個極點的座標。 d.找出量優解。 30.確定 M&D公司問題（見第2.5節）的極點解。確定在每個極點處的目標函式值及鬆弛變數值、冗餘變數值各是多少。 32. 考思如下線性規劃問題： min 2x， +2x S. t. 1x+3%≤12 3x，+1x≥13 1x」-1x=3，4≥0 a. 畫出可行域。 b.可行域的極點是什麼？ c•用圖解法求最優解。 34. 為了改善產品的質量，鞏固電子公司僱員接受了兩項培訓計劃，一項是為期3天的基於團隊方面的，一項是為期2天的基於問題解決方面的。質量改進部門的經理要求他們在6個月內至少要接受8種團隊培訓和 10種問題解決培訓。此外，鞏固電子公司的高管還指定，這一時期必須至少提供25種培訓內容。公司聘請了諮詢人員指導培訓。在接下來的6個月裡，諮詢人員總共有84個可工作日。每項基於團隊方面的培訓計劃的成本是10000美元，每項基於問題解決方面的培訓計劃的成本是8000美元。 日.建立線性規劃模型，確定兩項培訓計劃各應該安排多少才能使成本最低。 b. 畫出可行域。 c.確定每個極點的函式座標。 d. 求出最小成本的解。 36.應用技術公司（ATI）生產腳踏車的框架。為了改進框架的抗壓率，公司需要使用兩種玻纖材料。標準級的材料成本是每碼7.50美元，而專業級的材料成本是每碼9美元。標準級和專業級包含不同的玻纖維、碳纖維以及凱夫拉爾纖維含量，見下表： 材料標準級專業級玻纖 84% 58% 碳纖維 10% 30% 凱夫拉爾纖維 6% 12% ATI 同一案腳踏車生產商簽訂了一份生產一種新框架的合同，這種框架的碳纖維含量至少要達20%，而凱夫拉爾纖維的含量不得超過10%。為了滿足特定重量的要求，每個框架一共必須用到30碼的材料。 a.為ATI公司建立線性規劃模型，計算為了使成本最小化，ATI 用在每個框架上的各種級別的材料數量是多少碼。定義決策變數並指明每個約束條件的目的。 b. 用圖解法找出可行域。各極點的座標是什麼？ c.計算每個極點上的總成本，最優解是什麼？ d.玻纖材料的分銷商存有過量的專業級材料。為了降低成本，分銷商答應 ATI 可以按每碼8美元的價格購買專業級材料。這種情況下最優解是否有變化？ e.假設分銷商進一步降低專業級材料的價格至每碼7.40美元。最優解會變化嗎？一個甚至更低的專業材料價格會對最優解有什麼影響？解釋原因。 38. 圖片化學制品公司生產兩種洗相液。這兩種產品的成本都是每加侖1美元。在基於現有的存貨水平以及下個月上游未滿足訂貨單的基礎上，管理層認為，下兩週必須至少生產出30加侖產品1 和20加侖產品2。
第2童線性規劃導論 47 管理層同時指出，因為有一種用來生產兩種洗相液的生產原料極易腐爛，所以現存的80磅這種原材料必須在下兩週內用完。如果生產時還需要更多的此原料，可以隨時訂，但如果現存的用不完就會腐爛掉。因此，管理層指示下兩週必須至少要用去80磅這種原材料。此外，我們還知道製造1加侖產品1需要這種易腐爛的原材料1磅，而產品2需要2磅。現在圖片化學制品公司的目標是儘可能降低生產成本，所以管理層希望制定一項計劃，在滿足用光全部的80磅易腐爛的原料以及至少生產出30加侖產品1和20加侖產品 2 的前提下，使生產成本最小。這個最小的生產成本是多少？ 40.以下線性規劃問題無可行解、有無界解或多重解的情況嗎？請解釋。 max 4x，+8x2 S. t. 2%+2x≤10 -1x， +1x≥8 X，X≥0 42. 考慮以下線性規劃問題： max S. t. 1x：+1x 5x，+3x≤15 3x，+5% ≤15 X，4≥0 日，找出量優解。 b.當目標方程為1x，+2x時的最優解。 c•透過調整x，的係數來構造一個新的目標函式，使（a）、（b）中的解均為更改目標函式後的最優解。 44.一家小型商店的老闆希望找到最好的安排飲料貨架的方法。商店售賣兩種型別的飲料，有全國性商標的或是沒有商標的。現在貨架共有200平方英尺的可用面積。老闆決定貨架中至少60%是有商標的飲料，而不論盈利與否都至少拿出10%給無商標飲料。在考慮到以下前提下，老闆應該如何分配貨架空同呢？ a.有商標的飲料比沒有商標的飲料利潤大。、 b.兩種飲料利潤相同。 c.無商標飲料利潤比有商標飲料利潤大。 46.對於M&D公司的問題（見第2.5節），如果管理層要求兩種產品的總產量最小是500加侖，會產生什麼影啊？列出兩三種你認為M&D公司應該採取的行動。 48. 考忠本部分第21題（見光碟）RMC 化學公司的情況。假設管理層提出了新的要求，即至少生產出30噸燃料新增劑和15噸基礎溶劑。 8.畫出改變決策後問題的約束條件。可行域將會有什麼變化？解釋原因。 b.如果無可行解，指出如果要生產30噸燃料新增劑和15噸基礎溶劑，還需要什麼？ 50. 遠征服裝公司為遠足、滑冰和登山愛好者製作很多種類的運動服。公司現在要為極冷的環境設計兩種皮風衣，名字已經選好了，分別叫珠穆朗瑪峰風衣和洛磯山風衣。公司可以用來製作這兩種風衣的生產時間分別是，切割120小時，縫合120小時。每件珠穆朗瑪峰風衣需要30分鐘切割，45分鐘縫合。每件洛磯山風衣需要20分鐘切割，15分鐘縫合。人工和原材料成本方面，每件珠穆朗瑪峰風衣需要150美元，每件洛磯山風衣要50美元，透過公司的郵購目錄，我們知道每件珠穆朗瑪峰風衣賣250美元，每件洛磯山風衣賣200美元。因為管理層認為，珠穆朗瑪峰風衣代表了公司的形象，所以至少要佔總產品的20%。假設公司可以將它們所生產的全部產品都賣出去，則每種產品各應生產多少才能使公司總利潤最大？ 52. 開創運動設計公司製造一種標準型網球拍和一種加長型網球拍。由於使用了公司創立者開發的鎂碳合金材料，公司的球拍極輕。每個標準型球拍使用0.125千克這種合金，每個加長型球拍使用0.4千克這種合金。在接下來的兩週，公司只有80千克這種合金可用。標準球拍的製造時間是10分鐘，加長球拍的製造時間是12分鐘。每個標準球拍的利潤是10美元，每個加長球拍的利潤是15美元，每週的生產時間是40 小時。管理層要求至少總產量的20%是標準型。那麼公司每種球拍應該生產多少才能保證總利潤最大？假設由於公司的產品是獨特的，因而所有生產出來的產品都能賣出去。
48 資料、模型與決策：管理科學篇 54. 傑克遜荷爾製造公司是一家小型製造公司，為汽車和計算機產品生產塑膠製品。它的一項主要合同是為一家大型的計算機公司提供行動式印表機的印表機盒。這種印表機盒是在兩種注模機上生產出來的。M-100 型機每小時能夠生產出25個盒子，M-200 型每小時能夠生產出40個盒子。兩種機器生產每種盒子所需的化學原料相同。M-100 型機每小時使用40磅原料，而 M-200 型機每小時使用50磅原料。客戶要求傑克遜街爾公司在接下來的一週儘可能生產出更多的盒子，它們為每個盒子付出18美元。但是下一週傑克遜荷爾公司生產部的大部分員工都休息。在此期間，公司將對廠裡的裝置進行維修和保養。因為這種原因，M100型機只能工作15小時，而M-200 型機只能工作10小時。又因為裝置啟動的費用很高，所以管理層建議一旦機器啟動，它就必須至少執行小時。化學原料供應商通知傑克遜荷爾公司，下一週原料的最大供應量是1000磅，這種原料的價格是每磅6美元。此外，操作M-100型和 M-200 型機的人工費用分別是 50美元和75美元。 a.建立數學規劃模型，使公司可以獲得最大利潤。 b.找到模型的最優解。 案例問題1 工作載荷平衡數字映像（Digial Imaging,DI）公司生產一種照片印表機，供應專業市場和普通消費市場。DI 的客戶部最近推出兩款可以進行彩色列印的照片印表機，同一家專業處理實驗室生產的產品相抗衡。DI-910 型可以在大約 37秒鐘裡進行4"×6"無邊界的列印。而更加專業且更快速的DI-950型甚至可以進行13"×19”的無邊界列印。財務預測品示，每臺DI-910 型可以獲利42 美元，每臺DI-950 型則可以獲利87美元。 這些印表機在位於北卡羅萊納州的新伯恩的DI工廠裡組裝、測試及包裝。這個工廠生產高度自動化，共有兩條生產線。第一條生產線完成組裝任務，其中，每臺 DI-910 組裝要花費3分鐘，而每臺 DI-950要花費6 分鐘。第二條生產線完成測試和包裝任務。在第二生產線上使用的時間是DI-910佔4分鐘，DI-950佔2分鐘。 因為D1-950印表機的列印速度更快，所以這個階段用時更少。兩條生產線的工作都只有一個班次，即8小時。 營理報告為了確定每種型號各生產多少，我們需要對DI 公司的問題進行分析。為DI 的總裁準備一個報告，介紹你的結論和建議。你需要考慮的問題包括如下方面（不僅限於此）： 1.在8小時班基礎上，要使總利潤最大，建議生產的各型號印表機數量是多少？管理層未執行你的建議的理由是什麼？ 2. 假如管理層表示， DI-910的生產數量至少得和 DI-950一樣多，目標也是在8小時班基礎上，使總利潤敏大。這時，各型號印表機的生產數量是多少？ 3. 你對問題（2）的求解平衡了第一條生產線和第二條生產線的所花的時間嗎？為什麼這種平衡也是管理層所考慮的。 4. 管理層需要對問題（2）進行擴充套件，要求在兩條生產線使用的總時間上更好地進行平衡。管理層希望將兩條生產線總用時的差額限制在30分鐘或更少。如果目標仍然是使總利潤最大，那麼各應該生產多少？這個工作載荷平衡要求對問題（2）有什麼影晌？ S. 設在問題（1）中，管理層的目標是使每一班生產的利潤最大化，而不是使總利潤最大化。在這種條件下，每班應各生產每種型號多少？這個目標對總利潤和工作載荷平衡有什麼影響？ 在你的報告中，你應將對每個問題求解的線性規劃模型和圖解法結果附在報告後面。 案例問題3哈特風險基金哈特風險基金（HVC）為計算機軟體和網際網路的應用發展提供風險資金。目前 HVC公司有兩個投資機會： （1）安全系統，一個公司需要更多的資金用於開發網際網路的安全軟體；（2）市場分析，一個市場調查公司需要更多資金用於開發一套可以對顧客滿意度進行調查的軟體系統。作為與安全系統公司的交換，HVC必須在接下來3年的第1年提供600 000 美元，第2年提供600 000 美元，第3年提供250 000美元。作為與市場分析公司的交換，市場分析公司要求 HVC公司在3年內第1年提供500 000美元，第2年提供350000美元，第3年提供400000美元。HVC公司認為這兩項投資都是值得嘗試的。但是，由於其他的投資，公司只能在第1年共投資800 000 美元，第2年投資700000 美元，第3年投資500000美元。 HVC 的金融分析小組對這兩項計劃進行了調查，建議公司的目標應該是追求總投資利潤淨現值最大化。淨第2章線性規劃導論 49 現值應考慮到3年後兩家公司的股票價值和3年內的資金流出量。按8%的回報率計算，HVC的財務分析小組估計，如果對安全系統公司進行100%的投資，淨現值應該是1800 000美元；對市場分析公司進行100%的投資，淨現值應該是1 600000美元。 HVC 有權對安全系統公司和市場分析公司投人任何比例的資金。比如，如果 HVC 對安全系統公司投人 40%的資金，那麼第1年就需要0.40 x 600 000 =240000 美元，第2年就需要0.40x 600 000=240 000美元， 第3年需要0.40x250 000=100000美元。在這種情況下，淨利潤的值就是0.40 x1 800 000 =720 000美元。 對市場分析公司的投資計算方法相同。 管理報告對HVC 的投資問題進行分析，準備一個報告展示你的建議和結論。包括如下內容（當然不僅限於此）： 1. 這兩種投資各應該佔多大的比例？總投資的淨現值是多少？ 2. 接下來3年的為兩個公司的資金分配計劃是什麼？HVC每年投資的總額是多少？ 3.如果HVC公司願意在第1年追加100000美元投資，會對投資計劃產生什麼影響？ 4. 制定追加100 000 美元投資以後的投資分配計劃。 5. 你是否建議公司第1年再追回投資100 000美元。 在報告的附錄中應該包括線性規劃和圖形的解。 附錄2A 用管理科學家軟體求解線性規劃問題在這一部分，我們將講解如何使用管理科學家軟體求解在管理科學家軟體中，用<表示≤， Par 公司的線性規劃問題。在啟動管理科學家軟體後先執行用＞表示≥。 以下幾步操作： 第一步選擇 Linear Programming 模型第二步選擇 File選單選擇New 第三步 Problem Features 對話方塊出現： 在 Number of Decision Variables 中輸入 2 在 Number of Constraints 中輸人 4 在 Optimization Type 中選擇最大化單擊 OK 第四步當資料輸入表單出現時（如圖2-22所示）： 分別改變 Variable Names，從X1 和X2到S和D 輸入 Objective Funetion Coefficients 對於每個約束條件： 輸入 Coefficients 輸入 Relation（<，=，＞） 輸入 Right- Hand - Side 的值第五步選擇 Solution 下拉選單選擇 Solve 已經輸入完資料的工作表如圖2-22所示。管理科學家軟體的輸出如圖2-14所示。輸人資料時，如果係數是0，則不用輸人。原來的問題可以透過選擇 Edit 下拉選單進行編輯或改寫。最後，選擇 Solution 下拉選單的 Print Solution 選項，可以列印結果。 附錄2B 用 LINDO 求解線性規劃問題 LINDO （Linear, INteractive, and Discrete Optimizer，線性、互動及分離最佳化工具）由萊納斯E.施拉格 （Linus E. Schrage）在芝加哥大學開發出來。這一部分我們將以 Par 公司問題為例向讀者介紹如何使用該軟體解決問題。 當你啟動LINDO時，首先映入眼帝的是兩個窗體。外面的窗體標有•LINDO，包含控制選單和命令工具欄。 一個比較小的窗體標著“<untiled>”，這是模型窗體。這個窗體用來輸入和編輯你想解決的線性規劃問題的
50 資料、模型與決策：管理科學篇 Vaiabe Names： Coelficienks： Subect Jg： Conttarr1 Contrait 2 Corstrengl Conairast4 Obiective funct S D 10 onslreints S 0.7 0.5 1 0.1 083333 0.66667 0.25 Relaticn（c.）） 圖2-22 Par 公司問題的資料輸入工作表 Bicht Hand Side 600 708 135 模型。首先在模型窗體輸入模型的目標方程。以Par公司的問題為例，在此輸人 max 10S +9D。目標函式全部輸人完以後，再輸入模型的約束條件，按回車鍵（Enter），寫入 subject to（或只是字母s.t.）。然後，按回車鍵換行，輸入第一個約束條件0.7S+1D<630。注意，LINDO用＜表示≤。再按回車鍵，輸入第二個約束條件 0.SS +0.833 33D<600。按回車鍵，輸入第三個約束條件 1S+0.666 67D<708。按回車鍵輸入第四個也是最後一個約束條件0.1S+0.25D<135。最後再按回車鍵，輸人END，告訴 LINDO 系統，模型輸人結束。此時，模型視窗應該包括以下內容： max 10S +9D S.t. 0.7S+ 0.5S+ 1S + 0.1S + 1D<630 0.833 33D <600 0.666 67D <708 0.250D<135 END 如果在模型輸人時發生了錯誤，只需簡單地將游標移動到那裡，進行修改就可以了。 為了對模型求解，你必須從Solve 選單中選擇 Solve 命令，或從 LINDO 工具欄中按下 Solve按鈕。如果 LINDO 沒有發現模型有任何錯誤，就開始對模型求解了。作為求解過程的一部分，LINDO 提供了一個狀態視窗用來對求解過程進行監控。當解已經求完了以後，LINDO 將問你是否進行範圍（敏感度）分析。如果選擇 YES 按鈕，並關閉狀態視窗，LINDO 將在一個新視窗中將Par 公司問題完整的解寫出來，視窗的名稱為“Reports Window”。輸出如圖2-23所示。 圖2-23中，輸出的第一部分是自動解釋的。例如，我們看到最優解是S=540及D=252，最優值是7668。 4 個約束的鬆弛變數是0、120、0和18。圖2-23中輸出的剩餘部分可以用來確定目標函式中係數的變化或約束條件右端值的變化怎樣影響最優解。我們會在第3章學習靈敏度分析時討論如何使用這些資訊。 附錄2C 用 Excel 求解線性規劃問題這裡我們將使用Excel 工作表來求解Par 公司問題。我們在工作表的最上面輸人 Par公司問題的資料，在工作表的底部寫數學規劃模型。 2C.1 建模用工作表來建立線性規劃模型，主要包括以下幾步： 第一步在工作表頂部輸入資料。 第二步確定每個決策變數所對應的單元格的位置。 第三步選擇單元格並輸人公式，找到目標函式的值。 第四步選擇一個單元格並輸人公式，計算每個約束條件左端值。 第五步選擇一個單元格並輸入公式，計算每個約束條件右端值。 我們按照這五步為Par 公司建立公式工作表，如圖2-24。注意，工作表包括兩部分：資料部分和模型部分。 模型的4個組成部分都已經展示在圖上了，為決策變數準備的單元格都已經用邊框框起來了。圖2-24所示的就第2章線性規劃導論 51 Objective Function Value 1） 7667.994 Variable CS Row 2） 3） 4） 5） NO. ITERATIONS = 2 OBJ COEFFICIENT RANGES Value -- 539.998413 252.001114 Slack/surplus -一0.000000 120.000717 0.000000 17.999882 Reduced Costs 0.000000 0.000000 Dual Prices 4.374956 0.000000 6.937531 0.000000 Variable D Current Coef 10.000000 9.000000 Allowable Increase 3.499932 5.285714 A11owable Decrease 3.700000 2.3333009 RIGHT HAND SIDE RANGES Row 2 3 4 5 Current RHS 630.000000 600.000000 708.000000 135.000000 A1lowable Increase -------- 52.363155 Infinity 192.000000 Infinity A1lowable Decrease 134.400009 120.000717 127.998589 17.999882 圖2-23 使用 LINDO 對 Par 公司問題進行求解是公式工作表，因為它展示了所有我們輸人的公式，而不是由公式得到的值。過一會兒我們將講解如何使用 Excel 中的Solver，找出Par公司問題的最優解。但現在我們先回顧一下解決問題的步驟。 第一步在工作表的頂部輸人問題的資料。 單元格 B5:C8 顯示每件產品的工作時間要求。 單元格 B9:C9顯示這兩種產品的每一件的貢獻毛益。 單元格 DS:D8 顯示每個部門的可工作時間。 第二步明確每個決策變數所對應的單元格的位置。 單元格 B16是標準袋的產量，單元格C16 是高階袋的產量。 第三步選擇一個單元格，輸人用來計算目標函式值的公式。 單元格 B18： = B9*B16+C9*C16 第四步選擇單元格並輸入公式，計算每個約束條件的左端值。 對於這個模型中的4個約束條件，我們使單元格 B21： = B5*B16 +C5*C16 單元格 B22： = B6 *B16 +C6* C16 單元格 B23： = B7*B16+C7*C16 單元格 B24： = B8 *B16 +C8 *C16 第五步選擇一個單元格並輸入公式，計算每個約束條件的右端值。 對於這個模型中的4個條件，我們使：
52 資料、模型與決策：管理科學篇 Par公司操作切熱與印染縫介成型檢查『j但裴每個袋的利潤 0.7 0.5 0.1 10 模型生產的袋最大總利潤約束切趔與印染縫合成型檢杏與但裝標準袋生產時間 1 10.833 33 10.666 67 10.25 19 高階袋可用時間 630 600 708 1135 決策變數標準袋高階袋耗用時間 （LHS） 可用時間 （RHS） 六弱六料圖2-24 Par 公司的公式工作表單元格 D21：=D5 單元格 D22： = D6 單元格 D23：=D7 單元格 D24：=D8 注意，工作表的上面有標籤，這使得我們很容易理解每一部分的意思。比如，我們在第15 和第16行寫上，標準袋、高階袋的產量，所以我們就很容易理解第15、16行的單元格的意思了。此外，我們在單元格 A18 中寫人“最大總利潤”，用來說明單元格 B18 所表示的是最大利潤。在工作表的約束條件部分，我們增加了約束條件的名稱“＜=”，用來表示約束條件左右兩邊的關係。雖然這些標籤對解題來說不是必要的，但它們幫可以幫助使用者對模型進行理解，並對最優解進行說明。 2C.2 用 Excel 求解由 Frontine 系統公司開發的標準 Excel解決工具，可以用來解決本書中所有的線性規劃問題。 以下是使用由 Frontline 系統公司開發的教育用高階解決工具對 Par 公司問題求解的過程。 第一步選擇 Tools 下拉選單第二步選擇 Solver 選項第三步當出現 Solver Parameters 對話方塊時（如圖2-25所示）： 在 Set Cell 框中輸入 B18 選擇 Equal To: max 項在By Changing Variable Cells 框中輸入 B16:C16 選擇Add 第四步當 Add Constraint 對話方塊出現時： 在 Cell Reference 框巾輸人 B21:B24 選擇<= 在 Constraint 框果輸入 D21:D24 單擊 OK