單純形法原理表格形式和人工變量法

單純形法原理表格形式和人工變量法第1頁，共19頁，2023年，2月20日，星期三2、舉例第2頁，共19頁，2023年，2月20日，星期三步驟：1、化標(biāo)準(zhǔn)型（SLP）第3頁，共19頁，2023年，2月20日，星期三2、找初始基可行解3、判斷第4頁，共19頁，2023年，2月20日，星期三4、換基迭代*換基：找一個(gè)非基變量作為換入變量，同時(shí)確定一個(gè)基變量為換出變量。*依據(jù)原則：1)新的基可行解能使目標(biāo)值增加；2)新的基仍然是可行基。(1)確定換入變量：變量下標(biāo)最小的（勃蘭特法則）變量對(duì)應(yīng)的價(jià)值系數(shù)最大的第5頁，共19頁，2023年，2月20日，星期三(2)確定換出變量第6頁，共19頁，2023年，2月20日，星期三*迭代（求新的基可行解）主元素第7頁，共19頁，2023年，2月20日，星期三5、判斷→代入目標(biāo)函數(shù)得第8頁，共19頁，2023年，2月20日，星期三6、確定進(jìn)基變量和出基變量第9頁，共19頁，2023年，2月20日，星期三7、換基迭代第10頁，共19頁，2023年，2月20日，星期三8、判斷代入目標(biāo)函數(shù)：最優(yōu)解：第11頁，共19頁，2023年，2月20日，星期三二、表格形式的單純形法

1、表的結(jié)構(gòu)及含義第12頁，共19頁，2023年，2月20日，星期三

2、計(jì)算步驟1)化標(biāo)準(zhǔn)型，建立初始單純形表;2)計(jì)算非基變量的檢驗(yàn)系數(shù)，若所有檢驗(yàn)系數(shù)都小于等于零，則已得到最優(yōu)解。否則轉(zhuǎn)一步;4)換基迭代，求出新的基可行解，轉(zhuǎn)步驟二;第13頁，共19頁，2023年，2月20日，星期三

10500

00

34105201

98第14頁，共19頁，2023年，2月20日，星期三cj

5300

bcBxB

x1x2x3x4

05x3x1

c011/5de01

2a

δj

b-1fgZ=10求出a,b,c,d,e,f,g的值。第15頁，共19頁，2023年，2月20日，星期三1、z=10=0×2+5×a→a=2

2、c=0,d=1,b=0,f=0;3、g=0-(05)(1/51)’=-54、3-(05)(0e)’=-1→e=4/5小結(jié)：單純形法的前提條件是SLP存在一個(gè)初始的單位基矩陣。第16頁，共19頁，2023年，2月20日，星期三三、人工變量法1、思路——人為構(gòu)造一個(gè)單位矩陣人工變量人工變量第17頁，共19頁，2023年，2月20日，星期三cj3-250-M-Mbθ

cBxbx1x2x3x4x5x6-M-Mx5x6

23410221201737/43/2δj3+3M-2+4M5+4M6M↑00→x5x4

-M

0-3-2101-21111/2101/23/2

δj3-3M–2-2M5+M00-3M↑→13…

53

x3

x102/516/52/51/514/502/5-1/52/511/52/5

δj0-32/50