1、主講主講: :周曉林周曉林Email:Email:Telel:135888264342021-6-19 浙江理工大學經管學院周曉林浙江理工大學經管學院周曉林22021-6-19 浙江理工大學經管學院周曉林浙江理工大學經管學院周曉林3二、運籌學的歷史與發展二、運籌學的歷史與發展 國際上運籌學的思想可追溯到1914年，當時的蘭徹斯特提出了軍事運籌學的作戰模型。1917年，丹麥工程師埃爾朗在研究自動電話系統中通話線路與用戶呼叫的數量關系問題時，提出了埃爾朗公式，研究了隨機服務系統中的系統排隊與系統擁擠問題。存儲論的最優批量公式是在20世紀20年代初提出的。 2021-6-1

2、9 浙江理工大學經管學院周曉林浙江理工大學經管學院周曉林4鮑德西（鮑德西（Bawdsey）雷達站的研究（）雷達站的研究（1935年）年）1935年，英國科學家R。Watson-Wart發明了雷達。丘吉爾命令在英國東海岸的Bawdsey建立了一個秘密雷達站。當時，德國已擁有一支強大的空軍，起飛17分鐘即到達英國本土。在如此短的時間內，如何預警和攔截成為一大難題。1939年由漫徹斯特大學物理學家、英國戰斗機司令部顧問、戰后獲得諾貝爾獎金的P。M。S。Blackett為首，組織了一個小組，代號“Blackett馬戲團”。這個小組包括三名心理學家、兩名數學家、兩名應用數學家、一名天文物理學家、一名普通

3、物理學家、一名海軍軍官、一名陸軍軍官、一名測量員。研究的問題是：設計將雷達信息傳送到指揮系統和武器系統的最佳方式；雷達與武器的最佳配置；對探測、信息傳遞、作戰指揮、戰斗機與武器的協調，作了系統的研究，并獲得成功。“Blackett馬戲團”在秘密報告中使用了“Operational Research”，即“運籌學”。2021-6-19 浙江理工大學經管學院周曉林浙江理工大學經管學院周曉林5護衛艦系統護衛艦系統2021-6-19 浙江理工大學經管學院周曉林浙江理工大學經管學院周曉林6 在生產管理方面的應用，最早是1939年前蘇聯的康特洛為奇提出了生產組織與計劃中的線性規劃問題，并給出解乘數法的求解

4、方法，出版了第一部關于線性規劃的著作生產組織與計劃中的數學方法。 但當時并沒有引起重視，直到1960年康特洛為奇再次出版了最佳資源利用的經濟計算，才受到國內外的一致重視，為此康特洛為奇獲得了諾貝爾經濟學獎（1975）。 線性規劃提出后很快受到經濟學家的重視，如二次世界大戰中從事運輸模型研究的美國經濟學家庫普曼斯（T.C.Koopmans），他很快看到了線性規劃在經濟中應用的意義，并呼吁年輕的經濟學家要關注線性規劃。其中阿羅、薩謬爾遜、西蒙、多夫曼和胡爾威茨等都獲得了諾貝爾獎。2021-6-19 浙江理工大學經管學院周曉林浙江理工大學經管學院周曉林72021-6-19 浙江理工大學經管學院周曉林

5、浙江理工大學經管學院周曉林8 50年代中期，錢學森、許國志等教授在國內全面介紹和推廣運籌學知識，1956年，中國科學院成立第一個運籌學研究室，1957年運籌學運用到建筑和紡織業中，1958年提出了圖上作業法，山東大學的管梅谷教授提出了“中國郵遞員問題”，1970年，在華羅庚教授的直接指導下，在全國范圍內推廣統籌方法和優選法。 在中國，最早的運籌學思想有戰國時期的田忌賽馬，它是對策論的一個典型例子，北宋時期的丁渭造皇宮，它是統籌規劃的一個例子。2021-6-19 浙江理工大學經管學院周曉林浙江理工大學經管學院周曉林9三、運籌學的基本內容三、運籌學的基本內容1、線性規劃（Linear Progra

6、m）是一個成熟的分支，它有效的算法單純形法，主要解決生產計劃問題，合理下料問題，最優投資問題。2、整數規劃(Integrate Program)：在線性規劃的基礎上，變量加上整數約束3、非線性規劃(Nonlinear Program)：目標函數和約束條件是非線性函數，如證券投資組合優化:如何合理投資使風險最小。4、動態規劃(Dynamic Program):多階段決策問題。是美國貝爾曼于1951年提出的。5、圖與網絡(Graph Theory and Network)：中國郵遞員問題、哥尼斯堡城問題、最短路、最大流問題。2021-6-19 浙江理工大學經管學院周曉林浙江理工大學經管學院周曉林1

7、06、存儲模型（Inventory Theory)：主要解決生產中的庫存問題，訂貨周期和訂貨量等問題。7、排隊論(Queue Theory)：主要研究排隊系統中的系統排隊和系統擁擠現象，從而評估系統的服務質量。8、對策論(Game Theory)：主要研究具有斗爭性質的優化問題。9、決策分析(Decision Analysis) ：主要研究定量化決策三、運籌學的工作步驟1、明確目標、收集資料、提出問題2、建立模型3、模型求解與檢驗4、結果分析與實施2021-6-19 浙江理工大學經管學院周曉林浙江理工大學經管學院周曉林112021-6-19 浙江理工大學經管學院周曉林浙江理工大學經管學院周曉林

8、12解：將一個實際問題轉化為線性規劃模型有以下幾個步驟：1確定決策變量：x1=生產甲產品的數量 x2=生產乙產品的數量2確定目標函數：工廠的目標是總利潤最大 max z=1500 x1+2500 x23確定約束條件： 3x1+2x265（A資源的限制） 2x1+ x2 40（B資源的限制） 3x2 75（C資源的限制）4變量取值限制： 一般情況，決策變量只取正值（非負值） x1 0, x2 0 2021-6-19 浙江理工大學經管學院周曉林浙江理工大學經管學院周曉林133x2 752021-6-19 浙江理工大學經管學院周曉林浙江理工大學經管學院周曉林142021-6-19 浙江理工大學經管學

9、院周曉林浙江理工大學經管學院周曉林15方方 案案 2.9m 2.1m 1.5m 合合 計計 余余 料料 1 2 0 1 7.3 0.1 2 1 2 0 7.1 0.3 3 1 1 1 6.5 0.9 4 1 0 3 7.4 0 5 0 3 0 6.3 1.1 6 0 2 2 7.2 0.2 7 0 1 3 6.6 0.8 8 0 0 4 6.0 1.4 2021-6-19 浙江理工大學經管學院周曉林浙江理工大學經管學院周曉林16技技術術系系數數右右端端項項價價值值系系數數線線性性規規劃劃問問題題的的規規模模約約束束行行數數變變量量個個數數: ;: ;: ;: ;:0,),(),(),(.)(m

10、ax(min)21221122222121112121112211ijjjnmnmnmmnnnnnnabcmnmnxxxbxaxaxabxaxaxabxaxaxatsxcxcxcxf一般表示形式：一般表示形式：2021-6-19 浙江理工大學經管學院周曉林浙江理工大學經管學院周曉林17njxmibxatsxcxfjinjjijnjjj, 2 , 1 , 0, 2 , 1 ,.)(max11其他常用表示形式：其他常用表示形式：2021-6-19 浙江理工大學經管學院周曉林浙江理工大學經管學院周曉林18 ),(),();,(.)(max212121212222111211TmTnnmnmmnnbb

11、bbxxxXcccCaaaaaaaaaA0XbAXtsCXxf2021-6-19 浙江理工大學經管學院周曉林浙江理工大學經管學院周曉林190000 ),( );,( .)(max210212121010bbbbaaaPxxxXcccC0XbxPtsCXxfmmjjjjTnnnjjj2021-6-19 浙江理工大學經管學院周曉林浙江理工大學經管學院周曉林20njijijbxa1njxmibxatsxcxfjinjjijnjjj,2, 1 ),0(0,2, 1 ,),(.)(max(min)11不不限限這可是這可是個重點個重點哦！哦！njjjxcz1max21b, xj0(j=12n)432021

12、-6-19 浙江理工大學經管學院周曉林浙江理工大學經管學院周曉林211Max zMin zab注意：z與z的解相同但目標函數值相差一負號 z z2021-6-19 浙江理工大學經管學院周曉林浙江理工大學經管學院周曉林22l 第第i i 個約束的個約束的b bi i 為負值，則該行左右兩端系數同時反號，同為負值，則該行左右兩端系數同時反號，同時不等號也要反向時不等號也要反向lExample: Example: 4 4=-6 - =-6 - 4 4= 6= 6l 第第i i 個約束為個約束為 型，在不等式左邊增加一個非負的變量型，在不等式左邊增加一個非負的變量x xn+in+i ，稱為松弛變量；同

13、時令稱為松弛變量；同時令 c cn+in+i = 0= 0lExample: Example: -2-2 9 9 -2-2=9=9l 第第i i 個約束為個約束為 型，在不等式左邊減去一個非負的變量型，在不等式左邊減去一個非負的變量x xn+in+i ，稱為剩余變量；同時令稱為剩余變量；同時令 c cn+in+i = 0= 0lExample: Example: -3-3 4 4 -3-3=4=4l 若若x xj j 0 0，令，令 x xj j= -= -x xj j ，代入非標準型，則有，代入非標準型，則有x xj j 0 0l若若x xj j 不限，令不限，令 x xj j= = x x

14、j j - - x xj j ， x xj j 0 0，x xj j 0 0，代入非標準代入非標準型型2342021-6-19 浙江理工大學經管學院周曉林浙江理工大學經管學院周曉林230, ,20040065300432.423)(min:213321321321321xxxxxxxxxxxxtsxxxxf不限不限原非標準型原非標準型 0,2004006653004432.0004423)(max:65433216332153321433216543321xxxxxxxxxxxxxxxxxxxxxxtsxxxxxxxxf標準型標準型2021-6-19 浙江理工大學經管學院周曉林浙江理工大學經管

15、學院周曉林2450403020103040 x1 2 線性規劃的圖解法線性規劃的圖解法3x2 75504030201010203040 x150等值線等值線B1 可行解可行解2 最優解最優解2021-6-19 浙江理工大學經管學院周曉林浙江理工大學經管學院周曉林252021-6-19 浙江理工大學經管學院周曉林浙江理工大學經管學院周曉林263 線性規劃問題解的基本性質線性規劃問題解的基本性質2021-6-19 浙江理工大學經管學院周曉林浙江理工大學經管學院周曉林272021-6-19 浙江理工大學經管學院周曉林浙江理工大學經管學院周曉林28線性規劃的線性規劃的基矩陣基矩陣、基變量基變量、非基變

16、量非基變量=目標函數約束條件行列式0基矩陣右邊常數2021-6-19 浙江理工大學經管學院周曉林浙江理工大學經管學院周曉林29012233. .23max321432143214xxxxxxxxtsxxxxz000032020001010 x1x2x4x3001300321=目標函數約束條件行列式0基矩陣X1,x2,x3為基變量為基變量,x4為非基變量為非基變量2021-6-19 浙江理工大學經管學院周曉林浙江理工大學經管學院周曉林302021-6-19 浙江理工大學經管學院周曉林浙江理工大學經管學院周曉林31約束方程的約束方程的解空間解空間基解基解可行解可行解非可行解非可行解基可基可行解行解

17、退化解退化解2021-6-19 浙江理工大學經管學院周曉林浙江理工大學經管學院周曉林320,78102.46)(max212212121xxxxxxxtsxxxf 可行解、基解和基本可行解舉例可行解、基解和基本可行解舉例 系數矩陣系數矩陣:A=21 1 0 01 1 0 1 00 1 0 0 10,78102. .46)(max543215242132121xxxxxxxxxxxxxtsxxxf：標準型x1 x2 x3 x4 x52021-6-19 浙江理工大學經管學院周曉林浙江理工大學經管學院周曉林33 可行解、基解和基本可行解舉例可行解、基解和基本可行解舉例 系數矩陣系數矩陣:A=21 1

18、 0 01 1 0 1 00 1 0 0 1x1 x2 x3 x4 x5 1 0 0 0 1 0 0 0 1 B=x3 x4 x5 2 1 1 1 0 0 x1 x2 N=A=(B,N)令非基變量令非基變量X1=0,X2=0得得X3=10,X4=8,X5=7,因此可得一基本解因此可得一基本解X=(0,0,10,8,7)T2021-6-19 浙江理工大學經管學院周曉林浙江理工大學經管學院周曉林341187654322x1876543O109x2A BCEDFGH123f(x)=36K2021-6-19 浙江理工大學經管學院周曉林浙江理工大學經管學院周曉林35二、線性規劃問題解的基本性質二、線性規

19、劃問題解的基本性質（一）幾個基本概念（一）幾個基本概念2021-6-19 浙江理工大學經管學院周曉林浙江理工大學經管學院周曉林36 。3、頂點：、頂點：設S是凸集, 若S中的點x 不能成為S中任何線段上的內點，則稱x為凸集S的頂點。即：若S中的任意兩點x(1),x(2) ，不存在數 （0 = 0 i = 1 , , m Max 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

20、 ， ，xn 0此時若系數矩陣中無單位矩陣，則可以引入人工變量。2021-6-19 浙江理工大學經管學院周曉林浙江理工大學經管學院周曉林63Max z = c1 x1 + c2 x2 + + cn xn s.t. a11 x1 + a12 x2 + + a1n xn + xn+1 = b1 a21 x1 + a22 x2 + + a2n xn + xn+2 = b2 am1 x1 + am2 x2 + + amn xn + xn+m = bm x1 ，x2 ， ，xn 0此時人工變量xn+1 、 xn+2 、. xn+m 的系數向量構成一個m*m的單位矩陣，因此可以作為初始可行基。但是但是20

21、21-6-19 浙江理工大學經管學院周曉林浙江理工大學經管學院周曉林642021-6-19 浙江理工大學經管學院周曉林浙江理工大學經管學院周曉林65s.t. a11x1 + a12x2 + a1nxn + xn+1 = b a21x1 + a22x2 + a2nxn + xn+2 = b2 am1x1 + am2x2 + amnxn + xn+m = bm xj0 （j = 1,2, n, n+1, n+m） Max w = c1 x1 + c2 x2 + + cn xn -M(xn+1 + xn+2 + xn+m )1、大、大M法法2021-6-19 浙江理工大學經管學院周曉林浙江理工大學經

22、管學院周曉林66 max z = 3x1 - x2 - x3s.t. x1 - 2x2 + x3 11 -4x1 + x2 + 2x3 3 -2x1 + x3 = 1 x1, x2, x30 max w = 3x1 - x2 - x3 + 0 x4 + 0 x5 Mx6 Mx7s.t. x1 - 2x2 + x3 +x4 =11 -4x1 + x2 + 2x3 x5 + x6 =3 2x1 + x3 +x7 =1 xj0 （j = 1,2,7） 2021-6-19 浙江理工大學經管學院周曉林浙江理工大學經管學院周曉林67 表1 -9 c 3 - 1 - 1 0 0 - M - M 序 號 cB

23、 xB x1 x2 x3 x4 x5 x6 x7 b 0 - M - M x4 x6 x7 1 - 4 - 2 - 2 1 0 1 2 1* 1 0 0 0 - 1 0 0 1 0 0 0 1 1 1 3 1 檢 驗 數 3 - 6 M - 1 + M - 1 + 3 M 0 - M 0 0 4 M 0 - M - 1 x4 x6 x3 3 0 - 2 - 2 1* 0 0 0 1 1 0 0 0 - 1 0 0 1 0 - 1 - 2 1 1 0 1 1 檢 驗 數 1 - 1 + M 0 0 - M 0 1 -3 M 1 + M 0 - 1 - 1 x4 x2 x3 3* 0 - 2 0

24、1 0 0 0 1 1 0 0 - 2 - 1 0 2 1 0 - 5 - 2 1 1 2 1 1 檢 驗 數 1 0 0 0 -1 1 -M - 1 - M 2 3 - 1 - 1 x1 x2 x3 1 0 0 0 1 0 0 0 1 1 /3 0 2 /3 - 2 /3 - 1 - 4 /3 2 /3 1 4 /3 - 5 /3 - 2 - 7 /3 4 1 9 檢 驗 數 0 0 0 - 1 /3 - 1 /3 1 /3 - M 2 /3 - M - 2 See you next time!See you next time!2021-6-19 浙江理工大學經管學院周曉林浙江理工大學經管學院周曉林682021-6-19 浙江理工大學經管學院周曉林浙江理工大學經管學院周曉林69不不是是人人工工變變量量時時當當為為人人工工變變量量時時當當時時目目標標函函數數為為不不是是人人工工變變量量時時當當為為人人工工變變量量時時當當時時目目標標函函數數為為jjjjjjjjxcxcxcxc01max01min2021-6-19 浙江理工大學經管學院周曉林浙江理工大學經管學院周曉林70 max z = 3x1 - x2 - x3s.t. x1 - 2x2 + x3 11 -4x1 + x