第二章线性规划基本概念.ppt

第 2 章 線性規劃：基本概念 學習目標 在讀完本章後，你應該能夠： 1. 解釋什麼是「線性規劃」。 2. 了解建構試算表模式前所必須找出的三項核心問題。 3. 指出及確認線性規劃試算表模式中四種儲存格的目的。 4. 根據問題描述於試算表中建構線性規劃模式。 5. 在試算表中表示線性規劃模型的代數式。 6. 運用圖解法求解雙變數線性規劃問題。 7. 使用 Excel 求解線性規劃試算表模式。 偉伯玻璃公司產品組合問題 偉伯公司發展以下的新產品： 鋁框 8 呎玻璃門 4 呎 ? 6 呎可雙面懸掛的木框窗戶 公司擁有三間工廠 ： 工廠 1：生產鋁框及金屬器件 工廠 2：生產木框 工廠 3：生產玻璃並進行門及窗戶的組裝 問題： 公司是否應該從事新產品的生產？ 如果是的話，最佳的產品組合為何？ 發展試算表模式 步驟一：資料儲存格 在試算表上輸入問題所有相關的資料 使用一致性的欄與列儲存方式 利用不同顏色來顯示這些「資料儲存格」（例如：淺色）是不錯的方法 發展試算表模式（續） 步驟二：變動儲存格 在試算表上替每個需要做的決策設置一儲存格 若是你沒有特殊的起始解（initial values）考量，只要輸入 0 即可 利用顏色與框線等來顯示這些「變動儲存格」（例如：淺色並加框線）是不錯的方法 發展試算表模式（續） 步驟三：目標儲存格 發展一個方程式來定義模式的目標 基本上此方程式涉及資料儲存格與變動儲存格以便決定感興趣的數量（例如：總利潤或總成本） 利用顏色來顯示這個儲存格（例如：深色並加粗框線）是不錯的方法 發展試算表模式（續） 步驟四：限制式 對於受限制的資源，在試算表某一儲存格中計算該資源使用量（輸出儲存格） 在三個連續的儲存格中定義限制式。例如：若數量A = 數量B，將此三項（數量A、 =、 數量B）置於相鄰的儲存格 一組試驗解 偉伯玻璃公司之代數模式 產品組合示意圖 滿足限制式：D ≥?0 及 W ≥ 0之區域示意圖 滿足 D ≤ 4 之非負解 滿足 2W ≤?12 之非負解 限制式 3D + 2W ≤?18 之邊界線 改變右側值將產生一些平行的限制式邊界線 滿足 3D + 2W ≤?18 之非負解 可行解區域之示意圖 目標函數（P = 1,500） 尋找最佳解 圖解法摘要 畫出每個函數限制式的限制邊界線，利用原點（或其他不在線上的點）決定線的哪一邊才能滿足限制式。 確定是否同時滿足所有的限制式，找出可行區域。 求出目標函數線的斜率，所有的目標函數線的斜率要相同。 以這個斜率，在可行區域內往可改善目標值的方向移動線段，直到此線段與可行區域只交於一點即停止移動，包含這條線段的直線即是最佳目標函數線。 在最佳目標函數線上的可行點即為最佳解。 辨識目標儲存格與變動儲存格 從「工具」選單選擇「規劃求解」 在「設定目標儲存格」視窗中，選擇你想要最佳化的儲存格 依據你是否要最大化或最小化目標儲存格，選擇「最大值」或「最小值」 在「變動儲存格」視窗中輸入所有變動儲存格 新增限制式 若要輸入限制式，選擇限制式視窗右側的「新增」按鈕 在「新增限制式」對話視窗中輸入限制式相關資料 完整的「規劃求解」對話視窗 一些重要的選項 按「選項」鈕，並且選取「採用線性模式」以及「採用非負值」二個選項 「採用線性模式」告訴規劃求解這是一個線性規劃模式 「採用非負值」會將非負限制式加到所有變動儲存格 「規劃求解結果」對話視窗 最佳解 Profit Gambit 公司 管理階層決定推動一個新的廣告活動，並把目標鎖定在以下三種主要產品上： 噴霧去漬劑 液態洗衣精 洗衣粉 這個活動將運用電視及平面媒體作廣告 最根本的目標是希望增加這些產品的銷售量 管理階層為該廣告活動訂定以下目標： 去漬劑的銷售額至少要增加 3%。 洗衣精的銷售額至少要增加 18%。 洗衣粉的銷售額至少要增加 4%。 問題：目標是要決定於各種媒體應該廣告多少數量，在達到銷售目標的前提下，使總成本最小化？ Profit Gambit 公司試算表模式 Profit Gambit 公司問題之代數模式 運用圖解法 最佳解 圖解法摘要 畫出每個函數限制式的限制邊界線，利用原點（或其他不在線上的點）決定線的哪一邊才能滿足限制式。 確定是否同時滿足所有的限制式，找出可行區域。 求出目標函數線的斜率，所有的目標函數線的斜率要相同。 以這個斜率，在可行區域內往可改善目標值的方向移動線段，直到此線段與可行區域只交於一點即停止移動，包含這條線段的直線即是最佳目標函數線。 在最佳目標函數線上的可行點即為最佳解。 一個生產問題 線性規劃 線性規劃使用數學模式來找出對於各項活動最佳的資源配置以使得利潤最大或是成本最小 圖形表示 線性規劃模式的組成元素 資料儲存格 變動儲存格（決策變數） 目標儲存格（目標函數）