第七章線性規(guī)劃模型的建立與應(yīng)用(農(nóng)業(yè)技術(shù)經(jīng)濟(jì)學(xué))

第七章線性規(guī)劃模型的建立與運(yùn)用學(xué)習(xí)目的與要求線性規(guī)劃是經(jīng)濟(jì)領(lǐng)域廣泛運(yùn)用的一種經(jīng)濟(jì)分析方法。講授本章目的是使同窗掌握線性規(guī)劃分析法的根本原理，掌握圖解法和單純形解法的程序及運(yùn)算，并借助電化教學(xué)，可以初步運(yùn)用線性規(guī)劃法處理最低本錢的農(nóng)業(yè)消費(fèi)資源最優(yōu)配合方式和最大收益的消費(fèi)構(gòu)造問題。第七章線性規(guī)劃模型的建立與運(yùn)用一、線性規(guī)劃的概念二、線性規(guī)劃三要素三、技術(shù)經(jīng)濟(jì)研討中運(yùn)用線性規(guī)劃方法的特點(diǎn)及局限性四、線性規(guī)劃模型的根本構(gòu)造五、線性規(guī)劃模型的普通方式六、線性規(guī)劃模型的根本假設(shè)

第一節(jié)線性規(guī)劃模型的根本原理線性規(guī)劃是指如何最有效或最正確地謀劃經(jīng)濟(jì)活動。它所研討的問題有兩類：一類是指一定資源的條件下，到達(dá)最高產(chǎn)量、最高產(chǎn)值、最大利潤；一類是，義務(wù)量一定，如何統(tǒng)籌安排，以最小的耗費(fèi)取完成這項(xiàng)義務(wù)。如最低本錢問題、最小投資、最短時間、最短間隔等問題。前者是求極大值問題，后者是求極小值問題。總之，線性規(guī)劃是一定限制條件下，求目的函數(shù)極值的問題。

第一節(jié)線性規(guī)劃模型的根本原理一、線性規(guī)劃的概念<經(jīng)濟(jì)大詞典>定義線性規(guī)劃：一種具有確定目的，而實(shí)現(xiàn)目的的手段又有一定限制，且目的和手段之間的函數(shù)關(guān)系是線性的條件下，從一切可供選擇的方案中求解出最優(yōu)方案的數(shù)學(xué)方法。

第一節(jié)線性規(guī)劃模型的根本原理一、線性規(guī)劃的概念二、線性規(guī)劃三要素1.目的函數(shù)最優(yōu)化——單一目的多重目的問題如何處置？2.實(shí)現(xiàn)目的的多種方法假設(shè)實(shí)現(xiàn)目的只需一種方法不存在規(guī)劃問題。3.消費(fèi)條件的約束——資源是有限的資源無限不存在規(guī)劃問題。第一節(jié)線性規(guī)劃模型的根本原理三、技術(shù)經(jīng)濟(jì)研討中運(yùn)用線性規(guī)劃方法的特點(diǎn)及局限性

第一節(jié)線性規(guī)劃模型的根本原理特點(diǎn)：1.可以使研討對象詳細(xì)化、數(shù)量化。可以對所研討的技術(shù)經(jīng)濟(jì)問題做出明確的結(jié)論；2.線性3.允許出現(xiàn)消費(fèi)要素的剩余量4.有一套完好的運(yùn)算程序三、技術(shù)經(jīng)濟(jì)研討中運(yùn)用線性規(guī)劃方法的特點(diǎn)及局限性

第一節(jié)線性規(guī)劃模型的根本原理局限性：1.線性規(guī)劃它是以價錢不變和技術(shù)不變?yōu)榍疤釛l件的，不能處置涉及到時間要素的問題。因此，線性規(guī)劃只能以短期方案為根底。2.在消費(fèi)活動中，投入產(chǎn)出的關(guān)系不完全是線性關(guān)系，由于在一定的技術(shù)條件下，報酬遞減規(guī)律起作用，所以要滿足線性假定是不能夠的。在線性規(guī)劃解題中，經(jīng)常把投入產(chǎn)出的非線性關(guān)系轉(zhuǎn)化為線性關(guān)系來處置，以滿足線性的假定性，客觀上產(chǎn)生誤差。3.線性規(guī)劃本身只是一組方程式，并不提供經(jīng)濟(jì)概念，它不能替代人們對現(xiàn)實(shí)經(jīng)濟(jì)問題的判別。四、線性規(guī)劃模型的根本構(gòu)造1.決策變量——未知數(shù)。它是經(jīng)過模型計算來確定的決策要素。又分為實(shí)踐變量——求解的變量和計算變量，計算變量又分松弛變量〔上限〕和人工變量〔下限〕。2.目的函數(shù)——經(jīng)濟(jì)目的的數(shù)學(xué)表達(dá)式。目的函數(shù)是求變量的線性函數(shù)的極大值和極小值這樣一個極值問題。3.約束條件——實(shí)現(xiàn)經(jīng)濟(jì)目的的制約要素。它包括：消費(fèi)資源的限制〔客觀約束條件〕、消費(fèi)數(shù)量、質(zhì)量要求的限制〔客觀約束條件〕、特定技術(shù)要求和非負(fù)限制。第一節(jié)線性規(guī)劃模型的根本原理四、線性規(guī)劃模型的根本構(gòu)造MinZ=10x1+20x2s.t.x1+x2≥103x1+x2≥15x1+6x2≥15x1≥0,x2≥0約束條件目的函數(shù)第一節(jié)線性規(guī)劃模型的根本原理五、線性規(guī)劃模型的普通方式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ī)劃模型的根本原理極大值模型其簡縮方式為第一節(jié)線性規(guī)劃模型的根本原理極大值模型五、線性規(guī)劃模型的普通方式MinZ=c1x1+c2x2+c3x3+…+cnxna11x1+a12x2+…+a1nxn≥b1 (1)a21x1+a22x2+…+a2nxn≥b2 (2)……am1x1+am2x2+…+amnxn≥bm (m)x1，x2，…xn≥0第一節(jié)線性規(guī)劃模型的根本原理極小值模型其簡縮方式為第一節(jié)線性規(guī)劃模型的根本原理極小值模型其簡縮方式為第一節(jié)線性規(guī)劃模型的根本原理極大值模型可用向量表示：C=(c1,c2,……cn)六、線性規(guī)劃模型的根本假設(shè)1.線性目的函數(shù)和約束條件2.可分性活動對資源的可分性3.可加性活動所耗資源的可加性，資源總需求量為多種活動所需資源數(shù)量的總和。4.明確性目的的明確性5.單一性期望值的單一性6.獨(dú)立性變量是獨(dú)立的表示各種作業(yè)對資源都是互竟關(guān)系，沒有互助關(guān)系7.非負(fù)性第二節(jié)線性規(guī)劃模型的建立與圖解法求解一、建模二、線性規(guī)劃的求解——圖解法一、建模[例1]某飼料公司用甲、乙兩種原料配制飼料，甲乙兩種原料的營養(yǎng)成份及配合飼料中所含各營養(yǎng)成份最低量由表1給出。知單位甲、乙原料的價錢分別為10元和20元，求滿足營養(yǎng)需求的飼料最小本錢配方。一、建模設(shè)配合飼料中，用甲x1單位，用乙x2單位，那么配合飼料的原料本錢函數(shù)，即決策的目的函數(shù)為Z=10x1+20x2。思索三種營養(yǎng)含量限制條件后，可得這一問題的線性規(guī)劃模型如下：MinZ=10x1+20x2x1+x2≥103x1+x2≥15x1+6x2≥15x1≥0,x2≥0一、建模[例2]某農(nóng)戶方案用12公頃耕地消費(fèi)玉米，大豆和地瓜，可投入48個勞動日，資金360元。消費(fèi)玉米1公頃，需6個勞動日，資金36元，可獲凈收入200元；消費(fèi)1公頃大豆，需6個勞動日，資金24元，可獲凈收入150元；消費(fèi)1公頃地瓜需2個勞動日，資金18元，可獲凈收入1200元，問怎樣安排才干使總的凈收入最高。設(shè)種玉米，大豆和地瓜的數(shù)量分別為x1、x2和x3公頃，根據(jù)問題建立線性規(guī)劃問題模型如下：一、建模MaxZ=200x1+150x2+100x3x1+x2+x3≤12 (1)6x1+6x2+2x3≤48 (2)36x1+24x2+18x3≤360 (3)x1≥0，x2≥0，x3≥0

一、建模[例3]某農(nóng)戶有耕地20公頃，可采用甲乙兩種種植方式。甲種植方式每公頃需投資280元，每公頃投工6個，可獲收入1000元，乙方式每公頃需投資150元，勞動15個工日，可獲收入1200元，該戶共有可用資金4200元、240個勞開工日。問如何安排甲乙兩種方式的消費(fèi)，可使總收入最大?解：設(shè)甲方式種x1公頃，乙方式種x2公頃，總收入為Z，那么有：一、建模MaxZ=1000x1+1200x2280x1+150x2≤42006x1+15x2≤240x1+x2≤20x1≥0,x2≥0

二、線性規(guī)劃的求解——圖解法〔一〕可行解〔二〕可行域〔三〕最優(yōu)解〔四〕最優(yōu)性定理〔五〕最大化問題的圖解法〔六〕最小化問題的圖解法二、線性規(guī)劃的求解——圖解法〔一〕可行解線性規(guī)劃問題的可行解是指，滿足規(guī)劃中一切約束條件及非負(fù)約束的決策變量的一組取值，其僅與約束條件有關(guān)而與目的函數(shù)值的大小無關(guān)?！捕晨尚杏蚩尚杏蚴怯梢磺锌尚薪鈽?gòu)成的集合。根據(jù)線性規(guī)劃的根本實(shí)際，任一個線性規(guī)劃問題的可行域，都是一個有限或無限的凸多邊形，凸多邊形的每個角，稱為可行域的極點(diǎn)。〔三〕最優(yōu)解線性規(guī)劃的最優(yōu)解是指，使目的函數(shù)值到達(dá)最優(yōu)(最大或最小)的可行解。一個線性規(guī)劃問題可以是有解的，也能夠是無解的，最優(yōu)解的個數(shù)能夠是獨(dú)一的，也能夠是有無窮多個，即決策變量有許多組不同的取值，都使目的函數(shù)到達(dá)同一個最優(yōu)值。二、線性規(guī)劃的求解——圖解法〔四〕最優(yōu)性定理假設(shè)一個線性規(guī)劃問題有最優(yōu)解，那么最優(yōu)解一定可以在可行域的某個極點(diǎn)上找到一個最優(yōu)解。同時仍有能夠有其他最優(yōu)解存在，但它們也只能夠存在于可行域的其他極點(diǎn)或是邊境上。假設(shè)我們的目的是找出一個最優(yōu)解而不是全部最優(yōu)解，這一定理實(shí)踐上是把尋覓的范圍，從可行域中的無窮多個可行點(diǎn)，減少到可行域的有限幾個極點(diǎn)上。二、線性規(guī)劃的求解——圖解法〔五〕最大化問題的圖解法第一步，找出問題的可行域第二步，在可行域中尋求最優(yōu)解，方法有兩種：A.查點(diǎn)法B.圖解法二、線性規(guī)劃的求解——圖解法

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二、線性規(guī)劃的求解——圖解法〔五〕最小化問題的圖解法例：MinZ=10x1+20x2s.t.x1+x2≥103x1+x2≥15x1+6x2≥15x1≥0,x2≥01515105105OABCDx2x1x1+6x2=15可行域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第三節(jié)單純形法單純形方法是一種較為完善的、步驟化的線性規(guī)劃問題求解方法。它的原理涉及到較多的數(shù)學(xué)實(shí)際上的推導(dǎo)和證明，我們在此僅引見這種方法的詳細(xì)操作步驟及每一步的經(jīng)濟(jì)上的含義。為更好地闡明問題，我們?nèi)越Y(jié)合實(shí)例引見這種方法第三節(jié)單純形法一、線性規(guī)劃的規(guī)范型二、線性規(guī)劃問題的解三、單純形法四、單純型表第三節(jié)單純形法一線性規(guī)劃的規(guī)范型LP目的函數(shù)有的要務(wù)虛現(xiàn)最大化，有的要務(wù)虛現(xiàn)最小化，約束條件可以是“<=〞、“>=〞、“＝〞，這種多樣性給討論問題帶來不便。為了便于討論，我們規(guī)定線性規(guī)劃問題的規(guī)范方式為：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ī)劃的規(guī)范型用向量表示其中C=(c1,c2,……cn)

向量Pj是其對應(yīng)變量xj的系數(shù)向量。第三節(jié)單純形法一線性規(guī)劃的規(guī)范型用矩陣描畫

第三節(jié)單純形法二線性規(guī)劃問題的解可行解最優(yōu)解基設(shè)A為約束方程組的m×n階系數(shù)矩陣，其秩為m。B是矩陣A中m×m階非奇特子矩陣〔〕,那么稱B是線性規(guī)劃問題的一個基。不失普通性可設(shè)稱Pj為基向量，與基變量Pj相對應(yīng)的變量為基變量。否那么為非基變量。為了進(jìn)一步討論線性規(guī)劃問題的解，我們來研討約束方程組求解的問題。假設(shè)方程組系數(shù)矩陣Z的秩為m，因m小于n故它有無窮多個解。假設(shè)前m個變量的系數(shù)列向量是線性獨(dú)立的，這時線性規(guī)劃模型可寫成:二線性規(guī)劃問題的解或設(shè)非基變量用高斯消去法，可求出一個解稱X為根本解根本可行解滿足非負(fù)條件的根本解二線性規(guī)劃問題的解[例3]某工廠在方案期內(nèi)安排消費(fèi)x1x2兩種產(chǎn)品，這些產(chǎn)品分別需求在A、B、C、D四種不同的設(shè)備上加工。按工藝規(guī)定，產(chǎn)品x1和產(chǎn)品x2在各設(shè)備上加工的臺時數(shù)見下表。知各設(shè)備在方案期內(nèi)有效臺時數(shù)分別是12、8、16和12。〔一臺設(shè)備任務(wù)一小時稱為一臺時〕該工廠每消費(fèi)一件產(chǎn)品x1可得利潤2元，每消費(fèi)一件產(chǎn)品x2可得利潤3元，問如何安排消費(fèi)方案，才干得到利潤最多？三單純形法設(shè)備產(chǎn)品ABCDx12140x22204三單純形法〔一〕求解過程〔二〕求解過程小結(jié)三單純形法MaxZ=2x1+3x22x1+2x2≤12x1+2x2≤84x1≤16 4x2≤12x1≥0，x2≥0引入松弛變量x3—A設(shè)備閑置臺時數(shù)x4—B設(shè)備閑置臺時數(shù)x5—C設(shè)備閑置臺時數(shù)x6—D設(shè)備閑置臺時數(shù)將線性規(guī)劃化為規(guī)范型.〔8.1〕三單純形法求解過程MaxZ=2x1+3x2+x3+x4+x5+x62x1+2x2+x3=12 x1+2x2+x4=84x1+x5=16 4x2+x6=12x1≥0，x2≥0,x3≥0，x4≥0,x5≥0，x6≥0〔8.2〕三單純形法求解過程x3,x4,x5,x6的系數(shù)列向量p3,p4,p5,p6是線性獨(dú)立的，這些列向量構(gòu)成一個基系數(shù)矩陣三單純形法求解過程x3=12－2x1－2x2 x4=8－x1－2x2x5=16－4x1 x6=12－4x2把上式帶入目的函數(shù)得到Z=0+2x1+3x2〔8.4〕當(dāng)非基變量x1=x2=0,便得z=0，這時得到一個根本可行解X(0)對應(yīng)于B的變量x3,x4,x5,x6為基變量，從規(guī)范型我們可以得到：〔8.3〕三單純形法求解過程這個根本可行解表示：工廠沒有安排消費(fèi)產(chǎn)品；設(shè)備的有效臺時數(shù)沒有被利用，所以構(gòu)成的利潤為0。從分析目的函數(shù)的表達(dá)式可以看到，非基變量x1,x2系數(shù)都是正數(shù)，假設(shè)將非基變量換成基變量，目的函數(shù)就會添加。所以，只需在目的函數(shù)的表達(dá)式中還存在正系數(shù)的非基變量，這表示目的函數(shù)還有添加的能夠，就需求將非基變量換成基變量。普通選擇正系數(shù)最大的那個非基變量?？砂匆韵路椒▉泶_定換出變量。三單純形法求解過程現(xiàn)分析〔8.4〕，將x2定為換入變量后，必需從x3,x4,x5,x6中換出一個，并保證其他的都是非負(fù)，即x3,x4,x5,x6≥0當(dāng)x1＝0，由〔8.3〕式得到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〕時，才干使〔8.5〕式成立。因當(dāng)x2=3時，基變量x6=0這就決議用x2去交換x6。三單純形法求解過程為了求得以x3,x4,x5,x2為基變量的一個根本可行解和進(jìn)一步分析問題，需將〔8.5〕中的x2位置與x6的位置兌換。得到x3＋2x2=12－2x1 x4＋2x2=8－x1〔8.6〕x5=16－4x1 4x2=12－x6用高斯消去法，將〔8.6〕式中的x2的系數(shù)列向量變?yōu)閱挝涣邢蛄?。x3=6－2x1+1/2x6 x4=2－x1+1/2x6〔8.7〕x5=16－4x1 x2=3－1/4x6三單純形法求解過程再將〔8.7〕代入〔8.1〕目的函數(shù)得到：Z=9+2x1-3/4x6〔8.8〕當(dāng)非基變量x1=x6=0，得到Z=9，并得到另一個根本可行解三單純形法求解過程從目的函數(shù)的表達(dá)式〔8.8〕中可看到，非基變量x1的系數(shù)是正的，闡明目的函數(shù)值還可以增大，X(1)不一定是最優(yōu)解。于是用上述方法，確定換入換出變量，繼續(xù)迭代，再得到另一個根本可行解X(2)再經(jīng)過一次迭代，又得到一個根本可行解這時得到的目的函數(shù)的表達(dá)式是：Z=14-1.5x4-0.125x5目的函數(shù)值到達(dá)最大，X(3)是線性規(guī)劃的最優(yōu)解。三單純形法求解過程1.人造基、初始根本可行解2.最優(yōu)性檢驗(yàn)三單純形法求解過程小結(jié)1.人造基、初始根本可行解1.1假設(shè)從線性規(guī)劃問題的Pj中能直接察看到存在m個線性獨(dú)立的單位向量，經(jīng)過重新安排次序便得到一個可行基三單純形法求解過程小結(jié)1.人造基、初始根本可行解1.2“≤〞規(guī)范化的方法，引入非負(fù)的松弛變量重新對xj及aij編號，經(jīng)整理那么可得到以下方程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顯然得到一個單位陣

三單純形法求解過程小結(jié)我們就將B作為可行基。將〔8.9〕每個等式進(jìn)展移項(xià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)得到一個初始根本可行解三單純形法求解過程小結(jié)2.最優(yōu)性檢驗(yàn)得到初始可行解后，要檢驗(yàn)一下能否是最優(yōu)解，假設(shè)是，那么停頓迭代，假設(shè)不是，那么繼續(xù)迭代……。但每次迭代后都要檢驗(yàn)一下能否是最優(yōu)解，為此需求建立一個判別準(zhǔn)那么。普通情況下，經(jīng)過迭代后式變成〔i=1,2,3,……,m〕將上式代入目的函數(shù)，整理后得三單純形法求解過程小結(jié)j=m+1,……,n三單純形法求解過程小結(jié)2.1最優(yōu)解判別定理：假設(shè)為對應(yīng)于B的根本可行解，且對于一切j=m+1,……,n有，那么X〔0〕為最優(yōu)解。無有限最優(yōu)解判別定理：假設(shè)為對應(yīng)于B的根本可行解，有一個并且對于一切i=1,2,3,……,m有，那么該線性規(guī)劃沒有有限最優(yōu)解。2.2換入變量確實(shí)定2.3換出變量確實(shí)定，為換入變量。三單純形法求解過程小結(jié)三單純形表例1例1例1例1例2例2例2目的函數(shù)系數(shù)靈敏度分析右邊值靈敏度分析第四節(jié)靈敏度分析目的函數(shù)系數(shù)靈敏度分析最優(yōu)解不變的條件下，允許C的變化范圍，最優(yōu)解不變的前提是σj≤0假設(shè)玉米價值系數(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目的函數(shù)系數(shù)