列初始單純形表PPT學(xué)習(xí)教案

1、會計學(xué)1 列初始單純形表列初始單純形表 0. . . . . 1111 11 221122 111111 nnmmmm mnmnmmmm nnmm nnmm xcxcxcxcZ bxaxax bxaxax bxaxax 第1頁/共42頁 xxxx mn12 2 1 0 0 0 j c B Cb B X jj zc 檢驗數(shù) b b m 1 x x m 1 c cm 1 單純形表結(jié)構(gòu) 單純形表 24/6 5/1 min A 0 z nm cccc 21C 第2頁/共42頁 xxxx mn12 2 1 0 0 0 j c B Cb B X jj zc 24/6 5/1 min C 檢驗數(shù) b b m

2、 1 x x m 1 c cm 1 單純形表結(jié)構(gòu) 單純形表 A 0 z )0 , 0 ,( 1 m bbX 基可行解： 第3頁/共42頁 單純形表結(jié)構(gòu) 單純形表 xxxx mn12 2 1 0 0 0 j c B Cb B X jj zc 24/6 5/1 min C 檢驗數(shù) b b m 1 x x m 1 c cm 1 A 0 z j n mj j jjj j n mj jj m i ijij m i ii xZZ Zc xZcZZ acZbcZ 1 0 1 0 1 1 0 )( )( 檢驗數(shù)令： 令： 有時不寫此項 第4頁/共42頁 單純形表結(jié)構(gòu) 單純形表 xxxx mn12 2 1 0

3、0 0 j c B Cb B X jj zc 24/6 5/1 min C 檢驗數(shù) b b m 1 x x m 1 c cm 1 A 0 z j n mj j jjj j n mj jj m i ijij m i ii xZZ Zc xZcZZ acZbcZ 1 0 1 0 1 1 0 )( )( 檢驗數(shù)令： 令： j c mj j a a 1 j 第5頁/共42頁 單純形表結(jié)構(gòu) 單純形表 xxxx mn12 2 1 0 0 0 j c B Cb B X jj zc 24/6 5/1 min C 檢驗數(shù) b b m 1 x x m 1 c cm 1 A 0 z kmm km a a , , 1

4、 km 不妨設(shè)此為主列 klm l kim kim i i a b a a b 0 min l 主行 第6頁/共42頁 單純形表結(jié)構(gòu) 單純形表 xxxx mn12 2 1 0 0 0 j c B Cb B X jj zc 24/6 5/1 min C 檢驗數(shù) b b m 1 x x m 1 c cm 1 A 0 z kmm km a a , , 1 km l kml a , 主元 第7頁/共42頁 0, 5 2426 155 2max 21 21 21 2 21 xx xx xx x xxz 例、用單純形表求解LP問題 第8頁/共42頁 0, 5 2426 155 0002max 51 521

5、 421 32 54321 xx xxx xxx xx xxxxxz 第9頁/共42頁 2 1 0 0 0 0 15 0 5 1 0 0 0 24 6 2 0 1 0 0 5 1 1 0 0 1 2 1 0 0 0 j c B Cb B X 1 x 3 x 2 x 4 x 5 x jj zc 3 x 4 x 5 x 24/6 5/1 min 主元化為1 主列單位向量 換出 換入 1 x 4 x 表1：列初始單純形表 （單位矩陣對應(yīng)的變量為基變量） 正檢驗數(shù)中最大者對應(yīng)的列為主列 第10頁/共42頁 2 1 0 0 0 0 15 0 5 1 0 0 2 4 1 2/6 0 1 /6 0 0 1

6、0 4/6 0 -1/6 1 0 1/3 0 -1/3 0 j c B Cb B X 1 x 3 x 2 x 4 x 5 x jj zc 3 x 1 x 5 x 15/5 24/2 6/4 min 0*5 2*2/6 +0*4/6 1- 2/3= 表2：換基 （初等行變換，主列化為單位向量，主元為1） 檢驗數(shù)0 確定主列 最小 確定主列 主元 第11頁/共42頁 2 1 0 0 0 0 15/2 0 0 1 5/4 -15/2 2 7/2 1 0 0 1/4 -1/2 1 3/2 0 1 0 -1/4 3/2 0 0 0 -1/4 -1/2 j c B Cb B X 1 x 3 x 2 x 4

7、 x 5 x jj zc 3 x 1 x 2 x min 檢驗數(shù)0，則目標函數(shù) 不可能實現(xiàn)最優(yōu)。 第21頁/共42頁 0, 1 2 32 4 11 2 3 321 31 321 321 321 xxx xx xxx xxx xxxMinZ 321 3xxxMaxz 一、大 M 法 第22頁/共42頁 0, 1 2 3 2 4 11 2 003 7654321 731 65321 4321 7654321 xxxxxxx xxx xxxxx xxxx MxMxxxxxxMinZ7654321 003MxMxxxxxxMaxz 一、大 M 法 l加入松弛變量和剩余變量進行標準 化, 加入人工變量構(gòu)

8、造初始可行基. 第23頁/共42頁 j 0 一、大 M 法 l用單純形法求解（見下頁）。 目標函數(shù)中添加“罰因子” -M為人工變量系數(shù)，只要人 工變量0，則目標函數(shù) 不可能實現(xiàn)最優(yōu)。 第24頁/共42頁 1 -2 1 -4 1 2 -2 0 1 3-63-6M M -1 3M-1M M -1 3M-1 3 -1 -1 x x1 x x2 x x3 0 x x4 11 -M x x6 3 -M x x7 1 C j - Z j C j CB XB b 1 0 0 -1 0 0 0 -M 0 0 x x4 x x5 11 3/2 1 0 0 1 0 0 1 0 0 - M - M x x6 x x

9、7 表1（初始單純形表） 一、大 M 法（單純形法求解 ） i 第25頁/共42頁 3 -2 0 0 1 0 -2 0 1 1 1 M M-1-1 0 0 3 -1 -1 x x1 x x2 x x3 0 x x4 10 -M x x6 1 -1 x x3 1 C j - Z j C j CB XB b 1 0 0 -1 0 0 0 -M 0 0 x x4 x x5 1 0 -1 1 -2 0 1 0 1 1-3 3M M - M - M x x6 x x7 一、大 M 法（單純形法求解 ） 表2 i 第26頁/共42頁 3 0 0 0 1 0 -2 0 1 1 0 0 3 -1 -1 x x

10、1 x x2 x x3 0 x x4 12 -1 x x2 1 -1 x x3 1 C j - Z j C j CB XB b 1 -2 0 -1 0 0 0 -1 0 0 x x4 x x5 4 2 -5 1 -2 0 1 1-1-M -1M -1 -M-M - M - M x x6 x x7 表3 一、大 M 法（單純形法求解 ） i 第27頁/共42頁 1 0 0 0 1 0 0 0 1 0 0 0 3 -1 -1 x x1 x x2 x x3 3 x x1 4 -1 x x2 1 -1 x x3 9 2 C j CB XB b 1/3 -2/3 0 -1 2/3 -4/3 -1/3 -

11、1/3 0 0 x x4 x x5 2/3 -5/3 1 -2 4/3 -7/3 1/3-1/3-M 2/3-MM 2/3-M - M - M x x6 x x7 表4 一、大 M 法（單純形法求解 ） 9 1 4 3 2 1 x x x 檢驗數(shù)均非正，此為最終單純形表 i 第28頁/共42頁 M在計算機上處理困難。 分階段處理 先求初始基，再求解。 二、兩階段法 第29頁/共42頁 0.,., . . . . . , 121 2211 222222121 111212111 21 mnnn mmnnmnmm nnn nnn mnnn xxxxx bxxaxaxa bxxaxaxa bxxax

12、axa xxxMin 第30頁/共42頁 二、兩階段法 下面舉例說明，仍用大M法的例。 第31頁/共42頁 0, 1 2 32 4 11 2 321 31 321 321 xxx xx xxx xxx 321 3xxxMaxz 例： 二、兩階段法 第32頁/共42頁 0, 1 2 3 2 4 11 2 7654321 731 65321 4321 76 xxxxxxx xxx xxxxx xxxx xxMin 二、兩階段法 l構(gòu)造第一階段問題并求解解： 用單純形法求解 第33頁/共42頁 二、兩階段法（第一階段、求min ） 1 -2 1 -4 1 2 -2 0 1 -6 1 3 0 0 0

13、x x1 x x2 x x3 0 x x4 11 -1 x x6 3 -1 x x7 1 C i CB XB b 1 0 0 0 -1 1 0 0 0 0 -1 0 0 0 -1 - 1 x x4 x x5 x x6 0 11 0 3/2 1 1 0 - 1 x x7 表1 jj zc i 第34頁/共42頁 -1 - -2 1 1 - -3 - 1 x x7 3 -2 0 0 1 0 -2 0 1 0 1 0 0 0 0 x x1 x x2 x x3 0 x x4 10 -1 x x6 1 0 x x3 1 C i CB XB b 1 0 0 0 -1 1 0 0 0 0 -1 0 0 0

14、-1 x x4 x x5 x x6 二、兩階段法（第一階段、求min ） 表2 jj zc i 第35頁/共42頁 -5 4 -2 - 1 - -1 - 1 x x7 3 0 0 0 1 0 -2 0 1 0 0 0 0 0 0 x x1 x x2 x x3 0 x x4 12 0 x x2 1 0 x x3 1 C i CB XB b 1 -2 2 0 -1 1 0 0 0 0 0 -1 0 0 -1 x x4 x x5 x x6 二、兩階段法（第一階段、求min ） 表3：最終單純形表 不含人工變量且=0 jj zc i 第36頁/共42頁 二、兩階段法 3 0 0 0 1 0 -2 0

15、1 3 -1 -1 x x1 x x2 x x3 0 x x4 12 -1 x x2 1 -1 x x3 1 C i CB XB b 1 -2 2 0 -1 1 0 0 0 0 0 x x4 x x5 1 0 0 0 -1 jj zc i 第37頁/共42頁 二、兩階段法 1 0 0 0 1 0 0 0 1 3 -1 -1 x x1 x x2 x x3 3 x x1 4 -1 x x2 1 -1 x x3 9 C i CB XB b 1/3 -2/3 0 -1 2/3 -4/3 0 0 x x4 x x5 0 0 0 -1/3 -1/3 9 1 4 3 2 1 x x x i jj zc 第38頁/共42頁 j 0 l1、目標函數(shù)極小化時解的最優(yōu)性判