任務五　整數規劃的軟件求解

用WinQSB求解整數規劃，主要使用到的是該軟件的“Linear and Integer Programming”（線性和整數規劃）模塊。

5.1　整數規劃

接下來，用WinQSB的Linear and Integer Programming模塊求解一下例3-1-1的問題。

（1）首先，點擊WinQSB中的“Linear and Integer Programming”，進入初始界面。點擊“新建”按鈕（即快捷欄中印有網格狀的按鈕）或“files”里的“New problem”，屏幕出現名為“LP-ILP Problem Specification”（問題描述）的工作界面。填入Problem Title（問題名稱）：例3-1-1；Number of Variables（變量個數）：2；Number of Constrains（約束條件個數）：2，這里的約束條件仍然不包括非負約束和整數約束，所以原模型的約束條件為2個；選擇Objective Criterion（目標函數的類型），因為我們題目是求最大值，所以在這里選擇Maximization；選擇Data Entry Format（數據輸入格式），我們可以選擇Spreadsheet Matrix Form，即表格輸入；最后選擇Default Variable Type（系統默認的變量類型），變量類型與線性規劃不同，在這里，我們選擇Nonnegative integer，具體參數見圖3-5-1。

（2）在彈出的窗口中輸入數據，見圖3-5-2。

（3）求解。單擊“Solve and Analyze—Solve the problem”，彈出對話框如圖3-5-3所示，點擊“確定”。

這時，就可以得到計算結果，如圖3-5-4所示。

所以最優解為（0，5），最優值maxz＝40。

5.2　0—1規劃

下面，我們用WinQSB求解例3-3-2的0—1規劃。

（1）首先，點擊WinQSB中的“Linear and Integer Programming”，進入初始界面。點擊“新建”按鈕或“files”里的“New problem”，填入Problem Title、Number of Variables、Number of Constrains，選擇Objective Criterion，選擇數據輸入格式Data Entry Format中的Spreadsheet Matrix Form，最后選擇Default Variable Type（系統默認的變量類型），在這里，我們選擇Binary［0，1］，如圖3-5-5所示。

（2）在彈出的窗口中輸入數據，如圖3-5-6所示。

（3）求解。單擊“Solve and Analyze—Solve the problem”，在彈出的對話框點擊確定，得到分析結果，如圖3-5-7所示。

5.3　指派問題

下面，我們用WinQSB求解例3-4-1的指派問題。指派問題和整數規劃、0—1規劃的求解不同，它的求解是使用“Network Modeling”（網絡建模）模塊求解的。

（1）首先，點擊WinQSB中的“Network Modeling”，進入初始界面。點擊“新建”按鈕或“files”里的“New problem”，在彈出的工作界面中選擇Assignment Problem（分配問題），填入Problem Title、Number of Objects（人數）、Number of Assignments（任務數），選擇Objective Criterion（目標函數的類型），選擇數據輸入格式Data Entry Format中的Spreadsheet Matrix Form，單擊“OK”，如圖3-5-8所示。

在這里，人數和任務數可以不相等。對于最大化指派問題，目標函數的類型要選擇Maximization。

（2）在彈出的窗口中輸入數據，如圖3-5-9所示。

（3）求解。單擊“Solve and Analyze—Solve the problem”，得到分析結果，如圖3-5-10所示。