目標規(guī)劃數(shù)學模型講義-全文預覽
【正文】 21442133212221112143332211?jddxxddxxddxxddxxddxxdPddPddPZjj、B C 滿意解是線段 上任意點，端點的解是 B(100/3， 80/3)， C(60， 0)． 決策者根據(jù)實際情形進行二次選擇． BCA (3) x1 x2 20 40 60 80 100 20 40 60 80 100 (2) (1) (4) ?1d?1d ?2d?3d?2?3?4d?4d圖 5－ 3 ?????????????????????????????????????4,1,0,)4()3(12023)2(56087)1(400510214421332122211121?jddxxddxxddxxddxxddxxjj、B C 滿意解是點 B， X=(100/3， 80/3) 1 1 2 2 3 3 3 4 41m in ( ) ( )Z P d d P d d P d Pd? ? ? ? ? ?? ? ? ? ? ?A (3) x1 x2 20 40 60 80 100 20 40 60 80 100 (2) (1) (4) ?1d?1d ?2d?3d?2?3?4d?4d圖 5－ 3 ?????????????????????????????????????4,1,0,)4()3(12023)2(56087)1(400510214421332122211121?jddxxddxxddxxddxxddxxjj、滿意解是點 A， X=(20， 40) ????? ????? 43322111 )2()(min dPddPddPZA 本節(jié)介紹了目標規(guī)劃的圖解法 2. 標明偏差變量大于零的變量 X的取值區(qū)域 The graphical method of GP 單純形法 Simplex Method 單純形法求解目標規(guī)劃可參照第一章的步驟，只是目標規(guī)劃的檢驗要按優(yōu)先級順序逐級進行，不同的是： （ 1）首先使得檢驗數(shù)中 P1的系數(shù)非負，再使得 P2的系數(shù)非負，依次進行； （ 2）當 P P … 、 Pk對應的系數(shù)全部非負時得到滿意解； （ 3）如果 P1， … ， Pi行系數(shù)非負，而 Pi+1行存在負數(shù)，并且負數(shù)所在列上面 P1， … ， Pi行中存在正數(shù)時，得到滿意解，計算結(jié)束． 單純形法 Simplex Method 【 例 】 用單純形法求解下述目標規(guī)劃問題 ??????????????????????????????????)3,2,1(0,8022402502)(min2133212221112132211iddxxddxxddxxddxxdPddPzii－【 解 】 以 d1－ 、 d2－ 、 d3－ 為基變量，求出檢驗數(shù)，將檢驗數(shù)中優(yōu)先因子分離出來，每一優(yōu)先級做一行，列出初始單純形表 45． 單純形法 Simplex Method Cj 0 0 P1 0 0 P1 P2 0 b CB 基 x1 x2 d1－ d1+ d2－ d2+ d3－ d3+ P1 d1－ 1 [2] 1 － 1 50→ 0 d2－ 2 1 1 － 1 40 P2 d3－ 2 2 1 － 1 80 Cj－ Zj P1 － 1 － 2 1 1 P2 － 2 － 2 1 表 4－ 5 單純形法 Simplex Method 表 4－ 5中， P1行中 (－ 2)最小，則 x2進基，求最小比值易知 d1－ 出基，將第二列主元素化為 1，其余元素化為零，得到表 46． Cj 0 0 P1 0 0 P1 P2 0 b CB 基 x1 x2 d1－ d1+ d2－ d2+ d3－ d3+ 0 x2 1/2 1 1/2 － 1/2 25 0 d2－ [3/2] 1/2 1 － 1 15→ P2 d3－ 1 1 1 － 1 30 Cj－ Zj P1 1 1 P2 － 1 1 － 1 1 表 4－ 6 單純形法 Simplex Method 表 46中 P1行全部檢驗數(shù)非負，表明第一目標已經(jīng)得到優(yōu)化． P2行存在負數(shù)， x1的檢驗數(shù)為－ P20，選 x1進基（也可以選 d1+進基），則 d3－ 出基，迭代得到表 47． Cj 0 0 P1 0 0 P1 P2 0 b CB 基 x1 x2 d1－ d1+ d2－ d2+ d3－ d3+ 0 x2 1 2/3 － 2/3 1/3 20 0 x1 1 [1/3] 2/3 10→ P2 d3－ 2/3 2/3 1 － 1 20 Cj－ Zj P1 1 1 P2 2/3 2/3 2/3 2/3 1 單純形法 Simplex Method 表 47 在表 47中， P1行的系數(shù)全部非負， P2行存在負數(shù)， d1+的檢驗數(shù)－ 2/3P20，選 d1+進基，則 x1出基，迭代得到表 48． 應當注意 ，表 47中不能選 d2+進基，檢驗數(shù) P1－ 2/3P2應理解為“大于零”，P P2是優(yōu)先級別的比較，而不是“數(shù)”的比較．例如， P1－ 3P2+5P3理解為小于零， 2P2－ 4P4理解為大于零等等． Cj→ 0 0 P1 0 0 P1 P2 0 b CB 基 x1 x2 d1－ d1+ d2－ d2+ d3－ d3+ 0 x2 2 1 1 － 1 40 0 d1+ 3 － 1 1 2 － 2 30 P2 d3－ － 2 － 2 2 1 － 1 0 Cj－ Zj P1 1 1 P2 2 2 － 2 1 表 4－ 8 單純形法 Simplex Method 表 48中 P2行的（－ 2）小于零，但（－ 2）列上面 P1行存在正數(shù) 1，檢驗數(shù) P1－ 2P20,所有檢驗數(shù)非負，得到滿意解 X＝（ 0， 40） 【 例 】 (1)用單純形法求解例 （ 2）當目標函數(shù)變?yōu)? ????? ????? 43322111 )2()(min dPddPddPZ【 解 】 （ 1）初始單純形表見表 49，最終單純形表見表 412．滿意解 X＝ (100/3， 80/3)T，對應于圖 46點 B．不難看出有多重解，將 d4－ 進基 x2出基 ，得到另一滿意解 X＝ (60， 0)T，對應于圖 46點 C，見表 413 單純形法 Simplex Method 求滿意解 Cj 0 0 P1 0 0 P1 P2 P2 0 P3 b CB 基 x1 x2 d1－ d1+ d2－ d2+ d3－ d3+ d4－ d4+ P1 d1－ [10] 5 1 － 1 400→ 0 d2－ 7 8 1 － 1 560 P2 d3－ 2 2 1 － 1 120 0 d4－ 1 1 － 1 100 Cj－ Zj P1 1 1 P2
教學課件相關推薦
鄂ICP備17016276號-1