整數(shù)規(guī)劃和0-1規(guī)劃(文件)
【正文】 1Z x x xx x xx x xs t x xxxx x x? ? ?? ? ???? ? ??????????? ??或Mathematical modeling 22 解：對(duì)于 01 規(guī)劃問題，由于每個(gè)變量只取 0， 1兩個(gè)值，一般會(huì)用窮舉法來解，即將所有的 0， 1 組合找出，使目標(biāo)函數(shù)達(dá)到極值要求就可求得最優(yōu)解。 Mathematical modeling 17 例 5一個(gè)旅行者要到某地作兩周的帶包旅行 ,裝背包時(shí) ,他發(fā)現(xiàn)除了已裝的必需物件外 ,他還能再裝 5公斤重的東西 .他打算從下列 4種東西中選取 ,使增加的重量不超過 5公斤又能使使用價(jià)值最大 .這 4種東西的重量和使用價(jià)值 (這里用打分?jǐn)?shù)的辦法表示價(jià)值 )如下表所示 ,問旅行者應(yīng)該選取哪些物件為好 ？ Mathematical modeling 18 解：建立模型為 ? ?1 2 3 41 2 3 4m a x Z = 6 x 7 3 92 3 4 5s . t. 0 , 1 1 , 2 , 3 , 4ix x xx x x xxi? ? ?? ? ? ????????Mathematical modeling 19 Mathematical modeling 20 由上表可知，問題的最優(yōu)解為 X*=( x1 =1 x2=0 x3=1 ) 但此法太繁瑣，工作量相當(dāng)大。01整數(shù)規(guī)劃 01整數(shù)規(guī)劃？ 01整數(shù)規(guī)劃法？ 01 整數(shù)規(guī)劃是一種特殊形式的整數(shù)規(guī)劃，這時(shí)的決策變量 xi 只取兩個(gè)值 0或 1，一般的解法為隱枚舉法。 這就是分枝定界法的主要思路 。 在求解整數(shù)規(guī)劃問題時(shí) ， 可將集合內(nèi)的整數(shù)點(diǎn)一一找出 ， 其最大目標(biāo)函數(shù)的值為最優(yōu)解 ， 此法為 完全枚舉法 。 顯然 ， 它們都不可能是整數(shù)規(guī)劃
研究報(bào)告相關(guān)推薦
鄂ICP備17016276號(hào)-1