线性规划概要.ppt

1、第二章,線性規劃概要 Introduction to Linear Programming, Anderson,作業研究(華泰書局2006),p.2/64,章節大綱,前言 範例1極大化問題(Maximize) 問題的模式化 圖解法 線性規劃的四個假設 範例2極小化問題(Minimize) LP模式的形式 線性規劃的解 線性規劃模式的範例,p.3/64,1. 前言,線性規劃（linear programming）簡稱LP 線性（linear）：模式中所有函數均為線性函數 規劃（planning）：指活動的規劃 LP屬數學規劃（mathematical programming，MP） MP：將問題

2、以目標函數及限制式表達的數學模式 LP：MP的所有數學式均為線性,p.4/64,2. 範例1極大化問題(Maximize)(1/3),Par公司是一家高爾夫用具的小型製造商，它的管理當局想要進入中高價位高爾夫球袋的市場。Par公司的經銷商對新產品的開發非常熱衷，並且答應買下往後3個月內所生產的所有球袋。,p.5/64,極大化問題(問題描述, Cont),在充分瞭解高爾夫球袋的生產步驟後，管理當局發現每一個球袋的生產必須經過以下的四個步驟： 1.皮革的切割及染色。 2.縫製。 3.細部製作。 4.檢驗及包裝。,p.6/64,極大化問題(問題描述, Cont),製造部門的主管在分析每一個步驟之後發

3、現 每個高爾夫球袋的生產需求如下：,p.7/64,極大化問題(問題描述, Cont),製造部門的主管在分析每一個步驟之後發現 每個高爾夫球袋的生產需求如下： 1.皮革的切割及染色。 2.縫製。 3.細部製作。 4.檢驗及包裝。,p.8/64,極大化問題(問題描述, Cont),Par公司的生產受限於每一個部門有限的生產工時。在瞭解每一個部門的工作負荷後，製造部門主管估計在未來3個月內， 切染部門的可用於生產高爾夫球袋的工時為630小時、 縫製部門為600小時、 細部製作為708小時、 檢驗及包裝部門為135小時。,p.9/64,極大化問題(問題描述, Cont),會計部門在分析生產資料、計算所

4、有相關的變動成本後，得到 每生產一個標準型球袋的利潤為10元， 生產一個豪華型球袋的利潤為9元。 現在，讓我們來為Par公司的問題建立一個數學模式，分別決定標準型及豪華型球袋的生產量，以使得總利潤為最大。,p.10/64,3. 問題的模式化,問題的模式化(problem formulation or modeling)是將問題的文字描述轉成數學描述的過程。建立LP模式四個步驟 定義決策變數。 寫出此問題的目標函數(並決定是予以極大化或極小化) 寫出限制條件。 決定各變數是否有非負限制式或不受正負限制。,p.11/64,3.1. 定義決策變數(Decision Variable),決策變數為所欲

5、決定之可控制輸入變數，在Par公司的問題中，所欲決定之可控制輸入有二，分別為標準型球袋和豪華型球袋的生產數量，因此，令 S = 標準型球袋的數量D = 豪華型球袋的數量,p.12/64,3.2. 決定目標函數(Objective Function),Par公司對球袋問題的目的在決定標準型及豪華型球袋的生產量，以使得總利潤為最大。而會計部門分析之結果顯示每生產一個標準型球袋的利潤為10元，生產一個豪華型球袋的利潤為9元，所以生產S 個標準型D 個豪華型球袋的利潤為 10S + 9 D，欲最化利潤，故目標函數為 Max 10S + 9D,p.13/64,3.3. 寫出限制條件(constraint

6、),生產受限於每一個部門有限的生產工時，生產球袋必須經過四個部門，每一部門所使用的工時必須小於或等於可用的工時。 限制條件一：生產一個標準型球袋需要花7/10小時的時間在切染部門，而生產一個豪華型球袋需要1小時的時間在切染部門，而切染部門的可用於生產高爾夫球袋的工時為630小時，因此限制條件一為：,p.14/64,寫出限制條件(cont),限制條件二：生產一個標準型球袋需要花1/2小時在縫製部門 ，而生產一個豪華型球袋需要5/6小時的縫製，而縫製部門的可用於生產高爾夫球袋的工時為600小時，因此限制條件二為：,p.15/64,寫出限制條件(cont),限制條件三：生產一個標準型球袋需要花1小時

7、在細部製作 ，而生產一個豪華型球袋需要2/3小時的細部製作，而細部製作部門的可用於生產高爾夫球袋的工時為708小時，因此限制條件三為：,p.16/64,寫出限制條件(cont),限制條件四：生產一個標準型球袋需要花1/10小時在檢驗及包裝細部製作 ，而生產一個豪華型球袋需要1/4小時的檢驗及包裝，而檢驗及包裝部門可用於生產高爾夫球袋的工時為135小時，因此限制條件四為：,p.17/64,3.4. 寫出非負(nonnegative)限制式,Par公司是生產球袋數量不應為負數，因此為了避免決策變數S及D產生負值，必須再加上限制條件 此限制條件可以確保決策變數的解為非負值，因此稱為非負限制式(non

8、negative constraints)。,p.18/64,3.5. 數學模式(mathematical model),Par公司問題完整的數學模式(mathematical model)為： Max10S + 9D Subject to (s.t.),Sec. 2.4,p.19/64,專有名詞,目標函數（objective function） 目標函數值（objective function value） 目標函數係數 限制式係數 右手邊常數（right-hand-side constant；RHS） 限制式（constraint） 功能限制式（functional constraint）

9、 非負限制式（non-negativity constraint）,p.20/64,4. 圖解法（graphical method）,一個只包含二個決策變數的線性規劃問題可以用圖解法求解。利用圖解法求解的三個步驟如下： 繪製非負限制式（或不受正負限制）的範圍 繪製各功能限制式的範圍，並決定可行區域 繪製目標函數的線條，並決定最佳解,p.21/64,4. 圖解法（graphical method）,代表切染時間的限制式為,p.22/64,4. 圖解法（graphical method）,合併所有限制條件的可行區域,p.23/64,4. 圖解法（graphical method）,繪製目標函數，求

10、最佳解,現性規劃問題的最佳解存在於該問題可行區域的極點(extreme points, 可行區的頂點),p.24/64,5. 線性規劃的四個假設,成比例性proportionality 各個項目對於該函數的貢獻和變數之值成比例 可加性additivity 函數的各項目彼此獨立，因此可相互加減 可分性divisibility 所有變數都可以是任何實數值，而不必是整數 確定性certainty 所有係數均為已知的常數,p.25/64,6.範例2極小化問題(Minimize),M&D化學生產兩種原料，賣給別的工廠用來製造肥皂及洗衣粉。根據目前的庫存量以及下個月的可能需求，M&D的管理當局認為，A產品

11、和B產品的產量加起來必須大於350加侖。此外，一個主要客戶的125加侖A產品的訂單也必須要能按時交貨。每一加侖的A產品需要2小時的製造時間，每一加侖的B產品需要1小時的製造時間。在下個月，所有可用的製造時間共有600小時。 M&D的目標是以最少的生產成本滿足這些要求。每加侖A的生產成本為2元，B則為每加侖3元。,p.26/64,定義決策變數及目標函數,令 A = 產品A的加侖數B = 產品B的加侖數 目標函數 Min 2A + 3B,p.27/64,數學模式,完整的數學模式(mathematical model)為： Min2A + 3B Subject to (s.t.),p.28/64,圖

12、解法（graphical method）,合併所有限制條件的可行區域,p.29/64,圖解法（graphical method）,繪製目標函數，求最佳解,現性規劃問題的最佳解存在於該問題可行區域的極點(extreme points, 可行區的頂點),p.30/64,7. LP模式的形式,標準形式,Sec. 2.4,p.31/64,其他形式,目標可以是極小化 限制式可以是大於等於或等於 變數可以無非負限制式 不受正負限制（unrestricted in sign）或 不受限（unrestricted）,p.32/64,8. 線性規劃模式的解,解（solution） 包含所有變數的任何特定值 可行

13、解（feasible solution） 滿足所有限制式 不可行解（infeasible solution） 至少違反其中一個限制式的解 最佳解（optimal solution） 在所有可行解中，具有最有利目標函數值的解,Sec. 2.5,p.33/64,LP問題四種可能解,唯一最佳解（unique optimal solution） 僅有一個最佳解 多重最佳解（multiple optimal solutions） 有無限多個目標函數值相同的最佳解 無可行解（no feasible solutions） 沒有任何可行解，亦即無解 無限解（unbounded solution） 對於極大化問

14、題， 對於極小化問題，,Sec. 2.5,p.34/64,多重最佳解的情況,Par 公司的問題，若目標函數變為,Max 6.3S+9D,Sec. 2.5,p.35/64,無可行解的情況,Par 公司的問題，若增加產量限制式，,D500 S360,Sec. 2.5,p.36/64,無限解,Maxs.t.,p.37/64,9. 線性規劃模式的範例,混合問題 人力安排問題 飲食問題 財務規劃問題 生產採購決策 生產排程問題,Sec. 2.7,p.38/64,混合問題,Sec. 2.7,p.39/64,混合問題 (1/2),定義決策變數： 原油1用於生產產品A的桶數 原油1用於生產產品B的桶數 原油2

15、用於生產產品A的桶數 原油2用於生產產品B的桶數 成分的限制式 產品A最低的辛烷含量是96，所以,Sec. 2.7,p.40/64,混合問題(2/2),LP模式：,Sec. 2.7,p.41/64,人力安排問題(1/2),問題 考慮一家五星級飯店客房部的人力安排問題 員工每週連續上班五天，然後休假兩天 至少需雇用人，才能滿足人力需求？,Sec. 2.7,p.42/64,人力安排問題(2/2),定義： 自星期i開始上班的員工數 LP模式：,Sec. 2.7,p.43/64,飲食問題(1/2),問題： 狗主人每個月應如何以最低的狗糧費用餵食這三隻狗，並滿足狗所需要的營養？,Sec. 2.7,p.4

16、4/64,飲食問題(2/2),定義： 每月餵食每隻狗狗糧A的磅數 每月餵食每隻狗狗糧B的磅數 LP模式： 最佳解：,p.45/64,財務規劃問題(1/2),目前有4億的資金 未來的第二、三、四年年初已確定各需支付1億 四項計畫： 計畫A：以一年為期，每期的預估報酬率為2.5% 計畫B：以兩年為期，每期的預估報酬率為5.2% 計畫C：以三年為期，每期的預估報酬率為8.5% 計畫D：以四年為期，每期的預估報酬率為10.5%,p.46/64,財務規劃問題(2/2),定義： 第 年年初投資計畫A的金額 （其餘同） LP模式：,p.47/64,生產/採購決策問題(1/10),我們將介紹如何使用線性規劃模

17、式於決定一個公司應該自行生產多少的零組件，以及向外採購多少的零組件。此類的決策問題稱為生產採購決策。,p.48/64,生產/採購決策問題(2/10),堅達公司主要銷售各種的商業及工程用品。目前堅達公司打算推出兩種新的電子計算器，一種是財務計算器稱為財務經理，另一種工程用計算器稱為技術師。每一個計算器由底座、電路板、以及面板三種零件所組成。底座可以通用於兩種計算器，但電路板及面板則是不同的。所有的零件都可以由公司自行生產或者向外採購。,p.49/64,生產/採購決策問題(3/10),各零件的製造成本及採購價格列於表4.5。,p.50/64,生產/採購決策問題(4/10),根據堅達公司的預測， 市

18、場的需求量為3000個財務經理計算器，以及2000個技術師計算器。 然而，以堅達公司有限的生產能量，只有200小時的正常生產工時，以及50小時的加班工時可以用於生產計算器。 加班工時的單位成本為9元。,p.51/64,生產/採購決策問題(5/10),表4.6所列為各種零件的生產時間(以分鐘為單位)。,p.52/64,生產/採購決策問題(6/10),堅達公司所面臨的問題在於 應該生產多少的零件以及向外採購多少的零件所需成本最小。 定義決策變數： BM = 底座的生產量BP = 座的採購量FCM = 財務型電路板的生產量 FCP =財務型電路板的採購量,p.53/64,生產/採購決策問題(7/10

19、),定義決策變數(續)： TCM = 工程型電路板的生產量TCP = 工程型電路板的採購量FTM =財務型面板的生產量FTP =財務型面板的採購量TTM = 工程型面板的生產量TTP =工程型面板的採購量 及 OT =加班所用的工時(小時),p.54/64,生產/採購決策問題(8/10),目標函數：最小化成本 Min,生產成本,採購成本,加班成本,p.55/64,生產/採購決策問題(9/10),限制一五：所需材料及產量滿足市場需求量： 3000個財務經理計算器及以及2000個技術師計算器，材料數要相搭配：,(底座總數),(財務型電路板),(財務型面板),(工程型面板),(工程型電路板),p.56/64,生產/採購決策問題(10/10),限制式六：加班的時間最多為50個小