整数线性规划的求解.pptVIP

LINDO求解整数线性规划概述 例2.6 员工聘用问题 例2.7 游泳队员的选拔问题（0-1规划） 讨论 例2.8 汽车生产计划（混合整数规划） 模型建立与求解 备注 优 化 建 模 LINDO可用于求解线性纯整数规划或混合整数规划(IP)， 模型的输入与LP问题类似, 但需在END标志后定义整型变量。 0/1型的变量可由INTEGER（可简写为INT）命令来标识， 有以下两种可能的用法： INT vname INT n 前者只将决策变量vname标识为0/1型, 后者将当前模型中前n 个变量标识为0/1型（模型中变量顺序由模型中输入时出现的先后顺序决定, 该顺序可由输出结果中的变量顺序查证是否一致）。 一般的整数变量可用命令GIN （是GENERAL INTEGER的意思）,其使用方式及格式与INT 命令相似。。 首先在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 + 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名员工，由于员工人数只能是整数，所以至少要聘用94（人）。而第一条说明目前得到的解就是聘用94（人），所以已经是最优的了。 LP OPTIMUM FOUND AT STEP 8 OBJECTIVE VALUE = 93.3333359 SET X2 TO = 4 AT 1, BND= -94.00 TWIN= -93.50 18 NEW INTEGER SOLUTION OF 94.0000000 AT BRANCH 1 PIVOT 18 BOUND ON OPTIMUM: 93.50000 DELETE X2 AT LEVEL 1 ENUMERATION COMPLETE. BRANCHES= 1 PIVOTS= 18 LAST INTEGER SOLUTION IS THE BEST FOUND RE-INSTALLING BEST SOLUTION... 求解结果的报告窗口如下： （接下页） OBJECTIVE FUNCTION VALUE 1) 94.00000 VARIABLE VALUE REDUCED COST X1 0.000000 1.000000 X2 4.000000 1.000000 X3 40.000000 1.000000 X4 2.000000 1.000000 X5 34.000000 1.000000 X6 10.000000 1.000