第二章-整数规划.doc

第二章整数规划

整数规划模型介绍

规划中的变量〔局部或全部〕限制为整数时，称为整数规划。假设在线性规划模型中，变量限制为整数，那么称为整数线性规划。对于整数线性规划模型大致可分为三类：

〔1〕变量全限制为整数时，称纯〔完全〕整数线性规划。

〔2〕变量局部限制为整数的，称混合整数线性规划。

〔3〕变量只能取0或1时，称之为0-1线性规划。

整数线性规划特点

〔=1\*romani〕原线性规划有最优解，当自变量限制为整数后，其整数规划解会出现下述情况：

〔1〕原线性规划最优解全是整数，那么整数线性规划最优解与线性规划最优解一致。

〔2〕整数线性规划无可行解。

〔3〕有可行解〔当然就存在最优解〕，但最优解值一定不会优于原线性规划的最优值。

〔=2\*romanii〕整数规划最优解不能按照实数最优解简单取整而获得。

二、整数规划的求解法之一〔分枝定界法〕

2.1分枝定界法的思想

对有约束条件的最优化问题〔其可行解为有限数〕的可行解空间恰当地进行系统搜索，这就是分枝与定界内容。通常，把全部可行解空间反复地分割为越来越小的子集，称为分枝；并且对每个子集内的解集计算一个目标上(下)界〔对于最大(小)值问题〕，这称为定界。在每次分枝后，但凡界限不优于可行解集目标值的那些子集不再进一步分枝，这样，许多子集可不予考虑，这称剪枝。这就是分枝定界法的主要思路。现用下例来说明：

例1求解下述整数规划

s.t.(2.1)

解〔=1\*romani〕先不考虑整数限制，即作为一般线性规划问题求解，得最优解为：

可见它不符合整数条件。这时是原问题的最优目标函数值的上界，记作。而显然是原问题的一个整数可行解，这时，是的一个下界，记作，即。

〔=2\*romanii〕因为当前均为非整数，故不满足整数要求，任选一个进行分枝。设选进行分枝：，,将原问题A分成两个子问题B1和B2。

问题：

s.t.

最优解为：。

问题：

s.t.

最优解为：。

再定界：。

〔=3\*romaniii〕对问题对再进行分枝：，，得问题和，它们的最优解为

再定界：，并将剪枝。

〔=4\*romaniv〕对问题对再进行分枝：，，得问题和，它们的最优解为

无可行解。

将剪枝。

于是可以断定原问题的最优解为：

从以上解题过程可得用分枝定界法求解整数规划〔最大化〕问题的步骤为：

开始，将要求解的整数规划问题称为问题，将与它相应的线性规划问题称为问题。

〔=1\*romani〕解问题可能得到以下情况之一：

〔a〕没有可行解，这时也没有可行解，那么停止．

〔b〕有最优解，并符合问题的整数条件，的最优解即为的最优解，那么停止。

〔c〕有最优解，但不符合问题的整数条件，记它的目标函数值为。

〔=2\*romanii〕用观察法找问题的一个整数可行解，一般可取，求得其目标函数值，并记作。以表示问题的最优目标函数值；这时有

进行迭代。

第一步：分枝，在的最优解中任选一个不符合整数条件的变量，其值为，以表示小于的最大整数。构造两个约束条件

和

将这两个约束条件，分别参加问题，求两个后继规划问题和。不考虑整数条件求解这两个后继问题。

定界，以每个后继问题为一分枝标明求解的结果，与其它问题的解的结果中，找出最优目标函数值最大者作为新的上界。从已符合整数条件的各分支中，找出目标函数值为最大者作为新的下界，假设无作用。

第二步：比拟与剪枝，各分枝的最优目标函数中假设有小于者，那么剪掉这枝，即以后不再考虑了。假设大于，且不符合整数条件，那么重复第一步骤。一直到最后得到为止。得最优整数解。

2.2整数规划的计算机解法

例2求解以下整数规划问题：

s.t.(2.2)

在LINGO模型窗口中输入以下模型：

MIN=X1+X2-4*X3;

X1+X2+2*X3=9;

X1+X2-X3=2;

-X1+X2+X3=4;

@GIN(X1);@GIN(X2);@GIN(X3);

选菜单Lingo|Solve〔或按Ctrl-S〕，或用鼠标点击“solve”按钮，可得结果如下：

Globaloptimalsolutionfound.

Objectivevalue:-16.00000

Extendedsolversteps:0

Totals