任務一　整數規劃的概念

1.1　整數規劃問題

1.1.1　整數規劃的概念

在實際問題中，因為決策變量不可無限細分而必須取整數時，這類規劃問題稱為整數規劃。整數規劃可以是線性的，也可以是非線性的。如果目標函數和約束條件都是線性的，那么把這種整數規劃稱為整數線性規劃。本書只研究整數線性規劃。

1.1.2　整數規劃的分類

如果一個整數規劃問題中所有決策變量要求取非負整數，那么把它稱為純整數規劃。如果只有一部分的決策變量要求取非負整數，另一部分可以取非負實數，就把它稱為混合整數規劃。當所有決策變量只能取0或1兩個整數時，把它稱為0—1規劃。

1.1.3　整數規劃問題的提出

整數線性規劃問題和線性規劃問題的區別就是決策變量要求部分還是全部為整數，所以，整數規劃模型的建立類似線性規劃。在下面的敘述中，我們把整數線性規劃簡稱為整數規劃。

例3-1-1　生產計劃問題　某廠在一個計劃期內擬生產甲、乙兩種大型設備。該廠有充分的生產能力來加工制造這兩種設備的全部零件，所需原材料和能源基本上能滿足供應，只有A、B兩種生產原料的供應受到嚴格限制。可供原料總量、每臺設備所需的原料的數量及利潤如表3-1-1所示。問該廠安排生產甲、乙設備各多少臺，才能使利潤達到最大？

表3-1-1

解：設x1、x2分別為該廠計劃期內生產甲、乙設備的臺數，z為生產這兩種設備可獲得的總利潤。x1、x2都是非負整數，根據題意，該生產計劃問題的數學模型為

顯然，若不考慮取整的條件的話，上述模型就是線性規劃模型。因此我們可以把去掉整數約束條件后得到的線性規劃稱為原整數規劃的松弛問題。

因此，整數規劃的一般形式為

1.2　整數規劃問題的求解

整數規劃問題就是一種特殊的線性規劃問題，那么可不可以用單純形法來求解，然后用取整數的方式獲得整數規劃的解呢？我們通過下面的例題3-1-2來分析一下。

例3-1-2　求解整數規劃問題。

先不考慮整數約束，用圖解法求解上述整數規劃的松弛問題，得到其可行域，如圖3-1-1所示。

通過圖3-1-1可以看出，該線性規劃問題的最優解，，。如果用“舍入取整法”可得到4個點即（1，3）、（2，3）、（1，4）、（2，4）。通過圖可以發現，它們都不是整數規劃的最優解，甚至不是可行解。按整數規劃約束條件，其可行解肯定在線性規劃問題的可行域內且為整數點。故整數規劃問題的可行解集是一個有限集，因此，可以將集合內的整數點一一找出，其最大目標函數的值為最優解，這種方法叫做完全枚舉法。

可以發現在所有的可行解中，在（2，2）、（3，1）處可以取得目標函數的最大值，這時z＝4。

由此可見，將松弛問題的最優解簡單取整之后，一般得不到原整數規劃的最優解，甚至不能保證是可行解。如果整數規劃的可行域是有界的，那么原整數規劃的可行解集應該是有限點集，因此，在問題規模不太大的情況下，可以考慮用上文的完全枚舉法來求解整數規劃。但對于復雜問題而言，這種方法并不是有效的。有時候即使用計算機，也無法在人們可接受的時間內找到最優解。整數規劃問題的求解成了運籌學的一大難題。近幾十年來，經過艱苦的努力，人們研究出了許多相對有效的算法來解決這個難題，比如分支定界法、割平面法等。從原理上看，這些方法大部分都是基于整數規劃和它的松弛問題的關系的。