整数线性规划的求解

《整数线性规划的求解》由会员分享，可在线阅读，更多相关《整数线性规划的求解（15页珍藏版）》请在金锄头文库上搜索。

1、 优 化 建 模 LINDO求解整数线性规划概述LINDO可用于求解线性纯整数规划或混合整数规划(IP)，模型的输入与LP问题类似, 但需在END标志后定义整型变量。 0/1型的变量可由INTEGER（可简写为INT）命令来标识， 有以下两种可能的用法：INT vname INT n 前者只将决策变量vname标识为0/1型, 后者将当前模型中前n 个变量标识为0/1型（模型中变量顺序由 模型中输入时出现的先后顺序决定, 该顺序可由输出结果中的 变量顺序查证是否一致）。 一般的整数变量可用命令GIN （是GENERAL INTEGER的意 思）,其使用方式及格式与INT 命令相似。优 化 建

2、模 例2.6 员工聘用问题 首先在LINDO模型窗口输入模型 :MIN X1 + X2 + X3 + X4 + X5 + X6 + X7 SUBJECT TO MON) X1 + X4 + X5 + X6 + X7 = 50 TUE) X1 + X2 + X5 + X6 + X7 = 50 WED) X1 + X2 + X3 + X6 + X7 = 50 THU) X1+ X2 + X3 + X4 +X7 = 50 FRI) X1 + X2 + X3 + X4 - X5 = 80 SAT) X2 + X3 + X4 - X5 + X6 = 90 SUN) X3 + X4 - X5 + X6 +

3、 X7 = 90 END GIN 7其中“GIN 7”表示7个变量都是一般整数变量。 （仍然默认为取值是非负的）优 化 建 模求解后状态窗口中与整数相关的三个域有了相关结果:“Best IP ：94”表示当前 得到的最好的整数解的目 标函数值为94（人）。 “IP Bound ：93.5” 表示 该整数规划目标值的下界 为93.5 （人）。 “Branches ：1”表示分枝 数为1（即在第1个分枝中 就找到了最优解）。 我们前面说过，LINDO求解IP 用的是分枝定界法。显然，上面第二条“整数规划目标值的下界为93.5 （人）”表明至少要聘 用93.5名员工，由于员工人数只能是整数，所以至少

4、要聘用94（人）。 而第一条说明目前得到的解就是聘用94（人），所以已经是最优的了。优 化 建 模LP OPTIMUM FOUND AT STEP 8OBJECTIVE VALUE = 93.3333359SET X2 TO = 4 AT 1, BND= -94.00 TWIN= -93.50 18NEW INTEGER SOLUTION OF 94.0000000 AT BRANCH 1 PIVOT 18BOUND ON OPTIMUM: 93.50000DELETE X2 AT LEVEL 1ENUMERATION COMPLETE. BRANCHES= 1 PIVOTS= 18LAST

5、INTEGER SOLUTION IS THE BEST FOUNDRE-INSTALLING BEST SOLUTION.求解结果的报告窗口如下： （接下页）优 化 建 模OBJECTIVE FUNCTION VALUE1) 94.00000VARIABLE VALUE REDUCED COSTX1 0.000000 1.000000X2 4.000000 1.000000X3 40.000000 1.000000X4 2.000000 1.000000X5 34.000000 1.000000X6 10.000000 1.000000 X7 4.000000 1.000000ROW SLA

6、CK OR SURPLUS DUAL PRICESMON) 0.000000 0.000000TUE) 2.000000 0.000000WED) 8.000000 0.000000THU) 0.000000 0.000000FRI) 0.000000 0.000000SAT) 0.000000 0.000000SUN) 0.000000 0.000000NO. ITERATIONS= 18BRANCHES= 1 DETERM.= 1.000E 0优 化 建 模报告窗口中前两行告诉我们：在8次迭代后找到对应的线性 规划（LP）问题的最优解，最优值=93.3333359。 LINDO求解IP用的

7、是分枝定界法，紧接着几行显示的是分 枝定界的信息，在第1个分枝中设定x2=4,并在该分枝中 找到了整数解，而且就是全局整数最优解，所以算法停止 。旋转迭代（PIVOT）共18次。 后面显示的是最后的最优解：x=(0,4,40,2,34,10,4).松弛和剩余变量（SLACK OR SURPLUS）仍然可以表示 约束的松紧程度，但目前IP尚无相应完善的敏感性分析理 论，因此REDUCED COST和DUAL PRICES的结果在整数 规划中意义不大。 优 化 建 模 例2.7 游泳队员的选拔问题（0-1规划） 在LINDO模型窗口中输入模型：MIN 66.8x11+75.6x12+87 x13+

8、58.6x14+57.2x21+66 x22+66.4x23+53 x24+78 x31+67.8x32+84.6x33+59.4x34+70 x41+74.2x42+69.6x43+57.2x44+67.4x51+71x52+83.8x53+62.4x54 SUBJECT TOx11+x12+x13+x14 0 x2 - 80 y2 0 x3 - 80 y3 0 end int y1 int y2 int y3优 化 建 模OBJECTIVE FUNCTION VALUE1) 611.2000VARIABLE VALUE REDUCED COSTY1 1.000000 108.800003Y

9、2 1.000000 0.000000Y3 0.000000 0.000000X1 80.000000 0.000000X2 150.399994 0.000000X3 0.000000 0.800000ROW SLACK OR SURPLUS DUAL PRICES2) 28.799999 0.0000003) 0.000000 0.0120004) 920.000000 0.0000005) 849.599976 0.0000006) 0.000000 0.0000007) 0.000000 -1.3600008) 70.400002 0.0000009) 0.000000 0.00000

10、0NO. ITERATIONS= 25BRANCHES= 1 DETERM.= 1.000E 0求解得到输出如下 ：即：只生产小型 和中型汽车，产 量分别为80辆和 150辆(近似值), 可获得最大利润 611.2万元。 不妨试试把产 量x也限定只取 整数，结果会 如何呢？ 优 化 建 模尽管LINDO 对整数规划问题很有威力, 但要想有效地使 用，有时还是需要一定的技巧的。这是因为, 人们很容易将 一个本质上很简单的问题列成一个不太好的输入模型, 从而 有可能会导致一个冗长的分枝定界计算。遗憾的是，我们往 往难以预先估计什么样的模型才能避免冗长的分枝定界计算 ，也难以判别什么样的模型是“不太好”的输入模型。当然这 时 LINDO 会主动砍去一些计算过程, 以缩短计算时间，而 且越是高版本的LINDO软件，这种自动处理的“智能”越强 。我们的建议是：如果分枝定界计算时间很长仍得不到最优 解，你可以试试对输入模型进行一些等价变换：如交换变量 的次序，交换约束的顺序等，有时也许会对减少求解所需的 时间有所帮助。 备注