精品資料（2021-2022年收藏的）線性規(guī)劃與數(shù)學(xué)建模簡介

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

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

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

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

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

6、探析，力爭得到最優(yōu)模型。6模型檢驗對于經(jīng)過分析后符合要求的模型，還要把它放回到實際對象中去進行檢驗，看它是否符合實際，能否解決相應(yīng)的實際問題。若不符合實際，就要修改前提假設(shè)，重新建模，重新分析，直到獲得符合實際的模型。7模型應(yīng)用建模最終目的，是用模型來分析、研究和解決實際問題。因此，一個成功和數(shù)學(xué)模型必須能夠在實踐中得到成功的應(yīng)用，甚至形成一套科學(xué)和理論。圖131是上述各步驟的直觀圖：建模準(zhǔn)備（分析實際問題確立課題）建模假設(shè)（抽象、簡化）構(gòu)建模型模型求解模型分析（是否相符）模型分析（是否相符模型應(yīng)用圖131數(shù)學(xué)建模步驟示意圖一、 數(shù)學(xué)模型的分類數(shù)學(xué)模型按照不同的分類標(biāo)準(zhǔn)有許多種類：1按照模型的

7、數(shù)學(xué)方法分，有幾何模型、代數(shù)模型、圖論模型、微分方程模型概率模型、最優(yōu)控制模型、隨機模型等等。2 按模型的特征分，有靜態(tài)模型和動態(tài)模型，確定性模型和隨機模型，離散模型和連續(xù)性模型，線性模型和非線性模型等。3按模型的應(yīng)用領(lǐng)域分，有人口模型、交通模型、經(jīng)濟模型、生態(tài)模型、資源模型、環(huán)境模型等。4。按建模的目的分，有預(yù)測模型、優(yōu)化模型、決策模型、控制模型等。5 按奪模型結(jié)構(gòu)的了解程度分，有白箱模型、灰箱模型、黑箱模型等。§2線性規(guī)劃問題及其數(shù)學(xué)模型線性規(guī)劃作為運籌學(xué)的一人重要分支，是研究較早，理論較完善，應(yīng)用最廣泛的一門科學(xué)。它所研究的問題主要包括兩個方面：一是在一項任務(wù)確定后，如何以最低

8、限度和成本（如人力、物力、資金和時間等）去完成這一任務(wù)；二是如何在現(xiàn)有條件下進行組織和安排，以完成更多的工作。因此，線性規(guī)劃就是求一組變量的值，使它滿足一組線性式子，并使一個線性函數(shù)的值最大（或最小）的數(shù)學(xué)方法。一、運輸問題例1設(shè)有A1，A2兩個香蕉基地，產(chǎn)量分別為60噸和80噸，聯(lián)合供應(yīng)B1，B2，B3三個銷地的銷售量經(jīng)預(yù)測分別為50噸、50噸和40噸。兩個產(chǎn)地到三個銷地的單位運價如下表所示：表131運價表（單位：元/噸） 銷地單位動價產(chǎn)地B1B2B3A1600300400A2400700300問每個產(chǎn)地向每個銷地各發(fā)貨多少，才能使總的運費最少？解（1）在該問題中，所要確定的量是各產(chǎn)地運往各

9、銷地的香蕉數(shù)量，即決策變量是運輸量。設(shè)Xij(i=1,2; j =1,2,3)分別表示由產(chǎn)地Ai運往銷地Bi的數(shù)量。 （2）在解決問題的過程中，要受到如下條件限制，即約束條件：j各產(chǎn)地運出的數(shù)量應(yīng)等于其產(chǎn)量，即 各銷地運進的數(shù)量應(yīng)等于其當(dāng)?shù)仡A(yù)測的銷售量，即 從各產(chǎn)地運往各銷地的數(shù)量不能為負(fù)值，即(3)該問題的目的是運價最低，所以運價是目標(biāo)函數(shù)，即因此，該問題的數(shù)學(xué)模型為：求 結(jié)束條件例1的一般形式是：設(shè)某種物資有m個產(chǎn)地產(chǎn)量分別為，有n個銷地,銷量分別為如果由產(chǎn)地運往銷地的單位運價為（元/噸），在產(chǎn)銷平衡的情況下，應(yīng)如何調(diào)運才能使運費最?。拷?設(shè)表示由產(chǎn)地運往銷地的數(shù)是(i=1,，m；j=1,

10、2,，n)則該問題數(shù)學(xué)模型為：求變量的一組值，使它們滿足 并使目標(biāo)函數(shù)的值最小。二、生產(chǎn)組織與計劃問題 例2 設(shè)某用種原料，生產(chǎn) 種產(chǎn)品，其中 種產(chǎn)品每單位需要原粉分別為；而該廠現(xiàn)有原料；的數(shù)量分別為各種產(chǎn)品每單位可是利潤分別為 。在該廠產(chǎn)品全部能銷售情況下，應(yīng)如何組織生產(chǎn)，才能使該企業(yè)獲得最大？解 設(shè)生產(chǎn)產(chǎn)中數(shù)量為，則此問題的數(shù)學(xué)模型為：求一組變量 的值，使?jié)M足 結(jié)束條件 并使目標(biāo)函數(shù)的值最大。三、配料問題例 設(shè)有種原料，配制含有幾種成分的產(chǎn)品，要求產(chǎn)品中各種成分的含量不低于；不高于；種成分在種原料中的單位含量為，各種原料的單位價格依次為問如何調(diào)配原料，才能使產(chǎn)品符合要求，又使成本最低？解

11、設(shè)表示每單位產(chǎn)品中原料的使用量(即決策變量)，則數(shù)學(xué)模型為：求一組變量的值，使其滿足 約束條件 并使目標(biāo)函數(shù) 最小。二、 線性規(guī)劃問題數(shù)學(xué)模型的一般形式和標(biāo)準(zhǔn)形式上面我們建立了經(jīng)濟領(lǐng)域中常見的實際問題的數(shù)學(xué)模型，盡管這些實際問題本身是多種多樣的，但是它們的數(shù)學(xué)模型卻具有相同的特征：要確定某些變量(決策變量)的一組值，使得在確定的確定的約束條件下，目標(biāo)函數(shù)是取得最大值或最小值。其中，約束條件是決策變量的線性方程或線性不等式。目標(biāo)函數(shù)是決策變量的線性函數(shù)。因此，我們把這種規(guī)劃問題稱為線性規(guī)劃問題。同時，我們可以得到對于一個線性規(guī)劃問題，其數(shù)學(xué)模型應(yīng)具有如下形式： 求 我們稱這種形式的線性規(guī)劃模型為

12、一般形式。其中，為目標(biāo)函數(shù)系數(shù)約束方程系數(shù)；為約束方程常數(shù)項；(i=1,m;j=1,n).由此可見，一個線性規(guī)劃問題問題的數(shù)學(xué)模型，必須含有三個要素：決策變量、約束條件和目標(biāo)函數(shù)。由上面的例子可知，線性規(guī)劃問題的數(shù)學(xué)模型的一般形式很多。目標(biāo)函數(shù)有求最大值和最小值；約束條件有“”，“”，“”三種情況。這種多樣性給問題的討論帶來很大的不便。為此，我們介紹線性規(guī)劃問題的一種統(tǒng)一形式標(biāo)準(zhǔn)形式。規(guī)定線性規(guī)劃問題的數(shù)學(xué)模型的標(biāo)準(zhǔn)形式為：S.t 線性規(guī)劃問題的標(biāo)準(zhǔn)（13.1）也可寫成矩陣形式s.t 其中，X，A，B對于線性規(guī)劃問題的一般形式，可以按如下方法化成標(biāo)準(zhǔn)形：（1）如果線性規(guī)劃問題是求目標(biāo)函數(shù)的最大

13、值，即求，只要令，即可化為求目標(biāo)函數(shù)的最小值，即求（2）如果某個約束條件為線性不等式，則可將其化為線性議程式的形式。設(shè)第k個約束條件為：則加入一個新變量，將其約束條件改為：這個所加的變量稱為松弛變量。若第個約束條件為：則加入一個新變量，將上述約束條件變?yōu)椋海?）若對某變量沒有非負(fù)限制，則引進兩個非負(fù)變量令代入約束條件和目標(biāo)函數(shù)，可化為全部變量都有非負(fù)限制。例4 將下列線性規(guī)劃模型化為標(biāo)準(zhǔn)形解引入松馳變量，令且即可得標(biāo)準(zhǔn)形式如下S.t§3線性規(guī)劃問題解的性質(zhì)及圖解法一、 線性規(guī)劃問題的解的性質(zhì)對于線性規(guī)劃問題（13.2）： 1 幾個概念（1）可行解：滿足線性規(guī)劃問題所有約束條件的向量稱

14、為可行解，所有可行解構(gòu)成的集合稱為可行域，記為R，則R（2）基礎(chǔ)可行解：若可行解X0，或X的非零分量所對應(yīng)的系數(shù)列向量線性無關(guān)，則稱X為基礎(chǔ)可行解。（3）最優(yōu)解：使目標(biāo)函數(shù)取最小值的可行解稱為最優(yōu)解。（4）基礎(chǔ)最優(yōu)解：使目標(biāo)函數(shù)取最小值的基礎(chǔ)可行解稱為基礎(chǔ)最優(yōu)解。（5）凸集：若連接n維點集S中任意兩點的線段仍要S內(nèi)，則稱S為凸集。換言之，若則稱S為凸集。（6）極點：若凸集S中的點,不能成為S中任何線段的內(nèi)點，則稱x為S的極點。換言之，若對任意不同兩點,不存在，使 則稱為S的極點。例如，圓周上的點都是極點。（7）凸集合：設(shè)，實數(shù)且,則稱 為點的一個凸組合。2 線性規(guī)劃問題的解由線性代數(shù)求解議程組

15、的方法及上述概念可知，線性規(guī)劃問題（LP）的解有如下幾種情況：有唯一最優(yōu)解有可行解有無窮多最優(yōu)解無最優(yōu)解無可行解3 線性規(guī)劃問題解的性質(zhì)性質(zhì)1線性規(guī)劃問題（LP）的可行域是凸集。性質(zhì)2可行域R中的點是極點的充要條件是是基礎(chǔ)可行解。性質(zhì)3若（LP）問題的可行域R，則R至少有一極點，且極點的個數(shù)有限。性質(zhì)4最優(yōu)值可以在極點上達到。這幾條性質(zhì)實際上給我們指出了線性規(guī)劃問題求解的思路和方向：由于線性規(guī)劃問題的最優(yōu)解一定能在可行解集的極點達到，而極點的數(shù)目中有限的。所以，總可以想辦法在有限的極點中經(jīng)過有限次尋找，得到最優(yōu)解。因而，就有了求解線性規(guī)劃問題的圖解法和單純形法。由于篇幅所限，下面僅介紹圖解法的

16、應(yīng)用。有興趣的讀者可以學(xué)習(xí)一下單純形法。二、 圖解法（又稱幾何法）圖解法是對于只是兩個決策變量的線性規(guī)劃問題，在平面內(nèi)建立直角坐標(biāo)系，使每個決策變量的取值在一個數(shù)軸上表示出來，可行解就成為平面上的點，可行域就是平面上的一個共域，從而最優(yōu)解必定是在這個平面區(qū)域內(nèi)（包括邊界上）的點。根據(jù)目標(biāo)函數(shù)在這個平面區(qū)域內(nèi)的取值找出使目標(biāo)函數(shù)取得最優(yōu)值的點（即最優(yōu)解）。圖解法便于我們理解和了解線性規(guī)劃問題的一些概念、理論及解的一些特性，也為我們進一步學(xué)習(xí)單純方法提供一個直觀圖形。例5求解線性問題解第一步，在平面直角坐標(biāo)系上繪出約束條件圖（圖132）畫出這條直線，再定出區(qū)域。把（0，0）代入不等式得02

17、3;028，所以，原點所在半平面及直線本身就是代表的區(qū)域。畫出這條直線，定出代表的區(qū)域，有（0，0）代入不等式得0·4042所以，代表的區(qū)域是包括原點的下半平面與直線本身。定出的區(qū)域，它就是第一象限。從圖132看出，滿足全部約束條件的點所構(gòu)成的區(qū)域（即可行域），就是凸多邊形OABC。第二步，繪制目標(biāo)函數(shù)圖形。對于目標(biāo)函數(shù)將S看作參數(shù)，即得到一簇平行直線（圖132中虛線所示），直線上每一點的目標(biāo)函數(shù)值為S。由圖可見，直線離原點越遠(yuǎn)，S值越大，我們尋找的是在可行域內(nèi)使S值最大點?？梢?，B點即為可行域內(nèi)使目標(biāo)函數(shù)最大的點，即為最優(yōu)解。第三步，確定最優(yōu)解。B點是直線交點，所以解方程組得到這就是最優(yōu)解。將其代入目標(biāo)函數(shù)，得最優(yōu)解例5有可行解且有唯一最優(yōu)解將目標(biāo)函數(shù)改為仍求其最大值，則BC或AB上每一點的坐標(biāo)均為最優(yōu)解，最優(yōu)解有無窮多個，而它們對應(yīng)的目標(biāo)函數(shù)數(shù)值是28或42。讀者可以證明習(xí)題中第4題的（1）小題有可行解但無最優(yōu)解（2）小題沒有可行解。這就說明了線性規(guī)劃問題解的情況。習(xí)題十三1 寫出下列問題的數(shù)學(xué)模型：（1）