線性規(guī)劃與單純形法ppt課件

1、 線性規(guī)劃與單純形法 線性規(guī)劃 LP： Linear Programming 規(guī)劃論中的靜態(tài)規(guī)劃 處理有限資源的最正確分配問題 求解方法： 圖解法 單純形解法 線性規(guī)劃簡介 19391939年蘇聯(lián)的康托洛維奇年蘇聯(lián)的康托洛維奇H.B.Kahtopob H.B.Kahtopob 和美國的希奇和美國的希奇柯克柯克F.L.HitchcockF.L.Hitchcock等人就在消費(fèi)組織管理和制定交通等人就在消費(fèi)組織管理和制定交通運(yùn)輸方案方面首先研討和運(yùn)用一線性規(guī)劃方法。運(yùn)輸方案方面首先研討和運(yùn)用一線性規(guī)劃方法。 19471947年旦茨格等人提出了求解線性規(guī)劃問題的單純形法，年旦茨格等人提出了求解線性規(guī)劃

2、問題的單純形法，為線性規(guī)劃的實(shí)際與計(jì)算奠定了根底。為線性規(guī)劃的實(shí)際與計(jì)算奠定了根底。 隨著電子計(jì)算機(jī)的出現(xiàn)和日益完善，規(guī)劃論得到迅速的開隨著電子計(jì)算機(jī)的出現(xiàn)和日益完善，規(guī)劃論得到迅速的開展，可用電子計(jì)算機(jī)來處置成千上萬個約束條件和變量的展，可用電子計(jì)算機(jī)來處置成千上萬個約束條件和變量的大規(guī)模線性規(guī)劃問題，從處理技術(shù)問題的最優(yōu)化，到工業(yè)、大規(guī)模線性規(guī)劃問題，從處理技術(shù)問題的最優(yōu)化，到工業(yè)、農(nóng)業(yè)、商業(yè)、交通運(yùn)輸業(yè)以及決策分析部門都可以發(fā)揚(yáng)作農(nóng)業(yè)、商業(yè)、交通運(yùn)輸業(yè)以及決策分析部門都可以發(fā)揚(yáng)作用。用。線性規(guī)劃問題的三個要素線性規(guī)劃問題的三個要素 決策變量 決策問題待定的量值稱為決策變量。 決策變量的取

3、值要求非負(fù)。 約束條件 任何問題都是限定在一定的條件下求解，把各種限制條件表示為一組等式或不等式，稱之為約束條件。 約束條件是決策方案可行的保證。 LP的約束條件，都是決策變量的線性函數(shù)。 目的函數(shù) 衡量決策方案優(yōu)劣的準(zhǔn)那么，如時間最省、利潤最大、本錢最低。 目的函數(shù)是決策變量的線性函數(shù)。 有的目的要實(shí)現(xiàn)極大，有的那么要求極小。1線性規(guī)劃問題及其數(shù)學(xué)模型 設(shè)設(shè) 備備原原料料A A原原料料B B 1 4 0 2 0 4 8臺時 16kg 12kg例 某工廠在方案期內(nèi)要安排消費(fèi)、兩種產(chǎn)品，知消費(fèi)單位產(chǎn)品所需的設(shè)備臺時和原料A、B的耗費(fèi)量如下表。 該工廠每消費(fèi)一件產(chǎn)品可獲利2元，每消費(fèi)一件產(chǎn)品可獲利

4、3元，問應(yīng)如何安排消費(fèi)方案能使該廠獲利最多？ 這個問題可以用下面的數(shù)學(xué)模型來描畫，設(shè)方案期內(nèi)產(chǎn)品、的產(chǎn)量分別為x1，x2，可獲利潤用z表示，那么有：Max Z=2x1+3x2x1+2x284x1 16 4x212x1, x201.1問題的提出問題的提出又例又例 接近某河流有兩個化工廠，接近某河流有兩個化工廠，流經(jīng)第一化工廠的河流流量為每天流經(jīng)第一化工廠的河流流量為每天500萬萬m3，兩工廠之間有一條流量，兩工廠之間有一條流量為每天為每天200萬萬m3的支流見圖。的支流見圖。 第一化工廠每天排放污水第一化工廠每天排放污水2萬萬m3，第二化工廠每，第二化工廠每天排放污水天排放污水 1.4萬萬m3。

5、污水從工廠。污水從工廠1流到工廠流到工廠2前前會有會有20%自然凈化。根據(jù)環(huán)保要求，河水中污水自然凈化。根據(jù)環(huán)保要求，河水中污水的含量應(yīng)不大于的含量應(yīng)不大于0.2%。而工廠。而工廠1和工廠和工廠2處置污處置污水的本錢分別為水的本錢分別為1000元元/萬萬m3和和800元元/萬萬m3。問。問兩工廠各應(yīng)處置多少污水才干使處置污水的總費(fèi)兩工廠各應(yīng)處置多少污水才干使處置污水的總費(fèi)用最低？用最低？ 設(shè)工廠設(shè)工廠1和工廠和工廠2每每天分別處置污水天分別處置污水x1和和x2萬萬m3，那么有：，那么有：Min z=1000 x1+800 x2 (2-x1)/500 0.0020.8(2-x1)+1.4-x2/

6、700 0.002 x12, x21.4 x1, x20以上兩例都有一些共同的特征：以上兩例都有一些共同的特征：用一組變量表示某個方案，普用一組變量表示某個方案，普通這些變量取值是非負(fù)的。通這些變量取值是非負(fù)的。存在一定的約束條件，可以用存在一定的約束條件，可以用線性等式或線性不等式來表示。線性等式或線性不等式來表示。都有一個要到達(dá)的目的，可以都有一個要到達(dá)的目的，可以用決策變量的線性函數(shù)來表示。用決策變量的線性函數(shù)來表示。 滿足以上條件的數(shù)學(xué)模型稱為線性規(guī)劃模型。線性規(guī)劃模型的普通方式如下：0,),(),(),(max(min)21221122222121112121112211nmnmnm

7、mnnnnnnxxxbxaxaxabxaxaxabxaxaxaxcxcxcz其中：其中：cj為價值系數(shù)；為價值系數(shù)；aij為技術(shù)系數(shù)；為技術(shù)系數(shù)；bi為限額系數(shù)；為限額系數(shù)；xj為非負(fù)變量為非負(fù)變量 圖解法即是用圖示的方法來求解線性規(guī)劃問圖解法即是用圖示的方法來求解線性規(guī)劃問題。題。 一個二維的線性規(guī)劃問題，可以在平面圖上一個二維的線性規(guī)劃問題，可以在平面圖上求解，三維的線性規(guī)劃那么要在立體圖上求求解，三維的線性規(guī)劃那么要在立體圖上求解，這就比較費(fèi)事，而維數(shù)再高以后就不能解，這就比較費(fèi)事，而維數(shù)再高以后就不能圖示了。圖示了。1.2線性規(guī)劃的圖解法線性規(guī)劃的圖解法可行域確實(shí)定可行域確實(shí)定 例例:

8、數(shù)學(xué)模型為數(shù)學(xué)模型為 maxZ= 3x1 +5 x2 x1 8 2x2 12 3x1 +4 x2 36 x1 0, x2 0S.t.x1 =82x2 =123x1 +4 x2 =36x1x24812369 五邊形五邊形OABCD內(nèi)內(nèi)(含邊境含邊境)的恣意一點(diǎn)的恣意一點(diǎn) (x1，x2) 都是滿足一切都是滿足一切約束條件的一個解，稱之可行解約束條件的一個解，稱之可行解 。 滿足一切約束條件的解的集合，稱之為可行域。即一切約束滿足一切約束條件的解的集合，稱之為可行域。即一切約束條件共同圍城的區(qū)域。條件共同圍城的區(qū)域。最優(yōu)解確實(shí)定最優(yōu)解確實(shí)定Z=30Z=42Z=15 目的函數(shù) Z= 3x1 +5 x2

9、 代表以Z為參數(shù)的一族平行線。x1 =82x2 =123x1 +4 x2 =36x1x24812369 等值線：位于同不斷線上的點(diǎn)的目的函數(shù)值一樣。等值線：位于同不斷線上的點(diǎn)的目的函數(shù)值一樣。 最優(yōu)解：可行解中使目的函數(shù)最優(yōu)最優(yōu)解：可行解中使目的函數(shù)最優(yōu)(極大或極小極大或極小)的解的解 由線性不等式組成的可行域是凸集由線性不等式組成的可行域是凸集(凸集的定凸集的定義是：集合內(nèi)部恣意兩點(diǎn)連線上的點(diǎn)都屬于這義是：集合內(nèi)部恣意兩點(diǎn)連線上的點(diǎn)都屬于這個集合個集合)。 可行域有有限個頂點(diǎn)。設(shè)規(guī)劃問題有可行域有有限個頂點(diǎn)。設(shè)規(guī)劃問題有n個變量，個變量，m個約束，那么頂點(diǎn)的個數(shù)不多于個約束，那么頂點(diǎn)的個數(shù)不

10、多于Cnm個。個。 目的函數(shù)最優(yōu)值一定在可行域的邊境到達(dá)，而目的函數(shù)最優(yōu)值一定在可行域的邊境到達(dá)，而不能夠在其內(nèi)部。不能夠在其內(nèi)部。幾點(diǎn)闡明幾點(diǎn)闡明解的能夠性解的能夠性x1 =82x2 =123x1 +4 x2 =36x1x24812369上例的數(shù)學(xué)模型變?yōu)樯侠臄?shù)學(xué)模型變?yōu)?maxZ= 3x1 +4 x2 x1 8 2x2 12 3x1 +4 x2 36 x1 0, x2 0S.t.Z=24Z=36Z=12 獨(dú)一最優(yōu)解：只需一個最優(yōu)點(diǎn)。 多重最優(yōu)解：無窮多個最優(yōu)解。假設(shè)在兩個頂點(diǎn)同時得到最優(yōu)解，那么它們連線上的每一點(diǎn)都是最優(yōu)解。 無界解：線性規(guī)劃問題的可行域無界，使目的函數(shù)無限增大而無界。缺

11、乏必要的約束條件例如例如 maxZ= 3x1 +2 x2 -2x1 + x2 2 x1 -3 x2 3 x1 0, x2 0-2x1 + x2 =2x1 -3 x2 =3x2123-1x1123-1Z=6Z=12S.t. 無可行解：假設(shè)約束條件相互矛盾，那么可行域?yàn)榭占缋?maxZ= 3x1 +2 x2 -2x1 + x2 2 x1 -3 x2 3 x1 0, x2 0-2x1 + x2 =2x1 -3 x2 =3x2123-1x1123-1S.t.獨(dú)一最優(yōu)解無窮多最優(yōu)解x1x2x1x2無界解無可行解當(dāng)線性規(guī)劃的可行域非空它是有界或無界凸多邊形，假設(shè)存在最優(yōu)解，那么最優(yōu)解一定在可行域的的

12、某個頂點(diǎn)或頂點(diǎn)的連線獲得，也即有獨(dú)一最優(yōu)解或無窮多最優(yōu)解圖解法雖然簡單直觀，但是只能處理兩個變量練習(xí):用圖解法求解以下LP模型無符號限制21212121,2322265maxxxxxxxxxzAnswerx1x2-2x1+3x2=2x1-2x2=20Ax1= -10,x2= -6,z= -861.3 線性規(guī)劃的規(guī)范型 線性規(guī)劃問題的數(shù)學(xué)模型有各種不同的方式，如 目的函數(shù)有極大化和極小化； 約束條件有“、“和“三種情況； 決策變量普通有非負(fù)性要求，有的那么沒有。 為了求解方便，特規(guī)定一種線性規(guī)劃的規(guī)范方式，非規(guī)范型可以轉(zhuǎn)化為規(guī)范型。規(guī)范方式為： 目的函數(shù)極大化 約束條件為等式 右端常數(shù)項(xiàng)bi0

13、決策變量非負(fù)。一一 、規(guī)范型、規(guī)范型1. 代數(shù)式二、規(guī)范型的表達(dá)方式二、規(guī)范型的表達(dá)方式 有代數(shù)式、矩陣式：有代數(shù)式、矩陣式：maxZ=c1x1+c2x2+cnxn a11x1+a12x2+a1nxn b1 a21x1+a22x2+a2nxn b2 am1x1+am2x2+amnxnbm x1,x2,xn 0maxZ= cjxj aijxjbi ( i=1,2,m) xj0 ( j=1,2,n)nj1nj1簡記2. 矩陣式矩陣式 0. .maxXbAXtsXCZ),(21ncccC價值向量mnmmnnaaaaaaaaaA212222111211技術(shù)矩陣mbbbb21資源向量nxxxX21決策向

14、量三、非規(guī)范型向規(guī)范型轉(zhuǎn)化三、非規(guī)范型向規(guī)范型轉(zhuǎn)化 規(guī)范型 例例1 maxZ= 3x1 +5 x2 x1 8 2x2 12 3x1 +4 x2 36 x1 0, x2 0S.t. x1 +x3 =8 2x2 +x4 = 12 3x1 +4 x2 +x5= 36 x1, x2 , x3 , x4 , x5 0 maxZ= 3x1 +5 x2 +0 x3 +0 x4+0 x5 minZ= x1 +2 x2 +3 x3 x1 +2 x2 + x35 2x1 +3 x2 + x36 -x1 - x2 - x3 -2 x1 0, x30 例例2 minZ= x1 +2 x2 -3 x3 x1 +2 x2

15、 - x3 5 2x1 +3 x2 - x3 6 -x1 - x2 + x3 -2 x1 0, x3 0 規(guī)范化規(guī)范化1S.t. 規(guī)范化規(guī)范化2 minZ= x1 +2 (x2-x 2) +3 x3 x1 +2 (x2-x 2) + x35 2x1 +3 (x2-x 2) + x36 - x1 - (x2-x 2) - x3 -2 x1, x2,x 2 , x3 0 規(guī)范化規(guī)范化3 minZ= x1 +2 (x2-x 2 ) +3 x3 x1 +2 (x2-x 2 ) + x35 2x1 +3 (x2-x 2 ) + x36 x1 + (x2-x 2 ) + x3 2 x1, x2, x 2,

16、 x3 0 規(guī)范化規(guī)范化4 minZ= x1 +2 (x2-x 2) +3 x3 x1 +2 (x2-x 2) + x3+ x4 =5 2x1 +3 (x2-x 2) + x36 x1 + (x2-x 2 ) + x3 2 x1, x2, x 2, x3, x4 0 規(guī)范化規(guī)范化5 minZ= x1 +2 (x2-x 2) +3 x3 x1 +2 (x2-x 2) + x3+ x4 =5 2x1 +3 (x2-x 2) + x3 - x5 = 6 x1 + (x2-x 2 ) + x3 2 x1, x2, x 2, x3, x4 , x5 0 規(guī)范化規(guī)范化6 minZ= x1 +2 (x2-x

17、 2) +3 x3 x1 +2 (x2-x 2) + x3+ x4 =5 2x1 +3 (x2-x 2) + x3 - x5 = 6 x1 + (x2-x 2 ) - x3 + x6= 2 x1, x2, x 2, x3, x4 , x5 , x6 0 規(guī)范化規(guī)范化7 maxZ= -x1 -2 (x2-x 2) - 3x3+0 x4+0 x5+0 x6 x1 +2 (x2-x 2) + x3+ x4 =5 2x1 +3 (x2-x 2) + x3 - x5 = 6 x1 + (x2-x 2 ) - x3 + x6 = 2 x1, x2, x 2, x3, x4 , x5 , x6 0 可行解：

18、 滿足約束條件AX=b, X0的解。 最優(yōu)解： 使目的函數(shù)到達(dá)最大的可行解，稱為最優(yōu)解。 基 設(shè)A是約束方程組的mn維系數(shù)矩陣，其秩為m，B是矩陣A中的mm階非奇特子矩陣，那么稱B是線性規(guī)劃問題的一個基。 mn，且m個方程線性無關(guān)，即矩陣A的秩為m；根據(jù)線性代數(shù)定理可知，nm，那么方程組有多個解，這也正是線性規(guī)劃尋求最優(yōu)解的余地所在。 一、線性規(guī)劃解的概念一、線性規(guī)劃解的概念 1.4 線性規(guī)劃問題的解的概念線性規(guī)劃問題的解的概念 線性方程組的增廣矩陣 例例 maxZ= 3x1 +5 x2 +0 x3 +0 x4+0 x5 x1 +x3 =8 2x2 +x4 = 12 3x1 +4 x2 +x5

19、= 36 x1, x2 , x3 , x4 , x5 036101201800043020101Ax1x2x3x4x5 基矩陣： 系數(shù)矩陣A中恣意m列所組成的m階非奇特子矩陣，稱為該線性規(guī)劃問題的一個基矩陣。 或稱為一個基，用B表示。 稱基矩陣的列為基向量，用Pj表示(j=1,2,m) 。100100043020101A的基矩陣的基矩陣B最多最多C53=10，如下：，如下：100010001x3x4 x5103010001x1x4 x5104012000 x2x4 x5130000011x3x1 x5140020001x3x2 x5300010101x3x4 x1400210001x3x4 x

20、2043020101x1x2 x5x1x2 x4043120001x1x2 x5143020001 基變量： 與基向量Pj相對應(yīng)的m個變量xj稱為基變量， 其他的m-n個變量為非基變量。 基解： 令一切非基變量等于零，對m個基變量所求的解 對應(yīng)一個特定的基矩陣能求得一組獨(dú)一解，這個對應(yīng)于基的解稱為基解。 結(jié)合圖解來看，基解是各約束方程及坐標(biāo)軸之間交點(diǎn)的坐標(biāo)。 100010001Bx3x4x5基變量是基變量是x3, x4, x5非基變量是非基變量是x1, x2令非基變量令非基變量x1=x2=0，得到一個基解，得到一個基解 x3=8，x4=12， x5=36 基可行解：滿足非負(fù)性約束的基解稱為基可

21、行解。 可行基：對應(yīng)于基可行解的基，稱為可行基。 最優(yōu)基：最優(yōu)解對應(yīng)的基矩陣，稱為最優(yōu)基。 可行解基解基可行解二、線性規(guī)劃的根本定理二、線性規(guī)劃的根本定理 線性規(guī)劃問題可以有無數(shù)個可行解，最優(yōu)解只能夠在線性規(guī)劃問題可以有無數(shù)個可行解，最優(yōu)解只能夠在頂點(diǎn)上到達(dá)，而有限個頂點(diǎn)對應(yīng)的是基可行解，故只頂點(diǎn)上到達(dá)，而有限個頂點(diǎn)對應(yīng)的是基可行解，故只需在有限個基可行解中尋求最優(yōu)解即可。需在有限個基可行解中尋求最優(yōu)解即可。 從一個頂點(diǎn)出發(fā)找到一個可行基，得到一組基可行解，從一個頂點(diǎn)出發(fā)找到一個可行基，得到一組基可行解，拿目的函數(shù)做尺度衡量一下看能否最優(yōu)。拿目的函數(shù)做尺度衡量一下看能否最優(yōu)。 如假設(shè)不是，那么

22、向臨近的頂點(diǎn)轉(zhuǎn)移，換一個基再行如假設(shè)不是，那么向臨近的頂點(diǎn)轉(zhuǎn)移，換一個基再行求解、檢驗(yàn)，如此迭代循環(huán)目的值逐漸改善，直至求求解、檢驗(yàn)，如此迭代循環(huán)目的值逐漸改善，直至求得最優(yōu)解。得最優(yōu)解。 三、線性規(guī)劃的解題思緒三、線性規(guī)劃的解題思緒 例maxz=2x1+3x2St:X1+2x2+x3 =8 4x1 +x4 =16 4x2 +x5=12 Xi=0 1 2 1 0 0 A= 4 0 0 1 0 0 4 0 0 1令非基變量X4=X5=0，那么可解出X1=4, X2=3, X3=-2所以得出基解 X1=4，2，-2，0，0，但由于X30,所以X2是可行解，相應(yīng)的B2為可行基假設(shè)用以上方法可枚舉出此

23、線性規(guī)劃問題的基可行解分別為X3(4,0,4,0,12)， X4(0,3,2,16,0)，X52，3，0，8，0和X64，2，0，0，4，將這些解代入目的函數(shù)，可知X6可使得Z最大，所以X6為最優(yōu)解2 單純形法單純形法 單純形法的思緒：先找到一個初始可行基，求出這個基可行解，然后判別該基可行解能否為最優(yōu)解，假設(shè)是最優(yōu)解，那么求解終了，假設(shè)不是，那么進(jìn)展基變換，得到一個新的可行基，再進(jìn)展判別該基可行解能否為最優(yōu)解。每次基變換后的目的函數(shù)不斷增大，不斷到找到最優(yōu)解為止。單純形法根本思緒能否最優(yōu)解求最優(yōu)目的函數(shù)值是基變換,迭代否確定初始可行解2.1單純形法的原理例： maxz=2X1+3X2+0X3

24、+0X4+0X5 st X1+2X2+X3=8 4X1+X4=16 4X2+X5=12 Xj 0系數(shù)子矩陣 1 2 1 0 0A=P1 P2 P3 P4 P5= 4 0 01 0 0 4 0 0 1初始可行基 1 0 0 B1= 0 1 0 0 0 11所以：X3=8-X1-2X2 X4=16-4X1 X5=12-4X2將此代入目的函數(shù)將此代入目的函數(shù)Z=2X1+3X2，令非基變量等于，令非基變量等于0，那么得到一個基可行解那么得到一個基可行解X0=0 0 8 16 12，目的，目的函數(shù)值等于函數(shù)值等于0。但是從目的函數(shù)可知，因。但是從目的函數(shù)可知，因X1，X2的的價值系數(shù)均大于價值系數(shù)均大于

25、0，當(dāng)，當(dāng)X1或或X2由非基變量變成基變由非基變量變成基變量時，目的函數(shù)就會添加，所以此解并非最優(yōu)解。量時，目的函數(shù)就會添加，所以此解并非最優(yōu)解。將x2換入，x2換入后，需從X3,X4,X5中換出一個變量，并保證一切變量非負(fù)X3=8-2X2 X4=16X5=12-4X2當(dāng)X2增大時，要滿足X3，X4，X5 0，所以x2的最大只能取3，且此時x5為換出變量2基變換 新基變量為X3，X4，X2，得X3=2-X1+0.5X5X4=16-4X1X2=3-0.25X5代入目的函數(shù)得Z=9+2X1-0.75X5由于x1的系數(shù)為正，依然不是最優(yōu)解，換入x1，再經(jīng)過迭代最后的最優(yōu)解4 2 0 0 42.2單純

26、形法求解單純形法求解1初始基可行解確實(shí)定初始基可行解確實(shí)定a 直接察看法直接察看法b 構(gòu)造法構(gòu)造法方式，加松弛變量方式，加松弛變量方式方式,減松弛變量后加人工變量詳細(xì)求解要用大法或減松弛變量后加人工變量詳細(xì)求解要用大法或二階段法二階段法目的目的:使初始可行基為單位陣使初始可行基為單位陣,令非基變量等于零令非基變量等于零,由于由于b0,即可以得到初始基可行解即可以得到初始基可行解.2最優(yōu)性檢驗(yàn)與解的判最優(yōu)性檢驗(yàn)與解的判別別四種情況四種情況:獨(dú)一最優(yōu)解獨(dú)一最優(yōu)解無窮多最優(yōu)解無窮多最優(yōu)解無界解無界解無可行解無可行解 普通情況下普通情況下,經(jīng)過迭代后經(jīng)過迭代后jnmjmiijijimiijnmjiji

27、ixaccbczmixabx)(), 2 , 1(1111z0j 對于對于 a.最優(yōu)解的判別定理最優(yōu)解的判別定理:假設(shè)假設(shè) 為對應(yīng)于基為對應(yīng)于基B的一個基可行解的一個基可行解,且對于一切且對于一切j=m+1,n有有j0,那么那么 為最優(yōu)解為最優(yōu)解.稱稱j為檢為檢驗(yàn)數(shù)驗(yàn)數(shù).21)0()0 , 0 ,(mbbbX)0(Xnmjjjxzz10 證明證明:因?qū)σ磺蟹腔兞康慕窍聵?biāo)因?qū)σ磺蟹腔兞康慕窍聵?biāo)j，均有均有0，顯然，對于任一可行解，顯然，對于任一可行解均有均有zz0,但根本可行解但根本可行解 能使等能使等式成立，故為最優(yōu)解式成立，故為最優(yōu)解)0(X)0(Xjb.無窮多最優(yōu)解的判別定理無窮多最優(yōu)

28、解的判別定理:假設(shè)假設(shè) 為一個基可行解為一個基可行解,且對于一切且對于一切j=m+1,n有有j0,又存在某個非基變量的檢驗(yàn)數(shù)又存在某個非基變量的檢驗(yàn)數(shù)m+k=0,那么線性規(guī)劃問題有無窮多最優(yōu)解那么線性規(guī)劃問題有無窮多最優(yōu)解21)0()0 , 0 ,(mbbbXc.無界解無有限最優(yōu)解判別定理無界解無有限最優(yōu)解判別定理假設(shè)假設(shè)為一基可行解，有一個為一基可行解，有一個m+k，并且對，并且對i=1,2,m有有ai,m+k0,那么該線性規(guī)劃問題具有無界解無最那么該線性規(guī)劃問題具有無界解無最優(yōu)解優(yōu)解21)0()0 , 0 ,(mbbbXd.無可行解無可行解約束條件相互矛盾，可行域?yàn)榭占s束條件相互矛盾，可

29、行域?yàn)榭占罱K計(jì)算表中人工變量依然為基變量最終計(jì)算表中人工變量依然為基變量3基變換基變換當(dāng)初始基可行解不是最優(yōu)解及不能判別無界時當(dāng)初始基可行解不是最優(yōu)解及不能判別無界時,需求找需求找一個新的基可行解一個新的基可行解,詳細(xì)是從原可行解基中換一個列向詳細(xì)是從原可行解基中換一個列向量量,得到一個新的可行基得到一個新的可行基,稱為基變換稱為基變換.基變換的關(guān)鍵是如何選擇換入變量和換出變量這兩個問基變換的關(guān)鍵是如何選擇換入變量和換出變量這兩個問題題.(原那么和原那么和原那么原那么)a.換入變量：當(dāng)換入變量：當(dāng)j0時取時取j中最大的所對應(yīng)的非基變量中最大的所對應(yīng)的非基變量xk 。b.換出變量：換出變量：=

30、bi/aik(aik0)中最小的所對應(yīng)的中最小的所對應(yīng)的xl為換為換出變量。出變量。經(jīng)過基變換得到的解是基可行解經(jīng)過基變換得到的解是基可行解,目的函數(shù)值添加目的函數(shù)值添加4迭代運(yùn)算迭代運(yùn)算將將xk和和xl進(jìn)展對換，即把進(jìn)展對換，即把Pk變?yōu)閱挝涣邢蛄咳∽優(yōu)閱挝涣邢蛄咳〈鶳l,可經(jīng)過系數(shù)矩陣的增廣矩陣的初等變換可經(jīng)過系數(shù)矩陣的增廣矩陣的初等變換來實(shí)現(xiàn)來實(shí)現(xiàn)將增廣矩陣的第將增廣矩陣的第l行除以行除以alk將將k列除列除alk變換為變換為1以外，其他都變成以外，其他都變成0。alk稱之為主元素，稱之為主元素，k列成為主元列，列成為主元列，l行稱為主行稱為主遠(yuǎn)行。遠(yuǎn)行。2.3 單純形表 單純形表，是

31、對上節(jié)討論的方法步驟進(jìn)展詳細(xì)化、規(guī)范化、表格化的結(jié)果。 CjC1C2CjCn比值CBXBbx1x2xjxnCB1xB1b1a11a12a1ja1n1CB2xB2b2a21 a22a2ja2n2CBnxBnbmam1 am2amjamn m檢驗(yàn)數(shù)j-Z12jn將線性規(guī)劃問題化成規(guī)范型。找出或構(gòu)造一個m階單位矩陣作為初始可行基，建立初始單純形表。計(jì)算各非基變量xj的檢驗(yàn)數(shù)j=Cj-CBPj ，假設(shè)一切j0，那么問題已得到最優(yōu)解，停頓計(jì)算，否那么轉(zhuǎn)入下步。在大于0的檢驗(yàn)數(shù)中，假設(shè)某個k所對應(yīng)的系數(shù)列向量Pk0，那么此問題是無界解，停頓計(jì)算，否那么轉(zhuǎn)入下步。根據(jù)maxjj0=k原那么，確定xk為換入變

32、量(進(jìn)基變量)，再按規(guī)那么計(jì)算：=minbi/aik| aik0=bl/ aik 確定xBl為換出變量。建立新的單純形表，此時基變量中xk取代了xBl的位置。以aik為主元素進(jìn)展迭代，把xk所對應(yīng)的列向量變?yōu)閱挝涣邢蛄浚碼ik變?yōu)?，同列中其它元素為0，轉(zhuǎn)第 步。 單純形法的計(jì)算步驟單純形法的計(jì)算步驟 maxZ=3x1 +5 x2 +0 x3 +0 x4+0 x5 =0 x1 + x3 =8 2x2 + x4 =12 3x1 +4 x2 + x5=36 單純形法計(jì)算舉例單純形法計(jì)算舉例Cj比值CBXBb檢驗(yàn)數(shù)jx1x2x3x4x53500081010012020103634001x3x4x5

33、000035000-12/2=636/4=9miijBjjaCCi1檢驗(yàn)數(shù)j81010060101/2012300-21x3x2x5050-30300-5/208-4Cj比值CBXBb檢驗(yàn)數(shù)jx1x2x3x4x53500081010012020103634001x3x4x5000035000-12/2=636/4=9Cj比值CBXBb檢驗(yàn)數(shù)jx1x2x3x4x53500081010060101/2012300-21x3x2x5050-30300-5/208-4檢驗(yàn)數(shù)j40012/3-1/360101/204100-2/31/3x3x2x1053-42000-1/2-1最優(yōu)解最優(yōu)解 :X*=(4

34、,6,4,0,0)T，Z*=42 最優(yōu)基 Cj35000比值CBXBbx1x2x3x4x50 x340012/3-1/35x260101/203x14100-2/31/3檢驗(yàn)數(shù)j-42000-1/2-1340020101*Bx3 x2x1313200210313211*B 最優(yōu)基的逆最優(yōu)基的逆 最優(yōu)基和最優(yōu)基的逆最優(yōu)基和最優(yōu)基的逆又例又例Max z=2x1+3x2 x1+2x2+x3 =8 4x1 +x4 =16 4x2 +x5=12 x1, x2, x3 ,x4,x50 此問題的最優(yōu)解為此問題的最優(yōu)解為:x1*=4, x2*=2, x5*=4, x3*= x4*= x1*=0, z*=24+

35、32=14例Max z=2x1+3x2 x1+2x2 8 4x1 16 4x2 12 x1, x2 0 例如例如 maxZ= 3x1 +2 x2 -2x1 + x2 2 x1 -3 x2 3 x1 , x2 0S.t. 規(guī)范化規(guī)范化 maxZ= 3x1 +2 x2 -2x1 + x2 + x3 =2 x1 -3 x2 + x4 =3 x1 , x2 , x3, x4 0Cj比值CBXBb檢驗(yàn)數(shù)jx1x2x3x432002-211031-301x3x40003200-3檢驗(yàn)數(shù)j80-512x3x103-31-301-90110-3 此時，檢驗(yàn)數(shù)2=11 0，還沒有得到最優(yōu)解。 確定x2進(jìn)基，但x

36、2所在列的系數(shù)向量元素非正，無界 值不存在，有進(jìn)基變量但無離基變量。 用單純形法解題時，需求有一個單位矩陣作為初始基。 當(dāng)約束條件都是“時，參與松弛變量就構(gòu)成了初始基。 但實(shí)踐存在“或“型的約束，沒有現(xiàn)成的單位矩陣。 采用人造基的方法：人工構(gòu)造單位矩陣采用人造基的方法：人工構(gòu)造單位矩陣 在沒有單位列向量的等式約束中參與人工變量，構(gòu)成原線在沒有單位列向量的等式約束中參與人工變量，構(gòu)成原線性規(guī)劃問題的伴隨問題，從而得到一個初始基。性規(guī)劃問題的伴隨問題，從而得到一個初始基。 人工變量是在等式中人為加進(jìn)的，只需它等于人工變量是在等式中人為加進(jìn)的，只需它等于0時，約束條時，約束條件才是它本來的意義。件才

37、是它本來的意義。 處置方法有兩種：處置方法有兩種： 大大M 法法 兩階段法兩階段法3.單純形法的進(jìn)一步討論 沒有單位矩陣，不符合構(gòu)造初始基的條件，需參與人工變量 。 人工變量最終必需等于0才干堅(jiān)持原問題性質(zhì)不變。 為保證人工變量為0，在目的函數(shù)中令其系數(shù)為-M。 M為無限大的正數(shù)，這是一個懲罰項(xiàng)，倘假設(shè)人工變量不為零，那么目的函數(shù)就永遠(yuǎn)達(dá)不到最優(yōu)，所以必需將人工變量逐漸從基變量中交換出去。 如假設(shè)到最終表中人工變量仍沒有置換出去，那么這個問題就沒有可行解，當(dāng)然亦無最優(yōu)解。 大大M法法 例如例如 maxZ= 3x1 - x2 -2 x3 3x1 + 2 x2 -3 x3 =6 x1 - 2 x2

38、 + x3 =4 x1 , x2 , x3 0S.t. 按大按大M法構(gòu)造人造基，引入人工變量法構(gòu)造人造基，引入人工變量x4 , x5 的輔助問題如的輔助問題如下：下： maxZ= 3x1 - x2 -2 x3 -M x4 -M x5 3x1 + 2 x2 -3 x3 + x4 =6 x1 - 2 x2 + x3 + x5 =4 x1 , x2 , x3 , x4 , x5 0Cj比值CBXBb檢驗(yàn)數(shù)jx1x2x3x4x53-1-2-M-M632-31041-210100-2-2M-13+4M-10Mx4x5-M-M24miijBjjaCCi1Cj比值CBXBb檢驗(yàn)數(shù)jx1x2x3x4x53-1

39、-2-M-M632-31041-21013+4M-1-2-2M00 x4x5-M-M24檢驗(yàn)數(shù)j212/3-11/3020-8/32-1/310-1-4M/31+2M-3-8M/30 x1x53-M-1檢驗(yàn)數(shù)j31-2/301/61/210-4/31-1/61/20-5/30-M-5/6-M-1/2x1x33-2用計(jì)算機(jī)處置數(shù)據(jù)時，只能用很大的數(shù)替代用計(jì)算機(jī)處置數(shù)據(jù)時，只能用很大的數(shù)替代M,M,能夠呵能夠呵斥計(jì)算機(jī)上的錯誤，故多采用兩階段法。斥計(jì)算機(jī)上的錯誤，故多采用兩階段法。 第一階段：第一階段： 在原線性規(guī)劃問題中參與人工變量，構(gòu)造如下模型：在原線性規(guī)劃問題中參與人工變量，構(gòu)造如下模型：

40、0 00min11111111111mnmmnnmnmnnnnmnnxxbxxaxabxxaxaxxxxW兩階段法兩階段法 對上述模型求解單純形法，假設(shè)對上述模型求解單純形法，假設(shè)W=0,W=0,闡明問題存在根本可行解，可以進(jìn)展闡明問題存在根本可行解，可以進(jìn)展第二個階段；否那么，原問題無可行解，第二個階段；否那么，原問題無可行解，停頓運(yùn)算。停頓運(yùn)算。 第二階段：在第一階段的最終表中，第二階段：在第一階段的最終表中，去掉人工變量，將目的函數(shù)的系數(shù)換成原去掉人工變量，將目的函數(shù)的系數(shù)換成原問題的目的函數(shù)系數(shù)，作為第二階段計(jì)算問題的目的函數(shù)系數(shù)，作為第二階段計(jì)算的初始表用單純形法計(jì)算。的初始表用單純

41、形法計(jì)算。單純形法補(bǔ)遺 進(jìn)基變量相持： 單純形法運(yùn)算過程中，同時出現(xiàn)多個一樣的j最大。 在符合要求的j(目的為max：j0，min：j0)中，選取下標(biāo)最小的非基變量為換入變量； 離基變量相持： 單純形法運(yùn)算過程中，同時出現(xiàn)多個一樣的最小值。 繼續(xù)迭代，便有基變量為0，稱這種情況為退化解。 選取其中下標(biāo)最大的基變量做為換出變量。 多重最優(yōu)解： 最優(yōu)單純形表中，存在非基變量的檢驗(yàn)數(shù)j=0。 讓這個非基變量進(jìn)基，繼續(xù)迭代，得另一個最優(yōu)解。 無界解： 大于0的檢驗(yàn)數(shù)中，假設(shè)某個k所對應(yīng)的系數(shù)列向量Pk0，那么解無界。 無可行解： 最終表中存在人工變量是基變量。 4.線性規(guī)劃的運(yùn)用解解 先看有多少種裁料

42、方案，再進(jìn)展組合和選擇。方案：先看有多少種裁料方案，再進(jìn)展組合和選擇。方案：套裁下料套裁下料 現(xiàn)要做一百套鋼管現(xiàn)要做一百套鋼管, 每套要長為每套要長為2.9m、2.1m和和1.5m的鋼管各的鋼管各一根。知原料長一根。知原料長7.4m，問應(yīng)如何下料，運(yùn)用的原料最省。，問應(yīng)如何下料，運(yùn)用的原料最省。 設(shè)用方案設(shè)用方案, ,分分別裁原料鋼管別裁原料鋼管x1,x2,.x5根根, 那那么：么：Min z= 0 x1+0.1 x2+0.2 x3+0.3x4+ 0.8x5x1+ 2x2 + x4 =100 2x3+2x4+x5 =100 3x1+x2 +2x3 +x5 =100 x1, x2, x3, x4

43、, x5 0 例例 某工廠要用三種原資料某工廠要用三種原資料C,P,HC,P,H混合調(diào)配出三種不同規(guī)混合調(diào)配出三種不同規(guī)格的產(chǎn)品格的產(chǎn)品A,B,DA,B,D。知產(chǎn)品的規(guī)格要求、單價和原料的供。知產(chǎn)品的規(guī)格要求、單價和原料的供應(yīng)量、單價如下表。該廠應(yīng)如何安排消費(fèi)，能使利潤最應(yīng)量、單價如下表。該廠應(yīng)如何安排消費(fèi)，能使利潤最大？大？產(chǎn)產(chǎn)品品名名規(guī)規(guī)格格要要求求單單價價A原原料料 C 不不少少于于 50%原原料料 P 不不超超過過 25%50 元/KGB原原料料 C 不不少少于于 25%原原料料 P 不不超超過過 50%35 元/KGD不不限限25 元/KG配料問題配料問題根據(jù)產(chǎn)品要求有：根據(jù)產(chǎn)品要求

44、有： AC0.5A, AP0.25A BC0.25B, BP0.5B AC+AP+AH=A BC+BP+BH=B根據(jù)原料供應(yīng)量有：根據(jù)原料供應(yīng)量有： AC+BC+DC100 AP+BP+DP100 AH+BH+DH60設(shè)設(shè)AC,AP,DH分別為分別為x1,x2,x9，有有Max z=50(x1+x2+x3)+35(x4+x5+x6) +25(x7+x8+x9) - 65(x1+x4+x7) - 25(x2+x5+x8) - 35(x3 +x6 +x9) x10.5(x1+ x2+ x3) x2 0.25(x1+ x2+ x3) x4 0.25(x4+ x5+ x6) x5 0.5(x4+ x5

45、+ x6) x1+ x4+ x7100 x2+ x5+ x8100 x3+ x6+ x960 xj0, j=1,2,3,4,5,6,7,8,9解：記產(chǎn)品解：記產(chǎn)品A A、B B、D D中中C C、P P、H H的含量分別為：的含量分別為：ACAC、APAP、AHAH、BCBC、BPBP、BHBH、DCDC、DPDP、DHDH。 例例 某單位有資金某單位有資金10萬元，在今后萬元，在今后5年內(nèi)可思索以下投年內(nèi)可思索以下投資工程，知：資工程，知： 工程工程A：從第：從第1到第到第4年每年初可投資，并于次年末年每年初可投資，并于次年末回收本利回收本利115%； 工程工程B：第：第3年初需求投資，到第

46、年初需求投資，到第5年末回收本利年末回收本利125%，但最大投資額不超越，但最大投資額不超越4萬元；萬元； 工程工程C：第：第2年初需求投資，到第年初需求投資，到第5年末能回收本利年末能回收本利140%，但最大投資額不超越，但最大投資額不超越3萬元；萬元； 工程工程D：5年內(nèi)每年初可購買公債，當(dāng)年末回收本利年內(nèi)每年初可購買公債，當(dāng)年末回收本利106%。 問它應(yīng)該如何安排每年的投資，使到問它應(yīng)該如何安排每年的投資，使到5年末擁有的年末擁有的資金最多？資金最多？投資方案投資方案 x2A+x2C+x2D=1.06x1D解：每年的投資額應(yīng)不超越手中的資金。由于工程解：每年的投資額應(yīng)不超越手中的資金。由

47、于工程D每每年都可投資，且當(dāng)年末就可收回。所以該單位每年必年都可投資，且當(dāng)年末就可收回。所以該單位每年必然把資金全部投出去，即投資額等于手中的資金數(shù)。然把資金全部投出去，即投資額等于手中的資金數(shù)。設(shè)第設(shè)第i年投資各工程的資金為年投資各工程的資金為xiA、xib、xiC、xiD ，數(shù)學(xué)模型為：數(shù)學(xué)模型為：Max z=1.15x4A+1.4x2C+1.25x3B+1.06x5D x1A+x1D=10 x3A+x3B+x3D=1.15x1A+1.06x2Dx4A+x4D=1.15x2A+1.06x3D x5D=1.15x3A+1.06x4DxiA,xib,xiC,xiD0例某晝夜效力的公交線路每天各

48、時間段內(nèi)所需司機(jī)和乘務(wù)人員數(shù)如下： 設(shè)司機(jī)和乘務(wù)人員分別在各時間段一開場時上班，并延續(xù)任務(wù)八小時，問該公交線路怎樣安排司機(jī)和乘務(wù)人員，既能滿足任務(wù)需求，又配備最少司機(jī)和乘務(wù)人員?人力資源分配的問題人力資源分配的問題解：設(shè) xi 表示第i班次時開場上班的司機(jī)和乘務(wù)人員數(shù),這樣我們建立如下的數(shù)學(xué)模型。目的函數(shù)： Min x1 + x2 + x3 + x4 + x5 + x6 約束條件：s.t. x1 + x6 60 x1 + x2 70 x2 + x3 60 x3 + x4 50 x4 + x5 20 x5 + x6 30 x1,x2,x3,x4,x5,x6 0 例：明興公司消費(fèi)甲、乙、丙三種產(chǎn)品

49、，都需求經(jīng)過鑄造、例：明興公司消費(fèi)甲、乙、丙三種產(chǎn)品，都需求經(jīng)過鑄造、機(jī)加工和裝配三個車間。甲、乙兩種產(chǎn)品的鑄件可以外包協(xié)作，機(jī)加工和裝配三個車間。甲、乙兩種產(chǎn)品的鑄件可以外包協(xié)作，亦可以自行消費(fèi)，但產(chǎn)品丙必需本廠鑄造才干保證質(zhì)量。數(shù)據(jù)亦可以自行消費(fèi)，但產(chǎn)品丙必需本廠鑄造才干保證質(zhì)量。數(shù)據(jù)如下表。問：公司為了獲得最大利潤，甲、乙、丙三種產(chǎn)品各如下表。問：公司為了獲得最大利潤，甲、乙、丙三種產(chǎn)品各消費(fèi)多少件？甲、乙兩種產(chǎn)品的鑄造中，由本公司鑄造和由外消費(fèi)多少件？甲、乙兩種產(chǎn)品的鑄造中，由本公司鑄造和由外包協(xié)作各應(yīng)多少件？包協(xié)作各應(yīng)多少件？消費(fèi)方案消費(fèi)方案解：設(shè) x1,x2,x3 分別為三道工序都

50、由本公司加工的甲、乙、丙三種產(chǎn)品的件數(shù)， x4,x5 分別為由外協(xié)鑄造再由本公司機(jī)加工和裝配的甲、乙兩種產(chǎn)品的件數(shù)。 求 xi 的利潤：利潤 = 售價 - 各本錢之和可得到 xii=1,2,3,4,5的利潤分別為15、10、7、13、9元。這樣我們建立如下的數(shù)學(xué)模型。目的函數(shù)： Max 15x1 + 10 x2 + 7x3 + 13x4 + 9x5 約束條件： s.t. 5x1 + 10 x2 + 7x3 8000 6x1 + 4x2 + 8x3 + 6x4 + 4x5 12000 3x1 + 2x2 + 2x3 + 3x4 + 2x5 10000 x1,x2,x3,x4,x5 0練習(xí)：某廠消費(fèi)練習(xí)：某廠消費(fèi)、三種產(chǎn)品，均要經(jīng)過三種產(chǎn)品，均要經(jīng)過A A、B B 兩道工序兩道工序加工。假設(shè)有兩種規(guī)格的設(shè)備加工。假設(shè)有兩種規(guī)格的設(shè)備A1A1、A2A2能完成能完成 A A 工序；有三種工序；有三種規(guī)格的設(shè)備規(guī)格的設(shè)備B1B1、B2B2、B3B3能完成能完成 B B 工序。工序?？稍诳稍贏 A、B B的任何規(guī)的任何規(guī)格的設(shè)備上加工；格的設(shè)備上加工； 可在恣意規(guī)