任务五　整数规划的软件求解

用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所示。