苏大 张芳华 运筹学课件第六章 整数规划

第六章整数规划(IntegerProgramming)第七章整数规划本章主要教学内容整数规划的概念和模型整数规划的应用整数规划的解法第七章整数规划本章教学的基本要求1、掌握一般整数规划问题的概念及模型结构；2、理解割平面法与分支定界法的解题原理；3、能够运用割平面法与分支定界法求解一般整数规划问题；整数规划的基本概念变量的取值为整数的LP问题为整数规划问题。纯整数规划当要求全部变量取整数值时,称为纯整数规划混合整数规划当要求部分变量取整数值时,称为混合整数规划整数规划的概念6.1整数规划的概念和应用第七章整数规划第七章整数规划整数规划的模型整数规划的一般模型maxz=≤bi(i=1,………m)xj≥0,且为整数(j=1,………n)式中cj,aij,bi均为常数,此即为整数规划的一般形式.jnjjxc1jnjijxa1第七章整数规划整数规划的应用（一）投资决策问题:我们假定某个公司要对n个投资方案作出选择,我们设:n=可以投资的项目的个数,m=实施投资项目所需有关资源的种类数,这种资源包括资金,材料,人力等;bi=各种资源的拥有量(I=1,………m)aij=实施第j项投资所需消耗第i种资源的数量cj=实施第j项投资所能获得的收益公司的目标是希望获得最大收益,问应如何进行投资?第七章整数规划整数规划的应用（一）投资决策问题:jnjjxc1maxz=s.t.≤bi(i=1,2………m)xj=0或1(j=1,2………n)jnjijxa1此类模型为0-1规划问题,0-1变量又称为逻辑变量,通常用来表示选择性的决策.xj=0不投资xj=1投资例：背包问题:一个旅行者准备徒步旅行,为此他必须决定携带某些物品,设有n件物品可供他选择,每件物品的价值为cj其重量为aj,他能携带的最大重量为b旅行者的目标当然是希望旅途最愉快,即所带物品能给他的旅行带来最大的价值，问应该选择这些物品各多少件？第七章整数规划例：背包问题:maxz=s.t.≤bxj≥0xj为整数(j=1,2………n)jnjjxc1jnjijxa1这是一个最简单的投资问题,即只有一种资源的情形此时xj表示旅行者可以携带第j种物品的件数,第七章整数规划第七章整数规划•设一背包最大的装载重量为50公斤,现有三种物品,每种物品数量无限,其重量和单价如下表所示,请问:每种物品各取多少件装入背包,使其中物品的总价值最高。甲乙丙重量（公斤）104120单件价值177235例：项目选择设某市计划在今年修建几个大的工厂,经初步分析已提出有A1,A2,……A8这八个厂可供选择,但因资金有限,这八个厂不能同时都建,根据人民生活和工农发展的需要,要求在A1,A2,中至少选一个,在A3,A4,A5,中至少选两个,在A6,A7,A8,中至多选两个,估计建厂Aj,需投资aj,元,每年可获利cj元,现在总的资金只有b元,问应何安排投资项目(即建哪些工厂)才能使每年获利最大?第七章整数规划引入0-1变量xj如下:xj=1若Aj厂被选上(j=1,2………8)xj=0否则例：项目选择maxz=s.t.x1+x2≥1x3+x4+x5≥2x6+x7+x8≤2≤bxj=0或1(j=1,2………8)jjjxc81jjijxa81第七章整数规划第七章整数规划（二）固定成本问题设xj为采用第j条生产线的产量，则它的产品成本函数写成：Fj为采用第j条生产线时的固定成本为(j=1,2………n)，Cj(Xj)=CjXj+Fj若Xj＞00若Xj=0成本函数表达式不统一第七章整数规划可以引入如下的0-1变量Yj：Yj=1当采用第j条生产线时即当Xj＞0时；Yj=0当不采用第j条生产线时即当Xj=0时，于是可将Cj(Xj)写为：Cj(Xj)=CjXj+FjYj再注意上面关于Yj的条件可用下述线性不等式来代替：Xj≤UjYj,其中Uj是采用第j条生产线生产的最大数量第七章整数规划设某厂有n条生产线可用来生产同一种产品,现要求至少生产出这种产品M吨，已知采用第j条生产线时每吨产品的可变成本为cj(j=1,2………n)；采用第j条生产线时的固定成本为Fj(j=1,2………n)，现问应如何组织生产，即如何分配各条生产线的任务产量，才能使总成本最低？第七章整数规划minz=s.t.≥m0≤xj≤UjYjj=1,2……nYj=0或1j=1,2……n其中Uj：采用第j条生产线时能生产出产品的最大数量。)(1jijjnjiytxcnjjx1另见书P170例题第七章整数规划（三）多重约束的选择见书P171例题：上述结果可以推广到一般情况，假定在某一问题中有m个约束条件：现在需要其中有k个被满足，但事先不知是哪k个≤bii=1,2……mjjijxa第七章整数规划假设我们已找出m个常数Ui,使得对于一切可行的xj，都有则m个约束条件中至少要满足k个这一要求就可表示为≤bi+ui，i=1,2……mjjijxajjijxa≤bi+ui，i=1,2……m,1kmymiiyi=0或1，i=1,2……m各个yi中有m-k个等于1,而其余k个则等于0,这就使得有k个约束条件将被满足.舍入化整法先不考虑整数条件,而解一个相应的连续型问题,然后把连续的最优解取整到最接近的可行整数,当连续最优解的数值都较大时,上述做法基本可行。但是，这种舍入化整的办法可能导致解的可行性受到破坏。6.2整数规划的解法第七章整数规划舍入化整法maxz=-5x1+2x2s.t.-3x1+x2≤2x1+3x2≤40x1-x2≤0x1,x2,≥0,整数若不考虑整数条件,则求最优解为:x1=3.4,x2=12.2,maxz=7.4若用舍入化整法，则将x1=3,x2=12代入方程中,则有maxz′=9,此整数解不是可行解。A（3.4，12.2）本例题中最优点是C,即点(4,12),相应的z=4≤z=7.4C（4,12）B（3,12）第七章整数规划割平面法(或切割法)割平面法是以线性规划的解法为基础的,通过增加适当的约束条件,将连续问题的可行域一次一次割去一部分,直到连续最优解满足整数性条件为止。6.3整数规划的解法的基本思想第七章整数规划隐枚举法(或搜索法)隐枚举法的基本思想是将所有可行解的集合分成一些子集,从整体上估计最优解一定不会在某些子集中,然后把这些子集丢掉,以缩小解的检查范围,分支定界法就是其中的一种.6.3整数规划的解法的基本思想第七章整数规划第七章整数规划介绍两种整数规划的解法割平面法分支定界法第七章整数规划对已给的整数规划问题，先不考虑其整数条件，而解一个相应的线性规划问题。若此线性规划问题的最优解都是整数，则它也就是所求整数规划问题的最优解。若线性规划问题的最优解中至少有一个基变量取非整数值，而问题中要求它为整数，则对原来的线性规划问题增加一个线性约束条件（几何上称为割平面）再行求解。这个割平面将从原可行域中切去一部分，其中只包含相应线性规划问题的非整数最优解。而不包含整数最优解。割平面法第七章整数规划例6.2-1求解下述IP问题:maxz=x1+x2（1）s.t.-x1+x2≤1（2）3x1+x2≤4（3）x1,x2≥0（4）x1,x2,整数（5）纯整数规划的解法如不考虑条件（5）,容易求得相应的线性规划的最优解.增加非负松驰变量x3,x4,用单纯型表解题,见表6-1,从中得到非整数最优解第七章整数规划纯整数规划的解法x1x2x3x4右端z′00-1/2-1/2-5/2x110-1/41/43/4x2013/41/47/4表6-1非整数最优解:x1=3/4,x2=7/4,x3=0x4=0maxz=5/2LP问题的最优解不符合整数条件.因此要找到一条直线去切割可行域,去掉非整数最优解,而保留整数解第七章整数规划我们由最优表中得到变量间的关系式:X1-1/4x3+1/4x4=3/4（8）x2+3/4x3+1/4x4=7/4=1+3/4（9）纯整数规划的解法此时我们任选一个等式,通常取右端分数部分较大的那个等式,由于两个右端分数部分相等,我们任取一个。现取（9）式,令其非基变量和右端常数均分解为整数和非负真分数之和,其中,整数要求不超过原来的数值,0≤真分数≤1,移项则有x2+3/4x3+1/4x4=7/4=1+3/4将整数项移至左端，分数项移至右端,则有x2-1=3/4-(3/4x3+1/4x4)（10）第七章整数规划由于x1,x2，x3,x4都是非负整数，因此等式（10）的左端为整数,则右端也必为整数,纯整数规划的解法因此就有:3/4-(3/4x3+1/4x4)≤0（11）成立这是要求全部变量都取整数数时必须满足的一个约束条件,也是我们得到的一个切割方程,将它作为增加约束条件代入原方程继续运算。x2-1=3/4-(3/4x3+1/4x4)（10）又知(3/4x3+1/4x4)必为正数,因此有3/4-(3/4x3+1/4x4)≤3/4＜1则3/4-(3/4x3+1/4x4)必为小于1的整数,第七章整数规划变形为-3x3-x4≤-3纯整数规划的解法由3/4-(3/4x3+1/4x4)≤0（11）引入松驰变量x5,得到等式:-3x3-x4+x5=-3将这新的约束方程加到表6-1的最优表,得到表6-2纯整数规划的解法表6-2利用对偶单纯形法x5离基,x3进基x1x2x3x4x5右端z′00-1/2-1/20x110-1/41/403/4x2013/41/407/4x500-3-11-3z′000-1/3-16-2x1100××1x2010××1x30011/3-1/31x1=1，x2=1maxz=2＜maxz=2.5为最优整数解第七章整数规划第七章整数规划纯整数规划的解法新的约束条件-3x3-x4≤-3如果用x1,x2表示则为x2≤1如图所示A（3/4，7/4）1D（1，1）B第七章整数规划求一个切割方程的步骤1.令xi是相应线性规划最优解中为分数值的一个基变量,(通常取分数部分最大的bi所对应的xi,分数值相等时,则任选一个xi)由单纯形表的最优表得到关于xi的约束方程。2.将该约束方程右端常数和所有非整数系数均分解成整数部分与非负真分数（其中整数为不超过原数值的最大整数）。3.将整数项至左端，所有分数项移至右端。令右端分数部分小于等于零，即得到一个切割方程。第七章整数规划1.切割方程真正进行了切割,至少把非整数最优解这一点割掉了。2.没有割掉整数解,这是因为相应的线性规划的任意整数可行解都满足切割方程的缘故.3.在求解整数规划问题时,要求所有系数和右端常数要用整数表示,若所给某个约束中有系数或右端常数为真分数,则要将它们先化成整数再加入松驰变量.见书P176例题割平面法总结第七章整数规划分支定界法分支定界法的基本思想以求相应的线性规划问题的最优解为出发点，如果得到的解不符合整数条件，就将原规划问题分成几支，每支增加了约束条件，即缩小了可行解区域，可行解范围也随之缩小了，因而整数规划的最优值不会优于相应的线性规划最优值。“定界”是指为目标函数定界，以便自动舍去那些最优值较差的子问题，提高计算效率。第七章整数规划分支定界法解法书P182页例6.2-3分支定界法：原问题maxz=x1+7x2s.t.-x1+3x2≤12x1+x2≤10x1,x2≥0x1,x2,整数第七章整数规划maxz=x1+7x2s.t.-x1+3x2≤12x1+x2≤10x1,x2≥0x1,x2,整数分支定界法解法x1x2x3x4右边z'-2/3-5/2-43x211/41/411/2x11-1/43/49/2从x1,x2中任取一个加以研究，x1=9/2,因为x1为整数，所以必有x1≤4或者x2≥5,将其加到原来LP问题，成为两个互斥子问题，上述步骤即为分支。maxz=x1+7x2s.t.-x1+3x2≤12x1+x2≤10x1≤4x1,x2≥0x1,x2,整数maxz=x1+7x2s.t.-x1+3x2≤12x1+x2≤10x1≥5x1,x2≥0x1,x2,整数第七章整数规划Z=43（9/2，11/2）Z=