【正文】 ??????????????0,30340243max432142132121xxxxxxxxxxxxZ系數(shù)矩陣 A及可行基 B1 ???????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ù)看出。 最優(yōu)解判斷標(biāo)準(zhǔn) 當(dāng)所有檢驗(yàn)數(shù) λj≤0（ j=1， … ， n）時(shí)，基本可行解為最優(yōu)解。其中基變量的檢驗(yàn)數(shù)必為零； ： （ a） 若 λj≤０ （ j＝１ ， ２ ， … ， n） 得到最解； （ b） 某個(gè) λk0且 aik≤０ （ i=1， 2,… ,m） 則線性規(guī)劃具有無(wú)界解 (見(jiàn)例 )。 單純形法 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ī)劃問(wèn)題 ,可以將其化為極大化問(wèn)題求解 ,也可以直接求解 ,這時(shí)判斷標(biāo)準(zhǔn)是： λj≥0(j=1， … ， n)時(shí)得到最優(yōu)解 。 由模型可以看出 ， 當(dāng)固定 x1使 x2→+∞且滿足約束條件 ， 還可以用圖解法看出具有無(wú)界解 。目標(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 極小值問(wèn)題 ,注意判斷標(biāo)準(zhǔn) ,選進(jìn)基變量時(shí) ,應(yīng)選 λj0的變量 xj進(jìn)基。 aLk為主元素； (c） 求新的基可行解：用初等行變換方法將 aLk 化為１ ,k列其它元素化為零 （ 包括檢驗(yàn)數(shù)行 ） 得到新的可行基及基本可行解 ， 再判斷是否得到最優(yōu)解 。 單純形法 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)潔 ，這種表格稱為單純形表 （ 表 ） 。 本例中 λ1=3,λ2=4,λ3=0,λ4=0。 它是一種逐步逼近最優(yōu)解的迭代方法 。 定理 ， 尋求最優(yōu)解不是在無(wú)限個(gè)可行解中去找 ， 而是在有限個(gè)基本可行解中去尋求 。 【 定理 】 若線性規(guī)劃有最優(yōu)解 ,則最優(yōu)值一定可以在可行解集合的某個(gè)極點(diǎn)上到達(dá) ,最優(yōu)解就是極點(diǎn)的坐標(biāo)向量 。 )()2()1( , KXXXX ? 及，且， 021 ?iK ???? ?11 ???Kii? iKii XX ??1?＝)()2()1( , KXXX ? 基本概念 Basic Concepts 2/4/2023 制作與教學(xué) 線性規(guī)劃 Linear Programming Page 55 極點(diǎn) (Extreme point) 設(shè) K是凸集 ， ， 若 X不能用K中兩個(gè)不同的 點(diǎn) 的凸組合表示為 KX ? )2()1( , XX? ) 1 0 ( ) 1 ( ) 2 ( ) 1 ( ? ? ? ? ? ? ? X X X 則稱 X是 K的一個(gè)極點(diǎn)或頂點(diǎn)。C點(diǎn)是基本可行解 。例如右圖中線段 的點(diǎn)為最優(yōu) 解時(shí)， Q1點(diǎn)及 Q2點(diǎn)是基本最優(yōu)解 ,線段 的內(nèi)點(diǎn)是最優(yōu)解而不是基本最優(yōu)解。 在例 ， 對(duì) Ｂ １ 來(lái)說(shuō) ， x1,x2是基變量 ， x3,x4， x5是非基變量 ，令 x3=x4=x5=0， 則式 （ ） 為 ???????2610352121xxxx－ ,610151 ????????B對(duì) B2來(lái)說(shuō) ， x1,x4,為基變量 ， 令非變量 x2,x3,x5為零 ， 由式 （ ） 得到 ， x4=4， 511 ??x因 |B1|≠０，由克萊姆法則知， x x2有唯一解 x1＝ 2/5,x2=1則 基本解為 TX )0,0,0,1,52()1( ? 基本概念 Basic Concepts 2/4/2023 制作與教學(xué) 線性規(guī)劃 Linear Programming Page 51 由于 是基本解，從而它是基本可行解，在 中x10,因此不是可行解，也就不是基本可行解。 例如， 與 X=（ 0， 0， 0， 3， 2，）都是例 1 的可行解。當(dāng)矩陣 B的行列式等式零即 |B|=0時(shí)就不是基 當(dāng)確定某一矩陣為基矩陣時(shí)，則基矩陣對(duì)應(yīng)的列向量稱為 基向量 (basis vector)，其余列向量稱為 非基向量 基向量對(duì)應(yīng)的變量稱為 基變量 (basis variable)，非基向量對(duì)應(yīng)的變量稱為 非基變量 在上例中 B2的基向量是 A中的第一列和第四列 ， 其余列向量是非基向量 ， x x4是基變量 ， x x x5是非基變量 。 作業(yè)：教材 P34 T 8 線性規(guī)劃的標(biāo)準(zhǔn)型 Standard form of LP 下一節(jié)：基本概念 2/4/2023 線性規(guī)劃的有關(guān)概念 Basic Concepts of LP 2/4/2023 制作與教學(xué) 線性規(guī)劃 Linear Programming Page 46 設(shè)線性規(guī)劃的標(biāo)準(zhǔn)型 max Z=CX （ ） AX=b