1、關于線性規(guī)劃及單純型法第一張，PPT共二百九十頁，創(chuàng)作于2022年6月 線性規(guī)劃問題的提出 線性規(guī)劃的基本概念 線性規(guī)劃的數(shù)學模型 線性規(guī)劃問題的標準形式繼續(xù)返回1.1 線性規(guī)劃問題及其數(shù)學模型第二張，PPT共二百九十頁，創(chuàng)作于2022年6月問題的提出例: 生產(chǎn)計劃問題第三張，PPT共二百九十頁，創(chuàng)作于2022年6月產(chǎn)品I產(chǎn)品2如何安排生產(chǎn)使利潤最大？第四張，PPT共二百九十頁，創(chuàng)作于2022年6月決策變量（Decision variables）目標函數(shù)（Objective function）約束條件（Constraint conditions）可行域（Feasible region)最優(yōu)解（

2、Optimal solution)基本概念問題中要確定的未知量，表明規(guī)劃中的用數(shù)量表示的方案、措施，可由決策者決定和控制。它是決策變量的函數(shù)指決策變量取值時受到的各種資源條件的限制，通常表達為含決策變量的等式或不等式。滿足約束條件的決策變量的取值范圍可行域中使目標函數(shù)達到最優(yōu)的決策變量的值第五張，PPT共二百九十頁，創(chuàng)作于2022年6月是問題中要確定的未知量，表明規(guī)劃中的用數(shù)量表示的方案、措施，可由決策者決定和控制。第1步 -確定決策變量設 I的產(chǎn)量 II的產(chǎn)量 利潤第六張，PPT共二百九十頁，創(chuàng)作于2022年6月第2步 -定義目標函數(shù)Max Z = x1 + x2決策變量第七張，PPT共二百

3、九十頁，創(chuàng)作于2022年6月 Max Z = 2 x1 + 3 x2系數(shù)第2步 -定義目標函數(shù)第八張，PPT共二百九十頁，創(chuàng)作于2022年6月對我們有何限制?第九張，PPT共二百九十頁，創(chuàng)作于2022年6月第3步 -表示約束條件 x1 + 2 x2 8 4 x1 16 4 x2 12 x1、 x2 0第十張，PPT共二百九十頁，創(chuàng)作于2022年6月該計劃的數(shù)學模型 目標函數(shù) Max Z = 2x1 + 3x2 約束條件 x1 + 2x2 8 4x1 16 4x2 12 x1、 x2 0 x1 x2第十一張，PPT共二百九十頁，創(chuàng)作于2022年6月線性規(guī)劃問題的共同特征一組決策變量X表示一個方案

4、,一般X大于等于零。約束條件是線性等式或不等式。目標函數(shù)是線性的。 求目標函數(shù)最大化或最小化第十二張，PPT共二百九十頁，創(chuàng)作于2022年6月 線性規(guī)劃模型的一般形式 第十三張，PPT共二百九十頁，創(chuàng)作于2022年6月線性規(guī)劃問題的標準形式標準形式為:目標函數(shù)最大約束條件等式?jīng)Q策變量非負第十四張，PPT共二百九十頁，創(chuàng)作于2022年6月 簡寫為第十五張，PPT共二百九十頁，創(chuàng)作于2022年6月 用向量表示第十六張，PPT共二百九十頁，創(chuàng)作于2022年6月 用矩陣表示C價值向量b資源向量X決策變量向量第十七張，PPT共二百九十頁，創(chuàng)作于2022年6月 min Z=CX 等價于 max Z = -

5、CX“” 約束：加入非負松馳變量一般線性規(guī)劃問題的標準形化例： 目標函數(shù) Max Z = 2x1 + 3x2 約束條件 x1 + 2x2 8 4x1 16 4x2 12 x1、 x2 0第十八張，PPT共二百九十頁，創(chuàng)作于2022年6月 min Z=CX 等價于 max Z = -CX“” 約束：加入非負松馳變量一般線性規(guī)劃問題的標準形化例：第十九張，PPT共二百九十頁，創(chuàng)作于2022年6月 “” 約束： 減去非負剩余變量； Max 例 ： 可正可負（即無約束）；第二十張，PPT共二百九十頁，創(chuàng)作于2022年6月 解 ：標準形為第二十一張，PPT共二百九十頁，創(chuàng)作于2022年6月線性規(guī)劃問題的

6、數(shù)學模型例 將下列線性規(guī)劃問題化為標準形式用 替換 ，且 解:（）因為x3無符號要求 ，即x3取正值也可取負值，標準型中要求變量非負，所以第二十二張，PPT共二百九十頁，創(chuàng)作于2022年6月線性規(guī)劃問題的數(shù)學模型(2) 第一個約束條件是“”號，在“”左端加入松馳變量x4，x40,化為等式；(3) 第二個約束條件是“”號，在“”左端減去剩余變量x5，x50；(4) 第3個約束方程右端常數(shù)項為-5，方程兩邊同乘以(-1),將右端常數(shù)項化為正數(shù)； (5) 目標函數(shù)是最小值，為了化為求最大值，令z=-z,得到max z=-z，即當z達到最小值時z達到最大值，反之亦然;第二十三張，PPT共二百九十頁，創(chuàng)

7、作于2022年6月線性規(guī)劃問題的數(shù)學模型標準形式如下：第二十四張，PPT共二百九十頁，創(chuàng)作于2022年6月 圖解法 線性規(guī)劃問題求解的 幾種可能結果 由圖解法得到的啟示1.2.1 線性規(guī)劃的圖解法繼續(xù)返回第二十五張，PPT共二百九十頁，創(chuàng)作于2022年6月例1的數(shù)學模型 目標函數(shù) Max Z = 2x1 + 3x2 約束條件 x1 + 2x2 8 4x1 16 4x2 12 x1、 x2 0 x1 x2第二十六張，PPT共二百九十頁，創(chuàng)作于2022年6月9 8 7 6 5 4 3 2 1 0 |123456789x1x2x1 + 2x2 8(0, 4)(8, 0) 目標函數(shù) Max Z = 2

8、x1 + 3x2 約束條件 x1 + 2x2 8 4x1 16 4x2 12 x1、 x2 04x1 164 x2 16圖解法第二十七張，PPT共二百九十頁，創(chuàng)作于2022年6月9 8 7 6 5 4 3 2 1 0 x2 目標函數(shù) Max Z = 2x1 + 3x2 約束條件 x1 + 2x2 8 4x1 16 4x2 12 x1、 x2 0|123456789x1x1 + 2x2 84x1 164 x2 16可行域圖解法第二十八張，PPT共二百九十頁，創(chuàng)作于2022年6月9 8 7 6 5 4 3 2 1 0 |123456789x1x2 目標函數(shù) Max Z = 2x1 + 3x2 約束

9、條件 x1 + 2x2 8 4x1 16 4x2 12 x1、 x2 0 x1 + 2x2 84x1 164 x2 16可行域BCDEA圖解法第二十九張，PPT共二百九十頁，創(chuàng)作于2022年6月9 8 7 6 5 4 3 2 1 0 x2 目標函數(shù) Max Z = 2x1 + 3x2 約束條件 x1 + 2x2 8 4x1 16 4x2 12 x1、 x2 0|123456789x1x1 + 2x2 84x1 164 x2 16BCDEA2x1 + 3x2 = 6圖解法第三十張，PPT共二百九十頁，創(chuàng)作于2022年6月9 8 7 6 5 4 3 2 1 0 x2 目標函數(shù) Max Z = 2x

10、1 + 3x2 約束條件 x1 + 2x2 8 4x1 16 4x2 12 x1、 x2 0|123456789x1x1 + 2x2 84x1 164 x2 16BCDEAx1+ 2x2=8 4x1 =16最優(yōu)解 (4, 2)圖解法第三十一張，PPT共二百九十頁，創(chuàng)作于2022年6月例1.目標函數(shù)： Max z = 50 x1 + 100 x2 約束條件： s.t. x1 + x2 300 (A) 2 x1 + x2 400 (B) x2 250 (C) x1 0 (D) x2 0 (E)得到最優(yōu)解： x1 = 50， x2 = 250 最優(yōu)目標值 z = 27500圖 解 法 對于只有兩個決

11、策變量的線性規(guī)劃問題，可以在平面直角坐標系上作圖表示線性規(guī)劃問題的有關概念，并求解。 下面通過例1詳細講解其方法：第三十二張，PPT共二百九十頁，創(chuàng)作于2022年6月圖 解 法 (1)分別取決策變量X1 , X2 為坐標向量建立直角坐標系。在直角坐標系里，圖上任意一點的坐標代表了決策變量的一組值，例1的每個約束條件都代表一個半平面。x2x1X20X2=0 x2x1X10X1=0第三十三張，PPT共二百九十頁，創(chuàng)作于2022年6月圖 解 法（2）對每個不等式(約束條件)，先取其等式在坐標系中作直線，然后確定不等式所決定的半平面。100200300100200300 x1+x2300 x1+x2=

12、3001001002002x1+x24002x1+x2=400300200300400第三十四張，PPT共二百九十頁，創(chuàng)作于2022年6月圖 解 法（3）把五個圖合并成一個圖，取各約束條件的公共部分，如圖2-1所示。100100 x2250 x2=250200300200300 x1x2x2=0 x1=0 x2=250 x1+x2=3002x1+x2=400圖2-1第三十五張，PPT共二百九十頁，創(chuàng)作于2022年6月圖 解 法（4）目標函數(shù)z=50 x1+100 x2，當z取某一固定值時得到一條直線，直線上的每一點都具有相同的目標函數(shù)值，稱之為“等值線”。平行移動等值線，當移動到B點時，z在可

13、行域內實現(xiàn)了最大化。A，B，C，D，E是可行域的頂點，對有限個約束條件則其可行域的頂點也是有限的。x1x2z=20000=50 x1+100 x2圖2-2z=27500=50 x1+100 x2z=0=50 x1+100 x2z=10000=50 x1+100 x2CBADE第三十六張，PPT共二百九十頁，創(chuàng)作于2022年6月圖解法求解步驟由全部約束條件作圖求出可行域；作目標函數(shù)等值線，確定使目標函數(shù)最優(yōu)的移動方向；平移目標函數(shù)的等值線，找出最優(yōu)點，算出最優(yōu)值。第三十七張，PPT共二百九十頁，創(chuàng)作于2022年6月線性規(guī)劃問題求解的 幾種可能結果(a) 唯一最優(yōu)解 x26 5 4 3 2 1 0

14、 |123456789x1第三十八張，PPT共二百九十頁，創(chuàng)作于2022年6月(b)無窮多最優(yōu)解6 5 4 3 2 1 0 x2|123456789x1線性規(guī)劃問題求解的 幾種可能結果第三十九張，PPT共二百九十頁，創(chuàng)作于2022年6月 (c)無界解 Max Z = x1 + x2 -2x1 + x2 4 x1 - x2 2 x1、 x2 0 x2x1線性規(guī)劃問題求解的 幾種可能結果第四十張，PPT共二百九十頁，創(chuàng)作于2022年6月(d)無可行解 Max Z = 2x1 + 3x2 x1 +2 x2 8 4 x1 16 4x2 12 -2x1 + x2 4 x1、 x2 0可行域為空集線性規(guī)劃

15、問題求解的 幾種可能結果第四十一張，PPT共二百九十頁，創(chuàng)作于2022年6月圖解法的幾點結論:（由圖解法得到的啟示）可行域是有界或無界的凸多邊形。若線性規(guī)劃問題存在最優(yōu)解，它一定可以在可行域的頂點得到。若兩個頂點同時得到最優(yōu)解，則其連線上的所有點都是最優(yōu)解。解題思路：找出凸集的頂點，計算其目標函數(shù)值，比較即得。第四十二張，PPT共二百九十頁，創(chuàng)作于2022年6月練習：用圖解法求解LP問題 Max Z = 34 x1 + 40 x24 x1 + 6 x2 48 2 x1 + 2 x2 182 x1 + x2 16x1、 x2 0第四十三張，PPT共二百九十頁，創(chuàng)作于2022年6月圖解法 （練習）

16、 18 16 14 12 10 8 6 4 2 0 |24681012141618x1x24x1 + 6x2 482x1 + 2x2 182x1 + x2 16第四十四張，PPT共二百九十頁，創(chuàng)作于2022年6月圖解法 （練習） 18 16 14 12 10 8 6 4 2 0 |24681012141618x1x24x1 + 6x2 482x1 + 2x2 182x1 + x2 16可行域ABCDE第四十五張，PPT共二百九十頁，創(chuàng)作于2022年6月圖解法 （練習） 18 16 14 12 10 8 6 4 2 0 |24681012141618x1x24x1 + 6x2 482x1 + 2

17、x2 182x1 + x2 16ABCDE (8,0)(0,6.8)34x1 + 40 x2 = 272第四十六張，PPT共二百九十頁，創(chuàng)作于2022年6月圖解法 （練習） 18 16 14 12 10 8 6 4 2 0 |24681012141618x1x24x1 + 6x2 482x1 + 2x2 182x1 + x2 16ABCDE (8,0)(0,6.8)第四十七張，PPT共二百九十頁，創(chuàng)作于2022年6月圖解法 （練習） x218 16 14 12 10 8 6 4 2 0 |24681012141618x14x1 + 6x2 482x1 + 2x2 182x1 + x2 16AB

18、CDE (8,0)(0,6.8)最優(yōu)解 (3,6)4x1+ 6x2=48 2x1+ 2x2 =18第四十八張，PPT共二百九十頁，創(chuàng)作于2022年6月1.2.1 線性規(guī)劃的圖解法結束返回第四十九張，PPT共二百九十頁，創(chuàng)作于2022年6月1.2.2 線性規(guī)劃解的性質線性規(guī)劃解的概念線性規(guī)劃問題的幾何意義 （單純形法原理）繼續(xù)返回第五十張，PPT共二百九十頁，創(chuàng)作于2022年6月線性規(guī)劃問題解的概念標準型可行解:滿足AX=b, X=0的解X稱為線性規(guī)劃問題的可行解。最優(yōu)解：使Z=CX達到最大值的可行解稱為最優(yōu)解。第五十一張，PPT共二百九十頁，創(chuàng)作于2022年6月 基：若B是矩陣A中mm階非奇異

19、子矩陣（B0），則B是線性規(guī)劃問題的一個基。不妨設： , j=1，2，,m 基向量。 ，j=1，2，,m 基變量。 , j=m+1,n 非基變量。線性規(guī)劃問題解的概念第五十二張，PPT共二百九十頁，創(chuàng)作于2022年6月例 求線性規(guī)劃問題的所有基矩陣。解: 約束方程的系數(shù)矩陣為25矩陣 r(A)=2，2階子矩陣有10個，其中基矩陣只有9個，即第五十三張，PPT共二百九十頁，創(chuàng)作于2022年6月 求解 線性規(guī)劃問題解的概念第五十四張，PPT共二百九十頁，創(chuàng)作于2022年6月基解：稱上面求出的X解為基解。基可行解：非負的基解X稱為基可行解可行基：對應基可行解的基稱為可行基線性規(guī)劃問題解的概念T基變量

20、令 可求出：第五十五張，PPT共二百九十頁，創(chuàng)作于2022年6月 線性規(guī)劃解的關系圖 非可行解可行解 基可行解 基解線性規(guī)劃問題解的概念 最優(yōu)解？第五十六張，PPT共二百九十頁，創(chuàng)作于2022年6月 例：求基解、基可行解、最優(yōu)解。線性規(guī)劃問題解的概念第五十七張，PPT共二百九十頁，創(chuàng)作于2022年6月1 0 0 5 10 4 5 Y 2 0 4 5 2 0 17 Y 3 5 0 0 5 4 10 Y 4 0 5 5 0 -1 20 N5 10 0 -5 0 4 15 N6 5 2.5 0 0 1.5 17.5 Y 7 5 4 0 -3 0 22 N8 2 4 3 0 0 19 Y 是否基可行解

21、最優(yōu)解線性規(guī)劃問題解的概念解：第五十八張，PPT共二百九十頁，創(chuàng)作于2022年6月 ：求基解、基可行解、最優(yōu)解。練習：線性規(guī)劃問題解的概念第五十九張，PPT共二百九十頁，創(chuàng)作于2022年6月線性規(guī)劃問題的幾何意義 基本概念凸集：線性規(guī)劃問題的幾何意義第六十張，PPT共二百九十頁，創(chuàng)作于2022年6月 頂點:若K是凸集，XK；若X不能用不同的兩點 的線性組合表示為： 則X為頂點. 凸集線性規(guī)劃問題的幾何意義第六十一張，PPT共二百九十頁，創(chuàng)作于2022年6月 凸組合： X n=2，k=3線性規(guī)劃問題的幾何意義第六十二張，PPT共二百九十頁，創(chuàng)作于2022年6月定理1: 若線性規(guī)劃問題存在可行域,

22、 則其可行域: 是凸集. 基本定理證明:線性規(guī)劃問題的幾何意義第六十三張，PPT共二百九十頁，創(chuàng)作于2022年6月 只要驗證X在D中即可第六十四張，PPT共二百九十頁，創(chuàng)作于2022年6月 引理：可行解X為基可行解 X的正分量對應的列向量線性無關定理3：若可行域有界，線性規(guī)劃 問題的目標函數(shù)一定可以在 其可行域的頂點上達到最優(yōu)。定理2：線性規(guī)劃問題的基可行解X 對應于可行域D的頂點。 證明：反證法。分兩步。第六十五張，PPT共二百九十頁，創(chuàng)作于2022年6月幾點結論：線性規(guī)劃問題的可行域是凸集。基可行解與可行域的頂點一一對應，可行域有有限多個頂點。最優(yōu)解必在頂點上得到。第六十六張，PPT共二百

23、九十頁，創(chuàng)作于2022年6月圖解法9 8 7 6 5 4 3 2 1 0 x2|123456789x1x1 + 2x2 84x1 164 x2 16可行域BCDEA可行域為凸集目標函數(shù)不同時等值線的斜率不同最優(yōu)解在頂點產(chǎn)生 目標函數(shù)等值線的斜率最優(yōu)解第六十七張，PPT共二百九十頁，創(chuàng)作于2022年6月圖解法9 8 7 6 5 4 3 2 1 0 x2|123456789x1x1 + 2x2 84x1 164 x2 16可行域BCDEA可行域為凸集目標函數(shù)不同時等值線的斜率不同最優(yōu)解在頂點產(chǎn)生 目標函數(shù)等值線的斜率最優(yōu)解第六十八張，PPT共二百九十頁，創(chuàng)作于2022年6月圖解法9 8 7 6 5

24、 4 3 2 1 0 x2|123456789x1x1 + 2x2 84x1 164 x2 16可行域BCDEA可行域為凸集目標函數(shù)不同時等值線的斜率不同最優(yōu)解在頂點產(chǎn)生 目標函數(shù)等值線的斜率最優(yōu)解第六十九張，PPT共二百九十頁，創(chuàng)作于2022年6月求解LP的基本思路1、構造初始可行基；2、求出一個基可行解（頂點）3、最優(yōu)性檢驗：判斷是否最優(yōu)解；4、基變化，轉2。要保證目標函數(shù)值比 原來更優(yōu)。第七十張，PPT共二百九十頁，創(chuàng)作于2022年6月1.2.2 線性規(guī)劃解的性質結束返回第七十一張，PPT共二百九十頁，創(chuàng)作于2022年6月1.3 單純形法原理 本節(jié)通過一個引例，可以了解利用單純形法求解線

25、性規(guī)劃問題的思路，并將每一次的結果與圖解法作一對比，其幾何意義更為清楚。第七十二張，PPT共二百九十頁，創(chuàng)作于2022年6月引例（上一章例）第七十三張，PPT共二百九十頁，創(chuàng)作于2022年6月求解線性規(guī)劃問題的基本思路1、構造初始可行基；2、求出一個基可行解（頂點）3、最優(yōu)性檢驗：判斷是否最優(yōu)解；4、基變化，轉2。要保證目標函數(shù)值比 原來更優(yōu)。從線性規(guī)劃解的性質可知求解線性規(guī)劃問題的基本思路。第七十四張，PPT共二百九十頁，創(chuàng)作于2022年6月第1步 確定初始基可行解 根據(jù)顯然 ， 可構成初等可行基B 。 為基變量第七十五張，PPT共二百九十頁，創(chuàng)作于2022年6月 第2步 求出基可行解 基變

26、量用非基變量表示，并令非基變量為 0時對應的解是否是最優(yōu)解？第七十六張，PPT共二百九十頁，創(chuàng)作于2022年6月第3步 最優(yōu)性檢驗分析目標函數(shù)檢驗數(shù)0 時， 無解換基，繼續(xù)只要取 或 的 值可能增大。換入？基變量換出？基變量考慮將 或 換入為基變量第七十七張，PPT共二百九十頁，創(chuàng)作于2022年6月第4步 基變換換入基變量：換入變量X2 （即選最大非負檢驗數(shù)對應的變量）一般選取 對應的變量均可換入。第七十八張，PPT共二百九十頁，創(chuàng)作于2022年6月?lián)Q出變量使換入的變量越大越好同時，新的解要可行。選非負 的最小者對應的變量換出為換入變量，應換出 ？ 變量。思考：當 時會怎樣？第七十九張，PPT

27、共二百九十頁，創(chuàng)作于2022年6月因此，基由 變?yōu)?轉第2步：基變量用非基變量表示。 第3步：最優(yōu)性判斷 檢驗數(shù) 存在正，按第4步換基繼續(xù)迭代 均非正，停止 （這時的解即是最優(yōu)解）為換入變量，應換出 變量。第八十張，PPT共二百九十頁，創(chuàng)作于2022年6月 轉 第2步第八十一張，PPT共二百九十頁，創(chuàng)作于2022年6月 繼續(xù)迭代, 可得到:最優(yōu)值最優(yōu)解第八十二張，PPT共二百九十頁，創(chuàng)作于2022年6月結合圖形法分析（單純形法的幾何意義）6 5 4 3 2 1 0 x2|123456789x1A(0,3)B(2,3)C(4,2)D(4,0)第八十三張，PPT共二百九十頁，創(chuàng)作于2022年6月單

28、純形法迭代原理從引例中了解了線性規(guī)劃的求解過程，將按上述思路介紹一般的線性規(guī)劃模型的求解方法單純形法迭代原理。第八十四張，PPT共二百九十頁，創(chuàng)作于2022年6月觀察法:直接觀察得到初始可行基約束條件: 加入松弛變量即形成可行基。（下頁）約束條件: 加入非負人工變量, 以后討論. 1、初始基可行解的確定第八十五張，PPT共二百九十頁，創(chuàng)作于2022年6月1、初始基可行解的確定 不妨設 為松弛變量，則約束方程組可表示為第八十六張，PPT共二百九十頁，創(chuàng)作于2022年6月 1、初始基可行解的確定第八十七張，PPT共二百九十頁，創(chuàng)作于2022年6月2、最優(yōu)性檢驗與解的判別第八十八張，PPT共二百九十

29、頁，創(chuàng)作于2022年6月 2、最優(yōu)性檢驗與解的判別第八十九張，PPT共二百九十頁，創(chuàng)作于2022年6月 2、最優(yōu)性檢驗與解的判別jnmjjjjjjnmjjjmiijijmiiixZZZcxZcZZacZbcZ+=+=+=-=-+=1010110 )()( ss檢驗數(shù)令：令：第九十張，PPT共二百九十頁，創(chuàng)作于2022年6月 (1) 最優(yōu)解判別定理：若： 為基可行解，且全部 則 為最優(yōu)解。（2）唯一最優(yōu)解判別定理：若所有 則存在唯一最有解。 2、最優(yōu)性檢驗與解的判別第九十一張，PPT共二百九十頁，創(chuàng)作于2022年6月 （3）無窮多最優(yōu)解判定定理：若： 且存在某一個非基變量 則存在無窮多最優(yōu)解。（

30、4）無界解判定定理：若有某一個非基 變量 并且對應的非基變量的系數(shù) 則具有無界解。 2、最優(yōu)性檢驗與解的判別第九十二張，PPT共二百九十頁，創(chuàng)作于2022年6月 （4）之證明：2、最優(yōu)性檢驗與解的判別第九十三張，PPT共二百九十頁，創(chuàng)作于2022年6月最優(yōu)解判斷小結 （用非基變量的檢驗數(shù)）所有 基變量中有非零人工變量某非基變量檢驗數(shù)為零唯一最優(yōu)解無窮多最優(yōu)解無可行解對任一 有 換基繼續(xù)YYYYNNN無界解N以后討論第九十四張，PPT共二百九十頁，創(chuàng)作于2022年6月3、基變換換入變量確定 對應的 為換入變量. (一般)注意：只要 對應的變量 均可作為換入變量此時，目標函數(shù)第九十五張，PPT共二

31、百九十頁，創(chuàng)作于2022年6月 換出變量確定3、基變換Z 大大（在可行的范圍內）則對應的 為換出變量.第九十六張，PPT共二百九十頁，創(chuàng)作于2022年6月4、迭代運算 寫成增廣矩陣的形式,進行迭代.第九十七張，PPT共二百九十頁，創(chuàng)作于2022年6月例： 4、迭代運算非基變量基變量001通過初等行變換化主列為主元第九十八張，PPT共二百九十頁，創(chuàng)作于2022年6月 4、迭代運算每次迭代的信息都在增廣矩陣及目標函數(shù)中。檢驗數(shù)第九十九張，PPT共二百九十頁，創(chuàng)作于2022年6月1.3 單純形法迭代原理結束第一百張，PPT共二百九十頁，創(chuàng)作于2022年6月1.4 單純形法的計算步驟 為書寫規(guī)范和便于

32、計算，對單純形法的計算設計了單純形表。每一次迭代對應一張單純形表，含初始基可行解的單純形表稱為初始單純形表，含最優(yōu)解的單純形表稱為最終單純形表。本節(jié)介紹用單純形表計算線性規(guī)劃問題的步驟。第一百零一張，PPT共二百九十頁，創(chuàng)作于2022年6月 在上一節(jié)單純形法迭代原理中可知，每一次迭代計算只要表示出當前的約束方程組及目標函數(shù)即可。 單純形表第一百零二張，PPT共二百九十頁，創(chuàng)作于2022年6月E單位陣N非基陣基變量XB非基變量XN0 單純形表第一百零三張，PPT共二百九十頁，創(chuàng)作于2022年6月 2 1 0 0 0 檢驗數(shù)單純形表結構 單純形表 24/65/1C已知第一百零四張，PPT共二百九十

33、頁，創(chuàng)作于2022年6月 2 1 0 0 0 24/65/1C檢驗數(shù)單純形表結構 單純形表基可行解：第一百零五張，PPT共二百九十頁，創(chuàng)作于2022年6月單純形表結構 單純形表 2 1 0 0 0 24/65/1C檢驗數(shù)有時不寫此項求第一百零六張，PPT共二百九十頁，創(chuàng)作于2022年6月單純形表結構 單純形表 2 1 0 0 0 24/65/1C檢驗數(shù)求第一百零七張，PPT共二百九十頁，創(chuàng)作于2022年6月單純形表結構 單純形表 2 1 0 0 0 24/65/1C檢驗數(shù)求不妨設此為主列主行第一百零八張，PPT共二百九十頁，創(chuàng)作于2022年6月單純形表結構 單純形表 2 1 0 0 0 24/

34、65/1C檢驗數(shù)主元第一百零九張，PPT共二百九十頁，創(chuàng)作于2022年6月用單純形表求解LP問題例、用單純形表求解LP問題第一百一十張，PPT共二百九十頁，創(chuàng)作于2022年6月解：化標準型第一百一十一張，PPT共二百九十頁，創(chuàng)作于2022年6月 2 1 0 0 0 0 15 0 5 1 0 0 0 24 6 2 0 1 0 0 5 1 1 0 0 1 2 1 0 0 0 24/65/1主元化為1主列單位向量 換出 換入表1：列初始單純形表 （單位矩陣對應的變量為基變量）正檢驗數(shù)中最大者對應的列為主列最小的值對應的行為主行第一百一十二張，PPT共二百九十頁，創(chuàng)作于2022年6月 2 1 0 0

35、0 0 15 0 5 1 0 0 2 4 1 2/6 0 1 /6 0 0 1 0 4/6 0 -1/6 1 0 1/3 0 -1/3 0 15/524/26/4 0*5 2*2/6 +0*4/61- 2/3=表2：換基 （初等行變換，主列化為單位向量，主元為1）檢驗數(shù)0確定主列 最小確定主列主元第一百一十三張，PPT共二百九十頁，創(chuàng)作于2022年6月 2 1 0 0 0 0 15/2 0 0 1 5/4 -15/2 2 7/2 1 0 0 1/4 -1/2 1 3/2 0 1 0 -1/4 3/2 0 0 0 -1/4 -1/2 檢驗數(shù)=0最優(yōu)解為X=(7/2,3/2,15/2,0,0)目標

36、函數(shù)值Z=8.5 2*7/2 1*3/2+0*15/28.5表3：換基 （初等行變換，主列化為單位向量，主元為1）第一百一十四張，PPT共二百九十頁，創(chuàng)作于2022年6月單純形法的表格形式 上面假設x1,x2,xm是基變量，即第i行約束方程的基變量正好是xi，而經(jīng)過迭代后，基將發(fā)生變化，計算zj的式子也會發(fā)生變化。如果迭代后的第i行約束方程中的基變量為xBi，與xBi相應的目標函數(shù)系數(shù)為cBi，系數(shù)列向量為 則 其中，(cB)是由第1列第m行各約束方程中的基變量相應的目標函數(shù)依次組成的有序行向量。 單純形法的表格形式是把用單純形法求出基本可行解、檢驗其最優(yōu)性、迭代某步驟都用表格的方式來計算求出

37、，其表格的形式有些像增廣矩陣，而其計算的方法也大體上使用矩陣的行的初等變換。以下用單純形表格來求解下例。 max 50 x1+100 x2+0s1+0s2+0s3. x1+x2+s1=300， 2x1+x2+s2=400， x2+s3=250， x1, x2, s1, s2, s30. 把上面的數(shù)據(jù)填入如下的單純形表格第一百一十五張，PPT共二百九十頁，創(chuàng)作于2022年6月單純形法的表格形式按照線性規(guī)劃模型在表中填入相對應的值，如上表所示；在上表中有一個m*m的單位矩陣，對應的基變量為s1,s2,s3；在zj行中填入第j列與cB列中對應的元素相乘相加所得的值，如z2=0*1+0*1+0*1=0

38、，所在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ū)別。第一百一十六張，PPT共二百九十頁，創(chuàng)作于2022年6月單純形法的表格形式以下進行第一次迭代，其變量為x2,s1,s2,通過矩陣行的初等變換，求出一個新的基本可行解，具體的做法用行的初等變換使得x2的系數(shù)向量p2變換成單位向

39、量，由于主元在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.第一百一十七張，PPT共二百九十頁，創(chuàng)作于2022年6月單純形法的表格形式從上表可以看出，第一次迭代的 ，因此不是最優(yōu)解。設x1為入基變量，從此值可知b1/a11

40、=50為最小正數(shù)，因此，s1為出基變量，a11為主元，繼續(xù)迭代如下表所示。從上表中可知第二次迭代得到的基本可行解為x1=50,x2=250,s1=0,s2=50, s3=0,這時z=27500。由于檢驗數(shù)都0= l x(l)主元素： alk 新單純表：pk=單位向量注：當所有檢驗數(shù)j 0時，若存在非基變量檢驗數(shù)為0時，則有無窮多解，否則只有唯一最優(yōu)解。i=1m第一百二十四張，PPT共二百九十頁，創(chuàng)作于2022年6月單純形法的計算步驟例 用單純形法求解解：將數(shù)學模型化為標準形式：不難看出x4、x5可作為初始基變量，列單純形表計算。第一百二十五張，PPT共二百九十頁，創(chuàng)作于2022年6月單純形法的

41、計算步驟20 x221/3150120753017131/309022560 x111017/31/31250128/9-1/92/335/300-98/9-1/9-7/3第一百二十六張，PPT共二百九十頁，創(chuàng)作于2022年6月 2 1 0 0 0 0 15 0 5 1 0 0 0 24 6 2 0 1 0 0 5 1 1 0 0 1 2 1 0 0 0 練習:一般主列選擇正檢驗數(shù)中最大者對應的列,也可選擇其它正檢驗數(shù)的列.以第2列為主列,用單純形法求解。正檢驗數(shù)對應的列為主列第一百二十七張，PPT共二百九十頁，創(chuàng)作于2022年6月結束2.4 單純形法的計算步驟第一百二十八張，PPT共二百九十

42、頁，創(chuàng)作于2022年6月2.5.1 單純形法的進一步討論一、大M法二、兩階段法-人工變量法第一百二十九張，PPT共二百九十頁，創(chuàng)作于2022年6月人工變量法問題：線性規(guī)劃問題化為標準形時，若約束條件的系數(shù)矩陣中不存在單位矩陣，如何構造初始可行基？ 第一百三十張，PPT共二百九十頁，創(chuàng)作于2022年6月人工變量法加入人工變量設線性規(guī)劃問題的標準型為：第一百三十一張，PPT共二百九十頁，創(chuàng)作于2022年6月 加入人工變量,構造初始可行基. 人工變量法系數(shù)矩陣為單位矩陣，可構成初始可行基。第一百三十二張，PPT共二百九十頁，創(chuàng)作于2022年6月 約束條件已改變，目標函數(shù)如何調整？人工變量法第一百三十

43、三張，PPT共二百九十頁，創(chuàng)作于2022年6月“懲罰” 人工變量?。?）大M法（2）兩階段法第一百三十四張，PPT共二百九十頁，創(chuàng)作于2022年6月一、大 M 法人工變量在目標函數(shù)中的系數(shù)為 -M, 其中，M 為任意大的正數(shù)。目標函數(shù)中添加“罰因子”-M（M是任意大的正數(shù)）為人工變量系數(shù)，只要人工變量0，則目標函數(shù)不可能實現(xiàn)最優(yōu)。第一百三十五張，PPT共二百九十頁，創(chuàng)作于2022年6月例: 求解線性規(guī)劃問題一、大 M 法第一百三十六張，PPT共二百九十頁，創(chuàng)作于2022年6月 一、大 M 法解:加入松弛變量和剩余變量進行標準 化, 加入人工變量構造初始可行基. 第一百三十七張，PPT共二百九十

44、頁，創(chuàng)作于2022年6月求解結果出現(xiàn)檢驗數(shù)非正若基變量中含非零的人工變量， 則無可行解； 否則，有最優(yōu)解。一、大 M 法用單純形法求解（見下頁）。目標函數(shù)中添加“罰因子”-M為人工變量系數(shù)，只要人工變量0，則目標函數(shù)不可能實現(xiàn)最優(yōu)。第一百三十八張，PPT共二百九十頁，創(chuàng)作于2022年6月 1 -2 1 -4 1 2 -2 0 1 3-6M M -1 3M-1 3 -1 -1 x1 x2 x3 0 x4 11 -M x6 3 -M x7 1C j - Z j C j CB XB b 1 0 0 -1 0 0 0 -M 0 0 x4 x5 11 3/2 1 0 0 1 0 0 1 0 0 - M

45、- M x6 x7 表1（初始單純形表）一、大 M 法（單純形法求解）第一百三十九張，PPT共二百九十頁，創(chuàng)作于2022年6月 3 -2 0 0 1 0 -2 0 1 1 M-1 0 3 -1 -1x1 x2 x3 0 x4 10 -M x6 1 -1 x3 1C j - Z j C j CB XB b 1 0 0 -1 0 0 0 -M 0 0 x4 x5 1 0 -1 1 -2 0 1 0 1-3M - M - M x6 x7 一、大 M 法（單純形法求解）表2第一百四十張，PPT共二百九十頁，創(chuàng)作于2022年6月 3 0 0 0 1 0 -2 0 1 1 0 0 3 -1 -1 x1 x

46、2 x3 0 x4 12 -1 x2 1 -1 x3 1C j - Z j C j CB XB b 1 -2 0 -1 0 0 0 -1 0 0 x4 x5 4 i 2 -5 1 -2 0 1 1-M -1 -M - M - M x6 x7 表3一、大 M 法（單純形法求解）第一百四十一張，PPT共二百九十頁，創(chuàng)作于2022年6月 1 0 0 0 1 0 0 0 1 0 0 0 3 -1 -1 x1 x2 x3 3 x1 4 -1 x2 1 -1 x3 9 2 C j CB XB b1/3 -2/3 0 -1 2/3 -4/3 -1/3 -1/3 0 0 x4 x5 2/3 -5/3 1 -2

47、 4/3 -7/3 1/3-M 2/3-M - M - M x6 x7 表4一、大 M 法（單純形法求解）最優(yōu)解為目標函數(shù)值 z=2檢驗數(shù)均非正，此為最終單純形表第一百四十二張，PPT共二百九十頁，創(chuàng)作于2022年6月在實際問題中有些模型并不含有單位矩陣，為了得到一組基向量和初基可行解，在約束條件的等式左端加一組虛擬變量，得到一組基變量。這種人為加的變量稱為人工變量，構成的可行基稱為人工基，用大M法或兩階段法求解，這種用人工變量作橋梁的求解方法稱為人工變量法?！纠?-20】用大M法解 下列線性規(guī)劃1. 大M 單純形法1.5.2大M和兩階段單純形法1.5 單純形法 Simplex Method第

48、一百四十三張，PPT共二百九十頁，創(chuàng)作于2022年6月【解】首先將數(shù)學模型化為標準形式式中x4，x5為松弛變量，x5可作為一個基變量，第一、三約束中分別加入人工變量x6、x7，目標函數(shù)中加入Mx6Mx7一項，得到人工變量單純形法數(shù)學模型用前面介紹的單純形法求解，見下表。 1.5 單純形法 Simplex Method第一百四十四張，PPT共二百九十頁，創(chuàng)作于2022年6月Cj32100MMbCBXBx1x2x3x4x5x6x7M0Mx6x5x74123121211000101000014101j3-2M2+M-1+2MM000M01x6x5x3632532001100010100381j5-6

49、M5M0M00201x2x5x36/53/52/51000011/53/52/50103/531/511/5j50000231x2x1x301010000111025/32/31331/319/3j0005-25/3第一百四十五張，PPT共二百九十頁，創(chuàng)作于2022年6月（2）初始表中的檢驗數(shù)有兩種算法，第一種算法是利用第一、三約束將x6、x7的表達式代入目標涵數(shù)消去x6和x7，得到用非基變量表達的目標函數(shù)，其系數(shù)就是檢驗數(shù)；第二種算法是利用公式計算，如最優(yōu)解X（31/3，13，19/3，0，0)T；最優(yōu)值Z152/3注意：1.5 單純形法 Simplex Method(1) M是一個很大的抽

50、象的數(shù)，不需要給出具體的數(shù)值，可以理解為它能大于給定的任何一個確定數(shù)值第一百四十六張，PPT共二百九十頁，創(chuàng)作于2022年6月【例1-21】求解線性規(guī)劃 【解】加入松馳變量x3、x4化為標準型在第二個方程中加入人工變量x5，目標函數(shù)中加上M x5一項，得到 1.5 單純形法 Simplex Method第一百四十七張，PPT共二百九十頁，創(chuàng)作于2022年6月用單純形法計算如下表所示。 Cj5800MbCBXBx1x2x3x4x50Mx3x5311210010164j5M8+2M0M05Mx1x5101/37/31/31/3010122j029/3+7/3M5/3+1/3MM01.5 單純形法

51、Simplex Method第一百四十八張，PPT共二百九十頁，創(chuàng)作于2022年6月表中j0，j=1，2，5，從而得到最優(yōu)解X=（2，0，0，0，2）， Z=10+2M。但最優(yōu)解中含有人工變量x50說明這個解是偽最優(yōu)解，是不可行的，因此原問題無可行解。1.5 單純形法 Simplex Method第一百四十九張，PPT共二百九十頁，創(chuàng)作于2022年6月M在計算機上處理困難。分階段處理先求初始基，再求解。二、兩階段法第一百五十張，PPT共二百九十頁，創(chuàng)作于2022年6月二、兩階段法第一階段: 構造如下的線性規(guī)劃問題人工變量的系數(shù)矩陣為單位矩陣，可構成初始可行基。 目標函數(shù)僅含人工變量，并要求實現(xiàn)

52、最小化。 若其最優(yōu)解的目標函數(shù)值不為0，也即最優(yōu)解的基變量中含有非零的人工變量，則原線性規(guī)劃問題無可行解。第一百五十一張，PPT共二百九十頁，創(chuàng)作于2022年6月 用單純形法求解上述問題,若=0,進入第二階段,否則,原問題無可行解。第二階段：去掉人工變量，還原目標函數(shù)系數(shù)，做出初始單純形表。 用單純形法求解即可。二、兩階段法下面舉例說明，仍用大M法的例。第一百五十二張，PPT共二百九十頁，創(chuàng)作于2022年6月例：二、兩階段法第一百五十三張，PPT共二百九十頁，創(chuàng)作于2022年6月 二、兩階段法構造第一階段問題并求解解：用單純形法求解第一百五十四張，PPT共二百九十頁，創(chuàng)作于2022年6月二、兩

53、階段法（第一階段、求min ） 1 -2 1 -4 1 2 -2 0 1 -6 1 3 0 0 0 x1 x2 x3 0 x4 11 -1 x6 3 -1 x7 1 C i CB XB b 1 0 0 0 -1 1 0 0 0 0 -1 0 0 0 -1 - 1 x4 x5 x6 0 11 0 3/2 1 1 0 - 1 x7 i 表1第一百五十五張，PPT共二百九十頁，創(chuàng)作于2022年6月 -1 - -2 1 1 - -3 - 1 x7 3 -2 0 0 1 0 -2 0 1 0 1 0 0 0 0 x1 x2 x3 0 x4 10 -1 x6 1 0 x3 1 C i CB XB b 1

54、0 0 0 -1 1 0 0 0 0 -1 0 0 0 -1 x4 x5 x6二、兩階段法（第一階段、求min ）表2第一百五十六張，PPT共二百九十頁，創(chuàng)作于2022年6月 -5 4 -2 - 1 - -1 - 1 x7 3 0 0 0 1 0 -2 0 1 0 0 0 0 0 0 x1 x2 x3 0 x4 12 0 x2 1 0 x3 1 C i CB XB b 1 -2 2 0 -1 1 0 0 0 0 0 -1 0 0 -1 x4 x5 x6二、兩階段法（第一階段、求min ）表3：最終單純形表第二階段不含人工變量且=0第一百五十七張，PPT共二百九十頁，創(chuàng)作于2022年6月二、兩階

55、段法第二階段 將去掉人工變量，還原目標函數(shù)系數(shù)，做出初始單純形表。 3 0 0 0 1 0 -2 0 1 3 -1 -1 x1 x2 x3 0 x4 12 -1 x2 1 -1 x3 1 C i CB XB b 1 -2 2 0 -1 1 0 0 0 0 0 x4 x5 1 0 0 0 -1第一百五十八張，PPT共二百九十頁，創(chuàng)作于2022年6月二、兩階段法 1 0 0 0 1 0 0 0 1 3 -1 -1 x1 x2 x3 3 x1 4 -1 x2 1 -1 x3 9 C i CB XB b 1/3 -2/3 0 -1 2/3 -4/3 0 0 x4 x5 第二階段 0 0 0 -1/3

56、-1/3最優(yōu)解為目標函數(shù)值 z=2第一百五十九張，PPT共二百九十頁，創(chuàng)作于2022年6月【例1-22】用兩階段單純形法求解例19的線性規(guī)劃?！窘狻繕藴市蜑樵诘谝弧⑷s束方程中加入人工變量x6、x7后，第一階段問題為用單純形法求解，得到第一階段問題的計算表如下：1.5 單純形法 Simplex Method第一百六十張，PPT共二百九十頁，創(chuàng)作于2022年6月Cj0000011 bCBXBx1x2x3x4x5x6x7101x6x5x74123121211000101000014101j2121000100 x6x5x3632532001100010100381j650100000 x2x5x3

57、6/53/52/51000011/53/52/50103/531/511/5j000001.5 單純形法 Simplex Method第一百六十一張，PPT共二百九十頁，創(chuàng)作于2022年6月最優(yōu)解為 最優(yōu)值w=0。第一階段最后一張最優(yōu)表說明找到了原問題的一組基可行解，將它作為初始基可行解，求原問題的最優(yōu)解，即第二階段問題為1.5 單純形法 Simplex Method第一百六十二張，PPT共二百九十頁，創(chuàng)作于2022年6月Cj32-100bCBXBx1x2x3x4x5201x2x5x3100001010j50000231x2x1x3010100001110213j0005Cj32100bCBX

58、Bx1x2x3x4x5201x2x5x36/53/52/51000011/53/52/50103/531/5 11/5j5 0000231x2x1x301010000111025/32/31331/319/3j000525/3用單純形法計算得到下表最優(yōu)解X（31/3，13，19/3，0，0)T；最優(yōu)值Z152/31.5 單純形法 Simplex Method第一百六十三張，PPT共二百九十頁，創(chuàng)作于2022年6月【例1-23】用兩階段法求解例1-21的線性規(guī)劃?！窘狻坷?-21的第一階段問題為用單純形法計算如下表：1.5 單純形法 Simplex Method第一百六十四張，PPT共二百九十頁

59、，創(chuàng)作于2022年6月Cj00001bCBXBx1x2x3x4x501x3x5311210010164j1201001x1x5101/37/31/31/3010122j07/31/310j0,得到第一階段的最優(yōu)解X=(2,0,0,0,2)T,最優(yōu)目標值w=20,x5仍在基變量中,從而原問題無可行解。1.5 單純形法 Simplex Method第一百六十五張，PPT共二百九十頁，創(chuàng)作于2022年6月解的判斷唯一最優(yōu)解的判斷：最優(yōu)表中所有非基變量的檢驗數(shù)非零,則線 規(guī)劃具有唯一最優(yōu)解 多重最優(yōu)解的判斷:最優(yōu)表中存在非基變量的檢驗數(shù)為零,則線則性規(guī)劃具有多重最優(yōu)解。 無界解的判斷: 某個k0且ai

60、k（i=1，2,m）則線性規(guī)劃具有無界解退化基本可行解的判斷:存在某個基變量為零的基本可行解。無可行解的判斷：(1)當用大M單純形法計算得到最優(yōu)解并且存在Ri0時，則表明原線性規(guī)劃無可行解。(2) 當?shù)谝浑A段的最優(yōu)值w0時，則原問題無可行解。1.5 單純形法 Simplex Method第一百六十六張，PPT共二百九十頁，創(chuàng)作于2022年6月單純形法計算中的幾個問題1、目標函數(shù)極小化時解的最優(yōu)性判斷 只需用檢驗數(shù) 作為最優(yōu)性的標志。2、無可行解的判斷 當求解結果出現(xiàn)所有 時，如基變量仍 含有非零的人工變量（兩階段法求解時第一階 段目標函數(shù)值不等于0），則問題無可行解。第一百六十七張，PPT共二