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

關(guān)于線性規(guī)劃及單純型法

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

MaxZ=2x1+3x2系數(shù)第2步--定義目標(biāo)函數(shù)第8頁,共290頁，2024年2月25日，星期天對我們有何限制?第9頁,共290頁，2024年2月25日，星期天第3步--表示約束條件

x1+2x2

84x1

164x2

12x1、x2

0第10頁,共290頁，2024年2月25日，星期天該計劃的數(shù)學(xué)模型

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

84x1

164x2

12x1、x2

0x1

x2第11頁,共290頁，2024年2月25日，星期天線性規(guī)劃問題的共同特征一組決策變量X表示一個方案,一般X大于等于零。約束條件是線性等式或不等式。目標(biāo)函數(shù)是線性的。求目標(biāo)函數(shù)最大化或最小化第12頁,共290頁，2024年2月25日，星期天

線性規(guī)劃模型的一般形式第13頁,共290頁，2024年2月25日，星期天線性規(guī)劃問題的標(biāo)準(zhǔn)形式標(biāo)準(zhǔn)形式為:目標(biāo)函數(shù)最大約束條件等式?jīng)Q策變量非負(fù)第14頁,共290頁，2024年2月25日，星期天

簡寫為第15頁,共290頁，2024年2月25日，星期天

用向量表示第16頁,共290頁，2024年2月25日，星期天

用矩陣表示C—價值向量b—資源向量X—決策變量向量第17頁,共290頁，2024年2月25日，星期天

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

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

84x1

164x2

12x1、x2

0第18頁,共290頁，2024年2月25日，星期天

minZ=CX等價于maxZ’=-CX“”約束：加入非負(fù)松馳變量一般線性規(guī)劃問題的標(biāo)準(zhǔn)形化例：第19頁,共290頁，2024年2月25日，星期天

“”約束：減去非負(fù)剩余變量；

Max例：可正可負(fù)（即無約束）；第20頁,共290頁，2024年2月25日，星期天

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

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

84x1

164x2

12x1、x2

0x1

x2第26頁,共290頁，2024年2月25日，星期天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)

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

84x1

164x2

12x1、x2

04x1

164x2

16圖解法第27頁,共290頁，2024年2月25日，星期天9—8—7—6—5—4—3—2—1—0x2

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

84x1

164x2

12x1、x2

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

84x1

164x2

16可行域圖解法第28頁,共290頁，2024年2月25日，星期天9—8—7—6—5—4—3—2—1—0| | | | | | | | |1 2 3 4 5 6 7 8 9x1x2

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

84x1

164x2

12x1、x2

0x1+2x2

84x1

164x2

16可行域BCDEA圖解法第29頁,共290頁，2024年2月25日，星期天9—8—7—6—5—4—3—2—1—0x2

目標(biāo)函數(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圖解法第30頁,共290頁，2024年2月25日，星期天9—8—7—6—5—4—3—2—1—0x2

目標(biāo)函數(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)圖解法第31頁,共290頁，2024年2月25日，星期天例1.目標(biāo)函數(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)目標(biāo)值z=27500圖解法對于只有兩個決策變量的線性規(guī)劃問題，可以在平面直角坐標(biāo)系上作圖表示線性規(guī)劃問題的有關(guān)概念，并求解。下面通過例1詳細(xì)講解其方法：第32頁,共290頁，2024年2月25日，星期天圖解法

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

為坐標(biāo)向量建立直角坐標(biāo)系。在直角坐標(biāo)系里，圖上任意一點的坐標(biāo)代表了決策變量的一組值，例1的每個約束條件都代表一個半平面。x2x1X2≥0X2=0x2x1X1≥0X1=0第33頁,共290頁，2024年2月25日，星期天圖解法（2）對每個不等式(約束條件)，先取其等式在坐標(biāo)系中作直線，然后確定不等式所決定的半平面。100200300100200300x1+x2≤300x1+x2=3001001002002x1+x2≤4002x1+x2=400300200300400第34頁,共290頁，2024年2月25日，星期天圖解法（3）把五個圖合并成一個圖，取各約束條件的公共部分，如圖2-1所示。100100x2≤250x2=250200300200300x1x2x2=0x1=0x2=250x1+x2=3002x1+x2=400圖2-1第35頁,共290頁，2024年2月25日，星期天圖解法（4）目標(biāo)函數(shù)z=50x1+100x2，當(dāng)z取某一固定值時得到一條直線，直線上的每一點都具有相同的目標(biāo)函數(shù)值，稱之為“等值線”。平行移動等值線，當(dāng)移動到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第36頁,共290頁，2024年2月25日，星期天圖解法求解步驟由全部約束條件作圖求出可行域；作目標(biāo)函數(shù)等值線，確定使目標(biāo)函數(shù)最優(yōu)的移動方向；平移目標(biāo)函數(shù)的等值線，找出最優(yōu)點，算出最優(yōu)值。第37頁,共290頁，2024年2月25日，星期天線性規(guī)劃問題求解的

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

x26—5—4—3—2—1—0| | | | | | | | |1 2 3 4 5 6 7 8 9x1第38頁,共290頁，2024年2月25日，星期天(b)無窮多最優(yōu)解6—5—4—3—2—1—0x2| | | | | | | | |1 2 3 4 5 6 7 8 9x1線性規(guī)劃問題求解的

幾種可能結(jié)果第39頁,共290頁，2024年2月25日，星期天(c)無界解

MaxZ=x1+x2

-2x1+x2

4

x1-x2

2

x1、x2

0

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

幾種可能結(jié)果第40頁,共290頁，2024年2月25日，星期天(d)無可行解

MaxZ=2x1+3x2x1+2x2

84x1

164x2

12

-2x1+x2

4x1、x2

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

幾種可能結(jié)果第41頁,共290頁，2024年2月25日，星期天圖解法的幾點結(jié)論:

（由圖解法得到的啟示）可行域是有界或無界的凸多邊形。若線性規(guī)劃問題存在最優(yōu)解，它一定可以在可行域的頂點得到。若兩個頂點同時得到最優(yōu)解，則其連線上的所有點都是最優(yōu)解。解題思路：找出凸集的頂點，計算其目標(biāo)函數(shù)值，比較即得。第42頁,共290頁，2024年2月25日，星期天練習(xí)：

用圖解法求解LP問題

MaxZ=34x1+40x24x1+6x2

482x1+2x2

182x1+x2

16x1、x2

0第43頁,共290頁，2024年2月25日，星期天圖解法—（練習(xí)）

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第44頁,共290頁，2024年2月25日，星期天圖解法—（練習(xí)）

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第45頁,共290頁，2024年2月25日，星期天圖解法—（練習(xí)）

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第46頁,共290頁，2024年2月25日，星期天圖解法—（練習(xí)）

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)第47頁,共290頁，2024年2月25日，星期天圖解法—（練習(xí)）

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第48頁,共290頁，2024年2月25日，星期天1.2.1線性規(guī)劃的圖解法結(jié)束返回第49頁,共290頁，2024年2月25日，星期天1.2.2線性規(guī)劃解的性質(zhì)線性規(guī)劃解的概念線性規(guī)劃問題的幾何意義（單純形法原理）繼續(xù)返回第50頁,共290頁，2024年2月25日，星期天線性規(guī)劃問題解的概念標(biāo)準(zhǔn)型可行解:滿足AX=b,X>=0的解X稱為線性規(guī)劃問題的可行解。最優(yōu)解：使Z=CX達(dá)到最大值的可行解稱為最優(yōu)解。第51頁,共290頁，2024年2月25日，星期天

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

求解線性規(guī)劃問題解的概念第54頁,共290頁，2024年2月25日，星期天基解：稱上面求出的X解為基解。基可行解：非負(fù)的基解X稱為基可行解可行基：對應(yīng)基可行解的基稱為可行基線性規(guī)劃問題解的概念T基變量令可求出：第55頁,共290頁，2024年2月25日，星期天線性規(guī)劃解的關(guān)系圖非可行解可行解

基可行解

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

最優(yōu)解？第56頁,共290頁，2024年2月25日，星期天

例：求基解、基可行解、最優(yōu)解。線性規(guī)劃問題解的概念第57頁,共290頁，2024年2月25日，星期天10051045Y

20452017Y

35005410Y

40550-120N5100-50415N652.5001.517.5Y

7540-3022N82430019

Y

是否基可行解最優(yōu)解線性規(guī)劃問題解的概念解：第58頁,共290頁，2024年2月25日，星期天

：求基解、基可行解、最優(yōu)解。練習(xí)：線性規(guī)劃問題解的概念第59頁,共290頁，2024年2月25日，星期天線性規(guī)劃問題的幾何意義基本概念凸集：線性規(guī)劃問題的幾何意義第60頁,共290頁，2024年2月25日，星期天

頂點:若K是凸集，X∈K；若X不能用不同的兩點的線性組合表示為：則X為頂點.凸集線性規(guī)劃問題的幾何意義第61頁,共290頁，2024年2月25日，星期天

凸組合：

Xn=2，k=3線性規(guī)劃問題的幾何意義第62頁,共290頁，2024年2月25日，星期天定理1:若線性規(guī)劃問題存在可行域,則其可行域:是凸集.基本定理證明:線性規(guī)劃問題的幾何意義第63頁,共290頁，2024年2月25日，星期天

只要驗證X在D中即可第64頁,共290頁，2024年2月25日，星期天

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

X的正分量對應(yīng)的列向量線性無關(guān)定理3：若可行域有界，線性規(guī)劃問題的目標(biāo)函數(shù)一定可以在其可行域的頂點上達(dá)到最優(yōu)。定理2：線性規(guī)劃問題的基可行解X對應(yīng)于可行域D的頂點。證明：反證法。分兩步。第65頁,共290頁，2024年2月25日，星期天幾點結(jié)論：線性規(guī)劃問題的可行域是凸集。基可行解與可行域的頂點一一對應(yīng)，可行域有有限多個頂點。最優(yōu)解必在頂點上得到。第66頁,共290頁，2024年2月25日，星期天圖解法9—8—7—6—5—4—3—2—1—0x2| | | | | | | | |1 2 3 4 5 6 7 8 9x1x1+2x2

84x1

164x2

16可行域BCDEA可行域為凸集目標(biāo)函數(shù)不同時等值線的斜率不同最優(yōu)解在頂點產(chǎn)生

目標(biāo)函數(shù)等值線的斜率最優(yōu)解第67頁,共290頁，2024年2月25日，星期天圖解法9—8—7—6—5—4—3—2—1—0x2| | | | | | | | |1 2 3 4 5 6 7 8 9x1x1+2x2

84x1

164x2

16可行域BCDEA可行域為凸集目標(biāo)函數(shù)不同時等值線的斜率不同最優(yōu)解在頂點產(chǎn)生

目標(biāo)函數(shù)等值線的斜率最優(yōu)解第68頁,共290頁，2024年2月25日，星期天圖解法9—8—7—6—5—4—3—2—1—0x2| | | | | | | | |1 2 3 4 5 6 7 8 9x1x1+2x2

84x1

164x2

16可行域BCDEA可行域為凸集目標(biāo)函數(shù)不同時等值線的斜率不同最優(yōu)解在頂點產(chǎn)生

目標(biāo)函數(shù)等值線的斜率最優(yōu)解第69頁,共290頁，2024年2月25日，星期天求解LP的基本思路1、構(gòu)造初始可行基；2、求出一個基可行解（頂點）3、最優(yōu)性檢驗：判斷是否最優(yōu)解；4、基變化，轉(zhuǎn)2。要保證目標(biāo)函數(shù)值比原來更優(yōu)。第70頁,共290頁，2024年2月25日，星期天1.2.2線性規(guī)劃解的性質(zhì)結(jié)束返回第71頁,共290頁，2024年2月25日，星期天1.3單純形法原理

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

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

為基變量第75頁,共290頁，2024年2月25日，星期天

第2步求出基可行解

基變量用非基變量表示，并令非基變量為0時對應(yīng)的解是否是最優(yōu)解？第76頁,共290頁，2024年2月25日，星期天第3步最優(yōu)性檢驗分析目標(biāo)函數(shù)檢驗數(shù)<=0時，最優(yōu)解>0時，無解換基，繼續(xù)只要取或的值可能增大。換入？基變量換出？基變量考慮將或換入為基變量第77頁,共290頁，2024年2月25日，星期天第4步基變換換入基變量：換入變量X2

（即選最大非負(fù)檢驗數(shù)對應(yīng)的變量）一般選取對應(yīng)的變量均可換入。第78頁,共290頁，2024年2月25日，星期天換出變量使換入的變量越大越好同時，新的解要可行。選非負(fù)的最小者對應(yīng)的變量換出為換入變量，應(yīng)換出？變量。思考：當(dāng)時會怎樣？第79頁,共290頁，2024年2月25日，星期天因此，基由變?yōu)檗D(zhuǎn)第2步：基變量用非基變量表示。

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

變量。第80頁,共290頁，2024年2月25日，星期天

轉(zhuǎn)第2步第81頁,共290頁，2024年2月25日，星期天

繼續(xù)迭代,可得到:最優(yōu)值Ｚ＝１４最優(yōu)解第82頁,共290頁，2024年2月25日，星期天結(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)第83頁,共290頁，2024年2月25日，星期天單純形法迭代原理從引例中了解了線性規(guī)劃的求解過程，將按上述思路介紹一般的線性規(guī)劃模型的求解方法——單純形法迭代原理。第84頁,共290頁，2024年2月25日，星期天觀察法:直接觀察得到初始可行基≤約束條件:加入松弛變量即形成可行基。（下頁）≥約束條件:加入非負(fù)人工變量,以后討論.1、初始基可行解的確定第85頁,共290頁，2024年2月25日，星期天1、初始基可行解的確定

不妨設(shè)為松弛變量，則約束方程組可表示為第86頁,共290頁，2024年2月25日，星期天

1、初始基可行解的確定第87頁,共290頁，2024年2月25日，星期天2、最優(yōu)性檢驗與解的判別第88頁,共290頁，2024年2月25日，星期天

2、最優(yōu)性檢驗與解的判別第89頁,共290頁，2024年2月25日，星期天

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

)()(

ss檢驗數(shù)令：令：第90頁,共290頁，2024年2月25日，星期天

(1)最優(yōu)解判別定理：若：為基可行解，且全部則為最優(yōu)解。（2）唯一最優(yōu)解判別定理：若所有則存在唯一最有解。2、最優(yōu)性檢驗與解的判別第91頁,共290頁，2024年2月25日，星期天

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

則具有無界解。

2、最優(yōu)性檢驗與解的判別第92頁,共290頁，2024年2月25日，星期天

（4）之證明：2、最優(yōu)性檢驗與解的判別第93頁,共290頁，2024年2月25日，星期天最優(yōu)解判斷小結(jié)

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

換基繼續(xù)YYYYNNN無界解N以后討論第94頁,共290頁，2024年2月25日，星期天3、基變換換入變量確定

對應(yīng)的為換入變量.(一般)注意：只要對應(yīng)的變量均可作為換入變量此時，目標(biāo)函數(shù)第95頁,共290頁，2024年2月25日，星期天

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

大大（在可行的范圍內(nèi)）則對應(yīng)的為換出變量.第96頁,共290頁，2024年2月25日，星期天4、迭代運算

寫成增廣矩陣的形式,進(jìn)行迭代.第97頁,共290頁，2024年2月25日，星期天例：

4、迭代運算非基變量基變量001通過初等行變換化主列為主元第98頁,共290頁，2024年2月25日，星期天

4、迭代運算每次迭代的信息都在增廣矩陣及目標(biāo)函數(shù)中。檢驗數(shù)第99頁,共290頁，2024年2月25日，星期天1.3單純形法迭代原理結(jié)束第100頁,共290頁，2024年2月25日，星期天1.4單純形法的計算步驟

為書寫規(guī)范和便于計算，對單純形法的計算設(shè)計了單純形表。每一次迭代對應(yīng)一張單純形表，含初始基可行解的單純形表稱為初始單純形表，含最優(yōu)解的單純形表稱為最終單純形表。本節(jié)介紹用單純形表計算線性規(guī)劃問題的步驟。第101頁,共290頁，2024年2月25日，星期天

在上一節(jié)單純形法迭代原理中可知，每一次迭代計算只要表示出當(dāng)前的約束方程組及目標(biāo)函數(shù)即可。單純形表第102頁,共290頁，2024年2月25日，星期天E單位陣N非基陣基變量XB非基變量XN0單純形表第103頁,共290頁，2024年2月25日，星期天

21000

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

—24/65/1C已知第104頁,共290頁，2024年2月25日，星期天

21000

—24/65/1C檢驗數(shù)單純形表結(jié)構(gòu)單純形表基可行解：第105頁,共290頁，2024年2月25日，星期天單純形表結(jié)構(gòu)單純形表

21000

—24/65/1C檢驗數(shù)有時不寫此項求第106頁,共290頁，2024年2月25日，星期天單純形表結(jié)構(gòu)單純形表

21000

—24/65/1C檢驗數(shù)求第107頁,共290頁，2024年2月25日，星期天單純形表結(jié)構(gòu)單純形表

21000

—24/65/1C檢驗數(shù)求不妨設(shè)此為主列主行第108頁,共290頁，2024年2月25日，星期天單純形表結(jié)構(gòu)單純形表

21000

—24/65/1C檢驗數(shù)主元第109頁,共290頁，2024年2月25日，星期天用單純形表求解LP問題例、用單純形表求解LP問題第110頁,共290頁，2024年2月25日，星期天解：化標(biāo)準(zhǔn)型第111頁,共290頁，2024年2月25日，星期天

21000

01505100

0

24620100511001

21000

—24/65/1主元化為1主列單位向量換出換入表1：列初始單純形表（單位矩陣對應(yīng)的變量為基變量）正檢驗數(shù)中最大者對應(yīng)的列為主列最小的值對應(yīng)的行為主行第112頁,共290頁，2024年2月25日，星期天

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確定主列最小確定主列主元第113頁,共290頁，2024年2月25日，星期天

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)目標(biāo)函數(shù)值Z=8.5

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

（初等行變換，主列化為單位向量，主元為1）第114頁,共290頁，2024年2月25日，星期天單純形法的表格形式上面假設(shè)x1,x2,…xm是基變量，即第i行約束方程的基變量正好是xi，而經(jīng)過迭代后，基將發(fā)生變化，計算zj的式子也會發(fā)生變化。如果迭代后的第i行約束方程中的基變量為xBi，與xBi相應(yīng)的目標(biāo)函數(shù)系數(shù)為cBi，系數(shù)列向量為則其中，(cB)是由第1列第m行各約束方程中的基變量相應(yīng)的目標(biāo)函數(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ù)填入如下的單純形表格第115頁,共290頁，2024年2月25日，星期天單純形法的表格形式按照線性規(guī)劃模型在表中填入相對應(yīng)的值，如上表所示；在上表中有一個m*m的單位矩陣，對應(yīng)的基變量為s1,s2,s3；在zj行中填入第j列與cB列中對應(yīng)的元素相乘相加所得的值，如z2=0*1+0*1+0*1=0，所在zi行中的第2位數(shù)填入0；在行中填入cj-zj所得的值，如；z表示把初始基本可行解代入目標(biāo)函數(shù)求得的目標(biāo)函數(shù)值，即b列*cB列；初始基本可行解為s1=300,s2=400,s3=250,x1=0,x2=0;由于250/1最小，因此確定s3為出基變量；由于，因此確定x2為入基變量。出基變量所在行，入基變量所在列的交匯處為主元，這里是a32=1，在表中畫圈以示區(qū)別。第116頁,共290頁，2024年2月25日，星期天單純形法的表格形式以下進(jìn)行第一次迭代，其變量為x2,s1,s2,通過矩陣行的初等變換，求出一個新的基本可行解，具體的做法用行的初等變換使得x2的系數(shù)向量p2變換成單位向量，由于主元在p2的第3分量上，所以這個單位向量是也就是主元素變成1。這樣我們又得到的第1次迭代的單純表如下所示。在上表中第3個基變量s1已被x2代替，故基變量列中的第3個基變量應(yīng)變?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.第117頁,共290頁，2024年2月25日，星期天單純形法的表格形式從上表可以看出，第一次迭代的，因此不是最優(yōu)解。設(shè)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)目標(biāo)函數(shù)值。實際上，我們可以連續(xù)地使用一個單純形表，不必一次迭代重畫一個表頭。第118頁,共290頁，2024年2月25日，星期天

單純形法的計算及示例單純形法幾何解釋---頂點尋優(yōu)例：maxz=2x1+3x2maxz=2x1+3x2+0x3+0x4 s.tx1+x2

3標(biāo)準(zhǔn)化s.tx1+x2+x3=3 x1+2x2

4

x1+2x2+x4=4 x1

0,x2

0 xj

0,(j=1,2,3,4) （1）初始基本可行解的選擇：-----坐標(biāo)原點處 令x1=x2=0,由

x1+x2+x3=3

x1+2x2+x4=4

（2）是否為最優(yōu)解的判定:-----計算檢驗數(shù) 若

x1↑1,則

x3↓1,x4↓1,

σ1=2-（0

1+0

1）=2 σj=△z=cj-zj=cj-

ciaij，稱σj為檢驗數(shù)。x3=3-(x1+x2)x4=4-(x1+2x2)

解得X=(0,0,3,4)T第119頁,共290頁，2024年2月25日，星期天若

x2↑1,則

x3↓1,x4↓2,

σ2=3-(0

1+0

2)=3 ****當(dāng)所有檢驗數(shù)均有σj

0時，則為最優(yōu)解。****（3）找新的頂點（基本可行解）： 直觀看，x2↑1,則z↑3，∴應(yīng)找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重復(fù)上述過程，直至所有檢驗數(shù)

σj

0。第120頁,共290頁，2024年2月25日，星期天繼續(xù)迭代：找新的頂點（基本可行解）： 若x1↑1,則z↑1/2，∴應(yīng)找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-（0

1/2+3

1/2）=1/2若

x4↑1,則

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

σ4=0-（0

(-1/2)+3

1/2）=-3/2σ3=-1, σ4=-1, zmax=7第121頁,共290頁，2024年2月25日，星期天①②O

C

A

BX1X2(0,2)(3,0)(2,1)34第122頁,共290頁，2024年2月25日，星期天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第123頁,共290頁，2024年2月25日，星期天單純形法計算過程總結(jié)：（1）化標(biāo)準(zhǔn)形，列初始單純形表；（2）計算檢驗數(shù)：σj=△z=cj-zj=cj-

ciaij（3）最優(yōu)性判斷：當(dāng)所有檢驗數(shù)均有σj

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

σk→xk 出基變量：取min{θi=bi/aik

aik>0}=θl

→x(l)

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

0時，若存在非基變量檢驗數(shù)為0時，則有無窮多解，否則只有唯一最優(yōu)解。i=1m第124頁,共290頁，2024年2月25日，星期天單純形法的計算步驟例用單純形法求解解：將數(shù)學(xué)模型化為標(biāo)準(zhǔn)形式：不難看出x4、x5可作為初始基變量，列單純形表計算。第125頁,共290頁，2024年2月25日，星期天單純形法的計算步驟20－x221/3150120753017131/30－90－22560x111017/31/31250128/9-1/92/335/300-98/9-1/9-7/3第126頁,共290頁，2024年2月25日，星期天

21000

01505100

0

24620100511001

21000練習(xí):一般主列選擇正檢驗數(shù)中最大者對應(yīng)的列,也可選擇其它正檢驗數(shù)的列.以第2列為主列,用單純形法求解。正檢驗數(shù)對應(yīng)的列為主列第127頁,共290頁，2024年2月25日，星期天結(jié)束2.4單純形法的計算步驟第128頁,共290頁，2024年2月25日，星期天2.5.1單純形法的進(jìn)一步討論一、大M法二、兩階段法----人工變量法第129頁,共290頁，2024年2月25日，星期天人工變量法問題：線性規(guī)劃問題化為標(biāo)準(zhǔn)形時，若約束條件的系數(shù)矩陣中不存在單位矩陣，如何構(gòu)造初始可行基？

第130頁,共290頁，2024年2月25日，星期天人工變量法加入人工變量設(shè)線性規(guī)劃問題的標(biāo)準(zhǔn)型為：第131頁,共290頁，2024年2月25日，星期天

加入人工變量,構(gòu)造初始可行基.人工變量法系數(shù)矩陣為單位矩陣，可構(gòu)成初始可行基。第132頁,共290頁，2024年2月25日，星期天

約束條件已改變，目標(biāo)函數(shù)如何調(diào)整？人工變量法第133頁,共290頁，2024年2月25日，星期天“懲罰”人工變量?。?）大M法（2）兩階段法第134頁,共290頁，2024年2月25日，星期天一、大M法人工變量在目標(biāo)函數(shù)中的系數(shù)為-M,其中，M為任意大的正數(shù)。目標(biāo)函數(shù)中添加“罰因子”-M（M是任意大的正數(shù)）為人工變量系數(shù)，只要人工變量>0，則目標(biāo)函數(shù)不可能實現(xiàn)最優(yōu)。第135頁,共290頁，2024年2月25日，星期天例:求解線性規(guī)劃問題一、大M法第136頁,共290頁，2024年2月25日，星期天

一、大M法解:加入松弛變量和剩余變量進(jìn)行標(biāo)準(zhǔn)化,加入人工變量構(gòu)造初始可行基.

第137頁,共290頁，2024年2月25日，星期天求解結(jié)果出現(xiàn)檢驗數(shù)非正若基變量中含非零的人工變量，則無可行解；否則，有最優(yōu)解。一、大M法用單純形法求解（見下頁）。目標(biāo)函數(shù)中添加“罰因子”-M為人工變量系數(shù)，只要人工變量>0，則目標(biāo)函數(shù)不可能實現(xiàn)最優(yōu)。第138頁,共290頁，2024年2月25日，星期天1-21-412-201

3-6MM-13M-13

-1-1

x1

x2

x3

0

x411-M

x63-M

x71Cj-ZjCj

CBXBb

100-1000-M

00

x4

x5

113/21

00100100

-

M

-M

x6

x7

表1（初始單純形表）一、大M法（單純形法求解）第139頁,共290頁，2024年2月25日，星期天

3-20010

-201

1M-103

-1-1x1

x2

x3

0x410-M

x61-1x31Cj-ZjCjCBXBb

100-1000-M

00

x4

x5

1

0-11-201

01-3M

-

M-M

x6

x7

一、大M法（單純形法求解）表2第140頁,共290頁，2024年2月25日，星期天3

00010