管理運(yùn)籌學(xué)線性規(guī)劃的圖解法課件

1、管理運(yùn)籌學(xué)線性規(guī)劃的圖解法管理運(yùn)籌學(xué)線性規(guī)劃的圖解法管理運(yùn)籌學(xué)線性規(guī)劃的圖解法第二章線性規(guī)劃的圖解法在管理中一些典型的線性規(guī)劃應(yīng)用合理利用線材問題：如何在保證生產(chǎn)的條件下，下料最少配料問題：在原料供應(yīng)量的限制下如何獲取最大利潤投資問題：從投資項目中選取方案，使投資回報最大產(chǎn)品生產(chǎn)計劃：合理利用人力、物力、財力等，使獲利最大勞動力安排：用最少的勞動力來滿足工作的需要運(yùn)輸問題：如何制定調(diào)運(yùn)方案，使總運(yùn)費(fèi)最小線性規(guī)劃的組成：目標(biāo)函數(shù) Max F 或 Min F約束條件 s.t. (subject to) 滿足于決策變量 用符號來表示可控制的因素2第二章線性規(guī)劃的圖解法在管理中一些典型的線性規(guī)劃應(yīng)用合

2、理利用線材問題：如何在保證生產(chǎn)的條件下，下料最少配料問題：在原料供應(yīng)量的限制下如何獲取最大利潤投資問題：從投資項目中選取方案，使投資回報最大產(chǎn)品生產(chǎn)計劃：合理利用人力、物力、財力等，使獲利最大勞動力安排：用最少的勞動力來滿足工作的需要運(yùn)輸問題：如何制定調(diào)運(yùn)方案，使總運(yùn)費(fèi)最小線性規(guī)劃的組成：目標(biāo)函數(shù) Max F 或 Min F約束條件 s.t. (subject to) 滿足于決策變量 用符號來表示可控制的因素21問題的提出例1. 某工廠在計劃期內(nèi)要安排、兩種產(chǎn)品的生產(chǎn)，已知生產(chǎn)單位產(chǎn)品所需的設(shè)備臺時及A、B兩種原材料的消耗、資源的限制，如下表：問題：工廠應(yīng)分別生產(chǎn)多少單位、產(chǎn)品才能使工廠獲利最

3、多？線性規(guī)劃模型： 目標(biāo)函數(shù)：Max z = 50 x1 + 100 x2 約束條件：s.t. x1 + x2 300 2 x1 + x2 400 x2 250 x1 , x2 031問題的提出建模過程1.理解要解決的問題，了解解題的目標(biāo)和條件；2.定義決策變量（ x1 ，x2 ， ，xn ），每一組值表示一個方案；3.用決策變量的線性函數(shù)形式寫出目標(biāo)函數(shù)，確定最大化或最小化目標(biāo)；4.用一組決策變量的等式或不等式表示解決問題過程中必須遵循的約束條件一般形式目標(biāo)函數(shù)： Max （Min） z = c1 x1 + c2 x2 + + cn xn 約束條件： s.t. a11 x1 + a12 x2

4、 + + a1n xn （ =, ）b1 a21 x1 + a22 x2 + + a2n xn （ =, ）b2 am1 x1 + am2 x2 + + amn xn （ =, ）bm x1 ，x2 ， ，xn 0 4例1.目標(biāo)函數(shù)： Max z = 50 x1 + 100 x2 約束條件： s.t. x1 + x2 300 (A) 2 x1 + x2 400 (B) x2 250 (C) x1 0 (D) x2 0 (E)得到最優(yōu)解： x1 = 50， x2 = 250 最優(yōu)目標(biāo)值 z = 275002圖 解 法 對于只有兩個決策變量的線性規(guī)劃問題，可以在平面直角坐標(biāo)系上作圖表示線性規(guī)劃問題

5、的有關(guān)概念，并求解。 下面通過例1詳細(xì)講解其方法：52圖 解 法 (1)分別取決策變量X1 , X2 為坐標(biāo)向量建立直角坐標(biāo)系。在直角坐標(biāo)系里，圖上任意一點(diǎn)的坐標(biāo)代表了決策變量的一組值，例1的每個約束條件都代表一個半平面。x2x1X20X2=0 x2x1X10X1=062圖 解 法（2）對每個不等式(約束條件)，先取其等式在坐標(biāo)系中作直線，然后確定不等式所決定的半平面。100200300100200300 x1+x2300 x1+x2=3001001002002x1+x24002x1+x2=40030020030040072圖 解 法（3）把五個圖合并成一個圖，取各約束條件的公共部分，如圖2-

6、1所示。100100 x2250 x2=250200300200300 x1x2x2=0 x1=0 x2=250 x1+x2=3002x1+x2=400圖2-182圖 解 法（4）目標(biāo)函數(shù)z=50 x1+100 x2，當(dāng)z取某一固定值時得到一條直線，直線上的每一點(diǎn)都具有相同的目標(biāo)函數(shù)值，稱之為“等值線”。平行移動等值線，當(dāng)移動到B點(diǎn)時，z在可行域內(nèi)實(shí)現(xiàn)了最大化。A，B，C，D，E是可行域的頂點(diǎn)，對有限個約束條件則其可行域的頂點(diǎn)也是有限的。x1x2z=20000=50 x1+100 x2圖2-2z=27500=50 x1+100 x2z=0=50 x1+100 x2z=10000=50 x1+1

7、00 x2CBADE92圖 解 法線性規(guī)劃的標(biāo)準(zhǔn)化內(nèi)容之一：引入松馳變量（含義是資源的剩余量） 例1 中引入 s1， s2， s3 模型化為 目標(biāo)函數(shù)：Max z = 50 x1 + 100 x2 + 0 s1 + 0 s2 + 0 s3 約束條件：s.t. x1 + x2 + s1 = 300 2 x1 + x2 + s2 = 400 x2 + s3 = 250 x1 , x2 , s1 , s2 , s3 0 對于最優(yōu)解 x1 =50 x2 = 250 ， s1 = 0 s2 =50 s3 = 0 說明：生產(chǎn)50單位產(chǎn)品和250單位產(chǎn)品將消耗完所有可能的設(shè)備臺時數(shù)及原料B，但對原料A則還剩

8、余50千克。102圖 解 法重要結(jié)論：如果線性規(guī)劃有最優(yōu)解，則一定有一個可行域的頂點(diǎn)對應(yīng)一個最優(yōu)解；無窮多個最優(yōu)解。若將例1中的目標(biāo)函數(shù)變?yōu)閙ax z=50 x1+50 x2，則線段BC上的所有點(diǎn)都代表了最優(yōu)解；無界解。即可行域的范圍延伸到無窮遠(yuǎn)，目標(biāo)函數(shù)值可以無窮大或無窮小。一般來說，這說明模型有錯，忽略了一些必要的約束條件；無可行解。若在例1的數(shù)學(xué)模型中再增加一個約束條件4x1+3x21200，則可行域為空域，不存在滿足約束條件的解，當(dāng)然也就不存在最優(yōu)解了。11進(jìn) 一 步 討 論 例2 某公司由于生產(chǎn)需要，共需要A，B兩種原料至少350噸（A，B兩種材料有一定替代性），其中A原料至少購進(jìn)1

9、25噸。但由于A，B兩種原料的規(guī)格不同，各自所需的加工時間也是不同的，加工每噸A原料需要2個小時，加工每噸B原料需要1小時，而公司總共有600個加工小時。又知道每噸A原料的價格為2萬元，每噸B原料的價格為3萬元，試問在滿足生產(chǎn)需要的前提下，在公司加工能力的范圍內(nèi)，如何購買A，B兩種原料，使得購進(jìn)成本最低？12進(jìn) 一 步 討 論解：目標(biāo)函數(shù)： Min f = 2x1 + 3 x2 約束條件：s.t. x1 + x2 350 x1 125 2 x1 + x2 600 x1 , x2 0 采用圖解法。如下圖：得Q點(diǎn)坐標(biāo)（250，100）為最優(yōu)解。100200300400500600100200300

10、400600500 x1 =125x1+x2 =3502x1+3x2 =8002x1+3x2 =9002x1+x2 =6002x1+3x2 =1200 x1 x2 Q133圖解法的靈敏度分析線性規(guī)劃的標(biāo)準(zhǔn)化一般形式目標(biāo)函數(shù)： Max （Min） z = c1 x1 + c2 x2 + + cn xn 約束條件： s.t. a11 x1 + a12 x2 + + a1n xn （ =, ）b1 a21 x1 + a22 x2 + + a2n xn （ =, ）b2 am1 x1 + am2 x2 + + amn xn （ =, ）bm x1 ，x2 ， ，xn 0 標(biāo)準(zhǔn)形式目標(biāo)函數(shù)： Max z

11、 = c1 x1 + c2 x2 + + cn xn 約束條件： s.t. a11 x1 + a12 x2 + + a1n xn = b1 a21 x1 + a22 x2 + + a2n xn = b2 am1 x1 + am2 x2 + + amn xn = bm x1 ，x2 ， ，xn 0，bi 0143圖解法的靈敏度分析 可以看出，線性規(guī)劃的標(biāo)準(zhǔn)形式有如下四個特點(diǎn)：目標(biāo)最大化；約束為等式；決策變量均非負(fù)；右端項非負(fù)。 對于各種非標(biāo)準(zhǔn)形式的線性規(guī)劃問題，我們總可以通過以下變換，將其轉(zhuǎn)化為標(biāo)準(zhǔn)形式:153圖解法的靈敏度分析1.極小化目標(biāo)函數(shù)的問題： 設(shè)目標(biāo)函數(shù)為 Min f = c1x1

12、+ c2x2 + + cnxn (可以)令 z -f ， 則該極小化問題與下面的極大化問題有相同的最優(yōu)解，即 Max z = - c1x1 - c2x2 - - cnxn 但必須注意，盡管以上兩個問題的最優(yōu)解相同，但它們最優(yōu)解的目標(biāo)函數(shù)值卻相差一個符號，即 Min f - Max z163圖解法的靈敏度分析2、約束條件不是等式的問題： 設(shè)約束條件為 ai1 x1+ai2 x2+ +ain xn bi 可以引進(jìn)一個新的變量s ，使它等于約束右邊與左邊之差 s=bi(ai1 x1 + ai2 x2 + + ain xn )顯然，s 也具有非負(fù)約束，即s0， 這時新的約束條件成為 ai1 x1+ai

13、2 x2+ +ain xn+s = bi173圖解法的靈敏度分析 當(dāng)約束條件為 ai1 x1+ai2 x2+ +ain xn bi 時， 類似地令 s=(ai1 x1+ai2 x2+ +ain xn)- bi 顯然，s 也具有非負(fù)約束，即s0，這時新的約束條件成為 ai1 x1+ai2 x2+ +ain xn-s = bi183圖解法的靈敏度分析 為了使約束由不等式成為等式而引進(jìn)的變量s,當(dāng)不等式為“小于等于”時稱為“松弛變量”；當(dāng)不等式為“大于等于”時稱為“剩余變量”。如果原問題中有若干個非等式約束，則將其轉(zhuǎn)化為標(biāo)準(zhǔn)形式時，必須對各個約束引進(jìn)不同的松弛變量。 3.右端項有負(fù)值的問題： 在標(biāo)準(zhǔn)

14、形式中，要求右端項必須每一個分量非負(fù)。當(dāng)某一個右端項系數(shù)為負(fù)時，如 bi0，則把該等式約束兩端同時乘以-1，得到：-ai1 x1-ai2 x2- -ain xn = -bi。193圖解法的靈敏度分析例：將以下線性規(guī)劃問題轉(zhuǎn)化為標(biāo)準(zhǔn)形式 Min f = 2 x1 -3x2 + 4 x3 s.t. 3 x1 + 4x2 - 5 x3 6 2 x1 + x3 8 x1 + x2 + x3 = -9 x1 , x2 , x3 0解：首先,將目標(biāo)函數(shù)轉(zhuǎn)換成極大化： 令 z= -f = -2x1+3x2-4x3 其次考慮約束，有2個不等式約束，引進(jìn)松弛變量x4，x5 0。 第三個約束條件的右端值為負(fù)，在等

15、式兩邊同時乘-1。203圖解法的靈敏度分析通過以上變換，可以得到以下標(biāo)準(zhǔn)形式的線性規(guī)劃問題： Max z = - 2x1 + 3 x2 - 4x3 s.t. 3x1+4x2-5x3 +x4 = 6 2x1 +x3 -x5= 8 -x1 -x2 -x3 = 9 x1 ,x2 ,x3 ,x4 ,x5 0* 變量無符號限制的問題*： 在標(biāo)準(zhǔn)形式中，必須每一個變量均有非負(fù)約束。當(dāng)某一個變量xj沒有非負(fù)約束時，可以令 xj = xj- xj” 其中 xj0，xj”0 即用兩個非負(fù)變量之差來表示一個無符號限制的變量，當(dāng)然xj的符號取決于xj和xj”的大小。213圖解法的靈敏度分析 靈敏度分析：建立數(shù)學(xué)模型

16、和求得最優(yōu)解后，研究線性規(guī)劃的一個或多個參數(shù)（系數(shù)）ci , aij , bj 變化時，對最優(yōu)解產(chǎn)生的影響。3.1 目標(biāo)函數(shù)中的系數(shù) ci 的靈敏度分析 考慮例1的情況， ci 的變化只影響目標(biāo)函數(shù)等值線的斜率，目標(biāo)函數(shù) z = 50 x1 + 100 x2 在 z = x2 (x2 = z 斜率為0 ) 到 z = x1 + x2 (x2 = -x1 + z 斜率為 -1 )之間時，原最優(yōu)解 x1 = 50，x2 = 100 仍是最優(yōu)解。一般情況： z = c1 x1 + c2 x2 寫成斜截式 x2 = - (c1 / c2 ) x1 + z / c2 目標(biāo)函數(shù)等值線的斜率為 - (c1

17、/ c2 ) ， 當(dāng) -1 - (c1 / c2 ) 0 （*） 時，原最優(yōu)解仍是最優(yōu)解。223圖解法的靈敏度分析假設(shè)產(chǎn)品的利潤100元不變，即 c2 = 100，代到式（*）并整理得 0 c1 100 假設(shè)產(chǎn)品的利潤 50 元不變，即 c1 = 50 ，代到式（*）并整理得 50 c2 + 假若產(chǎn)品、的利潤均改變，則可直接用式（*）來判斷。假設(shè)產(chǎn)品、的利潤分別為60元、55元，則 - 2 - (60 / 55) - 1 那么，最優(yōu)解為 z = x1 + x2 和 z = 2 x1 + x2 的交點(diǎn) x1 = 100，x2 = 200 。233圖解法的靈敏度分析 3.2 約束條件中右邊系數(shù) b

18、j 的靈敏度分析 當(dāng)約束條件中右邊系數(shù) bj 變化時，線性規(guī)劃的可行域發(fā)生變化，可能引起最優(yōu)解的變化。 考慮例1的情況： 假設(shè)設(shè)備臺時增加10個臺時，即 b1變化為310，這時可行域擴(kuò)大，最優(yōu)解為 x2 = 250 和 x1 + x2 = 310 的交點(diǎn) x1 = 60，x2 = 250 。 變化后的總利潤 - 變化前的總利潤 = 增加的利潤 (5060+ 100250) - (50 50+100 250) = 500 ，500 / 10 = 50 元 說明在一定范圍內(nèi)每增加（減少）1個臺時的設(shè)備能力就可增加（減少）50元利潤，稱為該約束條件的對偶價格。243圖解法的靈敏度分析 假設(shè)原料 A 增加10