整数规划-模型

1、1整数规划方法整数规划方法一一. .整数规划的一般模型整数规划的一般模型二二. .整数规划的求解方法整数规划的求解方法 三三.0-1.0-1整数规划整数规划 四四. .整数规划案例分析整数规划案例分析2一一. .整数规划的一般模型整数规划的一般模型1. 问题的提出：固定资源分配问题问题的提出：固定资源分配问题34 在这个问题中，所求解均是整数，初看起来，在这个问题中，所求解均是整数，初看起来，似乎只要把已得到的带有分数或小数的解经过似乎只要把已得到的带有分数或小数的解经过“舍入化整舍入化整”就可以了，实际上这常常是不行的，就可以了，实际上这常常是不行的，因为化整后不见得是可行解，或虽是可行解但

2、不因为化整后不见得是可行解，或虽是可行解但不一定是最优解。这种求最优整数解的问题就是整一定是最优解。这种求最优整数解的问题就是整数规划。数规划。 整数规划中如果所有的变量都限制为（非负）整数规划中如果所有的变量都限制为（非负）整数，称为纯整数规划；如果仅一部分变量限制整数，称为纯整数规划；如果仅一部分变量限制为整数，称为混合整数规划；整数规划一种特殊为整数，称为混合整数规划；整数规划一种特殊的情形是的情形是0-1规划，它的变量取值仅限于规划，它的变量取值仅限于0和和1。52. 整数规划模型的一般形式整数规划模型的一般形式问题是如何求解整数规划问题呢？问题是如何求解整数规划问题呢？能否设想先略去

3、决策变量整数约束，即变为线性能否设想先略去决策变量整数约束，即变为线性规划问题求解，再对其最优解进行取整处理呢？规划问题求解，再对其最优解进行取整处理呢？实际上，可借鉴这种思想来解决整数规划问题实际上，可借鉴这种思想来解决整数规划问题6二二. .整数规划的求解方法整数规划的求解方法1. 分枝定界法的基本思想（举例说明）分枝定界法的基本思想（举例说明）分枝定界法分枝定界法.ppt7 继续求解定界，重复下去，直到得到最优解继续求解定界，重复下去，直到得到最优解为止为止. .82. 分枝定界法的一般步骤分枝定界法的一般步骤 问题问题(B)(B)无可行解，则无可行解，则(A)(A)也无可行解，停止；也

4、无可行解，停止；91011123. 整数规划的整数规划的lingo解法解法11min(1,2,)0,(1,2, )njjjnijjijjjzc xa xb imxxjn为整数13例：一个简单的整数规划模型例：一个简单的整数规划模型1212121212max264520,0,zxxxxxxx xx x且取整数14其其lingolingo语句如下：语句如下：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;enddataOBJmax=sum(arrange(

5、j):c(j)*x(j);for(row(i):sum(arrange(j):a(i,j)*x(j)=0;);for(arrange(j):gin(x(j););END 运行该程序后可得最优解为（运行该程序后可得最优解为（0，4），目标函），目标函数最优值为数最优值为4.15三三.0-1.0-1整数规划整数规划1. 0-1整数规划的模型整数规划的模型162. 指派（分配）问题（指派（分配）问题（0-1规划的特例）规划的特例） 在生产管理上，总希望把人员最佳分派，在生产管理上，总希望把人员最佳分派，以发挥其最大工作效率，创造最大的价值。以发挥其最大工作效率，创造最大的价值。 例如：某部门有例如：

6、某部门有n n项任务，正好需要项任务，正好需要n n个个人去完成，由于任务的性质和各人的专长不人去完成，由于任务的性质和各人的专长不同，如果分配每个人仅能完成一项任务。同，如果分配每个人仅能完成一项任务。 如何分派使完成如何分派使完成n n项任务的总效益为最高项任务的总效益为最高（效益量化），这是典型的分配问题。（效益量化），这是典型的分配问题。17 （1 1）例例1 1：现在不妨设有现在不妨设有4 4个人，各有能力去个人，各有能力去完成完成4 4项科研任务中的任一项，由于项科研任务中的任一项，由于4 4个人的能力个人的能力和经验不同，所需完成各项任务的时间如下表：和经验不同，所需完成各项任务

7、的时间如下表： 项项目目人人员员ABCD甲甲乙乙丙丙丁丁2109715414813141611415139问如何分配何问如何分配何人去完成何项人去完成何项目使完成目使完成4 4项项任务所需总时任务所需总时间最少？间最少？18每每个个人人去去完完成成一一项项任任务务的的约约束束为为 111144434241343332312423222114131211xxxxxxxxxxxxxxxx 19目目标标函函数数： 444342413433323124232221141312119118713161491514410413152minxxxxxxxxxxxxxxxxz 2021 （2 2）指派问题的一

8、般模型指派问题的一般模型22 ), 2, 1,(10, 2, 1, 1, 2, 1, 111njixnjxnixijniijnjij或233.用用lingo求解求解 0-1整数规划模型整数规划模型MODEL:MODEL: sets: sets: row/1.m/:b; arrange/1.n/:c,x; link(row,arrange):a; endsets data: b=b(1),b(2),b(m); c=c(1),c(2),c(n); a=a(1,1),a(1,2),a(1,n), a(2,1),a(2,2),a(2,n), . . . . a(m,1),a(m,2),a(m,n);

9、enddata OBJ min=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):BIN(x(j);); END 11min(1,2,)01(1,2, )njjjnijjijjzc xa xb imxorjn24P16P16页例页例1 1用用lingolingo求解后，可知让甲求解后，可知让甲去完成任务去完成任务D D，乙完成任务，乙完成任务B B，丙完成，丙完成任务任务A A，丁完成任务，丁完成任务C C，所用时间最少，所用时间最少为为28.28.25四四. . 整数规划案例分析整数规划案例分析1. 兼职值班员问题兼职值班员问题26实验室开放时间为上午实验室开放时间为上午8:008:00至晚上至晚上10:00;10:00;开放时间内须有且仅有一名学生值班开放时间内须有且仅有一名学生值班; ;规定大学生每周值班不少于规定大学生每周值班不少于8 8小时小时; ;研究生每周值班不少于研究生每周值班不少于7 7小时小时; ;每名学生每周值班不超每名学生每周值班不超3 3次次; ;每次值班不少于每次值班不少于2 2小时小时; ;每天安