4整数规划数学模型及其解法.pptVIP

* 数学模型 minz=175y2+300y3+375y4+500y5+8xll+4x12+3x13+5x21+2x22+3x23+4x31+3x32+4x33+9x41+7x42+5x43+10x51+4x52+2x53 xll+x12+x13≤30 x21+x22+x23≤10y2 x31+x32+x33≤20y3 x41+x42+x43≤30y4 x51+x52+x53≤40y5 xll+x21+x31+x41+x51=30 x12+x22+x32+x42+x52=20 x13+x23+x33+x43+x55=20 xij为非负整数 yi为0-1变量 产量约束 销量约束 * 解题（6） 最优解 y5=1，x52=20，x53=20，x11=30， 其余变量均为零，最优值为860 即：选择在A5建厂；第一个厂的产量全部给第一个销售地；第五个厂的产量平均运送给第二和第三个销地。 产销平衡。 * 解题（7） 解b)如果由于政策要求必须在A2，A3建一个厂，应在哪几个地方建厂 在以上模型上加一个约束条件 y2+y3=1， 用计算机可求得最优解如下： y2=1，y4=1， x41=30， x22=10，x12=10，x13=20， 其余变量均为零，最优值为940。 * 整数规划举例3——团体项目运动员选拔问题 有5名运动员的各种姿势和50米游泳成绩（秒），问如何从中选拔一个参加200米混合泳的接力队，使预期比赛成绩最好。 游泳姿势 赵 钱 张 王 周 仰泳 37.7 32.9 33.8 37.0 35.4 蛙泳 43.4 33.1 42.2 34.7 41.8 蝶泳 33.3 28.5 38.9 30.4 33.6 自由泳 29.2 26.4 29.6 28.5 31.1 钱以什么姿势的游泳？ * 解题 设运动员有i人，i=1-5；游泳姿势有j种，j=1-4； xij表示第i个人以第j种姿势参加比赛； aij表示表示第i个人以第j种姿势游泳的时间 可得该问题的数学模型： 最优组合： 张：仰泳； 王：蛙泳； 钱：蝶泳； 赵：自由泳； 预期成绩：126.2s * 本章强化训练 P100: 4.4 (a) * 整数规划解法2——分枝定界法 步骤： 1. 寻找替代问题并求解 2. 分枝与定界 3. 剪枝 * 基本思路 maxZ=CX AX=b X?0 (A) maxZ=CX AX=b X?0 X为整数 (B) (B)为(A)的松弛问题。 * (C) (D) (B) Xj ? i+1 (B) Xj ? i X* Xj* i+1 i * maxZ=40X1 + 90X2 9X1+7X2 ? 56 7X1+20X2 ? 70 X1 , X2? 0 X1 , X2为整数 例： * 解：先解该整数规划对应的松弛问题 X* = 4.809 1.817 Z* =355.890， 上界Z* 选X1分枝 问题(2) (1) X1 ? 4 问题(3) (1) X1 ? 5 * 选(2)继续分枝 问题(4) (2) X2 ? 2 问题(5) (2) X2 ? 3 解为 X1 =4 X2 =2.1 Z=349.0 解为 X1 =5 X2 =1.571 Z=341.39 * (1) 4.809 1.817 355.890 (2) 4 2.1 349.0 (3) 5 1.571 341.39 (4) 4 2 340 (5) 1.428 3 340 327.12 (6) 5.444 1 340 307.76 (7) 无解 X1? 4 X1? 5 X2? 2 X2? 1 X2? 2 X2? 3 * 整数规划解法3——割平面法 割平面法的基本思想： 在整数规划问题的松弛问题中依次引进线性约束条件(称Gomory约束或割平面)，使问题的可行域逐步缩小。但每次切割只割去问题的部分非整数解，直到使问题的目标函数值达到最优的整数点成为缩小后可行域的一个顶点，这样就可以用求解线性规划问题的方法找出这个最优解。 * 割平面法解题步骤 第一步：把问题中所有约束条件的系数均化为整数，若不考虑变量的整数约束，可得到该整数规划的松弛问题G0 ，求解G0，若得到整数解，求解结束；否则转入第二步； 第二步：找出非整数解变量中分数部分最大的一个基变量，处理得到Gomory约束； 第三步：将Gomory约束加到G0中得到新的线性规划问题G1 ； 第四步：重复第一至第三步一直到找出问题的整数最优解为止 。 * 割平面法实例 第一步：把问题中所有约束条件的系数均化为整数，若不考虑变量的整数约束，可得到该整数