武漢大學(xué)MBA課程《數(shù)據(jù)模型與決策》課件 (29)線性規(guī)劃與電子表格

據(jù)、模型與決策 3 性規(guī)劃與電子表格 一個課堂操作舉例 線性規(guī)劃的基本概念 P 線性規(guī)劃的圖解法 用微軟 解 P 線性規(guī)劃問題的主要類型 P 三個經(jīng)典的線性規(guī)劃應(yīng)用 每個小組都有一組拼裝玩具 (8個小塊和 6 大塊 ) ，這些是你們的原材料（ 你們要用這些原材料去生產(chǎn)桌和椅（ 兩種產(chǎn)品（ 具體拼裝圖如下一個幻燈片。 裝玩具生產(chǎn) 自己動手 你怎么去分析呢？ 想想看！ 原材料 6 大塊 8 小塊 產(chǎn)品 桌 椅 $20/ $15/己動手 M a x i m i z e ($ 15 ) C h a i r s ($ 20 ) T a b l e ss u b j e c t t oL a rg e B ri c k s : C h a i r s 2 T a b l e s 6S m a l l B ri c k s : 2 C h a i r s 2 T a b l e s 8a n dC h a i r s 0 , T a b l e s 0 自己動手 你的答案是什么？ 型的組成部分 策變量 標(biāo)函數(shù) 束 性規(guī)劃的假設(shè) 線性 可分性 確定性 非負(fù)性 為什么要使用線性規(guī)劃 線性規(guī)劃很容易而有效率地被求解 如果存在最優(yōu)解，則肯定能夠找到 功能強大的敏感性分析（ 許多實際問題本質(zhì)上是線性的 P 性規(guī)劃的數(shù)學(xué)描述 線性規(guī)劃要確定決策變量 , 得 M a x i m i z e Z e c t t a1 a2 0 , , 0 , ; , ; , P 性規(guī)劃問題建模步驟 需要做哪些決策？決策變量是什么 問題的目標(biāo)是什么？寫出目標(biāo)函數(shù) 資源和需求之間的情況如何？ 確定約束條件 P 線性規(guī)劃的圖解法 P 線性規(guī)劃的單純形法 (0 , 0 )(4 , 0 )(0 , 6 )Pr o d u ct i o n e fo r w i n d o w o d u ct i o n e fo r d o o r o f i t = $ 3 , 0 0 0(2 , 6 )Pr o f i t = $ 3 , 6 0 0Pr o f i t = $ 2 , 7 0 0Pr o f i t = $ 1 , 2 0 0i b l e i o , 3 )Pr o f i t = 0用微軟 解 解玩具拼裝問題 用易理解方式輸入數(shù)據(jù)和構(gòu)筑數(shù)據(jù)之間的聯(lián)系 定義目標(biāo)單元格（目標(biāo)函數(shù)） 確定可變單元（決策變量） 添加約束變量 （ 解結(jié)果 P 線性規(guī)劃問題主要類型 資源分配問題（ 成本收益平衡問題 （ 網(wǎng)絡(luò)配送問題（ 混合問題（ 問題類型 資源分配（ 問題 是將有限的資源 分配到各種活動中去的線性規(guī)劃問題。這一類問題的 共性是在線性規(guī)劃模型中每一個函數(shù)限制均為資源限 制 (, 并且每一種有限資源都可以表 現(xiàn)為如下的形式： 使用的資源數(shù)量 可用的資源數(shù)量 集數(shù)據(jù) 問題所有活動可獲得使用的每種資源的有限數(shù)量 每一種活動所需要的各種資源的數(shù)量 , 每一種資源 與活動的組合 ,單位活動消耗資源量必須首先估計 每一種活動對總的績效測度的單位貢獻(xiàn) 超級谷物公司 實際舉例 o. 夢大發(fā)展公司 實際舉例 本收益平衡問題 問題類型 成本收益平衡問題（ 是一類線性規(guī)劃問題，這類問題中，通過選擇各種 活動水平的組合，從而以最小的成本來實現(xiàn)最低可 接受的各種收益的水平。這類問題的共性是，所有 的函數(shù)約束均為收益約束，并具有如下的形式： 完成的水平 最低可接受的水平 本收益平衡問題舉例 作人員排程 制空氣污染 邦聯(lián)航空公司 實際舉例 絡(luò)配送問題 問題類型 網(wǎng)絡(luò)配送問題 （ 以最小的成 本完成貨物的配送，所以稱之為網(wǎng)絡(luò)配送問題并具有 如下的確定性約束形式： 提供的數(shù)量需要的數(shù)量 2 u n i t sp ro d u c u n i t s p ro d u c u n i t sn ee d u n i t s n ee d 7 0 0 / u n i t$ 9 0 0 / u n i t$ 2 0 0 / u n i t 5 0 u n i t s m $ 4 0 0 / u n i t 5 0 u n i t s m $ 3 0 0 / u n i t 5 0 u n i t s m $ 4 0 0 / u n i t 5 0 u n i t s m o. 無限配送公司 實際舉例 合問題 問題類型 資源分配問題 ， 成本收益平衡問題以及網(wǎng)絡(luò)配送問 題 ， 都以一類約束條件為特色的 。 實際上 ， 純資源 分配問題的共性是它所有的函數(shù)約束均為資源約束 ， 而成本收益平衡問題的共性是它所有的函數(shù)約束均 為收益約束 ， 網(wǎng)絡(luò)配送問題中 ， 主要的函數(shù)約束為 一特定類型的確定需求的約束 。 混合問題 是第四類線性規(guī)劃問題，這一類型包括 了三類約束函數(shù) 維特公司 實際舉例 維特公司 實際舉例 P 性規(guī)劃問題總結(jié) 類型總結(jié) 類型 形式 解釋 主要用于 資源約束 于特定的資源使用的數(shù)量 可獲得的數(shù)量 資源分配問題混合問題 收益約束 于特定的收益達(dá)到的水平 最低可接受水平 成本收益平衡問題混合問題 需求確定約束 于一些數(shù)量提供的數(shù)量 需求的數(shù)量 網(wǎng)絡(luò)配送問題混合問題 理視角的建模 總績效測度必須是管理層想獲得的現(xiàn)實目標(biāo) 準(zhǔn)確細(xì)致地描述資源約束 管理科學(xué)小組與管理層的有效溝通 模型往往要不斷地修改和擴展 要進(jìn)行 P 線性規(guī)劃經(jīng)典應(yīng)用回顧 應(yīng)用回顧 為潘德羅索工業(yè)公司選擇產(chǎn)品組合 聯(lián)合航空公司工作人員排程 送 與營銷的規(guī)劃 德羅索工業(yè)公司 公司經(jīng)驗 潘德羅索應(yīng)用成功的因素： 以 自然語言 為用戶界面的財務(wù)計劃系統(tǒng)，使用自然語言而不是數(shù)學(xué)符號來顯示線性規(guī)劃模型各個組成部分以及輸出的結(jié)果，使得做決策的管理者能夠很容易看懂整個過程。 最優(yōu)化系統(tǒng)是 互動的 （ 管理者在從一個版本的模型中獲得一組最優(yōu)解之后，可以提出一系列的 能立即得到回應(yīng)。 A. 聯(lián)合航空公司人員排程 公司經(jīng)驗 聯(lián)合航空公司 利用線性規(guī)劃，來為其在主要的機場和定票點的上萬個工作人員安排每周的工作時間表。目標(biāo)是為了能夠在滿足客戶的服務(wù)需要的同時，將一周內(nèi)每天每半個小時的人員成本最小化。聯(lián)合航空公司一些地點的規(guī)劃模型卻包括 20，000個決策變量。 應(yīng)用成功最主要的因素是因為得到了運營經(jīng)理以及其它員工的大力支持。 公司經(jīng)驗 運用管理科學(xué)的技術(shù)，特別是線性規(guī)劃，建立供應(yīng)、配送與營銷的建模系統(tǒng)將公司主要產(chǎn)品的供應(yīng)、配送與營銷通過公司龐大的銷售與配送網(wǎng)絡(luò)得到很好的協(xié)調(diào)。在 90年代中期創(chuàng)造了大量的財富。 公司每種主要產(chǎn)品的模型都含有大約 1， 500個決策量以及3， 000個確定需求的約束 最重要的 成功因素 是高層管理者所給予的 無限制 的支持，并且設(shè)立運作協(xié)調(diào)副總裁，來負(fù)責(zé)評價與協(xié)調(diào)這一跨組織邊界的模型所提供的建議 講小結(jié) 小結(jié) 以 符號表示的函數(shù)約束稱為資源約束 ， 這些限制要求使用的資源必須小于等于所能提供的資源的數(shù)量 。 資源分配問題的共性就是它們的函數(shù)約束全部為資源約束 。 以 符號表示的函數(shù)約束為收益約束 ， 形式為收益取得的水平必須大于等于最低可接受水平 。 收益約束反映了管理層所規(guī)定的目標(biāo) 。 如果所有約束均為收益約束 ， 這一問題為成本收益平衡問題 。 講小結(jié) 小結(jié) 以符號表示的函數(shù)約束稱為確定需求的約束 ， 它們表示了一定數(shù)量的確定的需求 ， 提供的數(shù)量等于要求的數(shù)量 。 網(wǎng)絡(luò)配送問題的共性就是它們的主要函數(shù)約束為一種特定形式的確定需求的約束 。 不能歸于這三類的任何線性規(guī)劃的問題稱為混合問題 。 在