丁基橡膠

[拼音]：zhengshu guihua

[英文]：integer programming

要求變數取整數值的數學規劃。若所有變數均要求取整數值，則稱為純整數規劃。若只是部分變數要求取整數值，則稱為混合整數規劃。整數規劃一詞常指純整數規劃。要求變數取整數值的線性規劃稱為線性整數規劃。1963年R.E.戈莫里提出解線性整數規劃的割平面法。1965年R.J.達金和蘭德-多伊格提出分枝限界法。此後對於一般線性整數規劃先後建立了若干演算法理論，對於特殊結構的線性整數規劃建立了各種有效演算法。60年代後期，整數規劃的研究範圍開始擴充套件到非線性整數規劃。

解整數規劃問題的典型方法是逐次生成一個個相關問題,即衍生問題，再對每個衍生問題放寬約束條件,構成鬆弛問題。衍生問題稱為鬆弛問題的源問題。通過解鬆弛問題來確定捨棄此衍生問題，還是再生成一個或幾個新的衍生問題，如此繼續下去，直到不再有未解決的衍生問題。若鬆弛問題的解對於源問題是可行的，則源問題得解。否則在不排除原可行解的條件下修正可行域。解此修正問題，直到修正問題的最優解在原可行域內為止。解整數規劃問題時鬆弛約束的方法通常是略去整數性約束和附加線性不等式約束來實現可行域的修正。略去整數性就可按線性規劃求解，再分別附加兩個互相排斥的線性不等式之一,就是把這一個變數修正到整數,如此繼續下去，直到要求整數約束的變數都成為整數為止。此即分枝限界法。若只附加一個線性不等式，就是割平面法。

割平面法

滿足線性整數規劃約束條件的點集 S是一離散點陣，這對求解整數規劃帶來本質上的困難。取消變數的整數性要求就可變成一個線性規劃問題，稱為原整數規劃的鬆弛問題。解線性整數規劃的割平面法就是從鬆弛問題的一個非整數的最優解出發，序貫地每次新增一個新的線性不等式（其對應的線性方程所代表的超平面即稱為割平面），求解新的鬆弛問題。每次增添的新的不等式須滿足兩個條件：

（1）前一個鬆弛問題的最優解不滿足這個不等式，即鬆弛問題的可行解集合被割去了一“塊”；

（2）s中的“點”都滿足這個不等式,即保證整數可行解不被割去。這一演算法的主要問題是如何構造出有效的割平面，以便儘快地得到一個有整數最優解的鬆弛問題。

分枝限界法

一種解離散問題的最優化方法，可用以解線性整數規劃。分枝限界法的基本思想是部分列舉法。對於給定的求極大值的線性整數規劃P,可按下述步驟求解：

（1）演算法開始時，去掉整數約束，解對應的鬆弛問題P′；如果P′的最優解是整數解，也就得到了P的最優解；

（2）如果不是，則把 P的可行解集合劃分成兩部分，得到兩個線性整數規劃子問題P1,P2。然後對每個子問題，求解對應的鬆弛問題P姈,P娦。如果P姈的最優解是整數解x壒，則x1是P的可行解,並且目標函式值f(x壒)是P的一個下界Z0,這時對問題P1已經考慮完畢。如果P娦的最優解x壗的目標函式值f(x壗)＜Z0，則P2也沒有再考慮的必要,原問題P 的最優解就是x壒。如果f(x壗)≥Z0,再分兩種情況考慮:若x壗是整數解,則x壗是原問題P的最優解；若x壗不是整數解，則返回②,對P2進行類似P的考慮。經有限次迴圈之後，即求得原線性整數規劃的最優解。