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

1、管理運籌學(xué)管理運籌學(xué)- - 第二章第二章 線形規(guī)劃的圖解法線形規(guī)劃的圖解法1第二章 線性規(guī)劃的圖解法 1 問題的提出 2 圖解法 3 圖解法的靈敏度分析管理運籌學(xué)管理運籌學(xué)- - 第二章第二章 線形規(guī)劃的圖解法線形規(guī)劃的圖解法2第二章 線性規(guī)劃的圖解法在管理中一些典型的線性規(guī)劃應(yīng)用 合理利用線材問題：如何在保證生產(chǎn)的條件下，下料最少 配料問題：在原料供應(yīng)量的限制下如何獲取最大利潤 投資問題：從投資項目中選取方案，使投資回報最大 產(chǎn)品生產(chǎn)計劃：合理利用人力、物力、財力等，使獲利最大 勞動力安排：用最少的勞動力來滿足工作的需要 運輸問題：如何制定調(diào)運方案，使總運費最小 能解決問題的共性特點：能解決

2、問題的共性特點： 11都有要求達到某些數(shù)量上的最大化或最都有要求達到某些數(shù)量上的最大化或最小化的目標。小化的目標。 2.2.所有問題都是在一定的約束條件下來追求所有問題都是在一定的約束條件下來追求其目標的。其目標的。管理運籌學(xué)管理運籌學(xué)- - 第二章第二章 線形規(guī)劃的圖解法線形規(guī)劃的圖解法31 問題的提出例例1. 某工廠在計劃期內(nèi)要安排某工廠在計劃期內(nèi)要安排、兩種產(chǎn)品的生產(chǎn)，已知兩種產(chǎn)品的生產(chǎn)，已知生產(chǎn)單位產(chǎn)品所需的設(shè)備臺時及生產(chǎn)單位產(chǎn)品所需的設(shè)備臺時及A、B兩種原材料的消耗、兩種原材料的消耗、資源的限制，如下表：資源的限制，如下表：問題：工廠應(yīng)分別生產(chǎn)多少單位問題：工廠應(yīng)分別生產(chǎn)多少單位、產(chǎn)

3、品才能使工廠獲利產(chǎn)品才能使工廠獲利最多？最多？管理運籌學(xué)管理運籌學(xué)- - 第二章第二章 線形規(guī)劃的圖解法線形規(guī)劃的圖解法4一、線性規(guī)劃數(shù)學(xué)模型的三要素一、線性規(guī)劃數(shù)學(xué)模型的三要素 現(xiàn)實世界中人們關(guān)心、研究的實際對象為原型，模型是將現(xiàn)實世界中人們關(guān)心、研究的實際對象為原型，模型是將某一部分信息簡縮、提煉而構(gòu)成的原型替代物。數(shù)學(xué)模型某一部分信息簡縮、提煉而構(gòu)成的原型替代物。數(shù)學(xué)模型就是對現(xiàn)實世界的一個特定對象，為達到一定目的，根據(jù)就是對現(xiàn)實世界的一個特定對象，為達到一定目的，根據(jù)內(nèi)在規(guī)律做出必要的簡化假設(shè)，并運用適當數(shù)學(xué)工具得到內(nèi)在規(guī)律做出必要的簡化假設(shè)，并運用適當數(shù)學(xué)工具得到的一個數(shù)學(xué)結(jié)構(gòu)。的一

4、個數(shù)學(xué)結(jié)構(gòu)。 決策變量決策變量 需要決策的量，即待求的未知數(shù)需要決策的量，即待求的未知數(shù) 目標函數(shù)目標函數(shù) 需要優(yōu)化的量，即欲達的目標，用決策變量的需要優(yōu)化的量，即欲達的目標，用決策變量的表達式表示，表達式表示，Max F 或或 Min F 約束條件約束條件 為實現(xiàn)優(yōu)化目標需受到的限制，用決策變量的為實現(xiàn)優(yōu)化目標需受到的限制，用決策變量的等式或不等式表示。等式或不等式表示。 s.t. (subject to) 滿足于滿足于管理運籌學(xué)管理運籌學(xué)- - 第二章第二章 線形規(guī)劃的圖解法線形規(guī)劃的圖解法5線形規(guī)劃的數(shù)學(xué)模型 例題例例1. 問題：工廠應(yīng)分別生產(chǎn)多少單位、產(chǎn)品才能使工廠獲利最多？決策變量：

5、產(chǎn)品和產(chǎn)品的產(chǎn)量單位數(shù)，記為x1 , x2 ；目標函數(shù)：總利潤，記為z ， 則z = 50 x1 + 100 x2 ，為體現(xiàn)對其追求極大化，在z的前面冠以極大號Max；約束條件：分別來自設(shè)備、原料A、原料B 的約束和產(chǎn)量非負的約束，表示為：數(shù)學(xué)模型數(shù)學(xué)模型 目標函數(shù)：Max z = 50 x1 + 100 x2 約束條件：s.t. x1 + x2 300 2 x1 + x2 400 x2 250 x1 , x2 0管理運籌學(xué)管理運籌學(xué)- - 第二章第二章 線形規(guī)劃的圖解法線形規(guī)劃的圖解法6二、線性規(guī)劃問題的建模過程1.理解要解決的問題，了解解題的目標和條件；2.定義決策變量（ x1 ，x2 ，

6、 ，xn ），每一組值表示一個方案；3.用決策變量的線性函數(shù)形式寫出目標函數(shù)，確定最大化或最小化目標；4.用一組決策變量的等式或不等式表示解決問題過程中必須遵循的約束條件 一般形式目標函數(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 管理運籌學(xué)管理運籌學(xué)- - 第二章第二章 線形規(guī)劃的圖解法線形規(guī)

7、劃的圖解法7管理運籌學(xué)管理運籌學(xué)- - 第二章第二章 線形規(guī)劃的圖解法線形規(guī)劃的圖解法8管理運籌學(xué)管理運籌學(xué)- - 第二章第二章 線形規(guī)劃的圖解法線形規(guī)劃的圖解法9 管理運籌學(xué)管理運籌學(xué)- - 第二章第二章 線形規(guī)劃的圖解法線形規(guī)劃的圖解法10 線性規(guī)劃模型特點總結(jié) 目標函數(shù)為變量的線性函數(shù) 約束條件也為變量的線性等式或不等式管理運籌學(xué)管理運籌學(xué)- - 第二章第二章 線形規(guī)劃的圖解法線形規(guī)劃的圖解法11課堂練習(xí) 練習(xí)：試寫出下列線形規(guī)劃模型的一般形式 1、某木材生產(chǎn)廠加工一批木料（直徑相同）木料需求為3米的90根，4米的60根，已知現(xiàn)有木料的長度為10米，問怎么加工最省料？ 2、課本P26第8

8、題管理運籌學(xué)管理運籌學(xué)- - 第二章第二章 線形規(guī)劃的圖解法線形規(guī)劃的圖解法12 三、線性規(guī)劃的標準形式S.t管理運籌學(xué)管理運籌學(xué)- - 第二章第二章 線形規(guī)劃的圖解法線形規(guī)劃的圖解法13n1 jn1 jS.t管理運籌學(xué)管理運籌學(xué)- - 第二章第二章 線形規(guī)劃的圖解法線形規(guī)劃的圖解法14n1 j管理運籌學(xué)管理運籌學(xué)- - 第二章第二章 線形規(guī)劃的圖解法線形規(guī)劃的圖解法15管理運籌學(xué)管理運籌學(xué)- - 第二章第二章 線形規(guī)劃的圖解法線形規(guī)劃的圖解法16管理運籌學(xué)管理運籌學(xué)- - 第二章第二章 線形規(guī)劃的圖解法線形規(guī)劃的圖解法17管理運籌學(xué)管理運籌學(xué)- - 第二章第二章 線形規(guī)劃的圖解法線形規(guī)劃的圖

9、解法18管理運籌學(xué)管理運籌學(xué)- - 第二章第二章 線形規(guī)劃的圖解法線形規(guī)劃的圖解法19 x x1 1 , x, x2 2 , , s s1 1 , s, s2 2 , , s s3 3 0 0S.tS.t管理運籌學(xué)管理運籌學(xué)- - 第二章第二章 線形規(guī)劃的圖解法線形規(guī)劃的圖解法20管理運籌學(xué)管理運籌學(xué)- - 第二章第二章 線形規(guī)劃的圖解法線形規(guī)劃的圖解法21管理運籌學(xué)管理運籌學(xué)- - 第二章第二章 線形規(guī)劃的圖解法線形規(guī)劃的圖解法22管理運籌學(xué)管理運籌學(xué)- - 第二章第二章 線形規(guī)劃的圖解法線形規(guī)劃的圖解法23S.t管理運籌學(xué)管理運籌學(xué)- - 第二章第二章 線形規(guī)劃的圖解法線形規(guī)劃的圖解法24

10、管理運籌學(xué)管理運籌學(xué)- - 第二章第二章 線形規(guī)劃的圖解法線形規(guī)劃的圖解法25 S.t管理運籌學(xué)管理運籌學(xué)- - 第二章第二章 線形規(guī)劃的圖解法線形規(guī)劃的圖解法26例1.目標函數(shù)： Max z = 50 x1 + 100 x2 約束條件： s.t. x x1 1 + x+ x2 2 300 (A) 300 (A) 2 x 2 x1 1 + x+ x2 2 400 (B) 400 (B) x x2 2 250 (C) 250 (C) x x1 1 0 (D) 0 (D) x x2 2 0 (E) 0 (E)得到最優(yōu)解：得到最優(yōu)解： x x1 1 = 50= 50， x x2 2 = 250= 2

11、50 最優(yōu)目標值 z = 275002 圖圖 解解 法法 對于只有兩個決策變量的線性規(guī)劃問題，可以在平面直角坐標系上作圖表示線性規(guī)劃問題的有關(guān)概念，并求解。 下面通過例1詳細講解其方法：管理運籌學(xué)管理運籌學(xué)- - 第二章第二章 線形規(guī)劃的圖解法線形規(guī)劃的圖解法27一、 圖 解 法 的 步 驟 (1)分別取決策變量X1 , X2 為坐標向量建立直角坐標系。在直角坐標系里，圖上任意一點的坐標代表了決策變量的一組值，例1的每個約束條件都代表一個半平面。x2x1X20X2=0 x2x1X10X1=0管理運籌學(xué)管理運籌學(xué)- - 第二章第二章 線形規(guī)劃的圖解法線形規(guī)劃的圖解法28（2）對每個不等式(約束條

12、件)，先取其等式在坐標系中作直線，然后確定不等式所決定的半平面。100200300100200300 x1+x2300 x1+x2=3001001002002x1+x24002x1+x2=400300200300400管理運籌學(xué)管理運籌學(xué)- - 第二章第二章 線形規(guī)劃的圖解法線形規(guī)劃的圖解法29（3）把五個圖合并成一個圖，取各約束條件的公共部分，如圖2-1所示。100100 x2250 x2=250200300200300 x1x2x2=0 x1=0 x2=250 x1+x2=3002x1+x2=400圖2-1管理運籌學(xué)管理運籌學(xué)- - 第二章第二章 線形規(guī)劃的圖解法線形規(guī)劃的圖解法30目標函

13、數(shù)等值線的確定（4）目標函數(shù)z=50 x1+100 x2，當z取某一固定值時得到一條直線，直線上的每一點都具有相同的目標函數(shù)值，稱之為“等值線”。平行移動等值線，當移動到B點時，z在可行域內(nèi)實現(xiàn)了最大化。A，B，C，D，E是可行域的頂點，對有限個約束條件則其可行域的頂點也是有限的。最優(yōu)解為50 x1=50， x2= 250 x1x2z=20000=50 x1+100 x2圖2-2z=27500=50 x1+100 x2z=0=50 x1+100 x2z=10000=50 x1+100 x2CBADE管理運籌學(xué)管理運籌學(xué)- - 第二章第二章 線形規(guī)劃的圖解法線形規(guī)劃的圖解法31管理運籌學(xué)管理運籌

14、學(xué)- - 第二章第二章 線形規(guī)劃的圖解法線形規(guī)劃的圖解法32 例7 某公司由于生產(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兩種原料，使得購進成本最低？解：目標函數(shù)： Min f = 2x1 + 3 x2 約束條件：s.t. x1 + x2 350 x1 125 2 x1

15、+ x2 600 x1 , x2 0管理運籌學(xué)管理運籌學(xué)- - 第二章第二章 線形規(guī)劃的圖解法線形規(guī)劃的圖解法33目標函數(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)解。100 200300 400 500 600100200300400600500 x1 =125x1+x2 =3502x1+3x2 =8002x1+3x2 =9002x1+x2 =6002x1+3x2 =1200 x2 Q管理運籌學(xué)管理運籌學(xué)- - 第二章第二章 線形規(guī)劃的圖解法線

16、形規(guī)劃的圖解法34二、線性規(guī)劃的最優(yōu)解的進一步討論管理運籌學(xué)管理運籌學(xué)- - 第二章第二章 線形規(guī)劃的圖解法線形規(guī)劃的圖解法35 管理運籌學(xué)管理運籌學(xué)- - 第二章第二章 線形規(guī)劃的圖解法線形規(guī)劃的圖解法36 管理運籌學(xué)管理運籌學(xué)- - 第二章第二章 線形規(guī)劃的圖解法線形規(guī)劃的圖解法37 管理運籌學(xué)管理運籌學(xué)- - 第二章第二章 線形規(guī)劃的圖解法線形規(guī)劃的圖解法38 （4）無界解。即可行域的范圍延伸到無窮遠，目標函數(shù)值可以無窮大或無窮小。一般來說，這說明模型有錯，忽略了一些必要的約束條件； （5）無可行解。出現(xiàn)這種情況是由于約束條件自相矛盾導(dǎo)致的建模錯誤。管理運籌學(xué)管理運籌學(xué)- - 第二章第二

17、章 線形規(guī)劃的圖解法線形規(guī)劃的圖解法39 對求解一般線性規(guī)劃問題的單純形法的啟發(fā)： （1）求解線性規(guī)劃問題時，解的情況有：唯一最優(yōu)解、無窮多最優(yōu)解、無界解、無可行解。 （2）若線性規(guī)劃問題的可行域存在，則可行域是一個凸集,所謂凸集，要求集合中的任何兩點的連線落在這個集合中； （3）若線性規(guī)劃問題的最優(yōu)解存在，則最優(yōu)解或最優(yōu)解之一（如果有無窮的話，一定能夠在可行域（凸集）的某個頂點找到； （4）為單純形法的解題的思路提供了依據(jù)。管理運籌學(xué)管理運籌學(xué)- - 第二章第二章 線形規(guī)劃的圖解法線形規(guī)劃的圖解法40線性規(guī)劃的標準化內(nèi)容之一：引入松馳變量（含義是資源的剩余量） 例1 中引入 s1， s2，

18、s3 模型化為 目標函數(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則還剩余50千克。約束條件：s.t. x1 + x2 350 x1 125 2 x1 + x2 600 x1 , x2 0 采用圖解

19、法。如下圖：得Q點坐標（250，100）為最優(yōu)解。進 一 步 討 論管理運籌學(xué)管理運籌學(xué)- - 第二章第二章 線形規(guī)劃的圖解法線形規(guī)劃的圖解法41管理運籌學(xué)管理運籌學(xué)- - 第二章第二章 線形規(guī)劃的圖解法線形規(guī)劃的圖解法423 圖解法的靈敏度分析線性規(guī)劃的標準化 一般形式目標函數(shù)：目標函數(shù)： Max Max （MinMin） z = cz = c1 1 x x1 1 + c+ c2 2 x x2 2 + + c+ + cn n x xn n 約束條件：約束條件： s.t. s.t. a a1111 x x1 1 + + a a1212 x x2 2 + + + + a a1n1n x xn n

20、 （ =, =, ）b b1 1 a a2121 x x1 1 + + a a2222 x x2 2 + + + + a a2n2n x xn n （ =, =, ）b b2 2 a am1m1 x x1 1 + + a am2m2 x x2 2 + + + + a amnmn x xn n （ =, =, ）b bm m x x1 1 ，x x2 2 ， ，x xn n 0 0 標準形式標準形式目標函數(shù)：目標函數(shù)：Max z = cMax z = c1 1 x x1 1 + c+ c2 2 x x2 2 + + c+ + cn n x xn n 約束條件約束條件s.t. s.t. a a11

21、11 x x1 1 + + a a1212 x x2 2 + + + + a a1n1n x xn n = b = b1 1 a a2121 x x1 1 + + a a2222 x x2 2 + + + + a a2n2n x xn n = b = b2 2 am1 x1 + am2 x2 + + amn xn = bm x1 ，x2 ， ，xn 0，bi 0管理運籌學(xué)管理運籌學(xué)- - 第二章第二章 線形規(guī)劃的圖解法線形規(guī)劃的圖解法43 靈敏度分析的含義就是指對系統(tǒng)或事物因周圍條件變化顯靈敏度分析的含義就是指對系統(tǒng)或事物因周圍條件變化顯示出來的敏感程度的分析。示出來的敏感程度的分析。 在前面

22、講的線性規(guī)劃問題中，都假定問題中的在前面講的線性規(guī)劃問題中，都假定問題中的c ci i , , a aij ij , , b bj j 是已知常數(shù)。但實際上這些數(shù)字往往是一些估計和預(yù)測的是已知常數(shù)。但實際上這些數(shù)字往往是一些估計和預(yù)測的數(shù)字，如市場條件發(fā)生變化，數(shù)字，如市場條件發(fā)生變化， c ci i 值會變化值會變化, a aij ij 是隨工藝技是隨工藝技術(shù)條件的改變而改變，而術(shù)條件的改變而改變，而 b bj j值則是根據(jù)資源投入后能產(chǎn)生值則是根據(jù)資源投入后能產(chǎn)生多大經(jīng)濟效果來決定的一種決策選擇。多大經(jīng)濟效果來決定的一種決策選擇。 因此就會提出以下因此就會提出以下問題：當這些參數(shù)中的一個或

23、幾個發(fā)生變化時，問題的最問題：當這些參數(shù)中的一個或幾個發(fā)生變化時，問題的最優(yōu)解就會有什么變化，或者這些參數(shù)在一個多大范圍內(nèi)變優(yōu)解就會有什么變化，或者這些參數(shù)在一個多大范圍內(nèi)變化時，問題的最優(yōu)解不變，這就是靈敏度反洗所要研究解化時，問題的最優(yōu)解不變，這就是靈敏度反洗所要研究解決的問題。決的問題。 靈敏度分析：建立數(shù)學(xué)模型和求得最優(yōu)解后，研究線性規(guī)劃的一個或多個參數(shù)（系數(shù)）ci , aij , bj 變化時，對最優(yōu)解產(chǎn)生的影響。管理運籌學(xué)管理運籌學(xué)- - 第二章第二章 線形規(guī)劃的圖解法線形規(guī)劃的圖解法443 圖解法的靈敏度分析一、目標函數(shù)中的系數(shù) ci 的靈敏度分析 考慮例1的情況， ci 的變化

24、只影響目標函數(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)解。一般情況： z = c1 x1 + c2 x2 寫成斜截式 x2 = - (c1 / c2 ) x1 + z / c2 目標函數(shù)等值線的斜率為 - (c1 / c2 ) ， 當 -1 - (c1 / c2 ) 0 （*） 時，原最優(yōu)解仍是最優(yōu)解。x1x2x2=0 x1=0 x2=250 x1+x2=3002x1+x2=400圖2-1管理運

25、籌學(xué)管理運籌學(xué)- - 第二章第二章 線形規(guī)劃的圖解法線形規(guī)劃的圖解法453 圖解法的靈敏度分析假設(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 的交點 x1 = 100，x2 = 200 。管理運籌學(xué)管理運籌學(xué)- - 第二章第二章 線形規(guī)劃的圖解法線形規(guī)劃的圖解法463 圖解法的靈敏度分析x2x2=0 x1=0 x1+x2=3102x1+x2=400圖2-1