線性規(guī)劃及單純形法

1、運籌學(xué)Operational Research運籌帷幄，決勝千里 史記張良傳1 緒 論一、運籌學(xué)發(fā)展簡介二、運籌學(xué)的特點及研究對象三、運籌學(xué)的工作步驟四、運籌學(xué)內(nèi)容介紹2一、運籌學(xué)（OR）發(fā)展簡介運籌學(xué)在國外英國稱為 Operational Research美國稱為 Operations Research起源于二戰(zhàn)期間的軍事問題，如雷達的設(shè)置、運輸船隊的護航艦隊的規(guī)模、反潛作戰(zhàn)中深水炸彈的深度、飛機出擊隊型、軍事物資的存儲等。二戰(zhàn)以后運籌學(xué)應(yīng)用于經(jīng)濟管理領(lǐng)域（LP、計算機）1948年英國首先成立運籌學(xué)會；1952年美國成立運籌學(xué)會。1952年，Morse 和 Kimball出版運籌學(xué)方法195

2、9年成立國際運籌學(xué)聯(lián)合會3運籌學(xué)在國內(nèi)中國古代樸素的運籌學(xué)思想（田忌與齊王對馬、都江堰工程、丁渭修復(fù)皇宮）1956年成立運籌學(xué)小組1958年提出運輸問題的圖上作業(yè)法1962年提出中國郵路問題1964年華羅庚推廣統(tǒng)籌方法我國于1982年加入國際運籌學(xué)聯(lián)合會，并于1999年8月組織了第15屆大會4二、運籌學(xué)的特點及研究對象運籌學(xué)的定義運籌學(xué)為決策機構(gòu)對所控制的業(yè)務(wù)活動作決策時，提供以數(shù)量為基礎(chǔ)的科學(xué)方法Morse 和 Kimball運籌學(xué)是把科學(xué)方法應(yīng)用在指導(dǎo)人員、工商企業(yè)、政府和國防等方面解決發(fā)生的各種問題，其方法是發(fā)展一個科學(xué)的系統(tǒng)模式，并運用這種模式預(yù)測、比較各種決策及其產(chǎn)生的后果，以幫助主

3、管人員科學(xué)地決定工作方針和政策英國運籌學(xué)會運籌學(xué)是應(yīng)用分析、試驗、量化的方法對經(jīng)濟管理系統(tǒng)中人力、物力、財力等資源進行統(tǒng)籌安排，為決策者提供有根據(jù)的最優(yōu)方案，以實現(xiàn)最有效的管理中國百科全書現(xiàn)代運籌學(xué)涵蓋了一切領(lǐng)域的管理與優(yōu)化問題，稱為 Management Science5三、運籌學(xué)的工作步驟明確問題建立模型設(shè)計算法整理數(shù)據(jù)求解模型評價結(jié)果簡化？ 滿意？YesNoNo明確問題建立模型設(shè)計算法整理數(shù)據(jù)求解模型評價結(jié)果6四、運籌學(xué)內(nèi)容介紹排隊論 線性規(guī)劃及單純形法 對偶理論及靈敏度分析 運輸問題 整數(shù)規(guī)劃 動態(tài)規(guī)劃 圖與網(wǎng)絡(luò)分析7第一章 線性規(guī)劃及單純形法 第一節(jié) 線性規(guī)劃問題及數(shù)學(xué)模型1939年

4、 蘇 康托洛維奇1941年 美 Hichook1947年 G.B.Dantzig 單純形法1979年 蘇 哈奇安算法1984年 Karmarkar算法 8一、實例例1 (書P8) I II設(shè) 備 1 2 8臺時 原材料A 4 0 16公斤原材料B 0 4 12公斤設(shè)I、II兩種產(chǎn)品的產(chǎn)量分別為x1, x2 。建立該問題的數(shù)學(xué)模型為：例2 現(xiàn)要做100套鋼架，每套需2.9米、2.1米和1.5米的圓鋼各一根。已知原料長7.4米，問如何下料，使用的原料最少（余料最少或根數(shù)最少）？9解：設(shè) x1, x2 , x3, x4 , x5分別代表五種不同的原料用量方案（余料最少）方案2.9米2.1米1.5米合

5、計余料x11037.40 x22017.30.1x30227.20.2x41207.10.3x50136.60.81011二、總結(jié) 目標(biāo)函數(shù)用決策變量的線性函數(shù)來表示。按問題的不同，要求目標(biāo)函數(shù)實現(xiàn)最大化和最小化。線性規(guī)劃問題（LP問題）的共同特征： 每一個問題變量都用一組決策變量（x1, x2, , xn）表示某一方案，這組決策變量的值代表一個具體方案，這些變量是非負(fù)的。 存在一定的約束條件，這些約束條件可以用一組線性等式或線性不等式來表示。12三、兩變量線性規(guī)劃問題的圖解法1.線性不等式的幾何意義 半平面作出LP問題的可行域作出目標(biāo)函數(shù)的等值線移動等值線到可行域邊界得到最優(yōu)點2.圖解法步驟

6、134x1=164x2=12x1+2x2=8x1x248430例1 （書P8）：Q(4,2)Z=2x1+3x2 做目標(biāo)函數(shù)2x1+3x2的等值線，與陰影部分的邊界相交于Q(4,2)點，表明最優(yōu)生產(chǎn)計劃為：生產(chǎn)I產(chǎn)品4件，生產(chǎn)II產(chǎn)品2件。14例2Z=36153. 圖解法的作用 能解決少量問題LP問題有可行解有最優(yōu)解唯一解無窮多解無最優(yōu)解（可行域為無界）無可行解（無解）規(guī)律1： 揭示了線性規(guī)劃問題的若干規(guī)律16結(jié)論2：若LP問題有最優(yōu)解，則要么最優(yōu)解唯一，要么有無窮多最優(yōu)解。17 規(guī)律2：線性規(guī)劃問題的可行域為一凸集線性規(guī)劃問題凸集的頂點個數(shù)是有限的最優(yōu)解肯定可在凸集的某頂點處達到 18四、 線

7、性規(guī)劃問題的標(biāo)準(zhǔn)型1. 標(biāo)準(zhǔn)型192. 所有LP問題均可化為標(biāo)準(zhǔn)型20例1可化為21例2 化標(biāo)準(zhǔn)型22課堂作業(yè)23五、標(biāo)準(zhǔn)型LP問題的解2425令B = =( P1 , P2 , , Pm ) 且| B | 0 ，則稱Pj (j=1,2,m) 為基向量。與基向量Pj對應(yīng)的變量xj稱為基變量，記為XB = ( x1 , x2 , , xm )T，其余的變量稱為非基變量，記為 XN = ( xm+1 , xm+2 , , xm+n ) T ?；兞浚?6基本解令非基變量 XN = 0，求得的一組基變量 XB的值稱為基礎(chǔ)解。 基可行解（頂點）既是基本解，又是可行解?；顑?yōu)點既是基本解，又是使目標(biāo)函數(shù)

8、值達到最優(yōu)的解27 線性規(guī)劃標(biāo)準(zhǔn)型問題解的關(guān)系約束方程的解空間基解可行解非可行解基可行解28 10/3 244x1x2x1+x2=43x1 +5x2=1029 可行解、基礎(chǔ)解和基礎(chǔ)可行解舉例30第二節(jié) 單純型法 一、基本思想化LP問題為標(biāo)準(zhǔn)型，確定一個初始基本可行解檢驗解的最優(yōu)性結(jié)束Y樞軸運算（旋轉(zhuǎn)運算）確定另一個基本可行解N31二、樞軸運算32三、檢驗數(shù)的意義33第三節(jié) 單純型法的步 驟一、步驟化LP問題為標(biāo)準(zhǔn)型,建立初始單純型表;34二、實例化為標(biāo)準(zhǔn)型35單純型表算法以4為樞軸元素進行旋轉(zhuǎn)運算，x2為換入變量，x5為換出變量以1為樞軸元素進行運算，x1為換入變量， x3為換出變量36以2為

9、樞軸元素進行運算，x5為換入變量， x4為換出變量此時達到最優(yōu)解。X*=(4,2), MaxZ=14。37第四節(jié) LP問題的進一步討論一、人工變量法381. 大M法(M為任意大的正數(shù))加入松弛變量x4;剩余變量x5;人工變量x6,x7391) 人工變量的識別2) 目標(biāo)函數(shù)的處理3) 計算(單純型法)40注意：本例是求最小值，所以用所有 來判別目標(biāo)函數(shù)是否實現(xiàn)了最小化。因而換入變量xk的選取標(biāo)準(zhǔn)為41結(jié)果得: X*=(4,1,9,0,0,0,0) Z*=2（接上表）42 兩階段法(將LP問題分成兩個階段來考慮) 第I 階段: 不考慮原問題是否存在可行解，給原LP問題加入人工變量，并構(gòu)造僅含人工變

10、量的目標(biāo)函數(shù)和要求最小化；然后用單純型法求解，若得w=0，則進行第二階段計算，否則無可行解。 第II 階段：將第一階段得到的最終表除去人工變量，將目標(biāo)函數(shù)行的系數(shù)換為原問題的系數(shù)，作為第二階段的初始表。43加入松弛變量x4;剩余變量x5;人工變量x6,x7用單純形法求解第一階段的結(jié)果得：44此時，達到第一階段的最優(yōu)解，W=045由于人工變量x6 =x7=0,所以（0,1,1,12,0）T是該線性規(guī)劃問題的基可行解。于是轉(zhuǎn)入第二階段運算：此時達到該LP問題的最優(yōu)解：x1=4,x2=1,x3=9; 目標(biāo)函數(shù)值Z=-2。46二、單純型法中存在的問題1. 存在兩個以上的最大正檢驗數(shù)。選擇任何變量（對應(yīng)

11、最大正檢驗數(shù)）作為進基變量。2. 最小比值相同。LP問題出現(xiàn)退化現(xiàn)象，即基變量取值為0 4748選取x1為換入變量；按Bland算法，選取下標(biāo)最小的x5為換出變量，得下表：此時換出變量為x1，換入變量為x4，迭代后目標(biāo)函數(shù)值不變，繼而出現(xiàn)了循環(huán)現(xiàn)象，達不到最優(yōu)解。49解決退化的方法有：“攝動法”、“辭典序法”、 Bland規(guī)則等1974年Bland提出Bland算法規(guī)則：503. 最小比值原則失效Cj2300CBXBbX1X2X3X40X36-20113X24-3101Cj-Zj-121100-3經(jīng)過一次迭代后可得右表514. 在最優(yōu)表中出現(xiàn)某非基變量檢驗數(shù)為052CBXBbX1X2X3X4X

12、50X340012/3-1/34X260101/203X14100-2/31/3Cj-Zj-360000-10X46003/21-1/24X2301-3/401/43X1810100Cj-Zj-360000-1Cj-Zj034000結(jié)論：若線性規(guī)劃問題存在某非基變量檢驗數(shù)為0,而其對應(yīng)列向量ak0,仍可判斷線性規(guī)劃問題有無窮多最優(yōu)解。任一個LP問題最優(yōu)解都可表示成其基本最優(yōu)解的凸組合加上其凸方向的線性組合.53第五節(jié) 應(yīng)用舉例例1 某工廠要用三種原材料C、P、H混合調(diào)配出三種不同規(guī)格的產(chǎn)品A、B、C。已知產(chǎn)品的規(guī)格要求、單價和原材料的供應(yīng)量、單價。該廠應(yīng)如何安排生產(chǎn)使利潤最大？產(chǎn)品名稱規(guī)格要求

13、單價(元/kg）A原材料C不少于50%原材料P不超過25%50B原材料C不少于25%原材料P不超過50%35D不限25原材料名稱每天最多供應(yīng)量(kg)單價(元/kg)C10065P10025H603554用單純型法計算得結(jié)果:每天生產(chǎn)A產(chǎn)品200kg,分別需要原料:C為100kg;P為50kg;H為50kg. 總利潤收入Z=500元/天.55先考慮一月份的線性規(guī)劃模型:例2 （書P41 例12）56以一月份內(nèi)各種設(shè)備的生產(chǎn)能力總和為分母,生產(chǎn)產(chǎn)品所需要的各類設(shè)備的總臺時數(shù)為分子,可計算出一月份的平均設(shè)備利用系數(shù)Z,將Z作為目標(biāo)函數(shù),可得下面的模型:57 考慮二月份線性規(guī)劃模型時:(1)從全年計

14、劃中減去一月份已生產(chǎn)的數(shù)量;(2)對批量小的產(chǎn)品,如一月份已經(jīng)安排較大產(chǎn)量的,二月份將剩余部分安排生產(chǎn);(3)保證第4號產(chǎn)品在月底前交貨.這樣,我們可以依次對12個月列出線性規(guī)劃模型并求解,再根據(jù)具體情況對計算結(jié)果進行必要調(diào)整.58例3 某部門在今后5年內(nèi)連續(xù)給以下項目投資： 項目A，第一年至第四年每年年初投資，次年末回收本利 115%； 項目B，第三年初投資，第五年末回收本利 125%，最大投資額不超過4萬元； 項目C，第二年初投資，第五年末回收本利 140%，最大投資額不超過3萬元； 項目D，五年內(nèi)每年初可購買公債，當(dāng)年末歸還，并加利息6% 。 該部門現(xiàn)有資金 10萬元，問該如何確定投資方案，使第五年末擁有的資金本利和最大？5960班次時間所需人數(shù)16:0010:0060210:0014:0070314:0018:0060418:0022:0050522:002:002062:006:0030例4 某公交線路每天各時段內(nèi)所需司乘 人員數(shù)如下： 設(shè)所有的司乘人員分別在各時段的開始上班，并連續(xù)工作8小時，問該公交線路至少需配備多少司乘人員。列出該問題的線性規(guī)劃模型