管理定量分析-規(guī)劃分析

1、規(guī)劃分析第8章第8章 規(guī) 劃 分 析通過本章的學習，讀者應理解線性規(guī)劃在實際生活中的應用，掌握線性規(guī)劃的求解方法圖解法及單純形法；通過實例分析掌握目標規(guī)劃的數學模型特點及其簡單求解方法圖解法，理解目標規(guī)劃與線性規(guī)劃問題的關系。(1) 理解線性規(guī)劃的數學模型及基本概念：基、基變量、非基變量、可行解、可行域、最優(yōu)解、三大基本定理及其含義。(2) 掌握線性規(guī)劃的標準形式三大部分：目標函數、約束條件和決策變量。(3) 理解線性規(guī)劃的解法圖解法。(4) 掌握線性規(guī)劃的解法單純形法。(5) 掌握目標規(guī)劃的數學模型。(6) 理解目標規(guī)劃的解法圖解法。本章導讀線性規(guī)劃(Line Programming)是運籌

2、學的一個重要分支。線性規(guī)劃問題是理論較為完整、應用極其廣泛的一門數學規(guī)劃學科。1939年，前蘇聯科學家兼經濟學家康托洛維奇發(fā)表了生產組織與計劃中的數學方法一書，第一次詳細地介紹了線性規(guī)劃問題。1947年，美國貝爾電話公司工程師G.B.Dantzig提出了單純形法，線性規(guī)劃在理論上趨于成熟，在實際應用中日益廣泛與深入。G.B.Dantzig對線性規(guī)劃理論的提煉和算法改進做出了卓越的貢獻。 線性規(guī)劃繼單純形法提出經歷了幾十年的發(fā)展，其應用日趨增多，已滲透到經濟活動的各個領域，特別是電子計算機能處理成千上萬個約束條件和決策變量的線性規(guī)劃問題之后，線性規(guī)劃的適用領域更為廣泛，從解決技術問題的最優(yōu)設計到

3、工業(yè)、農業(yè)、商業(yè)、交通運輸、軍事、經濟計劃和管理決策等領域也發(fā)揮著各自的作用。線性規(guī)劃成為重要的現代管理方法之一。1961年，查恩斯(A.Charnes)與庫伯(W.W.Cooper)繼丹捷格之后提出了目標規(guī)劃。艾吉利(Y.Ijiri)提出了用優(yōu)先因子來處理多目標問題，使目標規(guī)劃得到發(fā)展。近10多年來，斯·姆·李(S.M.Lee)與杰斯開萊尼(V.Jaaskelainen)應用計算機處理目標規(guī)劃問題，使目標規(guī)劃在實際應用方面比線性規(guī)劃更廣泛，更為管理者所重視。目標規(guī)劃在這里指的是線性目標規(guī)劃，其一個很大的優(yōu)點就是非常靈活，適用于許多方面，既適用于一個大目標附帶有許多從屬目標

4、的問題，也適用于許多目標并附有許多從屬目標的問題，而且目標的計量單位不像線性規(guī)劃那樣只是單一的，而是可以多種多樣的。8.1 線 性 規(guī) 劃8.1.1 線性規(guī)劃問題及其數學模型線性規(guī)劃所解決的問題主要分為兩類：一類是在人力、物力資源一定的情況下，如何規(guī)劃利用這些現有的資源來完成最多的任務；另一類是在任務確定的情況下，如何統(tǒng)籌規(guī)劃，如何利用最小的人力、物力資源來完成這個確定的任務。一般來說，用線性規(guī)劃解決一個實際問題時，首先根據待要解決的線性規(guī)劃問題，分析問題所要實現的目標及所存在的約束條件，建立線性規(guī)劃的數學模型；其次對該模型利用計算機求解；再次檢驗解的合理性；最后付諸于實踐。下面將通過幾個實例

5、來說明線性規(guī)劃問題建模的思路及其在實際問題中的應用，最后引出線性規(guī)劃的標準模型。【例8-1】 某工廠計劃生產和兩種產品，已知生產單位產品所需的兩種原材料見表8-1。表8-1 生產單位產品所需的兩種原材料產 品現有原材料數量(kg)原材料原材料A原材料B423112050又已知每生產單位產品和分別可獲利50元和30元，問應如何安排生產該工廠才能獲得最大利潤？分析：(1) 確定未知變量，設分別表示產品和的產量。(2) 該工廠的目標是使總利潤最大，若用z表示利潤，則，總利潤最大記成。(3) 各種原材料數量是有限的，由原材料的限量可得到以下不等式：綜上所述，可得該問題的數學模型：【例8-2】 某企業(yè)生

6、產兩種混合配料A和B，每100kg的成本分別為110元和80元。每種產品含三種營養(yǎng)成分，但它們的含量各不相同。在每100kg混合配料中各種營養(yǎng)成分的含量見表8-2。表8-2 每100kg混合配料中各種營養(yǎng)成分的含量混 合 配 料混合配料A混合配料B營養(yǎng)成分營養(yǎng)成分甲(kg)營養(yǎng)成分乙(kg)營養(yǎng)成分丙(kg)1034239現要獲得各種營養(yǎng)成分的總量為：營養(yǎng)成分甲至少20kg；營養(yǎng)成分乙至少18kg；營養(yǎng)成分丙至少36kg，問滿足這些要求的最低成本為多少？分析：(1) 確定未知變量，設(100kg)分別表示混合配料A和B的需要量。(2) 該企業(yè)的目標是使總成本最小，若用z表示成本，則，總成本最小

7、記成。(3) 各種營養(yǎng)成分數量有最低標準，由各營養(yǎng)成分的限量可得到以下不等式：綜上所述，可得該問題的數學模型：一般來說，線性規(guī)劃的數學模型的一般形式為：凡能表示為以上形式的問題統(tǒng)稱為線性規(guī)劃問題。線性規(guī)劃問題具有以下特征。(1) 線性規(guī)劃問題的目標能表示為最大化或最小化的問題。例如，求最小成本或人力、投資等，最大化利用材料儲備，實現企業(yè)的最大利潤等問題。(2) 問題的解可以用一組變量來表示，而且解的個數不只一個，即必須要有選擇的可能性。(3) 要達到的目標是有限制條件的。(4) 問題的目標和限制條件都能表示為線性表達式。8.1.2 線性規(guī)劃的標準形式為了討論問題方便，規(guī)定線性規(guī)劃問題的標準形式

8、為：實際中碰到各種線性規(guī)劃問題的數學模型都應變化為標準形式后求解。將非標準形式線性規(guī)劃化為標準形式線性規(guī)劃時可能出現以下幾種可能情況，處理的方法有以下幾種。1. 決策變量(1) 決策變量有非正約束，即，令，于是新變量。(2) 決策變量有上下界，即，可將上下界分別處理。令，則新變量且。這時滿足了非負要求，上限約束作為新的約束條件按照相應方法轉化為等式。(3) 決策變量符號不受限制，即可以為一切實數。令，其中，。2. 目標函數目標函數為最小化，即。令，則得到。3. 約束條件(1) 約束條件為小于或等于形式，即存在約束，這時在不等式左端加上一個非負的新變量即可化為等式，即，新增變量為松弛變量。(2)

9、 約束條件為大于或等于形式，即存在約束，這時在不等式左端減去一個非負的新變量即可化為等式，即，新增變量為松弛變量。(3) 某一等式約束中存在，即存在，令，即在該不等式兩邊同乘以-1變?yōu)椋??！纠?-3】 將下述線性規(guī)劃問題化為標準形式。解：(1) 首先分析決策變量，令，其中，。(2) 在第一不等式兩邊乘以-1得：。在第二不等式左邊加上松馳變量，化為等式：，其中。在第三個不等式左邊減去松馳變量，化為等式：，其中。(3) 在目標函數兩端同乘以-1，同時令，得該線性規(guī)劃的標準形式為：8.1.3 線性規(guī)劃的圖解法圖解法簡單直觀，有助于了解線性規(guī)劃問題求解的基本原理?，F用圖解法求解例8-1，即求解線性規(guī)劃

10、：如圖8.1所示：在以為坐標軸的直角坐標系中，非負條件指第一象限；約束條件代表以直線為邊界的左下方的半平面；約束條件代表以直線為邊界的左下方的半平面。同時滿足例8-1中三個約束條件的點必然位于圖8.1中多邊形OABC內(包括邊界點)，因而此區(qū)域為例8-1的可行解的集合，稱為可行域。再分析目標函數，它可表示斜率為-5/3的一簇平行線，如圖8.2中就是其中一條線，當Z值逐漸增大時，直線向右上方移動，使Z值在可行域OABC的頂點B達到最大值。B點坐標(15，20)即為該線性規(guī)劃的最優(yōu)解，即，可計算出最優(yōu)值：。圖8.1 例8-1的可行域 圖8.2 例8-1的最優(yōu)解8.1.4 單純形法在介紹單純形法之前

11、，先引入以下幾個基本概念。(1) 基：設是約束方程組的系數矩陣，其秩為m。B是矩陣A中的階非奇異子矩陣()，則稱B是線性規(guī)劃問題的一個基。設：(2) 基向量：基B的列向量稱為線性規(guī)劃問題的基向量。基B中共有m個基向量。(3) 基變量：與基向量相對應的變量被稱為基變量，否則稱為非基變量。在單純形法求解線性規(guī)劃基可行解過程中令所有非基變量為零?，F以例8-1為例介紹單純形法，即求解線性規(guī)劃問題：(8-1)該線性規(guī)劃問題的標準形式為： (8-2)容易看出的系數構成一個基：，因此為基變量，為非基變量。基變量可用非基變量表示為： (8-3)將式(8-3)代入目標函數式(8-1)得： (8-4)令非基變量，

12、由式(8-3)可得一個基本可行解：，目標函數值。分析目標函數表達式(8-4)，的系數都是正數，因此，非基變量中任意一個變量取值從零變?yōu)檎?變成基變量)，都可能使目標函數值增大，這就是所謂的基變換。為使目標函數值增加幅度最大，選取系數最大的非基變量作為入基變量。下面確定出基變量。由于作為入基變量，仍然是基變量，即，代入式(8-3)可得到：即，也就是說，當新基變量的值增大時，原基變量的值最先降為零，因此選為出基變量。上述基變換過程用單純形表表示見表8-3。表8-3 例8-1初始單純形表503000比值004231100112050120/4=3050/2=25503000表中第一行列出了線性規(guī)劃

13、標準形式中所有變量在目標函數中對應的目標系數，第二列為所有基變量，第一列為基變量在目標函數中對應的目標系數，中間部分數據為各變量在約束條件中對應的約束系數。最下端一行數字對應式(8-4)中各變量系數，又稱為檢驗數，也可通過公式，計算，可以證明基變量對應的檢驗數為零。線性規(guī)劃問題取得最優(yōu)解的判定條件為：若所有檢驗數，所對應的基本可行解為最優(yōu)解。箭頭表示了入基變量及出基變量的選取方法，其中入基變量的選擇方法是：如果存在正的檢驗數，選取最大的正檢驗數對應的變量作為入基變量(選取正系數最大的非基變量作為入基變量，使目標函數值增加幅度最大)，即。出基變量的選擇依據是選取最小的比值對應的基變量作為出基變量

14、(新基變量的值增大時，原基變量的值最先降為零)，其中比值。經過上述基變換，新的基變量為，非基變量為。根據式(8-3)得出新的基變量表達式： (8-5)將式(8-5)代入目標函數表達式(8-1)，得： (8-6)令非基變量為零，得到另一個基本可行解：，目標函數值。從目標函數表達式(8-6)可以看出，的系數仍為正值，說明目標函數值還可能繼續(xù)增大，因此需再次進行基變換，方法如前所述。對應單純形表見表8-4。表8-4 例8-1單純形表基變換過程一503000比值0500111/210-21/2202520/1=2025/1/2=50050-25表中數字變化方法為，表8-3入基變量和出基變量所在行和列交

15、叉處元素為主元(如表中方框中數字)，對表格中約束系數進行基本行變換，即將主元變?yōu)?，主元所在列其他元素變?yōu)?，即得表8-4。根據線性規(guī)劃問題取得最優(yōu)解的判定條件：若所有檢驗數，所對應的基本可行解為最優(yōu)解。因此表8-4中所得基本可行解不是最優(yōu)解，再次進行基變換得單純形表，見表8-5。表8-5 例8-1單純形表基變換過程二503000305001101-1/2-23/2201500-5-151 350這時滿足線性規(guī)劃最優(yōu)解判定條件，即所有，因此，為原線性規(guī)劃問題的最優(yōu)解，最優(yōu)值：。8.2 目 標 規(guī) 劃目標規(guī)劃(Goal programming)是運籌學中非常重要的一個分支，最早由美國管

16、理學家彼特德魯克(Peter F. Drucker)于1954年正式提出，現已由對管理人員進行的目標管理發(fā)展成為對企業(yè)各項任務的目標管理，已成為一種廣泛使用的目標管理方法。線性規(guī)劃有一致命的弱點，就是目標單一，即尋求某一個目標之最大或最小，這和現代經濟社會的要求很不一致。目標規(guī)劃最重要的特點是強調系統(tǒng)性，采用多目標的統(tǒng)籌安排來替代單目標的制定，通過尋求各目標與成果之間最小差距來達到生產過程中的多目標成果；用“令人滿意”的概念來替代“最優(yōu)”的傳統(tǒng)概念，這些都與線性規(guī)劃有很大的不同。8.2.1 目標規(guī)劃的數學模型【例8-4】 在例8-1中如果由于某種原因廠長要求：(1) 總利潤不小于1 

17、200元；(2) 充分利用原材料B。試建立該問題的數學模型。分析：(1) 確定未知變量，設仍分別表示產品和的產量。(2) 該工廠的目標是使總利潤不小于1 200元，從例8-1的最優(yōu)解可知該工廠可實現的最大總利潤為1 350元。為此引入正負偏離變量，其中：高于所定目標的數量低于所定目標的數量則該約束可表示為(3) 充分利用原材料B可表示為。原材料A隱含約束不變，仍為。(4) 確定新的目標函數若決策者想準確實現目標，目標函數形式為：。、為該目標中相應的偏離變量。若決策者想不超過某一目標，目標函數形式為：。若決策者想不低于某一目標，目標函數形式為：。例8-4中第一目標目標函數形式

18、為：。第二目標目標函數形式為：。按照決策者要求，分別賦于這兩個目標優(yōu)先系數p1和p2，并規(guī)定p1>>p2，表示p1比p2有更大的優(yōu)先權。該問題的目標函數為：。綜上所述，可得該問題的數學模型：8.2.2 目標規(guī)劃的圖解法【例8-5】 圖解法求解例8-4，即求解目標規(guī)劃：對只具有兩個決策變量的目標規(guī)劃的數學模型，可以用圖解法來求解。由于式(4)變量為非負約束，在平面直角坐標系第一象限內做各約束條件。約束條件(3)的作圖與線性規(guī)劃問題相同，代表圖8.3中以直線為邊界的左下方半平面；做約束(1)時，先令，做相應的直線，然后在直線旁標上，如圖8.3所示，表明該約束條件可以沿所示的方向平移。考

19、慮具有優(yōu)先因子的目標，在目標函數中要求實現，從圖中可以看出，滿足的區(qū)域位于直線的右上方半平面。同理可以分析約束條件(2)所代表區(qū)域為直線2x1+x2=50上位于第一象限內所有的點。約束條件(3)代表區(qū)域為直線4x1+3x2=120的左下方平面。綜合分析上述約束條件，得出該目標規(guī)劃問題的解為虛線段AB上所有的點。圖8.3 例8-6 可行域及最優(yōu)解8.3 案例應用分析應用線性規(guī)劃方法輔助高校經濟決策1【案例說明】在社會主義市場經濟條件下，高等學校在辦好本科和研究生教育的同時如何發(fā)揮學科優(yōu)勢，利用學校現有房屋、設備、場地、科技和人才開展對外服務，提高經濟效益已成為高校管理決策中的重要問題。一切生產過

20、程都要發(fā)生活勞動和物化勞動的消費，精神產品和物質產品一樣都有一個成本問題，對外服務發(fā)生的支出應從對外服務收入中獲得補償，如果不注重這部分成本的計算，就可能會發(fā)生擠占預算撥款或發(fā)生純收入不“純”的問題。段海艷. 提升高校財務管理水平的途徑D . 西安：西北工業(yè)大學，2003.因此高校開展對外服務之前都要對其成本進行測算，定出其服務價格，比如一個班國家批準計劃招收學生30名，而教室可坐40名學生的情況下，不增加師資、教室再招10名插班生，僅有增量活動的追加成本，便可降低收費標準，招收10名插班生的收費價格在市場同行業(yè)學校中是有競爭力的。但是在對外服務項目中有很多復雜的因素要考慮，而利用線

21、性規(guī)劃可以解決這種成本最小、價格最優(yōu)、利潤最大的問題測算?！景咐治觥?. 分析資料用線性規(guī)劃解決對外服務成本測算問題可按以下三步進行。(1) 提出問題。從高校管理與決策的立場出發(fā)，研究對外服務各項目方面的成本支出、資金分配及使用問題，當然也可依本單位的業(yè)務性質及管理的需要擬定對象。(2) 建立線性規(guī)劃模型。線性規(guī)劃模型是用數學符號和函數關系式來描述研究對象各因素之間數量上本質聯系的數學表達式。線性規(guī)劃模型一般由以下三要素構成: 決策變量：即決策者對問題需要考慮和控制的因素，如招收學生數量多少的確定，需要考慮教室、食堂、學生宿舍容納數量，圖書資料可供借閱人次，基礎及專業(yè)教師等因素，即一組未知數

22、。這些因素可記為或。 約束條件：即決策者為實現目標函數最優(yōu)、最大或最小的一些限制條件，如學校的教職工人力限制、校舍限制、教學儀器設備的限制等?？山⑷缦录s束條件： 目標函數：即決策者欲達到的最優(yōu)目標與決策變量之間相互關系的數學表達式。它是要求實現最大化或最小化的問題。如學校在現有條件下辦學規(guī)模最優(yōu)、效益最大；或學校在現有條件下對外服務支出成本最低利潤最大；即目標函數達到最大值或最小值。目標函數如下：。(3) 求解線性規(guī)劃模型。即根據建立的模型采用單純形法求出使目標函數值最大或最小的各決策變量的數值作為安排工作的參考。2. 建立該問題的數學模型，測算學校招生結構下面將建立該問題的數學模型并用單純

23、型法求解，再根據求得的決策變量的值來說明線性規(guī)劃的具體運用。設為國家任務學生數；為全脫產成人教育或定向生；為自考或者函授生。那么，依前面給定的目標函數，該校每年所得的收入應該是：。上式中是可以變化的，是根據該校在校學生歷史、當前和將來的情況測算的各類學生數，稱它為決策變量。一旦的數值決定下來，Z也就決定下來了。上式中變量前的系數為收費和撥款標準，假設類學生每年撥款約3 000元加學雜費2 000元，合計5 000元，得到收款額；類學生交學雜費3 000元，得到收款額3 000；類學生交學費1 000元，得到收款額1 000。

24、在這個問題中，決策變量的取值并不是完全自由的，而是受到一些變化中的條件的制約。這些限制條件為問題的約束條件。設有如下約束條件：(1) 校舍能力限制。由于學生食堂、宿舍、教室建筑平米數的限制，能容納學生數量也受限制，假定上例能容納全日制學生3 000名，約束條件：。(2) 師資力量的限制。由于學生在校學習的課程及門數與教師人數及專業(yè)有關，與基礎課與專業(yè)課的搭配結構有關，故對上例做如下假設：在校教師約210人，學生人數為每班50人；任課方式有單班課和合班課，依工科本、?？频那闆r，學生平均每屆應學課程為20門課，平均每年完成為5門課。另外，3、4個班的合班課為基礎課，占整個上課比例的5%或

25、10 %；2個班的合班課為專業(yè)基礎課，占整個上課比例的20%、30%或40%；1個班的單班課為專業(yè)課，占整個上課比例的70%、50%或40%。于是，有如下約束條件：簡化為：。(3) 后勤支出能力限制。由于在校生需使用水、電、暖等，其各類學生消耗成本不一樣，上例按類每生每年消耗700元，類每生每年消耗500元，類每生每年消耗300元，水電暖耗費取為250元，則約束條件為：(4) 受國家任務限制。由于目前我國培養(yǎng)本?？粕菄医涛逻_培養(yǎng)任務，而建校規(guī)模是按教育發(fā)展目標建立的，上例國家任務為1 900，則約束條件：。至此可建立以下模型 (max表示最大，s.t.表示約束條件)：3. 求解

26、及結果分析用單純形法求解得：最優(yōu)解，；最優(yōu)值。以上求得最優(yōu)解為：國有任務類學生1 900名；全日制成教或定向生1 100名；函授生600名；其收入值為1 340萬元。依此，學校在完成國家任務每年培養(yǎng)1 900名本科生的同時，又可培養(yǎng)定向生1 100名，函授生600名，扣除本科生的收入值950萬元(1 900×5 000)，可在不增添設施的前提下多收入390萬元。例中設定的系數隨著測算目的和時間的變化應做相應的調整。在不同的條件下變動其值又可得出變動后的最優(yōu)值，這就為管理決策提供了較為堅實的依據。以上用單純形法測算學

27、校某個時點上辦學招生方面的結構和收入情況，用此方法還可預測不同時期不同情況的辦學、科研、后勤服務等結構及收入值，若使用圖解法、特殊模型法亦可編成應用程序輸入計算機，則對不同的約束條件，即可求得優(yōu)化值，供決策參考，使用很方便，并能提高學校財務管理決策的質量和工作效率。本 章 小 結本章第一部分通過實例引出了線性規(guī)劃的建模思路及數學模型；第二部分介紹了線性規(guī)劃問題的標準形式及一般線性規(guī)劃問題化為標準形式的方法；第三部分介紹了求解線性規(guī)劃問題的圖解法，圖解法簡單直觀并反映了線性規(guī)劃的求解原理，但其只適用于含有兩個或三個變量的線性規(guī)劃問題；第四部分介紹了線性規(guī)劃問題的單純形解法，通過案例簡單介紹了該方法的求解過程及原理，給出了單純形表的變化過程；最后介紹了目標規(guī)劃的數學模型及圖解法，線性規(guī)劃的缺點就是目標單一，在一組約束條件下，求某一個目標之最大或最小，這和現代經濟社會的要求很不一致，目標規(guī)劃一個很大的優(yōu)點就是非常靈活，適用于許多方面。習 題1. 試建立下列問題的數學模型：(1) 某廠生產甲、乙兩種產品