分支定界算法在運(yùn)籌學(xué)模型中的應(yīng)用.pdf

1、整數(shù)規(guī)劃是一類特殊的規(guī)劃問(wèn)題，整數(shù)規(guī)劃是從1958年由 R.E.戈莫里提出割平面法之后形成獨(dú)立分支的，50多年來(lái)發(fā)展出很多方法解決各種問(wèn)題。這不僅因?yàn)樗鄬?duì)地簡(jiǎn)單，在理論和算法上都比較成熟，還因?yàn)樗旧碓趯?shí)際問(wèn)題中有著廣泛的應(yīng)用。由于在管理，經(jīng)濟(jì)以及工業(yè)生產(chǎn)的最優(yōu)化模型中的廣泛應(yīng)用，所以整數(shù)規(guī)劃在優(yōu)化理論中擔(dān)當(dāng)著十分重要的角色。
　　早在20世紀(jì)60年代由Land Doig和Dakin等人提出的分支定界算法以其獨(dú)特的算法策略被人們

2、所引用。其算法不僅適用于表達(dá)成整數(shù)線性規(guī)劃(或混合整數(shù)線性規(guī)劃)的問(wèn)題，也適用于幾乎任何組合優(yōu)化問(wèn)題。雖然整數(shù)規(guī)劃問(wèn)題是 NP困難的，但是線性問(wèn)題卻是有有效算法的。分支定界算法恰好就是利用這一點(diǎn)。
　　論文研究?jī)?nèi)容如下：
　　首先論文分析、總結(jié)了優(yōu)化理論、優(yōu)化算法的發(fā)展過(guò)程以及介紹了一種特殊的優(yōu)化算法－分支定界算法；
　　其次根據(jù)分支定界算法的思想原理對(duì)算法進(jìn)行改進(jìn)從而加速了算法的收斂性，并將改進(jìn)后的算法應(yīng)用于一維下料