運(yùn)籌學(xué)課件第5章整數(shù)線性規(guī)劃-第1-4節(jié)-資料下載頁(yè)
2024-10-18 21:04本頁(yè)面
【正文】 c2x2)+(k3y3+c3x3) (515)式這個(gè)規(guī)定可由以下 3個(gè)線性約束條件表示： ? xj≤y jM， j=1,2,3 (516) ? 其中 M是個(gè)充分大的常數(shù)。 ? (516)式說(shuō)明，當(dāng) xj＞ 0時(shí) yj必須為 1； ? 當(dāng) xj=0時(shí)只有 yj為 0時(shí)才有意義， ? 所以 (516)式完全可以代替 (515)式 01型整數(shù)線性規(guī)劃的解法 ? 解 01型整數(shù)線性規(guī)劃最容易想到的方法 ， 和一般整數(shù)線性規(guī)劃的情形一樣 ， 就是窮舉法 ， 即檢查變量取值為 0或 1的每一種組合 ， 比較目標(biāo)函數(shù)值以求得最優(yōu)解 ， 這就需要檢查變量取值的 2n個(gè)組合 。對(duì)于變量個(gè)數(shù) n較大 (例如 n＞ 10)， 這幾乎是不可能的 。 因此常設(shè)計(jì)一些方法 ， 只檢查變量取值的組合的一部分 ， 就能求到問(wèn)題的最優(yōu)解 。 這樣的方法稱為隱枚舉法 (implicit enumeration)， 分枝定界法也是一種隱枚舉法 。 當(dāng)然 ， 對(duì)有些問(wèn)題隱枚舉法并不適用 ， 所以有時(shí)窮舉法還是必要的 。 下面舉例說(shuō)明一種解 01型整數(shù)線性規(guī)劃的隱枚舉法 例 6 目標(biāo)函數(shù) max z=3x12x2+3x5 約束條件： ? x1+2x2x3≤ 2 ① ? x1+4x2+x3≤ 4 ② (517) ? x1+x2≤ 3 ③ ? 4x1+x3≤ 6 ④ ? x1， x2， x3=0或 1 ⑤ 解題時(shí)先通過(guò)試探的方法找一個(gè)可行解， 容易看出 (x1， x2， x3)=(1， 0， 0)就是合于①～④條件的，算出相應(yīng)的目標(biāo)函數(shù)值 z=3。 ? 我們求最優(yōu)解 ， 對(duì)于極大化問(wèn)題 ， 當(dāng)然希望 z≥ 3，于是增加一個(gè)約束條件： 3x12x2+5x3≥ 3 ◎ ? 后加的條件稱為過(guò)濾的條件 (filtering constraint)。這樣，原問(wèn)題的線性約束條件就變成 5個(gè)。用全部枚舉的方法， 3個(gè)變量共有 23=8個(gè)解，原來(lái) 4個(gè)約束條件，共需 32次運(yùn)算?，F(xiàn)在增加了過(guò)濾條件◎，如按下述方法進(jìn)行，就可減少運(yùn)算次數(shù)。將 5個(gè)約束條件按◎～④順序排好 (表 55)，對(duì)每個(gè)解，依次代入約束條件左側(cè)，求出數(shù)值，看是否適合不等式條件，如某一條件不適合，同行以下各條件就不必再檢查，因而就減少了運(yùn)算次數(shù)。 ? 本例計(jì)算過(guò)程如表 55，實(shí)際只作 24次運(yùn)算。 ? 于是求得最優(yōu)解 (x1， x2， x3)=(1， 0， 1), max z=8 ? 在計(jì)算過(guò)程中 ， 若遇到 z值已超過(guò)條件 ◎ 右邊的值 ， 應(yīng)改變條件 ◎ ， 使右邊為迄今為止最大者 ， 然后繼續(xù)作 。 例如 ， 當(dāng)檢查點(diǎn) (0， 0， 1)時(shí)因 z=5(＞ 3)， 所以應(yīng)將條件 ◎ 換成 ? 3x12x2+5x3≥5 ◎ ? 這種對(duì)過(guò)濾條件的改進(jìn)，更可以減少計(jì)算量。 表 55 條件 點(diǎn) ◎ ① ② ③ ④ 滿足條件 ? 是 ( √ ) 否 ( ) z 值 (0,0,0) (0,0,1) (0,1,0) (0,1,1) (1,0,0) (1,0,1) (1,1,0) (1,1,1) 0 5 2 3 3 8 1 6 1 1 1 0 2 1 5 1 2 6 0 1 1 1 0 1 √ √ √ 5 3 8 注意： 一般常重新排列 xi的順序使目標(biāo)函數(shù)中 xi的系數(shù)是遞增 (不減 )的 ， 在上例中 ， 改寫 z=3x12x2+5x3=2x2+3x1+5x3 ? 因?yàn)?2， 3， 5是遞增的序，變量 (x2， x1，x3)也按下述順序取值： (0， 0， 0)， (0， 0， 1)， (0， 1， 0)， (0， 1， 1)， …， ? 這樣，最優(yōu)解容易比較早的發(fā)現(xiàn)。 再結(jié)合過(guò)濾條件的改進(jìn)，更可使計(jì)算簡(jiǎn)化 ? 。 在上例中 ? max z=2x2+3x1+5x3 ? 2x2+3x1+5x3≥3 ◎ ? 2x2+x1x3≤2 ① ? 4x2+x1+x3≤4 ② (518) ? x2+x1≤3 ③ ? 4x2+x3≤6 ④ ? 解題時(shí)按下述步驟進(jìn)行 (見(jiàn)表 56)： 表 56（ a）（ b） 條件 點(diǎn) (x 2 ,x 1 ,x 3 ) ◎ ① ② ③ ④ 滿足條件 ? 是 ( √ ) 否 ( ) z 值 (0,0,0) (0,0,1) 0 5 1 1 0 1 √ 5 條件 點(diǎn) (x 2 ,x 1 ,x 3 ) ◎ ’ ① ② ③ ④ 滿足條件 ? 是 ( √ ) 否 ( ) z 值 (0,1,0) (0,1,1) 3 8 0 2 1 1 √ 8 ? 改進(jìn)過(guò)濾條件 ， 用 ? 2x2+3x1+5x3≥5 ◎ ′ ? 代替 ◎ ， 繼續(xù)進(jìn)行 。 ? 再改進(jìn)過(guò)濾條件 ， 用 ? 2x2+3x1+5x3≥8 ◎ ″ ? 代替 ◎ ′ ， 再繼續(xù)進(jìn)行 。 至此 ， z值已不能改進(jìn) ， 即得到最優(yōu)解 ， 解答如前 ， 但計(jì)算已簡(jiǎn)化 。 表 56（ c） 條件 ? 點(diǎn) (x 2 ,x 1 ,x 3 ) ◎″ ① ② ③ ④ 滿足條件 ? 是 ( √ ) 否 ( ) z 值 (0,0,0) (0,0,1) (1,1,0) (1,1,1) 2 3 1 6 ? 第 5章，第 1， 2， 3， 4節(jié)結(jié)束
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1