管理運(yùn)籌學(xué)整數(shù)規(guī)劃-wenkub.com
2025-01-08 19:41 本頁(yè)面
【正文】 以上這求從 A到 E的最短路徑問(wèn)題，可以轉(zhuǎn)化為三個(gè)性質(zhì)完全相同，但規(guī)模較小的子問(wèn)題，即分別從 B B B3到 E的最短路徑問(wèn)題。 如果用窮舉法，則從 A到 E一共有 3 3 2=18條不同的路徑，逐個(gè)計(jì)算每條路徑的長(zhǎng)度，總共需要進(jìn)行 4 18=72次加法計(jì)算；對(duì) 18條路徑的長(zhǎng)度做兩兩比較，找出其中最短的一條，總共要進(jìn)行 18－ 1=17次比較。 2 基本概念、基本方程與最優(yōu)化原理 167。轉(zhuǎn) 2。找出所有子問(wèn)題框邊標(biāo)記 f175。 把已標(biāo)記“”的子問(wèn)題，稱(chēng)為已探明的枝。把 f175。對(duì)每個(gè)分枝的試探解進(jìn)行檢驗(yàn)（把自由變量逐次定為固定變量的順序可以是任意的，在不進(jìn)行先驗(yàn)考察時(shí)，常按指標(biāo)變量從小到大的順序進(jìn)行）。顯然 x = 0 時(shí)，目標(biāo)值 f ＝ 0 是不考慮線性不等式約束的最小解，于是 f* ≥ 0。 用于隱枚舉法的 0— 1規(guī)劃標(biāo)準(zhǔn)形式： 為了計(jì)算的方便，需要把一般的 0— 1規(guī)劃問(wèn)題等價(jià)地化成下列標(biāo)準(zhǔn)形式 Min f = c1 x1 + c2 x2 + … + c n xn cj ≥ 0 j = 1,2,…,n . ai1 x1 + ai2 x2 + … + ain xn ≤ bi i = 1,2,…,m x1 ， x2 ， … ， xn = 0 或 1 下面說(shuō)明一個(gè)完全的 0— 1規(guī)劃問(wèn)題可以化為等價(jià)的標(biāo)準(zhǔn)形式： (1)若目標(biāo)函數(shù)求最大： Max z， 可令 f = z， 變?yōu)榍笞钚? Min f ； (2)若目標(biāo)函數(shù)的系數(shù)有負(fù)值時(shí)，如 cj ＜ 0。 4整數(shù)規(guī)劃的分枝定界法 (3) 分枝定界法是求整數(shù)規(guī)劃的一種常用的有效的方法，既能解決純整數(shù)規(guī)劃的問(wèn)題，也能解決混合整數(shù)規(guī)劃的問(wèn)題。 通過(guò)比較，若子問(wèn)題不剪枝則返回 2 。這里的同層子問(wèn)題是指每個(gè)子問(wèn)題 (AI)都是 (A)經(jīng)過(guò)相同分枝次數(shù)得到的。 4整數(shù)規(guī)劃的分枝定界法 (2) 對(duì)當(dāng)前問(wèn)題進(jìn)行分枝和定界： 分技： 無(wú)妨設(shè)當(dāng)前問(wèn)題為 (A)， 其松弛問(wèn)題 (B)的最優(yōu)解不符合整數(shù)約束，任取非整數(shù)的分量 xr 。 (注：找 (A)問(wèn)題的可行解往往需要較大的計(jì)算量，這時(shí)可簡(jiǎn)單記 z175。若情況③發(fā)生，得到 (A)問(wèn)題最優(yōu)值的一個(gè)下界。停止對(duì)這個(gè)問(wèn)題的計(jì)算； ③ (B)有最優(yōu)解 x 及最優(yōu)值 z 但不符合整數(shù)條件。 關(guān)于項(xiàng)目 B的投資額規(guī)定 : x3B ≥ 30000 y3B ， x3B ≤ 50000 y3B ； 保證當(dāng) y3B = 0時(shí)， x3B = 0 ； 當(dāng) y3B = 1時(shí)， 50000 ≥ x3B ≥ 30000 。 項(xiàng)目 D： 五年內(nèi)每年初可購(gòu)買(mǎi)公債，于當(dāng)年末歸還，并加利息 6%，此項(xiàng)投資金額不限。 167。 四、分布系統(tǒng)設(shè)計(jì) 例 7．某企業(yè)在 A1 地已有一個(gè)工廠，其產(chǎn)品的生產(chǎn)能力為 30 千箱，為了擴(kuò)大生產(chǎn)，打算在 A2， A3， A4， A5地中再 選擇幾個(gè)地方建廠。 解 ： 引入 0— 1變量 xij， 并令 xij = 1(當(dāng)指派第 i人去完成第 j項(xiàng)工作時(shí) )或 0（當(dāng)不指派第 i人去完成第 j項(xiàng)工作時(shí) )． 這可以表示為一個(gè) 01整數(shù)規(guī)劃問(wèn)題： Min z=15x11+18x12+21x13+24x14+19x21+23x22+22x23+18x24+26x31+17x32+16x33+19x34+19x41 +21x42+23x43+17x44 . x11+ x12+ x13+ x14= 1 (甲只能干一項(xiàng)工作 ) x21+ x22+ x23+ x24= 1 (乙只能干一項(xiàng)工作 ) x31+ x32+ x33+ x34= 1 (丙只能干一項(xiàng)工作 ) x41+ x42+ x43+ x44= 1 (丁只能干一項(xiàng)工作 ) x11+ x21+ x31+ x41= 1 ( A工作只能一人干 ) x12+ x22+ x32+ x42= 1 ( B工作只能一人干 ) x13+ x23+ x33+ x43= 1 ( C工作只能一人干 ) x14+ x24+ x34+ x44= 1 ( D工作只能一人干 ) xij 為 01變量 ， i,j = 1,2,3,4 * * * 求解可用《管理運(yùn)籌學(xué)》軟件中整數(shù)規(guī)劃方法。 設(shè) x1， x2， x3 分別為小號(hào)容器、中號(hào)容器和大號(hào)容器的生產(chǎn)數(shù)量。 這樣我們可建立如下的數(shù)學(xué)模型： Max z =36x1+40x2+50x3+22x4+20x5+30x6+25x7+48x8+58x9+61x10 . 100x1+120x2+150x3+80x4+70x5+90x6+80x7+140x8+160x9+180x10 ≤ 720 x1 + x2 + x3 ≤ 2 x4 + x5 ≥ 1 x6 + x7 ≥ 1 x8 + x9 + x10 ≥ 2 xj ≥ 0 xj 為
公司管理相關(guān)推薦
鄂ICP備17016276號(hào)-1