DMC第四講

時(shí)間：4月10日周五 18:00~20:00

騰訊會(huì)議ID：242 125 010

整數(shù)規(guī)劃

????生活中的很多實(shí)際問題都可以歸結(jié)為整數(shù)規(guī)劃問題，如車輛路徑規(guī)劃問題、背包問題和倉儲(chǔ)物流規(guī)劃等。我們將在本次DMC中為大家介紹整數(shù)規(guī)劃的相關(guān)內(nèi)容，包括整數(shù)規(guī)劃的問題形式、對偶理論、精確求解算法以及啟發(fā)式求解算法。

主要內(nèi)容

1

線性整數(shù)規(guī)劃及精確解法

線性整數(shù)規(guī)劃可以看做線性規(guī)劃的一個(gè)特殊部分，只是將線性規(guī)劃中的全部或部分變量限制為整數(shù)，在1958年Gomory提出割平面法后逐漸形成獨(dú)立的分支。我們將介紹整數(shù)規(guī)劃的基本概念：整數(shù)規(guī)劃是什么，一些經(jīng)典的整數(shù)規(guī)劃問題，整數(shù)規(guī)劃問題的分類；以及經(jīng)典的精確式解法：用于求解純整數(shù)規(guī)劃和混合整數(shù)規(guī)劃的分枝定界法、割平面法和用于求解指派問題(特殊0-1整數(shù)規(guī)劃)的匈牙利算法

2

對偶理論

對偶理論在整數(shù)規(guī)劃的求解中有重要作用。在原問題較難求解時(shí)，利用拉格朗日松弛以及原問題的獨(dú)特結(jié)構(gòu)，從而得到便于求解的松弛形式，能夠大大降低問題的求解難度。為了能夠求解不光滑的對偶問題，我們也會(huì)引入次梯度的概念，使用次梯度下降方法求解對偶問題。

3

啟發(fā)式求解算法

問題復(fù)雜度的研究對于整數(shù)規(guī)劃至關(guān)重要，對問題的正確分類有助于我們找到對具體問題合適的求解方法。在精確算法難以得到精確解時(shí)，我們考慮使用啟發(fā)式算法在較快時(shí)間內(nèi)得到一個(gè)滿意的可行解。我們將從局部搜索算法開始，介紹其如何處理約束，我們也會(huì)介紹其他啟發(fā)式算法，如禁忌搜索算法，模擬退火算法等。

掃碼關(guān)注我們

?DMC

總結(jié)

以上是生活随笔為你收集整理的割平面法只能求解纯整数规划吗_【DMC第四讲】整数规划的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。