管理學(xué)線性規(guī)劃問題PPT學(xué)習教案

1、會計學(xué)1管理學(xué)線性規(guī)劃問題管理學(xué)線性規(guī)劃問題引言引言在經(jīng)濟生活中，人們經(jīng)常遇到這樣兩類實際問題：1、資源給定，如何對給定資源予以充分地、合理地運用，使之完成的任務(wù)盡可能地多。2、任務(wù)給定，如何以盡可能少的資源消耗來完成給定的任務(wù)。 可見，上述兩類問題都是尋求利潤最大。第一類，是以最大收益扣除定量成本；第二類，是以定量收益扣除最小成本。 在滿足一定條件時，這類優(yōu)化問題都可以用線性規(guī)劃的方法來予以解決。第1頁/共24頁線性規(guī)劃的概念線性規(guī)劃的概念 當收益和消耗均與計劃指標呈正比時，一個規(guī)劃問題所列出的數(shù)學(xué)表達式都是關(guān)于計劃指標的線性關(guān)系式，稱此類型規(guī)劃問題為線性規(guī)劃問題。線性規(guī)劃問題是：在一組線性

2、約束條件下，求一組非負變量的值，使一個線性目標函數(shù)達到最大或最小。第2頁/共24頁例1：某廠生產(chǎn)兩種產(chǎn)品，需要三種資源，已知各產(chǎn)品的利潤、各資源的限量和各產(chǎn)品的資源消耗系數(shù)如下表：產(chǎn)品產(chǎn)品A產(chǎn)品產(chǎn)品B資源限制資源限制勞動力勞動力94360工時工時設(shè)備設(shè)備45200臺時臺時原材料原材料310300公斤公斤單位產(chǎn)品利潤（元）單位產(chǎn)品利潤（元）70120問題：如何安排生產(chǎn)計劃，使得獲利最多？第3頁/共24頁分析： 這是一個生產(chǎn)計劃問題，設(shè)生產(chǎn)A產(chǎn)品X1kg, B產(chǎn)品X2kg. 則該問題可以用如下模型來描述： Max Z=70X1+120X2 9X1+4X2360 s.t. 4X1+5X2 200 3

3、X1+10X2 300 X10 X20 該模型的解為生產(chǎn)計劃。第4頁/共24頁例2：某運輸問題，已知資料如下表所示，問如何調(diào)運，使產(chǎn)銷平衡且總運費最小？B1B2B3B4產(chǎn)量產(chǎn)量（噸）（噸）A15610360A2419740A3424860銷量（噸）30504040單位運費產(chǎn)地銷地單位：百萬/噸第5頁/共24頁這是一個產(chǎn)銷平衡運輸問題，即：Ai 地產(chǎn)量ai= Bj 地銷量bj (i=1，2，3；j=1,2,3,4) 設(shè)從生產(chǎn)地Ai到銷售地Bj的調(diào)運量為： Xij (i=1，2，3；j=1,2,3,4） 該問題的數(shù)學(xué)模型為：Min Z=5 X11+6 X12+10X13+3X14+4X33+8 X

4、34 X11+X12+X13+X14=60 X21+X22+X23+X24 =40 s.t. X11+X21+X31=30 X14+X24+X34=40 Xij 0 (i=1，2，3；j=1,2,3,4） 產(chǎn)量約束銷量約束第6頁/共24頁從數(shù)學(xué)上來講,它們的共同特征是:(1)每個問題都用一組決策變量(x1 , x2 , , xn)表示某一方案 ,這組未知數(shù)的值就代表一個具體的方案,通常要求這些未知數(shù)取值是非負的。(2) 存在一定的限制條件(稱為約束條件),這些條件都可以用關(guān)于決策變 量的一組線性等式或不等式來表示。(3) 都有一個目標要求,并且這個目標可表示為這組決策變量的線性函數(shù)(稱為目標函

5、數(shù)),按研究問題的不同,要求目標函數(shù)實現(xiàn)最大化或最小化。 第7頁/共24頁線性規(guī)劃的三要素線性規(guī)劃的三要素u 決策變量：根據(jù)影響所要達到目的的因素找到?jīng)Q策變量 生產(chǎn)產(chǎn)品量，運輸分配量等u 目標函數(shù)：由決策變量和所要達到目的之間的函數(shù)關(guān)系確定目標函數(shù)； 最大利潤，最小運費等u 約束條件：由決策變量所受的限制條件確定決策變量所要滿足的約束條件 原材料限制，工時限制等第8頁/共24頁求解線性規(guī)劃問題的方法：求解線性規(guī)劃問題的方法：（1）數(shù)學(xué)方法：單純形法，圖解法等（2）計算機方法：各種軟件（lingo, matlab，excel等）第9頁/共24頁二、利用二、利用Excel SolverExcel

6、Solver求解線性規(guī)劃問題求解線性規(guī)劃問題第10頁/共24頁如何加載如何加載Excel的的“規(guī)劃求解規(guī)劃求解”安裝office的時候，系統(tǒng)默認的安裝方式不會安裝宏程序，需要用戶根據(jù)自己的需求選擇安裝。下面是加載“規(guī)劃求解”宏的步驟：（1）在“工具”菜單上，單擊“加載宏”第11頁/共24頁（2）在彈出的對話框中的“可用加載宏”列表框中，選定待添加的加載宏“規(guī)劃求解”選項旁的復(fù)選框，然后單擊“確定”。單擊“確定”以后，“工具”菜單下酒會出現(xiàn)一項“規(guī)劃求解”。第12頁/共24頁實例實例11生產(chǎn)計劃問題生產(chǎn)計劃問題某公司最暢銷的3種商品單位利潤不一，A為10元，B為8元，C為9元。不論哪一種商品，其

7、生產(chǎn)過程都需要經(jīng)過“制造”、“測試”、“品管”和“封裝”四個部門，而每種商品在各個部門所耗費的工時也不一樣，如下表。每個部門的可用工時也是有限制的，如下表。每單位所需人工工時（小時）每單位所需人工工時（小時）各部門可用各部門可用工時（小時）工時（小時）部門A產(chǎn)品B產(chǎn)品C產(chǎn)品制造1.120.840.767200測試0.480.680.724100品管0.880.71.046100封裝0.120.440.381800問：如何安排生產(chǎn)，才能使總利潤最大？第13頁/共24頁excel求解結(jié)果：第14頁/共24頁“規(guī)劃求解規(guī)劃求解”各參數(shù)解釋和設(shè)置各參數(shù)解釋和設(shè)置單擊“規(guī)劃求解”按鈕，將會出現(xiàn)以下的規(guī)劃

8、求解參數(shù)的對話框。第15頁/共24頁（1）目標單元格：存放目標函數(shù)的計算值的位置（2）最大值、最小值：在此指定是否希望目標單元格為最大值、最小值或某一特定數(shù)值。如果需要指定書，請在右側(cè)編輯框中鍵入該值。（3）可變單元格：在此指定可變單元格。求解時其中的數(shù)值不斷調(diào)整，直到滿足約束條件并且“設(shè)置目標單元格”框中指定的單元格達到目標值。（4）約束：在此列出了規(guī)劃求解的所有約束條件。（5）最長運算時間：在此設(shè)定求解過程的時間。默認值100（秒），一般可以滿足大多數(shù)小型規(guī)劃求解要求。（6）迭代次數(shù)：在此設(shè)定求解過程中迭代運算的次數(shù)，限制求解過程的時間。默認值100次，基本可以滿足大多數(shù)小型規(guī)劃求解要求。

9、第16頁/共24頁（7）精度：在此輸入用于控制求解精度的數(shù)字，以確定約束條件單元格中的數(shù)值是否滿足目標值或上下限。（8）允許誤差：在此輸入滿足整數(shù)約束條件并可被接受的目標單元格求解結(jié)果與真實的最佳結(jié)果間的百分偏差。這個選項只用于具有整數(shù)約束條件的問題。設(shè)置的允許誤差值越大，求解過程就越快。（9）采用線性模型：當模型中的所有關(guān)系都是線性的，并且希望解決線性優(yōu)化問題時，選中此復(fù)選框可加速求解過程。（10）顯示迭代結(jié)果：如果選中此復(fù)選框，每進行一次迭代都將中斷“規(guī)劃求解”，并顯示當前的迭代結(jié)果。（11）假定非負：如果選中此復(fù)選框，則對于在“添加約束”對話框的“約束值”框中沒有設(shè)置下限的所有可變單元格

10、，假定其下限為0.第17頁/共24頁Excel Excel 求解線性規(guī)劃問題的步驟：求解線性規(guī)劃問題的步驟：1、在電子表格中確定目標單元格、活動單元格，輸入所有參數(shù)；2、利用數(shù)據(jù)組相乘公式（常用函數(shù)里SUMPRODUCT)確定好約束條件的左邊對應(yīng)單元格；3、打開工具欄里的規(guī)劃求解 （1）給定目標單元格、活動單元格，求最大或最??； （2）添加約束條件 （3）選項欄里：線性、非負，確定 （4）確定求解第18頁/共24頁第19頁/共24頁地區(qū)地區(qū)需求量需求量北京150上海225廣州100天津250香港120西安150合計995地區(qū)地區(qū)濟南濟南杭州杭州廈門廈門庫存量400350500表2 倉儲中心庫存

11、總量（單位：臺）實例2運費問題表1 運輸成本（單位：元） 倉儲中倉儲中心心地區(qū)地區(qū)濟南濟南杭州杭州廈門廈門北京5847108上海8746100廣州1213057天津1496683香港62115164西安1282838第20頁/共24頁實例2運費問題 倉儲中心倉儲中心 地區(qū)地區(qū)濟南濟南杭州杭州廈門廈門北京X11X12X13上海X21X22X23廣州X31X32X33天津X41X42X43香港X51X52X53西安X61X62X63假設(shè)各倉儲中心運往各地區(qū)的數(shù)量如下表：第21頁/共24頁實例2運費問題目標函數(shù)：Min Z=58 X11+47 X12+108 X13+87 X21+28 X62+38 X63 約束條件：Subject to X11+X12+X13=150 X21+X22+X23=225 X31+X32+X33=100 X41+X4