整数规划-模型

整数规划方法一.整数规划的一般模型二.整数规划的求解方法三.0-1整数规划四.整数规划案例分析1一.整数规划的一般模型1.问题的提出：固定资源分配问题23在这个问题中，所求解均是整数，初看起来，似乎只要把已得到的带有分数或小数的解经过“舍入化整”就可以了，实际上这常常是不行的，因为化整后不见得是可行解，或虽是可行解但不一定是最优解。这种求最优整数解的问题就是整数规划。整数规划中如果所有的变量都限制为（非负）整数，称为纯整数规划；如果仅一部分变量限制为整数，称为混合整数规划；整数规划一种特殊的情形是0-1规划，它的变量取值仅限于0和1。42.整数规划模型的一般形式问题是如何求解整数规划问题呢？能否设想先略去决策变量整数约束，即变为线性规划问题求解，再对其最优解进行取整处理呢？实际上，可借鉴这种思想来解决整数规划问题．5二.整数规划的求解方法1.分枝定界法的基本思想（举例说明）分枝定界法.ppt6继续求解定界，重复下去，直到得到最优解为止.72.分枝定界法的一般步骤

问题(B)无可行解，则(A)也无可行解，停止；8910113.整数规划的lingo解法12例：一个简单的整数规划模型13其lingo语句如下：MODEL:sets:row/1..2/:b;arrange/1..2/:c,x;link(row,arrange):a;endsetsdata: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.14三.0-1整数规划1.0-1整数规划的模型152.指派（分配）问题（0-1规划的特例）

在生产管理上，总希望把人员最佳分派，以发挥其最大工作效率，创造最大的价值。例如：某部门有n项任务，正好需要n个人去完成，由于任务的性质和各人的专长不同，如果分配每个人仅能完成一项任务。如何分派使完成n项任务的总效益为最高（效益量化），这是典型的分配问题。16

（1）例1：现在不妨设有4个人，各有能力去完成4项科研任务中的任一项，由于4个人的能力和经验不同，所需完成各项任务的时间如下表：问如何分配何人去完成何项目使完成4项任务所需总时间最少？17181920

（2）指派问题的一般模型21223.用lingo求解0-1整数规划模型23P16页例1用lingo求解后，可知让甲去完成任务D，乙完成任务B，丙完成任务A，丁完成任务C，所用时间最少为28.24四.整数规划案例分析1.兼职值班员问题25实验室开放时间为上午8:00至晚上10:00;开放时间内须有且仅有一名学生值班;规定大学生每周值班不少于8小时;研究生每周值班不少于7小时;每名学生每周值班不超3次;每次值班不少于2小时;每天安排值班的学生不超过3人，且其中必须有一名