1、精選優(yōu)質(zhì)文檔-傾情為你奉上管理運籌學(xué)課件第一章_管理運籌學(xué)線性規(guī)劃管理運籌學(xué)Operational Research天津大學(xué)管理學(xué)院郭均鵬管理運籌學(xué)教師簡介：郭均鵬：博士，副教授， 碩士生導(dǎo)師。主要研究領(lǐng)域： 運籌決策技術(shù)；信息管理與8企業(yè)信息3化；績效考核與薪酬體系設(shè)計 聯(lián)系方式：天津大學(xué)管理學(xué)院， 管理運籌學(xué)授課內(nèi)容： 線性規(guī)劃 圖論與網(wǎng)絡(luò)分析 網(wǎng)絡(luò)計劃 風(fēng)險型決策排隊論 博弈論課程教材：吳育華,杜綱. 管理科學(xué)基礎(chǔ)，天津大學(xué)出版社。管理運籌學(xué)緒 論 產(chǎn)生于二戰(zhàn)時期，運籌學(xué)（Operational Research) 直譯為“運作研究”。 60年代，在工業(yè)、農(nóng)業(yè)、社

2、會等各領(lǐng)域得到廣泛應(yīng)用 在我國，50年代中期由錢學(xué)森等引入 運用數(shù)學(xué)方法，為決策者進(jìn)行最優(yōu)決策提供科學(xué)依據(jù)的一門應(yīng)用科學(xué)。一、運籌學(xué)的產(chǎn)生與發(fā)展二、學(xué)科性質(zhì)管理運籌學(xué)三、運籌學(xué)的分支線性規(guī)劃非線性規(guī)劃圖論與網(wǎng)絡(luò)分析存儲論決策論排隊論對策論（博弈論）管理運籌學(xué)四、管理運籌學(xué)的工作程序明確問題問題分類建立數(shù)學(xué)模型求解數(shù)學(xué)模型結(jié)果分析實施 注意計算機(jī)軟件的應(yīng)用 Lindo、WinQSB等管理運籌學(xué)第一章 線性規(guī)劃（Linear Programming，簡稱LP）1 線性規(guī)劃的模型與圖解法一、LP問題及其數(shù)學(xué)模型例1 某工廠可生產(chǎn)甲、乙兩種產(chǎn)品，需消耗煤、電、油三種資源，有關(guān)單耗數(shù)據(jù)如表，試擬定使總收

3、入最大的生產(chǎn)計劃。127單價300103油20054電36049煤資源限制乙甲產(chǎn)品資源管理運籌學(xué)127單價300103油20054電36049煤資源限制乙甲產(chǎn)品資源線性規(guī)劃模型三要素：（1）決策變量 設(shè)甲產(chǎn)品生產(chǎn)x1，乙產(chǎn)品生產(chǎn)x2（2）目標(biāo)函數(shù) Max Z=7 x1 +12x2（3）約束條件9 x1 +4x23604x1 +5x2 2003 x1 +10x2 300x1 , x20s.t.返回Subject To， 意為“使其滿足”管理運籌學(xué)Max （Min） Z = c1 x1 + c2 x2 + + cn xn a11 x1 + a12 x2 + + a1n xn （ =, ）b1 am

4、1 x1 + am2 x2 + + amn xn （ =, ）bmx1 ，x2 ， ，xn 0s.t. LP模型的一般形式矩陣表示Max Z = CXAX bX 0s.t.其中: X= (x1,x2, , xn) T 為決策變量 C=(c1,c2, , cn) 稱為價格系數(shù)A=(aij)mn 稱為技術(shù)系數(shù)b= (b1,b2, , bm) T 稱為資源系數(shù)管理運籌學(xué)課堂練習(xí) 某蓄場每日要為每頭牲畜購買飼料，以使其獲取所需的A、B、C、D四種養(yǎng)分。有關(guān)數(shù)據(jù)如下表，現(xiàn)飼料可從市場上出售的M、N兩種飼料中選擇，試決定總花費最小的購買方案。（列出模型）78510每頭日需2000.1N3

5、000M價格DCBA養(yǎng)分飼料管理運籌學(xué)課堂練習(xí) 某蓄場每日要為每頭牲畜購買飼料，以使其獲取所需的A、B、C、D四種養(yǎng)分。有關(guān)數(shù)據(jù)如下表，現(xiàn)飼料可從市場上出售的M、N兩種飼料中選擇，試決定總花費最小的購買方案。（列出模型）78510每頭日需2000.1N3000M價格DCBA養(yǎng)分飼料答案：設(shè)購買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 +200x2管理運籌學(xué)二、線性規(guī)劃的圖解法1. 步驟（1）作約束的圖形可行域可

6、行解的集合先作非負(fù)約束再作資源約束9x1+4x2=3604x1+5x2=2003x1+10x2=300公共部分，即為可行域例：煤電油例Max Z=7 x1 +12x29 x1 +4x23604x1 +5x2 2003 x1 +10x2 300x1 , x20s.t.x1x240206080100204060801000管理運籌學(xué)（2）作目標(biāo)函數(shù)的等值線給z不同的值，作相應(yīng)直線，判斷出z增大時，直線的移動方向?qū)⒅本€向增大方向移動，直至可行域邊界，交點X*即為最優(yōu)解。7x1+12x2=847x1+12x2=168如：令7 x1 +12x2=84 7 x1 +12x2=1689x1+4x2=3604

7、x1+5x2=2003x1+10x2=300x1x240206080100204060801000X*=（20，24），Z*=428管理運籌學(xué)最優(yōu)解： x1 = 0， x2 = 1 最優(yōu)目標(biāo)值 z = 3課堂練習(xí)圖解法求解線性規(guī)劃012341234x1x2O-1-2(1)(2)(3)管理運籌學(xué)2. LP 解的幾種情況（1）唯一解（2）多重最優(yōu)解（3）無可行解注：出現(xiàn)（3）、（4）情況時，建模有問題（4）無有限最優(yōu)解管理運籌學(xué)圖解法的結(jié)論：線性規(guī)劃的可行域是凸集 線性規(guī)劃的最優(yōu)解若存在，必在可行域的在極點獲得 若在兩個極點同時獲得，則有無窮多最優(yōu)解凸集不是凸集極點管理運籌學(xué)三、 線性規(guī)劃應(yīng)用舉例

8、與軟件求解 例1 （下料問題） 某工廠要做100套鋼架，每套用長為2.9 m,2.1 m,1.5 m的圓鋼各一根。已知原料每根長7.4 m，問：應(yīng)如何下料，可使所用原料最?。抗芾磉\籌學(xué) 例1 （下料問題） 某工廠要做100套鋼架，每套用長為2.9 m,2.1 m,1.5 m的圓鋼各一根。已知原料每根長7.4 m，問：應(yīng)如何下料，可使所用原料最?。坑嗔戏桨?.4 m2.9m2.1m1.5 m2010.11200.31110.910300301.10220.20130.80041.4管理運籌學(xué)501030 2x1 + x2 + x3 + x4 = 100 2x2 + x3 + 3

9、x5 + 2x6 + x7 = 100 x1 + x3+ 3x4 + 2x6 + 3x7 + 4x8 = 100 x1, x2, x3, x4, x5, x6, x7, x8 0設(shè) x1,x2,x3,x4,x5,x6,x7,x8 分別為上述8種方案下料的原材料根數(shù)，建立如下的LP模型：最優(yōu)解為： x1=10,x2=50,x3=0,x4=30,x5=0,x6=0,x7=0,x8=0min Z =x1 + x2 + x3 + x4 + x5 + x6 + x7 + x8s.t.余料方案2010.11200.31110.910300301.10220.20130.80041.4管理

10、運籌學(xué)一、線性規(guī)劃的標(biāo)準(zhǔn)型Max Z = c1 x1 + c2 x2 + + cn xn a11 x1 + a12 x2 + + a1n xn =b1 am1 x1 + am2 x2 + + amn xn =bmx1 ，x2 ， ，xn 0s.t.1、標(biāo)準(zhǔn)形式Max Z = CXAX=bX 0s.t.注：標(biāo)準(zhǔn)型中要求bi 02 單純形法矩陣表示管理運籌學(xué)2、非標(biāo)準(zhǔn)型標(biāo)準(zhǔn)型（1）Min Z = CXMax Z' = -CX（2）約束條件例如： 9 x1 +4x23609 x1 +4x2+ x3=360松弛變量 “”型約束，加松弛變量； “”型約束，減松弛變量；（3）自由變量xj進(jìn)行變量

11、替換： xj= xj ' - xj ' ' ，其中xj ' 、 xj ' ' 0管理運籌學(xué)二、LP解的基本概念考慮標(biāo)準(zhǔn)型：Max Z = CXAX=bX 0s.t.（1）（2）1. 可行解滿足（1）、（2）的解2. 基本解設(shè)r(A)=m，則BX=b有唯一解，稱為基本解，簡稱基解。且不妨設(shè)非奇異，。設(shè)為，結(jié)論：基本解的個數(shù)管理運籌學(xué)3. 基可行解若基解X0，則稱為基可行解?？尚薪饣饣尚薪饨Y(jié)論：LP的基可行解對應(yīng)于可行域的頂點?；篈中m階可逆子陣，記為B?；蛄浚築中的列?；兞浚汉突蛄肯鄬?yīng)的決策變量。其余部分稱為非基子陣，記為

12、N。管理運籌學(xué)例、研究約束集合基本解的個數(shù)令x2=x3=0，得基本解X1=(1/2, 0, 0)T,對應(yīng)于A點；1/211/3ABCx2x3x1令x1=x3=0，得基本解X2=(0, 1, 0)T,對應(yīng)于B點；令x1=x2=0，得基本解X3=(0, 0, 1/3)T,對應(yīng)于C點；管理運籌學(xué)基可行解例、研究約束集合基本解的個數(shù)令x1=0，得基本解X1=(0, 3, 2, -1)T,對應(yīng)于A點；令x2=0，得基本解X2=(3, 0, 1, -8)T,對應(yīng)于B點；令x3=0，得基本解X3=(2, 1, 0, 5)T,對應(yīng)于F點；畫出可行域12341234ABCDEF0x1x2標(biāo)準(zhǔn)化令x4=0，得基本

13、解X4=(1/3, 8/3, 5/3, 0)T,對應(yīng)于D點；管理運籌學(xué)三、單純形法的基本方法基本方法：確定初始基可行解檢驗是否最優(yōu)？轉(zhuǎn)到另一更好的基可行解停YN方法前提：模型化為標(biāo)準(zhǔn)型管理運籌學(xué)1. 初始可行基B0的確定若A中含有I：B0=I若A中不含I：人工變量法管理運籌學(xué)2. 最優(yōu)性檢驗矩陣分塊把目標(biāo)函數(shù)用非基變量表示：檢驗數(shù)向量，記為。當(dāng) 0時，當(dāng)前解為最優(yōu)解。方法：（1）計算每個xj的檢驗數(shù)（2）若所有j 0 ，則當(dāng)前解為最優(yōu)；否則，至少有k >0 ，轉(zhuǎn)3。管理運籌學(xué)3. 換基迭代（基變換）（1）進(jìn)基：取對應(yīng)的Pk進(jìn)基。（2）出基：取對應(yīng)的Pl進(jìn)基。得新基，轉(zhuǎn)2。管理運籌學(xué)的計算

14、:x5x4x3x2x1B-1bCBXB四、單純形法的實現(xiàn)單純形表例：煤電油例Max Z=7 x1 +12x29 x1 +4x23604x1 +5x2 2003 x1 +10x2 300x1 , x20s.t.Max Z=7 x1 +12x29 x1 +4x2 +x3 =3604x1 +5x2 +x4 = 2003 x1 +10x2 +x5 = 300x1 ,x50s.t.化為標(biāo)準(zhǔn)型x3x4x5000360200300943451010001000112000單純形表:7管理運籌學(xué)x5x4x3x2x1B-1bCBXB四、單純形法的實現(xiàn)單純形表例：煤電油例Max Z=7 x1 +12x29 x1

15、+4x23604x1 +5x2 2003 x1 +10x2 300x1 , x20s.t.Max Z=7 x1 +12x29 x1 +4x2 +x3 =3604x1 +5x2 +x4 = 2003 x1 +10x2 +x5 = 300x1 ,x50s.t.化為標(biāo)準(zhǔn)型x3x4x5000360200300943451010001000112000單純形表:790的計算:4030管理運籌學(xué)x5x4x3x2x1B-1bCBXB四、單純形法的實現(xiàn)單純形表例：煤電油例Max Z=7 x1 +12x29 x1 +4x23604x1 +5x2 2003 x1 +10x2 300x1 , x20s.t.Max

16、Z=7 x1 +12x29 x1 +4x2 +x3 =3604x1 +5x2 +x4 = 2003 x1 +10x2 +x5 = 300x1 ,x50s.t.化為標(biāo)準(zhǔn)型x3x4x5000360200300943451010001000112000單純形表:7904030 樞紐元素管理運籌學(xué)x5x4x3x2x1B-1bCBXBx3x4x5000360200300943451010001000112000單純形表:7904030 x3x4x20012300.31000.1以10為主元進(jìn)行初等行變換502.5001-0.52407.8010-0.43.4000-1.2即:管理運籌學(xué)x5x4x3x2x

17、1B-1bCBXBx3x4x5000360200300943451010001000112000單純形表:7904030 x3x4x20012300.31000.1以10為主元進(jìn)行初等行變換502.5001-0.52407.8010-0.43.4000-1.2即:30.820100管理運籌學(xué)x5x4x3x2x1B-1bCBXBx3x4x5000360200300943451010001000112000單純形表:7904030 x3x4x20012300.31000.1以10為主元進(jìn)行初等行變換502.5001-0.52407.8010-0.43.4000-1.230.820100 管理運籌學(xué)

18、x3x1x2071224010-0.120.16201000.4-0.284001-3.121.16000-1.36-0.52x5x4x3x2x1B-1bCBXBx3x4x5000360200300943451010001000112000單純形表:7904030 x3x4x20012300.31000.1502.5001-0.52407.8010-0.43.4000-1.230.820100 以 為主元進(jìn)行初等行變換2.5管理運籌學(xué)x3x1x2071224010-0.120.16201000.4-0.284001-3.121.16000-1.36-0.52x5x4x3x2x1B-1bCBXB

19、x3x4x5000360200300943451010001000112000單純形表:7904030 x3x4x20012300.31000.1502.5001-0.52407.8010-0.43.4000-1.230.820100 X*=(20,24,84,0,0)T Z*=428管理運籌學(xué)例：用單純形法求解Min S= - x1 +2x2x1 - x2 - 2x1 +2x2 6x1 , x20s.t.化為標(biāo)準(zhǔn)型Max S?= x1 -2x2-x1 + x2 +x3 = 2x1 +2x2 +x4= 6x1 , ,x40s.t.-216102160x4不考慮011-120x3x4x3x2x1

20、B-1bCBXB-10-40102161x1113080x3X*=(6,0,8,0)T Z*= -6管理運籌學(xué)x3x1x2071224010-0.120.16201000.4-0.284001-3.121.16000-1.36-0.52x5x4x3x2x1B-1bCBXBx3x4x5000360200300943451010001000112000單純形表:7904030x3x4x20012300.31000.1502.5001-0.52407.8010-0.43.4000-1.230.820100注：單純形表中的信息每一列的含義：B-1(b A)=(B-1b, B-1 P1,， B-1 Pn

21、)每個表中的B和B-1的查找： B從初表中找； B-1從當(dāng)前表中找，對應(yīng)于初表中的I的位置。 以第2個表為例：管理運籌學(xué)終表分析最優(yōu)基B* 和(B*)-1的查找x3x1x2071224010-0.120.16201000.4-0.284001-3.121.16000-1.36-0.52x5x4x3x2x1B-1bCBXBx3x4x5000360200300943451010001000112000單純形表:7904030x3x4x20012300.31000.1502.5001-0.52407.8010-0.43.4000-1.230.820100注：單純形表中的信息管理運籌學(xué)1五、人工變量法

22、（大M法）1 問題:例：用單純形法求解Max Z = 5x1+3x2+2x3+4x45x1+ x2+ x3+8x4=102x1+4x2+3x3+2x4=10x1,x2,x3,x4 0s.t.Max Z = CXAX=bX 0s.t.設(shè)問題：，A中不含I()管理運籌學(xué)增加人工變量 X人=（xn+1，xn+m）T，X人在目標(biāo)函數(shù)中的系數(shù)為 -M（M為充分大正數(shù)）。于是原問題化為：2 方法:單純形法求解() ,若最優(yōu)基變量中不含X人，則所得解的前n個分量即為X*否則， ()無解。3 結(jié)論:Max Z = CX- M X人AX +IX人=bX , X人 0s.t.()管理運籌學(xué)例：用單純形法求解Max

23、 Z = 5x1+3x2+2x3+4x45x1+ x2+ x3+8x4=102x1+4x2+3x3+2x4=10x1,x2,x3,x4 0s.t.解：增加人工變量x5、x6，則模型化為：Max Z = 5x1+3x2+2x3+4x4-Mx5-Mx65x1+ x2+ x3+8x4+x5 =102x1+4x2+3x3+2x4 +x6=10x1,x6 0s.t.管理運籌學(xué)Max Z = 5x1+3x2+2x3+4x4-Mx5-Mx65x1+ x2+ x3+8x4+x5 =102x1+4x2+3x3+2x4 +x6=10x1,x6 0s.t.01x51234208115x6x4x3x2x1B-1bCB

24、XBx5x6-M-M10105+7M3+5M2+4M4+10M005/45管理運籌學(xué)01x51234208115x6x4x3x2x1B-1bCBXBx5x6-M-M10105+7M3+5M2+4M4+10M005/45x4x64-M5/45/81/81/81015/23/415/411/4015/2+3/4M005/2+15/4M3/2+11/4M102管理運籌學(xué)01x51234208115x6x4x3x2x1B-1bCBXBx5x6-M-M10105+7M3+5M2+4M4+10M005/45x4x64-M5/45/81/81/81015/23/415/411/4015/2+3/4M005/

25、2+15/4M3/2+11/4M102x4x24313/501/30121/5111/150200-1/35/310管理運籌學(xué)01x51234208115x6x4x3x2x1B-1bCBXBx5x6-M-M10105+7M3+5M2+4M4+10M005/45x4x64-M5/45/81/81/81015/23/415/411/4015/2+3/4M005/2+15/4M3/2+11/4M102x4x24313/501/30121/5111/150200-1/35/310x1x2535/3101/185/35/30113/18-1/30-10/30-4/9X*=(5/3, 5/3, 0, 0)

26、T, Z*=40/3管理運籌學(xué)六、單純形法總結(jié)1、Min型單純形表與Max型的區(qū)別僅在于： 令 k=minj 0的xk進(jìn)基，當(dāng) 0時最優(yōu)。2、解的幾種情況及其在單純形表上的體現(xiàn)（討論Max型）唯一最優(yōu)解j 0,非基<0多重最優(yōu)解j 0有非基k=0無界解有k >0但B-1Pk 0無可行解用大M法求解，最優(yōu)基中含有X人退化解最優(yōu)解中某基變量為0管理運籌學(xué)3 線性規(guī)劃的對偶問題（Dual Programming，簡稱DP）一、對偶問題的提出和模型1、問題的提出煤電油例 今有另廠要購買三種資源，在原廠可接受的條件下，單價多少可是另廠付費最低？Max Z=7 x1 +12x29 x1 +4x

27、23604x1 +5x2 2003 x1 +10x2 300x1 , x20s.t.設(shè)煤電油價格分別為y1, y2, y3Min W=360y1+200y2+300y3s.t.9y1+4y2+3y374y1+5y2+10y312y1, y2, y3 0DUAL管理運籌學(xué)2、模型Max Z = CXAXbX 0s.t.原問題（P）：對偶問題（D）：Min W = bTYATY CTY 0s.t.特點：（1）P為max型，D為min型（2）P的變量個數(shù)=D的約束個數(shù)（3）P的約束個數(shù)=D的變量個數(shù)Max Z=7 x1 +12x29 x1 +4x23604x1 +5x2 2003 x1 +10x2

28、300x1 , x20s.t.Min W=360y1+200y2+300y3s.t.9y1+4y2+3y374y1+5y2+10y312y1, y2, y3 0管理運籌學(xué)1、對稱性（P）與（D）互為對偶二、對偶性質(zhì)與定理2、弱對偶性設(shè)X、Y 分別為（P）、（D）的任一可行解，則管理運籌學(xué)3、解的最優(yōu)性設(shè) 、 分別為（P）與（D）的可行解，且則4、無界性若（P）為無界解，則（D）無可行解若（D）為無界解，則（P）無可行解管理運籌學(xué)5、對偶定理若（P）有最優(yōu)解，則（D）也有最優(yōu)解，且二者最優(yōu)值相等.管理運籌學(xué)小結(jié)：（1）對偶最優(yōu)解Y*= CB B-1，其中B為原問題的最優(yōu)基；（2）如何從（P）的終

29、表中確定Y* ? Y*即為（P）終表的XS的檢驗數(shù)的負(fù)值； 若無XS，則用Y*= CB* (B*)-1計算。- CB B-1C - CB B-1AB-1B-1A CB B-1b0XSCX6、檢驗數(shù)管理運籌學(xué)x3x1x2071224010-0.120.16201000.4-0.284001-3.121.16000-1.36-0.52x5x4x3x2x1B-1bCBXBx3x4x5000360200300943451010001000112000例：煤電油的單純形表:7904030（初表）（終表）由終表：Y*=(0 ,1.36 , 0.52)T管理運籌學(xué)三、對偶問題最優(yōu)解的經(jīng)濟(jì)解釋影子價格 設(shè)DP

30、其最優(yōu)值為Z *(注：與LP最優(yōu)值同），則根據(jù)Z * = bT y* = b1y1* + b2y2* + ? + bmym*?Z / ?bi = yi* 簡單推導(dǎo)： Y*=(y1* , y2* ,， ym* ）為DP的最優(yōu)解，則yi* 表示 LP某資源bi 變化1個單位對目標(biāo) 產(chǎn)生的影響，稱 yi* 為 bi的影子價格。例、煤電油例的對偶問題的最優(yōu)解為Y* =(0 1.36 0.52), 則煤電油三種資源的影子價格分別為0 、 1.36 、 0.52管理運籌學(xué)影子價格在管理決策中的作用：（1）影子價格市場價格 若影子價格市場價格，則應(yīng)影子價格市場價格，則應(yīng)買進(jìn)該資源賣出該資源（2）影子價格反映

31、了資源的稀缺性， 影子價格越高，則越稀缺例如：煤的影子價格為0，則表明有剩余管理運籌學(xué)4 靈敏度分析任務(wù)：當(dāng)LP的系數(shù)A、b、c變化時，是否影響最優(yōu)解或最優(yōu)基？ 或：若不影響最優(yōu)解或最優(yōu)基， A、b、c的變化范圍？對解的影響可行性：B-1b0最優(yōu)性：管理運籌學(xué)一、b變（只影響解的可行性）問題：br在何范圍變化時，不影響最優(yōu)基？設(shè)第 r 種資源brbr+ （b）方法：（保證可行性）即，解出即可例：煤電油例，討論b2的變化解得-5027或150b2227管理運籌學(xué)二、C 變（只影響解的最優(yōu)性）問題： cj在何范圍變化時，不影響最優(yōu)基（解）？設(shè)第 j 種資源cjcj+ （c ）方法：（討論檢驗數(shù)）（

32、1） cj為非基價格系數(shù)，解出管理運籌學(xué)（2） cj為基價格系數(shù)此時需考慮所有非基變量的檢驗數(shù)：解出例：煤電油例，為使最優(yōu)解不變，求c1的變化范圍。解：考慮所有非基檢驗數(shù)同理，令基變量的檢驗數(shù)仍全為0，故無需考慮。管理運籌學(xué)三、A 變（1） 增加新變量xn+1810單價48油36電123煤丁丙例如，煤電油例又增加產(chǎn)品丙或丁，相關(guān)數(shù)據(jù)如右表。問題：增加后是否影響最優(yōu)基（解），從而判斷是否 有利？（使目標(biāo)改善）方法：是否有利取決于是否進(jìn)基。故只需計算，則有利，則不利例:丙不應(yīng)投產(chǎn)。同理可得丁應(yīng)投產(chǎn)。管理運籌學(xué)（2） 某列Pj Pj?（只考慮非基向量情形）問題：改變后是否影響最優(yōu)基（解）、有利？方法

33、：只需計算，則有利，則不利管理運籌學(xué)5 整數(shù)規(guī)劃Integer Programming(簡稱IP)一、整數(shù)規(guī)劃的一般模型LP: max z=CX AX=b X0IP: max z=CX AX=b X0 X為整數(shù)管理運籌學(xué)整數(shù)規(guī)劃的解法：分枝定界法或割平面法 基本思想是把一個整數(shù)規(guī)劃問題化為一系列的線性規(guī)劃問題來求解整數(shù)規(guī)劃的分類： 純整數(shù)規(guī)劃：所有變量都限制為整數(shù) 混合整數(shù)規(guī)劃：僅部分變量限制為整數(shù) 0-1整數(shù)規(guī)劃：變量的取值僅限于0或1管理運籌學(xué)例 人力資源分配的問題 某晝夜服務(wù)的公交線路每天各時間段內(nèi)所需司機(jī)和乘務(wù)人員數(shù)如下： 設(shè)司機(jī)和乘務(wù)人員分別在各時間段一開始時上班，并連續(xù)工作八小時，

34、問該公交線路怎樣安排司機(jī)和乘務(wù)人員，既能滿足工作需要，又配備最少司機(jī)和乘務(wù)人員?302：00 6：0062022：00 2：0055018：00 22：0046014：00 18：0037010：00 14：002606：00 10：001所需人數(shù)時間班次管理運籌學(xué) 解：設(shè) xi 表示第i班次時開始上班的司機(jī)和乘務(wù)人員數(shù),于是LP模型為: x1 + x6 60x1 + x2 70x2 + x3 60x3 + x4 50x4 + x5 20x5 + x6 30x1,x2,x3,x4,x5,x6 0且為整數(shù)min z=x1 + x2 + x3 + x4 + x5 + x6 最優(yōu)解：X* =(60

35、，10，50 ，0 ，30 ，0）， Z*=150管理運籌學(xué)二、 0-1整數(shù)規(guī)劃 投資場所的選址問題 指派問題 背包問題 消防隊問題管理運籌學(xué)1. 投資場所的選址問題 某城市擬在東、西、南三區(qū)設(shè)立商業(yè)網(wǎng)點，備選位置有A1A7共7個，如果選Ai，估計投資為bi元，利潤為ci元，要求總投資不超過B元，規(guī)定 東區(qū)：A1、A2、A3中至多選2個 西區(qū)：A4、A5中至少選一個 南區(qū)：A6、A7中至少選一個問如何設(shè)點使總利潤最大？ 1， Ai被選中 0， Ai沒被選中 解：令 xi=max z= xi=0或 1，i=1, ,7 bixiBi=17x1+x2+x32x4+x51x6+x71s.t.管理運籌學(xué)

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

37、位使總費用最小？ 1， Si被選中 0， Si沒被選中 解：令 xi=min z= s.t.或 1，i=1, ,10管理運籌學(xué) 某籃球隊有8名隊員，其身高和專長如下表，現(xiàn)要選拔5名球員上場參賽，要求：（1）中鋒只有1人上場（2）后衛(wèi)至少有一人上場（3）只有2號上場，6號才上場要求平均身高最高，應(yīng)如何選拔隊員？課堂練習(xí)2:管理運籌學(xué)1， 隊員i被選中 0，隊員i沒被選中 解：令 xi=max z= 或 1，i=1, ,8s.t. 某籃球隊有8名隊員，其身高和專長如下表，現(xiàn)要選拔5名球員上場參賽，要求：（1）中鋒只有1人上場（2）后衛(wèi)至少有一人上場（3）只有2號上場，6號才上場要求平均身高最高，應(yīng)

38、如何選拔隊員？管理運籌學(xué)2. 指派問題 例： 有一份中文說明書，需譯成英、日、德、俄四種文字，分別記作任務(wù)E、J、G、R，現(xiàn)有甲、乙、丙、丁四人，他們將中文說明書翻譯成不同語種說明書所需的時間如下表所示，問應(yīng)指派何人去完成何項任務(wù)，使所需總時間最少？問題描述：n項任務(wù)可由n個人完成，由于專長不同，各人完成各任務(wù)的時間也不同，求最優(yōu)安排。要求：每人只能完成一項任務(wù)，每項任務(wù)只能由一人完成。管理運籌學(xué) x11+ x12+ x13+ x14= 1 (甲只能干一項工作) x21+ x22+ x23+ x24= 1 (乙只能干一項工作) x31+ x32+ x33+ x34= 1 (丙只能干一項工作)

39、x41+ x42+ x43+ x44= 1 (丁只能干一項工作) x11+ x21+ x31+ x41= 1 ( E任務(wù)只能一人干) x12+ x22+ x32+ x42= 1 ( J任務(wù)只能一人干) x13+ x23+ x33+ x43= 1 ( G任務(wù)只能一人干) x14+ x24+ x34+ x44= 1 ( R任務(wù)只能一人干) xij = 0 或 1，i,j = 1,2,3,4min z=2x11+15x12+13x13+4x14+10x21+4x22+14x23+15x24 +9x31+14x32+16x33+13x34+7x41 +8x42+11x43+9x441， 指派第i人去完成第j項任務(wù) 0， 不指派第i人去完成第j項任務(wù) 解：令 xij=管理運籌學(xué)課堂練習(xí):P57例2.23例：甲、乙、丙、丁是四名游泳運動員，他們各種姿勢的100m游泳成績?nèi)绫?。為組成一個4100m混合泳接力隊，怎