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

2、在計劃期內(nèi)要安排、兩種產(chǎn)品的生產(chǎn)，已知生產(chǎn)單位產(chǎn)品所需的設備臺時及A、B兩種原材料的消耗、資源的限制，如下表： 問題：工廠應分別生產(chǎn)多少單位、產(chǎn)品才能使工廠獲利最多？,線性規(guī)劃模型： 目標函數(shù)：Max z = 50 x1 + 100 x2 約束條件：s.t. x1 + x2 300 2 x1 + x2 400 x2 250 x1 , x2 0,4,1問題的提出,建模過程 1.理解要解決的問題，了解解題的目標和條件； 2.定義決策變量（ x1 ，x2 ， ，xn ），每一組值表示一個方案； 3.用決策變量的線性函數(shù)形式寫出目標函數(shù)，確定最大化或最小化目標； 4.用一組決策變量的等式或不等式表示解

3、決問題過程中必須遵循的約束條件 一般形式 目標函數(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,5,例1.目標函數(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

4、 0 (E) 得到最優(yōu)解： x1 = 50， x2 = 250 最優(yōu)目標值 z = 27500,2圖 解 法,對于只有兩個決策變量的線性規(guī)劃問題，可以在平面直角坐標系上作圖表示線性規(guī)劃問題的有關概念，并求解。 下面通過例1詳細講解其方法：,6,2圖 解 法,(1)分別取決策變量X1 , X2 為坐標向量建立直角坐標系。在直角坐標系里，圖上任意一點的坐標代表了決策變量的一組值，例1的每個約束條件都代表一個半平面。,7,2圖 解 法,（2）對每個不等式(約束條件)，先取其等式在坐標系中作直線，然后確定不等式所決定的半平面。,8,2圖 解 法,（3）把五個圖合并成一個圖，取各約束條件的公共部分，如圖

5、2-1所示。,9,2圖 解 法,（4）目標函數(shù)z=50 x1+100 x2，當z取某一固定值時得到一條直線，直線上的每一點都具有相同的目標函數(shù)值，稱之為“等值線”。平行移動等值線，當移動到B點時，z在可行域內(nèi)實現(xiàn)了最大化。A，B，C，D，E是可行域的頂點，對有限個約束條件則其可行域的頂點也是有限的。,10,2圖 解 法,線性規(guī)劃的標準化內(nèi)容之一：引入松馳變量（含義是資源的剩余量） 例1 中引入 s1， s2， s3 模型化為 目標函數(shù)：Max z = 50 x1 + 100 x2 + 0 s1 + 0 s2 + 0 s3 約束條件：s.t. x1 + x2 + s1 = 300 2 x1 +

6、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ù)及原料B，但對原料A則還剩余50千克。,11,2圖 解 法,重要結(jié)論： 如果線性規(guī)劃有最優(yōu)解，則一定有一個可行域的頂點對應一個最優(yōu)解； 無窮多個最優(yōu)解。若將例1中的目標函數(shù)變?yōu)閙ax z=50 x1+50 x2，則線段BC上的所有點都代表了最優(yōu)解； 無界解。即可行域的范圍延伸到無窮遠，目標函數(shù)值可以無窮大或無窮小。一般來說，這說明模型

7、有錯，忽略了一些必要的約束條件； 無可行解。若在例1的數(shù)學模型中再增加一個約束條件4x1+3x21200，則可行域為空域，不存在滿足約束條件的解，當然也就不存在最優(yōu)解了。,12,進 一 步 討 論,例2 某公司由于生產(chǎn)需要，共需要A，B兩種原料至少350 噸（A，B兩種材料有一定替代性），其中A原料至少購進125 噸。但由于A，B兩種原料的規(guī)格不同，各自所需的加工時間 也是不同的，加工每噸A原料需要2個小時，加工每噸B原料需 要1小時，而公司總共有600個加工小時。又知道每噸A原料的 價格為2萬元，每噸B原料的價格為3萬元，試問在滿足生產(chǎn)需 要的前提下，在公司加工能力的范圍內(nèi)，如何購買A，B兩

8、種 原料，使得購進成本最低？,13,進 一 步 討 論,解：目標函數(shù)： Min f = 2x1 + 3 x2 約束條件： s.t. x1 + x2 350 x1 125 2 x1 + x2 600 x1 , x2 0 采用圖解法。如下圖：得Q點坐標（250，100）為最優(yōu)解。,14,3圖解法的靈敏度分析,線性規(guī)劃的標準化 一般形式 目標函數(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

9、 + am2 x2 + + amn xn （ =, ）bm x1 ，x2 ， ，xn 0 標準形式 目標函數(shù)： Max 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 0,15,3圖解法的靈敏度分析,可以看出，線性規(guī)劃的標準形式有如下四個特 點： 目標最大化； 約束為等式； 決策變量均非負； 右端項非負。 對于各種非標準形式的線性規(guī)劃問題，

10、我們總可 以通過以下變換，將其轉(zhuǎn)化為標準形式:,16,3圖解法的靈敏度分析,1.極小化目標函數(shù)的問題： 設目標函數(shù)為 Min f = c1x1 + c2x2 + + cnxn (可以)令 z -f ， 則該極小化問題與下面的極大化問題有相同的最優(yōu)解， 即 Max z = - c1x1 - c2x2 - - cnxn 但必須注意，盡管以上兩個問題的最優(yōu)解相同，但它們 最優(yōu)解的目標函數(shù)值卻相差一個符號，即 Min f - Max z,17,3圖解法的靈敏度分析,2、約束條件不是等式的問題： 設約束條件為 ai1 x1+ai2 x2+ +ain xn bi 可以引進一個新的變量s ，使它等于約束右邊

11、與左 邊之差 s=bi(ai1 x1 + ai2 x2 + + ain xn ) 顯然，s 也具有非負約束，即s0， 這時新的約束條件成為 ai1 x1+ai2 x2+ +ain xn+s = bi,18,3圖解法的靈敏度分析,當約束條件為 ai1 x1+ai2 x2+ +ain xn bi 時， 類似地令 s=(ai1 x1+ai2 x2+ +ain xn)- bi 顯然，s 也具有非負約束，即s0，這時新的約 束條件成為 ai1 x1+ai2 x2+ +ain xn-s = bi,19,3圖解法的靈敏度分析,為了使約束由不等式成為等式而引進的變量s,當 不等式為“小于等于”時稱為“松弛變量

12、”；當不等式 為“大于等于”時稱為“剩余變量”。如果原問題中有 若干個非等式約束，則將其轉(zhuǎn)化為標準形式時，必須 對各個約束引進不同的松弛變量。,3.右端項有負值的問題： 在標準形式中，要求右端項必須每一個分量非負。當某一個右端項系數(shù)為負時，如 bi0，則把該等式約束兩端同時乘以-1，得到：-ai1 x1-ai2 x2- -ain xn = -bi。,20,3圖解法的靈敏度分析,例：將以下線性規(guī)劃問題轉(zhuǎ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 , x

13、3 0 解：首先,將目標函數(shù)轉(zhuǎn)換成極大化： 令 z= -f = -2x1+3x2-4x3 其次考慮約束，有2個不等式約束，引進松弛變量 x4，x5 0。 第三個約束條件的右端值為負，在等式兩邊同時乘-1。,21,3圖解法的靈敏度分析,通過以上變換，可以得到以下標準形式的線性規(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 * 變量無符號限制的問題*： 在標準形式中，必須每一個變量均有非負約束。當某一個變量xj沒 有非負約束時，

14、可以令 xj = xj- xj” 其中 xj0，xj”0 即用兩個非負變量之差來表示一個無符號限制的變量，當然xj的符號 取決于xj和xj”的大小。,22,3圖解法的靈敏度分析,靈敏度分析：建立數(shù)學模型和求得最優(yōu)解后，研究線性規(guī) 劃的一個或多個參數(shù)（系數(shù)）ci , aij , bj 變化時，對最優(yōu)解產(chǎn) 生的影響。 3.1 目標函數(shù)中的系數(shù) ci 的靈敏度分析 考慮例1的情況， ci 的變化只影響目標函數(shù)等值線的斜率， 目標函數(shù) z = 50 x1 + 100 x2 在 z = x2 (x2 = z 斜率為0 ) 到 z = x1 + x2 (x2 = -x1 + z 斜 率為 -1 )之間時，

15、原最優(yōu)解 x1 = 50，x2 = 100 仍是最優(yōu)解。 一般情況： z = c1 x1 + c2 x2 寫成斜截式 x2 = - (c1 / c2 ) x1 + z / c2 目標函數(shù)等值線的斜率為 - (c1 / c2 ) ， 當 -1 - (c1 / c2 ) 0 （*） 時，原最優(yōu)解仍是最優(yōu)解。,23,3圖解法的靈敏度分析,假設產(chǎn)品的利潤100元不變，即 c2 = 100，代到式（*）并整理得 0 c1 100 假設產(chǎn)品的利潤 50 元不變，即 c1 = 50 ，代到式（*）并整理得 50 c2 + 假若產(chǎn)品、的利潤均改變，則可直接用式（*）來判斷。 假設產(chǎn)品、的利潤分別為60元、55

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