整数规划-模型研究.ppt

整数规划方法 一.整数规划的一般模型 * 一.整数规划的一般模型 二.整数规划的求解方法 三.0-1整数规划 四.整数规划案例分析 1. 问题的提出：固定资源分配问题 在这个问题中，所求解均是整数，初看起来，似乎只要把已得到的带有分数或小数的解经过“舍入化整”就可以了，实际上这常常是不行的，因为化整后不见得是可行解，或虽是可行解但不一定是最优解。这种求最优整数解的问题就是整数规划。 整数规划中如果所有的变量都限制为（非负）整数，称为纯整数规划；如果仅一部分变量限制为整数，称为混合整数规划；整数规划一种特殊的情形是0-1规划，它的变量取值仅限于0和1。 2. 整数规划模型的一般形式 问题是如何求解整数规划问题呢？ 能否设想先略去决策变量整数约束，即变为线性规划问题求解，再对其最优解进行取整处理呢？ 实际上，可借鉴这种思想来解决整数规划问题． 二.整数规划的求解方法 1. 分枝定界法的基本思想（举例说明） 分枝定界法.ppt 继续求解定界，重复下去，直到得到最优解为止. 2. 分枝定界法的一般步骤 问题(B)无可行解，则(A)也无可行解，停止； 3. 整数规划的lingo解法 例：一个简单的整数规划模型 其lingo语句如下： MODEL: sets: row/1..2/:b; arrange/1..2/:c,x; link(row,arrange):a; endsets data: b=6,20;c=1,1;a=2,1,4,5; enddata [OBJ]max=@sum(arrange(j):c(j)*x(j)); @for(row(i):@sum(arrange(j):a(i,j)*x(j))=b(i);); @for(arrange(j):x(j)=0;); @for(arrange(j):@gin(x(j));); END 运行该程序后可得最优解为（0，4），目标函数最优值为4. 三.0-1整数规划 1. 0-1整数规划的模型 2. 指派（分配）问题（0-1规划的特例） 在生产管理上，总希望把人员最佳分派，以发挥其最大工作效率，创造最大的价值。 例如：某部门有n项任务，正好需要n个人去完成，由于任务的性质和各人的专长不同，如果分配每个人仅能完成一项任务。 如何分派使完成n项任务的总效益为最高（效益量化），这是典型的分配问题。 （1）例1：现在不妨设有4个人，各有能力去完成4项科研任务中的任一项，由于4个人的能力和经验不同，所需完成各项任务的时间如下表： 问如何分配何人去完成何项目使完成4项任务所需总时间最少？ （2）指派问题的一般模型 3.用lingo求解 0-1整数规划模型 P16页例1用lingo求解后，可知让甲去完成任务D，乙完成任务B，丙完成任务A，丁完成任务C，所用时间最少为28.