線性規(guī)劃與數(shù)學建模簡介教學教材

1、學習 好資料更多精品文檔第十三章線性規(guī)劃與數(shù)學建模簡介【授課對象】理工類專業(yè)學生【授課時數(shù)】6 學時【授課方法】課堂講授與提問相結(jié)合【基本要求】1 、了解數(shù)學模型的基本概念、方法、步驟；2、了解線性規(guī)劃問題及其數(shù)學模型；3 、了解線性規(guī)劃問題解的性質(zhì)及圖解法.【本章重點】 線性規(guī)劃問題 .【本章難點】 線性規(guī)劃問題、線性規(guī)劃問題解的性質(zhì)、圖解法 .【授課內(nèi)容】本章簡要介紹數(shù)學建模的基本概念、方法、步驟，并以幾個典型線性規(guī)劃問題為例，介紹構建數(shù)學模型的方法及其解的性質(zhì)。1數(shù)學建模概述一、數(shù)學建模數(shù)學建模是構造刻劃客觀事物原型的數(shù)學模型并用以分析、研究和解決實際問題的一種科學方法。運用這種科學方法

2、，必須從實際問題出發(fā)，遵循從實踐到認識再實踐的認識規(guī)律，圍繞建模的目的，運用觀察力、想象力的抽象概括能力，對實際問題進行抽象、簡化，反復探索，逐步完善，直到構造出一個能夠用于分析、研究和解決實際問題的數(shù)學模型。因此，數(shù)學建模是一種定量解決實際問題的創(chuàng)新過程。二、數(shù)學模型的概念模型是人們對所研究的客觀事物有關屬性的模擬。例如在力學中描述力、量和加速度之間關系的牛頓第二定律F= ma就是一個典型的（數(shù)學）模型。一般地,可以給數(shù)學模型下這樣的定義：數(shù)學模型是磁于以部分現(xiàn)實世界為一定目的而做的抽象、簡化的數(shù)學結(jié)構。通俗而言，數(shù)學模型是為了一定目的對原型所作的一種抽象模擬，它用數(shù)學式子，數(shù)學符號以及程序

3、、圖表等描述客觀事物的本質(zhì)特征與內(nèi)在聯(lián)系。三建立數(shù)學模型的方法和步驟建立數(shù)學模型沒有固定模式。下面介紹一下建立模型的大體過程：1 . 建模準備建模準備是確立建模課題的過程。這類課題是人們在生產(chǎn)和科研中為了使認識和實踐過一步發(fā)展必須解決的問題。因此，我們首先要發(fā)現(xiàn)這類需要解決的實際問題。其次要弄清所解決問題的目的要求并著手收集數(shù)據(jù)。進行建?；I劃，組織必要的人力、物力等，確立建模課題。2 模型假設作為建模課題的實際問題都是錯綜復雜的、具體的。如果不對這些實際問題進行抽象簡化，人們就無法準確把握它的本質(zhì)屬性，而模型假設就是根據(jù)建模的目的對原型進行抽象、簡化，抓住反映問題本質(zhì)屬性的主要因素，簡化掉那些

4、非本質(zhì)的次要因素。有了這些假設，就可以在相對簡單的條件下，弄清各因素之間的關系，建立相應的模型。合理的假設是建立理想模型的必要條件和基本保證。如果假設是合理的，則模型切合實際，能解決實際問題；如果假設不合理中或過于簡化，則模型與實際情況不符或部分相符，就解決不了問題，就要修改假設，修改模型。3 構造模型在模型假設的基礎上，開始構建數(shù)學模型。首先分析變量類型，恰當使用數(shù)學工具。一般而言，如果實際問題中的變量是確定型變量，數(shù)學工具可采用微積分、微分方程、線性或非線性規(guī)劃、投入產(chǎn)出、確定性庫存論等。如果變量是隨機變量，數(shù)學工具可采用概率與統(tǒng)計、排隊論、對策論、決策論、隨機微分方程、隨機性庫存論等。其

5、次，抓住問題本質(zhì)，簡化變量之間的關系?？梢哉f，數(shù)學的任一分支在構造模型時都可能有用，而同一實際問題也可以構造不同的數(shù)學模型。一般而言，在能夠達到建模目的前提下，所用的數(shù)學工具應力求簡單、易解，但要保證模型的解的精確在允許的范圍內(nèi)。4 模型求解不同的模型要選擇或設計不同的數(shù)學方法和算法求解，許多模型還可以通過編寫計算機程序軟件包，借助計算機快速完成對模型的求解。5 模型分析對模型的求解結(jié)果進行分析，主要包括穩(wěn)定性分析，參數(shù)的靈敏度分析，誤差分析等。通過分析，若發(fā)現(xiàn)不符合建模要求，就要修改或增減建模假設條款，重新構造模型，直到符合要求。若模型符合要求，則可以對模型進行評價是、預測民、優(yōu)化等方面的探

6、析，力爭得到最優(yōu)模型。6 模型檢驗對于經(jīng)過分析后符合要求的模型，還要把它放回到實際對象中去進行檢驗，看它是否符合實際，能否解決相應的實際問題。若不符合實際，就要修改前提假設，重新建模，重新分析，直到獲得符合實際的模型。7 模型應用建模最終目的，是用模型來分析、研究和解決實際問題。因此，一個成功和數(shù)學模型必須能夠在實踐中得到成功的應用，甚至形成一套科學和理論。圖 13 1學習-好資料是上述各步驟的直觀圖:圖13 1數(shù)學建模步驟示意圖一、數(shù)學模型的分類數(shù)學模型按照不同的分類標準有許多種類：1 .按照模型的數(shù)學方法分，有幾何模型、代數(shù)模型、圖論模型、微分方程模型概率模型、最優(yōu)控制模型、隨機模型等等。

7、2 .按模型的特征分，有靜態(tài)模型和動態(tài)模型，確定性模型和隨機模型，離散模型和 連續(xù)性模型，線性模型和非線性模型等。3 .按模型的應用領域分，有人口模型、交通模型、經(jīng)濟模型、生態(tài)模型、資源模型、 環(huán)境模型等。4。按建模的目的分，有預測模型、優(yōu)化模型、決策模型、控制模型等。5.按奪模型結(jié)構的了解程度分，有白箱模型、灰箱模型、黑箱模型等。2線性規(guī)劃問題及其數(shù)學模型線性規(guī)劃作為運籌學的一人重要分支，是研究較早，理論較完善，應用最廣泛 的一門科學。它所研究的問題主要包括兩個方面：一是在一項任務確定后，如何以 最低限度和成本（如人力、物力、資金和時間等）去完成這一任務；二是如何在現(xiàn) 有條件下進行組織和安排

8、，以完成更多的工作。因此，線性規(guī)劃就是求一組變量的 值，使它滿足一組線性式子，并使一個線性函數(shù)的值最大（或最?。┑臄?shù)學方法。一、運輸問題例1設有Ai, A2兩個香蕉基地，產(chǎn)量分別為 60噸和80噸，聯(lián)合供應Bi, B2, B3三個銷地的銷售量經(jīng)預測分別為 50噸、50噸和40噸。兩個產(chǎn)地到三個銷地 的單位運價如下表所示：表131運價表（單位：元/噸）地BiB2B3Ai600300400A2400700300問每個產(chǎn)地向每個銷地各發(fā)貨多少，才能使總的運費最少?解 (1)在該問題中，所要確定的量是各產(chǎn)地運往各銷地的香蕉數(shù)量，即決策變量是運輸量。設Xj(i=1,2; j =1,2,3)分別表示由產(chǎn)地

9、Ai運往銷地Bi的數(shù)量。(2)在解決問題的過程中，要受到如下條件限制，即約束條件:各產(chǎn)地運出的數(shù)量應等于其產(chǎn)量，即6080+ + X11 X12 X13 一+ + -匚 X 21 X 22 X 23各銷地運進的數(shù)量應等于其當?shù)仡A測的銷售量，即Xl+X21=50 X12+X22=50-X13*X23=40從各產(chǎn)地運往各銷地的數(shù)量不能為負值，即Xij -0(i =1,2; j =1,2,3)該問題的目的是運價最低，所以運價是目標函數(shù)，即S = 600 X11 +300X12 + 400 X12 + 400 X21 + 700 X22 + 300 X23 因止匕，該問題的數(shù)學模型為：求 min S

10、-600X11 300X12 400X13 400*1 700X22 300X23廠 Xii*Xi2*Xi3=60X21 + X22 + X23 = 80結(jié)束條件XiX21=50X12 + X22 = 50 X/X23 =40例1的一般形式是：設某種物資有m個產(chǎn)地A，A2,Am產(chǎn)量分別為 a1,a2,am5有n個銷地BB,B,銷量分別為b,b“.b(噸)。如果由 產(chǎn)地A運往銷地Bj的單位運價為Cj (元/噸)，在產(chǎn)銷平衡的情況下，應如何調(diào)運才能使運費最??？解 設Xj表示由產(chǎn)地Ai運往銷地Bj的數(shù)是(i=l, m； j=1,2,n)則該問題數(shù)學模型為：求變量Xj的一組值，使它們滿足X xii +

11、xi2+xin=ai+ + + Xm1 Xm2 . Xmn 一 HmIXli+X2lt.*Xm1=blX24X22 +4 Xm2=b2Xin+X2n * +Xmn=bnXj 0(i=i,2,.m;j=i2.n),并使目標函數(shù)S=CiiXii+Ci2Xi2+CmnXmn的值最小。二、生產(chǎn)組織與計劃問題例2設某用a，a，,Am種原料，生產(chǎn)B1，B2,Bm種產(chǎn)品，其中Bj種產(chǎn)品 每單位需要 A，A2,Am原粉分別為；而該廠現(xiàn)有原料 ai，a2，,amj；的數(shù)量分別為 bi，b2,bm，Bi，B2,Bn各種產(chǎn)品每單位可是利潤分別為Ci，C2,Cn。在該廠產(chǎn) 品全部能銷售情況下，應如何組織生產(chǎn)，才能使該

12、企業(yè)獲得最大？解 設生產(chǎn)產(chǎn)Bj中數(shù)量為Xj(j =i,2,n)，則此問題的數(shù)學模型為：求一組變量的值，使?jié)M足廠aiiXi+ai2X2+十 anH2iXi+a22X2+. .ta2nXn-b2結(jié)束條件-amiXi am2 X2 . amn Xn - bm lXj 之O(j=i, 一口)，并使目標函數(shù)S=CiXi+C2X2+CnXn的值最大。三、配料問題例 設有A1,Am種原料，配制含有幾種成分 B1，B2,Bn的產(chǎn)品，要求產(chǎn)品中各 種成分的含量不低于a1，a2，an ；不高于b1，b2，,bn ； Bj種成分在A種原料中的 單位含量為，各種原料的單位價格依次為d1，d2，dm.問如何調(diào)配原料，才

13、能使產(chǎn)品 符合要求，又使成本最低？解 設xi表示每單位產(chǎn)品中原料 Ai的使用量（即決策變量），i =1,2,m,則數(shù)學模型 為：求一組變量的值，使其滿足a al -Cl1 Xi +C21 X2 +. + CmlXm - bla2 -C12X1 +C22 X2. +Cm2Xm-b2約束條件1 ）an -C1nX1+C2n X2 + .+CmnXn - bnX1 + X2+Xm=1I Xi ,（i =1,m）并使目標函數(shù)S=d1X+dmXm最小。二、線性規(guī)劃問題數(shù)學模型的一般形式和標準形式上面我們建立了經(jīng)濟領域中常見的實際問題的數(shù)學模型，盡管這些實際問題本身是多種多樣的，但是它們的數(shù)學模型卻具有相

14、同的特征：要確定某些變量（決策變量）的一組值，使得在確定的確定的約束條件下，目標函數(shù)是取得最大值或最小值。其 中，約束條件是決策變量的線性方程或線性不等式。目標函數(shù)是決策變量的線性函 數(shù)。因此，我們把這種規(guī)劃問題稱為線性規(guī)劃問題。同時，我們可以得到對于一個 線性規(guī)劃問題，其數(shù)學模型應具有如下形式：求 max（或 min）S=C1X1 C2X2 CnXna aux+2x2+ainXnb（或至b，或=9a2lXl +a22X2+ + a2nXn b2（或至 b2,或加0(j =i,2,n)線性規(guī)劃問題的標準（i3.i ）也可寫成矩陣形式minS =CXAX =bs.tLx -0其中 C =（C，C

15、2,，Cn），XX=廣2.JX3-b，B= b2- ai2 a侵amA= a21a22a2 n.ami am2 amn -更多精品文檔學習-好資料對于線性規(guī)劃問題的一般形式，可以按如下方法化成標準形：(1)如果線性規(guī)劃問題是求目標函數(shù)的最大值，即求maxS = ClX1+cnxn,只要令S = -S ,即可化為求目標函數(shù)的最小值，即求 m iSnC1X1 C2X2CnXn(2)如果某個約束條件為線性不等式，則可將其化為線性議程式的形式。設第k個約束條件為akiXl +ak2X2 +akmXn蕓bk :則加入一個新變量，將其約束條件改為：akiXl ak2X2aknXn Xn k =bk這個所加

16、的變量稱為松弛變量。若第l個約束條件為：aMXi +ai2X2+ ainXn -b則加入一個新變量，將上述約束條件變?yōu)椋篴ilXl ai2X2ainXn Xnl =bl(3)若對某變量沒有非負限制，則引進兩個非負變量X，j之0，X”j20令Xj = Xj X：代入約束條件和目標函數(shù)，可化為全部變量都有非負限制。例4 將下列線性規(guī)劃模型化為標準形m aSX-2Xi 3X2X2+X2-5S.tj3Xi X22Y?0，Y2為非負限制X1 X2X“2 且 xFQxy0解引入松馳變量X30，X40,令S=-S，X2 = X2更多精品文檔學習-好資料即可得標準形式如下m iSn2Xi-3x2 3xXi+2

17、X22X %X3=5S.t 3Xix 2 x 2 X4 =2X2-0，X 2-0，Xj-（j =1,3,4）3線性規(guī)劃問題解的性質(zhì)及圖解法一、線性規(guī)劃問題的解的性質(zhì)對于線性規(guī)劃問題(13.2):minS =CX1.幾個概念(D 口仃解：滿足線性規(guī)劃問題所有約束條件的向量 x =(x1(0)，Xn(0)T稱為可行解，所有可行解構成的集合稱為可行域，記為 R,則R= x| Ax = b,x2 0(2)基礎可行解：若可行解X=0,或X的非零分量所對應的系數(shù)列向量線性無關， 則稱X為基礎可行解。(3)最優(yōu)解：使目標函數(shù)取最小值的可行解稱為最優(yōu)解。 (4)基礎最優(yōu)解：使目標函數(shù)取最小值的基礎可行解稱為基

18、礎最優(yōu)解。 (5)門”：若連接n維點集S中任意兩點Xl，X2的線段仍要S內(nèi)，則稱S為凸集。換言之，若x|x = ： X1 1-： X2，0- -1，Xi，X2 S : S，S En則稱S為凸集。更多精品文檔學習-好資料（6）強點：若凸集S中的點x,不能成為S中任何線段的內(nèi)點，則稱x為S的極點，換言之，若對任意不同兩點 x1,x2e S,不存在a（0a1）,使x =二 x1 （1 ）X2 三 S則稱x為S的極點。例如，圓周上的點都是極點。s（7）門”學:設xi = En,實數(shù)九0=1,2,s,且九i=1,則稱.i 1x = 1x1 x2s s為點x1, x2, , xs的一個凸組合。2. 線性規(guī)

19、劃問題的解由線性代數(shù)求解議程組的方法及上述概念可知，線性規(guī)劃問題（ LP）的解有如下幾種情況：ff.有唯一最優(yōu)解有可行解有無窮多最優(yōu)解無最優(yōu)解無可行解3. 線性規(guī)劃問題解的性質(zhì)性質(zhì)1線性規(guī)劃問題（LP）的可行域R = x|AX=b,X20 是凸集。性質(zhì)2可行域R中的點x是極點的充要條件是x是基礎可行解。性質(zhì)3若（LP）問題的可行域Rw，則R至少有一極點，且極點的個數(shù)有限。性質(zhì)4最優(yōu)值可以在極點上達到。這幾條性質(zhì)實際上給我們指出了線性規(guī)劃問題求解的思路和方向：由于線性規(guī)劃問題的最優(yōu)解一定能在可行解集的極點達到，而極點的數(shù)目中有限的。所以，總更多精品文檔學習-好資料可以想辦法在有限的極點中經(jīng)過有限

20、次尋找，得到最優(yōu)解。因而，就有了求解線性 規(guī)劃問題的圖解法和單純形法。由于篇幅所限，下面僅介紹圖解法的應用。有興趣 的讀者可以學習一下單純形法。二、圖解法（又稱幾何法）圖解法是對于只是兩個決策變量的線性規(guī)劃問題，在平面內(nèi)建立直角坐標系， 使每個決策變量的取值在一個數(shù)軸上表示出來，可行解就成為平面上的點，可 行域就是平面上的一個共域，從而最優(yōu)解必定是在這個平面區(qū)域內(nèi)（包括邊界 上）的點。根據(jù)目標函數(shù)在這個平面區(qū)域內(nèi)的取值找出使目標函數(shù)取得最優(yōu)值 的點（即最優(yōu)解）。圖解法便于我們理解和了解線性規(guī)劃問題的一些概念、理論及解的一些特性， 也為我們進一步學習單純方法提供一個直觀圖形。例5 求解線性問題m

21、 iS n 7 x1 + 5x2xi +2x2-28S.tJ4xi + X242Xi，X2 0解 第一步，在平面直角坐標系OX1X2上繪出約束條件圖（圖13 2）畫出這條直線 X1+2X2=28,再定出X1+2X2W28區(qū)域。把（0, 0）代入不等式得0+2 028,所以，原點所在平平面及直線本身就是X1+2X2M28代表的區(qū)域。畫出4Xl + X2=42這條直線，定出4Xl+X2E42代表的區(qū)域，有（0, 0）代入不等式得0 4 + 042所以，4X1 + X2W42代表的區(qū)域是包括原點的下半平面與直線本身。4Xi X2 = 42定出X1之0,X2之0的區(qū)域，它就是第一象限。從圖X X7X1 5X2=106學習-好資料13 2看出，滿足全部約束條件的點所構成的區(qū)域（即7 Xi 5x2 50可行域）,就是凸多邊形OABC。X1 2X1 = 28第二步，繪制目標函數(shù)圖形。對于目標函數(shù) S = 7X1+5X2、將S看作參數(shù)，即得到一簇平行直線（圖13-2中虛線所.示），直線上每一點的目標函數(shù)值為 So由圖可見，直線離飛原點越遠，S值越大，我們尋找的