數(shù)學建模的建立與應用

第七章線性規(guī)劃模型(móxíng)的建立與應用一、線性規(guī)劃的概念二、線性規(guī)劃三要素三、技術經濟研究中運用線性規(guī)劃方法(fāngfǎ)的特點及局限性四、線性規(guī)劃模型的根本結構五、線性規(guī)劃模型的一般形式六、線性規(guī)劃模型的根本假設

第一節(jié)線性規(guī)劃模型的根本(gēnběn)原理第一頁，共73頁。1線性規(guī)劃是指如何最有效或最正確地謀劃經濟活動。它所研究的問題有兩類：一類是指一定資源的條件下，到達最高產量、最高產值、最大利潤；一類是，任務量一定，如何統(tǒng)籌安排，以最小的消耗取完成這項任務。如最低本錢問題、最小投資、最短時間、最短距離等問題。前者(qiánzhě)是求極大值問題，后者是求極小值問題。總之，線性規(guī)劃是一定限制條件下，求目標函數(shù)極值的問題。

第一節(jié)線性規(guī)劃模型的根本(gēnběn)原理一、線性規(guī)劃(xiànxìnɡɡuīhuá)的概念第二頁，共73頁。2?經濟大詞典?定義線性規(guī)劃(xiànxìnɡɡuīhuá)：一種具有確定目標，而實現(xiàn)目標的手段又有一定限制，且目標和手段之間的函數(shù)關系是線性的條件下，從所有可供選擇的方案中求解出最優(yōu)方案的數(shù)學方法。

第一節(jié)線性規(guī)劃模型的根本(gēnběn)原理一、線性規(guī)劃(xiànxìnɡɡuīhuá)的概念第三頁，共73頁。3二、線性規(guī)劃(xiànxìnɡɡuīhuá)三要素1.目標函數(shù)最優(yōu)化——單一目標多重目標問題如何處理？2.實現(xiàn)目標的多種方法假設實現(xiàn)目標只有一種方法不存在規(guī)劃問題。3.生產條件的約束——資源(zīyuán)是有限的資源(zīyuán)無限不存在規(guī)劃問題。第一節(jié)線性規(guī)劃(xiànxìnɡɡuīhuá)模型的根本原理第四頁，共73頁。4三、技術經濟研究中運用線性規(guī)劃方法(fāngfǎ)的特點及局限性

第一節(jié)線性規(guī)劃模型的根本(gēnběn)原理特點：1.可以使研究對象具體化、數(shù)量化?？梢詫λ芯康募夹g經濟問題做出明確的結論(jiélùn)；4.有一套完整的運算程序第五頁，共73頁。5三、技術經濟(jīngjì)研究中運用線性規(guī)劃方法的特點及局限性

第一節(jié)線性規(guī)劃模型的根本(gēnběn)原理局限性：1.線性規(guī)劃它是以價格不變和技術不變?yōu)榍疤釛l件的，不能處理涉及到時間因素的問題。因此，線性規(guī)劃只能以短期方案為根底(gēndǐ)。2.在生產活動中，投入產出的關系不完全是線性關系，由于在一定的技術條件下，報酬遞減規(guī)律起作用，所以要滿足線性假定是不可能的。在線性規(guī)劃解題中，常常把投入產出的非線性關系轉化為線性關系來處理，以滿足線性的假定性，客觀上產生誤差。3.線性規(guī)劃本身只是一組方程式，并不提供經濟概念，它不能代替人們對現(xiàn)實經濟問題的判斷。第六頁，共73頁。6四、線性規(guī)劃(xiànxìnɡɡuīhuá)模型的根本結構1.決策變量——未知數(shù)。它是通過模型計算來確定的決策因素。又分為實際變量——求解的變量和計算變量，計算變量又分松弛變量〔上限(shàngxiàn)〕和人工變量〔下限〕。2.目標函數(shù)——經濟目標的數(shù)學表達式。目標函數(shù)是求變量的線性函數(shù)的極大值和極小值這樣一個極值問題。3.約束條件——實現(xiàn)經濟目標的制約因素。它包括：生產資源的限制〔客觀約束條件〕、生產數(shù)量、質量要求的限制〔主觀約束條件〕、特定技術要求和非負限制。第一節(jié)線性規(guī)劃模型的根本(gēnběn)原理第七頁，共73頁。7四、線性規(guī)劃模型(móxíng)的根本結構MinZ=10x1+20x2

s.t.x1+x2≥103x1+x2≥15

x1+6x2≥15

x1≥0,x2≥0約束條件目標(mùbiāo)函數(shù)第一節(jié)線性規(guī)劃(xiànxìnɡɡuīhuá)模型的根本原理第八頁，共73頁。8五、線性規(guī)劃模型(móxíng)的一般形式MaxZ=c1x1+c2x2+c3x3+…+cnxna11x1+a12x2+…+a1nxn≤b1 (1)a21x1+a22x2+…+a2nxn≤

b2 (2)……am1x1+am2x2+…+amnxn≤bm (m)x1，x2，…xn≥0第一節(jié)線性規(guī)劃(xiànxìnɡɡuīhuá)模型的根本原理極大值模型(móxíng)第九頁，共73頁。9其簡縮(jiǎnsuō)形式為第一節(jié)線性規(guī)劃模型(móxíng)的根本原理極大值模型(móxíng)第十頁，共73頁。10五、線性規(guī)劃模型的一般(yībān)形式MinZ=c1x1+c2x2+c3x3+…+cnxn

a11x1+a12x2+…+a1nxn≥b1 (1)a21x1+a22x2+…+a2nxn≥b2 (2)……am1x1+am2x2+…+amnxn≥bm (m)

x1，x2，…xn≥0第一節(jié)線性規(guī)劃模型的根本(gēnběn)原理極小值模型(móxíng)第十一頁，共73頁。11其簡縮(jiǎnsuō)形式為第一節(jié)線性規(guī)劃模型的根本(gēnběn)原理極小值模型(móxíng)第十二頁，共73頁。12其簡縮(jiǎnsuō)形式為第一節(jié)線性規(guī)劃模型的根本(gēnběn)原理極大值模型(móxíng)可用向量表示：

C=(c1,c2,……cn)第十三頁，共73頁。13六、線性規(guī)劃(xiànxìnɡɡuīhuá)模型的根本假設1.線性目標函數(shù)和約束條件2.可分性活動對資源的可分性3.可加性活動所耗資源的可加性，資源總需要量為多種活動所需資源數(shù)量的總和。4.明確性目標的明確性5.單一性期望值的單一性6.獨立性變量是獨立的表示各種(ɡèzhǒnɡ)作業(yè)對資源都是互竟關系，沒有互助關系第十四頁，共73頁。14第二節(jié)線性規(guī)劃模型(móxíng)的建立與圖解法求解一、建模二、線性規(guī)劃(xiànxìnɡɡuīhuá)的求解——圖解法第十五頁，共73頁。15一、建模[例1]某飼料公司用甲、乙兩種原料配制飼料，甲乙兩種原料的營養(yǎng)成份及配合飼料中所含各營養(yǎng)成份最低量由表1給出。單位甲、乙原料的價格分別(fēnbié)為10元和20元，求滿足營養(yǎng)需要的飼料最小本錢配方。第十六頁，共73頁。16一、建模設配合飼料中，用甲x1單位，用乙x2單位，那么配合飼料的原料本錢函數(shù)，即決策的目標函數(shù)為Z=10x1+20x2?？紤]三種營養(yǎng)含量限制(xiànzhì)條件后，可得這一問題的線性規(guī)劃模型如下：MinZ=10x1+20x2x1+x2≥103x1+x2≥15x1+6x2≥15x1≥0,x2≥0第十七頁，共73頁。17一、建模[例2]某農戶方案用12公頃耕地生產玉米，大豆和地瓜，可投入48個勞動日，資金360元。生產玉米1公頃，需6個勞動日，資金36元，可獲凈收入200元；生產1公頃大豆，需6個勞動日，資金24元，可獲凈收入150元；生產1公頃地瓜需2個勞動日，資金18元，可獲凈收入1200元，問怎樣安排才能使總的凈收入最高。設種玉米，大豆和地瓜的數(shù)量分別為x1、x2和x3公頃，根據(jù)(gēnjù)問題建立線性規(guī)劃問題模型如下：第十八頁，共73頁。18一、建模MaxZ=200x1+150x2+100x3

x1+x2+x3≤12 (1)6x1+6x2+2x3≤48 (2)36x1+24x2+18x3≤360 (3)

x1≥0，x2≥0，x3≥0

第十九頁，共73頁。19一、建模[例3]某農戶有耕地20公頃，可采用甲乙兩種種植方式。甲種植方式每公頃需投資280元，每公頃投工6個，可獲收入1000元，乙方式每公頃需投資150元，勞動15個工日，可獲收入1200元，該戶共有可用資金4200元、240個勞開工日。問如何(rúhé)安排甲乙兩種方式的生產，可使總收入最大?解：設甲方式種x1公頃，乙方式種x2公頃，總收入為Z，那么有：第二十頁，共73頁。20一、建模MaxZ=1000x1+1200x2280x1+150x2≤42006x1+15x2≤240x1+x2≤20x1≥0,x2≥0

第二十一頁，共73頁。21二、線性規(guī)劃(xiànxìnɡɡuīhuá)的求解——圖解法〔一〕可行(kěxíng)解〔二〕可行(kěxíng)域〔三〕最優(yōu)解〔四〕最優(yōu)性定理〔五〕最大化問題的圖解法〔六〕最小化問題的圖解法第二十二頁，共73頁。22二、線性規(guī)劃(xiànxìnɡɡuīhuá)的求解——圖解法〔一〕可行解線性規(guī)劃問題的可行解是指，滿足規(guī)劃中所有約束條件及非負約束的決策變量的一組取值，其僅與約束條件有關而與目標函數(shù)值的大小(dàxiǎo)無關?！捕晨尚杏蚩尚杏蚴怯伤锌尚薪鈽嫵傻募?。根據(jù)線性規(guī)劃的根本理論，任一個線性規(guī)劃問題的可行域，都是一個有限或無限的凸多邊形，凸多邊形的每個角，稱為可行域的極點。〔三〕最優(yōu)解線性規(guī)劃的最優(yōu)解是指，使目標函數(shù)值到達最優(yōu)(最大或最小)的可行解。一個線性規(guī)劃問題可以是有解的，也可能是無解的，最優(yōu)解的個數(shù)可能是惟一的，也可能是有無窮多個，即決策變量有許多組不同的取值，都使目標函數(shù)到達同一個最優(yōu)值。第二十三頁，共73頁。23二、線性規(guī)劃(xiànxìnɡɡuīhuá)的求解——圖解法〔四〕最優(yōu)性定理假設一個線性規(guī)劃問題有最優(yōu)解，那么最優(yōu)解一定可以在可行域的某個極點上找到一個最優(yōu)解。同時(tóngshí)仍有可能有其他最優(yōu)解存在，但它們也只可能存在于可行域的其他極點或是邊界上。如果我們的目的是找出一個最優(yōu)解而不是全部最優(yōu)解，這一定理實際上是把尋找的范圍，從可行域中的無窮多個可行點，縮小到可行域的有限幾個極點上。第二十四頁，共73頁。24二、線性規(guī)劃(xiànxìnɡɡuīhuá)的求解——圖解法〔五〕最大化問題的圖解法第一步，找出問題的可行(kěxíng)域第二步，在可行(kěxíng)域中尋求最優(yōu)解，方法有兩種：第二十五頁，共73頁。25二、線性規(guī)劃(xiànxìnɡɡuīhuá)的求解——圖解法

O2040x120ABCD280x1+150x2=42006x1+15x2=240x1+x2=20x2Z=1000x1+1200x2A(0,16)B(6.7,13.3)C(9.2,10.8)D(15,0)ZA=19200ZB=22660ZC=22160ZD=15000第二十六頁，共73頁。26二、線性規(guī)劃(xiànxìnɡɡuīhuá)的求解——圖解法〔五〕最小化問題(wèntí)的圖解法例：MinZ=10x1+20x2s.t.x1+x2≥103x1+x2≥15x1+6x2≥15x1≥0,x2≥0第二十七頁，共73頁。271515105105OABCDx2x1x1+6x2=15可行(kěxíng)域3x1+x2=15x1+x2=1010x1+20x2＝0A(0,15)B(2.5,7.5)C(9,1)D(15,0)ZA=300ZB=175ZC=110ZD=150第二十八頁，共73頁。28第三節(jié)單純形法單純形方法是一種較為完善的、步驟化的線性規(guī)劃問題求解方法。它的原理涉及到較多的數(shù)學理論上的推導和證明，我們在此僅介紹這種方法的具體操作步驟及每一步的經濟上的含義(hányì)。為更好地說明問題，我們仍結合實例介紹這種方法第二十九頁，共73頁。29第三節(jié)單純形法一、線性規(guī)劃(xiànxìnɡɡuīhuá)的標準型二、線性規(guī)劃(xiànxìnɡɡuīhuá)問題的解三、單純形法四、單純型表第三十頁，共73頁。30第三節(jié)單純形法一線性規(guī)劃(xiànxìnɡɡuīhuá)的標準型LP目標函數(shù)有的要求實現(xiàn)最大化，有的要求實現(xiàn)最小化，約束條件可以是“<=〞、“>=〞、“＝〞，這種多樣性給討論問題(wèntí)帶來不便。為了便于討論，我們規(guī)定線性規(guī)劃問題(wèntí)的標準形式為：MaxZ=c1x1+c2x2+c3x3+…+cnxna11x1+a12x2+…+a1nxn=b1 (1)a21x1+a22x2+…+a2nxn=b2 (2)……am1x1+am2x2+…+amnxn=bm (m)x1，x2，…xn≥0第三十一頁，共73頁。31第三節(jié)單純形法其簡縮(jiǎnsuō)形式為一線性規(guī)劃(xiànxìnɡɡuīhuá)的標準型用向量(xiàngliàng)表示其中C=(c1,c2,……cn)

向量Pj是其對應變量xj的系數(shù)向量。第三十二頁，共73頁。32第三節(jié)單純形法一線性規(guī)劃(xiànxìnɡɡuīhuá)的標準型用矩陣(jǔzhèn)描述

第三十三頁，共73頁。33第三節(jié)單純形法二線性規(guī)劃(xiànxìnɡɡuīhuá)問題的解可行解最優(yōu)解基設A為約束方程組的m×n階系數(shù)矩陣，其秩為m。B是矩陣A中m×m階非奇異子矩陣〔〕,那么(nàme)稱B是線性規(guī)劃問題的一個基。不失一般性可設稱Pj為基向量，與基變量Pj相對(xiāngduì)應的變量為基變量。否那么為非基變量。第三十四頁，共73頁。34為了進一步討論線性規(guī)劃問題的解，我們來研究約束方程組求解的問題。假設方程組系數(shù)矩陣Z的秩為m，因m小于n故它有無窮多個解。假設前m個變量的系數(shù)列向量是線性獨立(dúlì)的，這時線性規(guī)劃模型可寫成:二線性規(guī)劃(xiànxìnɡɡuīhuá)問題的解第三十五頁，共73頁。35或設非基變量(biànliàng)用高斯(ɡāosī)消去法，可求出一個解稱X為根本(gēnběn)解根本可行解滿足非負條件的根本解二線性規(guī)劃問題的解第三十六頁，共73頁。36[例3]某工廠在方案期內安排生產x1x2兩種產品，這些產品分別需要在A、B、C、D四種不同的設備上加工。按工藝(gōngyì)規(guī)定，產品x1和產品x2在各設備上加工的臺時數(shù)見下表。各設備在方案期內有效臺時數(shù)分別是12、8、16和12?！惨慌_設備工作一小時稱為一臺時〕該工廠每生產一件產品x1可得利潤2元，每生產一件產品x2可得利潤3元，問如何安排生產方案，才能得到利潤最多？三單純形法第三十七頁，共73頁。37設備產品ABCDx12140x22204三單純形法第三十八頁，共73頁。38〔一〕求解(qiújiě)過程〔二〕求解(qiújiě)過程小結三單純形法第三十九頁，共73頁。39MaxZ=2x1+3x22x1+2x2≤12

x1+2x2≤84x1

≤16 4x2

≤12

x1≥0，x2≥0引入松弛變量(biànliàng)x3—A設備閑置臺時數(shù)x4—B設備閑置臺時數(shù)x5—C設備閑置臺時數(shù)x6—D設備閑置臺時數(shù)將線性規(guī)劃化為標準型.〔8.1〕三單純形法求解(qiújiě)過程第四十頁，共73頁。40MaxZ=2x1+3x2+x3+x4+x5+x6

2x1+2x2+x3=12

x1+2x2+x4=84x1

+x5=16 4x2

+x6=12

x1≥0，x2≥0,x3≥0，x4≥0,x5≥0，x6≥0〔8.2〕三單純形法求解(qiújiě)過程第四十一頁，共73頁。41x3,x4,x5,x6的系數(shù)(xìshù)列向量p3,p4,p5,p6是線性獨立的，這些列向量構成一個基系數(shù)(xìshù)矩陣三單純形法求解(qiújiě)過程第四十二頁，共73頁。42x3=12－2x1－2x2 x4=8－x1－2x2x5=16－4x1 x6=12－4x2把上式帶入目標函數(shù)得到Z=0+2x1+3x2〔8.4〕當非基變量(biànliàng)x1=x2=0,便得z=0，這時得到一個根本可行解X(0)對應于B的變量x3,x4,x5,x6為基變量，從標準型我們(wǒmen)可以得到：〔8.3〕三單純形法求解(qiújiě)過程第四十三頁，共73頁。43這個根本可行解表示：工廠(gōngchǎng)沒有安排生產產品；設備的有效臺時數(shù)沒有被利用，所以構成的利潤為0。從分析目標函數(shù)的表達式可以看到，非基變量x1,x2系數(shù)都是正數(shù)，假設將非基變量換成基變量，目標函數(shù)就會增加。所以，只要在目標函數(shù)的表達式中還存在正系數(shù)的非基變量，這表示目標函數(shù)還有增加的可能，就需要將非基變量換成基變量。一般選擇(xuǎnzé)正系數(shù)最大的那個非基變量。可按以下方法來確定換出變量。三單純形法求解(qiújiě)過程第四十四頁，共73頁。44現(xiàn)分析〔8.4〕，將x2定為換入變量后，必須從x3,x4,x5,x6中換出一個，并保證其余的都是非負，即x3,x4,x5,x6≥0當x1＝0，由〔8.3〕式得到(dédào)x3=12－2x2≥0 x4=8－2x2 ≥0〔8.5〕x5=16 ≥0 x6=12－4x2≥0從〔8.5〕式中可以看出，只有選擇Z=0+2x1+3x2〔8.4〕時，才能(cáinéng)使〔8.5〕式成立。因當x2=3時，基變量x6=0這就決定(juédìng)用x2去替換x6。三單純形法求解過程第四十五頁，共73頁。45為了求得以x3,x4,x5,x2為基變量的一個根本可行解和進一步分析問題，需將〔8.5〕中的x2位置與x6的位置兌換。得到x3＋2x2=12－2x1 x4＋2x2=8－x1〔8.6〕x5=16－4x1 4x2=12－x6用高斯消去法，將〔8.6〕式中的x2的系數(shù)(xìshù)列向量變?yōu)閱挝涣邢蛄俊3=6－2x1+1/2x6 x4=2－x1+1/2x6〔8.7〕x5=16－4x1 x2=3－1/4x6三單純形法求解(qiújiě)過程第四十六頁，共73頁。46再將〔8.7〕代入〔8.1〕目標函數(shù)得到(dédào)：Z=9+2x1-3/4x6〔8.8〕當非基變量x1=x6=0，得到(dédào)Z=9，并得到(dédào)另一個根本可行解三單純形法求解(qiújiě)過程第四十七頁，共73頁。47從目標函數(shù)的表達式〔8.8〕中可看到，非基變量x1的系數(shù)是正的，說明目標函數(shù)值還可以增大，X(1)不一定是最優(yōu)解。于是用上述方法，確定換入換出變量，繼續(xù)迭代，再得到另一個根本可行解X(2)再經過(jīngguò)一次迭代，又得到一個根本可行解這時得到的目標函數(shù)的表達式是：Zx4-0.125x5目標函數(shù)值到達最大，X(3)是線性規(guī)劃的最優(yōu)解。三單純形法求解(qiújiě)過程第四十八頁，共73頁。481.人造基、初始根本(gēnběn)可行解2.最優(yōu)性檢驗三單純形法求解(qiújiě)過程小結第四十九頁，共73頁。491.人造基、初始根本可行(kěxíng)解Pj中能直接觀察到存在m個線性獨立的單位向量，經過重新安排次序便得到一個可行(kěxíng)基三單純形法求解過程(guòchéng)小結第五十頁，共73頁。501.人造基、初始根本可行解1.2“≤〞標準化的方法，引入非負的松弛變量重新對xj及aij編號，經整理那么可得到以下(yǐxià)方程MaxZ=c1x1+c2x2+c3x3+…+cnxnx1+a1m+1xm+1+a1m+2xm+2+…+a1nxn=b1x2+a2m+1xm+1+a2m+2xm+2+…+a2nxn=b2 〔8.9〕………xm+amm+1xm+1+amm+2xm+2+…+amnxn=bm x1，x2，…xn≥0顯然得到一個單位陣

三單純形法求解過程(guòchéng)小結第五十一頁，共73頁。51我們就將B作為可行基。將〔8.9〕每個等式進行(jìnxíng)移項得x1=b1-a1m+1xm+1-a1m+2xm+2-…-a1nxnx2=b2-a2m+1xm+1-a2m+2xm+2-…-a2nxn〔8.10〕……xm=bm-amm+1xm+1-amm+2xm+2-…-amnxn x1，x2，…xn≥0令xm+1=xm+2=……=xn=0,由〔8.10〕可得xi=bi(I=1,2,……m)得到一個初始根本可行解三單純形法求解過程(guòchéng)小結第五十二頁，共73頁。52得到初始可行解后，要檢驗一下是否是最優(yōu)解，如果是，那么停止迭代，如果不是，那么繼續(xù)(jìxù)迭代……。但每次迭代后都要檢驗一下是否是最優(yōu)解，為此需要建立一個判別準那么。一般情況下，經過迭代后式變成〔i=1,2,3,……,m〕將上式代入目標函數(shù)，整理后得三單純形法求解過程(guòchéng)小結第五十三頁，共73頁。53j=m+1,……,n三單純形法求解(qiújiě)過程小結第五十四頁，共73頁。542.1最優(yōu)解判別定理：假設為對應于B的根本可行解，且對于一切(yīqiè)j=m+1,……,n有，那么X〔0〕為最優(yōu)解。無有限最優(yōu)解判別定理：假設為對應于B的根本可行解，有一個并且對于一切(yīqiè)i=1,2,3,……,m有，那么該線性規(guī)劃沒有有限最優(yōu)解。2.3換出變量確實定，為換入變量。三單純形法求解(qiújiě)過程小結第五十五頁，共73頁。55三單純形表例1第五十六頁，共73頁。56例1第五十七頁，共73頁。57例1第五十八頁，共73頁。58例1第五十九頁，共73頁。59例2第六十頁，共73頁。60例2第六十一頁，共73頁。61例2第六十二頁，共73頁。62目標函數(shù)(hánshù)系數(shù)靈敏度分析右邊值靈敏度分析第四節(jié)靈敏度分析(fēnxī)第六十三頁，共73頁。63目標函數(shù)(hánshù)系數(shù)靈敏度分析最優(yōu)解不變的條件(tiáojiàn)下，允許C的變化范圍，最優(yōu)解不變的前提是σj≤0假設玉米價值系數(shù)C1發(fā)生了變化，其變化量為△1-50≤△1≤100△1≥-50△1≤100△1≥－100-50-△1≤0-50+0.5△1≤0-25-0.25△1≤0第六十四頁，共73頁。64目標函數(shù)系數(shù)(xìshù)靈敏度分析假設大豆價值系