1、上页 下页 返回整数规划（ integer programming)1.几个实例2.整数规划的算法 分支定界法和割平面方法3.Lingo/Lindo求解整数规划上页 下页 返回例 1。人员安排问题整数规划某宾馆一天各时段需要的人数如下所示。按规定，服务员连续工作八小时为一 班。现要求安排服务员的工作时间，使所需服务员总数最少。上页 下页 返回时段 始末时间 所需服务员人数1 6:008:00 62 8:0010:00 123 10:0012:00 104 12:0014:00 85 14:0016:00 96 16:0018:00 147 18:0020:00 88 20:0022:00 69
2、 22:0024:00 4某宾馆一天各时段需要的人数如下所示。按规定，服务员连续工作八小时为一 班。现要求安排服务员的工作时间，使所需服务员总数最少。上页 下页 返回解：设 xj 表示第 j时段开始上班的服务员人数。由于每两小时为一时段，所以第 j时段开始上班的服务员将在第 j+3时段结束时下班。因此只考虑相应的模型为：时段 始末时间 所需服务员人数1 6:008:00 62 8:0010:00 123 10:0012:00 104 12:0014:00 85 14:0016:00 96 16:0018:00 147 18:0020:00 88 20:0022:00 69 22:0024:00
3、 4上页 下页 返回时段 始末时间 所需服务员人数1 6:008:00 62 8:0010:00 123 10:0012:00 104 12:0014:00 85 14:0016:00 96 16:0018:00 147 18:0020:00 88 20:0022:00 69 22:0024:00 4第 4阶段5阶段6阶段7阶段7阶段9阶段上页 下页 返回整数规划上页 下页 返回利用数学软件 lingo可求得一个最优解为：X1 = 12.000000 X2 = 0.000000 X3 = 6.000000 X4 = 2.000000 X5 = 1.000000 X6 = 5.000000 最优
4、值为 26，具体过程如下：上页 下页 返回求解程序为 Liti1aMIN =x1+x2+x3+x4+x5+x6;x16;x1+x212;x1+x2+x310;x1+x2+x3+x48;x2+x3+x4+x59;x3+x4+x5+x614;x4+x5+x68;x5+x66;x64;gin(x1);gin(x2);gin(x3);gin(x4);gin(x5);gin(x6);end上页 下页 返回OBJECTIVE FUNCTION VALUE(1) 26.00000 VARIABLE VALUE X1 12.000000 X2 0.000000X3 6.000000X4 2.000000X5
5、1.000000X6 5.000000 另一最优解为OBJECTIVE FUNCTION VALUE1) 26.00000VARIABLE VALUEX1 6.000000X2 6.000000X3 0.000000X4 0.000000X5 3.000000X6 11.000000最优解不唯一liti1b上页 下页 返回OBJECTIVE FUNCTION VALUE 1) 26.00000VARIABLE VALUE REDUCED COSTX1 12.000000 1.000000X2 0.000000 1.000000X3 6.000000 1.000000X4 2.000000 1.000000X5 1.000000 1.000000X6 5.000000 1.000000
