[管理學(xué)]ie10_or12ch3運(yùn)輸問題4andch4整數(shù)規(guī)劃(編輯修改稿)
2025-03-18 11:13 本頁面
【文章內(nèi)容簡(jiǎn)介】 ?x1 3 2 X 2 5 4 X 1 2 3 1 )310,23(AS2 對(duì) S1分枝： 構(gòu)造約束： 32 ?x和 22 ?x形成分枝問題 S11和 S12，得解 D S12 )2,( 1433D14611433 )。,2( : ?zDS11無可行解 S 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 S11 無可行解 S12 D: x1=33/14,x2=2 Z=61/14 11 ?x32 ?x22 ?x21 ?x1 3 2 X 2 5 4 X 1 2 3 1 )310,23(AS2 對(duì) S12分枝： 構(gòu)造約束： 31 ?x和 21 ?x形成分枝問題 S121和 S122，得解 E和 F S121 )1,3(E4)。( 3 , 1 : ?zES122 )2,2(F4)。( 2 , 2 : ?zFS 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 S11 無可行解 S12 D: x1=33/14,x2=2 Z=61/14 11 ?x32 ?x22 ?x21 ?xS122 F: x1=2,x2=2 Z=4 S121 E: x1=3,x2=1 Z=4 31 ?x21 ?x例 2 用分枝定界法求解： Max Z=4x1+3x2 . 3x1+4x2 ? 12 4x1+2x2 ? 9 x1,x2 ? 0 整數(shù) 用單純形法可解得相應(yīng)的松馳問題的最優(yōu)解（ 6/5， 21/10） Z=111/10為各分枝的上界。 0 1 2 3 4 4 3 2 1 x1 x2 分枝： X1 ? 1,x1 ? 2 P1 P2 兩個(gè)子問題： （ 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 再對(duì)（ P1）分枝： X1 ? 1 （ P3） x2 ? 2 （ P4） x2 ? 3 P1 P2 P3 P4 （ P1）兩個(gè)子問題： （ 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）兩個(gè)子問題： （ 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）
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1