经管类线性规划概论.ppt

第二章 線性規劃概論 Introduction to Linear Programming 章節大綱 前言 典型範例 圖解法 線性規劃模式的形式 線性規劃模式的解 線性規劃的假設 線性規劃模式的範例 2.1 前言 線性規劃（linear programming）簡稱LP 線性（linear）：模式中所有函數均為線性函數 規劃（planning）：指活動的規劃 線性規劃屬數學規劃（mathematical programming，MP） MP：將問題以目標函數及限制式表達的數學模式 LP：MP的所有數學式均為線性 2.2 典型範例 某公司生產兩種產品P1及P2，需要使用兩部機器M1與M2 ，每箱利潤為$7000及$8000 ，詳細資料如下表，每週應分別生產多少箱的P1及P2，才能獲得最大的利潤？ 建立LP模式四個步驟 定義決策變數 寫出此問題的目標函數，並決定是予以極大化或極小化 寫出各功能限制式 決定各變數是否具有非負限制式或不受正負限制 2.2 典型範例 LP模式： 2.3 圖解法（graphical method） 三個步驟： 繪製非負限制式（或不受正負限制）的範圍 繪製各功能限制式的範圍，並決定可行區域 繪製目標函數的線條，並決定最佳解 以圖解法求解典型範例 2.4 LP模式的形式 標準形式 專有名詞 目標函數（objective function） 目標函數值（objective function value） 目標函數係數 限制式係數 右手邊常數（right-hand-side constant；RHS） 限制式（constraint） 功能限制式（functional constraint） 非負限制式（non-negativity constraint） 其他形式 目標可以是極小化 限制式可以是「大於等於」或「等於」 變數可以無非負限制式 不受正負限制（unrestricted in sign）或 不受限（unrestricted） 2.5 線性規劃模式的解 解（solution） 包含所有變數的任何特定值 可行解（feasible solution） 滿足所有限制式 不可行解（infeasible solution） 至少違反其中一個限制式的解 最佳解（optimal solution） 在所有可行解中，具有最有利目標函數值的解 LP問題四種可能解 唯一最佳解（unique optimal solution） 僅有一個最佳解 多重最佳解（multiple optimal solutions） or 擇一最佳解（alternative optimal solutions） 有無限多個目標函數值相同的最佳解 無可行解（no feasible solutions） 簡稱無解 沒有任何可行解 無窮解（unbounded solution） 對於極大化問題， 對於極小化問題， 多重最佳解的情況 無可行解的情況 無窮解的情況 2.6 線性規劃的假設 成比例性proportionality 各個項目對於該函數的貢獻和變數之值成比例 可加性additivity 函數的各項目彼此獨立，因此可相互加減 可分性divisibility 所有變數都可以是任何實數值，而不必是整數 確定性certainty 所有係數均為已知的常數 2.7 線性規劃模式的範例 混合問題 人力安排問題 飲食問題 財務規劃問題 混合問題 混合問題 (1/2) 定義決策變數： 原油1用於生產產品A的桶數 原油1用於生產產品B的桶數 原油2用於生產產品A的桶數 原油2用於生產產品B的桶數 成分的限制式 產品A最低的辛烷含量是96，所以 混合問題(2/2) LP模式： 人力安排問題(1/2) 問題 考慮一家五星級飯店客房部的人力安排問題 員工每週連續上班五天，然後休假兩天 至少需雇用人，才能滿足人力需求？ 人力安排問題(2/2) 定義： 自星期開始上班的員工數 LP模式： 飲食問題(1/2) 問題： 狗主人每個月應如何以最低的狗糧費用餵食這三隻狗，並滿足狗所需要的營養？ 飲食問題(2/2) 定義： 每月餵食每隻狗狗糧A的磅數 每月餵食每隻狗狗糧B的磅數 LP模式： 最佳解： 財務規劃問題(1/2) 目前有4億的資金 未來的第二、三、四年年初已確定各需支付1億 四項計畫： 計畫A：以一年為期，每期的預估報酬率為2.5% 計畫B：以兩年為期，每期的預估報酬率為5.2% 計畫C：以三年為期，每期的預估報酬率為8.5% 計畫D：以四年為期，每期的預估報酬率為10.5% 財務規劃問題(2/2) 定