数学规划概述要点.ppt

用连续优化方法求解松弛问题，如果松弛问题最优解（分量）全为整数，则也是原整数规划问题的最优解（见例1） 对松弛问题的最优解（分量）舍入为整数，得到的往往不是原整数规划问题的最优解（甚至不是可行解） ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． x1 x2 0 P o 6 9 Zmax 5 6 去掉整数限制后，可行域为点（0,0), (6,0), (0,5), P (2.25,3.75) 围成的4边形 从LP最优解经过简单的 “移动”不一定能得到IP最优解 例 LINDO可用于求解线性纯整数规划或混合整数规划(IP)， 模型的输入与LP问题类似, 但需在END标志后定义整型变量。 0/1型的变量可由INTEGER（可简写为INT）命令来标识， 有以下两种可能的用法： INT vname INT n 前者只将决策变量vname标识为0/1型, 后者将当前模型中前n 个变量标识为0/1型（模型中变量顺序由模型中输入时出现的先后顺序决定, 该顺序可由输出结果中的变量顺序查证是否一致）。 一般的整数变量可用命令GIN （是GENERAL INTEGER的意思）,其使用方式及格式与INT 命令相似。 LINDO求解整数线性规划概述 纯整数规划 - 聘用方案 决策变量：周一至周日每天(新)聘用人数 x1, x2,?x7 目标函数：7天(新)聘用人数之和 约束条件：周一至周日每天需要人数 连续工作5天 周一工作的应是(上)周四至周一聘用的 设系统已进入稳态（不是开始的几周） 聘用方案 整数规划 模型(IP) 首先在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