1、第二篇 規劃和優化模型第三章 線性規劃學習目的 線性規劃是運籌學的一個重要分支。通過對本章的學習要求：能夠掌握線性規劃問題中的主要概念能夠掌握線性規劃問題中的線性規劃的標準形式能夠掌握線性規劃問題的求解方法圖解法及單純形法理解線性規劃問題解的概念和根本定理了解線性規劃問題的敏感性分析以及善于建立線性規劃模型來解決一些實際問題。第三章 線性規劃3.1 線性規劃問題概述3.2 線性規劃問題的圖解法3.3 單純形法3.4 對偶問題3.5 敏感性分析3.1 線性規劃問題概述3.1.1 線性規劃問題中的主要概念3.1.2 線性規劃問題的數學模型3.1.1 線性規劃問題中的主要概念目標（objective

2、）: 所要到達的最優結果（最大或最小）。約束條件（constraints）：對所能產生結果的限制。線性規劃：一種解決帶有約束條件的最優化問題的方法。解決線性規劃問題的步驟 定義問題和收集數據。建立模型，用恰當的數學式子表示問題求出問題的最優解進行敏感性分析，檢查條件發生變化是會發生的情況。確定潘得羅索工業公司的產品組合潘得羅索工業公司是一家墨西哥公司，截至在1998年的銷售，公司生產了全國膠合板產量的四分之一，與其他膠合板生產廠商一樣，潘得羅索工業公司的許多產品根據厚度和所用木材的質量而有所不同。因為產品在一個競爭的環境中進行銷售，產品的價格由市場決定，所以產品的價格每月都有很大的變化。結果導

3、致每項產品對公司整體利潤的奉獻也有很大的變動。從1980年開始，潘得羅索工業公司管理部門每個月使用線性規劃指導下個月的產品組合決策。線性規劃的數學模型考慮了這一決策的所有相關限制條件，包括生產產品所需的有限的可得數量。然后對模型求解，找出可行并且最大可能利潤（largest possible profit）的產品組合。采用線性規劃后，潘得羅索工業公司的成績是顯著的。改進的產品組合使公司的總利潤增加了20%，線性規劃得其他奉獻包括更好的原材料利用，更好的資本投資，和更好的人員利用。航空業的本錢控制那時，聯行在其11個航班訂票處，有超過4，000名的機場銷售代表和支持人員。在十個最大的機場大約有一

4、千名顧客效勞代表，有些時兼職的，每班2到8個小時不等，大局部是全職的，每班8現實或10小時，有許多個不同的上班時間。每個訂票處都有一天24小時營業（通過電話訂票。然而，每個地點提供所需水平效勞的雇員數量在一天24小時種的變化很大，或許美國半個小時就會有很大的變化。為了更有效率的滿足效勞要求，在每個地點為所有工作人員設計動作排成，是一個組合的夢魘。一旦一名雇員上了班，就會工作一個班次，只有就餐和每個兩個小時的短暫的休息時間，給定24小時的一天中每半個小時各的效勞所需的最小雇員數，在七天一周中，24小時一天中每個班次需要多少雇員并且適宜上班呢？幸運的是，線性規劃能解決這些組合夢魘問題。據有形估計，

5、建立在線性規劃基礎上的計算機規劃系統每年為聯合航空公司在直接薪酬和津貼本錢上節省了600萬美元，得到的其他好處包括改善客戶效勞以及降低雇員的工作負擔。線性規劃問題的數學模型一家玻璃產品生產公司生產帶有把戲圖案的彩色玻璃花瓶。每一個花瓶經過藝術玻璃吹風機從液態加工而成，然后進入儲藏室冷卻至室溫，花瓶有大和小兩種尺寸，但是生產過程幾乎相當，而且使用同一種材料。不管尺寸，每一個花瓶都需要20分鐘的藝術加工，每周藝術加工工作時間為40小時；大小花瓶每個個需彩色玻璃2 OZ和1 OZ。每周可用的玻璃為160 OZ。另外，一個小花瓶占用2單位儲存空間，大花瓶占用3個單位儲存空間，一共有260個單位儲存空間

6、。大小花瓶的利潤奉獻率分別為12元/個和10元/個。問應該怎樣安排生產，才能使利潤值最大。線性規劃問題的數學模型工序花瓶種類占用材料（OZ）藝術加工（小時）儲存空間（一單位）利潤值（元）大花瓶21/3312小花瓶11/3210每周可用能力16040260B表示大花瓶每周生產的數量，S表示小花瓶每周生產的數量。 約束條件2B+S1601/3B+1/3S40 3B+2S260 B0, S0 目標函數：max z =12B+10S 數學模型表述如下目標函數 max z =12B+10S 材料約束 2B+S160 時間約束 1/3B+1/3S40 儲存約束 3B+2S260 非負約束 B0, S0 數

7、學建模四個步驟：決策變量確定目標函數確定約束條件確定非負約束實例分析：A集團有1,000,000元的資金可供投資，該集團有五個可供選擇的投資工程，其中各種資料如下：投資項目風險%紅利%增長%信用度110510112681783187141041262245410710A集團的目標為：投資風險最小，每年紅利至少是80,000元，最低平均增長率14%，最低平均信用度為6，請用線性規劃方法描述該問題。決策變量為個工程的投資數額，設為xi ( i =1,2,3,4,5)目標函數： min z = ( 0.1x1 + 0.06x2 +0.18x3 + 0.12x4+ 0.04x5 )約束條件：各工程投資

8、總和為1,000,000元 x1 + x2 + x3 + x4+ x5 = 1,000,000所得紅利最少為80,000元0.05 x1 + 0.08 x2 + 0.07 x3 + 0.06 x4+ 0.1 x5 80,000增加額不低于140,000元1x1 + 0.17 x2 + 0.14 x3 + 0.22 x4+0.7 x5140,000平均信用度不低于6(11 x1 + 8 x2 + 10 x3 + 4 x4+10 x5)/56非負約束 xi 0 ( i =1,2,3,4,5)實例分析：某石油公司利用三種有生產兩種混合原料。每種油的本錢和每天的可用量如下表所示：油成本（元/升）可用量

9、（升）A810,000B1015,000C1220,000燃料1A：最多占25%B：最少占30%C：最多占40%燃料2A：最少占20%B：最多占50%C：最少占30%燃料1售價為30元/升，燃料2 售價為35元/升，該公司有一向長期合同，每天供給兩種原料，各10，000升。請建立該問題的數學規劃模型。 解題過程：決策變量為參加到兩種燃料種的各種油的量：A1為原料1中參加A種油的升數。A2為原料2中參加A種油的升數。B1為燃料1中參加B種油的升數。B2為燃料2中參加B種油的升數。C1為燃料1中參加C種油的升數。C2為燃料2中參加C種油的升數。燃料1和燃料2 的產量為：燃料1：A1+B1+C1燃料

10、2：A2+B2+C2各種油的使用量：A種油= A1+A2B種油= B1+ B2C種油= C1+ C2 目標是取得最大化的利潤，兩種燃料的銷售收入為：30(A1+ B1+ C1)+35(A2+ B2+ C2)而三種油的本錢為：8(A1+A2)+10(B1+ B2)+12(C1+ C2 )利潤是銷售收入和本錢之差，作為目標函數可以表示如下：max z =22A1+27 A2 +20 B1+25B2+18 C1+23 C2三種可用的原料油的約束為：A1+A210,000B1+ B215,000C1+ C220,000各種原料油所占比例的六個約束：A10.25(A1+B1+C1)B10.3(A1+B1

11、+C1)C10.4(A1+B1+C1)A20.2(A2+B2+C2)B20.5(A2+B2+C2)C20.3(A2+B2+C2)長期供貨合同約束：A1+B1+C110,000A2+B2+C210,000非負約束：Ai，Bi，Ci0 (i=1,2)第三章 線性規劃3.1 線性規劃問題概述3.2 線性規劃問題的圖解法3.3 單純形法3.4 對偶問題3.5 敏感性分析3.2線性規劃問題的圖解法3.2.1 圖解法的過程介紹3.2.2 規劃問題求解的幾種可能結果3.2.3 圖解法延伸3.2.1 圖解法的過程介紹花瓶問題目標函數 max z =12B+10S 材料約束 2B+S160 （1）時間約束 1/

12、3B+1/3S40 （2）儲存約束 3B+2S260 （3）非負約束 B0, S0 直線把圖分為兩局部，直線上方的點都不符合約束條件，而直線上和直線下方的點都滿足約束條件。 最優解為：B=20, S=100 將B和S值代入目標函數中得：Z=1220+10100=1240 所以最大利潤值是1240。 圖解法的步驟：其中一個變量作為橫坐標軸，另一個變量作為縱坐標軸，畫出平面直角坐標系，并適中選取單位坐標長度，由于變量是非負的，因此，畫出坐標系的第一象限即可。出各約束條件在坐標軸上對應的直線，找出可行域（常用陰影區域標識）。圖標目標函數，z是一個待求的目標函數值。目標函數常用一組平行虛線表示，離坐標

13、原點越遠的虛線表示的目標函數值越大。確定最優解。因為最優解是可行域中使目標函數值到達最優的點，當目標函數直線由原點開始向右上方移動時，z值開始增大，一直移到目標函數直線與可行域相切時為止，切點就是最優解的點。3.2.2規劃問題求解的幾種可能結果無窮多最優解無界解無解或者無可行解3.2.3圖解法延伸圖解法的解體方法和幾何判斷對于求解一般的線性規劃問題有很大啟發：1、性規劃問題的解的情況有以下幾種：唯一最優解；無窮多最優解；無界解；無可行解。2、線性規劃問題有解，那么可行域是凸集。3、規劃問題優解存在，那么唯一最優解一定是可行域凸集的某個頂點；無窮最優解一定是可行域的某個邊或某個面。4、規劃問題的

14、一般解體思路：先找出凸集的任一頂點，計算該點處目標函數值，與周圍相鄰頂點處的目標函數值相比較，如果該點值最大，那么該點就是最優解或者最優解之一；如果不是，那么就對目標函數值比該點大的另一點重復此過程，直到找出最優解。實例分析：某工廠生產A,B兩種產品，分別經過三道工序，建立的模型如下所示，可行域為凸多邊形OACDB, 試以圖解法求解最優生產方案。目標函數 max z =20A+30B 工序一約束 2A+B40 工序二約束 A+2B40 工序三約束 A+B25 非負約束 A0, B0 A+2B=40 工序二約束A+B=25 工序三約束聯立以上方程，可以求得最優解A=10, B=15代入目標函數，

15、求得最大目標函數值為20*10+30*15=650。第三章 線性規劃3.1 線性規劃問題概述3.2 線性規劃問題的圖解法3.3 單純形法3.4 對偶問題3.5 敏感性分析3.3 單純形法3.3.1 線性規劃問題的標準形式3.3.2 線性規劃問題解的概念和根本定理3.3.3 單純形法解題步驟3.3.1線性規劃問題的標準形式規定線性規劃問題的一般形式：目標函數約束條件 （i =1,m）非負約束 0 ( j =1,n) 轉化為標準形式方法：如果模型的目標函數為極小值： ，那么令z=-z , 。如果右端項bi小于零，等式兩端同時乘以-1 。約束條件一般情況下是不等式。例如：x1+x26, 令x3=6-

16、x1-x2 ，x3 0，將約束條件轉化為x1+x2+x3=6 ，x3稱作松弛變量。如果有x1+x26 ,令x4=6-x1-x2 , x40，約束條件轉化為x1+x2-x4=6，x4稱作剩余變量。變量取值可能無約束。決策變量可以大于或等于零，也可以小于零。此時令xj=xj-xj, xj0, xj0, 將其代入線性規劃模型。決策變量小于等于零, 即xj0。令xj=-xj , 將xj代入線性規劃模型。3.3.2線性規劃問題解的概念和根本定理目標函數約束條件 （i =1,m） 非負約束 xj 0 ( j =1,n) 可行解：滿足約束條件的解為可行解，全部可行解的集合為可行域。最優解：使目標函數值到達最

17、大的可行解為最優解。定理一 ： 若線性規劃問題存在可行解，則問題的可行域為凸集。定理二 ： 線性規劃問題的基可行解對應于線性規劃問題可行域的頂點。定理三 ：若線性規劃問題有最優解，一定存在一個基可行解是最優解。3.3.3單純形法解題步驟模型如下：目標函數 max z =20A+30B 工序一約束 2A+B40 工序二約束 A+2B40 工序三約束 A+B25 非負約束 A0, B0 ，引入三個松弛變量：C、D、E原問題轉變為如下形式：max z =20A+30B+0C+0D+0E 2A+B+C=40 A+2B+D=40 A+B+E=25 A0, B0,C0,D0,E0 約束條件的系數矩陣為：U

18、=(P1 ,P2 ,P3 ,P4 ,P5) =P3= ，P4= ，P5= 三個向量是線性無關的這些向量構成基矩陣：V=(P3, P4, P5 ) =對應于V的變量為基變量，他們分別為：C=40-2A-BD=40-A-2BE=25-A-B將上述基變量代入目標函數中，得到：Z=20A+30B+0 當還未生產時，A=B=0，資源未被利用。取C=40 ,D=40 ,E=25，利潤值還未產生， 得到初始根本可行解：X(0) =(0，0，40，40，25)。B的取值滿足： C=40-2A-B0 D=40-A-2B0 E=25-A-B0因為A=0,所以有： C=40-B0 D=40-2B0 E=25-B0B

19、的取值要求滿足上述三式，因此B為:B=min 40/1 ,40/2 ,25/1 =20現在知道，A=0 ,B=20 ,將其代入三個約束條件中，2A+B+C=40A+2B+D=40A+B+E=25得到一組新的解：X(1)=(0，20，20，0，5)將上面三式變形，得到下式：C+B=40-3/2A (1)2B=40-A-D (2)E+B=25-A (3)將其進行轉化，(1)-1/2*(2)，(2)/2，(3)-(2)/2，上述三式又變為：C=20-3/2A (4)B=20-1/2A-1/2D (5)E=5-1/2A+1/2D (6)將上述三式代入目標函數式中，Z=600+5A-15D V=(C,

20、B, E) = 根據(4)、(5)、(6)式可以得到新的約束方程的系數矩陣：U= 從目標表達式Z=600+5A-15D上看，A的系數式正值，說明增加A的產量仍然可以提高利潤，A的取值滿足： C=20-3/2A0 B=20-1/2A-1/2D0 E=5-1/2A+1/2D0由于D=0，可得： C=20-3/2A0 B=20-1/2A0 E=5-1/2A0A要求滿足上述三式，因此A=min 20/1.5, 20/0.5, 5/0.5=10A變為基變量，而E變為非基變量，將A=10, E=0代入三個約束條件中：2A+B+C=40A+2B+D=40A+B+E=25通過求解可得：B=15, C=5, D

21、=0新的根本可行解為：X(2)=(10，15，5，0，0)。用A置換E，得到：C+3/2A=20B+1/2A=20-1/2D1/2A=5+1/2D-E經變形得到下面三個新的式子： C=5-3/2D+3E B=15-D+E A=10+D-2E將上述三式帶入目標函數Z=650-10D-10E 從上式可以看出，D、E系數皆為負，如果這些變量值增加，將導致目標函數值的減少。因此最正確生產方案為：X(2)=(10，15，5，0，0)最大利潤值為：Z=650例 Keku公司一直開始從事汽車零配件的設計、生產，最近公司設計了兩種新型改進產品(產品I和II)。根據以往新產品上市的經驗和市場行情，Keku公司預

22、計每生產一件產品I可獲利2元，每生產一件產品II可獲利3元。公司準備利用現有的生產資源，在方案期內安排生產I、II兩種新產品，生產單位產品所需的設備臺時及A、B兩種原材料的消耗，如下表所示。 站在Keku公司的立場想知道如何安排生產才能獲利最多？用單純形法對它進行求解。分別設 、 表示在方案期內產品I、II的產量，建立該問題的數學模型為： 將其轉換為標準型為： （4） （5）確定初始可行基和基可行解由式（5）可得 ， 和 對應的系數列向量線性無關，因此，取可行基：則 ， 和 為基變量， ， 為非基變量。將基變量和目標函數用非基變量表示為： （6） （7）當非基變量 ， 時，得到基可行解 ，此時

23、， ，即Keku公司未生產任何產品，其利潤為0。確定換入變量在目標函數式（6）中，非基變量 ， 的系數都是正數，因此，不管以誰作為換入變量都能使目標函數值增大，其經濟意義為安排生產任一種產品都可以增加Keku公司的利潤。我們選擇系數較大的 作為換入變量。確定換出變量選擇 作為換入變量后，必須從 ， 和 中確定一個換出變量。解 （令 ），得到 解 （令 ），得到 為保證所有變量的非負性，故 ，此時， 為換出變量。這種確定換出變量的規則稱為 規則。重復上述過程，可得最優解結論：Keku公司應生產4件產品I和2件產品II，共可獲得利潤14元。第三章 線性規劃3.1 線性規劃問題概述3.2 線性規劃問

24、題的圖解法3.3 單純形法3.4 對偶問題3.5 敏感性分析3.4 對偶問題3.4.1 原問題與對偶問題的關系3.4.2 舉例說明3.4.1 原問題與對偶問題的關系求原問題的對偶問題的步驟：（1）如約束條件中有“ 的情況，將其轉換成“ ，使得所有約束條件全部變成“ 或“=的形式。（2）如果原問題的目標函數是“ 的形式，則對偶問題的目標函數是“ 的形式。原問題的 n個變量對應于對偶問題中 n個約束條件。具體地，若變量 的取值“ 0，則對偶問題中第 i個約束條件為“ 的不等式；若變量 的取值“ 0，則對偶問題中第 個約束條件為“ 的不等式；若變量 無約束，則對偶問題中第i 個約束條件為等式。原問題的 m個約束條件對應于對偶問題中 m個變量。具體來講，若第i 個約束條件是“ 的不等式，則變量 的取值“ 0；若第i 個約束條件為等式，則變量 無約束。（