線性規(guī)劃和單純形法

1、關于線性規(guī)劃與單純形法第一張，PPT共一百零一頁，創(chuàng)作于2022年6月第二章 線性規(guī)劃與單純形法第1節(jié) 線性規(guī)劃問題及其數學模型第2節(jié) 圖解法第3節(jié) 解第4節(jié) 單純形法原理及其計算步驟第5節(jié) 人工變量法第6節(jié) 小結第二張，PPT共一百零一頁，創(chuàng)作于2022年6月第1節(jié) 線性規(guī)劃問題及其數學模型一、規(guī)劃如何合理地利用有限的人力、物力、財力等資源，以便得到最好的經濟效果。第三張，PPT共一百零一頁，創(chuàng)作于2022年6月第1節(jié) 線性規(guī)劃問題及其數學模型例1：用一塊邊長為a的正方形鐵皮做一個容器，應該如何裁剪，使做成的容器的容積最大（如下圖所示）。ax第四張，PPT共一百零一頁，創(chuàng)作于2022年6月第

2、1節(jié) 線性規(guī)劃問題及其數學模型例1：解：設在鐵皮四個角上剪去四個邊長各為x的正方形 V=(a-2x)(a-2x)xmax 滿足 xa/2 x0第五張，PPT共一百零一頁，創(chuàng)作于2022年6月第1節(jié) 線性規(guī)劃問題及其數學模型例2：某企業(yè)計劃生產、兩種產品，都要分別在A，B，C，D四種不同設備上加工。按工藝資料規(guī)定，生產每件產品需占用各設備分別為2，1，4，0（小時），生產每件產品需占用各設備分別為2，2，0，4（小時）。已知各設備計劃期內用于生產這兩種產品的能力分別為12，8，16，12（小時），又知每生產一件產品，企業(yè)能獲利2元，每生產一件產品 ，企業(yè)能獲利3元。問：該企業(yè)應如何安排生產兩種產

3、品各多少件，使企業(yè)的利潤收入最大。第六張，PPT共一百零一頁，創(chuàng)作于2022年6月第1節(jié) 線性規(guī)劃問題及其數學模型例2：解：設、兩種產品在計劃期內的產量分別為x1、x2 z =2x1+3x2max 2x1+2x212 x1+2x28 滿足 4x116 4x212 x1，x20表示形式第七張，PPT共一百零一頁，創(chuàng)作于2022年6月第1節(jié) 線性規(guī)劃問題及其數學模型二、數學規(guī)劃研究在一些給定的條件下，求所考察函數在某種意義下的極值問題。第八張，PPT共一百零一頁，創(chuàng)作于2022年6月第1節(jié) 線性規(guī)劃問題及其數學模型特征（1）決策變量（2）約束條件（3）目標函數第九張，PPT共一百零一頁，創(chuàng)作于20

4、22年6月第1節(jié) 線性規(guī)劃問題及其數學模型三、線性規(guī)劃問題特征（三要素）（1）決策變量：問題中的未知量（2）目標函數：問題要達到的目標（最大或最?。硎緸闆Q策變量的線性函數（3）約束條件：表示為含決策變量的一組互不矛盾的線性等式或線性不等式的函數約束和決策變量的非負約束第十張，PPT共一百零一頁，創(chuàng)作于2022年6月第1節(jié) 線性規(guī)劃問題及其數學模型V=(a-2x)(a-2x)xmax xa/2 x0z =2x1+3x2max 2x1+2x212 x1+2x28 4x116 4x212 x1，x20第十一張，PPT共一百零一頁，創(chuàng)作于2022年6月第1節(jié) 線性規(guī)劃問題及其數學模型線性規(guī)劃問題數

5、學模型的形式（1）一般形式第十二張，PPT共一百零一頁，創(chuàng)作于2022年6月第1節(jié) 線性規(guī)劃問題及其數學模型（2）簡寫形式（3）向量形式 （4）矩陣形式第十三張，PPT共一百零一頁，創(chuàng)作于2022年6月第1節(jié) 線性規(guī)劃問題及其數學模型例3：寫出例2數學模型的一般形式和矩陣形式。一般形式 矩陣形式 max z =2x1+3x2 2x1+2x212 x1+2x28 4x116 4x212 x1，x20解第十四張，PPT共一百零一頁，創(chuàng)作于2022年6月第1節(jié) 線性規(guī)劃問題及其數學模型四、線性規(guī)劃數學模型的標準形式（標準型）目標函數求最大值函數約束條件全為等式決策變量全為非負函數約束條件右端項全為非

6、負第十五張，PPT共一百零一頁，創(chuàng)作于2022年6月第1節(jié) 線性規(guī)劃問題及其數學模型五、線性規(guī)劃的非標準型如何轉化為標準型目標函數求最小值：令z-z函數約束條件為不等式： ：在函數約束條件左端加非負的松弛變量 ：在函數約束條件左端減非負的松弛變量 松弛變量在目標函數中的系數全為0決策變量為負值：令xj-xj， xj0決策變量取值無約束： 令xj xj- xj，xj0， xj0函數約束條件右端項（bi）為負值：函數約束條件兩端同乘-1第十六張，PPT共一百零一頁，創(chuàng)作于2022年6月第1節(jié) 線性規(guī)劃問題及其數學模型要求：將下列線性規(guī)劃問題轉化為標準型。例4：min z =x1+2x2+3x3 -

7、2x1+x2+x39 -3x1+x2+2x34 3x1-2x2-3x3=-6 x10，x20，x3取值無約束第十七張，PPT共一百零一頁，創(chuàng)作于2022年6月第1節(jié) 線性規(guī)劃問題及其數學模型例4：解：令 max z=x1-2x2-3x3+3x3+0 x4+0 x5 2x1+x2+x3-x3+x4=9 3x1+x2+2x3-2x3-x5=4 3x1+2x2+3x3-3x3=6 x1，x2，x3，x3，x4，x50第十八張，PPT共一百零一頁，創(chuàng)作于2022年6月第1節(jié) 線性規(guī)劃問題及其數學模型例5： min z =-x1+2x2-3x3 x1+x2+x37 x1-x2+x32 -3x1+x2+2

8、x3=5 x1，x20，x3無約束第十九張，PPT共一百零一頁，創(chuàng)作于2022年6月第1節(jié) 線性規(guī)劃問題及其數學模型例5：解：令 max z=x1-2x2-3x3+3x3 x1+x2+x3-x3+x4=7 x1-x2+x3-x3-x5=2 -3x1+x2+2x3-2x3=5 x1，x2，x3，x3，x4，x50第二十張，PPT共一百零一頁，創(chuàng)作于2022年6月第1節(jié) 線性規(guī)劃問題及其數學模型例6： max z =2x1+3x2+5x3 x1+x2-x3-5 -6x1+7x2-9x3=16 19x1-7x25x313 x1，x20，x3無約束第二十一張，PPT共一百零一頁，創(chuàng)作于2022年6月第

9、1節(jié) 線性規(guī)劃問題及其數學模型例6：解：令 max z=2x1+3x2+5x3-5x3 -x1-x2+x3-x3+x4=5 -6x1+7x2-9x3+9x3=16 19x1-7x2+5x3-5x3+x5=13 -19x1+7x2-5x3+5x3+x6=13 x1，x2，x3，x3，x4，x5 ，x60第二十二張，PPT共一百零一頁，創(chuàng)作于2022年6月作業(yè)2-1作業(yè)2-1：將下列線性規(guī)劃問題化為標準型。1、min z =5x1-2x2+4x3-3x4 -x1+2x2-x3+4x4=-2 -x1+3x2+x3+x414 2x1-x2+3x3-x42 x1無約束，x20，x3，x402、 min

10、z =x1+2x2+4x3 2x1+x2+3x320 3x1+x2+4x325 x1，x20，x30第二十三張，PPT共一百零一頁，創(chuàng)作于2022年6月第2節(jié) 解線性規(guī)劃問題數學模型的標準型（以一般形式表示）第二十四張，PPT共一百零一頁，創(chuàng)作于2022年6月第2節(jié) 解一、線性規(guī)劃問題解的概念可行解：滿足函數約束條件和非負約束條件的解，全部可行解的集合稱為可行域最優(yōu)解：使目標函數達到最大值的可行解，對應的目標函數值稱為最優(yōu)值第二十五張，PPT共一百零一頁，創(chuàng)作于2022年6月第2節(jié) 解基：設A是約束方程組的mn階系數矩陣，B是矩陣A中mm階非奇異子矩陣，稱B是線性規(guī)劃問題的一個基基向量：基B中

11、每一個列向量Pj非基向量：A中其余列向量Pj（不在B中）基變量：與基向量Pj對應的決策變量xj非基變量：與非基向量對應的決策變量基解基可行解：滿足非負約束條件的基解可行基：對應于基可行解的基克萊姆法則非奇異矩陣解的關系第二十六張，PPT共一百零一頁，創(chuàng)作于2022年6月第2節(jié) 解非奇異矩陣：行列式不等于0的矩陣。克萊姆法則：如果線性方程組 a11x1+a12x2+a1mxm=b1 a21x1+a22x2+a2mxm=b2 am1x1+am2x2+ammxm=bm 的系數行列式不等于0，則方程組有唯一解。第二十七張，PPT共一百零一頁，創(chuàng)作于2022年6月第2節(jié) 解二、線性規(guī)劃問題解的關系最優(yōu)解

12、第二十八張，PPT共一百零一頁，創(chuàng)作于2022年6月第2節(jié) 解例7：寫出例2的標準型，并指出基、基變量、基解、基可行解和可行基。第二十九張，PPT共一百零一頁，創(chuàng)作于2022年6月第2節(jié) 解例7：標準型max z =2x1+3x2 2x1+2x212 x1+2x28 4x116 4x212 x1，x20 max z =2x1+3x2 2x1+2x2+x3=12 x1+2x2+x4=8 4x1+x5=16 4x2+x6=12 x1-60圖解法第三十張，PPT共一百零一頁，創(chuàng)作于2022年6月第2節(jié) 解例8：求下述線性規(guī)劃的所有基解、基可行解及最優(yōu)解。 max z =3x1+x2+3x3 x1+x

13、2+x32 x1+2x2+4x36 x1，x2，x30第三十一張，PPT共一百零一頁，創(chuàng)作于2022年6月作業(yè)2-2作業(yè)2-2：求下列線性規(guī)劃的所有基解、基可行解及最優(yōu)解。1、 max z =2x1+3x2+4x3+7x4 2x1+3x2-x3-4x48 -x1+2x2-6x3+7x43 x1，x2，x3，x402、 max z =-5x1+2x2-3x3+6x4 x1+2x2+3x3+4x47 2x1+x2+x3+2x43 x1，x2，x3，x40第三十二張，PPT共一百零一頁，創(chuàng)作于2022年6月第3節(jié) 圖解法一、圖解法適用條件：適用于求解只有兩個決策變量的線性規(guī)劃問題特點（1）不必將線性

14、規(guī)劃問題轉化為標準型（2）直觀性強，計算方便第三十三張，PPT共一百零一頁，創(chuàng)作于2022年6月第3節(jié) 圖解法例9：用圖解法求解下述線性規(guī)劃問題。 max z =2x1+3x2 x1+2x28 4x116 4x212 x1，x20第三十四張，PPT共一百零一頁，創(chuàng)作于2022年6月第3節(jié) 圖解法例9：標出約束條件(0,0)(0,3)(2,3)(4,2)(4,0)第三十五張，PPT共一百零一頁，創(chuàng)作于2022年6月第3節(jié) 圖解法例9：標出目標函數目標函數z唯一最優(yōu)解第三十六張，PPT共一百零一頁，創(chuàng)作于2022年6月第3節(jié) 圖解法二、圖解法的求解步驟建立 二維坐標系將約束條件表示在坐標系中，以確

15、立可行域畫出每個函數約束的約束邊界，用原點判斷直線的哪一邊是約束條件所允許的找出所有約束條件都同時滿足的區(qū)域，即可行域將目標函數繪制在坐標系中，并標出變化的方向給定目標函數一個特定的值k，畫出目標函數特定線，當k變化時，目標函數特定線將平行移動對于目標函數最大（?。┗膯栴}，找出目標函數增加（減少）的方向，目標函數最后離開可行域的點是最優(yōu)解確定最優(yōu)解第三十七張，PPT共一百零一頁，創(chuàng)作于2022年6月第3節(jié) 圖解法三、圖解法解的類型唯一最優(yōu)解：僅有一點使目標函數值取得最大（?。┲禑o窮多（多重）最優(yōu)解：線段（射線）上任意一點都使目標函數值取得相同的最大（?。┲禑o界解：可行域無界，目標函數值可以增

16、大到無窮大無可行解：可行域為空集無界解和無可行解統(tǒng)稱為無最優(yōu)解第三十八張，PPT共一百零一頁，創(chuàng)作于2022年6月第3節(jié) 圖解法要求：用圖解法求解下列線性規(guī)劃問題。例10： max z =2x1+4x2 x1+2x28 4x116 4x212 x1，x20第三十九張，PPT共一百零一頁，創(chuàng)作于2022年6月第3節(jié) 圖解法例10：目標函數 max z=2x1+4x2 z多重最優(yōu)解第四十張，PPT共一百零一頁，創(chuàng)作于2022年6月第3節(jié) 圖解法例11： max z =2x1+3x2 4x116 x1，x20無界解第四十一張，PPT共一百零一頁，創(chuàng)作于2022年6月第3節(jié) 圖解法例12： max z

17、 =2x1+3x2 2x1+2x212 x1+2x214 x1，x20無可行解第四十二張，PPT共一百零一頁，創(chuàng)作于2022年6月第3節(jié) 圖解法四、圖解法解的特點當可行域非空集時，可行域必是有界或無界凸多邊形。（凸集：集合C中任意兩個點a和b，其連線上所有點也必為集合C中的點。）若可行域有界，則目標函數一定可以在可行域的頂點上達到最優(yōu)；若可行域無界，則可能無最優(yōu)解，也可能有最優(yōu)解，若有也必定在某頂點上達到。第四十三張，PPT共一百零一頁，創(chuàng)作于2022年6月第3節(jié) 圖解法線性規(guī)劃問題的每個基可行解對應可行域的一個頂點。線性規(guī)劃問題的最優(yōu)解在頂點上達到，則一定存在一個基可行解是最優(yōu)解。若有唯一最

18、優(yōu)解，則一定在可行域的某個頂點處得到；若有兩個頂點同時達到最優(yōu)解，則兩個頂點之間線段上的任意一點都是最優(yōu)解，既有無窮多最優(yōu)解。線性規(guī)劃問題有最優(yōu)解，則解題思路：找出可行域的頂點，計算頂點處的目標函數值，比較各頂點的目標函數值，值最大（?。┑捻旤c為最優(yōu)解的點或最優(yōu)解的點之一。第四十四張，PPT共一百零一頁，創(chuàng)作于2022年6月第3節(jié) 圖解法例13：下列哪一個圖是凸集？A BC D凸多邊形第四十五張，PPT共一百零一頁，創(chuàng)作于2022年6月第3節(jié) 圖解法例9圖解：目標函數z第四十六張，PPT共一百零一頁，創(chuàng)作于2022年6月第3節(jié) 圖解法例10圖解：目標函數 max z=2x1+4x2 z頂點最優(yōu)

19、第四十七張，PPT共一百零一頁，創(chuàng)作于2022年6月第3節(jié) 圖解法要求：用圖解法求解下列線性規(guī)劃問題。例14： min z =2x1-x2 -2x1+x22 x1-2x21 x1，x20無界可行域第四十八張，PPT共一百零一頁，創(chuàng)作于2022年6月第3節(jié) 圖解法例15：1、 max z =x1+x2 -2x1+x24 x1-x22 x1，x20 2、 max z =x1+2x2 x1+2x28 4x116 4x212 x1，x20第四十九張，PPT共一百零一頁，創(chuàng)作于2022年6月第3節(jié) 圖解法例15：2、(0,0)(0,3)(2,3)(4,2)(4,0)第五十張，PPT共一百零一頁，創(chuàng)作于2

20、022年6月作業(yè)2-3作業(yè)2-3：用圖解法求解下列線性規(guī)劃問題。1、 max z =50 x1+100 x2 x1+x2300 2x1+x2400 x2250 x1，x202、 max z =4x1+8x2 2x1+2x210 -x1+x2 8 x1，x203、max z =3x1+9x2 x1+3x222 -x1+x24 x26 2x1-5x20 x1，x204、max z =2x1+2x2 x1-x2 -1 -0.5x1+x2 2 x1，x20第五十一張，PPT共一百零一頁，創(chuàng)作于2022年6月第4節(jié) 單純形法原理及其計算步驟例16：求解下述線性規(guī)劃問題。 max z =2x1+3x2 x

21、1+2x28 4x116 4x212 x1，x20第五十二張，PPT共一百零一頁，創(chuàng)作于2022年6月第4節(jié) 單純形法原理及其計算步驟例16：解：方法一：圖解法z*=2x1+3x2=14(0,3)(2,3)(4,0)(0,0)Q4Q3Q1X*第五十三張，PPT共一百零一頁，創(chuàng)作于2022年6月第4節(jié) 單純形法原理及其計算步驟例16：解：方法二：確定所有基解、基可行解及最優(yōu)解轉化為標準型 max z =2x1+3x2 x1+2x2+x3=8 4x1+x4=16 4x2+x5=12 x1-50第五十四張，PPT共一百零一頁，創(chuàng)作于2022年6月第4節(jié) 單純形法原理及其計算步驟例16：解：方法三：確

22、定部分基可行解及最優(yōu)解轉化為標準型 max z =2x1+3x2 x1+2x2+x3=8 4x1+x4=16 4x2+x5=12 x1-50第五十五張，PPT共一百零一頁，創(chuàng)作于2022年6月第4節(jié) 單純形法原理及其計算步驟一、單純形法的解題思路從某一基可行解開始，轉化到另一個相鄰的基可行解，并且使相應的目標函數值有改進。即從可行域的一個頂點沿約束邊界轉換到可行域的另一個相鄰的且使目標函數值有改進的頂點，直到目標函數值到達最優(yōu)時的頂點為止。第五十六張，PPT共一百零一頁，創(chuàng)作于2022年6月第4節(jié) 單純形法原理及其計算步驟兩個基可行解相鄰：在基變量集合中，除了一個基變量以外，其他基變量全是相同

23、的，只是數值可能不相同而已。第五十七張，PPT共一百零一頁，創(chuàng)作于2022年6月第4節(jié) 單純形法原理及其計算步驟二、單純形法的含義單純形法是一種迭代算法，首先找到一個初始基可行解，然后判斷它是否為最優(yōu)解，如果是就停止迭代，否則，按照一定的法則，再找到一個更好且與當前基可行解相鄰的基可行解，再進行判斷，直到找不到更好的基可行解或判斷問題無解為止。第五十八張，PPT共一百零一頁，創(chuàng)作于2022年6月第4節(jié) 單純形法原理及其計算步驟三、單純形法的解題步驟1、找出初始可行基，確定初始基可行解，建立初始單純形表。第五十九張，PPT共一百零一頁，創(chuàng)作于2022年6月第4節(jié) 單純形法原理及其計算步驟例：線性

24、規(guī)劃問題數學模型的某種標準形式第六十張，PPT共一百零一頁，創(chuàng)作于2022年6月第4節(jié) 單純形法原理及其計算步驟初始單純形表c1cmcm+1cncBxBbx1xmxm+1xnc1x1b110a1,m+1 a1,nc2x2b200a2,m+1a2,ncmxmbm01am,m+1am,n00第六十一張，PPT共一百零一頁，創(chuàng)作于2022年6月第4節(jié) 單純形法原理及其計算步驟2、檢驗各非基變量xj（j=m+1，m+2，n）的檢驗數j，若j0，則已得最優(yōu)解，停止計算，否則轉入3。3、在j0 （j=m+1，m+2，n）中，若有某個k對應的xk的系數列向量Pk0，則此線性規(guī)劃問題存在無界解，停止計算，否則

25、轉入4。4、根據 ，確定xk為換入變量，通過 ，計算確定xl為換出變量，轉入5。第六十二張，PPT共一百零一頁，創(chuàng)作于2022年6月第4節(jié) 單純形法原理及其計算步驟5、以alk為主元素進行迭代（高斯消去法），把xk所對應的列向量 將xB列中xl的換為xk，得到新的單純形表，重復25，直至終止。變換為單純形法求解例16第六十三張，PPT共一百零一頁，創(chuàng)作于2022年6月第4節(jié) 單純形法原理及其計算步驟高斯消去法的基本代數運算：一行乘以一個數一行乘上一個數加到另外一行中去第六十四張，PPT共一百零一頁，創(chuàng)作于2022年6月第4節(jié) 單純形法原理及其計算步驟例16：解：方法四：單純形法轉化為標準型 m

26、ax z =2x1+3x2 x1+2x2+x3=8 4x1+x4=16 4x2+x5=12 x1-50第六十五張，PPT共一百零一頁，創(chuàng)作于2022年6月第4節(jié) 單純形法原理及其計算步驟例17：用單純形法求解下述線性規(guī)劃問題。 max z =2x1+x2 5x215 6x1+2x224 x1+x25 x1，x20第六十六張，PPT共一百零一頁，創(chuàng)作于2022年6月第4節(jié) 單純形法原理及其計算步驟例17：解：轉化為標準型 max z =2x1+x2 5x2+x3=15 6x1+2x2+x4=24 x1+x2+x5=5 x1，x2，x3，x4，x50第六十七張，PPT共一百零一頁，創(chuàng)作于2022年

27、6月作業(yè)2-4作業(yè)2-4：用單純形法求解下列線性規(guī)劃問題。1、 max z =5x1+2x2+3x3-x4+x5 x1+2x2+2x3+x4=8 3x1+4x2+x3+x5=7 x1，x2，x3，x4，x502、 min z =-5x1-4x2 x1+2x26 2x1-x24 5x1+3x215 x1，x20第六十八張，PPT共一百零一頁，創(chuàng)作于2022年6月第5節(jié) 人工變量法例18：求解下述線性規(guī)劃問題。 max z =-3x1+x3 x1+x2+x34 -2x1+x2 -x31 3x2+x3=9 x1，x2，x30第六十九張，PPT共一百零一頁，創(chuàng)作于2022年6月第5節(jié) 人工變量法例18

28、：解：標準型第七十張，PPT共一百零一頁，創(chuàng)作于2022年6月第5節(jié) 人工變量法標準型人為構造單位矩陣第七十一張，PPT共一百零一頁，創(chuàng)作于2022年6月第5節(jié) 人工變量法例18：線性規(guī)劃問題的最后形式第七十二張，PPT共一百零一頁，創(chuàng)作于2022年6月第5節(jié) 人工變量法一、人工變量法的解題思路線性規(guī)劃問題中不存在現成的可行基，為了求一個初始可行基和初始基可行解，在每個約束方程中人為地加上一個變量（人工變量），使約束方程組的系數矩陣中產生初始基。第七十三張，PPT共一百零一頁，創(chuàng)作于2022年6月第5節(jié) 人工變量法二、人工變量法的含義為了確保引入人工變量以后新的線性規(guī)劃問題與原線性規(guī)劃問題求解

29、的一致性：在最優(yōu)解中人工變量取值必須為零；令人工變量的系數為-M（M0，表示充分大的數），“-M”稱為“罰因子”，表示只要人工變量取值大于零，目標函數就不可能達到最大值。第七十四張，PPT共一百零一頁，創(chuàng)作于2022年6月第5節(jié) 人工變量法三、人工變量法的解題步驟將原問題轉化為標準型對或的約束條件添加人工變量，直至構造出單位矩陣，且人工變量在目標函數中的系數為-M，建立初始單純形表按照單純形法的解題步驟25求解人工變量法求解例18第七十五張，PPT共一百零一頁，創(chuàng)作于2022年6月第5節(jié) 人工變量法例18：解：第七十六張，PPT共一百零一頁，創(chuàng)作于2022年6月第5節(jié) 人工變量法例19：用人工

30、變量法求解下述線性規(guī)劃問題。 max z =2x1+x2 x1+x22 2x1+2x26 x1，x20第七十七張，PPT共一百零一頁，創(chuàng)作于2022年6月第5節(jié) 人工變量法例19：解：標準型并添加人工變量 max z =2x1+x2-Mx5 x1+x2+x3=2 2x1+2x2-x4+x5=6 x1，x2 ，x3 ，x4，x50第七十八張，PPT共一百零一頁，創(chuàng)作于2022年6月第5節(jié) 人工變量法小結（1）將線性規(guī)劃化為標準型后，對或的約束條件添加人工變量（若約束條件系數矩陣A中已有k個單位列向量，只要引入m-k個人工變量，使它們與原來的k個單位列向量合成單位矩陣）（2）在最優(yōu)解中，若人工變量

31、大于0，則原問題無可行解第七十九張，PPT共一百零一頁，創(chuàng)作于2022年6月作業(yè)2-5作業(yè)2-5：用人工變量法求解下列線性規(guī)劃問題。1、 max z =3x1-x2-x3 x1-2x2+x311 -4x1+x2+2x33 2x1-x3=-1 x1，x2，x302、min z =-x1-3x2+x3 x1+x2+2x3+x4=4 -x1+x3-x5=4 x3-x6=3 x1，x2，x3，x4，x5，x60第八十張，PPT共一百零一頁，創(chuàng)作于2022年6月第6節(jié) 小結第八十一張，PPT共一百零一頁，創(chuàng)作于2022年6月第6節(jié) 小結二、單純形表中解的表示形式1、唯一最優(yōu)解：最終單純形表中，所有非基變

32、量檢驗數j02、無窮多最優(yōu)解：最終單純形表中，某非基變量檢驗數j03、無界解：某檢驗數j0對應變量的系數列向量Pk04、無可行解：線性規(guī)劃問題中添加人工變量后，最終單純形表中，基變量中含有非零的人工變量（0）第八十二張，PPT共一百零一頁，創(chuàng)作于2022年6月第6節(jié) 小結5、退化現象：用規(guī)則確定換出變量時，出現兩個以上相同的最小比值，使下一個單純形表中出現一個或多個基變量等于零。退化基可行解：一個或幾個基變量取值0的基可行解退化基可行解出現的原因：模型中存在多余的約束，使多個基可行解對應同一頂點第八十三張，PPT共一百零一頁，創(chuàng)作于2022年6月第6節(jié) 小結退化基可行解的處理規(guī)則：出現退化基可

33、行解，可能導致從某個基開始，經過若干次迭代后又回到原來的基，即單純形法出現了循環(huán)，永遠達不到最優(yōu)解，導致計算失敗。為避免出現死循環(huán)，法則如下：選擇換入變量時，若有幾個正的檢驗數具有相同的最大值，則選擇下標最小的對應的非基變量作為換入變量選擇換出變量時，若按規(guī)則計算，有幾個比值同時達到最小，則選擇下標最小的對應的基變量作為換出變量第八十四張，PPT共一百零一頁，創(chuàng)作于2022年6月第6節(jié) 小結例20：下列表格是求線性規(guī)劃問題的單純形表，試說明解的情況。1、最終表 2 3 0 0 0CBxBb x1 x2 x3 x4 x5203x1x5x2442 1 0 0 1/4 0 0 0 -2 1/2 1

34、0 1 1/2 -1/8 0 0 0 -3/2 -1/8 0第八十五張，PPT共一百零一頁，創(chuàng)作于2022年6月第6節(jié) 小結2、最終表 3 2 -1 0 0 0CBxBb x1 x2 x3 x4 x5 x6023x4x2x129/56/521/5 0 0 -1 1 -1/5 8/5 0 1 1 0 1/5 -3/5 1 0 0 0 1/5 2/5 0 0 -3 0 -1 0第八十六張，PPT共一百零一頁，創(chuàng)作于2022年6月第6節(jié) 小結3、中間表（最終表） 4 5 0 0 0CBxBb x1 x2 x3 x4 x5000 x3x4x5723 4 -1 1 0 0-1 -5 0 1 0 7 -3

35、 0 0 1 4 5 0 0 0第八十七張，PPT共一百零一頁，創(chuàng)作于2022年6月第6節(jié) 小結4、中間表（最終表） 4 3 0 0 0CBxBb x1 x2 x3 x4 x5000 x3x4x5723 4 -1 1 0 0-1 -5 0 1 0 7 -3 0 0 1 4 3 0 0 0第八十八張，PPT共一百零一頁，創(chuàng)作于2022年6月第6節(jié) 小結5、最初表 3 3 2 0 0CBxBb x1 x2 x3 x4 x500 x4x512 -1 3 -1 1 0 2 -1 1 0 1 3 3 2 0 0第八十九張，PPT共一百零一頁，創(chuàng)作于2022年6月第6節(jié) 小結6、中間表 2 3 0 0 0

36、 0CBxBb x1 x2 x3 x4 x5 x60203x3x1x5x22283 0 0 1 -2 0 1/2 1 0 0 1 0 -1/2 0 0 0 -4 1 2 0 1 0 0 0 1/4 0 0 0 -2 0 1/4第九十張，PPT共一百零一頁，創(chuàng)作于2022年6月第6節(jié) 小結三、單純形法對給定的線性規(guī)劃問題，首先化為標準型，選取或構造一個單位矩陣作為基矩陣，求出初始基可行解并列出初始單純形表。（若線性規(guī)劃問題的標準型為目標函數最小化，則最優(yōu)解判別規(guī)則為：所有檢驗數j0）第九十一張，PPT共一百零一頁，創(chuàng)作于2022年6月單純形法計算步驟框圖第九十二張，PPT共一百零一頁，創(chuàng)作于2022年6月第6節(jié) 小結例21：用單純形法求解下述線性規(guī)劃問題，并說明解的情況。 max z =2.5x1+x2 3x1+5x215 5x1+2x210 x1，x20第九十三張，PPT共一百零一頁，創(chuàng)作于2022年6月第6節(jié) 小結例21：解：max z =2.5x1+x2 3x1+5x2+x3=15 5x1+2x2+x4=10 x1，x2 ，x3，x40第九十四張，PPT共一百零一頁，創(chuàng)作于2022年6月作業(yè)2-6作業(yè)2-6：求解下列線性規(guī)劃問題，并說明解的情況。1、max z =6x1+4x2 -x1+2x24 3x1+2x214 2x1-x24 x1，x202、max z =2x1