【正文】 由模型可以看出 ， 當(dāng)固定 x1使 x2→+∞且滿足約束條件 ， 還可以用圖解法看出具有無界解 。目標(biāo)函數(shù)中含有基變量 x4,由第二個約束得到 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/29/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) ,選進基變量時 ,應(yīng)選 λj0的變量 xj進基。 單純形法 Simplex Method 2/29/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/29/2023 制作與教學(xué) 線性規(guī)劃 Linear Programming Page 69 【例 】用單純形法求解 421 22min xxxZ ??????????????????????5,1,0212665521421321?jxxxxxxxxxxj【解】 這是一個極小化的線性規(guī)劃問題 ,可以將其化為極大化問題求解 ,也可以直接求解 ,這時判斷標(biāo)準(zhǔn)是： λj≥0(j=1， … ， n)時得到最優(yōu)解 。 aLk為主元素； (c） 求新的基可行解：用初等行變換方法將 aLk 化為１ ,k列其它元素化為零 （ 包括檢驗數(shù)行 ） 得到新的可行基及基本可行解 ， 再判斷是否得到最優(yōu)解 。其中基變量的檢驗數(shù)必為零； ： （ a） 若 λj≤０ （ j＝１ ， ２ ， … ， n） 得到最解； （ b） 某個 λk0且 aik≤０ （ i=1， 2,… ,m） 則線性規(guī)劃具有無界解 (見例 )。 單純形法 Simplex Method 檢驗數(shù) 目標(biāo)函數(shù)用非基變量表達時的變量系數(shù) 2/29/2023 制作與教學(xué) 線性規(guī)劃 Linear Programming Page 63 進基列 出基行 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/29/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/29/2023 制作與教學(xué) 線性規(guī)劃 Linear Programming Page 65 單純形法全過程的計算 ， 可以用列表的方法計算更為簡潔 ，這種表格稱為單純形表 （ 表 ） 。 最優(yōu)解判斷標(biāo)準(zhǔn) 當(dāng)所有檢驗數(shù) λj≤0（ j=1， … ， n）時，基本可行解為最優(yōu)解。 本例中 λ1=3,λ2=4,λ3=0,λ4=0。 【例 】用單純形法求下列線性規(guī)劃的最優(yōu)解 ????????????0,30340243max21212121xxxxxxxxZ 單純形法 Simplex Method 普通單純形法 2/29/2023 制作與教學(xué) 線性規(guī)劃 Linear Programming Page 61 【 解 】 化為標(biāo)準(zhǔn)型 ， 加入松馳變量 x x4則標(biāo)準(zhǔn)型為 ??????????????0,30340243max432142132121xxxxxxxxxxxxZ系數(shù)矩陣 A及可行基 B1 ???????10310112A??????10011Br(B1)=2， B1是一個初始基 ,x x4為基變量 ， x x2為非基變量 ， 令 x1=0、 x2=0由約束方程知 x3=x4=30得到初始基本可行解 X(1)=(0,0,40,30)T 單純形法 Simplex Method 2/29/2023 制作與教學(xué) 線性規(guī)劃 Linear Programming Page 62 以上得到的一組基可行解是不是最優(yōu)解，可以從目標(biāo)函數(shù)中的系數(shù)看出。 它是一種逐步逼近最優(yōu)解的迭代方法 。 基本概念 Basic Concepts 2/29/2023 制作與教學(xué) 線性規(guī)劃 Linear Programming Page 58 1. 線性規(guī)劃常用的概念：可行解、基本解、基本 可行解、最優(yōu)解、基本最優(yōu)解、基、可行基、最優(yōu)基、凸集、極點（凸點）、凸組合 。 定理 ， 尋求最優(yōu)解不是在無限個可行解中去找 ， 而是在有限個基本可行解中去尋求 。 線性規(guī)劃的基本定理 基本概念 Basic Concepts 2/29/2023 制作與教學(xué) 線性規(guī)劃 Linear Programming Page 57 定理 ， 若最優(yōu)解唯一 ， 則最優(yōu)解只能在某一極點上達到 ， 若具有多重最優(yōu)解 ， 則最優(yōu)解是某些極點的凸組合 ， 從而最優(yōu)解是可行解集的極點或界點 ， 不可能是可行解集的內(nèi)點 。 【 定理 】 若線性規(guī)劃有最優(yōu)解 ,則最優(yōu)值一定可以在可行解集合的某個極點上到達 ,最優(yōu)解就是極點的坐標(biāo)向量 。 1Q2QO 3Q4Q 基本概念 Basic Concepts 2/29/2023 制作與教學(xué) 線性規(guī)劃 Linear Programming Page 56 【 定理 】 若線性規(guī)劃可行解 K非空 ,則 K是凸集。 )()2()1( , KXXXX ? 及，且， 021 ?iK ???? ?11 ???Kii? iKii XX ??1?＝)()2()1( , KXXX ? 基本概念 Basic Concepts 2/29/2023 制作與教學(xué) 線性規(guī)劃 Linear Programming Page 55 極點 (Extreme point) 設(shè) K是凸集 ， ， 若 X不能用K中兩個不同的 點 的凸組合表示為 KX ? )2()1( , XX? ) 1 0 ( ) 1 ( ) 2 ( ) 1 ( ? ? ? ? ? ? ? X X X 則稱 X是 K的一個極點或頂點。 0,0402212121??????xxxxxxx1x2O10 20 30 4010203040( 3 , 4 )A(15 , 1 0 )最優(yōu)解 X = (1 5 , 1 0 )最優(yōu)值 Z = 8 5)20,0(C)35,5(DB(10 ,1 0)例 1 . 6 m ax Z= 3 x1+4 x2 基本概念 Basic Concepts 2/29/2023 制作與教學(xué) 線性規(guī)劃 Linear Programmi