[管理學]ie10_or12ch3運輸問題4andch4整數(shù)規(guī)劃-文庫吧資料
2025-02-25 11:13本頁面
【正文】 kKkjkMiijNjij,2,1 , 21 , )( ,2,1 , 111111 111 1???客戶需求：＝供銷平衡：供應(yīng)能力：第 38頁 西南科技大學制造科學與工程學院工業(yè)工程與設(shè)計系 石宇強 運籌學 解法概述 ?因為可行方案數(shù)目有限，因此經(jīng)過一一比較后，總能求出最好方案，例如，背包問題充其量有 2n1種方式；連線問題充其量有 n!種方式； ?實際上這種方法是不可行。 0 1 2 3 4 4 3 2 1 x1 x2 分枝： X1 ? 1,x1 ? 2 P1 P2 兩個子問題： （ P1） Max Z=4x1+3x2 . 3x1+4x2 ? 12 4x1+2x2 ? 9 x1,x2 ? 0 ， x1 ? 1 ，整數(shù) 用單純形法可解得相應(yīng)的（ P1）的最優(yōu)解（ 1， 9/4） Z=43/4 （ P2） Max Z=4x1+3x2 . 3x1+4x2 ? 12 4x1+2x2 ? 9 x1,x2 ? 0 ， x1 ? 2 ，整數(shù) 用單純形法可解得相應(yīng)的（ P2）的最優(yōu)解（ 2， 1/2） Z=19/2 0 1 2 3 4 4 3 2 1 x1 x2 再對（ P1）分枝： X1 ? 1 （ P3） x2 ? 2 （ P4） x2 ? 3 P1 P2 P3 P4 （ P1）兩個子問題： （ P3） Max Z=4x1+3x2 . 3x1+4x2 ? 12 4x1+2x2 ? 9 x1,x2 ? 0 ,x1 ? 1, x2 ? 2整數(shù) 用單純形法可解得相應(yīng)的（ P3）的最優(yōu)解（ 1， 2） Z=10 （ P1）兩個子問題： （ P4） Max Z=4x1+3x2 . 3x1+4x2 ? 12 4x1+2x2 ? 9 x1,x2 ? 0 ,x1 ? 1, x2 ? 3整數(shù) 用單純形法可解得相應(yīng)的（ P4）的最優(yōu)解（ 0， 3） Z=9 X1 ? 2 X2 ? 2 X1 ? 1 X2 ? 3 P1:(1,9/4) Z=43/4 P4: (0,3) Z=9 P2:(2,1/2) Z=19/2 P3: (1,2) Z=10 P:(6/5,21/10) Z=111/10 原問題的最優(yōu)解 （ 1， 2） Z=10 第 26頁 西南科技大學制造科學與工程學院工業(yè)工程與設(shè)計系 石宇強 運籌學 167。( 3 , 1 : ?zES122 )2,2(F4)。( 1 , : ?zCS A: x1=3/2,x2=10/3 Z=29/6 S2 C: x1=1,x2=7/3 Z=10/3 S1 B: x1=2,x2=23/9 Z=41/9 11 ?x 21 ?x1 3 2 X 2 5 4 X 1 2 3 1 )310,23(AS2 對 S1分枝： 構(gòu)造約束： 32 ?x和 22 ?x形成分枝問題 S11和 S12，得解 D S12 )2,( 1433D14611433 )。 分支定界法 混合整數(shù)規(guī)劃的求解 分枝定界方法 分枝： 當 不符合整數(shù)要求時，構(gòu)造兩個約束條件： ii bx ?? ? ? ?
教學課件相關(guān)推薦
鄂ICP備17016276號-1