《管理學運籌學》PPT課件.ppt

1、第一章 線性規(guī)劃 linear Programming,第一節(jié) 線性規(guī)劃問題及其數學模型 第二節(jié) 可行區(qū)域與基本可行解 第三節(jié) 單純形方法,第一節(jié) 線性規(guī)劃問題及其數學模型,線性規(guī)劃是運籌學中研究較早、發(fā)展較快、應用較廣、比較成熟的一個分支，它是一種合理利用和調配有限資源的數學方法。,線性規(guī)劃研究的問題：,極大化問題：面對一定的資源，要求充分利用，以獲得最大的經濟效益。,極小化問題：給定一項任務，要求統(tǒng)籌安排，盡量做到用最少的人力、物力資源去完成這一任務。,一、實例： 生產安排問題 運輸問題 二、線性規(guī)劃問題的結構特征 線性規(guī)劃問題的特征 線性規(guī)劃問題的一般形式 線性規(guī)劃問題的標準形式 一般形

2、式向標準形式的轉化,本節(jié)內容安排,一、實例,例1 生產安排問題,某工廠擁有A、B、C三種類型的設備，生產甲、乙兩種產品。每件產品在生產中需要占用的設備機時數，每件產品可以獲得的利潤以及三種設備可利用的時數如下表所示：,問題：工廠應如何安排生產可獲得最大的總利潤？,可控因素：生產兩種產品的數量，設分別為x1 , x2，目標是生產利潤最大，設生產利潤為z.,利潤函數為：,限制條件：三臺設備的使用時間不超過設備能力的限制 設備A: 3x1+2x265 設備B: 2x1+ x2 40 設備C: 3x2 75,蘊涵約束：產量為非負 x10, x2 0,目標函數 約束條件,生產兩種產品的數量，設分別為為x

3、1,x2，總利潤為z.,在處理產、供、銷的經濟活動中，會經常遇到物資調撥的運輸問題。如糧棉油、煤炭、鋼鐵、水泥、化肥、木材等物資要由若干個產地調運到若干個銷售地。問題是，怎樣制定合理的調運方案才能使總運輸費用最少？這類問題稱為運輸問題,例2 運輸問題,設要從甲地調出物資2000噸，從乙地調出物資600噸，從丙地調出物資500噸，分別供應給A地1700噸、B地1100噸、C地200噸、D地100噸。已知每噸運費如下表所示。,假定運費與運量成正比例，問怎樣才能找到一個總運費最省的調撥計劃？,丙,問題分析： 可控因素：從三個產地到四個銷地的運輸量； 目標： 總運費最??； 限制條件：各個產地的產量和銷

4、地的需求量的限制 。,用 （i=1,2,3; j=1,2,3,4）分別表示從甲乙丙三個產地運往A,B,C,D四個銷地的物資數量。,則問題歸結為尋求一組xij的值，使函數,達到最小。并且下面的每一個約束條件都被滿足,簡化表達式,例 某工廠制造A,B兩種產品，它們的原材料單位消耗，單位利潤以及資源現有量如下表,問如何組織生產可使工廠獲得最大利潤？,如何建立數學模型？,1.選擇決策變量：設A，B兩種產品各生產 個單位；,2.建立目標函數：利潤函數是 求它的最大值，即,3.生產的產量受到限制：,4.決策變量必須有非負限制：,綜合上述各點，該問題的數學模型如下,目標函數,約束條件,非負限制,注意：目標函

5、數和約束條件中變量的次數都是一次的，這樣的模型稱為線性規(guī)劃數學模型。,二、線性規(guī)劃問題的結構特征：,1. 線性規(guī)劃問題的特征； （1）都有一組決策變量。 （2）都有一組線性的約束條件，它們是線性等式或不等式。 （3）都有一個確定的目標，這個目標可以表示成決策變量的線性函數，根據問題不同，有的要求實現極大化，有的要求實現極小化。,線性規(guī)劃問題的本質：研究在一組線性約束下，一個線性函數的極值問題。,2. 線性規(guī)劃問題的一般形式,一般形式的簡化表達,規(guī)范形式,極小化問題,極大化問題,3. 線性規(guī)劃的標準形式,標準形式的矩陣表達,標準形式的特點：,(1).目標函數極大化,(2).約束條件全部是等式,(

6、3).所有的變量都是非負的,(4).約束條件右端常數為非負的,4. 一般形式向標準形式的轉化：,(1) 目標函數極大化,(2) 不等式約束化等式約束,對于 形的不等式，可以在不等式的左邊加上（減去）一個非負的變量使不等式化成等式。這樣的變量稱為松弛（剩余）變量。,例如：,(3) 自由變量化非負變量的差,自由變量可以用兩個非負變量的差代替，例如對于一個符號無限制的變量 ，可以引進兩個非負變量 并設,(4) 約束條件右端的負常數化為非負常數,對于右端常數為負數的約束，可以兩端同時乘以-1。,例 將下列LP問題化成標準形式,s.t.,s.t.,1、先化變量和目標函數 2、調整約束條件 3、調整目標函

7、數,作業(yè)：,1.某車間生產甲、乙兩種產品，每件甲產品的利潤是2元，乙產品的利潤是4元。制造每件甲產品需要勞動力3個，而制造每件乙產品需要勞動力8個。車間現有勞動力總數是32個。制造每件甲產品需要原材料1000克，而乙產品需要原材料600克，車間共有原材料5500克可供利用。問應該安排甲、乙兩種產品各生產多少件才能獲得最大總利潤？（列出數學模型并化成標準形式）,第二節(jié) 單純形法原理,一、幾個概念 二、兩變量LP問題的圖解法 三、可行區(qū)域的幾何結構 四、基可行解及線性規(guī)劃的基本定理,可行解：任何一組滿足所有約束條件的決策變量值 稱為LP問題的一個可行解。,最優(yōu)解：使目標函數達到最大（?。┲档目尚薪?/p>

8、。 最優(yōu)值：最優(yōu)解對應的目標函數值。,可行域：所有可行解的集合稱為可行域。,一、幾個概念：,二、兩變量LP問題的圖解法,圖解法是根據平面直角坐標系和二元一次方程（不等式）的特點設計的。,1. 圖解法的一般步驟：,（1） 建立直角坐標系，以 為橫軸， 為縱軸。,（2） 將約束條件在直角坐標系中表示，并找出可行域。,（3）作出目標函數的等值線簇，找出目標函數值的增加（或減?。┓较?，用箭頭表示。,（4）確定出問題的最優(yōu)解。若為極大（小）化問題，目標函數沿增加（減?。┓较蚱揭疲c可行域的最后一個交點即為最優(yōu)解。,例1 用圖解法解下列線性規(guī)劃問題,最優(yōu)解 x*=(10,15)T, 最優(yōu)值 z*=6010

9、+5015=1350.,例2 用圖解法解線性規(guī)劃問題,最優(yōu)解 x*=(1,4)T, 最優(yōu)值 z*=-1+4=3.,例3 用圖解法求解線性規(guī)劃問題,最優(yōu)解不唯一（A1A2連線上的所有點都是最優(yōu)解），最優(yōu)值 z*=-4.,例4 用圖解法解線性規(guī)劃問題,可行域無界， 原問題最優(yōu)解無界。,例5 用圖解法解線性規(guī)劃問題,無解，或無可行解,用圖解法求解下面的LP問題,目標函數等值線,此點為LP的最優(yōu)解,目標函數等值線,可行解集,計算出這個最優(yōu)解:,上述作法稱為LP的圖解法.,本問題有唯一最優(yōu)解.,例2 用圖解法解下面的線性規(guī)劃,目標函數等值線,目標函數等值線,計算出LP的最優(yōu)解及目標函數最優(yōu)值:,除A,B

10、兩個最優(yōu)解外,AB線段上的所有點都是LP的最優(yōu)解.本問題有無窮多最優(yōu)解.,用圖解法解下面的線性規(guī)劃,無可行解,本題無可行解,更無最優(yōu)解,可行域是空集。 可行域存在，則一定是一個凸多邊形。,無界解（可行域一定無界）。 最優(yōu)解存在且唯一，則一定在頂點上達到。 最優(yōu)解存在且不唯一，一定存在一個頂點是最優(yōu)解 無解,2. 圖解法求解兩變量LP問題時可能出現的情況：,三、可行區(qū)域的幾何結構,1. 凸集及其性質 2. 可行域的凸性,凸集：若集合S中任意兩點X(1)S, X(2)S的連線上的所有點也都是集合S中的點，則稱S為一個凸集。 X(1)S, X(2)S的連線可表示為： X(1)+ (1- )X(2)S

11、, (0 1);,性質：任意多個凸集的交集仍然是凸集。,1. 凸集及性質,頂點：設S是凸集，XS；若對任何X(1)S和 X(2)S， X(1) X(2)，以及任何0 1，都有 X X(1)+ (1- )X(2) 則稱X為凸集S的一個頂點（或極點）。,凸集,凸集,不是凸集,極點,根據頂點的定義，長方形的四個角點就是長方形區(qū)域的全部頂點，而圓周上的點則是圓形區(qū)域的全部頂點。,2. 可行域的凸性,定理1：若線性規(guī)劃問題的可行域 D=x Rn|AX=b,X0非空，則必為凸集。,可行域凸性的證明思路,設X1,X2為可行域R內任意兩點，則X1 R,X2 R,將X1， X2帶入約束條件有AX1=b,AX2=

12、b,X1和X2連線上的任意一點可表示為： X=aX1+(1-a)X2, (0a1) 則AX= AaX1+(1-a)X2=aAX1+AX2-aAX2=ab+b-ab=b, 所以XR.由于集合中任意兩點連線上的點均在集合內，所以R為凸集,四、基可行解及線性規(guī)劃的基本定理,基可行解的定義 線性規(guī)劃的基本定理 問題,1. 基可行解的定義,考慮標準形式的線性規(guī)劃問題,基：A是約束方程組的系數矩陣(設nm)，其秩為m，B是A中的一個m階滿秩子方陣，稱B是線性規(guī)劃問題的一個基。 B中每一個列向量稱為一個基向量，與基向量對應的變量稱為基變量。其余變量稱為非基變量。,不失一般性，設,則Pj（j=1，2m）是基向

13、量，xj（ j=1，2m ）是基變量。 xj（ j=m+1，n ）是非基變量。,基解：在約束方程組x中令所有的非基變量m+1=x m+2=x n=0，得,此方程組有唯一解XB=(x1，x2，xm)T，將這個解加上非基變量取0的值有X=(x1，x2，xm,0,0)T,稱X為線性規(guī)劃問題的基解。,顯然，基解中取非零值的變量個數不超過m，基解的總數不超過Cnm個。,基可行解：滿足非負約束的基解稱為基可行解。 可行基：對應于基可行解的基。,基可行解,用矩陣形式表示的基解,考慮標準形式的線性規(guī)劃問題：,是它的兩個基，對應的基解分別為,可見X1是基可行解，B1是可行基。而X2不是基可行解。,根據以上定義,

14、可行解集,基礎可行解,最優(yōu)解,基礎最優(yōu)解,2. 線性規(guī)劃的基本定理,定理2：LP問題的可行解X是基可行解的充要條件是它的正分量所對應的A中的列向量線性無關。,定理3：線性規(guī)劃問題的基可行解對應可行域的頂點。（X是基可行解X是可行域的頂點）（基可行解個數有限）,定理4：一個LP問題，若有最優(yōu)解，則一定存在一個基可行解是最優(yōu)解。,例 設線性規(guī)劃為,則下述解中為基可行解的是 A.(2,0,4,0);B.(6,0,3,3);C.(3,2,3,2);D.(0,6,0,0),3. 問題,如何得到第一個基可行解？ 如何判別一個基可行解是否最優(yōu)？ 如果當前的基可行解不是最優(yōu)，如何從一個基可行解轉化到另一個基可

15、行解？,第三節(jié) 單純形方法,單純形方法（Simplex Method）是G.B.Dantzing 在1947年提出的。,一、 單純形方法 二、 第一個基可行解的求法,一、單純形方法,典式 最優(yōu)性檢驗和解的判別 基可行解的改進 單純形方法的基本步驟 單純形表,考慮標準形式的LP問題,假設可行域非空， A為一mn實矩陣，r(A)=mn 。,1. 典式,假設B是一個可行基，不妨設B是由A的前m個列向量組成的，即A=(B,N)，則線性規(guī)劃問題的等式約束AX=b 可以化成：,目標函數 Z=CX 可以化成,線性規(guī)劃問題的典式（典則形式）,典式的特點：（1）約束條件中含有一個單位矩陣，（2）目標函數中不含基

16、變量。,有了典式，就很容易寫出線性規(guī)劃問題的基解,其中,如果基B是可行基，則 即X0是基可行解，對應的目標函數值為z0 。,問題：如何判斷一個基可行解是否為最優(yōu)解呢？,在典式中，目標函數中非基變量的系數稱為檢驗數，檢驗數是用來判斷相應基可行解是否最優(yōu)的標志。,3. 基可行解的改進,1) 基的修改：進基變量、出基變量的選取準則。 2) 迭代：得到新基對應的典式。,基的修改準則：新基與原有基有m-1 個相同的基變量，只有一個基變量不同。,進基變量：從非基變量變?yōu)榛兞康淖兞俊?出基變量：由基變量變?yōu)榉腔兞康淖兞俊?1) 進基變量的選取原則：,最優(yōu)性原則：若K0,則與K相對應的變量xk是非基變量，

17、當xk變?yōu)榛兞繒r，它的值由0變?yōu)檎龜担热缯fxk=0，其余的非基變量仍取值為零。由(3.4)式知，對應新解的目標函數值為z=z0+ Kz0，顯然越大目標函數值越大。,可行性原則（最小比值原則）： 的取值應保證新解仍然是基可行解。,2) 出基變量的選取原則,進基變量和出基變量的選取準則,Max z=z0+ m+1xm+1+ kxk+ nxn s.t. x1 +a1m+1xm+1+ a1kxk + a1nxn= 1 x2 +a2m+1xm+1+ a2kxk +a2nxn= 2 . xm +amm+1xm+1+ +amkxk + amnxn= m xj0 j=1,2,n,當xk=0成為基變量以后，

18、其余非基變量仍然取值為0。設新基對應的基可行解為X1=(x11, xn1)T,則X1應滿足約束條件，即,x11 + a1k = 1 x21 + a2k = 2 . xm1 +amk = m xj10 j=1,2,n,由于xi1必須是非負的，即,如果aik0，顯然只要0，就有xi1 = i- aik 0 ，對于aik0，就要求,所以應滿足,2. 最優(yōu)性檢驗和解的判別,對于j 0,而aij0,則可以無限大使得目標函數值的增量（ j ）無限大,注意：,1.在選取進基變量時，若有幾個非基變量的檢驗數都是正數，則可以任意選取一個正檢驗數對應的非基變量作為進基變量，一般選取最大正檢驗數對應的非基變量。但實

19、際情況表明這種策略不一定最好。(當 j最大時對應的xj 不一定最大，我們要求的是 j 0最大),2.在選取出基變量時，若有幾個比值同時達到最小，可以任意選擇一個，但在新的基本可行解中這些對應分量均為零。從而新的基本可行解是一個退化的基本可行解。假若問題是非退化的，則不會出現這種情況。,迭代（新的基可行解對應的典式的確定）,利用線性方程組的等價變換將約束條件和目標函數化成新基對應的典式，從而求出新的基可行解及相應的檢驗數,4. 單純形方法的基本步驟,Step 1 將線性規(guī)劃問題化成典式,求出各個非基變量的檢驗數. Step 2 判斷所有非基變量的檢驗數是否非正,若是,則結束;否則轉step 3.

20、 Step 3 選取一個檢驗數大于零的非基變量為進基變量; Step 4 若進基變量所對應的約束條件系數全為非正數,則原問題無界,結束;否則,按最小比值原則確定出基變量; Step 5 進行迭代(用方程組的初等變換法確定新的基對應的典式)及檢驗數),轉step 2.,例1：利用單純形法求下列線性規(guī)劃問題,將該問題化成標準形式（也是典式）,基變量是：x3 ，x4 ，x5 ，非基變量是x1 x2,求出第一個基可行解X0=(0,0,65,40,75)T，非基變量的檢驗數均為正數，所以X0不是最優(yōu)解。,確定進基變量 x2，按照最小比值原則確定出基變量x5，最小比值是0=25. 求出新基對應的典式,X1

21、=(0,25,15,15,0)T,目標函數值為62500。,確定進基變量 x1，按照最小比值原則確定出基變量x3，最小比值是0=5. 求出新基對應的典式,X2=(5,25,0, 5,0)T,目標函數值為70000。,當前的解是最優(yōu)解,5. 單純形表,= - cn+i bi j = cj - cn+i,用單純形表求解例1,例2：利用單純形法求下列線性規(guī)劃問題,將該問題化成標準形式（也是典式）,基變量是：x3 ，x4 ，x5 ，非基變量是x1 x2,填入單純形表求解,最優(yōu)解X*=(2,3,2,0,0)T，最優(yōu)值19。,例3：用單純形法求解線性規(guī)劃問題（多解問題）,Max z = x1 + x2 s

22、.t. -x1 + x2 4 x1 - x2 4 x1+ x2 6 x1 , x2 0,Max z = x1 + x2 s.t. -x1 + x2 + x3 = 4 x1 - x2 + x4 = 4 x1+ x2 + x5 = 6 x1 , x2 , x3 , x4 , x5 0,解: 化成標準形式,填入單純形表求解,最優(yōu)解X1=(1,5,0,8,0)T，最優(yōu)值6。,最優(yōu)解X2=(5,1,8,0,0)T，最優(yōu)值6。,實際上X1與X2的連線上的任意點都是最優(yōu)解.,例4：用單純形法求解線性規(guī)劃問題（無有限最優(yōu)解的情況）,Max z = 2 x1 + x2 s.t. - x1 + x2 + x3 =

23、 5 2 x1-5 x2 + x4 = 10 x1 , x2 , x3 , x4 0,X2的檢驗數為正，但約束條件中x2的系數全為負，因此該問題無有限最優(yōu)解。,二、 第一個基可行解的求法,在給定的LP問題的標準形式中，如果約束條件系數矩陣A中含有一個m階單位矩陣，并且b0，則我們已經找到了一個明顯的基可行解，并且約束方程組已經是典式，這時可以直接填入單純形表中進行迭代。但是實際問題往往并非如此，因此我們需要尋找第一個基可行解，通常使用兩種常用的方法求解第一個基可行解。,1.大M法 2.兩階段法,Max z =c1x1 +c2x2 +cnxn s.t. a11x1+a12x2 +a1nxn = b1 a21x1+a22x2 + a2nxn = b2 . . . am1x1+am2x2+amnxn = bm x1 ，x2 ， ，xn 0,考慮標準形式的線性規(guī)劃問題,1. 大M法,原問題,輔助問題,人工變量,為了得到原問題的一個基可行解，只要將輔助問題的基可行解中的人工變量全部變?yōu)榉腔兞考纯?。為此，將人工變量加到輔助問題的目標函數中并賦予系數-M。（M