線性規(guī)劃與數(shù)學(xué)建模簡(jiǎn)介教學(xué)教材

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

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

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

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

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

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

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

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

9、Ai運(yùn)往銷地Bi的數(shù)量。(2)在解決問題的過程中，要受到如下條件限制，即約束條件:各產(chǎn)地運(yùn)出的數(shù)量應(yīng)等于其產(chǎn)量，即6080+ + X11 X12 X13 一+ + -匚 X 21 X 22 X 23各銷地運(yùn)進(jìn)的數(shù)量應(yīng)等于其當(dāng)?shù)仡A(yù)測(cè)的銷售量，即Xl+X21=50 X12+X22=50-X13*X23=40從各產(chǎn)地運(yùn)往各銷地的數(shù)量不能為負(fù)值，即Xij -0(i =1,2; j =1,2,3)該問題的目的是運(yùn)價(jià)最低，所以運(yùn)價(jià)是目標(biāo)函數(shù)，即S = 600 X11 +300X12 + 400 X12 + 400 X21 + 700 X22 + 300 X23 因止匕，該問題的數(shù)學(xué)模型為：求 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的一般形式是：設(shè)某種物資有m個(gè)產(chǎn)地A，A2,Am產(chǎn)量分別為 a1,a2,am5有n個(gè)銷地BB,B,銷量分別為b,b“.b(噸)。如果由 產(chǎn)地A運(yùn)往銷地Bj的單位運(yùn)價(jià)為Cj (元/噸)，在產(chǎn)銷平衡的情況下，應(yīng)如何調(diào)運(yùn)才能使運(yùn)費(fèi)最?。拷?設(shè)Xj表示由產(chǎn)地Ai運(yùn)往銷地Bj的數(shù)是(i=l, m； j=1,2,n)則該問題數(shù)學(xué)模型為：求變量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),并使目標(biāo)函數(shù)S=CiiXii+Ci2Xi2+CmnXmn的值最小。二、生產(chǎn)組織與計(jì)劃問題例2設(shè)某用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)品每單位可是利潤(rùn)分別為Ci，C2,Cn。在該廠產(chǎn) 品全部能銷售情況下，應(yīng)如何組織生產(chǎn)，才能使該

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

13、能使產(chǎn)品 符合要求，又使成本最低？解 設(shè)xi表示每單位產(chǎn)品中原料 Ai的使用量（即決策變量），i =1,2,m,則數(shù)學(xué)模型 為：求一組變量的值，使其滿足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）并使目標(biāo)函數(shù)S=d1X+dmXm最小。二、線性規(guī)劃問題數(shù)學(xué)模型的一般形式和標(biāo)準(zhǔn)形式上面我們建立了經(jīng)濟(jì)領(lǐng)域中常見的實(shí)際問題的數(shù)學(xué)模型，盡管這些實(shí)際問題本身是多種多樣的，但是它們的數(shù)學(xué)模型卻具有相

14、同的特征：要確定某些變量（決策變量）的一組值，使得在確定的確定的約束條件下，目標(biāo)函數(shù)是取得最大值或最小值。其 中，約束條件是決策變量的線性方程或線性不等式。目標(biāo)函數(shù)是決策變量的線性函 數(shù)。因此，我們把這種規(guī)劃問題稱為線性規(guī)劃問題。同時(shí)，我們可以得到對(duì)于一個(gè) 線性規(guī)劃問題，其數(shù)學(xué)模型應(yīng)具有如下形式：求 max（或 min）S=C1X1 C2X2 CnXna aux+2x2+ainXnb（或至b，或=9a2lXl +a22X2+ + a2nXn b2（或至 b2,或加0(j =i,2,n)線性規(guī)劃問題的標(biāo)準(zhǔn)（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 -更多精品文檔學(xué)習(xí)-好資料對(duì)于線性規(guī)劃問題的一般形式，可以按如下方法化成標(biāo)準(zhǔn)形：(1)如果線性規(guī)劃問題是求目標(biāo)函數(shù)的最大值，即求maxS = ClX1+cnxn,只要令S = -S ,即可化為求目標(biāo)函數(shù)的最小值，即求 m iSnC1X1 C2X2CnXn(2)如果某個(gè)約束條件為線性不等式，則可將其化為線性議程式的形式。設(shè)第k個(gè)約束條件為akiXl +ak2X2 +akmXn蕓bk :則加入一個(gè)新變量，將其約束條件改為：akiXl ak2X2aknXn Xn k =bk這個(gè)所加

16、的變量稱為松弛變量。若第l個(gè)約束條件為：aMXi +ai2X2+ ainXn -b則加入一個(gè)新變量，將上述約束條件變?yōu)椋篴ilXl ai2X2ainXn Xnl =bl(3)若對(duì)某變量沒有非負(fù)限制，則引進(jìn)兩個(gè)非負(fù)變量X，j之0，X”j20令Xj = Xj X：代入約束條件和目標(biāo)函數(shù)，可化為全部變量都有非負(fù)限制。例4 將下列線性規(guī)劃模型化為標(biāo)準(zhǔn)形m aSX-2Xi 3X2X2+X2-5S.tj3Xi X22Y?0，Y2為非負(fù)限制X1 X2X“2 且 xFQxy0解引入松馳變量X30，X40,令S=-S，X2 = X2更多精品文檔學(xué)習(xí)-好資料即可得標(biāo)準(zhǔn)形式如下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ì)對(duì)于線性規(guī)劃問題(13.2):minS =CX1.幾個(gè)概念(D 口仃解：滿足線性規(guī)劃問題所有約束條件的向量 x =(x1(0)，Xn(0)T稱為可行解，所有可行解構(gòu)成的集合稱為可行域，記為 R,則R= x| Ax = b,x2 0(2)基礎(chǔ)可行解：若可行解X=0,或X的非零分量所對(duì)應(yīng)的系數(shù)列向量線性無關(guān)， 則稱X為基礎(chǔ)可行解。(3)最優(yōu)解：使目標(biāo)函數(shù)取最小值的可行解稱為最優(yōu)解。 (4)基礎(chǔ)最優(yōu)解：使目標(biāo)函數(shù)取最小值的基礎(chǔ)可行解稱為基

18、礎(chǔ)最優(yōu)解。 (5)門”：若連接n維點(diǎn)集S中任意兩點(diǎn)Xl，X2的線段仍要S內(nèi)，則稱S為凸集。換言之，若x|x = ： X1 1-： X2，0- -1，Xi，X2 S : S，S En則稱S為凸集。更多精品文檔學(xué)習(xí)-好資料（6）強(qiáng)點(diǎn)：若凸集S中的點(diǎn)x,不能成為S中任何線段的內(nèi)點(diǎn)，則稱x為S的極點(diǎn)，換言之，若對(duì)任意不同兩點(diǎn) x1,x2e S,不存在a（0a1）,使x =二 x1 （1 ）X2 三 S則稱x為S的極點(diǎn)。例如，圓周上的點(diǎn)都是極點(diǎn)。s（7）門”學(xué):設(shè)xi = En,實(shí)數(shù)九0=1,2,s,且九i=1,則稱.i 1x = 1x1 x2s s為點(diǎn)x1, x2, , xs的一個(gè)凸組合。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中的點(diǎn)x是極點(diǎn)的充要條件是x是基礎(chǔ)可行解。性質(zhì)3若（LP）問題的可行域Rw，則R至少有一極點(diǎn)，且極點(diǎn)的個(gè)數(shù)有限。性質(zhì)4最優(yōu)值可以在極點(diǎn)上達(dá)到。這幾條性質(zhì)實(shí)際上給我們指出了線性規(guī)劃問題求解的思路和方向：由于線性規(guī)劃問題的最優(yōu)解一定能在可行解集的極點(diǎn)達(dá)到，而極點(diǎn)的數(shù)目中有限的。所以，總更多精品文檔學(xué)習(xí)-好資料可以想辦法在有限的極點(diǎn)中經(jīng)過有限

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

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