MAchp6-線性規(guī)劃.ppt

1、,運(yùn)籌學(xué) Operations Research,Chapter 1 線性規(guī)劃 Linear Programming,1.1 LP的數(shù)學(xué)模型 Mathematical Model of LP 1.2 圖解法 Graphical Method 1.3 標(biāo)準(zhǔn)型 Standard form of LP 1.4 基本概念 Basic Concepts 1.5 單純形法 Simplex Method,1.1 數(shù)學(xué)模型 Mathematical Model,Chapter 1 線性規(guī)劃 Linear Programming,【例1.1】最優(yōu)生產(chǎn)計(jì)劃問(wèn)題。某企業(yè)在計(jì)劃期內(nèi)計(jì)劃生產(chǎn)甲、乙、丙三種產(chǎn)品。這些產(chǎn)品

2、分別需要在設(shè)備A、B上加工，需要消耗材料C、D，按工藝資料規(guī)定，單件產(chǎn)品在不同設(shè)備上加工及所需要的資源如表1.1所示。已知在計(jì)劃期內(nèi)設(shè)備的加工能力各為200臺(tái)時(shí)，可供材料分別為360、300公斤；每生產(chǎn)一件甲、乙、丙三種產(chǎn)品，企業(yè)可獲得利潤(rùn)分別為40、30、50元，假定市場(chǎng)需求無(wú)限制。企業(yè)決策者應(yīng)如何安排生產(chǎn)計(jì)劃，使企業(yè)在計(jì)劃期內(nèi)總的利潤(rùn)收入最大？,1.1.1 應(yīng)用模型舉例,1.1 線性規(guī)劃的數(shù)學(xué)模型 Mathematical Model of LP,Chapter 1 線性規(guī)劃 Linear Programming,表1.1 產(chǎn)品資源消耗,1.1 線性規(guī)劃的數(shù)學(xué)模型 Mathematical

3、 Model of LP,Chapter 1 線性規(guī)劃 Linear Programming,【解】 設(shè)x1、x2、x3 分別為甲、乙、丙三種產(chǎn)品的產(chǎn)量, 則 數(shù)學(xué)模型為：,最優(yōu)解X=(50,30,10); Z=3400,1.1 線性規(guī)劃的數(shù)學(xué)模型 Mathematical Model of LP,Chapter 1 線性規(guī)劃 Linear Programming,【例1.2】某商場(chǎng)決定：營(yíng)業(yè)員每周連續(xù)工作5天后連續(xù)休息2天， 輪流休息。根據(jù)統(tǒng)計(jì)，商場(chǎng)每天需要的營(yíng)業(yè)員如表1.2所示。,表1.2 營(yíng)業(yè)員需要量統(tǒng)計(jì)表,問(wèn)：商場(chǎng)人力資源部應(yīng)如何安排每天的上班人數(shù)，使商場(chǎng)總的營(yíng)業(yè)員最少？,【解】 設(shè)

4、( j=1，2，7)為休息2天后星期一到星期日開始上班的營(yíng)業(yè)員，則這個(gè)問(wèn)題的線性規(guī)劃模型為,1.1 線性規(guī)劃的數(shù)學(xué)模型 Mathematical Model of LP,Chapter 1 線性規(guī)劃 Linear Programming,1.1 線性規(guī)劃的數(shù)學(xué)模型 Mathematical Model of LP,Chapter 1 線性規(guī)劃 Linear Programming,1解決問(wèn)題的目標(biāo)函數(shù)是多個(gè)決策變量的線性函數(shù)，通常是 求最大值或最小值； 2解決問(wèn)題的約束條件是一組多個(gè)決策變量的線性不等式或等式。,線性規(guī)劃數(shù)學(xué)模型的特征：,線性規(guī)劃數(shù)學(xué)模型的三要素：,決策變量( Decision

5、 variables); 目標(biāo)函數(shù)(Objective function); 約束條件(Constraints);,建立一個(gè)問(wèn)題的線性規(guī)劃模型的一般步驟：,確定決策變量； (2)確定目標(biāo)函數(shù)； (3)確定約束條件； (4)確定變量是否有非負(fù)約束。,1.1 線性規(guī)劃的數(shù)學(xué)模型 Mathematical Model of LP,Chapter 1 線性規(guī)劃 Linear Programming,【例1.3】合理用料問(wèn)題。某汽車需要用甲、乙、丙三種規(guī)格的軸各一根，這些軸的規(guī)格分別是1.5，1，0.7(m)，這些軸需要用同一種圓鋼來(lái)做，圓鋼長(zhǎng)度為4 m。現(xiàn)在要制造1000輛汽車，最少要用多少圓鋼來(lái)生產(chǎn)

6、這些軸？,【解】這是一個(gè)條材下料問(wèn)題 ，設(shè)切口寬度為零。 設(shè)一根圓鋼切割成甲、乙、丙三種軸的根數(shù)分別為y1，y2，y3,則切割方式可用不等式1.5y1+y2+0.7y34表示，求這個(gè)不等式關(guān)于y1，y2，y3的非負(fù)整數(shù)解。象這樣的非負(fù)整數(shù)解共有10組，也就是有10種下料方式，如表1.3所示。,1.1 線性規(guī)劃的數(shù)學(xué)模型 Mathematical Model of LP,Chapter 1 線性規(guī)劃 Linear Programming,表1. 3 下料方案,1.5y1+y2+0.7y3 4,設(shè)xj ( j = 1,2,10)為第 j 種下料方案所用圓鋼的根數(shù)，則用料最少數(shù)學(xué)模型為:,1.1 線

7、性規(guī)劃的數(shù)學(xué)模型 Mathematical Model of LP,Chapter 1 線性規(guī)劃 Linear Programming,1.1 線性規(guī)劃的數(shù)學(xué)模型 Mathematical Model of LP,Chapter 1 線性規(guī)劃 Linear Programming,注 意,求下料方案時(shí)，余料不能超過(guò)最短毛坯的長(zhǎng)度；最好將毛坯長(zhǎng)度按降的次序排列，即先切割長(zhǎng)度最長(zhǎng)的毛坯，再切割次長(zhǎng)的，最后切割最短的，不能遺漏了方案 。如果方案較多，用計(jì)算機(jī)編程排方案，去掉余料較長(zhǎng)的方案，進(jìn)行初選。,1.1 線性規(guī)劃的數(shù)學(xué)模型 Mathematical Model of LP,Chapter 1 線

8、性規(guī)劃 Linear Programming,1.1.2 線性規(guī)劃的一般模型 一般地，假設(shè)線性規(guī)劃數(shù)學(xué)模型中,有m個(gè)約束,有n個(gè)決策變量xj(j=1,2,n)，目標(biāo)函數(shù)的變量系數(shù)用cj表示, cj稱為價(jià)值系數(shù)。約束條件的變量系數(shù)用aij表示，aij稱為工藝系數(shù)。約束條件右端的常數(shù)用bi 表示，bi 稱為資源限量。則線性規(guī)劃數(shù)學(xué)模型的一般表達(dá)式可寫成,1.1 線性規(guī)劃的數(shù)學(xué)模型 Mathematical Model of LP,Chapter 1 線性規(guī)劃 Linear Programming,在實(shí)際中一般xj0, 但有時(shí) xj0或 xj 無(wú)符號(hào)限制。,為了書寫方便，上式也可寫成：,1.1 線性

9、規(guī)劃的數(shù)學(xué)模型 Mathematical Model of LP,1.2 圖解法 Graphical Method,Chapter 1 線性規(guī)劃 Linear Programming,圖解法的步驟：,1. 在直角坐標(biāo)系中畫出可行解集：分別畫出滿足每個(gè)約束包括變量非負(fù)要求的區(qū)域，其交集就是可行解集，或稱可行域；,2. 繪制目標(biāo)函數(shù)圖形：先過(guò)原點(diǎn)作一條矢量指向點(diǎn)(c1,c2 )，矢量的方向就是目標(biāo)函數(shù)值增加的方向，稱為梯度方向，再作一條與矢量垂直的直線，這條直線就是目標(biāo)函數(shù)圖形；,3. 求最優(yōu)解：依據(jù)目標(biāo)函數(shù)求最大或最小移動(dòng)目標(biāo)函數(shù)直線， 直線與可行域相交的點(diǎn)對(duì)應(yīng)的坐標(biāo)就是最優(yōu)解。,一般地，先將目

10、標(biāo)函數(shù)直線放在可行域中： 若要求最大值，則將目標(biāo)函數(shù)直線沿著矢量方向移動(dòng)； 若要求最小值，則將目標(biāo)函數(shù)直線沿著矢量的反方向移動(dòng)。,1.2 圖解法 The Graphical Method,Chapter 1 線性規(guī)劃 Linear Programming,x1,x2,O,10,20,30,40,10,20,30,40,(3,4),(15,10),最優(yōu)解X=(15,10),最優(yōu)值Z=85,例1.4,1.2 圖解法 The Graphical Method,Chapter 1 線性規(guī)劃 Linear Programming,2,4,6,x1,x2,2,4,6,最優(yōu)解X=(3,1) 最優(yōu)值Z=5,(

11、3,1),min Z=x1+2x2,例1. 5,(1,2),1.2 圖解法 The Graphical Method,Chapter 1 線性規(guī)劃 Linear Programming,2,4,6,x1,x2,2,4,6,X（2）（3,1）,X（1）（1,3）,(5,5),min Z=5x1+5x2,例1.6,有無(wú)窮多個(gè)最優(yōu)解 即具有多重解,通解為,01,當(dāng)=0.5時(shí) =(x1,x2)=0.5(1,3)+0.5(3,1)=(2,2),1.2 圖解法 The Graphical Method,Chapter 1 線性規(guī)劃 Linear Programming,2,4,6,x1,x2,2,4,6,

12、(1,2),無(wú)界解(無(wú)最優(yōu)解),max Z=x1+2x2,例1.7,1.2 圖解法 The Graphical Method,Chapter 1 線性規(guī)劃 Linear Programming,x1,x2,O,10,20,30,40,10,20,30,40,50,50,無(wú)可行解，從 而無(wú)最優(yōu)解。,max Z=10 x1+x2,例1.8,1.2 圖解法 The Graphical Method,Chapter 1 線性規(guī)劃 Linear Programming,由以上例題可知，線性規(guī)劃的解有4種形式：,1.有惟一最優(yōu)解(例1.4、例1.5),2.有多重解(例1.6),3.有無(wú)界解(例1.7),4

13、.無(wú)可行解(例1.8),1、2情形為有最優(yōu)解 3、4情形為無(wú)最優(yōu)解,1.2 圖解法 The Graphical Method,Chapter 1 線性規(guī)劃 Linear Programming,1.3 線性規(guī)劃的標(biāo)準(zhǔn)型 Standard form of LP,Chapter 1 線性規(guī)劃 Linear Programming,在用單純法求解線性規(guī)劃問(wèn)題時(shí)，為了討論問(wèn)題方便，需將線性規(guī)劃模型化為統(tǒng)一的標(biāo)準(zhǔn)形式。,1.3 線性規(guī)劃的標(biāo)準(zhǔn)型 Standard form of LP,線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)型為: 1目標(biāo)函數(shù)求最大值（或求最小值） 2約束條件都為等式方程 3變量xj非負(fù) 4常數(shù)bi非負(fù),Ch

14、apter 1 線性規(guī)劃 Linear Programming,max(或min)Z=c1x1+c2x2+cnxn,1.3 線性規(guī)劃的標(biāo)準(zhǔn)型 Standard form of LP,注：本教材默認(rèn)標(biāo)準(zhǔn)型中目標(biāo)函數(shù)是 max,Chapter 1 線性規(guī)劃 Linear Programming,或?qū)懗上铝行问剑?或用矩陣形式,1.3 線性規(guī)劃的標(biāo)準(zhǔn)型 Standard form of LP,Chapter 1 線性規(guī)劃 Linear Programming,通常X記為： , 稱為約束方程的系數(shù)矩陣，m是約束方程的個(gè)數(shù)，n是決策變量的個(gè)數(shù)，一般情況mn，且r()m。,其中:,1.3 線性規(guī)劃的標(biāo)準(zhǔn)型

15、 Standard form of LP,Chapter 1 線性規(guī)劃 Linear Programming,一般形式線性規(guī)劃模型的標(biāo)準(zhǔn)化準(zhǔn)則: （前提 bi 0 ）,5. xj0,令xj = xj , xj 0,Chapter 1 線性規(guī)劃 Linear Programming,【例1】將下列線性規(guī)劃化為標(biāo)準(zhǔn)型,【分析】()因?yàn)閤3無(wú)符號(hào)要求 ，即x3 可取正值也可取負(fù)值，標(biāo)準(zhǔn)型中要求變量非負(fù)，所以令,1.3 線性規(guī)劃的標(biāo)準(zhǔn)型 Standard form of LP,Chapter 1 線性規(guī)劃 Linear Programming,(3)第二個(gè)約束條件是“”號(hào)，在“”號(hào)左端減去剩余 變量(

16、surplus variable) x5 ，x50，也稱松馳變量；,1.3 線性規(guī)劃的標(biāo)準(zhǔn)型 Standard form of LP,(2) 第一個(gè)約束條件是“”號(hào)， 在“”號(hào)左端加入松馳變量 (slack variable) x4，x40, 化為等式；,(4)第三個(gè)約束條件是“”號(hào)且常數(shù)項(xiàng)為負(fù)數(shù)，因此在“”左邊加入松馳變量x6，x60，同時(shí)兩邊乘以1。,(5)目標(biāo)函數(shù)是最小值，為了化為求最大值，令Z=Z, 得到 max Z=Z，即當(dāng)Z達(dá)到最小值時(shí)Z達(dá)到最大值。,Chapter 1 線性規(guī)劃 Linear Programming,綜合起來(lái)得到下列標(biāo)準(zhǔn)型,1.3 線性規(guī)劃的標(biāo)準(zhǔn)型 Standar

17、d form of LP,Chapter 1 線性規(guī)劃 Linear Programming,當(dāng)某個(gè)約束是絕對(duì)值不等式時(shí)，將絕對(duì)值不等式化為兩個(gè)不等式，再化為等式，例如約束,將其化為兩個(gè)不等式,再加入松馳變量化為等式。,1.3 線性規(guī)劃的標(biāo)準(zhǔn)型 Standard form of LP,1.4 線性規(guī)劃的有關(guān)概念 Basic Concepts of LP,Chapter 1 線性規(guī)劃 Linear Programming,設(shè)線性規(guī)劃的標(biāo)準(zhǔn)型 max Z=CX (1.1) AX=b (1.2) X 0 (1.3) 式中A 是mn矩陣，mn并且r(A)=m，顯然A中至少有一個(gè)mm子矩陣B，使得r(B

18、)=m。,1.4 基本概念 Basic Concepts,基 (basis)：A中 mm子矩陣 B 并且有r(B)=m，則稱B是線性規(guī)劃的一個(gè)基(或基矩陣basis matrix )。,Chapter 1 線性規(guī)劃 Linear Programming,【例2】線性規(guī)劃,求所有基矩陣。,【解】約束方程的系數(shù)矩陣為25矩陣,1.4 基本概念 Basic Concepts,Chapter 1 線性規(guī)劃 Linear Programming,容易看出r(A)=2，2階子矩陣有C52=10個(gè)，其中第1列與第3列構(gòu)成的2階矩陣不是一個(gè)基，基矩陣只有9個(gè)，即,Chapter 1 線性規(guī)劃 Linear P

19、rogramming,當(dāng)確定某一矩陣為基矩陣時(shí)，則基矩陣對(duì)應(yīng)的列向量稱為基向量(basic vector)，其余列向量稱為非基向量;,基向量對(duì)應(yīng)的變量稱為基變量(basic variable)， 非基向量對(duì)應(yīng)的變量稱為非基變量 ；,在上例中B2的基向量是A中的第一列和第四列，其余列向量是非基向量，x1、x4是基變量，x2、x3、x5是非基變量?；兞俊⒎腔兞渴轻槍?duì)某一確定基而言的，不同的基對(duì)應(yīng)的基變量和非基變量也不同。,1.4 基本概念 Basic Concepts,Chapter 1 線性規(guī)劃 Linear Programming,可行解(feasible solution): 滿足式(1

20、.2)及(1.3)的解X=（x1, x2 , xn)T 稱為可行解；,基本可行解(basic feasible solution): 若基本解是可行解 則稱為是基本可行解（也稱基可行解）。,基本解(basic solution) : 對(duì)某一確定的基B，令非基變量 等于零，利用式(1.2)解出基變量，則這組解稱為基 的 基本解。,最優(yōu)解(optimal solution): 滿足式(1.1)的可行解稱為最優(yōu) 解，即使得目標(biāo)函數(shù)達(dá)到最大值的可行解就是最優(yōu)解；,非可行解(infeasible solution) 無(wú)界解 (unbounded solution),1.4 基本概念 Basic Conc

21、epts,Chapter 1 線性規(guī)劃 Linear Programming,顯然，只要基本解中的基變量的解滿足式(1.3)的非負(fù)要求，那么這個(gè)基本解就是基本可行解。,在上例中，對(duì)來(lái)說(shuō)，x1, x2是基變量，x3 , x4 ，x5是非基變量，令x3=x4=x5=0，則式(1.2)為,因|B1|，由克萊姆法則知，x1、x2有惟一解x12/5, x2=1, 從而基本解為,1.4 基本概念 Basic Concepts,Chapter 1 線性規(guī)劃 Linear Programming,對(duì)B2來(lái)說(shuō)，x1, x4,為基變量，令非變量x2, x3, x5為零，由式(1.2)得 ，x4=4，則基本解為,反

22、之，可行解不一定是基本可行解，如 滿足式(1.2)(1.3)，但不是任何基矩陣的基本解。,在 中x10, 不是可行解，因此也不是基本可行解。,Chapter 1 線性規(guī)劃 Linear Programming,可行基: 基可行解對(duì)應(yīng)的基稱為可行基； 最優(yōu)基: 基本最優(yōu)解對(duì)應(yīng)的基稱為最優(yōu)基； 如上述B3就是最優(yōu)基，最優(yōu)基肯定是可行基。,1.4 基本概念 Basic Concepts,基本最優(yōu)解: 最優(yōu)解是基本解稱為基本最優(yōu)解。例如 滿足式(1.1)(1.3)是最優(yōu)解, 又是B3的基本解, 因此它是基本最優(yōu)解。,注：當(dāng)最優(yōu)解惟一時(shí)，最優(yōu)解亦是基本最優(yōu)解， 當(dāng)最優(yōu)解不惟一時(shí)，則最優(yōu)解不一定是基本最優(yōu)

23、解。,Chapter 1 線性規(guī)劃 Linear Programming,基本最優(yōu)解、最優(yōu)解、基本可行解、基本解、可行解的關(guān)系:,基本最優(yōu)解,基本可行解,可行解,最 優(yōu) 解,基本解,1.4 基本概念 Basic Concepts,Chapter 1 線性規(guī)劃 Linear Programming,【定理1.1】 若線性規(guī)劃可行解集 K 非空, 則 K 是凸集。,【定理1.2】 線性規(guī)劃的可行解集合 K 的點(diǎn) X 是極點(diǎn)的充要條件為 X 是基本可行解。,【定理1.3】 若線性規(guī)劃有最優(yōu)解, 則最優(yōu)值一定可以在可行解集合的某個(gè)極點(diǎn)上達(dá)到, 最優(yōu)解就是極點(diǎn)的坐標(biāo)向量。,線性規(guī)劃的基本定理,1.4 基

24、本概念 Basic Concepts,Chapter 1 線性規(guī)劃 Linear Programming,。,定理1.2及1.3還給了我們一個(gè)啟示，尋求最優(yōu)解可不在無(wú)限個(gè)可行解中去找，而是去有限個(gè)基本可行解中去找。下一節(jié)將介紹一種有效地尋找最優(yōu)解的方法。,1.4 基本概念 Basic Concepts,Chapter 1 線性規(guī)劃 Linear Programming,1.5 單純形法 Simplex Method,Chapter 1 線性規(guī)劃 Linear Programming,單純形計(jì)算方法(Simplex Method)是先求出一個(gè)初始基可行解并判斷它是否最優(yōu)，若不是最優(yōu)，再換一個(gè)基可

25、行解并判斷，直到得出最優(yōu)解或判斷出問(wèn)題無(wú)最優(yōu)解。它是一種逐步逼近最優(yōu)解的迭代方法。,當(dāng)系數(shù)矩陣A中可以觀察得到一個(gè)可行基時(shí)(通常是一個(gè)單位矩陣或m個(gè)線性無(wú)關(guān)的單位向量組成的矩陣)，則可以通過(guò)解線性方程組求得基本可行解。,1.5 單純形法 Simplex Method,1.5.1 普通單純形法,Chapter 1 線性規(guī)劃 Linear Programming,【例3】 用單純形法求下列線性規(guī)劃的最優(yōu)解,【解】化為標(biāo)準(zhǔn)型:,1.5 單純形法 Simplex Method,Chapter 1 線性規(guī)劃 Linear Programming,系數(shù)矩陣A及可行基B1,r(B1)=2, B1是一個(gè)初始基

26、, x3、x4為基變量, x1、x2為非基變量, 令x1=0、x2=0, 由約束方程知x3=40、x4=30得到初始基本可行解,X(1)=(0, 0, 40, 30)T,1.5 單純形法 Simplex Method,上述基本可行解是不是最優(yōu)解？,Chapter 1 線性規(guī)劃 Linear Programming,我們可在目標(biāo)函數(shù)中把基變量用非基變量來(lái)表示，則可根據(jù)非基變量的系數(shù)來(lái)判斷目標(biāo)函數(shù)有沒(méi)有達(dá)到最優(yōu)值，把判別線性規(guī)劃問(wèn)題是否達(dá)到最優(yōu)解的數(shù)稱為檢驗(yàn)數(shù)，記作j ( j=1,2,n)。,本例中1=3,2=4,3=0,4=0。,最優(yōu)解判斷標(biāo)準(zhǔn): 當(dāng)所有檢驗(yàn)數(shù)j0(j=1，n)時(shí)，基本可行解為最

27、優(yōu)解。,注：當(dāng)目標(biāo)函數(shù)中有基變量xi 時(shí)，利用約束條件將目標(biāo)函數(shù)中的 xi 消去即可求出檢驗(yàn)數(shù)。,1.5 單純形法 Simplex Method,檢驗(yàn)數(shù): 目標(biāo)函數(shù)用非基變量表達(dá)時(shí)的變量系數(shù)。,Chapter 1 線性規(guī)劃 Linear Programming,典則形式(典式): (1)約束方程組中基變量的系數(shù)矩陣是的單位矩陣，移項(xiàng)后基變量可由非基變量表出； (2)目標(biāo)函數(shù)中不含有基變量，只含非基變量(因?yàn)榛兞靠捎煞腔兞勘沓?。,通常我們把典式中的相關(guān)數(shù)據(jù)列在一張表上，顯得比較直觀、簡(jiǎn)潔。若初始基可行解不是最優(yōu)解，我們也可直接在表上進(jìn)行作業(yè)，換到下一個(gè)基可行解，把這樣的表叫做單純形表。,1

28、.5 單純形法 Simplex Method,如何通過(guò)觀察第一個(gè)基本可行解并能判斷是否為最優(yōu)解，關(guān)鍵看模型是不是典則形式（簡(jiǎn)稱典式）：,Chapter 1 線性規(guī)劃 Linear Programming,進(jìn)基列,出基行,bi /ai2，ai20,i,表1. 5,基變量,1,10,0,0,1/3,0,1/3,10,5/3,1,-1/3,40,5/3,0,-4/3,30,1,0,3/5,-1/5,18,0,1,-1/5,2/5,4,0,0,-1,-1,將3化為1,乘以1/3后得到,1.5 單純形法 Simplex Method,30,18,Chapter 1 線性規(guī)劃 Linear Program

29、ming,單純形法的計(jì)算步驟：,1. 找一個(gè)初始可行基，寫出對(duì)應(yīng)的典式，列出初始單純形表,其中基變量的檢驗(yàn)數(shù)必為零；,2. 判斷： (a)若j( j，n)，則得到最優(yōu)解； (b)若存在某個(gè)k0且aik(i=1，2,m)，則線性 規(guī)劃具有無(wú)界解； (c)若存在k0且aik (i=1,m)不全非正，則進(jìn)行換基；,1.5 單純形法 Simplex Method,3. 換基： (a)選進(jìn)基變量：設(shè)k=max j | j 0, 選第k列所對(duì)應(yīng)的變量xk為進(jìn)基變量。,Chapter 1 線性規(guī)劃 Linear Programming,第個(gè)比值最小，選最小比值對(duì)應(yīng)行的基變量為出基變量，若有相同最小比值，則任選一個(gè)aLk為主元素。,(c)求新的基可行解：用初等行變換方法將aLk化為, 第 k 列其它元素化為零（包括檢驗(yàn)數(shù)行）得到新的可行基及基本可行解，再判斷是否得到最優(yōu)解。,(b)選出基變量 ：求最小比值,1.5 單純形法 Simplex Method,Chapter 1 線性規(guī)劃 Linear Programming,【例4】 用單純形法求解,【解】將數(shù)學(xué)模型化為標(biāo)準(zhǔn)型：,1.5 單純形法 Simplex Method,Chapter 1 線性規(guī)劃 Linear Programming,表1. 6,1/3,1,5,0,1,20,