第7章整数规划11.ppt

《第7章整数规划11.ppt》由会员分享，可在线阅读，更多相关《第7章整数规划11.ppt（59页珍藏版）》请在三一办公上搜索。

1、第七章 整数规划,1整数规划的图解法 2整数规划的计算机求解 3整数规划的应用 4整数规划的分枝定界法,7.1 引言,在工程设计和企业管理中，常会遇到要求决策变量取离散的非负整数值的线性规划问题。例如，最优调度的车辆数，设置的销售网点数，指派工作的人数等。这类问题在形式上与线性规划类似，只是比线性规划增加了某些约束条件，来限制全部或部分决策变量必须取离散的非负整数值。我们称之为整数线性规划问题，也经常简称为整数规划问题。,在整数规划中，如果所有的变量都为非负整数，则称为纯整数规划问题；如果有一部分变量为非负整数，则称之为混合整数规划问题。所有决策变量均要求为0或1，则称之为纯 01 整数规划。

2、部分决策变量要求为0或1，则称之为混合01 整数规划。,整数规划是一类要求变量取整数值的数学规划，可分成线性和非线性两类。求整数解的线性规划问题，不是用四舍五入法或去尾法对线性规划的非整数解加以处理都能解决的，而要用整数规划的方法加以解决。,例7-1 求下列问题：Max Z=3x1+13x2s.t.2x1+9x2 40 11x1-8x2 82 x1,x2 0,且取整数值,7.2整数规划的图解法,O 1 2 3 4 5 6 7 8 9 10,5 4 3 2 1,x1,x2,I(2,4),B(9.2,2.4),A,D,可行域OABD内整数点，放弃整数要求后，最优解B(9.2,2.4)Z0=58.8

3、，而原整数规划最优解I(2,4)Z0=58，实际上B附近四个整点(9,2)(10,2)(9,3)(10,3)都不是原规划最优解。,O 1 2 3 4 5 6 7 8 9 10,5 4 3 2 1,x1,x2,I(2,4),B(9.2,2.4),A,D,假如能求出可行域的“整点凸包”（包含所有整点的最小多边形OEFGHIJ），则可在此凸包上求线性规划的解，即为原问题的解。但求“整点凸包”十分困难。,E,F,G,H,I,J,O 1 2 3 4 5 6 7 8 9 10,5 4 3 2 1,x1,x2,I(2,4),B(9.2,2.4),A,D,假如把可行域分解成五个互不相交的子问题P1 P2 P3

4、 P4 P5之和,P3 P5的定义域都是空集,而放弃整数要求后P1最优解I(2,4),Z1=58 P2最优解(6,3),Z2=57,P4最优解(9,2),Z4=53,P1,P2,P4,X1 2,X1 6,X2 3,X2 2,X1 3,X1 7,X2 4,X2 3,P1,P5,P4,P2,P3,P,性质1：任何求最大目标函数值的纯整数规划或混合整数规划的最大目标函数值小于或等于相应的线性规划的最大目标函数值；任何求最小目标函数值的纯整数规划或混合整数规划的最小目标函数值大于或等于相应的线性规划的最小目标函数值。,例2：Max z=3x1+x2+3x3 s.t.-x1+2x2+x3 4 4x2-3

5、x3 2 x1-3x2+2x3 3 x1,x2,x3 0 且为整数,7.3整数规划的计算机求解,例3：Max z=3x1+x2+3x3 s.t.-x1+2x2+x3 4 4x2-3x3 2 x1-3x2+2x3 3 x3 1 x1,x2,x3 0,x1，x3 为整数,x3为0-1变量,7.4整数规划的应用,一、投资场所的选择 例4、京成畜产品公司计划在市区的东、西、南、北四区建立销售门市部，拟议中有10个位置 Aj(j1，2，3，10)可供选择，考虑到各地区居民的消费水平及居民居住密集度，规定：在东区由A1，A2，A3 三个点至多选择两个；在西区由A4，A5 两个点中至少选一个；在南区由A6，

6、A7 两个点中至少选一个；在北区由A8，A9，A10 三个点中至少选两个。,Aj 各点的设备投资及每年可获利润由于地点不同都是不一样的，预测情况见表所示(单位：万元)。但投资总额不能超过720万元，问应选择哪几个销售点，可使年利润为最大?,解：设：0-1变量 xi=1(Ai 点被选用）或 0(Ai 点没被选用）。这样我们可建立如下的数学模型：Maxz=36x1+40 x2+50 x3+22x4+20 x5+30 x6+25x7+48x8+58x9+61x10s.t.100 x1+120 x2+150 x3+80 x4+70 x5+90 x6+80 x7+140 x8+160 x9+180 x1

7、0 720 x1+x2+x3 2 x4+x5 1 x6+x7 1 x8+x9+x10 2 xj 0 且xj 为0-1变量，i=1,2,3,10,0-1变量的概念 0-1变量：一种逻辑变量，常用来表示系统处于某个特定状态，或者决策时是否取某个特定方案。,固定费用问题 例：有三种资源被用于生产三种产品，资源量、产品单件可变费用售价、资源单耗量及组织三种产品生产的固定费用见下表。要求制定一个生产计划使总收益为最大。,设xj 为生产第 j 种产品的产量。y为0-1变量Max Z=4x1+5x2+6x3-100y1-150y2-200y3,2x1+4x2+8x35002x1+3x2+4x3300 x1+

8、2x2+3x3100 x1 My1x2 My2x3 My3xj 0且为整数，j=1,2,3yj=0或1，j=1,2,3,指派问题,指派问题：有n项工作，恰好有n个人去承担，每个人的专长不同，做每项工作的效率不同，应派哪个人去完成哪项工作，使总效率最高。,例：有一份中文说明书，需译成英、日、德、俄四种文字。表格如下：,丁,人员,甲,乙,丙,任务,E,G,J,R,21097,154148,13141611,415139,人,工作,1 2n,1 2 n,应派哪个人去完成哪项工作，使总效率最高。,当指派第 个人完成第 项任务,当不指派第 个人完成第 项任务,数学模型：设 是第 个人完成第 项任务的效率

9、，=1，2，n.引入变量，其取值为1或0。,当指派第 个人完成第 项任务,当不指派第 个人完成第 项任务,第 项任务只能有一个人来完成,第 个人只能完成一项任务,引入变量，其取值为1或0，=1，2，n.,当指派第 个人完成第 项任务,当不指派第 个人完成第 项任务,第 项任务只能有一个人来完成,第 个人只能完成一项任务,7.5整数规划的分枝定界法,分枝定界法是求解整数规划的一种常用的有效的方法，它既能解决纯整数规划的问题，又能解决混合整数规划的问题。大多数求解整数规划的商用软件就是基于分枝定界法而编制成的。,分枝定界解法（Branch and Bound Method)原问题的松驰问题：任何整

10、数规划（IP），凡放弃某些约束条件（如整数要求）后，所得到的问题（LP）都称为（IP）的松驰问题。,分枝定界法步骤一般求解对应的松驰问题，可能会出现下面几种情况：若所得的最优解的各分量恰好是整数，则这个解也是原整数规划的最优解，计算结束。,若松驰问题无可行解，则原整数规划问题也无可行解，计算结束。若松驰问题有最优解，但其各分量不全是整数，则这个解不是原整数规划的最优解，转下一步。,从不满足整数条件的基变量中任选 一个xl进行分枝，它必须满足xl xl 或xl xl+1中的一个，把这两个约束条件加进原问题中，形成两个互不相容的子问题（两分法）。,定界：把满足整数条件各分枝的最优目标函数值作为上（

11、下）界，用它来判断分枝是保留还是剪枝。剪枝：把那些子问题的最优值与界值比较，凡不优或不能更优的分枝全剪掉，直到每个分枝都查清为止。,分枝定界法是先求解整数规划的线性规划问题，如果其最优解不符合整数条件，则求出整数规划的上下界，用增加约束条件的办法，把相应的线性规划的可行域分成子区域（称为分枝），再求解这些子区域上的线性规划问题，不断缩小整数规划的上下界的距离，最后得整数规划的最优解。,例 用分枝定界法求解：Max Z=4x1+3x2s.t.3x1+4x2 12 4x1+2x2 9 x1,x2 0且都为整数用单纯形法可解得相应的松驰问题的最优解（6/5，21/10）Z=111/10为各分枝的上界

12、。,0 1 2 3 4,4 3 2 1,x1,x2,分枝：X1 1,x1 2,P1,P2,两个子问题：（P1）Max Z=4x1+3x2 s.t.3x1+4x2 12 4x1+2x2 9 x1 1且为整数 x1,x2 0 用单纯形法可解得相应的（P1）的最优解（1，9/4）Z=10(3/4),（P2）Max Z=4x1+3x2 s.t.3x1+4x2 12 4x1+2x2 9 x1 2且为整数 x1,x2 0用单纯形法可解得相应的（P2）的最优解（2，1/2）Z=9(1/2),0 1 2 3 4,4 3 2 1,x1,x2,再对（P1）分枝：X1 1（P3）x2 2（P4）x2 3,P1,P2

13、,P3,P4,（P1）两个子问题：（P3）Max Z=4x1+3x2 s.t.3x1+4x2 12 4x1+2x2 9 x1,x2 0,x1 1,x2 2整数用单纯形法可解得相应的（P3）的最优解（1，2）Z=10,（P1）两个子问题：（P4）Max Z=4x1+3x2 s.t.3x1+4x2 12 4x1+2x2 9 x1,x2 0,x1 1,x2 3整数用单纯形法可解得相应的（P4）的最优解（0，3）Z=9,X1 2,X2 2,X1 1,X2 3,P1:(1,9/4)Z=10(3/4),P4:(0,3)Z=9,P2:(2,1/2)Z=9(1/2),P3:(1,2)Z=10,P:(6/5,2

14、1/10)Z=111/10,原问题的最优解（1，2）Z=10,例 用分枝定界法求解：Min Z=x1+4x2s.t.2x1+x2 8 x1+2x2 6 x1,x2 0 且都为整数用单纯形法可解得相应的松驰问题的最优解（10/3，4/3）Z=26/3为各分枝的下界。,0 1 2 3 4 5 6,8 7 6 5 4 3 2 1,x1,x2,p,0 1 2 3 4 5 6,8 7 6 5 4 3 2 1,x1,x2,p,P1,选 x1进行分枝：(P1)x1 3(P2)x1 4 为空集,（P1）Min Z=x1+4x2s.t.2x1+x2 8 x1+2x2 6 x1,x2 0 x1 3 整数用单纯形法

15、可解得（P1）的最优解（3，3/2）Z=9,（P2）Min Z=x1+4x2s.t.2x1+x2 8 x1+2x2 6 x1,x2 0 x1 4 整数无可行解。,0 1 2 3 4 5 6,8 7 6 5 4 3 2 1,x1,x2,p,对(P1)x1 3 选 x2进行分枝：(P3)x2 1无可行解(P4)x2 2,P4,（P3）Min Z=x1+4x2s.t.2x1+x2 8 x1+2x2 6 x1,x2 0，x1 3，x2 1整数无可行解。,（P4）Min Z=x1+4x2s.t.2x1+x2 8 x1+2x2 6 x1,x2 0，x1 3，x2 2整数用单纯形法可解得（P4）的最优解（2

16、，2）Z=10,X1 4,X2 1,X1 3,X2 2,P1:(3,3/2)Z=9,P4:(2,2)Z=10,P2:无可行解,P3:无可行解,P:(10/3,4/3)Z=26/3,原问题的最优解（2，2）Z=10,7.6 指派问题,一、典型的指派问题 某单位需完成n项任务，恰有n个人可以承担，由于每个人的专长不同，各人完成任务的效率不同，各人完成一项任务的同时，不能同时去做其它任务，如何分配任务会使所需的时间最小或成本最低。,例：有一份中文说明书，需译成英、日、德、俄四种文字，分别记做E、J、G、R。现有甲、乙、丙、丁4人，他们将中文说明书翻译成不同语种的说明书所需的时间如下，问应指派何人去完

17、成何种工作，使所需总时间最少？,用匈牙利算法求解下面的指派问题，使得总的费用最小。,匈牙利算法的步骤：（1）变换系数矩阵，使其每行每列都出现0元素。首先每行减去该行最小数，再每列减去该列最小数。,(2)进行试分派，寻求最优解。经第（1）步变换后，系数矩阵每行每列都已有了0元素，但需找出n个独立的0元素，为此，按下列的步骤进行。,-4-2-3-3,-1,从只有一个0元素的行（列）的0元素开始，给这个0元素加圈，即作，这表示对这行所代表的人，只有一种任务可分派。然后划去所在列（行）的其它0元素，记作，这表示这列所代表的任务已分派完，不必再考虑别人了。,给只有一个0元素的列(行)的元素加圈，记作；然

18、后划去所在的行的其它0元素，即作。,若仍有没有圈出或划掉的0元素，且同行（列）的0元素至少有2个，则找出0元素的闭回路，任选一个0元素加圈，破闭回路，直到所有0元素都已圈出和划掉为止。列如：,反复进行、两步，直到所有0元素都被圈出或划掉为止。转第步。,若元素的数目等于矩阵的阶数，那末，这分派问题的最优解已经得到，否则转第（3）步。,（3）作最少的直线覆盖所有的0元素，以确定该系数矩阵能找到最多的独立0元素。为此按以下步骤进行：对没有的行打号；对已打的行中所有0元素所对应的列打号；再对打有的列中元素所对应的行打号；重复、，直到得不出新的打号的行、列为止。对没有打号的行画一横线，有打号的列画一纵线，这就得到覆盖所有的0元素的最少直线数。,做最少直线,（4）在未被直线覆盖的部分中找出最小元素，然后在打行各元素中都减去这最小元素，而在打列的各元素都加上这最小元素。这样得到新的系数矩阵（它的最优解和原问题相同）。,调整后，再试指派,指派结果：第1个人做第3个工作；第2个人做第1个工作第3个人做第2个工作；第4个人做第4个工作,调整后，再试指派,四、一般的指派问题1.最大化指派问题（用最大元素-所有元素化成最小化问题）2.人数和事数不等3.一个人可做几件事的指派问题4.某件事一定不能由某人做,