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

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

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

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

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

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

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

為基向量。與基向量Pj

對應(yīng)的變量xj

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

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

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

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

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

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

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

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

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

；則有基可行解：

目標函數(shù)值：

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

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

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

，選最小的θ對應(yīng)基變量作為換出變量。 第32頁，課件共49頁，創(chuàng)作于2023年2月單純形法的計算步驟用換入變量xk替換基變量中的換出變量，得到一個新的基。對應(yīng)新的基可以找出一個新的基可行解，并相應(yīng)地可以畫出一個新的單純形表。5）重復(fù)3）、4）步直到計算結(jié)束為止。 第33頁，課件共49頁，創(chuàng)作于2023年2月單純形法的計算步驟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頁，課件共49頁，創(chuàng)作于2023年2月單純形法的計算步驟例2用單純形法求解解：將數(shù)學(xué)模型化為標準形式：不難看出x4、x5可作為初始基變量，列單純形表計算。第35頁，課件共49頁，創(chuàng)作于2023年2月單純形法的計算步驟cj12100θicB基變量bx1x2x3x4x50x4152-32100x5201/31501121000x42x220－x221/3150120753017131/30－90－22560x111017/31/31250128/9-1/92/335/300-98/9-1/9-7/3第36頁，課件共49頁，創(chuàng)作于2023年2月單純形法的計算步驟練習1用單純形法求解線性規(guī)劃問題（無窮解的情況）:第37頁，課件共49頁，創(chuàng)作于2023年2月單純形法的計算步驟練習2用單純形法求解線性規(guī)劃問題（無界解的情況）:第38頁，課件共49頁，創(chuàng)作于2023年2月單純形法的計算步驟

關(guān)于單純形法的補充說明：第39頁，課件共49頁，創(chuàng)作于2023年2月單純形法的計算步驟 學(xué)習要點：

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

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

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

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