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

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

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

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

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

5、問題。 3.約束條件實(shí)現(xiàn)經(jīng)濟(jì)目標(biāo)的制約因素。它包括：生產(chǎn)資源的限制（客觀約束條件）、生產(chǎn)數(shù)量、質(zhì)量要求的限制（主觀約束條件）、特定技術(shù)要求和非負(fù)限制。 第一節(jié) 線性規(guī)劃模型的基本原理 四、線性規(guī)劃模型的基本結(jié)構(gòu) Min Z=10 x1+20 x2 s.t. x1+x210 3x1+x215 x1+6x215 x10 , x20 約束條件目標(biāo)函數(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ī)劃模型的基本假設(shè)1.線性線性 目標(biāo)函數(shù)和約束條件目標(biāo)函數(shù)和約束條件2.可分性可分性 活動(dòng)對(duì)資源的可分性活動(dòng)對(duì)資源的可分性3.可加性可加性 活動(dòng)所耗資源的可加性，資源總需要活動(dòng)所耗資源的可加性，資源總需要量為多種活動(dòng)所需資源數(shù)量的總和。量為多種活動(dòng)所需資源數(shù)量的總和。4.明確性明確性 目標(biāo)的明確性目標(biāo)的明確性5.單一性單一性

8、 期望值的單一性期望值的單一性6.獨(dú)立性獨(dú)立性 變量是獨(dú)立的表示各種作業(yè)對(duì)資源都變量是獨(dú)立的表示各種作業(yè)對(duì)資源都是互竟關(guān)系，沒有互助關(guān)系是互竟關(guān)系，沒有互助關(guān)系7.非負(fù)性非負(fù)性第二節(jié) 線性規(guī)劃模型的建立與圖解法求解一、建模二、線性規(guī)劃的求解圖解法一、建模例例1某飼料公司用甲、乙兩種原料配制飼料，甲乙兩種原料的營養(yǎng)成份及配合飼料中所含各營養(yǎng)成份最低量由表1給出。已知單位甲、乙原料的價(jià)格分別為10元和20元，求滿足營養(yǎng)需要的飼料最小成本配方。 一、建模 設(shè)配合飼料中，用甲x1單位，用乙x2單位，則配合飼料的原料成本函數(shù)，即決策的目標(biāo)函數(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)戶計(jì)劃用12公頃耕地生產(chǎn)玉米，大豆和地瓜，可投入48個(gè)勞動(dòng)日，資金360元。生產(chǎn)玉米1公頃，需6個(gè)勞動(dòng)日，資金36元，可獲凈收入200元；生產(chǎn)1公頃大豆，需6個(gè)勞動(dòng)日，資金24元，可獲凈收入150元；生產(chǎn)1公頃地瓜需2個(gè)勞動(dòng)日，資金18元，可獲凈收入1200元，問怎樣安排才能使總的凈收入最高。 設(shè)種玉米，大豆和地瓜的數(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個(gè)，可獲收入1000元，乙方式每公頃需投資150元，勞動(dòng)15個(gè)工日，可獲收入1200元，該戶共有可用資金4200元、240個(gè)勞動(dòng)工日。問如何安排甲乙兩種方式的生產(chǎn)，可使總收入最大?解：設(shè)甲方式種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ī)劃中所有約束條件及非負(fù)約束的決策變量的一組取值，其僅與約束條件有關(guān)而與目標(biāo)函數(shù)值的大小無關(guān)。 （二）可行域 可行域是由所有可行解構(gòu)成的集合。根據(jù)線性規(guī)劃的基本理論，任一個(gè)線性規(guī)劃問題的可行域，都是一個(gè)有限或無限的凸多邊形，凸多邊形的每個(gè)角，稱為可行域的極點(diǎn)。 （三）最優(yōu)解 線性規(guī)劃的最優(yōu)解是指，使目標(biāo)函數(shù)值達(dá)到最優(yōu)(最大或最小)的可行解。一個(gè)線性規(guī)劃問題可以是有解的，也

12、可能是無解的，最優(yōu)解的個(gè)數(shù)可能是惟一的，也可能是有無窮多個(gè)，即決策變量有許多組不同的取值，都使目標(biāo)函數(shù)達(dá)到同一個(gè)最優(yōu)值。 二、線性規(guī)劃的求解圖解法 （四）最優(yōu)性定理 若一個(gè)線性規(guī)劃問題有最優(yōu)解，則最優(yōu)解一定可以在可行域的某個(gè)極點(diǎn)上找到一個(gè)最優(yōu)解。同時(shí)仍有可能有其他最優(yōu)解存在，但它們也只可能存在于可行域的其他極點(diǎn)或是邊界上。如果我們的目的是找出一個(gè)最優(yōu)解而不是全部最優(yōu)解，這一定理實(shí)際上是把尋找的范圍，從可行域中的無窮多個(gè)可行點(diǎn)，縮小到可行域的有限幾個(gè)極點(diǎn)上。 二、線性規(guī)劃的求解圖解法 （五）最大化問題的圖解法第一步，找出問題的可行域第二步，在可行域中尋求最優(yōu)解，方法有兩種 ： A.查點(diǎn)法 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ù)學(xué)理論上的推導(dǎo)和證明，我們在此僅介紹這種方法的具體操作步驟及每一步的經(jīng)濟(jì)上的含義。為更好地說明問題，我們?nèi)越Y(jié)合實(shí)例介紹這種方法 第三節(jié) 單純形法一、線性規(guī)劃的標(biāo)準(zhǔn)型二、線性規(guī)劃問題的解三、單純形法 四、單純型表第三節(jié) 單純形法一線性規(guī)劃的標(biāo)準(zhǔn)型LP目標(biāo)函數(shù)有的要求實(shí)現(xiàn)最大化，有的要求實(shí)現(xiàn)最小化，約束條件可以是“=”、“”，這種多樣性給討論問題帶來不便。為了便于討論，我們規(guī)定

15、線性規(guī)劃問題的標(biāo)準(zhǔn)形式為：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ī)劃的標(biāo)準(zhǔn)型njxbxaxcxcxcZjinjjijnn, 3 , 2 , 1,0max12211用向量表示 01jnjjjxbxPnxxxX21mjjjjaaaP21bmbbb21 其中 C=(c1,c2,cn) 向量Pj是其對(duì)應(yīng)變量xj 的系數(shù)向量。 第三節(jié) 單純形法一線性規(guī)劃的標(biāo)準(zhǔn)型用矩陣描述CXzMax

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

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

18、時(shí)）該工廠每生產(chǎn)一件產(chǎn)品x1可得利潤2元，每生產(chǎn)一件產(chǎn)品x2可得利潤3元，問如何安排生產(chǎn)計(jì)劃，才能得到利潤最多？ 三單純形法 設(shè)備產(chǎn)品ABCDx12140 x22204三單純形法w （一）求解過程 w （二）求解過程小結(jié)三單純形法Max Z=2x1+3 x2 2x1+2x212 x1+2x28 4x1 16 4x2 12 x10，x20 引入松弛變量x3 A設(shè)備閑置臺(tái)時(shí)數(shù)x4 B設(shè)備閑置臺(tái)時(shí)數(shù)x5 C設(shè)備閑置臺(tái)時(shí)數(shù)x6D設(shè)備閑置臺(tái)時(shí)數(shù)將線性規(guī)劃化為標(biāo)準(zhǔn)型.（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是線性獨(dú)立的，這些列向量構(gòu)成一個(gè)基 系數(shù)矩陣 100040010004001021000122654321PPPPPPA10000100001000016543PPPPB三單純形法 求解過程x3 = 122x12x2 x4 = 8x12x2 x5 = 164x1 x6 = 124x2 把上式帶入目標(biāo)函數(shù)得到 Z=0+2x1+3 x2 （8.4） 當(dāng)非基變量x1=x2=0,便得

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

21、可按以下方法來確定換出變量。三單純形法 求解過程 現(xiàn)分析（8.4），將x2定為換入變量后，必須從x3, x4, x5, x6中換出一個(gè)，并保證其余的都是非負(fù)，即x3, x4, x5, x60 當(dāng)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時(shí)，才能使（8.5）式成立。因當(dāng)x2=3時(shí)，基變量x6=0這就決定用x2去替換x6。三單純形法 求解過程為了求得以x3, x4, x5, x2為基變量的一個(gè)基本可行解和進(jìn)

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）目標(biāo)函數(shù)得到：w Z=9+2x1-3/4 x6 （8.8） w 當(dāng)非基變量x1=x6=0，得到Z=9，并得到另一個(gè)基本可行解TTxxxxxxX)0 ,16, 2 , 6 , 3 , 0(),

23、() 1 (6) 1 (5) 1 (4) 1 (3) 1 (2) 1 (1) 1 (三單純形法 求解過程 從目標(biāo)函數(shù)的表達(dá)式（8.8）中可看到，非基變量x1的系數(shù)是正的，說明目標(biāo)函數(shù)值還可以增大，X(1)不一定是最優(yōu)解。于是用上述方法，確定換入換出變量，繼續(xù)迭代，再得到另一個(gè)基本可行解X(2) 再經(jīng)過一次迭代，又得到一個(gè)基本可行解 這時(shí)得到的目標(biāo)函數(shù)的表達(dá)式是： Z = 14-1.5x4-0.125 x5 目標(biāo)函數(shù)值達(dá)到最大，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)性檢驗(yàn) 三單純形法 求解過程小結(jié)w 1.人造基、初始基本可行解 w 1.1若從線性規(guī)劃問題的 Pj中能直接觀察到存在m個(gè)線性獨(dú)立的單位向量，經(jīng)過重新安排次序便得到一個(gè)可行基jnjjxczMax101jnjjjxbxP10001000121MPPPB三單純形法 求解過程小結(jié)w 1.人造基、初始基本可行解 w 1.2“”標(biāo)準(zhǔn)化的方法，引入非負(fù)的松弛變量重新對(duì)xj及aij編號(hào)，經(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顯然得到一個(gè)單位陣 10001000121MPPPB三單純形法 求解過程小結(jié)我們就將B作為可行基。將（8.9）每個(gè)等式進(jìn)行移項(xiàng)得 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、一個(gè)初始基本可行解TmnmTmnmbbbxxxX)0, 0,()0, 0,(2121個(gè)個(gè)，三單純形法 求解過程小結(jié)2.最優(yōu)性檢驗(yàn)w 得到初始可行解后，要檢驗(yàn)一下是否是最優(yōu)解，如果是，則停止迭代，如果不是，則繼續(xù)迭代。但每次迭代后都要檢驗(yàn)一下是否是最優(yōu)解，為此需要建立一個(gè)判別準(zhǔn)則。w 一般情況下，經(jīng)過迭代后式變成w （i=1,2,3,m） w 將上式代入目標(biāo)函數(shù)，整理后得nmjjijiixabx1三單純形法 求解過程小結(jié)nmjjijmiijimiiixaccbcz111)(ijmiijimiiaczbcz110,j=m+1,n nmjjjjxzczz10)(), 1(nmjzcjjjnmjjjx

27、zz10三單純形法 求解過程小結(jié)w 2.1最優(yōu)解判別定理：w 若 為對(duì)應(yīng)于B的基本可行解，且對(duì)于一切j=m+1,n有 ，則X（0）為最優(yōu)解。w 無有限最優(yōu)解判別定理：w 若 為對(duì)應(yīng)于B的基本可行解，有一個(gè) 并且對(duì)于一切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為換入變量則對(duì)應(yīng)的kkjx )0max(ckcikikabaabRi0mincx三單純形法 求解過程小結(jié)三單純形表例1例1例1例1例2例2例2w 目標(biāo)函數(shù)

28、系數(shù)靈敏度分析w 右邊值靈敏度分析第四節(jié) 靈敏度分析目標(biāo)函數(shù)系數(shù)靈敏度分析w 最優(yōu)解不變的條件下，允許C的變化范圍，最優(yōu)解不變的前提是j 0w 假設(shè)玉米價(jià)值系數(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í)際際活活動(dòng)動(dòng)松松弛弛活活動(dòng)動(dòng)目目標(biāo)標(biāo)系系數(shù)數(shù)行行c cj j機(jī)機(jī)會(huì)會(huì)成成本本行行Z Zj