《管理運(yùn)籌學(xué) _線性規(guī)劃課件》由會(huì)員分享，可在線閱讀，更多相關(guān)《管理運(yùn)籌學(xué) _線性規(guī)劃課件（64頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

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

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

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

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

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

6、理運(yùn)籌學(xué) _線性規(guī)劃甲甲乙乙資源限制資源限制煤煤94360電電45200油油310300單價(jià)單價(jià)712產(chǎn)品產(chǎn)品資源資源線性規(guī)劃模型三要素：線性規(guī)劃模型三要素：（1）決策變量）決策變量 設(shè)甲產(chǎn)品生產(chǎn)設(shè)甲產(chǎn)品生產(chǎn)x1，乙產(chǎn)品生產(chǎn)，乙產(chǎn)品生產(chǎn)x2（2）目標(biāo)函數(shù)）目標(biāo)函數(shù) Max Z=7 x1 +12x2（3）約束條件）約束條件9 x1 +4x23604x1 +5x2 2003 x1 +10 x2 300 x1 , x20s.t.返回Subject To， 意為意為“使其滿使其滿足足”管理運(yùn)籌學(xué) _線性規(guī)劃目標(biāo)函數(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模型的一般形式模型的一般形式管理運(yùn)籌學(xué) _線性規(guī)劃課堂練習(xí)課堂練習(xí) 某蓄場(chǎng)每日要為每頭牲畜購(gòu)買飼料，以使其某蓄場(chǎng)每日要為每頭牲畜購(gòu)買飼料，以使其獲取所需的獲取所需的A、B、C、D四種養(yǎng)分。有關(guān)數(shù)據(jù)四種養(yǎng)分。有關(guān)數(shù)據(jù)如下表，現(xiàn)飼料可從市場(chǎng)上出售的如下表，現(xiàn)飼料可從市場(chǎng)上出售的M、N兩種飼兩種飼料中選擇，試決定總花費(fèi)最小的購(gòu)買方案。料中選擇，試決

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

9、200每頭日需每頭日需10587養(yǎng)分養(yǎng)分飼料飼料答案：答案：設(shè)購(gòu)買設(shè)購(gòu)買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管理運(yùn)籌學(xué) _線性規(guī)劃二、線性規(guī)劃的標(biāo)準(zhǔn)型二、線性規(guī)劃的標(biāo)準(zhǔn)型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、標(biāo)準(zhǔn)形式、標(biāo)準(zhǔn)形式矩陣表示矩陣表示Max Z = CXAX=bX 0s.t.其中：其中：C=(c1,c2, , cn) 稱為稱為價(jià)格系數(shù)價(jià)格系數(shù) A=(aij)mn 稱為稱為技術(shù)系數(shù)技術(shù)系數(shù) b= (b1,b2, , bm) 稱為稱為資源系數(shù)資源系數(shù)管理運(yùn)籌學(xué) _線性規(guī)劃2、非標(biāo)準(zhǔn)型、非標(biāo)準(zhǔn)型標(biāo)準(zhǔn)型標(biāo)準(zhǔn)型（1）Min Z = CXMax Z = -CX（2）約束條件）約束條件例如：例如： 9 x1 +4x23609 x1 +4x2+ x3=360松弛變量松弛變量 “”型約束，加松弛變量；型約束，加松弛變量； “”型約束，減松弛變量；型約束，減松弛變量；管理運(yùn)籌學(xué) _線性規(guī)劃例、

11、將如下問題化為標(biāo)準(zhǔn)型例、將如下問題化為標(biāo)準(zhǔn)型 0,52327.32321321321321321xxxxxxxxxxxxtsxxxzMin解解：令：令第二個(gè)約束減松弛變量第二個(gè)約束減松弛變量x6，得標(biāo)準(zhǔn)型：得標(biāo)準(zhǔn)型：)(zzzMaxzMin 0,52327.3232132153214321321xxxxxxxxxxxxxxtsxxxzMax，第一個(gè)約束加松弛變量，第一個(gè)約束加松弛變量x5 5，管理運(yùn)籌學(xué) _線性規(guī)劃三、線性規(guī)劃的圖解法三、線性規(guī)劃的圖解法1. 步驟步驟（1）作約束的圖形）作約束的圖形可行域可行域可行解的集合可行解的集合先作非負(fù)約束先作非負(fù)約束再作資源約束再作資源約束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管理運(yùn)籌學(xué) _線性規(guī)劃（2）作目標(biāo)函數(shù)的等值線）作目標(biāo)函數(shù)的等值線給給z不同的值，作相應(yīng)直線，判斷出不同的值，作相應(yīng)直線，判斷出z增大時(shí)，直線的移動(dòng)方向增大時(shí)，直線的移動(dòng)方向?qū)⒅本€向增大方向移動(dòng)，直至可行域?qū)⒅本€向增大方向移動(dòng)，直至可行域邊界，交點(diǎn)邊界，交點(diǎn)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管理運(yùn)籌學(xué) _線性規(guī)劃最優(yōu)解：最優(yōu)解： x1 = 0， x2 = 1 最優(yōu)目標(biāo)值最優(yōu)目標(biāo)值 z = 6課堂練習(xí)課堂練習(xí)圖解法求解線性規(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)管理運(yùn)籌學(xué) _線性規(guī)劃2. LP 解的幾種情況解的幾種情況（1）唯一解）唯一解（2）多重最優(yōu)解）多重最優(yōu)解（3）無(wú)可行解）無(wú)可行解注：出現(xiàn)（注：出現(xiàn)（3）、（）、（4）情況時(shí)，建模有問題）情況時(shí)，建模有問題（4）無(wú)有限最優(yōu)解）無(wú)有限最優(yōu)解管理運(yùn)籌學(xué) _線性規(guī)劃圖解法的結(jié)論：圖解法的結(jié)論：線性規(guī)劃的可行域是凸集線性規(guī)劃的可行域是凸集 線性規(guī)劃的最優(yōu)解若存在，必在可行域的在極點(diǎn)獲得線性規(guī)劃的最優(yōu)解若存在，必在可行域的在極點(diǎn)獲得 若在兩個(gè)極點(diǎn)同時(shí)獲得，則有無(wú)窮多最優(yōu)解若在兩個(gè)極點(diǎn)同時(shí)獲得，則有無(wú)窮多最優(yōu)解凸集凸集不是凸集不是凸集極極點(diǎn)點(diǎn)管理運(yùn)籌學(xué) _線性規(guī)劃2 2 線性規(guī)劃應(yīng)用

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

16、原料每根長(zhǎng)根長(zhǎng)7.4 m7.4 m，問：應(yīng)如何下料，可使所用原料最??？，問：應(yīng)如何下料，可使所用原料最?。糠桨?.92.11.5余料7.4 m7.4 m2.9m2.9m2.1m2.1m1.5 m1.5 m2010.11200.31110.910300301.10220.20130.80041.4管理運(yùn)籌學(xué) _線性規(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設(shè)設(shè) 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管理運(yùn)籌學(xué) _線性規(guī)劃線性規(guī)劃求解軟件lindo管理運(yùn)籌學(xué) _線性規(guī)劃3 3 整數(shù)規(guī)劃整數(shù)規(guī)劃Integer Programming(Integer Pro

19、gramming(簡(jiǎn)稱簡(jiǎn)稱IP)IP)一、整數(shù)規(guī)劃的一般模型一、整數(shù)規(guī)劃的一般模型LP: max z=CX AX=b X0IP: max z=CX AX=b X0 X為整數(shù)管理運(yùn)籌學(xué) _線性規(guī)劃整數(shù)規(guī)劃的解法：分枝定界法或割平面法整數(shù)規(guī)劃的解法：分枝定界法或割平面法 基本思想是把一個(gè)整數(shù)規(guī)劃問題化為一基本思想是把一個(gè)整數(shù)規(guī)劃問題化為一系列的線性規(guī)劃問題來(lái)求解系列的線性規(guī)劃問題來(lái)求解整數(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管理運(yùn)籌學(xué) _線性規(guī)劃 例例 人力資源分配的問題人力資源分配的問題 某晝夜服務(wù)的公交線路每天各時(shí)間段內(nèi)所需司機(jī)和乘某晝夜服務(wù)的公交線路每天各時(shí)間段內(nèi)所需司機(jī)和乘務(wù)人員數(shù)如下：務(wù)人員數(shù)如下： 設(shè)司機(jī)和乘務(wù)人員分別在各時(shí)間段一開始時(shí)上班，并連續(xù)工設(shè)司機(jī)和乘務(wù)人員分別在各時(shí)間段一開始時(shí)上班，并連續(xù)工作八小時(shí)，問該公交線路怎樣安排司機(jī)和乘務(wù)人員，既能滿作八小時(shí)，問該公交線路怎樣安排司機(jī)和乘務(wù)人員，既能滿足工作需要，又配備最少司機(jī)和乘務(wù)人員足工作需要，又配備最少司機(jī)和乘務(wù)人員? ?班次班次時(shí)間時(shí)間所需人數(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管理運(yùn)籌學(xué) _線性規(guī)劃 解：設(shè)解：設(shè) x xi i 表示第表示第i i班次時(shí)開始上班的司機(jī)和乘務(wù)人班次時(shí)開始上班的司機(jī)和乘務(wù)人員數(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í) 間間 所所 需需 人人 數(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管理運(yùn)籌學(xué) _線性規(guī)劃二、二、 0-10-1整數(shù)規(guī)劃整數(shù)規(guī)劃 投資場(chǎng)所的選址問題投資場(chǎng)所的選址問題 指派問題指派問題 背包問題背包問題 消防隊(duì)問題消防隊(duì)問題管理運(yùn)籌學(xué) _線性規(guī)劃1. 投資場(chǎng)所的選址問題投資場(chǎng)所的選址問題 某城市擬在東、西、南三區(qū)設(shè)立商業(yè)網(wǎng)點(diǎn)，備選位置有某城市擬在東、西、南三區(qū)設(shè)立商業(yè)網(wǎng)點(diǎn)，備選位置有A1A7共共7個(gè)，如果選個(gè)，如果選Ai，估計(jì)投資為，估計(jì)投資為bi元，利潤(rùn)為元，利潤(rùn)為ci元，要元，要求總投資不超過求總投資不超過B元，規(guī)定元，規(guī)定 東區(qū)：東區(qū)：A1、A2、A3中至多選中至多選2個(gè)個(gè) 西區(qū)

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

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

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

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

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

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

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

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

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項(xiàng)任務(wù)項(xiàng)任務(wù) 0， 不指派

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

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

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

36、各地區(qū)由哪個(gè)消防站負(fù)責(zé)。問題：可否減少消圖中連線表示各地區(qū)由哪個(gè)消防站負(fù)責(zé)。問題：可否減少消防站的數(shù)目，仍能同樣負(fù)責(zé)各地區(qū)的防火任務(wù)？如果可以，防站的數(shù)目，仍能同樣負(fù)責(zé)各地區(qū)的防火任務(wù)？如果可以，應(yīng)關(guān)閉哪個(gè)消防站？應(yīng)關(guān)閉哪個(gè)消防站？12345678910111234管理運(yùn)籌學(xué) _線性規(guī)劃1， 保留第保留第i個(gè)消防隊(duì)個(gè)消防隊(duì) 0， 撤消第撤消第i個(gè)消防隊(duì)個(gè)消防隊(duì)解：解：令令 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則模型為則模型為管理運(yùn)籌學(xué) _線性規(guī)劃課堂練習(xí)課堂練習(xí): 某市為方便學(xué)生上學(xué)，擬在新建的居民小區(qū)增設(shè)某市為方便學(xué)生上學(xué)，擬在新建的居民小區(qū)增設(shè)若干所小學(xué)。已知備選校址代號(hào)及其能覆蓋的居民若干所小學(xué)。已知備選校址代號(hào)及其能覆蓋的居民小區(qū)編號(hào)如表所示，問為覆蓋所有小區(qū)至少應(yīng)建多小區(qū)編號(hào)如表所示，問為覆蓋所有小區(qū)至少應(yīng)建多少所小學(xué)？少所小學(xué)？備選校址代號(hào)備選校址代號(hào)覆蓋的居民小區(qū)編號(hào)覆蓋的居民小區(qū)編號(hào)ABCDEF1、5、71、2、51、3、52、4、53、64、6管理運(yùn)籌學(xué) _線性規(guī)劃4 4 運(yùn)輸問題運(yùn)輸問題一、運(yùn)輸問題的提出一、運(yùn)輸問題的提出生產(chǎn)某種產(chǎn)品，生產(chǎn)某種產(chǎn)品， m m個(gè)產(chǎn)地：個(gè)產(chǎn)地：

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

39、應(yīng)量供應(yīng)量供應(yīng)地供應(yīng)地運(yùn)價(jià)運(yùn)價(jià)需求量需求量需求地需求地311310192874105管理運(yùn)籌學(xué) _線性規(guī)劃運(yùn)輸問題的表格表示運(yùn)輸問題的表格表示 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 管理運(yùn)籌學(xué) _線性規(guī)劃運(yùn)輸問題線性規(guī)劃模型運(yùn)輸問題線性規(guī)劃模型 0), 1(), 1(min1111ijjmiijinjijminjijijxnjbxmiaxstxcz產(chǎn)量約束產(chǎn)量約束銷量約束銷量約束管理運(yùn)籌學(xué) _線性規(guī)劃三、運(yùn)輸問題的

40、分類三、運(yùn)輸問題的分類產(chǎn)銷平衡問題：產(chǎn)銷平衡問題：aai i= b= bj j產(chǎn)銷不平衡問題：產(chǎn)銷不平衡問題：供大于求：供大于求：ai bj供不應(yīng)求：供不應(yīng)求：ai bj管理運(yùn)籌學(xué) _線性規(guī)劃四、運(yùn)輸問題的求解四、運(yùn)輸問題的求解表上作業(yè)法表上作業(yè)法確定初始可行調(diào)運(yùn)方案確定初始可行調(diào)運(yùn)方案最小元素法最小元素法判別當(dāng)前可行方案是否最優(yōu)判別當(dāng)前可行方案是否最優(yōu)閉回路法閉回路法對(duì)現(xiàn)有方案進(jìn)行調(diào)整對(duì)現(xiàn)有方案進(jìn)行調(diào)整 閉回路法閉回路法管理運(yùn)籌學(xué) _線性規(guī)劃用最小元素法確定初始可行調(diào)運(yùn)方案用最小元素法確定初始可行調(diào)運(yùn)方案 最小元素法的基本思想：就近盡量滿足供應(yīng)最小元素法的基本思想：就近盡量滿足供應(yīng) 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管理運(yùn)籌學(xué) _線性規(guī)劃36453銷量銷量8410720134630810229109520101產(chǎn)量產(chǎn)量戊戊丁丁丙丙乙乙甲甲 產(chǎn)地產(chǎn)地銷地銷地例：最小元素法求解下面運(yùn)輸問題的初始解例：最小元素法求解下面運(yùn)輸問題的初始解4543113管理運(yùn)籌學(xué) _線性規(guī)劃用閉回路法進(jìn)行最優(yōu)性檢驗(yàn)用閉回路法進(jìn)行最優(yōu)性檢驗(yàn) 1 1、找空格的閉回路、找空格的閉回路：以某空格為起點(diǎn)，用水平線或以某空格為起點(diǎn)，用水平線或垂直線向前劃，只能在碰到某一數(shù)字格時(shí)才能轉(zhuǎn)彎

42、，按照這垂直線向前劃，只能在碰到某一數(shù)字格時(shí)才能轉(zhuǎn)彎，按照這一規(guī)則繼續(xù)前進(jìn)，直到回到起始的空格為止。一規(guī)則繼續(xù)前進(jìn)，直到回到起始的空格為止。 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管理運(yùn)籌學(xué) _線性規(guī)劃2 2、根據(jù)閉回路計(jì)算空格的檢驗(yàn)數(shù)：、根據(jù)閉回路計(jì)算空格的檢驗(yàn)數(shù)：檢驗(yàn)數(shù)檢驗(yàn)數(shù) = = 奇數(shù)頂點(diǎn)的單位運(yùn)價(jià)之和奇數(shù)頂點(diǎn)的單位運(yùn)價(jià)之和 偶數(shù)頂點(diǎn)的單位運(yùn)價(jià)之和偶數(shù)頂點(diǎn)的單位運(yùn)價(jià)之和 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檢驗(yàn)數(shù)的檢驗(yàn)數(shù)的經(jīng)濟(jì)含義：經(jīng)濟(jì)含義：當(dāng)由產(chǎn)地當(dāng)由產(chǎn)地Ai往銷地往銷地Bj增運(yùn)一個(gè)增運(yùn)一個(gè)單位貨物單位貨物時(shí)所引起時(shí)所引起的總運(yùn)輸?shù)目傔\(yùn)輸成本的變成本的變化數(shù)化數(shù)結(jié)論：若所有檢驗(yàn)數(shù)都大于等于結(jié)論：若所有檢驗(yàn)數(shù)都大于等于0 0，則當(dāng)前方案最優(yōu)，則當(dāng)前方案最優(yōu)管理運(yùn)籌學(xué) _線性規(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對(duì)現(xiàn)有方案進(jìn)行調(diào)整對(duì)現(xiàn)有方案進(jìn)行調(diào)整 在負(fù)的檢驗(yàn)數(shù)中選擇絕對(duì)值最大的空格，在方案表中從該空在負(fù)的檢驗(yàn)數(shù)中選擇絕對(duì)值最大的

44、空格，在方案表中從該空格出發(fā)，沿著其閉回路依次標(biāo)上格出發(fā)，沿著其閉回路依次標(biāo)上“+q”+q”、 “ “-q”-q”，+q-q+q-q 其中其中q q表示最大調(diào)整量，它的取值為標(biāo)表示最大調(diào)整量，它的取值為標(biāo)“-q”-q”的數(shù)字中最小的數(shù)值。的數(shù)字中最小的數(shù)值。于是于是q=min3,1 =1q=min3,1 =1管理運(yùn)籌學(xué) _線性規(guī)劃調(diào)整后的方案為調(diào)整后的方案為 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管理運(yùn)籌學(xué) _線性規(guī)劃36453銷量銷量841072013463081022910

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

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

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

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

49、年生產(chǎn)總費(fèi)用為最小的決策方案。試求在完成合同的情況下，使該廠全年生產(chǎn)總費(fèi)用為最小的決策方案。 生生產(chǎn)產(chǎn)能能力力（臺(tái)臺(tái)） 單單位位成成本本（萬(wàn)萬(wà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分析：分析：本問題可轉(zhuǎn)化為一運(yùn)輸問題本問題可轉(zhuǎn)化為一運(yùn)輸問題管理運(yùn)籌學(xué) _線性規(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)方案為：管理運(yùn)籌學(xué) _線性規(guī)劃