運籌學

OperationalResearch運籌帷幄，決勝千里史記?張良傳?桂林理工大學理學院賈貞1精選課件緒論一、運籌學開展簡介二、運籌學的特點及研究對象三、運籌學的工作步驟四、運籌學內(nèi)容介紹2精選課件一、運籌學〔OR〕開展簡介運籌學在國外英國稱為OperationalResearch美國稱為OperationsResearch起源于二戰(zhàn)期間的軍事問題，如雷達的設(shè)置、運輸船隊的護航艦隊的規(guī)模、反潛作戰(zhàn)中深水炸彈的深度、飛機出擊隊型、軍事物資的存儲等。二戰(zhàn)以后運籌學應(yīng)用于經(jīng)濟管理領(lǐng)域〔LP、計算機〕1948年英國首先成立運籌學會；1952年美國成立運籌學會。1952年，Morse和Kimball出版?運籌學方法?1959年成立國際運籌學聯(lián)合會3精選課件

運籌學在國內(nèi)中國古代樸素的運籌學思想〔田忌賽馬、都江堰工程、丁渭修復皇宮〕1956年中科院成立運籌學小組1957年正式將OperationsResearch命名為“運籌學〞1958年提出運輸問題的圖上作業(yè)法〔解決糧食合理運輸問題〕1962年提出中國郵路問題〔管梅谷〕1964年華羅庚推廣統(tǒng)籌方法1980年中國運籌學學會正式成立1982年中國參加國際運籌學聯(lián)合會1999年8月我國組織了第15屆大會4精選課件＊齊王賽馬〔齊王和田忌〕戰(zhàn)國時期，齊威王與田忌賽馬，規(guī)定雙方各出上中下三個等級的馬各一匹。如果按同等級的馬比賽，齊王可獲全勝。田忌的謀士孫臏提出的以下、上、中對齊王的上、中、下對策，使處于劣勢的田忌戰(zhàn)勝齊王，這是從總體出發(fā)制定對抗策略的一個著名事例。5精選課件丁渭主持皇宮的修復〔北宋，皇宮因火焚毀〕北宋真宗年間，皇城失火，宮殿燒毀，大臣丁謂主持了皇宮修復工程。他采用了一套綜合施工方案:①先在需要重建的大道上就近取土燒磚；②在取土后的深溝中引水，形成人工河，再由此水路運入建筑材料，從而加快了工程進度；③皇宮修復后，又將碎磚廢土填入溝中，重修大道。使燒磚、運輸建筑材料和處理廢墟三項繁重工程任務(wù)協(xié)調(diào)起來，從而在總體上得到了最正確解決，一舉三得，節(jié)省了大量勞力、費用和時間。6精選課件運籌學為決策機構(gòu)對所控制的業(yè)務(wù)活動作決策時，提供以數(shù)量為根底的科學方法——Morse和Kimball運籌學是把科學方法應(yīng)用在指導人員、工商企業(yè)、政府和國防等方面解決發(fā)生的各種問題，其方法是開展一個科學的系統(tǒng)模式，并運用這種模式預測、比較各種決策及其產(chǎn)生的后果，以幫助主管人員科學地決定工作方針和政策——英國運籌學會運籌學是應(yīng)用分析、試驗、量化的方法對經(jīng)濟管理系統(tǒng)中人力、物力、財力等資源進行統(tǒng)籌安排，為決策者提供有根據(jù)的最優(yōu)方案，以實現(xiàn)最有效的管理——中國百科全書現(xiàn)代運籌學涵蓋了一切領(lǐng)域的管理與優(yōu)化問題，稱為ManagementScience運籌學的定義二、運籌學的特點及研究對象7精選課件運籌學的特點：優(yōu)化：從全局觀點看問題，追求總體效果最優(yōu)量化：通過建立和求解模型使問題在量化的根底上得到合理決策綜合：多學科交叉運籌學的研究對象：生產(chǎn)與經(jīng)濟等各種實踐活動中提出來的實際問題二、運籌學的特點及研究對象8精選課件三、運籌學的工作步驟明確問題建立模型設(shè)計算法整理數(shù)據(jù)求解模型評價結(jié)果簡化？滿意？YesNoNo明確問題建立模型設(shè)計算法整理數(shù)據(jù)求解模型評價結(jié)果9精選課件四、運籌學內(nèi)容介紹線性規(guī)劃及單純形法對偶理論及靈敏度分析運輸問題整數(shù)規(guī)劃動態(tài)規(guī)劃圖與網(wǎng)絡(luò)分析

10精選課件第一章線性規(guī)劃及單純形法1939年蘇康托洛維奇發(fā)表“生產(chǎn)組織與方案中的數(shù)學方法〞，1960年出版“最正確資源利用的經(jīng)濟計算〞獲諾貝爾經(jīng)濟學獎1941年美Hichcock提出運輸問題1947年美丹捷格〔G.B.Dantzig〕提出單純形法，1963年出版“線性規(guī)劃及其擴展〞

在生產(chǎn)管理中如何有效地利用現(xiàn)有人力、物力完成更多的任務(wù)，或在預定的任務(wù)目標下，如何耗用最少的人力、物力去實現(xiàn)目標。11精選課件第一節(jié)線性規(guī)劃問題及數(shù)學模型例1生產(chǎn)方案問題(P4)

III資源限量設(shè)備128臺時原材料A4016公斤原材料B0412公斤單位利潤23設(shè)I、II兩種產(chǎn)品的產(chǎn)量分別為x1,x2。建立該問題的數(shù)學模型為：目標函數(shù)約束條件決策變量一、實例12精選課件例2合理下料問題

現(xiàn)要做100套鋼架，每套需2.9米、2.1米和1.5米的圓鋼各一根。原料長7.4米，問如何下料，使用的原料最少〔余料最少或根數(shù)最少〕？解：設(shè)x1,x2,x3,x4,x5分別代表五種不同的原料用量方案〔余料最少〕13精選課件方案2.9米2.1米1.5米合計余料x11037.40x22017.30.1x30227.20.2x41207.10.3x50136.60.8決策變量？目標函數(shù)？特點？約束條件？決策方案？最優(yōu)方案？最優(yōu)值？14精選課件二、總結(jié)目標函數(shù)用決策變量的線性函數(shù)來表示。按問題的不同，要求目標函數(shù)實現(xiàn)最大化和最小化。線性規(guī)劃問題〔LP問題〕的共同特征：每一個問題變量都用一組決策變量〔x1,x2,…,xn〕表示某一方案，這組決策變量的值代表一個具體方案，這些變量是非負的。存在一定的約束條件，這些約束條件可以用一組線性等式或線性不等式來表示。線性規(guī)劃模型的一般形式與標準形式〔P7稍后講〕15精選課件三、兩變量線性規(guī)劃問題的圖解法1.線性不等式的幾何意義—半平面作出LP問題的可行域作出目標函數(shù)的等值線移動等值線到可行域邊界得到最優(yōu)點2.圖解法步驟16精選課件4x1=164x2=12x1+2x2=8x1x248430例1〔書P4〕：Q(4,2)Z=2x1+3x2做目標函數(shù)2x1+3x2的等值線，與陰影局部的邊界相交于Q(4,2)點，說明最優(yōu)生產(chǎn)方案為：生產(chǎn)I產(chǎn)品4件，生產(chǎn)II產(chǎn)品2件。最大利潤：14.根本概念：可行解、可行域、最優(yōu)解？17精選課件例2Z=3618精選課件3.圖解法的作用能解決少量問題LP問題有可行解有最優(yōu)解唯一解無窮多解無最優(yōu)解〔可行域為無界〕無可行解〔無解〕規(guī)律1：揭示了線性規(guī)劃問題的假設(shè)干規(guī)律見P9-10例題19精選課件結(jié)論：假設(shè)LP問題有最優(yōu)解，那么要么最優(yōu)解唯一，要么有無窮多最優(yōu)解。★20精選課件

規(guī)律2：線性規(guī)劃問題的可行域為一凸集線性規(guī)劃問題凸集的頂點個數(shù)是有限的最優(yōu)解肯定可在凸集的某頂點處到達21精選課件四、線性規(guī)劃問題的標準型1.一般形式22精選課件2.標準型LP模型的各種表示法見P723精選課件3.所有LP問題均可化為標準型1.目標函數(shù)最大化2.約束條件為等式3.變量約束為非負4.約束右端項非負24精選課件例1可化為25精選課件例2化標準型26精選課件課堂作業(yè)27精選課件五、標準型LP問題的解LP模型向量表示法見P728精選課件29精選課件令B==(P1,P2,…,Pm)且|B|0，稱A中基B對應(yīng)的列向量Pj(j=1,2,…,m)

為基向量。與基向量Pj對應(yīng)的變量xj稱為基變量，記為XB=(x1,x2,…,xm)T，其余的變量稱為非基變量，記為XN=(xm+1,xm+2,…,xm+n)T。基變量：30精選課件根本解令非基變量XN=0，求得的一組基變量XB的值稱為根本解。基可行解〔頂點〕既是根本解，又是可行解。基最優(yōu)點既是根本解，又是使目標函數(shù)值到達最優(yōu)的解31精選課件如引例中：

基基變量非基變量根本解是否可行目標函數(shù)值ZB1x1,x2x3,x4〔-2，3，0，0〕否B2x1,x3x2,x4〔3，0，1，0〕是Z=3B3x1,x4x2,x3〔4，0，0，-3〕否B4x2,x3x1,x4〔0，9/5，2/5，0〕是Z=9/5B5x1,x4x2,x3〔2，0，0，-1〕否B3x3,x4x1,x2〔0，0，4，9〕是Z=032精選課件

線性規(guī)劃標準型問題解的關(guān)系約束方程的解空間基解可行解非可行解基可行解LP解的根本定理見P1233精選課件第二節(jié)單純型法

一、根本思想化LP問題為標準型，確定一個初始根本可行解檢驗解的最優(yōu)性結(jié)束Y樞軸運算〔旋轉(zhuǎn)運算〕確定另一個根本可行解N34精選課件二、樞軸運算35精選課件又如：36精選課件三、檢驗數(shù)的意義P1737精選課件四、單純形表基變量非基變量常數(shù)項約束方程增廣矩陣檢驗數(shù)+目標函數(shù)值P1738精選課件第三節(jié)單純型法的步驟一、步驟化LP問題為標準型,建立初始單純型表;直接求最小化問題，P23說明39精選課件二、用單純形表求解LP問題實例化為標準型例1.40精選課件單純型表

算法步驟：Cj23000

CBXBbX1X2X3X4X50X30X40X58161212100440010-0[4]0013023000以[4]為樞軸元素進行旋轉(zhuǎn)運算，x2為換入變量，x5為換出變量Cj23000

CBXBbX1X2X3X4X50X30X43X22163[1]010-1/2240010401001/4--92000-3/4以[1]為樞軸元素進行運算，x1為換入變量，x3為換出變量〔1〕建立初始單純形表；〔2〕求檢驗數(shù)并判斷最優(yōu)性，假設(shè)最優(yōu)，終止，否那么轉(zhuǎn)下一步；〔3〕確定出基與進基變量；〔4〕換基迭代，轉(zhuǎn)入〔2〕。41精選課件Cj23000

CBXBbX1X2X3X4X52X10X43X22831010-1/2-00-41[2]401001/412-1300-201/4以[2]為樞軸元素進行運算，x5為換入變量，x4為換出變量Cj23000

CBXBbX1X2X3X4X52X10X53X24421001/4000-21/21011/2-1/80-1400-3/2-1/80此時到達最優(yōu)解。X*=(4,2),MaxZ=14。42精選課件例243精選課件解:化標準型44精選課件

21000

01505100

0

24620100511001

21000

—24/65/1主元化為1主列單位向量換出換入表1：列初始單純形表〔單位矩陣對應(yīng)的變量為基變量〕正檢驗數(shù)中最大者對應(yīng)的列為主列最小的值對應(yīng)的行為主行45精選課件

21000

01505100

2

412/601/600104/60-1/61

01/30-1/30

15/524/26/4

0*52*2/6+0*4/61-2/3=表2：換基〔初等行變換，主列化為單位向量，主元為1〕檢驗數(shù)>0確定主列最小確定主列主元46精選課件

21000

015/20015/4-15/2

2

7/21001/4-1/213/2010-1/43/2000-1/4-1/2

檢驗數(shù)<=0最優(yōu)解為X=(7/2,3/2,15/2,0,0)目標函數(shù)值Z=8.5

2*7/21*3/2+0*15/28.5表3：換基〔初等行變換，主列化為單位向量，主元為1〕47精選課件

21000

01505100

0

24620100511001

21000練習:一般主列選擇正檢驗數(shù)中最大者對應(yīng)的列,也可選擇其它正檢驗數(shù)的列.以第2列為主列,用單純形法求解。正檢驗數(shù)對應(yīng)的列為主列注：1.幾種特殊情形P20-23；2.對于極小化的LP問題，只須改成檢驗數(shù)≥0為最優(yōu)。48精選課件第四節(jié)LP問題的進一步討論一、人工變量法49精選課件1.大M法(M為任意大的正數(shù))參加松弛變量x4;剩余變量x5;人工變量x6,x750精選課件1)人工變量的識別2)目標函數(shù)的處理3)計算(單純型法)51精選課件Cj-31100MMCBXBbx1x2x3x4x5x6x70x4111-21100011Mx63-4120-1103/2Mx71-20100011-3+6M1-M1-3M0M000x4103-20100-1-Mx610100-11-211x31-2010001--11-M00M03M-1注意：本例是求最小值，所以用所有來判別目標函數(shù)是否實現(xiàn)了最小化。因而換入變量xk的選取標準為52精選課件結(jié)果得:X*=(4,1,9,0,0,0,0)Z*=2Cj-31100MMCBXBbx1x2x3x4x5x6x70x4123001-22-541x210100-11-2-1x31-2010001--10001M-1M+1-3x141001/3-2/32/3-5/31x210100-11-21x390012/3-4/34/3-7/30001/31/3M-1/3M-2/3〔接上表〕53精選課件兩階段法(將LP問題分成兩個階段來考慮)第I階段:求解模型〔1〕得到原問題的一個根本可行解。做法是：先不考慮原問題是否存在可行解，給原LP問題參加人工變量，并構(gòu)造僅含人工變量之和的目標函數(shù)w并要求最小化；然后用單純型法求解，假設(shè)得w=0，那么求得原問題的一個根本可行解，進行第二階段計算，否那么無可行解。54精選課件第II階段：求解模型〔2〕得到原LP問題的最優(yōu)解。做法是：將第一階段得到的最終表除去人工變量，將目標函數(shù)行的系數(shù)換為原問題的系數(shù)，作為第二階段的初始表。解的理論見：P24命題1.5.1，1.5.255精選課件參加松弛變量x4;剩余變量x5;人工變量x6,x7用單純形法求解第一階段的結(jié)果得：56精選課件Cj0000011CBXBbx1x2x3x4x5x6x70x4111-211000111x63-4120-1103/21x71-201000116-1-301000x4103-20100-1-1x610100-11-210x31-2010001-0-1001030x4123001-22-540x210100-11-2-0x31-2010000-0000011此時，到達第一階段的最優(yōu)解，W=057精選課件Cj-31100CBXBbx1x2x3x4x50x4123001-241x210100-1-1x31-20100--10001-3x141001/3-2/31x210100-11x390012/3-4/30001/31/3由于人工變量x6=x7=0,所以〔0,1,1,12,0〕T是該線性規(guī)劃問題的基可行解。于是轉(zhuǎn)入第二階段運算：此時到達該LP問題的最優(yōu)解：x1=4,x2=1,x3=9;目標函數(shù)值Z=-2。58精選課件二、單純型法中存在的問題1.存在兩個以上的最大正檢驗數(shù)。選擇任何變量〔對應(yīng)最大正檢驗數(shù)〕作為進基變量。2.最小比值相同。LP問題出現(xiàn)退化現(xiàn)象，即基變量取值為0★59精選課件Cj3/4-201/2-6000CBXBbX1X2X3X4X5X6X70X501/4-8-191000X601/2-12-1/230100X71001000103/4-201/2-600060精選課件Cj3/4-201/2-6000CBXBbX1X2X3X4X5X6X73/4X101-32-4364000X60043/2-150100X7100100010047/221-300選取x1為換入變量；按Bland算法，選取下標最小的x5為換出變量，得下表：此時換出變量為x1，換入變量為x4，迭代后目標函數(shù)值不變，繼而出現(xiàn)了循環(huán)現(xiàn)象，達不到最優(yōu)解。Cj3/4-201/2-6000CBXBbX1X2X3X4X5X6X73/4X101-32-4364000X60043/2-150100X7100100010047/221-30061精選課件解決退化的方法有：“攝動法〞、“辭典序法〞、Bland規(guī)那么等1974年Bland提出Bland算法規(guī)那么：62精選課件3.最小比值原那么失效Cj2300CBXBbX1X2X3X40X36-20113X24-3101Cj-Zj-121100-3經(jīng)過一次迭代后可得右表★63精選課件4.在最優(yōu)表中出現(xiàn)某非基變量檢驗數(shù)為064精選課件CBXBbX1X2X3X4X50X340012/3-1/34X260101/203X14100-2/31/3Cj-Zj-360000-10X46003/21-1/24X2301-3/401/43X1810100Cj-Zj-360000-1Cj-Zj034000結(jié)論：假設(shè)線性規(guī)劃問題存在某非基變量檢驗數(shù)為0,而其對應(yīng)列向量ak≤0,仍可判斷線性規(guī)劃問題有無窮多最優(yōu)解。任一個LP問題最優(yōu)解都可表示成其根本最優(yōu)解的凸組合加上其凸方向的線性組合.65精選課件第五節(jié)應(yīng)用舉例例1某工廠要用三種原材料C、P、H混合調(diào)配出三種不同規(guī)格的產(chǎn)品A、B、D。產(chǎn)品的規(guī)格要求、單價和原材料的供給量、單價。該廠應(yīng)如何安排生產(chǎn)使利潤最大？產(chǎn)品名稱規(guī)格要求單價