線性規(guī)劃圖解法幾何意.ppt

1、1.3線性規(guī)劃問題的標(biāo)準(zhǔn)形式,(其中bi0(i=1,2,.,m),稱下列形式為線性規(guī)劃問題的標(biāo)準(zhǔn)形式:,目標(biāo)函數(shù)求極大,約束條件為等式,決策變量及右邊常數(shù)項(xiàng)為非負(fù),線性規(guī)劃問題的幾種表示形式,用向量表示為：,則標(biāo)準(zhǔn)形式的矩陣表示：,若令,A稱為系數(shù)矩陣,b稱為資源向量,C稱為價(jià)值向量,X稱為決策變量向量,用矩陣表示為：,非標(biāo)準(zhǔn)形式化為標(biāo)準(zhǔn)形式的方法,1.當(dāng)目標(biāo)函數(shù)為求極小值,即 min z=c1x1+c2x2+.+cnxn,因?yàn)榍髆in z 等價(jià)于max (-z),故可令,則目標(biāo)函數(shù)化為:,2.當(dāng)右端項(xiàng) bi0時(shí),只需將等式或不等式兩端同乘(-1),則右端項(xiàng)必大于0,3.當(dāng)約束條件為ai1x1

2、+ai2x2+.+ainxnbi,引入一個(gè)變量xn+i0,可使成為等式即 ai1x1+ai2x2+.+ainxnxn+ibi,變量xn+i稱為松弛變量,4. 當(dāng)約束條件為ai1x1+ai2x2+.+ainxnbi時(shí),則引入一個(gè)變量xn+i0,可使不等式成為等式,即 ai1x1+ai2x2+.+ainxnxn+ibi,變量xn+i稱為剩余變量,5.當(dāng)變量xi為無約束的變量時(shí),則我們引入兩個(gè)變量,令:,將其代入線性規(guī)劃模型中,6.當(dāng)變量xi0時(shí),則令,再代入線性規(guī)劃模型中,例3 將例1的數(shù)學(xué)模型化為標(biāo)準(zhǔn)形,該線性規(guī)劃問題加入三個(gè)松馳變量x3,x4,x50后：,例4 將下述線性規(guī)劃問題化為標(biāo)準(zhǔn)形,解

3、：分以下步驟進(jìn)行處理,(1)令z= -z，把求min z 改為求max z; (2) 在第一個(gè)約束不等式號(hào)的左端加入松弛變量x4； (3) 在第二個(gè)約束不等式號(hào)的左端減去剩余變量x5； (4)用x3-x”3替換x3，其中x3，x”30,即可得到該問題的標(biāo)準(zhǔn)形.,得原問題的標(biāo)準(zhǔn)形為：,1.4 線性規(guī)劃問題的解的概念,1.可行解 2.基 3.基可行解 4.可行基,一. 線性規(guī)劃問題解的概念,線性規(guī)劃問題,1.可行解:,滿足線性規(guī)劃問題的約束條件的解X=(x1，x2，.，xn ) T稱為線性規(guī)劃問題的可行解。,2.可行域:,全部可行解構(gòu)成的集合稱為可行域。,3.最優(yōu)解:,使目標(biāo)函數(shù)達(dá)到最優(yōu)的可行解稱

4、為最優(yōu)解。,4.基:,設(shè)系數(shù)矩陣Amn(nm)其秩為m,B是矩陣A中的一個(gè)mm階的滿秩子矩陣,稱B是線性規(guī)劃問題的一個(gè)基。,一. 線性規(guī)劃問題解的概念（2）,=(P1,P2,.,Pm),B中的每一列向量Pj(j=1,2,.m)稱為基向量,基向量：,與基向量Pj的對應(yīng)的變量xj 稱為基變量,基變量：,非基變量：,線性規(guī)劃中的其余變量稱為非基向量,5.基解,設(shè)X是（LP）的約束方程AX=b的一個(gè)解，B是一個(gè)基，若X中對應(yīng)基B的非基變量取值全為零，則稱X為(LP)關(guān)于基B的基解，記作X(B),不妨設(shè)基為,基解的個(gè)數(shù)不會(huì)超過 個(gè),一. 線性規(guī)劃問題解的概念（3）,可證明:一個(gè)基唯一地確定一個(gè)基解.,6

5、.基可行解：,若基解X(B)滿足非負(fù)條件X(B)0，則稱基解X(B)為基可行解,7.基最優(yōu)解：,若基可行解X(B)是(LP)的最優(yōu)解,則稱X(B)為(LP)的基最優(yōu)解.,最優(yōu)基：,基最優(yōu)解對應(yīng)的可行基B稱為最優(yōu)基.,可行基：,基可行解對應(yīng)的基B稱為可行基.,注:基解沒有X0的限制,故基解不一定是可行解.,X(B)=,一. 線性規(guī)劃問題解的概念（4）,8.退化解：,若基本可行解X的所有基變量的值均大于0，則稱X是非退化的，否則稱X為退化的。,若(LP)的所有基本可行解都是非退化的, 則稱線性規(guī)劃問題是非退化的.,二. 例題,考慮線性規(guī)劃問題：,約束方程的系數(shù)矩陣A,很顯然A中的后3列是線性無關(guān)的

6、，它們構(gòu)成一個(gè)基,基B1對應(yīng)的變量x3,x4,x5是基變量, x1,x2是非基變量,二. 例題（2）,若令：,得,該解是對應(yīng)B1的基解，它是基可行解，B1是可行基；,如取,是（LP）的一個(gè)基，,若令：,基B2對應(yīng)的變量x1,x2,x3是基變量， ,x4,x5是非基變量,得,該解是對應(yīng)B2的基解，它不是基可行解，B2不是可行基；,三. 線性規(guī)劃問題解的關(guān)系圖,AX=b的解,基解,若非基變量為0,基可行解,基最優(yōu)解,B是A的m階子矩陣,基B,若|B|0,可行基B,當(dāng)B-1b0,最優(yōu)基B,若基變量取非負(fù),若對應(yīng)目標(biāo)函數(shù) 值最優(yōu),非可行解,三. 線性規(guī)劃問題解的關(guān)系圖（2）,可行解,基可行解,基解,基

7、,可行基,最優(yōu)基,第2節(jié) 線性規(guī)劃問題的幾何意義,2.1 基本概念 2.2 幾個(gè)定理,一.凸集與頂點(diǎn),凸集:,如果集合K中任意兩個(gè)點(diǎn)X(1),X(2),其連線上的所有點(diǎn)也都是集合K中的點(diǎn),則稱集合K為凸集.,或K=X|X=X(1)+(1-)X(2), X(1)K,X(2)K,01,定理: D xRn| Ax=b,x0是凸集,頂點(diǎn):凸集K中滿足下列條件的點(diǎn)X稱為頂點(diǎn):如 果K中不存在任何兩個(gè)不同的點(diǎn)X1,X2,使X 成為這兩個(gè)點(diǎn)連線上的一個(gè)點(diǎn).,定理: 有限個(gè)凸集的交集還是凸集,凸組合:設(shè),是n維歐氏空間中的k個(gè)點(diǎn),則稱X是的凸組合,凸集的概念：,凸集,凸集,不是凸集,頂點(diǎn),不是凸集,二.幾個(gè)基

8、本定理,定理1,若線性規(guī)劃問題存在可行解,則問題的可行域是凸集.,定理2,若線性規(guī)劃問題有非零可行解，則其必有基可行解。,定理4,若線性規(guī)劃問題有最優(yōu)解，一定存在一個(gè)基可行解是最優(yōu)解。,定理3,線性規(guī)劃問題的基可行解X對應(yīng)線性規(guī)劃問題可行域(凸集)的頂點(diǎn).,引理1,線性規(guī)劃的可行解X(x1,x2,xn)T為基可行解的充要條件是X的正分量所對應(yīng)的系數(shù)列向量是線性無關(guān)的。,第3節(jié) 單 純 形 法,一. 單純形法迭代的基本思想,開始于某一個(gè)可行基及其對應(yīng)的基可行解，從一個(gè)基可行解迭代到另一個(gè)基可行解，并且使目標(biāo)函數(shù)值不斷增大，經(jīng)過有限步必能求得線性規(guī)劃問題的最優(yōu)解或者判定線性規(guī)劃問題無有界的最優(yōu)解（

9、無界解）。,二. 單純形法引例,考慮線性規(guī)劃問題：,約束方程的系數(shù)矩陣A,很顯然A中的后3列是線性無關(guān)的，它們構(gòu)成一個(gè)基,基B對應(yīng)的變量x3,x4,x5是基變量，則,二. 單純形法引例（2）,即：,將它們代入目標(biāo)函數(shù)中得,令非基變量x1=x2=0,得目標(biāo)值z0 一個(gè)基可行解X(0)(0,0,8,16,12),為了使目標(biāo)函數(shù)能更大，讓x2變成基變量，原基變量 的x3，x4，x5要有一個(gè)變?yōu)榉腔兞?當(dāng)x1=0,由最上式得,從上式可看出，當(dāng)x2=3仍可保證所有變量非負(fù)， 并使目標(biāo)函數(shù)增大,二. 單純形法引例（3）,為了得到以x3,x4,x2為基變量的一個(gè)基可行解，則對左邊方程中的x2與x5互換,得

10、,再令非基變量x1=x5=0,得目標(biāo)值z9 一個(gè)基可行解X(0)(0,3,2,16,0),為了使目標(biāo)函數(shù)能更大，讓x1變成基變量，原基變量 的x3，x4，x2要有一個(gè)變?yōu)榉腔兞?目標(biāo)函數(shù)變?yōu)?二. 單純形法引例（4）,這樣如此下去，可得,X(2)(2,3,0,8,0),為了使目標(biāo)函數(shù)能更大，讓x1變成基變量，原基變量 的x3，x4，x2要有一個(gè)變?yōu)榉腔兞?此時(shí)目標(biāo)函數(shù)變?yōu)?X(3)(4,2,0,0,4),由于目標(biāo)函數(shù)中的變量系數(shù)都小于等于0， 所以X(3)（4,2,0,0,4)為最優(yōu)解， 最優(yōu)值z14,下面從幾何角度分析一下最優(yōu)解的尋求過程：,幾何意義：頂點(diǎn)轉(zhuǎn)移，目標(biāo)增大,三. 單純形法原

11、理,1.確定初始基可行解：,對標(biāo)準(zhǔn)型的LP問題,在約束條件(1.1)的變量的系數(shù)矩陣中總會(huì)存在一個(gè)單位矩陣。,(2)當(dāng)線性規(guī)劃的約束條件都為號(hào)時(shí)，其松弛變量對應(yīng)的系數(shù)列向量構(gòu)成的矩陣即為單位陣；,(3)當(dāng)線性規(guī)劃的約束條件為或的情況，引入人工變量后也可實(shí)現(xiàn)。,(1)系數(shù)矩陣中可以直接觀察得到一個(gè)單位子矩陣；,三. 單純形法原理（2）,2. 從一個(gè)基可行解轉(zhuǎn)換為相鄰的基可行解：,定義：兩個(gè)基可行解稱為相鄰的，如果他們之間變換且僅變換一個(gè)基變量。,設(shè)初始基可行解為：,可知：,其對應(yīng)的系數(shù)矩陣的增廣矩陣為：,三. 單純形法原理（3）,易得：,(1.3)+(1.4) (0), 得,令：,顯然：,為使X

12、(1)成為可行解，令：,可證明:將(1.6)式代回到X(1)中,X(1) 為基可行解，此時(shí)完成了從一個(gè)基可行解到另一個(gè)與其相鄰的基可行解的轉(zhuǎn)換。,三. 單純形法原理（4）,證明：將與變量 x1,xl-1,xl+1,xm,xj對應(yīng)的列向量，經(jīng)重新排列后加上b列有如下形式：,因?yàn)?P1,P2, ,Pl-1， Pj,Pl+1,Pm 線性無關(guān)，故X(1)為基可行解。,三. 單純形法原理（5）,3.最優(yōu)性檢驗(yàn)與解的判別：,將2中的基可行解X(0)與X(1)分別代入目標(biāo)函數(shù)，得,稱為檢驗(yàn)數(shù),三. 單純形法原理（6）,(1)當(dāng)所有的j0時(shí) ，現(xiàn)行基可行解為最優(yōu)解； 當(dāng)所有的j0時(shí) ，該線性規(guī)劃問題有唯一最優(yōu)

13、解； 當(dāng)所有的j0，且對某個(gè)非基變量xk，有k=0,該線性規(guī)劃問題有無窮多最優(yōu)解。,(2)當(dāng)存在某個(gè)j0且對應(yīng)的列向量Pj 0時(shí)，該線性規(guī)劃問題有無界解；,(4)對線性規(guī)劃問題無可行解的判別將在后面討論。,(2)當(dāng)存在某個(gè)j0且對應(yīng)的列向量Pj 中有正分量時(shí)，說明目標(biāo)函數(shù)值還可以增大，需要進(jìn)行基變換；,第 4 節(jié) 單 純 形 法的計(jì)算步驟,一. 單純形法的計(jì)算步驟,第一步：求初始基可行解，列出初始單純形表,首先寫出關(guān)于價(jià)值系數(shù)的表：（非單純形表）,一. 單純形法的計(jì)算步驟（2）,將基變量下方的價(jià)值系數(shù)通過變換化為零，得初始單純形表,一. 單純形法的計(jì)算步驟（3）,第二步：最優(yōu)性檢驗(yàn),(1)當(dāng)所

14、有的j0時(shí) ，現(xiàn)行基可行解為最優(yōu)解； 當(dāng)所有的j0時(shí) ，該線性規(guī)劃問題有唯一最優(yōu)解； 當(dāng)所有的j0，且對某個(gè)非基變量xk，有k=0,該線性規(guī)劃問題有無窮多最優(yōu)解。,(2)當(dāng)存在某個(gè)j0且對應(yīng)的列向量Pj 0時(shí)，該線性規(guī)劃問題有無界解；,(3)當(dāng)存在某個(gè)j0且對應(yīng)的列向量Pj 中有正分量時(shí)，說明目標(biāo)函數(shù)值還可以增大，需要進(jìn)行基變換。,一. 單純形法的計(jì)算步驟(4),第三步：換基迭代,(1)確定進(jìn)基變量,選擇檢驗(yàn)數(shù)最大的非基變量為進(jìn)基變量,k=max j| j0,j=1,2,.,n,則xk為進(jìn)基變量,(2)確定出基變量,根據(jù)下列原則確定出基變量,則l所對應(yīng)的基變量xl為出基變量,元素alk為軸心項(xiàng)

15、(或稱為主元素),(3)以alk為軸心項(xiàng)進(jìn)行換基迭代,即利用矩陣的初等行變換,把元素alk所在的列化為單位向量.得到新的單純形表,一. 單純形法的計(jì)算步驟（5）,第四步：重復(fù)第二、三步，一直到計(jì)算結(jié)束為止。,二單純形法 例1(1),例 用單純形法解下列線性規(guī)劃,解:,將原問題化為標(biāo)準(zhǔn)形為：,得單純形初表為:,二單純形法 例1(2),T(B1),x3,x4,x2,-z,2,1 0 1 0 -1/2,16,4 0 0 1 0,3,0,1,0,0,1/4,-9,2,0,0,0,-3/4,T(B2),T(B2),x1,x4,x2,-z,2,1 0 1 0 -1/2,8,0 0 -4 1 2,3,0,1

16、,0,0,1/4,-13,0,0,-2,0,1/4,T(B3),二單純形法 例1(3),T(B3),x1,x5,x2,-z,4,1 0 0 1/4 0,4,0 0 -2 1/2 1,2,0,1,1/2,-1/8,0,-14,0,0,-3/2,-1/8,0,T(B4),二單純形法 例1(4),二單純形法 例1(4),在單純形終表中，x3,x4為非基變量，所有非基變量檢驗(yàn)數(shù)均小于零，故該線性規(guī)劃問題有唯一最優(yōu)解X*=(4,2,0,0,4)T ，最優(yōu)值為 Z*=14。,二單純形法 例2(1),例2: 用單純形法解下列線性規(guī)劃,解:,將原問題化為標(biāo)準(zhǔn)形為：,得單純形初表為:,T(B1),x3,x2,x

17、5,-z,4,1 0 1 0 0,3,0 1 0 1 0,2,1,0,0,-2,1,-6,1,0,0,-2,0,T(B2),二單純形法 例2(2),T(B2),x3,x2,x1,-z,2,0 0 1 2 -1,3,0 1 0 1 0,2,1,0,0,-2,1,-8,0,0,0,0,-1,T(B3),二單純形法 例2(3),二單純形法 例2(4),在單純形終表中，x4,x5為非基變量，非基變量檢驗(yàn)數(shù)均小于等于零，且4=0,5=-10;故該線性規(guī)劃問題有無窮多最優(yōu)解。,注：在上述單純形終表中，以x4為進(jìn)基變量，按照極小化原則確定出基變量x3，進(jìn)行基變換，可得該線性規(guī)劃問題的另一個(gè)最優(yōu)解。,T(B3

18、),x4,x2,x1,-z,1,0 0 1/2 1 -1/2,2,0 1 -1/2 0 1/2,4,1,0,1,0,0,-8,0,0,0,0,-1,T(B4),最優(yōu)解X* =(2,3,2,0,0)T,最優(yōu)值 Z*=8,六單純形法舉例2(5),最優(yōu)值 Z*=8,最優(yōu)解X*= (4,2,0,1,0)T,開始,判斷所有檢驗(yàn)數(shù)是否小于等于0,得到最優(yōu)解,構(gòu)造單純形表,NO,輸入,結(jié)束,Yes,是否存在某個(gè)大于0的檢驗(yàn)數(shù)所對應(yīng)的列的元素全小于等于0？,原問題為無界解,換基迭代,選擇出基變量,Yes,選擇進(jìn)基變量,NO,單純形法的框圖表示為如下:,注：退化情形的處理,為避免出現(xiàn)計(jì)算的循環(huán)，1947年勃蘭特（Bland）提出了一個(gè)簡單有效的規(guī)則：,(1)當(dāng)存在多個(gè)j0時(shí)，始終選取下標(biāo)值為最小的變量為進(jìn)基變量；,(2)當(dāng)計(jì)算值出現(xiàn)兩個(gè)以上相同的最小比值時(shí)，始終選取下標(biāo)值為最小的變量為出基變量。,按最小比值來確定出基變量時(shí)，有時(shí)會(huì)出現(xiàn)兩個(gè)以上相同的最小比值，從而使下一個(gè)單純形表中出現(xiàn)一個(gè)或多個(gè)基變量等于零的退化解。將使得多個(gè)基可行解對應(yīng)同一頂點(diǎn)，可能出現(xiàn)迭代計(jì)算的循環(huán)。,注：目標(biāo)函數(shù)求最小的情況,(1) 化成標(biāo)準(zhǔn)型，目標(biāo)函數(shù)求極大；,(2)有些書中規(guī)定目標(biāo)函數(shù)的極小化作為線性規(guī)劃的標(biāo)準(zhǔn)形式，這時(shí)只需以所有檢驗(yàn)數(shù)j0作為判別表中解是否是最優(yōu)的標(biāo)志。,(1)