關于線性規劃及單純型法第一頁，共二百九十頁，2022年，8月28日

線性規劃問題的提出線性規劃的基本概念線性規劃的數學模型線性規劃問題的標準形式繼續返回1.1線性規劃問題及其數學模型第二頁，共二百九十頁，2022年，8月28日問題的提出例:生產計劃問題第三頁，共二百九十頁，2022年，8月28日產品I產品2如何安排生產使利潤最大？第四頁，共二百九十頁，2022年，8月28日決策變量（Decisionvariables）目標函數（Objectivefunction）約束條件（Constraintconditions）可行域（Feasibleregion)最優解（Optimalsolution)基本概念問題中要確定的未知量，表明規劃中的用數量表示的方案、措施，可由決策者決定和控制。它是決策變量的函數指決策變量取值時受到的各種資源條件的限制，通常表達為含決策變量的等式或不等式。滿足約束條件的決策變量的取值范圍可行域中使目標函數達到最優的決策變量的值第五頁，共二百九十頁，2022年，8月28日是問題中要確定的未知量，表明規劃中的用數量表示的方案、措施，可由決策者決定和控制。第1步-確定決策變量設——I的產量——II的產量——利潤第六頁，共二百九十頁，2022年，8月28日第2步--定義目標函數MaxZ=x1+x2決策變量第七頁，共二百九十頁，2022年，8月28日

MaxZ=2x1+3x2系數第2步--定義目標函數第八頁，共二百九十頁，2022年，8月28日對我們有何限制?第九頁，共二百九十頁，2022年，8月28日第3步--表示約束條件

x1+2x2

84x1

164x2

12x1、x2

0第十頁，共二百九十頁，2022年，8月28日該計劃的數學模型

目標函數MaxZ=2x1+3x2約束條件x1+2x2

84x1

164x2

12x1、x2

0x1

x2第十一頁，共二百九十頁，2022年，8月28日線性規劃問題的共同特征一組決策變量X表示一個方案,一般X大于等于零。約束條件是線性等式或不等式。目標函數是線性的。求目標函數最大化或最小化第十二頁，共二百九十頁，2022年，8月28日

線性規劃模型的一般形式第十三頁，共二百九十頁，2022年，8月28日線性規劃問題的標準形式標準形式為:目標函數最大約束條件等式決策變量非負第十四頁，共二百九十頁，2022年，8月28日

簡寫為第十五頁，共二百九十頁，2022年，8月28日

用向量表示第十六頁，共二百九十頁，2022年，8月28日

用矩陣表示C—價值向量b—資源向量X—決策變量向量第十七頁，共二百九十頁，2022年，8月28日

minZ=CX等價于maxZ’=-CX“”約束：加入非負松馳變量一般線性規劃問題的標準形化例：

目標函數MaxZ=2x1+3x2約束條件x1+2x2

84x1

164x2

12x1、x2

0第十八頁，共二百九十頁，2022年，8月28日

minZ=CX等價于maxZ’=-CX“”約束：加入非負松馳變量一般線性規劃問題的標準形化例：第十九頁，共二百九十頁，2022年，8月28日

“”約束：減去非負剩余變量；

Max例：可正可負（即無約束）；第二十頁，共二百九十頁，2022年，8月28日

解：標準形為第二十一頁，共二百九十頁，2022年，8月28日線性規劃問題的數學模型例將下列線性規劃問題化為標準形式用替換，且解:（１）因為x3無符號要求，即x3取正值也可取負值，標準型中要求變量非負，所以第二十二頁，共二百九十頁，2022年，8月28日線性規劃問題的數學模型(2)第一個約束條件是“≤”號，在“≤”左端加入松馳變量x4，x4≥0,化為等式；(3)第二個約束條件是“≥”號，在“≥”左端減去剩余變量x5，x5≥0；(4)第3個約束方程右端常數項為-5，方程兩邊同乘以(-1),將右端常數項化為正數；(5)目標函數是最小值，為了化為求最大值，令z′=-z,得到maxz′=-z，即當z達到最小值時z′達到最大值，反之亦然;第二十三頁，共二百九十頁，2022年，8月28日線性規劃問題的數學模型標準形式如下：第二十四頁，共二百九十頁，2022年，8月28日圖解法線性規劃問題求解的幾種可能結果由圖解法得到的啟示1.2.1線性規劃的圖解法繼續返回第二十五頁，共二百九十頁，2022年，8月28日例1的數學模型

目標函數MaxZ=2x1+3x2約束條件x1+2x2

84x1

164x2

12x1、x2

0x1

x2第二十六頁，共二百九十頁，2022年，8月28日9—8—7—6—5—4—3—2—1—0| | | | | | | | |1 2 3 4 5 6 7 8 9x1x2x1+2x2

8(0,4)(8,0)

目標函數MaxZ=2x1+3x2約束條件x1+2x2

84x1

164x2

12x1、x2

04x1

164x2

16圖解法第二十七頁，共二百九十頁，2022年，8月28日9—8—7—6—5—4—3—2—1—0x2

目標函數MaxZ=2x1+3x2約束條件x1+2x2

84x1

164x2

12x1、x2

0| | | | | | | | |1 2 3 4 5 6 7 8 9x1x1+2x2

84x1

164x2

16可行域圖解法第二十八頁，共二百九十頁，2022年，8月28日9—8—7—6—5—4—3—2—1—0| | | | | | | | |1 2 3 4 5 6 7 8 9x1x2

目標函數MaxZ=2x1+3x2約束條件x1+2x2

84x1

164x2

12x1、x2

0x1+2x2

84x1

164x2

16可行域BCDEA圖解法第二十九頁，共二百九十頁，2022年，8月28日9—8—7—6—5—4—3—2—1—0x2

目標函數MaxZ=2x1+3x2約束條件x1+2x2

84x1

164x2

12x1、x2

0| | | | | | | | |1 2 3 4 5 6 7 8 9x1x1+2x2

84x1

164x2

16BCDEA2x1+3x2=6圖解法第三十頁，共二百九十頁，2022年，8月28日9—8—7—6—5—4—3—2—1—0x2

目標函數MaxZ=2x1+3x2約束條件x1+2x2

84x1

164x2

12x1、x2

0| | | | | | | | |1 2 3 4 5 6 7 8 9x1x1+2x2

84x1

164x2

16BCDEAx1+2x2=84x1=16最優解(4,2)圖解法第三十一頁，共二百九十頁，2022年，8月28日例1.目標函數：

Maxz=50x1+100x2約束條件：

s.t.x1+x2≤300(A)2x1+x2≤400(B)x2≤250(C)x1≥0(D)x2≥0(E)得到最優解：

x1=50，x2=250

最優目標值z=27500圖解法對于只有兩個決策變量的線性規劃問題，可以在平面直角坐標系上作圖表示線性規劃問題的有關概念，并求解。下面通過例1詳細講解其方法：第三十二頁，共二百九十頁，2022年，8月28日圖解法

(1)分別取決策變量X1,X2

為坐標向量建立直角坐標系。在直角坐標系里，圖上任意一點的坐標代表了決策變量的一組值，例1的每個約束條件都代表一個半平面。x2x1X2≥0X2=0x2x1X1≥0X1=0第三十三頁，共二百九十頁，2022年，8月28日圖解法（2）對每個不等式(約束條件)，先取其等式在坐標系中作直線，然后確定不等式所決定的半平面。100200300100200300x1+x2≤300x1+x2=3001001002002x1+x2≤4002x1+x2=400300200300400第三十四頁，共二百九十頁，2022年，8月28日圖解法（3）把五個圖合并成一個圖，取各約束條件的公共部分，如圖2-1所示。100100x2≤250x2=250200300200300x1x2x2=0x1=0x2=250x1+x2=3002x1+x2=400圖2-1第三十五頁，共二百九十頁，2022年，8月28日圖解法（4）目標函數z=50x1+100x2，當z取某一固定值時得到一條直線，直線上的每一點都具有相同的目標函數值，稱之為“等值線”。平行移動等值線，當移動到B點時，z在可行域內實現了最大化。A，B，C，D，E是可行域的頂點，對有限個約束條件則其可行域的頂點也是有限的。x1x2z=20000=50x1+100x2圖2-2z=27500=50x1+100x2z=0=50x1+100x2z=10000=50x1+100x2CBADE第三十六頁，共二百九十頁，2022年，8月28日圖解法求解步驟由全部約束條件作圖求出可行域；作目標函數等值線，確定使目標函數最優的移動方向；平移目標函數的等值線，找出最優點，算出最優值。第三十七頁，共二百九十頁，2022年，8月28日線性規劃問題求解的

幾種可能結果(a)唯一最優解

x26—5—4—3—2—1—0| | | | | | | | |1 2 3 4 5 6 7 8 9x1第三十八頁，共二百九十頁，2022年，8月28日(b)無窮多最優解6—5—4—3—2—1—0x2| | | | | | | | |1 2 3 4 5 6 7 8 9x1線性規劃問題求解的

幾種可能結果第三十九頁，共二百九十頁，2022年，8月28日(c)無界解

MaxZ=x1+x2

-2x1+x2

4

x1-x2

2

x1、x2

0

x2x1線性規劃問題求解的

幾種可能結果第四十頁，共二百九十頁，2022年，8月28日(d)無可行解

MaxZ=2x1+3x2x1+2x2

84x1

164x2

12

-2x1+x24x1、x2

0可行域為空集線性規劃問題求解的

幾種可能結果第四十一頁，共二百九十頁，2022年，8月28日圖解法的幾點結論:

（由圖解法得到的啟示）可行域是有界或無界的凸多邊形。若線性規劃問題存在最優解，它一定可以在可行域的頂點得到。若兩個頂點同時得到最優解，則其連線上的所有點都是最優解。解題思路：找出凸集的頂點，計算其目標函數值，比較即得。第四十二頁，共二百九十頁，2022年，8月28日練習：

用圖解法求解LP問題

MaxZ=34x1+40x24x1+6x2

482x1+2x2

182x1+x2

16x1、x2

0第四十三頁，共二百九十頁，2022年，8月28日圖解法—（練習）

18—16—14—12—10—8—6—4—2—0| | | | | | | | |2 4 6 8 10 12 14 16 18x1x24x1+6x2

482x1+2x2

182x1+x2

16第四十四頁，共二百九十頁，2022年，8月28日圖解法—（練習）

18—16—14—12—10—8—6—4—2—0| | | | | | | | |2 4 6 8 10 12 14 16 18x1x24x1+6x2

482x1+2x2

182x1+x2

16可行域ABCDE第四十五頁，共二百九十頁，2022年，8月28日圖解法—（練習）

18—16—14—12—10—8—6—4—2—0| | | | | | | | |2 4 6 8 10 12 14 16 18x1x24x1+6x2

482x1+2x2

182x1+x2

16ABCDE(8,0)(0,6.8)34x1+40x2=272第四十六頁，共二百九十頁，2022年，8月28日圖解法—（練習）

18—16—14—12—10—8—6—4—2—0| | | | | | | | |2 4 6 8 10 12 14 16 18x1x24x1+6x2

482x1+2x2

182x1+x2

16ABCDE(8,0)(0,6.8)第四十七頁，共二百九十頁，2022年，8月28日圖解法—（練習）

x218—16—14—12—10—8—6—4—2—0| | | | | | | | |2 4 6 8 10 12 14 16 18x14x1+6x2

482x1+2x2

182x1+x2

16ABCDE(8,0)(0,6.8)最優解(3,6)4x1+6x2=482x1+2x2=18第四十八頁，共二百九十頁，2022年，8月28日1.2.1線性規劃的圖解法結束返回第四十九頁，共二百九十頁，2022年，8月28日1.2.2線性規劃解的性質線性規劃解的概念線性規劃問題的幾何意義（單純形法原理）繼續返回第五十頁，共二百九十頁，2022年，8月28日線性規劃問題解的概念標準型可行解:滿足AX=b,X>=0的解X稱為線性規劃問題的可行解。最優解：使Z=CX達到最大值的可行解稱為最優解。第五十一頁，共二百九十頁，2022年，8月28日

基：若B是矩陣A中m×m階非奇異子矩陣（B≠0），則B是線性規劃問題的一個基。不妨設：,j=1，2，…,m——基向量。，j=1，2，…,m——基變量。,j=m+1,…,n——非基變量。線性規劃問題解的概念第五十二頁，共二百九十頁，2022年，8月28日例求線性規劃問題的所有基矩陣。解:約束方程的系數矩陣為2×5矩陣r(A)=2，2階子矩陣有10個，其中基矩陣只有9個，即第五十三頁，共二百九十頁，2022年，8月28日

求解線性規劃問題解的概念第五十四頁，共二百九十頁，2022年，8月28日基解：稱上面求出的X解為基解。基可行解：非負的基解X稱為基可行解可行基：對應基可行解的基稱為可行基線性規劃問題解的概念T基變量令可求出：第五十五頁，共二百九十頁，2022年，8月28日線性規劃解的關系圖非可行解可行解

基可行解

基解線性規劃問題解的概念

最優解？第五十六頁，共二百九十頁，2022年，8月28日

例：求基解、基可行解、最優解。線性規劃問題解的概念第五十七頁，共二百九十頁，2022年，8月28日10051045Y

20452017Y

35005410Y

40550-120N5100-50415N652.5001.517.5Y

7540-3022N82430019

Y

是否基可行解最優解線性規劃問題解的概念解：第五十八頁，共二百九十頁，2022年，8月28日

：求基解、基可行解、最優解。練習：線性規劃問題解的概念第五十九頁，共二百九十頁，2022年，8月28日線性規劃問題的幾何意義基本概念凸集：線性規劃問題的幾何意義第六十頁，共二百九十頁，2022年，8月28日

頂點:若K是凸集，X∈K；若X不能用不同的兩點的線性組合表示為：則X為頂點.凸集線性規劃問題的幾何意義第六十一頁，共二百九十頁，2022年，8月28日

凸組合：

Xn=2，k=3線性規劃問題的幾何意義第六十二頁，共二百九十頁，2022年，8月28日定理1:若線性規劃問題存在可行域,則其可行域:是凸集.基本定理證明:線性規劃問題的幾何意義第六十三頁，共二百九十頁，2022年，8月28日

只要驗證X在D中即可第六十四頁，共二百九十頁，2022年，8月28日

引理：可行解X為基可行解

X的正分量對應的列向量線性無關定理3：若可行域有界，線性規劃問題的目標函數一定可以在其可行域的頂點上達到最優。定理2：線性規劃問題的基可行解X對應于可行域D的頂點。證明：反證法。分兩步。第六十五頁，共二百九十頁，2022年，8月28日幾點結論：線性規劃問題的可行域是凸集。基可行解與可行域的頂點一一對應，可行域有有限多個頂點。最優解必在頂點上得到。第六十六頁，共二百九十頁，2022年，8月28日圖解法9—8—7—6—5—4—3—2—1—0x2| | | | | | | | |1 2 3 4 5 6 7 8 9x1x1+2x2

84x1

164x2

16可行域BCDEA可行域為凸集目標函數不同時等值線的斜率不同最優解在頂點產生

目標函數等值線的斜率最優解第六十七頁，共二百九十頁，2022年，8月28日圖解法9—8—7—6—5—4—3—2—1—0x2| | | | | | | | |1 2 3 4 5 6 7 8 9x1x1+2x2

84x1

164x2

16可行域BCDEA可行域為凸集目標函數不同時等值線的斜率不同最優解在頂點產生

目標函數等值線的斜率最優解第六十八頁，共二百九十頁，2022年，8月28日圖解法9—8—7—6—5—4—3—2—1—0x2| | | | | | | | |1 2 3 4 5 6 7 8 9x1x1+2x2

84x1

164x2

16可行域BCDEA可行域為凸集目標函數不同時等值線的斜率不同最優解在頂點產生

目標函數等值線的斜率最優解第六十九頁，共二百九十頁，2022年，8月28日求解LP的基本思路1、構造初始可行基；2、求出一個基可行解（頂點）3、最優性檢驗：判斷是否最優解；4、基變化，轉2。要保證目標函數值比原來更優。第七十頁，共二百九十頁，2022年，8月28日1.2.2線性規劃解的性質結束返回第七十一頁，共二百九十頁，2022年，8月28日1.3單純形法原理

本節通過一個引例，可以了解利用單純形法求解線性規劃問題的思路，并將每一次的結果與圖解法作一對比，其幾何意義更為清楚。第七十二頁，共二百九十頁，2022年，8月28日引例（上一章例）第七十三頁，共二百九十頁，2022年，8月28日求解線性規劃問題的基本思路1、構造初始可行基；2、求出一個基可行解（頂點）3、最優性檢驗：判斷是否最優解；4、基變化，轉2。要保證目標函數值比原來更優。從線性規劃解的性質可知求解線性規劃問題的基本思路。第七十四頁，共二百九十頁，2022年，8月28日第1步確定初始基可行解

根據顯然，可構成初等可行基B。

為基變量第七十五頁，共二百九十頁，2022年，8月28日

第2步求出基可行解

基變量用非基變量表示，并令非基變量為0時對應的解是否是最優解？第七十六頁，共二百九十頁，2022年，8月28日第3步最優性檢驗分析目標函數檢驗數<=0時，最優解>0時，無解換基，繼續只要取或的值可能增大。換入？基變量換出？基變量考慮將或換入為基變量第七十七頁，共二百九十頁，2022年，8月28日第4步基變換換入基變量：換入變量X2

（即選最大非負檢驗數對應的變量）一般選取對應的變量均可換入。第七十八頁，共二百九十頁，2022年，8月28日換出變量使換入的變量越大越好同時，新的解要可行。選非負的最小者對應的變量換出為換入變量，應換出？變量。思考：當時會怎樣？第七十九頁，共二百九十頁，2022年，8月28日因此，基由變為轉第2步：基變量用非基變量表示。

第3步：最優性判斷檢驗數存在正，按第4步換基繼續迭代均非正，停止（這時的解即是最優解）為換入變量，應換出

變量。第八十頁，共二百九十頁，2022年，8月28日

轉第2步第八十一頁，共二百九十頁，2022年，8月28日

繼續迭代,可得到:最優值Ｚ＝１４最優解第八十二頁，共二百九十頁，2022年，8月28日結合圖形法分析（單純形法的幾何意義）6—5—4—3—2—1—0x2| | | | | | | | |1 2 3 4 5 6 7 8 9x1A(0,3)B(2,3)C(4,2)D(4,0)第八十三頁，共二百九十頁，2022年，8月28日單純形法迭代原理從引例中了解了線性規劃的求解過程，將按上述思路介紹一般的線性規劃模型的求解方法——單純形法迭代原理。第八十四頁，共二百九十頁，2022年，8月28日觀察法:直接觀察得到初始可行基≤約束條件:加入松弛變量即形成可行基。（下頁）≥約束條件:加入非負人工變量,以后討論.1、初始基可行解的確定第八十五頁，共二百九十頁，2022年，8月28日1、初始基可行解的確定

不妨設為松弛變量，則約束方程組可表示為第八十六頁，共二百九十頁，2022年，8月28日

1、初始基可行解的確定第八十七頁，共二百九十頁，2022年，8月28日2、最優性檢驗與解的判別第八十八頁，共二百九十頁，2022年，8月28日

2、最優性檢驗與解的判別第八十九頁，共二百九十頁，2022年，8月28日

2、最優性檢驗與解的判別jnmjjjjjjnmjjjmiijijmiiixZZZcxZcZZacZbcZ????+=+===+=-=-+===10101'1'0

)()(

ss檢驗數令：令：第九十頁，共二百九十頁，2022年，8月28日

(1)最優解判別定理：若：為基可行解，且全部則為最優解。（2）唯一最優解判別定理：若所有則存在唯一最有解。2、最優性檢驗與解的判別第九十一頁，共二百九十頁，2022年，8月28日

（3）無窮多最優解判定定理：若：且存在某一個非基變量則存在無窮多最優解。（4）無界解判定定理：若有某一個非基變量并且對應的非基變量的系數

則具有無界解。

2、最優性檢驗與解的判別第九十二頁，共二百九十頁，2022年，8月28日

（4）之證明：2、最優性檢驗與解的判別第九十三頁，共二百九十頁，2022年，8月28日最優解判斷小結

（用非基變量的檢驗數）所有基變量中有非零人工變量某非基變量檢驗數為零唯一最優解無窮多最優解無可行解對任一有

換基繼續YYYYNNN無界解N以后討論第九十四頁，共二百九十頁，2022年，8月28日3、基變換換入變量確定

對應的為換入變量.(一般)注意：只要對應的變量均可作為換入變量此時，目標函數第九十五頁，共二百九十頁，2022年，8月28日

換出變量確定3、基變換Z

大大（在可行的范圍內）則對應的為換出變量.第九十六頁，共二百九十頁，2022年，8月28日4、迭代運算

寫成增廣矩陣的形式,進行迭代.第九十七頁，共二百九十頁，2022年，8月28日例：

4、迭代運算非基變量基變量001通過初等行變換化主列為主元第九十八頁，共二百九十頁，2022年，8月28日

4、迭代運算每次迭代的信息都在增廣矩陣及目標函數中。檢驗數第九十九頁，共二百九十頁，2022年，8月28日1.3單純形法迭代原理結束第一百頁，共二百九十頁，2022年，8月28日1.4單純形法的計算步驟

為書寫規范和便于計算，對單純形法的計算設計了單純形表。每一次迭代對應一張單純形表，含初始基可行解的單純形表稱為初始單純形表，含最優解的單純形表稱為最終單純形表。本節介紹用單純形表計算線性規劃問題的步驟。第一百零一頁，共二百九十頁，2022年，8月28日

在上一節單純形法迭代原理中可知，每一次迭代計算只要表示出當前的約束方程組及目標函數即可。單純形表第一百零二頁，共二百九十頁，2022年，8月28日E單位陣N非基陣基變量XB非基變量XN0單純形表第一百零三頁，共二百九十頁，2022年，8月28日

21000

檢驗數單純形表結構單純形表

—24/65/1C已知第一百零四頁，共二百九十頁，2022年，8月28日

21000

—24/65/1C檢驗數單純形表結構單純形表基可行解：第一百零五頁，共二百九十頁，2022年，8月28日單純形表結構單純形表

21000

—24/65/1C檢驗數有時不寫此項求第一百零六頁，共二百九十頁，2022年，8月28日單純形表結構單純形表

21000

—24/65/1C檢驗數求第一百零七頁，共二百九十頁，2022年，8月28日單純形表結構單純形表

21000

—24/65/1C檢驗數求不妨設此為主列主行第一百零八頁，共二百九十頁，2022年，8月28日單純形表結構單純形表

21000

—24/65/1C檢驗數主元第一百零九頁，共二百九十頁，2022年，8月28日用單純形表求解LP問題例、用單純形表求解LP問題第一百一十頁，共二百九十頁，2022年，8月28日解：化標準型第一百一十一頁，共二百九十頁，2022年，8月28日

21000

01505100

0

24620100511001

21000

—24/65/1主元化為1主列單位向量換出換入表1：列初始單純形表（單位矩陣對應的變量為基變量）正檢驗數中最大者對應的列為主列最小的值對應的行為主行第一百一十二頁，共二百九十頁，2022年，8月28日

21000

01505100

2

412/601/600104/60-1/61

01/30-1/30

15/524/26/4

0*52*2/6+0*4/61-2/3=表2：換基

（初等行變換，主列化為單位向量，主元為1）檢驗數>0確定主列最小確定主列主元第一百一十三頁，共二百九十頁，2022年，8月28日

21000

015/20015/4-15/2

2

7/21001/4-1/213/2010-1/43/2000-1/4-1/2

檢驗數<=0最優解為X=(7/2,3/2,15/2,0,0)目標函數值Z=8.5

2*7/21*3/2+0*15/28.5表3：換基

（初等行變換，主列化為單位向量，主元為1）第一百一十四頁，共二百九十頁，2022年，8月28日單純形法的表格形式上面假設x1,x2,…xm是基變量，即第i行約束方程的基變量正好是xi，而經過迭代后，基將發生變化，計算zj的式子也會發生變化。如果迭代后的第i行約束方程中的基變量為xBi，與xBi相應的目標函數系數為cBi，系數列向量為則其中，(cB)是由第1列第m行各約束方程中的基變量相應的目標函數依次組成的有序行向量。單純形法的表格形式是把用單純形法求出基本可行解、檢驗其最優性、迭代某步驟都用表格的方式來計算求出，其表格的形式有些像增廣矩陣，而其計算的方法也大體上使用矩陣的行的初等變換。以下用單純形表格來求解下例。

max50x1+100x2+0·s1+0·s2+0·s3.x1+x2+s1=300，

2x1+x2+s2=400，

x2+s3=250，

x1,x2,s1,s2,s3≥0.把上面的數據填入如下的單純形表格第一百一十五頁，共二百九十頁，2022年，8月28日單純形法的表格形式按照線性規劃模型在表中填入相對應的值，如上表所示；在上表中有一個m*m的單位矩陣，對應的基變量為s1,s2,s3；在zj行中填入第j列與cB列中對應的元素相乘相加所得的值，如z2=0*1+0*1+0*1=0，所在zi行中的第2位數填入0；在行中填入cj-zj所得的值，如；z表示把初始基本可行解代入目標函數求得的目標函數值，即b列*cB列；初始基本可行解為s1=300,s2=400,s3=250,x1=0,x2=0;由于250/1最小，因此確定s3為出基變量；由于，因此確定x2為入基變量。出基變量所在行，入基變量所在列的交匯處為主元，這里是a32=1，在表中畫圈以示區別。第一百一十六頁，共二百九十頁，2022年，8月28日單純形法的表格形式以下進行第一次迭代，其變量為x2,s1,s2,通過矩陣行的初等變換，求出一個新的基本可行解，具體的做法用行的初等變換使得x2的系數向量p2變換成單位向量，由于主元在p2的第3分量上，所以這個單位向量是也就是主元素變成1。這樣我們又得到的第1次迭代的單純表如下所示。在上表中第3個基變量s1已被x2代替，故基變量列中的第3個基變量應變為x2。由于第0次迭代表中的主元a32已經為1，因此第3行不變。為了使第1行的a12為0，只需把第3行*(-1)加到第1行即可。同樣可以求得第2行。求得第1次迭代的基本可行解為s1=50,s2=150,x2=250,x1=0,s3=0,z=25000.第一百一十七頁，共二百九十頁，2022年，8月28日單純形法的表格形式從上表可以看出，第一次迭代的，因此不是最優解。設x1為入基變量，從此值可知b1/a11=50為最小正數，因此，s1為出基變量，a11為主元，繼續迭代如下表所示。從上表中可知第二次迭代得到的基本可行解為x1=50,x2=250,s1=0,s2=50,s3=0,這時z=27500。由于檢驗數都<0，因此所求得的基本可行解為最優解，z=27500為最優目標函數值。實際上，我們可以連續地使用一個單純形表，不必一次迭代重畫一個表頭。第一百一十八頁，共二百九十頁，2022年，8月28日

單純形法的計算及示例單純形法幾何解釋---頂點尋優例：maxz=2x1+3x2maxz=2x1+3x2+0x3+0x4 s.tx1+x23標準化s.tx1+x2+x3=3 x1+2x24 x1+2x2+x4=4 x10,x20 xj0,(j=1,2,3,4) （1）初始基本可行解的選擇：-----坐標原點處 令x1=x2=0,由

x1+x2+x3=3

x1+2x2+x4=4

（2）是否為最優解的判定:-----計算檢驗數 若

x1↑1,則

x3↓1,x4↓1,

σ1=2-（01+01）=2 σj=△z=cj-zj=cj-ciaij，稱σj為檢驗數。x3=3-(x1+x2)x4=4-(x1+2x2)

解得X=(0,0,3,4)T第一百一十九頁，共二百九十頁，2022年，8月28日若

x2↑1,則

x3↓1,x4↓2,

σ2=3-(01+02)=3 ****當所有檢驗數均有σj

0時，則為最優解。****（3）找新的頂點（基本可行解）： 直觀看，x2↑1,則z↑3，∴應找A點，即增加x2。x2可增加多少？需要保證x3=3-(x1+x2)0

x4=4-(x1+2x2)0， ∴

x2=min（3/1，4/2），從而 x3=1-(x1/2-x4

/2）

x2=2-(x1/2+x4/2)

令x1=x4=0，則新的基本可行解為X=(0，2，1，0)T重復上述過程，直至所有檢驗數

σj

0。第一百二十頁，共二百九十頁，2022年，8月28日繼續迭代：找新的頂點（基本可行解）： 若x1↑1,則z↑1/2，∴應找B點，即增加x1。

x1可增加多少？需要保證x3=1-(x1/2-x4/2)0

x2=2-(x1/2+x4/2)0， ∴

x1=min（2，4），從而 x1=2-(2x3-x4)

x2=1-(-x3+x4), 則新的基本可行解為X=(2，1，0，0)T若

x1↑1,則

x3↓1/2,x2↓1/2,

σ1=2-（01/2+31/2）=1/2若

x4↑1,則

x3↓-1/2,x2↓1/2,

σ4=0-（0(-1/2)+31/2）=-3/2σ3=-1, σ4=-1, zmax=7第一百二十一頁，共二百九十頁，2022年，8月28日①②O

C

A

BX1X2(0,2)(3,0)(2,1)34第一百二十二頁，共二百九十頁，2022年，8月28日Cj→x1x2x3x4XBbCB1 1 1 01 2 012 3 0 034x3x400cj-zj23003/1=34/2=21/2 0 1 -1/21/2 1 01/2x3x212cj-zj1/2 00-3/203241 0 2 -10 1 -11x1x221cj-zj0 0 -1 -1231.4.2單純形法計算：θi第一百二十三頁，共二百九十頁，2022年，8月28日單純形法計算過程總結：（1）化標準形，列初始單純形表；（2）計算檢驗數：σj=△z=cj-zj=cj-ciaij（3）最優性判斷：當所有檢驗數均有σj

0時，則為最優解。否則 迭代求新的基本可行解。（4）迭代： 入基變量：取max{σj0}=

σk→xk 出基變量：取min{θi=bi/aikaik>0}=θl

→x(l)

主元素：[alk] 新單純表：pk=單位向量注：當所有檢驗數σj

0時，若存在非基變量檢驗數為0時，則有無窮多解，否則只有唯一最優解。i=1m第一百二十四頁，共二百九十頁，2022年，8月28日單純形法的計算步驟例用單純形法求解解：將數學模型化為標準形式：不難看出x4、x5可作為初始基變量，列單純形表計算。第一百二十五頁，共二百九十頁，2022年，8月28日單純形法的計算步驟20－x221/3150120753017131/30－90－22560x111017/31/31250128/9-1/92/335/300-98/9-1/9-7/3第一百二十六頁，共二百九十頁，2022年，8月28日

21000

01505100

0

24620100511001

21000練習:一般主列選擇正檢驗數中最大者對應的列,也可選擇其它正檢驗數的列.以第2列為主列,用單純形法求解。正檢驗數對應的列為主列第一百二十七頁，共二百九十頁，2022年，8月28日結束2.4單純形法的計算步驟第一百二十八頁，共二百九十頁，2022年，8月28日2.5.1單純形法的進一步討論一、大M法二、兩階段法----人工變量法第一百二十九頁，共二百九十頁，2022年，8月28日人工變量法問題：線性規劃問題化為標準形時，若約束條件的系數矩陣中不存在單位矩陣，如何構造初始可行基？

第一百三十頁，共二百九十頁，2022年，8月28日人工變量法加入人工變量設線性規劃問題的標準型為：第一百三十一頁，共二百九十頁，2022年，8月28日

加入人工變量,構造初始可行基.人工變量法系數矩陣為單位矩陣，可構成初始可行基。第一百三十二頁，共二百九十頁，2022年，8月28日

約束條件已改變，目標函數如何調整？人工變量法第一百三十三頁，共二百九十頁，2022年，8月28日“懲罰”人工變量！（1）大M法（2）兩階段法第一百三十四頁，共二百九十頁，2022年，8月28日一、大M法人工變量在目標函數中的系數為-M,其中，M為任意大的正數。目標函數中添加“罰因子”-M（M是任意大的正數）為人工變量系數，只要人工變量>0，則目標函數不可能實現最優。第一百三十五頁，共二百九十頁，2022年，8月28日例:求解線性規劃問題一、大M法第一百三十六頁，共二百九十頁，2022年，8月28日

一、大M法解:加入松弛變量和剩余變量進行標準化,加入人工變量構造初始可行基.

第一百三十七頁，共二百九十頁，2022年，8月28日求解結果出現檢驗數非正若基變量中含非零的人工變量，則無可行解；否則，有最優解。一、大M法用單純形法求解（見下頁）。目標函數中添加“罰因子”-M為人工變量系數，只要人工變量>0，則目標函數不可能實現最優。第一百三十八頁，共二百九十頁，2022年，8月28日1-21-412-2013-6MM-13M-13

-1-1

x1

x2

x3

0

x411-M

x63-M

x71Cj-ZjCj

CBXBb100-1000-M

00

x4

x5

113/21

00100100

-

M

-M

x6

x7

表1（初始單純形表）一、大M法（單純形法求解）第一百三十九頁，共二百九十頁，2022年，8月28日3-20010

-201

1M-103

-1-1x1

x2

x30x410-M

x61-1x31Cj-ZjCjCBXBb100-1000-M

00

x4

x5

1

0-11-201

01-3M

-

M-M

x6

x7

一、大M法（單純形法求解）表2第一百四十頁，共二百九十頁，2022年，8月28日300010-2011003

-1-1

x1

x2

x30x412-1x21-1x31Cj-ZjCjCBXBb1-20-1000-1

00

x4

x5

4

i

2-51-2011-M-1

-M

-

M-M

x6

x7

表3一、大M法（單純形法求解）第一百四十一頁，共二百九十頁，2022年，8月28日1000100010003

-1-1

x1

x2

x33x14-1x21-1x392Cj

CBXB

b1/3-2/3

0-12/3-4/3

-1/3-1/3

00

x4

x5

2/3-5/3

1-24/3-7/3

1/3-M2/3-M

-

M-M

x6

x7

表4一、大M法（單純形法求解）最優解為目標函數值z=2檢驗數均非正，此為最終單純形表第一百四十二頁，共二百九十頁，2022年，8月28日在實際問題中有些模型并不含有單位矩陣，為了得到一組基向量和初基可行解，在約束條件的等式左端加一組虛擬變量，得到一組基變量。這種人為加的變量稱為人工變量，構成的可行基稱為人工基，用大M法或兩階段法求解，這種用人工變量作橋梁的求解方法稱為人工變量法。【例1-20】用大M法解下列線性規劃1.大M單純形法大M和兩階段單純形法1.5單純形法

SimplexMethod第一百四十三頁，共二百九十頁，2022年，8月28日【解】首先將數學模型化為標準形式式中x4，x5為松弛變量，x5可作為一個基變量，第一、三約束中分別加入人工變量x6、x7，目標函數中加入―Mx6―Mx7一項，得到人工變量單純形法數學模型用前面介紹的單純形法求解，見下表。1.5單純形法

SimplexMethod第一百四十四頁，共二百九十頁，2022年，8月28日Cj32－100－M－MbCBXBx1x2x3x4x5x6x7－M

0－Mx6x5x7－4123－1－212[1]－1000101000014101→λj3-2M2+M-1+2M↑－M000－M0－1x6x5x3－6－32[5]3－2001－1000101003→81λj5