整数规划-模型

1整数规划方法一.整数规划的一般模型二.整数规划的求解方法三.0-1整数规划四.整数规划案例分析2一.整数规划的一般模型1.问题的提出：固定资源分配问题设某企业有n个生产车间需要m种资源，对于第i个生产车间分别利用第j种资源ijx进行生产，单位资源可以获得利润为ijr(1,2,,;1,2,,)injm．若第j种资源的单位价格为(1,2,,)jajm，该企业现有资金M元.试问该企业应购买多少第j种资源(总量为jX），又如何分配给所属的n个生产车间，使得总利润最大？3解设决策变量为(1,2,,;1,2,,)ijxinjm表示分配给第i个生产车间的第j种资源的资源量，均为非负整数，第j种资源的需求总量(1,2,,)jXjm也都为整数．1111max,(1,2,,),,s.t.0(1,2,,),0(1,2,,).nmijijijnijjimjjjijjzrxxXjmaXMxinXjm且为整数且为整数问题的目标函数为总利润求11nmijijijzrx的最大值．4在这个问题中，所求解均是整数，初看起来，似乎只要把已得到的带有分数或小数的解经过“舍入化整”就可以了，实际上这常常是不行的，因为化整后不见得是可行解，或虽是可行解但不一定是最优解。这种求最优整数解的问题就是整数规划。整数规划中如果所有的变量都限制为（非负）整数，称为纯整数规划；如果仅一部分变量限制为整数，称为混合整数规划；整数规划一种特殊的情形是0-1规划，它的变量取值仅限于0和1。52.整数规划模型的一般形式(A)),,2,1(,0),,2,1(),(max(min)11njxxmibxaxczjjinjjijnjjj为整数•问题是如何求解整数规划问题呢？•能否设想先略去决策变量整数约束，即变为线性规划问题求解，再对其最优解进行取整处理呢？•实际上，可借鉴这种思想来解决整数规划问题．6二.整数规划的求解方法1.分枝定界法的基本思想（举例说明）(A)),,2,1(,0),,2,1(),(max(min)11njxxmibxaxczjjinjjijnjjj为整数(B)11max(min)(,)(1,2,,)0(1,2,,)njjjnijjijjzcxaxbimxjn将原问题（Ａ）中整数约束去掉变为问题（Ｂ）,求出（Ｂ）的最优解.分枝定界法.ppt7如果不是原问题（Ａ）的可行解，则通过附加线性不等式约束(整数)，将问题(B)分枝变为若干子问题),,2,1)((IiBi，即对每一个非整变量附加两个互相排斥（不交叉）的整型约束，就得两个子问题.继续求解定界，重复下去，直到得到最优解为止.82.分枝定界法的一般步骤1)将原整数规划问题（A）去掉所有的整数约束变为线性规划问题（B），用线性规划的方法求解问题（B）:•问题(B)无可行解，则(A)也无可行解，停止；问题(B)有最优解*X，并是(A)的可行解，则此解就是(A)的最优解，计算结束；问题(B)有最优解*X，但不是(A)的可行解，转下一步。92）将*X代入目标函数，其值记为z，并用观察法找出（A）的一个可行解（整数解，不妨可取),,2,1(0njxj），求得目标函数值（下界值），记为z，则（A）的最优值记为*z，即有zzz*，转下一步；103)分枝：在问题(B)的最优解中任选一个不满足整数约束的变量jjbx，附加两个整数不等式约束：][jjbx和1][jjbx到问题(B)中，构成两个新的子问题)(1B和)(2B，求)(1B和)(2B的解。定界：对每一子问题的求解结果，找出最优值最小者为新的上界z，从所有符合整数约束条件的分枝中找出目标函数值最大的为新下界z114）比较与剪枝：各分枝问题的最优值同z比较，如果其值小于z，则这个分枝可以剪掉，以后不再考虑。如果其值大于z，且又不是（A）的可行解，则继续分枝，返回（3），直到最后得到最优解使zz*，即),,2,1(*njxj为最优解。123.整数规划的lingo解法MODEL:sets:row/1..m/:b;arrange/1..n/:c,x;link(row,arrange):a;endsetsdata: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(m,1),a(m,2),…,a(m,n);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):@GIN(x(j)););END11min(1,2,,)0,(1,2,,)njjjnijjijjjzcxaxbimxxjn为整数13例：一个简单的整数规划模型1212121212max264520,0,zxxxxxxxxxx且取整数14其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.15三.0-1整数规划1.0-1整数规划的模型如果整数线性规划问题的所有决策变量ix仅限于取0或1两个值，则称此问题为0-1线性规划，简称为0-1规划。0-1规划一般模型:njjjxcz1max(min)),,2,1(,10),,2,1(),(1njxmibxajinjjij或162.指派（分配）问题（0-1规划的特例）在生产管理上，总希望把人员最佳分派，以发挥其最大工作效率，创造最大的价值。例如：某部门有n项任务，正好需要n个人去完成，由于任务的性质和各人的专长不同，如果分配每个人仅能完成一项任务。如何分派使完成n项任务的总效益为最高（效益量化），这是典型的分配问题。17（1）例1：现在不妨设有4个人，各有能力去完成4项科研任务中的任一项，由于4个人的能力和经验不同，所需完成各项任务的时间如下表：项目人员ABCD甲乙丙丁2109715414813141611415139问如何分配何人去完成何项目使完成4项任务所需总时间最少？18建立模型：设ijx表示第i个人去完成第j项任务，则项任务时个人不去完成第当第项任务时个人去完成第当第jijixij,0,1每个人去完成一项任务的约束为111144434241343332312423222114131211xxxxxxxxxxxxxxxx每一项任务必有一人完成的约束：111144342414433323134232221241312111xxxxxxxxxxxxxxxx19目标函数：444342413433323124232221141312119118713161491514410413152minxxxxxxxxxxxxxxxxz记系数矩阵为9118713161491514410411152ijc称其为效益（价值）矩阵.ijc表示第i个人去完成第j项任务时有关的效益（时间、费用、价值等）。则目标函数可表示为ijijijxcz4141min20)4,3,2,1,(1034,2,1,14,3,2,1,14141jiorxjxixijijiijj故模型为：ijijijxcz4141min21（2）指派问题的一般模型设指派问题有相应的系数矩阵nnijc，其元素ijc表示分配第i个人去完成第j项任务时的效益（0），或者说：以ijc表示给定的第i单位资源分配用于第j项活动时的有关效益。设问题的决策变量为ijx是0-1变量，即项活动时个单位资源用于第当不分配第项活动时个单位资源用于第当分配第jijixij,0,122其数学模型为ijninjijxcz11min),,2,1,(10,,2,1,1,,2,1,111njixnjxnixijniijnjij或233.用lingo求解0-1整数规划模型MODEL:sets:row/1..m/:b;arrange/1..n/:c,x;link(row,arrange):a;endsetsdata: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);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)););END11min(1,2,,)01(1,2,,)njjjnijjijjzcxaxbimxorjn24P16页例1用lingo求解后，可知让甲去完成任务D，乙完成任务B，丙完成任务A，丁完成任务C，所用时间最少为28.25四.整数规划案例分析1.兼职值班员问题某大学实验室准备聘请4名大学生(代号为1、2、3、4)和2名研究生（代号为5、6）值班答疑。已知每人从周一到周日每天最多可以安排的值班时间及每人每小时值班的报酬如下表所示：每天最多可安排的值班时间值班员代号报酬(元/小时)周一周二周三周四周五周六周日1234561010991516606071200606001248305121255604012304801200606301226•实验室开放时间为上午8:00至晚上10:00;•开放时间内须有且仅有一名学生值班;•规定大学生每周值班不少于8小时;•研究生每周值班不少于7小时;•每名学生每周值班不超3次;•每次值班不少于2小时;•每天安排值班的学生不超过3人，且其中必须有一名研究生.试为该实验室安排一张人员的值班表，使总支付的报酬额最少。27设ijx为学生i在周j的值班时间;1,0,ijijy当安排学生在周值班时否则，用ija代表学生i在周j最多可值班的值班时间;ic为学生i的每小时的报酬;问题有下面的0-1规划模型286711717161716561min2(1,2,,6;1,2,,7)8(1,2,3,4)7(5,6)..14(1,2,,7)3,(1,2,,6)3,1(1,2,7)0,01(1,2,,6;1,iijijijijijijijjijjijiijjijjjiijijzcxyxayijxixistxjyiyyyjxyij或2,,7)问题的数学模型：29用LINGO软件求可得结果:11131522243235364