單純形方法求解課件

1.圖解法的局限圖解法只可解決兩個變量的線性規(guī)劃問題，而在實(shí)際應(yīng)用中還有多個變量的線性規(guī)劃問題無法解決。因此，

1947年G.B.Dantzig提出的單純形法提供了方便、有效的通用算法求解線性規(guī)劃。

1.圖解法的局限圖解法只可解決兩個變量的線性規(guī)劃問題，而在實(shí)2基：已知A是約束條件的m×n系數(shù)矩陣，其秩為m。若B是A中m×m階非奇異子矩陣（即可逆矩陣），則稱B是線性規(guī)劃問題中的一個基?；蛄浚夯鵅中的一列即稱為一個基向量?；鵅中共有m個基向量。非基向量：在A中除了基B之外的一列則稱之為基B的非基向量?；兞浚号c基向量pi相應(yīng)的變量xi叫基變量，基變量有m個。非基變量：與非基向量pj相應(yīng)的變量xj叫非基變量，非基變量有n－m個?；靖拍?基：已知A是約束條件的m×n系數(shù)矩陣，其秩為m。若B是A中一、單純形法的基本原理

頂點(diǎn)的逐步轉(zhuǎn)移

即從可行域的一個頂點(diǎn)（基本可行解）開始，轉(zhuǎn)移到另一個頂點(diǎn)（另一個基本可行解）的迭代過程，轉(zhuǎn)移的條件是使目標(biāo)函數(shù)值得到改善（逐步變優(yōu)），當(dāng)目標(biāo)函數(shù)達(dá)到最優(yōu)值時，問題也就得到了最優(yōu)解。一、單純形法的基本原理

頂點(diǎn)的逐步轉(zhuǎn)移即從可基本思路：基本思路：

根據(jù)線性規(guī)劃問題的可行域是凸多邊形或凸多面體，一個線性規(guī)劃問題有最優(yōu)解，就一定可以在可行域的頂點(diǎn)上找到。

于是，若某線性規(guī)劃只有唯一的一個最優(yōu)解，這個最優(yōu)解所對應(yīng)的點(diǎn)一定是可行域的一個頂點(diǎn)；若該線性規(guī)劃有多個最優(yōu)解，那么肯定在可行域的頂點(diǎn)中可以找到至少一個最優(yōu)解。頂點(diǎn)轉(zhuǎn)移的依據(jù)根據(jù)線性規(guī)劃問題的可行域是凸多邊形或凸多面體表格單純形法例題1：用單純形法求解線性規(guī)劃問題

maxf=3x1+4x2x1+2x2≤63x1+2x2≤12x2≤2x1≥0,x2≥0表格單純形法例題1：用單純形法求解線性規(guī)劃問題首先將此現(xiàn)行規(guī)劃問題化為標(biāo)準(zhǔn)形式得到：minf’=-f=-3x1-4x2x1+2x2+x3=63x1+2x2+x4=12x2+x5=2x1≥0,x2≥0,x3≥0,x4≥0,x5≥0首先將此現(xiàn)行規(guī)劃問題化為標(biāo)準(zhǔn)形式表格單純形法：1、初始單純形表的建立(1)表格結(jié)構(gòu)：

-3-4000常數(shù)dx1x2x3x4x50x31210060x432010120x5010012檢驗(yàn)數(shù)b340000cjxjxBcB表格單純形法：-3-4000常數(shù)x1x2x3x4x50x31單純形表的列法：原方程中自帶的變量稱為非基變量，如x1,x2;為解題而設(shè)出的變量稱為基變量，如x3,x4,x5。cj：目標(biāo)函數(shù)中變量的系數(shù);xj:變量；xB：基變量；cB:基變量在目標(biāo)函數(shù)中對應(yīng)的系數(shù)；d:各約束條件的常數(shù)項(xiàng)；檢驗(yàn)數(shù)：單純形表的列法：求例題的檢驗(yàn)數(shù)：b01=0*1+0*3+0*0-(-3)同理求得b02,b03,b04,b05則最右下角的我們稱之為b0，所以b0=0求例題的檢驗(yàn)數(shù)：解答：（1）確定換入基的變量。只要有檢驗(yàn)數(shù)b﹥0，對應(yīng)的變量xj就可作為換入基的變量，當(dāng)有一個以上檢驗(yàn)數(shù)大于零時，一般從最大的開始。因此在本題的檢驗(yàn)數(shù)中找到最大的正檢驗(yàn)數(shù)。-3-4000常數(shù)dx1x2x3x4x50x31210060x432010120x5010012檢驗(yàn)數(shù)b340000cjxjxBcB解答：-3-4000常數(shù)x1x2x3x4x50x312100這說明我要調(diào)整非基變量x2，使其成為基變量，并相應(yīng)調(diào)出一個基變量為非基變量。（2）確定換出基的變量。為確定哪個基變量調(diào)出首先計(jì)算:所以本題有：則此最小值對應(yīng)x5,所以我們將x5行與x2列相交的數(shù)值“1”圈起來。即要將x2與x5進(jìn)行調(diào)整?！?”被稱為旋轉(zhuǎn)元素。這說明我要調(diào)整非基變量x2，使其成為基變量，并相應(yīng)調(diào)出一個（3）用換入變量xj替換換出變量xB，得到一個新的基。對應(yīng)這個基找出新的基可行解并列出新的單純性表。ⅰ）首先將旋轉(zhuǎn)元變?yōu)椤?”，即將所要轉(zhuǎn)換的基變量行除以旋轉(zhuǎn)元。因?yàn)楸绢}中旋轉(zhuǎn)元已經(jīng)為“1”，所以x5行不用調(diào)整。ⅱ）將旋轉(zhuǎn)元所在行轉(zhuǎn)換后的整行數(shù)字乘以（-aij),加到表中的第i行數(shù)字上，即將要轉(zhuǎn)化為基變量的列變?yōu)槌D(zhuǎn)換元為“1”外，其他數(shù)字都為“0”的列。在本題中，即是將x5行中的各數(shù)乘以（-2），分別加到x3和x4行上。再將x5行乘以（-4）加到檢驗(yàn)行上。使得x2列上除了旋轉(zhuǎn)元變?yōu)椤?”，其余數(shù)字都變?yōu)椤?”。并將xB列中的x5調(diào)為x2,表示x2調(diào)入基變量，x5調(diào)入非基變量。因此得到下表。（3）用換入變量xj替換換出變量xB，得到一個新的基。對應(yīng)這-3-4000常數(shù)dx1x2x3x4x50x31010-220x43001-28-4x2010012檢驗(yàn)數(shù)b3000-4-8cjxjxBcB以上不過程稱之為迭代。如果檢驗(yàn)數(shù)中任然存在大于“0”的數(shù)字，則重復(fù)以上3個步驟。直至檢驗(yàn)數(shù)中所有數(shù)字均小于等于0，此時所的的結(jié)果即為最優(yōu)解。-3-4000常數(shù)x1x2x3x4x50x31010-220以上線性規(guī)劃問題所得的最后檢驗(yàn)數(shù)都小于或等于“0”的單純形法表格如下：-3-4000常數(shù)dx1x2x3x4x5-3x110-1/21/2030x500-3/41/411/2-4x2013/4-1/403/2檢驗(yàn)數(shù)b00-3/2-1/20-15cjxjxBcB因此得到當(dāng)x1=3，x2=3/2,x3=x4=0,x5=1/2時，目標(biāo)函數(shù)最大值f=15.以上線性規(guī)劃問題所得的最后檢驗(yàn)數(shù)都小于或等于“0”的單純形法練習(xí)1：練習(xí)1：①將線性規(guī)劃問題化成標(biāo)準(zhǔn)型②建立初始單純形表③計(jì)算各非基變量xB的檢驗(yàn)數(shù)

若所有b≤0，則問題已得到最優(yōu)解，停止計(jì)算，否則轉(zhuǎn)入下步。④在大于0的檢驗(yàn)數(shù)中，若某個bj﹥0，而所對應(yīng)的列中沒有正數(shù)，則此問題是無界解，停止計(jì)算，否則轉(zhuǎn)入下步。二、單純形法的計(jì)算步驟

①將線性規(guī)劃問題化成標(biāo)準(zhǔn)型二、單純形法的計(jì)算步驟⑤根據(jù)max{dj｜dj＞0}=dk原則，確定xk為換入變量(進(jìn)基變量)，再按規(guī)則計(jì)算：=min{bi′/aik′|aik′＞0}=bl′/aik′

確定出換出變量。建立新的單純形表，此時換入非基變量取代了換出基變量的位置。以aik′為主元素進(jìn)行迭代，把xk所對應(yīng)的列向量變?yōu)閱挝涣邢蛄?，即aik′變?yōu)?，同列中其它元素為0。后轉(zhuǎn)第③步。

⑤根據(jù)max{dj｜dj＞0}=dk原則，確定xk為換入變量練習(xí)2：練習(xí)2：人工變量法

用單純形法解題時，需要有一個單位陣作為初始基。當(dāng)約束條件都是“≤”時，加入松弛變量就形成了初始基。但實(shí)際存在“≥”或“＝”型的約束，沒有現(xiàn)成的單位矩陣。人工變量

采用人造基的辦法：人工構(gòu)造單位矩陣在沒有單位列向量的等式約束中加入人工變量，構(gòu)成原線性規(guī)劃問題的伴隨問題，從而得到一個初始基。人工變量是在等式中人為加進(jìn)的，只有它等于0時，約束條件才是它本來的意義。處理方法有兩種：大M法兩階段法人工變量法用單純形法解題時，需要有一個單位陣作為初始基。人例題2：大M法例題2：大M法大M法：本題化為標(biāo)準(zhǔn)形式后，發(fā)現(xiàn)只有x4一個基變量，但題中需要三個基變量，于是，加入行x6,x7兩個人工變量。其目標(biāo)函數(shù)中的系數(shù)為M，M代表任意大的正值。大M法：本題化為標(biāo)準(zhǔn)形式后，發(fā)現(xiàn)只有x4一個基變量，但題中需練習(xí)3：練習(xí)3：兩階段法：第一階段：先求解一個目標(biāo)函數(shù)中只包含人工變量的線性規(guī)劃問題，即令目標(biāo)函數(shù)中的其他變量系數(shù)取零，人工變量的系數(shù)取某個正的常數(shù)（一般取1），在保持原問題約束條件不變的情況下求這個目標(biāo)函數(shù)極小化的解。顯然在第一階段中，當(dāng)人工變量取值為零時，目標(biāo)函數(shù)值為零。這個時候的最優(yōu)解就是原線性規(guī)劃問題的一個基可行解。如果第一階段求解結(jié)果最優(yōu)解的目標(biāo)函數(shù)值不為零，即最優(yōu)解的非基變量中含有非零的人工變量，表明線性規(guī)劃問題無可行解。第二階段：當(dāng)?shù)谝浑A段求解結(jié)果表明問題有可行解，則此階段在原問題中去除人工變量，并從此可行解出發(fā)繼續(xù)尋找最優(yōu)解。兩階段法：第一階段：先求解一個目標(biāo)函數(shù)中只包含人工變量的線性例3：兩階段法例3：兩階段法單純形法一般還可證明：1.解的情況：(1)如果在單純形表中所有檢驗(yàn)數(shù)都非正：

1）若基變量中含非零的人工變量，則無可行解。

2）若基變量中不含非零的人工變量：①若存在非基變量的檢驗(yàn)數(shù)為零，則有無窮多解。②若不存在非基變量的檢驗(yàn)數(shù)為零，則有唯一解(2)如果單純形表中，某一檢驗(yàn)數(shù)大于零，而且對應(yīng)變量所在列中沒有正數(shù)，則線性規(guī)劃問題為無界解。2.利用單純形法一定可以求出線性規(guī)劃問題的最優(yōu)解或可以判斷線性規(guī)劃問題無最優(yōu)解。

單純形法一般還可證明：1.解的情況：1.圖解法的局限圖解法只可解決兩個變量的線性規(guī)劃問題，而在實(shí)際應(yīng)用中還有多個變量的線性規(guī)劃問題無法解決。因此，

1947年G.B.Dantzig提出的單純形法提供了方便、有效的通用算法求解線性規(guī)劃。

1.圖解法的局限圖解法只可解決兩個變量的線性規(guī)劃問題，而在實(shí)28基：已知A是約束條件的m×n系數(shù)矩陣，其秩為m。若B是A中m×m階非奇異子矩陣（即可逆矩陣），則稱B是線性規(guī)劃問題中的一個基?；蛄浚夯鵅中的一列即稱為一個基向量。基B中共有m個基向量。非基向量：在A中除了基B之外的一列則稱之為基B的非基向量?；兞浚号c基向量pi相應(yīng)的變量xi叫基變量，基變量有m個。非基變量：與非基向量pj相應(yīng)的變量xj叫非基變量，非基變量有n－m個?；靖拍?基：已知A是約束條件的m×n系數(shù)矩陣，其秩為m。若B是A中一、單純形法的基本原理

頂點(diǎn)的逐步轉(zhuǎn)移

即從可行域的一個頂點(diǎn)（基本可行解）開始，轉(zhuǎn)移到另一個頂點(diǎn)（另一個基本可行解）的迭代過程，轉(zhuǎn)移的條件是使目標(biāo)函數(shù)值得到改善（逐步變優(yōu)），當(dāng)目標(biāo)函數(shù)達(dá)到最優(yōu)值時，問題也就得到了最優(yōu)解。一、單純形法的基本原理

頂點(diǎn)的逐步轉(zhuǎn)移即從可基本思路：基本思路：

根據(jù)線性規(guī)劃問題的可行域是凸多邊形或凸多面體，一個線性規(guī)劃問題有最優(yōu)解，就一定可以在可行域的頂點(diǎn)上找到。

于是，若某線性規(guī)劃只有唯一的一個最優(yōu)解，這個最優(yōu)解所對應(yīng)的點(diǎn)一定是可行域的一個頂點(diǎn)；若該線性規(guī)劃有多個最優(yōu)解，那么肯定在可行域的頂點(diǎn)中可以找到至少一個最優(yōu)解。頂點(diǎn)轉(zhuǎn)移的依據(jù)根據(jù)線性規(guī)劃問題的可行域是凸多邊形或凸多面體表格單純形法例題1：用單純形法求解線性規(guī)劃問題

maxf=3x1+4x2x1+2x2≤63x1+2x2≤12x2≤2x1≥0,x2≥0表格單純形法例題1：用單純形法求解線性規(guī)劃問題首先將此現(xiàn)行規(guī)劃問題化為標(biāo)準(zhǔn)形式得到：minf’=-f=-3x1-4x2x1+2x2+x3=63x1+2x2+x4=12x2+x5=2x1≥0,x2≥0,x3≥0,x4≥0,x5≥0首先將此現(xiàn)行規(guī)劃問題化為標(biāo)準(zhǔn)形式表格單純形法：1、初始單純形表的建立(1)表格結(jié)構(gòu)：

-3-4000常數(shù)dx1x2x3x4x50x31210060x432010120x5010012檢驗(yàn)數(shù)b340000cjxjxBcB表格單純形法：-3-4000常數(shù)x1x2x3x4x50x31單純形表的列法：原方程中自帶的變量稱為非基變量，如x1,x2;為解題而設(shè)出的變量稱為基變量，如x3,x4,x5。cj：目標(biāo)函數(shù)中變量的系數(shù);xj:變量；xB：基變量；cB:基變量在目標(biāo)函數(shù)中對應(yīng)的系數(shù)；d:各約束條件的常數(shù)項(xiàng)；檢驗(yàn)數(shù)：單純形表的列法：求例題的檢驗(yàn)數(shù)：b01=0*1+0*3+0*0-(-3)同理求得b02,b03,b04,b05則最右下角的我們稱之為b0，所以b0=0求例題的檢驗(yàn)數(shù)：解答：（1）確定換入基的變量。只要有檢驗(yàn)數(shù)b﹥0，對應(yīng)的變量xj就可作為換入基的變量，當(dāng)有一個以上檢驗(yàn)數(shù)大于零時，一般從最大的開始。因此在本題的檢驗(yàn)數(shù)中找到最大的正檢驗(yàn)數(shù)。-3-4000常數(shù)dx1x2x3x4x50x31210060x432010120x5010012檢驗(yàn)數(shù)b340000cjxjxBcB解答：-3-4000常數(shù)x1x2x3x4x50x312100這說明我要調(diào)整非基變量x2，使其成為基變量，并相應(yīng)調(diào)出一個基變量為非基變量。（2）確定換出基的變量。為確定哪個基變量調(diào)出首先計(jì)算:所以本題有：則此最小值對應(yīng)x5,所以我們將x5行與x2列相交的數(shù)值“1”圈起來。即要將x2與x5進(jìn)行調(diào)整?！?”被稱為旋轉(zhuǎn)元素。這說明我要調(diào)整非基變量x2，使其成為基變量，并相應(yīng)調(diào)出一個（3）用換入變量xj替換換出變量xB，得到一個新的基。對應(yīng)這個基找出新的基可行解并列出新的單純性表。?。┦紫葘⑿D(zhuǎn)元變?yōu)椤?”，即將所要轉(zhuǎn)換的基變量行除以旋轉(zhuǎn)元。因?yàn)楸绢}中旋轉(zhuǎn)元已經(jīng)為“1”，所以x5行不用調(diào)整。ⅱ）將旋轉(zhuǎn)元所在行轉(zhuǎn)換后的整行數(shù)字乘以（-aij),加到表中的第i行數(shù)字上，即將要轉(zhuǎn)化為基變量的列變?yōu)槌D(zhuǎn)換元為“1”外，其他數(shù)字都為“0”的列。在本題中，即是將x5行中的各數(shù)乘以（-2），分別加到x3和x4行上。再將x5行乘以（-4）加到檢驗(yàn)行上。使得x2列上除了旋轉(zhuǎn)元變?yōu)椤?”，其余數(shù)字都變?yōu)椤?”。并將xB列中的x5調(diào)為x2,表示x2調(diào)入基變量，x5調(diào)入非基變量。因此得到下表。（3）用換入變量xj替換換出變量xB，得到一個新的基。對應(yīng)這-3-4000常數(shù)dx1x2x3x4x50x31010-220x43001-28-4x2010012檢驗(yàn)數(shù)b3000-4-8cjxjxBcB以上不過程稱之為迭代。如果檢驗(yàn)數(shù)中任然存在大于“0”的數(shù)字，則重復(fù)以上3個步驟。直至檢驗(yàn)數(shù)中所有數(shù)字均小于等于0，此時所的的結(jié)果即為最優(yōu)解。-3-4000常數(shù)x1x2x3x4x50x31010-220以上線性規(guī)劃問題所得的最后檢驗(yàn)數(shù)都小于或等于“0”的單純形法表格如下：-3-4000常數(shù)dx1x2x3x4x5-3x110-1/21/2030x500-3/41/411/2-4x2013/4-1/403/2檢驗(yàn)數(shù)b00-3/2-1/20-15cjxjxBcB因此得到當(dāng)x1=3，x2=3/2,x3=x4=0,x5=1/2時，目標(biāo)函數(shù)最大值f=15.以上線性規(guī)劃問題所得的最后檢驗(yàn)數(shù)都小于或等于“0”的單純形法練習(xí)1：練習(xí)1：①將線性規(guī)劃問題化成標(biāo)準(zhǔn)型②建立初始單純形表③計(jì)算各非基變量xB的檢驗(yàn)數(shù)

若所有b≤0，則問題已得到最優(yōu)解，停止計(jì)算，否則轉(zhuǎn)入下步。④在大于0的檢驗(yàn)數(shù)中，若某個bj﹥0，而所對應(yīng)的列中沒有正數(shù)，則此問題是無界解，停止計(jì)算，否則轉(zhuǎn)入下步。二、單純形法的計(jì)算步驟

①將線性規(guī)劃問題化成標(biāo)準(zhǔn)型二、單純形法的計(jì)算步驟⑤根據(jù)max{dj｜dj＞0}=dk原則，確定xk為換入變量(進(jìn)基變量)，再按規(guī)則計(jì)算：=min{bi′/aik′|aik′＞0}=bl′/aik′

確定出換出變量。建立新的單純形表，此時換入非基變量取代了換出基變量的位置。以aik′為主元素進(jìn)行迭代，把xk所對應(yīng)的列向量變?yōu)閱挝涣邢蛄?，即aik′變?yōu)?，同列中其它元素為0。后轉(zhuǎn)第③步。

⑤根據(jù)max{dj｜dj＞0}=dk原則，確定xk為換入變量練習(xí)2：練習(xí)2：人工變量法

用單純形法解題時，需要有一個單位陣作為初始基。當(dāng)約束條件都是“≤”時，加入松弛變量就形成了初始基。但實(shí)際存在“≥”或“＝