《管理運籌學》02-2求解線性規(guī)劃的單純形法ppt課件

1、求解線性規(guī)劃的單純形法求解線性規(guī)劃的單純形法單純形法思緒YES停頓求解線性規(guī)劃的單純形法求解線性規(guī)劃的單純形法 Q1：初始根本可行解如何找？：初始根本可行解如何找？ 規(guī)范型規(guī)范型 根本解根本解 Q2：怎樣判別最優(yōu)？：怎樣判別最優(yōu)？ 最優(yōu)性條件最優(yōu)性條件 Q3：如何找下一個相鄰的根本可行解？：如何找下一個相鄰的根本可行解？ 確定挪動的方向確定挪動的方向 確定在何處停下確定在何處停下 確定新的根本可行解確定新的根本可行解關(guān)鍵問題求解線性規(guī)劃的單純形法求解線性規(guī)劃的單純形法例：用單純形法求解以下線性規(guī)劃問題求解線性規(guī)劃的單純形法求解線性規(guī)劃的單純形法首先將模型轉(zhuǎn)化成規(guī)范方式求解線性規(guī)劃的單純形法求解

2、線性規(guī)劃的單純形法Q1：確定初始的根本可行解 選擇原點：選擇原點： 令決策變量令決策變量 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)：添加非基變量的值，可以使得目的函數(shù)Z值添加 基變量在目的函數(shù)中的系數(shù)為0 非基變量在目的函數(shù)中的系數(shù)=0Q2：最優(yōu)性檢驗檢驗數(shù)求解線性規(guī)劃的單純形法求解線性規(guī)劃的單純形法 迭代步驟迭代步驟1：

3、確定挪動的方向：確定挪動的方向 例：例：z = 2x1 + 3x2 選擇選擇 x1 ？Z的增長率的增長率=2 選擇選擇 x2 ？Z的增長率的增長率=3 32，選擇，選擇x2！ 進基變量的選擇：進基變量的選擇： 選擇非基變量的系數(shù)最大的！選擇非基變量的系數(shù)最大的！Q3：如何找下一個相鄰的根本可行解確定進基變量確定進基變量檢驗數(shù)的絕對值哦求解線性規(guī)劃的單純形法求解線性規(guī)劃的單純形法 迭代步驟迭代步驟2：確定在何處停下：確定在何處停下 添加添加x2 的值，的值， x1 =0 一切變量非負一切變量非負 令令x2 =2，從而，從而 x4 =0 離基變量的選擇：離基變量的選擇： 最小比值法最小比值法確定離

4、基變量確定離基變量1233212442 + 3 3 + 2 + =4 42 xxxxxxxxxx32242233 0 314420 =22xxxxxx最小比值法Q3：如何找下一個相鄰的根本可行解求解線性規(guī)劃的單純形法求解線性規(guī)劃的單純形法迭代步驟迭代步驟3：確定新的根本可行解：確定新的根本可行解原方程原方程 尋覓新的根本可行解：尋覓新的根本可行解：初等數(shù)學變換初等數(shù)學變換121231242 -3 =0 + 3 + 2 + =4 Zxxxxxxxx初等數(shù)學初等數(shù)學變換變換初始初始BF解解新的新的BF解解非基變量（Non-basics）x1 =0，x2 =0 x1 =0，x4 =0基變量（Basi

5、cs）x3 =3，x4 =4x3 =？，x2 =21X*=0, 2, 1, 0Z*=6+ x1/2- 3x4/26u新方程Q3：如何找下一個相鄰的根本可行解非基變量x1的系數(shù)是正數(shù)！非最優(yōu)解！14134124/2 + 3 /2 =6 /2 + - /2 1 /2 + 2 + /2 =2 Zxxxxx xxx求解線性規(guī)劃的單純形法求解線性規(guī)劃的單純形法 第第2次迭代次迭代 確定進基變量確定進基變量x1 確定離基變量確定離基變量3142141/2/202/2/20 xxxxxx 134124/2 - /2 1/2 + + /2 =2xxxxxx1124xx非基變量x4=012x 30 x 確定確定

6、x3x3為離基變量為離基變量 初等行變換初等行變換14134124/2 + 3 /2 =6 /2 + - /2 1 /2 + 2 + /2 =2 Zxxxxx xxx初等初等行變換行變換34134234 + + =7 2 - 2 - + =1 Zxxxxx xxx非基變量系數(shù)0，最優(yōu)！Z*=7,X*=(2,1,0,0)求解線性規(guī)劃的單純形法求解線性規(guī)劃的單純形法目的函數(shù)無界的情況min z=-x1-2x2 s.t.-x1+x21 x22 x1,x20用單純形法求解以下線性規(guī)劃模型。求解線性規(guī)劃的單純形法求解線性規(guī)劃的單純形法最優(yōu)性檢驗：最優(yōu)性檢驗：然后確定初始根本可行解 X0 = (0, 0,

7、 1, 2)T z0 = 0 當前解當前解 X0 非優(yōu)；非優(yōu)；須由須由X0 轉(zhuǎn)化為另一個根本可行解轉(zhuǎn)化為另一個根本可行解 X1。首先規(guī)范化，令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 離基最小比值規(guī)那么離基最小比值規(guī)那么 ：w x2 min 1/1，2/1 = 1w x2 = min 1/1，2/1 = 1 x3x3為離基變量為離基變量w 進基最小檢驗數(shù)規(guī)那么：進基最小檢驗數(shù)規(guī)那么

8、：w 在負檢驗數(shù)中選擇最小的進基。在負檢驗數(shù)中選擇最小的進基。w min jj0 = k xk 進進基基w min -1，-2 = -2= 2 x2 進基進基z - x1 -2x2 = 0 - x1 + x2 +x3 = 1 x2 +x4 = 2 ()0由由 有有求解線性規(guī)劃的單純形法求解線性規(guī)劃的單純形法求解線性規(guī)劃的單純形法求解線性規(guī)劃的單純形法 1主列主列進基進基主元主元 z - x1 - 2 x2 = 0- x1 + x2 - x1 + x2 +x3 = 1 +x3 = 1 1 x2 +x4 = 2 ()min以主列中正值元素為分母，同行右端常數(shù)為分子，求比值；以主列中正值元素為分母，

9、同行右端常數(shù)為分子，求比值；按最小比值規(guī)那么確定主方程和主元素，以及離基變量。按最小比值規(guī)那么確定主方程和主元素，以及離基變量。求解線性規(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用換基運算用換基運算將將X0 轉(zhuǎn)化為轉(zhuǎn)化為另一個根本另一個根本可行解可行解 X1。求解線性規(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ī)劃的單純形法目