線性規(guī)劃模型的建立與應(yīng)用重點(diǎn)PPT學(xué)習(xí)教案

1、會(huì)計(jì)學(xué)1線性規(guī)劃模型的建立與應(yīng)用重點(diǎn)線性規(guī)劃模型的建立與應(yīng)用重點(diǎn)第一節(jié) 線性規(guī)劃模型的基本原理 第1頁(yè)/共73頁(yè)第一節(jié) 線性規(guī)劃模型的基本原理 第2頁(yè)/共73頁(yè)第一節(jié) 線性規(guī)劃模型的基本原理 第3頁(yè)/共73頁(yè)第一節(jié) 線性規(guī)劃模型的基本原理 第4頁(yè)/共73頁(yè)第一節(jié) 線性規(guī)劃模型的基本原理 特點(diǎn)：1.可以使研究對(duì)象具體化、數(shù)量化?？梢詫?duì)所研究的技術(shù)經(jīng)濟(jì)問(wèn)題做出明確的結(jié)論；2.線性3.允許出現(xiàn)生產(chǎn)要素的剩余量4.有一套完整的運(yùn)算程序第5頁(yè)/共73頁(yè)第一節(jié) 線性規(guī)劃模型的基本原理 局限性：1. 線性規(guī)劃它是以價(jià)格不變和技術(shù)不變?yōu)榍疤釛l件的，不能處理涉及到時(shí)間因素的問(wèn)題。因此，線性規(guī)劃只能以短期計(jì)劃為基

2、礎(chǔ)。2.在生產(chǎn)活動(dòng)中，投入產(chǎn)出的關(guān)系不完全是線性關(guān)系，由于在一定的技術(shù)條件下，報(bào)酬遞減規(guī)律起作用，所以要滿足線性假定是不可能的。在線性規(guī)劃解題中，常常把投入產(chǎn)出的非線性關(guān)系轉(zhuǎn)化為線性關(guān)系來(lái)處理，以滿足線性的假定性，客觀上產(chǎn)生誤差。3.線性規(guī)劃本身只是一組方程式，并不提供經(jīng)濟(jì)概念，它不能代替人們對(duì)現(xiàn)實(shí)經(jīng)濟(jì)問(wèn)題的判斷。 第6頁(yè)/共73頁(yè)第一節(jié) 線性規(guī)劃模型的基本原理 第7頁(yè)/共73頁(yè)約束條件目標(biāo)函數(shù)第一節(jié) 線性規(guī)劃模型的基本原理 第8頁(yè)/共73頁(yè) x1 ，x2 ，xn0第一節(jié) 線性規(guī)劃模型的基本原理 極大值模型第9頁(yè)/共73頁(yè)njxbxaxcxcxcZjinjjijnn, 3 , 2 , 1,0m

3、ax12211其簡(jiǎn)縮形式為其簡(jiǎn)縮形式為 第一節(jié) 線性規(guī)劃模型的基本原理 極大值模型第10頁(yè)/共73頁(yè)第一節(jié) 線性規(guī)劃模型的基本原理 極小值模型第11頁(yè)/共73頁(yè)njxbxaxcxcxcZjinjjijnn, 3 , 2 , 1,0min12211其簡(jiǎn)縮形式為其簡(jiǎn)縮形式為 第一節(jié) 線性規(guī)劃模型的基本原理 極小值模型第12頁(yè)/共73頁(yè)其簡(jiǎn)縮形式為其簡(jiǎn)縮形式為 第一節(jié) 線性規(guī)劃模型的基本原理 極大值模型可用向量表示： 01jnjjjxbxPCXzMaxnxxxX21mjjjjaaaP21bmbbb21 C=(c1,c2,cn) 第13頁(yè)/共73頁(yè)第14頁(yè)/共73頁(yè)第15頁(yè)/共73頁(yè)第16頁(yè)/共73頁(yè)

4、第17頁(yè)/共73頁(yè)數(shù)量分別為x1、x2和x3公頃，根據(jù)問(wèn)題建立線性規(guī)劃問(wèn)題模型如下：第18頁(yè)/共73頁(yè)第19頁(yè)/共73頁(yè)式種x2公頃，總收入為Z，則有：第20頁(yè)/共73頁(yè)第21頁(yè)/共73頁(yè)第22頁(yè)/共73頁(yè)第23頁(yè)/共73頁(yè)無(wú)窮多個(gè)可行點(diǎn)，縮小到可行域的有限幾個(gè)極點(diǎn)上。第24頁(yè)/共73頁(yè)第25頁(yè)/共73頁(yè)O 20 40 x120ABCD280 x1+150 x2=42006x1+15x2=240 x1+x2=20 x2Z=1000 x1+1200 x2A(0,16)B(6.7,13.3)C(9.2,10.8)D(15,0)ZA=19200ZB=22660ZC=22160ZD=15000第26頁(yè)

5、/共73頁(yè)第27頁(yè)/共73頁(yè)1515105105OABCDx2x1x1+6x2=15可行域3x1+x2=15x1+x2=1010 x1+20 x20A(0,15)B(2.5,7.5)C(9,1)D (15,0)ZA=300ZB=175ZC=110ZD=150第28頁(yè)/共73頁(yè) 單純形方法是一種較為完善的、步驟化的線性規(guī)劃問(wèn)題求解方法。它的原理涉及到較多的數(shù)學(xué)理論上的推導(dǎo)和證明，我們?cè)诖藘H介紹這種方法的具體操作步驟及每一步的經(jīng)濟(jì)上的含義。為更好地說(shuō)明問(wèn)題，我們?nèi)越Y(jié)合實(shí)例介紹這種方法 第29頁(yè)/共73頁(yè)一、線性規(guī)劃的標(biāo)準(zhǔn)型二、線性規(guī)劃問(wèn)題的解三、單純形法 四、單純型表第30頁(yè)/共73頁(yè)第三節(jié) 單純

6、形法一線性規(guī)劃的標(biāo)準(zhǔn)型LP目標(biāo)函數(shù)有的要求實(shí)現(xiàn)最大化，有的要求實(shí)現(xiàn)最小化，約束條件可以是“=”、“”，這種多樣性給討論問(wèn)題帶來(lái)不便。為了便于討論，我們規(guī)定線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式為：Max Z=c1x1+c2x2+c3x3+cnxn a11x1+a12x2+a1nxn=b1 (1) a21x1+a22x2+a2nxn=b2 (2) am1x1+am2x2+amnxn=bm (m) x1 ，x2 ，xn0 第31頁(yè)/共73頁(yè)第三節(jié) 單純形法其簡(jiǎn)縮形式為 一線性規(guī)劃的標(biāo)準(zhǔn)型njxbxaxcxcxcZjinjjijnn, 3 , 2 , 1,0max12211用向量表示 01jnjjjxbxPnxxx

7、X21mjjjjaaaP21bmbbb21 其中 C=(c1,c2,cn) 向量Pj是其對(duì)應(yīng)變量xj 的系數(shù)向量。 第32頁(yè)/共73頁(yè)第三節(jié) 單純形法一線性規(guī)劃的標(biāo)準(zhǔn)型用矩陣描述CXzMax0XbAX mnmnmmnbbbbbPPPaaaaaaA321212111211;第33頁(yè)/共73頁(yè)第三節(jié) 單純形法二線性規(guī)劃問(wèn)題的解 可行解可行解最優(yōu)解最優(yōu)解 基基 設(shè)A為約束方程組的mn階系數(shù)矩陣，其秩為m。B是矩陣A中mm階非奇異子矩陣（ ）,則稱B是線性規(guī)劃問(wèn)題的一個(gè)基。不失一般性可設(shè) 0BmmmmmmPPPaaaaaaB212111211稱Pj為基向量，與基變量Pj相對(duì)應(yīng)的變量為基變量。否則為非基

8、變量。 第34頁(yè)/共73頁(yè)二線性規(guī)劃問(wèn)題的解 第35頁(yè)/共73頁(yè)nmnnnmmmmmmmmmmmmmxaaaxaaabbbxaaaxaaaxaaa211112112121122212112111nmjjjmjjjxPbxP11或 021nmmxxxTmxxxX)0 , 0 ,(21設(shè)非基變量用高斯消去法，可求出一個(gè)解稱X為基本解基本解基本可行解基本可行解 滿足非負(fù)條件的基本解二線性規(guī)劃問(wèn)題的解 第36頁(yè)/共73頁(yè)如何安排生產(chǎn)計(jì)劃，才能得到利潤(rùn)最多？三單純形法第37頁(yè)/共73頁(yè) 設(shè)備產(chǎn)品ABCDx12140 x22204三單純形法第38頁(yè)/共73頁(yè)三單純形法第39頁(yè)/共73頁(yè)引入松弛變量x3 A

9、設(shè)備閑置臺(tái)時(shí)數(shù)x4 B設(shè)備閑置臺(tái)時(shí)數(shù)x5 C設(shè)備閑置臺(tái)時(shí)數(shù)x6D設(shè)備閑置臺(tái)時(shí)數(shù)將線性規(guī)劃化為標(biāo)準(zhǔn)型.（8.1） 三單純形法 求解過(guò)程第40頁(yè)/共73頁(yè)（8.2） 三單純形法 求解過(guò)程第41頁(yè)/共73頁(yè)系數(shù)矩陣 100040010004001021000122654321PPPPPPA10000100001000016543PPPPB三單純形法 求解過(guò)程第42頁(yè)/共73頁(yè)對(duì)應(yīng)于B的變量x3, x4, x5, x6為基變量，從標(biāo)準(zhǔn)型我們可以得到： （8.3） 三單純形法 求解過(guò)程第43頁(yè)/共73頁(yè)TxxxxxxX121681200121681200)0(6)0(5)0(4)0(3)0(2)0(1)

10、0(這個(gè)基本可行解表示：工廠沒(méi)有安排生產(chǎn)產(chǎn)品；設(shè)備的有效臺(tái)時(shí)數(shù)沒(méi)有被利用，所以構(gòu)成的利潤(rùn)為0。 從分析目標(biāo)函數(shù)的表達(dá)式可以看到，非基變量x1 ,x2系數(shù)都是正數(shù)，若將非基變量換成基變量，目標(biāo)函數(shù)就會(huì)增加。所以，只要在目標(biāo)函數(shù)的表達(dá)式中還存在正系數(shù)的非基變量，這表示目標(biāo)函數(shù)還有增加的可能，就需要將非基變量換成基變量。一般選擇正系數(shù)最大的那個(gè)非基變量?？砂匆韵路椒▉?lái)確定換出變量。三單純形法 求解過(guò)程第44頁(yè)/共73頁(yè)Z=0+2x1+3 x2 （8.4）3412,28,212min2x時(shí)，才能使（8.5）式成立。因當(dāng)x2=3時(shí)，基變量x6=0這就決定用x2去替換x6。三單純形法 求解過(guò)程第45頁(yè)/共

11、73頁(yè)三單純形法 求解過(guò)程第46頁(yè)/共73頁(yè)TTxxxxxxX)0 ,16, 2 , 6 , 3 , 0(),() 1 (6) 1 (5) 1 (4) 1 (3) 1 (2) 1 (1) 1 (三單純形法 求解過(guò)程第47頁(yè)/共73頁(yè)TX)0 , 8 , 0 , 2 , 3 , 2()2(TX)4 , 0 , 0 , 0 , 2 , 4()3(三單純形法 求解過(guò)程第48頁(yè)/共73頁(yè)三單純形法 求解過(guò)程小結(jié)第49頁(yè)/共73頁(yè)jnjjxczMax101jnjjjxbxP10001000121MPPPB三單純形法 求解過(guò)程小結(jié)第50頁(yè)/共73頁(yè)10001000121MPPPB三單純形法 求解過(guò)程小結(jié)第

12、51頁(yè)/共73頁(yè)TmnmTmnmbbbxxxX)0, 0,()0, 0,(2121個(gè)個(gè)，三單純形法 求解過(guò)程小結(jié)第52頁(yè)/共73頁(yè)nmjjijiixabx1三單純形法 求解過(guò)程小結(jié)第53頁(yè)/共73頁(yè)nmjjijmiijimiiixaccbcz111)(ijmiijimiiaczbcz110,j=m+1,n nmjjjjxzczz10)(), 1(nmjzcjjjnmjjjxzz10三單純形法 求解過(guò)程小結(jié)第54頁(yè)/共73頁(yè)TmbbbX)0, 0(, 2, 1)0(0j0kmTmbbbX)0, 0(, 2, 1)0(0,kmia為換入變量則對(duì)應(yīng)的kkjx )0max(ckcikikabaabRi

13、0mincx三單純形法 求解過(guò)程小結(jié)第55頁(yè)/共73頁(yè)三單純形表例1第56頁(yè)/共73頁(yè)例1第57頁(yè)/共73頁(yè)例1第58頁(yè)/共73頁(yè)例1第59頁(yè)/共73頁(yè)例2第60頁(yè)/共73頁(yè)例2第61頁(yè)/共73頁(yè)例2第62頁(yè)/共73頁(yè)第63頁(yè)/共73頁(yè)x x1 1x x2 2x x3 3x x4 4x x5 5x x6 61 10 00 0 x x3 36 60 00 01 13 3/ /2 2- -0 0. .2 25 50 02 20 00 0+ +1 1x x1 16 61 11 10 0- -0 0. .5 51 1/ /4 40 00 0 x x6 63 36 60 0- -1 12 20 0- -

14、9 9- -4 4. .5 51 12 20 00 0+ +1 11 15 50 01 10 00 00 00 00 01 18 80 00 02 20 00 0+ +1 12 20 00 0+ +1 11 10 00 05 50 0- -0 0. .5 51 12 25 5+ +0 0. .2 25 51 10 01 18 80 00 00 0- -5 50 0- -1 10 0- -5 50 0+ +0 0. .5 51 1- -2 25 5- -0 0. .2 25 51 10 0實(shí)實(shí)際際活活動(dòng)動(dòng)松松弛弛活活動(dòng)動(dòng)目目標(biāo)標(biāo)系系數(shù)數(shù)行行c cj j機(jī)機(jī)會(huì)會(huì)成成本本行行Z Zj j第第三三單單

15、純純形形表表C CB BX XB Bb b檢檢驗(yàn)驗(yàn)數(shù)數(shù)行行j j-50 1 1001 -501 1001 100 -50-1 0 -50+0.51 0 -25-0.251 0第64頁(yè)/共73頁(yè)2 -50-502 0第65頁(yè)/共73頁(yè)-100/3 3 1003 -100/33 100 -50-1.53 0 -250.253 0第66頁(yè)/共73頁(yè)表8-3 目標(biāo)系數(shù)的允許變動(dòng)范圍活動(dòng)目標(biāo)系數(shù)當(dāng)前值可減上限 可增上限 可變范圍玉米種植x120050100150300大豆種植x2150無(wú)窮大50-200地瓜種植x3100100/3100200/3200 當(dāng)僅有一種目標(biāo)系數(shù)在允許范圍內(nèi)變動(dòng)時(shí)，最優(yōu)方案不會(huì)

16、變動(dòng)，但最優(yōu)目標(biāo)值會(huì)隨之變化。 第67頁(yè)/共73頁(yè)0360481212/9904/12/104/12/301PBX當(dāng)右邊值發(fā)生變化時(shí)，如耕地變化，此時(shí)，影子價(jià)格不變的條件是 第68頁(yè)/共73頁(yè)0360481212/9904/12/104/12/3101PBX得到 6+3/210 6-1/210 -414 36-910因此耕地影子價(jià)格不變的耕地?cái)?shù)量范圍為：8，16第69頁(yè)/共73頁(yè)0360481212/9904/12/104/12/3201PBX得到 61/420 6+1/420 -2428 36-9/220因此勞動(dòng)力影子價(jià)格不變的勞動(dòng)力數(shù)量范圍為：24，56第70頁(yè)/共73頁(yè)0360481212/9904/12/104/12/3301