1.線性規(guī)劃課件(PPT 95頁)

1、運籌學(xué)管理科學(xué)與工程學(xué)院電子商務(wù)系劉承昕第1頁，共95頁。運籌學(xué)第一章 緒論第二章 線性規(guī)劃（Linear Programming）第三章 對偶理論（Dual Theory）第四章 運輸問題（Transportation Problem）第五章 整數(shù)規(guī)劃（Integer Programming）第六章 圖論（Graph Theory）第2頁，共95頁。第一章 緒論第3頁，共95頁。第一章 緒論一、運籌學(xué)的定義運用科學(xué)的方法研究管理和工程中各種決策問題，為決策者提供科學(xué)的決策依據(jù)的學(xué)科。二、運籌學(xué)的研究方法將實際問題定量化和模型化，運用數(shù)學(xué)、統(tǒng)計學(xué)、計算機科學(xué)和工程等學(xué)科的原理和技術(shù)研究各種組織

2、系統(tǒng)的管理問題和生產(chǎn)經(jīng)營活動，以求得到一個合理的運用資源的最優(yōu)方案，達到系統(tǒng)效益的最優(yōu)化。第4頁，共95頁。第一章 緒論三、運籌學(xué)的工作步驟提出問題，并根據(jù)需要收集有關(guān)數(shù)據(jù)信息建立模型，引入決策變量，確定目標函數(shù)（約束條件）模型求解，獲得最優(yōu)或次優(yōu)解檢驗?zāi)Ｐ秃徒獾暮侠硇?，必要時修正根據(jù)最優(yōu)方案提出管理建議幫助實施管理決策第5頁，共95頁。第二章 線性規(guī)劃Linear Programming第6頁，共95頁。第1節(jié) 數(shù)學(xué)模型一、規(guī)劃問題含義：如何合理地利用有限的人力、物力、財力等資源，以便得到最好的經(jīng)濟效果。第7頁，共95頁。第1節(jié) 數(shù)學(xué)模型例1：用一塊邊長為a的正方形鐵皮做一個容器，應(yīng)該如何裁

3、剪，使做成的容器的容積最大（如下圖所示）。ax第8頁，共95頁。第1節(jié) 數(shù)學(xué)模型例1：解：設(shè)在鐵皮四個角上剪去四個邊長各為x的正方形 V=(a-2x)(a-2x)xmax 滿足 xa/2 x0第9頁，共95頁。第1節(jié) 數(shù)學(xué)模型例2：某企業(yè)計劃生產(chǎn)、兩種產(chǎn)品，都要分別在A，B，C，D四種不同設(shè)備上加工。按工藝資料規(guī)定，生產(chǎn)每件產(chǎn)品需占用各設(shè)備分別為2，1，4，0（小時），生產(chǎn)每件產(chǎn)品需占用各設(shè)備分別為2，2，0，4（小時）。已知各設(shè)備計劃期內(nèi)用于生產(chǎn)這兩種產(chǎn)品的能力分別為12，8，16，12（小時），又知每生產(chǎn)一件產(chǎn)品，企業(yè)能獲利2元，每生產(chǎn)一件產(chǎn)品 ，企業(yè)能獲利3元。問：該企業(yè)應(yīng)如何安排生產(chǎn)兩

4、種產(chǎn)品各多少件，使企業(yè)的利潤收入最大。第10頁，共95頁。第1節(jié) 數(shù)學(xué)模型例2：解：設(shè)、兩種產(chǎn)品在計劃期內(nèi)的產(chǎn)量分別為x1、x2 z =2x1+3x2max 2x1+2x212 x1+2x28 滿足 4x116 4x212 x1，x20第11頁，共95頁。第1節(jié) 數(shù)學(xué)模型特征（1）決策變量（2）約束條件（3）目標函數(shù)第12頁，共95頁。第1節(jié) 數(shù)學(xué)模型二、線性規(guī)劃問題特征（三要素）（1）決策變量：問題中的未知量（2）目標函數(shù)：問題要達到的目標（最大或最?。?，表示為決策變量的線性函數(shù)（3）約束條件：表示為含決策變量的一組互不矛盾的線性等式或線性不等式的函數(shù)約束和決策變量的非負約束第13頁，共95

5、頁。第1節(jié) 數(shù)學(xué)模型線性規(guī)劃問題數(shù)學(xué)模型的形式（1）一般形式第14頁，共95頁。第1節(jié) 數(shù)學(xué)模型（2）簡寫形式（3）向量形式 （4）矩陣形式第15頁，共95頁。第1節(jié) 數(shù)學(xué)模型例2：一般形式 矩陣形式 max z =2x1+3x2 2x1+2x212 x1+2x28 4x116 4x212 x1，x20第16頁，共95頁。第1節(jié) 數(shù)學(xué)模型三、線性規(guī)劃數(shù)學(xué)模型的標準形式（標準型）目標函數(shù)求最大值函數(shù)約束條件全為等式?jīng)Q策變量全為非負函數(shù)約束條件右端項全為非負第17頁，共95頁。第1節(jié) 數(shù)學(xué)模型四、線性規(guī)劃的非標準型如何轉(zhuǎn)化為標準型目標函數(shù)求最小值：令z-z函數(shù)約束條件為不等式： ：在函數(shù)約束條件左

6、端加非負的松弛變量 ：在函數(shù)約束條件左端減非負的松弛變量 松弛變量在目標函數(shù)中的系數(shù)全為0決策變量為負值：令xj-xj， xj0決策變量取值無約束： 令xj xj- xj，xj0， xj0函數(shù)約束條件右端項（bi）為負值：函數(shù)約束條件兩端同乘-1第18頁，共95頁。第1節(jié) 數(shù)學(xué)模型要求：將下列線性規(guī)劃問題轉(zhuǎn)化為標準型。例3：min z =x1+2x2+3x3 -2x1+x2+x39 -3x1+x2+2x34 3x1-2x2-3x3=-6 x10，x20，x3取值無約束第19頁，共95頁。第1節(jié) 數(shù)學(xué)模型例3：解：令 max z=x1-2x2-3x3+3x3+0 x4+0 x5 2x1+x2+x

7、3-x3+x4=9 3x1+x2+2x3-2x3-x5=4 3x1+2x2+3x3-3x3=6 x1，x2，x3，x3，x4，x50第20頁，共95頁。第1節(jié) 數(shù)學(xué)模型例4： min z =-x1+2x2-3x3 x1+x2+x37 x1-x2+x32 -3x1+x2+2x3=5 x1，x20，x3無約束第21頁，共95頁。第1節(jié) 數(shù)學(xué)模型例4：解：令 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第22頁，共95頁。第1節(jié) 數(shù)學(xué)模型例5： max z =2x

8、1+3x2+5x3 x1+x2-x3-5 -6x1+7x2-9x3=16 19x1-7x25x313 x1，x20，x3無約束第23頁，共95頁。第1節(jié) 數(shù)學(xué)模型例5：解：令 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第24頁，共95頁。作業(yè)1作業(yè)1：將下列線性規(guī)劃問題化為標準型。1、min z =5x1-2x2+4x3-3x4 -x1+2x2-x3+4x4=-2 -x1+3x2+

9、x3+x414 2x1-x2+3x3-x42 x1無約束，x20，x3 ，x4 02、 min z =x1+2x2+4x3 2x1+x2+3x320 3x1+x2+4x325 x1，x20，x30第25頁，共95頁。作業(yè)1答案 1、 2、第26頁，共95頁。第2節(jié) 解一、線性規(guī)劃問題解的概念可行解：滿足函數(shù)約束條件和非負約束條件的解最優(yōu)解：使目標函數(shù)達到最大值的可行解基：設(shè)A是約束方程組的mn階系數(shù)矩陣，B是矩陣A中mm階非奇異子矩陣，稱B是線性規(guī)劃問題的一個基基向量：基B中每一個列向量Pj非基向量：A中其余列向量Pj（不在B中）基變量：與基向量Pj對應(yīng)的決策變量xj非基變量：與非基向量對應(yīng)的

10、決策變量基解基可行解：滿足非負約束條件的基解可行基：對應(yīng)于基可行解的基第27頁，共95頁。第2節(jié) 解二、線性規(guī)劃問題解的關(guān)系最優(yōu)解第28頁，共95頁。第2節(jié) 解線性規(guī)劃問題數(shù)學(xué)模型的標準形式（一般形式）第29頁，共95頁。第2節(jié) 解補充（復(fù)習(xí)）內(nèi)容秩：設(shè)在矩陣A中一個不等于0的r階子式D，且所有r1階子式（如果存在的話）全等于0，那么D為矩陣A的最高階非零子式，數(shù)r為矩陣A的秩。非奇異矩陣：行列式不等于0的矩陣?？巳R姆法則：如果線性方程組 a11x1+a12x2+a1mxm=b1 a21x1+a22x2+a2mxm=b2 am1x1+am2x2+ammxm=bm 的系數(shù)行列式不等于0，則方程組

11、有唯一解。第30頁，共95頁。第2節(jié) 解例6：求下述線性規(guī)劃的所有基解、基可行解及最優(yōu)解。 max z =3x1+x2+3x3 x1+x2+x32 x1+2x2+4x36 x1，x2，x30第31頁，共95頁。作業(yè)2作業(yè)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第32頁，共95頁。作業(yè)2答案1、 2、第33

12、頁，共95頁。第3節(jié) 圖解法一、圖解法適用條件：適用于求解只有兩個決策變量的線性規(guī)劃問題特點（1）不必將線性規(guī)劃問題轉(zhuǎn)化為標準型（2）直觀性強，計算方便第34頁，共95頁。第3節(jié) 圖解法例7：用圖解法求解下述線性規(guī)劃問題。 max z =2x1+3x2 x1+2x28 4x116 4x212 x1，x20第35頁，共95頁。第3節(jié) 圖解法例7：標出約束條件(0,0)(0,3)(2,3)(4,2)(4,0)第36頁，共95頁。第3節(jié) 圖解法例7：標出目標函數(shù)目標函數(shù)z第37頁，共95頁。第3節(jié) 圖解法二、圖解法的求解步驟建立 二維坐標系將約束條件表示在坐標系中，以確立可行域畫出每個函數(shù)約束的約束

13、邊界，用原點判斷直線的哪一邊是約束條件所允許的找出所有約束條件都同時滿足的區(qū)域，即可行域?qū)⒛繕撕瘮?shù)繪制在坐標系中，并標出變化的方向給定目標函數(shù)一個特定的值k，畫出目標函數(shù)特定線，當k變化時，目標函數(shù)特定線將平行移動對于目標函數(shù)最大（小）化的問題，找出目標函數(shù)增加（減少）的方向，目標函數(shù)最后離開可行域的點是最優(yōu)解確定最優(yōu)解第38頁，共95頁。第3節(jié) 圖解法三、圖解法解的類型唯一最優(yōu)解：僅有一點使目標函數(shù)值取得最大（?。┲禑o窮多（多重）最優(yōu)解：線段（射線）上任意一點都使目標函數(shù)值取得相同的最大（小）值無界解：可行域無界，目標函數(shù)值可以增大到無窮大無可行解：可行域為空集第39頁，共95頁。第3節(jié) 圖

14、解法要求：用圖解法求解下列線性規(guī)劃問題。例8： max z =2x1+4x2 x1+2x28 4x116 4x212 x1，x20第40頁，共95頁。第3節(jié) 圖解法例8：目標函數(shù) max z=2x1+4x2 z第41頁，共95頁。第3節(jié) 圖解法例9： max z =2x1+3x2 4x116 x1，x20第42頁，共95頁。第3節(jié) 圖解法例10： max z =2x1+3x2 2x1+2x212 x1+2x214 x1，x20第43頁，共95頁。第3節(jié) 圖解法四、圖解法解的特點當可行域非空集時，可行域必是有界或無界凸多邊形。（凸集：集合C中任意兩個點a和b，其連線上所有點也必為集合C中的點。）

15、若可行域有界，則目標函數(shù)一定可以在可行域的頂點上達到最優(yōu)；若可行域無界，則可能無最優(yōu)解，也可能有最優(yōu)解，若有也必定在某頂點上達到。第44頁，共95頁。第3節(jié) 圖解法線性規(guī)劃問題的每個基可行解對應(yīng)可行域的一個頂點，若線性規(guī)劃問題有最優(yōu)解，則必在頂點上達到。若有唯一最優(yōu)解，則一定在可行域的頂點處得到；若有兩個頂點同時達到最優(yōu)解，則兩個頂點之間線段上的任意一點都是最優(yōu)解，既有無窮多最優(yōu)解。線性規(guī)劃問題有最優(yōu)解，則解題思路：找出可行域的頂點，計算頂點處的目標函數(shù)值，比較各頂點的目標函數(shù)值，值最大（?。┑捻旤c為最優(yōu)解的點或最優(yōu)解的點之一。第45頁，共95頁。第3節(jié) 圖解法例11：下列哪一個圖是凸集？A

16、BC D第46頁，共95頁。第3節(jié) 圖解法例7圖解：目標函數(shù)z第47頁，共95頁。第3節(jié) 圖解法例8圖解：目標函數(shù) max z=2x1+4x2 z第48頁，共95頁。第3節(jié) 圖解法要求：用圖解法求解下列線性規(guī)劃問題。例12： min z =2x1-x2 -2x1+x22 x1-2x21 x1，x20第49頁，共95頁。第3節(jié) 圖解法例13：1、 max z =x1+x2 -2x1+x24 x1-x22 x1，x20 2、 max z =x1+2x2 x1+2x28 4x116 4x212 x1，x20第50頁，共95頁。作業(yè)3作業(yè)3：用圖解法求解下列線性規(guī)劃問題。1、 max z =50 x1

17、+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第51頁，共95頁。作業(yè)3答案1、2、3、4、第52頁，共95頁。第4節(jié) 單純形法一、單純形法的解題思路從某一基可行解開始，轉(zhuǎn)化到另一個相鄰的基可行解，并且使相應(yīng)的目標函數(shù)值有改進。即從可行域的一個頂點沿約束邊界轉(zhuǎn)換到可行域的另一個相鄰的且使

18、目標函數(shù)值有改進的頂點，直到目標函數(shù)值到達最優(yōu)時的頂點為止。第53頁，共95頁。第4節(jié) 單純形法定義兩個基可行解稱為相鄰的，如果它們之間變換且僅變換一個基變量。第54頁，共95頁。第4節(jié) 單純形法二、單純形法的含義單純形法是一種迭代算法，首先找到一個初始基可行解，然后判斷它是否為最優(yōu)解，如果是就停止迭代，否則，按照一定的法則，再找到一個更好且與當前基可行解相鄰的基可行解，再進行判斷，直到找不到更好的基可行解或判斷問題無解為止。第55頁，共95頁。第4節(jié) 單純形法三、單純形法的解題步驟1、找出初始可行基，確定初始基可行解，建立初始單純形表。c1cmcm+1cncBxBbx1xmxm+1xnc1x

19、1b110a1,m+1 a1,nc2x2b200a2,m+1a2,ncmxmbm01am,m+1am,n00第56頁，共95頁。第4節(jié) 單純形法例：線性規(guī)劃問題數(shù)學(xué)模型的某種標準形式第57頁，共95頁。第4節(jié) 單純形法2、檢驗各非基變量xj（j=m+1，m+2，n）的檢驗數(shù)j，若j0，則已得最優(yōu)解，停止計算，否則轉(zhuǎn)入3。3、在j0 （j=m+1，m+2，n）中，若有某個k對應(yīng)的xk的系數(shù)列向量Pk0，則此線性規(guī)劃問題存在無界解，停止計算，否則轉(zhuǎn)入4。4、根據(jù) ，確定xk為換入變量，通過 ，計算確定xl為換出變量，轉(zhuǎn)入5。第58頁，共95頁。第4節(jié) 單純形法5、以alk為主元素進行迭代，把xk所

20、對應(yīng)的列向量 將xB列中xl的換為xk，得到新的單純形表，重復(fù)25，直至終止。變換為第59頁，共95頁。第4節(jié) 單純形法例14：用單純形法求解例7。解： max z =2x1+3x2 x1+2x2+x3=8 4x1+x4=16 4x2+x5=12 x1，x2，x3，x4，x50第60頁，共95頁。第4節(jié) 單純形法例15：用單純形法求解下述線性規(guī)劃問題。 max z =2x1+x2 5x215 6x1+2x224 x1+x25 x1，x20第61頁，共95頁。第4節(jié) 單純形法例15：解： max z =2x1+x2 5x2+x3=15 6x1+2x2+x4=24 x1+x2+x5=5 x1，x2

21、，x3，x4，x50第62頁，共95頁。作業(yè)4作業(yè)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第63頁，共95頁。作業(yè)4答案1、2、第64頁，共95頁。第5節(jié) 人工變量法一、人工變量法的解題思路線性規(guī)劃問題中不存在現(xiàn)成的可行基，為了求一個初始可行基和初始基可行解，在每個約束方程中人為地加上一個變量（人工變量），使約束方程組的系數(shù)矩陣中產(chǎn)生初始基。第

22、65頁，共95頁。第5節(jié) 人工變量法二、人工變量法的含義若原線性規(guī)劃問題有可行解，則新的線性規(guī)劃問題的最優(yōu)解中人工變量的取值一定為0。第66頁，共95頁。第5節(jié) 人工變量法三、人工變量法的解題步驟將原問題轉(zhuǎn)化為標準型對或的約束條件添加人工變量，直至構(gòu)造出單位矩陣，且人工變量在目標函數(shù)中的系數(shù)為-M，建立初始單純形表按照單純形法的解題步驟25求解第67頁，共95頁。第5節(jié) 人工變量法例16：用人工變量法求解下述線性規(guī)劃問題。 max z =-3x1+x3 x1+x2+x34 -2x1+x2 -x31 3x2+x3=9 x1，x2，x30第68頁，共95頁。第5節(jié) 人工變量法例16：解：標準型第6

23、9頁，共95頁。第5節(jié) 人工變量法添加人工變量第70頁，共95頁。第5節(jié) 人工變量法例17：用人工變量法求解下述線性規(guī)劃問題。 max z =10 x1+15x2+12x3 5x1+3x2+x39 -5x1+6x2+15x315 2x1+x2+x35 x1，x2 ，x30第71頁，共95頁。第5節(jié) 人工變量法例17：解：標準型并添加人工變量 max z =10 x1+15x2+12x3-Mx7 5x1+3x2+x3+x4=9 -5x1+6x2+15x3+x5=15 2x1+x2+x3-x6+x7=5 x1，x2 ，x3 ，x4，x5 ，x6 ，x70第72頁，共95頁。第5節(jié) 人工變量法小結(jié)（

24、1）將線性規(guī)劃化為標準型后，對或的約束條件添加人工變量（若約束條件系數(shù)矩陣A中已有k個單位列向量，只要引入m-k個人工變量，使它們與原來的k個單位列向量合成單位矩陣）（2）在最優(yōu)解中，若人工變量大于0，則原問題無可行解第73頁，共95頁。作業(yè)5作業(yè)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第74頁，共95頁。作業(yè)5答案1、2、

25、第75頁，共95頁。第6節(jié) 單純形法小結(jié)標準型第76頁，共95頁。第6節(jié) 單純形法小結(jié)單純形表中解的表示形式1、唯一最優(yōu)解：所有非基變量檢驗數(shù)j02、無窮多最優(yōu)解：某非基變量檢驗數(shù)j03、無界解：某檢驗數(shù)j0對應(yīng)變量的系數(shù)列向量Pk04、無可行解：最終單純形表中含有0的人工變量第77頁，共95頁。第6節(jié) 單純形法小結(jié)5、退化基可行解：一個或幾個基變量0的基可行解出現(xiàn)退化基可行解，可能導(dǎo)致從某個基開始，經(jīng)過若干次迭代后又回到原來的基，即單純形法出現(xiàn)了循環(huán)，永遠達不到最優(yōu)解，導(dǎo)致計算失敗。為避免出現(xiàn)死循環(huán)，法則如下：選擇換入變量時，若有幾個正的檢驗數(shù)具有相同的最大值，則選擇下標最小的對應(yīng)的非基變量

26、作為換入變量選擇換出變量時，若按規(guī)則計算，有幾個比值同時達到最小，則選擇下標最小的對應(yīng)的基變量作為換出變量第78頁，共95頁。第6節(jié) 單純形法小結(jié)例18：下列表格是求線性規(guī)劃問題的單純形表，試說明解的情況。1、最終表 2 3 0 0 0CBxBb x1 x2 x3 x4 x5203x1x5x2442 1 0 0 1/4 0 0 0 -2 1/2 1 0 1 1/2 -1/8 0 0 0 -3/2 -1/8 0第79頁，共95頁。第6節(jié) 單純形法小結(jié)2、最終表 3 2 -1 0 0 0CBxBb x1 x2 x3 x4 x5 x6023x4x2x129/56/521/5 0 0 -1 1 -1/

27、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第80頁，共95頁。第6節(jié) 單純形法小結(jié)3、中間表 2 3 0 0 0 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第81頁，共95頁。第6節(jié) 單純形法小結(jié)4、最初表 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第82

28、頁，共95頁。第6節(jié) 單純形法小結(jié)5、中間表（最終表） 4 5 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 5 0 0 0第83頁，共95頁。第6節(jié) 單純形法小結(jié)6、中間表 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第84頁，共95頁。單純形法計算步驟框圖第85頁，共95頁。第6節(jié) 單純形法小結(jié)例19：用單純形法求解下述線性規(guī)劃問題，并說明解的情況。 max z =

29、2.5x1+x2 3x1+5x215 5x1+2x210 x1，x20第86頁，共95頁。第6節(jié) 單純形法小結(jié)例19：解：max z =2.5x1+x2 3x1+5x2+x3=15 5x1+2x2+x4=10 x1，x2 ，x3，x40第87頁，共95頁。作業(yè)6作業(yè)6：求解下述線性規(guī)劃問題，并說明解的情況。1、max z =6x1+4x2 -x1+2x24 3x1+2x214 2x1-x24 x1，x2 02、max z =2x1-x2+2x3 x1+x2+x36 -2x1+x32 2x2-x30 x1，x2，x30第88頁，共95頁。作業(yè)6答案第89頁，共95頁。第6節(jié) 單純形法小結(jié)例20：下表為求某最大化線性規(guī)劃問題的最終單純形表，其中x4，x5為松弛變量，試寫出該問題的最優(yōu)解。b x1 x2 x3 x4 x524 0 -1 1 3 1 1 -1 0 -1 0 0 -3 0 -3 -1第90頁，共95頁。第6節(jié) 單純形法小結(jié)例21：某線性規(guī)劃問題的標準型為 max z =CX AX=b X0其最終單純形表如下表，其中x4，x5為對應(yīng)于初始單位矩陣的