線性規(guī)劃及單純型法

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

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

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

x1+2x2

84x1

164x2

12x1、x2

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

目標函數(shù)MaxZ=2x1+3x2約束條件x1+2x2

84x1

164x2

12x1、x2

0x1

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

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

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

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

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

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

目標函數(shù)MaxZ=2x1+3x2約束條件x1+2x2

84x1

164x2

12x1、x2

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

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

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

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

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

目標函數(shù)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)

目標函數(shù)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

目標函數(shù)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

目標函數(shù)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

目標函數(shù)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

目標函數(shù)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最優(yōu)解(4,2)圖解法第三十一頁，共二百九十頁，2022年，8月28日例1.目標函數(shù)：

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

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

x1=50，x2=250

最優(yōu)目標值z=27500圖解法對于只有兩個決策變量的線性規(guī)劃問題，可以在平面直角坐標系上作圖表示線性規(guī)劃問題的有關概念，并求解。下面通過例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）目標函數(shù)z=50x1+100x2，當z取某一固定值時得到一條直線，直線上的每一點都具有相同的目標函數(shù)值，稱之為“等值線”。平行移動等值線，當移動到B點時，z在可行域內(nèi)實現(xiàn)了最大化。A，B，C，D，E是可行域的頂點，對有限個約束條件則其可行域的頂點也是有限的。x1x2z=20000=50x1+100x2圖2-2z=27500=50x1+100x2z=0=50x1+100x2z=10000=50x1+100x2CBADE第三十六頁，共二百九十頁，2022年，8月28日圖解法求解步驟由全部約束條件作圖求出可行域；作目標函數(shù)等值線，確定使目標函數(shù)最優(yōu)的移動方向；平移目標函數(shù)的等值線，找出最優(yōu)點，算出最優(yōu)值。第三十七頁，共二百九十頁，2022年，8月28日線性規(guī)劃問題求解的

幾種可能結(jié)果(a)唯一最優(yōu)解

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

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

MaxZ=x1+x2

-2x1+x2

4

x1-x2

2

x1、x2

0

x2x1線性規(guī)劃問題求解的

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

MaxZ=2x1+3x2x1+2x2

84x1

164x2

12

-2x1+x24x1、x2

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

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

（由圖解法得到的啟示）可行域是有界或無界的凸多邊形。若線性規(guī)劃問題存在最優(yōu)解，它一定可以在可行域的頂點得到。若兩個頂點同時得到最優(yōu)解，則其連線上的所有點都是最優(yōu)解。解題思路：找出凸集的頂點，計算其目標函數(shù)值，比較即得。第四十二頁，共二百九十頁，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)最優(yōu)解(3,6)4x1+6x2=482x1+2x2=18第四十八頁，共二百九十頁，2022年，8月28日1.2.1線性規(guī)劃的圖解法結(jié)束返回第四十九頁，共二百九十頁，2022年，8月28日1.2.2線性規(guī)劃解的性質(zhì)線性規(guī)劃解的概念線性規(guī)劃問題的幾何意義（單純形法原理）繼續(xù)返回第五十頁，共二百九十頁，2022年，8月28日線性規(guī)劃問題解的概念標準型可行解:滿足AX=b,X>=0的解X稱為線性規(guī)劃問題的可行解。最優(yōu)解：使Z=CX達到最大值的可行解稱為最優(yōu)解。第五十一頁，共二百九十頁，2022年，8月28日

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

求解線性規(guī)劃問題解的概念第五十四頁，共二百九十頁，2022年，8月28日基解：稱上面求出的X解為基解?；尚薪猓悍秦摰幕釾稱為基可行解可行基：對應基可行解的基稱為可行基線性規(guī)劃問題解的概念T基變量令可求出：第五十五頁，共二百九十頁，2022年，8月28日線性規(guī)劃解的關系圖非可行解可行解

基可行解

基解線性規(guī)劃問題解的概念

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

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

20452017Y

35005410Y

40550-120N5100-50415N652.5001.517.5Y

7540-3022N82430019

Y

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

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

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

凸組合：

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

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

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

X的正分量對應的列向量線性無關定理3：若可行域有界，線性規(guī)劃問題的目標函數(shù)一定可以在其可行域的頂點上達到最優(yōu)。定理2：線性規(guī)劃問題的基可行解X對應于可行域D的頂點。證明：反證法。分兩步。第六十五頁，共二百九十頁，2022年，8月28日幾點結(jié)論：線性規(guī)劃問題的可行域是凸集?；尚薪馀c可行域的頂點一一對應，可行域有有限多個頂點。最優(yōu)解必在頂點上得到。第六十六頁，共二百九十頁，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可行域為凸集目標函數(shù)不同時等值線的斜率不同最優(yōu)解在頂點產(chǎn)生

目標函數(shù)等值線的斜率最優(yōu)解第六十七頁，共二百九十頁，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可行域為凸集目標函數(shù)不同時等值線的斜率不同最優(yōu)解在頂點產(chǎn)生

目標函數(shù)等值線的斜率最優(yōu)解第六十八頁，共二百九十頁，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可行域為凸集目標函數(shù)不同時等值線的斜率不同最優(yōu)解在頂點產(chǎn)生

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

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

根據(jù)顯然，可構成初等可行基B。

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

第2步求出基可行解

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

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

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

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

轉(zhuǎn)第2步第八十一頁，共二百九十頁，2022年，8月28日

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

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

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

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

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

)()(

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

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

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

則具有無界解。

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

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

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

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

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

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

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

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

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

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

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

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

21000

檢驗數(shù)單純形表結(jié)構單純形表

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

21000

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

21000

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

21000

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

21000

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

21000

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

21000

01505100

0

24620100511001

21000

—24/65/1主元化為1主列單位向量換出換入表1：列初始單純形表（單位矩陣對應的變量為基變量）正檢驗數(shù)中最大者對應的列為主列最小的值對應的行為主行第一百一十二頁，共二百九十頁，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）檢驗數(shù)>0確定主列最小確定主列主元第一百一十三頁，共二百九十頁，2022年，8月28日

21000

015/20015/4-15/2

2

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

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

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

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

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

單純形法的計算及示例單純形法幾何解釋---頂點尋優(yōu)例：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）是否為最優(yōu)解的判定:-----計算檢驗數(shù) 若

x1↑1,則

x3↓1,x4↓1,

σ1=2-（01+01）=2 σj=△z=cj-zj=cj-ciaij，稱σj為檢驗數(shù)。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 ****當所有檢驗數(shù)均有σj

0時，則為最優(yōu)解。****（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重復上述過程，直至所有檢驗數(shù)

σj

0。第一百二十頁，共二百九十頁，2022年，8月28日繼續(xù)迭代：找新的頂點（基本可行解）： 若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日單純形法計算過程總結(jié)：（1）化標準形，列初始單純形表；（2）計算檢驗數(shù)：σj=△z=cj-zj=cj-ciaij（3）最優(yōu)性判斷：當所有檢驗數(shù)均有σj

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

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

→x(l)

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

0時，若存在非基變量檢驗數(shù)為0時，則有無窮多解，否則只有唯一最優(yōu)解。i=1m第一百二十四頁，共二百九十頁，2022年，8月28日單純形法的計算步驟例用單純形法求解解：將數(shù)學模型化為標準形式：不難看出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練習:一般主列選擇正檢驗數(shù)中最大者對應的列,也可選擇其它正檢驗數(shù)的列.以第2列為主列,用單純形法求解。正檢驗數(shù)對應的列為主列第一百二十七頁，共二百九十頁，2022年，8月28日結(jié)束2.4單純形法的計算步驟第一百二十八頁，共二百九十頁，2022年，8月28日2.5.1單純形法的進一步討論一、大M法二、兩階段法----人工變量法第一百二十九頁，共二百九十頁，2022年，8月28日人工變量法問題：線性規(guī)劃問題化為標準形時，若約束條件的系數(shù)矩陣中不存在單位矩陣，如何構造初始可行基？

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

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

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

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

第一百三十七頁，共二百九十頁，2022年，8月28日求解結(jié)果出現(xiàn)檢驗數(shù)非正若基變量中含非零的人工變量，則無可行解；否則，有最優(yōu)解。一、大M法用單純形法求解（見下頁）。目標函數(shù)中添加“罰因子”-M為人工變量系數(shù)，只要人工變量>0，則目標函數(shù)不可能實現(xiàn)最優(yōu)。第一百三十八頁，共二百九十頁，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法（單純形法求解）最優(yōu)解為目標函數(shù)值z=2檢驗數(shù)均非正，此為最終單純形表第一百四十二頁，共二百九十頁，2022年，8月28日在實際問題中有些模型并不含有單位矩陣，為了得到一組基向量和初基可行解，在約束條件的等式左端加一組虛擬變量，得到一組基變量。這種人為加的變量稱為人工變量，構成的可行基稱為人工基，用大M法或兩階段法求解，這種用人工變量作橋梁的求解方法稱為人工變量法?！纠?-20】用大M法解下列線性規(guī)劃1.大M單純形法大M和兩階段單純形法1.5單純形法

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