線性規(guī)劃模型的建立與應用

1、第七章第七章 線性規(guī)劃模型的建立與應用線性規(guī)劃模型的建立與應用學習目的與要求 線性規(guī)劃是經(jīng)濟領域廣泛應用的一種經(jīng)濟分析方法。講授本章目的是使同學掌握線性規(guī)劃分析法的基本原理，掌握圖解法和單純形解法的程序及運算，并借助電化教學，能夠初步應用線性規(guī)劃法解決最低成本的農(nóng)業(yè)生產(chǎn)資源最優(yōu)配合方式和最大收益的生產(chǎn)結構問題。 第七章第七章 線性規(guī)劃模型的建立與應用線性規(guī)劃模型的建立與應用一、線性規(guī)劃的概念二、線性規(guī)劃三要素三、技術經(jīng)濟研究中運用線性規(guī)劃方法的特點及局限性四、線性規(guī)劃模型的基本結構五、線性規(guī)劃模型的一般形式六、線性規(guī)劃模型的基本假設 第一節(jié) 線性規(guī)劃模型的基本原理 線性規(guī)劃是指如何最有效或最佳

2、地謀劃經(jīng)濟活動。它所研究的問題有兩類： 一類是指一定資源的條件下，達到最高產(chǎn)量、最高產(chǎn)值、最大利潤； 一類是，任務量一定，如何統(tǒng)籌安排，以最小的消耗取完成這項任務。如最低成本問題、最小投資、最短時間、最短距離等問題。前者是求極大值問題，后者是求極小值問題。總之，線性規(guī)劃是一定限制條件下，求目標函數(shù)極值的問題。 第一節(jié) 線性規(guī)劃模型的基本原理 一、線性規(guī)劃的概念 經(jīng)濟大詞典定義線性規(guī)劃：一種具有確定目標，而實現(xiàn)目標的手段又有一定限制，且目標和手段之間的函數(shù)關系是線性的條件下，從所有可供選擇的方案中求解出最優(yōu)方案的數(shù)學方法。 第一節(jié) 線性規(guī)劃模型的基本原理 一、線性規(guī)劃的概念二、線性規(guī)劃三要素1.

3、目標函數(shù)最優(yōu)化單一目標 多重目標問題如何處理？2.實現(xiàn)目標的多種方法 若實現(xiàn)目標只有一種方法不存在規(guī)劃問題。 3.生產(chǎn)條件的約束資源是有限的 資源無限不存在規(guī)劃問題。 第一節(jié) 線性規(guī)劃模型的基本原理 三、技術經(jīng)濟研究中運用線性規(guī)劃方法的特點及局限性 第一節(jié) 線性規(guī)劃模型的基本原理 特點：1.可以使研究對象具體化、數(shù)量化?？梢詫λ芯康募夹g經(jīng)濟問題做出明確的結論；2.線性3.允許出現(xiàn)生產(chǎn)要素的剩余量4.有一套完整的運算程序三、技術經(jīng)濟研究中運用線性規(guī)劃方法的特點及局限性 第一節(jié) 線性規(guī)劃模型的基本原理 局限性：1. 線性規(guī)劃它是以價格不變和技術不變?yōu)榍疤釛l件的，不能處理涉及到時間因素的問題。因此

4、，線性規(guī)劃只能以短期計劃為基礎。2.在生產(chǎn)活動中，投入產(chǎn)出的關系不完全是線性關系，由于在一定的技術條件下，報酬遞減規(guī)律起作用，所以要滿足線性假定是不可能的。在線性規(guī)劃解題中，常常把投入產(chǎn)出的非線性關系轉化為線性關系來處理，以滿足線性的假定性，客觀上產(chǎn)生誤差。3.線性規(guī)劃本身只是一組方程式，并不提供經(jīng)濟概念，它不能代替人們對現(xiàn)實經(jīng)濟問題的判斷。 四、線性規(guī)劃模型的基本結構1.決策變量 未知數(shù)。它是通過模型計算來確定的決策因素。又分為實際變量求解的變量和計算變量，計算變量又分松弛變量（上限）和人工變量（下限）。2.目標函數(shù)經(jīng)濟目標的數(shù)學表達式。目標函數(shù)是求變量的線性函數(shù)的極大值和極小值這樣一個極值

5、問題。 3.約束條件實現(xiàn)經(jīng)濟目標的制約因素。它包括：生產(chǎn)資源的限制（客觀約束條件）、生產(chǎn)數(shù)量、質量要求的限制（主觀約束條件）、特定技術要求和非負限制。 第一節(jié) 線性規(guī)劃模型的基本原理 四、線性規(guī)劃模型的基本結構 Min Z=10 x1+20 x2 s.t. x1+x210 3x1+x215 x1+6x215 x10 , x20 約束條件目標函數(shù)第一節(jié) 線性規(guī)劃模型的基本原理 五、線性規(guī)劃模型的一般形式Max Z=c1x1+c2x2+c3x3+cnxn a11x1+a12x2+a1nxn b1 (1) a21x1+a22x2+a2nxn b2 (2) am1x1+am2x2+amnxn bm (

6、m) x1 ，x2 ，xn0第一節(jié) 線性規(guī)劃模型的基本原理 極大值模型njxbxaxcxcxcZjinjjijnn, 3 , 2 , 1,0max12211其簡縮形式為其簡縮形式為 第一節(jié) 線性規(guī)劃模型的基本原理 極大值模型五、線性規(guī)劃模型的一般形式Min Z=c1x1+c2x2+c3x3+cnxn a11x1+a12x2+a1nxn b1 (1) a21x1+a22x2+a2nxn b2 (2) am1x1+am2x2+amnxn bm (m) x1 ，x2 ，xn0第一節(jié) 線性規(guī)劃模型的基本原理 極小值模型njxbxaxcxcxcZjinjjijnn, 3 , 2 , 1,0min1221

7、1其簡縮形式為其簡縮形式為 第一節(jié) 線性規(guī)劃模型的基本原理 極小值模型其簡縮形式為其簡縮形式為 第一節(jié) 線性規(guī)劃模型的基本原理 極大值模型可用向量表示： 01jnjjjxbxPCXzMaxnxxxX21mjjjjaaaP21bmbbb21 C=(c1,c2,cn) 六、線性規(guī)劃模型的基本假設1.線性線性 目標函數(shù)和約束條件目標函數(shù)和約束條件2.可分性可分性 活動對資源的可分性活動對資源的可分性3.可加性可加性 活動所耗資源的可加性，資源總需要活動所耗資源的可加性，資源總需要量為多種活動所需資源數(shù)量的總和。量為多種活動所需資源數(shù)量的總和。4.明確性明確性 目標的明確性目標的明確性5.單一性單一性

8、 期望值的單一性期望值的單一性6.獨立性獨立性 變量是獨立的表示各種作業(yè)對資源都變量是獨立的表示各種作業(yè)對資源都是互竟關系，沒有互助關系是互竟關系，沒有互助關系7.非負性非負性第二節(jié) 線性規(guī)劃模型的建立與圖解法求解一、建模二、線性規(guī)劃的求解圖解法一、建模例例1某飼料公司用甲、乙兩種原料配制飼料，甲乙兩種原料的營養(yǎng)成份及配合飼料中所含各營養(yǎng)成份最低量由表1給出。已知單位甲、乙原料的價格分別為10元和20元，求滿足營養(yǎng)需要的飼料最小成本配方。 一、建模 設配合飼料中，用甲x1單位，用乙x2單位，則配合飼料的原料成本函數(shù)，即決策的目標函數(shù)為Z=10 x1+20 x2?？紤]三種營養(yǎng)含量限制條件后，可得

9、這一問題的線性規(guī)劃模型如下： Min Z=10 x1+20 x2 x1+x210 3x1+x215 x1+6x215 x10 , x20一、建模例例2某農(nóng)戶計劃用12公頃耕地生產(chǎn)玉米，大豆和地瓜，可投入48個勞動日，資金360元。生產(chǎn)玉米1公頃，需6個勞動日，資金36元，可獲凈收入200元；生產(chǎn)1公頃大豆，需6個勞動日，資金24元，可獲凈收入150元；生產(chǎn)1公頃地瓜需2個勞動日，資金18元，可獲凈收入1200元，問怎樣安排才能使總的凈收入最高。 設種玉米，大豆和地瓜的數(shù)量分別為x1、x2和x3公頃，根據(jù)問題建立線性規(guī)劃問題模型如下： 一、建模Max Z=200 x1+150 x2+100 x3

10、 x1+x2+x312(1) 6x1+6x2+2x348(2) 36x1+24x2+18x3360(3) x10，x20，x30 一、建模 例例33某農(nóng)戶有耕地20公頃，可采用甲乙兩種種植方式。甲種植方式每公頃需投資280元，每公頃投工6個，可獲收入1000元，乙方式每公頃需投資150元，勞動15個工日，可獲收入1200元，該戶共有可用資金4200元、240個勞動工日。問如何安排甲乙兩種方式的生產(chǎn)，可使總收入最大?解：設甲方式種x1公頃，乙方式種x2公頃，總收入為Z，則有： 一、建模Max Z=1000 x1+1200 x2 280 x1+150 x24200 6x1+15x2240 x1+x

11、220 x10,x20 二、線性規(guī)劃的求解圖解法（一）可行解 （二）可行域 （三）最優(yōu)解（四）最優(yōu)性定理 （五）最大化問題的圖解法（六）最小化問題的圖解法 二、線性規(guī)劃的求解圖解法 （一）可行解 線性規(guī)劃問題的可行解是指，滿足規(guī)劃中所有約束條件及非負約束的決策變量的一組取值，其僅與約束條件有關而與目標函數(shù)值的大小無關。 （二）可行域 可行域是由所有可行解構成的集合。根據(jù)線性規(guī)劃的基本理論，任一個線性規(guī)劃問題的可行域，都是一個有限或無限的凸多邊形，凸多邊形的每個角，稱為可行域的極點。 （三）最優(yōu)解 線性規(guī)劃的最優(yōu)解是指，使目標函數(shù)值達到最優(yōu)(最大或最小)的可行解。一個線性規(guī)劃問題可以是有解的，也

12、可能是無解的，最優(yōu)解的個數(shù)可能是惟一的，也可能是有無窮多個，即決策變量有許多組不同的取值，都使目標函數(shù)達到同一個最優(yōu)值。 二、線性規(guī)劃的求解圖解法 （四）最優(yōu)性定理 若一個線性規(guī)劃問題有最優(yōu)解，則最優(yōu)解一定可以在可行域的某個極點上找到一個最優(yōu)解。同時仍有可能有其他最優(yōu)解存在，但它們也只可能存在于可行域的其他極點或是邊界上。如果我們的目的是找出一個最優(yōu)解而不是全部最優(yōu)解，這一定理實際上是把尋找的范圍，從可行域中的無窮多個可行點，縮小到可行域的有限幾個極點上。 二、線性規(guī)劃的求解圖解法 （五）最大化問題的圖解法第一步，找出問題的可行域第二步，在可行域中尋求最優(yōu)解，方法有兩種 ： A.查點法 B.圖

13、解法二、線性規(guī)劃的求解圖解法 O 20 40 x120ABCD280 x1+150 x2=42006x1+15x2=240 x1+x2=20 x2Z=1000 x1+1200 x2A(0,16)B(6.7,13.3)C(9.2,10.8)D(15,0)ZA=19200ZB=22660ZC=22160ZD=15000二、線性規(guī)劃的求解圖解法 （五）最小化問題的圖解法w 例：Min Z=10 x1+20 x2w s.t. x1+x210w 3x1+x215w x1+6x215w x10, x201515105105OABCDx2x1x1+6x2=15可行域3x1+x2=15x1+x2=1010 x

14、1+20 x20A(0,15)B(2.5,7.5)C(9,1)D (15,0)ZA=300ZB=175ZC=110ZD=150第三節(jié) 單純形法 單純形方法是一種較為完善的、步驟化的線性規(guī)劃問題求解方法。它的原理涉及到較多的數(shù)學理論上的推導和證明，我們在此僅介紹這種方法的具體操作步驟及每一步的經(jīng)濟上的含義。為更好地說明問題，我們?nèi)越Y合實例介紹這種方法 第三節(jié) 單純形法一、線性規(guī)劃的標準型二、線性規(guī)劃問題的解三、單純形法 四、單純型表第三節(jié) 單純形法一線性規(guī)劃的標準型LP目標函數(shù)有的要求實現(xiàn)最大化，有的要求實現(xiàn)最小化，約束條件可以是“=”、“”，這種多樣性給討論問題帶來不便。為了便于討論，我們規(guī)定

15、線性規(guī)劃問題的標準形式為：Max Z=c1x1+c2x2+c3x3+cnxn a11x1+a12x2+a1nxn=b1 (1) a21x1+a22x2+a2nxn=b2 (2) am1x1+am2x2+amnxn=bm (m) x1 ，x2 ，xn0 第三節(jié) 單純形法其簡縮形式為 一線性規(guī)劃的標準型njxbxaxcxcxcZjinjjijnn, 3 , 2 , 1,0max12211用向量表示 01jnjjjxbxPnxxxX21mjjjjaaaP21bmbbb21 其中 C=(c1,c2,cn) 向量Pj是其對應變量xj 的系數(shù)向量。 第三節(jié) 單純形法一線性規(guī)劃的標準型用矩陣描述CXzMax

16、0XbAX mnmnmmnbbbbbPPPaaaaaaA321212111211;第三節(jié) 單純形法二線性規(guī)劃問題的解 可行解可行解最優(yōu)解最優(yōu)解 基基 設A為約束方程組的mn階系數(shù)矩陣，其秩為m。B是矩陣A中mm階非奇異子矩陣（ ）,則稱B是線性規(guī)劃問題的一個基。不失一般性可設 0BmmmmmmPPPaaaaaaB212111211稱Pj為基向量，與基變量Pj相對應的變量為基變量。否則為非基變量。 w 為了進一步討論線性規(guī)劃問題的解，我們來研究約束方程組求解的問題。假設方程組系數(shù)矩陣Z的秩為m，因m小于n故它有無窮多個解。假設前m個變量的系數(shù)列向量是線性獨立的，這時線性規(guī)劃模型可寫成 :二線性規(guī)

17、劃問題的解 nmnnnmmmmmmmmmmmmmxaaaxaaabbbxaaaxaaaxaaa211112112121122212112111nmjjjmjjjxPbxP11或 021nmmxxxTmxxxX)0 , 0 ,(21設非基變量用高斯消去法，可求出一個解稱X為基本解基本解基本可行解基本可行解 滿足非負條件的基本解二線性規(guī)劃問題的解 w 例例3某工廠在計劃期內(nèi)安排生產(chǎn)x1 x2兩種產(chǎn)品，這些產(chǎn)品分別需要在A、B、C、D四種不同的設備上加工。按工藝規(guī)定，產(chǎn)品x1和產(chǎn)品x2在各設備上加工的臺時數(shù)見下表。已知各設備在計劃期內(nèi)有效臺時數(shù)分別是12、8、16和12。（一臺設備工作一小時稱為一臺

18、時）該工廠每生產(chǎn)一件產(chǎn)品x1可得利潤2元，每生產(chǎn)一件產(chǎn)品x2可得利潤3元，問如何安排生產(chǎn)計劃，才能得到利潤最多？ 三單純形法 設備產(chǎn)品ABCDx12140 x22204三單純形法w （一）求解過程 w （二）求解過程小結三單純形法Max Z=2x1+3 x2 2x1+2x212 x1+2x28 4x1 16 4x2 12 x10，x20 引入松弛變量x3 A設備閑置臺時數(shù)x4 B設備閑置臺時數(shù)x5 C設備閑置臺時數(shù)x6D設備閑置臺時數(shù)將線性規(guī)劃化為標準型.（8.1） 三單純形法 求解過程Max Z=2x1+3 x2+ x3+ x4+ x5+ x6 2x1+2x2+ x3 =12 x1+2x2

19、+ x4 =8 4x1 + x5 =16 4x2 + x6 =12 x10，x20, x30，x40 ,x50，x60 （8.2） 三單純形法 求解過程 x3, x4, x5, x6的系數(shù)列向量p3, p4, p5, p6是線性獨立的，這些列向量構成一個基 系數(shù)矩陣 100040010004001021000122654321PPPPPPA10000100001000016543PPPPB三單純形法 求解過程x3 = 122x12x2 x4 = 8x12x2 x5 = 164x1 x6 = 124x2 把上式帶入目標函數(shù)得到 Z=0+2x1+3 x2 （8.4） 當非基變量x1=x2=0,便得

20、z=0，這時得到一個基本可行解X(0) 對應于B的變量x3, x4, x5, x6為基變量，從標準型我們可以得到： （8.3） 三單純形法 求解過程TxxxxxxX121681200121681200)0(6)0(5)0(4)0(3)0(2)0(1)0(這個基本可行解表示：工廠沒有安排生產(chǎn)產(chǎn)品；設備的有效臺時數(shù)沒有被利用，所以構成的利潤為0。 從分析目標函數(shù)的表達式可以看到，非基變量x1 ,x2系數(shù)都是正數(shù)，若將非基變量換成基變量，目標函數(shù)就會增加。所以，只要在目標函數(shù)的表達式中還存在正系數(shù)的非基變量，這表示目標函數(shù)還有增加的可能，就需要將非基變量換成基變量。一般選擇正系數(shù)最大的那個非基變量。

21、可按以下方法來確定換出變量。三單純形法 求解過程 現(xiàn)分析（8.4），將x2定為換入變量后，必須從x3, x4, x5, x6中換出一個，并保證其余的都是非負，即x3, x4, x5, x60 當x10，由（8.3）式得到 x3 = 122x2 0 x4 = 82x20 （8.5） x5 = 160 x6 = 124x2 0 從（8.5）式中可以看出，只有選擇 Z=0+2x1+3 x2 （8.4）3412,28,212min2x時，才能使（8.5）式成立。因當x2=3時，基變量x6=0這就決定用x2去替換x6。三單純形法 求解過程為了求得以x3, x4, x5, x2為基變量的一個基本可行解和進

22、一步分析問題，需將（8.5）中的x2位置與x6的位置兌換。得到x3 2x2 = 122x1 x4 2x2 = 8x1 （8.6） x5 = 164x1 4x2 = 12 x6 用高斯消去法，將（8.6）式中的x2的系數(shù)列向量變?yōu)閱挝涣邢蛄?。x3 = 62x1+1/2x6 x4 = 2x1+1/2x6 （8.7） x5 = 164x1 x2 = 31/4x6三單純形法 求解過程w 再將（8.7）代入（8.1）目標函數(shù)得到：w Z=9+2x1-3/4 x6 （8.8） w 當非基變量x1=x6=0，得到Z=9，并得到另一個基本可行解TTxxxxxxX)0 ,16, 2 , 6 , 3 , 0(),

23、() 1 (6) 1 (5) 1 (4) 1 (3) 1 (2) 1 (1) 1 (三單純形法 求解過程 從目標函數(shù)的表達式（8.8）中可看到，非基變量x1的系數(shù)是正的，說明目標函數(shù)值還可以增大，X(1)不一定是最優(yōu)解。于是用上述方法，確定換入換出變量，繼續(xù)迭代，再得到另一個基本可行解X(2) 再經(jīng)過一次迭代，又得到一個基本可行解 這時得到的目標函數(shù)的表達式是： Z = 14-1.5x4-0.125 x5 目標函數(shù)值達到最大，X(3)是線性規(guī)劃的最優(yōu)解。 TX)0 , 8 , 0 , 2 , 3 , 2()2(TX)4 , 0 , 0 , 0 , 2 , 4()3(三單純形法 求解過程w 1.

24、人造基、初始基本可行解 w 2.最優(yōu)性檢驗 三單純形法 求解過程小結w 1.人造基、初始基本可行解 w 1.1若從線性規(guī)劃問題的 Pj中能直接觀察到存在m個線性獨立的單位向量，經(jīng)過重新安排次序便得到一個可行基jnjjxczMax101jnjjjxbxP10001000121MPPPB三單純形法 求解過程小結w 1.人造基、初始基本可行解 w 1.2“”標準化的方法，引入非負的松弛變量重新對xj及aij編號，經(jīng)整理則可得到下列方程 Max Z=c1x1+c2x2+c3x3+cnxn x1 +a1m+1xm+1+a1m+2xm+2+a1nxn =b1 x2 +a2m+1x m+1+a2m+2x m

25、+2+a2nxn=b2 （8.9） xm +amm+1x m+1+amm+2x m+2+amnxn=bm x1 ，x2 ，xn0顯然得到一個單位陣 10001000121MPPPB三單純形法 求解過程小結我們就將B作為可行基。將（8.9）每個等式進行移項得 x1 =b1 -a1m+1xm+1-a1m+2xm+2-a1nxn x2 =b2 -a2m+1x m+1-a2m+2x m+2-a2nxn （8.10） xm =bm -amm+1x m+1-amm+2x m+2-amnxn x1 ，x2 ，xn0令x m+1 = x m+2 =x n=0,由（8.10）可得xi=bi(I=1,2,m)得到

26、一個初始基本可行解TmnmTmnmbbbxxxX)0, 0,()0, 0,(2121個個，三單純形法 求解過程小結2.最優(yōu)性檢驗w 得到初始可行解后，要檢驗一下是否是最優(yōu)解，如果是，則停止迭代，如果不是，則繼續(xù)迭代。但每次迭代后都要檢驗一下是否是最優(yōu)解，為此需要建立一個判別準則。w 一般情況下，經(jīng)過迭代后式變成w （i=1,2,3,m） w 將上式代入目標函數(shù)，整理后得nmjjijiixabx1三單純形法 求解過程小結nmjjijmiijimiiixaccbcz111)(ijmiijimiiaczbcz110,j=m+1,n nmjjjjxzczz10)(), 1(nmjzcjjjnmjjjx

27、zz10三單純形法 求解過程小結w 2.1最優(yōu)解判別定理：w 若 為對應于B的基本可行解，且對于一切j=m+1,n有 ，則X（0）為最優(yōu)解。w 無有限最優(yōu)解判別定理：w 若 為對應于B的基本可行解，有一個 并且對于一切i=1,2,3,m有， 那么該線性規(guī)劃沒有有限最優(yōu)解。w 2.2換入變量的確定w 2.3換出變量的確定 ，w 為換入變量。TmbbbX)0, 0(, 2, 1)0(0j0kmTmbbbX)0, 0(, 2, 1)0(0,kmia為換入變量則對應的kkjx )0max(ckcikikabaabRi0mincx三單純形法 求解過程小結三單純形表例1例1例1例1例2例2例2w 目標函數(shù)

28、系數(shù)靈敏度分析w 右邊值靈敏度分析第四節(jié) 靈敏度分析目標函數(shù)系數(shù)靈敏度分析w 最優(yōu)解不變的條件下，允許C的變化范圍，最優(yōu)解不變的前提是j 0w 假設玉米價值系數(shù)C1發(fā)生了變化，其變化量為1 x x1 1x x2 2x x3 3x x4 4x x5 5x x6 61 10 00 0 x x3 36 60 00 01 13 3/ /2 2- -0 0. .2 25 50 02 20 00 0+ +1 1x x1 16 61 11 10 0- -0 0. .5 51 1/ /4 40 00 0 x x6 63 36 60 0- -1 12 20 0- -9 9- -4 4. .5 51 12 20 00 0+ +1 11 15 50 01 10 00 00 00 00 01 18 80 00 02 20 00 0+ +1 12 20 00 0+ +1 11 10 00 05 50 0- -0 0. .5 51 12 25 5+ +0 0. .2 25 51 10 01 18 80 00 00 0- -5 50 0- -1 10 0- -5 50 0+ +0 0. .5 51 1- -2 25 5- -0 0. .2 25 51 10 0實實際際活活動動松松弛弛活活動動目目標標系系數(shù)數(shù)行行c cj j機機會會成成本本行行Z Z