運籌學(xué) 第一二章-引言+線性規(guī)劃

《運籌學(xué)》任課教師：郵箱：@163.com手機：1引言1.1“運籌”的含義最早出自《史記·高祖本紀》：“夫運籌帷幄之中，決勝千里之外，吾不如子房?！爆F(xiàn)代含義：運籌是對資源進行統(tǒng)籌安排，決策者進行決策提供最優(yōu)解決方案，以達到最有效的管理。古代典故：齊王賽馬，丁謂修皇宮，沈括運糧。1引言1.2《運籌學(xué)》的由來與發(fā)展起源于20世紀30年代二戰(zhàn)時期，當時由數(shù)學(xué)、軍事領(lǐng)域技術(shù)人員組成的小組，有效的解決了雷達布局、反潛深水炸彈爆炸深度、大小船只逃避轟炸等軍事問題。20世紀40-50年代，戰(zhàn)爭期間研究數(shù)據(jù)逐漸公開。1951年P(guān).M.Morse和G.E.Kimball書寫的《運籌學(xué)方法》著作問世。1引言1.2《運籌學(xué)》的由來與發(fā)展20世紀50年代開始，各國陸續(xù)成立運籌學(xué)會，英國1948、美國1952、法國1956、中國1980。英國OperationalResearch，美國OperationsResearch，簡稱OR，是當前管理科學(xué)領(lǐng)域的主要基礎(chǔ)理論課程。1引言1.2《運籌學(xué)》的由來與發(fā)展運籌學(xué)在中國的發(fā)展1956年錢學(xué)森和許國志在中國科學(xué)院力學(xué)所成立第1個運籌學(xué)小組；1959年大躍進時期在中國科學(xué)院數(shù)學(xué)所成立第2個運籌學(xué)研究部門；1960年兩個部門合并；1963年在中國科學(xué)技術(shù)大學(xué)開設(shè)《運籌學(xué)》課程；1965年開始，“華羅庚小分隊”走遍20多個省，使“優(yōu)選法”“統(tǒng)籌法”廣為流傳；（打麥場選址、中國郵遞員問題）1980年成立運籌學(xué)學(xué)會（系統(tǒng)工程學(xué)會、管理科學(xué)學(xué)會）。1引言1.3《運籌學(xué)》的應(yīng)用目前運籌學(xué)以被廣泛的應(yīng)用到：生產(chǎn)計劃、庫存管理、運輸問題、財政和會計、工程優(yōu)化與設(shè)計等眾多領(lǐng)域。運籌學(xué)研究領(lǐng)域重要獎項：①INFORMSFranzEdelman獎，1972年開始每年選擇一個運籌學(xué)領(lǐng)域的杰出應(yīng)用成果授獎。/Recognize-Excellence/Franz-Edelman-Award獲獎華人：于剛2002年。②INFORMSJohnvonNeumannTheoryPrize自1975年每年1-2人/Recognize-Excellence/INFORMS-Prizes-Awards/John-von-Neumann-Theory-Prize獲獎華人：葉蔭宇2009年本章小結(jié)運籌學(xué)是在實行管理的領(lǐng)域，運用數(shù)學(xué)方法，對需要進行管理的問題統(tǒng)籌規(guī)劃，作出決策的一門應(yīng)用科學(xué)。運籌學(xué)其他定義：主要研究人類對各種資源的運用及籌劃活動，以期通過了解和發(fā)展這種運用及籌劃活動的基本規(guī)律，發(fā)揮有限資源的最大效益，達到總體最優(yōu)的目標。當前《運籌學(xué)》已成為管理類、工業(yè)工程類等專業(yè)的重要基礎(chǔ)課程。2線性規(guī)劃和單純性法2.1模型的構(gòu)建（1）生產(chǎn)計劃問題例題1：某工廠在計劃期內(nèi)要安排生產(chǎn)I，II兩種產(chǎn)品，已知生產(chǎn)單位產(chǎn)品所需要的設(shè)備臺時和A、B兩種原材料的消耗，如表所示。該工廠每生產(chǎn)一件產(chǎn)品I可獲利2元，II可獲利3元，問如何安排生產(chǎn)計劃使該工廠獲利最多？產(chǎn)品I產(chǎn)品II現(xiàn)有資源量設(shè)備128臺時原材料A4016kg原材料B0412kg2線性規(guī)劃和單純性法2.1模型的構(gòu)建建模的思路：a設(shè)立決策變量；b構(gòu)建目標函數(shù)；c構(gòu)建約束條件。本問題模型：決策變量：表示生產(chǎn)產(chǎn)品I的數(shù)量；表示生產(chǎn)產(chǎn)品II的數(shù)量；目標函數(shù)：約束條件：約束條件Part1：條件約束約束條件Part2：非負約束目標函數(shù)z的優(yōu)化方向，Max表示越大越好，反之Min，全稱Maximize，Minimize。2線性規(guī)劃和單純性法2.1模型的構(gòu)建污水處理問題例題2：已知工廠1和工廠2同屬某企業(yè)集團，且工廠1和2日排污水量分別為2萬立方米和1.4萬立方米，環(huán)保要求污水含量不超過0.2%，工廠1的污水流至工廠2可以自然凈化20%，工廠1和2處理污水成本分別為1000元/萬立方米和800元/萬立方米，請問工廠1和2應(yīng)各處理多少污水，使總成本最低。工廠1工廠2500萬立方米200萬立方米2線性規(guī)劃和單純性法2.1模型的構(gòu)建決策變量：表示工廠1處理污水量；表示工廠2處理污水量；目標函數(shù)：約束條件：條件1工廠1處理污水后水質(zhì)達標：條件2工廠2處理污水后水質(zhì)達標：條件3決策變量和應(yīng)該滿足的條件？2線性規(guī)劃和單純性法2.1模型的構(gòu)建整理后模型：2線性規(guī)劃和單純性法2.1模型的構(gòu)建租車問題例題3：山東科技大學(xué)(青島)在2015年招生8000余人，根據(jù)預(yù)先反饋信息在2015年9月19日有4800人(包括家長和接站人員)會到達青島火車站。學(xué)校為了做好迎新工作，打算租用某公司車輛為新生接站，已知租車公司有小客車70輛，大客車40輛可供學(xué)校租用；且小客車可載16人(不包含司機)，大客車可載32人；小客車每天往返5次，大客車每天往返3次；小客車每天租金1200元，大客車每天租金1400元；請問山東科技大學(xué)應(yīng)該租用大小客車各多少輛？2線性規(guī)劃和單純性法2.1模型的構(gòu)建租車問題模型：2線性規(guī)劃和單純性法2.1模型的構(gòu)建下料問題例題4：設(shè)原材料7.4m長1根，現(xiàn)需要1.5m、2.1m、2.9m各100根，求需要的原材料根數(shù)。

12345678需求1.5m001123341002.1m321021001002.9m01120010100余料（m）01.4x1x2x3x4x5x6x7x82線性規(guī)劃和單純性法2.1模型的構(gòu)建下料問題模型：最優(yōu)方案：z=90根。其中，x2=50，x4=10，x7=30，其他決策變量均為0。2線性規(guī)劃和單純性法2.1模型的構(gòu)建項目連續(xù)投資問題例題5：某部門在今后五年內(nèi)考慮給下列項目投資，已知：設(shè)當前有資金10萬，請問如何投資這些項目，使到第5年年末擁有的資金最大？

項目投資方式本利%項目周期A第1-4年年初投資，于次年年末收回1152年B第3年年初投資，于第5年末收回，至多投資4萬1253年C第2年年初投資，于第5年末收回，至多投資3萬1404年D每年年初投資，于當年年末收回1061年2線性規(guī)劃和單純性法2.1模型的構(gòu)建設(shè)決策變量。

項目第1年初第2年初第3年初第4年初第5年初Ax1Ax2Ax3Ax4ABx3BCx2CDx1Dx2Dx3Dx4Dx5D

項目第1年初第2年初第3年初第4年初第5年初第6年初A1.15x1A1.15x2A1.15x3A1.15x4AB1.25x3BC1.4x2CD1.06x1D1.06x2D1.06x3D1.06x4D1.06x5D投資表收益表2線性規(guī)劃和單純性法2.1模型的構(gòu)建連續(xù)投資問題模型：2線性規(guī)劃和單純性法2.2圖解法（1）適用條件：模型中僅有2個決策變量的簡單模型如例題1：模型2線性規(guī)劃和單純性法2.2圖解法（2）圖解法步驟第一步：建立以x1為橫坐標軸的直角坐標系，x2為縱坐標軸；第二步：根據(jù)約束條件，在坐標系中確定可行解的集合，即可行域；第三步：根據(jù)目標函數(shù)，在可行域中找到最優(yōu)解。概念：解（方案）可分為（1）可行解（可行方案）；（2）不可行解（不可行方案）。滿足所有約束條件的解為可行解，否則為不可行解。最優(yōu)解：可行解中能夠使目標函數(shù)取得最大（或最小）值的解。2線性規(guī)劃和單純性法2.2圖解法（2）圖解法基礎(chǔ)知識直線方程，y=kx+b，其中k為斜率，b為截距；線性不等式在直角坐標系中代表的幾何含義，如y>-x+1代表什么幾何含義？xy11先畫出邊界直線y=-x+1再根據(jù)特殊點（不在邊界直線上）法，確定線性不等式代表的半個平面2線性規(guī)劃和單純性法2.2圖解法（3）例題1實例求解步驟一：建立直角坐標系；步驟二：確定可行域；步驟三：根據(jù)目標函數(shù)確定最優(yōu)解。x1x232112344(2,3)(4,2)x1+2x2=84x2=124x1=162線性規(guī)劃和單純性法2.2圖解法（4）圖解法注意問題①橫坐標軸為x1，縱坐標軸x2；②準確判斷不等式約束條件代表的半平面區(qū)域，確定可行域；③區(qū)分目標函數(shù)直線束與約束條件邊界直線的陡峭程度。如：斜率為1和2的直線，后者更陡峭；那么斜率為-1和-2的呢？注：斜率為同符號的，絕對值越大越陡峭。2線性規(guī)劃和單純性法2.2圖解法（5）圖解法的其他3種情況情況1：將例題1的模型修改如下：這種情況屬于無窮多最優(yōu)解x1x232112344(2,3)(4,2)線段上所有的點均為最優(yōu)解。2線性規(guī)劃和單純性法2.2圖解法（5）圖解法的其他3種情況情況2：圖解法求如下模型：這種情況屬于無界解x1x232112344繼續(xù)移動，目標函數(shù)可以無限制增大。2線性規(guī)劃和單純性法2.2圖解法（5）圖解法的其他3種情況情況3：圖解法求如下模型：這種情況屬于無可行解x1x232112344沒有可行域。2線性規(guī)劃和單純性法2.2圖解法（6）練習(xí)題污水處理問題模型；P55頁，2.1題（1）-（4）2線性規(guī)劃和單純性法2.3線性規(guī)劃問題的標準型（1）標準模型特點1：目標函數(shù)最大化特點2：約束條件均為等式特點3：等式右邊常數(shù)均≥0特點4：所有決策變量均≥02線性規(guī)劃和單純性法2.3線性規(guī)劃問題的標準型（2）標準模型的矩陣形式價值向量決策變量向量資源向量系數(shù)矩陣m＜n2線性規(guī)劃和單純性法2.3線性規(guī)劃問題的標準型（2）標準模型的矩陣形式2線性規(guī)劃和單純性法2.3線性規(guī)劃問題的標準型（3）非標準型模型的標準化練習(xí)P55-2.2（1）2線性規(guī)劃和單純性法2.3線性規(guī)劃問題的標準型（4）相性規(guī)劃問題的相關(guān)概念①可行解——滿足所有約束條件(包括非負約束)的解②基——是標準模型系數(shù)矩陣A中，選擇m列構(gòu)成的m階非奇異方陣，用B表示。如模型：2線性規(guī)劃和單純性法2.3線性規(guī)劃問題的標準型（4）相性規(guī)劃問題的相關(guān)概念

由于B是非奇異矩陣，所以是一個基。2線性規(guī)劃和單純性法2.3線性規(guī)劃問題的標準型（4）相性規(guī)劃問題的相關(guān)概念③基變量、非基變量基中系數(shù)列向量，對應(yīng)的變量為基變量，其他的為非基變量。因此，一個基對應(yīng)一種基變量和非基變量的劃分方式，以上基顯然，x3、x4、x5為基變量，x1，x2為非基變量。2線性規(guī)劃和單純性法2.3線性規(guī)劃問題的標準型（4）相性規(guī)劃問題的相關(guān)概念④基解、基可行解、基不可行解、可行基一個基會唯一對應(yīng)一個基解；求本基對應(yīng)的基解方式，在標準模型等式約束中，令非基變量x1，x2為0，解方程組求出所有的基變量x3、x4、x5。2線性規(guī)劃和單純性法2.3線性規(guī)劃問題的標準型（4）相性規(guī)劃問題的相關(guān)概念令非基變量x1，x2為0，解方程組求出所有的基變量x3、x4、x5。得到B對應(yīng)的一個基解由于X中所有的變量值，也滿足模型中的非負約束，因此為基可行解（此時可知B為可行基），否則為基不可行解。2線性規(guī)劃和單純性法2.3線性規(guī)劃問題的標準型（4）相性規(guī)劃問題的相關(guān)概念一個m×n的系數(shù)矩陣A，至多有多少個基？可行解、非可行解，基可行解，基不可行解的關(guān)系。練習(xí)題P55-2.3（1）（2）基可行解基不可行解可行解不可行解2線性規(guī)劃和單純性法2.3線性規(guī)劃問題的標準型（4）相性規(guī)劃問題的相關(guān)概念⑤凸集凸集的定義：如果在一個區(qū)域中（n維）的任意兩個不同點之間的連線也同屬于該區(qū)域，那么該集合為凸集。證明一個區(qū)域是凸集的方法，任取兩個不同點，證明連線上的點均屬于該區(qū)域。2線性規(guī)劃和單純性法2.3線性規(guī)劃問題的標準型（4）相性規(guī)劃問題的相關(guān)概念線性規(guī)劃模型的可行域為凸集；凸集的“角”：一個點如果找不到兩個不同的點，連一條線，使該點在連線上（不含連線端點），那么該點為角?；尚薪馀c可行域凸集的角一一對應(yīng)。如果一個線性規(guī)劃問題有最優(yōu)解，那么一定可以在基可行解中找到最優(yōu)解。2線性規(guī)劃和單純性法2.4單純形法（1）單純形方法由于線性規(guī)劃問題的最優(yōu)解一定可以在基可行解中找到，那么窮舉所有的基可行解一定可以找到最優(yōu)解。但是遺憾的是當n和m足夠大時會非常大。2線性規(guī)劃和單純性法2.4單純形法（2）單純形方法本質(zhì)由美國著名運籌學(xué)家GeorgeBernardDantzig在1947年提出。單純形方法本質(zhì)：由任何一個基可行解開始，根據(jù)單純形法規(guī)則可以找到下一個更優(yōu)的基可行解，再不斷重復(fù)單純形法規(guī)則，直到找到最優(yōu)的基可行解，即問題的最優(yōu)解。單純形法在線性規(guī)劃領(lǐng)域的出現(xiàn)，就好比幫助一群迷路的登山者，找到了一條通往山頂?shù)碾A梯（可以保證每一步后都更接近目標）。2線性規(guī)劃和單純性法2.4單純形法（3）單純形方法適用于求解任何線性規(guī)劃問題標準模型。2線性規(guī)劃和單純性法2.4單純形法（3）單純形方法步驟一：找到標準模型中的初始基可行解。如果標準模型系數(shù)矩陣中包括1個m階單位矩陣，那么可以找到一個顯見的基可行解。因此顯見的基可行解為2線性規(guī)劃和單純性法2.4單純形法（3）單純形方法步驟二：基于當前的基可行解，找到下一個更優(yōu)的基可行解。本步驟的內(nèi)容是對等式約束條件和目標函數(shù)變形，即用非基變量和常數(shù)表示基變量和目標z。本例變形：選擇系數(shù)為正數(shù)，且最大的非基變量。2線性規(guī)劃和單純性法2.4單純形法（3）單純形方法步驟二：基于當前的基可行解，找到下一個更優(yōu)的基可行解。重新用當前非基變量和常數(shù)表示基變量和目標z。2線性規(guī)劃和單純性法2.4單純形法（3）單純形方法步驟二：基于當前的基可行解，找到下一個更優(yōu)的基可行解。重新用當前非基變量和常數(shù)表示基變量和目標z。2線性規(guī)劃和單純性法2.4單純形法（3）單純形方法步驟二：基于當前的基可行解，找到下一個更優(yōu)的基可行解。重新用當前非基變量和常數(shù)表示基變量和目標z。找不到系數(shù)大于0的非基變量，說明？2線性規(guī)劃和單純性法2.4單純形法（3）單純形方法步驟三：如果所有非基變量在目標函數(shù)中的系數(shù)小于等于0，說明找到最優(yōu)解。2線性規(guī)劃和單純性法2.4單純形法（3）單純形方法將上述標準模型，修改。2線性規(guī)劃和單純性法2.4單純形法（3）單純形方法步驟一：找到標準模型中的初始基可行解。如果標準模型系數(shù)矩陣中包括1個m階單位矩陣，那么可以找到一個顯見的基可行解。因此顯見的基可行解為2線性規(guī)劃和單純性法2.4單純形法（3）單純形方法步驟二：基于當前的基可行解，找到下一個更優(yōu)的基可行解。本步驟的內(nèi)容是對等式約束條件和目標函數(shù)變形，即用非基變量和常數(shù)表示基變量和目標z。本例變形：選擇系數(shù)為正數(shù)，且最大的非基變量。2線性規(guī)劃和單純性法2.4單純形法（3）單純形方法步驟二：基于當前的基可行解，找到下一個更優(yōu)的基可行解。重新用當前非基變量和常數(shù)表示基變量和目標z。2線性規(guī)劃和單純性法2.4單純形法（3）單純形方法步驟二：基于當前的基可行解，找到下一個更優(yōu)的基可行解。重新用當前非基變量和常數(shù)表示基變量和目標z。2線性規(guī)劃和單純性法2.4單純形法（3）單純形方法步驟二：基于當前的基可行解，找到下一個更優(yōu)的基可行解。重新用當前非基變量和常數(shù)表示基變量和目標z。2線性規(guī)劃和單純性法2.4單純形法（3）單純形方法步驟三：如果所有非基變量在目標函數(shù)中的系數(shù)小于等于0，說明找到最優(yōu)解，如果還存在非基變量檢驗數(shù)等于0，說明有無窮個解。為什么求得兩個不同基可行解，就可以確定得到無窮個最優(yōu)解？證明：引理：如果可行域中線段端點使目標函數(shù)值相等，那么線段上的點目標函數(shù)值與端點相同。2線性規(guī)劃和單純性法2.4單純形法（3）單純形方法用單純形法求解以下模型。2線性規(guī)劃和單純性法2.4單純形法（3）單純形方法此模型為無界解。說明x1可以無限制增加，x3和x4也不會取負數(shù)。2線性規(guī)劃和單純性法2.4單純形法（4）單純形表形式-唯一解單純形表格式ci23000CBXBbx1x2x3x4x5zz000x3x4x5812100164001012040010002343x23x4x3000301001/4164001021010-1/20002-3/424-92線性規(guī)劃和單純性法2.4單純形法（4）單純形表形式-唯一解單純形表格式ci23000CBXBbx1x2x3x4x5zx23x4x300301001/4164001021010-1/20002-3/424-92x1410000x5400-213x22010z14000x12x23x4021010-1/2800-412301001/4000-20-2×1-0×(-4)-3×0=-21/4-412z131/21/41/2-1/8-1/8-3/2目標Max：非基變量檢驗數(shù)，均小于0。2線性規(guī)劃和單純性法2.4單純形法ci23000CBXBbx1x2x3x4x5-z000x3x4x58121001640010120400100023430ci23000CBXBbx1x2x3x4x5x23x4x300301001/4164001021010-1/20002-3/424-9z2線性規(guī)劃和單純性法2.4單純形法（5）單純形表-無窮多最優(yōu)解ci24000CBXBbx1x2x3x4x5ci23000CBXBbx1x2x3x4x541000400-212011/201600-20x24x5x120zx12x24x4021010-1/2800-412301001/4000-20-412z161/41/2-1/80目標Max：非基變量檢驗數(shù)，均小于等于0，且至少有一個非基變量的檢驗數(shù)等于0。2線性規(guī)劃和單純性法2.4單純形法2線性規(guī)劃和單純性法2.4單純形法2線性規(guī)劃和單純性法2.4單純形法（5）無窮最優(yōu)解判斷ci-2400CBXBbx1x2x3x40x34-121020x41-11011z0-24000x32101-224x21-1101-z4200-4-2x12101-24x23011-1z800-202線性規(guī)劃和單純性法2.4單純形法（5）無窮最優(yōu)解判斷x1x232112344(2,3)射線上的點均為最優(yōu)解2線性規(guī)劃和單純性法2.4單純形法（6）單純形表-無界解ci1100CBXBbx1x2x3x40x31-11100x44-1201z01100目標Max：存在某非基變量檢驗數(shù)大于0，且對應(yīng)當前表中系數(shù)列向量元素均小于等于0。2線性規(guī)劃和單純性法2.4單純形法思考與練習(xí)題如果目標函數(shù)為Min，單純形表的唯一解、無窮解和無界解如何判斷？唯一最優(yōu)解無窮最優(yōu)解無界解練習(xí)題P55頁2.1（3）、P56頁2.5和2.8題。目標Max：非基變量檢驗數(shù)，均小于0。目標Min：非基變量檢驗數(shù)，均大于0。目標Max：非基變量檢驗數(shù)，均小于等于0，且至少有一個非基變量的檢驗數(shù)等于0。目標Min：非基變量檢驗數(shù)，均大于等于0，且至少有一個非基變量的檢驗數(shù)等于0。目標Max：存在某非基變量檢驗數(shù)大于0，且對應(yīng)當前表中系數(shù)列向量元素均小于等于0。目標Min：存在某非基變量檢驗數(shù)小于0，且對應(yīng)當前表中系數(shù)列向量元素均小于等于0。2線性規(guī)劃和單純性法2.4單純形法（7）大M和兩階段法2線性規(guī)劃和單純性法2.4