《运筹学课程06-整数规划》由会员分享，可在线阅读，更多相关《运筹学课程06-整数规划（76页珍藏版）》请在金锄头文库上搜索。
1、1,整数规划,Integer Linear Programming,整数规划的难度远大于一般线性规划,2, 整数规划的模型, 分支定界法, 割平面法, 01 整数规划, 指派问题,本章主要内容,3,一、整数规划的模型,1、案例：, 某财团有 万元的资金，经初期考察选中 个投资项目，每个项目只能投资一个。其中第 个项目需投资金额为 万元，预计5年后获利 万元，问应如何选择项目使得5年后总收益最大？,4,变量每个项目是否投资约束总金额不超过限制目标总收益最大,5,6,某公司计划在m个地点建厂，可供选择的地点有A1,A2Am ，它们的生产能力分别是a1,a2,am（假设生产同一产品）。第i个工厂的建
2、设费用为fi (i=1.2m),又有n个地点B1,B2, Bn 需要销售这种产品，其销量分别为b1.b2bn 。从工厂运往销地的单位运费为Cij。试决定应在哪些地方建厂，即满足各地需要，又使总建设费用和总运输费用最省？,7,设： xij 表示从工厂运往销地的运量(i=1.2m；j=1.2n), 1 在Ai建厂又设 yi （i=1.2m）0 不在Ai建厂模型：,8,某人出国留学打点行李，现有三个旅行包，容积大小分别为1000毫升、1500毫升和2000毫升，根据需要列出需带物品清单，其中一些物品是必带物品共有7件，其体积大小分别为400、300、150、250、450、760、190、（单位毫升
3、）。尚有10件可带可不带物品，如果不带将在目的地购买，通过网络查询可以得知其在目的地的价格（单位美元）。这些物品的容量及价格分别见下表，试给出一个合理的安排方案把物品放在三个旅行包里。,9,变量对每个物品要确定是否带同时要确定放在哪个包裹里，如果增加一个虚拟的包裹把不带的物品放在里面，则问题就转化为确定每个物品放在哪个包裹里。如果直接设变量为每个物品放在包裹的编号，则每个包裹所含物品的总容量就很难写成变量的函数。为此我们设变量为第i个物品是否放在第j个包裹中,10,约束,包裹容量限制,必带物品限制,选带物品限制,11,目标函数未带物品购买费用最小,12,13,2、总结：,特征变量整数性要求 来
4、源问题本身的要求；引入逻辑变量需要 性质可行域是离散集合,一般整数规划模型,14,依照决策变量取整要求的不同，整数规划可分为纯整数规划、全整数规划、混合整数规划、01整数规划,纯整数规划：所有决策变量要求取非负整数（这时引进的松弛变量和剩余变量可以不要求取整数）。,全整数规划：除了所有决策变量要求取非负整数外，系数和常数也要求取整数（这时引进的松弛变量和剩余变量也必须是整数）。,混合整数规划：只有一部分的决策变量要求取非负整数，另一部分可以取非负实数。,01整数规划：所有决策变量只能取 0 或 1 两个整数。,15,3、IP与LP关系：,设整数规划问题如下,首先不考虑整数约束，得到线性规划问题
5、,且为整数,16,用图解法求出最优解 x13/2, x2 = 10/3 且有Z = 29/6,x1,x2,3,3,(3/2,10/3),现求整数解（最优解）：如用“舍入取整法”可得到4个点即(1，3)， (2，3)，(1，4)， (2，4)。显然，它们都不可能是整数规划的最优解。,按整数规划约束条件，其可行解肯定在线性规划问题的可行域内且为整数点。故整数规划问题的可行解集是一个有限集，如图所示。,17,因此，可将集合内的整数点一一找出，其最大目标函数的值为最优解，此法为完全枚举法。如上例：其中（2，2）（3，1）点为最大值，Z=4。,目前，常用的求解整数规划的方法有：分枝定界法割平面法对于特别
6、的01规划问题采用隐枚举法和匈牙利法。,18,01 整数规划是一种特殊形式的整数规划，这时的决策变量xi 只取两个值0或1，一般的解法为隐枚举法。,例1、求解下列01 规划问题,二、01 整数规划,19,对于01 规划问题，由于每个变量只取0，1两个值，一般会用穷举法来解，即将所有的0，1 组合找出，使目标函数达到极值要求就可求得最优解。,但此法太繁琐，工作量相当大。而隐枚举法就是在此基础上，通过加入一定的条件，就能较快的求得最优解。,20,由上表可知，问题的最优解为 X*=( x1 =1 x2=0 x3=1 ) 由上表可知： x1 =0 x2=0 x3=1 是一个可行解，为尽快找到最优解，可
7、将3 x12 x25 x3 5 作为一个约束，凡是目标函数值小于5 的组合不必讨论，如下表。,21,指派问题的数学模型设n 个人被分配去做n 件工作，规定每个人只做一件工作，每件工作只有一个人去做。已知第I 个人去做第j 件工作的的效率（ 时间或费用）为Cij(i=1.2n;j=1.2n)并假设Cij 0。问应如何分配才能使总效率（ 时间或费用）最高？ 最小指派问题 最大指派问题,三、指派问题（ Assignment problem ）,22,设决策变量 1 分配第i 个人去做第j 件工作xij =0 相反 ( i,j=1.2. n ),其数学模型为：,23,指派问题是0-1 规划的特例，也是
8、运输问题的特例，当然可用整数规划，0-1 规划或运输问题的解法去求解，这就如同用单纯型法求解运输问题一样是不合算的。利用指派问题的特点可有更简便的解法，这就是匈牙利法（Hungarian method ）。,24,定理：在费用矩阵C=（cij）的任一行（列）中减去一个常数或加上一个常数不改变原问题的最优解,-b,25,匈牙利算法：,1、变换指派问题的系数矩阵（cij）为(bij)，使在(bij)的各行各列中都出现0元素，即(1) 从（cij）的每行元素都减去该行的最小元素； (2) 再从所得新系数矩阵的每列元素中减去该列的最小元素。,指派问题的最优解：若C中有n 个位于不同行不同列的零元素，则
9、令这些零元素对应的变量取1，其余变量取零，即得指派问题的最优解,26,例1：,27,2,4,9,7,4,2,28,2、进行试指派，以寻求最优解。在(bij)中找尽可能多的独立0元素，若能找出n个独立0元素，就以这n个独立0元素对应解矩阵(xij)中的元素为1，其余为0，这就得到最优解。找独立0元素，常用的步骤为：(1)从只有一个0元素的行(列)开始，给这个0元素加圈，记作 。然后划去 所在列(行)的其它0元素，记作 ；这表示这列所代表的任务已指派完，不必再考虑别人了。(2)给只有一个0元素的列(行)中的0元素加圈，记作；然后划去 所在行的0元素，记作 (3)反复进行(1)，(2)两步，直到尽可
10、能多的0元都被圈出和划掉为止。,29,(4)若仍有没有划圈的0元素，且同行(列)的0元素至少有两个，则从剩有0元素最少的行(列)开始，比较这行各0元素所在列中0元素的数目，选择0元素少的那列的这个0元素加圈(表示选择性多的要“礼让”选择性少的)。然后划掉同行同列的其它0元素。可反复进行，直到所有0元素都已圈出和划掉为止。（5）若 元素的数目m 等于矩阵的阶数n，那么这指派问题的最优解已得到。,30,31,32,例2 有一份中文说明书，需译成英、日、德、俄四种文字，分别记作A、B、C、D。现有甲、乙、丙、丁四人，他们将中文说明书译成不同语种的说明书所需时间如下表所示，问如何分派任务，可使总时间最
11、少？,33,5,第二步，试指派：,找到 3 个独立零元素但 m = 3 n = 4,第一步，变换系数矩阵：,34,（5）若 元素的数目m 等于矩阵的阶数n，那么这指派问题的最优解已得到。若m n, 则转入下一步。3、作最少的直线覆盖所有0元素。(1)对没有的行打号；(2)对已打号的行中所有含元素的列打号；(3)再对打有号的列中含 元素的行打号(4)重复(2)，(3)直到得不出新的打号的行、列为止；,35,(5)对没有打号的行画横线，有打号的列画纵线，这就得到覆盖所有0元素的最少直线数 l 。l 应等于m，若不相等，说明试指派过程有误，回到第二步(4)，另行试指派；若 lm n，须再变换当前的系
12、数矩阵，以找到n个独立的0元素，为此转第四步。4、变换矩阵(bij)以增加0元素。 在没有被直线覆盖的所有元素中找出最小元素，然后打各行都减去这最小元素；打各列都加上这最小元素（以保证系数矩阵中不出现负元素）。新系数矩阵的最优解和原问题仍相同。转回2。,36,第三步，作最少的直线覆盖所有0元素：,独立零元素的个数m等于最少直线数l，即lm=3n=4；,第四步，变换矩阵(bij)以增加0元素：没有被直线覆盖的所有元素中的最小元素为1，然后打各行都减去1；打各列都加上1，得如下矩阵，并转第二步进行试指派：,37,得到4个独立零元素， 所以最优解矩阵为：,目标函数值为：5,38,匈牙利算法的适用条件
13、, 要求所有 目标函数为min型对于max型目标函数（最大指派问题）：,39,四、分支定界法,基本思路,考虑纯整数问题：,相应的松弛问题：,40,分支定界法,分支定界法的基本思想 以求相应的线性规划问题的最优解为出发点，如果得到的解不符合整数条件，就将原规划问题分成几支，每支增加了约束条件，即缩小了可行解区域，可行解范围也随之缩小了，因而整数规划的最优值不会优于相应的线性规划最优值。 “定界”是指为目标函数定界，以便自动舍去那些最优值较差的子问题，提高计算效率。,41,第一步 寻求替代问题并求解,方法是放宽或取消原问题的某些约束，找出一个替代的问题，要求：容易求解并且原问题的解集应无例外的包含
14、在替代问题的解集中 如果替代问题的最优解是原问题的可行解，这个解就是原问题的最优解；否则，这个解的值是原问题最优解的上界（求极大时）或下界值（求极小时）,42,第二步 分支与定界,方法是将替代问题分成若干子问题，对子问题也要求容易求解，且各子问题的解的集合要包含原问题的解集。 对每个子问题求最优解，如该解满足原问题的约束，即找到了一个原问题的可行解；否则，该解为所属分支的边界值（对求最大问题该解为上界，对求最小问题该解为下界） 如果所有子问题的最优解均非原问题的可行解，则选取其边界值最大（求极大）或最小（求极小）的一个保留,43,第三步 剪枝,将各子问题边界值与保留的可行解的值进行比较。把边界
15、值劣于可行解的分支剪去。 如果除保留下来的可行解外，其余分支均被剪去，则该可行解就是原问题的最优解 否则回到第二步选取边界值最优的一个继续分支，如果计算中又出现新的可行解时，则与原可行解比较，保留最优的，并重复上述过程,44,记为（IP）,首先去掉整数约束，变成一般线性规划问题,记为（LP）,例题：,45,用图解法求（LP）的最优解，如图所示。,x1,x2,3,3,(18/11,40/11),对于x118/111.64，取值x1 1， x1 2 对于x2 =40/11 3.64，取值x2 3 ，x2 4 先将（LP）划分为（LP1）和（LP2）,取x1 1, x1 2,x118/11, x2 =40/11Z(0) =218/11(19.8)即Z 也是（IP）最小值的下限。,46,有下式：,现在只要求出（LP1）和（LP2）的最优解即可。,47,x1,x2,3,3,(18/11,40/11),
