線性規(guī)劃ppt課件(2)-資料下載頁(yè)
2025-04-29 02:51本頁(yè)面
【正文】 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 單純形計(jì)算方法 (Simplex Method)是先求出一個(gè)初始基可行解并判斷它是否最優(yōu) ， 若不是最優(yōu) ， 再換一個(gè)基可行解并判斷 ，直到得出最優(yōu)解或無(wú)最優(yōu)解 。 它是一種逐步逼近最優(yōu)解的迭代方法 。 換言之：從可行域中某一個(gè)頂點(diǎn)開(kāi)始，判斷此頂點(diǎn)是否是最優(yōu)解，如不是 ,則再找另一個(gè)使得其目標(biāo)函數(shù)值更優(yōu)的頂點(diǎn)，稱(chēng)之為迭代，再判斷此點(diǎn)是否是最優(yōu)解。直到找到一個(gè)頂點(diǎn)為其最優(yōu)解，就是使得其目標(biāo)函數(shù)值最優(yōu)的解，或者能判斷出線性規(guī)劃問(wèn)題無(wú)最優(yōu)解為止。 當(dāng)系數(shù)矩陣 A中可以觀察得到一個(gè)可行基時(shí) （ 通常是一個(gè)單位矩陣或 m個(gè)線性無(wú)關(guān)的單位向量組成的矩陣 ） ， 可以通過(guò)解線性方程組求得基本可行解 。 【 解 】 化為標(biāo)準(zhǔn)型 ， 加入松馳變量 x x4則標(biāo)準(zhǔn)型為 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是一個(gè)初始基 ,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)解，可以從目標(biāo)函數(shù)中的系數(shù)看出。目標(biāo)函數(shù) Z=300x1+400x2中 x1的系數(shù)大于零，如果 x1為一正數(shù)，則 Z的值就會(huì)增大，同樣若 x2不為零為一正數(shù)，也能使 Z的值增大；因此只要目標(biāo)函數(shù)中非基變量的系數(shù)大于零，那么目標(biāo)函數(shù)就沒(méi)有達(dá)到最大值，即沒(méi)有找到最優(yōu)解，判別線性規(guī)劃問(wèn)題是否達(dá)到最優(yōu)解的數(shù)稱(chēng)為檢驗(yàn)數(shù)，記作 λj , j=1,2,… ,n 本例中 λ1=300,λ2=400,λ3=0,λ4=0。參看表 16 最優(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ù)。 檢驗(yàn)數(shù) 目標(biāo)函數(shù)用非基變量表達(dá)時(shí)的變量系數(shù) 單純形法全過(guò)程的計(jì)算 ， 可以用列表的方法計(jì)算更為簡(jiǎn)潔 ，這種表格稱(chēng)為單純形表 （ 表 16） 。 計(jì)算步驟： ，列出初始單純形表，求出檢驗(yàn)數(shù)。其中基變量的檢驗(yàn)數(shù)必為零； ： （ a） 若 λj≤０ （ j＝１ ， ２ ， … ， n） 得到最解； （ b） 某個(gè) λk0且 aik≤０ （ i=1， 2,… ,m） 則線性規(guī)劃具有無(wú)界解 (見(jiàn)例 118)。 （ c） 若存在 λk0且 aik (i=1,… ,m)不全非正 ， 則進(jìn)行換基； m i n 0 , 0 ,iiL i k i ki k i kbba a M Maa?????????當(dāng) ≤ 時(shí) ＝ 為 任 意 大 的 正 數(shù)第 Ｌ 個(gè)比值最小 ， 選最小比值對(duì)應(yīng)行的基變量為出基變量 ， 若有相同最小比值 ， 則任選一個(gè) 。 aLk為主元素； (c） 求新的基可行解：用初等行變換方法將 aLk 化為１ ,k列其它元素化為零 （ 包括檢驗(yàn)數(shù)行 ） 得到新的可行基及基本可行解 ， 再判斷是否得到最優(yōu)解 。 （ b）選出基變量 ，求最小比值： ： （ a）選進(jìn)基變量 設(shè) λk=max｛ λj | λj 0｝ ,xk為進(jìn)基變量 進(jìn)基列 出基行 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ù)學(xué)模型化為標(biāo)準(zhǔn)形式： 321 2m a x xxxZ ????????????????????5,2,1,0205311523253214321?jxxxxxxxxxj不難看出 x x5可作為初始基變量，單純法計(jì)算結(jié)果如表 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
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1