環(huán)境系統(tǒng)分析：第六章 線性規(guī)劃基礎(chǔ)

1、第六章第六章 線性規(guī)劃基礎(chǔ)線性規(guī)劃基礎(chǔ)-環(huán)境系統(tǒng)污染控制規(guī)劃的數(shù)學(xué)基礎(chǔ)6.1 6.1 線性規(guī)劃概述線性規(guī)劃概述 線性規(guī)劃是數(shù)學(xué)規(guī)劃與運(yùn)籌學(xué)的一個(gè)分支，線性規(guī)劃是數(shù)學(xué)規(guī)劃與運(yùn)籌學(xué)的一個(gè)分支，是運(yùn)籌學(xué)中最重要的一種數(shù)學(xué)方法。主要研是運(yùn)籌學(xué)中最重要的一種數(shù)學(xué)方法。主要研究解決有限資源的最佳分配問(wèn)題，即如何對(duì)究解決有限資源的最佳分配問(wèn)題，即如何對(duì)有限的資源作出最佳方式的調(diào)配和最有利的有限的資源作出最佳方式的調(diào)配和最有利的使用，以便最充分地發(fā)揮資源的效能去獲取使用，以便最充分地發(fā)揮資源的效能去獲取最佳經(jīng)濟(jì)效益。最佳經(jīng)濟(jì)效益。 這種數(shù)學(xué)規(guī)劃的方法，如果用數(shù)學(xué)語(yǔ)言表達(dá)，這種數(shù)學(xué)規(guī)劃的方法，如果用數(shù)學(xué)語(yǔ)言表達(dá)

2、，就是在一定的約束條件下，尋找目標(biāo)函數(shù)的就是在一定的約束條件下，尋找目標(biāo)函數(shù)的極值問(wèn)題。所謂線性規(guī)劃，是指約束條件為極值問(wèn)題。所謂線性規(guī)劃，是指約束條件為線性等式或不等式，且目標(biāo)函數(shù)也是線性函線性等式或不等式，且目標(biāo)函數(shù)也是線性函數(shù)數(shù)。 生產(chǎn)調(diào)度問(wèn)題生產(chǎn)調(diào)度問(wèn)題1. 線性規(guī)劃問(wèn)題的提出線性規(guī)劃問(wèn)題的提出一、線性規(guī)劃及其數(shù)學(xué)模型一、線性規(guī)劃及其數(shù)學(xué)模型 某企業(yè)生產(chǎn)甲、乙兩種產(chǎn)品，分別用某企業(yè)生產(chǎn)甲、乙兩種產(chǎn)品，分別用A A、B B、C 3C 3種不同的原料，每生產(chǎn)種不同的原料，每生產(chǎn)1 1個(gè)單位的甲，需用個(gè)單位的甲，需用1 1個(gè)單位的個(gè)單位的A A、1 1個(gè)單位的個(gè)單位的B B、0 0個(gè)單位的個(gè)

3、單位的C C，利潤(rùn)為，利潤(rùn)為3 3千元；每生產(chǎn)千元；每生產(chǎn)1 1個(gè)單位的乙，需用個(gè)單位的乙，需用1 1個(gè)單位的個(gè)單位的A A、2 2個(gè)單位的個(gè)單位的B B、1 1個(gè)單位的個(gè)單位的C C，利潤(rùn)為，利潤(rùn)為4 4千元；現(xiàn)有千元；現(xiàn)有6 6個(gè)單位的個(gè)單位的A A、8 8個(gè)單位的個(gè)單位的B B、3 3個(gè)單位的個(gè)單位的C C，問(wèn)企業(yè)，問(wèn)企業(yè)如何安排生產(chǎn)，可使利潤(rùn)最大。如何安排生產(chǎn)，可使利潤(rùn)最大。產(chǎn)品產(chǎn)品 甲甲乙乙x1x2原料原料ABC利潤(rùn)利潤(rùn)11031214原料原料限制限制6832. 建模的步驟建模的步驟(1)明確問(wèn)題的經(jīng)濟(jì)背景明確問(wèn)題的經(jīng)濟(jì)背景(2)設(shè)定決策變量設(shè)定決策變量(3)明確目標(biāo)明確目標(biāo)-給出目

4、標(biāo)函數(shù)給出目標(biāo)函數(shù)(4)明確問(wèn)題的所有限制明確問(wèn)題的所有限制-給出約束條件給出約束條件Z = 3x1 + 4x2x1 + x2 6x1 + 2x2 8x2 3x10, x2 0 每天總利潤(rùn)：每天總利潤(rùn)：Z = 3xZ = 3x1 1 + 4x+ 4x2 2 變量變量 x x1 1 和和x x2 2 必須滿足三個(gè)條件：必須滿足三個(gè)條件： x x1 1 + x + x2 2 6 6 x x1 1 + 2x + 2x2 2 8 8 x x2 2 3 3 非負(fù)性約束：非負(fù)性約束：x x1 10, 0, x x2 2 00目標(biāo)函數(shù)目標(biāo)函數(shù)決策變量決策變量函函數(shù)數(shù)約約束束約束條件約束條件Max Z = 3

5、xMax Z = 3x1 1 + 4x+ 4x2 2 x x1 1 +x +x2 2 6 6 x1 +2x x1 +2x2 2 8 8 x x2 2 3 3 x x1 10, 0, x x2 2 00數(shù)學(xué)模型數(shù)學(xué)模型s.t.線性規(guī)劃的數(shù)學(xué)表達(dá)線性規(guī)劃的數(shù)學(xué)表達(dá)即求一組變量即求一組變量x x1 1 , x, x2 2 , x, xn n , ,在滿足約束條件：在滿足約束條件： a11x1 + a12x2 + +a1nxnb1 a21x1 + a22x2 + +a2nxnb2 am1x1 + am2x2 + +amnxnbm x1 , x2 , , xn 0 的情況下，使目標(biāo)函數(shù)：的情況下，使目標(biāo)

6、函數(shù)：f=cf=c1 1x x1 1+c+c2 2x x2 2+ +c+ +cn nx xn n 達(dá)到最大值或最小值。達(dá)到最大值或最小值。 Max / Min F=CX AXB 或或 AXB X0 或或 X0 或或 X自由自由其中：其中：C=(c1,c2,cn) B=(b1,b2,bm) X=(x1,x2, ,xn) A=aij（i=1,2, ,m；j=1,2, ,n ） 一般來(lái)說(shuō)，滿足約束條件的變量一般來(lái)說(shuō)，滿足約束條件的變量X=(x1,x2,xn)T有無(wú)窮多個(gè)解，求解有無(wú)窮多個(gè)解，求解LPLP問(wèn)問(wèn)題的目的就是從中找出一個(gè)能滿足目標(biāo)題的目的就是從中找出一個(gè)能滿足目標(biāo)函數(shù)最大或最小的解，作為該

7、函數(shù)最大或最小的解，作為該LPLP問(wèn)題的問(wèn)題的最終決策。最終決策。 決策變量、目標(biāo)函數(shù)、約束條件是決策變量、目標(biāo)函數(shù)、約束條件是LPLP模模型的三要素，其中后兩者都是關(guān)于前者型的三要素，其中后兩者都是關(guān)于前者的線性表達(dá)式；而的線性表達(dá)式；而LPLP模型就是由最優(yōu)化模型就是由最優(yōu)化的目標(biāo)函數(shù)和約束條件這兩部分構(gòu)成的。的目標(biāo)函數(shù)和約束條件這兩部分構(gòu)成的。二、線性規(guī)劃的圖解法 線性規(guī)劃的圖解法，就是借助幾何圖形來(lái)線性規(guī)劃的圖解法，就是借助幾何圖形來(lái)求解線性規(guī)劃問(wèn)題的一種方法。求解線性規(guī)劃問(wèn)題的一種方法。 圖解法的基本步驟：圖解法的基本步驟：1.1.可行域的確定可行域的確定 LPLP模型所有約束條件共

8、同構(gòu)成的圖形，稱模型所有約束條件共同構(gòu)成的圖形，稱為可行域圖形。為可行域圖形。2.2.目標(biāo)函數(shù)的等值線和最優(yōu)點(diǎn)的確定目標(biāo)函數(shù)的等值線和最優(yōu)點(diǎn)的確定F(0,6)x1+x2=6X1X2OB(4,2)C(2,3)E(8,0)G(0,6)Z=20Z=3x1+4x2A(6,0)x1+2x2=8x2=3D(0,3) 可以看到：當(dāng)沿法線方向平行移動(dòng)直線可以看到：當(dāng)沿法線方向平行移動(dòng)直線Z=Z=3x1+4x2至至B點(diǎn)時(shí)，點(diǎn)時(shí)，Z Z值在可行域值在可行域R R上就達(dá)到上就達(dá)到了最大值，從而確定了最大值，從而確定B點(diǎn)即為該點(diǎn)即為該LPLP問(wèn)題的問(wèn)題的最最優(yōu)點(diǎn)。優(yōu)點(diǎn)。 最優(yōu)點(diǎn)的坐標(biāo)值為最優(yōu)點(diǎn)的坐標(biāo)值為最優(yōu)解最優(yōu)解。

9、記為。記為X*=(x1*,x2*)T,X* *對(duì)應(yīng)的目標(biāo)函數(shù)值稱為對(duì)應(yīng)的目標(biāo)函數(shù)值稱為最優(yōu)最優(yōu)值，記為值，記為Z Z* *。 該實(shí)例的最優(yōu)解：該實(shí)例的最優(yōu)解：X X* *=(4,2)=(4,2)T T,Z,Z* *=20 =20 說(shuō)明說(shuō)明最優(yōu)生產(chǎn)方案是：生產(chǎn)甲產(chǎn)品最優(yōu)生產(chǎn)方案是：生產(chǎn)甲產(chǎn)品4 4件，乙產(chǎn)品件，乙產(chǎn)品2 2件，可獲得最大利潤(rùn)件，可獲得最大利潤(rùn)2020千元。千元。 LP問(wèn)題幾種可能的結(jié)果：?jiǎn)栴}幾種可能的結(jié)果：唯一解；唯一解；多多重解；重解；無(wú)界解；無(wú)界解；無(wú)可行解。無(wú)可行解。 唯一解：只有一個(gè)最優(yōu)點(diǎn)唯一解：只有一個(gè)最優(yōu)點(diǎn) 多重解：有些多重解：有些LP問(wèn)題最優(yōu)解可能不唯一，問(wèn)題最優(yōu)解

10、可能不唯一，如如:前例中目標(biāo)函數(shù)改為：前例中目標(biāo)函數(shù)改為：max Z=x1+2x2 則目標(biāo)函數(shù)等值線與約束條件則目標(biāo)函數(shù)等值線與約束條件x1+2x28的的邊界線平行。當(dāng)將等值線沿法線方向平移邊界線平行。當(dāng)將等值線沿法線方向平移到到B點(diǎn)時(shí)，就與點(diǎn)時(shí)，就與R的邊界線的邊界線BC段重合。這表段重合。這表明明BC上的每一點(diǎn)都使目標(biāo)函數(shù)值取得同樣上的每一點(diǎn)都使目標(biāo)函數(shù)值取得同樣的最大值。這時(shí)出現(xiàn)多重解的情形。的最大值。這時(shí)出現(xiàn)多重解的情形。 無(wú)界解：無(wú)界解：Max Z = 3xMax Z = 3x1 1 + 2x+ 2x2 2 -2x -2x1 1 + x + x2 2 2 2 x x1 1 - 3x-

11、 3x2 2 3 3 x x1 10, 0, x x2 2 00s.t.x1x2 無(wú)可行解：有些無(wú)可行解：有些LP問(wèn)題可能不存在可行點(diǎn)，問(wèn)題可能不存在可行點(diǎn)，也就是說(shuō)由約束條件得到的可行域也就是說(shuō)由約束條件得到的可行域R為空集，為空集，即即R=。這時(shí)問(wèn)題無(wú)可行解，也就無(wú)最優(yōu)。這時(shí)問(wèn)題無(wú)可行解，也就無(wú)最優(yōu)解了，簡(jiǎn)稱無(wú)解。解了，簡(jiǎn)稱無(wú)解。 LP問(wèn)題的可行域一般是凸多邊形，而且若問(wèn)題的可行域一般是凸多邊形，而且若最優(yōu)解存在，則一定在可行域的某個(gè)頂點(diǎn)最優(yōu)解存在，則一定在可行域的某個(gè)頂點(diǎn)上得到；若在兩個(gè)頂點(diǎn)同時(shí)得到最優(yōu)解，上得到；若在兩個(gè)頂點(diǎn)同時(shí)得到最優(yōu)解，則這兩個(gè)頂點(diǎn)連線上的每一點(diǎn)都是最優(yōu)解，則這兩個(gè)

12、頂點(diǎn)連線上的每一點(diǎn)都是最優(yōu)解，且最優(yōu)值相等；若可行域無(wú)界，則可能發(fā)且最優(yōu)值相等；若可行域無(wú)界，則可能發(fā)生最優(yōu)解無(wú)界的情況，此時(shí)無(wú)最優(yōu)解。若生最優(yōu)解無(wú)界的情況，此時(shí)無(wú)最優(yōu)解。若可行域?yàn)榭占瑒t問(wèn)題無(wú)可行解。可行域?yàn)榭占?，則問(wèn)題無(wú)可行解。三、線性規(guī)劃的標(biāo)準(zhǔn)形式 LP問(wèn)題的各種不問(wèn)題的各種不同形式可以相互同形式可以相互轉(zhuǎn)化，只需給出轉(zhuǎn)化，只需給出其中一種形式的其中一種形式的解法，就可以普解法，就可以普遍適用于一切形遍適用于一切形式的式的LP問(wèn)題，而問(wèn)題，而單純形法所基于單純形法所基于的的LP問(wèn)題的形式，問(wèn)題的形式，稱為標(biāo)準(zhǔn)形式。稱為標(biāo)準(zhǔn)形式。1.1.線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式mib

13、nixbxaxaxabxaxaxabxaxaxatsxcxcxcziimnmnmmnnnnnn, 2 , 10, 2 , 10. .max221122222121112121112211A=（aij）mn為約束方程組的系數(shù)陣。R(A)=mn,即A為滿秩陣，稱m為L(zhǎng)P問(wèn)題的階數(shù)，n為維數(shù)njxmibxatsxczjnjijijnjjj, 2 , 1, 0, 2 , 1,. .max11mnmnmmnnnTTbbbbxxxXaaaaaaaaaAcccCXbAXtsXCZ212121222211121121,0. .max其中： 目標(biāo)函數(shù)目標(biāo)函數(shù) min Z=CTX 函數(shù)約束函數(shù)約束b bi i0

14、0 兩端乘以兩端乘以-1-1約束為約束為“”“”的情況，增加非負(fù)變量的情況，增加非負(fù)變量 松弛變量松弛變量約束為約束為“”“”的情況，減去非負(fù)變量的情況，減去非負(fù)變量剩余變量剩余變量 決策變量決策變量對(duì)不滿足非負(fù)性要求的變量，采用對(duì)不滿足非負(fù)性要求的變量，采用“變量代換變量代換法法”2.2.非標(biāo)準(zhǔn)形非標(biāo)準(zhǔn)形LPLP問(wèn)題的標(biāo)準(zhǔn)化問(wèn)題的標(biāo)準(zhǔn)化舉例：1221 xx1221xx0,36431228. .00053max521521423154321xxxxxxxxxxtsxxxxxz0036431228. .53max21212121xxxxxxtsxxz0, 01361532324312. .23m

15、in212121212121xxxxxxxxxxtsxxz0,151532324312. .23max543212152142132121xxxxxxxxxxxxxxxxtsxxz 如果xk0,可令xk=- xk ， xk 0。 如果xk為自由變量，可令xk=xk_xk，且xk0，xk0。 如果方程中有多個(gè)xk為自由變量，按照上述方法會(huì)使變量的個(gè)數(shù)擴(kuò)大一倍，從而增加問(wèn)題求解時(shí)的計(jì)算量，為了盡量少地增加變量的個(gè)數(shù)，可以令xk=xk-x“，其中x“對(duì)每個(gè)xk的表達(dá)式都是同一個(gè)數(shù)。變量代換法四、四、 線性規(guī)劃的解及其性質(zhì)線性規(guī)劃的解及其性質(zhì) 可行解：滿足可行解：滿足LP問(wèn)題所有約束條件的向量問(wèn)題所有

16、約束條件的向量X 可行域可行域所有可行解構(gòu)成的集合所有可行解構(gòu)成的集合 最優(yōu)解：滿足目標(biāo)要求的可行解，記為最優(yōu)解：滿足目標(biāo)要求的可行解，記為X*，其所對(duì)應(yīng)的目標(biāo)函數(shù)值稱為最優(yōu)值，記為其所對(duì)應(yīng)的目標(biāo)函數(shù)值稱為最優(yōu)值，記為z*。 基本解：基本解的概念只適用于標(biāo)準(zhǔn)型基本解：基本解的概念只適用于標(biāo)準(zhǔn)型LP問(wèn)題。問(wèn)題。 基向量和非基向量：基向量和非基向量：A=(aij)mn=(P1 P2 Pn)為線性規(guī)劃問(wèn)題為線性規(guī)劃問(wèn)題LP的約束條件系數(shù)矩陣，其秩為的約束條件系數(shù)矩陣，其秩為m。則。則A中任中任一組一組m個(gè)線性無(wú)關(guān)的列向量構(gòu)成的矩陣個(gè)線性無(wú)關(guān)的列向量構(gòu)成的矩陣B=(Pji pj2 Pjm)非奇異，稱此

17、非奇異，稱此m個(gè)線性個(gè)線性無(wú)關(guān)的列向量為線性規(guī)劃問(wèn)題的一個(gè)無(wú)關(guān)的列向量為線性規(guī)劃問(wèn)題的一個(gè)基基。如果約束矩陣如果約束矩陣A中某一列向量中某一列向量Pj包含于基包含于基B中，中，則稱則稱Pj為為基向量基向量，否則稱為，否則稱為非基向量非基向量。對(duì)于給定的一個(gè)基，整個(gè)矩陣對(duì)于給定的一個(gè)基，整個(gè)矩陣A可以分為兩可以分為兩部分，即可表示為部分，即可表示為A=(B N) 基變量與非基變量：基變量與非基變量：與基向量與基向量Pjt(t=1,2,m)相對(duì)應(yīng)的變量相對(duì)應(yīng)的變量xjt稱為稱為基變量，否則稱為非基變量?；兞浚駝t稱為非基變量。LP問(wèn)題的變量問(wèn)題的變量也自然被相應(yīng)地分成了兩部分也自然被相應(yīng)地分成了

18、兩部分X=(xB xN)T 基本解：基本解：在在LP問(wèn)題中，滿足條件問(wèn)題中，滿足條件AX=b且非且非基變量全部為零的基變量全部為零的X成為基本解。成為基本解。 X=(xB xN)T=(xB 0)T AX=(B N) (xB xN)T=BxB+NxN=b 即基本解即基本解X可以用基變量部分來(lái)表示成可以用基變量部分來(lái)表示成xB=B-1b 基本可行解：基本可行解：滿足非負(fù)條件的基本解，或者滿足非負(fù)條件的基本解，或者說(shuō)說(shuō)xB=B-1b00就稱其為基本可行解。就稱其為基本可行解?；窘饣窘饪尚薪饪尚薪饣究尚薪饣究尚薪饧s束矩陣約束矩陣A中中基的數(shù)目最多基的數(shù)目最多為為Cnm，因而，因而基本解的個(gè)數(shù)基

19、本解的個(gè)數(shù)最多也只能有最多也只能有Cnm個(gè)，所以個(gè)，所以基本可行解的基本可行解的個(gè)數(shù)也不會(huì)超個(gè)數(shù)也不會(huì)超過(guò)過(guò)Cnm 退化基本解：如果基本解中有一個(gè)或者多退化基本解：如果基本解中有一個(gè)或者多個(gè)基變量為零，則稱為退化基本解個(gè)基變量為零，則稱為退化基本解 可行基：基本可行解對(duì)應(yīng)的基可行基：基本可行解對(duì)應(yīng)的基 最優(yōu)基：最優(yōu)基本解對(duì)應(yīng)的基最優(yōu)基：最優(yōu)基本解對(duì)應(yīng)的基 標(biāo)準(zhǔn)形標(biāo)準(zhǔn)形LP問(wèn)題的任一基本可行解，其所含問(wèn)題的任一基本可行解，其所含正分量的個(gè)數(shù)比不超過(guò)問(wèn)題的階數(shù)正分量的個(gè)數(shù)比不超過(guò)問(wèn)題的階數(shù)m，而，而一個(gè)非退化的基本可行解必恰有一個(gè)非退化的基本可行解必恰有m個(gè)正分個(gè)正分量，其余分量均為量，其余分量均

20、為0。標(biāo)準(zhǔn)形LP問(wèn)題解的概念與關(guān)系解解滿足條件滿足條件適用適用對(duì)象對(duì)象備注備注可行解可行解XAX=bX0各種形各種形式的式的LP問(wèn)題問(wèn)題最優(yōu)解最優(yōu)解X*AX*=b X*0CTX*=optCTX基本解基本解X=(xB xN)TAX=b|B|0,XN=0標(biāo)準(zhǔn)形標(biāo)準(zhǔn)形LP問(wèn)題問(wèn)題XB所含所含分量個(gè)分量個(gè)數(shù)恰為數(shù)恰為階數(shù)階數(shù)m，XN含含n-m個(gè)個(gè)0分分量量基本可行解基本可行解X=(xB xN)TAX=bXB0|B|0,XN=0線性規(guī)劃解的性質(zhì)線性規(guī)劃解的性質(zhì) 性質(zhì)性質(zhì)1：LP問(wèn)題的可行域問(wèn)題的可行域R為一凸集為一凸集 性質(zhì)性質(zhì)2：LP問(wèn)題的一個(gè)基本可行解與可行域問(wèn)題的一個(gè)基本可行解與可行域R的一的一個(gè)

21、極點(diǎn)互相對(duì)應(yīng)個(gè)極點(diǎn)互相對(duì)應(yīng) 性質(zhì)性質(zhì)3：線性規(guī)劃的基本定理：對(duì)于任何一個(gè)給定：線性規(guī)劃的基本定理：對(duì)于任何一個(gè)給定的標(biāo)準(zhǔn)形的標(biāo)準(zhǔn)形LP問(wèn)題問(wèn)題M來(lái)說(shuō)，若來(lái)說(shuō)，若M有可行解，則必有有可行解，則必有基本可行解；如基本可行解；如M有最優(yōu)解，則必有最優(yōu)基本可行有最優(yōu)解，則必有最優(yōu)基本可行解。解。 性質(zhì)性質(zhì)4：若：若LP問(wèn)題的可行域問(wèn)題的可行域R，則，則R至少有一極至少有一極點(diǎn)點(diǎn) 性質(zhì)性質(zhì)5：LP問(wèn)題可行域問(wèn)題可行域R的極點(diǎn)數(shù)量必為有限多個(gè)的極點(diǎn)數(shù)量必為有限多個(gè)五、線性規(guī)劃的單純形法五、線性規(guī)劃的單純形法 單純形法的基本思想單純形法的基本思想 單純形法有三種形式：?jiǎn)渭冃畏ㄓ腥N形式：方程組形式方程組形式

22、 表格形式表格形式 矩陣形式矩陣形式 單純形法的計(jì)算過(guò)程單純形法的計(jì)算過(guò)程 單純形表單純形表單純形法的基本思想單純形法的基本思路：?jiǎn)渭冃畏ǖ幕舅悸罚?求出可行域求出可行域S S的一個(gè)基本可行解的一個(gè)基本可行解 判別這個(gè)基本可行解是否為最有解判別這個(gè)基本可行解是否為最有解 在使得目標(biāo)函數(shù)值有所改進(jìn)的前提下進(jìn)在使得目標(biāo)函數(shù)值有所改進(jìn)的前提下進(jìn)行頂點(diǎn)的轉(zhuǎn)換行頂點(diǎn)的轉(zhuǎn)換 重復(fù)上述過(guò)程，通過(guò)有限步來(lái)求解重復(fù)上述過(guò)程，通過(guò)有限步來(lái)求解LPLP問(wèn)題。問(wèn)題。范例說(shuō)明范例說(shuō)明Max Z z 3x1 5x2 =0 x1 + x 3 =8 2x2 + x4 =12 3x1 +4x2 +x5 =36 x1, x2

23、, x3 , x4 ,x5 00 約束方程系數(shù)陣：約束方程系數(shù)陣：54321,100430102000101aaaaaA有一個(gè)基有一個(gè)基的非退化的基本可行解為: X0=(0,0,8,12,36)T543100010001aaaB 條典：條典： 基本可行解對(duì)應(yīng)的可行基是一個(gè)基本可行解對(duì)應(yīng)的可行基是一個(gè)m階單階單位陣（排列陣）位陣（排列陣） 目標(biāo)方程中所有基變量的系數(shù)全為目標(biāo)方程中所有基變量的系數(shù)全為0 典式：典式：滿足條典的線性方程組滿足條典的線性方程組 檢驗(yàn)數(shù)：檢驗(yàn)數(shù)：當(dāng)目標(biāo)方程中基變量的系數(shù)全為當(dāng)目標(biāo)方程中基變量的系數(shù)全為0時(shí)，非基變量的系數(shù)可以作為判斷當(dāng)前基時(shí)，非基變量的系數(shù)可以作為判斷當(dāng)

24、前基本可行解是否最優(yōu)的一個(gè)標(biāo)志，稱檢驗(yàn)數(shù)本可行解是否最優(yōu)的一個(gè)標(biāo)志，稱檢驗(yàn)數(shù) 只要目標(biāo)方程中存在負(fù)檢驗(yàn)數(shù)，就意味著只要目標(biāo)方程中存在負(fù)檢驗(yàn)數(shù)，就意味著目標(biāo)值還能增加，就需要把它對(duì)應(yīng)的非基目標(biāo)值還能增加，就需要把它對(duì)應(yīng)的非基變量變換為基變量。變量變換為基變量。 進(jìn)基變量選擇的規(guī)則進(jìn)基變量選擇的規(guī)則最小檢驗(yàn)數(shù)規(guī)則最小檢驗(yàn)數(shù)規(guī)則 在負(fù)檢驗(yàn)數(shù)中選擇數(shù)值最小者，讓它對(duì)應(yīng)在負(fù)檢驗(yàn)數(shù)中選擇數(shù)值最小者，讓它對(duì)應(yīng)的非基變量進(jìn)基。即：的非基變量進(jìn)基。即： 如果記檢驗(yàn)數(shù)為如果記檢驗(yàn)數(shù)為j j（j=1,2, nj=1,2, n）包括基）包括基變量的檢驗(yàn)數(shù)（全為變量的檢驗(yàn)數(shù)（全為0 0）那么可用數(shù)學(xué)表達(dá)）那么可用數(shù)學(xué)表

25、達(dá)式表示：式表示： minminj j| | j j0= 0= bl/alk 確定主元確定主元alk，同時(shí)也確定，同時(shí)也確定l行的基變量離基。行的基變量離基。 基本可行解的變換基本可行解的變換矩陣初等變換矩陣初等變換68X1X2OABCDE(12,0)G(0,9)F(8,6)Z=42單純形法的單純形法的幾何意義幾何意義單純形法的計(jì)算過(guò)程單純形法的計(jì)算過(guò)程單純形表單純形表CjCjC1 C2 Cm Cm+1 Cn比值比值基基解解x1 x2 xm xm+1 xnC1C2Cmx1x2xmb1b2bm1 0 0 a1,m+1 a1n0 1 0 a2,m+1 a2n. 0 0 1 am,m+1 amn檢驗(yàn)

26、行檢驗(yàn)行z00 0 0 m+1m+1 mnmn單純形法的計(jì)算步驟單純形法的計(jì)算步驟1.把把LP問(wèn)題化成標(biāo)準(zhǔn)型問(wèn)題化成標(biāo)準(zhǔn)型2.在系數(shù)陣中找出或構(gòu)造出一個(gè)在系數(shù)陣中找出或構(gòu)造出一個(gè)m階排列矩陣作為初始階排列矩陣作為初始可行基，建立初始單純形表可行基，建立初始單純形表3.若所有檢驗(yàn)數(shù)若所有檢驗(yàn)數(shù)j0，得到一個(gè)最優(yōu)基本解，停止運(yùn)算，得到一個(gè)最優(yōu)基本解，停止運(yùn)算，否則轉(zhuǎn)否則轉(zhuǎn)44.在所有在所有j0中，只要有一個(gè)中，只要有一個(gè)r0所對(duì)應(yīng)的系數(shù)列向量所對(duì)應(yīng)的系數(shù)列向量ar0,即一切即一切air0,則該問(wèn)題無(wú)最優(yōu)解，停止運(yùn)算，否則該問(wèn)題無(wú)最優(yōu)解，停止運(yùn)算，否則轉(zhuǎn)則轉(zhuǎn)55.按最小檢驗(yàn)數(shù)規(guī)則按最小檢驗(yàn)數(shù)規(guī)則mi

27、nminj j| | j j0= 0= K K確定進(jìn)基變確定進(jìn)基變量量x xk k和主列和主列a ak k，再按最小比值規(guī)則，再按最小比值規(guī)則min bi/aik | aik0= bl/alk 確定主元確定主元alk，同時(shí)也確定，同時(shí)也確定l行的基變量離基。行的基變量離基。6.以以ak為主元對(duì)當(dāng)前表格進(jìn)行一次換基運(yùn)算，得到一個(gè)為主元對(duì)當(dāng)前表格進(jìn)行一次換基運(yùn)算，得到一個(gè)新的單純形表的形式。新的單純形表的形式。CjCj3 5 0 0 0 比值比值基基解解x1 x2 x3 x4 x5000 x3x4x5812 361 0 1 0 00 2 0 1 03 4 0 0 1-12/236/4檢驗(yàn)行檢驗(yàn)行

28、0-3 -5 0 0 0CjCj3 5 0 0 0 比值比值基基解解x1 x2 x3 x4 x5050 x3x2x586121 0 1 0 00 1 0 1/2 03 0 0 -2 18-4檢驗(yàn)行檢驗(yàn)行 30 -3 0 0 5/2 0CjCj3 5 0 0 0 比值比值基基解解x1 x2 x3 x4 x5053x3x2x146 40 0 1 2/3 -1/30 1 0 1/2 01 0 0 -2/3 1/3檢驗(yàn)行檢驗(yàn)行 42 0 0 0 1/2 1人工變量法人工變量法 單純形法要求先從系數(shù)陣中找出一個(gè)m階排列陣，這往往不容易做到，特別對(duì)于系數(shù)陣A為降秩陣的LP問(wèn)題，根本就找不出；還有些LP問(wèn)題

29、本身并沒(méi)有可行解，當(dāng)然也就找不出基本可行解。但由于問(wèn)題的形式比較復(fù)雜，往往不易判斷。 采用人工變量法可以解決上述問(wèn)題。mibnixbxaxaxabxaxaxabxaxaxatsxcxcxcziimnmnmmnnnnnn, 2 , 10, 2 , 10. .max221122222121112121112211A分別給每個(gè)約束方程硬行加入一個(gè)非負(fù)變量分別給每個(gè)約束方程硬行加入一個(gè)非負(fù)變量xn+1，xn+2，xn+m，得到，得到mibmnixbxxaxaxabxxaxaxabxxaxaxatsxcxcxcziimmnnmnmmnnnnnnnn, 2 , 10, 2 , 10. .max221122

30、22221211112121112211B這樣，以這樣，以xn+1，xn+2，xn+m為基變量，可以得到為基變量，可以得到如下的一個(gè)初始基本可行解：如下的一個(gè)初始基本可行解：X0=(0,0,0,b1,b2,bm)T這個(gè)解這個(gè)解X0完全是人為地加入完全是人為地加入m個(gè)變量而得到的，因此個(gè)變量而得到的，因此稱為人造基本解，而把變量稱為人造基本解，而把變量xn+1，xn+2，xn+m稱稱為人工變量。為人工變量。人造解人造解X0顯然不是原顯然不是原LP問(wèn)題問(wèn)題A的基本可行解，但是若的基本可行解，但是若能通過(guò)單純形法的迭代步驟將虛擬的人工變量全部從能通過(guò)單純形法的迭代步驟將虛擬的人工變量全部從基中替換出去，這時(shí)可以得到一個(gè)基本解基中替換出去，這時(shí)可以得到一個(gè)基本解Xk，不僅滿，不僅滿足式足式B,而且由于人工變量而且由于人工變量xn+1=xn+2=xn+m=0，因，因此此Xk的前的前n個(gè)分量就構(gòu)成了原個(gè)分量就構(gòu)成了原LP問(wèn)題的一個(gè)基本可行問(wèn)題的一個(gè)基本可行解。如果經(jīng)過(guò)迭代不能將人工變量變?yōu)榉腔兞浚瑒t解。如果經(jīng)過(guò)迭代不能將人工變量變?yōu)榉腔兞浚瑒t