【正文】 10310112A??????10011Br(B1)=2， B1是一個(gè)初始基 ,x x4為基變量 ， x x2為非基變量 ， 令 x1=0、 x2=0由約束方程知 x3=x4=30得到初始基本可行解 X(1)=(0,0,40,30)T 單純形法 Simplex Method 2/4/2023 制作與教學(xué) 線性規(guī)劃 Linear Programming Page 62 以上得到的一組基可行解是不是最優(yōu)解，可以從目標(biāo)函數(shù)中的系數(shù)看出。目標(biāo)函數(shù) Z=3x1+4x2中 x1的系數(shù)大于零，如果 x1為一正數(shù)，則 Z的值就會(huì)增大，同樣若 x2不為零為一正數(shù)，也能使 Z的值增大；因此只要目標(biāo)函數(shù)中非基變量的系數(shù)大于零，那么目標(biāo)函數(shù)就沒有達(dá)到最大值，即沒有找到最優(yōu)解，判別線性規(guī)劃問題是否達(dá)到最優(yōu)解的數(shù)稱為檢驗(yàn)數(shù)，記作 λj , j=1,2…, n。 本例中 λ1=3,λ2=4,λ3=0,λ4=0。參看表 （ a）。 最優(yōu)解判斷標(biāo)準(zhǔn) 當(dāng)所有檢驗(yàn)數(shù) λj≤0（ j=1， … ， n）時(shí)，基本可行解為最優(yōu)解。 當(dāng)目標(biāo)函數(shù)中有基變量 xi時(shí)，利用約束條件將目標(biāo)函數(shù)中的 xi消去即可求出檢驗(yàn)數(shù)。 單純形法 Simplex Method 檢驗(yàn)數(shù) 目標(biāo)函數(shù)用非基變量表達(dá)時(shí)的變量系數(shù) 2/4/2023 制作與教學(xué) 線性規(guī)劃 Linear Programming Page 63 進(jìn)基列 出基行 bi /ai2， ai20 θi 表 14 (1) XB x1 x2 x3 x4 b x3 2 1 1 0 40 x4 1 3 0 1 30 λj 3 4 0 0 (2) x3 x2 λj (3) x1 x2 λj 基變量 1 10 0 0 1/3 0 1/3 10 5/3 1 1/3 40 5/3 0 4/3 30 1 0 3/5 1/5 18 0 1 1/5 2/5 4 0 0 1 1 將 3化為 1 乘以1/3后得到 單純形法 Simplex Method 30 18 2/4/2023 制作與教學(xué) 線性規(guī)劃 Linear Programming Page 64 最優(yōu)解 X=(18， 4， 0， 0)T，最優(yōu)值 Z=70 O 20 30 10 40 (3,4) X(3)=(18,4) 最優(yōu)解 X=(18,4) 最優(yōu)值 Z=70 402 21 ?? xx 21 ?? xx??????????????0,30340243max432142132121xxxxxxxxxxxxZX(1)=(0,0) 20 10 x2 x1 30 單純形法 Simplex Method 0,0402212121??????xxxxxxX(2)=(0,10) 2/4/2023 制作與教學(xué) 線性規(guī)劃 Linear Programming Page 65 單純形法全過(guò)程的計(jì)算 ， 可以用列表的方法計(jì)算更為簡(jiǎn)潔 ，這種表格稱為單純形表 （ 表 ） 。 計(jì)算步驟： ，列出初始單純形表，求出檢驗(yàn)數(shù)。其中基變量的檢驗(yàn)數(shù)必為零； ： （ a） 若 λj≤０ （ j＝１ ， ２ ， … ， n） 得到最解； （ b） 某個(gè) λk0且 aik≤０ （ i=1， 2,… ,m） 則線性規(guī)劃具有無(wú)界解 (見例 )。 （ c） 若存在 λk0且 aik (i=1,… ,m)不全非正 ， 則進(jìn)行換基； 單純形法 Simplex Method 2/4/2023 制作與教學(xué) 線性規(guī)劃 Linear Programming Page 66 m in 0 , 0 ,iiL ik ikik ikbba a M Maa?????????當(dāng) ≤ 時(shí) ＝ 為 任 意 大 的 正 數(shù)第 Ｌ 個(gè)比值最小 ， 選最小比值對(duì)應(yīng)行的基變量為出基變量 ，若有相同最小比值 ， 則任選一個(gè) 。 aLk為主元素； (c） 求新的基可行解：用初等行變換方法將 aLk 化為１ ,k列其它元素化為零 （ 包括檢驗(yàn)數(shù)行 ） 得到新的可行基及基本可行解 ， 再判斷是否得到最優(yōu)解 。 （ b）選出基變量 ，求最小比值： 單純形法 Simplex Method ： （ a）選進(jìn)基變量 設(shè) λk=max｛ λj | λj 0｝ ,xk為進(jìn)基變量 2/4/2023 制作與教學(xué) 線性規(guī)劃 Linear Programming Page 67 【 例 】 用單純形法求解 321 2max xxxZ ???????????????02053115232321321321xxxxxxxxx、【 解 】 將數(shù)學(xué)模型化為標(biāo)準(zhǔn)形式： 321 2max xxxZ ????????????????????5,2,1,0205311523253214321?jxxxxxxxxxj不難看出 x x5可作為初始基變量，單純法計(jì)算結(jié)果如表 。 單純形法 Simplex Method 2/4/2023 制作與教學(xué) 線性規(guī)劃 Linear Programming Page 68 Cj 1 2 1 0 0 b θ CB XB x1 x2 x3 x4 x5 0 x4 2 － 3 2 1 0 15 0 x5 1/3 1 5 0 1 20 λj 1 2 1 0 0 0 x4 2 x2 λj 1 x1 2 x2 λj 表 1－ 5 1/3 1 5 0 1 20 3 0 17 1 3 75 1/3 0 － 9 0 － 2 M 20 25 60 1 0 17/3 1/3 1 25 0 1 28/9 － 1/9 2/3 35/3 0 0 － 98/9 － 1/9 － 7/3 最優(yōu)解 X=(25， 35/3， 0， 0， 0)T，最優(yōu)值 Z=145/3 單純形法 Simplex Method 2/4/2023 制作與教學(xué) 線性規(guī)劃 Linear Programming Page 69 【例 】用單純形法求解 421 22min xxxZ ??????????????????????5,1,0212665521421321?jxxxxxxxxxxj【解】 這是一個(gè)極小化的線性規(guī)劃問題 ,可以將其化為極大化問題求解 ,也可以直接求解 ,這時(shí)判斷標(biāo)準(zhǔn)是： λj≥0(j=1， … ， n)時(shí)得到最優(yōu)解 。 容易觀察到 ,系數(shù)矩陣中有一個(gè) 3階單位矩陣 ,x x x5為基變量。目標(biāo)函數(shù)中含有基變量 x4,由第二個(gè)約束得到 x4=6+x1－ x2，并代入目標(biāo)函數(shù)消去 x4得 1 2 1 2 1 22 2 ( 6 ) 6Z x x x x x x? ? ? ? ? ? ? ?＝ 單純形法 Simplex Method 2/4/2023 制作與教學(xué) 線性規(guī)劃 Linear Programming Page 70 XB x1 x2 x3 x4 x5 b θ x3 x4 x5 1 1 6 [1] 1 2 1 0 0 0 1 0 0 0 1 5→ 6 21 5 6 21/2 λj 1 1↑ 0 0 0 x2 x4 x5 1 2 4 1 0 0 1 1 2 0 1 0 0 0 1 5 1 11 λj 2 0 1 0 0 表中 λj≥0,j=1,2,? ,5所以最優(yōu)解為 X=(0,5,0,1,11,)最優(yōu)值 Z=2x1－ 2x2－ x4=－ 2 5－ 1=－ 11 極小值問題 ,注意判斷標(biāo)準(zhǔn) ,選進(jìn)基變量時(shí) ,應(yīng)選 λj0的變量 xj進(jìn)基。 單純形法 Simplex Method 表 2/4/2023 制作與教學(xué) 線性規(guī)劃 Linear Programming Page 71 21max xxZ ???????????????0,42123212121xxxxxx【例 】求解線性規(guī)劃 【 解 】 化為標(biāo)準(zhǔn)型 21max xxZ ????????????????4,1,042123421321?jxxxxxxxj 單純形法 Simplex Method 2/4/2023 制作與教學(xué) 線性規(guī)劃 Linear Programming Page 72 初始單純形表為 XB x1 x2 x3 x4 b x3 x4 3 2 － 2 － 1 1 0 0 1 1 4 λj － 1 1 0 0 λ2=10, x2進(jìn)基 ， 而 a120， a220， 沒有比值 ， 從而線性規(guī)劃的最優(yōu)解無(wú)界 。 由模型可以看出 ， 當(dāng)固定 x1使 x2→+∞且滿足約束條件 ， 還可以用圖解法看出具有無(wú)界解 。 單純形法 Simplex Method 2/4/2023 制作與教學(xué) 線性規(guī)劃 Linear Programming Page 73 【 例 】 求解線性規(guī)劃