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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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