第二章-線性規(guī)劃基本概念-精選課件

1、第二章 線性規(guī)劃：基本概念 任何有用的資源都不是取之不盡，用之不竭的。水和空氣都是這樣。既然如此，人類每一個組織的管理都必須面對向不同的活動分配有限資源的問題。那么，如何分配才能達到組織的目標(biāo)，就是一個經(jīng)常需要面對的問題，而線性規(guī)劃（Linear Programming）使得作出這些決策成為可能。第二章 線性規(guī)劃：基本概念 任何有用的資一、三個經(jīng)典的線性規(guī)劃應(yīng)用確定潘德羅索工業(yè)公司的產(chǎn)品組合聯(lián)合航空公司的員工排程Citgo石油的供應(yīng)、配送和營銷規(guī)劃一、三個經(jīng)典的線性規(guī)劃應(yīng)用確定潘德羅索工業(yè)公司的產(chǎn)品組合你有沒有如下感覺茫然驚奇沖動問題頭緒較多，不 知道如何下手線性規(guī)劃究竟是什么樣子？有這 么神

2、奇的“功效”我得盡快搞清楚這個東西，它太誘人了你有沒有如下感覺茫然問題頭緒較多，不 知道如何下手二、案例研究：Wyndor玻璃制品公司產(chǎn)品組合問題 公司背景資料 Wyndor玻璃制品公司有三個工廠工廠1：生產(chǎn)鋁框和硬制件工廠2：生產(chǎn)木框工廠3：生產(chǎn)玻璃和組裝窗和門他們的新產(chǎn)品開發(fā)部最近開發(fā)出兩種新產(chǎn)品： 8英尺的鋁框玻璃門 4英尺6英尺的雙把木框窗二、案例研究：Wyndor玻璃制品公司產(chǎn)品組合問題 公司面臨的問題 由于公司某些產(chǎn)品銷售量的下降，公司高層決定調(diào)整公司的生產(chǎn)線。即停掉一些產(chǎn)品的生產(chǎn)。但是否將騰出來的一部分生產(chǎn)能力來生產(chǎn)這兩種新產(chǎn)品還需要作進一步的論證。公司管理部門現(xiàn)在需要考慮下列兩

3、個問題： 1.公司是否應(yīng)該生產(chǎn)這兩個新產(chǎn)品？ 2.如果生產(chǎn)，兩個新產(chǎn)品的生產(chǎn)組合如何？公司面臨的問題 由于公司某些產(chǎn)品銷售量的下初步解決的辦法 帶著這些問題，公司總裁召集有關(guān)人員開會討論。結(jié)果是，第一個問題作出了肯定的決策，而第二個問題，則需要管理小組利用管理科學(xué)方法先作出建議，而總裁的要求是我們需要對公司而言贏利最大的兩種產(chǎn)品的組合。初步解決的辦法 帶著這些問題，公司總裁召管理科學(xué)小組要做的首項工作定義問題和收集數(shù)據(jù) 問題：兩種新產(chǎn)品的生產(chǎn)率（每周生產(chǎn)數(shù)量）的哪種組合能最大化兩種產(chǎn)品的總利潤 所需要的數(shù)據(jù)： 1.每家工廠的生產(chǎn)能力； 2.生產(chǎn)每一產(chǎn)品各需要每家工廠多少生產(chǎn)能力； 3.每一產(chǎn)品

4、的單位利潤。管理科學(xué)小組要做的首項工作定義問題和收集數(shù)據(jù)Wyndor玻璃制品公司產(chǎn)品組合問題的數(shù)據(jù) 生產(chǎn)每個單位所需要的時間工廠門窗每周可得時間1231小時03小時02小時2小時4小時12小時18小時單位利潤（美元）$300$500Wyndor玻璃制品公司產(chǎn)品組合問題的數(shù)據(jù) 生產(chǎn)想一想，議一議如果Wyndor玻璃制品公司的產(chǎn)品組合問題在以上條件下就能夠解決的話，你是否覺得潘德羅索工業(yè)公司的產(chǎn)品組合問題也有些頭緒了?對于潘德羅索工業(yè)公司的產(chǎn)品組合問題，你確定的目標(biāo)是什么?你需要哪些數(shù)據(jù)？想一想，議一議如果Wyndor玻璃制品公司的產(chǎn)品組合問題在以三、Wyndor公司問題的電子表格模型Excel工

5、作表偉恩德公司問題模型.xls三、Wyndor公司問題的電子表格模型Excel工作表偉恩四、Wyndor公司問題的代數(shù)模型線性規(guī)劃代數(shù)模型的建立方法 1.設(shè)出決策變量； 2.寫出目標(biāo)函數(shù)； 3.確定約束條件。對Wyndor公司問題而言，設(shè)D為每周應(yīng)生產(chǎn)的門數(shù)，W為每周應(yīng)生產(chǎn)的窗數(shù)，那么，目標(biāo)函數(shù)就是P=300D+500W,而約束條件則為：四、Wyndor公司問題的代數(shù)模型線性規(guī)劃代數(shù)模型的建立方法 （）我們的目的就是確定D和W的值，在（）條件下，使得目標(biāo)函數(shù)P300D500W達到最大。 線性規(guī)劃的一些術(shù)語：代表特定活動程度決策的一個代數(shù)變量，稱為決策變量；由決策變量的線性表達式表達的績效稱為目

6、標(biāo)函數(shù)；決策變量須受到的限制（通常為關(guān)于決策變量的線性等式或不等式）稱為約束條件；線性規(guī)劃的一些術(shù)語：代表特定活動程度決策的一個代數(shù)變量，稱為決策變量的任何一個取值稱為模型的一個解；滿足所有約束條件的解，稱為可行解；所有的可行解構(gòu)成的集合，稱為可行域；是目標(biāo)函數(shù)達到最大的可行解，稱為最優(yōu)解。決策變量的任何一個取值稱為模型的一個解； 某工廠有一批長度為5米的鋼管（數(shù)量充分多），為制造零件的需要，要將它們截成長度分別為1400毫米，950毫米，650毫米的管料，而且這三種管料要按2：4：1的比例配套生產(chǎn)，就是說每制造一個成品分別需要2根1400毫米，4根950毫米，1根650毫米的管料。 某工廠有

7、一批長度為5米的鋼管（數(shù)量充分多），為制造零件的把一根一定長度的鋼管截成n段需要的管料時，一般要產(chǎn)生殘料，例如，把5米的管料截成1400毫米的3根和650毫米的1根，要剩殘料150號毫米；如果截成1400毫米的2根和950毫米的兩根剩殘料300毫米。現(xiàn)在的問題是如何截分才能使剩下來的三種管料，既能配套，又使殘料最少。把一根一定長度的鋼管截成n段需要的管料時，一般要產(chǎn)生殘料，例8種不錯的截法： 截 法1 2 3 4 5 6 7 8 長度1400mm950mm650mm3 2 2 1 1 0 0 00 2 0 3 1 5 3 11 0 3 1 4 0 3 6殘料（mm）150 300 250 10

8、0 50 250 200 150 截 法1 2 3 4 用xi(i=1,2,，8)表示采用第i種截法的鋼管數(shù)目，那么截出1400mm的管料數(shù)目是： 3x1+2x2+2x3+x4+x5 截出900mm的管料數(shù)目是： 2x2+3x4+x5+5x6+3x7+x8 截出650mm的管料數(shù)目是： x1+3x3+x4+4x5+3x7+6x8 根據(jù)配套要求，它們應(yīng)分別等于2a,4a,a(a是套數(shù))，我們先讓a等于某一個正整數(shù)，例如a=1,求出xi以后，如果xi是分數(shù)，就乘以xi的分母的最小公倍數(shù)，這時候殘量 S=150 x1+300 x2+250 x3+100 x4+50 x5+250 x6+200 x7+

9、150 x8 用xi(i=1,2,，8)表示采用第i五、求解兩變量問題的圖解法（以Wyndor問題為例）246240DW可行域最優(yōu)解（2，6）P=3600P=3000P=1500五、求解兩變量問題的圖解法（以Wyndor問題為例）2462六、應(yīng)用Excel求解線性規(guī)劃問題建立問題的Excel電子表格；在工具菜單中選擇“規(guī)劃求解”得到“規(guī)劃求解參數(shù)”對話框；確定目標(biāo)單元格（鍵入或點擊），選擇最大值（或最小值），確定可變單元格（鍵入或點擊），添加約束條件（鍵入或點擊）；點及“選項”，選擇“假定線性模型”和“假定非負條件”；點及“規(guī)劃求解參數(shù)”對話框中的“求解”，即可得到線性規(guī)劃的最優(yōu)解（存在的話）

10、。六、應(yīng)用Excel求解線性規(guī)劃問題建立問題的Excel電子表一個最小化的例子利博公司廣告組合問題利博公司生產(chǎn)家用的清潔產(chǎn)品，這是一個高度競爭的市場，為此，公司高層決定通過廣告增加三種主要產(chǎn)品的銷售量，這三種主要產(chǎn)品是： 1.一種噴霧去污劑 2.一種新的液體洗滌劑 3.一種成熟的洗衣粉管理部門的目標(biāo)是以最低的總成本來達到預(yù)定的產(chǎn)品銷售量的增加值。一個最小化的例子利博公司廣告組合問題利博公司生產(chǎn)家用的清管理部門選定廣告的媒體是電視和印刷出版物，且設(shè)定了廣告的最低目標(biāo)： 1.噴霧去污劑必許再增加3的市場份額； 2.新的液體洗滌劑必須在西低級市場中獲得18的份額； 3.洗衣粉占洗滌劑市場的份額必須增

11、加4。 通過市場調(diào)查，可得到一個單位電視廣告的費用為100萬元，一個單位印刷廣告的費用為200萬元。此外，問題中的其它數(shù)據(jù)也是可以得到的（盡管都是估計值）。管理部門選定廣告的媒體是電視和印刷出版物，且設(shè)定了廣告的最低利博公司廣告組合問題的數(shù)據(jù)每單位廣告增加的市場份額產(chǎn)品電視印刷出版物需要最小的增加量去污劑液體洗滌劑洗衣粉0311243184單位成本100萬美元200萬美元利博公司廣告組合問題的數(shù)據(jù)每單位廣告增加的市場份額產(chǎn)品電視印利博公司廣告組合問題的電子表格模型Excel工作表利博公司廣告組合問題模型.xls利博公司廣告組合問題的電子表格模型Excel工作表利博公司利博公司廣告組合問題的代數(shù)模型設(shè)TV和PM分別是公司應(yīng)做的電