[管理學(xué)]整數(shù)規(guī)劃(2)-文庫吧資料
2024-10-25 01:40本頁面
【正文】 例 5． 高壓容器公司制造小、中、大三種尺寸的金屬容器， 所用資源為金屬板、勞動(dòng)力和機(jī)器設(shè)備，制造一個(gè)容器所需 的各種資源的數(shù)量如表所示。 Aj 各點(diǎn)的設(shè)備投資及每年可獲利潤由于地點(diǎn)不同都是不一樣的，預(yù)測情況見表所示 (單位：萬元 )。 Ｘ １ ＝２．４４ Ｘ ２ ＝３．２６ f＝１４．６６ ＬＰ１ ＬＰ 5 ＬＰ４ ＬＰ３ ＬＰ２ f上＝１４．６６ f下 (觀察法 )＝１３ Max f=2x1+3x2 +273x2≤1365 4x1+40x2 ≤140 0≤x 1≤4 , 0≤x 2 x1 x2為整數(shù) x1 ≤2 x1 ≥ 3 Ｘ １ ＝２ Ｘ ２ ＝ f＝ Ｘ １ ＝ 3 Ｘ ２ ＝ f＝１４． 58 f上＝１４． 58 f下 (觀察法 ) ＝１３ x1 ≥ 3，Ｘ ２ ≤ ２ x1 ≥ 3，Ｘ ２ ≥ 3 Ｘ １ ＝４ Ｘ ２ ＝２ f＝１４ 無解 f上＝１４ f下＝１４ ＬＰ１ＬＰ２分枝定界法步驟 ：（稱求解整數(shù)規(guī)劃問題為Ａ，其相應(yīng)線形規(guī)劃問題為Ｂ） １．求解問題Ｂ， 若Ｂ無解，則Ａ無解 若Ｂ有解，且符合整數(shù)要求，則Ｂ的解就是Ａ的解 若Ｂ有解，但不符合整數(shù)要求，則記其目標(biāo)函數(shù)值為Ｚ１ ２．確定問題Ａ的上界，記為 Z上界 ，再用觀察法找到Ａ的一個(gè) 整數(shù) 可行解，令其為Ａ的下界 : Z下界 ３．判斷上界是否等于下界，如果相等則得到其最優(yōu)值；如果不相等，則做第４步 ４．在Ｂ的最優(yōu)解中找到一個(gè) 小數(shù)部分最大 的解，把它分為相應(yīng)的兩個(gè)整數(shù)部分，是問題Ｂ變?yōu)椋拢薄ⅲ拢? ５．求解Ｂ１、Ｂ２，判斷上下界是否相等，若不相等則取上界最大的分枝Ｂ i再分割，求上下邊界，直到上下界相等為止。 Ax ?0整數(shù)規(guī)劃的分枝定界法 分枝定界法： 首先求出相應(yīng)線形規(guī)劃的最優(yōu)解。但問題 (1) 確難多了。顯然 (2)的最優(yōu)值小于 等于問題 (1)的最優(yōu)值。 （２）在 LP的可行域中，整數(shù)點(diǎn)不多時(shí)（ 12個(gè)），是否可以用窮舉法。 啟示２： （１）是否能在 LP的約束區(qū)域中切去幾塊不含整數(shù)解的可行域，使整數(shù)解作為頂點(diǎn)，這樣求 LP問題的最優(yōu)解，即為整數(shù)解。當(dāng) n=60時(shí)， 260約等于 1018，這使計(jì)算機(jī)也難以實(shí)現(xiàn)。 求 最小值 時(shí) ,整數(shù)規(guī)劃的目標(biāo)函數(shù)值 大于等于 相應(yīng)一般線形規(guī)劃的目標(biāo)函數(shù)值 。 下面通過整數(shù)規(guī)劃的求解來說明。每種物品的重量與 價(jià)值，如表。整數(shù) (線性 )規(guī)劃 (Integer Programming,IP) 在線性規(guī)劃問題的討論中，有些最優(yōu)解是小數(shù)，但 某些常要求最優(yōu)解是整數(shù)（即整數(shù)解）
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1