線性規(guī)劃及單純形法學(xué)習(xí)教案

1、會(huì)計(jì)學(xué)1第一頁，共132頁。第1頁/共131頁第二頁，共132頁。第2頁/共131頁第三頁，共132頁。(mbio)函數(shù)的取值。函數(shù)的取值。第3頁/共131頁第四頁，共132頁。第4頁/共131頁第五頁，共132頁。00 max bXbAXCXZ第5頁/共131頁第六頁，共132頁?；蛄俊⒒兞?、非基變量、基向量、基變量、非基變量、基本解？基本解？第6頁/共131頁第七頁，共132頁。),.,(,.,.,.,11111mmmmmPPaaaaB第7頁/共131頁第八頁，共132頁。12max23Zxx12121228416412, 0 xxxxx x第8頁/共131頁第九頁，共132頁。123

2、451231425max23000284164120,1,2,5jZxxxxxxxxxxxxxj第9頁/共131頁第十頁，共132頁。100400100400121A第10頁/共131頁第十一頁，共132頁。第11頁/共131頁第十二頁，共132頁。第12頁/共131頁第十三頁，共132頁。321321100400100400121bbbxxxbAX第13頁/共131頁第十四頁，共132頁。1234512100()4001004001， ， ， ，APPPPP對(duì)應(yīng)的基變量是對(duì)應(yīng)的基變量是 x3 x4 x5第14頁/共131頁第十五頁，共132頁?；窘猓簩?duì)于某一特定的基基本解：對(duì)于某一特定的基

3、B B，令非基變量等于零，令非基變量等于零，則可由約束方程組則可由約束方程組 AX AXb b求得一個(gè)解，這樣求得一個(gè)解，這樣(zhyng)(zhyng)的解稱為基本解。的解稱為基本解。思考：基本思考：基本(jbn)解與可行解的區(qū)別？解與可行解的區(qū)別？第15頁/共131頁第十六頁，共132頁。(duyng)B6(duyng)B6） x(7)= (0,3,2,16,0)T x(7)= (0,3,2,16,0)T （對(duì)應(yīng)（對(duì)應(yīng)(duyng)B7(duyng)B7） x ( 9 ) = ( 0 , 4 , 0 , 1 6 , - 4 ) T x ( 9 ) = ( 0 , 4 , 0 , 1 6 ,

4、 - 4 ) T （對(duì)應(yīng)（對(duì)應(yīng)(duyng)B9(duyng)B9） x(10) = (0,0,8,16,12)T x(10) = (0,0,8,16,12)T （對(duì)應(yīng)（對(duì)應(yīng)(duyng)B10(duyng)B10）第16頁/共131頁第十七頁，共132頁。X(2)(2,3)X(1)(4,3)X(3)(4,2)X(6)(8,0)X(10)(0,0)6 5 4 3 2 1 0 x2|123456789x1X(7)(0,3)X(9)(0,0)X(5)(4,0)第17頁/共131頁第十八頁，共132頁?；究尚薪猓夯窘獠灰欢ǘ际强尚械?。滿足基本可行解：基本解不一定都是可行的。滿足非負(fù)限制的基本解，

5、稱為非負(fù)限制的基本解，稱為(chn wi)(chn wi)基本可行基本可行解。解?？尚谢号c基本可行解對(duì)應(yīng)的基，稱為可行基：與基本可行解對(duì)應(yīng)的基，稱為(chn (chn wi)wi)可行基?？尚谢??？尚薪狻⒒究尚薪?、基本(jbn)解、基本解、基本(jbn)可行解的關(guān)系？可行解的關(guān)系？第18頁/共131頁第十九頁，共132頁。第19頁/共131頁第二十頁，共132頁。第20頁/共131頁第二十一頁，共132頁。第21頁/共131頁第二十二頁，共132頁。第22頁/共131頁第二十三頁，共132頁。第23頁/共131頁第二十四頁，共132頁。第24頁/共131頁第二十五頁，共132頁。第25頁/

6、共131頁第二十六頁，共132頁。第26頁/共131頁第二十七頁，共132頁。第27頁/共131頁第二十八頁，共132頁。 1、 凸集凸集設(shè)設(shè)K是是n維歐氏空間的一維歐氏空間的一個(gè)點(diǎn)集，若任意個(gè)點(diǎn)集，若任意(rny)兩點(diǎn)兩點(diǎn)X（1）K，X（2）K的連線上的一切點(diǎn)：的連線上的一切點(diǎn)： X（1）+（1-）X（2） K （01），則稱），則稱K為凸集。為凸集。 第28頁/共131頁第二十九頁，共132頁。非凸集非凸集第29頁/共131頁第三十頁，共132頁。2、 凸組合 設(shè)X（1）,X（2）, ,X（k）是n維歐氏空間(kngjin)中的K個(gè)點(diǎn),若存在k個(gè)數(shù)1, 2 , ,k ,滿足0i1, i=1

7、,2, ,k；且 ， 則稱X=1X（1）+2X（2）+kX(k)為 X（1）, ，X（2） ，X（k）的凸組合。 kii11第30頁/共131頁第三十一頁，共132頁。 3、 頂點(diǎn)頂點(diǎn) 設(shè)設(shè)K是凸集，是凸集，XK；若；若X不能用不能用 X（1） K，X（2） K 的線性組合表示的線性組合表示(biosh)，即，即 XX（1）+（1-）X（2） （01） 則稱則稱X為為K的一個(gè)頂點(diǎn)（也稱極點(diǎn)或角點(diǎn)）的一個(gè)頂點(diǎn)（也稱極點(diǎn)或角點(diǎn)）第31頁/共131頁第三十二頁，共132頁。第32頁/共131頁第三十三頁，共132頁。njjjjxbxPXD10, njjjjxbxPXD10, 第33頁/共131頁第三

8、十四頁，共132頁。第34頁/共131頁第三十五頁，共132頁。第35頁/共131頁第三十六頁，共132頁。第36頁/共131頁第三十七頁，共132頁。第37頁/共131頁第三十八頁，共132頁。第38頁/共131頁第三十九頁，共132頁。從線性規(guī)劃解的性質(zhì)可知從線性規(guī)劃解的性質(zhì)可知(k zh)求解線性規(guī)劃問題的基本思路。求解線性規(guī)劃問題的基本思路。第39頁/共131頁第四十頁，共132頁。 為書寫規(guī)范和便于計(jì)算，對(duì)單純形法的計(jì)算設(shè)計(jì)了單純形表。每一次迭代對(duì)應(yīng)一張單純形表，含初始基本可行解的單純形表稱為初始單純形表，含最優(yōu)解的單純形表稱為最終單純形表。本節(jié)介紹用單純形表計(jì)算線性規(guī)劃(xin x

9、n u hu)問題的步驟。第40頁/共131頁第四十一頁，共132頁。第41頁/共131頁第四十二頁，共132頁。第42頁/共131頁第四十三頁，共132頁。miijijjBjjaccPBCC11第43頁/共131頁第四十四頁，共132頁。ikaikiab第44頁/共131頁第四十五頁，共132頁。第45頁/共131頁第四十六頁，共132頁。12max23Zxx12121228416412, 0 xxxxx x第46頁/共131頁第四十七頁，共132頁。123451231425max23000284164120,1,2,5jZxxxxxxxxxxxxxj第47頁/共131頁第四十八頁，共132

10、頁。 b 2 3 0 0 0 x1 x2 x3 x4 x5CB XB 0 x3 1 2 1 0 0 8 0 x4 4 0 0 1 0 16 0 x5 0 4 0 0 1 12 j 2 3 0 0 0 Cj第48頁/共131頁第四十九頁，共132頁。第49頁/共131頁第五十頁，共132頁。x x1 1 x x2 2 x x3 3 x x4 4 x x5 5第50頁/共131頁第五十一頁，共132頁。第51頁/共131頁第五十二頁，共132頁。第52頁/共131頁第五十三頁，共132頁。第53頁/共131頁第五十四頁，共132頁。第54頁/共131頁第五十五頁，共132頁。第55頁/共131頁第

11、五十六頁，共132頁。第56頁/共131頁第五十七頁，共132頁。第57頁/共131頁第五十八頁，共132頁。第58頁/共131頁第五十九頁，共132頁。x2504030201010203040 x1可可行行域域可可行行域域O（0，0）Q1（25，0）Q2（15，20）Q3（0，40）第59頁/共131頁第六十頁，共132頁。x2504030201010203040 x1可行域可行域可行域可行域O（0，0）Q1（25，0）Q2（15，20）Q3（0，40）第60頁/共131頁第六十一頁，共132頁。x2504030201010203040 x1可行域可行域可行域可行域O（0，0）Q1（25，0

12、）Q2（15，20）Q3（0，40）第61頁/共131頁第六十二頁，共132頁。x2504030201010203040 x1可行域可行域可行域可行域O（0，0）Q1（25，0）Q2（15，20）Q3（0，40）第62頁/共131頁第六十三頁，共132頁。x2504030201010203040 x1可行域可行域可行域可行域O（0，0）Q1（25，0）Q2（15，20）Q3（0，40）第63頁/共131頁第六十四頁，共132頁。x2504030201010203040 x1可行域可行域可行域可行域O（0，0）Q1（25，0）Q2（15，20）Q3（0，40）第64頁/共131頁第六十五頁，共1

13、32頁。x2504030201010203040 x1可行域可行域可行域可行域O（0，0）Q1（25，0）Q2（15，20）Q3（0，40）第65頁/共131頁第六十六頁，共132頁。x2504030201010203040 x1可行域可行域可行域可行域O（0，0）Q1（25，0）Q2（15，20）Q3（0，40）第66頁/共131頁第六十七頁，共132頁。x2504030201010203040 x1可行域可行域可行域可行域O（0，0）Q1（25，0）Q2（15，20）Q3（0，40）第67頁/共131頁第六十八頁，共132頁。第68頁/共131頁第六十九頁，共132頁。 x1 , x2 ,

14、 x3 , x4 x1 , x2 , x3 , x4 0 0第69頁/共131頁第七十頁，共132頁。第70頁/共131頁第七十一頁，共132頁。計(jì)算檢驗(yàn)計(jì)算檢驗(yàn)(jinyn)數(shù)，確定進(jìn)基變量、出數(shù)，確定進(jìn)基變量、出基變量，找到主元：基變量，找到主元：第71頁/共131頁第七十二頁，共132頁。進(jìn)行進(jìn)行(jnxng)初等行變換：初等行變換：第72頁/共131頁第七十三頁，共132頁。再計(jì)算再計(jì)算(j sun)檢驗(yàn)數(shù)：檢驗(yàn)數(shù)：第73頁/共131頁第七十四頁，共132頁。第74頁/共131頁第七十五頁，共132頁。第75頁/共131頁第七十六頁，共132頁。第76頁/共131頁第七十七頁，共132

15、頁。計(jì)算計(jì)算(j sun)檢驗(yàn)數(shù)：檢驗(yàn)數(shù)：第77頁/共131頁第七十八頁，共132頁。第78頁/共131頁第七十九頁，共132頁。第79頁/共131頁第八十頁，共132頁。 x1 , x2 , x3 , x4 x1 , x2 , x3 , x4 0 0第80頁/共131頁第八十一頁，共132頁。第81頁/共131頁第八十二頁，共132頁。計(jì)算計(jì)算(j sun)檢驗(yàn)數(shù)，確定進(jìn)基變量、出檢驗(yàn)數(shù)，確定進(jìn)基變量、出基變量，找到主元：基變量，找到主元：第82頁/共131頁第八十三頁，共132頁。第83頁/共131頁第八十四頁，共132頁。再計(jì)算檢驗(yàn)數(shù)，確定再計(jì)算檢驗(yàn)數(shù)，確定(qudng)進(jìn)基變量為進(jìn)基變

16、量為x2：第84頁/共131頁第八十五頁，共132頁。第85頁/共131頁第八十六頁，共132頁。 x1 , x2 x1 , x2 0 0(3) (3) 教材教材p31 2p31 2（3 3）第86頁/共131頁第八十七頁，共132頁。 x1 , x2 , x3 , x4 x1 , x2 , x3 , x4 0 0第87頁/共131頁第八十八頁，共132頁。第88頁/共131頁第八十九頁，共132頁。第89頁/共131頁第九十頁，共132頁。第90頁/共131頁第九十一頁，共132頁。第91頁/共131頁第九十二頁，共132頁。第92頁/共131頁第九十三頁，共132頁。第93頁/共131頁第

17、九十四頁，共132頁。第94頁/共131頁第九十五頁，共132頁。第95頁/共131頁第九十六頁，共132頁。第96頁/共131頁第九十七頁，共132頁。第97頁/共131頁第九十八頁，共132頁。第98頁/共131頁第九十九頁，共132頁。第99頁/共131頁第一百頁，共132頁。第100頁/共131頁第一百零一頁，共132頁。第101頁/共131頁第一百零二頁，共132頁。第102頁/共131頁第一百零三頁，共132頁。第103頁/共131頁第一百零四頁，共132頁。第104頁/共131頁第一百零五頁，共132頁。第105頁/共131頁第一百零六頁，共132頁。第106頁/共131頁第一百

18、零七頁，共132頁。第107頁/共131頁第一百零八頁，共132頁。第108頁/共131頁第一百零九頁，共132頁。重新計(jì)算檢驗(yàn)重新計(jì)算檢驗(yàn)(jinyn)數(shù)，確定進(jìn)基變量，出基數(shù)，確定進(jìn)基變量，出基變量變量第109頁/共131頁第一百一十頁，共132頁。得到得到(d do)最優(yōu)解最優(yōu)解X*=(4,1,9,0,0,0,0)t,最優(yōu)值為最優(yōu)值為z=2，Z=-2第110頁/共131頁第一百一十一頁，共132頁。第111頁/共131頁第一百一十二頁，共132頁。第112頁/共131頁第一百一十三頁，共132頁。第113頁/共131頁第一百一十四頁，共132頁。第114頁/共131頁第一百一十五頁，共132頁。第115頁/共131頁第一百