《第六章 整数规划》由会员分享，可在线阅读，更多相关《第六章 整数规划（52页珍藏版）》请在金锄头文库上搜索。
1、第六章 整数规划,(Integer Programming ),第七章 整数规划,本章主要教学内容,整数规划的概念和模型 整数规划的应用整数规划的解法,第七章 整数规划,本章教学的基本要求,1、掌握一般整数规划问题的概念及模型结构；2、理解割平面法与分支定界法的解题原理；3、能够运用割平面法与分支定界法求解一般整 数规划问题；,整数规划的基本概念 变量的取值为整数的LP问题为整数规划问题。纯整数规划 当要求全部变量取整数值时,称为纯整数规划 混合整数规划 当要求部分变量取整数值时,称为混合整数规划,整数规划的概念,6.1整数规划的概念和应用,第七章 整数规划,第七章 整数规划,整数规划的模型,
2、整数规划的一般模型,max z = bi (i=1,m) xj0,且为整数(j=1,n) 式中cj,aij,bi均为常数, 此即为整数规划的一般形式.,第七章 整数规划,整数规划的应用,（一）投资决策问题:,我们假定某个公司要对n个投资方案作出选择,我们设: n=可以投资的项目的个数, m=实施投资项目所需有关资源的种类数,这种 资源包括资金,材料,人力等; bi=各种资源的拥有量(I=1,m) aij=实施第j项投资所需消耗第i种资源的数量 cj=实施第j项投资所能获得的收益 公司的目标是希望获得最大收益,问应如何进行投资?,第七章 整数规划,整数规划的应用,（一）投资决策问题:,max z
3、 =s.t. bi (i=1,2m)xj=0或1 (j=1,2n),此类模型为0-1规划问题,0-1变量又称为逻辑变量, 通常用来表示选择性的决策.,xj=0 不投资xj=1 投资,例：背包问题:,一个旅行者准备徒步旅行,为此他必须决定携带某些物品, 设有n件物品可供他选择, 每件物品的价值为cj 其重量为aj, 他能携带的最大重量为b旅行者的目标当然是希望旅途最愉快,即所带物品能给他的旅行带来最大的价值，问应该选择这些物品各多少件？,第七章 整数规划,例：背包问题:,max z =s.t. bxj0 xj 为整数 (j=1,2n),这是一个最简单的投资问题,即只有一种资源的情形,此时xj表示
4、旅行者可以携带第j种物品的件数,第七章 整数规划,第七章 整数规划,设一背包最大的装载重量为50公斤,现有三种物品,每种物品数量无限,其重量和单价如下表所示,请问:每种物品各取多少件装入背包,使其中物品的总价值最高。,例：项目选择,设某市计划在今年修建几个大的工厂,经初步分析已提出有A1, A2,A8这八个厂可供选择,但因资金有限,这八个厂不能同时都建,根据人民生活和工农发展的需要, 要求在A1, A2,中至少选一个,在A3, A4, A5,中至少选两个,在A6, A7, A8,中至多选两个,估计建厂Aj,需投资aj,元,每年可获利cj元,现在总的资金只有b元,问应何安排投资项目(即建哪些工厂
5、)才能使每年获利最大?,第七章 整数规划,引入0-1变量xj如下: xj=1 若Aj厂被选上 (j=1,28)xj=0 否则,例：项目选择,max z =s.t. x1+x21 x3+x4+ x52 x6+x7+ x82 b xj=0或1(j=1,28),第七章 整数规划,第七章 整数规划,（二）固定成本问题,设xj为采用第j条生产线的产量，则它的产品成本函数写成：,Fj为采用第j条生产线时的固定成本为 (j=1,2n)，,成本函数表达式不统一,第七章 整数规划,可以引入如下的0-1变量Yj：,Yj=1 当采用第j条生产线时即当Xj0时；Yj=0 当不采用第j条生产线时即当Xj=0时， 于是可
6、将Cj(Xj)写为： Cj(Xj)= CjXj+FjYj,再注意上面关于Yj的条件可用下述线性不等式来代替： XjUjYj, 其中Uj是采用第j条生产线生产的最大数量,第七章 整数规划,设某厂有n条生产线可用来生产同一种产品,现要求至少生产出这种产品M吨，已知采用第j条生产线时每吨产品的 可变成本为 cj(j=1,2n)；采用第j条生产线时的 固定成本为Fj(j=1,2n)，现问应如何组织生产，即如何分配各条生产线的任务产量，才能使总成本最低？,第七章 整数规划,min z =s.t. m 0xjUjYj j=1,2n Yj=0或1 j=1,2n其中Uj：采用第j条生产线时能生产出产品的最大数
7、量。,另见书P170 例题,第七章 整数规划,（三）多重约束的选择,见书 P171 例题：,上述结果可以推广到一般情况，假定在某一问题中有m个约束条件：,现在需要其中有k个被满足，但事先不知是哪k个,bi i=1,2m,第七章 整数规划,假设我们已找出m个常数Ui,使得对于一切可行的xj，都有,则m个约束条件中至少要满足k个这一要求就可表示为,各个yi中有m-k个等于1,而其余k个则等于0, 这就使得有k个约束条件将被满足.,舍入化整法 先不考虑整数条件,而解一个相应的连续型问题,然后把连续的最优解取整到最接近的可行整数,当连续最优解的数值都较大时,上述做法基本可行。 但是，这种舍入化整的办法
8、可能导致解的可行性受到破坏 。,6.2 整数规划的解法,第七章 整数规划,舍入化整法,max z = -5x1+2x2s.t.-3x1+x22 x1+3x240 x1-x2 0 x1, x2,0,整数,若不考虑整数条件,则求最优解为: x1=3.4, x2=12.2, max z =7.4,若用舍入化整法，则将x1=3, x2=12代入方程中,则有maxz =9,此整数解不是可行解。,A（3.4，12.2）,本例题中最优点是C,即点(4,12),相应的z= 4z=7.4,C（4,12）,B（3,12）,第七章 整数规划,割平面法 (或切割法) 割平面法是以线性规划的解法为基础的, 通过增加适当
9、的约束条件,将连续问题的可行域一次一次割去一部分,直到连续最优解满足整数性条件为止。,6.3 整数规划的解法的基本思想,第七章 整数规划,隐枚举法 (或搜索法) 隐枚举法的基本思想是将所有可行解的集合分成一些子集,从整体上估计最优解一定不会在某些子集中,然后把这些子集丢掉,以缩小解的检查范围,分支定界法就是其中的一种.,6.3 整数规划的解法的基本思想,第七章 整数规划,第七章 整数规划,介绍两种整数规划的解法,割平面法分支定界法,第七章 整数规划,对已给的整数规划问题，先不考虑其整数条件，而解一个相应的线性规划问题。若此线性规划问题的最优解都是整数，则它也就是所求整数规划问题的最优解。若线性
10、规划问题的最优解中至少有一个基变量取非整数值，而问题中要求它为整数，则对原来的线性规划问题增加一个线性约束条件（几何上称为割平面）再行求解。这个割平面将从原可行域中切去一部分，其中只包含相应线性规划问题的非整数最优解。而不包含整数最优解。,割平面法,第七章 整数规划,例 6.2-1 求解下述IP问题: max z = x1+x2 （1）s.t. -x1+x21 （2） 3x1+x24 （3） x1,x2 0 （4） x1, x2,整数 （5）,纯整数规划的解法,如不考虑条件（5）,容易求得相应的线性规划的最优解.增加非负松驰变量x3, x4 ,用单纯型表解题,见表6-1,从中得到非整数最优解,
11、第七章 整数规划,纯整数规划的解法,表6-1,非整数最优解: x1=3/4, x2=7/4, x3=0 x4=0 max z =5/2,LP问题的最优解不符合整数条件.因此要找到一条直线去切割可行域,去掉非整数最优解,而保留整数解,第七章 整数规划,我们由最优表中得到变量间的关系式: X1 -1/4x3+ 1/4x4=3/4 （8） x2+3/4x3+1/4x4=7/4=1+3/4 （9）,纯整数规划的解法,此时我们任选一个等式,通常取右端分数部分较大的那个等式,由于两个右端分数部分相等,我们任取一个。现取（9）式,令其非基变量和右端常数均分解为整数和非负真分数之和,其中,整数要求不超过原来的
12、数值,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/41 则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进基,x1=1，x2=1 maxz=2 maxz=2.5为最优整数解,第七章 整数规划,第七章 整数规划,纯整数规划的解法,新的约束条件 -3x3-x4-3 如果用x1, x2 表示 则为 x21 如图所示,
