《管理運籌學 _線性規(guī)劃課件》由會員分享，可在線閱讀，更多相關《管理運籌學 _線性規(guī)劃課件（64頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、管理運籌學 _線性規(guī)劃天津大學管理學院天津大學管理學院郭均鵬郭均鵬管理運籌學 _線性規(guī)劃教師簡介：教師簡介：郭均鵬：博士，副教授，郭均鵬：博士，副教授， 碩士生導師。碩士生導師。主要研究領域：主要研究領域： 運籌決策技術；運籌決策技術；信息管理與企業(yè)信息化；信息管理與企業(yè)信息化；績效考核與薪酬體系設計績效考核與薪酬體系設計 聯(lián)系方式：天津大學管理學院，聯(lián)系方式：天津大學管理學院，300072 ； 管理運籌學 _線性規(guī)劃課程教材：課程教材：吳育華吳育華,杜綱杜綱. 管理科學基礎管理科學基礎，天津大學出版社。，天津大學出版社。管理運籌學 _線性規(guī)劃緒緒 論論運籌學（運籌學（Operational

2、Research) 直譯為直譯為“運作研究運作研究”。 產(chǎn)生于二戰(zhàn)時期產(chǎn)生于二戰(zhàn)時期 60年代，在工業(yè)、農(nóng)業(yè)、社會等各領域得到廣泛應用年代，在工業(yè)、農(nóng)業(yè)、社會等各領域得到廣泛應用 在我國，在我國，50年代中期由錢學森等引入年代中期由錢學森等引入 運用數(shù)學方法，為決策者進行最優(yōu)決策提供科學依據(jù)運用數(shù)學方法，為決策者進行最優(yōu)決策提供科學依據(jù)的一門的一門應用科學應用科學。一、運籌學的產(chǎn)生與發(fā)展一、運籌學的產(chǎn)生與發(fā)展二、運籌學的性質二、運籌學的性質管理運籌學 _線性規(guī)劃三、運籌學的分支三、運籌學的分支線性規(guī)劃線性規(guī)劃非線性規(guī)劃非線性規(guī)劃圖論與網(wǎng)絡分析圖論與網(wǎng)絡分析存儲論存儲論決策論決策論動態(tài)規(guī)劃動態(tài)規(guī)

3、劃排隊論排隊論管理運籌學 _線性規(guī)劃四、四、運籌學在管理中的應用運籌學在管理中的應用生產(chǎn)計劃：生產(chǎn)計劃：生產(chǎn)作業(yè)的計劃、日程表的編排、合理生產(chǎn)作業(yè)的計劃、日程表的編排、合理下料等，追求利潤最大化和成本最小化下料等，追求利潤最大化和成本最小化庫存管理庫存管理運輸問題：運輸問題：確定最小成本的運輸線路、物資的調撥確定最小成本的運輸線路、物資的調撥以及建廠地址的選擇等以及建廠地址的選擇等人力資源管理：人力資源管理：對人員的需求和使用的預測，確定對人員的需求和使用的預測，確定人員編制、人員編制、 人員合理分配，建立人才評價體系等人員合理分配，建立人才評價體系等工程網(wǎng)絡計劃：工程網(wǎng)絡計劃：確定工期、關鍵

4、工序等確定工期、關鍵工序等管理運籌學 _線性規(guī)劃明確問題明確問題問題分類問題分類建立數(shù)學模型建立數(shù)學模型求解數(shù)學模型求解數(shù)學模型結果分析結果分析實施實施五、五、運用運籌學方法解決實際問題的工作流程運用運籌學方法解決實際問題的工作流程 注意計算機軟件的應用 Lindo、Exel等管理運籌學 _線性規(guī)劃第一章第一章 線性規(guī)劃線性規(guī)劃（Linear Programming，簡稱，簡稱LP）1 1 線性規(guī)劃的模型與圖解法線性規(guī)劃的模型與圖解法2 2 線性規(guī)劃的舉例與軟件求解線性規(guī)劃的舉例與軟件求解3 3 整數(shù)規(guī)劃整數(shù)規(guī)劃4 4 運輸問題運輸問題管理運籌學 _線性規(guī)劃第一章第一章 線性規(guī)劃線性規(guī)劃（Li

5、near Programming，簡稱，簡稱LP）1 線性規(guī)劃的模型與圖解法線性規(guī)劃的模型與圖解法一、一、LP問題及其數(shù)學模型問題及其數(shù)學模型二、線性規(guī)劃的標準型二、線性規(guī)劃的標準型三、線性規(guī)劃的圖解法三、線性規(guī)劃的圖解法管理運籌學 _線性規(guī)劃一、一、LP問題及其數(shù)學模型問題及其數(shù)學模型例例1 某工廠可生產(chǎn)甲、乙兩種產(chǎn)品，需消耗煤、某工廠可生產(chǎn)甲、乙兩種產(chǎn)品，需消耗煤、電、油三種資源，有關單耗數(shù)據(jù)如表，試擬定電、油三種資源，有關單耗數(shù)據(jù)如表，試擬定使總收入最大的生產(chǎn)計劃。使總收入最大的生產(chǎn)計劃。127單價單價300103油油20054電電36049煤煤資源限制資源限制乙乙甲甲產(chǎn)品產(chǎn)品資源資源管

6、理運籌學 _線性規(guī)劃甲甲乙乙資源限制資源限制煤煤94360電電45200油油310300單價單價712產(chǎn)品產(chǎn)品資源資源線性規(guī)劃模型三要素：線性規(guī)劃模型三要素：（1）決策變量）決策變量 設甲產(chǎn)品生產(chǎn)設甲產(chǎn)品生產(chǎn)x1，乙產(chǎn)品生產(chǎn)，乙產(chǎn)品生產(chǎn)x2（2）目標函數(shù)）目標函數(shù) Max Z=7 x1 +12x2（3）約束條件）約束條件9 x1 +4x23604x1 +5x2 2003 x1 +10 x2 300 x1 , x20s.t.返回Subject To， 意為意為“使其滿使其滿足足”管理運籌學 _線性規(guī)劃目標函數(shù)： Max （Min） Z = c1 x1 + c2 x2 + + cn xn a11

7、x1 + a12 x2 + + a1n xn （ =, ）b1a21 x1 + a22 x2 + + a2n xn （ =, ）b2 am1 x1 + am2 x2 + + amn xn （ =, ）bmx1 ，x2 ， ，xn 0約束條件：s.t. LP模型的一般形式模型的一般形式管理運籌學 _線性規(guī)劃課堂練習課堂練習 某蓄場每日要為每頭牲畜購買飼料，以使其某蓄場每日要為每頭牲畜購買飼料，以使其獲取所需的獲取所需的A、B、C、D四種養(yǎng)分。有關數(shù)據(jù)四種養(yǎng)分。有關數(shù)據(jù)如下表，現(xiàn)飼料可從市場上出售的如下表，現(xiàn)飼料可從市場上出售的M、N兩種飼兩種飼料中選擇，試決定總花費最小的購買方案。料中選擇，試決

8、定總花費最小的購買方案。（列出模型）（列出模型）ABCD價格價格M0.50.20.30300N0.10.30.40.2200每頭每頭日需日需10587養(yǎng)分養(yǎng)分飼料飼料管理運籌學 _線性規(guī)劃課堂練習課堂練習 某蓄場每日要為每頭牲畜購買飼料，以使其獲取所需的某蓄場每日要為每頭牲畜購買飼料，以使其獲取所需的A、B、C、D四四種養(yǎng)分。有關數(shù)據(jù)如下表，現(xiàn)飼料可從市場上出售的種養(yǎng)分。有關數(shù)據(jù)如下表，現(xiàn)飼料可從市場上出售的M、N兩種飼料中選兩種飼料中選擇，試決定總花費最小的購買方案。（列出模型）擇，試決定總花費最小的購買方案。（列出模型）ABCD價格價格M0.50.20.30300N0.10.30.40.2

9、200每頭日需每頭日需10587養(yǎng)分養(yǎng)分飼料飼料答案：答案：設購買設購買M飼料飼料x1，N飼料飼料x20.5 x1 +0.1x2100.2x1 +0.3x2 50.3x1 +0.4x2 8 0.2x2 7x1 , x20s.t.Min Z=300 x1 +200 x2管理運籌學 _線性規(guī)劃二、線性規(guī)劃的標準型二、線性規(guī)劃的標準型Max Z = c1 x1 + c2 x2 + + cn xn a11 x1 + a12 x2 + + a1n xn =b1a21 x1 + a22 x2 + + a2n xn =b2 am1 x1 + am2 x2 + + amn xn =bmx1 ，x2 ， ，xn

10、 0s.t.1、標準形式、標準形式矩陣表示矩陣表示Max Z = CXAX=bX 0s.t.其中：其中：C=(c1,c2, , cn) 稱為稱為價格系數(shù)價格系數(shù) A=(aij)mn 稱為稱為技術系數(shù)技術系數(shù) b= (b1,b2, , bm) 稱為稱為資源系數(shù)資源系數(shù)管理運籌學 _線性規(guī)劃2、非標準型、非標準型標準型標準型（1）Min Z = CXMax Z = -CX（2）約束條件）約束條件例如：例如： 9 x1 +4x23609 x1 +4x2+ x3=360松弛變量松弛變量 “”型約束，加松弛變量；型約束，加松弛變量； “”型約束，減松弛變量；型約束，減松弛變量；管理運籌學 _線性規(guī)劃例、

11、將如下問題化為標準型例、將如下問題化為標準型 0,52327.32321321321321321xxxxxxxxxxxxtsxxxzMin解解：令：令第二個約束減松弛變量第二個約束減松弛變量x6，得標準型：得標準型：)(zzzMaxzMin 0,52327.3232132153214321321xxxxxxxxxxxxxxtsxxxzMax，第一個約束加松弛變量，第一個約束加松弛變量x5 5，管理運籌學 _線性規(guī)劃三、線性規(guī)劃的圖解法三、線性規(guī)劃的圖解法1. 步驟步驟（1）作約束的圖形）作約束的圖形可行域可行域可行解的集合可行解的集合先作非負約束先作非負約束再作資源約束再作資源約束9x1+4x

12、2=3604x1+5x2=2003x1+10 x2=300公共部分，即為可行域公共部分，即為可行域例：煤電油例例：煤電油例Max Z=7 x1 +12x29 x1 +4x23604x1 +5x2 2003 x1 +10 x2 300 x1 , x20s.t.x1x240206080100204060801000管理運籌學 _線性規(guī)劃（2）作目標函數(shù)的等值線）作目標函數(shù)的等值線給給z不同的值，作相應直線，判斷出不同的值，作相應直線，判斷出z增大時，直線的移動方向增大時，直線的移動方向將直線向增大方向移動，直至可行域將直線向增大方向移動，直至可行域邊界，交點邊界，交點X*即為最優(yōu)解。即為最優(yōu)解。7

13、x1+12x2=847x1+12x2=168如：令如：令7 x1 +12x2=84 7 x1 +12x2=1689x1+4x2=3604x1+5x2=2003x1+10 x2=300 x1x240206080100204060801000X*=（20，24），），Z*=428管理運籌學 _線性規(guī)劃最優(yōu)解：最優(yōu)解： x1 = 0， x2 = 1 最優(yōu)目標值最優(yōu)目標值 z = 6課堂練習課堂練習圖解法求解線性規(guī)劃圖解法求解線性規(guī)劃 0,)3(22)2(22)1(432min2121212121xxxxxxxxstxxz0 01 12 23 34 41 12 23 34 4x1x2O O-1-1-2

14、-2(1)(2)(3)管理運籌學 _線性規(guī)劃2. LP 解的幾種情況解的幾種情況（1）唯一解）唯一解（2）多重最優(yōu)解）多重最優(yōu)解（3）無可行解）無可行解注：出現(xiàn)（注：出現(xiàn)（3）、（）、（4）情況時，建模有問題）情況時，建模有問題（4）無有限最優(yōu)解）無有限最優(yōu)解管理運籌學 _線性規(guī)劃圖解法的結論：圖解法的結論：線性規(guī)劃的可行域是凸集線性規(guī)劃的可行域是凸集 線性規(guī)劃的最優(yōu)解若存在，必在可行域的在極點獲得線性規(guī)劃的最優(yōu)解若存在，必在可行域的在極點獲得 若在兩個極點同時獲得，則有無窮多最優(yōu)解若在兩個極點同時獲得，則有無窮多最優(yōu)解凸集凸集不是凸集不是凸集極極點點管理運籌學 _線性規(guī)劃2 2 線性規(guī)劃應用

15、舉例與軟件求解線性規(guī)劃應用舉例與軟件求解 例例1 1 （下料問題）下料問題） 某工廠要做某工廠要做100100套鋼架，每套用長為套鋼架，每套用長為2.9 m,2.1 2.9 m,2.1 m,1.5 mm,1.5 m的圓鋼各一根。已知原料每的圓鋼各一根。已知原料每根長根長7.4 m7.4 m，問：應如何下料，可使，問：應如何下料，可使所用原料最??？所用原料最省？管理運籌學 _線性規(guī)劃 例例1 1 （下料問題）下料問題） 某工廠要做某工廠要做100100套鋼架，每套用套鋼架，每套用長為長為2.9 m,2.1 m,1.5 m2.9 m,2.1 m,1.5 m的圓鋼各一根。已知原料每的圓鋼各一根。已知

16、原料每根長根長7.4 m7.4 m，問：應如何下料，可使所用原料最?。?，問：應如何下料，可使所用原料最?。糠桨?.92.11.5余料7.4 m7.4 m2.9m2.9m2.1m2.1m1.5 m1.5 m2010.11200.31110.910300301.10220.20130.80041.4管理運籌學 _線性規(guī)劃505010103030 2x 2x1 1 + x + x2 2 + x+ x3 3 + x + x4 4 = 100 = 100 2x 2x2 2 + x+ x3 3 + 3x + 3x5 5 + 2x+ 2x6 6 + x+ x7 7 = 100 = 100 x x1 1 +

17、x + x3 3+ 3x+ 3x4 4 + 2x + 2x6 6 + 3x + 3x7 7 + 4x + 4x8 8 = 100 = 100 x x1 1, x, x2 2, x, x3 3, x, x4 4, x, x5 5, x, x6 6, x, x7 7, x, x8 8 0 0設設 x x1 1,x,x2 2,x,x3 3,x,x4 4,x,x5 5,x,x6 6,x,x7 7,x,x8 8 分別為上述分別為上述8 8種方案下料的原材料根數(shù)，種方案下料的原材料根數(shù)，建立如下的建立如下的LPLP模型：模型：最優(yōu)解為：最優(yōu)解為： x x1 1=10,x=10,x2 2=50,x=50,x

18、3 3=0,x=0,x4 4=30,x=30,x5 5=0,x=0,x6 6=0,x=0,x7 7=0,x=0,x8 8=0=0min Z =xmin Z =x1 1 + x + x2 2 + x + x3 3 + x + x4 4 + x + x5 5 + x + x6 6 + x+ x7 7 + x + x8 8s.t.余料1.52.12.9方案2010.11200.31110.910300301.10220.20130.80041.4管理運籌學 _線性規(guī)劃線性規(guī)劃求解軟件lindo管理運籌學 _線性規(guī)劃3 3 整數(shù)規(guī)劃整數(shù)規(guī)劃Integer Programming(Integer Pro

19、gramming(簡稱簡稱IP)IP)一、整數(shù)規(guī)劃的一般模型一、整數(shù)規(guī)劃的一般模型LP: max z=CX AX=b X0IP: max z=CX AX=b X0 X為整數(shù)管理運籌學 _線性規(guī)劃整數(shù)規(guī)劃的解法：分枝定界法或割平面法整數(shù)規(guī)劃的解法：分枝定界法或割平面法 基本思想是把一個整數(shù)規(guī)劃問題化為一基本思想是把一個整數(shù)規(guī)劃問題化為一系列的線性規(guī)劃問題來求解系列的線性規(guī)劃問題來求解整數(shù)規(guī)劃的分類：整數(shù)規(guī)劃的分類： 純整數(shù)規(guī)劃：所有變量都限制為整數(shù)純整數(shù)規(guī)劃：所有變量都限制為整數(shù) 混合整數(shù)規(guī)劃：僅部分變量限制為整數(shù)混合整數(shù)規(guī)劃：僅部分變量限制為整數(shù) 0-10-1整數(shù)規(guī)劃：變量的取值僅限于整數(shù)規(guī)劃

20、：變量的取值僅限于0 0或或1 1管理運籌學 _線性規(guī)劃 例例 人力資源分配的問題人力資源分配的問題 某晝夜服務的公交線路每天各時間段內(nèi)所需司機和乘某晝夜服務的公交線路每天各時間段內(nèi)所需司機和乘務人員數(shù)如下：務人員數(shù)如下： 設司機和乘務人員分別在各時間段一開始時上班，并連續(xù)工設司機和乘務人員分別在各時間段一開始時上班，并連續(xù)工作八小時，問該公交線路怎樣安排司機和乘務人員，既能滿作八小時，問該公交線路怎樣安排司機和乘務人員，既能滿足工作需要，又配備最少司機和乘務人員足工作需要，又配備最少司機和乘務人員? ?班次班次時間時間所需人數(shù)所需人數(shù)16 6：00 1000 10：00006021010：0

21、0 1400 14：00007031414：00 1800 18：00006041818：00 2200 22：00005052222：00 200 2：00002062 2：00 600 6：000030管理運籌學 _線性規(guī)劃 解：設解：設 x xi i 表示第表示第i i班次時開始上班的司機和乘務人班次時開始上班的司機和乘務人員數(shù)員數(shù), ,于是于是LPLP模型為模型為: : x x1 1 + x + x6 6 60 60 x x1 1 + x + x2 2 70 70 x x2 2 + x + x3 3 60 60 x x3 3 + x + x4 4 50 50 x x4 4 + x +

22、x5 5 20 20 x x5 5 + x + x6 6 30 30 x x1 1,x,x2 2,x,x3 3,x,x4 4,x,x5 5,x,x6 6 0 0且為整數(shù)且為整數(shù)min z=xmin z=x1 1 + x + x2 2 + x + x3 3 + x + x4 4 + x + x5 5 + x + x6 6 班班 次次 時時 間間 所所 需需 人人 數(shù)數(shù) 1 6： 00 10： 00 60 2 10： 00 14： 00 70 3 14： 00 18： 00 60 4 18： 00 22： 00 50 5 22： 00 2： 00 20 6 2： 00 6： 00 30 最優(yōu)解：最

23、優(yōu)解：X* =(60 ，10，50 ，0 ，30 ，0），）， Z*=150管理運籌學 _線性規(guī)劃二、二、 0-10-1整數(shù)規(guī)劃整數(shù)規(guī)劃 投資場所的選址問題投資場所的選址問題 指派問題指派問題 背包問題背包問題 消防隊問題消防隊問題管理運籌學 _線性規(guī)劃1. 投資場所的選址問題投資場所的選址問題 某城市擬在東、西、南三區(qū)設立商業(yè)網(wǎng)點，備選位置有某城市擬在東、西、南三區(qū)設立商業(yè)網(wǎng)點，備選位置有A1A7共共7個，如果選個，如果選Ai，估計投資為，估計投資為bi元，利潤為元，利潤為ci元，要元，要求總投資不超過求總投資不超過B元，規(guī)定元，規(guī)定 東區(qū)：東區(qū)：A1、A2、A3中至多選中至多選2個個 西區(qū)

24、：西區(qū)：A4、A5中至少選一個中至少選一個 南區(qū)：南區(qū)：A6、A7中至少選一個中至少選一個問如何設點使總利潤最大？問如何設點使總利潤最大？ 1， Ai被選中被選中 0， Ai沒被選中沒被選中 解：令解：令 xi=max z= 71iiixcxi=0或或 1，i=1, ,7 bixiBi=17x1+x2+x32x4+x51x6+x71s.t.管理運籌學 _線性規(guī)劃課堂練習課堂練習1: 某鉆井隊要從某鉆井隊要從S1S10共共10個井位中確定五個鉆個井位中確定五個鉆井探油，如果選井探油，如果選Si，估計鉆探費用為，估計鉆探費用為ci元，并且元，并且井位選擇上要滿足下列條件：井位選擇上要滿足下列條件：

25、 （1）或選擇或選擇S1和和S7，或選擇，或選擇S8 ; （2）選擇了選擇了S3或或S4就不能選擇就不能選擇S5，反，反 過來也一樣過來也一樣;（3）在在S5，S6 ，S7，S8中最多只能選中最多只能選兩個。兩個。問如何選擇井位使總費用最?。繂柸绾芜x擇井位使總費用最?。?管理運籌學 _線性規(guī)劃課堂練習課堂練習1: 某鉆井隊要從某鉆井隊要從S1S10共共10個井位中確定五個鉆井探油，個井位中確定五個鉆井探油，如果選如果選Si，估計鉆探費用為，估計鉆探費用為ci元，并且井位選擇上要滿足下列條件：元，并且井位選擇上要滿足下列條件： （1）或選擇）或選擇S1和和S7，或選擇，或選擇S8 （2）選擇了）

26、選擇了S3或或S4就不能選擇就不能選擇S5，反過來也一樣，反過來也一樣 （3）在）在S5，S6 ，S7，S8中最多只能選兩個中最多只能選兩個問如何選擇井位使總費用最?。繂柸绾芜x擇井位使總費用最?。?1， Si被選中被選中 0， Si沒被選中沒被選中 解：令解：令 xi=min z= 101iiixcs.t. 5101iix 181 xx187 xx153 xx154 xx28765xxxx或 1，i=1, ,10 0ix管理運籌學 _線性規(guī)劃 某籃球隊有某籃球隊有8名隊員，其身高和專長如下表，現(xiàn)要選名隊員，其身高和專長如下表，現(xiàn)要選拔拔5名球員上場參賽，要求：名球員上場參賽，要求：（1）中鋒只

27、有）中鋒只有1人上場人上場（2）后衛(wèi)至少有一人上場）后衛(wèi)至少有一人上場（3）只有）只有2號上場，號上場，6號才上場號才上場要求平均身高最高，應如何選拔隊員？要求平均身高最高，應如何選拔隊員？隊隊員員 1 2 3 4 5 6 7 8 身身高高 1.92 1.90 1.88 1.86 1.85 1.83 1.80 1.78 專專長長 中中鋒鋒 中中鋒鋒 前前鋒鋒 前前鋒鋒 前前鋒鋒 后后衛(wèi)衛(wèi) 后后衛(wèi)衛(wèi) 后后衛(wèi)衛(wèi) 課堂練習課堂練習2:管理運籌學 _線性規(guī)劃1， 隊員隊員i被選中被選中 0，隊員，隊員i沒被選中沒被選中 解：令解：令 xi=max z= 8151iiixc 581iix 121 xx1

28、876xxx 26xx 或 1，i=1, ,8 0ixs.t. 某籃球隊有某籃球隊有8名隊員，其身高和專長如下表，現(xiàn)要選名隊員，其身高和專長如下表，現(xiàn)要選拔拔5名球員上場參賽，要求：名球員上場參賽，要求：（1）中鋒只有）中鋒只有1人上場人上場（2）后衛(wèi)至少有一人上場）后衛(wèi)至少有一人上場（3）只有）只有2號上場，號上場，6號才上場號才上場要求平均身高最高，應如何選拔隊員？要求平均身高最高，應如何選拔隊員？管理運籌學 _線性規(guī)劃2. 指派問題指派問題 例：例： 有一份中文說明書，需譯成英、日、德、俄四種文字，有一份中文說明書，需譯成英、日、德、俄四種文字，分別記作任務分別記作任務E、J、G、R，現(xiàn)

29、有甲、乙、丙、丁四人，他們，現(xiàn)有甲、乙、丙、丁四人，他們將中文說明書翻譯成不同語種說明書所需的時間如下表所示，將中文說明書翻譯成不同語種說明書所需的時間如下表所示，問應指派何人去完成何項任務，使所需總時間最少？問應指派何人去完成何項任務，使所需總時間最少？ E J G R 甲甲 2 15 13 4 乙乙 10 4 14 15 丙丙 9 14 16 13 丁丁 7 8 11 9 問題描述：問題描述：n項任務可由項任務可由n個人完成，由于專長不同，各人個人完成，由于專長不同，各人完成各任務的時間也不同，求最優(yōu)安排。完成各任務的時間也不同，求最優(yōu)安排。要求：要求：每人只能完成一項任務，每項任務只能由

30、一人完成。每人只能完成一項任務，每項任務只能由一人完成。管理運籌學 _線性規(guī)劃 x x1111+ + x x1212+ + x x1313+ + x x1414= 1 (= 1 (甲只能干一項工作甲只能干一項工作) ) x x2121+ + x x2222+ + x x2323+ + x x2424= 1 (= 1 (乙只能干一項工作乙只能干一項工作) ) x x3131+ + x x3232+ + x x3333+ + x x3434= 1 (= 1 (丙只能干一項工作丙只能干一項工作) ) x x4141+ + x x4242+ + x x4343+ + x x4444= 1 (= 1 (

31、丁只能干一項工作丁只能干一項工作) ) x x1111+ + x x2121+ + x x3131+ + x x4141= 1 ( E= 1 ( E任務只能一人干任務只能一人干) ) x x1212+ + x x2222+ + x x3232+ + x x4242= 1 ( J= 1 ( J任務只能一人干任務只能一人干) ) x x1313+ + x x2323+ + x x3333+ + x x4343= 1 ( G= 1 ( G任務只能一人干任務只能一人干) ) x x1414+ + x x2424+ + x x3434+ + x x4444= 1 ( R= 1 ( R任務只能一人干任務只

32、能一人干) ) x xijij = 0 = 0 或或 1 1，i,j i,j = 1,2,3,4= 1,2,3,4min z=2min z=2x x1111+15+15x x1212+13+13x x1313+4+4x x1414+10+10 x x2121+4+4x x2222+14+14x x2323+15+15x x2424 +9 +9x x3131+14+14x x3232+16+16x x3333+13+13x x3434+7+7x x41 41 +8+8x x4242+11+11x x4343+9+9x x44441， 指派第指派第i人去完成第人去完成第j項任務項任務 0， 不指派

33、第不指派第i人去完成第人去完成第j項任務項任務 解：令解：令 xij=管理運籌學 _線性規(guī)劃課堂練習課堂練習:P57例例2.23例：例：甲、乙、丙、丁是四名游泳運動員，他們各種甲、乙、丙、丁是四名游泳運動員，他們各種姿勢的姿勢的100m游泳成績?nèi)绫怼榻M成一個游泳成績?nèi)绫?。為組成一個4100m混合泳接力隊，怎樣選派運動員，方使接力隊的游混合泳接力隊，怎樣選派運動員，方使接力隊的游泳成績最好？泳成績最好？運動員運動員仰泳仰泳蛙泳蛙泳蝶泳蝶泳自由泳自由泳甲甲75.586.866.658.4乙乙65.866.257.052.8丙丙67.684.377.859.1丁丁74.069.460.857.0管

34、理運籌學 _線性規(guī)劃3. 背包問題背包問題問題描述問題描述已知：已知：一個背包最大容量為一個背包最大容量為b公斤；有公斤；有m件物品供選擇，每件物品供選擇，每件物品重件物品重ai公斤，價值為公斤，價值為ci（i=1,m）。）。問題：問題：攜帶哪些物品可使總價值最大？攜帶哪些物品可使總價值最大？一般模型一般模型 miiixczMax1s.t.bxamiii 110或或 ix1， 物品物品i被選中被選中 0，物品，物品i沒被選中沒被選中 xi=管理運籌學 _線性規(guī)劃例：例：一個徒步旅行者要在背包中選擇一些最有價值的物品攜一個徒步旅行者要在背包中選擇一些最有價值的物品攜帶。他最多能帶帶。他最多能帶1

35、15kg的物品，現(xiàn)有的物品，現(xiàn)有5件物品，分別重件物品，分別重54、35、57、46、19kg，其價值依次為，其價值依次為7、5、9、6、3。問攜帶哪些物。問攜帶哪些物品可使總價值最大？品可使總價值最大？解：解：模型為：模型為：5432136957xxxxxZMax s.t.115194657355454321 xxxxx),51,i (10 或或ix管理運籌學 _線性規(guī)劃4. 消防隊問題消防隊問題 某城市的消防總部將全市劃分為某城市的消防總部將全市劃分為11個防火區(qū)，設有個防火區(qū)，設有4個個消防救火站。下圖消防救火站。下圖表示消防站，表示消防站，111表示防火區(qū)域，表示防火區(qū)域，圖中連線表示

36、各地區(qū)由哪個消防站負責。問題：可否減少消圖中連線表示各地區(qū)由哪個消防站負責。問題：可否減少消防站的數(shù)目，仍能同樣負責各地區(qū)的防火任務？如果可以，防站的數(shù)目，仍能同樣負責各地區(qū)的防火任務？如果可以，應關閉哪個消防站？應關閉哪個消防站？12345678910111234管理運籌學 _線性規(guī)劃1， 保留第保留第i個消防隊個消防隊 0， 撤消第撤消第i個消防隊個消防隊解：解：令令 xi=min z= x1+x2+x3+x4 x1+x2 1x1+x2 1x1 1x1 +x3 1 x3 1x1 +x3+x41x1 +x41x1+x2 +x41x1 +x41 x41 x3+x41xi=0或或 1，i=1,

37、,4則模型為則模型為管理運籌學 _線性規(guī)劃課堂練習課堂練習: 某市為方便學生上學，擬在新建的居民小區(qū)增設某市為方便學生上學，擬在新建的居民小區(qū)增設若干所小學。已知備選校址代號及其能覆蓋的居民若干所小學。已知備選校址代號及其能覆蓋的居民小區(qū)編號如表所示，問為覆蓋所有小區(qū)至少應建多小區(qū)編號如表所示，問為覆蓋所有小區(qū)至少應建多少所小學？少所小學？備選校址代號備選校址代號覆蓋的居民小區(qū)編號覆蓋的居民小區(qū)編號ABCDEF1、5、71、2、51、3、52、4、53、64、6管理運籌學 _線性規(guī)劃4 4 運輸問題運輸問題一、運輸問題的提出一、運輸問題的提出生產(chǎn)某種產(chǎn)品，生產(chǎn)某種產(chǎn)品， m m個產(chǎn)地：個產(chǎn)地：

38、A A1 1,，A Am m, ,產(chǎn)量：產(chǎn)量：a a1 1,，a am m n n個銷地：個銷地：B B1 1,，B Bn n, ,銷量：銷量：b b1 1,，b bn n已知：已知：A Ai i至至B Bj j的運輸單價為的運輸單價為c cijij問題：確定問題：確定A Ai i運往運往B Bj j的數(shù)量的數(shù)量x xijij，使總運費最低？使總運費最低？管理運籌學 _線性規(guī)劃二、運輸問題的表示二、運輸問題的表示網(wǎng)絡圖網(wǎng)絡圖運輸表運輸表線性規(guī)劃模型線性規(guī)劃模型管理運籌學 _線性規(guī)劃A2A3B2A1B3B4B1運輸問題網(wǎng)絡圖運輸問題網(wǎng)絡圖a2=4a3=9b1=3b2=6b3=5b4=6a1=7供

39、應量供應量供應地供應地運價運價需求量需求量需求地需求地311310192874105管理運籌學 _線性規(guī)劃運輸問題的表格表示運輸問題的表格表示 B1 B2 B3 B4 3 11 3 10 A1 x11 x12 x13 x14 7 1 9 2 8 A2 x21 x22 x23 x24 4 7 4 10 5 A3 x31 x32 x33 x34 9 3 6 5 6 管理運籌學 _線性規(guī)劃運輸問題線性規(guī)劃模型運輸問題線性規(guī)劃模型 0), 1(), 1(min1111ijjmiijinjijminjijijxnjbxmiaxstxcz產(chǎn)量約束產(chǎn)量約束銷量約束銷量約束管理運籌學 _線性規(guī)劃三、運輸問題的

40、分類三、運輸問題的分類產(chǎn)銷平衡問題：產(chǎn)銷平衡問題：aai i= b= bj j產(chǎn)銷不平衡問題：產(chǎn)銷不平衡問題：供大于求：供大于求：ai bj供不應求：供不應求：ai bj管理運籌學 _線性規(guī)劃四、運輸問題的求解四、運輸問題的求解表上作業(yè)法表上作業(yè)法確定初始可行調運方案確定初始可行調運方案最小元素法最小元素法判別當前可行方案是否最優(yōu)判別當前可行方案是否最優(yōu)閉回路法閉回路法對現(xiàn)有方案進行調整對現(xiàn)有方案進行調整 閉回路法閉回路法管理運籌學 _線性規(guī)劃用最小元素法確定初始可行調運方案用最小元素法確定初始可行調運方案 最小元素法的基本思想：就近盡量滿足供應最小元素法的基本思想：就近盡量滿足供應 B1 B

41、2 B3 B4 3 11 3 10 A1 7 1 9 2 8 A2 4 7 4 10 5 A3 9 3 6 5 6 31 346 301 040303 0300管理運籌學 _線性規(guī)劃36453銷量銷量8410720134630810229109520101產(chǎn)量產(chǎn)量戊戊丁丁丙丙乙乙甲甲 產(chǎn)地產(chǎn)地銷地銷地例：最小元素法求解下面運輸問題的初始解例：最小元素法求解下面運輸問題的初始解4543113管理運籌學 _線性規(guī)劃用閉回路法進行最優(yōu)性檢驗用閉回路法進行最優(yōu)性檢驗 1 1、找空格的閉回路、找空格的閉回路：以某空格為起點，用水平線或以某空格為起點，用水平線或垂直線向前劃，只能在碰到某一數(shù)字格時才能轉彎

42、，按照這垂直線向前劃，只能在碰到某一數(shù)字格時才能轉彎，按照這一規(guī)則繼續(xù)前進，直到回到起始的空格為止。一規(guī)則繼續(xù)前進，直到回到起始的空格為止。 B1 B2 B3 B4 3 11 3 10 A1 7 1 9 2 8 A2 4 7 4 10 5 A3 9 3 6 5 6 31 34 6 3管理運籌學 _線性規(guī)劃2 2、根據(jù)閉回路計算空格的檢驗數(shù)：、根據(jù)閉回路計算空格的檢驗數(shù)：檢驗數(shù)檢驗數(shù) = = 奇數(shù)頂點的單位運價之和奇數(shù)頂點的單位運價之和 偶數(shù)頂點的單位運價之和偶數(shù)頂點的單位運價之和 B1 B2 B3 B4 3 11 3 10 A1 7 1 9 2 8 A2 4 7 4 10 5 A3 9 3 6

43、 5 6 31 346 3121-11012檢驗數(shù)的檢驗數(shù)的經(jīng)濟含義：經(jīng)濟含義：當由產(chǎn)地當由產(chǎn)地Ai往銷地往銷地Bj增運一個增運一個單位貨物單位貨物時所引起時所引起的總運輸?shù)目傔\輸成本的變成本的變化數(shù)化數(shù)結論：若所有檢驗數(shù)都大于等于結論：若所有檢驗數(shù)都大于等于0 0，則當前方案最優(yōu)，則當前方案最優(yōu)管理運籌學 _線性規(guī)劃 B1 B2 B3 B4 3 11 3 10 A1 7 1 9 2 8 A2 4 7 4 10 5 A3 9 3 6 5 6 31 346 3-11211012對現(xiàn)有方案進行調整對現(xiàn)有方案進行調整 在負的檢驗數(shù)中選擇絕對值最大的空格，在方案表中從該空在負的檢驗數(shù)中選擇絕對值最大的

44、空格，在方案表中從該空格出發(fā)，沿著其閉回路依次標上格出發(fā)，沿著其閉回路依次標上“+q”+q”、 “ “-q”-q”，+q-q+q-q 其中其中q q表示最大調整量，它的取值為標表示最大調整量，它的取值為標“-q”-q”的數(shù)字中最小的數(shù)值。的數(shù)字中最小的數(shù)值。于是于是q=min3,1 =1q=min3,1 =1管理運籌學 _線性規(guī)劃調整后的方案為調整后的方案為 B1 B2 B3 B4 3 11 3 10 A1 7 1 9 2 8 A2 4 7 4 10 5 A3 9 3 6 5 6 31 3 56 20221912管理運籌學 _線性規(guī)劃36453銷量銷量841072013463081022910

45、9520101產(chǎn)量產(chǎn)量戊戊丁丁丙丙乙乙甲甲 產(chǎn)地產(chǎn)地銷地銷地例：檢驗下表所給可行解的最優(yōu)性例：檢驗下表所給可行解的最優(yōu)性45431131017111230121 所給可行解的最優(yōu)所給可行解的最優(yōu)所有檢驗數(shù)都大于等于所有檢驗數(shù)都大于等于0 0管理運籌學 _線性規(guī)劃五、產(chǎn)銷不平衡問題五、產(chǎn)銷不平衡問題1. 產(chǎn)大于銷產(chǎn)大于銷 （ ） jiba模型：模型： 0), 1(), 1(min1111ijjmiijinjijminjijijxnjbxmiaxstxcz增加增加松弛變量松弛變量), 1(11miaxinjij 運輸表：運輸表：B1BnBn+1A1x11x1nx1,n+1a1Amxm1xmnxm,

46、n+1amb1bnbn+1實際意義：實際意義：虛設一虛設一 個銷地個銷地 jiba運價為零運價為零管理運籌學 _線性規(guī)劃2. 產(chǎn)小于銷產(chǎn)小于銷 （ ） jiba模型：模型： 0), 1(), 1(min1111ijjmiijinjijminjijijxnjbxmiaxstxcz增加增加松弛變量松弛變量), 1(11njbxjmiij 運輸表：運輸表：實際意義：實際意義：虛設一虛設一 個產(chǎn)地個產(chǎn)地 ijabB1BnA1x11x1na1Amxm1xmnamAm+1xm+1，1xm+1,nam+1b1bn管理運籌學 _線性規(guī)劃 六、應用舉例（六、應用舉例（生產(chǎn)與儲存問題生產(chǎn)與儲存問題） 例例、某廠按

47、合同規(guī)定須于當年每個季度末分別提供、某廠按合同規(guī)定須于當年每個季度末分別提供10、15、25、20臺同一規(guī)格的柴油機。已知該廠各季臺同一規(guī)格的柴油機。已知該廠各季度的生產(chǎn)能力及生產(chǎn)每臺柴油機的成本如右表。如果度的生產(chǎn)能力及生產(chǎn)每臺柴油機的成本如右表。如果生產(chǎn)出來的柴油機當季不交貨，每臺每積壓一個季度生產(chǎn)出來的柴油機當季不交貨，每臺每積壓一個季度需儲存、維護等費用需儲存、維護等費用0.15萬元。萬元。 試求在完成合同的情況下，使該廠全年生產(chǎn)總費用試求在完成合同的情況下，使該廠全年生產(chǎn)總費用為最小的決策方案。為最小的決策方案。生產(chǎn)能力生產(chǎn)能力單位成本（萬元）單位成本（萬元）一季度一季度2510.8

48、二季度二季度3511.1三季度三季度3011.0四季度四季度1011.3管理運籌學 _線性規(guī)劃 六、應用舉例（六、應用舉例（生產(chǎn)與儲存問題生產(chǎn)與儲存問題） 例例、某廠按合同規(guī)定須于當年每個、某廠按合同規(guī)定須于當年每個季度末分別提供季度末分別提供10、15、25、20臺同一臺同一規(guī)格的柴油機。已知該廠各季度的生產(chǎn)能規(guī)格的柴油機。已知該廠各季度的生產(chǎn)能力及生產(chǎn)每臺柴油機的成本如右表。如果力及生產(chǎn)每臺柴油機的成本如右表。如果生產(chǎn)出來的柴油機當季不交貨，每臺每積壓一個季度需儲存、維護等費用生產(chǎn)出來的柴油機當季不交貨，每臺每積壓一個季度需儲存、維護等費用0.15元。元。 試求在完成合同的情況下，使該廠全

49、年生產(chǎn)總費用為最小的決策方案。試求在完成合同的情況下，使該廠全年生產(chǎn)總費用為最小的決策方案。 生生產(chǎn)產(chǎn)能能力力（臺臺） 單單位位成成本本（萬萬元元） 一一季季度度 25 10.8 二二季季度度 35 11.1 三三季季度度 30 11.0 四四季季度度 10 11.3 產(chǎn)地產(chǎn)地銷地銷地第一季度第一季度第二季度第二季度第三季度第三季度第四季度第四季度第一季度第一季度第二季度第二季度第三季度第三季度第四季度第四季度產(chǎn)量產(chǎn)量銷量銷量253530101015252010.9510.811.1011.2511.111.2511.4011.0011.1511.30MMMMMM分析：分析：本問題可轉化為一運輸問題本問題可轉化為一運輸問題管理運籌學 _線性規(guī)劃 第第一一季季度度 第第二二季季度度 第第三三季季度度 第第四四季季度度 產(chǎn)產(chǎn)量量 第第一一季季度度 1 10 0 1 15 5 0 0 2 25 5 第第二二季季度度 5 5 3 35 5 第第三三季季度度 2 20 0 1 10 0 3 30 0 第第四四季季度度 1 10 0 1 10 0 銷銷量量 1 10 0 1 15 5 2 25 5 2 20 0 最優(yōu)方案為：最優(yōu)方案為：管理運籌學 _線性規(guī)劃