線性規(guī)劃問題的數(shù)學(xué)模型教學(xué)課件

0傲財(cái)大學(xué)第一篇線性規(guī)劃模型及應(yīng)用第1章線性規(guī)劃問題的數(shù)學(xué)模型第2章單純形方法第3章對(duì)偶線性規(guī)劃問題第4章運(yùn)輸問題第5章整數(shù)規(guī)劃Linearprogramming&modeFandapplieati獎(jiǎng)財(cái)詠數(shù)學(xué)建模應(yīng)用10數(shù)學(xué)數(shù)學(xué)精微何處尋紛紜世界有模型。應(yīng)用8建模描摹萬象得神韻,應(yīng)用6方法識(shí)破玄機(jī)算古今。豈是空文無實(shí)效,應(yīng)用636時(shí)能手妙策濟(jì)蒼生。應(yīng)用4經(jīng)天緯地顯身手,七十二行任縱橫李尚志】城自備bAck3/59ch1線性規(guī)劃問題2線性Ch2單純形方法2規(guī)劃Ch3對(duì)偶線性規(guī)劃問題2模型Ch4運(yùn)輸問題2及應(yīng)用10ch5整數(shù)規(guī)劃2建模案例(自學(xué)+點(diǎn)評(píng))數(shù)學(xué)建樣方法2019年1月1日星期日兇第1章線性規(guī)劃問題的數(shù)學(xué)模型及其解的性質(zhì)>&k459§1-1LP問題數(shù)學(xué)模型、兩個(gè)變量線性規(guī)劃[LP背景介紹]問題的圖解法步驟引例二、線性規(guī)劃解的匯總、合理下料問題§13LINGO軟件簡介二、資源合理利用問題(資源的最優(yōu)配置)一、軟件簡介三、配料問題食譜問題)二、舉例說明四、運(yùn)輸問題§1-2兩變量線性規(guī)劃問題的圖解法數(shù)學(xué)建樣方法2019年1月1日星期日兇第1章線性規(guī)劃問題的數(shù)學(xué)模型及其解的性質(zhì)>&sk59背景介紹現(xiàn)了許多線性規(guī)劃軟件,如MPSX,三影0PHEIE,,WPIR等,可以很方便地求解幾千個(gè)變量的線性規(guī)劃問題。線性◆1979年蘇聯(lián)數(shù)學(xué)家L.G.Khachian提出解線性規(guī)劃問題的橢球規(guī)劃算法,并證明它是多項(xiàng)式時(shí)間算法。1984年美國貝爾電話實(shí)驗(yàn)室的印度數(shù)學(xué)家N.卡馬卡提出解線性規(guī)劃問題的新的多項(xiàng)式時(shí)間算法。用這種方法求解線性規(guī)劃問題在變量個(gè)數(shù)為5000時(shí)只要單純形法所用時(shí)間的1/50?，F(xiàn)已形成線性規(guī)劃多項(xiàng)式算法理論。50年代后線性規(guī)劃的應(yīng)用范圍不斷擴(kuò)大數(shù)學(xué)建樣方法2019年1月1日星期日兇§1-1線性規(guī)劃問題的數(shù)學(xué)模型通36/59引例某工廠生產(chǎn)一種型號(hào)的機(jī)床,每臺(tái)機(jī)床上需要29米、21米和15米長的三種軸各一根,這些軸需要用同一種圓鋼制作,圓鋼的長度為7米。如果要生產(chǎn)100臺(tái)機(jī)床,應(yīng)如何下料,才能使得用料最省?2.9米數(shù)學(xué)建樣方法2019年1月1日星期日兇§1-1線性規(guī)劃問題的數(shù)學(xué)模型引例某工廠生產(chǎn)一種型號(hào)的機(jī)床,每臺(tái)機(jī)床上需要29米、21米和1.米長的三種軸各一根,這些軸需要用同一種圓鋼制作,圓鋼的長度為74米。如果要生產(chǎn)100臺(tái)機(jī)床,應(yīng)如何下料,才能使得用料最省?分析對(duì)于每一根長為74米的圓鋼,截成2.9米、2.1米和15米長的毛坯,可以有若千種下料方式,把它截成我們需要的長度,有以下8種下料方式表1-1):表11下料方式下料方長度B1B2B3B4B5B6B7|B需要量式及每29米2000|100種類型2米03210100的數(shù)目1.5米100余料010.30901102.8|14數(shù)學(xué)建樣方法2019年1月1日星期日兇§1-1線性規(guī)劃問題的數(shù)學(xué)模型bAck8/59下料方式是從大到小、從長到短的順序考慮的。1.若只考慮用B3方式下料,需用料100根,沒優(yōu)化。2.若采用木工師傅的下料方法:先下最長的、再下次長的、最后下短的(見表1-2),共需原料96根下料方式下料根數(shù)|29米根數(shù)21.根數(shù)15米根數(shù)表12B15010050木工師B3330傅的下料情況B120000902B2合計(jì)96100101100動(dòng)一下腦筋,就可以發(fā)現(xiàn)用此方式下料節(jié)約用料4根,降低成本,但這仍然不是最好的下料方法。數(shù)學(xué)建方法2019年1月1日星期日§1-1線性規(guī)劃問題的數(shù)學(xué)模型CBack9/593.若要我們安排下料,暫不排除8種下料方式中的任何種通過建立數(shù)學(xué)模型進(jìn)行求解尋找最好的下料方案設(shè)用B1,B2,B3,B4,B3,B6,B2,B方式下料的根數(shù)分別為x1,x2,x3,x4,x5,x6,x,x3,則下料數(shù)量要求非負(fù):x1,x2,x3,x4,x53,x6,x7x≥0共需要原料數(shù)為S=x1+x2+x3+x4+x3+x6+x2+x29米、21米和15米圓鋼的數(shù)量均不低于100根,即:2x1+x2+x3+x4≥1002x2+x3+3x5+2x6+x7≥100x1+x2+2x+3x1+4x≥10因此,可以建立以下數(shù)學(xué)模型數(shù)學(xué)建樣方法2019年1月1日星期日兇§1-1線性規(guī)劃問題的數(shù)學(xué)模型>Bask10/59因此,可以建立以下數(shù)學(xué)模型minS=x,+x2+x3+x4+xs+r6+x,tx2x1+x,+x3+x≥1002x2+x3+3x5+2x6+x≥100S