線性規(guī)劃及單純形法詳解演示文稿

線性規(guī)劃及單純形法詳解演示文稿現(xiàn)在是1頁\一共有150頁\編輯于星期三（優(yōu)選）線性規(guī)劃及單純形法現(xiàn)在是2頁\一共有150頁\編輯于星期三運籌學(xué)的定義運籌學(xué)（OperationsResearch） 系統(tǒng)工程的最重要的理論基礎(chǔ)之一，在美國有人把運籌學(xué)稱之為管理科學(xué)(ManagementScience)。運籌學(xué)所研究的問題，可簡單地歸結(jié)為一句話：“依照給定條件和目標，從眾多方案中選擇最佳方案”故有人稱之為最優(yōu)化技術(shù)。《中國企業(yè)管理百科全書》：“運籌學(xué)應(yīng)用分析、試驗、量化的方法，對經(jīng)濟管理系統(tǒng)中人、財、物等有限資源進行統(tǒng)籌安排，為決策者提供有依據(jù)的最優(yōu)方案，以實現(xiàn)最有效的管理。”現(xiàn)在是3頁\一共有150頁\編輯于星期三運籌學(xué)名稱的由來英文原名:OperationsResearch（縮寫為O.R.）直譯為“運用研究”、“作業(yè)研究”據(jù)研究內(nèi)容取名為“管理數(shù)學(xué)”：運籌學(xué)涉及的主要領(lǐng)域是管理問題，研究的基本手段是建立數(shù)學(xué)模型，并比較多地運用各種數(shù)學(xué)工具。1957年取名“運籌學(xué)”：《史記.高祖本紀》“夫運籌帷幄之中，決勝于千里之外”現(xiàn)在是4頁\一共有150頁\編輯于星期三運籌學(xué)在工商管理中的應(yīng)用生產(chǎn)計劃：生產(chǎn)作業(yè)的計劃、日程表的編排、合理下料、配料問題、物料管理等。庫存管理：多種物資庫存量的管理，庫存方式、庫存量等。運輸問題：確定最小成本的運輸線路、物資的調(diào)撥、運輸工具的調(diào)度以及建廠地址的選擇等。人事管理：對人員的需求和使用的預(yù)測，確定人員編制、人員合理分配，建立人才評價體系等?，F(xiàn)在是5頁\一共有150頁\編輯于星期三運籌學(xué)在工商管理中的應(yīng)用市場營銷：廣告預(yù)算、媒介選擇、定價、產(chǎn)品開發(fā)與銷售計劃制定等。財務(wù)和會計：包括預(yù)測、貸款、成本分析、定價、證券管理、現(xiàn)金管理等。其他：設(shè)備維修、更新，項目選擇、評價，工程優(yōu)化設(shè)計與管理等?，F(xiàn)在是6頁\一共有150頁\編輯于星期三運籌學(xué)的主要內(nèi)容（1）數(shù)學(xué)規(guī)劃線性規(guī)劃、非線性規(guī)劃、整數(shù)規(guī)劃、動態(tài)規(guī)劃、目標規(guī)劃（2）組合優(yōu)化最優(yōu)計數(shù)問題、網(wǎng)絡(luò)優(yōu)化、排序問題、統(tǒng)籌圖（3）隨機優(yōu)化對策論、排隊論、庫存論、決策分析、可靠性分析先修課：高等數(shù)學(xué)，基礎(chǔ)概率、線性代數(shù)特點：系統(tǒng)整體優(yōu)化；多學(xué)科的配合；模型方法的應(yīng)用現(xiàn)在是7頁\一共有150頁\編輯于星期三應(yīng)用運籌學(xué)解決問題的過程運籌學(xué)技術(shù)與方法的應(yīng)用可以讓決策者在面臨較為復(fù)雜且不確定的決策環(huán)境時，在保持自身判斷及偏好一致的條件下，進行輔助決策，但注意，不是代替決策者進行決策。規(guī)定目標和明確問題收集數(shù)據(jù)和建立模型求解模型和優(yōu)化方案檢驗?zāi)Ｐ秃驮u價方案方案實施和不斷改進解決問題制定決策現(xiàn)在是8頁\一共有150頁\編輯于星期三第1章線性規(guī)劃與單純形法現(xiàn)在是9頁\一共有150頁\編輯于星期三運籌學(xué)的一個主要的分支是數(shù)學(xué)規(guī)劃。數(shù)學(xué)規(guī)劃研究：在一些給定的條件（約束條件）下，求所考察函數(shù)（目標函數(shù)）在某種意義下的極值（極小或極大）問題。例如：在經(jīng)濟決策中，經(jīng)常會遇到諸如在有限的資源（人、原材料、資金等）情況下，如何合理安排生產(chǎn)，使效益達到最大；或者給定具體的任務(wù)，如何統(tǒng)籌安排現(xiàn)有資源，能夠完成給定的任務(wù)，使花費最小這類問題。在這章，我們重點介紹的是應(yīng)用最為廣泛的線性規(guī)劃問題。現(xiàn)在是10頁\一共有150頁\編輯于星期三第一章線性規(guī)劃與單純形法一、線性規(guī)劃模型實例二、線性規(guī)劃問題的數(shù)學(xué)模型三、求解線性規(guī)劃模型的圖解法四、單純形法五、單純形法的進一步討論六、作業(yè)現(xiàn)在是11頁\一共有150頁\編輯于星期三一、線性規(guī)劃模型實例（問題的提出）例1-1（生產(chǎn)計劃問題）某企業(yè)計劃生產(chǎn)I、II兩種產(chǎn)品。這兩種產(chǎn)品都要分別在A、B、C、D四個不同設(shè)備上加工。按工藝資料規(guī)定，生產(chǎn)每件產(chǎn)品I需占用各設(shè)備分別為2、1、4、0h，生產(chǎn)每件產(chǎn)品II需占用設(shè)備分別為2、2、0、4h。已知各設(shè)備計劃期內(nèi)用于生產(chǎn)兩種產(chǎn)品的能力分別為12、8、16、12h。又知每生產(chǎn)一件I企業(yè)能獲得2元利潤，每生產(chǎn)一件產(chǎn)品II企業(yè)能獲得3元利潤。問該企業(yè)應(yīng)如何安排生產(chǎn)，才能使總的利潤最大。現(xiàn)在是12頁\一共有150頁\編輯于星期三一、線性規(guī)劃模型實例（問題的提出）設(shè)備產(chǎn)品ABCD利潤（元/件）I21402II22043生產(chǎn)能力（h）1281612表1-1問題分析：（1）問題的目標是什么？合理安排生產(chǎn)，實現(xiàn)利潤最大化（2）利潤與哪些因素有關(guān)？產(chǎn)量和單位產(chǎn)量的利潤現(xiàn)在是13頁\一共有150頁\編輯于星期三問題分析：（1）問題的目標是什么？（2）利潤與哪些因素有關(guān)？（3）單位利潤最大的II產(chǎn)品，那么我們就僅生產(chǎn)II產(chǎn)品，是否可行？不可行，原因是各設(shè)備生產(chǎn)II產(chǎn)品的能力是有限的，僅僅生產(chǎn)II產(chǎn)品，設(shè)備的生產(chǎn)能力還有剩余。結(jié)論是兩種產(chǎn)品都要進行生產(chǎn)。（4）兩種產(chǎn)品的產(chǎn)量會受到什么限制條件呢？各種設(shè)備的生產(chǎn)能力，即占用各種設(shè)備的工時。（5）要決策的問題是：I產(chǎn)品生產(chǎn)多少？II產(chǎn)品生產(chǎn)多少？才能實現(xiàn)利潤最大化呢？現(xiàn)在是14頁\一共有150頁\編輯于星期三一、線性規(guī)劃模型實例（問題的提出）例1-1【解】：設(shè)x1和x2分別表示I、II兩種產(chǎn)品在計劃期內(nèi)的產(chǎn)量。因設(shè)備A在計劃期內(nèi)的有效時間為12h，不允許超過，因此建立不等式方程：2x1+2x2≦12同理對設(shè)備B、C、D也可以列出類似的不等式方程

x1+2x2≦84x1≦164x2≦12建立各種設(shè)備允許的情況下，企業(yè)總的利潤收入方程：

z=2x1+3x2按工藝資料規(guī)定，生產(chǎn)每件產(chǎn)品I需占用各設(shè)備分別為2、1、4、0h；生產(chǎn)每件產(chǎn)品II需占用設(shè)備分別為2、2、0、4h；已知各設(shè)備計劃期內(nèi)用于生產(chǎn)兩種產(chǎn)品的能力分別為12、8、16、12h現(xiàn)在是15頁\一共有150頁\編輯于星期三一、線性規(guī)劃模型實例（問題的提出）因此，該實例的問題可以歸結(jié)為如下的數(shù)學(xué)模型?；貞洠簲?shù)學(xué)規(guī)劃研究：在一些給定的條件（約束條件）下，求所考察函數(shù)（目標函數(shù)）在某種意義下的極值（極小或極大）問題。如何理解“線性規(guī)劃”？現(xiàn)在是16頁\一共有150頁\編輯于星期三一、線性規(guī)劃模型實例（問題的提出）例1-2（能源利用問題）假設(shè)某電廠以甲、乙、丙三種煤作為燃料煤，已知這三種煤的含硫量、發(fā)熱量及價格，見表1-2?，F(xiàn)在要將上述三種煤混合燃燒，按鍋爐要求，發(fā)熱量不能低于17000kJ/t；按環(huán)保要求，含硫量不能超過0.025%。問應(yīng)按什么比例將煤混合，才能使混合煤的價格最低？建立其數(shù)學(xué)模型?，F(xiàn)在是17頁\一共有150頁\編輯于星期三一、線性規(guī)劃模型實例（問題的提出）電廠含硫量（%）發(fā)熱量（kJ/t）價格（元/t）甲0.011600080乙0.052000070丙0.031800076表1-2分析：問題的目標是什么？通過三種煤的組合實現(xiàn)混合煤的價格最低問題目標實現(xiàn)的約束條件是什么？含硫量和發(fā)熱量現(xiàn)在是18頁\一共有150頁\編輯于星期三一、線性規(guī)劃模型實例（問題的提出）例1-2求解：設(shè)單位混合煤中甲、乙、丙三種煤的組合比例為x1：x2：x3因為是組合比例，所以有x1+x2+x3=1，且為非負。考慮約束條件：含硫量和發(fā)熱量有16000x1+20000x2+18000x3≧170000.01x1+0.05x2+0.03x3≦0.025該問題的目標是在滿足上述約束條件下使每噸混合煤的價格最低，用z來表示價格，則：z=80x1+70x2+76x3現(xiàn)在是19頁\一共有150頁\編輯于星期三一、線性規(guī)劃模型實例（問題的提出）例1-2求解：因此，該問題的數(shù)學(xué)模型為：目標函數(shù)約束條件現(xiàn)在是20頁\一共有150頁\編輯于星期三一、線性規(guī)劃模型實例（問題的提出）例1-3（運輸問題）假設(shè)某電力系統(tǒng)有三個火電廠B1、B2、B3，它們每月需燃料煤分別為10、20、25萬t。供應(yīng)這三個電廠燃料煤的煤礦有三個，即A1、A2、A3，它們每月分別可供該電力系統(tǒng)燃料煤15、25、15萬t。已知各煤礦到各電廠的運輸距離（單位km），如表1-3所示。問如何確定調(diào)運方案，使總的運輸量（總?cè)f噸公里數(shù)）最少？建立數(shù)學(xué)模型。現(xiàn)在是21頁\一共有150頁\編輯于星期三一、線性規(guī)劃模型實例（問題的提出）

電廠運距(km)煤礦B1B2B3A180100120A27012090A310080150表1-3現(xiàn)在是22頁\一共有150頁\編輯于星期三分析：問題是什么？如何確定調(diào)運方案，使總的運輸量（總?cè)f噸公里數(shù)）最少！調(diào)運方案如何理解？A1分別向B1、B2、B3三個電廠輸送多少萬t煤炭？A2分別向B1、B2、B3三個電廠輸送多少萬t煤炭？A3分別向B1、B2、B3三個電廠輸送多少萬t煤炭？總的運輸量（總?cè)f噸公里數(shù)）如何計算？各個煤礦向各個電廠輸送的煤的噸數(shù)×輸送的距離之和。有哪些約束條件？各火電廠的煤炭需要量和各煤礦的煤炭供給量現(xiàn)在是23頁\一共有150頁\編輯于星期三例1-3【解】：設(shè)煤礦Ai（i=1，2，3）每月供給電廠Bj（j=1，2，3）燃料煤xij萬t。該問題的目標是在滿足供需平衡的條件下使總運輸量最少。設(shè)z表示總運輸量，則該運輸問題的數(shù)學(xué)模型為：現(xiàn)在是24頁\一共有150頁\編輯于星期三自己動手試一試：某工廠要生產(chǎn)兩種新產(chǎn)品：門和窗。經(jīng)測算，每生產(chǎn)一扇門需要在車間1加工1小時、在車間3加工3小時；每生產(chǎn)一扇窗需要在車間2和車間3各加工2小時。而車間1每周可用于生產(chǎn)這兩種新產(chǎn)品的時間為4小時、車間2為12小時，車間3為18小時。已知每扇門的利潤為300元，每扇窗的利潤為500元。而且根據(jù)經(jīng)市場調(diào)查得到的這兩種產(chǎn)品的市場需求狀況可以確定，按當前的定價可確保所有新產(chǎn)品均能銷售出去。問該工廠如何安排這兩種產(chǎn)品的生產(chǎn)計劃，才能使總利潤最大？現(xiàn)在是25頁\一共有150頁\編輯于星期三自己動手試一試【解】兩種新產(chǎn)品的有關(guān)數(shù)據(jù)如表：車間單位產(chǎn)品的生產(chǎn)時間（小時）每周可獲得的生產(chǎn)時間（小時）門窗11042021233218單位利潤（元）300500現(xiàn)在是26頁\一共有150頁\編輯于星期三自己動手試一試【解】設(shè)x1為每周門的產(chǎn)量（扇），x2為每周窗的產(chǎn)量（扇）。線性規(guī)劃模型如下：現(xiàn)在是27頁\一共有150頁\編輯于星期三二、線性規(guī)劃問題的數(shù)據(jù)模型規(guī)劃問題的數(shù)學(xué)模型包含三個組成要素：（1）決策變量，指問題中要確定的未知量（2）目標函數(shù)，指問題所要達到的目標要求，表示為決策變量的函數(shù)（3）約束條件，指決策變量取值時應(yīng)滿足的一些限制條件，表示為含決策變量的等式或不等式如果在規(guī)劃問題的模型中，決策變量為可控變量，且取值是連續(xù)的，目標函數(shù)及約束條件都是線性的，這類模型叫做線性規(guī)劃模型。現(xiàn)在是28頁\一共有150頁\編輯于星期三二、線性規(guī)劃問題的數(shù)據(jù)模型1、線性規(guī)劃模型的一般表達形式（1）一般形式現(xiàn)在是29頁\一共有150頁\編輯于星期三決策變量及各類系數(shù)之間的對應(yīng)關(guān)系現(xiàn)在是30頁\一共有150頁\編輯于星期三二、線性規(guī)劃問題的數(shù)據(jù)模型1、線性規(guī)劃模型的一般表達形式（1）一般形式模型的簡寫形式為：現(xiàn)在是31頁\一共有150頁\編輯于星期三二、線性規(guī)劃問題的數(shù)據(jù)模型1、線性規(guī)劃模型的一般表達形式（1）一般形式（2）向量形式現(xiàn)在是32頁\一共有150頁\編輯于星期三二、線性規(guī)劃問題的數(shù)據(jù)模型1、線性規(guī)劃模型的一般表達形式（1）一般形式（2）向量形式（3）矩陣形式A為約束方程組（約束條件）的系數(shù)矩陣?，F(xiàn)在是33頁\一共有150頁\編輯于星期三二、線性規(guī)劃問題的數(shù)據(jù)模型2、線性規(guī)劃模型的標準形式為了研究問題的方便，規(guī)定線性規(guī)劃問題的標準形式為：現(xiàn)在是34頁\一共有150頁\編輯于星期三2、線性規(guī)劃模型的標準形式對標準形式的說明：（1）標準形式的線性規(guī)劃模型中的要求①目標函數(shù)為求最大值（有些文獻規(guī)定是求最小值）；②約束條件全為等式，約束條件右端常數(shù)項bi全為非負值；③變量xj的取值全為非負值。現(xiàn)在是35頁\一共有150頁\編輯于星期三2、線性規(guī)劃模型的標準形式（2）非標準形式的線性規(guī)劃問題轉(zhuǎn)化為標準形式的方法①目標函數(shù)為求最小值只需令z’=-z，則目標函數(shù)轉(zhuǎn)化為②約束條件為不等式當約束條件為“≦”時，例如2x1+2x2≦12可令x3=12-2x1-2x2或者2x1+2x2+x3=12。顯然，x3≧0，稱x3為松弛變量?，F(xiàn)在是36頁\一共有150頁\編輯于星期三2、線性規(guī)劃模型的標準形式（2）非標準形式的線性規(guī)劃問題轉(zhuǎn)化為標準形式的方法②約束條件為不等式當約束條件為“≧”時，例如10x1+12x2≧18可令x4=10x1+12x2-18或者10x1+12x2-x4=18。顯然，x4≧0，稱x4為剩余變量。松弛變量和剩余變量在實際問題中分別表示未被利用的資源數(shù)和短缺的資源數(shù)，均未轉(zhuǎn)化為價值和利潤。因此在目標函數(shù)中，松弛變量和剩余變量的系數(shù)均為零?，F(xiàn)在是37頁\一共有150頁\編輯于星期三2、線性規(guī)劃模型的標準形式（2）非標準形式的線性規(guī)劃問題轉(zhuǎn)化為標準形式的方法①目標函數(shù)為求最小值②約束條件為不等式③無約束變量。設(shè)x為無約束變量，則令無約束變量的實際含義：若變量x代表某產(chǎn)品當年計劃數(shù)與上一年計劃數(shù)之差，則x的取值可正可負。現(xiàn)在是38頁\一共有150頁\編輯于星期三二、線性規(guī)劃問題的數(shù)據(jù)模型例如1-4將下述線性規(guī)劃模型化為標準形式現(xiàn)在是39頁\一共有150頁\編輯于星期三二、線性規(guī)劃問題的數(shù)據(jù)模型例如1-4【解】：按規(guī)則將問題轉(zhuǎn)化為：X4為松弛變量X5為剩余變量現(xiàn)在是40頁\一共有150頁\編輯于星期三二、線性規(guī)劃問題的數(shù)據(jù)模型2、線性規(guī)劃模型的標準形式自己動手試一試：將下列線性規(guī)劃模型轉(zhuǎn)化為標準型?，F(xiàn)在是41頁\一共有150頁\編輯于星期三二、線性規(guī)劃問題的數(shù)據(jù)模型2、線性規(guī)劃模型的標準形式自己動手試一試：將下列線性規(guī)劃模型轉(zhuǎn)化為標準型現(xiàn)在是42頁\一共有150頁\編輯于星期三參考答案:現(xiàn)在是43頁\一共有150頁\編輯于星期三三、求解線性規(guī)劃模型的圖解法線性規(guī)劃模型的基本求解方法有：圖解法和單純形法。圖解法直觀明了，但是只適用于兩個變量的問題，目前常用的方法是單純形法。1、圖解法的步驟：第1步：建立坐標系，畫出由約束條件所確定的區(qū)域第2步：對任意確定的z，畫出目標函數(shù)所代表的直線第3步：平移目標函數(shù)直線，確定最優(yōu)解。現(xiàn)在是44頁\一共有150頁\編輯于星期三三、求解線性規(guī)劃模型的圖解法2、圖解法的實例例1-5用圖解法求最優(yōu)解現(xiàn)在是45頁\一共有150頁\編輯于星期三2、圖解法的實例例1-5用圖解法求最優(yōu)解（1）先分析約束條件是如何圖示的。x1x2Q4Q3Q2Q1現(xiàn)在是46頁\一共有150頁\編輯于星期三2、圖解法的實例例1-5用圖解法求最優(yōu)解（1）先分析約束條件是如何圖示的。x1x2Q4Q3(3,3)Q2(4,2)Q1從圖形中我們看到陰影部分的圖形是凸的，以后我們要證明，如果線性規(guī)劃問題存在可行域，則可行域一定是一個凸集?，F(xiàn)在是47頁\一共有150頁\編輯于星期三2、圖解法的實例例1-5用圖解法求最優(yōu)解（2）目標函數(shù)的幾何意義。目標函數(shù)maxz=2x1+3x2，z是待定的值，將函數(shù)改寫為x2=-2/3x1+z/3，由解析幾何知，這是變量為z、斜率為-2/3的一族平行的直線。如圖！這族平行線中，離原點越遠的直線，z的直線越大。若對x1、x2的取值無限制，z的值可以無限增大。但在線性規(guī)劃問題中，對x1、x2的取值范圍是有限制?，F(xiàn)在是48頁\一共有150頁\編輯于星期三2、圖解法的實例例1-5用圖解法求最優(yōu)解（2）目標函數(shù)的幾何意義。x1x2Z=6現(xiàn)在是49頁\一共有150頁\編輯于星期三2、圖解法的實例例1-5用圖解法求最優(yōu)解（3）最優(yōu)解的確定。最優(yōu)解必須滿足約束條件的要求，并使目標函數(shù)達到最優(yōu)值。因此x1、x2的取值范圍只能從凸多邊形OQ1Q2Q3Q4中去尋找。從圖中看到，當代表目標函數(shù)的直線和約束條件包圍成的凸多邊形相切時為止，切點就代表最優(yōu)解的點。思考：為什么z直線不能繼續(xù)向右上方移動？現(xiàn)在是50頁\一共有150頁\編輯于星期三x1x2Q4Q3(3,3)Q2(4,2)Q12、圖解法的實例例1-5用圖解法求最優(yōu)解（3）最優(yōu)解的確定。例1-5中目標函數(shù)直線與凸多邊形的切點是Q3，該點的坐標（3，3），將其代入到目標函數(shù)得z=15?，F(xiàn)在是51頁\一共有150頁\編輯于星期三2、圖解法的實例例1-6將例1-5中的目標函數(shù)maxz=2x1+3x2改為maxz=3x1+3x2，則線性規(guī)劃問題的最優(yōu)解為？最優(yōu)解為Q3Q2上的所有點，因此此問題有無窮多個最優(yōu)解。x1x2Q4Q3(3,3)Q2(4,2)Q1現(xiàn)在是52頁\一共有150頁\編輯于星期三2、圖解法的實例例1-6我們看到目標函數(shù)的圖形恰好與約束條件（1）平行。當目標函數(shù)直線向右上方移動時，他與凸多邊形相切時不是一個點，而是在整個線段Q2Q3上相切。這時在Q2點、Q3點及Q2Q3線段上的任意點都是目標函數(shù)值z達到最大，即該線性規(guī)劃問題有無窮多最優(yōu)解，也稱具有多重最優(yōu)解?，F(xiàn)在是53頁\一共有150頁\編輯于星期三2、圖解法的實例例1-7用圖解法求下列線性規(guī)劃問題的最優(yōu)解x1x2如圖：此問題有可行域，但為無界解（無最優(yōu)解）其原因是由于在建立實際問題的數(shù)學(xué)模型時遺漏了某些必要的資源約束?，F(xiàn)在是54頁\一共有150頁\編輯于星期三2、圖解法的實例例1-8用圖解法求下列線性規(guī)劃問題的最優(yōu)解x1x2用圖解法求解時找不到滿足所有約束條件的公共范圍，這時此問題無可行解。原因是模型本身有錯誤，約束條件相互矛盾，應(yīng)檢查修正。現(xiàn)在是55頁\一共有150頁\編輯于星期三圖解法的解題思路和幾何上直觀得到的一些概念判斷，對求解一般線性規(guī)劃問題的單純形法有很大的啟示：（1）求解線性規(guī)劃問題時，解的情況有：惟一最優(yōu)解、無窮多最優(yōu)解、無界解、無可行解；（2）若線性規(guī)劃問題的可行域存在，則可行域是一個凸集（凸多邊形，稍后介紹）；（3）若線性規(guī)劃問題的最優(yōu)解存在，則最優(yōu)解或最優(yōu)解之一（如果有無窮多的話）一定能夠在可行域（凸集）的某個頂點找到；現(xiàn)在是56頁\一共有150頁\編輯于星期三三、求解線性規(guī)劃模型的圖解法（4）解題思路是：先找出凸集的任一頂點，計算在頂點處的目標函數(shù)值。比較周圍相鄰頂點的目標函數(shù)值是否比這個值更優(yōu)，如果為否，則該頂點就是最優(yōu)解的點或最優(yōu)解的點之一，否則轉(zhuǎn)到比這個點的目標函數(shù)值更優(yōu)的另一個頂點，重復(fù)上述過程，一直到找出使目標函數(shù)值達到最優(yōu)的頂點為止。圖解法雖然直觀、簡便，但是當變量數(shù)大于兩個時，它就無能為力了。引入單純形法！現(xiàn)在是57頁\一共有150頁\編輯于星期三四、單純形法1、預(yù)備知識：凸集和頂點2、線性規(guī)劃問題的解3、幾個基本定理（不要求證明）4、單純形法求解線性規(guī)劃5、單純形法的計算步驟現(xiàn)在是58頁\一共有150頁\編輯于星期三四、單純形法單純形法是求解一般線性規(guī)劃問題的基本方法，是1947年由丹齊格（）提出。1、預(yù)備知識：凸集和頂點①凸集：對一個給定的幾何圖形，通常可從直觀上判斷其凹凸性。但容易產(chǎn)生錯誤。凸集的嚴格定義：如果集合C中任意兩個點X1、X2，其連線上的所有的點也都是集合C中的點，稱C為凸集?，F(xiàn)在是59頁\一共有150頁\編輯于星期三四、單純形法1、預(yù)備知識：凸集和頂點①凸集：因為X1、X2的連線可表示為：

aX1+（1-a）X2（0<a<1）所以凸集定義用數(shù)學(xué)語言表示為：對任何X1∈C，X2∈C，有aX1+（1-a）X2∈C（0<a<1），則稱C為凸集?，F(xiàn)在是60頁\一共有150頁\編輯于星期三1、預(yù)備知識：凸集和頂點①凸集判斷下列幾何圖形是否是凸集？（a）（b）（c）（d）現(xiàn)在是61頁\一共有150頁\編輯于星期三四、單純形法1、預(yù)備知識：凸集和頂點①凸集：②頂點凸集C中滿足下述條件的點X稱為頂點：如果C中不存在任何兩個不同的點X1、X2，使X成為這兩個點連線上的一個點。對任何X1∈C，X2∈C，不存在X=aX1+（1-a）X2（0<a<1），則稱X是凸集C的頂點。解釋：頂點是不會出現(xiàn)在集合C中任意兩點之間的連線上?，F(xiàn)在是62頁\一共有150頁\編輯于星期三四、單純形法2、線性規(guī)劃問題的解假設(shè)所要研究的線性規(guī)劃模型的形式為：求解線性規(guī)劃問題，就是滿足約束條件（b）、（c）的方程組中找出一個解，使目標函數(shù)（a）達到最大值。（a）（b）（c）現(xiàn)在是63頁\一共有150頁\編輯于星期三（a）（b）（c）四、單純形法（1）可行解滿足上述約束條件（b）、（c）的解X=（x1，…，xn）T

稱為線性規(guī)劃問題的可行解，全部可行解的集合稱為可行域。（2）最優(yōu)解使目標函數(shù)（a）達到最大值的可行解稱為最優(yōu)解。2、線性規(guī)劃問題的解現(xiàn)在是64頁\一共有150頁\編輯于星期三（3）基設(shè)A為約束方程組（b）的m×n階系數(shù)矩陣（設(shè)n>m），其秩為m。B是矩陣A中的一個m×m階的滿秩子矩陣，稱B是線性規(guī)劃問題的一個基。不失一般性，設(shè)B中的每一個列向量Pj（j=1,…,m）稱為基向量，與基向量Pj對應(yīng)的變量xj稱為基變量。線性規(guī)劃中除基變量以外的其他變量稱為非基變量?；蛄楷F(xiàn)在是65頁\一共有150頁\編輯于星期三回顧：矩陣的秩的定義定義:如果數(shù)域F

上的m

n

矩陣存在一個k

階子式不為零，并且所有的k+1階子式全為零，則稱A

秩為k

，記作r(A)=k.顯然，r(A)min(m,n);r(AT)=r(A).現(xiàn)在是66頁\一共有150頁\編輯于星期三例求矩陣A

的秩，其中

解:在A中，容易看出２階子式而A

的三階子式只有一個｜Ａ｜因此現(xiàn)在是67頁\一共有150頁\編輯于星期三（3）基例1-9已知線性規(guī)劃求所有基矩陣。現(xiàn)在是68頁\一共有150頁\編輯于星期三【解】：約束方程的系數(shù)矩陣為2×5矩陣：容易看出r（A）=2，2階子矩陣有C25=10個，其中第1列與第3列構(gòu)成的2階矩陣不是一個基，因此基矩陣只有9個，即：由線性代數(shù)知道，基矩陣B必為非奇異矩陣，即|B|≠0。當矩陣B的行列式等于零是就不是基。現(xiàn)在是69頁\一共有150頁\編輯于星期三根據(jù)：B中的每一個列向量Pj（j=1,…,m）稱為基向量，與基向量Pj對應(yīng)的變量xj稱為基變量。線性規(guī)劃中除基變量以外的其他變量稱為非基變量。請指出例1-9中B2的基向量、基變量和非基變量。B2的基向量是A中的第一列和第四列B2的基變量是x1和x4B2的非基變量是x2、x3和x5。基變量和非基變量是針對某一確定的基而言的，不同的基對應(yīng)的基變量和非基變量是不相同的。現(xiàn)在是70頁\一共有150頁\編輯于星期三（a）（b）（c）四、單純形法（4）基本解在約束方程組（b）中，令所有非基變量xm+1=xm+2=…=xn=0,又因為有|B|≠0，根據(jù)克拉默規(guī)則，由m個約束方程可解出m個基變量的惟一解XB=（x1，…，xm）。這個解加上非基變量取0的值有X=（x1，x2，…，xm，0，…，0）T，稱為線性規(guī)劃問題的基解。顯然在基解中變量取非零值的個數(shù)不大于方程數(shù)m，又基解的總數(shù)不超過Cnm個。2、線性規(guī)劃問題的解對某一特定的基B，令非基變量等于零，利用（b）求解出基變量，則這組解成為基B的基本解?，F(xiàn)在是71頁\一共有150頁\編輯于星期三定理(克拉默法則)

如果含有n

個方程的n

元線性方程組現(xiàn)在是72頁\一共有150頁\編輯于星期三的系數(shù)行列式則方程組(1)有唯一解，并且其中detBj

是將系數(shù)行列式detA

的第j

列元a1j,a2j,…,anj,換成常數(shù)項b1,b2,…,bn后得到的行列式.現(xiàn)在是73頁\一共有150頁\編輯于星期三（a）（b）（c）四、單純形法（5）基本可行解滿足變量非負約束條件（c）的基解稱為基可行解。（6）可行基對應(yīng)于基可行解的基稱為可行基（7）最優(yōu)基基本最優(yōu)解對應(yīng)的基稱為最優(yōu)基2、線性規(guī)劃問題的解現(xiàn)在是74頁\一共有150頁\編輯于星期三例1-9中對于B1來說，x1、x2是基變量，x3、x4、x5是非基變量，令x3=x4=x5=0，則因|B|≠0，由克萊姆法則知，X1、x2有惟一解，解得x1=2/5，x2=1則基本解為X（1）=現(xiàn)在是75頁\一共有150頁\編輯于星期三例1-9中對于B2來說，x1、x4是基變量，x2、x3、x5是非基變量，令x2=x3=x5=0，則因|B|≠0，由克萊姆法則知，X1、x4有惟一解，解得x1=-1/5，x4=4則基本解為X（2）=現(xiàn)在是76頁\一共有150頁\編輯于星期三滿足非負約束條件，所以它是基本可行解；不滿足非負約束條件，所以它不是可行解，也不是基本可行解；注意：可行解不一定是基本可行解。例滿足約束方程和非負約束，因此是可行解，但它不是任何基矩陣的基本解。對應(yīng)的基B1稱為可行基現(xiàn)在是77頁\一共有150頁\編輯于星期三基本最優(yōu)解、最優(yōu)解、基本可行解、基本解和可行解的關(guān)系如圖表示：基本最優(yōu)解基本可行解最優(yōu)解基本解可行解箭尾的解一定是箭頭的解，否則不一定成立現(xiàn)在是78頁\一共有150頁\編輯于星期三四、單純形法1、預(yù)備知識：凸集和頂點2、線性規(guī)劃問題的解3、幾個基本定理（不要求證明）定理1：若線性規(guī)劃問題存在可行解，則問題的可行域是凸集。定理1描述了可行解集的特征。現(xiàn)在是79頁\一共有150頁\編輯于星期三四、單純形法3、幾個基本定理定理2：線性規(guī)劃問題的基可行解X對應(yīng)線性規(guī)劃問題可行域（凸集）的頂點。定理2描述了可行解集的頂點與基本可行解的對應(yīng)關(guān)系，頂點是基本可行解；反之，基本可行解在頂點上。但它們并非一一對應(yīng)，可能有兩個或幾個基本可行解對應(yīng)于同一個頂點。定理3：若線性規(guī)劃問題有最優(yōu)解，一定存在一個基可行解是最優(yōu)解?，F(xiàn)在是80頁\一共有150頁\編輯于星期三四、單純形法2、線性規(guī)劃問題的解例1-10在下述線性規(guī)劃問題中，列出全部基、基解、基可行解和指出最優(yōu)解。標準型現(xiàn)在是81頁\一共有150頁\編輯于星期三例1-10解寫出約束方程組的系數(shù)矩陣P1P2P3P4P5矩陣A的秩≦3。所以只要找出3個列向量組成的矩陣滿秩，這3個向量就是線性規(guī)劃問題的一個基?，F(xiàn)在是82頁\一共有150頁\編輯于星期三例1-10解寫出約束方程組的系數(shù)矩陣P1P2P3P4P5令與基對應(yīng)的變量為基變量，其余變量為非基變量，令非基變量等于零，求解方程組就可以找出基解。下表中列出本線性規(guī)劃問題的全部基、基解?，F(xiàn)在是83頁\一共有150頁\編輯于星期三基基解基可行解？目標函數(shù)值x1x2x3x4x5P1P2P343-200否17P1P2P433040是15P1P2P542005是14P1P3P5404015是8P1P4P5600-815否12P2P3P4036160是9P2P4P506016-15否18P3P4P500121615是0例1-10表現(xiàn)在是84頁\一共有150頁\編輯于星期三基本結(jié)論：線性規(guī)劃問題的所有可行解構(gòu)成的集合是凸集，也可能為無界域，它們有有限個頂點，線性規(guī)劃問題的每個基可行解對應(yīng)可行域的一個頂點。若線性規(guī)劃問題有最優(yōu)解，必在某頂點上得到。雖然頂點數(shù)目是有限的，若采用“枚舉法”找所有基可行解，然后一一比較，最終必然能找到最優(yōu)解。但當n,m較大時，這種辦法是行不通的，所以要繼續(xù)討論如何有效尋找最優(yōu)解的方法。我們將主要介紹單純形法。現(xiàn)在是85頁\一共有150頁\編輯于星期三四、單純形法4、單純形法求解線性規(guī)劃通過示例來了解單純形法求解線性規(guī)劃?，F(xiàn)在是86頁\一共有150頁\編輯于星期三單純形法示例：例1-11

某工廠在計劃期內(nèi)要安排生產(chǎn)Ⅰ、Ⅱ兩種產(chǎn)品，已知生產(chǎn)單位產(chǎn)品所需的設(shè)備臺時及A、B兩種原材料的消耗，如表所示。如何用單純形法求解下列標準線性規(guī)化數(shù)學(xué)模型。每生產(chǎn)一件產(chǎn)品Ⅰ可獲利2元，每生產(chǎn)一件產(chǎn)品Ⅱ可獲利3元，問應(yīng)如何安排計劃使該工廠獲利最多?

產(chǎn)品資源III擁有量設(shè)備128臺時原材料A4016kg原材料B0412kg現(xiàn)在是87頁\一共有150頁\編輯于星期三例1-11【解】設(shè)x1和x2分別表示計劃生產(chǎn)產(chǎn)品I和產(chǎn)品II的數(shù)量。建立的線性規(guī)劃數(shù)學(xué)模型如下：現(xiàn)在是88頁\一共有150頁\編輯于星期三約束條件例1-11【解】將上頁的線性規(guī)劃模型轉(zhuǎn)換成標準型如下：現(xiàn)在是89頁\一共有150頁\編輯于星期三約束方程的系數(shù)矩陣從式中可以看到x3,x4,x5的系數(shù)列向量現(xiàn)在是90頁\一共有150頁\編輯于星期三P3,P4,P5是線性獨立的，這些向量構(gòu)成一個基從(1-2)式中可以得到（1-3）對應(yīng)于B的變量x3,x4,x5為

基變量，x1、x2為非基變量現(xiàn)在是91頁\一共有150頁\編輯于星期三將(1-3)式代入目標函數(shù)(1-1)得到令非基變量x1=x2=0，便得到z=0。這時得到一個基可行解X(0)=(0,0,8,16,12)T

這個基可行解表示：工廠沒有安排生產(chǎn)產(chǎn)品Ⅰ、Ⅱ；資源都沒有被利用，所以工廠的利潤指標z=0。到這里，完成了單純形法的第一個環(huán)節(jié)：確定初始基本可行解；然后再確定這個基本可行解是否是最優(yōu)的，如果不是，則還要繼續(xù)去尋找最優(yōu)解！現(xiàn)在是92頁\一共有150頁\編輯于星期三下面進行最優(yōu)性的檢驗！從分析目標函數(shù)的表達式(1-4)可以看到：非基變量x1,x2(即沒有安排生產(chǎn)產(chǎn)品Ⅰ，Ⅱ)的系數(shù)都是正數(shù)，因此將非基變量變換為基變量，目標函數(shù)的值就可能增大。從經(jīng)濟意義上講，安排生產(chǎn)產(chǎn)品Ⅰ或Ⅱ，就可以使工廠的利潤指標增加。所以只要在目標函數(shù)(1-4)的表達式中還存在有正系數(shù)的非基變量，這表示目標函數(shù)值還有增加的可能，當前的基本可行解還不是最優(yōu)解。因此，最優(yōu)解否定后，又要去尋找新的基本可行解，這就需要將非基變量與基變量進行對換。現(xiàn)在是93頁\一共有150頁\編輯于星期三如何確定換入，換出變量？一般選擇正系數(shù)最大的那個非基變量x2為換入變量，將它換入到基變量中去，同時還要確定基變量中有一個要換出來成為非基變量，可按以下方法來確定換出變量?，F(xiàn)分析(1-3)式，當將x2定為換入變量后，必須從x3,x4,x5中確定一個換出變量，并保證其余的都是非負，即x3,x4,x5≥0?，F(xiàn)在是94頁\一共有150頁\編輯于星期三當x1=0,由(1-3)式得到現(xiàn)在是95頁\一共有150頁\編輯于星期三x2取何值時，才能滿足非負要求？從(1-5)式中可以看出，只有選擇x2=min(8/2,12/4)=3時，才能使(1-5)式成立。因當x2=3時，基變量x5=0，這就決定用x2去替換x5。以上數(shù)學(xué)描述說明了每生產(chǎn)一件產(chǎn)品Ⅱ，需要用掉各種資源數(shù)為(2，0，4)。由這些資源中的薄弱環(huán)節(jié)，就確定了產(chǎn)品Ⅱ的產(chǎn)量。這里就是由原材料B的數(shù)量確定了產(chǎn)品Ⅱ的產(chǎn)量x2=12/4=3件?，F(xiàn)在是96頁\一共有150頁\編輯于星期三為了求得以x3,x4,x2為基變量的一個基可行解和進一步分析問題，需將(1-3)中x2的位置與x5的位置對換。得到現(xiàn)在是97頁\一共有150頁\編輯于星期三用高斯消去法將(1-6)式中x2的系數(shù)列向量變換為單位列向量。其運算步驟是：③′=③/4；①′=①-2×③′;②′=②,并將結(jié)果仍按原順序排列有：現(xiàn)在是98頁\一共有150頁\編輯于星期三再將(1-7)式代入目標函數(shù)(1-1)式得到令非基變量x1=x5=0，得到z=9，并得到另一個基可行解X（1）X（1）=（0，3，2，16，0）T現(xiàn)在是99頁\一共有150頁\編輯于星期三從目標函數(shù)的表達式(1-8)中可以看到，非基變量x1的系數(shù)是正的，說明目標函數(shù)值還可以增大，X(1)還不是最優(yōu)解。于是再用上述方法，確定換入、換出變量，繼續(xù)迭代，再得到另一個基可行解X(2)X(2)=(2,3,0,8,0)T再經(jīng)過一次迭代，再得到一個基可行解X(3)X(3)=(4,2,0,0,4)T而這時得到目標函數(shù)的表達式是：z=14-1.5x3-0.125x4(1-9)現(xiàn)在是100頁\一共有150頁\編輯于星期三z=14-1.5x3-0.125x4(1-9)再檢查(1-9)式，可見到所有非基變量x3,x4的系數(shù)都是負數(shù)。這說明若要用剩余資源x3,x4，就必須支付附加費用。所以當x3=x4=0時，即不再利用這些資源時，目標函數(shù)達到最大值。所以X(3)是最優(yōu)解。即當產(chǎn)品Ⅰ生產(chǎn)4件，產(chǎn)品Ⅱ生產(chǎn)2件，工廠才能得到最大利潤?，F(xiàn)在是101頁\一共有150頁\編輯于星期三四、單純形法4、單純形法求解線性規(guī)劃再引入一實例，介紹利用單純形法求解線性規(guī)劃時可以使用的一種工具，即單純形表。例1-12用單純形法求解下列線性規(guī)劃的最優(yōu)解現(xiàn)在是102頁\一共有150頁\編輯于星期三例1-12【解】化為標準型為：約束方程的系數(shù)矩陣A為：現(xiàn)在是103頁\一共有150頁\編輯于星期三例1-12【解】確定初始基和基變量、非基變量、初始基本可行解?；兞繛椋簒3，x4非基變量為：x1，x2令非基變量x1=x2=0，代入約束方程中得到：x3=40，x4=30則初始基本可行解為：X（0）=（0，0，40，30）T現(xiàn)在是104頁\一共有150頁\編輯于星期三例1-12【解】以上得到的一組基本可行解是否是最優(yōu)解?從目標函數(shù)z=3x1+4x2中看出：X1和x2的系數(shù)大于零，如果x1和x2為一個正數(shù)，那么目標值就能夠變得更大。因此，只要非基變量的系數(shù)大于零，那么目標函數(shù)就沒有達到最大，即沒有找到最優(yōu)解。判別線性規(guī)劃問題是否達到最優(yōu)解的數(shù)稱為檢驗數(shù)，記作λj（j=1，2，…，n）。在例1-11中λ1=3，λ2=4，λ3=0，λ4=0。檢驗數(shù)：目標函數(shù)用非基變量表示，其變量的系數(shù)為檢驗數(shù)現(xiàn)在是105頁\一共有150頁\編輯于星期三下面，我們要引入一個工具，來幫助我們利用單純形法來求解線性規(guī)劃，這個工具是單純形表。根據(jù)以上得到的結(jié)果，我們可以建立初始的單純形表。cj3400θi(min)CBXBx1x2x3x4b0x32110400x4130130λj(max)34000基變量的檢驗數(shù)為零現(xiàn)在是106頁\一共有150頁\編輯于星期三因為X（0）不是最優(yōu)解，因此我們就要繼續(xù)尋找下一個基解，并判斷它是否是最優(yōu)解。所以我們需要對已經(jīng)得到的基解進行改進，改進的方法是：換基變量。（1）確定換入變量（進基變量）方法：λk=max{λj|λj>0}（2）確定換出變量（出基變量）方法：θk=min{θi=bi/aik|aik>0}現(xiàn)在是107頁\一共有150頁\編輯于星期三cj3400θi(min)CBXBx1x2x3x4b0x32110400x4130130λj(max)34000換入變量為：x2那么換出變量為x3還是x4呢？確定換出變量為x440/130/3現(xiàn)在是108頁\一共有150頁\編輯于星期三cj3400θi(min)CBXBx1x2x3x4b0x32110400x4130130λj(max)34000換入變量為：x2;換出變量為x4初始單純形表變更為：40/130/3X2希望變成1希望變成0這樣，形成的基就是單位矩陣。因此，對增廣矩陣進行初等變換！

4現(xiàn)在是109頁\一共有150頁\編輯于星期三cj3400θi(min)CBXBx1x2x3x4b0x32110404x2130130λj(max)34000換入變量為：x2;換出變量為x4初始單純形表變更為：4010增廣矩陣的第2行中的每個元素都÷3得：如圖所示1/311/310增廣矩陣的第1行-第2行得：如圖所示5/3

0-1/330經(jīng)過增廣矩陣的初等變換后，基變成了單位矩陣現(xiàn)在是110頁\一共有150頁\編輯于星期三cj3400θi(min)CBXBx1x2x3x4b0x35/301-1/3304x21/3101/310λj(max)340004010確定基可行解X（1）=？令非基變量x1=x4=0，基變量x2=10，x3=30所以X（1）=（0，10，30，0）T基可行解是否是最優(yōu)解？依據(jù)檢驗數(shù)定義：目標函數(shù)用非基變量表示，其變量的系數(shù)為檢驗數(shù)。因此需要將基變量的λ變換為0因為λ3=0了，所以只需要將λ2變換為0。方法：矩陣的第3行-第2行×4-40

05/3-4/3現(xiàn)在是111頁\一共有150頁\編輯于星期三cj3400θi(min)CBXBx1x2x3x4b0x35/301-1/3304x21/3101/310λj(max)5/300-4/3-40得出：X（1）=（0，10，30，0）T不是最優(yōu)解下一步：確定換入變量和換出變量請大家自己運算，直到確定最優(yōu)解。3018x13現(xiàn)在是112頁\一共有150頁\編輯于星期三cj3400θi(min)CBXBx1x2x3x4b3x15/301-1/330184x21/3101/31030λj(max)5/300-4/3-40將基（P1P2）初等變換為單位矩陣方法：①÷5/3②-①×1/3確定基本可行解X（2）=（18，4，0，0）T最優(yōu)性性判斷？③-①×5/3看到所有的檢驗數(shù)都小于0，所以X（2）是最優(yōu)解同時目標函數(shù)值為70

13/5-1/518

0-1/52/54

0

-1

-1

-70-z現(xiàn)在是113頁\一共有150頁\編輯于星期三練習(xí)：將例1-11用單純形表求解。練習(xí)：單純形法求解（1）現(xiàn)在是114頁\一共有150頁\編輯于星期三小結(jié)單純形法是求解線性規(guī)劃問題的一種極為有效和方便的方法，用單純形法時一定要注意以下幾個問題：第一：要將問題化為標準型第二：迭代過程進行的應(yīng)是線性變換；第三：判斷是否為最優(yōu)解的標準，即對極大化問題，檢驗數(shù)應(yīng)為非正；大家思考：對極小化問題，檢驗數(shù)應(yīng)為什么？對極小化問題，檢驗數(shù)應(yīng)為非負?，F(xiàn)在是115頁\一共有150頁\編輯于星期三例1-13單純形法求解現(xiàn)在是116頁\一共有150頁\編輯于星期三以上我們討論的是有惟一最優(yōu)解的情況，如果最優(yōu)解有無窮多個，求解的過程是怎樣的呢？例1-14現(xiàn)在是117頁\一共有150頁\編輯于星期三例1-14【解】化為標準型為：現(xiàn)在是118頁\一共有150頁\編輯于星期三cj24000θi(min)CBXBx1x2x3x4x5b0x3-1210040x412010100x51-10012λj(max)初始單純形表如下：X（0）=（0，0，4，10，2）T240000判斷是否最優(yōu)？不是最優(yōu)！換基方案？換入變量：x2，25換出變量：x3現(xiàn)在是119頁\一共有150頁\編輯于星期三cj24000θi(min)CBXBx1x2x3x4x5b4x2-1210040x412010100x51-10012λj(max)240000經(jīng)初等變換，將（P2，P4，P5）變換為單位矩陣判斷是否最優(yōu)？-1/2

21/2

1

0

01/2

-11/2基本解為X（1）=（0，2，0，6，4）T

2

6

4不是最優(yōu)解！

4

0

-2

-8換基方案？換入變量：x1，

3

8換出變量：x4現(xiàn)在是120頁\一共有150頁\編輯于星期三cj24000θi(min)CBXBx1x2x3x4x5b4x2-1/211/20022x120-11060x51/201/2014λj(max)40-200-8經(jīng)初等變換，將（P1，P2，P5）變換為單位矩陣判斷是否最優(yōu)？基本解為X（2）=（3，7/2，0，0，5/2）T是最優(yōu)解！

0

1

0

1/4-1/23/4

1/41/2-1/4

7/2

3

5/2

-2-20

0

0目標函數(shù)值為z=20但是這時，非基變量x3的檢驗數(shù)為零，表示原問題還有其他的最優(yōu)解，也就是說這是多重最優(yōu)解的情況。還可以進一步迭代！現(xiàn)在是121頁\一共有150頁\編輯于星期三cj24000θi(min)CBXBx1x2x3x4x5b4x2011/41/407/22x110-1/21/2030x5003/4-1/415/2λj(max)000-20-20換基方案？換入變量：x3，換出變量：x5

14

10/3

x3經(jīng)初等變換，將（P1，P2，P3）變換為單位矩陣基本解為X（3）=（14/3，8/3，10/3，0，0）T

1

0

01/31/3-1/3-1/32/34/38/314/310/3基本解為X（3）是最優(yōu)解！目標函數(shù)值z=20現(xiàn)在是122頁\一共有150頁\編輯于星期三小結(jié)該例是有無窮多最優(yōu)解（多重解）的線性規(guī)劃問題，單純形表中的檢驗數(shù)除了基變量的檢驗數(shù)為零外，還有非基變量的檢驗數(shù)也為零。該例的迭代過程中還需注意在用最小比值法則時，要求分母大于0，即當系數(shù)矩陣中對應(yīng)的向量小于等于零時，則不需要計算比值，所以對應(yīng)的變量也不是出基變量。現(xiàn)在是123頁\一共有150頁\編輯于星期三例1-15現(xiàn)在是124頁\一共有150頁\編輯于星期三cj2200θi(min)CBXBx1x2x3x4b0x3-111010x4-0.51012λj(max)2200因為問題是最大化問題，這時非基變量x1的檢驗數(shù)=2（>0），可以作為進基變量，但是增廣矩陣中x1對應(yīng)的系數(shù)都小于0，所以目標函數(shù)無上界，問題無最優(yōu)解！現(xiàn)在是125頁\一共有150頁\編輯于星期三小結(jié)本例是無最優(yōu)解的線性規(guī)劃問題。在計算過程中，一定要注意：若某個檢驗數(shù)對應(yīng)的變量的系數(shù)都小于等于零，則此問題無界，停止計算。同時要注意：無最優(yōu)解并不代表無可行解；無界解是有可行解的，但沒有最優(yōu)解?，F(xiàn)在是126頁\一共有150頁\編輯于星期三四、單純形法1、預(yù)備知識：凸集和頂點2、線性規(guī)劃問題的解3、幾個基本定理（不要求證明）4、單純形法求解線性規(guī)劃5、單純形法的計算步驟現(xiàn)在是127頁\一共有150頁\編輯于星期三四、單純形法5、單純形法的計算步驟（1）將線性規(guī)劃問題轉(zhuǎn)換為標準型（2）求初始基本可行解（3）通過計算檢驗數(shù)判斷基本可行解是否為最優(yōu)若所有檢驗數(shù)都小于等于零，則得到最優(yōu)解若某個檢驗數(shù)大于零，但對應(yīng)變量系數(shù)都小于等于零，則線性規(guī)劃有無界解若存在檢驗數(shù)大于零，而且對應(yīng)變量的系數(shù)不全為負，則進行換基現(xiàn)在是128頁\一共有150頁\編輯于星期三5、單純形法的計算步驟（1）將線性規(guī)劃問題轉(zhuǎn)換為標準型（2）求初始基本可行解（3）通過計算檢驗數(shù)判斷基本可行解是否為最優(yōu)（4）換基選進基變量：選擇檢驗數(shù)最大的變量選出基變量：最小比值法則（5）求新的基本可行解：用初等變換將aLK化為1，k列其他元素化為零（基向量成單位矩陣），再判斷是否得到最優(yōu)現(xiàn)在是129頁\一共有150頁\編輯于星期三五、單純形法的進一步討論在實際問題中有些模型并不含有單位矩陣，為了得到一組基向量和初基可行解，在約束條件的等式左端加一組虛擬變量，得到一組基變量。這種人為加的變量稱為人工變量，構(gòu)成的可行基稱為人工基，用大M法或兩階段法求解，這種用人工變量作橋梁的求解方法稱為人工變量法。1、人工變量法（大M法）2、兩階段法現(xiàn)在是130頁\一共有150頁\編輯于星期三五、單純形法的進一步討論1、人工變量法（大M法）（1）人工變量法的思路當線性規(guī)劃問題的約束條件是等式，而系數(shù)矩陣中又不包含有單位矩陣時，采用人工變量法在約束條件左端加上一個人工變量，從而人為地構(gòu)造一個單位基矩陣。若約束條件是“≧”的情況，先在不等式左端減去一個大于等于零的剩余變量（松弛變量）轉(zhuǎn)化為等式約束。然后，為了構(gòu)造一個單位矩陣，在約束條件左端再加上一個人工變量?，F(xiàn)在是131頁\一共有150頁\編輯于星期三1、人工變量法（大M法）（2）目標函數(shù)的變化在一個線性規(guī)劃問題的約束條件中加入人工變量后，要求人工變量對目標函數(shù)值沒有影響，因此人工變量在目標函數(shù)中的系數(shù)應(yīng)為“-M”（M為任意大的正數(shù)）。這樣，在目標函數(shù)要實現(xiàn)最大化時，必須把人工變量從基變量中置換出來，否則，目標函數(shù)不可能實現(xiàn)最大化，也即原線性規(guī)劃問題無可行解?，F(xiàn)在是132頁\一共有150頁\編輯于星期三1、人工變量法（大M法）例1-16用大M法求解線性規(guī)劃問題。（1）將問題化成標準形式。系數(shù)矩陣A為：系數(shù)矩陣A中不包含單位矩陣，因此增加人工變量去構(gòu)造單位矩陣，但增加的人工變量不能影響目標函數(shù)。現(xiàn)在是133頁\一共有150頁\編輯于星期三1、人工變量法（大M法）例1-16用大M法求解線性規(guī)劃問題。(1)將問題化成標準形式。(2)增加人工變量?，F(xiàn)在是134頁\一共有150頁\編輯于星期三1、人工變量法（大M法）例1-16用大M法求解線性規(guī)劃問題。系數(shù)矩陣A為：有1單位子矩陣系數(shù)為負數(shù)，我們知道在換基時，會把它們置換出來，這樣就不會影響目標函數(shù)了現(xiàn)在是135頁\一共有150頁\編輯于星期三五、單純形法的進一步討論1、人工變量法（大M法）例1-16用大M法求解線性規(guī)劃問題。接下來，用單純形法求解線性規(guī)劃模型?，F(xiàn)在是136頁\一共有150頁\編輯于星期三cj32-100-M-MCBXBx1x2x3x4x5x6x7b-Mx6-431-101040x51-12010010-Mx72-2100011λj(max