1、,第一章 線性規(guī)劃,線性規(guī)劃的標(biāo)準(zhǔn)形式,內(nèi) 容,線性規(guī)劃及其建模,圖解法,1,2,3,單純形法,4,大M法和兩階段法,5,幾種特殊情況的解,6,運(yùn)籌學(xué) 第一章 線性規(guī)劃,Slide 3,第一節(jié) 線性規(guī)劃的數(shù)學(xué)模型,一、線性規(guī)劃簡(jiǎn)介 1、線性規(guī)劃（Linear Programming，簡(jiǎn)稱LP）是運(yùn)籌學(xué)中研究比較早，理論上比較成熟，在方法上有效，應(yīng)用廣泛的一個(gè)分支。 1939年蘇聯(lián)的康托洛維奇（H.B.Kahtopob ）和美國(guó)的希奇柯克（F.L.Hitchcock）等人就在生產(chǎn)組織管理和制定交通運(yùn)輸方案方面首先研究和應(yīng)用線性規(guī)劃方法。 1947年丹捷格（G.R.Dantzig）等人提出了求解線

2、性規(guī)劃問(wèn)題的單純形方法，為線性規(guī)劃的理論與計(jì)算奠定了基礎(chǔ)。 特別是電子計(jì)算機(jī)的出現(xiàn)和日益完善，更使規(guī)劃論得到迅速的發(fā)展，可用電子計(jì)算機(jī)來(lái)處理成千上萬(wàn)個(gè)約束條件和變量的大規(guī)模線性規(guī)劃問(wèn)題。,運(yùn)籌學(xué) 第一章 線性規(guī)劃,Slide 4,2、研究對(duì)象 一類是在現(xiàn)有人力、物力、財(cái)力的條件下，研究如何合理地計(jì)劃和安排，使得某一目標(biāo)達(dá)到最大（產(chǎn)量最大、利潤(rùn)最大）。 另一類是任務(wù)確定后，如何計(jì)劃和安排，用最少的人力、物力和財(cái)力，去實(shí)現(xiàn)該任務(wù)，使得成本最小。 二、一般線性規(guī)劃問(wèn)題的建模過(guò)程（方法） 追求什么目標(biāo)？ 決策變量？ 目標(biāo)函數(shù)？ 約束條件？,運(yùn)籌學(xué) 第一章 線性規(guī)劃,Slide 5,課本P4例1.1:

3、生產(chǎn)安排問(wèn)題 設(shè)X1,X2,X3是甲、乙、丙三種產(chǎn)品的產(chǎn)量，Z是工廠的總利潤(rùn)。 maxz=3X1+2X2+5X3 s.t. X1+2X2+X3=0, X2=0 , X3=0,運(yùn)籌學(xué) 第一章 線性規(guī)劃,Slide 6,1、融會(huì)貫通地理解要解決的問(wèn)題，搞清在什么條件下，要追求什么目標(biāo)？ 2、這個(gè)要實(shí)現(xiàn)的目標(biāo)是由一組變量決定的，決策變量。定義決策變量，每一個(gè)問(wèn)題用一組決策變量（x1,x2,x3,xn）來(lái)表示某一方案，每組決策變量的值就代表一個(gè)具體方案；一般這些變量取值是非負(fù)的； 3、用決策變量的線性函數(shù)來(lái)表示寫(xiě)出所要追求的目標(biāo)，我們稱之為目標(biāo)函數(shù)。按問(wèn)題的不同，可能要求這目標(biāo)函數(shù)實(shí)現(xiàn)最大化或最小化。

4、 4、這些決策變量需要一定的限制和約束，這些約束條件可以用一組線性等式或不等式來(lái)表示。,三、線性規(guī)劃的特點(diǎn)及數(shù)學(xué)模型的一般形式,1、為什么叫線性規(guī)劃？ 用一組變量表示某個(gè)方案，一般這些變量取值是非負(fù)的。 有一個(gè)要達(dá)到的目標(biāo)，可以用決策變量的線性函數(shù)來(lái)表示。 存在一定約束條件，可以用線性等式或線性不等式來(lái)表示。 2、數(shù)學(xué)模型 目標(biāo)函數(shù)： 滿足約束條件：,Cj為價(jià)值系數(shù)，aij為技術(shù)系數(shù)，bi為資源（限額）系數(shù),運(yùn)籌學(xué) 第一章 線性規(guī)劃,Slide 8,四、線性規(guī)劃問(wèn)題舉例,（一）生產(chǎn)計(jì)劃 生產(chǎn)過(guò)程中合理安排機(jī)器設(shè)備和原材料，使得工廠獲利最大。 例1. 1 P70 習(xí)題17 : 設(shè)Xij為第i個(gè)車

5、間分配到第j種部件的工時(shí)數(shù)。 MAXZ= MIN (10X11+15X21+20X31+10X41, 15X12+10X22+5X32+15X42, X13+5X23+10X33+20X43) S.T. X11+X12+X13=0,運(yùn)籌學(xué) 第一章 線性規(guī)劃,Slide 9,（二）人力資源的分配 P70 習(xí)題14： 設(shè)從第i班(i1,2,3,4,5,6)才開(kāi)始工作的人數(shù)為Xi minZX1+X2+X3+X4+X5+X6 S.T. X1+X64 X2+X1 8 X3+X210 X4+X3 7 X5+X412 X6+X54 Xi 0 （三）合理下料（套裁下料、切割損失）,運(yùn)籌學(xué) 第一章 線性規(guī)劃,S

6、lide 10,設(shè)按這三種方案下料的原材料根數(shù)分別為x1、x2、x3 。 min x1+x2+x3 S.t. 2x1+3x2=90 x1+2x3=60 Xi=0 P6 例1. 3 切割損失最少,P70 習(xí)題11：,運(yùn)籌學(xué) 第一章 線性規(guī)劃,Slide 11,（四）配料,P5 例1. 2 P7 例1. 4 （五）倉(cāng)儲(chǔ) P70 習(xí)題16 設(shè)Xi為第i個(gè)月進(jìn)貨的件數(shù)，Yi為第i個(gè)月銷售的件數(shù)。 MAXZ=9Y1+8Y2+10Y38X16X29X3 S.T. X1=0 銷售數(shù)量的限制 200+X1Y1+X2Y2=0 200+X1Y1+X2Y2+X3Y3=0 Xi=0, Yi=0,運(yùn)籌學(xué) 第一章 線性規(guī)

7、劃,Slide 12,（六）投資,P8 例1. 5 P71 習(xí)題18 設(shè)Xij為第i年初（i=1,2,3）投資于j項(xiàng)目（j=1,2）的金額。(萬(wàn)元) MAX 1.7X31+3X22 S.T. X11+X12=10 X21+X22-1.7X11=0 X311.7X213X12=0 Xij=0,運(yùn)籌學(xué) 第一章 線性規(guī)劃,Slide 13,建模應(yīng)注意： 如何設(shè)好變量； 將解題的步驟寫(xiě)清； 約束條件按實(shí)際情況分類寫(xiě)清，勿遺漏； 目標(biāo)函數(shù)和約束條件寫(xiě)好后，應(yīng)合并同類項(xiàng)整理好，且約束條件的右邊為不含有變量的數(shù)字；,運(yùn)籌學(xué) 第一章 線性規(guī)劃,Slide 14,第二節(jié) 線性規(guī)劃問(wèn)題的解和單純形法,一、線性規(guī)劃

8、的圖解法 對(duì)于只包含兩個(gè)決策變量的線性規(guī)劃問(wèn)題，可以使用圖解法來(lái)求解。 圖解法簡(jiǎn)單直觀，有助于了解線性規(guī)劃求解的基本原理。 1、有唯一最優(yōu)解 P12例1.7：,maxz=4X1+3X2 s.t. 2X1+3X2=0, X2=0 ,P71 習(xí)題112：,四邊形OABC區(qū)域（含邊界）是四個(gè)半平面的交集，稱之為可行域。 視為以X1、X2為變量，z為參數(shù)的一族直線。它們互相平行，斜率為1。 在這族等值線中Z取得最大且又要在可行域內(nèi)的直線L*。與可行域相切的點(diǎn)B即為最優(yōu)解。最優(yōu)解為X*(301/45，49/45)T，最優(yōu)值為Z*280/9,運(yùn)籌學(xué) 第一章 線性規(guī)劃,Slide 16,2、無(wú)窮多解,max

9、z=3X1+2X2 s.t. 3X1+2X2=0, X2=0,L*即邊BC，故BC上的任意一點(diǎn)都是最優(yōu)解，有無(wú)窮多個(gè)。,最優(yōu)值Z*302816,P71 習(xí)題111：,L*上(從B以上)的任意一點(diǎn)都是最優(yōu)解，有無(wú)窮多個(gè)。 最優(yōu)值Z*62.521.512,運(yùn)籌學(xué) 第一章 線性規(guī)劃,Slide 18,3、無(wú)最優(yōu)解(無(wú)界解),maxz=X1+X2 s.t. X1X2=0, X2=0,可行域無(wú)界，目標(biāo)函數(shù)值可以增大到無(wú)窮大，稱為無(wú)界解，即無(wú)最優(yōu)解。,運(yùn)籌學(xué) 第一章 線性規(guī)劃,Slide 19,4、無(wú)可行解可行域?yàn)榭占?maxz=2X1+4X2 s.t. X1X2=6 X12X2=0, X2=0,約束條件

10、所組成的可行域?yàn)榭占瑹o(wú)可行解。,運(yùn)籌學(xué) 第一章 線性規(guī)劃,Slide 20,1、目標(biāo)函數(shù)： 滿足約束條件： 簡(jiǎn)寫(xiě)成： S.T. Xi=0, i=1,2,n bj =0, j=1,2,m,(1.14),(1.15),二、線性規(guī)劃的標(biāo)準(zhǔn)形式,使用矩陣和向量的形式，可表示為： Max CTX S.T. AX=B X=0,B =0 2、非標(biāo)準(zhǔn)形式線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)化 1）目標(biāo)函數(shù)的轉(zhuǎn)化。 MinZ=CTX Max(-Z)=CTX 當(dāng)求出目標(biāo)函數(shù)最大值后，乘以1，可以得到原問(wèn)題的目標(biāo)函數(shù)最小值。 2）約束條件的轉(zhuǎn)化。,松弛變量Xn+i=0 剩余變量Xn+i=0,(1.16),3）變量的非負(fù)約束。 若X

11、k為無(wú)約束的變量，則令Xk Xk Xk Xk , Xk =0 4）約束條件右邊為負(fù)。 兩邊乘以1 P11 例1. 6 P71 習(xí)題110（1）,minz=2X13X25X3 s.t. X1X2X3=5 6X17X29X3=15 19X17X25X3=0, X2=0,令X3=X3X3 -X1X2X3 X3 X4=5 6X17X29X39X3=15 19X17X25X35X3+X5=13 19X17X25X3 5X3X6=13 maxz=2X13X25X3 5X3 0X4+0X5+0X6 X1,X2,X3,X3,X4,X5,X6=0 三、線性規(guī)劃的解的概念（參考P12例1.7） 1、可行解和最優(yōu)解

12、：滿足約束條件的解（X1，X2，Xn）T稱為線性規(guī)劃的可行解。而使得目標(biāo)函數(shù)達(dá)到最優(yōu)值的可行解稱為最優(yōu)解。 2、基：（注意課本P15的定義對(duì)“基”的定義有誤） 設(shè)A是約束方程組mn維的系數(shù)矩陣，其秩為m，B是矩陣A中mm階非奇異子矩陣（B的行列式B0），則稱B是線性規(guī)劃問(wèn)題的一個(gè)基。,運(yùn)籌學(xué) 第一章 線性規(guī)劃,Slide 24,基向量、基變量： 設(shè)B （a1，a2，am） 稱aj（j1,2, ，m）為基向量。 它們是一個(gè)線性無(wú)關(guān)的向量組，與基向量對(duì)應(yīng)的變量Xj（j1,2, ，m）稱為基變量。其他變量就稱為非基變量。 3、基本解、基可行解、可行基： 設(shè)約束方程組（1.15）的系數(shù)矩陣A秩為m，由

13、mn，故有無(wú)窮多個(gè)解，假設(shè)前m個(gè)變量的系數(shù)列向量是線性無(wú)關(guān)的，那么，約束方程組（1.15）可寫(xiě)成,(1.17),運(yùn)籌學(xué) 第一章 線性規(guī)劃,Slide 25,X1 X2 Xm Xm1 Xn (1.18) 用向量的形式表示為： (1.19) 方程組的基是B，設(shè)XB是對(duì)應(yīng)于這個(gè)基的基變量，XB=（X1，X2，Xm）T,若令(1.19)式的非基變量Xm1Xm2Xn0，可以求出一個(gè)解：X=（X1，X2，Xm，0，0）T稱X為基本解。若滿足非負(fù)約束條件的基解。稱為基可行解。對(duì)應(yīng)于基可行解的基，稱為可行基。 【補(bǔ)充】：線性規(guī)劃的幾何意義和性質(zhì)： 1、線性規(guī)劃問(wèn)題若存在可行域，則其可行域是凸集(凸集：集合內(nèi)部

14、任意兩點(diǎn)連線上的點(diǎn)都屬于這個(gè)集合) 。 2、可行域有有限個(gè)頂點(diǎn)。設(shè)線性規(guī)劃問(wèn)題有n個(gè)變量，m個(gè)約束，則頂點(diǎn)的個(gè)數(shù)不多于Cnm個(gè)。 3、線性規(guī)劃問(wèn)題的基可行解對(duì)應(yīng)于可行域的頂點(diǎn)。線性規(guī)劃問(wèn)題的可行解為基可行解的充要條件是它的正分量所對(duì)應(yīng)的系數(shù)列向量是線性獨(dú)立的。 4、若線性規(guī)劃問(wèn)題存在最優(yōu)解，它一定在可行域的某個(gè)頂點(diǎn)得到。若在兩個(gè)頂點(diǎn)同時(shí)得到，則有無(wú)窮多最優(yōu)解。,運(yùn)籌學(xué) 第一章 線性規(guī)劃,Slide 27,線性規(guī)劃標(biāo)準(zhǔn)型問(wèn)題解的關(guān)系（P15 圖1.3）,約束方程的 解空間,可行解,非可行解,退化解,基 可行解,最優(yōu)基可行解,基解,運(yùn)籌學(xué) 第一章 線性規(guī)劃,Slide 28,四、單純形法原理,1、

15、單純形法的主要思想 線性規(guī)劃的求解軟件大多數(shù)都基于單純形法與理論。 如果線性規(guī)劃問(wèn)題有最優(yōu)解，則必可在某一基可行解（頂點(diǎn)）處達(dá)到。因而，求解只須在基可行解中尋找最優(yōu)解。 從可行域中某一個(gè)頂點(diǎn)開(kāi)始（先用最簡(jiǎn)單的辦法找一個(gè)基可行解） ，判別它是否最優(yōu)，若不是，就找一個(gè)更好的基可行解，再進(jìn)行檢驗(yàn)，如此迭代進(jìn)行，直至找到最優(yōu)解（可能不止一個(gè)），或者判定它無(wú)界或無(wú)解。 注：必須先化成標(biāo)準(zhǔn)形式。 主要有三個(gè)問(wèn)題：一是尋找初始解，二是判別最優(yōu)解，三是迭代。,2、舉例：,1）例1.7的標(biāo)準(zhǔn)形式為： MAXZ=4X1+3X2+0S1+0S2+0S3+0S4 (1.1) S.T. 2X1+3X2+ S1 =6 -

16、3X1+2X2 + S2 =3 2X2 +S3 =5 2X1+ X2 + S4=4 X1, X2,S1,S2,S3,S4=0, (1.2) 2）約束方程(1.2)的系數(shù)矩陣 A（P1,P2,P3,P4,P5,P6）=,P16例1.7： maxz=4X1+3X2 s.t. 2X1+3X2=0, X2=0,運(yùn)籌學(xué) 第一章 線性規(guī)劃,Slide 30,可以看到系數(shù)列向量 P3 ，P4 ，P5 ，P6 是線性獨(dú)立的，構(gòu)成一個(gè)基B(P3,P4,P5,P6)= 對(duì)應(yīng)B的變量S1,S2,S3,S4為基變量，從(1.1)(1.2)中可以得到 S1 =6 2X1 3X2 S2 =3 + 3X1 2X2 S3 =

17、5 2X2 S4=4 2X1 X2 (1. 3),非奇異子矩陣，作為一個(gè)基,運(yùn)籌學(xué) 第一章 線性規(guī)劃,Slide 31,將(1. 3)帶入(1. 1)得到 maxZ=4X1+3X20 (1. 4) 令非基變量X1和X2為0，得到Z0。這時(shí)可得到一個(gè)基可行解X(0)。 X (0)=(0,0,6,3,5,4) 從(1.1)可以看到非基變量的系數(shù)都是正數(shù)，因此將非基變量變換基變量，目標(biāo)函數(shù)的值就可能增大。（只要在目標(biāo)函數(shù)1.4的表達(dá)式中還存在正系數(shù)的非基變量，這表示目標(biāo)函數(shù)值還有增加的可能。） 判斷是否最優(yōu) 一般選擇系數(shù)最大的那個(gè)非基變量X1作為調(diào)入變量（入基變量），將它換入到基變量中去。同時(shí)還要確

18、定基變量中有一個(gè)要換出來(lái)成為非基變量。如何迭代,運(yùn)籌學(xué) 第一章 線性規(guī)劃,Slide 32,現(xiàn)分析(1.3)，當(dāng)將X1定為入基變量后，必須從S1、S2、S3、S4中換出一個(gè)，并保證其余都是非負(fù)的。 當(dāng)X20，由(1. 3)可得到 S1 =6 2X1 =0 X1=0 S3 =5 =0 S4=4 2X1 =0 X1=2 (1. 5) 從(1. 5)中可以看出，只有選擇 X1min（3， , 2）=2 時(shí)，才能使(1. 5)成立。所以出基變量為S4。,運(yùn)籌學(xué) 第一章 線性規(guī)劃,Slide 33,3）求出以X1、S1、S2、S3為基變量的一個(gè)基可行解。 X1和S4的位置交換，得 S1 =6 2X1 3

19、X2 (1) S2 =3 + 3X1 2X2 (2) S3 =5 2X2 (3) X1=2 1/2X2 1/2 S4 (4) (1. 6) 這樣，將(4)代入(1)(2)(3)后可得，,第一次迭代,運(yùn)籌學(xué) 第一章 線性規(guī)劃,Slide 34,S1 =2 2 X2 +S4 (1) S2 =9 7/2X2 3/2S4 (2) S3 =5 2X2 (3) X1=2 1/2X2 1/2 S4 (4) (1. 7) 代入目標(biāo)函數(shù)，可得 Z8X22S4 (1. 8) 令非基變量X2S40，得到Z8。并得到另一個(gè)基可行解X(1) 。X(1)=(2,0,2,9,5,0)T 從(1.8)中可以看到，非基變量X2

20、的系數(shù)是正的，說(shuō)明目標(biāo)函數(shù)值還可以增大。 將X2作為調(diào)入變量，當(dāng)S40 X2min（1, 18/7,5/2, 4）=1時(shí)，出基變量為S1。,X2和S1的位置交換，得 X2 =1 1/2S1 + 1/2S4 (1) X1 = 3/2+1/4S1 3/4S4 (2) S2 =11/2 +7/4S113/4S4 (3) S3 = 3 + S1 S4 (4) (1. 9) 代入目標(biāo)函數(shù)，可得 Z91/2S12/3S4 可以得到另一個(gè)基可行解X(2)=(3/2,1,0,11/2,3,0)T 。 可以看到非基變量S1、S4的系數(shù)都是負(fù)數(shù)，所以X(2) 是最優(yōu)解。即經(jīng)過(guò)二次迭代，當(dāng)X13/2，X21時(shí)，目標(biāo)

21、函數(shù)達(dá)到最優(yōu)，最優(yōu)值為9。 前兩個(gè)基可行解X (0)=(0,0,6,3,5,4)T和X(1)=(2,0,2,9,5,0)T分別對(duì)應(yīng)于圖1.2中的點(diǎn)A和點(diǎn)B。即從初始基可行解X (0) 開(kāi)始迭代，經(jīng)過(guò)X(1)，最后到達(dá)X(2)C點(diǎn)。,第二次迭代,運(yùn)籌學(xué) 第一章 線性規(guī)劃,Slide 36,3、單純形法求解的基本過(guò)程,1）轉(zhuǎn)化為線性規(guī)劃的標(biāo)準(zhǔn)形式 2）找出基本可行解 如果在約束方程組系數(shù)矩陣中找到一個(gè)基，令非基變量0，再求解這個(gè)m元線性方程就可得到唯一的解，稱為線性規(guī)劃的一個(gè)基本解。若能滿足變量非負(fù)的條件，則稱為一個(gè)基本可行解，并把這樣的基稱為可行基。 3）判斷已求得的基本可行解是否最優(yōu) 用非基變

22、量換出目標(biāo)函數(shù)的基變量。 檢驗(yàn)數(shù)j：此時(shí)目標(biāo)函數(shù)中所有變量的系數(shù)即為各變量的檢驗(yàn)數(shù)。 如果所有檢驗(yàn)數(shù)j= 0，則這個(gè)基可行解最優(yōu)。,4）基變換 入基變量和出基變量的確定，進(jìn)一步再求解得到新的基本可行解。 入基變量：選檢驗(yàn)數(shù)最大的非基變量為入基變量。 出基變量：把已確定的入基變量在各約束方程中(變量都移到方程的左邊)的正的系數(shù)除其所在約束方程中的常數(shù)項(xiàng)的值，把其中最小比值所在的約束方程中的原基變量確定為出基變量。 P72習(xí)題118 標(biāo)準(zhǔn)形式為： MAXZ=4X1+4X2+0S1+0S2 (118.1) S.T. 2X1+7X2+ S1 =21 7X1+2X2 + S2 =49 X1, X2,S1

23、,S2=0,以S1,S2 為基變量， S1 =212X17X2 S2=497X12X2 帶入1-18.1， 得出MAXZ=4X1+4X2+0 令非基變量X1和X2為0，得到Z0。這時(shí)可得到一個(gè)基可行解X(0)。 X (0)=(0,0,21,49) 非基變量的系數(shù)都是正數(shù)，且一樣，任意選擇X1為入基變量。令非基變量X2為0。 S1 =212X1 =0 S2=497X1 =0 X1min（21/2，7）=7 所以出基變量為S2。,X1和S2的位置交換，得 S1 =21 2X1 7X2 (1) X1=7 2/7X2 1/7 S2 (2) 這樣，將(2)代入(1)后可得， S1 =7 45/7X2 2

24、/7S2 (1) X1=7 2/7X2 1/7 S2 (2) 代入目標(biāo)函數(shù)，可得 MAXZ=2820/7X24/7S2 令非基變量X2S20，得到Z28。并得到另一個(gè)基可行解X(1) 。X(1)=(7,0,7,0)T 非基變量X2的系數(shù)是正的，說(shuō)明目標(biāo)函數(shù)值還可以增大。 將X2作為調(diào)入變量，當(dāng)S20,第一次迭代,X2min（49/2,49/45）=49/45時(shí)，出基變量為S1。 S1 =7 45/7X2 2/7S2 (1) X1=7 2/7X2 1/7 S2 (2) （1）式中X2和S1的位置交換，得 X2=49/45+2/45S27/45S1 帶入（2）可得 X1=301/457/45S2+

25、2/45S1 代入目標(biāo)函數(shù)，可得 MAXZ=280/94/9S14/9S2 令非基變量S1S20，得到Z280/9。并得到另一個(gè)基可行解X(2) 。X(2)=(301/45, 49/45,0,0)T 可以看到非基變量S1、S2的系數(shù)都是負(fù)數(shù)，所以X(2) 是最優(yōu)解。即經(jīng)過(guò)二次迭代，當(dāng)X1301/45，X249/45時(shí)，目標(biāo)函數(shù)達(dá)到最優(yōu)，最優(yōu)值為280/9 。,第二次迭代,運(yùn)籌學(xué) 第一章 線性規(guī)劃,Slide 41,五、表格單純形法,表格單純形法，是對(duì)上節(jié)討論的方法步驟進(jìn)行具體化、規(guī)范化、表格化的結(jié)果。其功能與增廣矩陣相似。 目標(biāo)函數(shù)和1.14式組成n+1個(gè)變量，m+1個(gè)方程的方程組。 X1 +

26、a1m+1Xm+1+a1nXn=b1 X2 +a2m+1Xm+2+a2nXn=b2 Xm +amm+1Xm+1+amnXn=bm Z+C1X1+C2X2+CmXm+Cm+1Xm+1 + +CnXn=0,1、單純形表,為了便于迭代運(yùn)算，可將上述方程組寫(xiě)成增廣矩陣。,若將Z看作不參與基變換的基變量，它與X1,X2, Xm的系數(shù)構(gòu)成一個(gè)基，這時(shí)可采用行初等變換將C1,C2, Cm變換為零，使其對(duì)應(yīng)的系數(shù)矩陣為單位矩陣。得到,XB列中填入基變量，CB列中填入基變量的價(jià)值系數(shù)； b列中填入約束方程右端的常數(shù)； Cj行中填入各變量的價(jià)值系數(shù)； i列中的數(shù)字是在確定調(diào)入變量后，按規(guī)則計(jì)算后填入； 最后一行是

27、檢驗(yàn)數(shù)行，對(duì)應(yīng)各非基變量的檢驗(yàn)數(shù)。,運(yùn)籌學(xué) 第一章 線性規(guī)劃,Slide 44,2、P16 例1.7,X (0)=(0,0,6,3,5,4)T, Z=0,運(yùn)籌學(xué) 第一章 線性規(guī)劃,Slide 45,例1.7,X (1)=(2,0,2,9,5,0)T, Z=8,例1.7,最優(yōu)解 :X*=(3/2,1,0,11/2,3,0)T，目標(biāo)函數(shù)最優(yōu)值Z*=9,注意：課本表格形式不同。見(jiàn)P18 表1.11表1.13,將線性規(guī)劃問(wèn)題化成標(biāo)準(zhǔn)型。 找出或構(gòu)造一個(gè)m階單位矩陣作為初始可行基，建立初始單純形表。 計(jì)算各非基變量Xj的檢驗(yàn)數(shù)j=Cj ，若所有j0，則問(wèn)題已得到最優(yōu)解，停止計(jì)算，否則轉(zhuǎn)入下步。 在大于0

28、的檢驗(yàn)數(shù)中，若某個(gè)k所對(duì)應(yīng)的系數(shù)列向量Pk0，則此問(wèn)題是無(wú)界解，停止計(jì)算，否則轉(zhuǎn)入下步。 根據(jù)maxjj0=k原則，確定Xk為調(diào)入變量(進(jìn)基變量)，再按規(guī)則計(jì)算：=minbi /aik | aik 0=bl / alk 確定Xl為換出變量。建立新的單純形表，此時(shí)基變量中Xk取代了Xl的位置。 以aik為主元素進(jìn)行迭代，把Xk所對(duì)應(yīng)的列向量變?yōu)閱挝涣邢蛄浚碼ik變?yōu)?，同列中其它元素為0，轉(zhuǎn)第 步。,3、計(jì)算步驟,P73 習(xí)題119(2) 化為標(biāo)準(zhǔn)形： MAXZ=-X1+3X2+2X3+0S1+0S2+0S3 S.T. 3X1X2+2X3+S1 =7 -2X1+4X2 +S2 =12 -4X1

29、+3X2+8X3 +S3 =10 X1,X2,X3,S1,S2,S3=0,運(yùn)籌學(xué) 第一章 線性規(guī)劃,Slide 50,最優(yōu)解 :X*=(78/25, 114/25, 11/10)T，Z*= 319/25 因?yàn)槟繕?biāo)函數(shù)是求最小值，所以Z*=- 319/25。,運(yùn)籌學(xué) 第一章 線性規(guī)劃,Slide 51,六、單純形法的進(jìn)一步討論大M法(人工變量法),Maxz= -4X1-X20S20S3-MR1-MR2 (2.3) S.T. 3X1+X2 +R1 =3 4X1+3X2S2+R2 =6 X1 +2X2 +S3 =3 X1,X2,S2,S3,R1,R2=0 (2.4),P21例1.9： minz=4X

30、1+X2 s.t. 3X1+ X2 =3 4X1+3X2=6 X1+2X2=0,1）例1.9的標(biāo)準(zhǔn)形式為： Maxz= -4X1-X2 (2.1) S.T. 3X1+X2 =3 4X1+3X2S2=6 X1 +2X2 +S3=3 X1,X2,S2,S3=0 (2.2),使用人工變量可以得到初始基可行解。 在約束條件中加入人工變量后，要求人工變量不影響目標(biāo)函數(shù)取值，為此假定人工變量在目標(biāo)函數(shù)中的系數(shù)為M（M為任意大的正數(shù)）。這樣，目標(biāo)函數(shù)要實(shí)現(xiàn)最大/小化時(shí)，必須把人工變量從基變量中換出，否則目標(biāo)函數(shù)不可能實(shí)現(xiàn)最大/小化。(注意：要引入幾個(gè)人工變量？),當(dāng)令非基變量X1、X2、S2為0，這時(shí)可得到

31、一個(gè)基可行解X(0)。 X (0)=(0,0,0,3,3,6)T，Z9M。,因?yàn)槟繕?biāo)函數(shù)要用非基變量來(lái)表示，所以要把各個(gè)基變量在目標(biāo)函數(shù)中的系數(shù)都變?yōu)?！,當(dāng)令非基變量X2、R1、S2為0，這時(shí)可得到一個(gè)基可行解X(1)。 X (1)=(1,0,0,2,0,2)T，Z42M。,當(dāng)令非基變量R1、R2、S2為0，這時(shí)可得到一個(gè)基可行解X(2)。 X (2)=(3/5,6/5,0,0,0,0)T，Z18/5。,當(dāng)令非基變量R1、R2、S3為0，這時(shí)可得到一個(gè)基可行解X(3)。 X (3)=(3/5,6/5,0,0,0,0)T，Z-18/5，為求最大值的最優(yōu)解。求最小值的最優(yōu)值是18/5。,P73

32、習(xí)題122（1） 化為標(biāo)準(zhǔn)形式，并引入人工變量 Maxz=2X1+3X25X3+0S1MR1MR2 S.T. X1+X2+X3+R1=7 2X15X2+X3S1+R2=10 X1,X2,X3,S1,R1,R2=0,運(yùn)籌學(xué) 第一章 線性規(guī)劃,Slide 58,當(dāng)令非基變量X1、X2、X3、S1為0，這時(shí)可得到一個(gè)基可行解X(0)。 X (0)=(0,0,0,0,7,10)T，Z17M。,把各個(gè)基變量在目標(biāo)函數(shù)中的系數(shù)都變?yōu)?！,運(yùn)籌學(xué) 第一章 線性規(guī)劃,Slide 59,當(dāng)令非基變量X2、X3、S1、R2為0，這時(shí)可得到一個(gè)基可行解X(1)。 X (1)=(5,0,0,0,2,0)T，Z102M

33、。,運(yùn)籌學(xué) 第一章 線性規(guī)劃,Slide 60,當(dāng)令非基變量X3、S1、R1、R2為0，這時(shí)可得到一個(gè)基可行解X(2)。 X (2)=(45/7,4/7,0,0,0,0)T，Z102/7，為最優(yōu)解。,兩階段法： 第一階段：用人工變量的和來(lái)代替原來(lái)的目標(biāo)函數(shù)，作出一個(gè)新的線性規(guī)劃問(wèn)題。如果原來(lái)的問(wèn)題有可行解，則新問(wèn)題的目標(biāo)函數(shù)的最小值一定等于零。 第二階段：把第一階段所求得的最優(yōu)基本解作為原問(wèn)題的一個(gè)初始解，再應(yīng)用一般線性規(guī)劃方法求出最優(yōu)解。 P23 例1.9：新目標(biāo)函數(shù)：minr=R1+R2 maxr=-R1-R2,第一階段：,運(yùn)籌學(xué) 第一章 線性規(guī)劃,Slide 62,當(dāng)令非基變量X1、X2、S2為0，這時(shí)可得到一個(gè)基可行解X(0)。 X (0)=(0,0,0,3,3,6)T，r-9。,運(yùn)籌學(xué) 第一章 線性規(guī)劃,Slide 63,當(dāng)令非基變量X2、S2、R1為0，這時(shí)可得到一個(gè)基可行解X(1)。 X (1)=(1,0,0,2,0,2)T，r-2。,運(yùn)籌學(xué)