整数规划方法

1第十一章整数规划方法整数规划的一般模型；整数规划解的求解方法；整数规划的软件求解方法；0-1规划的模型与求解方法；整数规划的应用案例分析。一、整数规划的一般模型21.问题的提出:固定资源分配问题设某企业有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也都为整数．问题的目标函数为总利润求11nmijijijzrx的最大值．1111max,(1,2,,),,s.t.0(1,2,,),0(1,2,,).nmijijijnijjimjjjijjzrxxXjmaXMxinXjm且为整数且为整数4一、整数规划的一般模型在这个问题中，所求解均是整数，初看起来，似乎只要把已得到的带有分数或小数的解经过“舍入化整”就可以了，实际上这常常是不行的，因为化整后不见得是可行解，或虽是可行解但不一定是最优解。这种求最优整数解的问题就是整数规划。整数规划中如果所有的变量都限制为（非负）整数，称为纯整数规划；如果仅一部分变量限制为整数，称为混合整数规划；整数规划一种特殊的情形是0-1规划，它的变量取值仅限于0和1。52.整数规划模型的一般形式一、整数规划的一般模型(A)),,2,1(,0),,2,1(),(max(min)11njxxmibxaxczjjinjjijnjjj为整数•问题是如何求解整数规划问题呢？•能否设想先略去决策变量整数约束，即变为线性规划问题求解，再对其最优解进行取整处理呢？•实际上，可借鉴这种思想来解决整数规划问题．61.分枝定界法的基本思想二、整数规划求解方法(A)),,2,1(,0),,2,1(),(max(min)11njxxmibxaxczjjinjjijnjjj为整数(B)11max(min)(,)(1,2,,)0(1,2,,)njjjnijjijjzcxaxbimxjn将原问题（Ａ）中整数约束去掉变为问题（Ｂ）,求出（Ｂ）的最优解.71.分枝定界法的基本思想如果不是原问题（Ａ）的可行解，则通过附加线性不等式约束(整数)，将问题(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*，转下一步；2.分枝定界法一般步骤二、整数规划求解方法103)分枝：在问题(B)的最优解中任选一个不满足整数约束的变量jjbx，附加两个整数不等式约束：][jjbx和1][jjbx到问题(B)中，构成两个新的子问题)(1B和)(2B，求)(1B和)(2B的解。定界：对每一子问题的求解结果，找出最优值最小者为新的上界z，从所有符合整数约束条件的分枝中找出目标函数值最大的为新下界z2.分枝定界法一般步骤二、整数规划求解方法112.分枝定界法一般步骤4）比较与剪枝：各分枝问题的最优值同z比较，如果其值小于z，则这个分枝可以剪掉，以后不再考虑。如果其值大于z，且又不是（A）的可行解，则继续分枝，返回（3），直到最后得到最优解使zz*，即),,2,1(*njxj为最优解。二、整数规划求解方法分枝定界法.ppt123.割平面法的思想将原整数规划问题(A)去掉整数约束变为线性规划问题(B)，引入线性约束条件(称为Gomory约束，几何术语割平面)使问题(B)的可行域逐步缩小.每次切割掉的是问题非整数解的一部分，不切掉任何整数解，直到最后使目标函数达到最优的整数解成为可行域的一个顶点时，即问题最优解。利用线性规划的求解方法逐步缩小可行域，最后找到整数规划的最优解。二、整数规划求解方法考虑纯整数规划问题：取整数jjinjjijnjjjxnjxmibxaxcz,,2,10,,1max11设其中aij和bi皆为整数（若不为整数时，可乘上一个倍数化为整数）。割平面法是R.E.Gomory于1958年提出的一种方法，它主要用于求解纯ILP。割平面法是用增加新的约束来切割可行域，增加的新约束称为割平面方程或切割方程。其基本思路为：若其松弛问题的最优解X*不满足整数约束，则从X*的非整分量中选取一个，用以构造一个线性约束条件，将其加入原松弛问题中，形成一个新的线性规划，然后求解之。若新的最优解满足整数要求，则它就是整数规划的最优解；否则重复上述步骤，直到获得整数最优解为止。为最终获得整数最优解，每次增加的线性约束条件应当两个基本性质：（1）已获得的不符合整数要求的LP最优解不满足该线性约束条件，从而不可能在以后的解中出现；（2）凡整数可行解均满足该线性约束条件，因而整数最优解始终被保留在每次剩余的线性规划可行域中。是整数2121212121,0,431..maxxxxxxxxxtsxxz例1用割平面法求解整数规划问题0,,,431..max432142132121xxxxxxxxxxtsxxz步骤1：标准化其松弛问题B0Cj1100CBXBbx1x2x3x411x2x17/43/401103/4－1/41/41/4cj-zj00－1/2－1/2引进一个割平面来缩小可行域，割平面要切去松弛问题的非整数最优解而又不要切去问题的的任一个整数可行解。步骤2：求一个割平面方程（1）在最终表上任选一个含有不满足整数条件基变量的约束方程。如选x1，则含x1的约束方程为)3(434141431xxx（2）将所选择的约束方程中非基变量的系数及常数项进行拆分处理。具体规则是：将上述系数和常数项均拆分成一个整数加上一个非负真分数（纯小数）之和。则（3）式变为：)4(430410431431xxx很明显，（5）左端为整数，右端1，则有其右端0，即（3）将上述约束方程（4）重新组合。组合的原则是：将非负基变量系数及常数项中的非负真分数移到等号右端，将其他部分移到等号左端，即得：)5(4143434331xxxx等式左端实际上由三部分组成，常数项的整数部分，基变量及非基变量（含松弛变量或剩余变量），前两部分都是整数或应取整数，而松弛变量x3、x4由松弛问题标准型知，也应取非负整数（对于这一点，当原问题的约束方程组中的系数或常数项中有非整数时，要求将约束方程先化为成整数系数及整数常数项，然后再标准化，就可满足）。)6(43414343xx（4）将割平面方程加到松弛问题的约束方程中，构成新的松弛问题并求解（对偶单纯形法）。0,,,,434143431..00max543215434213214321xxxxxxxxxxxxxxtsxxxxz割平面方程Cj11000CBXBbx1x2x3x4x5110x2x1x57/43/4-3/40101003/4-1/4-3/41/41/4-1/4001cj-zj00-1/2-1/20110x2x1x311101010000101/31/31-1/3-4/3cj-zj00－1/3－2/3注释：（1）本题注只用一次割平面就求得了最优解，但大多数问题中不是只用一、二次割平面就能求得整数最优解。若一次割平面不能求得整数最优解，则按步骤2中的4个步骤，在松弛问题的最终单纯形表中找出第二个割平面方程，将此割平面方程加到伴随规划中，过程伴随规划，再用对偶单纯形法(单纯形法)求解。若求得了整数最优解，则停止计算，否则继续再作割平面，缩小可行域，直到求得整数最优解为止。（2）实际解题时，经验表明若从最终单纯形表中选择具有最大分数部分的非整分量所在行构造割平面约束，往往可以提高“切割”效果，减少“切割”次数。（3）在用割平面法解整数规划时，常会遇到收敛很慢的情形，因此实际中通常不单独使用。用割平面法求整数规划问题最优解的步骤：1.求整数规划问题所对应的线性规划问题的最优解。如果是整数解，则停止计算，否则，进行下一步。2.由最终单纯形表得到：是基变量iikkikixbxax:即之和，和非负真分数都分解为整数部分，将fNbaiik10ikikikikffNa10iiiiffNb代入上式整理得：kkikiikkikixffNxNx2.45=2+0.45-2.45=-3+0.55令上式的右边小于等于零，得到切割方程。即：kkikiikkikixffNxNxkkikixff03.将切割方程化为下列形式：是松驰变量inkiinkikxfxxf4.将切割方程加到最终单纯形表，用对偶单纯形法继续求解。注：1.切割方程真正进行了切割，至少将非整数最优解割掉了；(非整数最优解不满足切割方程）2.没有割掉整数解。(所有整数解都满足切割方程)5.如果求得整数解，停止计算，否则重复2—5步。4、整数规划的LINGO解法二、整数规划的求解方法23MODEL: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为整数241、0-1整数规划的模型三、0-1整数规划0-1规划一般模型:njjjxcz1max(min)),,2,1(,10),,2,1(),(1njxmibxajinjjij或如果整数线性规划问题的所有决策变量ix仅限于取0或1两个值，则称此问题为0-1线性规划，简称为0-1规划。252、指派（或分配）问题三、0-1整数规划在生产管理上，总希望把人员最佳分派，以发挥其最大工作效率，创造最大的价值。例如：某部门有n项任务，正好需要n个人去完成，由于任务的性质和各人的专长不同，如果分配每个人仅能完成一项任务。如何分派使完成n项任务的总效益为最高（效益量化），这是典型的分配问题。2.指派（或分配）问题26现在不妨设有4个人，各有能力去完成4项科研任务中的任一项，由于4个人