運籌學第2章線性規(guī)劃的圖解法

1、管管 理理 運運 籌籌 學學1第二章線性規(guī)劃的圖解法l1 1問題的提出問題的提出l2 2圖解法圖解法l3 3圖解法的靈敏度分析圖解法的靈敏度分析管管 理理 運運 籌籌 學學2第二章線性規(guī)劃的圖解法線性規(guī)劃的組成：線性規(guī)劃的組成：目標函數(shù) Max F 或 Min F約束條件 s.t. (subject to) 滿足于決策變量 用符號來表示可控制的因素管管 理理 運運 籌籌 學學31問題的提出例例1. 某工廠在計劃期內(nèi)要安排、兩種產(chǎn)品的生產(chǎn)，已知生產(chǎn)單位產(chǎn)品所需的設備臺時及A、B兩種原材料的消耗、資源的限制，如下表：問題：工廠應分別生產(chǎn)多少單位、產(chǎn)品才能使工廠獲利最多？線性規(guī)劃模型：線性規(guī)劃模型：

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

3、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 0 (E)得到最優(yōu)解： x1 = 50， x2 = 250 最優(yōu)目標值 z = 275002圖圖 解解 法法 對于只有兩個

4、決策變量的線性規(guī)劃問題，可以在平面直角坐標系上作圖表示線性規(guī)劃問題的有關(guān)概念，并求解。 下面通過例1詳細講解其方法：管管 理理 運運 籌籌 學學6 2圖 解 法一、基本概念一、基本概念l可行解可行解(Feasible Solution)任一滿足約束條件任一滿足約束條件的一組決策變量的數(shù)值；的一組決策變量的數(shù)值；l可行域可行域(Feasible Region)所有可行解組成的集所有可行解組成的集合，也稱為可行解集；合，也稱為可行解集；l目標函數(shù)等值線目標函數(shù)等值線(Objective function line)為于為于同一直線上的點，具有相同的目標函數(shù)值；同一直線上的點，具有相同的目標函數(shù)值；

5、二、圖解法步驟二、圖解法步驟(Procedure)（1）畫出線性規(guī)劃問題的可行域；）畫出線性規(guī)劃問題的可行域；（2）畫出兩條目標函數(shù)等值線；）畫出兩條目標函數(shù)等值線；（3）平行移動目標函數(shù)等值線，使目標函數(shù)在可行）平行移動目標函數(shù)等值線，使目標函數(shù)在可行域范圍內(nèi)達到最優(yōu)。域范圍內(nèi)達到最優(yōu)。管管 理理 運運 籌籌 學學7三、圖解法舉例例例1 max Z=50 x1+100 x2 x1 + x2300 2x1 + x2400 x2250 x1、x20 x2x1z* =27500z1=50 x1+100 x2=0BOACDz2=14000該問題有唯一最優(yōu)解該問題有唯一最優(yōu)解x1=50=50；x2=2

6、50=250 x1 + x23002x1 + x2400 x2250管管 理理 運運 籌籌 學學8例例2 max Z=50 x1+50 x2 x1 + x2300 2x1 + x2400 x2250 x1、x20 x2x1z1=50 x1+50 x2=0B點和點和C點所代表的坐點所代表的坐標同時為最優(yōu)解，即該標同時為最優(yōu)解，即該問題有問題有無窮多最優(yōu)解無窮多最優(yōu)解BOACDx1 + x23002x1 + x2400 x2250max Z=50 x1+100 x2z* =27500z2=15000管管 理理 運運 籌籌 學學9例例3 max z =x1+x2 x1x2 1 x1 + 2x20 x

7、1、x20 問題有無界解問題有無界解 (unbounded)例例4 min z =x1+x2 x1x2 1 x1 + 2x20 x1、x20 有唯一最優(yōu)解有唯一最優(yōu)解111z=32z=5OA2x1xx1x2 1x1 + 2x20管管 理理 運運 籌籌 學學10例例4 max z =x1+x2 x1 + 2x21 x1 + x22 x1、x20 問題無可行解問題無可行解 (no feasible solution)管管 理理 運運 籌籌 學學11直 觀 結(jié) 論1)可行域可以是個凸多邊形，可能無界，也可可行域可以是個凸多邊形，可能無界，也可能為空；能為空；2)若線性規(guī)劃問題的最優(yōu)解存在，它一定可以

8、若線性規(guī)劃問題的最優(yōu)解存在，它一定可以在可行域的某一個頂點上得到；在可行域的某一個頂點上得到；3)若在兩個頂點上同時得到最優(yōu)解，則該兩點若在兩個頂點上同時得到最優(yōu)解，則該兩點連線上的所有點都是最優(yōu)解，即連線上的所有點都是最優(yōu)解，即LP有無窮多有無窮多最優(yōu)解；最優(yōu)解；4)若可行域非空有界，則一定有最優(yōu)解。若可行域非空有界，則一定有最優(yōu)解。管管 理理 運運 籌籌 學學122圖 解 法l線性規(guī)劃的標準化內(nèi)容之一：線性規(guī)劃的標準化內(nèi)容之一：引入松馳變量（含義是資源的剩余量） 例1 中引入 s1， s2， s3 模型化為 目標函數(shù)：Max z = 50 x1 + 100 x2 + 0 s1 + 0 s2

9、 + 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管管 理理 運運 籌籌 學學13進 一 步 討 論 例例2 2 某公司由于生產(chǎn)需要，共需要A，B兩種原料至少350噸（A，B兩種材料有一定替代性），其中A原料至少購進125噸。但由于A，B兩種原料的規(guī)格不同，各自所需的加工時間也是不同的，加工每噸A原料需要2個小時，加工每噸B原料需要1小時，而公司總共有600個加工小

10、時。又知道每噸A原料的價格為2萬元，每噸B原料的價格為3萬元，試問在滿足生產(chǎn)需要的前提下，在公司加工能力的范圍內(nèi)，如何購買A，B兩種原料，使得購進成本最低？管管 理理 運運 籌籌 學學14進 一 步 討 論解：目標函數(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)解。100200300 400 500 600100200300400600500 x1 =125x1+x2 =3502x1+3x2 =8002x1+3x2 =9002x1+x2

11、=6002x1+3x2 =1200 x1 x2 Q管管 理理 運運 籌籌 學學153圖解法的靈敏度分析線性規(guī)劃的標準化線性規(guī)劃的標準化l一般形式一般形式目標函數(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 l標準形式標準形式目標函數(shù)： Max z = c1 x1 + c2 x2 + + cn xn

12、 約束條件： 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管管 理理 運運 籌籌 學學163圖解法的靈敏度分析 可以看出，線性規(guī)劃的標準形式有如下四個特點：l目標最大化；l約束為等式；l決策變量均非負；l右端項非負。 對于各種非標準形式的線性規(guī)劃問題，都可以轉(zhuǎn)化為標準形式。管管 理理 運運 籌籌 學學173圖解法的靈敏度分析1.極小化目標函數(shù)的問題： 設目標函數(shù)為 Min f = c1x1 + c2x

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

14、ai1 x1+ai2 x2+ +ain xn+s = bi管管 理理 運運 籌籌 學學193圖解法的靈敏度分析 當約束條件為 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管管 理理 運運 籌籌 學學203圖解法的靈敏度分析 為了使約束由不等式成為等式而引進的變量s,當不等式為“小于等于”時稱為“松弛變量”；當不等式為“大于等于”時稱為“剩余變量”。如果原問題中有若干個非等式約束，則將其轉(zhuǎn)化為標準形

15、式時，必須對各個約束引進不同的松弛變量。 3.右端項有負值的問題： 在標準形式中，要求右端項必須每一個分量非負。當某一個右端項系數(shù)為負時，如 bi0，則把該等式約束兩端同時乘以-1，得到：-ai1 x1-ai2 x2- -ain xn = -bi。管管 理理 運運 籌籌 學學213圖解法的靈敏度分析例：將以下線性規(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 , x3 0 Max z = - 2x1 + 3 x2 - 4x3 s.t. 3x1+

16、4x2-5x3 +x4 = 6 2x1 +x3 -x5= 8 -x1 -x2 -x3 = 9 x1 ,x2 ,x3 ,x4 ,x5 0管管 理理 運運 籌籌 學學223圖解法的靈敏度分析 在標準形式中，必須每一個變量均有非負約束。當某一個變量xj沒有非負約束時，可以令 xj = xj- xj” 其中 xj0，xj”0 即用兩個非負變量之差來表示一個無符號限制的變量，當然xj的符號取決于xj和xj”的大小。管管 理理 運運 籌籌 學學233圖解法的靈敏度分析 靈敏度分析靈敏度分析：建立數(shù)學模型和求得最優(yōu)解后，研究線性規(guī)劃的一個或多個參數(shù)（系數(shù)）ci , aij , bj 變化時，對最優(yōu)解產(chǎn)生的影

17、響。3.1 目標函數(shù)中的系數(shù)目標函數(shù)中的系數(shù) ci 的靈敏度分析的靈敏度分析 考慮例1的情況， ci 的變化只影響目標函數(shù)等值線的斜率，目標函數(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)解。l一般情況： z = c1 x1 + c2 x2 寫成斜截式 x2 = - (c1 / c2 ) x1 + z / c2 目標函數(shù)等值線的斜率為 - (c1 / c2 ) ， 當 -1 - (c1 / c2 ) 0 （*） 時，原最

18、優(yōu)解仍是最優(yōu)解。管管 理理 運運 籌籌 學學243圖解法的靈敏度分析l假設產(chǎn)品的利潤100元不變，即 c2 = 100，代到式（*）并整理得 0 c1 100 l假設產(chǎn)品的利潤 50 元不變，即 c1 = 50 ，代到式（*）并整理得 50 c2 + l假若產(chǎn)品、的利潤均改變，則可直接用式（*）來判斷。l假設產(chǎn)品、的利潤分別為60元、55元，則 - 2 - (60 / 55) - 1 那么，最優(yōu)解為 z = x1 + x2 和 z = 2 x1 + x2 的交點 x1 = 100，x2 = 200 。管管 理理 運運 籌籌 學學253圖解法的靈敏度分析 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元利潤，稱為該約束條件的對偶價格。管管 理理 運運 籌籌 學學263圖解