第三章線性規(guī)劃模型的單純形法

第三章線性規(guī)劃模型的單純形法第1頁(yè)，課件共49頁(yè)，創(chuàng)作于2023年2月本章教學(xué)目的、重點(diǎn)、難點(diǎn)：

理解線性規(guī)劃模型的可行解、基本解、基本可行解等概念和這些概念之間的關(guān)系；熟悉單純形法的基本思路和單純形法的基本原理；掌握掌握單純形法求解線性規(guī)劃問(wèn)題的基本步驟；掌握單純形表法求出線性規(guī)劃模型的基本最優(yōu)解；會(huì)用計(jì)算機(jī)軟件求解線性規(guī)劃問(wèn)題，進(jìn)一步理解單純形法的基本原理Chapter3線性規(guī)劃模型的單純形法

(SimplexMethod)第2頁(yè)，課件共49頁(yè)，創(chuàng)作于2023年2月線性規(guī)劃模型解的相關(guān)概念及基本性質(zhì)1.線性規(guī)劃問(wèn)題解的相關(guān)概念線性規(guī)劃問(wèn)題求解線性規(guī)劃問(wèn)題，就是從滿足約束條件(2)、(3)的方程組中找出一個(gè)解，使目標(biāo)函數(shù)(1)達(dá)到最大值。第3頁(yè)，課件共49頁(yè)，創(chuàng)作于2023年2月

可行解：滿足約束條件②、③的解為可行解。所有可行解的集合為可行域。

最優(yōu)解：使目標(biāo)函數(shù)達(dá)到最大值的可行解。

基：設(shè)A為約束條件②的m×n階系數(shù)矩陣(m<n)，其秩為m，B是矩陣A中m階滿秩子矩陣（∣B∣≠0），稱B是規(guī)劃問(wèn)題的一個(gè)基。設(shè)：稱B中每個(gè)列向量Pj(j=12……m)

為基向量。與基向量Pj

對(duì)應(yīng)的變量xj

為基變量。除基變量以外的變量為非基變量。線性規(guī)劃模型解的相關(guān)概念及基本性質(zhì)第4頁(yè)，課件共49頁(yè)，創(chuàng)作于2023年2月

基本解：某一確定的基B，令非基變量等于零，由約束條件方程②解出基變量，稱這組解為基B的基本解。在基本解中變量取非0值的個(gè)數(shù)不大于方程數(shù)m，基解的總數(shù)不超過(guò)個(gè)；

基可行解：滿足變量非負(fù)約束條件的基本解，簡(jiǎn)稱基可行解。可行基：對(duì)應(yīng)于基可行解的基稱為可行基。

基本最優(yōu)解：使目標(biāo)函數(shù)最優(yōu)的基本可行解成為基本最優(yōu)解；線性規(guī)劃模型解的相關(guān)概念及基本性質(zhì)第5頁(yè)，課件共49頁(yè)，創(chuàng)作于2023年2月線性規(guī)劃模型解的相關(guān)概念及基本性質(zhì)2.基本解和基本可行解的計(jì)算例3-1通過(guò)下面例3-1來(lái)說(shuō)明線性規(guī)劃問(wèn)題的基、對(duì)應(yīng)的基本解、基本可行解的概念和計(jì)算.

第6頁(yè)，課件共49頁(yè)，創(chuàng)作于2023年2月線性規(guī)劃模型解的相關(guān)概念及基本性質(zhì)2.基本解和基本可行解的計(jì)算與幾何解釋第7頁(yè)，課件共49頁(yè)，創(chuàng)作于2023年2月線性規(guī)劃模型解的相關(guān)概念及基本性質(zhì)2.基本解和基本可行解的計(jì)算與幾何解釋第8頁(yè)，課件共49頁(yè)，創(chuàng)作于2023年2月線性規(guī)劃模型解的相關(guān)概念及基本性質(zhì)2.基本解和基本可行解的計(jì)算與幾何解釋第9頁(yè)，課件共49頁(yè)，創(chuàng)作于2023年2月線性規(guī)劃模型解的相關(guān)概念及基本性質(zhì)2.基本解和基本可行解的計(jì)算與幾何解釋第10頁(yè)，課件共49頁(yè)，創(chuàng)作于2023年2月線性規(guī)劃模型解的相關(guān)概念及基本性質(zhì)2.基本解和基本可行解的計(jì)算第11頁(yè)，課件共49頁(yè)，創(chuàng)作于2023年2月線性規(guī)劃模型解的相關(guān)概念及基本性質(zhì)2.基本解和基本可行解的計(jì)算與幾何解釋由于基本解為非負(fù)，可見(jiàn)該基本解是基本可行解，基是可行基。該基本解對(duì)應(yīng)于圖3-1中的C點(diǎn)。該點(diǎn)是可行域的頂點(diǎn)圖3-1線性規(guī)劃模型對(duì)應(yīng)的基、基本解、基本可行解第12頁(yè)，課件共49頁(yè)，創(chuàng)作于2023年2月線性規(guī)劃模型解的相關(guān)概念及基本性質(zhì)2.基本解和基本可行解的計(jì)算與幾何解釋第13頁(yè)，課件共49頁(yè)，創(chuàng)作于2023年2月線性規(guī)劃模型解的相關(guān)概念及基本性質(zhì)

3.線性規(guī)劃問(wèn)題解的基本性質(zhì)第14頁(yè)，課件共49頁(yè)，創(chuàng)作于2023年2月思考：通過(guò)前面的學(xué)習(xí)可知，若線性規(guī)劃模型有最優(yōu)解，必可在某個(gè)極點(diǎn)上達(dá)到，即在某個(gè)基可行解上取得最優(yōu)解。因此，你會(huì)想到求解線性規(guī)化問(wèn)題最簡(jiǎn)單的方法是？這種方法的缺陷？線性規(guī)劃模型解的相關(guān)概念及基本性質(zhì)第15頁(yè)，課件共49頁(yè)，創(chuàng)作于2023年2月?lián)Q一種思路：若從某一基可行解出發(fā)，每次總是尋找比上一個(gè)“更好”的基可行解，而不去計(jì)算不比上一個(gè)更好的基可行解，可以減少很大的計(jì)算量，怎么實(shí)現(xiàn)這種逐步改善的求解方法呢？線性規(guī)劃模型解的相關(guān)概念及基本性質(zhì)第16頁(yè)，課件共49頁(yè)，創(chuàng)作于2023年2月需要解決以下幾個(gè)問(wèn)題：（1）如何得到一個(gè)初始的基可行解；（2）如何判斷當(dāng)前的基可行解是否達(dá)到最優(yōu)解；（3）若當(dāng)前解不是最優(yōu)解，如何去尋找一個(gè)改善的基可行解？線性規(guī)劃模型解的相關(guān)概念及基本性質(zhì)美國(guó)數(shù)學(xué)家丹齊格提出的單純形法解決了以上三個(gè)問(wèn)題，單純形法是求解線性規(guī)劃問(wèn)題的一種普遍有效方法。第17頁(yè)，課件共49頁(yè)，創(chuàng)作于2023年2月單純形法的基本思路單純形法的思路找出一個(gè)初始可行解是否最優(yōu)轉(zhuǎn)移到另一個(gè)基本可行解（找出更大的目標(biāo)函數(shù)值）最優(yōu)解是否循環(huán)核心是：變量迭代結(jié)束第18頁(yè)，課件共49頁(yè)，創(chuàng)作于2023年2月基本原理單純形法的基本原理初始基可行解的確定最優(yōu)解的檢驗(yàn)換基迭代

最優(yōu)性檢驗(yàn)的依據(jù)---檢驗(yàn)數(shù)最優(yōu)解判定定理入基變量的確定出基變量的確定第19頁(yè)，課件共49頁(yè)，創(chuàng)作于2023年2月單純形法的基本原理1.初始基可行解的確定B為可行基，由B得到的解為初始基可行解。

第20頁(yè)，課件共49頁(yè)，創(chuàng)作于2023年2月單純形法的基本原理1.初始基可行解的確定

在第一次找可行基時(shí)，所找到的基或?yàn)閱挝痪仃嚮驗(yàn)橛蓡挝痪仃嚨母髁邢蛄克M成，稱之為初始可行基，其相應(yīng)的基本可行解叫初始基本可行解。如果找不到單位矩陣或由單位矩陣的各列向量組成的基作為初始可行基，我們將構(gòu)造初始可行基，具體做法在以后詳細(xì)講述。第21頁(yè)，課件共49頁(yè)，創(chuàng)作于2023年2月單純形法的基本原理2.最優(yōu)解的檢驗(yàn)(1)檢驗(yàn)數(shù)的意義第22頁(yè)，課件共49頁(yè)，創(chuàng)作于2023年2月單純形法的基本原理2.最優(yōu)解的檢驗(yàn)假設(shè)

；則有基可行解：

目標(biāo)函數(shù)值：

為了判斷是否為最優(yōu)解，首先把基變量、目標(biāo)函數(shù)用非基變量表示：第23頁(yè)，課件共49頁(yè)，創(chuàng)作于2023年2月單純形法的基本原理2.最優(yōu)解的檢驗(yàn)其中：第24頁(yè)，課件共49頁(yè)，創(chuàng)作于2023年2月單純形法的基本原理2.最優(yōu)解的檢驗(yàn)

(2)最優(yōu)解的判斷法則：若對(duì)基可行解，若所有檢驗(yàn)數(shù)，則為最優(yōu)解；換個(gè)角度，由于每個(gè)非基變量檢驗(yàn)數(shù)非正，引入任意非基變量都不能使Z值上升,故為最優(yōu)解。若存在某個(gè)，則不是最優(yōu)解，計(jì)算過(guò)程繼續(xù)。第25頁(yè)，課件共49頁(yè)，創(chuàng)作于2023年2月單純形法的基本原理2.換基迭代

(1)換入變量（進(jìn)基變量）(2)換出變量（出基變量）第26頁(yè)，課件共49頁(yè)，創(chuàng)作于2023年2月單純形法的基本原理2.換基迭代(2)換出變量（出基變量）第27頁(yè)，課件共49頁(yè)，創(chuàng)作于2023年2月單純形法的基本原理2.換基迭代(2)換出變量（出基變量）通過(guò)初等變換將新的一組基變量用非基變量表示出，判斷解的最優(yōu)性。第28頁(yè)，課件共49頁(yè)，創(chuàng)作于2023年2月單純形表法的計(jì)算步驟單純形表第29頁(yè)，課件共49頁(yè)，創(chuàng)作于2023年2月單純形法的計(jì)算步驟例1用單純形法求下列線性規(guī)劃的最優(yōu)解解：1）將問(wèn)題化為標(biāo)準(zhǔn)型，加入松馳變量x3、x4則標(biāo)準(zhǔn)型為:第30頁(yè)，課件共49頁(yè)，創(chuàng)作于2023年2月單純形法的計(jì)算步驟2）求出線性規(guī)劃的初始基可行解，列出初始單純形表。cj3400θicB基bx1x2x3x40x34021100x43013013400檢驗(yàn)數(shù)第31頁(yè)，課件共49頁(yè)，創(chuàng)作于2023年2月單純形法的計(jì)算步驟3）進(jìn)行最優(yōu)性檢驗(yàn)如果表中所有檢驗(yàn)數(shù)，則表中的基可行解就是問(wèn)題的最優(yōu)解，計(jì)算停止。否則繼續(xù)下一步。4）從一個(gè)基可行解轉(zhuǎn)換到另一個(gè)目標(biāo)值更大的基可行解，列出新的單純形表確定換入基的變量。選擇，對(duì)應(yīng)的變量xj作為換入變量，當(dāng)有一個(gè)以上檢驗(yàn)數(shù)大于0時(shí)，一般選擇最大的一個(gè)檢驗(yàn)數(shù)，即：，其對(duì)應(yīng)的xk作為換入變量。確定換出變量。根據(jù)下式計(jì)算并選擇θ

，選最小的θ對(duì)應(yīng)基變量作為換出變量。 第32頁(yè)，課件共49頁(yè)，創(chuàng)作于2023年2月單純形法的計(jì)算步驟用換入變量xk替換基變量中的換出變量，得到一個(gè)新的基。對(duì)應(yīng)新的基可以找出一個(gè)新的基可行解，并相應(yīng)地可以畫(huà)出一個(gè)新的單純形表。5）重復(fù)3）、4）步直到計(jì)算結(jié)束為止。 第33頁(yè)，課件共49頁(yè)，創(chuàng)作于2023年2月單純形法的計(jì)算步驟cj3400θicB基變量bx1x2x3x40x34021100x430130134000x34x23x14x2換入列bi/ai2，ai2>04010換出行將3化為15/311801/301/3101－1/3303005/30－4/3乘以1/3后得到103/5－1/51801－1/5－2/5400－1－1基本最優(yōu)解、最優(yōu)值第34頁(yè)，課件共49頁(yè)，創(chuàng)作于2023年2月單純形法的計(jì)算步驟例2用單純形法求解解：將數(shù)學(xué)模型化為標(biāo)準(zhǔn)形式：不難看出x4、x5可作為初始基變量，列單純形表計(jì)算。第35頁(yè)，課件共49頁(yè)，創(chuàng)作于2023年2月單純形法的計(jì)算步驟cj12100θicB基變量bx1x2x3x4x50x4152-32100x5201/31501121000x42x220－x221/3150120753017131/30－90－22560x111017/31/31250128/9-1/92/335/300-98/9-1/9-7/3第36頁(yè)，課件共49頁(yè)，創(chuàng)作于2023年2月單純形法的計(jì)算步驟練習(xí)1用單純形法求解線性規(guī)劃問(wèn)題（無(wú)窮解的情況）:第37頁(yè)，課件共49頁(yè)，創(chuàng)作于2023年2月單純形法的計(jì)算步驟練習(xí)2用單純形法求解線性規(guī)劃問(wèn)題（無(wú)界解的情況）:第38頁(yè)，課件共49頁(yè)，創(chuàng)作于2023年2月單純形法的計(jì)算步驟

關(guān)于單純形法的補(bǔ)充說(shuō)明：第39頁(yè)，課件共49頁(yè)，創(chuàng)作于2023年2月單純形法的計(jì)算步驟 學(xué)習(xí)要點(diǎn)：

1.線性規(guī)劃解的概念以及3個(gè)基本定理

2.熟練掌握單純形表法的解題思路及求解步驟第40頁(yè)，課件共49頁(yè)，創(chuàng)作于2023年2月 思考：如果找不到單位矩陣或由單位矩陣的各列向量組成的基作為初始可行基，我們將如何構(gòu)造初始可行基？單純形法的計(jì)算步驟 作業(yè)：

P523、4第41頁(yè)，課件共49頁(yè)，創(chuàng)作于2023年2月單純形法的進(jìn)一步討論－人工變量法人工變量法： 前面討論了在標(biāo)準(zhǔn)型中系數(shù)矩陣有單位矩陣，很容易確定一組基可行解。在實(shí)際問(wèn)題中有些模型并不含有單位矩陣，為了得到一組基向量和初基可行解，在約束條件的等式左端加一組虛擬變量，得到一組基變量。這種人為加的變量稱為人工變量，構(gòu)成的可行基稱為人工基，用大M法或兩階段法求解，這種用人工變量作橋梁的求解方法稱為人工變量法。第42頁(yè)，課件共49頁(yè)，創(chuàng)作于2023年2月單純形法的進(jìn)一步討論－人工變量法人工變量法：

人工變量時(shí)為了獲得初始基可行解，在約束條件化為等式后，認(rèn)為的加入的虛擬變量，只有當(dāng)他們同時(shí)為零，即在最終的單純形表中它們?nèi)孔優(yōu)榉腔兞浚藭r(shí)加入人工變量的等式約束才與原約束條件等價(jià)。因此在最優(yōu)解的基變量中不允許含有人工變量，這就要求在迭代過(guò)程中把人工變量從基變量中迭代出去，通常采用M法和兩階段法第43頁(yè)，課件共49頁(yè)，創(chuàng)作于2023年2月單純形法的進(jìn)一步討論－人工變量法人工變量、松弛變量和剩余變量是不同的，松弛變量、剩余變量可以取零值，也可以取正值。但是人工變量只能取零值，否則約束條件1、2就和原始的約束條件不等價(jià)了。為了使得人工變量為零，規(guī)定人工變量在目標(biāo)函數(shù)中的系數(shù)為-M,M>0,且為任意大的數(shù)。這樣只要人工變量不為零，目標(biāo)函數(shù)最大值就是一個(gè)任意小的數(shù)。為了使目標(biāo)函數(shù)實(shí)現(xiàn)最大化人工變量要為零，所以只有在最終單純形表中人工變量為非基變量，人工變量的值才能是0。為了構(gòu)造初始可行基，強(qiáng)行將人工變量加到約束條件中去；又為了把人工變量從基變量中替換出來(lái)，就令人工變量在求最大值的目標(biāo)函數(shù)中為-M,M>0,這一方法稱大M法。大M法：第44頁(yè)，課件共49頁(yè)，創(chuàng)作于2023年2月單純形法的進(jìn)一步討論－人工變量法例3用大M法解下列線性規(guī)劃解：首先將數(shù)學(xué)模型化為標(biāo)準(zhǔn)形式系數(shù)矩陣中不存在單位矩陣，無(wú)法建立初始單純形表。第45頁(yè)，課件共49頁(yè)，創(chuàng)作于2023年2月單純形法的進(jìn)一步討論－人工變量法故人為添加兩個(gè)單位向量，得到人工變量單純形法數(shù)學(xué)模型：其中：M是一個(gè)很大的抽象的數(shù)，不需要給出具體的數(shù)值，可以理解為它能大于給