運(yùn)籌學(xué)課件第5章整數(shù)線性規(guī)劃-第1-4節(jié)-展示頁
2024-10-27 21:04本頁面
【正文】 合于條件⑤ 。 本例還可以用圖解法來說明。 ? 是不是可以把所得的非整數(shù)的最優(yōu)解經(jīng)過 “ 化整 ”就可得到合于條件 ⑤ 的整數(shù)最優(yōu)解呢 ?如將 (x1=，x2=0)湊整為 (x1=5， x2=0)， 這樣就破壞了條件 ② (關(guān)于體積的限制 )， 因而它不是可行解；如將 (x1=，x2=0)舍去尾數(shù) ， 變?yōu)?(x1=4， x2=0)， 這當(dāng)然滿足各約束條件 ， 因而是可行解 ， 但不是最優(yōu)解 ， 因?yàn)楫?dāng) x1=4， x2=0, 時(shí) z=80. ? 非整數(shù)的最優(yōu)解在 C(， 0)點(diǎn)達(dá)到 。 這是一個(gè) (純 )整數(shù)線性規(guī)劃問題 ， 用數(shù)學(xué)式可表示為： max z =20x1+10x2 ① 5x1+4x2≤24 ② 2x1+5x2≤13 ③ () x1， x2≥0 ④ x1， x2整數(shù) ⑤ 它和線性規(guī)劃問題的區(qū)別僅在于最后的條件⑤。 例 1某廠擬用集裝箱托運(yùn)甲乙兩種貨物 ， 每箱的體積 、 重量 、 可獲利潤以及托運(yùn)所受限制如表 51所示 。本章最后講到的指派問題就是一個(gè) 01規(guī)劃問題。 ? 整數(shù)線性規(guī)劃中如果所有的變數(shù)都限制為 (非負(fù) )整數(shù)，就稱為純整數(shù)線性規(guī)劃 (pure integer linear programming)或稱為全整數(shù)線性規(guī)劃 (all integer linear programming)；如果僅一部分變數(shù)限制為整數(shù)，則稱為混合整數(shù)計(jì)劃 (mixed integer linear programming)。因此，對(duì)求最優(yōu)整數(shù)解的問題，有必要另行研究。為了滿足整數(shù)解的要求，初看起來，似乎只要把已得到的帶有分?jǐn)?shù)或小數(shù)的解經(jīng)過 “ 舍入化整 ” 就可以了。 運(yùn)籌學(xué) （第三版） 《 運(yùn)籌學(xué) 》 教材編寫 組 第 5章 整數(shù)線性規(guī)劃 第 14節(jié) 清華大學(xué)出版社 第 5章 整數(shù)線性規(guī)劃 ? 第 1節(jié) 整數(shù)線性規(guī)劃問題的提出 ? 第 2節(jié) 分支定界解法 ? 第 3節(jié) 割平面解法 ? 第 4節(jié) 01型整數(shù)線性規(guī)劃 ? 第 5節(jié) 指 派 問 題 ? 第 1節(jié) 整數(shù)線性規(guī)劃問題的提出 ? 在前面討論的線性規(guī)劃問題中，有些最優(yōu)解可能是分?jǐn)?shù)或小數(shù)，但對(duì)于某些具體問題，常有要求解答必須是整數(shù)的情形 (稱為整數(shù)解 )。例如，所求解是機(jī)器的臺(tái)數(shù)、完成工作的人數(shù)或裝貨的車數(shù)等，分?jǐn)?shù)或小數(shù)的解答就不合要求。但這常常是不行的，因?yàn)榛蟛灰姷檬强尚薪猓换螂m是可行解，但不一定是最優(yōu)解。我們稱這樣的問題為整數(shù)線性規(guī)劃(integer linear programming)，簡(jiǎn)稱 ILP，整數(shù)線性規(guī)劃是最近幾十年來發(fā)展起來的規(guī)劃論中的一個(gè)分支。整數(shù)線性規(guī)劃的一種特殊情形是 01規(guī)劃，它的變數(shù)取值僅限于 0或 1。 ? 現(xiàn)舉例說明用前述單純形法求得的解不能保證是整數(shù)最優(yōu)解 。 問兩種貨物各托運(yùn)多少箱 ， 可使獲得利潤為最大 ?表 51 貨物 體積 (m 3 / 箱 ) 重量 (100kg/ 箱 ) 利潤 (100 元 / 箱 ) 甲 乙 5 4 2 5 20 10 托運(yùn)限制 24m3 1300kg ? 現(xiàn)在我們解這個(gè)問題 ， 設(shè) x1， x2分別為甲 、 乙兩種貨物的托運(yùn)箱數(shù) (當(dāng)然都是非負(fù)整數(shù) )?，F(xiàn)在我們暫不考慮這一條件，即解①～④ (以后我們稱這樣的問題為與原問題相應(yīng)的線性規(guī)劃問題 )， 很容易求得最優(yōu)解為 :x1=， x2=0， max z=96 但 x1是托運(yùn)甲種貨物的箱數(shù) ， 現(xiàn)在它不是整數(shù) ， 所以不合條件 ⑤ 的要求 。 但當(dāng) x1=4， x2=1(這也是可行解 )時(shí)， z=90。 見圖 5 1 ? 圖中畫 (+)號(hào)的點(diǎn)表示可行的整數(shù)解 。 為了滿足題中要求 ， 表示目標(biāo)函數(shù)的 z的等值線必須向原點(diǎn)平行移動(dòng) ， 直到第一次遇到帶 “ +”號(hào) B點(diǎn) (x1=4， x2=1)為止 。 ? 由上例看出 ， 將其相應(yīng)的線性規(guī)劃的最優(yōu)解 “ 化整 ” 來解原整數(shù)線性規(guī)劃 ， 雖是最容易想到的 ， 但常常得不到整數(shù)線性規(guī)劃的最優(yōu)解 ， 甚至根本不是可行解 。 第 2節(jié) 分支定界解法 ? 在求解整數(shù)線性規(guī)劃時(shí) ， 如果可行域是有界的 ， 首先容易想到的方法就是窮舉變量的所有可行的整數(shù)組合 ， 就像在圖 51中畫出所有“ +”號(hào)的點(diǎn)那樣 ， 然后比較它們的目標(biāo)函數(shù)值以定出最優(yōu)解 。 在例 1中，變量只有 x1和 x2 ? 由條件②， x1所能取的整數(shù)值為 0、 4共 5個(gè)；由條件③， x2所能取的整數(shù)值為 0、 2共 3個(gè)，它的組合 (不都是可行的 )數(shù)是 3 5=15個(gè)，窮舉法還是勉強(qiáng)可用的。例如在本章第 5節(jié)的指派問題 (這也是整數(shù)線性規(guī)劃 )中，將 n項(xiàng)任務(wù)指派 n個(gè)人去完成，不同的指派方案共有 n!種，當(dāng) n=10，這個(gè)數(shù)就超過 300萬；當(dāng) n=20，這個(gè)數(shù)就超過 2 1018，如果一一計(jì)算，就是用每秒百萬次的計(jì)算機(jī)，也要幾萬年的功夫，很明顯，解這樣的題，窮舉法是不可取的。分支定界解法 (branch and bound method)就是其中的一個(gè) . ? 分支定界法可用于解純整數(shù)或混合的整數(shù)線性規(guī)劃問題 。由于這方法靈活且便于用計(jì)算機(jī)求解 ， 所以現(xiàn)在它已是解整數(shù)線性規(guī)劃的重要方法 。分支定界法就是將 B的可行域分成子區(qū)域 (稱為分支 )的方法 ， 逐步減小和增大 ， 最終求到 z*。 這時(shí) z0是問題 A的最優(yōu)目標(biāo)函數(shù)值 z*的上界 ， 記作 z0= 。 zz zzz分支定界法的解法 ? 首先注意其中一個(gè)非整數(shù)變量的解 ， 如 x1， 在問題 B的解中 x1=。 這并不影響問題 A的可行域 ， 不考慮整數(shù)條件解問題 B1和 B2， 稱此為第一次迭代 。 因z1＞ z2， 故將 改為 349， 那么必存在最優(yōu)整數(shù)解 ， 得到 z*， 并且 0≤z*≤ 349 z繼續(xù)對(duì)問題 B1和 B2進(jìn)行分解 ? 因 z1＞ z2，故先分解 B1為兩支。在圖 53中再舍去 x2＞ 2與 x3＜ 3之間的可行域， ? 再進(jìn)行第二次迭代。
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1