運籌學A-第1章線性規(guī)劃

1、第1章 線性規(guī)劃 與單純形法,2020/9/15,2,第1 章 線性規(guī)劃,內容提要,第一節(jié) 線性規(guī)劃問題的數學模型 第二節(jié) 兩個變量LP問題的圖解法 第三節(jié) LP問題數學模型的標準型 第四節(jié) 線性規(guī)劃問題解的性質 第五節(jié) 單純形法原理及求解步驟,2020/9/15,3,第一節(jié) 線性規(guī)劃問題的數學模型,線性規(guī)劃(Linear Programming，LP)是運籌學的重要分支之一，在實際中應用得較廣泛，其方法也較成熟，借助計算機，使得計算更方便，應用領域更廣泛和深入。,線性規(guī)劃通常研究資源的最優(yōu)利用、設備最佳運行以及費用最低等問題。例如，當任務或目標確定后，如何統籌兼顧，合理安排，用最少的資源 （

2、如資金、設備、原標材料、人工、時間等）去完成確定的任務或目標；企業(yè)在一定的資源條件限制下，如何組織安排生產獲得最好的經濟效益（如產品量最多 、利潤最大）。,2020/9/15,4,一、問題的提出（線性規(guī)劃問題舉例）3.26,例1-1(生產計劃問題) 某廠在計劃期內安排、生產兩種產品，已知生產單位產品所需要的設備臺數、A和B兩種原材料的消耗量以及利潤如表1-1所示，問如何安排生產使利潤最大？（假設產品全部售出）,x1,x1,x1,x2,x2,x2,2020/9/15,5,(1)決策變量：設x1為甲產品的產量，x2為乙產品的產量。 (2)約束條件：生產受資源制約，不能突破有限供給量。 設備約束條件

3、的數學表達為： x1 + 2x2 8 原材料A約束條件數學表達為：4x1 16 原材料B約束條件數學表達為： 4x2 12 (3)目標函數：目標函數反映企業(yè)利潤最大化 max Z = 2x1 + 3x2 (4)非負約束：兩產品的產量為非負 x1 0， x2 0,LP模型：,s.t. (subject to) 使?jié)M足，使服從,例1-2 見教材第5頁,2020/9/15,6,例1-3. 某工地租賃甲、乙兩種機械安裝A、B、C三種構件，這兩種機械每天的安裝能力、租賃費用以及工程任務如下表所示，問如何租賃甲、乙兩機械才能使總的租賃費用最低？,2020/9/15,7,【解】設租賃機械甲x1天、機械乙x2

4、天，則該線性規(guī)劃問題的數學模型為：,例1-4 見教材第6頁，例【1.2】人員分配問題,2020/9/15,8,某一機床需要用甲、乙、丙三種規(guī)格的軸各一根，這些軸的規(guī)格分別是2.9、2.1和1.5m，這些軸需要用同一種圓鋼切割而成，圓鋼長度為7.4m?，F在要制造100臺機床，問：最少要用多少圓鋼來生產這些軸？(切割損失不計),解：1、設一根圓鋼切割成甲、乙、丙三種軸的根數分別為y1, y2, y3, 則切割方式可用不等式2.9y1+2.1y2+1.5y37.4表示，求這個不等式關于y1，y2，y3的非負整數解。例如：y1=2， y2=0 ，則 y3 只能為1，余料為0.1。像這樣的非負整數解共有

5、8組，也就是有8種下料方式，如表1.4所示。,2、建立線性規(guī)劃數學模型。設xj (j=1,2,8)為第 j 種下料方案所用圓鋼的根數。,思考題：（下料問題）,2020/9/15,9,min Z = x1+x2+x3 +x4+x5 +x6+x7 +x8,(x1=10, x2=50, x4=30, 16m),2020/9/15,10,思考題：某糖果廠用原料A，B，C加工成三種不同牌號糖果甲、乙、丙。已知各種糖果的中A，B，C的含量，原料成本，各種原料每月的限制用量，三種牌號糖果的單位加工費及售價如下表所示。,問該廠每月生產這三種牌號糖果各多少kg，利潤最大？,2020/9/15,11,解：設xij

6、為生產第j種糖果使用的第i種原料的公斤數，i=1,2,3；j=1,2,3，則該問題的數學模型可歸結為：,最優(yōu)解：,即該廠每月應生產甲種牌號糖果906.67kg，乙種牌號糖果4793.33kg。,2020/9/15,12,思考題：（投資問題）,某投資公司在第一年初有100萬元資金，每年都有如下的投資方案：假使第一年初投入一筆資金，第二年初又繼續(xù)投入此資金的50%，那么到第三年初就可回收第一年初投入資金的兩倍。問：該投資公司如何確定投資策略使第六年初所擁有的資金最多？,解：設x1為第一年的投資，x2為第一年的保留資金，則：,x1 + x2 = 100,第二年： 設x3為第二年新的投資，x4為第二年

7、的保留資金，則：,2020/9/15,13,第三年：設 x5 為新的投資，x6 為第三年的保留資金；,第四年：設新的投資 x7 ，第四年的保留資金 x8 ；,第五年：設 x9 為第五年的保留資金。根據題意，第五年初不再進行新的投資，因為這筆投資要到第七年初才能收回。,約束條件 每年應滿足如下的關系： 追加投資金額 + 新投資金額 + 保留資金=可利用的資金總額,2020/9/15,14,X*(22.64, 72.36, 58.54, 0, 26.02, 0, 104.06, 0, 0)T，Z*208.12。,到第六年初，實有資金總額為x9 + 2x7，整理后得到下列線性規(guī)劃模型：,max Z

8、= 2x7 + x9,第一年投資22.64元; 第二年新投資58.54元; 第三年新投資26.02元;第四年新投資104.06元; 第六年初擁有資金208.12萬元。,2020/9/15,15,思考題：某人有30萬元資金，在今后的三年內有以下投資 項目可供參考： (1) 三年內的每年年初均可投資，每年獲利為投資額的20%，其本利可一起用于下一年的投資； (2) 只允許第一年年初投入，第二年末可收回，本利合計為投資額的150%，但此類投資額不超過15萬元； (3) 第二年初允許投資，可于第三年末收回，本利合計為投資額的160%，這類投資限額20萬元； (4) 第三年初允許投資，一年回收，可獲利4

9、0%，投資限額為10萬元。 試為該人確定一個使第三年末本利和為最大的投資計劃？ （假設有錢就用于投資）,設xij為第 i 年初投入到 j 項目的資金額,2020/9/15,16,對于約束條件：,第1年，可用于項目1和2投資： x11 + x12 = 300000,第2年，可用于項目1和3投資，投資額為x11的本利和：x21 + x23 = 1.2 x11,第3年，可用于項目1和4投資，投資額x21和x12有關： x31 + x34 = 1.2 x21 + 1.5 x12,投資限額： x12 150000; x23 200000; x34 100000,非負約束： xij 0 ( i = 1,2

10、,3; j = 1,2,3,4 ),對于目標函數，只需考慮第3年末的收益：,項目1：x31 1.2 x31 (本利和)；,項目2：x22 0；,項目3：x23 1.6 x23 (本利和)；,項目4：x34 1.4x34 (本利和)；,maxZ = 1.2 x31 + 1.6 x23 + 1.4 x34,2020/9/15,17,解：設xij為第 i 年初投入到 j 項目的資金額，其數學模型為：,maxZ = 1.2 x31 + 1.6 x23 + 1.4 x34,注意本題條件：有錢就會用于投資，即： 可利用的資金 = 投資金額，據此建立約束等式。,x11 + x12 = 300000 x21

11、+ x23 = 1.2 x11 x31 + x34 = 1.2 x21 + 1.5 x12 x12 150000 x23 200000 x34 100000 xij 0 (i = 1,2,3; j = 1,2,3,4),2020/9/15,18,二、線性規(guī)劃問題的數學模型3.30,線性規(guī)劃問題的數學模型包括三大要素： （1）一組決策變量（x1 , x2 , , xn），是模型中需要首確定的未知量。 （2）一組約束條件，是模型中決策變量受到的約束限制，包括兩個部分：不等式或等式；非負取值（實際問題）。 （3）一個目標函數，是關于決策變量的最優(yōu)函數，max或min。,2020/9/15,19,思考

12、：為什么稱以上問題為線性規(guī)劃問題呢？,其主要特征是： 1. 解決的問題是規(guī)劃問題； 2解決問題的目標函數是多個決策變量的 線性函數，通常是求最大值或最小值； 3解決問題的約束條件是多個決策變量 的線性不等式或等式。,2020/9/15,20,線性規(guī)劃問題模型的一般形式可總結為：,線性規(guī)劃問題模型的一般形式,用一組非負決策變量表示的一個決策問題； 存在一組等式或不等式的線性約束條件； 有一個希望達到的目標，可表示成決策變量的極值線性函數。,為了書寫方便，上式也可簡寫：,2020/9/15,21,一般地，xj0，但有時xj0或xj無符號限制。,2020/9/15,22,其中：cj為價值系數，C=(

13、c1, c2, cn)為價值向量；aij為技術系數，A=(P1, P2, Pn)為技術矩陣，如： P1=(a11, a21, am1)T， P2=(a12, a22, am2)T， Pn=(a1n, a2n, amn)T； bi為限制系數，b=(b1, b2, bm)T。,2020/9/15,23,線性規(guī)劃模型矩陣形式，,其中： X=(x1, x2, xn)T； C=(c1, c2, cn) ； b=(b1, b2, bm)T。,技術系數矩陣：,2020/9/15,24,第二節(jié) 用于兩個變量線性規(guī)劃問題的圖解法,1、概念： 利用幾何圖形求解兩個變量線性規(guī)劃問題的方法。,3、求解步驟：,第一步：

14、建立平面直角坐標系；,第三步：在可行域內平移目標函數等值線， 確定最優(yōu)解及最優(yōu)目標函數值。,2、特點： 簡單、直觀，但只適用于兩個變量的LP問題。,第二步：根據約束條件畫出可行域；,2020/9/15,25,可行解：滿足約束條件的解； 可行域：所有可行解的集合； 最優(yōu)解：使目標函數達到最優(yōu)的可行解。 可行域：滿足所有約束條件的解的集合，即所有約束條件 共同圍城的區(qū)域。,maxZ= 3x1 + 5x2 2x1 16 2x2 10 3x1+4x2 32 x10, x20,s.t.,2020/9/15,26,目標函數等值線,目標函數 Z = 3x1 + 5x2 代表以 Z 為參數的一族平行線。,(4

15、, 5),2020/9/15,27,例：用圖解法求解線性規(guī)劃問題？,坐標系：橫坐標x1 ，縱坐標x2,(2, 6),先將約束不等式變?yōu)榈仁?，畫出各等式對應的直線，然后再根據不等式符號確定可行域,*線性規(guī)劃問題解的可能,結論： 該問題具有唯一最優(yōu)解，X*=(2,6)T，Z*=360,向上平移目標函數等值線 x2 = -3x1/5 + Z/50，確定最優(yōu)解。,2020/9/15,28,x1,x2,O,10,20,30,40,10,20,30,40,(15,10),最優(yōu)解 X* = (15,10)T,最優(yōu)值 Z* = 85,2020/9/15,29,2,4,6,x1,x2,2,4,6,最優(yōu)解 X*

16、= (3,1)T 最優(yōu)值 Z* = 5,(3,1),min Z = x1 + 2x2,2020/9/15,30,例：用圖解法進行求解線性規(guī)劃問題？,如果線性規(guī)劃問題有兩個最優(yōu)解， 則它一定有無窮多最優(yōu)解（多重最優(yōu)解）。,2020/9/15,31,例 用圖解法求線性規(guī)劃問題？,2020/9/15,32,該線性規(guī)劃問題具有無界解。 可行域無上界，目標值可以無限增大 (缺乏必要約束),2020/9/15,33,例,2020/9/15,34,該線性規(guī)劃問題無可行解，原因： 線性規(guī)劃問題的可行域是空集 (約束條件相互矛盾),2020/9/15,35,x2,x1,O,10,20,30,40,10,20,3

17、0,40,50,50,無可行解 即無最優(yōu)解,max Z=10 x1+4x2,2020/9/15,36,圖解法的解題思路和幾何上的直觀表示，對求解線性規(guī)劃問題的求解具有重要啟示： （1）LP問題的解一般有唯一解、無窮多最優(yōu)解、無界解和無可行解四種情況。 （2）LP問題的可行域一般為無界或有界凸多邊形。 （3）若LP問題的最優(yōu)解存在，即有唯一最優(yōu)解或無窮多最優(yōu)解，則必在可行域的某個項點上找到最優(yōu)解。 （4）若LP問題有兩個最優(yōu)解，則在它們的連線上的任意一點都是最優(yōu)解。,作業(yè)：教材第37頁，1.3：(1)、(2)、(3)；1.4,2020/9/15,37,一、線性規(guī)劃數學模型的標準型,第三節(jié) 線性規(guī)

18、劃問題數學模型的標準形式,1、標準型表達方式,(1)代數式：,(2)向量式：,(3)矩陣式：,A：技術系數矩陣，簡稱系數矩陣； B：可用的資源量，稱資源向量； C：決策變量對目標的貢獻，稱價值向量； X：決策向量。,2020/9/15,38,通常X記為： ，其中，為約束方程的系數矩陣，m是約束方程的個數，n是決策變量的個數，一般情況mn，且r()m。,其中:,2020/9/15,39,2、一般型標準型的轉換方法,(1) “決策變量非負”。若某決策變量 xk 為“取值無約束”(無符號限制)，令：xk = xk x”k ，(xk0, x”k 0) 。 (2) “目標函數求最大值”。如果極小化原問題

19、minZ = CX，則令 Z = Z，轉為求 maxZ = CX 。 注意：求解后還原。 (3) “約束條件為等式”。對于 “”型約束，則在“”左端加上一個非負松弛變量(slack variable) ，使其為等式。 對于“”型約束，則在“”左端減去一個非負剩余變量(Surplus variable) ，使其為等式。 (4) “資源限量非負”。若某個 bi 0，則將該約束兩端同乘 “1” ，以滿足非負性的要求。,2020/9/15,40,【例】將下列線性規(guī)劃化為標準型？,【解】(1)因為 x3 無符號要求(取值無約束) ，x3可以取正值也可取負值，但標準型中要求變量非負，所以可令：,對于x10

20、 ，可令：,2020/9/15,41,(3) 第二個約束條件是“”號，在“”左端減去剩余變量x5，x50， x5也稱松馳變量,(2) 第一個約束條件是“”號，在“”左端加入松馳變量 x4，x40，化為等式；,(4) 第三個約束條件右端常數項為負數，因此在不等式兩端乘以“1”。,(5) 目標函數是最小值，令Z=Z,得到max Z= max(Z)，即當Z達到最小值時Z達到最大值，反之亦然。,(1) x3 取值無約束 ，令 x3 = x3 x3，x3, x3 0。 同時,2020/9/15,42,標準型為：,2020/9/15,43,【練習】將下列線性規(guī)劃化為標準型？,【解】(1)因為 x3 無符號

21、要求(取值無約束) ，即x3取正值也可取負值，但標準型中要求變量非負，所以可令：,2020/9/15,44,(3) 第二個約束條件是“號”，在“號”左端減去剩余變量x5，x50， x5也稱松馳變量,(2) 第一個約束條件是“號”，在“”左端加入松馳變量 x4，x40，化為等式；,(4) 第三個約束條件是“號”且常數項為負數，因此在“”左邊加入松馳變量x6，x60，同時不等式兩端乘以“1”。,(5) 目標函數是最小值，令Z=Z,得到max Z= max(Z)，即當Z達到最小值時Z達到最大值，反之亦然。,(1) x3 取值無約束 ，令 x3 = x3 x3，x3, x3 0。,作業(yè)：教材第38頁，

22、1.5：(1)、(2)、(3),2020/9/15,45,【練習】將下列線性規(guī)劃化為標準型？(教材第38頁，1.5),【解】先將模型變換成一般形式：,標準型：,2020/9/15,46,第四節(jié) 線性規(guī)劃問題解的一般性質,1、線性規(guī)劃解的概念,基矩陣：一個非奇異的子矩陣（線性無關）。 矩陣A 中任意一個 m 列的線性無關子矩陣 B ，稱為一個基(矩陣)。 組成基的列向量稱為基向量，用 Pj 表示 ( i = 1 , 2 , , m ) 。 基變量： 與基向量 Pj 相對應的變量 xj 稱為基變量。 其余的 n m 個變量稱為非基變量(基矩陣以外的列向量對應變量)。,基(本)解：令所有非基變量等于

23、零，得出的唯一解。,2020/9/15,47,重要概念,可行解：滿足約束條件AX=b和X0的解。 基(本)解：令所有非基變量等于零，得出的唯一解。 基(本)可行解：滿足X0的基解。 可行基：基可行解對應的基矩陣。 最優(yōu)解：使目標函數最優(yōu)的基可行解，稱為最優(yōu)解。 最優(yōu)基：最優(yōu)解對應的基矩陣，稱為最優(yōu)基。,2020/9/15,48,基的概念,假設線性規(guī)劃問題模型系數矩陣為m行、n列，則系數矩陣中秩為m的m行m列子矩陣，稱為基矩陣，簡稱為基。,基中的列向量對應的變量稱為基變量，決策變量中基變量以外的變量稱為非基變量。,2020/9/15,49,基本解,對于某一確定的基，令所有非基變量為0，由約束方程

24、組AX=b可解出m個基變量的唯一解，稱為一個基本解。,2020/9/15,50,基本可行解,滿足非負條件的基本解，稱為基本可行解，基本可行解對應于凸多邊形的項點。,2020/9/15,51,練習：已知線性規(guī)劃問題4.2,問：,中哪一個是基本可行解？,2020/9/15,52,二、線性規(guī)劃問題解的性質,1、凸集和極點(頂點)的概念,由約束條件形成的可行域是凸多邊形(凸集) 凸集：對于某一集合內部任意兩點連線上的點都屬于這個集合，我們就稱這個集合為凸集(直觀理解)。,可行域具有有限個頂點。 目標函數最優(yōu)值一定在可行域的邊界(頂點)達到，而不可能在其區(qū)域的內部。,2020/9/15,53,凸集的數學

25、定義,設K為n維歐氏空間的一個點集，若K中任意兩個點X1和X2連線上的所有點都屬于K，則稱K為凸集。,X2,X1,X,設X(x1,x2,xn); X1(u1,u2,un); X2(v1,v2,vn),2020/9/15,54,極點： 設S為凸集，若S中的點x不能成為S中任何線段的內點，即“不能用S中兩個不同的點線性表示”，則稱x為S的極點。,2020/9/15,55,定理1.1 若線性規(guī)劃問題的可行域非空，則S為凸集(有界或無界)。即連接任意兩個可行解的線段上的點仍為可行解。 定理1.2 線性規(guī)劃問題的可行域S中的點X是極點的充要條件是X是基本可行解。即凸多邊形的頂點就是基本可行解。 定理1.

26、3 若可行域有界，線性規(guī)劃的目標函數一定可以在可行域的頂點上達到最優(yōu)。 如果線性規(guī)劃問題有最優(yōu)解，則最優(yōu)解一定在可行域S的某個極點上得到。,2020/9/15,56,第五節(jié) 單純形法原理,一、線性規(guī)劃問題的解題思路,首先，找到一個初始基可行解，也就是找到一個初始可行基，想辦法判斷這個基可行解是不是最優(yōu)解。 如果是最優(yōu)解，就得到這個線性規(guī)劃問題的最優(yōu)解； 如果判斷出不是最優(yōu)解，就想法由這個可行基按一定規(guī)則變化到下一個可行基，然后再判斷新得到的基可行解是不是最優(yōu)解； 如果還不是，再接著進行下一個可行基變化，直至找到最優(yōu)解。,2020/9/15,57,求解線性規(guī)劃問題的思路單純形法,2020/9/1

27、5,58,一、用消化法求解線性規(guī)劃問題（教材第20頁例題）,解：(一)標準化：,(二)求初始基可行解,2020/9/15,59,令非基變量：x1=x2=0，得到初始基可行解： X(0)=(0,0,4,3,8)T,此時，目標函數值： Z(0) = 2x1 + 5x2 + 0 = 0目標函數用非基變量表示。,(三)判優(yōu),對于Z(0) = 2x1 + 5x2 ，若x1或x2從0變?yōu)檎龜?，則目標函數值會增加，因此可判斷X(0)一定不是最優(yōu)解。(X(0) X*),2020/9/15,60,Z(0) = 2x1 + 5x2,(四)方案調整(換基),尋找一個新的基可行解，使目標函數值得到改善。,選擇入基變量

28、 尋找使目標函數增加量最大的非基變量入基，即目標函數中系數最大的變量。(x2),選擇出基變量 為什么要選擇原基變量出基？,要求決策變量非負，因此有：,說明x2最大可以是3，且當x2=3時，x4=0，即x4出基。 ( x4),2020/9/15,61,(五)求新的基可行解,此時，基變量為x3、x2和x5，非基變量為x1和x4。,用非基變量表示基變量：用x4表示x2，x2 = 3 x4 ，用x4表示x5，x5 = 2 x1 2x4 。,令非基變量 x1 = x4 = 0，則 X(1) = (0, 3, 4, 0, 2)T 。,2020/9/15,62,(六)判優(yōu)(檢驗),將式(4)代入目標函數，目

29、的：用非基變量表示目標函數，得到新的目標函數值： Z(1) = 2x1 + 5x2 = 2x1 + 5(3 x4) = 2x1 5x4 + 15,非基變量x1的系數為2，大于零，可見，如果x1 能從非基變量變?yōu)榛兞?，即變?yōu)檎龜担瑒t目標函數值會增加，因此X(1) = (0, 3, 4, 0, 2)T 不是最優(yōu)解。,2020/9/15,63,Z(1) = 2x1 5x4 + 15,(七)換基,當x1 = 2時，x5 = 0,即：當x1 入基，x5 出基。,2020/9/15,64,(八)求新的基可行解,此時，基變量為x3、x2和x1，非基變量為x4和x5。,用非基變量表示基變量： x1 = 2

30、+ 2x4 x5 ， x3 = 2 2x4 + x5 。,令非基變量 x4 = x5 = 0，則 X(2) = (2, 3, 2, 0, 0)T 。,2020/9/15,65,松弛變量x3 = 2,說明第一項資源有剩余，資源相對寬松，這就是松馳變量的經濟含義。,(九)判優(yōu)(檢驗),非基變量x4和x5的系數均為負值，如果x4 和x5從非基變量變?yōu)榛兞?，即從零變?yōu)檎龜?，則目標函數值會減少，因此X(2) = (2, 3, 2, 0, 0)T 是最優(yōu)解，目標函數最優(yōu)值Z* = 19。,2020/9/15,66,求解過程(換基迭代過程),初始基,初始基可行解：X(0)=(0,0,4,3,8)T Z(0

31、) =0,新的基可行解：X(1)=(0,3,4,0,2)T Z(1) =15,新的可行基,最優(yōu)基,最優(yōu)解：X* = (2,3,2,0,0)T Z* =19,2020/9/15,67,單純形法原理-矩陣推導(1),2020/9/15,68,單純形法原理-矩陣推導(2),非基變量檢驗數,令非基變量等于0，則,2020/9/15,69,單純形法原理(單純形表),2020/9/15,70,單純形法求解線性規(guī)劃問題的步驟：,(1)求出初始基本可行解(標準化、單位基)；,(2)最優(yōu)性檢驗(非基變量檢驗數非正時停止，否則進入下一步)；,(3)換基(迭代)； 確定入基變量 確定出基變量 初等變換，求出新的基本

32、可行解,(4)重復步驟(2)、(3)，直到求出最優(yōu)解。,2020/9/15,71,單純形法求解步驟舉例,maxZ = 2x1 + 5x2 +0 x3 +0 x4+0 x5 x1 + x3 = 4 x2 + x4 = 3 x1 + 2x2 + x5 = 8 xj0, j = 1, 2, , 5,2020/9/15,72,最優(yōu)解: X*=(2,3,2,0,0)T，Z*=19,思考: 在最終單純形表中，B-1 = ？4.8,2020/9/15,73,單純形法的管理啟示,x1= 4,x1 + 2x2 = 8,X(0) =(0, 0, 4, 3, 8)T,X(1) =(0, 3, 4, 0, 2)T,X

33、(2) =(2, 3, 2, 0, 0)T,在管理過程中，把現有方案作為初始方案，找到最急需要改進的某個問題和改進方向，一次做好某個主要問題的解決與改進；一次只解決和改進一個問題的難度最?。唤鉀Q之后，再尋求可以改進的其它地方，再次改進，不斷地追求更優(yōu)。,2020/9/15,74,解：引入松馳變量x3, x4 , x5 ，化為標準形式：,2020/9/15,75,由于x1，x2的檢驗數均為非負，且x2的檢驗數2最大，選x2為入基變量；再按最小比值l = min(-, 3/1, 8/2) = 3，選x4為出基變量。,x2,5,2,1,0,0,-2,1,2,0,0,-5,0,15,2020/9/15

34、,76,由于x1檢驗數為非負，選x1為入基變量；再按最小比值 l = min（4/1, -, 2/1）=2，選x5為出基變量。,x1,2,2,0,0,1,2,-1,0,0,0,-1,-2,19,2020/9/15,77,初始基本可行解：X(0) = (0, 0, 4, 3, 8)T，Z(0) = 0,新的基本可行解：X(1) = (0, 3, 4, 0, 2)T，Z(1) = 15,新的基本可行解：X(2) = (2, 3, 2, 0, 0)T，Z(2) = 19,判別定理 1： 在單純形表中，若所有非基變量的檢驗數小于零，且B-1b均為非負，則線性規(guī)劃問題具有唯一最優(yōu)解。,2020/9/15

35、,78,圖解法與單純形法求解結果對照：,A (0, 0),A：X(0) = (0, 0, 4, 3, 8)T，Z(0) = 0,B (0, 3),B：X(1) = (0, 3, 4, 0, 2)T，Z(1) = 15,C,C：X * = (2, 3, 2, 0, 0)T，Z* = 19,D (4, 2),E (4, 0),2020/9/15,79,課堂練習 求解下列線性規(guī)劃問題,解：引進松馳變量x3, x4, x5，化為標準形式：,2020/9/15,80,x2,4,2,-1/2,1,1/2,0,0,6,2,0,-1,1,0,4,1/2,0,1/2,0,1,4,0,-2,0,0,8,2020/

36、9/15,81,x1,2,3,1,0,-1/2,1/2,0,0,1,1/4,1/4,0,7/2,0,0,3/4,-1/4,1,5/2,0,0,-2,0,20,0,2020/9/15,82,x3,0,10/3,0,0,1,-1/3,4/3,8/3,0,1,0,1/3,-1/3,14/3,1,0,0,1/3,2/3,0,0,-2,0,0,20,2020/9/15,83,初始基本可行解：X(0) = (0, 0, 4, 10, 2)T，Z(0) = 0,新的基本可行解：X(1) = (0, 2, 0, 6, 4)T，Z(1) = 8,新的基本可行解：X(2) = (3, 7/2, 0, 0, 5/2

37、)T，Z(2) = 20,新的基本可行解：X(3) = (14/3, 8/3, 10/3, 0, 0)T，Z(3) = 20,判別定理 2：在單純形表中，若所有非基變量的檢驗數小于等于零，且B-1b均為非負，其中某個檢驗數等于零，則線性規(guī)劃問題具有無窮多最優(yōu)解(多重最優(yōu)解)。,2020/9/15,84,圖解法求解結果：,A (0, 0),A：X(0) = (0, 0, 4, 10, 2)T，Z(0) = 0,B (0, 2),B：X(1) = (0, 2, 0, 6, 4)T，Z(1) = 8,C (3,7/2),C：XC* = (3, 7/2, 0, 0, 5/2)T，Z* = 20,D (

38、14/3, 8/3),E (2, 0),D：XD* = (14/3, 8/3, 10/3, 0, 0)T，Z* = 20,2020/9/15,85,例 求解下列線性規(guī)劃問題,解：引進松馳變量x3, x4，標準化：,2020/9/15,86,不滿足出基變量確定法則：,雖然，不能確定x3和x4中哪個變量出基，但無論哪個變量出基，都必須滿足： x30，x40。x2入基，則： x2 0 (x20) 。,說明x2可以無限增大，所以目標函數值可以無限增大。,2020/9/15,87,圖解法求解結果：,判定定理3：,在單純形表中，若某個檢驗數k 大于零，且xk對應列向量的元素均為非正，導致出基變量無法確定，

39、則線性規(guī)劃問題具有無界解。,2020/9/15,88,練習 求解下列線性規(guī)劃問題,解：引進松馳變量x3, x4，化為標準形式：,從標準形中可看出存在可行基B=(P3，P4)=I，基變量為X3，X4；非基變量為X1，X2。建立初始單純形表得：,2020/9/15,89,由于x1，x2的檢驗數均為非負，且x1的檢驗數絕對值最大，選取x1為進基變量；再按最小比值=min（24/2，26/3）=26/3，選取x4為出基變量，進行換基迭代。,2020/9/15,90,表中最后一行的所有檢驗數均為非正，表明目標函數已達到最大值，上表為最優(yōu)單純形表。從表中可得到最優(yōu)解為：X*=(x1, x2, x3, x4

40、)T = (6, 4, 0, 0)T，最優(yōu)值為：Z*=36。,作業(yè)：教材39頁，1.8第(1),(4)題,在最終單純形表中，所有非基變量檢驗數均為負數，說明該線性規(guī)劃問題具有唯一最優(yōu)解：X= (6, 4, 0, 0)T，Z*=36。,2020/9/15,91,練習：已知某線性規(guī)劃用單純形法求得的某兩步迭代表如下，請將表中空白處填上適當的數字。,2020/9/15,92,討論：用單純形法求解某極大化問題的單純形表如下，問表中參數 a1, a2, a3, d, 1, 2 為何取值范圍時，下列結論成立。,(1)表中解為唯一最優(yōu)解： (2)表中解為無窮多最優(yōu)解： (3)該問題具有無界解： (4)表中解

41、為退化的基解： (5)表中解為不可行解： (6) x1入基，x6出基：,10, 20, 12 = 0, d 0,1 0, 2 0, d 0,2 0, a1 0, d 0,d = 0,d 0,1 0, a3 0 , d 0, d /4 3/a3,2020/9/15,93,思考題： 已知線性規(guī)劃問題：,其中b1, b2是常數，且已知此問題的最終單純形表如下。試確定表中所有的參數及b1和b2的值？,e = 0, d = 5, b = 5, c = 10, a = 23, b1= 30, b2= 40,2020/9/15,94,思考題：已知線性規(guī)劃問題的最優(yōu)單純形表如下，求初始單純形表中參數C, A,

42、 b 以及最優(yōu)基B ？,2020/9/15,95,解法(一)：矩陣初等行變換,增廣矩陣：,求A和b：,2020/9/15,96,求cj：,最優(yōu)基？,2020/9/15,97,解法(二)：用B-1求解,2020/9/15,98,求C和b：,2020/9/15,99,求解結果：,2020/9/15,100,大M法（大M單純形法）,通過添加人工變量構成單位基，進而求解線性規(guī)劃問題的方法。,2020/9/15,101,例 求解下列線性規(guī)劃問題,解：引進松馳變量x4, x5，化為標準形式：,2020/9/15,102,加入變量x6, x7，加入參數M，M為任意大的正數,2020/9/15,103,x3,

43、-1,10,3,-2,0,1,0,0,-1,1,0,1,0,0,-1,1,-2,1,-1+M,0,0,-M,0,1-3M,2020/9/15,104,x2,-1,12,3,0,0,1,-2,2,-5,1,-2,0,1,0,0,0,1,1,0,0,0,-1,1-M,-1-M,2020/9/15,105,x1,3,4,1,0,0,1/3,-2/3,2/3,-5/3,9,0,0,1,2/3,-4/3,4/3,-7/3,0,0,0,-1/3,-1/3,1/3-M,2/3-M,2,X*= (4, 1, 9, 0, 0, 0, 0)T,Z*= 2,2020/9/15,106,大M法求解的可能結果：,(1)基變量中不含人工變量；,(2)基變量中含人工變量，但人工變量取值為零；,(3)基變量中含人工變量，但人工變量取值不為零；,只在前兩種情況下，線性規(guī)劃問題有最優(yōu)解，對于第三種情況，線性規(guī)劃問題無可行解。,2020/9/15,107,例,2020/9/15,108,x1,30,2,0,0,-1,-1,0,0,1,6,0,2,-3,0,0,1,0,2020/9/