《管理學(xué)運籌學(xué)》PPT課件.ppt

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

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

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

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

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

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

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

8、。 最優(yōu)值：最優(yōu)解對應(yīng)的目標(biāo)函數(shù)值。,可行域：所有可行解的集合稱為可行域。,一、幾個概念：,二、兩變量LP問題的圖解法,圖解法是根據(jù)平面直角坐標(biāo)系和二元一次方程（不等式）的特點設(shè)計的。,1. 圖解法的一般步驟：,（1） 建立直角坐標(biāo)系，以 為橫軸， 為縱軸。,（2） 將約束條件在直角坐標(biāo)系中表示，并找出可行域。,（3）作出目標(biāo)函數(shù)的等值線簇，找出目標(biāo)函數(shù)值的增加（或減小）方向，用箭頭表示。,（4）確定出問題的最優(yōu)解。若為極大（?。┗瘑栴}，目標(biāo)函數(shù)沿增加（減?。┓较蚱揭疲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問題,目標(biāo)函數(shù)等值線,此點為LP的最優(yōu)解,目標(biāo)函數(shù)等值線,可行解集,計算出這個最優(yōu)解:,上述作法稱為LP的圖解法.,本問題有唯一最優(yōu)解.,例2 用圖解法解下面的線性規(guī)劃,目標(biāo)函數(shù)等值線,目標(biāo)函數(shù)等值線,計算出LP的最優(yōu)解及目標(biāo)函數(shù)最優(yōu)值:,除A,B

10、兩個最優(yōu)解外,AB線段上的所有點都是LP的最優(yōu)解.本問題有無窮多最優(yōu)解.,用圖解法解下面的線性規(guī)劃,無可行解,本題無可行解,更無最優(yōu)解,可行域是空集。 可行域存在，則一定是一個凸多邊形。,無界解（可行域一定無界）。 最優(yōu)解存在且唯一，則一定在頂點上達(dá)到。 最優(yōu)解存在且不唯一，一定存在一個頂點是最優(yōu)解 無解,2. 圖解法求解兩變量LP問題時可能出現(xiàn)的情況：,三、可行區(qū)域的幾何結(jié)構(gòu),1. 凸集及其性質(zhì) 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);,性質(zhì)：任意多個凸集的交集仍然是凸集。,1. 凸集及性質(zhì),頂點：設(shè)S是凸集，XS；若對任何X(1)S和 X(2)S， X(1) X(2)，以及任何0 1，都有 X X(1)+ (1- )X(2) 則稱X為凸集S的一個頂點（或極點）。,凸集,凸集,不是凸集,極點,根據(jù)頂點的定義，長方形的四個角點就是長方形區(qū)域的全部頂點，而圓周上的點則是圓形區(qū)域的全部頂點。,2. 可行域的凸性,定理1：若線性規(guī)劃問題的可行域 D=x Rn|AX=b,X0非空，則必為凸集。,可行域凸性的證明思路,設(shè)X1,X2為可行域R內(nèi)任意兩點，則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.由于集合中任意兩點連線上的點均在集合內(nèi)，所以R為凸集,四、基可行解及線性規(guī)劃的基本定理,基可行解的定義 線性規(guī)劃的基本定理 問題,1. 基可行解的定義,考慮標(biāo)準(zhǔn)形式的線性規(guī)劃問題,基：A是約束方程組的系數(shù)矩陣(設(shè)nm)，其秩為m，B是A中的一個m階滿秩子方陣，稱B是線性規(guī)劃問題的一個基。 B中每一個列向量稱為一個基向量，與基向量對應(yīng)的變量稱為基變量。其余變量稱為非基變量。,不失一般性，設(shè),則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ī)劃問題的基解。,顯然，基解中取非零值的變量個數(shù)不超過m，基解的總數(shù)不超過Cnm個。,基可行解：滿足非負(fù)約束的基解稱為基可行解。 可行基：對應(yīng)于基可行解的基。,基可行解,用矩陣形式表示的基解,考慮標(biāo)準(zhǔn)形式的線性規(guī)劃問題：,是它的兩個基，對應(yīng)的基解分別為,可見X1是基可行解，B1是可行基。而X2不是基可行解。,根據(jù)以上定義,

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

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

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

17、當(dāng)xk變?yōu)榛兞繒r，它的值由0變?yōu)檎龜?shù)，比如說xk=0，其余的非基變量仍取值為零。由(3.4)式知，對應(yīng)新解的目標(biāo)函數(shù)值為z=z0+ Kz0，顯然越大目標(biāo)函數(shù)值越大。,可行性原則（最小比值原則）： 的取值應(yīng)保證新解仍然是基可行解。,2) 出基變量的選取原則,進(jìn)基變量和出基變量的選取準(zhǔn)則,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,當(dāng)xk=0成為基變量以后，

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

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

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

21、=(0,25,15,15,0)T,目標(biāo)函數(shù)值為62500。,確定進(jìn)基變量 x1，按照最小比值原則確定出基變量x3，最小比值是0=5. 求出新基對應(yīng)的典式,X2=(5,25,0, 5,0)T,目標(biāo)函數(shù)值為70000。,當(dāng)前的解是最優(yōu)解,5. 單純形表,= - cn+i bi j = cj - cn+i,用單純形表求解例1,例2：利用單純形法求下列線性規(guī)劃問題,將該問題化成標(biāo)準(zhǔn)形式（也是典式）,基變量是：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,解: 化成標(biāo)準(zhǔn)形式,填入單純形表求解,最優(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的檢驗數(shù)為正，但約束條件中x2的系數(shù)全為負(fù)，因此該問題無有限最優(yōu)解。,二、 第一個基可行解的求法,在給定的LP問題的標(biāo)準(zhǔn)形式中，如果約束條件系數(shù)矩陣A中含有一個m階單位矩陣，并且b0，則我們已經(jīng)找到了一個明顯的基可行解，并且約束方程組已經(jīng)是典式，這時可以直接填入單純形表中進(jìn)行迭代。但是實際問題往往并非如此，因此我們需要尋找第一個基可行解，通常使用兩種常用的方法求解第一個基可行解。,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,考慮標(biāo)準(zhǔn)形式的線性規(guī)劃問題,1. 大M法,原問題,輔助問題,人工變量,為了得到原問題的一個基可行解，只要將輔助問題的基可行解中的人工變量全部變?yōu)榉腔兞考纯?。為此，將人工變量加到輔助問題的目標(biāo)函數(shù)中并賦予系數(shù)-M。（M