線性規(guī)劃ppt課件(2)-資料下載頁
2025-04-29 02:51本頁面
【正文】 0 )最優(yōu)值 Z = 8 5)20,0(C)35,5(DB (1 0, 1 0)例 1 . 6 m ax Z = 3 x1+4 x2 單純形計算方法 (Simplex Method)是先求出一個初始基可行解并判斷它是否最優(yōu) ， 若不是最優(yōu) ， 再換一個基可行解并判斷 ，直到得出最優(yōu)解或無最優(yōu)解 。 它是一種逐步逼近最優(yōu)解的迭代方法 。 換言之：從可行域中某一個頂點開始，判斷此頂點是否是最優(yōu)解，如不是 ,則再找另一個使得其目標函數(shù)值更優(yōu)的頂點，稱之為迭代，再判斷此點是否是最優(yōu)解。直到找到一個頂點為其最優(yōu)解，就是使得其目標函數(shù)值最優(yōu)的解，或者能判斷出線性規(guī)劃問題無最優(yōu)解為止。 當系數(shù)矩陣 A中可以觀察得到一個可行基時 （ 通常是一個單位矩陣或 m個線性無關的單位向量組成的矩陣 ） ， 可以通過解線性方程組求得基本可行解 。 【 解 】 化為標準型 ， 加入松馳變量 x x4則標準型為 121 2 31 2 41 2 3 4m a x 3 0 0 4 0 02 4 03 / 2 3 0, , , 0Z x xx x xx x xx x x x??? ? ???? ? ??? ??系數(shù)矩陣 A及可行基 B1 2 1 1 01 3 / 2 0 1A ??? ???????????10011Br(B1)=2， B1是一個初始基 ,x x4為基變量 ， x x2為非基變量 ， 令 x1=0、 x2=0由約束方程知 x3=x4=30得到初始基本可行解 X(1)=(0,0,40,30)T 【 例 212】 用單純形法求例 11線性規(guī)劃的最優(yōu)解 以上得到的一組基可行解是不是最優(yōu)解，可以從目標函數(shù)中的系數(shù)看出。目標函數(shù) Z=300x1+400x2中 x1的系數(shù)大于零，如果 x1為一正數(shù)，則 Z的值就會增大，同樣若 x2不為零為一正數(shù)，也能使 Z的值增大；因此只要目標函數(shù)中非基變量的系數(shù)大于零，那么目標函數(shù)就沒有達到最大值，即沒有找到最優(yōu)解，判別線性規(guī)劃問題是否達到最優(yōu)解的數(shù)稱為檢驗數(shù)，記作 λj , j=1,2,… ,n 本例中 λ1=300,λ2=400,λ3=0,λ4=0。參看表 16 最優(yōu)解判斷標準 當所有檢驗數(shù) λj≤0（ j=1， … ， n）時，基本可行解為最優(yōu)解。 當目標函數(shù)中有基變量 xi時，利用約束條件將目標函數(shù)中的 xi消去即可求出檢驗數(shù)。 檢驗數(shù) 目標函數(shù)用非基變量表達時的變量系數(shù) 單純形法全過程的計算 ， 可以用列表的方法計算更為簡潔 ，這種表格稱為單純形表 （ 表 16） 。 計算步驟： ，列出初始單純形表，求出檢驗數(shù)。其中基變量的檢驗數(shù)必為零； ： （ a） 若 λj≤０ （ j＝１ ， ２ ， … ， n） 得到最解； （ b） 某個 λk0且 aik≤０ （ i=1， 2,… ,m） 則線性規(guī)劃具有無界解 (見例 118)。 （ c） 若存在 λk0且 aik (i=1,… ,m)不全非正 ， 則進行換基； m i n 0 , 0 ,iiL i k i ki k i kbba a M Maa?????????當 ≤ 時 ＝ 為 任 意 大 的 正 數(shù)第 Ｌ 個比值最小 ， 選最小比值對應行的基變量為出基變量 ， 若有相同最小比值 ， 則任選一個 。 aLk為主元素； (c） 求新的基可行解：用初等行變換方法將 aLk 化為１ ,k列其它元素化為零 （ 包括檢驗數(shù)行 ） 得到新的可行基及基本可行解 ， 再判斷是否得到最優(yōu)解 。 （ b）選出基變量 ，求最小比值： ： （ a）選進基變量 設 λk=max｛ λj | λj 0｝ ,xk為進基變量 進基列 出基行 bi/ai2, ai20 θi 表 16 (a) XB x1 x2 x3 x4 b x3 2 1 1 0 40 x4 1 3/2 0 1 30 λj 300 400 0 0 (b) x3 x2 λj (c) x1 x2 10 λj 基變量 1 20 0 0 2/3 0 2/3 20 4/3 1 2/3 40 100/3 0 800/3 30 1 0 3/4 1/2 15 0 1 1/2 1 10 0 0 25 250 將 3/2化為 1 20 15 【 例 213】 用單純形法求解 321 2m a x xxxZ ???????????????02053115232321321321xxxxxxxxx、【 解 】 將數(shù)學模型化為標準形式： 321 2m a x xxxZ ????????????????????5,2,1,0205311523253214321?jxxxxxxxxxj不難看出 x x5可作為初始基變量，單純法計算結果如表 17所示 。 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－ 7 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
教學課件相關推薦
鄂ICP備17016276號-1