求解線性規(guī)劃的單純形法(1)課件

1、求解線性規(guī)劃的單純形法求解線性規(guī)劃的單純形法NO找到相鄰的基本可行解最優(yōu)性檢驗(yàn)當(dāng)前的CPF是最優(yōu)解嗎？開(kāi)始找到初始的基本可行解單純形法思路YES停止求解線性規(guī)劃的單純形法求解線性規(guī)劃的單純形法 Q1：初始基本可行解如何找？ 標(biāo)準(zhǔn)型 基本解 Q2：怎樣判斷最優(yōu)？ 最優(yōu)性條件 Q3：如何找下一個(gè)相鄰的基本可行解？ 確定移動(dòng)的方向 確定在何處停下 確定新的基本可行解關(guān)鍵問(wèn)題求解線性規(guī)劃的單純形法求解線性規(guī)劃的單純形法例：用單純形法求解以下線性規(guī)劃問(wèn)題求解線性規(guī)劃的單純形法求解線性規(guī)劃的單純形法首先將模型轉(zhuǎn)化成標(biāo)準(zhǔn)形式求解線性規(guī)劃的單純形法求解線性規(guī)劃的單純形法Q1：確定初始的基本可行解 選擇原點(diǎn)：選

2、擇原點(diǎn)： 令決策變量 x1= x2 = 0得：得：X0 = ( 0，0，3，4)T 選擇單元陣作為初始基：選擇單元陣作為初始基：令非基變量 x1= x2 = 0得：得：X0 = ( 0，0，3，4)T12341 110(,)1201Aa a a a3410(,)01Ba a求解線性規(guī)劃的單純形法求解線性規(guī)劃的單純形法 非最優(yōu)：增加非基變量的值，可以使得目標(biāo)函數(shù)Z值增加 基變量在目標(biāo)函數(shù)中的系數(shù)為0 非基變量在目標(biāo)函數(shù)中的系數(shù)=0Q2：最優(yōu)性檢驗(yàn)檢驗(yàn)數(shù)求解線性規(guī)劃的單純形法求解線性規(guī)劃的單純形法 迭代步驟迭代步驟1：確定移動(dòng)的方向：確定移動(dòng)的方向 例：例：z = 2x1 + 3x2 選擇 x1

3、？Z的增長(zhǎng)率=2 選擇 x2 ？Z的增長(zhǎng)率=3 32，選擇x2！ 進(jìn)基變量的選擇： 選擇非基變量的系數(shù)最大的！Q3：如何找下一個(gè)相鄰的基本可行解確定進(jìn)基變量確定進(jìn)基變量檢驗(yàn)數(shù)的絕對(duì)值哦求解線性規(guī)劃的單純形法求解線性規(guī)劃的單純形法 迭代步驟迭代步驟2：確定在何處停下：確定在何處停下 增加x x2 2 的值， x1 =0 所有變量非負(fù) 令x2 =2，從而 x4 =0 離基變量的選擇： 最小比值法確定離基變量確定離基變量1233212442 + 3 3 + 2 + =4 42 xxxxxxxxxx32242233 0 314420 =22xxxxxx最小比值法Q3：如何找下一個(gè)相鄰的基本可行解求解線

4、性規(guī)劃的單純形法求解線性規(guī)劃的單純形法迭代步驟迭代步驟3：確定新的基本可行解：確定新的基本可行解u原方程 尋找新的基本可行解： 初等數(shù)學(xué)變換121231242 -3 =0 + 3 + 2 + =4 Zxxxxxxxx初等數(shù)學(xué)初等數(shù)學(xué)變換變換初始初始BF解解新的新的BF解解非基變量（Non-basics）x1 =0，x2 =0 x1 =0，x4 =0基變量（Basics）x3 =3，x4 =4x3 =？，x2 =21X*=（0, 2, 1, 0）Z*=6+ x1/2- 3x4/26u新方程Q3：如何找下一個(gè)相鄰的基本可行解非基變量x1的系數(shù)是正數(shù)！非最優(yōu)解！14134124/2 + 3 /2 =

5、6 /2 + - /2 1 /2 + 2 + /2 =2 Zxxxxx xxx求解線性規(guī)劃的單純形法求解線性規(guī)劃的單純形法 第第2次迭代次迭代 確定進(jìn)基變量確定進(jìn)基變量x1 確定離基變量確定離基變量3142141/2/202/2/20 xxxxxx 134124/2 - /2 1/2 + + /2 =2xxxxxx1124xx非基變量x4=012x 30 x 確定確定x x3 3為離基變量為離基變量 初等行變換初等行變換14134124/2 + 3 /2 =6 /2 + - /2 1 /2 + 2 + /2 =2 Zxxxxx xxx初等初等行變換行變換34134234 + + =7 2 -

6、2 - + =1 Zxxxxx xxx非基變量系數(shù)0，最優(yōu)！Z*=7,X*=(2,1,0,0)求解線性規(guī)劃的單純形法求解線性規(guī)劃的單純形法目標(biāo)函數(shù)無(wú)界的情況min z=-x1-2x2 s.t.-x1+x21 x22 x1,x20用單純形法求解以下線性規(guī)劃模型。求解線性規(guī)劃的單純形法求解線性規(guī)劃的單純形法最優(yōu)性檢驗(yàn)：最優(yōu)性檢驗(yàn)：j 0 ？然后確定初始基本可行解 X0 = (0, 0, 1, 2)T z0 = 當(dāng)前解當(dāng)前解 X0 非優(yōu)；非優(yōu)；須由須由X0 轉(zhuǎn)化為另一個(gè)基本可行解轉(zhuǎn)化為另一個(gè)基本可行解 X1。：讓：讓X0 中的一個(gè)中的一個(gè)非基變量非基變量進(jìn)基進(jìn)基，去替換原來(lái)的一個(gè)，去替換原來(lái)的一個(gè)（

7、離基離基）。）。首先標(biāo)準(zhǔn)化，令z=-z，引入松弛變量x3, x4max z=x1+2x2 s.t.-x1+x2+x3 =1 x2 +x4=2 x1,x2,x3,x40 x1仍為非基變量，其值為仍為非基變量，其值為0。x3 = 1 - -x2x4 = 2 - -x2 x2 1/1 x2 2/1w （） ： x2 min 1/1，2/1 = 1 x2 = min 1/1，2/1 = 1 x3x3為為離基變量離基變量w 進(jìn)基進(jìn)基（）：）： 在在中選擇中選擇進(jìn)基進(jìn)基。 min jj0 = k xk 進(jìn)基進(jìn)基 min - -1，- -2 = - -2= 2 x2 進(jìn)基進(jìn)基z - x1 -2x2 = -

8、x1 + x2 +x3 = 1 x2 +x4 = 2 ()0由由 有有求解線性規(guī)劃的單純形法求解線性規(guī)劃的單純形法求解線性規(guī)劃的單純形法求解線性規(guī)劃的單純形法 1主列主列進(jìn)基進(jìn)基主元主元 z - - x1 - - 2 x2 = 0- - x1 + x2 +x3 = 1 1 x2 +x4 = 2 ()min以以主列主列中中為為，同行，同行為為，求，求；按按確定確定和和，以及，以及。求解線性規(guī)劃的單純形法求解線性規(guī)劃的單純形法 () -x1 + x2 +x3 = 1 得得稱為單純形法的一次稱為單純形法的一次迭代迭代。z- - x1 - -2x2 = 0 - - x1+ x2 +x3 = 1 1 x2 +x4 = 2 ()10 x1 -x3 + x4 = 1 z-3x1 +2x3 = 20的的是把是把變?yōu)樽優(yōu)樽冏優(yōu)闉?，其余變?yōu)?，其余變?yōu)?。用用將將X0 轉(zhuǎn)化為轉(zhuǎn)化為另一個(gè)基本另一個(gè)基本可行解可行解 。求解線性規(guī)劃的單純形法求解線性規(guī)劃的單純形法() - x1 + x2 +x3 = 1 1x1 -x3 + x4 = 1 z-3x1 +2x3 = 20min() z -x3 +3x4 = 5x2 + x4 = 2 x1 -x3 + x4 = 1 0得得 參數(shù)=0 x1 = 1+ x3 -x4=0 x2、 x1不受x3限制！求解線性規(guī)劃的單純形法求解線性規(guī)劃的單純形法目標(biāo)函數(shù)無(wú)界的線性規(guī)