——單純形原理改PPT學(xué)習(xí)教案

1、會計(jì)學(xué)1單純形原理改單純形原理改通過初等變換把約束方程寫成，方程左邊是一個基變量，右邊是非基變量的形式x x3 38 8 x x1 12x2x2 2x x4 416164x4x1 1 x x5 512124x4x2 2 代入目標(biāo)函數(shù)，將目標(biāo)函數(shù)用非基變量來表達(dá)代入目標(biāo)函數(shù)，將目標(biāo)函數(shù)用非基變量來表達(dá)令非基變量為零，得到基可行解令非基變量為零，得到基可行解X X（0 0） （0 0，0 0，8 8，1616，1212）T TZ= 2 x1+3 x2 第1頁/共24頁在目標(biāo)函數(shù)的表達(dá)式中，只要非基變量的系數(shù)是正數(shù)，在目標(biāo)函數(shù)的表達(dá)式中，只要非基變量的系數(shù)是正數(shù)，就說明目標(biāo)值還有增加的可能，也就是說

2、目前的基可行解就說明目標(biāo)值還有增加的可能，也就是說目前的基可行解還不是最優(yōu)解。還不是最優(yōu)解。 就需要將非基變量與基變量進(jìn)行對換。一般選擇正系數(shù)最大的那個非基變量x2為換入變量，將它換入到基變量中去，同時還要確定基變量中有一個要換出來成為非基變量。可按以下方法來確定換出變量。 當(dāng)將x2定為換入變量后，必須要從x3、x4、x5中換出一個，并要保證其余的都是非負(fù)，即x3、x4、x5 0。 當(dāng)當(dāng)x10時，時， x382x2 0 x416 0 x5124x2 0 只有選擇只有選擇x x2 2minmin（8/28/2，12/412/4）3 3時時 第2頁/共24頁當(dāng)x23時，x50，這就決定了x5為換出

3、變量，用x2去替換x5。 第二輪x2與 x5互換，即x2為基變量，x5為非基變量，為了求得新的基本可行解，并將目標(biāo)函數(shù)z用非基變量x1、 x5表示以判別所求的基本可行解是否為最優(yōu)解 ,需將約束方程組進(jìn)行初等變換，使方程左邊是一個基變量，右邊是非基變量的形式x32 x1+1/2x5x4164x1 x231/41/4x5 令非基變量為零，得到基可行解X X（1 1） （0 0，3 3，2 2，1616，0 0）T Tz= 9+2 xz= 9+2 x1 1 3/4x3/4x5 5第3頁/共24頁即目前的基本可行解不是最優(yōu)解，x1應(yīng)為換入變量。在方程組中，用各方程負(fù)的x1的系數(shù)（如果x1在方程的左邊，

4、則用正的x1系數(shù)）去除對應(yīng)的常數(shù)項(xiàng)，選最小者， x1min（2/1，16/4，）2 第三輪第三輪 x1與 x3互換。將第二輪的方程組進(jìn)行初等變換，使得由基變量x1、x4、x2所構(gòu)成的基為單位矩陣。 x x1 12 2 x x3 3+1/2x+1/2x5 5x x4 48+4x8+4x3 32 x2 x5 5 x x2 23 31/4x1/4x5 5 X X（2 2） （2 2，3 3，0 0，8 8，0 0）T T z = 13 z = 131/2 x1/2 x3 3+1/4x+1/4x5 5 第4頁/共24頁 x5與 x4互換。將約束方程組進(jìn)行初等變換，使得每個約束方程只含一個基變量且基變量

5、的系數(shù)為1。第四輪： x x1 14 41/4x1/4x4 4 x x5 54 42x2x3 31/2 x1/2 x5 5 x x2 22 21/2x1/2x3 31/8x1/8x4 4 X X（3 3） （4 4，2 2，0 0，0 0，4 4）T T z = 14 z = 143/2 x3/2 x3 3-1/8x-1/8x4 4 第5頁/共24頁4 4單純形法的計(jì)算步驟單純形法的計(jì)算步驟不不失失一一般般性性，考考慮慮如如下下的的線線性性規(guī)規(guī)劃劃模模型型 Z=c1x1+c2x2+cmxm+cm+1xm+1+cnxn x1 +a1m+1xm+1+ +a1nxn=b1 x2 + a2m+1xm+

6、1+ +a2nxn=b2 xm+ amm+1xm+1+ +amnxn=bm 即即 nmjijijibxax1 ( i=1，,m),m) 第6頁/共24頁cjc1cmcm+1cnCBXBbx1xmxm+1xnIc1c2cmx1x2xmb1b2bm100001a1,m+1a2,m+1am,m+1a1na2namn12m-z-z 值00m+1nXB列基變量， CB列基變量的價值系數(shù)(目標(biāo)函數(shù)系數(shù))cj行價值系數(shù)，b列方程組右側(cè)常數(shù) 列確定換入變量時的比率計(jì)算值下面一行檢驗(yàn)數(shù)， 中間主要部分約束方程系數(shù)41單純形表單純形表 用表格法求解LP，規(guī)范的表格單純形表如下：第7頁/共24頁檢驗(yàn)數(shù)的表達(dá)形式檢驗(yàn)

7、數(shù)的表達(dá)形式 將將 nmjjijiixabx1 ( i=1，2，,m),m) 代入目標(biāo)函數(shù)中消去基變量：代入目標(biāo)函數(shù)中消去基變量： njminmjnmjjjjijiijjxc)xab(cxcz1111 = = minmjmijijijiix)acc(bc111 令令jjmiijijjzcacc 1 ，又，又 miiibcz10 則則 nmjjjxzz10 z 與當(dāng)前非基變量的關(guān)系與當(dāng)前非基變量的關(guān)系 最優(yōu)性判別定理：最優(yōu)性判別定理： 若基可行解對應(yīng)的檢驗(yàn)數(shù)若基可行解對應(yīng)的檢驗(yàn)數(shù) 0 ( j=1，2，,n),n)，則此解是最優(yōu)解，否則不是最優(yōu)解。，則此解是最優(yōu)解，否則不是最優(yōu)解。j 第8頁/共2

8、4頁用單純形方法求解用單純形方法求解 max z =4040 x1+45x2+24x3 s.t. 0,12023310032 321321321xxxxxxxxxmax max z z = 2 = 2x1+ 3x2s.t. x1 + 2 x2 8 4 x1 16 4 x2 12 x1，x2 0第9頁/共24頁用單純形方法求解用單純形方法求解 max z =4040 x1+45x2+24x3 s.t. 0,12023310032 321321321xxxxxxxxxmax max z z = 2 = 2x1+ 3x2s.t. x1 + 2 x2 8 4 x1 16 4 x2 12 x1，x2 0

9、第10頁/共24頁用單純形方法求解用單純形方法求解 max z =4040 x1+45x2+24x3 s.t. 0,12023310032 321321321xxxxxxxxxmax max z z = 2 = 2x1+ 3x2s.t. x1 + 2 x2 8 4 x1 16 4 x2 12 x1，x2 0第11頁/共24頁cjCB XBbx1x2x3x4x5-z 2 3 0 0 0 1 2 1 0 0 4 0 0 1 0 0 4 0 0 1 0 2 3 0 0 000081612x3x4x54-3例例 1 1 的的初初始始單單純純形形表表：cjCB XBbx1x2x3x4x5-z 2 3 0

10、 0 0 2 1 0 1 0 -1/2 - 9 2 0 0 0 -3/4003x3x4x224-( ) 3 0 1 0 0 1/4 16 4 0 0 1 0X(0)(0)=(0=(0，0 0，8 8，1616，12)12)T T， z z0 0 =0=0第12頁/共24頁用單純形方法求解用單純形方法求解 max z =4040 x1+45x2+24x3 s.t. 0,12023310032 321321321xxxxxxxxxmax max z z = 2 = 2x1+ 3x2s.t. x1 + 2 x2 8 4 x1 16 4 x2 12 x1，x2 0第13頁/共24頁cjCB XBbx1

11、x2x3x4x5-z 2 3 0 0 0 1 2 1 0 0 4 0 0 1 0 0 4 0 0 1 0 2 3 0 0 000081612x3x4x54-3例例 1 1 的的初初始始單單純純形形表表：cjCB XBbx1x2x3x4x5-z 2 3 0 0 0 2 1 0 1 0 -1/2 - 9 2 0 0 0 -3/4003x3x4x224-( ) 3 0 1 0 0 1/4 16 4 0 0 1 0X(0)(0)=(0=(0，0 0，8 8，1616，12)12)T T， z z0 0 =0=0第14頁/共24頁cjCB XBbx1x2x3x4x5-z 2 3 0 0 0 2 1 0

12、1 0 -1/2-13 0 0 -2 0 1/4203x1x4x2-412 3 0 1 0 0 1/4 8 0 0 -4 1 2cjCB XBbx1x2x3x4x5-z 2 3 0 0 0 2 1 0 1 0 -1/2 -9 2 0 0 0 -3/4003x3x4x224- 3 0 1 0 0 1/4 16 4 0 0 1 0( ) X X(1)(1)=(0=(0，3 3，2 2，1616，0)0)T T， z z1 1 =9=9第15頁/共24頁用單純形方法求解用單純形方法求解 max z =4040 x1+45x2+24x3 s.t. 0,12023310032 321321321xxxx

13、xxxxxmax max z z = 2 = 2x1+ 3x2s.t. x1 + 2 x2 8 4 x1 16 4 x2 12 x1，x2 0第16頁/共24頁cjCB XBbx1x2x3x4x5-z 2 3 0 0 0 1 2 1 0 0 4 0 0 1 0 0 4 0 0 1 0 2 3 0 0 000081612x3x4x54-3例例 1 1 的的初初始始單單純純形形表表：cjCB XBbx1x2x3x4x5-z 2 3 0 0 0 2 1 0 1 0 -1/2 - 9 2 0 0 0 -3/4003x3x4x224-( ) 3 0 1 0 0 1/4 16 4 0 0 1 0X(0)(

14、0)=(0=(0，0 0，8 8，1616，12)12)T T， z z0 0 =0=0第17頁/共24頁cjCB XBbx1x2x3x4x5-z 2 3 0 0 0 2 1 0 1 0 -1/2-13 0 0 -2 0 1/4203x1x4x2-412 3 0 1 0 0 1/4 8 0 0 -4 1 2cjCB XBbx1x2x3x4x5-z 2 3 0 0 0 2 1 0 1 0 -1/2 -9 2 0 0 0 -3/4003x3x4x224- 3 0 1 0 0 1/4 16 4 0 0 1 0( ) X X(1)(1)=(0=(0，3 3，2 2，1616，0)0)T T， z z1

15、 1 =9=9第18頁/共24頁用單純形方法求解用單純形方法求解 max z =4040 x1+45x2+24x3 s.t. 0,12023310032 321321321xxxxxxxxxmax max z z = 2 = 2x1+ 3x2s.t. x1 + 2 x2 8 4 x1 16 4 x2 12 x1，x2 0第19頁/共24頁cjCB XBbx1x2x3x4x5-z 2 3 0 0 0 1 2 1 0 0 4 0 0 1 0 0 4 0 0 1 0 2 3 0 0 000081612x3x4x54-3例例 1 1 的的初初始始單單純純形形表表：cjCB XBbx1x2x3x4x5-

16、z 2 3 0 0 0 2 1 0 1 0 -1/2 - 9 2 0 0 0 -3/4003x3x4x224-( ) 3 0 1 0 0 1/4 16 4 0 0 1 0X(0)(0)=(0=(0，0 0，8 8，1616，12)12)T T， z z0 0 =0=0第20頁/共24頁cjCB XBbx1x2x3x4x5-z 2 3 0 0 0 2 1 0 1 0 -1/2-13 0 0 -2 0 1/4203x1x4x2-412 3 0 1 0 0 1/4 8 0 0 -4 1 2cjCB XBbx1x2x3x4x5-z 2 3 0 0 0 2 1 0 1 0 -1/2 -9 2 0 0 0

17、 -3/4003x3x4x224- 3 0 1 0 0 1/4 16 4 0 0 1 0( ) X X(1)(1)=(0=(0，3 3，2 2，1616，0)0)T T， z z1 1 =9=9第21頁/共24頁cjCB XBbx1x2x3x4x5-z 2 3 0 0 0 2 1 0 1 0 -1/2-13 0 0 -2 0 1/4203x1x4x2-412 3 0 1 0 0 1/4 8 0 0 -4 1 2( )cjCB XBbx1x2x3x4x5-z 2 3 0 0 0 4 1 0 0 1/4 0-14 0 0 -1.5 -1/8 0203x1x5x2 2 0 1 1/2 -1/8 0 4 0 0 -2 1/2 1 X X(2)(2)=(2=(2，3 3，0 0，8 8，0)0)T T， z z2 2 =13=13 X X(3)(3)=(4=(4，2 2，0 0，0, 4)0, 4)T T， z z3 3 =14=14第22頁/共24頁 (5).以 alk為主元素進(jìn)行迭代(即用高斯消去法或稱為旋轉(zhuǎn)變換)，把 xk所對應(yīng)的列向量變換為(0，0，1，0)T，將XB列中的第l個基