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

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

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

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

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

上的m

n

矩陣存在一個(gè)k

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

秩為k

，記作r(A)=k.顯然，r(A)min(m,n);r(AT)=r(A).當(dāng)前66頁，總共150頁。例求矩陣A

的秩，其中

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

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

如果含有n

個(gè)方程的n

元線性方程組當(dāng)前72頁，總共150頁。的系數(shù)行列式則方程組(1)有唯一解，并且其中detBj

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

的第j

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

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

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

基變量，x1、x2為非基變量當(dāng)前91頁，總共150頁。將(1-3)式代入目標(biāo)函數(shù)(1-1)得到令非基變量x1=x2=0，便得到z=0。這時(shí)得到一個(gè)基可行解X(0)=(0,0,8,16,12)T

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

4當(dāng)前109頁，總共150頁。cj3400θi(min)CBXBx1x2x3x4b0x32110404x2130130λj(max)34000換入變量為：x2;換出變量為x4初始單純形表變更為：4010增廣矩陣的第2行中的每個(gè)元素都÷3得：如圖所示1/311/310增廣矩陣的第1行-第2行得：如圖所示5/3

0-1/330經(jīng)過增廣矩陣的初等變換后，基變成了單位矩陣當(dāng)前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ù)檢驗(yàn)數(shù)定義：目標(biāo)函數(shù)用非基變量表示，其變量的系數(shù)為檢驗(yàn)數(shù)。因此需要將基變量的λ變換為0因?yàn)棣?=0了，所以只需要將λ2變換為0。方法：矩陣的第3行-第2行×4-40

05/3-4/3當(dāng)前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ùn)算，直到確定最優(yōu)解。3018x13當(dāng)前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看到所有的檢驗(yàn)數(shù)都小于0，所以X（2）是最優(yōu)解同時(shí)目標(biāo)函數(shù)值為70

13/5-1/518

0-1/52/54

0

-1

-1

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